Opportunistic Underwater Routing Protocols: A Survey

Abstract

Underwater Acoustics Sensor Networks (UASNs) play a significant role in the different underwater applications. Some underwater applications include underwater environment monitoring, mine detection, pollution monitoring, etc. UASNs exhibit several challenges like node movement, changes in link quality between nodes, low bandwidth, high bit-error rate, and high energy consumption. These challenges in UASNs make data delivery unreliable during routing. One of the solutions to achieve better performance during routing is using an opportunistic routing approach. In the opportunistic routing, the sender will forward the data to the set of neighbors so that at least a neighbor can receive and forward the data. Evaluating the neighboring nodes, selecting the set of the neighbors, and coordinating among the selected nodes to forward the received data is the significant steps in opportunistic routing. Thus, we consider the Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) approach to select the best next-hops during routing. Therefore, we are making a detailed survey on protocols that apply TOPSIS to evaluate neighboring nodes’ multiple attributes. Then we discuss various clustering techniques used in the selection of the best next-hops. Finally, we discuss methods used to compute hold time to achieve coordination between cluster nodes.

1 Introduction

The majority of the earth’s surface is covered by water. Underwater Acoustic Sensor Networks (UASNs) enable exploring underwater in the fields like underwater monitoring, detecting mining resources, underwater environment, etc. However, in the perspective of underwater networking, there are several challenges like node mobility, high energy consumption, low bandwidth, the highly dynamic link between nodes [1,2,3].

The dynamic links between nodes impact the routing performance, resulting in poor communication reliability. One of the solutions to improve communication reliability is using opportunistic routing (OR). Instead of a single next-hop forwarder node selected in traditional routing, Opportunistic routing chooses a set of neighboring nodes called candidate forwarding. Further, the packet will be forwarded to the candidate forwarding set.

In the forwarding set, nodes forward the packets in a prioritized way; upon overhearing transmission by other nodes, they suppress the forwarding of the same packet. The opportunistic routing increases the chances of delivering the packet to at least one of the next-hop present in the candidate forwarding set. Thereby OR increases the communication reliability. The nodes in the candidate forwarding set are prioritized by determining hold time. The hold time determines how long a candidate node can hold the received packet before releasing it before forwarding it. Hold time can be determined based on different criteria like depth distance with other nodes in the candidate forwarding set [4, 5].

Fig. 1

Basic flow of OR protocols

The flowchart in Fig. 1 represents the overall flow of the OR protocols. Neighboring nodes are chosen for the forwarding set based on the attribute values. The paper focuses on cluster formation and picking the optimal cluster to forward data to. The nodes coordinate by calculating the holding time for each node.

The paper is organized as follows: Sect. 2 elaborates the usage of the TOPSIS in finding the suitability of neighboring nodes, Sect. 3, elaborates existing clustering techniques in opportunistic underwater routing protocols, Sect. 4 discusses holding time calculation methods in existing OR underwater routing. The paper is concluded with the conclusion in Sect. 5.

2 Usage of Topsis in Underwater Routing

Hwang and Yoon [6] introduced a technique for multi-criteria decision making called TOPSIS. TOPSIS chooses the best alternative from many alternatives based on its similarity to the ideal solution. It selects the alternative farthest from the worst solution and nearest to the best solution. In the following subsections, we discuss the applications of the TOPSIS technique in WSNs.

2.1 Fuzzy-TOPSIS-Based Cluster Head Selection in Wireless Sensor Networks

Bilal and Young [7], proposed a cluster head selection scheme based on fuzzy TOPSIS. This scheme mainly aims to extend the network lifespan. In this scheme, some nodes are selected as cluster heads, while other nodes form the cluster members. The cluster heads collect the packets from their respective cluster members, aggregate the data and send it to the sink. The five main criteria considered to choose the cluster head are the residual energy of the node, the energy consumption rate, distance between the node and the sink, the node density and the average of distances to each neighbor.

Every sensor node broadcasts a ‘Hello’ message carrying the five attributes. All sensor nodes update their neighborhood tables after receiving the ‘hello’ packets from their neighbors. The fuzzy TOPSIS algorithm returns the rank of every node, and the node with the highest rank is selected as the cluster head. The cluster heads broadcast advertisements to their neighbors. The nodes choose to associate with the closest cluster head. Re-clustering is performed only if the threshold value is smaller than the neighbors to avoid overhead. The protocol uses a threshold-based multi-hop communication protocol.

