無線網(wǎng)狀網(wǎng)中延長網(wǎng)絡生命周期的機會路由

徐 倩，徐玉斌

(太原科技大學 計算機科學與技術學院，太原 030024)

無線傳感器網(wǎng)絡[1](Wireless Sensor Networks, WSNs)是由很多個傳感器節(jié)點構成的多跳網(wǎng)絡，普遍應用于各個領域。由于網(wǎng)絡中節(jié)點的能量由電池供應，能量存儲有一定的限制，所以如何改善網(wǎng)絡的生存周期，使節(jié)點的能量消耗變得均衡尤為重要。而在無線傳感器網(wǎng)絡中，在均衡能量消耗方面，設計低能耗的路由協(xié)議起到了舉足輕重的作用，其中，Biswas[2]等人首先提出的機會路由[3-4]充分利用無線鏈路的廣播特性和異變性，考慮節(jié)點選擇下一跳轉發(fā)路徑的機會性，從而有效提高了無線多跳網(wǎng)絡的可靠性，減少了數(shù)據(jù)傳輸次數(shù)，對照傳統(tǒng)的路由協(xié)議，機會路由有效的提高了網(wǎng)絡的生命周期。在節(jié)能機會路由的研究中，文獻[5]結合節(jié)點的成功傳輸次數(shù)與節(jié)點剩余能量，提出了一種候選節(jié)點選擇策略，對網(wǎng)絡的生存時間有了明顯的提高。文獻[6]利用地理信息，提出一種自適應轉發(fā)集優(yōu)化算法，優(yōu)化傳輸效率并最大化網(wǎng)絡生命周期。文獻[7]綜合考慮了節(jié)點剩余能量和鏈路上收發(fā)雙方總能耗，同時引入隨機網(wǎng)絡編碼，設計了一種轉發(fā)節(jié)點集選擇算法。不僅保證了數(shù)據(jù)傳輸?shù)目煽啃?，也?yōu)化了網(wǎng)絡生存時間。上述研究從優(yōu)化節(jié)點候選集出發(fā)，通過減小節(jié)點傳輸數(shù)據(jù)的能耗來降低網(wǎng)絡能量消耗。由于候選集節(jié)點的數(shù)量大小也會影響無線網(wǎng)絡的性能，文獻[8-10]分別提出幾種控制節(jié)點數(shù)量的方法。文獻[10]考慮了節(jié)點間隔距離、網(wǎng)絡密度等因素，設計了一種候選節(jié)點數(shù)量選取算法，減少了網(wǎng)絡中冗余的候選節(jié)點，提升了網(wǎng)絡的性能。

智能電表網(wǎng)狀網(wǎng)(AMI mesh network)是由多個智能電表組成的一種多跳無線網(wǎng)絡，相比于有線通信的組網(wǎng)方式，無線通信的模式使得傳感器節(jié)點部署便利，成本低廉[11]。文獻[12]以此為背景，將機會路由應用在智能電表網(wǎng)狀網(wǎng)中，提出盡快完成采集數(shù)據(jù)傳輸?shù)臋C會路由問題，將機會路由候選節(jié)點選擇問題建模并求解。文獻[13]考慮數(shù)據(jù)流的分布，將機會路由選擇問題描述成凸優(yōu)化問題，并且提出了一種多流機會路由算法以提升網(wǎng)絡吞吐量。

本文以智能電表為應用背景，在多跳無線的組網(wǎng)形式下，結合該網(wǎng)絡固有的特征，設計了一種基于地理位置信息、以均衡節(jié)點能耗為目的的機會主義路由協(xié)議GEOR，旨在保證數(shù)據(jù)傳輸可靠性的同時，有效延長網(wǎng)絡的生命周期。

1 問題描述

如圖1所列舉的一個簡單無線網(wǎng)狀網(wǎng)示例圖，其中，節(jié)點D作為目的節(jié)點，剩余節(jié)點均作為源節(jié)點。其網(wǎng)絡特征總結如下：

