基于節點測速的水下傳感器時鐘同步迭代算法

劉廣鐘，田紀堯，孔維全

(上海海事大學 信息工程學院 水聲傳感器網絡實驗室，上海 201306)

0 引 言

節點間協調與合作完成各項分布式任務離不開時間同步技術作為支撐和依靠，它是多項關鍵性技術的基礎[1]，例如時分復用調度、傳感數據融合、介質訪問控制協議等等[2]。然而，水下傳感器節點部署要求高，一旦部署完成很難進行維護和更換，所以傳感器的計算資源與能量存儲都十分有限。一些陸地傳感器在進行時間同步時往往忽略傳播延遲，然而在水下環境，巨大的傳播延遲在節點通信時是不可忽略的重要因素，并且受到海水的溫度、鹽度、密度等多種環境因素的影響，水下聲波的速度會發生隨機性較大的變化。其次，傳感器節點具有隨洋流影響而移動的特點。當某節點發送消息和收到回復消息的間隔中，節點已發生了相對移動，導致傳播延遲在每次信息交互中都會發生變化；更重要的是，水下傳感器計算能力有限，不宜設計過于復雜的算法使其消耗大量能量。所以，在設計水聲傳感器網絡的時間同步算法中，須考慮到上述特性。

本文綜合考慮了水聲通信中存在的各種特點，提出了一種水下傳感器時間同步算法。本文主要貢獻如下：

(1)考慮節點的移動性與空間相關性，通過一種節點運動速度估計公式，計算出待同步節點的移動速率，這是提高時間同步精度的重要因素。

(2)使用3個錨節點輔助待同步節點完成時間同步，錨節點隨機分布在水下環境，具有標準時間。完成時間同步的普通節點有機會稱為參考節點，完成對剩余待同步節點的同步工作。通過此迭代方法可加快整個網絡的收斂時間，更適用于高密度環境。

(3)采用發送-接收的信息交互模式，完成時鐘頻偏與時鐘相偏的估計，并對誤差較大的節點實施相偏補償。

1 相關工作

目前，針對陸地傳感器的時間同步算法的研究成果已十分豐富，但是它們都沒有考慮到海洋環境的特殊性，并且忽略傳播延遲的存在。因此這類協議并不適用于水下傳感器。關于水下傳感器時間同步的研究在近年來開始興起，并且取得了一些研究進展。在文獻[3]中提出了一種成簇時間同步協議，簇首節點直接向水面浮標發出同步請求，但未考慮某些簇首所處位置過深的情況，導致傳播距離過遠，影響同步精度。在文獻[4]中提出了一種多源時間同步算法MSTS，通過多跳傳輸方法進行同步，但每個中間節點處理數據包時都會產生一定時延，經過多跳累積造成更大的延遲。并且更多的文獻并未考慮到這個問題。在文獻[5]中提出了基于能量衰減的時間同步算法Ea-Sync，使用移動信標節點對所有節點進行時間同步。文獻[6]曾提出使用多普勒原理完成時間同步，通過檢測接收到的超聲波頻率變化來實現時間同步校正，但該方法計算復雜，且應用場景局限性較大。文獻[7]提出了一種多普勒輔助水下傳感器網絡時間同步機制，但文中只研究發送方和接收方相向運動時的情況，然而真實情況中水下環境復雜，節點可能更傾向于無規則運動，所以需要考慮到節點各種運動模式。且該方法實現難度過高，且需要額外的硬件才能完成，不適用于實際情況。Mobi-sync[8]引入節點移動模型，并使用3個信標節點對一個節點進行同步，通過一組速度矢量描述一個節點的運動情況，但此算法過于繁瑣，能耗較大，實現有一定困難。

2 速度預測方法

