高精度低功耗無線傳感器網(wǎng)絡(luò)時(shí)間同步算法*

陳孟元，周 婭，郎 朗

(安徽工程大學(xué) 安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000)

高精度低功耗無線傳感器網(wǎng)絡(luò)時(shí)間同步算法*

陳孟元，周 婭，郎 朗

(安徽工程大學(xué) 安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000)

通過對(duì)無線傳感器網(wǎng)絡(luò)參考廣播同步(RBS)算法的研究，針對(duì)RBS多跳算法網(wǎng)絡(luò)開銷大和不能實(shí)現(xiàn)全網(wǎng)同步的問題，在基于環(huán)形網(wǎng)絡(luò)拓?fù)涞膮⒖紡V播環(huán)形同步(RBRS)算法基礎(chǔ)上,提出一種改進(jìn)的RBRS(IRBRS)算法。該算法引入可變周期同步法：根據(jù)貝葉斯最大后驗(yàn)估計(jì)原理，估算出最大相位偏差來決定同步周期，從而減少節(jié)點(diǎn)同步次數(shù)，并且采用最小二乘線性回歸法，周期性擬合時(shí)鐘偏移。運(yùn)用Matlab環(huán)境進(jìn)行仿真，仿真結(jié)果表明：IRBRS算法同步精度顯著提高，并且能量消耗顯著減少，更有利于延長無線傳感器網(wǎng)絡(luò)的壽命。

無線傳感器網(wǎng)絡(luò)；時(shí)間同步；多跳；參考廣播同步；誤差開銷分析

0 引 言

時(shí)間同步技術(shù)是無線傳感器網(wǎng)絡(luò)(WSNs)的關(guān)鍵技術(shù)。由于分布式結(jié)構(gòu)、硬件振蕩器以及物理層、介質(zhì)訪問層消息傳輸延遲的缺陷會(huì)導(dǎo)致時(shí)間不能同步[1],同時(shí)節(jié)點(diǎn)的時(shí)間同步對(duì)無線傳感器網(wǎng)絡(luò)中的能量管理、休眠調(diào)度、數(shù)據(jù)融合、定位追蹤以及安全協(xié)議等步驟起著關(guān)鍵作用[2]。因此，保持無線傳感器網(wǎng)絡(luò)各節(jié)點(diǎn)的時(shí)間同步有著現(xiàn)實(shí)的意義。在傳感器網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)計(jì)方面，傳感器網(wǎng)絡(luò)的壽命與電池容量呈正比，而且由于空間和其它操作的限制，能量不足會(huì)成為傳感器網(wǎng)絡(luò)的實(shí)際操作中的現(xiàn)實(shí)問題[3]。

不同的算法設(shè)計(jì)面向不同的應(yīng)用,傳感器網(wǎng)絡(luò)定時(shí)同步協(xié)議(timing-sync protocol for sensor networks,TPSN)算法是基于發(fā)送接收端之間的時(shí)間同步，算法時(shí)間精度，計(jì)算負(fù)荷小，但是魯棒性差，能耗較參考廣播同步(reference broadcast synchronization,RBS)算法大，不適應(yīng)拓?fù)浣Y(jié)構(gòu)的變化。本文旨在對(duì)中小型網(wǎng)絡(luò)實(shí)現(xiàn)全網(wǎng)的時(shí)間同步，針對(duì)RBS多跳算法網(wǎng)絡(luò)開銷大和不能實(shí)現(xiàn)全網(wǎng)同步的問題，提出一種改進(jìn)的參考廣播環(huán)形同步(improved references broadcast ring synchronization，IRBRS)算法。該算法引入可變周期同步法[4]：根據(jù)貝葉斯最大后驗(yàn)估計(jì)原理[5]，估算出最大相位偏差來決定同步周期[6]，從而減少節(jié)點(diǎn)同步次數(shù),并且采用最小二乘線性回歸法[7]，周期性擬合時(shí)鐘偏移，最終實(shí)現(xiàn)全網(wǎng)同步。

