The Library

An effective genetic algorithm for network coding

Tools

Hu, Xiao-Bing, Leeson, Mark S., 1963- and Hines, Evor, 1957-. (2012) An effective genetic algorithm for network coding. Computers & Operations Research, Vol.39 (No.5). pp. 952-963. ISSN 0305-0548

Preview

PDF
WRAP_Leeson_9976551-es-010911-ga4nc3rdresubmission-msl.pdf - Accepted Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (716Kb)

Official URL: http://dx.doi.org/10.1016/j.cor.2011.07.014

Abstract

The network coding problem (NCP), which aims to minimize network coding resources such as nodes and links, is a relatively new application of genetic algorithms (GAs) and hence little work has so far been reported in this area. Most of the existing literature on NCP has concentrated primarily on the static network coding problem (SNCP). There is a common assumption in work to date that a target rate is always achievable at every sink as long as coding is allowed at all nodes. In most real-world networks, such as wireless networks, any link could be disconnected at any time. This implies that every time a change occurs in the network topology, a new target rate must be determined. The SNCP software implementation then has to be re-run to try to optimize the coding based on the new target rate. In contrast, the GA proposed in this paper is designed with the dynamic network coding problem (DNCP) as the major concern. To this end, a more general formulation of the NCP is described. The new NCP model considers not only the minimization of network coding resources but also the maximization of the rate actually achieved at sinks. This is particularly important to the DNCP, where the target rate may become unachievable due to network topology changes. Based on the new NCP model, an effective GA is designed by integrating selected new problem-specific heuristic rules into the evolutionary process in order to better diversify chromosomes. In dynamic environments, the new GA does not need to recalculate target rate and also exhibits some degree of robustness against network topology changes. Comparative experiments on both SNCP and DNCP illustrate the effectiveness of our new model and algorithm.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Engineering
Library of Congress Subject Headings (LCSH):	Genetic algorithms, Packet transport networks
Journal or Publication Title:	Computers & Operations Research
Publisher:	Elsevier BV
ISSN:	0305-0548
Date:	May 2012
Volume:	Vol.39
Number:	No.5
Number of Pages:	12
Page Range:	pp. 952-963
Identification Number:	10.1016/j.cor.2011.07.014
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	EP/F033591/1 (EPSRC)
References:	[1] Ahlswede, R. N. Cai, S.Y.R. Li and R.W. Yeung, ―Network information flow‖, IEEE Trans. Inform. Theory, vol.46, no.4, pp. 1204-1216, 2000. [2] Kim, M., C.W. Ahn, M. Medard and M. Effros, ―On minimizing network coding resources: An evolutionary approach‖, NetCod 2006, Boston, 7 April 2006. [3] Richey, M.B. and R.G. Parker, ―On multiple steiner subgraph problems‖, Networks, vol.16, no.4, pp. 423-438, 1986. [4] Fragouli, C. and R.G. Parker, ―Information flow decomposition for network coding‖, IEEE Trans, Inform. Theory, vol.52, no.3, pp. 829-848, 2006. [5] Langberg, M., A. Sprintson and J. Bruck, ―The encoding complexity of network coding‖, IEEE Trans, Inform. Theory, vol.52, no.6, pp. 2386-2397, 2006. [6] Bhattad, K, N. Ratnakar, R. Koetter and K.R. Narayanan, ―Minimal network coding for multicast‖, in Proc. IEEE ISIT’05, pp. 1730-1734, Adelaide, SA, 4-9 Sep, 2005. [7] Holland, J.H. Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975. [8] Eiben, A.E. and J. E. Smith, Introduction to Evolutionary Computing, Berlin, Germany: Springer-Verlag, 2003. [9] Rose, C. and R.D. Yates, ―Genetic algorithms and call admission to telecommunications networks‖, Computers & Operations Research, vol.23,no.5, pp. 485-499, 1996. [10] Mendes, J.J.M., J.F. Gonçalves, and M.G.C. Resende. ―A random key based genetic algorithm for the resource constrained project scheduling problem‖, Computers & Operations Research, vol.36, no.1, pp. 92-109, 2009. [11] Kim, M., M. Medard, V. Aggarwal, U.M. O’Reilly, W. Kim, C.W. Ahn and M. Effros, ―Evolutionary approachs to minimizing network coding resources‖, Proceedings of the 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007), Anchorage, AK, May 2007. [12] Kim, M, V. Aggarwal, U.M. O’Reilly, M. Medard and W. Kim, ―Genetic representation for evolutionary minimization of network coding resources‖, Proceedings of the 4th European Workshop on the Application of Nature-Inspired Techniques to Telecommunication Networks and Other Connected Systems (EvoCOMNET 2007), Valencia, Spain, April 2007. [13] Kim, M., V. Aggarwal, U.M. O’Reilly and M. Medard, ―A Doubly Distributed Genetic Algorithm for Network Coding‖, Proceedings of the 9th annual conference on Genetic and evolutionary computation (GECCO 2007), London, England, 2007. [14] Ho, T., B. Leong, M. M´edard, R. Koetter, Y. Chang, and M. Effros., ―The Utility of Network Coding in Dynamic Environments‖. In IWWAN, 2004. [15] Ho, T., M. M´edard, J. Shi, M. Effros, and D. R. Karger, ―On randomized network coding,‖ in 41st Annual Allerton Conference on Communication,Control and Computing, Monticello, USA, 2003. [16] Ho, T., R. Koetter, M. M´edard, D. R. Karger, and M. Effros, ―The benefits of coding over routing in a randomized setting,‖ in IEEE Int. Symp.Inform. Theory, Yokohama, Japan, 2003. [17] Ho, T., M. M´edard, R. Koetter, D. R. Karger, M. Effros, S. Jun, and B. Leong, ―A Random Linear Network Coding Approach to Multicast,‖ IEEE Trans. Inform. Theory, vol.52(10), pp. 4413 - 4430, 2006. [18] Cooper, C. ―On the distribution of rank of a random matrix over a finite field,‖ Random Struct. Algorithms, vol. 17, pp. 197–212, 2000. [19] Campo, A.T. and A. Grant, ―On Random Network Coding for Multicast‖, available online. [20] Hu, X.B., M,S. Leeson, E.L. Hines, ―An Effective Genetic Algorithm for the Network Coding Problem‖, The 2009 IEEE Congress on Evolutionary Computation (CEC2009), 18-21 May 2009, Trondheim, Norway. [21] Koetter, R. and M. M´edard, ―An algebraic approach to network coding,‖ IEEE/ACM Trans. Networking, vol. 11, no. 5, pp. 782–795, 2003. [22] Ngatchou, P. Anahita Zarei El-Sharkawi, M.A., ―Pareto Multi-Objective Optimization‖, Proceedings of the 13th International Conference on Intelligent Systems Application to Power Systems, pp. 84 - 91, 6-10 Nov. 2005 [23] Sywerda, G., ―Uniform crossover in genetic algorithms‖, Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2-9, San Francisco, USA, [24] Falkenauer, E., ―The worth of uniform crossover‖, Proceedings of the 1999 Congress on Evolutionary Computation, pp. 782, CEC99, USA. [25] Melancon, G. and F. Philippe, ―Generating connected acyclic digraphs uniformly at random,‖ Inf. Process. Lett., vol. 90, no. 4, pp. 209–213, 2004. [26] Corder, G.W. and D.I. Foreman, "Nonparametric Statistics for Non-Statisticians: A Step-by-Step Approach". New York: Wiley, 2009.
URI:	http://wrap.warwick.ac.uk/id/eprint/37245