The Comparative Study Of Hierarchical Or Cluster Based Routing Protocol For Wireless Sensor Network

The Comparative Study Of Hierarchical Or Cluster Based Routing Protocol For Wireless Sensor Network

Atul Pratap Singp, Nishu Sharma2

1, 2 M. Tech Scholars, School of Computer Science & Engineering,

Galgotias University, Greater Noida

Abstract

Wireless sensor network has gained increasing attention for the research community and users in the last years. The network layer is responsible for the packet delivery and implements an addressing scheme to accomplish this. It mainly provides the best path for data transfer in wireless sensor network. Routing is the more challenging in wireless sensor network due to their limited recourses in term of available energy, processing capability and communication. So the routing protocol becomes a good area for the research community. Based on the network structure routing protocol divide in two category first is flat routing and second is hierarchical or cluster based routing. Because of some advantage cluster based routing protocol becomes an active protocol for wireless sensor network. In this paper we will study of latest cluster based protocol and comparisons to each other on the base of some parameter and advantages or disadvantages.

Keywords: Clustering Based Routing, Cluster Construction, Wireless Sensor Networks

1. Introduction

   In wireless sensor network recent advances in Micro- Electro-Mechanical Systems (MEMS) in tandem with significant research in digital signal processing (DSP) have led to the great development of micro-sensors. Wireless implementation makes the wide deployment of sensor nodes more feasible than before. Routing is one of the critical technologies in WSNs. Opposed to traditional ad hoc networks, routing in WSNs is more challenging as a result of their inherent characteristics based on the network structure routing protocol divides into two categories: flat routing and hierarchy or cluster based routing. In small-scale networks flat routing protocols are relatively effective. However, it is relatively undesirable in large-scale networks because resources are limited. The some flat routings

   in WSNs are Trajectory Based Forwarding (TBF) [1], Sensor Protocols for Information via Negotiation (SPIN) [2] , Rumor, Greedy Perimeter Stateless Routing (GPSR) [3] , Directed Diffusion (DD)[4], Energy-Aware Routing (EAR)[5] , Gradient-Based Routing (GBR)[6] , Sequential Assignment Routing (SAR)[7] , etc.

   Cluster based routing is becoming an active branch of routing technology in WSNs on account of a variety of advantages, such as more scalability, data aggregation/fusion, less load and less energy consumption clustering routings protocols in WSNs include Low-energy Adaptive Clustering Hierarchy (LEACH)[8] , Hybrid Energy-Efficient Distributed clustering (HEED) [9] , Distributed Weight-based Energy-efficient Hierarchical Clustering protocol (DWEHC)[10], Two-Level Hierarchy LEACH (TL- LEACH)[11] , Unequal Clustering Size (UCS) [12] model, Energy-Efficient Uneven Clustering (EEUC)[13] algorithm, Base-Station Controlled Dynamic Clustering Protocol (BCDCP)[14], Power- Efficient Gathering in Sensor Information Systems (PEGASIS)[15], Threshold sensitive Energy Efficient sensor Network protocol (TEEN)[16], The Adaptive Threshold sensitive Energy Efficient sensor Network protocol (APTEEN)[17], Concentric Clustering Scheme (CCS)[18], and etc. Given the unique characteristic of WSNs, cluster-based protocols show significant advantages over flat strategies. The followings are several advantages of clustering schemes that introduce them as the most compatible protocols with WSNs attributes:

   • Decrease the total transmission power.

   • Balancing the exhausting load among all nodes.

   • Minimize the bandwidth demand and efficient use of limited channel bandwidth.

   • Decrease routing and topology maintenance overhead.

   • Remove the redundant and highly correlated data in the aggregation process.

   • Minimize data collision and interference in the data transmission process by use of

     multi-power levels in the cluster-scale and network-scale communications.

   • Increasing the manageability and scalability of the network.

   • Localizing the route setup within the cluster boundaries and thus generating small-size routing tables.

     The cluster based protocol has two phases [19]: Setup phase and Steady state phase. A setup phase consists of two stages: Cluster head selection and Cluster formation. Steady state phase consists these two stages: Data aggregation and Data communication.

     Fig.1 Clustering process

