孫友偉， 張　晶， 王辰寰

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

優(yōu)化鏈路狀態(tài)路由多點(diǎn)中繼選擇策略改進(jìn)

孫友偉， 張晶， 王辰寰

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

摘要:對(duì)優(yōu)化鏈路狀態(tài)路由協(xié)議中多點(diǎn)中繼選擇策略加以改進(jìn)。在求解中繼節(jié)點(diǎn)集時(shí)，對(duì)源節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)中已被其他源節(jié)點(diǎn)選進(jìn)中繼節(jié)點(diǎn)集的節(jié)點(diǎn)，視其具有較高二跳節(jié)點(diǎn)覆蓋數(shù)，并將其加入退出檢測(cè)隊(duì)列，以減少網(wǎng)絡(luò)中繼節(jié)點(diǎn)的冗余。仿真結(jié)果顯示，在節(jié)點(diǎn)速率為1～30 m/s時(shí)，改進(jìn)策略能夠降低網(wǎng)絡(luò)時(shí)延1%～4%，減少網(wǎng)絡(luò)拓?fù)淇刂品纸M2%～7%。

關(guān)鍵詞:優(yōu)化鏈路狀態(tài)路由協(xié)議；貪心算法；中繼節(jié)點(diǎn)；局部?jī)?yōu)化；選擇策略

作為信息技術(shù)的重要組成部分,被納入重大發(fā)展規(guī)劃的物聯(lián)網(wǎng)技術(shù)已深入到了人們?nèi)粘Ｉ畹母鱾€(gè)方面[1]：智能家庭可用電力線進(jìn)行載波通信，以方便各種家用電器進(jìn)行數(shù)據(jù)通信[2]；交通智能化領(lǐng)域則采用無(wú)線通信技術(shù)實(shí)現(xiàn)車輛間的相互連接，以實(shí)現(xiàn)汽車互聯(lián)網(wǎng)。

汽車互聯(lián)網(wǎng)是一種特殊的移動(dòng)自組織網(wǎng)絡(luò)(adhoc)。移動(dòng)自組織網(wǎng)絡(luò)具有自組織，無(wú)中心，多跳路由和動(dòng)態(tài)拓?fù)涞奶攸c(diǎn)。優(yōu)化鏈路狀態(tài)路由(OptimizedLinkStateRouting，OLSR)是adhoc網(wǎng)絡(luò)中常用的路由協(xié)議,其關(guān)鍵概念是消息的多點(diǎn)轉(zhuǎn)播，主要通過(guò)選取多個(gè)中繼節(jié)點(diǎn)(MultiPointRelay，MPR)來(lái)代替全部的一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)消息[3]。MPR集是在消息廣播洪泛的過(guò)程中由MPR選擇者節(jié)點(diǎn)挑選的轉(zhuǎn)發(fā)消息的節(jié)點(diǎn)集。在優(yōu)化鏈路協(xié)議中，鏈路拓?fù)淇刂菩畔?(TopologyControl，TC)是由MPR集中的節(jié)點(diǎn)產(chǎn)生的。這種機(jī)制可克服表驅(qū)動(dòng)式路由協(xié)議中網(wǎng)絡(luò)維護(hù)開(kāi)銷大的缺點(diǎn)[4]，但傳統(tǒng)優(yōu)化鏈路狀態(tài)路由中MPR集的選取使用貪心策略，而此策略并不從整體優(yōu)化上加以考慮，只是通過(guò)局部?jī)?yōu)化來(lái)求得一種近似最優(yōu)解，不能有效減少整個(gè)網(wǎng)絡(luò)中洪泛的信息數(shù)量[5]，容易造成網(wǎng)絡(luò)堵塞。

本文給出一種全局性選擇策略(Global-MultiPointRelay,G-MPR)，以繼承貪心策略簡(jiǎn)單高效的優(yōu)點(diǎn)，并綜合考慮全局優(yōu)化且無(wú)法回避各源節(jié)點(diǎn)之間選擇的關(guān)聯(lián)性，在符合MPR選擇準(zhǔn)則的基礎(chǔ)上減小其對(duì)選取的影響，使其達(dá)到近似最優(yōu)。