由于受到水中洋流、溫度、潮汐等多種環境因素的影響，水下物體的運動速度在方向與數值上發生較大的變化。根據目前的研究結果表明，水下物體的運動并不是完全隨機，會根據洋流或者潮汐呈現半周期性的運動特點，這對于預測節點的速度有著積極的影響，我們可以通過一個具體的洋流模型來預測節點在水平方向上的運動速度。根據流體運動學中的假設，水下物體的深度基本保持不變，只在水平方向上發生移動。文獻[9]使用了一種權威的二維洋流模型，本文也將使用此洋流模型對錨節點的運動狀態進行預測，如式(1)所示

(1)

其中，c用來控制洋流位移速率，B(t)用來控制曲線的寬度，ε用來控制整個洋流場的振幅，參數ω就是流場中洋流流過的頻率。按經驗取值A=1.2，c=0.12，ω=0.4，ε=0.3，k=2π/7.5。一般情況下僅考慮節點在x和y方向上的位移，不考慮豎直方向上的位移，所以節點在x和y方向上的運動速度如式(2)所示

(2)

對于每個普通節點來說，由于其通訊能力有限，它不能與表面浮標通信，且無法預測自身運動狀態，但是利用節點的時空相關性，其移動速度的估算可以實現。假定某普通節點j想要獲得自身的速度[vx(j),vy(j)]，其中vx(j)，vy(j)分別是在x軸與y軸分量上的速度。如果節點j能夠獲取其周圍錨節點的速度，則其自身的速度可以按式(3)計算得到[10]

(3)

其中，m為鄰近錨節點的數量，ζij為差值系數，可用式(4)計算得到

(4)

其中，rij為普通節點與錨節點之間的歐幾里得距離。需要注意的是，若要使用此運動模型，必須首先獲得錨節點的運動速度。

3 算法設計與實現

為了完成本文提出的同步算法，我們將使用如圖1所示的水下節點部署場景。場景中共有3種類型的節點，分別為浮標、錨節點和普通節點。浮標均勻部署在監測區域的水平面上，其能量充足，且帶有GPS定位功能，具有全球標準時間。錨節點隨機部署在水下區域，能與浮標直接通信，同樣具有標準時間，用于輔助完成對普通節點的時鐘同步。普通節點為待同步節點，其通信能力較差，無法與浮標直接通信，通過接收錨節點提供的信息完成自身的同步。本文將主要精力集中在處理錨節點和普通節點同步的問題上。

圖1 監測區域網絡拓撲結構

3.1 節點迭代同步方法

本文將在節點的同步過程中使用迭代遞歸法的思想。此方法可有效地提高整個網絡同步的收斂速度，有效避免隱藏節點的問題，并適用于大規模的監測環境。其基本思想是已完成同步的普通節點也可充當錨節點的工作職責，繼續對水中剩余的待同步節點進行同步。如圖2所示，在網絡初始化階段，水中只有錨節點，通過不斷廣播數據分組告訴其它節點自己的身份和位置，此時所有普通節點皆未同步。其中普通節點A可通過接收在它通信范圍內的3個錨節點1、2、3完成同步。已完成同步的節點A此時可扮演參考節點的角色，向網絡中廣播同步信息，普通節點B此時就可利用節點4、5、A完成同步，并以此不斷迭代，直至所有節點完成同步。使用此方法的原因在于，水中錨節點的數量畢竟有限，會有一部分普通節點并不在錨節點的通信范圍之內，導致這些節點無法進行時間同步。采用迭代法后將不會再存在上述問題，我們只需要保證每個節點都能接收到其相鄰3個節點的信息即可。

圖2 節點迭代同步過程

錨節點廣播的數據分組結構見表1。

表1 錨節點廣播數據幀格式

其中節點ID為每個錨節點的唯一標識號；時間戳我們選用MAC層獲取的時間，用于表明信息的發送時間；速度向量為錨節點使用洋流模型預測得到的值；所有錨節點的置信度值皆為1，是普通節點識別錨節點的方法。

我們會考慮給每個錨節點和參考節點都設置一個置信度，每個待同步節點內部都會維護一張參考節點表，選取其中3個置信度最高的節點幫助自身完成時間同步。規定所有錨節點的置信度都為1。參考節點的置信度會按式(5)進行計算

