一種基于ＯＬＳＲ的新型層次路由算法

摘要：提出了一種新型的基于OLSR的層次化改進算法HOLSR，旨在提高OLSR的整體效率。該算法通過分層設置洪泛范圍和靈活調整各層拓撲控制分組的更新周期，降低路由執行開銷；同時采用差值路由補償技術提高數據分組的傳輸效率。仿真實驗結果表明：HOLSR與OLSR路由算法相比，數據分組成功傳輸率高，端到端延遲小，路由協議開銷少；與DSR、AODV、DSDV等典型路由算法相比，在不同節點移動速度和不同通信負載下，綜合性能也有優勢，尤其在通信負載較大時（880 kbps），優勢更加明顯。

關鍵詞：普適計算； 移動Ad hoc網絡； OLSR協議； 層次路由

中圖分類號：TN915文獻標志碼：A

文章編號：1001－3695(2008)06－1693－05

0引言

基于無線通信技術的移動Ad hoc網絡是一種無中心、拓撲變化、多跳的網絡結構，它既可以用來控制也可以用于通信。由于它的每個節點都具有移動、計算、路由、感應、嵌入的能力，具有組網靈活、不依賴固定網格、生存性強等諸多優點，非常適合在沒有固定通信設施（包括基站、GPS等）的廣闊復雜環境中使用。移動Ad hoc網絡使隨時隨地、透明的計算成為可能，已成為普適計算應用的重要基礎架構[1]。然而，在具備諸多優勢的同時，移動Ad hoc網絡的節點移動頻繁、能源有限、物理獨立的固有特性也為其路由、節能、定位等帶來了新的問題。OLSR是一種典型的應用于移動Ad hoc網絡的路由協議，由于采用平坦的先應式路由技術，每個節點必須通過不斷地廣播拓撲控制（TC）分組和Hello分組來及時掌握整個網絡的拓撲信息，進而計算出去往全網的路由表。為了緩解由于每個節點的頻繁廣播、轉發路由控制分組帶來的洪泛效應，OLSR采用了MPR（multipoint relay，多點中繼）技術，即每個節點在自己的一跳鄰居節點之中選擇一部分節點作為MPR，只有被選為MPR的鄰居節點才負責轉發消息，從而有效地減少消息發送的開銷。盡管如此，與許多反應式路由協議相比，OLSR的路由協議開銷仍然較大，尤其是當網絡規模較大時，此類問題更加突出：一方面，網絡中傳輸的TC分組數量隨節點數量呈級數增長；另一方面，節點移動導致遠距離傳輸過來的TC分組所攜帶的消息大量失效。為了提高路由效果，國內外學者對后一方面問題提出了許多改進辦法，可以分為三類：a)通過提高Hello分組的發送頻率，增強TC分組所攜帶鄰居信息的準確性[2]；b)通過提高TC分組的發送頻率[3]或自適應地調節TC分組的發送頻率[4]，保證TC分組及時有效；c)減少MAC層IEEE 802．11協議中最大重試次數，降低傳輸的延遲，從而增加TC分組的時效性[5]。前兩類方法在一定程度上提高了路由效果，但都不可避免地增加了路由開銷；第三類方法則是對MAC層協議的改進，與路由協議關系不大。

本文針對大規模網絡中TC分組數量大、遠距離TC分組失效明顯這兩個方面的問題，借鑒FSR中的fisheye技術[6]，提出了基于OLSR的分層路由算法，即HOLSR（hierarchical OLSR）。

1基于OLSR的層次路由算法——HOLSR

HOLSR算法是對OLSR協議的一種層次化改進，旨在合理利用協議開銷，獲得可用性更強的拓撲、路由信息；在同等路由精度下，減少TC分組的傳輸總量，降低OLSR的路由協議開銷，提高OLSR協議整體效率。

1．1OLSR路由協議

