论文部分内容阅读
多信道无线数据广播是一种向大量用户传播数据的有效方法。这篇论文展示了无线数据广播系统基于字母序哈弗曼树（AH-Tree)索引机制的全局优化方案，这种优化方案能够有效地处理分布不均匀的数据。论文提出了3种优化技术来降低系统的访问延迟（access latency）和探测时间（tuning time）。首先，文中使用了动态规划的技术有效地降低了AH-Tree的构建时间复杂度。传统的Hu-Tucker算法的时间复杂度是O(tk)，而文中提出的算法能够在O(t2)里构建一棵k叉的AH-Tree。其次，文中描述了一种全新的控制表（control table）设计，这种设计能够在保持查询效率的同时消除原来控制表里面至多50％的冗余数据。另外，文中也从理论上证明了，对于分布不均匀的数据，在所有的索引树中最优的字母序哈弗曼树的平均探测时间最少。最后，文中提出了新的索引和数据分配算法，进一步减少了访问延迟和探测次数。模拟的结果验证了算法的有效性。总而言之，文中提出的全局优化机制有效地提高了无线数据广播系统的性能。