一種無線自組織網絡動態路由協議

姜永廣，田永春

（中國電子科技集團公司第三十研究所， 四川 成都 610041）

0 引言

無線自組織移動網（Mobile Ad-hoc Network，MANET）是一種新型的無中心、分布控制的無線移動通信網絡，不需要建設網絡基礎設施，具有快速開設能力，早期主要應用于軍事通信。與其他移動通信系統相比，MANET無固定的基站，具有高效的自組性，支持動態變換的網絡拓撲結構和多跳轉發技術，采用分布式控制，系統魯棒性和抗毀性較高，已廣泛運用于軍事戰術環境、事故突發現場、搶險救災等緊急環境。

然而在無線通信環境中，特別是戰場和搶險救災等環境，無線信道變化快速，節點移動、加入、退出，地形、地物等都會引起網絡拓撲結構的動態變化。路由協議的作用就是在這種環境中，監控跟蹤網絡拓撲結構的變化，及時交換網絡連通性變化信息，產生、維護和選擇最優路由，并根據選擇的路由轉發數據，從而提供上層業務的連續性。目前，已存在數十種MANET路由協議[1-2]，可以劃分為：

①主動路由（Proactive Routing Protocol）：一類表驅動協議，網絡中所有節點都周期性的維護網絡拓撲，比較典型的有：按序距離矢量協議（DSDV）、優化鏈路狀態協議（OLSR）、魚眼狀態協議（FSR）、模糊視野鏈路狀態協議（FSLS）等；

②被動路由（Reactive Routing Protocol）：主要是針對主動路由協議開銷大，不能適應拓撲快速響應的缺陷而發展的，其基本思想是各節點不再按周期維護網絡拓撲，而是在有業務需求時通過協議去發現最短路徑，比較典型的有：動態源路由協議（DSR）、按需距離矢量協議（AODV）等；

③混合路由（Hybrid Routing Protocol）：為了改善主動路由開銷大、被動路由實時性差而發展的一類協議，比較典型的有：分區路由協議（ZRP）、界標特殊路由協議（LANMAR）等；

④地理輔助路由[3]（Geographic Position Aided Rou-ting）：把節點的網絡拓撲位置與地理位置結合起來。在 GP S位置信息的支持下，按照方向進行數據分組的轉發，可極大地節省路由開銷，比較典型的有位置輔助路由協議（LAR）。

這些協議各有優缺點，但應用到窄帶電臺環境，還需要在分布式控制、環路避免、減小開銷、路由快速建立等多方面進行優化設計。本文介紹一種基于稀疏樹的自組織路由協議（STRP）。

1 基于稀疏樹的自組織路由協議（STRP）

STRP是一個在所有節點中維護全網路由信息的表驅動路由協議，綜合了距離矢量和鏈路狀態路由協議的優點，由鄰居維護（Hello協議）、拓撲更新協議、路徑尋找算法三個主要部分組成，每個節點維鄰居距離表與路由表。

鄰居維護：采用Hello協議周期性地檢測與鄰居間的連通狀態。每個hello分組中攜帶了節點的鄰居列表。接收節點通過hello報文建立節點的鄰居關系，通過hello報文中攜帶的鄰居列表進行信道狀態的判斷。

拓撲更新：節點利用收到的Hello消息建立一跳的路由關系，生成最基本的路由表。這個新的路由表會通過拓撲更新協議被傳遞出去，每個鄰居節點收到該更新后，檢查是否存在環路并修改更新消息里的代價后把它存入鄰居距離表對應該鄰居的表項中，此后通過該鄰居距離表節點生成自己的路由表，而路由表的生成是通過計算鄰居距離表中到目的節點的最短路徑稀疏樹（SST，Shortest path Spanning Tree)來實現的，到某個目的節點的路由也是到該目的節點的稀疏樹。在發生路由改變時，該節點將把稀疏樹發生了改變的部分傳遞出去，它的鄰居存儲該消息到鄰居距離表中，同時根據接收到的ST重新計算自己的ST或路由表。

改進的路徑尋找算法：路徑算法采用改進的路徑發現算法（APFA），一方面計算路徑，一方面消除環路。網絡各節點依據自己建立的SST執行Dijkstra算法分散計算各自的路由表，實質上，STRP實現的Dijkstra最短路徑算法是在一個分級圖上分布實現的，分級圖代表網絡的連接性。

根據 STRP協議的思想，協議的大部分流程都和常規的路由協議類似，這里不再贅述。這里僅介紹在 STRP里采用的避免計數到無窮與環路消除算法。

2 改進的路徑查找算法

由于STRP依據自己的SST執行Dijkstra算法分散計算各自的路由表，其實質是STRP實現的Dijkstra最短路徑算法是在一個分級圖上分布實現的，分級圖代表了網絡的連接性。該算法是路徑發現算法（Path-finding Algorithm，PFA）的一個改進版本（APFA）。

在STRP中，每個節點路由表都包含了目的地址、距離、下一跳和去目的節點的倒數第二跳信息，APFA正是利用距離和路由上的“倒數第二跳節點”信息，使每個節點利用本地信息就可以推導出隱含路由，而路由存儲信息和路由更新信

