一種新的戰術網絡路由與組網方法

張傳金， 王劍鋒， 姜永廣

0 引言

戰術網絡既不同于傳統有線網絡，也與純粹的 Ad Hoc網絡[1-2]不同。戰術網絡可能既包含了有線IP網絡的成份，又含有無線 Ad Hoc網絡的組成部分。戰術網絡還可能具有衛星鏈路與數據鏈鏈路。戰術網絡的無線網絡成分較多，其帶寬資源十分寶貴，設計戰術網絡的路由協議時，必須盡量減少路由協議自身的傳輸開銷。

我們將戰術網絡看成為廣義的Ad Hoc網絡，則不宜采用反應式(按需)路由協議。因為大多數按需路由是基于查詢/響應的方法，并且采用了泛洪機制來散播查詢分組與維持路由，當網絡業務負荷和移動性增大時，按需路由往往效率很低。此外，反應式路由協議無法保證各類信息業務的服務質量(QoS)要求，特別是不能滿足時延要求。因此，在戰術網絡中應采用先應式路由協議。路由算法大致可以分為距離矢量與鏈路狀態兩類。傳統的距離矢量的優勢，是協議與算法簡單、信息量比較小而且計算效率高，可是由于無序號控制機制，使其具有收斂慢和產生路由環的致命弱點，不適合于高移動性的戰術網絡。而鏈路狀態路由雖然具有收斂快且無環路的優點，但由于其報文格式長、路由信息量較大，使其擴充性受到很大的影響，不適合于戰術網絡。

由于戰術網絡內的節點比較多，網絡規模較大，即使采用分層的路由設計方法[3]，每一層網絡內也可能達到數十甚至上百個以上的節點，路由協議自身的控制開銷不容忽視。因此，戰術網絡的路由協議必須具有可擴充性，能夠適應組建大規模網絡的需要。

戰術網絡的路由協議，必須滿足戰場環境戰術節點的隨遇接入、任意互連、快速開通、快速部署、網絡能快速重組以及能及時反應拓撲變化等需求。戰術網絡中連接的局域網較多，每個節點都可能至少連接了一個附屬的本地IP子網。若采用傳統的 IP子網路由交換方法，則路由協議控制開銷將非常大；若采用廣義Ad Hoc以及ID與IP子網映射的方法，節點之間只交換 ID，既不交換互連子網的 IP，也不交換每個節點的附屬 IP子網的信息，則可以大大壓縮路由協議的控制開銷。

戰術網絡需要一種先應式的、路由信息量小的、無路由環路的、可擴充的路由協議。在這篇文章中，我們提出一種基于多點中繼、模糊視野泛洪機制以及目的地序號控制的距離矢量路由方法，并采取了高效率的消息壓縮機制，該路由方法能滿足戰術網絡的要求。

1 廣義Ad Hoc網絡設計

在每個戰術網絡節點中，除了本地連接的局域網外，將其它所有用于節點間互聯的無線接口與有線接口當成為一個廣義的Ad Hoc網絡接口。組成廣義Ad Hoc網絡接口的各個物理接口，無論是有線還是無線接口，都不需要分配 IP子網地址。廣義Ad Hoc網絡接口也不需要分配IP地址。在廣義Ad Hoc網絡中，每個節點只有一個ID地址。

廣義Ad Hoc網絡中的每一條有線鏈路，相當于無線網絡中在特定方向上的一條無線鏈路。在廣義Ad Hoc網絡中，節點ID與其本地IP子網之間為一種固定的靜態映射關系。無論網絡拓撲如何變化，無論網絡如何重組，這種映射關系始終保持不變。采用這種設計，戰術網絡內的各個節點之間，將不再需要交換關于 IP子網的路由信息，只需要交換關于節點ID的路由信息。只要建立了節點ID路由，通過IP子網路由與節點ID路由之間的映射，就能實現IP子網之間的路由。這種方法是從網絡規劃設計出發，進行減少網絡內路由信息總量的宏觀控制。

廣義Ad Hoc網絡的設計思想，能夠滿足戰術網絡快速開通、快速部署以及壓縮路由消息的長度的需求。此外，還便于采用適用于無線網絡的 Ad Hoc路由協議，適應戰術網絡的任意拓撲結構應用。

2 基于多點中繼與模糊視野路由的距離矢量路由方法

在路由信息量的微觀控制上，我們聯合采用多種方法來減少戰術網絡中交換的路由信息總量。

基于多點中繼與模糊視野路由的距離矢量路由方法(HSMPR)包含五個有機組成部分，即 Hello協議、目的地序號控制(DSDV)距離矢量路由方法、多點中繼(MPR)算法、模糊視野(HS)路由控制方法以及路由消息內容信息聚類壓縮，下面分別進行敘述。

