无线传感器网络时间同步综述.pdf

无线传感器网络时间同步综述.pdf

《无线传感器网络时间同步综述.pdf》由会员分享，可在线阅读，更多相关《无线传感器网络时间同步综述.pdf（4页珍藏版）》请在冰点文库上搜索。

文章编号：

16714598（2005）101021一03中图分类号：

TP301文献标识码：

A无线传感器网络时间同步综述康冠林，王福豹，段渭军（西北工业大学宽带网络与远程教育技术研究所，陕西西安710072）摘要：

时间同步是无线传感器网络技术研究的一个新热点，很多无线传感器网络应用都要求传感器节点的时钟保持同步；由于无线传感器网络自身的特点，它在同步范围、能量消耗以及同步精度上都有特殊的要求，这使传统的时间同步方法并不适合无线传感器网络，对目前典型的无线传感器网络时间同步算法进行了论述，并指出了进一步的研究方向。

关键词：

无线传感器网络；时间同步SurvevonTimeSvnchronizationforWirelessSensOrNetworksKangGuanlin，WangFubao，DuanWeijun（InstituteofBroadbandNetwork，NorthwestPolytechnicaIUniversity，Xran710072，China）Abstract：

TimesynchronizationisanewfocustopicintheresearchofwirelessSensorNetworksManyapplicationsofwSNneedclocksofsensornodestobesynchronizedHowever，TimeSynchronizationforWSNhasuniquerequirementsforscope，energyconsumptionandprecisionofsynchronizationresultfromitsowncharacteristics，makingtraditionalsynchronizationmethodsunsuitableforWSNTheexistingtypicaltimesynchronizationalgo“thmsforWSNarediscussedandpresentedindetail，andthefuturedirectionsofresearchontimesynchronizationforWSNareforecastedKeywords：

wirelesssensornetworks；timesynchronization0引言融合了传感器技术、信息处理技术和网络通信技术的无线传感器网络（wSN，wirelessSensorNetwork）由分布在物理空间上大量传感器节点通过自组织的方式构成网络，借助节点中内置的不同类型传感器探测所在周围环境中包括温度、湿度、移动目标方向和速度等众多物质现象。

传感器网络可实现数据的采集量化、处理融合和传输应用，它是信息技术的一个新兴领域，目前已应用于军事、环境监测、工业控制等领域1。

时间同步是无线传感器网络应用的重要组成部分，传感器数据融合、传感器节点自身定位等都要求节点问的时钟保持同步。

在wSN应用中，传感器节点通常需要协调操作共同完成一项复杂的传感任务。

例如在目标追踪应用中，传感器节点将传感到的运动目标的位置、时间等信息发送给传感器网络中的首领节点，首领节点在对不同传感器发来的数据进行处理后便可获得目标的移动方向、速度等信息；为了能够正确监测事件发生的次序要求传感器节点之间实现相对时间同步。

在火灾监测等应用中，事件自身的发生时间是相当重要的参数，这要求每个节点维持唯一的全局时间以实现整个网络的时间同步。

目前广泛用于网络时间同步的方法主要有GPs和NTP。

GPS33具有相当高的同步精度，但其成本较高并且能耗较大，收稿日期：

20041220；修回日期：

2005124。

基金项目：

国家自然科学基金资助项目（60472074）。

作者简介：

康冠林（1979一），男，硕士研究生，主要从事传感器网络与网络软件方向的研究；王福豹（1963一），男，博士，教授，主要从事计算机网络，流媒体，传感器网络等方面的研究；段渭军（1962一），男，博士，高工，主要从事流媒体、无线通信等方面的研究。

而且在恶劣的环境下同步精度会受到很大影响。

NTP（NetworkTimeProtoc01）是Internet上进行时钟同步的协议，它能实现网络上高精度的计算机校时，但它是计算密集型的，具有很大的计算开销4。

在wSN应用中，传感器节点对功耗有严格的要求，并且要求尽可能保持较小的外形和低廉的成本使其能够被大量部署，其部署环境经常是常人难以接近的恶劣环境，这使得部署后的维护通常是不可能的；显然将GPs和NTP用于wSN的时间同步是不可取的。

分布式系统中对时间同步也有大量研究5“，但这些方法都没有考虑传感器网络的特点，需要较大的资源开销，所以不适合wsN的时间同步。

1消息传递过程分解将消息在wSN节点间传递的过程分解成不同的阶段是对wSN时间同步问题研究的关键，一条消息在wSN节点间的传递过程可分解成如下六个部分。

（1）SendTime：

发送节点构造一条消息所需要的时间，包括内核协议处理和缓冲时间等，它取决于系统调用开销和处理器当前负载。

