引言

無線傳感器網(wǎng)絡是由密集型、低成本、隨機分布的節(jié)點組成，集成了傳感器技術、計算機技術和通信技術,能夠協(xié)同地實時監(jiān)測、感知并采集各種環(huán)境的數(shù)據(jù)，適用于戰(zhàn)場通信、搶險救災和公共集會等突發(fā)性、臨時性場合。保持節(jié)點之間時間上的同步在無線傳感器網(wǎng)絡中非常重要，它是保證可靠的數(shù)據(jù)傳輸、精確的節(jié)點定位、可靠的數(shù)據(jù)融合、準確的目標跟蹤與檢測的前提。如利用波的到達時間差測距，就需要高精度的時間同步。無線傳感器網(wǎng)絡中，由于頻率漂移，各個節(jié)點之間必然會產(chǎn)生一定的時鐘偏移，因此有效的時間同步技術對保證各個節(jié)點之間的時鐘同步非常重要[2]。

2002年,Elson等人在影響未來網(wǎng)絡研究發(fā)展方向的國際權威學術會議HotNets上，首次提出無線傳感器網(wǎng)絡時間同步的研究課題,至今已有相當多的典型時間同步算法。基于發(fā)送者接收者的雙向同步算法中，比較典型的如TPSN(Timingsync Protocol for Sensor Networks)算法[3]。TPSN算法分成兩個階段，第一階段為層次發(fā)現(xiàn)階段，第二階段為同步階段。在同步階段采用發(fā)送者接收者的雙向成對同步算法， MAC層采用加入時間戳的技術，進而估算出節(jié)點之間的傳輸延遲與時鐘偏移。該作者在Mica 節(jié)點上測試過，TPSN平均單跳誤差為17.61 μs。基于發(fā)送者接收者的單向時間同步算法中，比較典型的如FTSP(Flooding Time Synchronization Protocol)算法[4]、DMTS(Delay Measurement Time Synchronization)算法[5]。基于接收者接收者的同步算法，典型的有RBS(Reference Broadcast Synchronization)算法[6]。近幾年，也有作者提出了協(xié)作同步機制[7]。協(xié)作同步的核心思想仍然是屬于集中式協(xié)議，要求整個網(wǎng)絡中節(jié)點密度較高。參考文獻[8]中，作者提出了分步式同步機制，整個網(wǎng)絡無需構造由根節(jié)點發(fā)起的生成樹，只需要每個節(jié)點之間使用分布式廣播同步機制。

傳統(tǒng)的同步機制只是簡單地修正節(jié)點之間的時鐘偏移，傳感器節(jié)點時鐘由晶體振蕩器驅(qū)動。晶體振蕩器的實際頻率通常與它標定的頻率之間存在一定的偏移，即存在時鐘頻率的漂移。傳統(tǒng)的同步算法為了提高同步精度，節(jié)點就必須頻繁地重復時間同步算法，以消除時鐘偏移的影響。頻繁地交換消息，必然給功耗受限的節(jié)點帶來額外的負擔，因此考慮節(jié)點之間的時鐘漂移也是非常重要的[9]。

1 、CDCO時鐘同步算法設計

1.1 時鐘模型

本同步算法采用的是發(fā)送者接收者的雙向同步算法，同時考慮了時鐘漂移與偏移對同步精度的影響。在無線傳感器網(wǎng)絡的節(jié)點中，如果采用的是時鐘速率恒定模型，那么節(jié)點的硬件時鐘Ci(t)與真實時間Ck(t)的關系可以表示為Ci(t)=aik·Ck(t)+mik。式中，aik為節(jié)點之間的相對漂移量，mik為節(jié)點之間的相對偏移量。如果兩個節(jié)點之間完全同步，則相對漂移量aik為1，相對偏移量mik為0。

1.2 單跳同步原理

如圖1所示，hi(t1)、hi(t4)、hi(t5)用來記錄參考節(jié)點的本地時間， hk(t2)、hk(t3)、hk(t6)用來記錄同步節(jié)點的本地時間。同步過程采用類似TPSN算法的雙向同步過程，假設同步節(jié)點與參考節(jié)點的時鐘關系采用時鐘恒定模型(這在現(xiàn)實中也是合理的)，則hk(t)=ρki·hi(t)+mki。式中，hk(t)、hi(t)分別為同步節(jié)點與參考節(jié)點在本地時刻t的時鐘，ρki、mki分別為時鐘漂移量與偏移量。

圖1 雙向同步原理圖

