摘要: 研究通信网络在不同目标下的铺设策略。为满足不同需求,建立网络终端之间的距离矩阵并将其转化为一个全连通无向赋权图。根据网络设计标准,以最低成本为唯一目标建立最短路径模型,利用Prim算法求解得到最小生成树。在最小生成树逻辑结构上建立稳定性度约束模型,给出满足度约束的铺设方案。综合考虑网络铺设的多方面影响因素,建立多目标组合优化模型,基于蚁群算法设计不同链路通断概率、不同链路数目和较高稳定性下的全局最优铺设策略。
关键词:
网络铺设,
最小生成树,
Prim算法,
蚁群算法,
组合优化
Abstract: This paper studies the laying strategy of communication network with different objectives. To satisfy different requirements, distance matrix of network terminals is established, and transferred to an undirected weighed graph that is fully connected. According to the network design standard, considering only the shortest distance, model of Minimum Spanning Tree(MST) is developed, and solved with Prim algorithm to obtain the shortest routes. Based on the logical structure of minimum spanning tree, a stability degree constraint model is established and the laying scheme is given. Considering the integrated factors of network laying, Ant Colony Algorithm(ACA) is employed to get the connecting condition with different on-off rate of links, different number of links and maximum network traffic, and to obtain the corresponding laying routes.
Key words:
network laying,
Minimum Spanning Tree(MST),
Prim algorithm,
Ant Colony Algorithm(ACA),
combined optimization
中图分类号:
龚承柱, 诸克军, 郭海湘. 基于蚁群算法的多目标网络铺设策略研究[J]. 计算机工程, 2011, 37(15): 177-180.
GONG Cheng-Zhu, CHU Ke-Jun, GUO Hai-Xiang. Research of Multi-objective Network Laying Strategy Based on Ant Colony Algorithm[J]. Computer Engineering, 2011, 37(15): 177-180.