基于多参数服务质量的多点中继选择算法

邵慧莹，李剑锋，2

（1.中国计量学院 经济与管理学院，浙江 杭州310018；2.上海理工大学 管理学院，上海200093）

0 引 言

针对优化链路状态路由 （optimized link state routing，OLSR）协议［1］中的多点中继 （multipoint relays，MPR）选择算法［2］问题，国内外众多学者和研究机构进行了大量、广泛而深入的研究，提出一些多点中继选择算法［3］。传统多点中继选择算法通过从其邻居节点中选择多个中继节点建立进行路由路径，它们均没有全面考虑服务质量 （QOS）参数，如节点饱和度、链路稳定性和带宽等，建立的数据路由并非最优，而且鲁棒性比较差［4，5］。为此，文献 ［6］提出一种采用遗传算法选择最小MPR 集的多点中继选择算法；文献 ［7］提出一种基于节点剩余能量的多点中继选择算法；文献 ［8］提出一种基于多参数QoS的多点中继选择算法，一定程度上解决传统多点中继选择算法存在的不足。

为提高移动自组织网络 （mobile ad hoc network，MANET）的服务质量，提出一种基于多参数服务质量的多点中继选择算法 （QoS－MPR），并通过仿真对比实验测试算法的有效性和优越性。实验结果表明，本文算法减少了网络丢包率和平均延时，能够获得比较理想的数据传输路由。

1 标准OLSR 协议的MPR选择机制

OLSR 协议是一种在经典链路状态 （link state，LS）基础上发展起来的、适合于MANET 的路由协议，通过根据最小跳数建立分组转发的最短路径［10］。多点中继（MPR）是OLSR 协议的核心，选择性泛洪广播信息，其主要目的是减少相同控制信息的重复转发次数，防止广播风暴现象出现，从而降低广播分组的数量。对于MANET 中的任意一个节点，其邻居节点可以划分为两类：MPR 节点和非MPR 节点，非MPR 节点不能转发控制信息，而MPR节点不仅可以处理控制信息，而且可以转发控制信息，第一个节点从邻居节点中选择MPR 节点，组成MPR 节点集，MPR 集可以覆盖其全部的两跳节点，OLSR 协议通过MPR 节点集将数据转发到目的节点，因此MPR 节点集越小，OLSR 协议的性能越好，MPR 选择性泛洪方式如图1所示［11］。

图1 MPR 选择性泛洪方式

2 多参数服务质量的多点中继选择算法

2.1 QoS的参数选择

QoS参数的选择直接影响算法的复杂度和效率，本文选择的QoS参数主要包括端到端的延时、带宽、节点的饱和率、链路稳定性、丢包率等。

（1）端到端延时。端到端延时是指数据包从源节点S到目标节点D 的时间延迟，其计算公式为

式中：T（i）——节点i的传输时延；k——路由上的节点数，Tp（i）——节点i的处理时延。

在多点中继选择算法工作过程中，考虑到信号自身的传输时延，因此有

式中：Tprop（S，D）——信号自身的传输时延。

（2）网络带宽。网络带宽是一个非常重要的QoS参数，其描述数据链路为数据包提供的传输速率，带宽越高，可以传输的数据量就越大，节点S 和D 之间的带宽定义如下

式中：mess＿size——接收数据包的大小；Tmess（i，j）——接收该数据包的延时。

（3）节点发送饱和度。由于MANET 采用TDMA 制式的通信方式，在一个周期内，每一点发送的数据流大小有限，当一个节点待发数据包排队的时间过长，这就表示该节点处于饱和状态，如果该节点被选择作为MPR 节点，那么导致网络数据包转发严重滞后，对整个网络的吞吐量产生不利影响。相关研究结果表明，靠近网络中心的节点转发大流量数据的概率要高于其它节点，其网络负载必然越大，易出现网络拥塞现象，数据包丢失的概率增加［12］。在MANET，不可避免出现数据包排队现象，而OLSR 协议发送的任何消息都有一个有效时间（Vtime），当Vtime＝0时，则该消息无效而被丢弃，根据OLSR 协议的这种特性，通过每个节点的待发数据包大小来判断该节点是否饱和。根据文献 ［13］，链路的饱和率PRsat可以根据节点的饱和率计算得到，具体计算公式如下

式中：Psat——节点的饱和率。

（4）链路稳定性。在MANET 过程中，由于节点的可移动性，网络拓扑结构具有动态变化特点，从而导致数据的链路极不稳定，但在极短时间，网络拓扑结构相对固定，因此链路具有一定的稳定性。链路质量变化主要由于节点的发射功率变化引起的，因此可以根据历史链路状态对链路稳定性进行评价。MANET 的链路稳定性评价指标主要包括两部分：本地链路稳定估值 （local stability，LS）和邻居链路稳定估值 （neighbor stability，NS）。定义一个稳定向量函数为

式中：R＿Power——接收信号功率。

