基于數(shù)據(jù)引流的無線傳感器網(wǎng)絡(luò)能量空洞避免研究

王施雨， 劉 唐

(1. 東北師范大學(xué) 物理學(xué)院, 吉林 長春 130024； 2. 四川師范大學(xué) 基礎(chǔ)教學(xué)學(xué)院, 四川 成都 610066)

近年來,隨著無線通信技術(shù)與微電子技術(shù)的持續(xù)發(fā)展,無線傳感器網(wǎng)絡(luò)(WSN)[1]得到越來越廣泛的應(yīng)用.傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)通常由能量有限的電池供電,這些節(jié)點(diǎn)在部署后難以更換電池,所以無線傳感器網(wǎng)絡(luò)有著嚴(yán)重的能量約束問題[2].

在采用多跳數(shù)據(jù)傳輸?shù)臒o線傳感器網(wǎng)絡(luò)中,如果某些節(jié)點(diǎn)承擔(dān)了更大的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),它們的能量消耗速度會(huì)明顯快于其他節(jié)點(diǎn),因而這些節(jié)點(diǎn)會(huì)首先死亡.在這些節(jié)點(diǎn)死亡后,它們負(fù)責(zé)轉(zhuǎn)發(fā)的數(shù)據(jù)將很難再有效傳輸至sink,此時(shí)網(wǎng)絡(luò)壽命結(jié)束,而網(wǎng)絡(luò)中其他節(jié)點(diǎn)內(nèi)大量的剩余能量被浪費(fèi),這種現(xiàn)象被稱為“能量空洞”[3-4].文獻(xiàn)[5]的實(shí)驗(yàn)結(jié)果表明當(dāng)網(wǎng)絡(luò)中出現(xiàn)能量空洞,網(wǎng)絡(luò)壽命結(jié)束時(shí),網(wǎng)絡(luò)中還剩余高達(dá)90%的能量被浪費(fèi).

在無線傳感器網(wǎng)絡(luò)的真實(shí)應(yīng)用場景下,傳感器節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生量會(huì)根據(jù)環(huán)境實(shí)時(shí)發(fā)生變化.例如,對(duì)用于面向人群監(jiān)控任務(wù)的傳感器網(wǎng)絡(luò),節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生速率與被監(jiān)控的人員數(shù)量密切相關(guān).由于人類出行的時(shí)空規(guī)律性[6],在不同時(shí)間被某個(gè)節(jié)點(diǎn)監(jiān)控的人員數(shù)量會(huì)有所不同,這使得該節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生速率會(huì)呈現(xiàn)有規(guī)律的動(dòng)態(tài)變化.因此,網(wǎng)絡(luò)中的節(jié)點(diǎn)的能耗負(fù)載也呈現(xiàn)出動(dòng)態(tài)變化的特點(diǎn).

近年來,盡管能量空洞現(xiàn)象已經(jīng)引起了研究者們的廣泛關(guān)注,并取得了一定的研究成果,但是還沒有面向由真實(shí)場景下節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生速率動(dòng)態(tài)變化造成的能量空洞問題的解決方案.

在對(duì)前人工作進(jìn)行總結(jié)的基礎(chǔ)上,為有效避免由節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生速率動(dòng)態(tài)發(fā)生變化造成的節(jié)點(diǎn)能量空洞現(xiàn)象,提出了一種數(shù)據(jù)引流的非均勻分簇算法FRUC.本文主要工作如下：

1) 利用分簇進(jìn)行數(shù)據(jù)收集與傳輸,但與傳統(tǒng)的非均勻分簇不同,FRUC算法在網(wǎng)絡(luò)初始階段對(duì)網(wǎng)絡(luò)進(jìn)行分層,每層網(wǎng)絡(luò)層高不等,簇的范圍限制在層內(nèi)；

2) 考慮所有節(jié)點(diǎn)的數(shù)據(jù)平均產(chǎn)生率,給出網(wǎng)絡(luò)各層內(nèi)的簇頭節(jié)點(diǎn)完成一次簇內(nèi)、簇間數(shù)據(jù)處理所消耗能量的計(jì)算方法,并讓網(wǎng)絡(luò)各層的層高取值滿足各層之間的所有簇頭節(jié)點(diǎn)的能耗均衡；

3) 考慮節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生率的動(dòng)態(tài)變化對(duì)路由負(fù)載的影響,引入基于數(shù)據(jù)引流的數(shù)據(jù)傳輸方法,讓一個(gè)簇的發(fā)送數(shù)據(jù)量發(fā)生變化時(shí),數(shù)據(jù)不再只發(fā)送給一個(gè)固定的簇頭,而是動(dòng)態(tài)地將數(shù)據(jù)引流到多個(gè)簇頭.

1 相關(guān)工作

目前,能量空洞作為無線傳感器網(wǎng)絡(luò)中一個(gè)瓶頸性的問題,國內(nèi)外許多研究者進(jìn)行了大量研究.

