無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中地理能量感知路由的改進(jìn)

摘要：無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的首要設計目標是能量的高效利用，所以設計其路由協(xié)議需要重點(diǎn)考慮能耗問(wèn)題。針對WSN的GEAR路由協(xié)議，提出一種能耗上的改進(jìn)方案并進(jìn)行仿真，仿真結果顯示，該方案能明顯降低能耗。

關(guān)鍵詞：無(wú)線(xiàn)傳感器網(wǎng)絡(luò )； 路由； 地理能量感知路由； 節能路由

引言

　　無(wú)線(xiàn)傳感器網(wǎng)絡(luò )是由部署在監測區域內的大量廉價(jià)的微型傳感器節點(diǎn)，通過(guò)無(wú)線(xiàn)通信的方式形成的一個(gè)多跳自組織網(wǎng)絡(luò )系統，其目的是協(xié)作地感知、采集和處理覆蓋區域內的事件信息，并發(fā)送給觀(guān)察者。由于節點(diǎn)能量有限且補充困難，無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的首要設計目標是能量[6]的高效利用。本文在原有GEAR[1]路由協(xié)議基礎上提出改進(jìn)方法，從而在路由協(xié)議[4]上節省無(wú)線(xiàn)傳感器節點(diǎn)有限的能量，并提高整個(gè)網(wǎng)絡(luò )的生存周期。

GEAR協(xié)議介紹和改進(jìn)

　　GEAR[5](Geographical and Energy Aware Routing)路由協(xié)議是根據事件區域的地理位置信息，建立匯聚節點(diǎn)到事件區域的優(yōu)化路徑，避免了泛洪查詢(xún)消息，從而減少了建立路由的開(kāi)銷(xiāo)。但是傳統的GEAR路由機制由于缺乏足夠的拓撲信息，路由過(guò)程中會(huì )遇到路由空洞[2]的現象。

　　本文提出了考慮兩跳節點(diǎn)信息的路由機制，大大減少了路由空洞出現的概率，降低了每次成功查詢(xún)的平均能耗；根據無(wú)線(xiàn)發(fā)射功率和通信半徑的關(guān)系，由通信距離確定發(fā)射功率[3]，并在路由選擇時(shí)考慮發(fā)射功率，提出了更加節省能量的GPEAR路由機制。

GEAHAR路由機制

　　過(guò)多的路由空洞會(huì )消耗很多不必要的能量，降低整個(gè)網(wǎng)絡(luò )的通信效率。為了減少或避免路由空洞，節點(diǎn)需要知道更多的拓撲信息，這就是GEAHAR（Geographical energy aware and hole avoid routing）機制提出的依據?；舅枷胧窃诓樵?xún)消息時(shí)，節點(diǎn)選擇下一跳節點(diǎn)不僅僅考慮鄰居一跳節點(diǎn)的代價(jià)值最小，而是考慮兩跳的信息。

　　鄰居節點(diǎn)是指節點(diǎn)一跳通信范圍內可以到達的所有節點(diǎn)的集合。如（1）式定義，dmax為節點(diǎn)最大通信距離，為所有節點(diǎn)的集合。

NbNi={Nj|d(Nj,Ni)}
≤dmax,Nj∈N}（1）

　　節點(diǎn)Ni選擇下一跳Nnext(i)的依據如（2）式。Nbi為節點(diǎn)Ni的鄰居節點(diǎn)集合，NbNbi(j)為節點(diǎn)Ni的鄰居節點(diǎn)Nbi(j)的鄰居節點(diǎn)集合。β為比例系數，取值范圍為0~1。β取值為1，算法退化為一跳的GEAR路由機制。式中需要注意的是NbNbi(j)(k)≠Ni，即第二跳節點(diǎn)不能選擇當前節點(diǎn)，否則將出現返回路由的現象，這將大量消耗不必要的能量。

Nnext(i)=min(βc(Nbi(j),T)+(1-β)min(c(NBNbj(j)(k),T)))Nbi(j)∈Nbi,NbNbi(j)(K)∈NbNbi(j),NbNb(j)(k)≠Ni（2）

GPEAR路由機制

