一种基于Ad hoc网络测距的时钟同步协议
扫描二维码
随时随地手机看文章
同所有的分布式系统一样，时钟同步也是Ad hoc网络技术研究中的一个关键问题。因为网络节点内部的硬件时钟具有一定的误差，所以节点的本地时间会存在偏差。然而，Ad hoc网络的许多应用需要全网络中的节点或一定范围内的部分节点具有高度的时间一致性，因此Ad hoc网络需要进行时钟同步。现有的有线网络和无线网络上的时钟同步协议并不能完全满足Ad hoc网络应用的需要，迫切需要进一步研究，探索出适合Ad hoc网络的时钟同步方法。
1 相关研究
1.1 有线网络上的时钟同步方法
传统的时钟同步方法中最典型的是利用GPS (Global Position System)或NTP[1]协议实现设备间的同步。Ad hoc网络,尤其是传感器网络的节点,必须考虑移动终端的成本代价。GPS装置价格昂贵，并且在建筑物或水下，其服务质量并不能得到很好的保证,尤其在军事应用中，利用GPS来获得无线网络节点的时钟同步是极不可靠的。因此，在众多Ad hoc网络的应用中利用GPS获得时钟同步是不可取的。
NTP协议假设网络中2个节点的时间请求、回复报文具有相同的时延，由于Ad hoc网络多跳的无线环境存在非对称链路、前向链路和反向链路，这些链路往往具有不同的时延，因此NTP协议不适合直接应用于Ad hoc网络；另外，NTP协议需要在网络中配置时间服务器，Ad hoc网络是一种移动自组织网络，没有中心节点，这也导致了NTP协议无法直接应用于Ad hoc的网络时钟同步。
1.2 无线传感器网络上的时钟同步协议
参考文献[2]提出了一种适合无线传感器网络的参考广播时钟同步协议(RBS)，该协议利用了“第三方”的广播时钟同步信息来完成2个单跳节点的时钟同步。其基本思路是：在广播域内周期性地广播1个数据分组(不必做时间标记)，所有接收到这个数据分组的接收方对该数据分组做时间标记。所有接收方互相交换它们的时间标记，并以此获得邻近节点的时钟。重复以上过程，所有节点不仅知道它们相互之间的相位偏移，而且知道它们相互之间的频率漂移率。所有节点都不调整它们的本地时钟，但要为每个邻近节点建立一个调整时钟所需要的参数表。仿真结果表明，在Berkeley Motes平台上30次同步后取平均所获得的同步精度为1.6 ?滋s。RBS协议虽然可以获得比较高的同步精度，但其只能应用于单跳范围内节点间的时钟同步,将RBS协议扩展到多跳是该协议能否应用于Ad hoc网络的关键。
TPSN(Time-synchronization Protocol for Sensor Networks)[3]是一种用于多跳传感器网络的时钟同步协议，该协议的目标是全网时钟同步。TPSN包括两个阶段，第一阶段是拓扑发现阶段，或称为全网络同步阶段，目的是要建立一个分级的网络拓扑，其本质就是建立生成树。如果根节点能访问一个外部的高精度时钟，那么网络中的所有节点都与这个高精度的时钟同步。第二阶段为比对同步阶段，由时钟参考节点周期性地广播一个同步标志发起，等级为1的节点接收到标志后即和时钟参考节点同步，同步策略采用类似NTP的“two-way message exchange”，随后同步依照节点等级向外扩散，每个等级为i的节点向等级为i-1的节点同步，最后完成全网节点与时钟参考节点的同步。
从直观上来看，RBS只引入了传播时延和接收时延，应该具有更高的精度，但在参考文献[4]的实验环境下，发送时延和接入时延的不确定性比较小，并且多种不确定因素的作用可能相互抵消，TPSN获得了优于RBS协议的精度。另外，RBS协议完成一对节点的时钟同步需要1次报文广播和至少2次报文单播，TPSN只需要2次报文单播，发送更少的报文，对于共享信道、数据容易发生冲突的无线信道来说,具有更好的可扩展性。
2 基于Ad hoc网络测距的时钟同步方法
2.1 双向传播时延的计算方法
参考有线网络上的DOCSIS规范[5]对测距过程的描述，本文提出一种基于时钟相对同步概念的可应用于Ad hoc网络的计算双向传播时延的方法。
Ad hoc网络的测距过程分为两个部分：初始测距和周期性测距。初始测距又分为初始维护(initial maintain)和站维护(station maintain)。在初始测距过程中，邻近子层设备节点要获取准确的定时偏移，即基准时钟同步信号的发送方(主时钟节点)与某一特定的接收方(从时钟节点)之间传输数据的双向传播时延(RTD)。从时钟节点根据RTD提前发送数据的时间以补偿网络时延,使不同的从时钟节点所发送的数据到达主时钟节点的时间与主时钟节点在带宽分配报文(MAP)中要求的时间对齐。带宽分配报文是主时钟节点向从时钟节点发送的。双向传播时延的计算过程如图1所示[6]。
RTD包括下行传输时延(从主时钟节点到从时钟节点)和上行传输时延(从从时钟节点到主时钟节点)。首先，从时钟节点从主时钟节点读取时间标记，获得当地时钟基准，然后根据MAP找到主时钟节点分配的初始维护区，发出初始测距请求(RNG-REQ)。由于从时钟节点与主时钟节点之间存在距离，该请求将延迟一段时间到达，假设到达时刻为T=440。主时钟节点计算收到RNG-REQ的实际时刻与初始维护区起始时刻之差，在测距响应(RNG-RSP)中通过“定时调整”字段返回给从时钟节点。主时钟节点在发送RNG-RSP前还应该获得从时钟节点发送的确切频率、接收的实际功率等信息。主时钟节点在这些数据的基础上计算出校正数据，并在RNG-RSP中发送给从时钟节点。从时钟节点收到RNG-RSP后，根据下式计算收到第n个RNG-RSP后得到的定时偏移tn：
图1中初始维护使得从时钟节点的定时偏移调整为t1=120。在随后的站维护过程中，从时钟节点提前t1发送RNG-REQ，该数据分组在站维护区的起始时刻T=740到达主时钟节点。主时钟节点根据接收参数计算需要进行的附加微调,并通过轮询RNG-RSP返回给从时钟节点。从时钟节点根据式(1)继续调整定时偏移,直到主时钟节点指示测距过程成功。
2.2 全网络生成树的建立
建立全网络同步是从建立生成树开始的。首先，从根节点发出一个层发现报文(包含根节点的层变量0)。根节点的所有单跳邻近节点为其自己分配的层号(1)加上层发现报文中的层变量，并接受根节点作为它们的父节点。然后第1层的节点发出它们自己的层发现报文，依此类推。同一层的每个节点选择一个随机延迟来避免过多的报文碰撞。一旦某个节点接收到第一个层发现报文，该报文的发出者就被作为接收方的父节点，而后来的层发现报文则被丢掉。节点找到它的父节点以后，就接收父节点周期性发出的时钟同步信号SYNC，并校正自己的本地时钟，同时，节点本身也周期性地发出时钟同步信号，使它的子节点也保持同步。
由于报文碰撞或者在生成树建立以后某个节点才加入到网络中，因此有的节点可能没有接收到层发现报文。如果某节点i在一定的时间内没有接收到任何层发现报文，那么它就会向它的单跳邻近节点发出一个层发现请求报文，询问关于现在生成树的情况。之后，节点i会密切监听网络，收集在某个时间范围内的请求应答报文，然后在它的邻近节点中选择一个层变量最小的节点作为它的父节点。图2是节点i加入网络层次结构的过程示意图。
2.3 测距时钟同步方法的设计实现
从时钟节点的初始测距要经历广播初始维护和单播站维护2个阶段。初始维护阶段调整从时钟节点的功率电平、上行信道中心频率和定时偏移等信息。站维护阶段对上述参数进行微量调整。初始测距过程可以设计为4个状态：等待初始维护机会、等待测距响应、等待站维护机会和等待轮询测距响应。图3所示为该过程的有限状态机图。
从时钟节点必须补偿物理层的传输时延，相当于将从时钟节点放在与主时钟节点相近的地方。因而系统将初始定时偏移设为内部固定的时延量，包括从MAC层到物理层的延迟等。初始测距期间发送第一个RNG-REQ时，根据初始定时偏移计算提前发送的时间。主时钟节点收到请求后计算定时偏移等参数的校正值，并通过RNG-RSP返回给从时钟节点。响应中的“测距状态”字段指出从时钟节点下一步的动作(继续、中断或测距成功)。站维护阶段的测距请求、响应步骤重复多次,直到从时钟节点得到含有测距成功的通知或主时钟节点放弃测距响应为止。在系统运行过程中，当来自于从时钟节点的数据的到达时间与主时钟节点分配的时间之间的误差超过一定限度时，主时钟节点可以向从时钟节点发送报文，要求进行突发性的测距。从时钟节点周期性地发送测距请求，一般来说，发送周期间隔会比较长。
为了避免主时钟节点一直没有响应而造成的从时钟节点无休止地等待状态，可以规定等待响应的最长时间，一旦超过这个时间，从时钟节点将认为主时钟节点没有收到它发送的测距请求报文或主时钟节点出现了故障。初始测距过程涉及到的超时情况包括：T2等待广播测距机会超时,T3等待测距响应超时,T4等待单播测距机会超时。
3 仿真实验及分析
实验采用中科院自主设计的GAINS-2节点，该节点与Mica2节点兼容。GAINS-2节点的微控制器采用Atmega128L，射频芯片采用CC1000。CC1000是一款面向字节的无线芯片，支持时钟同步算法在MAC层标记时间戳。节点的操作系统采用无线传感器网络专用操作系统TinyOS。实物测试中，为了采集到同一时刻多个节点的本地时钟信息，把需要同步节点和时钟基准节点控制器的外部中断引脚通过导线连接在一起，由需要同步节点触发外部中断引脚产生中断，并在中断处理程序中记录采集时间点各个节点的时钟信息。
仿真环境为一个由64个节点组成的Ad hoc网络，节点的编号为1~64。分别使用了1号、21号、41号、61号节点作为时间基准节点，并随机变换节点在网络中的拓扑位置，从多个角度对时钟同步算法、同步精度和稳定性进行测试。设同步周期为30 s，在同步完成后5 s采集时钟信息。这主要是考虑到Ad hoc网络节点的任务处理延迟，如数据包的加密与解密、连续跟踪一个活动目标、连续高频率采集传感器数据等。图4所示为网络中各个节点在不同采集时刻的时钟同步精度统计数据。
从图4的统计数据中可以发现，64个节点中的绝大多数节点在采集时刻都具有良好的时钟同步精度，能够满足应用的要求。由于Ad hoc网络在实际应用中，节点可能被随机散布在监控区域中，因此系统应当允许有个别节点不能在规定时间内取得时钟同步，这也是对系统健壮性的一个衡量指标。仿真实验中，导致个别节点不能在规定时间内取得时钟同步的原因是节点位置较偏，邻居节点数目较少，以及实验中设置的5%的误码率和10%的丢包率。
本文提出了一种基于Ad hoc网络测距的时钟同步协议，相比传统的时钟同步方法，该协议建立系统相对同步只需要一次报文广播，而RBS协议要求有至少两次的报文单播；在初始测距成功后，DOCSIS规范只有周期性测距，而本文引进了突发测距机制，允许周期性测距的时间间隔更长。当双向传播时延突变时，主时钟同步节点可以及时进行新一轮测距。仿真测试表明，这种时钟同步方法能满足不同时钟同步精度下的Ad hoc网络的应用要求，具有低功耗和高可靠性的特点。
参考文献
[1] MILLS D L． Internet time synchronization： the network time protocol[J]．IEEE Trans Communication，1991，39(10)： 1482-1493．
[2] JERE MY E，LEWIS G，DEBORAH E． Fine-grained network time synchronization using reference broadcasts[A]．Proc 5th Symp Op．Sys Design and Implementation [C]．Boston，MA，2002．
[3] FIKRET S，BULENT Y． Time synchronization in sensor networks：a survey [J]． IEEE Network，2004，7(8)：45-50．
[4] HILL J，CULLER D． A wireless embedded sensor architecture for system level optimization[R]．Tech Rep，UC Berkeley，2001．
[5] CableLabs． Data-over-cable service interface specifications radio frequency interface specification， SP-RFIv1.1I06- 001215[S]．2000：82-85．
[6] 王沁，龙萍，张晓彤，等．基于DOCSIS规范的测距机制分析与嵌入式实现[J]．通信学报，2006，27(9)：96-101．
下载文档
