具有低能耗、低功率及微型化等特点的节点组成的无线传感器网络(wireless sensor network,简称WSN)^[1]是当前的研究热点,且在环境监测、智能家居、智能交通以及医疗监控系统等应用场合中显示出巨大的应用前景^{[2, 3, 4]}.其中,大部分无线传感器网络应用技术依赖于全网节点的时间同步,如数据融合技术、休眠调度技术^{[5, 6]}、基于TOA的定位技术以及目标追踪等^{[7, 8]}.然而,由于节点工作环境(如工作电压、温度、湿度以及震动等)的不稳定、节点晶振老化以及节点制造工艺差别等多种因素的影响,节点晶振的实际振荡频率与其标称频率之间存在一定差别.这一现象使得全网各个节点的本地时间存在差异,这种差异被称作时间相偏(offset).若不及时对时钟相偏进行补偿,任由其不断累积增长,会造成网络性能的急剧下降,并且最终危及到网络的正常运行.

最近的研究成果^{[9, 10, 11]}表明,传感器节点的廉价设计使得其晶振极易受到所处环境温度的影响.并且,无线传感器网络通常部署于室外环境中,温度敏感的特性使得节点晶振频率会随着环境温度的动态变化变得极不稳定.这为室外环境下大规模传感器网络时间同步带来了两个严重问题:(1) 过高的通信开销;(2) 精度与能耗之间的不平衡.

· 通信开销过高问题

室外环境下节点晶振的不稳定性迫使节点必须频繁地进行时钟相偏的估计以及补偿,以保证较高的时间同步精度.然而,当今大多数时间同步算法的相偏估计过程主要依赖于节点间频繁的时间戳交换,如RBS^[12],TPSN^[13],FTSP^[14]等.Pottie等人^[15]指出:当传输距离大于100m时,传感器节点每发送1bit数据的能耗相当于执行300万条指令.因此,这种依赖于时戳交换的时间同步方法势必会造成节点能量的迅速流失;并且随着网络规模的不断增大,时戳交换数量将会呈指数方式增长.因此,该方法最终会缩短网络生命周期.

· 精度与能耗之间的不平衡

现有的时间同步算法通常使用固定同步周期来对节点频偏及相偏进行更新.虽然这种固定周期的同步方式能够满足大多数网络应用的同步精度需求,但却无法使得能量被高效利用:首先,由于传感器节点通常被部署在室外环境中,室外温度的动态变化使得节点频偏在不同时间段内呈现出不同的变化模式,而不同频偏变化模式下所需要的频偏估计频率不同;其次,在无线传感器中通常存在多个应用,如节点休眠调度、目标追踪等,这些应用对时间同步的精度要求也各不相同.因此,为了高能效地满足不同环境、不同应用下节点的时间同步需求,采用自适应的、动态变化的同步周期是一个很好的选择.

为了解决通信开销过高的问题,Yang等人^[9]提出了利用温度信息进行传感器网络时间同步的方法EACS.这种同步方法在节点部署之前,通过大量实验为每个节点获得“温度-频偏”映射表.在同步过程中,该方法完全依赖于映射表进行同步,无需时戳交换过程,因此有效地降低了通信开销.然而,这种方法存在以下两方面问题:

(1) 无线传感器网络通常由成百上千个节点组成,在部署前为每个节点获得“温度-频偏”映射表格,会耗费大量人力物力.因此,该方法仅适用于小规模传感器网络;

(2) 该方法假设“温度-频偏”映射关系不会随着时间变化,在同步过程中完全依赖于部署前获得的映射表进行同步.然而这种假设并不成立,因此,该方法会带来较高的同步误差.

针对以上问题,本文提出一种基于温度感知的、自适应的无线传感器网络时间同步算法.该算法能够对频偏与温度之间的关系进行动态估计及更新,并依赖该关系以及本地温度信息进行时钟频偏的估计及补偿,从而在很大程度上降低了通信开销.除此之外,本文还提出了一种动态同步周期调节机制.该机制能够根据当前温度变化情况对时间同步周期进行调节,因此使得节点能够在满足特定同步精度的前提下,尽可能地减少能量消耗,从而达到能耗和精度的平衡.本文工作的主要贡献体现在以下几个方面:

(1) 根据频偏与温度之间的关系,本文提出了“温度敏感度因子(temperature sensitivity factor,简称TSF)”,并对其进行周期性的估计.与Yang等人提出的“温度-频偏”映射表相比,TSF能够更准确地描述温度频偏关系的动态变化,从而提高了时间同步精度.除此之外,TSF的提出,使得频偏估计不再依赖于先验知识,因此避免了部署前的大量实验;

(2) 基于TSF,本文提出了一种能量有效的分步时间同步算法TSFB(TSF based synchronization approach). TSFB在进行频偏估计以及补偿的过程中仅仅依赖于TSF以及当前温度信息,几乎不需要进行时间戳的交换.因此显著降低了通信开销.除此之外,由于TSFB算法对节点之间的相互通信依赖较低,因此能够适应野外恶劣环境造成的节点通信失效的情况,有较高的鲁棒性;

(3) 本文提出了一种动态周期调节机制,该机制能够根据当前同步误差累积情况以及温度变化情况动态调节TSF估计周期,使得同步能耗与同步精度相平衡.除此之外,该机值能够根据应用需求对不同节点的同步精度进行设置,使得TSFB方法适用于不同的应用需求.实验结果表明:在平均同步周期相同的情况下,适用动态周期的TSFB方法与适用固定周期的TSFB方法相比,同步误差降低了10%.

本文进行了大量的仿真实验,其结果表明:TSFB方法可将通信能耗降低至传统基于时戳交换的同步算法的10%;且在环境温度不断变化的情况下,80%的频偏估计值其误差小于0.5ppm.而EACS算法则有将近20%的频偏估计值的误差大于2.5ppm.

1 相关工作

无线传感器网络时间同步研究大致经历了3个阶段.早期提出的同步算法致力于提高同步精度.它们主要依赖于节点间的时间戳交换来获得时钟频偏时钟相偏等信息,并通过分析节点的通信传输延迟提高时间戳标记的准确度,减少了延迟不确定性对时间同步精度的不利影响,并在此基础上构造如生成树等集中式、平面型路由结构来向节点发送包含网络参考时间的同步消息,从而实现全网同步.比较著名的基于时戳交换的时间同步算法包括:

1) 采用接收者-接受者同步模式的RBS(reference broadcast synchronization)^[12]算法,该算法利用无线信号的广播特性消除了发送端延迟为同步精度带来的影响;

2) 改良自NTP协议的TPSN(timing-sync protocol for sensor networks)^[13]算法,该算法采用双向时戳交换机制,消除了时戳的传输延迟,同时采用MAC层时戳标志机制消除了其余网络延迟带来的影响;

3) 基于洪范路由的FTSP(the flooding time synchronization protocol)^[14]算法,该方法采用多时戳机制来防止中断处理过程中的抖动给同步精度带来的影响.

然而以上提出的时间同步算法主要是从降低同步过程中时间戳的传输延迟的角度来提升同步精度,它们并没有对造成时间同步的主要原因——时钟频偏进行深入的研究.

为了更有效地提升同步精度,研究人员开始研究节点时钟频偏的变化规律.起初,许多同步方法^{[16, 17]}用恒定频偏模型(constant-skew model)来描述时钟频偏,并利用线性回归分析对节点时钟频偏进行估计;随后,考虑到节点时钟频偏的不可预测性以及其变化范围的局限性,更多的算法^{[18, 19]}采用限定频偏模型(bounded-skew model)来描述时钟频偏.然而,由于该模型过高地估计了时钟频偏的不稳定性,因此导致了其过高的算法复杂度以及能耗.为了解决这一问题,Hamilton^[20],Liu^[21]以及Yang^[9]等人通过对时钟频偏的变化规律进行分析,提出了用“双模型”来描述时钟频偏的思想,即,认为时钟频偏会由于环境以及老化等因素在恒定频偏模型以及匀速模型(constant-rate skew model)之间发生变化,并利用卡尔曼滤波来对这种变化进行追踪,最终实现对时钟频偏的高精度估计.

以上提出的时间同步算法均采用基于时戳交换的频偏估计机制,然而与传统的网络不同,无线传感器网络为能源有限型网络.频繁的时戳交换会导致过高的通信开销,最终影响网络生命周期.为了解决这一问题,研究者们在同步过程中引入外部辅助信息来减少甚至消除时戳交换带来的通信开销.外部信息的形式分为两种: (1) 周期性外部信号;(2) 环境信息.对于利用周期性外部信号的同步方法,它们将该外部信号看作参考量,并通过对该信号进行采集来获取频率信息,依赖该频率信息进行时钟频偏的估计以及补偿,其中,具有代表性的信号有交流电信号^[22]、FM广播信号^[23]、WIFI信号^[24]以及日光灯信号^[25]等.然而,传感器网络大多部署在以上信号无法覆盖的野外环境,因此,Schmid^[10],Yang^[9]以及Castillo-Secilla^[11]等人提出了适用于野外恶劣环境的传感器网络同步方法——基于环境感知的时间同步方法.该类方法主要利用传感器节点晶振频率极易受到工作环境温度影响的特点,在节点部署前或同步过程中对节点频偏与其所处环境温度的相关性进行分析,并将相关关系以表格的方式存储在节点内,在同步过程中,依赖该表格以及当前温度信息进行频偏估计.由于这两种方法主要依赖于本地信息对频偏进行估计以及补偿,很大程度上降低了通信开销.然而,这类方法过分依赖于先验知识,在网络部署之前需要通过大量实验为每个节点获取“温度-频偏”映射表,因此限制了网络规模.同时,完全依赖于先验知识会导致过高的同步误差.

综上所述,无线传感器网络时间同步技术研究已经受到广泛的关注,并取得了一定成果.但目前,已有的同步方法仍然无法解决大规模野外环境下无线传感器网络的两个关键问题:(1) 过高的通信开销;(2) 精度与能耗之间的不平衡.

2 时钟偏移与时钟同步模型 2.1 相偏与频偏

相偏与频偏是描述两个节点时钟不同步程度的两个重要参数,相偏和频偏越大,表示两个节点不同步程度越严重.

· 相偏:将节点在真实时间t时刻的本地时间记作C_A(t).由于环境、节点老化以及制作工艺等因素的影响,节点A的本地时间C_A(t)与真实时间t不同.这里记节点A在真实时间t的时间相偏为q_A(t),则有:

qA(t)=CA(t)-t

(1)

· 频偏:节点频偏是节点相偏的变化速率,主要反映了节点频率与标称频率的差别.节点频偏是导致节点间时间不同步的本质原因.将节点A在真实时间t的时间频偏记作a_A(t),则有:

\[{\alpha _A}(t) = \frac{{{\theta _A}(t + \tau ) - {\theta _A}(t)}}{\tau }\]

(2)

其中,τ为采样间隔.

2.2 基于时戳交换的频偏估计方法

在传统时间同步方法中,节点的时间频偏可以通过与参考节点进行时间戳交换来获得,这里将参考节点的时间看作标准时间.假设需要获得节点A相对于节点B(参考节点)的时间频偏,因此需要由节点A周期性地向节点B发送时间戳,如图1所示,节点A在时间C_A(t₀)和C_A(t₁)分别向节点B发送两个时间戳,时间戳中包含了节点A发送该时间戳的时间.

节点B分别在时间${C_B}({t'_0})$和${C_B}({t'_1})$收到了来自节点A的时间戳,因此,节点B可获得以下两条信息:

1) 在t₁-t₀时间段内,节点A测量到的时间间隔为C_A(t₁)-C_A(t₀);

2) 在t₁-t₀时间段内,节点B测量到的时间间隔为C_B(t'₁)-C_B(t'₀).

这里,将节点B看作标准时间,则可获得节点A相对于节点B在t₀及t₁时刻的相偏分别为

\[\begin{array}{l} {{\hat \theta }_{A,B}}({t_0}) = {C_A}({t_0}) - {C_B}({{t'}_0})\\ {{\hat \theta }_{A,B}}({t_1}) = {C_A}({t_1}) - {C_B}({{t'}_1}) \end{array}\]

(3)

