李旭， 何浩雄， 彭進(jìn)霖， 宋顧楊， 邵小桃

(1.北京交通大學(xué) 電子信息工程學(xué)院, 北京 100044； 2.北京跟蹤與通信技術(shù)研究所， 北京 100092)

一種區(qū)分路由頻次的移動(dòng)無(wú)線自組織網(wǎng)絡(luò)混合路由協(xié)議

李旭1， 何浩雄1， 彭進(jìn)霖2， 宋顧楊1， 邵小桃1

(1.北京交通大學(xué) 電子信息工程學(xué)院, 北京 100044； 2.北京跟蹤與通信技術(shù)研究所， 北京 100092)

隨著移動(dòng)無(wú)線自組織網(wǎng)絡(luò)在編隊(duì)通信、應(yīng)急通信等領(lǐng)域的廣泛應(yīng)用，越來(lái)越多的應(yīng)用場(chǎng)景呈現(xiàn)路由使用頻次不同的現(xiàn)象，對(duì)此現(xiàn)有按需路由協(xié)議和主動(dòng)路由協(xié)議固定不變的路由維護(hù)策略無(wú)法高效適用。面向路由使用頻次不同的應(yīng)用場(chǎng)景，基于按需距離矢量(AODV)路由協(xié)議，設(shè)計(jì)并提出了一種按需策略和主動(dòng)策略相結(jié)合的混合式路由算法，即通過(guò)源節(jié)點(diǎn)對(duì)每條路由使用頻次的評(píng)估，將路由劃分為高頻次路由和低頻次路由。對(duì)于高頻次路由，運(yùn)用主動(dòng)策略維護(hù)；對(duì)于低頻次路由，則運(yùn)用按需策略維護(hù)。通過(guò)定性分析和仿真驗(yàn)證得出，相比AODV協(xié)議，該算法將數(shù)據(jù)包的端到端平均傳輸時(shí)延降低約20%.

兵器科學(xué)與技術(shù)； 移動(dòng)無(wú)線自組織網(wǎng)絡(luò)； 混合路由； 按需距離矢量

0 引言

移動(dòng)無(wú)線自組織網(wǎng)絡(luò)(MANET)根據(jù)路由發(fā)現(xiàn)策略，分為主動(dòng)式路由和按需路由。主動(dòng)式路由實(shí)時(shí)地維護(hù)全網(wǎng)中的路徑，為網(wǎng)絡(luò)中的數(shù)據(jù)包提供了盡可能多的路由信息。然而，大量的控制開(kāi)銷(xiāo)使得主動(dòng)路由在自組織網(wǎng)絡(luò)中占用太多的傳輸帶寬資源，這對(duì)于存在帶寬瓶頸的網(wǎng)絡(luò)是極為奢侈的。按需路由的出現(xiàn)在很大程度上解決了主動(dòng)路由高開(kāi)銷(xiāo)的問(wèn)題。在按需路由中，業(yè)務(wù)數(shù)據(jù)的產(chǎn)生會(huì)激發(fā)相應(yīng)路由的尋路過(guò)程。并且在數(shù)據(jù)傳輸過(guò)程中，路由的維護(hù)也是按需進(jìn)行的，即業(yè)務(wù)數(shù)據(jù)的停止也會(huì)引起路由維護(hù)的終止，不會(huì)產(chǎn)生過(guò)多的控制開(kāi)銷(xiāo)。

隨著自組織網(wǎng)絡(luò)按需距離矢量(AODV)路由協(xié)議[1]、動(dòng)態(tài)源路由(DSR)協(xié)議[2]等按需路由協(xié)議的普及和研究，其暴露的問(wèn)題也越發(fā)的明顯，即按需的機(jī)制會(huì)在很大程度上增大一部分?jǐn)?shù)據(jù)包的端到端傳輸時(shí)延，并且引起時(shí)延的較大波動(dòng)。文獻(xiàn)[3-4]分別針對(duì)幾種不同的按需路由協(xié)議和主動(dòng)路由協(xié)議進(jìn)行了較為全面的仿真比較，提出了各自的適用場(chǎng)景。然而，這兩篇文獻(xiàn)并沒(méi)有提出一種更為高效的路由算法。文獻(xiàn)[5]提出了一種對(duì)按需路由的改進(jìn)算法，通過(guò)檢測(cè)接收數(shù)據(jù)包的能量信息預(yù)測(cè)路由的不可用，進(jìn)而以主動(dòng)的方式對(duì)當(dāng)前路由進(jìn)行修復(fù)。但此算法仍然沒(méi)有解決反復(fù)尋路帶來(lái)的時(shí)延損耗。文獻(xiàn)[6-7]設(shè)計(jì)了類(lèi)似文獻(xiàn)[5]的路由策略，實(shí)質(zhì)上也僅僅是運(yùn)用主動(dòng)的策略加快路由修復(fù)過(guò)程。文獻(xiàn)[8-10]分別提出了幾種有關(guān)路由緩存的優(yōu)化策略，這在一定程度上可以減少路由尋路的次數(shù)。但在某些拓?fù)渥兓^快的應(yīng)用場(chǎng)景下，這些算法的適用性較低，并且無(wú)法保證當(dāng)前路由的最優(yōu)性。

為了平衡網(wǎng)絡(luò)的時(shí)延以及開(kāi)銷(xiāo)，不少的國(guó)內(nèi)外相關(guān)學(xué)者對(duì)混合路由進(jìn)行了研究。文獻(xiàn)[11]提出一種結(jié)合AODV和目的序號(hào)距離矢量(DSDV)路由協(xié)議的混合式路由算法，在兩跳范圍內(nèi)采用DSDV協(xié)議維護(hù)路由，兩跳之外采用AODV協(xié)議建立路由。文獻(xiàn)[12]提出了一種雙區(qū)域混合式路由協(xié)議，在區(qū)域內(nèi)執(zhí)行主動(dòng)路由策略，在區(qū)域外執(zhí)行按需路由策略。類(lèi)似的，文獻(xiàn)[13]將兩種路由進(jìn)行了結(jié)合，在區(qū)域內(nèi)運(yùn)用優(yōu)化鏈路狀態(tài)路由(OSLR)協(xié)議，在區(qū)域外運(yùn)用AODV協(xié)議。上述幾種算法都是在一定范圍之內(nèi)使用表驅(qū)動(dòng)路由協(xié)議，范圍之外使用按需路由協(xié)議，沒(méi)有考慮在區(qū)域內(nèi)或者區(qū)域外路由對(duì)不同業(yè)務(wù)的適應(yīng)性。

