实用标准文案精彩文档多约束QoS路由选择算法研究邓慈云１宁玲一１刘泽文１１（湖南信息职业技术学院湖南410200）摘要:对于多约束QoS路由选择问题，将其转化为一个多约束赋权图，通过捕食模型调整最小时延和最小丢包率这两个目标的权值，找到非劣解集；然后，利用人工鱼群算法较好地平衡全局搜索能力和局部搜索能力，完成最小成本的路由选择。实验表明：该算法的可行性。关键词:QoS路由选择；捕食模型；非劣解集；人工鱼群算法文献标识码:A中图分类号:TP301.6ResearchofmultipleconstrainedQoSroutingalgorithmDengci-yun１,Liuze-wen１１(HunanCollegeofInformation,Changsha410200,China)Abstract:ThepapertransformsmultipleconstrainedQoSroutingproblemasthemostshortpathproblemofmultipleconstrainedassign-weightchartthroughaimingatit,andusetheprey-predatormodeltofindthenon-inferiorsetimmediatelybyadjustingtheobjectsrightoftheminimumdelayandtheminimumpacketlossrate,TheArtificialFishSwarmAlgorithm,whichcankeepthebalancebetweenglobalandlocalsearchability.Ithasaccomplishedultimateroutingwiththeminimumcostbyusingtheabilityofsearchingtheglobaloptimization.Theexperimentresultsshowthatthealgor-ithmiseffective.Keywords:QoSrouting;prey-predatormodel;non-inferiorset;artificialfishswarmalgorithm0引言随着Internet高速网络的迅速发展，要求通信网络能提供高效的服务质量（Qos）支持，通常在QoS路由选择时,对带宽、延时、成本及丢包率都有一定的要求.而现有很多算法只针对一个或两个约束条件产生的,在多约束Qos下,这些算法具有局限性。如何解决多约束Qos路由问题，及满足业务要求时，尽量减少资源消耗，合理分配网络的流量负荷，减少阻塞率，成为关注的热点。生态系统的捕食模型为解决该问题提供了新的思路，在捕食模型中，捕食者和被捕食者始终维持一种动态平衡，两个种群交替占优，种群规模周期性变化，借鉴该模型，将路由选择的时延和丢包率两个约束条件作为目标，通过捕食者与被捕食者种群进化产生最小时延和最小丢包率的非劣解集[1]。在路由选择众多的约束条件中，成本常常被优先考虑，借鉴人工鱼群算法，从捕食模型产生的满足的最小时延和最小丢包率的非劣解集中获取符合最小成本的最优解。1多约束QoS路由模型一个网络可以表示成一个无向赋权图G（V,E），图中顶点表示网络节点，边表示网络中连接节点的通信链路。其中V表示网络节点集，E表示连接节点的通信链路集。为简化问题，假设网络中每对节点之间至多只有一条链路。基于无向图G(V,E),设p=p(r,s)为从源结点r到目的节点s的一条路径，e为路径p上的一条链路，即e∈p。对几个常用QoS指标进行数学表示如下[3]：(1)瓶颈带宽：bandwidth(p)=min{b(e)},b(e)为链路e上带宽；(2)链路时延:()(),epdelaypdelaye()delaye为链路e上的时延；(3)成本：cos()cos(),cos()eptptete为链路e上成本；(4)丢包率：()1(1()),()eplossplele为链路e上的丢包率。多约束QoS问题的目标：找到一条路径p(s,d),在下列的多个约束条件下，使它符合最小成本且满足最小链路时延和最小丢包率。(1)瓶颈带宽约束：bandwidth(p)B，B表示瓶颈带宽约束；(2)链路时延约束：delay(p)D，D表示链路时延约束；(3)成本约束：delay-jitter(p)C，C表示成本约束；(4)丢包率约束：loss(p)L,L表示丢包率约束。2基于捕食模型的多目标优化求解算法多约束QoS路由选择中两个约束条件:时延和丢包率映射到下述捕食模型中，考虑两个目标:最小链路时延和最小丢包率，一个种群对应待求解问题的一个目标，种群数量表示相应目标的权值。通过将种群数量对应到多目标优化问题的目标权值，可得到权值调整策略。故目标的重要性体现在种群的竞争优势，种群的竞争使进化过程中各个目标交替占优，从而实现动态演化的多目标优化算法。基于捕食模型的一般算法流程如图1所示，其中算法流程图中的进化产生新一代种群，利用捕食者—被捕食者差分方程模型计算种群的数量，实现如下：(1)变量的定义：it表示指定的时刻;iF表示在时刻it的被捕食者收稿日期：2012-3-10...
