一種基于集合運(yùn)算的MPR集選擇算法

張 洪， 朱國(guó)全， 王俊杰

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都 610106； 2.成都大學(xué) 模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室, 四川 成都 610106)

一種基于集合運(yùn)算的MPR集選擇算法

張 洪1,2， 朱國(guó)全1， 王俊杰1

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院, 四川 成都 610106； 2.成都大學(xué) 模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室, 四川 成都 610106)

在傳統(tǒng)的OLSR協(xié)議中有MPR集和非MPR集2種轉(zhuǎn)發(fā)節(jié)點(diǎn).MPR集是在廣播洪泛的過(guò)程中挑選的轉(zhuǎn)發(fā)廣播的節(jié)點(diǎn)，但在某些情況下傳統(tǒng)的MPR集并不是最優(yōu)的，這樣網(wǎng)絡(luò)節(jié)點(diǎn)也會(huì)轉(zhuǎn)發(fā)不必要的數(shù)據(jù)，造成資源浪費(fèi).針對(duì)經(jīng)典算法的不足之處，提出一種逆向思維的新型算法，通過(guò)循環(huán)和集合運(yùn)算相結(jié)合的方法有效剔除無(wú)效冗余的節(jié)點(diǎn)，不僅能達(dá)到傳統(tǒng)OLSR協(xié)議的效果，而且比傳統(tǒng)OSLR協(xié)議的數(shù)據(jù)開(kāi)銷(xiāo)更小、效率更高.最后，通過(guò)仿真平臺(tái)(OPNET)實(shí)現(xiàn)重新定義OLSR的MPR集算法.結(jié)果表明，該算法對(duì)于網(wǎng)絡(luò)吞吐量、數(shù)據(jù)包傳輸時(shí)延有一定的提升.

OLSR；MPR；集合運(yùn)算；仿真

0 引 言

在Ad Hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)具有報(bào)文轉(zhuǎn)發(fā)能力，且節(jié)點(diǎn)間的通信可能要經(jīng)過(guò)多個(gè)中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)，即經(jīng)過(guò)多跳(Multi-hop)，這是Ad Hoc網(wǎng)絡(luò)與其他移動(dòng)網(wǎng)絡(luò)的最根本區(qū)別.節(jié)點(diǎn)通過(guò)分層的網(wǎng)絡(luò)協(xié)議和分布式算法相互協(xié)調(diào)，實(shí)現(xiàn)了網(wǎng)絡(luò)的自動(dòng)組織和運(yùn)行.因此，Ad Hoc網(wǎng)是一種多跳的、無(wú)中心的自組織無(wú)線網(wǎng)絡(luò)，又稱為多跳網(wǎng)(Multi-hop Network)或自組織網(wǎng)(Self-organizing Network)[1].

1 OLSR與MPR

1.1 OLSR協(xié)議

優(yōu)化鏈路狀態(tài)路由(Optimized Link State Routing，OLSR)協(xié)議是一種基于最優(yōu)化鏈路狀態(tài)的表驅(qū)式路由協(xié)議.在OLSR協(xié)議中，通過(guò)選取多點(diǎn)中繼(MultiPoint Relay，MPR)機(jī)制有效地減少了在洪泛過(guò)程中廣播消息的轉(zhuǎn)發(fā)數(shù)量，克服了表驅(qū)式路由協(xié)議中網(wǎng)絡(luò)維護(hù)開(kāi)銷(xiāo)大的缺點(diǎn)，并廣泛應(yīng)用于大而密集的網(wǎng)絡(luò)環(huán)境中.由于只有被選作MPR的節(jié)點(diǎn)才轉(zhuǎn)發(fā)控制消息，且MPR節(jié)點(diǎn)只產(chǎn)生其與MPR選擇節(jié)點(diǎn)間的鏈路狀態(tài)信息，因此在OLSR協(xié)議中，MPR集的選取至關(guān)重要，將直接影響網(wǎng)絡(luò)的性能[2-4].

1.2 MPR

1.2.1 MPR的定義.