\[{\hat \alpha _{A,B}}({t_1}) = \frac{{{\theta _{A,B}}({t_1}) - {\theta _{A,B}}({t_0})}}{{{C_B}({{t'}_1}) - {C_B}({{t'}_0})}} = \frac{{({C_A}({t_1}) - {C_A}({t_0})) - ({C_B}({{t'}_1}) - {C_B}({{t'}_0}))}}{{{C_B}({{t'}_1}) - {C_B}({{t'}_0})}}\]

(4)

采用这种方法获得的时间相偏包含了传输延迟带来的误差,如图1所示的d₀和d₁.这里,将传输延迟误差记作d,且将d看作是高斯噪声:

\[d\tilde{\ }N({{\mu }_{d}},\sigma _{d}^{2}),\]

其中,μ_d以及$2\sigma _d^2$是由硬件或软件性能决定的,可通过实验获得.

2.3 温度敏感度因子TSF

在节点制作工艺以及节点老化等因素的影响下,节点晶振的实际输出频率与其标称频率存在差异.除此之外,根据文献^{[9, 10, 11]},节点晶振输出频率会随着其所处环境温度的变化而变化,该变化规律主要表现为一个二次函数(如公式(5)及图2所示).晶振的这一特性导致了其输出频率的不稳定性,给节点时钟同步带来了严峻挑战.

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

(5)

公式(5)中:f(t)代表当前节点输出频率;f₀代表标称频率;k代表温度系数,即,频偏对温度的敏感度,反映了节点晶振当前的稳定程度^{[26, 27]},在通常情况下,k=-0.034±0.006ppm/°C;T(t)代表当前温度.频率随温度的变化趋势如图2所示.根据第2.1节,节点频偏主要是由其晶振频率的漂移造成的,因此节点频偏a(t)还可表示为与标准频率f₀以及节点当前频率f(t)相关的函数:

\[\alpha (t) = \frac{{{f_0}}}{{f(t)}} - 1\]

(6)

根据公式(5)、公式(6)可以看出,节点频偏值对温度的变化十分敏感.比如:当温度从25°C下降至15°C时,相应的频偏变化为4ppm(即,每秒4μs).所以节点在对频偏进行估计时,为了达到提高估计精度同时降低能耗的目的,同步算法需要将温度对频偏的影响考虑在内.

理想状态下,节点的当前频偏可以通过对节点当前所处温度的测量,并将测量结果带入公式(5)、公式(6)获得.然而实际情况并非如此,下面将对此进行详细说明.

在实际情况下,节点晶振稳定性差的特性导致其同样易受到除温度外其余环境因素的影响,如电压、湿度、震动等.根据文献^{[28, 29, 30]},节点当前电压越低,其晶振稳定性越差.且在无线传感器网络中,节点通常由电池供电,因此节点电压值会随时间不断降低,从而节点稳定性也会随之不断变化.因此,为了更准确地描述节点时钟频偏与温度的关系,公式(5)中温度系数k应表示为一个动态变量k(t),如公式(7)所示.而对于湿度、震动等其他影响因素,由于其相较于温度对节点频偏产生的影响很小,因此在本文中,我们将其影响看作系统噪声.

k(t)=k+ωk(t)

(7)

公式(7)中,ω_k(t)表示t时刻的温度系数与公式(5)中的标准温度系数k之差;且由于电压等因素对k(t)的影响具有持续性,因此,ω_k(t)满足:

\[\varpi \tilde{\ }N({{\mu }_{\varpi }},\sigma _{\varpi }^{2}).\]

因此可以得到以下结论:

定理1. 根据公式(5)得到的当前频率估计值$\hat f(t)$并非节点当前真实输出频率f(t)的无偏估计,且估计误差为f₀×μ_k×(T(t)-T₀)².

证明:根据公式(7),公式(5)中的标准温度系数k可看作:

k=k(t)-ωk(t).

因此可以得到t时刻频率估计值$\hat f(t)$的期望为

\[\begin{array}{l} E[\tilde f(t)] = E[\hat f(t) - f(t)]\\ \;\;\;\;\;\;\;\;\;\;\; = E[{f_0}(1 - k{(T(t) - {T_0})^2}) - {f_0}(1 - k(t) \cdot {(T(t) - {T_0})^2})]\\ \;\;\;\;\;\;\;\;\;\;\; = {\rm{ }}E[{f_0}(1 - \left( {k(t) - {\varpi _k}(t)} \right) \cdot {(T(t) - {T_0})^2}) - {f_0}(1 - k(t) \cdot {(T(t) - {T_0})^2})]\\ \;\;\;\;\;\;\;\;\;\;\; = {\rm{ }}{f_0} \cdot E[(k(t) - {\varpi _k}(t)) \cdot {(T(t) - {T_0})^2} - k(t) \cdot {(T(t) - {T_0})^2}]\\ \;\;\;\;\;\;\;\;\;\;\; = {f_0} \cdot {\mu _k} \cdot {(T(t) - {T_0})^2} \ne 0. \end{array}\]

因此根据公式(5)得到的当前频率估计值$\hat f(t)$并非节点当前真实输出频率f(t)的无偏估计.

讨论:根据实验可得,μ_k通常为10^-9KHz/°C.假设节点周围环境变化范围为-10°C~40°C,因此可得T(t)-T₀的均值为15.节点标称频率为f₀=32.768KHz.因此,根据公式(5)获得的频率估计误差数量级为 10^-6.

根据定理1,由于电压对节点晶振稳定性的影响,将温度系数看作常量会带来较高的同步误差.因此,应将温度系数看作与时间相关的变量k(t).根据文献^[29],节点电压的变化速度较慢,因此只要在同步过程中周期性地对k(t)进行估计及更新,即可很大程度上降低电压对晶振稳定性带来的影响.然而温度-频偏关系系数的在线估计复杂度过高,且需要大量的通信开销来获得大量频偏值,这违背了传感器节点计算资源及能耗有限的特性.

考虑到以上问题,我们引入了温度敏感因子TSF(t)(temperature-skew sensitivity factor)来描述温度与频率之间的动态关系,并对TSF(t)进行周期性更新.TSF(t)将温度与频率之间的关系看作是一个关于时间t的函数,它描述了当前环境下节点晶振频率对环境温度的敏感程度,TSF(t)越大,表示当前节点频率对温度变化越敏感.

