多层动态分簇的WSN时间同步算法*

杜永文,冯 珂,彭 冲

(兰州交通大学电子与信息工程学院,兰州 730070)



多层动态分簇的WSN时间同步算法*

杜永文*,冯 珂,彭 冲

(兰州交通大学电子与信息工程学院,兰州 730070)

无线传感器网络受多跳传输延迟和节点中的晶振准确度的影响,造成时间同步误差较大。为了减小同步误差,传统解决方法提高了同步算法的频率,这使得算法面临两个问题:①通信能耗较高;②精度与能耗之间的不平衡。针对以上问题,结合单向广播机制和双向成对机制,提出一种多层动态分簇的无线传感器网络时间同步算法。采用节点分层策略减少了同步通信开销;采用同步误差补偿机制降低了算法同步误差的影响,使用时钟补偿机制减少了传感器节点运行的累积误差。实验测试表明:在保证精度的前提下,本算法降低了同步次数,减少了同步通信开销,从而延长了网络的生命周期。

无线传感器网络;时间同步;传输延迟;晶振

无线传感器网络WSN(Wireless Sensor Network)是一种分布式的自组织网络,时间同步作为关键技术之一发挥着重要作用。传感器网络内部节点只有保持时间同步,才能互相协作完成相应的任务。数据融合、节点定位、休眠周期的同步、介质访问控制(MAC)链路调度等都需要统一的时钟基准。所以研究一种精准、高效的时间同步算法具有重要的科研意义和实用价值。

目前常用的无线传感器网络时间同步算法主要可分为2类:单向广播同步和双向成对同步。单向广播时间同步算法采用单向报文进行时间同步,以参考广播同步(RBS)[1]算法为例,该类算法在排除了发送端的不确定性后,它的到达时间被接收节点用作参考来对比本地时钟,从而实现接收者彼此同步,但为提高单向报文的时间精度,往往需要提高报文发送频率,这会致使同步报文发送过多,能耗较大。双向成对时间同步算法采用双向报文交换机制实现节点间的时间同步,以时间同步协议(TPSN)[2]算法为例,双向报文可以较准确的估计无线传输延迟,但双向报文使得时间同步报文交互数量增加,增大节点能耗,且同步时间存在累积误差。除此之外,时间同步算法还有仿生时间同步算法,如萤火虫同步算法[3]。萤火虫同步算法要求每个传感器节点安装一个RC振荡器(由电阻R和电容C构成的适用于产生低频信号的电路),增大了传感器节点的成本,增加了节点能耗,不利于大规模传感器网络的布置。

本文针对传感器网络能量的特点,提出了一种基于多层动态分簇的主次分级时间同步算法——PSLTS(Primary-Secondary Layered Time Synchronization)。PSLTS算法采用多层动态分簇的策略,将网络节点划分为主次两层网络,在簇首通信的主网络中使用传感器网络TPSN的思想进行时间同步;簇内通信的次网络在不降低时间精度的前提下降低簇首节点能量消耗,采用延迟测量时间同步(DMTS)算法的思想进行时间同步。同时采用同步误差补偿机制修正由于跳数距离增加造成的同步误差,采用时钟补偿机制减少长时间工作由于晶振频率不稳造成的误差,从而提高时间同步精度。同TPSN算法以及ATSP算法比较,PSLTS算法降低了时钟同步的频率,降低能量消耗。

图1 网络拓扑结构

1 多层动态分簇的PSLTS算法

1.1 网络拓扑结构

PSLTS算法采用动态分簇方式对网络拓扑进行层次式划分,将网络节点划分为主次两种网络。主网络中簇首节点将数据融合后再采用多跳通信方式把数据传送到汇聚节点,次网络中同一簇的簇首节点和簇内成员节点通过单跳通信,进行信息汇聚[4]。基于动态分簇的无线传感器网络拓扑结构如图1所示[5]。

1.2 主网络-簇间通信网络

图1所示网络的簇首节点形成了主网络,其拓扑如图2所示。

图2 主网络拓扑结构

采用多跳网络的TPSN算法思想将主网络时间同步分成两个阶段。①第1阶段为层次发现阶段[6],该阶段在网络分簇后将网络簇首节点层次化,将汇聚节点作为第0层参考节点;根据簇首节点到汇聚节点的跳数分为1到n层;②第2阶段为时钟同步阶段,层次结构建立后,通过时间同步包,从1层到n层逐层时钟同步。

PSLTS算法中的簇首节点避免了TPSN中节点要与多个上层节点同步,而只与其直接父节点同步,减少了消息交换数目和同步时间。

主网络簇间通信算法采用基于双向报文的时间同步算法。上层节点广播发送信标消息,下一层各节点接收到信标消息并立即记下本地的时间戳,将其发送到上层节点进行处理,节点计算和保存节点与参考节点时间的误差值,并将其发送到对应节点完成时钟误差的修正。

