Research On Network Coding Resource Minimization Problem Based On Ant Colony Optimization Algorithm

With repaid developments of information technique, recent years witness a significant growth in multimedia applications. Multicast is a one-to-many communications technology with multiple receivers simultaneously requesting the same information sent from a single source. This technology can well support multimedia applications with multiple end users involved. However, multicast employing store-and-forward forwarding cannot guarantee the theoretically maximized throughput. Fortunately, network coding that is proposed in 2000, can always help the multicast achieve the theoretical maximum throughput.In the original studies, in order to achieve the theoretical maximum throughput of multicast, it was assumed that coding operations have to be performed at all coding-possible nodes. However, only a subset of coding-possible nodes suffices to realize network coding-based multicast (NCM) with an expected data rate. As network coding involves complicated mathematical operations, performing coding operations will consume significant computational and buffering resources in the corresponding nodes. The less the coding operations, the less computational and buffering costs, which is the network coding resource minimization (NCRM) problem. Nowadays, Evolutionary Algorithms (EAs) are the mainstream solutions for NCRM problem. While ant colony optimizations (ACOs) have been intensively investigated and successfully applied to a vast number of optimization problems. However, to the best of our knowledge, there has not been any research conducted about applying ACO for the NCRM problem.The paper presents a modified ant colony optimization approach for the network coding resource minimization problem. It is featured with several attractive mechanisms specially devised for solving the concerned problem:1) a multidimensional pheromone maintenance mechanism is put forward to address the issue of pheromone overlapping; 2) problem specific heuristic information is employed to enhance the capability of heuristic search (neighboring area search); 3) a tabu-table based path construction method is devised to facilitate the construction of feasible (link-disjoint) paths from the source to each receiver; 4) a local pheromone updating rule is developed to guide ants to construct appropriate promising paths; 5) a solution reconstruction method is presented, with the aim of avoiding prematurity and improving the global search efficiency of proposed algorithm. Due to the way it works, the ant colony optimization can well exploit the global and local information of routing related problems during the solution construction phase. The simulation results on benchmark instances demonstrate that with the integrated five extended mechanisms, our algorithm outperforms a number of existing algorithms with respect to the best solutions obtained and the computational time.