《电子技术应用》

简论无线传感网络时间同步的问题

摘要: 想要在无线传感网络中很好地保证数据传输的可靠性,非常重要的一点就是保持节点之间时间上的同步。目前因特网上采用时间同步协议标准是NTP协议,采用有线传输,不适合用于功耗、成本受限制的无线传感网络中。GPS系统也可以提供高精度的时间同步,但它的信号穿透性差,GPS天线必须安装在空旷的地方,功耗也较大,所以不适合无线传感网络。

Abstract:

 引言

  想要在无线传感网络中很好地保证数据传输的可靠性,非常重要的一点就是保持节点之间时间上的同步。目前因特网上采用时间同步协议标准是NTP协议,采用有线传输,不适合用于功耗、成本受限制的无线传感网络中。GPS系统也可以提供高精度的时间同步,但它的信号穿透性差,GPS天线必须安装在空旷的地方,功耗也较大,所以不适合无线传感网络。
  天线的基本功能是辐射和接收无线电波。发射时,把高频电流转换为电磁波;接收时,把电磁波转换为高频电流。天线的一般原理是:当导体上通以高频电流时,在其周围空间会产生电场与磁场。按电磁场在空间的分布特性,可分为近区、中间区、远区。设R为空间一点到导体的距离,是高频电流信号的波长,在R<λ/2π时的区域称近区,在该区内的电磁场与导体中电流、电压有紧密的联系;在R>A/2π的区域称为远区,在该区域内电磁场能离开导体向空间传播,它的变化相对于导体上的电流、电压就要滞后一段时间,此时传播出去的电磁波已不与导线上的电流、电压有直接的联系了,这区域的电磁场称为辐射场。 [全文]

  凡是利用一定的物性(物理、化学、生物)法则、定理、定律、效应等把物理量或化学量转变成便于利用的电信号的器件。传感器是测量系统中的一种前置部件,它将输入变量转换成可供测量的信号”。按照Gopel等的说法是:“传感器是包括承载体和电路连接的敏感元件”,而“传感器系统则是组合有某种信息处理(模拟或数字)能力的系统”。传感器是传感系统的一个组成部分,它是被测量信号输入的第一道关口。 [全文]

ElsON等人2002年首次提出无线传感器网络时间同步的研究课题以来,已有相当多的典型时间同步算法,主要可以分为以下几类:基于发送者-接收者的双向同步算法,典型算法如TPSN算法;基于发送者-接收者的单向时间同步算法,典型算法如FTSP算法、DMTS算法;基于接收者-接收者的同步算法,典型算法有RBS算法。

  近年来根据以上几种典型同步算法,还有人提出了分簇式的层次型拓扑结构算法,以及结合生成树等来提高整个网络的性能,如LTS算法、CHTS算法、CRIT算法、PBS算法、 HRTS 算法、BTS算法、ETSP算法等。

  然而,无论以上同步算法怎样发展,精度如何提高,整个网络功耗怎样降低,都是基于单跳时间同步机制。随着无线传感网络的运用与发展,传感节点体积不断缩小,单跳距离变小,整体网络规模变大,同步误差的累积现象必将越来越严重。目前也有比较新的同步算法,试图尽量避开单跳累加来解决这些问题,如协作同步。

  1  时间同步

  1.1  时间同步不确定性的影响因素

  时间同步不确定性的主要的影响因素如图1所示。

 报文传输延迟

