Research Repository

See what's under the surface

A nondominated sorting genetic algorithm for bi-objective network coding based multicast routing problems

Xing, Huanlai; Qu, Rong

Authors

Huanlai Xing

Rong Qu

Abstract

Network coding is a new communication technique that generalizes routing, where, instead of simply forwarding the packets they receive, intermediate nodes are allowed to recombine (code) together some of the data packets received from different incoming links if necessary. By doing so, the maximum information flow in a network can always be achieved. However, performing coding operations (i.e. recombining data packets) incur computational overhead and delay of data processing at the corresponding nodes.

In this paper, we investigate the optimization of the network coding based multicast routing problem with respect to two widely considered objectives, i.e. the cost and the delay. In general, reducing cost can result into a cheaper multicast solution for network service providers, while decreasing delay improves the service quality for users. Hence we model the problem as a bi-objective optimization problem to minimize the total cost and the maximum transmission delay of a multicast. This bi-objective optimization problem has not been considered in the literature. We adapt the Elitist Nondominated Sorting Genetic Algorithm (NSGA-II) for the new problem by introducing two adjustments. As there are many infeasible solutions in the search space, the first adjustment is an initialization scheme to generate a population of feasible and diversified solutions. These initial solutions help to guide the search towards the Pareto-optimal front. In addition, the original NSGA-II is very likely to produce a number of solutions with identical objective values at each generation, which may seriously deteriorate the level of diversity and the optimization performance. The second adjustment is an individual delegate scheme where, among those solutions with identical objective values, only one of them is retained in the population while the others are deleted. Experimental results reveal that each adopted adjustment contributes to the adaptation of NSGA-II for the problem concerned. Moreover, the adjusted NSGA-II outperforms a number of state-of-the-art multiobjective evolutionary algorithms with respect to the quality of the obtained nondominated solutions in the conducted experiments.

Journal Article Type Article
Publication Date Jun 1, 2013
Journal Information Sciences
Print ISSN 0020-0255
Electronic ISSN 0020-0255
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 233
Institution Citation Xing, H., & Qu, R. (2013). A nondominated sorting genetic algorithm for bi-objective network coding based multicast routing problems. Information Sciences, 233, doi:10.1016/j.ins.2013.01.014
DOI https://doi.org/10.1016/j.ins.2013.01.014
Keywords multicast, multiobjective optimization, network coding, Elitist nondominated sorting genetic algorithm (NSGA-II)
Publisher URL http://www.sciencedirect.com/science/article/pii/S0020025513000716
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
Additional Information NOTICE: this is the author’s version of a work that was accepted for publication in Information Sciences. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Information Sciences, 233 (2013), 36-52, doi: 10.1016/j.ins.2013.01.014

Files

INS13nsga.pdf (1.3 Mb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf




Downloadable Citations