孫力，鄒德財(cái)，韓濤

基于卡爾曼濾波的Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)間時(shí)間同步算法研究

孫力1,2,3，鄒德財(cái)1,2,4，韓濤5

（1. 中國(guó)科學(xué)院 國(guó)家授時(shí)中心，西安 710600；2. 中國(guó)科學(xué)院 精密導(dǎo)航定位與定時(shí)技術(shù)重點(diǎn)實(shí)驗(yàn)室，西安 710600；3. 中國(guó)科學(xué)院大學(xué)，北京 100049；4. 中國(guó)科學(xué)院大學(xué) 天文與空間科學(xué)學(xué)院，北京 101048；5.西安理工大學(xué) 理學(xué)院，西安 713300）

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

Ad Hoc；網(wǎng)絡(luò)節(jié)點(diǎn)；分形特性；Kalman濾波

0 引言

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

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

圖1 Ad Hoc網(wǎng)絡(luò)架構(gòu)圖

1 Ad Hoc網(wǎng)絡(luò)時(shí)間同步算法

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

表1 網(wǎng)絡(luò)時(shí)間同步算法

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

2 Ad Hoc網(wǎng)絡(luò)時(shí)鐘模型

式（5）中

那么，離散的時(shí)鐘模型可以表示為

3 Ad Hoc網(wǎng)絡(luò)時(shí)鐘模型的Kalman濾波方法

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

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

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

則：

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

3.1 時(shí)鐘噪聲序列特征分析

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

3.1.1 時(shí)差序列獲取

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

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

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

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

圖2 3個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)晶振時(shí)差序列頻數(shù)統(tǒng)計(jì)直方圖

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

構(gòu)造JB統(tǒng)計(jì)量[13]：

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

表3 節(jié)點(diǎn)時(shí)鐘偏差殘差JB統(tǒng)計(jì)量檢驗(yàn)結(jié)果（顯著性水平α = 0.05）

3.2 時(shí)差噪聲的分形特征

① 計(jì)算均值：

圖3 網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)鐘偏差的分析結(jié)果

其中，3個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)鐘晶振噪聲的Hurst指數(shù)線性擬合表達(dá)式為

式（27）的計(jì)算結(jié)果表明，3個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)鐘晶振噪聲序列的Hurst指數(shù)均大于0.5，具有分形特性，是分形序列。

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

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

4 仿真分析

本文通過(guò)軟件Matlab來(lái)進(jìn)行移動(dòng)自組織網(wǎng)絡(luò)的時(shí)間同步算法的仿真驗(yàn)證，網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)鐘的本振頻率為10 MHz，仿真時(shí)間為180 s，同步周期設(shè)置為1 s[19]。通過(guò)仿真可以得到卡爾曼濾波前的時(shí)鐘偏差情況，其結(jié)果如圖4所示。

圖4 卡爾曼濾波前的時(shí)鐘偏差

從圖4可以看到卡爾曼濾波前的時(shí)鐘偏差是隨機(jī)抖動(dòng)的，通過(guò)分析可知，時(shí)鐘偏差的均值和方差分別為5.051 4×10-6s和1.229 6×10-13s。卡爾曼濾波后的時(shí)鐘偏差情況，其結(jié)果如圖5所示。

圖5 卡爾曼濾波后的時(shí)鐘偏差

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

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

5 結(jié)語(yǔ)

本文對(duì)建立的Ad Hoc網(wǎng)絡(luò)的節(jié)點(diǎn)時(shí)鐘模型進(jìn)行了數(shù)學(xué)描述，利用分形方法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)鐘噪聲進(jìn)行分析和研究。為了對(duì)節(jié)點(diǎn)時(shí)鐘的噪聲狀態(tài)進(jìn)行描述，采用Kalman濾波方法對(duì)時(shí)鐘噪聲序列特征進(jìn)行分析，其中包括了時(shí)差序列獲取和噪聲序列的非正態(tài)性分析。基于分形特征分析結(jié)果，估計(jì)Kalman濾波的協(xié)方差矩陣，從而提高了濾波算法效率。通過(guò)Matlab對(duì)文中的基于Kalman濾波算法對(duì)Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)間同步精度進(jìn)行仿真，結(jié)果表明該算法能明顯降低網(wǎng)絡(luò)節(jié)點(diǎn)間的時(shí)鐘偏差，基于該模型實(shí)現(xiàn)了Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)間的高精度時(shí)間同步，同步精度優(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網(wǎng)絡(luò)時(shí)間同步技術(shù)研究[J]. 計(jì)算機(jī)工程與設(shè)計(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的無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步算法[J]. 通信學(xué)報(bào), 2008, 29(6): 82-86.

[5] 葉玲, 李太華, 代學(xué)武. 無(wú)線傳感器網(wǎng)絡(luò)環(huán)境下基于卡爾曼濾波的PTP協(xié)議[J]. 智能系統(tǒng)學(xué)報(bào), 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] 宋曉雪. 無(wú)線自組織網(wǎng)絡(luò)時(shí)間同步技術(shù)研究[D]. 成都: 電子科技大學(xué), 2018.

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

[10] 郭海榮, 郭樹(shù)人, 焦文海, 等. 原子鐘時(shí)域頻率穩(wěn)定性計(jì)算方法[J]. 飛行器測(cè)控學(xué)報(bào), 2007, 26(2): 47-52.

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

[12] 陳伊卿. 無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步算法研究[D]. 西安: 西安電子科技大學(xué), 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] 顧仁財(cái), 劉飛. 自適應(yīng)Kalman濾波的戰(zhàn)術(shù)數(shù)據(jù)鏈自主時(shí)間同步算法[J]. 火力與指揮控制, 2019, 44(2): 76-79.

[16] 莊曉燕, 王厚軍. 基于卡爾曼濾波器的IEEE 1588時(shí)鐘同步算法[J]. 電子測(cè)量與儀器學(xué)報(bào), 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] 胡愛(ài)華, 鄧中亮, 張耀. 基于改進(jìn)TPSN和卡爾曼濾波的時(shí)間同步算法[J]. 現(xiàn)代電子技術(shù), 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

孫力, 鄒德財(cái), 韓濤. 基于卡爾曼濾波的Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)間時(shí)間同步算法研究[J]. 時(shí)間頻率學(xué)報(bào), 2020, 43(4): 279-287.

2020-04-17；

2020-05-06

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