黃 佳，趙 佳，劉小娟，汪偲怡

（武漢中原電子集團有限公司，湖北 武漢 430205）

0 引言

無線移動自組網(wǎng)（Mobile Ad-hoc Networks，MANETs）是一組由不需要中心管理和無固定網(wǎng)絡(luò)基礎(chǔ)設(shè)施的無線移動節(jié)點組成的多跳臨時自治系統(tǒng)。隨著現(xiàn)代通信對網(wǎng)絡(luò)移動性和組網(wǎng)靈活性的需求，無線自組網(wǎng)的應(yīng)用范圍大大擴展，特別適用于軍事通信領(lǐng)域。

MANETs 每個節(jié)點的地位是平等的。當(dāng)某些節(jié)點不在相互的傳播范圍內(nèi)時，為實現(xiàn)通信需要中間節(jié)點進(jìn)行中繼，這使得MANETs 中每個節(jié)點均是潛在的路由器，必要時能擔(dān)負(fù)起路由的功能。當(dāng)前無線移動網(wǎng)絡(luò)中，組網(wǎng)使用的路由協(xié)議主要分為兩類：被動式協(xié)議與主動式協(xié)議。

被動式路由協(xié)議即按需路由協(xié)議，包括源前驅(qū)動路由協(xié)議（Ad hoc On-Demand Distance Vector Routing，AODV）[1]、動態(tài)源路由協(xié)議（Dynamic Source Routing，DSR）[2]和臨時 預(yù)定路 由算法（Temporally Ordered Routing Algorithm，TORA）[3]等，這類協(xié)議在沒有數(shù)據(jù)傳輸時不需要交換控制信息。路由發(fā)現(xiàn)過程由源節(jié)點需要與新的目的節(jié)點進(jìn)行數(shù)據(jù)傳輸時啟動，包含兩步：首先源節(jié)點在網(wǎng)絡(luò)中泛洪路由請求包；然后目的節(jié)點若能收到請求包，則進(jìn)行單播回復(fù)，從而建立起路由。被動式路由協(xié)議需要大量的泛洪，一方面，給網(wǎng)絡(luò)帶來了大量的控制開銷，另一方面，路由建立的時延也較大。

主動式路由協(xié)議，如優(yōu)化鏈路狀態(tài)路由（Optimized Link State Routing，OLSR）[4]、基于拓?fù)鋸V播的反向路徑轉(zhuǎn)發(fā)（Topology Broadcast Based on Reverse Path Forwarding，TBRPF）[5]等，需要周期性地交互路由控制信息，在網(wǎng)絡(luò)中產(chǎn)生了數(shù)據(jù)流量外的額外流量，不過節(jié)點持續(xù)地檢測網(wǎng)絡(luò)拓?fù)涫沟脙?yōu)化控制流量成為可能，典型的如OLSR 使用多點中繼[6-7]（Multipoint Relay，MPR）技術(shù)來控制廣播信息的開銷。由于節(jié)點實時維護網(wǎng)絡(luò)的動態(tài)信息變化，主動式路由協(xié)議能在需要時迅速建立路由，從而降低數(shù)據(jù)的傳輸時延。

由于時延的要求，特別是考慮到戰(zhàn)場上態(tài)勢的瞬息變化，軍事通信領(lǐng)域往往傾向于采取主動式路由協(xié)議，因此OLSR 得到了廣泛的關(guān)注[8-9]。近年來，很多學(xué)者針對不同的應(yīng)用場景對MPR 選舉機制進(jìn)行了研究。

文獻(xiàn)[10]考慮鏈路穩(wěn)定問題和節(jié)點剩余能量（生存時間）因素，提出一種新的MPR 選擇算法，根據(jù)MPR集的更新頻繁程度控制拓?fù)淇刂疲═opology Control，TC）消息的洪泛周期，降低了網(wǎng)絡(luò)的開銷和能源的消耗。其針對傳統(tǒng)OLSR 協(xié)議應(yīng)用于無人機自組網(wǎng)中時可能會選取與源節(jié)點間鏈路連接易斷開并且剩余能量低的節(jié)點作為MPR 的不足。

