同步技术.doc

无线传感器网络同步技术

专业：信号与信息处理
姓名：魏菊锦
学号：2013361

摘要

时间同步技术是无线传感器网络中非常重要的协议之一, 也是其他协议可靠运行的前提条件, 近年来也有相当多的同步机制被提出来, 在大规模的无线传感器网络中, 单跳同步误差的累加, 时钟偏移与漂移同时补偿, 同步机制的拓扑性能, 同步收敛速度等是目前同步机制研究过程中的主要挑战, 传统的集中式同步机制无法满足大规模无线传感器网络的性能要求,研究者们也提出了梯度同步机制, 协作同步机制, 以及分步式同步机制等来应对这些挑战。本文详细的分析了这些同步机制, 并探讨了未来可能的发展方向。

关键词：无线传感器网络 集中式同步 分布式同步 协作同步 梯度同步

引言

无线传感器网络是新兴的下一代传感器网络，这种集成了传感器技术、微机电系统(MEMS)、网络技术、嵌人式计算机技术、分布式信息处理技术和无线通信技术等于一体的新型信息获取和处理技术，在国防军事、国家安全、环境监测、交通管理、医疗卫生、制造自动化、物流及资产管理、智能家居、反恐救灾、灾害预测、智能城市建设等领域显现出良好的应用前景，成为当前国际国内学术界和工业界的一个研究热点。
从报道的研究成果来看，无论是国际还是国内，这一领域的研究目前仍然处在基础阶段，大量挑战性的课题有待于进一步深人研究．该领域的一些关键问题和核心技术，如节能、网络可扩展性、数据管
理、查询与处理、协同信号处理、信息融合、网络层协议、仿真环境、传感器描述语言、网络时钟同步与节点定位等，还需要深入研究来加以解决+对于无线传感器网络这样一个新的领域，相关领域的一些已有技术，如传统的网络时钟同步机制、嵌入式操作系统、基于Internet的网络协议栈及路由算法、蓝牙技术等，都不能很好地直接加以应用，需要对它们进行改进甚至提出新的替代技术。

1 时间同步技术
1.1时间同步的概述
时间同步是所有分布式系统都要解决的一个重要问题。在集中式系统中，由于任何进程或模块都可以从系统唯一的全局时钟中获取时间，因此系统内任何两个事件都有着明确的先后关系。而在分布式系统中，由于物理上的分散性，系统无法为彼此间相互独立的模块提供一个统一的全局时钟，必须由各个进程或模块各自维护它们的本地时钟。由于这些本地时钟的计时速率、运行环境存在不一致性，因此即使所有的本地时钟在某一时刻都被校准，一段时间后，这些本地时钟间也会出现失步。为了让这些本地时钟再次达到相同的时间值，必须进行时间同步操作。时间同步就是通过对本地时钟的某些操作，达到为分布式系统提供一个统一时间标度的过程。
无线传感器网络是联系物理世界和计算机系统的桥梁，对物理世界的观测必须建立在统一的时间标度上，因此相对于通常的分布式系统，无线传感器网络对时间同步的需求尤为重要，可以说时间同步是无线传感器网络的一项支撑技术。
1.2时间同步不确定因素
目前大部分作者都把无线传感器网络中时间同步不确定性的主要的影响因素归结为以下几个因素, 如图1所示。
图1 报文传输延迟
( 1)发送时间: 发送方用于构造分组并将分组转交给发送方的MAC 层的时间。主要取决于时间同步程序的操作系统调用时间和处理器负载等。
( 2)访问时间: 分组到达MAC 层后, 获取信道发送权的时间。主要取决于共享信道的竞争, 当前的负载等。
( 3)传送时间: 发送分组的时间, 主要取决于报文的长度等。
( 4)传播时间: 分组离开发送方后, 并将分组传输到接收方之间的无线传输时间。主要取决于传输介质、传输距离等。
( 5)接收时间: 接收端接收到分组, 并将分组传送到MAC 层所需的时间。
( 6)接受时间: 处理接收到分组的时间。主要受到操作系统的影响。