OLSR協(xié)議的核心內(nèi)容是多點(diǎn)中繼技術(shù)MPR.在每個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)中選取部分節(jié)點(diǎn)作為它的多點(diǎn)中繼節(jié)點(diǎn)，這些被選為多點(diǎn)中繼的節(jié)點(diǎn)可以擁有路由的功能，反之則沒(méi)有路由功能.簡(jiǎn)單來(lái)說(shuō)，在OLSR協(xié)議中每個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)如果有路由功能，那么該節(jié)點(diǎn)就是MPR，反之就是非MPR.

1.2.2 傳統(tǒng)OLSR協(xié)議選擇MPR集的缺點(diǎn).

廣播中繼泛洪的特例如圖1所示.

圖1 廣播中繼泛洪的特例

如果采用傳統(tǒng)的OLSR協(xié)議選擇MPR，那么選出來(lái)的MPR應(yīng)為{a,b,d,f}或{a,c,f,d}或{a,e,b,d}或{a,c,e,d}.其選擇過(guò)程如下：

Step1.把N的一跳鄰居作為一個(gè)集合F、二跳鄰居作為一個(gè)集合S.

Step2.由圖1可以看出，在二跳鄰居中的1、2這兩個(gè)節(jié)點(diǎn)只與一個(gè)一跳鄰居有關(guān)聯(lián)，所以把d從F中選入MPR，同時(shí)把所有與d有關(guān)聯(lián)的二跳鄰居從S中移除，然后看集合S是否為空，如果為空則終止，反之繼續(xù)下面的步驟.

Step3.把剩余的一跳鄰居按與二跳鄰居關(guān)聯(lián)的二跳鄰居的數(shù)目從大到小排序，在圖1中即把a(bǔ)、b、c、e、f按與二跳鄰居關(guān)聯(lián)的數(shù)目從大到小排序，排序后的順序?yàn)閍,b,f,c,e.

Step4.先把最大的一跳鄰居移到MPR.在圖1中，即把a(bǔ)移到MPR，同時(shí)把與a有關(guān)的二跳鄰居從S中刪除，然后看集合S是否為空，如果為空則結(jié)束，反之從Step3繼續(xù)執(zhí)行直到集合S為空.

可見(jiàn)，按傳統(tǒng)的方法，MPR可以為{a,b,d,f}、{a,c,f,d}、{a,e,b,d}、{a,c,e,d}之一.發(fā)生這種情況主要原因是排序時(shí)同等大小的位置是隨機(jī)的.此外，從圖1可以很容易看出，如果MPR={b,f,d}同樣能滿足要求，那么傳統(tǒng)的方法有時(shí)就不是最優(yōu)的.

2 重新定義MPR集的OLSR改進(jìn)方案

2.1 更新的MPR集選擇方案

針對(duì)經(jīng)典的MPR選擇算法，張洪等[5-6]利用集合的思路，使用數(shù)學(xué)算法對(duì)MPR集進(jìn)行了改進(jìn)，改進(jìn)后的算法對(duì)于提升數(shù)據(jù)傳輸時(shí)延有一定的幫助，但由于計(jì)算過(guò)于復(fù)雜，因此算法收斂性不理想，張信明等[7]利用遺傳算法找出了一種比較理想化的MPR選擇方案，其對(duì)于極端的網(wǎng)絡(luò)比較符合要求，但是針對(duì)普遍的網(wǎng)絡(luò)結(jié)構(gòu)，其效果不如經(jīng)典的MPR選擇算法.

在此基礎(chǔ)上，本研究根據(jù)以前的研究經(jīng)驗(yàn)和分析，提出了一種更新的MPR選擇方案，并以實(shí)驗(yàn)仿真的方式驗(yàn)證了合理性.

本研究提出的更新的MPR集算法如下：

Step1.假設(shè)全網(wǎng)泛洪，對(duì)一跳鄰居用字母進(jìn)行編號(hào)a,b,c,d，…，對(duì)二跳鄰居用數(shù)字進(jìn)行編號(hào)1,2,3,4，…，并設(shè)置MPR的初始值為空.

Step2.把每一個(gè)一跳鄰居作為一個(gè)集合，該集合的元素為它能夠連接的所有二跳鄰居.把所有的一跳鄰居作為集合F的元素，把所有的二跳鄰居作為集合S的元素.