文獻(xiàn)[11]對傳統(tǒng)的MPR 選取算法進(jìn)行改進(jìn)，改進(jìn)后的LEC-OLSR 協(xié)議中MPR 選取算法綜合考慮了節(jié)點間鏈路生存時間、節(jié)點剩余能量和節(jié)點深度這3 種影響因素，利用層次分析法構(gòu)建判斷矩陣精確地計算各影響因素的權(quán)重因子，并將它們的加權(quán)和作為MPR 節(jié)點的選取標(biāo)準(zhǔn)。

文獻(xiàn)[12]提出一種基于鏈路質(zhì)量的低開銷路由協(xié)議（LQLR-OLSR），針對飛行自組網(wǎng)（Flying Ad-Hoc Network，F(xiàn)ANET）中的MPR 集進(jìn)行優(yōu)化，減少冗余的MPR 節(jié)點，并修改基于期望傳輸計數(shù)（Expected Transmission Count，ETX），使其作為路由度量，融合正向傳輸成功率、反向傳輸成功率、鏈路分組大小和鏈路帶寬4 個特征，實現(xiàn)路由多徑自適應(yīng)。OPNET 仿真結(jié)果表明，F(xiàn)ANET 環(huán)境下LQLR-OLSR 在平均吞吐量、發(fā)包成功率、路由開銷和平均端到端時延性能方面明顯優(yōu)于GlobalOPOLSR[13]和OLSR。

傳統(tǒng)的MPR 算法只是減少了同一區(qū)域內(nèi)相同消息的泛洪，并沒有考慮網(wǎng)絡(luò)中新加入節(jié)點獲取全網(wǎng)拓?fù)湫畔⒌臅r間問題。文獻(xiàn)[14]針對該問題進(jìn)行了研究，并提出一種高效的MPR 選擇算法，該算法有三個步驟：首先，減少了部分拓?fù)淇刂疲═opology Control，TC）消息冗余問題；其次在選擇MPR 時考慮有效覆蓋面積，讓新加入的節(jié)點獲取全網(wǎng)拓?fù)湫畔⑺璧臅r間縮短；最后，考慮到移動性對網(wǎng)絡(luò)拓?fù)涞挠绊?，基于歷史信息預(yù)估下一時刻節(jié)點的位置，增強了鏈路的穩(wěn)定性。通過仿真，將改進(jìn)的MPR 算法與傳統(tǒng)算法進(jìn)行比較，端到端時延降低，數(shù)據(jù)包的傳遞成功率也有所提升。

基于優(yōu)化鏈路狀態(tài)路由協(xié)議的MPR 集選擇算法（GLOBALOPMPR）在網(wǎng)絡(luò)拓?fù)浞€(wěn)定的情況下能有效減少網(wǎng)絡(luò)中的MPR 節(jié)點數(shù)，但在網(wǎng)絡(luò)拓?fù)渥兓那闆r下會出現(xiàn)冗余。為此，文獻(xiàn)[15]提出一種能適應(yīng)網(wǎng)絡(luò)拓?fù)渥兓腗PR 集選擇算法（GLOBALADMPR）。該算法在不增加復(fù)雜度的情況下，通過將選定的MPR 節(jié)點再次遍歷去除冗余，從而得到更優(yōu)的MPR 節(jié)點集合。實驗結(jié)果表明，與GLOBALOPMPR 算法相比，GLOBALADMPR 算法能有效降低數(shù)據(jù)包傳輸時延及網(wǎng)絡(luò)開銷，提高網(wǎng)絡(luò)吞吐量。

