# Introduction ireless sensor network consist of tiny devices called sensor node and sink called base station. Sensor node sense and collect information from surrounding environment in which they lie and transfer it to sink. Various application areas such as security surveillance, military reconnaissance, habitat monitoring, medical and health, disaster management, industrial automation, etc make use of WSN to sense data in harsh environment. In above mentioned applications, reliability and on time delivery of sensory data is must for the critical mission success. Major challenges with wireless sensor networks are their limited source of energy, high traffic load and the coverage constraint. Routing of data in WSN has been one of the challenging areas for researchers [1]. In most wireless sensor network (WSN) applications network have the capability to operate unattended in harsh environments. Nodes in such environments are energy constrained and their batteries cannot be recharged .Such environment demands energy-aware routing and data aggregation protocols providing high scalability in order to maximize network lifetime. Routing protocols in WSN, on the basis of network structure are categorized in to 3 main categories [2]:-1. Flat 2. Hierarchical 3. Location based In particular, hierarchical routing protocols (explained in section 4) offer significant savings in total energy utilization in WSN. In hierarchical routing protocols, sensor nodes organized the in to clusters. Each cluster is governed by a cluster-head and only heads send messages to a BS. Research community widely accepted the grouping of sensor node in cluster to achieve objectives such as scalability, prolonging network lifetime and high energy. Advantage of this method is it saves energy by data aggregation by CH. Less the energy utilization, the more the network life time in WSN. But this method of clustering may commence overhead due to the cluster organization and maintenance, but it has been verified that cluster-based protocols demonstrate better energy consumption and performance in comparison to flat network topologies for large-scale WSNs. # II. # Related Work Kumarawadu et al. [4] present a survey on clustering protocol and categorized them on the basis of CH selection and cluster formation parameters. In the survey author discuss the design issues and performance challenges in clustering protocol based on the taxonomy of neighbourhood information based clustering protocol, identity-based clustering approach, and biologically encouraged clustering algorithms and probabilistic clustering protocol. Arboleda et al. [3] briefly discussed LEACHbased protocols, proactive and reactive protocol and presented a survey comparing various clustering protocols. Some concept such as clustering advantages, cluster types, cluster structure of clustering process explained in detail. Jiang et al. [6] analyzed hierarchical routing protocol, author compare these protocols on eight parameter of clustering. Author highlight the three important advantages of clustering process for WSNs, such as more less overheads, scalability, and easy maintenance, and then present a categorization of WSN clustering schemes. Deosarkar et al. [5] focus on CH election criteria based on three metrics deterministic, adaptive and combined metric. The author analyse the cost of CH election and evaluate it against cluster formation and distribution of CHs and concluded that there is a need of more scalable, energy capable and efficient clustering scheme in WSNs for data aggregation. Deng [13] focuses on design issues and relative analysis of WSN clustering routing protocol for increasing the network lifetime. The authors analyzed numerous challenging issues that influence design of routing techniques in WSNs, and categorized routing algorithm with comparative analysis. Xu et al. [11] consider six clustering protocol and compare them on various parameters such as data gathering robustness, scalability, network lifetime, security energy conservation. Maimour et al. [7] considered nine distinctive clustering protocols based on two categories, preestablished clustering routing protocol and on-demand clustering routing protocol clustering routing protocols to attain energy conservation in WSNs and also discuss clustering protocol from the point of view of data routing. # III. # Clustering In order to study different clustering protocol we need to have knowledge of clustering parameters and its taxonomy. The objective of clustering protocols is to increase scalability, balance load, improve energy consumption, fault tolerance, efficient energy/resource, latency reduction, guarantee of connectivity and provide robustness in a WSN [3]. # a) Challenges of clustering Wireless Sensor Networks present vast challenges in terms of implementation. There are several key attributes that Designers must carefully consider which are of particular importance in wireless sensor networks [3], [4]. Cluster count: cluster count can be fix or variable depending up on which clustering technique is used [5]. In probabilistic and randomized approaches CH are not predetermined thus the cluster formation process result in to variable no. of clusters. Cluster count is fixed for approaches where the CH is predetermined. Cluster-head election: Various published approaches adopt various criteria for selection of CH. The sensor node in every cluster elects a leader among all the node either on randomized basis or follow a probabilistic approach or based on some other criteria (such as based on residual energy, node degree etc.) Cluster formation process: cluster formation technique are of two type centralized or distributed earlier approaches followed centralized or hybrid approach ,when CHs are just one or more coordinator nodes are used to partition the whole network off-line and control the cluster membership [6].But nowadays as time efficiency is important distributed approach is followed. Communication among nodes: In clustering two type of communication can occur intercluster communication or intra cluster communication both can be further of two type single hop and multi hop. Earlier clustering approaches assume the communication among its nodes and CH to be single hop but nowadays various approaches are published which provide multihop communication in intracluster. Overlapping: Overlapping in clustering is said to occur when a sensor node is shared by more than one cluster. Overlapping provide better routing efficiency and also fasten up cluster formation process [7]. Some published approaches allow overlapping, some try to have minimum overlap some not at all permit overlaps c) Classification of clustering approaches Clustering approaches varies depending on various features. On the basis of functionality and characteristics of sensor nodes in cluster clustering approaches are categorised in to two categories homogenous algorithm and heterogeneous algorithm. Heterogeneous sensor networks consist of two type sensors, common sensors (lower capabilities sensor, used to sense data) and sensor equipped with complex hardware (sensor with higher capabilities ,does the task of data aggregation etc). Homogeneous networks consist of sensor node with same characteristics, hardware and processing capabilities [8]. Based on cluster formation clustering approaches are of two type centralized and distributed algorithm. Considering the network structure, there are two type of routing protocol in WSN: flat and hierarchical routing protocol [9]. In flat routing protocol all the node have same functionality. But effective for small scale network where as hierarchical routing protocol is suitable for large scale network. Most hierarchical routing protocols are having cluster-based organization of nodes to imply data aggregation, thus saving significant amount of energy. In hierarchical network each cluster has a cluster head (CH) which performs the specialized task of data aggregation and fusion, and several sensor nodes act as members. The cluster formation process has two-level hierarchy where cluster head form higher level and member nodes in cluster form the lower level. The sensor nodes send data sense by them to their corresponding cluster-head periodically. CH nodes aggregate this data remove redundant information and transmit it to sink or base station (BS) directly or through multihop routing. However, most of the time CH nodes need to send data at higher distances than common member nodes of cluster, thus they spending greater energy than common nodes. Common solution to this problem is load balancing among the sensor nodes by re-electing new CHs periodically. Figure 1 : classification for various clustering approaches Another classification of clustering approaches is dynamic clustering and static clustering [11]. Cluster formation process is called dynamic when its CHS reelection is either event driven or periodic and react and adjust appropriately with cluster as well as network topology otherwise it is called static clustering approach .Dynamic clustering approach is very useful for sensors in WSN as it improve the network lifetime and manage the consumption of energy . Most Clustering approaches are categorised in to two categories probabilistic and non probabilistic [12]. In Probabilistic approach a prior probability assigned to each sensor node is used to determine the initial CHs where as in non probabilistic clustering approach, a deterministic criteria for CH selection and cluster formation is followed and is based on nodes' proximity and on the data received from neighbouring nodes The typical clustering hierarchical protocols in WSNs include LEACH, EEHC, and HEED and their extensions. These are probabilistic algorithm some of them (LEACH and EEHC) follows random approach for CH election where as HEED is a hybrid approach where primary criteria followed by secondary criteria considered for CH. Based on proactivity, clustering routing protocol can be categorized into proactive, reactive, and hybrid [10]. In proactive protocol, all routes between source and the BS are established before they are really needed in spite of data traffic. Once a message arrives, it go along a predestined route to the BS. Whereas, no predestined routes exist in reactive protocol, in which the routing is selected when a message desires to be delivered from source node to the BS. Hybrid approaches use a blend of the above two approaches. For this sort of clustering routing, occasionally proactive clustering mode is adopted, but at other period reactive mode is used. IV. Hierarchical Routing Protocols a) LEACH Low-Energy Adaptive Clustering Hierarchy was first hierarchical routing clustering protocols. In WSNs, we need energy efficient network protocol such as LEACH is due to the fact that nodes in the WSNs are battery operated and have limited energy. In the LEACH protocol, the sensor nodes organize themselves into clusters each cluster is governed with cluster head (CH). Leach do load balancing by randomized alternation of cluster heads among all the sensor node in the network. This randomized approach is adopted to delay the first node death by distributing the load among all nodes in network. Cluster heads not only collect data from their clusters, but also aggregate the gathered data for reducing the data to be sent to the Base station, for less energy dissipation, to increase the network life time. Sensor nodes select themselves to be CHs at any time with some probability. The decision to nominate a node as cluster head is taken periodically. The elevation decision is to be ended only by each node free of other nodes. This is done to reduce overhead in cluster head organization. The Threshold function is defined as [14] Where n is the total node, r is the present round number, P is the probability of a node to be a cluster head and G is the set of nodes that have been not nominated as cluster heads in the previous 1/P rounds. Every node during cluster head selection will create a random number in between 0 and 1. The node will be converted into a cluster head if the number is less than the threshold (T (n)). # b) TEEN TEEN stands for Threshold sensitive Energy Efficient sensor Network protocol (TEEN) [17]. It is a mixture of data-centric protocols and hierarchical clustering routing protocol and intended for real-time applications. It is a reactive protocol, quickly respond to sudden changes of some of the feature observed in the WSN (e.g., pressure).The protocol initially goes through cluster formation and cluster head selection. The CHs then transmit two thresholds to sensor nodes in their clusters. These are soft and hard thresholds for the sensed feature: Hard Threshold (HT): It is the value, of the feature below which, the node sensing this value must turn on its transmitter and inform its cluster head. Soft Threshold (ST): It stimulates the node to switch on its transmitter and inform the sensed data to its cluster head if change in the value is greater than the ST. # Figure 2 : Clustering topology in TEEN A node will send data only when the sensed value is below the HT or alteration in the value is above the ST the. However, TEEN cannot be functional for sensor networks where sensor readings should be conveyed to the Sink in regular intervals, as the values of the feature may not accomplish the threshold at all. Furthermore, we have a number of shattered time-slots in TEEN protocol and there is forever likelihood that the sink may not be able to differentiate dead and alive nodes. Another drawback of the protocol is that the message broadcast is done by CHs only. If CHs are not in each other's transmission radius, the messages will be lost. c) APTEEN APTEEN-Adaptive Threshold sensitive Energy Efficient sensor Network protocol [18] is an expansion to TEEN protocol and goal at both having periodic data collections and reacting to real-time events. The structural design of APTEEN is same as in TEEN. In APTEEN firstly the clusters are formed by base station, the cluster heads relay the attributes, the transmission schedule and the threshold values to all nodes. Cluster heads achieve data aggregation in APTEEN in order to save energy. It supports three query types: one-time, to take a snapshot view of the network; historical, to analyze precedent data values; and determined to monitor an event at a time. # d) EECS An Energy Efficient Clustering Scheme (EECS) [15] is a clustering algorithm in which cluster head candidates compete for the ability to elevate to cluster head for a given round. This competition involves candidates broadcasting their residual energy to neighbouring candidates. If a given node does not find a node with more residual energy, it becomes a cluster head. Cluster formation is different than that of LEACH. LEACH forms clusters based on the minimum distance of nodes to their corresponding cluster head. EECS extends this algorithm by dynamic sizing of clusters based on cluster distance from the base station. The result is an algorithm that addresses the problem that clusters at a greater range from the base station requires more energy for transmission than those that are closer. Ultimately, this improves the distribution of energy throughout the network, resulting in better resource usage and extended network life time. EECS is a LEACH-like clustering scheme, where the network is partitioned into a set of clusters with one cluster head in each cluster. Communication between cluster head and BS is direct (single-hop).In the network deployment phase, the BS broadcasts a "hello" message to all the nodes at a certain power level. By this way each node can compute the approximate distance to 0the BS based on the received signal strength. It helps nodes to select the proper power level to communicate with the BS. Also this distance is used to balance the load among cluster heads. In cluster head election phase, well distributed cluster heads are elected with a little control overhead. And In cluster formation phase, a The most important aspect of HEED is the method of Cluster head selection. Cluster heads are determined based on two important parameters [13]: 1) The residual energy of each node is used to probabilistically choose the initial set of cluster heads. This parameter is commonly used in many other clustering schemes. 2) Intra-Cluster Communication Cost is used by nodes to determine the cluster to join. This is especially useful if a given node falls within the range of more than one Cluster head. In HEED it is important to identify what the range of a node is in terms of its power levels as a given node will have multiple discrete transmission power levels. The power level used by a node for intracluster announcements and during clustering is referred to as cluster power level [13]. Low cluster power levels promote an increase in spatial reuse while high cluster power levels are required for intercluster communication as they span two or more cluster areas. Therefore, when choosing a cluster, a node will communicate with the cluster head that yields the lowest intra-cluster communication cost. The intra-cluster communication cost is measured using the Average Minimum Reach ability Power (AMRP) measurement. The AMRP is the average of all minimum power levels required for each node within a cluster range R to communicate effectively with the cluster head i. The AMRP of a node i then become a measure of the expected intra-cluster communication energy if this node is elevated to cluster head. Utilizing AMRP as a second parameter in cluster head selection is more efficient then a node selecting the nearest cluster head [13]. # f) PEGASIS PEGASIS is a data-gathering and near-optimal chain-based algorithm. Power-Efficient Gathering in Sensor Information Systems [8] protocol reduces the consumption by creation of a chain structure containing of all nodes and simultaneously do data aggregation across the chain. According to PEGASIS algorithm if nodes made a chain from source to sink, among all the node across chain only one node will send the data to base station in a given transmission time-frame. Dataaggregation occurs at all node in the sensor network to pervade all important information across the network. In PEGASIS in spite of multiple nodes only one node in a chain transmit data to the BS. It increases the network life time, when all nodes take turns in communicating with the BS and node communicate only with their nearby neighbours. It reduces the power required to send data per round as the energy draining is spread equally among all nodes. In, PEGASIS energy conservation is achieved in two ways: 1. The head node receives at most two data messages. 2. The distance over which the data are transmitted to closest neighbour is much smaller So, PEGASIS conserves energy by reducing the number of data messages gathering at head node [8] [9]. g) CCS CCS is a protocol [16] which reduces energy consumption and extension of PEGASIS protocol. In CCS, the entire network is separated into co-centric circular path and each one of these paths form a cluster. Each path is assigned with a stage. For example, the nearest path to the BS is assigned as stage-1, and as it moves further from the BS the level number increases like Stage-2, stage-3 and so on. In every path, nodes form a chain exactly like PEGASIS. A head node is selected among all of the nodes in the chain and these head nodes are allocated with node numbers. All non head node in a chain, obtain data from its immediate neighbour, aggregate it with its own data and then broadcast it to its immediate neighbour. So it's clear that the head node in each path receives almost two messages. After broadcasting data in a path and receiving it at the head node and then the head nodes in closest path cooperate and send data to the BS. For example the head node in stage-n send out data to the head node in stage-(n-1) and this process persist until sending data to the BS is ended. Data aggregation can be done at every head nodes. In this scheme, the distance over source BS from the head node is reduced. This reduced transmission distance saves a significant amount of energy. Also, as the network is separated into a number of concentric clusters, the backward flow of data from BS, which was significant in PEGASIS, is reduced. Due to this, a considerable amount of energy is preserved during data transmission, but this repeated data broadcast can still be less than this protocol proposed. V. # Conclusion A comparison between various clustering protocol is concluded in the below mention table In this document we have studied the current state of hierarchical routing algorithms, with respect to their various requirements such as energy utilization, stability, delivery delay etc. In wireless sensor networks, the nodes have limited energy in them which demand to have a careful approach in designing and implementation of clustering algorithm [1]. Moreover there is much future work to be done. Further improvements on energy utilization can be obtained by minimizing the energy used in the clusterhead election process [13]. Energy efficient clustering should eradicate all operating cost associated with the clusterhead selection, as well as with node association respective to their clusterheads. Various algorithms explained the concept of reliability of Sensor network reliability by using re-clustering that occurs in time period; but mostly are energy inefficient and restrict the time accessible within network for data sensing and transmission. Reliability further should be improved by modifying the re-clustering mechanisms subsequent the initial clusterhead selection. Thus reliability can be increase by reducing the wastage and efficient utilization of resources. ![Hierarchal Routing Protocol in Wireless Sensor Networks](image-2.png "") ![Hierarchal Routing Protocol in Wireless Sensor Networks](image-3.png "") ![Hierarchal Routing Protocol in Wireless Sensor Networks](image-4.png "") ![Hierarchal Routing Protocol in Wireless Sensor Networks novel weighted function is introduced to form load balanced clusters. e) HEED Hybrid Energy-Efficient Distributed Clustering (or HEED) is energy efficient clustering protocol for wireless sensor networks, with a focus on efficient clustering by proper selection of cluster heads based on the physical distance between nodes. The main objectives of HEED are to [13]: ? Distribute energy consumption to prolong network lifetime; ? Minimize energy during the cluster-head selection phase; ? Minimize the control overhead of the network.](image-5.png "") 3![Figure 3 : Data transmission scheme in PEGASIS](image-6.png "Figure 3 :") 4![Figure 4 : Stages in CCS algorithm](image-7.png "Figure 4 :") 1ProtocolScalibilityClusterEnergyLoadAlgorothmDelivery DelayStabilityEfficiencyBalancingComplexityLeachVery LowModerateVery LowModerateLowVery SmallHeedModerateHighModerateModerateModerateModerateEecsLowHighLowModerateVery HighSmallPegasisVery LowLowVery HighModerateHighVery LargeTeenLowVery LowModerateGoodHighSmallApteenLowLowLowModerateVery HighSmallCcsLowHighLowVery BadModerateLarge © 2014 Global Journals Inc. (US) * Wireless sensor networks: A survey IFAkyildiz WSu YSankarasubramaniam ECayirci Comput. Netw 38 2002 * A survey on clustering algorithms for wireless sensor networks AAAbbasi MYounis Comput. Commun 30 2007 * Comparison of Clustering Algorithms and Protocols for Wireless Sensor Networks LM CArboleda NNasser Proceedings of IEEE CCECE/CCGEI IEEE CCECE/CCGEIOttawa, ON, Canada, 7-10 May 2006 * Algorithms for Node Clustering in Wireless Sensor Networks: A Survey PKumarawadu DJDechene MLuccini ASauer Proceedings of 4th International Conference on Information and Automation for Sustainability 4th International Conference on Information and Automation for SustainabilityColombo, Sri Lanka December 2008 * Cluster Head Selection in Clustering Algorithms for Wireless Sensor Networks: A Survey BPDeosarkar NSYada RPYadav Proceedings of the 2008 International Conference on Computing, Communication and Networking the 2008 International Conference on Computing, Communication and NetworkingVirgin Islands, USA August 2008 * Towards Clustering Algorithms in Wireless Sensor Networks-A Survey CJiang DYuan YZhao Proceedings of IEEE Wireless Communications and Networking Conference IEEE Wireless Communications and Networking ConferenceBudapest, Hungary April 2009 * Cluster-based Routing Protocols for Energy-Efficiency in Wireless Sensor Networks MMaimour HZeghilet FLepage December 2010 14 * Hierarchical Routing in Wireless Sensor Networks: A Survey JJLotf MHosseinzadeh RMAlguliev Proceedings of 2010 2nd International Conference on Computer Engineering and Technology 2010 2nd International Conference on Computer Engineering and TechnologyChengdu, China April 2010 * OBoyinbode HLe AMbogho Takizawa, M * A Survey on Clustering Algorithms for Wireless Sensor Networks RPoliah Proceedings of 2010 13th International Conference on Network-Based Information Systems 2010 13th International Conference on Network-Based Information SystemsTakayama, Japan * Cluster-Based Routing Protocols in Wireless Sensor Networks: A Survey CWei JYang YGao ZZhang Proceedings of 2011 International Conference on Computer Science and Network Technology 2011 International Conference on Computer Science and Network TechnologyHarbin, China December 2011 * Comparison study to hierarchical routing protocols in wireless sensor networks DXu JGao Procedia Environ. Sci 10 2011 * A Survey of Hierarchical Routing Protocols in Wireless Sensor Network AJoshi MLakshmi Priya May 2011 17 * HEED: A Hybrid Energy-Efficient Distributed Clustering Approach for Ad Hoc Sensor Networks OYounis SFahmy IEEE Transactions on Mobile Computing 3 4 Oct-Dec 2004 * A Two-Level Hierarchy for Low Energy Adaptive Clustering Hierarchy GLoscri SMorabito Marano DEIS Department, University of Calabria * Energy Efficient Communication Protocol for Wireless Sensor Networks WRHeinzelman AChandrakasan HBalakrishnan Proceedings of the33th Hawaii International Conference on System Sciences the33th Hawaii International Conference on System Sciences 2000 * SMJung YJHan TMChung The Concentric Clustering Scheme for Efficient Energy consumption in the PEGASUS 9th International Conf. on Advanced Communication Technology Feb. 2007 1 * TEEN: A Protocol for Enhanced Efficiency in Wireless Sensor Network 1st international Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing AManjeshwar DP 2001 189 * APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks AManjeshwar DP 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing 2002