王義君 錢志鴻

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

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

1 引言

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)在數(shù)據(jù)采集、信號傳輸和信息處理等方面優(yōu)勢顯著[1]。在設(shè)計WSN的過程中，需要考慮眾多因素，如硬件條件限制、面向節(jié)點(diǎn)失效時的網(wǎng)絡(luò)容忍度、網(wǎng)絡(luò)延展性、動態(tài)網(wǎng)絡(luò)拓?fù)浼熬W(wǎng)絡(luò)能量消耗等。但對于絕大多數(shù)WSN應(yīng)用而言，保證節(jié)點(diǎn)的時間同步精度是重中之重。高效的WSN時間同步算法一方面有利于增強(qiáng)網(wǎng)絡(luò)延展性、適應(yīng)動態(tài)拓?fù)渥兓徒档腿W(wǎng)能耗，另一方面對于諸如數(shù)據(jù)融合、能量管理、傳輸調(diào)度、定位及目標(biāo)跟蹤等方面應(yīng)用也可提升性能指標(biāo)、保證系統(tǒng)可靠性[2]。

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

本文首先實(shí)現(xiàn)兩節(jié)點(diǎn)成對時間同步，然后在拓?fù)浣Y(jié)構(gòu)確立前提下實(shí)現(xiàn)全網(wǎng)節(jié)點(diǎn)的自適應(yīng)時間同步，并從時間精度、能量消耗和不同拓?fù)湎滤惴ǖ膱?zhí)行效率等方面對同步算法進(jìn)行了驗(yàn)證。其余部分安排如下：第2節(jié)分析了目前WSN時間同步技術(shù)的研究現(xiàn)狀，總結(jié)了目前時間同步技術(shù)存在的問題；第3節(jié)給出了同步算法的具體實(shí)現(xiàn)思想及執(zhí)行過程；為了驗(yàn)證同步機(jī)制的有效性，第4節(jié)建立了仿真實(shí)驗(yàn)環(huán)境，并通過實(shí)驗(yàn)結(jié)果對算法有效性進(jìn)行了分析；第5節(jié)對全文進(jìn)行了總結(jié)。

2 研究現(xiàn)狀

由于網(wǎng)絡(luò)資源相對受限，傳統(tǒng)的網(wǎng)絡(luò)時間同步方法都無法適用于WSN。因此，設(shè)計符合WSN要求的時間同步算法成為研究熱點(diǎn)[4]。WSN時間同步通常分為2類：發(fā)送端-接收端(Sender-Receiver)同步和接收端-接收端(Receiver-Receiver)同步。本文提出的時間同步優(yōu)化算法基于Receiver-Receiver機(jī)制，眾多學(xué)者開展了相關(guān)研究。

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

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

3 AEO時間同步算法

3.1 時鐘同步模型

WSN中網(wǎng)絡(luò)節(jié)點(diǎn)通過多跳方式相互鏈接完成信息傳輸，網(wǎng)絡(luò)時鐘同步模型包括Receiver-Receiver同步通信模型和時間同步模型。

3.1.1 Receiver-Receiver同步通信模型

Receiver-Receiver成對節(jié)點(diǎn)同步典型通信方式如圖1所示。節(jié)點(diǎn)R為參考節(jié)點(diǎn)，負(fù)責(zé)周期性廣播包含同步消息的信標(biāo)包，以滿足接收端節(jié)點(diǎn)的同步需求。節(jié)點(diǎn)A和節(jié)點(diǎn)B是接收端節(jié)點(diǎn)。節(jié)點(diǎn)B為從節(jié)點(diǎn)，接收參考節(jié)點(diǎn)的廣播信標(biāo)包后，向主節(jié)點(diǎn)A通過請求鏈路發(fā)送同步請求，當(dāng)接收到主節(jié)點(diǎn)A返回消息時，完成自身的同步誤差修正，實(shí)現(xiàn)與主節(jié)點(diǎn)的時間同步。節(jié)點(diǎn)A為主節(jié)點(diǎn)，接收節(jié)點(diǎn)R發(fā)送的廣播信標(biāo)包，通過應(yīng)答鏈路向從節(jié)點(diǎn)B返回同步誤差估計量信息。

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

3.1.2 Receiver-Receiver時間同步模型

假設(shè)WSN覆蓋區(qū)域內(nèi)有n個節(jié)點(diǎn)，節(jié)點(diǎn)i的本地時鐘為ti，t為理想?yún)⒖紩r間，時間模型定義為

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