OLSR 路由協(xié)議與一般的鏈路狀態(tài)協(xié)議相比，其采納了MPR 機制，在一定程度上抑制了網(wǎng)絡(luò)中廣播控制信息的洪泛，從而降低了網(wǎng)絡(luò)的控制開銷。但是這種機制是否會影響路由的魯棒性是值得探討的問題，目前的眾多研究成果都集中對MPR 算法進(jìn)行改進(jìn)，降低路由開銷，而忽略了MPR 選舉算法對網(wǎng)絡(luò)魯棒性的影響。本文設(shè)計了相應(yīng)的MPR選舉算法，并對MPR 覆蓋度對網(wǎng)絡(luò)性能的影響進(jìn)行了仿真分析。

本文的剩余部分內(nèi)容安排如下：第1 節(jié)簡要介紹OLSR 協(xié)議；第2 節(jié)介紹本文提出的MPR 覆蓋度算法；第3 節(jié)是仿真與分析；第4 節(jié)總結(jié)全文。

1 OLSR 協(xié)議

OLSR 是一種鏈路狀態(tài)協(xié)議，本節(jié)首先對鏈路狀態(tài)協(xié)議進(jìn)行介紹。在鏈路狀態(tài)協(xié)議中，MANETs中的兩個節(jié)點能監(jiān)聽到彼此，則稱這對節(jié)點間存在鏈路。鑒于單向鏈路使用的協(xié)議不同于雙向鏈路，本文重點研究雙向鏈路下的協(xié)議，故略掉單向鏈路的介紹。多跳的數(shù)據(jù)傳輸由路徑上的各個節(jié)點之間的鏈路組成。鏈路狀態(tài)協(xié)議中每個節(jié)點都獲知網(wǎng)絡(luò)中存在的鏈路，從而計算出到網(wǎng)絡(luò)各個節(jié)點的最短路徑鏈路，這得益于每個節(jié)點都必須執(zhí)行下述兩個過程。

（1）鄰居發(fā)現(xiàn)：探測毗鄰鏈路。最普遍的鄰居發(fā)現(xiàn)機制是周期性地在一跳范圍內(nèi)廣播HELLO包，其中HELLO 包包含該節(jié)點所監(jiān)聽到的鄰居。通過對收到的HELLO 包進(jìn)行解析，并將其和本地存儲的鄰居鏈路信息進(jìn)行對比，即可獲得鄰接的雙向鏈路。

（2）拓?fù)鋸V播：在整個網(wǎng)絡(luò)中將重要的鄰接鏈路信息廣而告之。初始簡單的鏈路狀態(tài)協(xié)議將TC 包在整個網(wǎng)絡(luò)中進(jìn)行泛洪，其中TC 包中包含該節(jié)點與其所有鄰居節(jié)點之間的鏈路信息。在泛洪中，通過TC 包的序列號避免同一個節(jié)點的反復(fù)轉(zhuǎn)發(fā)。在包傳輸不出錯的情況下，這種機制使得TC 包的前傳次數(shù)等于網(wǎng)絡(luò)中的節(jié)點數(shù)目。

若假設(shè)HELLO 包和TC 包的傳輸率分別為α和β，那么如圖1（a）所示，其中圓圈表示節(jié)點，線段表示TC 包的傳播途徑，以包為單位的控制開銷為：

為了優(yōu)化網(wǎng)絡(luò)中的控制開銷，OLSR 應(yīng)運而生。OLSR 主要通過選擇MPR 節(jié)點的方式進(jìn)行控制包的轉(zhuǎn)發(fā)，減小控制開銷，其中MPR 節(jié)點為所考察節(jié)點的一跳鄰居節(jié)點的子集，且該子集能夠覆蓋到該考察節(jié)點的所有二跳節(jié)點。具體地，MPR 對TC 包進(jìn)行了如下兩種方式的優(yōu)化。

（1）TC 包產(chǎn)生優(yōu)化。對于TC 消息的產(chǎn)生優(yōu)化，存在兩種方式：一種是只在MPR 節(jié)點而非網(wǎng)絡(luò)中所有節(jié)點產(chǎn)生TC 包；另一種優(yōu)化是在MPR 節(jié)點產(chǎn)生的TC 包中只包括MPR selectors，這種優(yōu)化的效果取決于網(wǎng)絡(luò)拓?fù)涞某砻艹潭取?/p>

