劉廣鐘,田紀堯,孔維全
(上海海事大學 信息工程學院 水聲傳感器網(wǎng)絡實驗室,上海 201306)
節(jié)點間協(xié)調(diào)與合作完成各項分布式任務離不開時間同步技術(shù)作為支撐和依靠,它是多項關(guān)鍵性技術(shù)的基礎[1],例如時分復用調(diào)度、傳感數(shù)據(jù)融合、介質(zhì)訪問控制協(xié)議等等[2]。然而,水下傳感器節(jié)點部署要求高,一旦部署完成很難進行維護和更換,所以傳感器的計算資源與能量存儲都十分有限。一些陸地傳感器在進行時間同步時往往忽略傳播延遲,然而在水下環(huán)境,巨大的傳播延遲在節(jié)點通信時是不可忽略的重要因素,并且受到海水的溫度、鹽度、密度等多種環(huán)境因素的影響,水下聲波的速度會發(fā)生隨機性較大的變化。其次,傳感器節(jié)點具有隨洋流影響而移動的特點。當某節(jié)點發(fā)送消息和收到回復消息的間隔中,節(jié)點已發(fā)生了相對移動,導致傳播延遲在每次信息交互中都會發(fā)生變化;更重要的是,水下傳感器計算能力有限,不宜設計過于復雜的算法使其消耗大量能量。所以,在設計水聲傳感器網(wǎng)絡的時間同步算法中,須考慮到上述特性。
本文綜合考慮了水聲通信中存在的各種特點,提出了一種水下傳感器時間同步算法。本文主要貢獻如下:
(1)考慮節(jié)點的移動性與空間相關(guān)性,通過一種節(jié)點運動速度估計公式,計算出待同步節(jié)點的移動速率,這是提高時間同步精度的重要因素。
(2)使用3個錨節(jié)點輔助待同步節(jié)點完成時間同步,錨節(jié)點隨機分布在水下環(huán)境,具有標準時間。完成時間同步的普通節(jié)點有機會稱為參考節(jié)點,完成對剩余待同步節(jié)點的同步工作。通過此迭代方法可加快整個網(wǎng)絡的收斂時間,更適用于高密度環(huán)境。
(3)采用發(fā)送-接收的信息交互模式,完成時鐘頻偏與時鐘相偏的估計,并對誤差較大的節(jié)點實施相偏補償。
目前,針對陸地傳感器的時間同步算法的研究成果已十分豐富,但是它們都沒有考慮到海洋環(huán)境的特殊性,并且忽略傳播延遲的存在。因此這類協(xié)議并不適用于水下傳感器。關(guān)于水下傳感器時間同步的研究在近年來開始興起,并且取得了一些研究進展。在文獻[3]中提出了一種成簇時間同步協(xié)議,簇首節(jié)點直接向水面浮標發(fā)出同步請求,但未考慮某些簇首所處位置過深的情況,導致傳播距離過遠,影響同步精度。在文獻[4]中提出了一種多源時間同步算法MSTS,通過多跳傳輸方法進行同步,但每個中間節(jié)點處理數(shù)據(jù)包時都會產(chǎn)生一定時延,經(jīng)過多跳累積造成更大的延遲。并且更多的文獻并未考慮到這個問題。在文獻[5]中提出了基于能量衰減的時間同步算法Ea-Sync,使用移動信標節(jié)點對所有節(jié)點進行時間同步。文獻[6]曾提出使用多普勒原理完成時間同步,通過檢測接收到的超聲波頻率變化來實現(xiàn)時間同步校正,但該方法計算復雜,且應用場景局限性較大。文獻[7]提出了一種多普勒輔助水下傳感器網(wǎng)絡時間同步機制,但文中只研究發(fā)送方和接收方相向運動時的情況,然而真實情況中水下環(huán)境復雜,節(jié)點可能更傾向于無規(guī)則運動,所以需要考慮到節(jié)點各種運動模式。且該方法實現(xiàn)難度過高,且需要額外的硬件才能完成,不適用于實際情況。Mobi-sync[8]引入節(jié)點移動模型,并使用3個信標節(jié)點對一個節(jié)點進行同步,通過一組速度矢量描述一個節(jié)點的運動情況,但此算法過于繁瑣,能耗較大,實現(xiàn)有一定困難。
由于受到水中洋流、溫度、潮汐等多種環(huán)境因素的影響,水下物體的運動速度在方向與數(shù)值上發(fā)生較大的變化。根據(jù)目前的研究結(jié)果表明,水下物體的運動并不是完全隨機,會根據(jù)洋流或者潮汐呈現(xiàn)半周期性的運動特點,這對于預測節(jié)點的速度有著積極的影響,我們可以通過一個具體的洋流模型來預測節(jié)點在水平方向上的運動速度。根據(jù)流體運動學中的假設,水下物體的深度基本保持不變,只在水平方向上發(fā)生移動。文獻[9]使用了一種權(quán)威的二維洋流模型,本文也將使用此洋流模型對錨節(jié)點的運動狀態(tài)進行預測,如式(1)所示
(1)
其中,c用來控制洋流位移速率,B(t)用來控制曲線的寬度,ε用來控制整個洋流場的振幅,參數(shù)ω就是流場中洋流流過的頻率。按經(jīng)驗取值A=1.2,c=0.12,ω=0.4,ε=0.3,k=2π/7.5。一般情況下僅考慮節(jié)點在x和y方向上的位移,不考慮豎直方向上的位移,所以節(jié)點在x和y方向上的運動速度如式(2)所示
(2)
對于每個普通節(jié)點來說,由于其通訊能力有限,它不能與表面浮標通信,且無法預測自身運動狀態(tài),但是利用節(jié)點的時空相關(guān)性,其移動速度的估算可以實現(xiàn)。假定某普通節(jié)點j想要獲得自身的速度[vx(j),vy(j)],其中vx(j),vy(j)分別是在x軸與y軸分量上的速度。如果節(jié)點j能夠獲取其周圍錨節(jié)點的速度,則其自身的速度可以按式(3)計算得到[10]
(3)
其中,m為鄰近錨節(jié)點的數(shù)量,ζij為差值系數(shù),可用式(4)計算得到
(4)
其中,rij為普通節(jié)點與錨節(jié)點之間的歐幾里得距離。需要注意的是,若要使用此運動模型,必須首先獲得錨節(jié)點的運動速度。
為了完成本文提出的同步算法,我們將使用如圖1所示的水下節(jié)點部署場景。場景中共有3種類型的節(jié)點,分別為浮標、錨節(jié)點和普通節(jié)點。浮標均勻部署在監(jiān)測區(qū)域的水平面上,其能量充足,且?guī)в蠫PS定位功能,具有全球標準時間。錨節(jié)點隨機部署在水下區(qū)域,能與浮標直接通信,同樣具有標準時間,用于輔助完成對普通節(jié)點的時鐘同步。普通節(jié)點為待同步節(jié)點,其通信能力較差,無法與浮標直接通信,通過接收錨節(jié)點提供的信息完成自身的同步。本文將主要精力集中在處理錨節(jié)點和普通節(jié)點同步的問題上。
圖1 監(jiān)測區(qū)域網(wǎng)絡拓撲結(jié)構(gòu)
本文將在節(jié)點的同步過程中使用迭代遞歸法的思想。此方法可有效地提高整個網(wǎng)絡同步的收斂速度,有效避免隱藏節(jié)點的問題,并適用于大規(guī)模的監(jiān)測環(huán)境。其基本思想是已完成同步的普通節(jié)點也可充當錨節(jié)點的工作職責,繼續(xù)對水中剩余的待同步節(jié)點進行同步。如圖2所示,在網(wǎng)絡初始化階段,水中只有錨節(jié)點,通過不斷廣播數(shù)據(jù)分組告訴其它節(jié)點自己的身份和位置,此時所有普通節(jié)點皆未同步。其中普通節(jié)點A可通過接收在它通信范圍內(nèi)的3個錨節(jié)點1、2、3完成同步。已完成同步的節(jié)點A此時可扮演參考節(jié)點的角色,向網(wǎng)絡中廣播同步信息,普通節(jié)點B此時就可利用節(jié)點4、5、A完成同步,并以此不斷迭代,直至所有節(jié)點完成同步。使用此方法的原因在于,水中錨節(jié)點的數(shù)量畢竟有限,會有一部分普通節(jié)點并不在錨節(jié)點的通信范圍之內(nèi),導致這些節(jié)點無法進行時間同步。采用迭代法后將不會再存在上述問題,我們只需要保證每個節(jié)點都能接收到其相鄰3個節(jié)點的信息即可。
圖2 節(jié)點迭代同步過程
錨節(jié)點廣播的數(shù)據(jù)分組結(jié)構(gòu)見表1。
表1 錨節(jié)點廣播數(shù)據(jù)幀格式
其中節(jié)點ID為每個錨節(jié)點的唯一標識號;時間戳我們選用MAC層獲取的時間,用于表明信息的發(fā)送時間;速度向量為錨節(jié)點使用洋流模型預測得到的值;所有錨節(jié)點的置信度值皆為1,是普通節(jié)點識別錨節(jié)點的方法。
我們會考慮給每個錨節(jié)點和參考節(jié)點都設置一個置信度,每個待同步節(jié)點內(nèi)部都會維護一張參考節(jié)點表,選取其中3個置信度最高的節(jié)點幫助自身完成時間同步。規(guī)定所有錨節(jié)點的置信度都為1。參考節(jié)點的置信度會按式(5)進行計算
(5)
其中,(u,v,w)是已完成同步的節(jié)點的位置,(xi,yi,zi)為輔助其完成時間同步的3個參考節(jié)點的位置。
本算法將會設置一個定位周期T,所有待同步節(jié)點都會周期性的更新自己的參考節(jié)點表,其中更新過程分為如下3個步驟:
(1)設置一個閾值,若某個參考節(jié)點廣播信息的最后達到時間加上此閾值后仍未被收到,則認為此參考節(jié)點失效,將其從列表中移除。
(2)更新表中參考節(jié)點的位置。由于節(jié)點具有移動性,必須頻繁獲取錨節(jié)點的最新位置以提高算法的精度。我們將按式(6)完成更新
Local(i)=Local(i-1)+T×v(i)
(6)
其中,v(i)是在第i個周期中的估計速度。
(3)若接收到新的參考節(jié)點的廣播消息,則將其信息和置信度添加到表中。
本節(jié)的主要內(nèi)容是描述錨節(jié)點與普通節(jié)點時間同步的具體信息交互過程,當普通節(jié)點的信息表中有足夠的可用于同步的參考節(jié)點后,分別向各個節(jié)點發(fā)送數(shù)據(jù)分組請求開始時間同步進程,參考節(jié)點收到后,隨即向普通節(jié)點發(fā)送多個包含同步數(shù)據(jù)的數(shù)據(jù)分組。具體的信息交互可如圖3所示。
圖3 報文交互過程
根據(jù)時鐘同步原理,待同步節(jié)點A的本地時鐘與標準時鐘的關(guān)系為T=at+b,其中t是標準時間,a代表時鐘頻偏,b代表時鐘相偏。A在T1時刻向錨節(jié)點發(fā)起同步進程,M在T2時刻收到消息后隨即向待同步節(jié)點A發(fā)送多個數(shù)據(jù)分組,其時間戳用t[i]表示,A接收到信息的時間戳用T[i]表示。當節(jié)點M首次發(fā)送同步信息,其發(fā)送時間為t[1],經(jīng)過時間d1后,信息到達待同步節(jié)點A,節(jié)點P記錄下信息到達的本地時間T[1]。經(jīng)過固定時間間隔后,浮標A再次向節(jié)點P發(fā)送第二個同步信息,由于節(jié)點受到洋流等影響會發(fā)生移動,在傳播過程中不可忽略,信息傳播延遲已不是t1而是t2。則可以得到
(7)
需要注意的是,M和A都具有移動性,則假設錨節(jié)點M的移動速度為VMi,待同步節(jié)點A的移動速度為VAi,水聲傳播速度為u,則可推出下式
udi=udi-1+VMi(di-1+di)+VAi(di-1+di)
(8)
此式的意義為,兩節(jié)點在第i次交互時的距離等于第i-1次交互時的距離加上簇首與待同步節(jié)點在傳播過程中分別發(fā)生移動而產(chǎn)生的距離。整理后可得
(9)
其中,VMi和VAi皆可由第二節(jié)提出的速度估計公式計算得出。得到傳播延遲后,則時鐘頻偏可通過下式計算
(10)
在執(zhí)行迭代算法的過程中,可以注意到,某些節(jié)點可通過3個錨節(jié)點輔助完成同步,但有部分節(jié)點可能以兩個錨節(jié)點加一個參考節(jié)點的方式完成同步,最壞情況下,會有少數(shù)節(jié)點利用3個參考節(jié)點完成同步。這在一定程度上會產(chǎn)生節(jié)點定位精度不均的情況,利用3個錨節(jié)點的,定位精度一定最高,利用3個參考節(jié)點的,定位精度一定最低。對于這種情況,本文設計了一種校正方法,令所有未使用3個錨節(jié)點進行同步的節(jié)點獲得相位偏差的補償。我們通過設置一個時間置信度值(TCL)來區(qū)分不同情況下的節(jié)點,當一個節(jié)點是通過k(k=0,1,2)個錨節(jié)點完成時間同步時,規(guī)定其相應的時間置信度為TCL=k/3,TCL值越低,說明需要更多次數(shù)的時間補償。
我們將采用發(fā)送-接收的交互方式使節(jié)點與錨節(jié)點在此進行信息交換。若在第一次同步時利用了兩個錨節(jié)點,則在補償時隨機選擇其中一個錨節(jié)點完成交互;若在第一次同步時利用了一個錨節(jié)點,則使用那唯一一個錨節(jié)點完成交互;若在第一次同步時未利用到錨節(jié)點,則選擇一個置信度最高的參考節(jié)點進行補償。
如圖4所示收集4個時間戳Ta、Tb、Tc、Td,并利用下述公式完成時鐘相偏的計算
(11)
t2-t1=aTd+aTa+2b-Tb-Tc
(12)
圖4 信息交互方式
(13)
(14)
本文采用MATLAB進行仿真,并在相同環(huán)境下,比較本文算法與一些現(xiàn)有算法之間的性能差異。本文的仿真在1000 m*1000 m的水下環(huán)境內(nèi)進行,其中共有200個傳感器節(jié)點且為隨機分布,節(jié)點運動采用隨機洋流模型,并假設節(jié)點深度保持不變。仿真中使用的時間戳為MAC層時間戳。其它實驗參數(shù)如下所示:
(1)時鐘初始頻偏(skew):40 ppm。
(2)時鐘初始相偏(offset):80 μs。
(3)時間粒度:1 μs。
(4)傳感器在水下的深度:100 m-1000 m。
(5)數(shù)據(jù)分組的間隔時間:1 s。
(6)接收端抖動:15 μs。
(7)節(jié)點移動速度變化:1 m/s-4.5 m/s。
由于網(wǎng)絡中存在極少數(shù)節(jié)點無法與任何錨節(jié)點進行通信,為了將這種情況的可能性降到最低,我們將通過仿真確定最合適的錨節(jié)點數(shù)量比例。定義節(jié)點密度為節(jié)點鄰域中的期望節(jié)點數(shù),通過改變節(jié)點的通信半徑來實現(xiàn)。節(jié)點覆蓋度為通信范圍內(nèi)包含錨節(jié)點的普通節(jié)點的數(shù)量占節(jié)點總數(shù)的比例。圖5顯示了錨節(jié)點比例分別為5%、10%、20%情況下的節(jié)點覆蓋度,隨著節(jié)點密度的增加,覆蓋度也隨之提高,所以本文最后決定使用20%的比例設置錨節(jié)點的數(shù)量。
圖5 錨節(jié)點比例與節(jié)點覆蓋度關(guān)系
水下環(huán)境未知多變,需充分考慮算法在不同水域條件下的穩(wěn)定性,圖6顯示了洋流模型中參數(shù)的變化對同步精度的影響,我們設置洋流流過的頻率ω的變化區(qū)間為0.4-0.8,觀察時鐘頻偏隨ω的變化情況(圖中括號后的數(shù)表示參與定位的錨節(jié)點的數(shù)量)。從仿真可以看出,誤差會隨著水流頻率的增大而增大,使用3個錨節(jié)點進行定位的節(jié)點的誤差趨于平穩(wěn),其它3種情況的誤差都有不同程度的上升,由此可見對精度進行補償?shù)闹匾浴?/p>
圖6 洋流頻率對時鐘頻偏的影響
圖7展示了在整個系統(tǒng)完成時間同步后,本地時鐘誤差的增長趨勢,通過將本文算法(MV-Sync)和TSHL、MU-Sync、NU-Sync[11]算法進行對比,從圖7中可以看出,本文算法的誤差累計明顯小于其它算法,而且隨著時間的推移,這種誤差會成倍的增加,本文算法同步誤差之所以會小于其它算法,一是因為通過多個節(jié)點輔助同一個節(jié)點的思想,極大程度上提高了同步精度;二是采用了洋流模型用于測算節(jié)點的速度,提高了傳播延遲的計算精度。
圖7 時鐘同步后時鐘偏差的變化
傳播延遲的動態(tài)變化主要是由節(jié)點的移動速度導致。圖8分析了節(jié)點的移動速度對同步誤差的影響,速度的變化范圍從1 m/s-4.5 m/s,將本文算法與同樣考慮節(jié)點移動性的MU-Sync、D-Sync、NU-Sync算法進行對比,從圖中可以看出,四者的同步精度基本不受速度變化的影響,但是同步誤差卻有好壞之分,MU-Sync的誤差主要在0.023 s左右,D-Sync的誤差主要在0.013 s左右,NU-Sync的誤差主要在0.006 s左右,而本文協(xié)議小于上述3種協(xié)議。
圖8 節(jié)點移動速度對同步的影響
水下傳感器的時間同步工作會受到節(jié)點移動、傳播時延高、低能耗等因素的影響,其中節(jié)點無規(guī)律運動的問題尤為突出,因此本文提出了一種新型的時間同步算法(MV-Sync),首先利用節(jié)點的運動模型與空間相關(guān)性進行節(jié)點的定位與速度測算,然后通過信標節(jié)點迭代方式完成對所有節(jié)點的時間同步工作,并推導出時間同步的參數(shù)計算方程。實驗結(jié)果表明,本文算法在水下環(huán)境中具有良好的穩(wěn)定性,且適用于高密度節(jié)點環(huán)境。在接下來的工作中將會進一步對誤差進行修正,并從能量消耗方面做進一步優(yōu)化。