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

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

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.     

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.     

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

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

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

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

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.     

An energy efficient re-access scheme for data caching in data broadcast of a mobile computing environment

Data caching is used to improve the response time and the power consumption of a mobile client in a mobile computing environment. To enhance the performance of data caching, one needs to improve the hit ratio and to reduce the cost in processing a cache miss. In a mobile computing environment, a cached data item of a mobile client needs to remain up-to-date with respect to its corresponding data item in the server. A cached data item which is out of date is called a cached invalidated data item. Accessing a cached invalidated data item can be regarded as processing a cache miss. To access a cached invalidated data item, a mobile client needs to download the new content of the data item from the broadcast channel. This operation is called a re-access operation in this paper. Re-accessing a cached invalidated data item incurs large tuning time overhead. In this paper, we propose a re-access scheme that reduces this overhead by allowing a mobile client to access a cached invalidated data item from the broadcast channel without accessing indices. We analyze the performance of the proposed scheme and validate the analysis through experiments. The experiments showed that the proposed scheme significantly reduces the tuning time of a mobile client. Furthermore, the proposed scheme is robust in the sense that it allows changes on the broadcast structure in data broadcasting.     

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.     

Dependent data broadcasting for unordered queries in a multiple channel mobile environment

Data broadcast is a promising technique to improve the bandwidth utilization and conserve the power consumption in a mobile computing environment. In many applications, the data items broadcast are dependent upon one another. However, most prior studies on broadcasting dependent data are restricted to a single broadcast channel environment, and as a consequence, the results are of limited applicability to the upcoming mobile environments. In view of this, we relax this restriction and explore the problem of broadcasting dependent data in multiple broadcast channels. By analyzing the model of dependent data broadcasting, we derive several theoretical properties for the average access time in a multiple channel environment. In light of the theoretical results, we develop a genetic algorithm to generate broadcast programs. Our experimental results show that the theoretical results derived are able to guide the search of the genetic algorithm very effectively, thus leading to broadcast programs of very high quality.     

Tree-based data retrieval algorithm for multi-item request with deadline in wireless networks

The data retrieval problem in wireless communication has attracted increasing attentions in many applications such as electronic information sharing and e-business. However, most existing studies do not consider how to retrieve the requested data items in their deadlines. In this paper, we discuss the so-called deadline-based multi-item data retrieval problem, which aims at finding an access pattern for retrieving requested data items in certain deadlines such that the access latency and data miss rate are minimized. We propose two algorithms, named EDFS and UR, to deal with the above problem. The EDFS algorithm gives priority to retrieve the requested data item with the least deadline, while the UR algorithm introduces the urgent rate that is computed by the broadcast time and deadline of requested data item for further reducing the access latency and data miss ratio. Moreover, we design a tree-based data retrieval algorithm that finds the longest downloading sequence of data items in one broadcast cycle and is applied to EDFS and UR for finding data retrieval sequence of requested data items. The efficiency of our proposed schemes has been validated by the extensive experiments.     

Information delivery through broadcasting in satellite communication networks

Satellite broadcast is an important candidate for large-scale multimedia information distribution due to the inherent wide-range multicasting capability of satellites and the asymmetry of satellite communications (high bandwidth downlink, limited bandwidth uplink) that matches nicely the information flow asymmetry in multimedia applications. We consider a data broadcasting model that is encountered in most asymmetric satellite communication environments. The problem of scheduling the data broadcast such that average response time experienced by the users is low is considered. In a push-based system, where the users cannot place requests directly to the server and the broadcast schedule should be determined based solely on the access probabilities, we formulate a deterministic dynamic optimization problem, the solution of which provides the optimal broadcast schedule. Properties of the optimal solution are obtained and then we propose a suboptimal dynamic policy which achieves average response time close to the lower bound. In a pull-based system where the users may place requests about information items directly to the server, the scheduling can be based on the number of pending requests for each item. Suboptimal policies with good performance are obtained in this case as well. If a user has local memory, it can alleviate its access latency by selectively prefetching the items from the broadcast and storing them in the memory. A good memory management strategy can substantially reduce the user's access latency. An optimal memory management policy is identified, that minimizes the expected aggregate latency. Memory update strategies with limited look-ahead are presented as implementable approximations of the optimal policy as well. We also consider the problem of joint broadcast scheduling and user's cache management and propos a joint optimization scheme which can achieve the performance up to 40% better than the existing non-joint approach.     

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.     

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

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

Semantic Access to Multichannel M-Services

