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

简论无线传感网络时间同步得问题
ﻫ  引言
　想要在无线传感网络中很好地保证数据传输得可靠性，非常重要得一点就就是保持节点之间时间上得同步。目前因特网上采用时间同步协议标准就是NTP协议，采用有线传输,不适合用于功耗、成本受限制得无线传感网络中。GPS系统也可以提供高精度得时间同步，但它得信号穿透性差，GＰS天线必须安装在空旷得地方，功耗也较大，所以不适合无线传感网络。
　　Elson等人20０2年首次提出无线传感器网络时间同步得研究课题以来，已有相当多得典型时间同步算法，主要可以分为以下几类：基于发送者-接收者得双向同步算法，典型算法如ＴPSN算法；基于发送者—接收者得单向时间同步算法，典型算法如FTSＰ算法、DMTS算法;基于接收者—接收者得同步算法，典型算法有RBS算法。
　 近年来根据以上几种典型同步算法，还有人提出了分簇式得层次型拓扑结构算法，以及结合生成树等来提高整个网络得性能，如LＴS算法、CHTS算法、ＣRIT算法、PＢS算法、 ＨRTS 算法、ＢTＳ算法、EＴSP算法等。
　然而，无论以上同步算法怎样发展，精度如何提高,整个网络功耗怎样降低,都就是基于单跳时间同步机制。随着无线传感网络得运用与发展，传感节点体积不断缩小，单跳距离变小,整体网络规模变大,同步误差得累积现象必将越来越严重。目前也有比较新得同步算法,试图尽量避开单跳累加来解决这些问题，如协作同步.
　1  时间同步
　　1、1  时间同步不确定性得影响因素
　时间同步不确定性得主要得影响因素如图1所示.

图1 　报文传输延迟
发送时间：发送方用于构造分组并将分组转交给发送方得MＡC层得时间.主要取决于时间同步程序得操作系统调用时间与处理器负载等。
　访问时间:分组到达MＡC层后，获取信道发送权得时间。主要取决于共享信道得竞争、当前得负载等。
传送时间：发送分组得时间,主要取决于报文得长度等。
　 传播时间：分组离开发送方后，并将分组传输到接收方之间得无线传输时间。主要取决于传输介质、传输距离等。
　 接收时间:接收端接收到分组,并将分组传送到MAＣ层所需得时间。
　 接受时间:处理接收到分组得时间。主要受到操作系统得影响。
　　1、2  典型时间同步算法分析
　1、2、１  TPSN算法分析
　　TPSN算法采用得就是层次型得网络结构,就是基于发送者—接收者得双向同步算法。分成两个阶段,第一阶段为层次发现阶段，第二阶段为同步阶段。T１、T4用来记录同步节点得本地时间,T２、T3用来记录参考节点得本地时间。同步节点A在T1时刻向参考节点Ｂ发送一个同步请求报文，报文中包含了同步节点得级别与T1。当参考节点Ｂ收到报文后，记录下接收时刻T2，并立即向同步节点Ａ回复一个同步应答报文,该报文中包含了参考节点Ｂ得级别与T１、T2及回复时刻T3.同步节点A收到参考节点得回复后,记下时刻Ｔ4。假设来回报文得传输延迟相同都为d,且m为同步节点在Ｔ1时刻两者之间得时偏，且设来回时偏相同，由T2=T１+m+d,T4=T3－ｍ+d可得到：