（2）AccessTime：

消息等待传输信道空闲所需时间，即从等待信道空闲到消息发送开始时的延迟，它取决于网络当前负载状况。

（3）TransmissionTime：

发送节点按位（bit）发射消息需时间，该时间取决于消息长度和发射速率。

（4）PropagationTime：

消息在两个节点之间传输介质中的传播时间，该时间主要取决于节点间的距离（电磁波在空气中的传播速率是一定的）。

（5）ReceptionTime：

接收节点按位（bit）接收消息并传递给MAC层的时间，这个过程和（3）相对应。

（6）ReceiveTime：

接收节点重新组装消息并传递给上层应用所需的时间。

万方数据1022计算机测量与控制第10期2无线传感器网络时间同步算法我们根据一对节点间同步的不同实现机制将目前提出的典型的时间同步算法分为三类：

基于receiverreceiver的同步算法、基于pairwise的同步算法和基于senderreceiver的单向（oneway）同步算法。

21基于ReceiverReceiver同步算法Receiverreceiver同步方法由加州大学JeremyElson等在RBs（ReferencebroadcastSynchronization）算法中引入L7j。

RBS采用接收者与接收者（receiverreceiver）之间进行同步的方法进行节点间的同步，排除了发送方对同步精度的影响，如图l，中间节点（sender）利用物理层广播周期性地向网络中其它节点发送参照广播（referencebroadcast），广播域中的节点收到参照广播后，就用自身的本地时钟记录收到的时间，然后相互交换各自的记录时间，

（2）式中”为接收节点数目；m为参照广播次数；L。

表示在收到参照广播6时接收节点r的时钟。

1”Vi”，j”：

o价Pfi，j一亡（L，tEt）

（2）一CrnicmP砸卜_一l+一斗蛔图1通过中间节点（sender）的参照广播Receiverl和Receiver2进行节点间同步示意图通过这种方式，接收节点能够知道彼此之间的时钟偏移量（offset），然后通过

（2）式形成的偏移量矩阵计算相对其它所有节点时钟偏移量的平均值，并用它对本地时钟进行相应调整，当每个节点都取得相对其它所有节点时钟偏移量的平均值时，所有接收到同一参照广播消息的接收节点便获得了一个相对网络时间。

由于RBS通过采用接收者之间进行同步的方法避免了发送方对同步精度造成的影响，从而提高了同步精度。

但是RBs有很大的交换次数，对于具有N个节点的单跳wsN，节点问至少有N条消息要交换，N一1个接收节点之间相互同步，但并不与发送节点同步；实际上，在wsN中发送节点很可能也是一个普通的网络节点因而也需要同步，为使该节点和其它节点进行同步，需要另外一个节点作为参照广播发射节点，并再次通过N条消息的广播获得N个节点的相对网络时间。

22基于成对同步（Pairwisesynchronization）算法221TPSN算法加州大学网络和嵌入式系统实验室SaurabhGaneriwaI等提出的TPSN（TimingSyncProtocoIforSensorNetworks）算法采用发送者与接受者（senderreceiver）之间进行成对同步的工作方式，并将其扩展到全网域（Networkwide）的时间同步8。

成对同步采用典型的两次消息交换法取得一对节点间的时钟同步。

TPsN同步算法的执行分两阶段：

第一阶段一层次发现阶段（Leveldiscoveryphase），该阶段主要在网络中产生一个分层的拓扑结构，使每个节点被赋予一个层次号。

首先选取一个节点作为根节点并赋予层次号o，然后由它广播一个leveldiscovery包，1ev刚一discovery包中封装有发送者的标识和层次号，根节点的直接相邻节点收到这个包后将包中的层次号加1作为自身的层次号，然后它们再广播一个新的lev毗一discovery包，重复这个过程直至网络中的每个节点都赋予一个层次号。

第二阶段一同步阶段（Synchronizationphase），在这个阶段中，从根节点开始与其下一层节点进行成对（pairwise）同步，接着属于i层的节点与i一1层的节点进行成对同步。

最终每个节点都同步于根节点并获得了网络的全局时间同步。

TPSN对任意节点其同步误差取决于它距离根节点的跳数而与网络中节点总数无关，使TPSN同步精度不会随节点数目增加而降级，从而使TPSN具有较好的扩展性。

TPSN算法的缺点是一旦根节点失效，就要重新选择根节点并重新进行上述两个阶段处理，增加了计算和能量开销。

222LTS算法加州大学伯克利分校JanavanGreunen等提出通过牺牲一定精度来减少能量开销的时间同步算法LTS（LightweightTreebasedSynchronization）。

