数据广播环境下实时查询处理

现有的实时数据广播研究中,只考虑了具有截止期约束的单个数据请求的调度问题,而支持实时查询处理的数据广播技术尚未得到足够的关注。该文研究在on-demand数据广播环境下,如何有效地处理实时查询问题,提出一种新的数据调度算法(QSA)。通过仿真实验与目前最为有效的数据请求调度算法SIN进行了比较,结果显示QSA具有更低的错过截止期比率,在最好的情况下,QSA比SIN降低了17.45%。     

数据广播调度自适应信道划分与分配方法

随着移动网络的不断发展,移动终端设备的计算能力与日俱增,越来越多的用户倾向于通过移动网络获取信息资源,这使得实时按需数据广播面临新的挑战：（1）数据内容和规模的多样化;（2）用户请求的实时性与需求多样性使得热点数据增加,直接导致广播数据总量的剧增;（3）用户对服务质量和水平的要求越来越高.当前的研究成果主要集中在固定信道模型和算法上,一定程度上忽略了当前数据广播调度环境的变化.固定信道存在如下问题：（1）局限于特定的网络,缺乏通用性;（2）信道大小、个数不能随着网络环境的变化而自动调整,降低了广播效率.基于以上考虑,对实时按需数据广播调度的自适应信道划分和分配进行研究,提出一种自适应信道划分与分配方法OCSM （optimized channel split method）,其根据数据请求特征的不同,实时自适应地调整信道个数和大小,从而提高系统敏感性、鲁棒性以及广播效率.该方法包括：（1）广播数据均衡聚类算法WASC （weight average and size clusteralgorithm）,其挖掘数据特征,为信道划分提供依据;（2）数据项广播优先级评定算法R×W/SL,其实时评定数据项调度优先级;（3）信道划分与分配算法CSA （channel split algorithm）.实验包括两个方面：（1）确定不同数据项大小和请求截止期分布下的信道划分策略,并分析聚类算法中聚类距离K在不同情况下的最佳取值以及最佳信道划分;（2）验证自适应信道划分与分配策略的有效性,并通过对比实验验证在不同情况下OCSM的有效性.实验结果表明：OCSM优于其他调度算法,并具有较强的自适应.     

交换以太网中实时消息截止期划分算法研究

为解决交换式以太网中实时消息在发送及接收链路上的截止期划分问题,首先给出了非抢占式EDF调度算法的可调度性分析方法,并分析了消息的提前释放对非抢占式EDF调度算法可调度性的影响,在此基础上提出了新的截止期划分算法(MDPS)。算法通过计算可满足调度条件时消息在发送链路及接收链路截止期应该划分的下限,并结合截止期的松驰量实现实时消息在发送及接收链路上的截止期划分。算法实验比较和分析表明,该算法在提高网络聚合带宽、减小消息的错失率方面明显优于现有的ADPS算法。     

一种新的组优先级动态实时调度算法

传统动态调度算法由于对优先级个数没有限制,在实际应用中往往受制约,达不到很好的调度性能.针对此问题,考虑硬实时抢占任务调度需要,提出一种新的组优先级动态实时调度算法.研究作业执行顺序改变对系统可调度性能的影响,给出作业分组可调度性能测试.新算法将满足分组可调度测试公式的作业作为一个任务组,各任务组之间按照最小截止期优先调度,任务组内按照最短作业优先的原则执行作业.仿真结果表明,与最小截止期优先等传统调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高任务调度的成功率,缩短平均响应时间,减少任务切换次数.     

基于数据时态特性的实时事务并发控制

通过对数据时态特性及其对事务调度的影响进行分析,提出了基于数据时态特性的实时事务并发控制算法.该算法根据数据截止期及事务的执行时间估算,改进了事务的验证规则,对事务的提交顺序进行调整,提高了系统的实时性能.理论分析与实验结果表明:该算法降低了事务重启个数及超截止期百分率,性能要优于已有的实时并发控制算法.     

双头镜像磁盘的实时调度算法及性能评价

本文对双头镜像磁盘系统模型进行实时扩展,并提出了三种实时调度算法：最早截止期优先算法（ＥＤＦ）,可满足的最早截止期优先算法（Ｆ－ＥＤＦ）和忽视超时限请求算法（ＩＧＭ－ＥＤＦ）．这三种算法充分考虑了Ｉ／Ｏ请求的截止期限,使双头镜像磁盘系统能更好地满足实时需求．在进行了性能模拟后,发现实时调度算法比非实时算法能更好地满足实时Ｉ／Ｏ请求的时限要求．三种实时调度算法中,适用于硬实时应用的ＩＧＭ－ＥＤＦ的性能最好,Ｆ－ＥＤＦ算法的性能次之,它适用于软实时环境．     

