无速率编码中度分布的研究和发展

doi:10.11959/j.issn.1000-0801.2022268

电信科学 ›› 2022, Vol. 38 ›› Issue (10): 1-19.doi: 10.11959/j.issn.1000-0801.2022268

• 综述 • 下一篇

无速率编码中度分布的研究和发展

乔越¹^,², 伏玉笋²^,³^,⁴, 原牧云¹^,², 唐金辉²

¹ 上海交通大学宁波人工智能研究院，浙江宁波 315000
² 上海交通大学电子信息与电气工程学院，上海 200240
³ 系统控制与信息处理教育部重点实验室，上海 200240
⁴ 上海工业智能管控工程技术研究中心，上海 200240

修回日期:2022-10-08 出版日期:2022-10-20 发布日期:2022-10-01
作者简介:乔越（1999- ），男，上海交通大学硕士生，主要研究方向为无速率编码、网络编码及其在工业中的应用等
伏玉笋（1972- ），男，博士，上海交通大学助理研究员，主要研究方向为无线通信与系统、无线网联智能系统、工业互联网与安全可信、智能制造等
原牧云（1997- ），男，上海交通大学硕士生，主要研究方向为无速率编码、网络编码及其在工业中的应用等
唐金辉（1999- ），男，上海交通大学硕士生，主要研究方向为工业通信系统与安全可信
基金资助:
国家重点研发计划项目(2019YFB1705703);宁波市重大科技任务攻关项目(2021Z022)

Research and development of degree distribution in the rateless code

Yue QIAO¹^,², Yusun FU²^,³^,⁴, Muyun YUAN¹^,², Jinhui TANG²

¹ Ningbo Artificial Intelligence Institute of Shanghai Jiao Tong University, Ningbo 315000, China
² School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
³ Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai 200240, China
⁴ Shanghai Engineering Research Center of Intelligent Control and Management, Shanghai 200240, China

Revised:2022-10-08 Online:2022-10-20 Published:2022-10-01
Supported by:
The National Key Research and Development Program of China(2019YFB1705703);The Major Scientific and Technological Research Program of Ningbo(2021Z022)

摘要/Abstract

摘要：

无速率编码作为一种纠删码，在减少反馈重传的同时也具有码率灵活、编译码简单的特性，在许多领域都有广阔的应用前景。度分布作为无速率编码设计的基础，对无速率编码的性能有至关重要的影响。随着无速率编码的广泛应用，度分布的设计也需要随着场景和需求的变化进行优化。首先论述了无速率编码的发展与应用，从几种经典的无速率编码和度分布开始，详细地从应用场景、优化目标以及现有优化方法 3 个角度，对目前无速率编码中度分布的研究和发展进行了总结与分析。最后，对无速率编码和度分布的发展应用趋势进行了分析与展望。

关键词: 无速率编码, 喷泉码, 度分布, 网络编码, 多路径

Abstract:

As a kind of deletion coding technology, the rateless code reduces feedback retransmission and has the characteristics of flexible bit rate and simple compilation code, which has broad application prospects in many fields.As the basis of rateless code design, degree distribution has a crucial impact on the performance of the rateless code With the wide application of the rateless code, the design of degree distribution also needs to change with changes in scenarios and needs.Firstly, the development and application of the rateless code were discussed.Starting with several classical rateless codes and degree distributions, the current research and development of the degree distribution were summarized and analyzed from three perspectives of application scenarios, optimization targets and existing optimization methods.Finally, the development and application trend of rateless codes and degree distribution were discussed.

Key words: rateless code, fountain code, degree distribution, network coding, multipath

中图分类号:

TN911

乔越, 伏玉笋, 原牧云, 唐金辉. 无速率编码中度分布的研究和发展[J]. 电信科学, 2022, 38(10): 1-19.

Yue QIAO, Yusun FU, Muyun YUAN, Jinhui TANG. Research and development of degree distribution in the rateless code[J]. Telecommunications Science, 2022, 38(10): 1-19.

图/表 4

图1

表1

图2

图3

参考文献 69

