陳維興，劉清濤，孫習習，陳 斌

（中國民航大學電子信息與自動化學院，天津 300300）

（?通信作者電子郵箱18369657956@163.com）

0 引言

智慧機場（四型機場）是當前民航業(yè)發(fā)展建設的重要領域，而機坪作為機場運生產運行的重要場所，囊括了大量的航班流、設備流、人員流、數據流等重要機場資源，是智慧機場的基礎建設部分，其感知智慧化程度將決定機場在數據層、設備層、系統層、安全層與管理層的智慧化水平和先進程度，也是機場（群）協同運行管控的重要保障。

目前，國內極少有機場完全實現了完整的機坪深度感知，但局部的機坪感知網絡（APron Sensor Network，APSN）已實現并形成一定規(guī)模。依靠物聯網技術的機坪感知系統現有問題主要是由于機坪地域特點、航班流及其衍生流密度影響、節(jié)點（智能體）數量及分布、智能體資源和網絡自身質量（運營商或自建網的問題）等因素造成的，一定程度上限制了機坪感知系統的發(fā)展和建設進程。

機坪感知網絡（APSN）架構本質上是異構物聯網，分布式、不對稱地感知、采集與處理周邊環(huán)境的信息，針對所提出的問題，本文從時間同步這一底層支撐技術角度展開研究，為APSN 的數據融合、協同監(jiān)測、節(jié)點定位、智能休眠、避免通信沖突等應用實現［1-5］提供基礎與前提。收斂速度是時間同步算法的核心著眼點和評價指標，尤其在大規(guī)模物聯應用中，快速收斂時間同步算法對于網絡應用的順利執(zhí)行是至關重要的，更快的一致性算法需要更少的同步周期達到網絡時間同步，同時能夠快速適應網絡拓撲結構與時間偏斜的變化。

時間同步問題及其方法廣泛應用于諸多物聯感知領域，如軍事國防、環(huán)境監(jiān)測、醫(yī)療健康等分布式網絡場景；而本文提出的APSN 場景，具有典型的行業(yè)應用特色，同時本質上和其他分布式物聯網絡有相似之處，故研究結果對其他領域應用同樣有參考價值。

當前，在分布物聯領域，大量網絡時間同步算法已被提出，主要可分為層級式和分布式。層級式時間同步算法如RBS（Reference-Broadcast Synchronization）算法［6］，它需要額外的拓撲管理協議，如生成樹協議、簇協議以保證算法有效性，考慮到網絡拓撲結構變化會導致算法失效，從而魯棒性不高。由于層級式算法魯棒性不高，進一步提出半分布式算法如FTSP（Flooding Time Synchronization Protocol）［7］，此類算法不需要拓撲管理協議，由一個參考節(jié)點定期廣播其時間在網絡中傳播，同時其他節(jié)點與該節(jié)點同步。再進一步，學者將多智能體一致性引入，提出全分布式的時間同步算法，如GTSP（Gradient Time Synchronization Protocol）［8］，ATS（Average TimeSynch）［9］算法，利用節(jié)點間的局部信息交換實現全局的狀態(tài)一致。它能夠適應有與拓撲變化問題，魯棒性高，近幾年得到廣泛關注。

基于一致性的時間同步算法相比其他算法更具魯棒性，但由于分布式同步協議主要基于全局節(jié)點進行時間擴散和不停地同步迭代，分布式時間同步協議的收斂速度相對于經典的時間同步算法來說比較慢。比較ATS 與FTSP 算法收斂速度，直徑為8的線型網絡ATS算法需要120個同步周期達到收斂，而FTSP 算法應用到直徑為29 的線型網絡在不超過20 個同步周期就能達到同步［10］，所以對于分布式的一致性時間同步算法，需要找到一種提高收斂速度的方法。

