謝顯中，黃倩,2，王柳蘇

(1. 重慶郵電大學(xué) 寬帶接入網(wǎng)絡(luò)研究所，重慶 400065；2. 重慶郵電大學(xué) 移通學(xué)院 計算機科學(xué)系，重慶 401520)

1 引言

隨著大數(shù)據(jù)的迅猛發(fā)展，如何在云存儲/分布式存儲的可靠性與帶寬消耗之間找到一個平衡點至關(guān)重要。2007年，Dimakis等[1]第一次將網(wǎng)絡(luò)編碼思想應(yīng)用于云存儲/分布式存儲，并提出了基于網(wǎng)絡(luò)編碼思想的再生碼方案。再生碼（regenerating codes）是指在云存儲（cloud storage）系統(tǒng)中，將網(wǎng)絡(luò)編碼（network codes）技術(shù)和失效節(jié)點修復(fù)技術(shù)相結(jié)合的編碼方案[2,3]。利用再生碼技術(shù)可以在提高云存儲可靠性的同時，減少修復(fù)需要的網(wǎng)絡(luò)流量和帶寬，進一步降低存儲和修復(fù)代價。因此，各類再生碼和失效節(jié)點修復(fù)方案受到廣泛重視。Suh等[4]提出了一種滿足最優(yōu)存儲容量-修復(fù)帶寬折衷曲線的極大距離可分（MDS, maximum distance separable）碼，并通過對偶變換的形式將該修復(fù)方案同時應(yīng)用于系統(tǒng)節(jié)點和冗余節(jié)點的修復(fù)。但文獻[4]的精確修復(fù)MDS（E-MDS, exact MDS）碼只能解決單節(jié)點失效的問題，而未涉及多節(jié)點失效的情況。

對于多節(jié)點失效修復(fù)問題，多節(jié)點協(xié)作修復(fù)是有效的解決方案[5～12]。文獻[5]給出了聯(lián)合再生節(jié)點方案，但需要更多的傳輸信道，這使修復(fù)過程更加繁瑣，導(dǎo)致修復(fù)的不穩(wěn)定。文獻[6,7]所闡述的多節(jié)點靈活再生方案主要是指在修復(fù)過程中，中間節(jié)點下載所需數(shù)據(jù)的靈活性，即可同時選擇從原健康節(jié)點和其他再生節(jié)點下載數(shù)據(jù)并通過干擾對齊來修復(fù)失效節(jié)點，雖然有效地降低了修復(fù)帶寬，但仍有修復(fù)時間不同步、修復(fù)過程復(fù)雜等問題。文獻[8]在多節(jié)點聯(lián)合修復(fù)時把干擾對齊獨立地運用其中，提高了修復(fù)效率，但在精確修復(fù)時這個方案只在k=2時有效，為了使其有更大的適應(yīng)性，還有很多問題需要解決。文獻[9,10]分別將其擴展到其他k值組合時的最小帶寬再生碼（MBRC, minimum-bandwidth regenerating codes）和最小存儲再生碼（MSRC, minimum-storage regenerating codes），但在 MBRC 和 MSRC 無法取得折中平衡。Shum等[11]通過改變部分中間節(jié)點選取的幫助節(jié)點，提出了一種多節(jié)點聯(lián)合修復(fù)（MCR, multi-node cooperative regenerating）碼。MCR碼雖然可以減少修復(fù)帶寬，但也使修復(fù)過程更加繁瑣，需要更多的傳輸信道，導(dǎo)致修復(fù)的不穩(wěn)定。具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型[12]在進行多節(jié)點修復(fù)時，幫助節(jié)點把用來修復(fù)失效節(jié)點的數(shù)據(jù)直接傳輸?shù)綇慕】倒?jié)點中選取的中間節(jié)點處。然后在此中間節(jié)點上進行相關(guān)計算和處理，在保證最低修復(fù)帶寬的前提下，同步節(jié)點修復(fù)過程，減少修復(fù)鏈路數(shù)目，簡化修復(fù)過程，減少對網(wǎng)絡(luò)資源的浪費和依賴，以此增加系統(tǒng)可靠性，從而達到安全高效修復(fù)節(jié)點的目的。但由于此模型將主要的計算和處理工作放在中間節(jié)點上，所以中間節(jié)點的存儲容量和運算負荷較大，系統(tǒng)穩(wěn)定性差。