為了有效均衡網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)能耗,解決能量空洞問題,研究者們提出了許多不同的策略來緩解能量空洞現(xiàn)象造成的影響.其中,研究者利用的技術(shù)包括：部署移動(dòng)sink、利用非均勻分簇算法、采用不同的傳輸策略、傳感器節(jié)點(diǎn)的非均勻分布等.下面介紹與本文研究相關(guān)的非均勻分簇算法研究.

與LEACH[7]、HEED[8]這樣的傳統(tǒng)分簇算法不同,非均勻分簇算法讓網(wǎng)絡(luò)中的各個(gè)簇具有不等的簇規(guī)模,以使有更大能耗的區(qū)域簇規(guī)模減小,有更小能耗的區(qū)域簇規(guī)模增大,從而均衡網(wǎng)絡(luò)內(nèi)各區(qū)域的節(jié)點(diǎn)負(fù)載,延遲能量空洞的出現(xiàn)并延長網(wǎng)絡(luò)壽命.

文獻(xiàn)[9]提出了一種分布式分簇路由協(xié)議DEBUC,該協(xié)議采用基于時(shí)間的簇頭競爭算法,節(jié)點(diǎn)的廣播時(shí)間由其鄰居節(jié)點(diǎn)和候選簇頭的當(dāng)前剩余能量決定.同時(shí),通過控制不同網(wǎng)絡(luò)區(qū)域的候選簇頭的競爭半徑,使得距離sink較近的簇規(guī)模較小.與之相類似的還包括文獻(xiàn)[10]提出的EEUC算法,該算法通過控制簇頭的競爭半徑來調(diào)整簇的規(guī)模,使靠近sink的簇比遠(yuǎn)離sink的簇?fù)碛懈〉拇匕霃?

文獻(xiàn)[11]將非均勻分簇引入節(jié)點(diǎn)非均勻分布的網(wǎng)絡(luò),以避免能量空洞問題，并提出了一個(gè)最小化網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)能耗的最優(yōu)簇結(jié)構(gòu)方法，還設(shè)計(jì)了一個(gè)簡單的分布式路由協(xié)議以實(shí)現(xiàn)所有節(jié)點(diǎn)能耗均衡.

文獻(xiàn)[12]提出了ACT分簇路由協(xié)議.該協(xié)議將網(wǎng)絡(luò)分層,簇的規(guī)模限制在層內(nèi).文獻(xiàn)[12]計(jì)算了簇頭節(jié)點(diǎn)的能耗,并讓網(wǎng)絡(luò)各層的大小滿足在一個(gè)簇周期,各層內(nèi)的單個(gè)簇頭節(jié)點(diǎn)的能耗相等.但是,由于各層規(guī)模不同,各層內(nèi)的簇頭節(jié)點(diǎn)數(shù)目也不同.因此該算法并沒有保證在一個(gè)簇周期內(nèi)各層中所有的節(jié)點(diǎn)能耗之和相等,因而該協(xié)議并不能真正均衡各層的能耗.

文獻(xiàn)[6]研究了異構(gòu)網(wǎng)絡(luò)中如何避免能量空洞.針對(duì)異構(gòu)環(huán)境下各個(gè)簇產(chǎn)生的數(shù)據(jù)量不等且未知的條件,文獻(xiàn)[6]提出了一種基于反饋機(jī)制的分均勻成簇算法.

文獻(xiàn)[13]的研究針對(duì)由初始能量較大節(jié)點(diǎn)擔(dān)任簇頭、初始能量較小的節(jié)點(diǎn)作為簇內(nèi)成員節(jié)點(diǎn)的異構(gòu)傳感器網(wǎng)絡(luò),提出了基于不等簇半徑的能量空洞避免策略.文獻(xiàn)[13]從理論上推導(dǎo)出距離sink不同距離處簇半徑的大小,并給出了不等簇半徑的取值與優(yōu)化方法.

文獻(xiàn)[14]提出了一個(gè)能量有效的分布式成簇算法,該算法根據(jù)與sink節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)距離確定適當(dāng)?shù)拇匕霃?以實(shí)現(xiàn)節(jié)點(diǎn)壽命的大致均衡.文獻(xiàn)[14]還提出了一個(gè)簡單的高效節(jié)能多跳數(shù)據(jù)收集協(xié)議來對(duì)成簇算法進(jìn)行評(píng)價(jià),并計(jì)算出該協(xié)議的能耗.

文獻(xiàn)[15]提出了一個(gè)模糊能量感知的非均勻分簇算法EAUCF.該算法為降低靠近sink的簇頭節(jié)點(diǎn)和低剩余能量簇頭節(jié)點(diǎn)的工作負(fù)載,引入模糊邏輯方法以處理簇頭半徑估計(jì)的不確定性.