[1]	LUBY M G , . LT codes[C]// Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 2002: 271-280.
[2]	SHOKROLLAHI A . Raptor codes[J]. IEEE Transactions on Information Theory, 2006,52(6): 2551-2567.
[3]	SHIRVANIMOGHADDAM M , LI Y H , VUCETIC B . Adaptive analog fountain for wireless channels[C]// Proceedings of 2013 IEEE Wireless Communications and Networking Conference. Piscataway:IEEE Press, 2013: 2783-2788.
[4]	YANG S H , YEUNG R W . Batched sparse codes[J]. IEEE Transactions on Information Theory, 2014,60(9): 5322-5346.
[5]	LáZARO F , LIVA G , BAUCH G . Inactivation decoding of LT and raptor codes:analysis and code design[J]. IEEE Transactions on Communications, 2017,65(10): 4114-4127.
[6]	徐大专, 许生凯, 华洁 ,等. 数字喷泉码度分布优化设计的最新研究进展[J]. 数据采集与处理, 2015,30(4): 733-746.
	XU D Z , XU S K , HUA J ,et al. Recent progress on optimization design of degree distributions in digital fountain codes[J]. Journal of Data Acquisition and Processing, 2015,30(4): 733-746.
[7]	MACKAY D J C . Fountain codes[J]. IEE Proceedings - Communications, 2005,152(6): 1062.
[8]	黄靖轩, 费泽松, 李欢 . 无速率编码及其应用综述[J]. 无线电通信技术, 2020,46(1): 44-54.
	HUANG J X , FEI Z S , LI H . Overview of rateless codes and their applications[J]. Radio Communications Technology, 2020,46(1): 44-54.
[9]	LUBY M G , MITZENMACHER M , SHOKROLLAHI M A . Analysis of random processes via AND-OR tree evaluation[C]// Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms.[S.l.:s.n.], 1998.
[10]	ETESAMI O , SHOKROLLAHI A . Raptor codes on binary memoryless symmetric channels[J]. IEEE Transactions on Information Theory, 2006,52(5): 2033-2051.
[11]	TANNER R . A recursive approach to low complexity codes[J]. IEEE Transactions on Information Theory, 1981,27(5): 533-547.
[12]	3GPP. Multimedia broadcast/multicast service(MBMS); protocols and codecs:TS 26.346 V7.2.0[S]. 2006.
[13]	ETSI T S . IP datacast over DVB-H:content delivery protocols:102 472 v1.2.1[S]. 2006.
[14]	JEON S Y , AHN J H , LEE T J . Reliable broadcast using limited LT coding in wireless networks[J]. IEEE Communications Letters, 2016,20(6): 1187-1190.
[15]	BORKOTOKY S S , PURSLEY M B . Fountain-coded broadcast distribution in multiple-hop packet radio networks[J]. IEEE/ACM Transactions on Networking, 2019,27(1): 29-41.
[16]	PALMA V , MAMMI E , VEGNI A M ,et al. A fountain codes-based data dissemination technique in vehicular Ad-hoc networks[C]// Proceedings of 2011 11th International Conference on ITS Telecommunications. Piscataway:IEEE Press, 2011: 750-755.
[17]	ABDULLAH N F , DOUFEXI A , PIECHOCKI R J . Raptor codes-aided relaying for vehicular infotainment applications[J]. IET Communications, 2013,7(18): 2064-2073.
[18]	GAO Y M , XU X L , GUAN Y L ,et al. V2X content distribution based on batched network coding with distributed scheduling[J]. IEEE Access, 2017(6): 59449-59461.
[19]	ANGLANO C , GAETA R , GRANGETTO M . Exploiting rateless codes in cloud storage systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015,26(5): 1313-1322.
[20]	LU H F , FOH C H , WEN Y G ,et al. Delay-optimized file retrieval under LT-based cloud storage[J]. IEEE Transactions on Cloud Computing, 2017,5(4): 656-666.
[21]	OKPOTSE T , YOUSEFI S . Systematic fountain codes for massive storage using the truncated Poisson distribution[J]. IEEE Transactions on Communications, 2019,67(2): 943-954.
[22]	段文雪, 胡铭, 周琼 ,等. 云计算系统可靠性研究综述[J]. 计算机研究与发展, 2020,57(1): 102-123.
	DUAN W X , HU M , ZHOU Q ,et al. Reliability in cloud computing system:a review[J]. Journal of Computer Research and Development, 2020,57(1): 102-123.