為解決上述多節(jié)點協(xié)作修復(fù)問題，本文首先根據(jù)文獻[13]的MDS雙碼(twin-MDS codes)架構(gòu)模型結(jié)合具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型，給出了一種具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型；這不但能解決具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)方案[12]中的存儲容量和運算負荷較大的問題，而且具有數(shù)據(jù)傳輸鏈路少、修復(fù)帶寬小、多節(jié)點同步修復(fù)的優(yōu)勢。進一步，本文對文獻[4]中的E-MDS碼進行擴展，給出了一種適用于多個系統(tǒng)節(jié)點和冗余節(jié)點同時修復(fù)的多節(jié)點協(xié)作的精確修復(fù)（MER, multi-node exact repair）編碼方案，并證明了其存在性。最后，通過數(shù)值仿真對比表明，本文的模型與方案在修復(fù)帶寬、數(shù)據(jù)傳輸鏈路具有較大改進，且隨著云存儲中節(jié)點數(shù)量的增多優(yōu)勢更加明顯。

2 MDS雙碼架構(gòu)下健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型

2.1 健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型簡介

具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型的基本思想是在修復(fù)r個節(jié)點失效時，d個健康節(jié)點互相協(xié)作，并從d個健康節(jié)點中選擇一個健康節(jié)點作為節(jié)點m代替再生節(jié)點，失效節(jié)點的修復(fù)過程就直接在節(jié)點m上進行，以此省掉修復(fù)過程中的中間節(jié)點環(huán)節(jié)。具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)過程如圖 1所示。

圖1 具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)過程

設(shè)原始用戶文件可分為 4個大小相同的數(shù)據(jù)塊（A1，A2，B1，B2），并存儲在2個系統(tǒng)節(jié)點（節(jié)點1、節(jié)點2）中，然后運用具有MDS性質(zhì)的再生碼對原始文件進行網(wǎng)絡(luò)編碼，再生成與系統(tǒng)節(jié)點同等大小的2個冗余節(jié)點（節(jié)點3、節(jié)點4）。假設(shè)節(jié)點1和節(jié)點3失效，選擇節(jié)點4為節(jié)點m，節(jié)點2直接將其存儲的數(shù)據(jù)塊A1和A2傳輸給節(jié)點m，然后節(jié)點m將接收到的數(shù)據(jù)再與其自身存儲的數(shù)據(jù)進行運算，則可以同時得到 2個失效節(jié)點的全部數(shù)據(jù)，并分別輸出從而修復(fù)出失效節(jié)點1和失效節(jié)點3。

在具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型中，其他健康節(jié)點傳送自己存儲的數(shù)據(jù)到節(jié)點m，則需要傳送d-1次大小為β的數(shù)據(jù)，然后再通過線性運算并輸出r個大小為α的數(shù)據(jù)，因此，成功修復(fù)所有失效節(jié)點所需的總修復(fù)帶寬為γ=(d-1)β+rα。因此，可以看出圖1中的數(shù)據(jù)傳輸量為6個數(shù)據(jù)塊，傳輸次數(shù)（傳輸線路）為 3，并且在一個修復(fù)過程就達到了同時修復(fù)2個失效節(jié)點的目的。

因此在云存儲環(huán)境中，當(dāng)存儲節(jié)點相隔距離非常大的情況下，具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型能使整個修復(fù)過程更加安全、簡便。該模型在修復(fù)失效節(jié)點時下載數(shù)據(jù)是同步的，且修復(fù)步驟簡便、安全易實施，有效地減少了所需的數(shù)據(jù)傳輸鏈路數(shù)，保證了高效率的修復(fù)節(jié)點，減少了對資源的浪費。雖然具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型的優(yōu)勢明顯，但仍然有中間節(jié)點m存儲容量、運算負荷較大的問題。因此，下一節(jié)將引入MDS雙碼架構(gòu)模型及其編碼過程。

2.2 MDS雙碼架構(gòu)簡介

在MDS雙碼架構(gòu)下，云存儲系統(tǒng)中的存儲節(jié)點（n個）被分成類型1（n1個）和類型2（n2個），如圖2所示。

圖2 MDS雙碼架構(gòu)下節(jié)點修復(fù)和源文件重建的數(shù)據(jù)下載方式

