姜　帆， 鄭　霖

(1.無(wú)線寬帶與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004；2.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

?

無(wú)線傳感器網(wǎng)絡(luò)TPSN-RBS聯(lián)合時(shí)間同步算法*

姜帆1,2， 鄭霖1,2

(1.無(wú)線寬帶與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004；2.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

摘要:針對(duì)大規(guī)模多跳傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間所存在的同步誤差及其累積誤差問(wèn)題，提出了一種基于加權(quán)最小二乘法的TPSN-RBS聯(lián)合時(shí)間同步算法。該算法充分利用可監(jiān)聽(tīng)到的消息，通過(guò)加權(quán)最小二乘法估計(jì)得到節(jié)點(diǎn)邏輯時(shí)鐘的時(shí)間偏移和頻率偏移的最優(yōu)解。用Cramér-Rao下界對(duì)本算法進(jìn)行性能分析，同時(shí)與TPSN算法進(jìn)行仿真對(duì)比，結(jié)果表明:該算法提高了節(jié)點(diǎn)間的同步精度，且在節(jié)點(diǎn)密集的大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中，在保證較低通信量的同時(shí)降低了累積誤差。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)； 時(shí)間同步； 加權(quán)最小二乘法

0引言

時(shí)間同步是無(wú)線傳感器網(wǎng)絡(luò)(WSNs) 的一項(xiàng)重要支撐技術(shù)，時(shí)間同步在很多方面都有廣泛的應(yīng)用。從目前的研究成果來(lái)看，無(wú)線傳感的網(wǎng)絡(luò)中的時(shí)間同步技術(shù)主要可以分為基于發(fā)送者—接收者的同步 (sender-receiver synchronization,SRS)機(jī)制[1]，這種算法單跳同步精度比較高，但是需要多次的時(shí)間信息收發(fā)，因此,需要較大的通信量和存儲(chǔ)空間?；诮邮照叩耐?receiver-only synchronization,ROS)[2]，以及基于接收者—接收者的同步 (receiver-recei-ver synchronization,RRS)機(jī)制[3]，這些算法很難做到同時(shí)兼顧同步精度和能耗，且這些算法的同步誤差隨跳距累積，難以擴(kuò)展到大規(guī)模高密度無(wú)線傳感器網(wǎng)絡(luò)。針對(duì)上述問(wèn)題，研究者分別從兩方面對(duì)時(shí)間同步算法進(jìn)行改進(jìn):一是在成對(duì)節(jié)點(diǎn)間將最優(yōu)融合估計(jì)引入到時(shí)間偏移和相位偏移的估計(jì)中，如最大似然估計(jì)[4,5]、最小二乘估計(jì)[6,7]以及卡爾曼濾波[8,9];二是改進(jìn)全網(wǎng)時(shí)間同步協(xié)議[10,11]來(lái)達(dá)到提高時(shí)間同步性能的目的。

常用最優(yōu)融合估計(jì)的有：最小二乘估計(jì)、線性最小方差估計(jì)、極大后驗(yàn)估計(jì)、Bayes估計(jì)以及極大似然估計(jì)等[12]。最小二乘估計(jì)使用的最優(yōu)指標(biāo)是使兩側(cè)估計(jì)的精度達(dá)到最佳，估計(jì)中不必使用與被估計(jì)量有關(guān)的動(dòng)態(tài)信息與統(tǒng)計(jì)信息。該方法的最大優(yōu)點(diǎn)是算法簡(jiǎn)單，在對(duì)被估計(jì)量和量測(cè)誤差缺乏了解的情況下仍能使用。

本文基于加權(quán)最小二乘法，提出了一種無(wú)線傳感器網(wǎng)絡(luò)TPSN-RBS聯(lián)合時(shí)間同步算法。它利用傳感器節(jié)點(diǎn)時(shí)間同步協(xié)議(timing-sync protocol for sensor networks，TPSN)的單跳同步精度高的優(yōu)點(diǎn)和參考廣播同步 (reference broadcast synchronization，RBS) 算法通信量低的優(yōu)點(diǎn)，同時(shí)結(jié)合了加權(quán)最小二乘估計(jì)，對(duì)節(jié)點(diǎn)的時(shí)間偏移和頻率偏移同時(shí)進(jìn)行同步。該算法在降低了通信量的基礎(chǔ)上，提高了單跳同步的精度，并且在大規(guī)模網(wǎng)絡(luò)中，降低了時(shí)間同步的累積誤差。

