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