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

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

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

    式(1)和式(2)中存在三個未知變量θ、v、t3，且存在三個有效的等式，因而可以求得這三個未知變量。從而，計(jì)算得到鏈路的可用時(shí)間TL(s，r)=t3-t2。
1．1．2 鏈路可用時(shí)間預(yù)測
    節(jié)點(diǎn)移動具有隨機(jī)性，處于一個動態(tài)變化的過程，可能造成實(shí)際鏈路可用時(shí)間值的急劇波動。因此，獲得準(zhǔn)確的實(shí)時(shí)值是非常困難的。本文利用鏈路可用時(shí)間的歷史信息值，預(yù)測當(dāng)前的鏈路可用時(shí)間。
    假設(shè)T時(shí)刻的鏈路可用時(shí)間為，T-1時(shí)刻的鏈路可用時(shí)間為，則T+1時(shí)刻的鏈路可用時(shí)間為
   
    其中，0≤a≤1，表示之前時(shí)間段對當(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ā)送路由請求包到目的節(jié)點(diǎn)D。路由請求包經(jīng)過鏈路(i，j)，在時(shí)刻tj預(yù)測出鏈路可用時(shí)間為。當(dāng)tD時(shí)刻路由請求包到達(dá)目的節(jié)點(diǎn)D時(shí)，鏈路(i,j)的可用時(shí)間并非tj時(shí)刻預(yù)測的值，變?yōu)椤Ｒ蚨?，可以求得路徑上每個鏈路的鏈路可用時(shí)間。
    路徑可用時(shí)間為各個鏈路可用時(shí)間的最小值，因?yàn)楫?dāng)路徑中存在一條鏈路不可用時(shí)，則整個路徑不可用。路徑可用時(shí)間為
   
    其中，任意鏈路(i，j)∈P。
1．2 LARP路由協(xié)議
    LARP路由協(xié)議建立在DSR協(xié)議的基礎(chǔ)上，分為路由發(fā)現(xiàn)和路由維護(hù)兩個部分。其中，路由維護(hù)部分與DSR相同，主要區(qū)別存在于路由發(fā)現(xiàn)的選擇過程中。
    LARP協(xié)議的路由請求包在DSR的基礎(chǔ)上添加了預(yù)測的鏈路可用時(shí)間字段LAT(Link Available Time)和當(dāng)前時(shí)鐘字段CT(Current Time)，用于記錄路由路徑中各個預(yù)測的鏈路可用時(shí)間和路由請求包經(jīng)過各個鏈路的時(shí)間。在各個節(jié)點(diǎn)的路由表中也增加了路徑可用時(shí)間字段PAT(Path Available Time)，用于存放各個路徑的可用時(shí)間信息。
    (1)在路由發(fā)現(xiàn)階段，路由請求包在增加的LAT和CT兩個字段中記錄沿途各個鏈路的可用時(shí)間和路由請求包經(jīng)過相應(yīng)鏈路的時(shí)間。
    (2)當(dāng)路由請求包到達(dá)目的節(jié)點(diǎn)后，提取其中的預(yù)測鏈路可用時(shí)間參數(shù)(LAT)和時(shí)鐘參數(shù)(CT)，利用式(4)計(jì)算出該路徑的可用時(shí)間。
    (3)目的節(jié)點(diǎn)收到的多個路由請求包代表從源節(jié)點(diǎn)到該目的節(jié)點(diǎn)的多個可能路徑，求出每條路徑的可用時(shí)間信息后，目的節(jié)點(diǎn)為每個路由請求包回復(fù)一個路由應(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個節(jié)點(diǎn)，拓?fù)鋮^(qū)域?yàn)?000×1000m，網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布。移動模型采用隨機(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ù)流，每個源節(jié)點(diǎn)每秒發(fā)送120個512字節(jié)的CBR分組。仿真時(shí)間為1000s。結(jié)果如下：

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

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

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