孫力，鄒德財，韓濤

基于卡爾曼濾波的Ad Hoc網絡節(jié)點間時間同步算法研究

孫力1,2,3，鄒德財1,2,4，韓濤5

（1. 中國科學院 國家授時中心，西安 710600；2. 中國科學院 精密導航定位與定時技術重點實驗室，西安 710600；3. 中國科學院大學，北京 100049；4. 中國科學院大學 天文與空間科學學院，北京 101048；5.西安理工大學 理學院，西安 713300）

本文建立了Ad Hoc網絡節(jié)點的時鐘模型，設計了適用于網絡節(jié)點時鐘模型的Kalman濾波算法，利用時差噪聲的分形特征估計Kalman濾波的協(xié)方差矩陣，并對時鐘噪聲序列特征進行分析。仿真結果表明，該算法不僅提高了濾波算法效率，同時能明顯降低網絡節(jié)點間的時鐘偏差，實現(xiàn)了Ad Hoc網絡節(jié)點間的高精度時間同步，同步精度優(yōu)于25ns。

Ad Hoc；網絡節(jié)點；分形特性；Kalman濾波

0 引言

近年來，無線通信技術取得了快速發(fā)展，傳統(tǒng)的無線移動通信網絡已不能滿足某些特殊場合，如軍事、救災搶險等對自主定位的需求。在這一背景下，Ad Hoc網絡[1]應運而生，在網絡部署方面比較靈活，可以在一些沒有通信基礎設施的地區(qū)自由組網。Ad Hoc網絡所有節(jié)點都可以隨意進入或退出，各節(jié)點之間的地位和功能是平等的[2]。但由于缺少標準時鐘為網絡中的節(jié)點提供時間參考，各個網絡節(jié)點時鐘不同步，其時間差異很有可能導致整個網絡架構不能正常運行，自主定位功能無法實現(xiàn)。因此，網絡節(jié)點間的時間同步是整個網絡系統(tǒng)有效運行的重要保證。

Ad Hoc網絡架構如圖1所示。Ad Hoc網絡不依賴基礎網絡設施的建立，避免了基礎設施網絡的故障影響到整個網絡系統(tǒng)通信的問題，它是一個沒有中心的網絡節(jié)點，所有的網絡節(jié)點都是平等的，沒有優(yōu)先級之分。在網絡系統(tǒng)結構中，采用分布式的組網特征，網絡節(jié)點之間自由組網，具有自主對等的特性，具有良好的抗毀性和健壯性。

圖1 Ad Hoc網絡架構圖

1 Ad Hoc網絡時間同步算法

當前，許多學者在無線自組織網絡時間同步方面開展了研究并提出了各種算法。在這些不同的網絡節(jié)點時間同步算法中，S. Ganeriwal等人[3]提出的傳感器網絡定時同步算法（TPSN）、J. Elson等專家[4-5]提出的參考廣播同步算法（RBS）、B. Kesy等人[6]提出的防洪時間同步算法（FTSP）和Pings等人提出的延時測量時間同步算法（DMTS）[7]是比較典型的幾個方法。傳統(tǒng)網絡節(jié)點時間同步算法的特點如表1所示。

表1 網絡時間同步算法

在Ad Hoc網絡中節(jié)點具有多跳的特征。據(jù)此FTSP算法采用層級的網絡結構，這種網絡結構在大規(guī)模的網絡節(jié)點下是比較適用的，多個接收者與根節(jié)點發(fā)送的廣播信息進行同步。對于網絡結構的動態(tài)變化以及一些網絡節(jié)點的異常情況，F(xiàn)TSP算法的容錯性都是比較好的。在時間同步的過程中利用線性回歸的方式不斷精確地計算偏移量，補償了網絡節(jié)點的時間偏差，從而獲得更高的同步精度。對比之下，F(xiàn)TSP算法更適合Ad Hoc網絡節(jié)點間的時間同步。

2 Ad Hoc網絡時鐘模型

式（5）中

那么，離散的時鐘模型可以表示為

3 Ad Hoc網絡時鐘模型的Kalman濾波方法

