一種自組織網(wǎng)絡(luò)能量平衡路由協(xié)議

引言

移動AdHoc網(wǎng)絡(luò)(MobileAdHocNetwork，MANET)是一種特殊的通信網(wǎng)絡(luò)，該網(wǎng)絡(luò)中沒有中心基站的控制。移動AdHoc網(wǎng)絡(luò)中的節(jié)點(diǎn)間以多跳的方式進(jìn)行通信。也就是說,每個(gè)節(jié)點(diǎn)本身不僅可以充當(dāng)路由器轉(zhuǎn)發(fā)數(shù)據(jù)，同時(shí)也是一個(gè)終端節(jié)點(diǎn)，可以發(fā)送或接收數(shù)據(jù)包。由于網(wǎng)絡(luò)中節(jié)點(diǎn)位置可以移動，其拓?fù)鋾粩嗟匕l(fā)生變化。在AdHoc網(wǎng)絡(luò)中，移動節(jié)點(diǎn)大多是小型便攜式設(shè)備，這些節(jié)點(diǎn)通常由電池提供動力，所以整個(gè)網(wǎng)絡(luò)是一個(gè)能量受限的系統(tǒng)。因此，在無線AdHoc網(wǎng)絡(luò)中，節(jié)能的路由協(xié)議是很重要的。

傳統(tǒng)的無線自組網(wǎng)按需平面距離矢量路由協(xié)議(AdhocOnDemandDistanceVector，AODV)傾向于選擇最小跳數(shù)的路徑。如果最小跳數(shù)的路徑總是包括相同的節(jié)點(diǎn)，那么這些節(jié)點(diǎn)的能量就會很快耗盡。當(dāng)過多的節(jié)點(diǎn)能量被耗盡時(shí)，剩下的節(jié)點(diǎn)將無法有效地進(jìn)行通信，然后整個(gè)網(wǎng)絡(luò)就很可能是分散的。因此，在能量受限的網(wǎng)絡(luò)中，如何平衡節(jié)點(diǎn)的能量消耗成為研究AODV路由協(xié)議的一個(gè)重要課題。

現(xiàn)在已有許多論文提出了各種能量均衡的方法以解決上述問題。一些文章提出了采用整個(gè)鏈路的最小平均能量或總能量作為最佳路徑選擇時(shí)的指標(biāo)。然而在這些論文中，作者并沒有考慮到對低能量節(jié)點(diǎn)的保護(hù)問題。所以都不能很好地解決上述問題，一些節(jié)點(diǎn)的能量仍然會很快耗盡。

針對以上問題，本文提出了分級能量平衡AODV路由協(xié)議(GradedEnergyBalancingAODV，GEB-AODV)。即存在GEB-AODV路由協(xié)議中，根據(jù)節(jié)點(diǎn)的剩余能量，將節(jié)點(diǎn)分為幾個(gè)等級，不同的等級有不同的成本系數(shù)。低能量的節(jié)點(diǎn)成本系數(shù)較大，相應(yīng)地，高能量的節(jié)點(diǎn)成本系數(shù)較小。目標(biāo)節(jié)點(diǎn)將優(yōu)先選擇總成本系數(shù)最小的路徑。采用GEB-AODV路由協(xié)議,整個(gè)路徑將包含更多的高能量節(jié)點(diǎn)和更少的低能量節(jié)點(diǎn)通過此方式，整個(gè)網(wǎng)絡(luò)的能量得以均衡，網(wǎng)絡(luò)的生存周期得以延長。

1AODV路由協(xié)議

AODV路由協(xié)議是一種按需路由協(xié)議。它包括路由發(fā)現(xiàn)和路由維護(hù)兩個(gè)過程。盡管它是一個(gè)成熟的無線網(wǎng)絡(luò)路由協(xié)議，但在能量受限的應(yīng)用場合仍有缺陷。

當(dāng)一個(gè)節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)發(fā)送數(shù)據(jù)包并進(jìn)行路徑選擇時(shí)，它將向鄰節(jié)點(diǎn)廣播路由請求分組(RouteRequest，RREQ)。鄰節(jié)點(diǎn)在收到RREQ請求后，將生成到源節(jié)點(diǎn)的反向路徑。然后,鄰節(jié)點(diǎn)將判斷其是否是目的節(jié)點(diǎn)，或是它有到目標(biāo)節(jié)點(diǎn)的新路徑。如果它是目標(biāo)節(jié)點(diǎn)，將以單播方式向源節(jié)點(diǎn)返回一個(gè)路由應(yīng)答分組(RouteReply，RREP)，否則它將繼續(xù)轉(zhuǎn)發(fā)RREQ。當(dāng)源節(jié)點(diǎn)接收到該RREP時(shí)，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間的路線就可以使用了。

