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