(5)

其中，(u,v,w)是已完成同步的節點的位置，(xi,yi,zi)為輔助其完成時間同步的3個參考節點的位置。

本算法將會設置一個定位周期T，所有待同步節點都會周期性的更新自己的參考節點表，其中更新過程分為如下3個步驟：

(1)設置一個閾值，若某個參考節點廣播信息的最后達到時間加上此閾值后仍未被收到，則認為此參考節點失效，將其從列表中移除。

(2)更新表中參考節點的位置。由于節點具有移動性，必須頻繁獲取錨節點的最新位置以提高算法的精度。我們將按式(6)完成更新

Local(i)=Local(i-1)+T×v(i)

(6)

其中，v(i)是在第i個周期中的估計速度。

(3)若接收到新的參考節點的廣播消息，則將其信息和置信度添加到表中。

3.2 信息交換過程

本節的主要內容是描述錨節點與普通節點時間同步的具體信息交互過程，當普通節點的信息表中有足夠的可用于同步的參考節點后，分別向各個節點發送數據分組請求開始時間同步進程，參考節點收到后，隨即向普通節點發送多個包含同步數據的數據分組。具體的信息交互可如圖3所示。

圖3 報文交互過程

根據時鐘同步原理，待同步節點A的本地時鐘與標準時鐘的關系為T=at+b，其中t是標準時間，a代表時鐘頻偏，b代表時鐘相偏。A在T1時刻向錨節點發起同步進程，M在T2時刻收到消息后隨即向待同步節點A發送多個數據分組，其時間戳用t[i]表示，A接收到信息的時間戳用T[i]表示。當節點M首次發送同步信息，其發送時間為t[1]，經過時間d1后，信息到達待同步節點A，節點P記錄下信息到達的本地時間T[1]。經過固定時間間隔后，浮標A再次向節點P發送第二個同步信息，由于節點受到洋流等影響會發生移動，在傳播過程中不可忽略，信息傳播延遲已不是t1而是t2。則可以得到

(7)

需要注意的是，M和A都具有移動性，則假設錨節點M的移動速度為VMi，待同步節點A的移動速度為VAi，水聲傳播速度為u，則可推出下式

udi=udi-1+VMi(di-1+di)+VAi(di-1+di)

(8)

此式的意義為，兩節點在第i次交互時的距離等于第i-1次交互時的距離加上簇首與待同步節點在傳播過程中分別發生移動而產生的距離。整理后可得

(9)

其中，VMi和VAi皆可由第二節提出的速度估計公式計算得出。得到傳播延遲后，則時鐘頻偏可通過下式計算

(10)

3.3 誤差補償

在執行迭代算法的過程中，可以注意到，某些節點可通過3個錨節點輔助完成同步，但有部分節點可能以兩個錨節點加一個參考節點的方式完成同步，最壞情況下，會有少數節點利用3個參考節點完成同步。這在一定程度上會產生節點定位精度不均的情況，利用3個錨節點的，定位精度一定最高，利用3個參考節點的，定位精度一定最低。對于這種情況，本文設計了一種校正方法，令所有未使用3個錨節點進行同步的節點獲得相位偏差的補償。我們通過設置一個時間置信度值(TCL)來區分不同情況下的節點，當一個節點是通過k(k=0,1,2)個錨節點完成時間同步時，規定其相應的時間置信度為TCL=k/3，TCL值越低，說明需要更多次數的時間補償。

我們將采用發送-接收的交互方式使節點與錨節點在此進行信息交換。若在第一次同步時利用了兩個錨節點，則在補償時隨機選擇其中一個錨節點完成交互；若在第一次同步時利用了一個錨節點，則使用那唯一一個錨節點完成交互；若在第一次同步時未利用到錨節點，則選擇一個置信度最高的參考節點進行補償。

如圖4所示收集4個時間戳Ta、Tb、Tc、Td，并利用下述公式完成時鐘相偏的計算

(11)

t2-t1=aTd+aTa+2b-Tb-Tc

(12)

