AOMDV多路徑協議的研究和改進

李子璇　童孟軍　江浩然

摘 要： 由于WSN網絡中每個節點的能量都是有限的，并且很難對電池充電再使用，所以能量就成為衡量一個網絡好壞的關鍵因素。針對節點間通信問題，傳統的AOMDV協議僅僅考慮了時延最短因素，常常導致某些節點局部死亡，甚至會導致整個網絡被分割。為此，提出一種新的協議RED-AOMDV，會考慮端到端時延的因素，會根據每條路徑的最大剩余能量來選擇最優路徑。改進協議綜合考慮每個節點中的能量值和時延，讓已有的多路徑均衡地承擔轉發數據的任務。實驗結果表明，改進協議在節點能耗、投遞率和網絡生命周期等方面都較之前的協議有了較大的提高。

關鍵詞： 多路徑協議； 節點能耗； 最優路徑； 時延

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2016）08-07-06

Abstract： Since the energy of each node in WSN network is limited， and it is difficult to recharge the battery， so the energy becomes a key factor to measure the network performance. For inter-node communication problems， the traditional AOMDV（Ad hoc On-demand Multipath Distance Vector Routing） protocol considers only the shortest delay， which often leads some nodes to the local death， or even causes the entire network to be divided into many small networks. This paper proposes a new protocol RED-AOMDV， will consider the end to end delay factors， and will choose the optimal path according to the maximum residual energy of each path. The improved protocol considers the energy value and delay of each node to allow the data forwarding in between the existing multiple paths in a balanced way. The experimental results show that the proposed protocol has been greatly improved in terms of energy consumption， delivery ratio and network lifetime.

Key words： multipath protocol； the energy consumption of nodes； optimal path； delay

0 引言

在WSN中，節點扮演一個路由器的角色。這樣的網絡具有以下特點：拓撲易變化、帶寬約束、能源受限，而且易出現安全問題。鑒于以上情況，路由將會是WSN中一個很重要的問題。

每個參與路由維護和數據轉發的節點都支持端到端通信。這些節點通常是小電池供電的設備，能夠感測、存儲、數據處理以及通過無線電節點與其他節點通信。在許多應用領域中，想要為節點充電或者是更換電池是不切實際的，因此網絡能量效率最大化是設計節點的關鍵所在。

最初的路由協議使用跳步數作為主要指標參數[1-2]，但延遲往往間接影響路由選擇[1]。更多新的協議使用一些其他的度量值，比如信號強度[3]、網絡穩定性[4]和負載均衡[5-6]，這些新的度量值都會影響性能并且間接的消耗能源。能量也可以用于作為路由選擇路徑的一個參考標準，通過它可以最大程度地降低能源消耗或者避免選擇那些即將因為能源不足而死亡的節點。設計路由協議最大的挑戰就是能源的有限使用率。相比有線網絡，無線網絡中能源的有限性是顯而易見的。節能通信是提高WSN的生命周期的關鍵所在。

之前Radhika等[7]已經提出了一種基于AODV（Ad hoc on-demand distance vector routing）的能量感知路由協議，通過所有節點的最小剩余能量來確定一條最優的路徑。該協議綜合考慮了跳步數和能耗兩個方面。Soo-Bum Kim等[8]在AOMDV基礎上評估了能量感知的性能[9]。

在AODVEA（AODV Energy Aware）協議中，將會選擇路由的最小剩余能量作為度量值。擁有最小剩余能量的節點被標記出來，而最大的剩余能量的那條路徑將會被選中。所以在協議設計過程中，將會在RREQ（RouteRequest）和RREP（RouteReply）結構中添加一個Min-RE（Minimum Remaining Energy）字段。該字段將會記錄所在路徑的最低能量剩余值。

AODVM（AOMDV Modified）協議是在AODVEA基礎上在Min-RE字段中添加一個每跳能量值，并加入到RREQ和RREP的結構中。當中間節點收到一個RREQ包，跳步數會加一并且重新改變Min-RE字段中最小剩余能量的值。

當目的節點收到所有信息后，它將決定一條最佳路徑，并通過這條路徑以單播的方式發送RREP包給源節點。AODVM中度量值的計算公式如式⑴：

目的節點根據收到的所有路由信息并計算出α值，并且選擇α最大值的那條路徑為最優路徑。

本文進一步改進之前的協議，通過充分利用節點的剩余能量來選擇一條最適合的路徑并且考慮整個網絡端到端時延問題的解決方案，進而優化現有的路由策略。

1 能量消耗模型

節點因數據包轉發而損失能量有以下兩種方式：發送數據包和接收數據包，而這兩種方式所造成的能量損失是不同的。RT（Packet Retransmission）表示重新發送報文，PF（Packet Failure）表示數據報文被丟棄，AF（Acknowledgement Failure）表示收到鏈路因為各種原因不能正常工作。因此對于數據發送和數據接收所損失的能量模型公式如式⑵和⑶。

