# Energy Efficient Routing in Wireless Sensor Networks: A Comprehensive Survey
## 3 Network Structure
### Hierarchical
#### 3.2.1 Hierarchy Based
To initialize the tree construction procedure, the BS sends a Child ReQuest packet (CRQ). The nodes that receive CRQ are candidates to elect as parents while the others wait for a short period of time. After that, they collect a number of candidate parent nodes and pick one based on the best defined metric. When a new node is introduced in the network, it sends a Parent ReQuest (PRQ) packet to inform its own neighbors for its existence. Data packets flow from children nodes to parent nodes and eventually to the BS. By using EDGE protocol, energy saving is achieved, flooding is avoided, and scalability is attained. On the other hand, the traffic overhead that is produced around the BS is particularly high. _Cluster Tree Power Aware_ (CTPA) [100] is a routing protocol that uses a splitting algorithm during clustering setup and the minimum spanning tree comparative analysis of energy efficient routing protocols for the WSN algorithm. During the process of cluster formation, the BS divides the network in two sub-clusters and further in smaller clusters until it meets the desired number of them. In the first round, the BS elects a node as cluster head in each cluster, the one closer to the center of it, while nodes outside the cluster elect their own cluster heads taking into account the power of received broadcast messages. After the first round is over, the procedure of cluster head election is executed by the sensor nodes. Via the Minimum Spanning Tree, the BS collects data from the cluster heads, while all nodes are able to aggregate data when the packets are transmitted to the cluster heads. In addition, cluster heads use a buffering mechanism to store latest queries and results or to check if the queries exist. In the case they do not, the queries are then forwarded to the rest of the nodes. CTPA protocol reduces energy consumption. On the other hand, the buffering mechanism used in CTPA protocol may cause overhead. _General Self Organized Tree Based_ (GSTEB) [101] is a protocol for periodic sensing of environment that aims to increase the network lifetime by using TDMA and Frequency Hopping Spread Spectrum (FHSS) mechanisms. In GSTEB, every node has an energy factor, for which is its residual energy is divided by an adjustable minimum energy value. After energy factor calculation, nodes transmit their factors to their neighbors via the TDMA mechanism and store these factors in a table. During every round, a root node, which is elected based on its residual energy, collects, aggregates, and transmits packets to the BS and broadcasts information, related with its energy and location, to the network. In addition, GSTEB uses a parent-children node scheme where nodes select their parent nodes, based on the energy factor and send them data packets to store them. Then, parent nodes change their roles to children nodes to send their data in the respective time slot. In the case that a node is about to die, it must broadcast a corresponding message to inform the other nodes by using TDMA scheduling. Nodesthat receive the announcement update their table. Finally, GSTEB balances the energy consumption by using the self-organizing mechanism to change topology. So, by using GSTEB, network lifetime is extended, collisions are avoided, and energy balance is attained. Yet, overhead is caused due to the large number of control packets, and scalability is limited. _Unequal Multi-hop Balanced Immune Clustering_ (UMBIC) [102] is a protocol that is particularly suitable for large scale monitoring. It combines the Multi-Objective Immune Algorithm (MOIA) and the Unequal Clustering Mechanism (UCM) in order to overcome the hot spot problem and improve network lifetime of WSNs with different densities. UMBIC uses an MOIA mechanism to elect cluster heads based on residual energy and build a routing tree among them to reduce the communication cost of data and control packets as well as to keep network connectivity.