（2）TC 包廣播優(yōu)化。對于TC 包的廣播，只通過MPR 節(jié)點進(jìn)行，即MPR 節(jié)點只轉(zhuǎn)發(fā)來自自己的MPR selectors 的TC 消息。值得注意的是，這里的MPR selectors 同時也是其他節(jié)點選擇出來的MPR 節(jié)點（因為如上條所述，只有MPR 節(jié)點產(chǎn)生TC 包）。

類似的，若假設(shè)HELLO 包和TC 包的傳輸率分別為α和β，那么如圖1（b）所示，其中圓圈表示節(jié)點，黑色圓圈表示選擇出的MPR 節(jié)點，線段表示TC 包的傳播途徑，以包為單位的控制開銷為：

式中：M為網(wǎng)絡(luò)中總的MPR 個數(shù)，M

從這個意義上講，MPR 集合越小，越有利于網(wǎng)絡(luò)中控制開銷的下降。然而，Andreas[2]提出一種擔(dān)憂，這種優(yōu)化可能是以犧牲路由協(xié)議的魯棒性為代價的。RFC3626 中指出，MPR 節(jié)點的選擇需要保證二跳鄰居節(jié)點中至少有一個是MPR 覆蓋的。那么MPR 節(jié)點應(yīng)該怎樣選取以及以何種程度覆蓋二跳節(jié)點呢？

首先，引入MPR 覆蓋度的概念，MPR 覆蓋度定義為任一嚴(yán)格二跳鄰居對應(yīng)的MPR 節(jié)點數(shù)目。MPR 覆蓋度若為m，則任一嚴(yán)格二跳鄰居節(jié)點對應(yīng)的MPR 節(jié)點數(shù)為m。如圖2 所示，其中圖2（a）中MPR 覆蓋度為1，圖2（b）中MPR 覆蓋度為2，黑色節(jié)點為選擇的MPR 節(jié)點。這里要指出的是，不是所有的二跳鄰居節(jié)點都有兩個MPR 節(jié)點進(jìn)行覆蓋，因為有的二跳節(jié)點由于通信范圍的限制，只有一個一跳節(jié)點連通。

圖2 MPR 覆蓋度

其次，為了分析MANETs 中MPR 覆蓋度對網(wǎng)絡(luò)的路由性能的影響，本文提出了覆蓋度可伸縮的MPR 選擇算法。

2 MPR 算法

尋找最優(yōu)的MPR 集合被證明是一個NP 完全問題，對此出現(xiàn)了多種啟發(fā)式算法來尋找OLSR 協(xié)議的MPR 集合。

RFC3626 中提出了一種簡單的啟發(fā)式MPR 選擇算法。該算法選取的MPR 集合能夠覆蓋所有的對稱嚴(yán)格的二跳鄰居，且MPR 節(jié)點的意愿度不是WILL_NEVER。節(jié)點的意愿度是指節(jié)點愿意成為MPR 的程度。影響節(jié)點意愿度的因素較多，MANETs 中主要考察節(jié)點的剩余能量，這是因為節(jié)點的能量需要通過電池來提供，一般是有限的，而成為MPR 意味著更多的能量消耗。

具體地，MPR 選擇算法使用到的參數(shù)見表1。

表1 網(wǎng)絡(luò)描述參數(shù)

該啟發(fā)式算法的流程如圖3所示，具體步驟如下。

圖3 MPR 選擇流程

（1）將節(jié)點意愿度N_willingness為WILL_ALWAYS的一跳鄰居節(jié)點設(shè)置為MPR 節(jié)點。

（2）對所有的一跳鄰居計算D(y)。

（3）對于只有一條鏈路可達(dá)的N2節(jié)點，將其鏈接的一個鄰居節(jié)點設(shè)置為MPR 節(jié)點。

