基于高斯模型的DMTS时间同步算法研究

郑顾平 马粤

摘 要：无线传感网络的时间同步算法中，DMTS算法简单，能耗小，但其精度和稳定性不好。在DMTS的基础上，分析数据传输中时延构成，采用高斯模型对时延建模，利用最大似然估计法得到时间偏差的无偏估计。提出EDMTS算法，使用CC2430进行物理实验，实验表明EDMTS相比DMTS具有更高的精度和稳定性。

关键词：无线传感网络 时间同步 高斯分布 延迟时间测量

中图分类号：TN915.9 文献标识码：A 文章编号：1007-3973（2013）009-125-03

1 引言

无线传感网络（WSN，Wireless Sensor Networks）是一种分布式的无线自组织网络，时间同步对于无线传感网络的应用具有极其重要的意义。如，信息传输调度需要时分多址 （Time division multiple access，TDMA）技术支撑；在功率管理中，传感器网络中的节点大部分时间处于休眠状态，协同处理任务时需要同步激活，同步采样等；定位、安全和跟踪协议等需要节点在数据包中添加时间戳。

目前，无线传感器网络时间同步方法的研究，概括起来可以分为以下四类：（1）基于发送者的同步模型，典型算法有基于延迟测量的DMTS（Delay Measurement Time Synchronization，延迟测量时间同步）算法和基于泛洪的FTSP算法；（2）基于发送者、接受者交互的同步模型，典型的如NTP、TPSN算法；（3）基于接收者、接受者交互的同步模型，典型的是RBS算法和Adaptive RBS；（4）基于仿生结构的算法，典型的如萤火虫同步算法。

较之四类时间同步方法，DMTS算法简单，能量效率高，它使用一个单向的数据包即可完成同步，但是它的同步精度较低，稳定性不好，本文在DMTS算法基础上引入高斯时延，利用最大似然估计得到时钟偏差的估计。提出改进的EDMTS算法，实验证明，本算法较DMTS算法具有更高的精度和更好的稳定性，点对点误差在1微秒至3微秒。双跳网络中，同步误差在1微秒至4微秒之间。相较其它类同步算法，本算法具有同步信息量少的优点。

2 DMTS算法原理

DMTS算法的原理为，发送节点在发送信道空闲时，在MAC层给广播分组加上时间戳t0。发送正式数据分组前，发送节点先发送前导码和起始字符，以便接收节点进行同步，根据发送的信息位个数n和发送每比特位所需要的时间n ，可以估计发送前导码和起始字符的时间为n 。接收节点在数据分组接收完成时刻加上时间戳t1，在接收的数据分组经过MAC层和应用层处理后，获得时间戳t2，这样接收端的接收处理延迟就是t2-t1。若忽略无线信号的传播延迟，接收节点从t0时刻计算的话，在调整自身时钟前的处理延迟为n +（t2-t1）。因此接收节点为了与发送节点时钟同步，就调整其时钟为t0+n +（t2-t1）。

对于多跳网络，需要进行分层并进行主节点选举。假设网络分为n层，分层结构为（L0，L1，…，Ln），其中L0仅包含主节点。先同步L0至L1，再让L1构成L2的主节点，同步L1至L2，以此类推，直到Ln同步完成。

3 无线网络时延分析

无线网络中的时延可以分为几个不同部分：

发送时延：应用层建立信息的时间，能够达到数百微秒量级。

接入时延：应用层信息用于接入信道的等待时间，一般在微秒到秒之间变化。

传输时延：与信息长度和在介质中无线电传播速度相关，一般为几十微秒的量级。

传播时延：无线信道中从发送端到接收端的时间，一般少于1 s，可忽略不计。

物理层接收时延：接收端物理层接受信息的时间，一般和传输时延相同。

上层接收时延：上层接收处理的时延。

这些延时部分又可分为固定时延和可变时延。可变时延取决于各种网络参数，人们已经提出了多个随机时延的概率密度函数，其中最广泛应用的是高斯、伽马、指数和韦氏概率密度函数。一般认为时延和测量误差由大量独立随机过程构成，根据中心极限定理，总的时延和各种误差之和适合选用高斯模型，延时的可变部分能以99.8%的可信度被建模为高斯分布随机变量。实际无线网络环境中存在许多干扰或碰撞，必定会有各种延迟。DMTS忽略这些时间延迟从而导致同步算法精度较低和不稳定。为了提高精度和稳定性，同时利用DMTS的简单、能量效率高的优势，在DMTS中引入时间延迟参数，对其采用高斯模型建模，由此提出EDMTS算法。

4 EDMTS算法

4.1 EDMTS算法原理

加入时间延迟后的同步模型为：t1= t0+n + +X，其中，n 为前导码和起始字符的发送时间， 为两个时钟节点之间的时钟偏移，X为时间延迟，服从高斯分布。t0为主节点发送时刻，t1为从节点MAC层数据接受完成时刻。

假设主节点和从节点之间同步了N次，则第i次交换的时间关系如下：t1i= t0i+n + +Xi，其中，n 为前导码和起始字符的发送时间， 为两个节点之间的时钟偏移，Xi为第i次同步时的随机延迟，服从高斯分布。t0i为第i次同步时主节点发送时刻，t1i为第i次同步时从节点MAC层数据接受完成时刻。

