0 引言

随着多机器人协同过程中多机器人组成的网络规模的不断扩大，网络拓扑关系越来越复杂，传统常用的集中式无线网络同步技术逐渐失去优势，人们急需研究出一种分布式时间同步算法^[1]。大自然给了人们研发分布式同步算法的灵感^[2-4]，其中典型的例子为东南亚萤火虫同步闪烁现象。MIROLLO R E和STROGATZ S H以前人的研究为基础^[5]，建立了萤火虫同步模型的动力学M&S PCO（M&S Pulse Couple Oscillator，M&S PCO）模型，证明其在全链接无延时耦合的多振荡器网络中可收敛^[6]。利用萤火虫同步算法可以将同步过程从网络拓扑结构中独立出来，使其适应大规模复杂拓扑结构的网络，且同步的鲁棒性增强^[7]。该类算法已在超帧结构同步和网络休眠中得到应用^[8]。

然而基于萤火虫的时间同步算法虽然一定程度上解决了大规模网络时间同步问题，但有两个问题亟待解决^[1]：一是目前大部分使用的并发脉冲耦合机制在全网接近同步时，同步报文并发冲突使得CSMA/CA达到最差的性能，容易造成网络拥堵和不可预见的延时，对算法稳定性造成影响；二是WSN的硬件不能满足萤火虫同步算法的大量浮点运算。因此，为弥补目前萤火虫同步网络拥堵和不便实现等问题，有些学者已经在这个方面做出了努力^[8-9]。然而这些研究仅在一定程度上起到缓解作用，在高密度网络中，集中发送同步报文仍会导致严重的信道冲突。

为了最大程度地解决密集节点集的发送同步报文拥堵问题，本文探索一种萤火虫时间同步算法的拥堵避免机制，提出基于随机脉冲耦合机制的无线传感器网络分布式协同时间同步方法，通过随机脉冲耦合，尽可能避免网络拥堵，充分利用网络带宽资源，增加了萤火虫同步算法的实用性。

1 同步数学模型建立

1.1 M&S PCO模型

针对初始不同步的系统，Charles将每个网络节点看作一个RC振荡器，建立了单个振荡器的两种基本数学模型^[5]：一种是自由运行模型，另一种是与其他节点耦合模型。节点自由运行状态下，振荡器的模型为：

式中，x表示进行了归一化后的单个振荡器电压，S₀代表充电的速度，i代表电阻漏电流因子。当电容电压达到最大值时，即x=1，振荡器迅速放电，电压突变为0。此时，振动器与其他振荡器进行脉冲耦合，将其他振荡器的电压提升一个耦合系数ε，即第二种数学模型：

MIROLLO R E与STROGATZ S H在Charles模型的基础上引入了节点的动力学模型，建立振荡器M&S PCO模型^[6]：

1.2 简化相位模型

上文介绍的M&S PCO为萤火虫同步提供了理论分析的基础。但是在以MCU为运算核心的无线传感器网络节点上，硬件运算资源有限，在做相位映射到状态值时，需进行大量的浮点运算会占据硬件资源，影响网络的正常功能，因此本文参考M&S PCO模型中相位状态映射的特征，对M&S PCO模型进行简化，并尽量避免复杂的浮点运算。

式中μ为相位提升量；以φ_j(t)为例，其表示节点i在t时刻的相位值。即当节点接收到有效触发信号后，相位提升c₁φ_j(t)+c₂并于相位阈值进行比较，如果达到阈值则触发。如此，便可通过相位的处理代替对节点状态值的处理，使用简单的运算代替复杂的相位状态映射，达到简化运算的目的。

2 拥堵避免机制

在传统的M&S PCO模型中，节点均在触发瞬间进行同步耦合。在无线传感器网络中，脉冲耦合是通过节点发出同步报文实现，而这将导致节点集接近同步状态时，节点的同步报文交换过于集中。为此，本节介绍一种拥堵避免机制，通过随机脉冲耦合(Stochastic Pulse Couple Oscillator，SPCO)将同步报文分散到整个相位增长的过程中，以缓解报文交换过于集中带来的信道冲突。

