無線傳感器網絡分布式同步協議

王 晶,張 帥,高 丹,王營冠

(中國科學院上海微系統與信息技術研究所無線傳感網與通信重點實驗室,上海 201899)

無線傳感器網絡分布式同步協議

王 晶,張 帥,高 丹,王營冠

(中國科學院上海微系統與信息技術研究所無線傳感網與通信重點實驗室,上海 201899)

針對無線傳感器網絡同步問題,提出分布式時間同步和分布式數據同步的解決方法.前者要求簇頭網絡進行局部信息交互,并采用低通濾波技術去除噪聲干擾;后者為節點提供網絡數據均值,要求簇頭網絡執行比例一致性算法,簇頭在迭代過程中引入簇內節點數量.實驗結果表明,分布式時間同步具備抗噪聲能力,該算法在前期收斂速度最快.網格狀網絡和隨機網絡實驗表明,分布式時間同步和分布式數據同步的通信開銷非常低,它們的收斂速度均高于普通數據同步.

無線傳感器網絡;同步;分簇;通信開銷;收斂速度

無線傳感網(Wireless Sensor Network,WSN)同步問題主要分為時間同步和數據同步兩類.時間同步為傳感器節點提供絕對或邏輯時鐘,從而服務于任務調度、睡眠機制、數據融合、定位跟蹤等應用.考慮用Ti(t)代表節點的本地時鐘,則時間同步確保節點時鐘滿足條件:

時間同步的研究對象分為單跳同步和多跳同步兩類.目前,單跳同步模型已經基本確立[1],而多跳同步模型包括自頂向下架構和分布式架構兩種設計方案.其中,自頂向下時間同步由根節點發起網內同步,或者沿同步樹逐層開展同步,或者通過洪泛方式執行同步,此類架構以降低同步開銷和提升同步精度為首要目標[2-3].與此相反,分布式時間同步僅要求節點與鄰居進行本地時鐘同步,通過分布式算法將局部時間信息擴散至全網絡,確保節點獲取相同的時鐘信息,此類架構具備高魯棒性和強抗毀性特征[4-6].

在傳感網中,數據同步是一種重要的數據融合算法[7],主要為節點提供全網絡數據的平均值.考慮用xi代表節點i的測量數據,則數據同步確保節點數據滿足

數據同步為時間同步提供基礎模型[4-5].由式(1)可知,時間同步要求網內節點共享相同的時鐘;由式(2)可知,數據同步不僅要求網內節點共享相同的數值,并且要求該數值等于全網絡測量值的平均值.由此可知,數據同步在時間同步的基礎上增加了限制條件.另外,數據同步也采用分布式架構實現,尤其適用于節點分布式布設的無線傳感器網絡.綜上所述,數據同步與分布式時間同步的實現方法相一致.

目前,基于數據同步實現的時間同步主要包括全局時鐘同步和平均時間同步.前者屬于異步算法,節點對鄰居時鐘取平均并將更新量發送給鄰居[4];后者要求節點對鄰居時間求和并進行低通濾波,可減少單跳同步噪聲干擾[5].在數據同步方面,研究者主要以分析算法的收斂速度為目標.研究者提出奧法提-賽博數據同步(Olfati-saber Data Synchronization,ODS),并指出當網絡拓撲保持連通時,該模型可實現網絡范圍內收斂[8].之后,ODS在特殊場景下的收斂條件也被提出,包括:①有向和無向網絡[9];②具有通信時延和拓撲變化的網絡[10];③采用二階分布式平均的網絡[11].

上述時間同步基于數據同步實現,而數據同步研究則側重于收斂速度分析.然而,以ODS為代表的數據同步并沒有綜合考慮傳感網的重要特點:節點規模大,節點能量受限,即節點規模大而導致無線傳感網執行數據同步收斂速度較慢,這會增加算法迭代次數,進而增大網絡通信負擔.因此,筆者重點解決在無線傳感網中實現分布式同步的收斂時間和通信開銷問題.

1　分布式時間同步協議

筆者提出分布式時間同步(Distributed Time Synchronization,DTS)協議.不同于數據同步,時間同步并不要求節點時鐘等于全網上電時刻的均值,這是因為節點時鐘會隨著時間而不斷增長,并且節點間只需要實現邏輯時鐘一致即可.因此,利用分簇技術對ODS進行改進,確保算法收斂性能的提升,并減少實現網絡同步的通信開銷.

圖1　信息傳遞示意圖

