移动Ad Hoc网络中一种基于多路径路由协议的QoS保障算法

姜海龙

(中国电子科技集团公司第20研究所，西安 710068)



移动Ad Hoc网络中一种基于多路径路由协议的QoS保障算法

姜海龙

(中国电子科技集团公司第20研究所，西安 710068)

摘要：移动Ad Hoc网络快速发展的同时，其中的服务质量(QoS)保障问题也日渐突出。设计了一种适用于移动Ad Hoc网络中多路径路由协议的路径选择和带宽分配算法，选择适合业务传输的路径，并合理分配带宽，实现QoS保障。计算机仿真表明，该算法能够适应移动Ad Hoc网络的动态性、不稳定性，有效地实现QoS保障，改善网络整体性能。

关键词：移动Ad Hoc网络；服务质量；线性规划

0引言

移动Ad Hoc网络是一种无中心、自组织、高动态的无线网络，目前广泛应用于军事、工业、商业等领域。但是由于其存在带宽资源受限、链路质量不稳定、网络拓扑动态变化等特点[1]，移动Ad Hoc网络对服务质量(QoS)要求较高的业务支持较差。

当前移动Ad Hoc网络中的QoS保障机制尚处于研究阶段。本文从网络层路由协议出发，提出一种适用于多路径路由协议的路径选择算法和带宽分配算法，通过合理选择传输路径并且合理分配带宽，尽可能提高传输带宽，降低传输时延和丢包率，提高传输业务的QoS。

1问题建模

假设已经利用某种多路径路由协议在网络中2点之间建立了多条链路不相交路径。本文研究的重点在于如何从中选择合适的传输路径，及如何在选择路径上合理分配传输带宽，以保障业务的带宽、时延、丢包率等QoS要求得到满足。

下面对上述问题进行建模。假设源目的节点之间建立了n条(n≥2)链路不相交路径，表示为集合P={P1,P2,…,Pn}。其中任一条路径Pi(1≤i≤n)均具备下列QoS参数：瓶颈带宽Bi、总时延Di、总平均丢包率Li，表示为(Bi,Di,Li)。当前传输业务的QoS要求如下：最小带宽要求λmin、最大时延要求Dmax、最大平均丢包率要求Lmax。

为了简化问题，假设多路径路由协议已具备保证建立路径时延满足业务的最大时延要求Dmax的机制。这里仅需要考虑路径的瓶颈带宽和平均丢包率参数。仅选择其中一条路径传输业务可能无法保障业务的所有QoS要求得到满足，因此需要采用分流传输和分集传输机制以满足业务的QoS要求。通过分流传输可以扩展可用带宽资源，通过分集传输(在不同路径上传输相同的冗余分组)可以提高容错率。这里用于分流传输的路径使用集合Pa表示，用于分集传输的路径使用集合Pb表示。

即任一路径上分配的分集带宽(如果存在)与所有路径分流带宽的总和应大于等于业务的最小带宽要求。

即任一路径上分配的分流带宽与分集带宽(如果存在)的总和应小于等于该路径的瓶颈带宽。

即任一用于分流传输的路径的平均丢包率应小于等于业务的最大丢包率要求。所有用于分集传输的路径的总平均丢包率(所有分集传输路径平均丢包率的乘积)应小于等于业务的最大丢包率要求。

(4) Di≤Djmax(∀i满足1≤i≤n且λi>0)

即任一传输业务的路径应满足业务的最大时延要求。假设路由协议具备该机制，下文不再考虑。

用Ci表示业务在路径Pi上传输的代价，定义如下：

(1)

Ci反映了对应路径Pi的带宽利用率。Ci越小，说明路径Pi负载越小，传输性能越好。Ci越大，则说明路径Pi负载越大，传输性能越差。

业务在所有选择的路径上传输的总代价定义为：

(2)

(3)

约束条件为：

(4)

该优化问题形似线性规划问题，但其中包含较多的未知量，并非标准线性规划问题。为了简化问题，采用的方法是通过一定原则确定其中部分未知量的值，将问题转化为标准的线性规划问题，然后再参照标准线性规划问题的解法求解。

2求解过程

为了简化优化问题，减少未知量，首先需要确定集合Pa和Pb包含的元素。

按如下算法确定Pb包含的元素(Pc表示满足Li≤Lmax的所有路径的集合)：

(2) 如果Pb在P中的补集CPPb=∅，Pb确定失败，结束；否则从CPPb中选取Pi，满足Li>Lmax且Li最小，更新Pb=Pb∪{Pi}，转(3)。

(4) 如果Pb在P中的补集CPPb=∅，Pb确定失败，结束；否则从CPPb中选取Pi，满足Bi≥λmin且Li最小，更新Pb=Pb∪{Pi}，转(5)。

按如下算法确定Pa包含的元素：

(1) Pa=∅。对于所有的Li(1≤i≤n)，如果不存在Li满足Li≤Lmax，则Pa=∅，结束；否则转(2)。

(2) 如果Pa在P中的补集CPPa=∅，Pa确定失败，结束；否则从CPPa中选取Pi，满足Li

这样Pa和Pb包含元素得到确定，同时约束条件:

(5)

得到满足。

当Pb=∅时，即不存在分集传输路径。优化目标函数简化为：

(6)

设Pa元素个数为n，约束条件简化为：

(7)

这样优化问题被简化为标准线性规划问题。

将约束条件转化为标准型，得到：

(8)

将标准型约束条件转化为规范型，存在以下2种情况。

情况1：Bi1-λmin≥0，得到：

(9)

在这里，取基变量为λi1、xj(j=2,3,…,n+1)。

