Energy-Efficient Hierarchical Cluster Based Routing Algorithm In WSN : A Survey

Energy-Efficient Hierarchical Cluster Based Routing Algorithm In WSN : A Survey

Amit Bhattacharjee1, Balagopal Bhallamudi2 and Zahid Maqbool3

1 International Institute of Information Technology, Bhubaneswar, Orissa, INDIA 2 International Institute of Information Technology, Bhubaneswar, Orissa, INDIA 3 International Institute of Information Technology, Bhubaneswar, Orissa, INDIA

Abstract

Recent technological advances in communications and computation have enabled the development of low-cost, low-power, small in size, and multifunctional sensor nodes in a wireless sensor network. One of the important issues in wireless sensor network is the inherent limited battery power within network sensor nodes. Therefore, battery power is crucial parameter in the algorithm design to increase lifespan of nodes in the network. Much research has been done in recent years, investigating different aspects like, low power protocols, network establishments, routing protocol, and coverage problems of wireless sensor networks. In this paper, the focus is mainly on energy-efficient hierarchical cluster-based protocols in Wireless Sensor Network, emphasizing on various clustering techniques and routing techniques, Challenges involved in cluster-based routings. Over the period of time many cluster algorithms have been developed like LEACH [2], PEGASIS [3], TEEN[4], APTEEN [5], HEED [6] etc, based on

these legacy algorithms on clustering and routing algorithms many new algorithms are developed. This paper is an analysis of recent algorithms those are developed above mentioned ones. The algorithms include energy efficient clustering techniques and routing techniques as well. The paper concludes with possible future research areas under the domain of hierarchical clustering and routing techniques.

Keywords: Wireless Sensor Networks, Cluster Head (CH), Cluster-based routing, Hierarchical clustering, Base Station (BS).

1. Introduction

   Wireless Sensor Networks (WSNs) consist of small nodes with sensing, computation, and wireless communications capabilities. The sensor node has four basic components: sensing unit, processing unit, radio unit, and power unit, with their capabilities for monitoring and control, one of the main applications of sensor network is to periodically gather data from a remote terrain where each node continually senses the environment and sends back the data to the Base Station (BS) for further analysis. The most restrictive factor in the life-time of wireless sensor network is limited energy resource of the deployed sensor nodes. A number of routing protocols have been proposed WSN must take the issue of energy efficiency into consideration. Protocol should take care of self-configuration, fault tolerance, delay, etc. Another important criterion in the design of a sensor network is data delivery time since it is critical. Many routing, protocol concerning power management, and data dissemination techniques have been specifically designed for WSNs where energy awareness is an essential design issue. At the network layer, it is highly desirable to find methods for energy-efficient route discovery and relaying of data f ro m the sensor nodes to the BS so that the lifetime of the network is maximized. Since operation of the sensor networks is un- attended. In WSNs, sometimes getting the data is more important than knowing the IDs of which nodes sending the data. D esign requirements of a sensor network change with application. For

   example data transmission may depend on a whether the application is event driven, periodic, or query driven. For localization of nodes it u s e s radio strength (RSSI) signal to measure distance between nodes and distance to BS. Hierarchical routing protocols are considered to deliver better performance in respect of scalability, energy efficiency, life time. Many algorithms have been proposed based on hierarchical architecture of WSN. These algorithms try to optimize various QoS parameters in WSN like cluster formation techniques, cluster head selection process, packet delivery time, mobility of Base station etc. In our survey we come to see tradeoffs between these QoS parameters. In earlier surveys authors presented legacy/traditional algorithms and their performance. Over the period of time many new cluster-based algorithms have been proposed which is modification over traditional ones. Our survey is based on these newly proposed algorithms and we also give a performance measurement of these newly proposed algorithms based on different QoS parameters.

   1. ROUTING CHALLENGES AND DESIGN ISSUES IN WSN [1]:

      1. Node deployment

      2. Energy Consumption without losing accuracy

      3. Data Reporting Method

      4. Node/Link Heterogeneity

      5. Scalability

      6. Network Dynamics

      7. Transmission Media

      8. Coverage

      9. Data Aggregation

      10. QoS

   2. Hierarchical Routing Protocol:

      Traditional routing protocols for WSN may not be optimal in terms of energy consumption. Clustering techniques can be efficient in terms of energy and scalability. The objective of clustering is to minimize the total transmission power aggregated over the nodes. Every cluster selects a cluster head (CH) responsible for coordinating the data transmission among the nodes in a cluster.

      Main advantages of clustering over other class of algorithms are:

      • Minimization of intra-cluster and inter cluster energy consumption

      • Scalability

      • Prolong network life time

      • Reducing data packet delay

      • Handling node heterogeneity.

      Fig-1: Clustering of Sensor Nodes

   3. Challenges in Hierarchical Cluster based algorithms:

      • Some cluster based algorithms are suitable for small region or small number of nodes (LEACH).

      • Some are suitable only for static deployment of nodes and degrades in the case of node mobility.

      • In some algorithm cluster heads distribution is concentrated in one area.

      • Some cluster based algorithms are not suitable for time critical application.

      • All earlier Cluster based algorithms are top down approach, that requires re clustering

      • Some algorithms allows all CH to send data to base station that incurs more energy dissipation

      • Few of the algorithms uses probabilistic approach, without considering residual energy, results in early dyeing of CHs.

