TR 2005 011
TR 2005 011
TR 2005 011
Contents
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 Introduction
2 Related Work
3.1
3.2
Election Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.3
10
4 Quantitative Analysis
11
4.1
11
4.2
Election Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.3
13
4.4
14
4.5
16
4.6
17
18
5.1
19
5.2
Energy Consumption . . . . . . . . . . . . . . . . . . . . . . . .
21
5.3
24
27
References
28
29
List of Figures
1
19
Cluster size with respect to distance from the base station and the
head-set size. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
21
22
Energy consumed per round with respect to head-set size and network diameter. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Time for iteration with respect to cluster diameter and the head-set
size. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
Time for iteration with respect to the number of clusters and the
head-set size. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
23
25
26
Abstract
Wireless sensor networks (WSNs) are used for various applications, such
as habitat monitoring, automation, agriculture, and security. Since numerous
sensors are usually deployed on remote and inaccessible places, the deployment and maintenance should be easy and scalable.
In this paper, we propose an energy efficient hierarchical cluster-based
routing protocol for continuous stream queries in WSN. We introduce a set
of cluster heads, head-set, for cluster-based routing. The head-set members
are responsible for control and management of the network. On rotation basis, a head-set member receives data from the neighboring nodes and transmits the aggregated results to the distant base station. For a given number of
data collecting sensor nodes, the number of control and management nodes
can be systematically adjusted to reduce the energy consumption, which increases the network life.
1 Introduction
With rapid advancement in electronics industry, small inexpensive battery-powered
wireless sensors have already started to make an impact on the communication
with the physical world. The wireless sensor networks (WSNs) can be deployed
in a wide geographical space to monitor physical phenomenon with acceptable
accuracy and reliability. The sensors can monitor various entities such as: temperature, pressure, humidity, salinity, metallic objects, and mobility; this monitoring capability can be effectively used in commercial, military, and environmental applications. Since WSNs consist of numerous battery-powered devices,
the energy efficient network protocols must be designed. Due to large network
size, limited power supply, and inaccessible remote deployment environment,
the WSN-based protocols are different from the traditional wireless protocols
[EGHK99, ECPS02]. The WSN-routing, for instance, uses multi-hop routing that
is not based on the principle of fairness. The redundant, inaccurate or uncertain
sensor data is filtered. Instead of address-based point-to-point communication,
the routing decisions are data centric in WSNs, where the goal is to efficiently
disseminate query and query results into the network.
The core operation of wireless sensor network is to collect and process data at
the network nodes, and transmit the necessary data to the base station for further
analysis and processing. Currently there are several energy efficient communication models and protocols that are designed for specific applications, queries, and
topologies. The routing algorithm proposed in this paper is suitable for continuous monitoring of numerous widespread sensors, which are at a large distance
from the base station.
The structure of the remaining paper is as follows: Section 2 briefly describes
the related work. In Section 3, our hierarchical cluster-based routing protocol is
described. In Section 4, we perform quantitative analysis for our protocol. Section
5 evaluates the performance of the proposed protocol. Finally, Section 6 concludes
the paper and provides directions for some future work.
2 Related Work
Heinzelman et al. [HCB00] describes the LEACH protocol, which is a hierarchical self-organized cluster-based approach for monitoring applications. The data
collection area is randomly divided into several clusters. Based on time division multiple access (TDMA), the sensor nodes transmit data to the cluster heads,
which aggregate and transmit the data to the base station. A new set of cluster
heads are chosen after specific time intervals. A node can be re-elected only when
all the remaining candidates have been elected.
Lindsey et al. propose PEGASIS [LR02], an extension of LEACH, where
nodes transmit to their nearest neighbor and messages are transmitted to the base
station on rotation basis. The PEGASIS protocol is found to be more robust to
node failures as compared to LEACH.
The cluster-based routing protocols are investigated in several research studies. For example, the work in [PCH+ 05] shows that a 2-tier architecture is more
energy efficient when hierarchical clusters are deployed at specific locations. Bandyopadhyay and Coyle [BC03] describe a multi-level hierarchical clustering algorithm, where the parameters for minimum energy consumption are obtained using
stochastic geometry.
Cluster-based approaches are suitable for habitat and environment monitoring,
which requires a continuous stream of sensor data. Directed diffusion and its
variations are used for event-based monitoring. Intanagonwiwat et al. [IGE00]
describes a directed diffusion protocol where query (task) is disseminated into
the network using hop-by-hop communication. When the query is traversed, the
gradients (interests) are established for the result return path. Finally, the result is
routed using the path based on gradients and interests. Braginsky et al. [BE02], a
variation of directed diffusion, use rumor routing to flood events and route queries;
this approach is suitable for a large number of queries and a fewer events.
Ye, Heidemann, and Estrin [YHE04] describe a contention-based medium access protocol, S-MAC, which reduces energy consumption by using virtual clus-
ters. The common sleep schedules are developed for the clusters. Moreover,
in-channel signaling is used to avoid overhearing. Cerpa et al. [CE04] propose
ASCENT that operates between routing and link layers. Any routing or data dissemination protocol can use ASCENT to manage nodes redundancy. In ASCENT,
nodes monitor their connectivity and decide whether to become active and participate in the multihop networking. Moreover, nodes other than active nodes remain
in passive state until they get a request from active nodes.
As an extension of LEACH [HCB00], our proposed protocol introduces a
head-set for the control and management of clusters. Although S-MAC [YHE04]
divides the network into virtual clusters, the proposed protocol divides the network into a few real clusters that are managed by a virtual cluster-head.
phase, the head-sets are chosen for the pre-determined number of clusters. In the
data transfer phase, the members of head-set transmit aggregated data to the base
station. Each data transfer phase consists of several epochs. Each member of a
head-set becomes a cluster head once during an epoch. A round consists of several
iterations. In one round, each sensor node becomes a member of head-set for one
time. The above communication stages are illustrated in Figure 1.
Round 1
Iteration 1
Election Phase
Epoch 1
Data Transfer
Epoch j
Iteration m
Election Phase
Epoch 1
Data Transfer
Epoch j
Round 2
Iteration 1
Election Phase
Epoch 1
Data Transfer
Epoch j
Time
Passive Associate
Associate
End of iteration
Start of an epoch
Start frame
End of iteration
End frame
End of iteration
Active
Noncandidate
Start of an iteration
Candidate
for the next iteration. Finally, at the end of a round, all the nodes have become
non-candidate members. At this stage, a new round is started and all the nodes
become candidate members.
4 Quantitative Analysis
In this section, we describe a radio communication model that is used in the quantitative analysis of our protocol. The energy dissipation, number of frames, time
for message transfer, and the optimum number of clusters are analytically determined.
(1)
Similarly, the energy consumed to transmit an l-bit message for a shorter distance
is given by:
ET = lEe + ls d2
(2)
Moreover, the energy consumed to receive the l-bit message is given by:
ER = lEe + lEBF
(3)
Equation 3 includes the cost of beam forming approach that reduces energy
consumption. The constants used in the radio model are given in Table 1.
11
Description
Symbol Value
10 pJ/bit/m2
0.0013
at a shorter distance
Energy consumed by the amplifier to transmit
pJ/bit/m4
at a longer distance
Ee
50 nJ/bit
EBF
5 nJ/bit
Table 1: Sample parameter values of the radio communication model used in our
quantitative analysis.
n
k
12
n
k
ECHelec = lEe
(6)
The first part of Equation 6 shows the energy consumed to receive messages
from k cluster heads; it is assumed that a sensor node receives messages from
all the cluster heads. The second part of Equation 6 shows the energy consumed
to transmit the decision to the corresponding cluster head. Equation 6 can be
simplified as follows:
EnonCHelec = lEe (1 + k) + klEBF + ls d2
(7)
n
m l(Ee + EBF
k
(8)
The first part of Equation 8 shows the energy consumed to transmit a message to
the distant base station. The second part of Equation 8 shows the energy consumed
to receive messages from the remaining
n
k
n
n
m + 1 lEe +
m lEBF
= ll d +
k
k
4
13
(9)
(10)
For circular clusters with a uniform distribution of sensor nodes and a network
diameter of M, the average value of d2 is given as: E[d2 ] =
can be simplified as follows:
EnonCH/f rame
M2
2k
. Equation 10
M2
= lEe + ls
2k
(11)
f2 =
n
k
n
k
1
m+1
1
k
(12)
n
k
1
k
(13)
m
m+1
The energy consumptions in a data transfer stage of each cluster are as follows:
ECHdata = f1 Nf ECH/f rame
(14)
(15)
n
km
, which is
an election phase and a data transfer stage. The energy consumed in one iteration
of cluster is as follows:
ECH/iter/cluster = ECHelec + ECHdata
(16)
(17)
ECH/node =
ECH/iter/cluster
m
(18)
EnonCH/node =
EnonCH/iter/cluster
n
m
k
(19)
The start energy, Estart , is an energy of a sensor node at the initial start time.
This energy should be sufficient for at least one round. In one round, a node
becomes a member of head-set for one time and a non-cluster head for
times. An estimation of Estart is given below:
Estart = ECH/node +
n
1 EnonCH/node
km
n
km
(20)
Using Equation 18, Equation 19 and Eqaution 20, Estart can be described as
below:
Estart =
1
ECH/iter/cluster + EnonCH/iter/cluster
m
(21)
Using Equation 21, Equation 16, Equation 17, Equation 14, and Equation 15,
Estart can be given as follows:
15
Estart =
ECHelec + EnonCHelec Nf
f1 ECH/f rame + f2 EnonCH/f rame (22)
+
m
m
Nf =
(23)
Ec = ECH/f rame +
n
m EnonCH/f rame
k
(24)
The first part of Equation 24 is due to the energy consumption as an active member
of the head-set. The second part of Equation 24 is due to
n
k
m non-cluster
(25)
Using Equation 25, Equation 24, Equation 11, and Equation 9, the total energy
consumed by k clusters is given below:
Etotal/f rame
n
n
= k ll d +
m + 1 lEe +
m lEBF +
k
k
(
!)
n
M2
k
m lEe + ls
k
2k
(26)
M2
(n km) lEe + (n km) ls
2k
16
(27)
M2
M2
lms
(28)
2k
2
(29)
M2
=0
2k 2
(30)
Using Equation 30, the optimum value of k for minimum dissipation of frame
energy is as follows:
k=
n
2
s
M
l d4 (2m 1)Ee mEBF
(31)
l
(32)
Rb
In one frame, messages are transmitted by all the non-cluster head nodes and
tmsg =
the active member of the head-set. Since at one time only one member of head-set
is active, the inactive head-set members, which are m 1, do not transmit during
the frame transmission. The time for one frame is given as follows:
17
tf rame =
n
m
kX
tmsgi
i=1
+ {tmsgcluster
n
k
head
(33)
nodes. The second part of Equation 33 is due to the transmission of the active
member of the head-set.
If we assume that message transfer time is same for all the nodes, Equation 33
can be simplified as follows:
tf rame
n
=
m + 1 tmsg
k
(34)
As Nf frames are transmitted in one iteration, time for one iteration, titeration
is as follows:
titeration = tf rame Nf
(35)
Using Equation 35, Equation 34, and Equation 32, the iteration time titeration
can be given as below:
n
km
l n
m + 1) Nf
(36)
titeration =
Rb k
iterations in one round, the time for one round, tround , is as
follows:
n
km
l n n
Nf
=
m+1
Rb k k
m
tround = titeration
(37)
# of Clusters
10
10
HeadSet Size
10
9
# of Clusters
8
7
6
5
4
3
2
1
250
5
4
200
3
2
Distance
150
HeadSet Size
Figure 4: Cluster size with respect to distance from the base station and the headset size.
sible. Moreover, when the distance from the base station is increased, more energy is spent for a distant transmission. As a result, for the same head-set size,
the maximum number of clusters decreases when the distance to the base station
increases.
Figure 5 shows graphs that illustrate the energy consumption with respect to
the number of clusters. As expected, the energy consumption is reduced when the
number of clusters are increased. However, the rate of reduction in energy consumption is reduced for higher cluster sizes. Moreover, the energy consumption
is lower when head-set size is 3 as compared to head-set size of 1.
20
Energy (J)
HeadSet Size=3
1
HeadSet Size=1
10
12
14
16
18
20
Number Of Clusters
Nf=10000,d=100,n=1000
HeadSet Size=1
Estart (J)
0.8
0.6
0.4
0.2
0
50
40
200
HeadSet Size=3
30
20
100
10
# Of Clusters k
150
50
0
n
k
head transmission. However, m 1 nodes are in sleep mode and do not transmit.
Further, there are fewer elections in our routing model as compared to LEACH;
22
n
k
to
n
.
km
Nf=10000,k=50,n=1000
0.12
0.1
Estart (J)
0.08
0.06
0.04
0.02
0
20
200
15
150
10
100
HeadSest Size
50
0
Figure 7: Energy consumed per round with respect to head-set size and network
diameter.
Figure 7 shows a graph that illustrates the variation in the energy consumed
per round with respect to head-set size and network diameter. The x-axis, yaxis, and z-axis represent the network diameter, the head-set size, and the energy
consumed in one round, respectively. Equation 20 is used to estimate the energy
consumed/round by each sensor node. The number of data frames in one iteration
is Nf = 10, 000 and the number of clusters k = 50. As expected, the graph shows
that energy consumption is reduced when the head-set size is increased.
The results of reduced energy consumption, as illustrated in Figure 6 and Figure 7, show that using a head-set of sensor nodes is more desirable than a single
cluster head. Moreover, this protocol provides a more systematic approach of
23
reducing the energy consumption. If more nodes are added in LEACH, all the
nodes are treated alike and these extra nodes will also be used in collecting the
sensor data. However, in our approach, the number of sensor nodes for data collection remain unchanged and the number of control and management nodes can
be adjusted.
x 10
HeadSet Size=3
4
3.5
3
2.5
2
1.5
1
0.5
0
100
HeadSet Size=3
80
200
60
150
40
100
20
50
0
Network Diameter
Figure 8: Time for iteration with respect to cluster diameter and the head-set size.
24
The graph of Figure 8 illustrates the variation in time to complete one iteration
with respect to cluster diameter and head-set size. The x-axis, y-axis, and z-axis
represent the cluster diameter, head-set size, and time to complete one iteration,
respectively. The head-set size is given as a percentage of cluster size. The start
energy, Estart is fixed for all the cases. The start energy can be used for the longest
period of time when the head-set size is 50% of the cluster size. When the headset size is less than 50% of the cluster size, there are fewer transmissions in each
iteration but there are more iterations to complete the round. However, when the
head-set size is greater than 50% of the cluster size, there are more transmissions
in each iteration, although there are fewer iterations.
3
n=1000,M=100,r=250*10
4
x 10
7
6
Time (sec)
5
4
3
2
1
0
1
20
50
15
40
10
30
20
HeadSet Size
10
0
# of clusters, k
Figure 9: Time for iteration with respect to the number of clusters and the head-set
size.
Figure 9 shows a graph that illustrates the variation in time for one iteration
25
with respect to the number of clusters and the head-set size. For the same number
of clusters, the time for iteration increases as the head-set size increases. It shows
that one iteration can last longer for larger head-set sizes. However, for larger
number of clusters, the time for iteration is reduced. This graph shows that the
head-set size and the number of clusters should be carefully chosen to extend the
network life time.
n=1000,k=50,r=250*103
x 10
18
16
# of Frames
14
12
10
8
6
4
2
0
20
200
15
150
10
100
5
HeadSet Size
50
0
Figure 10: Number of frames transmission per iteration with respect to the headset size and cluster diameter.
Figure 10 shows a graph that illustrates the number of frames transmitted with
respect to cluster diameter and head-set size. The x-axis, y-axis, and z-axis represent the network diameter, head-set size, and number of frames, respectively. As
expected, for increased value of head-set sizes, more frames can be transmitted.
As a result, the iteration can last for a longer time, which is also consistent with
26
the results shown in Figure 9. In other words, when the head-set size is increased,
there are more control and management sensor nodes. Consequently, the data
collecting nodes can be used for a longer period of time.
27
References
[BC03]
[BE02]
D. Braginsky and D. Estrin. Rumor routing algorthim for sensor networks. In Proceedings of the 1st ACM International Workshop on
Wireless Sensor Networks and Applications, pages 2231, New York,
NY, USA, 2002. ACM Press.
[CE04]
A. Cerpa and D. Estrin. ASCENT: Adaptive self-configuring sensor networks topologies. IEEE Transactions on Mobile Computing
(TMC) Special Issue on Mission-Oriented Sensor Networks, 3(3),
July-September 2004.
W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energyefficient communication protocol for wireless microsensor networks.
In Proceedings of the Hawaii International Conference on System
Sciences, January 2000.
[IGE00]
28
S. Lindsey and C. S. Raghavendra. PEGASIS: Power-efficient gathering in sensor information systems. In Proceedings of the IEEE
Aerospace Conference, March 2002.
[PCH+ 05] J. Pan, L. Cai, Y. T. Hou, Y. Shi, and S. X. Shen. Optimal base-station
locations in two-tiered wireless sensor networks. IEEE Transactions
on Mobile Computing (TMC), 4(5):458473, 2005.
[YHE04]
W. Ye, J. Heidemann, and D. Estrin. Medium access control with coordinated adaptive sleeping for wireless sensor networks. IEEE/ACM
Transactions on Networks, 12(3):493506, 2004.
29
30
Enon_ch_elect=l.*(Ee.*(1+k)+es*d2);
Ech_frame=l.*(((n./k)-m+1)*Ebf+el*d4+((n./k)-m+1)*Ee);
Enon_ch_frame=l.*(Ee+es*((M2)./((2*3.14159).*k)));
Ech_data=(1./((n./k)-m+1)).*(Nf./k).*Ech_frame;
Enon_ch_data=(((n./k)-m)./((n./k)-m+1)).*(Nf./k).*Enon_ch_frame;
Ech_iter=Ech_elect+Ech_data;
Enon_ch_iter=Enon_ch_elect+Enon_ch_data;
Eround=(Ech_iter/m)+(((n./(k*m))-1).*Enon_ch_iter)./((n./k)-m);
plot(k,Eround);
xlabel(Number Of Clusters, FontSize,14)
ylabel(Energy (J), FontSize,14)
31
32
33