[IEEE 2011 IEEE International Conference on Control System, Computing and Engineering (ICCSCE) -...
Transcript of [IEEE 2011 IEEE International Conference on Control System, Computing and Engineering (ICCSCE) -...
Energy Efficient Algorithm for Heterogeneous
Wireless Sensor Network N.Tuah,M.Ismail,K. Jumari
Department of electrical, electronic and system engineering,
Universiti Kebangsaan Malaysia,UKM Bangi, Selangor,43600, Malaysia
E-mail:norah,mahamod,[email protected]
Abstract— Wireless sensor networks (WSNs) are composed of a
large number of sensor nodes with sensing capability. The critical
challenges in such network is the limited lifetime of the battery in
the sensor node. Hence, an efficient node clustering algorithm to
the heterogeneous network approach can be adopted to increase
the lifetime of the network. In this paper, we proposed a new
node clustering algorithm which called as ETLE (Efficient Three
Level Energy) for selecting the cluster head in a distributed
approach to three level hierarchical WSNs. The work has been
compared with the EEHC algorithm in terms of a lifetime of the
network. As a result, it shows that our proposed method may
improve 10% the lifetime of the WSNs.
Keywords-Energy efficient ; heteregeneous network; wireless
sensor network
I. INTRODUCTION
Wireless sensor network has been used widely in many
industries application. For example, it can be applied in
environmental applications, health application, home
automation and smart environment [1]. Besides that, it can be
deployed in the inaccessible area terrains, polluted area or
disaster area, where battery replacement is difficult or even
impossible to be performed. Therefore, a relevant scheme has
to develop to prolong the lifetime of the network by
considering energy efficiency.
Node clustering algorithm is a scheme called when several
nodes were aggregated to form a group (cluster). Usually, it is
operated in two phases which are called node clustering setup
and clustering maintenance [6]. In the node-clustering setup
phase, cluster heads (CHs) are chosen among the nodes in the
network based on the selection cluster head scheme. After
selecting the cluster heads, other node affiliated with the CHs
would form the clusters. Nodes that are not cluster head is
called non-cluster head node. CHs as a router will transmit
data collected from non-cluster head node to the sink
node/base station. In the clustering maintenance phases, the
clustering configuration may be changed after initial cluster
was set up due to node movements or topology changes.
In a homogeneous network, the base station was cooperated
with sensor node, which has the same capability, in
computational power and storage. Some researchers have been
proposed a routing protocol based on these characteristics like
LEACH[2] and ACHTH-LEACH[3] . The assumption of this
kind of network is not practicable because the sensor node
itself is not always have the same communication and sensing
capabilities. In fact, sensor nodes used the same platform is
not guaranteed have exactly the same physical properties [4].
Recently, the heterogeneous networks have studied as its
ability to extend the lifetime of the network, improving
reliability data transmission and decreasing latency of data
transportation [5]. Some routing protocols also have been
proposed in a heterogeneous network environment like SEP[7]
and EEHC[8].
Stable Election Protocol (SEP) [7] is among the first an
energy efficiency routing protocol that used a heterogeneous
network, in the sense that election probabilities are weighted
by the initial energy of the node relative to that of other nodes
in the network. It is two-level heterogeneous WSNs, which is
composed of two types of nodes accordingly to the initial
energy. First nodes called as normal nodes and seconds nodes
known as advanced nodes with more energy at the beginning.
SEP may extend the lifetime of the network, but it cannot
apply to multilevel heterogeneous WSNs.
Energy Efficient Heterogeneous Clustered EEHC [8] is
three-level heterogeneous WSNs. In the model, it will assume
m is the fraction of the total number of nodes n, mo is the
percentage of the total number of nodes m, which is equipped,
with β times more energy resources than the normal node,
which called as super nodes. The rest (1-mo)*m*n nodes are
equipped with α time more energy than the normal nodes
known as advance node and remained n*(1-m) as normal
nodes. EEHC may extend the network lifetime and suitable for
multilevel heterogeneous WSNs.
II. THE DEVELOPED EFFICIENT THREE LEVEL ENERGY
(ETLE) ALGORITHM
ETLE algorithm was considered in the heterogeneous
network. The network is organized into a clustering hierarchy,
and the cluster head collect measurements information from
cluster nodes and transmit the aggregated data to the base
station directly. All the nodes in the WSNs are heterogeneous
in their initial amount of energy. All the procedure of ETLE
has been explained in the following part.
A. Radio Energy Model
The energy consumption by the sensor nodes in the WSNs
can be calculated by using the energy model as proposed by
[2]. The energy consumption during sending k bit of data to a
distance d was calculated using (1). The distance threshold
value, d0 will differentiate type of data communication. First
equation is called free space model which the transmission
power was attenuated d2
for d < d0. Second equation is called
2011 IEEE International Conference on Control System, Computing and Engineering
978-1-4577-1642-3/11/$26.00 ©2011 IEEE 92
multi-path fading model which transmission power was
attenuated d4 for d> d0.
0
4
0
2
:
:),(
dddkkE
dddkkEdkE
ampraytwoelec
ampfrisselec
Tx
(1)
Consequently, the energy consumed when receiving k bit of
data was calculated using (2).
ERx(k) = E Rx-elec(k) = kEelec
(2)
Where Eelec means the energy consumed in transmitting or
receiving a bit of data, ampfriss , ampraytwo respectively,
show that the two channel model parameters of energy needed
to power amplification.
B. ETLE Details
In this section, we describe ETLE algorithm. All the sensor
nodes in the network were randomly distributed and not
mobile. Node clustering algorithm is use to form a cluster
based network in the WSNs. ETLE algorithm for WSNs has a
periodic round; each round is divided into four different
phases known as information revise, cluster head selection,
cluster creation and data communication. Some nodes were
added with some percentage of energy, in order to form the
energy heterogeneity in the network. We use m symbol to
present the percentage of nodes and α as times more energy of
nodes. Normally, in cluster-based network, some nodes will be
selected as the cluster head. The cluster head will aggregate
the sensing data of their cluster members and transmit to the
sink node. It uses a single – hop data transmission to the sink
node.
For homogenous network liked LEACH protocol, it was
guarantees that every node has a chance to become a cluster
head once every round. In the heterogeneous concept, this
number of rounds is changed to epoch. Epoch concept is
particularly valuable in order to balance the average total
number of cluster heads per round per heterogeneous epoch.
1) Cluster head selection
The network was formed by three-level energy. First is
called as a most energy node, with m1 percent of n nodes,
which have α more times energy. It was followed by a more
energy node, with mo percent of n nodes, with α/2 more times
energy and finally common energy node, with (1-(mo + m1))
percent of n nodes, which have initial energy Eo.
Consequently, total energy can be obtained as presented in (3).
Total Energy = Common energy nodes + More energy nodes + Most energy
nodes
= (3)
From (3), it shows that, the total energy of the network was
increased by a factor of 1+ . In the network, there
are n* nodes, with energy equal to the
initial energy of a common energy node. In the network, it is
necessary to maintain the minimum energy consumption for
each round within an epoch. As a result, the average number
of cluster head is must constant and equal to n x Popt for each
round within an epoch. Consequently, for example, in the
common energy node there are n*
*Pcommon cluster heads per round per epoch. The weighted
probability for common energy node, more energy node and
most energy node was shown in (4), (5) and (6).
(4)
(5)
(6)
Where Popt is the probability of the node to become a cluster
head in the network. In addition, a deterministic cluster head
selection[14] have been used to calculate the threshold, T(n) in
each round as presented in (7).
(7)
Where En_current is the current energy, En_max is the initial
energy of the node and r is the current round number (starting
from round 0). Afterwards, for each round, P value will be
replaced by equation 4 for common node cluster head
selection as shown in (8). The same procedure also uses for
both types of nodes.
2011 IEEE International Conference on Control System, Computing and Engineering
93
(8)
If cluster head was selected in the present round, it will not be
a cluster head in the same epoch. But for nodes that have not
yet selected as cluster head (set G), its probability to become a
cluster head was increased for each round in the same epoch.
Each node s ∈ G will independently chose random number
between 0 and 1. The node will be selected as the cluster head
for the current round if the random number selected is less
than T(n) value.
2) Cluster formation
After cluster head was selected, each non cluster head node
determines to which cluster it belongs by choosing the cluster-
head that requires the minimum communication energy, based
on the received signal strength of the advertisement from each
cluster head. Note that typically this will be the cluster-head
closest to the sensor node. Consequently, non cluster head
node will measure the approximate d between all cluster head
selected and itself. The d value was calculated by using
Euclidean distance. After make a decision, the non cluster
head node will transmit joint-request message to the chosen
cluster head. It is a message which contains node‘s ID and the
cluster head‘s ID. There is no restriction on the number of
nodes in the cluster members for each cluster in the network.
3) Information revise
Each round the remaining energy of the nodes has to revise.
Each sensor nodes broadcasts an update packet with
information about its remaining energy to all its neighbor.
4) Data communication
After cluster formation was completed, all the alive nodes in
for each cluster will periodically collect data and send it to the
cluster heads node. Consequently, the cluster head will collect
all the data and send it to the sink node by using a single – hop
data transmission.
III. MODEL EVALUATION
A. Evaluation setup
100 sensor nodes were simulated in the wireless sensor
network in a field dimension 100m x 100m. The packet length
is 4000 bits. All the nodes deployed randomly in a square area.
The sink node was located in the centre of sensing are [50,50].
The optimal probability, Popt is 10%. The initial energy of the
network is 0.5 Joules, Eelec = 50 nJ/bit, EDA = 5nJ/bit/report,
ampfriss = 10pJ/bit/m2 and ampraytwo = 0.0013 pJ/bit/m
4.
B. Simulation Results
The validation of the performance of our proposed protocol
was simulated in MATLAB. Fig. 1 shows the snapshot for the
first round of the simulation for mo=m1=0.1 and α = 1. We
denote ‗0‘ a common energy node, with ‗+‘ a more energy
node, with ‗*‘ a most energy node, ‗.‘ As a dead node and ‗X‘
as the sink node. Beside that the selected cluster head from
three types of node also have been shown which transmitting
the data to the sink node. Fig. 2 shows a snapshot of the
cluster formation in the network. Each cluster will have one
selected node called as CH node. It will aggregate all the data
from its member‘s node in the cluster and transmit the data to
the sink node using a single hop data transmission. It shows
that, the transmission data for sensor node close to sink node
was not optimized. For the future research, we will consider
this weakness by make some modification to the existing
algorithm proposed.
Figure 1: A snapshot first round of network when all the nodes are alive
Figure 2: A snapshot of cluster formation in the network
Consequently, Fig.3 shows the snapshot of the network when some
node was died (power energy is zero) at 1500 rounds.
0 10 20 30 40 50 60 70 80 90 1000
10
20
30
40
50
60
70
80
90
100
Most energy node
more energy node
Common energy node
Sink Node
0 10 20 30 40 50 60 70 80 90 1000
10
20
30
40
50
60
70
80
90
100
2011 IEEE International Conference on Control System, Computing and Engineering
94
Figure 3 : A Snapshot at 1500 rounds when some nodes are dead
We used the number of dead nodes parameter to evaluate the
network lifetime. Fig. 4 shows the network lifetime
comparison between ETLE and EEHC algorithm. It shows
that ETLE is better than EEHC (by 10%) for network size 100
x 100 m2. The ETLE is better in their performance because its
sensor node with more energy is many than implemented in
EEHC. Besides that, ETLE have been considering the
remaining energy for each node which may extend the lifetime
of the network. It also happened when we simulate the
network in the area 200 x 200 m2. As shown in Fig.5, the
performance of ETLE is better as compare to EEHC. From the
graph, it show the first node die is more earlier in the EEHC as
compare to ETLE and it will make the lifetime of the network
is short. As a suggestion, it is better to used ETLE algorithm
in order to use a bigger area network to prolong the lifetime of
the network.
Figure 4: The number of dead nodes for each round over an area 100 x 100 m2
Figure 5: The number of dead nodes for each round over an area 200 x 200 m2
A comparison for the first node die is shown in Table 1. Both
algorithms have been compared in three different initial energy
values. As a result, ETLE shows a better performance as compare to
EEHC. For example during Eo value is 1J, first node was die during
2484 round for ETLE and 2307 round for EEHC. That is mean in
EEHC the network lifetime is die earlier than in ETLE algorithm.
Table 1: Comparison of first node die
Algorithm Initial Energy, Eo
(J/node)
1st node die
(Round experienced)
ETLE 0.25 609
EEHC 528
ETLE 0.5 1256
EEHC 1051
ETLE 1 2484
EEHC 2307
IV. CONCLUSION
We proposed ETLE (Efficient Three Level Energy) algorithm
in three-level hierarchical network. Each sensor node selects
itself as a cluster head independently and by considering
remaining energy for each node in each round. To make a
validation, we compare our proposed protocol with EEHC and
as a result ETLE may extend 10% the lifetime of the network
more than EEHC.
ACKNOWLEDGMENT
We would like to thank the reviewers for their comments.
This research was supported by research grant UKM-OUP-
ICT-36-185/2011 .
0 10 20 30 40 50 60 70 80 90 1000
10
20
30
40
50
60
70
80
90
100
0 2000 4000 6000 8000 10000 120000
10
20
30
40
50
60
70
80
90
100
Time steps (Rounds)
Num
ber
of
Dead n
odes
ETLE
EEHC
0 2000 4000 6000 8000 10000 120000
10
20
30
40
50
60
70
80
90
100
Time steps (Rounds)
Num
ber
of
Dead n
odes
EEHC
ETLE
2011 IEEE International Conference on Control System, Computing and Engineering
95
REFERENCES
[1] A. Hac, ―Wireless Sensor Network Design‖, John Wiley and Sons,
Ltd, 2003.
[2] W.B.Henizelman, A.P.Chandrakasan and H.Balakrishnan, ―an
application-specific protocol architecture for wireless micro sensor
networks‖ IEEE transactions on wireless communication, vol 1,
No.4, pp. 660 – 670, October 2002.
[3] L.Q.Guo,Y.Xie,C.H.Yang and Z.W.Jing, ―Improvement on
LEACH by combining adaptive cluster head selection and two-hop
transmission‖, IEEE proceedings of the 9th International
conference on machine learning and cybernetics, 2010.
[4] S.K.Das and H.M.Ammari.: ―Routing and data dissemination‖, in
J. Zheng and A. Jamalipour (Ed.): ―Wireless Sensor Network: A
networking Perspective‖ (IEEE Press, 2009, 1st edn.), pp. 67 – 139.
[5] M.Yarvis, N.Kushalnagar, H.Singh, ―Exploiting heterogeneity in
sensor networks, IEEE INFOCOM, 2005.
[6] C.Zhang, E. Hou and N. Ansari: ‗Node clustering‘, in J. Zheng and
A. Jamalipour (Ed.): ‗Wireless Sensor Networks: A Networking Perspective‘ (IEEE press, 2009,1st edn.), pp173-209.
[7] G. Smaragdakis, I.Matta and A.Bestavros, ―SEP: A Stable Election
Protocol for Clustered Hetergenous Wireless Sensor Networks, ―
Proceeding of 2nd International Workshop on Sensor and Actor
Network Protocol and Applications (SANPA), Boston, U.S.A.,
2004, pp.1-11.
[8] D.kumar, T.C.Aseri and R.B.Patel, ―EEHC: Energy efficient
hetergenous clustered scheme for wireless sensor networks‖,
Computer Communications 32(2009),pp.662-667.
[9] M.J.Handy,M.Haase and D.Timmermann, ―Low energy adaptive
clustering hierarchy with deterministic cluster-head selection‖,
IEEE, 2000.
2011 IEEE International Conference on Control System, Computing and Engineering
96