On The Theory And Techniques Of Random Linear Network Coding In Wireless Broadcast Networks

Network coding is a significant coding concept after the emergence of source coding and channel coding.Network coding can improve network transmission throughput,reliability and security,and it has impaceted many disciplines.Random Linear Network Coding(RLNC)enables distributed and independent coding of all nodes in a network.The concept of RLNC solves the problem of network coding design in the case of unknown network topology,which makes network coding a more practical techinique.Wireless broadcast network is a very common wireless communication transmission scenario.As a technique suitable for distributed deployment,RLNC can significantly improve the throughput of wireless broadcast networks.Completion delay is an important metric to measure throughput.A lower completion delay reflects higher network throughput and lower energy consumption.There are two fundamental types of wireless broadcast networks,that is,the classical one without relay and the relay broadcst network.For both types,existing works lack theoretical characterization of RLNC completion delay,and the high decoding complexity of traditional finite-field-based RLNC hinders its practical deployment.This thesis focuses on the theoretical and technical research of RLNC in wireless broadcast networks,and the main contributions are summarized as follows:First,in the wireless broadcast network without relay,the completion delay performance of the RLNC scheme over finite field GF(q)is theoretically analyzed.Closed-form formulae of expected completion delay at a single receiver as well as expected system completion delay are obtained.Moreover,it is proved that the expected completion delay of GF(2)-RLNC scheme can asymptotically approach the optimal completion delay with an increasing number of original packets.In addition,the decoding complexity of GF(q)-RLNC is theoretically analyzed.In order to overcome the high decoding complexity of GF(q)-RLNC,a novel vector RLNC scheme named circular-shift-based RLNC is proposed,its decodability is discussed theoretically and its completion delay performance is characterized.Finally,in comparison with the traditional GF(q)-RLNC scheme,the proposed new vector RLNC scheme is both theoretically and numerically demonstrated to achieve a better trade-off between completion delay and decoding complexity.Second,in the full-duplex relay broadcast network,in order to explore the fundamental performance limit of RLNC in terms of completion delay,this thesis proposes a scheme named perfect RLNC with buffer,and derives a closed-form formula of the expected completion delay at a single reciever.A recursive formula of the expected completion delay at a single receiver is also obtained.By establishing a Markov chain model,the expected system completion delay of perfect RLNC with buffer is analyzed.In addition,the recursive expression of the expected system completion delay of perfect RLNC with buffer is derived,and the lower bound of the expected completion delay is given.Finally,the accuracy of the lower bound is numerically verified.The expected completion delay of perfect RLNC with buffer serves as the theoretical limit for all RLNC schemes in the full-duplex relay broadcast network.Third,in the full-duplex relay broadcast network,a known scheme named Fewest Broadcast Packet First(FBPF)RLNC is generalized to a new FBPF RLNC scheme with the buffer size configured as a parameter.An upper bound of the expected completion delay at a single reciever for the general FBPF RLNC scheme is derived.For the original FBPF RLNC scheme whose buffer size is set to infinity,the closed-form formula of the expected completion delay at a single receiver is also obtained.Under a certain quality of service constraint,we present a criterion on the optimal buffer size selection,which can improve the practicability of FBPF RLNC scheme.In addition,as a special case of general FBPF RLNC when the buffer size is set to 0,we propose a scheme named perfect RLNC without buffer,and obtain closed-form formulae of the expected completion delay for a single receiver and for the system.Perfect RLNC without buffer provides a performance guarantee for all perfect RLNC schemes in terms of the completion delay performance.In conclusion,on one hand,this thesis enriches the theoretical characterization of completion delay performance of RLNC in wireless broadcast networks,so as to provide a more complete theoretical foundation of RLNC in wireless broadcast networks.On the other hand,this thesis proposes more practical RLNC schemes in the wireless broadcast network without relay,and also proposes new RLNC schemes with better buffer utilization,which provide more options for future application of RLNC in wireless broadcast networks.