International Journal of Scientific & Engineering Research, Volume 4, Issue 8, August-2013 132

ISSN 2229-5518

A Novel Protocol for Energy Efficient Clustering for Heterogeneous Wireless Sensor Networks

S.Thiripura Sundari, P.Maheswara Venkatesh, Dr.A.Sivanantharaja

Abstract— The W ireless sensor network (W SN) consisting of a large number of sensors are effective for gathering data in a variety of environments. Sensors are usually randomly deployed where battery replacement or recharge is difficult or even impossible to be performed. In this paper, we first completely analyze the basic distributed clustering routing protocol LEACH (Low Energy Adaptive Clustering Hierarchy). All classical schemes consider that all nodes are deployed with same amount of energy. Here we consider a heterogeneous medium, i.e. each node is provided with varying power levels called Heterogeneous - Hybrid Energy Efficient Distributed Protocol (H-HEED). Heterogeneity can be implemented by various parameters here we consider node energy as the basic parameter. Transmitting data from each node of the sensor field may lead to high power consumption and unreliable network lifetime. In order to avoid this we go for clustering and election of cluster heads. Cluster head alone transmits the aggregate data of the cluster. The formation of the clusters and cluster head selection are done by comparing the residual energy of the individual in every round this improves the lifetime to a considerable level. Also we introduce a node scheduling scheme in HEED. The nodes are classified into ACTIVE and SLEEP nodes. A widely employed energy-saving technique is to place nodes in sleep mode, corresponding to low-power consumption as well as to reduce the operational capabilities. Finally the simulation result demonstrates that proposed work achieves longer lifetime and more effective data packets in comparison with the HEED and LEACH protocol.

Index Terms— Heterogeneity, H-HEED, LEACH, Network Lifetime, Wireless Sensor Network (W SN)

—————————— ——————————

I INTRODUCTION

Wireless Sensor Networks are networks of tiny, battery powered sensor nodes with limited on-board processing, stor- age and radio capabilities [1]. A node in sensor network con- sists of CPU for data processing, memory for data storage, battery for energy and transceiver for receiving and sending signals or data one node to another node. Sensor nodes are typically operated by batteries, which are limited in energy capacity, and difficult or even impossible to be replaced or recharged. The sensor nodes are deployed in a sensor field. The deployment of the sensor nodes can be random, regular or mobile sensor nodes can be used. The base station is a master node. Data sensed by the network is routed back to a base sta- tion [1,2]. The base station is a larger computer where data from the sensor network will be compiled and processed. The base station may communicate with the remote Controller node via Internet or Satellite Sensor nodes coordinate among themselves to produce high-quality information about the physical environment. Power control is needed to efficiently make use of the limited energy resources in order to minimize the energy consumed by the sensor nodes and thus prolong network lifetime [3, 4]. For this purpose, energy efficiency must be considered in every aspect of network design and operation, not only for individual sensor nodes, but also for the communication of the entire network. Energy efficiency and power control are the basic guarantee of the network per- formance. HEED (Hybrid Energy-Efficient Distributed cluster- ing) [5] that periodically select cluster heads according to a hybrid of the node residual energy and a secondary parame- ter, such as node proximity to its neighbours or node degree. In all classical methods all nodes are assumed to be homoge- nous i.e. all sensor nodes are equipped with same initial ener- gy. But, in this paper we study the impact of heterogeneity in
terms of node energy. We assume that a percentage of the node population is equipped with more energy than the rest of the nodes in the same network - this is the case of heteroge- neous sensor networks. As the lifetime of sensor networks is limited there is a need to re-energize the sensor network by adding more nodes. These nodes will be equipped with more energy than the nodes that are already in use, which creates heterogeneity in terms of node energy. Furthermore, the pro- posed model enables us to investigate the trade-offs existing between these performance metrics and the sensor dynamics in active/sleep mode. From the energy saving viewpoint, a widely employed technique is to place nodes in a low-power operational mode, the so-called sleep mode. Each sensor is characterized by two operational states: active and sleep. In active state the node is fully working and is able to trans- mit/receive data, while in sleep state it cannot take part in the network activity; thus, the network topology changes as nodes enter/exit the sleep state. The remainder of the paper is orga- nized as follows. In Section 2, we briefly review related work. Section 3 describes the Network Initialization in the H-HEED protocol. Section 4 describes formation of cluster and cluster head selection H-HEED protocol. Section 5 shows the hetero- geneous WSN model of H-HEED. Section 6 shows the imple- mentation of Active and Sleep nodes. Section 7 shows the simulation results by comparing with the preceding methods.