1MPR集選擇準(zhǔn)則及問(wèn)題

1.1傳統(tǒng)MPR集選擇準(zhǔn)則

傳統(tǒng)OLSR路由協(xié)議中MPR選擇策略比較簡(jiǎn)單，其每個(gè)節(jié)點(diǎn)相對(duì)獨(dú)立地選擇各自的MPR集。MPR集的選取需要滿足兩個(gè)條件：首先，源節(jié)點(diǎn)所選取的MPR集應(yīng)全部取自源節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)。其次，選定的MPR集須覆蓋源節(jié)點(diǎn)的所有二跳鄰居節(jié)點(diǎn)。MPR選擇的問(wèn)題就是在符合以上兩個(gè)條件的情況下，使得MPR集的成員節(jié)點(diǎn)數(shù)最少。

1.2存在的問(wèn)題

傳統(tǒng)的選擇策略使用貪心策略，正是由于貪心策略僅采用一跳鄰居節(jié)點(diǎn)的覆蓋數(shù)作為衡量尺度，因此求解的近似解很大程度上帶有冗余，且其只針對(duì)局部求最小集，沒(méi)有做全局考慮。

關(guān)于MPR的改進(jìn)大多局限于單個(gè)節(jié)點(diǎn)的MPR集選擇策略，并未考慮多節(jié)點(diǎn)的選擇情況(圖1)，要減少網(wǎng)絡(luò)中產(chǎn)生的信息分組數(shù)，必須降低整個(gè)網(wǎng)絡(luò)的MPR節(jié)點(diǎn)。僅僅意識(shí)到從全局考慮選擇MPR集的重要性[6]，但缺乏一種具體優(yōu)化的選擇策略，想提高M(jìn)PR鏈路的穩(wěn)定性還遠(yuǎn)遠(yuǎn)不夠。全局選擇策略(Global_OP_MPR)[7]引入了全局因素，但策略第三步將一跳節(jié)點(diǎn)中已被其他源節(jié)點(diǎn)選為MPR節(jié)點(diǎn),且轉(zhuǎn)發(fā)承載值不為0的所有節(jié)點(diǎn),加入MPR集中，即源節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)中有一些節(jié)點(diǎn)早已經(jīng)被默認(rèn)選為MPR節(jié)點(diǎn)。這種選擇策略勢(shì)必造成節(jié)點(diǎn)間的關(guān)聯(lián)性增加，且某源節(jié)點(diǎn)選擇MPR節(jié)點(diǎn)時(shí)需要依賴其他節(jié)點(diǎn)所選擇的MPR節(jié)點(diǎn)，不做任何判斷地將其他節(jié)點(diǎn)所選MPR節(jié)點(diǎn)加入本節(jié)點(diǎn)的MPR集，會(huì)在很大程度上干擾原MPR選擇策略，造成整個(gè)網(wǎng)絡(luò)冗余度大幅增加。

圖1　一個(gè)自組織網(wǎng)絡(luò)的簡(jiǎn)單拓?fù)?/p>

在整個(gè)網(wǎng)絡(luò)中，各源節(jié)點(diǎn)選取各自MPR節(jié)點(diǎn)時(shí)互相存在的關(guān)聯(lián)性，除過(guò)第一個(gè)選取MPR集的節(jié)點(diǎn)，所有的其他源節(jié)點(diǎn)被迫選擇一個(gè)不僅大于最小的，而且大于在不考慮其他源節(jié)點(diǎn)的情況下選擇的MPR集。由于現(xiàn)實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)眾多，這種關(guān)聯(lián)性造成的冗余可能會(huì)大幅度的增加，使網(wǎng)絡(luò)中洪泛的信息量增加[8]，從而導(dǎo)致信息擁塞。

2改進(jìn)的選擇策略

2.1G-MPR選擇策略