其中，αio和βio分別為節(jié)點(diǎn)o和節(jié)點(diǎn)i間的相對頻率漂移和相對相位偏差。因此，當(dāng)αio= 1，βio= 0時，兩個節(jié)點(diǎn)將完全實(shí)現(xiàn)時間同步。

3.2 雙節(jié)點(diǎn)時間同步

3.2.1 雙節(jié)點(diǎn)時間同步原理

同步機(jī)制設(shè)計目的在于保證同步精度的同時，降低網(wǎng)絡(luò)能耗，因此，本文所設(shè)計的雙節(jié)點(diǎn)時間同步原理包括3個方面：接收端同步消息確認(rèn)及時間修正、交互參數(shù)同步包構(gòu)建和雙節(jié)點(diǎn)同步實(shí)現(xiàn)。

(1) 接收端同步消息確認(rèn)及時間修正。參考節(jié)點(diǎn)周期性廣播同步消息包，將該包稱為參考節(jié)點(diǎn)信標(biāo)包。兩個連續(xù)信標(biāo)包之間的時間間隔為同步信標(biāo)間隔，用Tb表示；假設(shè)一個完整同步周期Tp內(nèi)發(fā)送Nb個信標(biāo)包，則

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

圖2 同步包結(jié)構(gòu)

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

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

其中，a為每個周期對應(yīng)的周期系數(shù)，不同周期輪次a的值按約定發(fā)生變化，其值為整數(shù)；l為預(yù)先設(shè)定值，其值為素數(shù)，l ≥ m。 (b) 將Tcode與Rid做異或運(yùn)算，得到Icode編碼，即Icode= Tcode⊕Rid。帶有Icode的交互參數(shù)同步包生成后，接收節(jié)點(diǎn)間通過握手進(jìn)行同步信息確認(rèn)時，不需要再轉(zhuǎn)發(fā)整個同步消息包，而只轉(zhuǎn)發(fā)交互參數(shù)同步包即可，因?yàn)樵摪屑劝瑢?shí)現(xiàn)同步的具體信息，又比整個同步消息包數(shù)據(jù)量有所降低，可有效節(jié)約網(wǎng)絡(luò)能耗。同時，交互參數(shù)同步包另一個作用在于Icode中包含了參考節(jié)點(diǎn)ID和參考節(jié)點(diǎn)周期號信息，這樣在接收端雙節(jié)點(diǎn)同步時不需要再與參考節(jié)點(diǎn)進(jìn)行消息確認(rèn)，兩節(jié)點(diǎn)間只要通過Icode匹配就可以實(shí)現(xiàn)同步過程。

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

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

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

U為累積經(jīng)驗(yàn)系數(shù)矩陣，ε為滿足擬合數(shù)據(jù)要求的指定閾值。

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

3.3 全網(wǎng)絡(luò)自適應(yīng)時間同步

3.3.1 拓?fù)浣Y(jié)構(gòu)建立

雙節(jié)點(diǎn)同步擴(kuò)展到全局多跳范圍網(wǎng)絡(luò)自適應(yīng)同步，必須建立有效的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。本節(jié)通過構(gòu)建Voronoi多邊形拓?fù)鋵?shí)現(xiàn)全網(wǎng)節(jié)點(diǎn)的覆蓋。

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

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

圖3 空圓特性示意圖

其次，當(dāng)節(jié)點(diǎn)的Delaunay三角剖分結(jié)構(gòu)建立以后，可以通過Delaunay三角剖分圖與Voronoi圖的對偶性構(gòu)建Voronoi多邊形拓?fù)?。具體步驟如下：

步驟1 網(wǎng)絡(luò)節(jié)點(diǎn)自動構(gòu)建Delaunay三角剖分網(wǎng)，對網(wǎng)絡(luò)節(jié)點(diǎn)和形成三角形進(jìn)行編號，并存儲構(gòu)成每個三角形的網(wǎng)絡(luò)節(jié)點(diǎn)編號；

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

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

步驟5 遍歷搜索結(jié)束，根據(jù)邊鏈表畫出WSN的Voronoi多邊形拓?fù)浣Y(jié)構(gòu)。

圖4給出了10 m× 10 m覆蓋范圍內(nèi)布置20個節(jié)點(diǎn)，基于Delaunay三角剖分的WSN網(wǎng)絡(luò)Voronoi多邊形拓?fù)浣Y(jié)構(gòu)。

圖4 Voronoi多邊形拓?fù)浣Y(jié)構(gòu)