如果想從類型1的節(jié)點下載數(shù)據(jù)，則該數(shù)據(jù)可以運用線性碼C1進行編碼解碼操作；而想從類型2的節(jié)點下載數(shù)據(jù)，則數(shù)據(jù)先通過簡單的移位操作改變順序，然后運用線性碼C2進行編碼解碼操作，并且這2種線性碼（C1、C2）可以相同。另外，當(dāng)一種類型的存儲節(jié)點失效時，需要從另一種類型的健康存儲節(jié)點子集下載數(shù)據(jù)以修復(fù)這個失效節(jié)點；而如果想要重建出整個原始用戶文件，則需要從同一種類型節(jié)點子集下載數(shù)據(jù)。因為MDS雙碼架構(gòu)下的兩種線性碼都滿足 MDS特性，因此任意選擇k個同類型節(jié)點就可以恢復(fù)出整個原始用戶文件。

假設(shè)原始用戶文件為在Fq的有限域里的M個信息符號，每個存儲節(jié)點存儲k個信息字符，對于類型i=0，1，令Ci為區(qū)間[ni,k]中在有限域Fq中任意的線性碼（具有MDS特性），生成矩陣為Gi，把矩陣Gi的第l列表示為g(i,l)(1≤l≤ni)。

首先，用戶數(shù)據(jù)被分為k2個數(shù)據(jù)片段，然后對于每一個數(shù)據(jù)片段進行編碼。把這k2個數(shù)據(jù)符號排列在k×k階信息矩陣A1中，且A2=A1t，其中，上標(biāo)t表示矩陣的置換。通過編碼Ci和信息矩陣Ai來獲取這些信息數(shù)據(jù)，存儲在類型i的每一個節(jié)點中的k個信息符號對應(yīng)到k×ni階矩陣AiGi中的每一列，類型i的節(jié)點l(1≤l≤ni)存儲的數(shù)據(jù)字符在對應(yīng)在矩陣的第l列，表示為Aig(i,l)(1≤l≤ni)。易知，每個類型i的節(jié)點l與矩陣Gi中列g(shù)(i,l)一一對應(yīng)，因此稱g(i,l)為所對應(yīng)存儲節(jié)點的編碼向量。如圖3所示。

圖3 MDS雙碼架構(gòu)下2種類型碼的編碼過程

為更加具體地描述MDS雙碼架構(gòu)下的節(jié)點修復(fù)過程，下面給出一個簡單的修復(fù)過程示例。假設(shè)類型1的節(jié)點1和節(jié)點4同時失效，除了類型2的節(jié)點2、3、4把所需數(shù)據(jù)傳輸給修復(fù)g(1,1)的中間節(jié)點外，類型2的節(jié)點1、2、3也要將數(shù)據(jù)傳輸?shù)叫迯?fù)g(2,4)的中間節(jié)點處，最終修復(fù)出這2個失效節(jié)點的數(shù)據(jù)，如圖4所示。

圖4 MDS雙碼架構(gòu)的多節(jié)點修復(fù)

2.3 具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型

為了進一步提高對失效節(jié)點的修復(fù)效率、系統(tǒng)可靠性，同時降低成本，可將MER碼運用于MDS雙碼架構(gòu)模型中，對多節(jié)點失效進行修復(fù)。利用MDS雙碼架構(gòu)模型與具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型相結(jié)合，不僅達到更優(yōu)的修復(fù)效果，而且還可以克服文獻[12,13]中存在的諸多問題。

具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型如圖5所示。將存儲節(jié)點根據(jù)雙碼結(jié)構(gòu)進行布局，用戶原始文件被存放在2種類型的節(jié)點中，并分別用C1碼和C2碼為類型1和類型2的存儲節(jié)點編碼。然后在兩部分各選擇一個健康節(jié)點作為修復(fù)對方失效節(jié)點的中間節(jié)點m1和m2。假設(shè)類型2的r2個節(jié)點損壞，則屬于類型1的用來修復(fù)這些節(jié)點的健康節(jié)點的個數(shù)為d1，傳輸?shù)絤1的鏈路數(shù)為d1-1；同樣的，若是類型1的r1個節(jié)點損壞，則傳輸?shù)絤2的鏈路數(shù)為d2-1，然后在中間節(jié)點進行線性運算，得到失效節(jié)點中的數(shù)據(jù)，輸出再生節(jié)點。

