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

简论无线传感网络时间同步的问题引言想要在无线传感网络中很好地保证数据传输的牢靠性,特别重要的一点就是保持节点之间时间上的同步。目前因特网上采纳时间同步合同标准是MrP合同，采纳有线传输，不适合用于功耗、成本受限制的无线传感网络中。些系统也可以供应高精度的时间同步，但它的信号穿透性差，GPS天线必需安装在空旷的地方，功耗也较大，所以不适合无线传感网络。EISon等人2002年首次提出无线传感器网络时间同步的讨论课题以来,己有相当多的典型时间同步算法，主要可以分为以下几类：基于发送者-接收者的双向同步算法，典型算法如TPSN算法；基于发送者-接收者的单向时间同步算法，典型算法如FTSP算法、DMTS算法；基于接收者-接收者的同步算法，典型算法有RBS算法。近年来依据以上几种典型同步算法，还有人提出了分簇式的层次型拓扑结构算法，以及结合生成树等来提高整个网络的性能，如LTS算法、CHTS算法、CRIT算法、PBS算法、HRTS算法、BTS算法、ETSP算法等。然而，无论以上同步算法怎样进展，精度如何提高，整个网络功耗怎样降低，都是基于单跳时间同步机制。随着无线传感网络的运用与进展，传感节点体积不断缩小，单跳距离变小，整体网络规模变大，同步误差的累积现象必将越来越严峻。目前也有比较新的同步算法,试图尽量避开单跳累加来解决这些问题，如协作同步。1 时间同步1.1 时间同步不确定性的影响因素时间同步不确定性的主要的影响因素如图1所示。发送时间I访问时间,一时间I传播时间接收时间I接变丽1图1报文传输延迟发送时间：发送方用于构造分组并将分组转交给发送方的MAC层的时间。主要取决于时间同步程序的操作系统调用时间和处理圈负载等。访问时间：分组到达MAC层后，猎取信道发送权的时间。主要取决于共享信道的竞争、当前的负载等。传送时间：发送分组的时间，主要取决于报文的长度等。传播时间：分组离开发送方后，并将分组传输到接收方之间的无线传输时间。主要取决于传输介质、传输距离等。接收时间：接收端接收到分组，并将分组传送到MAC层所需的时间。接受时间：处理接收到分组的时间。主要受到操作系统的影响。1.2 典型时间同步算法分析TPSN算法分析TPSN算法采纳的是层次型的网络结构，是基于发送者-接收者的双向同步算法。分成两个阶段，第一阶段为层次发觉阶段，其次阶段为同步阶段。TbT4用来纪录同步节点的木地时间，T2、T3用来纪录参考节点的本地时间。同步节点A在TI时刻向参考节点B发送一个同步恳求报文，报文中包含了同步节点的级别和Tl。当参考节点B收到报文后，纪录下接收时刻T2,并马上向同步节点A回复一个同步应答报文，该报文中包含了参考节点B的级别和Tl、T2及同复时刻T3。同步节点A收到参考节点的回复后，登记时刻T4。假设来回报文的传输延迟相同都为d,且In为同步节点在TI时刻两者之间的时偏，且设来回时偏相同，由T2=Tl+m+d,T4=T3-m+d可得到：则在T4时刻，若在同步节点A的本地时间增加修正量m,就能达到同步节点A与参考节点B之间的同步。RBS算法分析RBS算法是基于接收者-接收者的同步算法。首先参考节点广播一个参考分组，当同步节点A收到这个分组，登记自己的本地时钟为T21,当同步节点B收到这个分组时，也登记自己的本地时钟为T22,然后同步节点A与同步节点B交换本地时钟T21与T22,这时其中一个节点只要依据时间差值m=T21-T22,修改自己的时钟就能达到与另一个节点之间的同步。在多跳网络中，RBS算法采纳多次广播同步消息，接收节点依据接收到同步消息的平均值，同时采纳最小平方线性回归方法进行线性拟合以减小同步误差。DMTS算法分析DMTS算法是基于发送者-接收者的单向时间同步算法。当发送节点在检测到通道空闲时，给广播分组加上时间戳t,从而排解了发送节点的处理延迟与MAC层的访问延迟。并假设发送报文的长度为NA个比特（包括前导码与同步字），传送每个比特的时间为t,而接收者在接收完同步字后，纪录下此时的本地时间为tl,并在调整自己的本地时间纪录之前纪录下此时的时刻t2,这时接收节点为了与发送节点达到时间上的同步，可以调整接收节点的时间改为t+tNA+(t2-tl)o可以看出，TPSN平均单跳误差为17.61s,DMTS平均单跳误差为30s,RBS平均单跳误差为6.29s,TPSN平均4跳误差为21.43Us,DMTS平均单跳误差为151s,RBS平均4跳误差为9.97USo其他算法分析1.TS合同是基于发送-接收同步机制进展而来，提出了集中式和分布式LTS多跳时间同步算法。LTS合同首先把网络组成广度优先生成树拓扑结构，并沿着树的每条边进行单跳成对同步。参考节点的子节点同步完成后，又以该节点为参考节点，采纳同样方式连续同步下去，直到同步完成。单跳成对同步采纳TPSN同步方法。成对同步的次数是边数的线性函数。UuiDUi等人提出来的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同步算法精度高的缘由是，发送者在发送一个同步恳求报文时连续标记了多个时间戳，接收者可以依据这几个中断时间计算出更精确的时间偏差。协作同步技术以上同步机制，无论怎样改进都是基于单跳同步基制，最近有人提出了协作同步技术，不再单纯地从单跳同步机制上进行改进，而是通过信号叠加原理，使同步基准节点能够把同步消息直接发送到远方待同步的节点，使远方节点直接与基准节点同步，消退了同步误差单跳累加的结果。HUA等人针对节点密度较高的网络提出了一种协作同步算法，基本思想是参考节点依据同步周期发出m个同步脉冲，其一跳邻居节点收到这个消息后保存起来，并依据最近的m个脉冲的发送时刻计算出参考节点的第m+1个同步消息发出的时间，并在计算出来的时刻同步与参考节点同时发送第m+1个同步消息。由于信号叠加，因此同步脉冲可以发送到更远的节点，当然前提是网络中节点密度较高的状况。A.Krohn等人提出了在物理层上面实现协作同步，只需要本地消息，避开了额外的消息同步交换开销。因此节点密度越高同步误差也会越小。2 时间同步算法误差分析与比较依据节点消息传输过程可以得到式（1）与式（2）：“=h-Sa-Aa-Tab-PAT-七（1）T2=TI+Sa-Aa+T、.+TE+R.e-Paz=Rb+4（2）在式（1）、（2）中，tl、t2是由标准时钟所确定的，表示UTC时间。Tl、T2分别是11、t2所对应的本地节点所测出的本地时间。SA代表节点A的报文发送时间，AA是发送报文的访问时间，TAiB是A节点按比特传输报文与B节点按比特接收报文所需要的时间，PA一B是节点A传播到节点B的时间。RB是节点B的报文接收处理过程时间。TNA是传输NA个比特的总时间。TerrOr指传输比特的误差，RerrOr打时标过程存在的误差。DAiBtI代表节点A与节点B在tl时刻的时偏。对于TPSN算法，由于在MAC采纳了加时间戳方法，因此消退了发送时间与访问时间对误差的影响。因此对TPSN算法式（1）、（2）就可以简写为式（3）、（4）：n=L-SaPAiB-Rb（3）T?=T-a-b+K-DLi（4）式中DAfBtl=DAfBt4+RDAfBtl-t40同理可以得到T4,如下所示：T4=Ts-Sb+Pa÷Ra-X7a（5）由以上各式可以得到时偏：（Tj-Tl）"（T4-Ts）Sa-S8m三=RDAiBtlit4代表从tl到t4时段内，节点A相对于节点B增加的时偏。DAiBt4是t4时刻节点A与节点B之间的时偏。则可以算出TPSN的同步误差：EE=m-TV=华一粤+春一(7)式中SUC=SA-SB,PUC=PAfB-PB-A,RUC=RB-RAo对于DMTS算法，发送节点A在TO时刻检测到空闲，接收节点B在报文到达时刻给报文加上时间戳Tl,并在调整自己的本地时间纪录之前纪录下此时的时刻为T2,在T3时间完成调整。则可以得到：TS=TC+TPAj+Rb-忧7(8)式中DAiBtO=DAfBt3+RDAfBtO-13。由TmAfB+RB=nt+Terror+Rerror+(T2-T1),其中n是前导码的长度，可以得到DMTS的时偏：m=P-Te+RB+Dh-RD：(9)DMTS的误差为：Error=m-中Ii=Pah-Te-Rmr÷R忧二：(10)对于RBS同步算法，可以得到：=T1一SB-ABT、Pi-R（三）=R-Sb+Ab+T-Pxc+RC-DrC(12)则由式(8)与式(9)可以得到节点B的时偏ml为：m：=T22-T21=(PICPi)一(Rc-Ra)÷(DC-DTa)(13)Dr-=K-C=XY+(14)则可以得到节点B的同步误差为：Error=m1-*°=(P&*c-Pi)÷(Rc-RA)÷RDf(15)IU从式(7)中可以看出，TPSN同步精度高的缘由是在MAC层采纳打时标方式消退了发送时间与访问时间的影响，并在消息双方向交换时消退了传播时间的影响。缺点是点到点之间的同步，每次只能一对节点进行时间同步，同步一次需要发送2个消息，接收2个消息，功耗较大。从式(10)可以看出DMTS同步误差较大的缘由是单播传播，没方法消退Terror与Rerror的影响，但DMTS同步一次只要消耗1个发送消息，1个接收消息，功耗较低。至于FTSP同步算法比DMTS高的缘由是，发送者在发送一个同步恳求报文时连续标记了多个时间戳，接收者可以依据这几个中断时间，计算出更精确的时间偏差。可以看出，RBS完全消退了发送方的影响，只是同步一次消耗3个发送消息，4个接收消息，功耗较大。而对于HRTS与PBS算法，都是其于以上算法进行融合运用，在簇首节点与子网节点选择上作了较大的改进，以降低整个网络的功耗。3 总结与展望从以上同步算法的误差分析比对中可以看出，每种算法都有各自的优缺点，都适合不同的无线传感网络。精度高，相对功耗也较大。对特定的无线传感网络，选择同步算法时应当折中考虑精度与功耗。从整体上看，近年来有关时间同步算法的讨论，大部分都是基于以往典型的单跳同步算法原理，进一步从整体网络中考虑误差与功耗，结合最优生成树、分簇路由算法等，以平均整个网络的功耗，降低节点传输的跳数，提高同步的精度。协作同步算法侧重于提高整个网络的可扩展性与健壮性，但要求节点具有相同的同步脉冲，比较困难，目前还需要进一步的进展验证，也是将来可能很好的进展方向。