基于Harary圖生成樹的部分重復(fù)碼構(gòu)造①

張?chǎng)伍?沈克勤,孫 偉,何亞錦

(長(zhǎng)安大學(xué) 信息工程學(xué)院,西安 710061)

目前,將海量數(shù)據(jù)存儲(chǔ)在分布式存儲(chǔ)系統(tǒng)中的不同存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)存儲(chǔ)方式已在實(shí)際系統(tǒng)中得到了廣泛應(yīng)用,如Google 文件系統(tǒng)[1]、Hadoop 文件系統(tǒng)等.為確保分布式存儲(chǔ)系統(tǒng)中數(shù)據(jù)的可用性和可靠性,通常采用諸如復(fù)制策略[2]或糾刪碼策略[3,4]的數(shù)據(jù)冗余策略.以復(fù)制策略中的三副本復(fù)制為例,三副本復(fù)制需要存儲(chǔ)大量副本數(shù)據(jù)以確保系統(tǒng)較高的可靠性,存儲(chǔ)代價(jià)過高;糾刪碼策略的提出使得修復(fù)造成的存儲(chǔ)開銷顯著降低,但其過大的修復(fù)帶寬開銷也成為了限制它的瓶頸.

2007年,Dimakis 等人指出存儲(chǔ)開銷和修復(fù)帶寬開銷之間存在某種平衡,平衡曲線上的點(diǎn)可通過再生碼來實(shí)現(xiàn)[5].再生碼基于網(wǎng)絡(luò)編碼的概念,其故障節(jié)點(diǎn)可通過連接一定數(shù)目的存活節(jié)點(diǎn)完成修復(fù),相比于糾刪碼降低了修復(fù)帶寬開銷.目前再生碼的研究主要集中在最小存儲(chǔ)再生碼和最小帶寬再生碼[6].

El Rouayheb和Ramchandran為進(jìn)一步降低修復(fù)過程中的運(yùn)算復(fù)雜和帶寬開銷,提出了一種基于最小帶寬再生點(diǎn)的精確修復(fù)編碼-部分重復(fù)(Fractional Repetition,FR)碼[7].部分重復(fù)碼結(jié)合再生碼和復(fù)制策略的優(yōu)點(diǎn),有效減少了修復(fù)帶寬開銷和磁盤I/O 開銷[8],并實(shí)現(xiàn)精確的無編碼修復(fù).

目前,FR 碼主要采用分組設(shè)計(jì)[9]、可分解設(shè)計(jì)[10,11]等方法進(jìn)行構(gòu)造.朱兵等人基于分組設(shè)計(jì)提出一種重復(fù)度異構(gòu)的FR 碼的構(gòu)造[12],使得常用數(shù)據(jù)的備份更加充分,且參數(shù)選取范圍較大,但同時(shí)也造成了較大的存儲(chǔ)開銷;Natalia Silberstein和Tuvi Etzion 等人基于組合設(shè)計(jì)和正則圖,提出了一種達(dá)到最大碼率的FR 碼的構(gòu)造方法[13],但其重復(fù)度受FR 碼結(jié)構(gòu)的約束,不能適用于任意參數(shù);Harout Aydinian和Holger Boche 等人則基于部分有序集構(gòu)造了一種普遍好的FR 碼[14],這種構(gòu)造方法雖然簡(jiǎn)便,但其重復(fù)度卻也十分受限.為此,本文基于Harary 圖生成樹構(gòu)造出了一種新型的部分重復(fù)(Fractional Repetition based on Spanning trees of Harary graph,FRSH)碼,可以在很大范圍內(nèi)選擇構(gòu)造參數(shù)和數(shù)據(jù)塊的重復(fù)度,還能修復(fù)多個(gè)故障節(jié)點(diǎn).通過調(diào)整Harary 圖的構(gòu)造參數(shù),可以構(gòu)造出不同重復(fù)度的FR 碼.相比現(xiàn)有的FR 碼,采用Harary 圖生成樹設(shè)計(jì)FR 碼更加簡(jiǎn)潔直觀.相較于RS 碼和SRC[15],FRSH 碼在修復(fù)帶寬開銷、修復(fù)復(fù)雜度以及修復(fù)局部性等方面得到了更低的開銷,且改善了修復(fù)效率,并將故障節(jié)點(diǎn)修復(fù)時(shí)間縮短.

1 預(yù)備知識(shí)

1.1 Harary 圖的基礎(chǔ)知識(shí)

