李旭， 何浩雄， 彭進霖， 宋顧楊， 邵小桃

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

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

李旭1， 何浩雄1， 彭進霖2， 宋顧楊1， 邵小桃1

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

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

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

0 引言

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

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

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

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

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

1 路由頻次不同場景下AODV路由協(xié)議存在的問題

1.1 路由頻次不同場景的特點

1.1.1 存在中心節(jié)點

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

圖1 編隊通信Fig.1 Formation communication

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

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

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

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

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

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

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

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

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

圖2 拓撲變化引起更優(yōu)路由Fig.2 Better route caused by topological change

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

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

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

2 POHR-AODV協(xié)議

2.1 主動策略與按需策略的判別

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

(1)

式中：tth和fth為閾值。

在不考慮鏈路狀態(tài)變化因素時，對主動路由協(xié)議DSDV協(xié)議、按需路由協(xié)議AODV協(xié)議和本文提出的混合式路由協(xié)議POHR-AODV協(xié)議的路由維護開銷進行如下分析：

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

(2)

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

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

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

CE=N+h，

(3)

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

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

(4)

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

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

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

(5)

式中：Ts表示路由的有效時間。

每一次路由失效都會引起重新尋路，因此第三部分的開銷為

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

(6)

所以AODV路由協(xié)議的維護開銷為

Con-demand=CE+CH+CR.

(7)

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

(8)

由第一次尋路的開銷和周期性維護的開銷兩部分組成。被動模式下的路由開銷為

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

(9)

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

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

(10)

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

(11)

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

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

(12)

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

因此得到

(13)

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

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

2.2 主動模式下的路由

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

2.2.1 源節(jié)點處理

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

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

Type：控制消息類型，6.

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

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

Mode Lifetime：路由模式的有效時間。

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

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

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

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

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

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

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

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

3.1 協(xié)議具體描述

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

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

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

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

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

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

圖7 主動模式下路由切換Fig.7 Routing switch in active mode

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

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

3.2 定性分析

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

4 仿真分析

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

4.1 仿真場景

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é)中動態(tài)變化的業(yè)務(wù)流的特點，對CBR(恒定比特流)數(shù)據(jù)流進行特殊設(shè)置，產(chǎn)生動態(tài)變化的業(yè)務(wù)流場景。在10條CBR數(shù)據(jù)流中，將其中5條的目的節(jié)點設(shè)置為2號節(jié)點，再將另外5條的目的節(jié)點設(shè)置為3號節(jié)點。因此，2號節(jié)點和3號節(jié)點可以看做網(wǎng)絡(luò)的中心節(jié)點。另外，對數(shù)據(jù)流的產(chǎn)生和結(jié)束時間進行特殊的設(shè)置，使得產(chǎn)生斷斷續(xù)續(xù)非均勻的業(yè)務(wù)流。

4.2 仿真結(jié)果分析

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

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

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

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

圖10 端到端時延對比Fig.10 End-to-end delay

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

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

圖11 控制開銷對比Fig.11 Control overhead

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

5 結(jié)論

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

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] 彭忠全, 朱昌洪. 基于無線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] 白樂強, 王玉濤. 基于非均勻分簇機制的ZigBee混合路由算法[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] 王帥. 一種基于相對移動性和鏈路穩(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

國家自然科學(xué)基金項目(61371068)； 國家“863”計劃項目(2015AA01A705)； 國家科技支撐計劃項目(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