DMTS与TPSN时间同步算法的融合设计

徐世武,王平,何花,施文灶,江华丽

(福建师范大学物理与光电信息科技学院,福州350007)

引 言

无线传感器网络集成了传感器技术、计算机技术和通信技术,在军事、环境、健康、家庭、商业等许多方面有着巨大的潜在应用前景[1]。功耗的高低是衡量一个无线传感器网络性能的主要标志之一,应该尽量让没有工作的节点处于休眠状态,以节省节点的功耗。当然可以在MAC层采用时分多路复用技术,但这就要求节点通信双方实现时间上的同步。

NTP协议是目前因特网上采用的时间同步协议标准。因无线传感网络具有体积、电能供应、存储容量等的约束,以及采用的是无线传输方式,算法的局部性等,所以NTP协议不适合用于无线传感网络中。GPS系统也可以提供高精度的时间同步,但它的信号穿透性差,GPS天线必须安装在空旷的地方,功耗也较大,所以不适合无线传感器网络。

1 节点硬件平台

传感器节点是构成无线传感网络的基本平台,具有传统网络的终端和路由的双重功能:一方面要实现数据的采集和处理;另一方面还要对其他节点转发的数据进行存储、管理和融合等处理。虽然其设计不一,但是基本结构相同。它一般由传感器模块、处理器模块、无线通信模块和能量供应模块组成[2]。基本组成如图1所示。

图1 无线传感器节点基本组成

2 时间同步

2.1 不确定性的影响因素

因受到各种器件、负载等因素的影响,传输延迟的不确定性主要的影响因素如图2所示。

图2 报文传输延迟

发送时间:发送方用于构造分组并将分组转交给发送方的MAC层的时间。主要取决于时间同步程序的操作系统调用时间和处理器负载等。

访问时间:分组到达MAC层后,获取信道发送权的时间。主要取决于共享信道的竞争,当前的负载等。

传送时间:发送分组的时间,主要取决于报文的长度等。

传播时间:分组离开发送方后,并将分组传输到接收方之间的无线传输时间。主要取决于传输介质、传输距离等。

接收时间:接收端接收到分组,并将分组传送到MAC层所需的时间。

接受时间:处理接收到分组的时间。主要受到操作系统的影响。

2.2 算法分类

在无线传感器网络中,目前时间同步协议比较成熟的协议中,根据同步节点间信息交互方式的不同,可以归结为以下3类:

①基于发送者—接收者的双向同步算法,比较典型的算法如TPSN(Timing-Sync Protocol for Sensor Networks)算法。

②基于发送者—接收者的单向时间同步算法,比较典型的算法如FTSP(Flooding Time Synchronization Protocol)算法,DM TS(Delay Measurement Time Synchronization)算法。

③基于接收者—接收者的同步算法,典型的有RBS(Reference Broadcast Synchronization)算法。

2.3 DMTS算法分析

DM TS(Delay Measurement Time Synchronization)算法[3],即延迟测量时间同步协议,是基于发送者—接收者的单向时间同步算法,该算法结构简单,功耗较低,具有广泛的运用,其算法原理图如图3所示。当发送节点在检测到通道空闲时,给广播分组加上时间戳t0,从而排除了发送节点的处理延迟与MAC层的访问延迟。并假设发送报文的长度为NA个比特(包括前导码与同步字),传送每个比特的时间为t,而接收者在接收完同步字后,记录下此时的本地时间为t1,并在调整自己的本地时间记录之前记录下此时的时刻t2,这时接收节点为了与发送节点达到时间上的同步,可以调整接收节点的时间改为t0+t◦NA+(t2-t1)。

图3 DMTS算法原理图

2.4 TPSN算法分析

TPSN(Timing-Sync Protocol for Sensor Networks)算法[4],采用的是层次型的网络结构,是基于发送者—接收者的双向同步算法。分层两个阶段,第一阶段为层次发现阶段,第二阶段为同步阶段。其算法原理图如图4所示。在图4中,T1、T4用来记录同步节点的本地时间,T2、T3用来记录参考

节点的本地时间。同步节点A在T1时刻向参考节点B发送一个同步请求报文,报文中包含了同步节点的级别和T1,当参考节点B收到报文后,记录下接收时刻T2,并立即向同步节点A回复一个同步应答报文,该报文中包含了参考节点B的级别和T1、T2、回复时刻T3。同步节点A收到参考节点的回复后,记下时刻T4,假设来回报文的传输延迟相同都为d,且m为同步节点在T1时刻两者之间的时偏,且设来回时偏相同,由则在T4时刻,若在同步节点A的本地时间增加修正量m,就能达到同步节点A与参考节点B之间的同步。

图4 TPSN算法原理图

2.5 两种算法的融合设计

