隨著無線通訊技術的進步，行動通訊裝置已經普遍成為個人隨身配備，但由於無線的頻寬不像有線的頻寬那樣充裕，所以如何利用有效率的廣播來減少頻寬的使用和客戶端查詢時間，並提供最快速的搜尋效能便是在無線環境中重要的課題，因此本論文以無線廣播中廣播資料項之間存在的相依性為主要考量，使用有向無循環圖形（DAG）表示其順序限制，而每一資料項對應於圖形中每一頂點；並用最小路徑方法求得線性排列的最佳解；本論文以Relabel-to-front演算法求得DAG中，每個節點的最小分割(minimum cut)，再提出利用joint vertex pair提高DAG中的Lower bound，最後則介紹如何運用此Lower bound進一步地降低Ａ*路徑搜尋法中，路徑搜尋的數量，並且尋找出一組最佳的拓撲排序。 透過模擬實驗結果的顯示，在本論文中所提出的方法確實可以縮短資料項之間的相依性長度，降低用戶端在收取所需資料項時花費的平均查詢讀取時間。 With the progress of wireless communication technology, the mobile device has been a necessary personal equipment. Since the bandwidth is not abundant compared to the wired environment, it is a important subject on making efficient broadcast to reduce the waiting time of user in the wireless environment.Our context consider the existence of data dependence between each data item which are broadcasted. The directed acyclic graph was used with its vertex representing its data item and its edges representing the dependence between data item. The problem of optimal directed ordering is then can be found through the shortest path problem with the embedding graph. In the context, we use the Relabel-to-front algorithm to find the minimum cut before each vertex in any topological order of DAG and also present a method which utilizing jointed vertex pair to increase the lower bound of cut before each vertex in any topological order of DAG. At last we introduce the algorithm which adopt this lower bound to prune the unnecessary path in the A* algorithm, which is used to find the optimal solution. We provide a lower bound based on well known max-flow-min-cut theorem for A* algorithm .The performance results were shown and compared through extensive simulations. This broadcasted order of data item will then minimize the average response time for client’s queries.
