摘 要： Ad hoc網絡是一種特殊的無線移動通信系統，具有無中心、多跳等特點。結合無線傳感器網絡時鐘同步協議RBS、TPSN和有線網絡DOCSIS協議，提出了一種適合Ad hoc網絡的時鐘同步協議。先在Ad hoc網絡上建立具有層次性的全網絡結構后，以發送廣播時鐘同步信號的方式實現全網絡節點的時鐘相對同步，并通過周期性和突發性的雙向測距實現和維護主從時鐘節點之間精確的時間同步，以滿足實際應用的要求。仿真實驗表明，該時鐘同步協議能滿足不同時鐘同步精度要求下的Ad hoc網絡應用，具有低功耗和高可靠性的特點。
關鍵詞： 無線自組網； 電纜數據傳輸規范； 時鐘同步； 測距
Ad hoc網絡是一種特殊的無線移動通信網絡。Ad hoc網絡的節點不僅具有一般移動終端的基本功能，而且具有報文轉發功能，因此節點間的通信有時需要通過多跳來完成。網絡中的各個節點通過分層的網絡協議相互協調，實現網絡的自組織和運行。由于以上特點，Ad hoc網絡又被稱為多跳無線網(Multi-hop Wireless Network)或自組織網絡(Self-organized Network)。
同所有的分布式系統一樣，時鐘同步也是Ad hoc網絡技術研究中的一個關鍵問題。因為網絡節點內部的硬件時鐘具有一定的誤差，所以節點的本地時間會存在偏差。然而，Ad hoc網絡的許多應用需要全網絡中的節點或一定范圍內的部分節點具有高度的時間一致性，因此Ad hoc網絡需要進行時鐘同步?，F有的有線網絡和無線網絡上的時鐘同步協議并不能完全滿足Ad hoc網絡應用的需要，迫切需要進一步研究，探索出適合Ad hoc網絡的時鐘同步方法。
1 相關研究
1.1 有線網絡上的時鐘同步方法
傳統的時鐘同步方法中最典型的是利用GPS (Global Position System)或NTP[1]協議實現設備間的同步。Ad hoc網絡,尤其是傳感器網絡的節點,必須考慮移動終端的成本代價。GPS裝置價格昂貴，并且在建筑物或水下，其服務質量并不能得到很好的保證,尤其在軍事應用中，利用GPS來獲得無線網絡節點的時鐘同步是極不可靠的。因此，在眾多Ad hoc網絡的應用中利用GPS獲得時鐘同步是不可取的。
NTP協議假設網絡中2個節點的時間請求、回復報文具有相同的時延，由于Ad hoc網絡多跳的無線環境存在非對稱鏈路、前向鏈路和反向鏈路，這些鏈路往往具有不同的時延，因此NTP協議不適合直接應用于Ad hoc網絡；另外，NTP協議需要在網絡中配置時間服務器，Ad hoc網絡是一種移動自組織網絡，沒有中心節點，這也導致了NTP協議無法直接應用于Ad hoc的網絡時鐘同步。
1.2 無線傳感器網絡上的時鐘同步協議
參考文獻[2]提出了一種適合無線傳感器網絡的參考廣播時鐘同步協議(RBS)，該協議利用了“第三方”的廣播時鐘同步信息來完成2個單跳節點的時鐘同步。其基本思路是：在廣播域內周期性地廣播1個數據分組(不必做時間標記)，所有接收到這個數據分組的接收方對該數據分組做時間標記。所有接收方互相交換它們的時間標記，并以此獲得鄰近節點的時鐘。重復以上過程，所有節點不僅知道它們相互之間的相位偏移，而且知道它們相互之間的頻率漂移率。所有節點都不調整它們的本地時鐘，但要為每個鄰近節點建立一個調整時鐘所需要的參數表。仿真結果表明，在Berkeley Motes平臺上30次同步后取平均所獲得的同步精度為1.6 ?滋s。RBS協議雖然可以獲得比較高的同步精度，但其只能應用于單跳范圍內節點間的時鐘同步,將RBS協議擴展到多跳是該協議能否應用于Ad hoc網絡的關鍵。
TPSN(Time-synchronization Protocol for Sensor Networks)[3]是一種用于多跳傳感器網絡的時鐘同步協議，該協議的目標是全網時鐘同步。TPSN包括兩個階段，第一階段是拓撲發現階段，或稱為全網絡同步階段，目的是要建立一個分級的網絡拓撲，其本質就是建立生成樹。如果根節點能訪問一個外部的高精度時鐘，那么網絡中的所有節點都與這個高精度的時鐘同步。第二階段為比對同步階段，由時鐘參考節點周期性地廣播一個同步標志發起，等級為1的節點接收到標志后即和時鐘參考節點同步，同步策略采用類似NTP的“two-way message exchange”，隨后同步依照節點等級向外擴散，每個等級為i的節點向等級為i-1的節點同步，最后完成全網節點與時鐘參考節點的同步。
從直觀上來看，RBS只引入了傳播時延和接收時延，應該具有更高的精度，但在參考文獻[4]的實驗環境下，發送時延和接入時延的不確定性比較小，并且多種不確定因素的作用可能相互抵消，TPSN獲得了優于RBS協議的精度。另外，RBS協議完成一對節點的時鐘同步需要1次報文廣播和至少2次報文單播，TPSN只需要2次報文單播，發送更少的報文，對于共享信道、數據容易發生沖突的無線信道來說,具有更好的可擴展性。
2 基于Ad hoc網絡測距的時鐘同步方法
2.1 雙向傳播時延的計算方法
參考有線網絡上的DOCSIS規范[5]對測距過程的描述，本文提出一種基于時鐘相對同步概念的可應用于Ad hoc網絡的計算雙向傳播時延的方法。
Ad hoc網絡的測距過程分為兩個部分：初始測距和周期性測距。初始測距又分為初始維護(initial maintain)和站維護(station maintain)。在初始測距過程中，鄰近子層設備節點要獲取準確的定時偏移，即基準時鐘同步信號的發送方(主時鐘節點)與某一特定的接收方(從時鐘節點)之間傳輸數據的雙向傳播時延(RTD)。從時鐘節點根據RTD提前發送數據的時間以補償網絡時延,使不同的從時鐘節點所發送的數據到達主時鐘節點的時間與主時鐘節點在帶寬分配報文(MAP)中要求的時間對齊。帶寬分配報文是主時鐘節點向從時鐘節點發送的。雙向傳播時延的計算過程如圖1所示[6]。
RTD包括下行傳輸時延(從主時鐘節點到從時鐘節點)和上行傳輸時延(從從時鐘節點到主時鐘節點)。首先，從時鐘節點從主時鐘節點讀取時間標記，獲得當地時鐘基準，然后根據MAP找到主時鐘節點分配的初始維護區，發出初始測距請求(RNG-REQ)。由于從時鐘節點與主時鐘節點之間存在距離，該請求將延遲一段時間到達，假設到達時刻為T=440。主時鐘節點計算收到RNG-REQ的實際時刻與初始維護區起始時刻之差，在測距響應(RNG-RSP)中通過“定時調整”字段返回給從時鐘節點。主時鐘節點在發送RNG-RSP前還應該獲得從時鐘節點發送的確切頻率、接收的實際功率等信息。主時鐘節點在這些數據的基礎上計算出校正數據，并在RNG-RSP中發送給從時鐘節點。從時鐘節點收到RNG-RSP后，根據下式計算收到第n個RNG-RSP后得到的定時偏移tn：
圖1中初始維護使得從時鐘節點的定時偏移調整為t1=120。在隨后的站維護過程中，從時鐘節點提前t1發送RNG-REQ，該數據分組在站維護區的起始時刻T=740到達主時鐘節點。主時鐘節點根據接收參數計算需要進行的附加微調,并通過輪詢RNG-RSP返回給從時鐘節點。從時鐘節點根據式(1)繼續調整定時偏移,直到主時鐘節點指示測距過程成功。
2.2 全網絡生成樹的建立
建立全網絡同步是從建立生成樹開始的。首先，從根節點發出一個層發現報文(包含根節點的層變量0)。根節點的所有單跳鄰近節點為其自己分配的層號(1)加上層發現報文中的層變量，并接受根節點作為它們的父節點。然后第1層的節點發出它們自己的層發現報文，依此類推。同一層的每個節點選擇一個隨機延遲來避免過多的報文碰撞。一旦某個節點接收到第一個層發現報文，該報文的發出者就被作為接收方的父節點，而后來的層發現報文則被丟掉。節點找到它的父節點以后，就接收父節點周期性發出的時鐘同步信號SYNC，并校正自己的本地時鐘，同時，節點本身也周期性地發出時鐘同步信號，使它的子節點也保持同步。
由于報文碰撞或者在生成樹建立以后某個節點才加入到網絡中，因此有的節點可能沒有接收到層發現報文。如果某節點i在一定的時間內沒有接收到任何層發現報文，那么它就會向它的單跳鄰近節點發出一個層發現請求報文，詢問關于現在生成樹的情況。之后，節點i會密切監聽網絡，收集在某個時間范圍內的請求應答報文，然后在它的鄰近節點中選擇一個層變量最小的節點作為它的父節點。圖2是節點i加入網絡層次結構的過程示意圖。
2.3 測距時鐘同步方法的設計實現
從時鐘節點的初始測距要經歷廣播初始維護和單播站維護2個階段。初始維護階段調整從時鐘節點的功率電平、上行信道中心頻率和定時偏移等信息。站維護階段對上述參數進行微量調整。初始測距過程可以設計為4個狀態：等待初始維護機會、等待測距響應、等待站維護機會和等待輪詢測距響應。圖3所示為該過程的有限狀態機圖。
從時鐘節點必須補償物理層的傳輸時延，相當于將從時鐘節點放在與主時鐘節點相近的地方。因而系統將初始定時偏移設為內部固定的時延量，包括從MAC層到物理層的延遲等。初始測距期間發送第一個RNG-REQ時，根據初始定時偏移計算提前發送的時間。主時鐘節點收到請求后計算定時偏移等參數的校正值，并通過RNG-RSP返回給從時鐘節點。響應中的“測距狀態”字段指出從時鐘節點下一步的動作(繼續、中斷或測距成功)。站維護階段的測距請求、響應步驟重復多次,直到從時鐘節點得到含有測距成功的通知或主時鐘節點放棄測距響應為止。在系統運行過程中，當來自于從時鐘節點的數據的到達時間與主時鐘節點分配的時間之間的誤差超過一定限度時，主時鐘節點可以向從時鐘節點發送報文，要求進行突發性的測距。從時鐘節點周期性地發送測距請求，一般來說，發送周期間隔會比較長。
為了避免主時鐘節點一直沒有響應而造成的從時鐘節點無休止地等待狀態，可以規定等待響應的最長時間，一旦超過這個時間，從時鐘節點將認為主時鐘節點沒有收到它發送的測距請求報文或主時鐘節點出現了故障。初始測距過程涉及到的超時情況包括：T2等待廣播測距機會超時,T3等待測距響應超時,T4等待單播測距機會超時。
3 仿真實驗及分析
實驗采用中科院自主設計的GAINS-2節點，該節點與Mica2節點兼容。GAINS-2節點的微控制器采用Atmega128L，射頻芯片采用CC1000。CC1000是一款面向字節的無線芯片，支持時鐘同步算法在MAC層標記時間戳。節點的操作系統采用無線傳感器網絡專用操作系統TinyOS。實物測試中，為了采集到同一時刻多個節點的本地時鐘信息，把需要同步節點和時鐘基準節點控制器的外部中斷引腳通過導線連接在一起，由需要同步節點觸發外部中斷引腳產生中斷，并在中斷處理程序中記錄采集時間點各個節點的時鐘信息。
仿真環境為一個由64個節點組成的Ad hoc網絡，節點的編號為1~64。分別使用了1號、21號、41號、61號節點作為時間基準節點，并隨機變換節點在網絡中的拓撲位置，從多個角度對時鐘同步算法、同步精度和穩定性進行測試。設同步周期為30 s，在同步完成后5 s采集時鐘信息。這主要是考慮到Ad hoc網絡節點的任務處理延遲，如數據包的加密與解密、連續跟蹤一個活動目標、連續高頻率采集傳感器數據等。圖4所示為網絡中各個節點在不同采集時刻的時鐘同步精度統計數據。
從圖4的統計數據中可以發現，64個節點中的絕大多數節點在采集時刻都具有良好的時鐘同步精度，能夠滿足應用的要求。由于Ad hoc網絡在實際應用中，節點可能被隨機散布在監控區域中，因此系統應當允許有個別節點不能在規定時間內取得時鐘同步，這也是對系統健壯性的一個衡量指標。仿真實驗中，導致個別節點不能在規定時間內取得時鐘同步的原因是節點位置較偏，鄰居節點數目較少，以及實驗中設置的5%的誤碼率和10%的丟包率。
本文提出了一種基于Ad hoc網絡測距的時鐘同步協議，相比傳統的時鐘同步方法，該協議建立系統相對同步只需要一次報文廣播，而RBS協議要求有至少兩次的報文單播；在初始測距成功后，DOCSIS規范只有周期性測距，而本文引進了突發測距機制，允許周期性測距的時間間隔更長。當雙向傳播時延突變時，主時鐘同步節點可以及時進行新一輪測距。仿真測試表明，這種時鐘同步方法能滿足不同時鐘同步精度下的Ad hoc網絡的應用要求，具有低功耗和高可靠性的特點。
參考文獻
[1] MILLS D L． Internet time synchronization： the network time protocol[J]．IEEE Trans Communication，1991，39(10)： 1482-1493．
[2] JERE MY E，LEWIS G，DEBORAH E． Fine-grained network time synchronization using reference broadcasts[A]．Proc 5th Symp Op．Sys Design and Implementation [C]．Boston，MA，2002．
[3] FIKRET S，BULENT Y． Time synchronization in sensor networks：a survey [J]． IEEE Network，2004，7(8)：45-50．
[4] HILL J，CULLER D． A wireless embedded sensor architecture for system level optimization[R]．Tech Rep，UC Berkeley，2001．
[5] CableLabs． Data-over-cable service interface specifications radio frequency interface specification， SP-RFIv1.1I06- 001215[S]．2000：82-85．
[6] 王沁，龍萍，張曉彤，等．基于DOCSIS規范的測距機制分析與嵌入式實現[J]．通信學報，2006，27(9)：96-101．