無線自組織網絡協作時間同步優化算法

劉大鹍， 陳桂芬， 王義君

(1.長春理工大學 電子信息工程學院， 吉林 長春 130022; 2.中國北方車輛研究所 網絡與信息中心， 北京 100072)

0 引言

無線自組織網絡通常布置在具有一定面積的局部范圍之內，由若干信息采集及傳輸節點組成，該網絡采用無線通信方式且能夠動態組網，具有多跳通信及移動性等特點[1]。在軍事應用領域，不論是集群單兵作戰系統還是無人平臺協作攻擊及防護系統，都可認為是無線自組織網絡的一部分。其目的是通過動態路由和移動管理技術傳輸具有服務質量要求的多媒體信息流，一般節點需要具有持續的能量供給[2]。從目前看，無線自組織網絡的關鍵技術包括射頻識別技術、無線傳感器網絡技術、智能嵌入技術、自組織管理技術以及安全技術等[3]。但是對于絕大多數應用場景，尤其是軍事領域，如果能夠通信的網絡節點不能有效實現時間同步，那么很多應用將變得沒有意義。因此無線自組織網絡時間同步技術的研究是未來軍事及民用領域能夠實現廣泛應用的技術基礎。無線自組織網絡中的節點只有實現精確的時間同步，才能保證目標跟蹤、定位、拓撲控制等技術得以有效實現[4-6]。

目前，眾多學者對于無線自組織網絡時間同步技術進行了較為深入的研究。文獻[7]提出一種基于相位同步的最小生成樹分析方法。該方法通過相位同步建立不同時間序列之間的相關性，主要包括相互關聯、 線性和非線性。同時，在這種方法中，一對時間序列 (節點) 之間的鏈接強度是由它們之間的相位同步級別決定的，利用非線性相關經濟時間序列實現同步分析。文獻[8]提出了面向無線傳感器網絡的快速精確、能量有效的時間同步協議。該協議的設計用于惡劣環境，并基于電阻式電網的思想。通過協議的執行可以產生高質量時間估計，在整個通信周期中保證時間同步的準確性。文獻[9]針對無線傳感器網絡經典同步算法穩定性較差等問題，提出一種基于頻率偏差估計的時間同步算法。該方法通過低開銷相位偏差和頻率偏差估計方法，結合分層和廣播監聽構建響應的同步策略，可有效地平衡同步能耗、同步精度及同步穩定性。針對同步精度對隨機延遲和時鐘速率波動敏感等問題，文獻[10]將成對同步誤差建模為隨機延遲和時鐘漂移的功能函數，并以定量的模型同步性能作為相關參數的函數衡量指標，同時，針對不同對等同步方案分析了同步誤差。文獻[11]針對時間誤差的累積以及節點多跳傳輸能量損耗等問題，提出基于移動參考節點和最優移動路徑的時鐘同步方法。該方法首先選取時鐘同步節點，然后建立數學模型，最后通過標記時間戳建立單跳同步機制，提高同步時間精度同時，降低了通信能耗。

本文在上述研究基礎上提出無線自組織網絡協作時間同步優化算法(CTSOA)。該算法在時間同步信號模型和基于接收端- 接收端的同步機制模型基礎上，利用指數延遲模型，通過對成對節點的時鐘偏移及時鐘漂移進行聯合估計提高時鐘同步精度；對網絡進行三角剖分，利用拓撲結構的自適應變化實現全網節點時鐘同步；通過協作時間同步優化算法的整體執行，保證鏈路時延及網絡能耗的降低。仿真結果表明，在本文提出的三角剖分拓撲結構控制下，與傳統分簇拓撲相比，CTSOA在平均同步誤差、同步算法能量消耗方面取得了一定的改進。

1 時間同步模型

無線自組織網絡中每個節點相互鏈接，通過多跳路由完成信息傳輸。大多數情況下，只有網絡節點的時間精度滿足一定的范圍要求，才能實現無線自組織網絡的應用，因此每個網絡節點都遵循自身的本地時鐘，而晶振的頻率和閾值決定了時鐘同步的解決方式。本文所設計及采用的時間同步模型主要包括時間同步信號模型及接收端- 接收端同步機制模型。

1.1 時間同步信號模型

對于接收端- 接收端時間同步方法，接收側的時間延遲是時間同步誤差的重要來源[12]。其最大特點是使關鍵路徑上的發送時間延遲和訪問時間延遲得以消除。傳輸時延示意圖如圖1所示。

圖1 傳輸時延分析Fig.1 Transmission delay analysis

令網絡節點的本地時鐘為T(t)，t為理想參考時間。由于晶振的不確定性，第i個節點的時間模型可以定義為