圖4 信息交互方式

(13)

(14)

4 實驗仿真

4.1 仿真參數設置

本文采用MATLAB進行仿真，并在相同環境下，比較本文算法與一些現有算法之間的性能差異。本文的仿真在1000 m*1000 m的水下環境內進行，其中共有200個傳感器節點且為隨機分布，節點運動采用隨機洋流模型，并假設節點深度保持不變。仿真中使用的時間戳為MAC層時間戳。其它實驗參數如下所示：

(1)時鐘初始頻偏(skew)：40 ppm。

(2)時鐘初始相偏(offset)：80 μs。

(3)時間粒度：1 μs。

(4)傳感器在水下的深度：100 m-1000 m。

(5)數據分組的間隔時間：1 s。

(6)接收端抖動：15 μs。

(7)節點移動速度變化：1 m/s-4.5 m/s。

4.2 實驗結果及分析

由于網絡中存在極少數節點無法與任何錨節點進行通信，為了將這種情況的可能性降到最低，我們將通過仿真確定最合適的錨節點數量比例。定義節點密度為節點鄰域中的期望節點數，通過改變節點的通信半徑來實現。節點覆蓋度為通信范圍內包含錨節點的普通節點的數量占節點總數的比例。圖5顯示了錨節點比例分別為5%、10%、20%情況下的節點覆蓋度，隨著節點密度的增加，覆蓋度也隨之提高，所以本文最后決定使用20%的比例設置錨節點的數量。

圖5 錨節點比例與節點覆蓋度關系

水下環境未知多變，需充分考慮算法在不同水域條件下的穩定性，圖6顯示了洋流模型中參數的變化對同步精度的影響，我們設置洋流流過的頻率ω的變化區間為0.4-0.8，觀察時鐘頻偏隨ω的變化情況(圖中括號后的數表示參與定位的錨節點的數量)。從仿真可以看出，誤差會隨著水流頻率的增大而增大，使用3個錨節點進行定位的節點的誤差趨于平穩，其它3種情況的誤差都有不同程度的上升，由此可見對精度進行補償的重要性。

圖6 洋流頻率對時鐘頻偏的影響

圖7展示了在整個系統完成時間同步后，本地時鐘誤差的增長趨勢，通過將本文算法(MV-Sync)和TSHL、MU-Sync、NU-Sync[11]算法進行對比，從圖7中可以看出，本文算法的誤差累計明顯小于其它算法，而且隨著時間的推移，這種誤差會成倍的增加，本文算法同步誤差之所以會小于其它算法，一是因為通過多個節點輔助同一個節點的思想，極大程度上提高了同步精度；二是采用了洋流模型用于測算節點的速度，提高了傳播延遲的計算精度。

圖7 時鐘同步后時鐘偏差的變化

傳播延遲的動態變化主要是由節點的移動速度導致。圖8分析了節點的移動速度對同步誤差的影響，速度的變化范圍從1 m/s-4.5 m/s，將本文算法與同樣考慮節點移動性的MU-Sync、D-Sync、NU-Sync算法進行對比，從圖中可以看出，四者的同步精度基本不受速度變化的影響，但是同步誤差卻有好壞之分，MU-Sync的誤差主要在0.023 s左右，D-Sync的誤差主要在0.013 s左右，NU-Sync的誤差主要在0.006 s左右，而本文協議小于上述3種協議。

圖8 節點移動速度對同步的影響

5 結束語

水下傳感器的時間同步工作會受到節點移動、傳播時延高、低能耗等因素的影響，其中節點無規律運動的問題尤為突出，因此本文提出了一種新型的時間同步算法(MV-Sync)，首先利用節點的運動模型與空間相關性進行節點的定位與速度測算，然后通過信標節點迭代方式完成對所有節點的時間同步工作，并推導出時間同步的參數計算方程。實驗結果表明，本文算法在水下環境中具有良好的穩定性，且適用于高密度節點環境。在接下來的工作中將會進一步對誤差進行修正，并從能量消耗方面做進一步優化。