姜　帆， 鄭　霖

(1.無線寬帶與信號處理重點實驗室，廣西 桂林 541004；2.桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

?

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

姜帆1,2， 鄭霖1,2

(1.無線寬帶與信號處理重點實驗室，廣西 桂林 541004；2.桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

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

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

0引言

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

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

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

1算法模型

1.1時鐘模型

節(jié)點i的本地時鐘可表示為

(1)

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

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

1.2基于鄰節(jié)點信息的時鐘同步模型

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

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

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

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

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

圖3　時間信息傳輸模型Fig 3　Time information transmission model

下面對加權(quán)最小二乘估計法在該時間同步算法中的應用進行推導說明。

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

(2)

由上述方程可以推出

(3)

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

節(jié)點A和節(jié)點P被動收聽節(jié)點B和C廣播的消息，最后節(jié)點P把標記的收聽時間發(fā)送回給節(jié)點A時，對于節(jié)點A就可以看作RBS同步過程，根據(jù)節(jié)點A所得到的時間同步消息，可以得到下面的方程

(4)

由上面兩個方程可以推出

(5)

由于

(6)

式(6)可以寫成

(7)

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

(8)

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

(9)

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

令

(10)

AX+e=B.

(11)

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

2算法描述

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

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

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

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

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

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

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

3克拉美羅下界分析

在實際應用中，估計的最佳性能可以通過一個下界得到?？死懒_下界(Cramér-Rao lower bound,CRLB)表述了無偏估計量理論上所能達到的最小方差

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

(12)

通?？梢岳霉烙嬃孔陨淼母怕史植己瘮?shù)(probability distribution function,PDF)來計算得到。

在式(11)中，有

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

(13)

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

(14)

考慮CRLB，定義矩陣I為

(15)

將上式簡化可得到

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

(16)

I為費雪信息矩陣，因此

(17)

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

4仿真分析

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

4.1算法性能比較

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

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

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

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

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

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

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

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

4.2MSE仿真分析

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

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

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

5結(jié)束語

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

參考文獻:

[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].北京:清華大學出版社,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)域為無線傳感器網(wǎng)絡。

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

作者簡介:

中圖分類號：TP 393

文獻標識碼：A

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

*基金項目：國家自然科學基金資助項目(61362006)；省部共建教育部重點實驗室認知無線電基金資助項目(2013ZR08)；2014年度廣西高?？茖W技術(shù)研究項目(YB2014137)

收稿日期：2015—03—30

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