2. Energy Efficient Clustering and Routing Techniques in WSN:

1. Distributed Hierarchical Agglomerative clustering Algorithm (DHAC), 2008 [7]:

   One of the most challenging tasks in cluster based algorithms is how efficiently cluster is formed. earlier approaches for forming cluster are top-down

   approach where CHs are selected first then clustering is done, this requires re clustering operation, DHAC is a bottom up approach that perform clustering then selects CHs, it saves energy during cluster formation. DHAC can accommodate both qualitative and quantitative information in selection of CHs with automatic CH rotation and rescheduling. They group nodes based on resemblance matrix created during information collection phase. During cluster formation each node sends HELLO messages to their one hop neighbour and exchange component attributes like location of mobile nodes, receive signal strength, residual energy etc. based on that resemblance coefficient between pair of node is computed corresponds to that resemblance matrix are prepared at node level. It indicates degree of similarity or de similarity between pair of nodes. Based on that a dendogram is created. After that DHAC merges two similar clusters together and update the resemblance Matrix (using SLINK, CLINK, UPGMA and WPGMA), once clustering is done CHs are selected. To choose the corresponding CHs, DHAC simply choose the lower ID node between the two nodes that join the cluster at the rst step. The CH chosen does not require extra processing. Phases of cluster head selection are: – (a) obtain the input data set. (b) Compute the resemblance coefficient. (c) Execute the HAC algorithm. (d) Cut the hierarchical cluster tree. (e) Control the minimum cluster size. (e) Choose CHs.This algorithm compared with LEACH and LEACH-C with respect to Network life time, total energy dissipation vs. amount of data packet received at sink, shows better performance against LEACH and LEACH-C.

2. SPSOC- Energy Efficient Hierarchical routing Protocol for WSN, 2008 [8]:

   In wireless sensor networks (WSN) to maximize its lifetime of network is the most important issue, but the existing protocols are prone to early death of CHs because they ignore the state of neighbours in the cluster head decision. This cluster based optimization algorithm optimizes clustering process effectively to avoid the low-energy and long-distance nodes as the cluster head. In this object cluster head routing protocol only object cluster head send overall data to

   sink node, which can balance energy depletion among the cluster heads in WSN, The simulation shows that this optimization strategy significantly prolongs survival time. Main principles applied in this algorithm are Particle swarm optimization (PSO) [8] and simulated annealing (SA) [8].combination of SA and PSO performs cluster convergence more quickly also reduces number of iterations to find optimal solutions

   .cluster head selection is based on fitness function model [8]. Selection of object CH routing protocol: under this protocol all the CH are refrain from sending their data to sink, and selected object CH only send data to sink on behalf of rest of the CHs, object CH selection is based on weight function as per the fitness function model [8]. Radio energy dissipation model adopted in algorithm are free space model and multi path fading model.

   Simulation is compared with LEACH, and shows better performance as compared to LEACH with respect to network life time.

