Interference-aware spatio-temporal link scheduling for long delay underwater sensor networks

In underwater sensor networks (UWSNs), acoustic communication is commonly used unlike that in terrestrial wireless networks. The long propagation delay of acoustic signals causes spatio-temporal uncertainty, which makes the link scheduling in UWSNs a challenging problem. To describe the propagation delays of the transmission links and deal with the spatio-temporal uncertainty, we construct a so called slotted spatio-temporal conflict graph. We propose efficient scheduling algorithms with constant approximation ratios to the optimum solutions. We consider both unified and weighted traffic load scenarios when designing the scheduling algorithms. In the weighted traffic load scenario, we consider the scheduling with and without the consecutive constraint. Simulations validate our theoretical results, and show the efficiency of our proposed algorithms.