基于最優線性擬合的WSN時間同步算法研究*

吳寶明,李聲飛

1.第三軍醫大學大坪醫院野戰外科研究所,創傷燒傷與復合傷國家重點實驗室,重慶 400042;2.重慶大學通信工程學院,重慶 400040

時間同步是無線傳感器網絡的重要支撐技術,很多傳感器網絡的應用和算法都需要統一的時鐘基準,如數據融合、節點定位、休眠周期的同步、TDMA定時等[1]。所以研究一種高效、精準的時間同步算法具有重要的科研意義和實用價值。目前常用的無線傳感器網絡時間同步算法有：RBS算法[2]、TPSN算法[3]、DMTS算法[4]和 FTSP算法[5-6]等。其中RBS算法是基于單向廣播機制,它排除了發送端對同步精度的影響,達到了較高的同步精度,但其計算量和同步開銷較大,能耗較高;TPSN算法基于雙向成對同步機制,同步效果較好(RBS同步精度的兩倍[3]),但能耗也較大,算法魯棒性較低;而 FTSP算法結合單向廣播機制和雙向成對機制,采用 MAC層打時間戳和線性回歸補償時間漂移和偏移的方式,達到了較高的同步精度,更適用于資源受限的傳感器網絡時間同步。但算法收斂時間較長,易受異常數據點影響[7],且對密度大的多跳網絡,泛洪廣播發送數據包容易引起數據碰撞。

通過對以上時間同步算法比較和總結,筆者選取 FTSP算法實現時間同步。在分析 FTSP算法基礎上,針對其缺點在同步開銷和異常數據處理方面予以改進,提出了基于最優線性擬合的時間同步算法。該算法采用節點分級策略而減少同步所需信息包開銷,并通過分析影響時間同步的因素,提出了基于參數估計的回歸算法,消除異常數據點對回歸曲線的影響,提高了同步精度。

1 FTSP同步算法介紹

FTSP算法由 Vanderbilt大學的 Branislav Kusy等[5-6]提出的,是基于發送者-接收者的同步算法。它結合單向廣播和雙向同步算法的優點,采用泛洪層次結構廣播同步報文,減少了同步信息開銷,對網絡拓撲結構變化和根節點失效有較好的健壯性。通過 MAC層打時間戳方法,縮短了消息傳輸延遲的不確定性,使同步精度達到 μs級。

FTSP算法采用一元線性回歸來估計節點時間漂移率和偏移,并對其進行補償[7]。節點收到同步消息數據包 SYNC后,構造本地時間-全局時間數據對,經過 N次信息交換,構造回歸表((t1,T1),(t2,T2),…(tn,Tn))。將回歸表中數據代入公式(2)和(3)估算時間漂移率和時間偏移

式(1)為本地時間與全局時間關系。式(2)、式(3)中,Ti、ti分別為第 i次同步周期的全局時間和本地時間 ,為全局時間和本地時間的期望 ;通過計算時間漂移率和偏移后,在每秒的末尾對節點本地時間進行補償。而考慮到一定時間范圍內節點晶振頻率是穩定的[8],則本地時間與全局時間成線性關系。通過構造最佳擬合曲線 L,在誤差允許的范圍內,可以通過 L直接計算某一時刻本地時間與全局時間偏移,從而減少了同步消息的發送次數,降低了節點能量消耗[9]。

2 基于最優線性擬合的時間同步算法

FTSP算法采用 MAC層時間戳和線性回歸補償時間偏移和漂移,降低傳輸延時的不確定性,具有較高的同步精度。但它也存在一些問題：(1)對于密度大的多跳網絡,采用泛洪廣播發送同步包,容易引起網內數據碰撞,導致同步包中只有一小部分會被利用,大部分同步包被當做冗余數據包而被拋棄,這樣非常消耗能量和網絡資源;(2)線性回歸算法易受到異常數據點影響,擬合出的回歸曲線不僅不會提高同步精度,反而引入更大的誤差,造成不必要的計算。

