TLH-DEEC: Two Level Hierarchical Distributed Energy-Efficient Clustering Technique for Wireless Sensor Network

TLH-DEEC: Two Level Hierarchical Distributed Energy-Efficient Clustering Technique for Wireless Sensor Network

Manpreet Kaur

Department of Computer Science and Engineering Punjab Technical University Gaini Zail Singh Campus Bathinda, Punjab

Abhilasha

Department of Computer Science and Engineering Punjab Technical University Gaini Zail Singh Campus Bathinda, Punjab

Abstract– Wireless sensor networks with the dynamic applications become a foremost attention-grabbing area of research, in past few years. Sensor nodes (SNs) in the network are micro-electromechanical battery powered devices with limited energy budget. Clustering is an efficient technique to extend the scalability and network lifetime, by reducing the energy consumption. But for the cluster heads (CHs) as the transmission distance to sink increase the transmission energy also increases. This paper focuses on how to reduce the transmission distance so that the energy consumption in transmission can be reduced, by using two level cluster heads. Proposed protocol is compared with Low-Energy Efficient Clustering Hierarchy (LEACH), Stable Election Protocol (SEP) and Distributed Energy Efficient Clustering (DEEC).Our simulation results shows that our proposed protocol outperforms all these protocols in terms of reliability and network lifetime..

Index Terms: TLH-DEEC; Network Lifetime; Total Energy Dissipation; Two Level Clustering.

