基于機器學習方法的無線傳感網(wǎng)絡(luò)時鐘同步算法

劉學超+郭改枝+潘亮

摘 要： 提出一種無線傳感網(wǎng)絡(luò)同步的方法，結(jié)合發(fā)送者?接收者同步（SRS）和接收者?接收者同步（RRS）兩種方法，使得位于特定區(qū)域的傳感器節(jié)點通過監(jiān)聽一對超級傳感器節(jié)點交換時鐘消息，借助最小二乘法精確估計出時鐘偏差以及頻率偏差進行補償，實現(xiàn)節(jié)點間同步。該時鐘同步方案的設(shè)計與其他已提出的同步方案相比，顯著降低了整個網(wǎng)絡(luò)的能量消耗而不引起任何同步精度的損失。

關(guān)鍵詞： 無線傳感網(wǎng)絡(luò)； 最小二乘法； 時鐘同步； 時鐘偏差； 頻率偏差； 均方誤差

中圖分類號： TN915.02?34 文獻標識碼： A 文章編號： 1004?373X（2018）05?0065?04

Abstract： A method of wireless sensor network （WSN） synchronization is proposed， which is combined with SRS （sender?receiver synchronization） and RRS （receiver? receiver synchronization） methods to make that the sensor nodes located in a specific area can exchange the clock messages by monitoring a pair of super sensor nodes. The least square method is used to accurately estimate the clock offset and frequency offset for compensation， so as to realize the synchronization among nodes. In comparison with other clock synchronization schemes， the proposed clock synchronization scheme can significantly reduce the energy consumption of the entire network without any loss of synchronization accuracy.

Keywords： wireless sensor network； least square method； clock synchronization； clock offset； frequency offset； mean square error

0 引 言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，無線傳感器網(wǎng)絡(luò)（WSN）逐漸在各領(lǐng)域中被廣泛的應用，微機電系統(tǒng)（MEMS）、數(shù)字電路設(shè)計和無線通信的發(fā)展給無線傳感網(wǎng)絡(luò)的普及提供了很多便利條件。無線傳感器網(wǎng)絡(luò)將會是未來通信環(huán)境的基礎(chǔ)設(shè)施，一個新的問題隨之產(chǎn)生，即網(wǎng)絡(luò)同步問題。無線傳感器網(wǎng)絡(luò)的時間同步對于維持數(shù)據(jù)的一致性、協(xié)調(diào)性以及執(zhí)行其他基本操作都至關(guān)重要[1]。

一般來說，在網(wǎng)絡(luò)同步中存在兩種不同的方法，即發(fā)送者?接收者同步（SRS）和接收者?接收者同步（RRS）。前者是針對一對節(jié)點之間的雙向消息交換的經(jīng)典模型，后者是在同步節(jié)點之間比較來自參考節(jié)點的信標包進行同步。大多數(shù)現(xiàn)有的時間同步協(xié)議都可以歸類為這兩種方法之一[2]。例如，參考廣播同步（RBS）協(xié)議[3]基于RRS，使得在參考節(jié)點傳輸范圍內(nèi)的一組無線傳感器同步，它需要子節(jié)點（除了參考節(jié)點）之間的消息交換對來補償它們的相對時鐘偏移。無線傳感器時鐘同步算法（TPSN）[4]采用SRS，因為它取決于假定雙向定時消息交換的一系列成對同步。TPSN基于網(wǎng)絡(luò)的層級結(jié)構(gòu)，并且通過沿著分層樹的每個分支（邊）交換定時消息來同步整個網(wǎng)絡(luò)。本文提出成對廣播同步（PBS）方案，其依賴于新穎的時間同步方法實現(xiàn)網(wǎng)絡(luò)范圍內(nèi)的同步，既不同于SRS也不同于RRS，稱之為僅接收者同步（ROS）。

1 主要思想

