利索能及
我要发布
收藏
专利号: 2020101632470
申请人: 长安大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-06-16
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.基于Harary图生成树的部分重复码的构造方法,其特征在于,包括以下步骤:

步骤1:将原始文件分成i个原始数据块,对i个原始数据块进行(n,i)MDS编码,得到n个编码块C1,C2,…,Cn,其中,n、i为正整数且i

步骤2:建立包括m个顶点和节点度为k的Harary图Hk,m,用1,2,…,m沿顺时针方向依次对Harary图的m个顶点编号,其中,k和m均为正整数,且k为偶数,m与n的个数相等,每个顶点存储与其编号相同的编码块;

步骤3:以Harary图的1号顶点为起始顶点得出图Hk,m的第一个生成树G,生成树G中的任一顶点为v,并将所述的第一个生成树G中的顶点按离心率分为a个组,所述的组中包含G中顶点的离心率相同,令1至a个组分别对应1至a个节点,每个节点s存有按编号从小到大的顺序排列的顶点所存储的编码块,得到所述的第一生成树的a个节点,其中,1≤v≤m,a≥1;

步骤4:根据部分重复码的重复度ρ更换起始顶点,重复ρ-1次步骤3,最终获得ρ个生成树的a×ρ个节点,共存有ρ×m个编码块,完成部分重复码的构造,其中,ρ>1。

2.如权利要求1所述的基于Harary图生成树的部分重复码的构造方法,其特征在于,步骤3中以Harary图的1号顶点为起始顶点得出图Hk,m的第一个生成树G的构建方法为:步骤3.1:画出边(1,v+1)和(1,m-v+1),其中,v表示生成树G中的顶点编号,步骤3.2:画出边(m-p+1,m-p-j+1)和(m-p-j+1,m-p-2j+1),…直到形成m-p+1到1的路径,其中p和j为间隔参数,步骤3.3,重复步骤3.2,画出边(m-q+1,m-q-j+1)和(m-q-j+1,m-q-2j+1),…当存在从m-q+1到1的路径时停止,否则转至步骤3.1,其中,q为间隔参数,q=p+1。

3.基于Harary图生成树的部分重复码的系统,其特征在于,包括构造模块和读取模块;

所述的构造模块用于执行权利要求1~2任一所述的基于Harary图生成树的部分重复码的构造方法;

所述的读取模块用于读取构造模块中的编码块。

4.故障节点修复方法,其特征在于,按照权利要求1或2任一所述的基于Harary图生成树的部分重复码的构造方法,将包含n个编码块的原始文件分别存储到分布式存储系统的a×ρ个节点中,共存有ρ×m个编码块,当某单节点发生故障时,从a×ρ-1个存活节点中采集编码块,并将采集到的编码块传送给新节点,完成单节点故障的修复;

当多个节点发生故障时,从a×ρ-1个存活节点中采集编码块,并将采集到的编码块传送给多个新节点,完成任多个节点故障的修复。