A Review of Hierarchical Networks Routing Protocols In Wireless Sensor Networks

A Review of Hierarchical Networks Routing Protocols In Wireless Sensor Networks

Sonali B. Patel1, Prof. Rohit Srivastava2

1 Parul Institute of Engineering and Technology, Vadodara, Gujarat, India

2 Department of Computer Science, Parul Institute of Engineering and Technology,

Vadodara, Gujarat, India

Abstract

Wireless Sensor Networks (WSNs) is a collection of sensor nodes with capability of sensing various types of environmental and physical conditions, data processing and provide wireless communication . The most important feature of routing protocol, in order to be efficient for WSNs, is the energy consumption and extension of the networks lifetime. Wireless network are highly dependent on specific application and have a limited transmission range, and their processing and storage capabilities as well as their energy resources are also limited. In this paper, we give a survey and analyze different hierarchical based routing protocols for wireless sensor networks and compare them based on various characteristics.

Keywords

Wireless Sensor Networks, Hierarchical protocols, Clusters.

1. Introduction

   Due to a large number of applications such as security, agriculture, automation and monitoring, WSN has been identified as one of the pioneer technique in 21st century. A WSNs is a collection of wireless nodes with

   limited energy capabilities that may be mobile or stationary and are located randomly on dynamic changing environment. These sensor nodes communicate over short distance via a wireless medium and collaborate to accomplish a common task. WSNs can be deployed on a global scale for environmental monitoring and habitat study, over a battlefield for military surveillance and reconnaissance, in emergent environments for search and rescue, in factories for condition based maintenance and process control, in buildings for infrastructure health monitoring, in homes to realize smart homes, or even in bodies for patient monitoring. The routing strategies selection is an important issue for the efficient delivery of the packets to their destination.

   Typically, WSNs [1] contain hundreds or thousands of these sensor nodes, and these sensors have the ability to communicate either among each other or directly to an external base station (BS). Figure 1 shows a schematic diagram of wireless sensor node. Basically each sensor node consists of Sensor module, Processing Module and Wireless Communication module. Sensor nodes are usually scattered in a sensor field,

   Figure 1. Architecture of a WSN node.

   which is an area where the sensor nodes are deployed. Sensor nodes coordinate among themselves to produce high-quality data information about the physical environment. Each node takes decision according to its knowledge of its computing, communication, energy resources and information. Each of these scattered sensor nodes has the capability to collect and route data either to other sensors or back to an external BSs. A BS may be a fixed or mobile node capable of connecting the sensor network to an existing communications infrastructure or to the Internet where a user can have access to the reported data. In a typical scenario, users can retrieve information of interest from a WSN by injecting queries and gathering results from the so-called base stations (or sink nodes), which behave as an interface between users and the network. In this way, WSNs can be considered as a distributed database.

   The sensor nodes are densely deployed either inside the sink or very close to it and have limited power, computational capacity and memory. Sensor nodes are very prone to failures. Sensor nodes may not have global identification (ID) because of the large amount of overhead. Sensor nodes are densely deployed in large numbers.

   There are many challenges in routing protocol for WSNs, which distinguish these networks from other wireless networks like MANET or cellular network. Due to large number of sensor nodes, it is not possible to build a global addressing scheme for the deployment of a large number of sensor nodes as the overhead of ID maintenance is high. Thus, traditional IP-based protocols may not be applied to WSNs. Further, sensor nodes are tightly constrained in terms of energy, processing, and storage capacities. Thus, they require careful resource management. Almost all applications of sensor networks require the flow of sensed data from multiple sources to a particular BS. This, however, does not prevent the flow of data to be in other forms (e.g., multicast or peer to peer). Sensor networks are application-specific, that is design requirements of a sensor network change with application. Sensor nodes in WSNs are generally stationary after deployment except for maybe a few mobile nodes. Position awareness of sensor nodes is important since data collection is normally based on the location. Currently, it is not feasible to use Global Positioning System (GPS) hardware for this purpose. Data collected by many sensors in WSNs is typically based on common phenomena, so there is a high probability that this data has some redundancy. Such redundancy needs to be exploited by the routing protocols to improve energy and bandwidth utilization.

   A large number of research activities have been carried out to explore and overcome the constraints of WSNs and solve design and application issues. In this paper various hierarchical routing protocols for wireless sensor network are discussed and compared. Section 2 of the paper discusses the network characteristics and design objectives. In Sections 3, Network Design Challenges and Routing Issues are described. In section 4,

   different Hierarchical Routing Protocols in Wireless Sensor Networks is described. Finally, Section 4 concludes the survey.

