自適應高效無線傳感器網絡時間同步優化算法

王義君 錢志鴻

①(長春理工大學電子信息工程學院 長春 130022)

②(吉林大學通信工程學院 長春 130012)

1 引言

無線傳感器網絡(Wireless Sensor Networks，WSN)在數據采集、信號傳輸和信息處理等方面優勢顯著[1]。在設計WSN的過程中，需要考慮眾多因素，如硬件條件限制、面向節點失效時的網絡容忍度、網絡延展性、動態網絡拓撲及網絡能量消耗等。但對于絕大多數WSN應用而言，保證節點的時間同步精度是重中之重。高效的WSN時間同步算法一方面有利于增強網絡延展性、適應動態拓撲變化和降低全網能耗，另一方面對于諸如數據融合、能量管理、傳輸調度、定位及目標跟蹤等方面應用也可提升性能指標、保證系統可靠性[2]。

由于WSN應用場景特殊，其硬件資源選擇往往處于受限狀態，在設計協議或算法時，除了考慮固有性能指標，需要考慮能量消耗是否滿足網絡通信生命周期要求[3]。因此，同步精度和能量消耗成為設計WSN時間同步算法主要考慮的兩個因素。

本文首先實現兩節點成對時間同步，然后在拓撲結構確立前提下實現全網節點的自適應時間同步，并從時間精度、能量消耗和不同拓撲下算法的執行效率等方面對同步算法進行了驗證。其余部分安排如下：第2節分析了目前WSN時間同步技術的研究現狀，總結了目前時間同步技術存在的問題；第3節給出了同步算法的具體實現思想及執行過程；為了驗證同步機制的有效性，第4節建立了仿真實驗環境，并通過實驗結果對算法有效性進行了分析；第5節對全文進行了總結。

2 研究現狀

由于網絡資源相對受限，傳統的網絡時間同步方法都無法適用于WSN。因此，設計符合WSN要求的時間同步算法成為研究熱點[4]。WSN時間同步通常分為2類：發送端-接收端(Sender-Receiver)同步和接收端-接收端(Receiver-Receiver)同步。本文提出的時間同步優化算法基于Receiver-Receiver機制，眾多學者開展了相關研究。

接收端-接收端時間同步的代表算法為RBS(Receiver Broadcast Synchronization)算法[5]。Kashyap等人[6]提出基于RBS和ACS(Adaptive Clock Synchronization)的聯合時鐘同步(RA)算法。該算法規定單個同步節點1跳范圍內的接收器數量，進而最小化同步整個網絡的能量消耗。同時還考慮如果1個或多個同步節點死亡，如何仍保持網絡覆蓋范圍和連接性。文獻[7]針對WSN中隨著節點數目增多，傳統的參考廣播同步算法網絡開銷非常大的問題，提出一種能量有效的參考廣播同步算法。該算法只對不相鄰的兩個接收節點在多個參考廣播消息的條件下求平均相位偏差，并且對計算得出的相位偏差進行最大后驗估計；采用最小二乘線性回歸方法周期性地擬合時鐘偏移，完成同步過程。文獻[8]提出從連通度和收斂速度方面考慮的時間同步算法。該算法通過采用多跳通信模型，生成多跳節點之間的虛擬通信鏈路，并實現網絡的代數連通度增加。同時，為了平衡收斂時間、精度和通信復雜度，設計了一種多跳控制器，通過延遲補償得到精確的相對時鐘偏移估計。該算法在連通及收斂方面取得了較好效果，但并未對能量消耗方面做實驗論證。文獻[9]提出一種能量高效的自適應參考廣播同步算法，該算法兼顧了能量消耗和精度，但其主要應用場景限定在WSN監測大規模光伏組件情況，具有一定局限性。Receiver-Receiver同步在無需MAC層時間戳介入的情況下表現出較好的同步精度，但這種機制由于其單跳同步精度較高的特點，目前更多考慮的是節點數量較少的小規模網絡覆蓋應用，對于多跳中大規模網絡的同步效果較差。在拓撲控制時，該機制主要選擇基于生成樹(spanning tree)的分簇結構，通信消耗較大，自適應同步能力不強。

