移动实时数据库中的数据广播策略研究

摘要

无线通信网络的迅猛发展使得移动计算成为现实。移动支持站点把被频繁请求的数据组织起来，以广播的形式传送给移动客户。
　　 数据广播有许多问题值得研究。
　　 移动实时环境里数据广播的首要问题是广播内容的选择。被频繁请求的热点数据能够及时广播，将会满足大量客户的需求，提高系统效率。传统的频繁元素获取通常采用计数、概要、分位数和散列等技术，时间性能最好的是散列类算法。在伯努利大数定理和马尔科夫不等式的基础上，通过统计散列冲突估算频繁元素出现的次数，利用多个散列函数和散列表可以使得误差被控制到精度许可的范围内。多散列计算可以充分利用现在主流多核微型处理器的计算能力。只需要增加散列函数的数量就可以提高统计精度，而增加的计算时间却很少。
　　 以最少的时间和能源消耗获得最多有用的数据是移动客户在数据广播中获取的最大效益。数据广播调度从客户效益出发，采用基于优先权的调度策略。优先权综合考虑了数据截止期，数据的被请求频率和数据请求的到达时间。通过参数来调整它们的权重，使得调度策略能够在满足数据请求成功率的基础上，权衡平均访问时间和调谐时间。在调度策略的实施过程中将同一客户请求的数据尽可能地放在一起调度播出。数据组织结构里增加了热点数据指示器，移动客户在侦听信道的时候，可以根据自己设备的电源情况，有选择地下载各级热点数据，提高缓存命中率，降低上行信道负荷和平均访问时间，提高系统的处理能力。
　　 实时系统中数据访问偏斜时，数据广播的索引技术鲜有研究。建立索引一方面要考虑数据的访问概率，另一方面要考虑数据的时间限制；同时构建索引的算法本身的时间复杂度要低。近似最优二叉索引树参考静态最优查找树的构造思想，在处理节点概率权重时引入实时加权，快速构造出查找效果近似最优的二叉索引树。其查找过程类似于折半查找，平均查找长度和logN 成正比，即调谐时间至多logN个时间单位。因为考虑数据访问概率，被频繁访问的数据放在广播序列的前端，缩短了平均调谐时间；因为考虑了实时加权，时限较短的数据也放在了广播序列的前端，提高了实时系统中数据请求的成功率。

目录

文摘

英文文摘

声明

1 绪论

2 嵌入式移动实时数据库热点数据的获取算法

3 基于效益的广播调度

4 一种近似最优的二叉索引树

5 一种基于收益的数据预取策略

6 原型系统实现

7 结束语

致谢

参考文献

附录