高效的MPR選擇算法

摘 要： OLSR（optimized link state routing）協議中最重要的功能之一是多點中繼（multi point relays，MPR）節點的選擇，該協議中路由的計算就要依靠MPR選擇相關表項。傳統的MPR算法只是減少了同一區域內相同消息的泛洪，并沒有考慮網絡中新加入節點獲取全網拓撲信息的時間問題。針對該問題進行了研究并提出一種高效的MPR選擇算法，該算法有三個步驟：首先減少了部分拓撲控制（topology control，TC）消息冗余問題;然后選擇MPR時考慮有效覆蓋面積讓新加入的節點獲取全網拓撲信息所需的時間縮短;最后考慮到移動性對網絡拓撲的影響，基于歷史信息預估下一時刻節點的位置，增強了鏈路的穩定性。通過仿真，將改進的MPR算法與傳統算法比較，端到端時延降低，數據包的傳遞成功率也有所提升。

關鍵詞： OLSR協議； 多點中繼； 有效覆蓋面積

中圖分類號： TP393"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-038-0221-05

doi：10.19734/j.issn.1001-3695.2021.06.0251

MPR algorithm for faster acquisition of network topology

Yang Jie， Ren Zhi， Zhu Qizheng

（School of Communication amp; Information Engineering， Chongqing University of Posts amp; Telecommunications， Chongqing 400065， China）

Abstract： One of the most important functions in the OLSR （optimized link state routing） protocol is the selection of multipoint relays （MPR） nodes. The routing calculations in this protocol rely on MPR to select related entries. The traditional MPR algorithm only reduces the flooding of the same message in the same area， and does not consider the time for newly added nodes in the network to obtain the topology information of the entire network. This paper studied this problem and proposed an efficient MPR selection algorithm. The algorithm had three steps： firstly， it reduced the problem of partial topology control （TC） message redundancy. And then it considered the effective coverage area when selecting MPR so that newly added nodes could obtain the entire network. It shortened the time required for topology information. Finally， considering the impact of mobility on the network topology， it estimated the location of the node at the next moment based on historical information， thereby enhancing the stability of the link. Through simulation， comparing the improved MPR algorithm with the traditional MPR algorithm， the end-to-end delay is reduced， and the success rate of data packet delivery is also improved.

Key words： OLSR protocol; multipoint relay; effective coverage area

0 引言

無線自組網［1，2］是一種不依賴任何基礎設施，可以隨時隨地建立臨時自治系統，非常適用于軍事行動、搶險救災、偏遠地區等的通信［3～5］。無線自組網的核心是路由協議，根據是否主動獲取全網拓撲信息分為主動路由協議、按需路由協議和混合路由協議。主動路由協議是指網絡中每個節點都會周期性獲取全網拓撲信息建立路由，而按需路由協議則是發送數據需要路由的節點才去全網找路，不需要周期性地獲取全網拓撲信息。本文主要研究主動路由協議中的OLSR協議［6～8］，該協議具有時延低、吞吐量高等特點。

OLSR協議的功能有鏈路檢測、鄰居探測、MPR計算、拓撲擴散以及路由計算幾部分。其中MPR計算可以說是一個橋梁作用，將鏈路檢測和鄰居探測的信息用于計算MPR，然后用與MPR相關信息填充TC消息，最后用TC消息構成全網的拓撲信息來計算路由。因此對MPR的研究是很有必要的，國內外的學者從不同方面對MPR進行了研究。

文獻［9］提出了一種在選擇MPR意愿時考慮剩余能量及其節點密度的新算法，該方法減少了節點中的拓撲控制流量并提高了傳遞數據包的成功率。但是該方法中對于測量剩余能量不是很完善，還有待提高。

文獻［10］的主要思想是在選擇節點的MPR集并進行路由計算時，對節點的可達性和剩余能量之間實現動態加權比。該方法可以有效地在一跳鄰居中選擇下一跳路由，確保了整個網絡的能量平衡，并延長了使用壽命。

