多跳無線傳感器網絡下基于KF優化的PTP協議

楊玉景，黃藝文，李太華，代學武

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

作為分布式系統的重要組成部分，時間的同步是對時間敏感的工業無線網絡的關鍵支撐技術。時間同步[1]是解決無線傳感器網絡系統可靠性和穩定性難題的關鍵，是一個將所有節點各自不同的局部時間統一校準的過程。作為一種全新的信息獲取和處理技術，無線傳感器網絡[2]以其功耗低、成本低、分布式和自組織的特點帶來了一場信息感知的變革。其眾多應用都依賴于時間同步，如TDMA調度[3]、數據融合[4]、面向波束成形的多節點協同技術[5]、基于TOF(time of flight)定位技術[6]等。因此，獲取高精度的時間同步，改善同步性能，是無線傳感器網絡相關領域的研究熱點和難點。IEEE 1588 精確時間同步協議(precision time synchronization protocol，PTP)[7]，在一定條件下，其時間同步的精度可控制在微秒級，且操作簡單、對帶寬的要求相對較低，因此在同步精度和功耗上能夠較好地實現平衡，更適合應用在通信帶寬及能量受限的無線傳感器網絡設備上[8]。

本研究在先前的工作中已將PTP協議應用于無線傳感器網絡，同時采用卡爾曼濾波器(Kalman filter，KF)進行優化，以提高PTP協議在無線傳感器網絡下的時間同步性能。工作中主要分析了在單跳環境下PTP時間同步精度與時鐘戳的不確定性和延遲抖動之間的數量關系[9]。單跳仿真實驗結果顯示：相對于無KF優化的PTP協議，基于KF優化的PTP協議在同步精度和穩定性上均呈現明顯優勢。在實際網絡中，從節省能源及易于部署的角度出發，一般采用多跳網絡進行通信。在多跳無線傳感器網絡[10]中，各節點既可以是數據的終端節點，也可以成為網絡的路由節點。如何將PTP協議應用于多跳無線傳感器網絡以提高時間同步的精度有突破性的實際意義[11]。因此本文重點研究如何在多跳無線傳感器網絡下實現高精度的時間同步。

本文嘗試通過構建由5個節點組成的二跳同步網絡，從動力學角度出發，突破傳統以通信協議為研究核心的模式，通過采用狀態空間模型來描述時間同步的過程，將理論分析與軟件仿真相結合，進而利用均勻采樣和濾波技術來抑制觀測噪聲，以提高時間同步的精度，并應用于無線傳感器網絡中，以驗證基于KF優化的精確時間同步協議在多跳無線傳感器網絡中的拓展性和適應性。

1 多跳PTP時間同步協議模型

PTP協議[7]是不同節點時鐘間的同步協議，其基本原理是：子節點通過與父節點[12]交換包含時間標記信息的時間戳，計算出2級節點間的時鐘偏移θ，從而估計出父節點的時間，并調整子節點的本地時鐘使其與父節點的時鐘保持同步。PTP協議的時間戳交換過程如圖1所示。

圖1中t0和t1為一次同步中父時鐘與子時鐘的時間戳；t2和t3為緊接著的下一次延遲請求報文傳輸的過程中，子時鐘與父時鐘的時間戳。考慮到兩時鐘間傳輸時延的不對等性，定義：

(1)

式(1)描述了時間同步協議中時間戳交換過程中父子時鐘標記之間的關系。其中：k代表第k次的時間同步過程， dfs代表數據包從父時鐘到子時鐘的傳播時延，dsf代表數據包從子時鐘到父時鐘的傳播時延。

圖1 PTP協議時間戳交換過程Fig.1 Timing diagram of message exchange by PTP

將θ視為未知量，求解方程組(1)，可得：

(2)

式(2)描述了父子時鐘的時鐘偏移如何從時間戳的信息中獲取的過程，是時鐘偏移的觀測方程。

式中：Δd是均值為0且方差為σd2/2的高斯隨機變量，描述了傳輸時延的不對等性。由于在嵌入式系統中存在著中斷處理延遲等造成的時間戳的不確定性，因此在父子節點時鐘的觀測值ti(i=0,1,2,3)中，同樣存在著由于時鐘值讀取帶來的誤差Δti(i=0,1,2,3)。其中Δt0和Δt3是父時鐘時間戳標記的不確定性, Δt1和Δt2是子時鐘時間戳標記的不確定性。由此θ的觀測方程為

θF[k]=[(t1[k]-t0[k])-(t3[k]-t2[k])]/2+vθF

(3)

式中：vθF是θ的觀測噪音，定義為

vθF[k]=Δt1+Δt2/2-Δt0+Δt3/2+Δd

