王 晶，张 帅，罗炬锋，高 丹，王营冠

(中国科学院上海微系统与信息技术研究所物联网系统技术实验室，上海 201899)

1 概述

无线传感器网络作为构建通信环境的基础架构，由大量随机布设的传感器节点组成，这类网络具有资源受限、低功耗、多跳、自组织、应用种类多等特点。时间同步是传感器网络的重要支撑技术，它服务于传感网的多种应用，如定位技术、睡眠机制、MAC层协议、调度机制等。因此，对无线传感器网络时间同步技术进行研究是十分必要的。

时间同步协议的一个研究重点是在保证同步精度的前提下，降低同步过程的通信开销。现有多数算法均强调单跳同步精度，未考虑同步开销问题。而传感器节点本身能量有限，节点无线收发会消耗大量能量。针对该问题，本文提出一种基于变长帧的传感器网络时间同步算法，同时对传感器时间同步的收敛时间进行分析。

2 基本模型及典型算法

无线传感器网络时间同步算法包含以下3种基本模型：发送者-接收者模型，成对同步模型和接收者-接收者同步模型。

(1)基于发送者-接收者模型的典型算法主要包括洪泛时间同步协议(Flooding Time Synchronization Protocol,FTSP)[1]和时延测量时间同步(Delay Measurement Time Synchronization,DMTS)[2]，该模型通过MAC层时间戳机制去除通信过程中的随机时延。由于其简单、可靠等特点，发送者-接收者同步可以很好地应用于各种传感器网络，是传感网的事实同步算法。此外，基于扩散机制的传感网同步协议[3]采用与洪泛时间同步协议相同的多跳方案，通过信息扩散实现全网络时间同步。相对于发送者-接收者同步，成对同步模型具有更高的同步精度。

(2)基于成对同步模型的同步算法包括轻量型时间同步(Lightweight Time Synchronization,LTS)[4]、传感网时间同步协议(Timing-sync Protocol for Sensor Networks,TPSN)[5]、极小同步和微型同步(Tiny-Sync And Mini-Sync,TS-MS)[6]和基于多层抽样反馈的传感网时间同步算法[7]。此类同步算法通过2个节点相互交换同步信息实现单跳同步，利用信息传播过程的对等性降低通信时延引起的同步误差。轻量型时间同步和传感网时间同步协议采用生成树机制实现全网时间同步，根节点的时间信息沿着生成树经历多跳传递给目的传感器节点。极小同步和微型同步算法采用边界估计方法代替线性回归实现时钟频偏估计。基于多层抽样反馈的传感网时间同步算法通过在生成树中进行链路抽样反馈获取网络同步状况。这类同步算法抗毁能力差，通信负载和能量开销较大。

(3)基于接收者-接收者同步模型的经典算法为参考广播同步(Reference Broadcast Synchronization,RBS)[8]和能量高效参考广播同步[9]。参考广播同步利用参考节点广播参考信息，其广播域内各节点记录并交换接收时间信息，实现相互的同步。参考节点的引入能够完全去除发送端时延，因此，接收者-接收者同步模型在3种同步模型中具有最高的同步精度，但其缺点在于参考节点未同步、通信开销大以及多跳同步扩展复杂。

上述算法均强调单跳同步精度，没有考虑同步开销问题。而传感器节点本身能量有限，节点无线收发需要消耗大量能量，因此，设计低功耗时间同步算法是十分必要的。当前同步算法多通过降低通信包数量来解决该问题。文献[10]对参考广播同步算法进行改进，利用参考节点收集并广播各子节点同步时间信息，减少节点间同步信息交换。文献[11-12]基于成对同步(Pair-wise Synchronization,PBS)[13]单跳模型实现多跳时间同步，利用贪婪算法和分布式同步策略来计算出实现全网同步所需的最少节点，从而达到减少同步数据包的目的。

本文提出的时间同步算法通过降低同步过程中的数据通信量来降低能量消耗。不同于传统算法，其目标不是减少同步节点个数或降低同步通信包数量，而是降低同步帧本身开销。

3 时间同步机制

发送者-接收者同步的信息传输模型如图1所示。其中，节点P为具有准确时间的父节点；节点B为待同步节点。

图1 发送者-接收者同步信息交互模型

不同于发送者-接收者同步模型，在接收者-接收者同步模型中参考节点广播参考信息，收到该信息后P和B分别记录自己的本地时间，然后通过式(1)、式(2)计算出B节点时钟参数。该模型完全去除发送端时延，其同步误差约为发送者-接收者同步模型的一半。