文獻［11］基于車載自組織網絡高動態性，提出了一種基于集群的專家協作，估算可靠穩定的路徑算法，提高了MPR方案維護路由壽命長的能力，通過信號強度信標和節點的移動性程度自適應地選擇最可持續的路徑來增強網絡可伸縮性，從而顯著減小路由表重新計算過程的大小。但是該方法引入了多種度量，增加了額外的開銷。

文獻［12］基于QoS約束條件增強了路由決策，提出了鏈路定義的OLSR，在選擇MPR集時考慮了鏈路的質量。該方法的性能優于普通方法，但這種方法在減少鏈路故障以及確保成功重發數據包方面沒有效果。

文獻［13］將感知信令技術的功能引入到一組選定的節點作為合適的成員節點。此技術作為減少控制拓撲開銷并有效利用可用帶寬的方法，應用于OLSR的MPR選擇，其在延遲、數據包丟失、信道利用率、數據包傳送率和吞吐量方面增強了路由性能。但是，文獻[13]并沒有考慮節點移動的影響。

大部分學者都是從鏈路的穩定性或者能量甚至控制開銷等方面入手，但是對于需要及時通信的節點來說并沒有任何的幫助，而且對于新節點還會有一段空白的時間，在這個時間段內，發送數據是找不到路由的。而本文主要是從新加入節點獲取全網拓撲信息的時間著手，提出了一種高效的MPR選擇算法。通過選舉成為MPR概率更大的節點為MPR，減少了頻繁切換MPR。讓新加入的節點能更快地獲取全網的拓撲信息，能更快速地進行通信，從而提高成功率。而且本文也考慮到了冗余的TC消息，節點的移動對整個網絡的影響，在該算法中優化了部分冗余，同時根據歷史信息預估了節點下一時刻的位置，選擇更穩定的節點作為MPR，提升了網絡的整體性能。

1 傳統MPR選擇算法的問題分析

1.1 存在冗余

傳統MPR算法選擇出來的MPR集可能不是最優的，即某些節點可能會收到來自不同節點轉發的相同TC消息。如圖1（a）所示，根據傳統MPR算法首先選擇這樣的節點為MPR節點，其對應某個兩跳鄰居節點只能通過唯一一個一跳鄰居節點中繼。圖1（a）中的節點C滿足該要求，即節點S要想與節點G通信只有通過節點C進行轉發，把節點C加入MPR集。然后將節點C對應的兩跳鄰居節點刪除，即圖1中的節點F和G。經過此次操作后，節點S對應的一跳鄰居還需要進行MPR選擇的節點如圖1（b）所示。此時，已經不存在孤立的兩跳鄰居節點了，因此需要使用覆蓋度（覆蓋度是指一跳鄰居節點對應覆蓋的兩跳鄰居節點的數量）作為指標選擇MPR。因為節點A和B的覆蓋度相同，傳統MPR算法選擇的是連接度（連接度是指初始時一跳鄰居節點對應覆蓋的兩跳鄰居節點的數量，也稱初始覆蓋度）更大的節點為MPR節點，即節點B。此時，節點S對應的兩跳鄰居集為空，MPR的計算到此結束。綜上，節點S的MPR集是{B，C}，然而當節點B和C接收到其他MPR節點發送過來的TC消息時，會對該消息進行轉發，此時節點F就會收到來自節點B和C轉發來的相同TC消息，造成冗余。

1.2 新節點獲取全網拓撲的時間過長

傳統MPR選擇算法在兩個節點的覆蓋度和連接度一樣的情況下，只是隨機地選擇了其中一個節點作為MPR節點，并沒有考慮其他因素，會出現下面這種情況。當新加入一個節點時，如果新加入節點對應的一跳鄰居節點本來就是MPR節點，那么新加入的節點就能更快獲得全網拓撲信息。如果其對應的一跳鄰居節點不是MPR節點，那么新加入的節點要得到全網的拓撲信息，只有其兩跳鄰居節點重新計算MPR，并選其一跳鄰居節點為MPR，且將該信息告知其一跳鄰居節點之后才能得到。這一時間段內是得不到全網拓撲信息的，如果在這段時間內發送數據包，會出現找不到路由的情況。

