第30卷第4期 2007年4月计 算 机 学 报CHINESE JOURNAL OF COMPU TERS无线传感器网络时间同步协议的改进策略徐朝农心赵磊E徐勇军八季晓维H）（中国科学院计算技术研究所计算机系统结构重点实缀室北京100080）刀（合肥工业大学计算机与信息学院合肥230009）3）（中国科学院研究生院北京100039）摘要鉴于NTP和无线传感器网络时间同步协议的相似性，提出把NTP中的时间过滤、时间选择和时间组合算 法简化后应用于无线传感器网络时间同步协议中以提高同步精度的策略.作为例证，将时间组合算法简化后引 入B TS协议中.模拟的结果表明:在由81个Mica2节点组成的8跳网络内，除抗拒节点的同步误差保持不变外，其 余节点的同步误差减小至改进前的67170 %91158 % ；具有相同跳距的节点的平均同步误差随跳距的增加率由 1918减小至151 5/W跳伺时没有额外的报文开销.理论分析表明：同步精度的提高得益于应用时间组合算法所导 致的节点时间偏移量均方差的减小.关铤词 无线传感器网络;时间同步;网络时间协议;同步性;低功耗中图法分类号TP393A Time Synchronization Improvement Strategy for Wireless Sensor Net worksXU Chao2Nongh ,2 ZHAO Lei” ,3) XU YongZJun0 3 LI Xiao2Wei0 3)H ( Key Laboratory of Com puter A rchiieclure bisliiiue of Com puling Technology , Chinese A cade my of Sciences Bei j ing 100080) J ( School of Com puter Science and Inf ormation Technology f Hef ei University of Technology t Hef ei 230009) Graduate University of Chinese Academy of Sciences , iiei j ing 100039)Abstract Taking t he similarity between N TP (Network Time Protocol) and time synchronization protocol in WSN ( Wireless Sensor Networks) into consideration , t he aut hors propose a st rategy of ini reducing simplified algoril hms in N TP such as clock filtering , clock selection and clock com2 bining algorit hm into WSN to imp rove synchronization precision. As a proof , a simplified clock combining algorithm in N TP is introduced into B TS (Broadcast Time Synchronization) protocol. Simulation result reveals t hat in a 82hop network consist of 81 Mica2 sensor nodes , t he synchroni2 zation error of every sensor node varies f rom 671 70 % to 911 58 % of t hat in B TS , except for some resister nodes whose synchronization errors keep unchanged. For all sensor nodes with same hop distance f rom t he time beacon node, t he ratio of t heir average synchronization error to hop dis2 tance switches f rom 191 8 to 151 5/Zs per hop . Furthermore, t hese improvement s co st no extra wireless l ransmissions. Theoretical analysis shows t hat l hese improvement s are due to l he de2 crease of t he standard deviation of t he node s time off set wit h t he time beacon , which is t he result of t he applying lime combination algoril hm.Key words wireless sensor network ; time synchronization ; network time protocol ; synchronicity ; low power收稿H期:2006203227;修改稿收到日期:2006211202.本课题得到国家“八六三”高技术研究发展计划项目基金(2006AA01 Z223 , 2006AA01Z225)、国家“九七三”页点基础研究发展规划项目佥金(2005CB321604)、国家日然科学基金(90207002)资助.徐朝农，男，1975 年生，博士研究生、研究方向为无线传感器网结、嵌入式系统.E2mail: xu.chaonong icl. ac. cn.赵 磊，男，1978年生，博士研究生、研究 方向为无线传喊器网是、嵌入式系统.徐勇军，男，1979年生，博士，助理研究员，研究方向为无线传感器网络、低功耗系统.李晓维，男, 1964年生,研究员，研究领域为VL SI/ SOC测试、嵌疽系统.1引言具有传感、处理和无线通信能力的微型节点所 组成的无线传感器网络是当前的研究热点.无线传 感器网络具有广泛的应用前景，在建筑物健康监测、 精准农业、智能交通、环境监测等应用场合中显示出 了巨大的市场前景.时间同步技术是无线传感器网络的一项支撑性 技术.由于低成本、低功耗和微型ftn勺要求，目前，绝 大多数无线传感器网络节点只能采用价格低廉的晶 体振荡器作为计时设备.由于不同厂家在晶体振荡 器制造工艺上存在差别并且晶体振荡器的振荡频率 易受到电压、温度及晶体老化等多种因素的影响，使 得晶体振荡器在实际使用时的振荡频率与其标称频 率之间存在一定的差别，从而导致节点计时速率的 不一致性和不稳定性，并导致了节点计时的异步性. 时问同步机制以保持网络中各节点时问的同步运行 为目的，可广泛应用在节点定位、无线信道的时分复 用、彳晰朝廊民、路山协议、数据融合以及传感事件 排序等多种服务和应用场合回，并且时间同步的精 度直接影响了其它服务的质量.目前无线传感器网络时间同步技术的研究重点 已经从单跳网络发展到多跳网络.现有的无线传感 器网络多跳时间同步算法充分体现了同步功耗和同 步精度间的折衷，但能否在不显著增加同步功耗的 前提下提高同步精度呢？文献1 ,3 探讨了将 N TP ( Network Time Pro2 iocoD,41用于无线传感器网络的可能性.它们认为， 因特网与无线传感器网络间的巨大差异是导致 N TP不适合于无线传感器网络的主要原因.首先， 这两种网络的节点具有很大差异：同以网络服务器 为代表的因特网节点相比，以Mica2为代表的无 线传感器网络节点具有体积、电能供应、计算能力和 存储空间的严格约束，导致复杂的、高精度的NTP 协议不可能在无线传感器网络节点上运行;其次，无 线传感器网络采用无线传输方式而因特网却主要采 用可靠得多的有线传输方式，这两种传输方式在带 宽、抗干扰能力和抗衰落能力等方面具有巨大的差 别，使得NTP针对有线传输方式的特点而对参数 所做的一些工程优化并不适合于无线传输方式；再 次，无线传感器网络的应用要求算法具有强的局部 性，即达到局部最优性，而因特网则强调整体最优 性.所以，现有文献普遍认为N TP并不适合于无线 传感器网络.然而，相似性也是存在的.无线传感器网络时间 同步面临的主要挑战之一为随着网络规模的不断扩 大，节点的同步误差出现累积，最终导致同步误差越 界.因此，大多数时间同步协议把网络组织成以时间 基准节点为根的广度优先生成树，力图尽可能减小 节点的跳段数，从而减缓误差的累积.这和NTP在 同步拓扑和同步方法上是类似的.因此，NTP协议 中的一些局部优化算法完全可以应用于无线传感器 网络中.例如:时间过滤、时间选择和时间组合算法 只对节点已收集的时间信息进行处理，不需要额外 的报文传输,计算相对简单，能去除网络时延的抖 动，可较大幅度地提高同步的精度.此外，这些算法 不会带来功耗的明显增加.但这些算法需要进行合 理的简化使得其时空复杂度降低后才适合在无线传 感器网络中应用.作为主要的创新点，本文把NTP中的时间组 合算法进行简化并引入先前提出的BTS协议中. 通过在Simsync时问同步模拟器上模拟后发现: 在由81个Mica2节点组成的8跳网络范围内，除那 些与时问基准节点只有唯一路径的节点的同步误差 保持不变外，其余节点的同步误差均有不同程度的 减小，减小至未改进前的67170 %91158 %;平均 同步误差随跳距的增加率由191 8减小到151 5爵 跳，并且没有带来额外的报文传输，功耗没有明显增 加.实验结果充分说明了该改进策略的有效，性.本文第2节介绍在NTP和无线传感器网络时 间同步方面的相矣工作；第3节简介B TS协议原 理；第4节首先介绍将NTP中的时间组合算法引入 B TS协议中得到的改进型B TS协议的原理;然后给 出实验和结果分析，论证改进策略的有效性;进而进 行理论分析，指出同步精度获得提高的本质原因;第 5节为结论与展望.2相矣的工作本节介绍NTP和无线传感器网络时间同步的 研究背景.由于NTP相对成熟，因此侧重于介绍其 体系结构.随后介绍在无线传感器网络时间同步方 面的相矣工作.211网络时间协议目前.NTP31。已经在因特网上大量使用并成 为RFC21305标准，其同步精度可达毫秒级，用于 把因特网上计算机的时间同步于UTC(Coordina2ted U niversal Time)时间.N TP41 0 在 31 0 的基础 上主要加强了安全特性，目前正处于测试阶段.此 外，由于进一步优化了频率预测功能，同步精度可达 微秒级.图1为NTP的同步拓扑图，每个时间服务器都 有一个变量用于指示其在拓扑图中的层次.图中 Al ,A2 ,A3为顶层时间服务器,B1 ,B2为第二层时 问服务器，其它均为客户机.顶层时问服务器通过广 播、卫星或调击懈调器与U TC时问同步，其它层的 时问服务器则可选择若干个上一 层时问服务器或本 层时间服务器作为同步源来实现时间同步，客户机 则可通过指定一个或多个上一层时间服务器来实现 与U TC时间的同步.可以看出:N TP的可靠性依赖 于时间服务器的冗余性和时间获取路径的多样性. 这种同步拓扑存在的问题是.离顶层时间服务器越 远，同步精度将会越差.N TP的体系结构如图2所示.N TP是一个对 频率变化响应比较灵敏的n类型的锁相环路.其 中，多个同步的时间服务器从不同路径提供时间服 务