机坪感知网络的快速收敛平均一致性时间同步算法

陈维兴，刘清涛，孙习习，陈 斌

（中国民航大学电子信息与自动化学院，天津 300300）

（∗通信作者电子邮箱18369657956@163.com）

0 引言

智慧机场（四型机场）是当前民航业发展建设的重要领域，而机坪作为机场运生产运行的重要场所，囊括了大量的航班流、设备流、人员流、数据流等重要机场资源，是智慧机场的基础建设部分，其感知智慧化程度将决定机场在数据层、设备层、系统层、安全层与管理层的智慧化水平和先进程度，也是机场（群）协同运行管控的重要保障。

目前，国内极少有机场完全实现了完整的机坪深度感知，但局部的机坪感知网络（APron Sensor Network，APSN）已实现并形成一定规模。依靠物联网技术的机坪感知系统现有问题主要是由于机坪地域特点、航班流及其衍生流密度影响、节点（智能体）数量及分布、智能体资源和网络自身质量（运营商或自建网的问题）等因素造成的，一定程度上限制了机坪感知系统的发展和建设进程。

机坪感知网络（APSN）架构本质上是异构物联网，分布式、不对称地感知、采集与处理周边环境的信息，针对所提出的问题，本文从时间同步这一底层支撑技术角度展开研究，为APSN 的数据融合、协同监测、节点定位、智能休眠、避免通信冲突等应用实现［1-5］提供基础与前提。收敛速度是时间同步算法的核心着眼点和评价指标，尤其在大规模物联应用中，快速收敛时间同步算法对于网络应用的顺利执行是至关重要的，更快的一致性算法需要更少的同步周期达到网络时间同步，同时能够快速适应网络拓扑结构与时间偏斜的变化。

时间同步问题及其方法广泛应用于诸多物联感知领域，如军事国防、环境监测、医疗健康等分布式网络场景；而本文提出的APSN 场景，具有典型的行业应用特色，同时本质上和其他分布式物联网络有相似之处，故研究结果对其他领域应用同样有参考价值。

当前，在分布物联领域，大量网络时间同步算法已被提出，主要可分为层级式和分布式。层级式时间同步算法如RBS（Reference-Broadcast Synchronization）算法［6］，它需要额外的拓扑管理协议，如生成树协议、簇协议以保证算法有效性，考虑到网络拓扑结构变化会导致算法失效，从而鲁棒性不高。由于层级式算法鲁棒性不高，进一步提出半分布式算法如FTSP（Flooding Time Synchronization Protocol）［7］，此类算法不需要拓扑管理协议，由一个参考节点定期广播其时间在网络中传播，同时其他节点与该节点同步。再进一步，学者将多智能体一致性引入，提出全分布式的时间同步算法，如GTSP（Gradient Time Synchronization Protocol）［8］，ATS（Average TimeSynch）［9］算法，利用节点间的局部信息交换实现全局的状态一致。它能够适应有与拓扑变化问题，鲁棒性高，近几年得到广泛关注。

基于一致性的时间同步算法相比其他算法更具鲁棒性，但由于分布式同步协议主要基于全局节点进行时间扩散和不停地同步迭代，分布式时间同步协议的收敛速度相对于经典的时间同步算法来说比较慢。比较ATS 与FTSP 算法收敛速度，直径为8的线型网络ATS算法需要120个同步周期达到收敛，而FTSP 算法应用到直径为29 的线型网络在不超过20 个同步周期就能达到同步［10］，所以对于分布式的一致性时间同步算法，需要找到一种提高收敛速度的方法。

文献［11］证明，平均一致性算法的收敛速度与网络的代数连通度成正相关，增加代数连通度是提高收敛速度的有效途径。而代数连通度又与网络拓扑的连接稠密程度即连通性有关，可见提高平均一致性算法收敛速度的有效方法是增加网络连通性。增加节点邻居数量是提高连通性的有效方法，文献［12］提出增加功率增加传输半径进而增加邻居数提高连通性方案，但考虑到APSN 大量节点的低成本低功耗特性，特别是机坪中存在着大量边缘区域（如远机位、除冰区等）中的无线感知节点，本身资源有限且距其他节点较远，单纯依靠增加节点功率也难以达到增加邻居数进而改善网络拓扑连接密度，所以很难在物理、功率上改变拓扑。若期望在不改变网络拓扑、不增加节点功率情况下提高网络的连通性，文献［13］提出通过多跳通信形成多跳节点间的虚拟链路，增加节点参考信息从而提高代数连通度。文献［14］利用此理论增加多跳邻居参考信息应用到多智能体系统编队一致性控制当中。文献［15］在GTSP 算法基础上通过增加虚拟链路应用到无线传感器网络时间同步，算法的收敛速度能提升数倍。但GTSP算法是一种简单的一致性时钟同步协议用来补偿时钟偏差，算法未对时钟的偏移量进行补偿，同步周期很短；在时钟延迟上，只是用MAC 层时间戳来消除大多数消息延迟，没有考虑传输延迟。

