一種適用于無線移動Mesh網的路由算法

張永忠，陸宏治

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

0 引言

近年來，無線網絡接入業務發展迅猛。無線移動 Mesh網絡(Wireless Mobile Mesh Networks，WMMN)是在無線 Ad Hoc網絡(Wireless Ad Hoc Network，MANET)和無線 Mesh網絡(Wireless Mesh Network，WMNET)的基礎上發展起來的一種新型網絡形態，融合了已有的MANET及WMNET網絡的特點。由于無線移動Mesh網絡具有大規模、異構性和自組織等技術特點，路由問題是最為復雜的問題之一，也是關鍵技術之一［1］。

目前國內外關于移動網絡的路由協議的分類方法，大多根據路徑是按事前的路徑信息建立還是在發送數據前臨時建立，將路由協議分為2種類型:先應式路由協議和反應式路由協議;另外，混合式路由協議［2］則結合了先應式路由協議和反應式路由協議的特點。

1 AFSLS路由算法設計思路

根據無線移動Mesh網絡節點對能量敏感較低、移動性較低的特點，基于鏈路狀態的先應式路由協議相對于反應式路由協議更適合WMMN，尤其是應用在WMMN的骨干網部分。此外，標準鏈路狀態(Standard Link State，SLS)路由具有簡單性、魯棒性和可預見的動態性等優點，對基于服務質量路由也有很好的支持［3］。在先應式路由協議中，OLSR協議是對標準鏈路狀態路由協議優化而形成的，具有路徑選擇等待時延小、路由信息開銷小等優點。

① 采用多點中繼(Multipoint Relay，MPR)機制［4］，減少同一區域內部相同控制分組的重復轉發次數來減少網絡中控制分組的數量;

②利用高效分發方法和受限分發方法提高鏈路狀態路由協議的可擴展性，并提出一種提高路由協議擴展性的所謂朦朧算法［5］;

③朦朧算法是根據如下事實提出來的:2個節點離得越遠，它們感覺彼此之間的相對移動性就會越小。所以為了感知移動節點，對近處的更新信息發送要比較迅速頻繁，而遠處的更新信息可以比較緩慢。朦朧算法的魯棒性強于分層或分區技術，也可以節省路由信息的開銷。HSLS路由協議在朦朧算法這一類路由協議中的性能是最優的［3－6］。

2 AFSLS路由算法

在OLSR協議基礎上，將有限分布路由信息機制與高效分發的路由信息機制進行結合，并整合網絡拓撲狀態變化自適應的檢測模塊和朦朧視覺算法，提出了一種綜合以上方法優點的自適應視覺朦朧鏈路狀態的路由算法(Adaptive Fuzzy Sighted Link

State，AFSLS)。

2.1 鄰居感應和MPR機制

AFSLS采用MPR機制，網絡中的每一個節點選取其一跳鄰居節點的一個子集用于轉發該節點發送的控制分組。這些被選擇的節點稱為該節點的MPR，而該節點就稱為這些MPR的多點中繼選擇者(MPR Selector)。

2.2 自適應朦朧

AFSLS使用了拓撲控制信息分發模式，即自適應朦朧發布模式。AFSLS根據不同的網絡狀態變化模式采用不同的拓撲信息分發策略。

網絡中的節點根據其狀態變化的快慢，處于不同的工作模式。

節點剛剛啟動或重啟后，節點處于UNINIT(未初始化)模式，等一小段時間(幾個HELLO周期)收集節點周圍的鄰居節點信息。

初始化時，節點發送第一個全局LSU分組并重置所有計數器和定時器。這可以使網絡快速收斂，且可以得到全網的精準拓撲結構圖，用于計算最優的路徑。初始化后節點進入UNDEC(未確定)模式，然后節點根據鏈路狀態的變化速率來確定其是進入SLS模式還是HSLS模式。

不管處于哪種模式，當一個TTL=∞的拓撲控制信息分發后，節點重置所有計數器和定時器，并重新返回UNDEC模式。當節點再次重啟，節點進入UNINIT模式。

