一种多跳无线传感器网络时间同步方法

邓雪峰,孙瑞志,聂　娟,2,张永瀚

(1.中国农业大学 农业部农业信息获取技术重点实验室,北京 100083;2.北京农学院 计算机与信息工程学院,北京 102206)



一种多跳无线传感器网络时间同步方法

邓雪峰1,孙瑞志1,聂娟1,2,张永瀚1

(1.中国农业大学 农业部农业信息获取技术重点实验室,北京 100083;2.北京农学院 计算机与信息工程学院,北京 102206)

摘要:针对无线传感器网络中时间同步技术，降低同步误差的问题，通过优化生成树模型的结构，利用协作同步时间同步技术与生成树生成过程结合，降低生成树的深度，解决同步中误差累积，减少了时间同步误差。通过模拟实验证明，节点经过优化后的同步误差累积低于未优化节点。本方案适合对常用的时间同步算法的优化。

关键词:无线传感器网络;时间同步;协同;误差;优化

随着无线通信技术、嵌入式技术的发展,无线传感器网络(Wireless Sensor Networks,WSN)已经广泛的应用于军事、农业、环保、医疗、建筑、制造等领域。

在互联网(Internet)技术中,时间同步问题已经有了成熟的协议,可以精确的实现当前互联网中的时间同步问题。有代表性的有:NTP(Network Time Protocol)时间同步协议[1]。利用GPS(Global Position System)时间同步技术。

由于WSN自身的特点，其中的时间同步问题不能直接利用Internet中使用的技术,如NTP时间同步协议并不适合网络不稳定、网络拓扑结构经常改变的无线传感器网络。GPS需要专门的设备进行时间同步,而传感器的功能受限、成本受限的环境往往不能单独配备相关的设备。

针对WSN的特点,ELSON et al提出了无线传感器网络时间同步问题[2]。此后,学术界提出了多种WSN时间同步算法。而这几种方式的解决方案中,单跳节点的WSN的时间同步技术基本可以用第一种方案满足同步需求。而多跳WSN由于其拓扑结构复杂,基本上可以把以上各种方案分为两大类,一种是以时间同步根节点为中心,根据同步目标节点到时间同步的根节点的路径上的跳数而分层同步的集中式时间同步模型,另一种是以相邻节点先同步而最后达到整个网络同步的分簇式的自组织时间同步模型。

在实际应用中,集中式时间同步模型现在的应用较为广泛,而对于集中式时间同步模型中一个重要的步骤就是建立层次结构。一般来说,在同步的初始过程中将首先建立一个生成树。由于时间同步目标节点到生成树根节点的跳数的增加也会带来误差的积累,目标节点到生成树根节点的跳数与生成树的深度成正比。因此,降低生成树的深度会降低误差的增加。

笔者在分析了当前多跳WSN时间同步主要技术的情况下,对于时间同步集中式时间同步模型进行进一步分析,结合协作时间同步技术,利用部分节点的协作时间同步降低时间同步中生成树的深度,从而降低时间同步过程中的误差累积。

1相关研究

时间同步技术对于WSN是一个基础问题,由于WSN的通信范围、传感器节点性能以及功能受限制等因素,不能将现在的Internet网络中同步的协议直接应用于WSN时间同步问题上。自从WSN时间同步问题被提出后,针对WSN不同属性的多种相关算法被提出。

1.1常用的WSN同步算法

比较常见的多跳WSN时间同步算法有TPSN(Timing-sync Protocol for Sensor Networks)，RBS(reference broadcast synchronization)[4]，DMTS(Delay Measurement Time Synchronization)[5]，FTSP(Flooding Time Synchronization Protocol)[6]，LTS(Lightweight Time Synchronization)[7]，HRTS(hierarchy referencing time synchronization)[8]等算法。

1.2WSN时间同步其它解决方案

萤火虫时间同步算法与协作同步技术的提出给WSN时间同步技术提供了新的思路。

