在這份碩士論文中，我們描述了一個全新應用於無線感測網路的時間同步方法，名為“利用廣播時間郵戳的無線感測網路時間同步技術”，簡稱TBS。TBS是一個針對網路全域的時間同步技術，並具有sender-receiver與receiver-receiver兩類時間同步技術混合的特質。TBS利用兩個階段構成整合時間同步過程，即組織階段與時間同步階段。TBS利用組織階段幫助被選中的參考節點評估它們與距離為一的相鄰節點的傳輸延緩時間，並在時間同步階段由參考節點發送一個以上包含了時間郵戳的訊息封包。TBS支援多點距離的時間同步需要，並使在網路系統中的節點能與外界的標準參考時間進行聯繫與同步。

　　這個全新的時間同步技術在模擬實驗中有著不錯的表現。結果顯示，相對另一個時間同步技術Lightweight Time Synchronization (LTS) [6]，TBS擁有約略二十倍的時間同步效率。另外，相對另一個時間同步技術Reference-Broadcast Synchronization (RBS) [3]而言，TBS具有稍為良好的時間同步效率。在能源考量上，TBS相較以上兩個時間同步技術均有更佳的節省能源消耗特性，尤其在距離為一的相鄰節點的數量不斷增加的情形下更為明顯。TBS是一個針對能源效率、時間精準度與感測元件運算效能等考量所特別設計應用於無線感測網路的時間同步技術。從模擬的結果顯示TBS在能源使用上較其它現成的時間同步技術為佳，利用較少的封包傳輸及簡單的運算便能得到良好的時間精準度，在各項無線感測網路的約束與基本限制上均表現優良。

　In this thesis, we present a novel Timestamp Broadcasting Synchronization (TBS) method for Wireless Sensor Networks, which aims at providing network-wide time synchronization in the network. TBS is a hybrid protocol of sender-receiver and receiver-receiver synchronizations. TBS works with two phases, which are Setup Phase and Synchronization Phase. Setup Phase helps reference nodes estimate the transmission delays with neighbor nodes, and reference nodes later send one or more reference timestamp pulses to their one-hop neighbor nodes in the Synchronization Phase. TBS is a multi-hop synchronization supported algorithm, in which nodes could synchronize to a standard reference time such as UTC.

　The novel scheme demonstrated acceptable results in simulations. TBS has a roughly 20x better time synchronization efficiency than Lightweight Time Synchronization [6], and a similar synchronization result with Reference-Broadcast Synchronization [3]. TBS also has better power consumption evaluations than the both ones which consume much more power while there become more one-hop neighbor nodes. TBS is novel proposed well performed synchronization algorithm with consideration for energy efficiency, precision and capability of computations for Wireless Sensor Networks.

[1] Ian F. Akyildiz, Weilian Su, Yogesh SanKarasubramaniam and Erdal Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, August 2002

[2] Fikret Sivrikaya and Bülent Yener, “Time Synchronization in Sensor Networks: A Survey,” IEEE Network, Vol. 18, July/August 2004

[3] Jeremy Elson, Lewis Girod and Deborah Estrin, “Fine-Grained Network Time Synchronization using Reference Broadcasts,” ACM SIGOPS Operating Systems Review Volume 36, December 2002

[4] Jeremy Elson and Deborah Estrin, “Time Synchronization for Wireless Sensor Networks,”, Proceedings of 15th International Parallel and Distributed Processing Symposium, April 2001

[5] Saurabh Ganeriwal, Ram Kumar and Mani B. Srivastava, “Timing-sync Protocol for Sensor Networks,” Proceedings of the first International Conference on Embedded Networked Sensor Systems, November 2003

[6] Jana V. Greunen and Jan Rabaey, “Lightweight Time Synchronization for Sensor Networks,” Proceedings of 2nd ACM International Conference on Wireless Sensor Networks and Applications, September 2003

[7] ISO/IEC. IEEE 802.11 Standard. IEEE Standard for Information Technology, ISO/IEC 8802-11:1999(E), 1999

[8] H. Kopetz and W. Schwabl, “Global time in distributed real-time systems,” Technical Report 15/89, Technische Universität Wien, 1989

[9] John R. Vig., “Introduction to Quartz Frequency Standards,” Technical Report SLCET-TR-92-1, Army Research Laboratory, Electronics and Power Sources Directorate, October 1992. Available at http://www.ieee-uffc.org/freqcontrol/quartz/vig/vigtoc.htm

[10] D. Estrin, et al., http://nesl.ee.ucla.edu/tutorials/mobicom02

[11] R. M. Metcalfe and D. R. Boggs, “Ethernet: Distributed packet switching for local computer networks,” Communications of the ACM, 26(1):90-95, January 1983

[12] I. Rubin, “Message Delay in FDMA and TDMA Communication Channels,” IEEE Trans. Communin., COM27(5)769-777, May 1979

[13] David L. Mills, “Internet Time Synchronization: The Network Time Protocol,” IEEE Transactions on Communications, Vol. 39, No. 10, October 1991

[14] Mihail L. Sichitiu and Chanchai Veerarittiphan, “Simple, Accurate Time Synchronization for Wireless Sensor Networks,” IEEE WCNC 2003

[15] An-swol Hu and Sergio D. Servetto, “Asymptotically Optimal Time Synchronization in Dense Sensor Networks,” Proceedings of 2nd ACM International Conference on Wireless Sensor Networks and Applications, September 2003

[16] Qun Li and Daniela Rus, “Global Clock Synchronization in Sensor Networks,” IEEE INFOCOM 2004

[17] G. Asada, M. Dong, T.S. Lin, et al., “Wireless Integrated Network Sensors: Low Power Systems on a Chip,” Proceedings of the European Solid State Circuits Conference, 1998

[18] Jeremy Elson and Kay Römer, “Wireless Sensor Networks: A New Regime for Time Synchronization,” ACM SIGCOMM Computer Communication Review Vol.33, January 2003

[19] Alberto Cerpa, Jeremy Elson, Deborah Estrin, et al., “Habitat monitoring: Application driver for wireless communications technology,” Proceedings of ACM SIGCOMM Workshop on Data Communications, April 2001

[20] Kay Römer, “Time Synchronization in Ad Hoc Networks,” Proceedings of 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, October 2001

[21] Wendi B. Heinzelman, Anatha Chandrakasan, and Hari Balakrishnan, “Energy-Efficient Communication Protocol for Wireless Microsensor Networks,” Proceedings of the 33rd Hawaii International Conference on System Sciences, 2000

[22] Wendi B. Heinzelman, Anatha P. Chandrakasan, and Hari Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Vol.1, No.4, October 2002

[23] Saâd Biaz and Yawen D. Barowski, “GANGS: an Energy Efficient MAC Protocol for Sensor Networks,” Proceedings of the 42nd Annual Southeast regional Conference, April 2004

[24] Ossama Younis and Sonia Fahmy, “Distributed Clustering in Ad-hoc Sensor Networks: A Hybrid, Energy-Efficient Approach,” IEEE INFOCOM 2004
[25] Jason Hill and David Culler, “A wireless embedded sensor architecture for system-level optimization”, Technical report, UC Berkeley, 2001

[26] Lennart Meier, Philipp Blum, and Lothar Thiele, “Internal Synchronization of Drift-Constraint Clocks in Ad-Hoc Sensor Networks,” Proceedings of 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing, May 2004

[27] Jason L. Hill and David E. Culler, “MICA: A Wireless Platform for Deeply Embedded Networks,” IEEE Micro of IEEE Computer Society, 2002