　　在接收靈敏度一定的情況下，無(wú)線(xiàn)發(fā)射功率P和接收半徑R之間關(guān)系是P正比于R2~R5，也就是P可能會(huì )遠遠大于R2。如果在節點(diǎn)間通信時(shí)考慮通信的距離，適當調整發(fā)射功率，而不是使用相同的發(fā)射功率（這樣的話(huà)只能以最大通信距離來(lái)發(fā)射），則可以大大降低通信的能耗，延長(cháng)整個(gè)網(wǎng)絡(luò )的壽命，降低每個(gè)數據包的通信代價(jià)。

　　GPEAR（Geographical and physical energy aware routing）路由機制是在傳統GEAR路由機制作下一跳路由選擇時(shí)，考慮物理層發(fā)射功率與通信半徑的關(guān)系，從而做出更加適合的選擇。

　　假設無(wú)線(xiàn)通信部分能量消耗與通信距離的四次方成正比，并將發(fā)射功率分為5檔，見(jiàn)表1。

表1 發(fā)射功率與通信半徑的關(guān)系


GPEAR路由機制則是選擇鄰居節點(diǎn)中代價(jià)值和發(fā)送一跳的通信代價(jià)的聯(lián)合最小的節點(diǎn)作為下一跳節點(diǎn)，如式（3）所示：

Nnext(Ni)={Nj|min(h(Ni,Nj,T)=rc(Nj,T)+(1-r)Esend(Ni,Nj)),Nj∈NbNi} （3）

　　式中，Nnext(Ni)為節點(diǎn)Ni選擇的下一跳節點(diǎn)；h(Ni,Nj,T)為節點(diǎn)Ni經(jīng)由Nj到事件區域T的新代價(jià)值；Esend(Ni,Nj)為節點(diǎn)Ni到節點(diǎn)Nj的通信代價(jià)，如表1中的歸一化數值；NbNi為節點(diǎn)Ni的鄰居節點(diǎn)集合；r為比例系數，取值范圍為0~1。

仿真環(huán)境

仿真條件假設

　?。?）查詢(xún)信息中包含了目標區域（即事件區域）的位置，此處假設用目標區域的中心位置作為目標區域的位置；

　?。?）每個(gè)節點(diǎn)都知道自己的位置信息和剩余能量，并且可以通過(guò)一個(gè)簡(jiǎn)單的Hello機制獲取鄰居節點(diǎn)的位置信息和剩余能量。節點(diǎn)的位置信息可以使用低成本的GPS定位機制或者其他現成的定位機制獲得；

　?。?）節點(diǎn)間的鏈接是雙向的，即如果節點(diǎn)可以獲得鄰居節點(diǎn)的訪(fǎng)問(wèn)，則節點(diǎn)也可以訪(fǎng)問(wèn)鄰居節點(diǎn)，這對于一般的MAC協(xié)議，如IEEE 802.11，都是容易實(shí)現的；

　?。?）節點(diǎn)每消耗總能量的10％時(shí)，通知鄰居節點(diǎn)自己的剩余能量信息，用于更新鄰居節點(diǎn)中的鄰居節點(diǎn)列表信息；當節點(diǎn)剩余能量小于一個(gè)閾值時(shí)，將通知自己的鄰居節點(diǎn)，將自己從鄰居節點(diǎn)列表中刪除，表示該節點(diǎn)已經(jīng)死亡。

仿真參數

　　在100m*100m的區域內，隨機分布200個(gè)傳感器節點(diǎn)，節點(diǎn)初始能量為1000J，節點(diǎn)死亡能量閾值為5J，最大通信距離為25m，最大通信距離通信時(shí)，每次消耗1J能量。對于GPEAR算法，通信能耗與通信距離的關(guān)系由表1給出。仿真環(huán)境假設會(huì )聚節點(diǎn)(Sink)在整個(gè)區域的中心（50，50）處，四個(gè)事件區域在整個(gè)區域的四個(gè)角上（0，0）、（0，100）、（100，0）和（100，100），每個(gè)事件區域做100次查詢(xún)后，輪流轉換。

3  測試標準

　?。?）查詢(xún)成功次數：只有成功的查詢(xún)對用戶(hù)才是有用的，所以網(wǎng)絡(luò )能夠進(jìn)行的成功查詢(xún)次數可以體現網(wǎng)絡(luò )的生存周期和傳輸可靠性。

