一種適用于凹陷型山地地形的無線傳感器網(wǎng)絡(luò)路由算法

張彥虎，鄢麗娟，孔淑梅

(廣東松山職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系，廣東 韶關(guān) 512126)

0 引 言

隨著科技的進(jìn)步和無線網(wǎng)絡(luò)技術(shù)的發(fā)展，無線傳感器節(jié)點(diǎn)的應(yīng)用范圍越來越廣[1-3]，有時(shí)因?yàn)楸O(jiān)控環(huán)境或科研需要，需將無線傳感器節(jié)點(diǎn)分布在各種復(fù)雜的山地地形去探測所需信息，如森林火災(zāi)、氣溫、降雨等自然狀況的監(jiān)測信息，這種狀況下，無線傳感器節(jié)點(diǎn)被分布在比較廣闊的區(qū)域，其特點(diǎn)是分布面積較廣、地形高低起伏不一、信號比較容易受障礙物的遮擋而減弱，因此無線傳感器網(wǎng)絡(luò)中各個節(jié)點(diǎn)的能量損耗相對平面無線網(wǎng)絡(luò)而言有所增加，造成無限傳感器節(jié)點(diǎn)能量容易消耗殆盡[4-5]。

本文著力于山地地形的特點(diǎn)，結(jié)合LEACH協(xié)議算法，對凹陷型山地地形進(jìn)行研究與分析，探索一種能減緩無線傳感器節(jié)點(diǎn)在高低起伏地形中各網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗速度的路由算法。

WSN路由協(xié)議分為平面、層次2種路由協(xié)議。平面路由協(xié)議一般適用于小規(guī)模網(wǎng)絡(luò)；另外一種層次路由協(xié)議也稱為分簇路由協(xié)議，其以簇頭為核心，周邊的普通傳感器將信息傳送至簇頭節(jié)點(diǎn)，由簇頭節(jié)點(diǎn)對其所收集的簇成員節(jié)點(diǎn)信息進(jìn)行數(shù)據(jù)融合，通過一跳或者多跳的方式傳送給基站[6]。分簇路由協(xié)議中最具代表性的一種協(xié)議是LEACH協(xié)議，許多學(xué)者在其基礎(chǔ)上進(jìn)行了多方面的優(yōu)化及改進(jìn)，如黃利曉等人[7]提出的LEACH-improved協(xié)議；葉繼華等人[8]提出了LEACH改進(jìn)協(xié)議——可變通信周期策略的能量均衡成簇協(xié)議ACPSEB-LEACH；鄢麗娟等人[9]提出了一種基于剩余能量進(jìn)行簇頭選舉的算法；張文柱等人[10]提出了一種基于梯度的異構(gòu)WSNs非均勻分簇路由協(xié)議(GUCRP)；余修武等人[11]提出了基于罰函數(shù)和水波優(yōu)化的無線傳感器網(wǎng)絡(luò)(WSN)定位算法；吳意樂等人[12]提出了一種基于改進(jìn)遺傳模擬退火算法(SAGA)的WSN路徑優(yōu)化算法；彭蕾等人[13]提出了一種適用大規(guī)模網(wǎng)絡(luò)的基于LEACH算法的混合無線傳感網(wǎng)絡(luò)節(jié)能路由算法；胡中棟等人[14]提出了一種基于最優(yōu)分簇的能量異構(gòu)無線傳感器網(wǎng)絡(luò)路由協(xié)議OCRP。文獻(xiàn)[15-21]從各個不同方向提出了無線傳感器的各類改進(jìn)算法；本文在深入分析LEACH分簇算法基礎(chǔ)上提出一種基于平均剩余能量產(chǎn)生簇頭且優(yōu)化節(jié)點(diǎn)信息傳輸方向的分簇路由協(xié)議。

1 相關(guān)模型

1.1 地形模型

橢圓拋物面數(shù)學(xué)模型方程定義為：

(1)

由橢圓拋物面來近似模擬山頭地形，其中h代表山頭高度，p、q分別是調(diào)整山頭表面形狀的因子。為方便研究，設(shè)p=q。則橢圓拋物面方程為：

x2+y2=p2(h-z)

(2)

圖1所示為橢圓面模擬凹形山區(qū)地形。

圖1 橢圓面模擬凹形山區(qū)地形

1.2 能量消耗模型

本文采用文獻(xiàn)[22]所述的無線通信能量消耗模型，將節(jié)點(diǎn)能耗按照能量消耗的功能分為3個部分，分別為：發(fā)送信息、接收信息、數(shù)據(jù)融合等操作產(chǎn)生的能量消耗。該模型如圖2所示。

圖2 無線電通信模型

