面向航空電子云的混合式時間同步算法

李 錚 李 峭 趙露茜 熊華鋼

(北京航空航天大學 電子信息工程學院，北京100191)

航空電子云[1]將美國國家航空航天局[2]和歐盟[3]提出的分布式思想擴展到網絡層面，將云計算概念引入航空電子領域，以提高航空電子系統的性能.航空電子云中的節點不但能共享信息，而且能實現處理能力的共享.因此，保持節點之間的時間同步非常重要.由于航空電子云網絡拓撲是動態變化的，并且航空電子應用具有時間關鍵性，因此航空電子云要求時間同步需要同時具備高同步精度、高收斂速度和高魯棒性3個性能.

針對傳統無線時間同步算法，文獻[4]提出基于全球定位系統(GPS，Global Position System)的方法，其同步精度高，但是依賴于美國的GPS衛星，缺乏安全保障.文獻[5－9]提出集中式同步方法，以根節點[5－8]或簇頭[9]為參考節點進行同步.該方法的收斂速度相對較快，但是魯棒性較差，一旦參考節點或中繼節點失效，部分節點將由于接收不到同步消息而失去同步.文獻[10]提出協作同步技術，遠方節點可直接與參考節點同步.該方法消除了同步誤差單跳累加，但是核心思想仍屬于集中式同步，參考節點失效將對時間同步產生毀滅性影響.文獻[11－14]提出分布式同步方法，節點通過調整自身時鐘到其可觀察到的更快的時鐘[11]，或對鄰居節點的時鐘取平均值[12－13]，或取帶有權重的平均值[14]來實現同步.該方法具有較強的魯棒性，但是收斂速度較慢[12].

本文建立了航空電子云系統模型，并以此為基礎提出了一種混合式時間同步算法.根據鄰居節點的狀態，網絡中各節點能夠在集中式和分布式兩種同步操作之間動態切換，同時借助貝葉斯估計，提高時間同步精度.該算法在保證高收斂速度和高精度的同時，仍然能夠維持較好的魯棒性，從而適應了航空電子云對時間同步的需求.

1 系統建模

1.1 網絡模型

對航空電子云進行抽象，假設網絡中有n個節點，通過一定的拓撲結構連接成一個無線網絡，并且網絡拓撲隨時間動態變化.用一個有向連通圖G(t)=(V，E(t))來描述此無線網絡，其中V表示網絡的節點集合，E(t)表示在t時刻網絡的邊集合.假設 Ai表示第 i個節點，則 V={A1，A2，…，An}.如果在t時刻Aj在Ai的通信范圍內，則稱Aj是Ai的鄰居節點，且存在邊eij∈E(t).

1.2 時鐘模型

本文采用的時鐘模型同時考慮了時鐘的偏移和漂移對本地時鐘的影響.在航空電子云網絡中，每一個節點Ai的本地時鐘，均由下式表示:

式中，Ti是本地時鐘的讀數;αi是本地時鐘的漂移;βi是本地時鐘的偏移量.

參考節點的時鐘存在由漂移引起的誤差.通常，參考節點的時鐘誤差服從均值為0、方差為σ的正態分布[15]，實驗測得σ的值為50 ns.

1.3 延時模型

節點同步是通過消息交換實現的，因此消息的傳輸延遲是產生同步誤差的主要原因之一.消息的傳輸延遲可分為發送處理時間、訪問時間、傳輸時間、傳播時間、接收時間和接收處理時間.

通過MAC層打時間戳技術，可以消除發送處理時間和訪問時間的影響.通過統一消息長度，可在交換消息過程中抵消傳輸時間和接收時間的影響.通過距離和無線電波的傳播速度，可以計算得到傳播時間.節點之間的接收處理時間差異服從均值為0、方差為11.1 μs的正態分布.

2 混合式時間同步算法

本文提出的混合式時間同步算法主要分為集中式同步和分布式一致同步兩類操作.

2.1 集中式同步操作

2.1.1 同步流程

集中式同步操作流程可以總結為5個步驟:

1)網絡中的所有節點按照時鐘精度排序，精度最高的時鐘作為主時鐘，建立拓撲生成樹.

2)主時鐘以固定的同步周期定期廣播同步消息SYNC到從時鐘，該消息包含發送時的時間戳和主時鐘位置的經緯度.記主時鐘發送第k次SYNC 消息的時間戳為 TSY，Mk，經緯度為(XSY，Mk，YSY，Mk)，從時鐘在本地時間TSY，Sk時刻，經緯度(XSY，Sk，YSY，Sk)處接收到該消息.