图1  报文传输延迟


  发送时间:发送方用于构造分组并将分组转交给发送方的MAC层的时间。主要取决于时间同步程序的操作系统调用时间和处理器负载等。

  访问时间:分组到达MAC层后,获取信道发送权的时间。主要取决于共享信道的竞争、当前的负载等。

  传送时间:发送分组的时间,主要取决于报文的长度等。

  传播时间:分组离开发送方后,并将分组传输到接收方之间的无线传输时间。主要取决于传输介质、传输距离等。

  接收时间:接收端接收到分组,并将分组传送到MAC层所需的时间。

  接受时间:处理接收到分组的时间。主要受到操作系统的影响。

  1.2  典型时间同步算法分析

  1.2.1  TPSN算法分析

  TPSN算法采用的是层次型的网络结构,是基于发送者-接收者的双向同步算法。分成两个阶段,第一阶段为层次发现阶段,第二阶段为同步阶段。T1、T4用来记录同步节点的本地时间,T2、T3用来记录参考节点的本地时间。同步节点A在T1时刻向参考节点B发送一个同步请求报文,报文中包含了同步节点的级别和T1。当参考节点B收到报文后,记录下接收时刻T2,并立即向同步节点A回复一个同步应答报文,该报文中包含了参考节点B的级别和T1、T2及回复时刻T3。同步节点A收到参考节点的回复后,记下时刻T4。假设来回报文的传输延迟相同都为d,且m为同步节点在T1时刻两者之间的时偏,且设来回时偏相同,由T2=T1+m+d,T4=T3-m+d可得到:


  则在T4时刻,若在同步节点A的本地时间增加修正量m,就能达到同步节点A与参考节点B之间的同步。

  1.2.2  RBS算法分析

  RBS算法是基于接收者-接收者的同步算法。首先参考节点广播一个参考分组,当同步节点A收到这个分组,记下自己的本地时钟为T21,当同步节点B收到这个分组时,也记下自己的本地时钟为T22,然后同步节点A与同步节点B交换本地时钟T21与T22,这时其中一个节点只要根据时间差值m=T21-T22,修改自己的时钟就能达到与另一个节点之间的同步。在多跳网络中,RBS算法采用多次广播同步消息,接收节点根据接收到同步消息的平均值,同时采用最小平方线性回归方法进行线性拟合以减小同步误差。

  1.2.3  DMTS算法分析

  DMTS算法是基于发送者-接收者的单向时间同步算法。当发送节点在检测到通道空闲时,给广播分组加上时间戳t0,从而排除了发送节点的处理延迟与MAC层的访问延迟。并假设发送报文的长度为NA个比特(包括前导码与同步字),传送每个比特的时间为t,而接收者在接收完同步字后,记录下此时的本地时间为t1,并在调整自己的本地时间记录之前记录下此时的时刻t2,这时接收节点为了与发送节点达到时间上的同步,可以调整接收节点的时间改为t0+t·NA+(t2-t1)。

  可以看出,TPSN平均单跳误差为17.61μs,DMTS平均单跳误差为30μs,RBS平均单跳误差为6.29μs, TPSN平均4跳误差为21.43μs,DMTS平均单跳误差为151μs,RBS平均4跳误差为9.97μs。

  1.2.4  其他算法分析

  LTS协议是基于发送-接收同步机制发展而来,提出了集中式和分布式LTS多跳时间同步算法。LTS协议首先把网络组成广度优先生成树拓扑结构,并沿着树的每条边进行单跳成对同步。参考节点的子节点同步完成后,又以该节点为参考节点,采用同样方式继续同步下去,直到同步完成。

  单跳成对同步采用TPSN同步方法。成对同步的次数是边数的线性函数。Hui Dui等人提出来的HRTS 利用了广播的特性,只需要一次同步过程可以完成一个单跳组网所有节点的同步,进一步降低了LTS协议的功耗。HRTS算法不再采用广度优先生成树的边,采用的是广度优先生成树非叶子节点个数的线性函数。相较于LTS协议,HRTS算法以牺牲一定的精确来降低了整个网络的功耗。

  BTS同步方法类似于HRTS算法,也是先建立广度优先成生树拓扑结构,只不过BTS采用的是时间转换技术,以达到整个网络的时间同步,而HRTS直接对同步节点的本地时间进行修改,得到全网的同步,同步报文个数降为HRTS协议的2/3。

  PBS同步算法的思想是参考节点与簇首节点之间采用双向同步方法,与TPSN相似,其他节点(在两个节点的通信范围内)可以侦听到同步消息,就可以根据接收者-接收者同步方法同步。类似于RBS同步,PBS同步的前提是每个同步节点必须在簇首节点的通信范围之内。

  ETSP算法主要采用的是设置门槛值N来选择同步算法,当父节点的子节点小于或等于N时,采用接收-接收(RBS)同步模式,否则采用发送-接收(TPSN)同步模式。N值的选择采用N2-3N-2m=0来计算,式中m=RxTx,Rx为节点的接收次数,Tx为传播次数。

  FTSP同步算法精度高的原因是,发送者在发送一个同步请求报文时连续标记了多个时间戳,接收者可以根据这几个中断时间计算出更精确的时间偏差。

  1.2.5  协作同步技术

  以上同步机制,无论怎样改进都是基于单跳同步基制,最近有人提出了协作同步技术,不再单纯地从单跳同步机制上进行改进,而是通过信号叠加原理,使同步基准节点能够把同步消息直接发送到远方待同步的节点,使远方节点直接与基准节点同步,消除了同步误差单跳累加的结果。Hu A等人针对节点密度较高的网络提出了一种协作同步算法,基本思想是参考节点根据同步周期发出m个同步脉冲,其一跳邻居节点收到这个消息后保存起来,并根据最近的m个脉冲的发送时刻计算出参考节点的第m+1个同步消息发出的时间,并在计算出来的时刻同步与参考节点同时发送第m+1个同步消息。由于信号叠加,因此同步脉冲可以发送到更远的节点,当然前提是网络中节点密度较高的情况。A.Krohn等人提出了在物理层
