姜永廣，田永春

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

2 改進的路徑查找算法

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

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

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

表1 由倒數(shù)第二跳推導隱含路由

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

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

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

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

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

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

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

APFA引入了可行距離（Feasible Distance，F(xiàn)D）的概念。如下：

3 仿真分析

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

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

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

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

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

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

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

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

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

4 結語

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