文獻(xiàn)[16]提出了一種流量均衡路由算法FBR.與已有的路由算法不同,FBR的骨干網(wǎng)絡(luò)構(gòu)造算法構(gòu)建了一種新的多層次骨干網(wǎng)絡(luò),該網(wǎng)絡(luò)不同于傳統(tǒng)樹形的簇頭通信拓?fù)浣Y(jié)構(gòu),而是每個(gè)簇頭擁有多個(gè)父節(jié)點(diǎn).簇頭間進(jìn)行數(shù)據(jù)傳遞時(shí),簇頭將待發(fā)送數(shù)據(jù)分發(fā)給多個(gè)父節(jié)點(diǎn),以平衡父節(jié)點(diǎn)的能耗,延長網(wǎng)絡(luò)壽命.但是該分簇算法讓每個(gè)簇的簇半徑相等,因此各簇能耗很難實(shí)現(xiàn)完全均衡.同時(shí),該算法并未讓所有的節(jié)點(diǎn)輪流擔(dān)當(dāng)簇頭,因此簇頭節(jié)點(diǎn)能耗速度明顯快于普通節(jié)點(diǎn).

2 網(wǎng)絡(luò)模型

2.1網(wǎng)絡(luò)模型本文定義W×L(m)的矩形網(wǎng)絡(luò)中分布著N個(gè)傳感器節(jié)點(diǎn).圖1給出了網(wǎng)絡(luò)模型示意圖,表1為相關(guān)符號(hào)說明.設(shè)該傳感器網(wǎng)絡(luò)性質(zhì)如下：

1) 唯一的sink節(jié)點(diǎn)位于網(wǎng)絡(luò)邊緣,sink以基站形式部署；

2) 網(wǎng)絡(luò)中所有的傳感器節(jié)點(diǎn)滿足隨機(jī)分布,節(jié)點(diǎn)的發(fā)射功率可調(diào),且在部署后靜止不動(dòng)；

3) 傳感器節(jié)點(diǎn)被組織成簇的形式,各簇的范圍限制在網(wǎng)絡(luò)分層內(nèi),簇頭節(jié)點(diǎn)在完成簇內(nèi)數(shù)據(jù)收集后,以簇間多跳形式將數(shù)據(jù)發(fā)送到sink節(jié)點(diǎn)；

4) 傳感器節(jié)點(diǎn)在不同時(shí)刻的數(shù)據(jù)產(chǎn)生率動(dòng)態(tài)變化,根據(jù)監(jiān)控區(qū)域的歷史數(shù)據(jù),在網(wǎng)絡(luò)生命周期內(nèi)的節(jié)點(diǎn)平均數(shù)據(jù)產(chǎn)生率可知.

2.2能耗模型本文采用典型的能量消耗模型[17],在數(shù)據(jù)傳輸過程中,傳感器節(jié)點(diǎn)傳輸lbit數(shù)據(jù)經(jīng)過距離d,產(chǎn)生的能耗為

ETx(l,d)=ETx_elec(k)+ETTx_amp(l,d)=

(1)

接收端所產(chǎn)生的能耗為

ERx(l)=ERx_elec(l)=lEelec，

(2)

其中,d0為一閾值,當(dāng)數(shù)據(jù)傳輸距離小于d0時(shí),發(fā)送方的能耗與距離的平方成正比,否則與距離的4次方成正比.Eelec表示發(fā)送或接收1 bit數(shù)據(jù)時(shí)的能量消耗,εfsd2和εmpd4是發(fā)送1 bit數(shù)據(jù)放大器的能量消耗.

圖 1 網(wǎng)絡(luò)模型結(jié)構(gòu)

符號(hào)含義W網(wǎng)絡(luò)寬度L網(wǎng)絡(luò)長度Li第i層網(wǎng)絡(luò)Hi第i層網(wǎng)絡(luò)的層高Ci第i層網(wǎng)絡(luò)中的簇‖Ci‖簇Ci的面積r(Cj)簇Ci的半徑ρ網(wǎng)絡(luò)中的節(jié)點(diǎn)密度ECHi簇Ci的簇頭節(jié)點(diǎn)在一個(gè)簇周期內(nèi)的能耗Eini簇Ci的簇頭節(jié)點(diǎn)一個(gè)簇周期內(nèi)用于完成簇內(nèi)數(shù)據(jù)處理的能耗Eiti簇Ci的簇頭節(jié)點(diǎn)一個(gè)簇周期內(nèi)用于完成簇間數(shù)據(jù)處理的能耗Ei第i層網(wǎng)絡(luò)中所有簇頭節(jié)點(diǎn)在一個(gè)簇周期的總能耗

3 網(wǎng)絡(luò)能耗分析與非均勻分層

在多跳傳感器網(wǎng)絡(luò)中,靠近sink的簇頭節(jié)點(diǎn)由于承擔(dān)更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),因而有著更大的能耗.通過傳感器節(jié)點(diǎn)的平均數(shù)據(jù)產(chǎn)生率,建立網(wǎng)絡(luò)各簇頭節(jié)點(diǎn)的能耗計(jì)算模型,提出基于網(wǎng)絡(luò)層次劃分的非均勻分簇模型,讓靠近sink的網(wǎng)絡(luò)分層內(nèi)的簇規(guī)模更小,讓遠(yuǎn)離sink的網(wǎng)絡(luò)分層內(nèi)的簇規(guī)模更大.

π(r(Ci))2ρlEelec.

(3)

因此,簇頭節(jié)點(diǎn)CHi接收外層網(wǎng)絡(luò)的數(shù)據(jù)所消耗的能量為