1 IRBRS算法

針對(duì)RBS多跳算法網(wǎng)絡(luò)開銷大和不能實(shí)現(xiàn)全網(wǎng)同步的問題，在RBRS算法基礎(chǔ)上，IRBRS算法分兩步實(shí)現(xiàn)網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的同步。首先進(jìn)行可變周期同步法，采用最大后驗(yàn)估計(jì)法估計(jì)出最大相位偏差，進(jìn)而調(diào)整算法的同步周期，然后采用最小二乘線性擬合對(duì)時(shí)間偏差和頻率偏差進(jìn)行補(bǔ)償，最終得到一種多跳高精度低功耗的IRBRS算法。

1.1 可變周期同步

(1)

其中，樣本的概率密度相乘得

-∞<φi<∞,i=1,2,…,n.

(2)

先驗(yàn)分布為

(3)

邊際分布為

(4)

對(duì)式(1)取對(duì)數(shù)

lnπ(φ/φi)=lnf(φi/φ)+lnπ(φ)-lng(φi).

(5)

將式(2)、式(3)、式(4)帶入式(5)，對(duì)φ求偏導(dǎo)得

(6)

(7)

則

(8)

式(8)計(jì)算最大的相位偏差估計(jì)量。根據(jù)本次同步的最大相位偏差估計(jì)量，可計(jì)算出下次同步周期。

設(shè)網(wǎng)絡(luò)要求的同步精度為a，在第n-1同步過程中，最大的傳輸時(shí)延為Tmax，同步周期為Tn-1，并且其同步的最大相位偏差為βmax，T為預(yù)計(jì)更新周期,則根據(jù)

(9)

可求出預(yù)計(jì)更新周期

(10)

下一次更新周期為

(11)

式中j1，j2為調(diào)節(jié)因子，j1+j2=1。在預(yù)計(jì)更新周期T和歷史統(tǒng)計(jì)周期Tn-1之間權(quán)衡計(jì)算，生成本次實(shí)際更新周期。

一般將最大相位偏差估計(jì)量作為一個(gè)比較相位偏差，以這個(gè)相位偏差值為標(biāo)準(zhǔn)來決定同步的次數(shù)。如果本次的最大時(shí)鐘偏移量較小時(shí)，則將下次的同步周期按比例加長;如果本次的最大時(shí)鐘偏移量較大時(shí)，則將下次的同步周期按比例縮短。同步次數(shù)減少，能耗降低。

1.2 相位偏差估計(jì)

RBS算法采用廣播的特性發(fā)送消息，消除了來自發(fā)送端的發(fā)送時(shí)延和接收時(shí)延的不確定性。節(jié)點(diǎn)訪問到信道后，空氣中的通信時(shí)延即傳播時(shí)延可以忽略。接收時(shí)延包括接收數(shù)據(jù)包、編碼以及上報(bào)操作系統(tǒng)的時(shí)間，隨著時(shí)鐘頻率的漂移和初始相位偏差的不同，使得各個(gè)節(jié)點(diǎn)的本地時(shí)鐘不同，各個(gè)節(jié)點(diǎn)間接收時(shí)延會(huì)有偏差[10]。圖1為節(jié)點(diǎn)同步時(shí)延圖。

圖1 節(jié)點(diǎn)同步時(shí)延Fig 1 Simultaneous delay of nodes

因此，需要對(duì)時(shí)鐘頻率偏移和初始相位偏差進(jìn)行估計(jì),可以采用最小二乘線性擬合法。

節(jié)點(diǎn)A1和A2之間的本地時(shí)鐘關(guān)系為

tim=aijtjm+bij+ε.

(12)

其中，aij為節(jié)點(diǎn)A1相對(duì)于節(jié)點(diǎn)A2的頻率偏差；bij為兩個(gè)節(jié)點(diǎn)本地時(shí)鐘的初始相位偏差；ε就是兩節(jié)點(diǎn)接受同一個(gè)分組的時(shí)間偏差，服從期望為0，方差為σ2的正態(tài)分布，具體的推算過程如下：

