無線傳感器網(wǎng)絡(luò)分布式同步協(xié)議

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

(中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所無線傳感網(wǎng)與通信重點實驗室,上海 201899)

無線傳感器網(wǎng)絡(luò)分布式同步協(xié)議

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

(中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所無線傳感網(wǎng)與通信重點實驗室,上海 201899)

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

無線傳感器網(wǎng)絡(luò);同步;分簇;通信開銷;收斂速度

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

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

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

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

目前,基于數(shù)據(jù)同步實現(xiàn)的時間同步主要包括全局時鐘同步和平均時間同步.前者屬于異步算法,節(jié)點對鄰居時鐘取平均并將更新量發(fā)送給鄰居[4];后者要求節(jié)點對鄰居時間求和并進(jìn)行低通濾波,可減少單跳同步噪聲干擾[5].在數(shù)據(jù)同步方面,研究者主要以分析算法的收斂速度為目標(biāo).研究者提出奧法提-賽博數(shù)據(jù)同步(Olfati-saber Data Synchronization,ODS),并指出當(dāng)網(wǎng)絡(luò)拓?fù)浔３诌B通時,該模型可實現(xiàn)網(wǎng)絡(luò)范圍內(nèi)收斂[8].之后,ODS在特殊場景下的收斂條件也被提出,包括:①有向和無向網(wǎng)絡(luò)[9];②具有通信時延和拓?fù)渥兓木W(wǎng)絡(luò)[10];③采用二階分布式平均的網(wǎng)絡(luò)[11].

上述時間同步基于數(shù)據(jù)同步實現(xiàn),而數(shù)據(jù)同步研究則側(cè)重于收斂速度分析.然而,以O(shè)DS為代表的數(shù)據(jù)同步并沒有綜合考慮傳感網(wǎng)的重要特點:節(jié)點規(guī)模大,節(jié)點能量受限,即節(jié)點規(guī)模大而導(dǎo)致無線傳感網(wǎng)執(zhí)行數(shù)據(jù)同步收斂速度較慢,這會增加算法迭代次數(shù),進(jìn)而增大網(wǎng)絡(luò)通信負(fù)擔(dān).因此,筆者重點解決在無線傳感網(wǎng)中實現(xiàn)分布式同步的收斂時間和通信開銷問題.

1　分布式時間同步協(xié)議

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

圖1　信息傳遞示意圖

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

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

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

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

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

第3階段,協(xié)議要求簇頭負(fù)責(zé)簇內(nèi)節(jié)點同步.簇內(nèi)同步由多個單跳同步子問題組成,每個單跳同步子問題在一個簇內(nèi)執(zhí)行.簇頭已經(jīng)成為具有準(zhǔn)確時間信息的根節(jié)點,它們通過經(jīng)典單跳同步算法進(jìn)行簇內(nèi)普通節(jié)點同步.

分布式時間同步利用簇頭代替原始網(wǎng)絡(luò)執(zhí)行ODS,協(xié)議在保持分布式同步的高魯棒性的前提下,有效地減少了參與同步的節(jié)點數(shù)量,從而降低了通信開銷.另外,由于簇頭網(wǎng)絡(luò)和原始網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)類似,而前者的節(jié)點規(guī)模遠(yuǎn)小于后者,尤其是在高密網(wǎng)絡(luò)條件下,所以在前者執(zhí)行同步的收斂速度遠(yuǎn)快于后者[8-9].高收斂速度保證簇頭網(wǎng)絡(luò)的迭代次數(shù)低于原始網(wǎng)絡(luò),這從另一個角度降低了通信開銷.

2　分布式數(shù)據(jù)同步協(xié)議

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

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

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

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