2.1 Hello協議

Hello協議用于建立和維護各節點之間的1-跳與2-跳鄰居的連通信息。節點周期性地發送Hello分組，通告自己的存在與存活。同時每個 Hello分組中攜帶了發送節點的Hello間隔、發送節點的1-跳鄰居節點ID表、鏈路方向表以及鏈路MPR狀態表。

1-跳鄰居節點ID表描述了發送節點通告的所有1-跳鏈路鄰居的ID。

鏈路方向表描述了 1-跳鄰居表包含的各個鏈路的方向(對稱或非對稱)。

鏈路MPR狀態表中包含了發送節點的MPR選擇信息(MPR節點或MPR選擇節點)。

接收節點通過 Hello報文建立和維持與發送節點之間的鄰居連通信息，通過Hello報文中攜帶的1-跳鄰居節點地址表進行 2-跳鄰域內的連通狀態的判斷，并建立自己的 2-跳鄰居表。

接收節點可以根據鄰居節點 Hello間隔來確定鄰居鏈路的超時值。

Hello分組攜帶了發送節點的MPR挑選信息，鄰居節點接收到Hello分組后，可以確定自己是否為該Hello分組發送節點的MPR節點。若為其MPR節點，則應對該Hello分組的發送節點承擔多點中繼的責任，即必須泛洪轉發從MPR挑選節點接收到的拓撲更新消息。

Hello分組還攜帶了發送節點與其所有 1-跳鄰居節點之間的鏈路方向屬性(單向鏈路或對稱鏈路標志)。每個節點在Hello協議的基礎上，完成單向與雙向對稱鏈路的識別，建立1-跳(包括單向的和對稱的)鄰居表與2-跳對稱鄰居表，進而執行MPR挑選算法。

Hello分組的發送周期可以通過配置來進行設置，但應該比拓撲控制的更新周期短，最好不要超過拓撲控制更新周期的一半，確保在一個拓撲控制更新周期內能夠發現對稱的1-跳鄰居。HSMPR路由協議啟動初期，采取較短的Hello發送周期，這樣可以快速建立(1-跳和2-跳)鄰居關系并盡快完成MPR節點的挑選；在節點運行穩定之后，以較大的Hello間隔周期發送，減少網絡負載。在節點運行穩定后，若節點發現了新鄰居，會觸發Hello報文的立即發送，無論Hello間隔是否到期。

Hello協議為MPR路由算法的基礎。

2.2 DSDV路由算法

目的地序號的距離矢量(DSDV)[4]協議來源于對傳統的Bellman-Ford路由(DBF)方法的改進，其特點是利用目的節點序列號解決了 DBF算法的路由環路和無窮計數問題。在DSDV中，每個節點保存一張路由表，路由表維護本節點到網絡內部所有可達的目的節點的路由。路由條目中保存目的節點的序列號，用以區別新舊路由。為維護路由表，節點周期性地廣播路由更新分組。收到路由更新分組后，節點比較其中的目的節點序列號和自己保存的同一目的節點的序列號，如果前者大，就更新自己的路由；如果路由序列相同，則選擇具有較少跳數的路由。路由更新分組要延遲一段時間發送，以防止路由表的波動。

DSDV協議的主要優點是消除了路由環路，加快了收斂速度，同時減少了控制信息的開銷。但是它的不足在于它難以適應速度變化快的移動 Ad Hoc網絡，不支持單向信道，并且為一種路由域內全局性的泛洪機制，存在一定程度的帶寬資源浪費。

2.3 MPR路由算法

多點中繼(MPR)算法，建立在Hello協議的基礎之上，為優化鏈路狀態路由協議(OLSR)的核心算法[5]，特別適合于密集型的Ad Hoc網絡。經過增強性擴展[6]，也能夠在稀疏型網絡中使用。

每個節點與鄰居節點通過Hello協議報文的交換，獲得其 2-跳鄰居信息。根據其 2-跳鄰居信息，挑選出愿意為自己轉發路由更新消息的多點中繼節點。在一個路由域內挑選出的所有 MPR節點，構成一個連通控制子集(CDS)，由 CDS內的節點來完成該區域內的路由消息的(非重復)泛洪。該路由域內的所有節點要么在CDS內，要么為CDS內節點1-跳可到達的。CDS內的節點僅僅為該路由域內的少量節點。

下面敘述我們采用的增強型MPR(EMPR)算法，它既適用于密集型網絡，又適用于稀疏型網絡。

在一個MPR路由域中，每個節點由一個標識號(ID，可為4字節的IP)來標識。增強型 MPR(EMPR)挑選算法中將使用以下術語：