如圖2所示，新加入的節點I是節點S的兩跳鄰居節點，而節點S對應的一跳鄰居節點也是節點I的一跳鄰居只有節點B。由圖2可知，節點A和B的覆蓋度、連接度都是一樣的，根據傳統MPR選擇算法，會從這兩個節點中隨機選擇一個作為MPR，將出現以下兩種情況。

情況1 若選擇節點A作為MPR節點，那么當節點I和B經過三次握手建立好雙向鏈路后，節點S計算MPR時其MPR集就會發生變化，而且在節點B被選為MPR之前，節點I都不能得到全網的拓撲信息。比如在這之前節點S發送TC消息，但是此時節點B不是MPR節點，只能接收不能轉發該消息，因此節點I收不到任何的TC消息。從新節點加入開始到選擇節點B作為MPR的時間，根據不同的情況就會有很大的差異。

情況2 若選擇節點B為MPR，不管節點I加入前還是加入后節點B都是MPR節點，只要節點B收到TC消息轉發或者發送自己的TC消息，新加入的節點I就能得到從節點B發來的拓撲信息（只要節點B到I這條鏈路沒問題）。當節點I和B建立好雙向鏈路后，就可以建立路由表并進行通信。

根據情況1和2可知，新加入的節點要獲取全網的拓撲信息在時間上有很大的差異。首先講述一下從新節點的加入到選其一跳鄰居節點為MPR的過程。如圖3所示，節點I是加入網絡的新節點，首先向其周圍發送一個空的握手（HELLO）消息，然后節點B收到此消息，并在自己的本地相關表中將節點I標記為非對稱節點，節點B發送HELLO消息（該消息中包含了節點I是非對稱的信息），接著節點I收到此消息將節點B標記為對稱節點（因為收到該消息，節點I就會將節點B標記為非對稱節點，且該消息里面又包含了節點I是非對稱節點的信息，所以最終將節點B標記為對稱節點）。節點I將含有節點B是對稱節點的信息放入HELLO消息里面發送出去，當節點B收到該消息后，將節點I標記為對稱節點。節點B發送HELLO消息里面就會包含節點I是對稱節點的信息。最后節點S收到節點B發送的HELLO消息，當節點S計算MPR時，就會選擇節點B為MPR。節點S發送HELLO消息時，里面就會包含選擇節點B為MPR的信息，當節點B收到該消息時就會知道自己被選為MPR了，就可以周期性地發送TC消息并轉發其他節點發來的TC消息。根據發送接收HELLO消息選擇節點B為MPR的時間有所差異，大致可以分為圖3中兩種比較極端的情況，其中圖（a）表示最少需要的時間，而圖（b）表示最多需要的時間。

在圖3（a）中，①過程結束，節點B收到HELLO消息后剛好到達節點B發送HELLO消息的時間;②過程結束時，節點I收到HELLO消息，此時還沒有到達發送HELLO的時間，即過程①和②總共用的時間小于一個HELLO消息周期;接著，過程③～⑤也是剛好銜接，中間沒有任何時間間隙或者說⑤在③后面一點點此時間間隙可忽略不計，同理，過程⑤⑥也是。因此，可以得到選擇節點B為MPR的最少時間，如式（1）所示。

t1=T+τ1+τ2+τ3（1）

其中：t1是指節點I發送HELLO消息開始到節點B知道自己被選為MPR的時間；T是指發送HELLO消息的周期；τ1、τ2以及τ3都是指從一個節點內部生成HELLO消息開始到另一個節點接收到該消息的時間，τ1是指過程③所用的時間，τ2是指過程⑤所用的時間，τ3是指過程⑥所用的時間。根據不同節點周圍的拓撲不同，自身節點內部的消息個數不同，這三個參數也存在著差異。

