Ad hoc 網絡的一種改進路由算法

陳 恒

（山東青年政治學院實驗設備管理處，山東濟南 250103）

0 引言

Ad hoc 網是一種多跳的、結構變動性強的自組織無線網絡。整個網絡中節點處于移動狀態，并且以分布式協議保持與其他節點的聯系。在這種網絡中，沒有固定的基礎設施。由于終端無線覆蓋取值范圍的有限性，2 個無法直接進行通信的用戶可以借助其他節點組成臨時鏈路完成通信［1］。因為可以方便地隨機組網，因此這種網絡在各種臨時性的無線通訊中應用廣泛。但是由于各節點的移動性，可能造成通信鏈路斷開而反復進行路徑的重構。為了避免這種情況發生，本文提出一種改進的路由算法，在考慮路徑距離的同時關注路徑的穩定性，避免路徑的頻繁重構［2-4］。

1 原理介紹

傳統通信網絡的各級節點設備相對固定，設備性能在滿足通常負載量的情況下一般還具有一定余量，因此網絡穩定性較好。在這種前提下，網絡的路由算法比較關注時效性，即跳數少、距離短、速度快等指標。但是對于Ad hoc 網絡來說，每一個節點既可以是通信終端又可能承擔路由功能?？紤]到移動性的特點，最短路徑的穩定性未必好。具體如圖1 所示。

XLMY 是通信始端X 和終端Y 之間的最短路徑，但是在這條路徑上有中間節點處于傳輸范圍的邊緣，隨著節點的移動，此條線路發生斷裂的可能性較大。另一條線路X0PQRY，雖然距離遠但是穩定性顯然較好。因此在該網絡系統中應統籌考慮線路的穩定性和距離的大小，從而確定最佳的路由選擇。

Ad hoc 網絡的通訊是否成功，取決于接收到信息的信號噪聲比：S/N=Ps/Pn。其中Ps為信號功率，Pn為噪聲功率。指定通道穩定因子：WDF=（S/N）/（S/N）th，其中（S/N）th為信噪比的閾值。當WDF＞1 時，信息傳輸正常，否則信息無法正確傳送。

圖1 邊緣節點示意圖

假設在某一通訊中，發射端到接收端存在t 條路徑，指定該通訊中的穩定因子為ZWDF=min｛WDFk｝，k∈t，即所有路徑中穩定性最小的因子為此通訊過程中的路徑穩定因子。同時還應考慮到，在Ad hoc 網絡中，隨著中間節點數量的增加，端到端的通信速率會明顯下降。所以需要在穩定性和效率之間進行綜合評判。在保證線路穩定的情況下，應選擇中間節點少的路徑。定義路徑判斷依據：J=ZWDF/H-count。此處，ZWDF 為一通訊中的穩定因子，H-count 為該路徑的節點數。當2 節點間有多條路徑可供選擇時，路由算法對J 進行排序，選擇J 值最大的路徑為首選，其他路徑按排序大小候選。

2 技術實現

2.1 路由發現過程概述

當網絡中2 節點間要進行通訊時，系統先查詢現有路徑中是否有滿足要求的選擇，如果沒有源節點首先向其鄰節點廣播“路由請求”報文。信息中包含分組Group，該分組由以下內容構成：

S-Node//源節點編號；

D-Node//目的節點編號；

Se-ID//報文順序號（標示該組信息編號）；

R-ID//路徑中的節點列表；

ZWDF//路徑穩定因子，為各條路徑中穩定因子的最小值；

H-count//途徑節點的個數；

當某節點收到一個Group 分組信息時，若確定該節點是目的節點，則發送路由確認消息給源節點。若（1）該節點是中間節點，（2）該節點不在路徑節點列表中，（3）該節點未收到過此分組信息，則將自己的信息加入到節點了列表中，并比較分組信息中ZWDF 與該路徑的WDF 的大小，并將較小值替換Group分組中的ZWDF 值，同時將途徑節點的個數H-count 加1，之后將該分組信息繼續廣播。若不滿足條件（2）（3），則說明對該節點在之前已進行過判別，可不予考慮。若有多條路徑可供選擇，對比綜合判斷依據J 的大小，選擇J 值最大的路徑。

2.2 路由維護過程概述

在進行網中通訊時，路徑的選擇既要考慮穩定性因素，又要考慮通信速率的因素，因此選擇結果一般依賴于綜合判斷依據J 的大小。在通訊發起時將ZWDF 值賦予一個足夠大的值，在路由的過程中，即時比較ZWDF 值與現有路徑的WDF 的大小，并將較小值賦予ZWDF 值，從而實現對J 值的優化調整。

