DEEG协议数据可靠性传输研究+文献综述(5)
时间:2018-04-29 13:40 来源:毕业论文 作者:毕业论文 点击:次
RS码是多进制BCH码的一种，在优尔十年代由Reed和Solomon提出来。它拥有很强的纠错能力，如今已被广泛运用于计算机网络中，是不能缺少的一种纠删码技术。 RS类纠删码有两种类型，基于矩阵运算，范德蒙阵列纠删码就是其中的一种，它使用的生成矩阵是范德蒙矩阵（Vandermonde Matrix）。RS类纠删码的原理可以表述为 。域在RS编码的过程中起着关键的作用，编码的码元均取自有限域 ，码元间的运算也需要在 上进行，这样就能使得运算封闭，数据在运算的过程中就会保持在设定的大小以内。 3.3.2 有限域 有限域也叫做伽罗瓦域( 域)，域中的元素个数是有限的，简而言之，域 中有 个符号。元素数目称为阶，其必定是一个素数的幂。 每一个阶对应的伽罗瓦域都是唯一确定的， 阶的有限域在编码理论里被广泛运用。伽罗瓦域中的加、减运算要求元素以二进制的表示方式进行运算，计算方式就是元素之间的异或运算。乘法运算即为元素的指数相加以后进行模 运算（如果有一个元素为0，那么所得结果也为0）。除法运算为元素的指数相减以后进行模 运算后（如果被除数为0，所得结果也为0）。 3.3.3 码字 Reed-Solomon码的典型码字的表示如下图所示（这是一个系统码，左边的数据块没有被改变，右边增加了校验块）： 其中， 表示有 个字符的数据块，每个字符大小为 比特； 表示有 个字符的校验块， 即为可以校正的最大字符数； 表示有 个字符的码字，从图上我们可以得出 。 3.3.4 范德蒙矩阵 如果一个矩阵为 ，它的元素 ， ( 大于0且唯一， 是素数， 是正整数)，那么矩阵 中的任意 列所组成的子方阵 ，它的转置 就是Vandermonde Matrix，如图所示： 图 3.3 Vandermonde Matrix Vandermonde Matrix中的任意 列都是互相线性独立的，也就是说像这样任意 列组成的子方矩阵为非奇异矩阵，这样才符合纠删码对Generator Matrix的要求。 3.3.5 编码原理 让我们假设需要编码的DataMatrix为 ，GeneratorMatrix为 ，那么编码后的矩阵EncodeMatrix为 。编码后的码是系统码，表示为向量前 位与编码前的原向量一致，后 位为冗余位。 3.3.6 解码原理 不同于二进制的BCH码，RS码的解码不仅需要确定错误符号的位置，还要确定其取值，这就增加了译码的复杂度。解码过程是解 元一次线性方程的问题。解码仍然需要GeneratorMatrix ，假设已知 及 ，让它们构造出方程组 = ，假设取其中任意 个方程组，前面 个方程组为 = = 。因为范德蒙矩阵列向量间线性无关，所以 存在逆矩阵，可以解得方程组。另外，也因为如此，从方程组中任取 列都能解得 ，即使有 个数据失效，我们仍然能根据剩下的 个数据求出所要的 。 3.4 可靠性方案的制定 DEEG协议对簇头具有较高的要求，簇头的能量损耗较之一般的节点来说要来的大的多，所以簇头很容易“死亡”。一旦簇头“死亡”了，该簇头所在的簇内的普通节点就无法向簇头传输数据，即使之后能重新进行簇头的选举，在新簇头没被选举出来的这段时间里，所有簇内普通节点都处于“无组织”的状态，这大大降低了网络的传输效率，这对于那些对实时性要求较高的网络来说更是致命的。所以，为了防止簇头的突然失效，在DEEG算法选出簇头之后，要再次选举出一个次簇头，次簇头就是优先级PRI第二高的那个节点。因为文[8]中已经详细讨论了簇头选举方案以及优先级PRI的计算的方法，在此就不专门讨论这一块了。这个次簇头将作为备选簇头，以备簇头失效之后，可以顶替簇头的位置，这样可以尽量减少簇内普通节点重新寻路的时间损耗和数据传输的损失。 (责任编辑：qin) |