基于多约束QoS问题的启发式算法

摘要：

由于多媒体通信的需要,QoS路由技术已成为通信网络中研究的热点.通常情况下,在网络中寻找同时满足多个独立加性约束条件的路由是一个NP完全问题.本文探讨了多约束条件下的路径选择(MCP)问题,通过将MCP问题转化为离散化的动态网络,得到了一个性能更好的启发式QoS路由算法,复杂度从O(Tmn)降低为O( Tm),其中m、n分别是节点数和边数,T是算法定义的正整数,并在理论上证明了算法的正确性.最后给出实验举例,并通过与现有算法性能比较,表明改进的启发式算法能快速、有效地解决MCP问题,且适用于大规模的网络系统.

关键词：QoS路由、路径选择、多约束条件、启发式算法、MCP

所属期刊栏目：33

分类号：TN915.1

资助基金：国家973计划资助项目613610202

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：19-23