无线宽带网络中的资源分配和调度算法研究

论文摘要

无线宽带接入技术的迅速发展给人们的工作和生活带来日新月异的变化,可以预见,在不远的将来无线宽带技术会渗透到世界的每一个角落。目前,各种无线技术互补发展,各尽所长,向接入多元化、网络一体化、应用综合化的宽带无线网络发展,并逐步实现和宽带固定网络的有机融合。如何提高无线资源的分配效率以适应日益增长的应用需求是当前无线通信领域的热点研究课题。本文对无线Mesh网络和移动宽带通信网络中的资源分配和调度进行了深入研究,提出了多信道分配算法,分布式联合资源调度算法和容错可伸缩视频多播资源分配算法等,以最大化提高无线网络资源的使用效率本文首先研究了多信道无线Mesh网络中的信道分配问题,对该问题模型进行了描述,证明其可以归约为图列表着色问题,是NP难解的；然后提出了一种最小化链路干扰的度量方法来保证网络公平性,并在此基础上提出了负载感知和距离受限的集中式信道分配算法,该算法能够最小化网络干扰从而提高网络吞吐量。由于集中式算法无法应用于大规模、动态变化的网络中,因此对集中式信道分配算法进行扩展,提出了分布式负载感知和距离受限的信道分配算法。分布式方法适用于规模较大的自组织结构的网络中,具有良好的扩展性和可靠性。仿真结果表明分布式算法虽然只使用了局部信息来进行信道分配,然而在性能上却非常接近集中式算法。为了解决无线网络中的单播和多播流量统一信道分配问题,本文提出了传输单元的概念,将单播和多播流量统一到相同模型中,从而将该问题转化为传输冲突图着色问题,并证明了该问题是NP难解的；由于弦图可以在多项式时间内求得极大团,而普通图需要指数时间才能找到极大图,因此本文通过增加一些冗余边将原始的传输冲突图转化为弦图；最后,采用了更准确选择信道的度量方法,该方法通过计算互相覆盖信道间隔和传输能量来选择最小化干扰的信道,并在此基础上提出了基于弦图的最优信道分配算法。仿真实验表明该算法无论在单播流量、多播流量还是混合流量中的网络性能都优于其它算法。由于无线信道分配、链路调度和路由问题之间互相依赖,单独考虑某一问题无法得到满意结果,因此本文提出了多信道多接口无线Mesh网络中的信道分配、链路和路由选择联合调度框架,对该联合调度问题进行了模型描述；其次,采用链路队列模型来描述网络流量的状态,并且在此基础上提出了基于两阶段队列的分布式最大化调度算法,该算法能够得到与最优算法可证明比率效率的性能,仿真实验结果表明该分布式最大化调度算法与其它相关算法相比,不仅性能有很大提升,而且算法运行复杂度大大降低。为了解决移动宽带通信网络中的容错视频多播问题,本文提出了分层混合FEC/ARQ算法,将容错视频多播问题形式化为无界背包问题并且证明了问题是NP难解的；为避免反馈爆炸问题,将多播用户按照信道条件划分为多组并且每组随机选出一个用户代表本组发送反馈信息；最后提出了组代表用户场景下的跨层最优资源分配算法,为不同视频层提供不平等错误保护。算法基于动态规划方法且具有伪多项式时间复杂度,仿真结果表明分层混合FEC/ARQ算法与其它相关算法相比性能有明显提高。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景和意义
• 1.1.1 移动宽带通信网络
• 1.1.2 无线Mesh网络
• 1.2 本文的主要研究内容
• 1.3 本文的组织结构及主要贡献
• 第2章 无线宽带网络中的资源分配和调度算法
• 2.1 资源分配和调度算法简介
• 2.2 多信道分配研究现状
• 2.2.1 单接口信道分配
• 2.2.2 多接口信道分配
• 2.2.3 集中式/分布式信道分配
• 2.3 可伸缩视频多播研究现状
• 2.3.1 无线网络中的可伸缩视频多播
• 2.3.2 容错视频多播
• 2.4 链路调度算法研究现状
• 2.4.1 集中式TDMA调度
• 2.4.2 分布式TDMA调度
• 第3章 负载感知和距离受限的多信道分配算法
• 3.1 引言
• 3.2 集中式负载感知和距离受限的多信道分配算法
• 3.2.1 系统模型和问题定义
• 3.2.2 算法描述
• 3.2.3 性能分析
• 3.3 扩展算法:分布式多信道分配算法
• 3.3.1 扩展模型
• 3.3.2 算法描述
• 3.3.3 性能分析
• 3.4 本章小结
• 第4章 基于弦图的单播和多播统一信道分配算法
• 4.1 引言
• 4.2 系统模型
• 4.2.1 路由树和传输集
• 4.2.2 传输冲突图
• 4.2.3 团可行性和信道分配可行性
• 4.2.4 覆盖信道选抒方法
• 4.3 基于弦图的最优信道分配框架
• 4.3.1 问题描述
• 4.3.2 算法描述
• 4.4 仿真环境
• 4.4.1 场景设置
• 4.4.2 结果分析
• 4.5 本章小结
• 第5章 基于容量最大化的分布式资源联合调度算法
• 5.1 引言
• 5.2 系统模型
• 5.2.1 无线网络中的公平性
• 5.2.2 模型描述
• 5.2.3 复杂性分析
• 5.3 单信道调度算法的多信道改进
• 5.3.1 集中式贪心最大化调度算法改进
• 5.3.2 分布式最大化调度改进
• 5.4 分布式调度算法设计
• 5.5 实验仿真
• 5.5.1 结果分析
• 5.6 本章小结
• 第6章 基于代表用户机制的容错视频多播资源分配算法
• 6.1 引言
• 6.2 系统模型
• 6.2.1 系统体系结构
• 6.2.2 组代表用户选择机制
• 6.2.3 分层混合FEC/ARO
• 6.2.4 通用效用目标函数
• 6.3 容错视频多播资源分配算法
• 6.3.1 单代表用户容错视频多播资源分配算法
• 6.3.2 组代表用户容错视频多播资源分配算法
• 6.4 性能分析
• 6.4.1 仿真环境
• 6.4.2 仿真结果
• 6.5 本章小结
• 第7章 全文总结与展望
• 7.1 全文总结
• 7.2 未来工作展望
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果