2. Related work

   1. Advantage and Objectives of Clustering Compared with flat routing protocols in WSNs, clustering routing protocols have a variety of advantages, such as more scalability, less load, less energy consumption and more robustness. In this section, we summarize these advantages as well as the objectives [20] of WSN clustering as follows:

      1. Data aggregation/fusion: The most important data aggregation/fusion method in wireless sensor network is clustering data aggregation, in which each CH aggregates the collected data and transmits the fused data to the BS

   2.1.2 Less Energy Consumption: Clustering with intra-cluster and inter-cluster communications can reduce the number of sensor nodes performing the task and reduce the distance of node for communications, thus allowing less energy consumption for the entire network.

   1. More Scalability: In the wireless sensor network clustering routing scheme, sensor nodes are divided into a variety of clusters with different assignment levels. The CHs are responsible for communication. Compared with a flat topology, this kind of network topology is easier to manage, and

      more scalable to respond to events in the environment.

   2. Less load: For clustering topology, all cluster members only send data to CHs, and data aggregation is performed at the CHs, which help to dramatically reduce transmission data and save energy. In addition, the communication set up within the clusters which thus reduce the size of the routing table stored at the individual sensor nodes.

   3. More Robustness: A clustering routing scheme only needs to cope with these changes within individual clusters, thus the entire network is more robust and more convenient for management.

   4. Collision Avoidance: Resources can be allocated orthogonally to each cluster to reduce collisions between clusters and be reused cluster by cluster. As a result, the multi-hop clustering model is appropriate for large-scale WSNs.

   5. Latency Reduction: The mode of data transmissions only out of the cluster helps avoiding collisions between the nodes. Accordingly latency is reduced.

   6. Fault-Tolerance: In order to avoid the loss of significant data from key sensor nodes, fault- tolerance of CHs is usually required in this kind of applications, thus effective fault-tolerant approaches must be designed in WSNs. Re-clustering is the most intuitive method to recover from a cluster failure, though it usually disarranges the ongoing operation.

   7. Maximizing of the Network Lifetime: Additionally, the aim of energy-aware idea is to select those routes that are expected to prolong the network lifetime in inter-cluster communications, and the routes composed of nodes with higher energy resources should be preferred.

   8. Quality of Service: The network applications and the functionalities of WSNs prompt the requirement of quality of service (QoS). Usually, effective sample, less delay and temporary precision are required.

   9. Load Balancing: Load balancing is an essential consideration aiming at prolonging the network lifetime in WSNs. Even distribution of sensor nodes among the clusters is usually considered for cluster construction where CHs perform the task of data processing and intra-cluster management.

   2.2. Design Goals for Wireless Micro sensor Network Protocols: – In order to design better protocols for wireless micro sensor networks. It is important to understand the parameters that are important for the sensor applications. While there are many ways in which Protocols are beneficial to the application. We use the following metrics.

   • Ease of deployment

   • System lifetime

   • Latency:

   • Quality

     To summarize wireless micro sensor network protocol is should be:-

   • self-configuring to enable ease of deployment of the networks

   • Energy efficient and robust to extend system lifetime

   • Latency aware to get the information to the end user as quickly as possible and

   • Cognizant of the application specific nature of sensor network quality

