張永忠，陸宏治

(1.廣州通信研究所，廣東廣州 510310;2.廣東電網(wǎng)公司廣州供電局，廣東廣州 510620)

0 引言

近年來(lái)，無(wú)線(xiàn)網(wǎng)絡(luò)接入業(yè)務(wù)發(fā)展迅猛。無(wú)線(xiàn)移動(dòng) Mesh網(wǎng)絡(luò)(Wireless Mobile Mesh Networks，WMMN)是在無(wú)線(xiàn) Ad Hoc網(wǎng)絡(luò)(Wireless Ad Hoc Network，MANET)和無(wú)線(xiàn) Mesh網(wǎng)絡(luò)(Wireless Mesh Network，WMNET)的基礎(chǔ)上發(fā)展起來(lái)的一種新型網(wǎng)絡(luò)形態(tài)，融合了已有的MANET及WMNET網(wǎng)絡(luò)的特點(diǎn)。由于無(wú)線(xiàn)移動(dòng)Mesh網(wǎng)絡(luò)具有大規(guī)模、異構(gòu)性和自組織等技術(shù)特點(diǎn)，路由問(wèn)題是最為復(fù)雜的問(wèn)題之一，也是關(guān)鍵技術(shù)之一［1］。

目前國(guó)內(nèi)外關(guān)于移動(dòng)網(wǎng)絡(luò)的路由協(xié)議的分類(lèi)方法，大多根據(jù)路徑是按事前的路徑信息建立還是在發(fā)送數(shù)據(jù)前臨時(shí)建立，將路由協(xié)議分為2種類(lèi)型:先應(yīng)式路由協(xié)議和反應(yīng)式路由協(xié)議;另外，混合式路由協(xié)議［2］則結(jié)合了先應(yīng)式路由協(xié)議和反應(yīng)式路由協(xié)議的特點(diǎn)。

1 AFSLS路由算法設(shè)計(jì)思路

根據(jù)無(wú)線(xiàn)移動(dòng)Mesh網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)能量敏感較低、移動(dòng)性較低的特點(diǎn)，基于鏈路狀態(tài)的先應(yīng)式路由協(xié)議相對(duì)于反應(yīng)式路由協(xié)議更適合WMMN，尤其是應(yīng)用在WMMN的骨干網(wǎng)部分。此外，標(biāo)準(zhǔn)鏈路狀態(tài)(Standard Link State，SLS)路由具有簡(jiǎn)單性、魯棒性和可預(yù)見(jiàn)的動(dòng)態(tài)性等優(yōu)點(diǎn)，對(duì)基于服務(wù)質(zhì)量路由也有很好的支持［3］。在先應(yīng)式路由協(xié)議中，OLSR協(xié)議是對(duì)標(biāo)準(zhǔn)鏈路狀態(tài)路由協(xié)議優(yōu)化而形成的，具有路徑選擇等待時(shí)延小、路由信息開(kāi)銷(xiāo)小等優(yōu)點(diǎn)。

① 采用多點(diǎn)中繼(Multipoint Relay，MPR)機(jī)制［4］，減少同一區(qū)域內(nèi)部相同控制分組的重復(fù)轉(zhuǎn)發(fā)次數(shù)來(lái)減少網(wǎng)絡(luò)中控制分組的數(shù)量;

②利用高效分發(fā)方法和受限分發(fā)方法提高鏈路狀態(tài)路由協(xié)議的可擴(kuò)展性，并提出一種提高路由協(xié)議擴(kuò)展性的所謂朦朧算法［5］;

③朦朧算法是根據(jù)如下事實(shí)提出來(lái)的:2個(gè)節(jié)點(diǎn)離得越遠(yuǎn)，它們感覺(jué)彼此之間的相對(duì)移動(dòng)性就會(huì)越小。所以為了感知移動(dòng)節(jié)點(diǎn)，對(duì)近處的更新信息發(fā)送要比較迅速頻繁，而遠(yuǎn)處的更新信息可以比較緩慢。朦朧算法的魯棒性強(qiáng)于分層或分區(qū)技術(shù)，也可以節(jié)省路由信息的開(kāi)銷(xiāo)。HSLS路由協(xié)議在朦朧算法這一類(lèi)路由協(xié)議中的性能是最優(yōu)的［3－6］。