(1) 網(wǎng)絡中節(jié)點排列有序，節(jié)點間最小間隔距離相同；

(2) 已知地理位置信息，且網(wǎng)絡拓撲結構基本不變；

(3) 在數(shù)據(jù)采集階段，源節(jié)點傳送單個數(shù)據(jù)包到目的端。

圖1 無線網(wǎng)狀網(wǎng)拓撲結構
Fig.1 Topology of wireless mesh network

傳統(tǒng)的以地理距離為測度的機會路由(如GeRaF)，僅考慮地理位置來決定節(jié)點轉發(fā)優(yōu)先級，造成過度利用距離目的節(jié)點較近節(jié)點的問題，第一個死亡節(jié)點的出現(xiàn)時間較早，導致整個網(wǎng)絡的生命周期較短。針對上述問題，將節(jié)點的剩余能量作為參考因素，提出了一種將節(jié)點剩余能量與地理距離結合的路由測度，在選擇節(jié)點轉發(fā)集時，優(yōu)先選擇距離目的節(jié)點近且能量高的節(jié)點，考慮如下路由測度公式：

REEi=REi/d(i,D)

(1)

其中，REi指代節(jié)點i的剩余能量，d(i,D)指代節(jié)點i與目的節(jié)點D之間的距離。

以RRE作為一種候選集節(jié)點選擇測度，雖然提高了網(wǎng)絡生命周期，但在選取下一跳節(jié)點時，仍然會對距離目的節(jié)點較近的節(jié)點造成一種能量負擔。考慮圖2所列舉的一個簡單網(wǎng)絡，S為源節(jié)點，D為目的節(jié)點，A,B,C作為轉發(fā)節(jié)點。令d(S,D)表示兩節(jié)點S與D的間隔距離，其中，d(B,D)= 20 m，d(C,D)=10，初始能量EB=EC=50 J，計算可得節(jié)點B與C的路由測度分別為：RREB=50/20,RREC=50/10，則選擇測度值較大的節(jié)點C作為下一跳節(jié)點，當節(jié)點C的能量消耗至25 J時，RREB=RREC，此時節(jié)點B的能量值較大，與均衡節(jié)點能耗的初衷相悖，并且這樣更容易出現(xiàn)節(jié)點過早死亡。

圖2 網(wǎng)絡拓撲結構
Fig.2 Network topology

由上述描述，在網(wǎng)絡拓撲結構變化較小的情況下，距離目的節(jié)點較近的節(jié)點有更大的機會轉發(fā)數(shù)據(jù)，并且其余節(jié)點轉發(fā)數(shù)據(jù)的機會受到候選集中節(jié)點間距離差值大小的影響。所以，如何結合節(jié)點剩余能量與位置信息選擇下一跳轉發(fā)節(jié)點，盡可能使得每個節(jié)點的剩余能量在一個較小的范圍內波動，是本文所要解決的問題。

2 GEOR路由協(xié)議設計

2.1 節(jié)點剩余能量模型及轉發(fā)測度

由文獻[14]的描述，first-order能耗模型中，傳輸k位數(shù)據(jù)包的發(fā)送能耗etx(d,k)與接收能耗erx(k)分別如下：

etx(d,k)=(eelec+eamp·dr)·k

(2)

erx(k)=eelec·k

(3)

其中，eelec為無線收發(fā)器運行開銷，eamp為傳輸開銷，d為傳輸距離，r為信道衰減指數(shù)。

在GEOR協(xié)議中，節(jié)點傳輸單個數(shù)據(jù)包的能量消耗主要包括發(fā)送能耗etx與接收數(shù)據(jù)的能耗erx.即節(jié)點的剩余能量RE(residual energy,RE)可表示為：

RE=E0-etx-erx

(4)