图3 簇间通信算法

如图3所示,T1、T4用来记录同步节点的本地时间,T2、T3用来记录参考节点的本地时间。同步节点A在T1时刻向参考节点B发送一个同步请求报文,报文中包含了同步节点的级别和T1,当参考节点B收到报文后,记录下接收时刻T2,并立即向同步节点A回复一个同步应答报文,该报文中包含了参考节点B的级别和T1、T2以及回复时刻T3,同步节点A收到参考节点的回复后,记下时刻T4,假设来回报文的传输延迟相同为d,同步节点在T1时刻的时钟偏差m为:

(1)

1.3 次网络-簇内通信网络

图1中每个簇首节点与簇内节点形成的网络称为次网络,次网络拓扑如图4所示,簇首节点使用单跳方式直接与簇内节点通信。由于接收簇内节点信息会消耗大量能量,簇首节点应在同步时尽量减少与簇内节点通信的次数,采用单向报文算法进行时间同步,如图5所示。

图4 次网络拓扑

图5 簇内通信算法

簇首节点在MAC层打时间戳t0的办法去除发送延迟和访问延迟。然后,簇首节点发送前导码和起始字符等接收同步信息,再广播时间分组。前导码和起始字符的发送时间等于发送信息位的个数n和发送单位比特需要的时间t的乘积;接收节点在t1时刻收到广播抵达时刻,并在修改本地时钟之前保存时间t2,则接收处理延迟为t2-t1。假设忽略传播延迟,接收节点与簇首节点同步,传感器节点需要进行的时钟调整为:

T=t0+nt+(t2-t1)

(2)

1.4 同步误差补偿机制

无线传感器网络时间同步协议中,消息传输延迟的计算精度决定了时间同步的精度。消息传输的非确定性延迟是影响父节点和子节点之间时间同步精度的主要因素[7]。节点通过交互同步信息估算相应的参数,然而同步信息在网络上传输会产生一定时延,导致算法同步误差与跳数距离成正比增长。同步误差补偿机制采用基于延迟估算的方法,使用线性回归分析节点随跳数变化造成的时间延迟变化情况,获得时间延迟变化数据。传感器节点根据自身到汇聚节点的跳数和获得的时间延迟数据修正由于跳数距离增加造成的非确定性延迟增大[8]。

假设在一定时间范围内节点时钟晶振频率是稳定的,给发送的每个字节标记时间,接收节点在接收完字节也做同样的标记,如图6所示。这样在接收节点处获得了多个时间标记对,对获得的时间标记对构造最佳拟合直线T(time)。在误差允许的时间间隔内,节点可直接通过T(time)计算某一时间节点间的时钟偏移量,而不必通过发送时间同步消息来计算,从而减少了消息的发送次数并降低了系统能量开销。

图6 时间标记格式

通过线性回归模型可以得到时钟偏移量与同步时间的转换公式[9]。

传感器节点的时钟偏移量如式(3)所示:

(3)

传感器节点的同步时间修正如式(4)所示:

(4)

式(3)、式(4)中:发送端时戳为tbegin,接收端时戳为tend,那么同步节点与时钟源节点的时间ttime=tend-tbegin,tlate是某一时刻节点间的时钟延迟量,T是节点全局同步时间。

图7 误差补偿包消息格式

未同步节点接收到已同步节点广播的误差补偿包后,从消息包中得到本地时间与全局时间的同步误差,调整自己的本地时间,使之与全局时间达到一致。

同步误差补偿机制解决了:①传统分层或分簇算法中的时延增加;②时间同步精度降;③及节点不停地在监听和发送之间转换导致的能耗增加问题。

1.5 时钟补偿机制

网络中每个节点维护各自的本地时钟,节点利用晶体振荡器驱动微处理器中的计数器以晶振振荡频率进行计数。无线传感器网络通常部署于室外环境中,温度敏感的特性使得节点晶振频率会随着环境温度的动态变化变得极不稳定。现实环境中无线传感器网络节点所处环境温度的变化大,节点晶振输出频率会随着其所处环境温度的变化而变化。室外环境下节点晶振的不稳定性迫使节点必须频繁地进行时钟相偏的估计以及补偿,以保证较高的时间同步精度[10]。然而,大多数时间同步算法的相偏估计过程主要依赖于节点间频繁的时间戳交换,这种依赖于时戳交换的时间同步方法势必会造成节点能量的迅速流失。

温度-频偏变化规律表现为一个二次函数[11],如式(5)所示。

f(t)=f0[1-k(T(t)-T0)2]

(5)