注意,有時簇頭與鄰居交換時間時需要引入網關,此時,一種較合理的方式是網關成為參考節點,兩相鄰簇頭同時偵聽參考節點的廣播,記錄收到該廣播時的本地時間,并通過網關相互轉發時間記錄.采用此方案可有效地去除發送端時延,其同步精度較高[1].式中ε代表節點與鄰居進行同步時引入的噪聲誤差,該誤差以99.8%的置信度符合高斯分布,并且各誤差間相互獨立分布,因此式(3)中噪聲方差會隨著迭代次數不斷變大.為有效地去除噪聲對算法穩定性的影響,采用低通濾波技術對時鐘調整量進行濾波,從而去除高頻噪聲

分布式時間同步主要分為3個階段.

第1階段,協議要求進行網絡分簇.分簇需滿足條件:獲取簇頭信息,簇頭可覆蓋全網絡,任一普通節點只屬于一個簇頭.在無線傳感網中,簇頭網絡的規模遠小于原始網絡,簇頭間為1跳或2跳鄰居,2跳鄰居簇頭需通過中間節點實現通信.分簇是傳感網的基本調度和路由算法,用于保證節點數據以較低跳數傳達至全網絡,該技術的引入不會增加額外通信開銷[12].

第2階段,協議要求簇頭網絡執行分布式同步,并通過多次迭代更新實現簇頭網絡同步.如圖1(b)所示,節點與鄰居進行單跳時間同步,并計算相互間的時鐘漂移量.具體表現為,在第k次迭代過程中,簇頭i以載波監聽多路訪問(Carrier Sense Multiple Access,CSMA)方式將時間Ti(k)發送給鄰居,同時,各節點也接收并存儲來自鄰居的時鐘信息.在此過程中,簇頭i利用介質訪問控制(Media Access Control,MAC)層時間戳機制記錄本地時鐘[2],去除發送/接收端隨機時延的影響,之后簇頭計算時鐘調整量:的干擾,即

其中,μ代表低通濾波器的調節因子,可以對濾波器性能進行調整.通過式(3)和(4),節點可以獲取時鐘調整量,從而進行本地時鐘更新,多次迭代過程后簇頭網絡將擁有相同的時間[8].

第3階段,協議要求簇頭負責簇內節點同步.簇內同步由多個單跳同步子問題組成,每個單跳同步子問題在一個簇內執行.簇頭已經成為具有準確時間信息的根節點,它們通過經典單跳同步算法進行簇內普通節點同步.

分布式時間同步利用簇頭代替原始網絡執行ODS,協議在保持分布式同步的高魯棒性的前提下,有效地減少了參與同步的節點數量,從而降低了通信開銷.另外,由于簇頭網絡和原始網絡拓撲結構類似,而前者的節點規模遠小于后者,尤其是在高密網絡條件下,所以在前者執行同步的收斂速度遠快于后者[8-9].高收斂速度保證簇頭網絡的迭代次數低于原始網絡,這從另一個角度降低了通信開銷.

2　分布式數據同步協議

數據同步能夠為時間同步提供理論模型,并且數據同步本身也是一種重要的數據融合算法.然而,ODS算法起源于多智能體領域,并沒有考慮到無線傳感網覆蓋范圍廣、節點數量多、節點能量有限的特性.筆者提出分布式數據同步(Distributed Data Synchronization,DDS),利用簇頭代替普通節點執行數據同步,從而降低了同步開銷.考慮數據同步的限制條件,提出新型比例一致性算法,確保節點獲取網絡數據均值.另外,對分布式數據同步的收斂性能進行了證明,并對其收斂速度進行了詳細分析.

分布式數據同步協議的信息傳遞方向如圖1所示.在圖1(a)中,簇內節點利用計數器獲取本地時鐘,或利用傳感器獲取測量數值,簇內節點將帶有自身標識符和初始數值的數據包轉發給簇頭,簇頭統計簇內數值之和,其中C代表簇內各節點的集合,數值X(0)成為簇頭的初始估計值.由此可見,簇頭估計值代表簇內所有節點的估計值之和.此后,如圖1(b)所示,簇頭與鄰居交換當前估計值.注意,初次交換的數據包需要包含簇內節點數量.之后,簇頭I利用鄰居估計值計算自身的更新量,即

式(5)與式(3)的不同體現了分布式數據同步與分布式時間同步的不同.在分布式時間同步中,雖然由簇頭代替簇內節點執行第2階段同步,但分布式時間同步僅要求節點間時間一致即可,并不要節點的時間信息等于網內初始上電時間的平均.簇頭在獲取估計值更新量后對估計值進行更新,即

