利用非精确参数的移动互联网业务感知多目标优化QoS路由算法

戴慧珺，曲 桦，赵季红，2

（1.西安交通大学电子与信息工程学院，710049，西安；2.西安邮电大学通信工程系，710061，西安）

移动互联网是以固定核心网为传输、无线接入为主的互联网络服务［1］。基于 M-Internet（Moble-Internet）的应用催生了许多新业务［2］，使得基于移动终端的移动互联网服务质量保证技术（Quantity of Service，QoS）面临巨大挑战。目前可行的技术方案是使用网络虚拟技术来屏蔽多个物理网络的差异，利用覆盖网和动态智能路由技术进行跨域传输的流量控制和带宽保障［3］。虚拟覆盖网不改变物理网络基础架构，从应用层优化业务QoS，在网络扩容受限的条件下，QoS路由可在路径选择时实现全局资源利用和负载的最优化［4］，因此，覆盖网结合QoS路由算法有利于解决移动互联网络中端到端QoS问题。

QoS路由作为通信网络技术领域的核心问题之一，应用背景由Internet、IP网络［5-6］发展到P2P网络、无线传 感网络［7］和 Ad-Hoc、MANET 网络［8］，算法主要有 QUEST［9］、PBSP［5］。上述研究采用的方法包括建立多约束多目标QoS优化模型［10-11］，根据近似算法得到解集，或者使用启发式算法，诸如智能蚁群来实现网络状态的QoS认知［12-13］等。在实际的动态网络环境中，网络节点所能获得的各节点和链路状态（特别是无线链路状态）信息并不是精确的［14-15］。常见方案是根据多目标优化理论重新建立网络模型，给出相应求解机制和实施方案从而设计网络［16-17］。移动互联网具有异构融合网络的特点，在应用层上采用覆盖网全局路由方法可以提高业务的QoS［18］，但覆盖网高度抽象和信息汇聚的特性导致相应节点获取的QoS参数具有不精确性，因此QoS路由必须结合非精确网络状态信息和业务感知来执行。

本文针对移动互联网应用背景，根据网络非精确参数特点，采用多目标优化理论来建立多QoS目标决策模型；利用覆盖网这一虚拟平台，对业务进行感知和匹配获得相应业务类型以及QoS需求，针对多个QoS参数的特点，结合概率和隶属度函数获得该多目标优化模型的解集。实验结果表明，该算法所选择的路径在各项QoS目标都满足的情况下，可有效减小时间开销，提高网络资源利用率和QoS满意率，从而优化资源配置调度。

1 多QoS目标优化模型

设网络G＜V，E＞，其中V=｛v1，v2，…，vm｝为节点集合，E=｛e1，e2，…，en｝为链路集合，设s∈V为源节点，d∈｛V-｛s｝｝为目的节点，则p（s，d）=（s，v1，v2，…，vi，d）为源节点s到目的节点d 的一条路由路径。

定义1 多目标优化模型 在限定约束下，最小化和最大化需同时满足的模型可以表示为

式中：x=［x1，x2，…，xD］为 D 维决策变量；y为目标函数；N为优化目标总数；fn（x）为第n个子目标函数；g（x）为K项不等式约束条件；h（x）为M 项等式约束条件，约束条件构成了可行域；xd-min和xd-max为向量搜索的上、下限。

定义2 理想点求解 设多目标最优化问题的可行域为D，如果对∀x∈D，都满足F（x＊）＜F（x），则称x＊为D的多目标绝对最优解，绝对最优解构成解集合，解集存在一个理想点fix＊，满足

理想点求多目标优化的方法是在解空间内找到一点作为确定的解，该点与理想点距离最近，距离远近的评价应用了泛函中距离的概念。

定义3 隶属度函数 设给定论域X，存在集合A，元素x∈X，元素x到A 的任一映射μA（x），μA：X→R，x→μA（x），μA（x）为元素x对集合A 的隶属度函数。

由于大多数固定网络存在方向对称性，因此基于核心骨干网的覆盖网可以被模型化为无向网络［19］。业务要求是约束，同时，QoS路由还应达到减小传输代价及提高业务满意率等多个目标，因此多目标优化可用来作为本文算法的理论模型。

