Adhoc網絡中不相關多路由源端尋路算法

周婧

摘 要 路由方案是Ad hoc網絡中一個熱點研究領域。其中，按需路由算法由于其有效性在帶寬受限的Ad hoc網絡中得到比較大的發展。然而大部分的按需路由算法，建立并只使用單條路由，當當前使用的路徑的鏈路斷開時，路由算法必須執行一個路由修復過程。本文提出了不相關多路由源端路由算法（DMSR），建立并利用多條最大不相關路由。在本文算法中，中間節點等待一段時間以得到多個路由請求包（RREQ），然后在這個RREQ中，選擇相關性最小的多路徑，并將這些信息寫入一個RREQ中，并將它廣播出去。從仿真結果可以看出本文的算法提高了數據包的正確傳輸率和業務均衡。

關鍵詞 通信保障 綜合保障 項目管理

1 引言

Ad hoc網絡是沒有中心節點的自組網絡，在這個網絡中，沒有固定的路由器，或者無線基站。在Ad hoc網絡中，移動節點之間的通信是通過點到點的多跳技術實現的，這就意味著網絡拓撲動態的變化，這就產生了許多值得探討的問題。在Ad hoc網絡中，路由技術是至關重要的，在任何業務連接之前，都首先必須完成尋路的過程。

目前，Ad hoc網絡中最多的是按需路由。然而，很多已經提出的按需路由協議，如傳統的DSR[1]，AODV[2]算法都只為每一個連接建立一條路徑，這不僅不能充分利用資源，而且無法有效處理擁塞，鏈路斷開等情況。多路由算法可以解決這些問題。使用多條路徑可以提高帶寬的有效利用率和傳輸可靠性以達到一定的QoS保證。

目前，對多路由的研究主要集中在以下兩個方面：建立多路由和在這些多路由之間分配業務的策略。

本文提出一種新的不相關多路由源端路由算法（DMSR）。DMSR算法在DSR算法的基礎上主要做了以下的改進：在尋路過程中，每個中間節點等待一段時間以接收到多個RREQ，然后在這個RREQ中，選擇相關性最小的多路徑，并將這些信息寫入一個RREQ中，并將它廣播出去。DMSR可以找到最大不相關路徑，因此可以減小發起路由頻率，以減小時延，同時可以提高數據包的正確傳輸率。

2 Ad hoc中的多路由

在網絡拓撲不確定的情況下，尋找到不相關的多路由是比較困難的。DSR協議能夠尋找到多條路由，并在主路由斷裂的情況下將其他路由作為備份路由。然而，DSR并未將不相關性考慮進來。在本篇文章里提出一種尋找不相關的多路由的方法。

2.1 DSR中的路由發現

在DSR算法中，如果源節點不知道到目的節點的路徑，那么源節點將通過洪泛路由請

求消息（RREQ）發起一個路由發現。在RREQ包頭中將依次記錄下這個RREQ包所經過的節點的地址。當一個節點接收到一個RREQ包，如果這是第一次接收到這個具有相同源節點地址和ID的RREQ包，這個節點經過處理將RREQ廣播出去。反之，節點將這個RREQ丟棄。一點RREQ到達目的節點，目的節點將經過RREQ中包含的路徑返回一個路由回復消息（RREP）到源節點。當RREP到達源節點，源節點和所有中間節點都會知道一條到達目的結點的路徑。

DSR中這種廣播RREQ的方式極大的減小了找到不相關的多路徑的可能性。也就是說DSR算法最后找到的多條路徑的一些節點是相同的。在一些文章的仿真結果中DSR找到完全不相關的多路徑的可能性幾乎為零。造成這種結果的原因是中間節點將丟棄后收到的相同的RREQ，而這些RREQ中包含著不相關的路徑。

2.2 不相關源多路由算法

A.路由發現

DMSR充分利用后來接收到的RREQ包。

當一個中間節點收到第一RREQ包，它不是像DSR那樣立刻將自身地址加到這個RREQ上并將這個RREQ廣播出去，而是將收到的RREQ儲存在高速緩沖存儲器中，同時啟動一個定時器，在定時器的這段之間內，該節點等待其它相同的RREQ（即具有相同源節點地址和RREQ ID的RREQ）。

當節點收到相同的RREQ，它首先要檢查這個RREQ中路徑的跳數是大于、小于或者等于之前收到的相同的RREQ的跳數。如果是大于，則節點丟棄該RREQ；如果等于，節點將RREQ記錄在cache中；如果小于，節點將刪除之前接收到的相同的RREQ，同時將新收到的RREQ記錄在高速緩沖存儲器中。

為了減小RREQ造成的信令開銷，限制一個節點最多記錄三條相同的RREQ。為了減小時延，如果已經記錄下三條RREQ，就將定時器歸零，開始處理高速緩沖存儲器中的RREQ。

當定時器到時，開始處理高速緩沖存儲器中記錄的RREQ：

