Sage Journals: Discover world-class research

Abstract

The high attenuation of radio signals in water leaves acoustic waves the most viable communication media for underwater sensor networks. Nevertheless, acoustic communication suffers from significantly high latency because of its low propagation speed compared to radio communication. In this article, we consider the problem of constructing connected dominating sets as virtual backbones under acoustic communication. We abstract a wireless sensor network as a graph with weighted edges, where the weight of an edge represents the latency between the wireless nodes it links. Three approximation algorithms are proposed to optimize the latency of a connected dominating set. The first algorithm provides a two-approximation to the diameter of a connected dominating set, where the diameter is defined as the length of the longest shortest path in a graph. The second algorithm guarantees a six-approximation to the minimum latency between any pair of nodes and meanwhile has constant approximations to the connected dominating set size in unit disk graphs and unit ball graphs. The third algorithm constructs a connected dominating set with 12-approximation to the diameter and 10.197-approximation to the size in unit disk graphs. Extensive simulations are carried out to validate the performance of the proposed algorithms.

Keywords

Virtual backbone connected dominating set latency underwater sensor network

Introduction

The growing need for ocean observation systems has stimulated considerable interest on the study of underwater sensor networks (USNs). A USN consists of underwater sensor nodes, which cooperatively work together to offer a wide spectrum of applications,^1–4 such as pollution monitoring, oceanographic data collection, and coastline protection. To make these applications viable, there is a need to enable underwater communications among underwater devices.

Wireless underwater acoustic networking is the enabling technology for these USN-based applications. In fact, electromagnetic waves propagate for long distances through sea water only at extra low frequencies (30–300 Hz),⁵ which requires large antennae and high transmission power. By comparison, acoustic waves do not have such high attenuation in water, so that a USN differs from terrestrial sensor networks that it relies on acoustic signals for communication. However, acoustic communication suffers from critically high latency and long end-to-end delay because of its low propagation speeds (1.5 × 10³ m/s) compared to radio communication (3 × 10⁸ m/s).

In wireless sensor networks, a lot of effort has been made on constructing a virtual backbone (VB)⁵ for efficient routing and network topology control. Due to the limited transmission range of sensor nodes, node-to-node communication in sensor networks usually follows a multi-hop pattern with the help of some intermediate relay nodes. That is to say, routing in sensor networks is about finding appropriate relay nodes for passing messages. Once a VB is used in a wireless sensor network, the routing tasks are restricted to the backbone nodes. A small size VB suffers less from interference and leads to more efficient energy consumption and simpler routing maintenance when network topology changes.

Unfortunately, the use of VBs also increases the latency of the network. The high latency of acoustic communication makes this problem more severe in USNs than in terrestrial sensor networks. In this article, we consider the problem of constructing latency-optimal VBs using acoustic communication. Currently, connected dominating set (CDS)-based approaches have become one of the most competitive VB construction methods in sensor networks. In a wireless sensor network abstracted as a graph $G = (V, E)$ , where $V$ represents sensor nodes and $E$ represents links between adjacent nodes, a dominating set (DS) is a node set $D \subseteq V$ , such that a node in $G$ is either in $D$ or adjacent to at least one node in $D$ . A DS is said to be a CDS if it induces a connected subgraph. We study approaches to optimize not only the size of a CDS but also the routing path length within a CDS to build latency-optimal VB-based USNs.

In this article, a wireless network is abstracted as an undirected graph with weighted edges, where the weight of an edge represents the latency between the sensor nodes it links. As some previous works,^6–9 we model a homogeneous wireless network as a unit disk graph (UDG) or a unit ball graph (UBG). A USN can be represented as an edge-weighted UBG because it naturally distributes in a three-dimensional (3D) underwater area. In addition, some monitoring missions require all underwater nodes deployed in the same depth,¹⁰ in which case a wireless network can be represented as an edge-weighted UDG.

Figure 1 presents an example of an edge-weighted UDG. In Figure 1, if ${b, c, e}$ are selected as a CDS, then the minimum latency between $a$ and $f$ is $4 + 5 + 2 = 11$ and if ${b, d, e}$ are selected as a CDS, then the minimum latency between $a$ and $f$ is $5 + 5 + 5 + 2 = 17$ . Thus illustrates the importance of devising latency-optimal CDS algorithms.

Figure 1.

An edge-weighted unit disk graph. ${b, c, e}$ or ${b, d, e}$ forms a CDS of the graph.

Three algorithms are proposed in this article:

The first algorithm is devised for general graphs and achieves a two-approximation to the diameter of a CDS. The diameter of a graph is defined as the length of the longest shortest path in it. That is, if C is a CDS of $G = (V, E)$ constructed through the first algorithm, then $Diam (C) \leq 2 D_{opt}$ , where $Diam (C)$ denotes the diameter of the subgraph induced by $C$ and $D_{opt}$ denotes any optimal CDS of $G$ .

Considering that the first algorithm does not guarantee desirable approximation ratio to CDS size, we devise the second algorithm and the third algorithm which have constant approximation ratios to CDS size in UDGs and UBGs. For any pair of nodes with minimum latency $L$ in $G$ , routing with a CDS constructed by the second algorithm guarantees the minimum latency between these two nodes at most $6 L + 5 L_{\max}$ , where $L_{\max}$ denotes the maximum latency between any pair of adjacent nodes. The second algorithm also guarantees a constant approximation ratio 140 to CDS size in UDGs.

Considering that approximation ratio to CDS size of the second algorithm is big, we devise the third algorithm which provides a 12-approximation to CDS diameter, and meanwhile a 10.197-approximation to CDS size in UDGs.

The proposed algorithms are summarized in Table 1, which shows that theoretically (1) the first algorithm is more suitable for networks demanding that the latency between a pair of nodes would not be too bad in the worst case, (2) the second algorithm is more suitable to be used when the latency between any pair of nodes is needed to be concerned, and (3) the third algorithm is promising when backbone size and latency are both important to operate the network.

Table 1.

Approximation ratio of the proposed algorithms.

Algorithm	Approximation ratio
	Size	Diameter	Routing cost
The first algorithm	None	2	None
The second algorithm	140	None	6
The third algorithm	10.197	12	None

Besides USNs, the proposed algorithms can also apply to other kinds of networks with high point-to-point delays, such as delay tolerant networks and large-area sensor networks. However, USNs are the most typical and reasonable networks to apply the proposed algorithms because of the high latency of acoustic communication. Therefore, we only discuss about the CDS problem in USNs in this article and the approaches can be simply extended to other target scenes.

The rest of this article is organized as follows.

A brief review for CDS construction algorithms is presented in section “Related work.” In “Problem statements,” we introduce the assumptions and formalize the problem. Details of the proposed algorithms are shown in sections “The first algorithm,”“The second algorithm,” and “The third algorithm.” Extensive simulations are conducted and the results are presented in section “Simulation.” Finally, we conclude this article in section “Conclusion.”

Related work

We briefly review existing CDS construction algorithms in this section by three categories: algorithms optimizing the size, algorithms optimizing the routing cost, and algorithms optimizing other parameters. Readers can refer to Du and Wan¹¹ for more comprehensive introductions about CDS construction algorithms.

CDS algorithms optimizing the size

Most of existing CDS algorithms focus on constructing a minimum size CDS. Guha and Khuller¹² proposed two approximation algorithms in general graphs. Their first algorithm grows a spanning tree as the dominating tree by the node with the maximum degree. Their second algorithm contains two phases, with the first phase to construct a DS and connects it in the second phase. These algorithms achieve performance ratio $O (H (▵))$ , $where ▵$ is the maximum degree of the graph and $H$ is a harmonic function. Wan et al.¹³ used a maximal independent set (MIS) as a DS and proposed a distributed CDS algorithm with constant approximation ratio 8 in UDGs. They also proved that in UDGs any MIS has upper bound $4 op t_{CDS} + 1$ , where $op t_{CDS}$ denotes the size of a minimum CDS. A lot of works follow this study and prove better MIS upper bounds to devise CDS algorithms with better approximation ratios.^14–17 Some works^6,8 extend these MIS-based approaches to 3D spaces, where a wireless sensor network is abstracted as the UBG model. The best MIS upper bounds as we know in UDGs and UBGs have been presented in Lemma 4 and Lemma 5 of this article, respectively. For heterogeneous wireless sensor networks, where sensor nodes have different transmission ranges, the MIS-based approaches are extended to general disk graphs and general ball graphs.^18–20