針對以上問題,筆者對傳統的 FTSP算法進行改進,設計一種新的消息包傳輸機制,通過將節點分為主動節點和被動節點方式,減少同步所需的通信開銷;對線性回歸算法進行改進,引入概率統計論中的參數估計理論,對進入同步表中的數據對進行可信度判斷,消除誤差較大的數據對擬合曲線的影響,達到了精確的時間同步,同時也延長了節點同步時間,進一步節省了節點的能耗。具體實現過程如下。

2.1 分級消息包傳輸機制

針對上述 FTSP算法存在的問題(1),筆者設計一個低開銷的數據包傳輸機制：將消息包傳輸過程分為節點分級、統計節點度和主/被動節點選擇三個階段

(1)節點分級

假設網絡中節點通信距離有限,通過廣播消息包的形式實現分級。根節點選定后,設定它的級別為 0級。根節點廣播信息包(包含節點級別和當前時間戳),周圍節點接收到信息包后,利用同步算法實現時間同步,并提取信息包中節點級別加 1做為本節點的級別,這樣以此類推,依此實現網絡節點分級。

(2)統計節點度

分級完成后,開始統計各節點的下級節點度,即節點廣播范圍內下級節點的個數。在一個同步周期內,若i級節點收到一個i+1級節點發送的同步包,則它的下級節點度加一,依此類推統計每一級節點的下級節點度。

(3)主動 /被動節點選擇

完成以上兩步后,進行主/被動節點選擇。方法如下：若節點的下級節點度為 0,將其設置為被動節點;若節點達到同步且下級節點度不為 0時,通過比較同級節點中下級節點度最大的節點,做為該級的主動節點,其它節點做為被動節點。

這樣經過幾個同步周期,網內各級中只有下級節點度最大的節點為主動節點,發送同步信息包,其它節點都為被動節點,這樣大大的減少了時間同步開銷,節省了節點能耗。

2.2 參數估計的線性回歸算法

針對上述 FTSP算法存在的問題(2),FTSP算法中未采取有效措施來消除這種影響[6]。筆者采用概率統計論中參數估計理論[10],設置置信區間來判斷進入回歸表中數據對的合法性。選取同步包中的全局時間 T和回歸表已有的數據對,來預測本地時間 t的范圍,具體方法如下：

設 t0是節點收到全局時間 T0時對應的本地時間,依據前式,t0的預測符合：

上式(5)是典型的一元線性回歸模型[10](給定的 x的一定的置信度區間,可以預測出 y的取值范圍),其中為回歸系數,以下采用參數估計的最小二乘法[10]來估計以上未知量。ε服從正態分布,由式(5)知,則服從如下正態分布：

其中 STT為全局時間 T的 2階中心距并能夠證明 t與相互獨立[10],由式 (4)、式(6)得。

又由本地時間 t的殘差平方和為：

Qe稱為殘差平方和,是 σ2的無偏估計

由式(9)可知,殘差平方和與 σ2的商服從分布卡方分布[10]：

將式(9)代入上式有：

可得到 t0服從的 t分布為：

于是對于給定的置信度區間 1-α,有

則可得 t0的預測區間[10]為：

稱為 t0的置信度為 1-α的預測區間。

若回歸表中數據點比較多,式(14)中的根式近似等于 1,若選擇 t0的置信度為 0.99時,查表知為 2.896,則 t的預測區間近似為：

從式(15)可以看出,本地時間的預測區間計算量比較大。由于是 σ2無偏估計,則有可用 σ來近似代替σ2為誤差分布的方差,這個誤差是由消息包傳輸延遲引入的,可以通過分析節點的時延分布特性來估計這個值(筆者針對本節點硬件特性,通過大量測試誤差為27.7μs)。在一次同步過程中,得到本地—全局數據點(ti,Ti)。根據全局時鐘 T和回歸表已有的數據,估計出 t的預測區間,并判斷當前本地時間 t是否在預測區間內。若在預測區間內,則說明這個數據是可信的,將其加入線性回歸表;若不在區間內,則表示這是異常數據將其拋棄,不需要更新線性回歸表。

采用以上預測區間,雖然增加了計算復雜度,但避免了異常數據對回歸曲線的影響。如果進一步增大置信度,將得到限定更加嚴格的可信區間,選出最優數據進行估計。

3 仿真結果分析

3.1 實驗建立

