无线传感器网络同步算法的研究与探讨※＊

徐雄伟，王平，徐世武，黄晞

（福建师范大学 物理与光电信息科技学院，福州 350007）

引 言

无线传感器网络技术融合了传感器、低功耗嵌入式计算器、无线网络和通信、分布式信息处理等技术，利用传感节点通过自组网络对监测对象进行实时监测、感知和采集，在环境、资源、智能交通、矿井安全等领域都有着良好的应用前景，是近年来国内外信息领域研究和竞争的焦点。而时间同步技术是无线传感器网络中一项非常关键的基础技术。网络时间协议 NTP［1］（Network Time Protocol）是传统网络的时间同步协议，最早由美国Delaware大学的Mill教授提出。然而NTP是应传统网络的能量效率、网络动态、基础设施和系统而构建，因此并不适合低功耗、低成本、微型化、高集成、协作式多跳自组织的无线传感器网络。另外，无线传感器网络时间同步算法还要考虑能量消耗、可拓展性、精确度、鲁棒性等问题，这些都对无线传感器网络的时间同步算法提出了新的要求和挑战。

在2002年的HotNets上，J Elson和Kay Romer首次提出并阐述了无线传感器网络时间同步技术的课题，在国际上引发了广泛的关注和思考，吸引了许多大学和研究机构参与研究，已经提出许多种不同的实现算法及改进算法，典型的有RBS［2］算法、TPSN［3］算法、还有TDP［4］算法、FTSP［5］算法、DMTS［6］算法、LTS［7］算法、TS／MS［8］算法、HRTS［9］算法、OFDC［10］算法、CHTS［11］算法、CRIT［12］算法以及最新的基于萤火虫技术和协作技术的时间同步算法等。

1 概念与定义

在计算机体系结构中，时钟通常用晶体振荡器脉冲来度量，即

式中C（t）为构造的本地时钟，t为真实时间变量，k为依赖于晶振的物理特性常量，ω（τ）为晶振的频率，间隔c（t）－c（t0）被用来作为度量时间。对于理想的时钟，有r（t）＝dc（t）／dt＝1，也就是说，理想时钟的变化速率r（t）为1。但在工程实践中，因为温度、压力、电源电压等外界环境的变化，往往会导致晶振频率产生波动。因此构造理想时钟比较困难，但在一般情况下晶振频率的波动幅度并非任意的，而是局限在一定范围之内。为了方便描述与分析，定义了速率恒定模型、漂移有界模型和漂移变化有界模型。

假定c（t）是一个理想的时钟。如果在t时刻有c（t）＝ci（t），则称ci（t）在t时刻是准确的；如果dc（t）／dt＝dci（t）／dt，则称时钟ci（t）在t时刻是精确的；如果ci（t）＝ck（t），则称时钟ci（t）在t时刻与时钟ck（t）是同步的。上述定义表明，两个同步时钟不一定是准确或精确的，时间同步与时间的准确性和精度没有必然的联系。

如果采用时钟速率恒定模型，由式（1），时钟ci（t）可以简化表示为：

由此可知，时钟ci（t）和ck（t）之间应该存在如下的线性关系：

式中aik、bik为相对漂移量和相对偏移量。

2 典型同步算法

Elson、Girod和Estrin在参考文献［2］中以“第三节点”实现同步的思想提出了RBS算法，这是一种基于接收者－接收者的时间同步协议。根节点周期性地向其广播域中的子节点发送不包含时间戳的参照广播（References Broadcast）消息。接收到广播消息后，邻居子节点用自己的本地时钟记录各自的接收时刻作为参考比对时钟，然后相互交换它们记录的时间信息，这样接收节点就能知道彼此之间的时钟偏移量。然后利用式（4）计算相对其他各个节点的时钟偏移的平均值，并相应进行调整。当所有节点都获得相对其他节点的时钟偏移量平均值时，所有接收同一参照广播消息的接收节点便获得了一个相对网络时间，即：

式中：n为待同步节点数，m为参考广播的次数，Ti，k为第i个节点接收第k次参考广播的本地时刻。显然，由offset（i，j）形成的矩阵为对称矩阵，且对角线元素为0。

TPSN算法是由Ganeriwal等人提出的，是一种基于发送者和接收者的时间同步算法。采用层次型网络结构。算法分两步：首先是层次发现阶段，建立网络拓扑结构；然后每个节点与上一级的一个节点进行时间同步，最终实现所有节点都与根节点的时间同步。

