A better-performing Q-learning game-theoretic distributed routing for underwater wireless sensor networks

Abstract

Underwater sensor networks have recently emerged as a promising networking technique for various underwater applications. However, the acoustic routing of underwater sensor networks in the aquatic environment presents challenges in terms of dynamic structure, high rates of energy consumption, long propagation delay, and narrow bandwidth. Therefore, it is difficult to adapt traditional routing protocols, which are known to be reliable in terrestrial wireless networks. In this study, we focus on the development of novel routing algorithms to tackle acoustic transmission problems in underwater sensor networks. The proposed scheme is based on reinforcement learning and game theory and is designed as a routing game model to provide an effective packet-forwarding mechanism. In particular, our Q-learning game paradigm captures the dynamics of the underwater sensor networks system in a decentralized, distributed manner. The results of a performance simulation analysis show that the proposed scheme can outperform existing schemes while displaying balanced system performance in terms of energy efficiency and underwater sensor networks throughput.

Introduction

Over 70% of the earth is covered with water in the form of rivers, canals, seas, and oceans. Therefore, underwater acoustic transmission has recently attracted much attention because of its significant abilities in distributed tactical surveillance, disaster prevention, mine reconnaissance, and environmental monitoring. Recent advances in communication technologies have led to the development of underwater sensor networks (USNs). Based on technologies that enable underwater exploration, USNs consist of sink nodes and autonomous micromechanical sensors. In USNs, spatially distributed sensors record water-related information; the sensors are connected wirelessly through acoustic signals in the underwater environment. Sink nodes on the surface collect data from the underwater sensors and transmit this information to a monitoring center via satellite for further analysis.^1–3

Routing is a fundamental issue in any network. In wireless sensor networks, routing protocols play an important role in the efficient transmission of data from the source to destination nodes. In general, network performance is strongly related to the routing algorithm; therefore, considerable efforts have been made to find adaptive network routing protocols. Ground-based terrestrial sensor networks have been comprehensively investigated, and numerous communication protocols have been proposed for such networks.^4–6 Although there are broad similarities between USNs and terrestrial sensor networks, certain characteristics of USNs mean that traditional routing concepts cannot be applied directly to the design of USN routing algorithms. To develop an effective USN routing algorithm, the high absorption factor, long propagation delay, limited bandwidth, and high bit-error ratio of the aquatic environment must be taken into account. ²

Existing routing algorithms can be classified according to their design objectives and routing scenarios. For instance, an algorithm may operate in either a static offline or dynamic online manner. In addition, operational methods can be classed as centralized or distributed paradigms. In general, it is not practical to use a centralized controller in large-scale sensor networks. Moreover, static algorithms cannot significantly improve USN performance under dynamically changing acoustic environments. Control decisions must be made in real time without any knowledge of future information. Based on these considerations, distributed and dynamic routing methodologies are best suited to large-scale USN operations.^6,7

The aim of this article is to propose a new routing scheme for USNs by addressing various issues concerning the harsh underwater environment, most notably the energy efficiency, long propagation delay, dynamic topology changes, and node localization of aquatic operations. To overcome these issues, the proposed algorithm must balance the overall USN performance. In addition, for real-world USN applications, we focus on design principles such as feasibility, self-adaptability, and effectiveness in providing a desirable routing solution. Although several USN routing schemes have been proposed, no systematic routing study based on an integrated approach has been conducted. Existing research indicates that this is an extremely challenging issue.

In this study, we adopt game-theoretic learning algorithm to handle point-to-point routing decisions. Usually, game theory considers independent decision-making players who are attempting to reach a joint decision that is acceptable to all players under a given conflict/cooperation environment. In the proposed scheme, each sensor node is assumed to be a game player who makes routing decisions in a distributed online manner to adapt to the highly dynamic USN changes.

The main concept behind the proposed game is the extension of the well-known Markov decision problem to the multiplayer routing game model. To select the best strategy, each player in our game learns the routing environment according to a reinforcement learning algorithm. In particular, we demonstrate that insights from game theory can be used to derive a distributed Q-learning algorithm. In general, learning can be defined as the ability to make intelligent decisions by taking into account the past and present system states. ⁷

This article makes the following contributions: (1) we develop a novel routing scheme for USNs; (2) we integrate game theory and the Q-learning algorithm to handle routing decisions; (3) we adopt a distributed online approach to implement self-adaptability and real-time effectiveness; (4) we design a routing algorithm that balances contradictory requirements; and (5) the probabilities for routing decisions are initially determined based on the current USN condition. The significance of our proposed scheme lies in its responsiveness to current USN system conditions while considering the dynamic underwater environment. To the best of our knowledge, there has been very little research on game-based distributed learning algorithms for USN routing problems.

The remainder of this article is organized as follows: In the next section, we review some related routing schemes and their problems. Then, we define the routing game model and Q-learning mechanism implemented in this study before providing a detailed description of the proposed USN routing algorithms. In particular, this section provides fresh insights into the benefits and design of a learning game-based routing approach. For convenience, the main steps of the proposed scheme are then listed before we validate the performance of the proposed scheme by means of a comparison with some existing methods. Finally, we present our conclusion and discuss ideas for future work.

Related work

There has been considerable research into the design of USN routing protocols. The energy-efficient depth-based routing (EEDBR) scheme ³ performs energy balancing and reduces the number of sensor node transmissions in order to enhance the network. In this scheme, packets are transmitted between a sensor node and a sink by selected nodes. The selection of the nodes is based on depth and residual energy. The EEDBR scheme consists of two phases: knowledge acquisition and forwarding. During the knowledge acquisition phase, the sensor node shares depth and residual energy information with each of its neighbors. During the forwarding phase, the sender includes a list of forwarding nodes based on depth and residual energy. Unfortunately, some unnecessary forwarding means that the stability period of this scheme is short-lived and there is a high load on low-depth nodes.^2,3

