基于可靠路徑穩(wěn)定性估計(jì)的MANET路由發(fā)現(xiàn)算法研究

李智楠，楊曉冬,2

（1. 哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江 哈爾濱 150001；2. 日本明星大學(xué)聯(lián)合研究中心，日本 東京 191-8506）

基于可靠路徑穩(wěn)定性估計(jì)的MANET路由發(fā)現(xiàn)算法研究

李智楠1，楊曉冬1,2

（1. 哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江 哈爾濱 150001；2. 日本明星大學(xué)聯(lián)合研究中心，日本 東京 191-8506）

提出一種基于可靠路徑剩余生存期（RPL,residual path lifetime）估計(jì)的 MANET路由發(fā)現(xiàn)算法（RLE-RPLP），該算法充分考慮相鄰鏈路剩余生存期相關(guān)性，建立優(yōu)化的多跳路徑 RPL統(tǒng)計(jì)特性分析，提供了更可靠的路由穩(wěn)定性評(píng)估。通過仿真分別與忽略鏈路RLL相關(guān)性的源路由協(xié)議及已有穩(wěn)定性路由協(xié)議進(jìn)行對(duì)比。仿真結(jié)果表明，RLE-RPLP算法能有效提高網(wǎng)絡(luò)吞吐量并減少路由重建次數(shù)；當(dāng)節(jié)點(diǎn)移動(dòng)度較高或網(wǎng)絡(luò)負(fù)載較大時(shí)，在吞吐量、路由開銷等方面均優(yōu)于已有的穩(wěn)定性路由對(duì)比算法。

移動(dòng)ad hoc網(wǎng)絡(luò)；鏈路剩余生存期；移動(dòng)相關(guān)性；路徑剩余生存期；穩(wěn)定性估計(jì)

1 引言

移動(dòng)ad hoc網(wǎng)絡(luò)（MANET）摒棄了蜂窩網(wǎng)絡(luò)昂貴的底層基站及相關(guān)基礎(chǔ)設(shè)施建設(shè)，實(shí)現(xiàn)了移動(dòng)節(jié)點(diǎn)分布式動(dòng)態(tài)組網(wǎng)、自主處理的優(yōu)越性能。節(jié)點(diǎn)間路徑可靠性評(píng)估是決定MANET路由優(yōu)化算法有效性及網(wǎng)絡(luò)連通性的關(guān)鍵因素之一。由于MANET網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)特性，多跳路徑都具備一定的路徑剩余生存期（RPL,residual path lifetime）[1]，即從路徑建立或傳輸過程中某時(shí)刻至構(gòu)成該路徑的任一條鏈路初次發(fā)生中斷的時(shí)間間隔。在主動(dòng)式路由機(jī)制（proactive routing protocols）中，準(zhǔn)確估計(jì)RPL可使算法在路徑中斷之前啟動(dòng)新的路徑發(fā)現(xiàn)進(jìn)程來保證節(jié)點(diǎn)間數(shù)據(jù)尤其是數(shù)據(jù)流業(yè)務(wù)的傳輸連續(xù)性；在反應(yīng)式路由機(jī)制（reactive routing protocols）中，RPL的過高估計(jì)會(huì)導(dǎo)致路由算法頻繁地啟動(dòng)路由修復(fù)或重建進(jìn)程，降低網(wǎng)絡(luò)通信質(zhì)量，增加傳輸延時(shí)和資源消耗。因此，可靠的RPL估計(jì)是MANET路由機(jī)制優(yōu)化和完善的關(guān)鍵因素。

文獻(xiàn)[1～8]提出了基于可靠路徑估計(jì)的路由策略。而作為多跳路徑構(gòu)成基礎(chǔ)的鏈路剩余生存期（RLL,residual link lifetime）估計(jì)理論也得到深入探討[9～13]。越來越多的路由優(yōu)化策略及MANET現(xiàn)實(shí)應(yīng)用[4,5,14]側(cè)重于RLL統(tǒng)計(jì)特性[1,15,16]描述，但相鄰鏈路 RLL相關(guān)性對(duì)路徑穩(wěn)定性評(píng)估的影響還沒有得到足夠重視。

文獻(xiàn)[16]在文獻(xiàn)[15]的基礎(chǔ)上指出，路徑生存期可以表示為各條鏈路生存期倒數(shù)之和，但兩者均以鏈路獨(dú)立性為前提。文獻(xiàn)[1]將上述條件改進(jìn)為一種漸進(jìn)性條件，即RLL相關(guān)性會(huì)隨路徑跳數(shù)及平均鏈路長度的增加而減弱。然而以該理論為基礎(chǔ)的RPL估計(jì)算法，并不適用于對(duì)路徑跳數(shù)有嚴(yán)格限制的普遍情況。文獻(xiàn)[4]提出了詳細(xì)的鏈路及路徑持續(xù)時(shí)間的理論分析模型，但推導(dǎo)設(shè)定所有節(jié)點(diǎn)移動(dòng)速率相等且為常量，限制了理論實(shí)用性且很大程度上降低了相鄰鏈路相關(guān)性約束。上述RPL預(yù)測的問題也同樣存在于 ad hoc網(wǎng)絡(luò)的實(shí)際擴(kuò)展應(yīng)用場景中，如VANET[5,17]、車聯(lián)網(wǎng)系統(tǒng)（connected vehicles）[18]及航空通信網(wǎng)絡(luò)[14,19]。文獻(xiàn)[20]強(qiáng)調(diào)了 RLL相關(guān)性的重要意義并將其用于平均路徑生存期估計(jì) PDMP（piecewise deterministic Markov process）理論建模當(dāng)中，然而離散的節(jié)點(diǎn)運(yùn)動(dòng)參數(shù)（速率和移動(dòng)方向）必須作為滿足數(shù)值分析的限制條件，同樣不符合實(shí)際情況。

