WSN中基于事件驅(qū)動的簇型時間同步協(xié)議①

徐世武,王平(福建師范大學(xué) 協(xié)和學(xué)院信息技術(shù)系,福州 3507)(福建師范大學(xué) 光電與信息工程學(xué)院,福州 3507)

?

WSN中基于事件驅(qū)動的簇型時間同步協(xié)議①

徐世武1,王平2
1(福建師范大學(xué) 協(xié)和學(xué)院信息技術(shù)系,福州 350117)
2(福建師范大學(xué) 光電與信息工程學(xué)院,福州 350117)

摘 要:針對事件驅(qū)動的無線傳感器網(wǎng)絡(luò),提出一種K覆蓋的簇型時間同步算法(K-CTSA).當(dāng)節(jié)點檢測到事件發(fā)生時,廣播事件信息,鄰居節(jié)點收到廣播信息后,從休眠轉(zhuǎn)為激活狀態(tài).為了保證監(jiān)測事件的準(zhǔn)確性,必須保證在監(jiān)測區(qū)域的K覆蓋.結(jié)合模糊邏輯在事件發(fā)生區(qū)域選舉K個節(jié)點協(xié)同完成任務(wù),并選舉一個簇首節(jié)點.為了保證監(jiān)測任務(wù)的可靠性,處于激活的節(jié)點必須保證時間的同步,簇首與成員節(jié)點之間采用最小線性二乘法估算時鐘偏移與漂移.實驗仿真表明,K-CTSA在保證同步精度的前提下,網(wǎng)絡(luò)節(jié)點生存時間與穩(wěn)定期都明顯優(yōu)于TPSN協(xié)議.

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò); 事件驅(qū)動; K覆蓋; 時間同步; 精度與能耗

時間同步技術(shù)是無線傳感器網(wǎng)絡(luò)(WSN)的關(guān)鍵技術(shù)之一,也是WSN其它協(xié)議研究的前提,如數(shù)據(jù)融合以及多點協(xié)作感知數(shù)據(jù)就必須融合包含時間的信息.采用波到達(dá)時間差測距與定位也需要節(jié)點之間時間的同步[1].因為外在的因素,以及節(jié)點本身長期處在休眠狀態(tài)等,導(dǎo)致節(jié)點時鐘的偏移與漂移,因此需要對節(jié)點時鐘進(jìn)行修正.RBS協(xié)議是經(jīng)典的基于接收-接收同步協(xié)議[2],節(jié)點比較密集時,同步開銷較大,不太適合于能量受限的WSN,TPSN協(xié)議是經(jīng)典的同步補(bǔ)償機(jī)制[3],該協(xié)議思想被國內(nèi)外研究者大量引用與借鑒.該協(xié)議分成層次發(fā)現(xiàn)以及時間同步兩個階段,在同步階段采用發(fā)送-接收雙向同步估算節(jié)點之間的時間偏差與傳輸延遲,同步精度較高.為了減小多跳同步誤差的累積,文獻(xiàn)[4]提出了協(xié)作同步機(jī)制,其思想是采用信號疊加原理,在不增加發(fā)射功率的同時,讓同步信號傳播到更遠(yuǎn)的節(jié)點.文獻(xiàn)[5]針對TPSN協(xié)議過度依賴父節(jié)點的缺陷,提出基于脈沖耦合的TPSN時間同步協(xié)議,下一級節(jié)點可以收到上一級節(jié)點發(fā)送的同步信息,通過加權(quán)平均來調(diào)節(jié)時鐘.文獻(xiàn)[6]中針對WSN拓?fù)浣Y(jié)構(gòu)的特點提出一種分簇實時監(jiān)測的時間同步協(xié)議,在簇型拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上,采用跨層協(xié)議提出一種高精度的時間偏移補(bǔ)償協(xié)議.結(jié)合線性模型與最大似然估計實現(xiàn)簇首以及成員節(jié)點時間的同步.文獻(xiàn)[7]中提出CCTS簇型時間同步協(xié)議,通過成員節(jié)點平均虛擬時鐘來調(diào)整時鐘偏移與漂移,減少同步的數(shù)據(jù)通信量,簇型協(xié)議提高了算法的收斂速度.目前大部分的同步機(jī)制都是針對時間驅(qū)動的模型,即節(jié)點都是周期性的同步,WSN大部分應(yīng)用場合是基于事件驅(qū)動的,當(dāng)有事件觸發(fā)的時候,如森林火災(zāi)探測,目標(biāo)追蹤等,節(jié)點才處于工作狀態(tài),為了減少能耗,沒有事件觸發(fā)區(qū)域的節(jié)點處于休眠狀態(tài).本文針對事件驅(qū)動的WSN,提出一種K覆蓋的簇型時間同步算法.動態(tài)分簇的路由架構(gòu)更適合運用于WSN中[7,8].對事件觸發(fā)的區(qū)域節(jié)點進(jìn)行時間同步,不參與事件監(jiān)測的節(jié)點處于休眠,不但可以降低傳輸?shù)臄?shù)據(jù)量,降低能耗,也可以加快同步算法的收斂性[9].

