论文部分内容阅读
随着科学技术的发展，数据广播已经成为一种主流的通讯方式。在实际的广播环境中，广播带宽资源往往有限，因此，如何在保证查询任务实时性要求的前提下，减小广播带宽的开销，这是一个急需解决的问题。 在一种新型的广播环境中，用户查询实时数据并持续关注数据的变化。在此环境下，通常采用的查询方式是连续周期性查询。在现有研究中，只有RM-UO算法适用于此类环境，然而，此算法在带宽利用方面存在着明显不足。当使用RM-UO算法调度查询任务集时，算法首先生成一个DC任务集，然后，调用Sr算法将DC任务集转化为2谐波任务集。由于Sr算法往往缩短部分DC任务的周期，因而，在RM-UO算法的执行过程中，往往存在着广播带宽的浪费。 分析可知，当DC任务集转化为2谐波任务集时，一些DC任务（连续的或者周期上具有一定关系的DC任务）可以合并成一个任务，从而减少广播带宽开销。基于上述分析结果，提出了两个任务合并规则（MQM规则和RQM规则）和两个分别使用这两种规则的广播调度算法（MQM-UO算法和RQM-UO算法）。此外，由于MQM规则和RQM规则的执行并不存在冲突，进一步提出了一种结合MQM-UO算法优点和RQM-UO算法优点的广播调度算法―UM算法。实验结果表明，与传统RM-UO算法相比，UM算法、MQM-UO算法和RQM-UO算法均能减少广播带宽开销，使广播系统可以同时为更多查询提供服务。 上述四种算法均为固定优先级广播调度算法，且均调用RM算法调度最终的任务集。由于RM算法的可调度性阈值较低，上述四种算法的可调度性受到了影响。于是，尝试用非固定优先级调度方式解决支持连续周期性查询的广播调度问题。出于兼顾广播数据共享性的考虑，部分数据需要周期性广播，因此，首先对实时调度问题进行研究，提出了一种新型的实时调度算法―PEDF算法。当使用PEDF算法调度实时任务集时，部分任务可以周期性执行。然后，基于PEDF算法，首次提出了一种支持连续周期性查询的非固定优先级广播调度算法―PCDI算法。实验结果表明，与传统RM-UO算法相比，PCDI算法能够有效节省广播带宽，具有较高的可调度性。 最后，结合UM算法和PCDI算法，提出了一种兼具UM算法优点和PUM算法优点的新型广播调度算法―PUM算法。实验结果表明，与传统RM-UO算法相比，所提出算法均在服务率和带宽利用率方面有着更好的表现，其中，PUM算法表现最佳。