# Lightweight Path Recovery in IPv6 Internet-of-Things Systems
## 4 Design of LiPa
### Iterative Path Recovery  
The proposed LiPa will iteratively use the known paths to recover unknown paths until no more paths can be recovered.  
Algorithm 2 gives the complete flow of this algorithm. At moment \(t\), the sliding window \([t-\tau,t]\) is used as the observation interval. The input is two sets, \(Pinit\) and \(Punknown\). Since the packets record the parent and grandpa nodes, \(Pinit\) is formed by  
Figure 5: The correlations of paths. (**a**) Case 1. (**b**) Case 2. (**c**) Case 3. (**d**) Case 4. (**e**) Case 5. (**f**) Case 6.  
packets whose path length is one or two hops, while the rest of the packets have unknown form _Punknown_. The packets with unknown paths will try to recover unknown paths according to the path correlation inference given in Algorithm 1. The algorithm terminates when no more unknown paths or no more paths can be recovered. The output is the packets with recovered paths.  
```
0:\(P_{init}\): a set of packets during \([t-\tau,t]\) whose paths have been recovered; \(P_{unknown}\): a set of packets during \([t-\tau,t]\) whose paths are unknown;
0:\(P_{known}\): a set of packets during \([t-\tau,t]\) whose paths are recovered;
1:\(P_{known}\gets P_{init}\)
2:while\(P_{unknown}\
eq\{\}\)do
3:\(P_{learn}\gets P_{known}\)
4:for each packet \(k\in P_{known}\)do
5:for each packet \(i\in P_{unknown}\)do
6:if\(RecoveryCore(k,i)\equiv TRUE\)then// Recalling the Algorithm 1
7:\(P_{learn}\gets P_{learn}\cup i\)
8:\(P_{unknown}\gets P_{unknown}-i\)
9:endif
10:endfor
11:endfor
12:if\(P_{learn}\equiv P_{known}\)then
13: Break
14:endif
15:\(P_{known}\gets P_{learn}\)
16:endwhile
```  
**Algorithm 2** The Lightweight Path Recovery Algorithm.  
**Time complexity analysis.** We set the number of nodes to be \(N\), the \(Ratio_{active}\) to be \(\alpha\), \(\alpha\in[0,1]\), and the window size to be \(\tau\). For Algorithm 1 (i.e., The Recovery Core Algorithm), its complexity is \(O(Alg.1)=O(1)\), due to it consisting of up to seven operations of if-then-else-then. For Algorithm 2 (i.e., The Lightweight Path Recovery Algorithm), the basic operation is to call Algorithm 1. As all active nodes will send packets, and the number of packets at each time slot is \(\alpha\times N\). The window size \(\tau=[\frac{1}{\alpha}]\) for path recovery is obtained from Equation (8), so the total number of packets in the time interval \([t-\tau,t+\tau]\) is \(N\), which consists of \(Pinit\) and \(Punknown\). The algorithm's complexity for Lines 4-11 in Algorithm 2 is obtained as \(O(N^{2})\). Since packet \(k\) with \(len(k)\) is able to recover packet \(i\) with \(len(i)\in[len(k)-1,len(k)+2]\) and the algorithm terminates when no more path can be recovered, the executed times of the whole loop can be considered as \(N\). Therefore, the total complexity of the LiPa algorithm is \(O(N^{3})\).  
The characteristic of this algorithm is that, for an unknown path of packet \(k\) at time \(t\), all known paths in the time interval \([t-\tau,t+\tau]\) will try to recover using correlation, which makes the search space of the problem expand. The setting of \(\tau\), as given in Equation (8), keeps the computational effort at a suitable level.