為了在路由機(jī)制中充分引入相鄰鏈路 RLL相關(guān)性進(jìn)而提供更準(zhǔn)確的路徑可靠性評(píng)估標(biāo)準(zhǔn)，本文首先提出了一種RLL相關(guān)性統(tǒng)計(jì)建模方法，在節(jié)點(diǎn)移動(dòng)模型不受限的情況下給出多跳路徑中各鏈路RLL聯(lián)合概率密度分布（PDF）表達(dá)式，在此基礎(chǔ)上提出一種基于可靠 RPL估計(jì)的路由發(fā)現(xiàn)算法（RLE-RPLP），該算法完善了路由發(fā)現(xiàn)進(jìn)程中路徑RPL的判斷標(biāo)準(zhǔn)，因而能夠減少路由失效頻率。仿真分析將 RLE-RPLP與另外 2種路由算法進(jìn)行對(duì)比，分別為忽略鏈路RLL相關(guān)性條件下的源路由協(xié)議及文獻(xiàn)[19]提出的穩(wěn)定性路由協(xié)議。通過性能對(duì)比驗(yàn)證了RLE-RPLP在提高網(wǎng)絡(luò)吞吐量、減少路由重建次數(shù)及路由開銷方面的有效性以及對(duì)基于路徑穩(wěn)定性路由算法的優(yōu)化作用。

2 基于RLL相關(guān)性的RPL統(tǒng)計(jì)特性分析

由于節(jié)點(diǎn)共享，MANET同一路徑中相鄰鏈路RLL相關(guān)性是RPL估計(jì)的關(guān)鍵因素。文獻(xiàn)[20]強(qiáng)調(diào)并驗(yàn)證了這一觀點(diǎn)。本文提出一種鏈路RLL相關(guān)性統(tǒng)計(jì)建模方法，利用隨機(jī)理論給出多跳路徑中各鏈路RLL聯(lián)合PDF明確表達(dá)式，該方法不以特定的節(jié)點(diǎn)移動(dòng)模型為限制，為路徑穩(wěn)定性提供更可靠的評(píng)估參考。

首先構(gòu)建簡化路由模型，如圖1(a)所示，并簡要證明相鄰鏈路RLL相關(guān)性。設(shè)節(jié)點(diǎn)N1、N2、N3構(gòu)成 2條相鄰鏈路 k1(N1?N2)、k2(N2?N3)。某時(shí)刻N(yùn)i移動(dòng)速率Vi及方向θi任意。實(shí)際上鏈路RLL主要受限于其 2個(gè)端節(jié)點(diǎn)的剩余能量和兩者相對(duì)距離，顯然，若圖1中僅N1或N3變化，k1和k2的RLL不會(huì)同時(shí)受到影響；而若k1和k2的共享節(jié)點(diǎn)N2能量消耗或隨機(jī)移動(dòng)，都會(huì)同時(shí)導(dǎo)致兩者RLL發(fā)生變化，因此k1、k2的RLL的PDF相關(guān)性普遍存在。本文著重對(duì)節(jié)點(diǎn)隨機(jī)移動(dòng)引起的相鄰鏈路 RLL相關(guān)性進(jìn)行分析并應(yīng)用于路由優(yōu)化策略。

圖1 子鏡頭分割流程

首先推導(dǎo)鏈路k1剩余生存期RLL1的PDF表達(dá)式。如圖1所示，設(shè)R為節(jié)點(diǎn)傳輸半徑，N2為坐標(biāo)參考點(diǎn)，V2平行于正x軸。初始時(shí)刻（t=0）N1位置與N2距離為d1(d1＜R)，與負(fù)x軸夾角為α且α服從(0,2π)均勻分布(α～U(0,2π))。若某時(shí)刻t1，兩節(jié)點(diǎn)間距首次超過R，則鏈路中斷，RLL1=T1=t1。θ 為V1與V2夾角且θ～U(?π,π)；

顯然，V1、V2、θ相互獨(dú)立，有

其中，v1、?分別代表隨機(jī)變量 V1、θ某一特定取值（下同），V、φ分別表示N1、N2間相對(duì)速度及V與 x軸的夾角，φ∈(?π,π)。文獻(xiàn)[19]中首先給出三維空間中2相鄰節(jié)點(diǎn)相對(duì)速率的PDF表達(dá)式，進(jìn)而推導(dǎo)出鏈路生存期的累積概率密度分布(CDF)和單條鏈路生存期期望值。上述推導(dǎo)均以V與φ相互獨(dú)立為前提，而實(shí)際上兩者存在統(tǒng)計(jì)相關(guān)性且不可忽略，證明如下：首先從直觀上分析，根據(jù)圖 1(b)顯然可以看出，V取決于V1、V2，而φ與有關(guān)，因此必然與V有關(guān)，兩者不可能是獨(dú)立的。具體而言，利用圖1中各參數(shù)幾何關(guān)系可得

φ同樣為V1、V2、θ的函數(shù)，且當(dāng)三者取值范圍變化時(shí)，函數(shù)對(duì)應(yīng)關(guān)系也隨之變化。為便于證明，討論當(dāng) θ∈[0,π)∩ (V1cosθ ?V2＞0)的情況（對(duì)應(yīng)圖 1（b）），此時(shí)有

由式(1)和式(2)可見，V1、V2、θ中任一參數(shù)發(fā)生變化均同時(shí)影響 V、φ取值，因此兩者相互獨(dú)立的假設(shè)并不成立。其次，考察V、φ相關(guān)系數(shù)

