英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
基于网络的局部修复码
- 摘要
局部修复（LR）码被用于分布式存储网络中，以达到在节点修复过程中参与的存储节点数最小化的目的。然而现存的局部修复码的结构没有将存储网络的拓扑结构考虑在内，这篇论文的工作主要是设计一个网络结构上的局部修复码。我们引入一个叫节点局部性的新概念。它表明在满足码率的限制，符号局部性，节点局部性和修复开销等约束条件下，决定一个二进制线性局部修复码是否存在的决策问题是NP-完全的。此决策问题所对应的最优化问题在这篇论文中也被讨论，NP-完全，它的目标是将码率最大化。这个问题已经被证明可以归约为最小k维集合覆盖问题，并且能够在符号局部性为1的特殊情况下，在多项式时间内被解决。对于符号局限性大于等于2的普通情况下，这个问题NP-难，它能够通过贪婪算法得到近似解。
- 介绍：
在异构分布式存储系统中，数据通常存储在几个地理位置分散的存储节点中，这些节点是网络链接的。在异构分布式存储系统中的存储节点通常不可靠且容易失效。为了维持一个分布式存储系统的可靠性，冗余技术被引用到不同的编码技术中。而且，一个数据修复机制必须能够处理普遍而非个例的节点失效。
复制码和纠删码被普遍应用于产生冗余。在复制码策略中，数据被复制并存储在多个存储节点中。这个方法虽然简单，但是有非常高的存储开销。相比于复制码，纠删码更节省存储空间。然而，当一个节点失效，纠删码为了恢复丢失数据，需要取回所有的原始文件，这会造成相当大的网络拥堵和输入输出操作。为了使修复一个失效的存储节点所需要的通信量，即修复带宽尽肯能小，Dimakis等人，基于网络编码的概念，提出了一个新的编码类型，叫做再生编码[1]。即使使用再生编码可以减少修复带宽，一个代替节点需要链接许多幸存节点，这普遍会造成大量的输入输出带宽。
修复局部性的概念被定义为参与修复失效节点的存储节点数量，[2]和[3]中对它有独立地介绍。在保证低修复开销的情况下，旨在减少修复局部性的编码叫局部修复码。对于标量线性码，[2]中确立了局部性和编码距离之间的权衡。给定一个修复局部性和每个节点的存储总数，[4]中给出了任何（线性或非线性）向量局部修复码在最小距离上的一个上界。最优局部修复码的明确结构能够在[5]和[6]中找到答案。使用再生码作为本地码，一些局部修复码在[7]中被构造。
现存的大多数局部修复码的研究中，分布式存储系统中所有的存储节点都简单地假设为与其他节点完全链接，并且存储网络中所有的通信链接都假设为相同的。然而在一般情况下，现实的分布式存储系统是异构的，这意味着每一对存储节点之间的通信链接在带宽和通信开销方面有不同的特性。举个例子，坐落于相同地理区域的存储节点的互相通信，相较于不同地区的节点通信，有着更高的带宽和更低的开销。此外，可能有一些存储节点没有直接链接。虽然[8],[9],[10],[11]中考虑了异构分布式存储系统，尽我们所知，但是对于如何设计一个异构存储网络上的局部修复码问题没有普适性结论。在[12]中，存储网络的拓扑结构在设计局部修复码时首次被考虑。局部修复码和指数编码之间的二元性结果在[12][13]中确立。
这篇论文，我们专注于设计异构网络上的局部修复码。如果存储节点可能没有完全链接，一个新的观念叫做节点局部性。我们考虑决定是否一个二进制线性码存在的判定问题时，需要考虑码率的限制，符号局部性，节点局部性和修复开销。当符号局限性的r大于2时，我们可以证明一个二进制线性LRC的判定问题是一个NP-完全。我们同样考虑了通信最优化版本，其目的在于使码率最大化。我们可以看到，在符号局限性为r的条件下，一个二进制线性LRC的码率最大值在多项式时间（polynomial time）中能够被归约为MIN-（r 1)-SETCOVER问题，当r=1的特殊情况下，能够在多项式时间中最优解答。对于一般情况，rge;2，这个问题是一个NP-hard，并用贪婪算法能够大致趋于最优解。
- 网络上的局部修复码
考虑到我们想要存储一些数据到分布式存储系统的情况，该分布式存储系统由n个通过网络任意链接的存储节点组成。被存储于分布式存储系统中的数据被假设为一个容量qge;2的字母表中的符号。让k个原始符号被存储，这k个符号由k维向量表示x=（x1,x2,...,xk）。我们通过一个无向图G=（V，ε）来代表一个网络上的分布式存储系统，V=N=｛1,2,...,n｝是存储节点的集合，E是边集。每一个边（i,j）isin;ε有权重wij，权重代表从顶点i到顶点j，或顶点j到顶点i传输一个符号的开销。
我们通过一个编码函数来定义存储编码C，这个函数将k维向量映射为n维向量：
，（1）
其中kle;n。定义C是的像。C的码率被定义为k/n。通过存储编码C将原数据编码后，n个已编码符号以一个节点存储一个符号的方式存入分布式存储系统。
不失一般性，我们假设节点iisin;V存储的符号。
给定任意向量和任意自然数的集合的子集，我们设是的子向量，通过移除中所有除指数在中的元素得到。当一个存储节点命名为节点i且失效时，失效节点能够轻易再生至关重要，从某种意义上不必先解码x然后再编码得到。符号的一个子向量，若有再生函数使得对于所有可能码字都满足，据说是可以从中再生。
我们考虑一个重要的存储编码的类型叫做局部修复码。局部修复码的一个关键概念是码字的任意符号与一个度量相关联，即符号局部性。具体来说，如果存在一个基数|H|=ri的集合，使可以从中再生，则一个编码符号可以说具有符号局部性。集合叫做节点i的帮手集合。
为了修复失效节点i，我们需要通过计算再生函数来再生，其中是节点i的帮手集合。为了这样做，节点i需要通过网络从中的节点取回信息。如之前提到的，沿着边（j,k）传输一个符号会造成开销wjk。节点i再生所需要的所有通信开销叫做的修复开销。在通信过程中，我们假设不仅路由选择，而且网络编码可以被使用。换言之，一个网络中的节点不仅可以基于本地符号和输入符号来计算新的符号，而且可以传输这些新符号到邻居节点。参与这个通信过程的所有节点总数叫做的节点局部性。显而易见，对于所有i，因为在再生符号期间所有存储节点可能仅仅发送它受到的符号，所以ge;。
如果其每一个编码符号的符号局部性不超过r，节点局部性不超过oslash;，修复开销不超过c，则一个在图G上的存储编码C可称为参数（r,oslash;,c）的局部修复码。如果是一个有限域，编码函数、译码函数和再生函数都是线性函数，我们称编码是线性的。
- 线性局部修复码和修复组
从现在开始，我们仅考虑在大小为q的有限域上的线性局部修复码C。它的正交补集，也叫做对偶码，通过表示。如果不能从的任何子集中再生，我们称是节点i的最小帮助集合。如果是最小的，可以写成：
，（2）
其中ajne;0。然后，其中kisin;但kne;i，能够被写成：
，（3）
由于系数都是非零的，是节点k的帮助集合。而且，这个帮助集合是最小的，否则可以从的一个适当的子集中重新生成，并且不能称为节点i的最小帮助集合。因此，我们说是一个修复组，其正式定义如下：
定义1（修复组）：给定一个n维线性编码C，如果每一个元素iisin;R可从R{i}中再生，一个N的子集R叫做C的修复组。
如下引理展示了一个线性码C的修复组和C的对偶码之间的关系。
定义2（支持集合）：一个码字的支持集合由supp（c）表示，
它是包含c的非零条目的指数的集合。也就是说，。
引理1：当且仅当有一个码字yisin;满足supp（y）=R，R是一个线性编码C的修复组。
证明：略。
相反地，猜测有一个码字且supp（y）=R。给定任意c=（c1,...,cn）isin;C，我们有，且对任意iisin;R有。因此，R是C的修复组。
回顾修复过程期间，通信和开销的限制都必须满足。考虑存储网络G中节点i的修复，iisin;R。因为编码是线性的，的再生函数能够通过（2）被表示。为了从除去节点i的R中再生，修复过程如下：
1). 找到G中的一个最小权重的斯坦纳树，其需要满足三个条件：
- 它包含了R中所有的顶点
- 它包含的顶点不超过Phi; 1个
- 边的权重之和不超过c
2). 让节点i称为斯坦纳树的根节点。斯坦纳树的所有的叶子节点都属于R。
3). 将每个叶子节点设为节点j，传递到它们的父亲节点。
4). 将每个中间节点设为节点k，当它们收到了其孩子节点的所有符号后，将加上输入的符号并传递给其父亲节点。
5). 收到孩子节点传来的所有符号后，节点i通过所有输入符号一起再生
斯坦纳树的每一个节点只传输过有且仅有一次符号。作为结果，修复开销等于最小权重斯坦纳树的权重。
标注每一个斯坦纳树的边仅被用来传递一个符号。作为结果，修复开销等于最小权重斯坦纳树的权重。上述修复过程衍生出如下定义：
定义3（可行修复组）：给定一个加权图 G=（V，ε），有V的一个子集R。若|R|le;r 1，并且有一个包含R中所有顶点的最小权重斯坦纳树，其顶点数不超过Phi; 1且所有边的权重之和不超过c，则称R为一个可行修复组。
- 线性局部修复码问题
在这一节中，我们考虑决定一个给定码率的线性局部修复码，在满足于符号局部性、节点局部性和修复开销的限制条件下是否存在的问题。我们假设r和oslash;是较小的常数，它们独立于n。所有的可行修复组能够通过算法1找到。分析对于n而言的计算复杂性，我们只需要考虑最外面的两个for-loop循环。我们需要检测对于每一个给定的i的个子集，其中i从2到Phi; 1。因为在i=Phi; 1时候，算法1的复杂性是。
找到所有可行修复组之后，可以回答如下问题：
问题：
实例：整数n,k和一个可行修复组的集合,其中|Ri|le;r 1（i从1到l），且R0中所有集合的并集为N。
疑问：这有一个码率至少为k 的q维线性局部修复码吗？
现在，我们证明是一个NP-完全。关键想法是归约为一个k维集合覆盖问题，描述如下：
问题：k维集合覆盖
实例：n个元素的总集U，一个U的子集的集合，其中|Si|le;k（i从1到l），且S0中所有集合的并集为U。
算法1：找到所有的可修复组
输入： G=（V，ε），r，Phi;，c
输出：所有可修复组的集合
- 初始化为一个空集
- for（i=2；ile;Phi; 1；i ）
{
选择所有V的i维子集并得到;
Z=min（i，r 1）;
for（j=1；jle;n；j ）
<st
剩余内容已隐藏，支付完成后下载完整资料</st
资料编号：[237149]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
