||A Dynamic Slot Scheduling MAC Protocol for TDMA-based Underwater Acoustic Sensor Networks
||Master's Program in Networking and Communications, Department of Computer Science and Information Engineering
Underwater Acoustic Sensor Networks
||水下無線聲納感測網路是個有趣且極具價值的研究領域，透過將水下感測器佈建於海洋中，便可以達到海嘯災害預防以及海洋污染監控等廣泛的應用目的。為了讓這些應用能夠順利且有效率地運作，一個良好且適用於水下環境的媒介存取控制協定是不可或缺的。然而，水中聲納傳播的巨大延遲、窄小的頻寬以及龐大的傳輸耗電量，種種的特性使得水中媒介存取控制協定的設計深具挑戰。本論文提出一個以TDMA-based的媒介存取控制協定，本協定除了避免水下時間與空間之不確定性產生的資料碰撞，同時妥善運用水下並行傳輸的特性以大幅提升頻道的利用度，此外，為了兼顧排程方法的可擴展性，更將Sink-to-node、Node-to-sink與Node-to-node三類的傳輸情況一起納入排程的考慮。由模擬的結果顯示，本論文提出的媒介存取協定在數種排程策略的幫助下，不但能有效的提升頻道利用度，且於Network throughput與Average packet delay上都有較佳的表現。
||In underwater acoustic sensor networks, sensors are usually deployed for sensing task, and the sensed data is able to be transmitted in a direct or multi-hop relaying manner to the sink in a single-hop topology. Considering the energy consumption model, the signal transmitted in a longer range will cost much energy than that in a shorter range. Therefore, three transmission types, sink-to-nodes, node-to-node, and node-to-sink are taken into consideration in the paper. However, due to the nature of the sound wave, the major issues of medium access control (MAC) are how to facilitate the concurrent transmission and to avoid the data collisions in underwater acoustic sensor networks. As a result, a TDMA-based MAC protocol with Dynamic Slot Scheduling Strategy (DSSS) is proposed for underwater acoustic sensor networks in this paper. DSSS can not only improve the channel utilization by increasing concurrent transmissions but also take the transmissions of sink-to-node, node-to-node, and node-to-sink into account to increase the network scalability. Simulation results verify that DSSS outperforms UD-TDMA, USS-TDMA and Original-TDMA in terms of the channel utilization and average delay.
List of Figures IV
List of Tables VI
1 Introduction 1
2 Network Model 6
3 The proposed TDMA-based MAC protocol with dynamic slot
scheduling strategies 12
3.1 Slot Selection Constraints 12
3.2 The dynamic slot schedule strategies 14
4 Performance Evaluations 19
4.1 Simulation Setups 19
4.2 Simulation Results 19
5 Conclusion 26
List of Figures
Figure 2.1 The frame structure in DSSS. 7
Figure 2.2 The network architecture in DSSS composes of vast underwater sensors and several sinks. Sensors cooperate with each other for detecting or monitoring task. The sensing data also can be either directly or multi-hop forwarded to the sink. 8
Figure 2.3 The ratio of the total energy consumption in terms of different number of hops forwarding. 11
Figure 3.1 s1s3 has been transmitting in slot21 , and then the states of all the slots are shown in (a). However, slot3
2 in (b) is a UB slot between s1s3 and s3s1. Therefore, s1s3 and s3s1 should be classified into a group to schedule. 13
Figure 3.2 The benefit of grouping. 15
Figure 3.3 An example scheduling and shifting policy. 17
Figure 3.4 The scheduling results of Group-I and Group-II merge into a frame. 18
Figure 4.1 Channel utilization of various protocols for different number of nodes. 20
Figure 4.2 Network throughput generated by various protocols for different offered load in 8 nodes. 22
Figure 4.3 Average packet delay caused by various protocols for different number of nodes. 23
Figure 4.4 One cycle time caused by various protocols for different number of nodes. 24
List of Tables
Table 1.1 Comparisons between UASNs and terrestrial WSNs. 2
Table 4.1 Simulation parameters. 21
|| L. Berkhovskikh and Y. Lysanov, Fundamentals of Ocean Acoustics. New York:
 J. Catipovic, D. Brady, and S. Etchemendy, “Development of underwater acoustic
modems and networks,” Oceanography, vol. 6, pp. 112–119, Mar 1993.
 N. Chirdchoo, W. seng Soh, and K. C. Chua, “RIPT: A receiver-initiated
reservation-based protocol for underwater acoustic networks,” IEEE Journal on
Selected Areas in Communications, vol. 9, no. 9, pp. 1744–1753, Sep. 2008.
 N. Chirdchoo, W.-S. Soh, and K. C. Chua, “MU-Sync: A time synchronization