1. INTRODUCTION

   1. Introduction

      Wireless sensor network (WSN) has emerged as a useful supplement to the modern wireless communication networks for data acquisition and processing. With the advances in the technology of micro-electromechanical system (MEMS), developments in wireless communications and wireless sensor networks have also emerged. Wireless sensor network can be described as an autonomy system consisting of lots of sensor nodes, deployed in a sensor field, designed to intercommunicate by wireless radio, can collaborate information by real monitoring and transfer this information to base station (BS) or Sink. Functions performed by SNs of wireless sensor field, make wireless sensors very useful for monitoring natural phenomena, environment changes

      ,border field security, disaster management, medical applications, object tracking, habitat monitoring, ,traffic monitoring etc. It does not need a fixed support so it has good application prospect. Until now the network subsystem is considered for work area, in which energy management operation are applied on sensor node as well as on network. Energy saving techniques are applied on network layer or MAC layer [15].

      Data transmission is very expensive in terms of energy expenditure, while data processing consumes significantly less [15], especially for long distance data transferring. As the transmission distance increase the energy consumption

      also increases. So, the direct communications between SNs and the base station are not encouraged. Transmissions distance should be kept smallest possible in order to prolong the network lifetime. Concept of Hierarchical-based or cluster based routing enforces a structure on the network to use the energy efficiently, extend the lifetime and scalability. LEACH [1] uses clustering technique. Sensor network can be made where sensors are divided into groups

      1. clusters with a leader (often called cluster head (CH)).CH can be elected by the SNs or pre-elected by the network designer. CHs are elected probabilistically where each node becomes a CH according to random number compared with threshold defined. SNs do low-power communication only with cluster heads, which process and transfer the aggregated information to BS. This prolongs the battery life of individual nodes as small transmit distances for most nodes; only few nodes (which are chosen as cluster heads) to transmit for long. The development of clustered sensor networks used to decrease system latency and save energy while performing data fusion and increase system throughput. Operation is broken up into rounds where each round has two phases:

         • Setup phase, when election of CH and formation of cluster is performed,

         • Steady- state phase, when data is transmitted from node to CH; CH then aggregates this data and transmits it to BS.

           Low-Energy Adaptive Clustering Hierarchy (LEACH)[1], Power-Efficient Gathering in Sensor Information Systems (PEGASIS)[11],Threshold Sensitive Energy Efficient Network(TEEN) [6], Hybrid, Energy- Efficient Distributed clustering (HEED)[7] are propose for homogeneous networks; here the term homogeneous refers to nodes having same initial energy . But under the conditions of network heterogeneity this protocol will not be efficient and gives poor performance. Stable Election Protocol (SEP)[2], Energy Efficient Clustering Scheme (EECS), Distributed Energy Efficient Clustering (DEEC)[4] are proposed for heterogeneous network(nodes may have different initial energy).

           DEEC [4] is clustering-based algorithm in which cluster head is selected on the basis of probability of ratio of residual energy of each node and the average energy of the network. The rotating epoch for being cluster heads for each

           node is different according to its initial energy and residual energy. The node having more energy has more chances to be a cluster head. It prolongs the stability period of the network and more effective messages than other heterogeneous protocols. In this paper our proposed scheme is TLH-DEEC which follows the thoughts of DEEC [4] which consider heterogeneity in terms of energy and two levels of cluster heads. So that the transmission distance can be reduced and energy of cluster head node can be saved. This enhances the reliability of network as time interval before the death of first node (called stability period) increase.

   2. Related Work

      Heinzelman et al. proposed LEACH that [1] guarantees that the energy load is well distributed by dynamically created clusters where cluster heads dynamically elected according to determined optimal probability. LEACH is base for all the clustering algorithms. In LEACH sensor network is not optimized in case of heterogeneity and cluster head election is unstable. Because of equal probability for nodes with different energy, instability period (time from death of first node to last node died) become large as nodes with more energy are left equipped with almost same energy. PEGASIS [11] is a chain based protocol which avoids cluster formation and uses only one node in a chain to transmit to the BS. Threshold sensitive Energy Efficient sensor Network protocol (TEEN)[6] is proposed by Manjeshwar et. al..TEEN uses a data-centric mechanism. The cluster head broadcasts two thresholds to the nodes. These thresholds are hard and soft thresholds for selection of sensed data to transmit.

      Smaragdakis, et al. proposed Stable Election Protocol (SEP) [2] which is two-level heterogeneous network where weighted probability is used for sensor nodes to elect cluster heads. Weight is given by ratio of initial energy of each node and initial energy of normal node. SEP yields longer stability region.

      Qing et al. worked on heterogeneous WSN and proposed a protocol named as Distributed Energy Efficient Clustering (DEEC) [4].It is an Energy-Efficient clustering protocol which use energy of each node efficiently. Cluster head selection is done on the basis of weighted probability correlating with the ratio of residual energy of each node and average energy of the network. So that the nodes with more energy should have given more chance to be cluster head compared to nodes with less energy. We discuss hierarchical clustering technique to minimize the transmission distance among cluster heads and base station which is not adopted in DEEC. Saving transmission distance save transmission cost which enhance the lifetime.

      Elbhiri et al, proposed Developed-DEEC (DDEEC)[12]. DDEEC introduces more efficient cluster head selection to improve network lifetime. Saini et al, proposed Enhanced- DEEC (EDEEC) [13] by using three level heterogeneity and it enhance lifetime and more effective messages. Saini et al, proposed Threshold-DEEC(TDEEC)[14] with modified threshold for CH selection.

   3. Motivation

   Many heterogeneity aware algorithms are proposed to enhance network lifetime. Every algorithm does not work efficiently for different networks having different heterogeneity levels and fails to maintain the same stability period and lifetime as in previous heterogeneous WSNs. We reviewed all variants of energy efficient protocols, where different protocols perform well under different conditions. But if the transmission distance of cluster head there is possibility to save more energy which will prolong the network lifetime. This possibility of enhancement motivated us.