其中，Cov(·)和 Var(·)分別表示協(xié)方差和方差函數(shù)。利用仿真方法進(jìn)行每組(v1,v2)采樣點(diǎn)下10 000次隨機(jī)實(shí)驗(yàn)，每次實(shí)驗(yàn)規(guī)定θ在(0,π)隨機(jī)取值并求解式(3)，將所有實(shí)驗(yàn)結(jié)果的平均值作為各坐標(biāo)點(diǎn)對(duì)應(yīng)的相關(guān)系數(shù)。圖2給出仿真結(jié)果，從圖中可以直觀看出，V、φ相關(guān)系數(shù)大多在0.5左右，這一結(jié)果有力證明了即使在V1、V2互不相關(guān)的條件下，V和φ的統(tǒng)計(jì)相關(guān)性依然存在且不可忽略。

圖2 V和φ相關(guān)系數(shù)仿真結(jié)果

針對(duì)文獻(xiàn)[19]中的問題，本文給出改進(jìn)后的鏈路剩余生存期 PDF推導(dǎo)過程。首先設(shè) F(·)為 CDF表達(dá)式，則引用文獻(xiàn)[19]將表示為

其中，P(·)為概率函數(shù)。當(dāng) V2為定值，V、φ均由V1和θ給定，有

其中，f(·)為 PDF函數(shù)。根據(jù) Jacobian轉(zhuǎn)換，可得如下條件PDF表達(dá)式

代入式(6)，可得

若假設(shè) V1～U (Vmin,Vmax)，則有

代入式(5)并對(duì)t1求導(dǎo)，可得RLL1條件PDF表達(dá)式為

利用Leibniz法則將式(7)簡化為一重積分，可得

進(jìn)而可得RLL1的PDF表達(dá)式為

本文進(jìn)一步給出考慮鏈路 RLL相關(guān)性的路徑RPL統(tǒng)計(jì)分析。與式(8)推導(dǎo)方法類似，因此當(dāng)V2取定值，k1和k2剩余生存期RLL1和RLL2的聯(lián)合條件PDF表達(dá)式為

對(duì) V2求積分，可得 RLL1及 RLL2的聯(lián)合 PDF表達(dá)式為

進(jìn)一步地，若路徑由3條鏈路構(gòu)成，它們各自RLL的聯(lián)合PDF可表示為

以此類推。

本文將路徑統(tǒng)計(jì)特性進(jìn)一步表示為多跳路徑(l)的RPL不小于某一時(shí)間間隔T的概率，即路徑中各鏈路RLL均不小于T的概率（Pl（T））。通過對(duì)式(9)或式(10)積分可得

3 RLE-RPLP路由算法設(shè)計(jì)

與主動(dòng)式路由機(jī)制不同的是，反應(yīng)式路由無需周期性地啟動(dòng)新舊路由替換來進(jìn)行路由維護(hù)，節(jié)點(diǎn)間傳輸路徑是按需建立的，節(jié)約了網(wǎng)絡(luò)運(yùn)行成本。AODV（ad hoc on-demand distance vector）和 DSR（dynamic source routing）是2種經(jīng)典的反應(yīng)式路由協(xié)議。本文首先根據(jù)上述理論建模提出一種以準(zhǔn)確 RPL預(yù)測為標(biāo)準(zhǔn)的路由選取準(zhǔn)則，接著以DSR協(xié)議為基礎(chǔ)，給出RLE-RPLP算法實(shí)現(xiàn)及網(wǎng)絡(luò)性能優(yōu)化目標(biāo)。

3.1 基于可靠RPL估計(jì)的路由穩(wěn)定性準(zhǔn)則

在路由發(fā)現(xiàn)進(jìn)程中，目的節(jié)點(diǎn)Nd收到來自源節(jié)點(diǎn)Ns的路由請(qǐng)求RREQ報(bào)文之后沿原路徑發(fā)送路由應(yīng)答RREP報(bào)文。經(jīng)典AODV協(xié)議中Ns只選取RREP最先到達(dá)的路徑，DSR同樣以“最短路徑”準(zhǔn)則進(jìn)行路由選取，兩者均無法保證路徑穩(wěn)定性。為了證明 RLE-RPLP路由策略在提供更準(zhǔn)確路徑RPL估計(jì)方面較以往算法的優(yōu)越性，在引入和忽略相鄰鏈路RLL相關(guān)性條件下，進(jìn)行雙鏈路RLL聯(lián)合PDF仿真求解并給出誤差分析。

首先在不考慮鏈路相關(guān)性時(shí)，式(9)可改寫為

圖3 RLL1、RLL2聯(lián)合PDF數(shù)值仿真對(duì)比（R=100,d1=d2=50,Vd=10）

圖3給出分別由式(9)和式(12)得到的RLL1和RLL2聯(lián)合 PDF數(shù)值仿真對(duì)比結(jié)果。可見雖然兩者變化趨勢基本一致，但x-y平面各點(diǎn)所對(duì)應(yīng)的聯(lián)合PDF值存在顯著差異，原點(diǎn)附近尤為明顯（式(11)是式(9)所得結(jié)果的 4～5倍），而這一誤差也直接影響Pl(T)求解結(jié)果。當(dāng)改變(d1,d2)參數(shù)設(shè)置時(shí)，大量仿真對(duì)比結(jié)果證明：節(jié)點(diǎn)間初始距離越小，忽略RLL相關(guān)性導(dǎo)致的Pl(T)估計(jì)誤差越大。因此，當(dāng)鏈路長度較短，考慮RLL相關(guān)性會(huì)使RPL估計(jì)準(zhǔn)確度提升更為明顯。

3.2 RLE-RPLP算法實(shí)現(xiàn)

RLE-RPLP路由發(fā)現(xiàn)算法采用與DSR相似的源路由機(jī)制，源節(jié)點(diǎn)保存完整路由并提供多路徑支持，具體實(shí)現(xiàn)過程如下。