本文采用自行研制的傳感器節點搭建實驗平臺。節點的處理器采用 TI的 CC2430射頻芯片,它是一個內嵌增強型 C8051的無線射頻收發模塊,支持算法在 MAC層打時間戳。節點外部有兩個晶振：32.768 kHz和 32 MHz,選取 32 MHz石英晶振做為節點的振蕩時鐘源。實驗平臺由 5個節點(編號為 node1～node5)組成,其中一個節點做中心節點,其它節點均為網絡中處于不同層次的子節點(節點距離為 10m),組建一個 level為 2的時間同步系統,進行單跳時間同步測試。測試平臺示意圖如圖 1所示,測試方法如下(所有節點最小定時單位為 10μs)。

圖1 時間同步測試圖

(1)中心節點(node1)建立網絡并定時 1 s周期性的廣播時間同步信息包,3個子節點(node2～node4)加入網絡后接收同步包,并利用本文提出的算法修改本地時間與中心節點保持同步;

(2)將節點配置為每次激勵信號電平跳變就報告本地時間到 PC機。采用定時器(文中選取 time3的 0通道)捕獲 IO口輸入電平跳變(上升沿),在捕獲中斷中,通過串口報告節點本地時間到 PC機。

(3)采用函數發生器產生標準方波(文中選擇周期為 100 ms,占空比為 50%的方波)做為激勵事件,接到節點上具有捕獲能力的 IO口上;值得注意的是,公共的脈沖方波信號不能有額外的雜波,才能保證每次查詢都在同一時刻進行。

3.2 同步精度穩定性試驗及分析

為了查看網絡中各節點時間同步精度,筆者任意選取一節點(以 node4為例),查看它的本地時間與中心節點(node1)的時間偏差。隨機選取開始查詢時間,查詢次數為 20次(約為 2 s),每次間隔為100ms,PC機串口接收的時間數據如圖 2所示。

圖2 Node4時間同步比較圖

由圖 2可知,以 node4為例,開始查詢時刻為0x00 15 08 00 C8 54,即在全局時間為 15 min 8 s 200(0x00C8)ms 84μs時,查看 node4節點本地時鐘與全局時鐘的誤差。可見 20次同步誤差范圍在-10 μs～40 μs間,平均誤差為 2.35 μs,Node4能夠很好的與中心節點保持時間同步,同步精度在μs級。

為了進一步查看子節點與根節點(node1)的同步情況,筆者任選兩節點(node2和 node4),隨機選取從開始查詢時刻(node2比 node4晚),連續查詢150次同步事件,查詢間為隔 100 ms,總測試時間約為 15 s。得到兩節點的同步誤差曲線如圖 3所示(最小定時單位為 10μs)。

圖3 同步誤差曲線

圖3(a)(b)知,node2的誤差在 -50μs～90μs之間,均值為 1.286 7μs,方差為 8.044 8;node4的誤差在 -90μs～80μs之間,均值為 0.42 μs,方差為 13.856。node4的誤差波動范圍明顯要比 node2波動范圍要大(node4方差比 node2大),分析其原因知 node4的開始查詢時間比 node2要早(相差15min),線性回歸算法未擬合出最佳估計曲線,隨著時間增長,同步誤差會逐漸趨于穩定。兩節點的誤差范圍都在 μs級,誤差呈正負交錯波動,且有逐漸減小的趨勢,可見算法收斂性較好,能夠有效的減少同步誤差。可得到以下結論：以上兩節點能夠很好的與中心節點保持同步。

為了比較本文的算法與 FTSP算法同步精度差異,任選 1個節點(筆者選取 node2),分別采用本文的算法和 FTSP算法實現該節點與中心節點(node1)時間同步,比較兩算法的同步誤差曲線如圖 4所示。查詢次數為 200次,查詢間隔為500m s,總測試時間約為 100 s。

圖4 兩種同步算法誤差對比圖

從圖 4中可以看出：同步精度方面,FTSP的同步誤差在 -40μs～400μs間,且誤差與同步周期有密切關系,隨著同步周期增加誤差逐漸增大,在每一個周期內,誤差隨時間線性增大,級間誤差會發生陡變情況。分析知主要有以下兩點原因：(1)節點晶振存在頻率漂移,隨著同步周期變大,漂移產生的誤差累計而帶來了更大的誤差;(2)異常數據點進入回歸表,導致線性擬合曲線計算出的全局時間與真實值偏差很大,導致個別同步周期的同步誤差很大。

