基于请求的多信道多数据项广播调度算法*

通过改进多信道单数据项请求的数据广播调度算法中的两层调度策略,提出了信道分配+QEM的算法;实现了用多信道广播来广播多数据项的请求;通过减少数据访问冲突和信道跳转减少了访问时间。分析证明此方法是可行和有效的。     

多数据项广播调度策略

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

移动环境下多数据项请求的广播策略研究*

提出了一种移动环境下的多信道试探广播策略MCHM（multiple channel heuristic method）。该广播策略在多信道广播中采用高效的数据调度算法,在不重复广播的情况下,消除了多信道广播中多数据请求的访问冲突,大大减少了移动客户机的访问时间,提高了数据广播的性能。     

基于贪心策略的多信道数据广播调度算法

为减少多信道数据广播环境中的多信道平均延迟时间,提出一种基于贪心策略的多信道数据广播调度算法,将数据项合理地分配到各信道,最小化多信道数据项平均访问时间,在每个信道内采用近似最优的Log-time算法。实验结果表明,在不同的系统环境下,该算法都能够达到近似最优的性能。     

移动计算环境中数据广播的启发式遗传调度算法

数据广播调度是移动计算环境中数据管理技术的研究热点之一.现有的广播调度算法在移动数据库环境中缺乏一定的实用性.在数据项长度可变的条件下,理论上分析了多盘数据广播的平均访问时间,并提出了一种启发式的遗传调度算法,在广播调度中引入贪婪变换的启发式求解策略.理论分析和实验结果表明,该算法在访问概率偏斜率较大和数据项长度不等的情况下,平均访问时间较小,能很好的适应于移动数据库环境.     

非对称网络环境中数据广播的启发式多盘调度算法

在以无线网络为代表的非对称网络环境中,数据广播是一种有效的数据访问方式。针对非均匀的访问概率分布,我们分析了数据广播访问时间的最优值,并提出了一种启发式多盘调度算法（ＨＭＤ）,该算法能够根据给定的数据项访问概率分布,自动生成广播调度。 欠的理论分析和实验结果表明,ＨＭＤ算法是一种高效的数据广播调度算法,具有接近于理论最优值的性能,并且具有良好的可操作性。     

移动环境下多数据项请求广播的改进算法

在移动计算环境下,为提高多数据项请求广播的响应率,提高服务器的响应能力,研究了广播内容选择对响应率的影响,提出了一种新的广播内容选择方式,并对多数据项请求广播调度算法QEM（Query Extend Method）进行了改进。试验结果表明改进后的算法能进一步提高多数据项请求广播的响应率。     

无线环境中多数据项广播调度算法综述

数据广播是无线环境中信息传递的主要方式,其中多数据项广播是一个重要且具有挑战性的研究热点.对多数据项广播调度算法进行了综述.分类介绍了各种典型算法,并做了系统的比较和分析,最后讨论了该领域研究的未来发展方向.     

多盘广播的偏斜索引算法

在移动环境中,多盘广播是被广泛使用的数据广播调度算法之一。为广播数据建立索引可以使移动客户机选择性地监听信道,以减少电源消耗,但过多地插入索引会增加数据访问时间。针对该问题,为多盘广播建立偏斜索引,设计索引树构造算法和广播数据的索引树算法。与可变扇出算法相比,多盘广播的偏斜索引算法需要的平均访问时间和平均调谐时间较短。     

移动环境中请求多数据项的广播调度算法

提出移动环境中请求多数据项的广播调度算法——基于权重的调度算法(BWS)和权重比截止时间算法(WID)。BWS算法根据数据项对客户的满足情况确定权重,并以数据项的总权重作为调度的依据,同时考虑数据项的使用频率和数据项对于客户的满足情况。WID算法以总权重与截止时间的比值作为调度依据,同时考虑广播效率和紧急性的要求。在数据广播调度方面这2种算法比传统的算法具有更好的性能。     

A concurrency control scheme for mobile transactions in broadcast disk environments

Broadcast disk technique has been often used to disseminate frequently requested data efficiently to a large volume of mobile clients over wireless channels. In broadcast disk environments, a server often broadcasts different data items with differing frequencies to reflect the skewed data access patterns of mobile clients. Previously proposed concurrency control methods for mobile transactions in wireless broadcast environments are focused on the mobile transactions with uniform data access patterns. These protocols perform poorly in broadcast disk environments where the data access patterns of mobile transactions are skewed. In broadcast disk environments, the time length of a broadcast cycle usually becomes large to reflect the skewed data access patterns. This will often cause read-only transactions to access old data items rather than the latest data items. Furthermore, updating mobile transactions will be frequently aborted and restarted in the final validation stage due to the update conflict of the same data items with high access frequencies. This problem will increase the average response time of the update mobile transactions and waste the uplink communication bandwidth. In this paper, we extend the existing FBOCC concurrency control method to efficiently handle mobile transactions with skewed data access patterns in broadcast disk environments. Our method allows read-only transactions to access the more updated data, and reduces the average response time of updating transactions through early aborts and restarts. Our method also reduces the amount of uplink communication bandwidth for the final validation of the update transactions. We present an in-depth experimental analysis of our method by comparing with existing concurrency control protocols. Our performance analysis shows that it significantly decreases the average response time and the amount of uplink bandwidths over existing methods.     

