# Energy Efficient Routing in Wireless Sensor Networks: A Comprehensive Survey
## 3 Network Structure
### Hierarchical
#### 3.2.1 Hierarchy Based
These cluster heads, also called gateways, set up multi hop routes and maintain node states. Nodes use a TDMA based MAC for data transfer to gateway nodes, which are only allowed to communicate with the BS. Every node can operate in active or low-power modes. Sensing and processing circuits can be turned on and off independently resulting in four operating modes:  
1. [label=()]
2. Sense only
3. Relay only
4. Sense-Relay
5. Inactive  
In Sense only mode, the node searches the environment and generates data in a constant rate. In Relay only mode, sensing circuits are shut down and only relaying circuits operate and transmit data to and from other nodes. In Sense-Relay mode, a node senses and transmits message from other nodes. Finally, if a node is in Inactive mode, sense and relay circuits are turned off. Using a cost function to calculate link cost, a minimum cost path can be found. The gateway node will monitor available energy levels of every node that is active in one operating mode. The rerouting process is triggered by an application related event that requires a different set of nodes that monitor the environment or battery level of active nodes. The protocols achieve high energy efficiency. However, many gateways may be required to ensure high coverage. The authors of _Self-organizing_ protocol [83] developed a taxonomy of sensor applications and proposed an architecture to build sensor applications. This protocol supports heterogeneous sensor nodes that can be either mobile or stationary, can sense the environment, and relay data to a set of nodes, called routers, which are static and the backbone of communication. Router nodes relay data from sensor nodes to more powerful sink nodes. In order to tolerate faults, self-organizing protocol uses a Local Markov Loop (LML) algorithm in data transmission which picks a random path in the spanning tree of a graph. There are four phases in the self-organizing algorithm:  
1. Discovery phase: Every node discovers neighbor nodes. 2. Organization phase: Groups that are formed and merged forming a hierarchy where every node has an address based on its hierarchy position. Then, size O (logN) routing tables are created and, after that, broadcast trees that span all nodes are constructed. 3. Maintenance phase: In this phase, routing tables and node energy levels are being created. LML is used to maintain broadcast trees. 4. Self-organization phase: If an error of partial or whole node groups, re-organizations are performed. In Self-organizing protocol low maintenance of routing table is required. In addition, hierarchical routing maintenance is strictly balanced. Moreover, less energy consumption than SPIN occurs when broadcasting messages. Furthermore, the use of LML in relaying trees can tolerate faults. On the other hand, not on demand organization phase results in extra overhead. In addition, organization phase is performed again if many network disruptions take place during hierarchy forming, thus resulting in extra overhead. Distributed Hierarchical Agglomerative Clustering (DHAC) [84] is a hierarchical protocol, which suggests that a node needs only to know its next hop neighbor to build clusters. During cluster formation in DHAC, nodes initially obtain input data set and build a resemblance matrix. During this process, nodes elect themselves as cluster heads and exchange information via HELLO messages with their neighbors. Then, the DHAC algorithm is executed and each cluster head establishes its local resemblance matrix to find the minimum coefficient, then every cluster determines its minimum cluster head. After that, it cuts the hierarchical tree if the predefined upper limit size of clusters is reached. Next, DHAC controls the minimum cluster size, which can be used as a lower limit size by using the procedure Merge Clusters. Finally, cluster heads with lower id between two nodes that join the cluster on the first step are chosen. This procedure does not require additional processing.