OLSR是由INRIA（法國國家信息與自動化研究所）開發提出，并被IETF MANET工作組確定為RFC標準的一種先應式無線移動Ad hoc 網絡路由協議[7]。OLSR協議是在傳統的鏈路狀態路由協議的基礎上改進而成，它需要通過周期性地廣播來交換各種控制信息，并采取分布式計算來更新、建立自己的網絡拓撲圖和路由表。在OLSR路由協議中，MPR是最重要的一個機制，其對傳統鏈路狀態路由協議的改進主要體現在兩個方面：a)每個節點在自己的一跳鄰居節點之中選擇一部分節點作為多點MPR，只有被選為 MPR 的鄰居節點才負責轉發消息，從而有效地減少控制消息的洪泛數量；b)OLSR中只有MPR才產生鏈路狀態信息，即MPR只報告其與把它選為MPR的節點(稱為 MPR selector)之間的鏈路信息。因此，與傳統的鏈路狀態算法相比，OLSR算法大大壓縮了單個路由控制分組的長度，進一步減少了消息發送的開銷。由于MPR機制在鄰居節點較多時優勢明顯，OLSR路由協議更適用于大型的、節點密集的Ad hoc網絡。

OLSR 主要采用兩種控制分組：Hello分組和 TC分組。Hello分組在一跳的范圍內周期性地廣播，不能被轉發，用于建立一個節點的本地鏈路表、鄰居表、兩跳鄰居表、MPR selector表等；與之相反，TC 分組必須被廣播到全網，TC 分組中包含了發送該TC 分組的節點的MPR selector信息，節點根據收到的 TC 分組來計算網絡的拓撲圖，進而獨立地計算通向全網的路由表。

1．2HOLSR的核心思想

HOLSR的核心思想是在OLSR算法的基礎上，進一步優化TC分組的傳輸開銷。離節點較近的范圍采用較高頻率發送TC分組；離節點較遠的范圍采用較低頻率發送TC分組，再結合使用差值路由補償技術，從而達到提高近距離路由的準確性，減少TC分組對遠距離通信資源消耗的效果。依據該思想對每個節點都設置兩個以上的拓撲更新層次，由近至遠更新頻率依次降低，分層更新示意圖如圖1所示。當網絡趨于穩定時，節點對近距離的網絡拓撲和路由信息掌握較準確，而對遠距離的網絡拓撲和路由信息掌握較粗糙。這一方面與實際通信鏈路的統計信息相吻合，即在大規模移動Ad hoc網絡中，大部分通信鏈路是在無線通信半徑內的節點之間建立的[8]，實現用較小的網絡路由開銷確保大部分通信的精度；另一方面，較粗糙的遠距離拓撲、路由信息不會對遠距離節點間的通信產生明顯影響，因為當一個數據分組接近其目標時，它將逐步進入到一個更高更新頻率的范圍中，同時逐漸獲得通向目標節點的精確的路由指導。

由圖1可知，以節點0為例，在其2跳以內、3跳、3跳以外的節點分別構成了第1、2、3層更新范圍。第1層更新范圍內，每T秒發送一次TC分組；第2層更新范圍內，每aT秒發送一次TC分組，a＞1；第3層更新范圍內，每bT秒發送一次TC分組，b＞a，則每層的更新頻率f可以表示成跳數hop的函數，如式（1）所示：

1．3差值路由補償技術

差值路由補償是指先對新、舊路由表作比較求差，然后對舊路由表進行補償更新。具體辦法是根據新計算出來的路由表調整舊路由表，這包括添加舊路由表中沒有的路由條目、修改舊路由表中已有的路由條目以及保持舊路由表中有而新路由表中沒有的條目等操作。傳統OLSR中，每次計算出新的路由表之前，必須完全刪除舊路由表。然而，筆者采用了分層更新路由之后，節點對遠距離的網絡拓撲和路由信息掌握較粗糙，計算出的新路由表往往不能覆蓋整個網絡。對于那些沒有被新路由表覆蓋，卻存在于舊路由表中的邊緣節點而言，舊路由表中的有關條目仍具有相當的路由指導價值；尤其是當網絡拓撲變化較小、邊緣節點的相對位置變化不大時，其作用更加明顯。因此，通過差值路由補償技術，充分保留舊路由表中有價值的路由信息是很有必要的。

