分簇型無線傳感器網(wǎng)絡(luò)時間同步機(jī)制的研究

楊 東，李燈熬，趙菊敏，安文秀

(太原理工大學(xué)信息工程學(xué)院，山西太原 030024)

無線傳感器網(wǎng)絡(luò)(WSN)是近年來逐漸興起的一種融多種技術(shù)的新興領(lǐng)域，用以自動感知、采集、傳輸和實時監(jiān)測待檢測對象信息［1］。無線傳感器網(wǎng)絡(luò)是一種面向應(yīng)用的網(wǎng)絡(luò)，在實際應(yīng)用中，缺乏時間信息的監(jiān)測結(jié)果對于監(jiān)測者來說是不具有任何意義的。時間同步機(jī)制的性能對無線傳感器網(wǎng)絡(luò)有著至關(guān)重要的影響。

WSN時間同步機(jī)制于2002年由Elson［2］等人在Hot-Net－Ⅰ國際會議上首次提出，并被無線傳感器網(wǎng)絡(luò)研究者廣泛關(guān)注。多年來眾多研究學(xué)者已提出了多種經(jīng)典時間同步算法?，F(xiàn)行的經(jīng)典時間同步算法可分為3類:基于接收者—接收者的時間同步算法(典型代表算法RBS［3］)、基于接收者—發(fā)送者的時間同步算法(典型代表算法TPSN［4－5］)和基于發(fā)送者的時間同步算法(典型代表算法DMTS［6］和 FTSP)。

隨著無線傳感器網(wǎng)絡(luò)研究水平提高及應(yīng)用的推廣，網(wǎng)絡(luò)的大規(guī)模性成為無線傳感器網(wǎng)絡(luò)發(fā)展的必然趨勢。時間同步機(jī)制的研究也必然致力于在降低網(wǎng)絡(luò)能量消耗的基礎(chǔ)上提高大規(guī)模網(wǎng)絡(luò)的時間同步精度。在網(wǎng)絡(luò)規(guī)模增大和網(wǎng)絡(luò)消耗降低的要求下，已有的很多算法得到了限制［7］。RBS 算法復(fù)雜度為O(m，n)，信息交換量為O(n2)(m，n分別為廣播消息的個數(shù)和節(jié)點數(shù)目)。當(dāng)節(jié)點數(shù)目較大時，信息交換量非常大，消耗網(wǎng)絡(luò)較多的能量，不適用于節(jié)點數(shù)目較多的網(wǎng)絡(luò)。同時RBS算法只能相對同步，同步精度較低。DMTS同步算法是以在犧牲同步精度的基礎(chǔ)上，降低算法的復(fù)雜度和網(wǎng)絡(luò)的開銷，只能適用于對同步要求不是很高的網(wǎng)絡(luò)，不能適應(yīng)未來無線傳感器網(wǎng)絡(luò)的發(fā)展要求。FTSP算法中，參考節(jié)點多次發(fā)送廣播消息，通過集中式線性回歸法對時鐘的相對漂移和相對偏移進(jìn)行估計。當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)目較多時，F(xiàn)TSP算法需要非常多的能量來維護(hù)大量的歷史數(shù)據(jù)，用來提高估計精度，從而加大了網(wǎng)絡(luò)的能量消耗。

TPSN算法應(yīng)用于層次型網(wǎng)絡(luò)結(jié)構(gòu)，采用雙向同步機(jī)制，同步精度較高，在同步過程中信息交換量為O(2n+1)。當(dāng)n變大時，TPSN算法的信息交換量遠(yuǎn)低于RBS的信息交換量，常用于大規(guī)模網(wǎng)絡(luò)，且易于實現(xiàn)。但是TPSN算法中未考慮根節(jié)點的失效問題，且同步精度隨著網(wǎng)絡(luò)跳數(shù)的增加而降低?？紤]到上述問題，本文提出了一種新的同步算法:創(chuàng)建分簇型網(wǎng)絡(luò)結(jié)構(gòu)，通過分簇降低網(wǎng)絡(luò)跳數(shù)避免同步誤差的積累量增大，同時用簇首節(jié)點代替根節(jié)點，通過周期性選取簇首節(jié)點，均衡簇首節(jié)點的能量消耗，降低簇首節(jié)點的失效率。在同步過程中，同時采用單向廣播同步機(jī)制和雙向時間同步機(jī)制，提高同步過程中的同步精度。

