Sage Journals: Discover world-class research

Abstract

The topology control techniques of underwater wireless sensor networks and terrestrial wireless sensor networks are significantly different because of the particularity of underwater environments and acoustic communication. In this paper, an underwater wireless sensor network model was constructed, and six universal topology control objectives were concluded. The QoS topology control problem was mapped into an ordinal potential game model, and a distributed strategy adjustment algorithm for nodes was designed accordingly. The strategy vector resulting from the algorithm converges to the Nash equilibrium; minor complexity and preferable approximate ratios can be represented by the algorithm as well. The performance of the algorithm was analyzed through simulation experiments which indicate a well-constructed topology. Every objective was upgraded when model parameters were set suitable.

1. Introduction

Recently, there has been growing interest in the application of sensor networks in underwater environments to enable and enhance applications such as ocean resource exploration, pollution monitoring, and tactical surveillance [1–3]. Before the emergence of wireless sensor networks (WSNs) [4], the perception and collection of underwater data are generally accomplished through wired networks which are very costly. Underwater wireless sensor networks (UWSNs) [5–7] are the enabling technology for these underwater applications. UWSNs consist of sensors that perform collaborative monitoring tasks over a three-dimensional volume. Acoustic communications [8, 9] are the typical physical layer technology in underwater networks. There are three types of nodes in UWSNs: bottom nodes, anchored nodes, and surface sinks. The given phenomenon is observed by interconnected bottom and anchored nodes in charge of relaying data to surface sinks. The architecture of a UWSN is depicted in Figure 1.

Figure 1

UWSN architecture.

Figure 1 illustrates a three-dimensional UWSN; each bottom or anchored node can monitor and detect environmental events locally, and then transfer these measurements to a surface sink by multihops. Bottom nodes are spread on the seabed. Anchored nodes are equipped with floating buoys that can be inflated by pump. The depth of the anchored node can be regulated by adjusting the length of the wire.

QoS is an important issue in WSNs because quality of service has immediate impact on the availability of networks, and topology control is one of the main techniques to improve the quality of WSN service. Due to the specificity and complexity of the water medium, UWSN and terrestrial wireless sensor networks are significantly different. These differences include the following: (a) the propagation delay of the acoustic wave is much larger than that of the electromagnetic wave, and the propagation delay in UWSN cannot be neglected. (b) The limited bandwidth of underwater acoustic links is prone to cause high error rates and frequent dynamics of topology [10]. (c) Underwater acoustic communication requires more energy for signal modulation, and the energy consumption for sending messages is significantly larger than that for receiving. These differences make it difficult to guarantee the quality of the service (e.g., propagation delay, bandwidth, and transmission success rate) in UWSNs. In this regard, topology control is an efficient way to enhance the quality of services. In addition to the common topology control objectives of WSNs (full coverage, network connectivity, decrease in energy consumption, enhancement of network capacity, reduction of communication interference, and increase of spatial reuse), the topology control objectives in UWSN should also include the shortening of propagation delay, improvement of energy consumption efficiency, extension of network lifetime, augmentation of transmission bandwidth, and increase in the transmission success rate. Therefore, in this paper QoS-based topology control for UWSN is defined as the art of coordinating nodes' decisions regarding their communication and sensing ranges, in order to generate a network topology with the desired properties (e.g., connectivity, coverage), while optimizing some (or all) of other service metrics (e.g., energy consumption, propagation delay, transmission bandwidth, and transmission success rate) in underwater environments.

The remainder of this paper is organized as follows. In Section 2, we discuss related works; in Section 3, we describe the UWSN model and define some concepts; in Section 4, we map QoS topology control problem into an ordinal potential game model; Section 5 proposes a strategy adjustment algorithm SAA; in Section 6, SAA is analyzed from the aspects of convergence, complexity, and approximate ratio; in Section 7, we discuss the performance evaluation of SAA; finally, Section 8 provides some conclusions.

2. Related Work

The problem of QoS topology control for WSN has been extensively studied. However, most studies have been based on specific applications or partial objectives. Furthermore, the characteristics of acoustic communication and underwater environments have never been taken into account. Li et al. [11] proposed an MST-based topology control algorithm (LMST) that can effectively reduce transmission power while maintaining global connectivity. However, the topology obtained by LMST is fragile, and network lifetime is prone to termination. In a study by Li et al. [12], the QoS topology control problem in heterogeneous ad hoc networks was formulated as an integer linear programming problem or a mixed integer linear programming problem. This produced a network topology that meets QoS requirements and minimizes the maximum energy utilization of nodes. Liu et al. [13] reported that each node in the network has different functionalities in data transmission, and they correspondingly proposed a topology control algorithm (EasiTPQ) to improve packet loss rate and propagation delay. Cai and Yang [14] presented a multi-QoS optimization distributed topology control algorithm (MQOTC) considering residual energy, end-to-end delay, and link loss ratio; every sensor node builds the local maximum QoS topology independently. MQOTC is distributed and is scalable, but it does not consider the full coverage objective, and it cannot be adapted when the requirements of specific applications change. To ensure high QoS (maximizing network lifetime and ensuring message delivery), a topology control algorithm (EBC) which exploits the edge of the centrality concept is proposed [15]. In the investigation conducted by Ma et al. [16], both centralized and distributed QoS topology control approaches employing opportunistic transmission are put forward; simulations demonstrate that the approach significantly improves energy efficiency with low communication overhead. Forghani et al. [17] improved network lifetime and decreased average energy consumption by reducing the transmission power of nodes and periodically choosing the active path. However, the approach ignores the extra overhead brought by the periodical regulation of active paths. Reference [18] proposed a framework, based on the emergent potential games to deal with a variety of network resource allocation problems. But the framework was designed for terrestrial wireless sensor networks, and some basic topology requirements (e.g., coverage) were not taken into account. An energy-efficient topology control algorithm FiYG was proposed in [19]. FiYG was designed for three dimensional UWSNs, but it was unable to achieve typical underwater QoS objectives.

In summary, the existing algorithms or approaches of QoS topology control are difficult to apply in UWSN because of the following. (a) Currently, the QoS topology control objectives of UWSN have not been analyzed intensively. Therefore, some important objectives in underwater environments have been neglected. (b) Due to the multiformity of UWSN applications, different QoS objectives will be required in different applications. The QoS topology control model and algorithm should be capable of objective-driven adaptation. (c) Most current studies assume that the deployment space is a two-dimensional plane. However, underwater topography is complicated, and so the deployment space must be three dimensional.