2.1 随机脉冲耦合

在SPCO中，节点在网络中的同步和M&S PCO主要不同在于:将触发和发出同步报文进行脉冲耦合的过程在时间轴上分离。触发和同步报文耦合两个任务相互独立。节点在运行过程中以大于一个周期的随机时间间隔发送出带有自身相位信息的同步报文。发送同步报文的时刻是随机的而非在节点相位达到阈值时，并且在同步报文中需包含本节点在发送瞬间的相位信息而非单纯的脉冲信息。

在SPCO模型中，当节点收到同步报文时，从中提取出相位信息，经过与自身相位的比对判断过滤出有效相位信息，并按照简化模型计算相位增加量。并将所得相位增加量加至相位中，即可对相位产生耦合作用。

为了方便说明，假设A、B两个节点进行随机脉冲耦合，节点B在随机相位β处发出了一个同步报文，节点A处理算法的具体过程如下：

(1)当节点A收到节点B同步报文后，记下收到瞬间本地的相位α和所收协议的前导码延时相位d，解析同步报文内的数据，得到节点B的发送报文时的相位β。

(2)进行同步报文过滤，过滤规则为：当且仅当β≥α-d+r且β≤1+α-d-r时，即节点A和节点B的相位误差在r范围之外，且在一个周期内节点B先于节点A触发，则接收的数据包有效。其中r的作用类似于M&S PCO模型中的不应期(Refractory Period)^[10]，故亦称其为不应期长度。

(3)进行有效报文处理。处理的核心思想是模拟节点B在发送同步报文的周期内触发，将该脉冲耦合对节点A相位的影响提前至收到同步报文的时刻。随着时间推进，由于β≥α-d+r，节点B的相位要超前于节点A，节点B会先与节点A到达阈值。当节点B达到相位阈值时，节点A的相位值为：

式中μ为调整步长；r为不应期长度；d为前导码延时相位；α、β为步骤(1)中记录的相位值；c₁、c₂为耦合常数。该次同步报文最终的结果是节点A的相位提高μ，一般情况下，为了避免节点集在同步接近收敛时相位抖动，需满足μ<1、c₂应为一个较小常量。

综上可知，该次触发过程的动力学模型总结为：

式中μ为调整步长；r为不应期长度；d为前导码延时相位；α、β为步骤(1)中记录的相位值；以φ_A(t)为例，其表示节点A在t时刻的相位值。

2.2 逃逸不稳定平衡区间

需要额外注意的是，由于当节点相差相位阈值的一半时，两个节点的位置互换并不影响相位调整的调整步长，这就导致任意节点所发同步报文对另外一个节点的相位增长影响近乎相同，两节点保持相位差相对不变。为了避免这种不稳定平衡现象，需要在相位阈值的一半处设置一个逃逸区间[0.5-δ，0.5]，当节点相位差落入这个区间后，调整步长迅速增大至逃逸速度U，且U>δ，使其逃离该不稳定平衡区域，达到加速同步的目的。

3 仿真与结果分析

在本节中，针对第2节提出的SPCO同步机制进行仿真验证。为了方便对比，将仿真实验分为两组，分别使用传统的M&S PCO 机制和本文中介绍的SPCO机制进行实验。通过记录相位和同步报文并发情况，从同步收敛精度、同步所需时间、同步报文并发情况三方面分析SPCO机制对同步过程的影响。

3.1 仿真参数设置

为了增强对比性，两组仿真实验中存在一些共同的仿真参数。在仿真实验中，20个节点被布置在一个全链接网络中，仿真时间为400 s。网络中的每个节点与其他19个节点向链接。节点的初始相位为随机分布于0~1之间。节点的相位阈值为1，相位周期为1 s。节点的不应期长度设为0.1，节点相位同步窗体大小为0.001（即相位误差在0.001之内便认为节点同步）。为满足μ<1=0.005，c₂=0.005，SPCO中不稳定平衡区间设为[0.4，0.5]，逃逸速度为0.3。

为了保证仿真模型的真实性，将每个节点的晶振速度增加50PPM的跳动，并在消息交换过程中设置了10~100 μs的随机延时。而为了比较SPCO对同步时间和精度的影响，暂不考虑信道冲突对同步报文传输的影响。

