一类最优带冗余的组合批处理码

发布时间：2020-03-22 01:17

【摘要】：2004年,Ishai,Kushilevitz,Ostrovsky和Sah_ai首次提出了批处理码的概念,.它是考虑如何把n项数据分配到m个服务器中(相当于编码),当用户需要这n项数据中的任意k项时,都能通过从每个服务器里至多读取t项数据来恢复这k项数据(相当于译码),同时让这m个服务器中的数据存储总量N尽可能小.其中批处理码有一类简单的情形,编码相当于直接复制总数据的子集,将译码简化成从服务器中直接读出数据,Paterson,Stinson和Wei称这类具有纯组合特性的批处理码为组合批处理码(简称CBC).2015年，Jung,Mummert,Niese 和 Schroeder 在 CBC 的基础上,添加了冗余参数 r,精确地定义了带冗余的组合批处理码(简称r-CBC).它假定读取数据时一些服务器难以利用,则对于任意k(k≤n)项数据,都能从任意选取的m-r个服务器中的每个服务器里至多读取f项数据来恢复.参数t保证了服务器间的负载平衡,当降低负载时,t的值越小越好,本文只考虑f = 1时的情形.我们称具有最小存储总量N(即N(n,k,m;r))的r-CBC是最优的,确定r-CBC的最优设计是我们研究的主要目的.本文利用纯组合的方法探究了 n = m + 1时,最优的r-CBC.第一章主要介绍了 r-CBC存在时关联矩阵所需满足的等价条件,以及r-CBC的相关定理和性质.第二章主要研究了一类特殊的0-1循环矩阵蕴含的基本性质,得到当r ≥ 1,k,≥3,mr + k+ 和(?)≤r + 1 时,r-CBC 的最优值.第三章主要研究了 r-CBC存在的另一个充要条件,如果r ≥ 2,k ≥ 3,mr + kk,则利用该条件得出,当[mn]= r + 1时r-CBC的最优值和当(?)r + 1时N(m + 1,k,m;r)的一个界.且对于特殊情况r = 1时,研究了 1-CBC与关联图之间的关系,利用图构造了一类最优的1-CBC,得出对于m ≥(?)+ k时1-CBC的最优值和对于k+ 1m ≤(?)+时N(m + 1,m;1)的一个界.
【学位授予单位】：河北师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.4

【相似文献】