3. Energy-Efficient Routing Protocol based on Clustering and Least Spanning Tree in WSN, 2008 [9]:

   This algorithm proposed a novel energy-efficient approach for clustering and least spanning tree approach for data transmission. Clustering includes partitioning stage and choosing CHs, and then all the CHs construct a least spanning tree towards BS to prolong the network life time. Different phases in this model of system are (1) constructing cluster-head part, in each area dynamic construction of cluster head according to remainder energy (2) A centralized approach to construction of least spanning tree, according to the cluster-head, sink will dynamic construct least spanning tree to prolong network lifetime.(3)sensing part, the sensors around the target area are responsible for probing the target/event and send the collected data to their cluster-head (4) relaying part, the collected data are relayed among the cluster-heads by least spanning tree to the sink (5) last the sink performs system-level data analysis and process for an overall situation awareness. Clustering involves 1) mention any specific clustering process

   mentioned any distributed clustering approach, in re clustering phase if residual energy of CH is lower than some threshold then only this process starts. For construction of least spanning tree it uses Prims algorithm approach.

4. CHIRON: Energy-Efficient chain based hierarchical routing protocol, 2009[10]

   This algorithm is an improvement over PEGASIS [3] and EPEGASIS, a chain based hierarchical algorithm. Principle technique applied in this algorithm is Beam Star concept[].the main idea of CHIRON is to split the sensing field into a number of smaller areas, so that it create multiple shorter chains to reduce the data transmission delay and redundant path, and therefore effectively conserve the node energy and prolong the network lifetime. In CHIRON, the technique of Beam Star [10] is first used to divide the sensing area into several fan-shaped groups. The sensor nodes within each group are then self- organized into a chain for data dissemination unlike traditional approaches, instead of taking turns, we consider the node with a maximum residual energy as chain leader candidate. In addition, for avoiding a longer transmission would be incurred among chain leaders, the nearest downstream chain leader will be elected for relaying the aggregated sensing information. Proposed CHIRON has the following merits. (1) Each node can get its location information passively from the BS with a minimum control overhead.( 2) The collected sensing data can be reported to the BS, in a short-haul and multi-hop transmission manner. (3) It can effectively reduce the chain length and redundant transmission path, so thus significantly improve the delay time and save network energy, as compared to other counterparts. Experimental results [10] show that the proposed CHIRON outperforms several existing chain-based routing protocols, in terms of network lifetime. This algorithm consists of following phases:

   1. Group Construction Phase

   2. Chain Formation Phase

   3. Leader node election phase

   4. Data collection and transmission phase

5. BCEE: Balanced clustering Energy Efficient Hierarchical Routing Algorithm in WSN, 2009 [11]: BCEE, which operates in two phases. During Phase 1,

   the balanced cluster formation is achieved by applying k-means clustering strategy, called KMDC algorithm, which does not require exact position of each node but use RSSI(receive signal strength indicator) instead. Then, ant colony optimization is used algorithm in Phase 2 to establish the route with optimal or sub-optimal power consumption between cluster heads and sink node. BCEE protocol can achieve better load-balance, offer significant reductions of energy consumption and prolong network lifetime hugely than LEACH. The algorithm goes through

   1. Centroid calculation model based on RSSI

   2. Apply KMDC procedure for re-clustering

   3. At steady state it uses ACO to form route to the destination.

   In k-means algorithm, the sum of squared Euclidean distances is measured, To choose centroids and form the clusters. Accordingly, It uses received signal strength indication (RSSI) is utilized to denote the distance between cluster head and sensor node in WSNs, not requiring the physical distance. Thus calculate the RSSI using k- means algorithm to select each cluster head and form clusters in sensor networks. This algorithm tries to optimize average energy consumption, Network life time, simulation result shows that energy consumption in transmission reduces considerably due to transmission of aggregated data in multi-Hop manner also BCEE lifetime is much longer than that of LEACH when rounds increase, which verifies the positive effect of BCEE on prolonging network lifetime. But the network lifetime with BCEE is almost the same with LEACH when the rounds are less than 100 which means BCEE is not so effective in the beginning. Problem with this algorithm is that it still suffers from re-clustering, but it provides uniform node distribution, scalability, fault tolerance and load balancing.

