水下的時間同步(Synchronization)問題為無線感測網路(Wireless Sensor Networks，WSN)中一個特殊的問題，為了完成無線感測器間的時間同步，通常必須先完成定位(Localization)的工作，來估計無線感測器間的距離，然而水面下並無法使用全球定位系統(Global Positioning System，GPS)以衛星來協助定位，又因為不適用波速較快的無線射頻(Radio Frequency，RF)技術來傳輸資訊，而僅能使用超音波(Ultra Sound)等波速較慢的方式，在定位移動的無線感測器時，常受限於傳輸延遲(Propagation Delay)造成準確性不足的問題，除此之外，為了時間同步所需的大量訊息收發，其所消耗的電量，也為補充電量不易的水下無線感測器造成一定的困擾。
本研究的目的，在嘗試運用一固定於水面上週期性發送同一頻率信號之信標(Buoy)，藉由移動中之水下無線感測器與信標間相對運動會造成的都卜勒效應(Doppler Effect)，讓水下無線感測器可僅觀察所收到訊號的頻率，即可估計自己相對於信標的距離與行進的速度，依照無線感測器的硬體配置與實際應用的需求差異，我們分別提出了UDE-NR(Underwater Distance Estimation-Nonlinear Regression)－以非線性擬合(Nonlinear Fit)無線感測器頻率觀測模型的方式，及UDE-SA(Underwater Distance Estimation-Simple Approximation)－找出簡化之頻率觀測模型，並以線性迴歸(Linear Regression)找出參數的方式，完成無線感測器與信標間的距離估計，再以兩種方式距離估計的結果，進行與信標的時間同步，最後達成將整個水下無線感測網路時間同步的目標。

Underwater synchronization is special issue for sensor networks. The problem is much more challengeable than the conventional synchronization problem on the ground. On the one hand, this is because underwater sensors cannot receive signals from GPS satellites directly. On the other hand, since electromagnetic signals decay extremely fast in water, traditional wireless message exchange using electromagnetic signals is not suitable for underwater environment.
This thesis investigates Doppler Effect experienced by an underwater mobile sensor when receiving ultrasonic signals from a fixed buoy on the surface of the water. Since the speed of ultrasonic signals is much slower than that of electromagnetic signals, ultrasonic signals can result in more obvious Doppler Effect. Furthermore, propagation delay of the slow speed ultrasonic signals cannot be ignored anymore in underwater environment. Thus, distance estimation between buoy node and sensor node becomes a critical factor in order to determine propagation delay for time synchronization. Two methods are proposed to estimate this distance, namely Underwater Distance Estimation-Nonlinear Regression (UDE-NR) and Underwater Distance Estimation-Simple Approximation (UDE-SA). UDE-NR estimates the sensor’s speed, depth under the surface, and horizontal distance from the buoy node by fitting the parameters to the non-linear objective frequency function. To reduce the complexity of the calculation, UDE-SA estimates the sensor’s speed and horizontal distance from the buoy based on the received signal and determines the depth of the sensor by linear regression to a simplified objective function. Propagation delay of the signal is then estimated and used to achieve time synchronization among sensors.

