葉玲，李太華，代學(xué)武

(西南大學(xué)電子信息工程學(xué)院，重慶400715)

保持節(jié)點之間時間上的同步在分布式系統(tǒng)中具有十分關(guān)鍵的地位，是保證各節(jié)點協(xié)同工作，處理數(shù)據(jù)正確和信息傳輸可靠的前提.時間同步(time synchronization)是一個將各分布式節(jié)點上的時鐘對準的過程，其目的是把各節(jié)點和設(shè)備的時鐘偏差限定在足夠小的范圍內(nèi).作為分布式系統(tǒng)的一個重要分支，無線傳感器網(wǎng)絡(luò)的很多應(yīng)用依賴于時間同步［1］，比如數(shù)據(jù)融合、TDMA 調(diào)度、基于 TOF(time of flight)定位技術(shù)［2］、面向波束成形(beam forming)的多節(jié)點協(xié)同技術(shù)［3］等.無線傳感器網(wǎng)絡(luò)具有能量受限、計算能力低、通信容量低等特點［4］.無線網(wǎng)絡(luò)節(jié)點的時鐘通常是通過本地的晶振和中斷機制來實現(xiàn)的，受制造誤差、溫度變化、CPU處理延遲等影響較明顯.因此，實施高精度的時間同步算法是一項具有挑戰(zhàn)性的工作.

目前在數(shù)據(jù)包交換網(wǎng)絡(luò)中，廣泛使用的時間同步算法主要采用時間信息包交換技術(shù)，其研究的內(nèi)容主要是如何通過時間信息的交換來提高不夠精確的時鐘的精確度，比如因特網(wǎng)上廣泛采用的NTP協(xié)議、針對工業(yè)以太網(wǎng)的IEEE 1588 PTP等.針對無線傳感器網(wǎng)絡(luò)已陸續(xù)出現(xiàn)多種時間同步協(xié)議，主要可以分為以下幾類:1)基于發(fā)送者—接收者的雙向同步，典型算法如 TPSN［5］(timing-sync protocol for sensor networks)算法;2)基于發(fā)送者—接收者的單向時間同步，如 FTSP［6］(flooding time synchronization protocol)算法和 DMTS［7］(delay measurement time synchronization)算法;3)基于接收者—接收者的同步算法，如 RBS(reference broadcast synchronization)［8］算法.但它們未能在能效和精度上進行充分的優(yōu)化［9］.針對有線包交換網(wǎng)絡(luò)，已經(jīng)形成了一個IEEE 1588精確時間同步協(xié)議(precision time synchronization protocol，PTP)標準［10］.在一定條件下，其時間同步的精度可以控制在微秒范圍內(nèi)，該同步的精度遠高于基于 NTP時間同步協(xié)議.相比于FTSP等時間同步協(xié)議，由于PTP操作簡單、對帶寬的要求相對較低，更適合于通信帶寬和能量受限的無線傳感器網(wǎng)絡(luò)設(shè)備.上述特點使其在同步精度和功耗上能夠?qū)崿F(xiàn)較好的平衡.但由于IEEE1588 PTP協(xié)議是針對有線網(wǎng)絡(luò)提出的，如何將PTP運用于無線傳感器網(wǎng)絡(luò)以提高無線網(wǎng)絡(luò)的時間同步精度尚未有定論，國際和國內(nèi)相關(guān)的工作才剛剛展開.因此本文重點研究如何利用卡爾曼濾波器在無線傳感器網(wǎng)絡(luò)中實現(xiàn)高精度的時間同步.

時間同步的本質(zhì)是一個用通信帶寬和計算功耗換時間精度的問題，受到通信延遲抖動(與通信帶寬相關(guān))和時間戳精度(與CPU處理能力相關(guān))的影響很大.基于時間信息包交換的時間同步過程涉及2個方面:有偏差的物理時鐘和時間信息交換協(xié)議(即時間同步算法).為了更好地研究時間同步，需要對物理時鐘和時間信息交換分別進行建模.時鐘模型主要有2種比較典型的方案:1)采用基于時鐘振蕩器物理特征的差分方程進行描述［11］.在真實的無線傳感器網(wǎng)絡(luò)中，節(jié)點時鐘頻率漂移在不同時期服從不同規(guī)律.因此該方案的關(guān)鍵是獲取差分方程模型的參數(shù).2)采用一階高斯馬爾可夫鏈模型，也稱一階自回歸模型(autoregressive，AR)來描述時變的時鐘漂移［12］.

