臺灣博碩士論文加值系統

時間同步對多點跳躍隨意式行動網路上的能源節省協定來說非常重要。然而，移動節點隨機加入形成隨意網路且沒有所謂的中控點(Infrastructure Node)增加了設計多點跳躍環境時間同步協定的困難度。因此，有相當多的能源節省協定開始往非同步醒來方向設計。非同步醒來能源節省協定雖然不需要時間同步但是卻較同步醒來能源節省協定浪費能源以及增加封包傳送的等待時間。IEEE 802.11 Standard定義的能源節省協定屬於同步醒來能源節省這類，並設計時間同步機制供節點在分散式環境時間同步。節點在每一個信標週期將其時間戳記包含在信標，並競爭發送信標。藉由收到並比對信標的時間戳記資訊，節點之間很容易取得同步。這樣的機制不適用於多點跳躍環境，會形成節點間時間分割的問題。本論文中，我們提出一個適用於IEEE 802.11多點跳躍環境的時間同步機制稱為多點跳躍時間同步協定(Multi-hop Time Synchronization Protocol, MTSP)。協定分為兩部分：信標視窗階段(Beacon Window Phase, BW-Phase)與同步階段(Synchronization Phase, SYN-Phase)，以解決時間同步時發生時間分割的問題。在信標視窗階段，節點形成同步群並在同步群中選出擁有最快時間戳記的節點來當領導點；在同步階段，透過我們的演算法同步這些領導點。最後，我們使用C語言模擬實驗環境來驗證多點跳躍時間同步協定在高節點密度多點跳躍隨意網路環境的時間同步效能。

Clock synchronization is very important for power management protocol in a multi-hop MANET. However, since MANET is a network temporarily formed by a collection of mobile nodes without the aid of any centralized coordinator, clock synchronization is very difficult to achieve. Therefore, most of previous works on power efficiency assumed asynchronous clock. As a consequence, a mobile node will waste a lot of power and time waiting for forwarding a packet to its neighbors, due to the lack of information of wakeup times of its neighbors. In IEEE 802.11 standard, time synchronization function (TSF) is defined to synchronize clocks of all mobile devices in a single hop ad hoc network. In this standard, devices generate beacons with timestamp and contend to send a beacon in each beacon interval. Based on the received timestamp, devices then can synchronize their clocks easily. However, the IEEE 802.11 TSF is not suitable for dense networks and will cause time partition problem when extended to multi-hop ad hoc networks. In this paper, we propose a multi-hop time synchronization protocol, referred to as MTSP, for IEEE 802.11 multi-hop ad hoc networks. The MTSP consists of two phases, namely the beacon window phase (BW-phase) and the SYN phase (SYN-phase). In beacon window phase (BW-phase), several devices, which can directly communicate with each others, form a synchronization group. And each group selects the device with fastest timer as the leader node of the group. In SYN phase (SYN-phase), leader nodes then synchronize with each other. Our simulation results show that MTSP is a distributed and effective multi-hop time synchronization protocol, especially for dense networks.

第一章 序論 1
第一節 背景簡介 1
第二節 研究動機 4
第三節 多點跳躍協定 7
第四節 模擬結果 8
第五節 論文架構 9
第二章 相關文獻探討 10
第一節 有線區域網路的時間同步協定 10
第二節 藍芽與無線感測網路的時間同步協定 12
第三節 IEEE 802.11 INFRASTRUCTURE模式的時間同步協定 13
第四節 IEEE 802.11 AD HOC模式的時間同步 14
第三章 多點跳躍時間同步協定 19
第一節 系統架構 20
第二節 BEACON WINDOW階段同步 22
第三節 SYNCHRONIZATION階段同步 30
第四章 系統效能分析 38
第一節 傳輸距離討論 38
第二節 BW階段同步討論 40
第三節 SYN階段同步討論 41
第四節 整體系統效能 41
第五章 模擬與分析 43
第一節 模擬環境與模擬參數 43
第二節 模擬結果與討論 44
第六章 結論與未來研究方向 51
參考文獻 52