综合上述研究分析，在考虑传输延迟、网络消耗，且考虑同时补偿时钟偏斜量和偏移量及其延迟［16］的基础上，可通过构建双跳节点间的虚拟链路进而改善收敛性能。基于此思路，本文提出快速收敛的平均一致性时间同步算法（Fast Convergence Average TimeSynch，FCATS），考虑实现ATS 算法的改进优化，在APSN 节点延迟项特别是双跳节点延迟项条件下，通过对相对时钟偏斜的修正补偿以及对逻辑时钟偏斜与偏移的一致性同步迭代使FCATS 算法收敛。此外，本文证明了通过增加虚拟链路可以有效提高代数连通度，进而影响收敛速度。故应用本文提出的算法，可使网络时间同步的收敛速度得到很大改善。

1 图论基础与节点时钟模型

1.1 图论

假设一个由N 个节点组成的机坪感知网络由G=(V，E)表示信息交换网络拓扑关系，其中V={1，2，…，N}为节点集合，边集E ⊆V × V表示N个节点间通信关系。若节点vi可接收到节点vj的信息，则{i，j}∈E；反之{i，j}∉E。令A 为网络的邻接矩阵，节点vi的邻居节点集合表示为Ni={ j|(i，j) ∈E，i ≠j}。D 为网络G 的度矩阵，那么网络的拉普拉斯矩阵L=D -A，拉普拉斯矩阵是代数图论中的有用工具，其特征结构揭示了图的许多重要性质。网络G的拉普拉斯矩阵L 的行和为零，为半正定矩阵，其特征值满足0=λ1≤λ2≤…≤λn，其中，第二小的特征值λ2是网络G的代数连通度。

引理1［11］网络的收敛速度与拉普拉斯矩阵L 的第二小特征值λ2(L)即网络G的代数连通度成正比。

1.2 节点时钟模型

在诸如APSN 的物联体系中，每个网络节点都有自己的本地时钟，称为硬件时钟，硬件时钟是通过该节点所使用的特定频率振荡器脉冲产生的。然而，基于APSN 本身异构物联这一基本属性，每个网络节点振荡器的振荡频率存在差异，同时因硬件寿命、电源电压或环境条件（温度、航空干扰）等不同，每个硬件时钟受不同时钟漂移的影响。由于这种时钟漂移，即使两个节点表现出相同的初始时间，它们也会由于时钟频率的差异在一定时间后呈现不同的时钟值。

令节点vi的硬件时钟值为τi(t)，可以数学地建模如下：

其中：αi为时钟偏斜，相当于时钟速度，理想情况下应为1；βi为时钟偏移。对于APSN 节点，只可以直接获取本地真实时间读数τi(t)，参数αi和βi是不可能得到的，硬件时钟不可能轻易调整，所以需定义逻辑时钟Li(t)也就是同步时钟概念。

节点逻辑时钟Li(t)数学模型为：

大量的实验观测数据［7］表明，节点传输过程中的延迟是满足正态分布的独立同分布随机变量，本文考虑的延迟有界且满足以下正态分布：

2 APSN 场景下快速收敛的平均一致性时间同步算法（FCATS）

2.1 FCATS算法原理

APSN 节点通过硬件时钟周期性地向邻居节点广播信息包即时钟信息，包括硬件时钟、逻辑时钟偏斜及逻辑时钟偏移；在本地节点成功接收到邻居节点的信息包中的时钟参数后，以邻居节点作为参考节点分别对本地时钟偏斜和时钟偏移进行迭代修正，从而使各个节点的逻辑时钟达到同步。FCATS 算法的核心思想为：在没有改变APSN 拓扑结构的基础上，通过在节点的双跳邻居节点与该节点建立虚拟链路，相比ATS算法增加了节点的参考节点数，提高了连通性，进而提高算法收敛速度。FCATS 与ATS 算法的节点vi的参考节点对比如图1所示。