本文嘗試將PTP協(xié)議用于無線傳感器網(wǎng)絡(luò)，主要研究PTP時間同步精度與時鐘戳的不確定性和延遲抖動之間的數(shù)量關(guān)系.利用AR時鐘模型構(gòu)建時鐘的狀態(tài)轉(zhuǎn)移方程，將PTP協(xié)議建模為一組觀測方程，然后基于卡爾曼濾波器對時鐘偏移(offset)和時鐘偏移率(skew)進行跟蹤，以提高PTP同步協(xié)議在無線傳感器網(wǎng)絡(luò)的時間同步的性能.

1 系統(tǒng)建模

1.1 時鐘模型

時鐘建模使用狀態(tài)轉(zhuǎn)移方程組來描述網(wǎng)絡(luò)節(jié)點自身的本地(物理)時鐘變化規(guī)律，而物理時鐘通常有偏差且不精確.如圖1所示，橫坐標表示基準時間(或全局時間)t，縱坐標表示一個節(jié)點有誤差的本地時間C(t).C(t)具有分段線性特征，除在可數(shù)點集P?R(集合P表示時鐘參數(shù)發(fā)生改變的情況)外二次可導(dǎo)的函數(shù)，即dC2(t)/dt2在t?P時總是存在的.C(t)可表示為

式中:θ0為時鐘偏移的初始值，dC(t)/dt為時鐘變化率，也稱作時鐘變化頻率偏移，描述了本地時鐘的頻率.理想情況下，精確時鐘C(t)=t，其時鐘變化率為dC(t)/dt=1且P=?.

圖1 時鐘漂移模型Fig.1 Clock model

在此后的論述中，用TM(t)=t來表示精確時鐘，即主時鐘或全局時鐘.時鐘偏移θ用來描述本地時鐘C(t)和全局時鐘 TM(t)之間的差值，θ=TM(t)－C(t).時鐘偏移率 α=1－dC(t)/dt，描述了本地時鐘頻率和全局時鐘頻率之間的差異.

本地軟件時鐘模型主要描述軟件時鐘和物理時鐘的關(guān)系，常用模型是:軟件時鐘對硬件時鐘值作仿射變換，硬件時鐘是只讀的，即不能更改硬件時鐘速率.不同的軟硬件配置有不同的軟件時鐘模型.本文中軟件時鐘的值是把物理時鐘的值根據(jù)θ和α來修正后得到的.

由于時鐘偏移率α通常會受溫度等環(huán)境因素影響，但比較緩慢，通常可以假設(shè)在一個較小的時間間隔內(nèi)，α是不變的.因此，通過離散化處理，連續(xù)時鐘模型(1)可轉(zhuǎn)化為一組離散時間域上的狀態(tài)轉(zhuǎn)移方程:

式中:θ0是初始時鐘漂移(即t=0時刻的時鐘漂移值)，α［i］是時間段 τ［i］內(nèi)的時鐘偏移率(0≤i≤k－1)，ψθ［k］是瞬時的時鐘偏移波動 ωθ［k］的累積和，即 ψθ［k+1］= ψθ［k］+ ωθ［k］.將式(2)寫成遞歸的形式，則時鐘偏移的狀態(tài)轉(zhuǎn)移方程為

根據(jù)文獻［12］，時鐘偏移率的變化可以用一個AR過程來描述，于是α的狀態(tài)轉(zhuǎn)移方程為