多数据项广播调度策略

多数据项广播是移动计算环境中一种重要的数据访问方式.为减少用户的平均访问时间和响应最多事务请求,提出了一种新的多数据项广播调度策略.调度策略分为两个阶段,第一阶段根据各事务包含的数据项数目和对重复申请数据项的处理选择事务请求;第二阶段对已选择的事务请求用QEM算法进行调度.实验结果表明,它比现有的QEM算法有更高事务调度成功率和更短的平均访问时间.     

双头镜橡磁盘的实时调度算法及性能评价

本文对双头镜像磁盘系统模型进行实时扩展,并提出了三种实时调度算法：最早截止期优先算法（ＥＤＦ）,可满足的最早截止期优先算法（Ｆ－ＥＤＦ）和忽视超时限请求算法（ＩＧＭ－ＥＤＦ）。这三种算法充分考虑了Ｉ／Ｏ请求的截止期限,使双头镜像磁盘系统能更好地满足实时需求,在进行了性能模拟后,发现实时调度算法比非实时算法能更好地满足时Ｉ／Ｏ请求的时限要求。三种实时调度算法中,适用于硬实时应用的ＩＧＭ－ＥＤＦ的性能     

移动环境中实时事务数据的广播调度

提出一种基于需求广播模型的实时事务数据的广播调度策略．在本策略中，综合考虑了事务存取多个数据项和满足定时限制的要求．本策略的目标是使错过截止期的事务数量最少，对我们提出的算法，通过建立模拟实验进行评价，结果显示它比现有的策略有明显的优越性．     

基于优先级的数据广播内容选择算法

在以无线网络为代表的移动计算环境中,数据广播是一种有效的数据访问方式。为响应最多用户数据请求,提出了优先级计算模型,进而提出了一种基于优先级的广播内容选择算法。该算法综合考虑了事务存取多个数据项和满足定时限制的要求,根据用户请求队列状态动态选择广播内容,并应用剪枝机制减少了选择开销。实验结果表明它比现有算法有明显的优越性。     

Dynamic priority scheduling of periodic queries in on-demand data dissemination systems

As an important wireless data broadcast technique, on-demand broadcast has been widely used for dynamic and large-scale data dissemination. An important class of emerging data broadcast applications requires monitoring multiple data items continuously in order to support data-driven decision making. Since wireless bandwidth is a precious shared medium, an important problem to solve is how to disseminate data to periodic queries, so that all the requests can be satisfied while the bandwidth consumption is minimized. In this paper, we first propose a new real-time scheduling algorithm called EDFS, which is a variant of the classic EDF [24] algorithm. Based on EDFS, we propose a novel on-line broadcast scheduling algorithm, called EDFS-BS. To our best knowledge, EDFS-BS is the first dynamic priority based broadcast scheduling algorithm that can be utilized to satisfy the timing constraints of periodic queries. We also propose a bandwidth utilization based schedulability test for EDFS-BS, which is used to ensure timing predictability of a periodic query set. Extensive experiments have been conducted to compare EDFS-BS versus existing solutions with comparable quality. The results show that EDFS-BS outperforms them considerably in terms of wireless bandwidth consumption and query service ratio.     

Scheduling on-demand broadcast with timing constraints

In a distributed system, broadcasting is an efficient way to dispense data in certain highly dynamic environments. While there are several well-known on-line broadcast scheduling strategies that minimize wait time, there has been little research that considers on-demand broadcasting with timing constraints. One application which could benefit from a strategy for on-demand broadcast with timing constraints is a real-time database system. Scheduling strategies are needed in real-time databases that identify which data item to broadcast next in order to minimize missed deadlines. The scheduling decisions required in a real-time broadcast system allow the system to be modeled as a Markov Decision Process (MDP). In this paper, we analyze the MDP model and determine that finding an optimal solution is a hard problem in PSPACE. We propose a scheduling approach, called Aggregated Critical Requests (ACR), which is based on the MDP formulation and present two algorithms based on this approach. ACR is designed for timely delivery of data to clients in order to maximize the reward by minimizing the deadlines missed. Results from trace-driven experiments indicate the ACR approach provides a flexible strategy that can outperform existing strategies under a variety of factors.     

Scheduling on-demand data broadcast in mixed-type request environments

