A Comparative Analysis of Hierarchical Routing Protocols in Wireless Sensor Networks

A Comparative Analysis of Hierarchical Routing Protocols in Wireless Sensor Networks

Gagandeep Singh 1, Anurag Sharma 2, Harjitpal Singh 3 Department of Electronics and Communication Engineering Quantum School of Technology, Roorkee (INDIA)1

CT Institute of Engg. Mgmt., & Technology, Jalandhar(INDIA)2,3

Abstract

Clustering is a key technique to improve the network lifetime, decrease the energy consumption and increase the scalability of the sensor network. In this paper, the different clustering algorithms for heterogeneous Wireless Sensor Networks (WSNs) are examined to study its performance with the impact of heterogeneity of the nodes. The main objective of this paper is to compare the different hierarchical routing protocol and propose an optimized algorithm for the clustering in order to prolong network lifetime. Prolonging network lifetime is the way to provide energy efficient WSNs.

Keywords: Wireless Sensor Networks, Clustering, SEP, TSEP, DSEP.

1. Introduction

   The sensor network is collection of several thousands or more tiny immobile sensor nodes also known as motes, densely deployed in the service area on an ad-hoc basis to sense and transmit regularly some defined characteristics of surrounding environment. Fig. 1 shows a typical wireless sensor network (WSN). All nodes have a small microprocessor, a radio chip, some sensors, and are generally battery powered which restricts the network lifetime. Every distributed sensor nodes have the ability to gather information, process and route them to base station node. An associated base station (or sink node) collects the data information forwarded by the sensing nodes on a data-centric basis. The sensors are simple, inexpensive and their power source is irreplaceable.

   Fig. 1: A typical Wireless Sensor Network [1]

   Early study on wireless sensor networks mainly focused on technologies based on the homogeneous wireless sensor network in which all nodes have same system resource. However, heterogeneous wireless sensor network is becoming more and more popular nowadays. And the results of researches [3][4] show that heterogeneous nodes can prolong network lifetime and improve network reliability without increasing the cost. A typical heterogeneous wireless sensor networks consists of a large number of normal nodes and a few heterogeneous nodes. The normal nodes are source-constrained and having low cost which are used to sense and issue data report. The heterogeneous nodes are expensive than normal nodes and provides data filtering, fusion and transport [2].

   In a hierarchical topology, nodes are organized into a specific set of clusters which perform different tasks in wireless sensor network as per the requirement. Generally, in each cluster nodes with higher energy act as cluster head (CH) and perform the task of data processing and information transmission towards base station, while nodes with low energy act as member nodes (MNs) and perform the task of information sensing as shown in fig. 2. In the last few years, a relatively large number of clustering routing protocols

   have been developed for WSNs. This paper is an attempt to broadly review and critically discuss the most prominent clustering routing algorithms that have been developed for WSNs.

   Fig.2. Nodes communicate to Base Station through Cluster Heads

2. Related Work

   Clustering in wireless sensor networks (WSNs) is the process of dividing the nodes of the WSN into groups, where each group agrees on a central node, called the cluster head, which is responsible for gathering the sensory data of all group members, aggregating it and sending it to the base station(s). The first clustering based routing protocol for WSNs was LEACH. This protocol uses random rotation of cluster head to distribute energy load between sensor nodes to enhance stability period and network lifetime. LEACH is designed for homogeneous networks which refer to the nodes having same initial energy. Due to lack of heterogeneity the LEACH was not very efficient [6].

   In the PEGASIS protocol all network becomes like a single sequence/chain in which only one node of the chain aggregates all data and sends it to the sink [8]. The complexity of this protocol is based on the requirement of the global knowledge of the network topology. Moreover, as each node had a fixed path and if a node fails during the transmission then the discovery of a new route becomes difficult.

   Stable Election Protocol (SEP) is based on weighted election probabilities of each node to become cluster-head (CHs) according to their respective energy [9]. This approach ensures that the cluster head election is randomly selected and its distribution is based on the fraction of energy of each node assuring a uniform use of the nodes energy.

   Threshold sensitive Energy Efficient sensor Network protocol (TEEN) is a hierarchical routing

   protocol which manages sudden changes in the sensed attributes like temperature, etc [10]. This protocol uses data-centric approach through which the nodes sense the environment continuously, but as compare to the proactive network the energy consumption in this algorithm is low.

   TSEP [11] is a reactive routing protocol in which nodes have three different levels of energies. Cluster heads selection is threshold based which causes increase in stability period and network life.

   A new SEP protocol called as Deterministic- SEP (D-SEP) is proposed [12], for electing cluster heads in a distributed fashion in two-, three-, and multi- level hierarchical wireless sensor networks.

