黃 曉，羅樹(shù)浩

(中山大學(xué)信息科學(xué)與技術(shù)學(xué)院，廣東 廣州 510006)

在無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)[1]中，節(jié)點(diǎn)搭載各種傳感器，通過(guò)無(wú)線傳輸將監(jiān)測(cè)的數(shù)據(jù)傳輸?shù)絽R聚點(diǎn)(sinks)。無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)具有體積小、低能耗、低成本和自組織等特點(diǎn)，在環(huán)境監(jiān)測(cè)、工業(yè)自動(dòng)化以及人員監(jiān)控管理等領(lǐng)域得到廣泛應(yīng)用[2]。

時(shí)間同步(Time Synchronization)在無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用中有關(guān)鍵的作用[3]。當(dāng)觀測(cè)到事件發(fā)生時(shí)，多個(gè)節(jié)點(diǎn)需要將事件的時(shí)間以及空間信息進(jìn)行數(shù)據(jù)融合(Data Fusioning)，必須維護(hù)一個(gè)與全網(wǎng)一致的時(shí)鐘。另一方面，精確的時(shí)間同步可降低網(wǎng)絡(luò)的能耗，例如在周期性工作的網(wǎng)絡(luò)中，所有節(jié)點(diǎn)在空閑周期同時(shí)關(guān)閉接收機(jī)進(jìn)入休眠狀態(tài)，等待工作周期到來(lái)后喚醒，進(jìn)行數(shù)據(jù)的傳輸。此外，在應(yīng)用信標(biāo)(Beacon)機(jī)制的傳感器網(wǎng)絡(luò)中，以及采用TDMA(Time Division Multiple Access)等協(xié)議避免碰撞，都需要精確的時(shí)間同步。

無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步的首要目標(biāo)是最小化同步誤差。但是由于節(jié)點(diǎn)存在能量、運(yùn)算以及通信能力方面的局限性，時(shí)間同步必須能量高效(Energy Efficient)。實(shí)際上，消息傳輸所需要的能量開(kāi)銷遠(yuǎn)大于運(yùn)算所需開(kāi)銷，所以時(shí)間同步過(guò)程中應(yīng)盡量減少同步消息的傳遞，同時(shí)可保證其他數(shù)據(jù)的有效傳輸。

1 研究現(xiàn)狀

時(shí)間同步問(wèn)題早年在分布式系統(tǒng)已有相關(guān)研究[4]。隨著無(wú)線傳感器網(wǎng)絡(luò)的發(fā)展，針對(duì)其所進(jìn)行的同步研究也有豐富的成果。根據(jù)同步過(guò)程的差異，將現(xiàn)有無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步算法劃分為集中式和分布式兩類。

集中式同步算法，是指在網(wǎng)絡(luò)中存在一個(gè)根節(jié)點(diǎn)(root)，向全網(wǎng)提供一個(gè)標(biāo)準(zhǔn)的時(shí)鐘，并發(fā)起同步流程。RBS(Referenced Broadcast Synchronization)是經(jīng)典的集中式同步算法[5]，通過(guò)同層節(jié)點(diǎn)交換時(shí)間戳的方法抵消發(fā)送時(shí)延，達(dá)到較高同步精度，但難以在多跳網(wǎng)絡(luò)中應(yīng)用。TPSN(Timing-sync Protocol for Sensor Networks)將同步分為兩個(gè)階段[6]，層次發(fā)現(xiàn)階段每個(gè)節(jié)點(diǎn)獲取層次屬性，同步階段每個(gè)節(jié)點(diǎn)都與父節(jié)點(diǎn)進(jìn)行雙向的消息交互從而同步，因此消息開(kāi)銷大。為解決開(kāi)銷問(wèn)題，Kyoung-Lae等[7]提出了成對(duì)廣播同步，一對(duì)節(jié)點(diǎn)雙向交換消息同步，而其共同鄰居能監(jiān)聽(tīng)到這些消息并完成同步。King-Yip等[8]將成對(duì)廣播同步應(yīng)用到多跳網(wǎng)絡(luò)中，采用分布式的方法并結(jié)合貪婪算法動(dòng)態(tài)選擇同步對(duì)，大大減少了同步過(guò)程中消息開(kāi)銷。為提高魯棒性，RTSP(Recursive Time Synchronization Protocol)算法實(shí)現(xiàn)根節(jié)點(diǎn)的動(dòng)態(tài)選舉[9]，通過(guò)下層節(jié)點(diǎn)迭代式向上層請(qǐng)求同步，但延長(zhǎng)了同步過(guò)程從而增加了誤差。