簇頭節(jié)點(diǎn)CHi發(fā)送到內(nèi)層網(wǎng)絡(luò)的數(shù)據(jù)包括接收的外層網(wǎng)絡(luò)數(shù)據(jù)及簇內(nèi)節(jié)點(diǎn)發(fā)送到簇頭的數(shù)據(jù),因此CHi需要發(fā)送到內(nèi)層網(wǎng)絡(luò)的數(shù)據(jù)總量為

根據(jù)能量消耗模型,簇頭節(jié)點(diǎn)CHi發(fā)送所有數(shù)據(jù)所消耗的能量為

根據(jù)(5)和(7)式能得出簇頭節(jié)點(diǎn)CHi在一個(gè)簇周期完成簇間數(shù)據(jù)處理所消耗的能量為

傳感器網(wǎng)絡(luò)中,簇頭節(jié)點(diǎn)承擔(dān)了數(shù)據(jù)收集和轉(zhuǎn)發(fā)任務(wù),它們的能耗遠(yuǎn)大于簇內(nèi)普通節(jié)點(diǎn).為避免能量空洞現(xiàn)象的出現(xiàn),應(yīng)著重考察在一個(gè)簇周期內(nèi),簇內(nèi)節(jié)點(diǎn)的能耗.由于網(wǎng)絡(luò)各層的簇頭節(jié)點(diǎn)數(shù)量不等,因而僅僅比較網(wǎng)絡(luò)各層內(nèi)單個(gè)簇頭節(jié)點(diǎn)的能耗,并不能有效平衡網(wǎng)絡(luò)各層的總能耗.因此,為避免能量空洞現(xiàn)象的出現(xiàn),平衡網(wǎng)絡(luò)各層的能耗,在一個(gè)簇周期內(nèi)網(wǎng)絡(luò)各層內(nèi)的所有簇頭節(jié)點(diǎn)的能耗之和應(yīng)相等.

對(duì)第i層網(wǎng)絡(luò),其所有簇頭節(jié)點(diǎn)的總能耗為

(9)

(10)式給出了為平衡網(wǎng)絡(luò)各層的能耗,各層層高應(yīng)滿足的條件

(10)

4 基于數(shù)據(jù)引流的路由算法描述

下面首先討論如何選擇簇頭,進(jìn)一步給出基于數(shù)據(jù)引流的路由算法.

4.1簇頭選擇在網(wǎng)絡(luò)首輪成簇前,網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)使用一定的傳輸能量進(jìn)行全網(wǎng)廣播,利用信號(hào)強(qiáng)度在傳輸過程中的衰減,節(jié)點(diǎn)可以感知相互之間的距離.文獻(xiàn)[17]給出了節(jié)點(diǎn)通過信號(hào)發(fā)送強(qiáng)度和接收強(qiáng)度之間的關(guān)系得出節(jié)點(diǎn)間相互距離的計(jì)算方法

(11)

sink在網(wǎng)絡(luò)初始階段以覆蓋全網(wǎng)絡(luò)范圍的廣播強(qiáng)度進(jìn)行一次廣播,網(wǎng)絡(luò)中的各節(jié)點(diǎn)在收到sink的廣播后根據(jù)(11)式得到自身與sink的距離,確定所屬網(wǎng)絡(luò)層次.進(jìn)一步,各節(jié)點(diǎn)在所屬網(wǎng)絡(luò)分層內(nèi)廣播包含自身當(dāng)前剩余能量信息的簇頭競爭消息.如果某節(jié)點(diǎn)發(fā)現(xiàn)自身的當(dāng)前剩余能量大于收到廣播的其他節(jié)點(diǎn)能量,該節(jié)點(diǎn)就發(fā)布成為簇頭的廣播.

4.2數(shù)據(jù)引流簇頭節(jié)點(diǎn)在每個(gè)簇周期收到簇內(nèi)各節(jié)點(diǎn)的數(shù)據(jù)后,需要將這些數(shù)據(jù)在網(wǎng)絡(luò)分層中進(jìn)行轉(zhuǎn)發(fā),以最終發(fā)送至sink.在傳統(tǒng)的多跳傳感器網(wǎng)絡(luò)中,一個(gè)數(shù)據(jù)包到sink之間只有一條固定的簇間路由路徑,如圖2所示.

圖 2 固定路由示意圖

這種固定簇間路由存在的問題如下：

1) 由于網(wǎng)絡(luò)各層的層高不等,各層內(nèi)的簇頭數(shù)量也不等,因而在簇頭數(shù)量較多的內(nèi)層網(wǎng)絡(luò)中,各簇頭的負(fù)載必然不均衡,會(huì)出現(xiàn)某些簇頭承擔(dān)了較多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)而某些簇頭沒有承擔(dān)轉(zhuǎn)發(fā)任務(wù).如圖2所示,越靠近sink的簇頭節(jié)點(diǎn)會(huì)呈現(xiàn)更大的路由負(fù)載不均衡現(xiàn)象.以最內(nèi)層網(wǎng)絡(luò)為例,路由負(fù)載最大的節(jié)點(diǎn),承擔(dān)了來自5個(gè)簇的數(shù)據(jù)轉(zhuǎn)發(fā)量,而該層網(wǎng)絡(luò)中有的簇頭并未承擔(dān)外層網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā).