文獻(xiàn)[14]在針對(duì)區(qū)域路由協(xié)議(ZRP)在重疊區(qū)域重復(fù)接收路由控制消息造成的資源浪費(fèi)問(wèn)題，提出一種分層的區(qū)域路由協(xié)議(HZRP)，通過(guò)選舉群首的方式減少重疊區(qū)域范圍，但是算法沒(méi)有考慮到這種類(lèi)似分簇的方式對(duì)不同業(yè)務(wù)的適應(yīng)性。文獻(xiàn)[15]是一種以節(jié)點(diǎn)劃分的混合路由算法，該文將節(jié)點(diǎn)劃分為普通節(jié)點(diǎn)和特殊節(jié)點(diǎn)，通過(guò)特殊節(jié)點(diǎn)對(duì)普通節(jié)點(diǎn)的控制實(shí)現(xiàn)按需策略和主動(dòng)策略的結(jié)合。但該算法中的節(jié)點(diǎn)身份固定不變，無(wú)法適用于動(dòng)態(tài)變化的業(yè)務(wù)應(yīng)用場(chǎng)景。文獻(xiàn)[16] 提出了一種基于閾值的混合路由協(xié)議，它支持移動(dòng)節(jié)點(diǎn)選擇性地運(yùn)行路由協(xié)議，但算法中節(jié)點(diǎn)為了更好地選擇路由協(xié)議需要監(jiān)測(cè)網(wǎng)絡(luò)流量情況，且閾值難以動(dòng)態(tài)的適應(yīng)。文獻(xiàn)[17]以節(jié)點(diǎn)的尋路次數(shù)作為依據(jù)，用主動(dòng)更新路由表的方式維護(hù)那些高頻尋路的路徑，這在動(dòng)態(tài)變化的業(yè)務(wù)場(chǎng)景下存在一定的適用性。但該算法實(shí)質(zhì)上僅僅是一種路由緩存的優(yōu)化策略，在拓?fù)渥兓^快的場(chǎng)景下無(wú)法保持路由的最優(yōu)性。文獻(xiàn)[18]提出一種基于非均勻分簇的混合路由算法，該算法將網(wǎng)絡(luò)分成不均勻的邏輯簇，并且在簇內(nèi)使用樹(shù)路由、簇間在樹(shù)路由無(wú)效時(shí)采用一種改進(jìn)的AODV算法。但該算法目的是解決網(wǎng)絡(luò)中節(jié)點(diǎn)耗能不均衡的問(wèn)題。

基于以上分析，本文將基于AODV路由協(xié)議，針對(duì)動(dòng)態(tài)變化的業(yè)務(wù)應(yīng)用場(chǎng)景，設(shè)計(jì)一種更加高效的混合式路由算法：按需和主動(dòng)策略結(jié)合的AODV(POHR-AODV)路由協(xié)議。在此算法下，以主動(dòng)的策略維護(hù)網(wǎng)絡(luò)中被高頻使用的節(jié)點(diǎn)間路由，以按需的策略維護(hù)網(wǎng)絡(luò)中使用頻率較低的路由，以此來(lái)提高網(wǎng)絡(luò)的性能。必須說(shuō)明的是，本文的設(shè)計(jì)思路不僅僅適用于AODV，而且可以有效地應(yīng)用于其他路由，具有較強(qiáng)的適用性。

1 路由頻次不同場(chǎng)景下AODV路由協(xié)議存在的問(wèn)題

1.1 路由頻次不同場(chǎng)景的特點(diǎn)

1.1.1 存在中心節(jié)點(diǎn)

中心節(jié)點(diǎn)即為業(yè)務(wù)的匯聚節(jié)點(diǎn)。相對(duì)普通節(jié)點(diǎn)，網(wǎng)絡(luò)的中心節(jié)點(diǎn)往往存在較高的數(shù)據(jù)流量。

圖1 編隊(duì)通信Fig.1 Formation communication

圖1為一個(gè)簡(jiǎn)單的編隊(duì)通信場(chǎng)景。在編隊(duì)通信中，各單兵節(jié)點(diǎn)需要接收指揮官下達(dá)的命令，并且常常要向指揮官匯報(bào)情況。在此情況下，指揮官所在節(jié)點(diǎn)參與的交互數(shù)據(jù)流數(shù)量最多，并且數(shù)據(jù)流量最大，因此可以稱(chēng)作一個(gè)中心節(jié)點(diǎn)。

1.1.2 高頻次路由和低頻次路由

在Ad Hoc網(wǎng)絡(luò)中，每?jī)蓚€(gè)節(jié)點(diǎn)間的通信量、通信時(shí)間、以及通信頻率往往是不均等的。在一段時(shí)間內(nèi)，網(wǎng)絡(luò)中會(huì)存在某兩個(gè)節(jié)點(diǎn)經(jīng)常有數(shù)據(jù)交互的需求，而其他節(jié)點(diǎn)間數(shù)據(jù)交互微乎其微的情況。在這里將前者定義為高頻次路由，后者定義為低頻次路由。

在編隊(duì)通信應(yīng)用場(chǎng)景下，指揮官作為一個(gè)中心節(jié)點(diǎn)，其產(chǎn)生或者接收的數(shù)據(jù)流的交互頻率一般較高。所以在該網(wǎng)絡(luò)中，典型的高頻次路由有：?jiǎn)伪?-單兵2-指揮官；單兵2-指揮官；單兵3-指揮官；單兵4-指揮官。低頻次路由有：?jiǎn)伪?-單兵2-單兵3；單兵1-單兵2-單兵4；單兵3-單兵2-單兵4等。

1.2 AODV路由協(xié)議存在的問(wèn)題

1.2.1 反復(fù)尋路的問(wèn)題