2. TWO LEVEL HIERARCHICAL DISTRIBUTED ENERGY-EFFICIENT CLUSTERING PROTOCOL

   TLH-DEEC is hierarchical based clustering routing protocol which follows the DEEC scheme; where all nodes use the initial and residual energy level for defining the cluster-heads. Cluster heads are responsible not only for sending data to base station but also collecting and processing the data from the associated non-CH sensor nodes. If the distance to base station increase that increases transmission cost. Proposed protocol is aimed to balance the energy load of cluster heads to minimize the transmission cost by using two levels of cluster heads. Primary cluster heads are chosen with probability based on ratio of residual energy of each node and average energy of the network and Secondary Cluster heads are chosen from primary cluster heads with some probability. The proposed protocol is described by steps given below:

   1. Deployment of Sensors: Sensor nodes are deployed uniformly in M×M region with two level of energy heterogeneity. Two types of SNs are deployed in heterogeneous WSNs with different energy. Advanced nodes are nodes with more energy and normal nodes with comparatively less energy. Energy heterogeneity benefits in the case of re-energization of sensor network and where deployment of new nodes is costly then embedded batteries. Suppose total n number of nodes are deployed with initial energy of each normal sensor node and m is percentage of advanced nodes, from total sensor nodes, with

      (1+) initial energy. Total (initial) energy of the system is

      1 + 1 + = (1 + )

      (1)

      So, in heterogeneous networks, total energy of network is increased by a factor of 1 + and network has virtually

      more nodes (with the same energy as the normal nodes) and times more energy. In Fig. 1, Normal nodes are represented as o and Advanced nodes are represented as

      +. To avoid the change of the topology, we assume that the nodes are stationary in our network.

   2. Calculation of Average distance: Average distance of all the nodes and base station is calculated =

      1

      where i is for sensor node. Fig. 1 has represented sensor nodes with distance more than average distance in red colour and other in blue colour.

      Figure 1: Sensor Deployment Figure 2: Data transmission

   3. Cluster head election: Traditionally as per LEACH, Cluster head algorithm is broken into rounds. At each round, each eligible sensor node decides whether to become a

      is related with (), average energy of the network and (), residual energy of each node at round r. Average energy of network is estimated as in DEEC[4].

      cluster head based on probability threshold. Sensor node is

      eligible if it has not been cluster head once in present epoch. Epoch is number of rounds in which each sensor node become cluster head at least once. Then eligible sensor nodes choose a random number between 0 and 1. If the number chosen is less than a threshold T(s) the node

      = 1 (1 ) (4)

      is energy dissipated in network during a round

      = (2 + + 4 + 2 ) (5)

      becomes a cluster head for current round. The threshold is set as:

      )

      Where k is optimum number of clusters, is energy used for data aggregation and L are bits of data.

      = 1 1

      (2)

      = , = 0.765

      0 otherwise

      (6)

      2

      2

      Where probability of node to become cluster head, r is the current round number and G the set of sensor nodes which are eligible to be cluster head. Using this threshold,

      As we assume that nodes are uniformly distributed in M×M region and k is calculated as

      each node will be a cluster head per epoch [2]. Epoch is

      =

      (7)

      different based on residual energy () in each round. TLH-DEEC adapt rotating epoch of each node to its energy. The nodes with high initial and residual energy have more

      2

      2

      chance to be cluster head . is optimum number of cluster heads which is used as reference value for calculating .Weighted probabilities to be a cluster head for normal and advanced nodes are:

      is energy dissipated per bit to run transmitter ( ) or receiver( ) circuit. We use similar energy model as proposed in [1]. To achieve an acceptable Signal-to-Noise Ratio (SNR) in transmitting an l-bit message over a distance d, the energy dissipation by first order radio model is:

      =

      ( ) (1+ )( )

      (3)

      , =

      + 2

      + 4 >

      (8)

      (1+ ) ( )

      (1+ )( )

      and depend on the radio model used, and d is the distance between the sender and the receiver. Both the free space (2 power loss) and the multi path fading (4

      power loss) channel models were used which depend on the distance between the transmitter and the receiver. is threshold distance. Threshold distance is taken 70m.

      R denotes the total rounds of the network lifetime and it can be calculated as

      calculated at each round of the protocol. Less the energy dissipation tends to longer lifetime of network.

      4. SIMULATION AND RESULTS

      =

      (9)

      The results considered in this paper are based on analysis of efficiency of proposed protocol and validated by using MATLAB. For analysis of our simulation results, we consider a heterogeneous sensor network with n sensor

      The nodes with more residual energy are nodes with

      more probability to be cluster head. R is calculated to find the ideal value of network lifetime. Cluster heads selected in this phase are called primary cluster heads.

   4. Selecting Secondary Cluster Head: Secondary cluster heads are selected from the primary cluster heads. Secondary cluster heads are primary cluster heads whose distance from the sink is less than the average distance of all the nodes from sink. And other cluster heads whose distance

      nodes which are randomly deployed in a square field with fixed location. Sensor nodes are of two types: Advanced nodes and Normal nodes. Advanced nodes are nodes with times more energy than normal nodes. Simulation parameters considered are mentioned in Table 1 shown below.

      Number of nodes	100	Initial Energy, Eo 0.5J
      Area	100×100	= = 50nJ/bit
      Base station	(50,175)	10pj/bit/ m2
      	0.1	0.0013pJ/bit/m4
      Message size, L	4000bits	5nJ/bit

      TABLE 1 SIMULATION PARAMETERS

      from sink is more than average distance,

      or which are

      far away, are primary cluster heads. Primary Cluster heads dont transfer their data directly to sink, they get associated with the nearest secondary cluster head and transfer own aggregated data to secondary cluster head. Secondary cluster heads transmit fused data of own and associated primary cluster heads to sink. Numbers of secondary cluster head are chosen with some probability from primary cluster heads.

   5. Data transmission: Data transmission is done by two level cluster heads as shown in Fig. 2. When cluster are formed, the nodes start sensing the data from environment and non-cluster head nodes send their sensed data to primary cluster heads which process the data and send their data to secondary cluster heads by using TDMA slots, which fuse the whole data send the processed data to base station by single-hop method.

      The green colour lines show the data transmission to sink by secondary cluster heads and red colour lines show data transmission from primary cluster heads to secondary cluster heads and blue colour lines are for non-cluster head nodes to associated cluster heads.

