# Energy Efficient Routing in Wireless Sensor Networks: A Comprehensive Survey
## 3 Network Structure
### Hierarchical
#### 3.2.1 Hierarchy Based
Distant nodes form first level clusters, while nearby nodes form second level clusters until a route to the BS is formed. After cluster formation process, two thresholds for sensed characteristics, which namely are Soft Threshold (ST) and Hard Threshold (HT), are broadcasted to cluster nodes from cluster heads. HT is the minimum value of a sensed parameter that a node needs to sense in order to activate its antenna and transmit it to a cluster head. In addition, it allows nodes to transmit only when the characteristic is in the range of the interest reducing significantly the number of broadcasts. Furthermore, it transmits data only when the value of this characteristic changes by an amount equal or greater than ST from the previous sensed value. Consequently, the use of ST reduces further the number of transmissions in the case that there is little or no change in the value of the sensed parameter. Both hard and soft thresholds can be adjusted in order to control the number of packet transmissions. TEEN provides higher energy efficiency than LEACH and LEACH-C and reduces the number of broadcasts. However, both overhead and complexity are high during multiple level cluster creation. Furthermore, periodic communication is not possible due to the reactive nature of the protocol. _AdaPtive TEEN_ (APTEEN) [62] is the extension of TEEN that aims both in capturing data collections and reacting in time critical events. When the BS has formed clusters, cluster heads broadcast, to every cluster node within their cluster, attributes, threshold values, and transmission schedule. Then, cluster heads perform data aggregation, before they forward data to the BS, to save energy. APTEEN follows the same architecture of TEEN but supports three different query types:  
1. [label=()]
2. Historical query, used to analyze past data values. 3. One-time query, used to take snapshot view of network. 4. Persistent query, used to monitor an event for a period of time. In APTEEN, energy dissemination is less than that in TEEN. However, APTEEN is more complex than TEEN and has longer delay times. _Virtual Grid Architecture_ (VGA) [63] is a protocol that utilizes a multi-level data aggregation and process during data routing, in order to improve network lifetime and energy efficiency. VGA's routing consists of two phases:  
1. [label=()]
2. Clustering aggregated data phase: divided in stationary clusters, the cluster head nodes, called Local Aggregators perform data aggregation. Master Aggregators, a part of Local Aggregator nodes, perform global or inter-cluster aggregation. 3. Routing aggregated data phase: in order to achieve an optimal and efficient solution, it uses heuristics, such as correlation of sensing information, in overlapping groups of Local Aggregator nodes. In VGA, energy efficiency is high, but the non-deterministic polynomial time problem of optimal selection of local aggregators as master aggregators exists. In _Two-Tier Data Dissemination_ (TTDD) [64], protocol sinks are able to move dynamically, while sensor nodes are static and location aware. Event data are created from a source node, which is the node closer to the event. The source builds a virtual grid, with itself as the first crossing point and transmits a message, with greedy geographical forwarding, at four different adjacent crossing points. The message stops when it reaches a node close to the crossing point and transmission ends when the boundaries of the network are reached. TTDD can be used for multiple mobile sinks in an area with static nodes. On the other hand, a virtual grid structure has to be built by each source node. _Base-Station Controlled Dynamic Clustering Protocol_ (BCDCP) [65] forms balanced clusters in terms of energy level and number of cluster nodes. Nodes transmit energy level information to the BS, which is a high energy node that calculates the average energy level. The BS selects nodes with energy level above the average level as cluster heads and forms clusters with similar number of cluster nodes.