在AODV路由協(xié)議中，路由的保持是以生存時(shí)間作為界定的。若在一條路由的生存時(shí)間內(nèi)沒(méi)有傳輸數(shù)據(jù)，則該路由失效，之后再下發(fā)數(shù)據(jù)則需要重新進(jìn)行尋路。在該機(jī)制下，發(fā)往某節(jié)點(diǎn)的數(shù)據(jù)包到達(dá)時(shí)間間隔大于其路由生存時(shí)間的幾率越大，則越容易出現(xiàn)反復(fù)尋路的狀況。單純地增加路由的生存時(shí)間可以在一定程度上減少按需路由的尋路頻率，然而在節(jié)點(diǎn)移動(dòng)的場(chǎng)景下，這可能會(huì)造成無(wú)效路由的存在或者當(dāng)存在更優(yōu)路由的時(shí)候無(wú)法更新。

1.2.2 無(wú)法保證最優(yōu)路由的問(wèn)題

在傳統(tǒng)的AODV協(xié)議中，在路由有效期間是不會(huì)尋找更優(yōu)路由進(jìn)行切換的。舉例而言，如圖2所示，之前的路由為0→1→2→3. 當(dāng)節(jié)點(diǎn)4移動(dòng)到0節(jié)點(diǎn)和3節(jié)點(diǎn)的通信范圍內(nèi)時(shí)，網(wǎng)絡(luò)中已經(jīng)存在跳數(shù)更優(yōu)的路由：0→4→3. 在AODV協(xié)議下，路由還會(huì)保持0→1→2→3進(jìn)行數(shù)據(jù)傳輸，而沒(méi)有進(jìn)行更優(yōu)路由的切換。

圖2 拓?fù)渥兓鸶鼉?yōu)路由Fig.2 Better route caused by topological change

1.3 其他路由協(xié)議存在的問(wèn)題

由于按需路由協(xié)議在路由策略上鮮明的特性，其他的按需路由協(xié)議(如DSR協(xié)議等)一般也都會(huì)存在反復(fù)尋路和無(wú)法保證最優(yōu)路由的問(wèn)題。另一方面，對(duì)于大多數(shù)主動(dòng)式路由協(xié)議而言(如DSDV協(xié)議、OSLR協(xié)議等)，其在動(dòng)態(tài)變化的業(yè)務(wù)場(chǎng)景下也會(huì)暴露出較為明顯的問(wèn)題。即當(dāng)網(wǎng)絡(luò)中存在中心節(jié)點(diǎn)并且存在較為明顯的高低頻次路由差異時(shí)，主動(dòng)路由策略在所有節(jié)點(diǎn)和所有路徑上花費(fèi)的控制開(kāi)銷(xiāo)是基本等同的。假設(shè)一個(gè)極端的情況，一個(gè)擁有30個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中只存在一條活躍的傳輸路徑(有傳輸?shù)臄?shù)據(jù)包)。那么在主動(dòng)式路由策略下，卻要花費(fèi)大量的控制開(kāi)銷(xiāo)去維護(hù)幾百條從來(lái)沒(méi)有用到過(guò)的路由，這明顯浪費(fèi)了過(guò)多的信道資源。除此之外，文獻(xiàn)[11-16]中提出的幾種混合式路由算法雖然可以在一定程度上平衡網(wǎng)絡(luò)的性能和開(kāi)銷(xiāo)，但卻無(wú)法對(duì)高頻次路由和低頻次路由做出高效的處理，不太適用于本文研究的在動(dòng)態(tài)變化的業(yè)務(wù)應(yīng)用場(chǎng)景。

下文將提出一種混合式AODV協(xié)議：POHR-AODV協(xié)議。在該算法中，節(jié)點(diǎn)通過(guò)前一時(shí)段的路由有效時(shí)長(zhǎng)和尋路頻率判斷一條路由是高頻還是低頻，并且用主動(dòng)的策略維護(hù)高頻次路由，用按需的策略維護(hù)低頻次路由。通過(guò)理論分析和仿真驗(yàn)證，該算法在動(dòng)態(tài)變化的業(yè)務(wù)下可以在很大程度上解決以上現(xiàn)有路由協(xié)議存在的問(wèn)題，提高系統(tǒng)的性能指標(biāo)。

2 POHR-AODV協(xié)議

2.1 主動(dòng)策略與按需策略的判別

在Ad Hoc網(wǎng)絡(luò)中，一組{源節(jié)點(diǎn)，目的節(jié)點(diǎn)}可以唯一確定一條路由。當(dāng)判斷一個(gè)源節(jié)點(diǎn)到一個(gè)目的節(jié)點(diǎn)之間的路由為高頻次路由時(shí)，POHR-AODV路由協(xié)議試圖主動(dòng)地維護(hù)它以此來(lái)提高網(wǎng)絡(luò)性能。一條路由是否高頻，這與兩個(gè)因素有較為直接的關(guān)系：一定時(shí)間內(nèi)路由的有效時(shí)間總長(zhǎng)度(設(shè)為t)和一定時(shí)間內(nèi)的尋路次數(shù)(設(shè)為f)。把整個(gè)時(shí)間軸分為以T為周期的時(shí)間段。以時(shí)間T為單位，在源節(jié)點(diǎn)分別統(tǒng)計(jì)t和f. 源節(jié)點(diǎn)通過(guò)統(tǒng)計(jì)建立路由到刪除路由的時(shí)間總和獲得有效時(shí)間總長(zhǎng)度t，如果時(shí)間T內(nèi)路由建立了兩次，那么有效時(shí)間總長(zhǎng)度t就是兩段時(shí)間構(gòu)成；源節(jié)點(diǎn)通過(guò)統(tǒng)計(jì)成功建立路由的次數(shù)獲得尋路次數(shù)。用t和f的統(tǒng)計(jì)結(jié)果來(lái)決定下一個(gè)T內(nèi)的路由策略(是按需模式還是主動(dòng)模式)：

(1)

式中：tth和fth為閾值。

在不考慮鏈路狀態(tài)變化因素時(shí)，對(duì)主動(dòng)路由協(xié)議DSDV協(xié)議、按需路由協(xié)議AODV協(xié)議和本文提出的混合式路由協(xié)議POHR-AODV協(xié)議的路由維護(hù)開(kāi)銷(xiāo)進(jìn)行如下分析：

DSDV協(xié)議的路由維護(hù)主要是通過(guò)周期性的控制消息將路由信息廣播給鄰居節(jié)點(diǎn)，則其不考慮鏈路狀態(tài)變化因素下的路由開(kāi)銷(xiāo)為