3. Cluster based routing protocols

   In this paper we will discuss only cluster based or hierarchical protocol, we present a more comprehensive and critical survey of prominent clustering routing protocols for WSNs compared with previous work. After that we analyze 10 classical WSN clustering routing algorithms in detail based on the classification of different algorithm-stages, and highlight their characteristics with advantages and disadvantages.

   1. Cluster-Construction Based Clustering Routing Protocols

      1. LEACH:

         LEACH (Low-Energy Adaptive Clustering Hierarchy), a communication protocol for micro sensor networks [8]. LEACH collects data from distributed micro sensors and transmits it to a base station. LEACH uses the following clustering-model: Some of the nodes elect themselves as cluster-heads. These clusters-heads collect sensor data from other nodes in the vicinity and transfer the aggregated data to the base station. Since data transfers to the base station dissipate much energy, the nodes takes turns with the transmission the cluster-heads rotate. This rotation of cluster-heads lead to a balanced energy consumption of all nodes and hence to a longer lifetime of the network.

         Fig.2 LEACH

         LEACH is a completely distributed approach and requires no global information of the network. In the literature, various modifications have been made to the LEACH protocol, which form LEACH family, such as TL-LEACH [11], E-LEACH [21], M- LEACH [22], LEACH-C [23], V-LEACH [24], etc.

      2. HEED

         Hybrid Energy-Efficient Distributed clustering (HEED) [9], introduced by Younis and Fahmy, is a multi-hop wireless sensor network clustering algorithm which brings an energy-efficient clustering routing with consideration of energy. Different from LEACH in the manner of CH election, HEED does not select nodes as CHs randomly. It considers energy for CH selection the manner of cluster construction is performed based on the hybrid combination of two parameters. One parameter depends on the nodes residual energy, and the other parameter is the intra-cluster communication cost. In HEED, CHs are periodically elected based on two important parameters: residual energy and intra- cluster communication cost of the candidate nodes. Initially, in HEED, a percentage of CHs among all nodes, Cprob, is set to assume that an optimal percentage cannot be computed a priori. The probability that a node becomes a CH is:

         Where Eresidualis the estimated current energy of the node, and Emax is a reference maximum energy, which is typically identical for all nodes in the network.

      3. DWEHC

   Distributed Weight-based Energy-efficient Hierarchical Clustering protocol (DWEHC), proposed by Ding et al. [10], is a distributed clustering algorithm similar to HEED. The main

   objective of DWEHC is to improvement in HEED by building balanced cluster sizes and optimizes the intra-cluster topology using location awareness of the nodes. Each node first locates its neighbors (in its enclosure region), then calculates its weight which is based on its residual energy and distance to its neighbors. The largest weight node in a neighborhood may become a cluster head. Neighboring nodes will then join the cluster head hierarchy. The clustering process terminates in O (1) iterations, and does not depend on network topology or size.

   3.1.5. BCDCP

   Fig.4 TL-LEACH

   Where Eresidual(s) and E Initial(s) are respectively residual and initial energy at nodes, R is the cluster range that corresponds to how far from the CH to a node inside a cluster, and d is the distance between nodes and the neighboring node u.

   Base-Station Controlled Dynamic Clustering Protocol (BCDCP), introduced by Muruganathan et al. [14], is a centralized clustering routing protocol with the BS being capable of complex computation. The concept of BCDCP is the cluster formation where each CH serves an almost equal number of nodes to balance CH overload and uniform CH placement throughout the network.

   Fig.5 BCDCP

   3.1.4. TL-LEACH

   Fig.3 DWEHC

   The figure is the topology of the network, in BCDCP a high-energy BS to set up clusters and uses MST to connect CHs and randomly chooses a leader to send data to the BS.

   Two-level Hierarchy LEACH (TL-LEACH), introduced by Loscrì et al. [11], is an extension to the algorithm of LEACH. TL-LEACH uses random rotation of local cluster base stations (primary cluster-heads and secondary cluster-heads). In this way we build, where it is possible, a two-level hierarchy. This permits to better distribute the energy load among the sensors in the network especially when the density of network is higher. TL-LEACH uses localized coordination to enable scalability and robustness. TL-LEACH introduced two-level hierarchy as shown in Figure 4: top CHs called primary cluster heads (CHi), second level represented from secondary cluster heads (CHij) and ONs

   1. UCS

      Unequal Clustering Size (UCS) model [12] was proposed by Soro and Heinzelman Unequal Clustering Size (UCS) model for network organization, which can lead to more uniform energy dissipation among the cluster head nodes, thus increasing network lifetime. UCS is the first unequal clustering model for WSN organization. It is assumed that the positions of the CHs are determined a priori, with all CHs arranged symmetrically in concentric circles around the BS which is located in the center of the network, thus its easy to control the actual sizes of different clusters.

      has the ability of data detection, wireless communication, data fusion and positioning. Energy load is distributed evenly among the sensor nodes in the network.

   2. EEUC

   Fig.6 UCS

   Fig.7 PEGASIS

   Energy-Efficient Uneven Clustering (EEUC) algorithm, proposed by Li et al. [13]. He proposed Energy- Efficient Unequal Clustering (EEUC) mechanism for periodical data gathering in wireless sensor networks. It partitions the nodes into clusters of unequal size, and clusters closer to the base station have smaller sizes than those farther away from the base station. Thus cluster heads closer to the base station can preserve some energy for the inter-cluster data forwarding. This makes EEUC an unequal clustering approach for the purpose of balancing energy consumption among CHs and solving the hot spot problem. During the process of CH election in EEUC, each node generates a random number, and only the node whose number is greater than a threshold will be activated for CH election by broadcasting compete message within a competition radius which is determined by its distance to the BS. The competition radius of the node has given by:

   Where R comp is the maximum competition radius which is predefined, dmax and dmin denote the maximum and minimum distance between sensor nodes and the BS, d (si, BS) is the distance between node si and the BS, c is a constant coefficient between 0 and 1.

   1. Data-Transmission Based Clustering Routing Protocols

      1. PEGASIS

         Power-Efficient Gathering in Sensor Information Systems (PEGASIS), proposed by Lindsey et al. [15], is an improvement of LEACH. The main idea of PEGASIS is for each node to only communicate with their close neighbors and take turns being the leader in transmission to the sink. In PEGASIS, the locations of nodes are random, and each sensor node

      2. TEEN

         Threshold sensitive Energy Efficient sensor Network protocol (TEEN) [16], proposed by Anjeshwar and Agrawal. TEEN is well suited for time critical applications and is also quite efficient in terms of energy consumption and response time. It also allows the user to control the energy consumption and accuracy to suit the application. The protocol combines the hierarchical technique in line with a data-centric approach. The nodes sense their environment continuously, but the energy consumption in this algorithm can potentially be much less than that in the proactive network, because data transmission is done less frequently.

         Fig.8 TEEN

         In TEEN, a 2-tier clustering topology is built as illustrated in Figure 9 and two thresholds, hard threshold and soft threshold, are defined. The former threshold is a threshold value for the sensed attribute. It is the absolute value of the attribute beyond which, the node sensing this value must switch on its transmitter and report to its CH. The latter threshold is a small change in the value of the sensed attribute which triggers the node to switch on its transmitter and transmit.

      3. APTEEN

         The Adaptive Threshold sensitive Energy Efficient sensor Network protocol (APTEEN) [17], introduced by Manjeshwar and Agrawal, is an extension to TEEN and aims at both transmitting periodic data and reacting to time critical events. APTEEN which allows for comprehensive information retrieval. The nodes in such a network not only react to time-critical situations, but also give an overall picture of the network at periodic intervals in a very energy efficient manner. Such a network enables the user to request past, present and future data from the network in the form of historical, one-time and persistent queries respectively APTEEN, on the other hand, is a hybrid protocol that changes the periodicity or threshold values used in TEEN according to the requirement of users and the type of the application. APTEEN is based on a query system which allows three types of queries: historical, on-time, and persistent which can be used in a hybrid network. Moreover, QoS requirements are introduced for the on-time queries and minimum delay is achieved by a TDMA schedule with a special time slot assignment manner.

      4. CCS

   The Concentric Clustering Scheme (CCS) has been proposed in [18] by Jung et al. To reduce the energy consumption loopholes in PEGASIS the main idea of CCS is to consider the location of the BS to enhance its performance and to prolong the lifetime of the network shown in fig.

   Fig.9 CCS