處理完RT′i(j)的所有條目后，結束。至此，RTi補償更新完畢，可以用來指導分組發送與轉發。

2HOLSR的實現與仿真

在Linux平臺上，使用C++語言對HOLSR算法進行編程實現。為了便于與OLSR路由算法的性能比較，本文采取了在OLSR基礎上進行改進的方法：a)在OLSR協議的調度過程中增加了分層調度控制模塊，完成對TC分組的轉發控制；b)在路由處理的路由更新功能上添加了差值路由補償模塊，其他部分保持不變。

2．1算法方框圖

HOLSR算法方框圖如圖2所示。圖中，Ad hoc路由協議位于網絡層。其中，灰色模塊和箭頭，即“分層調度控制”和“計算路由表+差值路由補償”是本文對OLSR的修改部分，其余為OLSR的原有內容。

2．2仿真場景及參數

仿真采用NS－2網絡模擬器[9]，通過擴展NS－2中的代理建立了移動Ad hoc網絡路由算法性能仿真框架。HOLSR算法采用插件形式，分層參數如表1所示，MAC層采用普遍使用的802．11協議[10]。利用NS－2中自帶的場景生成工具setdest生成運動場景，運動場景中節點移動模型為廣泛使用的隨機路點模型（random way point model，RWPM），場景參數如表2所示。本文仿真的流量場景選用的業務流量類型為CBR。CBR流量是常速比特流，是一種用于語音傳輸的實時通信協議，它以固定的速率發送數據可以方便地比較多種協議在不同拓撲、運動場景下的性能。使用NS－2中自帶的流量生成工具cbrgen．tcl創建CBR流量場景，流量參數如表3所示。為了比較節點移動速度和網絡通信負載對協議的影響，本文設計了兩組實驗：實驗1中，分組發送速率為1 packets/s，節點最大運動速度為1、5、10、15、20 m/s五種情況；實驗2中，節點最大運動速度為5 m/s，分組發送速率為1、5、10 packets/s三種情況。

2．3路由算法性能指標及計算方法

為了觀察本文協議的性能改進情況，筆者使用了五種性能指標進行度量，如表4所示。

端到端延遲ED反映協議的效率高低。ED越小，網絡越通暢，則協議的效率越高。ED可使用式（2）計算得到。其中，rt表示CBR分組到達目的節點的時間；st表示CBR分組被發送的時間；N為分組個數。從理論上講，要計算網絡的延遲，需考慮所有成功發送、接收的分組，但實際上，網絡通信隨機性很強并且動態變化，準確統計網絡中所有分組比較困難且無必要。因此在仿真中，隨機產生了44條CBR通信鏈路以模擬現實通信的復雜情況，并固定選取了一條鏈路統計其ED，以該條鏈路的ED值衡量不同協議的性能。

路由開銷率RO可以用來比較不同協議的可擴展性、適應網絡擁塞能力和協議的效率[11]。RO可使用如下公式計算得到：

RO=（所有Hello分組比特數+所有TC分組比特數）/

仿真時間（3）

平均跳數也可以反映協議的效率高低[12]。跳數越多，則分組在網絡中傳輸時對帶寬資源的消耗越大，協議的效率越低。計算平均跳數時，本文對其進行了簡化，在隨機產生了44條CBR通信鏈路中固定選取一條鏈路，統計其平均跳數。

3實驗結果及分析

