臺灣博碩士論文加值系統

隨著無線通訊日益蓬勃，基地台和行動客戶端的聯繫以及客戶端能源的運用更形重要。為了減少行動客戶端所裝備電池的能源消耗，目前解決方法是利用選擇性讀取的功能，由基地台建立適當的資料索引，使客戶端在讀取頻道時避免長時處於活動模式。為了減少資料讀取時間，需考慮目錄錯過和廣播週期長度，因此降低目錄錯過的機率和因索引空間所增長的廣播週期是目前主要的研究方向。 本研究的目的在於建立可彈性調整的索引機制，降低索引所需空間及目錄錯過機率。
鑒於傳統索引機制，如NSV96、IVB94a、IVB94b等方法所採用的資料指標，受限於所廣播的資料鍵值、週期長度、樹狀結構，無法有效改善客戶端能源消耗和資料讀取時間，因此本研究藉由觀察廣播週期的特性，將資料搜尋過程轉換成座標模型，利用此座標模型的參數建立具有彈性的資料索引，並提出保證客戶端不會錯過所要資料的預測演算法，最後針對不同層次的使用者效能需求提供參數調整策略。本研究搜尋資料所運用的指標不採用精準位置，而提供客戶端預測資料可能出現的範圍，將資料指標轉換成可彈性調整的格式，使得基地台建立資料索引時能根據不同需求調整參數。
由模擬結果顯示，本研究藉由整理廣播資料的相對關係，使索引空間大量減少。相較於(1，m)可因索引空間減少約2.5倍，降低讀取資料索引的能源消耗；在調整時間上可較彈性索引和雜湊機制各減少約46%、37%。由於預測索引可彈性調整索引空間和目錄錯過機率，藉由參數調整的實驗可發現，本機制可針對不同需求建立最佳的廣播參數。

Broadcasting is an essential paradigm to transport data and support scalability in the wireless environment. Traditional index-based broadcast schemes take advantage of tree structures for saving energy, but they record too much index information to make the broadcast cycle short. On the other hand, the hash scheme may suffer from longer broadcast cycles and data collision problems, resulting in longer access time and tuning time. In this study, we propose a novel broadcast scheme, named predictive indexing, which allows mobile clients to access data by predicting data locations in the broadcast cycle. The new scheme not only has very compact structure, but also is flexible enough to allow the server to adjust the index structure for saving energy or reducing access time. Experimental studies show that it outperforms the tree-based schemes 2.5 times in energy saving, while maintaining roughly the same access time. It also outperforms the flexible indexing 46% and the hash scheme 37%, respectively, in energy consumption.

目錄
第一章、導論…………………………………………………………… 1
第二章、相關研究………………………………………………………. 5
2.1 AHT索引機制…………………………………………………………. 5
2.2 單一頻道的索引機制…………………………………………………… 7
2.2.1 彈性索引機制(Flexible Indexing Scheme)……………………… 7
2.2.2 (1，m)索引機制…………………………………………………………….. 9
2.3 雜湊機制(Hash Scheme)..……………..………………………………... 11
2.4傳統廣播頻道架構………………………………………………………. 13
第三章、問題和方法描述………………………………………………… 16
3.1問題描述…………………………………………………………………. 16
3.2問題分析…………………………………………………………………. 17
3.3方法描述…………………………………………………………………. 18
3.3.1預測資料落點之模型…………………………………………….. 18
3.3.2 預測資料落點座標系之參數說明……………………………………... 20
3.3.2.1 伺服器所需處理函數………………………………….. 20
3.3.2.2 客戶端所需處理函數……………………………………………………. 22
3.4 廣播頻道預測索引機制………………………………………………… 23
3.4.1 預測索引結構……………………………………………………. 23
3.4.2 伺服器建構索引流程……………………………………………………... 26
3.4.3 客戶端讀取資料流程……………………………………………………... 27
第四章、預測索引機制參數設計………………………………………… 30
4.1 影響預測索引效能的參數……………………………………………... 30
4.2 改善預測索引效能的參數調整策略…………………………………... 34
4.2.1 調整基準點數目…………………………………………………. 34
4.2.2 調整鍵值斜率範圍的切割數目………………………………………… 36
4.2.3 調整基準鍵值斜率………………………………………………………… 38
4.3 利用可容忍誤差控制預測範圍………………………………………… 43
第五章、預測索引機制效能分析………………………………………… 46
5.1 空間需求………………………………………………………………… 46
5.2 讀取時間………………………………………………………………… 48
5.3 調整時間………………………………………………………………… 50
第六章、實驗及結果分析……………………………………………….. 52
6.1 效能評估參數…………………………………………………………… 52
6.2 實驗平台及資料………………………………………………………… 54
6.3 預測索引效能和參數調整策略的影響………………………………… 56
6.3.1 調整基準點數目對效能的影響………………………………… 56
6.3.2 調整基準斜率範圍的切割數目對效能的影響………………… 59
6.3.3 調整基準斜率對效能的影響……………………………………………. 62
6.4 效能比較………………………………………………………………… 66
6.4.1 改變廣播資料量對效能的影響………………………………………… 66
6.4.2 改變儲存桶容量對效能的影響………………………………………… 73
6.4.3 改變週期索引區段數對效能的影響………………………………….. 78
第七章、結論及未來工作………………………………………………… 83
參考文獻……………………………………………………………….. 85