2 业务感知模型

常见业务根据应用层不同服务分为语音业务、IPTV、E-mail等，每类业务有大致的QoS要求，例如VoIP业务，要求最小带宽大于8KB／s，端到端时延最大不超过100ms，误帧率小于1%［20］。当该业务在UMTS网络传输时，其帧被打上实时会话类业务标签，路由器解析该类业务时可获得相应的QoS要求。

业务感知的作用是识别并还原网络分组所属的业务类型，包括P2P、视频、音频等。本文设计一种识别速度较快且识别精度合适的感知模型，把感知结果作为多目标QoS优化模型的约束条件输入。模型结构如图1所示。

图1 业务感知模型

在该模型中，业务首先进入端口识别模块，按照常见端口映射表识别，如表1所示，业务与端口数据源进行比对，识别成功则给出业务类型；未识别则进入特征码识别模块，特征码用于识别相应协议的关键字信息和P2P特征。特征码匹配根据特征库采用了快速字符串匹配，能提高深度包探测方法的精度。

表1 常见端口映射表

该模块通过在网络中对数据包的截获将数据包还原为相应业务，如感知结果为VoIP业务，则得到业务带宽Bpath≥8KB／s，端到端时延Dpath≤100ms，误帧率Lpath≤0.01。

3 QoS参数处理

QoS路由算法包括收集处理网络QoS状态和寻找合适路径两部分［21］。

3.1 参数分类

从数据处理角度，QoS参数可分为可加性、可乘性和瓶颈参数。可加性参数表示路径参数为路径上链路参数的累加值，例如，时延Dpath=∑Dlink。可乘性参数表示路径参数为路径上所有链路参数的乘性值，例如，丢包率1-Lpath=∏（1-Llink）。瓶颈类参数表示路径参数为路径上所有链路参数的最小值，例如，带宽Bpath=min［Blink］，根据分类可以获得从链路参数到路径参数的计算方法。不同参数采用不同隶属度函数处理，能够全面考虑不同类型参数对链路性能的影响。

3.2 不精确参数处理

单次测量和非精确值的网络状态将影响路由算法的性能，导致网络负载能力恶化，例如丢包率和阻塞率的上升等。相关研究中，一些算法根据参数所在的区间进行弹性处理，取其边界值［22］；另一些结合参数分布函数和统计特性采用概率方法进行处理［23］。不精确参数给QoS路由算法带来的问题是网络链路更新策略、网络拓扑和链路代价函数对QoS路由带来的影响［24］。本文算法综合概率方法和隶属度预处理非精确参数，根据多目标QoS方程寻路获得优化路径。

覆盖网 QoS参数xi（i=1，2，…，n）多次测量值服从正态分布，以带宽参数为例，某条链路的带宽参数Bi，i∈（1，…，n），其测量值服从正态分布 N（μ，σ2），根据n次带宽测量结果，其带宽值为…，，其极大似然函数为

3.3 构建隶属度矩阵

由3.2节得到QoS参数计算值用于构建隶属度矩阵，作为非精确QoS参数处理的最后一步，也是多目标QoS模型求解的第一步，隶属度矩阵可以对多种属性多个维度的QoS参数进行均质化。隶属度方法和数据的归一化相比，更侧重多量纲的数据本质属性和统一处理。使用隶属度矩阵，输入是多个QoS参数列表，输出是根据QoS约束获得的优选序列。

将业务需求等约束条件作为滤波进行转换。根据单个目标的隶属度公式，其构造为

多目标模型中的QoS参数有m个，根据3.2节其链路状态信息可表示为向量xi=（¯B，¯D，¯L，¯J，…），每个向量经过隶属度转换，形成μ（xi），μ（xi）=（x′B，x′D，x′L，x′J，…），评价指标共有n个，进行隶属度转换后，可构建m×n隶属度矩阵μ

隶属度矩阵可以作为多目标模型的输入，对模型进行求解。在给定n个QoS参量后，该矩阵可利用每个参量的权值，通过模糊综合评价等方法对QoS路径进行排序。