文獻［11］證明，平均一致性算法的收斂速度與網絡的代數連通度成正相關，增加代數連通度是提高收斂速度的有效途徑。而代數連通度又與網絡拓撲的連接稠密程度即連通性有關，可見提高平均一致性算法收斂速度的有效方法是增加網絡連通性。增加節(jié)點鄰居數量是提高連通性的有效方法，文獻［12］提出增加功率增加傳輸半徑進而增加鄰居數提高連通性方案，但考慮到APSN 大量節(jié)點的低成本低功耗特性，特別是機坪中存在著大量邊緣區(qū)域（如遠機位、除冰區(qū)等）中的無線感知節(jié)點，本身資源有限且距其他節(jié)點較遠，單純依靠增加節(jié)點功率也難以達到增加鄰居數進而改善網絡拓撲連接密度，所以很難在物理、功率上改變拓撲。若期望在不改變網絡拓撲、不增加節(jié)點功率情況下提高網絡的連通性，文獻［13］提出通過多跳通信形成多跳節(jié)點間的虛擬鏈路，增加節(jié)點參考信息從而提高代數連通度。文獻［14］利用此理論增加多跳鄰居參考信息應用到多智能體系統編隊一致性控制當中。文獻［15］在GTSP 算法基礎上通過增加虛擬鏈路應用到無線傳感器網絡時間同步，算法的收斂速度能提升數倍。但GTSP算法是一種簡單的一致性時鐘同步協議用來補償時鐘偏差，算法未對時鐘的偏移量進行補償，同步周期很短；在時鐘延遲上，只是用MAC 層時間戳來消除大多數消息延遲，沒有考慮傳輸延遲。

綜合上述研究分析，在考慮傳輸延遲、網絡消耗，且考慮同時補償時鐘偏斜量和偏移量及其延遲［16］的基礎上，可通過構建雙跳節(jié)點間的虛擬鏈路進而改善收斂性能?；诖怂悸?，本文提出快速收斂的平均一致性時間同步算法（Fast Convergence Average TimeSynch，FCATS），考慮實現ATS 算法的改進優(yōu)化，在APSN 節(jié)點延遲項特別是雙跳節(jié)點延遲項條件下，通過對相對時鐘偏斜的修正補償以及對邏輯時鐘偏斜與偏移的一致性同步迭代使FCATS 算法收斂。此外，本文證明了通過增加虛擬鏈路可以有效提高代數連通度，進而影響收斂速度。故應用本文提出的算法，可使網絡時間同步的收斂速度得到很大改善。

1 圖論基礎與節(jié)點時鐘模型

1.1 圖論

假設一個由N 個節(jié)點組成的機坪感知網絡由G=(V，E)表示信息交換網絡拓撲關系，其中V={1，2，…，N}為節(jié)點集合，邊集E ?V × V表示N個節(jié)點間通信關系。若節(jié)點vi可接收到節(jié)點vj的信息，則{i，j}∈E；反之{i，j}?E。令A 為網絡的鄰接矩陣，節(jié)點vi的鄰居節(jié)點集合表示為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 節(jié)點時鐘模型

在諸如APSN 的物聯體系中，每個網絡節(jié)點都有自己的本地時鐘，稱為硬件時鐘，硬件時鐘是通過該節(jié)點所使用的特定頻率振蕩器脈沖產生的。然而，基于APSN 本身異構物聯這一基本屬性，每個網絡節(jié)點振蕩器的振蕩頻率存在差異，同時因硬件壽命、電源電壓或環(huán)境條件（溫度、航空干擾）等不同，每個硬件時鐘受不同時鐘漂移的影響。由于這種時鐘漂移，即使兩個節(jié)點表現出相同的初始時間，它們也會由于時鐘頻率的差異在一定時間后呈現不同的時鐘值。

令節(jié)點vi的硬件時鐘值為τi(t)，可以數學地建模如下：

其中：αi為時鐘偏斜，相當于時鐘速度，理想情況下應為1；βi為時鐘偏移。對于APSN 節(jié)點，只可以直接獲取本地真實時間讀數τi(t)，參數αi和βi是不可能得到的，硬件時鐘不可能輕易調整，所以需定義邏輯時鐘Li(t)也就是同步時鐘概念。

