Ad Hoc多徑路由算法

高永貴，龍昭華，張 林

（重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065）

0 引 言

由于Ad Hoc網(wǎng)絡(luò)連接的不穩(wěn)定性和動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，單路徑的網(wǎng)絡(luò)路由協(xié)議已不能滿足網(wǎng)絡(luò)的性能需求［1］。由于多徑路由的優(yōu)勢(shì)，其成為當(dāng)前Ad Hoc網(wǎng)絡(luò)中研究的熱點(diǎn)，多徑的主要思想是在一次路由進(jìn)程中，發(fā)現(xiàn)多條可用路徑，利用多條路徑進(jìn)行并行或備份的方式傳輸數(shù)據(jù)，提高網(wǎng)絡(luò)的穩(wěn)定性和資源利用率。使用多徑路由傳輸業(yè)務(wù)數(shù)據(jù)，一定程度上減少了數(shù)據(jù)傳輸在帶寬方面的限制；隨著多媒體業(yè)務(wù)在Ad Hoc網(wǎng)中廣泛應(yīng)用，多路徑在延遲和鏈路穩(wěn)定性方面更滿足多媒體業(yè)務(wù)的QoS需求［2］。

如果路由的開(kāi)銷過(guò)大，多徑的優(yōu)勢(shì)就會(huì)明顯減弱［3］，因此開(kāi)發(fā)更簡(jiǎn)潔、高效的多徑路由協(xié)議有著重要意義。同時(shí)動(dòng)態(tài)的拓?fù)浣Y(jié)構(gòu)導(dǎo)致多次路由發(fā)現(xiàn)過(guò)程耗費(fèi)大量時(shí)間和網(wǎng)絡(luò)資源，不利于當(dāng)前的多媒體業(yè)務(wù)的需求。信息熵作為不確定性因素的度量［3］，和Ad Hoc中移動(dòng)節(jié)點(diǎn)的不確定性移動(dòng)有著相似的對(duì)應(yīng)關(guān)系，將熵的概念應(yīng)用到Ad Hoc網(wǎng)絡(luò)中，對(duì)于發(fā)現(xiàn)可靠性的路徑有著顯著作用。本文在分析Ad Hoc網(wǎng)絡(luò)特點(diǎn)的基礎(chǔ)上，利用熵與自組織網(wǎng)絡(luò)的共性分析問(wèn)題，基于高效、簡(jiǎn)潔多徑路由協(xié)議的開(kāi)發(fā)思想，提出了一種聯(lián)合熵的開(kāi)銷最小多徑路由協(xié)議ENDMAODV，該算法有效改進(jìn)了分組投送率、平均控制開(kāi)銷和端到端延遲。

1 相關(guān)工作

自組織網(wǎng)絡(luò)可以表示為帶權(quán)的有向圖G（V，E）［4］，其中V 表示移動(dòng)節(jié)點(diǎn)的集合，E 表示可連接的節(jié)點(diǎn)間的鏈路集合。在研究Ad Hoc網(wǎng)絡(luò)時(shí)，使用R 表示節(jié)點(diǎn)間鏈路的屬性結(jié)合，如i，j兩可連接節(jié)點(diǎn)，則＜i，j＞鏈路的屬性可表現(xiàn)為帶寬、時(shí)延、代價(jià)、鏈路持續(xù)時(shí)間等等。

