臺灣博碩士論文加值系統

無線資料廣播是一種用來傳送數位資訊給裝配有行動設備的客戶端之有效方式。它提供大量的行動客戶端同時在無線環境中能隨時隨地存取資料。能使用無線資料廣播來傳輸資訊的應用包含股票交易資訊與交通狀況。在廣播檔案中加入索引技術 (選擇性聽頻道) 可以大量地減少行動設備的電源消耗，且又不會急劇地延長客戶端等待時間。大部分的選擇性聽頻道技術研究都假設每一個在無線頻道播放的資料都平均地被客戶端存取。在現實生活中，與冷門資料比起來，熱門資料較常被客戶端存取，即「偏斜存取模式」。在這博士論文中，為了有效地支援單頻道無線環境中偏斜存取模式之選擇性聽頻道技術，我們首先提出一個在均勻資料廣播上的偏斜分散式索引 (Skewed Distributed Index，SDI)。均勻資料廣播即每一個資料只會在同一廣播循環中播放一次。我們接著提出一個在非均勻資料廣播上的偏斜索引 (Skewed Index，SI)。非均勻資料廣播即少數熱門資料會比其它資料在同一廣播循環中播放多次。我們的 SDI 演算法考慮播放資料的存取機率與索引節點複製機制。這個演算法會尋訪一顆平衡樹的節點，根據子節點的存取機率來決定其父節點是否需要被複製。我們的效能分析與程式模擬結果顯示出，我們 SDI演算法的效能比 Variant-Fanout Tree Index 與 Distributed Index 這兩個演算法來得好。我們的 SI 演算法採用 Acharya 等人的 Broadcast Disks 產生資料排程，以達到減少客戶端等待時間。在此排程中，熱門資料會比其它資料播放較多次。我們的 SI 演算法接著針對排程的資料建立一顆偏斜樹。我們的演算法在同一廣播循環中針對熱門資料配置較多相關索引節點，針對冷門資料配置較少相關索引節點。我們的效能分析與程式模擬結果顯示出，我們 SI 演算法的效能比 Flexible Index 與 Flexible Distributed Index 這兩個演算法來得好。