節(jié)點邏輯時鐘Li(t)數學模型為：

大量的實驗觀測數據［7］表明，節(jié)點傳輸過程中的延遲是滿足正態(tài)分布的獨立同分布隨機變量，本文考慮的延遲有界且滿足以下正態(tài)分布：

2 APSN 場景下快速收斂的平均一致性時間同步算法（FCATS）

2.1 FCATS算法原理

APSN 節(jié)點通過硬件時鐘周期性地向鄰居節(jié)點廣播信息包即時鐘信息，包括硬件時鐘、邏輯時鐘偏斜及邏輯時鐘偏移；在本地節(jié)點成功接收到鄰居節(jié)點的信息包中的時鐘參數后，以鄰居節(jié)點作為參考節(jié)點分別對本地時鐘偏斜和時鐘偏移進行迭代修正，從而使各個節(jié)點的邏輯時鐘達到同步。FCATS 算法的核心思想為：在沒有改變APSN 拓撲結構的基礎上，通過在節(jié)點的雙跳鄰居節(jié)點與該節(jié)點建立虛擬鏈路，相比ATS算法增加了節(jié)點的參考節(jié)點數，提高了連通性，進而提高算法收斂速度。FCATS 與ATS 算法的節(jié)點vi的參考節(jié)點對比如圖1所示。

根據機坪網絡場景的實際特征，圖1 所示APSN 節(jié)點，可劃分為三類：i類節(jié)點表示APSN中區(qū)域數據中心節(jié)點（位于特種車車載、固定于機坪設施等處），具有豐富的電力、處理和存儲硬件資源以及路線驅動的移動性；j類節(jié)點為APSN 中數據中繼/集中節(jié)點，而且具有有限的移動性，能夠轉發(fā)來自k類節(jié)點的時鐘信息；k 類節(jié)點是APSN 中邊緣感知節(jié)點或其簇頭，數量巨大且資源有限，分布式分散部署，感知采集機坪資源數據，由于布置分散，k節(jié)點對時間同步實現要求較高（特別是定位、故障、應急信息類感知節(jié)點），如果將k 類節(jié)點信息發(fā)送到雙跳鄰居i類節(jié)點，由于距離較遠需要j類節(jié)點的中繼轉發(fā)。

圖1 兩種一致性算法節(jié)點vi參考節(jié)點對比Fig.1 Reference nodes comparison of node vi between two consensus algorithm

由于自身資源和機坪部署位置，節(jié)點j 與i 類的鏈路往往是比較穩(wěn)定和容易控制的，而對同步性要求較高的k 類節(jié)點，有時與i類節(jié)點難以保證鏈路穩(wěn)定。

平均一致性算法提高收斂速度的有效方法是增加網絡連通性，即提高網絡拓撲的連接稠密程度［11］。在不改變網絡拓撲，不增加節(jié)點功率情況下，本文通過在雙跳鄰居間建立虛擬鏈路，增加了節(jié)點的參考節(jié)點數，提高了網絡的連通性從而提高算法收斂速度。

雙跳鄰居間虛擬鏈路建立過程，以圖1 中的vi與距離兩跳的雙跳鄰居vk建立虛擬鏈路為例，即節(jié)點vk不直接將時鐘信息發(fā)送給節(jié)點vi，而是先傳送至節(jié)點vj（節(jié)點vi的單跳鄰居節(jié)點），經vj轉發(fā)至節(jié)點vi，由于沒有直接發(fā)送給vi，相當于在vi與雙跳鄰居vk間建立虛擬鏈路?？梢姡疚奶岢龅奶摂M鏈路，其基本思想是：在不改變原有網絡拓撲條件下，針對感知節(jié)點的時鐘信息，通過j 類節(jié)點轉發(fā)，增加傳輸跳數使k 類節(jié)點時鐘信息傳送到i 類節(jié)點，i 與k 類節(jié)點相當于在拓撲上增加了虛擬的鏈路，即虛擬鏈路。