In addition to these MIS-based algorithms, some marking-based algorithms are proposed in Dai and colleagues.^21,22 These algorithms first mark a CDS and then prune redundant nodes to obtain a small size. Compared to MIS-based algorithms which usually have polynomial time complexities, the marking-based algorithms do not guarantee constant approximation ratios, but are localized with $O (1)$ time complexity. Hence, the marking-based algorithms lead to easier VB maintenance and are more appropriate to be used in mobile wireless ad hoc networks.

For wireless networks composed of nodes equipped with directional antennas, the network can be modeled as a graph with directional links. The CDS problem on directional network models has been studied in Wu and colleagues.^23,24

CDS algorithms optimizing the routing cost

Some existing works optimize the routing path lengths of a CDS in wireless sensor networks. Ding et al.²⁵ proposed an algorithm to construct a minimum routing cost CDS (MOC-CDS). Their algorithm guarantees that each routing path between any pair of nodes is also the shortest path in the network. Their key idea is based on the observation that a MOC-CDS is equivalent to a 2hop-CDS, which ensures that for any two nodes with distance equal to 2, there exists at least one shortest path between them. Ding et al.²⁶ extended the MOC-CDS problem to an α-MOC-CDS, which guarantees α-approximations to the routing path length between any pair of nodes. Liu et al.²⁷ considered to optimize the CDS routing cost in heterogeneous wireless networks. Du et al.²⁸ proposed an MIS-based approach which guarantees constant approximation ratio to both CDS size and routing path length between any pair of nodes. Kim et al.²⁹ proposed two algorithms to optimize the diameter of a CDS. Their algorithms guarantee constant approximation ratio to both the size and diameter of a CDS.

Algorithms optimizing other characteristics of a CDS

There are also many works considered to optimize other characteristics of a CDS, such as load balancing, network lifetime, and fault tolerance.

For algorithms optimizing other parameters of a CDS, He et al.³⁰ suggested to construct a load-balanced CDS to balance the communication overhead of backbone nodes. Alzoubi et al.³¹ proposed a distribute algorithm to optimize the message complexity while ensuring constant approximation in terms of CDS size.

Some applications assume that sensor nodes have different weights, where the weight of a node usually represents its remaining energy. Hence, an important line of works studies the problem of constructing a minimum weight CDS (MWCDS). The MWCDS problem plays an important role for the study of maximum lifetime problem in wireless sensor networks. In fact, Garg and Koenemann³² proved that if the minimum weight sensor cover problem has a ρ-approximation, then the maximum lifetime problem will have a (ρ + ε)-approximation. For the construction of a MWCDS, interested readers can refer to the literature.^9,33,34

Dai and Wu³⁵ initially discussed about constructing a k-connected m-dominating set ((k,m)-CDS) as a fault-tolerant VB. A (k,m)-CDS can survive after any k − 1 backbone nodes fail. A non-backbone node can connect to the VB even after its m − 1 adjacent backbone nodes fail. Dai and Wu³⁵ proposed three algorithms to construct a (k,k)-CDS, but no performance ratio was analyzed. Approximation algorithms with constant performance ratio to construct a (k,m)-CDS in UDGs have been studied previously.^36–39 Zhang et al.⁴⁰ proposed a performance-guaranteed algorithm for the minimum (3,m)-CDS problem in a general graph.

Some works consider to construct a CDS under other communication models. Yu et al.⁷ discussed about CDS construction under the beeping model, which is a novel communication model compared to the traditional message passing model. Wu et al.⁴¹ studied the CDS problem under the cooperative communication model. Dai et al.^42,43 studied the backbone problem in cognitive radio networks.

Discussion

The differences between this article and existing works are twofold. First, for weighted graphs, existing works suppose that sensor nodes are weighted to represent the remaining energy. Instead, this work uses the weight of a link between nodes to represent latency caused by acoustic communication and motivates to optimize the routing cost instead of network lifetime. Second, existing routing cost optimization CDS algorithms measure the length of a routing path by the hop-distance among sensor nodes. Thus, the theoretical analyses for these algorithms are inappropriate for edge-weighted graphs. In addition, more proper implementations should be proposed for acoustic communication-based wireless networks.

Problem statements

We use an edge-weighted UDG $G = (V, E)$ as Figure 1 to abstract a two-dimensional (2D) wireless sensor network. A 3D wireless sensor network is abstracted as an edge-weighted UBG. The weight of the edge between a pair of sensor nodes represents their communication latency under acoustic communication. We consider to minimize not only size but also the routing path length of a CDS in an edge-weighted graph.

With acoustic communication, the latency between a pair of adjacent nodes can be obtained through two schemes:

If all sensor nodes are well synchronized, then the end-to-end delay between two adjacent nodes can be tested through passing messages with time stamps.

If the sensor nodes are not well synchronized, the communication latency between two neighboring nodes can also be estimated by their locations with some simple assumptions. For underwater sensor node localization, interested readers can refer to Liu et al.¹⁰ For a pair of adjacent sensor nodes $u$ and $v$ in a graph $G = (V, E)$ , let $| u, v |$ denote the Euclidean distance between them. Let $(u, v)$ denote the edge between $u$ and $v$ . Assume that the propagation speed of acoustic wave in water is a constant $spee d_{aw}$ . Let $L (u, v)$ denote the latency between $u$ and $v$ . Then, $L (u, v)$ can be obtained from $| u, v |$ and $spee d_{aw}$ as shown in equation (1)

\begin{matrix} L (u, v) = \frac{| u, v |}{spee d_{aw}} \end{matrix}

(1)

Let $TR$ denote the transmission range of nodes and $L_{\max}$ denote the maximum latency between any pair of adjacent nodes. Then, $L_{\max}$ can be obtained as shown in equation (2)

L_{\max} = \frac{TR}{spee d_{aw}}

(2)

We assume that 1 unit distance causes 1 unit latency. Thus, hereafter, in this article, the weight of $(u, v)$ can represent not only the latency but also the Euclidean distance between $u$ and $v$ .

We use ${v_{0}, v_{1}, \dots, v_{n}}$ to denote a routing path in $G$ , where $v_{k} (0 \leq k \leq n - 1)$ and $v_{k + 1}$ are adjacent nodes. The weight of ${v_{0}, v_{1}, \dots, v_{n}}$ is denoted as $| {v_{0}, v_{1}, \dots, v_{n}} |$ and defined as shown in equation (3)

\begin{matrix} | {v_{0}, v_{1}, \dots, v_{n}} | = \sum_{k = 0}^{n - 1} | v_{k}, v_{k + 1} | \end{matrix}

(3)

Hence, the minimum latency between two arbitrary nodes $u$ and $v$ is defined as the weight of a routing path linking them with minimum weight.

Suppose $C$ is a CDS of $G$ . If we use $C$ as a VB of the network, then for any node $u$ and $v$ , $u$ and $v$ can only communicate with each other through a routing path ${u, v_{1}, v_{2}, \dots, v_{n}, v}$ , where $v_{k} \in C (1 \leq k \leq n)$ . It can be simply proved that for any $u$ and $v$ , the minimum latency between $u$ and $v$ in $G$ must not be greater than their minimum latency routing with any CDS of $G$ .

The first algorithm

Algorithm description

The basic idea of the first algorithm is to build a dominating tree, where every node in the network retransmits the flooding message when it is the first time to receive it. It can be proved that the dominating tree is also a shortest path tree, which means it provides a shortest routing path from root to each node in the network. Since a shortest path tree provides routing of at most two-approximation to the diameter of the graph, the first algorithm also guarantees a two-approximation to optimal CDS diameter. Note that traditional shortest path algorithms, such as Dijkstras algorithm and Floyd–Warshall algorithm, require the entire topology information of a graph and have running time at least $O (n^{2})$ . By comparison, our first algorithm is devised following a distributed pattern, and surprisingly has time complexity $O (n)$ .

