臺灣博碩士論文加值系統

在行動環境下，行動裝置的電源能量相當有限，因此如何將能量的耗損降到最低，是一個很重要的議題。其中，將資料以索引的方式呈現在廣播頻道上，能方便使用者只需監聽他所需要的相關資訊即可，而不必浪費能量去監聽其不需要的資訊，如此便能省下許多的能量資源。
此外，我們可以很直覺的知道，使用者只有在他完全接收到其查詢內所需求的多筆資料時，才算是一個服務真正的完成，因此在廣播頻道的排序處理上，應以具有多筆資料的查詢為處理單位，並進一步分析查詢間的關係，才能算是真正且快速的滿足使用者的需求。
所以在本篇論文中，我們先針對簡易及父子關係的查詢來分類決定他們彼此之間在廣播頻道上的排列順序，接著，利用建立索引樹的方式，來節省行動設備在監聽廣播頻道上所不必要的能量耗損。最後我們以實驗模擬來驗證我們所提出的方法，實驗結果顯示我們的方法比過去只針對資料為單位所建的索引樹且未考量查詢間彼此關係的方式要來的好。

In a mobile environment, the battery power of mobile devices is precious. An indexing technique provides the selective tuning to reduce the cost of power consumption, that is, a mobile device only listens to necessary channel slots without listening to all slots. The cost parameter, tuning time, is used to measure the efficiency of scheduling indices and data items in the broadcast channel.
Intuitively, a mobile user gets satisfied with his submitted query only when he obtained all the data items in the query. Therefore, a query with multiple data items should be considered as a processing unit and the relationship of queries should be taken into further considerations. Hence, in this paper, we first determine the scheduling order of queries with simple and parent-child relationships in the broadcast channel. Then, an imbalanced index tree is built to efficiently reduce the cost parameter of the tuning time. At last, a simulation model is conducted and the experimental results show that our approach outperforms the previously proposed approach, which only concerns the index structure on the data items.

Chapter 1 Introduction
Chapter 2 Literature Survey
2.1 Techniques of data allocation
2.2 Techniques of indexing structure
2.2.1 Imbalanced index tree construction for fixed fanout
2.2.2 Imbalanced index tree construction for variant fanout
2.3 Scheduling queries with multiple data items
2.4 Discussion
Chapter 3 Index and Allocation Methods
3.1 Preliminary
3.2 The relationship of queries
3.3 Determine the order of queries
3.3.1 Queries with simple relationship
3.3.1.1 Queries with simple relationship divided into
more than one partition
3.3.2 Queries with parent-child relationship
3.4 Build an index tree
3.4.1 Problem statement
3.4.2 Determine the segmentation point
3.4.3 Adjust the index tree
Chapter 4 Experiment Results
4.1 Effect of the skew factor (α)
4.2 Effect of the number of queries
4.3 Effect of the maximum number of data items per query (M)
Chapter 5 Conclusions and Future Work
References

[1]S. Acharya, R. Alonso, M. Franklin and S. Zdonik, “Broadcast Disks: Data Management for Asymmetric Communication Environments,” Proc. ACM SIGMOD Conference, pages 199~210, 1995.
[2]S. Acharya, R. Alonso and S. Zdonik, “Dissemination-based Data Delivery Using Broadcast Disks,” IEEE Personal Communications, 2(6), 1995.
[3]M. Chen, P.Yu and K. Wu, “Indexed Sequential Data Broadcasting in Wireless Mobile Computing,” 17th IEEE International Conference on Distributed Computing Systems, pages 124~131, 1997.
[4]Y. D. Chung and M. H. Kim, “On Scheduling Wireless Broadcast Data,” Technical Report CS-TR-98-134, KAIST, Department of Computer Science, 1998.
[5]Y. D. Chung and M. H. Kim, “QEM: A Scheduling Method for Wireless Broadcast Data,” Proc. International Conference on Database Systems for Advanced Applications proceedings, pages 135~142, 1999.
[6]M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, CA, 1979.
[7]T.Imielinski, and S. Viswanathan, “Adaptive Wireless Information System,” Proc. SIGDBS Conference, 1994.
[8]T.Imielinski, S. Viswanathan, and B. R. Badrinath, “Energy Efficient Indexing on Air,” Proceedings of ACM SIGMOD, Minneapolis, MN, pages 25~36, May, 1994.
[9]G.K. Zipf, Human Behavior and the Principle of Least Effort : An Introduction to Human Ecology, Addison Wesley Press, Cambridge, Massachusetts, 1949.
[10]G. Lee, M. S. Yeh, S. C. Lo and Arbee L. P. Chen, “A Strategy for Efficient Access of Multiple Data Items in Mobile Environment,” Proc. International Conference on Mobile Data Management, 2002.
[11]K. Prabhakara, K.A. Hua and J. Oh, “Multi-Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment,” Proc. IEEE International Conference on Data Engineering, pages 167~176, 2000.
[12]K.Stathatos, N.Roussopoulos and J.S. Baras, “Adaptive Data Broadcast in Hybrid Networks,” Proc. VLDB Conference, pages 326~335, 1997.
[13]K. L. Tan and J. X. Yu, “An Analysis of Selective Tuning Schemes for Nonuniform Broadcast,” Data and Knowledge Engineering, Vol.22, No. 3, pages 319~344, 1997.
[14]//jwilson.coe.uga.edu/EMT668/EMAT6680.2001/Youn/EMAT6690/ Ins.%20Units/les4/lesson4.html, May 2003.