一种基于集合运算的MPR集选择算法

张 洪， 朱国全， 王俊杰

(1.成都大学 信息科学与工程学院, 四川 成都 610106； 2.成都大学 模式识别与智能信息处理四川省高校重点实验室, 四川 成都 610106)

一种基于集合运算的MPR集选择算法

张 洪1,2， 朱国全1， 王俊杰1

(1.成都大学 信息科学与工程学院, 四川 成都 610106； 2.成都大学 模式识别与智能信息处理四川省高校重点实验室, 四川 成都 610106)

在传统的OLSR协议中有MPR集和非MPR集2种转发节点.MPR集是在广播洪泛的过程中挑选的转发广播的节点，但在某些情况下传统的MPR集并不是最优的，这样网络节点也会转发不必要的数据，造成资源浪费.针对经典算法的不足之处，提出一种逆向思维的新型算法，通过循环和集合运算相结合的方法有效剔除无效冗余的节点，不仅能达到传统OLSR协议的效果，而且比传统OSLR协议的数据开销更小、效率更高.最后，通过仿真平台(OPNET)实现重新定义OLSR的MPR集算法.结果表明，该算法对于网络吞吐量、数据包传输时延有一定的提升.

OLSR；MPR；集合运算；仿真

0 引 言

在Ad Hoc网络中，节点具有报文转发能力，且节点间的通信可能要经过多个中间节点的转发，即经过多跳(Multi-hop)，这是Ad Hoc网络与其他移动网络的最根本区别.节点通过分层的网络协议和分布式算法相互协调，实现了网络的自动组织和运行.因此，Ad Hoc网是一种多跳的、无中心的自组织无线网络，又称为多跳网(Multi-hop Network)或自组织网(Self-organizing Network)[1].

1 OLSR与MPR

1.1 OLSR协议

优化链路状态路由(Optimized Link State Routing，OLSR)协议是一种基于最优化链路状态的表驱式路由协议.在OLSR协议中，通过选取多点中继(MultiPoint Relay，MPR)机制有效地减少了在洪泛过程中广播消息的转发数量，克服了表驱式路由协议中网络维护开销大的缺点，并广泛应用于大而密集的网络环境中.由于只有被选作MPR的节点才转发控制消息，且MPR节点只产生其与MPR选择节点间的链路状态信息，因此在OLSR协议中，MPR集的选取至关重要，将直接影响网络的性能[2-4].

1.2 MPR

1.2.1 MPR的定义.

OLSR协议的核心内容是多点中继技术MPR.在每个节点的邻节点中选取部分节点作为它的多点中继节点，这些被选为多点中继的节点可以拥有路由的功能，反之则没有路由功能.简单来说，在OLSR协议中每个节点的邻节点如果有路由功能，那么该节点就是MPR，反之就是非MPR.

1.2.2 传统OLSR协议选择MPR集的缺点.

广播中继泛洪的特例如图1所示.

图1 广播中继泛洪的特例

如果采用传统的OLSR协议选择MPR，那么选出来的MPR应为{a,b,d,f}或{a,c,f,d}或{a,e,b,d}或{a,c,e,d}.其选择过程如下：

Step1.把N的一跳邻居作为一个集合F、二跳邻居作为一个集合S.

Step2.由图1可以看出，在二跳邻居中的1、2这两个节点只与一个一跳邻居有关联，所以把d从F中选入MPR，同时把所有与d有关联的二跳邻居从S中移除，然后看集合S是否为空，如果为空则终止，反之继续下面的步骤.

Step3.把剩余的一跳邻居按与二跳邻居关联的二跳邻居的数目从大到小排序，在图1中即把a、b、c、e、f按与二跳邻居关联的数目从大到小排序，排序后的顺序为a,b,f,c,e.

Step4.先把最大的一跳邻居移到MPR.在图1中，即把a移到MPR，同时把与a有关的二跳邻居从S中删除，然后看集合S是否为空，如果为空则结束，反之从Step3继续执行直到集合S为空.

可见，按传统的方法，MPR可以为{a,b,d,f}、{a,c,f,d}、{a,e,b,d}、{a,c,e,d}之一.发生这种情况主要原因是排序时同等大小的位置是随机的.此外，从图1可以很容易看出，如果MPR={b,f,d}同样能满足要求，那么传统的方法有时就不是最优的.

2 重新定义MPR集的OLSR改进方案

2.1 更新的MPR集选择方案

针对经典的MPR选择算法，张洪等[5-6]利用集合的思路，使用数学算法对MPR集进行了改进，改进后的算法对于提升数据传输时延有一定的帮助，但由于计算过于复杂，因此算法收敛性不理想，张信明等[7]利用遗传算法找出了一种比较理想化的MPR选择方案，其对于极端的网络比较符合要求，但是针对普遍的网络结构，其效果不如经典的MPR选择算法.

在此基础上，本研究根据以前的研究经验和分析，提出了一种更新的MPR选择方案，并以实验仿真的方式验证了合理性.

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

Step1.假设全网泛洪，对一跳邻居用字母进行编号a,b,c,d，…，对二跳邻居用数字进行编号1,2,3,4，…，并设置MPR的初始值为空.

Step2.把每一个一跳邻居作为一个集合，该集合的元素为它能够连接的所有二跳邻居.把所有的一跳邻居作为集合F的元素，把所有的二跳邻居作为集合S的元素.

Step3.根据每一个一跳邻居所能连接的二跳邻居的数量给集合F(即一跳邻居)进行由小到大的排序，如遇到多个一跳邻居连接二跳邻居的数量相同，则按一跳邻居的编号字母排序.