Harary 圖是一種正則圖,定義為Hk,m,其中k為每個(gè)節(jié)點(diǎn)所鄰接的節(jié)點(diǎn)個(gè)數(shù),即頂點(diǎn)的度;m為頂點(diǎn)個(gè)數(shù).根據(jù)k和m的取值,可分為3 種情況構(gòu)造Harary 圖.

(1)k是偶數(shù)

設(shè)k=2r,則H2r,m構(gòu)造如下:先給出它的頂點(diǎn)0,1,2,…,i,…,j,…,m?1,然后連接所有滿足|i?j|≤r的頂點(diǎn),即可完成H2r,m的構(gòu)造.

(2)k是奇數(shù),m是偶數(shù)

設(shè)k=2r+1,則H2r+1,m構(gòu) 造如下:首先構(gòu)造出H2r,m,為滿足k=2r+1,還需添加一些邊:這些邊連接了每個(gè)頂點(diǎn)i與頂點(diǎn)連接完即可得到H2r+1,m.

(3)k是奇數(shù),m是奇數(shù)

設(shè)k=2r+1,此時(shí)的H2r+1,m構(gòu)造如下:首先構(gòu)造出H2r,m,為滿足k=2r+1,需要添加一些邊:這些邊連接了頂點(diǎn)0與頂點(diǎn)和再將每個(gè)頂點(diǎn)i連到頂點(diǎn)如此連接即可完成構(gòu)造.

圖1所示是構(gòu)造的k=4,m=8的Harary 圖H4,8.

1.2 生成樹的基礎(chǔ)知識(shí)

無圈圖是指不包含圈的圖,連通的無圈圖定義為樹.無圈圖的生成樹是指頂點(diǎn)與無圈圖相同、邊集是無圈圖的邊集子集,且含邊數(shù)最少的連通子圖.圖2中T1是完全圖K8的生成樹,它包含K8中的所有9個(gè)頂點(diǎn),邊集是完全圖K8 邊集的子集,且包含了最小數(shù)目的邊數(shù).

圖1 Harary 圖H4,8

圖2 完全圖K8和它的生成樹T1

由構(gòu)造的Harary 圖G=Hk,m,以頂點(diǎn)1為起始頂點(diǎn)得出生成樹.具體構(gòu)造步驟如下[16]:

步驟1.畫出邊(1,v+1)和(1,m-v+1),v=1,2,…,

步驟2.令p=+1,j=,畫出邊(m?p+1,m?p?j+1),(m?p?j+1,m?p?2j+1),…,直到形成從頂點(diǎn)m?p+1 到頂點(diǎn)1的路徑時(shí)停止.

步驟3.令q=p+1,重復(fù)步驟2 畫出邊(m?q+1,m?q?j+1),(m?q?j+1,m?q?2j+1),…,當(dāng)存在從頂點(diǎn)m?p+1 到頂點(diǎn)1的路徑時(shí)停止,否則轉(zhuǎn)至步驟1.

圖3為基于H4,8,且以頂點(diǎn)1為起始頂點(diǎn)構(gòu)造的生成樹.

1.3 離心率的基礎(chǔ)知識(shí)

對(duì)于連通圖G的一個(gè)頂點(diǎn)v,v的離心率定義為v 到G中除v 外所有頂點(diǎn)的距離的最大值.例如圖4中頂點(diǎn)1的離心率值為3,由于距離頂點(diǎn)1 最長(zhǎng)的頂點(diǎn)是頂點(diǎn)6,而從頂點(diǎn)1 到頂點(diǎn)6的路徑中共經(jīng)過3個(gè)頂點(diǎn),即距離為3,故頂點(diǎn)1的離心率,其它頂點(diǎn)同理.G的半徑定義為G中所有頂點(diǎn)離心率的最小值,直徑則定義為G的最大離心率,分別記為rad(G)和diam(G).在圖4中頂點(diǎn)最小離心率為2,最大離心率為4,所以有rad(G)=2,diam(G)=4.

圖3 基于H4,8的生成樹

圖4 離心率參考圖

2 基于Harary 圖生成樹的部分重復(fù)碼構(gòu)造

2.1 構(gòu)造方法

ρ的FRSH 碼的構(gòu)造算法,具體步驟如算法1.

基于Harary 圖生成樹與離心率,給出重復(fù)度為

