ABSTRACT
Broadcasting data delivery is rapidly becoming the good choice for disseminating information to a massive user population in many new application areas where the client-to-server communication is limited. There are two different ways of data dissemination. One is called push-based that the data items are broadcasted periodically in the channels, another one is called pull-based that the client requests a piece of data on the uplink channel and the server responds by sending this piece of data to the client. In push-based, most of the previous researches assume that each mobile client needs only one data item. However, in many situations, a mobile client might need more than one data item. In pull-based, the data items were broadcasted dynamically. Most of the previous researches assume that the data items which requested by the clients are of the same size. However, the data items may of different sizes in reality. In this thesis, we propose Improved QDS Expansion Method (Improved-QEM) and Heuristic On-line Algorithm to overcome the above two weaknesses, respectively. The issue of scheduling the broadcast data for the situation that each client may access multiple data items can not be simply considered as multiple subissues. There have been two methods was proposed, Query Expansion Method (QEM) and Modified Query Expansion Methods (Modified-QEM). These two methods are heuristic-based algorithm and do not provide the optimal solution. To improve the performance, our Improved-QEM is an efficient scheduling for query-set-based broadcasting, which is integrated with Query Expansion Method (QEM) and mining association rules technique. The mining association rules can globally find the data item sets (large itemsets) which are requested by clients, frequently. From our simulation results, we show that, as compared to the local optimal approach in the previous methods, our Improved-QEM can construct the schedule with the smaller TQD than that constructed by QEM and Modified-QEM, where TQD is denotes Total Query Distance and is proportional to the average access time. The on-line (push-based) algorithms are easy to adapt to time varying demands for the data items, which uses some decision-making mechanism to determine which data item is to be broadcasted next. Hence, when the number of data items is huge, it is important to schedule broadcasting program such that, it can provide the small overall mean access time. Therefore, Vaidya and Hameed have proposed two on-line algorithms, On-line Algorithm and On-line with Bucketing Algorithm. The main disadvantage of On-line Algorithm is the heavy run-time overhead and the main disadvantage of On-line Algorithm with Bucketing is the poor performance of the overall mean access time. Therefore, we propose the heuristic on-line algorithm to solve these two problems. From our simulation results, we show that our heuristic algorithm provides the performance that closes to the overall mean access time and has with low run-time overhead.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0725103-112230 |
| Date | 25 July 2003 |
| Creators | Hsieh, Wu-Han |
| Contributors | Tei-Wei Kuo, San-Yih Hwang, Chien-I Lee, Ye-In Chang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0725103-112230 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0015 seconds