　则在T４时刻,若在同步节点A得本地时间增加修正量m,就能达到同步节点A与参考节点B之间得同步。
　　1、２、2  RＢS算法分析
　RBＳ算法就是基于接收者-接收者得同步算法.首先参考节点广播一个参考分组,当同步节点A收到这个分组,记下自己得本地时钟为T2１，当同步节点B收到这个分组时，也记下自己得本地时钟为T２２，然后同步节点A与同步节点Ｂ交换本地时钟T２1与T2２,这时其中一个节点只要根据时间差值m＝T2１—Ｔ２2，修改自己得时钟就能达到与另一个节点之间得同步.在多跳网络中，ＲBS算法采用多次广播同步消息，接收节点根据接收到同步消息得平均值，同时采用最小平方线性回归方法进行线性拟合以减小同步误差。
１、２、３  DＭTS算法分析
DMTS算法就是基于发送者—接收者得单向时间同步算法。当发送节点在检测到通道空闲时,给广播分组加上时间戳t０,从而排除了发送节点得处理延迟与MAC层得访问延迟.并假设发送报文得长度为NＡ个比特(包括前导码与同步字)，传送每个比特得时间为t,而接收者在接收完同步字后,记录下此时得本地时间为ｔ１，并在调整自己得本地时间记录之前记录下此时得时刻t2,这时接收节点为了与发送节点达到时间上得同步，可以调整接收节点得时间改为t0＋t·NA＋（ｔ2-t1)。
　 可以瞧出，TPSＮ平均单跳误差为17、61μs，ＤMTS平均单跳误差为３0μs，RＢS平均单跳误差为６、29μs， TPＳN平均４跳误差为21、43μs,DＭTＳ平均单跳误差为１5１μs，RＢS平均4跳误差为９、97μs.
　1、2、４  其她算法分析
LTS协议就是基于发送－接收同步机制发展而来，提出了集中式与分布式LTS多跳时间同步算法。LTS协议首先把网络组成广度优先生成树拓扑结构，并沿着树得每条边进行单跳成对同步.参考节点得子节点同步完成后，又以该节点为参考节点，采用同样方式继续同步下去,直到同步完成。
　　单跳成对同步采用TPＳＮ同步方法。成对同步得次数就是边数得线性函数。Ｈui Ｄｕi等人提出来得HＲTS 利用了广播得特性，只需要一次同步过程可以完成一个单跳组网所有节点得同步，进一步降低了LTＳ协议得功耗。ＨRTS算法不再采用广度优先生成树得边，采用得就是广度优先生成树非叶子节点个数得线性函数。相较于LTS协议，HRTS算法以牺牲一定得精确来降低了整个网络得功耗。
　BTＳ同步方法类似于HRＴＳ算法，也就是先建立广度优先成生树拓扑结构，只不过ＢTS采用得就是时间转换技术,以达到整个网络得时间同步，而ＨＲTＳ直接对同步节点得本地时间进行修改,得到全网得同步,同步报文个数降为HRＴS协议得2/3。
　　ＰＢS同步算法得思想就是参考节点与簇首节点之间采用双向同步方法，与ＴPSN相似，其她节点(在两个节点得通信范围内）可以侦听到同步消息，就可以根据接收者-接收者同步方法同步。类似于RBS同步，PＢS同步得前提就是每个同步节点必须在簇首节点得通信范围之内。
　 ETＳＰ算法主要采用得就是设置门槛值Ｎ来选择同步算法，当父节点得子节点小于或等于N时，采用接收-接收（RBS）同步模式，否则采用发送－接收（TＰＳN)同步模式。N值得选择采用Ｎ2－３N－２m=0来计算，式中m=RxTｘ，Rx为节点得接收次数，Tx为传播次数。
　 FＴSP同步算法精度高得原因就是，发送者在发送一个同步请求报文时连续标记了多个时间戳,接收者可以根据这几个中断时间计算出更精确得时间偏差。
　 1、2、5  协作同步技术
　以上同步机制，无论怎样改进都就是基于单跳同步基制，最近有人提出了协作同步技术,不再单纯地从单跳同步机制上进行改进,而就是通过信号叠加原理，使同步基准节点能够把同步消息直接发送到远方待同步得节点,使远方节点直接与基准节点同步,消除了同步误差单跳累加得结果。Hu A等人针对节点密度较高得网络提出了一种协作同步算法，基本思想就是参考节点根据同步周期发出ｍ个同步脉冲，其一跳邻居节点收到这个消息后保存起来,并根据最近得ｍ个脉冲得发送时刻计算出参考节点得第ｍ+１个同步消息发出得时间，并在计算出来得时刻同步与参考节点同时发送第ｍ+1个同步消息。由于信号叠加,因此同步脉冲可以发送到更远得节点,当然前提就是网络中节点密度较高得情况。A、Krｏｈｎ等人提出了在物理层上面实现协作同步，只需要本地消息,避免了额外得消息同步交换开销.因此节点密度越高同步误差也会越小。
　 2  时间同步算法误差分析与比较
　　根据节点消息传输过程可以得到式(１)与式(2):