首先需要有進行雙向時鐘信息交換的兩個節(jié)點，這兩個節(jié)點的能量必須足夠大，因此可稱為超級節(jié)點。由于功率約束，傳感器的通信范圍嚴格地限于其半徑，半徑的大小取決于發(fā)射功率（參見圖1）的（無線電幾何）圓，所以在無線傳感器探頭布控過程中，需要合理放置兩個超級節(jié)點，使得以超級節(jié)點為中心的這兩個圓有盡可能大的交集并且使得盡可能多的待同步節(jié)點同時處于兩個超級節(jié)點的通信范圍內(nèi)。

假設(shè)一個無線傳感器網(wǎng)絡(luò)的節(jié)點布控如圖1所示，當兩個超級節(jié)點進行同步信息交換時，處于兩圓交集內(nèi)的每個節(jié)點（例如，節(jié)點）可以監(jiān)聽到來自節(jié)點和節(jié)點的消息包。節(jié)點和節(jié)點之間進行雙向定時消息交換，節(jié)點為父節(jié)點。此時，在兩圓交集的所有節(jié)點可以監(jiān)聽到分別來自節(jié)點和節(jié)點包含成對同步時間戳的同步消息。在這個過程中，該范圍內(nèi)的其他待同步節(jié)點不需要發(fā)送額外定時消息就可以同步到父節(jié)點上，這種同步方法顯著減少了發(fā)送定時消息的數(shù)量。

2 算法描述與實現(xiàn)

PBS同步中父節(jié)點和子節(jié)點實現(xiàn)同步的消息交換模型如圖2所示。代表之間的時鐘偏移，假設(shè)時鐘消息交換了次，在第次信息交換時的本地時鐘是，的本地時鐘是。節(jié)點向節(jié)點發(fā)送同步消息包中包含節(jié)點的標識符（ID）和節(jié)點發(fā)送消息時的時間戳。節(jié)點在時刻接收到該同步消息包并且在時刻向節(jié)點發(fā)送確認消息，該消息包含節(jié)點的標識符（ID），節(jié)點在時刻收到該消息，故本次消息交換完成消息包內(nèi)共有4個時戳被記錄。

在整個消息交換的過程中，延遲是不可忽略的。分組延遲包含以下幾個部分：發(fā)送延遲、接收延遲、傳輸延遲、處理延遲、信道訪問延遲。這些延遲分量可以進一步分為兩個部分：固定延遲和隨機延遲。關(guān)于這些延遲的詳細研究請參考文獻[5]。

到目前為止，已經(jīng)提出了幾個隨機延遲模型。單服務器M/M/1隊列可以有效地表示點到點連接的累積鏈路延遲，其中隨機延遲被建模為指數(shù)隨機變量。假設(shè)延遲是多個獨立隨機過程的加法，則建模為高斯延遲模型是合適的。卡方檢驗表明，隨機延遲建模為高斯分布隨機變量后具有99.8%的置信度。本文中假設(shè)隨機延遲和是服從均值為方差為的正態(tài)分布。endprint

如圖2所示，在兩圓交集中的任意節(jié)點，例如，節(jié)點當節(jié)點和節(jié)點交換時鐘消息時，節(jié)點能夠監(jiān)聽到這兩個時鐘消息。因此，當節(jié)點從節(jié)點接收到分組時，節(jié)點可以在其本地時鐘觀測到一組時間讀數(shù)。關(guān)于時間戳集合的信息也可以通過從節(jié)點接收分組來獲得。本文同時考慮時鐘偏移和時鐘頻偏的影響，節(jié)點第次收到同步消息的時間戳可以表示為：

式中：代表之間的相對時鐘偏移；代表之間的相對時鐘頻偏。

（節(jié)點在第次收到同步消息的時間）可表示為：

要使時鐘偏差以及時鐘頻偏的計算盡可能達到精確的程度，本文借助最小二乘法來估計時鐘偏差以及時鐘頻偏，需要構(gòu)造一元線性回歸模型，由式（1）、式（2）得：