Perkins、Belding－Roryer等人提出了AODV 路由 （基于距離矢量的按需路由）協(xié)議［5］。AODV 是一種單徑路由協(xié)議，主要有路由發(fā)現(xiàn)和路由維護(hù)2 個(gè)階段和RREQ、RREP、RRER、HELLO 這4 種報(bào)文組成。AODV 實(shí)質(zhì)上是DSR［6］和DSDV［7］的結(jié)合，借用了DSR 中路由發(fā)現(xiàn)和維護(hù)的機(jī)制，以及DSDV 逐跳路由和目的節(jié)點(diǎn)序列號(hào)的周期更新機(jī)制的思想，以DSDV 為基礎(chǔ)，結(jié)合DSR 按需的思想進(jìn)行改進(jìn)而來(lái)。AODV 中每個(gè)節(jié)點(diǎn)隱式保存了路由請(qǐng)求和應(yīng)答的結(jié)果，利用擴(kuò)展環(huán)搜索的思想限制RREQ 的傳播范圍。AODV 使用目的節(jié)點(diǎn)序列號(hào)實(shí)現(xiàn)了路由的無(wú)環(huán)，并提高了算法的收斂速度。

AOMDV （按需多徑路由）協(xié)議［8］是基于AODV 擴(kuò)展的多徑路由協(xié)議，AOMDV 修改了AODV 的路由發(fā)現(xiàn)方式并引入了廣播跳數(shù)的概念來(lái)替換原來(lái)的跳數(shù)。仍使用目的節(jié)點(diǎn)序列號(hào)來(lái)確保無(wú)環(huán)和路由更新。為了存儲(chǔ)多條可用的路由路徑，參照AODV 的選擇算法在多條無(wú)環(huán)不相交路徑中進(jìn)行選擇，每一個(gè)目的節(jié)點(diǎn)路由中都記錄了下一個(gè)轉(zhuǎn)發(fā)列表和跳數(shù)。

MSR 協(xié)議 （分離多徑路由）［9］是基于DSR 的擴(kuò)展的一種多徑路由協(xié)議，該算法能夠發(fā)現(xiàn)并使用最大不相交的2條路由路徑，并選擇其中一條性能優(yōu)秀的路徑作為傳輸?shù)闹髀酚?，另外一條作為備份路由使用，這樣一種主從備份的方式，有效的提高了路由利用率，減少了啟動(dòng)路由發(fā)現(xiàn)的次數(shù)和網(wǎng)絡(luò)時(shí)延，提高了網(wǎng)絡(luò)的整體分組投送率。

2 路徑穩(wěn)定性度量

B.An和S.Papavassiliou最早在移動(dòng)自組織網(wǎng)絡(luò)中應(yīng)用熵評(píng)價(jià)路徑的穩(wěn)定性［3］。由于自組織網(wǎng)絡(luò)的節(jié)點(diǎn)移動(dòng)性，找到相對(duì)穩(wěn)定的路由路徑能夠顯著的減少路由重構(gòu)的時(shí)間、減少了時(shí)延，進(jìn)而對(duì)于業(yè)務(wù)的傳輸有著重要的作用。在移動(dòng)Ad Hoc 網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)的狀態(tài)可以用節(jié)點(diǎn)位置Positon（i）和速度V（i）來(lái)表示?？梢赃@樣認(rèn)為對(duì)于網(wǎng)絡(luò)中的任意節(jié)點(diǎn)m，其特征向量am，n表示如下所示

式中：Position（m，n，t）——m 節(jié)點(diǎn)和n 節(jié)點(diǎn)的相對(duì)位置。V（m，n，t）——m 節(jié)點(diǎn)和n 節(jié)點(diǎn)在t時(shí)刻的相對(duì)速度。二者的計(jì)算表示形式如下 （執(zhí)行向量運(yùn)算）所示

基于上述，則構(gòu)造可連接移動(dòng)節(jié)點(diǎn)對(duì)（m，n）在時(shí)間間隔內(nèi)的特征向量如下所示

式中：R——節(jié)點(diǎn)的傳輸半徑，N ——在Δt時(shí)間間隔內(nèi)離散時(shí)刻ti的總個(gè)數(shù)，即每間隔時(shí)間Δt，相對(duì)位置向量和速度向量被更新和計(jì)算的次數(shù)?；诖?，我們定義熵

在式 （5）的基礎(chǔ)上，進(jìn)行求導(dǎo)去負(fù)對(duì)數(shù)的方法，得到式 （6）

