Research On Analysis And Optimization Of Sparse Random Linear Network Coding For Satellite Communication

The satellite communication has been widely used in many fields because of its large coverage area and low dependence on ground infrastructure.But the satellite link is susceptible to the packet loss caused by error,due to long transmission distance,high radio frequency and large rainfall attenuation.The congestion control mechanism of transmission control protocol（TCP）does not distinguish between the packet losses caused by congestion and error,resulting in a significant decrease in the throughput of TCP.The TCP/SRLNC scheme based on sparse random linear network coding（SRLNC）is proposed in this dissertation,which uses the erasure correction capability of SRLNC to reduce the packet loss rate and hence improve the throughput of TCP.Since the sparsity of SRLNC can significantly reduce the encoding and decoding complexity,TCP/SRLNC can satisfy the requirements of resource constrained satellite terminal for low computational capability and less power.The throughput and the encoding and decoding complexity of TCP/SRLNC are mainly determined by the number of transmitted coded packets and the sparsity of SRLNC,respectively.In order to achieve the best performance of TCP/SRLNC,the main work and innovation in this dissertation are as follows:（1）For the optimization problem of the number of the transmitted coded packets of SRLNC under packet loss channel,the exact methods for analyzing the full rank probability of SRLNC based on maximal linearly independent set and homomorphism transform are proposed.In the maximal linearly independent set based exact method,a basis such that the coordinates of a vector with respect to this basis are explicit,is constructed to obtain a non-trivial necessary and sufficient condition that a vector is contained in a subspace,and hence the exact expression for the full rank probability of SRLNC.In the homomorphism transform based exact method,the feature of the sparse distribution and the property of the non-trivial character of the finite field are used to obtain a closed-form expression for the homomorphism transform of the sparse distribution,and hence the exact expression for the full rank probability of SRLNC.Compared with the computational complexity O(q^{（m+1）（n-1）}) of the maximal linearly independent set based exact method（m is the number of received coded packets,n is the number of source packets and q is the field size）,the computational complexity of the homomorphism transform based exact method is lower and independent of m,and is only O(q^n2/4).Compared with exhaustive computer search,above two exact methods for analyzing the full rank probability of SRLNC both have lower computational complexity.（2）In view of the high computational complexity of the exact expression for the full rank probability of SRLNC,which makes it difficult to optimize the number of the transmitted coded packets of SRLNC under packet loss channel in real-time,the approximate method for analyzing the full rank probability of SRLNC based on the maximal linearly independent set is proposed.In this method,the limiting behavior of the full row rank matrix is analyzed to obtain a high-accuracy approximate distribution of the full row rank sparse random matrix,and hence a high-accuracy approximation for the full rank probability of SRLNC.Since the maximal linearly independent set and the remaining columns set of the full row rank sparse random matrix are decoupled,the computational complexity of the full rank probability of SRLNC is reduced to O（n²）by above method.Numerical results show that,compared with existing recursive approximation,the derived approximation for the full rank probability of SRLNC has lower computational complexity;compared with existing non-recursive approximation,the derived approximation for the full rank probability of SRLNC provides up to 39%smaller number of transmitted coded packets.（3）For the optimization problem of the sparsity of SRLNC under packet loss channel,the exact methods for analyzing the rank distribution of SRLNC based on the exclusion and the Markov chain,and the approximate method for analyzing the rank distribution of SRLNC based on the Markov chain are proposed.In the exclusion based exact method,the exclusion of the events is proved to obtain the probability of the union of the event that some rows of the decoding matrix increases the rank and remaining rows maintains the rank,and hence the exact expression for the rank distribution of SRLNC.The computational complexity of the exclusion based exact method is O(r^m-rq^{（n+1）r（m-r）})（r is the rank of the decoding matrix）.In the Markov chain based exact method,a bidiagonal transition matrix is constructed to obtain a closed-form expression for the power of the transition matrix of a Markov chain,and hence the exact expression for the rank distribution of SRLNC.Since the number of received coded packets is transformed into the number of transitions of the Markov chain,the computational complexity of the Markov chain based exact method is lower and independent of m,and is only O(r² q^nr).The Markov chain based approximate method is the combination of the Markov chain based exact method and the maximal linearly independent set based approximate method.Due to low computational complexity of the maximal linearly independent set based approximate method,the computational complexity of the Markov chain based approximate method can be reduced to O（r³）.Numerical results show that,compared with existing recursive approximation,the derived approximation of the rank distribution of SRLNC provides up to 26.7%larger sparsity.（4）To validate the performance of the derived approximations of the full rank probability and the rank distribution of SRLNC in TCP/SRLNC,a testbed of TCP/SRLNC for satellite link is implemented.The test results show that,compared with existing non-recursive approximation,the derived approximation of the full rank probability of SRLNC provides up to 39.3%higher throughput of TCP/SRLNC;compared with existing recursive approximation,the derived approximation of the rank distribution of SRLNC provides up to 21.2%and 9.7%higher encoding and decoding throughput of TCP/SRLNC,respectively;compared with TCP Hybla,the proposed TCP/SRLNC scheme provides 219 times higher throughput when the packet loss rate is 30%.The results in this dissertation advance the theory of SRLNC,TCP/SRLNC scheme significantly improves the performance of satellite communication and promotes the application of SRLNC in practical communication system.