2.2 Cluster Head Selection in Wireless Sensor Networks Under Fuzzy Environment

Azad and Sharma [8] proposed a new cluster head selection scheme based on fuzzy TOPSIS. The sensor nodes are assigned to clusters, and cluster heads are selected for every cluster. The cluster heads collect the packets from their respective cluster members using TDMA, aggregate the data and forward it to the base station. The best candidate for cluster head is the one that has the highest residual energy, the neighbor node density, and the least distance to the base station. The three criteria of a node considered are,the residual energy of the node, distance from the node to the base station and the node density.

The TOPSIS algorithm is implemented to rank the nodes. The nodes with the higher TOPSIS ranks announce themselves as cluster heads. The sensor nodes choose to associate with the closest cluster head. If the node is nearer to the base station than the cluster head, it communicates directly to the base station. The cycle of re-clustering and data transmission repeats until the death of all the nodes. The number of clusters keeps on changing along with the node density. If nodes start dying, the smaller clusters merge with the larger ones, thus reducing the number of clusters.

2.3 RODENT: A Flexible TOPSIS-Based Routing Protocol for Multi-technology Devices in WSN

Brandon and Mitton [9] proposed a new routing protocol for multi-technology networks by using a lightweight TOPSIS method. WSNs are limited by the capabilities of the Radio Access Technology used in the network. An MTN overcomes these limitations by supporting several RATs. The nodes can switch between different RATs at each hop. RODENT is mainly designed to support multiple RATs in an MTN. The RODENT protocol dynamically selects the best route and the best RAT at each hop based on the data requirement by using the TOPSIS algorithm.

RODENT accesses the link and route matrices of a node. The Link matrix consists of the attributes of every link between the node and its neighbors. A node constructs its route matrix from its link matrix and the routes received from neighboring nodes. The routing matrix contains the attributes of all the available routes of the node. The requirement vector contains the attribute weights based on the data requirements. The lightweight TOPSIS takes as input the routing matrix of a node and a requirement vector for the use case and outputs the route ranking. The top route is selected for the use case.

2.4 A Novel Approach for Smart Cities in Convergence to Wireless Sensor Networks

Jain and Rani [10], proposed a novel ring-based cross-layer routing model for the IoT in smart cities. The effectiveness of an IoT application depends on how fast the information is relayed from the sensors to the base station. This paper proposes a WSN-IoT protocol designed for real-time applications. The focus is on delivering the information with minimum delay through multi-hop routing.

Routing is performed based on the shortest path, using the TOPSIS algorithm. The nodes follow a ring system in which every node has a ring number. The base station is assumed to be located at the center of the field. The next-hop candidates must be from the next ring or within the same ring in the transmission range. At each hop, the best node is selected using the TOPSIS algorithm. The optimal node is chosen based on the four criteria: shortest distance of selected nodes from the base station, residual Energy, minimum Euclidean distance between $m$th selected node and next optimum $n$th node in the transmission range and the number of neighbors. The packet is transferred from the source node to the base station from the outermost ring nodes following the shortest path. The proposed scheme achieves a balance between energy consumption and performance.

2.5 Multi-criteria Decision-Based Path Planning for Data Collection in Fuzzy-Cluster-Based Large Sensor Networks

Sunil and Prabhat [11] propose a fuzzy-logic-based cluster head selection and TOPSIS-based path planning of the mobile sink. The nodes closest to the sink send out more data than the rest of the network and hence use up more power. The hotspot problem reduces the network’s lifetime. The mobile sink is employed to deal with this issue. Every node discovers its coordinates using localization and keeps track of its neighbors. Fuzzy logic selects the cluster head based on residual energy and the node degree. The nodes associate themselves with the closest cluster head.

The base station is uninformed of the new cluster heads. So, the mobile sink will traverse in circular paths to learn about all the cluster heads. The cluster heads send information to the mobile sink whenever they fall within the communication range. Thus, the mobile sink now has information about all the cluster heads’ residual energy, node degree, and edge cost. The mobile sink will have to decide the order in which it should visit the cluster heads, so the TOPSIS method is used to rank all the cluster heads based on the three criteria: residual energy, node degree, and edge cost. The mobile sink visits the cluster heads according to the sorted order. When the mobile sink approaches a cluster head, it broadcasts a beacon message. The cluster head will acknowledge the beacon message before sending the data it gathered.