2 AFSLS路由算法

在OLSR協(xié)議基礎(chǔ)上，將有限分布路由信息機(jī)制與高效分發(fā)的路由信息機(jī)制進(jìn)行結(jié)合，并整合網(wǎng)絡(luò)拓?fù)錉顟B(tài)變化自適應(yīng)的檢測(cè)模塊和朦朧視覺(jué)算法，提出了一種綜合以上方法優(yōu)點(diǎn)的自適應(yīng)視覺(jué)朦朧鏈路狀態(tài)的路由算法(Adaptive Fuzzy Sighted Link

State，AFSLS)。

2.1 鄰居感應(yīng)和MPR機(jī)制

AFSLS采用MPR機(jī)制，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)選取其一跳鄰居節(jié)點(diǎn)的一個(gè)子集用于轉(zhuǎn)發(fā)該節(jié)點(diǎn)發(fā)送的控制分組。這些被選擇的節(jié)點(diǎn)稱(chēng)為該節(jié)點(diǎn)的MPR，而該節(jié)點(diǎn)就稱(chēng)為這些MPR的多點(diǎn)中繼選擇者(MPR Selector)。

2.2 自適應(yīng)朦朧

AFSLS使用了拓?fù)淇刂菩畔⒎职l(fā)模式，即自適應(yīng)朦朧發(fā)布模式。AFSLS根據(jù)不同的網(wǎng)絡(luò)狀態(tài)變化模式采用不同的拓?fù)湫畔⒎职l(fā)策略。

網(wǎng)絡(luò)中的節(jié)點(diǎn)根據(jù)其狀態(tài)變化的快慢，處于不同的工作模式。

節(jié)點(diǎn)剛剛啟動(dòng)或重啟后，節(jié)點(diǎn)處于UNINIT(未初始化)模式，等一小段時(shí)間(幾個(gè)HELLO周期)收集節(jié)點(diǎn)周?chē)泥従庸?jié)點(diǎn)信息。

初始化時(shí)，節(jié)點(diǎn)發(fā)送第一個(gè)全局LSU分組并重置所有計(jì)數(shù)器和定時(shí)器。這可以使網(wǎng)絡(luò)快速收斂，且可以得到全網(wǎng)的精準(zhǔn)拓?fù)浣Y(jié)構(gòu)圖，用于計(jì)算最優(yōu)的路徑。初始化后節(jié)點(diǎn)進(jìn)入U(xiǎn)NDEC(未確定)模式，然后節(jié)點(diǎn)根據(jù)鏈路狀態(tài)的變化速率來(lái)確定其是進(jìn)入SLS模式還是HSLS模式。

不管處于哪種模式，當(dāng)一個(gè)TTL=∞的拓?fù)淇刂菩畔⒎职l(fā)后，節(jié)點(diǎn)重置所有計(jì)數(shù)器和定時(shí)器，并重新返回UNDEC模式。當(dāng)節(jié)點(diǎn)再次重啟，節(jié)點(diǎn)進(jìn)入U(xiǎn)NINIT模式。

2.3 路由表的計(jì)算

每個(gè)節(jié)點(diǎn)都有一張路由表。路由表項(xiàng)由目的地址、下一跳地址和到目的地的距離組成。當(dāng)拓?fù)湫畔⒈?、鄰居信息表或MPR發(fā)生變化，都會(huì)重新計(jì)算路由。計(jì)算路由時(shí)首先會(huì)刪掉舊的路由表，然后重新根據(jù)節(jié)點(diǎn)拓?fù)湫畔⑹褂肈ijkstra算法構(gòu)建新的路由表。

3 AFSLS路由算法的NS仿真與分析

3.1 仿真場(chǎng)景

