## 5 Multiple Trees Hector Extension
### Algorithm  
For using multiple trees, some additional notations are introduced. Let \(\Omega\) be the set of trees. We note \(d_{mT}(u,v)\) the distance in the forest or set of trees between nodes \(u\) and \(v\):  
\[d_{mT}(u,v)=min_{t\in\Omega}d_{T}(u,v,t)\]  
where \(d_{T_{i}}(u,v)\) if the \(d_{T}\) distance in tree \(i\) between nodes \(u\) and \(v\). We note \(N_{mT}(u,u^{\prime})\) the set of neighbors of node \(u\) that provides a positive progress to \(u^{\prime}\) in the forest: \(N_{mT}(u,u^{\prime})=\{v|v\in N(u),d_{mT}(v,u^{\prime})<d_{mT}(u,u^{\prime})\}\). Based on this, we can now define the \(COP_{mT}\) function as the cost over the progress realized over the forest and not a single tree as follows: \(COP_{T}(u,v,d)=\frac{cost(|wv|)}{d_{mT}(u,d)-d_{mT}(v,d)}\). By replacing \(1\)-tree notations by these new notation, the same algorithm as Algorithm 1 applies. Algorithm 2 details the new routing algorithm. The current node \(u\) holding the packet first considers the set of its neighbors that provide both a positive progress on \(V\) coordinates and a positive or null progress over \(T\) coordinate whatever the tree considered (\(u\) considers nodes \(v\) such that \(v\in\{\{N_{mT}(u,d)\}\cup\{v|d_{mT}(v,d)=d_{mT}(u,d)\}\}\cap\{N_{V}(u,d)\}\)) and chooses the one among them that provides the best cost-over-progress over \(V\) coordinates. If no such node exists, \(u\) chooses the next hop as the one that provides the best progress over \(T\) coordinates over every tree. To break ties, it applies the _minimizing label_ and _label balancing_ rules that we describe below. ```
1:if\(u=d\)then
2: exit {/*Routing has succeeded*/}
3:else
4:\(H=\{\{N_{mT}(u,d)\}\cup\{v|d_{mT}(v,d)=d_{mT}(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\) for all trees. */}
7:\(H^{\prime}=\left\{v|COP_{mT}(u,v,d)=\min_{w\in N_{mT}(u)}COP_{mT}(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:\(M=\{v|v\in H^{\prime}\cap|l(v,t)|=min_{t^{\prime}\in\Omega,w\in H^{\prime}}|l _{t^{\prime}}(w)|\}\) {Minimizing label rule}
12:\(M^{\prime}=\{v\,\,\,\text{such that}\,\,v\,\,\text{has the best balanced labels over nodes in}\,\,M\}\) {Label balancing rule}
13:
14:\(Next\_Hop=rand(M^{\prime})\)
15:endif
```  
**Algorithm 2** Run at each node \(u\) on the routing path toward \(d\) to select next hop. Indeed, some cases may appear in which, from the local point of view of the current node, every tree provides the same progress to the destination. For instance, let us consider node \(13\) on Figure 2 aiming to send a message to node \(6\). Here, paths in both trees \(A\) and \(B\) have the same length, regarding \(T\) coordinates (\(7\) hops). Nevertheless, the message may follow the path through nodes \(13-0-3-4-5-6\), which is the shortest one but only if node \(13\) chooses Tree \(A\). To help node \(13\) make the right decision, two selection rules are introduced: the _minimizing labels_ rule and the _label balancing_ rule. _Minimizing labels_ rule: When paths are equivalent, the next hop in route selection is the node with the lowest label size. The idea here is that by selecting the next hop in such a way, the message goes at least \(1\) hop toward the tree roots and, as further stated by Theorem 6, the path in the tree from the root to any other node is the shortest path. This is easily done by counting and summing the number of digits of every label of a node. For instance, node \(13\) has to choose between node \(0\) (which label global size is \(|A00|+|B0110|=3+5=8\)) and node \(12\) (which global label size is \(|A0010|+|B0200|=5+5=10\)). Thus here, Tree \(A\) is selected since the number of digits of node \(0\) is the smallest one. When node \(0\) is reached, it reiterates the same process and so on. _Minimizing label_ rule: This rule allows the selection of a node with a high position in every tree.