但是當ZWDF 值接近于1 時，應引起高度重視。此時意味著通訊過程處于穩定性崩潰的邊緣，通訊鏈路有較大可能斷開，從而引起路徑的重新構造。如不預先處理，必然引起網絡中負載量的大幅增加。源節點接收到即時的Group 信息后，如果發現以上情況，立即啟動預先切換模式，根據J 值的候選順序，將通訊切換到備用線路上，從而避免路徑的頻繁重構。

在信息傳輸過程中，所有節點各自維護自己的線路信息狀態表，表中含有如下字段：N-List，WDF，time。N-List 字段內容為臨節點的ID 號；WDF 為通道穩定因子；time 為WDF 維持現值的時間。按照之前的定義，WDF 的取值等于某節點接收到的正確信號的功率與接收到的噪聲信號的功率之比。當WDF 的值長時間未得到更新時，為避免該線路退出路徑選擇，此時啟動廣播機制，向鄰近的節點發送WDF-應答信號。其他節點收到該信號時，向發射節點回傳一個應答，從而通過該通信過程計算出通道穩定因子WDF 的最新取值，用以進行路徑選擇。當通訊線路中多條通道都可使用時，依據J 值的大小，選擇綜合性能較好的幾線路，由系統自動控制向目的節點發送狀態確認信息，目的節點收到信息后回傳應答信號至源節點。由此實時更新鏈路狀態，以保證當前線路在穩定性達到臨界值前，通訊過程及時切換到備用路徑。

3 性能測試

3.1 測試環境介紹

為了對改進后的實際效果有直觀的了解，可以采用仿真軟件對改進算法和普通DSR 算法進行性能比較。采用NS2 軟件進行仿真，測試范圍：800m×800m；網絡類型：Ad hoc 網絡；設置有效帶寬為2Mb/s；每節點無線信號通訊范圍：150m；節點的移動速度在10m/s 以內變化。共設定40 個節點隨機分布在測試范圍內，通信中源節點和目的節點隨機選取，選擇恒定比特率的數據，包長256 字節，發送速率為每秒300 包，仿真時間設置為500s，重復30 次，對取值平均處理后進行對比。

3.2 性能分析

該仿真主要在節點移動的情況下，考察改進算法和DSR 協議的分組成功傳輸率、延時抖動和開銷性能的差異。由圖2 可以看到，在節點移動速度較小時，2 種方式的成功傳輸率都比較高，且差別不太大。隨著移動速度的增加，DSR 協議的成功傳輸率快速下降。改進算法的成功率雖然也有下調，但明顯高于前者。合理的解釋是隨著節點移動速度的增加，鏈路的穩定性快速下降。改進算法中由于具備了鏈路穩定性檢測及備用鏈路的切換機制，所以確保了成功傳輸率沒有出現嚴重的下滑。

由圖3 可以看到節點移動速度對延時抖動的影響。DSR算法隨著節點移動速度的增加，其穩定性明顯下降。因此，整個通訊過程中可能要頻繁進行通道的重構，DSR 協議由于不具備這方面的預處理機制，所以其延時抖動增加明顯。

圖4 可以看到，在節點移動速度較小時，通訊線路的穩定性尚可，由于改進算法加入了若干監測信息，因此其網絡開銷略大于DSR 協議。隨著節點移動速度的增加，DSR協議鏈路穩定性下降，其斷開次數不斷增加，此時需要頻繁進行網絡重構，由此向網絡中發起大量廣播信息，帶來的結果就是產生大量網絡開銷。改進算法的優化機制發揮作用后，可有效控制網絡開銷的大幅增加。

4 結論

針對Ad hoc 網絡在實際應用中對鏈路穩定性比較敏感的特點，本文提出了一種基于穩定性檢測和不穩定鏈路預處理的方法。這種方法綜合考慮了網絡的穩定性和通信速率。仿真結果表明，改進后的路由算法可以提高通訊線路的穩定性，避免鏈路的反復重構，大幅降低無效網絡開銷，從而切實改進了通訊質量。

圖2 通訊成功傳輸率示意圖

圖3 延時抖動示意圖

圖4 通訊開銷示意圖

［1］孟昊，鐘章隊，艾渤.Ad Hoc 網絡路由協議研究及其性能比較［J］.信息與電子工程，2009（2）：151-155.

［2］陳躍泉，郭曉峰，曾慶凱，等.Ad Hoc 網絡多路徑研究［J］.計算機科學，2005（6）：33-36.

［3］孫寶林，李臘元.多跳無線移動Ad Hoc 網絡路由協議的研究分析［J］.小型微型計算機系統2004（10）：1737-1741.

［4］李云，趙為糧，隆克平，等.無線Ad Hoc 網絡支持QoS 的研究進展與展望［J］.軟件學報，2004（12）：1885-1893.

［5］張暉，董育寧，楊龍祥，等.移動Ad hoc 網絡中基于穩定性的QoS 路由算法綜述［J］.計算機工程與應用，2009（1）：1-5.