在1990年,文献[9]中提出M&S模型,该模型采用脉冲耦合振荡器的原理,将目标同步节点抽象为振荡器,通过同步信号达到各个节点共振,从而完成时间同步操作。因此,RFA(reachback firefly algorithm)[10]协议利用了萤火虫同步算法的基本原理,并且降低了该模型的收敛时间。但是,脉冲耦合振荡器的原理仅是萤火虫同步模型在理论模型上模拟,还不能揭示其原理,并且实现这个模型受节点相似等条件约束。

协作同步机制是在文献[11]中提出,在其后,文献[12]中提出了空间平均的概念,协作同步机制的提出是以概率论为基础,利用同步节点相邻的节点的共同作用,消除同步产生的误差,理论上,当节点数越大时,同步产生的误差越小,其同步结构如图1所示。

图1　协作同步结构图Fig.1　Collaboration synchronization structure chart

协作同步过程由R0开始,首先也是建立整个网络的层次结构,但是建立些分层结构会记录各层间所有的节点间的可通信的结构。如,R0至R1层之间,时间同步根节点R0与R1层节点间的每个连通点只能与R0连接,此时只有一个路径,而当同步信号由R1层向R2层节点传播时,R1层可能有多个节点与R2层的目标节点有通路,在协作同步机制中,这样的通路会被记录,用来共同完成时间同步消息的传播,由于各个节点的随机误差服从高斯分布,因此,可以利用平均的方案消除系统误差,从而达到提升整个系统同步精度的目标。但是,协作同步机制中要求系统节点密度较高,才可以实现多个节点共同协作完成时间同步的目标,并且实际系统中现在应用较少,还处于实验阶段。

综上所述,在常用的WSN时间同步过程中,依层次对待同步的节点进行划分,形成时间同步生成树是时间同步的第一个步骤,不管用集中式同步还是分布式同步的方式。时间同步生成树的深度在常用的WSN时间同步方案中起到了累积误差的效果,因此降低生成树的深度是对降低误差是一个有效的途径。在WSN的其它解决方案中,萤火虫算法与协作同步算法在实际应用中还是应用较少,萤火虫算法由于原理的模型至今依然是个可以探讨的问题,协作同步的算法利用概率的方法可以降低系统的误差,因此,本文将协作同步原理用于常用同步算法中的部分节点之中,从而降低生成树的深度,在不改变网络物理拓扑形式的基础上,提升算法的精度。

2同步模型分析

WSN时间同步模型一般说来都以一个时间基准点开始。这个节点在同步过程中一般作为时间同步生成树的根节点。同步的过程中一般是建立一个线性的时间同步模型,待同步的目标节点与同步基准节点间以消除节点间的时间差为目标进行通信。降低通信的误差一直是WSN时间同步算法的一个改进目标。

2.1WSN时间同步拓扑结构分析

Gwsn为一个WSN的拓扑结构图,设

式中：V为顶点集合；E为边的集合，E=V×V.

不妨以图1中的图为例说明WSN的物理拓扑结构。在时间同步协议中,设R0级的节点,即同步过程中的基准节点为v00；R1级的节点,分别设为v10,v11,v12，…；R2级的节点为v20,v21,v22，…；Rn级的节点为vn0,vn1,vn2，….则V={v00,v10,v11,v12，…,v20,v21,v22，…,vn0,vn1,vn2，…},E={e0010,e0011,e0012,…}.其中e0010代表v00至v10有一条消息通信路径相连。

假设有如图2所示的一个WSN拓扑结构,图中虚线圆代表圆内范围内节点可以通信,虚线箭头代表节点间或以通信,但是在依照时间同步算法分层时,被生成树忽略的通信路径。因此

式中：V={v00,v10,v11,v20,v21,v22,v30,v31,v32}；E={e0010,e0011,e1020,e1021,e1121,e1122,e2030,e2031,e2131,e2232}.

图2　WSN拓扑结构Fig.2　WSN topology

2.2WSN时间同步生成树

在进行时间同步时,第一个步骤就是生成一颗树结构,从而对时间同步中的各个节点以时间同步基点为中心进行分层,并以此生成树为基础对各层的节点进行消息传送。

Twsn为WSN时间同步的生成树,满足从根节点到任一节点必须有通路。Twsn中节点数与Gwsn中节点数相同,Twsn中的边集是Gwsn中边集的子集。

由以上条件,图3中的生成树为

