基于最大互鄰集合的無線傳感器網絡單向時間同步*

黃 曉，羅樹浩

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

在無線傳感器網絡(Wireless Sensor Networks, WSNs)[1]中，節點搭載各種傳感器，通過無線傳輸將監測的數據傳輸到匯聚點(sinks)。無線傳感器網絡的節點具有體積小、低能耗、低成本和自組織等特點，在環境監測、工業自動化以及人員監控管理等領域得到廣泛應用[2]。

時間同步(Time Synchronization)在無線傳感器網絡的應用中有關鍵的作用[3]。當觀測到事件發生時，多個節點需要將事件的時間以及空間信息進行數據融合(Data Fusioning)，必須維護一個與全網一致的時鐘。另一方面，精確的時間同步可降低網絡的能耗，例如在周期性工作的網絡中，所有節點在空閑周期同時關閉接收機進入休眠狀態，等待工作周期到來后喚醒，進行數據的傳輸。此外，在應用信標(Beacon)機制的傳感器網絡中，以及采用TDMA(Time Division Multiple Access)等協議避免碰撞，都需要精確的時間同步。

無線傳感器網絡時間同步的首要目標是最小化同步誤差。但是由于節點存在能量、運算以及通信能力方面的局限性，時間同步必須能量高效(Energy Efficient)。實際上，消息傳輸所需要的能量開銷遠大于運算所需開銷，所以時間同步過程中應盡量減少同步消息的傳遞，同時可保證其他數據的有效傳輸。

1 研究現狀

時間同步問題早年在分布式系統已有相關研究[4]。隨著無線傳感器網絡的發展，針對其所進行的同步研究也有豐富的成果。根據同步過程的差異，將現有無線傳感器網絡時間同步算法劃分為集中式和分布式兩類。

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

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

分布式算法普遍存在著收斂時間長、適用網絡規模受限等缺點，集中式算法雖然在應對網絡動態變化(如根節點失效)方面稍顯不足，但同步精度高、收斂快速。本文研究了集中式同步算法，在層次發現階段，采用基于最大互鄰集合的分布式策略獲取精簡的同步集，降低節點能耗和網絡開銷。在硬件平臺和軟件仿真平臺進行的實驗，證明了算法的有效性。

2 單向時間同步模型

2.1 單向時間同步和雙向時間同步

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

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

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

(1)

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

Δ=T2-T1

(2)

圖2 單向同步原理

這種時間戳標記方法脫離了協議棧的層次結構，由硬件系統獨立完成，因此比MAC層標記方法的精度更高。單向同步過程引入了消息在空氣中的傳播時延d，由此帶來的誤差可忽略[6]，故認為可取得與雙向同步相同的精度。另外，節點只需廣播單個時間戳即可實現多個鄰節點的同步，顯著降低了同步通信開銷。

2.2 單向時間同步數學模型

由于單向同步可達到雙向同步的精度，而且具有降低消息開銷、節省同步節點能耗的優勢，故本文選擇單向同步作為研究對象。同時由于無線傳感器網絡的能量資源少，運算能力弱，故本文算法的目標為降低能量開銷，降低算法復雜度，提高同步成功率。

同步分成兩個階段。第一階段為層次發現階段，尋找包括根節點在內的所有廣播節點組成的同步集，同時控制同步集節點數量以降低同步消息開銷。第二階段為同步階段，同步消息自根節點起經同步集節點向外傳播，其余節點監聽，實現全網同步。本文使用單向同步技術實現全網同步，建立尋找最小同步集的數學模型。

設節點集合為Ψ，其元素數量為‖Ψ‖=N。對于任意兩個節點?ψi,ψj∈Ψ，定義其連通性cψiψj

(3)

設同步集為Ω?Ψ，根節點屬于Ω。Ω中每個節點都有一個層次屬性，表示與根節點的最短拓撲距離，根節點的層次規定為0。對于任意兩個節點?φp,φq∈Ω，定義變量λφpφq表示兩者的層次關系

(4)

對于非根節點的?φq∈Ω，Ω至少存在一個節點與其互為鄰居且是其上層節點，從而同步消息可由根節點開始沿廣播節點向外傳播

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

(5)

為確保網絡中所有節點可監聽到同步消息，須保證每個節點至少與一個廣播節點互為鄰居，即

?ψi∈Ψ,ψi≠φp

(6)

目標是求取符合上述條件的具有最小元素數量的同步集Ω

argminΩ‖Ω‖

(7)

將網絡看作一個無向連通圖，尋找最小同步集的問題等價于構造一個以根節點為樹根的非葉子節點最少的生成樹，即最多葉子生成樹(MLST, Maximum Leaf Spanning Tree)[15]，是一個NP-HARD問題，可利用集中式優化算法求解。集中式算法通過節點把拓撲連接信息傳輸到匯聚節點，求取最優解，再將結果分發給每個節點。這種方法對網絡鏈路造成較大負荷，當傳輸過程發生消息丟失時會造成結果錯誤。本文研究了更具實用意義的分布式算法，節點通過有限數量的消息交互，判斷自身是否廣播節點。

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