(2)

式中：Tc表示主動(dòng)維護(hù)的周期長(zhǎng)度；N表示網(wǎng)絡(luò)中節(jié)點(diǎn)的總個(gè)數(shù)。

AODV路由協(xié)議的開(kāi)銷(xiāo)可以分為第一次建立路由的開(kāi)銷(xiāo)、周期性發(fā)送Hello消息的開(kāi)銷(xiāo)和業(yè)務(wù)包到達(dá)時(shí)間間隔太大引起路由失效所產(chǎn)生的開(kāi)銷(xiāo)三部分。

在第一次建立路由時(shí)需要廣播RREQ(路由請(qǐng)求)消息，如果網(wǎng)絡(luò)中存在N個(gè)節(jié)點(diǎn)則RREQ消息會(huì)傳遞給每一個(gè)節(jié)點(diǎn)。當(dāng)目的節(jié)點(diǎn)收到RREQ消息之后進(jìn)行RREP(路由應(yīng)答)消息回復(fù)時(shí)，建立的路由有幾跳就需要傳遞多少個(gè)包，因此第一次建立開(kāi)銷(xiāo)為

CE=N+h，

(3)

式中：h表示成功建立路由的跳數(shù)。

周期性發(fā)送Hello消息的開(kāi)銷(xiāo)為

(4)

式中：THello表示Hello消息的發(fā)送周期。

假設(shè)網(wǎng)絡(luò)中的業(yè)務(wù)服從到達(dá)速率為λ的泊松分布，根據(jù)泊松分布性質(zhì)可知，兩個(gè)業(yè)務(wù)數(shù)據(jù)包之間的到達(dá)時(shí)間間隔服從參數(shù)為λ的指數(shù)分布，因此可以得到在單位時(shí)間T中因業(yè)務(wù)包到達(dá)時(shí)間間隔大于路由有效時(shí)間引起的路由尋路次數(shù)為

f=h·(e-λTs-e-λT)，

(5)

式中：Ts表示路由的有效時(shí)間。

每一次路由失效都會(huì)引起重新尋路，因此第三部分的開(kāi)銷(xiāo)為

CR=h·(e-λTs-e-λT)·(N+h)，

(6)

所以AODV路由協(xié)議的維護(hù)開(kāi)銷(xiāo)為

Con-demand=CE+CH+CR.

(7)

根據(jù)上面的分析可以得出，在本文提出的混合式路由協(xié)議POHR-AODV協(xié)議在主動(dòng)模式下的路由開(kāi)銷(xiāo)為

(8)

由第一次尋路的開(kāi)銷(xiāo)和周期性維護(hù)的開(kāi)銷(xiāo)兩部分組成。被動(dòng)模式下的路由開(kāi)銷(xiāo)為

Cpo=(N+h)+h·(e-λTs-e-λT)·(N+h).

(9)

由第一次尋路的開(kāi)銷(xiāo)和業(yè)務(wù)包達(dá)到時(shí)間間隔大于路由有效周期引起的重新尋路開(kāi)銷(xiāo)兩部分組成。根據(jù)(5)式可得

Cpo=(N+h)+f·(N+h).

(10)

當(dāng)Cpa小于Cpo時(shí)，就應(yīng)該切換到主動(dòng)模式，因此得到

(11)

假設(shè)在單位時(shí)間T內(nèi)除了路由失效之后重新建立路由的時(shí)間外，路由均存在并處于有效狀態(tài)，則t可以為

t=T-f·2(h·Tb)，

(12)

式中：Tb表示路由消息傳輸和處理的時(shí)延。

因此得到

(13)

在20個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，針對(duì)一個(gè)5跳的路由進(jìn)行閾值tth和fth的計(jì)算。單位時(shí)間T為1 000 ms，主動(dòng)維護(hù)周期為100 ms，路由消息傳輸和處理的時(shí)延為10 ms，得到fth為2，tth為800 ms. 也就是說(shuō)，在1 000 ms內(nèi)如果有一個(gè)路由進(jìn)行兩次以上的尋路，或者路由的有效時(shí)間總長(zhǎng)度超過(guò)800 ms，在下一個(gè)1 000 ms內(nèi)就應(yīng)該采用主動(dòng)模式，否則繼續(xù)使用按需模式。

文獻(xiàn)[19]為了解決由于節(jié)點(diǎn)移動(dòng)導(dǎo)致的重新尋路問(wèn)題提出一種基于AODV協(xié)議的路由維護(hù)機(jī)制，網(wǎng)絡(luò)中的節(jié)點(diǎn)需要周期性的去維護(hù)備份路由。這種改進(jìn)還是按需的一種維護(hù)，所以數(shù)據(jù)包到達(dá)時(shí)間間隔大于路由有效期這種情況還是無(wú)法避免的。從上面的分析中可以看出，在主動(dòng)維護(hù)策略下，周期性的維護(hù)可以避免數(shù)據(jù)包到達(dá)間隔對(duì)路由的影響。并且主動(dòng)的維護(hù)可以加快路由的更新速度，所以本文中主動(dòng)和按需結(jié)合的維護(hù)方式在節(jié)點(diǎn)移動(dòng)和數(shù)據(jù)包容易出現(xiàn)較大到達(dá)間隔時(shí)更優(yōu)。

2.2 主動(dòng)模式下的路由

在剛剛過(guò)去的時(shí)間T內(nèi)，當(dāng)源節(jié)點(diǎn)根據(jù)上文的方法判斷出某條路由為高頻次路由時(shí)，即可將該路由的維護(hù)方式切換為主動(dòng)模式。在主動(dòng)模式下，源節(jié)點(diǎn)和目的節(jié)點(diǎn)分別有不同的處理。

2.2.1 源節(jié)點(diǎn)處理

在傳統(tǒng)的AODV協(xié)議中，存在著3種路由控制消息：RREQ、RREP和RRER. 在本文設(shè)計(jì)的方案中，增加一條控制消息RCHA(路由切換模式)，源節(jié)點(diǎn)利用此消息通知目的節(jié)點(diǎn)進(jìn)行主動(dòng)模式和按需模式的切換。RCHA消息格式如圖3所示。

圖3 RCHA消息格式Fig.3 RCHA message format

Type：控制消息類(lèi)型，6.