4. Comparison

   After the study of all clusters based routing protocol we compare to all protocols based on energy efficiency, load balancing and delivery delay parameters and also discuss advantages and disadvantages of each protocol. The comparison [20] among the different types of routing protocols is shown in Table 1.

   Table 1. Comparison of cluster based routing protocols.

   Protocol name	Energy Efficiency	Load balancing	Delivery Delay	Advantages	Disadvantages
   LEACH	Very low	Medium	Very small	Each node equally shares the load and TDMA schedule prevents CHs from unnecessary collisions.	Not applicable for large region, Energy is not considered for Cluster head selection and dynamic clustering brings extra overhead.
   HEED	Medium	Medium	Medium	Fully distributed clustering method, Multi-hop routing, uniform CH selection, more energy conservation and long range communication.	Unbalanced energy consumption, overhead of cluster head selection in each round and CH near to the base die soon because of extra work load.
   DWECH	Very high	Very good	Medium	Fully distributed clustering method, Consider energy for CH selection and clustering process of terminates in a few iterations.	Single-hope communication, not applicable for large region and high control message overhead.
   TL-LEACH	Low	Bad	Small	Better energy load distribution, localized coordination and reduces the total energy consumption.	Not applicable for large regions, energy is not considered for CH selection and bad load balancing.

   UCS	Very low	Bad	Small	More uniform energy consumption among the CHs and two-hop communication method.	It lacks universality, residual energy not consider for CH selection and still not applicable for large region.
   EEUC	High	Medium	Medium	An unequal clustering mechanism to balance the energy consumption among CHs, multi-hop routing mechanism.	Significant overhead, extra global data aggregation and The routing scheme can result in new hot spots.
   BCDCP	Very low	Good	Small	Ensures similar power dissipation of CHs control by BS. Allows sensor nodes to open communication interfaces	Worse scalability and robust to large networks, more design complexity and more energy consumption. Single hop routing and not suitable for reactive network
   PAGASIS	Low	Medium	Very large	It reduces the overhead of dynamic cluster formation, decreases data transmission volume through the chain of data aggregation and The energy load is dispersed uniformly	Unsuitable for networks with a time varying topology, not suitable for large network, large delay and difficult to maintenance database.
   TEEN	Very high	Good	Small	Two thresholds reduces the energy transmission consumption and suitable for reactive scenes and time critical applications.	Not suitable for periodic reports application, the BS may not be able to distinguish dead nodes from alive ones and data may be lost.
   APTEEN	Medium	Medium	Small	Suitable for both proactive and reactive application and flexibility by setting the count-time interval for control the energy consumption.	High overhead complexity for design and implementation of cluster construction in multiple levels.
   CCS	Low	Very bad	Large	Multi-hop routing, a considerable amount of energy is also conserved during data transmission.	Node distribution in each level is unbalanced, Residual energy is not considered for CH election, long chain would cause large delay