通過上述分析，目前WSN同步算法主要存在同步累積誤差及能耗大、MAC層非確定性延遲及硬件局限等問題，進而影響全網同步效率。本文基于Receiver-Receiver同步思想，提出一種自適應高效優化無線傳感器網絡時間同步算法(Adaptive and Efficient time synchronization Optimization algorithm in WSN， AEO)。AEO算法一方面闡明了雙節點時間同步原理，即包括接收端同步消息確認及時間修正、交互參數同步包構建和雙節點同步實現；另一方面在拓撲結構建立和節點身份認定的基礎上，研究了全網絡自適應時間同步過程。

3 AEO時間同步算法

3.1 時鐘同步模型

WSN中網絡節點通過多跳方式相互鏈接完成信息傳輸，網絡時鐘同步模型包括Receiver-Receiver同步通信模型和時間同步模型。

3.1.1 Receiver-Receiver同步通信模型

Receiver-Receiver成對節點同步典型通信方式如圖1所示。節點R為參考節點，負責周期性廣播包含同步消息的信標包，以滿足接收端節點的同步需求。節點A和節點B是接收端節點。節點B為從節點，接收參考節點的廣播信標包后，向主節點A通過請求鏈路發送同步請求，當接收到主節點A返回消息時，完成自身的同步誤差修正，實現與主節點的時間同步。節點A為主節點，接收節點R發送的廣播信標包，通過應答鏈路向從節點B返回同步誤差估計量信息。

圖1 Receiver-Receiver成對同步通信模型

3.1.2 Receiver-Receiver時間同步模型

假設WSN覆蓋區域內有n個節點，節點i的本地時鐘為ti，t為理想參考時間，時間模型定義為

其中，αi為頻率漂移，βi為相位偏差，ε為隨機噪聲。頻率漂移和相位偏差是影響成對節點同步誤差精度的2個重要參數。頻率漂移主要受節點微控制器的晶振影響，相位偏差主要由各類延遲決定。假設網絡中節點o需要與節點i進行同步，則節點o的本地時鐘可表示為

其中，αio和βio分別為節點o和節點i間的相對頻率漂移和相對相位偏差。因此，當αio= 1，βio= 0時，兩個節點將完全實現時間同步。

3.2 雙節點時間同步

3.2.1 雙節點時間同步原理

同步機制設計目的在于保證同步精度的同時，降低網絡能耗，因此，本文所設計的雙節點時間同步原理包括3個方面：接收端同步消息確認及時間修正、交互參數同步包構建和雙節點同步實現。

(1) 接收端同步消息確認及時間修正。參考節點周期性廣播同步消息包，將該包稱為參考節點信標包。兩個連續信標包之間的時間間隔為同步信標間隔，用Tb表示；假設一個完整同步周期Tp內發送Nb個信標包，則

每個信標包中包括參考節點標識(IDentification，ID)、發送時間戳(Sending Timestamp， ST)、信標碼( beacon code)和周期號( period number)。其中，參考節點ID用于雙節點同步的識別與確認；發送時間戳在參考節點的應用層生成，表示時間同步包的生成時間；信標碼記錄每個周期內的信標是否全部被接收節點接收，該記錄決定了一個同步周期是否有效；周期號在每個同步周期的末尾，由參考節點按時間序列遞增。每個接收節點接收到參考節點發送的信標包后，將信息存儲在接收端同步消息包中，將該包稱為接收節點信宿包。每個信宿包中存儲的內容包括接收節點ID、參考節點ID、發送時間戳、信標碼，同步周期輪次。同時，每個信標到達時，接收節點會產生本地接收時間戳(Receiving Timestamp， RT)，該時間戳存儲在大小為Nb的循環存儲緩沖區中。參考節點和接收節點同步包結構如圖2所示。

圖2 同步包結構

在一個完整同步周期結束時，接收節點執行本地頻率漂移和相位偏差估計。首先，對接收到的發送時間戳進行聚類分析，將大范圍偏離的數據去除；其次，在ST和RT之間采用Huber Loss方式對誤差進行估計，計算出與參考節點的偏差，算法具體執行過程在3.2.2節詳細介紹。

