OLSR 協議MPR 覆蓋度對網絡性能的影響分析*

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

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

0 引言

無線移動自組網（Mobile Ad-hoc Networks，MANETs）是一組由不需要中心管理和無固定網絡基礎設施的無線移動節點組成的多跳臨時自治系統。隨著現代通信對網絡移動性和組網靈活性的需求，無線自組網的應用范圍大大擴展，特別適用于軍事通信領域。

MANETs 每個節點的地位是平等的。當某些節點不在相互的傳播范圍內時，為實現通信需要中間節點進行中繼，這使得MANETs 中每個節點均是潛在的路由器，必要時能擔負起路由的功能。當前無線移動網絡中，組網使用的路由協議主要分為兩類：被動式協議與主動式協議。

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

主動式路由協議，如優化鏈路狀態路由（Optimized Link State Routing，OLSR）[4]、基于拓撲廣播的反向路徑轉發（Topology Broadcast Based on Reverse Path Forwarding，TBRPF）[5]等，需要周期性地交互路由控制信息，在網絡中產生了數據流量外的額外流量，不過節點持續地檢測網絡拓撲使得優化控制流量成為可能，典型的如OLSR 使用多點中繼[6-7]（Multipoint Relay，MPR）技術來控制廣播信息的開銷。由于節點實時維護網絡的動態信息變化，主動式路由協議能在需要時迅速建立路由，從而降低數據的傳輸時延。

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

文獻[10]考慮鏈路穩定問題和節點剩余能量（生存時間）因素，提出一種新的MPR 選擇算法，根據MPR集的更新頻繁程度控制拓撲控制（Topology Control，TC）消息的洪泛周期，降低了網絡的開銷和能源的消耗。其針對傳統OLSR 協議應用于無人機自組網中時可能會選取與源節點間鏈路連接易斷開并且剩余能量低的節點作為MPR 的不足。

文獻[11]對傳統的MPR 選取算法進行改進，改進后的LEC-OLSR 協議中MPR 選取算法綜合考慮了節點間鏈路生存時間、節點剩余能量和節點深度這3 種影響因素，利用層次分析法構建判斷矩陣精確地計算各影響因素的權重因子，并將它們的加權和作為MPR 節點的選取標準。

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

傳統的MPR 算法只是減少了同一區域內相同消息的泛洪，并沒有考慮網絡中新加入節點獲取全網拓撲信息的時間問題。文獻[14]針對該問題進行了研究，并提出一種高效的MPR 選擇算法，該算法有三個步驟：首先，減少了部分拓撲控制（Topology Control，TC）消息冗余問題；其次在選擇MPR 時考慮有效覆蓋面積，讓新加入的節點獲取全網拓撲信息所需的時間縮短；最后，考慮到移動性對網絡拓撲的影響，基于歷史信息預估下一時刻節點的位置，增強了鏈路的穩定性。通過仿真，將改進的MPR 算法與傳統算法進行比較，端到端時延降低，數據包的傳遞成功率也有所提升。

基于優化鏈路狀態路由協議的MPR 集選擇算法（GLOBALOPMPR）在網絡拓撲穩定的情況下能有效減少網絡中的MPR 節點數，但在網絡拓撲變化的情況下會出現冗余。為此，文獻[15]提出一種能適應網絡拓撲變化的MPR 集選擇算法（GLOBALADMPR）。該算法在不增加復雜度的情況下，通過將選定的MPR 節點再次遍歷去除冗余，從而得到更優的MPR 節點集合。實驗結果表明，與GLOBALOPMPR 算法相比，GLOBALADMPR 算法能有效降低數據包傳輸時延及網絡開銷，提高網絡吞吐量。

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

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

1 OLSR 協議

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

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

（2）拓撲廣播：在整個網絡中將重要的鄰接鏈路信息廣而告之。初始簡單的鏈路狀態協議將TC 包在整個網絡中進行泛洪，其中TC 包中包含該節點與其所有鄰居節點之間的鏈路信息。在泛洪中，通過TC 包的序列號避免同一個節點的反復轉發。在包傳輸不出錯的情況下，這種機制使得TC 包的前傳次數等于網絡中的節點數目。

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

