Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Xing, Huanlai; Qu, Rong; Bai, Lin; Ji, Yuefeng (2014)
Publisher: Springer US
Languages: English
Types: Article
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] Miller CK (1998) Multicast networking and applications. Pearson Education.
    • [2] Xu Y, Qu R (2012) A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems. APPL INTELL 36: 229-241.
    • [3] Jahanshahi M, Dehghan M, Meybodi MR (2013) LAMR: learning automata based multicast routing protocol for multi-channel multi-radio wireless mesh networks. APPL INTELL 38: 58-77.
    • [4] Ahlswede R, Cai N, Li SYR and Yeung RW (2000) Network information flow. IEEE T INFORM THEORY 46(4):1204-1216.
    • [5] Li SYR, Yeung RW, and Cai N (2003) Linear network coding. IEEE T INFORM THEORY 49(2):371-381.
    • [6] Noguchi T, Matsuda T, Yamamoto M (2003) Performance evaluation of new multicast architecture with network coding. IEICE T COMMUN E86-B: 1788-1795.
    • [7] Wu Y, Chou PA, and Kung SY (2005) Minimum-energy multicast in mobile ad hoc networks using network coding. IEEE T COMMUN 53(11): 1906-1918.
    • [8] Fragouli C, Boudec JYL, Widmer J (2006) Network coding: an instant primer. COMPUT COMMUN REV 36: 63-68.
    • [9] Kim M, Ahn CW, Médard M, and Effros M (2006) On minimizing network coding resources: An evolutionary approach. In: Proceedings of Second Workshop on Network Coding, Theory, and Applications (NetCod2006), Boston.
    • [10] Kim M, Médard M, Aggarwal V, Reilly VO, Kim W, Ahn CW, and Effros M (2007) Evolutionary approaches to minimizing network coding resources. In: Proceedings of 26th IEEE International Conference on Computer Communications (INFOCOM2007), Anchorage, pp 1991-1999.
    • [11] Kim M, Aggarwal V, Reilly VO, Médard M, and Kim W (2007) Genetic representations for evolutionary optimization of network coding. In: Proceedings of EvoWorkshops 2007, LNCS 4448, Valencia, pp 21-31.
    • [12] Mitchell M (1996) An introduction to genetic algorithms. MIT Press.
    • [13] Krasnogor N, Smith JE (2005) A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE T EVOLUT COMPUT: 474-488.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article