基于蜂窩虛擬網(wǎng)格的WSN混合多跳分簇路由算法*

余修武,胡沐芳,劉 琴,3,劉 永

(1.南華大學(xué)環(huán)境與安全工程學(xué)院,湖南 衡陽 421001;2.湖南省鈾尾礦庫(kù)退役治理技術(shù)工程技術(shù)研究中心,湖南 衡陽 421001;3.金屬礦山安全與健康國(guó)家重點(diǎn)實(shí)驗(yàn)室,安徽 馬鞍山 243000)

無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)應(yīng)用廣泛,能應(yīng)用于海洋環(huán)境監(jiān)測(cè)、礦山監(jiān)測(cè)、醫(yī)療衛(wèi)生監(jiān)測(cè)等領(lǐng)域。而在無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)是靠蓄電池進(jìn)行供電的,所以整個(gè)網(wǎng)絡(luò)使用壽命是有限的[1-2]。在WSNs關(guān)鍵技術(shù)中,路由技術(shù)占有重要地位,在該項(xiàng)技術(shù)中節(jié)點(diǎn)的能量多在數(shù)據(jù)傳輸過程中損耗且節(jié)點(diǎn)能耗不均勻[3-4]。因此,降低并均衡網(wǎng)絡(luò)能耗是在進(jìn)行路由設(shè)計(jì)時(shí)考慮的首要問題。基于地理位置的分簇路路由算法相對(duì)于其他平面路由來說,具有很強(qiáng)的擴(kuò)展性和高效的數(shù)據(jù)融合性,能降低通信能耗[5]。而蜂窩式虛擬劃分方案較其他多邊形的虛擬單元格在網(wǎng)絡(luò)覆蓋性方面占有很大的優(yōu)勢(shì),有利于節(jié)點(diǎn)調(diào)整信號(hào)發(fā)射功率[6-7]。大量學(xué)者以網(wǎng)格模型和分簇路由為基礎(chǔ)提出了許多WSN路由協(xié)議。崔燦等人[8]利用混合壓縮感知理論優(yōu)化正六邊形混合路由協(xié)議。同時(shí)利用數(shù)據(jù)傳輸次數(shù)和壓縮比例以及分簇的大小,確定最優(yōu)成簇?cái)?shù)量,從而提高網(wǎng)絡(luò)利用效率。劉壯等人[9]提出一種可調(diào)節(jié)網(wǎng)格改進(jìn)的跨區(qū)域邊界無狀態(tài)貪婪路由協(xié)議。解決邊界區(qū)域能量不均衡問題,但是該算法在簇頭節(jié)點(diǎn)選舉時(shí)并沒有給出明確的選舉機(jī)制,也沒考慮簇頭節(jié)點(diǎn)能耗問題。文獻(xiàn)[10]提出一種區(qū)域劃分的多跳分簇路由算法,將監(jiān)測(cè)區(qū)域劃分為等間距的圓環(huán)然后等夾角的二次劃分區(qū)域。這種非均勻分區(qū)方式可以均衡網(wǎng)絡(luò)能耗,延長(zhǎng)網(wǎng)絡(luò)生命周期。文獻(xiàn)[11]提出的改進(jìn)型分簇路由算法,考慮節(jié)點(diǎn)剩余能量以及與基站的距離因素優(yōu)化簇頭選擇機(jī)制。引入超級(jí)簇頭作為普通簇頭與基站的通信中繼,這在一定程度上緩解了能量均衡的問題,但未考慮到簇內(nèi)節(jié)點(diǎn)的非均勻分布及由此帶來的能耗不均衡問題。文獻(xiàn)[12]提出EB-GAF算法,該算法引入均勻度模型,通過二次劃分使得單元內(nèi)節(jié)點(diǎn)分布均勻。同時(shí)在選舉簇頭節(jié)點(diǎn)時(shí)考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)位置,利于選舉出最優(yōu)簇首節(jié)點(diǎn),提高網(wǎng)絡(luò)有效性。文獻(xiàn)[13]提出了一種虛擬網(wǎng)格分簇路由算法(CRVB)。首先通過計(jì)算得出最優(yōu)格距,然后節(jié)點(diǎn)自組織成簇,簇內(nèi)節(jié)點(diǎn)構(gòu)建近優(yōu)生成路由樹,簇首節(jié)點(diǎn)采用多跳與基站通信。仿真實(shí)驗(yàn)表明,CRVB算法能減少通信時(shí)延減少網(wǎng)絡(luò)能耗。但由于CRVB算法采用正方形劃分網(wǎng)格,導(dǎo)致簇間通信能耗較大,存在一定的弊端。

