Topology-Efficient Discovery: A Topology Discovery Algorithm for Underwater Acoustic Networks

In this paper, we describe topology-efficient discovery (TED), the first designated topology-efficient discovery algorithm for underwater acoustic networks. Topology information is essential for network operations. By knowing the network topology, information sources can determine destination nodes and routing possibilities for their packets and schedule transmissions accordingly. It is therefore of interest to use a schedule for topology discovery to be used at the early stages of network operation. Such schedule must efficiently perform topology discovery and also guarantee a convergence time at the end of which topology discovery is complete and the network switches to its steady-state scheduling protocol. Considering this need, we offer a TED algorithm aimed to discover acoustic links and to assess their reliability. Designed to reduce the time overhead posed by the topology discovery phase, TED allows nodes to share time slots while controlling the number of passible collisions such that the delay of the topology discovery process is minimized. TED also discovers scheduling conflicts by discovering node pairs whose transmissions block one another, often referred to as near-far node pairs (NFNPs). Information about NFNPs can assist for power control or to increase channel utilization if interference cancelation techniques are employed. TED is applicable for underwater networks consisting of modems whose transmission range is on the order of a few kilometer and above, and when the maximal distance between the nodes is known to be large or assumed equal to the modem's transmission range. Numerical results show that under these conditions, TED accurately detects the network topology in a much shorter time compared to benchmark methods. The results also show that, using TED, more packets are received, and thus the accuracy in determining the reliability of communication links increases. We also report results from a sea experiment demonstrating the applicability of TED and its benefits in a real-world scenario.