Design And Optimization Research Of BATS Codes Encoding And Decoding Algorithms

With the development of communication technology and the increasing demand for higher transmission rate and wider coverage,wireless multi-hop network has been more and more widely concerned and applied than traditional single-hop network.In wireless network,channel noise,interference,attenuation,etc,will cause packet loss in wireless transmission,thus affecting the transmission reliability.Compared with the traditional routing,network coding applied on relay nodes can effectively improve the transmission rate of data in the communication network.However,the use of network coding usually produces high computation complexities and requires large storage space.BATS codes can solve this problem effectively.BATS codes are the combination of fountain codes and random linear network coding,which not only preserve the advantages of fountain codes but also achieve higher rate than fountain codes.BATS codes have a series of advantages,so they have great research value and application prospect in the field of communication.However,BATS codes have some disadvatages that can not be ignored.First,among all the decoding methods of BATS codes,belief propagation(BP)algorithm has the lowest decoding complexity.With BP decoding,the decoding performance degrades as the source block length decreases.Second,BATS codes decoder needs to receive enough encoded packets before decoding,which induces long delay.Furthermore,the larger is the source block,the longer is the decoding delay,thus affecting transmission efficiency.Third,the decoding performance of BATS codes greatly depends on the degree distribution,the degree distribution needs to be optimized according to the changed channel environment or encoding structure.Therefore,this thesis focused on how to improve the decoding performance of BATS codes and reduce their decoding delay.The main contributions include the following aspects:Firstly,for improving the decoding performance of finite-length BATS codes,this thesis improves gaussian elimination algorithm in BP decoding and inactivation decoding algorithms by exploiting the fact that some packets can be decoded when the rank of the efficient matrix is smaller than its degree,where the decodable input packets can be found by feature recognition.Secondly,in order to further improve the decoding performance of BATS codes,this thesis proposes “BP+ incremental Gaussian” iterative decoding algorithm,which combines BP decoding with inremental gaussian elimination algorithm.When BP decoding stops,incremental GE algorithm is used to resume the BP decoding.Simulation results show that “BP+ incremental Gaussian” algorithm can achieve the same decoding performance with GE and the computational complexity can be reduced significantly.Moreover,the decoding complexity of GE algorithm increases with the increase of coding overhead,while the decoding complexity of “BP+ incremental Gaussian” algorithm decreases with the increase of coding overhead.Thirdly,aiming at the problem that BATS codes have long decoding delay,this thesis proposes sliding-window BATS codes which divide the long source block into multiple short blocks for reducing delay.After sending enough packets,window can move forward without feedbacks between the successive windows.The decoding of the input packets in the overlaps can promote the decoding of the previous windows.The proposed scheme virtually extends the block length,so that its decoding performance will not be greatly degraded.For improving the decoding performance of sliding-window BATS codes,this thesis improves the encoding structure.The encoding probabilities of input packets in a window can be different to make the allocation of coding overhead more reasonable.Simulation results show that compared with the traditional BATS codes,the decoding delay of the optimized sliding-window BATS codes is greatly reduced without sacrificing the decoding performance.However,the decoding performance of the input packets out of the sliding window will degrade as the window moves forward.Lastly,this thesis further proposes the expanding-window BATS codes for reducing delay.The expanding-window scheme is introduced to gradually decode the long source block by using the expanded window.Unlike sliding-window BATS codes,expandingwindow BATS codes always include the undecoded input packets in the expanded windows.Moreover,in order to improve the decoding performance of expanding-window BATS codes,we improve the encoding structure and optimize the degree distribution accordingly.Simulation results show that compared with traditional BATS codes,the decoding delay of the optimized expanding-window BATS code is greatly reduced.Furthermore,the decoding performance has been further improved compared with slidingwindow BATS codes.