## 4 CTP and Probabilistic Routing
### Proportional Distance Metric  
Node routing tables keep information of the ETX to some of their neighbours, CTP protocol selects the route with minimum ETX as a candidate for transmission. In order to balance the number of packets transmitted through a route, we investigated the use of a proportional probabilistic metric based on the differences between ETX of candidate paths.  
In order to determine the parent for the next transmission a subset \(\Lambda\) of \(k\) (where k \(\geq\) 1) neighbours is selected. The subset is formed by the \(k\) neighbours with minimum ETX excluding the current parent. The selected neighbours and the current parent are then divided in two groups (group one, and group two). Those with ETX at a distance lower than a given threshold \(\theta>0\) of the best candidate neighbour, and those ones with higher distance but not overpassing a threshold \(\omega\). Within those groups, nodes are assigned weights according to the following formula:  
\[\forall_{i,j}\in k\;\;w_{i}=\begin{cases}|\theta-i_{etx}|^{\alpha}&if\;i_{etx }-min(j_{etx})<=\theta\\ |\omega-i_{etx}|^{\alpha}&if\;\theta<i_{etx}-min(j_{etx})<=\omega\\ \infty&otherwise\end{cases}\]Textually, the weight of a neighbour \(i\) depends on the distance to the best candidate node, (_i.e._, the neighbour with minimum ETX). If this distance is lower than a \(\theta\) weight is computed as the result of calculating the distance between \(\theta\) and the ETX of neighbour \(i\). In the other case, considering nodes in group 2, the weight is calculated using the threshold \(\omega\). This distinction is done to maximize distances between good candidates and not so good candidates. The \(\alpha\) parameter is used to magnify differences.  
A constraint in our algorithm is also introduced. Weights for nodes in group one constitute the \(\sigma\)% (98% in our implementation) of the weight of the nodes in the subset \(\Lambda\). This is motivated by the fact that with \(1-\sigma\)% (2% in our implementation) probability other paths out of the best ones eventually will be explored.  
Once nodes have been assigned a weight, probabilities of being selected are assigned as a proportion of the quotient between their weight with respect to the total weight of the \(k\) neighbours in \(\Lambda\), _i.e._,  
\[p_{i}=w_{i}/\sum w_{i}\]  
Finally for each group a random number \(\delta\) drawn from the uniform distribution in the interval \((0,\sum(w_{i}))\) is chosen. A lottery scheme is used to chose the parent. \(w_{i}\) represents the number of tickets of a candidate \(i\) and the \(\delta\) represents the ticket. A neighbour \(i\) is elected if:  
\[\sum(w_{i})\geq\delta\]  
Considering that neighbours are sorted in ascending order of weight. Once there is a winner for both groups, another ticket is issued with probability \(\sigma\) for the first group and \((1-\sigma)\) for the second one.  
The value of \(\theta\) should be 10 ETX as 10 is the minimum ETX for one hop. This value ensures that any node within the group is not descendant of any other node in the group. For \(\omega\) the suggested value is \(\omega>50\) ETX. For CTP implementation a node is discarded as neighbour if its ETX falls 50 (MaxLinkQuality). Then \(\omega>50\) ETX is selected in order to do not definitively discard the node since eventually it can become a good candidate.