基于OLSR 的大規(guī)模組網(wǎng)路由*

賈 森，劉小娟，吳明曦

（武漢中原電子集團(tuán)有限公司，湖北 武漢 430205）

0 引言

移動(dòng)自組織網(wǎng)絡(luò)（Mobile Ad hoc Networks，MANET）是一種由移動(dòng)節(jié)點(diǎn)組成的自組織的無(wú)線網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)同時(shí)具有終端和路由器兩者的功能[1]。不同于傳統(tǒng)的蜂窩無(wú)線網(wǎng)絡(luò)，MANET 不依賴(lài)基站，每個(gè)節(jié)點(diǎn)具有同等的地位，節(jié)點(diǎn)可以通過(guò)中間節(jié)點(diǎn)轉(zhuǎn)發(fā)與多跳節(jié)點(diǎn)通信，因此它是一種多跳網(wǎng)絡(luò)。MANET由于每個(gè)節(jié)點(diǎn)都具有終端和路由器的功能，對(duì)外部環(huán)境有更強(qiáng)的適應(yīng)力，每個(gè)節(jié)點(diǎn)可以隨意移動(dòng)和自動(dòng)組網(wǎng)，因此被廣泛應(yīng)用于軍事通信、車(chē)車(chē)通信和無(wú)人機(jī)群通信等領(lǐng)域，具有很光明的發(fā)展前景。尤其在軍用領(lǐng)域，野外環(huán)境復(fù)雜多變，MANET 無(wú)中心和自組織的特點(diǎn)非常適合陸、海、空作戰(zhàn)使用。

美國(guó)國(guó)防部早在20 世紀(jì)70 年代初就開(kāi)始研究移動(dòng)分組網(wǎng)絡(luò)，即MANET 的前身[2]。后美軍MANET 技術(shù)迅速發(fā)展成熟，現(xiàn)在已經(jīng)具有完整的技術(shù)體系[3]。我國(guó)在MANET 軍用化方面起步較晚，現(xiàn)在還處于研究摸索階段，尚未形成完整的體系。我國(guó)應(yīng)重視網(wǎng)絡(luò)技術(shù)，學(xué)習(xí)美軍的長(zhǎng)處，大力發(fā)展戰(zhàn)術(shù)互聯(lián)網(wǎng)[4]。在戰(zhàn)場(chǎng)無(wú)線通信領(lǐng)域，網(wǎng)絡(luò)中參與通信組網(wǎng)的節(jié)點(diǎn)一般最多30 多個(gè)，而隨著我國(guó)無(wú)線通信技術(shù)以及網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)中組網(wǎng)節(jié)點(diǎn)的容量需求已經(jīng)達(dá)到了100 多個(gè)節(jié)點(diǎn)的規(guī)模。但在大規(guī)模組網(wǎng)中，現(xiàn)有的一些網(wǎng)絡(luò)路由協(xié)議并不完全適用，尤其是平面網(wǎng)絡(luò)架構(gòu)，該架構(gòu)中的節(jié)點(diǎn)數(shù)量太大，會(huì)導(dǎo)致網(wǎng)絡(luò)中路由開(kāi)銷(xiāo)過(guò)大，通信性能不佳，故針對(duì)大規(guī)模組網(wǎng)路由的研究十分必要。

本文內(nèi)容安排為：第1 節(jié)介紹分簇網(wǎng)絡(luò)架構(gòu)，第2 節(jié)介紹簇內(nèi)路由，第3 節(jié)介紹簇間路由，第4 節(jié) 進(jìn)行仿真和分析，第5 節(jié)總結(jié)全文。

1 分簇網(wǎng)絡(luò)架構(gòu)

傳統(tǒng)的平面網(wǎng)絡(luò)架構(gòu)如圖1 所示，具有結(jié)構(gòu)簡(jiǎn)單、網(wǎng)內(nèi)節(jié)點(diǎn)地位平等、健壯性較好的優(yōu)點(diǎn)。但隨著網(wǎng)內(nèi)節(jié)點(diǎn)數(shù)量的增加，網(wǎng)內(nèi)路由開(kāi)銷(xiāo)會(huì)急劇增加，故平面網(wǎng)絡(luò)架構(gòu)只適用于小規(guī)模的MANET 網(wǎng)絡(luò)，因此本文方案采取分簇網(wǎng)絡(luò)架構(gòu)來(lái)進(jìn)行大規(guī)模組網(wǎng)[5]，如圖2 所示。分簇是指將網(wǎng)絡(luò)中節(jié)點(diǎn)劃分為不同的虛擬群組集合這一過(guò)程。分簇網(wǎng)絡(luò)架構(gòu)中的節(jié)點(diǎn)類(lèi)型有簇首節(jié)點(diǎn)、網(wǎng)關(guān)節(jié)點(diǎn)和成員節(jié)點(diǎn)3 種。可以看出，分簇網(wǎng)絡(luò)架構(gòu)的結(jié)構(gòu)更復(fù)雜，網(wǎng)內(nèi)開(kāi)銷(xiāo)更少，很適合大規(guī)模MANET 網(wǎng)絡(luò)。