相比之下本文提出的同步算法,誤差范圍控制在 -90μs～40μs內,遠遠小于前者,且在 100 s(200次查詢時間)時間內能夠維持較高同步精度。而誤差波動也較為穩定,不會隨著同步周期的增加而陡變的情況。這是由于改進的算法采取補償晶振時間漂移方式,防止誤差隨周期增長而累加,并采取有效措施避免異常數據點對同步精度影響,從而獲得了更加平穩的誤差曲線,算法收斂時間縮短。可見采用本算法后,算法的執行周期顯著增大,適合于資源受限的無線傳感器網絡的應用。

由于無線傳感器網絡對不同的應用環境中表現出不同特點,對時間同步要求也存在差異。所以在分析同步算法時,一般在同步方式,誤差,通信開銷,能耗和有效范圍方面進行比較,筆者對 RBS、TPSN和本文算法在以上方面進行對比,如表 1所示。

表1 三種同步算法比較圖

表中 RBS和 TPSN算法數據是參考文獻[11]在 Mica平臺上獲取的,通過比較可看出本算法同步精度介入 TPSN算法和 RBS算法之間,達到了較高的同步精度,能滿足一般傳感器網絡應用需求;在運算復雜度和能耗方面都優于其它兩種算法;在同步開銷方面,受到技術限制只限于理論上分析,傳統的FTSP算法一次同步周期需要 o(n2)個信息包開銷,而本文算法僅需要 m?n(m為級數,n為當前級活動節點數)個信息包開銷,減小了同步通信開銷,降低節點能耗和計算量,減輕了節點的負擔。因此本算法更適合于能量、資源受限的傳感器網絡應用。

4 結論

目前針對資源、能量受限的傳感器網絡時間同步算法研究相對較少,很多算法仍處于仿真階段,與實際應用有一定距離。本文在分析 FTSP算法基礎上,主要在同步開銷和異常數據處理方面對其進行改進。采用節點分級策略,較少了同步通信開銷;采用概率統計理論中參數估計思想,排除了異常數據點的影響,提高了回歸曲線的跟蹤精度。最后通過實驗測試表明：本算法在保證精度的前提下,大幅度提高算法的執行周期,減少了同步通信開銷,在各方面優于傳統的 FTSP算法,更適用于能量受限的無線傳感器網絡的應用。

[1]周中良,于雷,潘泉.綜合化多傳感器空間管理模型與算法研究[J].傳感器技術學報,2007,20(11)：256-259.

[2]Elson Jeremy,Girod Lewis,Estrin Deborah.Fine-Grained Network Time Synchronization Using Reference Broadcasts[C]//Proceedings of the Fifth Symposium on Operating Systems Design and Implementation.Boston,MA,2002：147-163.

[3]田賢忠,陳登,胡同森.無線傳感器網絡按需時間同步算法研究[J].傳感器技術學報,2008,21(11)：1881-1886.

[4]張杰,石為人.基于無線傳感器網絡的信息采集檢測系統設計[J].傳感技術學報,2009,22(6)：861-864.

[5]Philipp Sommer,Philipp Sommer.Gradient Clock Synchronization in Wireless Sensor Networks[J].2009：37-48.

[6]Kyoung-lae Noh,Serpedin.A New Approach for Time Synchronization in Wireless Sensor Networks：Pairwise Broadcast Synchronization[J].Wireless Communications,2008,9,7(9)：3318-3322.

[7]周賢偉,韋煒.無線傳感器網絡的時間同步算法研究[J].傳感技術學報,2006,19(1)：20-25.

[8]黃天戍,陳苒菁.石英晶振頻率測試系統的研究與開發[J].中國儀器儀表,2005,(10).

[9]孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京：清華大學出版社,2005：158-176.

[10]楊虎,孫瓊蓀,鐘波.數理統計[M].北京：高等教育出版社,2004：103-135.

[11]Ganeriwal Saurahh,Kumar Ram,Srivastava Mani.Tim ing Sync Protocol for Sensor Networks[C]//ACM SenSys.Los Angeles,CA,2008.