Wireless data broadcast is an efficient way to disseminate digital information to clients equipped with mobile devices. It allows a huge number of the mobile clients simultaneously access data at anytime and anywhere in the wireless environments. Applications using wireless data broadcast to disseminate information include accessing stock activities and traffic conditions. Using index technologies on the broadcast file, i.e., selective tuning, can reduce a lot of energy consumption of the mobile devices without significantly increasing client waiting time. Most of the research work for selective tuning assumes that each data item broadcast on the wireless channel is fairly evenly accessed by mobile clients. In real-life applications, more popular data may be frequently accessed by clients than less popular ones, i.e., skewed access patterns. In this dissertation, to support efficiently selective tuning with skewed access patterns in the single-channel wireless environments, we first propose a skewed distributed index, SDI, on the uniform data broadcast, on which each data item is broadcast once in a broadcast cycle. Second, we propose a skewed index, SI, on the nonuniform data broadcast, on which a few popular data items are broadcast more frequently in a broadcast cycle than the others. The first proposed algorithm, SDI, considers the access probabilities of data items and the replication of index nodes. The proposed algorithm traverses a balanced tree to determine whether an index node should be replicated by considering the access probability of its child node. In our performance analysis and simulation results, we have shown that our proposed algorithm outperforms the variant-fanout tree index and the distributed index. The second proposed algorithm, SI, applies Acharya et al.''s Broadcast Disks to generate a broadcast program, in which the popular data items are broadcast more times than the others, in order to reduce client waiting time. Moreover, the proposed algorithm builds a skewed tree for these data items and allocates index nodes for the popular data items more times than those for the less popular ones in a broadcast cycle. From our performance analysis and simulation results, we have shown that our proposed SI outperforms the flexible index and the flexible distributed index.

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Wireless Data Broadcast . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Selective Tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 A Classification of the Research Work for Selective Tuning . . . . . . 7
1.4 Motivations and Contributions . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 A Skewed Distributed Index on the Uniform Data Broadcast . 12
1.4.2 A Skewed Index on the Nonuniform Data Broadcast . . . . . . 14
1.5 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . 16
2. A Survey of Index Structures for Selective Tuning . . . . . . . . . 17
2.1 Index Structures on the Uniform Data Broadcast . . . . . . . . . . . 19
2.1.1 Hashing A and Hashing B . . . . . . . . . . . . . . . . . . . . 19
2.1.2 The TopK Index . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 The (1, m) Index . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.4 The Distributed Index . . . . . . . . . . . . . . . . . . . . . . 25
2.1.5 The Variant-Fanout Tree Index . . . . . . . . . . . . . . . . . 27
2.1.6 The Adaptive Index . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.7 The Signature Indexes . . . . . . . . . . . . . . . . . . . . . . 29
2.1.8 The Hybrid Index . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.9 Imielinski et al.’s Flexible Index . . . . . . . . . . . . . . . . . 33
2.1.10 The Exponential Index . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Index Structures on the Nonuniform Data Broadcast . . . . . . . . . 36
2.2.1 Yu and Tan’s Flexible Index . . . . . . . . . . . . . . . . . . . 37
2.2.2 The MHash Index . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.3 The Flexible Distributed Index . . . . . . . . . . . . . . . . . 39
2.3 Index Structures on the Multichannel Data Broadcast . . . . . . . . . 41
2.3.1 The Alphabetic-Huffman-Tree Index . . . . . . . . . . . . . . 42
2.3.2 The Topological-Tree Index . . . . . . . . . . . . . . . . . . . 43
2.3.3 The Separated Replication Index . . . . . . . . . . . . . . . . 45
2.3.4 The Stripping Index . . . . . . . . . . . . . . . . . . . . . . . 48
3. A Skewed Distributed Index on the Uniform Data Broadcast . . 51
3.1 A Skewed Distributed Index . . . . . . . . . . . . . . . . . . . . . . . 52
3.1.1 Description of the Algorithm . . . . . . . . . . . . . . . . . . . 52
3.1.2 Control Index . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.3 Access Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.1 The System Model . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.2 Analysis of Access Time and Tuning Time . . . . . . . . . . . 61
3.2.3 Experimental Results: SDI vs. VF . . . . . . . . . . . . . . . 64
3.2.4 Experimental Results: SDI vs. DI . . . . . . . . . . . . . . . . 72
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4. A Skewed Index on the Nonuniform Data Broadcast . . . . . . . . 78
4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 A Skewed Index for Broadcast Disks . . . . . . . . . . . . . . . . . . 81
4.2.1 Description of the Algorithm . . . . . . . . . . . . . . . . . . . 81
4.2.2 Access Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.1 The System Model . . . . . . . . . . . . . . . . . . . . . . . . 91
4.3.2 Analysis of Access Time and Tuning Time . . . . . . . . . . . 92
4.3.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 94
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.2 The Future Research Direction . . . . . . . . . . . . . . . . . . . . . 110
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