Step4.根据排序后的集合F，首先，找到只属于一个一跳邻居的二跳邻居，然后把这个二跳邻居所能连接的一跳邻居直接从集合F放入MPR中，同时把该元素所连接的二跳邻居在集合S和集合F元素所连接的二跳邻居中做标记.如果没有这种情况的一跳邻居，那么就移除集合F中最小的元素，然后把移除后的集合F做并集，如果并集后集合F的元素所连接的没有被标记的二跳邻居和集合S的元素所连接的没有被标记的二跳邻居完全相同，则该元素真正被移除，反之则把该元素移到MPR，同时把该元素所连接的二跳邻居在集合S和集合F元素所连接的二跳邻居中做标记.每次有元素移到MPR时，都需要对MPR做并集，判断并集后MPR元素所连接的二跳邻居是否与集合S的元素完全相同，如果相同则算法结束.

Step5.重复第4步，直到所有的MPR集中的元素被完全遍历，算法结束.

针对图1的情形，本研究做以下详细说明，对上述算法过程进行演示.

Step1.将一跳邻居用a、b、c、d、e、f进行编号，二跳邻居用1、2、3、4、5、6、7、8、9、10、11、12进行编号，然后定义MPR为空.

Step2.统计a、b、c、d、e、f各自的元素数量，然后根据元素的数量从大到小排序，

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中标记1与2，并对MPR里的元素做并集，

d∪d={1,2}

d∪d≠S(标记的也要算进去)

Step4.忽略已标记的二跳邻居，看是否有专属二跳邻居的一跳邻居，

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}

可见，这次没有专属二跳邻居的一跳邻居.然后，根据Step2排序后的集合F移除最小的元素，由于Step3已把d移到MPR，所以现有的集合F={a,b,f,c,e}，应该移除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.忽略已标记的二跳邻居，看是否有专属二跳邻居的一跳邻居，

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，然后标记与f有关的二跳邻居3、4、5、6、7，最后把MPR做并集，看是否等于集合S(把标记的节点也算进去)，

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

d∪f≠S

由于d∪f≠S，所以继续下面的步骤.

Step6.忽略已标记的二跳邻居，看是否有专属二跳邻居的一跳邻居，

a={8，9，10}

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

c={11，12}

可见，这次没有专属二跳邻居的一跳邻居.根据Step2排序后的集合F，移除最小的元素.由于Step3、Step5已把d、f移到MPR，step4从F中去除了e，所以现有集合F={a,b,c}.去除c，这时集合F={a,b}，然后a与b做并集，

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

a∪b=S

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

Step7.忽略已标记的二跳邻居，看是否有专属二跳邻居的一跳邻居，

a={8,9,10}

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

b有专属的二跳邻居，所以b只能选为MPR，同时标记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，算法结束.

2.2 仿真实验

本研究采用当前比较流行的OPNET网络仿真软件对算法进行验证.实验中，采用成熟的Ad Hoc网络模型建模，网络通信MAC底层采用IEEE 802.11通信协议，以CSMA/CA方式接入，物理层采用扩频调频方式，路由层采用表驱动的经典路由协议OLSR算法[8-9].

在网络环境设置中，由于节点通信半径和节点移动速度有限，通常节点通信半径最大为300 m，节点移动速度为5 m/s，因此网络面积设定在3 km×3 km范围，符合本实验要求.同时，由于节点移动方向不确定，为了保证仿真结果，本实验设置25个随机移动节点，可以保障路由的健壮性.

按照无线自组织网络的特性要求，本研究对该算法的2个性能进行仿真：数据传输成功率和数据传输时延[10].

仿真实验结果如图2、图3所示.

图2 数据传输成功率对比图

图3 数据传输时延对比图

图2表明，由于改进后的MPR集可以最大限度提升MPR的有效性，减少冗余数据的传输，因此数据传输成功率有比较大的提升.同时，由于本算法与经典的OLSR算法相比具有一定的复杂性，尤其是用集合处理MPR集时，该算法的实际传输时延比经典算法有一定的增加(见图3).但综合分析来看，这样的时延相比传输成功率来说是值得的.

3 结 语

本研究通过对传统OLSR路由协议的MPR集进行分析发现，经典的MPR集对于常见的网络环境还是比较符合减少转发数据包的要求，但对于比较复杂或者特殊的网络结构来说，其减少转发节点的能力比较有限.对此，本研究通过循环与集合运算相协助的方法，找到了一种最新、最有效的MPR选择算法，使得网络的数据传输成功率得到了比较大的提升.当然，对于传统的移动自组织网络，经典的MPR选择算法仍具有时延较小等优势.因此，下一步本研究的方向是进一步寻找传统与改进的MPR选择算法的集合，使之在不同的网络环境下，都可以得到最优的网络性能.

[1]张洪.高速移动自组网OLSR路由协议研究与改进[D].成都:西南交通大学，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]张洪,王传真,陈海霞，等.基于最优子集的MPR选择算法研究[J].成都大学学报(自然科学版)，2015,34(2):156-159.

[6]张洪,高杨.一种新型的MPR选择算法[J].成都大学学报(自然科学版)，2015,34(1):38-40.

[7]张信明,曾依灵,干国政，等.用遗传算法寻找OLSR协议的最小MPR集[J].软件学报,2006,17(4):932-938.

[8]卢宇,魏敏,吴钦章.基于MAC层信息的OLSR改进方案[J].计算机工程,2007,33(22):121-123.

[9]陈文宇,陈洁莲,孙世新.面向链路状态信息的路由算法LSDSR[J].电子科技大学学报(自然科学版),2009,38(6):993-996.

[10]张洪,黄闽英.基于高速移动节点网络的OLSR路由协议改进[J].成都大学学报(自然科学版),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.

成都大学校青年基金(2016XJZ14)资助项目.

张 洪(1980 — )， 男， 博士， 副教授， 从事计算机网络体系结构研究.

TP393.06；TN929.5

A