2. Network Characteristics and Design Objectives

   The characteristics of sensor networks and application requirements have a decisive impact on the network design objectives in term of network capabilities and network performance [2].

   1. Network Characteristics

      Wireless sensor networks have the following unique characteristics and constraints as compared to the traditional wireless communication networks such as MANET and cellular systems

      Dense sensor node deployment: Sensor nodes are usually densely deployed and can be several orders of magnitude higher than that in a MANET.

      Battery-powered sensor nodes: Sensor nodes are usually powered by battery and are deployed in a harsh environment where it is very difficult to change or recharge the batteries.

      Severe energy, computation, and storage constraints: Sensors nodes are having highly limited energy, computation, and storage capabilities.

      Self-configurable: Sensor nodes are usually randomly deployed and autonomously configure themselves into a communication network.

      Unreliable sensor nodes: Since sensor nodes are prone to physical damages or failures due to its deployment in harsh or hostile environment.

      Data redundancy: In most sensor network application, sensor nodes are densely deployed in a region of interest and

      collaborate to accomplish a common sensing task. Thus, the data sensed by multiple sensor nodes typically have a certain level of correlation or redundancy.

      Application specific: A sensor network is usually designed and deployed for a specific application. The design requirements of a sensor network change with its application. Many-to-one traffic pattern: In most sensor network applications, the data sensed by sensor nodes flow from multiple source sensor nodes to a paricular sink, exhibiting a many-to-one traffic pattern.

      Frequent topology change: Network topology changes frequently due to the node failures, damage, addition, energy depletion, or channel fading.

   2. Network Design Objectives

      Most sensor networks are application specific and have different application requirements. Thus, all or part of the following main design objectives is considered in the design of sensor networks:

      Small node size: Since sensor nodes are usually deployed in a harsh or hostile environment in large numbers, reducing node size can facilitate node deployment. It will also reduce the power consumption and cost of sensor nodes.

      Low node cost: Since sensor nodes are usually deployed in a harsh or hostile environment in large numbers and cannot be reused, reducing cost of sensor nodes is important and will result into the cost reduction of whole network.

      Low power consumption: Since sensor nodes are powered by battery and it is often very difficult or even impossible to charge or recharge their batteries, it is crucial to reduce the power consumption of sensor nodes so that the lifetime of the sensor nodes, as well as the whole network is prolonged.

      Scalability: Since the number sensor nodes in sensor networks are in the order of tens, hundreds, or thousands, network protocols designed for sensor networks should be scalable to different network sizes.

      Reliability: Network protocols designed for sensor networks must provide error control and correction mechanisms to ensure reliable data delivery over noisy, error- prone, and time-varying wireless channels. Self-configurability: In sensor networks, once deployed, sensor nodes should be able to autonomously organize themselves into a communication network and reconfigure their connectivity in the event of topology changes and node failures.

      Adaptability: In sensor networks, a node may fail, join, or move, which would result in changes in node density and network topology. Thus, network protocols designed for sensor networks should be adaptive to such density and topology changes.

      Channel utilization: Since sensor networks have limited bandwidth resources, communication protocols designed for sensor networks should efficiently make use of the bandwidth to improve channel utilization.

      Fault tolerance: Sensor nodes are prone to failures due to harsh deployment environments and unattended operations. Thus, sensor nodes should be fault tolerant and have the abilities of self- testing, self- calibrating, self-repairing, and self- recovering.

      Security: A sensor network should introduce effective security mechanisms to prevent the data information in the network or a sensor node from unauthorized access or malicious attacks.

      QoS support: In sensor networks, different applications may have different quality-of- service (QoS) requirements in terms of delivery latency and packet loss. Thus, network protocol design should consider the QoS requirements of specific applications.

3. Network Design Challenges and Routing Issues

   The design of routing protocols for WSNs is challenging because of several network constraints. WSNs suffer from the limitations of several network resources, for example, energy, bandwidth, central processing unit, and storage. The design challenges in sensor networks involve the following main aspects [3,4,5]:

   Limited energy capacity: Since sensor nodes are battery powered, they have limited energy capacity. Energy poses a big challenge for network designers in hostile environments, for example, a battlefield, where it is impossible to access the sensors and recharge their batteries. Furthermore, when the energy of a sensor reaches a certain threshold, the sensor will become faulty and will not be able to function properly, which will have a major impact on the network performance. Thus, routing protocols designed for sensors should be as energy efficient as possible to extend their lifetime, and hence prolong the network lifetime while guaranteeing good performance overall.

   Sensor locations: Another challenge that faces the design of routing protocols is to manage the locations of the sensors. Most of the proposed protocols assume that the sensors either are equipped with global positioning system (GPS) receivers or use some localization technique to learn about their locations.

   Limited hardware resources: In addition to limited energy capacity, sensor nodes have also limited processing and storage capacities, and thus can only perform limited computational functionalities. These hardware constraints present many challenges in software development and network protocol design for sensor networks, which must consider not only the energy constraint in sensor nodes, but also

   the processing and storage capacities of sensor nodes.

   Massive and random node deployment: Sensor node deployment in WSNs is application dependent and can be either manual or random which finally affects the performance of the routing protocol. In most applications, sensor nodes can be scattered randomly in an intended area or dropped massively over an inaccessible or hostile region. If the resultant distribution of nodes is not uniform, optimal clustering becomes necessary to allow connectivity and enable energy efficient network operation.

   Network characteristics and unreliable environment: A sensor network usually operates in a dynamic and unreliable environment. The topology of a network, which is defined by the sensors and the communication links between the sensors, changes frequently due to sensor addition, deletion, node failures, damages, or energy depletion. Also, the sensor nodes are linked by a wireless medium, which is noisy, error prone, and time varying. Therefore, routing paths should consider network topology dynamics due to limited energy and sensor mobility as well as increasing the size of the network to maintain specific application requirements in terms of coverage and connectivity.

   Data Aggregation: Since sensor nodes may generate significant redundant data, similar packets from multiple nodes can be aggregated so that the number of transmissions is reduced. Data aggregation technique has been used to achieve energy efficiency and data transfer optimization in a number of routing protocols.

   Diverse sensing application requirements: Sensor networks have a wide range of diverse applications. No network protocol can meet the requirements of all applications. Therefore, the routing protocols should guarantee data delivery

   and its accuracy so that the sink can gather the required knowledge about the physical phenomenon on time.

   Scalability: Routing protocols should be able to scale with the network size. Also, sensors may not necessarily have the same capabilities in terms of energy, processing, sensing, and particularly communication. Hence, communication links between sensors may not be symmetric, that is, a pair of sensors may not be able to have communication in both directions. This should be taken care of in the routing protocols.

