低复杂度的最小冗余再生码的矩阵构造方法

汪汉新，李 淼

(中南民族大学 智能无线通信湖北省重点实验室，武汉 430074)

低复杂度的最小冗余再生码的矩阵构造方法

汪汉新，李 淼

(中南民族大学 智能无线通信湖北省重点实验室，武汉 430074)

针对现有的基于矩阵的最小冗余再生码的构造方法中存在的编码和重构复杂度高及参数选择受到限制的问题，设计了一种矩阵实现的最小冗余再生码的构造方法.该方法通过改变数据矩阵和修复向量的结构，能够有效地减少最小冗余再生码的编码和数据重构的复杂度，同时参数的选择更加简单和灵活.

最小冗余再生码；可靠性；矩阵构造；编码复杂度

分布式系统通过增加冗余来保证数据的完整性和可靠性,提高系统的容错能力[1].冗余策略由最初的简单副本策略发展为纠删码，进而发展为再生码[2].通过选取单个节点的存储空间与带宽消耗的最优折衷曲线的两个极值点，再生码分为最小冗余再生码(MSR)和最小带宽再生码(MCR)[3].再生码在修复失效节点的过程中，首先在帮助节点内进行线性运算，随后将结果传送给新节点，使得传输的数据量显著减少.再生码的失效节点修复分为功能性修复和精确修复，功能性修复后的节点与原失效节点的数据不一样，但是同样能够完成数据的重建.而精确修复的节点与失效节点数据完全一样，并且具有保持系统码特性、修复开销小的优点[4]，因此在实际应用中通常采取精确修复.文献[5]提出了一种矩阵形式的(n,k,d)MSR码的精确修复构造方法，当d=2k-2时，能够直接进行编码、节点修复以及数据重构，然而在d>2k-2时，虽然可以由另一组满足d′=2k′-2的(n′,k′,d′)码转换得到，但是需要首先求出满足C=Ψk·M时的系统码的数据矩阵，编码的过程相当复杂.文献[6]提出了一种d≥2k-2的矩阵实现框架，可以直接完成MSR码的编码，但是其数据矩阵的构造和数据重构以及节点修复的复杂度也较高，而且参数的选择受到限制.本文提出一种d=l(k-l)(其中l>2)时MSR码的矩阵构造方法，该方法通过改变数据矩阵和修复矩阵的结构，能够有效的减少编码复杂度，同时参数的选择也比较简单和灵活.

1 MSR码的矩阵构造法

对于一种(n,k,d)再生码，编码时将k个数据块编码成n个数据块进行存储，其中每个节点存储α个数据.数据重构时，会连接k个节点，每个节点传输α个数据，数据收集者根据收到的数据完成数据重构.当某个节点失效时，新节点会连接d个帮助节点，其中d≥k.每个帮助节点首先进行一次线性运算，然后传输运算结果，传输量为β，新节点根据收到的数据完成节点修复.修复过程中的修复带宽γ=dβ，修复带宽γ随着d的增大而变小，因为d的增大会使得节点的传输量β显著减小，而且β减小的速度会更快.在MSR码的编码过程中，α，γ和β分别满足：

(1)

(2)

其中B表示原数据大小.通过条带化处理，选取β=1，从而可以得到：

BMSR=k(d-k+1),αMSR=d-k+1.

(1)

1.1 MSR码的编码

对于(n,k,d)MSR码，编码矩阵方程可以表示为：

C=Ψ·M,

(4)

其中C表示码字矩阵，C中的每一行代表一个节点的存储数据，Ψ是编码矩阵，M是输入数据矩阵.

当d=l(k-1)时，

(5)

选取数据矩阵M为：

(6)

(7)

可以看出S包含了所有的原数据.

编码矩阵Ψ为(n×d)矩阵，可以表示为:

Ψ=(φ Λφ Δ),

(8)

其中Ψ中任意d行线性无关.φ表示n×(k-1)矩阵，并且任意k-1行数据线性无关.Λ表示(n×n)对角矩阵，并且n个元素互不相同.Δ表示n×(d-2k+2)矩阵.而范德蒙德矩阵满足这些要求，因此可以采用范德蒙德矩阵作为编码矩阵.

Ψ中的每一行为：

(9)

表示每个节点的编码向量.

在编码时，M中的全0矩阵对编码结果没有影响，因此编码矩阵方程(4)可以表示为：

(10)

从(10)式可以看出：在MSR码的编码过程中，编码矩阵和数据矩阵都较小，因此编码的复杂度得到了明显的降低.

1.2 MSR码的节点修复

在MSR码的某个节点失效后，新节点可以通过连接其他任意的d个帮助节点完成失效节点的修复.假设失效节点为e1，每个节点存储的数据为：

(11)

其中i表示相应矩阵的行值，t表示矩阵的转置运算.可以推导得到e1储存的数据为：