(2) 交互參數同步包構建。當接收節點完成與參考節點通信，計算出對于參考節點的相對頻率漂移和相對相位偏差估算量后，開始構建并生成交互參數同步包，由以下字段構成：{Lid， Rid， Foff，Poff， Icode}。Lid為接收節點ID，Rid為參考節點ID，Foff為本地接收節點相對于參考節點的頻率漂移偏差，Poff為本地接收節點相對于參考節點的相位偏差偏差，Icode為交互參數同步碼。Icode的編碼包括2部分：(a) 以參考節點周期號為輸入，通過散列函數形成周期確認碼Tcode。令X = {x0， ···， xi， ··· ，xm–1}為參考節點周期號的集合，則Tcode的編碼方式如式(4)所示

其中，a為每個周期對應的周期系數，不同周期輪次a的值按約定發生變化，其值為整數；l為預先設定值，其值為素數，l ≥ m。 (b) 將Tcode與Rid做異或運算，得到Icode編碼，即Icode= Tcode⊕Rid。帶有Icode的交互參數同步包生成后，接收節點間通過握手進行同步信息確認時，不需要再轉發整個同步消息包，而只轉發交互參數同步包即可，因為該包中既包含實現同步的具體信息，又比整個同步消息包數據量有所降低，可有效節約網絡能耗。同時，交互參數同步包另一個作用在于Icode中包含了參考節點ID和參考節點周期號信息，這樣在接收端雙節點同步時不需要再與參考節點進行消息確認，兩節點間只要通過Icode匹配就可以實現同步過程。

3.2.2 頻率漂移及相位偏差估計

接收端節點收到參考節點發送的信標包，需要對本地時間進行估計，計算出與參考節點的偏差估計量后才能申請與其他節點同步。參考節點在每個周期發送的信標包越多，接收節點所獲得的估計數據也就越多，則每個周期內同步精度就會越高，偏差估計量就會越小。因此，當一個周期內信標包發送結束后，接收節點需要估算出與參考節點的時間偏差估計量。接收節點在一個周期內能夠接收到多少信標包可以由信標碼來確定。在一個有效周期結束后，接收端節點開始對頻率漂移和相位偏差進行估計，包括兩個步驟：擬合估計部分通過Huber Loss方法對時間誤差進行計算，實現數據的瞬時估算。數據更新部分通過算法自適應調整，對歷史數據進行自我聚類訓練，通過不斷學習，使得數據經驗值更加準確，這將使同步精度進一步提升。

(1) 擬合估計。能量有效是WSN需要重要考慮的因素，部分學者在保證同步精度的同時，往往考慮采用單一的最小二乘線性回歸方法估計頻率漂移和相位偏差，但最小二乘法需要將誤差數據進行平方運算，當某個接收數據與真實數據差別過大時，該方法就會犧牲較為理想的數據值[10]。因此，在數據存在異常值時，單一的最小二乘法會帶來較大的擬合誤差。在統計學中，Huber Loss是用于魯棒回歸的損失函數，與平方誤差損失相比，它對數據的異常值敏感程度大大降低[11]。本文采用Huber Loss實現擬合估計。定義誤差范圍變量δ，當接收數據與本地數據的誤差小于δ時，采用最小二乘法擬合估算；當接收數據與本地數據的誤差大于δ時，采用最小絕對值法擬合估算，如式(7)所示，其中x表示接收數據，f(x)表示經驗數據，Fδ(x，f(x))為擬合估計函數值，δ的取值為11.221 μs[12]。

U為累積經驗系數矩陣，ε為滿足擬合數據要求的指定閾值。

式(8)中，U根據累積歷史數據不斷調整自身稀疏結構，在更新過程中使接收端數據更加準確。因此，本文通過調整U使TrU能夠近似達到相對最佳。在實際的計算處理中，一次找到TrU的相對最優值是不可能的，所以該過程是每次僅更新TrU的1列，第k列的更新重構子項如式(10)所示。通過將乘法TrU分解為z個秩為1的矩陣的和，z的最大值為K，假定其他K–1列為固定的，用Wk表示，第k列未知，完成此步驟后，通過奇異值分解達到第k列的最小化分布。

