网络编码中的优化问题研究

简要回顾了网络编码的理论研究,阐述了网络编码优化问题研究的重要意义.在介绍网络信息流模型的基础上,针对优化问题的陈述、特点和解法,结合最新的研究成果进行了综述.根据优化目标的不同,优化问题可分成4类:最小花费组播,无向网络的最大吞吐率,最小编码节点、编码边,基于网络编码的网络拓扑设计.归纳了问题的求解性质,对其中的(线性或凸)规划问题总结了求解的一般方法,对NP完全问题讨论了最新的启发式算法及其设计难点.同时,展望了未来的发展方向.

Research on the Optimization Problems in Network Coding

This paper briefly reviews the theoretical researches on network coding, from which the significance of research on optimization problems is revealed. Based on the network information flow model, it makes a survey on the formulation, characteristics and algorithms of optimization problems with the latest results. According to the goal of optimization, the typical optimization problems in network coding are classified into four categories: minimum-cost multicast, throughput maximization in undirected networks, minimum number of coding nodes and links, topology design of network coding-based multicast networks. The general approaches to deal with these problems are categorized. For (linear or convex) programming problems, the solutions are summarized; for NP complete problems, the latest heuristic algorithms and their difficulties are analyzed. The perspectives on future work are also discussed.