物理层

  物理层是TCP/IP 网络模型的第一层,它虽然处于最底层,却是整个通信系统的基础, 正如高速公路和街道是汽车通行的基础一样。理层为设备之间的数据通信提供传输媒体及 互连设备,为数据传输提供可靠的环境。

上面实现协作同步,只需要本地消息,避免了额外的消息同步交换开销。因此节点密度越高同步误差也会越小。

  2  时间同步算法误差分析与比较

  根据节点消息传输过程可以得到式(1)与式(2):


  在式(1)、(2)中,t1、t2是由标准时钟所确定的,表示UTC时间。T1、T2分别是t1、t2所对应的本地节点所测出的本地时间。SA代表节点A的报文发送时间,AA是发送报文的访问时间,TA→B是A节点按比特传输报文与B节点按比特接收报文所需要的时间,PA→B是节点A传播到节点B的时间。RB是节点B的报文接收处理过程时间。TNA是传输NA个比特的总时间。terror指传输比特的误差,Rerror打时标过程存在的误差。DA→Bt1代表节点A与节点B在t1时刻的时偏。

  对于TPSN算法,因为在MAC采用了加时间戳方法,因此消除了发送时间与访问时间对误差的影响。因此对TPSN算法式(1)、(2)就可以简写为式(3)、(4):

 


 

  式中DA→Bt1=DA→Bt4+RDA→Bt1→t4。

  同理可以得到T4,如下所示:


 

  由以上各式可以得到时偏:


 

  RDA→Bt1→t4代表从t1到t4时段内,节点A相对于节点B增加的时偏。DA→Bt4是t4时刻节点A与节点B之间的时偏。则可以算出TPSN的同步误差:


 

  式中SUC=SA-SB,PUC=PA→B-PB→A,RUC=RB-RA。

  对于DMTS算法,发送节点A在T0时刻检测到空闲,接收节点B在报文到达时刻给报文加上时间戳T1,并在调整自己的本地时间记录之前记录下此时的时刻为T2,在T3时间完成调整。则可以得到:

   式中DA→Bt0=DA→Bt3+RDA→Bt0→t3。

  由TmA→B+RB=n·t+Terror+Rerror+(T2-T1),其中n是前导码的长度,可以得到DMTS的时偏:



  DMTS的误差为:

 
 

  对于RBS同步算法,可以得到:



 

  则由式(8)与式(9)可以得到节点B的时偏m1为:


 

  则可以得到节点B的同步误差为:


 


  从式(7)中可以看出,TPSN同步精度高的原因是在MAC层采用打时标方式消除了发送时间与访问时间的影响,并在消息双方向交换时消除了传播时间的影响。缺点是点到点之间的同步,每次只能一对节点进行时间同步,同步一次需要发送2个消息,接收2个消息,功耗较大。从式(10)可以看出DMTS同步误差较大的原因是单播传播,没办法消除Terror 与Rerror的影响,但DMTS同步一次只要消耗1个发送消息,1个接收消息,功耗较低。至于FTSP同步算法比DMTS高的原因是,发送者在发送一个同步请求报文时连续标记了多个时间戳,接收者可以根据这几个中断时间,计算出更精确的时间偏差。可以看出,RBS完全消除了发送方的影响,只是同步一次消耗3个发送消息,4个接收消息,功耗较大。而对于HRTS与PBS算法,都是其于以上算法进行融合运用,在簇首节点与子网节点选择上作了较大的改进,以降低整个网络的功耗。

  3  总结与展望

  从以上同步算法的误差分析比对中可以看出,每种算法都有各自的优缺点,都适合不同的无线传感网络。精度高,相对功耗也较大。对特定的无线传感网络,选择同步算法时应该折中考虑精度与功耗。从整体上看,近年来有关时间同步算法的研究,大部分都是基于以往典型的单跳同步算法原理,进一步从整体网络中考虑误差与功耗,结合最优生成树、分簇路由算法等,以平均整个网络的功耗,降低节点传输的跳数,提高同步的精度。协作同步算法侧重于提高整个网络的可扩展性与健壮性,但要求节点具有相同的同步脉冲,比较困难,目前还需要进一步的发展验证,也是未来可能很好的发展方向。


 

继续阅读>>