3.3 全網絡自適應時間同步

3.3.1 拓撲結構建立

雙節點同步擴展到全局多跳范圍網絡自適應同步，必須建立有效的網絡拓撲結構。本節通過構建Voronoi多邊形拓撲實現全網節點的覆蓋。

首先，采用Bowyer-Watson算法來構建覆蓋區域內所有節點的Delaunay三角剖分結構[13]。利用該方法構建網絡三角剖分的目的在于：(1) 所有節點滿足空圓特性：Delaunay三角剖分網絡是唯一的(任意4點不能共圓)，即在構建的Delaunay三角剖分網絡中任何一個三角形的外接圓范圍內不會有其它點存在。利用這個特點可保證網絡的唯一性和魯棒性；(2) 最大化最小角特性：在所有節點形成的三角剖分中，在兩個相鄰的三角形構成凸四邊形的對角線，在相互交換后，6個內角的最小角不再增大，該方法所形成的三角形的最小角最大。利用這個特點可保證每個三角形區域不會因角度問題過窄，在硬件設置確定的情況下，可滿足節點間通信能耗相對減少。如何保證空圓特性，是實現Delaunay三角剖分的關鍵，即如何判斷任意三角形的外接圓內不會存在第4個頂點。

對于2維覆蓋區域，空圓特性示意如圖3所示。設節點A， B， C， D的坐標分別為(Ax， Ay)， (Bx，By)， (Cx，Cy)， (Dx， Dy)，A， B， C 3點構成三角形，D點為待判斷節點，可通過式(11)的行列式來判斷D點是否在三角形的外接圓內。當A， B和C按逆時針順序排序時，當且僅當D位于外接圓內時，式(11)所表示的行列式值為正。

圖3 空圓特性示意圖

其次，當節點的Delaunay三角剖分結構建立以后，可以通過Delaunay三角剖分圖與Voronoi圖的對偶性構建Voronoi多邊形拓撲。具體步驟如下：

步驟1 網絡節點自動構建Delaunay三角剖分網，對網絡節點和形成三角形進行編號，并存儲構成每個三角形的網絡節點編號；

步驟2 計算并標記每個三角形外接圓圓心；步驟3 遍歷搜索三角形鏈表，尋找與當前三角形3邊共邊的相鄰的3個三角形；

步驟4 如果找到，則把尋找到的三角形的外心與當前三角形的外心連接，存入Voronoi邊鏈表中；如果找不到，則求出最外邊的中垂線射線存入Voronoi邊鏈表中；

步驟5 遍歷搜索結束，根據邊鏈表畫出WSN的Voronoi多邊形拓撲結構。

圖4給出了10 m× 10 m覆蓋范圍內布置20個節點，基于Delaunay三角剖分的WSN網絡Voronoi多邊形拓撲結構。

圖4 Voronoi多邊形拓撲結構

其中，藍色虛線表示節點間相互連接的Delaunay三角，紅色多邊形即為Voronoi多邊形，表示每個節點的感知控制區域。

3.3.2 節點身份確認

WSN中的節點根據全網同步需求分為3類：參考節點、鄰域節點和接收節點。Voronoi多邊形拓撲結構構建完成后，參考節點除了具有雙節點同步的功能外，其通信范圍擴展到與其相鄰的Voronoi多邊形區域中所有節點，實現擴展后大規模時間同步；鄰域節點可接收到多個Voronoi多邊形區域的參考節點消息，此類節點同時處在多個參考節點的通信范圍內，主要作用是作為參考節點時間同步的補充，協調參考節點間的同步精度；接收節點是不包括參考節點和鄰域節點在內的網絡中所有其他節點，即等待同步節點。如何在WSN中確認參考節點及鄰域節點是實現全網同步的重要環節。

(1) 參考節點確認。2維覆蓋空間中的網絡節點，令S表示其所在Voronoi多邊形的邊數量集合，S集合表示該節點鄰居節點的數量，反映了其空間位置的重要性；令E表示其自身能量集合，反映了其傳輸能力的重要性。設節點z在第c個周期時的S和E分別表示為sz(c)和ez(c)，在每次迭代計算中，根據局部范圍內各個節點在一個周期內不同時間段其自身Voronoi多邊形的邊數量和剩余能量的變化，可以得到該局部范圍內節點的最優值排序

