Ad hoc網(wǎng)絡(luò)路由協(xié)議的節(jié)能算法

摘　要　AODV（Ad hoc on-demand distance vector）路由協(xié)議是Ad hoc網(wǎng)絡(luò)中一種具有代表性的按需路由協(xié)議，傳統(tǒng)的AODV是以“最小跳數(shù)”為參數(shù)建立和更新路由的，隨著網(wǎng)絡(luò)負(fù)荷的增加，以這種方式建立和更新路由容易引起網(wǎng)絡(luò)中部分節(jié)點(diǎn)較其他節(jié)點(diǎn)更多地參與通信，在這些節(jié)點(diǎn)發(fā)生擁塞的可能性將更大，頻率將更高，這會(huì)增加網(wǎng)絡(luò)能耗縮短網(wǎng)絡(luò)生存時(shí)間。針對(duì)這一問題，我們提出了一種通過控制擁塞對(duì)AODV進(jìn)行節(jié)能改進(jìn)的算法——Lengthen Lifetime AODV（LLAODV）。

關(guān)鍵詞　擁塞控制　生存時(shí)間　AODV　能量消耗速度

Ad hoc網(wǎng)絡(luò)是一種多跳的、自組織的網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)既是主機(jī)，又是路由器，兩個(gè)節(jié)點(diǎn)之間如果要進(jìn)行通信，而對(duì)方又不在自己的信號(hào)覆蓋范圍內(nèi)，就需要借助其他節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。路由選擇的優(yōu)劣在很大程度上影響著網(wǎng)絡(luò)的性能。由于Ad hoc網(wǎng)絡(luò)中的節(jié)點(diǎn)隨時(shí)可能移動(dòng)，并且沒有基站之類的中央控制設(shè)備與之相連，這就為設(shè)計(jì)合適的路由協(xié)議帶來了困難。

目前已針對(duì)Ad hoc網(wǎng)絡(luò)提出了許多路由協(xié)議，這些路由協(xié)議通�？煞殖苫�于路由表驅(qū)動(dòng)的路由協(xié)議和按需驅(qū)動(dòng)的路由協(xié)議。AODV（Ad hoc on-demand distance vector routing)路由協(xié)議就是一種典型的按需驅(qū)動(dòng)的路由協(xié)議。

1　AODV路由協(xié)議及其存在的問題

A0DV是基于距離向量的按需路由協(xié)議，協(xié)議由路由發(fā)現(xiàn)和路由更新兩部分組成。當(dāng)源節(jié)點(diǎn)試圖與目的節(jié)點(diǎn)通信時(shí)，源節(jié)點(diǎn)首先在路由表中查找是否存在到目的節(jié)點(diǎn)的有效路由。若無，則發(fā)起一個(gè)路由發(fā)現(xiàn)過程，源節(jié)點(diǎn)廣播路由請(qǐng)求信息RREQ（route request），RREQ中包含了目的序列號(hào)，該序列號(hào)是源路由表中所知道的目的節(jié)點(diǎn)的最新序列號(hào)，如果路由表中沒有該序列號(hào)，則將目的序列號(hào)設(shè)為0。網(wǎng)絡(luò)中的節(jié)點(diǎn)收到有效的RREQ后，將建立一條到源節(jié)點(diǎn)的反向路由表。如果收到RREQ的這個(gè)節(jié)點(diǎn)就是目的節(jié)點(diǎn)或該節(jié)點(diǎn)中存在到目的節(jié)點(diǎn)的有效路由，則將不再廣播轉(zhuǎn)發(fā)該RREQ，而產(chǎn)生相應(yīng)的路由應(yīng)答消息RREP（route reply）。節(jié)點(diǎn)產(chǎn)生RREP后，將沿已建立的反向路由將RREP發(fā)送至源節(jié)點(diǎn)。反向路徑中每個(gè)收到RREP的節(jié)點(diǎn)，將路由表中至目的節(jié)點(diǎn)的路由表項(xiàng)中的目的序列號(hào)與RREP中的目的序列號(hào)相比較，若RREP中的目的序列號(hào)更大或在目的序列號(hào)相等的情況下，RREP中包含的跳數(shù)更少，則節(jié)點(diǎn)將根據(jù)RREP對(duì)至目的節(jié)點(diǎn)的路由進(jìn)行更新。最終RREP到達(dá)源節(jié)點(diǎn)，建立從源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路由。為更新已建立的路由，每個(gè)節(jié)點(diǎn)周期地廣播發(fā)送HELLO消息，提供與相鄰節(jié)點(diǎn)的相互連接信息。HELLO消息的生存時(shí)間TTL值為1，使得該消息的傳播限于發(fā)送節(jié)點(diǎn)和相鄰節(jié)點(diǎn)間。收到HELLO消息的節(jié)點(diǎn)，將更新或新建一條至發(fā)送節(jié)點(diǎn)的路由。當(dāng)路由超期或檢測(cè)到有效路由的下一跳鏈路中斷時(shí)，節(jié)點(diǎn)將中斷的路由設(shè)為無效，經(jīng)過一段時(shí)間后將其刪除，同時(shí)產(chǎn)生路由錯(cuò)誤消息RERR（route error），通知由于鏈路中斷造成目的節(jié)點(diǎn)不可達(dá)的路徑上的其他節(jié)點(diǎn)。沿途轉(zhuǎn)發(fā)的節(jié)點(diǎn)也將對(duì)路由表進(jìn)行同樣的操作。

