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

无线传感器网络中的时间同步技术的研究摘要：本文首先介绍了无线传感器网络中时间同步技术的国内外研究动态和基本理论，然后分析和比较了现有的几种典型算法。在此基础上，说明了传统网络的时间同步协议不适用于无线传感器网络的原因和现有无线传感器网络时间同步算法的不足之处。关键字：无线传感器网络；时间同步；多跳；误差分析一.研究目的及意义无线传感器网络是一种基于信息监测与获取的分布式无线网络体系，是一门新兴的前沿技术。及时的开展无线传感器网络节点及其关键技术的研究，将极大推动无线传感器网络和节点技术的国产化研究，为中国提供具有自主知识产权的高科技产品。对我国社会、经济的发展具有重大的战略意义，也将对人类未来生活产生深远的影响。时间同步是无线传感器网络的重要支撑技术之一，基于传感器网络的应用，如：目标追踪、协同休眠、定位、协同数据采集、时分多址、数据整合等都需要网络中节点的时钟保持同步。在目标追踪应用中，每个传感器节点可能只观测到目标返回的信号强度，并不能得到目标的位置、速度和前进方向等信息，需要多个传感器节点将传感到的数据发送给传感器网络中的汇聚节点，汇聚节点在对不同传感器发送来的数据进行处理后才能获得目标的移动方向、速度等信息，这就要求相关的传感器节点采集的数据在时间上是相关的。无线传感器网络中的多数节点是无人职守的，仅携带有少量有限的能量，为了延长网络的使用期限，网络中的节点大部分时间都处于定时休眠状态，为了能协同完成工作任务，节点必须进行协同休眠，这也要求节点具有准确的时间同步。波束成型阵列在确定声源的位置时，需要计算多个传感器接收到的信号的相位差，这要深圳市接收到的数据是同步的。在无线传感器网络的应用中，为了减少网络的通信量以降低能耗，往往将传感器节点采集到的数据进行必要的融合处理，进行这些处理的前提是网络中的节点具有相同的时间标准。由于无线传感器网络自身的能量、体积、价格、技术等方面的约束，研究满足无线传感器网络同步精度的时间同步机制，具有很重要的理论和实践价值。二.时间同步技术研究现状无线传感器网络的时间同步这一研究课题是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)，然后利用上述公式形成的偏移量矩阵计算其相对其它所有节点时钟偏移量的平均值，并根据这个平均值相应地调整各节点的本地时钟，当各个节点都获得其他任何节点的时钟偏移量的平均值后，接收到同一广播分组消息接收节点便获得了一个相对网络一致的时间。由于RBS算法只同步接收者，从而避免了发送方对同步精度的影响，提高了时间同步的精度。在多跳网络中，RBS通过有效分簇划分广播域并选取公共节点以实现多个广播域间的同步。下面以图2中a)的节点9和节点1为例说明RBS在多跳网络中的同步原理。易知，节点9和4位于参考节点C的单跳区域内，根据单跳RBS协议，它们之间的本地时钟可以相互转换。同理，节点1和节点4位于参考节点A的单跳区域内，它们之间的本地时钟也可以转换。从而，将节点4作为媒介，则可以实现节点9的本地时间与节点1的本地时间之间的转换。在规模较大的无线传感器网络中，完全静态地指定媒介节点是不太现实的，而且也和因通信故障或节点失效等影响而造成的网络拓扑变化不相适应。故而，在寻找连接目标节点和同步源节点之间的转换路径时，RBS采取了“时间路由”的方法。图26中，与a)相对应的逻辑拓扑图如b)所示。在逻辑拓扑图中，每个单跳范围内可直接进行时间转换的节点对必有一条对应边，由此可知每个单跳区域的逻辑拓扑图必是一个完全图。在此完全图中，可以选择一条连接目标节点和同步源节点的最短路径，接下来即可按照该路径逐跳进行时间转换。此最短路径的确定可以采用链路状态法、Dijkstra等算法。RBS协议一次同步涉及3方节点，频繁的再同步必将给网络带来较大的通信和能量开销，不适合有限能量供应的应用场合。针对该问题，JElson提出了“后同步”的思想，即当节点监测到事件发生后才用自身的本地时钟记录发生时间，然后运行RBS协议，使得监测事件的发生保持时间同步。3.2基于成对同步机制的双向时间同步算法双向同步机制的原理是：发送方发出同步请求分组，接收方返回应答分组，发送方根据分组中的时间标记估算同步参量并校准本地时钟或构造逻辑时钟，完成两节点的同步。（1）TPSN算法图2多跳RBS原理图图1Sender-Receive同步机制和Receiver-Receiver同步机制加州大学网络和嵌入式系统实验室的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算法的缺点是健壮性差，其根节点一旦失效，就要重新选择根节点，重复全网同步的两个阶段，增加了能耗和网络开销。（2）LTS算法加州大学伯克利分校JanavanGreunen等提出了通过牺牲一定精度来减少能量开销的时间同步算法LTS(LightweightTree-basedSynchronization)。LTS算法主要应用于全局的时钟同步，它是通过将成对同步进行简单的线性扩展而得到的一种新的算法，应用该算法的网络拓扑是由所有节点形成的一个低深度的生成树T，之后沿着树T的边实施成对同步机制即可。同步过程的初始化是由参考节点和所有它的直接的子节点执行成对同步实现的;参考节点的直接子节点又和它们自身的子节点进行双向成对同步。整个同步过程持续到将T的叶子节点都被同步后为止，算法的运行时间是与树的深度成比例的。在LTS算法中，其双向成对同步是只沿着生成树的边进行的，所以容易得到其双向成对同步的次数和生成树T的边数是一种线性关系，而直接将双向成对同步扩展应用到多跳环境，需要同步的次数将高达扩次。相比之下，LTS算法很大程度上减少了同步次数，极大地减少了成对同步的网络开销，但其同步精度也在一定程度上打了折扣。（3）ATS及Adaptive-ATS协议ATS协议(averaget