在G-MPR選擇策略中，對(duì)于已被其他源節(jié)點(diǎn)選入MPR集的一跳鄰居節(jié)點(diǎn)，且其轉(zhuǎn)發(fā)承載值不為0，則默認(rèn)其有高的優(yōu)先權(quán)，也加入退出判斷行列中。G-MPR選擇策略是一種能使全局網(wǎng)絡(luò)中MPR節(jié)點(diǎn)數(shù)達(dá)到優(yōu)化的改進(jìn)策略，具體描述如下。

步驟1定義源節(jié)點(diǎn)i的MPR集為S。

步驟2對(duì)于一跳鄰居節(jié)點(diǎn)N1(i)中所有節(jié)點(diǎn)，計(jì)算他們各自在二跳鄰居節(jié)點(diǎn)N2(i)中能覆蓋的節(jié)點(diǎn)個(gè)數(shù)。

步驟3檢測(cè)N1(i)中所有節(jié)點(diǎn)，選出其中已被其他源節(jié)點(diǎn)選為MPR的節(jié)點(diǎn),并判斷其轉(zhuǎn)發(fā)承載值是否為0，若為0則將其從N1(i)中剔除；然后分別將未被其他源節(jié)點(diǎn)選為MPR的節(jié)點(diǎn)和已被選為MPR的節(jié)點(diǎn),按照每個(gè)節(jié)點(diǎn)在二跳鄰居節(jié)點(diǎn)集中的覆蓋數(shù),從小到大進(jìn)行各自排序；分別將未被其他源節(jié)點(diǎn)選中和已被選中的兩部分，先后加入S集。

步驟4按照S集中節(jié)點(diǎn)的順序，將節(jié)點(diǎn)依次退出，每次查看N2(i)中是否還有未被S中其他任何節(jié)點(diǎn)覆蓋的節(jié)點(diǎn)，如果存在則說(shuō)明該節(jié)點(diǎn)不能退出S，否則，將此節(jié)點(diǎn)退出S。

從多個(gè)源節(jié)點(diǎn)選取MPR節(jié)點(diǎn)的角度出發(fā)，考慮已被其他節(jié)點(diǎn)選為MPR的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的特殊性，將已被其他源節(jié)點(diǎn)選為MPR的節(jié)點(diǎn)集和剩余節(jié)點(diǎn)集分為兩部分各自排序，然后重新整合，最后執(zhí)行退出檢測(cè)策略。這種新策略給已被其他源節(jié)點(diǎn)選為MPR的節(jié)點(diǎn)賦予更高的優(yōu)先權(quán)，默認(rèn)其有多的覆蓋數(shù)，既能減少整個(gè)網(wǎng)絡(luò)的MPR節(jié)點(diǎn)數(shù)，也能減小相關(guān)性引起的冗余。

2.2實(shí)例分析

依據(jù)改進(jìn)的選擇策略，對(duì)圖1所示實(shí)例，求解整個(gè)網(wǎng)絡(luò)的MPR節(jié)點(diǎn)集。

假設(shè)源節(jié)點(diǎn)1先選取MPR節(jié)點(diǎn)，因此，選取不受源節(jié)點(diǎn)2的關(guān)聯(lián)性影響，源節(jié)點(diǎn)1的MPR集為

M1={2,3,4,6,7}。

源節(jié)點(diǎn)2的一跳鄰居節(jié)點(diǎn)

N1={1,6,7,8,9}。

節(jié)點(diǎn)6和7已被源節(jié)點(diǎn)1選定，且N1中的節(jié)點(diǎn)在二跳鄰居節(jié)點(diǎn)的覆蓋數(shù)分別是{3,4,2,3,2}，根據(jù)步驟3分別排序的結(jié)果是

S={9,8,1,7,6}。

依次退出，檢測(cè)是否影響其覆蓋完整性。通過(guò)測(cè)試發(fā)現(xiàn)節(jié)點(diǎn)7的退出不影響節(jié)點(diǎn)的覆蓋完整性，因此源節(jié)點(diǎn)2的MPR集為

M2={1,6,8,9}。

