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