CAJ | 학술논문

在On-Demand数据广播环境下,广播服务器基于用户发送的数据请求等信息进行调度决策来满足用户的数据访问需求.在很多实际应用中,用户的数据请求需要在一定时间段内得到满足,即数据请求是有截止期的.现有研究只考虑了具有截止期约束的单个数据请求的调度问题,而实时查询处理即用户以查询为单位依次发送多个数据请求的研究尚未得到足够的关注.本文重点研究了On-Demand数据广播环境下如何有效地处理实时有序查询这一问题.基于对该问题的分析,定义了一类新的调度问题ROBS并证明了ROBS的off-Line版本是NP-Hard的;提出了一种新的考虑查询语义的On-Line调度算法OL-ROBS,该算法通过综合考虑数据请求个数、查询截止期和查询剩余数据请求个数来确定待广播数据项的优先级;为提高OL-ROBS的执行效率,设计了一种裁减算法,用以减少调度决策的搜索空间.模拟实验将OL-ROKS与目前最为有效的实时数据请求调度算法Sin-θ进行了比较,结果显示OLROBS具有更低的错过截止期比率.
재On-Demand수거엄파배경하,엄파복무기기우용호발송적수거청구등신식진행조도결책래만족용호적수거방문수구.재흔다실제응용중,용호적수거청구수요재일정시간단내득도만족,즉수거청구시유절지기적.현유연구지고필료구유절지기약속적단개수거청구적조도문제,이실시사순처리즉용호이사순위단위의차발송다개수거청구적연구상미득도족구적관주.본문중점연구료On-Demand수거엄파배경하여하유효지처리실시유서사순저일문제.기우대해문제적분석,정의료일류신적조도문제ROBS병증명료ROBS적off-Line판본시NP-Hard적;제출료일충신적고필사순어의적On-Line조도산법OL-ROBS,해산법통과종합고필수거청구개수、사순절지기화사순잉여수거청구개수래학정대엄파수거항적우선급;위제고OL-ROBS적집행효솔,설계료일충재감산법,용이감소조도결책적수색공간.모의실험장OL-ROKS여목전최위유효적실시수거청구조도산법Sin-θ진행료비교,결과현시OLROBS구유경저적착과절지기비솔.
Existing research efforts on real-time data dissemination in on-demand data broadcast environments are only concerned with scheduling single data request with deadline constraints.The issue of processing real-time ordered query in on-demand broadcast systems was investigated.Particularly,we first formally defined a new kind of scheduling problem called ROBS by formulating the reabtime ordered query processing problem.We also showed that the ROBS problem is NP-hard.Secondly,a novel scheduling algorithm called OL-ROBS was proposed to address the on-line version of ROBS.To tackle the performance issue of OL-ROBS,a delicate data structure for managing data requests was constructed and an efficient pruning algorithm was proposed.Finally,extensive simulations were conducted and the empirical resuits show that OL-ROBS owns significant performance gain over the well-known Sin-θ algorithm.