在圖3（b）中過程①節點I發送HELLO消息，此時節點B收到該消息時剛好錯過發送HELLO的時間，即要等待一個周期節點B才會發送HELLO消息，同理，該圖中的其他過程也是如此。因此，可以得到選擇節點B為MPR需要最多的時間，如式（2）所示。

t2=4T+τ1+τ2+τ3+τ4+τ5（2）

其中：τ1是指過程①所用的時間；τ2是指過程②所用的時間；τ3是指過程③所用的時間；τ4是指過程⑤所用的時間；τ5是指過程⑥所用的時間。

根據上面的分析，一個新節點能夠獲取全網拓撲信息的時間至少需要t1，最多需要t2，而且根據不同的網絡應用場景以及節點設備性能等方面各種τ的值也有所變化。如果該新節點在這個時間段里面需要通信，這時會出現找不到路由的情況，造成無法通信。

1.3 拓撲動態變化導致鏈路失效的問題

如圖2所示，節點A和B只是隨機的選擇一個，沒有考慮鏈路持續時間，容易出現路由表中存在相關路由，但是此時的路由實際上是無效的。若節點B相對于節點S來說是運動的，但隨機選擇的MPR節點就是節點B，那么在后面的某一個時刻，節點B會運動出節點S的一跳范圍。在那個時刻節點S還沒有得到節點B的相關信息，此時還認為它是自己的一跳鄰居， MPR集也就不會有什么變化。若節點H要向節點E通信，會發送數據包給節點S，然后節點S搜索路由表查找路由，就會找到下一跳為節點B，但是此時實際上節點S和B之間已經不存在鏈路了，因此該數據包是不會達到目的節點的。

2 RFC-MPR選擇算法

為了解決上述問題，提出了一種RFC-MPR選擇算法，該算法能降低切換MPR的頻率，讓選擇的MPR節點成為新加入節點一跳鄰居的概率更大一些，并且提前預測鏈路的穩定性，同時在該算法里面加入了減少冗余的步驟。

2.1 有效覆蓋面積

為了解決新節點獲取全網拓撲信息時間過長的問題，本文提出了有效覆蓋面積的概念。如圖2所示，當節點A和B相對于節點S是靜止的，并且節點A和B的覆蓋度、連接度是一樣的情況下，選擇有效覆蓋面積最大的節點為MPR，即新加入的節點是其一跳鄰居相對概率更大的節點為MPR。

將HELLO消息里面的reserve保留字段改為LOIN，攜帶節點的位置信息，當節點S得到其一跳鄰居時，計算α的值，α為相對角度，表示以節點S為坐標原點建立的坐標系，以x軸為起始邊，而節點S與其鄰居節點的連線為終邊的角度。根據xi－x，yi－y的正負可以得到一跳鄰居節點在S坐標系的哪一個象限，其中（x，y）表示節點S的位置信息，而（xi，yi）表示節點S一跳鄰居節點的位置信息。然后再根據反正切函數就可以得到α的值，α具體值的計算如表1所示。

如圖2所示，節點M和N必選為MPR節點，而節點A和B則根據有效覆蓋面積來選擇。有效面積計算過程以節點A為例：

a）根據α先順時針找一個最靠近節點A、B的MPR節點，然后再逆時針找一個最靠近節點A、B的MPR節點，即節點M和N；

b）以節點A為圓心，通信距離R為半徑的圓，計算其面積為SA=πR2；

c）計算節點A和S以通信距離R為半徑的圓相交部分的面積SSA；

d）判斷節點A和M以通信距離R為半徑的圓是否相交，根據兩節點之間的距離與通信距離R相比較判斷，如果（xM－xA）2+（yM－yA）2≥2R則不相交，其相交面積為0， （xM－xA）2+（yM－yA）2lt;2R則相交，接著計算圓A和M相交的面積SMA；