其中，帶有Success的表示成功接收/發送數據所損失的能量，帶有AF和PF的表示由于數據傳輸過程中遇到丟棄或者鏈路故障所導致的能量損耗；i表示節點硬件工作時的電流值，Lpack表示數據的長度。式中的能量損耗考慮了無線通道使用指數路徑損耗和特征路徑損耗。節點的狀態轉換由圖1表示。

其中，PD和Idle狀態屬于當前閑置狀態，而RX和TX兩個狀態屬于真正的數據傳輸狀態。

2 改進的RED-AMODV協議

2.1 RED-AOMDV協議介紹

AOMDV協議選擇源節點最先接收到來自目的節點發來的RREP報文的路徑為轉發數據的路徑。研究結果表明，擁塞少的路徑相比跳步數少的路徑而言，具有更短的端到端的時延。RED-AOMDV（Remaining Energy Delay for Ad hoc on-demand multipath distance vector routing）協議主要是針對節點能源的有限性和節點間頻繁的中斷這些問題而設計的一種多路徑路由協議。

2.2 RED-AOMDV協議報文改進設計

RED-AOMDV協議新添加了兩個字段：received time（Tr）和transmission delay（Delay）。Tr字段表明收到RREQ報文的時間，Delay表明本節點和上一個節點收到RREQ包的時延。在原有的RREP報文的基礎上，新添加了一個字段：remaining_energy（Er），用來標識每個節點的剩余能量。新改進的RREQ和RREP報文結構如圖2、圖3所示。

S-IP—源節點的IP地址。

D-IP—目的節點的IP地址。

Sequence Number—節點自身的序列號。

hopcount—跳步數，RREQ包類型的跳步計數初始值為0。

Timeout—時間戳。

Tr—節點收到RREQ報文的時間。

Delay—節點收到RREQ包的時延。

Er—節點的剩余能量。

2.3 RED-AOMDV中RREQ報文發送

如果有數據要從節點S發送到指定節點D，S必須判斷本節點有沒有直接到達D的轉發路徑。

當中間節點N1收到來自源節點的RREQ報文，N1會將此時的時間記錄到Tr字段中保存下來，然后將RREQ報文轉發給鄰居節點。鄰居節點N2收到RREQ時，會根據此時的時間和RREQ報文中所記錄上一個節點（N1）的時間計算出RREQ報文從N1轉發到N2的時間間隔，計算公式如式⑷：

中間節點N1自己會定義一個時延門閾值[9]，如果時延超過這個閾值就表明兩者之間不可達，并且在N1不能發送任何相關的報文；否則，節點首先將自己收到RREQ報文的時間記錄到Tr字段中，并且計算出時延值記錄到Delay字段中，并將該RREQ報文轉發出去。當目的節點收到RREQ報文時，目的節點會將整條路徑的總時延值計算出來。根據RREQ包的時延數據，利用式⑸來計算出數據報文傳輸的時延值：

2.4 RED-AOMDV協議RREP報文發送

目的節點接收相應的報文后，生成一個對應的應答報文RREP，并且通過RREQ來的路徑反向發送出去。當中間節點收到RREP報文時，會將節點自己的剩余能量記錄到RREP中的Er字段中，并將RREP報文前向發送給鄰居節點。當源節點收到RREP報文時，該報文記錄了該條路徑上所有節點的剩余能量。源節點根據式⑹來選擇最適宜的轉發路徑

En表明路徑中參與數據傳輸的節點的剩余能量， Delay（i，j）表明節點i與節點j之間數據傳輸的時延。數據傳輸過程中，傳感器節點可能因為能源不足導致不能進行轉發，所以每個節點需設置一個最低能量值，如果當前節點的能量值低于這個門閾值，說明該節點不可用，經過這個節點的路徑都標識為無效路徑，并且向源節點發送RRER分組，源節點會從路由表中刪除所有不可達的路由，防止數據傳輸中因為能耗原因發生丟包情況。

2.5 RED-AOMDV協議路由表結構

RED-AOMDV協議新添加了兩個字段：delay字段和remaining_energy字段。具體路由結構如圖4所示。

每個節點會根據remaining_energy字段的值進行降序排列。

2.6 RED-AOMDV算法流程圖

RED-AOMDV協議RREQ算法流程如圖5所示。

2.7 RED-AOMDV算法開銷分析

路由開銷的大小直接影響數據傳輸的性能。RED-AOMDV協議是按需的，其開銷主要是路由發現過程中的消耗和當鏈路失效時進行的檢測控制分組，主要包括RREQ、RREP和RERR等。