路由請(qǐng)求。當(dāng)有數(shù)據(jù)請(qǐng)求到達(dá)，Ns以廣播形式向鄰居節(jié)點(diǎn)發(fā)送RREQ報(bào)文，報(bào)文格式如圖4(a)所示。除了 Ns、Nd地址及路由表等基本信息，RLE-RPLP算法的RREQ中還需要包含路徑選取所需的節(jié)點(diǎn)移動(dòng)參數(shù)，該參數(shù)隨RREQ轉(zhuǎn)發(fā)實(shí)現(xiàn)獲取，詳細(xì)記錄了路由表中各節(jié)點(diǎn)所遵循的隨機(jī)移動(dòng)模型以及與其上游節(jié)點(diǎn)的相對(duì)運(yùn)動(dòng)信息，并按照不同的分組與各節(jié)點(diǎn)對(duì)應(yīng)。

路由決策。Nd接收到來自同一數(shù)據(jù)請(qǐng)求的首個(gè)RREQ時(shí)啟動(dòng)延時(shí)定時(shí)器，進(jìn)入路由選取階段。具體算法實(shí)現(xiàn)見算法 1。Nd首先在定時(shí)器規(guī)定時(shí)間內(nèi)根據(jù)RREQ攜帶的路徑信息選取多條鏈路不相交（link-disjoint）路徑，構(gòu)成備用路徑集合{l}，再利用各路徑的節(jié)點(diǎn)移動(dòng)參數(shù)，根據(jù)式(11)或其推廣形式計(jì)算{l}中路徑 RPL不小于預(yù)設(shè)時(shí)間間隔T的概率Pl(T)（T應(yīng)大于待傳數(shù)據(jù)的預(yù)期傳輸時(shí)間Te）。設(shè)Pth為RLE-RPLP算法預(yù)設(shè)的穩(wěn)定性閾值，最終滿足Pl(T)≥Pth且跳數(shù)最少的路徑將被選為最終路由。

路由應(yīng)答。路由決策完成后（與路由選取定時(shí)器數(shù)值歸零基本同步），Nd將所選路徑信息保存于RREP報(bào)文中并沿該路徑發(fā)送至Ns。RLE-RPLP算法的RREP報(bào)文格式如圖4(b)所示。

圖4 RLE-RPLP算法路由控制報(bào)文格式

算法1目的節(jié)點(diǎn)處路由選取

描述：目的節(jié)點(diǎn)Nd接收到其上游節(jié)點(diǎn)Np發(fā)送的RREQ報(bào)文，報(bào)文中攜帶路徑l的相關(guān)信息。

1)if （RREQ生存期值歸零）or（l與Nd已記錄的具有相同lt;Ns地址,廣播ID＞的某條路徑重合）

2)丟棄該RREQ報(bào)文

3)else 將Nd添加到RREQ路由表中

4)if （l為其lt; Ns地址,廣播 ID ＞對(duì)應(yīng)的第一條路徑）

5)添加l至備選路徑集合{ }

6)啟動(dòng)該lt; Ns地址,廣播ID ＞路徑選取定時(shí)器Timer

7)else if （l與Nd中已有的含相同lt; Ns地址，廣播ID ＞的路徑均嚴(yán)格不相交）and（Timer未歸零）

8)添加l至備選路徑集合{ }

9)else丟棄該RREQ報(bào)文

10)end all if

11)when (Timer==0)

12)find Pl(T)≥Pth且跳數(shù)最少的路徑

13)設(shè)置該路徑為 RLE-RPLP算法最終路由

3.3 網(wǎng)絡(luò)性能優(yōu)化目標(biāo)

本文以吞吐量（Th，單位時(shí)間內(nèi)網(wǎng)絡(luò)成功傳輸?shù)臄?shù)據(jù)量），路由重建次數(shù)Nr及路由開銷作為評(píng)價(jià)標(biāo)準(zhǔn)來驗(yàn)證 RLE-RPLP在提高網(wǎng)絡(luò)性能方面的優(yōu)勢。Nr表示一定時(shí)間內(nèi)所有用于數(shù)據(jù)傳輸?shù)穆窂接捎阪溌窋嗔研枰亟ǖ拇螖?shù)；路由開銷是指 Ns與Nd間完成一次數(shù)據(jù)傳輸需要交換的路由控制報(bào)文主要為RREQ和RREP數(shù)量。Th實(shí)際上由網(wǎng)絡(luò)中各層協(xié)議共同決定。本文為了強(qiáng)調(diào)路徑穩(wěn)定性對(duì)Th的影響，作如下定義及說明。

定義1Pls( T)表示路徑ls在間隔T內(nèi)傳輸數(shù)據(jù)被目的節(jié)點(diǎn)正確接收的概率。若ls由Q條鏈路構(gòu)成，t1,t2,…,tq分別表示各鏈路RLL，則根據(jù)式(11)有

式(13)實(shí)質(zhì)上從網(wǎng)絡(luò)層角度量化了路徑在所需時(shí)間間隔內(nèi)成功完成數(shù)據(jù)傳輸?shù)哪芰ΑＮ墨I(xiàn)[21]通過定義鏈路成功傳輸概率 pi,j來描述物理層干擾對(duì)鏈路的影響，因此本文定義1作為pi,j定義的延伸，旨在描述網(wǎng)絡(luò)層路由機(jī)制中路徑穩(wěn)定性對(duì)端到端數(shù)據(jù)傳輸?shù)恼w影響，具有合理性。