路由維護(hù)是通過使用路由錯誤(RouteError，RERR)消息和Hello消息實(shí)現(xiàn)的?；钴S鏈路上的每個(gè)節(jié)點(diǎn)必須周期性地向其鄰節(jié)點(diǎn)廣播Hello消息，以此來檢測活躍鏈路上相鄰節(jié)點(diǎn)的連接狀況。如果某節(jié)點(diǎn)在規(guī)定的最大時(shí)間內(nèi)沒有收到相鄰節(jié)點(diǎn)的Hello消息，就認(rèn)為鏈路連接失敗。此時(shí)，該節(jié)點(diǎn)發(fā)起一次指向鄰節(jié)點(diǎn)的局部路由修復(fù)過程，如果局部路由修復(fù)失效，貝筋節(jié)點(diǎn)向源節(jié)點(diǎn)和目的節(jié)點(diǎn)發(fā)送RERR消息。當(dāng)源節(jié)點(diǎn)接收RERR包時(shí)，它將再次發(fā)起路由發(fā)現(xiàn)過程。

AODV路由協(xié)議以最小跳數(shù)作為路徑選擇的指標(biāo)，而不考慮節(jié)點(diǎn)的能量消耗問題。一些位于熱區(qū)或中央?yún)^(qū)域的中繼節(jié)點(diǎn)將被許多路線頻繁使用，這些節(jié)點(diǎn)的能量將被很快耗盡,會使得網(wǎng)絡(luò)生存期的減少，鏈接失敗的概率提高，增加系統(tǒng)的開銷以及源節(jié)點(diǎn)的發(fā)起頻率，降低了分組遞交率凱

2GEB-AODV路由協(xié)議

在GEB-AODV路由協(xié)議中，為使網(wǎng)絡(luò)的能量平衡建立一個(gè)能量分級模型。從這個(gè)模型中，能得到一個(gè)總成本系數(shù)變量，然后將這個(gè)變量添加到修訂的RREQ包結(jié)構(gòu)中。當(dāng)?shù)谝粋€(gè)RREQ數(shù)據(jù)包到達(dá)目標(biāo)節(jié)點(diǎn)時(shí)，啟動計(jì)時(shí)器（計(jì)時(shí)器的時(shí)間是事先給定的）在此期間，可能有多個(gè)RREQ數(shù)據(jù)包從相同的源節(jié)點(diǎn)到達(dá)這個(gè)目標(biāo)節(jié)點(diǎn)。然后目標(biāo)節(jié)點(diǎn)就會從這些RREQ數(shù)據(jù)包中提取有用的信息，并將其保存到RREQ存儲表（RREQ-ST）中。當(dāng)計(jì)時(shí)器計(jì)到給定的時(shí)間時(shí)，目標(biāo)節(jié)點(diǎn)就會根據(jù)RREQ-ST表格的信息，選擇總成本系數(shù)值最小的路線。2.1能量分級模型

假設(shè)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)具有相同的初始能量值E。，并設(shè)Ei是節(jié)點(diǎn)n的剩余能量。我們根據(jù)節(jié)點(diǎn)的剩余能量，把這些節(jié)點(diǎn)劃分為4個(gè)等級。不同的等級有不同的成本系數(shù)（CostCoefficients，CC）。等級劃分的方法如表1所列。

表1中，從等級1級到等級4共有四個(gè)等級。于此同時(shí),有四個(gè)相應(yīng)的能量范圍和四個(gè)相應(yīng)的成本系數(shù)。在這個(gè)模型中,ai>a2>a3并且bi<b2<b3<b4?也就是說，低能量的節(jié)點(diǎn)成本系數(shù)較大，高能量的節(jié)點(diǎn)成本系數(shù)較小。采用這種機(jī)制的優(yōu)點(diǎn)就是，可以減少低能量節(jié)點(diǎn)的使用頻率，從而起到保護(hù)低能量節(jié)點(diǎn)的作用。另一方面，可以選擇高能量節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，優(yōu)先消耗能量較大的節(jié)點(diǎn)，從而起到了使整個(gè)網(wǎng)絡(luò)能量均衡的效果。

