移動(dòng)Ad hoc網(wǎng)絡(luò)基于鏈路可用時(shí)間的動(dòng)態(tài)源路由協(xié)議

摘要：為了提高鏈路的穩(wěn)定性，增加路徑可用時(shí)間，提出一種應(yīng)用于移動(dòng)Ad hoc網(wǎng)絡(luò)的基于鏈路可用時(shí)間的動(dòng)態(tài)源路由協(xié)議(LARP)。該協(xié)議以路徑可用時(shí)間作為路徑評(píng)價(jià)的參數(shù)，優(yōu)先選擇具有最大路徑可用時(shí)間的路徑進(jìn)行數(shù)據(jù)包傳遞。路徑可用時(shí)間反映了當(dāng)前節(jié)點(diǎn)移動(dòng)對(duì)路徑穩(wěn)定性的影響，其數(shù)值取決于路徑中的最小鏈路可用時(shí)間。仿真結(jié)果表明該協(xié)議相對(duì)于動(dòng)態(tài)源路由協(xié)議(DSR)，提高了路徑穩(wěn)定性，減少了路由發(fā)現(xiàn)次數(shù)，有效提高了吞吐量等網(wǎng)絡(luò)性能。
關(guān)鍵詞：移動(dòng)Ad hoc網(wǎng)絡(luò)；鏈路穩(wěn)定性；路徑可用時(shí)間；鏈路可用時(shí)間
 
0 引言
    移動(dòng)Ad hoc網(wǎng)絡(luò)(MANET)是一種不依賴于任何固定設(shè)施的無線網(wǎng)絡(luò)。網(wǎng)絡(luò)中的節(jié)點(diǎn)可以自由移動(dòng)，具有數(shù)據(jù)轉(zhuǎn)發(fā)的功能，從而形成了網(wǎng)絡(luò)的多跳特性。因此，路由成為移動(dòng)Ad hoc網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)通信的核心問題。
    目前國(guó)內(nèi)外有很多關(guān)于路由協(xié)議的研究。主要可以分為先驗(yàn)式路由協(xié)議和反應(yīng)式路由協(xié)議。先驗(yàn)式路由協(xié)議定期更新路由信息，對(duì)拓?fù)浣Y(jié)構(gòu)的變化反應(yīng)靈敏，但是該類協(xié)議需要維護(hù)路由表并定期更新路由表信息，費(fèi)了大量的網(wǎng)絡(luò)帶寬。反應(yīng)式路由協(xié)議僅在需要路由時(shí)才進(jìn)行路由發(fā)現(xiàn)，有效節(jié)省了網(wǎng)絡(luò)資源。但是節(jié)點(diǎn)的移動(dòng)可能會(huì)導(dǎo)致已有的鏈路發(fā)生斷裂，使已有的路徑失效，從而發(fā)啟新的路由發(fā)現(xiàn)過程。這不僅會(huì)降低數(shù)據(jù)包的成功發(fā)送率，還會(huì)帶來新的路由發(fā)現(xiàn)開銷。
    因此，為了減少移動(dòng)性帶來的鏈路斷裂，提高鏈路的穩(wěn)定性，本文提出了一種基于鏈路可用時(shí)間的路由協(xié)議。該協(xié)議可以有效增加路徑可用時(shí)間，并提高網(wǎng)絡(luò)吞吐量等性能。

1 基于鏈路可用時(shí)間的動(dòng)態(tài)源路由協(xié)議
    本文提出的路由協(xié)議LARP選擇具有最大路徑可用時(shí)間的路徑進(jìn)行路由。路徑可用時(shí)間由路徑中的最小鏈路可用時(shí)間決定，而鏈路可用時(shí)間可以通過節(jié)點(diǎn)之間的相互運(yùn)動(dòng)模型進(jìn)行計(jì)算。另外，為了減少節(jié)點(diǎn)隨機(jī)移動(dòng)帶來的影響，通過歷史鏈路可用時(shí)間信息，預(yù)測(cè)下一時(shí)刻的鏈路可用時(shí)間。
1．1 路由選擇參數(shù)
1．1．1 鏈路可用時(shí)間
    圖1呈現(xiàn)了發(fā)送節(jié)點(diǎn)s和接收節(jié)點(diǎn)r之間的相對(duì)移動(dòng)過程。假設(shè)點(diǎn)S代表節(jié)點(diǎn)s在時(shí)刻t1時(shí)所處的位置，在時(shí)間t1、t2、t3，節(jié)點(diǎn)r相對(duì)于節(jié)點(diǎn)s的位置分別為R1、R2和R3，這三個(gè)時(shí)刻s和r之間的距離分別為D1、D2和R，而這些距離可以通過無線傳播模型計(jì)算得到。節(jié)點(diǎn)s和節(jié)點(diǎn)r相