\[TSF(t) = \frac{{f(t) - f(t - \tau )}}{{T(t) - T(t - \tau )}}\]

(8)

TSF(t)的引入,使得节点时间同步过程可以仅仅依赖于本地信息,降低了通信开销;并且TSF(t)的估计复杂度远低于温度系数,能够适用于计算能力有限的无线传感器网络.

3 基于TSF估计的时间同步方法

本节具体介绍基于TSF估计的时间同步算法的基本思想及其具体实现方式.

3.1 时间同步方法

节点间的时间不同步主要表现在节点之间存在时间相偏θ(t),而根据第1.1节关于相偏与频偏的分析可知,节点之间存在相偏的根本原因是节点之间频偏的不断累积,即:

\[\theta ({t_i} + t) = \theta ({t_i}) + \int_{{\rm{ }}{t_i}}^{{\rm{ }}{t_i} + t} {\alpha (t){\rm{d}}t} .\]

理论上,如果节点的相偏估计及补偿频率足够高,则可以保持较高的同步精度,如图3中第1种方法所示.然而,这种高同步精度是以极大的通信开销为代价的.如果能够对节点每一时刻的频偏进行准确的估计,便可以根据该频偏值获得相偏,因而能够延长“再同步”周期(即,包交换周期),从而降低了通信开销.因此,节点需要周期性地对频偏进行估计及补偿以抑制相偏增长,如图3中的FTSP算法所示.

在传统的同步算法中,如FTSP^[14]算法,频偏的变化在短时间段内认为是可以忽略的,因此从降低能耗的角度出发,只要周期性地对频偏进行估计及更新,就可以保证节点在“休眠”阶段(即,两次频偏估计之间的间隔)无需进行时间戳交换,仍可以依赖上一周期频偏估计值进行相偏更新以及本地时间补偿,如图3所示,箭头表示数据包交换过程.因此可以看出:与不进行频偏估计,仅进行基于时戳交换的相偏估计的算法相比,FTSP很大程度上降低了通信开销.TCTS^[10]算法对FTSP进行了改进,该算法考虑到了温度对频偏的影响,利用一个“温度-频偏”表格对频偏进行估计.如图3所示,由于在同步的初始阶段,表格为空,因此TCTS算法在此阶段与FTSP基本相同,周期性地进行基于时戳交换的频偏估计,只是在估计的过程中将频偏值与相应的温度值记录在一个“温度-频偏”表格内.当表格建立到一定规模,节点能够在表格中找到与当前温度相匹配的入口时,便进入同步阶段.在该阶段,仅根据当前温度与“温度-频偏”表格来进行频偏估计.然而,当再次出现当前温度无法在表格中查找到的情况时,节点会再次返回表格建立阶段进行基于包交换的频偏估计以及频偏记录过程.TCTS算法比FTSP算法通信开销低,然而却仍存在一个问题:与EACS方法相同,该方法假设“温度-频偏”映射关系不会随着时间发生变化,在同步过程中完全依赖于部署前获得的映射表进行同步.然而这种假设并不成立,因此该方法同样会带来较高的同步误差.

本文提出的算法是一种基于TSF的时间同步(temperature sensitivity factor based,简称TSFB)算法.该方法的周期关系如图4所示.

TSFB方法可分为两个阶段:(1) TSF估计阶段;(2) 基于TSF的同步阶段.在TSF估计阶段,节点首先通过包交换的方法对温度敏感因子TSF进行估计,获得TSF值之后,进入同步阶段;同步阶段根据当前TSF值以及节点当前所处环境温度,通过公式(5)、公式(6)对频偏进行估计,不需要依赖包交换.然而由第1.3节可知,频率对温度的敏感程度TSF会随着环境动态变化.因此,在经过ΔT时长的同步过程后,节点将再次回到TSF估计过程,对当前TSF值进行更新,以便适应新的环境.

TSFB算法能够依赖TSF敏感度因子对时间频偏进行估计,相对于FTSP算法,很大程度上降低了通信开销(如图4所示,包交换过程仅在进行TSF估计时才会进行);并且与TCTS算法不同,TSFB算法认为节点频偏与当前环境温度之间的关系是不断变化的,并通过对TSF值的不断更新来适应这种动态变化,因此提高了同步精度.

3.2 TSF估计

TSF估计阶段的主要任务为:通过待同步节点与其对应的参考节点之间进行的数据包交换,来获得节点当前相偏以及频偏;并以此为基础,根据节点当前所处的环境温度变化情况以及节点自身相应的频率变化情况对节点当前温度敏感度因子TSF进行估计.为描述方便,下面我们称待同步节点为节点A,其对应的参考节点为节点B.

由于在进行同步的初始时刻,节点A并不知道其当前敏感度因子TSF(t),因此这一阶段中的频偏估计主要依赖于节点A与参考节点B之间的数据包交换.该频偏估计过程与FTSP^[14]算法中的频偏估计过程相同,只是在频偏估计的过程中需要同时记录温度,这里不再赘述.

根据本周期TSF估计阶段获得的节点频率f[i](这里,节点频率的获取可以通过节点频偏以及公式(6)获得)、上一周期TSF估计阶段获得的节点频偏f[i-1]以及本周期获得的温度值T[i]、上一周期获得的温度值T[i-1],获得当前节点的温度敏感度因子TSF[i]:

\[TSF[i] = \frac{{f[i] - f[i - 1]}}{{T[i] - T[i - 1]}}\]

(9)

假设在下一次TSF估计阶段之前的ΔT时间段(即,基于TSF的时间同步阶段)内节点的TSF不会发生变化,节点将转入同步阶段.在该阶段,节点主要依赖TSF估计阶段得到的TSF值来进行频偏估计以及本地时间补偿,不需要任何包交换过程.

3.3 基于TSF的时间同步

基于TSF的同步阶段的主要任务为:根据TSF估计阶段获得的温度敏感因子TSF以及温度传感器获得的节点当前温度值进行频偏估计.该阶段无需依赖于节点之间的包交换.

在该阶段,节点周期性地对其当前所处环境温度进行采样(这里的周期指的是同步阶段内部的温度采样周期,与TSF估计周期不同),这里,将第j个采样周期获得的温度值记为T[j].采样过后,节点根据当前环境温度值T[j]以及当前温度敏感因子TSF对当前频偏进行估计.因此,节点A在第i个同步周期的第j个采样周期的频率f[j]以及频偏a_A[j]可更新为