1算法模型

1.1時(shí)鐘模型

節(jié)點(diǎn)i的本地時(shí)鐘可表示為

(1)

其中，fi(t)為節(jié)點(diǎn)i本地時(shí)鐘的頻率偏差，t0為初始時(shí)刻，Ti(t0)為節(jié)點(diǎn)在t0時(shí)刻的本地時(shí)間。

在每個(gè)節(jié)點(diǎn)內(nèi)有一個(gè)本地時(shí)鐘和邏輯時(shí)鐘。同步算法就是要使所有節(jié)點(diǎn)的邏輯時(shí)鐘值同步。

1.2基于鄰節(jié)點(diǎn)信息的時(shí)鐘同步模型

本文中的算法結(jié)合了TPSN和RBS兩種算法，兼顧了同步精度和通信量，同時(shí)降低了集中式網(wǎng)絡(luò)層次結(jié)構(gòu)中的累積誤差。

圖1為整體網(wǎng)絡(luò)結(jié)構(gòu);圖2為整體網(wǎng)絡(luò)結(jié)構(gòu)中的參考節(jié)點(diǎn)和下層節(jié)點(diǎn)之間的連接情況，參考節(jié)點(diǎn)P和下層節(jié)點(diǎn)A，B，C都在彼此的通信范圍內(nèi)，它是整體網(wǎng)絡(luò)結(jié)構(gòu)中的一個(gè)典型的上下層節(jié)點(diǎn)連接結(jié)構(gòu)。因此，在闡述該算法時(shí)，皆以此結(jié)構(gòu)為例。

圖1　整體網(wǎng)絡(luò)結(jié)構(gòu)Fig 1　Overall network structure

圖2　部分網(wǎng)絡(luò)結(jié)構(gòu)Fig 2　Part of the network structure

圖3所示即為時(shí)間信息傳播模型，在一個(gè)同步周期內(nèi)的時(shí)鐘消息發(fā)送情況。下層節(jié)點(diǎn)A,B,C分別給在其廣播范圍內(nèi)的其他節(jié)點(diǎn)廣播時(shí)鐘信息，接收節(jié)點(diǎn)記錄下接收到的消息。在下層節(jié)點(diǎn)結(jié)束廣播消息時(shí)，參考節(jié)點(diǎn)P將接收到下層節(jié)點(diǎn)的消息時(shí)所記錄下的時(shí)間廣播發(fā)送給下層節(jié)點(diǎn)。待同步節(jié)點(diǎn)最后收到參考節(jié)點(diǎn)發(fā)送過(guò)來(lái)的消息時(shí)，同時(shí)完成了TPSN算法和RBS算法，最后一個(gè)接收到的數(shù)據(jù)包包含了TPSN算法和RBS算法所需要的信息。

圖3　時(shí)間信息傳輸模型Fig 3　Time information transmission model

下面對(duì)加權(quán)最小二乘估計(jì)法在該時(shí)間同步算法中的應(yīng)用進(jìn)行推導(dǎo)說(shuō)明。

在時(shí)間同步過(guò)程中，根據(jù)TPSN同步原理，通過(guò)節(jié)點(diǎn)A和節(jié)點(diǎn)P的信息交換，可以得到下面兩個(gè)方程

(2)

由上述方程可以推出

(3)

其中，f′=1/fPA，fPA=fP/fA，φ′=φPA/fPA,φPA=φA-φP，D為傳輸延遲中的固定傳輸延遲，d1和d2為隨機(jī)傳輸延遲。

節(jié)點(diǎn)A和節(jié)點(diǎn)P被動(dòng)收聽(tīng)節(jié)點(diǎn)B和C廣播的消息，最后節(jié)點(diǎn)P把標(biāo)記的收聽(tīng)時(shí)間發(fā)送回給節(jié)點(diǎn)A時(shí)，對(duì)于節(jié)點(diǎn)A就可以看作RBS同步過(guò)程，根據(jù)節(jié)點(diǎn)A所得到的時(shí)間同步消息，可以得到下面的方程