本文提出了一種基于蜂窩虛擬網(wǎng)格式混合多跳分簇的路由算法IHCRA(Improved Hexagon Cluster Routing Algorithm)。即把監(jiān)測(cè)目標(biāo)區(qū)域劃分成若干個(gè)正六邊形虛擬單元格。這些區(qū)域中的節(jié)點(diǎn)自組成簇,在簇頭選舉時(shí)綜合考慮簇頭剩余能量以及簇頭位置與單元格網(wǎng)絡(luò)撲拓區(qū)域質(zhì)心的角度比和距離比,以此來均衡簇頭節(jié)點(diǎn)的能量消耗和抑制孤立點(diǎn)的產(chǎn)生。在簇內(nèi)通信時(shí)采用混合跳模式,在保證通信質(zhì)量的情況下,提高網(wǎng)絡(luò)的生命周期。

1 系統(tǒng)模型

傳統(tǒng)GAF路由算法是將監(jiān)測(cè)區(qū)域劃分為多個(gè)正方形,如圖1(a)所示。根據(jù)分析該結(jié)構(gòu)只與4個(gè)虛擬格有公共邊,而在正六邊形虛擬網(wǎng)格中,每個(gè)單元格都與附近6個(gè)單元格相鄰。并且正六邊形虛擬網(wǎng)格中心節(jié)點(diǎn)到相鄰格的距離都相等,說明與圖1(a)模型相比圖1(b)模型具有更好的網(wǎng)絡(luò)覆蓋性。根據(jù)相關(guān)資料分析,相比正方形的虛擬單元格,正六邊形虛擬網(wǎng)格還在單跳覆蓋面積和單元格內(nèi)節(jié)點(diǎn)總數(shù)方面占有優(yōu)勢(shì)。

圖1 虛擬網(wǎng)格模型結(jié)構(gòu)

所以在IHCRA算法中,將監(jiān)測(cè)區(qū)域劃分為多個(gè)正六邊形,節(jié)點(diǎn)隨機(jī)布置在監(jiān)測(cè)區(qū)域內(nèi)。劃分后的區(qū)域都將產(chǎn)生一個(gè)G-ID(Grid-ID),節(jié)點(diǎn)利用自身定位坐標(biāo)得出所屬的G-ID。WSNs中六邊形網(wǎng)格通信模型如圖2所示,設(shè)每個(gè)六邊形的邊長(zhǎng)為R。現(xiàn)假設(shè)監(jiān)測(cè)區(qū)域內(nèi)節(jié)點(diǎn)具有如下性質(zhì):①普通節(jié)點(diǎn)和Sink節(jié)點(diǎn)一旦布置就固定,具有唯一的N-ID(node-ID)且隨機(jī)布置在監(jiān)測(cè)區(qū)域內(nèi)。②對(duì)于所有的普通節(jié)點(diǎn)能量有限、相同,而Sink節(jié)點(diǎn)和基站能量不受限。③所有節(jié)點(diǎn)能夠存儲(chǔ)數(shù)據(jù),具有相同的計(jì)算、轉(zhuǎn)發(fā)功能且各節(jié)點(diǎn)地位相同都能參與簇頭競(jìng)爭(zhēng)。④區(qū)域內(nèi)節(jié)點(diǎn)通過定位算法已知自身位置,并能計(jì)算之間距離。⑤區(qū)域內(nèi)節(jié)點(diǎn)能夠周期性的采集數(shù)據(jù),并能保證數(shù)據(jù)成功發(fā)送至基站。

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