Remarks From the Sect. 2.1 through 2.5 discussed usage of the TOPSIS for routing in wireless sensor networks (WSNs) for terrestrial applications. In the above subsections, TOPSIS selects the best neighbor by considering various attributes of neighboring nodes to forward the data. TOPSIS is not used in any of the underwater routing protocols to the best of our knowledge. Thus in the future, we can consider the usage of TOPSIS in underwater routing decision making.

3 Cluster Formation

Clustering is the process of grouping sensor nodes together to forward the received packets. One of the fundamental objectives of clustering is to eliminate duplicate data transmission by the receiving nodes and overcome the hidden-node problem [12, 13]. In the following subsections, the methods of cluster formation used in different routing protocols are discussed.

3.1 HydroCast

Noh et al. [12], proposed HydroCast, a hydraulic pressure-based anycast routing protocol. For selecting a candidate forwarding set, for a node, the Normalized Advancement (NADV) to a neighbor node n having the packet delivery probability, $p_{n}$ and the progress to the destination $d^p_{n}$, in meters, is:

$$\begin{aligned} \text {NADV}_n = d^p_{n} \times p_{n} \end{aligned}$$

(1)

Packet delivery probability, $p_{n}$, is dependent on the frequency, the distance between sender and receiver, and the size of the packet [14]. Thereafter, to form the cluster, sender S will select the neighboring node C, which has the highest NADV. The node S will identify common nodes in its own neighboring set and neighbors of C at a distance $< 0.5 \times R$, where R is the maximum communication range of the node. The highest NADV value is considered among the nodes that are not clustered. In this way, all nodes must be clustered. Finally, one among multiple clusters must be selected as a candidate forwarding set by considering the highest Expected Packet Advancement (EPA). Nodes in the Cluster$_k$ are ordered as $n_1> n_2> n_3, \cdots > n_k$, based on their priorities. The EPA of the cluster is computed by Eq. (2).

$$\begin{aligned} \text {EPA(Cluster}_k) = \sum \limits _{i=1}^k d_{n_i} P_{n_i} \prod \limits _{j=0}^{i-1} (1 - P_{n_j}) \end{aligned}$$

(2)

Another routing protocol, Geographic and opportunistic routing with Depth Adjustment-based topology control for communication Recovery over void regions (GEDAR), employs a similar cluster formation strategy [13].

3.2 Opportunistic Void Avoidance Routing (OVAR)

OVAR selects the cluster that maximizes the probability of packet delivery and packet advancement [15]. EPA is the expected advancement of each packet if a given cluster forwards it. The EPA for a cluster $\phi$ created by $R_i$ :

$$\begin{aligned} \text {EPA}(\phi _z) = \sum \limits _{k=1}^l \beta _{ik} P_{ik} \prod \limits _{y=0}^ {k-1} (1-P_{iy}) \end{aligned}$$

(3)

The forwarding node calculates the EPA for each cluster, and the cluster with the highest EPA value is chosen as the relaying set. When j nodes engage in packet forwarding, let EPA(F, j) and E(F, j) be the expected packet advancement and energy consumption of the forwarding set, respectively. By incorporating all of the nodes in the forwarding set, EPA(F, r) and E(F, r), where $r = |F|$, the highest value for EPA and energy ($\text {EPA}_{\max }$ and $E_{\max }$, respectively) may be determined. Thus, taking $\mu$ and $\rho$ as the weighting coefficients for EPA and energy, respectively, EEPA may be defined by picking j forwarding candidates from F:

$$\begin{aligned} \text {EEPA}(F, j) = \mu \frac{\text {EPA}(F, j)}{\text {EPA}_{\max }} - \rho \frac{E(F,j)}{E_{\max }} \end{aligned}$$

(4)

To obtain the highest value for EEPA, the forwarding set should be checked for different numbers of members by looking through EEPA for $j = 1,2,3, \ldots ,r$ and then selecting the set with the highest value; after that, removing other extra nodes from the forwarding set. Finally, the best set is chosen to relay the packet.