1 基于分簇型網(wǎng)絡(luò)結(jié)構(gòu)的時間同步算法

本文提出的算法分為2個階段:分簇結(jié)構(gòu)的建立階段和時間同步階段。在分簇結(jié)構(gòu)的建立階段，利用本文提出的優(yōu)化LEACH算法創(chuàng)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并選取各簇簇首節(jié)點，其他節(jié)點根據(jù)收到簇首節(jié)點發(fā)送消息的信號強(qiáng)度選擇加入簇，使每個節(jié)點均處于簇結(jié)構(gòu)中。在時間同步階段，首先進(jìn)行的是簇首節(jié)點或助理簇首節(jié)點與基站之間的時間同步，該階段使用雙向時間同步機(jī)制;其次，完成上述時間同步階段后，開始啟動簇首節(jié)點與同簇內(nèi)其他節(jié)點的時間同步階段，在該階段使用雙向時間同步機(jī)制與單向廣播時間同步機(jī)制相結(jié)合的時間同步機(jī)制。

1.1 分簇型網(wǎng)絡(luò)結(jié)構(gòu)的創(chuàng)建

在無線傳感器網(wǎng)絡(luò)層次型拓?fù)淇刂扑惴ǚ矫?，研究者提出了較多經(jīng)典拓?fù)浣Y(jié)構(gòu)控制算法。其中，較為經(jīng)典的是LEACH(Low Energy Adaptive Clustering Hierarchy)算法［8］，該算法能夠周期性自動形成簇型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，運行階段可分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。在LEACH算法選取簇首節(jié)點過程中，節(jié)點產(chǎn)生一個0～1的隨機(jī)數(shù)，若該隨機(jī)數(shù)小于閾值T(n)，則該節(jié)點以T(n)的概率當(dāng)選簇首節(jié)點。已當(dāng)選過的節(jié)點則把T(n)的值設(shè)置為0，在下輪選取中不再當(dāng)選。閾值T(n)表示為

LEACH算法可以保證每一個傳感器節(jié)點以相同的概率當(dāng)選簇首節(jié)點，均衡了簇首節(jié)點所消耗的能量，從而避免了因簇首節(jié)點能量過低而導(dǎo)致全網(wǎng)絡(luò)失效的情況出現(xiàn)，較好地提高了整個網(wǎng)絡(luò)的運行時間。但是LEACH算法存在著一些缺陷:首先，該算法在簇首選取機(jī)制中，傳感器節(jié)點隨機(jī)數(shù)產(chǎn)生的隨機(jī)性較強(qiáng)，有可能導(dǎo)致產(chǎn)生較多的傳感器節(jié)點距離簇首節(jié)點的位置較遠(yuǎn)，容易造成簇首節(jié)點的能量消耗過多、過快;其次，該算法簇首選取機(jī)制中并沒有考慮到傳感器節(jié)點的初始能量和剩余能量的問題，有可能會出現(xiàn)剩余能量較低的節(jié)點被選取為簇首節(jié)點，加速簇首節(jié)點因能量消耗過快而迅速導(dǎo)致死亡。

針對以上LEACH算法中存在的缺陷，本文提出的時間同步算法提供了良好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。本文提出了一種LEACH優(yōu)化算法，在優(yōu)化算法中，簇首節(jié)點選取閾值中融入簇首節(jié)點剩余能量和鄰居節(jié)點密度因子，同時在非簇首節(jié)點中選取助理簇首節(jié)點用以均衡簇首節(jié)點的能量消耗。設(shè)定簇首節(jié)點選取的時間門限值Tth，該值與節(jié)點的剩余能量相關(guān)，使簇首節(jié)點的當(dāng)選周期與剩余能量有關(guān)。優(yōu)化算法的具體描述如下:

定義E0為傳感器節(jié)點的初始能量，在本文中，假定所有傳感器節(jié)點的初始能量E0是相等的;定義Eres(r)為第r輪簇首節(jié)點選取時，節(jié)點i的剩余能量，則節(jié)點i從網(wǎng)絡(luò)結(jié)構(gòu)初始化至第r輪簇首選取時，因接收、發(fā)送消息共消耗的能量(r)，(r)分別為

式中:為第m輪期間，節(jié)點i接收數(shù)據(jù)的比特數(shù);為第m輪期間，節(jié)點i發(fā)送數(shù)據(jù)的比特數(shù);dm為第m輪期間節(jié)點i的通信距離總和。

在綜合分析以上兩個因素對簇首節(jié)點的影響后，結(jié)合上述公式，本文提出了優(yōu)化算法的簇首節(jié)點選取機(jī)制的閾值T'(n)，T'(n)表達(dá)式為

式中:N為無線傳感器網(wǎng)絡(luò)簇首節(jié)點的總次數(shù);α根據(jù)網(wǎng)絡(luò)的實際情況確定且0＜α＜1。

由于簇首節(jié)點在整個時間同步算法中具有重要的作用，其一但失效不僅會影響時間同步機(jī)制的同步精度，嚴(yán)重者甚至?xí)＜罢麄€無線傳感器網(wǎng)絡(luò)的使用壽命。同時，簇首節(jié)點將與基站和簇內(nèi)非同步節(jié)點進(jìn)行大量的信息交換，能量消耗要遠(yuǎn)超過簇內(nèi)其他節(jié)點。為了均衡簇首節(jié)點的能量消耗，提高整個網(wǎng)絡(luò)的能量利用率，本文提出一種簇首節(jié)點助理機(jī)制。在該機(jī)制中，該節(jié)點主要用來實現(xiàn)數(shù)據(jù)融合并將融合后的數(shù)據(jù)傳遞給基站。所以在助理簇首節(jié)點選取的過程中，該節(jié)點與基站位置的距離成為重要的選取原則。定義dBS(i)為節(jié)點i與基站之間的距離，則助理簇首節(jié)點的選取閾值為

式中:β和γ均根據(jù)網(wǎng)絡(luò)的實際情況所定，β和γ均為小于1的實數(shù);G'為簇內(nèi)非簇首節(jié)點。

1.2 時間同步階段

時間同步階段主要分為2個階段:簇首節(jié)點及助理簇首節(jié)點與基站的時間同步階段;簇首節(jié)點與同簇內(nèi)待同步節(jié)點時間同步階段。在簇首節(jié)點及助理簇首節(jié)點與基站間的時間同步階段采用雙向時間同步機(jī)制。在簇首節(jié)點與同簇內(nèi)的其他待同步節(jié)點時間同步階段采用雙向時間同步機(jī)制和單向時間同步機(jī)制混合式時間同步機(jī)制。

在簇首節(jié)點及助理簇首節(jié)點與基站實現(xiàn)時間同步的階段，時間同步原理如圖1所示，簇首節(jié)點或助理簇首節(jié)點在T1時刻向基站發(fā)送時間同步請求消息，基站在T2時刻收到該請求消息后，并在T3時刻響應(yīng)該消息，簇首節(jié)點或助理簇首節(jié)點在T4時刻收到基站發(fā)送的響應(yīng)消息。根據(jù)式(7)和式(8)計算自身節(jié)點與基站之間的時間偏差和時間消息傳播時延，并根據(jù)計算結(jié)果調(diào)整自身本地時鐘，從而實現(xiàn)簇首節(jié)點或助理簇首節(jié)點與基站的時間同步。

式中:d為消息傳播時延;Δ為兩節(jié)點間的時間偏移值。

圖1 簇首節(jié)點或助理簇首節(jié)點與基站時間同步原理圖

在簇首節(jié)點與同簇內(nèi)待同步節(jié)點時間同步階段，采用雙向時間同步機(jī)制和單向廣播時間同步機(jī)制混合式時間同步機(jī)制。具體同步過程如下:

1)簇首節(jié)點在T1時刻廣播啟動簇內(nèi)節(jié)點時間同步消息，簇內(nèi)各節(jié)點記錄各自收到該廣播消息的時刻Tk(i)，并保存該時刻。

