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