一種改進PBS的無線傳感器網絡時鐘同步方法SCRT

車步波 郭改枝

關鍵詞： 無線傳感網絡; PBS; 時鐘同步; SCRT; 時鐘偏移; 頻率偏移

中圖分類號： TN926?34; TP391.9 ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）04?0031?06

An improved PBS based clock synchronization method

SCRT for wireless sensor networks

CHE Bubo， GUO Gaizhi

（School of Computer and Information Engineering， Inner Mongolia Normal University， Hohhot 010022， China）

Abstract： In allusion to the problem that the synchronization range of sensor nodes is limited when the pairwise broadcast synchronization （PBS） method is used to conduct clock synchronization for wireless sensor networks （WSNs）， an improved PBS based clock synchronization method SCRT is proposed for WSNs. In the method， the sender?receiver （SR） synchronization and receiver?only （RO） synchronization are combined. The cluster head nodes in the packet clustered network exchange the clock information with the reference nodes， and the member nodes adjust the local clock according to the reference time stamps carried in the cluster head sending and receiving clock messages， so as to achieve clock synchronization. It is found that the clock offset estimation and frequency offset estimation are optimal in the comparison with the calculated Cramer?Rao Lower Bound （CRLB） in the Matlab simulation. The experimental results show that in comparison with the PBS scheme， the clock synchronization method can increase the synchronization range of the nodes， significantly reduce the synchronization errors of the entire network， and improve the synchronization efficiency.

Keywords： wireless sensor network; PBS; clock synchronization; SCRT; clock offset; frequency offset

0 ?引 ?言

無線傳感器網絡（WSN）由于其相對于傳統網絡具有規(guī)模大、自組織能力強、廉價、動態(tài)性能好等優(yōu)點，因此在軍事防衛(wèi)、環(huán)境監(jiān)測、醫(yī)療衛(wèi)生、科學研究及工業(yè)、民用和家用網絡等領域具有廣泛的應用[1]。無線傳感器網絡的一個技術支撐是時鐘同步[2?3]，比如在數據融合、移動物體的速度測量[4]、時分多址接入等技術的應用上都需要無線傳感器網絡中節(jié)點具有一致的時鐘消息，因此時鐘同步非常重要。

目前，在無線傳感器網絡時鐘同步協議的研究中，根據是否有參考節(jié)點可將時鐘同步協議分為兩種：一種是基于參考節(jié)點的時鐘同步協議;另一種是分布式的時鐘同步協議。本文研究的是基于參考節(jié)點的時鐘同步協議，即發(fā)送者?接收者（SR）和僅接收者（RO）。對于SR，文獻[5]中提出的RBS（Reference Broadcast Synchronization）是基于參考節(jié)點的時鐘同步協議的代表。協議剛開始會將其中的一個節(jié)點選作參考節(jié)點，之后剩余的節(jié)點會周期性地和這個參考節(jié)點同步，以致使整個網絡的時鐘同步。文獻[6]提出TPSN（Times Synchronization Protocol for Sensor Networks），其原理是選一個節(jié)點作為根節(jié)點（或參考節(jié)點），在這個根節(jié)點的基礎上，整個網絡會逐漸形成一個樹狀結構，而網絡中的節(jié)點都與其父節(jié)點同步后整個網絡的時鐘就能夠同步。文獻[7]提出FTSP（Flooding Time Synchronization Protocol），其原理是選取一個節(jié)點作為根節(jié)點之后，根節(jié)點會以Flooding“泛洪”傳播的方式向整個樹狀網絡周期性地傳播自己的時鐘信息從而達到全網時鐘同步。對于RO，文獻[8]提出PBS，一組節(jié)點可以通過僅監(jiān)聽一對節(jié)點之間交換的時鐘消息來同步。該方法可以顯著降低消息傳遞的能量和帶寬。通過查閱文獻可知，若N為同步過程所需的定時消息數目，L為網絡中整體傳感器節(jié)點的數目，對于RBS，FTSP，TPSN和PBS來說，它們的能量消耗分別為：[NRBS=N+LL-12]，[NFTSP=NL]，[NTPSN=2NL-1]和[NPBS=2N]。通過對比發(fā)現，PBS在每個同步周期中僅需要2N個定時消息，NPBS的大小不取決于網絡中傳感器的數量，這將會節(jié)省巨大的能量，而且網絡規(guī)模越大，此優(yōu)勢越明顯。因此，PBS相對于RBS，TPSN和FTSP等在能量節(jié)省方面有巨大優(yōu)勢，是一種較為理想的同步方法。然而，這種方法也有限制性條件：簇內成員節(jié)點只有位于簇頭節(jié)點和參考節(jié)點的通信范圍內才能達到相對比較好的同步效果。為了解決這個問題，提出了攜帶參考時間戳同步方法，即SCRT。它利用雙層結構的WSN，每個簇都有一個簇頭節(jié)點，簇頭通過與網絡中的參考節(jié)點消息交換進行時鐘同步[9]。SCRT要求在簇頭消息中附加參考時間戳，以便簇內成員可以監(jiān)聽它們的時鐘變化進而調整自己的時鐘。

