频率互异多相位粒度线性脉冲耦合WSN 时间同步模型∗

洪金祥，崔丽珍∗，曹 坚，安竹林

(1.内蒙古科技大学信息工程学院，内蒙古 包头 014010；2.中国科学院计算技术研究所，北京 100190)

无线传感器网络(Wireless Sensor Network，WSN)是物理世界和计算机系统的联络通道，不同传感器节点的时间同步是WSN 应用的先决条件。如果传感器节点的时钟未正确同步，信息在时间一致性上将无法准确传递[1－3]。时间同步可以为WSN提供公共参考时间，保证信息传输的一致性，是分布式系统实现数据融合，降低能量消耗和传感器节点定位等方面的有效保证。由于传感器节点通常使用低成本的晶体振荡器为传感器进行时钟计时，容易受到温度、振荡器老化、电池电量及压力等因素的影响[4－5]，导致时间同步的准确性和稳定性受到影响。即使在某一时刻这些节点实现同步，在运行过程中，还会再次发生失步现象。文献[6]考虑了石英晶体的缺陷，基于控制理论原理对低频时钟晶体引起的时钟漂移提出了能够同步WSN 中多节点的时钟同步方案。随着研究的深入，基于主从关系同步的传统同步协议[7－11]使用时钟补偿机制来减少晶体振荡器误差，但在多跳大规模网络同步过程中伴随着同步误差的积累，要求交换许多数据包，需要第三方中心节点的存在，并且需要路由协议的维护，导致大规模网络的应用需求无法满足。

受生物学的启发，基于萤火虫同步闪烁现象的脉冲耦合振荡器(Pulse-Coupled Oscillators，PCOs)的理论是适合WSN 的自组织同步的有效解决方案[12－14]。PCOs 可以通过离散时刻的脉冲耦合而不是数据包交换方式获得具有成本效益的物理层同步，避免了同步过程中同步误差积累的问题，并且不需要选择中心节点(节点即为振荡器)来同步网络。文献[15]针对时钟漂移等问题提出基于时间和相位离散的多相位粒度萤火虫同步算法。文献[16]提出非漏电脉冲耦合振荡器同步模型，将线性状态变化函数匹配于WSN 的计算能力，该模型同M＆S模型[17]一样均假设所有振荡器的频率相同，但是对于WSN 来说，由于采用廉价的晶振，其频率的一致性难以保证。Peskin[18]对频率的差异而进行猜想:“即使每个振荡器并不相同，系统最终也会达到同步”。文献[19]认为时钟频率受振荡器温度漂移的影响变化缓慢，漂移时钟的频率可视为恒定值，验证了传感器节点频率互异的PCOs 同步。文献[20]受萤火虫同步启发，结合主从节点时间信息交换的同步方式，通过带有时间戳的脉冲传输来确定偏移量和校正本地漂移时钟，但以上基于萤火虫同步的WSN 时间同步研究并没有考虑晶振频率的变化。文献[21]利用载波频率偏移来估计两个节点之间的时钟偏移，使用低成本振荡器时具有显着的可靠性，但目前针对频率差异和多相位离散的线性PCOs同步的研究鲜有涉及。

针对节点间存在晶振频率偏差导致时间漂移的时间去同步问题，本文提出一种频率互异的多相位粒度线性脉冲耦合WSN 时间同步模型。有别于基于主从关系的报文传输时间同步协议，采用了基于萤火虫同步机制的脉冲传输的多相位离散耦合同步方式，在建模和同步过程中考虑网络中每个节点时钟的频率差异，以接近WSN 实际应用的情况，验证了频率不一致的情况下系统能够实现稳定同步，并且适合低成本传感器节点的计算能力，有效提高了同步收敛速率。

1 相关工作与模型描述

1.1 相关工作