2.3 路由表的計算

每個節點都有一張路由表。路由表項由目的地址、下一跳地址和到目的地的距離組成。當拓撲信息表、鄰居信息表或MPR發生變化，都會重新計算路由。計算路由時首先會刪掉舊的路由表，然后重新根據節點拓撲信息使用Dijkstra算法構建新的路由表。

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

3.1 仿真場景

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

圖1 仿真網絡拓撲圖

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

3.2 仿真結果與性能分析

本場景的仿真目的主要是分析節點的移動速度對路由算法性能的影響。

整網CBR數據流的吞吐量(縱坐標)與節點移動速度(橫坐標)的關系如圖2所示。由圖2中可見，隨著節點移動速度的增加，AFSLS、SLS_AODV、OLSR的數據流吞吐量均呈現下降的趨勢。AFSLS路由算法是一個自適應的算法，能動態監測網絡拓撲變化的快慢，從而調整路由信息發送的周期，因此對隨機拓撲有更好的適應性，比OLSR算法有更好的性能;另一方面，AFSLS是先應式路由算法，每個節點均動態維護一張整網路由表，當CBR數據流需要發送的時候，不需要重新找尋路徑，可以直接發送，因此比反應式路由SLS_AODV有更好的性能。

整網CBR數據流的丟包率(縱坐標)與節點移動速度(橫坐標)的關系如圖3所示。由圖3中可見，隨著節點移動速度的增加，網絡的丟包率隨之增加，而AFSLS路由算法的丟包率比SLS_AODV和OLSR路由算法均低。這證明了AFSLS路由算法能動態監測網絡拓撲變化的快慢，從而調整路由信息發送的周期，因此對隨機拓撲有更好的適應性。AFSLS算法能夠更有效地使節點動態地維護整網的拓撲，路由的動態收斂時間比SLS_AODV和OLSR要好。

圖2 數據流的吞吐量

圖3 數據流的丟包率

整網CBR數據包的平均時延(縱坐標)與節點移動速度(橫坐標)的關系如圖4所示。由圖4可見，AFSLS路由算法的數據包的時延比SLS_AODV好，但比OLSR算法的時延大。這是因為每個數據流發包的速度均是1個/s，而單位時間內發送的數據包很少。所以，延時大的包對整網數據平均時延影響很大。OLSR算法在CBR數據流數目大的時候，會有較大的丟包率，被丟棄的數據包不算在平均時延內。因此，AFSLS路由算法的數據包時延會比OLSR的大。

路由算法交互信息所需的帶寬開銷(縱坐標)與節點移動速度(橫坐標)的關系如圖5所示。由圖5中可以看出，隨著節點移動速度的增加，導致拓撲變化頻率的增加，AFSLS、SLS_AODV路由算法由于具有觸發的機制，當檢測到鏈路變化的時候會發送路由控制信息，因此其占用的帶寬均呈現上升的趨勢。而OLSR路由算法的控制信息是周期性的發送與鏈路變化無關，因此OLSR路由算法占用的帶寬變化不大。

由上述的仿真結果和分析可知，隨著節點移動速度的增多，AFSLS在平均時延、網絡吞吐量以及丟包率均比OLSR和SLS_AODV擁有更好的性能。在路由占用帶寬方面也優于OLSR。AFSLS適用于數據流數據多的核心網絡，在拓撲變化頻率很大時，比SLS_AODV、OLSR具有更好的收斂性以及網絡性能。

圖4 數據流的平均時延

圖5 交互信息的帶寬開銷

4 結束語

AFSLS以先應式路由協議OLSR為基礎，整合有限分發路由信息機制與高效分發路由信息機制，并結合自適應的檢測模塊，具有快速、準確、高效和可擴展性好等優點，能夠滿足無線移動Mesh網絡對路由協議的要求。AFSLS在網絡吞吐量、丟包率以及平均時延等常規QoS參數方面都有良好的性能，能夠擴展支持soft QoS。 ■

［1］方旭明.下一代無線因特網技術:無線Mesh網絡［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，FOTINO 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.