圖5 具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型

假設(shè)云存儲系統(tǒng)中有總共有r個節(jié)點失效，其中，屬于C1碼和C2碼這2種類型的失效節(jié)點個數(shù)分別為r1和r2。本文分別從d1和d2個節(jié)點下載數(shù)據(jù)來修復(fù)所有失效節(jié)點，系統(tǒng)管理員從2個類型的健康節(jié)點中分別選擇 2個節(jié)點作為中間節(jié)點m1和m2，其他健康節(jié)點分別傳送數(shù)據(jù)到與自身同類型的接收端m1或者m2，則需要傳送di-1次大小為βi的數(shù)據(jù)，再通過線性運算并輸出ri個α大小的數(shù)據(jù)。因此，修復(fù)全部失效節(jié)點所需的修復(fù)帶寬為γ=γ1+γ2，其中，γi=(di-1)βi+riα。

從上面的分析可以看出，與簡單的具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型相比，只增加了少量的存儲節(jié)點，但中間節(jié)點的數(shù)據(jù)存儲量少了一半，明顯地減小了中間節(jié)點m的存儲及運算負擔(dān)。同時，在同樣的修復(fù)條件下，當(dāng)2種類型的節(jié)點中都存在多節(jié)點失效的情況時，在傳輸鏈路方面，傳輸鏈路數(shù)減少了1條。因為多了1個中間節(jié)點就少了1次健康節(jié)點傳輸數(shù)據(jù)的過程，在這個方案中d=d1-1+d2-1=d1+d2-2，而具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型中d=d1+d2-1。在修復(fù)帶寬方面，每條鏈路傳輸?shù)臄?shù)據(jù)量為α沒變，但傳輸鏈路減少了一條，也就是減少了β大小的修復(fù)帶寬，這里β=α。

綜上所述，整個系統(tǒng)的可靠性、靈活性都大大增加，既保留、甚至優(yōu)化了具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)方案的數(shù)據(jù)傳輸鏈路少、修復(fù)帶寬小、多節(jié)點同步修復(fù)的優(yōu)勢；也解決了這個方案中間節(jié)點存儲、運算負擔(dān)大的問題，在大量存儲節(jié)點的網(wǎng)絡(luò)中，此優(yōu)勢會更加明顯。在下一節(jié)中，本文將給出一種運用于具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型中的，能適用于多個系統(tǒng)節(jié)點或冗余節(jié)點的MER碼，并證明其存在性。

3 MDS雙碼架構(gòu)下具有健康節(jié)點協(xié)作的MER修復(fù)方案

Suh等[4]給出了一種(n,k,d)=(2k,k, 2k-1)的E-MDS碼。對于該 E-MDS碼，可以計算M=kβ(d-k+1)，β=1，則有這里進一步將E-MDS碼再進行簡要地概括，并為了強調(diào) E-MDS碼的對偶性，將使用與文獻[4]不同的符號表述。

設(shè)k階非奇異矩陣X=[xij],Y=[yij],Ψ=[ψij],Φ=Ψ-1=[φij]滿足

其中，矩陣Ψ、Φ為初等變換矩陣，矩陣X的列向量為x1,…,xk，矩陣Y的列向量為y1,…,yk。設(shè)K={1,…,k}，則對于?i∈K，式(1)可以表示為

設(shè)矩陣X～=(XT)-1，Y～ =(YT)-1。其中，對矩陣X（或Y）的列向量進行轉(zhuǎn)置和求逆操作后得到矩陣X～（或Y～）的列向量x～1,…,x～k（或～y1,…,～yk）。設(shè)k×k階矩陣Θ=[θ1…θk]，D=[δ1…δk]。其中，θi表示節(jié)點i中存儲的長度為k的列向量，δi表示節(jié)點k+i中存儲長度為k的列向量。

文獻[4]中給出了E-MDS編碼方案的兩種構(gòu)造方法：一種方法是將節(jié)點1到節(jié)點k設(shè)為系統(tǒng)節(jié)點，節(jié)點k+1到節(jié)點2k設(shè)為冗余節(jié)點；另一種方法是將節(jié)點k+1到節(jié)點2k設(shè)為系統(tǒng)節(jié)點，節(jié)點1到節(jié)點k設(shè)為冗余節(jié)點。首先對于第一種構(gòu)造方法，系統(tǒng)節(jié)點i中存儲的是未編碼的原始數(shù)據(jù)分塊，而冗余節(jié)點k+i中存儲的是對系統(tǒng)節(jié)點中的數(shù)據(jù)分塊進行線性變換后的編碼數(shù)據(jù)塊，其中，?i∈K。因此，k個冗余節(jié)點中的數(shù)據(jù)可以表示為