定義 2若只考慮路徑跳數(shù)較少的情況，可以假設(shè)備選路徑傳輸Fs（packets）所需時(shí)間T0(s)大致相等，若Fs為Ns到Nd單次傳輸請(qǐng)求所含數(shù)據(jù)量，N為T0內(nèi)網(wǎng)絡(luò)數(shù)據(jù)傳輸路徑總數(shù)，則吞吐量定義為

式(14)未考慮物理層和 MAC層影響，即忽略物理層信號(hào)衰落并假設(shè) Nd對(duì)接收數(shù)據(jù)都能正確解碼且無重復(fù)或亂序。由于本文研究MANET網(wǎng)絡(luò)層路由協(xié)議優(yōu)化，因此上述簡化不影響算法評(píng)估有效性及其可擴(kuò)展性。

接下來，利用圖 5(a)中簡化網(wǎng)絡(luò)模型將 RLERPLP路由選取方法與“最短路徑”準(zhǔn)則進(jìn)行對(duì)比，給出算法優(yōu)化例證。設(shè)Fs從Ns到Nd的傳輸需在T0內(nèi)完成，A、B、C分別表示3個(gè)中間節(jié)點(diǎn)，Nd在路由選取結(jié)束后共得到l1(Ns→A→Nd)和l2(Ns→ B→C→Nd)2條備選路徑信息。圖5(b)給出本文算法和忽略RLL相關(guān)性時(shí)兩者Pl(T0)值，即P1，P2分別代表數(shù)據(jù)成功接收概率的實(shí)際（準(zhǔn)確）估值和過高（錯(cuò)誤）估值。

設(shè)路徑穩(wěn)定性閾值Pth=0.7，F(xiàn)s和T0歸一化為1。本文算法參考P1，只有l(wèi)2達(dá)到標(biāo)準(zhǔn)，由式(14)得到網(wǎng)絡(luò)吞吐量為0.8；若不考慮鏈路RLL相關(guān)性（P2為參考），l1和l2均達(dá)到穩(wěn)定性標(biāo)準(zhǔn)，最終跳數(shù)較少的l1被選為最終路由。但Th計(jì)算需要用數(shù)據(jù)成功接收概率的實(shí)際值P1，因此Th僅為0.6。由此可見RLE-RPLP算法能夠避免RPL估計(jì)誤差造成的路徑穩(wěn)定性誤判，優(yōu)化了網(wǎng)絡(luò)性能。

圖5 RLE-RPLP優(yōu)化性例證簡化網(wǎng)絡(luò)模型及路徑穩(wěn)定性設(shè)置

4 網(wǎng)絡(luò)性能仿真分析

為了驗(yàn)證RLE-RPLP算法合理性及有效性，進(jìn)行MATLAB仿真環(huán)境下的MANET網(wǎng)絡(luò)構(gòu)建，路由機(jī)制實(shí)現(xiàn)及性能對(duì)比分析。MATLAB廣泛應(yīng)用于路由算法仿真中，并且能夠?qū)螌訁f(xié)議設(shè)計(jì)提供可信度較高的性能分析及合理性驗(yàn)證[22～24]。本文利用兩組參數(shù)設(shè)置將 RLE-RPLP算法分別與忽略鏈路RLL相關(guān)性條件下的源路由協(xié)議及文獻(xiàn)[19]中提出的穩(wěn)定性路由協(xié)議進(jìn)行對(duì)比并給出仿真結(jié)果及性能分析。

4.1 引入RLL相關(guān)性的路由機(jī)制優(yōu)化作用

對(duì)比算法與本文算法路由發(fā)現(xiàn)進(jìn)程類似，但區(qū)別在于：路徑穩(wěn)定性評(píng)估不考慮RLL相關(guān)性，Pl(T)利用式(12)及其推廣形式計(jì)算。采用Th和 Nr作為性能指標(biāo)對(duì)兩者進(jìn)行對(duì)比分析。

4.1.1 網(wǎng)絡(luò)參數(shù)設(shè)置

設(shè)移動(dòng)節(jié)點(diǎn)隨機(jī)分布于100 m×100 m的方形區(qū)域，各節(jié)點(diǎn)帶寬足夠大（無鏈路擁塞延遲），每個(gè)仿真周期T0=5時(shí)隙起始時(shí)刻加載N個(gè)(N=10)Ns不同且大小為Fs(25單元)的數(shù)據(jù)流服務(wù)請(qǐng)求，數(shù)據(jù)預(yù)期傳輸時(shí)長為T0，R=20 m，Pth=0.8，路徑選取定時(shí)器=0.05 T0，Pl(T)計(jì)算中取 T=1.5 T0。仿真共運(yùn)行100 T0。速率和吞吐量單位分別設(shè)為米/時(shí)隙、單位/時(shí)隙。

定義路由重建（失效）條件：1)RLE-RPLP算法，路由發(fā)現(xiàn)進(jìn)程中備選路徑Pl(T)值均未達(dá)到Pth；2)對(duì)比算法，所選路徑實(shí)際Pl(T)值未達(dá)到Pth（因該算法會(huì)導(dǎo)致 Pl(T)估計(jì)過高，因此當(dāng)參數(shù)設(shè)置合理，每個(gè)數(shù)據(jù)請(qǐng)求備選路徑中至少有一條路徑滿足Pl(T)≥Pth）。若發(fā)生路由重建，則 Th 計(jì)算時(shí)（式(14)）對(duì)應(yīng)路徑Pl(T)值為0，即認(rèn)為數(shù)據(jù)不允許重傳，一旦路徑失效，則數(shù)據(jù)丟失。

4.1.2 結(jié)果與分析

