无线传感器网络中的时间同步技术的研究

无线传感器网络中的时间同步技术的研究摘要：本文首先介绍了无线传感器网络中时间同步技术的国内外研究动态和根本理论，然后分析和比拟了现有的几种典型算法。在此根底上，说明了传统网络的时间同步协议不适用于无线传感器网络的原因和现有无线传感器网络时间同步算法的缺乏之处。关键字：无线传感器网络；时间同步；多跳；误差分析一.研究目的及意义无线传感器网络是一种基于信息监测与获取的分布式无线网络体系，是一门新兴的前沿技术。及时的开展无线传感器网络节点及其关键技术的研究，将极大推动无线传感器网络和节点技术的国产化研究，为中国提供具有自主知识产权的高科技产品。对我国社会、经济的开展具有重大的战略意义，也将对人类未来生活产生深远的影响。时间同步是无线传感器网络的重要支撑技术之一，基于传感器网络的应用，如：目标追踪、协同休眠、定位、协同数据采集、时分多址、数据整合等都需要网络中节点的时钟保持同步。在目标追踪应用中，每个传感器节点可能只观测到目标返回的信号强度，并不能得到目标的位置、速度和前进方向等信息，需要多个传感器节点将传感到的数据发送给传感器网络中的会聚节点，会聚节点在对不同传感器发送来的数据进行处理后才能获得目标的移动方向、速度等信息，这就要求相关的传感器节点采集的数据在时间上是相关的。无线传感器网络中的多数节点是无人职守的，仅携带有少量有限的能量，为了延长网络的使用期限，网络中的节点大局部时间都处于定时休眠状态，为了能协同完成工作任务，节点必须进行协同休眠，这也要求节点具有准确的时间同步。波束成型阵列在确定声源的位置时，需要计算多个传感器接收到的信号的相位差，这要深圳市接收到的数据是同步的。在无线传感器网络的应用中，为了减少网络的通信量以降低能耗，往往将传感器节点采集到的数据进行必要的融合处理，进行这些处理的前提是网络中的节点具有相同的时间标准。由于无线传感器网络自身的能量、体积、价格、技术等方面的约束，研究满足无线传感器网络同步精度的时间同步机制，具有很重要的理论和实践价值。二.时间同步技术研究现状无线传感器网络的时间同步这一研究课题是2002年由J.Elson和KayRomer在国际权威的学术会议HotNets上首次提出的。到目前为止，已经提出了近10余种不同的实现算法，典型的有RBS、DMTS、FTSP、TPSN、TS/MS、LTS等。纵观这几种算法可以将其分为以下三类：基于接收者-接收者的时间同步算法，基于成对同步的双向时间同步算法，基于发送者-接收者的单向时间同步算法。这三种机制都有其典型的代表算法，比方RBS、TPSN和DMTS等三种算法就分别对应上述的三类机制。它们给出了WSN中节点的时间同步问题的不同的解决方案，可以满足不同的应用，同时在根底设施、能量需求和时空复杂度方面也均有不同。2002年9月由J.Elson等人提出的参考播送RBS同步协议，是第一种非常系统的实现无线传感器网络时间同步的方法。RBS算法是通过同步接收节点而实现同步的方法，它减小了发送者的不确定性，缩短了关键路径，在多跳的环境中要保证各个簇之间拥有公共的节点，误差随着跳数的增加而逐渐增大。RBS的时间复杂度为(N')，这无疑增大了网络的能量开销，它仅仅适用于单跳范围内节点间的同步，其可扩展性较差。2003年6月，PingS等学者提出了DMTS—延迟测量时间同步机制，它主要考虑了分组消息往返时间的不同，首先选取一个节点作为时间基准节点，发送一个包含自身时钟当前读数的同步分组，其他节点接收到该分组后，测量时间延迟并调整自身的时间为分组携带的时间信息加上测量的时间延迟，从而实现和时间基准节点间的同步。此方法的同步精度是由时间延迟的测量精度决定的，其特点是精度低，开销小。TPSN协议]是由SaurabhGaneriwal等人于2003年11月提出的。它通过将所有节点进行逻辑分级建立了一种层次结构的网络，进而实现了全网络节点的时钟同步。在TPSN中，考虑了传播时间和接收时间的影响，利用双向分组交换机制计算分组的传输延迟，提高了精度。但此算法没有考虑根节点失效的问题，导致了其鲁棒性较差。由Greunen和Rabaey提出的LTS(LightweightTree-BasedSynchronization)算法主要是以减小同步的复杂度为主要目的，未过多考虑其精度，该算法是在成对双向同步的根底上进行线性扩展得到的，适用于全局网络的时间同步。除了上述的几种算法外，还有许多非常优秀的时间同步协议，比方:MarotiM等学者提出的FTSP(FloodingTimeSynchronizationProtocol)协议；在多跳的网络中，Strogatz和Mirollo提出的利用耦合振荡器的同步技术实现网络无状态自然同步的方法也倍受关注，这是一种高效的、可无限扩展的时间同步新技术；由清华大学提出的ATS协议对存储能力的要求较高，不适用于大规模的无线传感器网络；由浙江大学提出的基于反应的时间同步协议，考虑了时钟的内部扰动和外部干扰，其鲁棒性比DMTS高，且到达了和FTSP一样的精度，但其不适用于动态拓扑的网络。目前，针对单跳同步的研究已经趋于成熟，精度可到达微秒级，而对于多跳同步的研究相对较为薄弱，通常采取的方法是：网络中的节点首先通过通信连接关系建立一定的网络拓扑结构，然后按照协议的约定，未同步节点和已同步节点交换同步分组，从而间接地实现与时间基准节点间的同步。这样的同步机制会使得同步误差累积加剧，而且还面临可扩展性问题的挑战。此外，时间同步技术也应考虑节点的移动性。因此，作为无线传感器网络的一个极为重要的研究方向，时间同步技术有着广阔的空间需要我们去探索。三.典型的时间同步机制目前已经提出众多同步算法，较为经典的同步算法可以归结为以下三类：基于接收者-接收者(Receiver-Receiver)机制的时间同步算法，基于成对(Pair-Wise)同步机制的双向时间同步算法，基于发送者-接收者(sender-receiver)的单向时间同步机制。下面分别以实例来说明这三种同步机制的原理。3.1基于接收者-接收者机制的时间同步算法图1是Sender-Receiver和Receiver-Receiver同步机制原理的示意图，从图中容易看出，Receiver-Receiver同步机制的关键路径大大缩短，完全排除了SendTime和AccessTime对同步精度的影响，其典型的代表算法主要是参考播送同步RBS(ReferenceBroadcastSynchronization)算法，它是由J.Elson等人提出的，其主要目标是实现接受节点间的同步。RBS算法充分利用了无线链路层播送信道的特点，由一个节点发送播送分组消息，在同一厂播域的其它节点将同时接收播送的分组消息，并用各自的本地时钟记录收到播送分组消息的时一间，之后接收节点将各自的记录时间相互交换，通过比拟和计算时钟的偏移而到达时间同步。任意两节点i和j之间的时钟偏移可以通过下公式得到:其中，n表示接收节点的数目，m表示播送的次数，Tr,b表示当收到播送b时接收节点r的时钟。通过上述方式，接收节点容易获得彼此之间的时钟偏移量(offset)，然后利用上述公式形成的偏移量矩阵计算其相对其它所有节点时钟偏移量的平均值，并根据这个平均值相应地调整各节点的本地时钟，当各个节点都获得其他任何节点的时钟偏移量的平均值后，接收到同一播送分组消息接收节点便获得了一个相对网络一致的时间。图1Sender-Receive图1Sender-Receive同步机制和Receiver-Receiver同步机制由于RBS算法只同步接收者，从而防止了发送方对同步精度的影响，提高了时间同步的精度。在多跳网络中，RBS通过有效分簇划分播送域并选取公共节点以实现多个播送域间的同步。下面以图2中a)的节点9和节点1为例说明RBS在多跳网络中的同步原理。易知，节点9和4位于参考节点C的单跳区域内，根据单跳RBS协议，它们之间的本地时钟可以相互转换。同理，节点1和节点4位于参考节点A的单跳区域内，它们之间的本地时钟也可以转换。从而，将节点4作为媒介，那么可以实现节点9的本地时间与节点1的本地时间之间的转换。图2图2多跳RBS原理图在规模较大的无线传感器网络中，完全静态地指定媒介节点是不太现实的，而且也和因通信故障或节点失效等影响而造成的网络拓扑变化不相适应。故而，在寻找连接目标节点和同步源节点之间的转换路径时，RBS采取了“时间路由”的方法。图26中，与a)相对应的逻辑拓扑图如b)所示。在逻辑拓扑图中，每个单跳范围内可直接进行时间转换的节点对必有一条对应边，由此可知每个单跳区域的逻辑拓扑图必是一个完全图。在此完全图中，可以选择一条连接目标节点和同步源节点的最短路径，接下来即可按照该路径逐跳进行时间转换。此最短路径确实定可以采用链路状态法、Dijkstra等算法。RBS协议一次同步涉及3方节点，频繁的再同步必将给网络带来较大的通信和能量开销，不适合有限能量供给的应用场合。针对该问题，JElson提出了“后同步”的思想，即当节点监测到事件发生后才用自身的本地时钟记录发生时间，然后运行RBS协议，使得监测事件的发生保持时间同步。3.2基于成对同步机制的双向时间同步算法双向同步机制的原理是：发送方发出同步请求分组，接收方返回应答分组，发送方根据分组中的时间标记估算同步参量并校准本地时钟或构造逻辑时钟，完成两节点的同步。〔1〕TPSN算法加州大学网络和嵌入式系统实验室的S.Ganeriwal等提出的传感器网络时间同步协议TPSN(Timing-SyncProtocolforSensorNetworks)属于典型的双向同步机制，它可以实现全网范围内的时钟同步，在网络中有一个可以装配如GPS接收机的复杂硬件部件的根节点，将它作为整个网络系统的时钟源。协议实现分为两个阶段:层次发现阶段(leveldiscoveryphase)和同步阶段(synchronizationphase)。同步阶段中的单跳同步采用比对同步的远程时钟读取方法，如图3所示，同步原理类似NTP的双向同步模式：待同步节点B在本地时刻或发送同步请求分组，节点A在本地时刻T2收到该分组，并在本地时刻T3回应答分组，节点B在本地时刻T4收到应答分组，dA表示分组从节点A到节点B的传输延迟，dB表示分组从节点B到节点A的传输延迟。利用这4个时间标记，节点B便可估算出相对偏移：从而B节点根据计算得到的时间偏移修正本地时钟与节点A实现同步。而多跳同步通过层次发现阶段形成的生成树结构来实现多节点的逐级同步，最终使网络中所有节点同步到根节点，实现全网同步。TPSN对任意节点其同步误差取决于它距离根节点的跳数，而与网络中节点总数无关，使TPSN同步精度不会随节点数目增加而降级，从而使TPSN具有较好的扩展性。TPSN算法的缺点是健壮性差，其根节点一旦失效，就要重新选择根节点，重复全网同步的两个阶段，增加了能耗和网络开销。图3图3TPSN单跳网络双向分组交换过程〔2〕LTS算法加州大学伯克利分校JanavanGreunen等提出了通过牺牲一定精度来减少能量开销的时间同步算法LTS(LightweightTree-basedSynchronization)。LTS算法主要应用于全局的时钟同步，它是通过将成对同步进行简单的线性扩展而得到的一种新的算法，应用该算法的网络拓扑是由所有节点形成的一个低深度的生成树T，之后沿着树T的边实施成对同步机制即可。同步过程的初始化是由参考节点和所有它的直接的子节点执行成对同步实现的;参考节点的直接子节点又和它们自身的子节点进行双向成对同步。整个同步过程持续到将T的叶子节点都被同步后为止，算法的运行时间是与树的深度成比例的。在LTS算法中，其双向成对同步是只沿着生成树的边进行的，所以容易得到其双向成对同步的次数和生成树T的边数是一种线性关系，而直接将双向成对同步扩展应用到多跳环境，需要同步的次数将高达扩次。相比之下，LTS算法很大程度上减少了同步次数，极大地减少了成对同步的网络开销，但其同步精度也在一定程度上打了折扣。〔3〕ATS及Adaptive-ATS协议ATS协议(averagetimeSynchronization)是国内较新的关于无线传感器网络时间同步的研究成果，它由清华大学的几位学者提出，其主要思想是：对于给定的某个簇，假设其簇内成员之间能相互通信，簇内各个成员节点的本地时间由簇头节点负责收集，然后计算所有簇内节点的本地时间的平均值，将次平均值作为全局时间播送至各成员节点，簇头节点和各成员节点依据此全局时间调整本地付钟即可实现同步。Adaptive-ATS协议的主要思想:在ATS的根底上，提高了协议的可扩展性和适应性。簇头节点维护一张叫PEtable的表，此表记录了一些较为常用的同步周期和对应的误差上限，具体的实际应用时，用户可以依据要求的误差，查表得到最正确的同步周期，进而进行调整，完成同步。但是在具体的实际应用中，系统要求的误差不一定都能够通过查表就能得到，此时可选取满足误差要求的最长周期，以便节省能量。该算法提高了同步精度，全局时间的连续性不会因为簇头节点的轮换而被打断，并且降低了能耗，其可扩展性和适应性明显得到了提高，但对存储能力的要求高一些，而且不适用于范围的无线传感器网络。3.3基于发送者-接收者的单向时间同步机制Sender-Receiver单向同步机制的根本原理如下所述：首先由发送节点(sender)发送一个包含自身本地时间戳的时间同步分组，接收节点(receiver)接收到此分组后，用其本地时钟记录接收时间并提取出同步分组中的时间戳，然后调整自身的本地时钟与发送节点的时钟到达一致，实现时钟间的同步。目前基于此机制的时间同步算法主要有以下两种：〔1〕DMTS算法DMTS算法的实现策略是为了降低计算的复杂度和网络系统的能耗，牺牲了局部的时间同步精度。其思想是：由接收分组的节点精确地测量分组从发送节点到接收节点的单向的时间延迟，并结合发送节点中的时间戳计算出时间的调整值。DMTS为了尽可能准确地测量出发送方到接收方的单向时间延迟，采取了下述措施：发送方在监测到信道空闲时才在即将发送的时间包上标记时间戳并马上发送，从而消除了SendTime和AccessTime对同步精度产生的影响；接收方在MAC层给时间同步包标记一个到达的时间戳，并在接收处理完毕时再标一记一个时间戳，通过计算这两个时间戳的差值来估计接收处理的时间延迟；DTMS通过发射数据的位数(bits)和数据的发射速率对发射延迟进行了估计，发射延迟包括起始符的时间、发射前导码以及发射数据的时间。图4DMTS图4DMTS算法原理示意图如图4所示，接收节点与发送节点间的时间延迟td可通过下式得出，其中te为发射前导码(Preamble)和起始符(Startsymbols)所需时间，te=nv，其中n为发射的位数((bits)，v为发射一位所需要的时间。当发送节点在MAC层监测到信道空闲时在同步包上标记时间戳t并发送，接收节点在接收到此时间同步包后通过规划方调整自身的本地时钟tr，从而实现两者的同步。也可以将DMTS算法扩展到多跳(Mufti-hop)的无线传感器网络，多跳DMTS算法采用分层同步的方式:首先选取一个节点作为根节点，并赋予其时间源层次0，它能直接收到leader的时间同步消息，赋予其时间源层次为1，以此类推，赋予能直接收到n-1层节点的时间同步消息的节点的层次为n。leader周期性地播送时间同步消息，时间源层次为1的节点在收到同步消息后，调整自己的本地时钟使之与根节点同步。类似地，层次为n的节点与层次为n-1的节点进行的时间同步，最终所有的节点都将与根节点同步，从而实现了WSN的全局时间同步。〔2〕FTSP协议FTSP(FloodingTimeSynchronizationProtocol)算法由Vanderbilt大学BranislavKusy等提出。FTSP算法同步的方式也是通过单个播送消息来同步发送节点与接收节点间的时钟，但是算法的具体实现与DMTS算法具有明显的不同，FTSP算法的实现步骤包括以下三步：节点在发送完SYNC字节后在时间同步消息包上标记时间戳t并发送出去；SNC字节与DMTS算法中的Startsymbols相类似；时间戳t为当前的本地时间减去发射时间戳t的消息数据局部的时间，发送消息数据局部的时间可通过数据的长度和发射速率计算得到；接收节点记录SYNC字节的最后到达时间t，并计算位偏移(bitoffset)。在收到完整的数据消息后，接收节点通过偏移位数与接收速率计算出位偏移产生的时间延迟tb；接收节点通过offset=tr-tb-t计算与发送节点间的时钟偏移量；然后调整本地时钟和发送节点的时钟一致，继而实现同步。FTSP算法通过线性回归分析对时钟漂移((clockdrifts)进行了补偿。在特定的时间范围内节点时钟的晶振频率可以认为是稳定的，基于此，FTSP算法认定节点之间的时钟偏移量(offset)与时间是线性关系;发送节点周期性的播送时间同步消息，接收节点将获得多个数据对(time，offset)，进而通过线性回归方法构造最正确的拟合直线L(time)。利用回归直线L(time)，在误差允许的时间间隔内，节点可直接计算出某一时刻节点之间的时钟偏移量而不必通过发送时间同步消息来进行计算，从而减少了消息的发送次数，降低了网络系统的能量开销。四.无线传感器网络时间同步算法分析和比拟以上介绍的几种时间同步算法是目前较为典型的时间同步算法，它们根据自身的特点都适用于不同的网络环境，并分别对它们各自的性能进行简单的分析和比拟。分析结果如表1所示。表1典型时间同步算法间的比拟同步算法优点缺点适用环境RBS缩短了关键路径，不考虑发送时延和访问时延，甚至排除了接收时间的不确定性；时钟的调整不影响时钟偏差的计算。算法复杂度高，多跳能耗大，不适合有限能量供给的应用场合不仅适用于有线网络也适用于无线网络，可广泛应用于商用硬件设备和已有的无线传感器网络软件。TPSN采用双向分组交换，能精确计算出分组的传输延迟，获得了RBS两位的精度；支持外部时钟源同步。能量开销大；不适合拓扑动态变化的网络。对时间同步要求较高的静