算法1.基于Harary 圖生成樹的部分重復(fù)碼構(gòu)造1)給定一個(gè)Harary 圖的設(shè)計(jì)參數(shù)k和m,其中k為每個(gè)節(jié)點(diǎn)所連接的節(jié)點(diǎn)個(gè)數(shù),即節(jié)點(diǎn)的度,m為頂點(diǎn)個(gè)數(shù),m>0.本文暫且只考慮k為偶數(shù)的情況.2)根據(jù)給出的設(shè)計(jì)參數(shù)k和m 構(gòu)造Harary 圖.3)選定Harary 圖上任一頂點(diǎn)作為頂點(diǎn)1,并從頂點(diǎn)1 開始給Harary圖的頂點(diǎn)順時(shí)針編號(hào),每個(gè)頂點(diǎn)存儲(chǔ)與其編號(hào)相同的數(shù)據(jù)塊.4)由構(gòu)造的Harary 圖以頂點(diǎn)1為起始頂點(diǎn)構(gòu)造生成樹.n(n≥1)5)對(duì)得到的生成樹的頂點(diǎn)按離心率分組,將第一個(gè)生成樹G的頂點(diǎn)按離心率分為組,分組后每組頂點(diǎn)的離心率相同,并將各組頂點(diǎn)按編號(hào)從小到大的順序分別寫入n個(gè)節(jié)點(diǎn)中,得到第一組節(jié)點(diǎn).ρ(ρ≥1)ρ?1 n?(ρ?1)6)按照所需構(gòu)造部分重復(fù)碼的重復(fù)度 更換起始頂點(diǎn),重復(fù)步驟4)和步驟5)再得到個(gè)生成樹,并將它們的頂點(diǎn)按離心率分組后分別寫入個(gè)新的節(jié)點(diǎn)中.

M=(ms,t)1≤s≤nρ,1≤t≤m 7)由生成樹頂點(diǎn)按離心率的分組得到關(guān)聯(lián)矩陣 ().關(guān)聯(lián)矩陣構(gòu)造公式如下(vt 代表生成樹中的任一頂點(diǎn),es 代表任一離心率取值):ms,t=■■■■■■■■■1,若vt與es相關(guān)聯(lián)0,其它情況d ρ ρ再將生成樹的關(guān)聯(lián)矩陣等價(jià)為FR 碼的關(guān)聯(lián)矩陣,關(guān)聯(lián)矩陣的行向量對(duì)應(yīng)FR 碼的存儲(chǔ)節(jié)點(diǎn),列向量對(duì)應(yīng)FR 碼的編碼塊.行向量的重表示表示節(jié)點(diǎn)存儲(chǔ)容量,列向量的重表示編碼塊重復(fù)度.由此即可得到重復(fù)度為的FR 碼.

綜上,重復(fù)度為ρ的FRSH 碼的構(gòu)造過程中,其包含的不同數(shù)據(jù)塊個(gè)數(shù)即為Harary 圖的頂點(diǎn)數(shù)m;重復(fù)度 ρ由生成樹個(gè)數(shù)決定;包含的節(jié)點(diǎn)個(gè)數(shù)為nρ.

具體地,我們以構(gòu)造 ρ=3的FR 碼的過程為例說明構(gòu)造方法.令k=4,m=11,構(gòu)造Harary 圖H4,11,并給其頂點(diǎn)編號(hào),如圖5(a)所示.再由構(gòu)造的Harary 圖以頂點(diǎn)1為起始頂點(diǎn)得出第一個(gè)生成樹,如圖5(b)所示.

圖5 H 4,11和它的生成樹

將圖5(b)中給出的生成樹的頂點(diǎn)按離心率分組,相同離心率頂點(diǎn)對(duì)應(yīng)的數(shù)據(jù)塊寫入同一分組.為滿足重復(fù)度 ρ=3,需重復(fù)步驟4)和步驟5),分別以頂點(diǎn)3和頂點(diǎn)5為起始頂點(diǎn)再得到第2個(gè)生成樹和第3個(gè)生成樹(此處圖略).進(jìn)一步將第2個(gè)生成樹和第3個(gè)生成樹的頂點(diǎn)存儲(chǔ)數(shù)據(jù)按離心率分組,構(gòu)造關(guān)聯(lián)矩陣M.以圖5(b)中的生成樹為例,本例中所有生成樹頂點(diǎn)的離心率es共有n=3個(gè)取值:e1=3、e2=4、e3=5.圖5(b)中頂點(diǎn)2、3、4、5的離心率都為e1=3,即v2、v3、v4、v5與e1相關(guān)聯(lián),故有m1,2=m1,3=m1,4=m1,5=1,以此類推便得到關(guān)聯(lián)矩陣M.