3. Comparison of TSEP and DSEP Clustering Routing Protocols in WSNs

   In this section, we analyze two classical WSN clustering routing algorithms in detail and present a more comprehensive and critical survey of prominent clustering routing protocols for WSNs. For the purpose of this study, we use similar radio communication and consumption model as reported in [9].

   1. TSEP

      TSEP (Threshold sensitive Stable Election Protocol) is reactive routing protocol which uses three heterogeneous nodes such normal nodes, intermediate nodes and advance nodes [11]. Advance nodes having energy greater than all other nodes, intermediate nodes having energy in between the normal nodes and advance nodes whereas the left behind nodes are the normal nodes. Intermediate nodes can be selected by using a fraction of j, and the relation that energy of normal nodes is times more than that of normal nodes. Energy for normal nodes is Eo, for advance nodes is Ea = Eo(1+A) and energy for intermediate nodes can be computed as Ei = Eo (1 + ), where = A/2 . The total energy of normal nodes, advance nodes and for intermediate nodes will be, n*j(1+A), n*Eo(1- m-n*j), and n*m*Eo(1+A) respectively. Thus, the total energy of all the nodes is, n*Eo(1-m-j*n) + n*m*Eo(1+A) + n*j(1+ ) = n*Eo(1+m*A + j*n) where, n is number of nodes, m is proportion of advanced nodes and j is proportion of intermediate nodes to total number of nodes n. The optimal probability of nodes to be elected as a cluster head is calculated by using following formulas:

      pn = p*/ (1+m*A + j*n) .. (1)

      pi = p*(1+ )/ (1+m*A + j*n) .. (2) pa = p*(1+A)/ (1+m*A + j*n) .. (3)

      Further, the threshold level factor is

      considered to ensure the selection of cluster head in which each node generates randomly a number inclusive of 0 and 1. Now, if generated value is less than threshold value then the node become Cluster head [6]. For all these type of nodes we have different formulas for the calculation of thresholddepending on their probabilities, which are given below:

      Tn = pn / [ 1 pn ( r*mod 1/pn) ] , if nn G ..(4) Ti = pi / [ 1 pi ( r*mod 1/ pi) ] , if nn G ..(5)

      Ta = pa / [ 1 pa ( r*mod 1/ pa) ] , if na G ..(6)

      G, G and G are the set of normal nodes, intermediate nodes and set of advanced nodes that has not become cluster heads in the past respectively

   2. DSEP

      In D-SEP, the threshold value is modified by using residual energy and set as [12]:

      T(Si)=[pi/1- (pi *(r mod1/ pi))]*[Eres+(rc div1/pi)*(1-Eres)]

      .. (7)

      where threshold is set differently and dependent on pi that has been set according to two-, three-level heterogeneity Here rc is the number of consecutive rounds in which a node has not been cluster-head. When rc reaches the value 1/pi the threshold T(Si) is reset to the value. Thus, the chance of node n to become cluster head increases because of a high threshold. Additionally, rc is reset to 0 when a node becomes cluster head. Thus, it is ensured that data is transmitted to the base station as long as nodes are alive.

      Pi = p*(1+ )* Eres / (1+m*A + j*n)* Eavg ..(10) Pa = p*(1+A)* Eres/ (1+m*A + j*n) * Eavg ..(11)

      Threshold value for cluster head selection is calculated for normal, advanced, super nodes by putting above values in Eq. (7) otherwise it is zero. G, G and G is the set of normal and advanced nodes.

4. Results and Discussion

   In our work, a comparative analysis between DSEP and TSEP protocols on the basis of stability period and network lifetime is achieved after creating a 100m x100m region of 100 sensor nodes deployed randomly. The sink or base station is located at the center point (50m×50m). The packet size that the nodes send to their cluster heads as well as the combined packet size that a cluster head sends to the sink is set to 4000 bits. The parameters used in the simulation are mentioned in Table 1.

   Parameters	Value
   Network Field	(100,100)
   Number of Nodes	100
   Eo (Initial Energy of Nodes)	0.5 J
   Message Size	4000 bits
   Eelec	50 nJ/bit
   Eamp	0.0013 pJ/bit/m4
   Efs	10 nJ/bit/m2
   EDA	5 nJ/bit/signal
   Do ( Threshold Distance)	70 m

   Parameters	Value
   Network Field	(100,100)
   Number of Nodes	100
   Eo (Initial Energy of Nodes)	0.5 J
   Message Size	4000 bits
   Eelec	50 nJ/bit
   Eamp	0.0013 pJ/bit/m4
   Efs	10 nJ/bit/m2
   EDA	5 nJ/bit/signal
   Do ( Threshold Distance)	70 m

   Table 1 Simulation Parameters

   The weighed election probability for normal node, intermediate node and advance node is considered on the basis of fractional difference in their initial energy level. The reference value of pi is different for these types of nodes. The probabilities of normal, advanced and advance nodes are [12][14][15]:

   Pi = { Pn, Pi, Pa } …(8)

   where

   Pn = p*Eres / (1+m*A + j*n)* Eavg ..(9)

   1. Stability Period

      Stability period is the time interval from the start of network operation until the death of the first sensor node. Fig. 3 shows the number of dead nodes for m =0.4, A=1, = 0.4, j= 0.2 over 5000 rounds. It is observed that for TSEP with three types of nodes having different initial energy, the first sensor node dies at the round of around 1210 whereas due to use of

      residual energy concept in DSEP, the first sensor node dies at the round of around 1435 which is more than TSEP. It shows that DSEP have more stable region than TSEP.

      Fig.3. Number of dead nodes per round

   2. Network Lifetime

      Network lifetime is defined as the time interval from the start of operation (of the sensor network) until the death of the last alive node. Fig. 4 shows the lifetime of the sensor network for m =0.4, A=1, = 0.4, j= 0.2 over 5000 rounds.

      Fig.4. Number of alive nodes per round

      We can observe that for the TSEP protocol, the last sensor node dies 3946 rounds whereas for DSEP the last sensor node still alive over 5000 rounds. It shows that the lifetime of network for DSEP is more than TSEP.