Inspired by such motivations, the QoS topology control for UWSN is investigated in this paper by exploiting the ordinal potential game model. Given an amount of wireless sensor nodes in a 3D space where nodes have a set of strategies (i.e., different communication radiuses and sensing radiuses) and given the capacities of energy consumption, propagation delay, bandwidth, and transmission success rates on links, the aim is to find a UWSN topology that can meet both full coverage and global connectivity while optimizing other objectives as much as possible.

3. UWSN Model

Our work is based on the scenario that a set of static sensors are deployed in underwater space $D \in I R^{3}$ . The topology of UWSN can be represented as a graph $G (V, E)$ , where the finite set of nodes $V = {V_{1}, V_{2}, \dots, V_{N}}$ and the set of links $E \subseteq V \times V$ .

3.1. Model Description

(1) Nodes

For all $V_{k} \in V$ , its current communication radius, sensing radius, and residual energy are denoted as $RC (k)$ , $RS (k)$ , and $e (k)$ , respectively. Any node $V_{k}$ can be in two kinds of status: awake or asleep. If $V_{k}$ is asleep, then $RS (k) = RC (k) = 0$ . The set of awake nodes $W = {V_{k} | V_{k} \in V, RS (k) > 0, RC (k) > 0}$ . For all $V_{k}, V_{k^{'}} \in V$ or for all $p, q \in D$ , the distance is $d (k, k^{'})$ and $d (p, q)$ . We define the neighboring nodes set of $V_{k}$ as $n e (k)$ and $n e (k) = {V_{k'} | d (k, k') \leq RC (k)}$ .

(2) Links

For all $V_{k'} \in n e (k)$ , the link between $V_{k}$ and $V_{k}$ is expressed as $(k, k')$ . The propagation delay, bandwidth, and transmission success rate of $(k, k')$ are denoted as $delay (k, k')$ , $band (k, k')$ , and $ratio (k, k')$ respectively. For all $V_{i}, V_{j} \in V$ if $d (i, j) \leq RC (i)$ , then $(i, j) \in E$ .

(3) Paths

For all $V_{i}, V_{j} \in V$ if there are $(i, i_{1}), (i_{1}, i_{2}), \dots, (j_{2}, j_{1}), (j_{1}, j) \in E$ , then $path (i, j)$ exists.

3.2. Definitions and Assumptions

Suppose that X is a set of Boolean values, and R is a set of positive real numbers. UWSN coverage function is expressed as $coverage (G) : G (V, E) \to X$ , the connectivity function is defined as $connectivity (G) : G (V, E) \to X$ , and the energy consumption function of the node is $consumption (k) : V k \to R$ , with $V_{k} \in W$ . To clarify and simplify the UWSN model, other definitions and assumptions are given.

Definition 1.

Node coverage space: for all $V_{k} \in V$ , coverage space of $V_{k}$ with sensing radius $RS (k)$ defined as $Cover (k, RS (k)) = {p | d (k, p) \leq RS (k), for all p \in D}$ .

Definition 2.

Bidirectional links: for all $V_{i}, V_{j} \in V$ if $d (i, j) \leq RC (i)$ and $d (i, j) \leq RC (j)$ , then link $(i, j)$ is bidirectional.

Definition 3.

Full coverage: for all $p \in D$ , there exist $V_{k} \in W$ , with $d (k, p) \leq RS (k)$ .

Definition 4.

Global connectivity: for all $V_{i}, V_{j} \in W$ , $path (i, j)$ and $path (j, i)$ exist.

Definition 5.

Alive status of UWSN: full coverage and global connectivity can be achieved by awake nodes set $W$ , and for all $V_{k} \in W$ , $e (k) > 0$ .

Assumption.

Sensor nodes are uniformly distributed in $D$ , and the coordinates of every node have been informed.

Assumption.

$D$ is a convex region, for all $p, q \in D$ , we get $α \bar{p} + (1 - α) \bar{q} \in D (0 \leq α \leq 1)$ .

Assumption.

${RC}_{1} \geq 2 {RS}_{χ}$ . ${RC}_{1}$ denotes the minimum communication radius, and ${RS}_{χ}$ denotes the maximum sensing radius.

Assumption.

For all $V_{k} \in V$ , $V_{k'} \in n e (k)$ , $delay (k, k')$ , $band (k, k')$ , and $ratio (k, k')$ are known values.

Assumption.

If for all $V_{k} \in V$ , then $RC (k) = {RC}_{χ}$ and $RS (k) = {RS}_{χ}$ ; therefore, $G (V, E)$ satisfies both full connectivity and global connectivity.

3.3. Objectives

The QoS topology control objectives of UWSN can be presented as (i)

$coverage (G) = 1$ ,

(ii)

$connectivity (G) = 1$ ,

(iii)

$\min \sum_{\forall V_{k} \in V} consumption (k)$ ,

(iv)

$\min \sum_{\forall V_{i}, V_{j} \in W} \sum_{\forall (i^{'}, j^{'}) \in path (i, j)} delay (i^{'}, j^{'})$ ,

(v)

$\max \sum_{\forall V_{i}, V_{j} \in W} \min_{\forall (i^{'}, j^{'}) \in path (i, j)} band (i^{'}, j^{'})$ ,

(vi)

$\max \sum_{\forall V_{i}, V_{j} \in W} \prod_{\forall (i^{'}, j^{'}) \in path (i, j)} ratio (i^{'}, j^{'})$ .

Objectives (i) and (ii) should be strictly satisfied, and objectives (iii)–(vi) are optimized as much as possible. The QoS topology control problem with multiobjective optimization is a NP-hard problem which will be solved approximately by the ordinal potential game in the next section.

4. Ordinal Potential Model

4.1. Game Description

Game theory attempts to mathematically capture behavior in strategic games, in which an individual's success in making choices depends on the choices of others [20]. Similarly, every node in UWSN expects to optimize service quality, and decisions of radiuses (communication and sensing radiuses) of nodes are dependent on each other, hence topology control can be considered as a game process. In order to map the topology control problem into a game model, the tuple (communication radius, sensing radius) is viewed as the strategy of node, and payoff function of every node should be defined. To facilitate the description of the model, the explanations of symbols are first given as shown in Table 1.

Table 1

Description of symbols in the game model.