根據(jù)關(guān)聯(lián)矩陣M,構(gòu)造重復(fù)度 ρ=3的FR 碼,構(gòu)成的FR 碼如圖6.

圖6 FR 碼

2.2 故障節(jié)點(diǎn)修復(fù)

本論文構(gòu)造的任意FRSH 碼都包含 ρ個(gè)平行類,且最多可容忍 ρ?1個(gè)節(jié)點(diǎn)故障,具體修復(fù)方案如下:

(1)當(dāng)單個(gè)節(jié)點(diǎn)失效時(shí),新生節(jié)點(diǎn)從存活平行類中下載失效節(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)塊,即可完成修復(fù).如節(jié)點(diǎn)N1故障時(shí),損壞的數(shù)據(jù)塊2、3、4、5 可從剩余兩個(gè)平行類N4、N5、N6或N7、N8、N9中下載.這里選擇連接存活節(jié)點(diǎn)N4、N9并分別下載4、5、2、3,即可修復(fù)故障節(jié)點(diǎn)N1.

(2)當(dāng)多個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)故障,由于仍至少存在一個(gè)平行類包含全部數(shù)據(jù)塊,而本方法構(gòu)造的FR 碼的任一平行類中包含的節(jié)點(diǎn)個(gè)數(shù)等于離心率分組數(shù)n,故至多連接n個(gè)節(jié)點(diǎn)即可完成修復(fù).具體地,當(dāng)多個(gè)故障節(jié)點(diǎn)所包含的數(shù)據(jù)塊個(gè)數(shù)d<αmin+αmax(這里αmin和αmax分別表示FRSH 碼中節(jié)點(diǎn)存儲(chǔ)的最小數(shù)據(jù)塊個(gè)數(shù)和最大數(shù)據(jù)塊個(gè)數(shù))時(shí),僅需連接n?1個(gè)故障節(jié)點(diǎn)即可完成修復(fù).例如當(dāng)N2和N5同時(shí)失效時(shí),故障節(jié)點(diǎn)N2和N5共包含d=6個(gè)數(shù)據(jù)塊,滿足d<αmin+αmax.此時(shí),修復(fù)故障節(jié)點(diǎn)N2和N5需要連接n?1=2個(gè)存活節(jié)點(diǎn)完成修復(fù).這里選擇存活節(jié)點(diǎn)N7和N9,并分別從存活節(jié)點(diǎn)N7和N9下載數(shù)據(jù)塊6、7、8、9和1、3,實(shí)現(xiàn)故障節(jié)點(diǎn)N2和N5的修復(fù).

(3)當(dāng)多個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)故障,且多個(gè)故障節(jié)點(diǎn)所包含的數(shù)據(jù)塊個(gè)數(shù)d≥αmin+αmax時(shí),需連接n?1或n個(gè)不同節(jié)點(diǎn)即可完成故障節(jié)點(diǎn)修復(fù).同樣先考慮圖6中的節(jié)點(diǎn)N4和N5發(fā)生故障,此時(shí)故障節(jié)點(diǎn)N4和N5包含d=7個(gè)數(shù)據(jù)塊,滿足d≥αmin+αmax.為修復(fù)故障節(jié)點(diǎn)N4和N5需要從n?1=2個(gè)存活節(jié)點(diǎn)中下載對(duì)應(yīng)數(shù)據(jù)塊,這里選擇存活節(jié)點(diǎn)N1和N7,并分別從N1和N7下載數(shù)據(jù)塊3、4、5和6、7、8、9,即可修復(fù)故障節(jié)點(diǎn)N4和N5.另當(dāng)N2和N7發(fā)生故障時(shí),此時(shí)故障節(jié)點(diǎn)N2和N7包含d=7個(gè)數(shù)據(jù)塊,同樣滿足d≥αmin+αmax.而此時(shí)修復(fù)N2和N7需連接n=3個(gè)存活節(jié)點(diǎn)N4、N5和N6,并分別下載6、7、8、9和1 便可修復(fù)N2和N7.

