ST-MAC: Spatial-Temporal MAC Scheduling for Underwater Sensor Networks

Underwater Sensor Networks (UWSNs) have attracted a lot of attention recently. Since data in UWSNs are transmitted by acoustic signals, the characteristics of a UWSN are different from those of a terrestrial sensor network. In other words, the high propagation delay of acoustic signals in UWSNs causes Spatial-Temporal uncertainty, and makes transmission scheduling in UWSNs a challenging problem. Hence, in this paper, we propose a Spatial-Temporal MAC Scheduling protocol, called ST-MAC, which is designed to overcome spatial-temporal uncertainty based on TDMA-based MAC scheduling for energy saving and throughput improvement. We construct the Spatial-Temporal Conflict Graph (ST-CG) to describe the conflict delays among transmission links explicitly, and model ST-MAC as a new vertex coloring problem of ST-CG. We then propose a novel heuristic, called the Traffic-based One-step Trial Approach (TOTA), to solve the coloring problem. In order to obtain the optimal solution of the scheduling problem, we also derive a Mixed Integer Linear Programming (MILP) model. Finally, we present a comprehensive performance study via simulations. The results show that ST-MAC can perform better than existing MAC schemes (such as S-MAC, ECDiG, and T-Lohi) in terms of the network throughput and energy cost.