(4)

由上面兩個(gè)方程可以推出

(5)

由于

(6)

式(6)可以寫成

(7)

同理，在節(jié)點(diǎn)C廣播時(shí)間同步消息時(shí)，節(jié)點(diǎn)A可以得到一個(gè)類似的方程

(8)

因此，通過(guò)上述討論，由式(3)、式(7)、式(8)可以得到以下一組方程組

(9)

這是一組關(guān)于未知量f′和φ′的矛盾方程組，即方程的數(shù)量大于未知量的數(shù)量。下面使用加權(quán)最小二乘方法對(duì)于這個(gè)矛盾方程組進(jìn)行求解。

令

(10)

AX+e=B.

(11)

計(jì)算得到f′和φ′，對(duì)節(jié)點(diǎn)中的全局參考時(shí)鐘的頻偏和相偏進(jìn)行校正。

2算法描述

節(jié)點(diǎn)i執(zhí)行的算法迭代過(guò)程如下：

1)在初始時(shí)刻n=0初始化節(jié)點(diǎn)初始頻率相位信息；

2)構(gòu)建節(jié)點(diǎn)網(wǎng)絡(luò)，給節(jié)點(diǎn)i分配能接收到消息的上層節(jié)點(diǎn)和同層節(jié)點(diǎn)；

3)在一個(gè)時(shí)間周期內(nèi)，從根節(jié)點(diǎn)開(kāi)始，下層節(jié)點(diǎn)首先廣播時(shí)間同步消息；

4)下層節(jié)點(diǎn)廣播消息結(jié)束，上層節(jié)點(diǎn)廣播時(shí)間同步消息；

5)每個(gè)下層節(jié)點(diǎn)根據(jù)記錄的發(fā)送時(shí)間和接收時(shí)間，使用加權(quán)最小二乘法同時(shí)估計(jì)頻偏和相偏；

6)校正本地頻偏和相偏。

3克拉美羅下界分析

在實(shí)際應(yīng)用中，估計(jì)的最佳性能可以通過(guò)一個(gè)下界得到。克拉美羅下界(Cramér-Rao lower bound,CRLB)表述了無(wú)偏估計(jì)量理論上所能達(dá)到的最小方差

其中,I(θ)為費(fèi)雪信息量(Fisher information)，定義為

(12)

通常可以利用估計(jì)量自身的概率分布函數(shù)(probability distribution function,PDF)來(lái)計(jì)算得到。

在式(11)中，有

式(11)可以寫成e=B-AX,e的協(xié)方差矩陣為

(13)

在未知矢量上，有聯(lián)合似然函數(shù)

(14)

考慮CRLB，定義矩陣I為

(15)

將上式簡(jiǎn)化可得到

I=A-1Ce(AT)-1.

(16)

I為費(fèi)雪信息矩陣，因此

(17)

在式(17)中，頻率偏移估計(jì)的均方誤差中包含瞬時(shí)時(shí)間分量。

4仿真分析

利用Matlab仿真軟件對(duì)算法進(jìn)行數(shù)值仿真。該算法從全網(wǎng)同步誤差、多跳累積誤差和通信量三個(gè)方面與TPSN算法進(jìn)行比較。

4.1算法性能比較

圖4為一個(gè)6層網(wǎng)絡(luò)中節(jié)點(diǎn)的連接情況。將位于第1行第1列的節(jié)點(diǎn)作為參考節(jié)點(diǎn)，觀察全網(wǎng)節(jié)點(diǎn)的平均誤差隨時(shí)間的變化情況。

圖4　網(wǎng)絡(luò)節(jié)點(diǎn)連接情況Fig 4　Connectivity of network node

圖5表示了兩種算法的全網(wǎng)節(jié)點(diǎn)誤差的均方誤差(mean square error,MSE)隨著時(shí)間同步周期的變化而變化情況。從圖中可以看出，最小二乘時(shí)間同步(least square time synchronization,LSTS)LSTS算法的全網(wǎng)節(jié)點(diǎn)誤差在經(jīng)過(guò)了一段時(shí)間的同步之后，平均誤差趨于穩(wěn)定，且誤差的MSE為0.1 μs。