4. Hierarchical Routing Protocols in Wireless Sensor Network

   Hierarchical routing protocols is an energy efficient communication protocol that can be used by the sensors to report their sensed data to the sink. Hierarchical routing is to efficiently maintain the energy consumption of network.

   Figure 2. Architecture of Hierarchical Routing Protocol

   In this, a network is divided into small region called cluster. A cluster consists of many sensor nodes, among which one sensor node is elected as special node called cluster head, which manage the activities of cluster. The sensor node senses the data and transfers the data to its cluster head in which it is present. The cluster head collect

   the data from all sensor nodes and directly or indirectly transfer the data to base station BS. Figure 2 show the architecture of hierarchical routing protocol. The cluster heads are used for higher level communication, reducing the traffic overhead. Clustering may be extended to more than just two levels having the same concepts of communication in every level. The use of routing hierarchy has a lot of advantages. It reduces the size of routing tables providing better scalability.

   1. Low energy adaptive clustering hierarchy (LEACH)

      Leach is one of the first hierarchical routing algorithms using cluster-based approach. It is most energy-efficient algorithm for WSNs that was proposed in order to reduce energy consumption [6,7].

      The operation of LEACH has two phases

      1. Set-up Phase: In this phase, sensor nodes are organized into clusters and one sensor node is selected as cluster head (CH) from each cluster. The cluster head perform task of data aggregation and compression and forward those data to the base station. Each sensor node gets chance to become cluster head by using stochastic algorithm at each round. If a node become cluster head for one time, it cannot become cluster head again for n round where n is percentage of cluster heads. This rotation of cluster heads will balance the energy consumption of all nodes and increase lifetime of network. Once the cluster head is chosen, it will use CSMA MAC protocol to advertise its status. Remaining nodes will take the decision about their cluster head for current round based on the received signal strength of the advertisement message. Before steady-state phase starts, certain parameters are considered, such as the network topology and the relative costs of computation versus

         the communication. A Time Division Multiple Access (TDMA) schedule is applied to all the members of the cluster group to send messages to the CH, and then to the cluster head towards the base station. As soon as a cluster head is selected for a region, steady-state phase starts.

      2. Steady state Phase: In this phase, the data is transfer to base station. Each node, other than cluster head, select closest cluster head and join that cluster. The cluster head (CH) then creates a schedule for each node in its cluster to transmit its data. Assuming nodes always have data to send, they send it during their allocated transmission time to the cluster head (CH). This transmission uses a minimal amount of energy (chosen based on the received strength of the cluster-head advertisement). The radio of each non-cluster-head node can be turned off until the nodes allocated transmission time, thus minimizing energy dissipation in these nodes. The cluster-head node must keep its receiver on to receive all the data from the nodes in the cluster. When all the data has been received, the cluster head node performs signal processing functions to generate the composite single signal. In order to minimize overhead, the steady-state phase is long compared to the set-up phase.

      The main advantage of LEACH is Low energy, ad-hoc, distributed protocol. The disadvantage is that it is not applicable to networks deployed in large regions and dynamic clustering brings extra overhead.

      Improvement in LEACH protocol E-LEACH Protocol

      Energy-LEACH protocol is an improvement of LEACH protocol. The main idea behind this is to improve the cluster head CH selection procedure [8]. Main metric use by E-LEACH is residual

      energy of node that decide whether the nodes become cluster head CH or not in each round, after first round. Like LEACH protocol, in the first round, every node has same probability to become cluster head that is randomly selected as cluster head CH, after first round, each node has different residual energy. In next round, cluster head CH is selected as per residual energy of the nodes. The node having maximum energy is selected as cluster head.

      TL-LEACH Protocol

      Another improvement in LEACH protocol lead to Two-Level Leach protocol [9]. In LEACH protocol, the cluster head CH collects data from sensors node that are present in its own cluster and passes directly to the BS. As distance between BS and CH is larger so it loss energy in transmitting data and it will die faster than other nodes. In TL-LEACH protocol, one more CH is use as relay station which lies between CH and BS, Thus, CH collect data from sensor nodes and transfer to this CH, a relay station, after that it transfer to BS directly.

      M-LEACH protocol

      In Multihop-LECH protocol [10], as name suggest it will transmit data hop-by-hop. That is, it find optimal path by selecting other CH as relay station between CH and BS. The data is transfer hop-by-hop among CHs only. The CH, which is nearest to BS, collects data from other CH and sends to BS. M-LEACH is similar to LEACH protocol; difference is from single hop to multiple hop between CHs and BS.

      LEACH-C protocol

      LEACH-C protocol works with centralize clustering algorithm [11]. It improves performance by dispersing cluster heads

      through out the network. Each node during set-up phase, each node in cluster send its current location and residual energy level to sink. In order to distribute energy evenly to all nodes, sink compute average node energy and list out which node have energy less than average. After the cluster heads and associate clusters are found, the sink broadcast message that obtain cluster head ID for each node. The node become cluster head if the cluster head ID matches to its own ID. If it doesnt match then node determine its TDMA slot for data transmission and goes for sleep until its time to transmit data. LEACH-C has same steady state as of LEACH.

      V-LEACH protocol

      In VLEACH, there is a node called Vice- CH, which become cluster head CH of cluster in case if the present CH dies. In LEACH protocol, when the CH dies, the cluster becomes useless because the data gathered by cluster nodes will never reach the base station. In V-LEACH protocol [12], the vice-CH takes the role of CH when CH in cluster dies. Due to this transfer of duty, the data will always reach to BS. No need of electing a new CH each time the CH dies and this will extend overall network lifetime.

      LEACH-F protocol

      In LEACH with Fixed Cluster [13], clusters that are formed once then they are fixed. It enhanced the LEACH protocol. The CH position rotates among the nodes within the cluster. The advantage with this is that, once the cluster is formed, there is no set-up overhead at the beginning of each round. To decide clusters, LEACH-F uses the same centralized cluster formation algorithm as LEACH-C. The fixed clusters in LEACH-F do not allow new nodes to be added to the

      system and do not adjust their behavior based on nodes dying.

   2. Power-Efficient Gathering in Sensor Information System protocol (PEGASIS)

      PEGASIS protocol [14] is extension and enhancement over LEACH protocol, in which nodes are organized to form chain, so they can communicate only with their nearest neighbors. Unlike LEACH, PEGASIS avoid cluster formation and only node is selected from chain to transmit to base station (sink) instead of using multiple nodes. This reduces the power required to transmit data per round. The chain construction is performed in greedy way. A sensor transmits to its local neighbors in the data fusion phase instead of sending directly to its CH as in the case of LEACH. In PEGASIS routing protocol, the construction phase assumes that all the sensors have global knowledge about the network. Specifically, it starts with the furthest sensor to sink to guarantee that sensors farther away from the sink have close neighbors. When a sensor fails or dies due to low battery power, the chain is constructed using the same greedy approach by bypassing the failed sensor. In each round, a randomly chosen sensor node from the chain will transmit the aggregated data to the BS, thus reducing the per round energy expenditure compared to LEACH, even PEGASIS increase the lifetime of network twice as much the lifetime of the network under LEACH. Such the lifetime of the network under the LEACH protocol. Such performance gain is achieve through the elimination of the overhead caused by dynamic cluster formation in LEACH and through decreasing the number of transmissions and reception by using data aggregation. It provide redundant data transmission since one node as been selected. Unlike LEACH transmission

      distance for most of the nodes is reduced in PEGASIS. The main drawback is there is no consideration of base stations location about the energy of nodes when one of the nodes is selected as the head node. PEGASIS assumes that each sensor node can be able to communicate with the BS directly. Also, PEGASIS assumes that all nodes maintain a complete database about the location of all other nodes in the network. In addition, PEGASIS assumes that all sensor nodes have the same level of energy and they are likely to die at the same time. PEGASIS introduces excessive delay for distant node on the chain. In addition, the single leader can become a bottleneck. Finally, although in most scenarios, sensors will be fixed or immobile as assumed in PEGASIS, some sensors may be allowed to move and hence affect the protocol functionality.

      Improvement in PEGASIS Hierarchical PEGASIS

      Hierarchical-PEGASIS [15] is an extension of PEGASIS, with the target of decreasing delay in transmitting the packets to BS. In PEGASIS, simultaneous transmissions of data messages are pursued, In order to reduce the delay. H-PEGASIS proposes a solution to the data gathering problem by considering energy × delay metric. To avoid collisions and possible signal interference among the sensors, two approaches have been investigated. The first approach incorporates signal coding, e.g. CDMA. In the second approach only spatially separated nodes are allowed to transmit at the same time. The chain-based protocol with CDMA capable nodes, constructs a chain of nodes, that forms a tree like hierarchy, and each selected node in a particular level transmits data to the node in the upper level of the hierarchy. This

      method ensures data transmitting in parallel and reduces the delay significantly. Hierarchical PEGASIS perform better than PEGASIS by a factor of 60.

      EB-PEGASIS

      In EB- PEGASIS [16], a node will consider average distance of formed chain. It is an energy efficient chaining algorithm. The closest node is a "far node", if the distance from closest node to its upstream node is longer than distance thresh (the distance thresh can obtain from average distance of formed chain). If the closest node joins the chain, it will emerge a "long chain". Through this method, the new protocol EB- PEGASIS can avoid "long chain" effectively. It avoids dying of some nodes early than other nodes to prolong lifetime of sensor networks. It saves and balance energy consumption of all sensor nodes.

   3. Threshold sensitive Energy Efficient sensor Network protocol (TEEN)

      The TEEN is a hierarchical protocol designed for the conditions like sudden changes in the sensed attributes such as temperature [17]. The responsiveness is important for time-critical applications, in which the network is operated in a reactive mode. The sensor network architecture in TEEN is based on a hierarchical grouping where closer nodes form clusters and this process goes on the second level until the sink is reached.

      In this scheme the cluster-head broadcasts to its members the Hard Threshold (HT) and the Soft Threshold (ST). The HT 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 cluster head. The ST is a small change in the value of the sensed attribute, which

      triggers the node to switch on its transmitter and transmit. The nodes sense their environment continuously. The first time a parameter from the attribute set reaches its hard threshold value, the node switches on its transmitter and sends the sensed data. The sensed value is stored in an internal variable in the node, called the sensed value (SV).

      The main advantage of TEEN is that it works well in the conditions like sudden changes in the sensed attributes such as temperature. On the other hand, in large area networks and when the number of layers in the hierarchy is small, TEEN tends to consume a lot of energy, because of long distance transmissions. Moreover, when the number of layers increases, the transmissions become shorter and overhead in the setup phase as well as the operation of the network exist.

   4. Adaptive Threshold sensitive Energy Efficient sensor Network (APTEEN)

      The APTEEN is an improvement of TEEN and aims at both capturing periodic data collections and reacting to time-critical events [18]. As soon as the base station forms the clusters, the cluster heads broadcast the attributes, the threshold values and the transmission schedule to all nodes. After that the cluster heads perform data aggregation, which has as a result to save energy.

      The main advantage of APTEEN, compared to TEEN, is that nodes consume lees energy. However, the main drawbacks of APTEEN are the complexity and that it results in longer delay times.

   5. Virtual Grid Architecture Routing (VGA)

      The VGA combines data aggregation and in-network processing to achieve energy efficiency and maximization of network

      life- time [19]. The overall scheme can be divided into two phases, clustering and routing of aggregated data. In the clustering phase, sensors are arranged in a fixed topology, as most of the applications require stationary sensors. Inside each cluster a cluster-head, known as local aggregator, performs aggregation. A subset of this Local Aggregators (LA) is selected to perform global or in-cluster aggregation and its members are known as master aggregator (MA). In the data aggregation phase, some heuristic are proposed which may give simple, efficient and near optimal solution. An example of a heuristic is that LA nodes form groups, which may be overlapping. Thus, the reading of members in a group can be correlated.

      The main advantage of this protocol is that it may achieve energy efficiency and maximization of network lifetime, but the problem of optimal selection of local aggregators as master aggregators is NP- hard problem.

   6. Two-Tier Data Dissemination (TTDD)

      The Two-Tier Data Dissemination (TTDD), provides data delivery to multiple mobile BS. It assumes that the sensor nodes are stationary and location aware and sinks are allowed to change their location dynamically [20]. At the time that an event is sensed by nearby sensors, one of them becomes the source that will generate data reports. After that the virtual grid structure is built, initiated by source node and chooses itself as a start crossing point of a grid. It sends a data announcement message to its four different adjacent crossing points using greedy geographical forwarding. The message only stops once it reaches to a node that is closest to the crossing point. This process continues until the message reaches boundary of the network. The nodes that store the source information are chosen

      as dissemination points. After this process, the grid structure is obtained. Using the grid, a BS can flood a query, which will be forwarded to the nearest dissemination point in the local cell to receive data. Then the query is forwarded along other dissemination points upstream to the source. The requested data then flows down in the reverse path to the sink.

      The TTDD can be used for multiple mobile sinks in a field of stationary sensor nodes. The main drawback is that each source node builds a virtual grid structure of dissemination points to supply data to mobile sinks.

   7. Base-Station Controlled Dynamic Clustering Protocol (BCDCP)

      The BCDCP sets up clusters based on the main idea that they will be balanced [21]. In order to achieve this, the base station, before constructing the routing path, receives information on the current energy status from all the nodes in the netwok. Based on this feedback, the base station first computes the average energy level of all the nodes. Then the base station chooses a set of nodes whose energy levels are above the average value.

      In addition to the above, at each cluster, the head clusters are serve an approximately equal number of member nodes between each others in order to achieve the following:

      • Avoid cluster head overload,

      • Uniform placement of cluster heads throughout the whole sensor field and

      • Utilize a clusterhead-to-clusterhead (CH- to-CH) routing to transfer the data to the base station.

        Also, in the BCDCP the base station is considered to be a high-energy node with a large amount of energy supply.

   8. Multi-hop Virtual Multiple Input Multiple Output (MIMO)

      In the Multi-hop Virtual MIMO the data are collected by multiple source nodes and transmitted to a remote sink by multiple hops [22]. The sensor nodes are organized into clusters. The cluster head broadcasts the data to the cluster nodes that belong to the specific cluster. An Additive White Gaussian Noise channel (a channel model in which the only impairment to communication is a linear addition of wideband or white noise with a constant spectral density expressed as watts per hertz of bandwidth and a Gaussian distribution of amplitude) with a squared power path loss is assumed in such a transmission due to the short intra-cluster transmission range. Next, the cluster nodes encode and trans- mit the data to the cluster head in the next hop according to the orthogonal Space-Time Block Code (STBC).

      In order to improve the energy saving performance, the Multi-hop Virtual MIMO presents that the average attenuation of the channel between each cluster node and cluster head can be estimated during the formation of the clusters, so it uses an equal Signal to Noise Ratio (SNR) policy to allocate the transmit power due to its spectral efficiency and simplicity.

   9. Hierarchical Power Aware Routing (HPAR)

      The HPAR is a power aware routing protocol that divides the network into a group of sensors called zones [23]. Each zone is a group of geographically close sensor nodes and is treated as an entity. Thus the first step of this protocol is to format the clustered zones. The next step is the function of routing scheme to decide how a message is routed across other zones hierarchically so that battery life of nodes in

      the system is maximized. This can be done by a message that is routed along a path with a maximum power over all minimum remaining powers. This path is called max- min path. The main idea of making such a decision is that it may be possible that a path with high residual power has more energy consumption than the minimum energy consumption path. This scheme presents an approximation algorithm called max-min ZPmin algorithm. The algorithm first finds a path with least power consumption by applying Dijkstra algorithm. It then finds a second path that maximizes the minimal residual power in the network. The protocol then tries to optimize both solution criteria.

      The main advantage of this protocol is that it takes into consideration both the transmission power and the minimum battery power of the node in the path. In addition, it makes use of zones to take care of the large number of sensor nodes. On the other hand, the discovery of the power estimation may consult on the overhead to the network.

   10. Sleep/Wake Scheduling Protocol

       The sleep/wake scheduling protocol conserves energy as it puts the radio to sleep during idle times and wake it up right before message transmission/reception [24]. The important part for a sleep/wake protocol is the synchronization between the sender and the receiver, so that they can wake up simultaneously to communicate with each other. The existing synchronization schemes achieve precise synchronization immediately after the exchange of synchronization messages, although there is still random synchronization error because of the non- deterministic factors in the system. These errors have as consequence the clock

       disagreement to grow with time and be comparable to the actual message transmission time. Thus, in an optimal sleep/wake scheduling algorithm is proposed. It achieves a message capture probability threshold with minimum energy consumption. Moreover, multi-hop communication is considered.

       The sleep/wake scheduling protocol is organized into cluster hierarchy and each cluster consists of a single cluster head and multiple cluster members. The most important issue, in this protocol, is that a cluster member can also be a cluster head in one cluster. C is the cluster head of E, but it is also a member of A. The member nodes are synchronized in the synchronization interval and in the transmission interval each member node transmits in a TDMA manner and sends one message to the cluster heads every T seconds.

   11. Grid Based Data Dissemination (GBDD)

       In GBDD the size of the cell is determined by dual radio range of a sensor node [25]. Unlike TTDD, where the source initiates grid construction, in GBDD the sink that first was interested in sending or receiving data starts the grid construction process. This node is set as the crossing point (CP) of the grid and its geographical coordinates (x,y) become the starting point for the formation of grid cells. The RH and RL are the transmission ranges of every sensor node while working in high power radio mode and low power radio mode respectively. The cell of the grid is a square and each side is of size a.

   12. Extending Lifetime of Cluster Head (ELCH)

       In ELCH the sensors vote for their

       neighbors in order to elect suitable cluster heads [26]. This protocol achieves to consume low energy and thus extending the life of the network utilizing a hybrid protocol, which combines the cluster architecture, with multi-hop routing.

       This protocol presents two phases:

       • Setup Phase. In this phase, the cluster formation and the cluster-head selection are performed. The nodes vote their neighbor sensors. The most voted sensor becomes the cluster-head.

       • Steady-State Phase: In this phase, the creation of clusters, the forwarding to the head and forwarding to the sink are performed. The clusters are formed in a way that they consist of one cluster-head and some sensors. These sensors have been chosen based on their location. This means that the sensors located in a radius less than the radio radius are selected. Then, the time slot TDMA for each cluster member in each round is used. In addition, each cluster-head maintains a table with maximum power for each node at each selection round. As soon as the above are completed the data transmission can start.

         As soon as the clusters have been organized, the cluster heads can form a multi-hop routing backbone. The data are forwarded directly to the cluster head by each node. Moreover, for the communication between the cluster heads and the sink, a multi-hop routing is adopted. This technique can minimize the transmission energy and the network can be more balanced in terms of energy efficiency.

   13. Novel Hierarchical Routing Protocol Algorithm (NHRPA)

       The NHRPA algorithm can adopt the suitable routing technology for the nodes

       that is relative to the distance of nodes to the base station, the density of nodes distribution and the residual energy of nodes [27]. A glance at the computation cost indicates that the proposed routing algorithm in dealing nodes mainly requires loop operations, judgment operations, and assignment operations. Moreover, the initialization process of the node is performed once during the period of deploying sensor networks. By selecting suitable threshold value, he NHRPA can balance varying concerns among different demand situations, such as security and energy concerns.

   14. Scaling Hierarchical Power Efficient Routing (SH-PER)

       The SHPER protocol supposes the coexistence of a base station and a set of homogeneous sensor nodes [28]. These nodes are randomly distributed within a delimited area of interest. The base station is located a long distance away from the sensor field. Both the base station and the set of the sensor nodes are supposed to be stationary. Also the base station is able to transmit with high enough power to all the network nodes, due to its unlimited power supply.

       The operation of SHPER protocol consists of two phases: initialization and steady state phase. In the first phase the base station broadcasts a TDMA schedule and requests the nodes to advertise themselves. The nodes transmit their advertisements and the relative distances among them are identified. After that the base station randomly elects a predefined number of high and low level cluster heads and broadcasts the IDs of the new cluster heads and the values of the thresholds. In the steady state phase the cluster head defines the mostly energy efficient path to route its messages to the base station.

       The main advantage of this protocol is that it performs the cluster leadership by taking into account the residual energy of nodes and energy balance is achieved and the power depletion among the nodes is performed in a more even way. Moreover, the data routing is based on a route selection policy, which takes into consideration both the energy reserves of the nodes and the communication cost associated with the potential paths. However, it does not support the mobility of the nodes.

   15. Distributed hierarchical agglomerative clustering (DHAC)

       The main idea in the DHAC is that a node needs the knowledge of only one hop neighbor to build the clusters [29]. The steps in the DHAC to form clusters are the following:

       • Obtain input data set and build resemblance matrix. In this step each node elects itself as a cluster head and exchanges the information via HELLO messages to its neighbors.

       • Execute the DHAC algorithm. In this phase each cluster establishes its own local resemblance matrix and the minimum coefficient can be easily found. In addition, each cluster then determines its minimum cluster head.

       • Cut the hierarchical cluster tree. In case that a predefined upper bound size of clusters is reached, the control conditions correspond to the step of cutting the hierarchical cluster tree.

       • Control the minimum cluster size. The next is to generate the clusters by running DHAC, the minimum cluster size can also be used to limit the lower bound of cluster size by performing the procedure MERGE CLUSTERS.

       • Choose CHs: To choose the CHs, the DHAC choose the lower id node between

       the two nodes that join the cluster at the first step. The CH chosen does not require extra processing.

       Following, the DHAC uses the sequence of nodes merging into the current cluster as the schedule. Each cluster member gets its assigned role and starts to send data to CH in turns.

   16. Small minimum energy communication network (MECN)

       MECH [30] is energy efficient routing protocol in which the transmission of data is in relay region. The relay region consists of nodes which provide energy efficient routing. That is, routing consist of fewer nodes and less power consumption in transferring data. This is performed using a localized search for each node considering its relay region. MECN is self-reconfiguring and thus can dynamically adapt to node failure or the deployment of new sensors. The small MECN (SMECN) [24] is an extension to MECN. The network build by SMECN is smaller and with minimum energy than the network constructed by MECN. The sub-network computed by SMECN helps in sending messages on mini- mum-energy paths. This algorithm introduce overhead in network.

   17. Self-organizing protocol:

       Self-organizing protocol [31] supports heterogeneous sensors, which can be mobile or stationary. This sensor forwards the data to a set of stationary nodes that are called routers. The routers collect the data and forwarded to BS nodes. In this, Local Markov Loops (LML) algorithm is used to support fault tolerance and means of broadcasting. The idea is similar to that of virtual grid. In this approach, sensor nodes can be addressed individually in the routing architecture; hence, it is suitable for

       applications where communication to a particular node is required. This algorithm incurs a small cost for maintaining routing tables and keeping a balanced routing hierarchy. It also introduce extra overhead. Another issue is related to the formation of a hierarchy. It could happen that there are many cuts in the network, and hence the probability of applying reorganization phase increases, which is an expensive operation. The energy consumed for broadcasting a message is less than that consumed in the SPIN protocol.

   18. Sensor aggregates routing:

   This protocol [32] includes a set of algorithms for constructing and maintaining sensor aggregates. A sensor aggregate consists of those nodes in network, which satisfies a grouping system for a collaborative processing task. This depends on the task and its resource requirements. Sensors in the network are divided into clusters based on their sensed signal strength, after that local cluster leaders are elected. In order to elect a leader, information is exchange between neighboring sensors. The sensor having higher sensed signal strength is declared as leader. This leader-based tracking algorithm assumes that the unique leader knows the geographical region of the collaboration.

   Three algorithms were proposed:

   1. Distributed Aggregate Management (DAM), is lightweight protocol, for forming sensor aggregates for target monitoring task. In this, each node decides if it should participate in aggregate and message exchange scheme M. A node determines if it belongs to an aggregate based on the result of applying the predicate to the data of the node as well as information from other nodes. Aggregates are formed when the process eventually

      Table 1. Comparisons of Hierarchical Routing Protocol

      Routing Protocols	Scalability	Mobility	Route Metric	Power usage	Overhead	Data Aggregation
      LEACH	Good	Fixed BS	Shortest Path	Low	Yes	Yes
      PEGASIS	Good	Fixed BS	Greedy Route Selection	Max	No	No
      TEEN	Good	Fixed BS	Best Route	Low	Yes	Yes
      APTEEN	Good	Fixed BS	Best Route	Max	Yes	Yes
      VGA	Good	NO	Greedy Route Selection	N/A	No	Yes
      TTDD	Low	NO	Greedy Route Selection	Limited	No	No
      BCDCP	Limited	NO	Best Route	Low	No	Yes
      MIMO	Good	NO	Greedy Route Selection	Low		Yes
      HPAR	Low	NO	Greedy Route Selection	Low	Yes	No
      Sleep/Wake	Good	NO	Best Route	Low	No	Yes
      GBDD	Good	Limited	Sink find out closest cornr node	Max	No	No
      ELCH	Limited	Fixed BS	Select node with maximum power	Low	Yes	Yes
      NHRPA	Good	Fixed BS	Best Route	Low	Yes	Yes
      SHPER	Good	Fixed BS	Best Route	Low	Yes	Yes
      DHAC	Good	NO	Best Route	Low	Yes	Yes
      MECH & SMECN	Low	NO	Minimum nodes with less energy consumption	Low	Yes	No
      SOP	Low	NO	It provide balanced routing hierarchical	N/A	Yes	No
      Sensor aggregate	Good	Limited	Route based on target tracking application	N/A	Yes	Yes

      converges.

   2. Energy-Based Activity Monitoring (EBAM) calculate the energy level of each node by combining a weighted form of the detected target energy at each impacted sensor, computing the signal impact area, assuming that each target sensor has equal or constant energy level.

   3. Expectation-Maximization Like Activity Monitoring (EMLAM) eliminates the constant and equal target energy level assumption. It estimates the target positions and signal energy using received signals, and uses the resulting estimates to predict how signals from the targets may be mixed at each sensor. These processes continue until the estimate calculated is good. The system works well in tracking multiple targets when the targets are not interfering, and it can recover from inter target interference once the targets move apart.

   Now, table 1 shows the classification and comparison of all the routing protocols that we have discussed. Comparison is based on characteristic like scalability, mobility, power usage, route metric, data aggregation etc.

