無(wú)線傳感器網(wǎng)絡(luò)中一種自適應(yīng)時(shí)間同步算法

金 虎

（黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，哈爾濱 150080）

0 引 言

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

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

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

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

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

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

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

節(jié)點(diǎn)S在計(jì)算時(shí)間偏差后，將它的時(shí)間同步到節(jié)點(diǎn)R。

2 自適應(yīng)時(shí)鐘同步算法

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

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

首先定義幾個(gè)變量：

θ：結(jié)點(diǎn)的同步周期。定義為兩次同步請(qǐng)求之間的時(shí)間間隔，θ0為下一次同步的周期，θ1，θ2，…，θm為以前的m次歷史時(shí)鐘周期。

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

C：標(biāo)準(zhǔn)時(shí)鐘。C1為前一次調(diào)整時(shí)所獲得的標(biāo)準(zhǔn)時(shí)鐘。

Δ：結(jié)點(diǎn)的時(shí)鐘偏移。定義為結(jié)點(diǎn)的本地時(shí)鐘和標(biāo)準(zhǔn)時(shí)鐘的絕對(duì)差Δ＝abs（C－t）。

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

Δp：預(yù)計(jì)下次同步周期時(shí)，節(jié)點(diǎn)所允許的時(shí)鐘偏移。

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

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

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

3 應(yīng)用實(shí)驗(yàn)

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

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

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

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

4 結(jié) 論

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

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

[1]孫利民，李建中，陳 渝，等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，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時(shí)間同步算法研究 [J].電子技術(shù)，2010，（7）：5-7.