3.3 Energy-Efficient Void Avoidance Geographic Routing (EVAGR)

EVAGR is an opportunistic routing protocol that uses a similar method to select the forwarding set as discussed in the HydroCast. For a node $n_i$, its candidate set $FC_i$ is obtained from its neighboring node $N_i$. For all nodes in the candidate set FC$_i$, the link reliability (packet reception ratio) of a node $n_i$ to its neighboring node $n_j$ is determined using the following formula:

$$\begin{aligned} \text {Link}R_{ij} = \mu \frac{N_{\text {succ}}}{N_{\text {total}}} + (1-\mu )\text {Link}R_{ij} \end{aligned}$$

(5)

Normalize advance (NADV) [16] is used to choose the neighbors who are making the most progress toward the sonobuoy. The estimation of this metric is based on a proposal in the literature [16, 17]. NADV of each node $n_j$ in forwarding candidate set FC$_i$ is:

$$\begin{aligned} \text {NADV}(n_j) = \text {Link}R_{ij} \times \text {ADV}(n_j), \end{aligned}$$

(6)

where $\text {Link}R_{ij}$ is calculated in step 2 and $\text {ADV}(n_j)$ is the packet advancement measure of node $n_j$, given by:

$$\begin{aligned} \text {ADV}(n_j) = \text {Dist}(n_i, S_i) - \text {Dist}(n_j, S_j), \end{aligned}$$

(7)

wherein $\text {Dist}(a,b)$ is the Euclidean distance between two nodes a and b, with b being the sonobuoy nearest to a. The expected packet advance (EPA) of each cluster of FC$_i$ is defined using the following equation where $P_{n_k}$ is delivery probability of packets to node $n_k$ [15, 17].

$$\begin{aligned} \text {EPA}(\text {FC}_i) = \sum _{l=1}^{i} \text {NADV}(n_l)\prod _{k=0}^{n-1}(1-P_{n_k}) \end{aligned}$$

(8)

The cluster with the highest EPA calculated in the previous step is selected as the forwarding set F. If none of the nodes of F receives the packet, the packet will be resent.

3.4 Energy-Efficient Clustering Algorithm for Underwater Acoustic Sensor Networks

The paper [18] describes a solution for underwater sensor networks that uses a low-energy clustering structure. When a member node chooses a cluster to join, it takes into account the cluster head’s location, as well as energy intake and consumption between member nodes and the cluster head. The cluster head is chosen at random during the initial step of the LEACH algorithm [19]. When a cluster grows too large, the nodes at the network’s edge are separated from the cluster head and may consume significantly more energy. The energy-efficient clustering algorithm incorporates two modifications to compensate for the lack of the LEACH procedure; these are, the cluster head’s position range should be limited and a new standard for selecting the heads of member nodes has been devised. The simulation results [18] show that the proposed algorithm efficiently balances the size of the cluster and lowers the network’s energy usage.

4 Holding Time Computation

Holding time is the time for which the receiving node needs to wait before forwarding the packet. When a candidate node successfully transmits a packet, neighboring nodes overhear the packet and stop the transmission of the same packet. This mechanism contributes to the elimination of duplicate packets and overcrowding.

4.1 HydroCast

HydroCast uses distance-based prioritization [12]. When a node receives the packet, the node sets its timer to have a similar approach, but it requires information regarding two-hop connectivity and its distance from neighboring nodes [12]. The calculation of holding time is done by using a linear function which is directly dependent on the distance of the node from the sender node. The timer function for the receiving node x is considered as follows:

$$\begin{aligned} f(d^P_x) = \alpha (R - d^P_x) \end{aligned}$$

(9)

Where R is the transmission range, and $d^P_x$ is the progress toward the surface for the given node x. Equation (9) ensures that the node having higher depth progress must have lower hold time. Thus $\alpha$ must guarantee that nodes in the vicinity of the high priority node must overhear the transmission of the packet. The $\alpha$ is given as

$$\begin{aligned} \alpha > \frac{t_{ci}-t_{cj}+t_{ij}+t_{\text {ack}}}{d^P_i-d^P_i} \end{aligned}$$

(10)

