由於行動裝置的能源十分有限，許多學者都致力於尋找在行動運算環境之中
降低的行動裝置能源使用量的方法。其中一種相當有效的方式，就是在廣播頻道中播放資料項目的索引。因此，在目前相關廣播環境的研究之中，有許多的結果都是有關於如何建立更有效的索引。為了能夠更進一步的降低能源的使用量，在本論文之中，我們提出了兩種嶄新的作法。在第一種作法之中，我們將快取在廣播頻道中播出的索引。並且我們也將談到如何使用已經被快取在客戶端的索引資料項目。此外，我們也提出了兩種索引快取空間的管理策略。 分別叫做:
lower-level-index-first， 簡稱為LLIF， 與 cut-plane-first，簡稱為CPF，兩種方式。 LLIF將優先快取索引樹底層的節點，而CPF則傾向於將索引樹的一組切面(cut-plane)保留在快取之中。 我們執行了廣泛的實驗，並將實驗結果與LRU
和LRFU兩種知名的快取管理方式比較。實驗的結果證明，索引快取將能有效的降低調校時間(Tuning time) 而並不會使反應時間(Access Time)增加。並且，針對調校時間而言，當客戶端對資料的喜好不集中時，CPF 的效果最好。而當客戶端的快取空間很小， 並且對資料的喜好十分集中時， LLIF將有最低的調校時間。 而針對反應時間而言， LLIF 的等待時間一直是最短的。

在論文中提出第二種方式之中，我們考慮客戶端使用資料快取來降低調校時間與反應時間的情況。為了要使快取資料項目可以用來回答客戶端的查詢，客戶端必須維護資料內容與伺服器端資料內容的一致性。當伺服器端資料內容改變時，客戶端必須由伺服器端取回新版本的資料內容後，才能用來回答查詢。這種由伺服器端取回新版本的資料內容的動作，在這篇論文中，我們定義為re-access。Re-access一個被異動過的快取資料項目是十分浪費時間與能源的。在這篇論文之中，我們利用過期資料項目中紀錄的bucket_id 來加速重新取得資料的過程。 我們稱這一個新的方式為 re-access scheme。 除了描述re-access scheme的詳細內容外，我們也透過模擬實驗與數學分析的方式來求算re-access scheme 的效率。 實驗的結果證明，re-access scheme確實能有效的降低重新取得一個快取資料項目時所需的調校時間。並且根據實驗結果，我們發現，當資料客戶端查詢頻率的很高或伺服器端異動資料頻率很低時，re-access scheme 將非常的有效率。 並且，re-access scheme 最大的特點是，當廣播結構發生改變時，re-access scheme 仍然可以使用。

Due to the limited power supply of mobile devices, much research has been done on reducing the power consumption in mobile computing environments. Since supporting indices on the broadcast data items can effectively reduce the power consumption of the mobile clients, most of the existing research on data broadcasting has focused on designing efficient indexing schemes. To further reduce the energy consumption, we propose in this thesis two novel approaches. In the first approach, we propose to cache indices on the mobile clients and use them to access the broadcast data items. To manage the cached indices, we propose two new cache management policies. The lower-level-index-first policy caches the index nodes that are at the lower level of the index tree, while the cut-plane-first policy caches the index nodes that belong to a cut-plane of the index tree. Through experiments, we compare the performance of the
two proposed policies with some existing policies in terms of tuning time and access time. The experiments show that index caching significantly reduces the tuning time of a mobile client without increasing its access time. In terms of tuning time, the experiments show that, when the access pattern of a mobile client is not skew, the cut-plane-first policy outperforms the lower-level-index first policy, LRU and LRFU. When the mobile client has limited cache and high skew of data access, the lower-levelindex- first policy outperforms the cut-plane-first policy, LRU and LRFU. In terms of access time, the lower-level-index first policy always outperforms the cut-plane-first
policy, LRU and LRFU.

In second approach, we explore the efficient data re-access problem in data broadcast of a mobile computing environment with data caching. Data caching is used in data broadcast with the aim of reducing both access time and tuning time. For the cache data items of a mobile client to be useful, they need to remain consistent with the source data items in the server. When the data items are updated in the server, a mobile client needs to access the new content of its cached data items from the server.
The operation to access the new content of a cached data item is called a re-access operation in this thesis. The re-access operation is time- and energy-consuming since a mobile client needs to tune in to the broadcast channel for the data item. In this thesis, we propose to uses the bucket id of a cached data item to speed up the reaccess operations. We call this approach the re-access scheme. We analyze the performance of the re-access scheme and validate the analysis results through experiments. The experiments show that the re-access scheme improves the performance of data caching by significantly reducing the tuning time in re-accessing a data item. The experiments
also show that the proposed re-access scheme is especially effective when the query frequency on the mobile client is high or when the data update frequency on the server is low. Besides, the proposed re-access scheme is robustness in the sense that it allows the broadcast server to update its broadcast structure in data broadcasting.