FTSP协议是一种单向广播的发送者和接收者的时间同步协议。协议首先要网络动态地选择一个节点作为网络的根节点，其时间作为全网的参考时间，根节点把含有当前本地时间的信息包发送给它单跳广播域内的邻居节点；邻居节点在收到信息后分别记录相应的接收时间，采用参数拟合技术算出相对于根节点的时间漂移和时间偏移；然后这些与根节点同步了的邻居节点也作为参考节点，采用与根节点同步的相同的办法，使它们的邻居节点也实现与其同步。

无线传感器网络的最常见的几种同步算法的性能比较如表1所列。

表1 几种常用时间同步算法的性能比较

3 萤火虫同步算法和梯度同步算法

前面的时间同步技术都是基于时间信息交换的同步技术，然而在大规模的无线传感器网络中，存在同步误差会随着跳距而积累的问题和可拓展性需求等问题。萤火虫同步技术和协作同步技术是为了实现节点的同步性，即使节点的某些周期性动作具有相同的周期和相位，例如使一群萤火虫同步闪烁并且闪烁周期相同。1990年，Mirollo和Strogatz在Peskin模型的基础上提出了更一般的脉冲耦合振荡器模型（后简称为M＆S模型）。在此模型中，振荡器使用状态变量x来描述，x的变化服从函数f（φ），其中f是一个［0，1］到［0，1］的光滑单调递增上凸函数，φ是相位变量且满足（T是同步周期）。Mirollo和Strogatz从理论上证明了在M＆S模型下，多个耦合振荡器系统在几乎所有的初始情况下都能够达到同步，并在无线多跳网络测试床Gains上实现了M＆S模型的萤火虫同步算法。

麻省理工学院的Rui Fan、Nancy Lynch两位作者第一次提出了GCS梯度同步算法。在移动自组织网络中往往是邻居节点联系比较密切，而相距较远的节点很少交换消息，因此相距较远的节点可以允许较大误差。如数据融合中，具有相同父节点的子节点需要精确的同步，但是较远的节点不是同一个父节点，可以允许误差大一些。作者就是根据这一特征提出了梯度同步算法。在通常的时间同步算法的基础上，假设两任意节点i、j，f（dij）为节点i和节点j之间的最大时钟差，时钟记为Lai（t）。信息从节点i

计算出时钟漂移的最低边界满足f（D）＝Ω（d＋lgD／lg lgD），这也就是说节点之间的时钟漂移不只与两个节点间的距离有关，还与整个网络的规模有关，越近的节点同步效果越好，反之越差。GTSP（Gradient Time Synchronization Protocol）协议中，每个节点通过接收邻居节点的时间来修正自己的时钟，整个网络无需建立一个拓扑树结构，也无需参考节点，主要是实现直接的邻居节点间直接的高精度的同步，同时考虑时间漂移和偏移补偿，漂移补偿采用式（5）。通过这种补偿机制，所有节点的逻辑漂移将趋近值Xss；时钟偏移补偿采用式（6）。协议的作者在Mica2节点上进行了仿真，通过20个节点实验，采用Mac层时间戳技术，得出邻居节点之间的平均同步精度达到4.0μs，整个网络的平均同步精度达到14.0μs。传到j的传播时间为0到dij，dij为节点i到节点j的距离。D＝maxijdij，为网络的直径。GCS提出了两要求：

4 分布式时隙同步算法

主从同步方法是网络中所有的节点与参考节点保持时间同步，对参考节点依赖性高，且同步的误差随着跳数而累积；分布式同步则利用网络中所有节点的彼此时间信息进行调整，不依赖任何特殊的节点，且不会有误差的累积，因此更加适合于大型的多跳自组织的无线传感器网络。分布式时隙同步算法利用了网络中邻居节点的时隙偏差值来计算时隙的调整量，实验证明该算法收敛速度快，平均每个节点的计算量小，非常适合于移动自组网的无线传感器网络终端节点的运行。采用固定的时隙调整时，根据节点间时隙基准是超前还是滞后来调整时隙基准。基于分布式一致的无线传感器网络的时间同步协议的收敛和加速问题研究中，将分布式一致的收敛和加速问题映射到马尔科夫链的状态转移过程，但是排除了连通度对收敛速度的影响，得出收敛速度与节点邻居数和网络规模有关的结论，并通过100个节点组网实验得出了可以降低25%的迭代数的结论。

假设网内任意节点i，对应其所有的邻居节点的时隙差值为Δtij，可以算出所有邻居节点的时隙偏差值的加权平均值为εi，时隙修正量ωij。节点互同步过程如图1所示，假设节点5能感知其邻居节点（节点3、节点6、节点9）的参考时隙偏差 Δt53（n）、Δt56和 Δt59（n），从而计算出自己的时隙调整量：

式中ω55＋ω53＋ω56＋ω59＝1，然后计算出参考的时隙基准：