為了對(duì)AFSLS路由算法性能進(jìn)行仿真分析，使用NS 2.31版本網(wǎng)絡(luò)模擬平臺(tái)，構(gòu)建無(wú)線(xiàn)移動(dòng)Mesh網(wǎng)仿真平臺(tái)。節(jié)點(diǎn)PHY層和MAC層采用實(shí)驗(yàn)室開(kāi)發(fā)的基于IEEE 802.16d Mesh的寬帶移動(dòng)Mesh協(xié)議，具體參數(shù)設(shè)定如下:OFDM子載波數(shù)目:256;控制時(shí)隙周期:4;每幀控制時(shí)隙數(shù)目:8;調(diào)制方式:QAM64_3/4;仿真總時(shí)間:200 s。仿真場(chǎng)景如下:在1250*1250的空間內(nèi)，16個(gè)通信距離為250的固定節(jié)點(diǎn)組成了4*4的矩形，形成了一張能覆蓋整個(gè)空間的通信網(wǎng)絡(luò)。而34個(gè)隨機(jī)移動(dòng)的節(jié)點(diǎn)(實(shí)心小圓)在這空間內(nèi)隨機(jī)移動(dòng)，如圖1所示。

圖1 仿真網(wǎng)絡(luò)拓?fù)鋱D

場(chǎng)景中，節(jié)點(diǎn)移動(dòng)到目的地后，停頓10 s再重新移動(dòng);節(jié)點(diǎn)之間是CBR的隨機(jī)數(shù)據(jù)流，通過(guò)UDP發(fā)送;CBR數(shù)據(jù)流的數(shù)目是500;節(jié)點(diǎn)最大的移動(dòng)速度分別是 2/s，4/s，6/s，8/s，10/s，12/s，14/s，16/s，18/s，20/s;仿真的路由協(xié)議分別是 AFSLS、SLS_AODV(支持單向鏈路的AODV算法)、OLSR。

3.2 仿真結(jié)果與性能分析

本場(chǎng)景的仿真目的主要是分析節(jié)點(diǎn)的移動(dòng)速度對(duì)路由算法性能的影響。

整網(wǎng)CBR數(shù)據(jù)流的吞吐量(縱坐標(biāo))與節(jié)點(diǎn)移動(dòng)速度(橫坐標(biāo))的關(guān)系如圖2所示。由圖2中可見(jiàn)，隨著節(jié)點(diǎn)移動(dòng)速度的增加，AFSLS、SLS_AODV、OLSR的數(shù)據(jù)流吞吐量均呈現(xiàn)下降的趨勢(shì)。AFSLS路由算法是一個(gè)自適應(yīng)的算法，能動(dòng)態(tài)監(jiān)測(cè)網(wǎng)絡(luò)拓?fù)渥兓目炻瑥亩{(diào)整路由信息發(fā)送的周期，因此對(duì)隨機(jī)拓?fù)溆懈玫倪m應(yīng)性，比OLSR算法有更好的性能;另一方面，AFSLS是先應(yīng)式路由算法，每個(gè)節(jié)點(diǎn)均動(dòng)態(tài)維護(hù)一張整網(wǎng)路由表，當(dāng)CBR數(shù)據(jù)流需要發(fā)送的時(shí)候，不需要重新找尋路徑，可以直接發(fā)送，因此比反應(yīng)式路由SLS_AODV有更好的性能。

整網(wǎng)CBR數(shù)據(jù)流的丟包率(縱坐標(biāo))與節(jié)點(diǎn)移動(dòng)速度(橫坐標(biāo))的關(guān)系如圖3所示。由圖3中可見(jiàn)，隨著節(jié)點(diǎn)移動(dòng)速度的增加，網(wǎng)絡(luò)的丟包率隨之增加，而AFSLS路由算法的丟包率比SLS_AODV和OLSR路由算法均低。這證明了AFSLS路由算法能動(dòng)態(tài)監(jiān)測(cè)網(wǎng)絡(luò)拓?fù)渥兓目炻?，從而調(diào)整路由信息發(fā)送的周期，因此對(duì)隨機(jī)拓?fù)溆懈玫倪m應(yīng)性。AFSLS算法能夠更有效地使節(jié)點(diǎn)動(dòng)態(tài)地維護(hù)整網(wǎng)的拓?fù)?，路由的?dòng)態(tài)收斂時(shí)間比SLS_AODV和OLSR要好。

圖2 數(shù)據(jù)流的吞吐量

圖3 數(shù)據(jù)流的丟包率