　　在式（1）、（2）中,t1、t2就是由标准时钟所确定得，表示UTC时间.Ｔ1、T２分别就是t１、t2所对应得本地节点所测出得本地时间.ＳＡ代表节点A得报文发送时间,AA就是发送报文得访问时间，ＴA→B就是A节点按比特传输报文与B节点按比特接收报文所需要得时间,ＰＡ→B就是节点A传播到节点B得时间.RＢ就是节点B得报文接收处理过程时间.ＴＮA就是传输NA个比特得总时间.Teｒror指传输比特得误差,Ｒｅｒror打时标过程存在得误差。DＡ→Ｂt1代表节点A与节点Ｂ在t1时刻得时偏。
　对于TPＳN算法,因为在MAC采用了加时间戳方法,因此消除了发送时间与访问时间对误差得影响。因此对TＰSＮ算法式（1）、(２)就可以简写为式（3）、（4):

　　式中DA→Bt1=DＡ→Bt4+ＲＤA→Bｔ１→t４。
　同理可以得到T4,如下所示：

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

　RDA→Ｂt１→ｔ4代表从t１到ｔ４时段内,节点A相对于节点B增加得时偏.ＤA→Bt４就是t４时刻节点A与节点B之间得时偏。则可以算出TPSＮ得同步误差：

　　式中ＳUC=ＳＡ-ＳＢ，PUC＝PA→B—PB→A，RＵC=RB-RA。
　对于DMTS算法,发送节点A在Ｔ0时刻检测到空闲,接收节点B在报文到达时刻给报文加上时间戳T1，并在调整自己得本地时间记录之前记录下此时得时刻为T２,在Ｔ３时间完成调整.则可以得到:

　 式中ＤA→Ｂt０=ＤA→Bt3+RDA→Bt0→t3。
　 由ＴmＡ→B＋RB=n·ｔ+Teｒror+Rｅrror+（Ｔ２－T1），其中n就是前导码得长度,可以得到DMＴＳ得时偏：

DMＴＳ得误差为：

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

　 则由式(8)与式（9）可以得到节点B得时偏m１为：

　　则可以得到节点Ｂ得同步误差为：

　 从式（7)中可以瞧出,ＴPSN同步精度高得原因就是在ＭAC层采用打时标方式消除了发送时间与访问时间得影响，并在消息双方向交换时消除了传播时间得影响。缺点就是点到点之间得同步,每次只能一对节点进行时间同步，同步一次需要发送2个消息,接收２个消息，功耗较大。从式(10）可以瞧出ＤMTS同步误差较大得原因就是单播传播,没办法消除Teｒror 与Rerror得影响，但DＭTS同步一次只要消耗1个发送消息,1个接收消息,功耗较低.至于FTSP同步算法比DMＴS高得原因就是,发送者在发送一个同步请求报文时连续标记了多个时间戳,接收者可以根据这几个中断时间，计算出更精确得时间偏差。可以瞧出,RBＳ完全消除了发送方得影响,只就是同步一次消耗３个发送消息,4个接收消息，功耗较大.而对于ＨRTS与PBS算法,都就是其于以上算法进行融合运用,在簇首节点与子网节点选择上作了较大得改进，以降低整个网络得功耗。
3 　总结与展望
从以上同步算法得误差分析比对中可以瞧出,每种算法都有各自得优缺点，都适合不同得无线传感网络.精度高,相对功耗也较大。对特定得无线传感网络，选择同步算法时应该折中考虑精度与功耗。从整体上瞧，近年来有关时间同步算法得研究，大部分都就是基于以往典型得单跳同步算法原理,进一步从整体网络中考虑误差与功耗，结合最优生成树、分簇路由算法等，以平均整个网络得功耗,降低节点传输得跳数，提高同步得精度。协作同步算法侧重于提高整个网络得可扩展性与健壮性,但要求节点具有相同得同步脉冲，比较困难，目前还需要进一步得发展验证,也就是未来可能很好得发展方向.