无线传感器网络典型时间同步技术分析

杨 颖，刘 军

(武警工程学院研究生管理大队，陕西西安 710086)

无线传感器网络是集微机电系统、传感器技术、嵌入式计算技术、信息处理技术、现代网络、无线通信技术和数字电子学于一体的新一代面向任务的分布式网络。它是由在物理空间上密集分布的大量各类集成化的传感器节点，通过自组织方式构成网络，借助节点中不同类型的微型传感器实时监测、感知和采集各种环境或被监测对象信息，协作地进行处理，并以自组织多跳的方式将信息传送到用户终端，实现物理世界、计算机世界以及人类社会三元世界的连通［1］。无线传感器网络具有广阔的应用前景，主要应用在工业控制、生态环境、农业、防灾救灾、医疗保健、军事国防、智能家居、空间探索、物流等领域。时间同步是无线传感器网络支撑技术的重要组成部分。研究无线传感器网络中的时间同步首先要分析其应用需求，在无线传感器网络中，由于传感器节点分布密度高，而且自身资源有限，因此传统网络中高精度、不计成本和能耗的时间同步技术就不再适用于无线传感器网络，例如NTP协议。因此，研究适合无线传感器网络的时间同步就成为个国内外热点问题。

1 时间同步模型及算法

1.1 时间同步模型

随着时间同步概念的提出，其根据应用需求经历了3种模型的演变。

(1)模糊模型。是指所谓的时间同步仅需知道事件发生的先后次序，无需了解事件发生的具体时间。它是将时间同步简化为先来后到的问题，给人直观的印象，无须将细节具体化。

(2)相对模型。指在维持节点间的相对时间。在该模型中，节点间彼此独立，不同步，每个节点都有自己的本地时钟，且它知道与其他节点的时间偏移量。根据需要，每个节点可与其他节点保持相对同步。

(3)精准模型。特点在于它的惟一性，它要求全网所有节点都与基准参考点保持同步，维持全网惟一的时间标准。

1.2 时间同步算法

随着应用需求的不断提高，时间同步趋于第3种模型，而时间同步算法也逐步成熟，完成级间的跳跃。

1.2.1 RBS

RBS(Reference Broadcast Synchronization)［2］由J.Elson等人于2002年提出基于参考广播接收者与接收者之间的局部时间同步。具体描述为:第三方节点定时发送参考广播给相邻节点，相邻节点接收广播并记录到达时间，以此时间作为参考与本地时钟比较。相邻节点交换广播到达时间利用最小方差线性拟合的方法，估算两者的初始相位差和频率差，以此调整本地时钟，达到接收节点间的同步。为提高同步精度，可以增加参考广播的个数，也可以多次广播。

RBS消除了发送节点的时延不确定性，误差来源于传输和接收时延，同步精度较高;但由于多次广播参考消息，能耗较大，随着网络规模及节点数目的增多，开销也会越来越大，不适用于能量有限的无线传感器网络。

1.2.2 TPSN

TPSN(Timing － sync Protocol for Sensor Networks)［3］是由Saurabh Ganeriwal等人于2003年提出的基于成对双向消息传送的发送者与接收者之间的全网时间同步。具体描述如下:同步过程分为分层和同步两个阶段。分层阶段是一个网络拓扑的建立过程。首先确定根节点及等级，此节点是全网的时钟参考节点，等级为0级，根节点广播包含有自身等级信息的数据包，相邻节点收到该数据包后，确定自身等级为1级，然后1级节点继续广播带有自身等级信息的数据包，以此类推，i级节点广播带有自身等级信息的数据包，其相邻节点收到后确定自身等级为i+1，直到网络中所有节点都有自身的等级。一旦节点被定级，它将拒收分级数据包。同步阶段从根节点开始，与其下一级节点进行成对同步，然后i级节点与i－1级节点同步，直到每个节点都与根节点同步。成对同步的过程如图1所示。

图1 成对同步过程