[23]	PUDUCHERI S , KLIEWER J , FUJA T E . The design and performance of distributed LT codes[J]. IEEE Transactions on Information Theory, 2007,53(10): 3740-3754.
[24]	HUSSAIN I , XIAO M , RASMUSSEN L K . Buffer-based distributed LT codes[J]. IEEE Transactions on Communications, 2014,62(11): 3725-3739.
[25]	SUN L , REN P Y , DU Q H ,et al. Fountain-coding aided strategy for secure cooperative transmission in industrial wireless sensor networks[J]. IEEE Transactions on Industrial Informatics, 2016,12(1): 291-300.
[26]	YI B S , XIANG M , HUANG T Q ,et al. Data gathering with distributed rateless coding based on enhanced online fountain codes over wireless sensor networks[J]. AEU - International Journal of Electronics and Communications, 2018,92: 86-92.
[27]	YUE J , XIAO M , PANG Z B . Distributed fog computing based on batched sparse codes for industrial control[J]. IEEE Transactions on Industrial Informatics, 2018,14(10): 4683-4691.
[28]	SEVERINSON A , AMAT A G I , ROSNES E . Block-diagonal and LT codes for distributed computing with straggling servers[J]. IEEE Transactions on Communications, 2019,67(3): 1739-1753.
[29]	SANDELL M , RAZA U . Application layer coding for IoT:benefits,limitations,and implementation aspects[J]. IEEE Systems Journal, 2019,13(1): 554-561.
[30]	YUAN M Y , FU Y S , QIAO Y ,et al. Rateless codes for reliable and secure packet transmission in industrial control systems[C]// Proceedings of 2021 China Automation Congress (CAC). Piscataway:IEEE Press, 2021: 6376-6381.
[31]	AGHA K A , KADI N , STOJMENOVIC I . Fountain codes with XOR of encoded packets for broadcasting and source independent backbone in multi-hop networks using network coding[C]// Proceedings of IEEE 69th Vehicular Technology Conference. Piscataway:IEEE Press, 2009: 1-5.
[32]	SEJDINOVIC D , PIECHOCKI R J , DOUFEXI A . AND-OR tree analysis of distributed LT codes[C]// Proceedings of 2009 IEEE Information Theory Workshop on Networking and Information Theory. Piscataway:IEEE Press, 2009: 261-265.
[33]	ZENG M , CALDERBANK R , CUI S G . On design of rateless codes over dying binary erasure channel[J]. IEEE Transactions on Communications, 2012,60(4): 889-894.
[34]	TSAI P C , CHEN C M , CHEN Y P . A novel evaluation function for LT codes degree distribution optimization[C]// Proceedings of 2014 IEEE Congress on Evolutionary Computation. Piscataway:IEEE Press, 2014: 3030-3035.
[35]	NGUYEN T D , YANG L L , HANZO L . Systematic Luby transform codes and their soft decoding[C]// Proceedings of 2007 IEEE Workshop on Signal Processing Systems. Piscataway:IEEE Press, 2007: 67-72.
[36]	WIBERG N . Codes and decoding on general graphs[D]. Linkoping:Linkoping University, 1996.
[37]	PAUL I J L , RADHA S , RAJA J . Studies on the suitability of LT codes with modified degree distribution (MDD) for fading channels[C]// Proceedings of 2014 International Conference on Advances in Computing,Communications and Informatics (ICACCI). Piscataway:IEEE Press, 2014: 1764-1769.
[38]	LIAU A , YOUSEFI S , KIM I M . Binary soliton-like rateless coding for the Y-network[J]. IEEE Transactions on Communications, 2011,59(12): 3217-3222.
[39]	LIAU A , KIM I M , YOUSEFI S . Improved low-complexity soliton-like network coding for a resource-limited relay[J]. IEEE Transactions on Communications, 2013,61(8): 3327-3335.
[40]	SHAO H Q , XU D Z , ZHANG X F . Asymptotic analysis and optimization for generalized distributed fountain codes[J]. IEEE Communications Letters, 2013,17(5): 988-991.
[41]	CUI Y , WANG L , WANG X ,et al. FMTCP:a fountain code-based multipath transmission control protocol[J]. IEEE/ACM Transactions on Networking, 2015,23(2): 465-478.
[42]	LIMMANEE A , HENKEL W . A cooperative scheme for shaping degree distribution of LT-coded symbols in network coding multicast[C]// Proceedings of 2010 International ITG Conference on Source and Channel Coding (SCC). Piscataway:IEEE Press, 2010: 1-6.
[43]	THOMOS N , FROSSARD P . Degree distribution optimization in Raptor network coding[C]// Proceedings of 2011 IEEE International Symposium on Information Theory Proceedings. Piscataway:IEEE Press, 2011: 2736-2740.
[44]	NESSA A , KADOCH M . Joint network channel fountain schemes for machine-type communications over LTE-advanced[J]. IEEE Internet of Things Journal, 2016,3(3): 418-427.
[45]	HYYTIA E , TIRRONEN T , VIRTAMO J . Optimal degree distribution for LT codes with small message length[C]// Proceedings of IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2007: 2576-2580.
[46]	MAATOUK G , SHOKROLLAHI A . Analysis of the second moment of the LT decoder[C]// Proceedings of 2009 IEEE International Symposium on Information Theory. Piscataway:IEEE Press, 2009: 2326-2330.
[47]	YEN K K , LIAO Y C , CHEN C L ,et al. Modified robust soliton distribution (MRSD) with improved ripple size for LT codes[J]. IEEE Communications Letters, 2013,17(5): 976-979.
[48]	戴新颖, 王建萍 . 基于输出可译集的LT码联合度分布优化[J]. 系统工程与电子技术, 2020,42(3): 727-732.
	DAI X Y , WANG J P . Optimization of combined degree distribution of LT codes based on output ripple size[J]. Systems Engineering and Electronics, 2020,42(3): 727-732.