4 多目标QoS路由寻路

4.1 构建多目标QoS方程

根据本文第2节业务感知模型，获得传输业务QoS约束g（x）≤0，要求业务的时延和丢包率在一定范围内，同时需尽可能最小化传输代价min（f1（epath，vpath）），和最大化资源利用率 max（f2（epath，vpath），f3（epath，vvpath））。f2和f3是资源利用函数，可理解为网络剩余带宽和剩余计算能力等资源。

式中：xpath=｛epath，vpath｝。在网络G＜V，E＞中，边为E=｛ei｝，节点为V=｛vi｝，测量获得ei的各个QoS指标值，根据3.2节不精确参数处理，得到ei=。根据3.1节，得到链路参数到路径参数的计算过程。

4.2 理想点法解方程

根据4.1节的式（6）可以建立方程组。式（6）中，最大化maxF（xi）表示剩余资源的最大化，意味着占用资源最小化，max（F（xi））=F-min（¯F（xi））。求解以最小化为优化目标的方程min（F（xi）），获得解f1x＊；相应地，求解以最大化为优化目标的方程max（F（x））得到解f2x＊。

根据定义2理想点法求解方程组，首先分别求各个方程的解，然后根据多个解构成的解空间搜索可行路径的排序，找距离解空间距离最短的点。

5 仿真实验

5.1 仿真参数

本算法的仿真实现通过omnet仿真工具结合Matlab输出验证分析。oment模拟网络资源和业务场景得到业务发生的仿真数据。具体仿真环境和参数如下。

本文选取对业务QoS区分较大、对用户QoE（Quantity of Experience）影响较大的节点计算能力、链路带宽、时延和丢包率这4个参数作为本实验具体参数，记为xi=（¯C，¯B，¯D，¯L）。

仿真环境基于覆盖网，根据omnet仿真工具绘制，使用多个智能路由器（服务器）节点结合普通路由器，在不指定物理位置的情况下生成随机网络。提取概率为30%的智能节点获得覆盖网拓扑，其智能节点数范围是［0，200］，采用临近邻接法（即两个覆盖节点之间的链路不存在其他覆盖节点）构造覆盖链路。链路参数根据网络agent的监测获得测量值。无向链路带宽范围为［0，10］MB／s，延时为［50，1 000］ms；每个节点计算能力为［0，500］。业务请求达到一定速率，服从泊松分布，服务请求的源节点和目的结点随机指定；被接收服务的服务时间服从指数分布，时间小于200s。网络拓扑结构如图2所示。

图2 网络拓扑结构

5.2 实验过程

仿真中和本文算法进行性能比较的算法是PB-SP和OSPF两种算法，QUEST算法等经典算法和本算法优化目标不一致。PBSP算法将链路带宽作为主要因素执行最短路径算法，OSPF算法运行在本覆盖网拓扑上，代价和带宽成反比。本文从全网优化性能、算法运行时间开销和资源优化等若干方面进行评价。

根据5.1节的仿真参数，考虑单次仿真结合多次随机仿真作为测试基本数据。定义QoS满意率为全网性能指标，QoS满意率为被接受的业务数除以到达的业务数。图3是单次仿真执行一段时间后本文算法和PBSP算法QoS满意率的对比。OSPF不考虑除带宽之外的QoS约束，因此不做QoS满意率的统计和比较。

图3 两种算法的QoS满意率曲线对比

当网络处于饱和状态时，新业务到达，网络拒绝处理，此阶段内的QoS满意率降到最低为0；直到网内业务结束，释放资源，QoS满意率将上升到最高。PBSP算法是线性加权多约束的方法，加权了链路QoS指标，而本文算法结合了业务感知利用理想点解来解该多目标QoS模型，兼顾链路和节点的性能。因此，同样的网络环境下，本文算法QoS满意率稍高于PBSP算法。

如图4所示，与OSPF、PBSP算法相比，本文算法时间开销较大，时间复杂度较大，PBSP算法和OSPF算法时间复杂度一致，而OSPF算法的时间开销较小。

图4 3种算法时间开销对比