1 ?SCRT算法

假設在一個成簇網絡中，簇頭在參考節(jié)點的通信范圍內（由于功率約束，傳感器的通信范圍被嚴格限定為半徑取決于傳輸功率的無線電幾何圓內[9]）。對于文獻[7]中的PBS，簇頭通過雙向消息交換與參考節(jié)點進行同步;位于兩圓交集內的簇內成員通過監(jiān)聽簇頭和參考節(jié)點之間的消息交換來進行成對同步。節(jié)點放置模型圖如圖1所示。假定[H]是簇頭節(jié)點，[G]是參考節(jié)點，[M1]～[M5]為簇內成員節(jié)點，那么只有成員節(jié)點[M1]和[M2]可以使用RO方法同步。而位于公共通信范圍之外的成員節(jié)點（[M3]，[M4]和[M5]）不能監(jiān)聽由參考節(jié)點發(fā)送的時鐘信息，所以它們的同步只能通過多跳同步。而這會導致同步精度的下降以及同步誤差的增大。但SCRT解決了這個不足，即利用通信范圍之外的成員節(jié)點監(jiān)聽簇頭發(fā)送的所有時鐘消息，以及[H]和[G]之間的基于SR方法的多輪雙向信息交換的同步。因此，第[i-1]輪中，參考節(jié)點發(fā)送的時鐘消息將被捎帶在同步消息中，以便在第[i]輪中由簇頭發(fā)送，這樣所有成員節(jié)點不管它們的位置如何都能通過監(jiān)聽時鐘消息來與參考節(jié)點同步。當簇頭[H]根據參考節(jié)點[G]采用SR方法進行時鐘同步時，SCRT能夠讓簇內的所有成員節(jié)點[Mj]采用RO方法進行時鐘同步，無論這些成員節(jié)點是否在[H]和[G]的通信范圍內。圖2為SCRT時鐘同步消息交換模型，時鐘消息進行[N]輪交換。要進行SR同步，節(jié)點需要發(fā)送和接收同步請求和確認消息的時間戳;同時，節(jié)點得到參考節(jié)點的接收時間和自己的同步請求消息的接收時間就可以進行RO同步。

假定在第[i]輪消息交換時，在節(jié)點[H]的本地時鐘上獲得同步請求發(fā)送時間戳和消息確認接收時間戳分別為[T（H）1，i]和[T（H）4，i]，在節(jié)點[G]的本地時鐘上得到同步請求發(fā)送時間戳和消息確認接收時間戳分別為[T（G）2，i]和[T（G）3，i]，在節(jié)點[Mj]的本地時鐘上得到同步請求接收時間戳[T（Mj）2，i]。在每個同步輪[i]，節(jié)點[H]在[T（H）1，i]時發(fā)送一個同步請求消息給節(jié)點[G]，該消息攜有發(fā)送時間戳[T（H）1，i]和節(jié)點[G]之前接收同步請求的接收時間[T（G）2，i-1]，攜帶[T（G）2，i-1]可以讓處于[G]的通信范圍外的節(jié)點進行RO同步。節(jié)點[G]在[T（G）2，i]時收到同步請求后，會在[T（G）3，i]返還發(fā)送一個包含時間戳[T（G）2，i]和[T（G）3，i]的確認消息，節(jié)點[H]收到確認消息后，會記錄其到達時間。節(jié)點[H]使用4個時間戳信息可以按照SR同步方法的原理與節(jié)點[G]同步。由于無線通信介質的廣播性質，成員節(jié)點可以完全或部分地監(jiān)聽這種雙向通信，這取決于它們是否在[G]和[H]的通信范圍內。在第[i]輪收到同步請求后會記錄其到達時間，還會得到本地接收時間。因為節(jié)點[G]和[Mj]都處于節(jié)點[H]的廣播范圍，它們有可能會在相同的時間收到同步請求消息。這樣，依照自己本地時鐘上得到時間戳和節(jié)點上的時間戳直接和[G]進行同步，而不需要和其他節(jié)點交換消息。

