何燕清， 鄧華秋

(華南理工大學(xué) 物理與光電學(xué)院，廣東 廣州 510640)

?

基于能量梯度改進(jìn)的GPSR協(xié)議

何燕清， 鄧華秋

(華南理工大學(xué) 物理與光電學(xué)院，廣東 廣州 510640)

針對貪婪周邊無狀態(tài)路由(GPSR)協(xié)議存在的路由熱點以及能量消耗過快的情況，提出了一種基于能量梯度和距離的改進(jìn)型GPSR路由協(xié)議。查詢消息在沿著路由路徑傳輸時，根據(jù)前方節(jié)點的能量和當(dāng)前節(jié)點到目的節(jié)點的距離選擇下一跳節(jié)點；根據(jù)能量閾值以及該節(jié)點的鄰居節(jié)點數(shù)對該節(jié)點進(jìn)行修正，從而均衡能量消耗。仿真結(jié)果表明：改進(jìn)的GPSR協(xié)議有效延長了網(wǎng)絡(luò)生存周期，并在網(wǎng)絡(luò)初期有效避免數(shù)據(jù)的冗余傳輸。

貪婪周邊無狀態(tài)路由(GPSR)協(xié)議； 能量閾值； 網(wǎng)絡(luò)生存周期

0 引 言

如何最大限度地降低無線傳感器網(wǎng)絡(luò)(WSNs)中傳感器節(jié)點的能耗，盡可能地延長網(wǎng)絡(luò)的生命周期，一直是該領(lǐng)域廣泛關(guān)注的研究熱點，也是衡量無線傳感器網(wǎng)絡(luò)路由協(xié)議的重要指標(biāo)。

基于地理位置的路由協(xié)議改進(jìn)了洪泛算法的盲目性和開銷大等缺陷[1],但是基于地理位置的路由存在路由空洞的問題。為此， Karp B等人提出的貪婪周邊無狀態(tài)路由(greedy perimeter stateless routing,GPSR)算法[2]，采用貪婪準(zhǔn)則和周邊轉(zhuǎn)發(fā)的路由方式保證數(shù)據(jù)包的可靠傳輸。但是仍然存在能量利用率不高的情況，主要表現(xiàn)在：節(jié)點使用不均衡，造成局部節(jié)點過早死亡[3]；存在需要周邊轉(zhuǎn)發(fā)時，不能提前預(yù)判造成部分節(jié)點能量流失。丁心體等人[4]提出的綜合考慮能量水平和位置信息選擇下一跳節(jié)點，從而使負(fù)載相對均衡，避免熱點路由上節(jié)點的過早死亡和網(wǎng)絡(luò)生存時間縮短。王建新等人[5]提出的基于兩跳鄰居信息的貪婪地理路由算法，對Greedy-2算法進(jìn)行改進(jìn)提出了平面化算法,這種算法不需要增加額外的平面開銷，就能將網(wǎng)絡(luò)平面化來采取邊緣恢復(fù)機(jī)制。朱全政等人[6]提出的能量角度聯(lián)合自適應(yīng)路由修復(fù)新算法和曹海英等人[7]提出的基于節(jié)點剩余能量和最大角度的無線傳感器網(wǎng)絡(luò)路由算法思路基本一致，都是將節(jié)點剩余能量與最大角度相結(jié)合對路由進(jìn)行修復(fù)。薛明等人[8]將網(wǎng)絡(luò)最大生命周期問題轉(zhuǎn)化成網(wǎng)絡(luò)最小歸一化負(fù)載問題，從而來延長網(wǎng)絡(luò)的生命周期。

為了均衡節(jié)點的能量消耗，有效延長網(wǎng)絡(luò)生存周期，本文采用能量梯度的概念，根據(jù)節(jié)點的網(wǎng)絡(luò)的能量劃定節(jié)點的能量閾值，同時在路由路徑選擇上還考慮節(jié)點到目的節(jié)點的距離。通過這種綜合考慮減少不必要路由的出現(xiàn)，極大地均衡了節(jié)點的能量消耗，從而延長傳感器網(wǎng)絡(luò)的生命周期。

1 相關(guān)模型

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

網(wǎng)絡(luò)是由N個傳感器節(jié)點隨機(jī)分布在一個矩形區(qū)域M×M內(nèi)，并假設(shè)傳感器網(wǎng)絡(luò)具有以下性質(zhì)：

1)沒有節(jié)點完全位于同一個位置，源節(jié)點和目的節(jié)點位于同一片區(qū)域范圍內(nèi)，且假定所有節(jié)點一旦布設(shè)好之后位置不能再變化；

2)每個傳感器具有唯一的標(biāo)識(ID)；