Step3.根據(jù)每一個(gè)一跳鄰居所能連接的二跳鄰居的數(shù)量給集合F(即一跳鄰居)進(jìn)行由小到大的排序，如遇到多個(gè)一跳鄰居連接二跳鄰居的數(shù)量相同，則按一跳鄰居的編號(hào)字母排序.

Step4.根據(jù)排序后的集合F，首先，找到只屬于一個(gè)一跳鄰居的二跳鄰居，然后把這個(gè)二跳鄰居所能連接的一跳鄰居直接從集合F放入MPR中，同時(shí)把該元素所連接的二跳鄰居在集合S和集合F元素所連接的二跳鄰居中做標(biāo)記.如果沒(méi)有這種情況的一跳鄰居，那么就移除集合F中最小的元素，然后把移除后的集合F做并集，如果并集后集合F的元素所連接的沒(méi)有被標(biāo)記的二跳鄰居和集合S的元素所連接的沒(méi)有被標(biāo)記的二跳鄰居完全相同，則該元素真正被移除，反之則把該元素移到MPR，同時(shí)把該元素所連接的二跳鄰居在集合S和集合F元素所連接的二跳鄰居中做標(biāo)記.每次有元素移到MPR時(shí)，都需要對(duì)MPR做并集，判斷并集后MPR元素所連接的二跳鄰居是否與集合S的元素完全相同，如果相同則算法結(jié)束.

Step5.重復(fù)第4步，直到所有的MPR集中的元素被完全遍歷，算法結(jié)束.

針對(duì)圖1的情形，本研究做以下詳細(xì)說(shuō)明，對(duì)上述算法過(guò)程進(jìn)行演示.

Step1.將一跳鄰居用a、b、c、d、e、f進(jìn)行編號(hào)，二跳鄰居用1、2、3、4、5、6、7、8、9、10、11、12進(jìn)行編號(hào)，然后定義MPR為空.

Step2.統(tǒng)計(jì)a、b、c、d、e、f各自的元素?cái)?shù)量，然后根據(jù)元素的數(shù)量從大到小排序，

a={5,6,7,8,9,10}

b={8,9,10,11,12}

c={11，12}

d={1，2}

e={3，4}

f={3，4，5，6，7}

S={1，2，3，4，5，6，7，8，9，10，11，12}

排序前：F={a,b,c,d,e,f}

排序后：F={a,b,f,c,d,e}

Step3.首先，找出像d集合這樣有專屬二跳鄰居的一跳鄰居；d；然后，把d放入MPR，同時(shí)在S中標(biāo)記1與2，并對(duì)MPR里的元素做并集，

d∪d={1,2}

d∪d≠S(標(biāo)記的也要算進(jìn)去)

Step4.忽略已標(biāo)記的二跳鄰居，看是否有專屬二跳鄰居的一跳鄰居，

a={5,6,7,8,9,10}

b={8,9,10,11,12}

c={11，12}

e={3，4}

f={3，4，5，6，7}

可見(jiàn)，這次沒(méi)有專屬二跳鄰居的一跳鄰居.然后，根據(jù)Step2排序后的集合F移除最小的元素，由于Step3已把d移到MPR，所以現(xiàn)有的集合F={a,b,f,c,e}，應(yīng)該移除e，這時(shí)集合F={a,b,f,c}，對(duì)a、b、f、c做并集，

a∪b∪f(wàn)∪c={3，4，5，6，7，8，9，10，11，12}

a∪b∪f(wàn)∪c=S

由此，a可以徹底被移除.

Step5.忽略已標(biāo)記的二跳鄰居，看是否有專屬二跳鄰居的一跳鄰居，

a={5,6,7,8,9,10}

b={8,9,10,11,12}

c={11，12}

f={3，4，5，6，7}

可見(jiàn)，f是有專屬二跳鄰居的一跳鄰居.先把f移入MPR，然后標(biāo)記與f有關(guān)的二跳鄰居3、4、5、6、7，最后把MPR做并集，看是否等于集合S(把標(biāo)記的節(jié)點(diǎn)也算進(jìn)去)，

d∪f(wàn)={1,2,3,4,5,6,7}

d∪f(wàn)≠S

由于d∪f(wàn)≠S，所以繼續(xù)下面的步驟.

