无线传感网络时间同步研究进展与分析
Elson等人2002年首次提出无线传感器网络时间同步的研究课题以来，已有相当多的典型时间同步算法，主要可以分为以下几类：基于发送者一接收者的双向同步算法，典型算法如TPSN(Timing-Sync Protocol for Sensor Networks)算法；基于发送者一接收者的单向时间同步算，典型算法如FTSP(Flooding Time Synclaronization Protocol)算法、DMTS(Delay Measurement Time Synchronization)算法；基于接收者一接收者的同步算法，典型算法有RBS(Reference Broadcast Synchronization)算法。
近年来根据以上几种典型同步算法，还有人提出了分簇式的层次型拓扑结构算法，以及结合生成树等来提高整个网络的性能，如LTS(Li-glatweight time synchronization)算法、CHTS(Cluster-based Hierarehical Time Synchronization)算法、CRIT(Chained-Ripple Time Synchronization)算法、PBS(The Pairwise Broadcast Synchronization)算法、HRTS(Hierarchy ReferencingTime Synchronization Pro-toc01)算法、BTS(Broadcasttime synchronization)算法、ETSP(Energy-efficient Time Synchronization Protocol)算法等。
然而，无论以上同步算法怎样发展，精度如何提高，整个网络功耗怎样降低，都是基于单跳时间同步机制。随着无线传感网络的运用与发展，传感节点体积不断缩小，单跳距离变小，整体网络规模变大，同步误差的累积现象必将越来越严重，目前也有比较新的同步算法，试图尽量避开单跳累加来解决这些问题，如协作同步。
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)。
从参考文献中，可以看出，文章作者在加州大学伯克利分校的Mica节点上测试过，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值的选择采用
来计算，式中m=Rx/Tx，Rx为节点的接收次数，Tx为传播次数。
FTSP同步算法精度高的原因是，发送者在发送一个同步请求报文时连续标记了多个时间戳，接收者可以根据这几个中断时间计算出更精确的时间偏差。
1．2．5 协作同步技术
以上同步机制，无论怎样改进都是基于单跳同步基制，最近有人提出了协作同步技术，不再单纯地从单跳同步机制上进行改进，而是通过信号叠加原理，使同步基准节点能够把同步消息直接发送到远方待同步的节点，使远方节点直接与基准节点同步，消除了同步误差单跳累加的结果。Hu A等人针对节点密度较高的网络提出了一种协作同步算法，基本思想是参考节点根据同步周期发出m个同步脉冲，其一跳邻居节点收到这个消息后保存起来，并根据最近的m个脉冲的发送时刻计算出参考节点的第m+1个同步消息发出的时间，并在计算出来的时刻同步与参考节点同时发送第m+1个同步消息。由于信号叠加，因此同步脉冲可以发送到更远的节点，当然前提是网络中节点密度较高的情况。A．Kr-ohn等人提出了在物理层上面实现协作同步，只需要本地消息，避免了额外的消息同步交换开销。参考文献证实了协作同步误差的方差与节点密度呈反比关系。因此节点密度越高同步误差也会越小。
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的报文接收处理过程时间。TN是传输NA个比特的总时间。Terror指传输比特的误差，Rerror打时标过程存在的误差。
代表节点A与节点B在t1时刻的时偏。
对于TPSN算法，因为在MAC采用了加时间戳方法，因此消除了发送时间与访问时间对误差的影响。因此对TPSN算法式(1)、(2)就可以简写为式(3)、(4)：
对于DMTS算法，发送节点A在T0时刻检测到空闲，接收节点B在报文到达时刻给报文加上时间戳T1，并在调整自己的本地时间记录之前记录下此时的时刻为T2，在T3时间完成调整。则可以得到：
从式(7)中可以看出，TPSN同步精度高的原因是在MAC层采用打时标方式消除了发送时间与访问时间的影响，并在消息双方向交换时消除了传播时间的影响。缺点是点到点之间的同步，每次只能一对节点进行时间同步，同步一次需要发送2个消息，接收2个消息，功耗较大。从式(10)可以看出DMTS同步误差较大的原因是单播传播，没办法消除Terror与Rerror的影响，但DMTS同步一次只要消耗1个发送消息，1个接收消息，功耗较低。至于FTSP同步算法比DMTS高的原因是，发送者在发送一个同步请求报文时连续标记了多个时间戳，接收者可以根据这几个中断时间，计算出更精确的时间偏差。可以看出，RBS完全消除了发送方的影响，只是同步一次消耗3个发送消息，4个接收消息，功耗较大。而对于HRTS与PBS算法，都是其于以上算法进行融合运用，在簇首节点与子网节点选择上作了较大的改进，以降低整个网络的功耗。
3 总结与展望
从以上同步算法的误差分析比对中可以看出，每种算法都有各自的优缺点，都适合不同的无线传感网络。精度高，相对功耗也较大。对特定的无线传感网络，选择同步算法时应该折中考虑精度与功耗。从整体上看，近年来有关时间同步算法的研究，大部分都是基于以往典型的单跳同步算法原理，进一步从整体网络中考虑误差与功耗，结合最优生成树、分簇路由算法等，以平均整个网络的功耗，降低节点传输的跳数，提高同步的精度。协作同步算法侧重于提高整个网络的可扩展性与健壮性，但要求节点具有相同的同步脉冲，比较困难，目前还需要进一步的发展验证，也是未来可能很好的发展方向。