息都不需要增加過多的開銷。網絡中節點路由表如表1所示。

表1 由倒數第二跳推導隱含路由

“倒數第二跳節點”定義為沿源節點到目的節點的整個最短路由上，去往目的節點的前一跳節點。如下所示：

下面說明 APFA利用倒數第二跳信息推導隱含路由和消除網絡拓撲快速變化帶來環路的過程。如圖1所示，網絡由a、b、c、d、e、f、g七個節點構成，節點a的路由表如表1由倒數第二跳推導隱含路由1所示。

舉例推導從節點a到節點c的路由，查尋節點c的表項，可以知道從a到c路由上的倒數第二跳是b；而在節點b的路由表中，從a到b的倒數第二跳是g；在節點g路由表中，倒數第二跳是a，從而可以推導從a到c的路由是a→g→b→c。

APFA可快速消除分布式Bellman-Ford算法中計數到無窮的問題，并及時發現穩定的環路，加速算法的收斂速度，但不能避免網絡快速變化而帶來的臨時環路的產生[4]。如圖1所示。

圖1 路徑發現算法中的臨時環路舉例

在網絡拓撲快速變化過程中，在網絡拓撲變化前，c到h的下一跳為d，由于網絡變化c到d的鏈路中斷（圖1中過程①），而更新到h的下一跳為e，在此路由更新消息還未交換到g之前，a與g之間鏈路失效（圖1中過程②），g會選擇b作為自己到h的下一跳，從而產生了c→e→g→b→c的臨時環路。

為了消除臨時環路，參考Cisco EIGRP協議采用APFA ，它利用鄰居間的同步機制消除臨時環路。

APFA引入了可行距離（Feasible Distance，FD）的概念。如下：

3 仿真分析

STRP協議是針對網絡拓撲變化快、傳輸帶寬窄的網絡而設計的，為了比較本文所提出的路由算法的性能，把它與無線 OSPF（WOSPF）作對比進行仿真。仿真場景設置如下：節點數32個，采用的電臺速率為288 kb/s，信道接入方式為TDMA，電臺單跳通信距離為 12 km，節點均勻分布在一個40×40 km2的范圍內，其中8個節點隨機移動。

圖2與圖3是協議收斂時間的對比，其中橫軸是仿真時間，縱軸是路由協議的收斂時間。圖2是節點靜止時協議收斂時間對比，圖3是節點移動時兩者收斂時間的對比。

圖2 節點靜止時收斂時間對比

由圖2可見在靜止時，STRP收斂時間遠比WOSPF要小，主要是稀疏樹算法對無線網絡拓撲進行了剪裁，網絡鏈路數少，而WOSPF要達到全網鏈路狀態數據庫的同步，需要的時間較長。由圖3可見節點移動時，STRP收斂更快速，主要原因是引入了可行距離的思想，并對移動性進行了吸收，將其變化限制在網絡的局部，而 WOSPF則是進行全網的變化與同步。

圖4與圖5是兩者在節點運動時協議開銷的對比，其中圖4是開銷的時間平均值，圖5是開銷的瞬時值。

由圖4,圖5可見，STRP的開銷明顯低于WOSPF，主要原因是STRP可以把節點在移動時對網絡拓撲的影響限制在其1跳周圍內，所引起的鏈路變化不會傳遞到全網，因此開銷較小。而WOSPF需要維持全網拓撲數據庫的一致，因此路由開銷較大。從仿真來看，STRP協議具有收斂快，開銷小、自動限制移動性影響等特性，能夠較好地適應窄帶無線通信環境的需要。

圖3 節點移動時收斂時間對比

圖4 節點運動時路由開銷瞬時值對比

圖5 節點運動時路由開銷平均值對比

4 結語

移動自組織網主要使用在軍事通信等沒有固定基礎設施的場合，這些場合的無線通信帶寬通常較窄，具有動態拓撲、波動的通信質量以及單向信道等特點，傳統的路由協議難以適應這種網絡環境的需要。目前出現了很多自組織路由協議，它們解決問題的思路各不相同。本文從簡單、實用的角度，提出了綜合DV和LS算法特點的STRP協議，采用稀疏樹算法來降低協議的開銷，采用快速路徑搜索算法來消除環路實現網絡的快速收斂，具有輕量、可靠、快速等優點，可以滿足較為嚴酷無線通信環境的需要。

[1] Hong X Y, Xu K X, Gerla M.Scalable Routing Protocols for Mobile ad hoc Networks[J].IEEE Network,2002,16(04):11-21.

[2] Ying C,Lv Q,Liu Y,et al.Routing Protocols Overview and Design Issues for Self-Organized Network[C]//Proceedings of 16th World Computer Congress & International Conference on Communication Technology. Beijing, China: [s.n.], 2000:275-282.

[3] Ko Y B,Vaidya N H.Location-Aided Routing(LAR)in Mobile Ad hoc Networks[C]//Proceedings of ACM/IEEE MOBICOM’98.Dallas,TX:IEEE,1998:66-75.

[4] Murthy S,Garcia-Luna-Aceves J J.A Path-find Algorithm for Loop-free Routing[J].IEEE ACM Transactions on Networking,1997,5(01):148-160.