相反地，分布式同步算法不存在根節(jié)點(diǎn)，同步在各個(gè)節(jié)點(diǎn)間異步進(jìn)行，整個(gè)網(wǎng)絡(luò)收斂于虛擬全局時(shí)鐘。螢火蟲(chóng)同步算法結(jié)合了生物現(xiàn)象中的激發(fā)模型[10]，節(jié)點(diǎn)通過(guò)觀測(cè)脈沖信號(hào)以及調(diào)整脈沖信號(hào)發(fā)射間隔，與周圍節(jié)點(diǎn)保持同步。ATS(Average TimeSync)算法用隨機(jī)矩陣方程的角度來(lái)解決同步問(wèn)題[11]，但僅適用于網(wǎng)絡(luò)規(guī)模較小的情況。一致時(shí)鐘同步算法(Consensus Clock Synchronization)使用置信賦權(quán)平均方法對(duì)鄰居時(shí)鐘戳賦權(quán)重從而補(bǔ)償本地時(shí)鐘[12]，算法的收斂速度較快。RGCS(Robust Gradient Clock Synchronization)算法通過(guò)滑動(dòng)平均賦權(quán)的方法[13]，更新本地的時(shí)鐘，算法的魯棒性較好。

分布式算法普遍存在著收斂時(shí)間長(zhǎng)、適用網(wǎng)絡(luò)規(guī)模受限等缺點(diǎn)，集中式算法雖然在應(yīng)對(duì)網(wǎng)絡(luò)動(dòng)態(tài)變化(如根節(jié)點(diǎn)失效)方面稍顯不足，但同步精度高、收斂快速。本文研究了集中式同步算法，在層次發(fā)現(xiàn)階段，采用基于最大互鄰集合的分布式策略獲取精簡(jiǎn)的同步集，降低節(jié)點(diǎn)能耗和網(wǎng)絡(luò)開(kāi)銷。在硬件平臺(tái)和軟件仿真平臺(tái)進(jìn)行的實(shí)驗(yàn)，證明了算法的有效性。

2 單向時(shí)間同步模型

2.1 單向時(shí)間同步和雙向時(shí)間同步

節(jié)點(diǎn)同步時(shí)，由作為主節(jié)點(diǎn)的某個(gè)鄰居提供所需的時(shí)間戳信息。單向同步是相對(duì)于雙向同步而言的，節(jié)點(diǎn)不必進(jìn)行雙向的消息交互，只需接收主節(jié)點(diǎn)的時(shí)間戳即完成同步，消息單向傳播。一般的同步算法(如TSPN)采用雙向同步策略[6]，節(jié)點(diǎn)A發(fā)送同步消息S1給B，而B(niǎo)回復(fù)S2給A，同步消息中攜帶相關(guān)時(shí)間戳，過(guò)程如圖1(a)所示。節(jié)點(diǎn)A獲取四個(gè)時(shí)間戳，通過(guò)(1)式可補(bǔ)償相位偏移Δ，利用線性回歸等方法補(bǔ)償速率漂移。

圖1 雙向同步(a)和單向同步(b)

Δ=[(T2-T1)-(T4-T3)]/2

(1)

文獻(xiàn)[14]提出了一種新的時(shí)間戳標(biāo)記方法，如圖2所示。B生成同步消息并打開(kāi)發(fā)射機(jī)，在發(fā)送幀首定界符SFD完畢的瞬間，硬件系統(tǒng)捕捉硬件時(shí)鐘的值T1并保存在寄存器中，此時(shí)消息其他字段正在傳輸。B立即將T1嵌入消息末端，通過(guò)當(dāng)前消息發(fā)送出去。A在收到消息的SFD時(shí)，也捕捉到本地時(shí)間戳T2，并嵌入到消息的末端，交給上層處理。A由(2)式即可完成相位偏移補(bǔ)償，過(guò)程見(jiàn)圖1(b)。

Δ=T2-T1

(2)

圖2 單向同步原理

這種時(shí)間戳標(biāo)記方法脫離了協(xié)議棧的層次結(jié)構(gòu)，由硬件系統(tǒng)獨(dú)立完成，因此比MAC層標(biāo)記方法的精度更高。單向同步過(guò)程引入了消息在空氣中的傳播時(shí)延d，由此帶來(lái)的誤差可忽略[6]，故認(rèn)為可取得與雙向同步相同的精度。另外，節(jié)點(diǎn)只需廣播單個(gè)時(shí)間戳即可實(shí)現(xiàn)多個(gè)鄰節(jié)點(diǎn)的同步，顯著降低了同步通信開(kāi)銷。

2.2 單向時(shí)間同步數(shù)學(xué)模型

