کدینگ شبکه (NC) با الگوریتم ژنتیک (GA) موثر

ABSTRACT An effective genetic algorithm for network coding

The notion of coding at the packet level –commonly called network coding –has attracted significant interest since the publication of [1], which showed its utility for multicast in wireline packet networks. It is now established that network coding may significantly improve network performance in terms of network throughput. It should be noted that conventional network optimization aims to maximize information flow by utilizing as much link capacity as possible, whilst network coding begins with the assumption that full link capacity utilization has already been achieved wherever possible and then attempts to further increase the network throughput at sinks by performing coding at nodes.

This advantage of network coding can be understood in the context of the example shown in Fig. 1.(a) and (b). It is assumed in Fig. 1 that two different pieces of one-unit-sized data/packets, a and b, are to be sent from the source node 1 to the sink node 6 and 7, and the capacity of every link is just 1 (in this paper, the link capacity is defined as the same as the one in conventional network optimization [1], all data are one-unit-sized, and all links are of unit-capacity). The aim is to maximize the rate achieved at each sink, i.e., the amount of different data received by a sink at one time. The rate is also measured in data units. Since all links are of unit-capacity, the potential maximal achievable rate at a sink is equivalent to the number of its incoming links. However, different links may carry the same data, such as the two incoming links of node 7 in Fig. 1.(a) and so the actually achieved rate at a sink may be less than the potential rate. This is likely to be the case if the nodes in the network only forward and replicate the data they receive. For example, as illustrated in Fig. 1(a), the sink node 7 can only receive 1 unit of data β at one time, although the other sink node 6 achieves a rate of 2 by receiving both α and β. The information flow in Fig. 1(a) is optimal from the conventional point of view because every link carries one unit of data, which gives a full utilization of the link capacity. However, if node 4 can combine data from its two incoming links through the ‘‘þ’’ operation, then by using the ‘‘–’’ operation to decode data, a rate of 2 can be achieved at both sinks, as shown in Fig. 1.(b). It should be noted that the result of operation ‘‘þ’’, e.g., α+β in Fig. 1.(b), is still an one-unit-sized data element. Therefore, without exceeding the link capacity, network coding increases the total rate of information flow through the same network from 3 to 4 in Fig. 1, a significant improvement.

Although network coding may be allowed at all nodes in some of the relevant literature, an interesting observation is that a given target rate can often be achieved by conducting network coding at only a relatively small proportion of the nodes [2]. For instance, in the network given by Fig. 1(c), network coding at both nodes 4 and 5 will make no difference in terms of the rate achieved at the sinks or in other word, network coding is not necessary in that network. Therefore, a question is raised: at which nodes does network coding need to be conducted, or how does one make most of network capacity at a minimal cost in terms of network coding resources? To answer this question, a minimal set of nodes needs to be found for coding, and this has been proved to be an NP-hard problem [3]. In this paper, the above problem of minimizing network coding resources is referred to as the Network Coding Problem (NCP). Some attempts have already been made using different methods to address this problem. For instance, two minimal approaches were reported in [4,5] which ascertain the minimal set of nodes for network coding in order to achieve a given target rate. It was determined in [4] that coding is required at no more than d-1 nodes in acyclic networks with 2 unit-rate sources and d sinks. An upper bound on the number of nodes required for both acyclic and cyclic networks was derived in [5]. However, the approaches in both [4,5] determine the minimal set of nodes for coding by removing links in a greedy fashion. A linear programming method was reported in [6] to optimize the various resources used for network coding, and its optimal formulations involved a number of variables and constraints that grow exponentially with the number of sinks.

As large-scale parallel stochastic search and optimization algorithms, genetic algorithms (GAs) have a good provenance in the resolution of diverse NP-hard problems [7,8], including network optimization and resource assignment [9,10]. However, the optimization of network coding is a relatively new area for GAs, and very few results have been reported [2,11–13] to date. The first attempt to apply GAs to network coding was made by Kim et al. [2]. This was then extended from acyclic networks to cyclic networks and from centralized cases to decentralized cases [11]. The genetic representation was the particular focus in later work [12], followed by the proposal of a distributed algorithm to improve GA computational efficiency [13].

There is a common assumption in the network coding optimization work to date that the target rate is always achievable if coding is allowed at all nodes, permitting attention to be focused on the minimization of the number of coding links/nodes. However, in dynamic environments, such as wireless networks, it is quite possible that the target rate may become unachievable due to uncertainty in the connections between the nodes [14]. If this is the case, it is the rate that is actually achieved rather than the target rate that plays a more important role in network coding. The previous studies using the assumption that the target rate was achievable, such as [2,4–13], did not consider the rate actually achieved when minimizing resources, and were therefore largely limited to the static NCP (SNCP). They may only be applied to the dynamic NCP (DNCP) by calculating the target rate and then reoptimizing resources every time a change occurs in the network topology.

Network coding in dynamic environments is a challenging research topic. Random network coding has proved to be very promising in coping with network topology changes, as it does not require the knowledge of the entire network topology [15–19].

However, in these random network coding studies the minimization of coding resources is not a concern and each node has to communicate its coding weights throughout the network, which means that not all of the network capacity will be available to transmit the signals sent by the source. Therefore, whilst the advantages of random network coding should be acknowledged, it is still necessary to investigate how to improve network coding based on the entire network topology. Robustness against changes in network topology will be a particular concern. As will be explained in Section 3, the DNCP model proposed in this paper exhibits such robustness to some extent when compared with previous work [2,11].

In our previous study [20], preliminary results relating to the design of effective GAs for the minimization of coding resources in the NCP, particularly in the DNCP, were reported but the work was restricted to the NCP utilizing only the simplest addition coding (i.e., the field size is 2) between two incoming signals. The work presented in this paper is concerned with further developments of our previous results by extending our work to NCP where coding with any finite field size is adopted to combine any finite number of incoming signals.