可變周期的基于貝葉斯估計(jì)的TPSN改進(jìn)算法*

齊 華，王 恒，劉 軍

(1．西安工業(yè)大學(xué)電子信息工程學(xué)院，西安710021;2．武警工程大學(xué)信息工程系，西安710086)

1 TPSN算法原理

TPSN(Timing-sync Protocol for Sensor Networks)[3－4]是美國(guó)學(xué)者 Ganeriwal等人提出的一種提供無線傳感器網(wǎng)絡(luò)全網(wǎng)范圍內(nèi)節(jié)點(diǎn)同步的時(shí)間同步算法。其同步過程分為兩個(gè)階段來實(shí)現(xiàn):

第一階段稱為層次發(fā)現(xiàn)與建立階段:這一階段是由根節(jié)點(diǎn)廣播包含發(fā)送節(jié)點(diǎn)的ID和級(jí)別的級(jí)別發(fā)現(xiàn)分組開始的。其基本原理為，當(dāng)一個(gè)節(jié)點(diǎn)收到來自i節(jié)點(diǎn)的廣播分組后，它便將自己的級(jí)別設(shè)為(i+1)級(jí)，并記下發(fā)送節(jié)點(diǎn)的ID，之后將包含自己級(jí)別和ID的分組繼續(xù)廣播發(fā)送下去。根節(jié)點(diǎn)的級(jí)別定為0級(jí)，所以收到根節(jié)點(diǎn)發(fā)送分組的節(jié)點(diǎn)，會(huì)將自己的級(jí)別設(shè)為1級(jí)，然后繼續(xù)廣播分組，依次類推下去，直到全網(wǎng)的節(jié)點(diǎn)都建立自己的級(jí)別。已經(jīng)建立級(jí)別的分組就忽略廣播分組，以防止產(chǎn)生網(wǎng)絡(luò)擁堵。

第二階段稱為時(shí)間同步階段:在第一階段的層次級(jí)別建立完成之后，開始進(jìn)入時(shí)間同步階段。首先根節(jié)點(diǎn)即0級(jí)節(jié)點(diǎn)廣播時(shí)間同步分組，收到分組之后，第1級(jí)節(jié)點(diǎn)經(jīng)過一段隨機(jī)時(shí)間的等待，向0級(jí)節(jié)點(diǎn)發(fā)送時(shí)間同步的請(qǐng)求信息包，開始時(shí)間同步過程。同時(shí)第2級(jí)節(jié)點(diǎn)在偵聽到第l級(jí)節(jié)點(diǎn)發(fā)送的時(shí)間同步請(qǐng)求信息包后也開始自己的同步過程。依次類推，最終完成整個(gè)網(wǎng)絡(luò)的時(shí)間同步[5]。

TPSN中兩節(jié)點(diǎn)間交換時(shí)間信息的原理如圖1所示，設(shè)兩節(jié)點(diǎn)分別為S和R，分別用圖中兩條橫線表示，S為第(i+1)級(jí)節(jié)點(diǎn)，R為第i級(jí)節(jié)點(diǎn)，令S在T1時(shí)刻向R發(fā)出一個(gè)時(shí)間同步請(qǐng)求消息并用本地時(shí)間記錄下來，R收到消息后用自己的本地時(shí)間記錄下其到達(dá)時(shí)刻T2，T2=T1+d+Δ，其中Δ表示兩節(jié)點(diǎn)間的時(shí)間偏移，d表示消息的傳播時(shí)延，之后R在T3時(shí)刻再反發(fā)一條應(yīng)答消息給S，并且記錄時(shí)刻，這個(gè)應(yīng)答消息中包含了前面的3個(gè)時(shí)間量T1，T2，T3，S接收到來自R的消息后，記錄下到達(dá)時(shí)刻T4，T4=T3+d－Δ。我們假設(shè)請(qǐng)求消息和應(yīng)答消息具有相同的傳播時(shí)延，從而可以推出:

在計(jì)算出時(shí)間偏移后，節(jié)點(diǎn)S將其本地時(shí)間同步到R。由于將傳播和接收時(shí)間都考慮在內(nèi)，并利用了消息的雙向交換計(jì)算出了消息的平均時(shí)延，TPSN使得時(shí)間同步的精度得以提高。

圖1 TPSN節(jié)點(diǎn)間交換時(shí)間消息原理圖

2 算法優(yōu)化