节点i在本地时刻T1时向节点j发送同步请求，该请求中包含节点i的等级和T1，节点j在本地时刻T2时收到请求并在T3时回发同步应答，该应答包含T2和T3，节点i于本地时刻T4收到应答信息，根据时间关系可列出方程

其中，d是消息传输迟延;Δ为时钟偏差，经过计算得节点i计算出时间偏差Δ，从而调整自己的时钟，达到同步。

TPSN采用层次分级形成拓扑树结构，从根节点开始完成了所有叶子节点与根节点的同步，在MAC层打时间戳，降低了发送端的不确定性，减少了传送时延、传播时延和接收时延。该算法中任意节点的同步误差与其到根节点的跳数有关，跳数越多，误差越大，而与网络节点总数无关，所以该算法具有较好的可扩展性;但由于全网参考时间由根节点确定，一旦根节点失效，就要重新选取根节点进行同步，其鲁棒性不强，再同步还需要大量计算和能量开销，增加整个网络负荷。

1.2.3 DMTS

DMTS(DelayMeasurementTimeSynchronization)［4］是由Ping S于2003年提出的基于基准节点广播的发送者与接收者之间的全网时间同步。具体描述为:选择一个基准节点，广播包含时间的同步消息，接收节点根据时间信息估算消息传输时延，调整自身本地时间为同步消息所带时间加传输时延，消息传输时延td等于发射时延ts加接收处理时间tv，发射时延为发射前导码和起始符所需的时间，等于发射位数n乘以发射一位所需的时间t，接收处理时间等于接收处理完成时间t2减消息到达时间t1，得出公式

将DMTS应用到多跳网络中还采用与TPSN相同的分层方法进行同步，只是将每一层看作一个单跳网络，基准节点依次定在0级，1级，2级，n级，逐步实现全网同步。为避免广播消息回传，每个节点只接收上一层等级比自己低的节点广播。

DMTS以牺牲同步精度换取低能耗，结合使用在MAC层打时间戳和时延估计技术，消除了发送时延和接入时延，计算简单，开销小;但DMTS没有估算时钟频偏，时钟保持同步时间较短，时钟计时精度仍然影响同步精度，致使精度不高难以用于定位等高精度的应用中。

1.2.4 FTSP

FTSP(Flooding Time Synchronization Protocol)［5］是由Branislav Kusy于2004年提出的基于单向广播消息传递的发送者与接收者之间的全网时间同步。FTSP是对DMTS的改进，具体不同在于:

(1)FTSP降低了时延的不确定性，将其分为发送中断处理时延、编码时延、传播时延、解码时延、字节对齐时延和接收中断处理时延。

(2)类似于RBS，FTSP可通过发送多个信令包，接收节点通过最小方差线性拟合计算出发送者与接收者之间的初始相位差和频率差。

(3)FTSP根据一定时间范围内节点时钟晶振频率稳定原则，得出各节点间时钟偏移量与时间成线性关系，利用线性回归的方法通过节点周期性发送同步广播使得接收节点得到多个数据对构造回归直线，而且在误差允许的时间间隔内，节点可通过计算得出某一时间节点间时钟偏移量，减少了同步广播的次数，节省了能量。

(4)FTSP提出了一套较完整的针对节点失效、新节点加入等引起的拓扑结构变化时根节点选举策略，从而提高了系统的容错性和健壮性。

FTSP通过在MAC层打时间戳和利用线性回归的方法估计位偏移量，降低了时延的不确定性，提高了同步精度，适用于军事等需要高同步精度的场合。

1.2.5 LTS