式中：V={v00,v10,v11,v20,v21, v22,v30,v31,v32}；E={e0010,e0011,e1020,e1021,e1121,e2030,e2031, e2232}.即图中实线边组成的集合。

2.3WSN协作同步策略分析

文献[12]中提出了利用空间同步消除误差的WSN时间同步机制,由于WSN节点间的同步过程中,基准节点向其相邻节点发送同步脉冲后,第i级节点与i+1级节点时间同步时,由于WSN拓扑结构中,可能存在多个第i级节点可以与第i+1级节点中待同步节点具备通信能力,如图3所示。

图3　协作同步节点同步分析Fig.3　Synchronization analysis of collaboration syncnodes

其中不妨设,第i层节点vij,vij+1，vij+2，vij+3，这些节点的下标表示的含义为第i层的第j个节点及j+1，j+2，j+3个节点，并都可以与第i+1层节点vi+1k(表示第i+1层第k个节点)通信。

由文献[12]中,WSN时间同步节点满足

式中：ci(t)为待同步的时钟；i为偏移；αi为一个常量；Ψi(t)为一个随机误差,一般情况下服从N(0,σ2)的分布。

当多个第i层节点向第i+1层节点同时发送同步脉冲的时候,由于第i层节点服从均值为0的正态分布,因此第i层的误差不会累积到第i+1层,从而达到了降低系统误差的目标。如图4所示的情况,第i+1层第k个节点同时接收到第i层节点j，j+1，j+2，j+3的同步脉冲,利用协作同步机制,第i+1层的节点k的时钟应该取第i层4个节点时钟的平均值。

3部分节点协作时间同步策略

降低生成树的深度可以提升时间同步算法的精度,即减少同步的误差。一般来说,常用的同步算法生成树的深度确定后,只能通过增加设备的精度等手段减少同步中产生的误差,在2.3节中提出的协作同步算法是一个新的思路；但是算法要求WSN同步中节点密度要满足要求,在现在使用的还较少,其利用多个节点协作降低系统误差的方案可以应用于其它同步算法中。本方案利用协作时间同步的方法,将生成树中部分满足协作同步的节点进行重新排列,生成一个虚拟的生成树,从而总体上降低生成树的深度,从而使常用的WSN时间同步算法得以改进,降低系统误差。

3.1虚拟生成树的生成

WSN中节点时间同步过程中,常用的时间同步算法一般只利用生成树所生成的路径进行时间同步。如图2所示,生成树为实线连接的网络部分；虚线连接的网络部分同样可以用于通信,传送同步信息,但不是每一个节点均有多个传送信息路径。由2.3节中理论分析,如果利用这些非实线的连接路径传送时间同步信息,节点间就可以满足协作同步条件；因此,可以利用这些可协作同步的节点对生成树进行改进,建立一虚拟生成树,在保证同层结点误差累积不变的情况下,扩大生成树的宽度,降低生成树的深度,从而减少生成树中离根节点较远节点的同步误差累积。

如图4中所示,虚拟生成树产生的过程主要由以下几步构成。为了说明问题的简化,不妨设如果有2个以上i层节点可以与生成树中i+1层节点进行通信,即可认为第i+1层的这个节点满足协作同步通信条件。一般应用中,应该取更多的节点作为参考才能更好的满足消除误差的要求。

图4　虚拟生成树产生过程Fig.4　Process of virtual spanning tree generation

图4中实线连接的图是由图2中的拓扑结构生成的生成树,v21节点分别由上层节点v10和v11连接,在产生生成树的过程中,v11到v21被忽略。本方案利用这个忽略的边,把v21作为第2层可以进行协作同步的节点处理,由v00至v21产生一条虚拟路径,从而将v21的位置提升至生成树的第2层；处理完v21后继续查找第2层中是否有其它节点满足条件增加虚拟路径。

将第2层处理完成后,生成树第1层将转换成一个有实路径与虚拟路径结合的结构。在处理第3层的过程中,将通过实线连接的生成树节点按上一步扫描,将可提升层次的节点列出,上一步中新增加的虚拟节点不参与扫描;实线列出的节点扫描完毕后,将所有虚拟到第1层的节点对其下层节点进行同实线连接节点一样的扫描步骤。这两部分完成后,将新发现的可以提升层次的节点提升层次。