[49]	郑志国, 侯登峰 . 基于可译集大小的 LT 码编码算法的改进[J]. 电视技术, 2011,35(5): 13-16.
	ZHENG Z G , HOU D F . Improvement of LT encoding algorithm based on ripple size[J]. Video Engineering, 2011,35(5): 13-16.
[50]	RENSEN J H S , POPOVSKI P , OSTERGAARD J . Design and analysis of LT codes with decreasing ripple size[J]. IEEE Transactions on Communications, 2012,60(11): 3191-3197.
[51]	YEN K K , LIAO Y C , CHANG H C . Design of LT code degree distribution with profiled output ripple size[C]// Proceedings of 2015 IEEE Workshop on Signal Processing Systems (SiPS). Piscataway:IEEE Press, 2015: 1-6.
[52]	雷维嘉, 张梦, 谢显中 . 基于度分布合并和可译集优化的 LT码度分布设计方案[J]. 电子学报, 2015,43(4): 800-805.
	LEI W J , ZHANG M , XIE X Z . A design scheme for LT codes degree distribution by combining degree distributions and optimizing ripple size[J]. Acta Electronica Sinica, 2015,43(4): 800-805.
[53]	ZHANG M , LEI W J , XIE X Z . Combined degree distribution:a simple method to design the degree distribution of fountain codes[C]// Proceedings of 2013 IEEE Third International Conference on Information Science and Technology. Piscataway:IEEE Press, 2013: 1089-1092.
[54]	任鹏, 相征 . LT 码中一种新的开关度分布[J]. 西安电子科技大学学报, 2015,42(5): 43-47.
	REN P , XIANG Z . New switch degree distribution for the LT code[J]. Journal of Xidian University, 2015,42(5): 43-47.
