With the big improvement of wireless technology, people can get their desired information at any time and any place. Due to communication asymmetry - physical asymmetry and/or information ow asymmetry, broadcast data deliv- ery is rapidly becoming the method of choice for disseminating information from server to clients. The main advantage of broadcast delivery is its scalability: it is independent of the number of users the system is serving. Acharya et al. have proposed the use of a periodic dissemination architecture in the context of mobile systems, called Broadcast Disks. Broadcast Disks can construct a mem- ory hierarchy in which the highest level contains a few items and broadcasts them with high frequency while subsequent levels contain more and more items and broadcast them with less and less frequency. However, based on Acharya et al.'s approach, some broadcast slots may be unused, which resulting in the waste of bandwidth and the increase of access time. Yang has presented a com- plementary approach to solve the empty slots problem, which also reduces the mean access time. However, based on the complementary approach, the dis- tances between slots containing the same page may not be a constant, resulting in an increase of the mean access time. Therefore, in this thesis, we propose two eÆcient broadcast programs to mitigate the above phenomenon and also to solve the empty slots problem. The rst one is a revised version of the com- plementary approach, and the second one is an adaptive approach. Most of the previous approaches assume that each mobile client needs only one data page. However, in many situations, a mobile client might need data of more than one page. Ke has proposed the SNV strategy for query set broadcast scheduling in multiple channels. In the SNV strategy, the data pages of the same query set are put as together as possible and it tries to avoid scheduling two or more pages of one query set at the same time slot of di erent channels. However, there are two disadvantages in the SNV strategy: (1) a data page with high access frequency may be scheduled at a time slot near the end of the broad- cast cycle, which results in the longer access time for requiring the whole query sets; (2) it may extend the number of slots in a certain chain, which results in the wasteness of bandwidth of the other channels. Therefore, we propose an eÆcient broadcast scheduling strategy, the Hybrid Version of the Set-based strategy ( HVS ) to improve these two disadvantages. From our performance analysis and simulation, we show that both our revised version of the com- plementary approach and adaptive approach create smaller number of slots in one broadcast cycle than Acharya et al.'s algorithm and require shorter mean access time than Acharya et al.'s algorithm and the complementary approach. Moreover,from our performance analysis and simulation, we also show that our HVS strategy requires shorter total expected delay access time, and creates smaller number of slots and smaller number of empty slots in one broadcast cycle than the SNV strategy.

With the increasing acceptance of wireless technology, mechanisms to efficiently transmit information to wireless clients are of interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. It has been proposed that in such systems, the server should broadcast the information periodically. Acharya et al. have proposed the use of a periodic dissemination architecture in the context of mobile systems, called Broadcast Disks. Using Broadcast Disks can construct a memory hierarchy in which the highest level contains a few items and broadcasts them with high frequency while subsequent levels contain more and more items and broadcast them with less and less frequency. In this way, one can establish a trade-off between access time for high-priority data and that of the low-priority items, where access time means that the time elapsed from the moment a client submits a query to the receipt of data of his (her) interest on the broadcast channel. A broadcast schedule specifies when and where each data page is to be transmitted. (Note that the smallest logical unit of the broadcast data is called a data page which is made up by data items. The time required to broadcast a data page is referred to as a time slot.) However, based on Acharya et al.'s algorithm, some broadcast slots may be unused, which resulting in the waste of bandwidth and the increase of access time, if it is not possible to evenly divide the number of broadcast pages assigned on a disk into the required number of chunks. (Note that each disk is split into a sequence of smaller units called chunks.) Therefore, in this thesis, we propose two efficient broadcast programs in which no empty slots is wasted. The first one is the binary-number-based approach and the second one is the complementary approach. In the binary-number-based approach, the broadcast frequency must be restricted to a value of 2^n , n¡Ù0, i.e. 1, 2, 4, 8..., etc; while in the complementary approach, there is no restriction on the broadcast frequency. From our performance analysis and simulation, we show that both of our proposed two approaches generate a small number of slots in one broadcast cycle (i.e., a shorter broadcast cycle) and shorter mean access time than Acharya et al. algorithm. Moreover, our first approach (the binary-number-based approach) requires a smaller number of slots in one broadcast cycle and shorter mean access time than the second approach (the complementary approach); however, there is some restriction on the chosen frequency in the first approach. Therefore, each of our proposed approaches has its own advantages and applicable domains, and both of them can avoid the wasteness of bandwidth and reduce the waiting time of clients.