Depth-based routing (DBR) is a novel protocol for transmitting packets toward the sink. ⁸ Based on the depth information of each sensor, the DBR scheme forwards data packets greedily toward the water surface. Each data packet contains a field that records the depth information of its most recent forwarder, which is updated at every hop. On receiving a packet, the node checks whether its depth is less than that of the previous forwarder; if so, it forwards the packet; otherwise, it discards the packet. If there are multiple data sinks deployed at the water surface, DBR can naturally take advantage of them. The main advantages of the DBR scheme are as follows: (1) it does not require full-dimensional location information, (2) it can handle dynamic networks with high energy efficiency, and (3) it can take advantage of the multiple-sink network architecture without incurring additional overheads. ⁸

The cooperative depth-based routing (CoDBR) scheme ⁹ is a unique routing protocol for mission-critical applications. In this scheme, all nodes exchange depth information when the network is initialized. The source node registers its neighbors in a list. Relay nodes are selected based on the minimum-depth neighbors in the list, and data are transmitted through the established path to the sink. Cooperation is employed at the network layer, thus increasing the reliability and throughput of the network. In CoDBR, this high reliability and improved throughput is achieved at the cost of high end-to-end delay.^2,9

The data gathering–based node coordination (DGNC) scheme ¹⁰ focuses on sparsely distributed USNs and a path-controllable autonomous underwater vehicle (AUV), with no time synchronization between the two. The DGNC scheme prolongs the lifetime of a sensor network using the AUV’s mobility to achieve the shortest wake-up time in the sensor nodes. In this scheme, the concept of received signal strength power control is used to modify the transmission power, which increases the communication reliability and decreases energy consumption. The DGNC scheme operates in two phases: connection and data transmission. Furthermore, the signal strength and signal-to-noise ratio (SNR) information provided by the acoustic modem can be used to apply adaptive power control during the transmission of data packets, thus conserving energy by obtaining a preferred communication position between the AUV and the sensor nodes.^2,10

In the cooperative best relay assessment (COBRA) scheme, ¹¹ a new best relay selection criterion is employed to minimize the one-way packet transmission (OPT) time, which is defined as the packet transmission time plus propagation delays. The COBRA criterion can take both the propagation delay and the channel state of every potential relay into account, enabling the overall OPT time to be minimized when the total power and outage probability limitations are satisfied. A best relay selection algorithm has been proposed based on the COBRA criterion. This algorithm requires only statistical information about the channel, rather than the instantaneous channel state. The COBRA scheme achieves improved results in terms of network throughput and delivery ratio but incurs high energy consumption.^2,11

The void-aware pressure routing (VAPR) scheme ¹² for USNs is an efficient anycast routing protocol for underwater data collection. In particular, the VAPR scheme uses surface reachability information to establish each node’s next-hop direction while taking advantage of geo-opportunistic forwarding. This approach is very robust to network dynamics such as node mobility and failure. The VAPR scheme does not require any additional recovery path maintenance and is not affected by the hop stretch caused by recovery fallbacks in existing solutions. Instead, the VAPR scheme exploits periodic beaconing to build directional trails toward the surface and features greedy, opportunistic directional forwarding for packet delivery. ¹²

The geographic and opportunistic routing with depth adjustment–based topology control for communication recovery over void regions (GDAR) scheme ¹³ is an anycast, geographic, and opportunistic routing protocol that routes data packets from sensor nodes to multiple sinks at the sea surface. The GDAR scheme uses location information of neighbor nodes and certain known sinks to select a next-hop forwarder set of neighbors to continue forwarding the packet toward the destination. To avoid unnecessary transmissions, low-priority nodes suppress their transmissions whenever they detect that the same packet has been sent by a high-priority node. When a node is in a communication void, the GDAR scheme switches to the recovery mode. This mode employs topological control by adjusting the depth of the void nodes, unlike traditional approaches that use control messages to discover and maintain routing paths along void regions. Therefore, the most significant aspect of the GDAR is its novel void node recovery methodology. ¹³

The energy-efficient and lifetime-aware routing (ELAR) scheme ¹⁴ is an innovative distributed routing protocol for USNs. In this scheme, the nodes learn the environment in order to take optimal actions and gradually improve the performance of the entire network. The ELAR scheme can easily be tuned to trade latency or energy efficiency for an extended lifetime and can thus be used in various applications. The major contributions of the ELAR scheme are (1) applying the Q-learning technique in a distributed routing protocol for USNs, (2) balancing the workload among sensor nodes for a longer network lifetime, (3) reducing the networking overhead for higher energy efficiency, and (4) learning the environment effectively to improve adaptability in dynamic networks. ¹⁴

The work by Sandeep and Kumar ¹⁵ provides a broad view of existing algorithms of clustering, coverage, and connectivity based on acoustic communication. This article also provides a useful guidance to the researchers in USNs from various other communication techniques’ perspective. Albarakati et al. ¹⁶ develop a set of underwater embedded system architectures that can handle different network configurations. The idea is to have dynamic architecture that will be configured based on network parameters to achieve best performance in terms of end-to-end delay and power consumption. Finally, an architecture is selected to match a given set of requirements including data rate, processing node capabilities, gathering nodes capabilities, and water depth. In Azam et al., ¹⁷ a new balanced load distribution scheme is proposed to avoid energy holes created due to unbalanced energy consumption in USNs. This scheme is specifically designed to solve the energy hole problem when a node does not find a forwarder node in the next corona to reach the sink.