式（6）可以看出，P’（m，n）的值越小，節(jié)點(diǎn)對(duì)（m，n）之間路徑越穩(wěn)定，由此得到評(píng)價(jià)路徑穩(wěn)定性的度量。

3 基于AODV的多徑路由算法

3.1 修改的控制結(jié)構(gòu)及路由建立

本文在深入研究AODV 路由協(xié)議的基礎(chǔ)上，為了實(shí)現(xiàn)使用最小開(kāi)銷找到源目的節(jié)點(diǎn)對(duì)之間的多條節(jié)點(diǎn)不相交路徑路由，對(duì)AODV 協(xié)議中的RREQ 控制包結(jié)構(gòu)、RREP控制包結(jié)構(gòu)和節(jié)點(diǎn)緩存路由表信息進(jìn)行了修改，同時(shí)修改路由表的相關(guān)信息，使其有能力存儲(chǔ)多條路徑和周期性的熵的計(jì)算值。（其中文中選擇的多路徑條數(shù)條數(shù)為2）。

1) 跟蹤精度提高。本文算法通過(guò)實(shí)時(shí)修正模型轉(zhuǎn)移概率，使與目標(biāo)運(yùn)動(dòng)匹配的模型概率增大，加快模型切換速度，最終提高了精度，如圖1所示。從表2可以看出，在全航路，距離精度提高8.2%，速度精度提高12.9%；尤其是在勻速段，速度精度提升26.9%。另一方面，在圖2中，細(xì)實(shí)線表示IMM3-EKF算法，由于IMM3中存在模型競(jìng)爭(zhēng)，實(shí)際濾波效果比本文算法還差。

修改的RREQ 控制包結(jié)構(gòu)，見(jiàn)表1。

表1 修改的RREQ 控制包結(jié)構(gòu)

修改的RREP控制包結(jié)構(gòu)，見(jiàn)表2。

表2 修改的RREP控制包結(jié)構(gòu)

表3 中，S＿address和Broadcast＿id 標(biāo)志位來(lái)源于RREQ 控制包，作為每次請(qǐng)求的獨(dú)立標(biāo)示。Jusr＿flag標(biāo)志位的初值為FALSE。在本算法中，為了確保發(fā)現(xiàn)節(jié)點(diǎn)不相交的多條路徑，規(guī)定，任何中間節(jié)點(diǎn)不回復(fù)RREQ 路由請(qǐng)求包，而是按照AODV 協(xié)議中沒(méi)有目的節(jié)點(diǎn)路由的中間節(jié)點(diǎn)的方式和后文算法1的方式處理RREQ 控制包。算法2顯示RREP控制包的處理過(guò)程。

表3 節(jié)點(diǎn)處增加的Justtable結(jié)構(gòu)

算法1 RREQ 控制包處理進(jìn)程

在執(zhí)行算法1之前，當(dāng)節(jié)點(diǎn)有數(shù)據(jù)需要發(fā)送時(shí)，首先檢查是否緩存有到目的節(jié)點(diǎn)的有效路由，如果有，則直接發(fā)送。啟動(dòng)路由發(fā)現(xiàn)過(guò)程，初始化RREQ 包，Justtable表和緩存路由表。算法2中，當(dāng)源節(jié)點(diǎn)收到RREP 路由控制包時(shí)，將緩存這些RREP 包，等待時(shí)間T，等待時(shí)間結(jié)束后，前所有收到的RREP 包按照Entropy 字段進(jìn)行排序，從中選擇Entropy字段最小的2條路徑。

算法2 RREP控制包處理進(jìn)程

