臺灣博碩士論文加值系統

科技日新月異，人們因網路的發達而方便了資訊的取得，無線環境因為科技進步而普及生活，便捷了人們逃離有線的羈絆，朝向更自由的無線生活，然而無線環境的使用者日益遽增，為了讓大量的使用者更有效率、更公平、更快速得到自己需求的資訊，我們依照資料要求的數量、資料滿足使用者的個數和等待的時間做出非常精確的判斷，使得廣播出的資訊能滿足更多的要求，並且能顧慮到某些使用者提出的冷門資料，使這些要求者不至於有挨餓的狀態發生。我們提出了一個新的要求式排程演算法「SaWa」，在多重需求查詢的廣播環境下，能有最好的廣播效能，「SaWa」排程演算法決定廣播的方式是以掃瞄目前正在等待被服務的要求，依照廣播資訊種類被等待的時間與廣播後滿足正在等待需求的個數，來決定下一個廣播時段將廣播哪種資訊。模擬實驗的證明，有詳盡的廣播效能比較及優缺點分析，顯示出「SaWa」排程演算法，在變動的要求下能有好的廣播效能。

none

感謝…………………………………………………………i
摘要…………………………………………………………ii
圖片列表……………………………………………………iii
第一章 導論…………………………………………………1
1.1日常生活廣播的運用……………………………1
1.2廣播系統的討論的議題…………………………2
1.3廣播方式的分類…………………………………3
1.4本篇論文的貢獻…………………………………7
1.5後續章節介紹……………………………………8
第二章 背景知識……………………………………………9
2.1無線廣播環境介紹………………………………9
2.2廣播演算法測量依據……………………………11
2.2.1廣播效能測量……………………………………11
2.2.2廣播公平性………………………………………14
2.2.3廣播排程負載……………………………………15
2.3已有的排程演算法………………………………16
第三章 排程…………………………………………………19
3.1動機………………………………………………19
3.2分析………………………………………………20
3.3主要演算法………………………………………20
3.3.1 X2D1………………………………………………20
3.3.2 SaWa………………………………………………23
3.4 資料結構…………………………………………26
3.5 簡化搜尋次數……………………………………27
第四章 實驗分析……………………………………………30
4.1模擬環境…………………………………………30
4.2資料產生…………………………………………30
4.3廣播效能分析……………………………………31
4.3.1平均等待時間分析………………………………32
4.3.2平均伸展值分析…………………………………33
4.3.3公平性分析………………………………………34
4.3.4排程負載分析……………………………………35
4.3.5資料分布分析……………………………………36
4.3.6資料要求數量分析………………………………38
第五章 結論與未來的工作…………………………………40
相關參考論文…………………………………………………41