對于時間同步過程中節(jié)點的參考節(jié)點，從圖1（a）可以看出，ATS 算法中節(jié)點vi只接收并處理其鄰居節(jié)點vj廣播信息包。而在FCATS算法中，從圖1（b）可以看出，本文提出節(jié)點vi不只接收并處理其鄰居節(jié)點vj的廣播信息包，通過vi與雙跳鄰居vk虛擬鏈路的建立，距離節(jié)點vi兩跳距離的節(jié)點vk也通過節(jié)點vj轉發(fā)給節(jié)點vi進行處理。因此，FCATS 算法通過節(jié)點vi與雙跳節(jié)點vk的虛擬鏈路建立，節(jié)點vi在同步過程中參考了鄰居節(jié)點vj與雙跳鄰居節(jié)點vk的時鐘信息，網絡的連通性得到提高。

在具體的時間同步過程中，如圖2 所示：每個節(jié)點在第l(l=1，2，…，n)個時鐘周期廣播信息包，節(jié)點同步過程異步接收鄰居節(jié)點時鐘信息，每個節(jié)點更新時鐘參數的時刻是不同的，所以降低了信息包傳送時的節(jié)點間時間偏移影響，但傳輸延遲對同步過程影響較大。當節(jié)點vk同步周期被觸發(fā)，節(jié)點vk的廣播包括時間戳Tk的信息包MSG1傳到鄰居節(jié)點vj，此時的傳輸延遲為本算法要求節(jié)點信息包不只傳輸到其鄰居節(jié)點，還要傳到其雙跳鄰居節(jié)點，節(jié)點vk信息包傳輸到雙跳鄰居節(jié)點vi需要節(jié)點vj轉發(fā)，所以節(jié)點vj將迅速將包括時間戳Tk與Tj的信息包MSG2傳遞給節(jié)點vi，其中在節(jié)點vj中停留的延遲Td忽略不計，此時的傳輸延遲為因此，節(jié)點vi不只收到節(jié)點vj的信息包，通過vj的中繼轉發(fā)，相當于在節(jié)點vi和vk之間產生了一條虛擬鏈路收到vk的信息包。

在考慮有界延遲情況下，對于雙跳鄰居節(jié)點，由于需要中間節(jié)點中繼，所以需要兩步才能完成同步包的傳輸，這里忽略中間節(jié)點的處理時間Td，所以其延遲為：

圖2 帶延遲的信息包傳遞示意圖Fig.2 Schematic diagram of packet delivery with delay

2.2 FCATS算法收斂性分析

在實際應用中，并不能得到APSN 節(jié)點自身的時鐘偏斜，所以不能直接對相鄰的APSN 節(jié)點進行偏斜估計，而是通過估計相對時鐘偏斜進而對邏輯時鐘偏斜估計，這樣完成對時鐘偏斜的補償。本文對于邏輯時鐘偏斜估計如下：

其中：ρα為收斂梯度系數，αij為APSN 節(jié)點vi、vj的相對時鐘偏斜。

在無延時的情況下，節(jié)點vi，vj的相對時鐘偏斜αij：

在存在延時的情況下，節(jié)點vi，vj的相對時鐘偏斜αij：

其中，對于vi的單跳鄰居節(jié)點vj：

由于vk是vi的雙跳虛擬鄰居節(jié)點，所以：

由式（5）、（7）可得，節(jié)點間延遲主要影響相對時鐘偏斜，從而影響邏輯時鐘偏斜估計，從而時鐘同步發(fā)散，故為避免同步過程發(fā)散，需要對其相對時鐘偏斜補償，采用加權平均的方式對所有相對時鐘偏斜取加權平均：

單跳鄰居節(jié)點對vi、vj與雙跳鄰居節(jié)點對vi、vk之間相對時鐘偏斜需要修正補償，下面證明經過式（10）的修正補償迭代，相對時鐘偏斜1概率收斂與真實情況。

定理1在存在正態(tài)分布的延遲情況下，由式（10）獲得相對時鐘偏斜估計αij(l)、αik(l)，經修正迭代后1 概率收斂到對于雙跳節(jié)點對1概率收斂到

