Design Of Efficient Coded Caching Schemes Based On Placement Delivery Array

The development of communication technology and the Internet,as well as the intelligence of various industries,has led to an explosive growth in network data traffic,which has brought a heavy burden and huge challenges to resource constrained communication networks.Moreover,the high variability of data traffic often leads to network congestion during peak hours and idle network resources during off-peak hours.Caching is one of the effective techniques for shifting traffic from peak to off-peak hours,thus alleviating data transmission pressure.Coded caching creates more multicast opportunities for users through appropriate file splitting and placement,thereby further reducing the transmission load.The implementation complexity of coded caching increases with the increase of file subpacketization,so designing coded caching schemes with transmission load and subpacketization as small as possible is the key issue of coded caching research.Combinatorial coded cache schemes（which adopt uncoded placement and one-shot transmission strategy）are highly favored due to their low computational domain and simple placement.However,the MN scheme,which is a combinatorial coded caching scheme with the optimal transmission load,has the problem of subpacketization being too high,and most existing combinatorial coded caching schemes with lower subpacketization only target special parameters（the number of users and memory ratio）and have relatively high transmission load.Therefore,for general parameters,designing combinatorial coded caching schemes with transmission load as small as possible at different subpacketization levels respectively has important theoretical significance and application value.Placement Delivery Array（PDA）can simultaneously characterize the placement and transmission strategies of combinatorial coded caching schemes.Therefore,the problem of designing combinatorial coded caching schemes is equivalent to the combinatorial mathematical problem of constructing PDA.By systematically studying the construction of PDA,this thesis unifies multiple existing coded caching schemes,and then designs new coded caching schemes suitable for general parameters at different subpacketization levels respectively,which have better performance than existing schemes.Finally,these new schemes are applied to multi-access caching systems.The detailed results are summarized as follows:1)A PDA construction method based on Hamming distance is proposed,which unifies multiple existing coded caching schemes.The row index set and column index set can be selected flexibly in this construction method.When the special column index set leading to the maximum number of users is selected,the row index set must be an orthogonal array.When the coding gain reaches its maximum（i.e.the transmission load reaches its minimum）,the row index set must be a covering array.Thus,tight lower bounds on the transmission load and subpacketization are obtained,and the connection between PDA coded caching schemes and Combinatorial Design Theory is established.Finally,by selecting the row index set and column index set based on the derived lower bounds,three new coded caching schemes are obtained using this construction method,which unifies multiple existing coded caching schemes.2)A PDA construction method based on Cartesian product is proposed,which designs a new coded caching scheme with asymptotically optimal transmission load and exponentially-reduced subpacketization with respect to the MN scheme under general parameters.Based on the8)-fold Cartesian product of a₁-user base PDA（where8）is any positive integer),this construction method constructs an8)₁-user PDA while keeping the memory ratio and transmission load unchanged.Since a base PDA must satisfy some additional constraints,a transformation from any existing PDA to a base PDA is proposed,which makes this construction method applicable to any existing PDA.By selecting or constructing high-performance base PDAs,three new coded caching schemes with better performance than existing schemes are obtained using this construction method,one of which is applicable to general number of users and memory ratio,and has asymptotically optimal transmission load and exponentially-reduced subpacketization with respect to the MN scheme.3)A PDA construction method based on Cartesian product and union is proposed,which designs coded caching schemes with sub-exponential subpacketization and transmission load as small as possible.By taking the union of cache configurations on the basis of the Cartesian product of a base PDA,the placement array is obtained.Then the non-star elements of the placement array are designed by using the conditions of the base PDA,such that the resulting array is a PDA with transmission load as small as possible.Based on the base PDAs used earlier,three new coded caching schemes with sub-exponential subpacketization and better performance than existing schemes are obtained using this construction method,one of which is applied to the multi-access caching system proposed by Katyal et al.Compared with existing multi-access coded caching schemes,the obtained scheme can achieve lower transmission load with the same subpacketization.Moreover,the obtained scheme is suitable for general memory ratio,while existing schemes are only suitable for special memory ratios.4)A PDA construction method under the consecutive cyclic placement is proposed,which designs a new coded caching scheme with linear subpacketization under general parameters,whose transmission load achieves the derived lower bound on the transmission load of PDA under the consecutive cyclic placement.Then the new scheme is applied to the multi-access caching system proposed by Hachem et al.to obtain a multi-access coded caching scheme with linear subpacketization under general parameters.Compared with the existing multi-access coded caching schemes with sub-exponential subpacktization,the obtained scheme can achieve lower transmission load and lower subpacketization simultaneously.Compared with the existing multi-access coded caching schemes with linear subpacketization,the obtained scheme can achieve lower transmission load.In summary,this thesis proposes several methods for designing coded caching schemes with transmission load as small as possible under different subpacketization levels,aiming to provide multiple coded caching schemes with low implementation complexity and high transmission efficiency for communication networks,as well as to provide new ideas for the research of Combinatorial Design Theory,Graph Theory,and so on.