定義：其中。

因此，上述一元線性回歸模型變成。

根據(jù)最小二乘法，要使殘差平方和達到最小才能達到最佳擬合曲線的標準：

殘差平方和如下：

通過最小確定最佳擬合直線，可視為以為變量關(guān)于的函數(shù)，即轉(zhuǎn)換為一個求極值的問題，可通過求倒數(shù)得到：

本文采用估計的方法[6]得出式（4），可實現(xiàn)節(jié)點與節(jié)點同步，同理在這個區(qū)域內(nèi)的其他節(jié)點也實現(xiàn)了與節(jié)點的同步而不需要發(fā)送其他信息，有效地節(jié)省了大部分能量。

3 幾種經(jīng)典時鐘同步方案的對比

該部分將提出的PBS與其他已提出的同步協(xié)議（例如TPSN，RBS和FTSP）針對能量消耗量（所需定時消息的數(shù)量）和同步精度進行比較。

令為同步過程所需的定時消息的數(shù)目，其中為網(wǎng)絡(luò)中整體傳感器節(jié)點的數(shù)目，則有以下4個結(jié)論。

結(jié)論1：

參考節(jié)點必須在RBS廣播信標包次。此外，每個傳感器節(jié)點必須在接收到廣播信標時與網(wǎng)絡(luò)中的所有其他節(jié)點一起發(fā)送時間讀數(shù)，以補償彼此之間的相對時鐘偏移。由于網(wǎng)絡(luò)中惟一對的數(shù)量為，因此[7]。

結(jié)論2：

由于網(wǎng)絡(luò)中的每個節(jié)點都連接到除參考節(jié)點之外的其父節(jié)點，所以在分層樹中存在個分支（邊）。此外，對于TPSN，在每個成對同步中需要個定時消息。TPSN中所需的定時消息的數(shù)目等于成對同步的數(shù)目乘以每個成對同步所需的定時消息的數(shù)目，因此[7]

結(jié)論3：

對于FTSP，每個傳感器節(jié)點必須在接收到信標（或廣播信標）時向其他節(jié)點發(fā)送其時間讀數(shù)，以便它們可以估計彼此之間的相對時鐘偏移。因此，F(xiàn)TSP中所需的定時消息的數(shù)目等于傳感器節(jié)點的數(shù)目乘以信標的數(shù)目[8]。

結(jié)論4：

本文提出的時間同步算法——成對廣播同步（PBS）在每個同步周期中僅需要個定時消息，因此，的大小不取決于網(wǎng)絡(luò)中的傳感器數(shù)量，這將會節(jié)省巨大的能量。此外，網(wǎng)絡(luò)規(guī)模越大，該優(yōu)勢越明顯。因此，PBS相對于RBS，TPSN和FTSP在能量節(jié)省方面有巨大的優(yōu)勢。

下面將通過計算克拉美羅界[9?10]來衡量本文提出的同步算法的精度。

式（3）用矩陣表示法可以表示為：

其中噪聲因子最小二乘估計得出可計算出費雪信息矩陣。

令，因此：

根據(jù)定義由費雪信息矩陣可計算出克拉美羅界如下：

通過Matlab進行仿真，結(jié)果如圖3所示，給出了PBS中所提出的時鐘偏移均方誤差（MSE）和克拉美羅界的對比，以及時鐘頻偏的均方誤差（MSE）和克拉美羅界的對比。

由圖3可知，克拉美羅界幾乎等于均方誤差，所以該無偏估計的性能是很好的。值得說明的是發(fā)送同步消息的次數(shù)的取值越大均方誤差越小，在該同步算法中盡量使相對于其他已提出的算法在能量節(jié)省方面有明顯的優(yōu)勢。

4 結(jié) 語

