一種無線自組織網絡動態(tài)路由協議

姜永廣，田永春

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

2 改進的路徑查找算法

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

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

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

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

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

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

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

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

圖1 路徑發(fā)現算法中的臨時環(huán)路舉例

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

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

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

3 仿真分析

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

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

圖2 節(jié)點靜止時收斂時間對比

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

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

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

圖3 節(jié)點移動時收斂時間對比

圖4 節(jié)點運動時路由開銷瞬時值對比

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

4 結語

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

[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.