2 ?RO和SR時鐘偏移和頻率偏移估計

使用一階線性模型來表示節(jié)點間的相對時鐘，包括時鐘偏移和頻率偏移的影響，即：

[T（G）2，i=ω（HG）T（H）1，i+δ（HG）+d（HG）+Xi] ? ? ? （1）

[T（G）3，i=ω（HG）T（H）4，i+δ（HG）-d（HG）-Yi] ? ? ? ?（2）

[T（M）2，i=ω（HM）T（H）1，i+δ（HM）+d（HM）+Zi] ? ? ?（3）

式中：[δ（HG）]和[ω（HG）]分別為節(jié)點[H]和[G]間的相對時鐘偏移和頻率偏移;[δ（HM）]和[ω（HM）]分別為節(jié)點[M]和[H]間的相對時鐘偏移和頻率偏移;[d（HG）]和[d（HM）]分別表示從節(jié)點[H]到[G]和節(jié)點[H]到[M]的傳輸固定延遲。[XiNi=1]，[YiNi=1]和[ZiNi=1]分別表示從節(jié)點[H]到[G]、節(jié)點[G]到[H]和節(jié)點[H]到[M]的傳輸隨機延遲。假定[XiNi=1]，[YiNi=1]和[ZiNi=1]服從均值為0，方差為[σ2]的正態(tài)分布，這樣，固定延遲可以用能夠被確定的傳輸時間來表示，用數據包大小和信號傳播模型來估計。由式（1）～式（3）可得出節(jié)點[M]和[G]之間的時鐘偏移和頻率偏移。

[T（G）2，i-T（M）2，i=ω（MG）T（H）1，i+δ（MG）+d（HG）-d（HM）+Xi-Zi] （4）

令[d?d（HG）-d（HM）]，[Ti?T（G）2，i-T（M）2，i-d]，[Ki?Xi-Zi]，代入式（4）可得：

[Ti=ω（MG）T（H）1，i+δ（MG）+Ki] （5）

因為隨機延遲[XiNi=1]和[ZiNi=1]服從正態(tài)分布，那么[KiNi=1]也服從正態(tài)分布，則基于[KiNi=1]的似然函數[L1]為：

[L1=12πσ2N·e-12σ2i=1NTi-δMG-ωMGTH1，i2] ?（6）

此時想要得到[δ（MG）]和[ω（MG）]的極大似然估計，需將式（6）化為：

[L1=12πσ2N2·e-12σ2i=1NTi-δMG-ωMGTH1，i2]

將其取對數為：

[ln L1=-12σ2i=1NTi-δ（MG）-ω（MG）T（H）1，i2]

并求[δ（MG）]的偏導數[?ln L1?δ（MG）]，令[?ln L1?δ（MG）=0]得到[δ（MG）]的極大似然估計為：

[δ（MG）=i=1N（Ti-T（H）1，iω（MG））N] ?（7）

同理可得[ω（MG）]的極大似然估計為：

[ω（MG）=i=1NT（H）1，iTi-δ（MG）i=1NT（H）1，ii=1N（T（H）1，i）2] （8）

聯合式（7）和式（8）并將[Ti]替換為[T（G）2，i-TM2，i-d]，假設固定延遲是對稱的，那么[d=0]，則時鐘偏移和頻率偏移為：

[ω（MG）=Ni=1Nj=1NT（H）1，j（T（G）2，j-T（M）2，j）-i=1Nj=1NT（H）1，i（T（G）2，j-T（M）2，j）Ni=1N（T（H）1，i）2-i=1Nj=1NT（H）1，iT（H）1，j] （9）

[δ（MG）= i=1Nj=1N（T（H）1，i）2（T（G）2，j-T（M）2，j）-i=1Nj=1NT（H）1，i（T（H）1，j（T（G）2，j-T（M）2，j））Ni=1N（T（H）1，i）2-i=1Nj=1NT（H）1，iT（H）1，j] （10）

為了對時鐘偏移和頻率偏移的精確度進行評估，計算出了相應的克拉美羅界（Cramer?Rao Lower Bound，CRLB）。CRLB給出了任何無偏估計量方差的理論下限。CRLB可通過費雪信息矩陣的倒數[I-1（θ）]獲得：

[I-1（θ）=σ2Ni=1N（T（H）1，i）2-i=1NT（H）1，i2· ? ? ? ? ? ? ? ? i=1N（T（H）1，i）2 ? ?-i=1NT（H）1，i -i=1NT（H）1，i ? ? ? ? ? ? N] ?（11）

則根據費雪信息得出對于RO方法時鐘偏移和頻率偏移的CRLB分別為[10]：

[var（ω（MG））≥Iθ1，1=σ2i=1N（T（H）1，i）2Ni=1N（T（H）1，i）2-i=1NT（H）1，i2] （12）

[var（δ（MG））≥Iθ2，2=Nσ2Ni=1N（T（H）1，i）2-i=1NT（H）1，i2] （13）

根據相對時鐘模型式（1）和式（2），將得出節(jié)點[H]和[G]之間的時鐘偏移和頻率偏移。令[T′2，i?T（G）2，i-d（HG）]，[T′3，i?T（G）3，i-d（HG）]，代入式（1）、式（2）可得：

[T′2，i=ω（HG）T1，i+δ（HG）+Xi] （14）

[T′3，i=ω（HG）T4，i+δ（HG）+Yi] （15）

因為隨機延遲[XiNi=1]和[YiNi=1]服從正態(tài)分布，則基于[XiNi=1]和[YiNi=1]的似然函數為：

[L2=12πσ2Ne-12σ2i=1N（Xi）2+（Yi）2] ? （16）

由式（16）可知，[ln L2=-12σ2i=1N（Xi）2+（Yi）2]，根據式（14）、式（15）將[Xi]和[Yi]代入，得到：[?ln L2?δHG=]

[12σ2i=1N（T′2，i+T′3，i）-ω（HG）i=1N（T（H）1，i+T（H）4，i）-2Nδ（HG），]

令[?ln L2?δ（HG）=0]，求得[δ（HG）]的極大似然估計為：

[δ（HG）=i=1N（T′2，i+T′3，i）2N-ω（HG）·i=1N（T（H）1，i+T（H）4，i）2N] ?（17）

同理可知[ω（HG）]的極大似然估計為：

[ω（HG）=i=1N（T（H）1，iT′2，i+T（H）4，iT′3，i）i=1N（T21，i+T24，i）-δ（MG）·i=1N（T（H）1，i+T（H）4，i）i=1N（T21，i+T24，i）] ?（18）

聯合式（17）、式（18）并替換[T′2，i?T（G）2，i-d（HG）]，[T′3，i?T（G）3，i-d（HG）]，則時鐘偏移和頻率偏移為：

由式（9）、式（10）可知，根據[T（H）1，i]，[T（G）2，i]和[T（Mj）2，i]的時間戳信息的變化來調節(jié)[M]和[G]之間的時鐘偏移[ω（MG）]和頻率偏移[δ（MG）];同理，由式（19）、式（20）可知，根據[T（H）1，i]，[T（G）2，i]，[T（G）3，i]和[T（H）4，i]的時間戳信息的變化來調節(jié)[H]和[G]之間的時鐘偏移[ω（HG）]和頻率偏移[δ（HG）]。通過Matlab進行仿真，圖3和圖4給出了RO和SR時鐘偏移均方誤差、頻率偏移均方誤差和克拉美羅界的對比。由圖3可知，使用RO方法時、隨著同步輪數N的取值變大，時鐘偏移與頻率偏移均方誤差逐漸減小，且當N[≥]50后，時鐘偏移均方誤差與克拉美羅下界基本重合，而頻率偏移均方誤差逐漸趨近于克拉美羅下界。由圖4可知，使用SR方法時鐘偏移與頻率偏移均方誤差曲線變化基本和RO方法一樣，得出的時鐘偏移與頻率偏移均方誤差要小于使用RO方法，但它們都最終收斂于CRLB，因此可以確定得到的時鐘偏移估計與頻率偏移估計為最優(yōu)估計。

3 ?實驗以及結果分析

本文使用基于CC2530芯片的ZigBee節(jié)點進行實驗來評估PBS和SCRT的同步誤差，如圖1所示，進行節(jié)點布控，選用4個節(jié)點分別放在[G]，[H]，[M1]，[M3]的位置。簇頭[H]和成員節(jié)點[M1]和[M3]使用SCRT和PBS和參考節(jié)點[G]進行同步。

