基于鏈路預測的可靠MPR選擇算法

摘 要：為了降低移動自組織網絡（MANET）中移動性對路由性能造成的影響，該文提出基于鏈路預測的可靠MPR選擇算法，通過節點間距離和無線傳輸范圍來預測節點與其相鄰節點之間的剩余鏈路有效時間，并提出將剩余鏈路有效時間（RTTQ）作為OLSR路由協議選擇多點中繼（MPR）的新的度量方法。利用NS2進行了大量的網絡仿真，結果顯示采用RTTQ大于臨界值的MPR節點，可以提高多項性能，如MPR生存時間、分組交付率（PDR）和平均吞吐量（ATT）。

關鍵詞：移動自組織網絡 多點中繼 鏈路中斷 NS2 MPR生存時間

中圖分類號：TP393 文獻標識碼：A 文章編號：1674-098X（2015）08（b）-0084-03

Abstract：In order to reduce the effect of the mobility of mobile ad-hoc network （MANET） on routing performance， this paper proposed a reliable MPR selection algorithm based on link prediction. The valid time of remaining chain between this node and adjacent node was predicted by both the distance between nodes and the range of wireless transmission. The paper also proposed a new measuring method on selecting multi-point relay by applying the remaining link effective time （RTTQ） as OLSR routing protocol. A lot of NS2 network simulation were conducted in this paper. The results show that a number of properties， such as MPR survival time， packet delivery ratio （PDR） and average throughput（ATT）， can be improved by using the MPR nodes， in which the RTTQ was greater than the critical value.

Key Word：MANET； Multi Point Relay； Link Interruption； NS2； MPR Survival Time

由于OLSR路由問題與MPR選擇有關，即可以通過在MPR選擇機制上增加度量，提高路由性能。關于OLSR路由優化的大部分文獻都致力于尋找除了RFC3626中（路徑質量通過跳數衡量）規定的默認度量之外的其他有效度量，如誤比特率（BER）[1]或隊列長度。QOLSR[2]是先應式路由的一個重大發展，其通過向OLSR增加QoS機制對帶寬利用率或時延等實施限制從而尋找最短最寬的路徑提供最佳路徑選擇。文獻[3]還提出了期望傳輸數（ETX）度量作為MANET因特網草案，目前有望成為標準。文獻[4]中提出了一種MPR選擇法，該方法通過將傳播包匯聚在MPR節點，進一步降低重新傳輸次數。但是鑒于無線環境的不穩定性，減少重新傳輸次數不一定對可靠數據包傳輸有利。文獻[5]提出了另一種方法，試圖預測一定時間范圍內的鏈路有效性以及兩節點間給定初始距離的鏈路有效性。由于MPR節點在將廣播包傳輸到下個MPR節點以及相鄰節點中起到重要作用，如果不能從MPR接收到廣播包，就會嚴重影響交付率。因此，根據鏈路生存時間預測選擇可靠MPR為改善路由性能提出了很好的切入點。由于節點移動，有些無線鏈路可能在路徑建立起來后立即中斷。如果再次發現路由，就會產生大量的數據丟失和通信開銷。

由此可見，現在路由的共同弱點是由于網絡環境中節點的移動特性，依據過去或當前的鏈路狀態信息確定的可靠鏈路可能隨著時間推移而變得不可靠，即不能較好的適應未知的鏈路變化。同時以往的很多鏈路狀態信息都是根據自組網的鏈路狀態的進行統計分析，并不能代表現實鏈路環境。為了降低此類網絡中移動性造成的影響，本文提出基于鏈路預測的可靠MPR選擇算法，通過每次信息包中攜帶的節點間距離和時間信息并結合無線傳輸范圍來預測節點與其相鄰節點之間的剩余鏈路有效時間RTTQ，并利用RTTQ作為MPR選擇的新的度量方法，從而選出鏈路更穩定，性能更優的MPR節點，進而提升路由性能。

1 OLSR協議概述

