汪漢新，李 淼

(中南民族大學 智能無線通信湖北省重點實驗室，武漢 430074)

低復雜度的最小冗余再生碼的矩陣構造方法

汪漢新，李 淼

(中南民族大學 智能無線通信湖北省重點實驗室，武漢 430074)

針對現(xiàn)有的基于矩陣的最小冗余再生碼的構造方法中存在的編碼和重構復雜度高及參數(shù)選擇受到限制的問題，設計了一種矩陣實現(xiàn)的最小冗余再生碼的構造方法.該方法通過改變數(shù)據(jù)矩陣和修復向量的結構，能夠有效地減少最小冗余再生碼的編碼和數(shù)據(jù)重構的復雜度，同時參數(shù)的選擇更加簡單和靈活.

最小冗余再生碼；可靠性；矩陣構造；編碼復雜度

分布式系統(tǒng)通過增加冗余來保證數(shù)據(jù)的完整性和可靠性,提高系統(tǒng)的容錯能力[1].冗余策略由最初的簡單副本策略發(fā)展為糾刪碼，進而發(fā)展為再生碼[2].通過選取單個節(jié)點的存儲空間與帶寬消耗的最優(yōu)折衷曲線的兩個極值點，再生碼分為最小冗余再生碼(MSR)和最小帶寬再生碼(MCR)[3].再生碼在修復失效節(jié)點的過程中，首先在幫助節(jié)點內進行線性運算，隨后將結果傳送給新節(jié)點，使得傳輸?shù)臄?shù)據(jù)量顯著減少.再生碼的失效節(jié)點修復分為功能性修復和精確修復，功能性修復后的節(jié)點與原失效節(jié)點的數(shù)據(jù)不一樣，但是同樣能夠完成數(shù)據(jù)的重建.而精確修復的節(jié)點與失效節(jié)點數(shù)據(jù)完全一樣，并且具有保持系統(tǒng)碼特性、修復開銷小的優(yōu)點[4]，因此在實際應用中通常采取精確修復.文獻[5]提出了一種矩陣形式的(n,k,d)MSR碼的精確修復構造方法，當d=2k-2時，能夠直接進行編碼、節(jié)點修復以及數(shù)據(jù)重構，然而在d>2k-2時，雖然可以由另一組滿足d′=2k′-2的(n′,k′,d′)碼轉換得到，但是需要首先求出滿足C=Ψk·M時的系統(tǒng)碼的數(shù)據(jù)矩陣，編碼的過程相當復雜.文獻[6]提出了一種d≥2k-2的矩陣實現(xiàn)框架，可以直接完成MSR碼的編碼，但是其數(shù)據(jù)矩陣的構造和數(shù)據(jù)重構以及節(jié)點修復的復雜度也較高，而且參數(shù)的選擇受到限制.本文提出一種d=l(k-l)(其中l(wèi)>2)時MSR碼的矩陣構造方法，該方法通過改變數(shù)據(jù)矩陣和修復矩陣的結構，能夠有效的減少編碼復雜度，同時參數(shù)的選擇也比較簡單和靈活.

1 MSR碼的矩陣構造法

對于一種(n,k,d)再生碼，編碼時將k個數(shù)據(jù)塊編碼成n個數(shù)據(jù)塊進行存儲，其中每個節(jié)點存儲α個數(shù)據(jù).數(shù)據(jù)重構時，會連接k個節(jié)點，每個節(jié)點傳輸α個數(shù)據(jù)，數(shù)據(jù)收集者根據(jù)收到的數(shù)據(jù)完成數(shù)據(jù)重構.當某個節(jié)點失效時，新節(jié)點會連接d個幫助節(jié)點，其中d≥k.每個幫助節(jié)點首先進行一次線性運算，然后傳輸運算結果，傳輸量為β，新節(jié)點根據(jù)收到的數(shù)據(jù)完成節(jié)點修復.修復過程中的修復帶寬γ=dβ，修復帶寬γ隨著d的增大而變小，因為d的增大會使得節(jié)點的傳輸量β顯著減小，而且β減小的速度會更快.在MSR碼的編碼過程中，α，γ和β分別滿足：

(1)

(2)

其中B表示原數(shù)據(jù)大小.通過條帶化處理，選取β=1，從而可以得到：

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

(1)

1.1 MSR碼的編碼

對于(n,k,d)MSR碼，編碼矩陣方程可以表示為：

C=Ψ·M,

(4)