由于單向同步可達(dá)到雙向同步的精度，而且具有降低消息開(kāi)銷、節(jié)省同步節(jié)點(diǎn)能耗的優(yōu)勢(shì)，故本文選擇單向同步作為研究對(duì)象。同時(shí)由于無(wú)線傳感器網(wǎng)絡(luò)的能量資源少，運(yùn)算能力弱，故本文算法的目標(biāo)為降低能量開(kāi)銷，降低算法復(fù)雜度，提高同步成功率。

同步分成兩個(gè)階段。第一階段為層次發(fā)現(xiàn)階段，尋找包括根節(jié)點(diǎn)在內(nèi)的所有廣播節(jié)點(diǎn)組成的同步集，同時(shí)控制同步集節(jié)點(diǎn)數(shù)量以降低同步消息開(kāi)銷。第二階段為同步階段，同步消息自根節(jié)點(diǎn)起經(jīng)同步集節(jié)點(diǎn)向外傳播，其余節(jié)點(diǎn)監(jiān)聽(tīng)，實(shí)現(xiàn)全網(wǎng)同步。本文使用單向同步技術(shù)實(shí)現(xiàn)全網(wǎng)同步，建立尋找最小同步集的數(shù)學(xué)模型。

設(shè)節(jié)點(diǎn)集合為Ψ，其元素?cái)?shù)量為‖Ψ‖=N。對(duì)于任意兩個(gè)節(jié)點(diǎn)?ψi,ψj∈Ψ，定義其連通性cψiψj

(3)

設(shè)同步集為Ω?Ψ，根節(jié)點(diǎn)屬于Ω。Ω中每個(gè)節(jié)點(diǎn)都有一個(gè)層次屬性，表示與根節(jié)點(diǎn)的最短拓?fù)渚嚯x，根節(jié)點(diǎn)的層次規(guī)定為0。對(duì)于任意兩個(gè)節(jié)點(diǎn)?φp,φq∈Ω，定義變量λφpφq表示兩者的層次關(guān)系

(4)

對(duì)于非根節(jié)點(diǎn)的?φq∈Ω，Ω至少存在一個(gè)節(jié)點(diǎn)與其互為鄰居且是其上層節(jié)點(diǎn)，從而同步消息可由根節(jié)點(diǎn)開(kāi)始沿廣播節(jié)點(diǎn)向外傳播

?φq∈Ω,φq≠0,p≠q

(5)

為確保網(wǎng)絡(luò)中所有節(jié)點(diǎn)可監(jiān)聽(tīng)到同步消息，須保證每個(gè)節(jié)點(diǎn)至少與一個(gè)廣播節(jié)點(diǎn)互為鄰居，即

?ψi∈Ψ,ψi≠φp

(6)

目標(biāo)是求取符合上述條件的具有最小元素?cái)?shù)量的同步集Ω

argminΩ‖Ω‖

(7)

將網(wǎng)絡(luò)看作一個(gè)無(wú)向連通圖，尋找最小同步集的問(wèn)題等價(jià)于構(gòu)造一個(gè)以根節(jié)點(diǎn)為樹(shù)根的非葉子節(jié)點(diǎn)最少的生成樹(shù)，即最多葉子生成樹(shù)(MLST, Maximum Leaf Spanning Tree)[15]，是一個(gè)NP-HARD問(wèn)題，可利用集中式優(yōu)化算法求解。集中式算法通過(guò)節(jié)點(diǎn)把拓?fù)溥B接信息傳輸?shù)絽R聚節(jié)點(diǎn)，求取最優(yōu)解，再將結(jié)果分發(fā)給每個(gè)節(jié)點(diǎn)。這種方法對(duì)網(wǎng)絡(luò)鏈路造成較大負(fù)荷，當(dāng)傳輸過(guò)程發(fā)生消息丟失時(shí)會(huì)造成結(jié)果錯(cuò)誤。本文研究了更具實(shí)用意義的分布式算法，節(jié)點(diǎn)通過(guò)有限數(shù)量的消息交互，判斷自身是否廣播節(jié)點(diǎn)。

3 基于最大互鄰集合的單向同步

可相互傳輸消息的兩個(gè)節(jié)點(diǎn)之間存在無(wú)線通信鏈路，而距離對(duì)鏈路通信質(zhì)量存在影響。節(jié)點(diǎn)接收消息時(shí)，采樣到對(duì)應(yīng)無(wú)線鏈路的LQI(Link Quality Indicator)參數(shù)，例如ZigBee采用接收信號(hào)強(qiáng)度指示值(Receive Signal Strength Indicator, RSSI)作為L(zhǎng)QI。在理想情況下，當(dāng)兩個(gè)節(jié)點(diǎn)之間沒(méi)有障礙物時(shí)，LQI值隨距離的增大而減?。划?dāng)障礙物存在時(shí)，以節(jié)點(diǎn)為中心向障礙物延伸的方向上，LQI值雖呈規(guī)律性變化，但距離越遠(yuǎn)LQI值越小的趨勢(shì)依然成立。因此，在實(shí)際環(huán)境中節(jié)點(diǎn)可通過(guò)消息的LQI值來(lái)獲知鄰居節(jié)的大概空間信息。

