# Energy Efficient Routing in Wireless Sensor Networks: A Comprehensive Survey
## 4 Topology
### Location Based
Greedy Distributed Spanning Tree RoutingGDSTR (GDP) [119] algorithm uses hull trees, which is a different kind of spanning tree, where every node stores all the locations of its descendant nodes in the tree, in a convex hull. The hull trees are constructed from aggregating convex hull information, which is used to avoid non-productive paths. In addition, they are able to traverse a significantly reduced sub-tree, which consists of nodes with convex hulls containing the destination point. GDSTR handles local dead ends differently than other geographic routing algorithms by switching to routing on a spanning tree until greedy forwarding can make progress again. Each node maintains a summary of the area covered by the sub-tree below each of its tree neighbors, to choose a direction on the tree that will probably make progress towards the destination. GDSTR is simple and easy to implement and understand. In addition, compared to other geographic face routing protocols, it has lower path and hop stretch. However, in GDSTR, a local dead end problem occurs. Minimum Energy Relay RoutingMERR (MERR) [120] is a protocol based on the concept that the energy consumption of a path from the source to the base station depends on the distance between the pairs of the nodes in this particular path. In MERR, a characteristic distance is defined. A node searches its descendant nodes within its maximum range and picks the node closer to the characteristic distance or, in case every descending node's distance is greater than the characteristic, it picks its direct descending node. When the selection has been done, the sending node reduces antenna's power level to the minimum required to reach only the selected node. MERR achieves both reduction and uniformity of energy consumption. Its disadvantage is that energy is wasted when nodes are close. In _On-demand Geographic Forwarding_ (OGF) [121], when a node needs to send a packet, it searches its forwarding table. Depending on the search results, the following cases can be the outcome of this search:  
1. Case one: it finds the desired information and sends the packet. 2. Case two: receiving node has a special code in its entry, called passive, which allows the sender node to transmit packets only to passive nodes, resulting in the sender node going directly into void handling. 3. Case three: no receiving node entries in forwarding table with the result of sender node starting a contention to find its next hop node. If a sender cannot find a destination node, it turns into void handling mode. After successful packet delivery, sender node updates the forwarding table, inserting an entry for the established connection. OGF accomplishes both high energy conservation and good scalability. Also, void handling is provided. Yet, it depends on the up to date local neighbor tables. Partial-partition Avoiding Geographic Routing-MobilePAGER-M (PAGER-M) [122] protocol introduces a function of cost for every node, which depends on the distance between nodes and base station. This function tries to estimate a route close to the Euclidean length of the shortest route of a node to the base station. In PAGER-M, nodes use Greedy forward to transmit packets to the base station, which may sometimes fail at a node with distant neighbors from a base station. In that case, the packet is transmitted according to the rule of High to Low cost. By using PAGER-M, energy consumption is kept low and low overhead of routing is managed. However, PAGER-M is a stateless location based routing protocol. Hybrid Geographic RoutingHGR (HGR) [123] protocol uses a combination of direction and distance criteria for its routing needs. In HGR, every node defines a priority for its next hop \(Q_{i}\), which can take many forms for proper use of its distance and direction routing criteria. This priority becomes greater as the projected progress of node i gets larger and as a deviation angle between the line that connects z with i and the line that connects z with j gets smaller.