Kalman濾波廣泛應用于導航、傳感器數(shù)據(jù)融合、雷達系統(tǒng)以及導彈追蹤等。近來更被應用于人臉識別、圖像分割等計算機圖像的處理。它也是一種經常用來描述網絡節(jié)點時鐘差的方法，可以用來描述節(jié)點時鐘的噪聲狀態(tài)。預測與更新是在使用卡爾曼濾波進行的兩個過程[15]。首先想要對當前時刻的狀態(tài)做出估計，就需要使用上一時刻的狀態(tài)對它進行預測估計，這個就是預測過程。然后想要優(yōu)化預測操作中預測的這個估計值，那就需要當前時刻的觀測狀態(tài)量來對其進行優(yōu)化，這個就是更新過程。整個卡爾曼濾波過程即：先預測，做出先驗估計。之后計算卡爾曼增益，再得到估計值，這個后驗估計值就與真值更為接近[16]。

假設在Ad Hoc網絡中，兩個節(jié)點的頻率是相同的。這個假設與整個網絡架構的實際情況是不相符的，但是通過時鐘模型的Kalman濾波方法可以改進頻率不同的情況。則基于上述的假設條件，網絡節(jié)點間時差的Kalman濾波的數(shù)學表達式為

狀態(tài)轉移矩陣和噪聲的協(xié)方差矩陣分別表示為：

則：

由上述可以知道，對協(xié)方差矩陣的估計、節(jié)點時鐘譜密度的估計以及時鐘漂移率譜密度的估計是使用Kalman濾波算法處理節(jié)點時鐘偏差的關鍵，可以參考系統(tǒng)時鐘噪聲序列特征對這些數(shù)值進行估計。

3.1 時鐘噪聲序列特征分析

對時鐘噪聲序列進行特征分析，可以使得節(jié)點時鐘模型能夠通過數(shù)學方法更準確的描述，是建立更精確的時鐘模型、提高網絡間時間同步精度和效率的前提。

3.1.1 時差序列獲取

為了更加準確地利用數(shù)學方法描述節(jié)點時鐘模型，必須對其數(shù)據(jù)特征進行描述。為此，本文基于中國科學院國家授時中心的1 PPS時間基準對3個網絡節(jié)點晶振的時間求取時差序列，分析其噪聲特性。由式（8）可知，對這3個觀測量進行線性擬合，其擬合殘差描述了它們各自的噪聲情況。殘差序列的數(shù)字特征如表2所示。

表2 節(jié)點時鐘偏差殘差序列數(shù)字特征 單位：s

3.1.2 噪聲序列的非正態(tài)性

對噪聲序列的分析是建立更精確的時鐘模型的前提，是提高網絡間時間同步精度和效率的必要前提。從它們的頻數(shù)直方圖（圖2）中很難看出它們是否服從正態(tài)分布。

圖2 3個網絡節(jié)點晶振時差序列頻數(shù)統(tǒng)計直方圖

本節(jié)將通過雅各-貝拉檢驗（Jarque-Bera）來驗證本文所采用的網絡節(jié)點時鐘數(shù)據(jù)是否具有符合正態(tài)分布的偏度和峰度的擬合優(yōu)度的檢驗。

構造JB統(tǒng)計量[13]：

本文的3個網絡時間節(jié)點時差噪聲序列的JB統(tǒng)計結果如表3所示。其中是判斷該檢驗是否接受原假設的值，當=0時，認為數(shù)據(jù)服從正態(tài)分布，接收原假設；當=1時，則拒絕原假設，認為數(shù)據(jù)不服從正態(tài)分布。，JBSTAT和CV分別指檢驗的概率值、檢驗統(tǒng)計量的值和判斷是否拒絕原假設的關鍵值。由于各個殘差序列的JB統(tǒng)計結果均在顯著性水平0.05時拒絕正態(tài)分布假設，因此，網絡節(jié)點時鐘的噪聲是非正態(tài)的，需要進一步討論和分析。

表3 節(jié)點時鐘偏差殘差JB統(tǒng)計量檢驗結果（顯著性水平α = 0.05）

3.2 時差噪聲的分形特征

① 計算均值：