由惠更斯发现摆钟的同步摆动，以及东南亚萤火虫同步闪烁等自然界存在的互同步现象，Peskin把互同步系统通过耦合行为建模成脉冲耦合振荡器模型，并且猜测振荡器结构不同和任意初始状态下的振荡器系统能够实现同步。在此基础之上，Mirollo 和Strogatz 提出一种更加一般化的脉冲耦合振荡器模型，也称为M＆S 模型，从理论上证明了此模型下的脉冲耦合多振荡器系统在几乎所有的初始情况下都能够达到同步。传统的报文同步方式是通过交换含有时间戳的报文信息而实现同步，通过报文含有的时间戳来计算时钟偏移，从而对本地时钟进行有效调整。但容易受到报文传输延迟的影响。与此同时，如果不对称的报文进行双向传输，则会影响到该算法的同步精度。萤火虫同步技术是WSN时间同步的一种新型时间同步机制，基于萤火虫同步的无线传感器网络时间同步模型中，不同传感器节点之间通过脉冲耦合的方式进行状态的改变。与传统的报文同步方式相比，它们以发射脉冲信号的信息交换方式实现同步，具有较好的可扩展性和稳定性，适合应用于大规模网络和复杂环境的WSN时间同步中。很好地避免了报文同步方式在时间同步过程中存在随着跳距的增加出现同步误差积累而影响同步精度的问题。

在无线传感器网络中，传感器节点间的协同工作建立在同步性的基础之上，而WSN 的时间同步所体现的同步性质与萤火虫同步现象类似，因此耦合的振荡器被建模为“集成－激发”的振荡器网络。非漏电脉冲耦合振荡器同步模型同M＆S 模型均理想化假设振荡器的频率相同，将每个传感器节点看作单个的脉冲耦合振荡器，通过脉冲传输而不是数据包交换方式获得具有成本效益的物理层同步，引入相位ϕ作为中间变量，表示振荡器的瞬时状态，并且建立振荡器线性的动态数学模型，将每个传感器节点看作为单个的脉冲振荡器，可以周期性输出脉冲信号作用在其他振荡器上，即式(1)的线性状态函数:

其他节点受到激发节点脉冲耦合的状态变化为:

非漏电脉冲耦合振荡器同步模型忽略了振荡器之间可能存在的频率差异，节点在随机初始状态开始同步演进，在接收到脉冲耦合时，相位和状态同时提升耦合强度ε。假如耦合后的状态大于上阈值1，那么该节点的状态在激发瞬间归零并重新开始同步演进，用激发映射和回归映射描述了振荡器之间的激发与耦合。

1.2 模型描述

脉冲耦合振荡器同步模型能够实现大规模传感器网络的稳定同步，而传感器节点晶振频率的不一致性是大规模传感器网络失步的主要原因之一。对于频率互异对同步的影响，本文基于萤火虫同步机制，考虑节点之间的频率差异，假设所有节点的频率为闭区间上独立同分布的随机变量，并且具有连续的概率密度函数，提出频率互异的多相位粒度线性脉冲耦合WSN 时间同步模型。

频率互异的多相位粒度线性脉冲耦合同步模型中每个振荡器的线性状态变化函数如式(3)所示，式中f为振荡器的晶振频率:

模型的动态方程如式(4)所示:

式中:xi(t)为节点i在时刻t的状态，xj(t＋)为节点j在i激发后瞬间t＋时刻的状态，fi和fj分别为节点i和j的晶振频率，εi为节点i所发射脉冲信号的耦合强度，该动态方程表示节点j在节点i激发瞬间的状态变化。

频率互异的多相位粒度线性脉冲耦合同步模型的同步示意如图1 所示，频率互异的两个节点i和j的振荡频率分别为fi和fj。在同步演进过程中，一个节点会受到另一个处于激发状态节点的脉冲信号的激励耦合改变自身的状态，同时振荡频率通过脉冲信号进行交互，高振荡频率节点对低振荡频率节点发出脉冲耦合激励，使得低振荡频率节点的自身状态和振荡器频率都发生变化。当节点的频率在激励耦合后达到一致，那么在下一次同步演进过程中只改变节点状态，随着同步过程的演进，两个节点的状态差异不断减小，频率和状态逐渐达到一致。

图1 模型同步示意图

当两个振荡器同步之后，会互相吸收成为一个同步演化的振荡器组，该振荡器组具有更大的耦合强度，因此会继续吸收其他的振荡器并导致一种正反馈作用。在多振荡器系统的演化过程中，可能会同时有多个这样的振荡器组共存，而随着吸收过程的继续，振荡器组会越来越少，最后所有的振荡器会组成一个大的振荡器组，这时整个系统达到同步状态。

