在本篇論文中，我們將提出一個適用於水下無線聲波感測網路環境之繞徑協定。聲波傳輸速度在不同海水深度時將有所變化。在水下 1000 公尺時聲速最慢，1000 公尺以上及以下速度皆較快。利用此特性，本篇論文提出一個聲速與海水深度變化之數學模型，並藉由此模型建立繞徑表。傳送端節點可依據所在之深度不同，透過查表的方式，可選擇向上傳送、向下傳送或直接傳送的方式。在盡可能的縮短傳輸時間的情形下，將封包傳送至水面上目的端節點。 
 在模擬的部分，由實驗結果可知，本論文所提出之封包傳輸路徑，雖然較傳統最短傳輸路徑長，但花費的傳輸時間較傳統最短傳輸路徑少。同時，隨著傳輸範圍的增加，傳輸時間亦隨之減少。此實驗結果足以驗證本篇論文所提出的具深度調節之繞徑協定可善用聲速在水下深度不同傳輸速度隨之改變的特性，以減少封包傳輸之時間花費。

In this thesis, we propose a depth adaptive routing protocol named DARP for underwater acoustic sensor networks. Sound speed varies with water depth. As the depth of water is 1000 meters, the speed of acoustic wave is the slowest. Based on this observation, this proposal analyzes the impact of sound speed in different water depth and with various transmission distances and then the analysis results are formulated as a routing table. Therefore, each sender can refer to this routing table to transmit with a shortest end-to-end delay time in DARP. 
The simulation results show that the routing path is longer than the traditional shortest path, but the cost time of our  proposed methods is less than the traditional shortest path. It improve the property of the sound speed is change by the water depth. At the same time, the large the transmission range is, the less the time is.

Contents
Contents III
List of Figures V
List of Tables VIII
1 Introduction 1
2 Preliminaries 5
3 Forwarding Path Analysis 9
3.1 Numerical Analyses 9
3.2 End-to-End Delay Estimation of Downward Path 16
3.3 End-to-End Delay Estimation of Straight Path 17
3.4 End-to-End Delay Estimation of Upward Path 19
4 The Depth Adaptive Routing Protocol (DARP) 21
4.1 Construction the Routing Table 21
4.2 Calculation the Waiting Time 30
4.3 Local minimum Problem 31
4.4 The DARP Algorithm 35
5 Performance Evaluations 36
5.1 The relationship between the end-to-end delay and the depth of source 37
5.2 The relationship between the end-to-end delay and the width 38
5.3 The relationship between the path length and the width 41
5.4 The relationship between the end-to-end delay and the packet size 44
5.5 The relationship between the end-to-end delay and the transmission ranges 44
6 Conclusions 48
Bibliography 50
Appendix 54