（4）對于N2中還未被至少一個MPR 節(jié)點覆蓋到的節(jié)點執(zhí)行如下操作：對于N中的每個節(jié)點，計算其可達(dá)性，即該節(jié)點可以鏈接到剩余N2集合中的節(jié)點數(shù)目；然后依次依據(jù)N中節(jié)點的N_willingness、可達(dá)性和D(y)選擇MPR。具體地，首先選擇N_willingness高且可達(dá)性非零的節(jié)點；其次若N_willingness相同，選擇可達(dá)性高的；若可達(dá)性也一致，選擇D(y)較高的。移除已選MPR 節(jié)點覆蓋到的N2 節(jié)點，重復(fù)執(zhí)行該步驟，直到N2 空為止。

（5）MPR 集合優(yōu)化。依N_willingness從小到大的次序進(jìn)行MPR 集的遍歷。在每一步中，若節(jié)點移除后，N2 節(jié)點仍然被全部覆蓋，且當(dāng)前考察節(jié)點的willingness不等于WILL_ALWAYS，則將該節(jié)點從MPR 集中移除。

為了探索MPR 覆蓋度對于網(wǎng)絡(luò)路由性能的影響，本文遵循上述啟發(fā)式算法選擇MPR 的思想，即盡可能保留N_willingness和度數(shù)高的節(jié)點為MPR 節(jié)點，設(shè)計了MPR 覆蓋度參數(shù)可變的MPR 算法，該算法的流程如圖4 所示，具體步驟如下。

圖4 MPR 覆蓋度可變的MPR 選取流程

（1）求取當(dāng)前節(jié)點的嚴(yán)格二跳鄰居集合，并將嚴(yán)格二跳鄰居的MPR 覆蓋度設(shè)置為對應(yīng)一跳鄰居的數(shù)目，且這些一跳鄰居均被設(shè)置為MPR 候選節(jié)點。

（2）對所有的一跳鄰居計算D(y)。

（3）依下列規(guī)則對MPR 候選節(jié)點集合進(jìn)行排除：依N_willingness從小到大和度數(shù)從小到大的順序?qū)PR 候選節(jié)點進(jìn)行遍歷，若MPR 候選節(jié)點對應(yīng)的嚴(yán)格二跳鄰居的MPR 覆蓋度均大于給定MPR覆蓋度，則刪除該MPR 候選節(jié)點，并將該MPR 候選節(jié)點對應(yīng)的嚴(yán)格二跳鄰居的MPR 覆蓋度減去1；否則保留該節(jié)點。

算法的有效性分析：當(dāng)MPR 覆蓋度取1 時，本文算法選取的MPR 節(jié)點與RFC3626 算法選取的MPR 節(jié)點一致。

算法復(fù)雜度分析：

（1）計算嚴(yán)格兩跳鄰居集合時，首先遍歷二跳鄰居節(jié)點，然后遍歷該鄰居節(jié)點的一跳鄰居節(jié)點，因此MPR 覆蓋度參數(shù)可變的MPR 算法的步驟（1）的算法復(fù)雜度為σ(n2)。

（2）計算所有一跳鄰居度數(shù)，首先遍歷一跳鄰居節(jié)點，然后遍歷統(tǒng)計該節(jié)點的嚴(yán)格兩跳鄰居節(jié)點的個數(shù)，因此MPR 覆蓋度參數(shù)可變的MPR 算法的步驟（2）的算法復(fù)雜度為σ(n2)。

（3）對已經(jīng)選出的MPR 候選節(jié)點按一定規(guī)則進(jìn)行刪除。首先依N_willingness從小到大和度數(shù)從小到大遍歷MPR 候選節(jié)點；其次遍歷該候選節(jié)點的嚴(yán)格兩跳節(jié)點，判斷該兩跳節(jié)點的MPR 覆蓋度是否都大于給定的MPR 覆蓋度。MPR 覆蓋度參數(shù)可變的MPR 算法的步驟（3）的復(fù)雜度為σ(M×N×n2)，其中M為N_willingness的等級個數(shù)，N為最大的度數(shù)，在有限規(guī)模的網(wǎng)絡(luò)中M和N都為常數(shù)，因此MPR 覆蓋度參數(shù)可變的MPR 算法的步驟（3）的算法復(fù)雜度為σ(n2)。