圖1 平面網(wǎng)絡(luò)架構(gòu)

圖2 分簇網(wǎng)絡(luò)架構(gòu)

簇首節(jié)點(diǎn)是分簇的管理者，負(fù)責(zé)管理分簇內(nèi)部的成員節(jié)點(diǎn)，是網(wǎng)內(nèi)的重要節(jié)點(diǎn)。簇首節(jié)點(diǎn)在不同的分簇路由算法中，起到的作用不完全相同。簇首節(jié)點(diǎn)可以統(tǒng)計(jì)分簇成員節(jié)點(diǎn)的信息和簇與簇之間的位置關(guān)系，并負(fù)責(zé)將簇內(nèi)廣播信息通知到分簇所有節(jié)點(diǎn)，還可以承擔(dān)簇間尋址的職責(zé)。選舉簇首及分簇常見(jiàn)的方法有最小ID分簇法、最高節(jié)點(diǎn)度分簇法、最低移動(dòng)性分簇法、地理位置中心分簇法這幾種[6]。最小ID 分簇法[7]為網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)都分配了一個(gè)獨(dú)有的ID 號(hào)，然后選取ID 號(hào)最小的節(jié)點(diǎn)為簇首節(jié)點(diǎn)，其一跳鄰居節(jié)點(diǎn)為該簇首節(jié)點(diǎn)的簇成員，然后繼續(xù)選取剩下節(jié)點(diǎn)中ID 最小的節(jié)點(diǎn)，循環(huán)此選取過(guò)程。最高節(jié)點(diǎn)度分簇法[8]是將鄰居節(jié)點(diǎn)最多的節(jié)點(diǎn)選為簇首節(jié)點(diǎn)。最低移動(dòng)性分簇法[9]中，節(jié)點(diǎn)移動(dòng)性越高，節(jié)點(diǎn)選為簇首的權(quán)重就越低，依次選擇最低移動(dòng)性的節(jié)點(diǎn)為簇首。地理位置中心分簇法[10]則是通過(guò)地理位置信息來(lái)選擇簇首。這幾種分簇方法各有優(yōu)劣，可以基于不同組網(wǎng)方案具體選擇其中一種來(lái)分簇。

網(wǎng)關(guān)節(jié)點(diǎn)負(fù)責(zé)鄰簇之間的通信，發(fā)往鄰簇的包須通過(guò)網(wǎng)關(guān)轉(zhuǎn)發(fā)到鄰簇的對(duì)應(yīng)網(wǎng)關(guān)。可以通過(guò)簇間感知，根據(jù)收到信號(hào)的能量強(qiáng)度，把相鄰兩簇的綜合信號(hào)能量強(qiáng)度最大的一對(duì)節(jié)點(diǎn)或幾對(duì)節(jié)點(diǎn)選為網(wǎng)關(guān)。

2 簇內(nèi)路由

路由協(xié)議的種類(lèi)有先驗(yàn)式路由協(xié)議、反應(yīng)式路由協(xié)議和這兩種混合式路由協(xié)議。本路由方案采用一種改進(jìn)的優(yōu)化的鏈路狀態(tài)路由（Optimized Link State Routing，OLSR）協(xié)議作為簇內(nèi)路由。OLSR[11]是一種典型的先驗(yàn)式路由協(xié)議，RFC3626 中有詳盡的描述。OLSR 會(huì)維護(hù)全網(wǎng)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)，周期性更新全網(wǎng)拓?fù)浣Y(jié)構(gòu)，根據(jù)最短路徑算法周期性計(jì)算本節(jié)點(diǎn)到網(wǎng)內(nèi)其他節(jié)點(diǎn)的路由。OLSR 路由可以即時(shí)根據(jù)拓?fù)渥兓焖俚夭樵兊铰酚桑浅＿m合MANET 使用。