圖6和圖7分別給出當(dāng)Vd=10，Th和Nr隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)（Np）變化的仿真對(duì)比結(jié)果。由圖6可見，Th隨Np增加（節(jié)點(diǎn)密度增大）呈上升趨勢。當(dāng)Vmin=2，RLE-RPLP算法所得Th比不考慮RLL相關(guān)性的結(jié)果平均提升約16%。其根本原因在于：忽略鏈路相關(guān)性使路徑Pl(T)估計(jì)值偏高，達(dá)到Pth要求的備選路徑數(shù)量增多，路由選取時(shí)可靠性最佳的路徑很容易被“跳數(shù)最少”路徑所替代，導(dǎo)致數(shù)據(jù)丟失頻率增加，降低網(wǎng)絡(luò)吞吐量。其次，當(dāng) Np=20和70，2種算法所得Th差值分別為3和8，說明RLE-RPLP對(duì)吞吐量優(yōu)化效果隨 Np增大而增加。這一結(jié)果的理論依據(jù)在于：Np越大，鏈路平均長度越短，2種算法Pl(T)計(jì)算值相差越大，以RPL估計(jì)準(zhǔn)確度占優(yōu)的RLE-RPLP算法能獲得更理想的Th。另外，當(dāng)節(jié)點(diǎn)移動(dòng)度增大（Vmin由2增加到5，Vd不變），Th均有所下降，但Vmin=5時(shí)，RLE-RPLP算法所得 Th依然優(yōu)于對(duì)比算法在Vmin=2時(shí)的結(jié)果，說明本文算法能夠有效緩解因節(jié)點(diǎn)移動(dòng)性增加而造成的網(wǎng)絡(luò)性能惡化。

圖6 Np變化時(shí)Th仿真結(jié)果對(duì)比（Vd=10）

圖7 Np變化時(shí)Nr仿真結(jié)果對(duì)比（Vd=10）

圖7同樣表明增加節(jié)點(diǎn)密度能夠提高網(wǎng)絡(luò)連通性，實(shí)現(xiàn)性能提升（Nr減少）。仿真結(jié)果顯示，RLE-RPLP算法能有效降低路由重建次數(shù)，且節(jié)點(diǎn)移動(dòng)度較高時(shí)效果更為明顯。以Np=70處仿真結(jié)果為例：Vmin=2時(shí)，RLE-RPLP的Nr值較其對(duì)比算法減少約53%；而Vmin=5時(shí)，這一比率上升至71%。另外，對(duì)比Np=70處Vmin分別為2和5的結(jié)果，可見忽略 RLL相關(guān)性時(shí) Nr差值為 21；而運(yùn)用RLE-RPLP算法Nr差值僅為3，進(jìn)一步驗(yàn)證了其在高節(jié)點(diǎn)移動(dòng)度下保證網(wǎng)絡(luò)性能的能力。

圖8和圖9分別給出當(dāng)Vmin=2，Th和Nr隨節(jié)點(diǎn)移動(dòng)度(Vd)變化的仿真對(duì)比結(jié)果。顯然Vd增大加劇了網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，使鏈路斷裂的概率增大，網(wǎng)絡(luò)性能有所降低。而RLE-RPLP在這種情況下依然表現(xiàn)出明顯的優(yōu)越性：當(dāng) Np=60，圖 9中RLE-RPLP算法Th較對(duì)比算法提升約20%；圖10中前者Nr較后者減少約57%。當(dāng)Np=40，網(wǎng)絡(luò)性能整體偏低，與圖6和圖7所得結(jié)論一致。

圖8 Vd變化時(shí)Th仿真結(jié)果對(duì)比（Vmin=2）

圖9 Vd變化時(shí)Nr仿真結(jié)果對(duì)比（Vmin=2）

4.2 與已有穩(wěn)定性路由協(xié)議性能對(duì)比

進(jìn)一步將RLE-RPLP算法與文獻(xiàn)[19]提出的基于鏈路有效性估計(jì)的路由（LEBR,link availability estimation based routing）算法進(jìn)行比較，以吞吐量和路由開銷作為性能指標(biāo)實(shí)現(xiàn)有效性驗(yàn)證。LEBR算法以鏈路生存期作為其有效性量化標(biāo)準(zhǔn)，主要特點(diǎn)為：1)以AODV協(xié)議為改進(jìn)基礎(chǔ)，同一路徑中的各節(jié)點(diǎn)只保存了其相鄰節(jié)點(diǎn)路由信息，各鏈路有效性(Lij)需隨RREP轉(zhuǎn)發(fā)逐跳計(jì)算；2)路徑有效性(PLA)為各鏈路 Lij的乘積，即 PLA=∏ Lij。由此可見，LEBR強(qiáng)調(diào)鏈路級(jí)別的穩(wěn)定性分析，且默認(rèn)各鏈路統(tǒng)計(jì)特性相互獨(dú)立。

4.2.1 網(wǎng)絡(luò)參數(shù)設(shè)置

各參數(shù)設(shè)置如表1所示。與文獻(xiàn)[19]不同，仿真中采用簡化的節(jié)點(diǎn)隨機(jī)移動(dòng)模型，節(jié)點(diǎn)速率服從最大值與最小值間的均勻分布特性。LEBR算法采用改進(jìn)的AODV協(xié)議實(shí)現(xiàn)，即在對(duì)應(yīng)RREP報(bào)文及路由表中加入PLA分區(qū)用于有效性指示及路由選取。

表1 仿真參數(shù)設(shè)置

4.2.2 結(jié)果與分析

