基于改進(jìn)GPSR的WSN多跳概率算法

龔瑞昆，王彥植，陳旭東，張仲

(1. 華北理工大學(xué) 電氣學(xué)院，河北 唐山 063210；2. 河北省安裝工程有限公司第二分公司，河北 唐山 063000)

引言

在環(huán)境監(jiān)測(cè)領(lǐng)域尤其是濕地環(huán)境下存在無法布線問題， 許多設(shè)備需要依靠電池并通過無線節(jié)點(diǎn)傳輸數(shù)據(jù)。網(wǎng)絡(luò)生存時(shí)間的長短影響著環(huán)境監(jiān)測(cè)的效率。根據(jù)調(diào)查，能量洞內(nèi)的節(jié)點(diǎn)電量消耗較快，但其余節(jié)點(diǎn)仍剩余大量電量，這導(dǎo)致外側(cè)的節(jié)點(diǎn)無法將數(shù)據(jù)傳送至sink節(jié)點(diǎn)，造成整個(gè)監(jiān)測(cè)系統(tǒng)的癱瘓。因此，如何利用現(xiàn)有的計(jì)算機(jī)技術(shù)延長網(wǎng)絡(luò)的生存時(shí)間，減少人力物力的浪費(fèi)，成為許多研究人員的研究熱點(diǎn)。

近年來，許多專家對(duì)此提出了不同的策略。文獻(xiàn)[1]提出一種和當(dāng)前電量掛鉤的轉(zhuǎn)發(fā)概率參數(shù)。電量越低，充當(dāng)轉(zhuǎn)發(fā)點(diǎn)的概率越低。該算法具有高動(dòng)態(tài)性，可以很好地適應(yīng)轉(zhuǎn)發(fā)的及時(shí)性，但當(dāng)電量過低時(shí)，轉(zhuǎn)發(fā)概率過低，無疑降低了系統(tǒng)效率。且將其他節(jié)點(diǎn)的電量當(dāng)作參考量，又要求實(shí)時(shí)查看其他節(jié)點(diǎn)的電量，查看過程中又浪費(fèi)了更多電量。文獻(xiàn)[2]提出一種將轉(zhuǎn)發(fā)任務(wù)強(qiáng)制安排給剩余電量多的節(jié)點(diǎn)的方法。此方法照顧了電量均衡，卻沒有考慮整體耗電，整體耗電量反而增加了，這不利于網(wǎng)絡(luò)壽命提高。文獻(xiàn)[3-5]均提出改進(jìn)GPSR算法，但是其條件函數(shù)復(fù)雜，需要頻繁維護(hù)鄰居列表，增加了能耗。還有文獻(xiàn)提出了新的節(jié)點(diǎn)部署策略[7-9]，但這些布點(diǎn)方法較為復(fù)雜，現(xiàn)實(shí)情況下難以實(shí)施。

針對(duì)上述不足，研究提出了一種基于改進(jìn)多跳模型的WSN能量均衡數(shù)據(jù)傳輸方法，該方法在解決節(jié)點(diǎn)能耗不均問題上，能夠取得較好效果，相較于其他算法，其適用簡單，穩(wěn)定性強(qiáng)。

1節(jié)點(diǎn)多跳傳輸模型

假設(shè)節(jié)點(diǎn)有2種能耗不同的發(fā)射半徑，其中r1半徑能耗為c1、r2半徑能耗為c2,且r2=2r1。接收1 bt數(shù)據(jù)能耗記為c0。節(jié)點(diǎn)間距離均為r1。sink節(jié)點(diǎn)放置在終點(diǎn)，不考慮電量。節(jié)點(diǎn)自身產(chǎn)生的數(shù)據(jù)量均為k bt。節(jié)點(diǎn)分別以Pi概率和1-Pi概率向距離r1和r2的節(jié)點(diǎn)發(fā)送數(shù)據(jù)。圖1所示為節(jié)點(diǎn)跳躍傳輸模型。

圖1 節(jié)點(diǎn)跳躍傳輸模型

如圖1所示，假設(shè)在單位時(shí)間內(nèi)，第i個(gè)節(jié)點(diǎn)以r1或r2傳送的數(shù)據(jù)量為Gi或Hi，第i個(gè)節(jié)點(diǎn)接收的數(shù)據(jù)量為Fi。模型的初始條件為：F0=nk，F(xiàn)n=0,Fn-1=Gn,H1=0。節(jié)點(diǎn)i自身產(chǎn)生的流量，此流量也將通過2種傳送方式傳送。依據(jù)流量守恒定律列式：

