双归属环形网络拓扑规划算法设计

doi:10.3969/j.issn.1000-0801.2012.08.013

摘要/Abstract

摘要：

本文研究了一种高效的双归属环形网络拓扑规划算法，提出了在满环与非满环间调整节点的启发式搜索算法，当节点数在1 500个以内时，本算法都能很快求解，而现有算法通常只能处理几百个节点的中等规模网络。本文首先给出了相关数学模型，然后详述了初始拓扑生成过程及采用的启发式优化算法。最后通过将CPLEX规划结果、人工规划结果和算法规划进行比对，验证算法性能。

关键词: 双归属, 环形拓扑, 启发式算法, 整数规划

Abstract:

This paper develops an efficient algorithm to design hierarchical dual-homing ring network.A heuristic algorithm that adjusts nodes between full-rings and non-full rings is presented.The solution can be obtained for up to 1 500 nodes in a small amount of time,while the existing algorithms usually can only handle a few hundred nodes.First this paper presentes the mathematical model,and then details the initial topology generation algorithm and the heuristic algorith m.Finally,the performance of the algorithm is verified through compare the topology with results obtained from the CPLEX and manual design.

Key words: dual-homing, ring topology, heuristic algorithm, integer programming

卢研平,吕光宏. 双归属环形网络拓扑规划算法设计[J]. 电信科学, 2012, 28(8): 69-74.

Yanping Lu,Guanghong Lv. Algorithm for Dual-Homing Ring Network Design[J]. Telecommunications Science, 2012, 28(8): 69-74.

图/表 7

图1

图2

表1

图3

表2

图4

表3

参考文献 10

1	Kang D , Lee K , Park S , et al. Design of local networks using USHRs. Telecommunication Systems, 2000, 14 (1-4): 197～217
2	SHI J , Fonseka J . Hierarchical self-healing rings. IEEE/ACM Transactions on Networking, 1994, 21 (4): 690～697
3	SHI J , Fonseka J . Analysis and design of survivable telecommunications networks, IEE Proceedings-Communications, 1997, 144 (5): 322～330
4	Kshirsagar K , Kaza K , Rajan K . Design of 2-level hierarchical ring networks. Proceedings of 3rd International Congress on Ultra Modern Telecommunications and Control Systems and Workshops （ICUMT）, Budapest 2011
5	Thomadsen T , Stidsen T . Hierarchical ring network design using branch-and-price. Telecommunication Systems, 2005, 29 (1): 61～76
6	Goldschmidt O , Laugier A , Olinick E . SONET/SDH ring assignment with capacity constraints. Discrete Applied Mathematics, 2003, 129 (1): 99～128
7	Fortz B , Soriano P , Wynants C . A tabu search algorithm for self-healing ring network design. European Journal of Operational Research, 2003, 151 (2): 280～295
8	Halit Uster , Sarath K . Algorithms for the design of network topologies with balanced disjoint rings. Journal of Heuristics, 2010, 16 (1): 37～63
9	Paula C , Bernard F , Martine L , et al. Improved formulations for the ring spur assignment problem. Proceedings of the 5th International Conference on Network Optimization, Hamburg,Germany, 2011: 24～36
10	Pop P C . New integer programming formulations of the generalized travelling salesman problem. American Journal of Applied Sciences, 2007, 4 (11): 932～937

节点个数	CPLEX代价（km）	算法代价（km）	代价比	CPLEX时间（s）
6	29.674	29.674	100%	21
7	30.876	30.876	100%	37
8	34.587	34.587	100%	80
9	38.321	40.873	93.8%	140
10	41.873	45.239	92.5%	210
11	48.839	48.839	100%	321
12	50.297	60.938	82.5%	698
13	55.987	59.932	93.4%	1 876
14	59.892	59.892	100%	4 876
15	60.192	76.389	78.8%	13 761

场景代号	节点个数（个）	w	l	时间（ms）
NVX-ATN	90	4	2	675
VLZ-ATN	113	4	4	1 013
NIV-ATN	180	5	4	3 300
LZS-ATN	180	5	3	4 018
MIN-ATN	215	9	5	4 896
NLZ-L2	270	7	3	4 691
NVX-L2	275	8	2	4 813
MIN-L2	306	6	4	8 297

节点个数（个）	汇聚节点个数（个）	初始拓扑时间（s）	总时间（s）
300	28	0.978	8.216
500	48	1.642	27.266
700	46	8.914	70.174
900	68	12.876	136.439
1 100	80	31.329	290.985
1 200	88	48.317	428.197
1 300	92	60.937	773.157
1 400	100	109.732	1 118.782
1 500	108	190.837	2 904.672

[1]	徐加利,张海霞,袁东风. 两跳放大转发中继网络中的ε-全局最优多中继选择策略[J]. 电信科学, 2011, 27(8): 39-44.
[2]	陈晓华,李春芝,张鹏宇. 虚拟主机云存储系统VCloudStorage及文件传输协议VCFTP[J]. 电信科学, 2011, 27(7): 59-66.
[3]	陈晓华,李春芝,俞坚奇. 虚拟主机云存储系统整数规划模型及最优化分配算法[J]. 电信科学, 2011, 27(1): 89-94.