下面對分布式數據同步的迭代更新階段進行分析,并結合圖論對分布式數據同步的收斂性能進行具體說明.在式(5)中,由于簇頭代替簇內節點執行分布式數據同步,所以簇頭擁有簇內所有節點估計值的總和,可知簇內任一節點i的更新量等價于簇頭估計值求取簇內平均:

考慮用G=(V,E)代表原始網絡,用G′=(V′,E′)代表致密網絡,其點集合滿足V′=V,其邊集合滿足E′={(i,j)|i∈CI,j∈CJ,I=J∨I∈NJ},則式(7)等于在致密網絡中執行ODS[8].考慮原始網絡中任一連接邊(i,j)∈E,i∈CI,j∈CJ,則有如下兩種情況:①I=J,由E′的定義知(i,j)∈E′;I≠J,因為(i, j)∈E,可知CI與CJ相鄰,所以I∈NJ,由E′的定義知(i,j)∈E′.由上述分析可知E?E′.因為原始網絡為無向連通圖,可知致密網絡也屬于無向連通圖,由式(7)可實現網絡數據同步[8],所以式(5)可實現網絡數據同步.在式(7)實現網絡數據同步后,節點估計值更新量近似為零,節點估計值近似相等,可知xi≈xj,近似等于網絡初始值均值,所以,發現簇頭估計值呈現比例關系,簇頭估計值正比于簇內節點數量.簇內節點數量越多,則簇頭估計值越大,所以稱式(5)為比例一致性算法.另外,原始網絡與致密網絡節點規模相同,前者的邊密度低于后者,可知在原始網絡執行ODS的收斂速度慢于在致密網絡執行ODS,所以ODS的收斂速度慢于分布式數據同步.最后,式(6)的加權值δ與致密網絡的拓撲結構相關聯,假設G′的拉普拉斯矩陣為L′,則L′的特征值滿足0=λ′1≤λ′2≤…≤λ′n≤2d′max,其中d′max為G′最大度數,可知第二小特征值λ′2為式(7)的收斂速度指數,而2/(λ′2+λ′n)代表理論最優加權值δ*[9].

最后,分布式數據同步通過減少迭代次數,并降低單次迭代過程的信息交互量來減少實現網絡同步的通信開銷.在原始網絡中用N代表算法迭代次數,用E代表單向邊個數,用P代表數據包大小,則ODS所需數據通信量為NE P.相應地,分布式數據同步所需數據通信量為N′E′P.由上述分析可知,分布式數據同步可有效地提升收斂速度,由此可知N＞N′.另外,由分簇算法選擇出的簇頭數目遠低于節點數量,由此可知, E?E′.通過上述兩點,可以發現NEP?N′E′P.綜上所述,分布式數據同步能夠有效地減少數據通信量,適用于能效要求高的無線傳感器網絡.

3　實驗結果

為驗證算法的有效性,通過MATLAB對算法進行仿真實驗,實驗場景主要包括網格狀網絡和隨機布設網絡.

3.1網格狀網絡理論性能分析

本實驗旨在對比網格網絡的單向邊數和拉普拉斯圖特征值,前者等于單次迭代通信包數量,后者代表網絡同步收斂速度.

在圖2中,采用貪心算法選擇簇頭[2],簇頭網絡的單向邊數綜合考慮簇頭直接相連和經過網關節點中轉兩種情況.如圖2(a)所示,原始網絡邊數量遠高于簇頭網絡,ODS要求原始網絡節點與鄰居交換數據,分布式時間同步和分布式數據同步要求簇頭網絡節點與鄰居交換數據,因此筆者所提算法具有更低的單次迭代

圖2　網格狀網絡的性能

數據交互量,它們的通信開銷非常低.圖2(b)顯示同步理論收斂速度,該速度由收斂指數λ2和加權值2/ (λ2+λn)的乘積來表示.在相同拓撲結構下,節點規模越大,則λ2越小.所以,3種算法的理論收斂速度整體上均隨著網絡規模的增大而降低,并且原始網絡的理論收斂速度慢于簇頭網絡的.在相同網絡規模下,邊密度越大,則λ2越大.由圖2(a)可知,原始網絡的邊密度遠小于致密網絡的,所以原始網絡的理論收斂速度慢于致密網絡的.另外,簇頭網絡執行數據同步的速度略微快于致密網絡的.綜上所述,在網格狀網絡中,ODS的理論收斂速度慢于分布式時間同步和分布式數據同步的,而分布式時間同步的收斂速度略微快于分布式數據同步的.

3.2網格狀網絡噪聲干擾分析

