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

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

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

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

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

1 系統模型

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

圖1 虛擬網格模型結構

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

圖2 傳感網絡模型

2 IHCRA路由算法

2.1 虛擬分區(qū)

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

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

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

2.2 簇頭選舉算法

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

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

(1)

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

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

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

(2)

(3)

(4)

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

(5)

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

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

f=aλ-bη+cp

(6)

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

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

2.3 數據傳輸階段

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

(7)

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

3 仿真結果與分析

本文以MATLAB為仿真平臺,將IHCRA路由算法與LEACH算法[14]和GAF算法[15]和CRVB算法進行仿真,四者之間進行了性能的比較。分別分析比較了網絡總能量消耗和網絡剩余總節(jié)點數。仿真場景中詳細的參數設置見表1。

表1 仿真參數設置

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

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

(8)

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

(9)

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

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

圖4 網絡總能量隨時間變化圖

圖5 節(jié)點存活個數變化圖

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

4 結束語

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