本文的創(chuàng)新點與難點:

(1)文獻(xiàn)[1-5]的同步協(xié)議采用的是平面的拓?fù)浣Y(jié)構(gòu),屬于時間驅(qū)動的同步協(xié)議.這些協(xié)議周期性的同步,側(cè)重于同步精度,未充分考慮WSN路由拓?fù)涮攸c,WSN拓?fù)浣Y(jié)構(gòu)特點屬于動態(tài)自組織性,因此這些協(xié)議很難應(yīng)用在WSN中.本文采用動態(tài)簇型的拓?fù)浣Y(jié)構(gòu),克服了平面拓?fù)涞娜毕?在保證事件區(qū)域節(jié)點之間同步的同時,均衡節(jié)點的能耗,延長整個網(wǎng)絡(luò)的生存時間.

(2)文獻(xiàn)[6-7]的時間同步協(xié)議采用的是動態(tài)簇型的拓?fù)浣Y(jié)構(gòu),可以應(yīng)用于事件驅(qū)動的無線傳感器網(wǎng)絡(luò)中,然而當(dāng)有事件觸發(fā)時,這些協(xié)議需要所有節(jié)點進(jìn)行同步消息交換.文獻(xiàn)[9]折中了同步精度與網(wǎng)絡(luò)節(jié)點能耗,提出了針對事件驅(qū)動的時間同步機(jī)制,協(xié)議可以根據(jù)同步精度要求增加或者減少事件區(qū)域同步數(shù)據(jù)包的交換量.節(jié)點處于觸發(fā)或者休眠兩種狀態(tài),觸發(fā)與觸發(fā)節(jié)點進(jìn)行雙向同步消息交換,休眠節(jié)點接收到消息,進(jìn)行轉(zhuǎn)發(fā)或丟棄.從而在保證觸發(fā)節(jié)點的同步精度,也減少了無關(guān)節(jié)點進(jìn)行同步而所需的能耗.然而該協(xié)議仍然需要對所有觸發(fā)節(jié)點進(jìn)行同步.而本文針對事件觸發(fā)節(jié)點,綜合考慮距離與節(jié)點的剩余能量,通過模糊邏輯選舉K個最有效的節(jié)點,保證事件監(jiān)測的準(zhǔn)確性,最大減少了同步消息的交換量與能耗.

(3)本文提出的K-CTSA算法需要在事件觸發(fā)區(qū)域選舉K個覆蓋節(jié)點,K的大小較難確定,K值越大,監(jiān)測越準(zhǔn)確,能耗相對也越大,需要根據(jù)實際應(yīng)用環(huán)境以及精度要求確定.

(4)與本文引用的大部分文獻(xiàn)一樣,K-CTSA算法也停留在理論探討階段,通過仿真軟件驗證了算法的有效性與可行性.如果通過真實實驗驗證,與文獻(xiàn)[6,7,9]的簇型同步協(xié)議一樣,需要考慮路由與同步的跨層設(shè)計.

1　能耗與時鐘模型

1.1能耗模型

節(jié)點發(fā)送和接收消息所消耗的能量我們采用自由空間模型,分別如式(1)和(2)所示[8,12,13].L為傳輸信息的比特數(shù),d為節(jié)點之間的距離.Eelec為發(fā)送或者接收每比特數(shù)據(jù)所消耗的能量,εfs為天線放大倍數(shù).式(1)為節(jié)點發(fā)送消息的能量消耗,發(fā)送能耗主要為信號處理與功率放大.式(2)為節(jié)點接收消息的能耗,接收節(jié)點主要能耗為信號處理.

1.2時鐘模型

在目前的大部分WSN時間同步機(jī)制研究中,采用的時鐘模型是時鐘速率恒定模型[9,10],如式(3)所示,式(3)中,Ci(t)為節(jié)點的硬件時鐘,Ck(t)為節(jié)點的真實時間,aik為節(jié)點之間的相對漂移量,mik為節(jié)點之間的相對偏移量.在節(jié)點完全同步的理想情況下,aik為1,mik為0.

2　K覆蓋簇型時間同步算法(K-CTSA)設(shè)計

