A nondominated sorting genetic algorithm for bi-objective network coding based multicast routing problems
Xing, Huanlai; Qu, Rong
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|
|Peer Reviewed||Peer Reviewed|
|APA6 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|
|Keywords||multicast, multiobjective optimization, network coding, Elitist nondominated sorting genetic algorithm (NSGA-II)|
|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|
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf
You might also like
A Multiobjective Computation Offloading Algorithm for Mobile Edge Computing
A Unified Framework of Graph-based Evolutionary Multitasking Hyper-heuristic
The General Combinatorial Optimisation Problem: Towards Automated Algorithm Design