（1）如果高速緩沖存儲器中只有一個RREQ，該節點將自身地址附加在RREQ中的路由紀錄中，并將它廣播出去；

（2）如果高速緩沖存儲器中有不止一個RREQ，節點檢查是否存在一個RREQ中只有一條路徑。如果存在這樣的RREQ，節點首先選擇這條路徑，然后在其他RREQ中分別選擇一條與該路徑相干系數最小的路徑；如果相干系數一樣，則選擇首先記錄下的那條路徑；如果所有的RREQ都包含不止一條路徑，則節點首先選擇第一個收到的RREQ的第一條路徑，其他路徑的選擇準則見2），然后：

（3）選擇完路徑，節點將自身地址附加到所選擇的路徑上，并將這些路徑寫到原來收到的RREQ中，這些路徑的寫入順序是：首先收到的RREQ中選擇的路徑是第一條路徑，第二個收到的RREQ中選擇的路徑是第二條路徑，同樣的，從最后收到的RREQ中選擇的路徑是第三條路徑。然后節點將新的RREQ廣播出去。

當第一個RREQ到達目的節點，目的節點等待一段時間以接收到更多的RREQ，并從這些RREQ中選擇相干最小的多路徑。

在DMSR算法中，在一段時間內收到的RREQ中，中間節點選擇跳數最小的路徑。因此，在目的節點可以得到跳數最小的路徑。同時DMSR算法中，優先選擇先到達的路徑，這同樣可以減小時延。

路徑中的一條鏈路可能由于移動、擁塞、包沖突而斷裂，因此，修復斷裂的路徑非常重要。在DMSR算法中，當一個節點不能夠將包傳送到下一個節點，就認為到下一個節點的鏈路已經斷開，于是發出一個路由錯誤包（RRER）到這條路徑的上游節點。這個RRER包中包含到源節點的路徑，以及斷開鏈路的上游、下游節點。一旦收到RRER包，源節點將刪除其路由表中所有使用斷開路由的表項，而同時源節點使用剩余的路徑傳送數據包。當所有的路徑斷開，源節點將重新發起一個路由發現過程。

2.3 DMSR和DSR的比較

圖2表示的是DMSR找到的多路徑，可以看出這些路徑是不相關的。圖3表示的是DSR找到的多路徑，這些多路徑幾乎是重疊的。可以看出，DMSR比DSR尋找多路徑的效率高得多。

3 仿真結果

3.1 仿真環境

3.3 結果與分析

圖4所示的是DMSR與DSR算法的數據包的正確傳輸率。從圖中可以看出，相對于DSR，DMSR提高了性能，尤其是當移動性增加時。當使用多路由時，移動性增加，性能的提高變得明顯，這是因為在DSR算法中，每一對業務只使用一條路徑，當這條路徑失效時，源節點必須重新尋找一條新的路由，在此過程中，會造成包的丟失。但是在DMSR中，源節點可同時使用三條并行路徑，因此重新尋路的頻率被大大減小，尤其當移動性增大時，因此DMSR能夠正確傳送更多的數據包。

圖5所示的是兩種算法的平均端到端時延。可以看到兩種算法的時延幾乎相同，但是DMSR算法比DSR算法的時延略微大一點。在DMSR中路由發現的頻率減小可以減小時延，但是在DMSR的尋路過程中RREQ必須從源節點發送到目的節點以尋找到多條路徑，而在DSR中，尋路過程中的任一節點可以使用自己路由表中的信息，不需要一定要將RREQ包發送到目的節點，在這方面，DSR可以減小時延。

圖6所示的是兩種算法負載均衡的結果。從圖中可以看出DMSR的網絡CoV性能優于DSR。這是因為DMSR可以將網絡業務分攤到多條路徑上。而在DSR算法中所選用的路徑為源節點與目的結點之間的最短路徑，因此會將更多的業務分配到這些路徑上。隨著休息時間的減少，DMSR和DSR的網絡CoV也減小，這表明移動性可以均衡負載。

4 結論

在本篇文章中，提出了一個新的ad hoc中的DMSR算法。DMSR算法在DSR算法的基礎上主要做了以下的改進：在尋路過程中，每個中間節點等待一段時間以接收到多個RREQ，然后在這個RREQ中，選擇相關性最小的多路徑，并將這些信息寫入一個RREQ中，并將它廣播出去。本文對DMSR的性能進行了研究，結果表明DMSR可以提高數據包的正確傳輸率和業務均衡性。

參 考 文 獻

[1] D. Johnson and D. Maltz， Dynamic source Routing in Ad Hoc wireless networks， in Mobile Computing， T. Imielinski and H. Korth， editors， Kluwer Academic，1996.

[2] C.E. Perkins and E.M. Royer， Ad-hoc On-Demand Distance Vector Routing，Proc. 2nd IEEE Wksp. Mobile Comp. Sys. And Apps.， Feb. 1999， pp.99-100.