Ad Hoc網絡是一種特殊的無線移動網絡，網絡中的所有節點地位平等，無需設置任何中心控制節點，既可以快速、自動地組成一個獨立的網絡運行，也可以作為當前具有固定設施網絡的一種補充形式[1]。在軍事、搶險救災等領域應用前景廣闊。

    與現有的有線網絡和有基站的無線網絡有很大不同，Ad Hoc網絡無中心、自組織、動態拓撲和能量有限的特點，使得現有的路由協議(RIP、OSPF)不再適應Ad Hoc網絡,因此路由技術一直是自組網的研究重點之一。目前主要有按需路由和表驅動路由兩類[2]，其中按需路由協議不必維護到達所有節點的路由,有效地節省了網絡資源，能夠較好地適應節點移動帶來的動態拓撲問題，得到了廣泛應用，其典型代表是AODV[3-4]協議。本文在AODV路由協議的基礎上，提出基于鏈路中斷預測的路由算法(RP-AODV), 能夠降低廣播開銷,提高網絡性能。
1 研究現狀
    針對路由可能發生中斷的問題，路由修復算法被提出。最簡單的修復算法是由源節點重新發起新的路由發現過程，顯然這會帶來極大的網絡開銷。參考文獻[3]認為路由斷裂時，斷裂處上游的節點會率先發現路徑失效，此時直接由該節點發起到目的節點的路徑修復過程。如果收到目標節點的應答，則說明路徑重建成功；如果路由發現規定時間內沒有收到目的節點返回的RREP，則向其上游節點發送該目的節點的RERR，直到通知到該路由的源節點，然后再由源節點進行新一輪的路由發現。
    參考文獻[5]提出一種兩跳范圍局部修復改進算法，當節點A到節點B失效時,在斷鏈的附近可能存在A、B的鄰居節點，因此由斷鏈的上游節點發送兩跳路由請求分組尋找下一跳節點B，使得修復限制在兩跳范圍內，路由開銷將會減少，尋路時間減短。
2 基于鏈路中斷預測的AODV路由算法設計
2.1 算法思想
    從降低開銷的角度，最理想的是路徑不中斷，但因為節點的移動性，即使采用穩定路由策略獲取的路由也會發生路徑中斷。而當路徑中斷之后再去修復，都會帶來較大的額外開銷，同時增大時延。如果在路徑中斷之前，能夠預測到即將中斷，提前采取措施尋找備用路由，則可以實現平滑的路徑切換，當鏈路中斷不可避免時，不必返回源節點搜索，而是逐層由上游節點展開局部搜索，在保證傳輸時延的同時使得路由開銷最小。
    節點的移動導致節點間鏈路中斷，但在較短時間內，節點并不會走遠，仍在原位置附近，在較短時間內節點的活動范圍也往往是以短途和小范圍為主[6-7]。同時鏈路中斷處也存在其他的鄰居節點。因此當鏈路中斷時可以在斷點附近展開鏈路修復，沒必要全網重新開始新的路由。如圖1所示，鏈路中斷一般有多種情況，圖1(a)中源節點S和目的節點D，經由A、B、C三個中間節點組成一條鏈路。隨著節點的移動，鏈路出現斷裂，如圖1(b)所示，B節點移動出了A的覆蓋范圍，A與C之間失去了聯系，但是存在E節點可以同時連接A和C，則可以選擇E取代B。如果E節點不能同時覆蓋到A和C，但可以覆蓋到A和B，如圖1(c)所示，則可以在原鏈路中增加一個E節點，鏈路變為S-A-E-B-C-D。如果B和E都移動出了A的覆蓋區域，如圖1(d)所示，則A到下游節點的鏈路完全中斷了，必須由它的上游節點開始新的鏈路搜索。

    基于這樣一種思想，將路由維護的過程分解為兩個步驟：(1)監聽路由中各個鏈路的聯通情況，判斷鏈路是否會中斷或者是否有更短鏈路的出現。(2)尋找保持鏈路聯通的備用節點，當鏈路出現中斷時，備用節點迅速啟動。如果找不到可用路由，則逐層由更上游節點發起路由發現過程，而并不是返回源節點。