In Step 1 of the first algorithm, the node with the smallest ID initiates the flooding process. An $INVITE$ message is flooded to the network. Each node passes the INVITE message to its neighbors only when it is the first time to receive the message. For a node $v$ , it can be proved that the INVITE message first reaches $v$ through the shortest routing path from $r$ to $v$ . The neighbor of $v$ who is the first time to send the message is the parent node of $v$ in the dominating tree. All non-leaf nodes are colored in black and outputted as CDS nodes. Details of the first algorithm are presented in Algorithm 1.

Algorithm 1. The first algorithm
Input: A graph $G = (V, E)$ . Every node in V is colored in white. Output: All black nodes form a CDS of $G$ . 1: The node with the smallest ID colors itself gray and sends an INVITE message to its neighbors. 2: If a white node $v$ receives an INVITE message from node $u$ , then $v$ (1) colors itself gray, (2) sends an INVITE message to its neighbors, and (3) sends a PARENT message to $u$ . 3: Upon receiving a PARENT message, a node colors itself black.

Algorithm 1. The first algorithm

Input: A graph

G = (V, E)

. Every node in V is colored in white.
Output: All black nodes form a CDS of

G

.
1: The node with the smallest ID colors itself gray and sends an INVITE message to its neighbors.
2: If a white node

v

receives an INVITE message from node

u

, then

v

(1) colors itself gray, (2) sends an INVITE message to its neighbors, and (3) sends a PARENT message to

u

.
3: Upon receiving a PARENT message, a node colors itself black.

Theorem 1

Black nodes outputted from Algorithm 1 form a CDS of $G$ .

Proof

Any node in $G$ have a parent which will be colored in black by Algorithm 1. Therefore, the black nodes form a DS of $G$ . In addition, any black node will be connected to the leader node through the path comprised by its ancestor nodes which are also colored black. Therefore, the black nodes form a CDS.

Performance analysis

In Theorem 2, we prove that the dominating tree is a shortest path tree, which guarantees a two-approximation to CDS diameter (equation (4)).

Theorem 2

If $C$ is a CDS obtained from the first algorithm, then

\begin{matrix} Diam (C) \leq 2 D_{opt} \end{matrix}

(4)

where $D_{opt}$ denotes the diameter of any optimal CDS of $G$ .

Proof

For any node $v_{0}$ , let $v_{i + 1}$ denote the parent of $v_{i}$ computed from Algorithm 1, where $0 \leq i \leq k - 1$ and $v_{k}$ is the leader node $r$ .