Symbol	Description	Symbol	Description
$A$	Strategy space	$A_{k}$	Optional strategies set of $V_{k}$
$a$	Strategy vector	$A_{- k}$	Strategies set of non- $V_{k}$ nodes
$a_{k}$	Selected strategy of $V_{k}$	$U (a)$	Payoff function vector
$a_{- k}$	Strategy vector of non- $V_{k}$ nodes	$u_{k} (a)$	Payoff function of $V_{k}$
${RC}_{ψ}$	ψth level communication radius	χ	Number of optional strategies
${RS}_{ψ}$	ψ th level sensing radius	$C_{k} (a)$	Coverage function of $V_{k}$
$E_{k} (a)$	Energy consumption function of $V_{k}$	$D_{k} (a)$	Propagation delay function of $V_{k}$
$B_{k} (a)$	Bandwidth function of $V_{k}$	$S_{k} (a)$	Transmission success rate function of $V_{k}$

The mixed-strategy game is impractical in the context of design problems [21, 22]; therefore, the pure strategy game [23, 24] is considered. The pure strategy game is denoted as $Γ (V, A, U (a))$ , and $A$ can be expressed as

A = \prod_{k = 1}^{n} A_{k} .

(1)

In Expression (1), for all $V_{k} \in V$ , $A_{k} = {(0,0), ({RC}_{1}, {RS}_{1}, ({RC}_{2}, {RS}_{2}), \dots, {RC}_{ψ}, {RS}_{ψ}), \dots, ({RC}_{χ}, {RS}_{χ})}$ , giving $0 < {RC}_{1} \leq {RC}_{2} \leq \dots \leq {RC}_{χ}$ , $0 < {RS}_{1} \leq {RS}_{2} \leq \dots \leq {RS}_{χ}$ · $A_{- k}$ is expressed as

A_{- k} = \prod_{k^{'} \neq k}^{} A_{k^{'}} .

(2)

Payoff function vector $U (a) = (u_{1} (a), u_{2} (a), \dots, u_{n} (a))$ , where $a = (a_{1}, a_{2}, \dots, a_{n})$ , $a_{k} \in A_{k}$ , $V_{k} \in {V_{1}, V_{2}, \dots, V_{n}}$ . Strategy vector of non- $V_{k}$ nodes $a_{- k} = (a_{1}, \dots, a_{k - 1}, a_{k + 1}, \dots, a_{n}) \in A_{- k^{°}}$ Payoff function $u_{k} (a)$ of $V_{k}$ is computed as

\begin{matrix} u_{k} (a) & = C_{k} (a) \\ \cdot [- φ_{1} E_{k} (a) - φ_{2} D_{k} (a) + φ_{3} B_{k} (a) + φ_{4} S_{k} (a) + φ_{5}] . \end{matrix}

(3)

In Expression (3), $φ_{5}$ is sufficiently large to let $u_{k} (a) \geq 0$ . The size of parameters ( $φ_{1}$ – $φ_{4}$ ) represents different levels of significance to corresponding objectives, and therefore, this topology control model can be adapted for diverse objectives of special applications by adjusting the parameter size.

4.2. Payoff Function

A sufficient condition is given for full network coverage size to guarantee global connectivity.

Lemma 6.

When ${RC}_{1} \geq 2 {RS}_{χ}$ , if UWSN covers the convex region $D$ , then $G (W, E)$ satisfies global connectivity.

Proof.

The proof is similar with Theorem 7 in a study by Wang et al. [25]; for any two nodes $V_{i}$ and $V_{j} W$ , $P_{i j}$ is the line segment joining $V_{i}$ and $V_{j}$ . Due to the coverage of UWSN, any point $p \in P_{i j}$ has been covered by at least one close and awake sensor node. Consequently, the set of closest nodes $s_{1}, \dots, s_{m}$ can be constructed for contiguous segments which consist of points with the same set of closest sensors. For all $u \in s_{k - 1}$ , $v \in s_{k}$ , we have $d (u, v) \leq RS (u) + RS (v)$ . We assume $RS (u) \geq RS (v)$ , which directly yields $RC (u) \geq RC (v)$ and $d (u, v) \leq 2 RC (v) \leq 2 RC (u)$ . Hence, both $(u, v)$ and $(v, u)$ are bidirectional links, and there must be $path (i, j)$ between $V_{i}$ and $V_{j}$ .

(a) Coverage Function

Any node $V_{k}$ has a coverage function

