張 洪， 朱國全， 王俊杰

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

一種基于集合運算的MPR集選擇算法

張 洪1,2， 朱國全1， 王俊杰1

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

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

OLSR；MPR；集合運算；仿真

0 引 言

在Ad Hoc網(wǎng)絡(luò)中，節(jié)點具有報文轉(zhuǎn)發(fā)能力，且節(jié)點間的通信可能要經(jīng)過多個中間節(jié)點的轉(zhuǎn)發(fā)，即經(jīng)過多跳(Multi-hop)，這是Ad Hoc網(wǎng)絡(luò)與其他移動網(wǎng)絡(luò)的最根本區(qū)別.節(jié)點通過分層的網(wǎng)絡(luò)協(xié)議和分布式算法相互協(xié)調(diào)，實現(xiàn)了網(wǎng)絡(luò)的自動組織和運行.因此，Ad Hoc網(wǎng)是一種多跳的、無中心的自組織無線網(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é)議中，通過選取多點中繼(MultiPoint Relay，MPR)機制有效地減少了在洪泛過程中廣播消息的轉(zhuǎn)發(fā)數(shù)量，克服了表驅(qū)式路由協(xié)議中網(wǎng)絡(luò)維護開銷大的缺點，并廣泛應(yīng)用于大而密集的網(wǎng)絡(luò)環(huán)境中.由于只有被選作MPR的節(jié)點才轉(zhuǎn)發(fā)控制消息，且MPR節(jié)點只產(chǎn)生其與MPR選擇節(jié)點間的鏈路狀態(tài)信息，因此在OLSR協(xié)議中，MPR集的選取至關(guān)重要，將直接影響網(wǎng)絡(luò)的性能[2-4].

1.2 MPR

1.2.1 MPR的定義.

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

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

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

圖1 廣播中繼泛洪的特例

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

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

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

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

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

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

2 重新定義MPR集的OLSR改進方案

2.1 更新的MPR集選擇方案

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

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

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

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

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

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

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

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

針對圖1的情形，本研究做以下詳細說明，對上述算法過程進行演示.

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

Step2.統(tǒng)計a、b、c、d、e、f各自的元素數(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，同時在S中標(biāo)記1與2，并對MPR里的元素做并集，

d∪d={1,2}

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

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}

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

a∪b∪f∪c={3，4，5，6，7，8，9，10，11，12}

a∪b∪f∪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}

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

d∪f={1,2,3,4,5,6,7}

d∪f≠S

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

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

a={8，9，10}

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

c={11，12}

可見，這次沒有專屬二跳鄰居的一跳鄰居.根據(jù)Step2排序后的集合F，移除最小的元素.由于Step3、Step5已把d、f移到MPR，step4從F中去除了e，所以現(xiàn)有集合F={a,b,c}.去除c，這時集合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，同時標(biāo)記8、9、10、11、12，這時MPR={d,f,b}.然后MPR中的元素做并集，

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

d∪f∪b=S

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

2.2 仿真實驗

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

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

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

仿真實驗結(jié)果如圖2、圖3所示.

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

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

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

3 結(jié) 語

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

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

[2]楊光.LTE助推信息消費[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é)報(自然科學(xué)版)，2015,34(2):156-159.

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

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

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

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

[10]張洪,黃閩英.基于高速移動節(jié)點網(wǎng)絡(luò)的OLSR路由協(xié)議改進[J].成都大學(xué)學(xué)報(自然科學(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)資助項目.

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

TP393.06；TN929.5

A