线性传感器网络时间同步协议

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@http://wendang.chazidian.com

Journal of Software, Vol.20, Supplement, December 2009, pp.266?277 http://wendang.chazidian.com © by Institute of Software, the Chinese Academy of Sciences. All rights reserved. Tel/Fax: +86-10-62562563

线性传感器网络时间同步协议

徐朝农1+, 徐勇军2, 邓志东1

1

2? (清华大学 智能技术与系统国家重点实验室,北京 100084) (中国科学院 计算技术研究所,北京 100190)

Timing-Sync Protocol for Linear Sensor Networks

XU Chao-Nong1+, XU Yong-Jun2, DENG Zhi-Dong1

1

2(State Key Laboratory of Intelligent Technology and Systems, Tsinghua University, Beijing 100084, China) (Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China)

+ Corresponding author: xu_chaonong@http://wendang.chazidian.com

Xu CN, Xu YJ, Deng ZD. Timing-Sync protocol for linear sensor networks . Journal of Software, 2009,

20(Suppl.):266?277. http://wendang.chazidian.com/1000-9825/09031.htm

Abstract: Due to the features of high synchronization error and high power consumption, the classic

synchronization scheme of two-way packets exchange is unfit for some applications in wireless sensor networks,

especially for networks with multi-hop linear topology. This paper proposes a time synchronization protocol named

Timing-sync Protocol for Linear Sensor Networks (TPLSN). The synchronization scheme of enhanced two-way

packets exchange and the scheme of clock skew compensation are keys to the success of TPLSN. The phenomenon

of its synchronization error accumulation over hop count is also investigated. TPLSN is evaluated on a

Mica2-compatible test bed. Its synchronization error is less than 20µs for the node which is 9 hops away from the

time beacon node, the increase ratio of synchronization error to hop count is less than 1µs per hop, and the increase

ratio of synchronization error to resynchronization cycle is 0.017µs per second. Further, to synchronize all nodes in

an n-hop linear wireless sensor network, only 2n packets are needed, which is least for any synchronization protocol

based on synchronization scheme of two-way packet exchange. Theoretical analysis shows that three factors,

including the approximated accuracy, the asymmetry of two-way packets exchange, and the clock skew, have great

influences on time offset between two adjacent nodes. Furthermore, the clock frequency order of the linear network

is found to be vital to the accumulation of synchronization error over hop count.

Key words: wireless sensor networks; time synchronization; clock synchronization; clock skew; synchronization

error accumulation

摘 要: 由于存在着高同步误差和高功耗的特点,尤其当网络拓扑为多跳线状时,经典的双向报文交换同步机

制不适合于无线传感器网络中的一些应用.提出了TPLSN时间同步协议.两个组件,包括:改进的双向报文交换

同步机制和时钟飘移补偿机制是TPLSN成功之关键.进一步讨论了TPLSN同步误差随跳数增长的现象.在一个

与Mica2兼容的测试床上对TPLSN进行了性能评估.距离时间基准节点9跳的节点的同步误差小于20μs,同步? Supported by the National Natural Science Foundation of China under Grant Nos.90820305, 60621062, 60772070 (国家自然科学基

金); the National High-Tech Research and Development Plan of China under Grant Nos.2007AA041702, 2009AA01Z126 (国家高技术研

究发展计划(863)); the China Postdoctoral Science Foundation under Grant No.20080430412 (中国博士后科学基金)

Received 2009-05-01; Accepted 2009-07-23

徐朝农 等:线性传感器网络时间同步协议 267

误差随跳数的增长率小于1μs/跳,同步误差随重同步周期的增长率为0.017μs/s.此外,同步一个n跳的线状网络只需要2n个报文,这也是所有基于双向报文交换同步机制的同步协议最小所需的报文数.理论分析表明:近似精度、双向报文交换的不对称性和相对时钟飘移因素对两个相邻节点之间的同步误差有很大的影响.进而,线状网络的时钟序对同步误差的累积至关重要.

关键词: 无线传感器网络;时间同步;时钟同步;时钟飘移;同步误差累积

时间同步[1]是无线传感器网络的基本中间件,它不仅是实际应用必不可少的组件,也是例如低功耗睡眠、MAC链路调度、路由、数据融合、定位等其他中间件的基础.