圖3 網絡節(jié)點時鐘偏差的分析結果

其中，3個網絡節(jié)點時鐘晶振噪聲的Hurst指數(shù)線性擬合表達式為

式（27）的計算結果表明，3個網絡節(jié)點時鐘晶振噪聲序列的Hurst指數(shù)均大于0.5，具有分形特性，是分形序列。

由式（10）可知，這3個噪聲序列的傅里葉頻譜指數(shù)分別為：2.984 0、2.997 2和2.984 6。將這些計算結果代入式（15），即可對Kalman濾波的協(xié)方差矩陣進行估計。

通過上述分析，得到了網絡節(jié)點時鐘模型、Kalman濾波算法以及分形特征參數(shù)。其中，分形特性可以用來估計Kalman濾波的協(xié)方差矩陣，從而提高濾波算法效率。

4 仿真分析

本文通過軟件Matlab來進行移動自組織網絡的時間同步算法的仿真驗證，網絡節(jié)點時鐘的本振頻率為10 MHz，仿真時間為180 s，同步周期設置為1 s[19]。通過仿真可以得到卡爾曼濾波前的時鐘偏差情況，其結果如圖4所示。

圖4 卡爾曼濾波前的時鐘偏差

從圖4可以看到卡爾曼濾波前的時鐘偏差是隨機抖動的，通過分析可知，時鐘偏差的均值和方差分別為5.051 4×10-6s和1.229 6×10-13s?？柭鼮V波后的時鐘偏差情況，其結果如圖5所示。

圖5 卡爾曼濾波后的時鐘偏差

從圖5可以看到卡爾曼濾波后的時鐘偏差也是隨機的，對仿真數(shù)據(jù)進行分析可知，時鐘偏差的均值和方差分別為2.375 7×10-8s和1.363 8×10-13s。

通過仿真分析與計算，可以看出使用卡爾曼濾波使得節(jié)點的時鐘偏差得到了明顯的改善，對時鐘系統(tǒng)狀態(tài)模型進行調整，使得節(jié)點間實現(xiàn)時間同步。

5 結語

本文對建立的Ad Hoc網絡的節(jié)點時鐘模型進行了數(shù)學描述，利用分形方法對網絡節(jié)點時鐘噪聲進行分析和研究。為了對節(jié)點時鐘的噪聲狀態(tài)進行描述，采用Kalman濾波方法對時鐘噪聲序列特征進行分析，其中包括了時差序列獲取和噪聲序列的非正態(tài)性分析?；诜中翁卣鞣治鼋Y果，估計Kalman濾波的協(xié)方差矩陣，從而提高了濾波算法效率。通過Matlab對文中的基于Kalman濾波算法對Ad Hoc網絡節(jié)點間同步精度進行仿真，結果表明該算法能明顯降低網絡節(jié)點間的時鐘偏差，基于該模型實現(xiàn)了Ad Hoc網絡節(jié)點間的高精度時間同步，同步精度優(yōu)于25 ns。

[1] ZHENG S R, WANG H T, ZHAO Z F, et al. Ad Hoc networks technology[M]. Beijing: Posts & Telecom Press, 2005.

[2] 楊海東, 鄧勇.Ad Hoc網絡時間同步技術研究[J]. 計算機工程與設計, 2008, 29(21): 5447-5450.

[3] GANERIWAL S, KUMAR R, SRIVASTAVA M B. Timing-syncprotocol for sensor networks[C] // SenSys’03: Proceedings of the1st International Conference on Embedded Networked Sensor Systems, New York: ACM, 2003: 138-149.

[4] 李文鋒, 王汝傳, 孫力娟. 基于RBS的無線傳感器網絡時間同步算法[J]. 通信學報, 2008, 29(6): 82-86.

[5] 葉玲, 李太華, 代學武. 無線傳感器網絡環(huán)境下基于卡爾曼濾波的PTP協(xié)議[J]. 智能系統(tǒng)學報, 2012, 7(6): 518-524.

[6] ELSON J, GIROD L, ESTRIN D. Fine-grained network time synchronization using reference broadcasts[J]. ACM SIGOPS Operating Systems Review, 2002, 36(1): 147-163.