2) 難以適應(yīng)節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生率隨網(wǎng)絡(luò)環(huán)境變化的動(dòng)態(tài)場景.在節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生率動(dòng)態(tài)變化的場景下,每個(gè)簇頭節(jié)點(diǎn)在每個(gè)簇周期接收到的簇內(nèi)成員產(chǎn)生的數(shù)據(jù)量也會(huì)隨之改變.如果采用傳統(tǒng)的固定簇間路由方法,數(shù)據(jù)轉(zhuǎn)發(fā)量的動(dòng)態(tài)變化會(huì)加重同層內(nèi)的各個(gè)簇頭間的能耗負(fù)載不均現(xiàn)象,從而更快的導(dǎo)致節(jié)點(diǎn)的死亡并出現(xiàn)能量空洞.

為解決上述問題,平衡網(wǎng)絡(luò)內(nèi)各簇簇頭的路由負(fù)載,本文提出一種基于數(shù)據(jù)引流的路由方法,讓一個(gè)簇的數(shù)據(jù)轉(zhuǎn)發(fā)到下一層時(shí),不再只轉(zhuǎn)發(fā)到一個(gè)簇頭,而是根據(jù)各個(gè)簇當(dāng)前需要轉(zhuǎn)發(fā)的數(shù)據(jù)量,實(shí)時(shí)將數(shù)據(jù)引流到多個(gè)簇頭.數(shù)據(jù)引流的思想如下：

1) 每個(gè)簇頭進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時(shí),將本簇產(chǎn)生的數(shù)據(jù)和收到的來自外層簇頭發(fā)送來的數(shù)據(jù),引流到內(nèi)層網(wǎng)絡(luò)中的多個(gè)簇頭；

2) 為實(shí)現(xiàn)避免個(gè)別節(jié)點(diǎn)提前死亡的目的,讓有更多剩余能量的簇頭承擔(dān)更大的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù).在每個(gè)簇周期,各個(gè)簇產(chǎn)生的數(shù)據(jù)量會(huì)動(dòng)態(tài)變化,因此在每個(gè)簇周期開始簇間數(shù)據(jù)傳輸時(shí),考察每個(gè)簇頭的剩余能量和每個(gè)簇頭所在簇內(nèi)的數(shù)據(jù)產(chǎn)生量.在某個(gè)簇頭有數(shù)據(jù)需要轉(zhuǎn)發(fā)時(shí),將更多的數(shù)據(jù)引流到剩余能量更多、簇內(nèi)數(shù)據(jù)量更少的簇頭,以平衡下層網(wǎng)絡(luò)內(nèi)的各個(gè)簇頭的能耗.

對(duì)Li(i≠1)層網(wǎng)絡(luò)中的第j個(gè)簇頭節(jié)點(diǎn)CHi,j,設(shè)當(dāng)前簇周期需傳輸至下一層網(wǎng)絡(luò)的數(shù)據(jù)量為li,j,CHi,j首先啟動(dòng)路由發(fā)現(xiàn)過程,向下一層網(wǎng)絡(luò)中發(fā)出路由請(qǐng)求消息.Li-1層網(wǎng)絡(luò)中所有簇頭在收到請(qǐng)求后,以一定功率發(fā)出包含自身能量信息和當(dāng)前簇周期所在簇的簇內(nèi)數(shù)據(jù)量的應(yīng)答消息.

簇頭節(jié)點(diǎn)CHi,j根據(jù)計(jì)算得出的引流值,將數(shù)據(jù)分為大小不等的若干份,發(fā)送至下一層的各個(gè)簇頭節(jié)點(diǎn).當(dāng)新一輪簇周期,各個(gè)簇產(chǎn)生的數(shù)據(jù)量和各個(gè)簇頭的剩余能量發(fā)生變化時(shí),數(shù)據(jù)引流量也會(huì)動(dòng)態(tài)更新.

圖 3 數(shù)據(jù)引流示意圖

圖3給出了在一個(gè)簇周期進(jìn)行簇間路由時(shí)的數(shù)據(jù)引流示意圖.可以看出,各簇的數(shù)據(jù)被引流到下一層網(wǎng)絡(luò)的多個(gè)簇頭,以平衡每一層內(nèi)的各簇之間的能量消耗,避免部分節(jié)點(diǎn)能量耗盡形成能量空洞.數(shù)據(jù)引流算法流程如下：

For 每一個(gè)簇周期

For 每一個(gè)簇

選舉能量最大的節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)

End for

For 從外到內(nèi)的每一層網(wǎng)絡(luò)

For 每一個(gè)簇頭節(jié)點(diǎn)

計(jì)算簇頭需要發(fā)送的數(shù)據(jù)量

啟動(dòng)路由發(fā)現(xiàn)過程

收到下一層網(wǎng)絡(luò)的應(yīng)答消息

計(jì)算引流到下一層每個(gè)簇頭節(jié)點(diǎn)的數(shù)據(jù)量

