# Opportunistic Multipath Routing in Long-Hop Wireless Sensor Networks
## 3 Energy-Efficient Reliable Multipath Routing Protocol Using Opportunistic Routing
### Multiple Path Bifurcation Decision Process  
In this section, we describe the path bifurcation decision process to determine the number of paths. Algorithm 1 describes the pseudocode for the bifurcation decision process at an intermediate node. The process proceeds as follows: (1) predict the packet delivery ratio, (2) decide whether to perform the bifurcation, and (3) calculate the number of paths. \(P_{n}\) is the link success ratio to node \(n\), and \(k\) is the number of neighbors that are located closer to the destination compared with the intermediate node. ```
1:Input:\(P_{req}\leftarrow\) required packet delivery ratio, \(k_{i}\leftarrow\) the number of neighbors
2:Output:\(n\leftarrow\) the number of paths(default = 1)
3:
4:\(P_{(k_{i},1)}=1-(1-P_{1})(1-P_{2})...(1-P_{k_{i}})\)\(\triangleright\) link reliability by opportunistic routing
5:\(N_{hop}=\lceil\frac{Dist(i,destination)}{{{P_{exp}}}}\rceil\)\(\triangleright\) expected hop-count from itself to the destination
6:\(P_{exp}=\left(P_{(k,1)}\right)^{N_{hop}}r\)\(\triangleright\) expected packet delivery ratio
7:
8:if\(P_{exp}>P_{req}\)then\(\triangleright\) bifurcation do not require
9: return \(n\)
10:endif
11:
12:while\(P_{exp}<P_{req}\)do\(\triangleright\) bifurcation required
13:\(n=n+1\)
14:\(P_{exp}=\left(P_{(k_{i},n)}\right)^{N_{hop}}\)\(\triangleright\)\(P_{exp}\) when \(n\) of \(k_{i}\) nodes is selected by opportunistic routing
15:endwhile
16:
17:return \(n\)
```  
**Algorithm 1** Pseudocode for the bifurcation decision process at an intermediate node \(i\)  
**Step 1 (lines 4-6):** First, all nodes can measure the link quality of each other through beacon message exchange before data transmission. Each node knows the transmission cycle of beacon messages; the link quality is calculated through the number of received beacon messages from each neighbor node over some time. For example, if the transmission cycle of beacon message is 1 second  
Figure 1: An overview of the opportunistic mulitpath routing protocol. and an intermediate \(i\) receives 80 beacon messages for 100 seconds from a neighbor node \(j\), the link quality \(P_{j}\) is 80%. That is, the link quality \(P_{j}\) could be computed as follows:  
\[P_{j}=\frac{B_{recv}}{(T/T_{B})} \tag{1}\]  
where (1), \(B_{recv}\) is a number of received beacon message and \(T\) and \(T_{B}\) are simulation time and beacon duration, respectively. Based on the measurements, an intermediate node can acquire the link quality to each neighbor node and forecast the link reliability \(P_{(k_{i},1)}\) based on opportunistic routing as \(P_{(k_{i},1)}=1-(1-P_{1})(1-P_{2})\)... \((1-P_{k_{i}})\) (line 4). Let \(r\) be the radius of the radio range and \(Dist(a,b)\) be the distance from \(a\) to \(b\). The intermediate node calculates expected number of hop counts from itself to the destination \(N_{hop}\) as \(\left[Dist(itself,destination)/r\right]\) (line 5). Using the probability \(P_{(k_{i},1)}\) and the expected number of hop counts \(N_{hop}\), the intermediate node can obtain the expected packet delivery ratio (\(P_{exp}\)) given by \((P_{(k_{i},1)})^{N_{hop}}\) (line 6). **Step 2 (lines 8-10):** After predicting the packet delivery ratio, the intermediate node compares \(P_{exp}\) with the required packet delivery ratio (\(P_{req}\)). If the \(P_{exp}\) is greater than \(P_{req}\), the intermediate node decides whether path bifurcation is required and returns \(n\) (lines 8-10). **Step 3 (lines 12-17):** However, if \(P_{exp}\) is less than \(P_{req}\), the intermediate node decides that path bifurcation should be performed to improve \(P_{exp}\) (line 12). The intermediate node increases \(n\) by 1 and recalculates \(P_{exp}\) (\(P_{(k_{i},n)})^{N_{hop}}\) (lines 13-14). When the intermediate node determines the number of nodes required to satisfy the condition that \(P_{exp}\) is greater than \(P_{req}\), the intermediate node can find the number of paths, \(n\), to satisfy \(P_{req}\) and returns \(n\) (line 17).