Some earlier studies^12–14 have attracted considerable attention while introducing unique challenges in handling the USN routing problems. In this article, we demonstrate that our proposed scheme significantly outperforms these existing schemes. Table 1 lists the advantages and disadvantages of the existing approaches.

Table 1.

Advantages and disadvantages of existing schemes.^2,3,8–14

Protocols	Advantages	Disadvantages
EEDBR scheme 3	Based on depth and residual energy; localization-free protocolMinimizes energy consumption and end-to-end delaySending-based forwarding	High load on intermediate nodesDelivery ratio decreased
DBR scheme 8	Receiving-based forwarding; high packet receiving ratioDepth, broadcasting nature	Unbalanced energy consumptionHigh load on low-depth nodes
CoDBR scheme 9	Reliability and throughput efficiency; cooperative routingBased on depth; localization-free protocol	Unbalanced energy consumption and greater end-to-end delay
DGNC scheme 10	Sensor nodes, AUV, node coordination schemeCommunication reliability; reduced energy consumption	Possibility of missing beacon message by sensor node from AUV in sleeping mode, leading to failure of data transmission
COBRA scheme 11	Improved reliability and throughputConsiders statistical properties of channel	Network density decreases rapidly because of cooperative routing by not considering residual energy of nodes
VAPR scheme 12	Efficient anycast routing protocol for data collectionSimple opportunistic directional forwarding mechanism	High load on intermediate nodes in the network
GDAR scheme 13	Avoids unnecessary transmissionsEffectively avoids void regions	Requires location information, which is an overhead
ELAR scheme 14	Energy efficiency for lifetime.Applies the Q-learning technique in a distributed routing protocol.	Slight computational overhead

EEDBR: energy-efficient depth-based routing; DBR: depth-based routing; CoDBR: cooperative depth-based routing; DGNC: data gathering–based node coordination; COBRA: cooperative best relay assessment; VAPR: void-aware pressure routing; GDAR: geographic and opportunistic routing with depth adjustment–based topology control for communication recovery over void regions; ELAR: energy-efficient and lifetime-aware routing.

Routing game model and Q-learning mechanism

In this section, we provide a brief introduction to the game theory model and general reinforcement learning mechanism, which form the theoretical basis of the proposed USN routing scheme. By adopting the Q-learning-based routing game, our scheme designs an anycast, opportunistic routing protocol to deliver packets from a sensor node to the sink node.

Routing game model

During the operation of a USN system, the sensor nodes make individual routing decisions by considering the end-to-end delay, hop count, packet error rate, and energy efficiency. Under dynamic acoustic conditions, the sensor nodes attempt to maximize their own profit in a distributed online manner based on the learning approach. In this study, we assume that the sensor nodes are game players that make rational routing decisions. Based on this assumption, we develop a new game model, known as the routing game, for the USN system. Formally, we define the routing game model $\mathbb{G}=\{\mathbb{N},{\mathbb{A}}_{i,1\le i\le n},U_{i,1\le i\le n},{\mathbb{U}}_{i,1\le i\le n}\left[m\right],{\mathbb{S}}_{i,1\le i\le n},T\}$ at each time period $t$ of gameplay:

• $\mathbb{N}$ is the finite set of game players $\mathbb{N}=\{{\delta }_1,\dots ,{\delta }_i,\dots ,{\delta }_n\}$ , where ${\delta }_i$ is the ith sensor node and n is the number of sensors.

• ${\mathbb{A}}_i=\{a_i^1,a_i^2,\dots ,a_i^m\}$ is the finite set of available actions of ${\delta }_i$ , where $a_i^m$ represents the selection of the mth neighboring node to relay the routing packet; $m$ is the total number of neighbors.

• $U_{i,1\le i\le n}$ is the payoff received by ${\delta }_i$ .

• The array ${\mathbb{U}}_i[m]=[{\mathcal{U}}_i^1,{\mathcal{U}}_i^2,\dots ,{\mathcal{U}}_i^m]$ is the payoff history of ${\delta }_i$ ; ${\mathcal{U}}_i^m$ represents the accumulated payoff of strategy $a_i^m$ . ${\mathbb{U}}_i[·]$ is used to estimate the strategy selection probabilities.

• ${\mathbb{S}}_i=\{s_i^1,s_i^2,\dots ,s_i^m\}$ is the set of states in ${\delta }_i$ . The definition of system states is related to routing strategies. If ${\delta }_i$ takes action $a_i^m$ , then the next state of ${\delta }_i$ is $s_i^m$ .

• $T=\{0,1,\dots ,t,t+1,\dots \}$ denotes time, which is represented by a sequence of time steps with imperfect information.

Reinforcement learning mechanism

Reinforcement learning concerns how system agents should take actions to maximize their reward. Reinforcement learning algorithms establish a balance between the exploration of uncharted territory and the exploitation of current knowledge based on online performance. In game theory, reinforcement learning is used to explain how an effective solution may arise under bounded rationality. Therefore, there has been growing interest in research incorporating game theory and learning algorithms. Game theoretic learning algorithm has become an increasingly important area of research in recent years.^7,14,18