相对于单向报文同步机制,经典的双向报文交换同步(简称为双向同步)机制对报文传输延迟不敏感[2],通用性较强,从而被NTP(network time protocol)[3]和工业网络标准IEEE1588所采纳.然而,其单跳同步精度有限,并且同步误差随跳数的增加而快速增加.对在实际应用中非常广泛的具有线状拓扑的网络(简称为线性网络)而言,由于网络直径较大,从而造成远离时间基准的节点同步误差很大,限制了经典的双向同步机制的应用.因此,经典的双向同步机制在应用到多跳线性网络时必须要进行改进.

非同步期过长以及在非同步期内发生较大时间的突变是造成经典的双向同步机制同步精度低的重要原因. 我们针对这两个问题对其进行了改进.基于这两处改进和一个时钟飘移的最小方差无偏估计器,我们提出了适合于多跳线性无线网络的时间同步协议TPLSN.在GAINS(global accessible intelligent nodes)节点[4]上的实验表明:(1) 单跳同步精度可达10μs左右,同步误差随跳距的增长率约为1μs/跳.这表明即使远离时间基准节点,节点的同步误差也很小.(2) 同步误差随重同步周期的增长率为0.017μs/跳,这表明即使长时间不进行重同步操作,同步精度也可满足需要.(3) 对于n跳线性网络,同步网络中所有节点的报文个数仅为2n,该值也是全程采用双向同步机制最少需要的同步报文数.以上结果表明TPLSN协议具有高精度和低能耗的优点.

为了进一步提高TPLSN协议在多跳线性网络下的同步精度,我们研究了其同步点处同步误差随跳数累积现象.理论分析表明:近似精度、双向报文交换的不对称性和相对时钟飘移对两个相邻节点间的同步误差有很大的影响.进而,线性网络的时钟序对同步误差随跳数的累积至关重要.从而我们认为:针对网络的实际特点进行合理的节点位置摆放能提高TPLSN协议的同步精度.

第1节定义本文所涉及的一些基本术语.作为第3节的基础,第2节简要介绍传统双向同步机制以及时钟飘移估计和时钟飘移补偿技术.第3节详细介绍TPLSN协议,包括TPLSN协议的框架、对经典双向同步机制的改进和对全局时钟飘移的估计.第4节分析TPLSN协议同步误差随跳数累积现象.第5节为实验与分析.第6节为相关工作回顾和讨论.最后为本文总结.

1 术 语

考虑这样的场景:全网中只有一个时间基准节点,只有该节点拥有获得真实时间(或实时时间)的能力.本文中的同步是指节点必须尽可能准确地从时间基准节点处获得真实时间.

时间(time)、频率(frequency):每个节点拥有一个由晶体振荡器驱动的计时设备.当实时时间为t时其晶体振荡器的频率记为f(t).而对应的本地时间记为c(t),也称为节点的本地时间.显然的:f(t)=dc(t)/dt.对于具体的某个节点,例如节点A,为表示方便,其晶体振荡器的频率记为fA(t),本地时间记为cA(t).

时间偏移(time offset)、同步误差(synchronization error)、全局时间偏移(global time offset)与全局同步误差(global synchronization error):节点间的本地时间之差称为时间偏移.例如:节点B相对于节点A的时间偏移定义为cA(t)?cB(t).与文献[5]一致,节点B和节点A之间的同步误差定义为abs(cA(t)?cB(t)).如果节点A为时间基准节点,则称cA(t)?cB(t)为全局时间偏移.abs(cA(t)?cB(t))为全局同步误差,这里abs为取绝对值操作.

跳数(hop count):连接节点和时间基准节点之间的最短路径的跳段数.

时钟飘移(clock skew):节点B相对于节点A的时钟飘移定义为(fA(t)?fB(t))/fB(t),记为k

B,A.

268 Journal of Software 软件学报 Vol.20, Supplement, December 2009

2 经典双向同步机制、时钟飘移估计及补偿技术

2.1 经典双向同步机制

图1表示了经典双向同步机制[6].考虑两个节点:节点A和节点B.在第i?1轮同步周期时,节点B需要和节点A

同步.此时,节点B向节点A发送一个同步请求报文.当节点A接收到该报文时,随即发出一个同步应答报文.

节点B获得cB(t1(i?1)),cA(t2(i?1)),cA(t3(i?1))和cB(t4(i?1))这4个时刻信息后,可根据(1)式计算出其相对于节点A

的时间偏移.

