Degree Optimization of Batched Sparse Codes Using Outer Code Block Encoding
-
摘要:
为解决分批稀疏码（BATS 码）在现有外码分块编码方案下，由于外码随机分批而导致的数据重复译码及资源浪费问题，系统地研究基于外码分块编码方案的 BATS 码理论批次数优化与动态适应性问题. 首先，在已知丢包率的条件下，构建 BATS 码批次数消耗分析模型，并推导得出最优度值的计算方法，以此应对现有方案在计算理论批次数以及确定最小化批次数消耗的最优度值方面所面临的挑战；其次，针对信道丢包率未知的场景，提出一种基于强化学习的BATS码动态度优化方法，借助智能学习机制，在丢包率未知的情况下实时获取度值；最后，通过仿真实验对所构建的理论模型和提出的动态优化方法进行评估. 理论分析结果显示，所构建的基于外码分块的传输模型及其理论批次数计算公式，能够精准计算批次数消耗并确定最优度值. 仿真结果进一步证明，在丢包率未知的场景下，所提出的强化学习优化方案的平均批次数消耗低于固定度值方案，且在动态信道环境中能够保持良好的性能表现.
Abstract:To address the issues of repeated decoding and resource waste caused by random batch generation of the outer code in existing outer code block coding schemes for batched sparse (BATS) codes, the optimization of theoretical batch count and dynamic adaptability of BATS codes was systematically investigated based on the outer code block encoding scheme. First, under the condition of a known packet loss rate, a batch consumption analysis model for BATS codes was established, and an optimal degree value computation method was derived to tackle the challenges in existing schemes regarding theoretical batch count calculation and optimal degree value determination for minimizing batch count consumption. Second, for scenarios with unknown packet loss rates in the channel, a reinforcement learning-based dynamic degree optimization method for BATS codes was proposed, enabling real-time acquisition of degree values through an intelligent learning mechanism. Finally, simulation experiments were conducted to evaluate the theoretical model and the proposed dynamic optimization method. Simulation results have shown that the established transmission model based on outer code blocks and its batch count computation formula can be used to calculate batch consumption and determine the optimal degree distribution. Simulation results demonstrate that the proposed reinforcement learning-based optimization scheme achieves lower average batch count consumption than fixed-degree value schemes with unknown packet loss rates and maintains great performance in dynamic channel environments.
-
Key words:
- batched sparse (BATS) code /
- code block /
- transmission time /
- reinforcement learning
-
图 2 基于强化学习的BATS码度优化流程
Figure 2. Flowchart of degree optimization of BATS code based on reinforcement learning
图 3 丢包率为0.1时，理论计算值与仿真传输次数对比
Figure 3. Comparison between theoretically calculated value and simulated transmission times at packet loss rate of 0.1
图 4 丢包率为0.2时，理论计算值与仿真传输次数对比
Figure 4. Comparison between theoretically calculated value and simulated transmission times at packet loss rate of 0.2
图 5 跳数为3跳时，度值13～19下的理论传输次数
Figure 5. Theoretical transmission times with degree values of 13–19 and hops of 3
图 6 跳数为1跳时，度值15～22下的理论传输次数
Figure 6. Theoretical transmission times with degree values of 15–22 and hop of 1
表 1 传输次数仿真参数
Table 1. Simulation parameters of transmission times
仿真参数 取值 输入数据包数/个 100 批次大小/批次 32 数据包长度/bit 100 度值 16～19 蒙特卡洛仿真次数/次 1500 丢包率/% 0.1, 0.2 
下载: 导出CSV
表 2 基于度值粗调强化学习的BATS码传输仿真参数
Table 2. Simulation parameters for BATS code transmission based on degree value coarse-tuning reinforcement learning
仿真参数 取值 原始数据包数/个 100 传输网络的跳数/跳 3 丢包率/% 0.2 批次数/批次 32 数据包所含的比特数/bit 100 度值 1～32 奖赏折扣/% 0.9 更新步长 0.1 最大学习次数/次 200 贪心策略的贪心概率/% 0.1 反馈函数系数 10 门限参数 1.3
下载: 导出CSV
表 3 网络跳数为3跳时的Q表
Table 3. Q-table with network hops of 3
度值/个 度值减 1 度值不变 度值加 1 12 −∞ −∞ + ∞ 13 −∞ 0.0405 1.1195 14 0.5179 3.1447 7.0977 15 − 3.8233 − 0.0099 0.0189 16 0.4767 0.1405 1.4218 17 − 1.5722 − 0.0614 − 1.3744 18 2.7366 0.5664 − 2.5214 19 4.2853 1.1138 −∞ 20 + ∞ −∞ −∞
下载: 导出CSV
表 4 基于度值精调强化学习的BATS码传输仿真参数
Table 4. Simulation parameters for BATS code transmission based on degree value fine-tuning reinforcement learning
仿真参数 取值 原始数据包数/个 100 传输网络的跳数/跳 1 丢包率/% 0.2 批次数/批次 32 数据包所含的比特数/bit 100 度值 1～32 最大学习次数/次 30
下载: 导出CSV
表 5 网络跳数为1跳时第1次强化学习后的Q表
Table 5. Q-table after first reinforcement learning with network hop of 1
度值 度值减 1 度值不变 度值加 1 14 −∞ −∞ + ∞ 15 −∞ 0.1617 0.6505 16 0.2911 0.2470 2.5826 17 − 1.4226 0.0564 − 1.0785 18 1.2134 0.1452 − 1.2383 19 2.2049 0.3014 1.0891 20 − 0.9744 0.7888 − 0.3698 21 1.1663 0.2979 − 3.5123 22 5.4088 0.0458 −∞ 23 + ∞ −∞ −∞
下载: 导出CSV
表 6 网络跳数为1跳时度值精调强化学习后的Q表
Table 6. Q-table after degree value fine-tuning reinforcement learning with network hop of 1
当前度值 度值跳变为 17 度值跳变为 20 17 0.7007 1.3088 20 − 0.9443 − 0.3196
下载: 导出CSV
-
[1] CHOU P A, WU Y, JAIN K. Practical network coding[C]//Proceeding of the 41th Annual Allerton Conference on Communications, Controls and Computations. Monticello: IEEE, 2003: 1-10. [2] HO T, KOETTER R, MEDARD M, et al. The benefits of coding over routing in a randomized setting[C]//IEEE International Symposium on Information Theory. Yokohama: IEEE, 2003: 442. [3] JAGGI S, CASSUTO Y, EFFROS M. Low complexity encoding for network codes[C]//2006 IEEE International Symposium on Information Theory. Seattle: IEEE, 2006: 40-44. [4] SANDERS P, EGNER S, TOLHUIZEN L. Polynomial time algorithms for network information flow[C]// Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures. San Dieg: ACM, 2003: 286-294. [5] XU X L, ZENG Y, GUAN Y L, et al. Expanding-window BATS code for scalable video multicasting over erasure networks[J]. IEEE Transactions on Multimedia, 2018, 20(2): 271-281. doi: 10.1109/TMM.2017.2742699 [6] YANG J, SHI Z P, WANG C X, et al. Design of optimized sliding-window BATS codes[J]. IEEE Communications Letters, 2019, 23(3): 410-413. doi: 10.1109/LCOMM.2019.2895867 [7] WANG S H, LIU H, MA Z, et al. Precoded batched sparse codes transmission based on low-density parity-check codes[C]//2022 IEEE 95th Vehicular Technology Conference: (VTC2022-Spring). Helsinki: IEEE, 2022: 9860907.1-9860907.5. [8] WANG S H, LIU H, MA Z, et al. Chunked BATS codes under time-invariant and time-variant channels[C]//2022 IEEE 95th Vehicular Technology Conference (VTC2022-Spring). Helsinki: IEEE, 2022: 9860749.1- 9860749.5. [9] LUBY M G, MITZENMACHER M , SHOKROLLAHI M A. Analysis of random processes via AND/OR tree evaluations[C]//ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics. San Francisco: [s.n.], 1998: 364-373. [10] LUBY M. LT codes[C]//The 43rd Annual IEEE Symposium on Foundations of Computer Science. Vancouver: IEEE, 2002: 271-280. [11] YANG S H, YEUNG R W. BATS codes: theory and practice[M]. [S.l.]: Morgan & Claypool Publishers, 2017. [12] XU X L, GUAN Y L, ZENG Y, et al. Quasi-universal BATS code[J]. IEEE Transactions on Vehicular Technology, 2017, 66(4): 3497-3501. doi: 10.1109/TVT.2016.2594051 [13] YANG S H, YEUNG R W. Batched sparse codes[J]. IEEE Transactions on Information Theory, 2014, 60(9): 5322-5346. doi: 10.1109/TIT.2014.2334315 [14] YANG S H, YEUNG R W. BATS codes: theory and practice[M]. [S.l.]: Morgan & Claypool Publishers, 2017. [15] DIMAKIS A G, GODFREY P B, WU Y, et al. Network coding for distributed storage systems[C]//The 26th IEEE International Conference on Computer Communications. Anchorage: IEEE, 2007: 2000-2008. [16] CHACHULSKI S, JENNINGS M, KATTI S, et al. Trading structure for randomness in wireless opportunistic routing[J]. ACM SIGCOMM Computer Communication Review, 2007, 37(4): 169-180. doi: 10.1145/1282427.1282400 [17] WANG M A, LI B C. Network coding in live peer-to-peer streaming[J]. IEEE Transactions on Multimedia, 2007, 9(8): 1554-1567. doi: 10.1109/TMM.2007.907460 [18] KATTI S, RAHUL H, HU W J, et al. XORs in the air: practical wireless network coding[J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 497-510. doi: 10.1109/TNET.2008.923722 [19] CHOU P A, WU Y, JAIN K. Practical network coding[C]//Proceeding of the 41th Annual Allerton Conference on Communications, Controls and Computations, Monticello: IEEE, 2003: 1-10. [20] DUFFY D G. Advanced engineering mathematics[M]. New York: CRC Press, Inc. , 2022. [21] WATKINS C J C H. Learning from delayed rewards [D]. Cambridge: University of Cambridge, 1989. [22] 胡晶晶, 黄有方. 两个轴辐式网络协同建设的多层编码遗传算法[J]. 西南交通大学学报, 2020, 55(5): 971-979.HU Jingjing, HUANG Youfang. Multi-layer coded genetic algorithm with collaborative construction of two hub-and-spoke networks[J]. Journal of Southwest Jiaotong University, 2020, 55(5): 971-979. [23] 范平志, 周维曦. 高移动无线通信抗多普勒效应技术研究进展[J]. 西南交通大学学报, 2016, 51(3): 405-417. doi: 10.3969/j.issn.0258-2724.2016.03.001FAN Pingzhi, ZHOU Weixi. Advances in anti-Doppler effect techniques for high mobility wireless communications[J]. Journal of Southwest Jiaotong University, 2016, 51(3): 405-417. doi: 10.3969/j.issn.0258-2724.2016.03.001 [24] 周敬轩, 包卫东, 王吉, 等. 基于编-解码器结构的无人机群多任务联邦学习[J]. 西南交通大学学报, 2024, 59(4): 933-941.ZHOU Jingxuan, BAO Weidong, WANG Ji, et al. Multi-task federated learning for unmanned aerial vehicle swarms based on encoder-decoder architecture[J]. Journal of Southwest Jiaotong University, 2024, 59(4): 933-941. [25] 朱西平, 方旭明. 基于网络编码的无线多跳自组网连接性增强[J]. 西南交通大学学报, 2010, 45(6): 972-976.ZHU Xiping, FANG Xuming. Connectivity enhancement based on network coding for wireless multi-hop ad hoc networks[J]. Journal of Southwest Jiaotong University, 2010, 45(6): 972-976. -
下载:
点击查看大图
计量
- 文章访问数: 48
- HTML全文浏览量: 39
- PDF下载量: 7
- 被引次数: 0