图5 为两种算法选取的若干条路径链路的资源占用率对比，对比参量为带宽占用百分比，两种算法在传送数据量相等的情况下，由于选用不同路径，其带宽占用率不同。本文算法充分考虑了资源优化问题，因此在13条路径上资源占用率在35%和65%之间，而PBSP算法的资源占用率最大接近80%，可见其选路过程没有刻意回避带宽资源有限的路径，容易造成链路的局部拥塞。

图5 两种算法资源占用率对比

以一定的置信区间增加overlay节点，图6为OSPF算法与本文算法执行时间对比。当节点数较少，OSPF算法时间开销明显小于本文算法，随着节点数目增加到一定程度时，本文算法的时间增长小于OSPF算法。原因是本文算法执行多目标模型求解的计算过程在网络规模较小时，其时间开销非常明显，当节点数目增多时，理想点法能够减少QoS路由的部分计算量，而OSPF算法随着节点数目增多，处理计算量增长较快。因此，中型以上规模的网络中，本文算法的时间性能较传统算法更好。

图6 算法时间开销与覆盖网节点数目的关系

6 结 论

基于覆盖网的虚拟化方法解决应用层的业务问题是移动互联网的一个重要的研究手段。QoS路由技术研究了如何在约束条件下满足业务流的QoS需求，并在路径选择上实现了全局资源利用和负载的最优化。多目标优化模型是本文QoS路由的基本模型，在业务感知的条件下实现业务约束的输入，在多量纲的基础上尽可能实现多个目标的优化。为体现算法的优点，与传统最短路径算法和经典覆盖网QoS路由算法进行多方面比较，从网络整体性能和时间开销代价上表明，算法在某种程度上能够实现在完成约束的同时又能够优化资源配置，实现业务的QoS保障。

［1］ 罗军舟，吴文甲，杨明.移动互联网：终端，网络与服务 ［J］.计算机学报，2011，34（11）：2029-2051.

LUO Junzhou，WU Wenjia，YANG Ming.Mobile internet：terminal devices，networks and services ［J］.Chinese Journal of Computers，2011，34（11）：2029-2051.

［2］ KIM H W，CHAN H C，GUPTA S.Value-based adoption of mobile internet：an empirical investigation［J］.Decision Support Systems，2007，43（1）：111-126.

［3］ DUAN Zhenhai，ZHANG Zhili，HOU Y T.Service overlay networks：SLAs，QoS，and bandwidth provisioning［C］∥Proceedings of the 10th IEEE International Conference on Network Protocols.Piscataway，NJ，USA：IEEE，2002：870-883.

［4］ RAO Ruan，WANG Ruchuan.Multi-path QoS routing using genetic algorithm for LEO satellite networks［J］.Computer and Microelectronics，2011，20（1）：17-20.

［5］ XUE Guoliang，ZHANG Weiyi，TANG Jian，et al.Polynomial time approximation algorithms for multiconstrained QoS routing ［J］.IEEE／ACM Transactions on Networking，2008，16（3）：656-669.

［6］ LI Zhi，MOHAPATRA P.QRON：QoS-aware routing in overlay networks［J］.IEEE Journal on Selected Areas in Communications，2004，22（1）：29-40.

［7］ 马震远，周杰，陈楚，等.一种分段测量保证QoS约束的任播通信模型 ［J］.西安交通大学学报，2010，44（2）：44-49.

MA Zhenyuan，ZHOU Jie，CHEN Chu，et al.An anycast communication model with QoS constraints based on segmental measurement［J］.Journal of Xi’an Jiaotong University，2010，44（2）：44-49.

［8］ GULATI M K，KUMAR K.QoS routing protocols for mobile ad hoc networks：a survey［J］.International Journal of Wireless and Mobile Computing，2012，5（2）：107-118.

［9］ GU Xiaohui，NAHRSTEDT K，CHANG R N，et al.QoS-assured service composition in managed service overlay networks［C］∥Proceedings of the 23rd International Conference on Distributed Computing Systems.Piscataway，NJ，USA：IEEE，2003：194-201.