其中，藍(lán)色虛線表示節(jié)點(diǎn)間相互連接的Delaunay三角，紅色多邊形即為Voronoi多邊形，表示每個節(jié)點(diǎn)的感知控制區(qū)域。

3.3.2 節(jié)點(diǎn)身份確認(rèn)

WSN中的節(jié)點(diǎn)根據(jù)全網(wǎng)同步需求分為3類：參考節(jié)點(diǎn)、鄰域節(jié)點(diǎn)和接收節(jié)點(diǎn)。Voronoi多邊形拓?fù)浣Y(jié)構(gòu)構(gòu)建完成后，參考節(jié)點(diǎn)除了具有雙節(jié)點(diǎn)同步的功能外，其通信范圍擴(kuò)展到與其相鄰的Voronoi多邊形區(qū)域中所有節(jié)點(diǎn)，實(shí)現(xiàn)擴(kuò)展后大規(guī)模時間同步；鄰域節(jié)點(diǎn)可接收到多個Voronoi多邊形區(qū)域的參考節(jié)點(diǎn)消息，此類節(jié)點(diǎn)同時處在多個參考節(jié)點(diǎn)的通信范圍內(nèi)，主要作用是作為參考節(jié)點(diǎn)時間同步的補(bǔ)充，協(xié)調(diào)參考節(jié)點(diǎn)間的同步精度；接收節(jié)點(diǎn)是不包括參考節(jié)點(diǎn)和鄰域節(jié)點(diǎn)在內(nèi)的網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)，即等待同步節(jié)點(diǎn)。如何在WSN中確認(rèn)參考節(jié)點(diǎn)及鄰域節(jié)點(diǎn)是實(shí)現(xiàn)全網(wǎng)同步的重要環(huán)節(jié)。

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

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

本文將整個網(wǎng)絡(luò)生命周期分為初期、中期和后期3個階段。在初期，可采用式(12)和式(13)所判定的節(jié)點(diǎn)排序確認(rèn)參考節(jié)點(diǎn)。但隨著網(wǎng)絡(luò)應(yīng)用的不斷深入，部分網(wǎng)絡(luò)節(jié)點(diǎn)可能因?yàn)槟芎?、環(huán)境和人為因素等情況，脫離網(wǎng)絡(luò)應(yīng)用場景，進(jìn)而不能有效反映在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，因此，除了考慮S和E外，在網(wǎng)絡(luò)整個生命周期的中、后期，還需評估其他性能指標(biāo)以實(shí)現(xiàn)參考節(jié)點(diǎn)確認(rèn)，具體步驟如下：

步驟1 統(tǒng)計覆蓋區(qū)域內(nèi)每個節(jié)點(diǎn)的鏈路誤包率和時間延遲兩項性能指標(biāo)，分別記為PERl和Td。PERl為該節(jié)點(diǎn)涉及無線通信鏈路中端到端誤包率，Td為該節(jié)點(diǎn)涉及無線通信鏈路中端到端傳輸時延；

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

步驟4 根據(jù)vx(c)值重新確定網(wǎng)絡(luò)生命周期中、后期的參考節(jié)點(diǎn)。

3.3.3 全網(wǎng)同步實(shí)現(xiàn)

全網(wǎng)同步實(shí)現(xiàn)流程如圖6所示，執(zhí)行步驟如下：

圖6 全網(wǎng)同步實(shí)現(xiàn)流程

步驟1 WSN節(jié)點(diǎn)構(gòu)建Voronoi多邊形拓?fù)浣Y(jié)構(gòu)，在拓?fù)鋭澐值臅r候?yàn)槊總€多邊形區(qū)域編號，即確定每個節(jié)點(diǎn)的覆蓋范圍；

步驟2 確定拓?fù)浣Y(jié)構(gòu)中的參考節(jié)點(diǎn)，并將與其相鄰的多邊形中的節(jié)點(diǎn)確認(rèn)為該參考節(jié)點(diǎn)負(fù)責(zé)同步的接收節(jié)點(diǎn)，同時，確認(rèn)該參考節(jié)點(diǎn)同步范圍內(nèi)的鄰域節(jié)點(diǎn)；

圖5 鄰域節(jié)點(diǎn)確認(rèn)

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

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

至此，參考節(jié)點(diǎn)通過式(18)和式(19)更新調(diào)整本地時間偏差，實(shí)現(xiàn)多區(qū)域的聯(lián)合時間同步。

4 仿真結(jié)果及分析

4.1 參數(shù)設(shè)置

