臺灣博碩士論文加值系統

論文摘要

隨著無線通訊科技的快速發展，行動計算的可行性變的可能。人們帶著電力有限的行動通訊設備，可以在任何時間地點存取各式各樣的資訊。但是囿於行動通訊環境的限制，例如窄小的頻寬與有限的電池容量，現行的無線通訊服務受到限制。在這個議題上，資料廣播是一個誘人的解決方法。相對於傳統的點對點通訊，透過廣播頻道來傳遞資料允許眾多的使用者同時擷取資訊，因此更有效地使用有限的頻寬。
有時候廣播頻寬是由好幾個頻道所組成的，而這些頻道被配置在不連續的頻譜上，而且不能合成一個頻道。運用多個頻道有其好處。例如，有較好容錯能力，能夠重組與擴充。在這篇論文裡，我們探討在多個廣播頻道下的兩個議題。一是考慮如何安排將資料項目分配於各個廣播頻道中，二是行動通訊使用者如何在各個頻道裡快速尋找到其所需要的資料項目。無線通訊傳播主要的效能判斷標準在於存取效率和能源保存。存取效率與滿足使用者的要求反應快慢有關，而存取時間 (access time) 則常被用來衡量存取效率。能源保存影響使用者存取資料時電力的節省，而調校時間 (tuning time) 則被用來衡量能源保存。
循環不斷地將資料廣播於一個頻道上是一種基本的廣播排程，稱之為基礎廣播。當有多個廣播頻道存在時，需要一種資料分配機制將資料項目分配到各個頻道。由於資料項目的存取機率各不相同，有些頻道保留給少數幾個經常被存取的資料項目，而多數不常被存取的資料項目則分配到其餘的頻道。這種資料配置稱為歪曲配置。在第三章中，假設每個廣播頻道皆為基礎廣播，我們探討如何將N個資料項目分配到K個廣播頻道上的歪曲配置，我們的目標是極小化使用者的平均存取時間。文獻上知名的DP資料配置機制是一種最佳的資料配置法，它採用直接的dynamic programming方法，其成本高達O(KN2)。我們提出一種restricted dynamic programming (RDP)資料配置法來達成近似最佳的資料配置，而成本只要O(NlogK)。模擬實驗的結果顯示RDP高達 90% 能達成最佳解，而其成效優於同類型的方法的兩倍。接著藉由最佳曲線擬合技巧，我們更進一步地改進RDP演算法而發展出O(NlogNlogK)的PKR演算法。模擬實驗的結果顯示PKR達成最佳解。
在第四章中我們探討如何快速存取在多個廣播頻道上播放的資料。如果行動使用者事先不知道資料如何配置到各個頻道，在最差的情況下，使用者找到其所需的資料項前可能要搜尋所有的頻道。我們提出加入索引資訊於一個眾人皆知的索引廣播頻道來幫助使用者搜尋資料項目。我們考慮存取資料的協定與資料結構來有效地使用多個廣播頻道。資料組織的安排包含二個步驟。首先將資料依其受歡迎程度安排到各個頻道，這藉由PKR演算法來完成。其次對於每一資料廣播頻道上的資料，藉由key值我們建立一類似二元樹的索引樹。然後將每一棵樹上的節點multiplex到索引頻道。當行動通訊者意圖抓取某一資料時，首先調頻到知名索引頻道以便獲取該資料項將於何時於何頻道播放。隨後即進入省電模式直到要播放該資料項的前刻。我們的方法將索引與資料項安排成為依受歡迎程度的階層組織，使得較熱門的索引與資料項被廣播的次數比較不熱門的索引與資料項多了許多。模擬實驗的結果顯示我們所提出的方法比以前的方法在使用者的平均存取時間上少了48%，但只伴隨少許的調校時間負擔。

