Evolutionary Approaches for Network Coding Based Multicast Routing Problems


Network coding is an emerging technique in communication networks, where the intermediate nodes are allowed to combine (code) the data received from different incoming links if necessary. The thesis investigates a number of routing problems for network coding based multicast (NCM), which belong to combinatorial optimization problems (COPs). Evolutionary algorithms (EAs) are used to tackle the problems. The contributions of the thesis are described below. We propose three EAs for the network coding resource minimization (NCRM) problem where the objective is to minimize the number of coding operations performed while meeting the data rate requirement based on NCM. The three EAs are population based incremental learning (PBIL), compact genetic algorithm (cGA) and path-oriented encoding EA (pEA), all specially developed for tackling the NCRM problem. PBIL adopts the binary link state (BLS) encoding which is an existing encoding approach. We find that PBIL is more suited to BLS encoding, compared with genetic algorithms (GAs). This is because the principle of updating the probability vector (PV) in PBIL can easily locate promising regions in the search space. An entropy-based restart scheme is developed, which can improve the global exploration ability of PBIL. cGA is also based on BLS encoding and fit for this encoding. Three improvement schemes are developed based on the features of the encoding and the structure of cGA, including all-one vector, a PV restart scheme and a problem specific local search operator. In particular, the local search operator is the very first domain-knowledge based operator for the problem concerned. We notice that BLS encoding and its variant have some weaknesses, namely high proportion of infeasible solutions in the search space and high computational costs spent on fitness evaluation. We therefore design a path-oriented encoding and develop pEA based on it, where a local search operator (based on the path-oriented encoding) is incorporated into the evolutionary framework to improve the local exploitation ability. Experimental results demonstrate that the three adapted EAs outperform existing EAs in the literature, in terms of the best results obtained and computational time. To support real-time multimedia applications, we for the first time extend the NCRM problem by introducing the maximum transmission delay into the problem as a constraint, which is called the delay constrained NCRM problem. Benchmark datasets are created based on the datasets for the NCRM problem. Three EAs originally used for the NCRM problem are adapted for the delay constrained NCRM problem, including GAs and PBIL. We find that for the same dataset a severer delay constraint leads to a harder problem. We also find that the restart scheme in PBIL is not suited to the delay constrained NCRM problem, due to the setting of threshold value and the memory-less structure. We therefore design a substitute for the restart scheme to adapt PBIL for the delay constrained problem, namely the combination of a new PV update scheme and a PV mutation. It is noted that the PV update scheme is based on a set of historically best solutions. The combination improves the global exploration of PBIL and avoids local optima. PBIL with the new PV update scheme and PV mutation performs better than PBIL with restart scheme. To study the conflicting interests of service providers and network users, we for the first time formulate a multi-objective NCM routing problem considering two objectives, cost and delay. The cost is the summation of the coding cost and link cost incurred in the NCM. The delay is the maximum transmission delay of paths in the NCM. This problem is referred to as the cost-delay bi-objective optimization (CDBO) problem. Benchmark datasets for the delay constrained NCRM problem are used to generate the datasets for the CDBO problem. Elitist nondominated sorting GA (NSGA-II) is adapted for the CDBO problem, where two problem specific schemes are proposed, namely an initialization scheme and an individual delegate scheme (IDS). The initialization scheme can generate a set of promising and diversified initial individuals, which initiates a diversified search at the beginning of the evolution. The IDS reduces the number of individuals having identical objective values in the population and leaves more space to accept other significant individuals. This scheme considers the crowding in both decision and objective spaces and helps to diversify the search during the evolution. The adapted NSGA-II performs better than a number of multi-objective EAs in terms of the inverted generational distance, generational distance and maximum spread.