式中:τ［k］為時間同步間隔(即2次同步之間的時間間隔)，本文中假定為固定不變，即τ［k］=ΔT;ωθ［k］代表時鐘偏移的白噪聲;ωα［k］代表時鐘偏移率的噪聲(白頻率噪聲).ωθ［k］和 ωα［k］是 2 個不相關(guān)的高斯白噪聲過程，方差分別為和.

1.2 PTP時間同步協(xié)議模型

PTP協(xié)議［10］是一種主從時鐘同步協(xié)議，其基本原理是:從節(jié)點通過與主節(jié)點交換包含時間標記的時間信息包，計算出主從節(jié)點之間的時鐘偏移θ，從而估計出主節(jié)點的時間，并調(diào)整從節(jié)點的本地時鐘使其與主時鐘保持同步.PTP中的時間標記信息包交換過程如圖2所示.

圖2中t1和t2為一次同步中主從時鐘記錄下的時間標記，t3和t4為緊接著的一次Delay_Req請求報文傳輸過程中，從時鐘和主時鐘記錄下的時間標記.考慮到主從之間數(shù)據(jù)包的傳輸延遲，它們之間的關(guān)系如下:

式中:k代表第k次時間同步過程，dms代表數(shù)據(jù)包從主時鐘到從時鐘的傳播時延，dsm代表數(shù)據(jù)包從從時鐘到主時鐘的傳播時延.將主從時鐘間的時鐘偏移θ看作待求解未知量，解方程組(5)，可得到

式(5)描述了時間同步協(xié)議中時間標記信息包交換過程中主從時間標記之間的關(guān)系.式(6)是時鐘偏移的觀測方程，描述了如何從時間信息包交換中“測量”出主從時鐘偏移.

圖2 PTP協(xié)議時間標記包交換過程Fig.2 Timing diagram of message exchange by PTP

在PTP時間同步協(xié)議中，傳輸時延假定對等，即dsm=dms.但實際網(wǎng)絡(luò)中由于無線介質(zhì)的共享、沖突退避和重發(fā)等因素，數(shù)據(jù)包的傳輸時延不會相等，即dsm≠dms.在這里，將傳輸延遲的不對等性可以用延遲抖動來描述，即把傳輸時延dsm和dms看作一個均值為d、方差為的高斯隨機過程N(d，σd)的2次取值.令 Δd=(dsm－dms)/2，計算 θ的式(6)可寫為

式中:Δd描述了傳輸延遲的不對稱性，Δd是一個均值為0，方差為1/2×的高斯隨機變量.進一步考慮由于嵌入式系統(tǒng)中斷處理延遲等所造成時間戳的不確定性，在主從時鐘的觀測值ti中，同樣存在時鐘值讀取誤差 Δti(i=1，2，3，4)，Δt1和 Δt4是主時鐘的蓋戳的不確定性，Δt2和Δt3是從時鐘的蓋戳的不確定性.于是θ的觀測方程為

式中:vθM代表θ的觀測噪音，定義為

觀測噪音 vθM是時間標記誤差 Δti(i=1，2，3，4)與傳輸延遲不對稱性Δd之和.假設(shè)時間標記的不確定性是零均值的獨立隨機變量是 Δt1和Δt4的方差是 Δt2和 Δt3的方差，則 vθM的方差是各個獨立隨機變量的方差之和:

因為Δt2和Δt3的均值不為零(時間延遲始終是個正數(shù))，故vθM的均值不為0，而是Δt2和Δt3的平均值相加.假定在一個同步周期τ［k］內(nèi)恒定不變，則時鐘偏移率α［k］可以從θ的觀測值中計算出來，α［k］的觀測方程為

同理，可以得到αM［k］的觀測噪音的方差為

注意，由于αM［k］是從θ的觀測值得到的，觀測噪音 vαM與 vθM相耦合，它們的協(xié)方差為

2 基于卡爾曼濾波器的時間同步

