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

陳 恒

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

0 引言

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

1 原理介紹

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

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

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

圖1 邊緣節(jié)點示意圖

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

2 技術實現

2.1 路由發(fā)現過程概述

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

S-Node//源節(jié)點編號；

D-Node//目的節(jié)點編號；

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

R-ID//路徑中的節(jié)點列表；

ZWDF//路徑穩(wěn)定因子，為各條路徑中穩(wěn)定因子的最小值；

H-count//途徑節(jié)點的個數；

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

2.2 路由維護過程概述

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

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

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

3 性能測試

3.1 測試環(huán)境介紹

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

3.2 性能分析

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

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

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

4 結論

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

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

圖3 延時抖動示意圖

圖4 通訊開銷示意圖

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

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

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

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

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