圖1中，結(jié)合具體的實(shí)例簡(jiǎn)單描述了算法的執(zhí)行過(guò)程。如圖1所示，假如S為源節(jié)點(diǎn)，D 為目的節(jié)點(diǎn)，當(dāng)S有數(shù)據(jù)需要發(fā)送時(shí)，啟動(dòng)路由發(fā)現(xiàn)過(guò)程，洪泛RREQ 包，根據(jù)算法1，中間節(jié)點(diǎn)或是丟棄RREQ 或是更新熵字段的值并廣播RREQ，假如當(dāng)目的節(jié)點(diǎn)D 在t1時(shí)刻收到了來(lái)至節(jié)點(diǎn)I的RREQ 包，目的節(jié)點(diǎn)初始化RREP1包，并通過(guò)反向路徑D－＞I－＞H－＞B－＞S傳播，當(dāng)中間節(jié)點(diǎn)收到RREP，檢查Just＿flag 標(biāo)志位是否為FALSE，是，則重置為T(mén)RUE，并建立正向路由，形成了一條S－＞B－＞H－＞I－＞D 的路由路徑。假如D 在t2時(shí)刻收到了來(lái)至J的RREQ 包，初始化RREP2包，同上建立了S－＞A－＞F－＞J－＞D 的路由路徑。在t3 時(shí)刻，D 收到了來(lái)至K 的RREQ 包，D 初始化RREP3包，RREP3包通過(guò)K 到達(dá)J，節(jié)點(diǎn)J檢查Just＿table標(biāo)志位為T(mén)RUE，則認(rèn)為收到了重復(fù)的RREP包，丟棄RREP3。在t4時(shí)刻，節(jié)點(diǎn)D 收到了來(lái)至M 的RREQ 包，初始化RREP4包，同上建立了S－＞C－＞E－＞L－＞M－＞D 的路由路徑。

圖1 多徑路由發(fā)現(xiàn)過(guò)程

當(dāng)源節(jié)點(diǎn)S在等待的T 時(shí)刻內(nèi)，收到了多個(gè) （此處是3個(gè)）RREP包，按照RREP中的Entropy值進(jìn)行排序，選擇其中最小2條路徑。

3.2 多徑路由的維護(hù)與失效

在上述的多徑路由選擇中，選擇熵值最小，也即是最穩(wěn)定的路徑最為主路徑，另外一條作為從路徑，形成主從備份的路由形式。

路由差錯(cuò)報(bào)告階段，當(dāng)正在進(jìn)行的數(shù)據(jù)傳輸?shù)逆溌窋嚅_(kāi)時(shí)，并不立即發(fā)送RRER 控制包進(jìn)行差錯(cuò)報(bào)告，而是節(jié)點(diǎn)檢測(cè)是否存在第2條路由，若存在，則將數(shù)據(jù)傳輸鏈路切換到另外一條鏈路，若不存在第2條路由或第2條路由斷開(kāi)或失效，則發(fā)送RREQ 控制包，通知受影響的節(jié)點(diǎn)，同時(shí)啟動(dòng)路由發(fā)現(xiàn)過(guò)程。圖1中，當(dāng)正在傳輸數(shù)據(jù)的路徑S－＞A－＞F－＞J－＞D 中J－＞D 鏈路斷開(kāi)時(shí)，并不立即啟動(dòng)RRER 過(guò)程，而是切換路徑為J－＞K－＞D，進(jìn)而形成S－＞A－＞F－＞J－＞K－＞D 路徑進(jìn)行傳輸，當(dāng)此路徑再次斷開(kāi)時(shí)才啟動(dòng)RRER 過(guò)程。

3.3 正確性證明

定理 選擇的路由路徑是無(wú)環(huán)的

證明：算法是在AODV 路由協(xié)議的基礎(chǔ)上進(jìn)行改進(jìn)，AODV 協(xié)議RREQ 階段的無(wú)環(huán)性保證了該算法RREQ 階段的無(wú)環(huán)性。當(dāng)節(jié)點(diǎn)收到路由的RREP應(yīng)答包后，檢查Justtable表中的Just＿flag二進(jìn)制位字段，看是否被置位，如被置位則丟棄相應(yīng)RREP 控制包；否則保存記錄轉(zhuǎn)發(fā)RREP控制包。由此看出，該算法選擇的路由路徑是無(wú)環(huán)的。

