高能量高信號強度節點優先的AODV路由協議

鄒修明

淮陰師范學院物理與電子電氣工程學院，江蘇淮安 223300

◎網絡、通信、安全◎

高能量高信號強度節點優先的AODV路由協議

鄒修明

淮陰師范學院物理與電子電氣工程學院，江蘇淮安 223300

針對AODV協議只選擇具有最少跳數路由，而不考慮節點能量即將耗盡或節點即將離開鄰節點傳送范圍，造成路由頻繁中斷的問題，提出新的改進方案，在路由發現階段，選擇能量較高和信號強度較強的節點作為路由節點，在路由維護階段，對能量即將耗盡或即將離開鄰節點有效傳送范圍的節點進行路由備份。仿真實驗結果表明改進后的協議能夠有效增加數據包投遞率和減少平均端到端延時，并能有效減緩能耗速度，提高整個網絡的生存期。

無線自組織網絡按需距離矢量路由協議（AODV）；節點能量；信號強度

1 引言

移動自組織網絡（Mobile Ad hoc Network，MANET）是由一組無線移動節點組成，是一種不需要依靠現有固定網絡通信基礎設施的能夠迅速展開使用的網絡體系[1]。在MANET網絡中，沒有中心控制節點，所有節點的地位平等，不僅能夠進行信息處理，而且具有報文轉發功能[2]。

由于節點的移動，有線網絡中的路由協議不再適用于MANET網絡，其協議主要分為兩類：主動型和按需型[3]。主動型路由協議：其代表性的路由協議是目的序列距離矢量路由協議（Destination-Sequenced Distance-Vector，DSDV），該型路由協議參考了有線網絡中路由的生成方法，每個無線節點會周期性地廣播自己的路由表信息，各個無線節點就根據收到的信息動態更新自己的路由表[4]。其缺點是，由于進行周期性的廣播，會大量浪費寶貴的帶寬資源和節點的電池能量，如果降低廣播的頻率，又不能及時地反映網絡拓撲的變化，造成數據發送的失敗[5]。按需型路由協議：其代表性的路由協議是按需距離矢量路由協議（Ad-hoc On-demand Distance Vector，AODV），該型路由協議只在節點需要通信時，才進行廣播來獲取到達目的地的路由，對帶寬的占用相對較小，更能適應拓撲的動態變化，更加高效[6]。因此相比于DSDV，AODV更加適合具有運動節點的MANET網絡。但是也存在一定的缺點，研究人員提出了許多協議的改進方案，如：文獻[7]提出，在路由發現過程中，將鏈路中各節點信號強度最小值記錄在路由請求報文RREQ中，目的節點選擇具有最大信號強度的RREQ進行回復作為本次通信的主路由，同時，將具有次大值RREQ的鏈路作為備份路由。這種方案雖然最大限度地減少了因節點離開傳送范圍，而導致的鏈路斷裂情況，但是沒有考慮到因為節點能量的耗盡而導致的鏈路斷裂。文獻[8]在路由發現的過程中，選擇距離較近的鄰節點作為路由節點（即節點信號強度大于一定的閾值，否則不轉發RREQ請求報文），這種方法只有部分節點轉發RREQ報文，節約了寶貴的帶寬資源，而且避免了因為點離開傳送范圍，而導致的鏈路斷裂情況，但是也沒有考慮到節點能量耗盡問題。文獻[9]提出一種基于節點能量的EOAODV方法，該方法通過HELLO消息和鄰節點交互，選擇具有高能量的節點作為路由的中間節點，以最大限度地防止因為節點能量耗盡而導致的鏈路斷裂，但是沒有考慮因為節點離開傳送范圍而導致的鏈路斷裂情況。

本文在前人研究基礎之上，針對引起鏈路斷裂的兩個因素，分別在路由發現和路由維護階段進行改進優化，以提高網絡運行效果。

2 路由發現

2.1 AODV的路由發現及存在問題

在AODV路由協議中，當源節點需要和新的目的節點通信時，它就會發起路由發現過程，通過廣播RREQ報文來查找相應路由[10-11]。當這個RREQ到達目的節點本身，或者是一個擁有足夠新的到達目的節點路由的中間節點時，目的節點只對第一個到達的RREQ進行確認，回送RREP報文，建立新路由[12-13]。所謂“足夠新”是通過目的序列號來判斷的，即RREQ中，目的節點序列號大于或等于中間節點中目的節點序列號[14]。