仿真區(qū)域分別設(shè)置為100 m×100 m，200 m×200 m，300 m×300 m，400 m×400 m和500 m×500 m，每個區(qū)域的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量分別為100，200，300，400和500，參考節(jié)點(diǎn)的數(shù)量按網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的10%計算，5個區(qū)域選擇參考節(jié)點(diǎn)數(shù)量分別為10， 20， 30， 40和50，具體仿真設(shè)置參數(shù)如表1所示。為了驗(yàn)證本文提出AEO算法有效性，在Voronoi多邊形拓?fù)浣Y(jié)構(gòu)、樹狀(Tree)拓?fù)浣Y(jié)構(gòu)和鏈狀(Chain)拓?fù)浣Y(jié)構(gòu)情況下，將其與基于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]進(jìn)行比較。需要指出的是，接收節(jié)點(diǎn)在接收到參考節(jié)點(diǎn)信標(biāo)包上打上時間戳，記錄信標(biāo)碼、信標(biāo)間隔和同步周期號；數(shù)據(jù)更新每小時執(zhí)行1次，U矩陣在整個仿真時間內(nèi)共更新5次。仿真實(shí)驗(yàn)過程分為2部分：成對節(jié)點(diǎn)同步分析及全網(wǎng)節(jié)點(diǎn)同步分析。

表1 仿真參數(shù)

4.2 結(jié)果分析

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

圖7 平均同步誤差

其次，對7類算法的能量消耗進(jìn)行仿真驗(yàn)證，仿真結(jié)果如圖8所示。AEO算法通過構(gòu)建交互參數(shù)同步包，降低了同步消息傳輸過程中的同步包字節(jié)數(shù)，利用散列函數(shù)周期確認(rèn)碼可以直接在主從節(jié)點(diǎn)間完成相互身份確認(rèn)，不需要與參考節(jié)點(diǎn)進(jìn)行通信，進(jìn)而降低同步過程中的能量消耗。圖8(a)中，隨著信標(biāo)包數(shù)量增加，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算法成對節(jié)點(diǎn)時間同步時其能量消耗最少。

圖8 能量消耗

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

圖9 拓?fù)浣Y(jié)構(gòu)

連通度可作為綜合衡量拓?fù)浣Y(jié)構(gòu)連通效率和收斂時間的性能參數(shù)[9]，設(shè)λi為第i個節(jié)點(diǎn)的連通度，則網(wǎng)絡(luò)連通效率η可定義網(wǎng)絡(luò)中所有節(jié)點(diǎn)連通度的和集與所有節(jié)點(diǎn)連通度的并集的比值

根據(jù)式(20)，3類拓?fù)浣Y(jié)構(gòu)在連通效率和收斂時間方面的性能指標(biāo)如圖10所示。網(wǎng)絡(luò)節(jié)點(diǎn)連接越多，物理鏈接的可能性就越大，網(wǎng)絡(luò)收斂速度越快，收斂時間越短。隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增加，Voronoi拓?fù)涞倪B通效率從86%上升到95%，收斂時間從25 min下降到6 min；Tree拓?fù)涞倪B通效率從75%上升到54%，收斂時間從61 min下降到23 min；Chain拓?fù)溥B通效率從63%上升到75%，收斂時間從76 min下降到51 min。

圖10 拓?fù)浣Y(jié)構(gòu)性能比較

同時，在拓?fù)浞治霾糠?，本文還針對網(wǎng)絡(luò)誤包率增加的情況，對3類拓?fù)浣Y(jié)構(gòu)連通效率的變化進(jìn)行了比較。在包含500個節(jié)點(diǎn)的WSN中，1個周期內(nèi)隨著丟包率的增加，3類拓?fù)浣Y(jié)構(gòu)連通效率實(shí)驗(yàn)結(jié)果如圖11所示。Voronoi拓?fù)湓?0%誤包率時，其連通效率仍可達(dá)到50%，而Tree拓?fù)浼癈hain拓?fù)鋭t分別為34%和19%。因此，與其他2類拓?fù)浣Y(jié)構(gòu)相比，Voronoi拓?fù)渚哂休^好的網(wǎng)絡(luò)穩(wěn)定性。

圖11 誤包率對拓?fù)浣Y(jié)構(gòu)性能影響

從上述分析可知，本文提出全網(wǎng)同步算法的執(zhí)行效率比其他典型算法均有所提升，其原因在于基于Voronoi拓?fù)涞木W(wǎng)絡(luò)構(gòu)建過程并不復(fù)雜，在此結(jié)構(gòu)下的節(jié)點(diǎn)身份確認(rèn)可以自適應(yīng)管理網(wǎng)絡(luò)并有效傳遞同步消息，因此帶來全網(wǎng)同步收斂時間下降及網(wǎng)絡(luò)可靠性提升。