為了優化網絡中的控制開銷，OLSR 應運而生。OLSR 主要通過選擇MPR 節點的方式進行控制包的轉發，減小控制開銷，其中MPR 節點為所考察節點的一跳鄰居節點的子集，且該子集能夠覆蓋到該考察節點的所有二跳節點。具體地，MPR 對TC 包進行了如下兩種方式的優化。

（1）TC 包產生優化。對于TC 消息的產生優化，存在兩種方式：一種是只在MPR 節點而非網絡中所有節點產生TC 包；另一種優化是在MPR 節點產生的TC 包中只包括MPR selectors，這種優化的效果取決于網絡拓撲的稠密程度。

（2）TC 包廣播優化。對于TC 包的廣播，只通過MPR 節點進行，即MPR 節點只轉發來自自己的MPR selectors 的TC 消息。值得注意的是，這里的MPR selectors 同時也是其他節點選擇出來的MPR 節點（因為如上條所述，只有MPR 節點產生TC 包）。

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

式中：M為網絡中總的MPR 個數，M

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

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

圖2 MPR 覆蓋度

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

2 MPR 算法

尋找最優的MPR 集合被證明是一個NP 完全問題，對此出現了多種啟發式算法來尋找OLSR 協議的MPR 集合。

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

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

表1 網絡描述參數

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

圖3 MPR 選擇流程

（1）將節點意愿度N_willingness為WILL_ALWAYS的一跳鄰居節點設置為MPR 節點。

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

（3）對于只有一條鏈路可達的N2節點，將其鏈接的一個鄰居節點設置為MPR 節點。

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

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

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

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

（1）求取當前節點的嚴格二跳鄰居集合，并將嚴格二跳鄰居的MPR 覆蓋度設置為對應一跳鄰居的數目，且這些一跳鄰居均被設置為MPR 候選節點。

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

（3）依下列規則對MPR 候選節點集合進行排除：依N_willingness從小到大和度數從小到大的順序對MPR 候選節點進行遍歷，若MPR 候選節點對應的嚴格二跳鄰居的MPR 覆蓋度均大于給定MPR覆蓋度，則刪除該MPR 候選節點，并將該MPR 候選節點對應的嚴格二跳鄰居的MPR 覆蓋度減去1；否則保留該節點。

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

算法復雜度分析：

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

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

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

算法的復雜度為3 個步驟的復雜度相加：

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

3 仿真與分析

為了驗證MPR 覆蓋度對于網絡路由性能的影響，本節在OPNET 網絡仿真軟件中進行了仿真實驗。

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

表2 網絡仿真參數

分別對同一網絡拓撲如圖5 的靜態場景和如 圖6 的動態場景進行了聯合測試。其中，前100 s為靜態場景，每個節點保持靜止；100 s 時動態場景中兩個節點以極快的速度運動出鄰居節點的通信范圍；100 s 后剩余節點組成的網絡為節點規模稍小的靜態場景。

圖5 靜態場景

圖6 動態場景

路由算法的衡量參數主要分為路由控制包開銷和路由收斂時間，其中路由控制包開銷主要是HELLO 包和TC 包，而HELLO 包每個節點都產生且只在一跳范圍內廣播，網絡拓撲固定后HELLO包的開銷也相對穩定，則TC 包是主要的比較對象。如圖7 所示，隨著MPR 覆蓋度的上升，路由控制包開銷也隨之增加。對比100 s 前后，可以發現隨著網絡規模的降低（兩個MPR 節點移出），路由控制開銷也隨之降低。

圖7 路由開銷

路由收斂時間考察網絡初始化或網絡拓撲發生變化后，重新獲得路由的時間。如圖8 所示，當網絡初始和節點快速移出網絡中其他節點的通信范圍這兩種情況下，隨著MPR 覆蓋度的上升，路由收斂所需時間減少。

圖8 路由表計算

綜上所述，MPR 覆蓋度的增加，雖然一定程度上增大了網絡中的控制開銷，但是加速了路由的收斂。因此對于拓撲變化頻繁的網絡，建議保留一定的MPR 冗余，以增加網絡控制開銷的代價，保證路由的收斂和數據的正常傳輸，提高網絡的 健壯性。

4 結語

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

基于以上分析，對于拓撲動態變化的網絡，建議將MPR覆蓋度設置較高，以便促進路由快速收斂。