對(duì)地面的移動(dòng)速度分別為vs和vr，則以s為參照系，如圖1所示，節(jié)點(diǎn)r相對(duì)于節(jié)點(diǎn)s的相對(duì)移動(dòng)速度為v，v=vr-vs。

    已知節(jié)點(diǎn)r在時(shí)刻t1和時(shí)刻t2的位置，而節(jié)點(diǎn)r移動(dòng)出發(fā)送者范圍的時(shí)刻t3未知。為了求得鏈路可用時(shí)間，需要對(duì)時(shí)刻t3進(jìn)行預(yù)測(cè)。根據(jù)余弦定理知道以下公式：
   
    式(1)中存在三個(gè)未知變量θ、v、t3，但只有兩個(gè)有效的等式，因而求解還需要另一個(gè)包含這三個(gè)未知變量的額外的公式。根據(jù)面積相等SSR1R3=SSR1R2+SSR2R3和海倫公式

    式(1)和式(2)中存在三個(gè)未知變量θ、v、t3，且存在三個(gè)有效的等式，因而可以求得這三個(gè)未知變量。從而，計(jì)算得到鏈路的可用時(shí)間TL(s，r)=t3-t2。
1．1．2 鏈路可用時(shí)間預(yù)測(cè)
    節(jié)點(diǎn)移動(dòng)具有隨機(jī)性，處于一個(gè)動(dòng)態(tài)變化的過程，可能造成實(shí)際鏈路可用時(shí)間值的急劇波動(dòng)。因此，獲得準(zhǔn)確的實(shí)時(shí)值是非常困難的。本文利用鏈路可用時(shí)間的歷史信息值，預(yù)測(cè)當(dāng)前的鏈路可用時(shí)間。
    假設(shè)T時(shí)刻的鏈路可用時(shí)間為，T-1時(shí)刻的鏈路可用時(shí)間為，則T+1時(shí)刻的鏈路可用時(shí)間為
   
    其中，0≤a≤1，表示之前時(shí)間段對(duì)當(dāng)前鏈路可用時(shí)間的影響因子，不失一般性，選取a為0．7。
1．1．3 路徑可用時(shí)間
    假設(shè)存在路徑P：S，…，i，j，…，D，源節(jié)點(diǎn)S進(jìn)行路由發(fā)現(xiàn)過程，發(fā)送路由請(qǐng)求包到目的節(jié)點(diǎn)D。路由請(qǐng)求包經(jīng)過鏈路(i，j)，在時(shí)刻tj預(yù)測(cè)出鏈路可用時(shí)間為。當(dāng)tD時(shí)刻路由請(qǐng)求包到達(dá)目的節(jié)點(diǎn)D時(shí)，鏈路(i,j)的可用時(shí)間并非tj時(shí)刻預(yù)測(cè)的值，變?yōu)?。因而，可以求得路徑上每個(gè)鏈路的鏈路可用時(shí)間。
    路徑可用時(shí)間為各個(gè)鏈路可用時(shí)間的最小值，因?yàn)楫?dāng)路徑中存在一條鏈路不可用時(shí)，則整個(gè)路徑不可用。路徑可用時(shí)間為
   
    其中，任意鏈路(i，j)∈P。
