劉學(xué)超+郭改枝+潘亮

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

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

中圖分類(lèi)號(hào)： TN915.02?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ú)線傳感器網(wǎng)絡(luò)（WSN）逐漸在各領(lǐng)域中被廣泛的應(yīng)用，微機(jī)電系統(tǒng)（MEMS）、數(shù)字電路設(shè)計(jì)和無(wú)線通信的發(fā)展給無(wú)線傳感網(wǎng)絡(luò)的普及提供了很多便利條件。無(wú)線傳感器網(wǎng)絡(luò)將會(huì)是未來(lái)通信環(huán)境的基礎(chǔ)設(shè)施，一個(gè)新的問(wèn)題隨之產(chǎn)生，即網(wǎng)絡(luò)同步問(wèn)題。無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步對(duì)于維持?jǐn)?shù)據(jù)的一致性、協(xié)調(diào)性以及執(zhí)行其他基本操作都至關(guān)重要[1]。

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

1 主要思想

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

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

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

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

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

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

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

式中：代表之間的相對(duì)時(shí)鐘偏移；代表之間的相對(duì)時(shí)鐘頻偏。

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

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

定義：其中。

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

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

殘差平方和如下：

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

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

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

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

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

結(jié)論1：

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

結(jié)論2：

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

結(jié)論3：

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

結(jié)論4：

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

下面將通過(guò)計(jì)算克拉美羅界[9?10]來(lái)衡量本文提出的同步算法的精度。

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

其中噪聲因子最小二乘估計(jì)得出可計(jì)算出費(fèi)雪信息矩陣。

令，因此：

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[1] 張玉強(qiáng)，何涇沙，徐晶，等.基于移動(dòng)參考節(jié)點(diǎn)的無(wú)線傳感器時(shí)鐘同步方法[J].通信學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)分析[J].智能計(jì)算機(jī)與應(yīng)用，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] 王樹(shù)寶，拱長(zhǎng)青，王富良，等.TCP/IP網(wǎng)絡(luò)時(shí)間同步機(jī)制的誤差分析[J].計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)時(shí)鐘同步的定位算法研究[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ú)線傳感器網(wǎng)絡(luò)的時(shí)鐘同步算法[J].計(jì)算機(jī)科學(xué)，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ú)線傳感器網(wǎng)絡(luò)時(shí)鐘同步算法研究[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ú)線傳感網(wǎng)絡(luò)的FTSP時(shí)間同步算法優(yōu)化與實(shí)現(xiàn)[D].呼和浩特：內(nèi)蒙古大學(xué)，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