# 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 main idea here is to take advantage of a group of relay nodes, which can simultaneously maximise packet advancement and packet delivery probability. First, we define the expected packet advancement (EPA) to estimate the advancement of each packet that is relayed by a set of nodes. Let \(\Phi=\{m_{1},m_{2},...,m_{l}\}\), \(1\leq l\leq c\), a subset of nodes with no hidden node, which are decreasingly ordered based on the value of \(\beta\) presented in Equation (8). We propose EPA for the subset \(\Phi\), created by forwarding node \(R_{i}\) as follows:  
\[\mathit{EPA}(\Phi)=\sum_{k=1}^{l}\beta_{ik}P_{ik}\prod_{y=0}^{k-1}\overline{ P}_{iy} \tag{9}\]where \(\overline{P}_{iy}=1-P_{iy}\), \(P_{i0}=0\) and \(\beta_{ik}\) is the normalised fitness factor, which is calculated based on the relative depth difference between the node \(R_{i}\) and each candidate node \(m_{k}\) using Equation (8). Now, we aim to extract a forwarding set with maximum EPA from the adjacency graph, which excludes any hidden node. In the first step of OVAR execution, each forwarding node, \(R_{i}\), constitutes its adjacency graph \(G(L(R_{i}))\) with the aid of information provided by beaconing, e.g., the adjacency graph in Figure 3, where the yellow lines show the existence of direct connections between pairs of nodes. In order to remove the possibility of having hidden nodes in a forwarding set, the forwarding node extracts a clique sub-graph from \(G(L(R_{i}))\) with the best EPA to forward the packet. Finding a clique of maximum cardinality in an adjacency graph is an NP-hard problem [40]. Some solutions, exact or heuristic-based, have already been proposed in the literature to address the maximum clique problem. However, every solution comes with some limitations or weaknesses. For instance, an exact solution may deteriorate the performance in order to obtain high accuracy or a heuristic approach may find a local optimum, which is far from a global optimum. The authors in [41] proposed a greedy randomized adaptive search procedure (GRASP) for the maximum clique problem, which can obtain an acceptable solution in a limited amount of time. Based on this approach, we apply a heuristic that is computationally efficient to extract a clique sub-graph from \(G(L(R_{i}))\) with maximum expected packet advancement. In this way, a greedy randomised search in an iterative manner is performed to find an acceptable solution among the local optimal solutions. The randomisation contributes to generating different solutions in each local search. The greediness of this approach leads to the quick convergence to a local minimum, which decreases the search time in each iteration. The proposed heuristic includes two phases of construction and local search. Before explaining each phase, it should be noted which criteria are used as a guide for construction. We introduce the probability advance density (PAD) as a metric in each local greedy search, which satisfies all conditions to obtain a better result. Let \(C\) be a subset of \(L(R_{i})\) in which the induced graph \(G(C)\) is complete. If \(deg_{G(C)}(n_{u})\) is the degree of \(n_{u}\in C\) with respect to \(G(C)\), the PAD of node \(n_{u}\) can be calculated as follows:  
\[PAD_{G(C)}(n_{u})=P_{iu}\times\beta_{iu}\times deg_{G(C)}(n_{u}) \tag{10}\]  
where \(P_{iu}\) and \(\beta_{iu}\) are the packet delivery probability and packet advancement between node \(R_{i}\) and \(n_{u}\), respectively. If a candidate node can maximise this value, this means that it is located in an ideal position in terms of packet delivery and packet advancement and also high connectivity with the rest of the candidate nodes. In the construction phase, at each step, a node is randomly selected from the candidate nodes with a high PAD value, and other nodes that have no connection to the selected nodes, are removed  
Figure 3: An example of an adjacency graph in a 3D environment. from the candidate list. Thus, at each step, we will have a clique sub-graph on hand.