0 引言

时钟同步作为无线传感器网络(wireless sensor network, WSN)中的一个关键技术, 是传感器网络中定位测距、网络路由、数据融合、目标跟踪、节点休眠/唤醒和避免通信冲突等大量应用实现的基础^[1-5].

受限于成本, 传感器节点的硬件时钟通常由晶体振荡器提供.由于晶振在制造过程中具有微小差异, 同时在工作时它的频率稳定性会受到环境温度、供电电压和机械振动等因素的影响, 节点的硬件时钟的速率(时钟偏斜)和初始值(时钟偏移)存在一定的差异, 为保证各应用的顺利执行需要反复对WSN中的节点进行时钟同步. WSN中时钟同步主要面对的问题有:节点的计算能力有限, 由电池供电导致节点寿命不同而引起的网络拓扑变化和采用无线通信及载波侦听机制而导致的丢包和时延.因此, 在WSN中, 设计一种计算简单、一次执行即可维持较长时间且同时能在时延和丢包下正常工作的时钟同步算法具有十分重要的意义.

时钟同步作为网络化系统中的一个必要环节, 已有大量的时钟同步协议被提出.最初WSN中的时钟同步协议通常沿用有线网络中的层级式时钟同步方法, 即构建层级式拓扑并依次将所有时钟同步到主时钟上.其中常用的方法有依赖报文传播机制的单向报文传递同步、双向报文交换同步和改良的IEEE 1588标准等^[6].网络中的时延、丢包和信道衰弱等因素在WSN中采用无线通信相比于在有线网络中更为明显^[7].同时, 由于节点电量有限, 网络的拓扑随时可能发生改变.上述因素制约了层级式时钟同步算法的应用, 使得上述算法需要补偿网络中不对称的前向时延和后向时延并花费大量的资源来维持层级式的网络拓扑.因此, 当前大量研究采用分布式时钟同步算法处理WSN中的时钟同步问题^[8-11].其中一部分研究侧重于将时钟同步归结于通信领域的滤波问题, 还有一部分研究只补偿了时钟偏移而没有对不同的节点硬件时钟变化速率进行补偿, 或是在估计时钟参数时引入矩阵求逆等复杂运算而使算法的执行依赖于节点的存储能力和计算能力.

近年来, 一些自动控制领域的学者注意到多智能体状态同步与时钟参数同步间的共同点并引入多智能体一致性的概念处理时钟同步问题^[12-17].多智能体系统的一致性指的是在没有全局控制和通信的情况下, 依靠节点间的局部信息交换实现各智能体状态(如位置、速度、加速度等)趋于一致, 其中一致性算法规定了智能体间信息交换和相互作用的规则.引入一致性的时钟同步算法具有全分布、异步、自适应和易于实施的优点, 能适应传感器网络中由不确定的信号衰弱、节点寿命有限等因素而引起的节点拓扑变化问题.如果忽略硬件时钟中的非线性量, 时钟同步问题可以归结为一阶多智能体一致性问题. Schenato等^[12]提出的平均一致性时钟同步(ATS)协议是一阶一致性时钟同步算法的具体实现, 其中也包含了对一阶一致性时钟同步算法收敛性的完整证明, 该方法依赖MAC层时间戳来确保相邻节点同时读取硬件时钟, 否则节点间的通信时延会影响算法的收敛; He等^[13]由实际应用中只需保证时钟同步而同步后时钟的大小并不重要这一结论, 提出了最大一致性时钟同步(maximum time synchronization, MTS)算法, 使所有时钟收敛到其中的最大者, 并证明了该算法在网络拓扑时变和时不变情况下都能在有限时间内收敛, 但在节点间存在通信时延的情况下, 时钟偏斜所收敛到的最大值是发散的; He等^[15]在后续的研究中通过限制节点间的相互参考次数确保了算法能获得最终结果; Lamonaca等^[18]分析了时钟同步精度与节点间的通信率的关系, 在ATS的基础上增加了事件驱动机制, 权衡了通信速率和同步精度, 在满足需求的同时降低了同步能耗; Brown等^[19]对不同网络拓扑下的一致性时钟同步算法的收敛性进行了分析, 给出了时钟状态单调均方收敛的充要条件; Carli等^[20]在一阶一致性时钟同步算法的基础上进行了扩展, 设计了基于二阶一致性的时钟同步算法, 在牺牲同步速度的前提下提高了算法在存在处理和测量噪声以及时变时钟偏斜情况下的执行性能.研究证明, 二阶一致性时钟同步算法对时钟同步过程中的不确定因素具有更好的鲁棒性^[21].但是对二阶一致性算法的收敛性分析针对的大多是存在特定假设的网络系统, 而且算法的执行也相对复杂.