可相互傳輸消息的兩個節點之間存在無線通信鏈路，而距離對鏈路通信質量存在影響。節點接收消息時，采樣到對應無線鏈路的LQI(Link Quality Indicator)參數，例如ZigBee采用接收信號強度指示值(Receive Signal Strength Indicator, RSSI)作為LQI。在理想情況下，當兩個節點之間沒有障礙物時，LQI值隨距離的增大而減小；當障礙物存在時，以節點為中心向障礙物延伸的方向上，LQI值雖呈規律性變化，但距離越遠LQI值越小的趨勢依然成立。因此，在實際環境中節點可通過消息的LQI值來獲知鄰居節的大概空間信息。

單向同步算法分為兩個階段，本文主要詳述層次發現階段，流程如圖3所示。

圖3 單向同步算法流程圖

Step 1 根節點啟動同步流程，廣播一跳層次發現幀P_DISCOVERY。在層次發現過程中的所有控制和數據幀都包括以下幾個公共域：

MsgTpyeSeqSourceIDSourceLevel

其中，MsgTpye為幀類型；Seq為層次發現幀序列號，根節點可增大Seq發起新一輪層次發現；SourceID為源節點的ID號，網絡中每個節點都有唯一的ID，根節點為0；SourceLevel是源節點的層次，根節點為0，子節點的層次為父節點加1。此外，節點保存一個狀態參數來指示工作狀態，初始時為S_INIT。

根節點置狀態為S_FINISH，表示層次發現階段結束。

Step 2 節點接收到i-1層節點的P_DISCOVERY幀，若狀態為S_INIT則接收該幀。節點收到多個幀時，選擇最小的ID作為父節點并記錄其ID，并把自身的層次修改為i。節點根據幀的LQI值判斷：

1)LQI>閾值L1，表明節點離其父節點較接近，則置狀態為S_FINISH，完成層次發現并退出；

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

候選廣播節點同時接收同層鄰居節點的P_EXCH_NEIGHBOR幀，等待一段時間確保接收完畢。通過準確的時序控制，可確保同一層次的所有節點在同一時間段內進行同步。候選廣播節點保存同層鄰居集合Ns的鄰居表及LQI值。

Step 3 第i層候選廣播節點在同層鄰居集合Ns中計算其最大互鄰集合Gmax和最近鄰集合Imax。

定義節點互鄰集合G，G中任意節點np和nq互為鄰居；則節點的最大互鄰集合Gmax為其所在K個互鄰集合中元素數量最多的一個，即

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

(8)

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

(9)

Gmax和Imax由候選廣播節點遍歷搜索Ns的鄰居表獲得。為降低搜索過程的運算量，可將Ns按其ID號的大小排序后存儲。對排序后的Ns搜索Gmax，運算復雜度為O(nlogn)，其中n為Ns的元素數量且值較小，故運算可在資源受限的傳感器節點上進行。獲取Imax只需搜索Ns的LQI值即可，運算復雜度為O(n)。另外初始化計數值CG=0和CI=0。

Step 4 候選廣播節點退避等待隨機時間trand，節點狀態修改為S_BACKOFF，在此期間接收Ns中節點發送的P_ABANDON幀。這些鄰居節點稱作放棄節點，說明該節點放棄成為廣播節點，在同步階段只作監聽，不發送同步消息。候選廣播節點將放棄節點ID寫入集合Sabandon，并判斷：

1) 若放棄節點nA∈Gmax，則使計數值CG=CG+1，即更新記錄最大互鄰集合中放棄節點的數量；

2) 若放棄節點nA∈Imax，則使計數值CI=CI+1，更新記錄最近鄰集合中放棄節點的數量。

Step 5 候選廣播節點隨機等待時間trand到達，分析是否成為廣播節點。

在最大互鄰集合Gmax中，任意節點廣播消息集合內其余節點都能監聽到，因此Gmax中的所有節點處于一個相對較小的空間范圍內。若Gmax中均為廣播節點，則同步時廣播的同步消息覆蓋范圍有較大面積的重疊，造成不必要的能量和網絡開銷。實際上，只需在Gmax中選取部分廣播節點，并使其分布合理，那么同步覆蓋范圍約等于Gmax中所有節點的同步覆蓋范圍。

候選廣播節點作以下判斷：

1)在trand內收到Gmax中所計數的放棄節點數量為CG，若CG<‖Gmax‖-B1，在Gmax中搜索，若存在未放棄的節點，且該節點為最近鄰集合Imax中節點，即：

(Gmax-Sabandon)∩Imax≠φ

(10)

則放棄成為廣播節點，廣播P_ABANDON幀通知鄰居節點；若上述條件不滿足，則進入2)。

2)在trand內收到Imax中放棄節點數量為CI，若CI<‖Imax‖-B2，即Imax中存在過多候選節點，則放棄成為廣播節點，同樣廣播P_ABANDON幀；否則，進入3)。這個條件保證了Imax中保留不多于B2個同步節點，因為集合內的節點進行同步廣播所覆蓋的有效面積會有大部分重疊，這是不必要的。

