## 2 Related Work and Motivations
\begin{table}
\begin{tabular}{|c|c|c|} \cline{2-3} \multicolumn{1}{c|}{} & Exact Position & Virtual Position \\ \hline hop count (HC) & MFR [12], greedy [14] & VCap \\ \hline Energy-efficient (EE) & COP [1] & VCost [9] \\ \hline HC+Guaranteed-delivery (GD) & GFG [2] & LTP [10] \\ \hline EE+GD & EtE [3] & HECTOR \\ \hline \end{tabular}
\end{table} 
Table 1: Classification of Georouting Protocols. delivery are only variants of GFG [3, 20]. There also exist some beaconless georouting protocols based on the same idea [21]. We now describe approaches that rely exclusively on virtual coordinates, derived from either relative distances or hop counting to a set of landmark nodes in the network, without the intervention of external location services. The general idea is to define a virtual coordinate system and use it to induce a routing protocol based on the virtual coordinates. We survey some of them below (Jumps [7] or VCost [9]). A system of virtual coordinates based on three _landmarks_ is proposed. Nodes are assigned a tuple of coordinates given as the number of hops the node is distant from each _landmark_. This virtual coordinate system establishment is described in detail in Section 3.1. In VCap and JUMPS [7], nodes apply a greedy routing [14], based on the Hamming distance computed on these coordinates (instead of the Euclidean distance). The storage overhead for each sensor is limited to the storage of its coordinates and the coordinates of its neighbors. The authors show how the coordinate system is consistent for a given density of the network, _i.e._, nodes with the same coordinates lie within a limited number of hops from each other. A different approach is used in [8] where landmarks are selected more carefully after partitioning the nodes into tiles, and elaborate gradient descent procedures are used to route packets, and high communication and storage overhead is required to increase the delivery rate. However these approaches are neither energy-efficient nor guaranteed-delivery. Therefore VCost [9] proposes to use this system by applying a greedy cost-over-progress routing, as in COP [1], still based on the Hamming distance. VCost is energy aware but still does not guarantee delivery. [PERSON] and [PERSON] [22] observed that increasing the number of landmarks cannot eliminate virtual anomalies since some portions of the network may be 1-connected to the rest of network. They propose a one-dimensional virtual coordinate system based on depth first search (DFS) preorder traversal of the graph. Starting from a root node, nodes are labeled 1, 2, 3... with label assigned when a node is visited for the first time. Each node \(m\) also has an interval [m, q] starting from itself until all its children nodes are assigned, before traversal returns back to its parent. Routing is based on these labels. Current node may have few forwarding options; each of them is a neighbor that contains destination label within its interval of labels. Forwarding to a child node is favored to forwarding to parent node. In LTP [10], the authors introduce a new coordinate system, based on a tree construction. Each node is assigned a label which embeds the path between this node to any other node in the network, based on the path in the tree which is unique. The labeling process of LTP is described in more details in Section 3.2. Because of this labeling, LTP ensures the delivery of the message and the success of the routing but is not energy aware and may provide paths which are much longer than the optimal ones. In this paper, we propose a routing protocol that combines early results from the literature in order to provide a protocol routing that at the same time _(i)_ is energy efficient, _(ii)_ guarantees packet delivery and _(iii)_ does not need any external position information but a means to estimate relative distance between neighboring nodes.