H1(v)：節點v的對稱1-跳鄰居(與v連接的對應接口地址)的集合。

H2(v)：節點v的嚴格對稱的2-跳鄰居的集合。

C(v)：節點v的MPR節點集合。

當為節點v確定轉發節點(MPR)時，先清除所有對稱1-跳鏈路的MPR狀態，然后執行以下步驟的MPR挑選操作：

① 對于H1(v)中的每個節點u，如果u的ID小于其所有1-跳對稱鄰居，且u具有兩個未相互連通的對稱1-跳鄰居(包括進行MPR計算的本節點)，則將u添加到C(v)中(將該1-跳對稱鏈路標記為MPR);

② 對于 H1(v)中的每個節點 u，如果 v不是 u的最小ID(1-跳)鄰居，則將u添加到C(v)中；

③ 對于H2(v)中的每個節點w，如果w只能通過H1(v)中的節點u覆蓋，則將u添加到C(v)中；反復執行該步驟，直到不存在這樣的H2(v)節點為止；

④ 如果H1(v)中的節點u覆蓋的H2(v)中沒有被C(v)覆蓋(即沒有被標記為 MPR的對稱 1-跳鄰居所覆蓋)的未覆蓋節點最多，則將u添加到C(v)中。當兩個節點覆蓋的未覆蓋節點的數量相同時，則由節點ID來選擇添加到C(v)中的那個節點。反復執行該步驟，直到H2(v)被H1(v)完全覆蓋為止。

與DSDV路由泛洪算法相比，MPR算法將路由信息限制在 CDS集合的范圍之內，進一步減小了路由域內交換的路由信息總量。

2.4 模糊視野路由算法

模糊視野(HS)路由方法可以與其它路由協議結合使用，該方法以控制路由消息泛洪范圍的機制來壓縮路由域內的路由信息總開銷。由于這兩種方法所解決的是不同的問題領域，它與其它路由機制一起運作可以創建一種聯合的泛洪機制，使其產生的開銷比單獨使用任何一種路由方法都低[6]。

HS算法的每個拓撲控制消息項中包含了一個向下計數的跳數域TTL，用于拓撲控制消息項的泛洪范圍控制。

HS算法在進行了一次全局性的路由更新(RMU)消息傳遞(即將TTL域設置為代表無窮大的值，RMU消息將在整個CDS內泛洪)之后，如果在過去的tes內發生了一次鏈路狀態變化，則節點每隔tes被“喚醒”并發送一個RMU消息，其TTL值為s1。此外，如果在過去的2tes內發生了一次鏈路狀態變化，則節點每隔2tes被“喚醒”并傳遞一個RMU消息，其 TTL 值為 s2。一般地說，如果在過去的 2i-1×tes(i=1，2，3，…)內發生了一次鏈路狀態變化，則節點每隔 2i-1×tes被“喚醒”并傳遞一個RMU消息，其TTL值為si。選擇s1=2將s1,s2,s3,s4,…替換為2,4,8,16,…,可以使一個加入網絡的節點引起的總開銷最小化。

在一個具有N個節點的網絡中，HS算法產生RMU消息的過程，可由下面的公式來描述：

如果i恰好等于2的冪值，則將RMU消息的跳數界限域的值設置為i。如果i不等于2的冪值，但能被2的j次冪除盡，則將RMU消息的跳數界限域的值設置為j。

為了使該算法適用于低移動性網絡，可以設置一個周期全局廣播(全局泛洪)定時器tb,確保每隔tbs至少傳遞一個全局RMU消息。為了便于理解，下面以圖例來說明HS產生RMU更新的過程。

圖1 HS算法產生拓撲更新消息的過程

圖1 展示了HS算法中RMU消息產生過程的一個例子，由于移動性高，其結果每隔tes都產生了一個RMU。例如，考慮在時刻4te的情形。該時刻為te(與s1關聯)的倍數，并且也為2te(與s2關聯)和4te(與s3關聯)的倍數。需要注意，如果在過去的te或2tes內發生了一次鏈路狀態變化，則意味著在過去的4tes內也發生了一次鏈路狀態變化。因而，如果節點已經設置TTL域至少為s1(或s2)，也必須將其增大為s3。同樣，如果在過去的4tes內沒有發生過一次鏈路狀態變化，那么在過去的te或2tes內也沒有發生過一次鏈路狀態變化。因此，如果節點沒有發送過TTL值設置為s3的RMU，那么節點也就根本沒有發送過RMU。所以，在時刻4te(同樣在時刻12te、20te以及4kte的任何其它時刻，這里k為奇數)，需要核查過去的4tes內是否發生鏈路狀態變化。如果有，則發送一個TTL值設置為s3的RMU。因而，假設在高移動性場景中，在時刻4te和12te，將發送一個TTL值等于s3的RMU。很明顯，HS算法能夠保證離參考節點 si跳遠的那些節點，將在最多 2i-1te秒后獲得該節點的鏈路狀態的變化情況。