單向同步算法分為兩個(gè)階段，本文主要詳述層次發(fā)現(xiàn)階段，流程如圖3所示。

圖3 單向同步算法流程圖

Step 1 根節(jié)點(diǎn)啟動(dòng)同步流程，廣播一跳層次發(fā)現(xiàn)幀P_DISCOVERY。在層次發(fā)現(xiàn)過(guò)程中的所有控制和數(shù)據(jù)幀都包括以下幾個(gè)公共域：

MsgTpyeSeqSourceIDSourceLevel

其中，MsgTpye為幀類型；Seq為層次發(fā)現(xiàn)幀序列號(hào)，根節(jié)點(diǎn)可增大Seq發(fā)起新一輪層次發(fā)現(xiàn)；SourceID為源節(jié)點(diǎn)的ID號(hào)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有唯一的ID，根節(jié)點(diǎn)為0；SourceLevel是源節(jié)點(diǎn)的層次，根節(jié)點(diǎn)為0，子節(jié)點(diǎn)的層次為父節(jié)點(diǎn)加1。此外，節(jié)點(diǎn)保存一個(gè)狀態(tài)參數(shù)來(lái)指示工作狀態(tài)，初始時(shí)為S_INIT。

根節(jié)點(diǎn)置狀態(tài)為S_FINISH，表示層次發(fā)現(xiàn)階段結(jié)束。

Step 2 節(jié)點(diǎn)接收到i-1層節(jié)點(diǎn)的P_DISCOVERY幀，若狀態(tài)為S_INIT則接收該幀。節(jié)點(diǎn)收到多個(gè)幀時(shí)，選擇最小的ID作為父節(jié)點(diǎn)并記錄其ID，并把自身的層次修改為i。節(jié)點(diǎn)根據(jù)幀的LQI值判斷：

1)LQI>閾值L1，表明節(jié)點(diǎn)離其父節(jié)點(diǎn)較接近，則置狀態(tài)為S_FINISH，完成層次發(fā)現(xiàn)并退出；

2)LQI<=L1，表明節(jié)點(diǎn)處于父節(jié)點(diǎn)廣播范圍的邊緣處，則置節(jié)點(diǎn)狀態(tài)為S_EXCH_NEIGHBOR，成為第i層候選廣播節(jié)點(diǎn)，廣播P_EXCH_NEIGHBOR幀，幀中攜帶一跳鄰居信息。節(jié)點(diǎn)的鄰居信息在網(wǎng)絡(luò)層周期性的鄰居掃描可獲取，不需要額外的同步消息開(kāi)銷。

候選廣播節(jié)點(diǎn)同時(shí)接收同層鄰居節(jié)點(diǎn)的P_EXCH_NEIGHBOR幀，等待一段時(shí)間確保接收完畢。通過(guò)準(zhǔn)確的時(shí)序控制，可確保同一層次的所有節(jié)點(diǎn)在同一時(shí)間段內(nèi)進(jìn)行同步。候選廣播節(jié)點(diǎn)保存同層鄰居集合Ns的鄰居表及LQI值。

Step 3 第i層候選廣播節(jié)點(diǎn)在同層鄰居集合Ns中計(jì)算其最大互鄰集合Gmax和最近鄰集合Imax。

定義節(jié)點(diǎn)互鄰集合G，G中任意節(jié)點(diǎn)np和nq互為鄰居；則節(jié)點(diǎn)的最大互鄰集合Gmax為其所在K個(gè)互鄰集合中元素?cái)?shù)量最多的一個(gè)，即

Gmax=argminGk‖Gk‖,1≤k≤K

(8)

定義節(jié)點(diǎn)最近鄰集合Imax，表示同層鄰居集合Ns中LQI值大于閾值L2的所有節(jié)點(diǎn)的集合，即

(9)

Gmax和Imax由候選廣播節(jié)點(diǎn)遍歷搜索Ns的鄰居表獲得。為降低搜索過(guò)程的運(yùn)算量，可將Ns按其ID號(hào)的大小排序后存儲(chǔ)。對(duì)排序后的Ns搜索Gmax，運(yùn)算復(fù)雜度為O(nlogn)，其中n為Ns的元素?cái)?shù)量且值較小，故運(yùn)算可在資源受限的傳感器節(jié)點(diǎn)上進(jìn)行。獲取Imax只需搜索Ns的LQI值即可，運(yùn)算復(fù)雜度為O(n)。另外初始化計(jì)數(shù)值CG=0和CI=0。