3)所有傳感器節(jié)點具有相同的傳輸率，且所有節(jié)點的傳輸半徑都是相同的為R；

4)所有的節(jié)點通過定位算法或是GPS能計算出自己的位置和鄰居節(jié)點的位置。相鄰節(jié)點之間的距離采用歐氏距離公式計算，計算公式為

(1)

式中 xi，yi，xj，yj分別為傳感器節(jié)點i與j的橫坐標(biāo)和縱坐標(biāo)，d(i,j)為兩傳感器節(jié)點之間的歐氏距離。

1.2 能量模型

所有節(jié)點的初始能量都是相同的為E0，在無線傳感器網(wǎng)絡(luò)路由過程中，除了發(fā)送數(shù)據(jù)和接收數(shù)據(jù)包消耗能量外，其他能量消耗都忽略不計。其中傳送數(shù)據(jù)包消耗能量為ETX,接收數(shù)據(jù)包消耗能量為ERX。 即傳輸距離為d且發(fā)射qbit的信息包所消耗的能量公式ETX(q,d)為[9]

ETX(q,d)=Eele×q+Eamp×q×d3

(2)

接收qbit信息包所損耗的能量公式ERX(q)為

ERX(q)=Eele×q

(3)

式中Eele為發(fā)射、接收電路傳輸單位bit信息的無線電耗能；Eamp為發(fā)射放大器將1 bit信息傳送單位面積(m2)所消耗的能量,q為數(shù)據(jù)包的大小。

傳感器節(jié)點i在傳輸過程中消耗的能量為

Ec=ETX(q,d)+ERX(q)

(4)

為了均衡網(wǎng)絡(luò)節(jié)點能量消耗，避免采用固定最小能量閾值的方法，本文采用何杏宇等人[10]提出的動態(tài)變化的節(jié)點剩余能量閾值模型

(5)

式中 α為協(xié)調(diào)系數(shù)用來調(diào)整網(wǎng)絡(luò)節(jié)點初始能量E0的減小速度，x為節(jié)點剩余能量閾值E的變化次數(shù)。該模型在網(wǎng)絡(luò)初始階段剩余能量閾值變化快，當(dāng)整個網(wǎng)絡(luò)能量水平較低時，能量閾值變化緩慢。

2 改進(jìn)的GPSR算法

2.1 GPSR算法描述

在文獻(xiàn)[4]中提到GPSR是一種基于傳統(tǒng)貪婪轉(zhuǎn)發(fā)方案的路由協(xié)議。采用貪婪策略和邊界轉(zhuǎn)發(fā)相結(jié)合選擇下一跳節(jié)點進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。貪婪策略，即節(jié)點在數(shù)據(jù)轉(zhuǎn)發(fā)時總是選擇比自己近且到目的節(jié)點距離最近的鄰居節(jié)點作為下一跳。GPSR算法在實現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)時，節(jié)點根據(jù)鄰居節(jié)點的分布情況選擇不同的轉(zhuǎn)發(fā)模式。當(dāng)節(jié)點能夠從鄰居節(jié)點中選出比自己更近的下一跳節(jié)點時，節(jié)點利用貪婪模式進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā);否則，節(jié)點利用邊界轉(zhuǎn)發(fā)模式進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。

2.2 改進(jìn)的GPSR算法分析

2.2.1 相關(guān)說明

(6)

網(wǎng)絡(luò)收斂：各節(jié)點發(fā)送自己的位置信息到鄰居節(jié)點，并收集鄰居節(jié)點的信息，將鄰居節(jié)點的信息加入到鄰居路由表中。

2.2.2 初始路徑下一跳節(jié)點選擇

源節(jié)點向自己通信范圍內(nèi)的所有相鄰節(jié)點廣播興趣消息，先根據(jù)路由表中的信息計算出所有鄰居節(jié)點的平均能量，如果當(dāng)前節(jié)點的鄰居節(jié)點的能量都相同，則采用最鄰近目的節(jié)點的貪婪準(zhǔn)則選擇下一跳節(jié)點。如果能量不全相同，則在這些節(jié)點中選擇滿足最大概率值的節(jié)點作為下一跳節(jié)點。最大概率選擇計算如下

(7)

式中 Ei為要選擇的下一跳節(jié)點的能量值，E-l為當(dāng)前節(jié)點有效節(jié)點的平均能量值,d為當(dāng)前節(jié)點到目的節(jié)點的距離，di為當(dāng)前節(jié)點要選擇的下一跳節(jié)點到目的節(jié)點的距離值，α和β為所占比例。

2.2.3 初始路徑的優(yōu)化