證明 對于雙跳節(jié)點對vi，vk，將式（7）代入式（10）得：

本文對于邏輯時鐘偏移估計如下：

其中ρb為收斂梯度系數。由文獻［13］可知，在延遲情況下時鐘偏移不會放大，其同步結果有界。

2.3 FCATS算法收斂速度的分析

關于代數連通度與收斂速率，網絡G的代數連通度λ2(L)影響平均一致性的收斂速度與收斂時間［13］，故提出：

引理2網絡節(jié)點鏈路越多，代數連通度越大，收斂速度越快。相對來說，對于稠密的網絡，代數連通度大；反之，代數連通度小。

由文獻［11］與［13］可知，代數連通度λ2(L)與網絡G的拓撲結構的連通性有關系，稠密圖的λ2(L)由于網絡的連通性的改善相對比稀疏圖大。如果對距離雙跳以上的APSN 節(jié)點之間建立虛擬鏈路，雖然使網絡變得更稠密，但是APSN 的時間同步對能耗的要求，需要盡可能地節(jié)約廣播包的個數，以及多跳延遲對算法收斂的不確定性影響。所以，在通信拓撲結構不變的情況下，針對提高平均一致性收斂速度的要求，本文提出對APSN 節(jié)點周邊的雙跳鄰居節(jié)點對之間進行虛擬鏈路擴充的操作，即使網絡變得更稠密，又相對減少了廣播包。

在增加虛擬鏈路前，APSN 節(jié)點vi的離散一致性動力學方程如下：

在增加虛擬鏈路后，APSN 節(jié)點vi的離散一致性動力學方程為：

對比式（13）與（14），APSN在雙跳鄰居節(jié)點之間建立虛擬鏈路后，在進行一致性時間同步迭代計算過程中增加了迭代參考，對于收斂速度的提升證明如下：

綜上可知，在通信拓撲結構不變的情況下，時間同步算法通過增加雙跳鄰居節(jié)點之間進行虛擬鏈路，算法的收斂速度得到提高。

3 仿真實驗與分析

本文所提的時間同步算法FCATS，是在增加虛擬鏈路基礎上的平均一致性算法。在考慮傳輸延遲的情況下，通過補償相對時鐘偏斜，避免了延遲對同步的影響；通過對時鐘偏斜和時鐘偏移的迭代估計修正，實現網絡的時間同步。

提出的FCATS 算法與ATS 算法在收斂性與收斂效果方面進行仿真比較，所用的APSN 是圖3 所示的5×4 的網格型網絡。為了分析算法適用性，將線型、環(huán)型與隨機網絡拓撲引入分析FCATS算法在收斂速度上提升的效果。

圖3 網格型拓撲結構Fig.3 Grid topology

在進行仿真實驗時，APSN節(jié)點時鐘參數如表1所示。

表1 APSN節(jié)點時鐘參數表Tab.1 APSN node clock parameters

其中，定義邏輯時鐘偏斜誤差為各節(jié)點邏輯時鐘偏斜誤差的最大值，邏輯時鐘誤差為各節(jié)點邏輯時鐘誤差的最大值。

FCATS的仿真過程偽代碼如下：

算法 FCATS算法。

在存在有界傳輸延遲的情況下，經過式（10）對相對時鐘偏斜的迭代補償修正，消除了延遲項θij(l)的影響使相對時鐘偏斜的得到收斂，又通過式（5）的一致性同步迭代，由圖4 可知，FCATS算法的邏輯時鐘偏斜誤差得到收斂，相較于ATS算法，FCATS 的邏輯時鐘偏斜誤差提前20 個迭代周期實現收斂。除此之外，從圖中可以看出，由于的雙跳節(jié)點間的虛擬鏈路增加，節(jié)點邏輯時鐘偏斜更新時，參考鄰居節(jié)點數量的增加，APSN 節(jié)點邏輯時鐘偏斜誤差在收斂拐點處，FCATS 在達到峰值時經過幾個迭代周期就達到穩(wěn)定值以下，而ATS 需要數倍時間才能達到穩(wěn)定值，這說明FCATS 能夠迅速使APSN節(jié)點邏輯時鐘偏斜達到同步值。