e）根據步驟d）計算節點A和N以通信距離R為半徑的圓相交的面積SNA；

f）節點A的有效面積為SA－SSA－SMA－SNA。

兩個圓相交部分的面積計算如式（3）所示。

S=Ddσ=∫x2x1（f1（x）－f2（x））dx" x1≠x2

∫y2y1（φ1（y）－φ2（y））dyx1=x2（3）

其中：D是指兩個圓的相交部分;（x1，y1）和（x2，y2）分別是兩個圓相交的坐標;y=f1（x）和f2（x）分別是兩個圓相交上下兩段弧線的函數表達式;當兩個圓相交的兩個坐標的橫坐標相等時，x=φ1（y）和φ2（y）分別表示兩個圓相交左右兩段弧線的函數表達式。f1（x）和φ1（y）以及f2（x）和φ2（y）互為反函數。

2.2 節點位置預估

為了解決因節點移動而導致拓撲劇烈變動，最終鏈路失效的問題，提出了一種根據歷史位置信息和當前時刻位置信息預估下一刻節點可能出現的位置，從而選擇更加穩定的節點作為MPR。在前面的有效覆蓋面積里面，在HELLO消息里面攜帶了本節點的位置信息，在接收該消息時將位置信息對應地添加到鄰居表里。預估節點下一時刻位置信息的具體步驟如下：

a）根據上一次接收到的位置信息以及本節點的位置信息將兩節點間的距離計算出來，接著本次接收到HELLO消息時，同樣計算該值，然后比較兩個值的大小。

b）如果兩個值相等，則說明這兩個節點沒有發生相對運動，表示兩節點之間的鏈路比較穩定。

c）如果兩個值不相等，說明這兩個節點發生相對運動，該值越大，說明發生的相對運動越大，即對網絡拓撲的影響越大。

2.3 RFC-MPR選擇算法具體步驟

N1表示節點的一跳鄰居集；N2表示節點的兩跳鄰居集；D（y）表示初始時一跳鄰居節點的連接度。

a）初始化集合S為空集。

b）計算N1中所有節點的連接度D（y）。

c）將N1中這樣的節點添加到S中，即只有通過該節點才能中繼到N2的節點，并從N2中刪除由S中節點所覆蓋的節點。

d）若N2為空，執行步驟g）；否則計算N1中還沒加入到S中所有節點的覆蓋度，選擇覆蓋度大的節點加入到S中；若覆蓋度相同，選擇D（y）更大的節點加入到S中，再從N2中刪除由選定節點覆蓋的節點，調轉到步驟c）；若D（y）也相同，轉到步驟e）。

e）在覆蓋度和D（y）相同的情況下，判斷這兩個一跳鄰居節點相對于上一次信息與本節點比較是否發生相對運動，選擇沒有發生相對運動或者相對運動較小的節點，將其加入S中，再從N2中刪除由選定節點覆蓋的節點，調轉到步驟c）；若兩個節點都沒有發生相對運動，轉至步驟e）。

f）兩個節點中，選擇有效覆蓋面積大的節點為MPR，將其加入S中，再從N2中刪除由選定節點覆蓋的節點，跳轉到步驟c）。

g）將S里面的節點按照α從小到大排序，如果存在兩個相鄰的節點，這兩個節點中任意一個從S里面去掉都不影響剩余節點對兩跳鄰居的覆蓋，則說明這兩個節點存在冗余，比較這兩個節點的有效覆蓋面積，將有效覆蓋面積小的節點從S里面刪除。重復該步驟直到沒有可以去掉的節點為止。

2.4 RFC-MPR選擇算法分析

為了不增加MPR節點的個數以及額外的控制消息，RFC-MPR選擇算法是在原算法基礎上的優化。該算法中的步驟g）將MPR集中的節點依次退出，看集合中剩余節點能否全部覆蓋兩跳鄰居，如果能說明該節點是冗余的，將其從MPR集中刪除，從而解決了傳統算法中存在冗余的問題。