[7] CHEN L, LENEUTRE J. Toward secure and scalable time synchronization in Ad Hoc networks[M]. Elsevier Science Publishers B: Computer Communications, 2007.

[8] 宋曉雪. 無線自組織網絡時間同步技術研究[D]. 成都: 電子科技大學, 2018.

[9] 袁海波, 武福平, 董紹武. 原子鐘信號主要噪聲類別的判定與分析[J]. 儀器儀表學報, 2008, 29(8): 187-191.

[10] 郭海榮, 郭樹人, 焦文海, 等. 原子鐘時域頻率穩(wěn)定性計算方法[J]. 飛行器測控學報, 2007, 26(2): 47-52.

[11] 張敏. 原子鐘噪聲類型和頻率穩(wěn)定度估計的自由度分析與探討[D]. 西安: 中國科學院國家授時中心, 2008.

[12] 陳伊卿. 無線傳感器網絡時間同步算法研究[D]. 西安: 西安電子科技大學, 2011.

[13] HUANG G, ZOMAYA A Y, DELICATO F C. An accurate on-demand time synchronization protocol for wireless sensor networks[J]. Journal of Parallel & Distributed Computing, 2012, 72(10): 1332-1346.

[14] MAKARAVA N, HOLSCHNEIDER M. Estimation of the Hurst exponent from noisy data: a Bayesian approach[J]. The European Physical Journal B, 2012, 85(8): 272-471.

[15] 顧仁財, 劉飛. 自適應Kalman濾波的戰(zhàn)術數(shù)據(jù)鏈自主時間同步算法[J]. 火力與指揮控制, 2019, 44(2): 76-79.

[16] 莊曉燕, 王厚軍. 基于卡爾曼濾波器的IEEE 1588時鐘同步算法[J]. 電子測量與儀器學報, 2012, 26(9): 747-751.

[17] SARANN L, CATHERINE C, AURORE D. Different methods for spatial interpolation of rainfall data for operational hydrology and hydrological modeling at watershed scale. A review[J]. Biotechnology Agronomy Society & Environment, 2013, 17(2): 392-406.

[18] HASAN M K, SAEED R A, HASHIM A H A, et al. Femtocell network time synchronization protocols and schemes[J]. Research Journal of Applied Science, Engineering and Technology, 2012, 4(23): 5136-5143.

[19] 胡愛華, 鄧中亮, 張耀. 基于改進TPSN和卡爾曼濾波的時間同步算法[J]. 現(xiàn)代電子技術, 2018, 41(13): 5-9.

Study on time synchronization algorithm of Ad Hoc networks based on Kalman filter

SUN Li1,2,3, ZOU De-cai1,2,4, HAN Tao5

(1. National Time Service Center, Chinese Academy of Sciences, Xi’an 710600, China;2. Key Laboratory of Precise Positioning and Timing Technology, Chinese Academy of Sciences, Xi’an 710600, China;3. University of Chinese Academy of Sciences, Beijing 100049, China;4. School of Astronomy and Space Science, University of Chinese Academy of Sciences, Beijing 101048, China；5.Faculty of Sciences, Xi’an University of Technology, Xi’an 713300, China)

In this study, the clock model of the Ad Hoc network node is established, the Kalman filter algorithm which suitable for the network node clock model is designed, the covariance matrix of the Kalman filter is estimated using the fractal characteristics of the time difference noise, and the characteristics of the clock noise sequence are analyzed. The simulation results shown that the filtering algorithm not only can improve the efficiency, but also can significantly reduce the clock deviation between network nodes, and achieveshigh-precision time synchronization between Ad Hoc network nodes. The accuracy of synchronization is better than 25 ns.

Ad Hoc; network node; fractal characteristics; Kalman filter

10.13875/j.issn.1674-0637.2020-04-0279-09

孫力, 鄒德財, 韓濤. 基于卡爾曼濾波的Ad Hoc網絡節(jié)點間時間同步算法研究[J]. 時間頻率學報, 2020, 43(4): 279-287.

2020-04-17；

2020-05-06

載人航天創(chuàng)新性預研資助項目（17680601）