优化链路状态路由多点中继选择策略改进

孙友伟， 张　晶， 王辰寰

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

优化链路状态路由多点中继选择策略改进

孙友伟， 张晶， 王辰寰

(西安邮电大学 通信与信息工程学院， 陕西 西安 710121)

摘要:对优化链路状态路由协议中多点中继选择策略加以改进。在求解中继节点集时，对源节点的一跳邻居节点中已被其他源节点选进中继节点集的节点，视其具有较高二跳节点覆盖数，并将其加入退出检测队列，以减少网络中继节点的冗余。仿真结果显示，在节点速率为1～30 m/s时，改进策略能够降低网络时延1%～4%，减少网络拓扑控制分组2%～7%。

关键词:优化链路状态路由协议；贪心算法；中继节点；局部优化；选择策略

作为信息技术的重要组成部分,被纳入重大发展规划的物联网技术已深入到了人们日常生活的各个方面[1]：智能家庭可用电力线进行载波通信，以方便各种家用电器进行数据通信[2]；交通智能化领域则采用无线通信技术实现车辆间的相互连接，以实现汽车互联网。

汽车互联网是一种特殊的移动自组织网络(adhoc)。移动自组织网络具有自组织，无中心，多跳路由和动态拓扑的特点。优化链路状态路由(OptimizedLinkStateRouting，OLSR)是adhoc网络中常用的路由协议,其关键概念是消息的多点转播，主要通过选取多个中继节点(MultiPointRelay，MPR)来代替全部的一跳节点转发消息[3]。MPR集是在消息广播洪泛的过程中由MPR选择者节点挑选的转发消息的节点集。在优化链路协议中，链路拓扑控制信息 (TopologyControl，TC)是由MPR集中的节点产生的。这种机制可克服表驱动式路由协议中网络维护开销大的缺点[4]，但传统优化链路状态路由中MPR集的选取使用贪心策略，而此策略并不从整体优化上加以考虑，只是通过局部优化来求得一种近似最优解，不能有效减少整个网络中洪泛的信息数量[5]，容易造成网络堵塞。

本文给出一种全局性选择策略(Global-MultiPointRelay,G-MPR)，以继承贪心策略简单高效的优点，并综合考虑全局优化且无法回避各源节点之间选择的关联性，在符合MPR选择准则的基础上减小其对选取的影响，使其达到近似最优。

1MPR集选择准则及问题

1.1传统MPR集选择准则

传统OLSR路由协议中MPR选择策略比较简单，其每个节点相对独立地选择各自的MPR集。MPR集的选取需要满足两个条件：首先，源节点所选取的MPR集应全部取自源节点的一跳邻居节点。其次，选定的MPR集须覆盖源节点的所有二跳邻居节点。MPR选择的问题就是在符合以上两个条件的情况下，使得MPR集的成员节点数最少。

1.2存在的问题

传统的选择策略使用贪心策略，正是由于贪心策略仅采用一跳邻居节点的覆盖数作为衡量尺度，因此求解的近似解很大程度上带有冗余，且其只针对局部求最小集，没有做全局考虑。

关于MPR的改进大多局限于单个节点的MPR集选择策略，并未考虑多节点的选择情况(图1)，要减少网络中产生的信息分组数，必须降低整个网络的MPR节点。仅仅意识到从全局考虑选择MPR集的重要性[6]，但缺乏一种具体优化的选择策略，想提高MPR链路的稳定性还远远不够。全局选择策略(Global_OP_MPR)[7]引入了全局因素，但策略第三步将一跳节点中已被其他源节点选为MPR节点,且转发承载值不为0的所有节点,加入MPR集中，即源节点的一跳邻居节点中有一些节点早已经被默认选为MPR节点。这种选择策略势必造成节点间的关联性增加，且某源节点选择MPR节点时需要依赖其他节点所选择的MPR节点，不做任何判断地将其他节点所选MPR节点加入本节点的MPR集，会在很大程度上干扰原MPR选择策略，造成整个网络冗余度大幅增加。

图1　一个自组织网络的简单拓扑

在整个网络中，各源节点选取各自MPR节点时互相存在的关联性，除过第一个选取MPR集的节点，所有的其他源节点被迫选择一个不仅大于最小的，而且大于在不考虑其他源节点的情况下选择的MPR集。由于现实网络中节点众多，这种关联性造成的冗余可能会大幅度的增加，使网络中洪泛的信息量增加[8]，从而导致信息拥塞。

2改进的选择策略

2.1G-MPR选择策略

在G-MPR选择策略中，对于已被其他源节点选入MPR集的一跳邻居节点，且其转发承载值不为0，则默认其有高的优先权，也加入退出判断行列中。G-MPR选择策略是一种能使全局网络中MPR节点数达到优化的改进策略，具体描述如下。

步骤1定义源节点i的MPR集为S。

步骤2对于一跳邻居节点N1(i)中所有节点，计算他们各自在二跳邻居节点N2(i)中能覆盖的节点个数。

步骤3检测N1(i)中所有节点，选出其中已被其他源节点选为MPR的节点,并判断其转发承载值是否为0，若为0则将其从N1(i)中剔除；然后分别将未被其他源节点选为MPR的节点和已被选为MPR的节点,按照每个节点在二跳邻居节点集中的覆盖数,从小到大进行各自排序；分别将未被其他源节点选中和已被选中的两部分，先后加入S集。

步骤4按照S集中节点的顺序，将节点依次退出，每次查看N2(i)中是否还有未被S中其他任何节点覆盖的节点，如果存在则说明该节点不能退出S，否则，将此节点退出S。