圖10和圖11分別為當(dāng)網(wǎng)絡(luò)加載的數(shù)據(jù)請(qǐng)求數(shù)量Nq為10，2種算法在節(jié)點(diǎn)移動(dòng)度（Vmax）變化情況下所得Th及路由開銷對(duì)比結(jié)果。如圖10所示，當(dāng)移動(dòng)度相對(duì)較低（Vmax不大于 6），兩者所得 Th基本一致（大于 7×104bit/s），而當(dāng) Vmax=10，RLE-RPLP算法Th（約4×104bit/s）約為LEBR算法Th（約2.4×104bit/s）的1.6倍，說明本文算法在Vmax較大時(shí)能夠保證較低的 Th下降速率，顯示出了在對(duì)抗網(wǎng)絡(luò)高度動(dòng)態(tài)性方面的優(yōu)勢。圖 11進(jìn)一步驗(yàn)證了 RLE-RPLP算法的這一優(yōu)勢：當(dāng)6≤Vmax≤10，RLE-RPLP算法路由開銷比LEBR算法降低了約26%。其原因?yàn)椋涸诠?jié)點(diǎn)高速運(yùn)動(dòng)使路徑穩(wěn)定性明顯下降的情況下，本文算法能夠以路徑整體生存期估計(jì)作為參考依據(jù)進(jìn)行更可靠地路由決策，有效地減少了因路由重建而產(chǎn)生的RREQ泛洪概率，從而降低了路由開銷。

圖10 Vmax變化時(shí)Th仿真結(jié)果對(duì)比(Nq=10)

圖11 Vmax變化時(shí)路由開銷仿真結(jié)果對(duì)比(Nq=10)

圖12和圖13分別為Vmax=8情況下，網(wǎng)絡(luò)中數(shù)據(jù)傳輸請(qǐng)求數(shù)量變化時(shí)2種算法所得Th及路由開銷對(duì)比結(jié)果。由圖12可知，兩者Th差值隨數(shù)據(jù)請(qǐng)求增加而增大：當(dāng)Nq=1，兩者Th幾乎相等；當(dāng)Nq=20，本文算法Th（約6.5×104bit/s）比LEBR算法Th（約4.3×104bit/s）提升約51%。實(shí)際上，當(dāng)Nq增加，網(wǎng)絡(luò)中物理層及鏈路層的數(shù)據(jù)通信質(zhì)量會(huì)受到影響，路由選擇機(jī)會(huì)相應(yīng)減少，相比LEBR算法中逐跳的鏈路有效性判斷，RLE-RPLP算法中基于路徑RPL的路由決策準(zhǔn)則能夠更有效、真實(shí)地評(píng)估所選路徑的穩(wěn)定性進(jìn)而保證其持續(xù)連通性。從圖 13結(jié)果來看，RLE-RPLP算法在所有Nq對(duì)應(yīng)值情況下都能更有效地控制路由開銷：較LEBR算法平均減少約17%，當(dāng) Nq較大時(shí)尤為明顯（當(dāng) Nq=20，這一比率約為21.6%）。這一結(jié)果同樣驗(yàn)證了本文算法在可靠路徑穩(wěn)定性判斷中的優(yōu)化效果以及對(duì)網(wǎng)絡(luò)性能的提升作用。

圖12 Nq變化時(shí)Th仿真結(jié)果對(duì)比（Vmax=8）

圖13 Nq變化時(shí)路由開銷仿真結(jié)果對(duì)比（Vmax=8）

5 結(jié)束語

本文將MANET多跳路徑中相鄰鏈路RLL相關(guān)性引入路徑RPL統(tǒng)計(jì)特性分析，重點(diǎn)研究更具一般性及實(shí)際意義的路徑穩(wěn)定性估計(jì)準(zhǔn)則，提出了一種基于可靠路徑 RPL估計(jì)的路由發(fā)現(xiàn)算法（RLE-RPLP）。該算法首先通過相鄰鏈路 RLL相關(guān)性統(tǒng)計(jì)建模，給出了在節(jié)點(diǎn)移動(dòng)模型不受限情況下多跳路徑中各鏈路RLL聯(lián)合PDF表達(dá)式及理論推導(dǎo)過程，進(jìn)而優(yōu)化了路徑RPL的統(tǒng)計(jì)特性描述，建立了更準(zhǔn)確的路由穩(wěn)定性判斷準(zhǔn)則，在此基礎(chǔ)上提出了優(yōu)化的RLE-RPLP路由發(fā)現(xiàn)算法。仿真分析表明：在路徑跳數(shù)較少、鏈路長度較小的一般性MANET環(huán)境中，該算法與不考慮RLL相關(guān)性的穩(wěn)定性路由算法相比，在提高網(wǎng)絡(luò)吞吐量、減少路由重建次數(shù)方面具有顯著優(yōu)越性；與基于鏈路有效性估計(jì)的LEBR算法相比，能夠在節(jié)點(diǎn)移動(dòng)度較高或網(wǎng)絡(luò)負(fù)載較大時(shí)更有效地保證網(wǎng)絡(luò)吞吐量及控制路由開銷，對(duì)網(wǎng)絡(luò)性能具有更明顯的優(yōu)化作用。

[1]LA R J,HAN Y. Distribution of path durations in mobile ad hoc networks and path selection[J]. IEEE/ACM Transactions on Networking,2007,15(5):993-1006.

[2]王博,陳訓(xùn)遜. ad hoc網(wǎng)絡(luò)中一種基于信任模型的機(jī)會(huì)路由算法[J]通信學(xué)報(bào),2013,34(9): 92-104.WANG B,CHEN X X. Opportunistic routing algorithm based on trust model for ad hoc network[J]. Journal on Communications,2013,34(9):92-104.

[3]VU T K,KWON S. Mobility assisted on demand routing algorithm for MANETs in the presence of location errors[J]. The Scientific World Journal,2014,Article ID 790103.

[4]NAMUDURI K,PENDSE R. Analytical estimation of path duration in mobile ad hoc networks[J]. IEEE Sensors Journal,2012,12(6): 1828-1835.

[5]NAMUDURI K,WAN Y,GOMATHISANKARAN M,et al. Airborne network: a cyber-physical system perspective[C]//The first ACM MobiHoc workshop on Airborne Networks and Communications. c2012:55-59.