6. CCPAR:- Clustered Chain Based Power Aware Routing, 2010[12]:

   This is a new power-aware, adaptive, hierarchical and chain based protocol. It utilizes periodic assignments of the cluster head role to different nodes based on the highest residual battery capacity for ensuring the even dissipation of power byall the nodes. Transmission from a single cluster head to the base station in each round and the distribution of the data aggregation also reduces the amount of information to be transmitted to the base station By chaining the nodes in each cluster and using a separate chain for the cluster heads, CCPAR offers the advantage of small transmit distances for most of the nodes and thus helps them to be operational for a longer period of time by conserving their limited energy. This algorithm introduces MAX threshold value that enables CCPAR to be quickly responsive to events and thus highly suitable for time critical applications. For t5ransmission and receiving it considers both free space model and multi path fading model. The algorithm goes through different phases like (1) cluster formation, CH selection and chain of CH construction.(2) chain formation within cluster and schedule setup (3) data transfer. In this proposed CCPAR the authors did not mention about cluster formation technique, for scheduling purpose they use CSMA MAC protocol. CH node broadcasts three parameters to their member nodes MIN threshold, MAX threshold, Change Factor CF, if sensed value is less than MIN threshold or in between MIN threshold and MAX threshold but less than change factor CF then nodes does not aggregate its sensed value to received value. If sensed value is in between MIN threshold and MAX threshold and greater than CF only then node aggregates its sensed value this saves energy dissipation in computation. At a given instant of time only one CH will send data to the BS station selected by CHs, for time critical application if sensed value is more than MAX threshold then sensor nodes immediately send data to their CH node. This algorithm compared with LEACH, PEGASIS, TEEN, APTEEN shows better performance in respect of power consumption.

7. EEHRP: Energy Efficient Hierarchical Routing Protocol for Long Range Transmission in WSN, 2010 [13]:

   This algorithm is an improvement over HEED [6]. It takes care of the problem of long range transmission when BS is located far away from the sensing field, in such situation cluster heads are burdened with heavier relay traffic and tend to die much faster. To mitigate the problem, author propose EEHRP for Long range transmission in the wireless sensor networks. It uses a number of gateway nodes, which do not engage in clustering but transmitting packets received from the CHs to the base station, thus the CHs can preserve some energy in data forwarding and the gateway nodes can ease their burden by not participating in clustering the network executing EEHRP proceeds through three phases: First formation of gateway nodes Second cluster processing, Third Cluster nodes connects to their gateway. Cluster formation is same as in HEED. In the third phase, all the cluster member nodes go into a state of sleep, and all the gateway nodes begin to send initial message Each CH node chooses its closest gateway with the largest received signal strength and informs the gateway node by sending a ChilReq message. The EEHRP algorithm is terminated when all the CHs find their gateway nodes. The network topology is shown in the fig:

   Fig-2: Network topology of EEHRP

8. HABRP: Hierarchical Balanced Energy-Efficient Routing Protocol for Heterogeneous WSN, 2010 [14] This algorithm considers node heterogeneity in cluster

   formation, it uses Adaptive balanced approach to decrease probability of failure of nodes and prolong network life time. In these networks some high-energy nodes called NCG nodes (Normal node/Cluster Head/ Gateway) are elected as cluster heads to

   aggregate the data of their cluster members and transmit it to the chosen Gateways that requires the minimum communication energy to reduce the energy consumption of cluster head and decrease probability of failure nodes and properly balance energy dissipation. Routing in HABRP works in rounds and each round is divided into two phases, the Setup phase and the Steady State, each sensor knows when each round start using a synchronized clock. The phases of the algorithm are 1.Gateway selection algorithm. 2. Cluster head selection algorithm. 3. Cluster formation algorithm. First gateway selection [8] is done based on probability Pg [8] such that expected number of gateways are Kg based on that T(Sgat) is calculated i.e. threshold for gateway nodes after that CH selection is done here nodes are classified in to normal node and advanced nodes based on probability Pnrm and Padv [8] correspondingly it calculates T(Snrm) and T(Sadv) , threshold value for normal nodes and advanced nodes During cluster formation phase each round begins with a set-up phase followed by a steady- state phase. in set-up phase gateways are elected and CH are selected after that cluster formation is done, in steady state phase data are transmitted from node to CHs and CHs to selected gateways. Data transmission from CH to BS is based on eq given by to the gateway if ECH_to_BS > ECH_to_Gat + EGat_to_BS. To the Base Station if: ECH_to_BS <= ECH_to_Gat + EGat_to_BS. Experiment [8] of this algorithm compares it with LEACH. The performance matrices consider are length of 1) Stable region, stability period is defined as the period from the start of the network operation and the first dead node. 2) Number of alive nodes per round. 3) Variation of residual energy for advanced and normal node per round. 4) Improvement of stability period. Shows better performance than LEACH.