2.1網(wǎng)絡(luò)拓?fù)涞臉?gòu)建

整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示,事件發(fā)起節(jié)點廣播發(fā)起事件信息,則與其通信距離內(nèi)的節(jié)點從休眠狀態(tài)轉(zhuǎn)為激活狀態(tài).為了保證事件監(jiān)測的準(zhǔn)確性,則需要K個傳感節(jié)點協(xié)同感知完成任務(wù),K大于等于1,即K覆蓋問題[11,12],又為了避免過多的節(jié)點參與感知,造成傳輸過多重復(fù)的數(shù)據(jù),導(dǎo)致數(shù)據(jù)碰撞,沖突以及能量的浪費.事件發(fā)起節(jié)點結(jié)合模糊邏輯原理選舉K個鄰近傳感節(jié)點,模糊輸入變量主要考慮兩個因素,節(jié)點的剩余能量,用RE表示,RE分成三個等級,分別用L表示低,用M表示中等,用H表示高.節(jié)點與最初事件發(fā)起節(jié)點的通信距離,距離可以通過接收信號強(qiáng)度差來估算[13],用CD表示,CD分成三個等級,分別用L表示近.用M表示中,用H表示遠(yuǎn).將機(jī)率CH量化為3個等級,分別為L、M、H,依次代表低、中、高.則我們可以得到模糊規(guī)則庫,如表1所示.從表1可以看出,節(jié)點的剩余能量越高,與事件發(fā)起節(jié)點越近的節(jié)點成為K覆蓋節(jié)點的概率越大,通過選舉后,可以均衡網(wǎng)絡(luò)能耗,近距離節(jié)點不但保證事件監(jiān)測的準(zhǔn)確性,且能夠降低通信能耗.

圖1　事件驅(qū)動的拓?fù)浣Y(jié)構(gòu)

表1　模糊規(guī)則庫

當(dāng)選舉完K覆蓋節(jié)點后,其他節(jié)點處于休眠狀態(tài),因簇首節(jié)點的能耗最大,所以從K覆蓋節(jié)點選舉一個剩余能量最多的節(jié)點為簇首節(jié)點,其它(K-1)節(jié)點則成為簇內(nèi)成員節(jié)點.簇首將數(shù)據(jù)融合后傳輸給基站.

2.2時間同步階段

圖2　簇首節(jié)點與簇內(nèi)成員節(jié)點的同步機(jī)制