II RELATED WORKS

W. R. Heinzelman, A. P. Chandrakasan and H. Balakrishnan [6] proposed Low Energy Adaptive Clustering Hierarchy (LEACH) protocol in 2000. It is one of the most popular hier- archical routing algorithms for sensor networks. The idea is to form clusters of the sensor nodes based on the received signal

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 8, August-2013 133

ISSN 2229-5518

strength and use local cluster heads as routers to the sink. This will save energy since the transmissions will only be done by such cluster heads rather than all sensor nodes. Optimal num- ber of cluster heads is estimated to be 5% of the total number of nodes. All the data processing such as data fusion and ag- gregation are local to the cluster. Cluster heads change ran- domly over time in order to balance the energy dissipation of nodes. This decision is made by the node choosing a random number between 0 and 1. The node becomes a cluster head for the current round if the number is less than the following threshold

p

T(n) = ��1-p*(r mod1⁄p) if n ϵ G (1)
0 otherwise
where p is the desired percentage of cluster heads (e.g. 0.05), r
is = the current round, and G is the set of nodes that have not been cluster heads in the last 1/p rounds.
In 2005, M. Ye, C. Li, G. Chen and J. Wu [7] proposed Energy Efficient Clustering Scheme (EECS) protocol. It is novel clus- tering scheme for periodical data gathering applications for wireless sensor networks. It elects cluster heads with more residual energy through local radio communication. In the cluster head election phase, a constant number of candidate nodes are elected and compete for cluster heads according to the node residual energy. The competition process is localized and without iteration. The method also produces a near uni- form distribution of cluster heads. Further in the cluster for- mation phase, a novel approach is introduced to balance the load among cluster heads. But on the other hand, it increases the requirement of global knowledge about the distances be- tween the cluster-heads and the base station.
In 2006, Q. Li, Z. Qingxin and W. Mingwen [8] proposed Dis- tributed Energy Efficient Clustering Protocol (DEEC) protocol. This protocol is a cluster based scheme for multi level and two level energy heterogeneous wireless sensor networks. In this scheme, the cluster heads are selected using the probability based on the ratio between residual energy of each node and the average energy of the network. The epochs of being clus- ter-heads for nodes are different according to their initial and residual energy. The nodes with high initial and residual en- ergy have more chances of the becoming cluster heads com- pared to nodes with low energy.
O. Younis and S. Fahmy proposed [9] Hybrid Energy Efficient Distributed clustering Protocol (HEED) protocol in 2004. It extends the basic scheme of LEACH by using residual energy as primary parameter and network topology features (e.g. node degree, distances to neighbours) are only used as sec- ondary parameters to break tie between candidate cluster heads, as a metric for cluster selection to achieve power bal- ancing. The clustering process is divided into a number of it- erations, and in each iterations, nodes which are not covered by any cluster head double their probability of becoming a
cluster head. Since these energy-efficient clustering protocols enable every node to independently and probabilistically de- cide on its role in the clustered network, they cannot guaran- tee optimal elected set of cluster heads.

III NETWORK INITIALIZATION

The network includes some of the initial setting of energy pa- rameters and the initialization of the sensor nodes. So it is nec- essary to generate a random distribution of these nodes in the L * L m2 of the region. Random 100- node topology for a 100 *
100 m2. Sink is located at (50, 50). Fig. 1 demonstrates the wireless sensor network initialization.

100

90

80

70

60

50

40

30

20

10

0

0 10 20 30 40 50 60 70 80 90 100

Fig. 1. Random deployment of nodes

IV CLUSTER AND CLUSTER HEAD FORMATION