Effective Generation of Data Broadcast Schedules with Different Allocation Numbers for Multiple Wireless Channels

Existing methods of scheduling data items over multiple wireless broadcast channels focus on the assignment of a data item to a channel. However, data items are not allocated more than once per broadcast cycle to a single channel. Our scheme considers the numbers of copies of a data item that should be allocated in the context of the channel assignment problem and aims to reduce the average data access time by allocating a popular data item more than once per cycle to the channel to which it is assigned. The number of times that each data item is allocated reflects its access probability. Simulation results show that our scheme reduces the average expected delay, especially when there are few channels.     

基于重复热点数据的CF广播结构改进算法*

针对现有广播结构构建中对数据访问概率倾斜度考虑不足的问题,在CF索引树的基础上提出了一种基于数据倾斜度的广播构建算法。该算法充分考虑热点数据的请求,根据数据在CF索引树中所处位置的不同,在一个广播周期内重复广播热点数据及其对应的索引节点,尽量减少移动用户的访问时间。最后通过实验验证了改进后广播结构的有效性。     

A tree-structured index allocation method with replication over multiple broadcast channels in wireless environments

Broadcast has often been used to disseminate frequently requested data efficiently to a large volume of mobile units over single or multiple channels. Since mobile units have limited battery power, the minimization of the access and tuning times for the broadcast data is an important problem. There have been many research efforts that focus on minimizing access and tuning times by providing indexes on the broadcast data. We have studied an efficient index allocation method for broadcast data with skewed access frequencies over multiple physical channels which cannot be coalesced into a single high bandwidth channel. Previously proposed index allocation techniques have one of two problems. The first problem is that they require equal size for both index and data. The second problem is that their performance degrades when the number of given physical channels is not enough. These two problems result in an increased average access time for the broadcast data. To cope with these problems, we propose a tree-structured index allocation method. Our method minimizes the average access time by broadcasting the hot data and their indices more frequently than the less hot data and their indexes over the dedicated index and data channels. We present an in-depth experimental and theoretical analysis of our method by comparing it with other similar techniques. Our performance analysis shows that it significantly decreases the average access and tuning times for the broadcast data over existing methods.     

An Efficient Algorithm for Near Optimal Data Allocation on Multiple Broadcast Channels

In a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. Data broadcast has become an excellent method for efficient data dissemination. In this paper, the problem for generating a broadcast program of a set of data items with the associated access frequencies on multiple channels is explored. In our approach, a minimal expected average access time of the broadcast data items is first derived. The broadcast program is then generated, which minimizes the minimal expected average access time. Simulation is performed to compare the performance of our approach with two existing approaches. The result of the experiments shows that our approach outperforms others and is in fact close to the optimal.     

无线数据广播中变长数据项偏斜调度算法

针对数据广播中用户访问时间最小化的问题,提出一种变长数据项的偏斜广播调度脱机算法。该算法在数据广播的平方根规则基础上,确定每个数据项的广播频率和在信道上的平均实例间隔,以此为依据选择生成周期广播序列。实验结果表明,该算法获得的平均访问时间接近于理论最优值,平均误差率在6%左右。     

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

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

Exploiting data mining techniques for broadcasting data in mobile computing environments

Mobile computers can be equipped with wireless communication devices that enable users to access data services from any location. In wireless communication, the server-to-client (downlink) communication bandwidth is much higher than the client-to-server (uplink) communication bandwidth. This asymmetry makes the dissemination of data to client machines a desirable approach. However, dissemination of data by broadcasting may induce high access latency in case the number of broadcast data items is large. We propose two methods aiming to reduce client access latency of broadcast data. Our methods are based on analyzing the broadcast history (i.e., the chronological sequence of items that have been requested by clients) using data mining techniques. With the first method, the data items in the broadcast disk are organized in such a way that the items requested subsequently are placed close to each other. The second method focuses on improving the cache hit ratio to be able to decrease the access latency. It enables clients to prefetch the data from the broadcast disk based on the rules extracted from previous data request patterns. The proposed methods are implemented on a Web log to estimate their effectiveness. It is shown through performance experiments that the proposed rule-based methods are effective in improving the system performance in terms of the average latency as well as the cache hit ratio of mobile clients.     

A hybrid scheduling scheme for data broadcast over a single channel in mobile environments

Various broadcast schemes have been proposed to reduce the data access time of mobile clients. However, they are based either on the mobile users’ data access frequencies or on the semantic relations of the data. In this paper, we present a hybrid data broadcast scheme based both on semantic relationships and access probabilities. The broadcast scheme we propose generates a broadcast sequence according to the semantic relationships and replicates popular data items several times according to the data access probabilities. The efficiency of our broadcast scheme is shown via performance evaluations.