［10］XUE Guoliang，SEN A，ZHANG Weiyi，et al.Finding apath subject to many additive QoS constraints［J］.IEEE／ACM Transactions on Networking，2007，15（1）：201-211.

［11］MISRA S，XUE Guoliang，YANG Dejun.Polynomial time approximations for multi-path routing with bandwidth and delay constraints［C］∥Proceedings of the 2009International Conference on Computer Communications.Piscataway，NJ，USA：IEEE，2009：558-566.

［12］亓晋，张顺颐，孙雁飞，等.基于自主蚁群算法的认知网络多约束QoS路由算法 ［J］.南京邮电大学学报：自然科学版，2012，32（6）：86-91.

QI Jin，ZHANG Shunyi，SUN Yanfei，et al.Cognitive networks multi-constraint QoS routing algorithm based on ant colony algorithm ［J］.Journal of Nanjing University of Posts and Telecommunications：Natural Science，2012，32（6）：89-91.

［13］曹雪松，胡瑞敏，王朝萍.覆盖网络中一种公平负载均衡QoS路由算法 ［J］.计算机学报，2011，34（9）：1650-1659.

CAO Xuesong，HU Ruimin，WANG Zhaoping.A fair load balancing QoS ［J］.Chinese Journal of Computers，2011，34（9）：1650-1659.

［14］GUERIN R A，ORDA A.QoS routing in networks with inaccurate information：theory and algorithms［J］.IEEE／ACM Transactions on Networking，1999，7（3）：350-364.

［15］ MASIP-BRUIN X，MARIN-TORDERA E，YANNUZZI M，et al.Reducing the effects of routing inaccuracy by means of prediction and an innovative linkstate cost［J］.IEEE Communications Letters，2010，14（5）：492-494.

［16］CUI Xunxue，LIN Chuang，WEI Yaya.A multiobjective model for QoS multicast routing based on genetic algorithm ［C］∥Proceedings of the 23rd International Conference on Computer Networks and Mobile Computing.Piscataway，NJ，USA：IEEE，2003：49-53.

［17］CHEN Lei，HEINZELMAN W B.QoS-aware routing based on bandwidth estimation for mobile ad hoc networks［J］.IEEE Journal on Selected Areas in Communications，2005，23（3）：561-572.

［18］唐明董，张国清，杨景，等.互联网可扩展路由 ［J］.软件学报，2010，21（10）：2524-2541.

TANG Mingdong，ZHANG Guoqing，YANG Jing，et al.Scalable routing for the internet ［J］.Journal of Software，2010，21（10）：2524-2541.

［19］李伟，徐正全，杨铸.应用于移动互联网的Peer-to-Peer关键技术 ［J］.软件学报，2009，20（8）：2199-2213.

LI Wei，XU Zhengquan，YANG Zhu.Peer-to-Peer key technologies in mobile internet ［J］.Journal of Software，2009，20（8）：2199-2213.

［20］HANDLEY M，SCHOOLER E，SCHULZRINNE H，et al.Session initiation protocol［S］∥Proposed Internet Standard.New York，USA：ACM，1997：2540-2543.

［21］林闯，李寅，万剑雄.计算机网络服务质量优化方法研究综述 ［J］.计算机学报，2011，34（1）：1-14.

LIN Chuang，LI Yin，WAN Jianxiong.Optimization approaches for QoS in computer networks：a survey［J］.Chinese Journal of Computers，2011，34（11）：1-14.

［22］SU Zhou，OGURO M，OKADA Y，et al.Overlay tree construction to distribute layered streaming by application layer multicast ［J］.IEEE Transactions on Consumer Electronics，2010，56（3）：1957-1962.

［23］AN Jing，PANGALOS P，AGHVAMI A H.Fuzzy non-dominance multipath link-state routing framework for network routing management with inaccurate information［C］∥Proceedings of the 2012IEEE Globecom Workshops.Piscataway，NJ，USA：IEEE，2012：886-890.

［24］SANGUANKOTCHAKORN T，PERERA N.Hybrid multi-constrained optimal path QoS routing with inaccurate link state［C］∥Proceedings of the 2010 9th International Conference on Networks.Piscataway，NJ，USA：IEEE，2010：321-326.