2.2 算法設計
    鏈路的中斷是由節點的移動導致的，但鏈路的中斷最終是由信號質量下降引起。因此判斷鏈路中斷最有效的方法是監測鏈路信號質量。無線信號在傳輸過程中存在著慢衰落和快衰落，多種因素會引起信號質量的起伏，為了避免頻繁的鏈路切換，可以取一個時間窗口，在這個窗口中取均值，作為判斷依據。
    AODV的路由機制中上游節點路由表中存有下一跳節點的信息，而下游節點不知道上游節點，這就決定了當鏈路中斷時，只能由上游節點決定去尋找哪個節點。而不在原鏈路上的節點可以監聽到周圍鏈路的信號質量，能夠知道自己是否可以修補鏈路 (如圖1(c)中的情況)，但是無法知道自己何時插入原鏈路，也無法知道是否可以縮短原鏈路(如圖1(b)、圖1(e)的情況)。因此需要修改AODV協議中的路由表，使之存有下面兩跳路由信息，即存放下游鏈路的兩個節點，這樣周圍節點可以通過檢測周邊鏈路信號情況，判斷自己是否處在有用鏈路上。
    根據鏈路斷裂的不同情況，路由維護分為以下幾類：
    (1)由周圍節點自己判斷是否能夠縮短原鏈路長度，如果能則由該節點主動聯系上游和下游節點，確認后啟動新鏈路。
    (2)鏈路可能斷裂處的上游節點通過監聽反向路徑的信號質量，判斷鏈路當前的狀況，然后向周圍節點發起備用節點查詢，找到后確認新鏈路。
　(3)周邊沒有備用節點的情況，由上游節點向更上游節點發送斷鏈請求，從而啟動新的路由搜索過程。在搜索備用節點的過程中，采用擴展環的方法，在網絡層分組的報頭部分設計一個字段TTL，限定為3，表示分組可以被轉發的次數，收到該分組的節點每次將TTL值減1，減至0則停止轉發。
2.3 算法流程
　路由維護的過程主要由鏈路上游節點和周邊節點完成，通過監聽各個鏈路質量，判斷鏈路是否會中斷或者是否有更短鏈路的出現，然后尋找保持鏈路聯通的備用節點，并迅速啟動。找不到備用節點時，鏈路會斷裂，此時啟動ERS算法在3跳之內進行局部路由修復。如果仍然不成功，則由更上游的節點啟動路由發現。算法流程描述如下：
    (1)節點從收到數據包中獲取下游兩跳節點路由信息;
    (2)監聽信號質量，更新時間窗口信息，計算均值，并與設定的閾值比較，判斷鏈路中斷概率;
    (3)上游節點判斷鏈路可能中斷則會啟動ERS搜索， 發起路由修復過程;
    (4)周邊節點判斷可以接續原鏈路或者縮短路由長度，
則會向上下游節點發送應答;
    (5)上游節點收到應答信息，則更新路由表；在規定時間內沒有收到應答，則會向更上游中間節點發送重新路由請求，啟動新的路由發現過程。
3 仿真分析
3.1 仿真模型
    用NS2作為仿真軟件進行了模擬實驗，將本文提出的基于鏈路中斷預測的AODV算法(RP-AODV)與標準AODV協議進行比較，重點關注數據包投遞率、歸一化路由開銷和端到端的平均延遲等3個性能指標。
    數據包投遞率：成功到達的數據包和全部發出數據包的比率。
    歸一化路由開銷：每發送一個DATA數據分組需要的控制消息分組數，其中路由分組每一跳的傳輸均認為是一個新的控制消息分組，反映了網絡的擁塞程度和路由效率。
    端到端的平均延遲：每個數據包從源節點到目標節點間的傳送時延。
    在仿真場景中，100個節點隨機分布在1 500 m×1 000 m 的矩形區域內，每個節點采用IEEE 802.11無線網絡接口，無線傳輸半徑為250 m，單一增益的全向天線，信道容量為2 Mb/s。每次仿真隨機選擇10對源-目的節點傳輸數據，通信源是CBR流，數據包大小為512 B，每秒發送2個包，隊列長度為50。采用Random Way Point 運動模型， 節點最大移動速度Vmax分別為5 m/s、10 m/s、15 m/s、20 m/s、25 m/s，暫停時間為30 s，實驗反復運行50次，每次仿真1 000 s，實驗結果取平均值。