當需要發送數據時，源節點首先檢查路由表中是否有達到目的節點的可用路由，若有則直接發送，否則通過廣播RREQ分組發起路由發現過程。其他節點收到RREQ分組后，會檢查源地址和標識號是否已經收到過，如果收到，則丟棄這個分組。如果路由表中有到目的節點的路由，則復制路由記錄表到RREP分組中，并反向發送到源節點。否則將自己的地址加入到路由記錄表，重新廣播這個RREQ分組，知道源節點收到目的節點的RREP分組，將路由信息存入路由緩沖器中，路由發現過程結束。在這一過程中，各種分組的轉發將會消耗一定的能量。

在按需路由協議中，路由維護和路由發現一樣，會增大整體開銷。當數據分組在傳輸過程中檢測到鏈路失效，鏈路上游節點則向源節點回傳一個RERR分組，收到RERR分組后，源節點從路由緩沖條目中刪除所有不可達的路由。此時，若路由表中沒有備用路由，源節點將重新啟動新的路由發現過程。此外，RED-AOMDV協議自身的HELLO分組機制同樣會帶來一定的開銷。

3 仿真環境及RED-AOMDV協議仿真分析

本次實驗是在ubuntu10.04操作系統下，通過NS2模擬軟件[10]進行仿真實驗。

3.1 協議添加

在NS2中，我們需要添加RED-AOMDV協議。添加一個新的協議模塊需要如下幾個步驟：添加協議類、定義協議分組頭結構、編譯代碼。下面是RED-AOMDV協議中的幾個主要文件：

～ns/RED-AOMDV/RED-AOMDV.cc

～ns/RED-AOMDV/RED-AOMDV_pkt.h

～ns/RED-AOMDV/RED-AOMDV_queue.cc

最后對新添加好的協議進行編譯，如果編譯成功，那么說明協議添加成功。

3.2 仿真場景和參數設置

節點移動模型為random waypoint模型[11-12]，節點在最小速度和最大速度間以一個隨機速度向目的節點運動。一些仿真系統初始化環境參數如表1所示。

3.3 實驗結果及性能分析

通過NS2實驗仿真，將實驗數據保存到trace文件中，再編寫相應的awk腳本得到所需數據。下面從三個角度對協議進行比較分析。

⑴ 網絡生命周期

節點的正常生存是整個網絡能夠正常工作的最基本的前提，如果節點死亡，那么整個網絡就沒有任何研究價值，因此，節點在網絡中生存時間的長短是網絡性能的一個很重要的衡量值。許多文獻給出了不同的網絡生命周期的定義，為了便于比較分析，本次實驗使用網絡中第一個節點耗盡能量的生命周期。

圖6表明節點在AOMDV、RED-AOMDV、AODV協議中，首個節點死亡時間隨著節點數量變化而變化。總體來看網絡中隨著節點數量增多，網絡生命周期有逐漸變小的趨勢。這是因為在計算路由時會消耗很多的能量。當網絡中節點數量較少時，路由表中路由條目較少，路由控制包較小，其能量花費較少。隨著網絡節點數增多，每個節點的路由表項會變的很多，二期路由控制包也變大，那么能量消耗速度更快，網絡生命周期都變小。根據圖6來看，AODV中的節點生存時間最短，AOMDV生存時間次之，而改進后的協議RED-AOMDV中的節點生存時間最長。由于AODV協議只是單路徑路由協議，如果該路徑斷開后，有新的數據發送時，就會重新發起一次尋路過程，在這個過程中，會消耗節點的能源，導致節點過早死亡；而AOMDV協議是多路徑路由協議，當轉發路徑斷開后，可以立即啟用備用路徑，減少了因再次發起路由尋找過程而消耗的能量；RED-AOMDV協議中，考慮了能量和時延這兩個參數，由于AOMDV協議在沒有其他影響的情況下，一般是由于轉發路徑上的節點能量耗盡才會導致該條路徑不可用，但是RED-AOMDV協議不會等到節點能量即將耗盡時才切換鏈路，保證了節點的生存時間，因此RED-AOMDV協議中的節點生存時間最長。

⑵ 分組投遞率

接收信息是無線傳感器網絡的一個最終目的，因此接收的數據量的多少也就成為衡量這個網絡的重要標準。接收報文數與發送報文數的比值越高說明收到的數據報文就越多，表明整個網絡的性能越好，反之則越差。