為了保證監(jiān)測事件的準(zhǔn)確性,必須保證K覆蓋節(jié)點時間的同步.只有同步的節(jié)點協(xié)同工作才可以保證監(jiān)測信息的準(zhǔn)確性.簇首節(jié)點與簇內(nèi)成員節(jié)點的同步機(jī)制如圖2所示.通過2.1節(jié)拓?fù)鋱D的構(gòu)建,簇首節(jié)點是K覆蓋節(jié)點中剩余能量最多的節(jié)點,從式(1)與式(2)節(jié)點的能耗模型可以看出,發(fā)送數(shù)據(jù)的能耗遠(yuǎn)大于接收數(shù)據(jù)的能耗.為了均衡網(wǎng)絡(luò)節(jié)點的能耗,同步機(jī)制采用發(fā)送—接收單向的同步機(jī)制,即簇首節(jié)點在短時間內(nèi)連續(xù)廣播幾個同步脈沖,脈沖的個數(shù)取決于當(dāng)前節(jié)點之間偏差的大小與同步精度要求.脈沖中記錄了簇首節(jié)點的發(fā)送時間,成員節(jié)點只負(fù)責(zé)接收同步脈沖,并記錄每次接收到的時間,在短時間內(nèi),節(jié)點之間的時鐘偏移與漂移是不變的,即圖2中的線段是平行的.成員節(jié)點通過最小線性二乘法擬合最優(yōu)的時鐘偏移與漂移,進(jìn)而與簇首節(jié)點實現(xiàn)同步.假設(shè)成員節(jié)點j與簇首的時鐘漂移為aj,成員節(jié)點j與簇首的時鐘偏移為mj,則根據(jù)式(3)我們可以得到簇首節(jié)點與成員節(jié)點的時鐘關(guān)系,如式(4)所示,式(4)中,dj為成員節(jié)點j與簇首的傳播延遲,由于電磁波在自由空間中的傳播近似為光速,而節(jié)點之間的通信距離很小,因此傳播延遲的時間約數(shù)十納秒,可以將其忽略[1],主要是對式(4)中的時鐘偏移與漂移進(jìn)行線性擬合.給出n對實驗數(shù)據(jù){(Ti,Ti+1,1≤i≤n},將這些數(shù)據(jù)帶入式(4)然后做差,如式(5)所示.要使偏差R最小,即所有數(shù)據(jù)偏差的平方和R2最小,分別對aj與mj求導(dǎo),得到式(6)與式(7),式(6)與式(7)等同于式(8),通過式(8)我們可以得到aj與mj,分別如式(9)與式(10)所示.則節(jié)點j就可以修改自己的時鐘偏移與時鐘漂移,使成員節(jié)點分別同步到簇首節(jié)點.

3　試驗仿真與分析

假設(shè)每個節(jié)點的初始能量為0.1J,100個節(jié)點隨機(jī)的分布在100m×100m的區(qū)域內(nèi),基站節(jié)點位于中間位置(50,50).Eelec=50nJ/bit,fse=100pJ/bit,節(jié)點的通信距離設(shè)置為30m.

3.1同步精度與同步開銷分析

假設(shè)K-CTSA算法簇首向成員節(jié)點連續(xù)廣播同步脈沖的個數(shù)為n.K的值為5,即在事件發(fā)生區(qū)域有一個簇首,四個成員節(jié)點協(xié)作完成任務(wù),假設(shè)簇首節(jié)點的初始相位為0.5,四個成員節(jié)點的初始相位服從(0,1)之間的均勻分布.

圖3　兩種算法平均單跳同步誤差(μs)

從圖3可以看出,TPSN同步協(xié)議采用的是雙向同步機(jī)制,與n值無關(guān),單跳平均同步誤差為25.6(μs).K-CTSA協(xié)議會隨n值增大,平均單跳同步精度精度提高.從圖3可以看出,簇首向成員節(jié)點連續(xù)廣播同步脈沖的個數(shù)n為4時,K-CTSA單跳平均同步誤差為23.6(μs),同步精度就優(yōu)于TPSN協(xié)議.

由1.1節(jié)的能耗模型分析可以看出,節(jié)點的能耗主要來源發(fā)送消息.由圖3可以知道,當(dāng)K=5,n=4時,K-CTSA的同步精度優(yōu)于TPSN,TPSN協(xié)議采用發(fā)送-接收雙向成對同步協(xié)議,4對節(jié)點完成一次同步需要發(fā)送8個同步消息包,而K-CTSA采用發(fā)送-接收單向廣播同步機(jī)制,4對節(jié)點完成一次同步需要發(fā)送4個同步消息包,發(fā)送個數(shù)取決于簇首連續(xù)廣播的脈沖個數(shù)n,而與K值無光.

圖4　兩種算法發(fā)送同步消息包比對(n=4)

從圖4可以看出,TPSN采用發(fā)送-接收雙向同步機(jī)制,發(fā)送同步消息數(shù)據(jù)包會隨K值增大成倍增加.而K-CTSA采用發(fā)送-接收單向廣播同步機(jī)制,不會隨K值而增加.

3.2整個網(wǎng)絡(luò)穩(wěn)定期與節(jié)點生存時間分析

圖5　節(jié)點運行過程中存活個數(shù)對比(n=4,K=10)

從圖5可以看出,當(dāng)n=4,K=10時,從整個網(wǎng)絡(luò)節(jié)點的生存時間來分析,K-CTSA生存時間明顯優(yōu)于TPSN協(xié)議.下面我們來分析一下,整個網(wǎng)絡(luò)的穩(wěn)定期對比,即第一個節(jié)點出現(xiàn)死亡的時間隨K值的變化.從圖6可以看出,因為TPSN協(xié)議采用的是層次的拓?fù)浣Y(jié)構(gòu),同步協(xié)議采用的是全網(wǎng)的雙向同步機(jī)制,每次有事件觸發(fā)時,都需要先進(jìn)行全網(wǎng)的同步,因此TPSN協(xié)議的穩(wěn)定期不會隨K值而改變.K-CTSA協(xié)議穩(wěn)定期會隨觸發(fā)區(qū)域K覆蓋度增大而減小,但其穩(wěn)定期都明顯優(yōu)于TPSN協(xié)議.

圖6　網(wǎng)絡(luò)穩(wěn)定期對比(n=4)

4　結(jié)語

節(jié)點能量有限是無線傳感器網(wǎng)絡(luò)的顯著特點,也是制約其發(fā)展的關(guān)鍵,因此低功耗協(xié)議的研究非常重要,本文針對事件驅(qū)動的無線傳感器網(wǎng)絡(luò),提出一種K覆蓋的簇型時間同步算法(K-CTSA),當(dāng)有事件觸發(fā)的區(qū)域節(jié)點處于激活狀態(tài),無關(guān)節(jié)點處于休眠狀態(tài),不但可以保證監(jiān)測事件的準(zhǔn)確性,也可以降低整個網(wǎng)絡(luò)的能耗.相比于層次的拓?fù)浣Y(jié)構(gòu)TPSN協(xié)議,K-CTSA協(xié)議在保證同步精度的前提下,可以較大的降低網(wǎng)絡(luò)節(jié)點的能耗,提高整個網(wǎng)絡(luò)的穩(wěn)定期.