protocol for underwater mobile networks,” in Proceedings of the ACM Interna-
tional Workshop on Underwater Networks (WuWNet), Sep 2008, pp. 35–42.
 P. Djukic and S. Valaee, “Delay aware link scheduling for multi-hop TDMA
wireless networks,” IEEE/ACM Transactions on Networking, vol. 17, pp. 870–
 T. Garrision, Oceanography: An Invitation to Marine Science. Thomson Learning,
 Y. Guan and C.-C. Shen, “MAC scheduling for high throughput underwater
acoustic networks,” in Proceedings of the IEEE Wireless Communications and
Networking Conference (WCNC), 2011.
 X. Guo, F. M.R., and R. M.J., “An adaptive propagation-delay-tolerant MAC
protocol for underwater acoustic sensor networks,” in OCEANS Europe, 2007,
 Z. Guo, Z. Li, and F. Hong, “USS-TDMA: Self-stabilizing TDMA algorithm for
underwater wireless sensor network,” in Proceedings of the International Confer-
ence on Computer Engineering and Technology (ICCET), vol. 1, Jan. 2009, pp.
578 – 582.
 C.-C. Hsu, K.-F. Lai, C.-F. Chou, and K.-J. Lin, “ST-MAC spatial-temporal
MAC scheduling for underwater sensor networks,” in Proceedings of the IEEE
INFOCOM, the Annual Joint Conference of the IEEE Computer and Commu-
nications Societies, 2009, pp. 1827–1835.
 K. Kredo, P. Djukic, and P. Mohapatra, “STUMP: Exploiting position diversity
in the staggered TDMA underwater MAC protocol,” in Proceedings of the IEEE
INFOCOM, the Annual Joint Conference of the IEEE Computer and Commu-
nications Societies, Apr. 2009, pp. 2961–2965.
 Z. Li, Z. Guo, H. Qu, F. Hong, P. Chen, and M. Yang, “UD-TDMA: A distributed
TDMA protocol for underwater acoustic sensor network,” in Proceedings of the
IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS),
Oct. 2009, pp. 918–923.
 L. Liu, Y. Xiao, and J. Zhang, “A linear time synchronization algorithm for
underwater wireless sensor networks,” in Proceedings of the IEEE International
Conference on Communications (ICC), Jun 2009, pp. 1–5.
 Y. Ma, Z. Guo, Y. Feng, M. Jiang, and G. Feng, “C-MAC: A TDMA-based
MAC protocol for underwater acoustic sensor networks,” in Proceedings of the International Conference on Networks Security, Wireless Communications and
Trusted Computing, 2009, pp. 728 –731.
 M. Molins and M. Stojanovic, “Slotted FAMAga MAC protocol for underwater
acoustic networks,” in Proceedings of the OCEANS, May 2006, pp. 1–7.
 T. N. Nguyen, S.-Y. Shin, and S.-H. Park, “Efficiency reservation MAC protocol
for underwater acoustic sensor networks,” in Proceedings of the International
Conference on Networked Computing and Advanced Information Management
(NCM), vol. 1, 2008, pp. 365–370.
 S. Park, “An efficient transmission scheme for underwater sensor networks,” in
Proceedings of the OCEANS, May 2009, pp. 1–3.
 D. Shin and D. Kim, “Ordered CSMA: a collision-free MAC protocol for underwater
acoustic networks,” in Proceedings of the OCEANS, Oct. 2007, pp. 1–6.
 E. M. Sozer, M. Stojanovic, and J. G. Proakis, “Underwater acoustic networks,”
IEEE journal of oceanic engineering, vol. 25, pp. 72–83, Jan. 2000.
 A. A. Syed and J. Heidemann, “Time synchronization for high latency acoustic
networks,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference
of the IEEE Computer and Communications Societies, Apr 2006, pp. 892–903.
 A. Syed, W. Ye, and J. Heidemann, “T-Lohi: A new class of MAC protocols for
underwater acoustic sensor networks,” in Proceedings of the IEEE INFOCOM,
the Annual Joint Conference of the IEEE Computer and Communications Soci-
eties, Apr. 2008, pp. 231–235.
 L. Tracy and S. Roy, “Short paper: A reservation MAC protocol for ad-hoc
underwater acoustic sensor networks,” in Proceedings of the ACM International
Workshop on Underwater Networks (WuWNet), Sep. 2008, pp. 95–98.
 W. Zhang, M. Stojanovic, and U. Mitra, “Analysis of a linear multihop underwater
acoustic network,” IEEE Journal of Oceanic Engineering, vol. 35, pp.
961–970, Oct. 2010.
 Y. Zhong, J. Huang, and J. Han, “A TDMA MAC protocol for underwater
acoustic sensor networks,” in Proceedings of the IEEE Youth Conference on In-
formation, Computing and Telecommunication, Sep 2009, pp. 534–937.