但是，該 E-MDS碼并不適合多節(jié)點修復(fù)。為了給具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型構(gòu)造一種適合的再生碼，這里對 E-MDS碼進行擴展，從而得到一種適用于多個系統(tǒng)節(jié)點或冗余節(jié)點的多節(jié)點修復(fù)網(wǎng)絡(luò)編碼方案——多節(jié)點精確修復(fù)（MER, multi-node exact repair）碼。該修復(fù)碼不僅保持了 E-MDS碼的最小修復(fù)帶寬，而且可以適用于多節(jié)點同時失效的精確修復(fù)情況。

定理1若E-MDS碼的參數(shù)矩陣Y、Ψ和編碼系數(shù)ω、σ、ω′和σ′滿足。

1) 矩陣Y是有限域GF(q)上k×k階的非奇異矩陣。

2) 矩陣Ψ是有限域GF(q)上k×k階的柯西矩陣。

3) 系數(shù)ω、σ、ω′和σ′是滿足式（7）的非零變量。

4) 對于?i，j∈K有ψijφij≠1。

則存在能同時修復(fù)r個失效節(jié)點的，并滿足再生碼割集邊界值的MER碼。

證明選取 E-MDS碼的第一種構(gòu)造方法。即對于?i∈K，矩陣Θ的列向量對應(yīng)于系統(tǒng)節(jié)點i的數(shù)據(jù)，矩陣D的列向量對應(yīng)于冗余節(jié)點k+i的數(shù)據(jù)。因為MER碼至多允許r個節(jié)點失效，所以MER碼的幫助節(jié)點數(shù)量d=n-r。

在節(jié)點修復(fù)過程中，若系統(tǒng)節(jié)點i失效，則幫助節(jié)點將各自存儲的向量與列向量yi做內(nèi)積操作，然后傳給再生節(jié)點i′；若冗余節(jié)點k+i失效，則幫助節(jié)點將各自存儲的向量與列向量xi做內(nèi)積操作，然后傳給再生節(jié)點(k+i)′。

首先證明當(dāng)r≥2時，且r個失效節(jié)點全為系統(tǒng)節(jié)點或r個失效節(jié)點全為冗余節(jié)點的情況。由于矩陣Θ和矩陣D的對稱性，所以這2種情況可以等效處理。

這樣完成定理1的證明。

根據(jù)以上的證明過程可以看出，MER碼作為E-MDS碼的擴展，不但保持了E-MDS碼在節(jié)點修復(fù)過程中滿足再生碼的割集邊界的性質(zhì)，而且可以實現(xiàn)對r個系統(tǒng)節(jié)點（冗余節(jié)點），或2個節(jié)點（單個系統(tǒng)節(jié)點和單個冗余節(jié)點）的精確修復(fù)。

4 架構(gòu)模型的數(shù)值仿真分析對比

在多節(jié)點修復(fù)問題中，前面本文已經(jīng)理論上分析了具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型與文獻[12,13]中的架構(gòu)模型比較，本文提出的架構(gòu)模型在修復(fù)帶寬、數(shù)據(jù)傳輸鏈路、中間節(jié)點存儲量運算量、系統(tǒng)可靠靈活性等方面都有一定的改進。

接下來，本文進行數(shù)值仿真對比。把幾種多節(jié)點修復(fù)模型（原始修復(fù)[1]、依次修復(fù)[15]、聯(lián)合修復(fù)[11]、健康節(jié)點協(xié)作修復(fù)[12]）與本文修復(fù)方案進行對比。為方便，當(dāng)k=d,r=n-k，且n＜2k時，把相關(guān)參數(shù)用集合的形式表示為(n,k,d)(α,B)。

4.1 修復(fù)帶寬比較