In many on-demand broadcast environments, there can be a mix of requests, in which some of the requests have real-time constraints, while other requests have no time constraints associated with them. We refer to such environments as mixed-type environments. Existing strategies for on-demand data in broadcast systems typically only consider how to minimize the wait time of the requests, while scheduling strategies for real-time requests typically only consider how to minimize the number of deadlines missed. How to satisfy both of these constraints is a challenging problem whose solution can benefit many applications. In this paper, we present an on-demand broadcast cost model that is more general than existing broadcast cost models because it considers both response time and number of deadlines missed. An analysis of the system is presented as a Markov decision process to ascertain the feasibility of an optimal policy. We propose two scheduling strategies for mixed-type broadcast systems that are based on our cost model: maximum paid cost first and maximum value gained first. The simulation results show that both of our strategies always achieve the best result, when compared to existing broadcast strategies, for varying request arrival rates, real-time to non-real-time request ratios, missed deadline weight values, wait-time bounds on the non-real-time requests, and varying broadcast rates.     

实时环境下一种混合广播调度策略

在实时的非对称通讯环境下,自适应混合广播策略能够根据数据的请求模式以及时间限制等特征来动态分配周期广播和按需广播的带宽比例.将这一策略推广到基于事务的多数据项广播调度中,同时引入"分布式广播"思想,以更精细的周期广播粒度来解决过长的周期广播与事务及数据的实时要求之间的矛盾,并且动态分配时间槽.实验结果表明:改进的调度策略更适合于实时环境下的数据广播,具有更低的事务失败率以及更小的上行信道负荷.     

On the performance of real-time multi-item request scheduling in data broadcast environments

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and capability to handle dynamic data access patterns. Previous studies on time-critical on-demand data broadcast were conducted under the assumption that each client requests only one data item at a time. With the rapid growth of time-critical information dissemination services in emerging applications, there is an increasing need for systems to support efficient processing of real-time multi-item requests. Little work, however, has been done. In this paper, we study the behavior of six representative single-item request based scheduling algorithms in time-critical multi-item request environments. The results show that the performance of all algorithms deteriorates when dealing with multi-item requests. We observe that data popularity, which is an effective factor to save bandwidth and improve performance in scheduling single-item requests, becomes a hindrance to performance in multi-item request environments. Most multi-item requests scheduled by these algorithms suffer from a starvation problem, which is the root of performance deterioration. Based on our analysis, a novel algorithm that considers both request popularity and request timing requirement is proposed. The performance results of our simulation study show that the proposed algorithm is superior to other classical algorithms under a variety of circumstances.     

无线环境中的数据广播调度理论分析及算法研究

数据广播是无线环境中一种独特的数据发布方式。首先系统地归纳了周期广播、on-demand广播和混合广播3种广播方式的理论分析模型及其特点,然后针对单信道和多信道对各种广播方式的调度算法进行了分类、比较,并突出了理论模型对调度算法研究的指导价值。最后指出今后的研究方向。     

Wireless real-time on-demand data broadcast scheduling with dual deadlines

In this paper, issues involved in the design of real-time on-demand broadcast system which maintains data temporal constraints are discussed. We propose a new online scheduling algorithm, called RDDS that incorporates access frequency, data size, request-deadline and data-deadline of pending requests for real-time on-demand broadcast system with dual deadlines. Furthermore, the concepts of deferrable requests and non-deferrable requests are introduced, cases of non-deferrable requests are analyzed, and Non-deferrable Request First policy is proposed and integrated into RDDS to form another new algorithm, called RDDS-W. We have performed a series of simulation experiments to evaluate the performance of our algorithms as compared with other previously proposed methods. The experimental results show that our algorithms can substantially outperform other algorithms under a wide range of scenarios, especially when combining with Non-deferrable Request First policy, which improves the performance significantly.     

移动计算环境中的自适应混合广播

提出一种自适应混合广播算法。在周期广播数据分配时采用多信道非均匀分配,使高访问率的数据获得高广播频率。在确定周期广播数据和联机请求数据个数时考虑联机请求信道响应时间和访问率之间的关系,从而在少量比较次数后获得数据最佳分割点。实验结果表明,该算法可以根据系统负载和用户访问模式的变化动态调节信道和数据的分配,性能优于纯广播和纯基于请求的广播,访问时间少于现有的混合数据广播方式。     

移动实时数据库系统中的更新分发

数据广播作为移动计算环境下有效的数据分发技术已有许多研究,当数据广播用于发送不断更新的数据时称它为更新分发．现有的更新分发协议因没有考虑实时数据库系统中数据和事务的定时要求而不适合移动实时只读事务的处理．重点研究了移动实时数据库系统中更新分发的问题,提出了混合前向多版本数据广播协议,该协议在保证事务一致性的同时满足了数据和事务的定时约束．模拟实验表明,该协议能够有效地降低事务错过率和提高数据流行性,较现有更新分发协议更适合移动实时只读事务的处理．