Convolutional Network Coding And Its Related Construction Algorithms

Network coding opens a new paradigm in data transport.The main idea is that it permits the nodes of network performing some encoding operations.Thus,the outgoing of every node in a network is a function of its incoming information.Comparing with the conventional store-and-forward routing mode,network codes have been shown to have more advantages in improving the throughput gains,the network load-balancing,the transmission rate of the wireless network,the network robustness and its universality,the safety and stability of the network and so on.Major work about network coding focused on acyclic networks.However,most practical networks are cyclic due to the bidirectional or multi-party communications.Over an acyclic network there exists an upstream-to-downstream order on the nodes,but for a cyclic network,such an order does not exist.This makes network coding over a cyclic network essentially different from that over an acyclic network.The convolutional network code(CNC)can be employed to deal with the propagation of a message pipeline through a cyclic network.Thus,in this paper,we focus on studying the characteristics and the related construction algorithms of convolutional network codes over the cycle network.All results and construction algorithms are also appropriate for the acyclic networks.The main results are shown as follows:1.The correspondence relationship between the weighted line graph of the original communication network and the Mason signal flow graph(MSFG)for the associated network has been established,which gives an interpretation of a convolutional network code(CNC)over a cyclic network from a different perspective.2.By virtue of Mason theorem,we present two new equivalent conditions to evaluate whether the global encoding kernels(GEKs)can be uniquely determined by the given complete set of local encoding kernels(LEKs)in a CNC over a cyclic network.Meanwhile,an alternative new method based on Mason formula is proposed to computing the GEKs.Based on the new equivalent conditions,we only need to concern the LEKs around the cycles in the original network but not the whole ones assigned to the network.Therefore,if we know the entire network topology information(including the pattern of interconnections of all cycles),it,is often efficient to use the graph-theoretic technique rather than matrix method.3.Inspired by the convolutional multicast(CM)construction method proposed by Erez and Feder,we present an efficient construction algorithm for basic convolutional network coding(BCNC)over cyclic networks.Our construction can give the maximal required cardinality of the encoding coefficients,which provides a definite domain for picking local encoding kernels(LEKs).And if we add some non-source nodes and associated edges in an existing code,our algorithm can modify the already assigned LEKs in an efficient localized manner in its expanding network.4.We present a direct construction algorithm for the delay invariant convolutional network coding(DI-F-CNC)over a cyclic network,some associated theoretical guarantees for algorithm implementation are also proposed.5.We introiduce a special vector called the linear independence detection vector in the main program of DI-F-CNC construction algorithm.And we obtain a faster construction algorithm of DI-F-CNC.The complexity analysis results show that the directly algorithm has the same size of coefficients domain and the same computational complexity with the indirect method proposed in[119].Moreover,when some non-source nodes and associated edges are added in an existing code,constructing DI-F-CNC on the expanding network corresponds to adding some new for-loop steps in our direct algorithm,and those already determined LEKs can not be reassigned.Thus,the direct algorithm possesses a good scalability.