(cA(t2(i?1))?cB(t1(i?1)))?(cB(t4(i?1))?cA(t3(i?1)))ξ(i?1)= (1) 2

随后,节点B在其本地时间上加上ξ(i?1)后,就达到了和节点A之间的瞬时同步.

与双向同步相关的一些术语定义如下:

同步点(synchronous moment):节点B计算出时间偏移后,修改自己的本地时间达到和节点A之间的瞬时同

步,此时刻称为节点B的同步点.

同步期(synchronized period)、非同步期(non-synchronized period):如图1所示,一轮同步由同步期和非同步

期组成.其中,双向报文交换开始直至同步点的时间段称为非同步期,从本轮同步点后直至下轮双向报文交换开

始的时间段称为同步期.

重同步周期(resynchronization cycle):由于节点间存在时钟飘移,因此即使在达到瞬时同步后,一段时间后

又将出现失步,因此需要再次进行同步操作.相邻轮同步操作之间的时间段长度称为重同步周期.很明显,重同

步周期是同步期和非同步期之和.

c(t2(i?1))c(t3(i?1))

A(i)(i)BBBBBSynchronous

moment of BSynchronizedperiodperiod

Resynchronized cycle

Fig.1 Synchronization scheme of classic two-way packets exchange

图1 经典双向同步机制

2.2 时钟飘移估计与补偿

线性时间模型[7,8]是目前最为广泛的时钟飘移模型.线性时间模型假设节点间的相对时钟飘移在一段时间

内保持恒定.基于线性时间模型,我们提出了一个时钟飘移估计器.

如图1所示,令:TA(i)=cA(t3(i))?cA(t3(i?1)),TB(i)=cB(t4(i))?ξ(i?1)?cB(t4(i?1)),以及e(i)=TA(i)?TB(i).显

然,e(i)是在TB(i)时间段内节点B落后节点A的时间. 根据线性时间模型,e(i)可被建模为e(i)=kB,A×

TB(i)+w(i).其中,w(i)为高斯白噪声,w(i)~N(0,σ2).

以下方法可估计出kB,A.令:E=(e(1),e(2),...,e(n))T,H=(TB(1),TB(2),...,TB(n))T.这里的n为缓冲区的尺寸,其

值设置过小,采样数不足,导致估计值抖动剧烈;设置过大,估计值不能反映晶体振荡器的短期动态性.文献[9]经

过在Mica2平台[10]上的测量后认为8较合适.第5节的实验也采纳了该值.

根据线性模型的估计理论[11],可得:

?=(HTH)?1HTE (2) kB,A

徐朝农 等:线性传感器网络时间同步协议 269

是kB,A的最小方差无偏估计.

在获得了时钟飘移后,时钟飘移补偿则易于进行.以图1进行说明.设第i?1轮同步点时刻之前节点B的时

