在多廣播頻道上對具時效性的動態資料查詢進行隨需資料廣播排程之研究

On-demand Data Broadcasting for Data Items with Time Constraints on Multiple Broadcast Channels

蘇大智(Ta-Chih Su)

指導教授 ： 劉傳銘

國立臺北科技大學/電資學院/資訊工程系研究所/碩士(2010年)

https://doi.org/10.6841/NTUT.2010.00298

摘要

近年來，資料廣播被認為是一種有效率的方法可以提供資訊給大量的使用者在無線環境中。而如何排程一個廣播使得使用者等待資料的平均時間會最短成為一個重要的議題。其中更困難的是當資料的存取模式是動態的以及資料是有時效性的時候，例如交通資訊或股價資訊。如果廣播排程會依據使用者的查詢而變化的時候，我們稱之為隨需應變(on-demand)資料廣播。在這種環境下有個特性就是我們並不知道未來查詢的變化，我們只能依據現有的情況做排程。大部分相關的研究都是在單一廣播頻道上，在此篇論文中，我們研究在多個廣播頻道上對具時效性的動態資料查詢進行隨需的資料廣播排程，其中每一筆的查詢可要求多筆資料，而提出的隨需資料廣播排程將以降低錯失率(miss rate)和查詢時間(latency)為目的。我們證明了這個問題即使在已知所有的查詢情形下仍然是NP-Hard。我們提出了兩個演算法(MPFH 和MPLH)並且和最佳解做比較分析。我們的實驗結果驗證了我們提出的演算法能有效地達成目的，其中MPLH 演算法產生的廣播排程錯失率較低，而MPFH 演算法產生的廣播排程查詢時間(latency)則較低。而更多的討論會在實驗結果中探討。

關鍵字

隨需應變(on-demand)資料廣播 ； 多廣播頻道 ； 時效性資料 ； NP-Hard ； Competitive Analysis

並列摘要

Data Broadcasting is an effective approach to provide information to a large group of clients in ubiquitous environments. How to generate the data broadcast schedule to
make the average waiting time short for clients is an important issue. In particular, when the data access pattern is dynamic and data have time constraints, such as traffic and stock information, scheduling the broadcast for such data to fulfill the requests becomes challenging. Since the content of the broadcast is dynamic and the request deadlines should be met, such data broadcasting is referred to as on-demand data broadcasting with time constraints. Many related papers discussed this type of data broadcasting with a single broadcast channel. In this thesis, we investigate how to schedule the on-demand broadcast for the data with time constraints using multiple broadcast channels and provide two heuristics to schedule the data broadcast. The objective of the proposed heuristics is to minimize the miss rate (i.e., ratio of the requests missing deadlines to all the requests) and latency (i.e., time between issuing and termination of the request).
Besides, we prove that the problem is NP-Hard when the access pattern is offline. We also present a competitive analysis on the proposed heuristics. More discussion about
the proposed heuristics is given through extensive simulation experiments. The experimental results validate that the proposed heuristics achieve the objectives.

並列關鍵字

On-Demand Data Broadcast ； Multiple Broadcast Channels ； Temporal Data ； NP-Hard ； Competitive Analysis

參考文獻

[1] Stefano Anticaglia, Ferruccio Barsi, Alan A. Bertossi, Lucio Iamele, and Maria Cristina Pinotti. Efficient heuristics for data broadcasting on multiple channels. Wireless Networks, 14(2):219–231, 2008.

[5] Shu-Yu Fu and Chuan-Ming Liu. Broadcast schedules and query processing for k nearest neighbors search on multi-dimensional index trees in a multi-channel environment. In Proceedings of the 2006 SMC IEEE International Conference

[6] Chih-Lin Hu. On-demand real-time information dissemination: A general approach with fairness, productivity and urgency. In Proceedings of the 2007 International Conference on Advanced Information Networking and Applications, volume 0, pages 362–369, 2007.

[7] Jae-Hoon Kim and Kyung-Yong Chwa. Scheduling broadcasts with deadlines. Theor. Comput. Sci., 325(3):479–488, 2004.

[8] Svetlana A. Kravchenko. On the complexity of minimizing the number of late jobs in unit time open shop. Discrete Appl. Math., 100(1-2):127–132, 2000.