[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.


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


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


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.


96

[ieee 2011 ieee international conference on control system, computing and engineering (iccsce) -...

Documents