Ti(t)=ωit+φi+εi，

(1)

式中：ωi為時鐘漂移(或頻率偏差)；φi為時鐘偏移(或相位偏差)；εi為隨機噪聲。此時，網絡中2個節點(節點1和節點2)間的時鐘關系可以表示為

T1(t)=ω12T2(t)+φ12+εi，

(2)

式中：ω12和φ12分別為節點1和節點2間的相對時鐘漂移系數和相對時間偏移。因此，當ω12=1、φ12=0 μs時，兩個節點將完全實現時間同步。如果網絡中有N個節點，則當Ti(t)=Tj(t)時，整個網絡將實現全局同步，i,j=1,…,N.

時鐘偏移估算是時間同步算法中非常重要的一個環節。Elson等[13]通過實驗證明接收端任意兩個節點間本地時間差的時鐘偏移符合μ=0、σ=11.1 μs的高斯分布，其中，μ為時鐘漂移系數，σ為相對時間偏移。本文仿真擬合出的最佳參數結果為μ=0.048、σ=11.221 μs，統計學分布圖如圖2所示。該實驗結果對于后續算法的實現具有重要指導作用。

圖2 時鐘偏移統計學分布Fig.2 Clock offset statistical distribution

1.2 通信模型

自組織網絡中異構網絡結構不同，對于傳輸對象的信號帶寬也不盡相同，每個節點必須能夠感知信號的頻帶寬度，用以完成對網絡的選擇和信號的傳輸。在實際應用中，當被監測區域中的監測對象不在節點的通信范圍之內時，節點則不能感知到監測對象，此時還需考慮發射功率對于接收節點的影響。

根據電磁波傳播理論，當其在自由空間中傳播時，如果發射端與接收端在視距范圍之內，則可用自由空間傳播模型預測接收信號的強度。如果發射端的信源發射功率為PT，則收發節點之間的信號功率關系為

(3)

式中：PR為信宿接收功率；λ為載波波長；r為收發端的距離；AT、AR分別為信源天線和信宿天線的增益；δ為信道衰落系數。

1.3 接收端- 接收端同步機制模型

圖3 接收端- 接收端同步機制模型Fig.3 Receiver-receiver synchronization model

接收端- 接收端同步機制模型如圖3所示。節點R表示參考節點，為發送端節點，負責初始化同步協議，并向在其通信范圍內的接收端節點S和M廣播信標包，其中：節點M為主節點，該節點與參考節點R實現雙向通信，接收節點R發送的廣播信標包，并向節點S發送同步信息；節點S為從節點，通過接收參考節點R的廣播信標包和主節點M同步信息完成自身的同步誤差修正，實現與主節點M的時間同步。接收端兩節點通過記錄每一輪同步信標包中的時間戳，完成對于時鐘偏移和時鐘漂移的相應估計，節點M修改自己的時間偏移來完成一次時間同步。隨著時間同步周期次數的增多，節點S通過周期性地接收節點R與節點M的雙向信息，不斷地調整自己的同步延遲，使自身與節點M時間同步。

2 時間同步算法

針對目前無線自組織網絡時間同步算法同步精度低、能量消耗大等問題[14-15]，提出無線自組織網絡協作時間同步優化算法。本算法利用指數模型，通過對成對節點的時鐘偏移及漂移進行聯合估計來提高時鐘同步精度；利用拓撲結構的自適應變化實現全網節點時鐘同步；通過協作時間同步優化算法的整體執行，保證鏈路時延及網絡能耗的降低。

2.1 成對節點時鐘漂移及時鐘偏移的聯合估計

圖4給出了主節點與從節點間時間信息交互的時鐘漂移與時鐘偏移模型。如圖4所示，M為主節點，S為從節點，主節點記錄第m輪信息交互的時間戳TM1、TM4，從節點記錄第m輪信息交互的時間戳TS2、TS3. 主節點傳輸同步包給從節點，該同步包中包含主節點的本地時間戳TM1，從節點在TS2接收到該同步包并且在TS3發出一個應答包，主節點在TM4接收到該應答包。該過程中，從節點的時間模型可定義為

TS2=(TM1+td)ω+φ+ΓS2，

(4)

TS3=(TM4-td)ω+φ+ΓS3，

(5)

式中：td為傳播過程的固定時延；ω為時鐘漂移；φ為時鐘偏移；ΓS2、ΓS3一般為符合高斯分布的隨機噪聲。

圖4 時間信息交互模型Fig.4 Timing message exchange model

由上述模型，給出一種指數模型估計的一般似然函數形式：

(6)

式中：Q為循環周期；輔助函數L定義為

(7)