［本刊相关文献链接］

陈家旭，唐亚哲，宁京宣，等.移动自组网中节点兴趣导向的人类运动模型.2013，（12）：110-115.［doi：10.7652／xjtuxb 2013 12019］

陈秀真，李生红，凌屹东，等.面向拒绝服务攻击的多标签IP返回追踪 新方法.2013，（10）：13-17.［doi：10.7652／xjtuxb 201310003］

李强，秦涛，管晓宏，等.对称性的起因：非业务性网络流量新特性的挖掘与探索.2013，（8）：19-25.［doi：10.7652／xjtuxb 201308004］

杜友田，辛刚，郑庆华.融合异构信息的网络视频在线半监督分类方法.2013，（7）：96-101.［doi：10.7652／xjtuxb201307 018］

林军，倪宏，孙鹏，等.一种服务质量可信的按需服务组合方法.2013，46（4）：112-117.［doi：10.7652／xjtuxb201304019］

曹步清，李兵，刘建勋.一种服务质量可信的按需服务组合方法.2013，（2）：131-138.［doi：10.7652／xjtuxb201302022］

夏秦，王志文，卢柯.入侵检测系统利用信息熵检测网络攻击的方法.2013，（2）：14-19.［doi：10.7652／xjtuxb201302003］

陈国强，王宇平.采用离散粒子群算法的复杂网络重叠社团检测.2013，（1）：107-113.［doi：10.7652／xjtuxb201301021］

李晓艳，张海林，郭超平，等.一种异步的认知无线电网络跳频算 法.2012，46（12）：30-35.［doi：10.7652／xjtuxb201212 006］

刘阳，冯志勇，尉志清，等.Nakagami-m信道下认知中继网络的中断概率上界闭式解模型.2012，46（10）：95-100.［doi：10.7652／xjtuxb201210017］

宋婧，丛犁，葛建华，等.双层网络中一种协作博弈的动态资源分配方法.2012，46（10）：89-94.［doi：10.7652／xjtuxb2012 10016］

杜文超，陈庶樵，胡宇翔.面向网络流的自适应正则表达式分组匹配算法.2012，46（8）：49-53.［doi：10.7652／xjtuxb2012 08009］

梁庆伟，姚道远，巩思亮.一种保障时延能量高效的无线传感器网络路由协议.2012，46（6）：48-52.［doi：10.7652／xjtuxb 201206009］

李彬，王文杰，殷勤业，等.无线传感器网络节点协作的节能路由传输.2012，46（6）：1-6.［doi：10.7652／xjtuxb201206001］

陈衡，钱德沛，伍卫国，等.传感器网络基于邻居信息量化的能量平衡路由.2012，46（4）：1-6.［doi：10.7652／xjtuxb2012 04001］

刘逵，刘三阳，冯海林.双信道无线传感器网络移动代理路由算法.2012，46（02）：113-118.［doi：10.7652／xjtuxb201202 019］

任浩，王劲林，尤佳莉.一种高效的对等网络流媒体数据调度算法.2011，45（6）：20-26.［doi：10.7652／xjtuxb201106004］

杨文静，杨新宇，董翅勇.移动Ad Hoc网络中提高路由稳定性的动态备份多径路由.2010，44（12）：16-21.［doi：10.7652／xjtuxb201012004］

翟社平，魏娟丽，李增智.利用服务质量参数值预测的 Web服 务 选 择 方 法.2010，44（6）：57-61.［doi：10.7652／xjtuxb 201006011］

刘刚，崔刚，刘宏伟，等.面向移动节点不确定性特征的自组网路由协议.2010，44（6）：46-50.［doi：10.7652／xjtuxb2010 06009］

翟社平，魏娟丽，李增智.利用服务质量参数值预测的 Web服 务 选 择 方 法.2010，44（6）：57-61.［doi：10.7652／xjtuxb 201006011］

张未展，郑庆华，刘兴卓，等.多P2P覆盖网络的带宽分配方法.2010，44（4）：5-8.［doi：10.7652／xjtuxb201004002］