Step 4 候選廣播節(jié)點(diǎn)退避等待隨機(jī)時(shí)間trand，節(jié)點(diǎn)狀態(tài)修改為S_BACKOFF，在此期間接收Ns中節(jié)點(diǎn)發(fā)送的P_ABANDON幀。這些鄰居節(jié)點(diǎn)稱作放棄節(jié)點(diǎn)，說(shuō)明該節(jié)點(diǎn)放棄成為廣播節(jié)點(diǎn)，在同步階段只作監(jiān)聽(tīng)，不發(fā)送同步消息。候選廣播節(jié)點(diǎn)將放棄節(jié)點(diǎn)ID寫(xiě)入集合Sabandon，并判斷：

1) 若放棄節(jié)點(diǎn)nA∈Gmax，則使計(jì)數(shù)值CG=CG+1，即更新記錄最大互鄰集合中放棄節(jié)點(diǎn)的數(shù)量；

2) 若放棄節(jié)點(diǎn)nA∈Imax，則使計(jì)數(shù)值CI=CI+1，更新記錄最近鄰集合中放棄節(jié)點(diǎn)的數(shù)量。

Step 5 候選廣播節(jié)點(diǎn)隨機(jī)等待時(shí)間trand到達(dá)，分析是否成為廣播節(jié)點(diǎn)。

在最大互鄰集合Gmax中，任意節(jié)點(diǎn)廣播消息集合內(nèi)其余節(jié)點(diǎn)都能監(jiān)聽(tīng)到，因此Gmax中的所有節(jié)點(diǎn)處于一個(gè)相對(duì)較小的空間范圍內(nèi)。若Gmax中均為廣播節(jié)點(diǎn)，則同步時(shí)廣播的同步消息覆蓋范圍有較大面積的重疊，造成不必要的能量和網(wǎng)絡(luò)開(kāi)銷。實(shí)際上，只需在Gmax中選取部分廣播節(jié)點(diǎn)，并使其分布合理，那么同步覆蓋范圍約等于Gmax中所有節(jié)點(diǎn)的同步覆蓋范圍。

候選廣播節(jié)點(diǎn)作以下判斷：

1)在trand內(nèi)收到Gmax中所計(jì)數(shù)的放棄節(jié)點(diǎn)數(shù)量為CG，若CG<‖Gmax‖-B1，在Gmax中搜索，若存在未放棄的節(jié)點(diǎn)，且該節(jié)點(diǎn)為最近鄰集合Imax中節(jié)點(diǎn)，即：

(Gmax-Sabandon)∩Imax≠φ

(10)

則放棄成為廣播節(jié)點(diǎn)，廣播P_ABANDON幀通知鄰居節(jié)點(diǎn)；若上述條件不滿足，則進(jìn)入2)。

2)在trand內(nèi)收到Imax中放棄節(jié)點(diǎn)數(shù)量為CI，若CI<‖Imax‖-B2，即Imax中存在過(guò)多候選節(jié)點(diǎn)，則放棄成為廣播節(jié)點(diǎn)，同樣廣播P_ABANDON幀；否則，進(jìn)入3)。這個(gè)條件保證了Imax中保留不多于B2個(gè)同步節(jié)點(diǎn)，因?yàn)榧蟽?nèi)的節(jié)點(diǎn)進(jìn)行同步廣播所覆蓋的有效面積會(huì)有大部分重疊，這是不必要的。

3)若CG<‖Gmax‖-B3，說(shuō)明Gmax中潛在的廣播節(jié)點(diǎn)數(shù)量超過(guò)最大值B3，強(qiáng)制放棄成為廣播節(jié)點(diǎn)，廣播P_ABANDON幀。否則，成為同步集中的廣播節(jié)點(diǎn)。為了控制同層節(jié)點(diǎn)在同一時(shí)間段內(nèi)進(jìn)行層次發(fā)現(xiàn)，保證算法流程準(zhǔn)確，加入一個(gè)時(shí)序控制策略。廣播節(jié)點(diǎn)在此前退避了隨機(jī)的周期trand監(jiān)聽(tīng)同層鄰居節(jié)點(diǎn)的P_ABANDON幀，變量trand由其本地保存；同時(shí)節(jié)點(diǎn)希望與同層的廣播節(jié)點(diǎn)在盡量接近的時(shí)刻廣播P_DISCOVERY幀告知下層節(jié)點(diǎn)。因此，設(shè)定每層的層次發(fā)現(xiàn)過(guò)程的執(zhí)行周期為T(mén)，則廣播節(jié)點(diǎn)在分析完畢后應(yīng)該等待時(shí)間(T-trand)后，再?gòu)V播P_DISCOVERY幀，進(jìn)入Step 6。