圖5　LSTS算法和TPSN算法全網(wǎng)節(jié)點(diǎn)平均誤差的MSE對(duì)比Fig 5　Comparison of MSE of entire network nodes averageerror between LSTS algorithm and TPSN algorithm

圖6表示了兩種算法累積誤差的均方誤差的對(duì)比，可以看出: LSTS算法的累計(jì)誤差比TPSN算法的累計(jì)誤差小2個(gè)數(shù)量級(jí)。

圖6　LSTS算法和TPSN算法累計(jì)誤差的MSE對(duì)比Fig 6　Comparison of MSE of accumulative error between LSTS algorithm and TPSN algorithm

下面來(lái)分析兩種算法在通信量上的對(duì)比。從圖4網(wǎng)絡(luò)節(jié)點(diǎn)連接圖中可以得到在第n層中有2n-1個(gè)節(jié)點(diǎn)，從第n層節(jié)點(diǎn)和第n+1層節(jié)點(diǎn)在兩種算法中的通信過(guò)程來(lái)分析。假設(shè)n≥2，在LSTS算法中，在一個(gè)同步周期內(nèi)，每個(gè)節(jié)點(diǎn)僅廣播一次時(shí)間信息消息，那么,LSTS算法的通信量可以表示成(2n-1)+(2n+1)=4n。在TPSN算法中，每個(gè)下層節(jié)點(diǎn)都要同它的每一個(gè)上層鄰節(jié)點(diǎn)有一次時(shí)間信息交換，由網(wǎng)絡(luò)節(jié)點(diǎn)連接圖中可以得到n+1層節(jié)點(diǎn)與n層節(jié)點(diǎn)的連接關(guān)系，則TPSN算法的通信量可以表示成2(1+4×2+(2n+1-5)×3)=12n-6。對(duì)于全網(wǎng)節(jié)點(diǎn)來(lái)說(shuō)，兩種算法的通信量關(guān)系也是如此。

從上述分析中可以看出:LSTS算法中是通過(guò)廣播的方式來(lái)傳遞時(shí)間信息，因此，LSTS算法與TPSN算法相比，通信量大大降低。

4.2MSE仿真分析

圖7和圖8分別表示隨著觀測(cè)節(jié)點(diǎn)層數(shù)的遞增，LSTS算法估計(jì)的相位偏移和頻率偏移MSE與CRLB的對(duì)比。仿真結(jié)果表明:LSTS算法估計(jì)的相位偏移和頻率偏移MSE隨觀測(cè)節(jié)點(diǎn)數(shù)變化的趨勢(shì)與CRLB相同，并且，相位偏移和頻率偏移MSE略大于CRLB。

圖7　CRLB和LSTS算法的相位偏移MSE對(duì)比Fig 7　Comparison of phase offset MSE between CRLBand LSTS algorithms

圖8　CRLB和LSTS算法的頻率偏移MSE對(duì)比Fig 8　Comparison of frequency offset MSE betweenLSTS and CRLB algorithms

5結(jié)束語(yǔ)

信息融合算法對(duì)于無(wú)線傳感器網(wǎng)絡(luò)中同步中相差和頻差的估計(jì)具有較高的準(zhǔn)確度。本文提出了一種基于加權(quán)最小二乘法的TPSN-RBS聯(lián)合時(shí)間同步算法LSTS。該算法充分利用了可監(jiān)聽(tīng)到的時(shí)間信息，在單跳同步中具有較高的精度，在大規(guī)模多跳網(wǎng)絡(luò)中具有較小的累積誤差，與傳統(tǒng)同步算法相比，降低了通信量。

參考文獻(xiàn):

[1]Ganeriwal S,Kumar R,Sribastava M B.Timing-sync protocol for sensor networks[C]∥Proceedings of the 1st International Conference on Embedded Networked Sensor System,Los Angeles,California,USA,2003:138-139.