5. Conclusion

In recent years, WSNs have greatly expanded playing an important role for data efficient selection and its delivery. In this paper, we concentrate on the hierarchical routing protocols that have been developed for WSNs. The hierarchical protocols divide the network into clusters and to efficiently maintain the energy consumption of sensor nodes and perform data aggregation and fusion in order to decrease the number of transmitted messages to the sink. The

clusters are formed based on the energy reserve by the nodes and also by the cluster head. Thus, hierarchical routing protocols are suitable for wide coverage area and the networks with heavy load.

Different hierarchical based routing protocols are explained in brief and even discuss its advantages and disadvantages. Also they are compared based on scalability, mobility, power usage, route metric, data aggregation etc, as table 1. Therefore, further investigation in order to develop a scheme that will extend the lifetime of the WSNs is needed in order to improve the energy consumption of the sensors on the network. The application of the proper routing protocol will increase the network lifetime and at the same time it will ensure the network connectivity and efficient data delivery.

References

1. Al-Karaki, A. Kamal, Routing Techniques in Wireless Sensor net- works: A Survey,

   Security and Networks, 2004, Vol. 11, Issue 6,

   pp. 6-28.

2. Jun Zheng and Abbas Jamalipour, Wireless Sensor Networks: A Networking Perspective, a book published by A John & Sons, Inc, and IEEEE, 2009.

