Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Network topology design (NTD) with multiple objectives has been presented by many researchers. However, no work in the literature has addressed this issue with both multiple objectives and multiple criteria. In order to suit real-world situations, this paper presents a new idea integrating genetic algorithm and goal programming to establish a model for solving the NTD problem with multiple objectives and multiple criteria taken into consideration. In addition, the proposed model can also solve both construct and extend network topology problems under shared risk link group (SRLG) constraints. Finally, illustrative examples are included to demonstrate the superiority and usefulness of the proposed method.

REFERENCES

• 1: Rana Ejaz Ahmed , Saad Haj Bakry, New topology designs for the future expansion of the academic network of the Gulf countries, International Journal of Network Management, v.7 n.1, p.18-32, January–February 1997 [doi>10.1002/(SICI)1099-1190(199701/02)7:1<18::AID-NEM231>3.0.CO;2-Q]
• 2: L. M. Berry, B. A. Murtagh, G. B. McMahon, S. J. Sugden, and L. D. Welling, "Genetic algorithms in the design of complex distribution networks," Int. J. Phys. Distribution Logist. Management, vol. 28, no. 5, pp. 377-381, 1998.
• 3: C.-T. Chang, "Multi-choice goal programming," Omega, vol. 35, pp. 389-396, 2007.
• 4: A. Charnes and W. W. Cooper, Management Model and Industrial Application of Linear Programming. New York: Wiley, 1961, vol. 1.
• 5: Carlos A. Coello, An updated survey of GA-based multiobjective optimization techniques, ACM Computing Surveys (CSUR), v.32 n.2, p.109-143, June 2000 [doi>10.1145/358923.358929]
• 6: D. Diakoulaki , G. Mavrotas , L. Papayannakis, Determining objective weights in multiple criteria problems: the critic method, Computers and Operations Research, v.22 n.7, p.763-770, Aug. 1995 [doi>10.1016/0305-0548(94)00059-H]
• 7: Reuven Elbaum , Moshe Sidi, Topological design of local-area networks using genetic algorithms, IEEE/ACM Transactions on Networking (TON), v.4 n.5, p.766-778, Oct. 1996 [doi>10.1109/90.541324]
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: L. Guo, H. Yu, and L. Li, "A new shared-path protection algorithm under shared risk link group constraints for survivable WDM mesh networks," Opt. Commun., vol. 246, pp. 285-295, 2005.
• 10: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 11: R. H. Jan, F. J. Hwang, and S. T. Cheng, "Topological optimization of a communication network subject to a reliability constraint," IEEE Trans. Reliabil., vol. 42, no. 1, pp. 63-70, Mar. 1993.
• 12: A. Kumar, R. M. Pathak, and Y. P. Gupta, "Genetic-algorithmbased reliability optimization for computer network expansion," IEEE Trans. Reliabil., vol. 44, no. 1, pp. 63-72, Mar. 1995.
• 13: King-Tim Ko , Kit-Sang Tang , Cheung-Yau Chan , Kim-Fung Man , Sam Kwong, Using Genetic Algorithms to Design Mesh Networks, Computer, v.30 n.8, p.56-61, August 1997 [doi>10.1109/2.607086]
• 14: Xian Liu, Network optimization with stochastic traffic flows, International Journal of Network Management, v.12 n.4, p.225-234, July/August 2002 [doi>10.1002/nem.439]
• 15: B. Liu and K. Iwamura, "Topological optimization models for communication network with multiple reliability goals," Comput. Math. Appl., vol. 39, no. 7, pp. 59-69, 2000.
• 16: E. Manzi, M. Labbe, G. Latouche, and F. Maffioli, "Fishman's sampling plan for computing network reliability," IEEE Trans. Reliabil., vol. 50, no. 1, pp. 41-46, Mar. 2001.
• 17: Nicholas F. Maxemchuk , Iradj Ouveysi , Moshe Zukerman, A quantitative measure for telecommunications networks topology design, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.731-742, August 2005 [doi>10.1109/TNET.2005.852889]
• 18: MATLAB, The Mathworks, Inc., 1999.
• 19: C. C. Palmer and A. Kershenbaumt, "An approach to a problem in network design using genetic algorithm," Networks, vol. 26, pp. 151-163, 1995.
• 20: A. Riedl, "A versatile genetic algorithm for network planning," in Proc. EUNICE'98, 1998, pp. 1-7.
• 21: C. Romero, "Extended lexicographic goal programming: A unifying approach," Omega, vol. 29, pp. 63-71, 2001.
• 22: D. Saha and U. K. Chakraborty, "An efficient link enhancement strategy for computer networks using genetic algorithm," Comput. Commun., vol. 20, no. 9, pp. 798-803, 1997.
• 23: J. Strand, A. L. Chiu, and R. Tkach, "Issues for routing in the optical layer," IEEE Commun. Mag., vol. 39, no. 2, pp. 81-87, Feb. 2001.
• 24: Takeaki Taguchi , Kenichi Ida , Mitsuo Gen, A genetic algorithm for optimal flow assignment in computer network, Computers and Industrial Engineering, v.35 n.3-4, p.535-538, Dec 1998 [doi>10.1016/S0360-8352(98)00152-1]
• 25: M. Tamiz, D. Jones, and C. Romero, "Goal programming for decision making: An overviewof the current state-of-the-art," Eur. J. Oper. Res., vol. 111, pp. 567-581, 1998.
• 26: A. Zalesky, H. L. Vu, M. Zukerman, and I. Ouveysi, "A framework for solving logical topology design problems within constrained computation time," IEEE Commun. Lett., vol. 7, no. 10, pp. 499-501, Oct. 2003.
• 27: G. Zhou and M. Gen, "Genetic algorithm approach on multicriteria minimum spanning tree problem," Eur. J. Oper. Res., vol. 114, no. 1, pp. 141-152, 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design

Keywords:
genetic algorithm (GA), goal programming, network topology design (NTD)