Study On Optimization Problems In Network Coding

Network Coding,namely,Network Information Flow(NIF),is an important breakthrough in the coding fields,Network Coding belongs to an important branch of network information theory.The basic idea is that the network node participates in encoding and decoding,which is essentially different from the classical source coding and channel coding.Network throughput and network performance can be effectively and significantly improved when network nodes are allowed to participate in encoding and decoding.These advantages have broad application prospects in the planning and optimization of wired and wireless networks,the establishment of wireless and satellite networks,and the planning and optimization of ubiquitous networks.The establishment of a model is the theoretical basis of pushing network coding to application as soon as possible;the network coding technology can be analyzed qualitatively and quantitatively is the key for the implementation of this technology;and finding a simple and feasible algorithm is a necessary way for the practical implementation of it.This dissertation begins with studying on the developments of the network coding technology.It selects cyclic network coding and wireless space information flow as the research objects,it focuses on following three aspects:Firstly,information flows inevitably intersect to form loops in the actual network.The loop formed by the information flow may cause the wrong causality of the link and the disorder of time sequential relations.To solve this problem,the effect of time delay must be considered.Under such circumstances,network coding in cyclic network presents different characteristics from that in acyclic network.These characteristics make the research on cyclic network coding more practical.On the premise of giving the mathematical theoretical framework and its transmission characteristics of cyclic network coding,a variable rate convolution broadcast network coding algorithm is proposed.Examples are given to illustrate the effectiveness of the algorithm,time and space complexity is analyzed.The algorithem develops the network coding theory.Secondly,a Space Information Flow(SIF)model is applied in wireless network with fixed terminals in Euclidean space.It can be allowed to add additional nodes and coded at the nodes.The key problem is whether the model can obtain an optimal cost while satisfying communication requirements on end-to-end unicast or multicast among different terminals at known coordinates without any consideration of inter-session network coding.By analyzing the properties of the model,an algorithm is designed to solve the near-optimal cost SIF problem.For non-convex objective functions,the nonlinear programming method can be used to give the local near-optimal solution,and at the same time,a multi-parameter joint optimization scheme is given,which includes routing,resource block allocation and the specific coordinates of relay nodes in space.It explains how to implement the algorithm in detail.Because of the high computational complexity,it must be reduced by reducing the dimension of variables.By reducing and restoring a series of variables,normalizing the constraint conditions,taking the first derivative of the objective function to smooth,etc.,the effective operation of the algorithm is realized.Finally,the results of space information flow near optimization algorithm and relay nodes optimization are illustrated by simulations.Thirdly,a nonlinear programming problem with linear constraints is modeled with inter-session and intra-session coding for more general situations in wireless network.A filling function method for solving the global near-optimal solution of non-convex problems is found and firstly used in information theory.A proof has been given how the filling function can find the global near-optimal.The filling function method is an excellent solution for the minimum network cost problem,it derives the optiamal solutions with resource block allocation schemes and locations of relay nodes.By means of numerical analysis,the communication examples in unicast and multicast are compared,and the complexity of the algorithm is analyzed.This dissertation provides some basic theory for the Network Coding in cyclic network,wireless network,satellite network and ubiquitous network,and would promote the feasibility of the practical applications for this network coding technology.