\[\hat{f}[j]=f[i]+TSF[i]\cdot (T[j]-T[i])\]

(10)

\[\hat{\alpha }[j]=\frac{{{f}_{0}}}{\hat{f}[j]}-1\]

(11)

接下来,对节点依赖公式(10)进行频率估计带来的误差进行分析.节点在TSF估计阶段获得的频率值是对多次数据包交换的结果采用最小均方方差方法获得的,是对节点当前频率的无偏估计^[14],因此假设公式(9)中的f[j]以及f[j-1]为第i个以及第i-1个TSF估计阶段的节点当前频率真实值,因此可得以下结论.

定理2. 公式(10)获得的当前频率估计值$\hat f[i]$的估计误差为f₀×k×σT².

证明:为计算方便,在证明过程中假设T[i]-T[i-1]=T[j]-T[i]=δT,因此,公式(10)中的频率估计值可以表示为

\[\hat{f}[j]=f[i]+\frac{f[i]-f[i-1]}{T[i]-T[i-1]}\cdot (T[j]-T[i])=f[i]+\frac{f[i]-f[i-1]}{\delta T}\cdot \delta T\]

(12)

因此,根据公式(12),$\hat f[j]$估计误差的期望值为

\[E[\tilde{f}[j]]=E[\hat{f}[j]-f[j]]=E\left[ f[i]+\frac{f[i]-f[i-1]}{\delta T}\cdot \delta T-f[j] \right]\]

(13)

根据公式(5)对公式(13)中的f[i]以及f[i-1]进行替换,得到:

\[\begin{align} & E[\tilde{f}[j]]=E[2{{f}_{0}}(1-k{{(T[i]-{{T}_{0}})}^{2}})-{{f}_{0}}(1-k{{(T[i]+\delta T-{{T}_{0}})}^{2}})-{{f}_{0}}(1-k{{(T[i]-\delta T-{{T}_{0}})}^{2}})] \\ & \text{ }=E[{{f}_{0}}\cdot k\cdot (2{{(T[i]-{{T}_{0}})}^{2}}-{{(T[i]+\delta T-{{T}_{0}})}^{2}}-{{(T[i]-\delta T-{{T}_{0}})}^{2}})] \\ & \text{ }={{f}_{0}}\cdot k\cdot \delta {{T}^{2}}. \\ \end{align}\]

证毕.

讨论:由于节点的温度采样速率很快,且TSF估计周期通常小于18min(第5.3节实验获得),因此可以认为,通常情况下有δT<0.5°C.根据第2.3节,节点晶振温度系数为k=(3.39±1.0)×10^-8,节点标称频率f₀=32.768KHz,因此,频率估计误差数量级为10^-8.然而根据定理1,通过公式(5)得到的频率误差数量级为10^-6,因此,通过公式(10)对节点频率进行估计能够很大程度上降低估计误差.

在对节点频偏进行更新之后,同样需要对其相偏进行估计以及更新.我们假设采样间隔内节点的频偏不会发生变化,因此,节点A在第j个采样周期的相偏q[j]可以根据上一次相偏估计结果$\hat \alpha [j - 1]$以及采样周期Δt获得:

\[\hat{\theta }[j]=\hat{\theta }[j-1]+\text{ }\!\!\Delta\!\!\text{ }t\cdot \hat{\alpha }[j-1]\]

(14)

在对时间相偏进行更新之后,根据$\hat \theta [j]$的值决定是否对时钟进行补偿.这里引入阈值θ_th,且θ_th的值通常设置为节点时钟周期长度.当$\hat \theta [j]$值超过这个阈值时,认为节点频偏超过应用可承受范围,需要进行时钟补偿,补偿方法为

C[j]=C[i-1]+θ[j].

接下来,对节点依赖公式(14)进行相偏估计带来的误差进行分析.

定理3. 节点在同步阶段的相偏累计估计误差为

\[{{\delta }_{\theta [N]}}={{\delta }_{{{\theta }_{0}}}}+\text{ }\!\!\Delta\!\!\text{ }t\cdot \sum\limits_{j=1}^{N}{{{\delta }_{\alpha [j]}}}\]

(15)

其误差方差为

\[\sigma _{\theta [N]}^{2}=\sigma _{{{\theta }_{0}}}^{2}+\text{ }\!\!\Delta\!\!\text{ }{{t}^{2}}\cdot \sum\limits_{j=1}^{N}{\sigma _{\alpha [j]}^{2}}\]

(16)

其中,N为同步阶段内的频偏估计次数(即,温度采样次数),${\delta _{{\theta _0}}}$以及$\sigma _{{\theta _0}}^2$分别为TSF估计阶段通过包交换获得相偏的估计误差以及误差方差.

证明:节点在第N个温度采样时刻的真实相偏为

\[\theta [N]={{\theta }_{0}}+\text{ }\!\!\Delta\!\!\text{ }t\cdot \sum\limits_{j=1}^{N}{\alpha [j]}.\]

而根据公式(14),节点在第N个温度采样时刻的相偏估计值可表示为

\[\hat{\theta }[N]={{\hat{\theta }}_{0}}+\text{ }\!\!\Delta\!\!\text{ }t\sum\limits_{j=1}^{N}{{{{\hat{\alpha }}}_{A}}[j-1]}.\]

因此,节点在第N个温度采样时刻的相偏估计误差值为

\[{{\delta }_{\theta [N]}}=\hat{\theta }[N]-\theta [N]=\left( {{{\hat{\theta }}}_{0}}+\text{ }\!\!\Delta\!\!\text{ }t\sum\limits_{j=1}^{N}{{{{\hat{\alpha }}}_{A}}[j-1]} \right)-\left( \theta [N]={{\theta }_{0}}+\text{ }\!\!\Delta\!\!\text{ }t\cdot \sum\limits_{j=1}^{N}{\alpha [j]} \right)={{\delta }_{{{\theta }_{0}}}}+\text{ }\!\!\Delta\!\!\text{ }t\cdot \sum\limits_{j=1}^{N}{{{\delta }_{\alpha [j]}}}.\]

于是,其误差方差为