[6]YANG W,YANG X,YANG S,et al. A greedy-based stable multi-path routing protocol in mobile ad hoc networks[J]. Ad Hoc Networks,2011,9(4): 662-674.

[7]SARGOLZAEY H,ALI B M,KHATUN S. A cross layer metric for discovering reliable routes in mobile ad hoc networks[J]. Wireless Personal Communications,2012,66(1): 207-216.

[8]居熙,陶軍,陸一飛,等. 一種基于遷移可測度的移動(dòng)自組織網(wǎng)絡(luò)路由模型[J]. 電子學(xué)報(bào),2010,38(6): 1-5.JU X,TAO J,LU Y F,et al. A predictable-delivery-ratio based routing model in mobile ad hoc networks[J]. Acta Electronical Sinica,2010,38(6): 1-5.

[9]HUA E Y,HAAS Z J. An algorithm for prediction of link lifetime in MANET based on unscented kalman filter[J]. IEEE Communications Letters,2009,13(10):782-784.

[10]HAAS Z J,HUA E Y. Residual link lifetime prediction with limited information input in mobile ad hoc networks[C]// The 27th IEEE International Conference on Computer Communications. c2008: 13-18.

[12]CARMO R D,WEMER M,HOLLICK M. Signs of a bad neighborhood: a lightweight metric for anomaly detection in mobile ad hoc networks[C]//8th ACM Symposium on QoS and Security for Wireless and Mobile Networks. c2012: 47-54.

[13]WANG C F,CHIOU Y P,LIAW G H. Next hop selection mechanism for nodes with heterogeneous transmission range in Vanets[J]. Computer Communications,2015,55: 22-31.

[14]VIRIYASITAVAT W,BAI F,TONGUZ O K. Dynamics of network connectivity in urban vehicular networks[J]. IEEE Journal on Selected Areas in Communications,2011,29(3): 515-533.

[15]SADAGOPAN N,BAI F,KRISHNAMACHARI B,et al. PATHS:analysis of path duration statistics and their impact on reactive MANET routing protocols[C]//The 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. c2003: 1-3.

[16]HAN Y,LA R J,MAKOWSKI A M,et al. Distribution of path durations in mobile ad hoc networks-Palm’s theorem to the rescue[J].Computer Networks,2006,50(12): 1887-1900.

[17]KARAGIANNIS G,ALTINTAS O,EKICI E,et al. Vehicular networking: a survey and tutorial on requirements,architectures,challenges,standards and solutions[J]. IEEE Communications Surveys and Tutorials,2011,13(4): 584-616.

[18]LU N,CHENG N,ZHANG N,et al. Connected vehicles: solutions and challenges[J]. IEEE Internet Things Journal,2014,1(4): 289-299.

[19]LEI L,WANG D,ZHOU L,et al. Link availability estimation based reliable routing for aeronautical ad hoc networks[J]. Ad Hoc Networks,2014,20: 53-63.

[20]ANTUNES N,JACINTO G,PACHECO A. An analytical framework to infer multihop path reliability in MANETs[C]//The ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. c2010: 323-332.

[21]LEE G Y,HAAS Z J. Simple,practical,and effective opportunistic routing for short-haul multi-hop wireless networks[J]. IEEE Transactions on Wireless Communications,2011,10(11): 3583-3588.

[22]DANA A,ZADEH A K,SADAT NOORI S A. Backup path set selection in ad hoc wireless network using link expiration time[J]. Computers and Electrical Engineering,2008,34(6): 503-519.

[23]WU Y S,LEE D H,JUNG J I. Derivation and analysis of link/route maintenance probability in multi hop mobile ad hoc networks[C]// International Conference on Information Technology: New Generations.c2009: 623-627.

[24]SHELLY S,VIJAY V,BABU A V. Model for path duration in vehicular ad hoc networks under greedy forwarding strategy[C]// International Conference on Computer,Communication and Convergence(ICCC 2014). c2014: 394-400.

Routing discovery algorithm based on reliable path stability estimation in MANET

LI Zhi-nan1,YANG Xiao-dong1,2

(1. College of Information and Communication Engineering,Harbin Engineering University,Harbin 150001,China;2. Collaborative Research Center,Meisei University,Tokyo 191-8506,Japan)

A novel routing discovery algorithm for MANETs was proposed based on reliable residual path lifetime (RPL)prediction (RLE-RPLP). Correlation between residual link lifetime (RLL)of neighboring links was explicitly investigated and fully taken into account in stability estimation of multi-hop paths in the algorithm. Optimized RPL statistical properties were further explored to offer a more reliable path stability metric. Simulation analysis demonstrates that the proposed RLE-RPLP routing discovery algorithm shows prominent superiority in improving network throughput and reducing route reconstruction frequency. Moreover,compared with the existing link stability-aware routing protocol,the RLE-RPLP achieves better performance improvement in terms of throughput and routing overhead.

MANET,residual link lifetime,mobility correlation,residual path lifetime,stability estimation

signal strength based link lifetime estimating mechanism in MANET[C]//IEEE Conference An-thology. c2013: 14.

TN929.5

A

2015-12-21；

2016-06-21

10.11959/j.issn.1000-436x.2016162

李智楠（1987-），女，遼寧丹東人，哈爾濱工程大學(xué)博士生，主要研究方向?yàn)闊o線通信系統(tǒng)理論、MANET路由優(yōu)化算法等。

楊曉冬（1963-），男，黑龍江哈爾濱人，博士，哈爾濱工程大學(xué)教授，主要研究方向?yàn)楝F(xiàn)代通信系統(tǒng)技術(shù)與理論、現(xiàn)代天線技術(shù)等。