Sensor node are densely deployed in wireless sensor network that means physical environment would produce very similar data in close by sensor node and transmitting such type of data is more or less redundant. So all these facts encourage using some kind of grouping of sensor nodes such that group of sensor node can be combined or compress data together and transmit only compact data. This can reduce localized traffic in individual group and also reduce global data .this grouping process of sensor nodes in a densely deployed large scale sensor node is known as clustering. The way of combing data and compress data belonging to a single cluster called data aggregation. Issues of clustering in wireless sensor net- work: (a) how many sensor nodes should be taken in a single cluster Selection procedure of cluster head in an individual cluster. (b) Heterogeneity in a network, it means user can put some power full nodes, in term of energy in the network which can behave like cluster head and simple node in a clus- ter work as a cluster member only. Many protocol and algo- rithm have been proposed which deal with each individual issue. Following assumptions are made regarding the network model is:
1. Nodes in the network are quasi-stationary.
2. Nodes locations are unaware i.e. it is not equipped
by the GPS capable antenna.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 8, August-2013 134

ISSN 2229-5518

3. Nodes have similar processing and communication capabilities and equal significance.

4. Nodes are left unattended after deployment
Start
All sensor nodes sent energy level to the BS

V HETEROGENOUS WSN MODEL

In this section we describe our model of a wireless sensor network with nodes heterogeneous in their initial amount of energy. We particularly present the setting, the energy model, and how the optimal number of clusters can be computed. Let us assume the case where a percentage of the population of sensor nodes is equipped with more energy resources than the rest of the nodes. Let m be the fraction of the total number of nodes n, which are equipped with α times more energy than the others. We refer to these powerful nodes as advanced nodes, and the rest (1-m)*n as normal nodes. We assume that all nodes are distributed uniformly over the sensor field.
Geographical group the data
Choose sensor node with highest energy level
Choose CH
As member node
Send information about join- ing cluster to cluster head

2 level H-HEED:

In 2-level H-HEED protocol, two types of sensor nodes, i.e., the advanced nodes and normal nodes are used. Let us as- sume there are ‘N’ numbers of sensor nodes deployed in a field. E0 is the initial energy of the normal nodes, and m is the fraction of the advanced nodes, which own a times more ener- gy than the normal ones. Thus there are m * N advanced
nodes equipped with initial energy of 𝐸𝑜 ∗ (1 + 𝑟) and (1- m)*𝐸0 normal nodes equipped with initial energy of E0 . The
total initial energy of the network is given by:
𝐸𝑡𝑜𝑡𝑎𝑙 = 𝑁 ∗ (1 − 𝑚) ∗ 𝐸0 + 𝑁 ∗ 𝑚 ∗ 𝐸0 (1 + 𝑟)
= 𝑁 ∗ 𝐸0 ∗ (1 + 𝑟𝑚) (3)
End

Fig. 2. Cluster head selection process

The secondary clustering parameter, intra-cluster communica- tion cost, is a function of (i) cluster properties, such as cluster size, and (ii) whether or not variable power levels are permis- sible for intra-cluster communication. If the power level used for intracluster communication is fixed for all nodes, then the cost can be proportional to (i) , if the requirement is to distrib- ute load among cluster heads, or (ii) , if the requirement is to create dense clusters. This means that a node joins the cluster head with minimum degree to distribute cluster head load or joins the one with maximum degree to create dense clusters. Each node performs neighbour discovery, and broadcasts its cost to the detected neighbours. Each node sets its probability
of becoming a cluster head,𝐶𝐶𝑝𝑟𝑜𝑏 , as follows:
𝐶𝐶_𝑝𝑝𝑝𝑝 = max(𝐶_𝑝𝑝𝑝𝑝 ∗ (𝐸_𝑝𝑟𝑟𝑟𝑟𝑟𝑟𝑟/𝐸_max ), 𝑃_min) (2)

3-level H-HEED:

There are three types of sensor nodes, i.e. the super nodes, advanced nodes and the normal nodes. Let m be the fraction of the total number of nodes N, and m0 is the percentage of the total number of nodes N * m which are equipped with β times more energy than the normal nodes, called as the super nodes, the number is N * m *m0 . The rest N * m * (1-m0 ) nodes are having a times more energy than the normal nodes, being called as advanced nodes and the remaining N * (1- m) nodes are the normal nodes. E0 is the initial energy of the normal
nodes. The energy of the each super node is 𝐸𝑜 (1 + 𝛽) and the energy of each advanced node is 𝐸0 (1 + 𝑟)
The total energy of the network is given by:
𝐸𝑡𝑜𝑡𝑎𝑙 = 𝑁 ∗ (1 − 𝑚) ∗ 𝐸0 + 𝑁 ∗ 𝑚 ∗ (1 − 𝑚0) ∗ 𝐸0 (1 + 𝑟) + 𝑁 ∗
𝑚 ∗ 𝑚0 ∗ 𝐸0 (1 + 𝛽) (4)
𝐸𝑡𝑜𝑡𝑎𝑙 = 𝑁 ∗ 𝐸0 (1 + 𝑚 ∗ (𝑟 + 𝑚0 ∗ 𝛽)) (5)
So, the total energy of the network is increased by the factor of
1 + 𝑚 ∗ (𝑟 + 𝑚0 ∗ 𝛽)

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 8, August-2013 135

ISSN 2229-5518

Fig. 3. Deployment of 3 level H- HEED

Fig. 4. Cluster head selection in 3 levels H-HEED

+ = Advanced node

VII SIMULATION RESULTS

The simulation is done in MATLAB. Let us assume the heter- ogeneous sensor network with 100 sensor nodes are randomly distributed in the 100m*100m area. The base station is located at the centre (50, 50). We have set the minimum probability for becoming a cluster head (pmin ) to 0.0001 and initially the clus- ter head probability for all the nodes is 0.05. The parameters used in our simulation are listed in the Table 1.

TABLE 1

SIMULATION PARAMETERS

Parameters

Values

Sink

At (50,50)

Threshold distance, d0

70 m

Cluster radius

25 m

Energy consumed in the electronics circuit to transmit or receive the signal, Eelec

50 nJ/bit

Energy consumed by the amplifier to transmit at a short distance, Efs

10 pJ/bit/m2

Energy consumed by the amplifier to transmit at longer distance, Eamp

0.0013 pJ/bit/m4

Data Aggregation Energy, EDA

5 nJ/bit/signal

Message Size

4000 bits

Initial Energy, E0

0.5 J

In the analysis, we use the same energy model as proposed in [6]. In the process of transmitting an l-bit message over a dis- tance d, the energy expended by the radio is given by:
𝐸𝑇𝑋(𝑙,𝑑) = 𝐸𝑇𝑋−𝑒𝑙𝑒𝑐 (𝑟) + 𝐸𝑇𝑋−𝑎𝑚𝑝 (𝑟, 𝑟)
𝑟𝐸𝑒𝑙𝑒𝑐+ 𝑟𝐸𝑓𝑠 𝑟2

O = Normal node

* = Super node


= Cluster head

VI ACTIVE AND SLEEP NODES

In this node scheduling the total available residual energy is
= 𝑓(𝑥) = �
𝑟𝐸𝑒𝑙𝑒𝑐+ 𝑟𝐸𝑓𝑠 𝑟4
And to receive the message, the radio expends:
𝐸𝑅𝑋 (𝑟) = 𝐸𝑅𝑋−𝑒𝑙𝑒𝑐 (𝑟)
= 𝑟𝐸𝑒𝑙𝑒𝑐 (7)
(6)
equally distributed and the cluster head also elected as per the
residual energy comparison. Only thing is whenever the node
is under sleep mode in each cluster it consumes very small
energy. Here the total rounds are increased by doing both
changing of sleeping and active modes and the available ener-
gy is distributed in a balanced manner. By properly doing the node scheduling in each cluster with proper time interval, the total energy consumed is low and the total lifetime of the wire- less sensor network is increased near to 50%, when compared with the normal LEACH.
There are other factors like noise, physical obstacles or colli- sion may affect the received power are ignored. We have in- troduced the advanced nodes to the HEED protocol, so as to assess the performance of HEED protocol in the presence of heterogeneity. Let us consider the case for 2-level H-HEED,
30% of the nodes are advanced nodes (m=0.3) and equipped
with 150% more energy than normal nodes (a=1.5). For 3-level
H-HEED, 30% of the nodes are advanced nodes and 20% of the nodes are super nodes are equipped with 150% and 300% more energy than the normal nodes (a=1.5 and b=3, m=0.5 and m0=0.4). For multilevel H-HEED, each node in the sensor

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research, Volume 4, Issue 8, August-2013 136

