摘要
基于跳数约束的R边连通网络设计就是设计一个网络,且任意两点之间满足给定的边连通度及跳数要求,使得链路的总费用为最小。本文提出了一个启发式迭代求解该问题的算法。首先形成一个初始R边连通图,通过边交换来迭代降低边集的费用;最后增加一些边满足跳数约束,再通过边置换和边删除来降低费用得到一个较优的扩充图。
The problem of R-edge-connectivity network planning based on hop-constraint is to design a network that meets the constraint of the given edge-connectivity and the number of hops while minimizing the total cost of the edge-linked connection. In this paper, a heuristic iterative algorithm is presented to solve the problem. According to this algorithm, an initial R-edge-connectivity graph is formed. Then the cost is reduced by iteratively exchanging edges. Finally some edges are added to meet the requirement of the number of hops. A better graph is obtained in terms of cost reduction through edge shifting and edge-deleting.
出处
《电路与系统学报》
CSCD
2004年第2期122-125,共4页
Journal of Circuits and Systems
基金
哈尔滨工业大学校基金资助项目(HIT2001.30)
关键词
网络设计
跳数
R边连通
network planning
hop
R-edge-connection
