# Parent and PHY Selection in Slot Bonding IEEE 802.15.4e TSCH Networks
## 3 Parent and PHY Selection Heuristic
### Heuristic
```
1:procedureassignParentAndPhy(\(\alpha\), \(\delta\))
2:for\(n\in N_{0}\)do\(\triangleright\) for every \(n\), assign the preferred PHY per parent
3:\(m_{n}=\textsc{mapPhyPerParent(n, \delta)}\)
4: converged = false
5:while\(\
eg\) converged do\(\triangleright\) stop when no node changed parent anymore
6: converged = true
7:\(x_{0}=0\)\(\triangleright\) score of root initialized to 0
8:for\(n\in N_{0}\)do
9:\(p_{n}=None\)\(\triangleright\) preferred parent of node \(n\)
10:\(x_{n}=None\)\(\triangleright\) score to preferred parent of \(n\)
11:for\(p\in P_{n}\)do
12:if\(x_{p}\
eq None\)then\(\triangleright\) only if possible parent has a score
13:\(ETX=\frac{1}{reliability(m_{n}|p|)}\)\(\triangleright\)\(ETX=\frac{1}{reliability}\)
14:\(x=x_{p}+ETX\cdot s_{m_{n}}|p|\)\(\triangleright\)\(s_{m}\) is bonded slot length of PHY \(m\)
15:if\(x_{n}=None\lor x<x_{n}\)then
16:\(x_{n}=x\)
17:\(p_{n}=p\)
18:converged = false\(\triangleright\) there was a change
19:return\(\{p_{0},p_{1},\ldots,p_{|N_{0}|}\},\{m_{0}[p_{0}],m_{1}[p_{1}],\ldots,m_{|N_{0}|} [p_{|N_{0}|}]\}\)
```  
**Algorithm 2** Heuristic to find preferred parents and PHYs. Having selected a PHY for each possible parent for each node \(n\), from line 5 onward in Algorithm 2, the heuristic searches for the preferred parent \(p_{n}\) of every node \(n\). The heuristic stops when every node has selected a preferred parent. Every node \(n\) is assigned a so-called _score_\(x_{n}\) and the score of the root is 0, assigned at line 7. The algorithm tries to minimize this score for each node as it represents the expected number of regular slots (i.e., not _bonded_ slots) needed to transmit a packet along the path from the node to the root. For every node \(n\), it loops over every possible parent \(p\) of node \(n\) and, if that parent was already assigned a score \(x_{p}\), it calculates a new score \(x\) for node \(n\). On line 13, this score is calculated by using the ETX value for the PHY selected for that possible parent. Afterwards, on line 14, that ETX is multiplied with the bonded slot length of that PHY (i.e., \(s_{m}\), the number of regular slots that need to be bonded together to transmit a packet, using PHY \(m\)), and added to the score \(x_{p}\) of the parent. If it is the first time the score is assigned to the node \(n\) or the score is smaller than the previous \(x_{n}\), this possible parent becomes the new preferred parent (see lines 15-17). By using the ETX and the bonded slot length for the score calculation, and by looking for the smallest parent score \(x_{p}\), the heuristic actually aims to pick a preferred parent with a path to the root that minimizes the number of allocations in the schedule. It was observed in the results of our previous work that more free space leads to higher PDR values; this way the heuristic tries to optimize the space in the schedule so every node can make sufficient allocations to successfully (re-)transmit their packets [7]. On line 18, it is denoted that there was a change in topology as this may affect other scores of other nodes. As such, the heuristic should not converge yet and keep running until no changes happen. Finally, when converged, the heuristic returns the sets of chosen parents and PHYs for each node. An example of the heuristic is given in Figure 2. Node 3 uses the heuristic to choose a preferred parent between nodes 0, 1 or 2 and a PHY to that parent. First, it selects a PHY per parent, with \(\delta=0.1\). Afterwards, it calculates the \(x\) score using the score from each possible parent, \(x_{p}\), the ETX value to that parent and the bonded slot length for the preferred PHY to that parent, \(s_{PHY}\), to select node 2 as its new preferred parent (using preferred PHY PHY1). The total time complexity of the proposed heuristic can be analysed by examining the time complexity of the two parts of the heuristic in Algorithm 2, that is, from line 2 to line 4 (including Algorithm 1) and from line 5 to line 18.