3.2虚拟生成树同层节点误差说明

虚拟生成树中的同层节点在同步时,有两种节点,一种是原始生成树中没有优化过的普通节点,这部分节点的误差与节点所在的生成树的层次成正比,层次越深的节点累积的误差越多,第i层节点累积的误差i的函数；而第i层的虚拟节点的累积误差跟非虚拟节点应该是相同的,以图5中节点v21为例。v21节点在未经优化前处于生成树的第2层,如果按照普通的同步方案,v21应该在同步的第二跳获得时间同步消息,因此,第1层节点v10的误差将累积到v21上,但是采用了本文的方案,v21提升至生成树的第1层后,根据协作同步方案的理论,由v10与v11共同产生同步信号,此时用平均的方法消除了系统误差,节点v21相当直接与v00进行时间同步,从而使v21的误差累积与v10，v11达到同一级别。

同样的情况在第i层同样适用,因此,通过此方案降低后的生成树,在第i层得到的误差将与原生成树第i层的误差是同一级别。

3.3虚拟生成树时间同步

利用虚拟生成树重新建立WSN时间同步生成树,可以降低生成树的深度的同时不增加相应层次的误差累积,有效的减少距离根结点较远处的时间同步误差累积,建立虚拟生成树的步骤如下:

1) 以v00为根节点扫描Gwsn,产生只有第一跳节点虚拟生成树Twsn,此时的叶子节点都是与v00相连的第一跳节点。

2) 从Twsn的叶子节点向第2层节点开始扫描Gwsn,设定可以协作同步的最少节点数为N,即当Twsn此时的某个叶子节点的下一跳节点在Gwsn的入度大于N时,该节点满足提升层次的条件,即建立一条虚拟边,连接该节点与其父节点的父节点。本次扫描结束后,第2层节点中有直接与根结点相连的一跳节点,也有通过N个第一跳节点,误差理论上累积等同于第一跳节点的虚拟第2层节点,标记虚拟节点的实际跳数与所在的虚拟生成树深度,并把虚拟节点实际跳数发布给所有本层节点。

3) 扫描虚拟生成树Twsn此时的叶子节点,所有节点按第2层扫描的原则标记,再次进行类似第2步的扫描并标记节点的层次与跳数,并把本层虚拟节点实际最大的跳数发布给本层所有节点。

4) 重复第3步,直到所有的节点都被插入到虚拟生成树中。

虚拟生成树生成后,本方案的时间同步步骤为:

1) 由虚拟生成树的根节点发送时间同步消息及协作时间同步脉冲(同步脉冲形式如文献[12]中提出的方案)。

2) 第i层节点接受到同步脉冲有两种情况,由于第i层节点有真实第i跳节点也同时有跳数大于i的虚拟节点组成,第i层通过对同步脉冲的计算,可以计算出本层节点最大跳数脉冲到达时间,所有本层节点等待最大跳数脉冲到达后,向下层节点发送计算后的多个协作同步脉冲。

4方案证明与验证

本方法对WSN时间同步算法给予优化,主要利用部分节点的协作同步优化了多跳WSN算法中由于跳数增加带来的时间同步误差累积。在最好的情况下,如果所有的虚拟生成树除了第1层节点外,其它层次的节点均为虚拟节点的情况下,本方案退化成协作时间同步算法,系统误差达到最小值;如果虚拟生成树中无虚拟节点,系统没有被优化。

优化过程中,最后的虚拟生成树比不优化的情况下会减少一层或同样深度,但是,如果虚拟生成树中有某层全部为虚拟节点,则系统误差在该层以下各层中至少减少一个层次累积。因此,优化后的虚拟生成树中,各层节点的误差累积小于等于不优化的方案。

本方案采用文献[13]中的误差分布方案,各实验节点的时钟误差假设服从正态分布(μ=0,σ=10μs),以图4所示的WSN结构为例,优化算法以TPSN算法为待优化的算法,节点可以协作同步的最少节点数设计为N=2.按照3.2节中的步骤生成的虚拟生成树如图5所示。