Fi=Gi+1+Hi+2

(1)

Fi+k=Gi+Hi

(2)

消去Hi后，由累加法得：

Gi=Fi+Fi-1+(i-n)k

(3)

代入選擇概率Pi：

Fi+k=PiGi+(1-Pi)Hi

(4)

設(shè)節(jié)點(diǎn)i的能耗為Ei則有：

Ei=C0Fi+C1Gi+C2Hi

(5)

消去Hi：

Ei=(C0+C2)Fi+(C1-C2)Gi+C2k

(6)

記(C0+C2)為A, (C1-C2)為B，C2k為C。當(dāng)全網(wǎng)的能耗均衡時(shí)，令Ei=Ei-1得：

(7)

(1+t)Δi+Δi-1=-k

(8)

消去常數(shù)k：

(1+t)Δi-tΔi-tΔi-1-Δi-2=0

(9)

令E1=En則：

(10)

-Δn=m(Δ1+nk)+k

(11)

由母函數(shù)法得：

(12)

(13)

Gi=Fi+Fi-1+(i-n)k

(14)

(15)

(16)

分析轉(zhuǎn)發(fā)概率Pi的表達(dá)式，Pi只與網(wǎng)絡(luò)規(guī)模n、特殊參數(shù)α和節(jié)點(diǎn)編號(hào)i相關(guān)，與節(jié)點(diǎn)數(shù)據(jù)產(chǎn)生量k無關(guān)。因此，只要確定n和α就可以確定節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率。

選取應(yīng)用于環(huán)境監(jiān)測(cè)的無線傳輸模塊，通過查閱通信模塊的數(shù)據(jù)手冊(cè)可得，α的取值在2.8到10之間。為了研究方便，分別設(shè)立3組 取值為3、6、9，研究n=10時(shí)α和Pi的關(guān)系。表1所示為Pi與α的關(guān)系。

表1 Pi與α的關(guān)系

表1的數(shù)據(jù)顯示，當(dāng)α取不同值時(shí)Pi隨i變化時(shí)，由于概率的取值非負(fù)，故舍去小于0的部分。根據(jù)表1可以看出，α較大的通信模塊，更有利于實(shí)現(xiàn)能量均衡。設(shè)n0為最大連續(xù)節(jié)點(diǎn)數(shù)。表1中的n0分別為5、8、10。當(dāng)n

2改進(jìn)GPSR算法

2.1 原始GPSR算法

GPSR算法由貪婪轉(zhuǎn)發(fā)與邊界轉(zhuǎn)發(fā)組合而成。節(jié)點(diǎn)根據(jù)相對(duì)位置確定轉(zhuǎn)發(fā)策略并周期性廣播hello數(shù)據(jù)包來更新鄰居路由表，確定相鄰節(jié)點(diǎn)位置。首先通過貪婪算法轉(zhuǎn)發(fā)數(shù)據(jù)，選擇更接近終點(diǎn)的鄰居節(jié)點(diǎn)。否則采用邊界轉(zhuǎn)發(fā)算法，把數(shù)據(jù)傳送給網(wǎng)絡(luò)平面圖的臨近節(jié)點(diǎn)，直到出現(xiàn)更接近終點(diǎn)的鄰居節(jié)點(diǎn)。GPSR流程圖如圖2所示。GPSR使用貪婪算法達(dá)成局部最優(yōu)，不需要在節(jié)點(diǎn)中構(gòu)建并更新全部路由列表，路由開銷小。

圖2 GPSR協(xié)議流程圖

2.2 改進(jìn)GPSR算法

GPSR算法優(yōu)化效果好，但在貪婪轉(zhuǎn)發(fā)模式下，節(jié)點(diǎn)只與距離最近的節(jié)點(diǎn)通信，這樣會(huì)在sink附近形成多個(gè)熱點(diǎn)節(jié)點(diǎn)，熱點(diǎn)節(jié)點(diǎn)負(fù)擔(dān)增加會(huì)提前耗盡能量，進(jìn)而產(chǎn)生能量洞，縮短網(wǎng)絡(luò)生存時(shí)間。因此，對(duì)GPSR算法進(jìn)行改良，增加能量均值函數(shù)，用能量均值限制GPSR選擇能量較低的節(jié)點(diǎn)。