GEB-AODV中RREQ報(bào)文結(jié)構(gòu)

GEB-AODV中RREQ報(bào)文結(jié)構(gòu)應(yīng)進(jìn)行修改。相對于AODV協(xié)議，GEB-AODV在RREQ報(bào)文的末尾增加了總成本系數(shù)（TotalCostCoefficients，TCC）。當(dāng)RREQ報(bào)文在網(wǎng)絡(luò)中傳輸時(shí)，需要不斷更新TCC字段的值，當(dāng)一個(gè)節(jié)點(diǎn)接收到RREQ包，TCC進(jìn)行更新的方法如下：。

上式中，TCCnew表示更新后的總成本系數(shù)值，TCCold表示之前的總成本系數(shù)值，CC表示當(dāng)前收到RREQ包時(shí)的成本系數(shù)值

RREQ存儲表

為了保存從目標(biāo)節(jié)點(diǎn)中提取有用的信息，為每個(gè)源節(jié)點(diǎn)建立了RREQ存儲表。RREQ存儲表應(yīng)該包含TCC的值，它可以用于路由選擇。與此同時(shí)，它還應(yīng)該包含根據(jù)所選的路線建立反向路徑所需的信息。RREQ的存儲表包括的信息包括：包計(jì)數(shù)器、源節(jié)點(diǎn)的地址、目標(biāo)節(jié)點(diǎn)的序列號、源節(jié)點(diǎn)的序列號、時(shí)間戳、跳數(shù)、標(biāo)記（用于標(biāo)記該表是否有效）以及總成本系數(shù)。

應(yīng)該注意RREQ存儲表每時(shí)都在更新。如果一個(gè)RREQ包到達(dá)目標(biāo)節(jié)點(diǎn)，就應(yīng)該從這個(gè)包中提取有用的信息，并保存到RREQ存儲表中。然后這個(gè)表的標(biāo)記必須更新為無效的,如果一個(gè)存儲表很長一段時(shí)間沒有更新，那么，這個(gè)表就應(yīng)該被刪除。

GEB-AODV協(xié)議的路由查找過程

如果一個(gè)源節(jié)點(diǎn)沒有通向目標(biāo)節(jié)點(diǎn)的有效路由，它將通過發(fā)送RREQ消息發(fā)起路由查找過程。如果一個(gè)中間節(jié)點(diǎn)接收到了RREQ消息，它會在轉(zhuǎn)發(fā)前更新TCC字段。這里更新和轉(zhuǎn)發(fā)RREQ消息的過程與AODV相同。然而中間節(jié)點(diǎn)即使有通向目標(biāo)節(jié)點(diǎn)的有效路由，也不再回復(fù)RREP消息。目標(biāo)節(jié)點(diǎn)負(fù)責(zé)所有路由應(yīng)答任務(wù)。

同AODV協(xié)議里的一樣，目標(biāo)節(jié)點(diǎn)應(yīng)該首先根據(jù)該數(shù)據(jù)包是否由其本身生成的，來判斷其是丟棄或是接收。然后目標(biāo)節(jié)點(diǎn)把從RREQ消息中提取到的有用的信息保存到RREQ存儲表中。假如這個(gè)消息是針對某個(gè)源節(jié)點(diǎn)的第一個(gè)RREQ消息（即包計(jì)數(shù)器為0的數(shù)據(jù)包），這時(shí)開啟源節(jié)點(diǎn)的定時(shí)器。同時(shí)包計(jì)數(shù)器加1。如果它不是第一個(gè)數(shù)據(jù)包，則只把包計(jì)數(shù)器加1。

當(dāng)定時(shí)器定時(shí)溢出后，目的節(jié)點(diǎn)將在RREQ存儲表中根據(jù)TCC最小的原則找到一條最優(yōu)的路由。假如有兩條以上的路由有相同的TCC，則選擇最先到達(dá)目的節(jié)點(diǎn)的路由為最佳路由。當(dāng)最佳路由找到后，可以利用這條最佳路由更新反向路由并向源節(jié)點(diǎn)發(fā)送RREP消息。此時(shí)，存儲表中關(guān)于該源節(jié)點(diǎn)備用路由變?yōu)闊o效，需要立即刪除。