3. Jamal Al-Karaki, and Ahmed E. Kamal, Routing Techniques in Wireless Sensor Networks: A Survey, IEEE Communications Magazine, vol 11, no. 6, Dec. 2004, pp. 6-28.

4. I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, A Survey on Sensor Network, IEEE Communication Magazine, vol. 40, no. 8, Aug. 2002, pp. 102-114.

5. Kemal Akkaya and Mohamed Younis, A Survey on Routing Protocols for Wireless Sensor Networks, Ad hoc Networks, vol. 3, no. 3, May 2005, pp. 325-349.

6. W.R. Heinzelman, A. Chandrakasan, and

   H. Balakrishnan, Energy-efficient Communication Protocol for Wireless Microsensor Networks, in IEEE Computer Society Proceedings of the Thirty Third Hawaii International Conference on System Sciences (HICSS '00), Washington, DC, USA, Jan. 2000, vol. 8, pp. 8020.

7. W.R. Heinzelman, A. Chandrakasan, and

   H. Balakrishnan, An Application-Specific Protocol Architecture for Wireless Microsensor Networks in IEEE Tmnsactions on Wireless Communications (October 2002), vol. 1(4), pp. 660-670.

8. Fan Xiangning, Song Yulin. "Improvement on LEACH Protocol of Wireless Sensor Network, 2007.

9. V. Loscr, G. Morabito and S. Marano. "A Two-Levels Hierarchy for Low-Energy Adaptive Clustering Hierarchy.

10. Dissertation, Hang Zhou, Zhe Jiang and Mo Xiaoyan, "Study and Design on Cluster Routing Protocols of Wireless Sensor Networks, 2006.

11. W. B. Heinzelman et al., "An Application- Specific Protocol Architecture for Wireless Microsensor Networks, PhD Thesis, MIT 2000.

12. M. Bani Yassein, A. Al-zoubi, Y. Khamayseh, W. Mardini, "Improvement on LEACH Protocol of Wireless Sensor Network (VLEACH), International Journal of Digital Content Technology and its Applications Volume 3, Number 2, June2009

13. W.R. Heinzelman, ìApplication-Specific Protocol Architecture for Wireless Networksî PhD Thesis, Massachusetts Institute of Technology, June 2000.

14. S. Lindsey and C.S. Raghavendra, ìPEGASIS: Power- efficient Gathering in Sensor Information Systemî, Proceedings IEEE Aerospace Conference, vol. 3, Big Sky, MT, Mar. 2002, pp. 1125-1130.

15. S. Lindsey, C. S. Raghavendra and K. Sivalingam, "Data Gathering in Sensor Networks using the Energy*Delay Metric", in the Proceedings of the IPDPS Workshop on Issues in Wireless Networks and Mobile Computing, San Francisco, CA, April 2001.

16. Liu Yueyang, Ji Hong, and Yue Guangxin, ìAn Energy-Efficient PEGASIS-Based Enhanced

    Algorithm in Wireless Sensor Networksî, China Communications Technology Forum, August 2006.

17. A. Manjeshwar, D. Agrawal, Teen: A Routing Protocol for Enhanced EfÞciency in Wireless Sensor Networks, In Proc. 15th International Parallel and Distributed Processing Symposium (IPDPS01) Work- shops, USA, California, 2001, pp. 2009-2015.

18. A. Manjeshwar, D. Agrawal, APTEEN: A

    Hybrid Protocol for EfÞ- cient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks, In Proc.

    International Parallel and Distributed Processing Symposium, Florida, 2002, pp. 195-202.

19. J.N Al-Karaki, R. Mustafa, A. Kamal, Data Aggregation in Wireless Sensor Networks Exact and Approximate Algorithms, In Proc. IEEE Workshop High Performance Switching and Routing 2004, Phoenix, AZ, 2004, pp. 241-245.

20. H. Luo, F. Ye, J. Cheng, S. Lu, L. Zhang, TTDD: Two-Tier Data Dissemination in Large-Scale Wireless Sensor Networks, Wireless Networks, Springer Netherlands, 2005, Vol. 11, Issue 1, pp. 161-175.

21. S. Muruganathan, D. Ma, R. Bhasin, A. Fapojuwo, A Centralized Energy-EfÞcient Routing Protocol for Wireless Sensor

Networks, IEEE Commun. Mag., 2005, Vol. 43, Issue 3, pp. 8-13.

1. Q. Li, J Aslam, D. Rus, Hierarchical

   Power-aware Routing in Sensor Networks, In Proc. DIMACS Workshop on Pervasive Networking, California, 2001, pp. 25-27.

2. Y. Wu, S. Fahmy, N. Shroff, Energy

   EfÞcient Sleep/Wake Scheduling for Multi-Hop Sensor Networks: non-Convexity and Approximation Algorithm, In Proc. 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007),

   Anchorage, Alaska, 2007, pp. 1568-1576.