M-services provide mobile users wireless access to Web services. In this paper, we present a novel infrastructure for supporting M-services in wireless broadcast systems. The proposed infrastructure provides a generic framework for mobile users to look up, access, and execute Web services over wireless broadcast channels. Access efficiency is an important issue in wireless broadcast systems. We discuss different semantics that have impact on the access efficiency for composite M-services. A multiprocess workflow is proposed for effectively accessing composite M-services from multiple broadcast channels based on these semantics. We also present and compare different broadcast channel organizations for M-services and wireless data. Analytical models are provided for these channel organizations. Practical studies are presented to demonstrate the impact of different semantics and channel organizations on the access efficiency.     

A speculative load adaptive streaming scheme for efficient video delivery

Video on demand services require video broadcast schemes to provide efficient and reliable performance under various client request loads. In this paper, we have developed an efficient request load adaptive broadcast scheme, speculative load adaptive streaming scheme (SLAS), that requires lower service bandwidth than previous approaches, regardless of request rate. We have provided both analysis and simulation to show the performance gain over previous schemes. In this paper, we provide the theoretic upper bound of the continuous segment allocations on channels. We found that the number of allocated segments of the SLAS is close to the theoretic upper bound when compared with other schemes over various numbers of stream channels. Our analysis of client waiting time is almost identical to simulation results about all client requests. By simulation, we compared the required service bandwidth and storage requirements of the SLAS scheme and other schemes and found the SLAS scheme is an efficient broadcast scheme as compared to well known seamless channel transition schemes.     

Segmented patching broadcasting protocol for video data

In adaptive segment-based patching scheme, the video is divided into fixed number of segments, which are transmitted over the server channels. For efficient transmission of the video segments, the server channels are classified into two types – regular and patching channels. A regular channel generally transmits fixed number of segments and a patching channel helps transmitting those segments that cannot be provided by any regular channel to the users. The number of segments transmitted by the first regular channel is decided by the number of regular channels that are allocated to the video by the video server. Other regular channels transmit pre-specified number of segments. This scheme estimates the bandwidth of the patching channels based on the requests received at the video server in terms of fixed time intervals, called time slots. The bandwidth estimation in this scheme is less accurate because for multiple requests received in a time slot more than one patching channels are used. Second, the probability distribution considered in this scheme does not satisfy the basic rule, i.e., the sum of all probabilities is not 1. In this paper, we address these issues and propose a new protocol named as Segmented Patching Broadcasting Protocol for Video Data. The average server bandwidth allocated to the patching channels is much less as compared to the adaptive segment-based patching scheme because only one patching channel is sufficient for any number of requests received in a time slot.     

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.     

Exploiting skewed access and energy-efficient algorithm to improve the performance of wireless data broadcasting

As wireless networks become an integral component of the current communication infrastructure, energy efficiency is a crucial design consideration because of the limited battery life of mobile terminals. Data broadcast is an effective data dissemination method in mobile environments. The current air indexing schemes for data broadcast focused on energy efficiency (reducing tuning time) only, and current broadcast scheduling schemes reduce access latency through nonflat data broadcast to improve only responsiveness. Few studies have addressed energy efficiency and responsiveness issues concurrently. This study proposes a fast data access scheme that concurrently supports the energy saving protocol, which constructs broadcast channels according to the access frequency of each type of message to improve energy efficiency in mobile devices. The windmill scheduling algorithm that is presented in this paper was used to organize all types of messages in the broadcast channel in the most symmetrical distribution, to reduce tuning and access time. The performance of the proposed mechanism was analyzed, and the efficiency improvement over existing methods was demonstrated numerically. Results indicate that the proposed mechanism is capable of improving both tuning and access time because of the presence of skewness in the access distribution among disseminated messages.     

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

随着移动网络的不断发展,移动终端设备的计算能力与日俱增,越来越多的用户倾向于通过移动网络获取信息资源,这使得实时按需数据广播面临新的挑战：（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优于其他调度算法,并具有较强的自适应.     

A General Framework of Time-Variant Bandwidth Allocation in the Data Broadcasting Environment

Data broadcast is an advanced technique to realize large scalability and bandwidth utilization in a mobile computing environment. In this environment, the channel bandwidth of each channel is variant with time in real cases. However, traditional schemes do not consider time-variant bandwidth of each channel to schedule data items. Therefore, the above drawback degrades the performance in generating broadcast programs. In this paper, we address the problem of generating a broadcast program to disseminate data via multiple channels of time-variant bandwidth. In view of the characteristics of time-variant bandwidth, we propose an algorithm using adaptive allocation on time-variant bandwidth to generate the broadcast program to avoid the above drawback to minimize average waiting time. Experimental results show that our approach is able to generate the broadcast programs with high quality and is very efficient in a data broadcasting environment with the time-variant bandwidth.