2 IHCRA路由算法

2.1 虛擬分區(qū)

通過幾何約束計(jì)算易判斷出平面區(qū)域內(nèi)節(jié)點(diǎn)所屬單元格。例如,判斷某個(gè)節(jié)點(diǎn)(xi,yi)是否在該正六邊形內(nèi)。首先將正六邊形劃分為如圖3所示的三段圖形。

在該正六邊形網(wǎng)格區(qū)域內(nèi),設(shè)6個(gè)頂點(diǎn)的坐標(biāo)依次為(a,b)、(c,b)、(d,e)、(c,f)、(a,f)、(g,e)。由于區(qū)域劃分是正規(guī)圖形,則易得出上述頂點(diǎn)的坐標(biāo)。同時(shí),由節(jié)點(diǎn)定位算法易得出普通節(jié)點(diǎn)坐標(biāo)位置為(xi,yi),那么判斷節(jié)點(diǎn)的G-ID就變成對(duì)比三段分段函數(shù)值的大小。區(qū)域內(nèi)所有節(jié)點(diǎn)通過計(jì)算依次判斷出所屬單元格。單元格內(nèi)節(jié)點(diǎn)自組成簇,減少了成簇復(fù)雜度,降低能耗。

圖3 節(jié)點(diǎn)區(qū)域分區(qū)

2.2 簇頭選舉算法

傳感器節(jié)點(diǎn)向各鄰居節(jié)點(diǎn)發(fā)送報(bào)文消息,交換各自的N-ID、G-ID和所處狀態(tài)。節(jié)點(diǎn)相同的G-ID就將其N-ID記錄在節(jié)點(diǎn)列表中,若不相同,就將消息丟棄。區(qū)域內(nèi)各節(jié)點(diǎn)設(shè)置定時(shí)器,長(zhǎng)度設(shè)置為TD。在定時(shí)器TD內(nèi),如果節(jié)點(diǎn)接收到其他節(jié)點(diǎn)競(jìng)選簇頭成功的消息,則說明該節(jié)點(diǎn)競(jìng)選簇頭節(jié)點(diǎn)失敗,將自動(dòng)進(jìn)入休眠狀態(tài)。在休眠期間只將自身的狀態(tài)和監(jiān)測(cè)數(shù)據(jù)上傳給簇頭節(jié)點(diǎn)。如果該節(jié)點(diǎn)未收到區(qū)域內(nèi)節(jié)點(diǎn)發(fā)送簇頭選舉成功消息,則該單元內(nèi)簇頭節(jié)點(diǎn)就為此節(jié)點(diǎn),并自動(dòng)開啟活動(dòng)狀態(tài),收集消息。同時(shí)給休眠狀態(tài)的節(jié)點(diǎn)設(shè)置長(zhǎng)度為TS的定時(shí)器,當(dāng)超過TS時(shí)間長(zhǎng)度,則睡眠狀態(tài)節(jié)點(diǎn)轉(zhuǎn)為活動(dòng)狀態(tài),反之則處于睡眠狀態(tài)并關(guān)閉收發(fā)器。設(shè)置簇頭節(jié)點(diǎn)定時(shí)器,時(shí)間長(zhǎng)度設(shè)為TC,當(dāng)簇頭節(jié)點(diǎn)超過TC時(shí),該簇頭節(jié)點(diǎn)開始收集本單元內(nèi)所有族成員節(jié)點(diǎn)的數(shù)據(jù)包。該數(shù)據(jù)包包括各節(jié)點(diǎn)N-ID、節(jié)點(diǎn)所屬的G-ID、節(jié)點(diǎn)剩余能量Er、正六邊形質(zhì)心與節(jié)點(diǎn)的距離DI等。通過這一系列的參考數(shù)值,選出理想簇頭。