算法的復(fù)雜度為3 個步驟的復(fù)雜度相加：

RFC3626 中MPR 選擇算法的復(fù)雜度也為σ(n2)，本算法與之相比，復(fù)雜度相當(dāng)。

3 仿真與分析

為了驗證MPR 覆蓋度對于網(wǎng)絡(luò)路由性能的影響，本節(jié)在OPNET 網(wǎng)絡(luò)仿真軟件中進(jìn)行了仿真實驗。

具體地，仿真中用到的參數(shù)如表2 所示。

表2 網(wǎng)絡(luò)仿真參數(shù)

分別對同一網(wǎng)絡(luò)拓?fù)淙鐖D5 的靜態(tài)場景和如 圖6 的動態(tài)場景進(jìn)行了聯(lián)合測試。其中，前100 s為靜態(tài)場景，每個節(jié)點保持靜止；100 s 時動態(tài)場景中兩個節(jié)點以極快的速度運動出鄰居節(jié)點的通信范圍；100 s 后剩余節(jié)點組成的網(wǎng)絡(luò)為節(jié)點規(guī)模稍小的靜態(tài)場景。

圖5 靜態(tài)場景

圖6 動態(tài)場景

路由算法的衡量參數(shù)主要分為路由控制包開銷和路由收斂時間，其中路由控制包開銷主要是HELLO 包和TC 包，而HELLO 包每個節(jié)點都產(chǎn)生且只在一跳范圍內(nèi)廣播，網(wǎng)絡(luò)拓?fù)涔潭ê驢ELLO包的開銷也相對穩(wěn)定，則TC 包是主要的比較對象。如圖7 所示，隨著MPR 覆蓋度的上升，路由控制包開銷也隨之增加。對比100 s 前后，可以發(fā)現(xiàn)隨著網(wǎng)絡(luò)規(guī)模的降低（兩個MPR 節(jié)點移出），路由控制開銷也隨之降低。

圖7 路由開銷

路由收斂時間考察網(wǎng)絡(luò)初始化或網(wǎng)絡(luò)拓?fù)浒l(fā)生變化后，重新獲得路由的時間。如圖8 所示，當(dāng)網(wǎng)絡(luò)初始和節(jié)點快速移出網(wǎng)絡(luò)中其他節(jié)點的通信范圍這兩種情況下，隨著MPR 覆蓋度的上升，路由收斂所需時間減少。

圖8 路由表計算

綜上所述，MPR 覆蓋度的增加，雖然一定程度上增大了網(wǎng)絡(luò)中的控制開銷，但是加速了路由的收斂。因此對于拓?fù)渥兓l繁的網(wǎng)絡(luò)，建議保留一定的MPR 冗余，以增加網(wǎng)絡(luò)控制開銷的代價，保證路由的收斂和數(shù)據(jù)的正常傳輸，提高網(wǎng)絡(luò)的 健壯性。

4 結(jié)語

路由開銷的控制優(yōu)化是MANETs 中的一個關(guān)鍵問題。本文從MPR 覆蓋度入手，設(shè)計了MPR 尋找算法，并通過仿真的手段分析了不同的MPR 覆蓋度下，MANETs 網(wǎng)絡(luò)的性能。分析結(jié)果表明，隨著MPR 覆蓋度的增大，在路由開銷也會增加的代價下，降低了路由收斂時間，一定程度上保證了MANETs的健壯性。

基于以上分析，對于拓?fù)鋭討B(tài)變化的網(wǎng)絡(luò)，建議將MPR覆蓋度設(shè)置較高，以便促進(jìn)路由快速收斂。