根据机坪网络场景的实际特征，图1 所示APSN 节点，可划分为三类：i类节点表示APSN中区域数据中心节点（位于特种车车载、固定于机坪设施等处），具有丰富的电力、处理和存储硬件资源以及路线驱动的移动性；j类节点为APSN 中数据中继/集中节点，而且具有有限的移动性，能够转发来自k类节点的时钟信息；k 类节点是APSN 中边缘感知节点或其簇头，数量巨大且资源有限，分布式分散部署，感知采集机坪资源数据，由于布置分散，k节点对时间同步实现要求较高（特别是定位、故障、应急信息类感知节点），如果将k 类节点信息发送到双跳邻居i类节点，由于距离较远需要j类节点的中继转发。

图1 两种一致性算法节点vi参考节点对比Fig.1 Reference nodes comparison of node vi between two consensus algorithm

由于自身资源和机坪部署位置，节点j 与i 类的链路往往是比较稳定和容易控制的，而对同步性要求较高的k 类节点，有时与i类节点难以保证链路稳定。

平均一致性算法提高收敛速度的有效方法是增加网络连通性，即提高网络拓扑的连接稠密程度［11］。在不改变网络拓扑，不增加节点功率情况下，本文通过在双跳邻居间建立虚拟链路，增加了节点的参考节点数，提高了网络的连通性从而提高算法收敛速度。

双跳邻居间虚拟链路建立过程，以图1 中的vi与距离两跳的双跳邻居vk建立虚拟链路为例，即节点vk不直接将时钟信息发送给节点vi，而是先传送至节点vj（节点vi的单跳邻居节点），经vj转发至节点vi，由于没有直接发送给vi，相当于在vi与双跳邻居vk间建立虚拟链路。可见，本文提出的虚拟链路，其基本思想是：在不改变原有网络拓扑条件下，针对感知节点的时钟信息，通过j 类节点转发，增加传输跳数使k 类节点时钟信息传送到i 类节点，i 与k 类节点相当于在拓扑上增加了虚拟的链路，即虚拟链路。

对于时间同步过程中节点的参考节点，从图1（a）可以看出，ATS 算法中节点vi只接收并处理其邻居节点vj广播信息包。而在FCATS算法中，从图1（b）可以看出，本文提出节点vi不只接收并处理其邻居节点vj的广播信息包，通过vi与双跳邻居vk虚拟链路的建立，距离节点vi两跳距离的节点vk也通过节点vj转发给节点vi进行处理。因此，FCATS 算法通过节点vi与双跳节点vk的虚拟链路建立，节点vi在同步过程中参考了邻居节点vj与双跳邻居节点vk的时钟信息，网络的连通性得到提高。

在具体的时间同步过程中，如图2 所示：每个节点在第l(l=1，2，…，n)个时钟周期广播信息包，节点同步过程异步接收邻居节点时钟信息，每个节点更新时钟参数的时刻是不同的，所以降低了信息包传送时的节点间时间偏移影响，但传输延迟对同步过程影响较大。当节点vk同步周期被触发，节点vk的广播包括时间戳Tk的信息包MSG1传到邻居节点vj，此时的传输延迟为本算法要求节点信息包不只传输到其邻居节点，还要传到其双跳邻居节点，节点vk信息包传输到双跳邻居节点vi需要节点vj转发，所以节点vj将迅速将包括时间戳Tk与Tj的信息包MSG2传递给节点vi，其中在节点vj中停留的延迟Td忽略不计，此时的传输延迟为因此，节点vi不只收到节点vj的信息包，通过vj的中继转发，相当于在节点vi和vk之间产生了一条虚拟链路收到vk的信息包。

在考虑有界延迟情况下，对于双跳邻居节点，由于需要中间节点中继，所以需要两步才能完成同步包的传输，这里忽略中间节点的处理时间Td，所以其延迟为：

图2 带延迟的信息包传递示意图Fig.2 Schematic diagram of packet delivery with delay

2.2 FCATS算法收敛性分析