如果根據(jù)Global_OP_MPR選擇策略[7]，則在源節(jié)點(diǎn)2選擇MPR集時(shí)，節(jié)點(diǎn)7會(huì)被加入M2中且不能被剔除。

這個(gè)簡(jiǎn)單的實(shí)例顯示，在全局網(wǎng)絡(luò)選擇MPR節(jié)點(diǎn)時(shí)，對(duì)已被其他節(jié)點(diǎn)選中的節(jié)點(diǎn)做退出判斷后剔除冗余節(jié)點(diǎn)，能減少網(wǎng)絡(luò)中消息的洪泛數(shù)量。

2.3性能分析

G-MPR選擇策略能快速選取局部?jī)?yōu)化，減少相關(guān)性引起的冗余，從而獲得全局優(yōu)化，不會(huì)額外增加算法的時(shí)間復(fù)雜度，還能減少全局MPR集的節(jié)點(diǎn)數(shù)量和洪泛消息的數(shù)量。

在OLSR路由協(xié)議中，相鄰節(jié)點(diǎn)之間可以通過(guò)HELLO消息獲取相互的身份信息[9]。伴隨著網(wǎng)絡(luò)中節(jié)點(diǎn)拓?fù)涞目焖僮兓?，MPR節(jié)點(diǎn)選取是一個(gè)持續(xù)過(guò)程，在網(wǎng)絡(luò)節(jié)點(diǎn)初始化的過(guò)程中，大部分節(jié)點(diǎn)都沒(méi)有獲取到是否已被其他節(jié)點(diǎn)選中的信息[10]。隨著選取自己的MPR集，且選取時(shí)間不同，節(jié)點(diǎn)將能夠檢測(cè)到已被其他節(jié)點(diǎn)選為MPR節(jié)點(diǎn)的節(jié)點(diǎn)，此時(shí)該選擇策略將呈現(xiàn)出全局優(yōu)化的趨勢(shì)。

OLSR路由協(xié)議通過(guò)選取中繼節(jié)點(diǎn)集(MPRs)來(lái)代替全部的一跳鄰居節(jié)點(diǎn)，實(shí)現(xiàn)消息的傳遞，被選為MPR的節(jié)點(diǎn)相對(duì)其他節(jié)點(diǎn)，會(huì)不可避免地產(chǎn)生額外傳輸負(fù)擔(dān)[11]。隨著網(wǎng)絡(luò)拓?fù)涞淖兓?，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都有可能被選為MPR節(jié)點(diǎn)，最終，在網(wǎng)絡(luò)中的節(jié)點(diǎn)會(huì)基本達(dá)到負(fù)載均衡。

3仿真驗(yàn)證

驗(yàn)證基于G-MPR選擇策略的優(yōu)化鏈路路由 (Global-OptimizedLinkStateRouting,G-OLSR)協(xié)議在全局網(wǎng)絡(luò)中的性能。在不同場(chǎng)景下，對(duì)OLSR協(xié)議和G-OLSR協(xié)議在整個(gè)網(wǎng)絡(luò)中分別做時(shí)延和TC消息分組數(shù)比較。

3.1仿真環(huán)境

使用NS2.34仿真軟件，對(duì)基于G-MPR選擇策略的G-OLSR協(xié)議進(jìn)行驗(yàn)證。

根據(jù)汽車節(jié)點(diǎn)在路上的運(yùn)動(dòng)特性，選取平面式網(wǎng)絡(luò)結(jié)構(gòu)，MAC層使用IEEE802.11，采用Two-raygroundreflection無(wú)線傳輸模型[12]，仿真區(qū)域的范圍取為1 000m×1 000m，使用NS自帶的工具setdest生成節(jié)點(diǎn)隨機(jī)移動(dòng)模型，網(wǎng)絡(luò)場(chǎng)景中有60個(gè)節(jié)點(diǎn)，仿真時(shí)間400s，移動(dòng)模型中節(jié)點(diǎn)的移動(dòng)速率最小為0m/s，最大分別為1m/s，5m/s，10m/s，15m/s，20m/s，25m/s和30m/s共7種[9]，節(jié)點(diǎn)停留時(shí)間為0s，節(jié)點(diǎn)的無(wú)線覆蓋半徑默認(rèn)為250m，數(shù)據(jù)流的業(yè)務(wù)類型采用由NS自帶的流量生成器cbrgen工具所產(chǎn)生的CBR流，其中數(shù)據(jù)包大小為512Bytes，發(fā)送速率為10packet/s。

