# A Novel Cooperative Opportunistic Routing Scheme for Underwater Sensor Networks
## 3 Opportunistic Void-Avoidance Routing Protocol
### Routing Algorithm
#### 3.5.3 Forwarding Set Selection
The construction phase is shown in Algorithm 2. Let \(C\) be the set of candidate nodes. Initially, all nodes in \(L(R_{i})\) are considered as candidates, _i.e._, \(C=L(R_{i})\). There is also a restricted candidate list (RCL), including all candidate nodes with the high PAD value in the sub-graph \(G(C)\) induced by the candidate nodes. A node \(n_{u}\in C\) is considered to have a high PAD value, if \(\mathit{PAD}_{G(C)}(n_{u})\) with respect to \(G(C)\) is at least \(\delta_{min}+\lambda(\delta_{max}-\delta_{min})\), where \(\delta_{min}=min\{\mathit{PAD}_{G(C)}(n_{u})\mid n_{u}\in C\}\) and \(\delta_{max}=max\{\mathit{PAD}_{G(C)}(n_{u})\mid n_{u}\in C\}\), and \(\lambda\) is a real parameter in the interval \([0,1]\). Among the candidate nodes in RCL, one node is randomly selected and added to the clique sub-graph under construction. Then, all nodes that are adjacent to the newly selected node will remain in the candidate list, and the rest of the nodes will be removed. This ensures that the new candidate list always includes the nodes that are adjacent to all previously selected nodes in \(\Phi\). After selecting each node and modifying the candidate list, the PAD value is calculated again for all of the remaining candidate nodes with respect to the new \(G(C)\). This procedure will continue until there is no node in the candidate list. ```
1:procedureConstruction(\(G(L(R_{i}))\), \(\lambda\), \(\Phi\) )
2: Set initial clique \(\Phi=\emptyset\)
3: Set \(C=L(R_{i})\)
4:while\(|C|>0\)do
5:\(G(C)=\) Sub-graph induced by C
6:\(\mathit{PAD}_{G(C)}(n_{u})=P_{iu}\times\beta_{iu}\times deg_{G(C)}(n_{u})\)
7:\(\delta_{min}=min\{\mathit{PAD}_{G(C)}(n_{u})\mid n_{u}\in C\}\)
8:\(\delta_{max}=max\{\mathit{PAD}_{G(C)}(n_{u})\mid n_{u}\in C\}\)
9:\(RCL=\{n_{u}\in C\mid\mathit{PAD}_{G(C)}(n_{u})\geq\delta_{min}+\lambda(\delta _{max}-\delta_{min})\}\)
10: Select \(n_{u}\) at random from the RCL
11:\(\Phi=\Phi\bigcup\{n_{u}\}\)
12:\(C=Neighbours_{C}(n_{u})\)
13:endwhile
14:endprocedure
```  
**Algorithm 2** Construction phase. By following a local search after the construction phase, each clique sub-graph is expanded by a simple exchange approach in which a node is removed from the clique sub-graph, \(\Phi\), if its removal allows two adjacent nodes out of the clique with more contribution in EPA to be included in the clique. Thus, the local search phase can enhance the EPA of each cluster. The details of the local search are described in Algorithm 3. Now, using Algorithm 4, it is shown how these procedures can be used to find a cluster with maximum EPA to forward a packet. In this pseudocode, \(maxitr\) indicates the maximum number of iterations. Increasing the number of iterations leads to exploring a better solution. In our problem, note that the adjacency graphs usually include a small number of nodes, and our heuristic approach works very well in small graphs, since iterations can be accomplished more quickly. The main factor for the complexity of this heuristic is the size of the neighbourhood and the search domain. The complexity of this randomized heuristic depends on the complexity of the heuristic and the number of vertices. Let \(n=c=|L(R_{i})|\) denote the number of vertices in the initial adjacency graph. By using a heap to store and update the vertex degrees for sparse graphs, the complexity of this class of heuristic to obtain each independent cluster is given as \(\mathcal{O}(n\log n)\)[42]. Using this approach, a cluster that can maximise EPA will be selected as the forwarding set (\(F(R_{i})\)). By utilising this approach, loss probability is decreased, and duplicate transmission paths can disappear efficiently without imposing a high cost to the system.