在实际应用中，并不能得到APSN 节点自身的时钟偏斜，所以不能直接对相邻的APSN 节点进行偏斜估计，而是通过估计相对时钟偏斜进而对逻辑时钟偏斜估计，这样完成对时钟偏斜的补偿。本文对于逻辑时钟偏斜估计如下：

其中：ρα为收敛梯度系数，αij为APSN 节点vi、vj的相对时钟偏斜。

在无延时的情况下，节点vi，vj的相对时钟偏斜αij：

在存在延时的情况下，节点vi，vj的相对时钟偏斜αij：

其中，对于vi的单跳邻居节点vj：

由于vk是vi的双跳虚拟邻居节点，所以：

由式（5）、（7）可得，节点间延迟主要影响相对时钟偏斜，从而影响逻辑时钟偏斜估计，从而时钟同步发散，故为避免同步过程发散，需要对其相对时钟偏斜补偿，采用加权平均的方式对所有相对时钟偏斜取加权平均：

单跳邻居节点对vi、vj与双跳邻居节点对vi、vk之间相对时钟偏斜需要修正补偿，下面证明经过式（10）的修正补偿迭代，相对时钟偏斜1概率收敛与真实情况。

定理1在存在正态分布的延迟情况下，由式（10）获得相对时钟偏斜估计αij(l)、αik(l)，经修正迭代后1 概率收敛到对于双跳节点对1概率收敛到

证明 对于双跳节点对vi，vk，将式（7）代入式（10）得：

本文对于逻辑时钟偏移估计如下：

其中ρb为收敛梯度系数。由文献［13］可知，在延迟情况下时钟偏移不会放大，其同步结果有界。

2.3 FCATS算法收敛速度的分析

关于代数连通度与收敛速率，网络G的代数连通度λ2(L)影响平均一致性的收敛速度与收敛时间［13］，故提出：

引理2网络节点链路越多，代数连通度越大，收敛速度越快。相对来说，对于稠密的网络，代数连通度大；反之，代数连通度小。

由文献［11］与［13］可知，代数连通度λ2(L)与网络G的拓扑结构的连通性有关系，稠密图的λ2(L)由于网络的连通性的改善相对比稀疏图大。如果对距离双跳以上的APSN 节点之间建立虚拟链路，虽然使网络变得更稠密，但是APSN 的时间同步对能耗的要求，需要尽可能地节约广播包的个数，以及多跳延迟对算法收敛的不确定性影响。所以，在通信拓扑结构不变的情况下，针对提高平均一致性收敛速度的要求，本文提出对APSN 节点周边的双跳邻居节点对之间进行虚拟链路扩充的操作，即使网络变得更稠密，又相对减少了广播包。

在增加虚拟链路前，APSN 节点vi的离散一致性动力学方程如下：

在增加虚拟链路后，APSN 节点vi的离散一致性动力学方程为：

对比式（13）与（14），APSN在双跳邻居节点之间建立虚拟链路后，在进行一致性时间同步迭代计算过程中增加了迭代参考，对于收敛速度的提升证明如下：

综上可知，在通信拓扑结构不变的情况下，时间同步算法通过增加双跳邻居节点之间进行虚拟链路，算法的收敛速度得到提高。

3 仿真实验与分析

本文所提的时间同步算法FCATS，是在增加虚拟链路基础上的平均一致性算法。在考虑传输延迟的情况下，通过补偿相对时钟偏斜，避免了延迟对同步的影响；通过对时钟偏斜和时钟偏移的迭代估计修正，实现网络的时间同步。

提出的FCATS 算法与ATS 算法在收敛性与收敛效果方面进行仿真比较，所用的APSN 是图3 所示的5×4 的网格型网络。为了分析算法适用性，将线型、环型与随机网络拓扑引入分析FCATS算法在收敛速度上提升的效果。

图3 网格型拓扑结构Fig.3 Grid topology

在进行仿真实验时，APSN节点时钟参数如表1所示。

表1 APSN节点时钟参数表Tab.1 APSN node clock parameters

其中，定义逻辑时钟偏斜误差为各节点逻辑时钟偏斜误差的最大值，逻辑时钟误差为各节点逻辑时钟误差的最大值。

FCATS的仿真过程伪代码如下：

算法 FCATS算法。