　?。?）每次成功查詢(xún)平均消耗的能量：該標準體現了整個(gè)網(wǎng)絡(luò )能量的利用效率。

　　每次查詢(xún)的平均消耗能量為整個(gè)網(wǎng)絡(luò )消耗能量除以成功查詢(xún)的次數，如式（4）所示。

仿真結果

圖1 衰減指數對算法性能的影響

　　圖1的結果表明，隨著(zhù)衰減指數（衰減指數為2表示發(fā)射能量和通信半徑的二次方成正比，依次類(lèi)推）的增長(cháng)， GPEAR算法的性能則改善非常明顯。

圖2最大允許跳數對算法性能的影響

　　圖2結果表明，最大允許跳數（即查詢(xún)從Sink節點(diǎn)到目的節點(diǎn)經(jīng)由的最大節點(diǎn)數，若超過(guò)這個(gè)最大數，則認為查詢(xún)失?。Ω魉惴ǖ挠绊懖皇呛苊舾?。若最大允許跳數小于15，GPEAR算法的成功查詢(xún)次數將大大下降，每次成功查詢(xún)的平均能耗也大大增加，這個(gè)是因為GPEAR算法的本質(zhì)是通過(guò)縮短每次通信半徑以降低總的查詢(xún)能耗，而這樣會(huì )增加中間經(jīng)由節點(diǎn)的數量，顯然若最大允許跳數太小，將會(huì )使失敗次數大大增加。另外GEAHAR算法要求最大允許跳數不能太大，否則會(huì )使失敗查詢(xún)消耗過(guò)多的能量，相對這種能耗過(guò)大更優(yōu)的方法是重新發(fā)送查詢(xún)信息。

　　綜合圖1和圖2表明，對于每次成功查詢(xún)平均消耗的能量：

　　(1)GEAHAR算法比GEAR算法約降低5%；

　　(2)當衰減指數為4、最大允許跳數為25時(shí)，GPEAR算法比AGEAR算法降低約60%。

圖3 GEAHAR算法中β參數的影響

　　圖3結果表明，β值在0.3～0.7時(shí)，GEAHAR算法性能基本是穩定的，而β過(guò)小或者過(guò)大則對算法性能影響較大。

　　圖4結果表明，參數y對GPEAR算法的性能有一定影響，參數y需要根據具體應用環(huán)境選擇，根據區域內的節點(diǎn)密度和衰減指數有關(guān)。

圖4 GPEAR算法中參數y的影響

結語(yǔ)

　　本文在GEAR路由的基礎上，以節約網(wǎng)絡(luò )節點(diǎn)能耗和延長(cháng)網(wǎng)絡(luò )生存周期為目標，提出了GEAHAR和GPEAR路由算法。仿真結果表明新的算法顯著(zhù)提高了網(wǎng)絡(luò )成功查詢(xún)次數，降低了每次查詢(xún)消耗的平均能量，從而達到了提高能量利用效率的效果。
    
參考文獻：

1.  Yu Y, Govindan R, Estrin D. Geographical and energy aware routing: A recursive data dissemination protocol for wireless sensor networks[R].UCLA Computer Science Department，2001，1—23．
2.  孫利民，無(wú)線(xiàn)傳感器網(wǎng)絡(luò )，清華大學(xué)出版社，2005
3.  孫雨耕、田飛，無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中一種能量有效的混合式拓撲算法，電子測量技術(shù)，2007，30(11)：69-73
4.  戴世瑾、張翼德，無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的路由協(xié)議研究與分析，計算機應用研究，2006，23(12)：294-297
5.  萬(wàn)東，無(wú)線(xiàn)傳感網(wǎng)絡(luò )路由算法的研究，浙江大學(xué)信息科學(xué)與工程學(xué)院，2006.
6.  高鍵，ZigBee無(wú)線(xiàn)傳感器網(wǎng)絡(luò )節點(diǎn)的耗能研究，電子測試，2008，2(2)：102-106.
7.  趙海霞,無(wú)線(xiàn)傳感器網(wǎng)絡(luò )GEAR協(xié)議的一種改進(jìn)方案，傳感器與微系統，2006，25(9)：61-63.
8.  劉林峰、劉業(yè)、莊艷艷，高效能耗傳感器網(wǎng)絡(luò )的模型分析與路由算法設計，電子學(xué)報，2007，35(3)：459-462.