\[\sigma _{\theta [N]}^{2}=\sigma _{{{\theta }_{0}}}^{2}+\text{ }\!\!\Delta\!\!\text{ }{{t}^{2}}\cdot \sum\limits_{j=1}^{N}{\sigma _{\alpha [j]}^{2}}.\]

证毕.

讨论:从定理3可以看出,节点在同步阶段的累计误差主要受到该阶段内频偏估计间隔Δt、频偏估计次数N以及频偏估计误差δ_α[j]的影响.由于同步阶段内的频偏估计不需要依赖数据包的交换,因此缩短Δt不会造成能耗的上升.因此,Δt对同步误差带来的影响可以通过简单地缩短频偏估计间隔来降低.在Δt确定的情况下,频偏估计次数N主要取决于同步阶段时长ΔT(如第3节所述):

\[N=\left| \frac{\text{ }\!\!\Delta\!\!\text{ }T}{\text{ }\!\!\Delta\!\!\text{ }t} \right|.\]

因此,N带来的影响实质上是ΔT对同步误差带来的影响.关于频偏估计误差δ_α[j],根据公式(11)、公式(12)以及定理2可知,频偏估计误差δ_α[j]与频偏估计间隔内的温度变化δT正相关.因此,节点在同步阶段的累计误差δ_θ[N]主要受到以下两个因素的影响:

· 同步阶段时长,即TSF估计周期ΔT;

· 频偏估计间隔内的温度变化δT.

下面通过仿真实验结果来验证以上结论,如图5、图6所示.

图5描述了当TSF估计间隔ΔT分别为1 500,1 800,2 000,2 300以及2 500时的相偏估计误差值.温度变化曲线如后文图9所示.很明显地,当ΔT延长时,频偏估计误差平均值会不断上升.这是由于:(1) TSF估计周期的延长会导致相偏估计误差无法及时被补偿,因此导致误差不断累积并偏离其真实值;(2) TSF估计周期的延长会导致在间隔内的温度变化值δT升高,δT的升高会导致频偏误差升高,从而间接导致相偏误差的累积.为了反映在恶劣环境下TSFB算法的频偏估计误差情况,整个仿真过程基本处于“温度变化”状态,因此,图5中所示的相偏估计误差要高于真实环境下的误差.

图6描述了频偏估计误差随温度变化的情况.曲线“—”描述了温度变化趋势,三角曲线“”描述了频偏估计误差变化情况.很明显:当温度变化平缓时,频偏估计误差值相对较低;反之,当温度处于上升阶段(如图所示3000s~ 9000s)时,频偏估计误差值开始迅速上升.这是因为,当节点所处环境温度发生明显变化时,节点的频率估计误差升高,从而导致了频偏估计误差的升高.

3.4 TSF估计周期调节

根据第3.3节,时间同步误差主要受两个因素影响:TSF估计周期ΔT以及频偏估计间隔内的温度变化δT.缩短TSF估计间隔ΔT可以很明显地达到降低同步误差的目的,然而根据第3.1节,TSF的估计过程需要进行数据包交换,盲目地缩短TSF估计周期会增加数据包交换频率,从而增加通信开销.为了解决这一矛盾,TSFB算法采用一种动态周期调节机制,该机制能够根据当前同步误差以及温度变化情况动态地调节TSF估计周期,使得节点能够在满足特定同步精度的前提下,尽可能地减少能量消耗,从而达到能耗与精度的平衡.

本文引入误差控制因子μ来限制在ΔT时间段内误差的累积,引入温度调节因子λ来调节不同温度变化情况下的ΔT.同时,用e[i]来表示在进行第i个TSF估计时周期的误差累积状况(在TSFB中,误差累计看作根据公式(14)得到的相偏与根据TSF周期根据包交换获得的相偏之差),用当前温度变化速率DT[i]来描述温度稳定情况;d表示同步阶段的标准时长.那么从当前时刻到下一次TSF估计阶段的间隔ΔT[i+1]可更新为

ΔT[i+1]=min(d1,d2)

(17)

\[{{d}_{1}}\text{=}d\cdot \frac{\mu }{e\left[ i+1 \right]}\]

(18)

\[{{d}_{2}}=d\cdot \frac{\lambda }{DT[i]}\]

(19)

\[DT[i]=\frac{T[i+1]-T[i]}{\text{ }\!\!\Delta\!\!\text{ }T[i]}\]

(20)

从公式(17)~公式(19)可以看出:当误差开始累积或温度突然变化时,TSF估计间隔ΔT会缩短,从而达到降低相偏估计误差的目的;反之,当误差很小,或温度变化缓慢时,ΔT会随之延长以达到降低能耗的目的.公式(20)为温度变化速率DT[i]的度量方式,即,用上一同步阶段内温度的平均变化率来描述当前温度变化情况.在实际应用中,TSFB主要根据d₁对ΔT进行调节来平衡能耗和误差值.然而当温度发生明显变化时,根据公式(17),温度将成为影响频偏估计精度的主要因素,此时,TSFB会根据温度变化情况来调节ΔT以适应该变化,如公式(19)所示.

在无线传感器中通常存在多个应用,如数据融合、休眠调度、目标追踪等,这些应用对时间同步的精度要求各不相同,因此在设计同步算法时,需要同时考虑不同应用对同步精度的需求.TSFB可以通过对误差控制因子μ以及温度协调因子λ高能效地满足其对同步精度的需求.对于对同步精度要求较低的应用,如数据融合技术,节点可以适当升高μ以及λ的值,以达到降低能耗的目的;而对于对同步精度要求较高的应用,如基于TOA的定位技术,节点可以适当降低μ以及λ的值来保证定位准确性.关于参数d,μ以及λ的取值将在第5.3节进行讨论.

然而,这种周期调节方式仍然存在一个问题.如图7中虚线框区域所示,当温度突然发生变化时(对应后文图9),当前同步阶段的频偏估计值(点线所示)严重偏离真实值(实线所示).这是由于TSFB在进行TSF估计间隔ΔT的更新时,是以上一周期的误差累积及温度变化情况为依据的,从而导致在TSF估计间隔ΔT内的温度变化值δT过高,因此带来了较大的频偏估计误差(根据定理2).