OLSR協議是針對MANET特點發展起來的表驅動路由協議，網絡中的每個節點都保存有到網絡中所有可達目的節點的路由，使用最小跳數來尋找出到達目的節點的最短路徑。協議最突出的就是通過MPR（Multipoint Relays）機制減少網絡控制信息的泛洪。網絡中的每個節都在其一跳節點中選擇出MPR節點，非MPR節點能夠處理控制信息但不能轉發控制信息，而且MPR集必須覆蓋其所有的兩條節點。協議通過HELLO信息周期性的廣播一跳鄰居節點的鏈路信息和地址來選擇MPR集。通過節點周期性的發送TC（Topology Control）分組來發布 MPR Selector 信息，以幫助其他節點建立到它的路由，并通過周期性地交換信息來維護網絡拓撲。因此，OLSR協議的核心功能包括以下幾方面：

鏈路感知：通過周期性（標準間隔為2秒）交換HELLO信息獲得，并更新本地鏈路表信息。

發現鄰近節點：像鏈路感知過程一樣，鄰近節點的檢測也是通過HELLO信息完成的。

MPR選擇：每個節點都在其一跳鄰近節點中選擇一個能到達所有兩跳鄰近節點的最小子集，該集合則為MPR節點節點集。

TC信息廣播：發布TC消息（拓撲控制信息）的目的在于為使每個網絡節點獲得全網的鏈路狀態信息，用以選定路由和發送信息。TC消息也是周期性的更新（標準間隔為5秒），通過MPR節點范洪到全網。

路由計算：網絡中每個節點都可以根據鏈路狀態信息的定期交換，重新計算路由表。

2 DIST-OLSR協議

2.1 剩余有效時間（RTTQ）

如圖1所示，以其中一個節點（S）對鄰居節點（N）鏈路有效時間進行估計并選擇MPR選擇為例，本節點根據兩次連續接收到的消息期間，節點移動的距離（D1和D2），對應移動所歷經時間（△t=T2–T1）和無線傳輸范圍（RANGE）可以估計出鄰居節點的鏈路有效時間。

其中，T1和T2分別指鄰居節點在D1和D2的時間。△d指的是新老距離之間的差（△d=D2-D1），并記錄在接收的消息中（包括HELLO，TC消息），△d的正負表示其鄰居節點相對源節點的遠離或靠近，這在MPR集運算過程中很重要。文中，RTTQ取最大的有效時間值，計算如式（1）：

（1）

2.2 受RTTQ臨界值限制的MPR集計算

節點每接收一個消息都會調用圖2的算法來對每個鄰居節點的RTTQ進行重新估計。因此，在選擇MPR節點時，可能較早離開（或在離開邊緣）的鄰居節點將不能作為MPR候選節點，且只有當節點的RTTQ值大于給定的臨界值時，MPR候選節點才會被納入MPR集中。在此方法中，不僅考慮了標準OLSR協議（RFC3626）中的節點到達性和節點度，同時考慮了節點的鏈路狀態。通過修改標準OLSR中的MPR選擇方法，就獲得了一個新版的OLSR協議（DIST-OLSR）。同樣，如果節點達到性非零且具有最高的意愿度同樣被選為MPR節點。在面臨多個選擇是，首先將到達性最大且RTTQ大于給定臨界值的節點選為MPR。如果多個節點具有相同的到達性和RTTQ，我們將節點度最大的節點選為MPR。

3 仿真分析

該文采用NS2-2.34[6]進行網絡仿真，并對標準版本的OLSR（UM-OLSR-0.8.8）[7]進行修改。仿真場景參數如表1，其中，每次模擬會隨機選擇10個節點作為固定比特率（CBR）業務的來源。

3.1 平均MPR節點數

如圖3所示，給出了不同RTTQ臨界值和節點移動速度，UM-OLSR協議和DIST-OLSR協議下的MPR平均數量。可以發現，在不同RTTQ臨界值下，DIST-OLSR協議和標準OLSR幾乎擁有相同的MPR數，基本上對于不同的RTTQ臨界值，標準OLSR只是增加了約0.25%。然而，當節點移動速度提高時，兩種版本OLSR（UM-OLSR和Dist-OLSR）協議產生的MPR平均數量均急劇減少。其主要是因為當速度增加時，節點間鏈路變化更快，節點的鏈路有效時間相對減少，這將大大影響網絡的性能。

3.2 MPR平均生存時間

圖4顯示了不同臨界值和速度時，UM-OLSR協議和DIST-OLSR協議下的MPR平均生存時間。