對(duì)各場(chǎng)景進(jìn)行多次仿真實(shí)驗(yàn)，將實(shí)驗(yàn)中采集的數(shù)據(jù)求其平均值。

3.2仿真結(jié)果

移動(dòng)速率和網(wǎng)絡(luò)中TC分組數(shù)量的關(guān)系如圖2所示。在7種不同移動(dòng)速率下，G-OLSR相比OLSR減少了TC消息的數(shù)量，這說(shuō)明G-OLSR選擇策略能有效減少全局網(wǎng)絡(luò)中MPR節(jié)點(diǎn)的數(shù)量，使MPR集得到優(yōu)化。

圖2　移動(dòng)速率和TC分組數(shù)

移動(dòng)速率和傳輸時(shí)延的關(guān)系如圖3所示。隨著節(jié)點(diǎn)運(yùn)動(dòng)速率的加快，OLSR的傳輸時(shí)延都會(huì)隨之加大，但G-OLSR因在全局網(wǎng)絡(luò)中有優(yōu)化的MPR集，能減少消息的洪泛，從而相比OLSR能減少時(shí)延。

圖3　移動(dòng)速率和節(jié)點(diǎn)時(shí)延

4結(jié)語(yǔ)

文中提出的G-MPR選擇策略能有效減少各個(gè)源節(jié)點(diǎn)之間選取MPR節(jié)點(diǎn)時(shí)相互之間的相關(guān)性，從全局上優(yōu)化了MPR選擇策略，減少了網(wǎng)絡(luò)中MPR集的冗余，達(dá)到全局網(wǎng)絡(luò)中洪泛消息的減少，從而提升網(wǎng)絡(luò)的性能。使用NS進(jìn)行移動(dòng)多點(diǎn)仿真，從仿真結(jié)果可以看出G-OLSR協(xié)議能有效減少網(wǎng)絡(luò)中消息的洪泛并減小網(wǎng)絡(luò)時(shí)延提升了網(wǎng)絡(luò)性能。

參考文獻(xiàn)

[1]孫友偉，溫雙濤．基于電力線通信的新型物聯(lián)網(wǎng)架構(gòu)[J].西安郵電大學(xué)學(xué)報(bào)，2014,19(3):43-48 [2015-09-30].http://mall.cnki.net/magazine/article/XAYD201403010.htm.DOI:10.13682/j.issn.2095-6533.2014.03.009.

[2]王勇斌，孫友偉．基于ES0191的電力線物聯(lián)網(wǎng)控制平臺(tái)[J].西安郵電大學(xué)學(xué)報(bào)，2014,19(03):49-53[2015-09-30].http://mall.cnki.net/magazine/article/XAYD201403011.htm.DOI:10.13682/j.issn.2095-6533.2014.03.010.

[3]張洪,高楊,等．一種新型MPR集選擇算法[J].成都大學(xué)學(xué)報(bào).2015.34(1):38-40[2015-09-30].http://mall.cnki.net/magazine/article/CDDD201501011.htm.

[4]楊彬,劉健,馮家剛.基于拓?fù)淇焖僮兓腛LSR改進(jìn)路由協(xié)議研究[J].計(jì)算機(jī)工程與應(yīng)用.2015,51(4):105-109[2015-09-30].http://mall.cnki.net/magazine/article/JSGG201504022.htm.DOI:10.3778/j.issn.1002-8331.1304-0356.

[5]PEREMontolio-Aranda,JOAQUINGarcia-Alfaro,DAVIDMegías.Improvedfloodingofbroadcastmessagesusingextendedmultipointrelaying[J].JournalofNetworkandComputerApplications. 2011.3(2):542-550[2015-09-30].http://www.sciencedirect.com/science/article/pii/S1084804510002225.DOI: 10.1016/j.jnca.2010.12.011.

