文档介绍：中国科学技术大学
博士学位论文
无线宽带网络中的资源分配和调度算法研究
姓名:靳俊峰
申请学位级别:博士
专业:计算机软件与理论
指导教师:赵保华
2011-05-01
摘要
摘要
无线宽带接入技术的迅速发展给人们的工作和生活带来日新月异的变化,
可以预见,在不远的将来,无线宽带技术会渗透到世界的每一个角落。目前,
各种无线技术互补发展,各尽所长,向接入多元化、网络一体化、应用综合化
的宽带无线网络发展,并逐步实现和宽带固定网络的有机融合。如何提高无线
资源的分配效率以适应日益增长的应用需求是当前无线通信领域的热点研究课
题。本文对无线 Mesh 网络和移动宽带通信网络中的资源分配和调度进行了深入
研究,提出了多信道分配算法,分布式联合资源调度算法和容错可伸缩视频多
播资源分配算法等,以最大化提高无线网络资源的使用效率。
本文首先研究了多信道无线 Mesh 网络中的信道分配问题,对该问题模型进
行了描述,证明其可以归约为图列表着色问题,是 NP 难解的;然后提出了一种
最小化链路干扰的度量方法来保证网络公平性,并在此基础上提出了负载感知
和距离受限的集中式信道分配算法,该算法能够最小化网络干扰从而提高网络
吞吐量。由于集中式算法无法应用于大规模、动态变化的网络中,因此对集中
式信道分配算法进行扩展,提出了分布式负载感知和距离受限的信道分配算法。
分布式方法适用于规模较大的自组织结构的网络中,具有良好的扩展性和可靠
性。仿真结果表明分布式算法虽然只使用了局部信息来进行信道分配,然而在
性能上却非常接近集中式算法。
为了解决无线网络中的单播和多播流量统一信道分配问题,本文提出了传
输单元的概念,将单播和多播流量统一到相同的模型中,从而将该问题转化为
传输冲突图着色问题,并证明了该问题是 NP 难解的;由于弦图可以在多项式时
间内求得极大团,而普通图需要指数时间才能找到极大图,因此本文通过增加
一些冗余边将原始的传输冲突图转化为弦图;最后,采用了更准确选择信道的
度量方法,该方法通过计算互相覆盖信道间隔和传输能量来选择最小化干扰的
信道,并在此基础上提出了基于弦图的最优信道分配算法,仿真实验表明该算
法无论在单播流量、多播流量还是混合流量中的网络性能都优于其它算法。
由于无线信道分配、链路调度和路由问题之间互相依赖,单独考虑某一问
题无法得到满意结果,因此本文提出了多信道多接口无线 Mesh 网络中的信道分
配、链路和路由选择联合调度框架,对该联合调度问题进行了模型描述;其次,
采用链路队列模型来描述网络流量的状态,并且在此基础上提出了基于两阶段
队列的分布式最大化调度算法,该算法能够得到与最优算法可证明比率效率的
I
摘要
性能,仿真实验结果表明该分布式最大化调度算法与其它相关算法相比,不仅
性能有很大提升,而且算法运行复杂度大大降低。
为了解决移动宽带通信网络中的容错视频多播问题,本文提出了分层混合
FEC/ARQ 算法,将容错视频多播问题形式化为无界背包问题并且证明了问题是
NP 难解的;为避免反馈爆炸问题,将多播用户按照信道条件划分为多组并且每
组随机选出一个用户代表本组发送反馈信息;最后提出了组代表用户场景下的
跨层最优资源分配算法,为不同视频层提供不平等错误保护。算法基于动态规
划方法且具有伪多项式时间复杂度,仿真结果表明分层混合 FEC/ARQ 算法与其
它相关算法相比性能有明显提高。
关键词:无线资源管理信道分配链路调度传输冲突图容错视频多播
分层混合 FEC/ARQ
II
Abstract
ABSTRACT
Growing wireless broadband access technologies have brought great convenience
and changes to our work and life during recent years. There are different wireless
technologies coexisting for different purposes and applications, and they will make a
ubiquitous coverage with the wired works over the world in the near
future. Due to the scarce wireless frequency resources, how to improve