賈 森，劉小娟，吳明曦
（武漢中原電子集團有限公司，湖北 武漢 430205）
0 引言
移動自組織網絡（Mobile Ad hoc Networks，MANET）是一種由移動節(jié)點組成的自組織的無線網絡，每個節(jié)點同時具有終端和路由器兩者的功能[1]。不同于傳統的蜂窩無線網絡，MANET 不依賴基站，每個節(jié)點具有同等的地位，節(jié)點可以通過中間節(jié)點轉發(fā)與多跳節(jié)點通信，因此它是一種多跳網絡。MANET由于每個節(jié)點都具有終端和路由器的功能，對外部環(huán)境有更強的適應力，每個節(jié)點可以隨意移動和自動組網，因此被廣泛應用于軍事通信、車車通信和無人機群通信等領域，具有很光明的發(fā)展前景。尤其在軍用領域，野外環(huán)境復雜多變，MANET 無中心和自組織的特點非常適合陸、海、空作戰(zhàn)使用。
美國國防部早在20 世紀70 年代初就開始研究移動分組網絡，即MANET 的前身[2]。后美軍MANET 技術迅速發(fā)展成熟，現在已經具有完整的技術體系[3]。我國在MANET 軍用化方面起步較晚，現在還處于研究摸索階段，尚未形成完整的體系。我國應重視網絡技術，學習美軍的長處，大力發(fā)展戰(zhàn)術互聯網[4]。在戰(zhàn)場無線通信領域，網絡中參與通信組網的節(jié)點一般最多30 多個，而隨著我國無線通信技術以及網絡技術的飛速發(fā)展，網絡中組網節(jié)點的容量需求已經達到了100 多個節(jié)點的規(guī)模。但在大規(guī)模組網中，現有的一些網絡路由協議并不完全適用，尤其是平面網絡架構，該架構中的節(jié)點數量太大，會導致網絡中路由開銷過大，通信性能不佳，故針對大規(guī)模組網路由的研究十分必要。
本文內容安排為：第1 節(jié)介紹分簇網絡架構，第2 節(jié)介紹簇內路由，第3 節(jié)介紹簇間路由，第4 節(jié) 進行仿真和分析，第5 節(jié)總結全文。
1 分簇網絡架構
傳統的平面網絡架構如圖1 所示，具有結構簡單、網內節(jié)點地位平等、健壯性較好的優(yōu)點。但隨著網內節(jié)點數量的增加，網內路由開銷會急劇增加，故平面網絡架構只適用于小規(guī)模的MANET 網絡，因此本文方案采取分簇網絡架構來進行大規(guī)模組網[5]，如圖2 所示。分簇是指將網絡中節(jié)點劃分為不同的虛擬群組集合這一過程。分簇網絡架構中的節(jié)點類型有簇首節(jié)點、網關節(jié)點和成員節(jié)點3 種�？梢钥闯觯执鼐W絡架構的結構更復雜，網內開銷更少，很適合大規(guī)模MANET 網絡。
圖1 平面網絡架構
圖2 分簇網絡架構
簇首節(jié)點是分簇的管理者，負責管理分簇內部的成員節(jié)點，是網內的重要節(jié)點。簇首節(jié)點在不同的分簇路由算法中，起到的作用不完全相同。簇首節(jié)點可以統計分簇成員節(jié)點的信息和簇與簇之間的位置關系，并負責將簇內廣播信息通知到分簇所有節(jié)點，還可以承擔簇間尋址的職責。選舉簇首及分簇常見的方法有最小ID分簇法、最高節(jié)點度分簇法、最低移動性分簇法、地理位置中心分簇法這幾種[6]。最小ID 分簇法[7]為網絡內每個節(jié)點都分配了一個獨有的ID 號，然后選取ID 號最小的節(jié)點為簇首節(jié)點，其一跳鄰居節(jié)點為該簇首節(jié)點的簇成員，然后繼續(xù)選取剩下節(jié)點中ID 最小的節(jié)點，循環(huán)此選取過程。最高節(jié)點度分簇法[8]是將鄰居節(jié)點最多的節(jié)點選為簇首節(jié)點。最低移動性分簇法[9]中，節(jié)點移動性越高，節(jié)點選為簇首的權重就越低，依次選擇最低移動性的節(jié)點為簇首。地理位置中心分簇法[10]則是通過地理位置信息來選擇簇首。這幾種分簇方法各有優(yōu)劣，可以基于不同組網方案具體選擇其中一種來分簇。
網關節(jié)點負責鄰簇之間的通信，發(fā)往鄰簇的包須通過網關轉發(fā)到鄰簇的對應網關�？梢酝ㄟ^簇間感知，根據收到信號的能量強度，把相鄰兩簇的綜合信號能量強度最大的一對節(jié)點或幾對節(jié)點選為網關。
2 簇內路由
路由協議的種類有先驗式路由協議、反應式路由協議和這兩種混合式路由協議。本路由方案采用一種改進的優(yōu)化的鏈路狀態(tài)路由（Optimized Link State Routing，OLSR）協議作為簇內路由。OLSR[11]是一種典型的先驗式路由協議，RFC3626 中有詳盡的描述。OLSR 會維護全網節(jié)點的拓撲結構，周期性更新全網拓撲結構，根據最短路徑算法周期性計算本節(jié)點到網內其他節(jié)點的路由。OLSR 路由可以即時根據拓撲變化，快速地查詢到路由，非常適合MANET 使用。
OLSR 的路由包主要有HELLO 和TC 兩種。HELLO 包用來進行鄰居發(fā)現，構建一跳兩跳拓撲。TC 包經多跳轉發(fā)，用來構建多跳拓撲。只有MPR節(jié)點才會產生TC 包，這樣就減少了網絡內TC 包的數量，大大減少了網絡開銷。節(jié)點在鄰居節(jié)點中選出MPR，選擇的標準是要保證通過MPR 節(jié)點集，可以到達節(jié)點的所有二跳節(jié)點。但標準MPR選舉過程[12]選出的MPR 集有冗余，并不是最少集合，本方案用統一連通支配集（Unifying Connected Dominating Set，UCDS）算法[13]來選舉MPR 集。UCDS 算法就是在尋找最少的連通支配集，本文方案MPR 選舉過程如圖3 所示。
圖3 MPR 集合選舉過程
其中的規(guī)則1 至規(guī)則4 具體如下文所述。
（1）規(guī)則1：
①如果節(jié)點i與其所有一跳鄰居相比具有最高的支配因子（一跳鄰居數量d），則節(jié)點i選擇自己作為DS 集合成員。
②如果節(jié)點i的鄰居節(jié)點j發(fā)現i在j的所有鄰居節(jié)點中具有最高的支配因子，則節(jié)點j選擇節(jié)點i作為DS 集合成員。
③如果節(jié)點i與N(j)中支配因子最高的節(jié)點k的支配因子相同，則比較節(jié)點ID，選擇ID 號小的作為DS 集合成員。N(j)表示j的鄰居節(jié)點集合。
（2）規(guī)則2：
①如果節(jié)點i的所有鄰居節(jié)點都是直接連通的，則節(jié)點i不是CS 集合成員，為普通節(jié)點。
（3）規(guī)則3。對于DS 集合之外，且不滿足規(guī)則2 的節(jié)點為：
①如果節(jié)點i不是DS 集合的成員，且i有鄰居節(jié)點l和m，l和m中至少有一個屬于DS集合的成員，如果節(jié)點l的Ds(N(l))與節(jié)點m的Ds(N(m))不相交，則i是CS 集合的候選成員。其中N(m)表示m的鄰居節(jié)點集合，Ds(N(m))表示N(m)中歸屬于DS 集合的節(jié)點集合。
②如果l和m還有其他的滿足上述條件的普通鄰居節(jié)點i'，則比較所有i和i'的支配因子，支配因子最高的為CS 集合成員，支配因子相同時節(jié)點ID 小的選為CS 集合成員。
（4）規(guī)則4。對于DS 集合之外，不滿足規(guī)則2，且滿足規(guī)則3 的節(jié)點為：如果i的兩個鄰居節(jié)點j和k中，j不是DS 集合成員，k是DS 集合成員，而且節(jié)點i和節(jié)點j有同一個DS 鄰居節(jié)點，則節(jié)點i不用執(zhí)行規(guī)則3，將節(jié)點i重置為普通節(jié)點。
3 簇間路由
跨簇業(yè)務需要簇間路由，常見的簇間路由協議分為先驗式和反應式兩種。區(qū)域路由協議（Zone Routing Protocol，ZRP）[14]和基于分簇路由協議（Cluster Based Routing Protocol，CBRP）[15]簇間都采用反應式的路由方式，需要簇間路由時，才去尋找簇間路徑，所以延遲比較大，簇間業(yè)務時延高。簇首網關交換路由協議（Cluster-head Gateway Switch Routing，CGSR）[16]簇間采用的是先驗式路由方式，簇首和簇首之間周期性交互簇路由信息和簇成員信息，即時維護簇首和簇首之間的路由。CGSR 路由協議目前使用最為廣泛，但是CGSR 路由協議有一個缺點，所有簇成員業(yè)務必須先發(fā)送到本簇簇首，然后通過本簇簇首轉發(fā)到目的簇，這樣會導致簇首節(jié)點流量過大，不利于負載均衡，網絡比較脆弱。國內有些學者也針對CGSR 這一缺點做了研究，例如：文獻[17]通過減少信息轉發(fā)次數，減少簇首能量消耗；文獻[18]通過選取多個簇首分攤流量的方式，平衡簇首能量消耗。但是這些研究中的業(yè)務仍需要先發(fā)往簇首，然后轉發(fā)到目的簇。本文提出了一種簇間路由方法，業(yè)務直接由節(jié)點發(fā)往網關，不經過簇首。
本文所提方案中，每個簇首會分別在規(guī)劃的簇首廣播時隙內，將簇鄰居信息和簇成員列表廣播洪泛到全網。把每個簇看成一個節(jié)點，簡稱簇節(jié)點，并分配一個獨有的ID，然后就可以得到簇與簇之間的路由，具體思路為：先根據本簇的鄰簇信息得到本簇的一跳簇節(jié)點；然后根據收到的一跳簇節(jié)點的鄰簇信息分析，若該節(jié)點的簇ID 不是本簇節(jié)點且不是本簇的一跳簇節(jié)點的簇，則為本簇的兩跳簇節(jié)點；再根據兩跳簇節(jié)點的鄰簇信息分析，若該節(jié)點的簇ID 不是本簇的一跳簇節(jié)點且不是本簇的兩跳簇節(jié)點的簇，則為本簇的三跳簇節(jié)點。以此類推，將此過程進行下去直到沒有新的多跳簇節(jié)點產生。這樣就構建出了整個簇間的路由。
參照圖4 以節(jié)點1 為例說明簇間路由建立過程，1 的一跳簇節(jié)點為2、3、4、7。2 和4 的一跳簇節(jié)點是本簇節(jié)點，故2 和4 方向沒有1 的二跳簇節(jié)點。3 的鄰簇節(jié)點中，非本簇節(jié)點且非本簇的一跳簇節(jié)點的有5 和6，所以5 和6 為1 的兩跳簇節(jié)點，路由為1-3-5，1-3-6。7 的符合條件的鄰居簇節(jié)點為8，故8 是1 的兩跳簇節(jié)點，路由為1-7-8。如圖4 所示，節(jié)點1 的所有路由構建完成。
圖4 8 個分簇鄰居關系
路由尋址時，根據簇間收到的簇內節(jié)點信息，可以判斷目的節(jié)點所處的簇ID，然后根據簇間路由查詢下一跳需要發(fā)往的簇節(jié)點，本節(jié)點發(fā)送到其對應的本簇網關即可。簇內節(jié)點只需要把業(yè)務發(fā)往由簇間路由確定的本簇網關，然后本簇網關把包發(fā)給對應鄰簇網關，業(yè)務到鄰簇后繼續(xù)通過簇間路由確定需要發(fā)往的對應網關，直到業(yè)務發(fā)到目的簇后，由網關發(fā)往目的節(jié)點。本簇間路由方案由于簇數量有限，所以建立路由的過程簡單方便，而且實現了業(yè)務直接發(fā)往網關，不需要簇首的參與，還可以在選舉網關時多選舉幾對來分攤網關的流量。
4 仿真及分析
本節(jié)用OPNET 仿真軟件進行模擬建模，將本方案的分簇OLSR 路由協議和平面網絡架構的標準OLSR 路由協議進行對比。如圖5 所示，網內共有128 個節(jié)點，在運行標準OLSR 路由協議情況下，128 個節(jié)點不分簇，在運行本方案路由情況下，128個節(jié)點分為4 個簇，每個簇32 個節(jié)點，兩者對比。
圖5 128 節(jié)點仿真分布
仿真結果如圖6 所示，對比兩種情況下網內路由開銷。仿真設置的10 s 開始運行路由，圖6 橫軸是運行時間，總共運行2分鐘，縱軸是全網路由開銷，單位bits/s 表示每秒全網路由開銷的比特數。圖6上半部分表示平面網絡架構下標準OLSR 的路由開銷，路由運行穩(wěn)定后路由開銷穩(wěn)定在每秒20 萬比特到每秒60 萬比特之間。圖6 下半部分表示本方案的分簇OLSR 路由的開銷，路由運行穩(wěn)定后路由開銷穩(wěn)定在接近每秒5 萬比特。可以看出，運用分簇網絡架構的本方案相比傳統的平面網絡架構的標準OLSR，能大幅度降低全網內網絡開銷，前者峰值僅為后者峰值的1/12。
圖6 仿真結果對比
5 結語
隨著MANET 中節(jié)點數越來越多，全網的路由開銷越來越大，傳統的平面網絡架構已經不適用于MANET 網絡。本文針對這一情況，選擇分簇網絡架構，提出了一種基于OLSR 的分簇路由協議，可以很好地降低大規(guī)模MANET 網內路由開銷。下一步研究需要考慮如何花費較小時隙資源將簇內成員信息和簇間鄰居關系廣播到全網。
