金 虎

（黑龍江大學 計算機科學技術學院，哈爾濱 150080）

0 引 言

大量集成了傳感器、處理器、無線通信模塊的節(jié)點以Ad Hoc方式構成大規(guī)模傳感器網(wǎng)絡，網(wǎng)絡中節(jié)點協(xié)作完成數(shù)據(jù)采集、融合處理，通信發(fā)送等任務。作為分布式自治系統(tǒng)，無線傳感器網(wǎng)絡具有高靈活性、強魯棒性及高智能度等優(yōu)點，可被廣泛應用于國防、環(huán)保、交通、醫(yī)療，以及制造業(yè)等多個領域[1]。時鐘同步是無線傳感器網(wǎng)絡的一項重要支撐技術，傳感器網(wǎng)絡自身協(xié)議的運行及基于其上的應用，如：標記數(shù)據(jù)采集時間、時分多址接入、協(xié)同休眠、定位、數(shù)據(jù)融合等都需要網(wǎng)絡中節(jié)點的時鐘保持同步[2]。

目前在Internet中廣泛使用的NTP同步算法同樣也不適合于傳感器網(wǎng)絡應用，因其采用雙向通信同步以抵消信息傳輸時延的影響，要求雙向時延必須對稱。在傳感器網(wǎng)絡中由于鏈路層的影響，雙向時延往往不對稱。而且NTP算法的工作場景是有線網(wǎng)絡，沒有針對能耗進行優(yōu)化、協(xié)議復雜度高[3]。因此研究適合于傳感器網(wǎng)絡的時鐘同步算法是目前國內(nèi)外學術界的一個熱點。通常在傳感器網(wǎng)絡中，除了非常少量的傳感器節(jié)點攜帶如GPS的硬件時間同步部件外，絕大多數(shù)傳感器節(jié)點都需要根據(jù)時間同步機制交換同步消息，與網(wǎng)絡中的其它傳感器節(jié)點保持時間同步[4]。

本文首先介紹基于層次的時間同步算法；然后介紹了能量節(jié)省的自適應時間同步算法以及相關實驗數(shù)據(jù)和結論。

1 基于層次的時間同步協(xié)議

傳感器網(wǎng)絡基于層次的時間同步協(xié)議類似于傳統(tǒng)網(wǎng)絡的NTP時間同步協(xié)議，目的是提供傳感器網(wǎng)絡全網(wǎng)范圍內(nèi)節(jié)點間的時間同步。基于層次的時間同步協(xié)議采用層次網(wǎng)絡結構，首先將所有節(jié)點按照層次結構進行分級，然后每個節(jié)點與上一級的一個節(jié)點進行時間同步，最終所有節(jié)點都與根節(jié)點時間同步。節(jié)點對之間的時間同步是基于發(fā)送者——接收者的同步機制[5]。

基于層次的時間同步協(xié)議假設每個傳感器節(jié)點都有惟一的標識號ID，節(jié)點間的無線通信鏈路是雙向的，通過雙向的消息交換實現(xiàn)節(jié)點間的時間同步?；趯哟蔚臅r間同步協(xié)議將整個網(wǎng)絡內(nèi)所有節(jié)點按照層次型結構，如TinyDB需要數(shù)據(jù)融合樹，這樣整個網(wǎng)絡只需生成和維護一個共享的層次結構。

鄰近級別的兩個節(jié)點對間通過交換兩個消息實現(xiàn)時間同步，其中節(jié)點S屬于第i級節(jié)點，節(jié)點R屬于第（i－1）級節(jié)點，T1和T4表示節(jié)點S本地時鐘在不同時刻測量的時間，T2和T3表示節(jié)點R本地時鐘在不同時刻測量的時間，Δ表示兩個節(jié)點之間的時間偏差，d表示消息的傳播時延，假設來回消息的延遲是相同的。節(jié)點S在T1時間發(fā)送同步請求分組節(jié)點R，分組中包含S的級別及T1時間，節(jié)點R在T2時間接收到分組，T2＝（T1＋d＋Δ），然后在T3時間發(fā)送應答分組給節(jié)點S，分組中包含節(jié)點R的級別及T1、T2和T3信息，節(jié)點S在T4時間收到應答，T4＝T3＋d－Δ，因此可以推出：

節(jié)點S在計算時間偏差后，將它的時間同步到節(jié)點R。

2 自適應時鐘同步算法

基于層次的時間同步協(xié)議是周期性執(zhí)行同步算法，而且同步協(xié)議的開銷比較大，所以提出自適應時間同步算法，根據(jù)最近的時間偏移和時間同步周期來調(diào)整同步的時間周期的長度?？梢詼p少同步協(xié)議的開銷，進而減少節(jié)點的能量開銷。同步周期選取要充分考慮無線傳感器網(wǎng)絡節(jié)點到節(jié)點傳輸時延的抖動，它考慮本次傳輸時延于前一次之間的差值，計算出一個補充值來減少抖動帶來的影響。統(tǒng)計分析每個包的延遲，來估計最大延遲，以一個平均延遲和初試設定的比例因子計算本次的補充值。

將考慮節(jié)點到節(jié)點傳輸延遲抖動帶來的更新周期抖動，客戶端根據(jù)時間精度要求、前個歷史同步周期的統(tǒng)計以及前m次時鐘偏移量和同步周期，來選取下次時鐘同步周期。

首先定義幾個變量：

θ：結點的同步周期。定義為兩次同步請求之間的時間間隔，θ0為下一次同步的周期，θ1，θ2，…，θm為以前的m次歷史時鐘周期。