采用2．2節中建立的運動場景和流量場景，對HOLSR路由算法和傳統的OLSR、AODV[13]、DSR[14]、DSDV[15]路由算法的執行進行仿真，采用2．3節中的性能指標進行度量。實驗1的結果如表5及圖3~6所示。其中，表5反映HOLSR較OLSR在不同節點移動速度下的性能改進情況，圖3~6分別給出HOLSR、OLSR、AODV、DSR和DSDV五種路由算法在不同節點移動速度下關于數據分組成功傳輸率、路由開銷、端到端延遲和數據分組平均跳數四種性能度量指標的對比情況。實驗2的結果如表6及圖7~10所示。其中，表6反映HOLSR較OLSR在不同通信負載下的性能改進情況，圖7~10分別給出HOLSR、OLSR、AODV、DSR和DSDV五種路由算法在不同通信負載下關于數據分組成功傳輸率、路由開銷、端到端延遲和數據分組平均跳數四種性能度量指標的對比情況。

由表5和6可知，在相同的條件下，本文提出的HOLSR路由算法較OLSR在性能上有明顯改進。在不同節點移動速度下，HOLSR數據分組成功傳輸率的均值為96．93%，比OLSR提高了4．78%，端到端平均延遲的均值為0．052 s，比OLSR下降了8．99%，路由開銷率的均值為55．76 kbps，比OLSR下降了7．04%；在不同通信負載下，HOLSR數據分組成功傳輸率平均比OLSR提高5．86%，端到端平均延遲平均下降53．09%，路由開銷率平均下降9．95%。在平均跳數上，兩種算法沒有明顯差異。該結果一方面表明HOLSR路由算法對節點移動具有較強的適應性；另一方面表明，HOLSR采用的層次化路由方法減少了網絡的TC分組發送量，從而有效地降低了路由開銷；同時，由于分組發射次數減少了，物理層發射沖突幾率降低了，因此，通信效率也得到了提高，數據分組成功傳輸率和端到端平均延遲等性能都得到了改善。

由圖3~6可知，HOLSR路由算法較AODV、DSR、DSDV等傳統路由算法也有顯著優勢：在數據分組成功傳輸率、端到端延遲和平均跳數上，HOLSR路由算法性能最好；在網絡路由開銷上，HOLSR協議始終保持較低且平穩的水平，相反，DSR和AODV兩個反應式路由算法波動較大。由圖7~10可知，在不同通信負載下，HOLSR路由算法在數據分組成功傳輸率、端到端延遲、路由開銷率和平均跳數四個方面也都保持了最優和近似最優的表現。尤其是在路由開銷率上始終保持在較低水平，且隨通信負載增長緩慢，如圖8所示?？梢?，HOLSR具有較好的網絡可擴展性，與其他協議相比，更適合在大型網路中使用。此外，由圖7可知，當通信負載達到880 kbps時，HOLSR仍然保持了87．32%的較高數據分組成功傳輸率，比AODV、DSR和DSDV大約高出一倍；同時，HOLSR的路由開銷分別約是AODV的1/2和DSR的1/4，HOLSR的端到端延遲約是DSR、DSDV的1/6。可見，HOLSR路由算法在通信負載較大時有著較其他協議更加突出的表現。由圖9可知，當通信負載達到1 760 kbps時，所有協議的端到端平均延遲都超過了2 s，DSDV和DSR甚至達到12 s，其原因是當通信負載較大時，由于大型網絡的拓撲比較密集，物理層發射沖突幾率驟增，導致MAC層802．11協議的重試次數增多。要從根本上解決這一問題須對MAC層及其下層的協議進行優化[5]。盡管如此，本文提出的HOLSR仍然具有最小的端到端延遲，其原因是層次路由機制有效地減少了TC分組的轉發數量，在一定程度上緩解了物理層發射沖突的產生。圖10給出了平均跳數隨通信負載變化的情況，HOLSR和OLSR的跳數在所有協議中是最少的，始終在4跳左右，反映出兩協議在不同通信負載下都能保持較高的效能。

4結束語