對于路徑上的節(jié)點可能會出現(xiàn)本來一跳就能到達(dá)的節(jié)點，又經(jīng)過另外一個中間節(jié)點才傳送的情況。這對于數(shù)據(jù)的傳輸時延會造成一定影響，還會大量消耗空洞附近節(jié)點的能量從而造成網(wǎng)絡(luò)的過早死亡。這種情況主要是路由空洞的出現(xiàn)造成的。為了有效避免路由空洞現(xiàn)象的發(fā)生，提出一種提前預(yù)判的解決方案，避免周邊轉(zhuǎn)發(fā)帶來的時延。根據(jù)初始路由選擇確定的下一跳節(jié)點，進(jìn)行重新優(yōu)化更新處理?；镜牧鞒虉D如圖1。

圖1 路由路徑優(yōu)化Fig 1 Routing path optimization

2.2.4 路徑修復(fù)

為了保存無線傳感器網(wǎng)絡(luò)節(jié)點的能量，改進(jìn)的GPSR算法允許不被初始路由路徑選中的節(jié)點進(jìn)入休眠狀態(tài)。本文進(jìn)一步提出了能量閾值隨網(wǎng)絡(luò)能量變化而變化的策略，即能量感知閾值變化的路由修復(fù)算法。

路徑修復(fù)具體流程如下：

1)隨著數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸，節(jié)點能量不斷被消耗。根據(jù)節(jié)點剩余能量閾值模型，節(jié)點的剩余能量閾值將會發(fā)生變化，這時將會使原來的路由路徑上的部分節(jié)點“失效”。路由路徑將進(jìn)行修復(fù)。

2)對于出現(xiàn)上述情況時，失效節(jié)點的父節(jié)點將會根據(jù)最大概率式(7)選擇下一跳節(jié)點。對于式(7)選擇出來的節(jié)點，根據(jù)路徑優(yōu)化原則進(jìn)行優(yōu)化。從而完成對無線傳感器網(wǎng)絡(luò)路由的修復(fù)。

上述對路由的修復(fù)過程，主要是為了均衡網(wǎng)絡(luò)能量消耗，縮短數(shù)據(jù)傳輸時延。路由修復(fù)的過程示意圖如圖2。

圖2 路徑修復(fù)示意圖Fig 2 Path repairing diagram

3 仿真實驗

3.1 仿真實驗環(huán)境參數(shù)

為了測試本文算法在延長網(wǎng)絡(luò)生命周期的有效性，采用Matlab 2010a仿真工具實現(xiàn)仿真實驗。本文提出的算法在初始路由路徑、路由路徑跳數(shù)、節(jié)點能量閾值和網(wǎng)絡(luò)能量關(guān)系以及網(wǎng)絡(luò)生存周期等方面進(jìn)行了綜合的分析，并與文獻(xiàn)[2]和文獻(xiàn)[6]進(jìn)行比較。不考慮無線通信鏈路的信號沖突和噪聲等因素[11]。仿真實驗場景參數(shù):節(jié)點數(shù)為75～150，網(wǎng)絡(luò)范圍為100 m×100 m，通信半徑為20 m，數(shù)據(jù)包長度為4 000 bit，Eele為50 nJ/bit，Eamp為0.1 nJ/(bit·m2，節(jié)點初始能量為0.5 J。

3.2 仿真結(jié)果分析

1) 初始路由路徑的選擇比較

將本文算法與文獻(xiàn)[2]和文獻(xiàn)[6]的初始路徑建立情況進(jìn)行比較如圖3，可以看出：本文在初始路徑上跳數(shù)相對較少，可以在網(wǎng)絡(luò)建立初期快速傳遞數(shù)據(jù)。同時也說明了對于遇到空洞情況能夠提前預(yù)判，避免GPSR算法那樣導(dǎo)致路由失敗。

圖3 不同算法初始路徑比較Fig 3 Comparison of initial routing paths by different algorithms

2)網(wǎng)絡(luò)建立之后的路由路徑跳數(shù)比較

路由路徑條數(shù)情況如圖4。本文算法為了均衡能量消耗，節(jié)點跳數(shù)較文獻(xiàn)[2]和文獻(xiàn)[6]多,但是隨著節(jié)點連通性變化，本文節(jié)點路由跳數(shù)也將減少達(dá)到最佳值。

圖4 路由跳數(shù)比較Fig 4 Comparison of routing hops

3)網(wǎng)絡(luò)總體能量隨時間的變化

隨著網(wǎng)絡(luò)的運行節(jié)點能量不斷消耗，本文提出的改進(jìn)GPSR算法節(jié)點能量消耗情況與文獻(xiàn)[6]和文獻(xiàn)[2]算法進(jìn)行比較如圖5，圖中虛線表示此時網(wǎng)絡(luò)已經(jīng)壞死。通過比較可以看出，本文算法在網(wǎng)絡(luò)建立初期消耗的能量較另外幾種算法多，這是均衡能量消耗帶來的結(jié)果。但是能量均衡消耗極大地延長了網(wǎng)絡(luò)的生存周期。