（3）获取本地时间t2，设置自身时钟为t0N + y + （t2-t1N），其中，t0N和t1N是最后一个同步包内t0和t1时刻的信息，补偿（t2-t1N）是为了消除算法计算时间导致的误差。

本算法的时间复杂度为 （n）。需要总数为N*M （M为t0和t1存储长度）的存储空间。假设采用64位二进制表示时间，则M为128位。无线传感网络节点能量有限，同步数据包不宜过多，实践中N一般小于20。故需要的最大存储空间为160字节，现代嵌入式系统完全能够满足这个空间需求。

5 实验

首先，使用Matlab仿真分析同步次数N与误差的关系。仿真采用一个主节点与50个从节点，仿真参数为 =13， =1， =5000（ s），n =50（ s）。统计各从节点时钟偏移计算结果的误差均值，结果如图1所示，横坐标为同步次数N，纵坐标为误差的绝对值。试验结果表明，同步次数增加使得误差呈指数型减小。

然后仿真分析EDMTS与DMTS的准确度关系，同样采用上述参数，分别仿真DMTS、同步3个、5个、7个数据包的情况。仿真结果与图1一致的，即随着同步次数的增加，误差快速减小。可以看出，DMTS误差较大。加入时延参数进行统计分析后，精度快速提升。当同步5个数据包时，误差仅为DMTS算法的1/2。

在CC2430平台上对本算法进行验证。CC2430是德州仪器（TI）公司的无线传感网络产品，在工程应用中非常广泛，TI公司提供了完整的说明文档和开发包，可以很方便地实现硬件级功能，如在数据包经过MAC后添加时间戳。

采用两个节点，每个节点采用STM32F103ZE主控芯片，CC2430为无线收发器。STM32F10系列芯片为ARM Cortex-M3架构，主频72MHz，具有很高的处理速度和中断响应速度。节点A作为主节点，连接GPS，接收高精度时间信号，在GPS的1PPS（秒脉冲）信号控制下，按照预定同步间隔发送同步信息。节点B为从节点，同样连接GPS，用于同步测量两个节点时间偏差，作为从节点计算结果的参考标准。两个节点距离为室内20米。分别对DMTS，使用5个同步数据包的EDMTS进行测试，各测试1000次。其详细误差分布如图2所示。

实际测量结果略多于1000次，此处按顺序选取1000组进行统计。通过图2可以看到，EDMTS精度和稳定性都优于DMTS。DMTS的测量结果波动很大，大部分位于2～8微秒之间，平均误差为5.3微秒。EDMTS大部分误差位于0～2微秒，平均误差1.2微秒。EDMTS精度的优势主要来自于在对多个测量值平均化，所以可以有效地排除误差，但是相对增大了信息交换量，能量消耗大于DMTS。

测试多跳网络中本算法的性能。采用3个节点，配置同前述实验，共分为3层，节点A为主节点，处于L0层。节点B和节点C分别处于L1和L2层。首先同步节点A和节点B，然后同步节点B和节点C。统计节点C和节点A的误差。详细误差分布如图3所示。

DMTS两跳平均误差为6微秒，EDMTS平均误差为1.5微秒，双跳误差并不大，理论上多跳网络中误差会随着跳数的增加而线性增长，然而在实际网络环境中，误差会相互抵消。稳定性方面，EDMTS仍然优于DMTS，双跳网络中，DMTS误差范围集中在3～9微秒，而EDMTS误差范围集中在0～3微秒。

6 结语

本文针对DMTS算法精度不高，稳定性不好的问题，分析了DMTS算法中忽略的时间延迟参数，对延迟采用高斯分布建模，利用最大似然估计法对时间偏差进行估计，提出EDMTS算法。

本算法在STM32F103+CC2430平台下的性能为，点对点同步误差平均为1.2微秒，多跳网络中平均同步误差为1.5微秒，同步误差波动不大，稳定性较好。EDMTS算法增加了同步包的数量，能量消耗量较DMTS更大，仍然保持了DMTS算法简洁的特性。

参考文献：

[1] 肖琳，程利娟，王福豹，等.一种低功耗无线传感器网络时间同步算法[J].计算机研究与发展，2008，45（1）：126-130.

[2] 张白桦.基于TPSN的时间同步改进算法[J].计算机工程，2010，36（9）：109.

[3] 沈明玉，艾治雄.无线传感网络低能耗时间同步的研究[J].计算机工程与应用，2012，48（8）：112-115.

[4] 王瑜，张继荣.无线传感器网络的时间同步[J].西安邮电学院学报，2010，15（1）：143-147.

[5] 荆琦，唐礼勇，陈洲峰，等.无线传感器网络应用支撑技术研究[J].计算机科学，2008，35（3）：22-27.

[6] 刘翠苹，张海涛，白舸.基于萤火虫群优化算法的无线传感器节点部署[J].计算机应用，2013，33（4）：905-907.

[7] 徐朝农，徐勇军，李晓维.无线传感器网络时间同步新技术[J].计算机研究与发展，2008，45（1）：138-145.