图5　虚拟生成树实验Fig.5　Experiment of virtual spanning tree

由于N=2,所以,位于第2层的v21节点可以优化提升层次至第1层,故算法扫描完第1层后,第1层的结点有v10，v11，v21,其中v21为虚拟节点,在扫描完第1层后,在第1层所有节点处标注第1层最大跳数为2,v21上标注实际跳数为2,同时标注自身所处于的层为1，完成了第1层的扫描,以第1层节点为叶子节点,扫描第2层节点,可以发现v31为入度为2的节点,故可以进行优化提升层次,同样,扫描后将v31标注实际跳数为3,同时标注自己所处扔层次为2,并在第2层所有节点标注第2层最大跳数为3 .

虚拟生成树生成完毕后同步过程为,由根节点发布时间同步信号,如本例中,将发送TPSN同步消息,发送一个协作同步脉冲,按照协作同步的过程,发送m个协作同步脉冲,间隔为d.

虚拟生成树的第1层节点如果自身标注跳数与自身所处层数相同的节点为非虚拟节点,如v10,v11,直接按照公式利用接收到的时间根节点发送的时间同步脉冲进行时间校正,而v21等m个协作同步脉冲结束后,接收由v10，v11转发的同步脉冲,此时,第1层节点同步完成,同时,v10，v11由于已知本层最大的跳数为2,在等v21接收完m个同步脉冲后,与v21同时向虚拟生成树第2层节点发送协作同步脉冲,v21由于是利用协作同步方式获得的时钟同步信息,虽然其跳数为2,但系统误差与v10，v11一致。v31的时间同步过程为v31等待第2层传送的时间同步脉冲,具体情况为等待2md个周期后,收到由v21传送的时间同步消息,但是v31此时已经成为虚拟生成树的第2层节点,它仅接收上层节点的同步消息,因此v31接收虚拟节点v21发送的时间同步消息,误差累积两次,因此跟同层节点v20,v22误差累积相当。

经实验,图5中上半部分为未利用本方案前,下半部分为利用本方案后,图中所有节点在经过一次实时同步后,图6为各节点的模拟实验误差图,图中取做7次模拟实验的误差数据。

图6　模拟实验误差数据图Fig.6　Experiment of virtual spaning tree

图6中各个节点取7次实验结果,每一个系列代表同一个节点在7个连续时间同步脉冲中的本身节点的误差值。假设各个节点的误差分布服务正态分布。

在经本方案优化后主要有两个节点的时间同步误差有所改变,如图7所示。图中各个节点未经累积的曲线代表各个节点在没有经过误差累积的误差的均值,是图6中7次实验的误差的均值。优化方案的曲线代表经本方案优化后各个节点的累积误差值,未经优化方案展示的是时间同步过程中一般方法所带来的累积误差,由图中可以看出在本方案中,如图5中的实例,v21与v31节点在优化过程中降低了时间同步误差。图中标注节点顺序(n)分别依次代表节点v00,v10,v11,v20,v21,v22,v30,v31,v32,同图中变化趋势可以看出在第5个节点和第8个节点的误差明显较示优化方案有所降低,其中第5个节点对应v21节点,第8个节点对应v31节点。

图7　时间同步分析图Fig.7　Time synchronization analysis chart

分别对v21,v31的误差优化与未优化状态进行对比分析。显然v21在未优化前v21获得时间同步信息路径为v00→v10→v21,优化后v00→(v10与v11协作)→v21.由于v10与v11协作完成了一跳的时间同步过程,因此这一跳时间同步过程没有带来系统误差；同样v31的同步误差仅由v21带来,在未优化的情况下,其误差由v10,v20经过两次传递时间同步消息,积累两次系统误差。

经过以上过程的分析,可以说明,在利用WSN中部分节点间协作时间同步的方法,可以减少系统中部分节点的时间同步误差。在节点密度较多的情况下,节点间通信更加密集,效果会更突出。

5总结

总结了WSN中时间同步算法,在常用的时间同步算法的设计中,生成树的深度是影响系统误差累积的主要因素,决定了离时间同步基准节点越远的节点同步时产生的系统误差越大。在引入了部分节点协作时间同步的方案后,可以降低系统中可以利用协作时间同步部分节点的系统误差积累,利用本方案可以优化常用的WSN时间同步算法。