ISSN 2229-5518

network is randomly assigned different energy between a closed set [0.5, 2].

Fig. 5. Simulated output

In Fig. 5, a detailed view of the behaviour of HEED and H- HEED protocol is illustrated; it shows the number of alive nodes per round. The number of nodes die in HEED is more than H-HEED over the same number of rounds. The number of normal nodes dies very fast and as a result the sensing field becomes sparse very fast. On the other hand, advanced nodes and super nodes die in a very slow fashion. But in multi-level H-HEED, all the sensor nodes are having different energy as a result nodes will die randomly. In this we can say that multi- level H-HEED prolongs lifetime and shows better perfor- mance than other level of H-HEED and HEED protocol. Figure
5 represents the total remaining energy of the network in each
round. In this both HEED and H-HEED, the energy depletes very fast at constant rate. We can conclude that both 3-level H- HEED and multi-level H-HEED is more energy efficient.

VIII CONCLUSIONS

In this paper, H-HEED protocol is proposed along with active and sleep node implementation for heterogeneous wireless sensor network. In this, we introduced different level of heter- ogeneity: 2-level and 3-level in terms of the node energy. We have evaluated the performance of the proposed H-HEED with HEED protocol using MATLAB 7.10. It is observed that there is significant improvement in the lifetime in case of H- HEED protocol in comparison with HEED protocol because the number of rounds is maximum with H-HEED.

REFERENCES

[1] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A Survey On Sensor Networks", IEEE Communications Magazine,

40(8):102–114, August 2002

[2] V. Raghunathan, C. Schurgers, M. B.Srivastava, and Park. S, 2002," Energy-Aware Wireless Microsensor Networks", IEEE Signal Processing Magazine, Volume: 19 Issue: 2, Page(s): 40 –50

[3] Yan Li, YanZhong Li, "Energy-Efficient Clustering Routing Algo

rithm based on LEACH", Journal of Computer Applications 2007

[4] F. Dressler, Self-Organization in Sensor and Actor Networks. Wiley

Series in Communications Networking & Distributed Systems, 2007.

[5] Ossama Younis ,Sonia Fahmy, 2004, "Distributed Clustering in Ad-hoc Sensor Networks: A Hybrid, Energy- Efficient Ap proach", In Proceedings of IEEE INFOCOM, Hong Kong, an ex tended version appeared in IEEE Transactions on Mobile Compu ting, 3(4)

[6] W.R. Heinzelman, A.P. Chandrakasan, H. Balakrishnan. 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications 1 (4)

660–670

[7] M. Ye, C. Li, G. Chen, J. Wu, 2005, "EECS: An Energy Efficient Cluster Scheme In Wireless Sensor Networks", In IEEE Interna tional Workshop on Strategies for Energy Efficiency in Ad Hoc and Sensor Networks (IEEE IWSEEASN-2005), Phoenix, Arizo na, April 7–9

[8] Q. Li, Z. Qingxin, W. Mingwen, 2006, "Design Of A Distri Buted Energy Efficient Clustering Algorithm For Heterogene ous Wireless Sensor Networks". Computer Communications, vol. 29, pp. 2230-7

[9] Ossama Younis ,Sonia Fahmy, 2004, Distributed Clustering in Ad-hoc Sensor Networks: A Hybrid, Energy- Efficient Approach. In Proceedings of IEEE INFOCOM, Hong Kong, an extended ver sion appeared in IEEE,Transactions on Mobile Computing, 3(4)

————————————————

S Thiripura Sundari is currently pursuing masters degree program in Communication Systems Engineering in University College of Engineer- ing, Trichirapalli (BIT Campus), Anna University, Chennai, Chennai-25., E-mail: sundaj@gmail.com.

Mr.P.Maheswara Venkatesh is working as Assistant Professor in the de- partment of ECE in University College of Engineering, Trichirapalli (BIT Campus), Anna University, Chennai, Chennai-25.E-mail: magesh_ven@yahoo.com. His area of interest is Energy Efficient networks.

Dr.A.Sivanantharaja is Associate Professor in the Department of Electron- ics and Communication Engineering in Alagappa Chettiar College of En-

gineering and Technology, Karaikudi.

IJSER © 2013 http://www.ijser.org