式中:f(t)为当前节点输出频率;fo为标称频率;k为温度系数,即频偏对温度的敏感度,反映了节点晶振当前的稳定程度,通常情况下,k=-0.034±0.006ppm/℃;T0表示晶振测试时的标准温度;T(t)代表当前温度。频率随温度的变化趋势如图8所示。

图8 频率随温度的变化趋势图

从图8可以看出,温度因素对节点频偏值的影响十分巨大,比如:当温度从25 ℃下降至10 ℃时,相应的频偏变化为4ppm(即每秒4μs)。当传感器节点长时间工作时,节点频偏值的累积会十分巨大,所以节点在对频偏进行估计时,为了提高估计精度,同步算法需要将温度对频偏的影响考虑在内。

节点频偏主要是由其晶振频率的漂移造成的,节点频偏α(t)的获取使得节点能够根据当前温度变化情况预测未来时钟漂移的范围,从而使节点可以通过数学计算补偿时钟漂移,对时间同步周期进行调节。因此节点频偏为:

(6)

式中:f0为标准频率,f(t)为节点当前频率相关的函数。节点的当前频偏可以通过对节点当前所处温度的测量,并将测量结果代入式(5)、式(6)获得。通过实验获得温度-频偏变化规律函数,在同步过程中,依赖于函数进行同步,无需时戳交换过程,因此有效地降低了通信开销。

PSLTS算法基于以上几种方法对无线传感器网络时间同步中的误差进行两次修正,算法整体流程如图9所示。

图9 算法流程图

传统时间同步算法的节点同步时间为:

T=tlocal+tlate

(7)

PSLTS算法的节点同步时间为:

TPSLTS=tlocal+tlate+f(Δt)

(8)

式(7)、式(8)中:tlocal为传感器节点本地时间,tlate为同步延迟误差时间,f(Δt)为晶振随时间变化误差函数。从公式可以看出,随着节点运行时间的增加,传统时间同步算法和PSLTS算法的同步时间差距越来越大,PSLTS算法可以更加准确的修正同步时间。

传统算法如果需要长时间的全网节点时间同步,需要周期性执行算法进行重同步。时钟补偿机制通过对节点时间漂移进行估计,使得算法能够在满足特定同步精度的前提下只需要一次同步就可以长时间保持全网节点时间同步,可以有效的减少周期性同步造成的能耗损失。

2 实验分析

针对PSLTS算法的时间同步性能,主要从2个方面描述PSLTS算法的性能特征:①时间同步精度;②通信报文开销[12]。参与对比实验的时间同步方法包括:①TPSN算法,②ATSP[13]算法。

2.1 算法复杂度分析

传统时间同步算法在进行时间同步时,传感器节点要与上层节点同步,并且需要周期性执行算法进行重同步,每一个传感器节点T(n)=O(n2)。

PSLTS算法只需要在传感器组网时获取自身到汇聚节点的跳数,就可以自身进行修改。算法执行时间与传感器节点的数量无关,时间复杂度为T(n)=O(1)。

2.2 同步精度分析

本文使用基于CC2530芯片的ZigBee节点进行实验验证本文算法的同步精度。算法每10min进行一次同步,进行五十次同步后,对每次同步后的时间误差求取平均值。

PSLTS算法和ATSP算法、TPSN算法随周期增加的误差如图10所示。

图10 相同时间下同步误差对比

PSLTS算法和ATSP算法、TPSN算法随跳数增加的同步精度如图11所示。由于采用了同步误差补偿机制,减小了多跳网络中同步误差的累积,时间偏移随着跳数增加的幅度比较缓和,平均每跳的同步误差控制在4μs以内。

图11 不同跳数下同步误差对比图

2.3 时间漂移分析

使用CC2530芯片自带的片上温度传感器获取温度信息。在不同温度下PSLTS算法的时间漂移误差如图12所示。

PSLTS算法采用时钟补偿机制,减小了晶振由于时间漂移造成的误差累积,时间漂移随着时间增加的幅度比较缓和,使得算法可以长时间运行,不需要进行周期性同步。

图12 不同温度时间漂移误差对比

2.4 同步能耗分析

本节验证PSLTS在无线传感器网络中的同步能耗。采用TinyOS2仿真软件验证本文算法的能量消耗。通过对不同跳数的ZigBee节点的时间误差进行测量,仿真实验中本文将节点的通信半径设为20m,在100m×100m的区域内随机布置了100个节点,簇首节点数量为10个,运行时间50min[10]。将RBS算法、TPSN算法同步周期设为10min。通过对同步报文开销的计算得到传感器节点的同步能耗。

图13给出了平均同步能耗随着节点数增加的变化趋势,从图13可以看出,随着节点数的增多,PSLTS的能耗明显小于ATSP和TPSN,且节点越多优势越明显。

平均能耗随着运行时间增加的变化趋势如图14所示,随着运行时间的增多,PSLTS的能耗开销明显小于ATSP和TPSN算法,且运行时间越长优势越明显。

