基于网络编码的无线单播和组播调度技术研究

摘要

随着无线技术和无线设备的不断发展，用户终端的无线应用迅速增长，包括文本，音频和视频等应用，其中基于视频业务的无线应用比重逐渐加大，对无线带宽的需求也日益增加。与有线网络相比，无线网络的信道带宽较低，难以提供可靠和稳定的用户服务。一种根本性的方法是增加无线网络的容量，其中网络编码被认为是最具发展前景的网络技术。网络编码通过允许中间节点对信息处理，可提高无线网络的单播和组播吞吐量，降低传输延时，节省传输能量并提高网络的鲁棒性。
　　 本文集中于基于网络编码的无线单播和组播调度技术研究。对于单播应用，本文讨论侦听缓存受限的无线单播网络编码性能和侦听缓存管理策略；对于可靠组播应用，本文分析了双源组播系统的组播速率界并提出基于随机线性网络编码的静态和动态交替调度算法；对于具有严格延时约束的组播调度，本文提出一种基于加权债务的组播重传调度算法。本文的主要研究内容如下：
　　 (1)侦听缓存受限的无线单播网络编码
　　 在基于机会式网络编码的的无线单播应用中，每个节点需要缓存一些数据包用来对编码数据包进行解码，该缓存称作侦听缓存。本文针对“X”型拓扑分析了传统的基于先入先出的侦听管理策略，讨论了不同队列调度算法和带宽分配对系统性能的影响，理论结果表明侦听缓存有限时吞吐量随侦听缓存的减小而迅速降低。为此，提出了一种基于尽力服务的侦听管理策略，提高了侦听缓存中数据包被用作解码的概率，进而提高了系统吞吐量。为减少无用数据包被缓存的概率，提出了一种基于历史信息的侦听管理策略，可有效减少干扰流对系统吞吐量的影响。
　　 (2)基于随机线性网络编码的双源交替调度算法
　　 为减少单源组播中链路质量最差的组播成员对组播速率的影响，本文分析了双源组播系统的组播速率界并提出适用于双源可靠组播的静态和动态交替调度算法。算法通过交替传输编码数据包，可充分挖掘组播成员到不同源节点链路质量差异性带来的优势。与单源组播相比，理论分析和仿真表明：两种调度算法可以有效提高组播速率，从而减少期望传输时间。动态交替调度算法通过动态更新参数，可以获得更低的期望传输时间。
　　 (3)基于加权债务的组播重传调度算法
　　 在典型的单基站多接收节点的组播模型中，考虑具有严格延时约束条件的组播流，其中接收节点对不同的流具有不同的平均吞吐量需求。本文提出一种基于加权债务的组播重传调度算法，该算法在每次传输完毕后统计每个接收节点对其订阅流的丢包情况并计算相应的加权债务，将寻找最优编码包问题转化为加权最大团问题，且加权最大团问题的顶点权值即为相应的加权债务。为解决加权最大团问题，提出了一种近似算法，该算法在优先调度最大权值顶点的前提下，尽可能的编码更多的数据包。仿真结果表明：无论是何种场景，基于加权债务的组播重传调度算法都可以明显降低吞吐量需求未满足比例，同时未满足吞吐量需求的平均债务也是最低的。

目录

声明

摘要

图索引

表索引

缩略词索引

第1章 绪论

1.1 研究背景

1.2 无线网络中网络编码研究现状

1.2.1 单播研究现状

1.2.2 组播研究现状

1.2.3 论文研究点的引入

1.3 本文的主要工作

1.4 本文的组织结构

第2章 网络编码概述

2.1 网络最大流

2.2 网络编码的数学模型

2.3 随机线性网络编码

2.4 基于异或操作的网络编码协议

2.4.1 经典的COPE协议

2.4.2 组播重传算法

2.5 网络编码的优点

2.5.1 提高网络吞吐量

2.5.2 均衡网络负载

2.5.3 节省节点能耗

2.5.4 提高网络的鲁棒性

2.5.5 提高网络的纠错能力

2.5.6 提高网络安全性

第3章 侦听缓存受限的无线单播网络编码

3.1 引言

3. 2 网络编码中的侦听管理策略

3.2.1 系统模型

3.2.2 基于FIFO的侦听管理策略分析

3.2.3 基于尽力服务的侦听管理策略

3.3 仿真

3.4 基于历史信息的侦听管理策略

3.5 本章小结

第4章 基于随机线性网络编码的双源交替调度算法

4.1 引言

4.2 系统模型及组播速率上界

4.3 交替调度算法

4.3.1 静态交替调度算法

4.3.2 动态交替调度算法

4.4 仿真结果与分析

4.5 本章小结

第5章 基于加权债务的组播重传调度算法

5.1 引言

5.2 系统模型

5.3 基于加权债务的组播重传调度算法

5.4 仿真

5.4.1 仿真场景

5.4.2 对比方案

5.4.3 仿真结果及讨论

5.5 本章小结

第6章 总结及下一步工作

6.1 本文的研究内容和成果

6.2 进一步工作

参考文献

致谢

在读期间发表的学术论文与取得的其他研究成果