Mode：下一個(gè)T內(nèi)的路由模式(主動(dòng)或者按需)。

Hops：從源節(jié)點(diǎn)到目的節(jié)點(diǎn)路由的總跳數(shù)。

Mode Lifetime：路由模式的有效時(shí)間。

在源節(jié)點(diǎn)判斷出下一個(gè)T內(nèi)該路由將使用主動(dòng)路由策略之后，首先查詢當(dāng)前路由是否有效。根據(jù)路由是否有效，分別有兩種處理：

1) 當(dāng)前路由有效時(shí)：源節(jié)點(diǎn)發(fā)送RCHA消息到目的節(jié)點(diǎn)來(lái)通知目的節(jié)點(diǎn)將路由切換至主動(dòng)模式。RCHA消息中的Mode置為1，表示主動(dòng)路由。Mode lifetime設(shè)為T(mén).T可以是一個(gè)在全網(wǎng)的定值，也可以在一定范圍內(nèi)不同的路由選取不同的值(Tmin≤T≤Tmax)。與其他3種控制消息不同的是，RCHA消息在中間節(jié)點(diǎn)不進(jìn)行處理，承載RCHA的IP包中的目的地址字段為路由的最終目的，生存時(shí)間ttl為路由總跳數(shù)。

2) 當(dāng)前路由無(wú)效時(shí)：當(dāng)查詢到路由已經(jīng)過(guò)期時(shí)，首先需要激發(fā)路由的尋路?？梢赃x擇在尋路成功之后再發(fā)送RCHA消息，但這種方式顯然是效率低的，因?yàn)榭刂葡⒁l(fā)送兩次。所以對(duì)RREQ消息進(jìn)行簡(jiǎn)單的修改，加入P標(biāo)志。源節(jié)點(diǎn)廣播帶有P標(biāo)志的RREQ(RREQ-P)，以此來(lái)完成尋路并告訴目的節(jié)點(diǎn)切換至主動(dòng)模式。

源節(jié)點(diǎn)以時(shí)間T為周期判斷下一個(gè)周期是否采用主動(dòng)路由策略。也就是說(shuō)，當(dāng)前路由為主動(dòng)時(shí)，源節(jié)點(diǎn)每個(gè)周期T都會(huì)發(fā)送一個(gè)RCHA消息(或者RREQ-P消息)通知目的節(jié)點(diǎn)下一個(gè)時(shí)間T內(nèi)的路由策略。

2.2.2 目的節(jié)點(diǎn)廣播RREP

目的節(jié)點(diǎn)維護(hù)一個(gè)統(tǒng)一的主動(dòng)路由標(biāo)志位：路由模式標(biāo)志位。當(dāng)它接收到源節(jié)點(diǎn)發(fā)送的RCHA消息或者RREQ-P消息后，將本節(jié)點(diǎn)切換至主動(dòng)路由模式。進(jìn)入主動(dòng)模式的目的節(jié)點(diǎn)需維護(hù)一個(gè)主動(dòng)路由的定時(shí)器，定時(shí)時(shí)間即為RCHA消息中的Mode lifetime字段。如果目的節(jié)點(diǎn)收到的是RREQ-P，則把定時(shí)時(shí)間設(shè)為T(mén)max. 在定時(shí)時(shí)間到達(dá)之前，如果收到新的RCHA消息，并且Mode字段為主動(dòng)，則重新置位定時(shí)器，延長(zhǎng)定時(shí)時(shí)間到Mode lifetime；若定時(shí)時(shí)間已到并且沒(méi)有收到新的RCHA消息，則將主動(dòng)模式切換成按需模式。

在主動(dòng)模式下，目的節(jié)點(diǎn)將有一個(gè)特殊的任務(wù)：周期性廣播RREP消息(傳統(tǒng)的AODV協(xié)議中RREP是單播傳輸?shù)?，告訴其他節(jié)點(diǎn)“我在這里”。廣播的RREP消息(RREP-f)的“Originator IP address”字段填寫(xiě)為廣播地址(0xFFFFFFFF)。承載RREP消息的IP包ttl值設(shè)為之前收到RCHA消息中的“Hops”。網(wǎng)絡(luò)中其他節(jié)點(diǎn)收到RREP后，更新本節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的路由，這當(dāng)然也包括之前發(fā)送RCHA消息的源節(jié)點(diǎn)。所以目的節(jié)點(diǎn)廣播RREP消息將會(huì)使得在“Hops”跳數(shù)內(nèi)的節(jié)點(diǎn)都會(huì)實(shí)時(shí)性地維護(hù)到達(dá)該目的節(jié)點(diǎn)的路由信息，這在某些情況下是非常有好處的。即，當(dāng)針對(duì)一個(gè)目的節(jié)點(diǎn)，同時(shí)存在多條到達(dá)該節(jié)點(diǎn)的高頻次路由時(shí)，此目的節(jié)點(diǎn)選取收到的多個(gè)RCHA消息中“Hops”最大的一個(gè)跳數(shù)作為廣播RREP的ttl值，這會(huì)在一次RREP廣播中同時(shí)實(shí)現(xiàn)多條高頻次路由的維護(hù)。這種新的方法會(huì)在網(wǎng)絡(luò)中存在業(yè)務(wù)中心節(jié)點(diǎn)的場(chǎng)景下發(fā)揮最大的作用。

3 協(xié)議具體描述和定性分析

3.1 協(xié)議具體描述

該小結(jié)將描述POHR-AODV協(xié)議下一條路由運(yùn)行的實(shí)例，主要描述該路由從按需模式切換為主動(dòng)模式再切換為按需模式的全過(guò)程。

如圖4所示，設(shè)源節(jié)點(diǎn)為0號(hào)節(jié)點(diǎn)，目的節(jié)點(diǎn)為3號(hào)節(jié)點(diǎn)。在網(wǎng)絡(luò)建立之初，路由默認(rèn)為按需模式。源節(jié)點(diǎn)0根據(jù)(1)式以周期T計(jì)算t和f值，并與閾值進(jìn)行比較。當(dāng)在某一時(shí)刻nT，0節(jié)點(diǎn)統(tǒng)計(jì)的t或f大于閾值時(shí)，0節(jié)點(diǎn)發(fā)送控制消息RCHA(其中Mode字段設(shè)置為1，表示主動(dòng)模式)，通知目的節(jié)點(diǎn)3進(jìn)行路由模式切換。節(jié)點(diǎn)3收到RCHA消息后，將本地的路由模式標(biāo)志位置為1(表示主動(dòng)模式)，自此以源節(jié)點(diǎn)為0，目的節(jié)點(diǎn)為3的路由從按需模式切換為主動(dòng)模式，如圖5所示。