3)在接收到第k次SYNC消息后，從時鐘隨機延時一段時間，在本地時間TDR，Sk時刻，經緯度(XDR，Sk，YDR，Sk)處發送延時請求消息 DELAY_REQ到主時鐘.

4)主時鐘在本地時間 TDR，Mk時刻，經緯度(XDR，Mk，YDR，Mk)處接收到第 k 次延時請求消息，并發送包含該時間戳的應答消息DELAY_RESP到從時鐘.

5)從時鐘根據上述4個時間戳和位置計算時鐘偏移并進行時鐘調整，實現與主時鐘的同步.

2.1.2 偏移的補償

從時鐘可以通過以下公式計算本地時鐘在第k個同步周期內與主時鐘之間的偏移βSk:

式中，DSY，Pk和 DSY，Rk分別表示第 k 個 SYNC 消息的傳播時間和接收處理時間;DDR，Pk和 DDR，Rk分別表示第k個DELAY_REQ消息的傳播時間和接收處理時間.暫時假設 DSY，Rk和 DDR，Rk相同，兩者差異可以之后通過貝葉斯估計進行補償，具體補償方法見2.3.2 節.則由式(2)和式(3)可得

式中 DSY，Pk和 DDR，Pk可分別由下式計算得到:

式中，111.17是單位地球中心夾角對應的地球表面弧長，單位是km;c是電磁波的傳播速度，取值為 0.3 km/μs.

偏移的計算在每個同步周期內進行.從時鐘根據偏移調整本地時鐘，從而實現與主時鐘同步.

2.2 分布式一致同步操作

2.2.1 同步流程

分布式一致同步操作是網絡內的節點與鄰居節點進行時間消息的融合，調整自身時鐘，最終實現全網節點同步到同一個虛擬時鐘上.節點Ai和節點Aj之間進行消息融合的流程如下所示:

1)節點Aj以固定的同步周期定期廣播同步消息SYNC到節點Ai，該消息包含發送時的時間戳和經緯度.記節點Aj發送第k次SYNC消息的時間戳為 Tj，k，經緯度為(Xj，k，Yj，k)，從時鐘在本地時間Ti，k時刻，經緯度(Xi，k，Yi，k)處接收到該消息.

2)節點Ai通過第k－1次和第k次SYNC消息攜帶的時間戳和經緯度，由下式可以計算得到節點Ai和Aj之間第k個時鐘相對漂移量αij，k:

式中，DP，k－1和 DR，k－1分別表示第 k－1 個 SYNC 消息的傳播時間和接收處理時間;DP，k和 DR，k分別表示第k個SYNC消息的傳播時間和接收處理時間.暫時假設 DR，k－1和 DR，k相同，兩者差異可以之后通過貝葉斯估計進行補償，具體補償方法見2.3.3節.則式(7)可以化簡為

式中 DP，k－1和 DP，k的計算方法同式(5)和式(6).

3)Ai根據αij，k進行時鐘漂移與偏移的調整，多次調整后實現全網同步到同一個虛擬時鐘上.

2.2.2 漂移和偏移的補償

記節點Ai對漂移和偏移的第k次補償分別為 αi，k和 βi，k，補償后的時鐘讀數 TCOM，i，k如下式所示:

式中，Ti表示節點 Ai的原始本地時鐘讀數;αi，k可由下式迭代計算得到:

式中，ρα表示漂移調整參數，0＜ρα＜1;αj，k－1表示節點 Aj對漂移的第k－1次補償，αi，0和 αj，0的取值為 1.βi，k可由下式迭代計算得到:

式中，ρβ是偏移調整參數，0＜ρβ＜1;βi，0取值為0.

文獻[12]證明了通過式(10)和式(11)對節點漂移和偏移進行不斷地調整，最終全網節點將同步到同一個虛擬時鐘上，證明過程這里不再贅述.

2.3 接收處理時間補償操作

由于節點之間的接收處理時間差異服從正態分布，因此可以通過貝葉斯估計對其進行補償.

2.3.1 貝葉斯估計

假設觀測值x的概率密度函數滿足正態分布p(x|μ) ～N(μ，σ2)，其中 μ 未知，σ2已知.假設 μ的先驗概率滿足正態分布，其中均已知.根據貝葉斯公式可以得到:

式中

與μ及x無關，為常數，所以p(μ|x)也滿足正態分布，令，則有

2.3.2 集中式同步的補償

