二分图因子分解的部分重复码构造
余春雷1，2，华春1，2，王萃清1，赵金阳1
（1.四川文理学院智能制造学院，四川达州635000；2.政务数据安全达州市重点实验室，四川达州635002）
摘要：为了提高分布式存储系统的可靠性和修复效率，提出一种基于二分图的部分重复码构造算法。实验结果表明，与里所码以及简单再生码相比，基于二分图的部分重复码具有灵活选择参数的特性以及显著的降低了分布式存储的修复局部性、修复带宽开销。
关键词：二分图；分布式存储；数据修复；部分重复码
中图分类号：TP393文献标识码：A文章编号：2096-9759（2023）07-0068-03
Construction of fractional repetition codes based on bipartite graphs
YU Chunlei1,2,HUA Chun1,2,WANG Cuiqing1,ZHAO Jinyang1
(1.The Institute of Intelligent Manufacturing,Sichuan University of Arts and Science,Dazhou635000,China;
2.Intelligent Manufacturing Industry Technology Research Institute,Dazhou635000,China;
3.Key Laboratory of Government Data Security in Dazhou City,635002,China)
Abstract:In order to improve the reliability and repair efficiency of distributed storage systems,an algorithm for constructing fractional repetition based on bipartite graphs is proposed.The results of the study show that,compared with reed-solomon cod-es and simple regeneration codes,FRGF codes have the characteristics of flexible parameter selection and significantly reduce repair locality,repair bandwidth overhead and repair time.
Key words:Network coding;distributed storage;data repair;fractional repetition code
当今社会是一个互联网高速发展的时代[1]，如何保证数据的可靠性和稳定性出现在存储厂商的面前[2-3]。目前，大数据存储涉及介质、数据结构、数据连接控制等关键技术，存储机制正由集中式向分布式存储系统方向转变[4]。分布式存储对数据的存储采用的策略是复制策略和纠删码策略[5-6]。但复制策略存在的缺陷是存储开销大[6]，纠删码策略修复带宽开销[7]大都不能广泛推广到分布式存储系统中。
为了提高分布式存储系统的可靠性和修复效率，部分重复（FR，fractional repetition）码[7-8]的概念被提出了。外部最大距离可分（MDS，maximum distance separable）码[9]和内部重复码是FR码的构造算法的核心过程[10]。本文一种基于二分图因子分解的部分重复（FRBG，fractional repetition based on bipartite graphs）码的构造算法。在系统修复故障节点时，提高了故障节点修复效率，保障了数据的可靠性和稳定性。
1基础知识
1.1二分图的因子分解
设设G为任意r（r≥1）正则的二分图，二分图G包含一个完美匹配M1，因此G M1是（r1）正则的。若r≥2，则G M1包含完美匹配M2。依次推广，二分图G的边E（G）可被分为完美匹配的并，因此，任意r正则的二分图（r≥1）是可1因子分解的。
1.2部分重复码的构造
FR码采用的编码规则是双层编码，内层编码采用的是RS 码编码，然后经过对RS码编码生成
的个编码数据块复
制倍，外层编码
将倍的编码数据按照排列组合的方式存储于分布式存储系统的n个节点中，并且系统中每个节点存放d个数据块，则参数
满足如下关系：
nd
=（1）如图1所示，是FR码的编码构造过程
。
Copyright©博看网. All Rights Reserved.
68
69
具体地，利用一个K 4，4的4正则的完全二分图构造FR 码。假
设=3，在二分图K 4，4部分因子分解中任选3个因子进行构造，这里我们选择因子F 1，F 2，F 4，然后对F 的边进行依次编号为e i （l ≤i ≤12）
，如图2所示
。图2K 4，4的因子分解
然后根据公式（2）求出因子矩阵m 1
如下：
（3）
把矩阵m 1的每个横向量当作FR 码的一个存储节点N i
（l ≤i ≤12），存储标记为1对应的数据块d i （l ≤j ≤8）。如图4所示，构造的FR 码的重复度=3
正则匹配关键词。
图5单节点故障修复局部性
3.3修复复杂度
对于（n ，k ）RS 码、（n ，k ，f ）SRC 、FRBG 码三种编码的修复
复杂度进行分析。RS 码需要经过k 2-1次有限域加法运算跟k 2+k 次有限域乘法运算才能修复故障节点时，因此RS 码在修复单节点的故障时它的修复复杂度为O （2k 2+k -1）。对于SRC ，系统需要执行（f -1）（f+1）次异或运算，所以SR
C 的修复复杂
度为O （f 2
-1）。对于FRBG 码，直接通过复制数据就可以进行修复，不需要经过其他复杂运算，因此FRBG 码相比于RS 码和SRC 具有较低修复复杂度，能够快速修复故障节点，降低修复时间。
Copyright ©博看网. All Rights Reserved.
3.4纠错能力比较
对于（n，k）RS码、(n，k，f）SRC、FRBG码三种编码的纠错能力进行分析，（n，k）RS码，他的纠错能力为n-k。对于（n，k，f）SRC，因为其仍保持了MDS（n，k）性质，即可以保证利用n个存储节点中的任意k个节点上存储的数据块，能够恢复出原始数据，因此（n，k，f）SRC的纠错能力也是n-k。对于FRBG码，由外部最大距离可分码和内部重复码构造，因此他的纠错能力跟外部最大距离可分码一样。
4结语
本文根据二分图的因子分解提出一种FRBG码能够快速修复故障节点，保障了分布式存储系统的可靠性。由于二分图因子分解简单灵活，所以FRBG码构造具有多样性，具有可扩展性。同时，在修复故障节点时，FRBG相较于传统的部分重复码，在修复局部性、修复复杂度、修复带宽开销都有较大的性能提升，更加具有发展的前景和应用背景。
参考文献：
[1]SIDDIQA A,AHMAD K,and ABDULLAH G.Big data s
torage technologies:a survey."Frontiers of Information Tech-nology&Electronic Engineering,2017,18(8):1040-1070. [2]MAZUMDAR S,SEYBOLD D,KRITIKOS K,et al.A survey
on data storage and placement methodologies for cloud-big data ecosystem[J].Journal of Big Data,2019,6(1):1-37.[3]余春雷，王娥，刘星等.图因子分解的故障节点快速修复[J].
计算机系统应用,2023,32(02):394-399.
[4]YANG Y,ZHENG X,GUO W,et al.Privacy-preserving
smart IoT-based healthcare big data storage and self-adap-tive access control system[J].Information Sciences,2019, 479:567-592.
[5]LEE O T,AKASH G J,KUMAR S D M,et al.Storage node
allocation methods for erasure code-based cloud storage sys-tems[J].Arabian Journal for Science and Engineering,2019, 44(11):9127-9142.
[6]余春雷，王静，王秘，等.图因子分解的部分重复码构造[J].
中国科技论文,2019,14(11):1260-1264.
[7]VAISHAMPAYAN V A.Lattice Erasure Codes of Low Rank
with Noise Margins[C]//2018IEEE International Symposium on Information Theory(ISIT).IEEE,2018:961-965.
[8]余春雷.分布式存储系统中数据存储研究[D].西安：长安
大学,2020.
[9]杨佳蓉，王娥，李静辉等.最优局部修复码的构造[J].计算机
测量与控制,2023,31(02):249-255.
[10]ZHU B,ZHANG S,WANG W.Expandable Fractional Repe
tition Codes for Distributed Storage Systems[C]//2021IEEE Information Theory Workshop(ITW).IEEE,2021:1-5.
（上接第67页）更有效和准确地解决LSMOPs。本文将MOEA/ ADA算法与四种大规模多目标进化算法MOEA/DV A、CC
GDE3、LMEA、S3CMAES在多个测试函数上进行比较以测试算法的有效性，并使用IGD指数评估算法的卓越性。实验结果表明，该算法可以很好地解决许多复杂的大规模多目标优化问题，是一种较为智能且优良的算法。
参考文献：
[1]闫世瑛.基于演化计算的大规模多目标优化算法研究[D].
江南大学,2022.DOI:10.27169/dki.gwqgu.2022.000884.
[2]王丽萍，林豪，潘笑天，俞维.基于决策变量交互识别的多目
标优化算法[J].浙江工业大学学报,2021,49(04):355-367. [3]季伟东，岳玉麒，王旭，林平.基于降维和聚类的大规模多目
标自然计算方法[J].系统仿真学报,2023,35(01):41-56.DOI:
10.16182/j.issn1004731x.joss.21-0667.
[4潘嘉敏.基于混合变量动态分组的大规模多目标进化算法[J].长江信息通信,2022,35(11):36-38.
[5]谢承旺，龙广林，程文旗，郭华.大规模多目标进化优化算法
研究进展[J].广西科学,2020,27(06):600-608.DOI:10.13656/
标粒子优化算法研究[J].计算机学报,2016,39(12):2598-2613.
[7]倪晓晔.基于协同进化算法解决大规模优化和多目标优
化问题的研究[D].华南理工大学,2017.
[8]兰丽尔，孙超利，何小娟，谭瑛.求解大规模多目标问题的改
进粒子算法[J].太原科技大学学报,2020,41(04):249-256.
[9]Antonio L M,Coello C.Use of cooperative coevolution
for solving large scale multiobjective optimization problems
[C]//Evolutionary Computation.IEEE,2013.
[10]Xiaoliang Ma,Fang Liu0001,Yutao Qi,Xiaodong Wang,Lin-
gling Li,Licheng Jiao,Minglei Yin,Maoguo Gong.A Multi-objective Evolutionary Algorithm Based on Decision Vari-able An
alyses for Multiobjective Optimization Problems With Large-Scale Variables.[J].IEEE Trans.Evolutionary Computation,2016,20(2).
[11]Zhang Xingyi,Tian Ye,Cheng Ran,Jin Yaochu.A Decision
Variable Clustering-Based Evolutionary Algorithm for Lar-ge-Scale Many-Objective Optimization[J].IEEE Transac-tions on Evolutionary Computation,2018,22(1)
.
Copyright©博看网. All Rights Reserved.
70

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。