以下對分布式時間同步的抗噪聲性能進行驗證.實驗場景為6×6網格狀網絡,實驗對象包括無噪聲干擾條件下執行ODS;-30 dBw噪聲干擾條件下執行ODS;-30 d Bw噪聲干擾條件下執行分布式時間同步,利用低通濾波器過濾數據更新量.圖3曲線代表全網絡數據標準差隨著迭代次數的變化情況,其中參數設定:迭代步長為3,統計次數為100,噪聲功率為-30 dBw,濾波因子為0.1.如圖3所示,在無噪聲干擾條件下, ODS的結果隨著迭代步數的增加而持續降低;在-30 d Bw高斯噪聲干擾條件下,ODS和分布式時間同步均在一定迭代次數后出現不繼續收斂現象,這是由于高斯噪聲干擾的疊加效果引發的.然而,當存在噪聲干擾時, ODS的收斂精度始終低于分布式時間同步,這說明后者具備抵抗噪聲的能力.另外,考慮迭代次數低于13的情況,發現分布式時間同步的收斂精度在3類場景中最高,這說明該算法在前期收斂速度最快,在同步精度要求不高的無噪聲干擾場景中可以代替ODS.

圖3　噪聲干擾條件下的協議性能

3.3隨機布設網絡實驗

本實驗在隨機網絡中執行,網絡大小為(100,100),節點數量為301,節點通信半徑為20,網內節點含有隨機分配的0～1之間的數值.

圖4(a)為隨機網絡節點分布圖.由圖可知,網絡中所有節點均為隨機分布,分布式貪心算法選擇出的簇頭均勻分布在網絡中,簇頭網絡可覆蓋所有網內節點.圖4(b)為網絡標準差跟隨迭代次數的變化情況,通過圖中曲線可知,3種算法均可保證網絡標準差不斷減少,能夠實現網絡數據同步.

圖4　隨機網絡實驗結果

圖5為簇頭數據跟隨迭代次數的變化統計,直觀展示了網絡數據同步現象.通過3幅子圖可知,3種算法均可保證網絡數據不斷趨于同步.

圖5　簇頭節點隨迭代次數變化情況

需要注意的是,圖4(b)結果顯示,分布式時間同步的收斂性能優于ODS的,而分布式數據同步的收斂性能優于分布式時間同步的,這與圖2(b)的理論收斂速度結果不完全一致.這是因為,一方面如圖4(b)和圖5所示,ODS和分布式時間同步的初始狀態相同,其初始狀態代表簇頭的初始分配值,而分布式數據同步的初始狀態更加集中,其初始狀態代表簇內數據均值;另一方面,分布式數據同步等價于在致密網絡中執行ODS,分布式數據同步尤其適用于大規模多跳無線傳感網.另外,圖5(a)中有一個明顯的鋸齒波形,該波形由圖4(a)中大黑點產生,該簇頭的特點是它位于網絡中間區域,此類節點更多地負責網內數據流動和平均化,其波動體現了網絡數據的不均衡特性和數據流動性特征.更進一步,在實驗過程中發現理論最優權值并非最優,對3種算法來說,其最優權值分別為ODS中,分布式時間同步中,分布式數據同步中,其中和分別代表原始網絡、簇頭網絡和致密網絡理論最優權值.表1所示為原始網絡和簇頭網絡連接邊數量對比,由表可知,圖4(a)隨機網絡包含4 784條邊,每次迭代過程需要發送9 568個數據包.在簇頭網絡中,直接相連的簇頭間有10條邊,通過網關節點中轉的簇頭間有24條邊,簇頭網絡中邊的數量為10+24×2=58,每次迭代過程需要發送116個數據包.通過數據可以看出,分布式時間同步和分布式數據同步能夠大幅度地降低數據通信開銷.

表1　不同網絡邊數量統計

4　結束語

筆者提出分布式時間同步和分布式數據同步協議,以降低算法通信開銷和提升算法收斂速度為目標.網格狀網絡實驗表明,分布式時間同步和分布式數據同步利用簇頭網絡代替原始網絡執行分布式同步,前者的邊密度遠小于后者的,因此分布式時間同步和分布式數據同步可大幅度地降低網絡負載.分布式時間同步在簇頭網絡執行普通數據同步ODS,簇頭網絡節點規模遠低于原始網絡的,分布式時間同步的理論收斂速度快于ODS的.分布式數據同步在簇頭網絡執行比例一致性算法,等價于在致密網絡執行ODS,致密網絡邊密度遠高于原始網絡的,分布式數據同步的理論收斂速度快于ODS的.另外,噪聲干擾環境實驗表明,分布式時間同步具備抗噪聲能力,該算法在前期收斂速度很快.最后,隨機網絡實驗表明,分布式數據同步的收斂速度快于ODS和分布式時間同步算法的,其原因在于分布式數據同步利用簇頭進行簇內數據求和,等價于一次簇內數據平均化.