綜上所述，改進(jìn)GPSR多跳算法的基本思想是：前期采用改進(jìn)GPSR算法對(duì)監(jiān)測(cè)區(qū)域進(jìn)行全局搜索，尋找全局最優(yōu)解；后期通過多跳算法進(jìn)行優(yōu)化，通過式(16)計(jì)算跳躍概率，節(jié)點(diǎn)按概率選擇單跳或多跳。2種算法優(yōu)勢(shì)結(jié)合，共同完成對(duì)節(jié)點(diǎn)路徑的選擇。

算法主要步驟如下：

(1)查找鄰居列表，如列表中包含sink，則直接傳遞給sink，否則轉(zhuǎn)到步驟(2)；

(2)記錄當(dāng)前節(jié)點(diǎn)到sink的距離，將小于此距離的節(jié)點(diǎn)納入可選列表里；

(3)計(jì)算可選列表里的節(jié)點(diǎn)能量均值，剔除 的節(jié)點(diǎn)；

(4)按照貪婪轉(zhuǎn)發(fā)與周邊轉(zhuǎn)發(fā)選擇下一跳節(jié)點(diǎn)。生成改進(jìn)GPSR路徑；

(5)按照多跳算法在GPSR已生成路徑上根據(jù)式(16)計(jì)算多跳概率。生成多跳路徑。

3實(shí)驗(yàn)結(jié)果與討論

為了驗(yàn)證不同算法對(duì)網(wǎng)絡(luò)能量消耗的均衡結(jié)果，采用NS2軟件進(jìn)行仿真實(shí)驗(yàn)。網(wǎng)絡(luò)區(qū)域?yàn)? 000 mm×1 000 mm的正方形，在區(qū)域內(nèi)隨機(jī)分布200個(gè)節(jié)點(diǎn)，sink節(jié)點(diǎn)坐標(biāo)設(shè)置為(0，500)所有節(jié)點(diǎn)開始攜帶的能量為2 J，sink節(jié)點(diǎn)無電量限制，節(jié)點(diǎn)通信半徑可調(diào)，最大通信半徑為300 m。Q設(shè)置為0.8。

3.1 平均能耗的比較

圖3所示為節(jié)點(diǎn)平均能耗變化圖。通過圖3可以比較出LEACH算法、PEGASIS算法和改進(jìn)GPSR多跳算法對(duì)節(jié)點(diǎn)能耗的優(yōu)化效果。開始時(shí)不同算法在能量充足的條件下均找到了最優(yōu)解,故起始階段平均能耗相同。隨后熱點(diǎn)節(jié)點(diǎn)電量下降，改進(jìn)GPSR多跳算法開始控制熱點(diǎn)節(jié)點(diǎn)電量，其平均能耗少于另外2種算法。

圖3 平均能耗隨仿真時(shí)間的變化

3.2 存活節(jié)點(diǎn)數(shù)量的比較

從圖4可以看出,仿真前期,各算法中節(jié)點(diǎn)能量均未耗盡,當(dāng)40 s后,LEACH由于平衡性不佳,率先出現(xiàn)死亡節(jié)點(diǎn)。60 s后,PEGASIS算法開始出現(xiàn)死亡節(jié)點(diǎn)。改進(jìn)GPSR多跳算法在第70 s后,出現(xiàn)死亡節(jié)點(diǎn)。并相繼產(chǎn)生死亡節(jié)點(diǎn)。在180 s迭代后,所有算法均加快產(chǎn)生死亡節(jié)點(diǎn),但改進(jìn)GPSR多跳算法存活節(jié)點(diǎn)數(shù)量依舊多于其他算法。

圖4 存活節(jié)點(diǎn)數(shù)隨仿真時(shí)間的變化

從圖3和圖4中可以看出，相比于GPSR多跳算法,常見的無線自組網(wǎng)算法對(duì)節(jié)點(diǎn)能耗均衡的平衡效果較差。常用的WSN算法響應(yīng)時(shí)間慢，更新鄰居列表頻繁。PEGASIS算法平均能耗較高，LEACH算法維護(hù)路由列表開銷大。而采用改進(jìn)GPSR多跳算法對(duì)延長網(wǎng)絡(luò)生存時(shí)間的效果就比較好，反應(yīng)速度快，鄰居列表維護(hù)次數(shù)少。

4結(jié)論

改進(jìn)GPSR多跳算法在延長網(wǎng)絡(luò)壽命上效果更好，能量消耗更少,和鄰居列表維護(hù)更簡單，有效地減少了能量洞現(xiàn)象,延長了網(wǎng)絡(luò)生存時(shí)間。