新節點獲取全網拓撲信息過長，該問題主要是在周圍節點知道與新節點之間的鏈路狀態后計算MPR，MPR集會不會變化引起的。如果MPR沒有發生變化，則表明新節點進入網絡時就能獲取全網的拓撲信息，反之，說明新節點是在MPR改變后才能獲取全網的拓撲信息。而RFC-MPR選擇算法就是為了減少新節點進入網絡前后MPR集變化，從而引入了有效覆蓋面積，即在一定條件下該節點能覆蓋的通信范圍更大，那么新節點落在該節點的一跳范圍內的概率更大，從而提高該節點被選為MPR節點且不變的概率。最終在一定程度上解決了新節點獲取全網拓撲信息過長的問題。

拓撲的動態變化會導致鏈路失效，針對該問題RFC-MPR算法首先選擇沒有發生相對運動或者相對運動更小的節點為MPR，即節點之間的鏈路狀態相對來說不會發生變化或者發生的變化要小一些。節點間的相對位置有以下兩種狀態：a）相對靜止，包括兩個節點還是原來的位置沒有發生變化，即節點沒有移動，以及兩個節點都移動了，但是兩個節點之間的相對位置沒有發生變化；b）相對運動，至少其中一個節點發生運動，包括兩節點之間的距離更近或者更遠。其中，相對靜止也就是沒有發生相對運動是不會導致拓撲變化的，因此首先選擇這種節點為MPR。其次，如果兩個節點之間發生了相對運動，但是之間的距離變小了，那么兩個節點之間的鏈路將會更加穩定，選擇此節點為MPR。如果兩節點之間的距離變大了，即兩節點越來越遠了，那么很有可能移出節點的一跳通信范圍。因此選擇MPR時，如果剛好有兩個節點都發生相對運動而且都遠離中間節點，則根據此時兩節點距離出中間節點的一跳通信范圍的距離以及在這段時間內節點的距離增加量來選擇MPR。

3 仿真分析

本文選取標準OLSR協議中的MPR、RFC-MPR以及文獻［14］中的LSB-MPR算法進行分析比較，通過仿真實驗分析端到端時延、控制開銷、吞吐量、成功率等性能指標。

3.1 仿真參數設置

本文使用Windows平臺上的OPNET Modeler 14.5仿真軟件，設置了五個仿真場景。每個節點的計算能力一樣，而且它們的通信范圍以及收發信機的各種參數也是一樣的，其他仿真參數的具體值如表2所示。

3.2 仿真結果分析

3.2.1 控制開銷分析

OLSR協議中的控制消息開銷是指在整個協議的運行過程中，發送的總的控制消息大小，即發送HELLO和TC消息的總量。

如圖4所示，RFC-MPR與其他兩種MPR算法的控制消息開銷是一樣的，原因在于RFC-MPR只是修改了HELLO消息里面的resved保留字段并沒有增加新的字段，而且HELLO和TC消息的周期也是相同的，在仿真時間一定的情況下，控制消息開銷也是一樣的。

本文的控制開銷是指控制消息開銷和算法的開銷（包括時間開銷和空間開銷）。由于控制消息開銷、時間開銷以及空間開銷所屬范疇不同，控制開銷不能只是這三個開銷單純地相加然后比較。采用以下方式：不計算某一個協議的具體控制開銷，每次計算時都采用兩個協議一起，將兩個協議的控制消息開銷、時間開銷以及空間開銷分別作比值然后相加，如果該值大于3說明分子上的協議控制開銷大，反之說明開銷小。如圖5所示，RFC-MPR和LSB-MPR相較于原協議來說，都增加了控制開銷，這是由于這兩個算法在原算法的基礎上都增加了一些額外的功能，使得算法的時間開銷增加。而RFC-MPR在此基礎上還存儲了鄰居的位置信息增加了空間開銷，所以該算法的控制開銷相較于LSB-MPR更大。隨著速度的增加，拓撲的變化更加明顯，導致算法中的輸入量變化，導致時間開銷和空間開銷增加，以至于總的控制開銷增加。而且RFC-MPR和LSB-MPR提高了在網絡拓撲變化時網絡的性能，因此隨著速度的增加，控制開銷方面相較于原算法增加得更大。