针对上述问题,本文提出一种“应急机制”,即:当节点在温度平缓的同步阶段一旦检测到温度发生突发性的明显变化时,无论当前ΔT是否均应转入TSF估计阶段,节点都应及时对TSF值进行估计及更新,以应对温度的突然变化.图8所示为增加“应急机制”之后节点的频偏估计情况,可以看出:由于在第3 500s时对TSF的及时更新,使得虚线框所示区域内的频偏估计误差升高现象得到明显的改善.需要注意的是:这种“应急机制”仅针对温度上升的初期所遇到的第1个估计周期(即图7、图8中虚线框所示区域),随后的温度上升过程中不会触发该应急机制.

4 实验结果与分析

我们通过大量的仿真实验验证了TSFB算法的时间同步性能,并主要从3个方面描述TSFB算法的性能特征:(1) 时间同步精度;(2) 通信开销(即包交换次数);(3) 鲁棒性.参与对比实验的时间同步方法包括:(1) FTSP算法^[14];(2) EACS算法^[9];(3) TCTS算法^[10].

4.1 实验初始化

· 温度模拟

我们首先模拟出一条温度变化轨迹,如图9所示;且为了证明本方法在温度变化情况下的同步性能,该轨迹主要在两种温度状况之间交替:温度平缓以及温度上升状态.温度变化范围为25°C~43°C.需要说明的是:为了反映各种算法在恶劣环境下TSFB算法的频偏估计误差情况,仿真实验中模拟的温度变化轨迹基本处于“温度迅速上升”状态.因此,第4.2节中所有算法的同步误差要高于正常环境下的误差值.

· 节点真实频率模拟

首先对节点在真实环境下的温度系数k(t)进行模拟.根据第2.3节,温度系数k(t)主要与节点当前电压值相关.而节点电压值会随时间不断降低,因此,真实环境下的节点温度系数k(t)会随着时间不断升高.本文仿真实验假设在实验过程中节点电压随时间线性变化^[29],因此,这里将节点温度系数看作参数为k_H与k_L的均匀分布,即:

K~U(kH,kL).

其中,根据文献^[29]的实验结果,节点电压在12 000s内大约下降0.2V,因此,本实验设定:

kH=-0.027ppm/°C,kL=-0.028ppm/°C[29].

在对节点真实频率进行模拟时,还需考虑湿度、震动等其他影响因素.然而相较于温度,其对节点频偏产生的影响很小,因此在本文中,我们将其影响看作均值为0的高斯噪声$h\tilde{\ }N(0,\sigma _{h}^{2}),$其中,s_h=8x10^-5KHz^[26].因此,仿真实验中,节点真实频率为

f(t)=f0(1-k(t)×(T(t)-T0)2)+h(t)

(21)

其中,f₀=32.768KHz,T₀=25.

· 同步周期配置

根据文献^{[9, 10, 14]},本文仿真实验的周期配置见表1.

对于TSFB算法,其数据包交换周期是动态变化的,若无特殊说明,本文实验部分对TSFB算法同步周期相关参数的设定可见表2.

数据包交换周期根据公式(17)~公式(20)计算得到.

· 误差计算方法

算法同步精度性能主要通过算法的频偏估计误差以及同步误差体现,其中,频偏估计误差定义为节点真实频偏skew_TRUE与根据TSFB算法估计的频偏skew_EST之差,即:

skewERROR=skewTRUE-skewEST

(22)

skew_TRUE可通过公式(21)与公式(11)获得,skew_EST则通过公式(9)~公式(11)获得.同步误差定义为真实相偏offset_TRUE与节点估计相偏offset_EST之差,即:

offsetERROR=offsetTRUE-offsetEST

(23)

offsetTRUE=skewTRUE×Δt

(24)

offset_EST可通过公式(14)获得.

4.2 TSFB算法同步精度性能分析

相比于其他基于环境感知的同步算法,TSFB算法的一个明显改进是:其认为温度与频偏的关系是动态变化的,因此采用了动态估计而非依赖于先验知识的方法来获得温度与频偏关系,从而能够提高算法同步精度.本文通过对4种算法:1) EACS算法^[9],2) TCTS算法^[10],3) 固定周期TSFB算法,4) 动态周期TSFB算法的频偏估计精度进行比较,证明了TSFB算法的优势.

图10描述了不同包交换间隔下,TCTS算法、固定周期TSFB算法以及动态周期TSFB算法的频偏估计误差情况.我们首先对动态周期的TSFB算法进行仿真,为了验证不同周期下的算法性能,在实验初始时,取标准TSF估计周期长度d(见第3.4节的公式(18)、公式(19))分别为1 500s,1 800s,2 000s,2 300s以及2 500s.实验结束后,得到平均包交换间隔分别为1 050s,1 190s,1 380s,1 450s以及1 950s.然后,根据得到的平均包交换间隔来设置TCTS算法的再同步周期 以及固定周期TSFB算法的TSF估计周期,并重复实验.实验结果如图10所示.我们给出了不同包交换周期下各种算法频偏周期的平均值以及最大值.通过对TCTS算法以及TSFB算法性能的比较可以看出:比起TCTS算法,固定周期TSFB算法的频偏估计误差降低了10%,而动态周期TSFB算法的频偏估计误差降低了20%.这是由于TSFB算法能够对温度与频偏之间的敏感程度TSF进行动态估计,从而能够有效避免由于环境带来的当前“温度-频偏”对应关系与先验知识不符所带来的频偏估计误差,因此提高了同步精度.通过对固定周期以及动态周期TSFB算法的比较可以看出:当包交换间隔相同时,相比动态周期TSFB,固定周期TSFB会增加10%的同步误差.这是由于,动态周期调节机制使得同步算法能够更好地适应温度等环境的变化,从而达到能耗和精度的平衡.

从图10中我们还可以发现:当数据包交换间隔较短时(比如小于1 200s),动态周期调节机制的引入对同步精度的提升并不明显.这是由于,当算法的包交换频率较高时,ΔT时间段内的温度上升值δT很低,因此无论是否采用动态周期调节机制,都不会导致频偏估计误差的升高.因此在包交换频繁的情况下,使用动态周期意义不大.最后,为了将频偏估计误差控制在0.8ppm以下,我们设置标准TSF估计周期长度d=2000s.