AODV是以“最少跳數(shù)”為參數(shù)建立和更新路由的，隨著網(wǎng)絡(luò)負(fù)荷的增加，以這種方式建立和更新路由將導(dǎo)致網(wǎng)絡(luò)中部分節(jié)點(diǎn)較其他節(jié)點(diǎn)更多地參與通信（包括報(bào)文的發(fā)起，轉(zhuǎn)發(fā)，接受，存儲(chǔ)等），在這些節(jié)點(diǎn)擁塞發(fā)生的概率將更大，頻率將更高。這會(huì)導(dǎo)致報(bào)文丟失，引起報(bào)文重傳，增加網(wǎng)絡(luò)能耗，這些通信參與程度高的節(jié)點(diǎn)將很快耗盡能量，而在Ad hoc網(wǎng)絡(luò)中節(jié)點(diǎn)多采用電池供電，許多場(chǎng)景中電池能量的補(bǔ)充或電池的更換是很困難的甚至不可能的，因此節(jié)點(diǎn)節(jié)能對(duì)延長網(wǎng)絡(luò)生存時(shí)間是至關(guān)重要的，針對(duì)上述問題，我們考慮從擁塞控制出發(fā)，對(duì)傳統(tǒng)AODV進(jìn)行改進(jìn)，從而達(dá)到一個(gè)節(jié)約網(wǎng)絡(luò)能量，延長網(wǎng)絡(luò)生存時(shí)間的目的，我們將改進(jìn)后的路由協(xié)議稱為Lengthen Lifetime AODV——LLAODV。

2　改進(jìn)方法

如前所述，一個(gè)節(jié)點(diǎn)如果較其他節(jié)點(diǎn)更多的參與了通信，那么在這一節(jié)點(diǎn)引起擁塞的可能性也更大，那我們?nèi)绾闻袛嘁粋�(gè)節(jié)點(diǎn)參與通信的多少呢？總的說來，一個(gè)節(jié)點(diǎn)的能量消耗速度較其他節(jié)點(diǎn)快，緩存器中緩存隊(duì)列較其他節(jié)點(diǎn)長則意味著這個(gè)節(jié)點(diǎn)參與通信較其他節(jié)點(diǎn)多，在此節(jié)點(diǎn)發(fā)生擁塞的可能性更大，因此我們可以考慮盡量選擇能量消耗速度慢，緩存隊(duì)列短的節(jié)點(diǎn)作為通信節(jié)點(diǎn)，這樣就起到了控制擁塞的作用，從而降低能耗延長網(wǎng)絡(luò)生存時(shí)間。接下來，我們將對(duì)我們的改進(jìn)作詳細(xì)闡述。

2.1　節(jié)點(diǎn)Ti值的計(jì)算

2.2　路由建立和更新的原則

......
......
......

3　仿真及性能評(píng)價(jià)

為了對(duì)改進(jìn)后的AODV，即LLAODV的性能作評(píng)價(jià)， 我們修改了網(wǎng)絡(luò)仿真器NS2[2]中的AODV模塊，實(shí)現(xiàn)了LLAODV，并將其與傳統(tǒng)的AODV作了比較。

3.1　仿真模型