Abstract
With the rapid development of wireless communication technology, mobile computing becomes possible. People with battery-limited mobile devices can access various kinds of information from anywhere at anytime. However, existing wireless services are limited by the constraints of mobile environments such as narrow bandwidth, frequent disconnections, and limited battery capacity. Data broadcast is an attractive approach in such context. Disseminating data through a broadcast channel allows simultaneous access by an unlimited number of mobile clients and thus allows efficient usage of scarce bandwidth.
Sometimes the broadcast bandwidth is composed of multiple channels, where channels are allocated on discontinuous spectrums and can not be combined to a shared channel. The use of multiple channels allows better fault tolerance, configurability, and scalability. In this dissertation, we consider two issues arises in case multiple broadcast channels are present: i) how should the broadcast data be allocated to various channels, and ii) how should mobile clients surf the channels to obtain the data of interest.
Access efficiency and energy conservation are two main performance issues in wireless broadcast system. Access efficiency concerns how fast a request is responded, and energy conservation concerns how to conserve a client’s battery power when it accesses the desired data. Efficient data accesses to multi-channel broadcast programs are motivated by the desire to satisfy client requirement efficiently with as little consumption of energy as possible.
Cyclically broadcasting data over a channel is a basic scheduling approach called flat broadcast. When multiple channels are available, a data allocation scheme is needed to assign data to channels. Some channels may be reserved for those few frequently requested items, while the infrequently accessed bulk of data are allocated on other channels, this kind of allocation scheme called skewed allocation. In view of data access skew (the access probabilities of data items are usually different), in Chapter 3, we study the problem of broadcasting N data items over K channels assuming skewed data allocation and flat broadcast per channel, with the object of minimizing the average expected delay of the clients. The previously known DP algorithm is a straightforward dynamic programming implementation to partition data items and achieves an optimal solution with cost O(KN2). We propose a restricted dynamic programming (RDP) approach to achieve a similar performance to DP while with a much cheaper cost O(NlogK). Simulation results show that, the hit rate obtained by RDP is higher than 90% and it also outperforms similar work 200%. By using the curve fitting technique, we further refine RDP and develop an O(NlogNlogK) PKR algorithm; simulation results show that the solution is optimal
In Chapter 4, we study fast access to data that are broadcast on multiple channels. If a client has not a priori knowledge of how data are allocated to them, in the worst case a client may have to scan all the channels before finding the desired data. We consider the access protocol and structure for making effective use of multiple channels. We propose adding index information to a skewed data allocation on a well-known index channel to help clients surf on data channels. Our solution consists of i) organizing data by popularity, which is done by PKR data allocation scheme; ii) organizing data by key, which is done by supplementing an index search tree for each data channel. Then nodes of all index trees are multiplexed onto a well-known index channel. Our method organizes data and index into a popularity hierarchy, thus the popular data and their indices are broadcast more frequently than less popular data and their indices. Simulation results show that the reduction of access time is on average about 48% over previous work with little tuning time overhead.

Table of Contents

Abstract in Chinese I
Abstract III
Acknowledgement V
Table of Contents VI
List of Figures VIII
List of Tables VX
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Wireless Data Broadcast 2
1.3 Challenges 3
1.4 Multiple Channels 4
1.5 Contributions and Organization of the Dissertation 5
Chapter 2 Literature Review 7
2.1 Broadcast Scheduling on a Single Channel 8
2.1.1 Push-Based Broadcast 8
2.1.2 On-demand Broadcast 10
2.1.3 Hybrid Broadcast 11
2.2 Air Indexing on a Single Channel 13
2.3 Data Allocation on Multiple Channels 17
2.4 Air Indexing on Multiple Channels 19
Chapter 3 Near-Optimal Data Allocation over Multiple
Broadcast Channels 23
3.1 Introduction 23
3.2 Preliminaries 26
3.2.1 System Model 26
3.2.2 Problem Statement 26
3.2.3 Motivation 27
3.3 A Restricted Dynamic Programming Algorithm 29
3.3.1 Predication of Optimal Cut Points 29
3.3.2 Preclude Computing Unnecessary opt Entries 30
3.3.3 The RDP Algorithm 30
3.4 Performance Evaluation on RDP 33
3.5 An Improvement on Estimation of aed 35
3.5.1 Lower Bound vs. Optimal 35
3.5.2 A Function to Estimate Factor 37
3.6 Performance Evaluation on pkr 41
3.6.1 Hit Rate 41
3.6.2 Computation Time 41
Chapter 4 An Efficient Index Allocation Method for
Multi-Channel Data Broadcast 44
4.1 Introduction 44
4.2 Related Work 45
4.3 TMBT 46
4.3.3 Index Organization on Index Channel 48
4.3.2 Client Access Protocol 50
4.3.3 Index Replication 52
4.4 Analytical Evaluation of Average Access Time 53
4.5 Simulation Results 55
4.5.1 Effects of R 56
4.5.2 Effects of Efficient Data Allocation Scheme 59
4.5.3 Varying N, K, and ratio 59
Chapter 5 Conclusions 61
References 63
Publication List 70
Biography 71

