# Energy Efficient Routing in Wireless Sensor Networks: A Comprehensive Survey
## 3 Network Structure
### Hierarchical
#### 3.2.1 Hierarchy Based
It combines a Dominating Set algorithm (DS) for cluster formation and Ant Colony Optimization (ACO) to shorten transmission distance within a cluster, in order to reduce the chain lengths of it. LEACH-DS-ACO extends network lifetime. On the other hand, mobility is not supported. _Power Efficient Gathering Sensor Information System_ (PEGASIS) [57] is an improvement of LEACH protocol, which, instead of creating clusters, it creates chains of nodes. The main characteristic of a chain is that every node transmits data only to the two nearby neighbor nodes and only one sensor node can be selected to communicate with BS. Collected data are transferred from node to node being aggregated and finally transmitted to the BS. PEGASIS provides higher energy efficiency than LEACH. In addition, less broadcasts use data aggregation. On the other hand, large delay is caused for distant nodes. In addition, redundant data are transmitted. Moreover, single leader mechanism may cause congestion. _Hierarchical PEGASIS_[58] is an extension of PEGASIS that tries to reduce the delay that occurs from packets during transmission to the BS and offers a solution to data collection problem taking into account the metric Energy x Delay. Simultaneous packet transmission used to reduce delay and suggests two approaches to prevent collisions and signal interference among sensor nodes. The first approach is called CDMA and incorporates signal coding while the second approach spatially separated nodes only can transmit packets simultaneous. The protocol with CDMA nodes can construct chains with a tree like hierarchy, in which a selected node in a specific level transmits data to a node in the higher level of the hierarchy. This method ensures parallel data transmission and reduces delay. On the other hand, the protocol without CDMA creates a three-level node hierarchy that reduces interference problems with carefully scheduled simultaneous broadcasts. However, significant overhead is caused. _Multi-Hop PEGASIS_ (MH-PEGASIS) [59] is an improved version of PEGASIS, which utilizes inter-cluster communication and multi-hop routing to reduce energy consumption during data transmission of distant cluster heads to the BS. In MH PEGASIS, every round consists of two phases the initialization and the data transmission phases. During the initialization phase, an inter cluster communication happens where every node communicates with its neighbors. Receiving nodes aggregate data with their own and transmit them until the cluster head receives them. During the transmission phase, cluster heads forward their data to upper level cluster heads until they reach the BS. In MH PEGASIS, the energy consumption of distant cluster heads is reduced and the network lifetime is extended. On the other hand, load balancing issues are caused. _Enhanced PEGASIS_[60] is an improved version of PEGASIS protocol, which reduces redundant data during transmission. To achieve this, the BS divides the network into levels depending on how strong the receiving signal of a node is. To determine optimum number of levels, enhanced PEGASIS takes into account various parameters such as network's density, the BS location, number of nodes, and application requirements. As performed in the original PEGASIS, within the level area, chain construction begins from the farthest nodes utilizing a greedy algorithm. Cluster heads collect data from nodes within the same level and forward them to the lower level until they reach the BS while higher level nodes are the most distant ones. In Enhanced PEGASIS, redundant data are reduced. However, delay is high in distant nodes. _Threshold sensitive Energy Efficient sensor Network_ (TEEN) [61] is one of the most popular hierarchical protocols. It has been designed for time critical applications, where the network operates in reactive mode, responsiveness is very important. TEEN's architecture is based on hierarchical clustering with a use of a Data-Centric mechanism.