從圖4和表2可以看出，DIST-OLSR協議下，有18次其MPR平均生存時間比標準OLSR協議長，相較而言，標準OLSR協議下只有10次的MPR平均生存時間較長。從整體看，DIST-OLSR協議下的MPR生存時間比標準OLSR協議下的生存時間提高了26.66%。另外，表2還說明：DIST-OLSR協議的最佳結果出現在當臨界值為3 s或4 s時。此外，在高速下（20～25 m/s），MPR平均生存時間趨向于平穩，約4.5 s，而且其值在所有臨界值下都幾乎一樣。

3.3 分組交付率（PDR）

RTTQ臨界值為3和4秒時，DIST-OLSR的MPR平均生存時間最長，那么有必要采用交付率來對網絡的性能進行評價。節點采用RWP移動模型時，不同速度下兩種協議的分組交付率（PDR）如圖5所示。

由圖5可知，不管臨界值是3 s還是4 s，隨著節點速度的增加，PDR都在下降。從圖上我們還發現，臨界值為3 s時，兩種OLSR協議的PDR值非常接近，DIST-OLSR協議下相對于標準OLSR協議的結果要稍微高一點。當臨界值為4 s時，低速下情況下，標準OLSR協議要優于DIST-OLSR，而高速下情況下，DIST-OLSR結果優于標準OLSR協議。

3.4 平均吞吐量

圖6顯示了當臨界值為3秒和4秒時，不同速度下，標準OLSR協議和DIST-OLSR的平均吞吐量仿真情況。臨界值為3 s或4 s時，低速下情形下（5和10 m/s）的DIST-OLSR協議的平均吞吐量較高。當臨界值為3 s，高速下情形下（20和25 m/s）的DIST-OLSR協議的平均吞吐量也高于標準OLSR協議。當速度為15 m/s時，標準OLSR協議的結果才優于DIST-OLSR協議結果。因此，總體上，在平均吞吐量方面，DIST-OLSR協議整體性能相對較好。

4 結論

該文的首要目標是將控制信息和數據包發送至目的地址的路徑的生存時間延長，提高鏈路可靠性。基本思想是通過信息包攜帶的位置信息和無線傳輸距離預測鏈路有效時間，并引入MPR選擇的新度量RTTQ，從而降低節點移動性的帶來的不利影響。通過仿真分析發現，DIST-OLSR協議的MPR有效時間比標準OLSR協議（UM-OLSR）提高約25%。

參考文獻

[1]M.Poussard， W.Hamidouche， R. Vauzelle， et al. Realistic SISO and MIMO physical layer implemented in two routing protocols for vehicular ad hoc network[C]//In 9th International Conference on Intelligent Transport Systems Tele-communications.2009：393-397.

[2]H.Badis， K. Al Agha. QOLSR， QoS routing for ad hoc wireless networks using OLSR[J]. uropean Transactions on Telecommunications， 2005， 16（5）： 427-442.

[3]xK. Yamada， T. Itokawa， T. Kitasuka， et al. Cooperative MPR selection to reduce topology control packets in OLSR[C]//TENCON 2010-2010 IEEE Region 10 Conference.2010：293-298.

[4]Q. Han， Y. Bai， L. Gong， et al. Link availability prediction-based reliable routing for mobile ad hoc networks[J].IET Communications，2011，5（16）：2291-2300.

[5]T. Clausen， P.Jacquet. Optimized Link State Routing protocol （OLSR）[C]//Internet Engeneering Task Force， RFC 3626.2003.

[6]N. Sadagopan， F. Bai， B. Krishnamachari， et al. PATHS： analysis of PATH duration statistics and their impact on reactive MANET routing protocols[C]//Proceedings of the 4th ACM international symposium on Mobile ad hoc networking and computing. 2003：245-256.

[7]Shengming Jiang， Dajiang He， Jianqiang Rao.A prediction-based link availability estimation for routing metrics in MANETs[C]//IEEE/ACM Transactions on Networking，2005，13（6）：1302-1312.

[8]Shengming Jiang. An enhanced prediction-based link availability estimation for MANETs[J].IEEE Transactions on Communications，2004，52（2）：183-186.