本文设计主要采用DM TS与TPSN两种算法的融合运用,充分利用两种算法的优点。本文主要分成两条路径,主路径和次路径。主路径即图5中的A、B、E三个路由节点形成的路径,次路径即路由节点B与两个传感节点(C、D)形成的一个子网络1,还有路由节点E与两个传感节点(F、G)形成的一个子网络2。在无线传感网络中大部分是由传感节点组成的,用来采集数据,还有一部分是路由节点用来存储和转发数据,因主路径中的路由节点跳数较多,为了提高网络的精度,可以在路由节点与路由节点之间,即主路径之间采用TPSN算法,而在子网内的传感节点与该子网的路由节点之间采用DMTS算法,这样既可以减少整个网络算法的复杂度,也可以减少整个网络的功耗。

主路径上的时间同步:首先A节点通过使用NLDEDATA.request原语,并设置DstAdd r参数为0xffff(广播网络地址)广播形式发送时间同步组包命令[5]。组包中包括了A节点的层次号0,A节点的ID号,并指定B节点为其下一跳同步节点。当B节点收到A节点发送的广播组包后,记下自己的层次号为1,父节点的ID号为A,并与A节点进行时间同步。同样,B节点也以广播的方式发送同步组包,指定E节点为其下一跳同步节点。当C、D、E节点收到B节点的广播同步包后,分别记下自己的层次号为2,但只有E节点才与A节点进行时间同步。

图5 实验节点组网图

次路径上的时间同步:在主路径上时间同步完成后,这时就可以在次路径上进行时间同步。对同步精度要求不是很高的情况下,次路径可以选择较长的周期进行同步,以减少网络的功耗。在子网络1中,B节点以广播的方式发送同步信息包,当然与主路径的同步包不同,这时B节点指定的下一跳节点为C、D两个节点。但C、D两个节点收到B节点的同步包后,修改自己的本地时间以达到以节点B的同步,子网2采用同样的办法进行同步。

2.6 算法误差分析

主路径误差分析,根据图2中的消息传输过程,可以得出以下各式:

在式(1)、(2)中,t1、t2是由标准时钟所确定的,表示UTC时间。T1、T2分别是t1、t2所对应的本地节点所测出的本地时间。SA代表节点A的报文发送时间,AA是发送报文的访问时间,TA→B是A节点按比特传输报文与B节点按比特接收报文所需要的时间,PA→B是节点A传播到节点B的时间。RB是节点B的报文接收处理过程时间。NAt是传输NA个比特的总时间。Terror指传输比特的误差,Rerror打时标过程存在的误差。代表节点A与节点B在t1时刻的时偏。因为在实验中我们采用了MAC层的打时标方法,这样就可以消除了发送时间与访问时间对误差的影响。于是式(1)、(2)就可以简写为式(3)、(4)。

由以上各式可以得到时偏:

次路径上的误差分析,由图1可以看出,发送节点A在T0时刻检测到空闲,接收节点B在报文到达时刻给报文加上时间戳T1,并在调整自己的本地时间记录之前记录下此时的时刻为T2,在T3时间完成调整。则可以得到[6]:

式子TA→B+RB=nt+Terror+Rerror+(T2-T1)中,n是前导码的长度,于是可以得到DMTS的时偏m:

从式(7)中可以看出TPSN的误差较小,因为两个传感节点的距离较小,而电波的传播速度快,所示PUC通常都在μs范围之内,而两个节点之间的来回时偏基本是不变的。所以TPSN误差大部分是由两个节点收、发报文的时间差。从式(10)中可以看出,DM TS是单播传送报文,所示不能消除Terror和Rerror的影响。虽然TPSN算法精度较高,但同步一次,需要发送2个消息和接收2个消息,共4个消息的能量消耗。DM TS算法精度较差,但同步一次,只需要发送1个消息和接收1个消息,共2个消息的能量消耗。所以结合了两者的优点,在无线传感器网络中不仅保证了网络的精确度,也减少了整个网络的功耗。

2.7 算法程序流程

算法总体流程如图6所示,主路径程序流程如图7所示,次路径程序流程如图8所示。22

图6 算法总体流程

图7 主路径程序流程

图8 次路径程序流程

结 语

本文的创新在于融合了DM TS和TPSN两种时间同步算法,网络功耗和精度均介于两者之间。虽然相较于TPSN算法,在同步精度上有所下降,但网络节点功耗低于TPSN算法,特别适用于同步精度要求不是非常高的中小型无线传感器网络中。

[1]田贤忠,陈登,胡同森.无线传感器网络按需时间同步算法研究[J].传感技术学报,2008,21(11):1881-1886.

[2]宋文.无线传感器网络技术与应用[M].北京:电子工业出版社,2007:128-144.

[3]Ping S.Delaymeasurement time synchronization for wireless sensor networks(IR-TR-2003-64).Intel Research Center,2003.

[4]MarotiM,Kusy B,Simon G.The Flooding time synchronization inw ireless sensor networks:ACM SenSys'04,November 2004,Baltinore[C].

[5]吕治安.ZigBee网络原理与应用开发[M].北京:北京航空航天大学出版社,2008:120-140.

[6]封红霞,周莹.无线传感器网络的时间同步算法误差分析[J].仪器仪表标准化与计量,2006(6):30-33.