基于鏈路預(yù)測的可靠MPR選擇算法

郭玉婷 李強

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

關(guān)鍵詞：移動自組織網(wǎng)絡(luò) 多點中繼 鏈路中斷 NS2 MPR生存時間

中圖分類號：TP393 文獻標(biāo)識碼：A 文章編號：1674-098X（2015）08（c）-0054-03

Reliable MPR Selection Algorithm Based on Link Prediction

Guo Yuting1，2， Li Qiang2

（1.Wuhan Lingyun Building Decoration Engineering CO.LTD.，Wuhan Hubei，430040；2.Air Force Early Warning Inst.，Wuhan Hubei，430019，China）

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 Words：MANET；Multi Point Relay；Link Interruption；NS2；MPR Survival Time

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

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

1 OLSR協(xié)議概述

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

（1）鏈路感知：通過周期性（標(biāo)準(zhǔn)間隔為2s）交換HELLO信息獲得，并更新本地鏈路表信息。

（2）發(fā)現(xiàn)鄰近節(jié)點：像鏈路感知過程一樣，鄰近節(jié)點的檢測也是通過HELLO信息完成的。

（3）MPR選擇：每個 節(jié)點都在其一跳鄰近節(jié)點中選擇一個能到達(dá)所有兩跳鄰近節(jié)點的最小子集，該集合則為MPR節(jié)點節(jié)點集。

（4）TC信息廣播：發(fā)布TC消息（拓?fù)淇刂菩畔ⅲ┑哪康脑谟跒槭姑總€網(wǎng)絡(luò)節(jié)點獲得全網(wǎng)的鏈路狀態(tài)信息，用以選定路由和發(fā)送信息。TC消息也是周期性的更新（標(biāo)準(zhǔn)間隔為5秒），通過MPR節(jié)點范洪到全網(wǎng)。

（5）路由計算：網(wǎng)絡(luò)中每個節(jié)點都可以根據(jù)鏈路狀態(tài)信息的定期交換，重新計算路由表。

2 DIST-OLSR協(xié)議

2.1 剩余有效時間（RTTQ）

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

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

（1）

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

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

3 仿真分析

文章采用NS2-2.34[6]進行網(wǎng)絡(luò)仿真，并對標(biāo)準(zhǔn)版本的OLSR（UM-OLSR-0.8.8）[7]進行修改。仿真場景參數(shù)如表1，其中，每次模擬會隨機選擇10個節(jié)點作為固定比特率（CBR）業(yè)務(wù)的來源。

3.1 平均MPR節(jié)點數(shù)

如圖3所示，給出了不同RTTQ臨界值和節(jié)點移動速度，UM-OLSR協(xié)議和DIST-OLSR協(xié)議下的MPR平均數(shù)量?？梢园l(fā)現(xiàn)，在不同RTTQ臨界值下，DIST-OLSR協(xié)議和標(biāo)準(zhǔn)OLSR幾乎擁有相同的MPR數(shù)，基本上對于不同的RTTQ臨界值，標(biāo)準(zhǔn)OLSR只是增加了約0.25%。然而，當(dāng)節(jié)點移動速度提高時，兩種版本OLSR（UM-OLSR和Dist-OLSR）協(xié)議產(chǎn)生的MPR平均數(shù)量均急劇減少。其主要是因為當(dāng)速度增加時，節(jié)點間鏈路變化更快，節(jié)點的鏈路有效時間相對減少，這將大大影響網(wǎng)絡(luò)的性能。

3.2 MPR平均生存時間

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

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

3.3 分組交付率（PDR）

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

由圖5可知，不管臨界值是3 s秒還是4 s，隨著節(jié)點速度的增加，PDR都在下降。從圖上我們還發(fā)現(xiàn)，臨界值為3s時，兩種OLSR協(xié)議的PDR值非常接近，DIST-OLSR協(xié)議下相對于標(biāo)準(zhǔn)OLSR協(xié)議的結(jié)果要稍微高一點。當(dāng)臨界值為4 s時，低速下情況下，標(biāo)準(zhǔn)OLSR協(xié)議要優(yōu)于DIST-OLSR，而高速下情況下，DIST-OLSR結(jié)果優(yōu)于標(biāo)準(zhǔn)OLSR協(xié)議。

3.4 平均吞吐量

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

4 結(jié)語

該文的首要目標(biāo)是將控制信息和數(shù)據(jù)包發(fā)送至目的地址的路徑的生存時間延長，提高鏈路可靠性?；舅枷胧峭ㄟ^信息包攜帶的位置信息和無線傳輸距離預(yù)測鏈路有效時間，并引入MPR選擇的新度量RTTQ，從而降低節(jié)點移動性的帶來的不利影響。通過仿真分析發(fā)現(xiàn)，DIST-OLSR協(xié)議的MPR有效時間比標(biāo)準(zhǔn)OLSR協(xié)議（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].European Transactions on Telecommunications，2005，16（5）：427-442.

[3] K.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(xiàn).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.