The Library
An effective genetic algorithm for network coding
Tools
Hu, Xiao-Bing, Leeson, Mark S. and Hines, Evor (2012) An effective genetic algorithm for network coding. Computers & Operations Research, Vol.39 (No.5). pp. 952-963. doi:10.1016/j.cor.2011.07.014 ISSN 0305-0548.
|
PDF
WRAP_Leeson_9976551-es-010911-ga4nc3rdresubmission-msl.pdf - Accepted Version - Requires a PDF viewer. 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 and Medicine > Engineering > 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 | ||||
Official Date: | May 2012 | ||||
Dates: |
|
||||
Volume: | Vol.39 | ||||
Number: | No.5 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 952-963 | ||||
DOI: | 10.1016/j.cor.2011.07.014 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 17 December 2015 | ||||
Date of first compliant Open Access: | 17 December 2015 | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||
Grant number: | EP/F033591/1 (EPSRC) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year