摘 要： 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)和維護(hù)主從時鐘節(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ò)的自組織和運(yùn)行。由于以上特點，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ò)需要進(jìn)行時鐘同步?，F(xiàn)有的有線網(wǎng)絡(luò)和無線網(wǎng)絡(luò)上的時鐘同步協(xié)議并不能完全滿足Ad hoc網(wǎng)絡(luò)應(yīng)用的需要，迫切需要進(jìn)一步研究，探索出適合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é)議
參考文獻(xiàn)[2]提出了一種適合無線傳感器網(wǎng)絡(luò)的參考廣播時鐘同步協(xié)議(RBS)，該協(xié)議利用了“第三方”的廣播時鐘同步信息來完成2個單跳節(jié)點的時鐘同步。其基本思路是：在廣播域內(nèi)周期性地廣播1個數(shù)據(jù)分組(不必做時間標(biāo)記)，所有接收到這個數(shù)據(jù)分組的接收方對該數(shù)據(jù)分組做時間標(biāo)記。所有接收方互相交換它們的時間標(biāo)記，并以此獲得鄰近節(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é)議擴(kuò)展到多跳是該協(xié)議能否應(yīng)用于Ad hoc網(wǎng)絡(luò)的關(guān)鍵。
TPSN(Time-synchronization Protocol for Sensor Networks)[3]是一種用于多跳傳感器網(wǎng)絡(luò)的時鐘同步協(xié)議，該協(xié)議的目標(biāo)是全網(wǎng)時鐘同步。TPSN包括兩個階段，第一階段是拓?fù)浒l(fā)現(xiàn)階段，或稱為全網(wǎng)絡(luò)同步階段，目的是要建立一個分級的網(wǎng)絡(luò)拓?fù)?，其本質(zhì)就是建立生成樹。如果根節(jié)點能訪問一個外部的高精度時鐘，那么網(wǎng)絡(luò)中的所有節(jié)點都與這個高精度的時鐘同步。第二階段為比對同步階段，由時鐘參考節(jié)點周期性地廣播一個同步標(biāo)志發(fā)起，等級為1的節(jié)點接收到標(biāo)志后即和時鐘參考節(jié)點同步，同步策略采用類似NTP的“two-way message exchange”，隨后同步依照節(jié)點等級向外擴(kuò)散，每個等級為i的節(jié)點向等級為i-1的節(jié)點同步，最后完成全網(wǎng)節(jié)點與時鐘參考節(jié)點的同步。
從直觀上來看，RBS只引入了傳播時延和接收時延，應(yīng)該具有更高的精度，但在參考文獻(xiàn)[4]的實驗環(huán)境下，發(fā)送時延和接入時延的不確定性比較小，并且多種不確定因素的作用可能相互抵消，TPSN獲得了優(yōu)于RBS協(xié)議的精度。另外，RBS協(xié)議完成一對節(jié)點的時鐘同步需要1次報文廣播和至少2次報文單播，TPSN只需要2次報文單播，發(fā)送更少的報文，對于共享信道、數(shù)據(jù)容易發(fā)生沖突的無線信道來說,具有更好的可擴(kuò)展性。
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ò)的測距過程分為兩個部分：初始測距和周期性測距。初始測距又分為初始維護(hù)(initial maintain)和站維護(hù)(station maintain)。在初始測距過程中，鄰近子層設(shè)備節(jié)點要獲取準(zhǔn)確的定時偏移，即基準(zhǔn)時鐘同步信號的發(fā)送方(主時鐘節(jié)點)與某一特定的接收方(從時鐘節(jié)點)之間傳輸數(shù)據(jù)的雙向傳播時延(RTD)。從時鐘節(jié)點根據(jù)RTD提前發(fā)送數(shù)據(jù)的時間以補(bǔ)償網(wǎng)絡(luò)時延,使不同的從時鐘節(jié)點所發(fā)送的數(shù)據(jù)到達(dá)主時鐘節(jié)點的時間與主時鐘節(jié)點在帶寬分配報文(MAP)中要求的時間對齊。帶寬分配報文是主時鐘節(jié)點向從時鐘節(jié)點發(fā)送的。雙向傳播時延的計算過程如圖1所示[6]。
RTD包括下行傳輸時延(從主時鐘節(jié)點到從時鐘節(jié)點)和上行傳輸時延(從從時鐘節(jié)點到主時鐘節(jié)點)。首先，從時鐘節(jié)點從主時鐘節(jié)點讀取時間標(biāo)記，獲得當(dāng)?shù)貢r鐘基準(zhǔn)，然后根據(jù)MAP找到主時鐘節(jié)點分配的初始維護(hù)區(qū)，發(fā)出初始測距請求(RNG-REQ)。由于從時鐘節(jié)點與主時鐘節(jié)點之間存在距離，該請求將延遲一段時間到達(dá)，假設(shè)到達(dá)時刻為T=440。主時鐘節(jié)點計算收到RNG-REQ的實際時刻與初始維護(hù)區(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中初始維護(hù)使得從時鐘節(jié)點的定時偏移調(diào)整為t1=120。在隨后的站維護(hù)過程中，從時鐘節(jié)點提前t1發(fā)送RNG-REQ，該數(shù)據(jù)分組在站維護(hù)區(qū)的起始時刻T=740到達(dá)主時鐘節(jié)點。主時鐘節(jié)點根據(jù)接收參數(shù)計算需要進(jìn)行的附加微調(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é)點選擇一個隨機(jī)延遲來避免過多的報文碰撞。一旦某個節(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)歷廣播初始維護(hù)和單播站維護(hù)2個階段。初始維護(hù)階段調(diào)整從時鐘節(jié)點的功率電平、上行信道中心頻率和定時偏移等信息。站維護(hù)階段對上述參數(shù)進(jìn)行微量調(diào)整。初始測距過程可以設(shè)計為4個狀態(tài)：等待初始維護(hù)機(jī)會、等待測距響應(yīng)、等待站維護(hù)機(jī)會和等待輪詢測距響應(yīng)。圖3所示為該過程的有限狀態(tài)機(jī)圖。
從時鐘節(jié)點必須補(bǔ)償物理層的傳輸時延，相當(dāng)于將從時鐘節(jié)點放在與主時鐘節(jié)點相近的地方。因而系統(tǒng)將初始定時偏移設(shè)為內(nèi)部固定的時延量，包括從MAC層到物理層的延遲等。初始測距期間發(fā)送第一個RNG-REQ時，根據(jù)初始定時偏移計算提前發(fā)送的時間。主時鐘節(jié)點收到請求后計算定時偏移等參數(shù)的校正值，并通過RNG-RSP返回給從時鐘節(jié)點。響應(yīng)中的“測距狀態(tài)”字段指出從時鐘節(jié)點下一步的動作(繼續(xù)、中斷或測距成功)。站維護(hù)階段的測距請求、響應(yīng)步驟重復(fù)多次,直到從時鐘節(jié)點得到含有測距成功的通知或主時鐘節(jié)點放棄測距響應(yīng)為止。在系統(tǒng)運(yùn)行過程中，當(dāng)來自于從時鐘節(jié)點的數(shù)據(jù)的到達(dá)時間與主時鐘節(jié)點分配的時間之間的誤差超過一定限度時，主時鐘節(jié)點可以向從時鐘節(jié)點發(fā)送報文，要求進(jìn)行突發(fā)性的測距。從時鐘節(jié)點周期性地發(fā)送測距請求，一般來說，發(fā)送周期間隔會比較長。
為了避免主時鐘節(jié)點一直沒有響應(yīng)而造成的從時鐘節(jié)點無休止地等待狀態(tài)，可以規(guī)定等待響應(yīng)的最長時間，一旦超過這個時間，從時鐘節(jié)點將認(rèn)為主時鐘節(jié)點沒有收到它發(fā)送的測距請求報文或主時鐘節(jié)點出現(xiàn)了故障。初始測距過程涉及到的超時情況包括：T2等待廣播測距機(jī)會超時,T3等待測距響應(yīng)超時,T4等待單播測距機(jī)會超時。
3 仿真實驗及分析
實驗采用中科院自主設(shè)計的GAINS-2節(jié)點，該節(jié)點與Mica2節(jié)點兼容。GAINS-2節(jié)點的微控制器采用Atmega128L，射頻芯片采用CC1000。CC1000是一款面向字節(jié)的無線芯片，支持時鐘同步算法在MAC層標(biāo)記時間戳。節(jié)點的操作系統(tǒng)采用無線傳感器網(wǎng)絡(luò)專用操作系統(tǒng)TinyOS。實物測試中，為了采集到同一時刻多個節(jié)點的本地時鐘信息，把需要同步節(jié)點和時鐘基準(zhǔn)節(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é)點作為時間基準(zhǔn)節(jié)點，并隨機(jī)變換節(jié)點在網(wǎng)絡(luò)中的拓?fù)湮恢茫瑥亩鄠€角度對時鐘同步算法、同步精度和穩(wěn)定性進(jìn)行測試。設(shè)同步周期為30 s，在同步完成后5 s采集時鐘信息。這主要是考慮到Ad hoc網(wǎng)絡(luò)節(jié)點的任務(wù)處理延遲，如數(shù)據(jù)包的加密與解密、連續(xù)跟蹤一個活動目標(biāo)、連續(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é)點可能被隨機(jī)散布在監(jiān)控區(qū)域中，因此系統(tǒng)應(yīng)當(dāng)允許有個別節(jié)點不能在規(guī)定時間內(nèi)取得時鐘同步，這也是對系統(tǒng)健壯性的一個衡量指標(biāo)。仿真實驗中，導(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ī)范只有周期性測距，而本文引進(jìn)了突發(fā)測距機(jī)制，允許周期性測距的時間間隔更長。當(dāng)雙向傳播時延突變時，主時鐘同步節(jié)點可以及時進(jìn)行新一輪測距。仿真測試表明，這種時鐘同步方法能滿足不同時鐘同步精度下的Ad hoc網(wǎng)絡(luò)的應(yīng)用要求，具有低功耗和高可靠性的特點。
參考文獻(xiàn)
[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ī)范的測距機(jī)制分析與嵌入式實現(xiàn)[J]．通信學(xué)報，2006，27(9)：96-101．