References
[1]S. Acharya, R. Alonso, M. J. Franklin, and S. Zdonik. Broadcast Disks: Data Management for Asymmetric Communications Environments. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 199-210, May 1995.
[2]S. Acharya, M. J. Franklin, and S. Zdonik. Balancing Push and Pull for Data Broadcast. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 183-194, May 1997.
[3]S. Acharya and S. Muthukrishnan. Scheduling On-Demand Broadcasts: New Metrics and Algorithms. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom), pages 43-54, October 1998.
[4]D. Aksoy and M. J. Franklin. RxW: A Scheduling Approach for Large-Scale On-Demand Data Broadcast. IEEE/ACM Transactions on Networking, 7(6): 846-860, 1999.
[5]M. S. Chen, K. L. Wu, and P. S. Yu. Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing. IEEE Transactions on Knowledge and Data Engineering, 15(1): 161-173, January/February 2003.
[6]G. Cormode and S. Muthukrishnan. What's Hot and What's Not: Tracking Most Frequent Items Dynamically. In Proceedings of the ACM PODS Symposium on Principles of Database Systems, pages 296-306, 2003.
[7]A. Datta, D. E. VanderMeer, A. Celik, and V. Kumar. Broadcast Protocols to Support Efficient Retrieval from Databases by Mobile Users. ACM Transactions on Database Systems, 24(1):1-79, March 1999.
[8]S. Hameed and N. H. Vaidya. Efficient Algorithms for Scheduling Data Broadcast. Wireless Networks, 5(3):183-193, 1999.
[9]A. Y. Ho, D. L. Lee. Data Indexing for Heterogeneous Multiple Broadcast Channel. In Proceedings of the IEEE International Conference on Mobile Data Management (MDM), pages 274-283, 2004.
[10]C. H. Hsu, G. Lee, A. L. P. Chen. A Near Optimal Algorithm for Generating Broadcast Programs on Multiple Channels. In Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM), pages 303-309, 2001.
[11]C. Hsu, G. Lee, and A. L. P. Chen. Index and Data Allocation on Multiple Broadcast Channels Considering Data Access Frequencies. In Proceedings of the IEEE International Conference on Mobile Data Management (MDM), pages 87-93, January 2002.
[12]T. C. Hu and A. C. Tucker. Optimal Computer Search Trees and Variable-Length Alphabetical Codes. SIAM Journal of Applied Mathematics, 21(4):514-532, 1971.
[13]Q. Hu, D. L. Lee, W. C. Lee. Performance Evaluation of a Wireless Hierarchical Data Dissemination System. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom), pages 163-173, August 1999.
[14]J. Hu, K. L. Yeung, G. Feng, and K. F. Leung. A Novel Push-and-Pull Hybrid Data Broadcast Scheme for Wireless Information Networks. In Proceedings of IEEE International Conference on Communications (ICC), pages 1778-1782, June 2000.
[15]Q. Hu, W. C. Lee, D. L. Lee. A Hybrid Index Technique for Power Efficient Data Broadcast. Distributed and Parallel Databases, 9(2):151-177, 2001.
[16]C. L. Hu and M. S. Chen. Dynamic Data Broadcasting with Traffic Awareness. In Proceedings of the IEEE International Conference of Distributed Computing Systems, pages 112-119, July 2002.
[17]Hughes Network Systems, http://www.direcway.com, 2006.
[18]T. Imielinski, S. Viswanathan, and B. R. Badrinath. Power Efficient Filtering of Data on Air. In Proceedings of the International Conference on Extending Database Technology (EDBT), pages 245-258, March 1994.
[19]T. Imielinski, S. Viswanathan, and B.R. Badrinath. Data on Air Organization and Access. IEEE Transactions on Knowledge and Data Engineering. 9(3): 353-372, May/June 1997.
[20]K. F. Jea and M. H. Chen. A Data Broadcast Scheme Based on Prediction for the Wireless Environment. In Proceedings of the International Conference on Parallel and Distributed Systems (ICPADS), pages 369-374, December 2002.
[21]S. Jiang and N. H.Vaidya. Scheduling Data Broadcast to Impatient Users. In Proceedings of the ACM International Workshop on Data Engineering for Wireless and Mobile Access, pages 52-59, August 1999.
[22]S. Jung, B. Lee, and S. Pramanik. A Tree-Structured Index Allocation Method with Replication over Multiple Broadcast Channels in Wireless Environments. IEEE Transactions on Knowledge and Data Engineering, 17(3):311-325, 2005.
[23]J. Juran, A. R. Hurson, N. Vijaykrishnan, and S. Kim. Data Organization and Retrieval on Parallel Air Channels: Performance and Energy Issues. Wireless Networks, 10(2):183-195, 2004.
[24]D. E. Knuth. The Art of Computer Programming, vol. 3. Addison-Wesley, second edition, 1981.
[25]S. Khanna and S. Zhou. On Indexed Data Broadcast. Journal of Computer and System Sciences, 60(3):575-591, 2000.
[26]C. W. Lin and D. L. Lee. Adaptive Data Delivery in Wireless Communication Environments. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS), pages 444-452, April 2000.
[27]W. C. Lee and D. L. Lee. Using Signature Techniques for Information Filtering in Wireless and Mobile Environments. Distributed and Parallel Databases, 4(3):205-227, July 1996.
[28]W. C. Lee, Q. Hu, and D. L. Lee. A Study on Channel Allocation for Data Dissemination in Mobile Computing Environments. Mobile Networks Application, 4(2):117-129, 1999.
[29]G. Lee, S. C. Lo, and A. L. P. Chen. Data Allocation on Wireless Broadcast Channels for Efficient Query Processing. IEEE Transactions on Computers, 51(10): 1237-1252, 2002.
[30]H. V. Leong and A. Si. Database Caching over the Air-Storage. The Computer Journal, 40(7): 401-415, 1997.
[31]Y. W. Leung. Design of Broadcast Delivery Schedules for Multiple Channels. IEICE Transactions on Communication, 86-B(4):1391-1398, April 2003.
[32]C. W. Lin, H. Hu, and D. L. Lee. Adaptive Real Time Bandwidth Allocation for Wireless Data Delivery. Wireless Networks, 10(2):103-120, 2004.
[33]S. C. Lo and A. L. P. Chen. Optimal Index and Data Allocation in Multiple Broadcast Channels. In Proceedings of the International Conference on Data Engineering, pages 293-302, 2000.
[34]S. C. Lo and A. L. P. Chen. An Adaptive Access Method for Broadcast Data under an Error-Prone Mobile Environment. IEEE Transactions on Knowledge and Data Engineering, 12(4):609-620, July/August 2000.
[35]MSN Direct Service, http://www.msndirect.com, 2006.
[36]W. C. Peng and M. S. Chen. Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment. Wireless Networks, 9(2):117-229, 2003.
[37]K. Prabhakara, K. A. Hua, and J. H. Oh. Multi-Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment. In Proceedings of the International Conference on Data Engineering, pages 167-186, February/March 2000.
[38]E. Shih, P. Bahl, and M. Sinclair. Wake on Wireless: An Event-Driven Energy Saving Strategy for Battery-Operated Devices. In Proceedings of the International Conference on Mobile Computing and Networking, pages 160-171, September 2002.
[39]N. Shivakumar and S. Venkatasubramanian. Efficient Indexing for Broadcast Based Wireless Systems. Mobile Networks and Applications, 1(4):433-446, December 1996.
[40]StarBand, http://www.starband.com, 2006.
[41]K. Stathatos, N. Roussopoulos, and J. S. Baras. Adaptive Data Broadcast in Hybrid Networks. In Proceedings of the International Conference on Very Large Data Bases, pages 326-335, 1997.
[42]C. J. Su, L. Tassiulas and V. J. Tsotras. Broadcast Scheduling for Information Distribution. Wireless Networks, 5(2):137-147, 1999.
[43]C. J. Su and L. Tassiulas. Joint Broadcast Scheduling and User's Cache Management for Efficient Information Delivery. Wireless Networks, 6(4):279-288, 2000.
[44]K. L. Tan and J. X. Yu. An Analysis of Selective Tuning Schemes for Nonuniform Broadcast. Data and Knowledge Engineering. 22(3):319-344, 1997.
[45]K. L. Tan and J. X. Yu. Generating Broadcast Programs That Support Range Queries. IEEE Transactions on Knowledge and Data Engineering, 10(4):668-672, 1998.
[46]K. L. Tan and B. C. Ooi. On Selective Tuning in Unreliable Wireless Channels. Data and Knowledge Engineering, 28(2):209-231, November 1998.
[47]N. H. Vaidya and S. Hameed. Scheduling Data Broadcast in Asymmetric Communication Environments. Wireless Networks, 5(3):171-182, 1999.
[48]M.A. Viredaz, L.S. Brakmo, and W.R. Hamburgen. Energy Management on Handheld Devices. ACM Queue, 1(7):44-52, October 2003.
[49]S. Wang and H. L. Chen. An O(NlogK) Restricted Dynamic Programming Algorithm for Data Allocation over Multiple Channels. IEICE Transactions on Communications, E88-B(9):3756-3764, September 2005.
[50]S. Wang and H. L. Chen. Near-Optimal Data Allocation over Multiple Broadcast Channels. Computer Communications, 29(6):1341-1349, May 2006.
[51]J. W. Wong. Broadcast Delivery. Proceedings of the IEEE, 76(12):1566-1577, 1998.
[52]W. Wu and K. L. Tan. Global Cache Management in Nonuniform Mobile Broadcast. In Proceedings of the IEEE International Conference on Mobile Data Management (MDM), 2006.
[53]J. Xu, W. C. Lee, and X. Tang. Exponential Index: A Parameterized Distributed Indexing Scheme for Data on Air. In Proceedings ACM/ USENIX MobiSys, pages 153-164, June 2004.
[54]J. Xu, Q. Hu, W. C. Lee, and D. L. Lee. Performance Evaluation of an Optimal Cache Replacement Policy for Wireless Data Dissemination. IEEE Transactions on Knowledge and Data Engineering, 16(1):125-139, January 2004.
[55]X. Yang and A. Bouguettaya. Broadcast-Based Data Access in Wireless Environments. In Proceedings of the International Conference on Extending Database Technology (EDBT), pages 553-571, March 2002.
[56]X. Yang and A. Bouguettaya. Using Hybrid Method for Accessing Broadcast Data. In Proceedings of the IEEE International Conference on Mobile Data Management (MDM), 2005.
[57]W. Yee, S. Navathe, E. Omiecinski, and C. Jermaine. Efficient Data Allocation over Multiple Channels at Broadcast Servers. IEEE Transactions on Computers, 51(10):1231-1236, October 2002.
[58]W. Yee and S. Navathe. Efficient Data Access to Multi-Channel Broadcast Programs. ACM Conference Information and Knowledge Management (CIKM), pages 153-160, 2003.
[59]M. K. H. Yeung and Y. K. Kwok. Wireless Cache Invalidation Schemes with Link Adaptation and Downlink Traffic. IEEE Transactions on Mobile Computing, 4(1):68-83, January/February 2005.
[60]J. X. Yu, T. Sakata, and K. L. Tan. Statistical Estimation of Access Frequencies in Data Broadcasting Environments. Wireless Networks, 6(2):89-98, May 2000.
[61]J. Zhang and L. Gruenwald. Optimizing Data Placement over Wireless Broadcast Channel for Multi-Dimensional Range Query Processing. In Proceedings of the IEEE International Conference on Mobile Data Management (MDM), January 2004.