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

引言

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

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

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

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

1AODV路由協(xié)議

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

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

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

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

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

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

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

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

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

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

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

RREQ存儲表

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

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

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

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

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

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

3仿真和分析

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

表2仿真參數(shù)

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

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

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

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

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

4結(jié)語

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

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