1.3 模型同步方式

本文同步模型采用去中心化的同步方式，避免WSN 同步过程中同步误差积累的现象，同时克服了传统的发送具有时间戳的报文信息的同步算法过分依赖中心节点和计算量过大的问题，具体同步过程如下:

步骤1 各个节点同步在随机状态下进行同步演进，未激发节点接收来自处于激发状态节点的脉冲激励信号，并建立“集成－激发”的振荡器网络。在高振荡频率的节点率先到达激发状态时，由于脉冲信号产生的耦合强度的作用，低振荡频率且未激发节点根据线性状态变化函数改变自身状态和振荡频率。若在这个过程中，存在某一节点立刻与激发节点的状态和频率一致，那么该两个节点实现同步，形成同步组，否则继续进行同步演进过程。

步骤2 在接收脉冲信号的未激发节点首次到达激发状态时，其他低振荡频率且未激发节点接收该节点的脉冲信号，改变自身状态和频率且计算当前相位和状态值，该状态为激发映射(Firing Map)。激发节点的状态在激发瞬间下跳到0，继续进行同步演进。

步骤3 相关节点经过步骤2 后，节点振荡频率与发出脉冲信号的激发节点的频率实现一致。那么，当首次达到激发状态的节点再次激发时，仍未激发的节点接收脉冲信号后改变自身状态，计算当前相位和自身状态，该状态为回归映射(Return Map)。激发节点的状态在激发瞬间下跳到0，继续进行同步演进。

步骤4 检查所有节点的状态是否调整，并且返回同一节点的回归映射与初始状态的差值，得到同步条件后。若差值为0 则意味系统达到同步状态，否则在同步条件的保持下，各个节点继续进行同步演进过程直到实现同步状态。

在系统同步演进过程中，激发映射和回归映射是研究脉冲耦合振荡器系统演化过程的有效工具。在某振荡器激发的时候获取系统的快照，然后分析这些快照可以对振荡器之间的状态关系进行分析，从而推导出同步条件。

引理1对于两个振荡器A、B，假设当前时刻为A某次激发之后，此时B的相位为ϕ，那么B关于A的回归映射RB｜A(ϕ)被定义为B在A下次激发之后的相位，系统由初始状态(ϕA，ϕB)＝(0，ϕ)转换为(ϕA，ϕB)＝(0，RB｜A(ϕ))，同步条件为RB｜A(ϕ)≠ϕ。

引理2对于两个振荡器A、B，假设当前时刻为A某次激发之后，此时B的相位为ϕ，那么A关于B的激发映射hA｜B(ϕ)被定义为A在B下次激发之后的相位。

由于多相位粒度的线性脉冲耦合振荡器同步模型的状态变化是离散型的，根据离散相位空间的变化而发生改变。因此，为了有效分析振荡器系统的同步演进过程，和表征节点受到脉冲耦合后其自身状态和频率的变化情况，对频率不一致的两个节点A和B组成的系统存在的两种初始状态，分别进行同步过程跟踪和同步条件分析，确保振荡器系统的初始状态具有完备性的同时可得到有效的回归映射。

初始状态1 假设某一时刻节点A处于激发状态，且fA>fB，此时A的相位ϕA＝1→0，B的相位ϕB＝ϕ0，即节点A在激发状态瞬间xA＝0 时，节点B为xB＝fBϕ0的初始状态。

初始状态2 假设某一时刻节点B处于激发状态，且fA>fB，此时B的相位ϕB＝1→0，A的相位ϕA＝ϕ0，即节点B在激发状态瞬间xB＝0 时，节点A为xA＝fAϕ0的初始状态。

根据两种初始状态分别对两个振荡器和多振荡器系统进行同步过程跟踪分析。

2 两个振荡器同步

在振荡器系统中，两个节点A和B组成最简单的振荡器系统同步模型，通过对两个振荡器在随机初始状态下的同步过程的跟踪分析，得到两个频率互异节点之间的映射关系，从而判断出该文模型中两个振荡器的同步保持条件和瞬时同步条件。

2.1 同步过程跟踪

