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

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

引言

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

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

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

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

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

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

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

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)

設節(jié)點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。當全網的能耗均衡時，令Ei=Ei-1得：

(7)

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

(8)

消去常數k：

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

(9)

令E1=En則：

(10)

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

(11)

由母函數法得：

(12)

(13)

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

(14)

(15)

(16)

分析轉發(fā)概率Pi的表達式，Pi只與網絡規(guī)模n、特殊參數α和節(jié)點編號i相關，與節(jié)點數據產生量k無關。因此，只要確定n和α就可以確定節(jié)點的轉發(fā)概率。

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

表1 Pi與α的關系

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

2改進GPSR算法

2.1 原始GPSR算法

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

圖2 GPSR協議流程圖

2.2 改進GPSR算法

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

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

算法主要步驟如下：

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

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

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

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

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

3實驗結果與討論

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

3.1 平均能耗的比較

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

圖3 平均能耗隨仿真時間的變化

3.2 存活節(jié)點數量的比較

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

圖4 存活節(jié)點數隨仿真時間的變化

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

4結論

改進GPSR多跳算法在延長網絡壽命上效果更好，能量消耗更少,和鄰居列表維護更簡單，有效地減少了能量洞現象,延長了網絡生存時間。