需要說明的是，在式(12)和式(13)中，節點S的優先級比E高。因為Voronoi多邊形的邊數量多證明其鄰居節點多，表示其可以通信的范圍大，此時可以確定該節點剩余能量能夠滿足通信需求。對于能量來講，只要不低于設定閾值即可作為參考節點。

本文將整個網絡生命周期分為初期、中期和后期3個階段。在初期，可采用式(12)和式(13)所判定的節點排序確認參考節點。但隨著網絡應用的不斷深入，部分網絡節點可能因為能耗、環境和人為因素等情況，脫離網絡應用場景，進而不能有效反映在網絡拓撲結構中，因此，除了考慮S和E外，在網絡整個生命周期的中、后期，還需評估其他性能指標以實現參考節點確認，具體步驟如下：

步驟1 統計覆蓋區域內每個節點的鏈路誤包率和時間延遲兩項性能指標，分別記為PERl和Td。PERl為該節點涉及無線通信鏈路中端到端誤包率，Td為該節點涉及無線通信鏈路中端到端傳輸時延；

步驟2 同時考慮S， E， PERl和Td，將參考節點最優值排序公式由式(12)和式(13)修正為式(14)

步驟4 根據vx(c)值重新確定網絡生命周期中、后期的參考節點。

3.3.3 全網同步實現

全網同步實現流程如圖6所示，執行步驟如下：

圖6 全網同步實現流程

步驟1 WSN節點構建Voronoi多邊形拓撲結構，在拓撲劃分的時候為每個多邊形區域編號，即確定每個節點的覆蓋范圍；

步驟2 確定拓撲結構中的參考節點，并將與其相鄰的多邊形中的節點確認為該參考節點負責同步的接收節點，同時，確認該參考節點同步范圍內的鄰域節點；

圖5 鄰域節點確認

步驟3 執行參考節點與主節點同步周期。參考節點進行第1輪消息廣播，該范圍內節點接收到消息后，每個節點統計當前周期以前可保證通信能夠可靠完成的性能指標，包括自身鏈路能量、歷史誤包率和累計時間延遲，通過歸一量處理計算出性能指標歸一化量值，將該值與預先設定的閾值進行比較，高于預設閾值的節點均可作為該范圍內的主節點。然后，確定的主節點給參考節點返回應答消息包，參考節點收到后實現通信范圍內主節點確認。此后，參考節點進行第2輪消息廣播，該消息包中包含參考節點的本地時間戳，所有主節點接收到該消息包后，調整自身時間，與參考節點實現同步。

步驟4 執行從節點與主節點同步周期，在同一參考節點覆蓋的區域內，主節點確定后，其余所有節點均為從節點。當參考節點第2輪廣播消息結束后，從節點與主節點一樣，都會記錄下參考節點的同步信息并完成時間調整，同時按照雙節點同步方式實現與主節點的同步。在1個周期范圍內，從節點僅會選擇第1個接收到的主節點信息，然后將不再接收其他主節點信息。

至此，參考節點通過式(18)和式(19)更新調整本地時間偏差，實現多區域的聯合時間同步。

4 仿真結果及分析

4.1 參數設置

仿真區域分別設置為100 m×100 m，200 m×200 m，300 m×300 m，400 m×400 m和500 m×500 m，每個區域的網絡節點數量分別為100，200，300，400和500，參考節點的數量按網絡節點數量的10%計算，5個區域選擇參考節點數量分別為10， 20， 30， 40和50，具體仿真設置參數如表1所示。為了驗證本文提出AEO算法有效性，在Voronoi多邊形拓撲結構、樹狀(Tree)拓撲結構和鏈狀(Chain)拓撲結構情況下，將其與基于One-way Broadcast同步的FTSP(The Flooding Time Synchronization Protocol)算法[14]和E-FTSP(Enhanced FTSP)算法[15]、基于Two-way Pairwise同步的TPSN(Timing-sync Protocol for Sensor Networks)算法[16]和E-PTS(Enhanced Precision Time Synchronization)算法[17]、基于Receiver-Receiver同步的RBS算法[5]和RA算法[6]進行比較。需要指出的是，接收節點在接收到參考節點信標包上打上時間戳，記錄信標碼、信標間隔和同步周期號；數據更新每小時執行1次，U矩陣在整個仿真時間內共更新5次。仿真實驗過程分為2部分：成對節點同步分析及全網節點同步分析。