在多節(jié)點失效的環(huán)境下，MDS雙碼架構(gòu)模型的節(jié)點的修復(fù)過程中用來修復(fù)失效節(jié)點的每一個健康節(jié)點的信息字符都是相互獨立的。因此，每個健康節(jié)點只需識別中間節(jié)點的編碼向量。并且在此架構(gòu)中，整個修復(fù)過程是以一種分布式方式完成的。這種方式可以使整個修復(fù)系統(tǒng)更容易實現(xiàn)，并進一步減少節(jié)點之間的修復(fù)帶寬消耗。用表示平均每個失效節(jié)點所消耗修復(fù)帶寬的大小，各修復(fù)模型的平均修復(fù)帶寬分析結(jié)果如表1所示?？梢悦黠@地看出，本文修復(fù)模型每個節(jié)點平均的修復(fù)帶寬最優(yōu)。并且隨著云存儲中節(jié)點數(shù)量的增多，優(yōu)勢更加明顯。

表1 修復(fù)帶寬比較

4.2 數(shù)據(jù)傳輸鏈路數(shù)比較

在多節(jié)點修復(fù)過程中，在網(wǎng)絡(luò)上傳輸數(shù)據(jù)所用傳輸鏈路數(shù)f越小，系統(tǒng)可靠性越大。各修復(fù)模型所用的傳輸鏈路數(shù)結(jié)果如表2所示?？梢悦黠@地看出，本方案不僅減少了修復(fù)帶寬，也有效地減少了修復(fù)傳輸鏈路數(shù)目，簡化修復(fù)過程，增加可靠性，減少對網(wǎng)絡(luò)資源的浪費，達到了安全高效地修復(fù)節(jié)點的目的。

表2 數(shù)據(jù)傳輸鏈路數(shù)比較

具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)方案雖然傳輸鏈路數(shù)已經(jīng)大大減少，但是本方案在同等參數(shù)下比它的傳輸鏈路數(shù)少 1，在減少中間節(jié)點存儲運算負擔(dān)的同時，減少了數(shù)據(jù)傳輸鏈路數(shù)，從而減少鏈路傳輸數(shù)據(jù)失敗的幾率，使系統(tǒng)更加可靠。

4.3 中間節(jié)點上的數(shù)據(jù)量比較

由于在MDS雙碼架構(gòu)下健康節(jié)點協(xié)作的多節(jié)點修復(fù)方案中，2種編碼均會選擇一個健康節(jié)點作為修復(fù)對方編碼中失效節(jié)點的中間節(jié)點m1和m2，并分別將修復(fù)所需的數(shù)據(jù)傳輸給相應(yīng)的中間節(jié)點（m1或m2）。因此相比健康節(jié)點協(xié)作修復(fù)方案[12]，分散了當(dāng)修復(fù)多個失效節(jié)點時，單個中間節(jié)點上的數(shù)據(jù)量。

各修復(fù)模型中，單個中間節(jié)點上的最大數(shù)據(jù)量如表3所示。雖然中間節(jié)點的總數(shù)據(jù)量并沒有明顯減少，但本文的修復(fù)模型通過增加中間節(jié)點個數(shù)，使得單個中間節(jié)點的處理數(shù)據(jù)量減少，從而分散了中間節(jié)點的處理壓力。

表3 單個中間節(jié)點上的數(shù)據(jù)量比較

除了以上3個方面的優(yōu)勢外，MDS雙碼架構(gòu)模型的另一個主要優(yōu)勢在與它適用于任意的線性糾刪碼，而MER編碼方案即是一種適用于多個系統(tǒng)節(jié)點和冗余節(jié)點的多節(jié)點修復(fù)線性網(wǎng)絡(luò)編碼方案。因此只要在E-MDS碼的基礎(chǔ)上使各參數(shù)滿足定理1中的約束條件，存在一種 MER碼可適用于具有健康節(jié)點協(xié)作的 MDS雙碼架構(gòu)模型，使系統(tǒng)性能更優(yōu)。

5 結(jié)束語

