Research On Data Broadcast Scheduling And Air Indexing In Wireless Environments

With the rapid development of wireless communication and computer technologies, wireless mobile computing is becoming to reality. Millions of mobile users can access a large variety of information through mobile devices anywhere and anytime. The concept of mobile computing emerged in the 1990s, and till now it obtains a lot of attraction from both research area and industrial area. The specific computing environment brings lots of new research issues and also many challenges.Asymmetric is a main characteristic of wireless network along with limited bandwidth, and the amount of concurrent mobile user is unpredictable. How to improve the scalability of a system in such environment is one of such challenges. Data broadcast is an efficient method to disseminate information in wireless environment. Frequently demanded data can be broadcast by the base station to the air through wireless channels, and by listening to the channel, mobile users can receive such information. A single broadcast of a data item can satisfy all the outstanding requests for that item simultaneously. Such system has the advantage of high scalability. Today data broadcast already has several successful applications in public data delivery, military area, etc.Two important performance metrics of data broadcast system are access time (AT) and tuning time (TT). To optimize these two metrics, data broadcast scheduling and air indexing technologies have been studied. This dissertation focuses on both these technologies, and the main efforts are on the following aspects:(1) The theoretical model of data broadcast scheduling. A non-linear programming model is put forward for multi-channel data broadcast scheduling, and Lagrange method is applied to solve this problem. We get the Multi-channel Square-Root Rule (MSRR) which indicates the condition to obtain the minimal average AT. This rule is general which can be applied to schedule variable-length data with skewed access probabilities on variable-bandwidth channels.(2) The scheduling method for data broadcast on one channel. The length of data broadcast cycle has important effect on the scheduling result. The formula to calculate the broadcast cycle length is introduced first and then based on this length, two algorithms are designed which can be applied to uniform-length data scheduling and variable-length data scheduling respectively. Both algorithms can obtain the average AT which is near optimal.(3) The scheduling method for multi-channel data broadcast. Based on MSRR, we propose a two-phase scheduling method for multi-channel data broadcast. In the first phase, data are partitioned onto each channel according to MSRR, and in the second phase, different one-channel scheduling algorithms can be adopted on each channel according to the skewness of data subset allocated on that channel. For the accuracy of MSRR, the two-phase scheduling method can achieve near optimal average AT and it can be applied in the general environments.(4) A flexible air indexing method. The original Flexible index has been improved, and with a little increase of AT, TT can be reduced greatly. And through the adjustment of several parameters, the compromise of AT and TT can be achieved with greater flexibility.