C_{k} (a) = C_{k} (a_{k}, a_{- k}) = {\begin{cases} 1 & if coverage (G) = 1, \\ 0, & else, \end{cases}

(4)

and

C_{k} (a)

can be converted to

C_{k} (a) = \prod_{V_{i} \in V}^{} F_{i} (a) .

(5)

Formula (5) shows that the coverage function is the product of all nodes' local coverage functions. $F_{i} (a)$ is defined as the local coverage function of node $V_{i}$ ,

F_{i} (a) = {\begin{cases} 1 & if \exists V_{j} \in W, d (j, p) \leq RS (j), \\ \forall p \in D \cap Cover (i, R S_{χ}), \\ 0, & else . \end{cases}

(6)

Formula (6) means all points in every node's possible maximum coverage area should be covered by at least another node.

Theorem 7.

Full coverage can be achieved when $C_{k} (a) = 1$ .

Proof.

$∵ C_{k} (a) = 1$ , ∴ for all $V_{i} \in V$ , $F_{i} (a) = 1$ , ∴ for all $p \in ⋃_{\forall V_{i} \in V}^{} (D \cap Cover (i, {RS}_{χ}))$ , there exist $V_{j} \in W$ , $d (j, p) \leq RS (j)$ . Assumption 5 gives $D \subseteq ⋃_{\forall V_{i} \in V}^{} Cover (i, {RS}_{χ})$ ; therefore, for all $p \in D$ , there exist $V_{j} \in W$ , $d (j, p) \leq RS (j)$ .

(b) Energy Consumption Function

For any node $V_{k}$ , the energy consumption function

\begin{matrix} E_{k} (a) & = E_{k} (a_{k}, a_{- k}) \\ = P_{0} (a_{k}) \\ = P_{0} RC {(k)}^{β} 10^{RC (k) α (f) / 10}, \end{matrix}

(7)

where

P_{0}

is the least received power level to guarantee the required quality of reception [26], and

(a_{k})

is signal attenuation [27]. The energy spreading factor and absorption coefficient are denoted by

β (β \in [1,2])

and

α (f)

, respectively.

(c) Propagation Delay Function

Suppose that the number of neighboring nodes is κ in $V_{k}$ with strategy $a_{k}$ , then $D_{k} (a)$ can be expressed as

\begin{matrix} D_{k} (a) = D_{k} (a_{k}, a_{- k}) = \frac{\sum_{V_{k^{'}} \in n e (k)} delay (k, k')}{κ}, \end{matrix}

(8)

where

delay (k, k')

[28] is computed as

\begin{matrix} delay (k, k') = \frac{L}{B} + \frac{d (k, k')}{R_{uw}}, \end{matrix}

(9)

where L is the length of every data packet, B is the channel capacity in bits per second, and

R_{uw}

is the propagation speed of underwater sound. Thus,

\begin{matrix} D_{k} (a_{k}, a_{- k}) = \frac{\sum_{V_{k'} \in n e (k)} d (k, k')}{κ R_{uw}} + \frac{L}{B} . \end{matrix}

(10)

(d) Bandwidth Function

\begin{matrix} B_{k} (a) = B_{k} (a_{k}, a_{- k}) = \min_{V_{k'} \in n e (k)} band (k, k') . \end{matrix}

(11)

(e) Transmission Success Rate Function

\begin{matrix} S_{k} (a) = S_{k} (a_{k}, a_{- k}) = {(\prod_{V_{k'} \in n e (k)}^{} ratio (k, k'))}^{1 / κ}, \end{matrix}

(12)

where

ratio (k, k') \in [0,1]

, and

S_{k} (a) \in [0,1]

Theorem 8.

$Γ (V, A, U (a))$ is an ordinal potential game.

Proof.

The ordinal potential function is defined as $\tilde{U} (a) = \sum_{V_{k} \in W} u_{k} (a)$ and let $Δ u_{k} = u_{k} (a_{k}, a_{- k}) - u_{k} (b_{k}, a_{- k})$ which gives

\begin{matrix} Δ \tilde{U} & = \tilde{U} (a_{k}, a_{- k}) - \tilde{U} (b_{k}, a_{- k}) = Δ u_{k} \\  +  \sum_{V_{i} \in W; i \neq k} {C_{i} (a_{k}, a_{- k}) \\ \cdot [φ_{1} E_{i} (a_{k}, a_{- k}) + φ_{2} D_{i} (a_{k}, a_{- k}) \\ + { φ}_{3} B_{i} (a_{k}, a_{- k}) +  φ_{4} S_{i} (a_{k}, a_{- k})  +  φ_{5}] \\ - C_{i} (b_{k}, a_{- k}) \\ \cdot [φ_{1} E_{i} (b_{k}, a_{- k}) + φ_{2} D_{i} (b_{k}, a_{- k}) \\ + φ_{3} B_{i} (b_{k}, a_{- k}) + φ_{4} S_{i} (b_{k}, a_{- k}) + φ_{5}]}, \\ Δ u_{k} & = {\begin{cases} = 0 & if C_{k} (a_{k}, a_{- k}) = C_{k} (b_{k}, a_{- k}) = 0 \\ > 0 & if C_{k} (a_{k}, a_{- k}) = 1, C_{k} (b_{k}, a_{- k}) = 0 \\ < 0 & if C_{k} (a_{k}, a_{- k}) = 0, C_{k} (b_{k}, a_{- k}) = 1 \\ Δ \tilde{U} & if C_{k} (a_{k}, a_{- k}) = C_{k} (b_{k}, a_{- k})  =  1, a_{k}  >  b_{k} \\ Δ \tilde{U} & if C_{k} (a_{k}, a_{- k}) = C_{k} (b_{k}, a_{- k})  =  1, a_{k}  <  b . \end{cases} \end{matrix}

(13)

If $C_{k} (a_{k}, a_{- k}) = C_{k} (b_{k}, a_{- k}) = 0$ , then $Δ \tilde{U} = Δ u_{k} = 0$ ,

If $C_{k} (a_{k}, a_{- k}) = 1, C_{k} (b_{k}, a_{- k}) = 0$ , then $Δ \tilde{U} > 0$ ,

If $C_{k} (a_{k}, a_{- k}) = 0, C_{k} (b_{k}, a_{- k}) = 1$ , then $Δ \tilde{U} < 0$ ,

If $C_{k} (a_{k}, a_{- k}) = C_{k} (b_{k}, a_{- k}) = 1$ and $i \neq k$ , then $E_{i} (a_{k}, a_{- k}) = E_{i} (b_{k}, a_{- k})$ , $D_{i} (a_{k}, a_{- k}) = D_{i} (b_{k}, a_{- k})$ , $B_{i} (a_{k}, a_{- k}) = B_{i} (b_{k}, a_{- k})$ , and $S_{i} (a_{k}, a_{- k}) = S_{i} (b_{k}, a_{- k})$ . Thus, $Δ \tilde{U} = Δ u_{k}$ .

As a result of the analysis, the sign of $Δ \tilde{U}$ is the same as the sign of $Δ u_{k}$ . Therefore, $Γ (V, A, U (a))$ is an ordinal potential game.

Definition 9.

Nash Equilibrium (NE): $a^{*}$ is NE if for all $V_{k} \in V$ , for all $a_{k} \in A_{k}$ , and $u_{k} (a^{*}) \geq u_{k} (a_{k}, {a^{*}}_{- k})$ .

Potential games are known to possess at least one NE in pure strategies as proven in previous reports [29].

5. Algorithm

In this section, a distributed strategy adjustment algorithm (SAA) is proposed for nodes to achieve objectives (i) and (ii) while optimizing objectives (iii)–(vi) approximately. The following are the description and pseudocode of the SAA algorithm.

Strategy Adjustment Algorithm (SAA)

Step 1.

Any node $V_{i}$ has an initial strategy set as $a_{i}^{(0)} = ({RC}_{χ}, {RS}_{χ})$ ; the adjustment function of $V_{i}$ is defined and initialized as $H (i) = 0$ . After the initial setting, every node with maximum communication radius ${RC}_{χ}$ broadcasts the message announce_msg whose structure is depicted in Table 2.

Step 2.

If one node receives announce_msg, then it replies with receive_msg (Table 2).

Step 3.

At the ξth round, the node which will adjust the strategy is selected randomly from the probability formula

P_{i} (ξ) = {\begin{cases} 0 & if H (i) \neq 0, \\ \frac{Δ u_{i} (a^{ξ - 1})}{\sum_{V_{j} \in V, H (j) = 0} Δ u_{j} (a^{ξ - 1})}, & else, \end{cases}

(14)

where for

V_{i}

at the ξth round,

{P_{i}}^{(ξ)}

denotes the probability of becoming the only strategy adjustment node, and

Δ u_{i} (a^{ξ - 1})

is the possible payoff enhancement which is computed as

Δ u_{i} (a^{ξ - 1}) = \max_{b_{i} \in A_{i}} (u_{i} (b_{i}, {a_{- i}}^{(ξ - 1)}) - u_{i} (a_{i}, {a_{- i}}^{(ξ - 1)})) .

(15)

For any node $V_{i}$ , if $H (i) = 0$ , $V_{i}$ should broadcast a message inquire_msg in the spheriform range of radius ${RC}_{χ}$ . Suppose that $V_{j}$ receives inquire_msg from $V_{i}$ , $V_{j}$ will compute all possible $F_{j} (a)$ when it adopts different strategies. Subsequently, a message feedback_msg containing all possible values of $F_{j} (a)$ will be replied to $V_{i}$ . The structures of inquire_msg and feedback_msg are shown in Table 3.

The strategy of $V_{i}$ should be updated according to Expression (16) provided that $V_{i}$ has been chosen to adjust its strategy at the ξth round; following this, the adjustment function must be set as $H (i) = ξ$

a_{i}^{(ξ)} = \arg \max_{b_{i} \in A_{i}} u_{i} (b_{i}, {a_{- i}}^{(ξ - 1)}) .

(16)

Step 4.

Upon completion of the strategy adjustment, the last round broadcasts announce_msg.

Step 5.

Steps 1 to 4 are repeated for N rounds.

Table 2

Announce_msg/receive_msg structure.

Message information	Node information				Neighbor information
Type	ID	Position	Strategy	Adjust	ID_Set	Delay	Bandwidth	Ratio

Table 3

Inquire_msg/feedback_msg structure.

Message information	Node information				Neighbor information
Type	ID	Position	Strategy	Adjust	ID_Set	Local coverage

The pseudocode of SAA is given in Pseudocode 1.

6. Algorithm Analysis

6.1. Convergence

SAA is theoretically proven to be convergent.

Theorem 10.

SAA converges to NE.

Proof.

For all $V_{i} \in V$ , the minimum sensing radius of $V_{i}$ to achieve full coverage is denoted as $Φ (a_{- i})$ , a monotonic, nonincreasing function of $a_{- i}$ , that is, if ${a_{- i}}^{k 1} = ((RC (k_{1}), RS (k_{1})), a_{- i - k 1})$ and ${a_{- i}}^{k 2} = ((RC (k_{2}), RS (k_{2})), a_{- i - k 2}) (RC (k_{1}) \geq RC (k_{2})$ , $RS (k_{1}) \geq RS (k_{2}))$ , then $Φ ({a_{- i}}^{k 1}) \leq Φ ({a_{- i}}^{k 2})$ . Accordingly, the value interval of sensing radius $R (a_{- i}) = {Φ (a_{- i}), \dots, ({RC}_{χ}, {RS}_{χ})}$ . To adjust the strategy of $V_{i}$ , Expression (16) can be rewritten as

{\tilde{a}}_{i} = {({RC}_{ψ}, {RS}_{ψ}) {RS}_{ψ} \geq Φ (a_{- i}), \max u_{i} ({\tilde{a}}_{i}, a_{- i})} .

(17)

After strategy update, the payoff of $V_{i}$ will be maximized with the strategy vector $({\tilde{a}}_{i}, a_{- i})$ ; if $V_{j}$ updates strategy to ${\tilde{a}}_{j}$ as well, there must be $RS (j) \leq {RS}_{χ}$ , $Φ ({\tilde{a}}_{j}, a_{- i - j}) \geq Φ (a_{- i})$ and ${\tilde{a}}_{i} \in R ({\tilde{a}}_{j}, a_{- i - j})$ . In this case, the new strategy vector $({\tilde{a}}_{i}, {\tilde{a}}_{j}, a_{- i - j})$ continues to maximize the payoff of $V_{i}$ . Therefore, the result of SAA execution $\tilde{a} = ({\tilde{a}}_{1}, {\tilde{a}}_{2}, \dots, {\tilde{a}}_{n})$ is determinately NE.

6.2. Complexity

For any node $V_{i}$ , even though $V_{i}$ changes strategy, the $F_{j} (a)$ of any node $V_{j}$ out of the spheriform range with center $V_{i}$ and radius ${RC}_{1}$ remains the same.

Theorem 11.

For all $V_{i}, V_{j} \in V$ , if $d (i, j) \geq R C_{1}$ , no point $p \in D \cap Cover (i, {RS}_{χ})$ can be found to satisfy $d (j, p) \leq {RS}_{χ}$ .

Proof.

Suppose that there exist $p \in D \cap Cover (i, {RS}_{χ})$ and $d (j, p) \leq {RS}_{χ}$ , $d (i, p) \leq {RS}_{χ}$ which gives $d (i, j) \leq d (i, p) + d (j, p) \leq 2 {RS}_{χ} \leq {RC}_{1}$ . This conclusion contradicts the premise $d (i, j) \geq {RC}_{1}$ .

The implementation and operating cost of algorithm realization can be measured with algorithm complexity. The complexity of a distributed algorithm is measured in message complexity and time complexity [30]. The quantity of messages in SAA depends mostly on the judgment of UWSN coverage (Step 3). According to Theorem 11 and Assumption 1, the strategy adjustment of one node can possibly influence the local coverage function of $(4 π {RC}_{1}^{3} / 3 | D |) N$ neighboring nodes. At some round, if $V_{i}$ has not adjusted strategy, that is, $H (i) = 0$ , then $V_{i}$ must broadcast inquire_msg to compute the possible payoff enhancement, and every neighboring node replies with a feedback_msg. There are about ( $1 + (4 π {RC}_{1}^{3} / 3 | D |) N$ ) messages required in this process. As a result, the quantity of total messages is $\sum_{k = 1}^{N} (4 k π {RC}_{1}^{3} / 3 | D |) N$ ; therefore, the message complexity of SAA is $O (N^{3})$ .

SAA should be executed N rounds; therefore, the time complexity of SAA is considered as $O (N)$ .

SAA has polynomial complexity, which indicates relatively low implementation cost of SAA realization.

6.3. Approximate Ratio

Supposing that the total payoff function $U (a)$ is the same as $\tilde{U} (a)$ , the strategy vector $\overset{̅}{a} = argmax U (a)$ , and $\tilde{a}$ is the NE from SAA execution. $Ω$ is defined in Expression(17)

Ω = \frac{- φ_{1} ma x_{V_{k} \in V} E_{k} (a) - φ_{2} ma x_{V_{k} \in V} D_{k} (a) + φ_{3} mi n_{V_{k} \in V} B_{k} (a) + φ_{4} mi n_{V_{k} \in V} S_{k} (a)}{- φ_{1} mi n_{V_{k} \in V} E_{k} (a) - φ_{2} mi n_{V_{k} \in V} D_{k} (a) + φ_{3} ma x_{V_{k} \in V} B_{k} (a) + φ_{4} ma x_{V_{k} \in V} S_{k} (a)} .

(18)

Apparently,

U (\tilde{a}) / U (\overset{̅}{a}) \geq \min_{a \in A} U (a) / \max_{a \in A} U (a) \geq mi n_{V_{k} \in V, C_{k} (a) = 1} u_{k} (a) / ma x_{V_{k} \in V} u_{k} (a) \geq Ω

, the NE obtained by SAA is at least

Ω (Ω < 1)

times the maximum value of

U (\overset{̅}{a}), Ω

can be considered as the approximate ratio of SAA.

7. Performance Evaluation

SAA is evaluated by observing the performance variation when adopting different model parameters and by comparing SAA with other algorithms. SAA is realized in OMNeT++ [31]. MAC Layer and routing are outside the scope of this paper. The IEEE 802.15.4 routing algorithm [32] is adopted for MAC and FA [33]. The simulation environment is set as $N - 1$ nodes evenly distributed in $D$ , with one sink node selected randomly at the horizontal plane. Moreover, node mobility, delay from calculation, and energy consumption by receiving messages are neglected in simulations. The values of the parameters are shown in Table 4.

Table 4

Simulation Parameters.

Parameters	Description	Value
N	Number of sensor nodes	2000
$\| D \|$	Deployment space	$100 m \times 500 m \times 200 m$
χ	Number of strategy ranks	10
E ₀	Initial battery energy of the node	8000 J
${RC}_{ψ}$	Communication radius of the ψth rank	$10 + 2 ψ m$
${RS}_{ψ}$	Sensing radius of the ψth rank	$5 + ψ$ m
β	Energy spreading factor	1.5
$α (f)$	Absorption coefficient	$2 \times 10^{- 3} dB / km$
L	Length of every data packet	50 B
B	Channel capacity	10 kbps
$band (k, k^{'})$	Bandwidth of link $(k, k^{'})$	random(100,200) kbps
$ratio (k, k^{'})$	Transmission success ratio of link $(k, k^{'})$	random(0.9,1.0)
$R_{uw}$	Propagation speed of sound underwater	1500 m/s
P ₀	Minimum signal power	0.07
$φ_{5}$	Parameter in payoff function	20

7.1. Connectivity and Coverage

The connectivity of UWSN is defined as the proportion of the maximum number of connected nodes and N; the coverage is the proportion of current covered space and $| D |$ . Figure 2 illustrates the connectivity and coverage of UWSN as N increases; the value of χ is assigned as 5, 7, and 10.

Figure 2

Connectivity and coverage.

Three observations can be made: (a) as N increases, both connectivity and coverage increase until 100% regardless of the value of χ. The reason for such behavior is that the deployment density of nodes must be large enough to achieve full coverage and global connectivity; (b) the plot $χ = 10$ is higher than the other two plots because the growth of χ augments the maximal communication radius and the sensing radius, acquiring higher connectivity and coverage; (c) the least number of nodes required for full coverage ( $N = 1200$ at $χ = 10$ ) is far more than what is required for global connectivity ( $N = 300$ at $χ = 10$ ). This phenomenon confirms the conclusions of Lemma 6 (full coverage is a sufficient condition of global connectivity).

7.2. Average Energy Consumption

Set $φ_{1} = 0.4$ and $φ_{2} = φ_{3} = φ_{4} = 0$ . This simulation compares the average energy consumption and UWSN lifetime in SAA, FiYG, LMST, and EBC. As shown in Figure 3, the SAA average energy consumption of the node in unit time is significantly lower than those of FiYG, LMST, and EBC. This is because the topology control model can be transformed into a QoS model aiming at low energy consumption. By setting the parameters, SAA can effectively reduce the average energy consumption of nodes. In Figure 3, the plots decrease as N increases, which is attributed to the fact that full coverage and global connectivity can be met by nodes with a relatively lower strategy rank as more nodes are densely deployed. Furthermore, from Figure 4, UWSN lifetime apparently increases as N increases, and the UWSN lifetime obtained by SAA is higher than those by other algorithms.

Figure 3

Average energy consumption.

Figure 4

UWSN lifetime.

7.3. Average Delay of Single Hop

Set $φ_{2} = 0.2$ and $φ_{1} = φ_{3} = φ_{4} = 0$ . In Figure 5, the average delay of single hop in SAA is lower than that in FiYG, LMST, and EBC. There is a 4.2 ms difference between SAA and LMST when $N = 3000$ . As N increases, the average delay of single hop of all algorithms gradually shortens due to increasing deployment density.

Figure 5

Average delay of a single hop.

7.4. Influence of $φ_{1}$ and $φ_{2}$

Low energy consumption and low propagation delay are the most important and common objectives. The influence of $φ_{1}$ and $φ_{2}$ on the average energy consumption and average delay will be observed and analyzed in this simulation.

There are three observations from Figure 6: (a) when $φ_{2}$ is set, the increase in $φ_{1}$ generally leads to the reduction in average energy consumption, and reduction is significantly weakened if $φ_{1}$ is large enough; (b) when $φ_{1}$ ( $φ_{1} \neq 0$ ) is set, the increase in $φ_{2}$ gives rise to a slight increase in average energy consumption because the QoS model is more concerned about propagation delay with a varying $φ_{2}$ ; (c) at $φ_{1} = 0$ , the plot has irregular fluctuations, and $φ_{2}$ consistently increases due to the randomness of topology (objective (iii)). An increase in $φ_{2}$ results in the contraction of the average delay of a single hop, and conversely, an increase in $φ_{1}$ causes the extension of the average delay of a single hop (Figure 7).

Figure 6

Influence of $φ_{1}$ and $φ_{2}$ on the average energy consumption.

Figure 7

Influence of $φ_{1}$ and $φ_{2}$ on the average delay.

7.5. Average Path Bandwidth

Set $φ_{3} = 0.1$ and $φ_{1} = φ_{2} = φ_{4} = 0$ . When χ is assigned as 5, 7, and 10, respectively, the average path bandwidth exhibits the three plots shown in Figure 8. A higher average path bandwidth will be obtained with higher values of χ. This is because an increase in χ implies enlargement of the set optional strategies, and better strategies may be selected for the nodes. The average path bandwidth has irregular fluctuation as N increases when χ is determined. Although lower-ranked strategies can be selected while more nodes are deployed, increasing path hops is possible. Therefore, the average path bandwidth is not affected by N. Moreover, from Figure 9, when $φ_{3} = 0.1$ and $φ_{1} = φ_{2} = φ_{4} = 0$ , the average path bandwidth obtained by SAA is higher than those by other algorithms, which did not take transmission bandwidth into account.

Figure 8

Average path bandwidth.

Figure 9

Comparison of average path bandwidth.

7.6. Average Path Transmission Success Ratio

Set $φ_{4} = 0.8$ and $φ_{1} = φ_{2} = φ_{3} = 0$ . The curved surface peak is nearly 0.89 ( $χ = 10$ , $N = 2700$ ), as shown in Figure 10. At a fixed χ, the variation in average path transmission success is irregular as N increases; the reason for this is similar to that in Simulation E. The phenomenon suggests that SAA is scalable with respect to the number of nodes. As shown in Figure 11, transmission success ratio of SAA is significantly higher than those of FiYG, LMST, and EBC, and the SAA plot fluctuates obviously with the increase of N. This is because dense nodes deployment will result in extension of practical strategy space, which will improve transmission success ratio probably. However, meanwhile an increase of hops number on paths giving rise to the reduction of transmission success ratio will be caused as well.

Figure 10

Average path transmission success ratio.

Figure 11

Comparison of average path transmission success ratio.

In summary, (a) the proposed algorithm SAA efficiently improves performance in terms of energy consumption, propagation delay, bandwidth, and transmission success rate while meeting both full coverage and global connectivity; (b) the simulation results indicate average energy consumption and UWSN lifetime: the average delay is optimized while N increases, whereas the average path bandwidth and average path transmission success ratios are independent of N. Therefore, SAA possesses scalability with respect to the number of nodes; (c) according to different multiobjectives of UWSN applications, SAA shows favorable performance at properly set parameters.

8. Conclusions

Aiming at the particularity of water medium and underwater acoustic communication, the QoS topology control problem was studied in this paper, and a distributed SAA was designed accordingly. SAA can exhibit outstanding performance in every typical objective. However, the UWSN model in this paper is idealistic, that is, it prohibits node mobility, and delays from calculation, energy consumption by receiving messages are neglected. Furthermore, the communication range and sensing range of nodes are irregular rather than spheres. Addressing QoS topology control in more real environments or scenarios is suggested for further study.

Pseudocode 1: SAA pseudocode.

SAA(G( V , E ))

${$ initial()

${$ for( $k = 1$ ; $k < = N$ ; $k + +$ )

${$ $a_{k} = ({RC}_{χ}, {RS}_{χ})$ ; $H (k) = 0$ ;

announce(); $}$

$}$

for $(ξ = 1; ξ < = N; ξ + +)$

${$ if ( $k = = random_select ({P_{k}}^{(ξ)}, {P_{- k}}^{(ξ)}$ ))

${a_k$ = strategy_adjust( $a_{- k}$ );

$H (k) = ξ$ ; $}$

$a = (a_{k}, a_{- k})$ ;

$}$

Footnotes

Acknowledgments

This research is supported by the National Natural Science Foundation of China under Grants Nos. 60903181, 61003236, 61003040, Talents Start Research Foundation of Nanjing University of Posts and Telecommunications under Grant No. NY208073. L. Liu also wants to acknowledge the support from the Key Laboratory of Ministry of Education for Computer Network and Information Integration (Southeast University), Nanjing, China.

References

Heidemann

Wills

Syed

Research challenges and applications for underwater sensor networking

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC ′06)

April 2006

Las Vegas, Nev, USA

228 235

2-s2.0-34250365027

Cui

J.-H.

Kong

Gerla

Zhou

The challenges of building scalable mobile underwater wireless sensor networks for aquatic applications

IEEE Network 2006 20 3 12 18

10.1109/MNET.2006.1637927

Partan

Kurose

Levine

B. N.

A survey of practical issues in underwater networks

Proceedings of the 1st ACM International Workshop on Underwater Networks (WUWNet ′06)

September 2006

17 24

2-s2.0-34247377791

10.1145/1161039.1161045

Elson

Estrin

Sensor Networks: A Bridge to the Physical World 2004

Norwell, Mass, USA

Kluwer Academic Publishers

3 20

Heidemann

Wills

Research challenges and applications for underwater sensor networking

Proceedings of the 1st ACM International Workshop on Underwater Networks

2006

ACM Press

33 40

Akyildiz

I. F.

Pompili

Melodia

Underwater acoustic sensor networks: research challenges

Ad Hoc Networks 2005 3 3 257 279

2-s2.0-13944252629

10.1016/j.adhoc.2005.01.004

Akyildiz

I. F.

Pompili

Melodia

Challenges for efficient communication in underwater acoustic sensor networks

ACM SIGBED Review 2004 1 2 3 8

Stojanovic

Proakis

J. G.

Acoustic (underwater) communications

Encyclopedia of Telecommunications 2003

New York, NY, USA

John Wiley & Sons

Ibrahim

Cui

J.-H.

Ammar

Surface-level gateway deployment for underwater sensor networks

Proceedings of the Military Communications Conference (MILCOM ′07)

October 2007

Orlando, Fla, USA

IEEE Press

1 7

2-s2.0-47949113744

10.1109/MILCOM.2007.4454996

10.

Domingo

M. C.

Prior

Energy analysis of routing protocols for underwater wireless sensor networks

Computer Communications 2008 31 6 1227 1238

2-s2.0-40949083548

10.1016/j.comcom.2007.11.005

11.

Hou

J. C.

Sha

Design and analysis of an MST-based topology control algorithm

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies (INFOCOM ′03)

March-April 2003

San Francisco, Calif, USA

1702 1712

12.

Jia

QoS topology control for nonhomogenous ad hoc wireless networks

EURASIP Journal on Wireless Communications and Networking 2006 2006 10

82417

2-s2.0-33645696597

10.1155/WCN/2006/82417

13.

Liu

Cui

Niu

EasiTPQ: QoS-based topology control in wireless sensor network

Journal of Signal Processing Systems 2008 51 2 173 181

2-s2.0-43449100059

10.1007/s11265-007-0105-2

14.

Cai

W.-Y.

Yang

H.-B.

A multi-QoS optimization distributed topology control algorithm for wireless sensor networks

Proceedings of the IET Conference on Wireless, Mobile and Sensor Networks (CCWMSN ′07)

December 2007

Shanghai, China

IEEE Press

261 264

10.1049/cp:20070133

15.

Cuzzocrea

Katsaros

Manolopoulos

EBC: a topology control algorithm for achieving high QoS in sensor networks

Proceedings of the 6th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness

2009

Canary Islands, Spain

Springer Press

613 626

16.

Qian

Zhang

L. M.

Opportunistic transmission based QoS topology control in wireless sensor networks

Proceedings of the 5th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS ′08)

October 2008

Atlanta, Ga, USA

IEEE Press

422 427

2-s2.0-67650665496

10.1109/MAHSS.2008.4660050

17.

Forghani

Rahmani

A. M.

Khademzadeh

QCTC: QoS-based clustering topology control algorithm for wireless sensor networks

Proceedings of the International Conference on Advanced Computer Theory and Engineering (ICACTE ′08)

December 2008

Phuket, Thailand

IEEE Press

966 970

2-s2.0-62949220161

10.1109/ICACTE.2008.154

18.

Scutari

Barbarossa

Palomar

D. P.

Potential games: a framework for vector power control problems with coupled constraints

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP ′06)

May 2006

Toulouse, France

IEEE Press

241 244

2-s2.0-33947641991

19.

Wang

Dahlberg

T. A.

Energy-efficient topology control for three-dimensional sensor networks

International Journal of Sensor Networks 2008 4 1 68 78

20.

Myerson

R. B.

Game Theory: Analysis of Conflict 1991

Cambridge, Mass, USA

Harvard University Press

21.

Ansheleich

Dasgupta

Tardos

Near-optimal network design with selfish agents

Proceedings of the 36th Symposium on Theroy of Computing

2004

Chicago, ILL, USA

ACM Press

511 520

22.

Eidenbenz

Anil Kumar

V. S.

Zust

Equilibria in topology control games for ad hoc networks

Proceedings of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC ′03)

2003

San Diego, Calif, USA

ACM Press

2 11

23.

Fudenberg

Tirole

Game Theory 1991

Cambridge, Mass, USA

MIT Press

24.

Komali

R. S.

MacKenzie

A. B.

Distributed topology control in ad-hoc networks: a game theoretic perspective

Proceedings of the 3rd IEEE Consumer Communications and Networking Conference (CCNC ′06)

January 2006

Orleans, La, USA

IEEE Press

563 568

2-s2.0-33749040867

10.1109/CCNC.2006.1593087

25.

Wang

Xing

Zhang

Pless

Gill

Integrated coverage and connectivity configuration in wireless sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

Los Angeles, Calif, USA

ACM Press

28 39

26.

Sozer

E. M.

Stojanovic

Proakis

J. G.

Underwater acoustic networks

IEEE Journal of Oceanic Engineering 2000 25 1 72 83

2-s2.0-0033882824

10.1109/48.820738

27.

Berkhovskikh

Lysanov

Fundamentals of Ocean Acoustics 2003 3rd

New York, NY, USA

Springer

28.

Ibrahim

Cui

J.-H.

Ammar

Surface-level gateway deployment for underwater sensor networks

Proceedings of the Military Communications Conference (MILCOM ′07)

October 2007

Sanfrancisco, Calif, USA

IEEE Press

1 7

2-s2.0-47949113744

10.1109/MILCOM.2007.4454996

29.

Monderer

Shapley

L. S.

Potential games

Games and Economic Behavior 1996 14 1 124 143

2-s2.0-0030147102

10.1006/game.1996.0044

30.

Tel

Introduction to Distributed Algorithms 2003 2nd

Beijing, China

Phei Press

31.

Varga

OMNeT++ -discrete event simulation system user manual[EB/OL]

http://www.omnet.org/

32.

IEEE 802.15.4 2003

Wireless Medium Access Control (MAC) and Physical layer (PHY) Specifications for low-rate wireless personal area networks

33.

Chang

Tassiulas

Energy conserving routing in wireless ad-hoc networks

Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′00)

March 2000

Tel Aviv, Israel

IEEE Press

22 31

2-s2.0-0033885342

A QoS-Based Topology Control Algorithm for Underwater Wireless Sensor Networks

Abstract

1. Introduction

2. Related Work

3. UWSN Model

3.1. Model Description

(1) Nodes

(2) Links

(3) Paths

3.2. Definitions and Assumptions

Definition 1.

Definition 2.

Definition 3.

Definition 4.

Definition 5.

Assumption.

Assumption.

Assumption.

Assumption.

Assumption.

3.3. Objectives

4. Ordinal Potential Model

4.1. Game Description

4.2. Payoff Function

Lemma 6.

Proof.

(a) Coverage Function

Theorem 7.

Proof.

(b) Energy Consumption Function

(c) Propagation Delay Function

(d) Bandwidth Function

(e) Transmission Success Rate Function

Theorem 8.

Proof.

Definition 9.

5. Algorithm

Strategy Adjustment Algorithm (SAA)

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

6. Algorithm Analysis

6.1. Convergence

Theorem 10.

Proof.

6.2. Complexity

Theorem 11.

Proof.

6.3. Approximate Ratio

7. Performance Evaluation

7.1. Connectivity and Coverage

7.2. Average Energy Consumption

7.3. Average Delay of Single Hop

7.4. Influence of φ 1 and φ 2

7.5. Average Path Bandwidth

7.6. Average Path Transmission Success Ratio

8. Conclusions

Pseudocode 1: SAA pseudocode.

Footnotes

Acknowledgments

References

7.4. Influence of $φ_{1}$ and $φ_{2}$