A cross entropy approach to design of reliable networks

被引:29
作者
Altiparmak, Fulya [1 ]
Dengiz, Berna [2 ]
机构
[1] Gazi Univ, Dept Ind Engn, TR-06570 Ankara, Turkey
[2] Baskent Univ, Dept Ind Engn, TR-06530 Ankara, Turkey
关键词
Communication networks; Network design; Network reliability; Cross-entropy method; Meta-heuristics; Monte Carlo technique; RELIABILITY OPTIMIZATION; TOPOLOGICAL OPTIMIZATION; GENETIC-ALGORITHM; COMMUNICATION-NETWORKS; ALLOCATION PROBLEM; SYSTEMS;
D O I
10.1016/j.ejor.2008.11.022
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on cross-entropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:542 / 552
页数:11
相关论文
共 40 条
[1]   A neural approach to topological optimization of communication networks, with reliability constraints [J].
AboElFotoh, HMF ;
Al-Sumait, LS .
IEEE TRANSACTIONS ON RELIABILITY, 2001, 50 (04) :397-408
[2]   TOPOLOGICAL LAYOUT OF LINKS FOR OPTIMIZING THE OVERALL RELIABILITY IN A COMPUTER-COMMUNICATION SYSTEM [J].
AGGARWAL, KK ;
CHOPRA, YC ;
BAJWA, JS .
MICROELECTRONICS AND RELIABILITY, 1982, 22 (03) :347-351
[3]   Application of the cross-entropy method to the buffer allocation problem in a simulation-based environment [J].
Alon, G ;
Kroese, DP ;
Raviv, T ;
Rubinstein, RY .
ANNALS OF OPERATIONS RESEARCH, 2005, 134 (01) :137-151
[4]   Optimal design of reliable computer networks: A comparison of metaheuristics [J].
Altiparmak, F ;
Dengiz, B ;
Smith, AE .
JOURNAL OF HEURISTICS, 2003, 9 (06) :471-487
[5]  
[Anonymous], 1979, Computers and Intractibility: A Guide to the Theory of NP-Completeness
[6]   RELIABILITY OPTIMIZATION OF COMMUNICATION-NETWORKS USING SIMULATED ANNEALING [J].
ATIQULLAH, MM ;
RAO, SS .
MICROELECTRONICS AND RELIABILITY, 1993, 33 (09) :1303-1319
[7]   LARGE-SCALE NETWORK TOPOLOGICAL OPTIMIZATION [J].
BOORSTYN, RR ;
FRANK, H .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1977, 25 (01) :29-47
[8]   A cross entropy algorithm for the Knapsack problem with setups [J].
Caserta, M. ;
Rico, E. Quinonez ;
Uribe, A. Marquez .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (01) :241-252
[9]   A cross entropy-Lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times [J].
Caserta, M. ;
Quinonez Rico, E. .
COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) :530-548
[10]   Topological optimization of a reliable communication network [J].
Cheng, ST .
IEEE TRANSACTIONS ON RELIABILITY, 1998, 47 (03) :225-233