3. PERFORMANCE METRICS

The performance metrics or parameters used to study and evaluate the clustering protocols are stability period, network lifetime, number of nodes alive, and total energy consumption of network

• Stability Period: It is the time interval from the start of the simulation operation until the death of the first node.

• Network Lifetime: It is time interval from start of operation until the death of the last alive node.

• Number of alive nodes: It is a measure that reflects the total number of nodes that has not yet used all of their energy.

• Network energy consumption: It is a measure to find the total energy dissipation of the network. It is

Assumptions and Properties of the Network: For the sensor network described in previous section have some assumptions for sensor nodes and network.

• Sensor Nodes are uniformly deployed in the wireless sensor network.

• Base Station or sink collects the data from sensor nodes. It is equipped with unlimited battery life.

• Sensor nodes always have data to transmit.

• Nodes are location-unaware, i.e. not equipped with GPS-capable antennae.

• All nodes have similar capabilities in terms of processing and communication and of equal significance.

1. Network Lifetime: Network lifetime is time from start of simulation to the time last node of network died. In wireless sensor network, network lifetime is considered as sum of stable period and instable period. Larger the stability period more the reliability of network. Results shown in Fig. 3 are taken with case where m=0.1 and a=3.TLH-DEEC has improved the stability period 22.14% than DEEC, 39.95% than SEP and 51.19% than LEACH. SEP has improved stability period by 18.73% as compared to LEACH, DEEC has improved stability period by 22.86% compared to SEP and TLH-DEEC has improved stability period by 22.14% than DEEC. The nodes remain alive for long time in LEACH because of unstable cluster formation because the equal probability of each node. Advanced nodes remain alive for long, as energy of nodes is not used properly. All nodes remain alive for long time (stability period) in TLH- DEEC so its having high reliability. Fig. 3 show alive nodes and Fig. 4 show dead nodes in network. Stability period is compared for different values where value of m varies from 0.1 to 0.9 and a varies from 0.5 to 5.The Fig. 5 shows that TLH-DEEC give us high stability in comparison of other protocols.

   Figure 3:Comparison of Alive nodes Figure 4:Comparison of dead nodes

   Figure 5: Round first node died (a) m=0.1 and a varies from 0.5 to 5 and (b) a=1 and m varies from 0.1 to 0.9

2. Throughput: Throughput is another metric to judge the efficiency of protocol. Throughput is number of data packets transmitted to base station. This depends on number of packets transmitted to cluster heads. A base station receiving more data packets confirms the efficiency of routing protocol. Throughput depends on life time of sensor network but not always. It is also affected by number of nodes alive. More the nodes alive more the data will be transmitted. Total Packets transmitted to CHs in LEACH are 94656, in SEP are 83745, in DEEC are 93942 and 110176 by TLH-DEEC. Considering the simulated results as shown in

   Fig. 6, we deduce that, maximum throughput is achieved by TLH-DEEC.