其中，E0表示節(jié)點初始能量。可以看出，節(jié)點接收或發(fā)送固定大小的數(shù)據(jù)包，其能量消耗值是一定的。

為了弱化節(jié)點間固有距離對其轉發(fā)機會的影響，同時使源節(jié)點能夠以較小的跳數(shù)傳遞數(shù)據(jù)到目的節(jié)點，避免忽略能量過多的節(jié)點，本文提出了一種新的路由測度。以下給出節(jié)點剩余能量與任一節(jié)點到目的節(jié)點的距離比值(Residual Energy Distance Ratio)：

(5)

其中，α,β是調節(jié)因子，根據(jù)網(wǎng)絡密度的大小及節(jié)點間最小間隔距離來設置相應的值。網(wǎng)絡密度大，β取值較大，節(jié)點最小間隔距離越大，α的取值越大，反之距離越小，α的取值也相應減小。從式(5)中可以看出，節(jié)點的剩余能量越大，越靠近目的節(jié)點，則其RED就越大。

本文將節(jié)點的RED值作為路由的測度，根據(jù)其大小進行候選集的選取并對節(jié)點進行優(yōu)先級排列。

2.2 GEOR協(xié)議的候選集選擇算法

此路由協(xié)議中將節(jié)點的RED值作為路由測度，根據(jù)該值進行候選節(jié)點集的選取并對節(jié)點進行優(yōu)先級的排列。以下是GEOR路由協(xié)議的工作原理：

(1) 信息獲取階段。節(jié)點通過一次全網(wǎng)廣播，即可獲知任意節(jié)點的位置信息；

(2) 候選集選取階段。比較源節(jié)點與鄰節(jié)點的測度值RED大小，將RED值大于源節(jié)點的鄰節(jié)點加入候選轉發(fā)集中，(候選集的大小不超過最大值Maxsize)并依照RED值大小對節(jié)點進行優(yōu)先級排序；

(3) 數(shù)據(jù)發(fā)送階段。源節(jié)點S向候選集中的節(jié)點發(fā)送單個數(shù)據(jù)包，接收到數(shù)據(jù)包且優(yōu)先級最高的那個節(jié)點作為下一跳轉發(fā)節(jié)點。以此循環(huán)，當目的節(jié)點接收到數(shù)據(jù)包時，數(shù)據(jù)發(fā)送結束。

定義如下符號：Fs表示源節(jié)點S的候選集；neighbor是鄰居節(jié)點集；Vi表示鄰居節(jié)點；REDVi表示節(jié)點Vi的路由測度；size_Fs表示候選集節(jié)點數(shù)量大小；Maxsize表示候選集中最大的節(jié)點數(shù)。

候選集選擇算法偽代碼如下：

setFS←φ

forVi∈neighbor

descendant order byREDVi

ifREDVi>REDS

FS←FS∪Vi

ifsize_Fs>Maxsize

returnFs

end if

end if

2.3 參數(shù)α,β的取值描述

在選取α,β值時，應滿足如下條件：

0<α

(6)

0<β

(7)

其中，Maxdis表示網(wǎng)絡中節(jié)點間最大間隔距離，取α,β為整數(shù)。

考慮到不同的網(wǎng)絡背景下，網(wǎng)絡密度與節(jié)點間隔距離都會影響對參數(shù)值的選取，在此，為了獲得合適的參數(shù)值，本文通過多次實驗，比較了在不同的參數(shù)值下，整個網(wǎng)絡生命周期的長短，選取網(wǎng)絡生命周期最大時相應的α,β值。

具體算法如下：

r←0 //網(wǎng)絡生命周期r初值為0

for allα

for allβ

equation(5)←(α,β) //將參數(shù)α與β帶入式(5)

get bestr//運行程序得到本次實驗bestr

if bestr>r

r←best

else

r←r

end

whileris biggest

returnα,β

end while

2.4 節(jié)點通信范圍算法