[AA95a] S. Acharya, R. Alonso, M. Franklin, and S. Zdonik. “Broadcast disks:Data management for asymmetric communication environments,” In Proceedings of the 1995 ACM-SIGMOD International Conference on Management of Data, pages 199-210, June 1995
[AA95b]S. Acharya, R. Alonso, M. Franklin, and S. Zdonik. “Broadcast disks:Data management for asymmetric communication environments,” In Management of Data, pages 199-210, June 1995.
[AA95c]S. Acharya ,M. Franklin ,and S. Zdonik ,”Dissemination-based Data Delivery Using Broadcast Disks,” IEEE Personal Communications, pp. 50-60,Dec. 1995
[AF96a] S. Acharya, M. Franklin, S. Zdonik, “Disseminating Updates on Broadcast Disks,” Proceedings of the 22nd VLDB Conference Mumbai(Bombay), India, 1996
[AF96b] S. Acharya, M. Franklin, S. Zdonik, “Prefetching from a Broadcast Disk,” Proceedings of the International Conference on Data Engineering, New Oreans, LA, Feb 1996
[AF98] D. Aksoy and M. Franklin. “Scheduling for large-scale on-demand data broadcasting,” In Proceeding of the 1998 IEEE INFOCOM Conference,San Francisco,CA,March 1998.
[AF99]Demet Aksoy and Michael Franklin. “RxW:A Scheduling Approach for Large-Scale On-Demand Data Broadcast,” In ACM/IEEE Transactions on Networking , Volume 7,Number 6,pp:846-860,December 1999
[AM98]S. Acharya and S. Muthukrishnan, “Scheduling On-Demand Broadcasts: New Metrics and Algorithm,” ACM MobiCom’98,pp.43-54,Oct. 1998
[BG92]T.F. Bowen,G. Gopal,G. Herman,T. Hickey,K.C. Lee,W.H. Mansfield,J Raitz, and A. Weinrib. “The datacycle architecture,” Communications of the ACM , 35(12) , December 1992.
[CK99]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.
[E98] Ozgur Ercetin. “Information Delivery in Two-Stage Satellite-Terrestrial Wireless Networks,” Number: MS 98-7 Year:1998 Advisor: Leandros Tassiulas
[FZ96] M. Franklin and S. Zdonik. “Dissemination-based information systems,” IEEE Data Engineering,19(3):20-30,September 1996
[HG87] G. Herman, G. Gopal,K.C. Lee,and A. Weinrib. “The datacycle architecture for very high throughput database systems,” In Proceedings of the 1987 ACM-SIGMOD International Conference on Management of Data,pages 97-103,June 1987.
[HL02]Chih-Hao Hsu, Guanling Lee and Arbee L.P. Chen , “Index and Data Allocation on Multiple Broadcast Channels Considering Data Access Frequencies,”International conference on mobile data management, 2002.
[HM96]H. Dykeman, M. H. Ammar, and J. Wong, “Scheduling Algorithms for Videotext Systems under Broadcast Delivery,” Proc. International Conference of Communications, pp. 1847-1857,1996.
[IV94] T. Imielinski and S. Viswanathan. “Adaptive wireless information systems,” In Proceedings of the SIGDBS Conference,page 19-41, Tokyo, Japan, October 1994.
[IV97]T. Imielinski,S. Viswanatan, and B.R. Badrinath. “Data on air: Organization and access,” IEEE Transactions on Knowledge and Data Engineering , 9(3) : 353-372,1997.
[LL96] W.C. Lee and D. Lee. “Using signature and caching techniques for information filtering in wireless and mobile environments,” Journal of Distributed and Parallel Databases, 4(3):205-227,1996.
[LL02]Guanling Lee, S.C. Lo and A.L.P. Chen, “Data Allocation on the
Wireless Broadcast Channel for Efficient Query Processing,” IEEE Trans. On Computers Special Section on Data.Management Systems and Mobile Computing, October, 2002, volume 51, pp. 1237~1252.
[LY01] Guanling Lee, Meng-Shin Yeh, Shou-Chih Lo, and Arbee LP Chen,,”A Strategy for Efficient Access of Multiple Data Items in Mobile Environments,” International conference on mobile data management, 2002.
[PC00] Wen-Chih Peng, Ming-Syan Chen, “Dynamic Generation of Data Broadcasting Programs for a Broadcast Disk Array in a Mobile Computing Environment,” Proc. of the ACM 9th Intern'l Conf. on Information and Knowledge Management, November 6-10, 2000, pp. 38-45.
[ST97a]C.J.Su and L.Tassiulas. “Designing Broadcast Schedules for Information
Dissemination through Broadcasting,” In Proceedings of the IEEE INFOCOM’97 , pages 109-113,Kobe,Japan,April 1997
[ST97b] Chi-Jiun Su, L. Tassiulas, “Broadcast Scheduling for Information Distribution,” IEEE INFOCOM '97. April 09 - 11, 1997 Kobe, Japan, p. 109
[TY97] K.L. Tan and J.X. Yu. “A dynamic scheduler for the infinite air-cache,” Data and Knowledge Engineering, 24(1):97-112,1997
[VH99] N. Vaidy and S. Hameed. “Scheduling data broadcast in asymmetric communication environment,” ACM/Baltzer Wireless Networks,5(3):171-182,1999
[W88] J.W.Wong. “Broadcast delivery,” Proceedings of the IEEE , 76 (12): 1566-1577 , December 1988.
[WC01] Y.Wu, G. Cao, “Stretch-Optimal Scheduling for On-Demand Data Broadcasts,” IEEE International Conference on Computer Communications and Networks (ICCCN'01), pp. 500-504, Oct. 2001