End for

End for

各個(gè)簇頭進(jìn)行數(shù)據(jù)發(fā)送

End for

5 仿真實(shí)驗(yàn)

將在Matlab仿真實(shí)驗(yàn)平臺(tái)下,驗(yàn)證提出的算法是否能有效避免.首先對(duì)網(wǎng)絡(luò)分均勻分層進(jìn)行驗(yàn)證,給出在默認(rèn)網(wǎng)絡(luò)環(huán)境下,網(wǎng)絡(luò)各層層高的取值；其次,將討論在網(wǎng)絡(luò)非均勻分層的情況下,數(shù)據(jù)引流對(duì)網(wǎng)絡(luò)性能提升的影響；進(jìn)一步,將對(duì)比LEACH、DEBUC、FBR和本文提出的FRUC4種算法不同的表現(xiàn).選擇這3個(gè)算法進(jìn)行對(duì)比的原因是LEACH是經(jīng)典的分簇算法；DEBUC為了實(shí)現(xiàn)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)能量均勻消耗,通過給出每個(gè)簇頭不同的簇頭競爭半徑值以實(shí)現(xiàn)非均勻分簇；FBR則是首先提出數(shù)據(jù)引流思想的路由算法.

表 2 實(shí)驗(yàn)參數(shù)

在仿真實(shí)驗(yàn)中,網(wǎng)絡(luò)默認(rèn)規(guī)模為250 m×150 m的矩形區(qū)域,唯一的sink位于網(wǎng)絡(luò)的邊緣位置.網(wǎng)絡(luò)帶寬為10 kbps,其他網(wǎng)絡(luò)參數(shù)以及相應(yīng)的缺省值見表2.實(shí)驗(yàn)結(jié)果若未特別說明,均為100次獨(dú)立實(shí)驗(yàn)結(jié)果的均值.

5.1網(wǎng)絡(luò)分層性能首先,在節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生率不變的條件下,考察網(wǎng)絡(luò)分層的情況,并對(duì)網(wǎng)絡(luò)最優(yōu)分層時(shí)各層內(nèi)的簇頭節(jié)點(diǎn)的能耗情況進(jìn)行分析.

表3給出了每個(gè)節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)消息大小為1 000 bit時(shí),由(10)式得出的網(wǎng)絡(luò)各層規(guī)模.

表 3 分層高度

從表3可以看出,在250 m×150 m的網(wǎng)絡(luò)分為了4層,越靠近sink的網(wǎng)絡(luò)分層層高越小,越遠(yuǎn)離sink的網(wǎng)絡(luò)分層層高越大.此時(shí)網(wǎng)絡(luò)壽命(第一個(gè)節(jié)點(diǎn)的死亡時(shí)間)為371輪.進(jìn)一步,隨機(jī)選擇了10輪簇周期,分布考察每個(gè)網(wǎng)絡(luò)分層內(nèi)的簇頭節(jié)點(diǎn)的總能耗.圖4給出了各網(wǎng)絡(luò)各層內(nèi)的簇頭節(jié)點(diǎn)在隨機(jī)選擇的10個(gè)簇周期的總能耗.可以看出,網(wǎng)絡(luò)4層內(nèi)的簇頭節(jié)點(diǎn),在這10個(gè)簇周期的總能耗,一直處于相對(duì)均衡的狀態(tài),能耗值基本上在39～52 mJ之間.這說明了,隨著網(wǎng)絡(luò)被劃分成了高度不等的分層,非均勻分簇能有效平衡網(wǎng)絡(luò)各區(qū)域節(jié)點(diǎn)的能耗.

圖 4 各層簇頭總能耗

進(jìn)一步,圖5顯示了在這10個(gè)簇周期,網(wǎng)絡(luò)各層簇頭節(jié)點(diǎn)總能耗的標(biāo)準(zhǔn)差.可以看出,在隨機(jī)選取的10個(gè)簇周期中,除了2個(gè)簇周期以外,其他8個(gè)簇周期各層簇頭節(jié)點(diǎn)的總能耗差異都很小,其標(biāo)準(zhǔn)差都在3以內(nèi),而層間能耗差異較大的2個(gè)簇周期,標(biāo)準(zhǔn)差也在4.5以內(nèi).這表明了,FRUC算法能有效平衡層間的簇頭能耗.

圖6顯示了每個(gè)網(wǎng)絡(luò)分層內(nèi)的簇頭節(jié)點(diǎn)在10個(gè)簇周期的總能耗標(biāo)準(zhǔn)差.可以看出,在更靠近sink的內(nèi)層網(wǎng)絡(luò)內(nèi),各簇頭節(jié)點(diǎn)總能耗在各個(gè)簇周期差異很小,而在遠(yuǎn)離sink的外層網(wǎng)絡(luò),各個(gè)簇周期節(jié)點(diǎn)能耗差異較大.

圖 5 層間簇頭節(jié)點(diǎn)能耗標(biāo)準(zhǔn)差

圖 6 層內(nèi)簇頭節(jié)點(diǎn)能耗標(biāo)準(zhǔn)差

