0804--安竹林无线传感器网络时间同步概述.doc

无线传感器网络时间同步概述安竹林 朱冠男 徐勇军摘要：时间同步服务是无线传感器网络要解决的一项关键问题本文对时间同步技术进行了介绍，分析了无线传感器网络时间同步所具有的特点文章还介绍了几种典型的用于无线传感网络的时间同步协议并对其优缺点做了简单比较最后，本文对时间同步目前的研究现状进行了总结，并对今后的发展进行了展望关键词：无线传感器网络；时间同步1 时间同步问题简述时间同步是所有分布式系统都要解决的一个重要问题在集中式系统中，由于任何进程或模块都可以从系统唯一的全局时钟中获取时间，因此系统内任何两个事件都有着明确的先后关系而在分布式系统中，由于物理上的分散性，系统无法为彼此间相互独立的模块提供一个统一的全局时钟，必须由各个进程或模块各自维护它们的本地时钟由于这些本地时钟的计时速率、运行环境存在不一致性，因此即使所有的本地时钟在某一时刻都被校准，一段时间后，这些本地时钟间也会出现失步为了让这些本地时钟再次达到相同的时间值，必须进行时间同步操作时间同步就是通过对本地时钟的某些操作，达到为分布式系统提供一个统一时间标度的过程无线传感器网络是联系物理世界和计算机系统的桥梁，对物理世界的观测必须建立在统一的时间标度上，因此相对于通常的分布式系统，无线传感器网络对时间同步的需求尤为重要，可以说时间同步是无线传感器网络的一项支撑技术。

2 无线传感器网络时间同步问题特点时间同步是所有分布式系统都需要解决的问题，因此对其研究已经较为深入，有许多成熟的方法被成功地应用于解决这一问题，有代表性的解决方法有NTP Network time protocol，网络时间协议和GPS Global Positioning System，全球定位系统NTP协议[1]是目前互联网上时间同步协议的标准，用于把互联网上计算机的时间同步于世界标准时间（UTC Coordinated Universal Time，又称协调世界时）NTP采用层状结构的同步拓扑，每一层均有若干时间服务器，如顶层时间服务器，第二层时间服务器等，其他均为客户机顶层时间服务器通过广播、卫星等方式与世界标准时间同步；其他层的时间服务器可选择若干个上一层时间服务器及本层时间服务器作为同步源来实现与世界标准时间的间接同步；客户机则可通过指定一个或多个上一层时间服务器来实现与世界标准时间的同步可以看出：NTP协议的可靠性依赖于时间服务器的冗余性和时间获取路径的多样性GPS是由美国国防部为满足军事部门对海陆空设施进行高精度导航和定位的需要而建立的它由三部分构成，分别为空间星座部分、地面监控部分和用户设备部分。

空间部分是由若干颗GPS 工作卫星所组成的，每颗卫星装置有精密的铷、铯原子钟，并由监控站经常进行校准，达到和推荐精选世界标准时间的同步每颗卫星不断发射包含其位置和精确到十亿分之一秒的时间的数字无线电信号用于接收设备的时间校准GPS接收装置接收到来自于四颗或四颗以上卫星的信号，根据伪距测量定位方法不仅可以计算出其在地球上的位置，而且也可计算出GPS接收机时间与世界标准时间之偏差，并进行时间校准，达到与世界标准时间的同步这种方法的同步精度可达100纳秒NTP和GPS尽管在技术上已经很成熟，但是却无法直接应用于无线传感器网络的时间同步，这是由于无线传感器网络具有其自身的特点，必须考虑以下因素：(1). 传输延迟的不确定性报文传输延迟的不确定性是无线传感器网络时间同步的主要挑战之一一方面传输延迟比要求的时间同步允许的误差大得多，另一方面它极易受到处理器负载、网络负载等因素的影响通常，报文的传输延迟可分为：发送前处理时间（Send time 发送前将数据流处理成适于发射的信号流（消息的码流）所用的时间）、排队时间（Access time 等候发射信道时间）、发送时间（Transmission time 信号流从头至尾从发射机发射所占用的时间）、传播时间（Propagation time 信号在介质中从发射端传播到接收端所用的时间）、接收时间（Reception time 信号流从头至尾被接收占用的时间）、收到后处理时间（Received time 收到信号后将码流处理成应用程序所需数据流的时间）。

传输延迟的不确定性严重影响了同步精度，因此需要对传输延迟仔细地测量、分析和补偿才能设计出高精度的时间同步协议2). 对低功耗、低成本与小体积的要求低功耗、低成本与小体积的要求对无线传感器网络软硬件设计的各个方面均提出挑战无线传感器网络强调低功耗，在设计时间同步软硬件时必须遵循该原则例如：对用于时间同步的硬件来说，类似于GPS接收机这样的高耗能、高成本设备是不合适的对时间同步软件来说，虽然提高同步操作的频率能够提高同步精度，但必然引起同步功耗的增加，因此完全依靠提高同步操作频率来提高同步精度的方法也是不合适的低成本和小体积更是加剧了电能供应的紧张趋势3). 对可扩展性的要求无线传感器网络时间同步协议会随着网络规模的扩大而出现同步精度劣化现象，即同步误差随着网络规模的扩大而增长，并最终导致同步误差越界网络规模的扩大还会引起时间同步协议其他方面性能的下降，甚至不能正常工作如何设计时间同步协议，使得其在大规模网络中不仅能正常工作，而且能保持较好的性能，即具有强的可扩展性这是大规模无线传感器网络时间同步需要考虑的主要问题之一4). 对健壮性的要求在互联网环境下，尽管NTP协议有时会遇到短暂的链路失败，但仍然能正常工作。

