Coded Caching for Dense-User Combination Network in Binary Field
Mingming Zhang, Minquan Cheng, Youlong Wu, Xianxian Li · IEEE Transactions on Communications · 2024
An$(H,r,M,N)$combination network is a symmetric relay network that involves a central server equipped with$N$files that communicates with$K$users through$H$cache-less intermediate relays, where each user maintains a local cache of size$M$files and is connected to a distinct subset of$r$relays. In this setting, the well-known uniform scheme is proposed by Zewail and Yener via Minimum Distance Separable (MDS) codes. For practical reasons, this paper studies a more general combination network where each distinct subset of$r$relays is connected to$\Lambda $users, referred to as$(H,r,\Lambda,M,N)$dense-user combination network. Although the Zewail-Yener scheme is also feasible for the considered system, it causes high computational complexity since the use of$(H,r)_{q}$MDS code involves expensive multiplication operations in large finite field. In this paper, we aim to design coded caching schemes not only to minimize the worst-case link-load, but also to be implemented over the minimum operation field, i.e., binary field$\mathbb {F}_{2}$. First, we propose a construction which can transform any coded caching scheme for the shared-link model to the considered dense-user combination network. By applying the transformation approach based on the seminal work proposed by Maddah-Ali and Niesen, we present the MAN-based scheme that operates in binary field. To further reduce the link-load under small memory regions, we propose a hybrid scheme that can extend any caching scheme for the original$(H,r,M,N)$combination network to the considered$(H,r,\Lambda,M,N)$dense-user combination network by an ingenious outer-inner construction. From the theoretical analysis of computation complexity, the proposed schemes can significantly reduce the number of bit operations. From numerical comparisons, the link-loads of proposed schemes are close to or even better than that of Zewail-Yener scheme, while significantly reducing the operation field.