无线传感器网络中一种自适应时间同步算法

金 虎

（黑龙江大学 计算机科学技术学院，哈尔滨 150080）

0 引 言

大量集成了传感器、处理器、无线通信模块的节点以Ad Hoc方式构成大规模传感器网络，网络中节点协作完成数据采集、融合处理，通信发送等任务。作为分布式自治系统，无线传感器网络具有高灵活性、强鲁棒性及高智能度等优点，可被广泛应用于国防、环保、交通、医疗，以及制造业等多个领域[1]。时钟同步是无线传感器网络的一项重要支撑技术，传感器网络自身协议的运行及基于其上的应用，如：标记数据采集时间、时分多址接入、协同休眠、定位、数据融合等都需要网络中节点的时钟保持同步[2]。

目前在Internet中广泛使用的NTP同步算法同样也不适合于传感器网络应用，因其采用双向通信同步以抵消信息传输时延的影响，要求双向时延必须对称。在传感器网络中由于链路层的影响，双向时延往往不对称。而且NTP算法的工作场景是有线网络，没有针对能耗进行优化、协议复杂度高[3]。因此研究适合于传感器网络的时钟同步算法是目前国内外学术界的一个热点。通常在传感器网络中，除了非常少量的传感器节点携带如GPS的硬件时间同步部件外，绝大多数传感器节点都需要根据时间同步机制交换同步消息，与网络中的其它传感器节点保持时间同步[4]。

本文首先介绍基于层次的时间同步算法；然后介绍了能量节省的自适应时间同步算法以及相关实验数据和结论。

1 基于层次的时间同步协议

传感器网络基于层次的时间同步协议类似于传统网络的NTP时间同步协议，目的是提供传感器网络全网范围内节点间的时间同步。基于层次的时间同步协议采用层次网络结构，首先将所有节点按照层次结构进行分级，然后每个节点与上一级的一个节点进行时间同步，最终所有节点都与根节点时间同步。节点对之间的时间同步是基于发送者——接收者的同步机制[5]。

基于层次的时间同步协议假设每个传感器节点都有惟一的标识号ID，节点间的无线通信链路是双向的，通过双向的消息交换实现节点间的时间同步。基于层次的时间同步协议将整个网络内所有节点按照层次型结构，如TinyDB需要数据融合树，这样整个网络只需生成和维护一个共享的层次结构。

邻近级别的两个节点对间通过交换两个消息实现时间同步，其中节点S属于第i级节点，节点R属于第（i－1）级节点，T1和T4表示节点S本地时钟在不同时刻测量的时间，T2和T3表示节点R本地时钟在不同时刻测量的时间，Δ表示两个节点之间的时间偏差，d表示消息的传播时延，假设来回消息的延迟是相同的。节点S在T1时间发送同步请求分组节点R，分组中包含S的级别及T1时间，节点R在T2时间接收到分组，T2＝（T1＋d＋Δ），然后在T3时间发送应答分组给节点S，分组中包含节点R的级别及T1、T2和T3信息，节点S在T4时间收到应答，T4＝T3＋d－Δ，因此可以推出：

节点S在计算时间偏差后，将它的时间同步到节点R。

2 自适应时钟同步算法

基于层次的时间同步协议是周期性执行同步算法，而且同步协议的开销比较大，所以提出自适应时间同步算法，根据最近的时间偏移和时间同步周期来调整同步的时间周期的长度。可以减少同步协议的开销，进而减少节点的能量开销。同步周期选取要充分考虑无线传感器网络节点到节点传输时延的抖动，它考虑本次传输时延于前一次之间的差值，计算出一个补充值来减少抖动带来的影响。统计分析每个包的延迟，来估计最大延迟，以一个平均延迟和初试设定的比例因子计算本次的补充值。

将考虑节点到节点传输延迟抖动带来的更新周期抖动，客户端根据时间精度要求、前个历史同步周期的统计以及前m次时钟偏移量和同步周期，来选取下次时钟同步周期。

首先定义几个变量：

θ：结点的同步周期。定义为两次同步请求之间的时间间隔，θ0为下一次同步的周期，θ1，θ2，…，θm为以前的m次历史时钟周期。

t：本地时钟。t1为前一次调整时节点的本地时钟。

C：标准时钟。C1为前一次调整时所获得的标准时钟。

Δ：结点的时钟偏移。定义为结点的本地时钟和标准时钟的绝对差Δ＝abs（C－t）。

