The Library
An effective genetic algorithm for network coding
Tools
Hu, XiaoBing, Leeson, Mark S., 1963 and Hines, Evor, 1957. (2012) An effective genetic algorithm for network coding. Computers & Operations Research, Vol.39 (No.5). pp. 952963. ISSN 03050548

PDF
WRAP_Leeson_9976551es010911ga4nc3rdresubmissionmsl.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 realworld 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 rerun 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 problemspecific 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.
[error in script] [error in script]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:  03050548 
Date:  May 2012 
Volume:  Vol.39 
Number:  No.5 
Number of Pages:  12 
Page Range:  pp. 952963 
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. 12041216, 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. 423438, 1986. [4] Fragouli, C. and R.G. Parker, ―Information flow decomposition for network coding‖, IEEE Trans, Inform. Theory, vol.52, no.3, pp. 829848, 2006. [5] Langberg, M., A. Sprintson and J. Bruck, ―The encoding complexity of network coding‖, IEEE Trans, Inform. Theory, vol.52, no.6, pp. 23862397, 2006. [6] Bhattad, K, N. Ratnakar, R. Koetter and K.R. Narayanan, ―Minimal network coding for multicast‖, in Proc. IEEE ISIT’05, pp. 17301734, Adelaide, SA, 49 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: SpringerVerlag, 2003. [9] Rose, C. and R.D. Yates, ―Genetic algorithms and call admission to telecommunications networks‖, Computers & Operations Research, vol.23,no.5, pp. 485499, 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. 92109, 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 NatureInspired 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), 1821 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 ElSharkawi, M.A., ―Pareto MultiObjective Optimization‖, Proceedings of the 13th International Conference on Intelligent Systems Application to Power Systems, pp. 84  91, 610 Nov. 2005 [23] Sywerda, G., ―Uniform crossover in genetic algorithms‖, Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 29, 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 NonStatisticians: A StepbyStep Approach". New York: Wiley, 2009. 
URI:  http://wrap.warwick.ac.uk/id/eprint/37245 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 