[1] T. Imielinski and B.R. Badrinath. Mobile wireless computing: Challenges in
data management. Communication of ACM, 37(10):18–28, 1994.

[2] J. Jing, A. Helal, and A. Elmagarmid. Client-server computing in mobile computing environments. ACM Computing Surveys, 31(2):118–157, 1999.

[3] D. Barbara. Mobile computing and database — a survey. IEEE Transaction on
Knowledge and Data Engineering, 11(1):108–117, 1999.

[4] M. H. Dunham and A. HELAL. Mobile computing and databases: Anything
new? SIGMOD Records, 24(4):5–9, 1995.

[5] K.-L. Tan and B.C. Ooi. Data Dissemination in Wireless Computing Environments. Kluwer Academic Publishers, 2000.

[6] R. Alonso and S. Ganguly. Query optimization for energy efficiency in mobile computing environments. In Proceedings of the 1993 Workshop on Optimization in Databases, September 1993.

[7] R. Alonso and H. Korth. Database systems in nomadic computing. In Proceedings of the 1993 ACM-SIGMOD International Conference on Management of data, pages 388–392, June 1993.

[8] S. Sheng, A. Chandrasekaran, and R. W. Broderson. A portable multimedia
terminal. IEEE Communications Magazine, 30:64–751, 1992.

[9] S. Acharya, R. Alonso, M. Franklin, and S. Zdonik. Broadcast disks: Data
management for asymmetric communications environments. In Proceedings of
the ACM SIGMOD Conference, pages 199–210, 1995.

[10] G.H. Forman and J. Zahorjan. The challenges of mobile computing. IEEE
Computers, 27(6):38–47, 1994.

[11] Jianliang Xu. Client-side data caching in mobile computing environments. PhD thesis, The Hong Kong University of Science and Technology, 2002.

[12] S.K. Madria and S.S Bhowmick. Mobile data management. IEEE Potentials,
20, October/November 2001.

[13] David J. Goodman. The wireless internet: Promises and challenges. IEEE
Computer, 5, 1999.

[14] J. Wong M. Ammer. The design of teletext broadcasts cycles. Performance
evalution, 5, 1985.

[15] G. Herman, K. Lee, and A. Weinrib. Datacycle architecture for very high
throughput database systems. In Proceedings of the ACM SIDMOD Conference,
pages 00–00, 1987.

[16] T. Imielinski, S. Viswanathan, and B.R. Badrinath. Data on air : Organization and access. IEEE Transaction on Knowledge and Data Engineering, 9(3):353– 372, 1997.

[17] S. Acharya. Broadcast Disks: Dissemination-based Data Management for Asymmetric Communication Environments. PhD thesis, Brown University, 1998.

[18] Ambient Devices Inc. Ambient Information Network and Device Design, 2005.

[19] Microsoft Corporation. DirectBand Network. Microsoft Smart Personal Objects Technology (SPOT), 2005.

[20] SkyTel Corporation. Timex Internet Messenger, 2005.

[21] S. Acharya, M. Franklin, and S. Zdonik. Disseminating updates on broadcast
disk. In Proceedings of the 22th International Conference on Very Large Data
Bases, pages 354–365, 1996.

[22] C.J. Su and L. Tassiulas. Joint broadcast scheduling and user’s cache management for efficient information delivery. ACM Wireless Networks, 6, 2000.

[23] E. Yajima, T. Hara, M. Tsukamoto, and S. Nishio. Scheduling and caching
strategies for broadcasting correlated data. In Proc. of the 16th ACM SAC 2001
symposium on Applied computing, 2001.

[24] S. Acharya, M. Franklin, and S. Zdonik. Prefetching from a broadcast disk.
In Proceeding of the 12th International Conference on Data Engineering, pages
276–285, 1996.

[25] M. H. Ammar and J.Wong. On the Optimality of Cyclic Transmission in Teletext Systems. IEEE Trans. on Communications, 35(1):68–73, 1987.

[26] V. Gondhalekar, R. Jain, and J. Werth. Scheduling on airdisks: efficient access to personalized information services via periodic wireless data broadcast. In Proceedings of 1997 International Conference on Communications Towards the Knowledge Millennium, pages Vol. 3, 1276–1280, 1997.

