On minimizing coding operations in network coding based multicast: an evolutionary algorithm
In telecommunications networks, to enable a valid data transmission based on network coding, any intermediate node within a given network is allowed, if necessary, to perform coding operations. The more coding operations needed, the more coding resources consumed and thus the more computational over...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Springer US
2014
|
| Online Access: | https://eprints.nottingham.ac.uk/28277/ |
| _version_ | 1848793541077106688 |
|---|---|
| author | Xing, Huanlai Qu, Rong Bai, Lin Ji, Yuefeng |
| author_facet | Xing, Huanlai Qu, Rong Bai, Lin Ji, Yuefeng |
| author_sort | Xing, Huanlai |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | In telecommunications networks, to enable a valid data transmission based on network coding, any intermediate node within a given network is allowed, if necessary, to perform coding operations. The more coding operations needed, the more coding resources consumed and thus the more computational overhead and transmission delay incurred. This paper investigates an efficient evolutionary algorithm to minimize the amount of coding operations required in network coding based multicast. Based on genetic algorithms, we adapt two extensions in the proposed evolutionary algorithm, namely a new crossover operator and a neighbourhood search operator, to effectively solve the highly complex problem being concerned. The new crossover is based on logic OR operations to each pair of selected parent individuals, and the resulting offspring are more likely to become feasible. The aim of this operator is to intensify the search in regions with plenty of feasible individuals. The neighbourhood search consists of two moves which are based on greedy link removal and path reconstruction, respectively. Due to the specific problem feature, it is possible that each feasible individual corresponds to a number of, rather than a single, valid network coding based routing subgraphs. The neighbourhood search is applied to each feasible individual to find a better routing subgraph that consumes less coding resource. This operator not only improves solution quality but also accelerates the convergence. Experiments have been carried out on a number of fixed and randomly generated benchmark networks. The results demonstrate that with the two extensions, our evolutionary algorithm is effective and outperforms a number of state-of-the-art algorithms in terms of the ability of finding optimal solutions. |
| first_indexed | 2025-11-14T19:01:56Z |
| format | Article |
| id | nottingham-28277 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:01:56Z |
| publishDate | 2014 |
| publisher | Springer US |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-282772020-05-04T20:13:18Z https://eprints.nottingham.ac.uk/28277/ On minimizing coding operations in network coding based multicast: an evolutionary algorithm Xing, Huanlai Qu, Rong Bai, Lin Ji, Yuefeng In telecommunications networks, to enable a valid data transmission based on network coding, any intermediate node within a given network is allowed, if necessary, to perform coding operations. The more coding operations needed, the more coding resources consumed and thus the more computational overhead and transmission delay incurred. This paper investigates an efficient evolutionary algorithm to minimize the amount of coding operations required in network coding based multicast. Based on genetic algorithms, we adapt two extensions in the proposed evolutionary algorithm, namely a new crossover operator and a neighbourhood search operator, to effectively solve the highly complex problem being concerned. The new crossover is based on logic OR operations to each pair of selected parent individuals, and the resulting offspring are more likely to become feasible. The aim of this operator is to intensify the search in regions with plenty of feasible individuals. The neighbourhood search consists of two moves which are based on greedy link removal and path reconstruction, respectively. Due to the specific problem feature, it is possible that each feasible individual corresponds to a number of, rather than a single, valid network coding based routing subgraphs. The neighbourhood search is applied to each feasible individual to find a better routing subgraph that consumes less coding resource. This operator not only improves solution quality but also accelerates the convergence. Experiments have been carried out on a number of fixed and randomly generated benchmark networks. The results demonstrate that with the two extensions, our evolutionary algorithm is effective and outperforms a number of state-of-the-art algorithms in terms of the ability of finding optimal solutions. Springer US 2014-10 Article PeerReviewed Xing, Huanlai, Qu, Rong, Bai, Lin and Ji, Yuefeng (2014) On minimizing coding operations in network coding based multicast: an evolutionary algorithm. Applied Intelligence, 41 (3). pp. 820-836. ISSN 0924-669X http://link.springer.com/article/10.1007%2Fs10489-014-0559-4 doi:10.1007/s10489-014-0559-4 doi:10.1007/s10489-014-0559-4 |
| spellingShingle | Xing, Huanlai Qu, Rong Bai, Lin Ji, Yuefeng On minimizing coding operations in network coding based multicast: an evolutionary algorithm |
| title | On minimizing coding operations in network coding based multicast: an evolutionary algorithm |
| title_full | On minimizing coding operations in network coding based multicast: an evolutionary algorithm |
| title_fullStr | On minimizing coding operations in network coding based multicast: an evolutionary algorithm |
| title_full_unstemmed | On minimizing coding operations in network coding based multicast: an evolutionary algorithm |
| title_short | On minimizing coding operations in network coding based multicast: an evolutionary algorithm |
| title_sort | on minimizing coding operations in network coding based multicast: an evolutionary algorithm |
| url | https://eprints.nottingham.ac.uk/28277/ https://eprints.nottingham.ac.uk/28277/ https://eprints.nottingham.ac.uk/28277/ |