节点间的时延是限制节点间时钟算法执行的一个关键因素^[22].现有的一致性时钟同步方法在时钟偏斜同步中需要对节点的相对偏斜进行估计, 而引入时延后会影响对相对时钟偏斜的估计. Tian^[23]考虑了这个问题, 在相对偏斜估计部分利用最小二乘法和低通滤波器获得更准确的估计结果, 但是该方法需要节点有较高的运算能力; Luo等^[24]将时钟偏斜、时钟偏移和时延的联合极大似然估计构建为一个线性规划问题来处理时钟同步问题, 但该方法中的时延是指数时延, 不适用存在其他时延的情况.

根据以上分析, 本文在ATS算法的基础上分析随机有界时延条件下的ATS算法的偏斜同步和偏移同步过程.通过修改相对时钟偏斜的估计过程, 保证时钟偏斜几乎必然收敛到一个共同的时钟偏斜上.同时, 在时钟偏移同步过程中对同步过程中的时延项进行分析, 得到偏移同步误差的最大上界和最小下界, 由此说明在随机有界时延情况下, 时钟偏移同步的误差是有界的, 从而确保本文中的一阶一致性时钟同步算法在随机有界时延条件下的正确执行.

1 WSN中时钟同步相关概念

考虑一个具有N个节点的无线传感器网络, 这里使用无向图G={V, E(t)}表示网络的拓扑结构.其中: V={1, 2, ..., N}表示传感器节点的集合; E(t)={(i, j):i, j∈ V}表示在t时刻能进行通信的节点之间的边的集合.节点i的邻节点集合表示为N_i={j∈ V:(i, j)∈ E(t)}.网络中能进行时钟同步的必要条件是网络是连通的, 即网络中至少存在一个节点, 在该节点上能建立与任何一个剩余节点相连的通路.

每个节点上的硬件时钟τ_i(t)定义为

(1)

其中: t表示真实物理世界的时间, α_i表示硬件时钟的偏斜, β_i表示硬件时钟的偏移.由于出厂时时钟元件具有细微差异以及受环境温度和电源电压的影响, 每个节点通常拥有不同的α_i和β_i参数, 通常α_i∈ [1-ρ, 1+ρ], 其中ρ∈ [5×10^-6, 20×10^-6].在实际节点的硬件时钟中, α_i和β_i参数会随时间而发生缓慢的变化, 但只要保证时钟同步过程在较短时间内完成, 上述线性时钟模型就能很好地对节点的硬件时钟进行近似.

由于节点中的部分功能依赖于持续的硬件时钟, 不能直接修改节点的硬件时钟.这里对每个节点构建如下的逻辑时钟进行时钟同步:

(2)

其中: 表示对时钟偏斜的补偿, 表示对时钟偏移的补偿.

由大量通信时延的实验数据以及中心极限定理可知, 这里考虑的通信时延是有界的, 是满足如下正态分布的独立同分布的随机变量:

(3)

本文中时钟同步的目标是考虑一个由无向连通图G={V, E(t)}表示的网络拓扑, 在具有正态通信时延的无线传感器网络中, 假设节点在同步周期内能收到足够数量的邻节点信息, 通过设计一个基于一阶平均一致性的时钟同步算法找到节点i的, 从而使逻辑时钟的时钟偏移和时钟偏斜同步到共识偏斜α和共识偏移β上, 即