本文提出的HOLSR路由算法適用于規模較大（如100個節點）、拓撲變化較小、通信負載大的移動Ad hoc網絡環境，如戰術互聯網[17]、智能戰場[18]等。實驗結果表明，與OLSR協議相比，在不同節點移動速度下，HOLSR數據分組成功傳輸率的均值為96．93%，提高了4．78%；端到端平均延遲的均值為0．052 s，下降了8．99%；路由開銷率的均值為55．76 kbps，下降了7．04%。在不同通信負載下，HOLSR數據分組成功傳輸率平均比OLSR提高5．86%，端到端平均延遲平均下降53．09%，路由開銷率平均下降9．95%。與AODV、DSR、DSDV等路由算法相比，HOLSR在綜合性能上也有明顯的優勢。

由于本文的層次路由的分層設計是固定的，具有一定局限性。下一步將研究自適應分層機制，根據網絡狀況靈活設置分層數及其范圍，從而使HOLSR協議適用于更廣泛的移動Ad hoc網絡應用中。

參考文獻：

［1］TOH C K，MASE K，YOSHIDA S．Special section on advances in Ad hoc mobile communications and networking[J].IEICE Trans Communications，2005，E88－B(9):3499．

[2]BENZAID M，MINET P， AGHA K A．Integrating fast mobility in the OLSR routing protocol[C]//Proc of the 4th Interational Workshop on Mobile and Wireless Communications Network.2002:217－221.

[3]孟芳兵． 基于移動Ad hoc網絡的OLSR路由改進協議[J]．武漢理工大學學報，2005， 27(5):116－119．

[4]任智． 基于拓撲維護的自適應多信道OLSR路由協議[J]． 系統工程與電子技術，2006，28(7):977－980．

[5]LAOUTI A，PAUL M，ABDELLAH N，et al．Simulation results of the OLSR routing protocol for wireless network，RR－4414[R]. INRIA， 2002．

[6]PEI Guang－yu， GERLA M， CHEN T． Fisheye state routing: a routing scheme for Ad hoc wireless networks[C]//Proc of ICDCS Workshop on Wireless Networks Mobile Comput.Taipei:[s.n.]，2000:70－74．

[7]CLAUSEN T， JACQUET P．RFC 3626， Optimized link state routing protocol[S]．[S.l.]:IETF MANET Working Group，2003.

[8]PAUL S．Communications networks for the force XXI digitized battlefield[J]．Mobile Networks and Applications，1999，4(3):139－155．

[9]Monarch Project. Wireless and mobility extensions to the NS－2[EB/OL].(2000－11－05)[2007－05－20].http://monarch．cs．cmu．edu/cmu－ns．html.

[10]GAST S M. 802．11 wireless networks: the definitive guide[M]. 2nd ed．[S．l．]:O’Reilly Media Inc，2005．

[11]周懿．Ad hoc 網中多信道 OLSR 路由協議研究[D]．成都：電子科技大學，2004．

[12]董超． 一種Ad hoc網絡組移動模型[J]． 系統仿真學報，2006，18(7):1879－1883．

[13]CHARLES E P， ELIZABETH M B R， SAMIR R D．RFC 3561 Ad hoc on－demand distance vector (AODV) routing protocol[S]．[S.l.]:IETF MANET Working Group， 2003．

[14]DAVID B J， DAVID A M， HU Y C．The dynamic source routing protocol for mobile Ad hoc networks(DSR)[S]．[S.l.]:IETF MANET Working Group， 2004．

[15]PERKINS C， BHAGWAT P．Highly dynamic destination－sequenced distance－vector routing (DSDV) for mobile computers[J].ACM SIGCOMM Computer Communication Revien，1994，24(4):234－244．

[16]張勖，程勝． 移動Ad hoc網絡路由協議性能仿真研究[J]． 計算機工程， 2005，31(5):61－62．

[17]萬永樂， 張劍． 戰術互聯網建模與仿真[J]．通信技術，2002，10(10):49－53．

[18]明亮，謝桂海． 基于移動自組網的智能戰場架構理論研究[J]． 軍械工程學院學報，2006，18(5):66－69．

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文