圖4 傳統(tǒng)按需模式Fig.4 Traditional on-demand mode

圖5 目的節(jié)點(diǎn)切換至主動(dòng)模式Fig.5 Destination node switches to active mode

主動(dòng)模式下，節(jié)點(diǎn)3周期性廣播RREP消息(見(jiàn)圖6)，RREP中的“Originator IP address”字段填寫(xiě)為全F，IP包ttl值設(shè)置為所收到RCHA消息中“Hops”字段的最大值。在主動(dòng)模式下，當(dāng)節(jié)點(diǎn)4移動(dòng)到節(jié)點(diǎn)3的通信范圍內(nèi)時(shí)，相比之前的路由0→1→2→3，出現(xiàn)了跳數(shù)更優(yōu)的路由0→4→3. 此時(shí)，節(jié)點(diǎn)0將會(huì)同時(shí)收到來(lái)自節(jié)點(diǎn)1和節(jié)點(diǎn)4轉(zhuǎn)發(fā)的RREP-f消息。由于來(lái)自節(jié)點(diǎn)4的RREP-f經(jīng)過(guò)了2跳到達(dá)節(jié)點(diǎn)0，所以0節(jié)點(diǎn)將路由的路徑從0→1→2→3更改為0→4→3，實(shí)現(xiàn)路由的切換，如圖7所示。當(dāng)某一時(shí)刻mT，0節(jié)點(diǎn)統(tǒng)計(jì)的t和f值都小于閾值時(shí)，0節(jié)點(diǎn)再次發(fā)送控制消息RCHA(其中Mode字段設(shè)置為0，表示按需模式)，通知目的節(jié)點(diǎn)3進(jìn)行路由模式切換。節(jié)點(diǎn)3收到RCHA后，將路由模式標(biāo)志位置為0，停止廣播RREP，恢復(fù)為按需模式(見(jiàn)圖8)。協(xié)議詳細(xì)流程圖如圖9所示。

圖6 主動(dòng)模式下目的節(jié)點(diǎn)廣播RREPFig.6 Destination node broadcasts RREP in active mode

圖7 主動(dòng)模式下路由切換Fig.7 Routing switch in active mode

圖8 目的節(jié)點(diǎn)恢復(fù)至按需模式Fig.8 Destination node back to on-demand mode

圖9 協(xié)議流程圖Fig.9 Flow chat of protocol

3.2 定性分析

POHR-AODV協(xié)議的核心思想是用主動(dòng)的策略維護(hù)高頻次路由，以此降低高頻次路由上路由尋路的次數(shù)，改善網(wǎng)絡(luò)中數(shù)據(jù)包的端到端平均傳輸時(shí)延。這實(shí)質(zhì)上是犧牲一部分控制開(kāi)銷(xiāo)去維護(hù)具有較高利用頻率的路由，提高了控制信道的利用率。POHR-AODV協(xié)議的最大特色是實(shí)現(xiàn)了主動(dòng)模式和按需模式的動(dòng)態(tài)切換，這種切換明顯增加了該算法的適用范圍。當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流量較低時(shí)，通過(guò)計(jì)算得出的高頻次路由較少，POHR-AODV協(xié)議趨近于按需路由；當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流量較高時(shí)，通過(guò)計(jì)算得出的高頻次路由較多，POHR-AODV協(xié)議趨近于主動(dòng)式路由。POHR-AODV協(xié)議路由模式的動(dòng)態(tài)切換使得按需策略在控制開(kāi)銷(xiāo)方面的優(yōu)勢(shì)和主動(dòng)策略在端到端時(shí)延方面的優(yōu)勢(shì)發(fā)揮到最佳。算法中對(duì)t和f值周期性的統(tǒng)計(jì)使得路由模式的切換頻率被控制在1/T以內(nèi)，這有效地降低了由于模式頻繁切換對(duì)系統(tǒng)性能造成的影響。對(duì)于一條路由而言，相比按需模式，主動(dòng)模式往往會(huì)帶來(lái)更多的控制開(kāi)銷(xiāo)。但當(dāng)網(wǎng)絡(luò)中存在較為明顯的中心節(jié)點(diǎn)時(shí)，以該中心節(jié)點(diǎn)作為目的節(jié)點(diǎn)的多條路由卻可以通過(guò)一次RREP消息的廣播進(jìn)行維護(hù)。相比按需路由中多次的RREQ廣播尋路，這反而在一定程度上降低了控制開(kāi)銷(xiāo)。主動(dòng)模式下目的節(jié)點(diǎn)對(duì)RREP消息的周期性廣播帶來(lái)的另外一個(gè)好處就是可以實(shí)現(xiàn)路由向最優(yōu)路徑的動(dòng)態(tài)切換，這是按需策略無(wú)法實(shí)現(xiàn)的。

4 仿真分析

根據(jù)上文設(shè)計(jì)的POHR-AODV路由協(xié)議，基于NS2網(wǎng)絡(luò)仿真平臺(tái)，搭建具有動(dòng)態(tài)變化的業(yè)務(wù)流的仿真環(huán)境對(duì)其進(jìn)行性能分析。通過(guò)計(jì)算網(wǎng)絡(luò)的端到端平均時(shí)延和控制開(kāi)銷(xiāo)，對(duì)比POHR-AODV協(xié)議、AODV協(xié)議、ZRP協(xié)議的路由性能。

4.1 仿真場(chǎng)景

NS2仿真中MAC層協(xié)議使用IEEE 802.11標(biāo)準(zhǔn)，基本的仿真參數(shù)如表1所示。

表1 仿真參數(shù)表Tab.1 Simulation parameters

