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

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

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

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

多数据项广播调度策略

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

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

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

多数据项请求的多信道并行广播调度算法

为减少数据广播中用户请求的平均访问时间、提高广播性能,提出了一种新的基于减少数据访问冲突和应用重复广播技术的广播调度算法。该算法有效减少了多信道并行广播中多数据项请求的访问冲突,对热点数据项采取重复广播技术,极大地减少了对热点数据项请求的访问时间。仿真实验结果表明,该算法有效地降低了平均访问时间,提高了数据广播性能,特别是在访问概率偏斜率较大时具有更好的性能。     

一种利用信道侦听的IEEE 802.11自适应优化算法

提出一种适用于DCF(distributed coordination function)机制的自适应优化算法.该算法基于网络节点侦听信道得到的网络状态信息进行相关参数的自适应调整以获得最优的网络性能,称为CSB(channel sensing backoff)算法.算法采用了对节点的信道接入请求以概率参数P_T进行过滤的方法控制节点竞争接入信道的激烈程度.不同于已有的DCF机制优化方法,CSB算法的特点在于,在优化调整过程中不需要进行计算复杂的网络节点数量估计,并且可以在不同网络状态下始终围绕确定的优化目标进行参数优化调整.仿真实验结果表明,算法能够针对网络节点数量和分组大小改变等网络状态变化作出自适应的网络优化调整,并获得了系统吞吐量、碰撞概率、延迟、延迟抖动、公平性等多方面的性能改善.     

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

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

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

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

移动环境中数据广播的自适应可靠性研究

在移动计算环境中,数据广播已成为数据发布和获取的重要手段。为了提高数据广播的可靠性,使移动用户能有效的访问到所需数据项,提出一种移动环境下的自适应等距离广播算法。根据广播数据项的被干扰情况,对广播数据项的广播顺序进行等距离调度。最后通过性能分析表明该广播算法有效的提高了数据广播的可靠性。     

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

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

Channel dynamic adjustment in data broadcast

Data broadcasting has become the preferred method to dispense data to a large number of mobile users. Current researches on on-demand data broadcast mainly propose algorithms based on a single broadcast channel or fixed multi-channel, i.e., fixed channel model. As a result of the dynamic diversity of data characteristics and client demands, the fixed channel model faces significant challenges in parallel broadcast diverse data. Further, the dynamic adjustment of the broadcast channel (dynamic channel model) based on client requests is favorable to service quality because it determines the number and sizes of channels that adapt to client demand in real-time. However, the dynamic channel model has not yet been thoroughly investigated for on-demand wireless data broadcasts. Accordingly, in this paper, a channel dynamic adjustment method (CDAM) is proposed. The innovations behind CDAM lie in three aspects. First, a data item priority evaluation and selection algorithm (S-RxW/SL) is proposed for evaluating the priority of data items and selecting the high priority data items to be considered in a broadcast cycle. Second, a weight and size average cluster algorithm (WSAC) is proposed for mining data item characteristics and clustering them. Third, based on the clustering results of WSAC, a channel splitting and data allocation algorithm (CSDA) is proposed for dynamically splitting the channel and allocating data items to the corresponding sub-channel. We compare the proposed method with some state-of-the-art scheduling methods through simulation. The theoretical findings and simulation results reveal that significantly better request loss rate (LR) can be obtained by using our method as compared to its alternatives.     

Maintaining mobile transactional consistency in hybrid broadcast environments

Recently there have been attempts in several research areas at efficiently utilizing the resources of mobile computers. Considering the properties in mobile computing environments, push-based data dissemination systems have lately attracted considerable attention. However, skewed access patterns among mobile clients makes response time worse, and they prefer to send data requests to the server explicitly through an uplink channel. A broadcast supporting an uplink channel is called a hybrid broadcast. In this paper, we devise new transaction processing algorithms for hybrid broadcasts. It is assumed that data objects that the server maintains are divided into Push_Data for periodic broadcasting and Pull_Data for on-demand service. That is, clients have to explicitly request data objects in Pull_Data. Maintaining transactional consistency in this environment without much additional cost is our main concern. Finally, we evaluate performance behavior through simulation study.Received: 15 November 2002, Published online: 5 August 2004This work was done as part of the Information & Communication Fundamental Technology Research Program, supported by the Ministry of Information & Communication in the Republic of Korea.     

