面向组通信的网络编码优化构造及其相关技术研究

论文摘要

随着计算机技术、网络技术的快速发展,多点接收数据的通信需求日益增加。组播通信技术是实现这类数据传输的最佳通信方式。网络编码技术的诞生为组播通信方式提供了一个新的平台,面向组播通信的网络编码技术成为一个令人关注的研究热点。网络编码是一种新型的数据传输技术,与传统的路由传输技术相比,中间节点不仅能进行信息转发和复制,还可以进行信息编码。网络编码能提高网络的传输性能,在提升网络的吞吐率、实现网络的负载均衡、增加网络的鲁棒性与安全性等方面具有优势,但因节点需要编码或解码,则数据传输过程中也增加了编码运算代价。采用网络编码实现组播通信的关键是构造编码方案,而编码方案完全决定了网络的吞吐率和编码运算代价。显然,提高网络的吞吐率、降低编码运算代价对基于网络编码的组播数据传输具有重要的意义,它们是构造网络编码方案的两个重要目标。从而面向组播通信的网络编码优化构造研究是一个具有实际意义的研究课题。论文在已有研究的基础上进一步拓展了这个领域的研究内容,基于以上提出的两个目标,其研究内容主要表现在以下三个方面：1)未知网络拓扑环境下单源组播网络编码优化构造研究；2)网络编码运算代价与环境参数(伽罗华域,组播率和数据块长)间的关系研究；3)多源组播网络编码优化构造研究。首先提出了不同组播率下线性网络编码的导出与扩展技术,结合随机线性网络编码方法,推导出了几个重要的性质,这些性质有助于运用线性网络编码技术实现组播连接,并为接下来的研究工作提供了最基本的技术支撑。针对源点不能获知网络全局拓扑知识且宿点具有至源点反馈路径的单源组播网络,基于网络吞吐率达到最大的目标,利用网络编码的导出与扩展技术,提出了基于网络编码的数据传输策略。分两种情形进行了研究,针对静态网络环境,提出了一种确定性的网络编码数据传输策略；针对网络拓扑随时间动态变化的环境,提出了在数据传输过程中测试组播容量并调整组播率的策略,能使组播率适应网络拓扑的变化,达到提升网络吞吐量的目标。利用网络编码的导出与扩展技术,提出了一个未知网络拓扑环境下基于最小编码信道数的分布式网络编码构造方法,与已有文献的研究结果相比,提出的方法无需事先给定组播率且能达到最大的组播率,不仅能求出其最小编码信道数还能构造出相应的编码方案。对伽罗华域的代数运算方法的时间复杂度进行了精确分析,在此基础上,以网络传输的运算延迟衡量编码运算代价,构造出了估算网络编码运算代价的数学模型,导出了运算代价与环境参数(组播率、伽罗华域、数据块长)间的确切关系,进而分析了影响运算代价的关键因素,这些分析有助于为减小运算代价而正确地选择环境参数。针对多个源点需组播信息至所有宿点的多源多宿组播网络,提出了使网络吞吐率达到最大的编码构造方法；针对一般的多源组播网络,提出了一个可行的,子优化网络吞吐量的网络编码构造方法,分析表明,就其提高网络的吞吐率而言,该方法优于路由传输技术。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 问题的提出
• 1.2 国内外研究现状
• 1.2.1 网络编码理论和应用的研究现状
• 1.2.2 网络编码的优化构造研究现状
• 1.3 本文要研究的内容
• 1.4 论文的组织结构
• 第二章 相关理论与技术
• 2.1 组播通信、网络的最大流
• 2.2 优化理论和模型
• 2.3 遗传算法的基本理论与应用
• 2.4 有限域的基本概念
• 2.5 线性网络编码的基本原理
• 2.6 仿真模型的建立方法
• 2.7 小结
• 第三章 线性网络编码的导出与扩展
• 3.1 引言
• 3.2 线性网络编码的导出与扩展
• 3.3 几个重要性质
• 3.4 仿真测试
• 3.5 小结
• 第四章 未知网络拓扑环境下基于最大吞吐率的网络编码组播
• 4.1 引言
• 4.2 未知网络拓扑环境下确定性网络编码数据传输策略
• 4.2.1 基本思路
• 4.2.2 试播法确定编码方案
• 4.2.3 算法的有效性分析
• 4.2.4 确定性网络编码数据传输
• 4.2.5 与已有方法的比较
• 4.2.6 仿真测试
• 4.3 网络拓扑动态变化环境下网络编码的数据传输策略
• 4.3.1 问题描述
• 4.3.2 总体思路
• 4.3.3 方法描述
• 4.3.4 仿真测试
• 4.4 本章小结
• 第五章 基于编码信道数最小的网络编码优化构造研究
• 5.1 引言
• 5.2 相关技术基础
• 5.2.1 统计编码方案所需的编码信道数
• 5.2.2 遗传表示
• 5.3 未知网络拓扑环境下基于信道数最小的分布式网络编码优化构造
• 5.3.1 基本思想
• 5.3.2 初始群体的产生
• 5.3.3 信息反馈
• 5.3.4 群体进化
• 5.3.5 算法描述
• 5.3.6 实验与分析
• 5.4 小结
• 第六章 网络编码运算代价的估算与分析
• 6.1 引言
• 6.2 伽罗华域代数运算及其时间复杂度分析
• 6.2.1 加（减）法运算
• 6.2.2 乘法运算
• 6.2.3 除法运算
• 6.3 采用高斯消元法求逆矩阵的运算量
• 6.4 网络编码运算代价的估算与分析
• 6.4.1 运算代价的估算
• 6.4.2 影响运算代价的因素
• 6.5 数值计算与仿真实验
• 6.6 小结
• 第七章 多源组播网络编码的优化构造研究
• 7.1 引言
• 7.2 多源多宿组播网络的网络编码优化构造
• 7.2.1 问题描述
• 7.2.2 解决方法
• 7.2.3 模型求解
• 7.2.4 构造各信道的局部编码向量
• 7.2.5 仿真测试
• 7.3 多源组播连接问题的线性网络编码构造
• 7.3.1 问题定义
• 7.3.2 多源组播连接的线性网络编码构造
• 7.3.4 与路由传输技术的比较
• 7.3.5 仿真测试
• 7.4 小结
• 第八章 工作总结与展望
• 8.1 本文的工作总结
• 8.2 本文的主要贡献
• 8.3 下一步的主要工作
• 参考文献
• 攻读学位期间主要的研究成果
• 致谢
• 附录
• 附录1 伽罗华域的生成多项式
• 附录2 仿真测试中部分随机生成的单源组播网络的邻接矩阵