مرتب سازی بدون تسلط الگوریتم ژنتیک برای برنامه نویسی شبکه های دو هدفه مبتنی بر مسائل مسیریابی چندپخشی

Network coding is a new communication technique that generalizes routing, where, instead of simply forwarding the packets they receive, intermediate nodes are allowed to recombine (code) together some of the data packets received from different incoming links if necessary. By doing so, the maximum information flow in a network can always be achieved. However, performing coding operations (i.e. recombining data packets) incur computational overhead and delay of data processing at the corresponding nodes. In this paper, we investigate the optimization of the network coding based multicast routing problem with respect to two widely considered objectives, i.e. the cost and the delay. In general, reducing cost can result into a cheaper multicast solution for network service providers, while decreasing delay improves the service quality for users. Hence we model the problem as a bi-objective optimization problem to minimize the total cost and the maximum transmission delay of a multicast. This bi-objective optimization problem has not been considered in the literature. We adapt the Elitist Nondominated Sorting Genetic Algorithm (NSGA-II) for the new problem by introducing two adjustments. As there are many infeasible solutions in the search space, the first adjustment is an initialization scheme to generate a population of feasible and diversified solutions. These initial solutions help to guide the search towards the Pareto-optimal front. In addition, the original NSGA-II is very likely to produce a number of solutions with identical objective values at each generation, which may seriously deteriorate the level of diversity and the optimization performance. The second adjustment is an individual delegate scheme where, among those solutions with identical objective values, only one of them is retained in the population while the others are deleted. Experimental results reveal that each adopted adjustment contributes to the adaptation of NSGA-II for the problem concerned. Moreover, the adjusted NSGA-II outperforms a number of state-of-the-art multiobjective evolutionary algorithms with respect to the quality of the obtained nondominated solutions in the conducted experiments.

Multicast is a one-to-many communication technique that simultaneously delivers information from the source to a group of destinations (receivers) within the same network so that in a single transmission any receiver is able to obtain the original information sent from the source [38]. With the emergence of increasingly more multimedia applications such as video conferencing and IPTV, multicast has become one of the key supporting technologies in modern communication networks [4], [17], [18] and [44]. Network coding is a new technique that generalizes routing in communication networks [1]. Since its introduction in 2000, network coding has drawn a significant amount of research attention in information and coding theory, networking, cryptography, and so on. In traditional routing, each intermediate node (i.e. router) within a network simply forwards the data received from an incoming link to one or a number of outgoing links. However, in network coding based routing, any intermediate node can recombine (code) data received from different incoming links if necessary. Network coding has promising advantages in payload balancing [14], [30] and [34], energy saving [7] and [45], security [5], robustness against failures [21], and so on. When incorporating network coding into multicast, the most attractive advantage is that (according to the MAX-FLOW MIN-CUT Theorem) the theoretical maximal throughput is always guaranteed [34]. Fig. 1 shows a comparison between network coding and traditional routing regarding the average data rate to receivers [46]. Fig. 1a is a network, where source s multicasts two-bit information (a) and (b) to node y and node z. Each link can forward a single bit at each time. According to the MAX-FLOW MIN-CUT Theorem, the theoretical maximal multicast throughput is two bits per time. However, as Fig. 1b illustrates, traditional routing can only obtain an average data rate of 1.5 bits per time unit due to the bottleneck link w → x. As can be seen in Fig. 1c, if we allow node w to perform a ⊕ b (⊕ stands for Exclusive-OR), both of the receivers obtain two-bit information at the same time, where original data can be decoded through a ⊕ (a ⊕ b) and b ⊕ (a ⊕ b). Hence, network coding can always achieve the theoretical maximal multicast throughput.

This paper investigates the bi-objective network coding based multicast routing problem, where the two objectives, the total cost and the maximum transmission delay, are minimized simultaneously. We adapt Elitist Nondominated Sorting Genetic Algorithm (NSGA-II) for the above problem by introducing two adjustments, namely the initialization scheme and the individual delegate scheme. The two adjustments both aim to diversify the population thus contribute to an effective evolution towards the Pareto Front. The simulation results show that the adjusted NSGA-II performs significantly better than a number of existing multiobjective evolutionary algorithms in terms of several popular performance measures, i.e. inverted generational distance, generational distance and maximum spread. As aforementioned, the bi-objective optimization problem in this paper is a highly challenging. Several widely-recognized multiobjective evolutionary algorithms, such as NSGA-II and SPEA2, when directly applied to the problem, fail to obtain decent solutions in our experiments. In the future, we will extend our investigation by developing local-search operators in NSGA-II that make use of the domain knowledge in the highly constrained problem to enhance the local exploitation of the algorithm. In addition, the problem concerned in the paper is a static optimization problem where the landscape of the problem is fixed during the evolution. As the status of links and nodes of a network may change over time, it is more practical to consider a dynamic network environment, e.g. receivers join and leave a multicast session dynamically. Therefore, based on our current research we will further study the network coding based multicast in dynamic environments. After that, we plan to setup a real communication network platform and evaluate the performance of the proposed schemes in real world applications.