5. Conclusion

   In this paper, we compare two hierarchical routing protocols TSEP and DSEP clustering algorithms for heterogeneous wireless sensor network on the basis of network lifetime and stability period. TSEP is reactive routing protocol where nodes have three different levels of energies. CHs selection is threshold based, due to three levels of heterogeneity and the D-SEP is based on the weighted probabilities to obtain the threshold for normal, intermediate and advanced nodes and that is used to elect the cluster head in each round. Our simulation result confirmed that the DSEP approach provides a longer network lifetime and stability as compared to the existing TSEP protocols.

6. REFERENCES

1. M M Islam , M A Matin, T K Mondol, Extended Stable Election Protocol (SEP) for Three level Hierarchical Clustered Heterogeneous WSN in proceeding of IET Conference on Wireless Sensor Systems (WSS 2012), London, 18-19 June 2012, pp: 1- 4.

2. Liyang Yu, Neng Wang, Wei Zhang, Deploying a Heterogeneous Wireless Sensor Network, in Proceeding of International Conference on Wireless Communications, Networking and Mobile Computing, 2007 (WiCom 2007)., Singapore, September 21st 25th

   ,2007. pp: 2588 – 2591.

3. R. Kumar, V. Tsiatsis, and M.B. Srivastava, Computation Hierarchy for In-Network Processing, in Proc. of the 2nd Intl. Workshop on Wireless Networks and Applications, San Diego, CA, Sept. 2003, September 2003. pp: 1-10.

4. S. Rhee, D. Seetharam, and S. Liu, Techniques for Minimizing Power Consumption in Low Data-Rate Wireless Sensor Networks, in Proceeding of IEEE Wireless Communications and Networking Conference, Atlanta, GA, March, 2004. Vol. 3, pp: 1727-1731.

5. Xuxun Liu, A Survey on Clustering Routing Protocols in Wireless Sensor Networks, Sensors, Vol. 12, Issue 8, pp: 11113-11115.

6. W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. "Energy-efficient communication protocol for wireless microsensor networks", Proceedings of the 33rd Hawaii International

   Conference on System Sciences (HICSS-33), (2000), pp: 1-10.

7. A. A. Khan, N. Javaid, U. Qasim, Z. Lu, Z. A. Khan, HSEP: Heterogeneity-aware Hierarchical Stable Election Protocol for WSNs, in Proceeding of Seventh International Conference on Broadband, Wireless Computing, Communication and Applications, 2012, pp: 373-378

8. S. Lindsey, C.S. Raghavenda, "PEGASIS: power efficient gathering in sensor information systems", Proceeding of the IEEE Aerospace Conference, Big Sky, Montana, 2002, Vol. 3, pp: 1125-1130.

9. Georgios Smaragdakis, Ibrahim Matta, Azer Bestavros, SEP: A Stable Election Protocol for clustered heterogeneous wireless sensor networks, Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 2004), 2004.

[10]. Manjeshwar, E.; Agrawal, D.P. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks, in Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS), San Francisco, CA, USA, 2327 April 2001;pp: 20092015.

1. A.Kashaf, N. Javaid, Z. A. Khan, I. A. Khan, TSEP: Threshold-sensitive Stable Election Protocol for WSNs, in Proceeding of 10th International Conference on Frontiers of Information Technology, 2012, pp: 164-168.

2. Manju Bala, Lalit Awasthi, Proficient D-SEP Protocol with Heterogeneity for Maximizing the Lifetime of Wireless Sensor Networks, I.J. Intelligent Systems and Applications, vol.7, 2012, pp: 1-15.

3. Q. Li, Z. Qingxinand W. Mingwen, "Design of a distributed energy efficient clustering algorithm for heterogeneous wireless sensor networks," Computer Communications, vol. 29, 2006, pp. 2230-2237.

4. Parul Saini and Ajay K Sharma, Energy Efficient Scheme for Clustering Protocol Prolonging the Lifetime of Heterogeneous Wireless Sensor Networks, International Journal of Computer Applications (0975 8887), Volume 6, Issue.2, 2010, pp. 31-36.

5. Y. Mao, Z. Liu, L. Zhang, X. Li, An Effective Data Gathering Scheme in Heterogeneous Energy Wireless Sensor Networks, Proceedings of

International Conference on Computational Science and Engineering, 2009, pp. 338-343.