3)若CG<‖Gmax‖-B3，說明Gmax中潛在的廣播節點數量超過最大值B3，強制放棄成為廣播節點，廣播P_ABANDON幀。否則，成為同步集中的廣播節點。為了控制同層節點在同一時間段內進行層次發現，保證算法流程準確，加入一個時序控制策略。廣播節點在此前退避了隨機的周期trand監聽同層鄰居節點的P_ABANDON幀，變量trand由其本地保存；同時節點希望與同層的廣播節點在盡量接近的時刻廣播P_DISCOVERY幀告知下層節點。因此，設定每層的層次發現過程的執行周期為T，則廣播節點在分析完畢后應該等待時間(T-trand)后，再廣播P_DISCOVERY幀，進入Step 6。

同層候選廣播節點鄰居收到P_ABANDON幀，按Step 4處理。上述的B1,B2,B3為可變參數，根據實際網絡情況調整其值大小使同步達到最佳狀況。

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

另外，第i層放棄節點A廣播P_ABANDON幀，狀態為S_INIT的鄰居B收到后，將A的ID存儲起來，并開啟定時器等待tabandon時間。若在此期間，B沒有收到任何的P_DISCOVERY幀，說明了自身在層次發現階段被遺漏了。此時B發送P_INFORM幀告知該放棄節點A，A重新成為廣播節點，發送P_DISCOVERY幀。

在實際場景中，網絡邊緣可能存在少量的節點，其僅有的鄰居在Step 2的LQI閾值判斷時放棄成為廣播節點，導致這些節點被遺漏從而同步失敗。這種極端的情況，可應用簡單的策略解決。具體在同步階段，被遺漏節點經過長時間沒有監聽到同步消息，確認同步失敗，向鄰居節點提出同步請求，等待其回復同步消息即可。

4 實驗與仿真

4.1 單雙向同步對比

為驗證單向同步策略的同步精度，本文進行了相關的實驗，并與雙向同步技術對比。實驗在CC2530為核心的ZigBee平臺上進行，協議棧為TI的Z-Stack2.5，利用兩個節點進行單跳的時間同步。單雙向同步各進行8次實驗，并使用雙蹤示波器測量同步誤差，結果見表1。硬件實驗數據表明，單向同步的平均同步誤差約為12.5 μs，雙向同步約為11 μs。由此可知利用時間戳捕捉技術進行單向同步，可達到與雙向同步一致的精度，而結果的差異來源于同步時引入的系統隨機誤差，并非同步方法所導致。

表1 單向與雙向同步誤差對比

4.2 大規模網絡實驗

在單向同步的基礎上，本文提出了基于最大互鄰集合的同步算法。為驗證算法的有效性，在NS2(Network Simulator 2)軟件平臺上進行大規模網絡下的仿真，同時使用文獻[8]中的算法進行對比。文獻[8]提出了基于雙向同步的成對廣播時間同步算法，控制同步消息開銷，與本文算法目標一致，新穎且具權威性。本文實驗中，參數取值分別為B1=1,B2=2,B3=3，實驗結果見圖4至圖7。

圖4 網絡規模100～400，同步集節點數量和同步消息開銷

圖5 網絡規模250，同步集節點數量和同步消息開銷

圖6 網絡規模250，執行算法的消息開銷

圖7 網絡規模250，成功同步節點比例

圖4是網絡節點數從100至400范圍變化的實驗結果，平均節點鄰居數大約保持在10個，即節點密度不變。在不同網絡規模下，本文的算法得到的廣播節點的數量均比文獻中算法結果少。在同步階段，本文算法的廣播節點只需發送一個同步消息，同步消息數量與廣播節點數量一致；而成對同步需要消息交換，因此消息開銷是同步集節點數量的兩倍。本文算法在同步階段平均消息開銷比單向同步算法低61.43%，在降低能耗方面更有效。

圖5中是網絡節點數固定為250個、節點密度變化時的實驗結果。本文算法的廣播節點數比文獻中方法同步集節點數量平均少20.74%，消息開銷節約60.37%。與網絡規模變化時相似，在不同網絡密度下本文的方法在節省網絡開銷和節點能耗方面更優秀。

圖6是節點密度變化時，在層次發現階段算法執行所需要傳遞的消息數量對比情況。表明本文方法所產生的平均消息開銷為文獻中算法的46.8%，遠小于后者。文獻中算法在層次發現流程中，節點選擇下層同步子節點需要多次的消息交互，而本文算法中節點只需固定數量的消息開銷。

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

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

5 結 語

本文對無線傳感器網絡的時間同步問題進行了研究。利用單向同步的時間戳標記技術，將時間同步轉化為構造最小同步集問題，并建立數學模型，提出分布式的算法求解。算法通過在層次發現階段節點生成最大互鄰集合和最近鄰集合，減少同步集節點數量。加入子節點向父節點注冊、層節點監聽放棄幀以及時序控制等策略提高了算法性能。ZigBee硬件平臺的實驗證明了單向同步可達到較高精度；NS2平臺的仿真表明本文方法在不同網絡規模、不同網絡密度下可降低同步消息開銷，提高成功同步節點比例，能更有效地解決時間同步問題。

參考文獻：

[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.