圖7表明三種協議的分組投遞率隨著移動速度的變化而變化。隨著節點移動速度的逐漸變大，三種協議的分組投遞率呈逐漸降低的趨勢。從整個過程來看，RED-AOMDV協議的分組投遞率最好，比AODV效率提高了約15%～19%，比AOMDV協議提高了約5%～10%。由于AODV是單路徑轉發數據，而另外兩個協議都是多路徑轉發數據，因此在數據流比較大的時候，AODV協議的效率相比而言就比較低，另外，節點的高速移動導致鏈路的不穩定性概率增大，這也是導致AODV效率低下的一個原因。RED-AOMDV協議考慮到了數據傳輸時延并考慮了鏈路中節點的能量這兩個因素，因此相比AODV、AOMDV這兩個協議來說具有更好的投遞率。

⑶ 路由開銷

仿真中的路由開銷是指每個節點平均收到一個報文時所需要的非數據報文的數目。平均需要的非數據報文數越少，表明整個網絡越好。

圖8表明三個協議中每個節點的能量消耗隨著節點移動速度的變化而變化。隨著節點移動速度的增大，三個協議中每個節點的能量消耗都呈逐漸遞增的趨勢，這主要是由于移動速度的增大，使得整個網絡拓撲處于不穩定狀態，所需要的控制報文也就會隨之增多。從圖8可知，RED-AOMDV協議的能量消耗低于AODV和AOMDV，并且其遞增趨勢也明顯小于這兩個協議。這主要是因為RED-AOMDV協議同時考慮了時延和能量這兩個因素，減小了網絡的擁塞。

4 結束語

針對傳統的AOMDV協議僅提供多條傳輸路徑且當前路徑故障才啟用備份鏈路，以及未考慮節點能量的弊端，本文研究了能量枯竭導致節點死亡這一問題，基于AOMDV協議提出了RED-AOMDV協議，該協議在選取傳輸路徑時，綜合考慮每個節點的能量值和時延，會根據每條路徑的最大剩余能量來選擇最優路徑。RED-AOMDV協議主要是針對節點能源的有限性和節點間頻繁的中斷問題而設計的一種多路徑路由協議。通過NS2仿真表明，改進后的RED-AOMDV協議相比AODV和AOMDV協議，在性能上有了較大提高，改善了網絡通信的質量。

參考文獻（References）：

[1] Ducksoo Shin， Jonghyup Lee， Jaesung Kim， Jooseok. A2OMDV： An adaptive ad hoc on-demand multipath distancevector routing protocol using dynamic route switching[J]. Journalof Engineering Science，2009.4（2）：171-183

[2] Yusuke Sakurai， Jiro Katto. AODV Multipath Extensionusing Source Route Lists with Optimized Route Estab-lishment[J]. International workshop on wireless ad hoc networks （IWWAN），2004.

[3] Sujata V.Mallapur， Sujata. Terdal.Enhanced Ad-Hoc on Demand Multipath Distance Vector Routing Potocol （EAOMDV[J]. （IJCSIS）International Journal of Computer Science and Information Security，2010.7（3）.

[4] Shuchita Upadhayaya， Charu Gandhi. QoS routing using link and node stability in mobile ad hoc networks[J]. Journal of Theoretical and Applied Information Technology，2009.6（4）.

[5] R. Vinod Kumar， R.D.Wahida Banu. Load-balancing Approach for AOMDV in Ad-hoc Networks[J]. IJC Special Issue on “Mobile Ad-hoc Networks”MANETs，2010.

[6] Gue H， Low K-S， Nguyen H-A. Optimizing the

localization of a wireless sensor network in real time based on a low-cost microcontroller[J]. IEEE Trans Ind Electron，2011.58（3）：741-749

[7] Radhika D. Joshi & Priti P.Rege. Energy Aware Routing in

Ad Hoc Networks[C]. 6th WSEAS International Conference on CIRCUITS， SYSTEMS， ELECTRONICS， CONTROL & SIGNAL PROCESSING， Cairo， Egypt，2007.12（8）：29-31

[8] Soo-Bum Kim， Ji-Hoon Lee， Seung-Yeon You， Sung-Wook Kim， Sung-Chun Kim. Power-aware Pat Selection Scheme for AOMDV[J]. Brain Korea21 Project I，2006.

[9] 童孟軍，江浩然，鄭拓.基于距離能量感知的 AOMDV協議研究[J].杭州電子科技大學學報，2014.34（2）：28-31

[10] 余本功，余超凡，劉剛.基于AODV和AOMDV路由協議的多移動節點通信分析[J].價值工程，2014.（15）：194-195

[11] Yang Tao， Oda Tetsuya. Performance evaluation of WSNs for different MAC protocols considering TwoRayGround radio model and AODV Routing Protocol[C]. Conference on Complex， Intelligent， and Software Intensive Systems，2012.

[12] Durrenbach Alban， Fourestie Benoit， Rault Maryna.Global shadowing margins for 3G Networks[C]. 57th IEEE Semiannual Vehicular Technology Conference，2003.2（57）：798-802