OLSR 的路由包主要有HELLO 和TC 兩種。HELLO 包用來(lái)進(jìn)行鄰居發(fā)現(xiàn)，構(gòu)建一跳兩跳拓?fù)洹C 包經(jīng)多跳轉(zhuǎn)發(fā)，用來(lái)構(gòu)建多跳拓?fù)洹Ｖ挥蠱PR節(jié)點(diǎn)才會(huì)產(chǎn)生TC 包，這樣就減少了網(wǎng)絡(luò)內(nèi)TC 包的數(shù)量，大大減少了網(wǎng)絡(luò)開(kāi)銷(xiāo)。節(jié)點(diǎn)在鄰居節(jié)點(diǎn)中選出MPR，選擇的標(biāo)準(zhǔn)是要保證通過(guò)MPR 節(jié)點(diǎn)集，可以到達(dá)節(jié)點(diǎn)的所有二跳節(jié)點(diǎn)。但標(biāo)準(zhǔn)MPR選舉過(guò)程[12]選出的MPR 集有冗余，并不是最少集合，本方案用統(tǒng)一連通支配集（Unifying Connected Dominating Set，UCDS）算法[13]來(lái)選舉MPR 集。UCDS 算法就是在尋找最少的連通支配集，本文方案MPR 選舉過(guò)程如圖3 所示。

圖3 MPR 集合選舉過(guò)程

其中的規(guī)則1 至規(guī)則4 具體如下文所述。

（1）規(guī)則1：

①如果節(jié)點(diǎn)i與其所有一跳鄰居相比具有最高的支配因子（一跳鄰居數(shù)量d），則節(jié)點(diǎn)i選擇自己作為DS 集合成員。

②如果節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)j發(fā)現(xiàn)i在j的所有鄰居節(jié)點(diǎn)中具有最高的支配因子，則節(jié)點(diǎn)j選擇節(jié)點(diǎn)i作為DS 集合成員。

③如果節(jié)點(diǎn)i與N(j)中支配因子最高的節(jié)點(diǎn)k的支配因子相同，則比較節(jié)點(diǎn)ID，選擇ID 號(hào)小的作為DS 集合成員。N(j)表示j的鄰居節(jié)點(diǎn)集合。

（2）規(guī)則2：

①如果節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)都是直接連通的，則節(jié)點(diǎn)i不是CS 集合成員，為普通節(jié)點(diǎn)。

（3）規(guī)則3。對(duì)于DS 集合之外，且不滿足規(guī)則2 的節(jié)點(diǎn)為：

①如果節(jié)點(diǎn)i不是DS 集合的成員，且i有鄰居節(jié)點(diǎn)l和m，l和m中至少有一個(gè)屬于DS集合的成員，如果節(jié)點(diǎn)l的Ds(N(l))與節(jié)點(diǎn)m的Ds(N(m))不相交，則i是CS 集合的候選成員。其中N(m)表示m的鄰居節(jié)點(diǎn)集合，Ds(N(m))表示N(m)中歸屬于DS 集合的節(jié)點(diǎn)集合。

②如果l和m還有其他的滿足上述條件的普通鄰居節(jié)點(diǎn)i'，則比較所有i和i'的支配因子，支配因子最高的為CS 集合成員，支配因子相同時(shí)節(jié)點(diǎn)ID 小的選為CS 集合成員。

（4）規(guī)則4。對(duì)于DS 集合之外，不滿足規(guī)則2，且滿足規(guī)則3 的節(jié)點(diǎn)為：如果i的兩個(gè)鄰居節(jié)點(diǎn)j和k中，j不是DS 集合成員，k是DS 集合成員，而且節(jié)點(diǎn)i和節(jié)點(diǎn)j有同一個(gè)DS 鄰居節(jié)點(diǎn)，則節(jié)點(diǎn)i不用執(zhí)行規(guī)則3，將節(jié)點(diǎn)i重置為普通節(jié)點(diǎn)。

3 簇間路由