t：本地時鐘。t1為前一次調(diào)整時節(jié)點的本地時鐘。

C：標準時鐘。C1為前一次調(diào)整時所獲得的標準時鐘。

Δ：結點的時鐘偏移。定義為結點的本地時鐘和標準時鐘的絕對差Δ＝abs（C－t）。

τ：系統(tǒng)的時鐘精度。它反映了系統(tǒng)對時鐘同步的要求，即允許的最大偏移，abs（C－t）＜τ。

Δp：預計下次同步周期時，節(jié)點所允許的時鐘偏移。

而θ的取值必須符合θρ≤τ。在計算下一次同步周期時，以Δp作為預計的偏移值。在理想情況下，以周期θ0進行更新時，時鐘偏移Δ0≤Δp（預計值）。

由于直接計算ρ比較復雜，可采用一個替代方法。該方法使用前m個同步的平均周期作為下次的參考周期，同時考慮最近一次的偏移情況，綜合計算出下次的同步周期，即：

在預計更新周期（用上一次更新中的偏移速度為基準得到）和歷史統(tǒng)計的平均周期之間進行權衡，計算生成本次的實際更新周期。另外，如果上一次的應答包返回的時延過長超過可信范圍 [0，Tmax]，或沒有收到應答包，則取μ1＝0，μ2＝1即以累計的平均周期為準。

3 應用實驗

本實驗在美國加州大學伯利克分校開發(fā)的TinyOS系統(tǒng)下進行。實驗1是在最大時間偏差一定的情況下，在PC上分別模擬在5、10、15和25個節(jié)點上執(zhí)行TPSN和ADTS時間同步算法。實驗2在不同的最大時間偏差下，在PC上分別模擬在15個節(jié)點執(zhí)行TPSN和ADTS時間同步算法。圖1表示最大時間偏差為5ms時，兩種時間同步算法執(zhí)行50000ms（每個周期為500ms）所需的同步次數(shù)。圖2表示最大時間偏差為5ms時，分別執(zhí)行兩種時間同步算法執(zhí)行50000ms所消耗的通信能量。圖3表示在15個節(jié)點上，兩種時間同步算法執(zhí)行50000ms所需的同步次數(shù)。圖4表示在15個節(jié)點上，分別執(zhí)行兩種時間算法50000ms所消耗的通信能量。本實驗在計算每個節(jié)點通信消耗的能量時，采用Mica2的性能參數(shù)，當無線部件工作在15mW的模式下，節(jié)點發(fā)送或接收一個數(shù)據(jù)包消耗的能量為0.4mJ。

由圖1可見，TPSN同步的次數(shù)遠多于ADTS，TPSN每個周期執(zhí)行一次時間同步操作，而ADTS可以動態(tài)調(diào)整同步的時間周期的長度，從而減少了同步次數(shù)。由圖2可見，TPSN通信消耗的能量遠大于ADTS。TPSN算法不但同步次數(shù)高于ADTS算法，而且TPSN每次執(zhí)行時間同步，需要交換兩個消息，這增加了發(fā)送接收信息次數(shù)，從而導致更大的通信能量消耗。隨著節(jié)點個數(shù)的增加，ADTS算法的優(yōu)越性越明顯，當節(jié)點個數(shù)為25時，ADTS算法所消耗的通信能量僅為TPSN算法的1／3。

圖4 不同最大時間偏差下通信消耗能量比較Fig.4 Energy consumption of communication for varying the maximal time error

由圖3，圖4可見，ADTS同步次數(shù)與通信消耗的能量遠小于TPSN，隨著最大時間偏差的減小，即同步精度的提高，差距越明顯。當最大偏差為1ms時，ADTS通信消耗的能量不足TPSN算法的1／3。

4 結 論

無線傳感器網(wǎng)絡中的時間同步是一個重要的問題，但是對于傳感器網(wǎng)絡的大部分應用來說，時間同步的精確性要求并不是特別高，而傳感器節(jié)點的電能十分有限，因此同步算法在滿足時間精確度的要求下，應盡量降低協(xié)議的開銷。

本文的同步算法是在傳感器網(wǎng)絡內(nèi)建立一個層次結構，然后從匯聚點開始，每相鄰層之間的節(jié)點采用成對的節(jié)點間的同步算法進行同步，最后實現(xiàn)了全網(wǎng)絡的同步。在此基礎之上，我們討論了可變時間同步周期的算法。由于傳感器的節(jié)點能量有限，本文根據(jù)節(jié)點時間的偏移速度完成了一種自適應的時間同步算法，是可節(jié)省節(jié)點能量的有一定價值的算法。

[1]孫利民，李建中，陳 渝，等.無線傳感器網(wǎng)絡[M].北京：清華大學出版社，2005.

[2]J.Elson，D.Estrin.Time synchronization for wireless sensor networks [A].In 2001International Parallel and Distributed Processing Symposium（IPDPS），Workshop on Parallel and Distributed Computing Issues in Wireless[C].2001.

[3]Jeremy Elson，Lewis Girod，Deborah Estrin.Finegrained network Time Synchronization using Reference Broadcasts [A].In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation（OSDI 2002）[C].Boston，MA，December 2002.

[4]Maroti M，Kusy B，Simon G，et al.Flooding time synchronization in wirless sensor networks [C]／／Acm SenSys’04，November 3-5，2004，Baltinore，Maryland.

[5]蓋旗濤，樊小平，蔡 蒨，等.WSN時間同步算法研究 [J].電子技術，2010，（7）：5-7.