[1] S. Acharya, M. Franklin, S. Zdonik, and R. Alongso, “Broadcast Disks: Data Management for Asymmetric Communications Environments,” Proc. of the 1995 ACM SIGMOD Int. Conf. on Management of Data, pp. 199–210, 1995.
[2] A. Bar-Noy, V. Dreizin, and B. Patt-Shamir, “Efficient Algorithms for Periodic Scheduling,” Computer Networks, Vol. 45, No. 2, pp. 155–173, June 2004.
[3] D. Barbar´a, “Mobile Computing and Database—A Survey,” IEEE Trans. on Knowledge and Data Eng., Vol. 11, No. 1, pp. 108–117, Jan./Feb. 1999.
[4] B. H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Comm. of the ACM, Vol. 13, No. 7, pp. 422–426, July 1970.
[5] Y. I. Chang and S. Y. Chiu, “A Hybrid Approach to Query Sets Broadcasting Scheduling for Multiple Channels inMobile Information,” Journal of Information Science and Eng., Vol. 18, No. 5, pp. 641–666, Sept. 2002.
[6] Y. I. Chang, S. Y. Chiu, and J. H. Shen, “An Improvement of the Complementary Approach to Data Broadcasting in Mobile Information Systems,” Proc. of Int. Conf. on Informatics, Cyberetics, and Systems, pp. 1384–1389, 2003.
[7] Y. I. Chang, S. Y. Chiu, and J. H. Shen, “An Adaptive Approach to Data Broadcasting in Mobile Information Systems,” Proc. of National Computer Symp., pp. 1–10, 2005.
[8] Y. I. Chang and C. N. Yang, “A Complementary Approach to Data Broadcasting in Mobile Information Systems,” Data and Knowledge Eng., Vol. 40, No. 2, pp. 181–194, Feb. 2002.
[9] Y. I. Chang, C. N. Yang, and J. H. Shen, “A Binary-Number-Based Approach to Data Broadcasting in Wireless Information Systems,” Proc. of the 3rd IEEE Int. Workshop on Mobility Management and Wireless Access, Vol. 1, pp. 348–353, 2005.
[10] M. S. Chen, K. L. Wu, and P. S. Yu, “Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing,” IEEE Trans. on Knowledge and Data Eng., Vol. 15, No. 1, pp. 161–173, Jan./Feb. 2003.
[11] M. S. Chen, P. S. Yu, and K. L. Wu, “Indexed Sequential Data Broadcasting in Wireless Mobile Computing,” Proc. of the 17th IEEE Int. Conf. on Distributed Computing Systems, pp. 124–131, 1997.
[12] Y. D. Chung and M. H. Kim, “An Index Replication Scheme for Wireless Data Broadcasting,” The Journal of Systems and Software, Vol. 51, No. 3, pp. 191–199, May 2000.
[13] Q. L. Hu, W. C. Lee, and D. L. Lee, “Indexing Techniques for Wireless Data Broadcast Under Data Clustering and Scheduling,” Proc. of the 8th Int. Conf. on Information and Knowledge Management, pp. 351–358, 1999.
[14] J. L. Huang and M. S. Chen, “Dependent Data Broadcasting for Unordered Queries in a Multiple Channel Mobile Environment,” IEEE Trans. on Knowledge and Data Eng., Vol. 16, No. 9, pp. 1143–1156, Sept. 2004.
[15] J. J. Hung and Y. Leu, “Efficient Index Caching for Data Dissemination in Mobile Computing Environments,” The Journal of Systems and Software, Vol. 79, No. 1, pp. 93–106, Jan. 2006.
[16] T. Imielinski, S. Viswanathan, and B. R. Badrinath, “Energy Efficient Indexing on Air,” ACM SIGMOD Record, Vol. 23, No. 2, pp. 25–36, June 1994.
[17] T. Imielinski, S. Viswanathan, and B. R. Badrinath, “Power Efficient Filtering of Data on Air,” Proc. of the 4th Int. Conf. on Extending DataBase Technology, pp. 245–258, 1994.
[18] T. Imielinski, S. Viswanathan, and B. R. Badrinath, “Data on Air: Organization and Access,” IEEE Trans. on Knowledge and Data Eng., Vol. 9, No. 3, pp. 353–372, May/June 1997.
[19] S. Jung, B. Lee, and S. Pramanik, “A Tree-Structured Index Allocation Method with Replication over Multiple Broadcast Channels in Wireless Environments,” IEEE Trans. on Knowledge and Data Eng., Vol. 17, No. 3, pp. 311–325, March 2005.
[20] D. Katsaros, N. Dimokas, and Y. Manolopoulos, “Generalized Indexing for Energy-Efficient Access to Partially Ordered Broadcast Data in Wireless Networks,” Proc. of the 10th Int. Database Eng. and Applications Symp., pp. 89–96, 2006.
[21] G. Lee and S. C. Lo, “Broadcast Data Allocation for Efficient Access of Multiple Data Items in Mobile Environments,” Mobile Networks and Applications, Vol. 8, No. 4, pp. 365–375, Aug. 2003.
[22] W. C. Lee and D. L. Lee, “Using Signature and Caching Techniques for Information Filtering in Wireless and Mobile Environments,” Distributed and Parallel Databases, Vol. 4, No. 3, pp. 205–227, July 1996.
[23] W. C. Lee and D. L. Lee, “Signature Caching Techniques for Information Filtering in Mobile Environments,” ACM Wireless Networks, Vol. 5, No. 1, pp. 57–67, Jan. 1999. [24] S. C. Lo and A. L. P. Chen, “An Adaptive Access Method for Broadcast Data Under an Error-Prone Mobile Environment,” IEEE Trans. on Knowledge and Data Eng., Vol. 12, No. 4, pp. 609–620, July/Aug. 2000.
[25] S. C. Lo and A. L. P. Chen, “Optimal Index and Data Allocation in Multiple Broadcast Channels,” Proc. of the 16th IEEE Int. Conf. on Data Eng., pp. 293–302, 2000.
[26] W. C. Peng and M. S. Chen, “Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment,” Wireless Networks, Vol. 9, No. 2, pp. 117–129, March 2003.
[27] A. Seifert and J. J. Hung, “FlexInd: A Flexible and Parameterizable Air-Indexing Scheme for Data Broadcast Systems,” Proc. of the 10th Int. Conf. on Extending Database Technology, LNCS, Vol. 3896, pp. 902–920, 2006.
[28] J. H. Shen and Y. I. Chang, “A Skewed Distributed Indexing for Skewed Access Patterns on the Wireless Broadcast,” The Journal of Systems and Software, Vol. 80, No. 5, pp. 711–723, May 2007.
[29] J. H. Shen and Y. I. Chang, “The TopK Scheme for the Energy-Saving Data Organization in Broadcast-Based Wireless Environments,” IAENG Int. Journal of Computer Science, Vol. 33, No. 1, pp. 43–49, March 2007.
[30] J. H. Shen and Y. I. Chang, “An Efficient Nonuniform Index in the Wireless Broadcast Environments,” accepted by The Journal of Systems and Software, Jan. 2008.
[31] N. Shivakumar and S. Venkatasubramanian, “Efficient Indexing for Broadcast Based Wireless Systems,” ACM/Baltzer Mobile Networks and Applications, Vol. 1, No. 4, pp. 433–446, Dec. 1996.
[32] K. L. Tan and B. C. Ooi, “On Selective Tuning in Unreliable Wireless Channels,” Data and Knowledge Eng., Vol. 28, No. 2, pp. 209–231, Nov. 1998.
[33] M. F. Triola, Elementary Statistics. Addison Wesley Longman, Inc., 7 ed., 1998.
[34] F. Tsakiridis, P. Bozanis, and D. Katsaros, “Interpolating the Air for Optimizing Wireless Data Broadcast,” Proc. of the 5th ACM Int. Workshop on Mobility Management and Wireless Access, pp. 112–119, 2007.
[35] J. Xu, W. C. Lee, and X. Tang, “Exponential Index: A Parameterized Distributed Indexing Scheme for Data on Air,” Proc. of the 2nd Int. Conf. on Mobile Systems, Applications and Services, pp. 153–164, 2004.
[36] J. Xu, W. C. Lee, X. Tang, Q. Gao, and S. Li, “An Error-Resilient and Tunable Distributed Indexing Scheme for Wireless Data Broadcast,” IEEE Trans. on Knowledge and Data Eng., Vol. 18, No. 3, pp. 392–404, March 2006.
[37] X. Yang and A. Bouguettaya, “Adaptive Data Access in Broadcast-Based Wireless Environments,” IEEE Trans. on Knowledge and Data Eng., Vol. 17, No. 3, pp. 326–338, March 2005.
[38] Y. Yao, X. Tang, E. P. Lim, and A. Sun, “An Energy-Efficient and Access Latency Optimized Indexing Scheme for Wireless Data Broadcast,” IEEE Trans. on Knowledge and Data Eng., Vol. 18, No. 8, pp. 1111–1124, Aug. 2006.
[39] W. G. Yee and S. B. Navathe, “Efficient Data Access to Multi-Channel Broadcast Programs,” Proc. of the 12th Int. Conf. on Information and Knowledge Management, pp. 153–160, 2003.
[40] W. G. Yee, S. B. Navathe, and E. Omiecinski, “Efficient Data Allocation over Multiple Channels at Broadcast Servers,” IEEE Trans. on Computers, Vol. 51, No. 10, pp. 1231–1236, Oct. 2002.
[41] W. G. Yee, S. B. Navathe, E. Omiecinski, and C. Jermaine, “Bridging the Gap Between Response Time and Energy-Efficiency in Broadcast Schedule Design,” Proc. of the 8th Int. Conf. on Extending Database Technology, pp. 572–589, 2002.
[42] J. X. Yu and K. L. Tan, “An Analysis of Selective Tuning Schemes for Nonuniform Broadcast,” Data and Knowledge Eng., Vol. 22, No. 3, pp. 319–344, May 1997.
[43] B. Zheng and D. L. Lee, “Information Dissemination via Wireless Broadcast,” Comm. of the ACM, Vol. 48, No. 5, pp. 105–110, May 2005.