对于频率和状态不一致的两个振荡器A和B，假设A在当前时刻到达激发状态，此刻B处于同步演进状态，即初始状态1 的情况。A率先从0 达到激发状态时，此时相位ϕA，B在相位ϕ0＋ϕA接收脉冲信号的激励耦合，改变自身状态和频率。随后B在相位ϕ1时达到激发状态，节点A接收到B激发瞬间的脉冲激励，当节点A再次到达激发状态时，B在相位ϕ2处接收脉冲信号，从而提升自身状态，减少两个节点之间的状态差，两个振荡器的同步过程如图2 所示。

图2 初始状态1 的同步过程(两振荡器)

由式(3)可得A激发状态的相位ϕA，即A从0到激发状态经过相位:

节点B从接收A脉冲信号首次到达到激发状态经过相位:

节点A从接收B脉冲信号再次到达激发状态经过相位:

具体同步过程两个节点A和B的状态变化如表1 所示。

表1 初始状态1 开始的状态变化(两振荡器)

假设B在当前时刻到达激发状态，此刻A处于同步演进状态，即初始状态2 的情况，由于fA>fB，节点A率先从ϕ0达到激发状态时，此时相位为ϕA，B在相位ϕA－ϕ0接收脉冲信号的激励耦合，改变自身状态和频率。随后B在相位ϕ1时达到激发状态，节点A接收到B激发瞬间的脉冲激励，当节点A再次到达激发状态时，B在相位ϕ2处接收脉冲信号，从而提升自身状态，两个振荡器的同步过程如图3所示。

图3 初始状态2 的同步过程(两振荡器)

具体同步过程中两个节点A和B的状态变化如表2 所示。

表2 初始状态2 开始的状态变化(两振荡器)

由式(3)可得A从相位ϕ0开始，到激发状态时的相位ϕA:

节点B接收节点A脉冲信号后首次到达到激发状态经过相位ϕ1－(ϕA－ϕ0):

节点A接收节点B脉冲信号后再次到达激发状态经过相位:

2.2 同步条件

由于节点的晶振频率存在差异，即使在某一时刻实现同步状态，也会逐渐再次失步，因此瞬时同步并不能代表振荡器系统实现同步。当耦合振荡器须满足瞬时同步条件和同步保持条件，才意味着能够达到同步状态并保持同步。

根据表1 和表2 分别可得初始状态1 和初始状态2 同步过程的激发映射和回归映射:

由引理1 可得瞬时同步条件:

如果节点A在达到激发状态时，耦合强度能够瞬间使B的状态提升到激发状态，那么A和B之间的同步被保持，推导出同步保持条件:

当频率互异的两个节点实现同步状态后，会吸收成为一个振荡器同步组。

3 多振荡器系统同步

3.1 同步过程跟踪

多振荡器系统的同步过程较为复杂，与两个振荡器同步区别在于频率互异的两个节点或振荡器同步组在同步演进过程中，会接收到其他激发状态振荡器的脉冲信号从而影响同步状态。

对于多振荡器系统中频率和状态不一致的两个振荡器i和j，系统中其他激发振荡器的集合表示为Ωi，fk为集合中最大的振荡频率，ϕk为该最大振荡频率的振荡器瞬时相位。在初始状态1 的情况时，i率先从0 到达激发状态，假设此过程中i在ϕ0＋ϕk处，j接收到系统中其他激发振荡器的脉冲信号，随后i在ϕi激发，j在ϕ0＋ϕi接收i的脉冲信号且在ϕ1处达到激发状态。当i再次激发时，j在ϕ2处接收脉冲信号，多振荡器系统中两个振荡器的同步过程如图4 所示。

图4 初始状态1 的同步过程(两振荡器)

多振荡器系统中两个节点i和j具有一组完备的回归映射的同步状态变化如表3 所示。

表3 初始状态1 开始的状态变化(两振荡器)

其中各个节点到达激发状态的相位变化分别如下:

对于初始状态2 的情况，j处于激发状态，相位为0，i的相位为ϕ0，同样假设在ϕk处节点i接收到系统中其他激发振荡器的脉冲信号，此刻节点j的相位为ϕk－ϕ0。由于fi>fj，i在ϕi处率先到达激发状态，j在ϕi－ϕ0处接收到该脉冲信号，随后在ϕ1处激发。当i再次激发时，j在ϕ2处接收脉冲信号，多振荡器系统中两个振荡器的同步过程如图5 所示。