LTS(Lightweight Time Synchronization)［6］是由 Van Greunen Jana和Rabaey Jan于2003年提出的基于成对机制的发送者与接收者之间的轻量级全网时间同步。该算法是在成对同步的基础上进行了改进，具体包括两种同步方式:第一种是集中式，首先构建一个低深度的生成树，以根节点作为参考节点，为节省系统有限能量，按边进行成对同步，根节点与其下一层的叶子节点成对同步，叶子节点再与其下一层的孩子节点成对同步，直到所有节点完成同步，因为同步时间和同步精度误差与生成树的深度有关，所以深度越小，同步时间越短，同步精度误差越小;第二种是分布式，当节点i需要同步时，发送同步请求给最近的参考节点，此方式中没有利用生成树，按已有的路由机制寻找参考点。在节点i与参考节点路径上的所有节点都被动地与参考节点同步，已同步节点不需要再发出同步请求，减少了同步请求的数量。为避免相邻节点发出的同步请求重复，节点i在发送同步请求时询问相邻节点是否也需同步，将同步请求聚合，减少了同步请求的数目和不必要的重复。

LTS根据不同的应用需求在可行的同步精度下降低了成本，简化了计算复杂度，节省了系统能量。

1.2.6 Tiny－sync和Mini－sync

Tiny－ sync和 Mini－ sync［7］是 由 Sichitiu 和Veerarittipahan于2003年提出的基于双向消息传递的发送者和接收者之间的轻量级时间同步。该算法的前提是假设每个时钟可近似为一个频率固定的晶振，则两个时钟C1(t)，C2(t)满足如下线性关系

其中，a12是两时钟的相对漂移;b12是两时钟的相对偏移。

算法仍采用TPSN中的双向信息传递，不同之处在于Tiny－sync和Mini－sync发送多次探测信息，探测信息与以往的同步请求不同，接收节点收到探测信息后立即返回消息，具体如下:节点i在本地时刻t0发送一个探测消息给节点j，节点j收到消息后记录本地时间tb并立即返回消息，节点i接收到消息后记录本地时间tr。(t0，tb，tr)叫做数据点，节点i多次发送探测消息，并根据式(6)用线性规划的原则得到a12和b12的最优估计，但用所有点计算运算量过大，Tiny－sync则是每次获得新数据点后与先前的进行比较，误差小于先前的误差时才采用新数据点，否则抛弃。Minisync是Tiny－sync的优化，修正了Tiny－sync可能抛弃有用点的缺憾，留下了可能在后面提供较好边界条件的数据点。

Tiny－sync和Mini－sync为满足无线传感器网络低能耗的要求，交换少量信息，利用夹逼准则和线性规划估算频偏和相偏，提高了同步精度，降低了通信开销。

2 时间同步算法性能对比分析

2.1 时间同步算法的性能评价指标

根据无线传感器网络自身资源有限、节点成本低、功耗低、自组织网络等特点，应从以下几点考虑无线传感器网络的时间同步算法［8］。

(1)能耗。由于无线传感器网络自身节点能量有限，其时间同步算法应保证在精度有效的前提下实现低能耗。

(2)可扩展性。在无线传感器网络中，节点数目增减灵活，时间同步算法应满足节点数目增减和密度变化，具有较强的可扩展性。

(3)鲁棒性。由于环境、能量等其它因素容易导致无线传感器网络节点无法正常工作，退出网络，所以时间同步算法应具有较强鲁棒性，保证通信畅通。

(4)同步寿命。是指节点间达到同步后一直保持同步的时间。同步寿命越短，节点就需要在较短时间内再同步，消耗的能量就越高。时间同步需要同步寿命较长的算法。

(5)同步消耗时间。是指节点从开始同步到完成同步所需的同步。同步消耗时间越长，所需的通信量、计算量和网络开销就越大，能耗也越高。

(6)同步间隔。是指节点同步寿命的结束到下一次同步开始所间隔的时间。同步间隔越长，同步开销就越小，能耗越低。

(7)同步精度。不同的应用要求不同数量级的同步精度，有的时间同步只需知道事件发生的先后顺序而有些则需精确到μs级。

(8)同步范围。分为全网同步和局部同步，全网同步难度大、费用高;局部同步较易实现。权衡整个系统的功能应用及能耗开支等因素才能选择合适的同步范围。

(9)硬件限制。考虑传感器节点的体积、大小、成本，时间同步算法会受到传感器节点硬件的限制，只有依赖硬件的条件，才能设计出满足应用需求的时间同步算法。