假設(shè)基于主從時鐘包交換所獲取的時間信息是絕對精確且可靠的，則如第1部分所述的關(guān)于時鐘偏移和時鐘偏移率的觀測值可直接用于矯正本地時鐘，以實現(xiàn)時間同步.然而，由于主從時鐘包交換過程中存在著各種不確定因素，期間獲取的時間信息通常是不精確且不可靠的.因此，需要通過濾波器技術(shù)對其進行預(yù)處理.在第1部分已經(jīng)建立的遞歸時鐘模型和同步協(xié)議模型的基礎(chǔ)上，可以利用卡爾曼濾波器方程實現(xiàn)遞歸估計器.

基于這一目的，正如第1部分所述，從式(7)和式(8)可以得到觀測方程:

將狀態(tài)轉(zhuǎn)移方程(3)、(4)和觀測方程(9)寫成矩陣形式，可建立時鐘同步的狀態(tài)空間模型:

式(10)分別稱為時鐘狀態(tài)方程和觀測方程.式中:x［k］=［θ［k］ α［k］］T為第 k 輪時鐘狀態(tài)向量;y［k］=［θM［k］ αM［k］］T為第 k 輪時鐘觀測向量;，為狀態(tài)轉(zhuǎn)移矩陣為測量系統(tǒng)的參數(shù)矩陣，它將真實狀態(tài)空間映射到觀測空間;=［vθM［k］ vαM［k］］T分別表示過程噪聲和觀測噪聲，ω［k］服從 N(0，Q)正態(tài)分布，v［k］服從N(0，R)正態(tài)分布，且兩噪聲的各樣本間均相互獨立.v［k］的零均值假設(shè)在實際系統(tǒng)中并不一定成立，v［k］的均值同樣是一個與發(fā)送節(jié)點、接收節(jié)點相關(guān)的變量，盡管如此，在v［k］均值未知的情況下對其進行零均值的假設(shè)是開展卡爾曼濾波所要求的條件，而零均值的假設(shè)所引入的誤差最終將體現(xiàn)在時鐘同步誤差的均值上.在這里，設(shè)定

由此，卡爾曼濾波器的迭代算法過程可以描述成如式(11)、(12):

式(13)～(15)為更新過程:

3 實驗結(jié)果分析

在這一部分，基于不同觀測噪聲條件，主要分析主從時鐘之間，時鐘偏移和時鐘偏移率估計誤差平均值和標準差的變化趨勢.

在仿真實驗中，時鐘模型(式(3)、(4))用來仿真不精確時鐘，最小步長是10－6s，遠遠小于時鐘同步周期ΔT(在仿真實驗中ΔT=0.1 s)，ΔT同樣是卡爾曼濾波器進行迭代算法的周期.

對于時間同步的精確度的衡量，采用了時鐘偏移的估計誤差和時鐘扭曲率估計誤差這2項指標，分別用估計誤差的均值和估計誤差的方差來表示.

圖3、4反應(yīng)了在不同σSTS取值下，主從時鐘在時鐘偏移(offset)和時鐘偏移率(skew)估計誤差均值的變化趨勢，體現(xiàn)了時鐘可靠性的變化規(guī)律.

圖3 時鐘偏移估計誤差的平均值Fig.3 Offset estimation error mean

圖4 時鐘偏移率估計誤差的平均值Fig.4 Skew estimation error mean

由圖3可知，隨著時間標記不確定性的增加，時鐘偏移估計誤差均值在2種算法模式下均呈現(xiàn)增加趨勢，但基于卡爾曼濾波器的PTP算法的均值明顯小于無卡爾曼濾波器的PTP算法.針對不同的時鐘類型，可以看出相對穩(wěn)定時鐘，在不同算法模式下其估計誤差均值均低于相對不穩(wěn)定時鐘.但同樣可以看出同一時鐘在2種算法模式下，當時間標記不確定性很小時，時鐘偏移估計誤差均值差別不顯著，但隨著時間標記不確定性增大，基于卡爾曼濾波器伺服的PTP算法的優(yōu)勢則十分顯著.

