Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding Resources
The minimization of network coding resources, such as coding nodes and links, is a challenging task, not only because it is a NP-hard problem, but also because the problem scale is huge; for example, networks in real world may have thousands or even millions of nodes and links. Genetic algorithms (G...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/268152 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832548143964618752 |
|---|---|
| author | Xiao-Bing Hu Mark S. Leeson |
| author_facet | Xiao-Bing Hu Mark S. Leeson |
| author_sort | Xiao-Bing Hu |
| collection | DOAJ |
| description | The minimization of network coding resources, such as coding nodes and links, is a challenging task, not only because it is a NP-hard problem, but also because the problem scale is huge; for example, networks in real world may have thousands or even millions of nodes and links. Genetic algorithms (GAs) have a good potential of resolving NP-hard problems like the network coding problem (NCP), but as a population-based algorithm, serious scalability and applicability problems are often confronted when GAs are applied to large- or huge-scale systems. Inspired by the temporal receding horizon control in control engineering, this paper proposes a novel spatial receding horizon control (SRHC) strategy as a network partitioning technology, and then designs an efficient GA to tackle the NCP. Traditional network partitioning methods can be viewed as a special case of the proposed SRHC, that is, one-step-wide SRHC, whilst the method in this paper is a generalized N-step-wide SRHC, which can make a better use of global information of network topologies. Besides the SRHC strategy, some useful designs are also reported in this paper. The advantages of the proposed SRHC and GA for the NCP are illustrated by extensive experiments, and they have a good potential of being extended to other large-scale complex problems. |
| format | Article |
| id | doaj-art-b0011b8013274ea090af0ca8ba04ece6 |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-b0011b8013274ea090af0ca8ba04ece62025-02-03T06:42:04ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/268152268152Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding ResourcesXiao-Bing Hu0Mark S. Leeson1State Key Laboratory of Earth Surface Processes and Resource Ecology, Beijing Normal University, Beijing 100875, ChinaSchool of Engineering, University of Warwick, Coventry CV4 7AL, UKThe minimization of network coding resources, such as coding nodes and links, is a challenging task, not only because it is a NP-hard problem, but also because the problem scale is huge; for example, networks in real world may have thousands or even millions of nodes and links. Genetic algorithms (GAs) have a good potential of resolving NP-hard problems like the network coding problem (NCP), but as a population-based algorithm, serious scalability and applicability problems are often confronted when GAs are applied to large- or huge-scale systems. Inspired by the temporal receding horizon control in control engineering, this paper proposes a novel spatial receding horizon control (SRHC) strategy as a network partitioning technology, and then designs an efficient GA to tackle the NCP. Traditional network partitioning methods can be viewed as a special case of the proposed SRHC, that is, one-step-wide SRHC, whilst the method in this paper is a generalized N-step-wide SRHC, which can make a better use of global information of network topologies. Besides the SRHC strategy, some useful designs are also reported in this paper. The advantages of the proposed SRHC and GA for the NCP are illustrated by extensive experiments, and they have a good potential of being extended to other large-scale complex problems.http://dx.doi.org/10.1155/2014/268152 |
| spellingShingle | Xiao-Bing Hu Mark S. Leeson Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding Resources The Scientific World Journal |
| title | Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding Resources |
| title_full | Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding Resources |
| title_fullStr | Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding Resources |
| title_full_unstemmed | Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding Resources |
| title_short | Evolutionary Computation with Spatial Receding Horizon Control to Minimize Network Coding Resources |
| title_sort | evolutionary computation with spatial receding horizon control to minimize network coding resources |
| url | http://dx.doi.org/10.1155/2014/268152 |
| work_keys_str_mv | AT xiaobinghu evolutionarycomputationwithspatialrecedinghorizoncontroltominimizenetworkcodingresources AT marksleeson evolutionarycomputationwithspatialrecedinghorizoncontroltominimizenetworkcodingresources |