[55]	姚渭箐, 胡凡 . 基于IBED和仿生算法的LT码度分布设计[J]. 电子学报, 2019,47(2): 428-433.
	YAO W Q , HU F . The design of degree distribution for LT codes based on IBED and bionic algorithm[J]. Acta Electronica Sinica, 2019,47(2): 428-433.
[56]	YAO W Q , YI B S , HUANG T Q ,et al. Poisson robust soliton distribution for LT codes[J]. IEEE Communications Letters, 2016,20(8): 1499-1502.
[57]	龚赟, 王俊义 . 一种用于LT码的新型联合度分布设计方法[J]. 桂林电子科技大学学报, 2017,37(5): 355-360.
	GONG Y , WANG J Y . A design method of novel combined degree distribution for LT code[J]. Journal of Guilin University of Electronic Technology, 2017,37(5): 355-360.
[58]	敖珺, 卢亚军, 马春波 . 基于短码长的喷泉码度分布设计[J]. 计算机与数字工程, 2015,43(12): 2101-2105.
	AO J , LU Y J , MA C B . Fountain codes degree distribution design based on short code length[J]. Computer ＆ Digital Engineering, 2015,43(12): 2101-2105.
[59]	ZAO J K , HORNANSKY M , DIAO P L . Design of optimal short-length LT codes using evolution strategies[C]// Proceedings of 2012 IEEE Congress on Evolutionary Computation. Piscataway:IEEE Press, 2012: 1-9.
[60]	李杰 . 无线传输中短码长喷泉码的度分布优化算法[J]. 电讯技术, 2016,56(8): 900-905.
	LI J . A degree distribution optimization algorithm for small size fountain codes in wireless transmission[J]. Telecommunication Engineering, 2016,56(8): 900-905.
[61]	YUAN L , DENG K Y , LI H A . Design of finite-length precoded EWF codes for scalable video streaming[J]. Wireless Personal Communications, 2017,97(3): 4111-4128.
[62]	BEIMEL A , DOLEV S , SINGER N . RT oblivious erasure correcting[J]. IEEE/ACM Transactions on Networking, 2007,15(6): 1321-1332.
[63]	JIA D , FEI Z S , SHANGGUAN C L ,et al. LT codes with limited feedback[C]// Proceedings of 2014 IEEE International Conference on Computer and Information Technology. Piscataway:IEEE Press, 2014: 669-673.
[64]	HAGEDORN A , AGARWAL S , STAROBINSKI D ,et al. Rateless coding with feedback[C]// Proceedings of IEEE INFOCOM 2009. Piscataway:IEEE Press, 2009: 1791-1799.
[65]	AGARWAL S , HAGEDORN A , TRACHTENBERG A . Adaptive rateless coding under partial information[C]// Proceedings of 2008 Information Theory and Applications Workshop. Piscataway:IEEE Press, 2008: 5-11.
[66]	牛芳琳, 李宝明, 陈付亮 ,等. 一种改进的基于部分信息喷泉码度分布设计[J]. 电子学报, 2016,44(2): 295-300.
	NIU F L , LI B M , CHEN F L ,et al. The improved degree distribution for rateless code under partial information[J]. Acta Electronica Sinica, 2016,44(2): 295-300.
[67]	SAVCHENKO Y , LIU Y . Optimizing degree distributions of LT-based codes with deep reinforcement learning[C]// Proceedings of IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops. Piscataway:IEEE Press, 2019: 228-233.
[68]	HUANG L C , ZHANG H Z , LI R ,et al. AI coding:learning to construct error correction codes[J]. IEEE Transactions on Communications, 2020,68(1): 26-39.
[69]	宋鑫, 倪淑燕, 张喆 ,等. 面向不等差错保护的低误码平台LT编码算法[J]. 通信学报, 2022,43(6): 85-97.
	SONG X , NI S Y , ZHANG Z ,et al. Low error floor LT coding algorithm for unequal error protection[J]. Journal on Communications, 2022,43(6): 85-97.