9. HEERP: Hierarchical Energy Efficient Routing Protocol for WSN, 2012 [9]:

   This algorithm introduces a newer centralized approach to hierarchy formation without the formation of cluster and selection of cluster heads. The algorithm steps involved 1) Network hierarchy and neighbour table construction 2) Data Transmission 3) Maintenance of Network. During first step objective is to setup hierarchy and neighbour table construction for each

   node. Sink initiates formation of hierarchy by broadcasting LCREQ packet, rest of nodes chooses LCREQ packets from nodes with lesser hop count field in this way nodes stores records and keep flooding the packet until the network is constructed. Every sensor node keeps in its Parents-information- table the identities of the parent nodes with lesser hop towards the base station. In data transmission phase every node is ready to send data to its node parents. During maintenance phase it take care of routing and removes entry of those nodes whose battery gets exhausted or damaged due to environmental factors. Simulation result shows in hierarchy formation HEERP consumes less energy than LEACH. Delay in packet delivery is also improved in HEERP compared to LEACH

10. EADC: A Cluster based routing protocol for WSN with non uniform node distribution, 2012 [10]: This algorithm includes a clustering algorithm and a

    cluster-based routing algorithm; it specially focuses on non uniform node distribution in a sensing field. It uses competition range (Rc) to construct cluster of even sizes and the routing algorithm disseminates data forwarding task of densely spaced CH nodes to sparsely spaced CHs with higher energy to achieve energy balance among CHs. It supports both multi-hop and single-hop transmission by CHs. The algorithm has the following phases 1. Information collection phase 2. CH completion phase 3. Cluster formation phase 4. Cluster based routing algorithm. During information collection phase each node Si calculates its average residual energy compared to its neighbours, node also calculates its waiting time ti for broadcasting Head_Msg, this paper mathematically calculates that the probability that multiple nodes broadcast the Head_Msg at the same time is very low by the help of a theorem [10]. During cluster head completion phase if node Si receives no Head_Msg when timer ti expires, it broadcasts the Head_Msg within radio range Rc to advertise that it will be a cluster head. Otherwise, it gives up the competition. In cluster formation phase every non-cluster head node choose the earest cluster head and sends the Join_Msg which contains the id and residual energy of this node. According to the received Join_Msgs, each cluster head creates a node schedule list including the Schedule_Msg for its cluster members, the Schedule Msg is used for telling the cluster members when they can transmit their data to

    the cluster head and in other time interval they can alter their state to asleep to reduce the energy consumption. After forming of clusters it constructs a routing tree among the elected CHs, data forwarding between CH to BS can be single-hop or multi-hop, based on threshold value DIST_TH. If transmission is multi-hop then CH selects its next-hop CH based on indicator called relay [10]. CH Si chooses the neighbour CH with the largest relay and closer to the BS as its next hop. Overall this algorithm tries to balance energy-heterogeneity between densely spaced CHs and sparsely spaced CHs by outsourcing data forwarding task to CHs which have less number of member nodes. Simulation experiment shows in EADC CH are evenly distributed across the topology area either in the case of randomly deployed or non-uniformly deployed topology region because of completion range Rc . Network life time also prolongs compared to LEACH.

11. MNUC: A Mixed Non-Uniform Clustering Algorithm for Wireless Sensor Networks, 2011 [17] This is a newly proposed algorithm that solves the problem of Hot-Spot in cluster based algorithms hot- spot is an area where nodes have to do more computation and transmission related work compared to other parts of the network, due to that these nodes drain more energy that leads to imbalance in energy. The idea is to form clusters of unequal radius to counter load imbalance, near the BS clusters of smaller size are formed, size of cluster increases as the distance from BS increases. Cluster size is determined by competition radius Ri [17], competition radius Ri is proportional to the distance di and node residual energy Ei. So more cluster head will be formed near the sink node, thus to solve the load imbalance. Algorithm is divided into two parts: cluster formation phase and clusters scheduling. During cluster formation phase each node generates a random number Q between 0 and 1. If Q is less than the threshold T, nodes turn into the state head competition, Else remain active. In practice, the optimal threshold T is with the network size and node density [17]. In next step nodes in CH competition calculates competition radius Ri and broad cast their current residual energy and ID in Ri to collect information competing nodes compare their residual energy and residual energy of nodes in their radius Ri to elect CH and broadcast this information in Ri , after selection of CH a node according to head signal

    strength receiving, determines the cluster to join in, and will send its own current energy, ID and the information about neighbours to cluster head. Clusters form minimum spanning tree by Kruskal algorithm, and data will be sent to the sink through the minimum spanning tree. If CHs residual energy gets down to threshold value then reconstruction phase starts that goes back to initial phase of candidate node generation and repeat the same procedure again. In cluster node scheduling phase CH decides some node as working nodes based on equation given in [17], establishes a TDMA schedule among them other nodes are kept in dormancy.