List of Figures
Figure 1.1 A scenario of UASNs 2
Figure 2.1 Changes in speed of sound by depth 6
Figure 3.1 Upward, straight, and downward path in the network 10
Figure 3.2 The downward path with the sinking, horizontal, and floating phases 11
Figure 3.3 Four considered paths in the numerical evaluation 11
Figure 3.4 Comparisons of the end-to-end delay of the straight, upward, and downward paths in terms of the depth of the source (d) 12
Figure 3.5 Comparisons of the end-to-end delay of the straight, upward, and downward paths in terms of the width (w) 13
Figure 3.6 The downward path changed by the major parameters θ1 and θ2 16
Figure 3.7 The straight path changed by the major parameter θ 18
Figure 3.8 The upward path changed by the major parameter θ 19
Figure 4.1 The end-to-end delay in terms of different depths of source when w=10km 22
Figure 4.2 The end-to-end delay in terms of different depths of source when w=20km 23
Figure 4.3 The end-to-end delay in terms of different depths of source when w=30km 23
Figure 4.4 The end-to-end delay in terms of different depths of source when w=40km 24
Figure 4.5 The end-to-end delay in terms of different depths of source when w=50km 24
Figure 4.6 The end-to-end delay in terms of different depths of source when w=60km 25
Figure 4.7 The end-to-end delay in terms of different depths of source when w=70km 25
Figure 4.8 The end-to-end delay in terms of different depths of source when w=80km 26
Figure 4.9 The end-to-end delay in terms of different depths of source when w=90km 26
Figure 4.10 The end-to-end delay in terms of different depths of source when w=100km 27
Figure 4.11 The end-to-end delay in terms of different depths of source when w=150km 27
Figure 4.12 The end-to-end delay in terms of different depths of source when w=200km 29
Figure 4.13 The illustration of parameters in the waiting function 30
Figure 4.14 Local minimum phenomenon 32
Figure 4.15 The illustration of bypassing the hole 33
Figure 4.16 The illustration of the retransmission 33
Figure 5.1 The end-to-end delay in terms of different depths of source when w=10km 38
Figure 5.2 The end-to-end delay in terms of different depths of source when w=50km 39
Figure 5.3 The end-to-end delay in terms of different depths of source when w=100km 39
Figure 5.4 The end-to-end delay in terms of different depths of source when w=150km 40
Figure 5.5 The end-to-end delay in terms of different depths of source when w=200km 40
Figure 5.6 The end-to-end delay in terms of different widths when d=4500m 41
Figure 5.7 The end-to-end delay in terms of different widths when d=8000m 42
Figure 5.8 The path length in terms of different widths when d=4500m 43
Figure 5.9 The path length in terms of different widths when d=8000m 43
Figure 5.10 The end-to-end delay in terms of different packet sizes when d=3000m and w=100km 45
Figure 5.11 The end-to-end delay in terms of different packet  sizes when d=3000m and w=200km 45
Figure 5.12 The end-to-end delay in terms of different transmission ranges when d=3000m and w=100km 46
Figure 5.13 The end-to-end delay in terms of different transmission ranges when d=3000m and w=200km 47

List of Tables
Table 4.1 The routing table in terms of different depths(d) of source and different width(w) of scenario(km) 28
Table 5.1 The simulation parameters 36

