基于交叉熵的多约束QoS组播路由蚂蚁算法

J4 ›› 2010, Vol. 45 ›› Issue (5): 35-41.

基于交叉熵的多约束QoS组播路由蚂蚁算法

葛连升1,周加强2,秦丰林1

1. 山东大学网络与信息中心, 山东济南 250100; 2. 山东大学基建处, 山东济南 250100

收稿日期:2010-02-03 出版日期:2010-05-16 发布日期:2010-05-24
作者简介:葛连升(1967-),男,副教授,主要研究方向为网络路由与组播算法、网络与系统安全等.Email:lsge@sdu.edu.cn
基金资助:
国家自然科学基金资助项目(60773101);山东省自然科学基金资助项目(Y2007G42);中国下一代互联网CNGI大规模路由和组播技术的研究与试验项目(CNGI-04-13-2T)

A cross-entropy based ant colony algorithm for multiple QoS constrained multicast routing

GE Lian-sheng1, ZHOU Jia-qiang2, QIN Feng-lin1

1. Network and Information Center, Shandong University, Jinan 250100, Shandong, China;
2. The Capital Construction Office, Shandong University, Jinan 250100, Shandong, China

Received:2010-02-03 Online:2010-05-16 Published:2010-05-24

摘要/Abstract

摘要：

基于多媒体传输的网络应用均对服务质量(quality of service,QoS)有迫切的需求,如带宽、延迟、丢包率等。寻找满足上述QoS要求的组播树问题是一个NP-完全问题。在已有的多约束QoS组播路由算法中主要是局部搜索算法或集中式搜索算法,这些均不能保证在实际网络中找到全局解。本文提出用基于交叉熵的蚁群优化算法来求解多约束QoS组播路由问题,NS2仿真结果表明该算法能够快速找到近似最优解。

关键词: 交叉熵;蚂蚁算法;组播路由;服务质量

Abstract:

Many applications in network like multimedia transmission have stringent demands for quality of service (QoS), such as bandwidth, delay, and packet loss rate. Finding the multicast tree that satisfies these requirements is an NP-complete problem. Among the existing algorithms for multiple QoS constrained multicast are local search algorithms or centralized algorithms, which cannot guarantee the finding of global solutions in a real network. In this paper, an ant colony algorithm based on cross-entropy was proposed for multiple QoS constrained multicast routing. Simulation results in the NS-2 environment indicated that this algorithm could quickly find the close-to-the-best solution.

Key words: cross-entropy; ant colony system; multicast routing; quality of service (QoS)

葛连升1,周加强2,秦丰林1. 基于交叉熵的多约束QoS组播路由蚂蚁算法[J]. J4, 2010, 45(5): 35-41.

GE Lian-sheng1, ZHOU Jia-qiang2, QIN Feng-lin1. A cross-entropy based ant colony algorithm for multiple QoS constrained multicast routing[J]. J4, 2010, 45(5): 35-41.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed