# Lightweight Path Recovery in IPv6 Internet-of-Things Systems
## 4 Design of LiPa
### Path Correlation Inference  
The core operation of path recovery lies in the correlation inference of paths. The question we want to answer is whether two paths are correlated? What kind of correlations exists? How can we use such a correlation to recover an unknown path? Algorithm 1 answers these questions above. For a packet \(i\) whose path is unknown and a packet \(k\) whose path is known already, the algorithm examines whether a correlation exists between the two paths. If it does, it uses the \(path(k)\) of packet \(k\) to recover the \(path(i)\) of packet \(i\). The different correlations and the corresponding methods of path recovery are summarized in the following cases. The following examples will describe different correlation and path recovery methods. **Case 1**: When \(len(i)\) of packet \(i\) is two hops longer than \(len(k)\) of packet \(k\), the sink will check whether the grandpa node \(g(i)\) of packet \(i\) is the source node \(o(k)\) of packet \(k\). If it is, \(path(i)\) is the combination of \(o(i)\), \(p(i)\), and \(path(k)\). To avoid the error of \(path(k)\) making the \(path(i)\) is also recovered incorrectly, it is necessary to evaluate whether the hash value \(h(i)\) is equal to \(hash(o(i),p(i),path(k))\). This recovery path can be assigned to \(path(i)\) if equal. The example is given in Figure 5a: In a collection cycle, node \(K\) generates packet \(K1\), and node \(A\) generates packet \(A1\). Since \(K\) is the grandpa node of \(A\), \(path(K1)\) with path \((K,G,H,I)\) can be used to recover \(path(A1)\), i.e., \(path(A1)=(A,B,K,G,H,I)\). **Case 2**: When \(len(i)\) is one hop longer than \(len(k)\), the sink will determine whether \(p(i)\) is equal to \(o(k)\). If so, \(path(i)\) is the combination of \(o(i)\) and \(path(k)\). Similarly, once \(h(i)\) is equal to \(hash(o(i),path(k))\), this recovery path can be assigned to \(path(i)\). The example is given in Figure 5b: In a collection cycle, node \(K\) generates packet \(K1\), and node \(B\) generates packet \(B2\). Since \(K\) is the parent node of \(B\), \(path(K1)\) with path \((K,G,H,I)\) can be used to recover \(path(B2)\), i.e., \(path(B2)=(B,K,G,H,I)\). ```
1:\(k\): a packet whose path has been recovered;
2:\(i\): a packet whose path is unknown;
3:\(\mathit{True}\) or False: whether packet \(k\) can be used to recover the path of packet \(i\);
4:if\(len(i)-len(k)\
otin\{2,1,0,-1\}\)then
5:return\(False\)
6:endif
7:if\(len(i)-len(k)\equiv 2\)then
8:if\(g(i)\equiv o(k)\)and\(h(i)\equiv\mathit{hash}(o(i),p(i),\mathit{path}(k))\)then
9:\(path(i)\leftarrow(o(i),p(i),path(k))\) //Case 1
10:return\(\mathit{True}\)
11:endif
12:endif
13:if\(g(i)\equiv o(k)\)and\(h(i)\equiv\mathit{hash}(o(i),p(i),\mathit{path}(k))\)then
14:\(path(i)\leftarrow(o(i),path(k))\) //Case 2
15:return\(\mathit{True}\)
16:else
17:if\(g(i)\equiv p(k)\)and\(h(i)\equiv\mathit{hash}(o(i),p(i),\mathit{path}(k)-o(k))\)then
18:\(path(i)\leftarrow(o(i),p(i),\mathit{path}(k)-o(k))\) //Case 3
19:return\(\mathit{True}\)
20:endif
21:else
22:if\(len(i)-len(k)\equiv 0\)then
23:if\(p(i)\equiv p(k)\)and\(h(i)\equiv\mathit{hash}(o(i),p(i),\mathit{path}(k)-o(k))\)then
24:\(path(i)\leftarrow(o(i),p(i),\mathit{path}(k)-o(k))\) //Case 4
25:return\(\mathit{True}\)
26:else
27:if\(g(i)\equiv g(k)\)and\(h(i)\equiv\mathit{hash}(o(i),p(i),\mathit{path}(k)-o(k)-p(k))\)then
28:\(path(i)\leftarrow(o(i),p(i),\mathit{path}(k)-o(k)-p(k))\) //Case 5
29:return\(\mathit{True}\)
30:endif
31:else //\(len(i)-len(k)\equiv-1\)
32:if\(p(i)\equiv g(k)\)and\(h(i)\equiv\mathit{hash}(o(i),p(i),\mathit{path}(k)-o(k)-p(k))\)then
33:\(path(i)\leftarrow(o(i),p(i),\mathit{path}(k)-o(k)-p(k))\) //Case 6
34:return\(\mathit{True}\)
35:endif
36:endif
37:return\(False\)
```  
**Algorithm 1** The Recovery Core Algorithm. **Case 3**: When \(len(i)\) is one hop longer than \(len(k)\), there is another possibility that \(g(i)\) is equal to \(p(k)\). In this case, \(path(i)\) is the combination of \(o(i)\), \(p(i)\), and the part of \(path(k)\) that removes \(o(k)\).