表1 仿真參數

4.2 結果分析

(1) 成對節點同步分析。首先，對7類算法的平均同步誤差進行仿真驗證，仿真結果如圖7所示。AEO算法在雙節點同步時一方面采用Huber Loss實現擬合估計，在每個周期結束后修正本地時鐘偏差；另一方面通過歷史數據自主訓練進行數據更新，實現本地時鐘偏差的累積誤差最小。圖7(a)中，隨著信標包數量增加，AEO算法的平均同步誤差在7.5～10 μs，E-PTS算法、E-FTSP算法和RA算法的平均同步誤差在15～25 μs，而FTSP算法、RBS算法和TPSN算法的平均同步誤差在25～35 μs；圖7(b)中，隨著同步周期輪次增加，平均同步誤差明顯降低，5輪同步周期過后，AEO算法的平均同步誤差可達2 μs，E-PTS算法約為8 μs，E-FTSP算法約為10 μs，RA算法約為13.5 μs，而FTSP算法、RBS算法和TPSN算法的平均同步誤差明顯高于提到的算法，維持在20～25 μs。因此，AEO算法成對節點時間同步時具有較好的時間同步精度。

圖7 平均同步誤差

其次，對7類算法的能量消耗進行仿真驗證，仿真結果如圖8所示。AEO算法通過構建交互參數同步包，降低了同步消息傳輸過程中的同步包字節數，利用散列函數周期確認碼可以直接在主從節點間完成相互身份確認，不需要與參考節點進行通信，進而降低同步過程中的能量消耗。圖8(a)中，隨著信標包數量增加，AEO算法的能量消耗在0.5～1 mW·s，E-PTS算法、E-FTSP算法和RA算法的能量消耗在1～2.5 mW·s，而FTSP算法、RBS算法和TPSN算法的能量消耗在5～10 mW·s；圖8(b)中，隨著同步周期輪次增加，能量消耗開始增加，5輪同步周期過后，AEO算法的能量消耗小于5 mW·s，E-PTS算法、E-FTSP算法和RA算法的能量消耗在5～15 mW·s，而FTSP算法、RBS算法和TPSN算法的能量消耗明顯高于提到的算法，維持在50～60 mW·s。因此，AEO算法成對節點時間同步時其能量消耗最少。

圖8 能量消耗

(2) 全網節點同步分析。本文實現全網節點的多跳時間同步依賴于Voronoi拓撲結構，因此，在本部分首先將Voronoi拓撲與另外2類典型拓撲結構，即Tree拓撲及Chain拓撲進行比較，圖9給出了9個節點情況下3類拓撲結構示意圖。如圖所示，如果節點1要實現與節點9的時間同步，在Chain拓撲中，同步消息包需要依次傳遞，需設置節點1為起始節點，如果節點5失效，通信鏈路完全中斷，同步消息傳遞失敗，兩節點不能實現同步，所以這種Chain拓撲實現簡單，但連通度較差；在Tree拓撲結構中，同步消息包需要分簇傳遞，需設置節點1為根節點，如果節點5失效，節點9則處于孤立狀態，在下一輪拓撲結構建立之前，其不能和其他任何節點實現時間同步，所以這種Tree拓撲結構緊密，但重新建立能耗較大，且孤立節點帶來同步誤差；在Voronoi拓撲中，同步消息包平行傳遞，設置節點1和節點6為參考節點，節點5為鄰域節點，其作用僅次于參考節點，如果其失效，節點9仍可以與參考節點6范圍內的節點7或節點8實現同步，在這種最不理想的情況下，可以保證網絡的連通度和同步精度。

圖9 拓撲結構