4 仿真分析

為了評(píng)價(jià)文中提出的路由算法的有效性和性能。在NS2［11］仿真環(huán)境下，實(shí)驗(yàn)中，20 個(gè)節(jié)點(diǎn)分布在1000 m×1000m 的場(chǎng)景中，節(jié)點(diǎn)最大移動(dòng)速度為10m／s，數(shù)據(jù)包的大小為512bytes，數(shù)據(jù)源是CBR，MAC 層使用802.11，仿真運(yùn)行時(shí)間500s，節(jié)點(diǎn)的傳輸范圍為200m，節(jié)點(diǎn)按照Waypoint模型隨機(jī)運(yùn)動(dòng)。主要從路徑重構(gòu)次數(shù)、平均分組投送率和平均控制開(kāi)銷、端到端時(shí)延4個(gè)方面來(lái)分析 （如式7）和驗(yàn)證本文提出的ENDM－AODV 算法

圖2 中給出了AOMDV 和ENDM－ADOV 路由算法的路由重構(gòu)次數(shù)的比較?？梢钥闯?，相對(duì)于AOMDV 而言，ENDM－ADOV 算法的重構(gòu)次數(shù)明顯減少，這是因?yàn)樗惴ㄖ谢陟卣业搅讼鄬?duì)穩(wěn)定的2條路徑，同時(shí)另外一條路由作為備份路由使用，只要當(dāng)2條路由同時(shí)失效的時(shí)候，才啟動(dòng)路由發(fā)現(xiàn)進(jìn)程，如此一來(lái)，進(jìn)一步減少了路由重構(gòu)次數(shù)。

圖3給出了在不同的移動(dòng)速度下AOMDV 和ENDMAODV 算法的分組投送率的比較，可以看出，隨著節(jié)點(diǎn)移動(dòng)速度的增大，分組投送率都持續(xù)下降?？傮wENDM－AODV算法有著明顯的優(yōu)勢(shì)。這是因?yàn)橹虚g找到了多條路由路徑（可能超過(guò)2條）同時(shí)選擇相對(duì)較可靠的路徑進(jìn)行數(shù)據(jù)傳輸，整體上提高了ENDM－AODV路由協(xié)議的分組投送率。

圖2 路徑重構(gòu)次數(shù)比較

圖3 分組投送率比較

圖4給出了平均控制開(kāi)銷的比較，分析2種不同的算法看出，ENDM－AODV 使用簡(jiǎn)單的標(biāo)志位信息進(jìn)行控制包傳輸中的比較與處理，相對(duì)于AOMDV 而言減少了開(kāi)銷信息，且在路由維護(hù)階段，中間節(jié)點(diǎn)可能存在2條到目的的路徑，一旦某條出現(xiàn)問(wèn)題，則可以切換到另外一條，減少了修復(fù)的開(kāi)銷。

圖4 平均控制開(kāi)銷的比較

圖5給出了2種協(xié)議的端到端時(shí)延的比較，可以看出，隨著移動(dòng)節(jié)點(diǎn)的速度增加，2 種算法的端到端的時(shí)延都增加較快。從圖中還可以看出對(duì)于AOMDV 算法，ENDMAODV 協(xié)議隨著節(jié)點(diǎn)移動(dòng)速度的增加端到端的要低。這是因?yàn)樵诤苄〉拈_(kāi)銷情況下，ENDM－AODV 就獲得了較穩(wěn)定的路由路徑。

圖5 端到端時(shí)延的比較

5 結(jié)束語(yǔ)

