Determining node density to guarantee average latency in duty-cycled wireless sensor networks
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
DETERMINING NODE DENSITY TO GUARANTEE AVERAGE
LATENCY IN DUTY-CYCLED WIRELESS SENSOR NETWORKS
Dao Thi Nga*, Bui Minh Tin, Truong Anh Dung
Le Quy Don Technical University
Abstract
Some applications of Internet of Things (IoTs) require that generated data are delivered to
the sink within an end-to-end (E2E) delay bound. Moreover, to save energy consumption or
to lengthen the network lifetime, a duty cycle scheme is applied in which sensor nodes
periodically switch the radio on and off. In the duty-cycled networks, packet delay is
greatly affected by node deployment, therefore we aim to determine node density in a
wireless sensor network in order to guarantee the average E2E delay given network
parameters using the probability theory. Simulation results show that the proposed node
deployment method consumes less energy while requiring a smaller number of sensor
nodes than those of other existing works.
Keywords: Energy consumption; routing scheme; delay requirement; wireless sensor networks.
1. Introduction
Thanks to the development of low-cost and multi-functional sensors, wireless
sensor networks (WSNs) have been widely used in many areas, such as military,
surveillance missions, industry, and agriculture, among others [1, 2]. In delay-sensitive
WSNs, there is a demand that the E2E packet delay is lower than a given delay
requirement. For example, detecting abnormal behavior (e.g., fire, gas leakage) should
be reported to the operator within a threshold value. Therefore, the main purpose of this
work lies on designing a wireless sensor network which guarantees the E2E packet
delay while consumes a small amount of energy.
For reducing the energy consumption, a duty-cycling technique can be applied, in
which nodes become active during a wake-up period, and sleep for the rest of a duty
cycle interval [3]. Since the data rate in WSNs is quite low, using the duty-cycling
technique is a good choice to preserve the energy of sensors. While using this technique,
two important factors, i.e., the duty-cycle interval and node deployment, which have
great impacts on the E2E delay, should be considered. More specifically, the packet
latency is directly proportional to the duty-cycle interval and inversely proportional to
node density of networks. Therefore, a node deployment strategy is introduced to meet
* Email: [email protected]
72
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
the delay requirement for a given duty-cycle interval. Note that node deployment
algorithms in the literature [4-8] generally focused on addressing the energy imbalance
problem in the network, i.e., some nodes die early while other sensors still have plenty
of energy. For example, in [5] they assumed that the maximum transmission range of
nodes in a concentric layer is used as the layer width. For energy consumption balance,
the authors computed the nodes’ communication range in each layer given network
parameters. Meanwhile, in [4] Wu et al. made an assumption that the whole area was
classified into a number of concentric layers and all nodes shared the same transmission
range. Then, it was proved that sub-balanced energy consumption can be obtained if the
number of nodes from the outermost layer increases with the geometric rule. Despite of
achieving energy balance, the existing algorithms did not consider the packet latency
deadline, which is unsuitable for time-strict applications, e.g., fire detection.
To this end, we propose a node deployment algorithm, which aims to satisfy a
given E2E deadline. Specifically, the one-hop packet delay is first estimated and then
the E2E delay distribution can be derived by summing one-hop packet delay variables.
Taking the advantages of the Taylor expansion and central limit theory, we analyze the
mean of E2E delay as a function of network parameters such as the node density in each
area and the duty cycle interval. Finally, using a brute-force search method, the node
density is derived in order to satisfy the delay requirement.
The contribution of this work is summarized as follows. Firstly, we formulate the
average E2E packet delay as a function of network parameters, which helps to estimate
the expected packet delay with a given network topology before the network is
deployed in the real situation. Secondly, the energy consumption and the required
number of nodes are collected to check the performance of the proposed scheme and
two other node deployment ones using Matlab. The simulation results indicate that the
proposed method outperforms other ones, especially when the deployment area
becomes larger.
In the remainder of this paper, the system model and assumption are first
introduced in Section 2. Then, the estimation of E2E packet delay and numerical results
are explained in details in Sections 3 and 4, respectively. Finally, conclusion of this
work has been drawn in Section 5.
2. System Model and Assumption
In this work, we assume that nodes are deployed in a circular area with the sink
node at the center. Each node knows its position and should have at least one forwarder
73
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
which is closer to the sink. Note that the minimum node density which guarantees
network connectivity should be considered [9]. The area is divided into k circular layers
[5, 10, 11] and nodes in layer i are supposed to forward data packets to only nodes in the
very next layer (i-1). Even though the smallest number of hops may be less than k, we
consider k hops in the worst case. The proposed algorithm, called E2E delay Bounded
Node Deployment (EBND), determines the number of nodes in each circular layer
N 1 i k in order to maximize network lifetime, then N nodes are deployed
i
i
randomly with a uniform distribution throughout layer . Note that each layer may have
i
different node distributions in order to maximize network lifetime. Let R and c denote
the transmission range and the width, respectively, of layer j 1 j k , and l is
defined as the radius of the entire area. The innermost layer is the circular area around
the sink with radius R . In order to forward packets to nodes in the next layer, c should
be less than R (i.e., 0 c R ). In other words, node A belongs to layer 1 if the
distance between node A and the sink node, dA , satisfies 0 dA R , meaning it can
transmit packets directly to the sink. Node A belongs to layer j 1 j k , if
dA satisfies:
R c( j 1) dA R c( j 1)
(1)
(2)
where 0 dA l . The total number of layers k is calculated as follows:
l R
k
1
c
Let Rj denote the radius of layer j , and Rj can be calculated as follows:
R
if j 1
(3)
R
j
R c j 1 if 2 j k
Define A as the area of layer j bounded by the radius of layers j and j 1 . The
j
size of Aj can be determined as follows:
R2
if j 1
Aj
(4)
R2 R2
if 2 j k
j1
j
Let random variable S j denote the forwarding area of nodes in layer j . As shown in
Fig. 1, Sj of a sender in layer j is defined as the intersection area between 2 circles: the
74
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
transmission range of the sender and the circular area with radius Rj1 . Since our
previous publication included formulation of S j , please refer to [12] for the detail
equation of the forwarding area.
Sensors use a duty-cycling strategy, i.e., nodes turn on the radio during an active
period and turn it off for the rest of duty cycle interval T . In this paper, a routing
algorithm, called layer-based forwarding (LF) algorithm, which is extended from [12] is
used. Unlike [12], LF uses neighboring nodes scheduling information (i.e., when
neighboring nodes turn on and off radio). All sensor nodes randomly select the wake-up
time during the duty cycle interval by using the same pseudo-random algorithm.
Specifically, nodes exchange their seed values and IDs at the beginning of network
formation. Using exchanged seed values, each node learns the schedules of its
neighboring nodes.
Fig. 1. Network model
75
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
Let potential forwarders of a node represent all neighboring nodes belonging to
the forwarding area. When it has a data packet, the sender waits until a node from
among all potential forwarders wakes up and forwards the packet to the node that wakes
up earliest. Since a node is able to predict the schedules of its neighbors, the sender
should be in sleep mode until the next hop becomes active. This strategy can help nodes
reduce energy consumption by turning off the radio when unnecessary.
In this paper, the energy model is one referred by [13]. On the transmitter side,
there are transmission electronics and a transmission amplifier, while the receiver side
consists of reception electronics. Transmission power etx and reception power erx can
be calculated as follows:
e d
L
tx
1
2
(5)
erx 3L
where is the power coefficient, 1L is transmission electronics energy consumption,
2dL is energy consumed by a transmission amplifier, and 3L is reception
electronics energy consumption. L and d denote the data rate of each node (bps) and
the transmission range, respectively.
3. Estimation of End-to-end Packet Delay
In general, the delay of packets from nodes in the outermost layer is higher than
the delay from inner layers. If nodes in layer k meet the delay constraint, nodes in the
inner layers may also satisfy the delay requirement. Thus, in this paper, we use the
average packet delay from nodes in the outermost layer as the delay requirement. Let
and denote the average end-to-end (E2E) delay of packets in layer k , and the given
average delay requirement for the outermost layer (ADROL), respectively.
Average latency
should be shorter than or equal to given ADROL . Note that
the mean of the sum of k random variables is equal to the sum of k random variables’
means. Since is the average E2E delay of a packet in layer k , it can be expressed as
follows: 2 k1 k where j is the one-hop packet delay of a node in layer
j . Note that 1 0 , i.e., nodes in the first layer can transmit data packet to the sink
immediately, because the sink is assumed to be active all the time. One-hop delay
includes processing time and waiting time. In this manuscript, waiting time is from the
76
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
time a node has a packet (its own packet or a packet received from a neighboring node)
to the time a forwarder wakes up. However, processing time can be ignored, since it is
much lower than the waiting time until the next hop wakes up. Thus, a one-hop delay
can be estimated as the waiting time until the next hop becomes active. Let T denote
the duty cycle interval of nodes in the network. Now, we will estimate the average one-
hop delay as a function of network parameters, such as the number of nodes in each
layer, the duty cycle interval, and the area radius. After that, the average delay of nodes
in layer k can be approximated using one-hop delays.
We consider a node in layer j that has mj potential forwarder(s). Let random
i'th
variable D denote the wake-up time of the
node among the mj potential
i
forwarder(s) 1 i mj . Since sensor nodes randomly and independently choose a
wake-up time, D are independent and identical random variables. The distribution
i
di '
function of D is F
d
P D d
if 0 di T . Let random variable Yj
i
D
i
i
i
i
T
denote the one-hop delay of a packet at layer j , then Yj will be defined as follows:
Y min D ,D ,,D . Let P Y y |m define the probability that a one-hop
j
j
1
2
mj
j
j
latency is shorter than yj given mj , i.e., it is the probability that at least one Di' yj
exists if the node has mj potential forwarder(s). Then, the cumulative distribution
function F(yj | mj ) of yj given mj can be expressed as follows:
F y |m 1 probability that all D y
j
j
i
j
mj
(6)
1
1 F
D y
i j
i1
m
j
yj
T
1 1
Now, distribution function F y can be obtained using Bayes' theorem, that is:
j
N 1
F y P m F y |m
j
j j
j
j
mj 0
(7)
77
m
j
N 1
yj
P m 1 1
j j
T
mj 0
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
where P m is the probability that a node in layer j has mj potential forwarders in
j j
the forwarding area. After that, probability density function f y can be obtained by
j
computing a derivative of distribution function F y :
j
dF y
j
f y
j
dy j
(8)
(9)
j
N 1
m j
T
y j
T
m
1 1
P m
j j
m j 0
Then, the average one-hop
T y j f
y
dy
0
j
j
j
N 1
T
T
P m
j j
E
m 1
m 1
m 0
j
where mj is the number of potential forwarders of a node in layer j .
1
After applying a Taylor expansion for function
around E X , we can obtain
X
the expectation of the inverse function by only considering three first elements of the
Taylor expansion as follows:
E
E
X E X
X E X 2
T
1
1
1
2
3
m 1
E X
E X
E X
(10)
1
1
Var X
3
E X
E X
2
E X
The ratio between the first and second terms is
. Note that in our work since
Var X
2
X is a non-negative variable with the minimum value 1, E X is much greater than
1
Var X . As a result, the second term
is much smaller than the first
Var X
3
E X
1
term
. For example, using our simulation setup, the first term is approximately
E X
13.38 times higher than the second one. Therefore, by ignoring the second term,
T
T
T
Equation. (9) can be written as follows: E
j
m 1
E[mj 1]
E mj 1
j
78
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
1
The approximate error is
6.9% , which is acceptable due to the
14.38
assumption that we are considering the worst case of k forwarding hops. Define
N j
as the node density in circular layer j where Aj is the area of layer j and N j
j
Aj
is the total number of node in area Aj . The average number of potential forwarders of a
N j1
where
E Sj1
node in layer j can be expressed
E mj j1E Sj1
Aj1
forwarding area S j is defined in Section 2. Let random variable x denote the distance
between the sender (group j ) and the boundary of group j 1; so that x has a uniform
distribution in the range 0,c where c is the width of a layer. Note that S is a function
j
of x , then the average of forwarding area is calculated as below:
cS x dx
(11)
1
E Sj
j
c 0
Thus, average one-hop delay j can be rewritten in relation to the number of nodes,
N j , in layer j as follows:
T
T
j
(12)
(13)
N j1
Aj1
E[mj 1]
E Sj1 1
E Sj
Define
, and the delay constraint can be rewritten as follows:
j
Aj
T
T
T
Nk1
Nk2
N1
E S 1
E S
1
E S 1
k1
k2
1
A
A
A
k1
k2
1
The optimization problem determines the number of nodes in each layer (i.e.,
N1,N2 ,,Nk1 ) to meet the delay constraint in Eq. (13) given the total number of nodes
k
T
T
T
N N j . If
, then the
f N
j
Nk1
Ak1
Nk2
N1
j1
E S 1
E S
1
E S
1
k1
k2
1
A
A
1
k2
optimization problem can be written as below:
minimize f N
j
subject to f N
j
79
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
k
N j N
j1
In order to determine the number of nodes in each layer, we consider a brute-force
algorithm which tries all possible cases of N j . Then, the proposed algorithm outputs
the case with the smallest average E2E packet delay.
4. Numerical Results
In this section, we compare EBND with other schemes that also aim at
maximizing network lifetime or balancing energy consumption. For example, Olariu's
scheme [5] adjusts the transmission range, and Wu's scheme [4] proposed a
deterministic non-uniform node deployment strategy. According to numerical results,
both schemes require a large number of nodes, which is costly.
The communication energy parameters 1,2 ,3 are referred to as follows [13]:
J
J
J
9
1 50109
,2 101012
, 3 5010
. Let N and a denote the total
bit
m2
bit
bit
number of nodes in the network, and the number of packets generated by each node
during the simulation period, respectively; tp and tsim are defined as packet
transmission time, and simulation time, respectively; is defined as duty cycling rate;
and ptx , prx and psleep are power consumption for transmission of one data packet,
reception of one data packet, and sleep mode, respectively. Let ntx and nrx denote the
total number of packet transmissions and receptions, respectively, when each node
generates only one packet. Then, ntx and nrx can be calculated based on the number of
k
k
nodes, N , in layer as follows: n iN and n
i 1 N
i
i
tx
i
rx
i
i1
i1
The total energy consumption in the network can be estimated as follows:
E at n p n p 1 t Np t N at n n
P
idle
p rx p
tx tx
rx
sim
sleep
sim
tx
rx
where at n p n p
p rx
is transmission and reception energy, 1 t Np
is
sleep
tx tx
rx
sim
energy consumption in sleep mode, and t N at n n
p
P
idle
is energy
sim
tx
rx
consumption in idle mode.
80
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
In this section, Matlab was used to validate the proposed algorithm and compare it
with other strategies. First, we present a network performance comparison of EBND and
Olariu's scheme. Then, a comparison with Wu's scheme is made.
4.1. Comparison of EBND and Olariu's Scheme
In Olariu's scheme [5], the transmission range of a node in layer is the same as
i
the width of layer . In order to achieve balanced energy consumption, the authors
i
derive the transmission range of nodes in each layer according to given network
parameters. However, the obtained transmission radius of nodes in inner layers is much
smaller than the maximum transmission radius, which reduces network connectivity. To
avoid the connectivity issue, Olariu's scheme requires a large number of nodes.
The number of nodes needed for network connectivity and total energy
consumption are selected as performance metrics. The area radius is set to 225 m, and
the maximum transmission range is 55 m. The number of layers is varied from 3 to 9.
Then, Olariu's scheme obtains the transmission ranges of nodes from the innermost
layer to the outermost, which are {8.19, 15.95, 20.95, 25.15, 29.22, 34.69, 40.50, 49.98}
meters.
Note that while selecting c value ( 0 c R ), there is a tradeoff between the hop
count and the number of forwarding nodes. More specifically, a small c value leads to
an increase in the hop count, which results in higher communication overhead. In
contrast, a high c value can reduce the hop count; however, the forwarding area S j
becomes smaller, which means fewer forwarding nodes can be found. Therefore, we
initially set c 0.5R to balance between the hop count and the number of forwarding
nodes. The effects of c selection on network performance (e.g., packet latency, energy
consumption) should be considered intensively in the future work.
The difference between EBND and Olariu's is that instead of using a uniformly
random node deployment in the whole area, EBND determines number of nodes Ni in
each layer, then deploys Ni nodes in layer randomly with a uniform distribution.
i
Moreover, in EBND, the maximum transmission range is used for all nodes, whereas
the transmission range of nodes increases from the innermost layer to the outermost in
Olariu's scheme.
81
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
Fig. 2. Comparison with Olariu's and Wu’s schemes:
(a) The total number of nodes; (b) Total energy consumption.
As shown in Fig. 2a, to satisfy the desired network connectivity, the Olariu's
scheme requires a much larger number of nodes than EBND. This is attributed to the
fact that the obtained transmission range set in Olariu's scheme is much lower than the
maximum transmission range. For example, nodes in the innermost layer can only
transmit a signal up to 8.19 m, while the maximum radio range is 55 m, i.e., the
2
8.19
55
connectivity range is reduced
44.89 times compared to nodes that use the
maximum transmission range. Total energy consumption of Olariu's scheme, as shown
in Fig. 1(b), is also much higher than that of EBND. Thus, Olariu's scheme is not
practical in a large network.
4.2. Comparison of EBND and Wu's Scheme
Wu et al. [4] proposed a non-uniform node distribution strategy in order to
achieve sub-balanced energy consumption between nodes. The area is divided into a
82
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
number of concentric layers and nodes have the same transmission range. They proved
that sub-balanced energy consumption can be achieved if the number of nodes from the
outermost layer increases with the geometric rule.
As shown in Fig. 2, with a small number of layers, the required number of nodes
in Fig. 2a and total energy consumption in Fig. 2b for EBND are slightly higher than in
Wu's scheme. This result is attributed to the fact that Wu's scheme uses a deterministic
deployment strategy and the number of nodes in layers increases from the outermost
layer to the innermost with a common ratio. Thus, when the number of layers increases,
the total number of nodes and total energy consumption increase exponentially.
5. Conclusions
This paper introduced a node deployment algorithm for delay-constrained
applications in duty-cycled WSNs. We determined number of nodes in each layer using a
brute-force search method given the total number of nodes. We conducted a simulation
using Matlab and experimental results show that EBND required fewer sensor nodes and
less energy consumption than other two node deployment strategies considered.
Acknowledgment
This research is funded by the Technology Science Program of the Ministry of
Defense in Vietnam, code: KC.BM (name of the project: “Design and Manufacturing a
Dynamite and Explosive Objects Detection Machine”) and the Le Quy Don Technical
University.
References
1. Luigi, L. Antonio and M. Giacomo (2010). The Internet of Things: A survey. Computer
Networks, 54(15), pp. 2787-2805.
2. M. El-hajj, A. Fadlallah, M. Chamoun and A. Serhrouchni (2019). A Survey of Internet of
Things (IoT) Authentication Schemes. Sensors, 19(5).
3. A. Fayez, H. Mohammad and A. Abdelrahman (2015). A Survey on MAC Protocols for
Duty-cycled Wireless Sensor Networks. Procedia Computer Science, 73, pp. 482-489.
4. G. C. I. S. a. S. D. X. Wu (2011). Avoiding energy holes in wireless sensor networks with
nonuniform node distribution. IEEE Transactions on Parallel and Distributed Systems, 19,
pp. 1297-1311.
5. O. Stephan and S. Ivan (2006). Design guidelines for maximizing lifetime and avoiding
energy holes in sensor networks with uniform distribution and uniform reporting. in IEEE
INFOCOM.
6. A. Fariba and N. Jafari (2017). Deployment Strategies in the Wireless Sensor Networks:
Systematic Literature Review, Classification, and Current Trends. Wireless Personal
Communications, 95(2), pp. 819-846.
83
Journal of Science and Technique - N.205 (3-2020) - Le Quy Don Technical University
7. P. Vipin, Y. Anju, K. Vinay and Y. P. Yadav (2018). Magnetic Field Line-Based Node
Deployment Strategy for Wireless Sensor Networks. in Optical and Wireless Technologies,
Spinger, pp. 667-673.
8. K. S. Umadevi, V. Shah and U. Desai (2018). Node Deployment Using Virtual Force with
Particle Swarm Optimization in WSN. Advanced Science Letters.
9. X. Liu (2006). Coverage with Connectivity in Wireless Sensor Networks. in 3rd
International Conference on Broadband Communications, Networks and Systems.
10. A. Liu, X. Jin, G. Cui and Z. Chen (2013). Deployment Guidelines for Achieving Maximum
Lifetime and Avoiding Energy Holes in Sensor Network. Information Sciences, 230,
pp. 197-226.
11. F. Barsi, A. A. Bertossi, F. B. Sorbelli, R. Ciotti, S. Olariu and M. C. Pinotti (2009).
Asynchronous Corona Training Protocols in Wireless Sensor and Actor Networks. IEEE
Transactions on Parallel and Distributed Systems, 20, pp. 1216-1230.
12. T. Dao, S. Yoon and J. Kim (2016). A deadline-aware scheduling and forwarding scheme in
wireless sensor networks. Sensors, p. 59.
13. W. Heinzelman, A. Chandrakasan and H. Balakrishnan (2002). An application-specific
protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless
Communications, 1(4), pp. 660-670.
TÍNH TOÁN MẬTĐỘ NÚTMẠNG ĐỂĐÁP ỨNG ĐỘ TRỄTRUNG BÌNH
TRONG MẠNG CẢM BIẾN KHÔNG DÂY LÀM VIỆC THEO CHU KÌ
Tóm tắt: Các ứng dụng trong Internet kết nối vạn vật (IoT) yêu cầu dữ liệu thu thập
phải được truyền tới người quản trị trong một khoảng thời gian trễ giới hạn. Để tiết kiệm
nặng lượng hay kéo dài thời gian làm việc của mạng, kỹ thuật duty cycle được sử dụng, ở đó
các cảm biến bật và tắt mạch thu phát theo chu kì. Trong mạng làm việc theo chu kì, độ trễ
gói tin bị ảnh hưởng lớn bởi việc phân bổ nút mạng, do đó chúng tôi xác định mật độ nút
mạng trong một mạng cảm biến không dây nhằm bảo đảm độ trễ đầu cuối trung bình với các
tham số cho trước sử dụng lý thuyết xác suất thống kê. Kết quả mô phỏng cho thấy phương
pháp phân bổ nút mạng đề xuất tiêu hao ít năng lượng hơn trong khi yêu cầu số lượng nút
cảm biến ít hơn các phương pháp hiện có.
Từ khóa: Tiêu hao năng lượng; kỹ thuật định tuyến; yêu cầu về độ trễ; mạng cảm biến
không dây.
Received: 20/12/2019; Revised: 03/4/2020; Accepted for publication: 06/4/2020
84
13 trang
18980
Free
Bạn đang xem tài liệu "Determining node density to guarantee average latency in duty-cycled wireless sensor networks", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- determining_node_density_to_guarantee_average_latency_in_dut.pdf