由圖4知，隨著時間標記不確定性的增加，時鐘偏移率估計誤差均值在無卡爾曼濾波器的算法模式下呈現(xiàn)顯著增大趨勢，但在基于卡爾曼濾波器的PTP算法模式下，估計誤差均值則表現(xiàn)出相對的穩(wěn)定性，且明顯小于無卡爾曼濾波器的PTP算法.針對不同的時鐘類型，可以看出相對穩(wěn)定時鐘，在不同算法模式下其估計誤差均值均低于相對不穩(wěn)定時鐘.

由圖5可知，隨著時間標記不確定性的增加，時鐘偏移估計誤差的標準差在2種算法模式下均呈現(xiàn)增加趨勢，但基于卡爾曼濾波器的PTP算法的標準差明顯小于無卡爾曼濾波器伺服的PTP算法.針對不同的時鐘類型，可以看出，相對穩(wěn)定時鐘，在不同算法模式下其估計誤差的標準差均低于相對不穩(wěn)定時鐘.但同樣可以看出，同一時鐘在2種算法模式下，當時間標記不確定性很小時，時鐘偏移(offset)估計誤差的標準差差別不顯著，但隨著時間標記不確定性增大，基于卡爾曼濾波器的PTP算法的優(yōu)勢顯著.

圖5 時鐘偏移估計誤差的標準差Fig.5 Offset estimation error standard deviation

由圖6可知，隨著時間標記不確定性的增加，時鐘偏移率估計誤差的標準差在無卡爾曼濾波器的模式下呈現(xiàn)顯著增大趨勢，但在基于卡爾曼濾波器的PTP模式下，估計誤差的標準差則表現(xiàn)出相對的穩(wěn)定性，且明顯小于無卡爾曼濾波器伺服的PTP算法.針對不同的時鐘類型，可以看出相對穩(wěn)定時鐘，在不同算法模式下其估計誤差的標準差均低于相對不穩(wěn)定時鐘.值得注意的是，圖6中時鐘偏移率估計誤差的標準差在前一段存在一變小趨勢，這需要更加精確的理論推導(dǎo)證明.

圖6 時鐘偏移率估計誤差的標準差Fig.6 Skew estimation error standard deviation

主從時鐘時鐘偏移和時鐘偏移率估計誤差均值和標準差反映了時鐘同步算法的精度和穩(wěn)定性.綜合圖3～6可知，基于卡爾曼濾波器的PTP時鐘同步算法對主從時鐘在時鐘偏移和時鐘偏移率的估計，無論是精度還是穩(wěn)定性，均優(yōu)于無卡爾曼濾波器的PTP時鐘同步算法.但是，當觀測噪聲比較小，即從時鐘時間標記不確定性非常小時(比如，σSTS=10－8s)，基于卡爾曼濾波器的PTP時鐘同步算法優(yōu)勢不顯著，而隨著觀測噪聲逐步增大時，基于卡爾曼濾波器的PTP時鐘同步算法優(yōu)勢則愈發(fā)顯著.因此，基于卡爾曼濾波器的PTP時鐘同步算法比較適用于觀測噪聲較大的應(yīng)用中.標準的無線傳感器網(wǎng)絡(luò)節(jié)點時鐘之間標記不確定性的標準差σSTS在10－5左右［15］.由圖3～6可以看出，當觀測噪聲處于這一量級時，基于卡爾曼濾波器的PTP時鐘同步算法優(yōu)勢已十分顯著.因此，基于卡爾曼濾波器的PTP時鐘同步算法適用于無線傳感器網(wǎng)絡(luò)的應(yīng)用.

根據(jù)仿真實驗結(jié)果(圖3～6)可知，穩(wěn)定性不同的2類時鐘，在2種不同時鐘同步算法模式下，當觀測噪聲較小時，比如σSTS≤10－5時，相對穩(wěn)定的時鐘的時鐘同步精度和穩(wěn)定性均優(yōu)于相對不穩(wěn)定的時鐘.但是當觀測噪聲較大時，比如σSTS＞10－5時，則相對穩(wěn)定的時鐘的時鐘同步精度和穩(wěn)定性相對不穩(wěn)定的時鐘雖有優(yōu)勢，但趨于不顯著，特別是在無卡爾曼濾波器的PTP時鐘同步算法模式下.因此，可以得出結(jié)論，當觀測噪聲較大時，選擇具有高穩(wěn)定度(往往價格更高)時鐘的無線傳感器網(wǎng)絡(luò)節(jié)點已無必要.