其中C表示碼字矩陣，C中的每一行代表一個節(jié)點的存儲數(shù)據(jù)，Ψ是編碼矩陣，M是輸入數(shù)據(jù)矩陣.

當d=l(k-1)時，

(5)

選取數(shù)據(jù)矩陣M為：

(6)

(7)

可以看出S包含了所有的原數(shù)據(jù).

編碼矩陣Ψ為(n×d)矩陣，可以表示為:

Ψ=(φ Λφ Δ),

(8)

其中Ψ中任意d行線性無關.φ表示n×(k-1)矩陣，并且任意k-1行數(shù)據(jù)線性無關.Λ表示(n×n)對角矩陣，并且n個元素互不相同.Δ表示n×(d-2k+2)矩陣.而范德蒙德矩陣滿足這些要求，因此可以采用范德蒙德矩陣作為編碼矩陣.

Ψ中的每一行為：

(9)

表示每個節(jié)點的編碼向量.

在編碼時，M中的全0矩陣對編碼結果沒有影響，因此編碼矩陣方程(4)可以表示為：

(10)

從(10)式可以看出：在MSR碼的編碼過程中，編碼矩陣和數(shù)據(jù)矩陣都較小，因此編碼的復雜度得到了明顯的降低.

1.2 MSR碼的節(jié)點修復

在MSR碼的某個節(jié)點失效后，新節(jié)點可以通過連接其他任意的d個幫助節(jié)點完成失效節(jié)點的修復.假設失效節(jié)點為e1，每個節(jié)點存儲的數(shù)據(jù)為：

(11)

其中i表示相應矩陣的行值，t表示矩陣的轉置運算.可以推導得到e1儲存的數(shù)據(jù)為：

(12)

在失效節(jié)點的修復過程中，首先將幫助節(jié)點內的數(shù)據(jù)與矩陣R相乘得到:

(13)

其中R為：

(14)

隨后將得到的數(shù)據(jù)傳送給新節(jié)點.

令連接的幫助節(jié)點為(h1,h2,…,hd)∈P0，可知修復矩陣為：

(15)

則新節(jié)點可以接收到數(shù)據(jù)Ψ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碼的數(shù)據(jù)重構

(18)

數(shù)據(jù)收集者收集到的數(shù)據(jù)為：

(19)

(20)

(21)

由于S1和S2均為對稱矩陣，因此P和Q同樣為對稱矩陣，由此可以得出:

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

(22)

因為Λ中的元素互不相同，所以可以解出P和Q非對角線上的元素.對矩陣P,可以得到除去第i項后的任意第i行的數(shù)據(jù)為：

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值，因此可以完成數(shù)據(jù)的重構.

2 實驗仿真結果與分析

為了驗證本文低復雜度的MSR碼的矩陣構造方法的有效性和可行性，我們選取180MB大小的視頻文件，在windows xp系統(tǒng)環(huán)境下，選取GF(28)域，采用Java語言對(8,3,6)MSR碼進行了編程實現(xiàn)，同時還與文獻[5]和[6]的構造方法作了對比，實驗結果如表1和表2.

從表1和表2可以看出，本文方法編碼耗時小于文獻[5]和[6]兩種方法.因為本文所設計的MSR碼的構造方法，數(shù)據(jù)矩陣和編碼矩陣的大小小于其他兩種方法，矩陣乘法只需要O(8×(4×4))次操作就能完成，因此本文方法的編碼復雜度更低.同時文獻[5]由于在編碼過程中必須首先將其轉換成系統(tǒng)碼，因此編碼耗時最大，但數(shù)據(jù)重構方面，文獻[5]的數(shù)據(jù)重構耗時最少.而文獻[6]和本文方法由于采取直接編碼，因此相比于文獻[5]而言，構造方法更靈活，編碼耗時大大的降低.在節(jié)點修復方面，三者的耗時相當.另外，本文方法的數(shù)據(jù)重構代碼復用率高，實現(xiàn)簡單，復雜度相對于文獻[6]方法也有降低.

3 結語

本文設計了一種基于矩陣實現(xiàn)的(其中)的MSR碼的構造方法，主要優(yōu)勢體現(xiàn)在：(1)所需編碼矩陣和數(shù)據(jù)矩陣比較小，因此運算的復雜度較低;(2) 能夠有效的減少數(shù)據(jù)重構復雜度，同時參數(shù)的選擇比較靈活;(3) 實現(xiàn)過程中代碼的復用性較高，不需要額外的操作，實現(xiàn)簡單.

[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