綜上,對(duì)于重復(fù)度為ρ的FRSH 碼,修復(fù)單節(jié)點(diǎn)故障時(shí)在剩余平行類中連接對(duì)應(yīng)存活節(jié)點(diǎn)(連接的節(jié)點(diǎn)數(shù)至多為n?1個(gè))下載所需數(shù)據(jù)塊即可;修復(fù)多節(jié)點(diǎn)故障時(shí),當(dāng)多個(gè)故障節(jié)點(diǎn)所包含的數(shù)據(jù)塊個(gè)數(shù)d<αmin+αmax時(shí),僅需連接n?1個(gè)故障節(jié)點(diǎn)即可完成修復(fù);當(dāng)多個(gè)故障節(jié)點(diǎn)所包含的數(shù)據(jù)塊個(gè)數(shù)d≥αmin+αmax時(shí),需連接n?1或n個(gè)不同節(jié)點(diǎn)即可完成故障節(jié)點(diǎn)修復(fù).

3 性能分析

基于Harary 圖生成樹構(gòu)造的FR 碼的性能分析主要集中在修復(fù)局部性、修復(fù)帶寬開銷和運(yùn)算復(fù)雜度這幾方面,并將其與傳統(tǒng)的RS 碼和簡(jiǎn)單再生碼(Simple Regenerating Codes,SRC)進(jìn)行性能比較.表1給出了SRC、RS 碼與FRSH 碼在一般情況下的的節(jié)點(diǎn)存儲(chǔ)開銷、修復(fù)帶寬開銷以及修復(fù)局部性的計(jì)算公式,之后我們會(huì)在給定具體文件大小和編碼數(shù)據(jù)等條件下用柱狀圖的形式把上文構(gòu)造的ρ=3的FR 碼與SRC、RS 碼的各種性能逐一進(jìn)行比較.

表1 幾種編碼方案的性能分析

3.1 修復(fù)局部性

修復(fù)局部性是衡量構(gòu)造出的部分重復(fù)碼性能的重要指標(biāo)之一,其定義為節(jié)點(diǎn)故障修復(fù)過程中連接的存活節(jié)點(diǎn)數(shù)目,即磁盤I/O 開銷.此處為方便比較,我們假設(shè)原文件大小M=1000 Mb,存儲(chǔ)節(jié)點(diǎn)數(shù)則為n=11,SRC 子文件數(shù)f=3,RS 碼和SRC的原文件重構(gòu)度為k=8,FRSH 碼外部采用(11,8)MDS 編碼.本小節(jié)僅考慮兩種節(jié)點(diǎn)故障情況:單節(jié)點(diǎn)故障與兩節(jié)點(diǎn)故障.

當(dāng)單節(jié)點(diǎn)出現(xiàn)故障時(shí),SRC在修復(fù)失效節(jié)點(diǎn)時(shí)需要連接2f個(gè)節(jié)點(diǎn),這里取f=3,則SRC的修復(fù)局部性為6;若采用(11,8)RS 碼,需要連接k=8個(gè)節(jié)點(diǎn)以恢復(fù)出完整的原文件,再由原文件修復(fù)故障節(jié)點(diǎn),故其修復(fù)局部性為8;而本文構(gòu)造的FRSH 碼需要連接2個(gè)節(jié)點(diǎn)來修復(fù)故障節(jié)點(diǎn),修復(fù)局部性為2.

在兩節(jié)點(diǎn)故障的情況下,SRC與(11,8)RS 碼都需要連接k=8個(gè)存活節(jié)點(diǎn)以修復(fù)故障節(jié)點(diǎn),故它們的修復(fù)局部性都為8;而基于Harary 圖生成樹構(gòu)造的FRSH碼的修復(fù)局部性為2 或3,為便于對(duì)比,此處取恒為3 作為比較.由圖7可見,在單節(jié)點(diǎn)故障與兩節(jié)點(diǎn)故障情況下,本文構(gòu)造的FRSH 碼的修復(fù)局部性都優(yōu)于SRC和RS 碼.

圖7 修復(fù)局部性

另與基于圖因子構(gòu)造的部分重復(fù)碼相比,在單節(jié)點(diǎn)故障時(shí)兩種部分重復(fù)碼都需要連接兩個(gè)節(jié)點(diǎn)進(jìn)行修復(fù);在兩節(jié)點(diǎn)故障時(shí),基于圖因子的部分重復(fù)碼需要連接4個(gè)節(jié)點(diǎn)進(jìn)行修復(fù),而FRSH 碼至多需連接3個(gè)節(jié)點(diǎn)進(jìn)行修復(fù),可見在兩節(jié)點(diǎn)故障時(shí)FRSH 碼具有顯著優(yōu)勢(shì).

