Huanlai Xing
A nondominated sorting genetic algorithm for bi-objective network coding based multicast routing problems
Xing, Huanlai; Qu, Rong
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.
Citation
Xing, H., & Qu, R. (2013). A nondominated sorting genetic algorithm for bi-objective network coding based multicast routing problems. Information Sciences, 233, https://doi.org/10.1016/j.ins.2013.01.014
Journal Article Type | Article |
---|---|
Publication Date | Jun 1, 2013 |
Deposit Date | Feb 26, 2015 |
Publicly Available Date | Feb 26, 2015 |
Journal | Information Sciences |
Print ISSN | 0020-0255 |
Electronic ISSN | 1872-6291 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 233 |
DOI | https://doi.org/10.1016/j.ins.2013.01.014 |
Keywords | multicast, multiobjective optimization, network coding, Elitist nondominated sorting genetic algorithm (NSGA-II) |
Public URL | https://nottingham-repository.worktribe.com/output/714771 |
Publisher URL | http://www.sciencedirect.com/science/article/pii/S0020025513000716 |
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
You might also like
A pattern-based algorithm with fuzzy logic bin selector for online bin packing problem
(2024)
Journal Article
Self-Bidirectional Decoupled Distillation for Time Series Classification
(2024)
Journal Article
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search