WSN中基于事件驅動的簇型時間同步協議①

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

?

WSN中基于事件驅動的簇型時間同步協議①

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

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

關鍵詞:無線傳感器網絡; 事件驅動; K覆蓋; 時間同步; 精度與能耗

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

本文的創新點與難點:

(1)文獻[1-5]的同步協議采用的是平面的拓撲結構,屬于時間驅動的同步協議.這些協議周期性的同步,側重于同步精度,未充分考慮WSN路由拓撲特點,WSN拓撲結構特點屬于動態自組織性,因此這些協議很難應用在WSN中.本文采用動態簇型的拓撲結構,克服了平面拓撲的缺陷,在保證事件區域節點之間同步的同時,均衡節點的能耗,延長整個網絡的生存時間.

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

(3)本文提出的K-CTSA算法需要在事件觸發區域選舉K個覆蓋節點,K的大小較難確定,K值越大,監測越準確,能耗相對也越大,需要根據實際應用環境以及精度要求確定.

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

1　能耗與時鐘模型

1.1能耗模型

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

1.2時鐘模型

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

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

2.1網絡拓撲的構建

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

圖1　事件驅動的拓撲結構

表1　模糊規則庫

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

2.2時間同步階段

圖2　簇首節點與簇內成員節點的同步機制

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

3　試驗仿真與分析

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

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

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

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

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

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

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

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

3.2整個網絡穩定期與節點生存時間分析

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

從圖5可以看出,當n=4,K=10時,從整個網絡節點的生存時間來分析,K-CTSA生存時間明顯優于TPSN協議.下面我們來分析一下,整個網絡的穩定期對比,即第一個節點出現死亡的時間隨K值的變化.從圖6可以看出,因為TPSN協議采用的是層次的拓撲結構,同步協議采用的是全網的雙向同步機制,每次有事件觸發時,都需要先進行全網的同步,因此TPSN協議的穩定期不會隨K值而改變.K-CTSA協議穩定期會隨觸發區域K覆蓋度增大而減小,但其穩定期都明顯優于TPSN協議.

圖6　網絡穩定期對比(n=4)

4　結語

節點能量有限是無線傳感器網絡的顯著特點,也是制約其發展的關鍵,因此低功耗協議的研究非常重要,本文針對事件驅動的無線傳感器網絡,提出一種K覆蓋的簇型時間同步算法(K-CTSA),當有事件觸發的區域節點處于激活狀態,無關節點處于休眠狀態,不但可以保證監測事件的準確性,也可以降低整個網絡的能耗.相比于層次的拓撲結構TPSN協議,K-CTSA協議在保證同步精度的前提下,可以較大的降低網絡節點的能耗,提高整個網絡的穩定期.

參考文獻

1王義君,錢志鴻,王桂琴,等.無線傳感器網絡能量有效時間同步算法研究.電子與信息學報,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時間同步協議.應用科學學報,2013,31(1):15–20.

6史昕,趙祥模,惠飛,等.一種面向分簇實時監測應用的WSN時間同步算法.四川大學學報(工程科學版),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徐世武,王平.異構無線傳感器網絡分簇路由機制.計算機系統應用,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田勇,唐禎安,喻言.能量均衡的室內無線傳感器網絡自適應分簇路由算法.電子與信息學報,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