图13 同步能耗随节点数变化趋势

图14 同步能耗随运行时间变化趋势

3 结论

针对无线传感器网络能量受限的特点和典型同步机制的不足,PSLTS算法结合单向广播机制和双向成对机制,并采用晶振补偿策略,降低了同步次数,减少了同步通信开销,延长了网络的生命周期,更适用于能量受限的无线传感器网络的应用。由于时间延迟的不确定性,为获得最优延迟时间,进行了大量实验,并对获取到的数据进行分析。算法中对晶振的影响因素只是考虑温度,对于其他因素的影响还有待下一步继续研究。

[1] 陶志勇,胡明. 基于等级层次结构的TPSN算法改进[J]. 传感技术学报,2012,25(5):691-695.

[2] 许万,杨光友,周晶晶. 基于RBS的无线传感器网络时间同步仿真研究[J]. Scientific Journal of Control Engineering,2013(3):64-70.

[3] 刘建娟. 基于改进萤火虫群优化的无线自组网路由算法[J]. 传感技术学报,2016,29(12):1905-1911.

[4] 李建洲,王海涛,陶安. 一种能耗均衡的WSN分簇路由协议[J]. 传感技术学报,2013,26(3):396-401.

[5] Leva A,Terraneo F,Rinaldi L,et al. High-Precision Low-Power Wireless Nodes’ Synchronization via Decentralized Control[J]. IEEE Transactions on Control Systems Technology,2015,24(4):1-15.

[6] Sakuru K L V S P,Kondapalli S R R. Performance Evaluation of Sink Node Selection for Time Synchronization in WSN[C]//International Conference on Devices,Circuits and Communications. 2014:1-5.

[7] 孙子文,吴梦芸,白勇. 抗延迟攻击的WSN时间同步方法[J]. 传感技术学报,2014,27(7):982-987.

[8] 吴宝明,李声飞. 基于最优线性拟合的WSN时间同步算法研究[J]. 传感技术学报,2010,23(12):1787-1791.

[9] Maggs M K,O’Keefe S G,Thiel D V. Consensus Clock Synchronization for Wireless Sensor Networks[J]. IEEE Sensors Journal,2012,12(6):2269-2277.

[10] Berger A,Pichler M,Klinglmayr J,et al. Low-Complex Synchronization Algorithms for Embedded Wireless Sensor Networks[J]. IEEE Transactions on Instrumentation and Measurement,2015,64(4):1032-1042.

[11] 金梦,陈晓江,房鼎益,等. 一种温度自适应无线传感网络时间同步方法[J]. 软件学报,2015,26(10):2667-2683.

[12] 徐久强,毕伟伟,朱剑,等. WSN中多跳均匀分簇路由算法的设计与仿真[J]. 系统仿真学报,2011,23(5):992-997.

[13] Wu J,Jiao L,Ding R. Average Time Synchronization in Wireless Sensor Networks by Pairwise Messages[J]. Computer Communications,2012,35(2):221-233.

杜永文(1974-),男,博士,副教授,研究领域为嵌入式系统;

冯 珂(1989-),硕士,研究生,研究领域为无线传感器网络;

彭 冲(1992-),硕士,研究生,研究领域为嵌入式系统。

WSN Time Synchronization Algorithm Based onHierarchical Dynamic Clustering*

DU Yongwen*,FENG Ke,PENG Chong

(Lanzhou Jiaotong University,The School of Electronics and Information Engineering,Lanzhou 730070,China)

Delay caused by multi-hop transmission and the inaccuracy crystal lead to a larger time synchronization error in WSN. In order to reduce the synchronization error,the traditional solution improves the frequency synchronization algorithm. It makes the traditional algorithm faces two problems:①high energy consumption used in the process of synchronization;②the imbalance between accuracy and energy consumption. Aiming at the above problems,a multi-layer dynamic clustering time synchronization algorithm for wireless sensor networks is proposed by combining one-way broadcast mechanism and bidirectional pairing mechanism. The algorithm reduces the cost of synchronous communication by adopting nodes stratification strategy. The synchronization error compensation mechanism is adopted to reduce the influence of synchronization errors. The clock compensation mechanism is used to reduce the accumulated error of the sensor nodes. Experimental results show that the proposed algorithm can prolong the life cycle of the network,reduce the frequency of synchronization and the consumption of communication under the premise of guaranteeing the accuracy.

wireless sensor network;time synchronization;delay;crystal oscillator

项目来源:甘肃省科技计划项目(144NKCA040);国家自然科学基金项目(61163009)

2016-12-26 修改日期:2017-03-14

TP 212

A

1004-1699(2017)07-1070-06

C:7230

10.3969/j.issn.1004-1699.2017.07.017