AODV路由協議只選擇具有最少跳數的路由，而不管這條路由是否有鏈路斷裂的危險。如圖1所示，如果節點S要和節點D進行通信，那么AODV路由協議會選擇S-＞A-＞D這條路由，因為在這條路由中，跳數最少。但是節點A處于節點S和節點D有效傳送范圍的邊緣，屬于危險的節點，即節點A有可能在下一秒離開節點S和節點D，那么剛剛建立的路由就會斷裂，必須重新進行路由發現過程。相反，由于節點B和節點C分別在節點S和節點D有效傳送范圍的內部，同時也在對方的有效傳輸范圍之內，立即離開有效傳送范圍的可能性大大降低，如果采用S-＞B-＞C-＞D這條路由，那么鏈路斷裂可能性會降低很多。文獻[8]就是在這個方面對其進行了改進。

圖1 AODV的路由發現過程

如果節點A處于節點S和節點D連線的中間，且不考慮其他因素的情況下，那么S-＞A-＞D這條路由就是最佳路由。但是如果節點A的電量接近耗盡，而節點B和節點C還有很多剩余電量，那么采用S-＞B-＞C-＞D這條路由是最佳路由，因為S-＞A-＞D很快就會因為A的電量不足而斷裂。文獻[9]就是在這個方面對其進行了改進。

2.2 路由發現的改進

針對AODV路由協議在路由發現的過程中存在的問題，應該盡量避免選擇即將離開有效傳送范圍的節點和電量即將耗盡的節點作為路由的中間節點，具體算法描述如下：

步驟1規定基本電量的閾值和有效傳輸距離的閾值（通過接收報文的信號強度來判斷，信號強度越大，則距離越近，信號強度越小則距離越遠）。

步驟2在進行首次路由發現時，接收到RREQ報文的節點，檢查自己剩余的電量和信號強度是否大于相應的閾值，如果都大于閾值，則轉發RREQ報文，否則丟棄RREQ報文。

步驟3如果成功則采用該路由，如果失敗，即說明沒有符合條件的最優路由，則采用原始的AODV路由發現過程。

該算法試圖通過首次路由發現來尋找含有最少危險節點的路由。如圖1所示，如果所有節點的剩余電量都大于預先設定的閾值，在進行路由發現時，節點S廣播RREQ報文，節點A和節點B都收到了RREQ報文，其中節點A的信號強度小于預先設定的閾值，那么節點A就將RREQ報文丟棄，不再轉發，也就是將來的S到D的路由中不會含有A節點，相反B大于該閾值，那么B就可以繼續轉發該RREQ報文，最終建立S-＞B-＞C-＞D的路由。其中，剩余電量是在路由層，通過M obileNode對象的energy（）方法獲得。節點信號強度值是通過RREQ報文的txinfo_.RxPr屬性進行獲取。在TwoRayGround傳輸模型下，節點信號強度計算如公式（1）所示：其中，p為接收到的信號強度，Pt為傳輸功率，Gt為發送節點的天線增益，Gr為接收節點的天線增益，ht為發送天線的高度，hr為接收天線高度，d為兩個節點間的距離，L為系統損失因子。

3 路由維護

3.1 AODV的路由維護及存在問題

AODV路由協議在建立好路由之后，就進入路由維護階段。在路由維護階段，如果收到一個數據包，首先檢查是否有到達目的節點的活躍路由，如果存在這樣一條活躍路由，則通過該路由進行轉發。如果傳送數據失敗，則進行路由修復，如果路由修復失敗，則向上游節點發送錯誤報告RERR分組，通知所有使用該路由的節點，終止使用這條路由[15]。在AODV路由維護的過程中，只有節點完全離開鄰節點的有效傳輸范圍或者能量完全耗盡的情況下才會進行路由修復工作，影響網絡傳輸的效率。

3.2 路由維護的改進