同層候選廣播節(jié)點(diǎn)鄰居收到P_ABANDON幀，按Step 4處理。上述的B1,B2,B3為可變參數(shù)，根據(jù)實(shí)際網(wǎng)絡(luò)情況調(diào)整其值大小使同步達(dá)到最佳狀況。

Step 6 第i層候選廣播節(jié)點(diǎn)廣播P_DISCOVERY幀，置狀態(tài)為S_WAIT_REGISTER，此時(shí)并未最終成為廣播節(jié)點(diǎn)。節(jié)點(diǎn)開(kāi)啟定時(shí)器，在設(shè)定時(shí)間內(nèi)等待子節(jié)點(diǎn)注冊(cè)。狀態(tài)若為S_INIT的鄰居節(jié)點(diǎn)可能收到多個(gè)P_DISCOVERY幀，選擇ID最小的父節(jié)點(diǎn)，進(jìn)入層次發(fā)現(xiàn)流程Step 2，并立即單播一個(gè)注冊(cè)幀P_REGISTER給父節(jié)點(diǎn)。當(dāng)父節(jié)點(diǎn)收到了該幀，正式成為廣播節(jié)點(diǎn)。這個(gè)策略防止了子節(jié)點(diǎn)有多個(gè)潛在的父節(jié)點(diǎn)時(shí)，造成某些廣播節(jié)點(diǎn)“懸空”，即實(shí)際上沒(méi)有子節(jié)點(diǎn)的情況。

另外，第i層放棄節(jié)點(diǎn)A廣播P_ABANDON幀，狀態(tài)為S_INIT的鄰居B收到后，將A的ID存儲(chǔ)起來(lái)，并開(kāi)啟定時(shí)器等待tabandon時(shí)間。若在此期間，B沒(méi)有收到任何的P_DISCOVERY幀，說(shuō)明了自身在層次發(fā)現(xiàn)階段被遺漏了。此時(shí)B發(fā)送P_INFORM幀告知該放棄節(jié)點(diǎn)A，A重新成為廣播節(jié)點(diǎn)，發(fā)送P_DISCOVERY幀。

在實(shí)際場(chǎng)景中，網(wǎng)絡(luò)邊緣可能存在少量的節(jié)點(diǎn)，其僅有的鄰居在Step 2的LQI閾值判斷時(shí)放棄成為廣播節(jié)點(diǎn)，導(dǎo)致這些節(jié)點(diǎn)被遺漏從而同步失敗。這種極端的情況，可應(yīng)用簡(jiǎn)單的策略解決。具體在同步階段，被遺漏節(jié)點(diǎn)經(jīng)過(guò)長(zhǎng)時(shí)間沒(méi)有監(jiān)聽(tīng)到同步消息，確認(rèn)同步失敗，向鄰居節(jié)點(diǎn)提出同步請(qǐng)求，等待其回復(fù)同步消息即可。

4 實(shí)驗(yàn)與仿真

4.1 單雙向同步對(duì)比

為驗(yàn)證單向同步策略的同步精度，本文進(jìn)行了相關(guān)的實(shí)驗(yàn)，并與雙向同步技術(shù)對(duì)比。實(shí)驗(yàn)在CC2530為核心的ZigBee平臺(tái)上進(jìn)行，協(xié)議棧為T(mén)I的Z-Stack2.5，利用兩個(gè)節(jié)點(diǎn)進(jìn)行單跳的時(shí)間同步。單雙向同步各進(jìn)行8次實(shí)驗(yàn)，并使用雙蹤示波器測(cè)量同步誤差，結(jié)果見(jiàn)表1。硬件實(shí)驗(yàn)數(shù)據(jù)表明，單向同步的平均同步誤差約為12.5 μs，雙向同步約為11 μs。由此可知利用時(shí)間戳捕捉技術(shù)進(jìn)行單向同步，可達(dá)到與雙向同步一致的精度，而結(jié)果的差異來(lái)源于同步時(shí)引入的系統(tǒng)隨機(jī)誤差，并非同步方法所導(dǎo)致。

表1 單向與雙向同步誤差對(duì)比

4.2 大規(guī)模網(wǎng)絡(luò)實(shí)驗(yàn)