(12)

在失效节点的修复过程中，首先将帮助节点内的数据与矩阵R相乘得到:

(13)

其中R为：

(14)

随后将得到的数据传送给新节点.

令连接的帮助节点为(h1,h2,…,hd)∈P0，可知修复矩阵为：

(15)

则新节点可以接收到数据ΨrepairMR.由于Ψrepair是(d×d)的可逆矩阵，因此可以得到：

(16)

最后，将(16)式中矩阵的第一行的转置加上第二行的转置乘以λe1得到：

Ci=[S1φe1S3φe1… S2l-3φe1]l+

λe1[S2φe1S4φe1… S2l-3φe1]l=

(17)

1.3 MSR码的数据重构

(18)

数据收集者收集到的数据为：

(19)

(20)

(21)

由于S1和S2均为对称矩阵，因此P和Q同样为对称矩阵，由此可以得出:

Pi,j=λiQi,j=Pi,j+λiQi,j.

(22)

因为Λ中的元素互不相同，所以可以解出P和Q非对角线上的元素.对矩阵P,可以得到除去第i项后的任意第i行的数据为：

Pi,j=1=φiS1[φi… φi-1φi+1… φα+1].

(23)

因为φ中任意α行线性无关，所以从(23)式可以求出：

φiS1=Pi,j=1[φ1… φi-1φi+1… φα+1]-1.

(24)

按照上述方法，可以求出所有的S值，因此可以完成数据的重构.

2 实验仿真结果与分析

为了验证本文低复杂度的MSR码的矩阵构造方法的有效性和可行性，我们选取180MB大小的视频文件，在windows xp系统环境下，选取GF(28)域，采用Java语言对(8,3,6)MSR码进行了编程实现，同时还与文献[5]和[6]的构造方法作了对比，实验结果如表1和表2.

从表1和表2可以看出，本文方法编码耗时小于文献[5]和[6]两种方法.因为本文所设计的MSR码的构造方法，数据矩阵和编码矩阵的大小小于其他两种方法，矩阵乘法只需要O(8×(4×4))次操作就能完成，因此本文方法的编码复杂度更低.同时文献[5]由于在编码过程中必须首先将其转换成系统码，因此编码耗时最大，但数据重构方面，文献[5]的数据重构耗时最少.而文献[6]和本文方法由于采取直接编码，因此相比于文献[5]而言，构造方法更灵活，编码耗时大大的降低.在节点修复方面，三者的耗时相当.另外，本文方法的数据重构代码复用率高，实现简单，复杂度相对于文献[6]方法也有降低.

3 结语

本文设计了一种基于矩阵实现的(其中)的MSR码的构造方法，主要优势体现在：(1)所需编码矩阵和数据矩阵比较小，因此运算的复杂度较低;(2) 能够有效的减少数据重构复杂度，同时参数的选择比较灵活;(3) 实现过程中代码的复用性较高，不需要额外的操作，实现简单.

[1] 郝 杰,逯彦博,刘鑫吉，等.分布式存储中的再生码综述[J]. 重庆邮电大学学报,2013,25(1):30-38.

[2] 谭鹏许,陈 越,兰巨龙,等. 用于云存储的安全容错编码[J]. 通信学报,2014,35(03):109-115.

[3] Dimakis A G, Godfrey P B, Wu Y, et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory, 2010,56(9): 4539-4551.

[4] Shum K W. Cooperative regenerating codes for distributed storage systems[C]//IEEE. 2011 IEEE International Conference on Communications. Kyoto:IEEE,2011:1-5.

[5] Rashmi K V, Shah N B, Kumar P V. Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction[J]. IEEE Transactions on Information Theory,2011,57(8): 5227-5239.

[6] Lin S J, Chung W H. An unified form of exact-MSR codes via product-matrix framework[C]//IEEE.2013 IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications. London:IEEE,2013:830-834.

Product-Matrix Minimum Storage Regenerating
Codes to Reduce Complexity

Wang Hanxing, Li Miao

(Hubei Key Laboratory of Intelligent Wireless Communications,South-Central University for Nationalities,Wuhan 430074,China)

This paper designed a novel product-matrix minimum storage regenerating (PM-MSR) codes which can efficiently reduce the encoding and reconstructing complexity by modifying the structure of data matrices and repairing vectors. For the proposed PM_MSR codes, the parameters are more simple and the construction is more flexible.

minimum storage regenerating codes; reliability; product-matrix; encoding complexity

2015-11-19

汪汉新(1966-),男，副教授，研究方向：信息与编码，无线通信技术，E-mail:wanghx8888@163.com

国家自然科学基金资助项目(61571467)；湖北省自然科学基金资助项目(2013CFB448),(2014CFA051)

TN911

A

1672-4321(2015)04-0085-04