參考文獻(xiàn)

1王義君,錢志鴻,王桂琴,等.無線傳感器網(wǎng)絡(luò)能量有效時間同步算法研究.電子與信息學(xué)報,2012,34(9): 2174–2179.

2Elson J,Girod L,Estrin D.Fine-grained network time synchronization using reference broadcasts.Proc.of the 5th Symposium on Operating Systems Design and Implementation.Boston.December,2002.147–163.

3Ganeriwal S,Kumar R,Srivastava MB.Timing-sync protocol for sensor networks.Proc.of the 1st International Conference Embedded Networked Sensor Systems.Los Angeles.November,2003.138–149.

4Hu A,Servetto SD.On the scalability of cooperative time synchronization in pulse-connected networks.IEEE Trans.on Information Theory,2006,52(6): 2725–2748.

5師超,仇洪冰.基于脈沖耦合的TPSN時間同步協(xié)議.應(yīng)用科學(xué)學(xué)報,2013,31(1):15–20.

6史昕,趙祥模,惠飛,等.一種面向分簇實時監(jiān)測應(yīng)用的WSN時間同步算法.四川大學(xué)學(xué)報(工程科學(xué)版),2012,44(5): 121 –129.

7Wu J,Zhang LY,Bai Y,et al.Cluster-based consensus time synchronization for wireless sensor networks.IEEE Sensors Journal,2015,15(3): 1404–1413.

8徐世武,王平.異構(gòu)無線傳感器網(wǎng)絡(luò)分簇路由機(jī)制.計算機(jī)系統(tǒng)應(yīng)用,2012,21(2):109–112.

9Lamonaca F,Gasparri R,Emanuele G,et al.Clock synchronization in wireless sensor network with selective convergence rate for event driven measurement applications.IEEE Trans.on Instrumentation and Measurement,2014,63(9): 2279–2287.

10Jun L,Zhou Z,Peng Z,et al.Mobi-Sync: Efficient time synchronization for mobile underwater sensor networks.IEEE Trans.on Parallel and Distributed Systems,2013,24(2): 406–416.

11Chamam A,Pierre S.On the planning of wireless sensor networks: Energy-efficient clustering under the joint routing and coverage constraint.IEEE Trans.on Mobile Computing,2009,8(8): 1077–1086.

12Ying SL,Chun YA,Chinh TV,et al.Delay-bounded and energy-efficient composite event monitoring in heterogeneous wireless sensor networks.IEEE Trans.on Parallel and Distributed Systems,2010,21(9): 1373–1385.

13田勇,唐禎安,喻言.能量均衡的室內(nèi)無線傳感器網(wǎng)絡(luò)自適應(yīng)分簇路由算法.電子與信息學(xué)報,2013,35(12): 2992–2998.

Clustering Time Synchronization Protocol Based on Event Driven for Wireless Sensor Network

XU Shi-Wu1,WANG Ping2
1(Concord College Department of Information Technology,Fujian Normal University,Fuzhou 350117,China)
2(College of Photonic and Electronic Engineering,Fujian Normal University,Fuzhou 350117,China)

Abstract:In this paper,we propose a K cover clustering time synchronization algorithm(K-CTSA)based on event driven for wireless sensor networks.When events are detected by a node,the node broadcasts event message.The neighbor nodes switch from dormancy to activation after they receive the broadcast message.In order to ensure the accuracy of the monitoring event,K coverage must be guaranteed in the monitoring area.In this paper,we election K nodes in the event area based on fuzzy logic and the K nodes cooperate to complete the task.The K-CTSA algorithm can select a cluster head from the K nodes.In order to ensure the reliability of monitoring tasks,the clock in the active nodes must be synchronized.Clock offset and drift are estimated by using the minimum linear two multiplication between cluster head and intra cluster nodes.Experimental simulation shows that the network node survival time and stability of K-CTSA are obviously better than the TPSN,which under the premise of ensuring the synchronization accuracy.

Key words:wireless sensor networks; event driven; K cover; time synchronization; accuracy and energy consumption

基金項目:①福建省教育廳A類科技項目(JA13368)

收稿時間:2015-07-22;收到修改稿時間:2015-09-28