[27] S. Hameed and N. H. Vaidya. Efficient algorithms for scheduling single and multiple channel data broadcast. Technical Report 97-002, Department of Computer Science, A&M University, 1997.

[28] S. Hameed and N. Vaidya. Efficient algorithm for scheduling data broadcast. Wireless Networks, 5:183–193, 1999.

[29] R. Jain and J. Werth. Airdisks and airRAID: Modeling and Scheduling Periodic wireless Data Broadcast. SIGARCH Comput. Archit. News, 23(4):23–28, 1995.

[30] L. Lin and Z. Xingming. Heuristic MultiDisk Scheduling for Data Broadcasting. In WOSBIS 1997, pages 1–5, 1997.

[31] W. C. Peng and M. S. Chen. Dynamic generation of data broadcasting programs for a broadcast disk array in a mobile computing environment. In Proceedings of the 9th International Conference on Information Knowledge Management, pages 38–45, 2000.

[32] K. Prabhakara, K. A. Hua, and J. H. Oh. Multi-Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment. In ICDE 2000, pages 167– 176, 2000.

[33] D. Aksoy and M. J. Franklin. RxW: A Scheduling Approach for Large-Scale
On-Demand Data Broadcast. TON, 7(6):846–860, 1999.

[34] A. Datta, D. VanderMeer, A. Celik J. Kim, and V. Kumar. Broadcast Protocols to Support Efficient Retrieval from Databases by Mobile Users. ACM Trans. on Database Systems, 24(1):1–79, 1999.

[35] T. Imielinski, S. Viswanathan, and B.R. Badrinath. Energy efficient indexing on air. In Proceedings of the ACM SIDMOD Conference, pages 25–36, 1994.

[36] T. Imielinski, S. Viswanathan, and B.R. Badrinath. Power efficient filtering of data on air. In Proceeding of the 4th International Conference on Extending Database Technology: Advance in Database Technology, pages 245–258, 1994.

[37] W.C. Lee and D.L. Lee. Using signature techniques for information filtering in wireless and mobile environments. Journal on Distributed and Parallel Databases, 4(3):205–227, 1996.

[38] K.-L. Wu M.-S. Chen and P.S. Yu. Optimizing index allocation for sequential data broadcasting in wireless mobile computing. IEEE Transaction on Knowledge and Data Engineering, 15(1):161–173, 2003.

[39] N. Shivakumar and S. Venlatasubramanian. Efficient indexing for broadcast
based wireless systems. Mobile Networks and Applications, 1:433–446, 1996.

[40] K. L. Tan and J. X. Yu. Energy Efficient Filtering of Nonuniform Broadcast. In 16th International Conference on Distributed Computing Systems, pages 520–528, 1996.

[41] Q. Hu, W.C. Lee, and D.L. Lee. Power conservative multi-attribute queries on data broadcast. In Proceeding of the 16th International Conference on Data
Engineering, pages 157–166, 2000.

[42] Q. L. Hu, W. C. Lee, and D. L. Lee. A Hybrid Index Technique for Power
Efficient Data Broadcast. DPDB, 9(2):151–177, 2001.

[43] D. Barbar´a and T. Imielinski. Sleepers and workaholics: Caching strategies in mobile environments. In Proceedings of the ACM SIDMOD Conference, pages 1–12, 1994.

[44] J. Cai and K.-L. Tan. Energy-efficient selective cache invalidation. Wireless Networks, 5(6):489–502, 1999.

[45] B.C. Ooi K.L. Tan, J. Cai. An Evalution of Cache Invalidation Strategies in Wireless Environents. IEEE Trans. on Parallel and Distributed Systems, 12:789–807, 2001.

[46] Y.Ijiri and H.Simon. Skew Distributions and the Sizes of Business Firms. North-Holland, New York, 1977.

[47] et al. D. Lee. Lrfu: A spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Trans. on Computer, 50, 2001.

[48] B. Walke G. Brasche. Concepts, services, and protocols of the new gsm phase 2+ general packet radio service. IEEE Communications Magazine, 35, 1997.

[49] Brian Davis Trevor Mudge Vinodh Cuppu, Bruce Jacob. A performance comparison of contemporary DRAM architectures. In Proc. of annual international
symposium on Computer architecture, pages 94–104, 1997.

[50] D.P. Bertsekas and J.N. Tsitsiklis. Introduction to Probability. Athena Scientific,2002.