求解QoS组播路由问题的满意优化方法

引言

  传统的QoS路由算法大都试图尽最大能力找到能满足用户要求的最优路由。然而,由于网络模型和网络状态信息的非精确性使得难以获得最优路由,甚至根本不存在传统意义下的最优路由。

  QoS路由问题是典型的多目标优化问题,其最显著特点是优化目标之间的不可公度性和优化目标的矛盾性。不可公度性是指各个优化目标之间没有统一的度量,如时延和时延抖动的度量单位是时间(ms)、费用是元、丢包率无量纲、带宽的单位用bps等。从物理意义上讲,不能像传统方法那样把多个优化目标简单归并为单个目标。另一个普遍存在着的问题是在进行多约束QoS路由优化时,许多文献为了计算方便将参数大量简化。例如去掉网络中剩余带宽比QoS要求带宽小的链路后,在剩下的链路中只考虑在其他QoS度量下的最优路由,而不再考虑带宽,对该参数的优化有一定的局限性。

  满意优化本质上是一个多目标优化方法,它摈弃了传统的最优概念,强调的是满意而不是最优[1,2]。本文针对QoS路由选择的实际情况,提出一个基于满意优化原理的QoS路由求解模型。它在难以获取最优解的情况下,寻求满意解以代替最优解;引入满意度函数,简单而合理的满意度函数使得不必为了简化而省略重要的QoS参数,达到同时优化多个约束参数、保证全部服务质量参数性能的目的。仿真实验证明,采用改进遗传算法(GA)实现多约束QoS路由问题满意优化设计的算法,具有操作简单、全局收敛速度快、实用性强等优点。

  3满意度函数的设计

  满意度函数是用来评价在一定性能评价准则下求得的满意解的质量函数。在实际应用中,可以根据优化问题的不同应用背景,设计相应的满意度函数来完成满意解的评价。图1为剩余带宽占有率的满意度函数。图2为时延的满意度函数。图1中Rmin代表用户应用对剩余带宽的最低要求。考虑到网络参数的非实时性和不准确性,所有的参数均应留有一定的冗余,这一点可以通过设定略高于业务最低要求的Ropt来保证。以带宽为例,假定找到一条路径,其剩余带宽刚刚满足业务对带宽的要求Rmin,则如果简单地把这条路径视为可行路径显然是不合理的。而且,如果网络中的部分链路已经负载很重,那么出于平衡流量的目的,更应该优先选择剩余带宽较多的路径。满意度函数是实现这个目的的有效手段。将Ropt点的满意度设为0.6,而将Rmin点的满意度设为0,即可达到提高链接建立成功率的目的。Rmax的值可以设定为远大于Rmin,以使那些有很多剩余带宽的路径可以得到优先考虑(剩余带宽最多的路径带宽满意度最高)。其他参数的满意度函数的设定原理与此类似。其中时延、时延抖动、丢包率和费用采用类似图2的降折线性满意度函数。 

  给出QoS路由多目标满意优化的一般步骤:

  a)建立网络QoS路由选择的数学模型。

  b)选择性能指标(QoS度量),并设计其满意度函数。

  c)设计综合满意度函数。

  d)用遗传算法对多约束QoS路由选择问题进行搜索寻优计算。

  e)通过仿真来验证优化设计结果。

  4QoS组播路由问题的满意优化遗传算法

  1)编码

  6结束语

  满意优化方法将多个服务质量参数同时优化,性能指标的满意度函数体现了对各性能指标的要求,而综合满意度函数则体现了决策者综合考虑了系统各种矛盾因素后作出的一种决策要求。这种满意优化方法融合了设计者关于性能指标要求的智能因素,更利于接近实际情况,具有很广泛的实用性和灵活性。当许多实际优化问题难以获得最优解或一些优化问题本身不存在最优解时,用本文的方法去寻求满意解以代替最优解是解决这类实际问题较好的策略。仿真实验证明了该算法的实用性、有效性、简易性以及收敛速度快的特点。当QoS约束参数较多时,该算法也能表示出很好的性能,能满足一定的实际需求。