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

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

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

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

1 OLSR協(xié)議概述

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

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

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

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

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

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

2 DIST-OLSR協(xié)議

2.1 剩余有效時(shí)間（RTTQ）

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

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

（1）

2.2 受RTTQ臨界值限制的MPR集計(jì)算

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

3 仿真分析

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

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

如圖3所示，給出了不同RTTQ臨界值和節(jié)點(diǎn)移動速度，UM-OLSR協(xié)議和DIST-OLSR協(xié)議下的MPR平均數(shù)量。可以發(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é)點(diǎn)移動速度提高時(shí)，兩種版本OLSR（UM-OLSR和Dist-OLSR）協(xié)議產(chǎn)生的MPR平均數(shù)量均急劇減少。其主要是因?yàn)楫?dāng)速度增加時(shí)，節(jié)點(diǎn)間鏈路變化更快，節(jié)點(diǎn)的鏈路有效時(shí)間相對減少，這將大大影響網(wǎng)絡(luò)的性能。

3.2 MPR平均生存時(shí)間

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

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

3.3 分組交付率（PDR）

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

由圖5可知，不管臨界值是3 s還是4 s，隨著節(jié)點(diǎn)速度的增加，PDR都在下降。從圖上我們還發(fā)現(xiàn)，臨界值為3 s時(shí)，兩種OLSR協(xié)議的PDR值非常接近，DIST-OLSR協(xié)議下相對于標(biāo)準(zhǔn)OLSR協(xié)議的結(jié)果要稍微高一點(diǎn)。當(dāng)臨界值為4 s時(shí)，低速下情況下，標(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秒和4秒時(shí)，不同速度下，標(biāo)準(zhǔn)OLSR協(xié)議和DIST-OLSR的平均吞吐量仿真情況。臨界值為3 s或4 s時(shí)，低速下情形下（5和10 m/s）的DIST-OLSR協(xié)議的平均吞吐量較高。當(dāng)臨界值為3 s，高速下情形下（20和25 m/s）的DIST-OLSR協(xié)議的平均吞吐量也高于標(biāo)準(zhǔn)OLSR協(xié)議。當(dāng)速度為15 m/s時(shí)，標(biāo)準(zhǔn)OLSR協(xié)議的結(jié)果才優(yōu)于DIST-OLSR協(xié)議結(jié)果。因此，總體上，在平均吞吐量方面，DIST-OLSR協(xié)議整體性能相對較好。

4 結(jié)論

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

參考文獻(xiàn)

[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.