考慮用G=(V,E)代表原始網(wǎng)絡(luò),用G′=(V′,E′)代表致密網(wǎng)絡(luò),其點集合滿足V′=V,其邊集合滿足E′={(i,j)|i∈CI,j∈CJ,I=J∨I∈NJ},則式(7)等于在致密網(wǎng)絡(luò)中執(zhí)行ODS[8].考慮原始網(wǎng)絡(luò)中任一連接邊(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′.因為原始網(wǎng)絡(luò)為無向連通圖,可知致密網(wǎng)絡(luò)也屬于無向連通圖,由式(7)可實現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)同步[8],所以式(5)可實現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)同步.在式(7)實現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)同步后,節(jié)點估計值更新量近似為零,節(jié)點估計值近似相等,可知xi≈xj,近似等于網(wǎng)絡(luò)初始值均值,所以,發(fā)現(xiàn)簇頭估計值呈現(xiàn)比例關(guān)系,簇頭估計值正比于簇內(nèi)節(jié)點數(shù)量.簇內(nèi)節(jié)點數(shù)量越多,則簇頭估計值越大,所以稱式(5)為比例一致性算法.另外,原始網(wǎng)絡(luò)與致密網(wǎng)絡(luò)節(jié)點規(guī)模相同,前者的邊密度低于后者,可知在原始網(wǎng)絡(luò)執(zhí)行ODS的收斂速度慢于在致密網(wǎng)絡(luò)執(zhí)行ODS,所以O(shè)DS的收斂速度慢于分布式數(shù)據(jù)同步.最后,式(6)的加權(quán)值δ與致密網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)相關(guān)聯(lián),假設(shè)G′的拉普拉斯矩陣為L′,則L′的特征值滿足0=λ′1≤λ′2≤…≤λ′n≤2d′max,其中d′max為G′最大度數(shù),可知第二小特征值λ′2為式(7)的收斂速度指數(shù),而2/(λ′2+λ′n)代表理論最優(yōu)加權(quán)值δ*[9].

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

3　實驗結(jié)果

為驗證算法的有效性,通過MATLAB對算法進(jìn)行仿真實驗,實驗場景主要包括網(wǎng)格狀網(wǎng)絡(luò)和隨機(jī)布設(shè)網(wǎng)絡(luò).

3.1網(wǎng)格狀網(wǎng)絡(luò)理論性能分析

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

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

圖2　網(wǎng)格狀網(wǎng)絡(luò)的性能

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

3.2網(wǎng)格狀網(wǎng)絡(luò)噪聲干擾分析

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

圖3　噪聲干擾條件下的協(xié)議性能

3.3隨機(jī)布設(shè)網(wǎng)絡(luò)實驗

本實驗在隨機(jī)網(wǎng)絡(luò)中執(zhí)行,網(wǎng)絡(luò)大小為(100,100),節(jié)點數(shù)量為301,節(jié)點通信半徑為20,網(wǎng)內(nèi)節(jié)點含有隨機(jī)分配的0～1之間的數(shù)值.

圖4(a)為隨機(jī)網(wǎng)絡(luò)節(jié)點分布圖.由圖可知,網(wǎng)絡(luò)中所有節(jié)點均為隨機(jī)分布,分布式貪心算法選擇出的簇頭均勻分布在網(wǎng)絡(luò)中,簇頭網(wǎng)絡(luò)可覆蓋所有網(wǎng)內(nèi)節(jié)點.圖4(b)為網(wǎng)絡(luò)標(biāo)準(zhǔn)差跟隨迭代次數(shù)的變化情況,通過圖中曲線可知,3種算法均可保證網(wǎng)絡(luò)標(biāo)準(zhǔn)差不斷減少,能夠?qū)崿F(xiàn)網(wǎng)絡(luò)數(shù)據(jù)同步.

圖4　隨機(jī)網(wǎng)絡(luò)實驗結(jié)果

圖5為簇頭數(shù)據(jù)跟隨迭代次數(shù)的變化統(tǒng)計,直觀展示了網(wǎng)絡(luò)數(shù)據(jù)同步現(xiàn)象.通過3幅子圖可知,3種算法均可保證網(wǎng)絡(luò)數(shù)據(jù)不斷趨于同步.

圖5　簇頭節(jié)點隨迭代次數(shù)變化情況

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

表1　不同網(wǎng)絡(luò)邊數(shù)量統(tǒng)計

4　結(jié)束語

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

[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]王晶,張帥,高丹,等.無線傳感器網(wǎng)絡(luò)擴(kuò)張型時間同步協(xié)議[J].西安電子科技大學(xué)學(xué)報,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]師超,仇洪冰,陳東華,等.一種簡單的分布式無線傳感器網(wǎng)絡(luò)時間同步方案[J].西安電子科技大學(xué)學(xué)報,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 網(wǎng)絡(luò)出版時間：2015-10-21

中國科學(xué)院戰(zhàn)略性先導(dǎo)專項資助項目(XDA06020300);上海市科委資助項目(12DZ0500100)

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

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.038.html