跨簇業(yè)務(wù)需要簇間路由，常見(jiàn)的簇間路由協(xié)議分為先驗(yàn)式和反應(yīng)式兩種。區(qū)域路由協(xié)議（Zone Routing Protocol，ZRP）[14]和基于分簇路由協(xié)議（Cluster Based Routing Protocol，CBRP）[15]簇間都采用反應(yīng)式的路由方式，需要簇間路由時(shí)，才去尋找簇間路徑，所以延遲比較大，簇間業(yè)務(wù)時(shí)延高。簇首網(wǎng)關(guān)交換路由協(xié)議（Cluster-head Gateway Switch Routing，CGSR）[16]簇間采用的是先驗(yàn)式路由方式，簇首和簇首之間周期性交互簇路由信息和簇成員信息，即時(shí)維護(hù)簇首和簇首之間的路由。CGSR 路由協(xié)議目前使用最為廣泛，但是CGSR 路由協(xié)議有一個(gè)缺點(diǎn)，所有簇成員業(yè)務(wù)必須先發(fā)送到本簇簇首，然后通過(guò)本簇簇首轉(zhuǎn)發(fā)到目的簇，這樣會(huì)導(dǎo)致簇首節(jié)點(diǎn)流量過(guò)大，不利于負(fù)載均衡，網(wǎng)絡(luò)比較脆弱。國(guó)內(nèi)有些學(xué)者也針對(duì)CGSR 這一缺點(diǎn)做了研究，例如：文獻(xiàn)[17]通過(guò)減少信息轉(zhuǎn)發(fā)次數(shù)，減少簇首能量消耗；文獻(xiàn)[18]通過(guò)選取多個(gè)簇首分?jǐn)偭髁康姆绞剑胶獯厥啄芰肯摹５沁@些研究中的業(yè)務(wù)仍需要先發(fā)往簇首，然后轉(zhuǎn)發(fā)到目的簇。本文提出了一種簇間路由方法，業(yè)務(wù)直接由節(jié)點(diǎn)發(fā)往網(wǎng)關(guān)，不經(jīng)過(guò)簇首。

本文所提方案中，每個(gè)簇首會(huì)分別在規(guī)劃的簇首廣播時(shí)隙內(nèi)，將簇鄰居信息和簇成員列表廣播洪泛到全網(wǎng)。把每個(gè)簇看成一個(gè)節(jié)點(diǎn)，簡(jiǎn)稱(chēng)簇節(jié)點(diǎn)，并分配一個(gè)獨(dú)有的ID，然后就可以得到簇與簇之間的路由，具體思路為：先根據(jù)本簇的鄰簇信息得到本簇的一跳簇節(jié)點(diǎn)；然后根據(jù)收到的一跳簇節(jié)點(diǎn)的鄰簇信息分析，若該節(jié)點(diǎn)的簇ID 不是本簇節(jié)點(diǎn)且不是本簇的一跳簇節(jié)點(diǎn)的簇，則為本簇的兩跳簇節(jié)點(diǎn)；再根據(jù)兩跳簇節(jié)點(diǎn)的鄰簇信息分析，若該節(jié)點(diǎn)的簇ID 不是本簇的一跳簇節(jié)點(diǎn)且不是本簇的兩跳簇節(jié)點(diǎn)的簇，則為本簇的三跳簇節(jié)點(diǎn)。以此類(lèi)推，將此過(guò)程進(jìn)行下去直到?jīng)]有新的多跳簇節(jié)點(diǎn)產(chǎn)生。這樣就構(gòu)建出了整個(gè)簇間的路由。

參照?qǐng)D4 以節(jié)點(diǎn)1 為例說(shuō)明簇間路由建立過(guò)程，1 的一跳簇節(jié)點(diǎn)為2、3、4、7。2 和4 的一跳簇節(jié)點(diǎn)是本簇節(jié)點(diǎn)，故2 和4 方向沒(méi)有1 的二跳簇節(jié)點(diǎn)。3 的鄰簇節(jié)點(diǎn)中，非本簇節(jié)點(diǎn)且非本簇的一跳簇節(jié)點(diǎn)的有5 和6，所以5 和6 為1 的兩跳簇節(jié)點(diǎn)，路由為1-3-5，1-3-6。7 的符合條件的鄰居簇節(jié)點(diǎn)為8，故8 是1 的兩跳簇節(jié)點(diǎn)，路由為1-7-8。如圖4 所示，節(jié)點(diǎn)1 的所有路由構(gòu)建完成。

圖4 8 個(gè)分簇鄰居關(guān)系

