[[alternative]]Greedy Heuristic for Problem of Scheduling Directed Wireless Data

[[abstract]] 隨著網路使用者的日漸增加，網路資訊的大量充斥，用戶端對於網頁資訊的取得也要求更快速、更有效率，但礙於現實網路環境頻寬有限及無線資訊產品能源限制，因此在整個無線網路的環境中，資料項的廣播儼然扮演重要的角色及應用。 本研究著重於無線網路廣播資料排程問題，以廣播資料項存在的相依性為主要的考量，藉由有向無循環圖形(Directed acyclic Graph ,DAG)的資料存取模式及其表示順序限制作為基礎，在資料排序路徑的搜尋上，運用各種不同的貪婪拓撲排序之策略，經由各個策略下所產生的有向性線性序列，運算其頂點之間的平均路徑長度，並且相互比較彼此優劣。其目的是試圖讓用戶端在查詢相關性資料時，可以降低讀取相關性資料平均等待查詢時間，找出最佳廣播資料排序，縮短資料項間的相依長度，確保聯網的服務品質(Quality of Service ,QoS)。 經本研究實驗結果數據顯示，所提出的連續性雙向演算法，確實比其他以貪婪拓撲排序的策略之演算法，更能獲得較短的平均查詢讀取時間。[[abstract]] Since the resource of transmission bandwidth and the power of portable devices are much limited under the wireless network environment, an efficient and effective data broadcasting algorithm is important in disseminating information to mobile clients in wireless broadcast environment. In this paper, we consider the problem of efficiently generating the broadcast schedule when there are possible data dependence exist between each broadcasted data item. By arranging the vertex set by topological sort with greedy strategy, one can generate a directed optimal linear broadcast schedule. One key issue related to data broadcasting is the technique used for server to organize data for clients accessing the broadcasted information more efficiently, which is in terms of the average response time. The short average response time can ensure the quality of service. Our result shows that by using the proposed schemes one can achieve a better broadcast schedule which reduces average response time