Scheduling time‐critical requests for multiple data objects in on‐demand broadcast

On‐demand broadcast is an effective data dissemination approach in mobile computing environments. Most of the recent studies on on‐demand data broadcast assume that clients request only a single‐data‐object at a time. This assumption may not be practical for the increasingly sophisticated mobile applications. In this paper, we investigate the scheduling problem of time‐critical requests for multiple data objects in on‐demand broadcast environments and observe that existing scheduling algorithms designed for single‐data‐object requests perform unsatisfactorily in this new setting. Based on our analysis, we propose new algorithms to improve the system performance. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

移动实时环境下一种改进的广播调度算法

在网络带宽不对称的移动实时环境中,数据广播是一种有效的数据访问方式。针对这种网络特性,分析了现今已经存在的某些广播调度算法。针对UFO算法,分别提出了SBS算法和CRS算法,它们从服务器、移动客户端两个方面进行了改进。两种算法可以根据给定的数据项访问概率分布,自动生成广播调度。通过理论分析和实验结果表明,该算法不会产生事务重启,并且可以有效减少数据的访问时间,使用户访问数据广播的平均等待时间最小。     

On-demand broadcast for multiple-item requests in a multiple-channel environment

On-demand broadcast is an effective approach to disseminating data in mobile computing environments. Substantial efforts have been devoted to improving the scheduling efficiency of on-demand broadcast. Previous studies focused mainly on the case of scheduling single-item requests in single-channel environments. However, requesting multiple dependent data items is common in many advanced applications such as electronic stock trading and traffic information enquiry services. In addition, multi-channel architectures are widely deployed in data broadcast systems. In this work, we investigate the issues arising in scheduling multi-item requests in multi-channel on-demand broadcast environments. Two problems, namely, the request starvation problem and the bandwidth utilization problem are identified in existing algorithms. To tackle the observed problems, an innovative algorithm is proposed. Results from our simulation study demonstrate the superiority of the proposed algorithm.     

An efficient nonuniform index in the wireless broadcast environments

Data broadcast is an efficient dissemination method to deliver information to mobile clients through the wireless channel. It allows a huge number of the mobile clients simultaneously access data in the wireless environments. In real-life applications, more popular data may be frequently accessed by clients than less popular ones. Under such scenarios, Acharya et al.’s Broadcast Disks algorithm (BD) allocates more popular data appeared more times in a broadcast period than less popular ones, i.e., the nonuniform broadcast, and provides a good performance on reducing client waiting time. However, mobile devices should constantly tune in to the wireless broadcast channel to examine data, consuming a lot of energy. Using index technologies on the broadcast file can reduce a lot of energy consumption of the mobile devices without significantly increasing client waiting time. In this paper, we propose an efficient nonuniform index called the skewed index, SI, over BD. The proposed algorithm builds an index tree according to skewed access patterns of clients, and allocates index nodes for the popular data more times than those for the less popular ones in a broadcast cycle. From our experimental study, we have shown that our proposed algorithm outperforms the flexible index and the flexible distributed index.     

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.     

Deterministic Broadcast and Gossiping Algorithms for Ad hoc Networks

We present in this paper three deterministic broadcast and a gossiping algorithm suitable for ad hoc networks where topology changes range from infrequent to very frequent. The proposed algorithms are designed to work in networks where the mobile nodes possessing collision detection capabilities. Our first broadcast algorithm accomplishes broadcast in O(nlog n) for networks where topology changes are infrequent. We also present an O(nlog n) worst case time broadcast algorithms that is resilient to mobility. For networks where topology changes are frequent, we present a third algorithm that accomplishes broadcast in O(Δ·nlog n + n·|M|) in the worst case scenario, where |M| is the length of the message to be broadcasted and Δ the maximum node degree. We then extend one of our broadcast algorithms to develop an O(Dn log n + D²) algorithm for gossiping in the same network model.