3.2 修復(fù)帶寬開銷

在單節(jié)點(diǎn)故障的情況下,SRC 需下載f個(gè)數(shù)據(jù)塊以完成修復(fù),而每個(gè)數(shù)據(jù)塊的大小為M/fk,因此SRC的帶寬開銷為(f+1)M/k;由于RS 碼在單節(jié)點(diǎn)故障的情況下完成修復(fù)需下載整個(gè)原文件,故RS 碼的帶寬開銷為原文件大小M;而本文構(gòu)造的FRSH 碼在單節(jié)點(diǎn)故障的情況下需要通過連接2個(gè)存活節(jié)點(diǎn)完成修復(fù),因此FRSH 碼的帶寬開銷為2M/k.

當(dāng)兩節(jié)點(diǎn)同時(shí)故障時(shí),RS 碼與SRC的帶寬開銷均為M.FRSH 碼的帶寬開銷為3M/k.

假設(shè)原文件大小為M=1000 Mb,存儲(chǔ)節(jié)點(diǎn)數(shù)n=11,SRC 子文件數(shù)f=3,RS 碼和SRC的原文件重構(gòu)度為k=8,FRSH 碼外部采用(11,8)MDS 編碼.當(dāng)單節(jié)點(diǎn)故障時(shí),RS 碼的帶寬開銷為1000 Mb,SRC的帶寬開銷為500 Mb,FRSH 碼的帶寬開銷為250 Mb;當(dāng)兩個(gè)節(jié)點(diǎn)故障時(shí),(11,8)RS 碼修復(fù)帶寬開銷為1000 Mb,SRC的帶寬開銷同樣為1000 Mb,為方便對(duì)比FRSH 碼的帶寬開銷取較大值3M/k=375 Mb.如圖8所示,無論單節(jié)點(diǎn)還是兩節(jié)點(diǎn)故障,FRSH 碼的修復(fù)帶寬開銷都相對(duì)較低.

圖8 修復(fù)帶寬開銷對(duì)比

3.3 構(gòu)造算法運(yùn)算復(fù)雜度

除去修復(fù)局部性與修復(fù)帶寬開銷這兩種直觀性能,構(gòu)造算法復(fù)雜度體現(xiàn)了算法在執(zhí)行時(shí)的難易程度,是衡量一個(gè)算法好壞的重要指標(biāo).所謂運(yùn)算復(fù)雜度,即將算法寫成程序在實(shí)際的計(jì)算機(jī)系統(tǒng)中運(yùn)行時(shí)涉及的計(jì)算量.本文構(gòu)造的FRSH 碼構(gòu)造時(shí)不需要任何計(jì)算量,只需調(diào)節(jié)Harary 圖與其生成樹的參數(shù)即可.相較于可達(dá)到同等性能的FRC,減少了大量的運(yùn)算時(shí)間.

將基于Harary 圖生成樹的FRSH與運(yùn)用圖因子分解構(gòu)造的FRC[17]在構(gòu)造算法運(yùn)算復(fù)雜度進(jìn)行對(duì)比分析,在文獻(xiàn)[17]中,構(gòu)造算法時(shí)運(yùn)用到了加法,乘法運(yùn)算和基于一次方程上的運(yùn)算共3 種運(yùn)算方式,相較于本文僅需調(diào)整Harary 圖參數(shù),可知本文的構(gòu)造算法運(yùn)算復(fù)雜度更優(yōu).

4 結(jié)論與展望

針對(duì)部分重復(fù)碼的有效修復(fù)問題,本文基于Harary圖生成樹構(gòu)造出了一種新型的部分重復(fù)碼.這種FRSH碼在構(gòu)造方面的優(yōu)勢(shì)在于參數(shù)選擇范圍較廣且運(yùn)算復(fù)雜度極低.在性能方面,實(shí)驗(yàn)結(jié)果表明,相較于現(xiàn)有的RS 碼和SRC,FRSH 碼在修復(fù)帶寬開銷、修復(fù)局部性等方面得到了更低的開銷,且改善了修復(fù)效率,并將故障節(jié)點(diǎn)的修復(fù)時(shí)間縮短;又與可達(dá)到類似性能的圖因子分解的部分重復(fù)碼在運(yùn)算復(fù)雜度方面進(jìn)行比較,得出本文的構(gòu)造算法運(yùn)算復(fù)雜度更優(yōu).