图5 初始状态2 的同步过程(两振荡器)

多振荡器系统两个节点i和j的状态变化如表4所示。

表4 初始状态2 开始的状态变化(两振荡器)

各个节点到达激发状态的相位变化分别如下:

3.2 同步条件

根据表3 和表4 可得初始状态1 和初始状态2同步过程的激发映射和回归映射分别为:

可得瞬时同步条件:

频率互异多振荡器系统中的两个节点在同步条件的保持下，系统逐渐形成多个同步振荡器组，各个节点的频率和状态逐渐趋于一致，随着同步过程的演进，最终多振荡器系统实现同步状态。

4 实验仿真与结果分析

本节对上文介绍的频率互异的多相位粒度线性脉冲耦合同步模型进行仿真验证，分析模型中的耦合强度对同步的影响，同时与文献[19]中未考虑节点频率不一致的传统非漏电脉冲耦合振荡器WSN同步模型进行对比，以证明该模型在同步稳定性和收敛速度的有效提升。

4.1 耦合强度参数对模型同步的影响分析

耦合强度参数包括耦合强度数值比率ε-ratio和耦合强度基数ε-base。图6 所示为耦合强度数值比率为0.05、0.2 和耦合强度基数为0.005，模型网络节点数量为10～200 时的同步结果，由图6 可知，两组数值在不同节点数量的同步周期趋于一致，并且随着节点数量的不断增加，同步周期逐渐减少，表明耦合强度数比值率对模型同步结果的影响非常小。

图6 耦合强度速数值比对模型同步的影响

图7 所示为30 个振荡器在耦合强度数值比率为0.1，耦合强度基数分别为0.005、0.015、0.025 和0.035 时多次同步仿真的同步周期，从图中可以看出耦合强度基数对模型同步周期影响较大，由于仿真实验的初始状态是随机的，图中同一耦合强度基数网络的同步周期也略有差异，并且同步周期随着耦合强度的增大而减小，表明耦合强度越大，模型的同步速率越快。

图7 耦合强度基数对模型同步的影响

4.2 模型同步效果分析

4.2.1 模型同步稳定性

图8 和图9rnfi 分别o 小规模和较大规模网络的同步情况。由图8 中可看出传感器节点数为20时频率互异多相位粒度线性脉冲耦合同步模型在200 次同步中，同步周期低于未考虑频率差异的非漏电脉冲耦合振荡器模型，并且同步所需周期的期望和方差小于对比模型，该模型在能够实现同步的同时表现出较好的同步稳定性。

图9 节点数100 的较大规模网络同步周期

图9 为传感器节点数为100 时网络在200 次同步实验的同步周期变化情况，从图中可以看出该模型在较大规模网络中的同步周期低于对比模型，并且网络规模越大所需同步周期越少。可见该模型更加适用于传感器节点数量较多的网络同步，同步周期变化波动较小，整体同步效果符合预期分析。

4.2.2 模型同步收敛速度

由于无线传感器网络低成本和低功耗的特点使得节点的计算能力有限，因此同步速度是判断脉冲耦合振荡器同步模型适用性的关键因素。图10 所示为模型同步收敛速度情况，随着网络节点数量不断增加，网络中“集成－激发”事件越容易出现，模型的同步所需周期逐渐减小，加快了同步收敛速度。

图10 节点数100 的较大规模网络同步情况

从图10 中可以看出，频率互异多相位粒度线性脉冲耦合同步模型的同步收敛与非漏电脉冲耦合振荡器同步模型同步收敛变化趋势相近，但明显在同一节点数量的同步周期更小，表示该模型的同步收敛速度有一定的提升。

5 结论

本文研究了节点晶振频率差异导致的无线传感器网络失步问题，基于去中心化同步方式的萤火虫同步机制，提出一种频率互异多相位粒度线性脉冲耦合WSN 时间同步模型。通过理论分析和仿真实验表明，该模型在频率不一致的无线传感器网络中能够实现稳定的时间同步，对网络中节点数目变化具有鲁棒性，同步收敛速度进一步提高，有效解决了无线传感器网络在运行过程中节点晶振频率差异导致的失步问题。