為了提前發現路由中斷危險，及時進行路由修復，本文在路由發現階段的基礎上，通過HELLO消息對下游節點的能量值和信號強度值來進行監測，對能量值或信號強度值小于閾值的危險節點，進行路由備份，以避免路由中斷，這里的閾值要比路由發現階段的閾值小。如圖2所示。

圖2 hello消息

在圖2中，存在一條路由S-＞A-＞B-＞C-＞D，由中間節點向上游節點發送Hello消息，其中目的節點不用發送hello消息。Hello消息是廣播的，為了減少網絡開銷，本文將Hello消息的目的地址改為上游節點的地址，即由單播來實現。如節點B給節點A發送Hello消息，將TTL值改為1（即只和鄰居節點交互），將節點B中Hello消息的目的地址字段（即daddr字段）改為上游節點A的地址。由于Hello消息被封裝在hdr_aodv_reply結構體中，因此，將發送Hello消息節點的能量值，放在該結構體的保留字段（reserved字段）中。上游節點A接收到B的Hello消息后，首先查看報文的daddr字段，如果是發送給A的，則獲取下游節點B的信號強度（即Hello報文的txinfo_.RxPr屬性值）和下游節點B的能量值。如果這兩個值有任一項小于閾值，則說明該路由有中斷的危險，那么A按2.2節中路由發現的方法進行路由備份，由A重新尋找到節點D的路由。一旦節點B的能量耗盡或這節點B離開A的有效傳送距離則啟用新路由。如圖3，圖4所示。

圖3 備份路由情況1

圖4 備份路由情況2

在節點A發現節點B成危險節點后，或立即找好備份路由E-＞C-＞D或E-＞F-＞D，當節點B失效后，啟用替代路由，以提高網絡傳送效果。

4 仿真實驗及結果分析

4.1 仿真環境介紹

仿真實驗采用NS2下進行，無線電傳播模式采用TwoRay Ground，對AODV協議、EOAODV協議和本文改進的AODV協議（NAODV）的性能進行比較。在本場景中，節點以10 m/s以內的隨機速度向一個隨機的方向運動，并停留一定的時間，再向下一個隨機的方向運動。其中，停留時間為0 s，則表示節點不停地運動，如果節點停留的時間為100 s，則說明節點沒有運動。本次仿真實驗分別對停留時間為0到100 s之間，每隔5 s，進行一次對比，共進行21次對比實驗。具體參數如表1所示。

表1 實驗參數

4.2 結果分析

實驗結果如圖5～圖7所示，naodv是本文的改進協議。在圖5中的前8次實驗中，即從停留時間為0 s到停留時間為35 s的實驗中，naodv的數據包投遞率明顯高于eoaodv和原始的aodv路由協議，這是因為，節點的活動性強，節點周圍出現高能量和高信號強度節點的可能性很大，所以提升的空間也比較大，從停留40 s的那次實驗開始，三種協議的數據包投遞率越來越趨近于相同，這是由于停留的時間越長即節點的運動性越低，那么節點周圍出現高能量和高信號強度節點的可能性也就越來越小，到停留時間為100 s，即節點都停止不動時，它們的數據包投遞率和平均端到端時延也就趨近于相同了，平均端到端時延則正好相反。圖7是節點停留時間為0，即節點處于不停運動情況下的節點平均剩余能量變化情況。在圖7中，naodv的能耗速度要明顯低于eoaodv和aodv，這是因為naodv中的路由節點是采用高能量高信號強度節點作為路由節點，路由斷裂的概率要比eoaodv和aodv低，其廣播路由發現報文RREQ的次數就少，因而其能耗就少，并且隨著時間推移和路由斷裂可能性的增加，這種能耗的差距越來越明顯。

圖5 數據包投遞率對比圖

圖6 平均端到端時延對比圖

圖7 節點平均剩余能量變化對比圖

5 結束語

改進的路由協議naodv在路由發現階段選擇能量較高和信號強度較強的節點作為路由的中間節點，以盡量避免路由的中斷，在路由維護階段結合Hello消息，及時發現路由鏈路中可能即將斷裂的節點，根據路由發現的方法做好路由備份，在原有路由斷裂后，立即啟用備份路由。仿真實驗表明改進的路由協議有效地提高了數據包投遞率，降低了平均端到端時延，并能夠有效減慢整個網絡的能耗速度，起到延長網絡生存期的目的。下一步將考慮更加優化的路由改進方法，研究其對低速運動場景網絡的改進效果。