時鐘同步為無線傳感器網(wǎng)絡(luò)提供了公共的時間標準，從而為傳感器網(wǎng)絡(luò)節(jié)點的相互協(xié)作以及網(wǎng)絡(luò)的數(shù)據(jù)融合提供了基礎(chǔ)前提。所以，時鐘同步是無線傳感器網(wǎng)絡(luò)中最基本、最重要的問題之一。當前已有時鐘同步算法主要存在的問題是同步精度不高并對硬件節(jié)點的能耗要求比較大，實際應用中無線傳感器網(wǎng)絡(luò)節(jié)點并不是很方便更換電池，因此改進時鐘同步方案的主要目的旨在改善上述兩個問題。將本文提出的方法與三種經(jīng)典的時鐘同步算法進行比較，本文方法在有效節(jié)省能量的同時保證了時間同步的精度。

參考文獻

[1] 張玉強，何涇沙，徐晶，等.基于移動參考節(jié)點的無線傳感器時鐘同步方法[J].通信學報，2015，36（z1）：171?180.

ZHANG Yuqiang， HE Jingsha， XU Jing， et al. Time synchronization method for wireless sensor networks based on mobile reference nodes [J]. Journal on communications， 2015， 36（S1）： 171?180.

[2] 林曉鵬.無線傳感器網(wǎng)絡(luò)時間同步技術(shù)分析[J].智能計算機與應用，2016，6（2）：17?19.

LIN Xiaopeng. The analyzing of time synchronization technique for wireless sensor networks [J]. Intelligent computer and applications， 2016， 6（2）： 17?19.

[3] ELSON J， GIROD L， ESTRIN D. Fine?grained network time synchronization using reference broadcasts [C]// Proceedings of the 5th Symposium on Operating System Design and Implementation. Boston： ACM， 2002： 147?163.endprint

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

[5] 王樹寶，拱長青，王富良，等.TCP/IP網(wǎng)絡(luò)時間同步機制的誤差分析[J].計算機工程，2009，35（18）：111?112.

WANG Shubao， GONG Changqing， WANG Fuliang， et al. Error analysis of time synchronization mechanism in TCP/IP network [J]. Computer engineering， 2009， 35（18）： 111?112.

[6] 陳輝，熊輝，殷昌盛，等.基于無線傳感器網(wǎng)絡(luò)時鐘同步的定位算法研究[J].現(xiàn)代電子技術(shù)，2015，38（7）：23?27.

CHEN Hui， XIONG Hui， YIN Changsheng， et al. Survey on clock synchronization localization algorithm based on wireless sensor network [J]. Modern electronics technique， 2015， 38（7）： 23?27.

[7] 郝綱，莊毅.一種用于大規(guī)模無線傳感器網(wǎng)絡(luò)的時鐘同步算法[J].計算機科學，2015，42（12）：189?194.

HAO Gang， ZHUANG Yi. Time synchronization algorithm for large?scale wireless sensor networks [J]. Computer science， 2015， 42（12）： 189?194.

[8] 殷鵬.基于安全性的無線傳感器網(wǎng)絡(luò)時鐘同步算法研究[J].現(xiàn)代電子技術(shù)，2017，40（4）：151?154.

YIN Peng. Research on security?based clock synchronization algorithm for wireless sensor network [J]. Modern electronics technique， 2017， 40（4）： 151?154.

[9] 張安然.無線傳感網(wǎng)絡(luò)的FTSP時間同步算法優(yōu)化與實現(xiàn)[D].呼和浩特：內(nèi)蒙古大學，2017.

ZHANG Anran. Optimization and realization of flooding time synchronization protocol in wireless sensor network [D]. Hohhot： Inner Mongolia University， 2017.

[10] NAZ A， PIRANDA B， GOLDSTEIN S C， et al. A time synchronization protocol for modular robots [C]// Euromicro International Conference on Parallel， Distributed， and Network?Based Processing. [S.l.]： IEEE， 2016： 109?118.endprint