当SS（d，tk）小于零时，表示MANET 的链路质量变差，S、D 两者相隔比较远，不然S、D 两者相互靠近。在tk＋1时刻，本地链路稳定估值 （LS）计算公式如下

式中：l＝1，2，…，k。

LS 的值越小，表示节点S 和点D 之间相对静止，两者之间的间隔变化不大，位置比较固定，相反，两者之间的运动变化比较频繁，两者之间的间隔变化比较大。

在tk＋1时刻，邻居链路稳定估值 （NS）计算公式如下

LS 的值越小，表示节点S 的邻居节点相对静止，位置比较固定，相反，节点之间的运动变化比较频繁。

在tk＋1时刻，节点S 和D 的链路稳定性计算公式如下

式中：α、β——LS 和NS 的权值，且有α＋β＝1。

TR（S，D，tk）值越小，表明源节点S 和D 的相对运动频率较低，链路稳定性较好，链路质量较高，TR（S，D，tk）越大，表明节点S 和D 的运动变化很频繁，链路越不稳定，链路质量比较低。

（5）丢包率。丢包率指由于节点移动等因素的干扰，数据包在网络传输过程中数据包丢失的百分比率。设源节点S发送的数据包为Totalsent，那么丢包率的计算公式如下

综合上述可知，任意一个时刻的网络性能，必须考虑多个QoS参数的综合影响，因此本文根据端到端延时、带宽、节点发送饱和度和链路稳定性概率、丢包率构建多参数的QoS性能评价函数，具体计算公式为

式中：a，b，c，d，e——权重，且有a＋b＋c＋d＋e＝1。

2.2 QoS－MPR的工作流程

QoS－MPR算法不仅考虑邻居节点的覆盖范围，还考虑节点的多参数的QoS，QoS－MPR 算法的工作步骤具体如下：

（1）清空节点P 的MPR节点集合，即有MPR（P）＝φ。

（2）计算P 节点的二跳邻居节点 （N2（p））数量。

（3）将P 节点的邻居节点集合中可以达到N2（p）的节点合并到MPR（P）中，并删除N2（p）中相应的节点。

（4）在N2（p）中，如果有节点没有被MPR（P）中节点所覆盖，则进行如下处理：

1）根据多参数QoS对N2（p）中的节点进行降序排列；

2）选择多参数QoS最大的节点i，如果该节点可以覆盖到N2（p）中节点，则将其合并到MPR（P）中，并将其从N2（p）中删除；

3）在N2（p）中，如果仍然还有节点没有被MPR（P）中的节点所覆盖，则重复步骤 （4），继续处理。

综合上述可知，QoS－MPR 算法的工作流程如图2所示。

MPR 算法与QoS－MPR 算法的对比结果如图3 所示。从图3可知，在MPR 算法中，节点C因为二跳节点覆盖度最大，被选为中继节点，但是节点C 与邻居节点之间的链路质量不稳定，易出现节点拥塞、丢包现象；QoS－MPR 算法根据节点的QoS作为权值进行MPR 节点选择，在选择最优转发链路的质量条件下，实现了二跳邻居节点的全部覆盖，性能得到了一定的提升。

图2 QoS－MPR算法的工作流程

图3 MPR 算法和QoS－MPR算法对比

2.3 改进的Dijkstra选路算法

在标准OLSR 路由协议中，Dijkstra选路算法通过路径跳数作为权值选择节点构建数据转发的路由，属于跳数最小路由选择法，没有全面考虑QoS参数，因此跳数最小的路由不一定是最优的数据路由［14］。为此，本文对Dijkstra选路算法进行改进，不仅考虑路径跳数，而且还考虑节点的延时、带宽、链路稳定性等因素对路径的影响，因此点S 和D 之间的路由质量的评价数 （Path（S，D，i，t））定义如下

式中：Hop——路由上的跳数；i——S 和D 之间的一条路径。

改进Dijkstra选路算法的工作流程如图4所示。

图4 改进Dijkstra选路算法的工作流程

3 仿真实验

3.1 仿真场景

为测试基于QoS－MPR 算法的OLSR 协议 （以下简称改进OLSR 协议）性能，在Intel 4核2.9GHz的CPU，4 GRAM，Windows XP操作系统个人计算机上，采用Open＋＋软件进行仿真测试。仿真场景参数设置见表1。采用标准OLSR 协议进行对照实验，从延时、丢包数目以及TC分组数量等方面对它们的性能进行综合分析。

表1 仿真场景参数

3.2 结果与分析

3.2.1 平均端到端延时性能对比

两种OLSR协议的平均端到端延时仿真结果如图5所示。从图5可以清楚看出，相对于标准OLSR 协议，改进OLSR协议的平均端到端延时更小，这主要由于改进OLSR协议在MPR选择和路由选择过程中，综合考虑了QoS参数的影响，选择链路质量较好的路由进行数据转发，数据包排队时间减少，加快了数据转发的速度，降低了平均端到端延时。

图5 平均端到端延时比较

3.2.2 丢包数目对比