本文首先根據(jù) MDS雙碼架構(gòu)模型結(jié)合具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)模型，給出了一種具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型。該模型在具有健康節(jié)點協(xié)作的多節(jié)點修復(fù)方案的基礎(chǔ)上，解決了中間節(jié)點存儲、運算負擔(dān)大的問題，尤其在海量存儲節(jié)點的網(wǎng)絡(luò)中，此優(yōu)勢會更加明顯。其次，本文通過約束參數(shù)條件，將適用于單節(jié)點修復(fù)的E-MDS碼擴展成了適用于多個系統(tǒng)節(jié)點或冗余節(jié)點同時修復(fù)的MER碼，并證明了其存在性。并在理論意義上將MER碼與具有健康節(jié)點協(xié)作的MDS雙碼架構(gòu)模型相結(jié)合，以達到對多節(jié)點修復(fù)的同時，降低修復(fù)帶寬、修復(fù)鏈路數(shù)和單個中間節(jié)點需要處理的數(shù)據(jù)量。最后本文將具有健康節(jié)點協(xié)作的 MDS雙碼架構(gòu)模型與現(xiàn)有的幾種架構(gòu)模型進行數(shù)值仿真對比。結(jié)果表明，在進行多節(jié)點修復(fù)時，本文給出的架構(gòu)模型減少了修復(fù)帶寬和數(shù)據(jù)傳輸鏈路數(shù)，降低了中間節(jié)點的數(shù)據(jù)處理量，進一步提高系統(tǒng)可靠性。對于下一步工作，將從MER碼的具體構(gòu)造和雙碼架構(gòu)下的MER碼在現(xiàn)實網(wǎng)絡(luò)中的實現(xiàn)進行研究。

[1] DIMAKIS A G, GODFREY P B, WAINWRIGHT M J,et al. Network coding for distributed storage systems[A]. IEEE International Conference on Computer Communications (INFOCOM)[C]. 2007. 2000-2008.

[2] DIMAKIS A G, RAMCHANDRAN K, WU Y,et al. A survey on network codes for distributed storage[J]. Proceedings of the IEEE,2011, 99(3): 476-489.

[3] 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.

[4] SUH C, RAMCHANDRAN K. Exact-repair MDS code construction using interference alignment[J]. IEEE Transactions on Information Theory, 2011, 57(3): 1425-1442.

[5] HU Y, XU Y, WANG X,et al. Cooperative recovery of distributed storage systems from multiple losses with network coding[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2): 268-275.

[6] WANG X, XU Y, HU Y,et al. MFR: multi-loss flexible recovery in distributed storage systems[A]. IEEE International Conference on Communications (ICC)[C]. 2010. 1-5.

[7] 謝顯中, 黃倩, 王柳蘇, 等. 一種云存儲中基于干擾對齊的多節(jié)點精確修復(fù)方法[J]. 電子學(xué)報，2014, 42 (10): 1873-1881.XIE X Z, HUANG Q, WANG L S,et al. A multi-node exact repair method in cloud storage based on interference alignment[J], Acta Electronica Sinica, 2014, 42 (10): 1873-1881.

[8] LE S N. Exact scalar minimum storage coordinated regenerating codes[A]. IEEE International Symposium on Information Theory Proceedings (ISIT)[C]. 2012. 1197-1201.

[9] WANG A, ZHANG Z. Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage[A]. IEEE International Conference on Computer Communications (INFOCOM)[C].2013. 400-404.

[10] LI J, LI B. Cooperative repair with minimum-storage regenerating codes for distributed storage[A]. IEEE International Conference on Computer Communications (INFOCOM)[C]. 2014. 316-324.

[11] SHUM K W, HU Y. Cooperative regenerating codes[J]. IEEE Transactions on Information Theory, 2013, 59(11): 7229-7258.

[12] 謝顯中, 王柳蘇, 黃倩, 等. 具有健康節(jié)點協(xié)作的高效多節(jié)點修復(fù)方案[J]. 北京郵電大學(xué)學(xué)報. 2014, 37(1):52-56.XIE X Z, WANG L S, HUANG Q,et al. Efficient multi-node regenerating program with healthy nodes collaboration in distributed storage systems[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(1):52-56.

[13] RASHMI K V, SHAH N B, KUMAR P V. Enabling node repair in any erasure code for distributed storage[A]. IEEE International Symposium on Information Theory(ISIT)[C]. Saint Petersburg, Russia, 2011.1235-1239.

[14] LI X, ZHENG Q, QIAN H,et al. Toward optimizing cauchy matrix for cauchy reed-solomon code[J]. IEEE Communications Letters, 2009,13(8): 603-605.

[15] WU Y, DIMAKIS A G. Reducing repair traffic for erasure coding-based storage via interference alignment[A]. IEEE International Symposium on Information Theory Proceedings (ISIT)[C]. Seoul,2009. 2276-2280.