这是因为NTP协议被手动配置了多个时间服务器，因此具有较强的健壮性在无线传感器网络中，节点的移动、故障及外界环境的变化等多种因素都会导致无线传感器网络的高度动态性静态配置方案并不能应对网络的高度动态性时间同步协议必须能够对这些情况进行处理，以保证系统的健壮性推荐精选3 典型无线传感器网络时间同步算法3.1 用于传感器网络的时间同步协议（TPSN） Timing-sync Protocol for Sensor Networks最易于想到的同步方法为：发送者在同步报文中嵌入其本地时间，在接收到该报文后，接收者立即把自己的本地时间设置为嵌在该报文中的时间但这种方法没有考虑到报文的传输延迟而延迟测量时间同步协议（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由：，可得：，因此在T4时刻，若在节点A的本地时间上增加修正量Δ，就达到和节点B之间的瞬时的时间同步用于传感器网络的时间同步协议将NTP时间同步方法引入无线传感器网络，可以获得比使用延迟测量时间同步协议更高的精度，但是其计算较为复杂，功耗较大，并且同步精度受到报文的传输延迟的影响；同时如果报文的双向传输不对称，同步精度也会受到影响。

3.2 轻量基于树形分布的同步算法（LTS） Lightweight Tree-based SynchronizationLTS同步算法[4]是一种与TPSN非常类似的算法无线传感器网络通常只具有非常有限的计算资源，但是其并不要求非常高的时间同步精度针对无线传感器网络的这一特点，LTS侧重于降低时间同步的复杂度，在有限的计算代价下获得合理的同步精度LTS有集中式和分布式两个版本，在集中式版本中，首先以时间参考节点为根建立生成树，然后从树根开始逐级向叶子节点进行同步：首先根节点同步其子节点，然后这些子节点再分别同步其子节点，如此继续下去，直到全部节点都被同步另外，为了达到最高的同步精度，要求生成树的深度尽可能的小，文推荐精选[4]给出了Distributed depth first search (DDFS)和Echo两种生成树算法在分布式版本中，任何节点都可以发起同步过程，不需要建立生成树，但是每个节点都必须知道参考节点的位置，并且知道其到这些节点的路径节点根据自己的时钟漂移确定需要同步的时间，需要同步时，节点选择距离自己最近的一个参考节点，并向其发出同步请求，然后参考节点向该节点的路径上的节点逐对进行同步，直到该节点被同步。

LTS算法与TPSN协议的区别在于，LTS算法中节点只与自己的父节点进行同步，其同步次数是路径长度的线性函数，同时精度也随路径的长度线性降低，即在降低计算代价的同时降低了同步精度3.3 参考广播时钟同步协议（RBS） Reference Broadcast Synchronization用于传感器网络的时间同步协议可以看作是NTP在无线传感器网络上的改进版本，而无线传感器网络的数据传播介质是无线信道，能否利用无线信道的广播特性设计相关的时间同步算法呢？参考广播时钟同步协议所依据的就是这样的算法[5]与用于传感器网络的时间同步协议不同，参考广播时钟同步协议不是去同步报文的收发双方，而是去同步报文的多个接收者如图2的右图所示：在由3个节点组成的单跳网络中，参考节点每发出一个参考报文，其广播域内的其他接收者节点都将接收到该报文，并各自记录下接收到该参考报文时的本地时刻接收者们交换它们记录的时刻并计算差值，该差值就是接收者之间的时钟偏移图2 发送者-接收者同步机制与接收者-接收者同步机制根据偏移信息可以实现发送者-接收者同步，若能精确地估计出报文传输延迟，这种方法将能够取得很高的精度然而仅根据单个报文的传输很难准确地估计出传输延迟。

图2的左图为发送者-接收者同步机制可以看出，发送者-接收者同步机制的同步关键路径为从发送方到接收方关键路径过长，导致传输延迟不确定性的增加，因此同步精度不可能很高右图则是接收者-接收者同步机制，其关键路径大为缩短，完全排除了发送时间和访问时间的影响3.4 层级时间同步协议（HRTS） Hierarchy Referencing Time Synchronization Protocol推荐精选基于双向报文交换的用于传感器网络的时间同步协议具有同步精度高的优点，但一次只能同步一对节点n个节点的单跳网络则需要n-1次同步操作，同步功耗较大参考广播时钟同步协议只需要一次同步过程就可完成一个单跳网内所有节点间的同步，同步功耗降低，当然，同步精度也相对变差层级时间同步协议[6]是一种结合用于传感器网络的时间同步协议和参考广播时钟同步协议思想的同步方法图3描述了层级时间同步的过程假设单跳网络有包含时间基准节点在内的3个节点BS、n1和n2同步步骤如下：。