5.2數(shù)據(jù)引流性能下面在對(duì)數(shù)據(jù)引流對(duì)網(wǎng)絡(luò)性能的影響進(jìn)行分析.首先,比較在默認(rèn)網(wǎng)絡(luò)環(huán)境下有無數(shù)據(jù)引流時(shí)的網(wǎng)絡(luò)壽命.

表 4 數(shù)據(jù)引流對(duì)網(wǎng)絡(luò)壽命的影響

從表4可以看出,數(shù)據(jù)引流能有效提升網(wǎng)絡(luò)壽命,延緩節(jié)點(diǎn)死亡時(shí)間.由于數(shù)據(jù)引流能有效平衡簇頭節(jié)點(diǎn)間的能耗負(fù)載,并能讓具有更多剩余能量和更小數(shù)據(jù)傳輸距離的簇頭節(jié)點(diǎn)承擔(dān)更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),因而更有利于節(jié)省數(shù)據(jù)路由過程中的能耗開銷.因此,在層間路由未進(jìn)行負(fù)載引流時(shí),網(wǎng)絡(luò)壽命僅為211輪,而采用數(shù)據(jù)引流后,網(wǎng)絡(luò)壽命提升到376輪.

圖7給出了未采用數(shù)據(jù)引流時(shí),網(wǎng)絡(luò)各分層中的簇頭節(jié)點(diǎn)在一個(gè)簇周期的能耗.可以看出,在內(nèi)層網(wǎng)絡(luò)中由于不同的簇頭節(jié)點(diǎn)承擔(dān)了不均衡的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),因而各簇頭節(jié)點(diǎn)間的能耗差異極大.以L1層網(wǎng)絡(luò)為例,能耗最高的一個(gè)簇頭節(jié)點(diǎn)在一個(gè)簇周期消耗了24.215 mJ能量,這是能耗最低的簇頭節(jié)點(diǎn)的20.875倍.

圖 7 無數(shù)據(jù)引流時(shí)簇頭節(jié)點(diǎn)能耗

圖8顯示了采用數(shù)據(jù)引流后,網(wǎng)絡(luò)各層中的簇頭節(jié)點(diǎn)在一個(gè)簇周期的能耗.顯然可以從圖8看出,與圖7相比，L1層和L2層網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)的能耗得到了相當(dāng)大的平衡.這是因?yàn)橥ㄟ^引流,L1層和L2層網(wǎng)絡(luò)中的所有簇頭節(jié)點(diǎn)都承擔(dān)了數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù),因而有效均衡了所有簇頭節(jié)點(diǎn)的能耗負(fù)載,這也有助于避免某些簇頭節(jié)點(diǎn)因能耗過大提前死亡而造成的能量空洞現(xiàn)象.

圖 8 數(shù)據(jù)引流時(shí)簇頭節(jié)點(diǎn)能耗

5.34種算法對(duì)比通過實(shí)驗(yàn)比較本文提出的基于數(shù)據(jù)引流的非均勻分簇算法FRUC、LEACH算法、DEBUC算法及FBR算法在網(wǎng)絡(luò)壽命和網(wǎng)絡(luò)首節(jié)點(diǎn)死亡時(shí)節(jié)點(diǎn)能量剩余率方面的性能.

圖9給出了在默認(rèn)網(wǎng)絡(luò)環(huán)境下,4個(gè)算法所取得的網(wǎng)絡(luò)壽命.可以看出LEACH算法由于是簇間單跳路由,因此有著最低的網(wǎng)絡(luò)壽命.DEBUC算法作為一種典型的非均勻分簇算法,網(wǎng)絡(luò)壽命相對(duì)于LEACH算法得到了明顯提升.FBR算法由于引入了引流機(jī)制,網(wǎng)絡(luò)壽命高于LEACH和DEBUC,但是FBR由于讓固定的節(jié)點(diǎn)擔(dān)當(dāng)簇頭,同時(shí)網(wǎng)絡(luò)內(nèi)所有簇規(guī)模相等,因此靠近sink的簇頭節(jié)點(diǎn)的死亡時(shí)間會(huì)早于其他普通節(jié)點(diǎn),從而使網(wǎng)絡(luò)壽命低于本文提出的FRUC算法.

圖 9 網(wǎng)絡(luò)壽命對(duì)比

圖10比較了4個(gè)算法在默認(rèn)網(wǎng)絡(luò)參數(shù)下,首節(jié)點(diǎn)死亡時(shí)所有節(jié)點(diǎn)的平均剩余能量.可以看到,對(duì)于LEACH算法,在網(wǎng)絡(luò)壽命結(jié)束時(shí)所有節(jié)點(diǎn)平均剩余能量最高,達(dá)到了0.472 8 J,這也與文獻(xiàn)[5]的實(shí)驗(yàn)結(jié)論相符.DEBUC算法和FBR算法的節(jié)點(diǎn)平均剩余能量分別為0.341 1 J和0.247 8 J.本文提出的FRUC算法能最好地利用節(jié)點(diǎn)能量,非均勻分簇保證了網(wǎng)絡(luò)各層之間簇頭節(jié)點(diǎn)能耗均衡,數(shù)據(jù)引流又保證了網(wǎng)絡(luò)各層內(nèi)的簇頭節(jié)點(diǎn)能量均衡消耗,因此當(dāng)網(wǎng)絡(luò)中出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)時(shí),網(wǎng)絡(luò)所有節(jié)點(diǎn)平均剩余能量僅為0.193 8 J.

