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

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.