Step6.忽略已標(biāo)記的二跳鄰居，看是否有專屬二跳鄰居的一跳鄰居，

a={8，9，10}

b={8,9,10,11,12}

c={11，12}

可見(jiàn)，這次沒(méi)有專屬二跳鄰居的一跳鄰居.根據(jù)Step2排序后的集合F，移除最小的元素.由于Step3、Step5已把d、f移到MPR，step4從F中去除了e，所以現(xiàn)有集合F={a,b,c}.去除c，這時(shí)集合F={a,b}，然后a與b做并集，

a∪b={8,9,10,11,12}

a∪b=S

由此，c可以徹底被移除.

Step7.忽略已標(biāo)記的二跳鄰居，看是否有專屬二跳鄰居的一跳鄰居，

a={8,9,10}

b={8,9,10,11,12}

b有專屬的二跳鄰居，所以b只能選為MPR，同時(shí)標(biāo)記8、9、10、11、12，這時(shí)MPR={d,f,b}.然后MPR中的元素做并集，

d∪f(wàn)∪b={1,2,3,4,5,6,7,8,9,10,11,12}

d∪f(wàn)∪b=S

由于MPR元素的并集等于集合S，算法結(jié)束.

2.2 仿真實(shí)驗(yàn)

本研究采用當(dāng)前比較流行的OPNET網(wǎng)絡(luò)仿真軟件對(duì)算法進(jìn)行驗(yàn)證.實(shí)驗(yàn)中，采用成熟的Ad Hoc網(wǎng)絡(luò)模型建模，網(wǎng)絡(luò)通信MAC底層采用IEEE 802.11通信協(xié)議，以CSMA/CA方式接入，物理層采用擴(kuò)頻調(diào)頻方式，路由層采用表驅(qū)動(dòng)的經(jīng)典路由協(xié)議OLSR算法[8-9].

在網(wǎng)絡(luò)環(huán)境設(shè)置中，由于節(jié)點(diǎn)通信半徑和節(jié)點(diǎn)移動(dòng)速度有限，通常節(jié)點(diǎn)通信半徑最大為300 m，節(jié)點(diǎn)移動(dòng)速度為5 m/s，因此網(wǎng)絡(luò)面積設(shè)定在3 km×3 km范圍，符合本實(shí)驗(yàn)要求.同時(shí)，由于節(jié)點(diǎn)移動(dòng)方向不確定，為了保證仿真結(jié)果，本實(shí)驗(yàn)設(shè)置25個(gè)隨機(jī)移動(dòng)節(jié)點(diǎn)，可以保障路由的健壯性.

按照無(wú)線自組織網(wǎng)絡(luò)的特性要求，本研究對(duì)該算法的2個(gè)性能進(jìn)行仿真：數(shù)據(jù)傳輸成功率和數(shù)據(jù)傳輸時(shí)延[10].

仿真實(shí)驗(yàn)結(jié)果如圖2、圖3所示.

圖2 數(shù)據(jù)傳輸成功率對(duì)比圖

圖3 數(shù)據(jù)傳輸時(shí)延對(duì)比圖

圖2表明，由于改進(jìn)后的MPR集可以最大限度提升MPR的有效性，減少冗余數(shù)據(jù)的傳輸，因此數(shù)據(jù)傳輸成功率有比較大的提升.同時(shí)，由于本算法與經(jīng)典的OLSR算法相比具有一定的復(fù)雜性，尤其是用集合處理MPR集時(shí)，該算法的實(shí)際傳輸時(shí)延比經(jīng)典算法有一定的增加(見(jiàn)圖3).但綜合分析來(lái)看，這樣的時(shí)延相比傳輸成功率來(lái)說(shuō)是值得的.

3 結(jié) 語(yǔ)

