Convolutional Network Coding And Its Applications

Reliability and efficiency are two keys in modern communication systems.Network Coding is a new capacity achieving technique, where intermediate nodes areallowed to do linear or nonlinear process of the incoming information and forward. Ithas been proved to have incomparable advantages in throughput, data security,robustness, universality, load equalization and low computational complexity and so on.Meanwhile, random linear network coding (RLNC) operates simply and adapts tounknown or changing topology, which leads to possible realization. So far, networkcoding has been one of the hottest topics in Telecommunications.In practice, due to the delay and cycles existing in networks, the messages fromdifferent times convolve together, which naturally causes convolutional network coding(CNC). The present studies on CNC are based on the whole system，and the sinks needto get all the global encoding kernels (GEKs) to decode the source messages. However,the GEKs are transmitted to sinks together mixed with messages. Therefore, it is notreasonable for a sink node waiting for receiving all the GEKs to recover the sourcemessages since large delays and high complexity are raised by the long length ofencoding kernels, infinite special for the case of cycles. To solve this problem, matrixpower series presentation is proposed to reanalyze CNC from the perspective of timesequence in this dissertation, which brings some valuable results on encoding anddecoding of CNC. Furthermore, an adaptive randomized CNC algorithm is proposed toreduce the delay and memory use.The main contributions are listed as follows.1. The determinant of transmission matrix should be non-zero to ensure the codesuccessful. However, it is always difficult to check as the encoding field size issufficiently large. Matrix power series representation is proposed to reformulate CNCand establish its theoretical fundamentals for practical implementations. Deduce that aCNC can be determined only by a nilpotent coefficient matrix of local encoding kernels(LEKs) at time0, which simplifies the CNC design.2. It is not reasonable for sinks to collect all GEKs to decode the source messagesover cyclic networks, especially for random coding approach. Inspired by the theory offinite inverse circuit, a time-variant decoding model of a CNC is proposed. Newnecessary and sufficient conditions are established for the decidability of CNC at a sinknode with certain delay. They only involve the first several terms in the power series expansion of the GEK matrix. This model only deals with partial information of GEKs,and hence potentially makes CNCs applicable in a decentralized manner. This approachreduces the decoding delay and lowers the complexity.3. For cyclic networks, polynomial fraction GEKs with non-zero denominator arepossible, and therefore the sequence decoder proposed by Erez et al. is no longerfeasible. We generalize this decoder and give the minimum decoding delay, whichequals to the difference between the minimum degree of the determinant of GEK matrixafter processing without denominators and the maximum degree of greatest commondivisor (GCD) of adjoint matrix of GEK matrix.4. An adaptive random convolutional network coding (ARCNC) is proposed toaddress the issue of field size in RLNC for multicast, and its decoding delayperformance through both analysis and numerical simulations. ARCNC operates as aconvolutional code, with the coefficients of LEKs chosen randomly over a small finitefield. The cardinality of LEKs increases with time until the GEKs matrices at relatedsink nodes have full rank. It adapts to unknown network topologies without priorknowledge, and has reductions in decoding delay and memory overheads. We showthrough theoretic analysis and simulations that this method performs as well as RLNCin terms of decodability, and can provide significant gains in terms of average decodingdelay or memory in Combination, Umbrella, Shuttle and random geometric networks.5. Wireless network is one hot topic in communication system, and it would beworth it to study the applications of network coding over wireless networks. Differentfrom wired networks, wireless networks have the features of broadcast, noise,interference and half-duplex and so on. To characterize the algebraic structure ofwireless network coding, a hypergragh is utilized to model wireless packet networksfrom the perspective of network layer. The algebraic description of random CNC overwireless packet networks is deduced, and the condition on coding success is alsopresented. It is shown through analysis and simulations that random CNC is capacityachieving with probability approaching1. This work provides the theoretic foundationfor wireless packet network coding.