在Voronoi拓?fù)湎?，對全網(wǎng)節(jié)點(diǎn)多跳時間同步精度及能耗做了進(jìn)一步仿真分析，將AEO算法與性能相對較好的E-PTS算法、E-FTSP算法和RA算法進(jìn)行比較。對于同步精度而言，首先，全網(wǎng)同步依賴于雙節(jié)點(diǎn)同步作為其基本構(gòu)成，雙節(jié)點(diǎn)同步誤差的降低為全網(wǎng)節(jié)點(diǎn)同步誤差降低奠定基礎(chǔ)。其次，Voronoi拓?fù)浣⒑?，通過衡量節(jié)點(diǎn)邊數(shù)和剩余能量自適應(yīng)確定參考節(jié)點(diǎn)選擇排序，并利用幾何關(guān)系設(shè)置其鄰域節(jié)點(diǎn)，使得參考節(jié)點(diǎn)網(wǎng)絡(luò)范圍內(nèi)同步誤差的平均值等同于所有成對同步誤差的平均值，相較于其他拓?fù)浣Y(jié)構(gòu)降低了誤差累積概率。圖12給出了Voronoi拓?fù)湎碌钠骄秸`差對比，相較于另外3類算法，隨著網(wǎng)絡(luò)規(guī)模增大，參考節(jié)點(diǎn)數(shù)量增多，AEO算法的平均同步誤差小于100 μs，取得了較好的全網(wǎng)同步精度效果。

圖12 Voronoi拓?fù)湎碌钠骄秸`差

對于能量消耗而言，首先，全網(wǎng)同步能量消耗取決于雙節(jié)點(diǎn)同步能量消耗，雙節(jié)點(diǎn)能量優(yōu)勢也反映在全網(wǎng)同步能量消耗的實(shí)驗(yàn)中。其次，WSN能耗與發(fā)送和接收的數(shù)據(jù)包數(shù)量成正比。從圖9可看出，Voronoi拓?fù)湎噍^于Chain、Tree拓?fù)?，?jié)點(diǎn)間同步所需要的同步消息包發(fā)送與接收的數(shù)量大大降低，從而提升能量利用效率。圖13給出了Voronoi拓?fù)湎碌哪芰肯膶Ρ?，相較于另外3類算法，隨著網(wǎng)絡(luò)規(guī)模增大，參考節(jié)點(diǎn)數(shù)量增多，AEO算法能量消耗在225～340 mW·s，節(jié)能效果顯著。

圖13 Voronoi拓?fù)湎碌哪芰肯?/p>

5 結(jié)束語

本文在接收端-接收端WSN時間同步概念的基礎(chǔ)上，提出自適應(yīng)高效無線傳感器網(wǎng)絡(luò)時間同步優(yōu)化算法。算法主要包括雙節(jié)點(diǎn)時間同步和自適應(yīng)全網(wǎng)絡(luò)節(jié)點(diǎn)時間同步。雙節(jié)點(diǎn)時間同步包括接收端同步消息確認(rèn)及時間修正、交互參數(shù)同步包構(gòu)建和雙節(jié)點(diǎn)同步實(shí)現(xiàn)。自適應(yīng)全網(wǎng)絡(luò)節(jié)點(diǎn)時間同步在拓?fù)浣Y(jié)構(gòu)建立和節(jié)點(diǎn)身份認(rèn)定的基礎(chǔ)上得以實(shí)現(xiàn)。雙節(jié)點(diǎn)同步時通過構(gòu)建交互參數(shù)同步包降低了網(wǎng)絡(luò)能量消耗，采用擬合估計和數(shù)據(jù)更新對每個節(jié)點(diǎn)的頻率漂移及相位偏差進(jìn)行修正，提高了同步精度。在Voronoi拓?fù)浣Y(jié)構(gòu)下，合理選擇參考節(jié)點(diǎn)及鄰域節(jié)點(diǎn)，完成全網(wǎng)節(jié)點(diǎn)的自適應(yīng)時間同步。仿真實(shí)驗(yàn)驗(yàn)證了算法在同步精度和能耗兩方面得以提高。后續(xù)將圍繞不同WSN應(yīng)用場景，將不同協(xié)議應(yīng)用到實(shí)際系統(tǒng)開發(fā)中。