12. a novel routing protocol with lifetime maximizing clustering algorithm for wsn, 2012 [18] This algorithm proposed a novel routing protocol based

    on new clustering approach and construction of routing tree for efficient data transmission. Clustering approach applied is top down where selection of CH is done first and then clustering is done, over this formed cluster a routing tree is formed by CHs for data transmission, but in this algorithm for M number of nodes number of clusters K is determined without knowing optimal value of Clusters. CH selection is based on probabilistic approach, residual energy of node also take in to consideration. As per the algorithm only even number node can be CH in each round, probability of node become a new CH is

    =

    During cluster formation elected CHs broad cast a low control message to all non-CH node in the network using CSMA/CD, based on RSS signal strength nodes choose to which cluster it will join and select appropriate CH. After forming cluster and selecting CH routing tree is prepared. Routing tree formation is a centralized approach where BS broadcast init_tree message to the CHs in response to that CH nodes sends t_accept message that is a request for parent and request for ID also. Sink send a message to the parent node and the parent node send the short range broadcast message to the other cluster heads. CHs reply with the create_child message. Parent node accepts the CHs as a child if number of child less than Cmax. Otherwise it forwards the

    request to one of its child. This procedure repeats until all the CHs entered in to the routing tree. Data transmission inside CH is done in TDMA manner, there is a threshold value G to avoid a single node transmitting data multiple times in a round. When compared with LEACH and TL-LEACH it shows increased network life time with respect to number of nodes alive after particular round and round after which first node dies, but it doesnt shows performance regarding data transmission and transmission cost of data delivery.

13. HSEP: Heterogeneity-aware Hierarchical Stable Election Protocol for WSNs, 2012, [19]

    This cluster based algorithm is an improvement over SEP [20], in SEP it takes care of heterogeneity of nodes in to consideration. SEP evenly consumes extra energy of advance nodes and gives longer stability period than LEACH; it takes separate threshold values for normal nodes and advance nodes. HSEP is hierarchical based clustering routing protocol uses two types of CHs primary CHs and secondary CHs. HSEP is heterogeneous-aware protocol in a sense that it consists two types of nodes i.e. advance nodes and normal nodes. In this protocol these probabilities of nodes to become CHs are weighted by initial energy of a node relative to other nodes in network. This approach prolongs time interval before death of rst node; in other words, stability period. In HSEP Secondary CHs can be from existing primary CHs. Primary CHs check distance between each other and transmit their data to those secondary CHs which are at minimum distance from them. data transmission is done using TDMA approach between nodes and primary CHs also in between primary and secondary CHs. only improvement by HESP over SEP is introduction of two level hierarchy in SEP.

14. MHL: Multi-hops routing Protocol based on level, 2012 [21]

    This algorithm proposed a protocol that resolves the issue of scalability of cluster based routing protocols earlier developed. This protocol adopted a probabilistic approach to CH selection same as LEACH, also rotation of CHs in random manner. Each node prepares a routing table based on broadcast information of CH inside the scope of radio range in multi level manner. Initially bone CH broadcast interest message to all

    sensor node in its radio range, the nodes that receive this message set to level 1, then level one nodes prepare a new interest message and broadcast it further to create second level, in this way levels are propagated, all the sensor nodes initialize their levels and prepare routing table. Above mentioned procedure is an incremental approach to solve the problem of scalability. Data transmission is in multi level manner from lower level to higher level towards the sink node. Data transmission is in unicast manner. It also shows that energy consumption in MHL is lesser than LEACH since transmission energy consumption in LEACH is

    Where L is the bit length and D is distance to CH but transmission energy dissipation in MHL is

    In multi hop i.e.

    Otherwise direct communication to sink node. Parameters that are optimized areremaining energy of nodes after first node dies and system lifetime compared to leach.