(4)

从而使所有节点的逻辑时钟收敛到一个共同的时钟上, 即

(5)

2 带有时延补偿的一致性时钟同步算法

本文中时钟同步算法的基本流程是:在保证相邻节点之间不同时收发信息的前提下, 每个节点依据自身的硬件时钟以周期T向相邻节点广播自身的逻辑时钟偏斜、逻辑时钟偏移和硬件时钟, 在节点i成功接收到相邻节点j的时钟参数后, 分别对时钟偏斜和时钟偏移进行修正, 从而使各个节点的逻辑时钟达到同步.在WSN中, 由于采用无线网络进行通信, 在设计时钟同步算法时, 需要考虑到丢包、时延等问题对节点之间交换时钟参数进行同步这一过程带来的影响.

丢包问题会影响节点接收相邻节点时钟信息的成功率.在本文中, 各节点的时钟同步过程是异步进行的, 具体就单个节点而言, 当该节点成功接收到相邻节点的时钟信息包时才对该节点的时钟偏斜和时钟偏移进行修正.在此过程中, 节点时钟同步的迭代次数是由成功接收到相邻节点的时钟信息包个数决定的.当发生丢包时, 在不存在网关或中介节点且不加入重传机制的前提下, 该节点不会修正自身时钟信息.只要能保证每个节点都能收到一定数量的相邻节点的时钟信息包, 文章中的时钟同步过程就能不受丢包影响正常进行.

文中一致性时钟同步算法的异步性可以使丢包问题仅影响时钟同步的速度而不影响算法的正确执行, 不引入重传机制可以避免由丢包问题对时延问题的讨论带来的影响.在此前提下, 本文侧重于对时延问题的讨论.针对时延问题, 本文分别分析时延对偏斜同步过程和偏移同步过程的影响, 并采取补偿方法确保逻辑时钟收敛到一个共同的时钟上.

2.1 时钟偏斜同步

由于物理真实时钟、硬件时钟偏斜和硬件时钟偏移在实际应用中无法获得, 不能对相邻节点对直接进行如下平均一致性偏斜同步:

(6)

其中ρ_α ∈ (0, 1)表示决定算法收敛速度的参数.

这里定义相对时钟偏移, 并在无时延的情况下使用相邻节点对i和j在通信过程中的两次硬件读数对相对时钟偏斜进行估计, 即

(7)

则偏斜同步过程可以转化为对逻辑时钟偏斜的同步

(8)

在有时延的情况下, 有

(9)

其中: 表示第k次迭代的时间, d_ij(k)表示第k次迭代时节点j到节点i的时延.这里考虑时延d_ij(k)满足如d_ij(k)~N(μ, δ²)所示的正态分布, 则参数θ_ij(k)分布满足θ_ij(k)~.此时式(6)叠加时延后可写为

(10)

令, 相邻矩阵的Laplacian矩阵L=[l_ij]_{n× n}, 其中

其中m(i)表示节点i的邻节点个数.定义状态转换矩阵为

(11)

其中I_n表示矩阵的单位阵.令R(k)=[r_ij]_{n× n}, 其中

由此式(10)的矩阵形式可写为

(12)

此时一阶平均一致性时钟同步算法的收敛性可由如下定理表述.

定理1  考虑如下线性系统:

其中: X(k)∈ Rⁿ, A表示式(11)所示的状态转换矩阵, 此时X(k)会以指数收敛到均值α1上, 即.

证明过程类同于文献[12]中对Theorem 3的证明过程, 这里不详细表述.

为了证明正态分布的时延会使基于一致性的时钟同步的结果发散, 需要首先证明在同步过程的进行中时钟偏斜项的方差存在下界.

定理2  在存在正态分布的有界时延情况下, 在基于一致性的时钟偏斜同步过程中(即式(10)中), 的方差存在下界.

证明  假设, 即时钟偏斜能完全同步, 对式(12)两端同时取极限可得

(13)

其中: 仍表示随机矩阵.由此式(13)可写为

(14)

