适用于线性网络编码关键路径的实时性算法

• 作者: 张立炜 韩晓冬 高飞
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 关键路径 代数结构 交换环 矩阵乘法 线性网络编码
• 年，卷（期）: 2020,（9）
• 所属期刊栏目: 计算机网络
• 页码范围: 232-237
• 页数: 6页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.11896/jsjkx.190800023

摘要

如今,人类社会存储和交换的信息总量呈几何级数飞速增长,数据传输的吞吐量和实时性亟待提升.然而,现有的网络编码研究专注于提升吞吐量,忽略了实时性对大数据网络多路径传输性能的重大影响.为此,文中针对线性网络编码的最快到达问题,提出一种矩阵优化相乘的关键路径算法,以提高算法的实时性.具体地,使用抽象代数分析关键路径算法,构造了关键路径的交换环代数,并证明了最优子结构性质.仿真结果显示,随着网络节点个数n的增加,基于Strassen思想优化的关键路径算法能够极大地降低计算复杂度,成功将时间复杂度降至O(n 2.81 lgn),缩短了传播时延,提高了数据传输的实时性.当n>6时,相比基于重复平方关键路径算法,基于Strassen关键路径算法的时间开销的增长速率明显更低;特别地,当n=12时,基于Strassen关键路径算法的计算量约是基于重复平方关键路径算法的2/3,而其所需的时间开销约为后者的1/2.