付菁波
(1.西安電子科技大學(xué)研究生院,陜西西安 710071;2.楊凌職業(yè)技術(shù)學(xué)院文理學(xué)院,陜西楊凌 712100)
無線傳感器網(wǎng)絡(luò)綜合了傳感器、分布式信息處理、嵌入式和無線通信技術(shù),形成一種新的信息獲取和處理方式,實(shí)現(xiàn)了物理世界、計(jì)算機(jī)和人類社會(huì)的交互,是物聯(lián)網(wǎng)絡(luò)發(fā)展的基礎(chǔ)[1]。被廣泛應(yīng)用于國防軍事、環(huán)境監(jiān)測、農(nóng)業(yè)科技和醫(yī)療衛(wèi)生等領(lǐng)域。
無線傳感器網(wǎng)絡(luò)由部署在戶外無人看護(hù)的大量傳感器節(jié)點(diǎn)構(gòu)成。這些傳感器節(jié)點(diǎn)肩負(fù)著監(jiān)測和傳輸數(shù)據(jù)的任務(wù),而傳感器節(jié)點(diǎn)本身體積微小,由電池供電,所以能量成為網(wǎng)絡(luò)中珍貴的資源,也是網(wǎng)絡(luò)運(yùn)行中的關(guān)鍵問題。數(shù)據(jù)聚合技術(shù)是無線傳感器網(wǎng)絡(luò)中多個(gè)節(jié)點(diǎn)將數(shù)據(jù)包傳送到一個(gè)節(jié)點(diǎn)后對數(shù)據(jù)進(jìn)行聚合處理的數(shù)據(jù)傳輸方式。這樣可以有效消除網(wǎng)絡(luò)中的冗余數(shù)據(jù),減少數(shù)據(jù)的傳輸量,延長網(wǎng)絡(luò)壽命。因此將數(shù)據(jù)聚合技術(shù)引入到無線傳感器網(wǎng)絡(luò)中具有廣泛的應(yīng)用前景。
LEACH是較早提出的經(jīng)典分層路由協(xié)議,隨后研究者們提出的多種分層協(xié)議都是建立在LEACH協(xié)議的基礎(chǔ)上。該協(xié)議分為簇的建立階段和穩(wěn)定傳輸階段。在簇建立階段,簇首隨機(jī)產(chǎn)生,具體選擇方法是傳感器節(jié)點(diǎn)在0和1之間產(chǎn)生一個(gè)隨機(jī)數(shù),如果該值小于設(shè)定的閾值T,則該節(jié)點(diǎn)就宣布成為簇首。其中閾值T是沒有考慮其他因素隨機(jī)產(chǎn)生的,沒有優(yōu)化簇首的數(shù)量,并且當(dāng)網(wǎng)絡(luò)運(yùn)行一段時(shí)間后就會(huì)出現(xiàn)簇首分布不均、個(gè)別節(jié)點(diǎn)由于能耗過大而出現(xiàn)失效等現(xiàn)象。在穩(wěn)定傳輸階段,簇首收集簇成員數(shù)據(jù),聚合后直接將結(jié)果發(fā)送給sink。這里簇首與sink直接通信,對簇首的能量造成快速損耗,不利于網(wǎng)絡(luò)長時(shí)間運(yùn)行。
基于LEACH的不足,文中對簇首的選舉和簇間數(shù)據(jù)的轉(zhuǎn)發(fā)做了改進(jìn)。首先根據(jù)網(wǎng)絡(luò)的規(guī)模和節(jié)點(diǎn)個(gè)數(shù),預(yù)先設(shè)定最優(yōu)的簇首數(shù)目。為使簇首分布比較均勻,將剩余能量大于網(wǎng)絡(luò)節(jié)點(diǎn)平均能量的節(jié)點(diǎn)作為候選簇首,借鑒兩分法的思想,以兩個(gè)符合能量要求、距離最遠(yuǎn)的候選簇首節(jié)點(diǎn)為當(dāng)選簇首將網(wǎng)絡(luò)分成兩個(gè)簇,在簇內(nèi)再以兩個(gè)符合能量要求、距離最遠(yuǎn)的節(jié)點(diǎn)為簇首再分成兩個(gè)簇,依次類推進(jìn)行分簇。應(yīng)用兩分法時(shí),從距離sink近的簇分起,當(dāng)簇首數(shù)目等于預(yù)先設(shè)定的最優(yōu)簇個(gè)數(shù)時(shí)停止分簇。這樣不但能保證能量較充足的節(jié)點(diǎn)當(dāng)選簇首,而且可以較好地控制簇首分布,有利于能量均衡消耗,從而達(dá)到延長網(wǎng)絡(luò)壽命的目的。其次在大規(guī)模網(wǎng)絡(luò)中,簇首將數(shù)據(jù)通過其他簇首多跳轉(zhuǎn)發(fā)到sink,比直接發(fā)送到sink進(jìn)行遠(yuǎn)距離通信更節(jié)省能量。本文通過考慮到下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)的距離和能耗代價(jià)兩方面的因素給出了數(shù)據(jù)傳輸?shù)拇鷥r(jià)函數(shù),計(jì)算出傳輸代價(jià)最小的路徑。同時(shí)考慮到數(shù)據(jù)的相關(guān)性,給出了簇內(nèi)數(shù)據(jù)聚合策略,減少了網(wǎng)絡(luò)中的冗余信息,提高了網(wǎng)絡(luò)的壽命。仿真實(shí)驗(yàn)表明,在降低網(wǎng)絡(luò)能耗、延長網(wǎng)絡(luò)壽命等方面都有顯著提高。
針對大規(guī)模部署網(wǎng)絡(luò)考慮數(shù)據(jù)收集的過程,做以下假設(shè):(1)網(wǎng)絡(luò)是一個(gè)規(guī)模較大的平面網(wǎng)絡(luò),其中只有一個(gè)sink節(jié)點(diǎn),部署在網(wǎng)絡(luò)區(qū)域外一個(gè)確定位置。(2)傳感器節(jié)點(diǎn)是隨機(jī)部署的,所有節(jié)點(diǎn)和sink都處于靜止?fàn)顟B(tài),且都有唯一的ID。(3)傳感器節(jié)點(diǎn)的功能相同,但初始能量不全相同,稍有差別。(4)傳感器節(jié)點(diǎn)的發(fā)送和接收功率是可調(diào)整的。(5)可以通過定位算法或GPS等,已知每個(gè)節(jié)點(diǎn)的位置信息。
傳感器節(jié)點(diǎn)的能耗分別來自于節(jié)點(diǎn)之間的數(shù)據(jù)通信和節(jié)點(diǎn)自身的運(yùn)算存儲(chǔ)。節(jié)點(diǎn)自身的運(yùn)算存儲(chǔ)能耗相比節(jié)點(diǎn)之間的通信能耗小得多。研究表明,將1 bit數(shù)據(jù)傳輸100 m所需的能耗相當(dāng)于節(jié)點(diǎn)執(zhí)行3 000次運(yùn)算存儲(chǔ)命令[3]。因此研究中忽略了節(jié)點(diǎn)自身進(jìn)行的運(yùn)算存儲(chǔ)能耗。文中節(jié)點(diǎn)接收能耗ERx和發(fā)送能耗ETx,采用無線通信能耗自由空間模型和多路徑衰減模型[4],如下
其中,Eelec表示每比特?zé)o線收發(fā)電路損耗;k表示接收或發(fā)送數(shù)據(jù)的比特?cái)?shù);d表示通信距離;εfs表示收發(fā)電路的基本能耗系數(shù);εmp表示電路放大功率的能耗系數(shù);d0是根據(jù)網(wǎng)絡(luò)具體情況設(shè)定的。
路由中采用數(shù)據(jù)聚合策略,數(shù)據(jù)聚合的能量模型表示如下:設(shè)聚合節(jié)點(diǎn)接收了k個(gè)節(jié)點(diǎn)的數(shù)據(jù),每個(gè)節(jié)點(diǎn)發(fā)送lbit數(shù)據(jù),對1 bit的數(shù)據(jù)聚合的能耗為EDa,則對k個(gè)節(jié)點(diǎn)的數(shù)據(jù)做聚合的能耗為
以上涉及的參數(shù)參考值為Eelec=50 nJ/bit,εfs=10 pJ/bit·m2,εmp=0.001 3 pJ/bit·m4,EDa=5 nJ/bit·signal。
文獻(xiàn)[4~5]中,根據(jù)網(wǎng)絡(luò)規(guī)模和能量消耗分析可以得出最優(yōu)的分簇?cái)?shù)kopt,本文在已知kopt的基礎(chǔ)上給出改進(jìn)的簇建立算法:(1)輸入網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的剩余能量ei,預(yù)設(shè)最優(yōu)的分簇個(gè)數(shù)為kopt。(2)初始化。計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的平均剩余能量,記為e;簇首集合D,初始D=?;網(wǎng)絡(luò)當(dāng)前的簇首個(gè)數(shù)為N,初始N=1。(3)將剩余能量大于平均能量的節(jié)點(diǎn)作為候選簇首組成集合S={節(jié)點(diǎn)剩余能量ei>}。(4)在集合S中選出距離最遠(yuǎn)的節(jié)點(diǎn)ti,tj作為簇首,其他節(jié)點(diǎn)按就近原則加入簇,網(wǎng)絡(luò)被分為兩個(gè)簇S1和S2,D=D+ti+Tj且N=N+1。(5)根據(jù)節(jié)點(diǎn)的位置信息,計(jì)算簇首ti和tj到sink的平面距離d(ti),d(tj)。(6)若N<kopt,對距離sink近的簇優(yōu)先使用兩分法,返回步驟(4);若N=kopt分簇結(jié)束,算法執(zhí)行完畢。
各個(gè)簇不能同時(shí)使用兩分法分簇,否則簇的數(shù)目是以2n指數(shù)型增長,難以保證簇的數(shù)目剛好等于最優(yōu)簇的個(gè)數(shù)。為解決這個(gè)問題,本文提出離sink近的簇優(yōu)先使用兩分法,按照簇首到sink的距離由近及遠(yuǎn),逐個(gè)分。這樣可能還沒有等到所有的簇都被分一遍時(shí),已經(jīng)達(dá)到了最優(yōu)簇的個(gè)數(shù),分簇停止。此時(shí)離sink較近的簇比較小,而離sink遠(yuǎn)的簇比較大,這也正符合簇首的能量消耗需求,因?yàn)殡xsink近的簇首會(huì)較多地承擔(dān)中繼其他簇首數(shù)據(jù)的任務(wù)。
其中,v0表示簇首節(jié)點(diǎn);CHaggr(v0)表示簇首聚合后的數(shù)據(jù)包大小;v1,v2,…,vk表示簇內(nèi)成員節(jié)點(diǎn);data(vi)(i=0,1,2,…,k)表示各節(jié)點(diǎn)原始數(shù)據(jù)包的大小。
由式(4)可看出,兩個(gè)節(jié)點(diǎn)間的距離越大,感知到的數(shù)據(jù)相關(guān)度就越小,data(vi)·[1- ρ(vi,v0)](i=0,1,2,…,k)就盡可能多地保留了源數(shù)據(jù);相反,節(jié)點(diǎn)間距離越小,數(shù)據(jù)相關(guān)度越大,數(shù)據(jù)就相應(yīng)地被聚合壓縮。從而有效刪除了網(wǎng)絡(luò)中的冗余數(shù)據(jù),減小了數(shù)據(jù)的傳輸量,節(jié)約了網(wǎng)絡(luò)能耗。
LEACH協(xié)議在簇間收集數(shù)據(jù)時(shí),是由簇首直接將數(shù)據(jù)發(fā)送給基站,但當(dāng)簇首距離sink節(jié)點(diǎn)較遠(yuǎn)的情況下,用于數(shù)據(jù)發(fā)送的能耗過大,將很快耗盡簇首的能量而最終導(dǎo)致網(wǎng)絡(luò)癱瘓。尤其是針對大規(guī)模網(wǎng)絡(luò),簇間采用多跳轉(zhuǎn)發(fā)的模式是有效節(jié)能的手段之一。文中給出了一種基于能耗代價(jià)的數(shù)據(jù)收集策略,基本思想是當(dāng)一個(gè)簇首向另一個(gè)簇首轉(zhuǎn)發(fā)數(shù)據(jù)時(shí),考慮距離因素,計(jì)算簇首和自己相鄰幾個(gè)簇首的能耗代價(jià),從中選出能耗代價(jià)最小的簇首作為數(shù)據(jù)的下一跳轉(zhuǎn)發(fā)簇首。這個(gè)能耗代價(jià)考慮了通信距離和下一跳簇首的剩余能量兩方面因素,并有效防止了數(shù)據(jù)的回傳。
網(wǎng)絡(luò)分簇后,簇內(nèi)節(jié)點(diǎn)調(diào)整通信功率只與簇首通信即可。sink節(jié)點(diǎn)向簇首以洪泛的形式發(fā)出報(bào)文,此報(bào)文包含了sink節(jié)點(diǎn)的位置信息ID和跳數(shù)計(jì)數(shù)值hop,sink節(jié)點(diǎn)的跳數(shù)值初始化為hopv0=0。從節(jié)點(diǎn)vi處接收到此廣播的節(jié)點(diǎn)vj用自己的ID替換原報(bào)文中的ID,并更新跳數(shù)值hopvj=hopvi+1。當(dāng)某個(gè)簇首重復(fù)收到報(bào)文信息時(shí),則與自己的hopvj比較判斷跳數(shù)值:(1)若 hopvj=hopvi+1,則vj記錄發(fā)送節(jié)點(diǎn)vi的ID,保留跳數(shù)值不變。這些被記錄ID的節(jié)點(diǎn)vi跳數(shù)值比vj的小1,是vj的上一級節(jié)點(diǎn),可列為vj轉(zhuǎn)發(fā)對象。(2)若hopvj>hopvi+1,則重新記錄節(jié)點(diǎn)vi的ID,并更新vj的跳數(shù)值為hopvi+1。(3)若 hopvj<hopvi+1,且vj的跳數(shù)值比hopvi+1小1,則記錄發(fā)送節(jié)點(diǎn)vi的ID,保留跳數(shù)值不變,這些記錄下來的節(jié)點(diǎn)vi的跳數(shù)值與vj的跳數(shù)值相等,和是同一級的節(jié)點(diǎn)。若hopvj與hopvi+1之差>1,則不記錄發(fā)送節(jié)點(diǎn)的ID,保留跳數(shù)值不變,丟棄該報(bào)文。
上述的跳數(shù)值是數(shù)據(jù)發(fā)送到sink需要轉(zhuǎn)發(fā)的次數(shù),直接反應(yīng)了簇首和sink節(jié)點(diǎn)之間的距離。當(dāng)報(bào)文按照上述方法在簇首之間廣播完畢后,每個(gè)簇首節(jié)點(diǎn)記錄了自己的跳數(shù)值信息,同時(shí)記錄了上級簇首節(jié)點(diǎn)和同級簇首節(jié)點(diǎn)的ID信息。在下一步數(shù)據(jù)轉(zhuǎn)發(fā)過程中,每個(gè)簇首就只需計(jì)算與自己上級或同級簇首通信的能耗代價(jià)。
每個(gè)簇首計(jì)算剛記錄下來的相鄰簇首的能耗代價(jià),代價(jià)函數(shù)Costmn具體表示為
其中,d(m,n)表示簇首m與n的距離;Ere(n)表示下一跳簇首n的剩余能量;hopmax表示簇首的最大跳數(shù)值;hopn表示下一跳簇首n的跳數(shù)值;α,β,γ為權(quán)重因子,且 α+β+γ=1,γ>α,β。
由式(5)可看出,代價(jià)函數(shù)Costmn正比于簇首間的傳輸距離,兩簇首間的距離越小能耗就越小;反比于下一跳簇首的剩余能量,數(shù)據(jù)優(yōu)先向剩余能量多的簇首轉(zhuǎn)發(fā);正比于下一跳簇首的跳數(shù)值,且此項(xiàng)的調(diào)節(jié)因子γ大于其他兩項(xiàng)的調(diào)節(jié)因子,說明在轉(zhuǎn)發(fā)過程中要把數(shù)據(jù)發(fā)送到距離sink節(jié)點(diǎn)近的簇首,而不能回傳,耗費(fèi)網(wǎng)絡(luò)的能量。如圖1所示,B為sink節(jié)點(diǎn),A,C,D是簇首,雖然A到D的距離最短,但是D遠(yuǎn)離sink,從整體看A通過D到sink所消耗的能量比A通過C到sink所消耗的能量大,因此從節(jié)能的角度出發(fā),A的數(shù)據(jù)通過C發(fā)送到sink,避免數(shù)據(jù)的回傳現(xiàn)象。從代價(jià)函數(shù)中可以看到下一跳簇首的跳數(shù)值越小,說明該簇首離sink越近,能耗代價(jià)就越小。
圖1 簇間防止數(shù)據(jù)回傳轉(zhuǎn)發(fā)示意圖
實(shí)驗(yàn)環(huán)境是將100個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的方形平面區(qū)域中,sink的位置坐標(biāo)是(50,150),數(shù)據(jù)包大小為1 024 bit,節(jié)點(diǎn)的初始能量為2 J。接收和發(fā)送消耗能量的參考數(shù)據(jù)在前文能量模型中已給出。
在基于分簇的無線傳感器網(wǎng)絡(luò)路由算法中,簇內(nèi)節(jié)點(diǎn)都是通過單跳將數(shù)據(jù)發(fā)送到簇首,它們的能量消耗在各種算法中相差都不大,而簇首承擔(dān)著收集、聚合簇成員節(jié)點(diǎn)的數(shù)據(jù),并將聚合的結(jié)果發(fā)送到sink,是各種算法中能量消耗的主要部分。因此本文將LEACH和改進(jìn)算法中簇首在一輪中消耗的能量加以對比。如圖2所示。圖2中給出了連續(xù)10輪中簇首的能量消耗總和,可以看出本文改進(jìn)的算法簇首能耗大幅低于LEACH算法,主要原因在于LEACH算法中簇首通過單跳將數(shù)據(jù)直接發(fā)送到sink,遠(yuǎn)距離的通信大幅消耗了簇首的能量。而本文采用兩分法控制了簇首的分布,且簇首間利用代價(jià)函數(shù)計(jì)算出能耗較小的轉(zhuǎn)發(fā)路徑,將數(shù)據(jù)通過短距離多跳轉(zhuǎn)發(fā)方式發(fā)送到sink,從而降低了簇首的能量消耗。
圖2 簇首的能耗對比
首先,定義網(wǎng)絡(luò)的生存期為網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)能量耗盡的時(shí)間或輪數(shù)。從圖3中可以看出,LEACH算法的網(wǎng)絡(luò)生存期是350輪,改進(jìn)算法的網(wǎng)絡(luò)生存期是580輪。相比之下,改進(jìn)算法有效延長了網(wǎng)絡(luò)的生存期。分析其原因在于,LEACH算法中簇首是隨機(jī)選取的,沒有考慮當(dāng)選節(jié)點(diǎn)的剩余能量和簇首在網(wǎng)絡(luò)中的分布情況,能量消耗的不均勻不利于網(wǎng)絡(luò)長時(shí)間運(yùn)行。而改進(jìn)算法在考慮節(jié)點(diǎn)剩余能量的基礎(chǔ)上采用兩分法選舉簇首,不但保證了新簇首有充足的能量,而且控制了簇首的分布,使網(wǎng)絡(luò)能耗更加均衡,從而延長了網(wǎng)絡(luò)的生存期。
圖3 兩種算法的網(wǎng)絡(luò)生存期比較
圖4 權(quán)重因子調(diào)整對比圖
在能耗代價(jià)函數(shù)式(5)中 α,β,γ是3個(gè)權(quán)重因子,它們的值決定了代價(jià)函數(shù)在距離、剩余能量和跳數(shù)3方面的側(cè)重程度,從而影響著網(wǎng)絡(luò)的整體能耗。如圖4所示,曲線①中 α=0.5,β=0.5,γ=0;曲線②中α=0.2,β=0.2,γ=0.6;曲線③中 α =0.3,β=0.3,γ=0.4。圖4所示曲線①只考慮了到下一跳簇首的距離和剩余能量,沒有考慮下一跳簇首到sink的跳數(shù),當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)僅根據(jù)這兩方面的局部信息作出判斷容易發(fā)生數(shù)據(jù)回傳現(xiàn)象,從而耗費(fèi)能量。曲線②、③中考慮了跳數(shù)因素,防止了數(shù)據(jù)回傳,能耗有所減少,但是曲線②對距離和剩余能量因素側(cè)重較少,使得有些簇首為了把數(shù)據(jù)發(fā)送到跳數(shù)小的下一跳簇首,而將數(shù)據(jù)發(fā)送到剩余能量少、距離遠(yuǎn)的簇首,導(dǎo)致能量的消耗和不均勻分布。相比較,曲線③在有效防止數(shù)據(jù)回傳的基礎(chǔ)上,綜合考慮了下一跳簇首的距離和剩余能量兩方面因素,使得網(wǎng)絡(luò)整體能耗偏低。說明α,β,γ 3個(gè)因子的取值要比較均衡,其中γ的值稍大,這樣能兼顧多方面因素,使能量消耗分布相對均衡,有利于延長網(wǎng)絡(luò)的生命期。
由于基于分簇的路由算法具有較好的可擴(kuò)展性、便于管理等特點(diǎn)在無線傳感器網(wǎng)絡(luò)的路由算法中被廣泛應(yīng)用。這類算法中簇首的能耗較大,容易產(chǎn)生能量消耗的熱點(diǎn)現(xiàn)象,是問題解決的關(guān)鍵。本文在LEACH算法的基礎(chǔ)上對簇首的選舉、簇首的分布控制和簇首間的數(shù)據(jù)轉(zhuǎn)發(fā)做了改進(jìn),并結(jié)合數(shù)據(jù)聚合機(jī)制進(jìn)一步節(jié)約網(wǎng)絡(luò)的能耗。仿真結(jié)果表明,算法有效地均衡了網(wǎng)絡(luò)的能耗,延長網(wǎng)絡(luò)的生存期。
[1]孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.
[2]JUNG W S,LIM K W,YOUNG B K,et al.Efficient clustering-based aggregation techniques for wireless sensor networks[J].Springer Science+Business Media,LLC Wireless Netwoerk,2011(17):1387-1400.
[3]BARR K C,ASANVIC K.Energy aware lossless data compression[J].ACM Transactions on Computer Systems,2006(8):1121-1126.
[4]張小慶.無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究與仿真[D].武漢:武漢理工大學(xué),2009.
[5]彭愛平,郭曉松,蔡偉,等.基于估計(jì)機(jī)制的分簇傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法[J].傳感技術(shù)學(xué)報(bào),2011,1(24):128-133.
[6]沈波,張世永,鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報(bào),2006,7(17):1588-1600.
[7]余勇昌,韋崗.無線傳感器網(wǎng)絡(luò)中能耗均衡的數(shù)據(jù)收集算法[J].通信技術(shù),2008(2):93-96.
[8]唐偉,郭偉.無線傳感器網(wǎng)絡(luò)中的最大生命基因路由算法[J].軟件學(xué)報(bào),2010,7(21):1646-1656.
[9]RICKENBACH P,WATTENHOFER R.Gathering correlated data in sensor networks[C].Philadelphia:Proceeding of the Joint Workshop on Foundations of Mobile Computing,ACM Sigmobile,2004:60-66.