路由尋址時(shí)，根據(jù)簇間收到的簇內(nèi)節(jié)點(diǎn)信息，可以判斷目的節(jié)點(diǎn)所處的簇ID，然后根據(jù)簇間路由查詢下一跳需要發(fā)往的簇節(jié)點(diǎn)，本節(jié)點(diǎn)發(fā)送到其對(duì)應(yīng)的本簇網(wǎng)關(guān)即可。簇內(nèi)節(jié)點(diǎn)只需要把業(yè)務(wù)發(fā)往由簇間路由確定的本簇網(wǎng)關(guān)，然后本簇網(wǎng)關(guān)把包發(fā)給對(duì)應(yīng)鄰簇網(wǎng)關(guān)，業(yè)務(wù)到鄰簇后繼續(xù)通過(guò)簇間路由確定需要發(fā)往的對(duì)應(yīng)網(wǎng)關(guān)，直到業(yè)務(wù)發(fā)到目的簇后，由網(wǎng)關(guān)發(fā)往目的節(jié)點(diǎn)。本簇間路由方案由于簇?cái)?shù)量有限，所以建立路由的過(guò)程簡(jiǎn)單方便，而且實(shí)現(xiàn)了業(yè)務(wù)直接發(fā)往網(wǎng)關(guān)，不需要簇首的參與，還可以在選舉網(wǎng)關(guān)時(shí)多選舉幾對(duì)來(lái)分?jǐn)偩W(wǎng)關(guān)的流量。

4 仿真及分析

本節(jié)用OPNET 仿真軟件進(jìn)行模擬建模，將本方案的分簇OLSR 路由協(xié)議和平面網(wǎng)絡(luò)架構(gòu)的標(biāo)準(zhǔn)OLSR 路由協(xié)議進(jìn)行對(duì)比。如圖5 所示，網(wǎng)內(nèi)共有128 個(gè)節(jié)點(diǎn)，在運(yùn)行標(biāo)準(zhǔn)OLSR 路由協(xié)議情況下，128 個(gè)節(jié)點(diǎn)不分簇，在運(yùn)行本方案路由情況下，128個(gè)節(jié)點(diǎn)分為4 個(gè)簇，每個(gè)簇32 個(gè)節(jié)點(diǎn)，兩者對(duì)比。

圖5 128 節(jié)點(diǎn)仿真分布

仿真結(jié)果如圖6 所示，對(duì)比兩種情況下網(wǎng)內(nèi)路由開(kāi)銷(xiāo)。仿真設(shè)置的10 s 開(kāi)始運(yùn)行路由，圖6 橫軸是運(yùn)行時(shí)間，總共運(yùn)行2分鐘，縱軸是全網(wǎng)路由開(kāi)銷(xiāo)，單位bits/s 表示每秒全網(wǎng)路由開(kāi)銷(xiāo)的比特?cái)?shù)。圖6上半部分表示平面網(wǎng)絡(luò)架構(gòu)下標(biāo)準(zhǔn)OLSR 的路由開(kāi)銷(xiāo)，路由運(yùn)行穩(wěn)定后路由開(kāi)銷(xiāo)穩(wěn)定在每秒20 萬(wàn)比特到每秒60 萬(wàn)比特之間。圖6 下半部分表示本方案的分簇OLSR 路由的開(kāi)銷(xiāo)，路由運(yùn)行穩(wěn)定后路由開(kāi)銷(xiāo)穩(wěn)定在接近每秒5 萬(wàn)比特。可以看出，運(yùn)用分簇網(wǎng)絡(luò)架構(gòu)的本方案相比傳統(tǒng)的平面網(wǎng)絡(luò)架構(gòu)的標(biāo)準(zhǔn)OLSR，能大幅度降低全網(wǎng)內(nèi)網(wǎng)絡(luò)開(kāi)銷(xiāo)，前者峰值僅為后者峰值的1/12。

圖6 仿真結(jié)果對(duì)比

5 結(jié)語(yǔ)

隨著MANET 中節(jié)點(diǎn)數(shù)越來(lái)越多，全網(wǎng)的路由開(kāi)銷(xiāo)越來(lái)越大，傳統(tǒng)的平面網(wǎng)絡(luò)架構(gòu)已經(jīng)不適用于MANET 網(wǎng)絡(luò)。本文針對(duì)這一情況，選擇分簇網(wǎng)絡(luò)架構(gòu)，提出了一種基于OLSR 的分簇路由協(xié)議，可以很好地降低大規(guī)模MANET 網(wǎng)內(nèi)路由開(kāi)銷(xiāo)。下一步研究需要考慮如何花費(fèi)較小時(shí)隙資源將簇內(nèi)成員信息和簇間鄰居關(guān)系廣播到全網(wǎng)。