整網(wǎng)CBR數(shù)據(jù)包的平均時(shí)延(縱坐標(biāo))與節(jié)點(diǎn)移動(dòng)速度(橫坐標(biāo))的關(guān)系如圖4所示。由圖4可見(jiàn)，AFSLS路由算法的數(shù)據(jù)包的時(shí)延比SLS_AODV好，但比OLSR算法的時(shí)延大。這是因?yàn)槊總€(gè)數(shù)據(jù)流發(fā)包的速度均是1個(gè)/s，而單位時(shí)間內(nèi)發(fā)送的數(shù)據(jù)包很少。所以，延時(shí)大的包對(duì)整網(wǎng)數(shù)據(jù)平均時(shí)延影響很大。OLSR算法在CBR數(shù)據(jù)流數(shù)目大的時(shí)候，會(huì)有較大的丟包率，被丟棄的數(shù)據(jù)包不算在平均時(shí)延內(nèi)。因此，AFSLS路由算法的數(shù)據(jù)包時(shí)延會(huì)比OLSR的大。

路由算法交互信息所需的帶寬開(kāi)銷(xiāo)(縱坐標(biāo))與節(jié)點(diǎn)移動(dòng)速度(橫坐標(biāo))的關(guān)系如圖5所示。由圖5中可以看出，隨著節(jié)點(diǎn)移動(dòng)速度的增加，導(dǎo)致拓?fù)渥兓l率的增加，AFSLS、SLS_AODV路由算法由于具有觸發(fā)的機(jī)制，當(dāng)檢測(cè)到鏈路變化的時(shí)候會(huì)發(fā)送路由控制信息，因此其占用的帶寬均呈現(xiàn)上升的趨勢(shì)。而OLSR路由算法的控制信息是周期性的發(fā)送與鏈路變化無(wú)關(guān)，因此OLSR路由算法占用的帶寬變化不大。

由上述的仿真結(jié)果和分析可知，隨著節(jié)點(diǎn)移動(dòng)速度的增多，AFSLS在平均時(shí)延、網(wǎng)絡(luò)吞吐量以及丟包率均比OLSR和SLS_AODV擁有更好的性能。在路由占用帶寬方面也優(yōu)于OLSR。AFSLS適用于數(shù)據(jù)流數(shù)據(jù)多的核心網(wǎng)絡(luò)，在拓?fù)渥兓l率很大時(shí)，比SLS_AODV、OLSR具有更好的收斂性以及網(wǎng)絡(luò)性能。

圖4 數(shù)據(jù)流的平均時(shí)延

圖5 交互信息的帶寬開(kāi)銷(xiāo)

4 結(jié)束語(yǔ)

AFSLS以先應(yīng)式路由協(xié)議OLSR為基礎(chǔ)，整合有限分發(fā)路由信息機(jī)制與高效分發(fā)路由信息機(jī)制，并結(jié)合自適應(yīng)的檢測(cè)模塊，具有快速、準(zhǔn)確、高效和可擴(kuò)展性好等優(yōu)點(diǎn)，能夠滿(mǎn)足無(wú)線(xiàn)移動(dòng)Mesh網(wǎng)絡(luò)對(duì)路由協(xié)議的要求。AFSLS在網(wǎng)絡(luò)吞吐量、丟包率以及平均時(shí)延等常規(guī)QoS參數(shù)方面都有良好的性能，能夠擴(kuò)展支持soft QoS。 ■

［1］方旭明.下一代無(wú)線(xiàn)因特網(wǎng)技術(shù):無(wú)線(xiàn)Mesh網(wǎng)絡(luò)［M］.北京:人民郵電出版社，2006.

［2］HAASZ J.A New Routing Protocol for The Reconfigurable Wireless Networks［J］.IEEE ICUPC 1997，1997(10):562－566.

［3］SANTIVANEZC A.Making Link-State Routing Scale for Ad Hoc Networks［J］.Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking ＆ Computing，2001(10):76－85.

［4］DE R F，F(xiàn)OTINO M，MARANO S.EE-OLSR:Energy Efficient OLSR Routing Protocol for Mobile Ad Hoc Networks［J］.IEEE/Military Communications Conference，2008(11):1－7.

［5］PEIG，GERLA M，CHEN T W.Fisheye State Routing in Mobile Ad Hoc Networks［J］.Workshop on Wireless Networks and Mobile Computing，2000(8):71 －78.

［6］SANTIVANEZ C A，RAMANATHAN R.Hazy Sighted Link State(HSLS)Routing:A Scalable Link State Algorithm［J］.BBNTechnical Memorandum，2001(8):1301 － 1304.