HS算法在MPR算法的基礎之上，限制了某些路由消息的泛洪范圍，進一步減少了路由域內交換的路由信息總量。

2.5 路由消息聚類壓縮

在對各節點進行ID編址時，若能保持高2字節或3字節相同，則在原始路由更新報文發送之前，可以根據信息內容組成，將各個HSMPR路由更新消息項的ID部分分離出來，集中形成多個 ID的聚類數據塊，然后對聚類數據塊進行壓縮[8]，得到壓縮后的路由更新報文，再進行傳輸。接收到壓縮的路由更新報文后，先進行解壓縮操作，然后復原為原始的路由消息報文，再進行正常的路由消息處理。

路由消息聚類壓縮可以大大壓縮路由更新報文的長度，進一步減少路由域內交換的路由信息總量。

3 HSMPR路由方法性能仿真

為便于性能對比，采用OPNET12.0.A仿真工具軟件，在分布在100 km×100 km區域上均勻分布32個數節點的平面Ad Hoc網絡內，分別對OLSR和HSMPR兩種路由協議進行仿真。

本次試驗的主要目的是對不同規模大小的扁平網絡中采用兩種路由協議的性能比較。

仿真的扁平戰術網絡規模為32個節點的平面網絡，信道帶寬為2 Mb/s，有效通信距離為設置為只能與相鄰節點通信的范圍，仿真網絡運行一小時，統計結果如下仿真場景如圖2所示。

圖2 HSMPR路由協議仿真場景

圖3 為32個節點的平面網絡中HSMPR與OLSR的路由開銷對比情況。

其中上面的統計線代表采用OLSR路由協議的情況，網絡的路由開銷穩定在 24 kb/s左右；下面的統計線代表采用HSMPR路由協議的情況，網絡的路由開銷穩定在10 kb/s左右。

從仿真結果來看，HSMPR路由方法，由于充分發揮了兩種多點中繼、模糊視野、距離矢量算法各自的優點。在這種場景中，HSMPR路由與 OLSR路由的平均開銷比為 10/24≈41.6%。對于戰術網絡，聯合采用HS、MPR以及DSDV的路由方法，是一種非常好的選擇。

圖3 32節點平面網絡中兩種協議的開銷

這種路由方法用于戰術網絡的缺點，是每個節點不能了解全局的拓撲信息，而在鏈路狀態路由方法中，每個節點都具有全局的網絡拓撲態勢信息。

4 結語

這篇文章提出了適用于戰術網絡的廣義Ad Hoc網絡概念，并提出了采用節點 ID與本地子網的固定映射關系，來解決 IP子網之間的路由問題。在戰術網絡中，只需要解決節點ID之間的Ad Hoc路由，這種方法可以大大壓縮交換的路由信息量。采用MPR與HS以及DSDV融合的路由方法，可使路由協議的控制開銷大大地降低，并且大大增強了戰術路由協議的可擴充性，這種路由方法可以應用于規模較大的戰術網絡中。下一步的工作是采用更加優化的MPR算法，進一步縮小CDS的大小，使這種路由方法更加優化。

[1] 郭中華,史浩山. Ad Hoc網絡路由協議性能分析[J].通信技術,2008,41(11)：111-113.

[2] 謝曉川,韋崗,吳克平.用于Ad Hoc網絡的多徑混合路由[J].通信技術,2009,42(01)：225-227.

[3] Xu Kaixin, Hong Xiaoyan, Gerla M,et al. Landmark Routing in Large Wireless Battlefield Networks Using Uavs[J]. IEEE,2001(01)：230-234.

[4] Perkins C E, Bhagwat P. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers[C].USA：ACM,1994：234-244.

[5] Clausen T, acquet P.The Optimized Link State Routing Protocol[S].France：[s.n.],2003.

[6] Jie Wu, Wei Lou. Extended Multipoint Relays to Determine Connected Dominating Sets in MANETs[C].USA：IEEE, 2005：556-560.

[7] Maker J P, Dean J W.A Study of Link State Flooding Optimizations for Scalable Wireless Networks[C]. USA：ACM, 2004：1-6.

[8] Clausen T,Dean J,Dearlove C,et al.Generalized MANET Packet/Message Format[EB/OL].(2009-03-01)[2009-03-20].http： //www.ietf.org/work in progress draft-ietf-manet-packetbb- 17.txt.