低復(fù)雜度的最小冗余再生碼的矩陣構(gòu)造方法

汪漢新，李 淼

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

低復(fù)雜度的最小冗余再生碼的矩陣構(gòu)造方法

汪漢新，李 淼

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

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

最小冗余再生碼；可靠性；矩陣構(gòu)造；編碼復(fù)雜度

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

1 MSR碼的矩陣構(gòu)造法

對于一種(n,k,d)再生碼，編碼時將k個數(shù)據(jù)塊編碼成n個數(shù)據(jù)塊進行存儲，其中每個節(jié)點存儲α個數(shù)據(jù).數(shù)據(jù)重構(gòu)時，會連接k個節(jié)點，每個節(jié)點傳輸α個數(shù)據(jù)，數(shù)據(jù)收集者根據(jù)收到的數(shù)據(jù)完成數(shù)據(jù)重構(gòu).當(dāng)某個節(jié)點失效時，新節(jié)點會連接d個幫助節(jié)點，其中d≥k.每個幫助節(jié)點首先進行一次線性運算，然后傳輸運算結(jié)果，傳輸量為β，新節(jié)點根據(jù)收到的數(shù)據(jù)完成節(jié)點修復(fù).修復(fù)過程中的修復(fù)帶寬γ=dβ，修復(fù)帶寬γ隨著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āng)d=l(k-1)時，

(5)

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

(6)

(7)

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

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

Ψ=(φ Λφ Δ),

(8)

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

Ψ中的每一行為：

(9)

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

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

(10)

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

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

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

(11)

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

(12)

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

(13)

其中R為：

(14)

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

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

(15)

則新節(jié)點可以接收到數(shù)據(jù)ΨrepairMR.由于Ψrepair是(d×d)的可逆矩陣，因此可以得到：

(16)

最后，將(16)式中矩陣的第一行的轉(zhuǎn)置加上第二行的轉(zhuǎn)置乘以λe1得到：

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

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

(17)

1.3 MSR碼的數(shù)據(jù)重構(gòu)

(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)

因為φ中任意α行線性無關(guān)，所以從(23)式可以求出：

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

(24)

按照上述方法，可以求出所有的S值，因此可以完成數(shù)據(jù)的重構(gòu).

2 實驗仿真結(jié)果與分析

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

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

3 結(jié)語

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

[1] 郝 杰,逯彥博,劉鑫吉，等.分布式存儲中的再生碼綜述[J]. 重慶郵電大學(xué)學(xué)報,2013,25(1):30-38.

[2] 譚鵬許,陳 越,蘭巨龍,等. 用于云存儲的安全容錯編碼[J]. 通信學(xué)報,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-),男，副教授，研究方向：信息與編碼，無線通信技術(shù)，E-mail:wanghx8888@163.com

國家自然科學(xué)基金資助項目(61571467)；湖北省自然科學(xué)基金資助項目(2013CFB448),(2014CFA051)

TN911

A

1672-4321(2015)04-0085-04