本文在深入分析AODV 單徑路由協(xié)議的基礎(chǔ)上，通過(guò)引入標(biāo)志位的方式，設(shè)計(jì)了一種多徑路由算法ENDMAODV，算法中結(jié)合信息熵的概念，在發(fā)現(xiàn)的多條路徑中選擇穩(wěn)定性最好的2條路徑形成主從備份路由路徑。簡(jiǎn)單的標(biāo)志位處理方式，極大的較少了路由的整體開(kāi)銷，信息熵的引入，減少了路由重構(gòu)的次數(shù)，進(jìn)而能更好的保證動(dòng)態(tài)拓?fù)涞腁d Hoc網(wǎng)絡(luò)中數(shù)據(jù)傳輸率。仿真的結(jié)果表明，ENDM－AODV 協(xié)議優(yōu)化了分組投送率、端到端延遲和平均節(jié)點(diǎn)控制開(kāi)銷。ENDM－ADOV 協(xié)議的提出為設(shè)計(jì)和優(yōu)化多徑路由協(xié)議提供了一種新的思路。

在未來(lái)的研究中，將結(jié)合多QoS的相關(guān)概念和節(jié)點(diǎn)移動(dòng)模型更加全面的考慮和優(yōu)化算法在自組網(wǎng)中的性能，提高組織網(wǎng)的網(wǎng)絡(luò)利用率。

［1］Chhagan LalA，Vijay Laxmi.A rate adaptive and multi－path routing protocol to support video streaming in MANETs［C］／／Proc of International Conference on Advances in Computing，Communications and Informatic，2012：262－268.

［2］Ron Banner，Ariel Orda.Multi－path routing algorithms for con－gestion minimization ［J］.IEEE／ACM Trangsactions on Networking，2007，15 （2）：413－418.

［3］SUN Baoling，GUI Chao.Multi－path on－demand routing and routing algorithm based on entropy in Ad Hoc［J］.Journal of Software，2008，19 （12）：112－120 （in Chinese）. ［孫寶林，桂超.Ad Hoc網(wǎng)絡(luò)多路徑需求路由及路徑熵選擇算法 ［J］.軟件學(xué)報(bào)，2008，19 （12）：112－120.］

［4］LI Mingzhe.Graph theory and algorithms［M］.Beijing：China Machine Press，2010：1－242 （in Chinese）.［李明哲.圖論及算法 ［M］.北京：機(jī)械工業(yè)出版社，2010：1－242.］

［5］Midhun Kalyan Anantapall，Li Wei.Multi－path multi－h(huán)op routing analysis in mobile Ad Hoc networks［J］.Wireless Netw，2010，16 （1）：573－575.

［6］Li Ming，Prabhakaran B.On supporting reliable Qos in multihop multi－rate mobile Ad Hoc networke［J］.Wireless Netw，2010，16 （1）：813－827.

［7］Hemanth Narra，Cheng Yufei.Destination－sequenced distance vector （DSDV）routing protocol implementation in ns－3［C］／／Proc of 4th Internation ICST Conference on Simulation Tools and Techniques，2011：439－446.

［8］LIU Jingwei，LEI Tao.The research and design of multi－path routing protocol in Ad Hoc ［J］.Computer Engineering and Design，2007，28 （17）：1415－1418 （in Chinese）. ［劉經(jīng)緯，雷濤.Ad－h(huán)oc網(wǎng)絡(luò)多徑路由協(xié)議的研究與設(shè)計(jì) ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28 （17）：1415－1418.］

［9］Bahador Amiri，Hamid R Sadjapour.Outage optimum routing for wireless Ad Hoc networks ［C］／／Proc of 7th Internation Conference of Wireless Communications and Mobile Computing，2011：1576－1587.

［10］Chen Quanjun，Salil S Kanhere.Adaptive positon update for geographic routing in mobile Ad Hoc networks ［J］.IEEE Transactions on Mobile Computing，2013，12 （2）：489－501.

［11］Teerawat Issariyakul，Ekram Hossain.Introduction to Network Simulator NS2 ［M］.Springer Publishing Company，2010：1－400.