where $t_{\text {ack}}$ is the ack transmission delay and the other term is to cover propagation delay over the distance $d_{ic}-d_{jc}+d_{ij}$ where i, j, and c are the nodes.

4.2 Geographic and Opportunistic Routing with Depth Adjustment-Based Topology Control for Communication Recovery (GEDAR)

In the paper GEDAR [13], they maintain a list of the candidate forwarding nodes. Each node sets itself a timer for when the node will be forwarding the data. Based on the priority, the holding time is set as:

$$\begin{aligned} T^i_w = T_p + \sum _{k=1}^{i} \frac{D(n_k, n_{k+1})}{s} + i * T_{\text {proc}} \end{aligned}$$

(11)

where, s is speed of sound underwater, $T_{\text {proc}}$ is the packet processing time, $T_p$ is the remaining propagation time given as,

$$\begin{aligned} T_p = \frac{(R_c) - D(n_a, n_b)}{s} \end{aligned}$$

(12)

where $n_a$ is current node, and $n_b$ is the node which broadcasts the packet. The summation in the holding time equation provides the propagation delay for all the high priority nodes.

4.3 Inherently Void-Aware Routing (IVAR)

Inherently Void Avoidance Routing Protocol [20] uses equation (13) to schedule forwarding of the received packet.

$$\begin{aligned} T_{\text {hold}} = \frac{1}{2}(1-\alpha )T_{\text {Delay}} + \frac{R - \mid \textbf{SC} \mid }{v_{\text {sound}}} \end{aligned}$$

(13)

where $T_{\text {Delay}}$ is the predefined delay, $\alpha$ is the fitness factor, which is nothing but normalized depth difference between sender and receiver, and given in the Eq. (14), $\mid \textbf{SC}\mid$ is the distance between sender and receiving candidate node, R communication range and $v_{\text {sound}}$ is the speed of the sound in the water.

$$\begin{aligned} \alpha = \frac{D_s - D_r}{R}, H_s > H_r, \alpha \in [-1,1] \end{aligned}$$

(14)

In Eq. (14), $D_s$ and $D_r$ are the depth of the sender and receiver, respectively.

Opportunistic void avoidance routing (OVAR) [15] is another routing protocol which uses the same equations (13) and (14).

4.4 Distance-Vector Based Opportunistic Routing (DVOR)

Distance-Vector based Opportunistic Routing for Underwater Acoustic Sensor Networks [21], in this paper, the nodes have a waiting time that is used to solve the problem of multiple nodes receiving the packet and attempting to forward it. The waiting time is given as follows:

$$\begin{aligned} t = 2*[N_i-n_p+2]^{+} * t_0 + \text {rand}(0, \text {CW})*t_{\text {slot}}*[N_i-n_p+2]^{+} \end{aligned}$$

(15)

where $t_0$ is the propagation time for the maximum transmission range, CW being the size of backoff window, unit time for backoff, and the $[.]^{+}$ is for max(.,0) meaning only positive values. The equation is divided into two parts: the first deals with different hop count in the link, and the second considers using a backoff mechanism to overcome forwarding nodes with the same hop count. Table 1 compares various underwater protocols in terms of type of the protocol in terms of sender or receiver-based, parameters used in the holding time computation , and state.

Remarks In this section, holding time computation methods for various opportunistic underwater routing protocols are discussed. Holding time is used to coordinate the data forwarding among multiple nodes of a cluster. Hold time is potential in suppression of transmission of duplicate packets. All the above-explained holding time computations require identifying the distance between the nodes in the cluster or identifying the hop-count. However, finding distance among nodes or hop-count of nodes increases the complexity of finding holding time. Thus, by considering maximum communication range or based on the priority of nodes, hold time can be computed.

Table 1 Comparison of various opportunistic underwater routing protocols

5 Conclusion

In this paper, we discussed the usage of the TOPSIS in routing for wireless sensor networks and found that it has not been used to select the forwarding nodes in underwater networks. Further, elaborated about clustering approaches are used in opportunistic underwater routing protocols. Existing clustering approaches require clustering of all neighboring nodes, which requires increases the computation complexity. This can be overcome by clustering only the required number of nodes. In last, we analyzed the holding time computations used in various opportunistic underwater routing protocols. Further, there is a scope to simplify hold time computation by eliminating the need to find the distance among nodes in the cluster.