3. Total Energy Dissipation: Less the energy consumption in network gives a long lifetime to the network. TLH-DEEC is improved algorithm of DEEC to save the energy of the network. Secondary cluster heads are taken for data transmission, for the cluster heads which are far from sink. So the energy of each node is saved hence the energy of network is saved in each round as shown in Fig. 7.

Figure 6: Throughput data transmitted from leaf node to Cluster heads

5. CONCLUSION

There are number of protocols discovered in heterogeneous wireless sensor networks for stability improvement. We proposed TLH-DEEC which is an energy-aware adaptive clustering protocol with two levels of clustering used in heterogeneous wireless sensor networks. Cluster head selection is same as in DEEC. And far cluster heads send their data to nearest cluster head, whose distance from sink is less. So transmission cost is saved which reduce the energy consumption of network. This improves the network lifetime, stability period and throughput by using two level hierarchical cluster heads.

Figure 7: Total Energy Consumption

REFERENCES

1. Heinzelman, W.R. and Chandrakasan, A. and Balakrishnan, H., Energy efficient communication protocol for wireless micro sensor networks, System Sciences, Proceedings of the 33rd Annual Hawaii International Conference on, pages (10pp), 2000.

2. Smaragdakis, G. and Matta, I. and Bestavros, A., SEP: A stable election protocol for clustered heterogeneous wireless sensor networks, Boston University Computer Science Department, 2004.

3. Aderohunmu, F.A. and Deng, J.D., An Enhanced Stable Election Protocol (E-SEP) for Clustered Heterogeneous WSN.

4. Qing, L. and Zhu, Q. and Wang, M., Design of a distributed energy efficient clustering algorithm for heterogeneous wireless sensor networks, Computer communications, volume (29), no. (12), pages (22302237), 2006.

5. Heinzelman, W.R., Chandrakasan, A.P., Balakrishnan, H.,An application- specific protocol architecture for wireless micro sensor networks, IEEE Transactions on Wireless Communications 1 (4) (2002) 660-670.

6. Manjeshwar, A., and Agarwal, D. P. , "TEEN: a routing protocol for enhanced efficiency in wireless sensor networks," In 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, April 2001.

7. Younis, O., Fahmy, S., "HEED: A hybrid, energy efficient, distributed clustering approach for ad hoc sensor networks", IEEE Transactions on Mobile Computing vol 3, no 4, pp 660-669, 2004.

8. Kumar, D., Aseri, T.C. and Patel, R.B. EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks Computer Communications 32(2009), pp.662-667

9. Katiyar, V., Chand, N., Soni, S.Clustering Algorithms for Heterogeneous Wireless Sensor Network: A Survey, International Journal Of Applied Engineering Research, Dindigul (2010),ISSN- 0976-4259

10. <>Akkaya, K., Younis, M. A survey on routing protocols for wireless sensor networks Ad Hoc Networks 3 (2005) 325349

11. Lindsey, S. and Raghavendra, C.S. (2002). PEGASIS: power efficient gathering in sensor information systems, in: Proceedings of the IEEE Aerospace Conference.

12. Elbhiri, B. ,Rachid, S., fkihi, S.E., Aboutajdine, D., Developed Distributed Energy-Efficient Clustering (DDEEC) for heterogeneous wireless sensor networks, I/V Communications and Mobile Network (ISVC), 2010 5th International Symposium on, Volume 2,October 2010.

13. Saini, P. ,Sharma, A.K., E-DEEC- Enhanced Distributed Energy Efficient Clustering Scheme for heterogeneous WSN,1st International Conference on Parallel, Distributed and Grid Computing ,2010

14. Saini, P. ,Sharma, A.K., Energy Efficient Scheme for Clustering Protocol Prolonging the Lifetime of Heterogeneous Wireless Sensor Networks, International Journal of Computer Applications, Volume 6,September 2010

15. A. Giuseppe, M. Conti, F. D. Mario, P. Andrea, Energy Conservation in wireless sensor networks: a survey