4 基于变长帧的时间同步算法

传感器节点同步数据帧包含父节点本地时间信息。该数据帧组成结构如图2所示，其中，帧头代表父节点ID；长度控制标志便于节点获取数据信息；同步帧数据区存储发送节点本地时间。该基本帧格式，广泛应用于不同无线传感器网络，更完善的帧结构定义可参考IEEE 802.15.4协议。

图2 传感器节点同步帧格式

同步帧数据区所代表的本地时间包含大量冗余字节。为保证节点时间在短时间内不重复，节点本地时间需要用多个字节表示。考虑传感器节点采用16 MHz外部晶振，在不分频的情况下，为保证节点时间在15 h内不重复，节点时间需要用4个字节的系统时间和2个字节的计数器信息组成。节点在一次同步过程后需要进行再同步。一方面是因为节点需要计算时钟频偏以提高同步精度。洪泛时间同步协议通过短时间内发送多次时间消息来提高同步精度并利用多个同步点来计算时钟频偏。在文献[14]所进行的实验中，这一再同步时间为10 ms，通常，这类时间为百毫秒级别。另一方面是因为节点在同步过程中会不可避免的引入同步误差。由于传感器网络的无线链路不稳定性，传感器节点计算得出的时钟相偏和时钟频偏总是会有误差。随着时间的积累，时钟频偏误差会导致时钟相偏逐步递增。相比于节点可代表的最大时间，传感器再同步周期往往比较短。在2次同步过程中，系统时间的高位字节有极大概率保持不变，如果每次同步过程都发送完整的时间信息，就会造成数据的浪费。

变长帧时间同步的帧结构设计原则是减少同步帧数据通信量，在保证时间信息的完整性、准确性的前提下尽量减少冗余时间的发送。父节点发送同步帧之前首先对时间信息进行判断，如果高位字节时间信息没有发生改变，则只发送低位字节时间信息。时间同步帧可以分为完整同步帧和短同步帧。变长帧时间同步旨在找出合理的短同步帧字节数，在保证同步精度的前提下，降低时间同步开销。

传感器节点晶振为计数器和定时器提供服务，用参数f代表传感器节点晶振频率。假设定时器和计数器采用的是外部晶振N倍分频，则定时器和计数器的一个计数代表时间N/f。用Ts代表节点的系统时间，则完整同步帧中数据区所需字节数为：

由式(3)计算得出短同步帧时间信息所需要的最少比特数bmin，则短同步帧时间信息所需字节数为：

因此，变长帧时间同步能够减少全网时间同步的数据通信量。

假设父节点为P，子节点为B。完整同步帧数据区除去低LB字节外的高位字节用HB表示。变长帧时间同步过程如下：(1)P发送完整同步帧，并存储HB；(2)B收到完整同步帧后存储HB，并进行同步；(3)P判断比较当前时间的高HB个字节和存储时间信息。如果两者相等，则P只发送LB段，反之，P执行步骤(1)；(4)若B只收到LB段，则认为HB段没有改变。B利用存储信息HB与接收到的LB组合成完整同步帧，并进行同步。

接收节点B伪代码如下：

5 收敛时间分析

对全网络同步的收敛时间进行分析，可得到以下定理：

定理 变长帧时间同步能够减少全网同步收敛时间。

用C代表传感器节点的信道容量，k代表节点对信道容量的利用率，该值与传感器网络采用的MAC层协议相关。进一步假设传感器节点均匀分布，ρ代表网络中节点分布的密度，R为节点通信半径，则节点i的吞吐量可以表示为：，用N代表节点同步帧字节数，发送一个完整的同步帧的时间为Ti=N/Si。从root节点到普通节点的最大跳数为Hopmax，那么实现全网时间同步的收敛时间可以表示为：

6 同步维护

在同步过程中，完整帧是非常重要的。一个完整同步帧的丢失会对后续所有短同步帧的精度产生影响。针对这种特殊情况，需要进行同步维护。由上文分析可知，2个完整同步帧之间的短帧个数最少为16。由于时间的累加性，短同步帧所代表的的数值会不断递增。如果任一完整帧丢失，在信道条件不是特别差的前提下，其后续第一个短帧的数值必然小于完整帧之前的短帧数值。此时，被同步节点判断异常，得知完整帧丢失。被同步节点发送完整同步帧请求。接收到该请求帧后，同步节点将完整时间同步帧重新发送给被同步节点。

7 实验与结果分析