5. Conclusion and future scope

   Wireless sensor network has gained increasing attention from the research community over the past few years because the wireless sensor network can be employed in a wide area of applications in both civilian and military scenarios. So design of energy efficient, effective, robust and scalable routing protocol for wireless sensor network is challenging task. In this paper we studied different type cluster based routing protocols and find out the comparison of all protocols on the bases of energy efficiency, load balancing and delay and also explains the merits and demerits of each protocol. We explain all these things in one table so it is very useful for new researchers to find out that which protocol is better for a particular parameter for new research or any application. For future work, simulation of some of these protocols for some quality of service parameters like throughput, cluster scalability, complexity can be considered and compare the cluster based protocol to flat routing protocol.

6. References

[1] D. Niculescu, B Nath . Trajectory Based Forwarding and Its Applications. In Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking (MOBICOM), San Diego, CA, USA, 1419 September 2003; pp. 260272

[2]J.Kulik, W.R. Heinzelman, H.Balakrishnan, Negotiation based protocols for disseminating information in wireless sensor networks. Wirel. Netw. 2002, 8, 169185.

1. B. Karp, H Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM), Boston, MA, USA, 611 August 2000; pp. 243254.

2. C. Intanagonwiwat, R.Govindan, D. Estrin, J. Heidemann, Directed diffusion for wireless sensor networking. IEEE/ACM Trans. Netw. 2003, 11, 216.