1.3时间同步问题特点
时间同步是所有分布式系统都需要解决的问题，因此对其研究已经较为深入，有许多成熟的方法被成功地应用于解决这一问题，有代表性的解决方法有NTP1和GPS2。
NTP协议[1]是目前互联网上时间同步协议的标准，用于把互联网上计算机的时间同步于世界标准时间（UTC3）。NTP采用层状结构的同步拓扑，每一层均有若干时间服务器，如顶层时间服务器，第二层时间服务器等，其他均为客户机。顶层时间服务器通过广播、卫星等方式与世界标准时间同步；其他层的时间服务器可选择若干个上一层时间服务器及本层时间服务器作为同步源来实现与世界标准时间的间接同步；客户机则可通过指定一个或多个上一层时间服务器来实现与世界标准时间的同步。可以看出：NTP协议的可靠性依赖于时间服务器的冗余性和时间获取路径的多样性。
GPS是由美国国防部为满足军事部门对海陆空设施进行高精度导航和定位的需要而建立的。它由三部分构成，分别为空间星座部分、地面监控部分和用户设备部分。空间部分是由若干颗GPS 工作卫星所组成的，每颗卫星装置有精密的铷、铯原子钟，并由监控站经常进行校准，达到和世界标准时间的同步。每颗卫星不断发射包含其位置和精确到十亿分之一秒的时间的数字无线电信号用于接收设备的时间校准。GPS 接收装置接收到来自于四颗或四颗以上卫星的信号，根据伪距测量定位方法不仅可以计算出其在地球上的位置，而且也可计算出GPS 接收机时间与世界标准时间之偏差，并进行时间校准，达到与世界标准时间的同步。这种方法的同步精度可达100 纳秒。

NTP 和GPS 尽管在技术上已经很成熟，但是却无法直接应用于无线传感器网络的时间同步，这是由于无线传感器网络具有其自身的特点，必须考虑以下因素：
(1). 传输延迟的不确定性
报文传输延迟的不确定性是无线传感器网络时间同步的主要挑战之一。一方面传输延迟比要求的时间同步允许的误差大得多，另一方面它极易受到处理器负载、网络负载等因素的影响。通常，报文的传输延迟可分为：发送前处理时间（Send time4）、排队时间（Access time5）、发送时间（Transmission time6）、传播时间（Propagation time7）、接收时间（Reception time8）、收到后处理时间（Received time9）。传输延迟的不确定性严重影响了同步精度，因此需要对传输延迟仔细地测量、分析和补偿才能设计出高精度的时间同步协议。

(2). 对低功耗、低成本与小体积的要求低功耗、低成本与小体积的要求对无线传感器网络软硬件设计的各个方面均提出挑战。 无线传感器网络强调低功耗，在设计时间同步软硬件时必须遵循该原则。例如：对用于时间同步的硬件来说，类似于GPS 接收机这样的高耗能、高成本设备是不合适的。对时间同步软件来说，虽然提高同步操作的频率能够提高同步精度，但必然引起同步功耗的增加，因此完全依靠提高同步操作频率来提高同步精度的方法也是不合适的。低成本和小体积更是加剧了电能供应的紧张趋势。
(3). 对可扩展性的要求
无线传感器网络时间同步协议会随着网络规模的扩大而出现同步精度劣化现象，即同步误差随着网络规模的扩大而增长，并最终导致同步误差越界。网络规模的扩大还会引起时间同步协议其他方面性能的下降，甚至不能正常工作。如何设计时间同步协议，使得其在大规模网络中不仅能正常工作，而且能保持较好的性能，即具有强的可扩展性。这是大规模无线传感器网络时间同步需要考虑的主要问题之一。
(4). 对健壮性的要求
在互联网环境下，尽管 NTP 协议有时会遇到短暂的链路失败，但仍然能正常工作。这是因为NTP 协议被手动配置了多个时间服务器，因此具有较强的健壮性。在无线传感器网络中，节点的移动、故障及外界环境的变化等多种因素都会导致无线传感器网络的高度动态性。静态配置方案并不能应对网络的高度动态性。时间同步协议必须能够对这些情况进行处理，以保证系统的健壮性。

2 典型无线传感器网络时间同步算法
2.1 用于传感器网络的时间同步协议（TPSN）