′),补偿的时间点在第i?1轮同步点之后到第i轮同步点之间为cB(tSM),同步点时刻之后节点B的时间为cB(tSM

′<t<t4(i).则时钟飘移补偿过程可用下式表示: 前,若节点B的本地时间为cB(t),即tSM

?((c(t)?c(t′)+(c(t)?c(t4(i?1))))=c(t)+k?((c(t)?ξ(i?1)?c(t4(i?1))) (3) cB(t)←cB(t)+k B,ABBSMBSMBBB,ABB

3 TPLSN协议

为达到与时间基准节点之间的同步,节点需要获知其全局时钟飘移信息.在介绍了TPLSN协议的概要和对双向同步机制的两处改进后,第3.3节介绍了如何根据局部时钟飘移计算出全局时钟飘移.

3.1 TPLSN协议概要

图2描述了TPLSN协议的概貌.节点N需要和时间基准节点(节点0)同步时,按照双向同步机制,它发出一个同步请求报文.其同步路径上的父节点在接收到该报文后,缓存报文中携带的时间信息,并继续向其父节点发送新的同步请求报文.该过程持续进行,直至时间基准节点接收到同步请求报文.随后时间基准节点立即返回一个同步应答报文.其子节点接收到该报文后,获取其中携带的时间信息,计算出全局时间偏移,修改自己的时间以达到和时间基准节点同步,并随即向其子节点发送一个同步应答报文,该报文中携带了与该同步应答报文相对应的同步请求报文中的时间信息.该过程继续进行直到节点N接收到同步应答报文时为止.明显的,实现n跳线性网络上所有节点的时间同步只需2n个同步报文,低能耗的优点显而易见. 8.Request9.Request

711.Reply110.Reply0

(a)

Node

1

7

8

9

(b)Synchronous momentRequestReplyTime

Fig.2 (a) Synchronization procedure of TPLSN; (b) Space-Time diagram of TPLSN

图2 (a) TPLSN协议的同步过程;(b) TPLSN协议的时空图

3.2 对双向同步机制的两处改进

非同步期过长以及在非同步期内可能发生较大时间突变,是造成经典的双向同步机制精度低的重要原因. 尤其对于TPLSN协议而言,直接采用经典的双向同步机制时问题会更加突出.从图2中可以看出:(1) 对于处于同步路径始端的节点(例如节点N)来说,同步请求和同步应答报文之间的时延过长,时钟飘移在非同步期内带来的误差不可忽略,并且路径越长,误差效应越明显[12].(2) 节点与其父节点的之间同步操作使得节点时间发生突变,而该突变时刻(即其同步点时刻)发生在其子节点的非同步期内,这严重影响了子节点的同步精度.这两点正是经典双向同步机制力图避免的情况,因此TPLSN协议必须要克服这两个弊端.

图3把节点与其父节点之间的同步操作单独分离出来进行研究(不再明确地表达出同步轮数标记,因为所有时间都在同一轮内).设节点A是节点B同步路径上的父节点.节点A在其同步期内时间发生了突变,即时间增加了λ.假设节点B的非同步期的时间很长,

时钟飘移在此期间的误差不可忽略.在这种情况下,节点B的时间修改量则不能简单地采用式(1)来进行计算.

270

Journal of Software 软件学报 Vol.20, Supplement, December 2009

→A

我们来推导合理的修改量的表达式.SA,PA→B和RB分别代表报文发送延迟,传播延迟与接收延迟.DtB代1

表在实时时间t1时,节点B相对于节点A的时间偏移. 由图3可得:

→A

(4) cA(t2)=cB(t1)+SB+PB→A+RA+DtB1

→A

(5) cB(t4)=cA(t3)+SA+PA→B+RB?DtB3

Time revision at its

(i?1) synchronous moment: cA(t)=cA(t)+λ

A

B

cB(t1)Synchronous

moment of node B

B

BBFig.3 Synchronization procedure of TPLSN between neighbor nodes

图3 TPLSN中相邻节点间的同步过程

→A

由图3,在节点B的非同步期内,当节点A的本地时间增加λ后,DtB则可分解为 1

B→A→A→A

DtB=RDtB?λ (6) 11→t3+Dt3

→A

其中,RDtB1→t3代表在t1~t3时间段内,由时钟飘移所导致的时间偏移变化量.

式(4)?式(5),可得:

→A→A

(cA(t2)?cB(t1))?(cB(t4)?cA(t3))SUCPUCRUCDtB+DtB31

=+++ (7)

22222

其中,SUC=SB?SA,PUC=PB→A?PA→B和RUC=RA?RB.

→A→A→BAB→AB→A

≈DtB=?DtA=Tt4?TtB由于DtB3444,RDt1→t3≈RDt1→t4.结合式(6),可得:

→A

(cA(t2)?cB(t1))?(cB(t4)?cA(t3))SUCPUCRUCRDtBλ→A1→t4

=+++?+DtB. 4

222222

→A

注意:DtB就是在t4时刻节点B相对于节点A的时间偏移,也是我们希望获得的目标.若令 4

→A

(cA(t2)?cB(t1))?(cB(t4)?cA(t3))RDtBλ1→t4

?+ (8)

222

为节点B在其同步点时刻的时间修改量,则在同步点时刻的瞬时同步误差为

ξ=

→A

而RDtB1→t4可如下计算:

Error=ξ?D

B→A

t4

SUCPUCRUC=++ (9) 222

→AB→A→A

RDtB?DtB+λ=cA(t1)?cB(t

1)?cA(t4)+cB(t4)+λ 1→t4=Dt14

=cB(t4)?cB(t1)?(cA(t4)?cA(t1)?λ)

?f??. =(cB(t4)?cB(t1))?1?A?=?(cB(t4)?cB(t1))kB,A

fB??

→A

λRDtB1→t4

与式(1)相比,式(8)中增加了两项.其中项解决了同步期过长的问题,项解决了父节点在同步期内

22

的时间突变问题.