通過對(duì)TPSN算法研究可知，雖然TPSN算法是一種精度很高的算法，但是當(dāng)節(jié)點(diǎn)間路徑的長(zhǎng)度增大，跳數(shù)增加時(shí)，由于每對(duì)同步節(jié)點(diǎn)之間信息交換的延遲，以及時(shí)鐘頻率具有不穩(wěn)定性等因素所造成的累積誤差將會(huì)影響到同步的精度[6]從而產(chǎn)生誤差。TPSN算法的誤差包括確定性和不確定性兩部分[7]，確定性部分主要為傳輸延遲，不確定性部分則包括時(shí)間偏差以及由時(shí)鐘頻率不一致而導(dǎo)致的時(shí)間漂移。不確定性部分的誤差主要是由是由消息傳遞延遲造成的。我們可以利用線性擬合來解決算法中確定性誤差[8]，這里算法的優(yōu)化主要針對(duì)不確定性部分的誤差。為了提高算法的同步精度并減少能耗，本文提出了一種對(duì)TPSN算法進(jìn)行改進(jìn)的方案，方案分為兩步，第一步是引入貝葉斯估計(jì)減小TPSN算法同步誤差，提高同步精度，第二步再利用可變周期同步法降低算法的能量消耗。改進(jìn)后的算法稱為TPSN-BY(Time Synchronization for Senor Network with Bayes Estimation and Changeable Cycle Synchronization Method)。由文獻(xiàn)[9]可知，我們可以將由消息傳遞延遲引起的誤差視為一個(gè)期望為0的正態(tài)分布，這樣一來，便可以引入貝葉斯估計(jì)。

2．1 貝葉斯估計(jì)原理

貝葉斯估計(jì)[10]是一種有效利用已知數(shù)學(xué)信息的估計(jì)方法，它是通過將未知參數(shù)H視為一個(gè)具有已知分布p(H)的隨機(jī)變量來實(shí)現(xiàn)的，通常p(H)稱為先驗(yàn)概率。在樣本空間D一定的情況下，我們可以由p(H)得到后驗(yàn)概率p(H/D)，根據(jù)貝葉斯理論，可得:

假設(shè)一個(gè)正態(tài)分布的隨機(jī)變量x∈D，且x～N(H，α)。其中期望 H未知，方差 α已知，對(duì)應(yīng)式(3)中即是p(x/H)～N(H，α)。假設(shè)p(H)也是正態(tài)分布，即H ～N(H0，α0)，其中 H0，α0均已知。那么由式(3)可知，其后驗(yàn)分布也是正態(tài)的:

（2）清理基層。在鋪設(shè)土工布之前必須將影響土工布與基層結(jié)合的雜物、油脂等清理干凈，并將基層上凸出的尖銳部分進(jìn)行破碎處理或清理出場(chǎng)。

因p(x)為一個(gè)數(shù)值，由式(3)可知 p(H/x)∞p(x/H)p(H)，∞為正比例符號(hào)。即:

由式(4)可算得后驗(yàn)分布的兩參數(shù):

2．2 算法的優(yōu)化過程

第一步:采用貝葉斯估計(jì)對(duì)TPSN算法進(jìn)行優(yōu)化

首先我們假設(shè)采用TPSN算法時(shí)當(dāng)前節(jié)點(diǎn)的時(shí)鐘時(shí)間為Ti(i∈n)，而通過貝葉斯估計(jì)估計(jì)方法所得的當(dāng)前節(jié)點(diǎn)時(shí)間值為ti(i∈n)，通過貝葉斯估計(jì)方法所得的上一層節(jié)點(diǎn)的時(shí)間值為ti－1(i∈n)，它服從方差為的正態(tài)分布。前面已經(jīng)提到，TPSN中通過消息傳遞得到的節(jié)點(diǎn)時(shí)鐘值并不是實(shí)際準(zhǔn)確的時(shí)間值，它是存在服從正態(tài)分布的隨機(jī)誤差的，即～，我們可以從前面的數(shù)據(jù)中取得的值。運(yùn)用貝葉斯理論，因?yàn)?ti－1(i∈n)的先驗(yàn)分布 ～N，再結(jié)合Ti，可以得到更為新的估計(jì):N。由式(5)，式(6)可得:

之后令t1=T1，δ'1=δ1。其中T1為根節(jié)點(diǎn)的時(shí)間觀測(cè)值，δ'1為其時(shí)鐘分辨率。其基本流程為上一級(jí)的節(jié)點(diǎn)將其貝葉斯估計(jì)時(shí)刻值ti=1和估計(jì)誤差的標(biāo)準(zhǔn)偏差δ'i－1發(fā)送給下一級(jí)節(jié)點(diǎn)。通過對(duì)下一級(jí)節(jié)點(diǎn)進(jìn)行觀測(cè)從而得到本地時(shí)間Ti，從之前的記錄時(shí)鐘信息中提取標(biāo)準(zhǔn)方差，由 ti－1，δ'i－1以及式(7)，式(8)便可得出ti和δ'i。全網(wǎng)節(jié)點(diǎn)按此流程最后達(dá)到同步。

對(duì)改進(jìn)后的算法進(jìn)行分析，我們選取一百次同步的時(shí)間統(tǒng)計(jì)值，每次同步都會(huì)產(chǎn)生同步誤差，圖2所示為不同同步次數(shù)時(shí)TPSN算法和TPSN-BY算法的同步誤差。

圖2 不同同步次數(shù)下的時(shí)間同步誤差

第二步:采用可變周期同步法對(duì)TPSN算法進(jìn)行優(yōu)化

可變周期同步法就是同步的時(shí)間周期長(zhǎng)度可以變化的一種同步方法，它根據(jù)時(shí)間同步周期和時(shí)間偏移的最近變化值來確定新的周期[11]。由于TPSN-BY算法的同步偏差在一定時(shí)間后會(huì)收斂并且穩(wěn)定下來，我們就可以利用可變周期同步減少節(jié)點(diǎn)同步次數(shù)，從而降低能耗。我們?cè)诘?0次同步后設(shè)置一個(gè)時(shí)間偏差的最大值，當(dāng)時(shí)間偏差小于此最大值時(shí)不再進(jìn)行同步而令節(jié)點(diǎn)保持休眠，當(dāng)其大于此最大值時(shí)才進(jìn)行下一輪同步，通過這種方式我們可以讓同步次數(shù)減少，如果相同的時(shí)間內(nèi)，TPSN算法同步60次，而TPSNBY算法同步了20次，那么，TPSN-BY算法就比TPSN算法少了了2/3的同步次數(shù)，因此其能耗也減少了2/3。我們可以通過前幾次同步的最大時(shí)間偏差計(jì)算出同步周期，其計(jì)算公式為:

其中:φ為同步周期，單位為s;μ為同步精度，單位為s;δ'i為節(jié)點(diǎn)i的漂移率，單位為ppm(parts per million)。δ'i的值可由(7)求得。

若同步周期的最大值為φmax，則有

由于改進(jìn)后的算法的同步誤差可以在同步一定時(shí)間后趨于一個(gè)定值并且穩(wěn)定下來，為判斷是否繼續(xù)進(jìn)行同步，可以設(shè)定一個(gè)時(shí)鐘偏移的臨界值θ，若點(diǎn)S相對(duì)于R的時(shí)鐘偏移小于θ，則令節(jié)點(diǎn)處于休眠狀態(tài)，若大于臨界值則進(jìn)行下一輪同步，θ計(jì)算公式為:

3 仿真結(jié)果分析

本文利用 NS2(Network Simulator version 2)[12]網(wǎng)絡(luò)仿真軟件對(duì)TPSN以及優(yōu)化算法進(jìn)行模擬，分析仿真結(jié)果并進(jìn)行性能評(píng)估。設(shè)置仿真環(huán)境為半徑為5 km的圓形區(qū)域，均勻布置20個(gè)節(jié)點(diǎn)，其中一個(gè)為根節(jié)點(diǎn)，19個(gè)為待同步節(jié)點(diǎn)，設(shè)置節(jié)點(diǎn)間的距離為200 m，無線通信傳輸距離為300 m，從而保證只有相鄰的節(jié)點(diǎn)才可以相互傳輸消息。這里選取了節(jié)點(diǎn)15與根節(jié)點(diǎn)在兩種算法下的同步誤差和能耗的仿真結(jié)果來進(jìn)行分析和說明。