在數(shù)據(jù)傳輸后期，隨著節(jié)點能量的消耗，節(jié)點間的能量分布開始表現(xiàn)出不均衡性。若仍然使用初始的固定功率，保持相同的通訊范圍，可能存在以下問題：當保持節(jié)點通信范圍不變時，發(fā)送節(jié)點的剩余能量可能已經(jīng)不足以支持傳輸數(shù)據(jù)所要消耗的能量，從而造成節(jié)點死亡。但是如果縮小節(jié)點的傳輸范圍，能更好的避免過早出現(xiàn)第一個死亡節(jié)點。雖然這也加重了整個數(shù)據(jù)傳輸過程中的能耗，但發(fā)送信息附近的節(jié)點有了更多的轉發(fā)機會。下面通過一個簡單的實例進行說明，假設節(jié)點A的通信范圍為10 m，傳輸一個數(shù)據(jù)包到10 m遠所消耗的能量為0.5 J，經(jīng)過一段時間的數(shù)據(jù)傳輸后，節(jié)點A的剩余能量為0.5 J，即如若保持節(jié)點A的通信范圍不變，那節(jié)點A再進行一次數(shù)據(jù)傳輸后就會死亡。但是，若將節(jié)點A的通信范圍變小，不僅滿足了自身發(fā)送數(shù)據(jù)所要消耗的能量，也增大了鄰居節(jié)點轉發(fā)數(shù)據(jù)的機會，這樣能更好的延長網(wǎng)絡生命周期。

通過以上描述，適當改變節(jié)點通訊范圍更加充分考慮了節(jié)點剩余能量的運用。這里，假設通訊范圍為10 m的節(jié)點，最遠可進行三跳將數(shù)據(jù)傳遞到目的節(jié)點。那么，通過逐級遞減其跳數(shù)來控制節(jié)點的通信范圍。本文會通過第3小結的實驗來檢測該節(jié)點通信范圍算法的優(yōu)劣。

具體算法為：

while 0

do=do-Mindis

Et←newEt

ifREi>newEt

return do

else

do=do-Mindis

Et←newEt

End

End

上述算法各個符號含義如表1：

表1 符號
Tab.1 Notations

符號含義REi節(jié)點i的剩余能量Et傳輸范圍為do時節(jié)點發(fā)送數(shù)據(jù)所消耗的能量do節(jié)點傳輸范圍Mindis節(jié)點間最小間隔距離

3 實驗仿真及結果分析

將GEOR路由協(xié)議算法在MATLAB下進行仿真評估。與經(jīng)典的路由協(xié)議ExOR及以能耗為目的的路由協(xié)議PLOR進行比較。

3.1 參數(shù)設置

仿真實驗中，采用Shadowing模型反映無線信道多徑衰落的特征，參照距離記為1 m，陰影方差記為4，路徑損耗系數(shù)記為2，節(jié)點傳輸范圍15 m.無線傳感器網(wǎng)絡節(jié)點有序排列在大小為45*45區(qū)間內，節(jié)點橫坐標范圍[20，62]，縱坐標范圍[20，62]，節(jié)點間最小間隔距離Mindis為3 m，共部署了225個節(jié)點，目的節(jié)點位于坐標(65，41)處，節(jié)點初始能量為1J，目的節(jié)點能量不設限，參數(shù)α,β取值分別為10，3.數(shù)據(jù)包大小為512bytes，采用802.11MAC協(xié)議，最大傳輸率是250 kb/s，仿真時間以第一個死亡節(jié)點為準。

實驗結果以網(wǎng)絡生存周期及節(jié)點能量均衡性作為評估標準，定義評價指標如下：

(1) 網(wǎng)絡生存周期：以出現(xiàn)第一個死亡節(jié)點為標準，評估整個網(wǎng)絡成功完成一次數(shù)據(jù)傳輸?shù)拇螖?shù)(源節(jié)點到目的節(jié)點成功完成一次數(shù)據(jù)傳輸記為一次循環(huán)r)；