假設傳播延遲為dki,因為在極短的時間內(nèi)來回傳播延遲與節(jié)點時偏可假設相同。假設漂移量

則在理想情況下，ρki為1，即線段hi(t1)hk(t2)平行于線段hi(t5)hk(t6)，此時不存在時鐘漂移[10]。如圖1所示，根據(jù)雙向同步原理與時鐘恒定模型可以得到：

則根據(jù)得到的ρBA、mBA修改同步節(jié)點的本地時鐘,就能實現(xiàn)與同步節(jié)點的時鐘同步。

1.3 多跳同步原理

假設節(jié)點A與其下一跳節(jié)點B已經(jīng)實現(xiàn)了時間同步，則可以得到：

由式(5)與式(6)可以得到:

同樣,假設節(jié)點B與下一跳節(jié)點C已經(jīng)實現(xiàn)了時間同步，同理可以得到：

顯然將式(7)帶入式(8)可以得到節(jié)點A與C之間的同步。

采用同樣的方法逐級迭代下去,就可以實現(xiàn)全網(wǎng)的時間同步。

1.4 理論誤差來源分析

由1.2節(jié)的分析可知,兩節(jié)點之間的時鐘關系為hk(t)=ρki·hi(t)+mki。如果兩個節(jié)點不存在時鐘頻偏的情況，ρki為1，即hi(t1)hk(t2)平行于邊hi(t5)hk(t6)，則頻率偏移誤差：

假設不存在頻率偏移的情況下，即ρki為1，我們來計算時鐘偏移的誤差來源。根據(jù)圖1所示的發(fā)送接收雙向消息同步過程，可以得到：

式中, hk(t3)、hi(t4)分別是t3、t4所對應的同步節(jié)點和本地節(jié)點所測出的本地時間，Sk代表節(jié)點k的報文發(fā)送時間，Ak是發(fā)送報文的訪問時間，Pk→i是節(jié)點k傳播到節(jié)點i的時間，Ri是節(jié)點i的報文接收處理時間，Nkt是傳輸Nk個比特的總時間，Terror指傳輸比特的誤差，Rerror為打時標過程存在的誤差，Dk→it3代表節(jié)點k與節(jié)點i在hk(t3)時刻的時偏。因為在實驗中采用了MAC層的打時標方法，這樣就可以消除發(fā)送時間與訪問時間對誤差的影響。于是式(11)就可以簡寫為：

式中,Dk→it3=Dk→it6+RDk→it3→t6。同理可以得到hk(t6)：

由以上各式可以得到時偏:

式中，RDk→it3→t6代表從hk(t3)到hk(t6)時段內(nèi)，節(jié)點k相對于節(jié)點i增加的時偏;Dk→it6是hk(t6)時刻節(jié)點k與節(jié)點i之間的時偏。可以算出時鐘偏差為：

2 、算法性能分析

無線傳感器節(jié)點采用的是晶體振蕩器來計時節(jié)點的本地時鐘，由于成本的限制，只能采用一些低成本的晶振。硬件設備廠商一般都會給出晶振頻率變化范圍，一般時鐘漂移為[10，100]ppm。同步周期取20 s,在一個周期內(nèi)采樣4次，得到的結果如表1所列。相同情況下的多跳同步誤差如表2所列。

從表1中可以看出，在同一個周期內(nèi)，相比TPSN算法，CDCO算法誤差隨采樣間隔的增長明顯比TPSN慢，在相同的采樣間隔，誤差也明顯低于TPSN算法。因為相比于TPSN算法，本文考慮了時鐘漂移，因此可以在較長的時間內(nèi)保持同步。從表2可以看出，隨跳數(shù)增加，CDCO算法精度較高于TPSN算法。在相同的跳數(shù)內(nèi)，CDCO算法的誤差明顯低于TPSN算法，且隨著跳數(shù)增加，CDCO算法的同步誤差增加明顯低于TPSN算法。相對于TPSN算法，CDCO算法可以減小誤差多跳累加的影響。

3、結語

本文基于發(fā)送方接收方雙向同步算法的原理，設計了一種同時考慮時鐘偏移與漂移的同步補償機制(CDCO算法)。實驗結果表明，相比傳統(tǒng)的發(fā)送方接收方雙向同步算法，CDCO算法因為采用了時鐘漂移補償技術，在同一個同步周期內(nèi)，同步誤差隨時間增加變化較小;而傳統(tǒng)的算法因為存在時鐘漂移，在同一個周期內(nèi)誤差隨時間增大而變得越來越大。相對于TPSN算法，CDCO算法可以減小誤差多跳累加的影響。

責任編輯：gt