本文在传感器节点上实现变长帧同步算法，并对其同步精度和数据通信量进行统计。传感器节点主控芯片采用德州仪器公司处理器MSP430F5438，芯片计数器和定时器使用频率16 MHz的外部晶振，最大时间精度为0.0625 μs；低功耗射频芯片采用德州仪器公司CC1100E，节点通信频率设定为470 MHz，通信速率设定为100 KBaud；为适应节点可移动性，传感器的供电系统为4.5 V充电锂电池。此外，传感器节点可提供多种外部接口：RS232串口，JTAG仿真接口，LED灯等。

实验在3种不同配置条件下完成。变长帧同步设计目标是对现有时间同步协议的同步帧进行压缩。为验证变长帧同步的数据通信量，实验将变长帧时间同步与现有同步模型融合后进行测试。

(1)基于变长帧同步的发送者-接收者同步模型单跳实验

实验采用3个传感器节点，分别为发送节点P、接收节点B和参考节点S。根据上文所述，为保证节点时间短时间内不发生重复，需要用6个字节代表系统时间。传感器节点再同步时间设定为为7 s，由式(4)可知，短同步帧中代表系统时间的字节数为4。发送节点P向接收节点B发送同步信息，节点B收到该同步信息后对本地时间进行调整，参考节点S侦听该同步过程并记录同步帧长，侦听到一次完整的同步过程后S发送查询帧。节点P和节点B收到查询帧后立即记录各自本地时间，并依次向参考节点汇报该时间。参考节点通过RS232串口线将同步帧数量、同步帧长及接收到的时间信息传送给PC。

实验采集100个同步数据点，节点的同步误差如图3所示。其中，节点误差的最大绝对值为0.9362μs，同步精度与发送者-接收者同步模型符合。100个同步数据点产生3个完整同步帧、97个短同步帧。由图2可知完整同步帧长为9个字节，短同步帧包含7个字节。变长帧时间同步效率η≈ 0.2156。

图3 基于变长帧的发送者-接收者同步单跳实验结果

(2)基于变长帧同步的发送者-接收者同步模型4跳实验

实验采用6个节点实现，节点同步时间传递方向为P1->P2->P3->P4->P5，每个节点只能与其邻居节点进行通信。P1为root节点具有准确的时间信息，P1采用变长帧时间同步结合发送者-接收者同步模型来同步节点P2，P2以相同方式同步节点P3，该过程持续直到P5被同步。实验利用超级节点S来侦听、统计所有节点的同步信息，S在侦听到一个完整的同步过程后广播查询帧，侦听到查询帧后节点P1、P2、P3、P4、P5记录本地时间并依次发送给节点S。S将同步帧数量、短同步帧数量、节点时间信息通过串口线传递给PC。

实验采集200个同步数据点，从图4可以看出变长帧同步能够与发送者-接收者同步很好地结合。变长帧发送者-接收者同步精度与普通发送者-接收者同步模型相同，都表现出了节点精度随同步跳数增加的特性。PC采集到的完整同步帧个数为796，短同步帧个数为772，变长帧节省的同步数据量比例为η ≈ 0.2155。可以看出变长帧时间同步在保证发送者-接收者同步多跳同步精度的前提下，降低了同步数据通信开销。

图4 基于变长帧的发送者-接收者同步4跳实验结果

(3)基于变长帧同步的接收者-接收者同步模型8跳实验

实验采用10个节点实现，同步信息传递方向为P1->P2->P3->P4->P5->P6->P7->P8->P9。每一对节点的同步都需要超级节点S的辅助，S广播参考信息，侦听到该信息后节点P1、P2各自记录本地时间，节点P1将本地时间记录发送给节点P2，P2利用2个时间记录实现与节点P1的同步，S再次发送参考信息，P2与P3以相同方式实现同步，该过程持续直到节点P9被同步。之后S广播查询帧，侦听到该信息后节点P1、P3、P5、P7、P9记录本地时间并发送给节点S。在整个同步过程中，节点S侦听同步信息并统计帧大小，S将该信息和节点时间信息发送给PC。

基于变长帧的接收者-接收者同步8跳同步符合接收者-接收者同步模型同步特性。图5显示，虽然接收者-接收者同步的最大同步精度低于发送者-接收者同步模型，但是前者具有比后者更高的同步精度，接收者-接收者同步模型在置信度为0.9时同步精度为1.0417 μs，优于置信度为0.9时发送者-接收者同步模型的同步精度1.3815 μs，考虑到接收者-接收者同步模型同步跳数为8，可知该模型同步精度大于发送者-接收者同步模型。PC采集到同步帧个数为1600，短帧个数为1552，参考信息帧个数为1600。每次同步过程中都需要参考信息，参考信息不包含图2中数据区部分，其帧长为3 Byte。在考虑参考信息的前提下，基于变长帧的接收者-接收者同步模型同步效率 η≈ 0.1617；如果只考虑包含时间信息的同步帧，则其同步效率为η≈ 0.2156。