除此之外，T設(shè)置為50 s，tth和fth分別設(shè)置為25和5. 根據(jù)3.1節(jié)中動(dòng)態(tài)變化的業(yè)務(wù)流的特點(diǎn)，對(duì)CBR(恒定比特流)數(shù)據(jù)流進(jìn)行特殊設(shè)置，產(chǎn)生動(dòng)態(tài)變化的業(yè)務(wù)流場(chǎng)景。在10條CBR數(shù)據(jù)流中，將其中5條的目的節(jié)點(diǎn)設(shè)置為2號(hào)節(jié)點(diǎn)，再將另外5條的目的節(jié)點(diǎn)設(shè)置為3號(hào)節(jié)點(diǎn)。因此，2號(hào)節(jié)點(diǎn)和3號(hào)節(jié)點(diǎn)可以看做網(wǎng)絡(luò)的中心節(jié)點(diǎn)。另外，對(duì)數(shù)據(jù)流的產(chǎn)生和結(jié)束時(shí)間進(jìn)行特殊的設(shè)置，使得產(chǎn)生斷斷續(xù)續(xù)非均勻的業(yè)務(wù)流。

4.2 仿真結(jié)果分析

本文選擇兩個(gè)最常用的指標(biāo)來(lái)評(píng)估協(xié)議的性能，它們分別是端到端平均時(shí)延和控制開(kāi)銷(xiāo)，具體計(jì)算方法如下：

端到端時(shí)延=收到數(shù)據(jù)包的總時(shí)延╱目的節(jié)點(diǎn)接收的數(shù)據(jù)包數(shù)；

控制開(kāi)銷(xiāo)=發(fā)送和轉(zhuǎn)發(fā)的控制包數(shù)╱目的節(jié)點(diǎn)接收的數(shù)據(jù)包數(shù)。

如圖10所示，從中可以明顯地看出：1)相比傳統(tǒng)的按需路由協(xié)議AODV協(xié)議，混合路由協(xié)議POHR-AODV協(xié)議將平均傳輸時(shí)延降低約20%；2)相比ZRP協(xié)議，POHR-AODV協(xié)議在時(shí)延方面也具有一定的優(yōu)勢(shì)；隨著移動(dòng)速度的增加，ZRP協(xié)議的時(shí)延增長(zhǎng)較快，而POHR-AODV協(xié)議相對(duì)較為穩(wěn)定。

圖10 端到端時(shí)延對(duì)比Fig.10 End-to-end delay

POHR-AODV協(xié)議具有時(shí)延方面優(yōu)勢(shì)的主要原因是網(wǎng)絡(luò)當(dāng)中的高頻次路由被主動(dòng)維護(hù)，并且算法能夠及時(shí)地將當(dāng)前路由向更優(yōu)的路由(跳數(shù)更少)進(jìn)行切換。而ZRP協(xié)議是以區(qū)域劃分的混合路由協(xié)議，在動(dòng)態(tài)變化的業(yè)務(wù)場(chǎng)景下不具有針對(duì)性。

如圖11所示，3種路由算法的開(kāi)銷(xiāo)對(duì)比：1)當(dāng)移動(dòng)速度小于10 m/s時(shí)，相比其他兩種混合路由協(xié)議，AODV協(xié)議在開(kāi)銷(xiāo)方面有著一定的優(yōu)勢(shì)；2)當(dāng)節(jié)點(diǎn)移動(dòng)速率大于10 m/s時(shí)，AODV協(xié)議的開(kāi)銷(xiāo)增長(zhǎng)幅度較大，而POHR-AODV協(xié)議的開(kāi)銷(xiāo)明顯低于其他兩種協(xié)議；3)POHR-AODV協(xié)議在開(kāi)銷(xiāo)方面優(yōu)于ZRP協(xié)議。

圖11 控制開(kāi)銷(xiāo)對(duì)比Fig.11 Control overhead

當(dāng)節(jié)點(diǎn)移動(dòng)速率較低時(shí)，傳統(tǒng)的AODV協(xié)議幾乎不需要進(jìn)行路由的修復(fù)，按需路由在開(kāi)銷(xiāo)方面的優(yōu)勢(shì)較為明顯；然而，當(dāng)節(jié)點(diǎn)移動(dòng)速度不斷增大時(shí)，AODV協(xié)議的尋路過(guò)程不斷增多，廣播過(guò)程頻繁。而對(duì)于POHR-AODV協(xié)議而言，中心節(jié)點(diǎn)的一次廣播即可以完成多跳路由的更新與維護(hù)，這在很大程度上節(jié)省了控制包的數(shù)量，所以控制開(kāi)銷(xiāo)低于AODV協(xié)議。這是RREP廣播機(jī)制所起的重要作用。相比POHR-AODV協(xié)議，ZRP協(xié)議網(wǎng)絡(luò)中的各節(jié)點(diǎn)都會(huì)以主動(dòng)的方式維護(hù)域內(nèi)路由，所需的控制消息較多，所以開(kāi)銷(xiāo)相對(duì)較大。

5 結(jié)論

本文面向MANET中動(dòng)態(tài)變化的業(yè)務(wù)應(yīng)用場(chǎng)景，基于AODV路由協(xié)議，提出了一種按需和主動(dòng)相結(jié)合的混合式路由協(xié)議：POHR-AODV協(xié)議。在POHR-AODV協(xié)議中，主動(dòng)模式用于維護(hù)網(wǎng)絡(luò)中的高頻次路由，按需模式用于維護(hù)網(wǎng)絡(luò)中的低頻次路由。通過(guò)定性分析和仿真驗(yàn)證可以得出以下結(jié)論：在動(dòng)態(tài)變化的業(yè)務(wù)場(chǎng)景下，相比傳統(tǒng)AODV路由協(xié)議以及區(qū)域型混合路由協(xié)議ZRP協(xié)議，POHR-AODV協(xié)議可以在合理控制網(wǎng)絡(luò)開(kāi)銷(xiāo)的同時(shí)，降低數(shù)據(jù)包的端到端平均傳輸時(shí)延。

References)

[1] Perkins C E, Royer E M. Ad-hoc on-demand distance vector routing.[C]∥The Workshop on Mobile Computing Systems and Applications. Menlo Park, CA, US:IEEE,1999:90-100.

[2] Johnson D B, Maltz D A. Dynamic source routing in ad hoc wireless networks[C]∥Mobile Computing. US:IEEE,1996:153-181.

[3] Razouqi Q, Boushehri A, Gaballah M, et al. Extensive simulation performance analysis for DSDV, DSR and AODV MANET routing protocols[C] ∥ 27th International Conference on Advanced Information Networking and Applications Workshops. Safat, Kuwait: IEEE, 2013:335-342.