最易于想到的同步方法为：发送者在同步报文中嵌入其本地时间，在接收到该报文后，接收者立即把自己的本地时间设置为嵌在该报文中的时间。但这种方法没有考虑到报文的传输延迟。而延迟测量时间同步协议（DMTS，Delay Measurement Time Synchronization）在此方法的基础上，进一步考虑了报文的传输延迟，接收者测量报文的传输延迟，并将本地时间设置为发送时刻加上报文传输延迟。
延迟测量时间同步协议简单，但同步精度不高。美国加州大学洛杉矶分校（UCLA）联网和嵌入式系统实验室（NESL, Networked and Embedded Systems）的甘纳瑞沃尔（S.Ganeriwal）指出[3]：传统的发送者-接收者同步协议的同步精度较低的根源在于基于单向报文所估算出的报文传播延迟不够精确。如果采用双向报文，基于报文传输的对称性，有可能精确地计算出报文的传输延迟，因此能获得更高的同步精度。为此，他引入了NTP协议中的双向报文交换协议（如图1所示），提出了用于传感器网络的时间同步协议。

图1 NTP协议的双向报文交换

图中的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。
用于传感器网络的时间同步协议将NTP时间同步方法引入无线传感器网络，可以获得比使用延迟测量时间同步协议更高的精度，但是其计算较为复杂，功耗较大，并且同步精度受到报文的传输延迟的影响；同时如果报文的双向传输不对称，同步精度也会受到影响。

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

2.3 参考广播时钟同步协议（RBS）
用于传感器网络的时间同步协议可以看作是NTP在无线传感器网络上的改进版本，而无线传感器网络的数据传播介质是无线信道，能否利用无线信道的广播特性设计相关的时间同步算法呢？参考广播时钟同步协议所依据的就是这样的算法[5]。
与用于传感器网络的时间同步协议不同，参考广播时钟同步协议不是去同步报文的收发双方，而是去同步报文的多个接收者。如图2的右图所示：在由3个节点组成的单跳网络中，参考节点每发出一个参考报文，其广播域内的其他接收者节点都将接收到该报文，并各自记录下接收到该参考报文时的本地时刻。接收者们交换它们记录的时刻并计算差值，该差值就是接收者之间的时钟偏移。

图2 发送者-接收者同步机制与接收者-接收者同步机制

根据偏移信息可以实现发送者-接收者同步，若能精确地估计出报文传输延迟，这种方法将能够取得很高的精度。然而仅根据单个报文的传输很难准确地估计出传输延迟。图2的左图为发送者-接收者同步机制。可以看出，发送者-接收者同步机制的同步关键路径为从发送方到接收方。关键路径过长，导致传输延迟不确定性的增加，因此同步精度不可能很高。右图则是接收者-接收者同步机制，其关键路径大为缩短，完全排除了发送时间和访问时间的影响。

总结与展望

本文介绍了无线传感器网络时间同步的特点以及一些时间同步算法。不同于其他网络，在无线传感器网络中，时间同步不仅要关注同步精度，还需要关注同步能耗、可扩展性和健壮性需求。典型的时间同步协议侧重于同步精度和同步能耗的需求，采用时钟飘移补偿、介质访问控制（MAC）层时间戳技术以及双向报文交换来提高同步精度，充分利用无线传输的广播特性和捎带技术来降低同步能耗。本文介绍的这些算法很多都已经很成熟，在单跳网络中已经具有很强的工程实用性。同步误差在Mica2平台上已经达到几微秒至十几微秒的量级，同步功耗也较低，能够满足大多数应用场合的需要。然而，当这些时间同步协议被扩展到多跳网络时，会出现累计误差较大、扩展性较差等问题。
时间同步是无线传感器网络的基础性中间件，其特性直接决定或影响着其他中间件或应用的质量与特性。提高同步精度、降低同步能耗、提高可扩展性及健壮性是无线传感器网络时间同步下一步的研究方向。

参考文献

[1]李哲涛, 李仁发, 魏叶华􀀁 无线传感器网络中时间同步与测距协同算法[ J] 􀀁 计算机研究与发展􀀁2010, 47( 4): 638- 644
[ 2] 徐朝农, 徐勇军, 李晓维􀀁 无线传感器网络时间同步新技术[ J] 􀀁 计算机研究与发展􀀁2008􀀁45( 1): 138- 145
[ 3]李立, 刘勇攀, 杨华中等􀀁 无线传感器网络分布式一致时间同步协议的收敛分析及加速设计[ J] 􀀁 电子与信息学报, 2010,
32( 9), 2045- 2050