根據(jù)無線電通信模型的特點(diǎn)，當(dāng)信號的傳輸距離d小于閾值dt，節(jié)點(diǎn)能量消耗與傳輸距離d的平方成線性相關(guān)；否則，能耗與間距d的四次方成正比關(guān)聯(lián)。εfs、εmp為以上2種模型下功率放大器的能量參數(shù)[23]。閾值dt的計(jì)算過程為：

(3)

當(dāng)傳輸距離為d，傳感器發(fā)送kbit信息所需要消耗的能量為ET(k,d)，其計(jì)算公式為：

ET(k,d)=ET-elec(k)+ET-amp(k,d)

(4)

式(4)中，Etx為傳感器發(fā)送1 bit信息所消耗的能耗，發(fā)送設(shè)備傳送kbit信息的能量消耗ET-elec=kEtx，ET-amp(k,d)表示如果傳輸間距為d，功率放大器發(fā)送kbit數(shù)據(jù)的能量消耗。

接收設(shè)備接收kbit信息的能量消耗Erx(k)=kErx，對大小為kbit的數(shù)據(jù)進(jìn)行融合所產(chǎn)生的能量消耗E(k)=kEda，其中Eda表示融合1 bit信息的能耗。節(jié)點(diǎn)接收kbit信息所需要的能耗為：

ER(k)=k×Eelec

(5)

式(5)中，Eelec表示發(fā)射電路的能耗，ER(k)為接收kbit信息消耗的能量。

2 改進(jìn)算法

基于LEACH算法基礎(chǔ)，結(jié)合凹陷型山區(qū)地形特點(diǎn)，本文提出一種在基站產(chǎn)生簇頭且優(yōu)化節(jié)點(diǎn)信息傳送方向使其總是向距離基站更近的簇頭發(fā)送信息的路由算法?；驹诋a(chǎn)生簇頭時(shí)，基于已獲取的全網(wǎng)絡(luò)節(jié)點(diǎn)的平均剩余能量、位置坐標(biāo)等信息，按照一定的規(guī)則產(chǎn)生簇頭，并將新產(chǎn)生的簇頭、各節(jié)點(diǎn)距離基站間距等信息向全網(wǎng)廣播。網(wǎng)絡(luò)節(jié)點(diǎn)接收到廣播信息之后，更新自己到基站距離的參數(shù)，同時(shí)檢查自己是否被設(shè)置為簇頭節(jié)點(diǎn)，并按照相關(guān)設(shè)置進(jìn)行工作模式切換；普通節(jié)點(diǎn)等待周圍簇頭節(jié)點(diǎn)發(fā)送的簇頭廣播信息，在收到的多個簇頭廣播中，選擇一個距離基站更近的簇頭節(jié)點(diǎn)入簇。

基站在產(chǎn)生簇頭的過程中，基于已獲取到的全網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)位置坐標(biāo)等信息，運(yùn)行F(x)函數(shù)產(chǎn)生新一輪的簇頭節(jié)點(diǎn)。

2.1 改進(jìn)算法描述

本文算法中，最主要的部分是簇頭的產(chǎn)生及無線網(wǎng)絡(luò)節(jié)點(diǎn)的組網(wǎng)過程，其中基站在產(chǎn)生簇頭時(shí)，將所有的規(guī)則設(shè)定在F(x)函數(shù)中并由其產(chǎn)生；節(jié)點(diǎn)的組網(wǎng)階段是在新一輪簇頭被確定，普通節(jié)點(diǎn)接收到周圍簇頭廣播之后進(jìn)行，下面對F(x)函數(shù)及網(wǎng)絡(luò)節(jié)點(diǎn)的組網(wǎng)過程展開描述。

2.1.1F(x)函數(shù)相關(guān)參數(shù)

1)最小剩余能量閾值EOvall。

為了確保下一輪被選舉簇頭節(jié)點(diǎn)的剩余能量能大于全網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量，定義全網(wǎng)平均剩余能量的運(yùn)算過程為：

(6)

式(6)中，ECi為節(jié)點(diǎn)Si的剩余能量，n為全網(wǎng)無線傳感器節(jié)點(diǎn)的數(shù)量，EAVall為全網(wǎng)節(jié)點(diǎn)平均剩余能量。

2)最優(yōu)簇頭數(shù)量Kopt。

凹陷型山區(qū)地形的節(jié)點(diǎn)布置在山區(qū)平面之上，并不是完整的空間模型，為了研究方便，通過計(jì)算凹陷型山區(qū)地形表面積的方法獲得節(jié)點(diǎn)需要覆蓋的范圍，然后通過凹陷型山區(qū)地形表面積除以一跳的距離而得到整個山區(qū)為了達(dá)到最優(yōu)能量消耗所需的簇頭數(shù)量。