其中: , R(k)α1中的每个元素表示一个不为0的量.

由此可知, 在存在时延的情况下, 时钟偏斜不能完全同步, 即任何时刻时钟偏斜同步结果方差不为0.假设第k次迭代时X(k)期望为x_k, 方差为d_k且由上述分析可得x_k> 0且d_k> 0, 则计算X(k+1)方差可得

由定理1可知, 无时延情况下一致性算法的执行过程中变量方差是递减的, 因此0 < var(AX(k)) < d_k.而, 设节点间两次同步的间隔最大为T, 已知网络连通时m(i)≥ 1, 则, 即的方差存在下界.

之后分析时延对逻辑时钟的影响.依据式(2), 偏斜同步过程直接影响逻辑时钟模型中的项.这里由定理2可知, 的方差由此得到结论:相邻节点间的通信时延会导致同步后逻辑时钟的方差随时间t的增加而增加, 最终导致逻辑时钟同步结果的发散.由式(8)可以看出, 时延在偏斜同步过程中仅影响相对时钟偏斜估计过程, 造成时延情况下基于一致性的时钟同步过程发散的一个重要原因是相对偏斜估计带来的误差.

为了修正由时延带来的相对偏斜估计的偏差, 这里采用式(15)对相对偏斜估计进行迭代修正.

(15)

下面证明, 经过式(15)的修正后, 相对偏斜估计以概率1收敛到真实的相对偏斜估计上.

定理3  在存在正态分布的时延情况下, 相对偏斜估计α_ij(k)由式(15)获得, 则迭代后每个α_ij(k)依概率1收敛到α_j/α_i.

证明  将式(9)代入(15)中得到

(16)

通过计算式(16)两端期望可以得到E 计算两端方差可以得到, 其中t_l-t_l-1为连续两次接收相邻节点信息的时间间隔, 设其下界为T, 则对方差两端取极限可得根据α_ij(k)的期望和k → ∞时α_ij(k)的方差为0可得α_ij(k)以概率1收敛到α_j/α_i.

由定理2和定理3可知, 随着时间t的增大, 在不进行本文中式(15)的迭代修正时, 存在时延的情况下, 时钟同步误差会随之增大.但与此同时, 节点的迭代次数k也随之增大, 在进行迭代修正后, 相对偏斜估计也随之收敛到真实的相对偏斜上, 消除了时延对时钟偏斜同步过程的影响, 避免了由此导致的时钟同步过程的发散.

2.2 时钟偏移同步

时钟偏移的同步过程如下:

(17)

由于时钟参数β_i无法获得, 考虑在时钟偏斜同步进行一定的迭代后利用下式进行同步:

(18)

在存在时延d_ij(k)~N(μ, δ²)的情况下, 有

(19)