在單向同步的基礎(chǔ)上，本文提出了基于最大互鄰集合的同步算法。為驗(yàn)證算法的有效性，在NS2(Network Simulator 2)軟件平臺(tái)上進(jìn)行大規(guī)模網(wǎng)絡(luò)下的仿真，同時(shí)使用文獻(xiàn)[8]中的算法進(jìn)行對(duì)比。文獻(xiàn)[8]提出了基于雙向同步的成對(duì)廣播時(shí)間同步算法，控制同步消息開(kāi)銷，與本文算法目標(biāo)一致，新穎且具權(quán)威性。本文實(shí)驗(yàn)中，參數(shù)取值分別為B1=1,B2=2,B3=3，實(shí)驗(yàn)結(jié)果見(jiàn)圖4至圖7。

圖4 網(wǎng)絡(luò)規(guī)模100～400，同步集節(jié)點(diǎn)數(shù)量和同步消息開(kāi)銷

圖5 網(wǎng)絡(luò)規(guī)模250，同步集節(jié)點(diǎn)數(shù)量和同步消息開(kāi)銷

圖6 網(wǎng)絡(luò)規(guī)模250，執(zhí)行算法的消息開(kāi)銷

圖7 網(wǎng)絡(luò)規(guī)模250，成功同步節(jié)點(diǎn)比例

圖4是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)從100至400范圍變化的實(shí)驗(yàn)結(jié)果，平均節(jié)點(diǎn)鄰居數(shù)大約保持在10個(gè)，即節(jié)點(diǎn)密度不變。在不同網(wǎng)絡(luò)規(guī)模下，本文的算法得到的廣播節(jié)點(diǎn)的數(shù)量均比文獻(xiàn)中算法結(jié)果少。在同步階段，本文算法的廣播節(jié)點(diǎn)只需發(fā)送一個(gè)同步消息，同步消息數(shù)量與廣播節(jié)點(diǎn)數(shù)量一致；而成對(duì)同步需要消息交換，因此消息開(kāi)銷是同步集節(jié)點(diǎn)數(shù)量的兩倍。本文算法在同步階段平均消息開(kāi)銷比單向同步算法低61.43%，在降低能耗方面更有效。

圖5中是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)固定為250個(gè)、節(jié)點(diǎn)密度變化時(shí)的實(shí)驗(yàn)結(jié)果。本文算法的廣播節(jié)點(diǎn)數(shù)比文獻(xiàn)中方法同步集節(jié)點(diǎn)數(shù)量平均少20.74%，消息開(kāi)銷節(jié)約60.37%。與網(wǎng)絡(luò)規(guī)模變化時(shí)相似，在不同網(wǎng)絡(luò)密度下本文的方法在節(jié)省網(wǎng)絡(luò)開(kāi)銷和節(jié)點(diǎn)能耗方面更優(yōu)秀。

圖6是節(jié)點(diǎn)密度變化時(shí)，在層次發(fā)現(xiàn)階段算法執(zhí)行所需要傳遞的消息數(shù)量對(duì)比情況。表明本文方法所產(chǎn)生的平均消息開(kāi)銷為文獻(xiàn)中算法的46.8%，遠(yuǎn)小于后者。文獻(xiàn)中算法在層次發(fā)現(xiàn)流程中，節(jié)點(diǎn)選擇下層同步子節(jié)點(diǎn)需要多次的消息交互，而本文算法中節(jié)點(diǎn)只需固定數(shù)量的消息開(kāi)銷。

圖7是節(jié)點(diǎn)密度變化時(shí)成功同步節(jié)點(diǎn)數(shù)量占網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的比例。由于消息碰撞等原因，消息傳遞時(shí)可能會(huì)丟失少量幀，節(jié)點(diǎn)獲取鄰居信息不準(zhǔn)確，從而造成少量節(jié)點(diǎn)被遺漏的情況。由于在本文中加入了遺漏節(jié)點(diǎn)處理、時(shí)序控制、放棄節(jié)點(diǎn)重新同步等策略，故同步算法更有效，成功同步節(jié)點(diǎn)的比例為99.07%，額文獻(xiàn)中方法缺乏相關(guān)處理，比例為96.76%。

在運(yùn)算時(shí)間復(fù)雜度方面，本文算法在搜索最大互鄰集合時(shí)的運(yùn)算復(fù)雜度為O(nlogn)，同層鄰居獲取最近鄰集合為O(n)，n為節(jié)點(diǎn)的平均同層鄰居數(shù)，而其余的步驟均為O(1)。在文獻(xiàn)中的算法中，獲取并排序所有低層鄰節(jié)點(diǎn)的鄰居表過(guò)程的復(fù)雜度為O(mlogm)，其后搜索最大共同鄰居集合和sync_num則為O(n2)，篩選最大的sync_num為O(m)，且需多次迭代，最后根據(jù)not_MAX消息作出的處理的復(fù)雜度為O(n*m)或O(1)，其中m和n分別為同層和上層鄰居數(shù)。對(duì)比可知，本文算法的運(yùn)算復(fù)雜度更低，流程更簡(jiǎn)單。

