Ad hoc 網(wǎng)絡(luò)的一種改進(jìn)路由算法

陳 恒

（山東青年政治學(xué)院實(shí)驗(yàn)設(shè)備管理處，山東濟(jì)南 250103）

0 引言

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

1 原理介紹

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

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

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

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

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

2 技術(shù)實(shí)現(xiàn)

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

當(dāng)網(wǎng)絡(luò)中2 節(jié)點(diǎn)間要進(jìn)行通訊時(shí)，系統(tǒng)先查詢現(xiàn)有路徑中是否有滿足要求的選擇，如果沒有源節(jié)點(diǎn)首先向其鄰節(jié)點(diǎn)廣播“路由請(qǐng)求”報(bào)文。信息中包含分組Group，該分組由以下內(nèi)容構(gòu)成：

S-Node//源節(jié)點(diǎn)編號(hào)；

D-Node//目的節(jié)點(diǎn)編號(hào)；

Se-ID//報(bào)文順序號(hào)（標(biāo)示該組信息編號(hào)）；

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

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

H-count//途徑節(jié)點(diǎn)的個(gè)數(shù)；

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

2.2 路由維護(hù)過程概述

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

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

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

3 性能測(cè)試

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

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

3.2 性能分析

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

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

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

4 結(jié)論

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

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

圖3 延時(shí)抖動(dòng)示意圖

圖4 通訊開銷示意圖

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

［2］陳躍泉，郭曉峰，曾慶凱，等.Ad Hoc 網(wǎng)絡(luò)多路徑研究［J］.計(jì)算機(jī)科學(xué)，2005（6）：33-36.

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

［4］李云，趙為糧，隆克平，等.無線Ad Hoc 網(wǎng)絡(luò)支持QoS 的研究進(jìn)展與展望［J］.軟件學(xué)報(bào)，2004（12）：1885-1893.

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