連通度可作為綜合衡量拓撲結構連通效率和收斂時間的性能參數[9]，設λi為第i個節點的連通度，則網絡連通效率η可定義網絡中所有節點連通度的和集與所有節點連通度的并集的比值

根據式(20)，3類拓撲結構在連通效率和收斂時間方面的性能指標如圖10所示。網絡節點連接越多，物理鏈接的可能性就越大，網絡收斂速度越快，收斂時間越短。隨著網絡節點數量的增加，Voronoi拓撲的連通效率從86%上升到95%，收斂時間從25 min下降到6 min；Tree拓撲的連通效率從75%上升到54%，收斂時間從61 min下降到23 min；Chain拓撲連通效率從63%上升到75%，收斂時間從76 min下降到51 min。

圖10 拓撲結構性能比較

同時，在拓撲分析部分，本文還針對網絡誤包率增加的情況，對3類拓撲結構連通效率的變化進行了比較。在包含500個節點的WSN中，1個周期內隨著丟包率的增加，3類拓撲結構連通效率實驗結果如圖11所示。Voronoi拓撲在50%誤包率時，其連通效率仍可達到50%，而Tree拓撲及Chain拓撲則分別為34%和19%。因此，與其他2類拓撲結構相比，Voronoi拓撲具有較好的網絡穩定性。

圖11 誤包率對拓撲結構性能影響

從上述分析可知，本文提出全網同步算法的執行效率比其他典型算法均有所提升，其原因在于基于Voronoi拓撲的網絡構建過程并不復雜，在此結構下的節點身份確認可以自適應管理網絡并有效傳遞同步消息，因此帶來全網同步收斂時間下降及網絡可靠性提升。

在Voronoi拓撲下，對全網節點多跳時間同步精度及能耗做了進一步仿真分析，將AEO算法與性能相對較好的E-PTS算法、E-FTSP算法和RA算法進行比較。對于同步精度而言，首先，全網同步依賴于雙節點同步作為其基本構成，雙節點同步誤差的降低為全網節點同步誤差降低奠定基礎。其次，Voronoi拓撲建立后，通過衡量節點邊數和剩余能量自適應確定參考節點選擇排序，并利用幾何關系設置其鄰域節點，使得參考節點網絡范圍內同步誤差的平均值等同于所有成對同步誤差的平均值，相較于其他拓撲結構降低了誤差累積概率。圖12給出了Voronoi拓撲下的平均同步誤差對比，相較于另外3類算法，隨著網絡規模增大，參考節點數量增多，AEO算法的平均同步誤差小于100 μs，取得了較好的全網同步精度效果。

圖12 Voronoi拓撲下的平均同步誤差

對于能量消耗而言，首先，全網同步能量消耗取決于雙節點同步能量消耗，雙節點能量優勢也反映在全網同步能量消耗的實驗中。其次，WSN能耗與發送和接收的數據包數量成正比。從圖9可看出，Voronoi拓撲相較于Chain、Tree拓撲，節點間同步所需要的同步消息包發送與接收的數量大大降低，從而提升能量利用效率。圖13給出了Voronoi拓撲下的能量消耗對比，相較于另外3類算法，隨著網絡規模增大，參考節點數量增多，AEO算法能量消耗在225～340 mW·s，節能效果顯著。

圖13 Voronoi拓撲下的能量消耗

5 結束語

本文在接收端-接收端WSN時間同步概念的基礎上，提出自適應高效無線傳感器網絡時間同步優化算法。算法主要包括雙節點時間同步和自適應全網絡節點時間同步。雙節點時間同步包括接收端同步消息確認及時間修正、交互參數同步包構建和雙節點同步實現。自適應全網絡節點時間同步在拓撲結構建立和節點身份認定的基礎上得以實現。雙節點同步時通過構建交互參數同步包降低了網絡能量消耗，采用擬合估計和數據更新對每個節點的頻率漂移及相位偏差進行修正，提高了同步精度。在Voronoi拓撲結構下，合理選擇參考節點及鄰域節點，完成全網節點的自適應時間同步。仿真實驗驗證了算法在同步精度和能耗兩方面得以提高。后續將圍繞不同WSN應用場景，將不同協議應用到實際系統開發中。