3.2 仿真結果分析
3.2.1歸一化路由開銷
　由圖2可以看出，在不同的最大移動速度下，RP-AODV的路由開銷最小，總體上比AODV減低了40%。說明通過新算法有效控制了鏈路中斷的次數，減小了路由發現的頻次，從而降低了路由開銷。在速度較低時路徑中斷的概率較小，隨著速度的增加，節點的移動性增強，路徑中斷概率增大，路由修復過程出現頻繁，路由開銷都有所增加，但是RP-AODV優勢顯現。當節點移動速度超過20 m/s以后，優勢縮小，主要是因為節點的移定性增強之后，鏈路預測和備份鏈路的選擇的準確性也會隨之下降，增加了路由開銷。總體上來看，RP-AODV相比傳統AODV算法歸一化路由開銷降低40%左右。

3.2.2 端到端平均時延
    圖3給出了平均端到端時延隨節點不同移動速度的變化情況。隨著節點移動速度的增加，RP-AODV和傳統AODV協議的端到端時延都在增加，其中AODV增加的幅度更為明顯。這是因為節點移動速度增加以后，鏈路斷開的幾率增大，路由修復頻次增多，而路由修復過程中數據傳輸中斷，數據包端到端時延增加，RP-AODV算法通過鏈路預測，啟用備用節點，盡量減少路徑斷開的幾率，即使鏈路斷開，也會采用局部修復的方法，降低了路由修復時間，從而減小了端到端時延。總體上來看，RP-AODV相比傳統AODV算法端到端時延降低25%左右。

3.2.3 數據包投遞率
    從圖4中可看出，與傳統AODV算法相比，改進的RP-AODV算法數據包投遞率有所提高，在節點最大移動速度不大時，兩者相差不大，這是因為節點移動較弱時，鏈路斷開的幾率較小，發起路由修復次數較少，數據包投遞率差別不大。當最大移動速度較大時，傳統AODV算法和算法投遞率都有所下降，但RP-AODV仍然優于傳統AODV。這主要是因為節點移動性提高之后，鏈路斷開的幾率增大，路由修復頻次增多，修復不成功的幾率也隨之增加，從而導致數據包投遞率有所下降。在路由修復過程中，RP-AODV能夠快速地找到備用節點，盡最大可能地保持原路由有效，減少了路徑中斷次數，從而提高了數據包投遞率。

    本文針對傳統AODV路由協議中的路由修復方法開銷大、時延長這一問題，設計了一種基于鏈路中斷預測的改進算法。通過監測鏈路質量，預測鏈路中斷概率，及時啟用備用節點，盡量避免路由修復；而當鏈路中斷時，采用逐層由上游節點發起的局部路由搜索，減小控制開銷的波及范圍。算法在經典的AODV協議上實現(稱之為RP-AODV)，并用NS2模擬軟件進行了仿真。仿真結果表明，在多種場景下新算法都降低了路由開銷，有效地提高了網絡性能，與傳統AODV相比控制開銷降低了40%，端到端時延減少了25%。
參考文獻
[1] CHLAMTAC I,CONTI M,LIU JN. Mobile Ad Hoc networking: imperatives and challenges[J]. Ad Hoc Networks,2003,1(1):13-64.
[2] 李世寶, 洪利. 基于距離預測的移動自組網路由發現算法[J].通信學報， 2010,31(11):180-187.
[3] PERKINS C, BELDING-ROYER E. AODV Ad Hoc Ondemand distance vector Routing[S]. The Internet Engineering Task Force, IETF, RFC 3561, 2003.
[4] NI S Y, TSENG Y C, CHEN Y S. The broadcast storm  problem in a mobile ad hoc network[A]. the Fifth Annual  ACM/IEEE International Conference on Mobile Computing  and Networking (MOBICOM 99)[C]. Seattle, Washington, 1999:151-162.
[5] 丁緒星,吳青,謝方方.AODV 路由協議的本地修復算法[J]. 計算機工程, 2010,36(6):126-127.
[6] GONZALEZ M C, HIDALGO CA, BARABASI A L. Understanding individual human mobility patterns[J]. Nature, 2008,453:779-782.
[7] RHEE I, SHIN M, HONG S, et al. On the levy walk nature of human mobility[A]. INFOCOM 2008:the 27th Conference on Computer Communications[C]. Phoenix, AZ, 2008:924-932.