[AFK95] S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, “Broadcast Disk Management for Asymmetric Communication Environment,” Proceeding of ACM SIGMOD Conference , May, 1995, pages 199-210.
[Bro92] T. Brown et.al., “The DATACYCLE Architecture,” Comm. ACM, 35(12), December 1992, pages 71-81.
[CK99] Y. D. Chung, and M. H. Kim, “QEM : A Scheduling Method for Wireless Broadcast Data,” Proceeding of the 6th International Conference on Database Systems for Advanced Application , April 19-21, 1999, pages 135-142.
[Gon95] V. Gondhalekar, Scheduling Periodic Wireless Data Broadcast, M.S.Thesis, The University of Texas at Austin, U.S.A., December, 1995.
[Good91] D. J. Goodman, “Trends in Cellular and Cordless Communications,” IEEE Communication Magazine, June 1991.
[HLL98] Q.Hu, D.L.Lee, and W.C.Lee,“A Comparison of Indexing Methods for Data Broadcast on the Air,”Proc. of the 12th International Conference on Information Networking, 1998, pages 656-659.
[IB94] T. Imielinksi, and B. Badrinath, “Mobile Wireless Computing : Challenges in Data Management,” Communication of the ACM, 37(10), October 1994, pages 18-28.
[IVB94a] T. Imielinski, S. Viswanathan, and B. Badrinath, “Energy Efficient Indexing on Air,” Proceeding of ACM SIGMOD Conference, 1994, pages 25-36.
[IVB94b] T. Imielinski, S. Viswanathan, and B. Badrinath, Data on Air : Organization and Access, Technical Report, Department of Computer Science, Rutgers University, U.S.A., 1994.
[IVB94c] T. Imielinski, S. Viswanathan, and B. Badrinath, “Power Efficient Filtering of Data on Air,” Proc. of the International Conference on Extending Database Technology, 1994, pages 245-258.
[JV98] S. Jiang, and N. Vaidya, Schedfsdauling Algorithms for a Data Broadcast System: Minimizing Variance of the Response Time, Technical Report 98-005, Computer Science, Texas A&M University, U.S.A., February 4, 1998.
[JW95] R. Jain, and J. Werth, Airdisks and AirRAID: Modeling and Scheduling Periodic Wireless Data Broadcast, DIMACS Technical Report 95-11, Rutgers University, U.S.A., May 1995.
[KKT93] H. Koch, L. Krombholz, and O. Theel, A Brief Introduction into the World of Mobile Computing, Technical Report THD-BS-1993-03, Department of Computer Science, University of Darmstadt, U.S.A., May 1993.
[LC00] S.C. Lo, and Arbee L.P. Chen,“Optimal Index and Data Allocation in Multiple Broadcast Channels, ” Proceeding of the 16th International Conference on Data Engineering, San Deigo, California, February 2000, pages 293-302.
[LL96a] W.-C. Lee, and D. L. Lee, “Using Signature Techniques for Information Filtering in Wireless and Mobile Environments,” Distributed and Parallel Databases, 4(3), 1996, pages 205-227.
[LL96b] D. L. Lee, and W. -C. Lee, “On Signature Caching of Wireless Broadcast and Filtering Services,” Proceeding of the 2nd International Mobile Computing Workshop, Hsinchu, Taiwan, March 25-27, 1996, pages15-24.
[SCB92] S. Sheng, A. Chandrasekaran, and R.W. Broderson, “A Portable Multimedia Terminal for Personal Communications,” IEEE Communications Magazine, December 1992, pages 64-75.
[SV96] N. Shivakumar, and S. Venkatasubramanian, “Efficient Indexing for Broadcast Based Wireless Systems,” Mobile Network and Applications, l(1), 1996, pages 433-446.
[TYE99] K. L. Tan, J. X. Yu, and P. K. Eng, “Supporting Range Queries in a Wireless Environment with Nonuniform Broadcast,“ Data & Knowledge Engineering, 29(4), 1999, pages 201-221.
[顏月珠91] 顏月珠, 統計學, 三民書局, 1991