从多个源节点选取MPR节点的角度出发，考虑已被其他节点选为MPR的节点在整个网络中的特殊性，将已被其他源节点选为MPR的节点集和剩余节点集分为两部分各自排序，然后重新整合，最后执行退出检测策略。这种新策略给已被其他源节点选为MPR的节点赋予更高的优先权，默认其有多的覆盖数，既能减少整个网络的MPR节点数，也能减小相关性引起的冗余。

2.2实例分析

依据改进的选择策略，对图1所示实例，求解整个网络的MPR节点集。

假设源节点1先选取MPR节点，因此，选取不受源节点2的关联性影响，源节点1的MPR集为

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

源节点2的一跳邻居节点

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

节点6和7已被源节点1选定，且N1中的节点在二跳邻居节点的覆盖数分别是{3,4,2,3,2}，根据步骤3分别排序的结果是

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

依次退出，检测是否影响其覆盖完整性。通过测试发现节点7的退出不影响节点的覆盖完整性，因此源节点2的MPR集为

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

如果根据Global_OP_MPR选择策略[7]，则在源节点2选择MPR集时，节点7会被加入M2中且不能被剔除。

这个简单的实例显示，在全局网络选择MPR节点时，对已被其他节点选中的节点做退出判断后剔除冗余节点，能减少网络中消息的洪泛数量。

2.3性能分析

G-MPR选择策略能快速选取局部优化，减少相关性引起的冗余，从而获得全局优化，不会额外增加算法的时间复杂度，还能减少全局MPR集的节点数量和洪泛消息的数量。

在OLSR路由协议中，相邻节点之间可以通过HELLO消息获取相互的身份信息[9]。伴随着网络中节点拓扑的快速变化，MPR节点选取是一个持续过程，在网络节点初始化的过程中，大部分节点都没有获取到是否已被其他节点选中的信息[10]。随着选取自己的MPR集，且选取时间不同，节点将能够检测到已被其他节点选为MPR节点的节点，此时该选择策略将呈现出全局优化的趋势。

OLSR路由协议通过选取中继节点集(MPRs)来代替全部的一跳邻居节点，实现消息的传递，被选为MPR的节点相对其他节点，会不可避免地产生额外传输负担[11]。随着网络拓扑的变化，网络中所有节点都有可能被选为MPR节点，最终，在网络中的节点会基本达到负载均衡。

3仿真验证

验证基于G-MPR选择策略的优化链路路由 (Global-OptimizedLinkStateRouting,G-OLSR)协议在全局网络中的性能。在不同场景下，对OLSR协议和G-OLSR协议在整个网络中分别做时延和TC消息分组数比较。

3.1仿真环境

使用NS2.34仿真软件，对基于G-MPR选择策略的G-OLSR协议进行验证。

根据汽车节点在路上的运动特性，选取平面式网络结构，MAC层使用IEEE802.11，采用Two-raygroundreflection无线传输模型[12]，仿真区域的范围取为1 000m×1 000m，使用NS自带的工具setdest生成节点随机移动模型，网络场景中有60个节点，仿真时间400s，移动模型中节点的移动速率最小为0m/s，最大分别为1m/s，5m/s，10m/s，15m/s，20m/s，25m/s和30m/s共7种[9]，节点停留时间为0s，节点的无线覆盖半径默认为250m，数据流的业务类型采用由NS自带的流量生成器cbrgen工具所产生的CBR流，其中数据包大小为512Bytes，发送速率为10packet/s。

对各场景进行多次仿真实验，将实验中采集的数据求其平均值。

3.2仿真结果

移动速率和网络中TC分组数量的关系如图2所示。在7种不同移动速率下，G-OLSR相比OLSR减少了TC消息的数量，这说明G-OLSR选择策略能有效减少全局网络中MPR节点的数量，使MPR集得到优化。

图2　移动速率和TC分组数

移动速率和传输时延的关系如图3所示。随着节点运动速率的加快，OLSR的传输时延都会随之加大，但G-OLSR因在全局网络中有优化的MPR集，能减少消息的洪泛，从而相比OLSR能减少时延。

图3　移动速率和节点时延

4结语

文中提出的G-MPR选择策略能有效减少各个源节点之间选取MPR节点时相互之间的相关性，从全局上优化了MPR选择策略，减少了网络中MPR集的冗余，达到全局网络中洪泛消息的减少，从而提升网络的性能。使用NS进行移动多点仿真，从仿真结果可以看出G-OLSR协议能有效减少网络中消息的洪泛并减小网络时延提升了网络性能。

参考文献

[1]孙友伟，温双涛．基于电力线通信的新型物联网架构[J].西安邮电大学学报，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的电力线物联网控制平台[J].西安邮电大学学报，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].成都大学学报.2015.34(1):38-40[2015-09-30].http://mall.cnki.net/magazine/article/CDDD201501011.htm.

[4]杨彬,刘健,冯家刚.基于拓扑快速变化的OLSR改进路由协议研究[J].计算机工程与应用.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协议的最小MPR集选择算法[J].计算机应用，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路由协议的改进及其NS2仿真分析[J].计算机仿真.2008.25(1):161-163[2015-09-30].http://mall.cnki.net/magazine/article/JSJZ200801047.htm.

[9]陈立,杨瑞娟,戚浩,等．一种改进的高动态OLSR协议算法研究[J].无线电工程.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]. 智能系统学报.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] 兰鹏,李二涛,何桂仙. 基于改进OLSR路由协议mesh网络的研究[J]. 杭州电子科技大学学报. 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].西安邮电大学学报.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.

[责任编辑:瑞金]

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

作者简介：孙友伟(1956-)，男，教授，从事下一代通信网研究。E-mail: syw@xupt.edu.cn 张晶(1991-)，男，硕士研究生，研究方向为物联网技术及应用。E-mail:296363682@qq.com

中图分类号：TN913.6

文献标识码：A

文章编号：2095-6533(2016)02-0036-05