圖3所示為節(jié)點(diǎn)15與根節(jié)點(diǎn)之間的同步誤差比較圖。由圖可知，采用TPSN-BY算法和TPSN算法時(shí)兩節(jié)點(diǎn)間同步時(shí)間誤差的最大值分別為11 μs和26 μs，兩節(jié)點(diǎn)間同步時(shí)間誤差的最小值分別為7 μs和16 μs;由此可見，相對(duì)于TPSN算法，TPSN-BY很好的減小了時(shí)間同步誤差，從而減少累積誤差。

如圖4所示為選取5、10、15和20個(gè)節(jié)點(diǎn)數(shù)時(shí)，兩種算法各自的能耗。由圖可知，TPSN-BY算法消耗的能量遠(yuǎn)遠(yuǎn)小于一直進(jìn)行同步的TPSN算法;隨著節(jié)點(diǎn)個(gè)數(shù)的增加，能量的消耗也必然會(huì)增長(zhǎng)，由圖我們可以看出，TPSN-BY算法的能量增長(zhǎng)速率遠(yuǎn)低于TPSN算法的能量增長(zhǎng)速率。在相同的節(jié)點(diǎn)個(gè)數(shù)時(shí)，TPSN-BY算法的能耗低于 TPSN算法的1/2。由此可得，經(jīng)過優(yōu)化改進(jìn)的算法大大降低了能量消耗，使得WSN的壽命得以延長(zhǎng)。

圖3 根節(jié)點(diǎn)與節(jié)點(diǎn)15的同步時(shí)間差值

圖4 兩種算法間能量消耗比較圖

4 結(jié)論

時(shí)鐘同步是無線傳感器網(wǎng)絡(luò)的一項(xiàng)關(guān)鍵技術(shù)，其算法研究也是當(dāng)前的一個(gè)熱點(diǎn)，本文的主要工作為，在原來的TPSN算法的基礎(chǔ)上，引入貝葉斯估計(jì)法和可變周期同步法針對(duì)其由消息傳遞延遲引起的誤差和同步時(shí)的能耗進(jìn)行改進(jìn)，得出了TSPN-BY算法。由仿真結(jié)果可知，TSPN-BY算法達(dá)到了提高精度和降低能耗的目的，有利于傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的提高和壽命的延長(zhǎng)。

[1]崔林．無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)研究[D]．哈爾濱:哈爾濱工業(yè)大學(xué)，2009．

[2]陳喬．無線傳感器網(wǎng)絡(luò)時(shí)間同步算法的研究與應(yīng)用[D]．西安:西安理工大學(xué)，2010．

[3]周賢偉，韋煒，覃伯平．無線傳感器網(wǎng)絡(luò)時(shí)間同步算法研究[J]．傳感技術(shù)學(xué)報(bào)，2006，19(1):20－25．

[4]Elson Jeremy，Girod Lewis，Estrin Deborah．Fine-Grained Net-Work Time Synchronization Using Reference Broadcasts[C]//Proceedings of the Fifth Symposium on Operating Systems Design and Implementation．Boston，MA，2002，147－163．

[5]田賢忠，陳登，胡同森．無線傳感器網(wǎng)絡(luò)按需時(shí)間同步算法研究[J]．傳感技術(shù)學(xué)報(bào)，2008，21(11):1881－1886．

[6]Ganeriwal Saurabh，Kumar Ram，Srivastava Mani．Timing Sync Protocol for Sensor Networks[C]//ACM SenSys．Los Angeles，CA，2003．

[7]俞家安，陳曉輝，王衛(wèi)東．一種低開銷的無線傳感器網(wǎng)絡(luò)時(shí)間同步算法[J]．計(jì)算機(jī)仿真，2009，26(5):121－124．

[8]Jeremy Eric Elson．Time Synchronization Services for Wireless Sensor Networks[D]．Dept of Computer Science，University of California，2003．

[9]沈明玉，艾治雄．無線傳感網(wǎng)絡(luò)低能耗時(shí)間同步的研究[J]．計(jì)算機(jī)工程與應(yīng)用．[2011－3－14]http://www．cnki．net/kcms/detail/11．2127．tp．20110314．1659．023．html．

[10]李賢平，沈崇圣，陳子毅．概率論與數(shù)理統(tǒng)計(jì)[M]．上海:復(fù)旦大學(xué)出版社，2003:98－100．

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

[12]方路平，劉世華，陳盼，等．NS2網(wǎng)路模擬基礎(chǔ)與應(yīng)用[M]．北京:國(guó)防工業(yè)出版社，2008，42－104．