首輪簇頭節(jié)點(diǎn)由最靠近正六邊形質(zhì)心的節(jié)點(diǎn)擔(dān)任。當(dāng)該節(jié)點(diǎn)發(fā)現(xiàn)自身能量少于競(jìng)選時(shí)節(jié)點(diǎn)平均能量的70%時(shí),則進(jìn)行下一輪簇頭節(jié)點(diǎn)競(jìng)選。首先節(jié)點(diǎn)采用式(1)計(jì)算出節(jié)點(diǎn)競(jìng)選簇頭的概率。

(1)

式中,i∈(1,n),Er為節(jié)點(diǎn)i剩余能量,Ea為簇內(nèi)節(jié)點(diǎn)剩余能量的平均值;a∈[0,1]為距離和剩余能量的權(quán)值;di為節(jié)點(diǎn)到正六邊形中心坐標(biāo)的距離;δij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。Pi概率越大成為簇頭節(jié)點(diǎn)的機(jī)會(huì)就越大。

計(jì)算出簇頭競(jìng)選概率后,另引入角度比作為理想簇頭節(jié)點(diǎn)的參考值。如式(2)、(3)、(4)所示。

χ=(分簇輪數(shù))mod(60),χ∈[0,60]

(2)

(3)

(4)

式中,χ為偏離角度,α為角度,η為角度比;(x1,y1)、(x2,y2)為兩節(jié)點(diǎn)坐標(biāo)。η越小說明與理想簇頭的接近度越高,偏度角利于動(dòng)態(tài)選舉簇頭節(jié)點(diǎn)。當(dāng)首輪簇頭節(jié)點(diǎn)剩余能量低于節(jié)點(diǎn)平均能量的70%時(shí),啟動(dòng)簇頭選舉機(jī)制。在選舉時(shí)先考慮參數(shù)Pi,挑選出Pi值為前三名的節(jié)點(diǎn),然后計(jì)算出各自的角度比。同時(shí),采用式(5)計(jì)算出每個(gè)節(jié)點(diǎn)在理想情況下的吞吐率。

(5)

式中,S表示監(jiān)測(cè)區(qū)域面積;δ表示節(jié)點(diǎn)最高傳輸速率;l表示節(jié)點(diǎn)到基站距離;Δ任意大于0的常數(shù);n表示節(jié)點(diǎn)個(gè)數(shù);R表示節(jié)點(diǎn)傳輸半徑。

最終引入簇頭選擇函數(shù)如下式(6)。

f=aλ-bη+cp

(6)

式中,a、b、c為大于0的影響因子且a+b+c=1。

各競(jìng)選節(jié)點(diǎn)計(jì)算出函數(shù)值后,比較函數(shù)值大小,最大者當(dāng)選為簇頭節(jié)點(diǎn)。競(jìng)選失敗的節(jié)點(diǎn)自動(dòng)進(jìn)入休眠狀態(tài),當(dāng)超過時(shí)間長(zhǎng)度TS時(shí),休眠狀態(tài)轉(zhuǎn)為發(fā)現(xiàn)狀態(tài)準(zhǔn)備參與下一輪簇頭選舉。選舉成功的簇頭節(jié)點(diǎn)進(jìn)入活動(dòng)狀態(tài),收集數(shù)據(jù)并進(jìn)行數(shù)據(jù)融合發(fā)送給Sink節(jié)點(diǎn)。當(dāng)簇頭節(jié)點(diǎn)經(jīng)過時(shí)間長(zhǎng)度TC時(shí),則進(jìn)行下一輪的簇頭選舉。

2.3 數(shù)據(jù)傳輸階段