3. R.C. Shah, J.M. Rabaey, Energy Aware Routing for Low Energy Ad Hoc Sensor Networks. In Proceedings of the Wireless Communications and Networking Conference (WCNC), Orlando, FL, USA, 2002; pp. 350355.

4. C.Schurgers, M.B Srivastava, Energy Efficient Routing in Wireless Sensor Networks. In Proceedings of Military Communications Conference on Communications for Network-Centric Operations: Creating the Information Force, McLean, VA, USA, 2831 October 2001; pp. 357- 361.

5. K. Sohrabi, J.Gao, V.Ailawadhi, G.J. Pottie, Protocols for self-organization of a wireless sensor network. IEEE Pers. Commun. 2000, 7, 1627.

6. W.R. Heinzelman, A.Chandrakasan, H.Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI, USA, 47 January 2000; pp. 1019.

7. O.Younis, S.Fahmy, HEED: A hybrid, energy- efficient, distributed clustering approach for ad-hoc sensor networks. IEEE Trans. Mobile Comput. 2004, 3, 366379.

8. P. Ding, J.Holliday, A.Celik, Distributed Energy Efficient Hierarchical Clustering for Wireless Sensor Networks. In Proceedings of the 8th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), Marina Del Rey, CA, USA, 810 June 2005; pp. 322339.

9. V. Loscri, G. Morabito, S.A.Marano, Two-Level Hierarchy for Low-Energy Adaptive Clustering Hierarchy. In Proceedings of the 2nd IEEE Semiannual Vehicular Technology Conference, Dallas, TX, USA, 2528 September 2005; pp. 18091813.

10. S.Soro, W.Heinzelman, Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering. In Proceedings of the 5th IEEE International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, CO, USA, 48 April 2005; pp. 236243.

11. C.F. Li, M. Ye, G.H.Chen, J. Wu, An Energy- Efficient Unequal Clustering Mechanism for Wireless Sensor Networks. In Proceedings of the 2nd IEEE International Conference on Mobile Ad-hoc and Sensor Systems Conference (MASS), Washington, DC, 710 November 2005; pp. 596604.

12. S.D. Murugunathan, D.C.F.Ma, R.I. Bhasin, A.O. Fapajuwo, A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks. IEEE Radio Commun. 2005, 43, S8S13.

13. S. Lindsey, C. Raghavendra, K.M. Sivalingam, Data gathering algorithms in sensor networks using energy metrics. IEEE Trans. Parallel Distrib. Syst. 2002, 13, 924 935.

14. E. Manjeshwar, D.P. Agrawal, 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.

15. A. Manjeshwar, D.P. Agrawal, APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks. In Proceedings of the 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile computing, Lauderdale, FL, USA, 1519 April 2002; pp. 195202.

16. S. Jung, Y. Han, T. Chung, The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS. In Proceedings of the 9th International Conference on Advanced Communication Technology, Gangwon-Do, Korea, 1214 February 2007; pp. 260265.

17. S. Naeimi , H. Ghafghazi , C. Chow 1 and H. Ishii, A Survey on the Taxonomy of Cluster-Based Routing Protocols for Homogeneous Wireless Sensor Networks, Sensors 2012.

18. Xuxun Liu, A Survey on Clustering Routing Protocols in Wireless Sensor Networks ,Sensors 2012.

19. X. Fan, Y. Song, Improvement on LEACH Protocol of Wireless Sensor Network. In Proceedings of International Conference on Sensor Technologies and Applications, Valencia, Spain, 1420 October 2007, pp. 260264.

20. Mo Xiaoyan, Study and Design on Cluster Routing Protocols of Wireless Sensor Networks. Ph.D. Dissertation. Zhejiang University, Hangzhou, China, 2006.

21. W.B. Heinzelman, A.P.Chandrakasan, H. Balakrishnan, An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel. Commun. 2002, 1, 660670.

22. .B. Yassein, A. Al-zoubi, Y. Khamayseh, W. Mardini, Improvement on LEACH protocol of wireless sensor network (VLEACH). Int. J. Digit. Content Technol. Appl. 2009, 3, 132-136.