无线传感器网络时间同步

第 6卷第 4期 信息技术快报 Vol.6 No.4 Information Technology Letter Jul. 2008 无线传感器网络时间同步概述 安竹林 朱冠男 徐勇军 摘要：时间同步服务是无线传感器网络要解决的一项关键问题。本文对时间同步技术进行了介绍，分析了 无线传感器网络时间同步所具有的特点。文章还介绍了几种典型的用于无线传感网络的时间同步协议并对 其优缺点做了简单比较。最后，本文对时间同步目前的研究现状进行了，并对今后的发展进行了展望。 关键词：无线传感器网络；时间同步 1 时间同步问题简述 时间同步是所有分布式系统都要解决的一个重要问题。在集中式系统中，由于任何进程 或模块都可以从系统唯一的全局时钟中获取时间，因此系统内任何两个事件都有着明确的先 后关系。而在分布式系统中，由于物理上的分散性，系统无法为彼此间相互独立的模块提供 一个统一的全局时钟，必须由各个进程或模块各自维护它们的本地时钟。由于这些本地时钟 的计时速率、运行环境存在不一致性，因此即使所有的本地时钟在某一时刻都被校准，一段 时间后，这些本地时钟间也会出现失步。为了让这些本地时钟再次达到相同的时间值，必须 进行时间同步操作。时间同步就是通过对本地时钟的某些操作，达到为分布式系统提供一个 统一时间标度的过程。 无线传感器网络是联系物理世界和计算机系统的桥梁，对物理世界的观测必须建立在统 一的时间标度上，因此相对于通常的分布式系统，无线传感器网络对时间同步的需求尤为重 要，可以说时间同步是无线传感器网络的一项支撑技术。 2 无线传感器网络时间同步问题特点 时间同步是所有分布式系统都需要解决的问题，因此对其研究已经较为深入，有许多成 熟的方法被成功地应用于解决这一问题，有代性的解决方法有NTP1和GPS2。 NTP协议[1]是目前互联网上时间同步协议的标准，用于把互联网上计算机的时间同步于 世界标准时间（UTC3）。NTP采用层状结构的同步拓扑，每一层均有若干时间服务器，如顶 层时间服务器，第二层时间服务器等，其他均为客户机。顶层时间服务器通过广播、卫星等 方式与世界标准时间同步；其他层的时间服务器可选择若干个上一层时间服务器及本层时间 服务器作为同步源来实现与世界标准时间的间接同步；客户机则可通过指定一个或多个上一 层时间服务器来实现与世界标准时间的同步。可以看出：NTP协议的可靠性依赖于时间服务 器的冗余性和时间获取路径的多样性。 GPS 是由美国国防部为满足军事部门对海陆空设施进行高精度导航和定位的需要而建 立的。它由三部分构成，分别为空间星座部分、地面监控部分和用户设备部分。空间部分是 由若干颗 GPS 工作卫星所组成的，每颗卫星装置有精密的铷、铯原子钟，并由监控站经常 进行校准，达到和世界标准时间的同步。每颗卫星不断发射包含其位置和精确到十亿分之一 1 Network time protocol，网络时间协议 2 Global Positioning System，全球定位系统 3 Coordinated Universal Time，又称协调世界时 12 无线传感器网络时间同步概述 秒的时间的数字无线电信号用于接收设备的时间校准。GPS 接收装置接收到来自于四颗或 四颗以上卫星的信号，根据伪距测量定位方法不仅可以计算出其在地球上的位置，而且也可 计算出 GPS 接收机时间与世界标准时间之偏差，并进行时间校准，达到与世界标准时间的 同步。这种方法的同步精度可达 100纳秒。 NTP和 GPS尽管在技术上已经很成熟，但是却无法直接应用于无线传感器网络的时间 同步，这是由于无线传感器网络具有其自身的特点，必须考虑以下因素： (1). 传输延迟的不确定性 报文传输延迟的不确定性是无线传感器网络时间同步的主要挑战之一。一方面传输延迟 比要求的时间同步允许的误差大得多，另一方面它极易受到处理器负载、网络负载等因素的 影响。通常，报文的传输延迟可分为：发送前处理时间（Send time4）、排队时间（Access time5）、 发送时间（Transmission time6）、传播时间（Propagation time7）、接收时间（Reception time8）、 收到后处理时间（Received time9）。传输延迟的不确定性严重影响了同步精度，因此需要对 传输延迟仔细地测量、分析和补偿才能设计出高精度的时间同步协议。 (2). 对低功耗、低成本与小体积的要求 低功耗、低成本与小体积的要求对无线传感器网络软硬件设计的各个方面均提出挑战。 无线传感器网络强调低功耗，在设计时间同步软硬件时必须遵循该原则。例如：对用于时间 同步的硬件来说，类似于 GPS 接收机这样的高耗能、高成本设备是不合适的。对时间同步 软件来说，虽然提高同步操作的频率能够提高同步精度，但必然引起同步功耗的增加，因此 完全依靠提高同步操作频率来提高同步精度的方法也是不合适的。低成本和小体积更是加剧 了电能供应的紧张趋势。 (3). 对可扩展性的要求 无线传感器网络时间同步协议会随着网络规模的扩大而出现同步精度劣化现象，即同步 误差随着网络规模的扩大而增长，并最终导致同步误差越界。网络规模的扩大还会引起时间 同步协议其他方面性能的下降，甚至不能正常工作。如何设计时间同步协议，使得其在大规 模网络中不仅能正常工作，而且能保持较好的性能，即具有强的可扩展性。这是大规模无线 传感器网络时间同步需要考虑的主要问题之一。 (4). 对健壮性的要求 在互联网环境下，尽管 NTP 协议有时会遇到短暂的链路失败，但仍然能正常工作。这 是因为 NTP 协议被手动配置了多个时间服务器，因此具有较强的健壮性。在无线传感器网 络中，节点的移动、故障及外界环境的变化等多种因素都会导致无线传感器网络的高度动态 性。静态配置并不能应对网络的高度动态性。时间同步协议必须能够对这些情况进行处 理，以保证系统的健壮性。 3 典型无线传感器网络时间同步算法 4 发送前将数据流处理成适于发射的信号流（消息的码流）所用的时间 5 等候发射信道时间 6 信号流从头至尾从发射机发射所占用的时间 7 信号在介质中从发射端传播到接收端所用的时间 8 信号流从头至尾被接收占用的时间 9 收到信号后将码流处理成应用程序所需数据流的时间 13 第 6卷第 4期 信息技术快报 Vol.6 No.4 Information Technology Letter Jul. 2008 3.1 用于传感器网络的时间同步协议（TPSN）10 最易于想到的同步方法为：发送者在同步报文中嵌入其本地时间，在接收到该报文后， 接收者立即把自己的本地时间设置为嵌在该报文中的时间。但这种方法没有考虑到报文的传 输延迟。而延迟测量时间同步协议（DMTS，Delay Measurement Time Synchronization）[2]在 此方法的基础上，进一步考虑了报文的传输延迟，接收者测量报文的传输延迟，并将本地时 间设置为发送时刻加上报文传输延迟。 延迟测量时间同步协议简单，但同步精度不高。美国 加州大学洛杉矶分校（UCLA）联网和嵌入式系统实验室 （NESL, Networked and Embedded Systems）的甘纳瑞沃 尔（S.Ganeriwal）指出[3]：传统的发送者-接收者同步协 议的同步精度较低的根源在于基于单向报文所估算出的 报文传播延迟不够精确。如果采用双向报文，基于报文 传输的对称性，有可能精确地计算出报文的传输延迟， 图1 NTP协议的双向报文交换 因此能获得更高的同步精度。为此，他引入了 NTP协议中的双向报文交换协议（如图 1 所 示），提出了用于传感器网络的时间同步协议。 图中的T1、T4用节点A的本地时间记录，T2、T3用节点B的本地时间记录。节点A向节点 B发送一个同步请求报文。节点B在接收到该报文后，记录下接收到时刻T2，并立即向节点A 返回一个同步应答报文，并把T2和该报文的发送时刻T3嵌入在报文中。当节点A接收到该报 文时，记录下接收到时刻T4。令∆为当节点A的本地时刻为T1时，节点A和B之间的时偏。由 于T1~T4时间比较短，可认为当节点A的本地时刻为T4时，其与节点B之间的时偏没有变化。 假设报文的传输延迟相同，均为d。由： dTT +∆+= 12 ， dTT +∆−= 34 可得： 2 )()( 3412 TTTT −−−=∆ ， 2 )()( 3412 TTTTd −+−= 。 因此在T4时刻，若在节点A的本地时间上增加修正量∆，就达到和节点B之间的瞬时的时 间同步。 用于传感器网络的时间同步协议将 NTP 时间同步方法引入无线传感器网络，可以获得 比使用延迟测量时间同步协议更高的精度，但是其计算较为复杂，功耗较大，并且同步精度 受到报文的传输延迟的影响；同时如果报文的双向传输不对称，同步精度也会受到影响。 3.2 轻量基于树形分布的同步算法（LTS）11 LTS同步算法[4]是一种与TPSN非常类似的算法。无线传感器网络通常只具有非常有限的 计算资源，但是其并不要求非常高的时间同步精度。针对无线传感器网络的这一特点，LTS 侧重于降低时间同步的复杂度，在有限的计算代价下获得合理的同步精度。LTS有集中式和 分布式两个版本，在集中式版本中，首先以时间参考节点为根建立生成树，然后从树根开始 逐级向叶子节点进行同步：首先根节点同步其子节点，然后这些子节点再分别同步其子节点， 10 Timing-sync Protocol for Sensor Networks 11 Lightweight Tree-based Synchronization 14 无线传感器网络时间同步概述 如此继续下去，直到全部节点都被同步。另外，为了达到最高的同步精度，要求生成树的深 度尽可能的小，文[4]给出了Distributed depth first search (DDFS)和Echo两种生成树算法。在分 布式版本中，任何节点都可以发起同步过程，不需要建立生成树，但是每个节点都必须知道 参考节点的位置，并且知道其到这些节点的路径。节点根据自己的时钟漂移确定需要同步的 时间，需要同步时，节点选择距离自己最近的一个参考节点，并向其发出同步请求，然后参 考节点向该节点的路径上的节点逐对进行同步，直到该节点被同步。LTS算法与TPSN协议 的区别在于，LTS算法中节点只与自己的父节点进行同步，其同步次数是路径长度的线性函 数，同时精度也随路径的长度线性降低，即在降低计算代价的同时降低了同步精度。 3.3 参考广播时钟同步协议（RBS）12 用于传感器网络的时间同步协议可以看作是NTP在无线传感器网络上的改进版本，而无 线传感器网络的数据传播介质是无线信道，能否利用无线信道的广播特性设计相关的时间同 步算法呢？参考广播时钟同步协议所依据的就是这样的算法[5]。 与用于传感器网络的时间同步协议不同，参考广播时钟同步协议不是去同步报文的收发 双方，而是去同步报文的多个接收者。如图 2的右图所示：在由 3个节点组成的单跳网络中， 参考节点每发出一个参考报文，其广播域内的其他接收者节点都将接收到该报文，并各自记 录下接收到该参考报文时的本地时刻。接收者们交换它们记录的时刻并计算差值，该差值就 是接收者之间的时钟偏移。 图2 发送者-接收者同步机制与接收者-接收者同步机制 根据偏移信息可以实现发送者-接收者同步，若能精确地估计出报文传输延迟，这种方 法将能够取得很高的精度。然而仅根据单个报文的传输很难准确地估计出传输延迟。图 2 的左图为发送者-接收者同步机制。可以看出，发送者-接收者同步机制的同步关键路径为从 发送方到接收方。关键路径过长，导致传输延迟不确定性的增加，因此同步精度不可能很高。 右图则是接收者-接收者同步机制，其关键路径大为缩短，完全排除了发送时间和访问时间 的影响。 3.4 层级时间同步协议（HRTS）13 基于双向报文交换的用于传感器网络的时间同步协议具有同步精度高的优点，但一次只 能同步一对节点。n个节点的单跳网络则需要n-1 次同步操作，同步功耗较大。参考广播时 钟同步协议只需要一次同步过程就可完成一个单跳网内所有节点间的同步，同步功耗降低， 当然，同步精度也相对变差。层级时间同步协议[6]是一种结合用于传感器网络的时间同步协 议和参考广播时钟同步协议思想的同步方法。图 3描述了层级时间同步的过程。假设单跳网 络有包含时间基准节点在内的 3个节点BS、n1和n2。同步步骤如下： 12 Reference Broadcast Synchronization 13 Hierarchy Referencing Time Synchronization Protocol 15 第 6卷第 4期 信息技术快报 Vol.6 No.4 Information Technology Letter Jul. 2008 步骤 1：参见图 3，时间基准节点 BS相当前面图 1中的 A节点，按照与用于传感器网 络的时间同步协议相同的同步方式，时间基准节点 BS发出一个同步请求报文，该报文随机 指定一个邻居节点（例如 n1）作为应答者节点（即对应于图 1中的 B节点）。同时 n2也记 录下该报文的接收到时刻，记为 。 '2T 步骤 2：与用于传感器网络的时间同步协议对同步方式相同，应答者节点 n1向 BS节点 发一个同步应答报文，报文中包含了 与 。 2T 3T 步骤 3：现在 BS节点已经和 n1节点进行了一次双向报文交换，按照用于传感器网络的 图3 层级时间同步协议同步过程 时间同步协议，BS 节点计算出它与 n1 节点 之间的时钟偏移∆。 步骤 4：BS节点发送一个包含 和 信 息的报文。 ∆ 2T 步骤 5：当 n1、n2 节点接收到该报文， 对于应答者节点 n1来说，只要将其本地时间 减去∆就达到与 BS 节点的瞬时同步。对于 其他节点来说，只要在其本地时间加上 ∆−− '22 TT 即可达到与 BS 节点间的瞬时同 步 层级时间同步协议充分利用了无线传输 的广播特性来进一步降低LTS协议的同步功 耗。和LTS协议不同，基本同步单元不再是广 度优先生成树的边，而是广度优先生成树14中 非叶子节点的单跳广播区域。同步次数是 广度优先生成树非叶子节点个数的线性函数，因此降低了同步功耗。但在同步精度上，层级 时间同步协议略逊于 LTS协议。 3.5 Tiny-Sync/Mini-Sync Tiny-Sync和Mini-Sync[7]是两种适用于无线传感器网络的轻量级时间同步算法。该算法 基于一个假设：传感器网络中的时钟频率恒定且线性相关。即对于时钟 、 有 1T 2T 122121 )()( btTatT += 其中a12为相对时钟漂移，b12为相对时钟 偏移。算法采用双向报文交换来估计相对时 钟漂移和相对时钟偏移，如图 4所示。 首先节点 1 向节点 2 发送一个探测数据 包，并加入发送时刻的本地时间 ；节点 2 收到该数据包后，立即返回给节点 1 一个数 据包，其中包含收到探测数据包的本地时间 oT 图4 Tiny-Sync和Mini-Sync的双向报文交换 bT ；最后，当节点 1 收到节点 2 发回的数据包时记录本地时间 。通过这三个时间戳的绝rT 14 Breadth First Spanning Tree，亦有译作“横向扩张树”的 16 无线传感器网络时间同步概述 对位置，可以得到： 1212 bTaT bo +< 1212 bTaT br +> 三个时间戳组成的三元组( , , )称作一个数据点。算法通过不断地收集这样的数据 点估计a oT bT rT 12和b12，并且随着数据点个数的增加，算法的精度不断提高。如图 5 所示，每个数 据点对应于两个约束（ , ）和（ , ）。注意到abT oT bT rT 12、b12对应的直线必定在所有的数据 点对之间，因此图中最陡的和最缓的两条虚线给出了a12、b12的上下界。并且上下界的区间 越小，精度越高。通过求解所有数据点约束下的线性问题，别可以得到最优解。但是， 这种方法太过复杂，无法在计算资源有限的无线传感器网络中实现。 通过观察可以发现，计算上下界时 并不需要所有数据点。如图 5 所示， 上下界其实只由第1、3个数据点确定。 Tiny-Sync算法就利用了这一点，而只 保存确定最优边界的 4 个约束点，因 此降低了计算复杂度。但是，这种方 法并不能总是给出最优的上下界，在 某些情况下算法可能会丢弃一些给出 最优上下界的点。Mini-Sync 是对 Tiny-Sync的扩展，其思路是防止算法 丢弃可能在未来能够给出更小的上下 界的数据点，作者给出了一个标准来 判断是否一个约束有可能会被用于计 算最优边界，而只在确认某一个约束 不会被用到的时候才将其丢弃。这样 图5 Tiny-Sync/Mini-Sync算法中数据点对时钟漂移 和时钟偏移的约束 在提高了计算复杂度的情况下保证能够找到最优解。 Tiny-Sync 和 Mini-Sync 这两个算法，非常符合无线传感器网络的要求，即所需存储空 间和计算资源非常少，同时对带宽的要求也很小。但这种算法的假设条件（传感器网络节点 时钟的漂移和偏移恒定）在低成本的传感器网络节点上是很难达到的。 4 总结与展望 本文介绍了无线传感器网络时间同步的特点以及一些时间同步算法。不同于其他网络， 在无线传感器网络中，时间同步不仅要关注同步精度，还需要关注同步能耗、可扩展性和健 壮性需求。典型的时间同步协议侧重于同步精度和同步能耗的需求，采用时钟飘移补偿、介 质访问控制（MAC）层时间戳技术以及双向报文交换来提高同步精度，充分利用无线传输 的广播特性和捎带技术来降低同步能耗。本文介绍的这些算法很多都已经很成熟，在单跳网 络中已经具有很强的工程实用性。同步误差在Mica2平台上已经达到几微秒至十几微秒的量 级，同步功耗也较低，能够满足大多数应用场合的需要。然而，当这些时间同步协议被扩展 到多跳网络时，会出现累计误差较大、扩展性较差等问题。 17 第 6卷第 4期 信息技术快报 Vol.6 No.4 Information Technology Letter Jul. 2008 时间同步是无线传感器网络的基础性中间件，其特性直接决定或影响着其他中间件或应 用的质量与特性。提高同步精度、降低同步能耗、提高可扩展性及健壮性是无线传感器网络 时间同步下一步的研究方向。 参考文献 [1] L., M.D., Network time protocol (Version3) specification, implementation and analysis. 1992, University of Delaware, DARPA Network Working Group. [2] Ping, S., Delay Measurement Time Synchronization for Wireless Sensor Networks. 2003, Intel Research. [3] Saurabh, G., K. Ram, and B.S. Mani, Timing-sync protocol for sensor networks, in Proceedings of the 1st international conference on Embedded networked sensor systems. 2003, ACM: Los Angeles, California, USA. [4] Jana van, G. and R. Jan, Lightweight time synchronization for sensor networks, in Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications. 2003, ACM: San Diego, CA, USA. [5] Jeremy, E., G. Lewis, and E. Deborah, Fine-grained network time synchronization using reference broadcasts. 2002, ACM. p. 147-163. [6] Hui, D. and H. Richard, TSync: a lightweight bidirectional time synchronization service for wireless sensor networks. 2004, ACM. p. 125-139. [7] M.L. Sichitiu, and C. Veerarittiphan. Simple, accurate time synchronization for wireless sensor networks. in Wireless Communications and Networking, 2003.. 作者简介： 安竹林： 中国科学院计算技术研究所、研究生 朱冠男： 中国科学院计算技术研究所、客座研究生 徐勇军： 中国科学院计算技术研究所、助理研究员 18