Abstract

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.