[1]HEIDARIAN F,SCHMALTZ J,VAANDRAGER F.Analysis of a Clock Synchronization Protocol for Wireless Sensor Networks[J].Theoretical Computer Science,2012,413(1):87-105.

[2]WANG J,ZHANG S,GAO D,et al.Two-hop Time Synchronization Protocol for Sensor Networks[J].EURASIP Journal on Wireless Communications and Networking,2014,2014(1):39.

[3]王晶,張帥,高丹,等.無線傳感器網絡擴張型時間同步協議[J].西安電子科技大學學報,2015,42(2):133-139. WANG Jing,ZHANG Shuai,GAO Dan,et al.Expansive Time Synchronization Protocol for Wireless Sensor Networks [J].Journal of Xidian University,2015,42(2):133-139.

[4]LI Q,RUS D.Global Clock Synchronization in Sensor Networks[J].IEEE Transactions on Computers,2006,55(2): 214-226.

[5]SCHENATO L,FIORENTIN F.Average TimeSynch:A Consensus-based Protocol for Clock Synchronization in Wireless Sensor Networks[J].Automatica,2011,47(9):1878-1886.

[6]師超,仇洪冰,陳東華,等.一種簡單的分布式無線傳感器網絡時間同步方案[J].西安電子科技大學學報,2013,40 (1):93-99. SHI Chao,QIU Hongbing,CHEN Donghua,et al.Simple Distributed Time Synchronization Scheme for Wireless Sensor Networks[J].Journal of Xidian University,2013,40(1):93-99.

[7]XIAO L,BOYD S,LALL S.A Scheme for Robust Distributed Sensor Fusion Based on Average Consensus[C]//Fourth International Symposium on Information Processing in Sensor Networks.Piscataway:IEEE,2005:63-70.

[8]OLFATI-SABER R,FAX J A,MURRAY R M.Consensus and Cooperation in Networked Multi-agent Systems[J]. Proceedings of the IEEE,2007,95(1):215-233.

[9]OLFATI-SABER R,MURRAY R M.Consensus Problems in Networks of Agents with Switching Topology and Timedelays[J].IEEE Transactions on Automatic Control,2004,49(9):1520-1533.

[10]WANG X,SABERI A,STOORVOGEL A A,et al.Consensus in the Network with Uniform Constant Communication Delay[J].Automatica,2013,49(8):2461-2467.

[11]WEN G,HU G,YU W,et al.Consensus Tracking for Higher-order Multi-agent Systems with Switching Directed Topologies and Occasionally Missing Control Inputs[J].Systems&Control Letters,2013,62(12):1151-1158.

[12]YU J,QI Y,WANG G,et al.A Cluster-based Routing Protocol for Wireless Sensor Networks with Nonuniform Node Distribution[J].AEU-International Journal of Electronics and Communications,2012,66(1):54-61.

(編輯:郭 華)

Distributed synchronization protocol for wireless sensor networks

WANG Jing,ZH ANG Shuai,GAO Dan,WANG Yingguan
(Key Lab.of Wireless Sensor Network and Communication,Shanghai Institute of Microsystem and Information Technology,Chinese Academy of Sciences,Shanghai 201899,China)

Distributed time synchronization and distributed data synchronization are proposed for the synchronization problem in wireless sensor networks.The former requires the cluster head network to execute local information exchange,and it adopts low-pass filtering to remove the noise interference.The latter provides network-wide data mean to nodes,and it requires the cluster head network to execute the proportion consistency algorithm,in which the number of nodes within a cluster is introduced during the iterative process.Experimental results show that the distributed time synchronization maintains anti-noise performance,and that the algorithm converges fast in the earlier stage.Grid-like network and random network experiments show that distributed time synchronization and distributed data synchronization have a low communication overhead,and their convergence rates are faster than that of general data synchronization.

wireless sensor networks;synchronization;clustering;communication cost;convergence speed

TP393

A

1001-2400(2016)04-0105-06

10.3969/j.issn.1001-2400.2016.04.019

2015-04-13 網絡出版時間：2015-10-21

中國科學院戰略性先導專項資助項目(XDA06020300);上海市科委資助項目(12DZ0500100)

王 晶(1988-),男,中國科學院上海微系統與信息技術研究所博士研究生,E-mail:wangjingchn@163.com.

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.038.html