在集中式同步過程中，接收處理時間的差異主要影響偏移量的計算，而偏移量則直接影響補償后的時鐘時間.記偏移量補償后的當前節點時鐘時間為TCOM，i，通過貝葉斯估計方法估算的當前節點實際時間為 TBAY，i，則 TBAY，i－1表示通過貝葉斯估計方法估算的上一層節點的實際時間，且服從方差為的正態分布.由 1.3 節中建立的延遲模型可知，接收處理時間的差異服從正態分布 N(0，σ2)，其中σ 取值為 11.1 μs.則由式(14)和式(15)可以計算得到通過貝葉斯估計后的當前節點時間分布，其中

根據1.2節建立的時鐘模型，令TBAY，1=T1，σBAY，1取值為50 ns，則上層節點把它的貝葉斯估計時間 TBAY，i－1和估計誤差方差傳給下層節點后，下層節點可以利用式(16)和式(17)計算出，如此逐級同步從而實現全網同步.

2.3.3 分布式一致同步的補償

在分布式一致同步過程中，接收處理時間的差異主要影響時鐘相對漂移量αij，k的計算.記節點通過貝葉斯估計方法估算的第k－1個時鐘相對漂移量為 αBAY，ij，k－1，且服從方差為的正態分布.由1.3節中建立的延遲模型可知，接收處理時間的差異服從正態分布N(0，σ2)，其中σ取值為11.1 μs.則由式(14)和式(15)可以計算得到通過貝葉斯估計后的第k個時鐘相對漂移量分布，其中

2.4 混合式同步算法流程

綜合上面給出的各操作，本文提出一種混合式時間同步算法，系統時鐘的同步流程如下所示:

1)網絡中的所有節點按照時鐘精度排序，精度最高的時鐘作為根節點，建立拓撲生成樹，設定所有節點的同步方式為“集中式”，根節點的狀態設定為“已同步”，所有從節點的狀態設定為“未同步”.

2)采用集中式同步操作對同步方式為“集中式”的從節點時鐘進行同步.

3)若從節點的時鐘校正值小于預先設定的閾值，則設定此節點的狀態為“已同步”，否則設定此節點的狀態為“未同步”.

4)狀態為“已同步”的節點查詢鄰居節點的狀態，若狀態為“已同步”的鄰居節點數大于等于預先設定的閾值，則設定此節點的同步方式為“分布式”，否則設定此節點的同步方式為“集中式”.

5)采用分布式一致同步操作對同步方式為“分布式”的節點時鐘進行同步.

6)若需要維持全網時間同步狀態，則返回第2)步，否則結束同步過程.

3 仿真實驗及結果分析

為了評價混合式同步算法的性能，將其與傳統的集中式算法[5]和分布式算法[11]進行比較.仿真在基于VC開發的異構通信系統仿真平臺下進行，該平臺已在具體工程項目中得到應用和驗證.仿真場景為飛機和地面站組成的航空電子云網絡，網絡拓撲如圖1所示.

圖1 實驗網絡拓撲Fig.1 Experimental network topology

在網絡中共有7個節點，其中節點1為地面站，其余節點為飛機.地面站作為根節點，根節點時鐘的漂移量為1，其余節點時鐘每秒漂移50 μs.根節點時鐘的初始偏移量為0，其余節點時鐘的初始偏移量為[－15，15]s之間的均勻分布.同步周期為5 s，調整參數 ρα=0.9，ρβ=0.4，校正值閾值為1 ms，鄰居節點數閾值為2，飛機航行速度為[750，800]km/h 之間的均勻分布.

圖2比較了3種算法的同步精度.因為跳數和鄰居節點數是影響同步誤差的主要因素，所以取節點7作為參考.在混合式算法中，穩定后的同步誤差最大僅有53 μs，而在集中式算法中，同步誤差最小值也達到了125 μs.在分布式算法中，雖然同步誤差最小值達到了25 μs，但是抖動較大，最大值達到了319 μs.由仿真結果可知，混合式算法通過貝葉斯估計，明顯提高了同步精度.

圖2 節點7的不同算法同步精度對比Fig.2 Node 7 synchronization accuracy comparison of different algorithms

圖3比較了3種算法的魯棒性.通過設定網絡邊集合E(t)中元素失效的概率，觀察網絡中同步失效的節點數占節點總數比例的變化趨勢.由圖3可知，集中式算法的魯棒性最差，因為根節點路徑和上級路由路徑的失效，會對同步產生較大影響.在鏈路失效率低于50%時，混合式算法的魯棒性與分布式算法基本持平;在鏈路失效率高于50%時，混合式算法的魯棒性介于集中式算法和分布式算法之間，因為此時部分節點切換為集中式同步操作，但是現實中高鏈路失效率的情況比較少見.

