多约束qos路由选择算法探究

《多约束qos路由选择算法探究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、多约束QoS路由选择算法探究摘要:对于多约束QoS路由选择问题，将其转化为一个多约束赋权图，通过捕食模型调整最小时延和最小丢包率这两个目标的权值，找到非劣解集；然后，利用人工鱼群算法较好地平衡全局搜索能力和局部搜索能力，完成最小成本的路由选择。实验表明：该算法是可行的。关键词:QoS路由选择；捕食模型；非劣解集；人工鱼群算法中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)22-5321-03ResearchofmultipleconstrainedQoSroutingalgorithmDENGCi-yun,LIUZe-wen,NI

2、NGLin-yi(HunanCollegeofInformation,Changsha410200,China)Abstract:ThepapertransformsmultipleconstrainedQoSroutingproblemasthemostshortpathproblemofmultipleconstrainedassign-weightchartthroughaimingatit,andusetheprey-predatormodeltofindthenon-inferiorsetimmediatelybyadjustingtheobjec

3、tsrightofthe6minimumdelayandtheminimumpacketlossrate,TheArtificialFishSwarmAlgorithm,whichcankeepthebalancebetweenglobalandlocalsearchability.Ithasaccomplishedultimateroutingwiththeminimumcostbyusingtheabilityofsearchingtheglobaloptimization.Theexperimentresultsshowthatthealgor-ith

4、miseffective.Keywords:QoSrouting;prey-predatormodel;non-inferiorset;artificialfishswarmalgorithm6随着Internet高速网络迅速发展，要求通信网络能提供高效率服务质量（Qos）支持，当QoS路由选择时，通常对带宽、延时、成本以及丢包率都存在一定的要求。而现有很多算法只针对一个或两个约束条件产生,在多约束Qos下,这些算法具有局限性。如何解决多约束Qos路由问题，及满足业务要求时，尽量减少资源消耗，合理分配网络流量负荷，减少阻塞率，成为关注的热点。生态系统的捕食模

5、型为解决上述问题提供了新解决方法，通常在捕食模型中，捕食者与被捕食者这两者之间能够始终保持一种动态的平衡，两个种群能够实现交替占优，种群规模发生周期性的变化，通过借鉴了上述模型，把路由选择时延与丢包率这两个约束条件作为目标，捕食者和被捕食者种群通过进化从而生成最小时延与最小丢包率的非劣解集[1]。在路由选择的约束条件中，通常优先考虑成本，通过运用人工鱼群算法，通过从捕食模型产生的满足最小时延与最小丢包率的非劣解集中得到满足最小成本的最优解。1多约束QoS路由模型通常一个无向赋权图G（V,E）可以用来表示一个网络，网络的节点用图中的顶点表示，网络连接节点的通信

6、链路用图中的边表示。假设网络节点集用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)链路时延:delay(p)=∑2基于捕食模型的多目标优化求解算法将多约束QoS路由选择时延与丢包率这两个约束条件映射到捕食模型之中，最小链路时延与最小丢包率为我们要考虑的两个目标，一

7、个种群对应了待求解问题的一目标，种群数量代表相应目标的权值。通过把种群数量对应到多目标优化问题的目标权值，3人工鱼群算法寻最优解6多约束QoS路由选择基于捕食模型得到满足最小链路时延和最小丢包率的非劣解集,其中包含捕食者与被捕食者种群,寻找最优解时，两类种群归为一类，把非劣解看成路由选择中若干个结点，再利用人工鱼群算法获取符合最小成本的最优路径即最优解。具体算法步骤如下：步骤1：初始化人工鱼群规模M、每条人工鱼的初始位置、视野Visual和步长Step、拥挤度δ、最大重复尝试次数try_number、最大迭代次数等参数。从非劣解集中给出各个节点的值和每条存在

8、的边的值，给出约束条件中bandwidth(p)、d