无线数据广播调度与索引技术研究

论文摘要

无线移动计算是随着无线网络技术的发展和移动设备的普及而逐步发展起来的一种计算方式,其目的是使移动用户可以随时随地访问网络中的资源。由于其具有极大的应用潜力,自上世纪90年代发展至今,一直受到研究界和工业界的强烈关注,而其特殊的计算环境也带来了一系列新的研究课题和挑战。无线移动网络具有低带宽和非对称特性,而无线移动应用的潜在用户数量又非常庞大,如何提高系统的可伸缩性是一个迫切需要解决的问题。数据广播是无线移动环境中一种新型的数据发布方式,基站服务器向空中(无线信道)广播数据,移动用户从空中接收数据。数据广播的特点是数据的一次发布就可以同时满足全部用户的需要,因此系统的可伸缩性很强。目前数据广播技术在公共信息的发布、军事应用等领域已有实际案例,并有着很好的应用前景。数据广播系统的主要评价指标是访问时间(Access Time,AT)和调谐时间(Tuning Time,TT),分别用来衡量系统的访问效率和能量使用效率,数据广播调度技术和空中索引技术就是围绕这两个性能指标的优化而展开。本文对这两种技术的几个关键问题进行研究,主要内容如下:(1)研究数据广播调度的理论模型。建立了多信道数据广播调度的非线性规划模型,并采用非线性规划的拉格朗日乘数法求解该问题,得出多信道广播调度的平方根规则。该规则指出了在信道带宽不相等的环境中,对变长数据项进行广播调度可以获得的最小平均AT,并提出达到这一最小值需要满足的条件。(2)研究单信道数据广播调度方法。首先发现广播周期长度这一参数对广播调度效果的影响,提出了一种计算广播周期长度的方法;然后使用该长度设计了分别适用于等长数据项的广播调度算法和变长数据项的广播调度算法。算法复杂度低,而且获得的平均AT非常逼近理论最小值。(3)研究多信道数据广播调度方法。基于多信道广播调度的平方根规则,提出了两阶段调度方法,第一阶段将数据按照平方根规则的要求划分到每个信道上,第二阶段对每个信道采用单信道的调度方法。由于多信道平方根规则的准确性,两阶段调度方法获得的平均AT非常逼近理论最小值;而由于该规则的通用性,两阶段调度方法适用于在通用环境中进行广播调度。(4)研究可以灵活调整的空中索引方法。改进了Flexible索引,充分利用数据块的空间,在不增加广播周期长度的前提下,为用户提供更小的TT。通过对多个参数的调整,实现在AT与TT之间进行更加灵活的折衷。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景与意义
• 1.1.1 无线移动计算系统的体系结构
• 1.1.2 无线移动计算环境的特点
• 1.1.3 应用背景与意义
• 1.2 数据广播问题及研究现状
• 1.2.1 数据广播及其特点
• 1.2.2 数据广播的性能指标
• 1.2.3 数据广播的研究内容
• 1.2.4 数据广播研究现状
• 1.3 本文研究内容与结构
• 1.3.1 研究内容
• 1.3.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 单信道与多信道广播调度的比较
• 2.5 本章小结
• 第三章 单信道广播调度方法
• 3.1 引言
• 3.2 广播周期长度的估算方法
• 3.3 基于平方根规则的偏斜调度算法
• 3.3.1 适用于等长数据项的调度算法（SS）
• 3.3.2 适用于变长数据项的调度算法（SSV）
• 3.4 实验与比较
• 实验1:广播周期长度对访问时间的影响
• 实验2:访问偏斜度对广播周期长度的影响
• 实验3:算法SS与SSV的比较
• 实验4:算法SSV的性能
• 3.5 本章小结
• 第四章 多信道广播调度方法
• 4.1 引言
• 4.2 相关研究
• 4.3 两阶段调度方法
• 4.4 数据划分算法
• 4.5 多信道混合调度策略
• 4.6 实验与比较
• 实验1:数据划分依据对性能的影响
• 实验2:混合调度策略的效果
• 实验3:与其他多信道广播调度算法的比较
• 4.7 本章小结
• 第五章 数据广播的空中索引技术
• 5.1 引言
• 5.2 空中索引的基本结构与访问协议
• 5.3 Flexible索引
• 5.4 改进的Flexible索引
• 5.4.1 索引结构
• 5.4.2 访问协议
• 5.4.3 性能分析
• 5.5 实验与比较
• 实验1:数据项个数对性能的影响
• 实验2:搜索步长对性能的影响
• 实验3:索引的可调整性
• 5.6 本章小结
• 第六章 结束语
• 参考文献
• 博士期间参与的科研项目和发表的论文
• 致谢