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