本研究通過(guò)對(duì)傳統(tǒng)OLSR路由協(xié)議的MPR集進(jìn)行分析發(fā)現(xiàn)，經(jīng)典的MPR集對(duì)于常見(jiàn)的網(wǎng)絡(luò)環(huán)境還是比較符合減少轉(zhuǎn)發(fā)數(shù)據(jù)包的要求，但對(duì)于比較復(fù)雜或者特殊的網(wǎng)絡(luò)結(jié)構(gòu)來(lái)說(shuō)，其減少轉(zhuǎn)發(fā)節(jié)點(diǎn)的能力比較有限.對(duì)此，本研究通過(guò)循環(huán)與集合運(yùn)算相協(xié)助的方法，找到了一種最新、最有效的MPR選擇算法，使得網(wǎng)絡(luò)的數(shù)據(jù)傳輸成功率得到了比較大的提升.當(dāng)然，對(duì)于傳統(tǒng)的移動(dòng)自組織網(wǎng)絡(luò)，經(jīng)典的MPR選擇算法仍具有時(shí)延較小等優(yōu)勢(shì).因此，下一步本研究的方向是進(jìn)一步尋找傳統(tǒng)與改進(jìn)的MPR選擇算法的集合，使之在不同的網(wǎng)絡(luò)環(huán)境下，都可以得到最優(yōu)的網(wǎng)絡(luò)性能.

[1]張洪.高速移動(dòng)自組網(wǎng)OLSR路由協(xié)議研究與改進(jìn)[D].成都:西南交通大學(xué)，2007.

[2]楊光.LTE助推信息消費(fèi)[J].通信世界，2013，15(20)：25-26.

[3]Xian Y，Tian F，Xu C，et al．AnalysisofM-LWDFfairnessandanenhancedM-LWDFpacketschedulingmechanism[J]．J Chin Univ Posts Telecomm，2011,18(4):82-88．

[4]Alfayly A,Mkwawa I,Sun L,et al．QoE-basedperformanceevaluationofschedulingalgorithmsoverLTE[C]//Procofthe2012IEEEGlobecomWorkshops．Anaheim,California,USA:IEEE Press，2012:1362-1366.

[5]張洪,王傳真,陳海霞，等.基于最優(yōu)子集的MPR選擇算法研究[J].成都大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015,34(2):156-159.

[6]張洪,高楊.一種新型的MPR選擇算法[J].成都大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015,34(1):38-40.

[7]張信明,曾依靈,干國(guó)政，等.用遺傳算法尋找OLSR協(xié)議的最小MPR集[J].軟件學(xué)報(bào),2006,17(4):932-938.

[8]盧宇,魏敏,吳欽章.基于MAC層信息的OLSR改進(jìn)方案[J].計(jì)算機(jī)工程,2007,33(22):121-123.

[9]陳文宇,陳潔蓮,孫世新.面向鏈路狀態(tài)信息的路由算法LSDSR[J].電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,38(6):993-996.

[10]張洪,黃閩英.基于高速移動(dòng)節(jié)點(diǎn)網(wǎng)絡(luò)的OLSR路由協(xié)議改進(jìn)[J].成都大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,27(1):38-40.

Selection Algorithm of MPRs Based on Set Operation

ZHANGHong1,2,ZHUGuoquan1,WANGJunjie1

(1.School of Information Science and Engineering, Chengdu 610106, China; 2.Key Laboratory of Pattern Recognition and Intelligent Information Processing of Sichuan Province, Chengdu University, Chengdu 610106, China)

There are two kinds of forwarding nodes in OLSR protocol,MPRs and non-MPRs.The MPRs is selected as the forwarding node in the broadcast flooding,but the MPRs is not the best under certain conditions.Thus,the network node will transmit the unnecessary data,resulting in the waste of resources.Aiming at the shortcomings of traditional algorithms,this paper proposes a new algorithm based on reverse thinking,which can eliminate the invalid redundant nodes effectively by combining the circulation method and the set operation.In this way,the effects of the traditional OLSR protocol can be achieved.Compared with the traditional OLSR protocol,the new algorithm is more efficient with less data overhead.At last,the paper redefines the algorithm of MPRs of OLSR by simulation platform,OPNET.According to the results,the algorithm improves the network throughput,time lapse of packet transmission obviously.

OLSR;MPR;set operation;simulation

1004-5422(2017)01-0051-04

2016-10-19.

成都大學(xué)校青年基金(2016XJZ14)資助項(xiàng)目.

張 洪(1980 — )， 男， 博士， 副教授， 從事計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)研究.

TP393.06；TN929.5

A