LTS算法主要用于全局时间同步，它在成对同步的基础上进行了简单的线性扩展，算法首先构造一个包括所有节点具有较低深度的生成树T，然后成对同步沿着树T的边进行。

参考节点通过与所有它的直接孩子节点进行成对同步来初始化整个同步过程；参考节点的孩子节点又与它们自己的孩子节点进行成对同步。

整个过程直到T的叶子节点被同步时终止。

算法的运行时间与树的深度成比例。

由于LTS算法只沿生成树的边进行成对同步，所以成对同步次数是生成树边数的线性函数，这与简单地将成对同步扩展到多跳同步的方法相比（要求舻次成对同步），极大的减少了成对同步的系统开销，但也在一定程度上降低了同步的精度。

23基于SenderReceiver单向同步算法基于SenderReceiver单向同步算法的基本原理是：

发送节点（sender）发送一个包含本地发送时间戳的时间同步消息，接收节点（receiver）用本地时钟记录接收时间并取出同步消息中的时间戳，然后调整自身时钟与同步节点时钟同步。

目前基于这种方法提出的时间同步算法有以下两种。

231DMTS算法DMTS（DelayMeasurementTimeSynchronization）算法的实现策略是牺牲部分时间同步精度换取较低的计算复杂度和能耗1。

接收节点通过精确地测量从发送节点到接收节点的单向时间延迟并结合发送节点中的时间戳计算出时间调整值。

DMTS为了较准确地测量发送方到接收方的单向时间延迟，采取了以下方法：

（1）发送方在检测到信道畅通时才给即将发送的时间包标记时间戳并立即发送，从而避免了SendTime和AccessTime对同步精度产生的影响。

（2）DTMs通过数据发射速率和发射数据的位数（bits）对发射延迟进行估计，发射延迟包括发射前导码和起始符的时间以及发射数据的时问。

（3）接收方在MAc层给同步包标记一个到达时间戳，并在接收处理完成时再标记一个时间戳，通过这两个时间戳的差值来估计接收处理延迟。

i|l|万方数据第10期康冠林，等：

无线传感器网络时间同步综述如图2所示，发送节点和接收节点间的时间延迟幻可通过（3）式得出，其中f。

为发射前导码（Preamble）和起始符（Startsymbols）所需时间，。

一疗其中行为发射位数（bits），u为发射一位所需时间。

幻=。

+（f2一1）（3）胁商，。

鲨-i塑雩避避n鞠fnl）leR触n陋ACKn醯gnce押盯r1五ii。

图2DMTS算法原理不意图当发送节点在MAC层检测到信道通畅时给同步包标记时间戳f并发射，接收节点在接收到时间同步包后通过（4）式设置本地时钟，从而实现两者的同步。

，一+行口+（f2一1）（4）文献10将DMTS扩展到多跳（Multihop）传感器网络，多跳DMTs算法采用分层同步的方法：

首先选取一个节点作为时间首领（1eader），并赋予其时间源层次O，能够直接收到leader时间同步消息的节点赋予时间源层次1，以此类推能直接收到层次为”一1节点时间同步消息的节点被赋予层次”。

leader周期性地广播时间消息，时间源层次l的节点在收到同步消息后，调整自己的时钟使之与leader节点（即根节点）同步；同样地，层次”的节点与层次行一1的节点进行时间同步，最终所有节点都与根节点同步从而取得wSN的全局时间同步。

232FTSP算法FTSP（FloodingTimeSynchronizationProtoc01）算法由Vanderbilt大学BranislavKusy等提出“_1。

FTSP算法也是使用单个广播消息实现发送节点与接收节点之间的时间同步，但是算法的具体实现与DMTs有所不同，FTsP算法实现步骤如下：

（1）FTsP算法在完成sYNc字节发射后给时间同步消息标记时间戳f并发射出去；sYNC字节类似DMTS算法中的Startsymbols。

时间戳为当前时间减去包含时间戳的消息数据部分的发射时间，消息数据部分的发射时间可通过数据长度和发射速率得出。

（2）接收节点记录SYNc字节最后到达时间，并计算位偏移（臃fo，s甜）。

在收到完整消息后，接收节点计算位偏移产生的时间延迟如，这通过偏移位数与接收速率得出。

（3）接收节点计算与发送节点间的时钟偏移量：

o，J以一f，一如一；然后调整本地时钟和发送节点时钟同步。

FTSP算法对时钟漂移（czo幽d一s）进行了线性回归分析。

FTSP算法考虑到在特定时间范围内节点时钟晶振频率是稳定的，因此节点间时钟偏移量（o，如甜）与时间成线性关系；通过发送节点周期性广播时间同步消息，接收节点取得多个数据对（time，osPf），并构造最佳拟合直线L（time）。