[1] I. F. Akyildiz, D. Pompili, and T. Melodia, “Underwater acoustic sensor networks: research challenges,” Journal of Ad Hoc Networks (Elsevier), vol. 3, no. 3, pp. 257–281, Mar. 2005.
[2] I. Akyildiz, D. Pompili, and T. Melodia, “State-of-the-art in protocol research for underwater acoustic sensor networks,” in Proceedings of the ACM International Workshop on Underwater Networks (WuWNet), 2006, pp. 7–16.
[3] S. Azad, P. Casari, C. Petrioli, R. Petroccia, and M. Zorzi, “On the impact of the environment on mac and routing in shallow water scenarios,” in Proceedings of the IEEE OCEANS, 2011, pp. 1–8.
[4] E. A. Carlson, P.-P. Beaujean, and E. An, “Location-aware routing protocol for underwater acoustic networks,” in Proceedings of the IEEE OCEANS, Sep. 2006, pp. 1–6.
[5] P. Casari, A. Asterjadhi, and M. Zorzi, “On channel aware routing policies in shallow water acoustic networks,” in Proceedings of the IEEE OCEANS, Sep. 2011, pp. 1–6.
[6] J.-H. Cui, Z. J. Shi, and H. Yan, “Dbr:  Depth-based routing for underwater sensor networks,” in Proceedings of the IFIP Networking, May 2008, pp. 72–86.
[7] S. K. Dhurandher, M. S. Obaidat, S. Goel, and A. Gupta, “Optimizing energy through parabola based routing in underwater sensor network,” in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), Dec. 2011,
pp. 1–5.
[8] ——, “Optimizing energy through parabola based routing in underwater sensor networks,” in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), Dec. 2011, pp. 1–5.
[9] M. Erol and S. Oktug, “A localization and routing framework for mobile underwater sensor networks,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Apr. 2008, pp. 1–3.
[10] T. Hu and Y. Fei, “Qelar: A machine-learning-based adaptive routing protocol for energy-efficient and lifetime-extended underwater sensor networks,” IEEE Transactions on Mobile Computing, vol. 9, no. 6, pp. 796–809, 2010.
[11] D. Hwang and D. Kim, “Dfr: Directional flooding-based routing protocol for underwater sensor networks,” in Proceedings of the IEEE OCEANS, 2008, pp. 1–7.
[12] K. K. II and P. Mohapatra, “Distributed scheduling and routing in underwater wireless networks,” in Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), Dec. 2010, pp. 1–6.
[13] M. T. Isik and O. B. Akan, “A three dimensional localization algorithm for underwater acoustic sensor networks,” IEEE Transactions on Wireless Communications, vol. 8, no. 9, pp. 4457–4463, 2009.
[14] J. M. Jornet, M. Stojanovic, and M. Zorzi, “Focused beam routing protocol for underwater acoustic networks,” in Proceedings of the ACM International Workshop on Underwater Networks (WuWNet), Sep. 2008, pp. 75–81.
[15] U. Lee, P. Wang, Y. Noh, L. F. M. Vieira, M. Gerla, and J.-H. Cui, “Pressure routing for underwater sensor networks,” in Proceedings of the IEEE INFOCOM, the Annual Joint Conference of the IEEE Computer and Communications Societies, Mar. 2010, pp. 1–9.
[16] N. Nicolaou, A. See, P. Xie, J.-H. Cui, and D. Maggiorini, “Improving the robustness of location-based routing for underwater sensor networks,” in Proceedings
of the IEEE OCEANS, 2007, pp. 1–6.
[17] Y. Noh, U. Lee, P. Wang, B. S. C. Choi, and M. Gerla, “Vapr: Void aware pressure routing for underwater sensor networks,” TMC, vol. 0, no. 99, pp. 1–14, 2012.
[18]  J. Partan, J. Kurose, and B. N. Levine, “A survey of practical issues in underwater networks,” in Proceedings of the ACM International Workshop on Underwater Networks (WuWNet), Sep. 2006, pp. 17–24.
[19] D. Pompili, T. Melodia, and I. F. Akyildiz, “Routing  algorithms  for  delay-insensitive and delay-sensitive applications in underwater sensor networks,” in Proceedings of the ACM International Conference on Mobile Computing and Networking (MOBICOM), Sep. 2006, pp. 298–309.
[20] ——, “Distributed routing algorithms for underwater acoustic sensor networks,” IEEE Transactions on Wireless Communications, vol. 9, no. 9, pp. 2934–2944, 2010.
[21] A. Y. Teymorian, W. Cheng, L. Ma, X. Cheng, X. Lu, and Z. Lu, “3d underwater sensor network localization,” IEEE Transactions on Mobile Computing, vol. 8, no. 12, pp. 1610–1621, 2009.
[22] I. Tolstoy and C. S. Clay, Ocean Acoustics: Theory and experiment in underwater sound, 1st ed. McGraw-Hill, 1987.
[23] A. Wahid, S. Lee, and D. Kim, “An energy-efficient routing protocol for uwsns using physical distance and residual energy,” in Proceedings of the IEEE OCEANS, 2011, pp. 1–6.
[24] P. Xie, J.-H. Cui, and L. Lao, “Vbf: Vector-based forwarding protocol for underwater sensor networks,” in Proceedings of the IFIP Networking, May 2006, pp. 1216–1221.
[25] B. Yahya and J. Ben-Othman, “Relax: An energy efficient multipath routing-protocol for wireless sensor networks,” in Proceedings of the IEEE International Conference on Communications (ICC), May 2010, pp. 1–6.
[26] Z. Zhou, Z. Peng, J.-H. Cui, and A. C. Bagtzoglou, “Scalable localization with mobility prediction for underwater sensor networks,” IEEE Transactions on Mobile Computing, vol. 10, no. 3, pp. 335–348, 2011.
[27] M. Zorzi, P. Casari, N. Baldo, and A. F. H. III, “Energy-efficient routing schemes for underwater acoustic networks,” JSAC, vol. 26, no. 9, pp. 1754–1755, 2008.