3.2.2 時延分析

端到端時延是指從源節點創建數據包開始到目的節點接收到相應數據包總共需要的時間。如圖6所示，RFC-MPR所用的時延相對于其他兩種算法要低一些，其原因有以下幾個：首先本文減少了部分TC消息的冗余，讓部分節點總體上少接收到了一部分TC消息，在發送緩存隊列里面就會減少部分控制消息，發送等待時間就會少一些，從而在端到端時延的總體上少一部分；其次，該算法對節點的位置進行了預估，讓選擇的MPR節點更加穩定，隨著速度的增加，端到端時延降低了更多。

3.2.3 發包成功率分析

發包成功率是指接收到的總體數據包數量與發送數據包數量的比值，該值越接近1，說明網絡的性能越好。

如圖7所示，RFC-MPR的成功率比其他兩種算法提高了很多。首先，該算法中減少了冗余，即在原來算法的基礎上再度減少了泛洪，在一定程度上降低了擁塞，使得因為擁塞而讓控制消息在三個周期內收不到該消息的情況減少，從而提高了成功率。而且本文基于歷史信息來預估節點下一時刻可能在的位置，提前將某些鏈路要失效的MPR節點剔除，選擇其他更穩定的節點為MPR，保證路由表里面的路由都是真實有效的，不會出現找不到路由的情況，減少了丟包的個數。而且如果有新節點加入網絡時，該算法的成功率會更高，原因在于該算法考慮到了新節點獲取全網拓撲的時間，讓其能更快地獲取全網的拓撲信息，該節點對網絡中任意一個節點發送數據包時都比其他算法更可能存在路由，最終讓成功率上升。

3.2.4 吞吐量分析

吞吐量是指單位時間內收到的數據量。RFC-MPR的時延降低了，成功率也提升了，而且網絡中沒有增加額外的控制開銷，所以吞吐量相對于其他兩種算法有一定的提升。如圖8所示，隨著速度的提升，吞吐量明顯下降，這是由于速度的增大會導致某些節點移動出通信范圍，從而出現找不到路由的情況，增加了丟包的個數，導致最終吞吐量下降。

3.2.5 網絡生存時間分析

網絡生存時間是指從網絡啟動到網絡中最后一個節點死亡的時間或者網絡中的節點死亡導致網絡不再連通的時間，這是對網絡整體而言。本文主要是從單個節點來說且不考慮能量問題，并不是節點啟動就開始計算網絡生存時間，網絡生存時間會有所不同。當節點能夠獲取全網拓撲信息時才是網絡生存時間的開始，因此節點從啟動到能夠獲取全網拓撲信息的時間，即入網時間越短網絡生存時間越久。

能獲取全網拓撲信息的時間數據是隨機選擇了網絡中的五個節點統計，然后計算這五個節點的平均值。如圖9所示，RFC-MPR的入網時間比其他兩種算法的時間少很多，主要是該算法考慮了有效覆蓋面積，選擇了更有效的節點作為MPR，從而讓其他節點能夠更快地獲取全網拓撲信息，入網時間縮短，其網絡生存時間也就更長了。其次，該算法還減少了部分TC消息的冗余以及預測節點的位置信息，選擇更穩定的節點作為MPR節點，讓節點與周圍節點之間鏈路的建立所需時間更少，即能夠更快入網。隨著速度的增加，節點間的鏈路也會出現不穩定從而導致已入網節點出網的現象，從而增加入網時間，導致網絡生存時間減短。

4 結束語