MAC層協(xié)議采用IEEE 802.11。無線模型采用朗訊的WaveLAN，傳輸率為2Mbit/s，無線覆蓋范圍250m。無線傳播模型是Two-ray Ground模型。應(yīng)用程序流量模型是CBR。源和目的連接隨機(jī)選擇。數(shù)據(jù)包大小為每包512字節(jié)，包發(fā)送率2packet/s。為了在較短時(shí)間通過仿真對(duì)比出LLAODV和AODV的性能，我們將節(jié)點(diǎn)的初始能量設(shè)置得較小，發(fā)射功率和接受功率設(shè)置得較大，每個(gè)節(jié)點(diǎn)的初始能量設(shè)為10J，發(fā)射功率為600mW，接受功率為300mW。移動(dòng)模型使用的是矩形區(qū)域內(nèi)的Random Waypoint模型。公式（1）中T我們?nèi)≈禐?s。仿真場(chǎng)景如下：50個(gè)節(jié)點(diǎn)隨機(jī)分布在800m×800m的矩形區(qū)內(nèi)，每個(gè)節(jié)點(diǎn)隨機(jī)選擇一個(gè)速度（均勻分布在0～15m/s之間）進(jìn)行移動(dòng)，到達(dá)隨機(jī)目的地后暫停5s。仿真時(shí)間設(shè)為65s。每一個(gè)數(shù)據(jù)點(diǎn)是5次運(yùn)行結(jié)果的平均值，每次使用相同的流量模型，不同的隨機(jī)生成的移動(dòng)方案。我們將連接數(shù)分別設(shè)為5和10，目的是分別對(duì)較小和較大的負(fù)荷進(jìn)行仿真。

我們通過對(duì)比網(wǎng)絡(luò)的活躍時(shí)間來評(píng)價(jià)LLAODV的性能。

3.2　仿真結(jié)果分析

圖1比較了當(dāng)連接數(shù)為5時(shí)，應(yīng)用傳統(tǒng)AODV的網(wǎng)絡(luò)與應(yīng)用LLAODV的網(wǎng)絡(luò)隨仿真進(jìn)行死亡節(jié)點(diǎn)數(shù)的變化，可以看到，應(yīng)用傳統(tǒng)AODV的網(wǎng)絡(luò)在48s時(shí)已有30個(gè)參與通信的節(jié)點(diǎn)因能量耗盡而死亡，網(wǎng)絡(luò)也因此而不再活躍。而應(yīng)用LLAODV的網(wǎng)絡(luò)則一直存活下來至到仿真結(jié)束。

圖2中，連接數(shù)增加為10時(shí)，應(yīng)用傳統(tǒng)AODV的網(wǎng)絡(luò)在43s時(shí)已有21個(gè)參與通信的節(jié)點(diǎn)因能量耗盡而死亡，網(wǎng)絡(luò)也因此而不在活躍。而應(yīng)用LLAODV的網(wǎng)絡(luò)同一時(shí)刻死亡節(jié)點(diǎn)數(shù)明顯少于應(yīng)用AODV的網(wǎng)絡(luò)，并一直存活下來。

從仿真中我們可以看出LLAODV通過擁塞控制均衡并節(jié)省了網(wǎng)絡(luò)能耗，延長了網(wǎng)絡(luò)生存時(shí)間。而且LLAODV延長網(wǎng)絡(luò)生存時(shí)間的優(yōu)勢(shì)隨著網(wǎng)絡(luò)負(fù)荷的增加更加顯著。

4　結(jié)論

按需式路由協(xié)議由于路由開銷低而特別適用于移動(dòng)Ad hoc網(wǎng)絡(luò)，但是這些協(xié)議在最初設(shè)計(jì)時(shí)由于忽略了能量問題而使得網(wǎng)絡(luò)的連通時(shí)間受到影響。本文通過研究能量問題的數(shù)學(xué)模型，結(jié)合路由協(xié)議的實(shí)際特點(diǎn)，提出一種簡(jiǎn)單實(shí)用的節(jié)約能量策略，同時(shí)利用其思想將按需式路由協(xié)議AODV改進(jìn)成為可以節(jié)約能量的路由協(xié)議，使得網(wǎng)絡(luò)的連通時(shí)間得到了優(yōu)化，能量問題得到了解決。雖然是以AODV為例，其思想同樣也可以被用來改進(jìn)其他的按需式路由協(xié)議。

由于本網(wǎng)頁不支持圖片與公式效果，如有需要請(qǐng)參閱雜志。