由于時間延遲始終是個正數，所以Δt1和Δt2的均值不為零，故vθF的均值也不為0，其值是Δt1和Δt2均值之和。假設在一個同步周期([k])內vθF保持不變，則時鐘偏移率[k]可以從式(4)中計算出來，故[k]的觀測方程為

(4)

同理得αF[k]的觀測噪音的方差：

需要注意的是，由于αF[k]是從θ的觀測值中得到的，所以觀測噪音vθF與vαF耦合，其協方差為

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

假設通過父子節點的同步信息包交換所獲取的時間戳信息是絕對精確可靠的，則如上所述，計算所得的時鐘偏移(offset)和時鐘偏移率(skew)的觀測值可以直接用于矯正子節點的本地時鐘，以實現節點間的時間同步。實際上，由于在同步信息包交換過程中存在著很多不確定性的因素，獲取得到的時間信息通常是不精確、不可靠的。因此，需要通過濾波器對其進行預處理。在已建立的同步協議模型的基礎上，再加以卡爾曼濾波器方程以實現遞歸估計器。

由式(3)和式(4)可以得到觀測方程：

(5)

將狀態轉移方程：

和觀測方程(5)寫成矩陣形式，以建立時鐘同步的狀態空間模型：

(6)

綜上，可用公式來描述卡爾曼濾波器的迭代算法過程，式(7)、(8)為預測過程式，式(9)、(10)、(11)為更新過程：

(7)

P(k|k-1)=AP(k-1)AT+R

(8)

K(k)=P(k|k-1)HT[HP(k|k-1)HT+S]-1

(9)

(10)

P(k)=[1-K(k)]P(k|k-1)

(11)

3 仿真實驗及結果分析

多跳同步原理如圖2所示。本實驗中，為更好的模擬真實情形，構造了由5個節點組成的二跳同步網絡，以驗證不同協議模式下的多跳同步性能。

在不同的觀測噪聲變化下，主要分析了父子時鐘之間時鐘偏移和時鐘偏移率的估計誤差平均值與標準差的變化趨勢。在如下的仿真實驗中，時鐘模型(式(6))是用來仿真不精確時鐘，其最小步長是10-6s，遠小于時鐘同步周期ΔΤ(ΔΤ=0.1 s)，ΔΤ同時也是KF進行迭代算法的周期。觀測噪聲(σSTS，即子時鐘做時間標記的不確定性)的變化區間為[10-8，10-4][13]，反應了不同時間標記機制所引起的時延。當σSTS較小時對應了基于硬件的時間標記，此情形下的offset主要受初始θ0和頻率偏移的影響；當σSTS較大時則對應于基于軟件的時間標記。衡量時間同步的精確度，則是通過時鐘偏移的偏移估計誤差和時鐘扭曲率估計誤差來衡量，在實驗中分別對應于估計誤差的均值和估計誤差的方差。

圖2 多跳同步拓撲結構Fig.2 Multi-hop synchronization topology

3.1 同步誤差實驗

兩跳同步誤差對比仿真實驗方案如表1所示。

表1 兩跳同步仿真實驗方案

圖3、圖4反映了隨觀測噪聲σSTS(即子節點時鐘標記不確定性的標準差)的變化，時鐘偏移和時鐘偏移率的估計誤差平均值，在4種方案下的變化趨勢。

圖3 時鐘偏移估計誤差的平均值 Fig.3 Means of clock offset estimation errors

由圖3可知，隨σSTS的增加，4種方案下的時鐘偏移估計誤差的均值變化均呈增加趨勢。但基于KF優化的PTP算法的均值明顯小于無KF優化的PTP算法。無KF優化的PTP算法，二跳子節點中offset的均值明顯大于一跳，且同步誤差的傳遞性較明顯。基于KF優化的PTP算法，二跳子節點中offset均值與一跳相差不大，且在一跳的均值上下呈現細微擺動，故其同步誤差的傳遞性不明顯。

圖4 時鐘偏移率估計誤差的平均值Fig.4 Means of clock skew estimation errors

由圖4可知，隨σSTS的增加，在無KF優化的PTP算法下子時鐘偏移率估計誤差的均值變化呈顯著增大趨勢，但在KF優化的PTP算法下，則表現出相對穩定的趨勢，其值明顯小于無KF優化的PTP算法。在無KF優化的PTP算法下，其二跳子節點中skew的均值大于一跳子節點的值，故同步估計誤差的傳遞性較明顯；基于KF優化的PTP算法，其二跳子節點中skew的均值略大于一跳子節點的值，故其估計誤差的傳遞性不明顯。