[6]LEONARDOMaccari,RENATOLoCigno.HowtoreduceandstabilizeMPRsetsinOLSRnetworks[C]//ProceedingsoftheIEEE8thInternationalConferenceonWirelessandMobileComputing,NetworkingandCommunications.Piscataway:IEEE, 2012:373-380[2015-09-30].http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6379101.DOI:10.1109/WiMOB.2012.6379101.

[7]劉杰，王玲，王杉，等.基于OLSR協(xié)議的最小MPR集選擇算法[J].計(jì)算機(jī)應(yīng)用，2015,35(2):305-308,339[2015-09-30].http://mall.cnki.net/magazine/article/JSJY201502004.htm.DOI:10.11772 /j.issn.1001-9081.2015.02.0305.

[8]趙健,孫俊鎖.OLSR路由協(xié)議的改進(jìn)及其NS2仿真分析[J].計(jì)算機(jī)仿真.2008.25(1):161-163[2015-09-30].http://mall.cnki.net/magazine/article/JSJZ200801047.htm.

[9]陳立,楊瑞娟,戚浩,等．一種改進(jìn)的高動(dòng)態(tài)OLSR協(xié)議算法研究[J].無(wú)線電工程.2014,44(22):44-47,21[2015-09-30].http://mall.cnki.net/magazine/article/WXDG201412002.htm.DOI:10.3969/j.issn.1003-3106.2014.12.02.

[10] 鐘珞,趙先明,夏紅霞. 求解最小MPR集的蟻群算法與仿真[J]. 智能系統(tǒng)學(xué)報(bào).2011(02):166-171[2015-09-30].http://mall.cnki.net/magazine/article/ZNXT201102015.htm.DOI:10.3969/j.issn.1673-4785.2011.02.012.

[11] 蘭鵬,李二濤,何桂仙. 基于改進(jìn)OLSR路由協(xié)議mesh網(wǎng)絡(luò)的研究[J]. 杭州電子科技大學(xué)學(xué)報(bào). 2013(04):54-57[2015-09-30].http://mall.cnki.net/magazine/article/HXDY201304014.htm.DOI:10.3969/j.issn.1001-9146.2013.04.014.

[12] 張繼榮,趙曉彤,等．改進(jìn)的貪婪型周邊無(wú)狀態(tài)路由協(xié)議[J].西安郵電大學(xué)學(xué)報(bào).2015(04):16-19[2015-09-30].http://mall.cnki.net/magazine/article/XAYD201504003.htm.DOI:10.13682/j.issn.2095-6533.2015.04.003.

[責(zé)任編輯:瑞金]

Animprovedmultipointrelayselectionstrategyinoptimizedlinkstaterouting

SUNYouwei,ZHANGJing,WANGChenhuan

(SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:An improved multipoint relay selection strategy in optimized link state routing is proposed. When solving the relay node sets, take source node’s one hop neighbor nodes, which have been drawn in relay node set by other source nodes, as that with a higher two hop node overlay number, and pull them into the exiting inspection queue to reduce the redundancy of relay nodes in the network. Simulation results show that, when the nodes move at a speed of 1～30 m/s, using the improved selection algorithm can reduce the network delay by 1%～4%, and cut down the number of network topology control group by 2%～7%.

Keywords:optimized link state routing protocol (OLSR), greedy algorithm，relay node，local optimization，selection strategy

doi:10.13682/j.issn.2095-6533.2016.02.007

收稿日期：2015-10-20

作者簡(jiǎn)介：孫友偉(1956-)，男，教授，從事下一代通信網(wǎng)研究。E-mail: syw@xupt.edu.cn 張晶(1991-)，男，碩士研究生，研究方向?yàn)槲锫?lián)網(wǎng)技術(shù)及應(yīng)用。E-mail:296363682@qq.com

中圖分類號(hào)：TN913.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-6533(2016)02-0036-05