在IHCRA算法中,數(shù)據(jù)傳輸采用簇內(nèi)單跳和簇間混合多跳的方式。在蜂窩網(wǎng)格簇內(nèi)節(jié)點(diǎn)通信時(shí),源節(jié)點(diǎn)將采集到的數(shù)據(jù)直接發(fā)送給簇頭節(jié)點(diǎn);簇間通信時(shí)采用多跳機(jī)制,尋找一條能耗最優(yōu)的路徑進(jìn)行數(shù)據(jù)傳播。簇首節(jié)點(diǎn)首先接受從Sink節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)并收集信息。同時(shí),記錄簇首節(jié)點(diǎn)與Sink節(jié)點(diǎn)的最短跳數(shù),將范圍內(nèi)的鄰居節(jié)點(diǎn)的N-ID、G-ID、剩余能量、簇內(nèi)成員節(jié)點(diǎn)數(shù)、與簇首的距離dij記錄下來。建立指向Sink節(jié)點(diǎn)的反向路由梯度。在選擇下一跳簇首節(jié)點(diǎn)時(shí),利用式(7)計(jì)算代價(jià)函數(shù),選擇下一跳值簇首節(jié)點(diǎn)具有最小的代價(jià)函數(shù),代價(jià)函數(shù)如式(7):

(7)

式中,dij代表節(jié)點(diǎn)i到j(luò)的距離,di,Sink表示節(jié)點(diǎn)i到Sink節(jié)點(diǎn)的距離,dj,Sink表示節(jié)點(diǎn)j到Sink節(jié)點(diǎn)的距離。如果簇首節(jié)點(diǎn)下一跳為本節(jié)點(diǎn)自身,則直接一跳將數(shù)據(jù)傳輸給Sink節(jié)點(diǎn),反之,則尋找下一跳節(jié)點(diǎn)簇首節(jié)點(diǎn)。直至所有節(jié)點(diǎn)都尋找到下一跳簇首節(jié)點(diǎn)為止,則表明簇間路由已建立。

3 仿真結(jié)果與分析

本文以MATLAB為仿真平臺(tái),將IHCRA路由算法與LEACH算法[14]和GAF算法[15]和CRVB算法進(jìn)行仿真,四者之間進(jìn)行了性能的比較。分別分析比較了網(wǎng)絡(luò)總能量消耗和網(wǎng)絡(luò)剩余總節(jié)點(diǎn)數(shù)。仿真場(chǎng)景中詳細(xì)的參數(shù)設(shè)置見表1。

表1 仿真參數(shù)設(shè)置

采用自由空間無線通信模型。已知傳感器節(jié)點(diǎn)耗能部分分別是傳感器模塊、處理器模塊和通信模塊,其中耗能最大的是無線通信模塊。該模型中,Erx和Etx分別表示節(jié)點(diǎn)發(fā)送abit數(shù)據(jù)至距離d處的發(fā)射耗能和接受數(shù)據(jù)能耗,計(jì)算公式如下:

Erx(a)=Erx-elec(a)=aEelec

(8)

Etx(a,d) =Etx-elec(a)+Etx-amp(a,d)

(9)

式中,Eelec為傳感器收發(fā)單位數(shù)據(jù)(bit)的電路耗能;εfs、εmp為自由空間和多徑衰弱時(shí)的衰減系數(shù),d0=(εfs/εmp)1/2為距離閾值。

網(wǎng)絡(luò)能耗是指網(wǎng)絡(luò)在運(yùn)行過程中消耗的總能量。網(wǎng)絡(luò)能耗越小,說明算法在綜合情況下(如網(wǎng)絡(luò)沖突,信道競(jìng)爭(zhēng),控制開銷等)的能量消耗越小,能量有效性越高。從圖4可知,在運(yùn)行時(shí)間超過200 s時(shí),算法的網(wǎng)絡(luò)總能量呈現(xiàn)快速下降趨勢(shì),說明能量消耗不斷增加。LEACH算法在網(wǎng)絡(luò)運(yùn)行至800 s左右時(shí)網(wǎng)絡(luò)總能量耗盡,而此時(shí)GAF算法剩余能量占總能量的40%,CRVB算法占50%,IHCRA算法占57%。說明IHCRA算法較前3種算法能減少網(wǎng)絡(luò)能耗。當(dāng)運(yùn)行時(shí)間達(dá)到1 200 s后,IHCRA算法較前3種算法在減少網(wǎng)絡(luò)能耗上占有明顯優(yōu)勢(shì),對(duì)比CRVB算法也占有相對(duì)優(yōu)勢(shì)。這是由于IHCRA算法利用蜂窩網(wǎng)格分簇,在簇首選舉時(shí)綜合考慮了節(jié)點(diǎn)能量、距離和偏度角。同時(shí)在傳輸數(shù)據(jù)時(shí)采用混合多跳機(jī)制,平衡了節(jié)點(diǎn)總能耗,提高了能量有效性。

