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

2013-04-29 17:41郑顾平马粤
科协论坛·下半月 2013年9期
关键词:无线传感网络高斯分布

郑顾平 马粤

摘 要:无线传感网络的时间同步算法中,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.

猜你喜欢
无线传感网络高斯分布
利用Box-Cox变换对移动通信中小区级业务流量分布的研究
2种非对称广义高斯分布模型的构造
在航集装箱船舶摇摆姿态的概率模型
不同分布特性随机噪声的FPGA实现
一种基于改进混合高斯模型的前景检测
改进的无线传感网络节点定位系统的设计与研究
基于物联网ZigBee技术的智能家居监控系统 
甲醛监测仪设计及其低功耗研究
试论无线传感网络动态休眠通信协议
基于CC2530的智能照明控制系统设计