楊 東,李燈熬,趙菊敏,安文秀
(太原理工大學(xué)信息工程學(xué)院,山西太原 030024)
無(wú)線傳感器網(wǎng)絡(luò)(WSN)是近年來(lái)逐漸興起的一種融多種技術(shù)的新興領(lǐng)域,用以自動(dòng)感知、采集、傳輸和實(shí)時(shí)監(jiān)測(cè)待檢測(cè)對(duì)象信息[1]。無(wú)線傳感器網(wǎng)絡(luò)是一種面向應(yīng)用的網(wǎng)絡(luò),在實(shí)際應(yīng)用中,缺乏時(shí)間信息的監(jiān)測(cè)結(jié)果對(duì)于監(jiān)測(cè)者來(lái)說(shuō)是不具有任何意義的。時(shí)間同步機(jī)制的性能對(duì)無(wú)線傳感器網(wǎng)絡(luò)有著至關(guān)重要的影響。
WSN時(shí)間同步機(jī)制于2002年由Elson[2]等人在Hot-Net-Ⅰ國(guó)際會(huì)議上首次提出,并被無(wú)線傳感器網(wǎng)絡(luò)研究者廣泛關(guān)注。多年來(lái)眾多研究學(xué)者已提出了多種經(jīng)典時(shí)間同步算法。現(xiàn)行的經(jīng)典時(shí)間同步算法可分為3類:基于接收者—接收者的時(shí)間同步算法(典型代表算法RBS[3])、基于接收者—發(fā)送者的時(shí)間同步算法(典型代表算法TPSN[4-5])和基于發(fā)送者的時(shí)間同步算法(典型代表算法DMTS[6]和 FTSP)。
隨著無(wú)線傳感器網(wǎng)絡(luò)研究水平提高及應(yīng)用的推廣,網(wǎng)絡(luò)的大規(guī)模性成為無(wú)線傳感器網(wǎng)絡(luò)發(fā)展的必然趨勢(shì)。時(shí)間同步機(jī)制的研究也必然致力于在降低網(wǎng)絡(luò)能量消耗的基礎(chǔ)上提高大規(guī)模網(wǎng)絡(luò)的時(shí)間同步精度。在網(wǎng)絡(luò)規(guī)模增大和網(wǎng)絡(luò)消耗降低的要求下,已有的很多算法得到了限制[7]。RBS 算法復(fù)雜度為O(m,n),信息交換量為O(n2)(m,n分別為廣播消息的個(gè)數(shù)和節(jié)點(diǎn)數(shù)目)。當(dāng)節(jié)點(diǎn)數(shù)目較大時(shí),信息交換量非常大,消耗網(wǎng)絡(luò)較多的能量,不適用于節(jié)點(diǎn)數(shù)目較多的網(wǎng)絡(luò)。同時(shí)RBS算法只能相對(duì)同步,同步精度較低。DMTS同步算法是以在犧牲同步精度的基礎(chǔ)上,降低算法的復(fù)雜度和網(wǎng)絡(luò)的開(kāi)銷,只能適用于對(duì)同步要求不是很高的網(wǎng)絡(luò),不能適應(yīng)未來(lái)無(wú)線傳感器網(wǎng)絡(luò)的發(fā)展要求。FTSP算法中,參考節(jié)點(diǎn)多次發(fā)送廣播消息,通過(guò)集中式線性回歸法對(duì)時(shí)鐘的相對(duì)漂移和相對(duì)偏移進(jìn)行估計(jì)。當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目較多時(shí),F(xiàn)TSP算法需要非常多的能量來(lái)維護(hù)大量的歷史數(shù)據(jù),用來(lái)提高估計(jì)精度,從而加大了網(wǎng)絡(luò)的能量消耗。
TPSN算法應(yīng)用于層次型網(wǎng)絡(luò)結(jié)構(gòu),采用雙向同步機(jī)制,同步精度較高,在同步過(guò)程中信息交換量為O(2n+1)。當(dāng)n變大時(shí),TPSN算法的信息交換量遠(yuǎn)低于RBS的信息交換量,常用于大規(guī)模網(wǎng)絡(luò),且易于實(shí)現(xiàn)。但是TPSN算法中未考慮根節(jié)點(diǎn)的失效問(wèn)題,且同步精度隨著網(wǎng)絡(luò)跳數(shù)的增加而降低??紤]到上述問(wèn)題,本文提出了一種新的同步算法:創(chuàng)建分簇型網(wǎng)絡(luò)結(jié)構(gòu),通過(guò)分簇降低網(wǎng)絡(luò)跳數(shù)避免同步誤差的積累量增大,同時(shí)用簇首節(jié)點(diǎn)代替根節(jié)點(diǎn),通過(guò)周期性選取簇首節(jié)點(diǎn),均衡簇首節(jié)點(diǎn)的能量消耗,降低簇首節(jié)點(diǎn)的失效率。在同步過(guò)程中,同時(shí)采用單向廣播同步機(jī)制和雙向時(shí)間同步機(jī)制,提高同步過(guò)程中的同步精度。
本文提出的算法分為2個(gè)階段:分簇結(jié)構(gòu)的建立階段和時(shí)間同步階段。在分簇結(jié)構(gòu)的建立階段,利用本文提出的優(yōu)化LEACH算法創(chuàng)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),并選取各簇簇首節(jié)點(diǎn),其他節(jié)點(diǎn)根據(jù)收到簇首節(jié)點(diǎn)發(fā)送消息的信號(hào)強(qiáng)度選擇加入簇,使每個(gè)節(jié)點(diǎn)均處于簇結(jié)構(gòu)中。在時(shí)間同步階段,首先進(jìn)行的是簇首節(jié)點(diǎn)或助理簇首節(jié)點(diǎn)與基站之間的時(shí)間同步,該階段使用雙向時(shí)間同步機(jī)制;其次,完成上述時(shí)間同步階段后,開(kāi)始啟動(dòng)簇首節(jié)點(diǎn)與同簇內(nèi)其他節(jié)點(diǎn)的時(shí)間同步階段,在該階段使用雙向時(shí)間同步機(jī)制與單向廣播時(shí)間同步機(jī)制相結(jié)合的時(shí)間同步機(jī)制。
在無(wú)線傳感器網(wǎng)絡(luò)層次型拓?fù)淇刂扑惴ǚ矫?,研究者提出了較多經(jīng)典拓?fù)浣Y(jié)構(gòu)控制算法。其中,較為經(jīng)典的是LEACH(Low Energy Adaptive Clustering Hierarchy)算法[8],該算法能夠周期性自動(dòng)形成簇型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),運(yùn)行階段可分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。在LEACH算法選取簇首節(jié)點(diǎn)過(guò)程中,節(jié)點(diǎn)產(chǎn)生一個(gè)0~1的隨機(jī)數(shù),若該隨機(jī)數(shù)小于閾值T(n),則該節(jié)點(diǎn)以T(n)的概率當(dāng)選簇首節(jié)點(diǎn)。已當(dāng)選過(guò)的節(jié)點(diǎn)則把T(n)的值設(shè)置為0,在下輪選取中不再當(dāng)選。閾值T(n)表示為
LEACH算法可以保證每一個(gè)傳感器節(jié)點(diǎn)以相同的概率當(dāng)選簇首節(jié)點(diǎn),均衡了簇首節(jié)點(diǎn)所消耗的能量,從而避免了因簇首節(jié)點(diǎn)能量過(guò)低而導(dǎo)致全網(wǎng)絡(luò)失效的情況出現(xiàn),較好地提高了整個(gè)網(wǎng)絡(luò)的運(yùn)行時(shí)間。但是LEACH算法存在著一些缺陷:首先,該算法在簇首選取機(jī)制中,傳感器節(jié)點(diǎn)隨機(jī)數(shù)產(chǎn)生的隨機(jī)性較強(qiáng),有可能導(dǎo)致產(chǎn)生較多的傳感器節(jié)點(diǎn)距離簇首節(jié)點(diǎn)的位置較遠(yuǎn),容易造成簇首節(jié)點(diǎn)的能量消耗過(guò)多、過(guò)快;其次,該算法簇首選取機(jī)制中并沒(méi)有考慮到傳感器節(jié)點(diǎn)的初始能量和剩余能量的問(wèn)題,有可能會(huì)出現(xiàn)剩余能量較低的節(jié)點(diǎn)被選取為簇首節(jié)點(diǎn),加速簇首節(jié)點(diǎn)因能量消耗過(guò)快而迅速導(dǎo)致死亡。
針對(duì)以上LEACH算法中存在的缺陷,本文提出的時(shí)間同步算法提供了良好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。本文提出了一種LEACH優(yōu)化算法,在優(yōu)化算法中,簇首節(jié)點(diǎn)選取閾值中融入簇首節(jié)點(diǎn)剩余能量和鄰居節(jié)點(diǎn)密度因子,同時(shí)在非簇首節(jié)點(diǎn)中選取助理簇首節(jié)點(diǎn)用以均衡簇首節(jié)點(diǎn)的能量消耗。設(shè)定簇首節(jié)點(diǎn)選取的時(shí)間門(mén)限值Tth,該值與節(jié)點(diǎn)的剩余能量相關(guān),使簇首節(jié)點(diǎn)的當(dāng)選周期與剩余能量有關(guān)。優(yōu)化算法的具體描述如下:
定義E0為傳感器節(jié)點(diǎn)的初始能量,在本文中,假定所有傳感器節(jié)點(diǎn)的初始能量E0是相等的;定義Eres(r)為第r輪簇首節(jié)點(diǎn)選取時(shí),節(jié)點(diǎn)i的剩余能量,則節(jié)點(diǎn)i從網(wǎng)絡(luò)結(jié)構(gòu)初始化至第r輪簇首選取時(shí),因接收、發(fā)送消息共消耗的能量(r),(r)分別為
式中:為第m輪期間,節(jié)點(diǎn)i接收數(shù)據(jù)的比特?cái)?shù);為第m輪期間,節(jié)點(diǎn)i發(fā)送數(shù)據(jù)的比特?cái)?shù);dm為第m輪期間節(jié)點(diǎn)i的通信距離總和。
在綜合分析以上兩個(gè)因素對(duì)簇首節(jié)點(diǎn)的影響后,結(jié)合上述公式,本文提出了優(yōu)化算法的簇首節(jié)點(diǎn)選取機(jī)制的閾值T'(n),T'(n)表達(dá)式為
式中:N為無(wú)線傳感器網(wǎng)絡(luò)簇首節(jié)點(diǎn)的總次數(shù);α根據(jù)網(wǎng)絡(luò)的實(shí)際情況確定且0<α<1。
由于簇首節(jié)點(diǎn)在整個(gè)時(shí)間同步算法中具有重要的作用,其一但失效不僅會(huì)影響時(shí)間同步機(jī)制的同步精度,嚴(yán)重者甚至?xí)<罢麄€(gè)無(wú)線傳感器網(wǎng)絡(luò)的使用壽命。同時(shí),簇首節(jié)點(diǎn)將與基站和簇內(nèi)非同步節(jié)點(diǎn)進(jìn)行大量的信息交換,能量消耗要遠(yuǎn)超過(guò)簇內(nèi)其他節(jié)點(diǎn)。為了均衡簇首節(jié)點(diǎn)的能量消耗,提高整個(gè)網(wǎng)絡(luò)的能量利用率,本文提出一種簇首節(jié)點(diǎn)助理機(jī)制。在該機(jī)制中,該節(jié)點(diǎn)主要用來(lái)實(shí)現(xiàn)數(shù)據(jù)融合并將融合后的數(shù)據(jù)傳遞給基站。所以在助理簇首節(jié)點(diǎn)選取的過(guò)程中,該節(jié)點(diǎn)與基站位置的距離成為重要的選取原則。定義dBS(i)為節(jié)點(diǎn)i與基站之間的距離,則助理簇首節(jié)點(diǎn)的選取閾值為
式中:β和γ均根據(jù)網(wǎng)絡(luò)的實(shí)際情況所定,β和γ均為小于1的實(shí)數(shù);G'為簇內(nèi)非簇首節(jié)點(diǎn)。
時(shí)間同步階段主要分為2個(gè)階段:簇首節(jié)點(diǎn)及助理簇首節(jié)點(diǎn)與基站的時(shí)間同步階段;簇首節(jié)點(diǎn)與同簇內(nèi)待同步節(jié)點(diǎn)時(shí)間同步階段。在簇首節(jié)點(diǎn)及助理簇首節(jié)點(diǎn)與基站間的時(shí)間同步階段采用雙向時(shí)間同步機(jī)制。在簇首節(jié)點(diǎn)與同簇內(nèi)的其他待同步節(jié)點(diǎn)時(shí)間同步階段采用雙向時(shí)間同步機(jī)制和單向時(shí)間同步機(jī)制混合式時(shí)間同步機(jī)制。
在簇首節(jié)點(diǎn)及助理簇首節(jié)點(diǎn)與基站實(shí)現(xiàn)時(shí)間同步的階段,時(shí)間同步原理如圖1所示,簇首節(jié)點(diǎn)或助理簇首節(jié)點(diǎn)在T1時(shí)刻向基站發(fā)送時(shí)間同步請(qǐng)求消息,基站在T2時(shí)刻收到該請(qǐng)求消息后,并在T3時(shí)刻響應(yīng)該消息,簇首節(jié)點(diǎn)或助理簇首節(jié)點(diǎn)在T4時(shí)刻收到基站發(fā)送的響應(yīng)消息。根據(jù)式(7)和式(8)計(jì)算自身節(jié)點(diǎn)與基站之間的時(shí)間偏差和時(shí)間消息傳播時(shí)延,并根據(jù)計(jì)算結(jié)果調(diào)整自身本地時(shí)鐘,從而實(shí)現(xiàn)簇首節(jié)點(diǎn)或助理簇首節(jié)點(diǎn)與基站的時(shí)間同步。
式中:d為消息傳播時(shí)延;Δ為兩節(jié)點(diǎn)間的時(shí)間偏移值。
圖1 簇首節(jié)點(diǎn)或助理簇首節(jié)點(diǎn)與基站時(shí)間同步原理圖
在簇首節(jié)點(diǎn)與同簇內(nèi)待同步節(jié)點(diǎn)時(shí)間同步階段,采用雙向時(shí)間同步機(jī)制和單向廣播時(shí)間同步機(jī)制混合式時(shí)間同步機(jī)制。具體同步過(guò)程如下:
1)簇首節(jié)點(diǎn)在T1時(shí)刻廣播啟動(dòng)簇內(nèi)節(jié)點(diǎn)時(shí)間同步消息,簇內(nèi)各節(jié)點(diǎn)記錄各自收到該廣播消息的時(shí)刻Tk(i),并保存該時(shí)刻。
2)隨機(jī)選擇一簇內(nèi)待同步節(jié)點(diǎn),并在T2時(shí)刻響應(yīng)該廣播消息,并發(fā)送響應(yīng)消息給簇首節(jié)點(diǎn)。該消息中包含其在步驟1)中收到的時(shí)間同步啟動(dòng)消息的時(shí)刻T2和發(fā)送響應(yīng)消息的時(shí)刻T3。
3)簇首節(jié)點(diǎn)于T4時(shí)刻收到該響應(yīng)節(jié)點(diǎn)發(fā)送的響應(yīng)消息,并根據(jù)式(7)和式(8)計(jì)算簇首節(jié)點(diǎn)與該相應(yīng)節(jié)點(diǎn)間的時(shí)間偏移值Δ和消息傳播延遲d。
4)簇首節(jié)點(diǎn)廣播時(shí)間校正消息,該消息中包含響應(yīng)節(jié)點(diǎn)在步驟1)中收到的時(shí)間同步啟動(dòng)消息的時(shí)刻T2以及步驟3)中簇首節(jié)點(diǎn)計(jì)算出的時(shí)間偏移值Δ和消息傳播延遲d。
5)簇內(nèi)待同步節(jié)點(diǎn)收到步驟4)中的時(shí)間校正消息后,讀取該消息包,比較在步驟1)中自身保存的Tk(i)與T2值的大小,得到自己與簇首節(jié)點(diǎn)間的時(shí)鐘偏差,并根據(jù)δ'調(diào)整本地時(shí)鐘,從而實(shí)現(xiàn)待同步節(jié)點(diǎn)與簇首節(jié)點(diǎn)間的同步。
簇首節(jié)點(diǎn)與同簇內(nèi)待同步節(jié)點(diǎn)時(shí)間同步機(jī)制原理圖如圖2所示。
圖2 簇首節(jié)點(diǎn)與同簇內(nèi)待同步節(jié)點(diǎn)時(shí)間同步原理圖
為了驗(yàn)證本文提出的優(yōu)化算法性能,對(duì)所提出的優(yōu)化算法進(jìn)行了實(shí)驗(yàn)仿真,并與TPSN算法的實(shí)驗(yàn)仿真結(jié)果進(jìn)行比較。在實(shí)驗(yàn)中假設(shè)基站的能量是無(wú)窮的,所有傳感器節(jié)點(diǎn)均是不可移動(dòng)的。其中,節(jié)點(diǎn)部署范圍100 m×100 m,基站位置(50,50),節(jié)點(diǎn)數(shù)300,節(jié)點(diǎn)的初始能量E0為0.15 J,Eelse為50 nJ/bit,Efs為10 pJ/(bit×m2)。
從圖3可知,本文算法與TPSN算法隨著節(jié)點(diǎn)數(shù)目的增加,節(jié)點(diǎn)的信息交換量也隨之增加。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目小于50時(shí),二者之間的差距不明顯,但是隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的增多,TPSN算法中的信息交換量要明顯大于相同數(shù)目下本文算法中的信息交換量。導(dǎo)致這種情況出現(xiàn)的原因是:TPSN算法中同步節(jié)點(diǎn)采用雙向時(shí)間同步機(jī)制,每對(duì)節(jié)點(diǎn)間實(shí)現(xiàn)同步需要2條消息進(jìn)行交換。而在本文算法中,只有簇首節(jié)點(diǎn)和助理簇首節(jié)點(diǎn)采用雙向同步機(jī)制,而在簇內(nèi)節(jié)點(diǎn)進(jìn)行同步時(shí),采用單向廣播時(shí)間同步機(jī)制。在整個(gè)網(wǎng)絡(luò)中,采用單向廣播時(shí)間同步機(jī)制的節(jié)點(diǎn)數(shù)目要遠(yuǎn)小于采用雙向時(shí)間同步機(jī)制的節(jié)點(diǎn)數(shù)目。所以當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目增多時(shí),本文算法在信息交換量的優(yōu)勢(shì)明顯優(yōu)于TPSN算法。
圖3 本文算法與TPSN算法信息交換量的比較
由圖4可知,本文算法與TPSN算法在同步過(guò)程中,隨著跳數(shù)的增加同步誤差越來(lái)越大。TPSN中同步誤差一方面由于雙向時(shí)間同步機(jī)制中存在消息傳播時(shí)延,更主要的是隨著跳數(shù)的增加,同步誤差在逐漸積累,導(dǎo)致隨著跳數(shù)的增加同步誤差越來(lái)越大。本文算法中出現(xiàn)的同步誤差首先出現(xiàn)在簇首節(jié)點(diǎn)與基站進(jìn)行的雙向時(shí)間同步機(jī)制,其次,較大程度的同步誤差是由于簇首節(jié)點(diǎn)在簇內(nèi)節(jié)點(diǎn)同步過(guò)程中隨機(jī)選擇的應(yīng)答節(jié)點(diǎn)。若應(yīng)答節(jié)點(diǎn)與周圍鄰居節(jié)點(diǎn)的時(shí)鐘偏移存在較大誤差,則也會(huì)導(dǎo)致本文中同步精度的降低。同時(shí),亦可觀察到,當(dāng)網(wǎng)絡(luò)跳數(shù)等于1時(shí),二者之間存在較小的差距,但是隨著跳數(shù)的增加,在相同的網(wǎng)絡(luò)跳數(shù)情況下,本文的同步誤差要小于TPSN算法中的同步誤差,即本文的時(shí)間同步精度要高于TPSN時(shí)間同步精度。
圖4 本文算法與TPSN算法同步誤差的比較
如圖5所示,在相同的輪數(shù)情況下,本文算法節(jié)點(diǎn)消耗的能量要低于TPSN算法。其主要原因是在本文算法中采用分簇型網(wǎng)絡(luò)結(jié)構(gòu),在簇首節(jié)點(diǎn)閾值中融入節(jié)點(diǎn)剩余能量因子和鄰居節(jié)點(diǎn)密度因子。鄰居節(jié)點(diǎn)密度因子越大,簇首節(jié)點(diǎn)周圍的鄰居節(jié)點(diǎn)數(shù)目也就越多,簇內(nèi)節(jié)點(diǎn)的部署也越均勻,簇首節(jié)點(diǎn)的通信總距離也就越小,從而簇首節(jié)點(diǎn)的通信消耗也就越小。另一方面,本文設(shè)定簇首節(jié)點(diǎn)的當(dāng)選時(shí)間門(mén)限值,該值隨著簇首節(jié)點(diǎn)剩余能量的變化自動(dòng)變化簇首時(shí)間的當(dāng)選周期,剩余能量越低,簇首節(jié)點(diǎn)的當(dāng)選時(shí)間也就越短,縮短簇首節(jié)點(diǎn)的工作時(shí)間,從而降低了節(jié)點(diǎn)的能量消耗。最后,本文中助理簇首節(jié)點(diǎn)均衡了簇首節(jié)點(diǎn)的能量消耗,提高了網(wǎng)絡(luò)利用率。
本文提出一種新的時(shí)間同步算法,在該算法的分簇結(jié)構(gòu)創(chuàng)建階段,簇首選取閾值融入簇首節(jié)點(diǎn)的剩余能量因子和鄰居節(jié)點(diǎn)密度因子,同時(shí)設(shè)定了助理簇首節(jié)點(diǎn)和簇首節(jié)點(diǎn)工作時(shí)間門(mén)限值,較好地優(yōu)化了網(wǎng)絡(luò)結(jié)構(gòu),降低了網(wǎng)絡(luò)的跳數(shù)。在時(shí)間同步階段,采用了雙向時(shí)間同步機(jī)制和單向廣播時(shí)間同步機(jī)制。實(shí)驗(yàn)證明,該算法降低了網(wǎng)絡(luò)跳數(shù),提高了時(shí)間同步精度,降低了節(jié)點(diǎn)的能量消耗,延長(zhǎng)了無(wú)線傳感器網(wǎng)絡(luò)的運(yùn)行壽命,具有一定的實(shí)用價(jià)值。
圖5 本文算法簇首節(jié)點(diǎn)與TPSN算法根節(jié)點(diǎn)剩余能量比較
:
[1]程敏敏,宋家友,張漢.基于梯度的分簇式路由協(xié)議[J].電視技術(shù),2012,36(15):108-111.
[2]汪富強(qiáng),曾鵬,于海斌.一種低開(kāi)銷的時(shí)間同步算法[J].儀器儀表學(xué)報(bào),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ú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.
[8]周治平,王亭,張明亮.傳感網(wǎng)絡(luò)中一種能量有效的簇頭選舉機(jī)制[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(8):105-108.