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