参考文献：

[1]MILLS D L.Internet time synchronization: the network time protocol[J].IEEE Transactions on Communications,1989,39(10):1482-1493.

[2]ELSON J,REMER K.Wireless sensor networks: a new regime for time synchronization[J].Proc of the First Workshop on Hot Topics in Networks,2003,33(1):149-154.

[3]GANERIWAL S,KUMAR R,SRIVASTAVA M B.Timing-sync protocol for sensor networks[C]∥Proceedings of the 1st international conference on Embedded networked sensor systems.ACM,2003:138-149.

[4]ElSON J,GIROD L,ESTRIN D.Fine-grained time synchronization using reference broadcasts[C]∥Proceedings of the Fifth Symposium on Operating Systems Design and Implementation(OSDI 2002),2002.

[5]SU P,SU P.Delay measurement time synchronization for wireless sensor networks[EB/OL].http:∥www.intel-reserch.net/Publications/Berkeley/08112003132T-127.Pdf,2003.

[7]GREUNEN J V,RABAEY J. Lightweight time synchronization for sensor networks[J].Workshop on Wireless Sensor Networks and Applications WSNA,2003:11-19.

[8]DAI H,HAN R.TSync:A lightweight bidirectional time synchronization service for wireless sensor networks[J].Acm Sigmobile Mobile Computing & Communications Review,1994,8(8):125-139.

[9]MIROLLO R E,STROGATZ S H.Synchronization of pulse-coupled biological oscillators[J].Siam Journal on Applied Mathematics,1990,50(6):1645-1662.

[10]WERNER-ALLEN G,TEWARI G,PATEL A,et al.Firefly-inspired sensor network synchronicity with realistic radio effects[C]∥Proc.of the Third Int’l Conf.on Embedded Networked Sensor Systems,2005:142-153.

[11]HU A S,SERVETTO S D.On the scalability of cooperative time synchronization in pulse-connected networks[J].IEEE Transactions on Information Theory,2006,14(6):2725-2748.

[12]HU A S,SERVETTO S D.A scalable protocol for cooperative time synchronization using spatial averaging[J].EprintArxiv:cs/0611003,2006.

[13]PALCHAUDHURI S,SAHA A K,JOHNSON D B.Adaptive clock synchronization in sensor networks[C]∥Proceedings of the 3rd international symposium on Information processing in sensor networks.ACM,2004:340-348.

(编辑：刘笑达)

A Time Synchronization Method of Multihop Wireless Sensor Network

DENG Xuefeng1,SUN Ruizhi1,NIE Juan1,2,ZHANG Yonghan1

(1.KeyLaboratoryofAgriculturalInformationAcquisitionTechnology(Beijing),MinistryofAgricultureP.R.China,ChinaAgriculturalUniversity,Beijing100083,China;2.CollegeofComputerandInformationEngineering，BeijingUniversityofAgriculture,Beijing102206，China)

Abstract:The way to reduce the time synchronization (TS) error between crunodes has been a hot issue in research of TS technology in wireless sensor network. In this research, we solve the problem of error accumulation when sending TS message by optimizing the structure of spanning tree established during TS. Combination of collaboration TS scheme and spanning tree(ST) can reduce the deepth of ST and decrease TS errors. Simulation experiments show that synchronization error accumulation of optimized node is less than that of non-optimized node.

Key words:wireless sensor network;time synchronization;cooperative;blunder;majorization

文章编号:1007-9432(2016)02-0183-07

*收稿日期：2015-05-28

基金项目：中央高校基本科研业务费专项基金资助项目:农业大数据关键技术研究与应用(2015XD001)

作者简介：邓雪峰(1975-),男，吉林白城人，博士生，主要从事移动互联网、物联网研究，(E-mail)dxf75@sohu.com 通讯作者：孙瑞志，教授，博士生导师，主要从事农业信息化技术、计算机支持的协同工作的研究，(E-mail)sunruizhi@cau.edu.cn

中图分类号:TP31,TP39

文献标识码:A

DOI：10.16355/j.cnki.issn1007-9432tyut.2016.02.012