一般采用最小二乘方法估計(jì)模型式(13)中的aij，bij，令

(13)

(14)

(15)

這組方程稱為正規(guī)方程組，經(jīng)過整理，可得

(16)

最終求得其結(jié)果為

(17)

(18)

a12，b12即完成了兩節(jié)點(diǎn)時(shí)鐘漂移的補(bǔ)償，但是a12，b12解決的是兩節(jié)點(diǎn)間瞬時(shí)的時(shí)間漂移。

2 算法仿真分析

為了驗(yàn)證算法的有效性，采用Matlab軟件進(jìn)行仿真。在一個(gè)類似于算法的網(wǎng)絡(luò)拓?fù)湫螤顢[放24個(gè)基于IEEE 802.15.4的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行同步實(shí)驗(yàn)。數(shù)據(jù)傳輸速率為50 kB/s，數(shù)據(jù)包大小約為10 kbit。文獻(xiàn)[11]已對(duì)4跳的線性網(wǎng)絡(luò)對(duì)RBS算法進(jìn)行了模擬。為了更好地比較RBS算法和IRBRS算法，將繼續(xù)在4跳的線性網(wǎng)絡(luò)上模擬IRBRS算法。

IRBRS算法首先采用最大后驗(yàn)估計(jì)法估算出最大相位偏差，并通過最大相位偏差估算同步周期值。在不同的周期值內(nèi)，發(fā)送的同步消息量不一樣，從而導(dǎo)致了不一樣的同步精度值和能量消耗。文獻(xiàn)[8]中，Elson J等人通過實(shí)驗(yàn)得出相位偏差服從u=0，σ=11.1的正態(tài)分布，其中最大相位偏移為53.4 μs。根據(jù)最大相位偏差，同步周期內(nèi)最大的相位偏差總小于或等于總體相位偏差。因此，IRBRS算法同步周期小于或等于RBS算法的最大同步周期。假設(shè)RBS算法最大同步周期為600 ms，第一次IRBRS算法的同步周期為300 ms。根據(jù)實(shí)際的運(yùn)作情況，圖2顯示了兩種算法的同步周期情況。

圖2 同步周期顯示Fig 2 Indication of simultaneous cycles

如果同步周期長，同步的次數(shù)多，同步誤差精準(zhǔn)度就越高，因此，下次的同步周期便減小;反之，下次的同步周期就變長。

同步周期的長短和能量消耗值緊密相關(guān)。IRBRS算法和RBS算法的傳輸機(jī)制一致，只是傳輸方式不同。由圖2可以看出:RBS算法的同步周期比動(dòng)態(tài)的IRBRS同步周期大。如圖3為各算法能耗對(duì)比圖，IRBRS算法能耗少于RBS的50%，而TPSN 算法在相應(yīng)節(jié)點(diǎn)數(shù)量下的能耗最大。

圖3 三種算法能耗對(duì)比Fig 3 Comparison of energy consumption of three kinds of algorithms

通過最大后驗(yàn)估計(jì)法估算出同步周期，在不同的同步周期內(nèi)，采集時(shí)間信息,再將這些時(shí)間信息用最小二乘法線性擬合，比較算法的精度，如圖4。

圖4 三種算法精度對(duì)比Fig 4 Comparison of precision of three kinds of algorithms

上述通過仿真得出RBS算法和RBRS算法的同步累積誤差相近。IRBRS算法就是在RBRS算法基礎(chǔ)上進(jìn)行優(yōu)化，4跳結(jié)束后，RBS和RBRS的平均誤差分別為70.30 μs和81.26 μs，而IRBRS算法的平均誤差只有59.87 μs。可以看出：IRBRS算法累積誤差明顯降低，即同步精度提高。

3 結(jié)束語

在經(jīng)典RBS算法基礎(chǔ)上提出RBRS算法雖比較新穎，還沒有達(dá)到最優(yōu)化。本文首先通過可變周期的想法，結(jié)合最大后驗(yàn)估計(jì)法，估算出算法的最大相位偏差，從而改變了算法的同步周期，降低了節(jié)點(diǎn)能耗；其次，采用最小二乘法，對(duì)周期值內(nèi)的時(shí)間值進(jìn)行線性擬合，完成對(duì)相位偏移和頻率偏移的補(bǔ)償，從而完成了整個(gè)同步過程。理論分析和仿真結(jié)果表明：IRBRS算法在能耗和同步精度方面均優(yōu)于RBS和RBRS算法，適用于中小型無線傳感器網(wǎng)絡(luò)，增強(qiáng)了網(wǎng)絡(luò)時(shí)間同步的可靠性。

[1] 孫利民，李建中.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2] Sivrikaya F,Yener B.Time synchronization in sensor networks: A survey[J].IEEE Network，2004,18(4):45-50.