1．2 LARP路由協(xié)議
    LARP路由協(xié)議建立在DSR協(xié)議的基礎(chǔ)上，分為路由發(fā)現(xiàn)和路由維護(hù)兩個(gè)部分。其中，路由維護(hù)部分與DSR相同，主要區(qū)別存在于路由發(fā)現(xiàn)的選擇過程中。
    LARP協(xié)議的路由請(qǐng)求包在DSR的基礎(chǔ)上添加了預(yù)測(cè)的鏈路可用時(shí)間字段LAT(Link Available Time)和當(dāng)前時(shí)鐘字段CT(Current Time)，用于記錄路由路徑中各個(gè)預(yù)測(cè)的鏈路可用時(shí)間和路由請(qǐng)求包經(jīng)過各個(gè)鏈路的時(shí)間。在各個(gè)節(jié)點(diǎn)的路由表中也增加了路徑可用時(shí)間字段PAT(Path Available Time)，用于存放各個(gè)路徑的可用時(shí)間信息。
    (1)在路由發(fā)現(xiàn)階段，路由請(qǐng)求包在增加的LAT和CT兩個(gè)字段中記錄沿途各個(gè)鏈路的可用時(shí)間和路由請(qǐng)求包經(jīng)過相應(yīng)鏈路的時(shí)間。
    (2)當(dāng)路由請(qǐng)求包到達(dá)目的節(jié)點(diǎn)后，提取其中的預(yù)測(cè)鏈路可用時(shí)間參數(shù)(LAT)和時(shí)鐘參數(shù)(CT)，利用式(4)計(jì)算出該路徑的可用時(shí)間。
    (3)目的節(jié)點(diǎn)收到的多個(gè)路由請(qǐng)求包代表從源節(jié)點(diǎn)到該目的節(jié)點(diǎn)的多個(gè)可能路徑，求出每條路徑的可用時(shí)間信息后，目的節(jié)點(diǎn)為每個(gè)路由請(qǐng)求包回復(fù)一個(gè)路由應(yīng)答包，將鏈路信息和路徑可用時(shí)間信息回復(fù)給源節(jié)點(diǎn)，并在路由表中相應(yīng)地記錄鏈路信息和路徑可用時(shí)間。
    (4)當(dāng)源節(jié)點(diǎn)需要再次發(fā)送數(shù)據(jù)包時(shí)，首先查找路由表，若路由表中已存在到達(dá)目的節(jié)點(diǎn)的路徑，則在這些路徑中選擇具有最大路徑可用時(shí)間的路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)；若路由表中不存在可用路徑，則進(jìn)行路由發(fā)啟過程。
    (5)路由維護(hù)過程和DSR相同。

2 實(shí)驗(yàn)結(jié)果與分析
    仿真實(shí)驗(yàn)使用NS-2．34，在DSR的基礎(chǔ)上實(shí)現(xiàn)了所提出的LARP路由協(xié)議。實(shí)驗(yàn)參數(shù)如下：網(wǎng)絡(luò)中有50個(gè)節(jié)點(diǎn)，拓?fù)鋮^(qū)域?yàn)?000×1000m，網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布。移動(dòng)模型采用隨機(jī)位點(diǎn)模型(RWP)，節(jié)點(diǎn)最大速度為15m／s。MAC層采用IEEE 802．11協(xié)議。節(jié)點(diǎn)通信范圍均為250m。在實(shí)驗(yàn)中隨機(jī)選取了12條固定比特率(CBR)的數(shù)據(jù)流，每個(gè)源節(jié)點(diǎn)每秒發(fā)送120個(gè)512字節(jié)的CBR分組。仿真時(shí)間為1000s。結(jié)果如下：

    圖2顯示了網(wǎng)絡(luò)吞吐量，隨著節(jié)點(diǎn)移動(dòng)速度的增加，這兩種路由協(xié)議的吞吐量都呈減小趨勢(shì)，但LARP協(xié)議的網(wǎng)絡(luò)吞吐量明顯高于DSR。這是因?yàn)長(zhǎng)ARP協(xié)議選擇具有最大路徑可用時(shí)間的路徑進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)，有效提高了鏈路的穩(wěn)定性，減少了移動(dòng)性帶來的影響。

    圖3顯示了節(jié)點(diǎn)移動(dòng)速度對(duì)數(shù)據(jù)包投遞率的影響。LARP協(xié)議的路徑由于具有更高的穩(wěn)定性，因而減少了鏈路斷裂帶來的丟包，有效地提高了數(shù)據(jù)包投遞率。圖中可以看到，LARP協(xié)議的數(shù)據(jù)包投遞率高于DSR。

3 結(jié)束語
    本文提出了一種基于鏈路可用時(shí)間的動(dòng)態(tài)源路由協(xié)議。該協(xié)議以路徑可用時(shí)間作為路徑評(píng)價(jià)的參數(shù)，選擇具有最大路徑可用時(shí)間的路徑，避免了頻繁的鏈路斷裂，提高了鏈路穩(wěn)定性，從而減少了路由發(fā)現(xiàn)次數(shù)。仿真結(jié)果顯示，本文提出的LARP協(xié)議同DSR協(xié)議相比，顯著地
提高了路徑穩(wěn)定性，減少了路由發(fā)現(xiàn)次數(shù)，有效提高了吞吐量等網(wǎng)絡(luò)性能。