4 結(jié)束語

本文對基于卡爾曼濾波器的PTP時間同步算法進行了理論分析、建模和仿真，并與無卡爾曼濾波的PTP時間同步算法就時鐘估計誤差精度和穩(wěn)定性進行比較研究.實驗結(jié)果顯示，基于卡爾曼濾波器的時間同步算法在精度和穩(wěn)定性上有明顯的優(yōu)勢，并為在真實物理環(huán)境中配置無線傳感器網(wǎng)絡(luò)提供了參考，比如在不同噪聲環(huán)境下，節(jié)點時鐘精度的選擇等.

［1］SUNDARARAMAN B，BUY U，KSHEMKALYANI A D.Clock synchronization for wireless sensor networks:a survey［J］.Ad Hoc Networks，2005，3(3):281-323.

［2］CAPKUN S，CAGALJ M，SRIVASTAVA M.Secure localization with hidden and mobile base stations［C］//Proceedings of 25th IEEE International Conference on Computer Communications.Barcelona，Spain，2006:1-10.

［3］MUDUMBAI R，BARRIAC G，MADHOW U.On the feasibility of distributed beamforming in wireless networks［J］.IEEE Transactions on Wireless Communications，2007，6(5):1754-1763.

［4］LIU Q，LIU X，ZHOU J，et al.Adasynch:a general adaptive clock synchronization scheme based on Kalman filter for WSNs［J］.Wireless Personal Communications，2012，63(1):217-239.

［5］GANERIWAL S，KUMAR R，SRIVASTAVA M B.Timingsync protocol for sensor networks［C］//The First ACM Conference on Embedded Networked Sensor System.New York，USA，2003:138-149.

［6］MAROTI M.The flooding time synchronization protocol［C］//Proc 2nd ACM Conf Embedded Networked Sensor Systems.New York，USA，2004:39-49.

［7］PING S.Delay measurement time synchronization for wireless sensor networks IRB-TR-03-013［R］.Berkeley:Intel Research，2003.

［8］ELSON J，GIROD L，ESTRIN D.Fine-gained network time synchronization using reference broadcasts［C］//Proc fifth Symposium on Operating Systems Design and Implementation.New York，USA，2002:147-163.

［9］ZENG Y，HU B，LIU S.Vector Kalman filter using multiple parents for time synchronization in multi-hop sensor networks［C］//Proc of the IEEE SECON.San Francisco，USA，2008:413-421.

［10］EIDSON J C，F(xiàn)ISCHER M，WHITE J.IEEE 1588 standard for a precision clock synchronization protocol for networked measurement and control systems［S］//IEC 61588(E):2004-IEEE Std.1588(E)，2002.

［11］GALLEANI L，SACERDOTE L，TAVELLA P，et al.A mathematical model for the atomic clock error［J］.Metrologia，2003，40(3):257-264.

［12］HAMITON B R，MA X，ZHAO Q，et al.Aces:adaptive clock estimation and synchronization using Kalman filtering［C］//Proceedings of the 14th ACM International Conference on Mobile Computing and Networking.New York，USA，2008:152-162.

［13］ABUBAKARI H，SASTRA S.IEEE 1588 style synchronization over wireless link［C］//Proc IEEE ISPCS.Ann Arbor，USA，2008:127-130.

［14］BARENDT N，CORRELL K，BRANICKY M.Servo design considerations for software-only implementations of the precision time protocol［C］//ISPCS.Zurich，Switzerland，2005:10-12.

［15］SAVVIDES A，HAN C，SRIVASTAVA M.Dynamic finegrained localization in ad-hoc networks of sensors［C］//Proceedings of the 7th Annual International Conference on Mobile Computing and Networking.New York，USA，2001:166-179.