The elimination of spatial-temporal uncertainty in underwater sensor networks

Chih Cheng Hsu, Ming Shing Kuo, Cheng Fu Chou, Ching-Ju Lin

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


Since data in underwater sensor networks (UWSNs) is transmitted by acoustic signals, the characteristics of a UWSN are different from those of a terrestrial sensor network. Specifically, due to the high propagation delay of acoustic signals in UWSNs, referred as spatial-temporal uncertainty, current terrestrial MAC schemes do not work well in UWSNs. Hence, we consider spatial-temporal uncertainty in the design of an energy-efficient TDMA-based MAC protocol for UWSNs. We first translate the TDMA-based scheduling problem in UWSNs into a special vertex-coloring problem in the context of a spatial-temporal conflict graph (ST-CG) that describes explicitly the conflict delays among transmission links. With the help of the ST-CG, we propose two novel heuristic approaches: 1) the traffic-based one-step trial approach (TOTA) to solve the coloring problem in a centralized fashion; and for scalability, 2) the distributed traffic-based one-step trial approach (DTOTA) to assign the data schedule for tree-based routing structures in a distributed manner. In addition, a mixed integer linear programming (MILP) model is derived to obtain a theoretical bound for the TDMA-based scheduling problem in UWSNs. Finally, a comprehensive performance study is presented, showing that both TOTA and DTOTA guarantee collision-free transmission. They thus outperform existing MAC schemes such as S-MAC, ECDiG, and T-Lohi in terms of network throughput and energy consumption.

Original languageEnglish
Article number6334449
Pages (from-to)1229-1242
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number4
StatePublished - 1 Jan 2013


  • MAC schedule
  • spatial-temporal uncertainty
  • TDMA
  • underwater sensor networks (UWSNs)

Fingerprint Dive into the research topics of 'The elimination of spatial-temporal uncertainty in underwater sensor networks'. Together they form a unique fingerprint.

Cite this