Speeding up of genetic algorithm for network topology optimization with use of cumulative updating of network reliability

ABSTRACT

Network optimization problems in conditions of constraints are NP-hard problems mostly. Genetic Algorithms are applicable solution for network structure optimization and for obtaining good results within acceptable periods of time. In this study we consider the problem of network topology optimization with unreliable communication channels and perfectly reliable nodes in order to obtain the most reliable structure. The problem of reliability computing for such networks is NP-hard so exact algorithm demands enormous computational effort. However, the method based on cumulative updating of lower and upper bounds of network reliability allows to decide the feasibility of a given network without performing exhaustive calculation of reliability. Relying on this technique we propose a new method which speed up network optimization process by the genetic algorithm.

References

1. F. Sun and M. Shayman. On Pairwise Connectivity of Wireless Multihop Networks. International Journal of Security and Networks, special issue on Computer and Network Security, Vol. 2, No. 1/2, p. 37--49, 2007.
2. M. Youssef, Y. Khorramzadeh and S. Eubank. Network reliability: The effect of local network structure on diffusive processes. Physical Review, E 88(5), Article 052810, 2013.
3. Ch. J. Colbourn. The Combinatorics of Network Reliability. New York: Oxford University Press, p. 160, 1987.
4. H. Cancela and L. Petingi. Diameter constrained network reliability: exact evaluation by factorization and bound. Proc. of the International Conf. on Industrial Logistics, Japan, p. 359--366, 2001.
5. Y. Chen, J. Li and J. Chen. A New Algorithm for Network Probabilistic Connectivity. Proc. of the Military Communications Conference. IEEE Press. Vol. 2, p. 920--923, 1999.
6. D. A. Migov and O. K. Rodionova. Calculating Two-Terminal Reliability in a Diameter Constrained Network with Cutenodes. In ACM ICUIMC 2012 Proceedings (Kuala Lumpur, Malaysia), article 130. ACM New York, USA, 2012.
7. D. A. Migov. Computing Diameter Constrained Reliability of a Network with Junction Points. Automation and Remote Control, Vol. 72, n. 7, p. 1415--1419, 2011.
8. J.-M. Won and F. Karray. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision. IEEE Trans. on Reliability, 59(3): 551--562, September 2010.
9. A. S. Rodionov, D. A. Migov and O. K. Rodionova. Improvements in the Efficiency of Cumulative Updating of All-Terminal Network Reliability. IEEE Transactions on Reliability, Vol. 61, n. 2, p. 460--465, June 2012.
10. J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann. Arbor, Michigan, 1975.
11. I. Njini and O. O. Ekabua. Genetic Algorithm Based Energy Efficient Optimization Strategies in Wireless Sensor Networks: A Survey. ACSIJ Advances in Computer Science: an International Journal, Vol. 3, Issue 5, No. 11, September 2014.
12. C. R. Darwin. On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. London: John Murray, 1859.
13. A. S. Rodionov, H. Choo and K. A. Nechunaeva. Framework for Biologically Inspired Graph Optimization. In Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication, article 11, 2011.
14. G. Pandurangan, P. Raghavan, and E. Upfal. Building Low-Diameter Peer-to-Peer Networks. IEEE Journal on Selected Areas in Communications (JSAC), Issue on Internet and WWW Measurement, Mapping, and Modeling, 21(6), p. 995--1002, August 2003.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows