Ａｄ ｈｏｃ網絡中一種新的路由選擇算法

摘 要：提出了一種基于網絡總時延最小的路由路徑選擇算法。該算法根據鏈路的時延來進行路由路徑選擇，從而達到網絡總時延最小的目的。仿真表明，該算法可以動態調整網絡路由路徑，從而使網絡總時延達到最小。

關鍵詞：Ad hoc; 路由路徑;時延

中圖法分類號：TP393文獻標識碼：A

文章編號：1001—3695(2007)02—0316—02

移動Ad hoc網絡（MANET）是指一組帶有無線收發裝置的移動節點組成的一個多跳的臨時性的自組織系統。整個網絡系統沒有固定的基礎設施，所有節點都是移動的，并且都可以動態方式動態地保持與其他節點的聯系。

由于節點移動、信道干擾和能源消耗等因素，Ad hoc網絡的拓撲結構具有動態變化特性，這給高性能路由協議的設計帶來很大的挑戰。迄今為止，已有多個Ad hoc網絡路由協議被用于Ad hoc網絡，如AODV[1]，DSDV[2]和DSR[3]。但是多數路由協議在路由選擇時都是以跳數最少作為選擇的依據。由于一條路徑的帶寬是有限的，當很多節點選擇此路徑作為路由路徑時，將會造成網絡擁塞，從而使網絡時延加大。因此本文把時延作為評估參數，提出了一種新的路由選擇算法。在本路由選擇算法中，當路由協議發現N條路徑時[2]，將以使網絡總時延最小作為路由路徑選擇的依據。

1 理論分析

影響Ad hoc 網絡性能參數有很多，主要有時延、分組丟失率等。但是筆者只選用了網絡時延作為路由路徑選擇的依據，這是因為一條路徑的時延容易獲得，只需要一條路徑兩端的源目節點間發送檢測分組即可得到。而其他參數很難用簡單的方法實時測量到，如分組丟失率。所以時延具有最重要的實際意義[4]，因此將時延作為路由選擇的基準。

我們設計路由選擇算法的目標是使整個網絡的性能達到最優化，在這里根據式（1），在M條路徑中選擇一條Fi最小的路徑作為可選擇的路由路徑，即分組x所選擇的路由路徑為

對于Ad hoc網絡中的單個節點來說，通信時延來源于排隊時延、處理時延和傳輸時延等。對于單個數據包而言，處理時延和傳輸時延較為固定，而排隊時延受網絡的擁塞程度影響，變化較大。在排隊論中，節點的接收和發送可以用馬爾可夫M/M/1服務模型[7]分析。根據Little公式可知，數據包的平均時延符合以下關系：

在有線網絡中，路由節點的接收和發送能力固定不變，而且互不影響。在Ad hoc網絡中，節點的接收和發送共享相同的無線信道，相互影響。設節點的處理能力為B（接收和發送共享），那么μ=B-λ，所以數據包的平均時延關系式變為

根據上述分析，可以計算每條鏈路平均時延，據此就可選取其中使網絡總時延最小的鏈路作為最終選擇的路由路徑。

2 算法描述

在本文提出的基于網絡總時延最小的路由路徑選擇算法執行時，只要建立合理的時延數學方程，如式（4）所示，就可以進行基于網絡總時延最小的路由路徑選擇了。但是式（4）依賴于路徑的有效帶寬和固有流量。在Ad hoc網絡中，它們都是動態變化且缺乏有效的辦法來測量。因此在實際網絡中，僅根據式（4）來進行路由選擇是不可行的，式（4）僅可用于從理論上分析路由選擇問題，因為實際網絡的平均時延往往與式（4）有一定偏差，根據式（4）進行動態流量分配是不精確的。本文提出了可用于實際網絡中路由路徑選擇算法，將網絡時延作為直接目標。鑒于路徑時延是實際可測的，我們使用類似于IGMP的Ping功能測量路徑的時延，并將這個時延作為路由路徑選擇的依據。算法的詳細步驟描述如下：

(1）據文獻[2]中的方法，在源節點與目的節點間探測多條路由路徑。

(2）動態檢測時延分組。啟動時延分組的實現類似于IGMP的Ping功能。源節點沿各條已知的路由路徑發送檢測分組，并打上時戳Ti，目的節點收到分組后直接按原路徑回復，并打上時戳Tj，則平均時延應該是E(Tj-Ti)。

(3）據測得的每條路由路徑的時延，找出其中使整個網絡的總時延達到最小的路由路徑作為源節點最終選擇的路由路徑。

(4）一個測量間隔之后，重復執行(2) 。

從上述對算法的描述可以看出，該算法可以根據網絡中各條路徑的時延情況動態調整從源節點到目的節點的路由路徑，使整個網絡的總時延動態達到最小，從而達到優化網絡性能的目的。

3 仿真分析

為了進一步驗證本文算法的有效性，筆者建立仿真實驗進行驗證分析。源節點到目的節點的路徑為四條，每條路由路徑上的固有流量速率分別為120，80，150和150，并隨時間發生緩慢變化，如圖 2所示。從源節點到目的節點的流量為20。四條路徑的服務速率分別為400，500，600和400。

為了與傳統基于跳數最少進行路由選擇的路由算法進行比較，我們采用各路徑跳數依次為N1=5，N2=5，N3=5和N4=3，對本算法性能進行了仿真。

圖3為把從源節點到目的節點的流量依次加載到各條路徑上，從而得到的不同路徑的時延曲線。從圖3中可以看出，由于路徑1—4上的固有流量不同，因此其鏈路時延情況也不相同。曲線Line 1—Line 4 依次是各路徑的時延曲線。由于第一條和第四條路徑的起始固有流量多，因此其時延也比較大，但是隨著流量的遞減，其時延也在逐漸減小；而對于第二條和第三條路徑，由于其起始固有流量比較少，因此時延比較小，但是隨著流量的增加，時延在逐漸增加。

圖4 為選擇不同路徑作為路由路徑時，整個網絡的總時延變化情況。圖4中所示的曲線Line 1是指選擇第一條路徑為路由路徑時，網絡的總時延（四條路徑的時延總和）情況；曲線Line 2為選擇第二條路徑作為路由路徑時，網絡的總時延情況；曲線Line 3和Line 4含義依此類推。從圖4中可看出，隨著各條路徑上的流量變化，上述四條曲線的網絡總時延情況也在發生變化。在仿真初期，曲線Line 4的網絡總時延最大，而曲線Line 2的網絡總時延最小，但是隨著仿真的進行，上述四條曲線的時延均在發生著緩慢的變化；在仿真后期，曲線Line 3的網絡總時延最大，Line 1的網絡總時延最小。為了使網絡總時延達到最小，我們在進行路由路徑選擇時，首先選擇第二條路徑作為路由路徑，當Line 1的網絡總時延小于Line 2時，調整路由路徑，將第一條路徑作為路由路徑。

圖5 為本文提出的基于網絡總時延最小路由路徑選擇算法和基于跳數最少路由路徑選擇算法的網絡總時延情況變化的比較。從圖5可以看出，本文采用的算法相對于基于跳數最少的算法可以使網絡的總時延實時達到最小，從而達到優化網絡性能的目的。 

4 結束語

本文針對Ad hoc網絡在已知M條路由路徑的情況下，如何進行路由選擇問題，提出了基于網絡總時延最小的路由選擇算法。仿真表明，本文的算法在路由路徑選擇時，可以保證網絡的總時延實時達到最小。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。