圖4 兩種算法邏輯時鐘偏斜誤差對比Fig.4 Skew error comparison of logic clocks between two algorithms

由圖4 可知，通過式（5）、（12）對邏輯時鐘偏斜與偏移的一致性同步迭代，邏輯時鐘誤差穩(wěn)定在10-3s內，能滿足APSN場景下應用的需要。相較于ATS 算法，由圖4 和圖5 可知，FCATS 在邏輯時鐘誤差與邏輯時鐘偏斜誤差收斂速度上快20 個迭代周期，快50%左右。這是由于FCATS 通過增加APSN的雙跳節(jié)點間的虛擬鏈路，APSN的鄰居節(jié)點增多，網絡與拓撲連通性得到改善，由式（15）知代數連通度λ2(L)增大，經計算其從0.382 增長到2.276。這說明在沒有改變通信拓撲結構的情況下，FCATS提升了收斂速度。

圖5 兩種算法的最大邏輯時鐘誤差對比Fig.5 Maximum logic clock error comparison of two algorithms

時間同步算法的可伸縮性即在不同直徑網絡拓撲下算法的適用性，是檢驗算法優(yōu)越性的重要指標。本文選取不同直徑的線型拓撲對收斂性能進行驗證，如圖6 所示：在不同直徑下的線性拓撲，FCATS 的代數連通度總是高于ATS。以上已證明通過在雙跳節(jié)點間添加虛擬鏈路，代數連通度增大，網絡一致性收斂速度提高。這說明FCATS 在不同直徑下的收斂快速性依然適用，算法的可伸縮性強。

圖6 網絡拓撲直徑與代數連通度關系圖Fig.6 Relationship between network topology diameter and algebraic connectivity

此外，本文對不同拓撲條件下的網絡收斂情況進行了對比研究，分別選取線型、環(huán)型、網格型和隨機網絡拓撲。由圖7 可知，在以上幾種實際常見網絡拓撲中，由于虛擬鏈路的建立，網絡的連通性增強，代數連通度λ2(L)增大，FCATS 始終比ATS 具有更短的收斂時間，而收斂速度分別提升63%、56%、54%和21%。除此之外，由于網絡拓撲結構的不同，從圖7 中可以看到，由于隨機網絡拓撲的結構特性，收斂速度快所以速度提升空間小，但通過FCATS，仍能夠提升收斂速度。所以，雖然拓撲結構關系對于不同拓撲算法的收斂速度提升效果不同，但FCATS 對于不同網絡拓撲時間同步收斂速度都能得到改善。

圖7 不同拓撲的收斂速度Fig.7 Convergence speeds of different topologies

4 結語

本文針對APSN 的一致性時間同步算法收斂速度慢問題，提出了一種基于虛擬鏈路的一致性時間同步算法FCATS，即在網絡拓撲結構不變的情況下，在雙跳鄰居節(jié)點間增加虛擬鏈路。FCATS 算法具有如下特點：1）在存在有界傳輸延遲下，通過對相對時鐘偏斜的修正補償以及邏輯時鐘偏斜與偏移的一致性同步迭代，APSN實現了在雙跳鄰居節(jié)點間增加虛擬鏈路后算法的時間同步收斂；2）相較于ATS，APSN 在雙跳鄰居節(jié)點間增加虛擬鏈路，增加了代數連通度，提高了收斂速度；3）算法在不同直徑、拓撲條件下依然能夠改善算法收斂速度，且本算法在除APSN 外其他場景具有適用性。本算法雖在收斂速度提升上效果明顯，但在增加虛擬鏈路后，APSN 節(jié)點傳輸信息包增多，以后將在進一步減少信息包傳輸次數基礎上加快收斂速度；還將在更多不同的場景中評估所提出的協議，并將其與其他協商一致的時間同步協議進行比較。