图11反映的是3种算法在平均数据包交换周期为1 880s的情况下,频偏估计误差CDF的累积情况.

从图11中可以明显得出:

1) 在环境温度不断变化的情况下,80%的频偏估计值的误差小于0.5ppm;而EACS算法则有将近20%的频偏估计值的误差大于2.5ppm;

2) 在误差较低的区域,EACS算法的性能优于TSFB算法.这是由于在某些情况下,温度与频偏之间的关系符合先验知识(即,EACS的“温度-频偏”表格);且由于表格的获得基于卡尔曼滤波去噪,因此在该情况下的EACS算法频偏估计误差相对较低.而由于EACS无法捕捉温度与频偏关系的变化,因此会带来将近20%的高误差;

3) 由于动态周期调节机制主要针对于改善由于温度变化引起的固定周期TSFB算法误差较大的部分,因此可以看出,对于误差大于1ppm的频偏改善得较为明显.这是由于,在温度变化缓慢的情况下,TSFB算法对TSF估计周期长度不敏感,即使在TSF估计周期ΔT延长的情况下也不会造成δT的明显变化.因此在该情况下,动态周期调节机制对算法性能的改善不够明显.

4.3 TSFB算法通信能耗性能分析

由于在仿真过程中无法对节点的能耗进行模拟,且由于在同步时的主要能耗是通信能耗,因此这里用包交换的次数作为评价标准来代替节点的能耗,以此说明TSFB在能耗方面的优势.

我们取误差控制因子μ=5,10,12,25,30个时钟周期(每个时钟周期为30.515μs),取温度协调因子λ=0.6,0.8,1.0,1.2,1.4°C分别进行实验,实验温度变化同样如图9所示.实验过程中统计包交换次数以及平均包交换间隔,统计结果如图12、图13所示.

很明显地,包交换次数会随着误差控制因子μ以及温度协调因子λ的增大而减少,原因已在第2.3节加以说明.因此,针对不同的应用,可以通过对误差控制因子μ以及温度协调因子λ高能效地满足其对同步精度的需求.除此之外,我们还观察到:随着μ以及λ的增大,数据包交换间隔变化趋于平缓.这是由于,当误差控制因子μ取值很大时,温度协调因子会根据当前温度值控制TSF估计周期ΔT的增长,以保证同步精度;反之亦然.

对于误差控制因子μ,当参数μ从150μm变化到300μm时,时间戳的交换次数明显减少.同时,平均TSF估计间隔明显增大;而在参数μ变化到300μm之后,这两项参数的变化趋于平缓.因此,本方法在精度控制参数μ=300μs时的性能最佳.同样地,对于温度协调因子λ,当参数λ从0.8°C变化到1.0°C时,时间戳的交换次数明显减少.同时,平均TSF估计间隔明显增大;而在参数λ变化到1.0°C之后,这两项参数的变化趋于平缓.因此,本方法在精度控制参数λ=1.0°C时的性能最佳.

从图12、图13还可以看出:即使在误差控制因子μ以及温度协调因子λ取值均非常低(μ=150μs,λ=0.6°C)的情况下,仍能够保证数据包交换周期大于900s.这相比于FTSP算法的150s,极大地降低了通信能耗,因此证明了TSFB算法能够在保证精度的前提下降低能耗,十分适用于能量有限的无线传感器网络.

4.4 TSFB算法鲁棒性

比起基于时间戳交换的时间同步算法FTSP,TSFB算法的另一个明显优势为:在待同步节点通信失效的情况下,TSFB算法仍然能够维持较高的同步精度;而此时,FTSP算法则无法进行时间同步.

与传统网络不同,无线传感器网络通常部署在室外环境中.因网络环境影响以及节点本身的变化,网络拓扑结构将发生动态变化,从而影响了节点之间的正常通信.除此之外,现场环境(如暴风雪等恶劣天气条件)也随时会影响无线链路的通信质量.因此,在通信失效的情况下,同步算法的鲁棒性十分重要.下面通过仿真实验对TSFB算法以及FTSP算法在通信失效情况下的算法性能进行对比,以证明TSFB算法鲁棒性强的特点.

实验模拟了从1 000s处开始,节点通信失效的情景.如图14所示,从1 000s开始,FTSP算法的同步误差开始上升.这是由于在无法进行时间戳交换的情况下,FTSP算法将会停止时钟频偏的估计和更新,时钟的补偿只能依赖最近一次的频偏估计结果进行.且如图14所示,节点环境温度值从3 000s开始不断上升,这使得节点的频偏不断发生变化.而此时,由于无法进行时戳交换,FTSP算法无法对频偏估计值进行更新,导致同步误差上升速度加快,最终带来了巨大的误差累积.然而对于TSFB算法,在通信失效的情况下,即使温度不断发生变化(如图14所示),仍然能够保持相对较低的同步误差.如图14所示,通信失效情况下的TSFB算法与正常通信情况下的TSFB算法相比,在12 000时长内的最终同步误差累积结果仅相差1s.这是因为通信失效仅导致TSF值无法正常更新,而节点依然可以根据最近一次TSF估计结果以及传感器节点采集到的温度信息来对频偏进行更新.因此证明:在节点通信失效以及环境温度不断变化的条件下,TSFB算法依然能够保证较低的同步精度.

5 总结与展望

在资源受限的无线传感器网络中,传感器节点的廉价晶振易受到温度干扰的特性,为室外环境下大规模传感器网络时间同步带来了两个严重问题:(1) 过高的通信开销;(2) 精度与能耗之间的不平衡.本文提出了一种基于温度感知的自适应时间同步算法TSFB,该协议分别利用基于TSF的频偏估计机制和动态同步周期调节机制解决了上述两个问题.而且大量的仿真实验结果表明:TSFB同步算法具有高精度、低能耗以及高鲁棒性等特点,尤其适用于大规模野外部署的传感器网络.

下一步的研究工作包括:(1) 分析温度测量误差以及网络规模对TSFB算法稳定性产生的影响,并结合对电压、湿度以及震动等其他影响因子的分析确定TSFB算法的误差范围,在此基础上,更好地实现按需同步这一思想;(2) 实现同步误差的在线估计以及补偿,进一步提高算法的同步精度.同时,延长再同步周期,降低算法能耗.