[1]LAN MAN Standards Committee of the IEEE Computer Society, “IEEE Std 802.11-1999, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” IEEE, 1999.
[2]Chiung-Ying Wang, Chi-Jen Wu, Guan Nan Chen and Ren-Hung Hwang, “p-MANET: Efficient Power Saving Protocol for Multi-Hop Mobile Ad Hoc Networks , ” the third IEEE International Conference on Information Technology and Applications, pp. 271–276, 2005.
[3]Y.C Tseng, C.S Hsu and T.Y Hsieh, “Power Saving Protocols for IEEE 802.11-Based Multi-Hop Ad Hoc Network ,” Computer Networks: The International Journal of Computer and Telecommunications Networking, pp. 317– 337 , October 2003
[4]J.R Jiang, Y.C Tseng, C.S Hsu and T.H Lai, “Quorum-Based Asynchronous Power-Saving Protocols for IEEE 802.11 Ad Hoc Networks,” IEEE International Conference on Parallel Processing, pp.257–264, 2003
[5]Rong Zheng, Jennifer C. Hou and Lui Sha, “Asynchronous wakeup for ad hoc networks, ” MobiHoc, pp.35–45, June 2003
[6]Mihail L. Sichitiu and Chanchai Veerarittiphan, “Simple, accurate time synchronization for wireless sensor networks,” IEEE Wireless Communications and Networking (WCNC 2003), pp. 1266–1273, March 2003.
[7]Ram Kumar, Mani B. Srivastava and Saurabh Ganeriwal, “Timing-sync Protocol for Sensor Networks, ”ACM SenSys, pp. 138–149, 2003.
[8]Task Group E of the IEEE 802.11 standards group, http://grouper.ieee.org/groups/802.11
[9]NTP: The Network Time Protocol (RFC-1305 version3), http://www.eecis.udel.edu/~mills/database/rfc/rfc1305/
[10]Nation Standard Time and Frequency Laboratory, http://www.stdtime.gov.tw/
[11]Wireless Sensor Networks, http://dblab.csie.ncku.edu.tw/imus/sensor/index.html
[12]Computer Time Synchronization GPS Clock, http://www.gpsclock.com/
[13]Sairam, K.V.S.S.S.S.; Gunasekaran, N.; Redd, S.R,“Bluetooth in wireless communication,” IEEE Communications Magazine, pp. 90–96, June 2002
[14]Baruch Awerbuch, David Holmer and Herbert Rubens, “The Pulse Protocol: Energy Efficient Infrastructure Access, ” IEEE INFOCOM, pp. 1467–1478, March 2004
[15]Lifer Huang and Ten-Hwang Lai, “On the scalability of IEEE 802.11 ad hoc networks, ” MobiHoc, pp. 173–182, 2002
[16]Ten-Hwang Lai and Dong Zhon, “Efficient and scalable IEEE 802.11 Ad Hoc Mode Timing Synchronization Function, ” IEEE International Conference on Advanced Information Networking and Applications, pp.318–323, 2003
[17]Dong Zhou and Ten-Hwang Lai, “Analysis and Implementation of Scalable Clock Synchronization Protocols in IEEE 802.11 Ad Hoc Networks, ” Mobile Ad Hoc and Sensor Systems (MASS), 2004
[18]M.H Ye, C.T. Lau and A.B. Premkumar, “A modified time synchronization function in IEEE 802.11 using differentiated contention window, ” IEEE International Conference on Information and Communication Security, pp. 1076–1080, Dec. 2003
[19]Peter Rauschert, Arasch Honarbacht and Anton Kummert, “On the IEEE 802.11 IBSS and its Timer Synchronization Function in Multi-Hop Ad Hoc Networks, ” IEEE International Symposium on Wireless Communication Systems, pp.304–308, Sept. 2004
[20]Jang-Ping Sheu, Chih-Min Chao and Ching-Wen Sun, “A clock synchronization algorithm for multi-hop wireless ad hoc networks, ” IEEE International Conference on Distributed Computing Systems, pp. 574-581, 2004
[21]Jungmin So and Nitin Vaidya, “MTSF: A Timing Synchronization Protocol to Support Synchronous Operations in Multi-hop Wireless Networks, ” University of Illinois at Urbana-Champaign, Tech. Rep. Wireless Networking Group Coordinated Science Laboratory, 2004
[22]J. Broch, D. Maltz, D. Johnson, Y. Hu and J. Jetcheva, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, ” in Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 85–97, October 1998.