[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,MA:ACM,2002:147-163.

[4] Ren F Y，Huang H N，Lin C． Wireless sensor networks[J]． Journal of Software，2003，4(7) : 1282-1291．

[5] 王義君，錢志鴻，王桂琴,等.無線傳感器網(wǎng)絡(luò)能量有效時(shí)間同步算法研究[J].電子與信息學(xué)報(bào)，2012，34(9)：2174-2179.

[6] 齊 華，王 恒，劉 軍.可變周期的基于貝葉斯估計(jì)的 TPSN 改進(jìn)算法[J].傳感技術(shù)學(xué)報(bào)，2013，26(3)：407-410.

[7] 譚 勵(lì).無線傳感器網(wǎng)絡(luò)理論與技術(shù)應(yīng)用[M].北京：機(jī)械工業(yè)出版社，2011.

[8] Elson J,Estrin D.Time synchronization for wireless sensor networks,parallel and distributed processing symposium[C]∥Proceedings of 15th International .Parallel and Distributed Processing Symposium,San Francisco,USA,2001:1965-1970.

[9] Walpole Ronald,Myers Raymond H.周 勇，等譯.理工科概率統(tǒng)計(jì)[M].北京：機(jī)械工業(yè)出版社，2009.

[10] Gradowska P L,Cooke R M.Least squares type estimation for Cox regression model and specification error[J].Computational Statistics & Data Analysis,2012,56(7):2288-2302.

[11] Sichitiu M L,Veerarittiphan C.Simple,accurate time synchronization for wireless sensor networks[C]∥Proc of the IEEE Wireless Communications and Networking Conf,2003.

High precision and low power consumption time synchronization algorithm for wireless sensor networks*

CHEN Meng-yuan, ZHOU Ya, LANG Lang

(Anhui Polytechnic University,Anhui Key Laboratory of Electric Drive and Control,Wuhu 241000,China)

Through research of reference broadcast synchronization(RBS) algorithms for wireless sensor networks(WSNs),aiming at problem of large amount of network overhead and the whole network synchronization,an algorithm based on references broadcast ring synchronization(RBRS) is presented,named improved RBRS(IRBRS) algorithm.The algorithm lead into variable cycle synchronization method.According to principle of Bayesian maximum posterior estimation,estimate the maximum phase offset to determine synchronization cycle to reduce the number of node synchronization,it also can fit clock skew periodically by least square linear regression method.Matlab software is used for simulation,results show that IRBRS algorithm synchronous precision is improved obviously and reduce energy consumption significantly to be better for extend life of wireless sensor networks.

wireless sensor networks(WSNs); time synchronization; multi-hop; reference broadcast synchronization(RBS); error overhead analysis

10.13873/J.1000—9787(2014)10—0125—03

2014—07—09

安徽省自然科學(xué)基金資助項(xiàng)目(11040606M153);安徽高校省級(jí)自然科學(xué)研究項(xiàng)目(KJ2013A041)

TP 393；TP 391

A

1000—9787(2014)10—0125—03

陳孟元(1984-)，男，安徽蕪湖人，碩士，講師，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)的優(yōu)化與時(shí)間同步。