2)隨機(jī)選擇一簇內(nèi)待同步節(jié)點，并在T2時刻響應(yīng)該廣播消息，并發(fā)送響應(yīng)消息給簇首節(jié)點。該消息中包含其在步驟1)中收到的時間同步啟動消息的時刻T2和發(fā)送響應(yīng)消息的時刻T3。

3)簇首節(jié)點于T4時刻收到該響應(yīng)節(jié)點發(fā)送的響應(yīng)消息，并根據(jù)式(7)和式(8)計算簇首節(jié)點與該相應(yīng)節(jié)點間的時間偏移值Δ和消息傳播延遲d。

4)簇首節(jié)點廣播時間校正消息，該消息中包含響應(yīng)節(jié)點在步驟1)中收到的時間同步啟動消息的時刻T2以及步驟3)中簇首節(jié)點計算出的時間偏移值Δ和消息傳播延遲d。

5)簇內(nèi)待同步節(jié)點收到步驟4)中的時間校正消息后，讀取該消息包，比較在步驟1)中自身保存的Tk(i)與T2值的大小，得到自己與簇首節(jié)點間的時鐘偏差，并根據(jù)δ'調(diào)整本地時鐘，從而實現(xiàn)待同步節(jié)點與簇首節(jié)點間的同步。

簇首節(jié)點與同簇內(nèi)待同步節(jié)點時間同步機(jī)制原理圖如圖2所示。

2 實驗仿真分析

圖2 簇首節(jié)點與同簇內(nèi)待同步節(jié)點時間同步原理圖

為了驗證本文提出的優(yōu)化算法性能，對所提出的優(yōu)化算法進(jìn)行了實驗仿真，并與TPSN算法的實驗仿真結(jié)果進(jìn)行比較。在實驗中假設(shè)基站的能量是無窮的，所有傳感器節(jié)點均是不可移動的。其中，節(jié)點部署范圍100 m×100 m，基站位置(50，50)，節(jié)點數(shù)300，節(jié)點的初始能量E0為0.15 J，Eelse為50 nJ/bit，Efs為10 pJ/(bit×m2)。

從圖3可知，本文算法與TPSN算法隨著節(jié)點數(shù)目的增加，節(jié)點的信息交換量也隨之增加。當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)目小于50時，二者之間的差距不明顯，但是隨著網(wǎng)絡(luò)中節(jié)點數(shù)目的增多，TPSN算法中的信息交換量要明顯大于相同數(shù)目下本文算法中的信息交換量。導(dǎo)致這種情況出現(xiàn)的原因是:TPSN算法中同步節(jié)點采用雙向時間同步機(jī)制，每對節(jié)點間實現(xiàn)同步需要2條消息進(jìn)行交換。而在本文算法中，只有簇首節(jié)點和助理簇首節(jié)點采用雙向同步機(jī)制，而在簇內(nèi)節(jié)點進(jìn)行同步時，采用單向廣播時間同步機(jī)制。在整個網(wǎng)絡(luò)中，采用單向廣播時間同步機(jī)制的節(jié)點數(shù)目要遠(yuǎn)小于采用雙向時間同步機(jī)制的節(jié)點數(shù)目。所以當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)目增多時，本文算法在信息交換量的優(yōu)勢明顯優(yōu)于TPSN算法。

圖3 本文算法與TPSN算法信息交換量的比較

由圖4可知，本文算法與TPSN算法在同步過程中，隨著跳數(shù)的增加同步誤差越來越大。TPSN中同步誤差一方面由于雙向時間同步機(jī)制中存在消息傳播時延，更主要的是隨著跳數(shù)的增加，同步誤差在逐漸積累，導(dǎo)致隨著跳數(shù)的增加同步誤差越來越大。本文算法中出現(xiàn)的同步誤差首先出現(xiàn)在簇首節(jié)點與基站進(jìn)行的雙向時間同步機(jī)制，其次，較大程度的同步誤差是由于簇首節(jié)點在簇內(nèi)節(jié)點同步過程中隨機(jī)選擇的應(yīng)答節(jié)點。若應(yīng)答節(jié)點與周圍鄰居節(jié)點的時鐘偏移存在較大誤差，則也會導(dǎo)致本文中同步精度的降低。同時，亦可觀察到，當(dāng)網(wǎng)絡(luò)跳數(shù)等于1時，二者之間存在較小的差距，但是隨著跳數(shù)的增加，在相同的網(wǎng)絡(luò)跳數(shù)情況下，本文的同步誤差要小于TPSN算法中的同步誤差，即本文的時間同步精度要高于TPSN時間同步精度。