[2]Maroti M,Kusy B,Simon G,et al.The flooding time synchronization protocol[C]∥Proceedings of the 2nd International Confe-rence on Embedded Networked Sensor System,Baltimore,USA,2004:39-49.

[3]Elson J,Girod L,Estrin D.Fine-griained network time synchronization using reference broadcasts[C]∥Proceedings of the 5th Symposium on Operating System Design and Implementation,Boston,MA,2002:147-163.

[4]Tian X,Miao Y,Hu T,et al.Maximum likelihood estimation based on time synchronization algorithm for wireless sensor networks[C]∥2009 ISECS International Colloquium on Computing,Communication,Control and Management,CCCM 2009,2009:416-420.

[5]Cao X,Yang F,Gan X,et al.Joint estimation of clock skew and offset in pairwise broadcast synchronization mechanism[J].IEEE Transaction on Communications,2013,61(6):2508-2521.

[6]Chepuri S P,Rajan R T,Leus G,et al.Joint clock synchronization and raning:Asymmetrical time-stamping and passive listening[J].IEEE Signal Processing Letters,2013,20(1):51-54.

[7]Akhlaq M,Sheltami T R. RTSP:An accurate and energy-efficient protocol for clock synchronization in WSNs[J].IEEE Transactions on Instrumentation and Measurement,2013,62(3):578-589.

[8]Xu X,Xiong Z,Sheng X,et al.A new time synchronization method for reducing quantization error accumulation over real-time networks:Theory and experiments[J].IEEE Transaction on Industrial Informatics,2013,9(3):1659-1669.

[9]Giorgi G.An event-based Kalman filter for clock synchro-nization[J].IEEE Transactions on Instrumentation and Measurement,2015,64(2):449-457.

[10] Yildirim K S,Kantarci A.Timing synchronization based on slow-flooding in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(1):244-253.

[11] Chang Q,Zhang M,Yao M.A new energy-efficient timing synchronization protocol in wireless sensor networks[C]∥2014 IEEE International Conference on Computer and Information Technology(CIT),2014:684-688.

[12] 韓崇昭,朱洪艷,段戰(zhàn)勝.多元信息融合[M].北京:清華大學(xué)出版社,2006:231-236.

[13] Kyoung-lae Noh,Chaudhari Q M,Serpedin E,et al.Novel clock phase offset and skew estimation using two-way timing message exchanges for wireless sensor networks[J].IEEE Transactions on Communications,2007,55(4):766-777.

[14] Leng M,Wu Y.On cock synchronization algorithms for wireless sensor networks under unknown delay[J].IEEE Transactions on Vehicular Technology,2010,59(1):182-190.

姜帆(1989-)，女，遼寧撫順人，碩士研究生，主要研究領(lǐng)域?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。

TPSN-RBS joint time synchronization algorithm for wireless sensor networks*

JIANG Fan1,2， ZHENG Lin1,2

(1.Key Laboratory of Wireless Wideband Communication and Signal Processing, Guilin 541004,China； 2.School of Information and Communication Engineering, Guilin University of Electronic Technology,Guilin 541004,China)

Abstract:A TPSN-RBS joint time synchronization algorithm based on weighted least square method is proposed,aiming at synchronization errors and its calculative errors existing between massive multiple hops sensor network nodes.The optimal solution for the time offset and frequency offset of logical clock of node is obtained by weighted least square method,using messages that can be heard.The Cramér-Rao lower bound is used for performance analysis,and compared with the TPSN algorithm,the simulation results show that,the synchronization precision between nodes is improved,and in large-scale wireless sensor networks with dense nodes,assure lower communication traffic,at the sometime cumulative errors are reduced.

Key words:wireless sensor networks(WSNs); time synchronization; weighted least square method

作者簡(jiǎn)介:

中圖分類號(hào)：TP 393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1000—9787(2016)01—0149—04

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61362006)；省部共建教育部重點(diǎn)實(shí)驗(yàn)室認(rèn)知無(wú)線電基金資助項(xiàng)目(2013ZR08)；2014年度廣西高?？茖W(xué)技術(shù)研究項(xiàng)目(YB2014137)

收稿日期：2015—03—30

DOI:10.13873/J.1000—9787(2016)01—0149—04