## 3 Preliminaries
### Assumptions and Notations  
Let \(N(u)\) be the set of physical neighbors of node \(u\), _i.e._, the set of nodes in communication range of node \(u\). Let \(\delta(u)\) be the cardinality of this set, also called the degree of node \(u\): \(\delta(u)=|N(u)|\). We define \(N_{V}(u,u^{\prime})\) as the set of neighbors of node \(u\) that reduce the distance to node \(u^{\prime}\), regarding the \(V\) coordinates: \(N_{V}(u,u^{\prime})=\{v|v\in N(u),\text{ and }d_{V}(v,u^{\prime})<d_{V}(u,u^{ \prime})\}\). Similarly, \(N_{T}(u,u^{\prime})\) is the set of neighbors of node \(u\) that reduce the distance to node \(u^{\prime}\), in \(T\) coordinates: \(N_{T}(u,u^{\prime})=\{v|v\in N(u),d_{T}(v,u^{\prime})<d_{T}(u,u^{\prime})\}\).  
Although HECTOR is cost model-independent, for the sake of proof of concept, we use the most common energy model [23], which is as follows: \(cost(r)=r^{\alpha}+c\) if \(r\
eq 0\), \(0\) otherwise, where \(r\) is the distance separating two neighboring nodes, \(c\) is the overhead due to signal processing, and \(\alpha\) is a real constant (\(>\)1) that represents the signal attenuation. Note that, in reality, this needs to be multiplied with a constant that includes, for example, the message length.  
The optimal transmission radius, \(r^{*}\), that minimizes the total power consumption for a routing task is equal to: \(r^{*}=\sqrt[n]{\frac{c}{\alpha-1}}\) assuming that nodes can be placed on a line toward the destination [17].  
Let us introduce the functions \(COP_{T}\) and \(COP_{V}\) as functions defining selection criteria of \(s\)'s next hop toward \(d\) in a cost-over-progress fashion [1] over coordinates \(T\) and \(V\) respectively. \(s\) selects node \(b\), which minimizes \(COP_{T}\) or \(COP_{V}\) as defined later in Algorithm 1. These functions are as follows:  
\[COP_{T}(u,v,d)=\frac{cost(|uv|)}{d_{T}(u,d)-d_{T}(v,d)} \tag{1}\]  
Figure 1: On Figure 1(a), the tree root is node \(4\) and has the label \(R\). Node \(13\) is labeled \(R211\) since it is the first child of node \(0\), which has label \(R21\). Dashed lines represent physical links. On Figure 1(b), node \(4\) has coordinates \((2,2,3)\) since it is \(2\)-hop away from landmarks \(1\) and \(2\) and \(3\)-hop away from landmark \(3\).  
\[COP_{V}(u,v,d)=\frac{cost(|uv|)}{d_{V}(u,d)-d_{V}(v,d)} \tag{2}\]  
where \(|uv|\) is the Euclidean distance between nodes \(u\) and \(v\).  
Algorithm 1 formally describes this routing process.  
```
1:if\(u=d\)then
2: exit {/*Routing has succeeded*/}
3:else
4:\(H=\{\{N_{T}(u,d)\}\cup\{v|d_{T}(v,d)=d_{T}(u,d)\}\}\cap\{N_{V}(u,d)\}\)
5:if (\(H=\emptyset\)) then
6: {/*No node is closer to \(d\) than \(u\) on both \(V\) and \(T\).*/}
7:\(H^{\prime}=\left\{v|COP_{T}(u,v,d)=\min_{w\in N_{T}(u)}COP_{T}(u,w,d)\right\}\)
8:else
9:\(H^{\prime}=\{v|COP_{V}(u,v,d)=\min_{w\in H}COP_{V}(u,w,d)\}\)
10:endif
11:if (\(|H^{\prime}|>1\)) then
12:\(Next\_Hop=rand(H^{\prime})\)
13:else
14:\(Next\_Hop=v\) where \(H^{\prime}=\{v\}\)
15:endif
16:endif
```  
**Algorithm 1** Run at each node \(u\) on the routing path toward \(d\) to select next hop.  
In this paper, we assume every node is able to control its transmitting power (and thus its range) and to estimate the Euclidean distance between itself and every of its neighbor, based on the received signal strength (RSSI).  
HECTOR uses RSSI rather than the angle of arrivals or triangulation that require additional communication overhead. In addition, even if some obstacles or external environment impact could mislead the computing of the distance based on RSSI, this computed distance reflects the state of the link. If a short link is seen as long by the node because of low RSSI, the link will be less likely to be used, which is a positive point. Virtual distances are not suitable in the cost calculation since they do not reflect the real cost of the transmission.