τ：系统的时钟精度。它反映了系统对时钟同步的要求，即允许的最大偏移，abs（C－t）＜τ。

Δp：预计下次同步周期时，节点所允许的时钟偏移。

而θ的取值必须符合θρ≤τ。在计算下一次同步周期时，以Δp作为预计的偏移值。在理想情况下，以周期θ0进行更新时，时钟偏移Δ0≤Δp（预计值）。

由于直接计算ρ比较复杂，可采用一个替代方法。该方法使用前m个同步的平均周期作为下次的参考周期，同时考虑最近一次的偏移情况，综合计算出下次的同步周期，即：

在预计更新周期（用上一次更新中的偏移速度为基准得到）和历史统计的平均周期之间进行权衡，计算生成本次的实际更新周期。另外，如果上一次的应答包返回的时延过长超过可信范围 [0，Tmax]，或没有收到应答包，则取μ1＝0，μ2＝1即以累计的平均周期为准。

3 应用实验

本实验在美国加州大学伯利克分校开发的TinyOS系统下进行。实验1是在最大时间偏差一定的情况下，在PC上分别模拟在5、10、15和25个节点上执行TPSN和ADTS时间同步算法。实验2在不同的最大时间偏差下，在PC上分别模拟在15个节点执行TPSN和ADTS时间同步算法。图1表示最大时间偏差为5ms时，两种时间同步算法执行50000ms（每个周期为500ms）所需的同步次数。图2表示最大时间偏差为5ms时，分别执行两种时间同步算法执行50000ms所消耗的通信能量。图3表示在15个节点上，两种时间同步算法执行50000ms所需的同步次数。图4表示在15个节点上，分别执行两种时间算法50000ms所消耗的通信能量。本实验在计算每个节点通信消耗的能量时，采用Mica2的性能参数，当无线部件工作在15mW的模式下，节点发送或接收一个数据包消耗的能量为0.4mJ。

由图1可见，TPSN同步的次数远多于ADTS，TPSN每个周期执行一次时间同步操作，而ADTS可以动态调整同步的时间周期的长度，从而减少了同步次数。由图2可见，TPSN通信消耗的能量远大于ADTS。TPSN算法不但同步次数高于ADTS算法，而且TPSN每次执行时间同步，需要交换两个消息，这增加了发送接收信息次数，从而导致更大的通信能量消耗。随着节点个数的增加，ADTS算法的优越性越明显，当节点个数为25时，ADTS算法所消耗的通信能量仅为TPSN算法的1／3。

图4 不同最大时间偏差下通信消耗能量比较Fig.4 Energy consumption of communication for varying the maximal time error

由图3，图4可见，ADTS同步次数与通信消耗的能量远小于TPSN，随着最大时间偏差的减小，即同步精度的提高，差距越明显。当最大偏差为1ms时，ADTS通信消耗的能量不足TPSN算法的1／3。

4 结 论

无线传感器网络中的时间同步是一个重要的问题，但是对于传感器网络的大部分应用来说，时间同步的精确性要求并不是特别高，而传感器节点的电能十分有限，因此同步算法在满足时间精确度的要求下，应尽量降低协议的开销。

本文的同步算法是在传感器网络内建立一个层次结构，然后从汇聚点开始，每相邻层之间的节点采用成对的节点间的同步算法进行同步，最后实现了全网络的同步。在此基础之上，我们讨论了可变时间同步周期的算法。由于传感器的节点能量有限，本文根据节点时间的偏移速度完成了一种自适应的时间同步算法，是可节省节点能量的有一定价值的算法。

[1]孙利民，李建中，陈 渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

[2]J.Elson，D.Estrin.Time synchronization for wireless sensor networks [A].In 2001International Parallel and Distributed Processing Symposium（IPDPS），Workshop on Parallel and Distributed Computing Issues in Wireless[C].2001.

[3]Jeremy Elson，Lewis Girod，Deborah Estrin.Finegrained network Time Synchronization using Reference Broadcasts [A].In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation（OSDI 2002）[C].Boston，MA，December 2002.

[4]Maroti M，Kusy B，Simon G，et al.Flooding time synchronization in wirless sensor networks [C]／／Acm SenSys’04，November 3-5，2004，Baltinore，Maryland.

[5]盖旗涛，樊小平，蔡 蒨，等.WSN时间同步算法研究 [J].电子技术，2010，（7）：5-7.