当时钟偏斜同步进行一段时间后, 式(19)中α_j(k会同步到一个常数共识时钟偏斜α上, 因此式(19)中时延前的系数为便于分析可以视为一个常数.

令时延项R(k)=[r₁(k), r₂(k), ..., r_n(k)]^T, 其中将式(17)叠加时延写成矩阵形式可得

(20)

其中: 表示相邻矩阵的Laplacian矩阵.将式(20)展开可得

(21)

为了证明时延不会放大时钟偏移同步结果的方差, 这里证明在存在时延的情况下, 同步结果X(k+1)有界.

定理4  在存在随机有界正态时延的情况下, 由式(20)所示的偏移同步过程完成后, X(k+1)的同步误差有界.

证明  由定理1可知, 式(21)中A^k+1X(0)项的方差在迭代后趋于0, 判断X(k)是否收敛只需判断项是否收敛.考虑其中的通项A^mR(k-m), 其中m为0到k之间的整数, 假设α(k-m)为R(k-m)的均值, 根据定理1, 该项会以指数收敛到α(k-m)1上, 由此可将通项改写为α(k-m)+(r_i(k-m)-α(k-m))e^-λm, 其中r_i(k-m)为R(k-m)中第i项的值, i∈ [1, n], λ为决定收敛速度的一个常数.此时计算通项A^mR(k-m)的方差可得

(22)

令可以看出P(k-m)是一个正的有界常量, 因此令P_max=max(P(k-m)), P_min=min(P(k-m)), 此时时延项的方差为

(23)

对式(23)取极限可得

(24)

因此在偏移同步过程完成后, X(k+1)的同步误差有界.

由定理4可知, 在存在有界时延的情况下, 随着时钟偏斜同步过程的进行, 时钟偏斜方差会趋向于在范围内波动. 是一个与时延相关的量, 在不能得到时延的具体参数时, 任何时钟同步方法都不能达到完全同步.考虑在实际情况下是一个很小的值, 这里采用式(18)进行时钟偏移同步能满足传感器网络中时钟同步时所需的精度.

在不存在时延的情况下, 同步后节点的逻辑时钟会收敛于各节点硬件时钟的均值上.由偏斜同步过程可知, 时延主要影响相对时钟偏斜估计的准确性, 利用本文的方法进行校正后, 相对时钟偏斜依概率1收敛于真实的时钟偏斜上, 因此仅需分析时延对相对时钟偏斜同步的影响.由式(21)可知, 误差项由表示, 其中R(k-m) < 0, 本文中的状态转换矩阵A不会改变该项的正负关系, 因此该项是一个负值, 且随着A的阶次m的上升, 其对应的R(k-m)列向量中每一个元素会收敛于由定理4的证明中所定义的α(k-m).综上, 在存在时延的情况下, 应用本文中的时钟同步算法处理时钟同步问题会使同步后的逻辑时钟小于各节点硬件时钟的均值, 且其差值会随迭代次数的增大而递增.但是, 在实际应用中, 时钟同步主要关注同步后节点的逻辑时钟是否达成一致, 而同步后逻辑时钟的大小并不会影响节点协同执行功能时各自时序的正确性.同时也需要注意到在实际应用中, 硬件时钟偏斜α_i和硬件时钟偏移β_i会随温度、压力等因素的变化而发生改变, 因此在一段时钟间隔后需要重新进行时钟同步, 共同的逻辑时钟的值的减小也会限制在一定的范围内.本文中考虑到其减小值在实际应用中是一个较小的值且不影响同步后各节点间相互协作的功能的实现, 因此不再进行更加深入的分析.

3 仿真结果与分析

本文中的时钟同步算法采用平均一致性算法分别对逻辑时钟参数中的逻辑时钟偏斜与逻辑时钟偏移进行同步, 同时对相对偏斜的估计过程进行修正, 避免了由时延项引起的同步结果发散.之后, 本文分别从时钟偏斜和时钟偏移的角度, 在存在时延的情况下, 将本文中的时钟同步方法与ATS同步方法进行仿真和比较.最后针对逻辑时钟同步的结果, 将本文中的时钟同步方法与当前几种主流的时钟同步方法进行比较.

文中的无线传感器网络由一定区域内随机部署的20个节点组成, 它们的拓扑如图 1所示.

令初始时刻逻辑时钟参数通信间隔T=1 s, 节点的硬件时钟参数α_i在区间[1-5^-6, 1+5^-6]内随机选取, β_i在[-1, 1]间随机选取, 时延项d_ij(k)~N(0.000 25, 0.000 1²).定义偏斜同步误差、偏移同步误差、时钟同步误差为

(25)

时钟同步的具体流程如下.

step 1:为每个节点给定初始条件=0.设置发送自身信息的周期T=1 s, 同时为每个节点分配不同的初始广播时间t_i;

step 2:当时, 节点i将信息发送给它的邻节点;

step 3:当节点i成功收到邻节点的信息后, 记录下收到j节点信息的次数k(j), 自身当前的硬件时间τ_i(t_k^j)以及

step 4:若k(j)>1, 则根据式(15)计算α_ij;

step 5:依据式(8)和(18)对和进行更新;

step 6:存储更新后的.

仿真时选取的时间间隔为0.01, 同时仿真期间节点的硬件时钟偏斜和偏移保持不变.

根据图 2可得, 在存在时延的情况下, 若不修正原有的相对时钟偏斜估计方法, 则由式(25)所定义的偏斜同步误差e_skew会逐渐增大, 最终影响时钟同步过程的收敛.如定理2所示, 存在时延的情况下, 存在下界, 而反应到偏斜同步误差上, 该项需要与时间t相乘, 因而导致偏移同步误差随时间增大.而经过式(15)迭代修正后偏斜同步误差趋于稳定, 说明随着迭代次数的增加, 利用式(15)可以获得相对准确的相对偏斜估计结果.

从图 3可以看出, 在存在有界时延的情况下, 不对相对偏斜估计进行修正会使偏移同步的误差同样无法收敛.这是由于偏移同步误差e_offset中存在项, 在时钟偏移同步时因无法获得硬件时钟偏移和偏斜而使用了偏斜同步后, 因此由时延引起的相对偏斜估计误差同样会影响偏移同步过程的进行.但是, 当对相对偏斜估计进行修正后, 偏移同步误差随着迭代过程的进行会稳定在一个范围内波动, 这和上文定理4中对有界时延下的偏移同步误差的分析, 即偏斜同步的方差在一定迭代后位于范围内的结论一致.这也意味着在有界时延情况下采用基于平均一致性算法的偏移同步算法, 在对相对偏斜估计结果进行修正的前提下, 可以使最终时钟同步的方差稳定在一个与随机时延的大小和方差有关的较小范围内.

图 4是每个节点的逻辑时钟同步误差的仿真.可以看出, 随着时钟同步过程的进行, 节点的逻辑时钟同步误差能很快下降到一个较小的范围内.这其中的误差是相对于节点当前逻辑时钟的均值而言的, 图 4展示了各节点逻辑时钟的差异随时钟同步过程的进行而逐步减小的过程.

图 5将本文的时钟同步方法与基于IEEE 1588的时钟同步方法、文献[12]的平均一致性时钟同步方法和文献[13]的最大一致性时钟同步方法进行了仿真比较.从图 5可以看出, 原有的平均一致性时钟同步算法的同步结果在不能获取精确时间戳且存在时延的情况下, 其时钟同步误差会逐渐增大, 在无法明确安排结束同步的时刻的情况下, 无法维持同步精度.而基于IEEE 1588的时钟同步方法中引入了时延测量机制, 但是在时延随机的前提下, 由于无法保证前向时延与后向时延相等, 无法达到理论上的同步精度. MTS同步方法相比ATS同步方法的优点是其能在有限迭代次数内完成同步, 但当存在时延时, 节点在获取相邻节点时钟信息时会由于时延的影响而无法正确比较时钟偏斜与逻辑时钟值的大小, 具体应用中需要通过限制算法的迭代次数减轻该问题的影响, 这影响了该同步方法在时延情况下的同步速度和同步精度.而文中的时钟同步方法能在存在时延的条件下正常完成同步, 且在完成同步后能维持一定的时钟同步精度, 这验证了文中的时钟同步方法在存在时延的情况下具有更好的性能.

4 结论

本文中同时对时钟偏斜和时钟偏移进行了同步, 在节点硬件时钟参数不发生改变的前提下, 能长时间维持时钟同步.相比仅同步时钟偏移的同步方法, 能有效降低时钟同步频率.针对相对偏斜估计误差与真实时钟相乘而导致时钟同步误差发散的问题, 本文对相对偏斜估计进行了迭代修正, 从而使其几乎必然收敛到真实的相对偏斜估计上.同时, 在偏移同步问题上, 本文通过分析得到由有界时延导致的同步误差随着迭代进行最终趋于一个与时延相关的范围内, 且实际应用中其造成的误差可以忽略.最后通过仿真验证了该时钟同步算法在有界随机时延下可以保证一定的同步精度且误差不会随着迭代进行而放大.在未来的研究中将分析动态的网络拓扑给时钟同步过程带来的影响, 同时根据网络的特点和同步精度需求设计对应的时钟同步算法来满足不同的传感器网络应用的需求.