两种OLSR 协议的网络丢包数目的对比结果如图6所示，从图6可以明显看出，改进的OLSR 协议丢包数目明显要少于标准OLSR 协议，这主要是因为改进OLSR 协议充分考虑了节点的发送饱和度，减少数据包的排队时间，在有效时间内，可以选择最优的链路将数据包发送出去，降低网络丢包数目，降低丢包概率。

图6 网络丢包数目对比

3.2.3 TC分组数量对比

两种OLSR 协议的TC分组数量仿真结果如图7所示。从图7可知，相对于标准OLSR 协议，改进OLSR 协议的TC分组数量大幅度降低，这主要是因为TC 控制消息由MPR 节点广播和转发，由于引入多参数QoS评价指标选择MPR 节点，减少MPR 节点集合的冗余节点和TC 分组转发数量，提高了OLSR 协议的性能。

图7 TC分组数量对比

4 结束语

针对标准OLSR 协议的MPR 选择算法的不足，提出一种基于多参数服务质量的多点中继选择算法，将延时，带宽等QoS参数引入到MPR 选择和路由选择算法中，最后采用仿真实验测试其性能。实验结果表明，相对于标准OLSR协议，基于QoS－MPR算法的OLSR 协议可以更好地选择MPR 节点集合，减少了MPR 集合中的节点冗余，大幅度减少数据转发的平均端到端延时延和丢包数目，选择质量更优的数据链路，提高了数据转发的成功率，具有更高的实际应用价值。

［1］Santhi G，Nachiappam A.A survey of QoS routing protocols for mobile ad hoc networks ［J］.International Journal of Computer Science ＆Information Technology，2010，2 （4）：125－132.

［2］Narangerei Dashbyamba，Ceiimuge Wu，Satoshi Ohzahata，et al.An improvement of OLSR using fuzzy logic based MPR selection ［C］／／Network Operations and Management Symposium，2013：1－6.

［3］LAN Peng，LI Ertao，HE Guixian.Research of mesh network based on the improved OLSR routing protocol ［J］.Journal of Hangzhou Dianzi University，2013，33 （4）：54－57 （in Chinese）.［兰鹏，李二涛，何桂仙.基于改进OLSR 路由协议mesh网络的研究［J］.杭州电子科技大学学报，2013，33 （4）：54－57.］

［4］Toutouh J，Alba E.Multi－objective OLSR optimization for VANETs［C］／／IEEE 8th International Conference on Wireless and Mobile Computing，Networking and Communications，2012：571－578.

［5］Boushaba A，Benabbou A，Benabbou R.Optimization on OLSR protocol for reducing topology control packets［C］／／IEEE International Conference on Multimedia Computing and Systems，2012：539－544.

［6］GAO Yu，ZENG Huashen，ZHANG Hong.Improvement of multipath routing algorithm based on OLSR and source routing［J］.Journal of Southwest Jiaotong University，2010，45 （3）：424－429 （in Chinese）.［高雨，曾华燊，张洪.基于OLSR 和源路由的多径路由算法的改进 ［J］.西南交通大学学报，2010，45 （3）：424－429.］

［7］Kots A，Kumar M.The fuzzy based QMPR selection for OLSR routing protocol［J］.Wireless Network，2014，20 （1）：1－10.

［8］WEN Huaiyu，LUO Guangchun.Link cognitive－based OLSR routing protocol for wireless Mesh networks ［J］.Journal of University of Electronic Science and Technology of China，2011，40 （2）：303－307 （in Chinese）. ［温怀玉，罗光春.无线Mesh网络链路认知OLSR 路由协议 ［J］.电子科技大学学报，2011，40 （2）：303－307.］

［9］ZHANG Dengyin，WANG Zhenxing.Security study of MPR nodes in OLSR routing protocol ［J］.Computer Technology and Development，2011，21 （12）：142－144 （in Chinese）.［张登银，王振兴.OLSR 路由协议中MPR 节点安全性研究［J］.计算机技术与发展，2011，21 （12）：142－144.］

［10］Belhassen M，Belghith AM.Performance evaluation of a cartography enhanced OLSR for mobile multi－hop ad hoc networks［C］／／IEEE Wireless Advanced，2011：149－155.

［11］Mcauley A，Sinkar K，Kant L.Tuning of reinforcement learning parameters applied to OLSR using a cognitive network design tool［C］／／IEEE Wireless Communications and Networking Conference，2012：2786－2791.

［12］Cervera G，Barbeau M，Kranakis E.QoS and security in link state routing protocols for MANETs ［J］.Wireless Days，2013：22 （7）：1－6.

［13］Zhichao M，Weibo Y，Dawei N.The position－aware routing protocol for pre－handoff on OLSR in vehicular networks［C］／／IEEE International Conference on intelligent System Design and Engineering Application，2012：1156－1159.

［14］Sondi P，Gantsou D，Lecomte S.A multiple－metric QoSaware implementation of the optimized link state routing protocol［J］.Communication Networks and Distributed Systems，2014，12 （4）：381－400.