摘 要 AODV(Ad hoc on-demand distance vector)路由協(xié)議是Ad hoc網絡中一種具有代表性的按需路由協(xié)議,傳統(tǒng)的AODV是以“最小跳數(shù)”為參數(shù)建立和更新路由的,隨著網絡負荷的增加,以這種方式建立和更新路由容易引起網絡中部分節(jié)點較其他節(jié)點更多地參與通信,在這些節(jié)點發(fā)生擁塞的可能性將更大,頻率將更高,這會增加網絡能耗縮短網絡生存時間。針對這一問題,我們提出了一種通過控制擁塞對AODV進行節(jié)能改進的算法——Lengthen Lifetime AODV(LLAODV)。
關鍵詞 擁塞控制 生存時間 AODV 能量消耗速度
Ad hoc網絡是一種多跳的、自組織的網絡,每個節(jié)點既是主機,又是路由器,兩個節(jié)點之間如果要進行通信,而對方又不在自己的信號覆蓋范圍內,就需要借助其他節(jié)點進行轉發(fā)。路由選擇的優(yōu)劣在很大程度上影響著網絡的性能。由于Ad hoc網絡中的節(jié)點隨時可能移動,并且沒有基站之類的中央控制設備與之相連,這就為設計合適的路由協(xié)議帶來了困難。
目前已針對Ad hoc網絡提出了許多路由協(xié)議,這些路由協(xié)議通?煞殖苫诼酚杀眚寗拥穆酚蓞f(xié)議和按需驅動的路由協(xié)議。AODV(Ad hoc on-demand distance vector routing)路由協(xié)議就是一種典型的按需驅動的路由協(xié)議。
1 AODV路由協(xié)議及其存在的問題
A0DV是基于距離向量的按需路由協(xié)議,協(xié)議由路由發(fā)現(xiàn)和路由更新兩部分組成。當源節(jié)點試圖與目的節(jié)點通信時,源節(jié)點首先在路由表中查找是否存在到目的節(jié)點的有效路由。若無,則發(fā)起一個路由發(fā)現(xiàn)過程,源節(jié)點廣播路由請求信息RREQ(route request),RREQ中包含了目的序列號,該序列號是源路由表中所知道的目的節(jié)點的最新序列號,如果路由表中沒有該序列號,則將目的序列號設為0。網絡中的節(jié)點收到有效的RREQ后,將建立一條到源節(jié)點的反向路由表。如果收到RREQ的這個節(jié)點就是目的節(jié)點或該節(jié)點中存在到目的節(jié)點的有效路由,則將不再廣播轉發(fā)該RREQ,而產生相應的路由應答消息RREP(route reply)。節(jié)點產生RREP后,將沿已建立的反向路由將RREP發(fā)送至源節(jié)點。反向路徑中每個收到RREP的節(jié)點,將路由表中至目的節(jié)點的路由表項中的目的序列號與RREP中的目的序列號相比較,若RREP中的目的序列號更大或在目的序列號相等的情況下,RREP中包含的跳數(shù)更少,則節(jié)點將根據RREP對至目的節(jié)點的路由進行更新。最終RREP到達源節(jié)點,建立從源節(jié)點至目的節(jié)點的路由。為更新已建立的路由,每個節(jié)點周期地廣播發(fā)送HELLO消息,提供與相鄰節(jié)點的相互連接信息。HELLO消息的生存時間TTL值為1,使得該消息的傳播限于發(fā)送節(jié)點和相鄰節(jié)點間。收到HELLO消息的節(jié)點,將更新或新建一條至發(fā)送節(jié)點的路由。當路由超期或檢測到有效路由的下一跳鏈路中斷時,節(jié)點將中斷的路由設為無效,經過一段時間后將其刪除,同時產生路由錯誤消息RERR(route error),通知由于鏈路中斷造成目的節(jié)點不可達的路徑上的其他節(jié)點。沿途轉發(fā)的節(jié)點也將對路由表進行同樣的操作。
AODV是以“最少跳數(shù)”為參數(shù)建立和更新路由的,隨著網絡負荷的增加,以這種方式建立和更新路由將導致網絡中部分節(jié)點較其他節(jié)點更多地參與通信(包括報文的發(fā)起,轉發(fā),接受,存儲等),在這些節(jié)點擁塞發(fā)生的概率將更大,頻率將更高。這會導致報文丟失,引起報文重傳,增加網絡能耗,這些通信參與程度高的節(jié)點將很快耗盡能量,而在Ad hoc網絡中節(jié)點多采用電池供電,許多場景中電池能量的補充或電池的更換是很困難的甚至不可能的,因此節(jié)點節(jié)能對延長網絡生存時間是至關重要的,針對上述問題,我們考慮從擁塞控制出發(fā),對傳統(tǒng)AODV進行改進,從而達到一個節(jié)約網絡能量,延長網絡生存時間的目的,我們將改進后的路由協(xié)議稱為Lengthen Lifetime AODV——LLAODV。
2 改進方法
如前所述,一個節(jié)點如果較其他節(jié)點更多的參與了通信,那么在這一節(jié)點引起擁塞的可能性也更大,那我們如何判斷一個節(jié)點參與通信的多少呢?總的說來,一個節(jié)點的能量消耗速度較其他節(jié)點快,緩存器中緩存隊列較其他節(jié)點長則意味著這個節(jié)點參與通信較其他節(jié)點多,在此節(jié)點發(fā)生擁塞的可能性更大,因此我們可以考慮盡量選擇能量消耗速度慢,緩存隊列短的節(jié)點作為通信節(jié)點,這樣就起到了控制擁塞的作用,從而降低能耗延長網絡生存時間。接下來,我們將對我們的改進作詳細闡述。
2.1 節(jié)點Ti值的計算
2.2 路由建立和更新的原則
......
......
......
3 仿真及性能評價
為了對改進后的AODV,即LLAODV的性能作評價, 我們修改了網絡仿真器NS2[2]中的AODV模塊,實現(xiàn)了LLAODV,并將其與傳統(tǒng)的AODV作了比較。
3.1 仿真模型
MAC層協(xié)議采用IEEE 802.11。無線模型采用朗訊的WaveLAN,傳輸率為2Mbit/s,無線覆蓋范圍250m。無線傳播模型是Two-ray Ground模型。應用程序流量模型是CBR。源和目的連接隨機選擇。數(shù)據包大小為每包512字節(jié),包發(fā)送率2packet/s。為了在較短時間通過仿真對比出LLAODV和AODV的性能,我們將節(jié)點的初始能量設置得較小,發(fā)射功率和接受功率設置得較大,每個節(jié)點的初始能量設為10J,發(fā)射功率為600mW,接受功率為300mW。移動模型使用的是矩形區(qū)域內的Random Waypoint模型。公式(1)中T我們取值為5s。仿真場景如下:50個節(jié)點隨機分布在800m×800m的矩形區(qū)內,每個節(jié)點隨機選擇一個速度(均勻分布在0~15m/s之間)進行移動,到達隨機目的地后暫停5s。仿真時間設為65s。每一個數(shù)據點是5次運行結果的平均值,每次使用相同的流量模型,不同的隨機生成的移動方案。我們將連接數(shù)分別設為5和10,目的是分別對較小和較大的負荷進行仿真。
我們通過對比網絡的活躍時間來評價LLAODV的性能。
3.2 仿真結果分析
圖1比較了當連接數(shù)為5時,應用傳統(tǒng)AODV的網絡與應用LLAODV的網絡隨仿真進行死亡節(jié)點數(shù)的變化,可以看到,應用傳統(tǒng)AODV的網絡在48s時已有30個參與通信的節(jié)點因能量耗盡而死亡,網絡也因此而不再活躍。而應用LLAODV的網絡則一直存活下來至到仿真結束。
圖2中,連接數(shù)增加為10時,應用傳統(tǒng)AODV的網絡在43s時已有21個參與通信的節(jié)點因能量耗盡而死亡,網絡也因此而不在活躍。而應用LLAODV的網絡同一時刻死亡節(jié)點數(shù)明顯少于應用AODV的網絡,并一直存活下來。
從仿真中我們可以看出LLAODV通過擁塞控制均衡并節(jié)省了網絡能耗,延長了網絡生存時間。而且LLAODV延長網絡生存時間的優(yōu)勢隨著網絡負荷的增加更加顯著。
4 結論
按需式路由協(xié)議由于路由開銷低而特別適用于移動Ad hoc網絡,但是這些協(xié)議在最初設計時由于忽略了能量問題而使得網絡的連通時間受到影響。本文通過研究能量問題的數(shù)學模型,結合路由協(xié)議的實際特點,提出一種簡單實用的節(jié)約能量策略,同時利用其思想將按需式路由協(xié)議AODV改進成為可以節(jié)約能量的路由協(xié)議,使得網絡的連通時間得到了優(yōu)化,能量問題得到了解決。雖然是以AODV為例,其思想同樣也可以被用來改進其他的按需式路由協(xié)議。
由于本網頁不支持圖片與公式效果,如有需要請參閱雜志。