(2) 節(jié)點能耗均衡性：第一個節(jié)點死亡時，用網(wǎng)絡節(jié)點剩余能量的分布和方差來反應其均衡性。

3.2 實驗結果分析

(1) 網(wǎng)絡生命周期的比較。三種路由協(xié)議網(wǎng)絡生命周期的試驗比較結果如圖3.從圖中可以得知，路由協(xié)議ExOR最先出現(xiàn)死亡節(jié)點，PLOR協(xié)議次之，路由協(xié)議GEOR出現(xiàn)第一個死亡節(jié)點時的傳輸次數(shù)更長。結果表明，GEOR的網(wǎng)絡生命周期得到了有效的提高。觀察圖3也可以看出，ExOR協(xié)議雖然第一個節(jié)點死亡時間較早，但并沒有影響其整體傳輸數(shù)據(jù)的次數(shù)；而PLOR在220次數(shù)據(jù)傳輸后，出現(xiàn)大批節(jié)點死亡的情況，這是由于節(jié)點能量均衡性較好，在數(shù)據(jù)傳輸后期，多數(shù)節(jié)點都已瀕臨死亡，但其整體的數(shù)據(jù)傳輸次數(shù)沒有ExOR表現(xiàn)的好。本文提出的路由協(xié)議GEOR不僅有效延長了網(wǎng)絡生命周期，也表現(xiàn)出較好的成功傳輸數(shù)據(jù)的性能。

圖3 網(wǎng)絡節(jié)點死亡個數(shù)
Fig.3 Number of died of network nodes

(2) 節(jié)點能耗均衡性的比較。如下圖4描繪了網(wǎng)絡中出現(xiàn)第一個節(jié)點死亡時，各個節(jié)點剩余能量的分布情況，以此來表明網(wǎng)絡節(jié)點能量均衡性問題。由圖4可知，GEOR表現(xiàn)出更好的均衡性。通過計算獲知ExOR，PLOR及GEOR的節(jié)點剩余能量平均值分別為0.96 J，0.34 J，0.07 J，方差分別為0.005 7,0.013 1，0.000 8.雖然ExOR方差較小，但從圖4 可以看出，有一部分節(jié)點剩余能量為1 J，其未進行過數(shù)據(jù)傳輸，而目的節(jié)點附近節(jié)點的能量消耗過多。相比于PLOR協(xié)議，GEOR的能耗均衡性表現(xiàn)的更好。

圖4 剩余能量分布
Fig.4 Distribution of residual energy

(3) 節(jié)點通信范圍算法的實驗仿真結果。在其余實驗參數(shù)設置相同的情況下，將未使用本文節(jié)點通信范圍算法的實驗記為a，使用本文算法的實驗記為b.圖5描述了節(jié)點通信范圍算法使用前后，網(wǎng)絡生命周期的情況。從圖中可以看出，實驗a較早出現(xiàn)第一個死亡節(jié)點，實驗b的網(wǎng)絡生命周期有小幅度的提高，整體傳輸數(shù)據(jù)的次數(shù)相差不多。

圖5 實驗a，b死亡節(jié)點個數(shù)
Fig.5 Number of died nodes in the test a and b

4 結束語

針對無線網(wǎng)狀網(wǎng)的網(wǎng)絡特征，本文設計了一種新的路由協(xié)議GEOR.該協(xié)議結合節(jié)點剩余能量和位置信息，給出一種新的路由測度，并設計了一種新的節(jié)點通訊范圍算法。實驗結果表明：協(xié)議GEOR較好的延長了網(wǎng)絡生命周期，實現(xiàn)了節(jié)點能量的均衡消耗。但在參數(shù)α,β的取值研究上無形加重了實驗的負擔，還有所欠缺。下一步工作中期望結合智能優(yōu)化算法來改善參數(shù)值的選取。