在SCRT和PBS中，[H]和[M1]分別使用SR和RO方法與[G]進行一跳同步。然而，[M3]使用SCRT的RO方法與[G]進行同步需要一跳，但是[M3]使用PBS的SR方法實現與[G]的同步需要兩跳。由于[H]，[M1]以相同的方式使用SCRT或PBS進行同步，它們將得到相同的同步誤差，因此，以節(jié)點[M3]進行同步時的精度（見圖5）和穩(wěn)定性（見圖6）來評估SCRT和PBS的同步誤差。

根據圖5可知，隨著執(zhí)行兩輪同步后的延遲的增加，使用PBS同步誤差逐漸增大，而使用SCRT同步誤差波動范圍較小，且相對平穩(wěn)，總體同步誤差小于PBS。而隨著同步輪數的增加，SCRT和PBS的同步誤差都在一個相對固定的范圍內波動，但SCRT的總體同步誤差也小于PBS。因此，在同步精度方面，SCRT要好于PBS。從圖6可以看出，隨著時間的增加，與SCRT相比使用PBS時同步誤差增加更快，且在同一時間，使用PBS時同步誤差明顯大于使用SCRT。因此，就同步精度和穩(wěn)定性的比較可知SCRT比PBS的性能更好。

4 ?結 ?語

本文提出一種改進PBS的無線傳感網絡時鐘同步方法SCRT，并給出了RO和SR的均方誤差與克拉美羅界的對比，得出時鐘偏移與頻率偏移估計為最優(yōu)估計。通過實驗證明SCRT在同步精度與穩(wěn)定性方面強于PBS，節(jié)點的同步范圍也大于PBS。

參考文獻

[1] 張忠厚，趙龍.無線傳感網絡節(jié)能跨層調度算法[J].計算機系統應用，2012，21（8）：48?51.

ZHANG Zhonghou， ZHAO Long. Energy?efficient cross?layer scheduling algorithm based on WSN [J]. Computer systems & applications， 2012， 21（8）： 48?51.

[2] LIU B， REN F， SHEN J， et al. Advanced self?correcting time synchronization in wireless sensor networks [J]. IEEE communications letters， 2010， 14（4）： 309?311.

[3] 王義君，錢志鴻，王桂琴，等.無線傳感器網絡能量有效時間同步算法研究[J].電子與信息學報，2012，34（9）：2174?2179.

WANG Yijun， QIAN Zhihong， WANG Guiqin， et al. Research on energy?efficient time synchronization algorithm for wireless sensor networks [J]. Journal of electronics & information technology， 2012， 34（9）： 2174?2179.

[4] ZHANG W， YIN Q， CHEN H， et al. Distributed angle estimation for localization in wireless sensor networks [J]. IEEE transactions on wireless communications， 2013， 12（2）： 527?537.

[5] ELSON J， GIROD L， ESTRIN D. Fine?grained network time synchronization using reference broadcasts [J]. ACM SIGOPS operating systems review， 2002， 36（SI）： 147?163.

[6] GANERIWAL S， KUMAR R， SRIVASTAVA M B. Timing?sync protocol for sensor networks [C]// Proceedings of the 1st International Conference on Embedded Networked Sensor System. Los Angeles： Scientific Research， 2003： 138?149.

[7] MAROTI M， KUSY B， SIMON G， et al. The flooding time synchronization protocol [C]// Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. Baltimore： ACM， 2004： 39?49.

[8] NOH K L， SERPEDIN E. Pairwise broadcast clock synchronization for wireless sensor networks [C]// Proceedings of IEEE International Symposium on a World of Wireless， Mobile and Multimedia Networks. Espoo： IEEE， 2007： 1?6.

[9] 蔣智鷹，陳勇，胡冰，等.無線傳感器網絡時間同步算法研究[J].計算機工程與應用，2017，53（1）：1?8.

JIANG Zhiying， CHEN Yong， HU Bing， et al. Research on time synchronization algorithm for wireless sensor networks [J]. Computer engineering and applications， 2017， 53（1）： 1?8.

[10] DJENOURI D， MERABTINE N， MEKAHLIA F Z， et al. Fast distributed multi?hop relative time synchronization protocol and estimators for wireless sensor networks [J]. Ad hoc networks， 2013， 11（8）： 2329?2344.