15. U-LEACH: – Universal LEACH, 2012[23]

    U-LEACH is an improvement over leach that shows reduction in energy consumption by the sensor nodes, in this clustering approach selection of CH is based upon initial and residual energy of nodes where in LEACH selection of CH is a probabilistic approach, apart from CH selection data dissemination is multi- hop approach from farthest node to CHs and from CH to master CH (MCH), MCH is responsible to send gathered data to BS. This protocol merges important features of I-LEACH [22] and PEGASIS [3]. It incorporates Energy aware CH selection approach from I-LEACH and multi-hop transmission approach to BS from PEGASIS. This algorithm considers node heterogeneity with respect to initial residual energy of nodes those are deployed in a planned manner. Clustering process is based upon X-coordinate values of nodes, but this paper does not mention clustering approach properly, also approach to clustering is bottom up where clustering is done and after that selection of CH, after that selection of master CH is

    done periodically to send gathered data to BS. Once this clustering procedure gets over, chain formation takes place in each cluster. The formation of chain takes place from the farthest node in a cluster and eventually ends with the CH. At CH, there is diffusion process, which reduces the gathered information from all the nodes of the cluster into small but meaningful information. Though it reduces energy consumption by introducing multi-hop data transmission but selection of MCH is periodic and on round robin basis, doesnt consider distance of MCH from BS, so delay may incur in data delivery if selected MCH is farther from BS, in that case transmission cost is more. Also in this algorithm deployment of nodes are not random, nodes are heterogeneous and deployment is done in planned manner, half of the nodes get higher energy values than the rest of the sensor nodes. Odd numbered nodes gets one value of the energy while even numbered nodes get the other value of the energy. Comparative study shows network life time with respect to death of first node and death of nodes in subsequent rounds.

16. WB-TEEN and WBM-TEEN2012 [24]

These two protocols are improvements of LEACH and TEEN, This protocol adopts the Time-driven model and uses a distributed clustering. Problem with LEACH is that it assumes the nodes are homogeneous and the routing of packets to the base station is done in a single hop via the cluster-heads that consumes considerable amount of transmission energy. Problem with TEEN is group disparity in cluster formation due to unequal number of nodes in different cluster. WB- TEEN tries to solve the problem of disparity by equal number of nodes in each cluster. WB-TEEN computes degree based on that it selects membership of node or rejects node membership. WBM-TEEN is other protocol that apart from the improvements of WB- TEEN imposes multi-hop intra cluster data transmission to sink. These two protocols compared with LEACH and TEEN with respect to network lifetime, energy consumption. In view of CH selection it adopts LEACH technique, the only unique feature is calculation of degree of node and multi-hop data transmission within cluster. Performance metric observed by them are energy consumed with respect to

number of rounds, number of nodes alive per round, and network lifetime of system.