2.2 时间同步算法性能对比分析

经过在Mica2节点上的对比实验，根据这些指标对以上的时间同步算法进行比较分析。具体性能比较如表1所示。

表1 时间同步算法性能对比分析表

3 结束语

随着大规模无线传感器网络的广泛应用，时间同步技术可以向以下几方面发展:

(1)节点移动导致的拓扑结构可变。目前，大部分无线传感器网络都认为拓扑结构固定，没有考虑到节点的移动性，但节点自身移动也可以将时间信息带到另一个地方。

(2)依赖于节点的硬件条件，时间同步算法应在满足应用需求的条件下尽可能地减少能量消耗，达到最优效率。

时间同步是无线传感器网络的一个重要支撑技术，仍需要研究人员的不断探索和发现。

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393 －422.

［2］JEREMY E，LEWIS G，DEBORAH E.Fine－grained network time synchronization using reference broadcasts［C］.Boston，MA:Proceedings of the Fifth Symposium on Operating Systems Design and Implementation，2002:147 －163.

［3］GANERIWAL S，KUMAR R，SRIVASTAVA M.Timing － sync protocol for sensor networks［C］.Losangeles，CA:ACM Sen-Sys，2003.

［4］PING S.Delay measurement time synchronization for wireless sensor networks［EB/OL］.(2003－07－12)［2011－01－08］Http//www.intel_research.net/publication/Berkeley/081120031327_137.pdf.

［5］MAROTI M，KUSY B，SIMON G，et al.The flooding time synchronization protocol［C］.Baltimore，Mariland:Proceedings of the 2ndACM Conference on Embedded Networked Sensor Systems(SenSys)，2004:39 －49.

［6］GREUNEN V J，RABAEY J.Lightweight time synchronization for sensor networks［C］.San Diego，CA:Proc.2nd ACM Int'l.Conf.Wireless Sensor Networks and Apps，2003:11－19.

［7］SICHITIU M L，VEERARITTIPAHAN C.Simple，accurate time synchronization for wireless sensor networks［C］.New Orleans，LA:Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC2003)，2003:1266－1273.

［8］周贤伟，韦炜，覃伯平.无线传感器网络的时间同步算法研究［J］.传感技术学报，2006，19(1):1005 －9490.

［9］STOJMENOVIC'I.Handbook of sensor networks:algorithms and architectures［M］.New York:Wiley，2005.

［10］CHARLES S P.Mathematical aspects of heart physiology［M/OL］.(2009－08－11)［2011－03－12］http://www.math.nyu.eduPfaculty/peskin/heartnotes/index.html.

［11］HONG Y，SCAGLIONE A.A scalable synchronization protocol for large scale sensor networks and its applications［J］.IEEE Journal of Selected Areas in Communications，2005，23(5):1085－1099.

［12］任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14(07):1282 －1291.

［13］杨宗凯，赵大胜，王玉明，等.无线传感器网络时钟同步算法综述［J］.计算机应用，2005，25(5):1170 －1176.

［14］康冠林，王福豹，段渭军.无线传感器网络时间同步综述［J］.计算机测量与控制，2005，13(10):1021 －1023.

［15］谢洁锐，胡月明.无线传感器网络的时间同步技术［J］.计算机工程与设计，2007，28(1):76 －77.

［16］赵建军，姜建国，裴庆祺.低开销的无线传感器网络时间同步方法［J］.计算机工程，2007，33(21):113 －115.

［17］叶雪，孙燕.一种节能的无线传感器网络分簇时间同步算法［J］.计算机工程，2009，35(19):117 －119.

［18］张白桦.基于TPSN的时间同步改进算法［J］，计算机工程，2010，36(9):109 －110.

［19］程利娟.无线传感器网络时间同步算法研究［D］.西安:西北工业大学，2007.

［20］张坤.无线传感器网络时间同步技术的研究［D］.重庆:西南大学，2007.

［21］孙佳伟.无线传感器网络时间同步的研究［D］.鞍山:辽宁科技大学，2008.