通过回归直线L（time），在误差允许的时间间隔内，节点可直接通过L（time）计算某一时间点节点间的时钟偏移量而不必发送时间同步消息进行计算，从而减少了消息的发送次数并降低了系统能量开销。

3无线传感器网络时间同步算法分析比较影响WSN节点间时间同步精度的6个因素中除PropagationTime外，都可采用不同方法减少这些因素对同步精度产生的影响，从而提高时间同步的精度；本文论述的同步算法都是通过不同途径减少或消除这些因素对同步精度的影响来提高时间同步的精度。

RBS采用的ReceiverReceiver同步算法完全排除了发送端对同步精度的影响因素，具有较高的同步精度；此外RBS算法还具有广泛的适用性，文献7论述了RBS使用现有商用硬件平台在IEEE80211方式下的实现；但是RBs有较高的计算复杂度，网络流量开销和能耗较大。

基于Pairwise同步算法中，TPSN算法通过在MAC层检测到信道空闲时给同步包标记时间戳并发射，并在MAC层为接收到的同步包标记接收时间戳，从而排除了sendTime、AccessTime和Receptiontime对同步精度的影响。

在文献8中对TPsN和RBS的同步误差进行了分析并在伯克利Mica节点n”“3中进行了实验对比，结果表明TPSN能够获得近似RBs两倍的同步精度。

此外TPSN的同步精度不会随节点数目的增加而降低，使它具有一定的扩展性。

TPsN算法主要针对全局时间同步，它进行一次全局同步有较大的能量?

肖耗；另外如果根节点失效，将会重新选择根节点并重新运行TPSN算法，这在一定程度上增加了系统的开销。

LTs算法主要用于全局时间同步，它沿着生成树的边进行单跳成对同步，成对同步的次数是边数的线性函数，这极大地减少了同步的能量开销但同时也降低了同步的精度；它适用于对时间精度要求不是很高的应用。

并且I。

Ts算法的精度与生成树的深度相关，要获得深度最小的生成树需要一定的网络和能量开销，而且该方法对从叶子节点到参考节点的路径上信息的可靠性和正确性要求较高；同步很可能受到些节点子集错误信息的影响而失败。

基于senderReceiver单向同步算法在上述三类方法中需要发送时间同步消息的数目最少。

发送节点只要发送一次时间同步消息就可完成发送节点与接收节点间的时间同步，因而具有较低的网络流量开销。

其中DMTs算法采取了三个措施提高对单向传输延迟的估计，它具有较低的计算复杂度，减少了系统能量开销；但是其同步精度比RBS和TPsN略有下降；该方法实现简单，适合对同步精度要求不太高的应用。

FTSP算法由于增加了对位偏移产生的时间延迟的估计，因而具有比DMTS算法更高的同步精度。

文献11中通过实验表明它的同步精度位于TPSN与RBS之间。

4无线传感器网络时间同步研究展望目前对wsN时间同步算法的研究已取得了很大进展，但是现有的wSN时间同步算法还不够完善，我们认为以下几个方面值得我们进一步研究。

大规模wsN时间同步一随着硬件技术的发展传感器节点的成本将会逐渐降低，使今后进行大规模传感器节点的部署成为可能，现有的wSN时间同步算法都是对中小规模的wsN时间同步进行仿真和实验的，因此wsN时间同步算法在大规模wsN中的应用是今后研究的方向之一。

（下转第1030页）奎望竺耐一一咕l王鸯盘鳖|11万方数据1030计算机测量与控制第10期振幅dB0一】O一152025相180160140120100一8060一40一20020ij一，；，、划伊l舅jj8i糊!

l。

一。

擞；一一0110100。

一策，r；，。

，r。

XL上jilr0110100图6互相关方法求取的频率响应特性曲线图5结束语该套测试系统，操作方便，数据采集和处理精度、效率都一比较高，计算机能自动打印测试报告以及曲线等，相比较专用的仪器，成本大大的降低。

平台配置灵活性较大，适用的范围较广，不仅可以进行机电系统频率响应特性的，而且也可以满足大部分电气系统频率响应特性的测试要求，应用前景十分的广阔。

率Hz参考文献：

1卢文祥，杜润生机械工程测试信息信号分析M武汉：

华中科技大学出版社，19992傅周东液压元件稳动态特性计算机辅助测试系统的开发D浙江大学硕士学位论文，19883NationalInstrumentsMeasurementstudioReferenceZNationalInstruments，2001厂4AdvantechAdvantechdevicedriverusermanualV15forWindowsrZAdvantech，20015AdvantechPcI一1721usefsmanualzAd