5 結(jié) 語(yǔ)

本文對(duì)無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步問(wèn)題進(jìn)行了研究。利用單向同步的時(shí)間戳標(biāo)記技術(shù)，將時(shí)間同步轉(zhuǎn)化為構(gòu)造最小同步集問(wèn)題，并建立數(shù)學(xué)模型，提出分布式的算法求解。算法通過(guò)在層次發(fā)現(xiàn)階段節(jié)點(diǎn)生成最大互鄰集合和最近鄰集合，減少同步集節(jié)點(diǎn)數(shù)量。加入子節(jié)點(diǎn)向父節(jié)點(diǎn)注冊(cè)、層節(jié)點(diǎn)監(jiān)聽(tīng)放棄幀以及時(shí)序控制等策略提高了算法性能。ZigBee硬件平臺(tái)的實(shí)驗(yàn)證明了單向同步可達(dá)到較高精度；NS2平臺(tái)的仿真表明本文方法在不同網(wǎng)絡(luò)規(guī)模、不同網(wǎng)絡(luò)密度下可降低同步消息開(kāi)銷，提高成功同步節(jié)點(diǎn)比例，能更有效地解決時(shí)間同步問(wèn)題。

參考文獻(xiàn)：

[1]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 393-422.

[2]ARAMPATZIS T H, LYGEROS J. A survey of applications of wireless sensors and wireless sensor networks [C]∥ Proceedings of the 13th Mediterranean Conference on Control and Automation, Limassol, 2005: 719-724

[3]SOMMER P, WATTENHOFER R. Gradient clock synchronization in wireless sensor networks[C]∥ Information Processing in Sensor Networks, San Francisco, 2009: 37-48.

[4]LISKOV B. Practical uses of synchronized clocks in distributed systems[J]. Distributed Computing, 1993, 6(4): 1-9.

[5]ELSON J, GIROD L, ESTRIN D. Fine-grained network time synchronization using reference broadcasts[C]. Proceedings of the 5th Symposium on Operating Systems Design and Implementation, New York, 2002, 36: 147-163.

[6]GANERIWAL S, KUMAR R, SRIVASTAVA M B. Timing-sync protocol for sensor networks[C]∥1st International Conference on Embedded Networked Sensor Systems, New York, 2003: 138-149.

[7]KYOUNG-LAE N, ERCHIN S, KHALID Q. A new approach for time synchronization in wireless sensor networks: pairwise nroadcast synchronization[J]. IEEE Transactions on Wireless Communications, 2008, 7(9): 3318-3322.

[8]KING-YIP C, KING-SHAN L, YIK-CHUNG W, et al. A distributed multihop time synchronization protocol for wireless sensor networks using pairwise broadcast synchronization[J]. IEEE Transactions on Wireless Communications, 2009,8(4): 1764-1772.

[9]MUHAMMAD A, TAREK R S. RTSP: an accurate and energy-efficient protocol for clock synchronization in WSNs[J].IEEE Transactions on Instrumentation and Measurement, 2013, 62(3): 578-589.

[10]GEOFFREY Werner-Allen, GEETIKA Tewari, ANKIT Patel, et al. Firefly-inspired sensor network synchronicity with realistic radio effects[C]∥ Proceedings of the 3rd International Conference on Embedded Networked Sensor Ssystems, New York, 2005: 142-153.

[11]LUCA Schenato, GIOVANNI Gamba. A distributed consensus protocol for clock synchronization in wireless sensor network[C]∥ Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, 2007: 2289-2294.

[12]MAGGS M K, O’KEEFE S G , THIEL D V. Consensus clock synchronization for wireless sensor networks[J]. IEEE Sensors Journal, 2012, 12(6): 2269-2277.

[13]PINHO A C, FIGUEIREDO D R , FRANCA F M G. A robust gradient clock synchronization algorithm for wireless sensor networks[C]∥ Communication Systems and Networks (COMSNETS), 4th International Conference on, Bangalore, 2012: 1-10.

[14]COX D, JOVANOV E, MILENKOVIC A. Time synchronization for ZigBee networks[C]∥Proceedings of the 37th Annual Southeastern Symposium on System Theory (SSST ’05), 2005:135-138.

[15]BONSMA S PAUL , TOBIAS B, GERHARD J. A faster FPT algorithm for finding spanning trees with many leaves[C]∥Mathematical Foundations of Computer Science, 28th International Symposium, Bratislava, 2003: 259-268.