基于网络编码的无线网络可靠多播机制研究

论文摘要

通信技术的发展促进了多种无线传输网络建设与应用,如蜂窝网络,无线自组织（Ad hoc）网络等。近年来,移动主机和掌上电脑不断普及,使得许多应用得以在各种无线网络上进行开发。由于无线网络中信道质量差和节点的移动性,数据包丢失在无线网络传输中很常见。而绝大多数应用都需要数据在无线网络中进行可靠传输。因此,无线网络中数据包的可靠传输是一个非常重要的问题。在无线网络中,根据接收节点的反馈信息,源节点可以知道接收节点已经接收到的数据包和丢失的数据包。本文利用网络编码研究了如何编码重传丢失的数据包以保证接收节点能够正确地接收到所有的数据包。针对不同的应用场景,本文研究了不同的编码方案以及传输调度方案来优化网络的性能,优化目标包括最小化发送节点重传的总次数,最小化超过延迟约束数据包的数目等。本文的主要研究内容与贡献如下：（1）基于网络编码的可靠重传算法本文研究了无线网络中基于网络编码的可靠组播,目标在于最小化发送节点重传数据包的总数。本文提出了一个图模型来刻画基于网络编码的重传问题,并将发送节点的重传策略模型化为图中的最小团划分。为了有效的解决编码重传问题,本文提出了一个时间复杂度为O（|E|）的近似最小团划分算法并证明了其正确性,其中|E|为图中边的数目。针对不同丢包率的无线网络,实验比较了基于网络编码的重传策略和传统重传策略所需重传数据包的总数。模拟实验结果表明,基于网络编码的重传策略需要的重传数据包数明显少于传统的重传策略。（2）基于网络编码的可靠多播模型在上述工作的基础上,我们提出了两个可靠多播模型,动态多播重传编码模型（Dynamic Multicast Retransmission Encoding, DMRE）和基于缓存的多播重传编码模型（Cache-based Multicast Retransmission Encoding, CMRE）以及相应的启发式算法来进一步减少重传次数。DMRE是无记忆模型,假定接收节点不会缓存重传的编码数据包,但DMRE模型通过持续更新多播组中每个接收节点当前已经收到的数据包来进一步减少重传次数,在这种模型下,每次重传都基于接收节点最新需要的数据包。CMRE模型假设接收节点能缓存所收到的所有重传包并当有足够的信息后才进行解码。模拟实验结果表明,采用DMRE模型的重传策略优于基于团划分的重传策略,而CMRE模型则更优于DMRE模型。（3）基于网络编码的延迟约束广播调度考虑到对数据包延迟等服务质量要求比较高的流媒体应用,本文研究了无线网络中数据包有延迟约束的基于网络编码的广播调度问题,目标在于最小化超过延迟约束数据包的数目。本文提出一个加权图模型来描述这个问题并证明了无线网络中基于网络编码的延迟约束广播调度问题是NP难的。提出了一个整数线性规划数学模型来求解该问题,但由于该问题是NP难解的,所提出的整数线性规划只能求解小规模的网络。通过将图中顶点的权值设置为关于数据包延迟约束的减函数,并进一步提出了一种在图中寻找最大加权团的近似算法来进行编码调度的算法,可以显著的减少超过延迟约束数据包的数目。针对不同的应用需求,还详细分析了顶点的权值函数应该如何设置,为以后针对QoS需求的网络编码问题提供了参考。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 无线网络简介
• 1.2 无线网络中可靠多播
• 1.2.1 多播
• 1.2.2 可靠多播协议
• 1.3 无线网络中基于网络编码的可靠多播研究现状
• 1.4 本文的主要研究内容和贡献
• 1.5 本文的组织
• 第2章 网络编码概述
• 2.1 网络编码的背景
• 2.2 网络编码的编解码策略
• 2.3 网络编码的优点
• 2.3.1 吞吐量提高
• 2.3.2 鲁棒性和自适应性增强
• 2.3.3 网络安全性的增强
• 2.4 无线网络中的网络编码
• 2.4.1 应用场景
• 2.4.2 理论基础
• 2.4.3 待解决的问题
• 第3章 基于网络编码的可靠重传算法
• 3.1 前言
• 3.2 问题描述
• 3.3 丢失包重传算法
• 3.3.1 图模型
• 3.3.2 重传算法
• 3.4 实验结果
• 3.5 本章小结
• 第4章 基于网络编码的可靠多播模型
• 4.1 前言
• 4.2 系统框架和问题描述
• 4.3 动态多播重传编码问题
• 4.3.1 辅助图的构造及编码算法
• 4.3.2 网络编码性能的分析
• 4.4 基于缓存的多播重传编码问题
• 4.4.1 编码算法
• 4.4.2 解码算法
• 4.5 性能分析
• 4.6 模拟实验
• 4.7 本章小结
• 第5章 基于网络编码的延迟约束广播调度
• 5.1 前言
• 5.2 系统框架和问题描述
• 5.3 无记忆编码问题
• 5.3.1 加权图模型
• 5.3.2 最小超过延迟约束率的团划分问题
• 5.3.3 基于最大加权团的编码算法
• 5.4 权值函数分析
• 5.4.1 延迟约束最小优先
• 5.4.2 最小延迟约束最大数量优先
• 5.4.3 重要标准最大优先
• 5.5 有记忆编码问题
• 5.5.1 问题的复杂度
• 5.5.2 编码算法
• 5.5.3 性能分析
• 5.6 模拟实验
• 5.7 本章小结
• 第6章 总结
• 6.1 本文的研究内容和成果
• 6.2 进一步的工作
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果