用yi统一表示所有的决策变量，即：

(10)

则目标函数转化为以下形式：

(11)

约束条件转化为以下形式：

(12)

情况2：Bi1-λmin<0，由于约束条件矩阵中找不到单位基，需要额外添加人工变量xn+2，得到：

(13)

在这里，取基变量为λi1、xj(j=3,4,…,n+2)。

用yi统一表示所有的决策变量，即：

(14)

则目标函数转化为以下形式：

(15)

约束条件转化为以下形式：

(16)

当Pa≠∅且Pb≠∅时，即同时存在分流传输路径和分集传输路径，优化目标函数转化为：

(17)

(18)

此时优化问题已经被简化为标准线性规划问题。

将约束条件转化为标准型，得到：

(19)

(20)

在这里，取基变量为λi1、xj(j=2,3,…,n1+n2+1+l)。

用yi统一表示所有的决策变量，即：

(21)

则目标函数转化为以下形式：

(22)

约束条件转化为以下形式：

(23)

(24)

在这里，取基变量为λi1、xj(j=3,4,…,n1+n2+2+l)。

用yi统一表示所有的决策变量，即：

(25)

则目标函数转化为以下形式：

(26)

约束条件转化为以下形式：

(27)

(28)

在这里，取基变量为λi1、xj(j=2,3,…,n2+1+l)。

用yi统一表示所有的决策变量，即：

(29)

则目标函数转化为以下形式：

(30)

约束条件转化为以下形式：

(31)

(32)

在这里，取基变量为λi1、xj(j=2,3+l,4+l,…,n2+2+l)。

用yi统一表示所有的决策变量，即：

(33)

则目标函数转化为以下形式：

(34)

约束条件转化为以下形式：

(35)

3仿真验证

下面通过计算机软件仿真验证采用本文算法的多路径路由协议的性能。这里使用OPNET Modeler软件[3-5]。网络场景设置为：范围10 km×10 km，节点数25个，每个节点按随机路径点模型运动，网络初始拓扑结构如图1所示。

图1　网络初始拓扑结构

仿真统计不同节点移动速度下，以及不同业务分组到达率下的网络吞吐量、时延和丢包率。并以无QoS保障的动态源路由协议(DSR)性能作参考。

从图2～图4的仿真结果可以看到，在不同节点移动速度条件下，采用本文算法的多路径路由协议的吞吐量、端到端时延、丢包率均优于DSR协议。

图2　节点移动速度与吞吐量关系曲线

图3　节点移动速度与端到端时延关系曲线

图4　节点移动速度与丢包率关系曲线

由于多路径路由协议采用分流传输，能够充分利用网络带宽资源，并且选择的路径丢包率较低，因此在节点移动速度较快的情况下，吞吐量下降程度低于DSR协议。多路径路由协议选择的路径均满足业务的时延要求，因此端到端时延低于DSR协议。由于多路径路由协议采用分集传输，容错率较高，因此在节点移动速度较快的情况下，虽然链路失效概率增加，丢包率依然低于DSR协议。

从图5～图7仿真结果可以看到，在不同业务分组到达率条件下，采用本文算法的多路径路由协议的吞吐量、端到端时延、丢包率均优于DSR协议。

图5　业务分组到达率与吞吐量关系曲线

图6　业务分组到达率与端到端时延关系曲线

图7　业务分组到达率与丢包率关系曲线

由于多路径路由协议采用分流传输，带宽资源较充足，在业务分组到达率较高的情况下，吞吐量高于DSR协议。多路径路由协议选择的路径均满足业务的时延要求，因此端到端时延低于DSR协议。

由于多路径路由协议采用分集传输，容错率较高，因此在业务分组到达率较高的情况下，虽然网络负荷加重，丢包率依然低于DSR协议。

4结束语

本文针对在移动Ad Hoc网络中实现传输业务QoS保障的问题，提出一种适用于多路径路由协议的路径选择和带宽分配算法，并通过计算机软件仿真验证了算法的性能。下一步将更多考虑在实际应用场景中改进算法，提高算法的实用性。

参考文献

[1]陈林星，曾曦，曹毅.移动Ad Hoc网络——自组织分组无线网络技术[M].北京：电子工业出版社，2012.

[2]陈开周.最优化计算方法[M].西安：西安电子科技大学出版社，1985.

[3]陈敏.OPNET网络仿真[M].北京：清华大学出版社，2004.

[4]王文博，张金文.OPNET Modeler与网络仿真[M].北京：人民邮电出版社,2003.

[5]龙华.OPNET Modeler与网络仿真[M].西安：西安电子科技大学出版社，2006.

An Algorithm of QoS Guarantees Based on Multipath Routing Protocol in Mobile Ad Hoc Network

JIANG Hai-long

(The 20th Research Institute of CETC，Xi'an 710068,China)

Abstract:With the rapid development of mobile Ad Hoc network (MANET)，quality of service (QoS) guarantee in MANET is becoming increasingly prominent.This paper designs routing selection and bandwidth allocation algorithm applicable to the multipath routing protocol in MANET.In this algorithm,the paths suiting for operation transmission are selected and bandwidth is allocated reasonably to realize the QoS guarantee.Computer simulation results show that the algorithm can adapt to the dynamics and instability of MANET,and realize QoS guarantees effectively,improve the overall performance of the networks.

Key words:mobile Ad Hoc network;quality of service;linear programming

收稿日期:2015-12-01

中图分类号：TP393

文献标识码：A

文章编号：CN32-1413(2016)02-0105-07

DOI:10.16426/j.cnki.jcdzdk.2016.02.026