即可根据和邻居节点的时隙偏差，选择合适的时隙修正量使全网时间同步。为了理论分析，可以认为时间基准偏差εi是该节点i与全网所有节点时隙偏差的加权平均值，不连通节点的权值为0，即，式中N为网络的节点数。一种可行的权值选择方法是采用邻居节点的算术平均法，把相邻的节点的时隙偏差算术平均后作为时隙的修正量。对此算法的收敛性的仿真分析得出，随着节点覆盖半径的提高，每个节点的连通度增大，网络的最大跳数变少，因而收敛速度提高。算法平均迭代38次可以达到最大时隙偏差收敛到10－6以下。

5 总结及展望

本文从时间同步的概念出发，首先简要介绍了几种典型的时间同步算法及分析了他们的优缺点，并对它们的时间同步算法的性能进行了综合比较，然后还介绍了与传统基于时间信息交换的时间同步算法不同的两种新技术：萤火虫同步技术和协作同步技术。虽然目前对于无线传感器网络时间同步算法的研究已经取得了如此大的进展，但是基于无线传感器网络的不同的应用特征，还可以在以下几个方面作进一步的研究和发展：

①大规模无限传感节点的时间同步研究。现有的大部分时间同步算法都是在实验室平台，是基于几个或小规模的单跳网络节点的仿真和研究。而现实中，随着传感器节点的低成本、微型化，及实际中的应用，大规模的多跳的无线自组网的传感器网络的研究将是今后研究的方向之一。

②鲁棒性和容错性的研究。现有的时间同步算法基本上都是在实验室或较简单的室外环境下实现的，和实际的不可预测的、恶劣的真实环境相比，存在更多的干扰因素，因此时间同步算法在现实中的鲁棒性和容错性的研究也将是今后的研究方向之一。

③可拓展性的研究。无线传感器网络节点的生产商很多，网络中一般会包含大量的不同类型的移动传感器节点，时间同步算法要相互兼容就需要很好的可拓展性，因此时间同步算法的可拓展性也值得进一步研究。

无线传感器网络是与实际应用相关的，不同的应用需要不同的时间同步精度和能耗要求，因此对时间同步的需求也是多种多样的，应该结合特定的实际应用来研究和开发时间同步算法。

编者注：本文为期刊缩略版，全文见本刊网站www.mesnet.com.cn。

［1］David L Mills.RFC 1305－Network Time Protocol（Version 3）Specification.Implementation，1992.

［2］J Elson，L Girod，D Estrin.Fine－Grained Network Time Synchronization using Reference Broadcasts［C］／／Pro.5th Symp.Op.Sys.Design and Implementation.Boston，MA，2002.

［3］S Ganeriwal，R Kumar，M B Srivastava.Timing－sync Protocol for Sensor Networks［C］／／Proceedings of the 1st International Conference Embedded Networked Sensor Systems（SenSys's03）.USA：ACM press，2003.

［4］Weilian Su，Ian F Akyildiz.Time－Diffusion Synchronization Protocol for Wireless Sensor Networks［J］.IEEE／ACM Transactions on networking，2005，13（2）.

［5］M Maroti，B Kusy，G Simon，et al.The flooding time synchronization protocol［C］／／Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems（Sen－Sys’04），USA，November，2004.

［6］Intel Research.Delay measurement time synchronization for wireless sensor networks，2003.

［7］J V Greunen，J Rabaey.Lightweight time synchronization for sensor networks［C］／／The 2nd ACM Int'l Workshop on Wireless Sensor Networks and Applications，San Diego，2003.

［8］Sichitiu M L，Veerarittiphan C.Simple，accurate time synchronization for wireless sensor networks［J］.IEEE Trans.on wireless communication and networking，2003（3）.

［9］H Dai，R Han.TSync：A Lightweight Bidirectional Time Synchronization Service for Wireless Sensor Networks［C］／／ACM SIGMOBILE Mobile Computing and Communications Review，Special Issue on Wireless PAN ＆Sensor Networks，University of Colorado，January 2004.

［10］王世军，徐朝农，徐勇军，等.同步精度稳定的多跳无线传感器网络时间同步算法［J］.计算机应用，2007（27）.

［11］Hyunhak Kim，Daeyoung Kim，Seong－eun Yoo.Clusterbased hierarchical time synchronization for multi－hop wireless sensor networks［C］／／Advanced Information Networking and Applications，2006.AINA 2006.20th International Conference，April 2006，2：5.

［12］S.Kee－Young ，K.Y.Lee，K.Lee.CRIT：A Hierarchical Chained－Ripple Time Synchronization in Wireless Sensor Networks［C］／／Networking，Sensing and Control，2006.ICNSC 06.Proceedings of the 2006IEEE International Conference，April 2006：797－802.