[1]陳林星，曾曦，曹毅.移動Ad Hoc網絡：自組織分組無線網絡技術[M].北京：電子工業出版社，2006：4-5.

[2]周鵬.移動Ad Hoc網快速自適應后備路由協議[J].計算機工程與應用，2012，48（23）：21-26.

[3]Qutaiba R，Ahmed B，Mohamed G，et al.Extensive simulation performance analysis for DSDV，DSR and AODV MANET routing protocols[C]//IEEE International Conference on Advanced Information Networking and Applications Workshops，2013：335-342.

[4]劉洛琨，張遠，許家棟.AODV與DSDV路由協議性能仿真與比較[J].計算機仿真，2008，23（2）：118-120.

[5]王立新，趙元慶，谷川.W IA-PA中基于DSDV的多路徑路由協議研究[J].計算機工程與設計，2011，32（10）：3338-3341.

[6]王琦進，侯整風.一種節點低能量避免的AODV改進協議[J].合肥工業大學學報：自然科學版，2013，36（4）：431-434.

[7]Wang S Y，Liu J Y，Huang C C，et al.Signal strengthbased routing protocol for mobile ad hoc networks[C]//IEEE International Conference on Advanced Information Networking and Applications，2005：17-20.

[8]Hemant D，Rachit J，Rinkoo B.Route selection in MANETs by intelligent AODV[C]//IEEE International Conference on Communication Systems and Network Technologies，2013：332-335.

[9]Gouda B S，Panigrahi P P，Choudhury A.A new optimal approach for improving energy efficiency in wireless ad-hoc networks[C]//IEEE Conference on Information and Communication Technologies，2013：1095-1100.

[10]張鵬，趙季紅，曲樺.基于鏈路故障的MANET本地修復技術[J].計算機工程，2010（1）：94-95.

[11]Vanaparthi R，Pmgati G.Routing protocols to entice security in MANETS[J].Global Journal of Computer Science and Technology，2011，11（13）

[12]Manikandan S P，Manimegalai R.Survey on mobile Ad Hoc network attacks and mitigation using muting protocols[J].Amcrican Journal of Applied Sciences，2012，9（11）：1796-1801.

[13]周杰.基于AODV的Ad Hoc網絡多路徑路由協議[J].長春工業大學學報：自然科學版，2012，33（4）：451-455.

[14]陳永輝，劉志勤，Nagasaka，等.基于節點能量和網絡穩定性的節能路由協議[J].計算機工程與應用，2010，46（21）：79-81.

[15]周少瓊，徐櫛，姜麗，等.蟻群優化算法在ad hoe網絡路由中的應用[J].計算機應用，2011，33（2）：332-334.

ZOU Xium ing

School of Physics and Electronic Electrical Engineering, Huaiyin Normal University, Huai’an, Jiangsu 223300, China

AODV routing protocol only selects the route with least number of hops, without considering the node energy depletion or being about to leave the transmission range of it’s neighbor node, it often results in routing fracture frequently. In order to solve this problem, a new scheme is improved. In the route discovery phase, the node which has greater energy and greater signal strength is selected. In the routing maintenance phase, routing backup is done when the node energy being about to run out or leaving the effective transmission range. Simulation results show that the improved routing protocol can increase the packet delivery ratio, reduce the average end to end delay and energy consumption rate, enhance survival time of the entire network.

Ad hoc On-demand Distance Vector routing（AODV）; node energy; signal strength

ZOU Xiuming. AODV routing protocol of greater energy and signal strength node first. Computer Engineering and Applications, 2014, 50（17）：86-89.

A

TP393.01

10.3778/j.issn.1002-8331.1310-0158

江蘇省淮安市科技支撐計劃（工業）項目（No.HASZ2012030）。

鄒修明（1968—），男，博士研究生，副教授，主要研究領域為網絡安全、模式識別、生物信息學。E-mail：brightzou@126.com

2013-10-15

2014-01-16

1002-8331（2014）17-0086-04

CNKI網絡優先出版：2014-03-12,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1310-0158.htm l