图5 基于变长帧的接收者-接收者同步8跳实验结果

从以上3个实验可以看出，变长帧时间同步能够应用于当前所有同步协议，因为其本质为针对时间同步的特性来压缩通信数据量。

8 结束语

本文提出适用于无线传感器网络的变长帧时间同步算法。分析研究表明，无线通信是传感网能量开销的主要部分，传感网全网同步的收敛时间与同步负载大小成正比。变长帧时间同步协议采用存储、压缩技术，将无线通信负载压缩并转化为节点存储问题，可有效减少平均同步帧长，为设计能量高效和快速收敛的传感网提供帮助。发送者-接收者同步单跳、发送者-接收者同步4跳和接收者-接收者同步8跳实验结果表明，该算法可有效减少同步帧平均负载，并很好的与现有协议融合，对协议精度和特性没有影响。但本文提出的数据帧都是应用在自定义的传感器网络中，更进一步的研究需要结合Zigbee 802.15.4来开展。此外，当前变长帧时间同步也需要结合现有同步模型实现。因此，下一步工作是提出更符合变长帧同步算法的时间模型，在降低同步数据量的基础上进一步提升同步精度。

[1]Maróti M,Kusy B,Simon G,et al.The Flooding Time Synchronization Protocol[C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.Baltimore,USA:ACM Press,2004:39-49.

[2]Ping S.Delay Measurement Time Synchronization for Wireless Sensor Networks[R].Berkeley,USA:Intel Research Berkeley Lab,Technical Report:IRB-TR-03-013,2003.

[3]孙德云,沈 杰,刘海涛.基于扩散机制的无线传感器网络时间同步协议[J].通信学报,2008,29(11):40-49.

[4]van Greunen J,Rabaey J.Lightweight Time Synchronization for Sensor Networks[C]//Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications.San Diego,USA:ACM Press,2003:11-19.

[5]Ganeriwal S,Kumar R,Srivastava M B.Timing-sync Protocol for Sensor Networks[C]//Proceedings of the 1st ACM Conference on Embedded Networked Sensor System.Los Angeles,USA:ACM Press,2003:138-149.

[6]Sichitiu M L,Veerarittiphan C.Simple,Accurate Time Synchronization for Wireless Sensor Networks[C]//Proceedings of Wireless Communications and Networking.Louisiana,USA:IEEE Press,2003:1266-1273.

[7]皇甫伟,周新运,陈灿峰.基于多层抽样反馈的传感器网络时间同步算法[J].通信学报,2009,30(3):59-65.

[8]Elson J E,Girod L,Estrin D.Fine-grained Network Time Synchronization Using Reference Broadcasts[C]//Proceedings of the 5th Symposium on Operating Systems Design and Implementation.Boston,USA:USENIX,2002:147-163.

[9]王义君,钱志鸿,王桂琴,等.无线传感器网络能量有效时间同步算法研究[J].电子与信息学报,2012,34(9):2174-2179.

[10]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.Berkeley,USA:ACM Press,2004.

[11]Cheng King-Yip,Lui King-Shan,Wu Yik-Chung,et al.A Distributed Multihop Time Synchronization Protocol for Wireless Sensor Networks Using Pairwise Broadcast Synchronization[J].IEEE Transactions on Wireless Communications,2009,8(4):1764-1772.

[12]Noh K L,Wu Y C,Qaraqe K,et al.Extension of Pairwise Broadcasting Clock Synchronization for Multi-cluster Sensor Networks[J].Eurasip Journal on Advances in Signal Processing:Special Issue on Distributed Signal Processing Techniques for Wireless Sensor Networks,2008,1-10.

[13]Noh K L,Serpedin E,Qaraqe K A.A New Approach for Time Synchronization in Wireless Sensor Networks:Pairwise Broadcast Synchronization[J].IEEE Transactions on Wireless Communications,2008,7(9):3318-3322.

[14]Huang Paihan,Desai M,Qiu Xiaofan,et al.On the Multihop Performance of Synchronization Mechanisms in High Propagation Delay Networks[J].IEEE Transactions on Computers,2009,58(5):577-590.