应用场景	具体应用	文献
广播通信	Raptor码及其改进方案在蜂窝移动通信中的多媒体广播与多播	[12]
	Raptor码及其改进方案在DVB-H中的应用	[13]
	有反馈的二次广播下LT码度分布设计	[14]
	无速率编码在多跳无线网络数据分发中的应用	[15]
汽车通信	LT码在车载自组织网络中的应用	[16]
	Raptor码在汽车通信场景中的应用	[17]
	BATS码在汽车通信数据分发中的应用	[18]
存储	LT码在云存储系统中的应用	[19]
	在基于LT码的存储系统中如何优化检索方式以降低时延	[20]
	LT码在分布式存储系统中的应用	[21]
	纠删码在存储系统容错中的应用	[22]
无线传感器	分布式LT码在无线传感器网络中的应用	[23]
	利用缓存存储部分接收符号参与编码，降低最大度值的限制	[24]
	无线传感器网络中基于无速率编码的安全协作传输	[25]
	OFC在无线传感器网络中用于数据收集	[26]
分布式计算	BATS码在分布式计算系统中的应用	[27]
	使用失活译码器的LT码在分布式计算系统中的应用	[28]
物联网	将喷泉码作为物联网中的应用层编码	[29]
	工业环境下有限码长对喷泉码的影响	[30]

无速率编码中度分布的研究和发展

Research and development of degree distribution in the rateless code

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 69

相关文章 15

Metrics

推荐阅读 0

[1]	王士恒, 刘恒, 唐林, 苏金领, 张瑞琦. 时变信道下线性网络分批稀疏码秩分布研究[J]. 电信科学, 2022, 38(5): 64-74.
[2]	时书锋, 于游洋. 多接入、无线、有线融合架构演进及流量调度机制[J]. 电信科学, 2022, 38(4): 146-155.
[3]	邵鹏飞,赵燕伟,方朝曦. 一种基于散列邻域搜索网络编码的机会中继重传方法[J]. 电信科学, 2016, 32(4): 9-16.
[4]	杨延平,陈巍,可珂,李鸥. 异构协同无线网络的多向中继技术：从理论到实践[J]. 电信科学, 2015, 31(9): 1-10.
[5]	邵鹏飞,赵燕伟,吴耀辉,姚信威. 多播网络中基于机会网络编码改进的重传方法[J]. 电信科学, 2015, 31(4): 98-105.
[6]	邓单,赵明,简贵胄. 网络编码系统中基于天线选择的安全传输技术研究[J]. 电信科学, 2015, 31(2): 69-74.
[7]	张伟,张玲华. 基于潜在博弈的多源多跳无线传感器网络流量分配算法[J]. 电信科学, 2015, 31(2): 75-79.
[8]	陈晓华,李春芝,陈良育,曾振柄. 虚拟网络映射最小费用流模型及算法[J]. 电信科学, 2014, 30(6): 90-94.
[9]	张冬梅,马文峰,孙保明,徐友云,益晓新. 协同融合泛在网传输试验平台的设计与实现[J]. 电信科学, 2013, 29(2): 77-83.
[10]	娄路. 基于E-MBMS的大范围动态交通信息发布方法研究[J]. 电信科学, 2012, 28(5): 120-126.
[11]	张小弟,樊平毅. 一种改善频谱利用率的新式混合非对称喷泉映射策略[J]. 电信科学, 2012, 28(3): 57-61.
[12]	谢满德,张国萍. XSeluge:一个基于网络编码的安全在线代码分发算法[J]. 电信科学, 2012, 28(11): 74-80.
[13]	葛杨,徐名海,迟欢. 关于传输虚拟化中数据分组乱序问题的研究[J]. 电信科学, 2012, 28(10): 80-87.
[14]	吴晓丹,秦雅娟. 流与路径绑定的并行多路径SCTP的设计与实现[J]. 电信科学, 2011, 27(8): 58-62.
[15]	袁涛,谢坚戈,鲍园,杨亮. 复数域网络编码中最大似然解码算法的改进[J]. 电信科学, 2011, 27(12): 44-47.