[4] Feiroz Khan T H, Sivakumar D. Performance of AODV, DSDV and DSR protocols in mobile wireless mesh networks[C]∥2nd International Conference on Current Trends in Engineering and Technology. Chennai, India: IEEE, 2014:397-399.

[5] Goff T, Abu-Ghazaleh N B, Phatak D S, et al. Preemptive routing in Ad Hoc networks[C]∥7th Annual International Conference. New York, NY, USA:ACM,2001:43-52.

[6] Catalan-Cid M, Gomez C, Paradells J, et al. DEMON: preemptive route recovery for AODV in multi-hop wireless networks based on performance degradation monitoring[J]. EURASIP Journal on Wireless Communications and Networking, 2013:286(18): 4047-4064.

[7] Rokonuzzaman S M, Pose R, Gondal I. A warning based preemptive routing scheme for QoS maintenance in wireless ad hoc networks[C]∥Proceedings of the 6th ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks. Tenerife, Canary Islands, Spain:ACM, 2009:27-32.

[8] Sakeena B, Eklarker R, Kohir V V, et al. QoS aware routing protocol to improve route maintenance in mobile ad-hoc networks[C]∥2013 International Conference on Emerging Trends in Communication, Control, Signal Processing and Computing Applications. Bangalore, India: IEEE,2013:281-285.

[9] Gupta S K, Sharma R, Saket R K. Effect of variation in active route timeout and delete period constant on the performance of AODV protocol [J]. International Journal of Mobile Communications, 2014, 12(2):177-191.

[10] Srinivasan P, Kamalakkannan P. Enhancing route maintenance in RSEA-AODV for mobile ad hoc networks[C]∥2013 7th International Conference on Intelligent Systems and Control (ISCO). Gulbarga, India:IEEE,2013:464-469.

[11] 彭忠全, 朱昌洪. 基于無(wú)線mesh網(wǎng)絡(luò)混合路由協(xié)議的優(yōu)化[J]. 大眾科技, 2013(12):46-48. PENG Zhong-quan, ZHU Chang-hong. Based on an improved routing protocol for wireless mesh network[J]. Popular Science & Technology, 2013(12):46-48. (in Chinese)

[12] Wang L, Olariu S. A two-zone hybrid routing protocol for mobile ad hoc networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(12):1105-1116.

[13] Wu S, Tan X, Jia S. AOHR: AODV and OLSR hybrid routing protocol for mobile ad hoc networks[C]∥International Conference on Communications, Circuits and Systems. Beijing, China: IEEE, 2006:1487-1491.

[14] 張希婕. Ad Hoc網(wǎng)絡(luò)混合路由協(xié)議的研究[D]. 北京：北京郵電大學(xué), 2015. ZHANG Xi-jie. The research of hybrid routing protocol in mobile ad hoc network[D]. Beijing: Beijing University of Posts and Telecommunications, 2015. (in Chinese)

[15] Roy S, Garcia-Luna-Aceves J J. Node-centric hybrid routing for ad-hoc wireless extensions of the Internet[C]∥Global Telecommunications Conference. Santa Cruz, CA, US:IEEE, 2002:183-187.

[16] Nair R R, Gandhi S I. Performance analysis of threshold based hybrid routing protocol for MANET[C]∥International Conference on Signal Processing, Communication and Networking. Chennai, India:IEEE, 2015.

[17] Dargahi T, Rahmani A M, Khademzadeh A. SP-AODV: a semi-proactive AODV routing protocol for wireless networks[C]∥International Conference on Advanced Computer Theory and Engineering. Phuket, Thailand: IEEE, 2008:613-617.

[18] 白樂(lè)強(qiáng), 王玉濤. 基于非均勻分簇機(jī)制的ZigBee混合路由算法[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(1):81-86. BAI Le-qiang,WANG Yu-tao. ZigBee hybrid routing algorithm based on uneven clustering mechanism[J]. Journal of Computer Applications， 2016, 36(1):81-86.(in Chinese)

[19] 王帥. 一種基于相對(duì)移動(dòng)性和鏈路穩(wěn)定性的AODV路由算法的研究與仿真[D]. 上海：東華大學(xué), 2015. WANG Shuai. A research and implementation of an AODV routing protocol based on relative mobility and links’ stability[D]. Shanghai:Donghua University, 2015. (in Chinese)

A Hybrid Routing Protocol for Differentiating Route Frequencies in MANET

LI Xu1, HE Hao-xiong1, PENG Jin-lin2, SONG Gu-yang1, SHAO Xiao-tao1

(1.School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044，China;2.Beijing Institute of Tracking and Telecommunication Technology, Beijing 100094, China)

As a result of the widely use of mobile Ad Hoc network (MANET) in formation communication and emergency communication, the high and low frequency routes appear in real situations. In these scenarios, no matter what routing protocol is used, on-demand routing protocols or proactive routing protocols always use fixed maintenance strategy, and obviously none of them can bring their advantages into play. Regarding this scenario, a totally new hybrid routing algorithm is put forward based on Ad Hoc on-demand distance vector (AODV) routing protocol, which makes use of both on-demand and proactive strategies. In this new protocol, the high frequency route is obtained by estimating the traffic flow to maintain the frequently used route through proactive strategy and deal with the low frequency route with on-demand strategy. The qualitative analysis and simulation show that the new hybrid routing algorithm makes the end-to-end packet average transmission delay is reduced by about 20% when compared with AODV protocol.

ordnance science and technology; mobile Ad Hoc network; hybrid routing protocol; Ad Hoc on-demand distance vector routing

2016-06-20

國(guó)家自然科學(xué)基金項(xiàng)目(61371068)； 國(guó)家“863”計(jì)劃項(xiàng)目(2015AA01A705)； 國(guó)家科技支撐計(jì)劃項(xiàng)目(2014BAK02B04)

李旭(1970—)， 女， 教授， 博士生導(dǎo)師。 E-mail: xli@bjtu.edu.cn； 何浩雄(1992—)， 男， 碩士研究生。 E-mail: 14120067@bjtu.edu.cn

TP393.04

A

1000-1093(2016)12-2308-09

10.3969/j.issn.1000-1093.2016.12.017