凹陷型山區(qū)地形表面積的計(jì)算公式使用式(7)進(jìn)行大概估算：

S=4πR2

(7)

其中，R為山區(qū)垂直投影所產(chǎn)生區(qū)域的半徑。

Kopt=S/(πdt2)

(8)

其中，Kopt為最優(yōu)簇頭的數(shù)量，dt為式(3)所示的閾值。

3)簇頭之間的最小間距d0。

為避免簇頭扎堆出現(xiàn)在一個區(qū)域造成不必要的能量損耗，對簇頭與簇頭之間的間距做一定的限制，定義其最小間距不能小于d0，計(jì)算過程根據(jù)式(3)為：

(9)

4)節(jié)點(diǎn)到基站的距離df。

節(jié)點(diǎn)到基站間距計(jì)算公式為：

(10)

其中，基站的坐標(biāo)為O(x0,y0,z0)，節(jié)點(diǎn)A的坐標(biāo)為A(x1,y1,z1)，df為節(jié)點(diǎn)A到基站的空間距離。

2.1.2F(x)函數(shù)的計(jì)算過程

基站根據(jù)已獲取的全網(wǎng)節(jié)點(diǎn)剩余能量、各簇平均剩余能量及各節(jié)點(diǎn)位置坐標(biāo)等信息運(yùn)行F(x)函數(shù)生成簇頭集合C。

1)根據(jù)式(6)計(jì)算EAVall，根據(jù)式(7)、式(8)計(jì)算Kopt，根據(jù)式(9)計(jì)算d0；對全網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)進(jìn)行遍歷，凡是符合剩余能量大于等于EAVall的節(jié)點(diǎn)，都加入集合SO。

2)對集合SO的所有節(jié)點(diǎn)進(jìn)行遍歷，凡是節(jié)點(diǎn)到已選定的簇頭集合C(初始值為null)的所有已選簇頭的最小距離dmin小于d0，則將該節(jié)點(diǎn)加入到集合C。

3)當(dāng)集合C中節(jié)點(diǎn)數(shù)量大于等于Kopt時(shí)，結(jié)束F(x)的運(yùn)算，得到集合C，即為函數(shù)F(x)所選定的簇頭節(jié)點(diǎn)集合。

4)根據(jù)所獲悉的全網(wǎng)絡(luò)節(jié)點(diǎn)的坐標(biāo)，對節(jié)點(diǎn)到基站距離df為空的節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)到基站的間距df，并將該值同簇頭信息一同發(fā)送給全網(wǎng)絡(luò)無線節(jié)點(diǎn)，并由各節(jié)點(diǎn)完成更新。

2.2 組網(wǎng)過程

1)普通節(jié)點(diǎn)接收到全網(wǎng)廣播之后，檢查自己是否被設(shè)置為下一輪的簇頭節(jié)點(diǎn)，同時(shí)更新該節(jié)點(diǎn)到基站的距離。

2)如果節(jié)點(diǎn)被設(shè)置為下一輪的簇頭節(jié)點(diǎn)，則將工作狀態(tài)設(shè)置為簇頭模式，同時(shí)向周圍發(fā)送自己成為簇頭的廣播信息，隨廣播信息一同發(fā)送的還包括簇頭節(jié)點(diǎn)距離基站的間距。

3)其它節(jié)點(diǎn)將工作狀態(tài)設(shè)置為普通節(jié)點(diǎn)模式，并等待周圍簇頭發(fā)送的信息；當(dāng)接收到簇頭信息之后，普通節(jié)點(diǎn)優(yōu)先選擇距離基站更近的簇頭加入。

4)當(dāng)節(jié)點(diǎn)組網(wǎng)完成之后，進(jìn)入信息采集與通信階段。

3 仿真實(shí)驗(yàn)

3.1 模擬實(shí)驗(yàn)

為驗(yàn)證本文路由改進(jìn)算法的效果，使用Matlab R2016模擬仿真軟件分別對LEACH和本文算法在垂直投影面積為100×100 m2的凹陷型山區(qū)地形區(qū)域上進(jìn)行了模擬實(shí)驗(yàn)。使用模擬軟件在該區(qū)域內(nèi)隨機(jī)產(chǎn)生100個節(jié)點(diǎn)，基站位于凹陷山區(qū)地形的底端中心位置。對各對比算法分別進(jìn)行100次的實(shí)驗(yàn)，每次運(yùn)行3000輪，測試環(huán)境的參數(shù)設(shè)置如表1所示。

表1 測試環(huán)境的部分關(guān)鍵參數(shù)

3.2 結(jié)果分析

1)首個死亡節(jié)點(diǎn)對比。