圖4 網(wǎng)絡(luò)總能量隨時(shí)間變化圖

圖5 節(jié)點(diǎn)存活個(gè)數(shù)變化圖

無線傳感器網(wǎng)絡(luò)中,網(wǎng)絡(luò)的生存時(shí)間通常用剩余節(jié)點(diǎn)存活數(shù)來衡量。在整個(gè)WSN中,隨著運(yùn)行時(shí)間的增加,剩余存活節(jié)點(diǎn)的數(shù)量就會(huì)減少,在某個(gè)時(shí)段內(nèi),剩余存活節(jié)點(diǎn)比例越高代表該算法的網(wǎng)絡(luò)生存時(shí)間越長(zhǎng)。從圖5可以看出LEACH節(jié)點(diǎn)開始出現(xiàn)節(jié)點(diǎn)死亡時(shí)間最早,GAF次之,CRVB算法和IHCRA較晚。IHCRA和CRVB在節(jié)點(diǎn)出現(xiàn)失效后,其余節(jié)點(diǎn)的失效速度相對(duì)于LEACH和GAF較快,說明IHCRA和CRVB算法的網(wǎng)絡(luò)節(jié)點(diǎn)能耗較為均衡。但由于IHCRA算法采用蜂窩網(wǎng)格分簇相對(duì)CRVB正方形來說有更好的網(wǎng)絡(luò)覆蓋性和較少的節(jié)點(diǎn)通信能耗,所以IHCRA算法節(jié)點(diǎn)存活個(gè)數(shù)較多。圖5中IHCRA算法與其他3種算法節(jié)點(diǎn)存活個(gè)數(shù)的比較可以看出,LEACH算法在400 s左右第1次出現(xiàn)了死亡節(jié)點(diǎn),GAF算法和CRVB算法在700 s左右就出現(xiàn)了死亡節(jié)點(diǎn),而IHCRA算法在900 s左右。說明IHCRA算法相比較于LEACH、GAF和CRVB算法能延長(zhǎng)節(jié)點(diǎn)死亡時(shí)間,這是由于IHCRA算法在蜂窩結(jié)構(gòu)的基礎(chǔ)上進(jìn)行了虛擬單元格劃分方法,并描述了一種有效的簇間混合跳的數(shù)據(jù)傳輸策略,有效地實(shí)現(xiàn)了全網(wǎng)的負(fù)載均衡。

4 結(jié)束語

本文提出了一種蜂窩虛擬網(wǎng)格劃分混合多跳路由算法。該算法采用蜂窩網(wǎng)格式的虛擬分區(qū)的方法,讓節(jié)點(diǎn)自組成簇。同時(shí)在簇頭選舉時(shí),引入新的簇首選舉概率公式并加入偏度角等參數(shù),使簇首節(jié)點(diǎn)選舉更合理。在數(shù)據(jù)傳輸時(shí)采用混合多跳的方式,均衡了節(jié)點(diǎn)能耗。仿真實(shí)驗(yàn)表明IHCRA與LEACH、GAF和CRVB算法比較,網(wǎng)絡(luò)總能耗較低,能提高網(wǎng)絡(luò)能量有效性。在剩余節(jié)點(diǎn)個(gè)數(shù)上,IHCRA算法有效的延長(zhǎng)了網(wǎng)絡(luò)的生存周期。