圖3 不同算法魯棒性對比Fig.3 Robustness comparison of different algorithms

圖4比較了3種算法的收斂速度.分布式算法的收斂速度最慢，因為節點之間需要進行多次信息融合才能同步到同一個虛擬時鐘上.混合式算法與集中式算法的收斂速度相同，因為混合式算法在同步初期采用的是集中式同步操作.

圖4 不同算法收斂速度對比Fig.4 Convergence rate comparison of different algorithms

4 結論

1)針對航空電子云對時間同步的需求，為航空電子云建立了網絡模型、時鐘模型和延時模型.

2)通過分析集中式和分布式兩種同步算法的特點，利用貝葉斯估計方法，提出了一種混合式時間同步算法，給出了系統時鐘同步的具體流程.

3)搭建了航空電子云的典型網絡，通過仿真實驗對混合式時間同步算法的性能進行了分析.實驗結果表明，該算法在同步精度上比集中式算法提高了72μs，比分布式算法提高了266 μs，同時該算法具有最高的收斂速度，并且在鏈路失效率低于50%時，其魯棒性與分布式算法基本持平.

References)

[1]Li Z，Li Q，Xiong H G.Avionics clouds:a generic scheme for future avionics systems[C]//31st Digital Avionics Systems Conference.Piscataway，NJ:IEEE，2012:6E41 －6E410

[2]Fletcher M.Progression of an open architecture:from Orion to Altair and LSS[R].S65-5000-20-0，2009

[3]Fuchsen R.IMA NextGen:a new technology for the Scarlett program[J].Aerospace and Electronic Systems Magazine，2010，25(10):10－16

[4]Sterzbach B.GPS-based clock synchronization in a mobile，distributed real-time system[J].Real-Time Systems，1997，12(1):63－75

[5]Ganeriwal S，Kumar R，Srivastava M B.Timing-sync protocol for sensor networks[C]//1st International Conference on Embedded Networked Sensor Systems.New York:ACM，2003:138 －149

[6]Su W，Akyildiz I F.Time-diffusion synchronization protocol for wireless sensor networks[J].IEEE/ACM Transactions on Networking，2005，13(2):384 －397

[7]張春梅，白鳳山，王平，等.一種改進的TPSN時間同步算法的實現[J].內蒙古大學學報:自然科學版，2013，44(3):316－319

Zhang Chunmei，Bai Fengshan，Wang Ping，et al.Implement of an improved TPSN time synchronization algorithm[J].Journal of Inner Mongolia University:NaturalScienceEdition，2013，44(3):316－319(in Chinese)

[8]師超，仇洪冰.基于脈沖耦合的TPSN時間同步協議[J].應用科學學報，2013，31(1):15 －20

Shi Chao，Qiu Hongbing.TPSN time synchronization protocol based on pulse coupling[J].Journal of Applied Sciences，2013，31(1):15－20(in Chinese)

[9]Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660 －669

[10]Hu A，Servetto S D.On the scalability of cooperative time synchronization in pulse-connected networks[J].IEEE Transactions on Information Theory，2006，52(6):2725 －2748

[11]Zhou D，Lai T H.An accurate and scalable clock synchronization protocol for IEEE 802.11-based multihop ad hoc networks[J].IEEE Transactions on Parallel and Distributed Systems，2007，18(12):1797 －1808

[12]Li Q，Rus D.Global clock synchronization in sensor networks[J].IEEE Transactions on Computers，2006，55(2):214 － 226

[13]師超，仇洪冰，陳東華，等.一種簡單的分布式無線傳感器網絡時間同步方案[J].西安電子科技大學學報，2013，40(1):93－99

Shi Chao，Qiu Hongbing，Chen Donghua，et al.Simple distributed time synchronization scheme for wireless sensor networks[J].Journal of Xidian University，2013，40(1):93 － 99(in Chinese)

[14]Schenato L，Gamba G.A distributed consensus protocol for clock synchronization in wireless sensor network[C]//46th IEEE Conference on Decision and Control.Piscataway，NJ:IEEE，2007:2289 －2294

[15]Lewandowski W，Petit G，Thomas C.Precision and accuracy of GPS time transfer[J].IEEE Transactions on Instrumentation and Measurement，1993，42(2):474 －479