The environment is typically formulated as a Markov decision process (MDP), which is, therefore, the basic concept of reinforcement learning. The MDP is a mathematical framework for modeling the decision-making process and is useful for optimization problems that are solved via learning algorithms.^14,18 In the current scenario, the MDP consists of the set of states ( $\mathbb{S}$ ), set of actions ( $\mathbb{A}$ ), state transition probabilities ( $\mathit{P}$ ), and rewards ( $\mathcal{R}$ ). $\mathit{P}$ is composed of elements $P_{s\to s\prime }^a$ , which are the probabilities of moving to state $s\prime$ from state $s$ (i.e. $s\prime$ , $s\in \mathbb{S}$ ) with a given action $a\in \mathbb{A}$ . $\mathcal{R}(s,a)$ is the reward for taking action $a$ from state $s$ . Mathematically, at time $t$ , $P_{s\to s\prime }^a$ and $\mathcal{R}(s,a)$ are defined as follows ¹⁴

$$\{\begin{array}{c}{P}_{s\to s\prime }^a=\mathrm{Pr}\{S_{t+1}=S\prime {|}_{s=s_t,a=a_t}\},\mathrm{s}.\mathrm{t}.,\sum _{s\prime \in S}{P}_{s\to s\prime }^a=1\hfill \\ \multicolumn{1}{c}{\mathcal{R}(s,a)=\left\{{\mathcal{R}}_t(s_t,a_t){|}_{s=s_t,a=a_t}\right\}=\sum _{s_{t+1}\in S}(P_{s_t\to s_{t+1}}^{a_t}\times {\mathcal{R}}_{s_t\to s_{t+1}}^{a_t})}\end{array}$$

(1)

where $s_t$ and $a_t$ denote the state and action at time $t$ , respectively. ${\mathcal{R}}_{s\to s\prime }^a$ is the reward expected for taking action $a$ at state s and entering the next state $s\prime$ . In the reinforcement learning algorithm, a policy $\psi$ is mapped from each state $s\in \mathbb{S}$ and action $a\in \mathbb{A}(s)$ to the probability $\psi (s,a)$ of taking action a when in state $s$ . The expected reward $(V^{\psi }(s))$ in state $s$ under policy $\psi$ is received after taking an action according to policy $\psi$ at time t and for following policy $\psi$ thereafter. $V^{\psi }(s)$ is defined as ¹⁴

$$\begin{array}{l}{V}^{\psi }\left(s\right)=E_{\psi }\left\{{ℛ}_t\left(s_t,a_t\right)\right\}\\ =E_{\psi }\left\{{\displaystyle \sum _{k=0}^{\infty }\left({\gamma }^k\times {ℛ}_{t+k}\left(s_{t+k},a_{t+k}\right)\right)}\right\},\mathrm{s}.\mathrm{t}.,\gamma \in [0,1)\end{array}$$

(2)

where $\gamma$ is a control factor that discounts the rewards in the future. Based on Bellman’s principle of optimality, equation (2) can be rewritten as a recursive equation

$$\begin{array}{c}\multicolumn{1}{c}{V^{*}\left(s\right)=\underset{\psi }{\mathbf{max}}{V}^{\psi }\left(s\right)=\underset{\psi }{\mathbf{max}}{E}_{\psi }\left\{\sum _{k=0}^{\infty }({\gamma }^k\times {\mathcal{R}}_{t+k}(s_{t+k},a_{t+k}))\right\}}\\ =\underset{\psi }{\mathbf{max}}{E}_{\psi }\{{\mathcal{R}}_t(s_t,a_t)+\sum _{k=1}^{\infty }({\gamma }^k\times {\mathcal{R}}_{t+k}(s_{t+k},a_{t+k}))\}\hfill \\ =\underset{a}{\mathbf{max}}[{\mathcal{R}}_t(s_t,a_t)+(\gamma \times \left(\sum _{s_{t+1}\in S}\left((P_{s_t\to s_{t+1}}^{a_t}\times V^{*}(S_{t+1})\right)\right))]\hfill \end{array}$$

(3)

To solve equation (3), reinforcement learning algorithms can be used. In this study, we adopt a well-known reinforcement learning technique called Q-learning. Q-learning works by successively improving its evaluations of the quality of particular actions at particular states. In addition, Q-learning provides agents with the ability to learn to act optimally in Markovian domains by experiencing the consequences of their actions but does not require the agents to build maps of the domains.^14,18 In the Q-learning algorithm, the value of state–action pairs is given by $Q^{\psi }(s,a)$ , which is the value of taking action $a$ in state $s$ under policy $\psi$ . This is defined as

$$\begin{array}{c}{Q}^{\psi }(s,a)=E_{\psi }\left\{\sum _{k=0}^{\infty }({\gamma }^k\times {\mathcal{R}}_{t+k}(s_{t+k},a_{t+k}))\right\}\hfill \\ =({\mathcal{R}}_t(s_t,a_t)+\gamma \times \left(\sum _{s_{t+1}\in S}\left((P_{s_t\to s_{t+1}}^{a_t}\times V^{*}(S_{t+1})\right)\right))\hfill \end{array}$$

(4)

According to equations (3) and (4), we can compute $V^{*}(s)$ as^14,18

$$\begin{array}{c}\multicolumn{1}{c}{V^{*}\left(s\right)=\underset{a}{\mathbf{max}}{Q}^{*}(s,a)=\underset{a}{\mathbf{max}}{Q}^{*}(s_t,a_t)}\\ =\underset{a_t}{\mathbf{max}}[{\mathcal{R}}_t(s_t,a_t)+\gamma \times \left(\sum _{s_{t+1}\in S}\left((P_{s_t\to s_{t+1}}^{a_t}\times \underset{a}{\mathbf{max}}{Q}^{*}(S_{t+1},a))\right)\right)]\hfill \end{array}$$

(5)

In equation (5), $Q^{*}(s_t,a_t)$ can be approximated as ¹⁴

$$Q^{\ast }\left(s_t,a_t\right)\cong \underset{t\to \infty }{\lim }\left[\left\{\left(1-\beta \right)\times Q\left(s_t,a_t\right)\right\}+\left(\beta \times \left({ℛ}_t\left(s_t,a_t\right)+\left\{\gamma \times \underset{a}{max}Q\left(s_{t+1},a\right)\right\}\right)\right)\right],\mathrm{s}.\mathrm{t}.,\beta \in (0,1]$$

(6)

where $\beta$ is a learning rate that models how the Q values are updated. The advantage of Q-learning is that it simply calculates the Q values of all actions based on the system model to update $V$ , which is less computationally demanding.^14,18 However, conventional Q-learning has the limitation that the reinforcement learning process is very slow.

Proposed USN routing scheme

In this section, the proposed USN routing scheme is explained in detail. The scheme consists of configuration and routing algorithms. The configuration algorithm effectively forms the network topology based on the current network condition by considering the distance and energy status. The routing algorithm establishes the one-hop behavior for transferring routing packets.

Configuration algorithm for underwater network topology

The key concept of the configuration algorithm is to configure the sensor network topology. Each sensor node maintains routing information in a control_record for self-organizing and independent control. The control_record consists of two system parameters: path cost ( $\mathcal{P}\mathcal{C}$ ) and the payoff history array ( $\mathbb{U}[·]$ ). $\mathcal{P}\mathcal{C}$ represents the degree to which communication can be adapted to reach the nearest sink node, whereas $\mathbb{U}[·]$ contains the payoff history for each action. The information in the control_record is used to determine adaptive routing decisions.

$\mathcal{P}\mathcal{C}$ is estimated based on the link costs in the route to the sink node. To estimate each wireless link between two sensor nodes, we define a link cost ( $L_c$ ). In each node, $\mathcal{P}\mathcal{C}$ is estimated as the sum of all $L_c$ values from the current node to the sink node. Using real-time monitoring of the remaining energy level of the node and the energy consumption of wireless communications, the value of $L_c$ from ${\delta }_i$ to ${\delta }_j$ ( $L_c(i,j)$ ) is obtained as follows

$$L_c(i,j)=[(1-{\alpha }_i)\times \frac{d_{i,j}}{D_M}]+[{\alpha }_i\times (1-\frac{{\mathcal{E}}_j}{E_M})]$$

(7)

where $d_{i,j}$ is the distance from ${\delta }_i$ to ${\delta }_j$ and ${\mathcal{E}}_j$ is the remaining energy of ${\delta }_j$ . $E_M$ and $D_M$ denote the initial energy and the maximum coverage range of each sensor node, respectively. Therefore, $d_{i,j}$ and ${\mathcal{E}}_j$ are normalized by $D_M$ and $E_M$ .

For the adaptive $L_c(i,j)$ estimation, the parameter ${\alpha }_i$ controls the relative weights given to the distance and the remaining energy of the corresponding node. When the remaining energy of the current node ${\delta }_i$ is high, we place more emphasis on the energy status of the next node ${\delta }_j$ , that is, on $(1-({\mathcal{E}}_j/E_M))$ . In this case, a higher value of ${\alpha }_i$ is more suitable. When the remaining energy of node i is insufficient, the path selection should be strongly dependent on the energy dissipation for data transmission. In this case, a lower value of ${\alpha }_i$ is preferable for the energy consumption rate, that is, on $(d_{i,j}/D_M)$ , as the distance between two neighbor nodes directly affects the energy consumption rate. In the proposed configuration algorithm, the value of ${\alpha }_i$ for the corresponding ${\delta }_i$ is dynamically adjusted based on the rate of remaining energy with respect to the initially assigned energy $({\mathcal{E}}_i/E_M)$ .

During network topology formation, each individual node estimates the $L_c$ values of its neighboring nodes. Nodes within one hop of the sink node set their $\mathcal{P}\mathcal{C}$ values to the one-hop $L_c$ value from themselves to the sink node. The remaining sensor nodes ${\delta }_i$ set their $\mathcal{P}\mathcal{C}$ values as follows

$$\mathcal{P}{\mathcal{C}}_i=\underset{j}{\mathbf{min}}\{\mathcal{P}{\mathcal{C}}_j+L_c(i,j)\},\mathrm{s}.\mathrm{t}.,j\in {\mathcal{N}}_i$$

(8)

where ${\mathcal{N}}_i$ is the set of neighboring nodes of ${\delta }_i$ . Based on the $\mathcal{P}\mathcal{C}$ values of the neighbor nodes, $\mathbb{U}[·]$ is initialized as

$${\mathbb{U}}_i{\left[j\right]}_{j\in {\mathcal{N}}_i}=\mathcal{P}{\mathcal{C}}_j+L_c(i,j)$$

(9)

When the proposed configuration algorithm has terminated, the virtual topology of the USN can be considered as a spanning tree structure that is rooted at the sink node while minimizing the $\mathcal{P}\mathcal{C}$ values. However, this is a temporary topology. During the routing operation, each node’s $\mathcal{P}\mathcal{C}$ and $\mathbb{U}[·]$ values are dynamically reestimated, and the network topology is also dynamically restructured.

Routing algorithm based on the Markov routing game

In designing the USN routing algorithm, we consider the multiplayer MDP. Each sensor node is assumed to be a player, and the objective of player $i$ ( ${\delta }_i$ ) is to find the best routing policy ${\psi }_i^{*}\in {\mathbb{A}}_i$ , where ${\mathbb{A}}_i$ is the action set of ${\delta }_i$ ; $\left|{\mathbb{A}}_i\right|=\left|{\mathcal{N}}_i\right|$ and ${\psi }_i$ represents a one-hop routing decision involving one of the neighboring nodes. Based on the routing decisions, each player statically determines its subsequent state. Let $s_i(t)$ and $a_i(t)$ be the state and action of ${\delta }_i$ at time step $t$ , respectively, where $s_i(t)\in {\mathbb{S}}_i$ and $a_i(t)\in {\mathbb{A}}_i$ . $U_i(s_i(t),a_i(t))$ is the payoff to ${\delta }_i$ at time $t$ when action $a_i(t)$ occurs in state $s_i(t)$ , and $U_i(s_i(t),a_i(t))\to \mathbb{R}$ . $U_i(s,a)$ can be interpreted as the reward ( $\mathcal{R}$ ) in $Q^{\psi }(s,a)$ , that is, the expected discounted reinforcement of taking action $a$ in state $s$ . The function $U_i(s,a)$ is critical to Q-learning as it determines the behavior and performance of ${\delta }_i$ .

By employing Q-learning, the main goal of the USN routing algorithm is to deliver the packet to the sink node with the maximum payoff. If the $m\mathrm{th}$ neighboring node is selected as a relay node at time period $t$ , that is, $a_i(t)=a_i^m$ , $U_i(·)$ can be defined as

$$\begin{array}{c}{U}_i(s_i\left(t\right),a_i\left(t\right)=a_i^m)={\mathcal{R}}_t(s_i\left(t\right),a_i^m)=\left(\frac{1}{\mathcal{P}{\mathcal{C}}_m^t+L_c(i,j)}\right)\times {(-\vartheta )}^{\mathcal{Q}\left(a_i^m\right)}\hfill \\ \mathrm{s}.\mathrm{t}.,\mathcal{Q}\left(a_i^m\right)=\{\begin{array}{cc}0,\hfill & \mathrm{if\; this\; packet\; is\; successfully\; delivered\; by\; action}{a}_i^m\hfill \\ \multicolumn{1}{c}{1,}& \mathrm{otherwise}\hfill \end{array}\hfill \end{array}$$

(10)

where $\mathcal{P}{\mathcal{C}}_m^t$ is the $\mathcal{P}\mathcal{C}$ value of the $m\mathrm{th}$ neighboring node at time $t$ , and $\vartheta$ is a penalty factor for packet delivery failure. According to $U_i(s_i(t),a_i(t)=a_i^m)$ , the corresponding ${\mathcal{U}}_i^m$ value in ${\mathbb{U}}_i[m]$ is updated; ${\mathbb{U}}_i[1,\dots ,m]=\{{\mathcal{U}}_i^1(·),{\mathcal{U}}_i^2(·),\dots ,{\mathcal{U}}_i^m(·)\}$ is a vector specifying the payoffs for ${\delta }_i$ . ${\mathbb{U}}_i[m]$ is updated as follows

$$\begin{array}{c}{\mathbb{U}}_i\left[m\right]={\mathcal{U}}_i^m(t+1)=\mathcal{J}+(\frac{1}{\eta }\times \{U_i(s_i\left(t\right),a_i\left(t\right)=a_i^m)-\mathcal{J}\})\hfill \\ \mathrm{s}.\mathrm{t}.,\mathcal{J}=\frac{1}{t}\times \left(\sum _{e=1}^t{U}_i(s_i\left(e\right),a_i\left(e\right))\right)\hfill \end{array}$$

(11)

where $\eta$ is a weight parameter for adjusting the current impact. At each time period, ${\delta }_i$ chooses action $a_i$ to maximize $U_i(·)$ and thus maximize $V$ , that is, $V^{*}(s)=\underset{a}{\mathbf{max}}{Q}^{*}(s,a)$ according to equation (5). A greedy Q-learning algorithm always chooses the action with the highest $Q$ value, which leads to packets being relayed to the sink node via the best route. To develop an effective Q-learning algorithm, we must define $P_{s_t\to s_{t+1}}^{a_t}$ in equations (4) and (5). Defining $P_{s_t\to s_{t+1}}^{a_t}$ is a probability decision problem. Through the multisensor routing game model, each sensor node adaptively learns the current USN state to dynamically determine $P_{s_t\to s_{t+1}}^{a_t}$ . Suppose there is a finite set of neighboring sensors $\{{\delta }_1,\dots ,{\delta }_m\}$ chosen by ${\delta }_i$ at game iteration $t$ . According to equations (10) and (11), each individual node obtains the $\mathcal{U}$ value and updates $\mathbb{U}[·]$ . Based on this information, we can determine $P_{s_t\to s_{t+1}}^{a_t}$ in equations (4) and (5). Let ${\mathit{P}}_i(t)=\{P_{s_t\to s_{t+1}}^{a_t^1},\dots ,P_{s_t\to s_{t+1}}^{a_t^m}\}$ be the probability distribution of the actions selected by ${\delta }_i$ . The values of ${\mathit{P}}_i(t)$ are defined as

$$\begin{array}{c}{P}_{s_t\to s_{t+1}}^{a_t^m}=P_i^m(S\prime |S,a_i^m\left(t\right))=\frac{\mathrm{EXP}\left({\mathcal{U}}_i^m\left(t\right)\right)}{\sum _{l\in {\mathcal{N}}_i}\mathrm{EXP}\left({\mathcal{U}}_i^l\left(t\right)\right)}\hfill \\ \mathrm{s}.\mathrm{t}.,\mathrm{EXP}\left(\mathcal{X}\right)=e^{\mathcal{X}}\hfill \end{array}$$

(12)

Main steps of the proposed USN routing algorithm

USNs have gained popularity for their application to environmental monitoring, military surveillance, and disaster prevention. Although some USN routing work has been conducted, existing schemes are strongly specialized for specific control issues. Therefore, it is challenging to obtain balanced system performance. In this article, we discuss a new perspective on USN routing problems. Using the Q-learning-based routing game model, we design a novel USN routing scheme through a step-by-step interactive feedback process. This allows each sensor node to learn the current situation and determine the best routing path. After a sequence of routing actions has been performed, the current USN condition dynamically changes. During the routing operation, each node periodically updates the routing information, reevaluates the current strategy and selects one of its neighbor nodes for packet forwarding. In terms of practical operations, we can transfer the computational burden from a central system to distributed nodes. Therefore, our distributed learning-based routing scheme is implemented as a dynamic repeated game for opportunistic routing. While traditional optimal solutions generally exhibit exponential time complexity, our proposed scheme operates in polynomial time. The main steps of the proposed USN routing algorithm are described as follows (see Figures 1 and 2):

• Step 1: Control parameters n, $\gamma$ , $\alpha$ , $\beta$ , $E_M$ , $D_M$ , $\eta$ , and $\vartheta$ are determined by the simulation scenario (see Table 2).

• Step 2: At the initial time, the sink node broadcasts the setup message. Within the power coverage area, message-receiving sensors individually estimate $L_c$ according to equation (7) and forward the setup message recursively to their neighbor nodes.

• Step 3: If a node has received multiple setup messages from reachable neighbor nodes, this node adaptively selects one of them to reach the sink node and initializes $\mathcal{P}\mathcal{C}$ and $\mathbb{U}[·]$ according to equations (8) and (9).

• Step 4: At every routing decision step, the individual sensor nodes statistically select the next relay node according to the probability distribution $\mathit{P}(·)$ .

• Step 5: Based on the selected routing strategy, the values in $\mathbb{U}[·]$ are modified at each sensor node in a real-time online manner.

• Step 6: At each time period, $\mathcal{P}\mathcal{C}$ , $\mathbb{U}[·]$ , and $\mathit{P}$ are reestimated at each sensor node based on equations (8), (11), and (12).

• Step 7: Using the Q-learning mechanism, each node’s routing strategy at time $t$ is adaptively selected according to equations (5) and (6).

• Step 8: Based on the interactive feedback mechanism, the dynamics of our routing game cause a cascade of interactions among the game players, who make their opportunistic routing decisions in a distributed fashion.

• Step 9: Under the relevant USN environment, individual nodes are constantly self-monitoring for the next routing game process; go to step 4.

Figure 1.

Flowchart of the proposed USN routing algorithm.

Figure 2.

Pseudo code of the proposed USN routing algorithm.

Table 2.

System parameters used in the simulation experiments.

Parameter	Value	Description
n	500	Number of sensor nodes
$\vartheta$	0.1	Penalty factor for packet delivery failure
$\eta$	0.8	Weight parameter for adjusting the current impact
edis	10 pJ/bit/m2	Energy dissipation coefficient for packet transmission
Eco	100 nJ/bit	System parameter for the electronic digital coding energy dissipation
B	1 Mb/s	Bandwidth of the wireless link
Packet	70 bits	Packet size for wireless communications
DM	100 m	Maximum wireless coverage range of each node
EM	100 J	Initial energy of each node
Parameter	Initial	Description	Values
$\alpha$	1	Relative weights given to the remaining energy	0–1 (ε/EM)

Performance evaluation

In this section, we evaluate the performance of our proposed protocol and compare it with that of VAPR, ¹² GDAR, ¹³ and ELAR. ¹⁴ Based on the simulation results, we confirm the superiority of the proposed approach. In this study, we have used the simulation tool MATLAB to develop our simulation model. MATLAB is one of the most widely used tools in a number of scientific simulation fields; high-level syntax and dynamic types of MATLAB are ideal for model prototyping. Our simulation results are achieved using MATLAB, which is widely used in academic and research institutions as well as industrial enterprises. To ensure a fair comparison, the following assumptions and system scenario were used:

• A 500-node USN was used in which the nodes were distributed randomly in a three-dimensional (3D) region of size 1000 m ×1000 m × 1000 m.

• No assumptions were made about the node dispersion or density in the acoustic field.

• The maximum wireless coverage range of each node was set to 100 m.

• The meandering current mobility model ¹⁹ was adopted to model the motility of each sensor node.

• Rayleigh fading was used to model small-scale fading.

• We used the carrier-sense multiple access (CSMA) media access control (MAC) protocol. In CSMA, when the channel is busy, a node waits for a predefined back-off period before attempting to sense the carrier again.

• For reliability, we implemented automatic repeat-requests (ARQ) at the routing layer. After packet reception, the receiver sends back a short acknowledgment (ACK) packet. If the sender fails to hear the ACK packet, the data packet is retransmitted; the packet will be dropped after three retransmissions.

• We used five sink nodes, each positioned at random on the surface.

• Data packets were generated at the source node at a rate of λ (packets/s), and the range of the offered load was varied from 0 to 3.0.

• At the start of the simulation, all nodes had an initial energy ( $E_M$ ) of 100 J.

• For simplicity, we assumed that the nodes were not affected by noise or physical obstacles.

• The energy dissipation in the transmitter node ( $E_{\mathrm{tran}}$ ) depends on the square of the covered distance ( $d^2$ ) and the electronic digital coding energy ( $E_{\mathrm{co}}$ ). Therefore, to transmit a k-bit packet, $E_{\mathrm{tran}}$ can be defined as

$$E_{\mathrm{tran}}=k\times (e_{\mathrm{dis}}\times d^2+E_{\mathrm{co}})$$

(13)

where d is the distance between the transmitter and receiver nodes and $e_{\mathrm{dis}}$ is the energy coefficient.^20,21

• The energy dissipation for the receiver node ( $E_{\mathrm{rec}}$ ) only depends on the electronic digital coding energy ( $E_{\mathrm{co}}$ ). Therefore, to receive a k-bit packet, $E_{\mathrm{rec}}$ can be defined as

$$E_{\mathrm{rec}}=k\times E_{\mathrm{co}}$$

(14)

• Network performance measures obtained on the basis of 100 simulation runs are plotted as functions of the packet generation per second (packets/s).

Usually, Rayleigh fading is a statistical model for the effect of a propagation environment on a radio signal, such as that used by wireless devices. It is most applicable when there is no dominant propagation along a line of sight between the transmitter and receiver. If there is a dominant line of sight, Rician fading may be more applicable. Rayleigh fading is a special case of two-wave with diffuse power (TWDP) fading. One of the limitations for the Rayleigh fading is its simplicity of assumption about dynamic wireless environments. In our simulation, we adopt the Rayleigh fading model for simplicity.

To demonstrate the validity of our proposed method, we measured the normalized energy consumption, network throughput, end-to-end delay, and packet loss ratio. Table 2 shows the system parameters used in the simulation. To emulate the USN system and ensure a fair comparison, we used the system parameters given in Table 2.

Figure 3 compares the packet loss ratio of each scheme. Packet loss is measured as the percentage of packets lost relative to the total number sent and is a key factor in USNs in terms of network operation. As the packet generation rate increases, the resultant network congestion results in increased packet loss. All schemes exhibit a similar trend; however, the proposed scheme outperforms the existing methods, particularly in heavy traffic load situations. In our scheme, packets are forwarded under an interactive environmental feedback mechanism, which guarantees a lower packet loss ratio than in other schemes.

Figure 3.

Packet loss ratio.

Figure 4 presents the normalized energy consumption per node for each scheme. Energy consumption increases with the packet generation rate, which is intuitively correct. In USNs, the main factor contributing to energy consumption is the communication distance. Therefore, it is important to determine the multiple-hop shortest path. Based on the online learning scheme, each node in our method is able to select the most energy-efficient routing path. Therefore, the proposed scheme attains superior energy efficiency to other schemes, from low to high traffic load intensities.

Figure 4.

Normalized energy consumption.

Figure 5 compares the network throughput. In this study, network throughput is defined as the ratio of data packets received at the sink node to the total number of data packets generated. The gain in network throughput achieved by the proposed scheme is a result of the effective feedback paradigm of employing an iterative learning model and the algorithm design for obtaining synergistic and complementary features. Therefore, the proposed scheme achieves superior network throughput performance to the existing schemes, which were designed as one-sided protocols and do not respond to current USN conditions.

Figure 5.

Network throughput.

The curves in Figure 6 indicate the normalized end-to-end packet delay. In general, as the packet generation rate increases, the packet delay increases linearly with the traffic load. At every period, each node in our scheme makes routing decisions in a distributed learning manner, reflecting changes in the network environment. Therefore, our approach reduces the packet delay more effectively than the other schemes.

Figure 6.

Normalized end-to-end delay.

The simulation results shown in Figures 3–6 demonstrate that the proposed scheme, which uses a Q-learning-based routing game model, can monitor the current USN conditions and adapt to highly dynamic environments. In particular, the sensors in our approach acquire information from the environment, gain knowledge, and make intelligent decisions in a self-adapting manner. The simulation results indicate that the proposed scheme generally exhibits superior performance to the existing schemes. Our approach also attains an appropriate balance of performance, something that the VAPR, ¹² GDAR, ¹³ and ELAR ¹⁴ schemes cannot offer.

Summary and conclusion

USNs have recently attracted considerable attention because of their significant capabilities for acoustic monitoring and resource discovery. USNs encompass a wide range of applications, from long-term measurements to imminent threats. In this article, we have presented a learning game approach to USN routing problems. Our major goal is to develop an efficient USN routing algorithm that is suitable for harsh underwater communication conditions. Considering the unique features of USNs, we have integrated an interactive feedback mechanism and designed a routing game model based on the well-known Q-learning concept. In the proposed model, individual sensor nodes learn better routing strategies and make routing decisions dynamically for adaptive, opportunistic routing. Using online self-monitoring and distributed learning techniques, the proposed scheme dynamically adapts to the current USN situation and effectively maximizes the expected benefits. To demonstrate the validity of our scheme, we compared our model with existing schemes and demonstrated that our approach outperforms the existing schemes in a simulation environment.

Although we have achieved our goals of energy efficiency and increased throughput in USN management, we believe that there is further scope for improving the efficiency of the USN system. Issues for further research include the design and validation of new USN control schemes in the fields of big data mining, cognitive radio, and network security. In addition, our work could be extended to error tolerance by investigating the effects of MAC layer activities such as packet loss and retransmission.