-
题名On-Demand数据广播环境下实时有序查询处理
- 1
-
-
作者
王洪亚
刘晓强
何浩源
宋晖
肖迎元
乐嘉锦
-
机构
东华大学计算机科学与技术学院
天津理工大学计算机科学与技术学院
-
出处
《计算机科学》
CSCD
北大核心
2010年第5期146-150,186,共6页
-
基金
国家自然科学基金(60903160)
上海市科技攻关项目(06dz150003)资助
-
文摘
在On-Demand数据广播环境下,广播服务器基于用户发送的数据请求等信息进行调度决策来满足用户的数据访问需求。在很多实际应用中,用户的数据请求需要在一定时间段内得到满足,即数据请求是有截止期的。现有研究只考虑了具有截止期约束的单个数据请求的调度问题,而实时查询处理即用户以查询为单位依次发送多个数据请求的研究尚未得到足够的关注。本文重点研究了On-Demand数据广播环境下如何有效地处理实时有序查询这一问题。基于对该问题的分析,定义了一类新的调度问题ROBS并证明了ROBS的Off-Line版本是NP-Hard的;提出了一种新的考虑查询语义的On-Line调度算法OL-ROBS,该算法通过综合考虑数据请求个数、查询截止期和查询剩余数据请求个数来确定待广播数据项的优先级;为提高OL-ROBS的执行效率,设计了一种裁减算法,用以减少调度决策的搜索空间。模拟实验将OL-ROBS与目前最为有效的实时数据请求调度算法Sinθ-进行了比较,结果显示OL-ROBS具有更低的错过截止期比率。
-
关键词
数据广播
实时有序查询处理
调度算法
-
Keywords
Data broadcast Real-time ordered query processing Scheduling algorithms
-
分类号
TP31
[自动化与计算机技术—计算机软件与理论]
-