3.2 仿真结果及分析

这两组试验仿真前后网络节点相位变化如图1。从图中可以看出，节点集的初始相位是分散的，经过SPCO和M&S PCO同步过程，在仿真结束后节点集相位均收敛。从最后的同步效果来看，基于SPCO的冲突避让机制并没有影响同步算法的稳定性和精度。

为统计网络中同步报文的并发情况，以0.000 5 s为单位时间区间，统计以不同中心时刻的单位时间区间中，同步报文的并发数目，以检测通信的拥堵情况，同时统计此时的相位误差以方便寻找其中的规律。

图2表示M&S PCO同步过程中的相位误差和报文并发数随时间的变化。从图中可看出随着同步过程的进行，报文并发数随着相位误差的减少明显增多。在350 s后，节点集达到同步，在单位时间区间内，节点并发数甚至达到20。较大的并发数会造成无线信道的严重堵塞，不利于该时刻数据的传输稳定性和即时性。

图3表示M&S PCO同步过程中的相位误差和报文并发数随时间的变化。从图中可以看出，网络相位在30 s时便达到收敛，并且并发报文数并没有随相位误差的减小而增加。整个节点集的同步报文发送均匀的分布在整个时间轴内，并不受相位误差的影响。

对比图2和图3可知，SPCO冲突避免机制在不影响同步精度的前提下，不仅可缩短同步时间，并且在时间轴上极大缓解了并发同步报文带来的信道拥堵。

4 结论

本文提出了一种基于随机脉冲耦合同步的萤火虫同步信道拥堵避免机制，实现多机器人分布式时间同步。文章首先简化传统萤火虫同步的数学模型，给出信道拥堵避免机制，然后通过仿真实验，进行对比验证。试验证明了相对于传统M&S PCO，SPCO同步机制可在不影响同步精度的条件下，加速同步进程，并且在很大程度上缓解集中触发耦合的信道拥堵，验证了拥堵避免机制的可行性。

随机脉冲耦合同步机制使用简化相位模型，便于在单片机中实现。其触发信息的发射可以更加充分的利用带宽，甚至和节点的常规数据包融合。算法本身对丢包不敏感，可以适应无线环境较为恶劣的条件。

参考文献

[1] 徐朝农，徐勇军，李晓维.无线传感器网络时间同步新技术[J].计算机研究与发展，2008，45(1)：138-145.

[2] ALLARD H A.Synchronous flashing of fireflies[J].Science(New York，NY)，1935，82(2120)：151-152.

[3] BUSCH N E，VINNICHE N K，WATERMAN A T，et al.Waves and turbulence[J].Radio Science，1969，4(12)：1377-1379.

[4] GLASS L，MACKEY M C.From clocks to chaos-the rhythms of life[J].Nature，1988，336(6195)：119.

[5] PESKIN C S.Mathematical aspects of heart physiology[M].New York：Courant Institute of Mathematical Sciences，New York University，1975.

[6] MIROLLO R E，STROGATZ S H.Synchronization of pulse-coupled biological oscillators[J].SIAM J Appl.Math.，1990，50(6)：1645-1662.

[7] BOJIC I，PODOBNIK V，LJUBI I，et al.A self-optimizing mobile network：Auto-tuning the network with firefly-synchronized agents[J].Inform Sciences，2012，182(1)：77-92.

[8] TYRRELL A，AUER G，BETTSTETTER C.Emergent slot synchronization in wireless networks[J].IEEE T.Mobile Comput.，2010，9(5)：719-932.

[9] LEIDENFROST R，ELMENREICH W.Firefly clock synchronization in an 802.15.4 wireless network[J].EURASIP Journal on Embedded Systems，2009(1)：1-17.

[10] HONG Y W，SCAGLIONE A.A scalable synchronization protocol for large scale sensor networks and its applications[J].IEEE J.Sel.Area.Comm.，2005，23(5)：1085-1099.

作者信息:

郝创博，宋 萍

（北京理工大学 机电学院，北京100081）