基于缓存辅助的共享链路广播网络和组合网络的基本限制

134 浏览量更新于2023-12-03 收藏 17.85MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

HAL Id: tel-01842269https://theses.hal.science/tel-01842269L’archive ouverte pluridisciplinaire HAL, estdestinée au dépôt et à la diffusion de documentsscientifiques de niveau recherche, publiés ou non,émanant des établissements d’enseignement et derecherche français ou étrangers, des laboratoirespublics ou privés.Kai Wan0提交日期：2018年7月18日0HAL是一个多学科的开放获取存档，用于存储和传播科学研究文件，无论它们是否发表。这些文件可以来自法国或国外的教育和研究机构，也可以来自公共或私人研究中心。0基于缓存辅助的共享链路广播网络和组合网络的基本限制0引用此版本：0Kai Wan. 基于缓存辅助的共享链路广播网络和组合网络的基本限制. 信息论 [cs.IT]. Université Paris Saclay(COmUE), 2018. 英文. �NNT : 2018SACLS217�. �tel-01842269�ii(Tang, Kenneth, Meysam, Ahmad, Sara, Narueporn) at UIC where I visited three times. My time at Chicagoand UIC, for their friendly assistant.I owe a lot to my parents, who encouraged and helped me at every stage of my personal and academiclife, and longed to see this achievement come true. I would like to thank them for their strong love andencouragement.Last but not the least, I am very much indebted to my wife, who is willing to accompany me in Franceduring these years. I can not ﬁnd any words to express my gratitude to her. I also would like to thank ourlovely dog and cat, who make our life really happy and colorful.0致谢0在完成这篇博士论文时，得到了多位人士的支持。我要感谢。0向他们表示衷心的感谢。0我非常感谢我的导师Daniela Tuninetti教授和Pablo Piantanida教授，他们的坚实支持。0感谢他们的支持。我要感谢他们对我的信任，并给予我这个职位。我要感谢。0感谢他们对这个对我来说完全陌生的主题的详细指导。我知道当我开始时，我对此一无所知。0我不擅长英语口语和写作。我要感谢他们在讨论期间的耐心。0他们一直陪伴着我，纠正我的论文。我希望在这三年之后，他们会发现他们没有犯下错误。0选择他们是我非常开心和自豪的事情。0我要感谢我们的合作者Mingyue Ji教授，他给了我们许多有趣的研究方向。0对我们的工作提供了有用的想法和详细的修正。0我还要感谢我的行政顾问Pierre Duhamel教授和Armelle Wautier教授，他们给予了我很多帮助。0在行政事务上给了我很多帮助。0除了我的导师和合作者，我还要感谢我的论文委员会的其他成员：，，。0以及Dr. ，感谢他们的深入评论。0我们还要感谢巴黎-苏德大学数学系的Zhangchi Chen，他启发我们推导出附录A.7。0感谢我在伊利诺伊大学芝加哥分校（UIC）电子与计算机工程系的Tang Liu，他证明了附录A.9。0Digicosme资助了我头三年和三个月，UIC资助了我最后四个月。0我衷心感谢为我博士学位工作提供资金支持的机构。我得到了Labex的资助。0Faton, Wafa, 两个Chao, Xiaoxia, Xiaojun, Jian, Xuewen和其他许多人，我要感谢他们。0对于我在Laboratoire des Signaux et Système (L2S)的同事们，Weichao, Chen, Li, Maggie，我要感谢你们。0我们一起度过了很多时光。我要感谢在法国的所有“兄弟们”（Siqi, Yunsong, Yao, Nan, Zhichao等）。0感谢大家在过去几年里进行的激动人心的讨论，感谢我们在一起度过的快乐时光，感谢我们一起工作的每一天。0在UIC，我访问了三次，感谢Tang, Kenneth, Meysam, Ahmad, Sara, Narueporn等人。在芝加哥的时光。0即使我远离家乡，也不会感到孤单。我还想感谢我的办公室同事们。0因为他们的存在，我的生活变得愉快。我想感谢L2S实验室的所有同事和秘书们。iiiContentsAcknowledgementsii1Introduction11.1Background and Motivation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1.1Motivation for Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.1.2Cache-aided Shared-link Broadcast Networks . . . . . . . . . . . . . . . . . . . . .11.1.3Cache-aided Combination Networks . . . . . . . . . . . . . . . . . . . . . . . . . .31.2State-of-the-Art and Main Contributions for Cache-aided Shared-link Networks . . . . . . .51.2.1Past Work on Cache-aided Shared-link Networks . . . . . . . . . . . . . . . . . . .51.2.2Past Work on Index Coding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.2.3Main Contributions for Cache-aided Shared-link Networks . . . . . . . . . . . . . .81.3State-of-the-Art and Main Contributions for Cache-aided Combination Networks . . . . . .91.3.1Past Work on Cache-aided Combination Networks. . . . . . . . . . . . . . . . . .91.3.2Combination Networks with Cache-aided Relays and Users. . . . . . . . . . . . .101.3.3Main Contributions for Cache-aided Combination Networks . . . . . . . . . . . . .101.4Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121.4.1Journal Articles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131.4.2Conference Papers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13Part 1Coded Caching in Shared-link Broadcast Networks152System Model and Some Known Results162.1The Index Coding Problem: Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162.2The Index Coding Problem: Composite (Index) Coding Achievable Bound . . . . . . . . . .172.3The Index Coding Problem: Acyclic Subgraph Converse Bound for Multiple Unicast IndexCoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .172.4The Caching Problem: Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .182.5The Caching Problem: Achievability of (1.1b) and (1.3), and of (1.5b) and (1.6) . . . . . . .202.6Mapping the Caching Problem with Uncoded Cache Placement into an Index Coding Problem 213Novel Index Coding Achievable Bound233.1Chapter Overview and Related Publications . . . . . . . . . . . . . . . . . . . . . . . . . .233.2Novel Index Coding Achievable Bound. . . . . . . . . . . . . . . . . . . . . . . . . . . .23iv4Optimal Converse Bound under the Constraint of Uncoded Cache Placement for Cache-aided Shared-link Broadcast Networks274.1Chapter Overview and Related Publications . . . . . . . . . . . . . . . . . . . . . . . . . .274.2Centralized Cache-aided Systems with Uncoded Cache Placement . . . . . . . . . . . . . .284.2.1Novel Converse Bound under the Constraint of Uncoded Cache Placement. . . . .284.2.2Optimality of the Proposed Converse Bound . . . . . . . . . . . . . . . . . . . . . .334.3Decentralized Cache-aided Systems with Uncoded Placement . . . . . . . . . . . . . . . . .34Part 2Coded Caching in Combination Networks385System Model and Some Known Results395.1System Model of Combination Networks with End-user-caches . . . . . . . . . . . . . . . .395.2Systems with Uncoded Cache Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . .415.3Caching Scheme in [50, Theorem 1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .415.4Bit-Borrowing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .436Novel Converse Bounds for Combination Networks with End-user-caches446.1Chapter Overview and Related Publications . . . . . . . . . . . . . . . . . . . . . . . . . .446.2Main Results on Novel Converse Bounds for Combination Networks with End-user-caches .446.3Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .466.4Proof of Theorem 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .486.5Proof of Theorem 10. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .496.6Proof of Theorem 11. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .516.7Proof of Theorem 12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .547Novel Inner Bounds for Combination Networks with End-user-caches567.1Chapter Overview and Related Publications . . . . . . . . . . . . . . . . . . . . . . . . . .567.2Novel Separation Based Achievable Schemes . . . . . . . . . . . . . . . . . . . . . . . . .577.2.1Direct Independent delivery Scheme (DIS). . . . . . . . . . . . . . . . . . . . . .587.2.2Interference Elimination delivery Scheme (IES) for the Case t = 1 . . . . . . . . . .587.2.3Concatenated Inner Code delivery Scheme (CICS). . . . . . . . . . . . . . . . . .647.2.4Improved Concatenated Inner Code delivery Scheme (ICICS). . . . . . . . . . . .677.3Novel Non-separation Based Delivery Scheme . . . . . . . . . . . . . . . . . . . . . . . . .707.3.1Example for H = 4, r = 2, N = K = 6 and M = 2. . . . . . . . . . . . . . . . . .707.3.2General Scheme of SRDS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .717.4Novel Non-separation Based Asymmetric Coded Placement. . . . . . . . . . . . . . . . .727.4.1Proposed Asymmetric Coded Placement for g ∈ [2 : K2 + 1] . . . . . . . . . . . . .737.4.2Proposed Asymmetric Coded Placement for g ∈ [K2 + 2 : K1] . . . . . . . . . . . .758Performance Analysis and Numerical Evaluations for Combination Networks with End-user-caches818.1Performance Analysis for Combination Networks with End-user-caches . . . . . . . . . . .81v8.1.1Optimality Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .818.1.2Comparison to Existing Schemes. . . . . . . . . . . . . . . . . . . . . . . . . . .8208.2 带终端用户缓存的组合网络的数值评估。08.2.1 H = 4，r = 2，N = K = 6的例子。08.2.2 H = 6，r = 2，N = K = 15和H = 6，r = 3，N = K = 20的例子。08.2.3 带终端用户的分散式组合网络的数值评估。0缓存。09 带缓存的扩展模型。09.1 章节概述和相关出版物。09.2 带缓存中继和带缓存用户的组合网络。09.3 带缓存的更一般的中继网络。0第三部分总结和展望。010 论文总结和未来工作展望。010.1 结论。010.1.1 带缓存的共享链路广播网络。010.1.2 带缓存的组合网络。010.2 对未来工作的展望。010.2.1 带缓存的组合网络中用户多于文件的情况。010.2.2 定理12中逆向界的线性规划。010.2.3 扩展到分布式计算。0A 附录。0A.1 定理3的证明。0A.2 表达式(4.1a)的证明。0A.3 引理1。0A.4 引理2。0A.6 证明：� 2 k +1 k � / (2 k + 1) 是一个整数。0A.7 干扰消除方案的群组划分讨论。0A.8 证明：问题2的解也是问题1的解。0A.9 定理29的证明。0A.10 定理19的证明。0A.10.1 定理19-1)的证明。0A.10.2 定理19-2)的证明。0A.10.3 定理19-3)的证明。0A.10.4 (A.55)的证明。0A.11 定理20的证明。0A.11.1 定理20-2)，3)，4)的证明。0A.11.2 定理20-5)的证明。0vi0A.12证明定理18........................................1200A.13证明定理22........................................1220A.14计算N a，其中a∈[H−r+1]在（7.47d）和（7.47e）中........................................1230A.15证明（9.3c）和（9.3f）........................................1240A.16证明定理25........................................1250A.17伪代码........................................1250B法语摘要1270参考文献1280vii0缩写列表0CICS连接内码传输方案0cMAN由Maddah-Ali和Niesen提出的集中式缓存方案0cYMA由Yu，Maddah-ali和Avestimehr提出的集中式缓存方案0dMAN由Maddah-Ali和Niesen提出的分散缓存方案0DIS直接独立传输方案0dYMA由Yu，Maddah-ali和Avestimehr提出的分散缓存方案0例如0IC索引编码0ICICS改进的连接内码传输方案0IES干扰消除传输方案0即是0MDS码最大距离可分离码0RAM随机存取存储器0ROM只读存储器0SRDS分离中继解码传输方案0viii0符号列表0花体符号表0其中集合是一组集合，例如，�{1,2}，{1,3}�0无衬线符号表示缓存系统参数0粗体字母表示向量0黑板符号表示矩阵或字段0A\B{x∈A|x/∈B}0AT矩阵A的转置0[a:b:c]{a,a+b,a+2b,...,c}0[a:c][a:1:c]0[a][1:a]0B一个文件中的位数0dim Q Q上的域扩展的次数0E[∙]期望运算符0GY连接至少两个中继的用户集合Y0与传统未编码缓存方案相比的编码缓存增益0gcd(j,n)j和n的最大公约数0H（∙）随机变量的熵0中继数量0HJ连接至少一个用户的中继集合J0Hk用户k的连接中继集合0I（∙；∙）两个随机变量之间的互信息0im（L）线性映射L的像0K缓存问题中的用户数量0的用户数量0Ki�H−ir−i�0KY用户的连接中继全部在Y中0ker（L）线性映射L的核0Q[ζ]通过添加单位ζ的原根到有理数得到的旋群域0ix0M，M用户每个用户的归一化内存大小0M中继每个中继的归一化内存大小0N缓存问题中的文件数量0N ′索引编码问题中的消息数量0Pr概率测度0Q有理数域0Q[ζ]通过将单位根ζ附加到有理数上得到的分圆域0r连接到每个用户的中继数0R最坏情况最大链路负载0R�c集中式系统中的最优最坏情况最大链路负载0R�c,u在集中式系统中具有未编码缓存放置的最优最坏情况最大链路负载0R�d分散系统中的最优最坏情况最大链路负载0R�d,u在分散式系统中具有未编码缓存放置的最优最坏情况最大链路负载0Rs→rmax服务器到中继的链路负载0Rr→umax从中继到用户的链路负载0RJ连接到J中所有用户的中继集合0RLC(m,S)m随机线性组合等长度数据包的集合，索引为S0T(n)ε(∙)弱典型n长度序列的集合0p(J)p(J):=�p1(J),...,p|p(J)|(J)�，J集合的元素的排列0Uh连接到中继h的用户集合0UY连接到Yc中所有中继的公共连接用户集合0Var()方差0Zt至少有一个中继连接到其中的用户的t-子集的集合0Z，Z+整数和正整数域0⊕对具有相同长度的二进制位或向量进行按位异或操作0|∙|集合的基数，或向量的长度，或（子）文件的长度（以位为单位）0φ欧拉phi函数�xy�二项式系数0对于两个整数x和y，如果x

下载后可阅读完整内容，剩余1页未读，立即下载