AOMDV多路徑協(xié)議的研究和改進(jìn)

李子璇　童孟軍　江浩然

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

關(guān)鍵詞： 多路徑協(xié)議； 節(jié)點能耗； 最優(yōu)路徑； 時延

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：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中，節(jié)點扮演一個路由器的角色。這樣的網(wǎng)絡(luò)具有以下特點：拓?fù)湟鬃兓?、帶寬約束、能源受限，而且易出現(xiàn)安全問題。鑒于以上情況，路由將會是WSN中一個很重要的問題。

每個參與路由維護(hù)和數(shù)據(jù)轉(zhuǎn)發(fā)的節(jié)點都支持端到端通信。這些節(jié)點通常是小電池供電的設(shè)備，能夠感測、存儲、數(shù)據(jù)處理以及通過無線電節(jié)點與其他節(jié)點通信。在許多應(yīng)用領(lǐng)域中，想要為節(jié)點充電或者是更換電池是不切實際的，因此網(wǎng)絡(luò)能量效率最大化是設(shè)計節(jié)點的關(guān)鍵所在。

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

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

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

AODVM（AOMDV Modified）協(xié)議是在AODVEA基礎(chǔ)上在Min-RE字段中添加一個每跳能量值，并加入到RREQ和RREP的結(jié)構(gòu)中。當(dāng)中間節(jié)點收到一個RREQ包，跳步數(shù)會加一并且重新改變Min-RE字段中最小剩余能量的值。

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

目的節(jié)點根據(jù)收到的所有路由信息并計算出α值，并且選擇α最大值的那條路徑為最優(yōu)路徑。

本文進(jìn)一步改進(jìn)之前的協(xié)議，通過充分利用節(jié)點的剩余能量來選擇一條最適合的路徑并且考慮整個網(wǎng)絡(luò)端到端時延問題的解決方案，進(jìn)而優(yōu)化現(xiàn)有的路由策略。

1 能量消耗模型

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

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

其中，PD和Idle狀態(tài)屬于當(dāng)前閑置狀態(tài)，而RX和TX兩個狀態(tài)屬于真正的數(shù)據(jù)傳輸狀態(tài)。

2 改進(jìn)的RED-AMODV協(xié)議

2.1 RED-AOMDV協(xié)議介紹

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

2.2 RED-AOMDV協(xié)議報文改進(jìn)設(shè)計

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

S-IP—源節(jié)點的IP地址。

D-IP—目的節(jié)點的IP地址。

Sequence Number—節(jié)點自身的序列號。

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

Timeout—時間戳。

Tr—節(jié)點收到RREQ報文的時間。

Delay—節(jié)點收到RREQ包的時延。

Er—節(jié)點的剩余能量。

2.3 RED-AOMDV中RREQ報文發(fā)送

如果有數(shù)據(jù)要從節(jié)點S發(fā)送到指定節(jié)點D，S必須判斷本節(jié)點有沒有直接到達(dá)D的轉(zhuǎn)發(fā)路徑。

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

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

2.4 RED-AOMDV協(xié)議RREP報文發(fā)送

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

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

2.5 RED-AOMDV協(xié)議路由表結(jié)構(gòu)

RED-AOMDV協(xié)議新添加了兩個字段：delay字段和remaining_energy字段。具體路由結(jié)構(gòu)如圖4所示。

每個節(jié)點會根據(jù)remaining_energy字段的值進(jìn)行降序排列。

2.6 RED-AOMDV算法流程圖

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

2.7 RED-AOMDV算法開銷分析

路由開銷的大小直接影響數(shù)據(jù)傳輸?shù)男阅?。RED-AOMDV協(xié)議是按需的，其開銷主要是路由發(fā)現(xiàn)過程中的消耗和當(dāng)鏈路失效時進(jìn)行的檢測控制分組，主要包括RREQ、RREP和RERR等。

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

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

3 仿真環(huán)境及RED-AOMDV協(xié)議仿真分析

本次實驗是在ubuntu10.04操作系統(tǒng)下，通過NS2模擬軟件[10]進(jìn)行仿真實驗。

3.1 協(xié)議添加

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

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

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

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

最后對新添加好的協(xié)議進(jìn)行編譯，如果編譯成功，那么說明協(xié)議添加成功。

3.2 仿真場景和參數(shù)設(shè)置

節(jié)點移動模型為random waypoint模型[11-12]，節(jié)點在最小速度和最大速度間以一個隨機(jī)速度向目的節(jié)點運(yùn)動。一些仿真系統(tǒng)初始化環(huán)境參數(shù)如表1所示。

3.3 實驗結(jié)果及性能分析

通過NS2實驗仿真，將實驗數(shù)據(jù)保存到trace文件中，再編寫相應(yīng)的awk腳本得到所需數(shù)據(jù)。下面從三個角度對協(xié)議進(jìn)行比較分析。

⑴ 網(wǎng)絡(luò)生命周期

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

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

⑵ 分組投遞率

接收信息是無線傳感器網(wǎng)絡(luò)的一個最終目的，因此接收的數(shù)據(jù)量的多少也就成為衡量這個網(wǎng)絡(luò)的重要標(biāo)準(zhǔn)。接收報文數(shù)與發(fā)送報文數(shù)的比值越高說明收到的數(shù)據(jù)報文就越多，表明整個網(wǎng)絡(luò)的性能越好，反之則越差。

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

⑶ 路由開銷

仿真中的路由開銷是指每個節(jié)點平均收到一個報文時所需要的非數(shù)據(jù)報文的數(shù)目。平均需要的非數(shù)據(jù)報文數(shù)越少，表明整個網(wǎng)絡(luò)越好。

圖8表明三個協(xié)議中每個節(jié)點的能量消耗隨著節(jié)點移動速度的變化而變化。隨著節(jié)點移動速度的增大，三個協(xié)議中每個節(jié)點的能量消耗都呈逐漸遞增的趨勢，這主要是由于移動速度的增大，使得整個網(wǎng)絡(luò)拓?fù)涮幱诓环€(wěn)定狀態(tài)，所需要的控制報文也就會隨之增多。從圖8可知，RED-AOMDV協(xié)議的能量消耗低于AODV和AOMDV，并且其遞增趨勢也明顯小于這兩個協(xié)議。這主要是因為RED-AOMDV協(xié)議同時考慮了時延和能量這兩個因素，減小了網(wǎng)絡(luò)的擁塞。

4 結(jié)束語

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

參考文獻(xiàn)（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協(xié)議研究[J].杭州電子科技大學(xué)學(xué)報，2014.34（2）：28-31

[10] 余本功，余超凡，劉剛.基于AODV和AOMDV路由協(xié)議的多移動節(jié)點通信分析[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