[1]C. F. Huang, Y. C. Tseng, “The Coverage Problem in a Wireless Sensor Network”, in Proc. of the 2nd ACM international conference on Wireless sensor networks and applications, 2003, pp. 115 – 121.
[2]L. Hu, D. Evans, “Localization for Mobile Sensor Network”, in Proc. of the 10th annual international conference on Mobile computing and networking, 2004, pp. 45-57.
[3]K. F. Ssu, C. H. Ou, H. C. Jiau, “Localization With Mobile Anchor Points in Wireless Sensor Networks”, IEEE Trans. Vehicular Technology, Vol. 54, pp. 1187-1197, 2005.
[4]O. Gurewitz, I. Cidon, M. Sidi, “Network Clock Frequency Synchronization”, in Proc. IEEE INFOCOM, 2006, pp. 1-9.
[5]Y. Zou, K. Chakrabarty, “Sensor Deployment and Target Localization Based on Virtual Forces”, in Proc. IEEE INFOCOM, 2003, pp. 1293-1303.
[6]N. Nicolaou, A. See., P. Xie, J. H. Cui, D. Maggiorini, “Improving the Robustness of Location-Based Routing for Underwater Sensor Networks”, in OCEANS 2007 – Europe, Aberdeen, 2007.
[7]J. Deng, R. Han, S. Mishra, ”Insens: Intrusion-tolerant routing for wireless sensor networks”, Computer Communications, Vol. 29, pp. 216-230, 2006.
[8]T. Small, Z. Hass, “The shared wireless infostation model:a new ad hoc networking paradigm (or where there is a whale, there is a way)”, in Proc. of the 4th ACM international symposium on Mobile ad hoc networking & computing table of contents, 2003, pp. 233-244.
[9]J. Elson, L. Girod, D. Estrin, “Fine-grained network time synchronization using reference broadcasts”, in Proc. of the 5th symposium on Operating systems design and implementation, 2002, pp. 147-163.
[10]S. Ganeriwal, R. Kumar, and M. Srivastava, “Timing-sync protocol for sensor networks” in Proc. of the 1st international conference on Embedded networked sensor systems, 2003, pp. 138-149.
[11]M. Mar’oti, B. Kusy, G. Simon, A. L’edeczi, “The flooding time synchronization protocol”, in Proc. of the 2nd international conference on Embedded networked sensor systems, 2004, pp. 39-49.
[12]J. P. Sheu, W. K. Hu, J. C. Lin, “Ratio-based time synchronization protocol in wireless sensor networks” Telecommunication Systems, Vol. 39, pp. 25-35, 2008.
[13]A. Syed, J. Heidemann, “Time Synchronization for high latency acoustic networks”, in Proc. IEEE INFOCOM, 2006, pp. 1-12.
[14]X. Tian,Y. Miao, T. Hu, B. Fan, J. Pan, W. Xu, “Maximum Likelihood Estimation Based on Time Synchronization Algorithm for Wireless Sensor Networks”, ISECS International Colloquium Computing, Communication, Control, and Management, 2009, Vol. 4, pp. 416-420.
[15]K. Arvind, “Probabilistic Clock Synchronization in Distributed Systems”, IEEE Trans. Parallel and Distributed Systems, Vol. 5, Issue 5, pp. 474-487, 1994.
[16]F. Cristian, “Probabilistic Clock Synchronization”, Distributed Computing, Vol. 3, pp. 146-158, 1989
[17]S. PalChaudhuri and A. K. Saha, D. B. Johnson, “Adaptive Clock Synchronization in Sensor Networks”, International Symposium Information Processing in Sensor Networks, 2004, pp. 340-348, 2004.
[18]K. Lei, W. Qianping, Z. Yan, “Time Synchronization algorithm based on Cluster for WSN”, The 2nd IEEE International Conference Information Management and Engineering (ICIME), pp. 126-130, 2010.
[19]H. Kim, D. Kim, S. E. Yoo, “Cluster-based Hierarchical Time Synchronization for Multi-hop Wireless Sensor Networks”, 20th International Conference Advanced Information Networking and Applications, pp. 318-322, 2006.
[20]K. Sun, P. Ning, C. Wang, “Fault-Tolerant Cluster-Wise Clock Synchronization for Wireless Sensor Networks”, IEEE Trans. Dependable and Secure Computing, Vol. 2, Issue 3, pp.177-189, 2005.
[21]Y. T. Chan, W. Y. Tsui, H. C. So, P. Ching, “Time-of arrival based localization under NLOS conditions”, IEEE Trans. Vehicular Technology, Vol. 55, Issue 1, pp. 17-24, 2006.
[22]M. Bocquet, C.. Loyez, A. Benlarbi-Delai, “Using enhanced-TDOA measurement for indoor positioning”, IEEE Microwave and Wireless Components Letters, Vol.15, pp. 612-614, 2005.
[23]H. Liu, H. Darabi, P. Banerjee, J. Liu, “Survey of Wireless Indoor Positioning Techniques and Systems”, IEEE Trans. Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 37, Issue 6, pp.1067-1080, 2007.
[24]T. S. Rappaport, “Wireless Communication Principles and Practice,” Prentice Hall, 1996.
[25]N. B. Priyantha, A. Chakraborty, H. Balakrishnan, “The Cricket location-support system”, Proc. of the 6th annual international conference on Mobile computing and networking, 2000, pp. 32-43.
[26]M. L. Sichitiu, V. Ramadurai, “Localization of wireless sensor networks with a mobile beacon”, 2004 IEEE International Conference Mobile Ad-hoc and Sensor Systems, pp. 174-183, 2004
[27]K. Kim, W. Lee, “MBAL: A mobile beacon-assisted localization scheme for wireless sensor networks”, in Proc. of 16th International Conference Computer Communications and Networks, 2007, pp. 57–62.
[28]N. Bulusu, J. Heidemann, D. Estrin, “GPS-less Low Cost Outdoor Localization for Very Small Devices”, IEEE Personal Communications, Vol. 7, pp. 28-34, 2000.
[29]T. He, C. Huang, B. M. Blum, J. A. Stankovic, T. Abdelzaher, “Range-free localization and its impact on large scale sensor networks”, ACM Trans. on Embedded Computing Systems, Vol. 4, pp. 877-906, 2005.
[30]L. Doherty, K. S. J. Pister, L. E. Ghaoui, “Convex Position Estimation in Wireless Sensor Networks” in Proc. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, 2001, pp. 1655-1663.
[31]J. P. Sheu, J. M. Li, C. S. Hsu, “A Distributed Location Estimating Algorithm for Wireless Sensor Networks”, IEEE International Conference Sensor Networks, Ubiquitous, and Trustworthy Computing, pp. 218-225, 2006.
[32]D. Niculescu, B. Nath, “DV based positioning in ad hoc networks”, Telecommunication Systems, Vol. 22, pp. 267 – 280, 2003.
[33]G. L. Joo, S. V. Rao, “A grid-based location estimation scheme using hop counts for multi-hop wireless sensor networks”, International Workshop Wireless Ad-Hoc Networks, pp. 330-334, 2004.
[34]R. Nagpal, “Organizing a global coordinate system from local information on an amorphous computer” in Proc. of the 2nd international conference on Information processing in sensor networks, 2003, pp. 333-348.
[35]S. Capkun, M. Hamdi, J. P. Hubaux, “GPS-free Positioning in mobile ad-hoc networks”, in Proc. of the 34th Annual Hawaii International Conference System Sciences, 2001, pp. 157-167.