Now, we prove by contradiction that the path ${v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r}$ is the shortest path in $G$ between $v_{0}$ and $r$ . Suppose that there exists another path ${v_{0}, v'_{1}, v'_{2}, \dots, v'_{k - 1}, r}$ that is shorter than ${v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r}$ , then according to Algorithm 1, $v_{0}$ will first get the INVITE message from $v'_{1}$ . Therefore, $v_{1'} = v_{1}$ . Hence, ${v_{0}, v_{1}, v'_{2}, \dots, v'_{k - 1}, r}$ is shorter than ${v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r}$ . According to Algorithm 1, $v_{1}$ will be the first time to receive the INVITE message from $v'_{2}$ . That is, $v'_{2} = v_{2}$ . Similarly, we have $v'_{i} = v_{i} (1 \leq i \leq k - 1)$ . This proves that ${v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r}$ is the shortest path between $v_{0}$ and $r$ in $G$ .

Therefore, for any node $u_{1}$ and $u_{2}$ in $G$ , there exists a path ${v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r, u_{k - 1}, \dots, u_{1}, u_{0}}$ , such that ${v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r}$ is the shortest path between $v_{0}$ and $r$ and ${r, u_{k - 1}, \dots, u_{1}, u_{0}}$ is the shortest path between $u_{0}$ and $r$ . Therefore

\begin{matrix} Diam (C) \leq | {v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r, u_{k - 1}, \dots, u_{1}, u_{0}} | \\ = | {v_{0}, v_{1}, v_{2}, \dots, v_{k - 1}, r} | \\ + | {r, u_{k - 1}, \dots, u_{1}, u_{0}} | \leq 2 D_{opt} \end{matrix}

Theorem 3

The time complexity and message complexity of the first algorithm are $O (n)$ .

Proof

In the first algorithm, a node sends the INVITE message when it is the first time to receive the message. In Theorem 2, we have proved that the INVITE message reaches a node through the shortest path from the leader node. Therefore, the algorithm ends in $O (n)$ time. Moreover, each node forwards the INVITE only once. Therefore, the algorithm has message complexity $O (n)$ .

Observe that the first algorithm does not guarantee any approximation ratio in terms of CDS size. In the rest of this article, we introduce the other two approximation algorithms which not only optimize routing path length of a CDS but also ensure constant approximation ratio in terms of CDS size.

The second algorithm

Algorithm description

The second algorithm follows an MIS-based two-phased approach. In the first phase, an MIS is constructed as a DS. In the second phase, each pair of MIS nodes within three hops is connected. The idea of the second algorithm is inspired by Alzoubi et al.³¹ and Du et al.²⁸ Alzoubi et al.³¹ used such a scheme to optimize the message complexity of a CDS algorithm. Du et al.²⁸ proved that the routing cost of the scheme is guaranteed. However, the routing cost in Du et al.²⁸ is defined as the hop-distance between a pair of nodes, which is different from this article. In this section, we show that using the shortest three-path (will be defined later) to connect MIS nodes, a constant approximation ratio to CDS size and routing cost can both be guaranteed in edge-weighted graphs.

Definition 1 (independent set)

For a graph $G = (V, E)$ , an independent set (IS) of $G$ is a subset $I \in V$ , such that any pair of nodes in $I$ is not adjacent.

Definition 2 (MIS)

An IS of $G$ is said to be an MIS if it is not a subset of any other IS.

An MIS is also a DS. The MIS is used in the second algorithm because some previous works have studied and presented upper bounds of MISs to the size of a minimum CDS^{6,8,13–15,17,18} in UDGs and UBGs. According to these works, we can provide theoretical analysis for the size of the constructed CDS.

In the second algorithm, a node in the MIS is colored in black. For an MIS $M$ , any subset of $M$ is at most three hops away from the rest nodes in $M$ . Based on this observation, for a black MIS node $v$ , we denote other black MIS nodes within two-hops or three-hops to $v$ as neighboring black nodes of $v$ hereafter in this article. As the example shown in Figure 2, nodes $a$ and $e$ are neighboring black nodes of each other.

Figure 2.

The shortest path between $a$ and $e$ is ${a, b, c, d, e}$ . The shortest three-path between $a$ and $e$ is ${a, f, g, e}$ .

We connect each pair of neighboring black nodes by the shortest three-path between them, where the shortest three-path is defined as the shortest path between two nodes with at most three edges. We stress that a shortest three-path may not be the shortest path between two neighboring black nodes, because a four-hop path may be the shortest path between two three-hop black nodes. As shown in Figure 2, the shortest path between nodes $a$ and $e$ is ${a, b, c, d, e}$ . However, the shortest three-path between $a$ and $e$ is ${a, f, g, e}$ . We use shortest three-path in the second algorithm instead of shortest path to control its approximation ratio in terms of CDS size.

The second algorithm can be summarized as follows:

Phase 1: Construct an MIS and color its nodes in black.

Phase 2: Connect each pair of neighboring black nodes by the shortest three-path between them.

Algorithm 2 describes the second algorithm in a distributed pattern.

Algorithm 2. The second algorithm
Input: A graph $G = (V, E)$ . Every node in V is colored in white and assigned an unique positive integer identifier. Output: All black and blue nodes form a CDS of $G$ . 1: Each node sends its neighbor list to its neighbors, so that every node obtains the identifiers of its two-hop neighbors. When a node has received neighbor lists from all its neighbors, the node sends its two-hop neighbor list to its neighbors, so that every node obtains the identifiers of its three-hop neighbors. 2: Each node compares its identifier with its neighbors. If its identifier is the smallest, then the node colors itself black and sends a GREY message to its neighbors. Subsequently, go to Step 5. 3: Upon receiving a GREY message, a white node colors itself gray and sends an ERASED message to its neighbors. Go to Step 5. 4: If a white node has received the ERASED message from all of its neighbors, the node colors itself black and sends a GREY message to its neighbors. Go to Step 5. 5: The node sends an $(ID, FINIS H_{3})$ message to its neighbors, where $ID$ is its identifier. 6: Upon receiving an $(ID, FINIS H_{3})$ message, a node sends an $(ID, FINIS H_{2})$ message. Upon receiving an $(ID, FINIS H_{1})$ message, a node sends an $(ID, FINIS H_{1})$ message. 7: If a node has colored itself in black and the node has received an $(ID, FINIS H_{i}) (i = 1 or 2 or 3)$ message from all of its neighbors within three-hops, then the node sends an $(ID, CONNEC T_{1})$ message to its neighbors, where ID is its identifier. 8: Upon receiving an $(I D_{u}, CONNEC T_{1})$ message, a node sends an $(I D_{u}, CONNEC T_{2}, ID)$ message, where ID is its identifier. Upon receiving an $(I D_{u}, CONNEC T_{2}, I D_{v})$ message, a node sends an $(I D_{u}, CONNEC T_{3}, I D_{v}, ID)$ message, where ID is its identifier. 9: When a black node t is the first time to receive an $(I D_{u}, CONNEC T_{2}, I D_{v})$ or an $(I D_{u}, CONNEC T_{3}, I D_{w}, I D_{v})$ message with $I D_{u}$ as its first item and $I D_{u} > I D_{v}$ , then node $t$ (1) drops the rest messages with first item $I D_{u}$ , (2) colors node $v$ in blue, and (3) sends a message to $v$ to color $w$ in blue if the received message has four items.

Algorithm 2. The second algorithm

Input: A graph

G = (V, E)

. Every node in V is colored in white and assigned an unique positive integer identifier.
Output: All black and blue nodes form a CDS of

G

.
1: Each node sends its neighbor list to its neighbors, so that every node obtains the identifiers of its two-hop neighbors. When a node has received neighbor lists from all its neighbors, the node sends its two-hop neighbor list to its neighbors, so that every node obtains the identifiers of its three-hop neighbors.
2: Each node compares its identifier with its neighbors. If its identifier is the smallest, then the node colors itself black and sends a GREY message to its neighbors. Subsequently, go to Step 5.
3: Upon receiving a GREY message, a white node colors itself gray and sends an ERASED message to its neighbors. Go to Step 5.
4: If a white node has received the ERASED message from all of its neighbors, the node colors itself black and sends a GREY message to its neighbors. Go to Step 5.
5: The node sends an

(ID, FINIS H_{3})

message to its neighbors, where $ID$ is its identifier.
6: Upon receiving an

(ID, FINIS H_{3})

message, a node sends an

(ID, FINIS H_{2})

message. Upon receiving an

(ID, FINIS H_{1})

message, a node sends an

(ID, FINIS H_{1})

message.
7: If a node has colored itself in black and the node has received an

(ID, FINIS H_{i}) (i = 1 or 2 or 3)

message from all of its neighbors within three-hops, then the node sends an

(ID, CONNEC T_{1})

message to its neighbors, where ID is its identifier.
8: Upon receiving an

(I D_{u}, CONNEC T_{1})

message, a node sends an

(I D_{u}, CONNEC T_{2}, ID)

message, where ID is its identifier. Upon receiving an

(I D_{u}, CONNEC T_{2}, I D_{v})

message, a node sends an

(I D_{u}, CONNEC T_{3}, I D_{v}, ID)

message, where ID is its identifier.
9: When a black node t is the first time to receive an

(I D_{u}, CONNEC T_{2}, I D_{v})

or an

(I D_{u}, CONNEC T_{3}, I D_{w}, I D_{v})

message with

I D_{u}

as its first item and

I D_{u} > I D_{v}

, then node

t

(1) drops the rest messages with first item

I D_{u}

, (2) colors node

v

in blue, and (3) sends a message to

v

to color

w

in blue if the received message has four items.

In Steps 1–6 of Algorithm 2, an MIS is constructed by the algorithm introduced in Alzoubi et al.³¹ The main idea of this MIS construction algorithm is if all neighbors of a node with larger identifiers have decided not to join the MIS, then the node decides to join the MIS. In Steps 5 and 6, a node sends the $(ID, FINIS H_{i}) (i = 1 or 2 or 3)$ message to inform its neighbors within three-hops that it has finished the first phase. When a black node finds that all of its neighbors within three-hops have finished the first phase, the node executes Steps 7–9 to add nodes in the shortest three-paths to the CDS.

Theorem 4

The black and blue nodes outputted from the second algorithm form a CDS of $G$ .

Proof

First, the black and blue nodes form a DS of $G$ because black nodes form an MIS of $G$ . Second, the blue nodes connect all the black nodes together. Therefore, the black and blue nodes form a CDS.

Performance analysis

Next, we show some theoretical analyses to evaluate the performance of the second algorithm. In order to analyze the latency of a CDS constructed by the second algorithm, we first introduce a fact as follows.

Fact 1

Given three adjacent nodes $a$ , $b$ , and $c$ in UDGs (or UBGs), then equation (5) holds

\begin{matrix} | (a, b) | \leq | (a, c) | + | (b, c) | \end{matrix}

(5)

Hereafter, in this article, for a set of black MIS nodes

\begin{matrix} {u_{k}, u_{k - 1}, \dots, u_{1}, u_{0}} \end{matrix}

(6)

where $u_{i + 1} (i = 0, 1, \dots, k - 1)$ is a neighboring black node of $u_{i}$ . We call equation (6) a black path, where $u_{i + 1}$ and $u_{i}$ are connected by the shortest three-path between them.

In fact, the second algorithm generates a CDS with all the black paths of $G$ in it. Theorem 5 proves that for any shortest path $P$ in $G$ , there exists a corresponding black path $P'$ to replace its routing and $| P' | < 6 | P | + 3 TR$ (equations (7) and (8)), where TR is the transmission range of nodes as aforementioned.

Theorem 5

For any two nodes $u \in G$ and $v \in G$ , $P = {n_{0}, n_{1}, n_{2}, \dots, n_{k - 1}, n_{k}}$ is the shortest path between $u$ and $v$ in $G$ , where $n_{0} = u$ and $n_{k} = v$ . There exists a black path $P'$ between black nodes u′ and v′, where u′ is adjacent to $u$ , v′ is adjacent to $v$ , and

If $k$ is an even number, then

\begin{matrix} | P' | < 6 | P | \end{matrix}

(7)

If k is an odd number, then

\begin{matrix} | P' | < 6 | P | + 3 TR \end{matrix}

(8)

Proof

We use $m_{i} (i = 0, 1, \dots, k)$ to denote a black node in the MIS adjacent to $n_{i}$ , where $m_{0} = u'$ and $m_{k} = v'$ (as shown in Figure 3).

When $k$ is an even number (as shown in Figure 3(a)), since $P$ is the shortest path between $u$ and $v$ , for any $(i = 0, 2, \dots, k - 2)$ , we have that $| {n_{i}, n_{i + 2}} | > 2 TR$ (according to Fact 1, otherwise $n_{i}$ and $n_{i + 2} (i = 0, 2, \dots, k - 2)$ would be adjacent, so that $P$ is not the shortest path between $u$ and $v$ ). Therefore

\begin{matrix} | P | > (\frac{k}{2}) TR \end{matrix}

For any $i = {0, 1, \dots, k - 1}$ , it can be seen that $m_{i}$ and $m_{i + 1}$ are at most three-hops away in $G$ . That is, $m_{i}$ and $m_{i + 1}$ are neighboring black nodes. Thus, we find a black path

\begin{matrix} P' = {u', m_{1}, m_{2}, \dots, m_{k - 1}, v'} \end{matrix}

such that

\begin{matrix} | P' | \leq k \cdot 3 TR < 6 | P | \end{matrix}

When $k$ is an odd number (as shown in Figure 3(b)), since $P$ is the shortest path between $u$ and $v$ , for any $(i = 0, 2, \dots, k - 3)$ , we have that $| {n_{i}, n_{i + 2}} | > 2 TR$ (otherwise $n_{i}$ and $n_{i + 2} (i = 0, 2, \dots, k - 2)$ would be adjacent, so that $P$ is not the shortest path between $u$ and $v$ ). Therefore

\begin{matrix} | P | > (\frac{k - 1}{2}) TR \end{matrix}

For any $i = {0, 1, \dots, k - 1}$ , $m_{i}$ and $m_{i + 1}$ are neighboring black nodes. Thus, we find a black path

\begin{matrix} P' = u', m_{1}, m_{2}, \dots, m_{k - 1}, v' \end{matrix}

such that

\begin{matrix} | P' | \leq k \cdot 3 TR < 6 | P | + 3 TR \end{matrix}

This completes the proof.

Figure 3.

On the proof of Theorem 5. $m_{i} (i = 0, 1, \dots, k)$ are MIS nodes: (a) k is an even number and (b) k is an odd number.

Corollary 1

For any two nodes in $G$ with minimum latency $L$ , routing with the CDS constructed by the second algorithm increases the minimum latency to at most $6 L + 5 L_{\max}$ .

Proof

The second algorithm constructs a CDS with all the black paths in it. According to Theorem 5, the corollary holds.

To analyze the approximation ratio of the second algorithm in terms of CDS size, we introduce some lemmas first.

Lemma 1

In a UDG, a node has at most 41 independent neighbors within three-hops.

Proof

As shown in Figure 4, the problem of the lemma can be solved referencing a classical mathematical problem, the circle packing in a circle problem. Observe that the result of the lemma equals to the following problem: how many unit circles can be packed in a bigger circle with radius 7? Alzoubi et al.³¹ proved an upper bound 47 of this problem. Du et al.²⁸ improved this result to 43. We find that this result can be further improved to 41 according to Gáspár and Tarnai.⁴⁴ We refer to Gáspár and Tarnai⁴⁴ for readers interested in detail.

Figure 4.

The problem of Lemma 1 is equivalent to another problem that packing as many circles with 0.5 radius as possible in a bigger circle with radius 3.5. And it is further equivalent to the problem that packing as many unit circles as possible in a bigger circle with radius 7.

Lemma 2

In a UBG, a node has at most 267 independent neighbors within three-hops.

Proof

As the proof of Lemma 1, the result of this lemma can be proved by the sphere packing in a sphere problem. The problem of this lemma is equivalent to the problem: how many unit spheres can be packed in a bigger sphere with radius 7. This problem has an upper bound 267. About this result, we refer to Bezdek⁴⁵ for interested readers.

Lemma 3

If $C$ is a CDS constructed by the second algorithm, then $| C |$ has a bound as equation (9)

\begin{matrix} | C | \leq k | M | \end{matrix}

(9)

where $M$ is the MIS constructed in the first phase, $k$ is 41 in UDGs and $k$ is 267 in UBGs.

Proof

According to Lemmas 1 and 2, there are at most $k - 1$ neighboring black nodes for a black node. Observe that there are at most $((k - 1) / 2) | M |$ pairs of neighboring black nodes. In the second algorithm, each pair of neighboring black nodes is connected by at most two intermediate blue nodes in the shortest three-path between them. Therefore, there are at most $(k - 1) | M |$ blue nodes in the second algorithm. Hence, there are at most $(k - 1) | M | + | M | = k | M |$ nodes in $C$ .

Lemma 4

In UDGs, for any MIS $M$ , $| M |$ has a bound as equation (10)¹⁷

\begin{matrix} | M | \leq 3.399 op t_{CDS} + 4.874 \end{matrix}

(10)

where $op t_{CDS}$ is the size of a minimum CDS.

Proof

See Du and Du.¹⁷

Lemma 5

In UBGs, for any MIS $M$ , |M| has a bound as equation (11)⁸

\begin{matrix} | M | \leq 10.917 op t_{CDS} + 1.083 \end{matrix}

(11)

where $op t_{CDS}$ is the size of a minimum CDS.

Proof

See Kim et al.⁸

Theorem 6 illustrates that the second algorithm guarantees constant approximation ratios in UDGs (equation (12)) and UBGs (equation (13)).

Theorem 6

If $C$ is a CDS constructed by the second algorithm, then in UDGs

\begin{matrix} | C | \leq 140 op t_{CDS} + 200 \end{matrix}

(12)

and in UBGs

\begin{matrix} | C | \leq 2915 op t_{CDS} + 290 \end{matrix}

(13)

where $op t_{CDS}$ is the size of a minimum CDS.

Proof

The theorem holds according to Lemmas 3–5.

Theorem 7

The time complexity and message complexity of the second algorithm are $O (n)$ .

Proof

Steps 1–6 of the second algorithm use the algorithm in Alzoubi et al.³¹ for MIS construction, which has time complexity and message complexity $O (n)$ . In addition, in Steps 7–9 of the second algorithm, only local information of a node is used. Therefore, the time complexity and message complexity of the second algorithm are both $O (n)$ .

The third algorithm

Algorithm description

Observe that the approximation ratio in terms of CDS size of the second algorithm is big. In this section, we show by the third algorithm that through further reducing the redundant nodes of the CDS constructed by the second algorithm, a smaller CDS can be obtained. The third algorithm guarantees 10.197-approximation in terms of CDS size in UDGs. Although the third algorithm cannot guarantee constant approximation to the minimum latency between an arbitrary pair of nodes as the second algorithm, it provides a 12-approximation in terms of CDS diameter, which ensures that the latency between nodes will not be too bad because of using the VB.

The basic idea of the third algorithm is to flood a dominating tree through the black paths obtained from the second algorithm. The third algorithm can be summarized as follows:

Phase 1: Execute the second algorithm to obtain a subgraph of $G$ .

Phase 2: Flood a message in the subgraph to construct a dominating tree of $G$ .

Details of the third algorithm are presented in Algorithm 3.

Algorithm 3. The third algorithm
Input: A graph $G = (V, E)$ outputted by the second algorithm. CDS nodes are colored in black or blue, and other nodes are colored in gray. Output: All yellow nodes form a CDS of $G$ . 1: Use a leader selection algorithm to choose $r \in V$ . $r$ sends an $(INVIT E_{3})$ message and colors itself in yellow. 2: Upon receiving an $(INVIT E_{3})$ message, a blue node sends an $(INVIT E_{2}, ID)$ message, where ID is its identifier. Upon receiving an $(INVIT E_{2}, I D_{v})$ message, a blue node sends an $(INVIT E_{1}, I D_{v}, ID)$ message, where ID is its identifier. 3: Upon receiving an $(INVIT E_{2}, I D_{v})$ message or an $(INVIT E_{1}, I D_{u}, I D_{v})$ message, a black node (1) colors itself in yellow, (2) colors node $v$ in yellow, and (3) sends a message to $v$ to color $u$ in yellow if the received message has three items.

Algorithm 3. The third algorithm

Input: A graph

G = (V, E)

outputted by the second algorithm. CDS nodes are colored in black or blue, and other nodes are colored in gray.
Output: All yellow nodes form a CDS of

G

.
1: Use a leader selection algorithm to choose

r \in V

r

sends an

(INVIT E_{3})

message and colors itself in yellow.
2: Upon receiving an

(INVIT E_{3})

message, a blue node sends an

(INVIT E_{2}, ID)

message, where ID is its identifier. Upon receiving an

(INVIT E_{2}, I D_{v})

message, a blue node sends an

(INVIT E_{1}, I D_{v}, ID)

message, where ID is its identifier.
3: Upon receiving an

(INVIT E_{2}, I D_{v})

message or an

(INVIT E_{1}, I D_{u}, I D_{v})

message, a black node (1) colors itself in yellow, (2) colors node

v

in yellow, and (3) sends a message to

v

to color

u

in yellow if the received message has three items.

Theorem 8

The yellow nodes outputted by the third algorithm form a CDS of $G$ .

Proof

The yellow nodes include all the MIS nodes, so that they form a DS of $G$ . Every MIS node is connected to the leader node by some yellow nodes, so that the yellow nodes form a CDS of $G$ .

Performance analysis

Theorem 9 shows that the CDS obtained from the third algorithm has a 12-approximation ratio in terms of diameter (equation (14)).

Theorem 9

If $C$ is a CDS obtained from the third algorithm, then

\begin{matrix} Diam (C) < 12 D_{opt} + 2 TR \end{matrix}

(14)

where $D_{opt}$ is the diameter of any optimal CDS of $G$ .

Proof

For any MIS node $v$ , the third algorithm constructs a CDS C with a black path ${u_{0}, u_{1}, \dots, u_{k - 1}, u_{k}}$ , where $u_{0} = v and u_{k} = r$ . Assume the shortest path in $G$ between $r$ and $v$ is ${n_{0}, n_{1}, \dots, n_{k - 1}, n_{k}}$ , where $n_{0} = v$ and $n_{k} = r$ .

When $k$ is an even number (as Figure 5(a)), we have that

\begin{matrix} | {n_{0}, n_{1}, \dots, n_{k - 1}, n_{k}} | > k / 2 TR \end{matrix}

according to the proof of Theorem 5. Suppose $m_{i} (i = 1, 2, \dots, k - 1)$ is a black neighbor of $n_{i}$ . Then, $v$ is at most two-hop neighbor of $m_{1}$ , $r$ is at most two-hop neighbor of $m_{k - 1}$ , and $m_{i} (i = 1, 2, \dots, k - 2)$ is at most three-hop neighbor of $m_{i + 1}$ . Therefore, for the black path ${v, m_{1}, \dots, m_{k - 1}, r}$ , we have

\begin{array}{l} | {v, m_{1}, …, m_{k - 1}, r} | \leq 2 T R \\ + k - 2 \cdot 3 T R + 2 T R = (3 k - 2) T R \end{array}

Figure 5.

On the proof of Theorem 9. $m_{i} (i = 0, 1, \dots, k - 1)$ are MIS nodes: (a) k is an even number and (b) k is an odd number.

That is

\begin{matrix} | {v, m_{1}, \dots, m_{k - 1}, r} | < 6 | {v, n_{1}, \dots, n_{k - 1}, r} | - 2 TR \end{matrix}

2. When $k$ is an odd number (as Figure 5(b)), we have that

\begin{matrix} | {n_{0}, n_{1}, \dots, n_{k - 1}, n_{k}} | > (k - 1) / 2 TR \end{matrix}

according to the proof of Theorem 5. Similarly to the proof in (1), for the black path ${v, m_{1}, \dots, m_{k - 1}, r}$ , we have that

\begin{matrix} | {v, m_{1}, \dots, m_{k - 1}, r} | \leq (3 k - 2) TR \end{matrix}

That is

\begin{matrix} | {v, m_{1}, \dots, m_{k - 1}, r} | < 6 | {v, n_{1}, \dots, n_{k - 1}, r} | + TR \end{matrix}

Overall, we have

\begin{matrix} | {v, m_{1}, \dots, m_{k - 1}, r} | < 6 | {v, n_{1}, \dots, n_{k - 1}, r} | + TR \end{matrix}

Now, we prove by contradiction that

\begin{matrix} | {v, u_{1}, \dots, u_{k - 1}, r} | \leq | {v, m_{1}, \dots, m_{k - 1}, r} | \end{matrix}

Assume that

\begin{matrix} | {v, u_{1}, \dots, u_{k - 1}, r} | > | {v, m_{1}, \dots, m_{k - 1}, r} | \end{matrix}

then $v$ will get the INVITE message from $m_{1}$ before $u_{1}$ . According to the algorithm, $m_{1} = u_{1}$ . Thus

\begin{matrix} | {v, u_{1}, u_{2}, \dots, u_{k - 1}, r} | > | {v, u_{1}, u_{2}, \dots, m_{k - 1}, r} | \end{matrix}

Similarly, we have $m_{i} = u_{i} (i = 1, 2, \dots, k - 1)$ . This completes the proof that

\begin{matrix} | {v, u_{1}, \dots, u_{k - 1}, r} | \leq | {v, m_{1}, \dots, m_{k - 1}, r} | \end{matrix}

Therefore

\begin{matrix} | {v, u_{1}, …, u_{k - 1}, r} | < 6 | \\ {v, n_{1}, …, n_{k - 1}, r} | + T R \leq 6 D_{o p t} + T R \end{matrix}

In addition, for another MIS node v′, there exists a black path ${v', u_{1'}, \dots, u_{k - 1^{'}}, r}$ , such that

\begin{matrix} | {v', u_{1'}, \dots, u_{k - 1'}, r} | < 6 D_{opt} + TR \end{matrix}

That is, for any CDS nodes v′ and $v$ , there exists a black path ${v', u_{1'}, \dots, u_{k - 1'}, r, u_{k - 1}, \dots, u_{1}, v}$ , such that

\begin{matrix} | {v', u_{1'}, \dots, u_{k - 1'}, r, u_{k - 1}, \dots, u_{1}, v} | < 12 D_{opt} + 2 TR \end{matrix}

This completes the proof.

Theorem 10 shows that the third algorithm guarantees constant approximation ratio in terms of CDS size. We first prove Lemma 6 for the proof of Theorem 10.

Lemma 6

In UDGs or UBGs, if $C$ is a CDS constructed by the third algorithm, then $| C |$ has a bound as shown in equation (15)

\begin{matrix} | C | \leq 3 | M | - 2 \end{matrix}

(15)

where $M$ is the MIS composed of the black nodes.

Proof

The third algorithm constructs a dominating tree with the black paths. In this dominating tree, each non-leader MIS node is connected to its parent MIS node by the shortest three-path between them. Therefore, there are at most $2 (| M | - 1)$ blue nodes constructed by the third algorithm. Hence

\begin{matrix} | C | \leq 2 (| M | - 1) + | M | = 3 | M | - 2 \end{matrix}

Theorem 10

If $C$ is a CDS constructed by the third algorithm, then in UDGs, $| C |$ has a bound as shown in equation (16)

\begin{matrix} | C | \leq 10.197 op t_{CDS} + 12.622 \end{matrix}

(16)

and in UBGs, $| C |$ has a bound as shown in equation (17)

\begin{matrix} | C | \leq 32.751 op t_{CDS} + 1.249 \end{matrix}

(17)

where $op t_{CDS}$ is the size of a minimum CDS.

Proof

According to Lemmas 4–6, we have that, in UDGs

| C | \leq 3 (3.399 o p t_{C D S} + 4.874) - 2 = 10.197 o p t_{C D S} + 12.622

and in UBGs

| C | \leq 3 (10.917 o p t_{C D S} + 1.083) - 2 = 32.751 o p t_{C D S} + 1.249

Theorem 11

The time complexity and message complexity of the third algorithm are $O (n)$ .

Proof

The third algorithm spends constant operations to add an MIS node to the dominating tree. Thus, the theorem holds.

Simulation

In our research, we carried out extensive simulations to test the performance of our algorithms. Among the simulation tools for USNs,⁴⁶ we use the UAN framework of the ns-3 simulator (version 3.26) in this article. The UAN framework provides a Thorp propagation model to simulate underwater acoustic communications. The simulation parameters are presented in Table 2. A 2D network is modeled as a set of nodes randomly deployed in a $1000 \times 1000 m^{2}$ plane and a 3D network is model as a set of nodes in a $1000 \times 1000 \times 1000 m^{3}$ region. The nodes follow a Poisson distribution. We assumed that all the nodes have the same transmission range and form a connected graph. We tested the algorithms with different transmission ranges and with different number of nodes. For each combination of node number and transmission range, 100 network instances were investigated and the results were averaged.

Table 2.

Simulation parameters.

Parameters	Values
Simulator	Ns-3 (version 3.26)
Transmission range	200–400 m
Side length of territory	1000 m
Number of nodes	100–500
Nodes distribution	Poisson distribution
Propagation model	Thorp propagation model

Since existing routing cost optimization CDS algorithms measure only hop-distances among nodes and their implementations are hard to be extended to edge-weighted graphs, we use the algorithm proposed by Wan et al.,^13,15 which is denoted as the Size-Optimal Algorithm (SOA), hereafter, in this article, for performance comparison. The SOA has the best-known approximation ratio in UDGs following the two-phased MIS-based approaches. The SOA constructs a two-hop MIS in the first phase and generates a dominating tree in the second phase. The approximation ratio is controlled because a two-hop MIS can be connected by almost the same number of intermediate nodes.

In addition to CDS size that is used to measure the performance of a VB, two other parameters, diameter and average routing path length (ARPL), are used to evaluate the communication latency of the network. ARPL was first introduced in Kim et al.,²⁹ which is defined as the average of all routing path lengths in the CDS. Simulation results indicate that our algorithms clearly improved the communication latency of the network with controlled VB size. The details are presented as follows.

Performance versus the number of nodes

The effects of the number of nodes in 2D networks are presented in this section. The results are shown in Figure 6. The number of nodes ranges from 100 to 500 nodes. The transmission range of nodes is fixed at 250 m. The size, diameter, and ARPL are, respectively, presented in Figure 6(a)–(c).

Figure 6.

Performance versus the number of nodes in 2D networks. With different numbers of nodes, the performance of our algorithms is compared with SOA in terms of: (a) size of the CDS, (b) diameter of the CDS, and (c) ARPL of the CDS.

As shown in Figure 6(a), in terms of CDS size, the third algorithm and SOA perform closely, and they clearly outperform the first and the second algorithms. In addition, the CDS size of the third algorithm and SOA increases little with the number of nodes, which indicates good scalability of them in terms of CDS size. For the first algorithm, the size of the CDS increases rapidly with the number of nodes in the network. The CDS size of the second algorithm also increases clearly with the number of nodes. This is reasonable because the first algorithm guarantees no performance to CDS size and the approximation ratio of the second algorithm in terms of CDS size is large.

For CDS diameter and ARPL, as shown in Figure 6(b) and (c), the first algorithm performs the best and SOA performs the worst. The proposed algorithms in this article perform closely, and they significantly outperform the SOA. In addition, it can be seen that the diameter and ARPL of CDS do not change clearly with the number of nodes. Thus indicates that the number of nodes in the network should not affect the decision to select the CDS construction algorithm while concerning the network communication latency.

In all, the third algorithm is promising to be used for CDS construction in USNs due to its good performance on all of the size, diameter, and ARPL of CDS. However, if the number of nodes in the network is not large, the first and the second algorithm can also be concerned to be used because their performance gap to the third algorithm and SOA is not very big according to Figure 6(a). If the network manager is quite aware of the network communication latency, then SOA is not suggested to be used because it will greatly increase the network latency. In fact, a large latency means high energy consumption to achieve the communication tasks among nodes.

Performance versus transmission range

In the simulation, the effects of the transmission range to the performance of the algorithms are also tested in 2D networks, and the results are shown in Figure 7. In this section, the number of nodes in the network is fixed at 200. The transmission range is selected from 200 to 400 m.

Figure 7.

Performance versus transmission range in 2D networks. With different transmission ranges, the performance of our algorithms is compared with SOA in terms of: (a) size of the CDS, (b) diameter of the CDS, and (c) ARPL of the CDS.

As shown in Figure 7(a), the CDS size decreases with the transmission range for all the algorithms. This is reasonable because when the transmission range increases, the network density also increases, so that less nodes are required to form a CDS. The first algorithm performs the worst for different transmission ranges. The second algorithm also does not perform well with small transmission ranges, but the performance gap between the second algorithm and the third algorithm becomes small when the transmission range increases. The third algorithm and the SOA perform well, which is reasonable because the third algorithm and the SOA achieve good approximation ratio in terms of CDS size.

For the diameter and ARPL, it can be seen that the proposed algorithms significantly outperform the SOA as shown in Figure 7(b) and (c). Although the performance gap between SOA and the proposed algorithms becomes smaller when the transmission range increases, the performance gap is still clear when the transmission range is close to 400 m.

In all, the third algorithm in this article performs well in terms of both CDS size and network latency. When the transmission range is big, the second algorithm is also a promising choice because its performance on CDS size becomes close to the third algorithm and the SOA.

The simulation results in 2D networks are in good agreement with the theoretical analyses presented before. For example, SOA guarantees the best approximation ratio in terms of CDS size, but it cannot guarantee the performance of network latency. The first algorithm and the second algorithm cannot guarantee good performance ratio in terms of CDS size, but they guarantee very good performance in terms of CDS diameter or ARPL. The third algorithm achieves a good trade-off between CDS size and latency and guarantees good performance for both CDS size and network latency.

Performance in 3D networks

The simulation results of 3D networks are presented in Figure 8. In Figure 8(a1), (a2), and (a3), we fix the transmission range at 200 m, and test the algorithm performance with different number of nodes in the network. In Figure 8(b1), (b2), and (b3), we fix the number of nodes at 200, and test the algorithm performance with different transmission ranges.

Figure 8.

Algorithm performance in 3D networks: in (a1), (a2), and (a3), the performance of our algorithms is compared with SOA with different numbers of nodes and in (b1), (b2), and (b3), the performance of our algorithms is compared with SOA with different transmission ranges.

The simulation results of 3D networks are similar to the results of 2D networks. As shown in Figure 8, the third algorithm performs well for all size, diameter, and ARPL of the CDS. The first and the second algorithm perform well in terms of CDS diameter and ARPL, but they cannot perform well in terms of CDS size when the number of nodes or the transmission range is large. These results are also in good agreement with the theoretical analyses presented before.

Conclusion

Communication latency greatly influences the performance of USNs because of the limited propagation speed of acoustic waves. The use of VB aggravates this problem because restricting routing tasks to backbone nodes inevitably increases length of a routing path. In this article, we use the weight of an edge to represent latency between sensor nodes. A USN is abstracted as an edge-weighted graph. Under such model, we suggested to control not only size but also the routing path lengths of a CDS as a VB. Therefore, we devised three algorithms to optimize both size and routing path length of a CDS.

The first algorithm guarantees two-approximation to CDS diameter and guarantees no constant approximation to CDS size. For a pair of nodes with minimum latency $L$ , the second algorithm generates a CDS which provides a routing path with latency at most $6 L + 5 L_{\max}$ . The second algorithm has approximation ratio 140 in UDGs and approximation ratio 2915 in UBGs to the size of a CDS. The third algorithm constructs a CDS with diameter at most $12 D_{opt} + 2 TR$ , where $D_{opt}$ is the diameter of any optimal CDS of $G$ . The third algorithm has approximation ratio 10.197 in UDGs and approximation ratio 32.751 in UBGs to CDS size.

Extensive simulations have been conducted and the results show that the proposed algorithms can achieve good trade-off between the backbone size and network communication latency.

Footnotes

Handling Editor: Miguel Ardid

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (NSFC) (grant nos. 61702298, 61602205, 51627805, and 61170004), National Key Research and Development Program of China (grant nos. 2016YFB0201503 and 2016YFB0701101), Specialized Research Fund for the Doctoral Program of Higher Education (20130061110052), Major Special Research Project of Science and Technology Department of Jilin Province (20160203008GX), Key Science and Technology Research Project of Science and Technology Department of Jilin Province (20140204013GX), and Graduate Innovation Fund of Jilin University.

References

Noh

Lee

et al . Hydrocast: pressure routing for underwater sensor networks. IEEE T Veh Technol 2016; 65(1): 333–347.

Liu

Wang

Cui

et al . A joint time synchronization and localization design for mobile underwater sensor networks. IEEE T Mobile Comput 2016; 15(3): 530–543.

Misra

Ojha

Mondal

. Game-theoretic topology control for opportunistic localization in sparse underwater sensor networks. IEEE T Mobile Comput 2015; 14(5): 990–1003.

Lloret

Sendra

Ardid

et al . Underwater wireless sensor communications in the 2.4 GHz ISM frequency band. Sensors 2012; 12(4): 4237.

Akyildiz

Pompili

Melodia

. Underwater acoustic sensor networks: research challenges. Ad Hoc Netw 2010; 3(3): 257–279.

Gao

Chen

. A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks. Theor Comput Sci 2015; 607: 363–380.

Jia

et al . Minimum connected dominating set construction in wireless networks under the beeping model. In: IEEE conference on computer communications (INFOCOM’15), Hong Kong, China, 26–28 April 2015, pp.972–980. New York: IEEE.

Kim

Zhang

et al . A better approximation algorithm for computing connected dominating sets in unit ball graphs. IEEE T Mobile Comput 2010; 9(8): 1108–1118.

Zhang

Shi

. Approximation algorithm for minimum weight fault-tolerant virtual backbone in homogeneous wireless sensor network. In: IEEE conference on computer communications (INFOCOM’15), Hong Kong, China, 26–28 April 2015, pp.1080–1085. New York: IEEE.

10.

Liu

Wang

Peng

et al . Suave: swarm underwater autonomous vehicle localization. In: IEEE conference on computer communications (INFOCOM’14), Toronto, ON, Canada, 27–30 April 2014. New York: IEEE.

11.

Wan

. Connected dominating set: theory and applications, vol. 77. Berlin: Springer Science+Business Media, 2012.

12.

Guha

Khuller

. Approximation algorithms for connected dominating sets. Algorithmica 1998; 20(4): 374–387.

13.

Wan

Alzoubi

Friede

. Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Netw Appl 2004; 9(2): 141–149.

14.

Jia

et al . Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor Comput Sci 2006; 352(1): 17.

15.

Wan

Wang

Yao

. Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. In: IEEE international conference on distributed computing systems (ICDCS’08), Beijing, China, 17–20 June 2008, pp.337–344. New York: IEEE.

16.

Wan

Yao

. Tighter approximation bounds for minimum CDS in unit disk graphs. Algorithmica 2011; 61(4): 1000–1021.

17.

. A new bound on maximum independent set and minimum connected dominating set in unit disk graphs. J Comb Optim 2015; 30(4): 1173–1179.

18.

Bai

Che

Bai

et al . Maximal independent sets in heterogeneous wireless ad hoc networks. IEEE T Mobile Comput 2016; 15(8): 2023–2033.

19.

Wang

Wan

Yao

. Minimum CDS in multihop wireless networks with disparate communication ranges. IEEE T Mobile Comput 2013; 12(5): 909–916.

20.

Thai

Wang

Liu

et al . Connected dominating sets in wireless networks with different transmission ranges. IEEE T Mobile Comput 2007; 6(7): 721–730.

21.

Dai

. An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE T Parall Distr 2004; 15(10): 908–920.

22.

Dai

Yang

. Iterative local solutions for connected dominating set in ad hoc wireless networks. IEEE T Comput 2008; 57(5): 702–715.

23.

Yang

Dai

. Efficient directional network backbone construction in mobile ad hoc networks. IEEE T Parall Distr 2008; 19(12): 1601–1613.

24.

Ding

Willson

et al . Efficient virtual backbone construction with routing cost constraint in wireless networks using directional antennas. IEEE T Mobile Comput 2012; 11(7): 1102–1112.

25.

Ding

Gao

et al . Distributed construction of connected dominating sets with minimum routing cost in wireless networks. In: IEEE international conference on distributed computing systems (ICDCS’10), Genoa, 21–25 June 2010, pp.448–457. New York: IEEE.

26.

Ding

Willson

et al . Efficient algorithms for topology control problem with routing cost constraints in wireless networks. IEEE T Parall Distr 2011; 22(10): 1601–1609.

27.

Liu

Huang

et al . Performance-guaranteed strongly connected dominating sets in heterogeneous wireless sensor networks. In: IEEE conference on computer communications (INFOCOM’16), San Francisco, CA, 10–15 April 2016, pp.1–9. New York: IEEE.

28.

et al . CDS-based virtual backbone construction with guaranteed routing cost in wireless sensor networks. IEEE T Parall Distr 2013; 24(4): 652–661.

29.

Kim

et al . Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE T Parall Distr 2009; 20(2): 147–157.

30.

Pan

et al . Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks. Theor Comput Sci 2013; 507(7): 2–16.

31.

Alzoubi

Wan

Frieder

. Message-optimal connected dominating sets in mobile ad hoc networks. In: ACM international symposium on mobile ad hoc networking and computing (MOBIHOC’02), Lausanne, 9–11 June 2002, pp.157–164. New York: IEEE.

32.

Garg

Koenemann

. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J Comput 2008; 37(2): 630–652.

33.

Huang

Gao

Zhang

et al . A better constant-factor approximation for weighted dominating set in unit disk graph. J Comb Optim 2009; 18(2): 179–194.

34.

Zou

Wang

et al . New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theor Comput Sci 2011; 412(3): 198–208.

35.

Dai

. On constructing k-connected k-dominating set in wireless ad hoc and sensor networks. J Parallel Distr Com 2006; 66(7): 947–958.

36.

Thai

Zhang

Tiwari

et al . On approximation algorithms of k-connected m-dominating sets in disk graphs. Theor Comput Sci 2007; 385(13): 49–59.

37.

Shang

Yao

Wan

et al . On minimum m-connected k-dominating set problem in unit disc graphs. J Comb Optim 2008; 16(2): 99–106.

38.

Kim

Wang

et al . A new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks. In: IEEE conference on computer communications (INFOCOM’10), San Diego, CA, 15–19 March 2010, pp.1–9. New York: IEEE.

39.

Wang

Liu

Kim

et al . A better constant approximation for minimum 3-connected m-dominating set problem in unit disk graph using tutte decomposition. In: IEEE conference on computer communications (INFOCOM’15), Hong Kong, China, 26–28 April 2015, pp.1796–1804. New York: IEEE.

40.

Zhang

Zhou

et al . Performance-guaranteed approximation algorithm for fault-tolerant connected dominating set in wireless networks. In: IEEE conference on computer communications (INFOCOM’16), San Francisco, CA, 10–15 April 2016, pp.1–8. New York: IEEE.

41.

Cardei

Dai

et al . Extended dominating set and its applications in ad hoc networks using cooperative communication. IEEE T Parall Distr 2006; 17(8): 851–864.

42.

Dai

Xin

. Virtual backbone construction for cognitive radio networks without common control channel. In: IEEE conference on computer communications (INFOCOM’13), Turin, 14–19 April 2013, pp.1456–1464. New York: IEEE.

43.

Dai

Xin

. Efficient virtual backbone construction without a common control channel in cognitive radio networks. IEEE T Parall Distr 2014; 25(12): 3156–3166.

44.

Gáspár

Tarnai

. Upper bound of density for packing of equal circles in special domains in the plane. Civil Eng 2000; 44(1): 13–32.

45.

Bezdek

. Sphere packings revisited. Eur J Combin 2006; 27(6): 864–883.

46.

Das

Thampi

. Simulation tools for underwater sensor networks: a survey. Netw Protoc Algorithm 2017; 8(4): 41–55.

Latency-optimal virtual backbone construction with acoustic communication in underwater sensor networks

Abstract

Keywords

Introduction

Related work

CDS algorithms optimizing the size

CDS algorithms optimizing the routing cost

Algorithms optimizing other characteristics of a CDS

Discussion

Problem statements

The first algorithm

Algorithm description

Theorem 1

Proof

Performance analysis

Theorem 2

Proof

Theorem 3

Proof

The second algorithm

Algorithm description

Definition 1 (independent set)

Definition 2 (MIS)

Theorem 4

Proof

Performance analysis

Fact 1

Theorem 5

Proof

Corollary 1

Proof

Lemma 1

Proof

Lemma 2

Proof

Lemma 3

Proof

Lemma 4

Proof

Lemma 5

Proof

Theorem 6

Proof

Theorem 7

Proof

The third algorithm

Algorithm description

Theorem 8

Proof

Performance analysis

Theorem 9

Proof

Lemma 6

Proof

Theorem 10

Proof

Theorem 11

Proof

Simulation

Performance versus the number of nodes

Performance versus transmission range

Performance in 3D networks

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References