1. Conclusion

   WSN routing protocol is a new area of research , here we try to show some new protocols developed over the years based on legacy based algorithms like LEACH,PEGASIS,TEEN, HEED, these new algorithm depict some new concepts and techniques. Emphasizes more on cluster formation and multi hop routing protocol development, our classification shows basic parameters those are optimized by these algorithms , improvements over these are possible to introduce QoS parameters. Although these protocols shows improvements but still there is possibility of improvements by researchers to deploy WSN in different aspects of applications.

   References

   1. Jamal N. Al-Karaki, Ahmad E. Kamal, Routing Techniques in Wireless Sensor Networks: A survey, IEEE wireless Communications Dec- 2004.

   2. W.R. Heinzelmam, A. Chandrakasan, and H. Balakrishnan, Energy-Efficient Communication protocol for Wireless Microsensor Networks , in IEEE Computer Society Proceedings of the 33rd Hawaii International Conf on System Sciences (HICSS 00) Washington,DC

      USA, Jan 2000,vol. 8,pp.8020.

   3. S. Lindsey, C . Raghavendra, PEGASIS: Power-Efficient Gathering in Sensor Information Systems, IEEE Aerospace Conference Proceedings, 2002, Vol. 3, 9-16 pp. 1125-1130.

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

   5. Manjeshwar and D. P. Agarwal, APTEEN: A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks, Parallel and Distributed Processing Symposium., Proceedings International, IPDPS, 2002, pp. 195-202.

   6. Ossama Younis, Student Member, IEEE, and Sonia Fahmy, Member, IEEE, HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks, IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 3, NO. 4, OCTOBER-DECEMBER, 2004.

   7. Chung-Horng Lung, Chenjuan Zhou, Using Hierarchical Agglomerative Clustering in Wireless

      Sensor Networks: An Energy-Efficient and Flexible Approach, 978-1-4244-2324-8/08, 2008, IEEE.

   8. Wen-Wen Huang, Min Yu, Li-Qiong Xiong, Jian Wen , Energy-Efficient Hierarchical Routing Protocol for Wireless Sensor Networks, IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, 2008

   9. Ming Zhang, Yanhong Lu, Chenglong Gong, Energy-Efficient Routing Protocol based on Clustering and Least Spanning Tree in Wireless Sensor Networks, International Conference on Computer Science and Software Engineering, ,

      IEEE, 2008

   10. Kuong-Ho Chen, Jyh-Ming Huang, Chieh-Chuan Hsiao, CHIRON: An Energy- Efficient Chain- Based Hierarchical Routing Protocol in Wireless Sensor Networks, IEEE

   11. Xiaoyan Cui, Zhao Liu, BCEE: A BALANCED- CLUSTERING, ENERGY-EFFICIENT HIERARCHICAL ROUTING PROTOCOL IN WIRELESS SENSOR NETWORKS , Proceedings of IC-NIDC, IEEE, 2009.

   12. Koushik Majumder, Sudhabindu Ray, A Novel Energy Efficient Chain Based Hierarchical Routing Protocol for Wireless Sensor Networks, 2010, IEEE

   13. Hui Li, Jianghong Shi, Qi Yang , Dezhong Zhang , An Energy-Efficient Hierarchical Routing Protocol for Long Range Transmission in Wireless Sensor Networks , 2nd International Conference on Education Technology and Computer (ICETC),

       IEEE, 2010

   14. Hui Li, Jianghong Shi, Qi Yang , Dezhong Zhang , An Energy-Efficient Hierarchical Routing Protocol for Long Range Transmission in Wireless Sensor Networks , 2nd International Conference on Education Technology and Computer (ICETC), IEEE, 2010.

   15. Khlifi Nesrine, Maher Ben Jemaa ,HEERP: Hierarchical Energy Efficient Routing Protocol for Wireless Sensor Networks, The 2nd International Conference on Communications and Information Technology (ICCIT): Communication Networks and Systems, Hammamet, 2012, IEEE

   16. Jiguo Yu, Yingying Qia, Guanghui Wangb, Xin Gua, A cluster-based routing protocol for wireless sensor networks with no uniform node distribution, Int. J. Electron. Commun. (AEÜ) 66 (2012) p.54 61

   17. Guibo Du, Qinghua Shi, Yunze Tang, Xiao Sun A Mixed Non-Uniform Clustering Algorithm for Wireless Sensor Networks, 978-1-61284-307-0/11 2011 IEEE

   18. L. Malathi, M.K. Chandrasekaran, R.K. Gnanamurthy, A NOVEL ROUTING PROTOCOL WITH LIFETIME MAXIMIZING CLUSTERING ALGORITHM OR WSN 978-1- 4673-2272-0/12 2012 IEEE

   19. A. A. Khan, N. Javaid, U. Qasim , Z. Lu , Z. A. Khan ,HSEP: Heterogeneity-aware Hierarchical Stable Election Protocol for WSNs Seventh

       International Conference on Broadband, Wireless Computing, Communication and Applications, 978-0-7695-4842-5/12 2012 IEEE.

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

   21. Ai-Li Zhang , Gui-Chao Wang , Yong-Zhen Li, WSN Multi-hops Routing Algorithm Based on Levels, Second International Conference on Instrumentation & Measurement, Computer,

       Communication and Control2012 ,IEEE

   22. Naveen Kumar, Jasbir Kaur, Improved LEACH Protocol for Wireless Sensor Networks. In Proceedings of 7 th International Conference on Wireless Communications Networking and Mobile Computing, Wuhan, China, 2011.

   23. Naveen Kumar, Sandeep, Pawan Bhutani, Prity Mishra ,U-LEACH: A Novel Routing Protocol for Heterogeneous Wireless Sensor Networks 2012 International Conference on Communication, Information & Computing Technology (ICCICT), Oct. 19-20, Mumbai, India.

   24. Zibouda Aliouat, Saad Harous. An Efficient Clustering Protocol IncreasingWireless Sensor Networks Life Time, International Conference on Innovations in Information Technology (IIT),2012, IEEE.