無線廣播環境下應用KL演算法於相關資料排程的配置研究

NHUIR > College of Science and Technology > Department of Information Management > Disserations and Theses > Item 987654321/22518

Please use this identifier to cite or link to this item: http://nhuir.nhu.edu.tw/handle/987654321/22518

Title:	無線廣播環境下應用KL演算法於相關資料排程的配置研究
Other Titles:	Using K-L based Algorithm for correlated data allocation in wireless broadcast system
Authors:	林曉吟 Lin, Siao-yin
Contributors:	資訊管理學研究所蔡德謙 Der-chian Tsaih
Keywords:	無線廣播;KL演算法;平均查詢讀取時間 average response time;wireless broadcast;KL algorithm
Date:	2006
Issue Date:	2015-08-04 14:50:32 (UTC+8)
Abstract:	無線網路的環境之下頻寬資源是有限的，透過伺服端以廣播的方式，可以有效率的傳送資料、利用頻寬。伺服端決定出一組較佳的廣播序列，能夠滿足用戶端的查詢需求，讓用戶端快速的取得所需資料。　　　本文探討的無線廣播排程問題中，以廣播資料項之間存在的相依性為主要考量，使用有向無循環圖形(DAG)表示其順序限制，且每一資料項對應於圖形中每一頂點，並應用加入Greedy方式之拓樸排序演算法、積體電路設計中常被使用的KL演算法，以及SA模擬退火演算法等方法於有向無循環圖形的排序問題，試圖降低頂點之間平均路徑長度，以減少用戶端平均查詢讀取時間，並透過模擬實驗結果的顯示分析，比較這幾種方法的優劣。實驗結果顯示，使用我們所提出加入Greedy方式的拓樸排序演算法，以及KL演算法、SA演算法，確實可以縮短資料項之間的相依性長度，降低用戶端在收取所需資料項時花費的平均查詢讀取時間。　　The resource of transmission bandwidth is limited under the wireless network environment. If data is broadcasted from server, bandwidth utilization can be maximized and data can be transmitted more efficiently. To satisfy the need of many different requests from mobile hosts, the broadcast server must schedule the data item such that most mobile host can read data from broadcast channel in short period of time.　　　Our context focus on the scheduling problem of wireless broadcast, consider dependence between each data item which are broadcasted. The directed acyclic graph was used with its edges as this dependence limitation and its vertex as its data item. Arrange the vertex set by topological sort with greedy strategy, KL algorithm which are used in integrated circuit design problem and Simulated Annealing (SA) algorithm to minimize the average edge weight across all vertices. This broadcasted order of data item will then minimize the average response time for client’s queries. The results for applying each algorithm in data schedule problem were shown and compared through extensive simulation.
Appears in Collections:	[Department of Information Management] Disserations and Theses

Files in This Item:

File	Description	Size	Format
094NHU05396030-001.pdf		1380Kb	Adobe PDF	509	View/Open
index.html		0Kb	HTML	236	View/Open

Loading...