圖5 網(wǎng)絡(luò)剩余能量隨工作輪數(shù)的變化Fig 5 Residual energy of network change with working rounds

4)網(wǎng)絡(luò)生存時間

通過圖6可以看出文獻(xiàn)[6]提高網(wǎng)絡(luò)生存周期的能力有限，而本文算法極大提高了網(wǎng)絡(luò)的生存周期。

圖6 網(wǎng)絡(luò)生存周期Fig 6 Network lifecycle

4 結(jié) 論

本文提出了一種能量梯度改進(jìn)的GPSR協(xié)議。在原有GPSR的基礎(chǔ)上對路徑上節(jié)點進(jìn)行標(biāo)記，每一個節(jié)點的選擇不僅考慮到節(jié)點的能量還考慮到節(jié)點到目的節(jié)點的距離。對于預(yù)選擇的節(jié)點進(jìn)行鄰居節(jié)點數(shù)的判斷，有效減少了節(jié)點出現(xiàn)空洞的情況。為了減少路由跳數(shù)進(jìn)一步均衡能量消耗，提出了節(jié)點能量閾值隨網(wǎng)絡(luò)總能量變化的策略。仿真結(jié)果表明：本文提出的改進(jìn)協(xié)議有效均衡了節(jié)點的能量消耗，延長了網(wǎng)絡(luò)的生存周期。

[1] 劉海燕,李道全,王懷彩,等.兩類無線自組網(wǎng)路由協(xié)議的比較研究[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2009(3):15-17.

[2] Kapp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proc of The 6th Annual International Conference on Mobile Computing and Networking,New York:

ACM,2000:243-254.

[3] 沈丹丹,王立華,王 宇,等.一種基于分簇的無線傳感器網(wǎng)絡(luò)GPSR協(xié)議[J].傳感器與微系統(tǒng),2015,34(12):124-130.

[4] 丁心體,彭新光.一種基于GPSR協(xié)議的能量均衡路由[J].傳感器與微系統(tǒng),2013,32(4):12-15.

[5] 王建新,趙湘寧,劉輝宇.一種基于兩跳鄰居信息的貪婪地理路由算法[J].電子學(xué)報,2008,36(10):193-199.

[6] 朱全政,楊 樂.能量角度聯(lián)合自適應(yīng)路由修復(fù)新算法[J].計算機(jī)應(yīng)用研究,2014,31(6):1779-1782.

[7] 曹海英,元 元,劉志強(qiáng).基于節(jié)點剩余能量和最大角度的無線傳感器網(wǎng)絡(luò)路由算法[J].傳感器與微系統(tǒng),2015,34(1):120-123.

[8] 薛 明,高德民.無線傳感器網(wǎng)絡(luò)最大生命期聚合樹路由算法[J].傳感器與微系統(tǒng),2014,33(1):130-133.

[9] 吳三斌,柳 強(qiáng),李成博,等.基于能量均衡的無線傳感器網(wǎng)絡(luò)路由算法[J].計算機(jī)應(yīng)用研究,2012,29(4):1465-1469.

[10] 何杏宇,周亦敏,楊桂松,等.無線傳感器網(wǎng)絡(luò)能量感知增強(qiáng)樹型路由協(xié)議研究[J].傳感技術(shù)學(xué)報,2015,28(4):551-556.

[11] 陳雪嬌,李向陽.WSNs中LEACH協(xié)議的研究及改進(jìn)[J].計算機(jī)應(yīng)用,2009,29(12):3241-3243.

鄧華秋，通訊作者，E—mail:hqdeng@scut.edu.cn。

Improved GPSR routing protocols based on energy gradient

HE Yan-qing， DENG Hua-qiu

(School of Physics and Optoelectronics,South China University of Technology,Guangzhou 510640,China)

Propose a modified greedy perimeter stateless routing(GPSR) routing protocol based on energy gradient and distance to solve problems of routing hotspot and energy consumption too fast of GPSR protocol.When the query message transmits along the routing path,choose the next-hop node,according to energy of the previous node and distance between the current node and the destination node; then,modify the node according to the energy threshold and the number of neighbor nodes,so as to balance energy consumption.The simulation results show that the improved GPSR protocol prolongs the network life cycle effectively,and avoids redundant data transmission at the beginning of the network.

greedy perimeter stateless routing(GPSR)protocol; energy threshold; network lifetime

10.13873/J.1000—9787(2016)12—0044—04

2016—10—10

TP 393

A

1000—9787(2016)12—0044—04

何燕清(1990-)，男，湖北十堰人，碩士研究生，研究方向為無線傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)。