通過分析得出：試驗(yàn)中，原LEACH協(xié)議首個死亡節(jié)點(diǎn)出現(xiàn)的平均輪數(shù)為34.25，即出現(xiàn)在第35輪左右，極大值為第54輪，極小值為第11輪；本文所述算法中，對100次的數(shù)據(jù)進(jìn)行分析得出，首個死亡節(jié)點(diǎn)出現(xiàn)的輪數(shù)平均值為113.77，即出現(xiàn)在第113輪，極大值為183，極小值為48。本文所述算法中首個死亡節(jié)點(diǎn)出現(xiàn)的輪數(shù)較LEACH協(xié)議晚37輪，從圖3可直觀看出，本文所述算法的首個死亡節(jié)點(diǎn)的均值要優(yōu)于LEACH協(xié)議。

(a) 首個死亡節(jié)點(diǎn)出現(xiàn)的輪數(shù)對比

(b) 實(shí)驗(yàn)過程中首個死亡節(jié)點(diǎn)的極值對比

2)成簇情況分析。

原LEACH協(xié)議簇頭布局與本文所述算法簇頭布局對比：

在原LEACH協(xié)議中，因?yàn)樵诖仡^產(chǎn)生過程中，對未做過簇頭的節(jié)點(diǎn)采用隨機(jī)方式產(chǎn)生，會出現(xiàn)若干個簇頭節(jié)點(diǎn)集中在一起扎堆的情況，如圖4(a)所示。因?yàn)榇仡^節(jié)點(diǎn)要承擔(dān)與基站的通信，其能量消耗相對而言要比普通節(jié)點(diǎn)高很多，在圖4所示的情況下，該區(qū)域分布的3個簇頭距離太近，而個別節(jié)點(diǎn)的通信距離又太遠(yuǎn)，造成全域節(jié)點(diǎn)能量消耗過快，有進(jìn)一步提升改進(jìn)的空間。

(a) LEACH協(xié)議產(chǎn)生的簇頭結(jié)果

(b) 本文算法產(chǎn)生的簇頭結(jié)果

在本文所述算法簇頭產(chǎn)生的過程中，加入了一個限定條件，即符合做簇頭條件且被系統(tǒng)選中擬產(chǎn)生的新簇頭，需要跟已經(jīng)確定為新一輪簇頭的所有節(jié)點(diǎn)做數(shù)據(jù)分析，如果該節(jié)點(diǎn)與已確定的簇頭列表中的任何一個簇頭的距離小于設(shè)定值dic，則該節(jié)點(diǎn)不能做簇頭。在這種條件下，系統(tǒng)中產(chǎn)生的所有簇頭節(jié)點(diǎn)，一定不會有若干個節(jié)點(diǎn)扎堆出現(xiàn)的情況，在一定程度上避免了過多的能量消耗，降低了全域網(wǎng)絡(luò)節(jié)點(diǎn)的能量耗損，增加了節(jié)點(diǎn)的存活時(shí)間。修正后簇頭布局及信息傳輸方向如圖4(b)所示。

3)剩余能量對比。

在對LEACH和本文所述算法所做的100次1000輪的測試中，將能被100整除輪次的剩余能量進(jìn)行記錄，然后求100次的平均值，進(jìn)行對比發(fā)現(xiàn)，相比LEACH協(xié)議，本文所述算法全域平均剩余能量要大于LEACH，存在較明顯的優(yōu)勢。

圖5 剩余能量對比圖

4 結(jié)束語

本文在經(jīng)典LEACH協(xié)議的基礎(chǔ)上，針對凹陷型山區(qū)地形的特點(diǎn)，對LEACH協(xié)議的簇頭選舉機(jī)制及節(jié)點(diǎn)對信息的傳輸方向進(jìn)行改進(jìn)，在簇頭選舉機(jī)制上，引入了全域網(wǎng)絡(luò)節(jié)點(diǎn)平均剩余能量的概念；節(jié)點(diǎn)信息傳輸過程中優(yōu)先向距離基站更近的簇頭傳輸，使整個網(wǎng)絡(luò)能量的耗散更均衡，避免了個別節(jié)點(diǎn)因能量消耗過多而過早死亡。通過使用Matlab對改進(jìn)算法與經(jīng)典LEACH協(xié)議進(jìn)行對比，結(jié)果表明，本文所述改進(jìn)算法在均衡全域節(jié)點(diǎn)能量消耗及延長網(wǎng)絡(luò)生存周期等方面具有較明顯的優(yōu)勢；本文存在的不足之處是未能更細(xì)致地為每個簇頭指定具體的傳感器節(jié)點(diǎn)，后期將以該方向?yàn)橹攸c(diǎn)開展相關(guān)研究。