本文提出了一種RFC-MPR算法，相較于其他算法本文考慮得更加充分。該算法主要是從新加入節點獲取全網拓撲信息的時間入手，在不增加額外控制開銷的前提下，縮短了新節點獲取全網拓撲信息的時間，從而能夠更早地建立到全網的所有路由。同時，本文考慮到可能存在冗余的TC消息，優化了部分冗余，并且根據節點的歷史信息和當前信息對下一時刻節點的位置進行了預估，選擇了相對更加穩定的節點作為MPR。在整個仿真結果中，本文算法在各個方面都得到了提升。下一步將不再把覆蓋度作為選擇MPR的第一要素，而是將鏈路穩定作為第一要素，考慮每個節點的能量、鏈路質量等因素從而優化整個網絡的性能。

參考文獻：

[1]王海濤.基于無線自組網的應急通信技術［M］.北京：電子工業出版社，2015.（Wang Haitao. Emergency communication technology based on wireless Ad hoc network［M］. Beijing：Publishing House of Electronics Industry，2015.）

［2]張淑軍．MANET網絡自適應可靠信息分發協議研究與實現［D］．成都：電子科技大學，2018．（Zhang Shujun. Research and implementation of MANET network adaptive and reliable information distribution protocol［D］.Chengdu：University of Electronic Science and Technology of China，2018.）

［3]聶建寧，李巍.無線Ad hoc網絡在搶險救災行動中的通信應用［J］.通信電源技術，2019，36（3）：190-191.（Nie Jianning， Li Wei. Communication application of wireless Ad hoc network in rescue and disaster relief operations［J］.Telecom Power Technologies，2019，36（3）：190-191.）

［4]Abhilash K J， Shivaprakasha K S. Secure routing protocol for MANET：a survey［C］//Advances in Communication， Signal Processing， VLSI， and Embedded Systems.Berlin：Springer，2020：263-277.

［5]Lachowski R， Pellenz M E， Jamhour E， et al. ICENET：an information centric protocol for big data wireless sensor networks［J］.Sensors，2019，19（4）：930.

［6]Mohapatra S， Kanungo P. Performance analysis of AODV， DSR， OLSR and DSDV routing protocols using NS2 simulator［J］.Procedia Engineering，2012，30：69-76.

［7]馬科.戰術互聯網環境下OLSR路由協議改進研究［D］.天津：南開大學，2016.（Ma Ke. Research on improvement of OLSR routing protocol in tactical Internet environment［D］.Tianjin：Nankai University，2016.）

［8]Clausen T H， Jacquet P. RFC 3626，Optimized link state routing protocol （OLSR）［S］.2003.

［9]Oyakhire O ， Gyoda K. Improved OLSR considering node density and residual energy of nodes in dense networks［C］//Proc of the 35th International Technical Conference on Circuits/Systems，Computers and Communications.2020：161-165.

［10]Belkhira S， Boukli-Hacene S， Lorenz P， et al. A new mechanism for MPR selection in mobile Ad hoc and sensor wireless networks［C］//Proc of IEEE International Conference on Communications.Pisca-taway，NJ：IEEE Press，2020：1-6.

［11]Al-Kharasani N M， Zukarnain Z A， Subramaniam S K， et al. An adaptive relay selection scheme for enhancing network stability in VANETs［J］.IEEE Access，2020（8）：128757-128765.

［12]Jain R， Kashyap I. An QoS aware link defined OLSR （LD-OLSR） routing protocol for MANETS［J］.Wireless Personal Communications，2019，108（3）：1745-1758.

［13]Usha M， Ramakrishnan B. An enhanced MPR OLSR protocol for efficient node selection process in cognitive radio based VANET［J］.Wireless Personal Communications，2019，106（2）：763-787.

［14]吳佳琪，任智，王磊，等.一種基于鏈路穩定性的最小MPR選擇算法［J］.小型微型計算機系統，2020，41（11）：2386-2391.（Wu Jiaqi， Ren Zhi， Wang Lei， et al. A minimum MPR selection algorithm based on link stability［J］.Journal of Chinese Computer Systems，2020，41（11）：2386-2391.）