3. T.P. Sharma, R.C. Joshi, Manoj Misra, GBDD: Grid Based Data Dis- semination in Wireless Sensor Networks, In Proc. 16th International Conference on Advanced Computing and Communications (ADCOM 2008), Chennai, India, 2008, pp. 234-240.

4. J. Lotf, M. Bonab, S. Khorsandi, A Novel Cluster-based Routing Protocol with Extending Lifetime for Wireless Sensor Networks, In Proc. 5th IFIP International Conference on Wireless and Communications Networks (WOCN08), East Java Indonesia, Surabaya, 2008, pp. 1-5.

5. H. Cheng, G. Yang, S. Hu, NHRPA: A Novel Hierarchical Routing Protocol Algorithm for Wireless Sensor Networks, China Universities of Posts and Telecommunications, 2008, Vol. 15, Issue 3, pp. 75-81.

6. D. Kandris, P. Tsioumas, A. Tzes, G. Nikolakopoulos, Dimitrios D. Vergados, Power Conservation Through Energy EfÞcient

   Routing in Wireless Sensor Networks,

   Sensors, 2009, Vol. 9, Issue 9, pp. 7320-

   7342.

7. C. H. Lung, C. Zhou, Using Hierarchical

   Agglomerative Clustering in Wireless Sensor Networks: An Energy-efÞcient and Flexible Approach, Ad Hoc Networks, 2010, Vol. 8, Issue 3, pp. 328-344.

8. V. Rodoplu and T. H. Meng, Minimum Energy Mobile Wireless Networks, IEEE JSAC, vol. 17, no. 8, Aug. 1999, pp. 133344.

9. L. Subramanian and R. H. Katz, An Architecture for Building Self Configurable Systems, Proc. IEEE/ACM Wksp. Mobile Ad Hoc Net. and Comp., Boston, MA, Aug. 2000.

10. Q. Fang, F. Zhao, and L. Guibas, Lightweight Sensing and Communication Protocols for Target Enumeration and Aggregation, Proc. 4th ACM MOBIHOC, 2003, pp. 16576.