3仿真和分析

本文使用NS2仿真軟件來仿真AODV以及GEB-AODV路由協(xié)議。在仿真中設(shè)置不同的移動速度;節(jié)點(diǎn)停留時(shí)間為5s；在最佳路徑選擇之前，目的節(jié)點(diǎn)定時(shí)器定時(shí)值為60ms；能量系數(shù)aw,分別為0.75、0.5、0.25；代價(jià)系數(shù)bl'bM、分別為1、2、4、8。通過這樣配置參數(shù)，成本系數(shù)將隨著剩余的能量的減少而呈指數(shù)增加，從而更好的保護(hù)剩余能量較小的節(jié)點(diǎn)，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的能量均衡。部分參數(shù)的設(shè)置如表2所列。

表2仿真參數(shù)

本文主要對能量耗盡的節(jié)點(diǎn)數(shù)、第一個(gè)節(jié)點(diǎn)的生存期、分組投遞率和平均端到端時(shí)延等性能指標(biāo)進(jìn)行了仿真分析。圖1所示是在最大移動速率為30m/s的仿真條件下得到的隨時(shí)間耗盡能量的節(jié)點(diǎn)數(shù)比較曲線。

隨著時(shí)間的推移，GEB-AODV路由協(xié)議會出現(xiàn)能量耗盡的節(jié)點(diǎn)數(shù)的增長速度較AODV相對遲緩。原因就是AODV路由協(xié)議是以最小跳數(shù)選擇路徑的，能量不均衡導(dǎo)致一些節(jié)點(diǎn)的能量過早地耗盡。而GEB-AODV路由協(xié)議是根據(jù)最小的總成本系數(shù)值進(jìn)行路徑選擇的，這種方法可以有效地保護(hù)低能量的節(jié)點(diǎn)，從而延長整個(gè)網(wǎng)絡(luò)得到生存周期。圖2所示是其分組投遞率比較曲線。

從圖2可以看到，GEB-AODV路由協(xié)議在各種移動速度下的分組投遞率都要高于AODV，這意味著GEB-AODV路由協(xié)議有更高的傳輸效率。一方面，該算法提高了路由連接的穩(wěn)定性，減少了由鏈路失敗造成的包丟失率。另一方面，由于能量均衡機(jī)制，很多的節(jié)點(diǎn)的生存期更長了，所以在仿真的后期,這些多余的節(jié)點(diǎn)能提供更可靠的數(shù)據(jù)傳輸。

圖3所示是端到端平均時(shí)延的比較。圖3表明：GEB-AODV路由協(xié)議的端到端平均時(shí)延比AODV更小。雖然GEB-AODV路由協(xié)議并不是選擇最小時(shí)延的路徑，但它，選擇的是最穩(wěn)定的路徑。這種方式可以減少鏈路失敗時(shí)，路由維護(hù)過程帶來的延時(shí)。另一方面，節(jié)點(diǎn)生存期的延長，進(jìn)一步減少了由于路由查找失敗帶來的延時(shí)。

從仿真結(jié)果可以看出，在能量受限的系統(tǒng)中，GEB-AODV路由協(xié)議能夠延長網(wǎng)絡(luò)的生存期，增大分組投遞率,同時(shí)減少端到端平均延時(shí)。

4結(jié)語

本文基于AODV路由協(xié)議，提出了分級能量平衡的路由協(xié)議。在這個(gè)協(xié)議中，能量成本系數(shù)用來平衡網(wǎng)絡(luò)的能量。在GEB-AODV路由發(fā)現(xiàn)過程中，中間節(jié)點(diǎn)計(jì)算總成本系數(shù)值,然后將其保存到修改的RREQ消息中并轉(zhuǎn)發(fā)。目標(biāo)節(jié)點(diǎn)從RREQ存儲表中選擇總成本系數(shù)值最小的路徑。NS2仿真結(jié)果表明，在能量受限的系統(tǒng)中，改進(jìn)算法較傳統(tǒng)的AODV路由協(xié)議有更好的性能。

20211221_61c1dc8a89e04__一種自組織網(wǎng)絡(luò)能量平衡路由協(xié)議