由(6)式可知，如果將隨機噪聲忽略，與時鐘估計相關的參量只有固定時延td，該參量一般可以通過消息包信息交換計算得出，但必然會增加網絡能耗。因此，在上述模型基礎上，不計算固定時延，認為其為未知量，在此條件下估算ω及φ值。

因為td和φ均未知，所以其定義域可限制為

(8)

統計因子E可表示為

(9)

式中：k為循環輪次。

(10)

(11)

(12)

2.2 自適應全網絡同步

2.2.1 參考節點確定

假設網絡覆蓋區域為C，采用計算幾何的方式選取參考節點。將區域C劃分為u個單調多邊形，目的是通過引入對角線消除多邊形不規則情況下引起的拐點。設點p為一拐點，與其連接的2條多邊形的邊為向下方向，則此時需構造1條以p為起點向上連接的對角線，該對角線將原多邊形分為2部分，此時p不再屬于拐點，而屬于劃分后2個多邊形的1個頂點，基于此完成區域C的單調劃分。然后，按隨機次序依次引入網絡中的各節點，維護程序的執行并更新一個與當前點集對應的三角剖分?；谌瞧史值木W絡區域劃分算法流程如圖5所示。

圖5 網絡區域劃分算法

Fig.5 Network region division algorithm

通過對覆蓋區域的外部多邊形結構進行單調劃分和三角剖分，圖6給出了無線自組織網絡內有50個節點時在平面區域內劃分的三角剖分拓撲結構圖。

圖6 經過三角剖分后的網絡拓撲結構Fig.6 Network topology after triangulating

經過三角剖分的拓撲結構形成后，令三角形頂點處的節點組成一個子集。為了最大限度地在該子集中找到盡可能少的節點、完成區域覆蓋任務，使用紅、黃、綠3種顏色給子集中的所有節點進行染色。染色方案需滿足由任何邊連接的2個節點，所染的顏色不能相同?；诖?，經過三角剖分的多邊形經過染色后，其中每個三角形都有且僅有1個紅色、黃色和藍色的頂點。通過上述方法，當網絡完成三角劃分后，選擇劃分好的三角形中質心點位置節點作為參考節點，該節點需覆蓋所在三角區域的通信距離。參考節點選擇示意圖如圖7所示。

圖7 參考節點選擇示意圖Fig.7 Reference node selection

2.2.2 多跳自適應拓撲結構建立

成對節點同步需要擴展到全局多跳范圍網絡自適應同步，而如果要實現全網同步，必須建立有效的網絡拓撲結構。下面通過構建一種基于參考節點的局部樹形網絡來實現節點的自適應同步。網絡拓撲結構圖如圖8所示。

圖8 網絡拓撲結構圖Fig.8 Network topology

首先，建立參考節點與主節點同步網絡。當通過三角剖分及染色選擇出每個三角形區域的參考節點后，該參考節點即為該區域的主同步節點，同時為樹形網絡的根節點，將其本地時間作為網絡的參考時間。此時，參考節點進行第1輪消息廣播，該范圍內所有節點通過比較自身鏈路能量、誤包率和時間延遲的權重，計算出歸一量化值，并與預先設定的閾值進行對比，高于預設閾值的節點均可作為該范圍內的主節點。時間延遲、誤包率和自身鏈路能量的計算公式分別為

(13)

PER=1-PERC，

(14)

(15)

其次，建立主節點與從節點同步網絡。在同一參考節點覆蓋的區域內，主節點確定后，其余所有節點均為從節點。當參考節點第2輪廣播消息結束后，從節點與主節點同樣，都會記錄下參考節點的時間戳信息。然后所有主節點均廣播已調整后的本地時間戳信息，從節點感知到信息后，僅會選擇第1個接收到的主節點信息，然后將不再接收其他主節點信息。此時，從節點根據接收到的主節點時間戳信息和參考節點時間戳信息進行時鐘偏移和漂移的估計。

第三，對于網絡邊緣的節點，有時可以接收到多個三角剖分區域的參考節點和主節點消息，此時將這類節點稱為同步輔助節點。該節點同時處在多個參考節點的通信范圍內，可以與參考節點進行雙向通信實現同步。其主要作用是作為參考節點同步的一個補充，能夠進一步協調參考節點間的同步精度。

整個網絡中通過三角剖分劃分區域，并通過染色確定參考節點，參考節點選取主節點，從節點與主節點實現同步。參考節點的時間為基準時間，能否準確地將網絡標準時間同步至全網絡，是至關重要的。該拓撲結構防止了單一節點突發性失效和被干擾等因素，從而影響到整個網絡的同步性能。CTSOA流程如圖9所示。

圖9 CTSOA流程圖Fig.9 CTSOA flow chart

3 仿真結果及分析