圖5、圖6反應了隨觀測噪聲(即σSTS的變化，時鐘偏移和時鐘偏移率同步估計誤差的標準差在4種方案下的變化趨勢。

圖5 時鐘偏移估計誤差的標準差Fig.5 Standard deviation of clock offset estimation errors

由圖5可知，隨σSTS的增加，4種方案下的時鐘偏移估計誤差的標準差均呈增加趨勢，但基于KF優化的PTP算法的值明顯小于無KF優化的PTP算法。無KF優化的PTP算法，二跳子節點中offset的標準差大于一跳，故其同步估計誤差的傳遞性較明顯。基于KF優化的PTP算法，二跳子節點中offset的標準差與一跳相差不大，故其同步估計誤差的傳遞性不明顯。

圖6 時鐘偏移率估計誤差的標準差Fig.6 Standard deviation of clock skew estimation errors

由圖6可知，隨σSTS的增加，時鐘偏移率估計誤差標準差在無KF優化下呈明顯增加趨勢。但在KF優化的PTP算法下，則呈相對穩定趨勢，明顯小于無KF優化的PTP 算法。無KF優化的PTP算法，二跳子節點中skew的標準差大于一跳同步子節點的值，且同步估計誤差的傳遞性較明顯；基于KF優化的PTP算法，二跳子節點中skew的標準差略大于對應一跳的值，故其同步估計誤差的傳遞性不明顯。

3.2 結果分析

上述實驗結果表明：在4種方案下，子節點的時鐘偏移和時鐘偏移率估計誤差的均值和標準差的變化趨勢反映了不同協議模式下的同步精度和穩定性的變化規律[14]。基于卡爾曼濾波器(KF)優化的PTP算法，其性能在精度和穩定性上均優于無KF優化的PTP算法，且在多跳同步中性能更優。

在多跳環境中，基于KF優化的PTP算法的時鐘偏移和時鐘偏移率的估計誤差在精度和穩定性上具有明顯優勢，能表現出較好的同步性能。當觀測噪聲較小(即σSTS時，基于KF優化的PTP算法在單跳網絡中的同步優勢不明顯，而在多跳網絡環境中，時間同步優勢明顯；隨觀測噪聲(即σSTS的逐步增大，基于KF優化的PTP算法在單跳和多跳同步中的優勢均顯著。由此可知，基于KF優化的PTP算法在觀測噪聲較大或同步跳數較多的無線傳感器網絡中能表現出良好的同步性能。由此說明，卡爾曼濾波器在同步過程中通過濾除同步噪聲的干擾，抑制同步誤差的傳遞，從而進一步有利于同步網絡的擴展。

4 結束語

通過對基于KF優化的PTP時間同步算法進行理論的分析、建模和仿真，并與單跳仿真結果對比分析可以得出如下實驗結論：在多跳同步網絡中，基于卡爾曼濾波器優化的精確時間同步協議，同步誤差控制在微秒級、誤差傳遞性較小且具有較好的穩定性，表現出優異的同步性能及良好的適應性并為在真實物理環境下配置無線傳感器網絡的相關參數提供了合理參考。

參考文獻:

[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]AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a survey[J]. Computer Networks， 2002， 38 (4): 393-422.

[3]WEI Zhu. TDMA frame synchronization of mobile stations using a radio clock signal for short range communications[C]//Proceedings of the 1994 IEEE 44th Vehicular Technology Conference. 1994, 3: 1878-1882.

[4]BROKMAN G, MARCH B, ROMHILD D, et al. Integrated multi-sensors for indusial humidity measurement[C]//Proceedings of the IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems. [S.l.], 2001: 201-203.

[5]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.

[6]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.

[7]EIDSON J C, FISCHER 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.

[8]Karaki J N, Mustafa R , Kamal A E. Data aggregation and routing in Wireless Sensor Networks: Optimal and heuristic algorithms[J]. Computer Networks, 2009, 53(7): 945-960.

[9]HAMITON B R, MA X, ZHAO Q, et al. Aces: adaptive clock estimation and synchronization using Kalman filtering[C]//Proc IEEE ISPCS. Ann Arbor, USA, 2008: 127-130.

[10]袁曉光，楊萬海，史林. 多跳無線傳感器網絡決策融合[J].系統工程與電子技術， 2009, 31(4)： 976-981.

YUAN Xiaoguang, YANG Wanhai, SHI Lin. Decision fusion in multi-hop wireless sensor networks[J]. Systems Engineering and Electronics, 2009, 31(4)： 976-981.

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

YE Ling, LI Taihua, DAI Xuewu. Kalman filtering for precision time synchronization in wireless sensor networks[J]. CAAI Transactions on Intelligent Systems, 2012, 7(6): 518-524.

[12]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.

[13]BARENDT N, CORRELL K, BARNICKY M. Servo design considerations for software-only implementations of precision time protocol[C]//ISPCS. Zurich, Switzerland, 2005: 10-12.

[14]MILLS D L. Internet time synchronization: the network time protocol[M]. IEEE Computer Society Press, 1994: 25-36.