在存在有界传输延迟的情况下，经过式（10）对相对时钟偏斜的迭代补偿修正，消除了延迟项θij(l)的影响使相对时钟偏斜的得到收敛，又通过式（5）的一致性同步迭代，由图4 可知，FCATS算法的逻辑时钟偏斜误差得到收敛，相较于ATS算法，FCATS 的逻辑时钟偏斜误差提前20 个迭代周期实现收敛。除此之外，从图中可以看出，由于的双跳节点间的虚拟链路增加，节点逻辑时钟偏斜更新时，参考邻居节点数量的增加，APSN 节点逻辑时钟偏斜误差在收敛拐点处，FCATS 在达到峰值时经过几个迭代周期就达到稳定值以下，而ATS 需要数倍时间才能达到稳定值，这说明FCATS 能够迅速使APSN节点逻辑时钟偏斜达到同步值。

图4 两种算法逻辑时钟偏斜误差对比Fig.4 Skew error comparison of logic clocks between two algorithms

由图4 可知，通过式（5）、（12）对逻辑时钟偏斜与偏移的一致性同步迭代，逻辑时钟误差稳定在10-3s内，能满足APSN场景下应用的需要。相较于ATS 算法，由图4 和图5 可知，FCATS 在逻辑时钟误差与逻辑时钟偏斜误差收敛速度上快20 个迭代周期，快50%左右。这是由于FCATS 通过增加APSN的双跳节点间的虚拟链路，APSN的邻居节点增多，网络与拓扑连通性得到改善，由式（15）知代数连通度λ2(L)增大，经计算其从0.382 增长到2.276。这说明在没有改变通信拓扑结构的情况下，FCATS提升了收敛速度。

图5 两种算法的最大逻辑时钟误差对比Fig.5 Maximum logic clock error comparison of two algorithms

时间同步算法的可伸缩性即在不同直径网络拓扑下算法的适用性，是检验算法优越性的重要指标。本文选取不同直径的线型拓扑对收敛性能进行验证，如图6 所示：在不同直径下的线性拓扑，FCATS 的代数连通度总是高于ATS。以上已证明通过在双跳节点间添加虚拟链路，代数连通度增大，网络一致性收敛速度提高。这说明FCATS 在不同直径下的收敛快速性依然适用，算法的可伸缩性强。

图6 网络拓扑直径与代数连通度关系图Fig.6 Relationship between network topology diameter and algebraic connectivity

此外，本文对不同拓扑条件下的网络收敛情况进行了对比研究，分别选取线型、环型、网格型和随机网络拓扑。由图7 可知，在以上几种实际常见网络拓扑中，由于虚拟链路的建立，网络的连通性增强，代数连通度λ2(L)增大，FCATS 始终比ATS 具有更短的收敛时间，而收敛速度分别提升63%、56%、54%和21%。除此之外，由于网络拓扑结构的不同，从图7 中可以看到，由于随机网络拓扑的结构特性，收敛速度快所以速度提升空间小，但通过FCATS，仍能够提升收敛速度。所以，虽然拓扑结构关系对于不同拓扑算法的收敛速度提升效果不同，但FCATS 对于不同网络拓扑时间同步收敛速度都能得到改善。

图7 不同拓扑的收敛速度Fig.7 Convergence speeds of different topologies

4 结语

本文针对APSN 的一致性时间同步算法收敛速度慢问题，提出了一种基于虚拟链路的一致性时间同步算法FCATS，即在网络拓扑结构不变的情况下，在双跳邻居节点间增加虚拟链路。FCATS 算法具有如下特点：1）在存在有界传输延迟下，通过对相对时钟偏斜的修正补偿以及逻辑时钟偏斜与偏移的一致性同步迭代，APSN实现了在双跳邻居节点间增加虚拟链路后算法的时间同步收敛；2）相较于ATS，APSN 在双跳邻居节点间增加虚拟链路，增加了代数连通度，提高了收敛速度；3）算法在不同直径、拓扑条件下依然能够改善算法收敛速度，且本算法在除APSN 外其他场景具有适用性。本算法虽在收敛速度提升上效果明显，但在增加虚拟链路后，APSN 节点传输信息包增多，以后将在进一步减少信息包传输次数基础上加快收敛速度；还将在更多不同的场景中评估所提出的协议，并将其与其他协商一致的时间同步协议进行比较。