在500 m×500 m區域內布置500個自組織協作網絡節點通過仿真計算驗證時間同步算法，具體仿真設置參數如表1所示。為了驗證本文提出的CTSOA有效性，將其與文獻[8]提出的有效單跳時間同步(ESTSP)算法、文獻[12]提出的能量有效參考廣播同步(ERBS)算法、文獻[13]提出的參考廣播同步(RBS)算法進行比較，前提是將4種算法同時置于表1所示仿真環境下進行實驗，并對本文所提三角剖分拓撲結構和傳統分簇拓撲結構下的同步參數進行對比。主要在平均同步誤差、能量消耗兩個方面進行數據處理和分析，而同步包數量和同步收斂時間的分析則可以更好地說明本文算法在精度和能耗方面的優勢。

首先，本文對4類算法的平均同步誤差進行仿真驗證，仿真結果如圖10所示。圖10(a)為采用本文提出的三角剖分拓撲結構仿真得到的平均同步誤差數據結果，可見同步周期越長，同步時間戳數據越精確，同步誤差越小。由于CTSOA采用時鐘漂移和時鐘偏移的聯合估計，相較于其他3種算法，其平均同步誤差最低，小于100 μs. ESTSP算法的平均同步誤差約為200～100 μs之間，ERBS算法的平均同步誤差約為300～200 μs之間，而RBS算法的平均同步誤差最大，大于600 μs. 圖10(b)為采用傳統分簇拓撲結構仿真得到的4類算法平均同步誤差實驗數據，通過與圖10(a)對比可知：其平均同步誤差要比三角剖分拓撲結構時均有所增加；盡管CTSOA效果最好，但是其平均同步誤差仍然在200～100 μs之間。

表1 仿真參數Tab.1 Simulation parameters

圖10 平均同步誤差Fig.10 Average synchronization error

圖11 能量消耗Fig.11 Energy consumption

其次，對4類算法的能量消耗進行仿真驗證，仿真結果如圖11所示。圖11(a)為采用本文提出的三角剖分拓撲結構仿真得到的能量消耗數據結果，可見參考節點數越多，網絡規模越大，能量消耗越高。由于CTSOA采用自適應拓撲控制，相較于其他3種算法，其能量消耗最低，約為200 mW左右。ESTSP算法的能量消耗比CTSOA略高，ERBS算法的能量消耗在400 mW左右，而RBS算法的能量消耗最高，在500～600 mW之間。圖11(b)為采用傳統分簇拓撲結構仿真得到的4類算法能量消耗實驗數據，通過與圖11(a)對比可知：其能量消耗要比三角剖分拓撲結構均有所增加；CTSOA和ESTSP算法效果相差不多，但是它們的能量消耗仍然在500 mW左右。

第三，采用兩種拓撲結構對CTSOA同步包數量進行仿真驗證，仿真結果如圖12所示。由圖12可見，隨著網絡節點數量的增多，在時鐘聯合估計和自適應三角剖分拓撲控制的基礎上，CTSOA的同步包數量明顯少于分簇拓撲結構時的同步包數量，證明了該算法的整體執行對于網絡開銷及系統穩定性均有所提升。

圖12 同步包數量比較Fig.12 Comparison of the number of synchronization packages

最后，采用兩種拓撲結構對CTSOA同步收斂時間進行仿真驗證，仿真結果如圖13所示。由圖13可見，隨著網絡節點數量的增多，在時鐘聯合估計和自適應三角剖分拓撲控制的基礎上，CTSOA的平均收斂時間約為3.28 s，而采用分簇拓撲結構的平均收斂時間約為6.21 s，由此可以看出，本文算法在收斂時間上得到較大幅度提升，具有較好的收斂性。

圖13 收斂時間比較Fig.13 Comparison of convergence times

4 結論

本文在分析無線自組織網絡時間同步算法存在問題的基礎上，提出無線自組織網絡協作時間同步優化算法。該算法主要利用時鐘偏移和時鐘漂移的聯合估計及三角剖分的自適應網絡拓撲控制實現時間同步算法優化。相較于其他算法，該算法平均同步誤差較小，能量消耗較低。同時，將該同步算法應用在本文提出的三角剖分拓撲中，結果表明：相較于分簇算法，在同步包數量和平均收斂時間兩方面都取得了較好效果。雖然仿真實驗證明了CTSOA的有效性，但本文在節點具有移動特性的情況下，相關性能指標優勢并不明顯。后續研究將節點移動性的時間同步技術作為研究重點，研究無線自組織協作網絡的覆蓋定位問題，從根本上提升無線自組織網絡在單兵作戰系統，以及異構無人平臺數據傳輸速率和可靠性等方面的應用效率。