圖4 本文算法與TPSN算法同步誤差的比較

如圖5所示，在相同的輪數(shù)情況下，本文算法節(jié)點消耗的能量要低于TPSN算法。其主要原因是在本文算法中采用分簇型網(wǎng)絡(luò)結(jié)構(gòu)，在簇首節(jié)點閾值中融入節(jié)點剩余能量因子和鄰居節(jié)點密度因子。鄰居節(jié)點密度因子越大，簇首節(jié)點周圍的鄰居節(jié)點數(shù)目也就越多，簇內(nèi)節(jié)點的部署也越均勻，簇首節(jié)點的通信總距離也就越小，從而簇首節(jié)點的通信消耗也就越小。另一方面，本文設(shè)定簇首節(jié)點的當(dāng)選時間門限值，該值隨著簇首節(jié)點剩余能量的變化自動變化簇首時間的當(dāng)選周期，剩余能量越低，簇首節(jié)點的當(dāng)選時間也就越短，縮短簇首節(jié)點的工作時間，從而降低了節(jié)點的能量消耗。最后，本文中助理簇首節(jié)點均衡了簇首節(jié)點的能量消耗，提高了網(wǎng)絡(luò)利用率。

3 總結(jié)

本文提出一種新的時間同步算法，在該算法的分簇結(jié)構(gòu)創(chuàng)建階段，簇首選取閾值融入簇首節(jié)點的剩余能量因子和鄰居節(jié)點密度因子，同時設(shè)定了助理簇首節(jié)點和簇首節(jié)點工作時間門限值，較好地優(yōu)化了網(wǎng)絡(luò)結(jié)構(gòu)，降低了網(wǎng)絡(luò)的跳數(shù)。在時間同步階段，采用了雙向時間同步機(jī)制和單向廣播時間同步機(jī)制。實驗證明，該算法降低了網(wǎng)絡(luò)跳數(shù)，提高了時間同步精度，降低了節(jié)點的能量消耗，延長了無線傳感器網(wǎng)絡(luò)的運行壽命，具有一定的實用價值。

圖5 本文算法簇首節(jié)點與TPSN算法根節(jié)點剩余能量比較

:

［1］程敏敏，宋家友，張漢.基于梯度的分簇式路由協(xié)議［J］.電視技術(shù)，2012，36(15):108－111.

［2］汪富強(qiáng)，曾鵬，于海斌.一種低開銷的時間同步算法［J］.儀器儀表學(xué)報，2011，32(6):1357－1361.

［3］ELSON J，GRIOD L，ESREIN D.Fine－grained network time synchronization using reference broadcasts［C］//Proc.5th Symposium Operating Systems Design and Implementation.Boston，MA:ACM Press，2002:147－163.

［4］GANERIWAL S，KUMAR R，SRIVASTAVA M B.Timing－sync protocol for sensor networks［C］//Proc.1st International Conference on Embedded Networked Sensor Systems(SenSys 2003).Los Angeles，CA:IEEE Press，2003:138－149.

［5］GANERIWAL S，KUMAR R，ADLAKHA S，et al.Network－wide time synchronization in sensor networks［EB/OL］.［2013－02－10］.http://nesl.ee.ucla.edu/fw/ram/ram － homepage/content/papers/time_sync.pdf.

［6］PING S.Delay measurement time synchronization for wireless networks［EB/OL］.［2013－02－10］.http://www.intel_research .net/publication/Berkeley/0811200031327－137.pdf.

［7］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

［8］周治平，王亭，張明亮.傳感網(wǎng)絡(luò)中一種能量有效的簇頭選舉機(jī)制［J］.計算機(jī)工程與應(yīng)用，2012，48(8):105－108.