圖 10 節(jié)點(diǎn)平均剩余能量對(duì)比

進(jìn)一步,改變節(jié)點(diǎn)初始能量,對(duì)4個(gè)算法的網(wǎng)絡(luò)壽命進(jìn)行比較,圖11給出了實(shí)驗(yàn)結(jié)果.可以看到,隨著節(jié)點(diǎn)初始能量的增加,4個(gè)算法所取得的網(wǎng)絡(luò)壽命均得到了提升,其中FRUC、DEBUC、FRB等3個(gè)算法網(wǎng)絡(luò)壽命的提升明顯.而節(jié)點(diǎn)初始能量取值不同時(shí),FRUC算法均有著最高的網(wǎng)絡(luò)壽命.

圖 11 不同節(jié)點(diǎn)初始能量下的網(wǎng)絡(luò)壽命

圖12給出了改變網(wǎng)絡(luò)中的節(jié)點(diǎn)密度,4個(gè)算法所取得的網(wǎng)絡(luò)壽命.可以看到,隨著節(jié)點(diǎn)數(shù)目的增加,LEACH和DEBUC算法的網(wǎng)路壽命均下降明顯,這是因?yàn)楣?jié)點(diǎn)數(shù)目越多,網(wǎng)絡(luò)內(nèi)產(chǎn)生的監(jiān)控?cái)?shù)據(jù)也隨之增加,節(jié)點(diǎn)消耗了更多的能量進(jìn)行數(shù)據(jù)傳輸,從而降低了網(wǎng)絡(luò)壽命.FBR算法由于數(shù)據(jù)引流的作用,網(wǎng)絡(luò)壽命在節(jié)點(diǎn)數(shù)目增加到350個(gè)以后,才出現(xiàn)下降,且下降趨勢明顯緩于DEBUC算法.本文提出的FRUC算法在網(wǎng)絡(luò)節(jié)點(diǎn)密度較低節(jié)點(diǎn)數(shù)目僅為300個(gè)時(shí),網(wǎng)絡(luò)壽命略低于DEBUC和FBR算法.這是因?yàn)镕RUC算法對(duì)網(wǎng)絡(luò)進(jìn)行了分層,且越靠近sink的網(wǎng)絡(luò)分層規(guī)模越小,這樣在節(jié)點(diǎn)低密度狀態(tài)下,L1層網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)目很少,從而少量的節(jié)點(diǎn)承擔(dān)了簇頭節(jié)點(diǎn)的工作,影響了網(wǎng)絡(luò)壽命.而在其他節(jié)點(diǎn)密度下,FRUC算法均有著最高的網(wǎng)絡(luò)壽命，并且由于數(shù)據(jù)引流平衡了簇頭節(jié)點(diǎn)的能耗,因此在節(jié)點(diǎn)數(shù)目大于400個(gè)以后,網(wǎng)絡(luò)壽命才出現(xiàn)了下降.

圖 12 不同節(jié)點(diǎn)密度下的網(wǎng)絡(luò)壽命

6 結(jié)束語

本文對(duì)無線傳感器網(wǎng)絡(luò)的能量空洞問題進(jìn)行了研究,提出了一種基于數(shù)據(jù)引流的非均勻分簇能量空洞避免策略FRUC.與已有工作相比,FRUC的主要貢獻(xiàn)表現(xiàn)在以下2個(gè)方面：

1) 不同于傳統(tǒng)的非均勻分簇算法DEBUC與EEUC,FRUC不再通過計(jì)算不同節(jié)點(diǎn)的不同簇頭競爭半徑，從而實(shí)現(xiàn)非均勻分簇.FRUC在網(wǎng)絡(luò)初始階段對(duì)網(wǎng)絡(luò)進(jìn)行非均勻分層,并讓簇的范圍限制在層內(nèi),以實(shí)現(xiàn)非均勻分簇,從而保證了網(wǎng)絡(luò)各層之間簇頭節(jié)點(diǎn)的能耗均衡；

2) FRUC算法引入了數(shù)據(jù)引流,讓一個(gè)簇的數(shù)據(jù)發(fā)送給下一層時(shí),不再只發(fā)送給一個(gè)簇頭,而是將數(shù)據(jù)引流到多個(gè)簇頭,這樣平衡了網(wǎng)絡(luò)各層內(nèi)各個(gè)簇頭節(jié)點(diǎn)的能耗均衡.

仿真實(shí)驗(yàn)結(jié)果表明,FRUC算法能夠獲得比LEACH、DEBUC、FBR等主要數(shù)據(jù)傳輸算法更均衡的節(jié)點(diǎn)能耗負(fù)載、更長的網(wǎng)絡(luò)壽命,并能有效避免能量空洞現(xiàn)象的出現(xiàn).