Short paper: Token-based data collection protocols for multi-hop underwater acoustic sensor networks

Abstract

We propose two novel token-based data collection protocols for multi-hop underwater acoustic sensor networks (UW-ASNs). The proposed protocols, namely the tree-based protocol and the ring-based protocol, use tokens to guarantee contention-free medium access for each transmission and reliable collection of data from each node. For the tree-based protocol, we propose a depth-first traversal of a Minimal Spanning Tree (MST) rooted at the sink node, providing a constant factor two approximation for the optimal total data collection delay. For the ring-based protocol, we formulate the problem as a Traveling Salesman Problem (TSP), and use the Christofides Heuristic algorithm to prove a constant factor 1.5 approximation to the optimal solution. We also argue that the tree-based protocol is more suitable for large-scale networks, and the ring-based protocol for small-scale networks. Copyright 2009 ACM.