無線廣播的環境中，頻寬的使用仍是目前熱門的議題之一。因此在有限的頻寬下如何讓資料廣播更有效率亦為無線網路研究的主題之一。然而伺服器端(Server)有效率的資料排程後的廣播，不但可以節省客戶端(Client)在存取資料時所花費的時間，也可以節省傳送、接收雙方能源的消耗及提升網路整體的效能。 在無線網路的環境下，有向性排序(Directed Linear Arrangement)已廣泛的被使用來解決資料排序和廣播的問題。本論文提出混合切割比率貪婪排序演算法(Hybrid Ratio Cut Greedy Sort Algorithm，HRCGS)和等邊叢集演算法(Equivalent Edge Clustering Algorithm，EEC)來解決資料排程的問題。HRCGS使用雙向貪婪排序(Two-Way greedy Sort)和遞迴二分法(Recursive Bipartition)的技術。透過此技術，可以高效率(Highly Efficient)的在區域內搜尋(Local Search)以達到全域最佳化(Global Optimization)的情況。 EEC演算法使用等邊的技巧來置換點與點之間的邊(Replace Edges)，並且使用有向HAC的方式來合併頂點(Merge Vertices)到一個區段(Segment)中。透過使用等邊集合(Equivalent Edge Set)的技巧，我們可以改善在有向圖(Directed Graph)中頂點分群(Clustering Vertices)的效能。 Wireless broadcasting environment, the use of bandwidth is still one of the hottest topics. So the limited bandwidth of information on how to make broadcasting more efficient for wireless networks on one of the main themes. However server-side (Server) efficient scheduling information on the radio, not only can save the client (Client) access to information in the time it takes, can also save send, receive, both energy consumption and improve overall network Performance. The directed linear arrangement is a widely used and studied problem in task-scheduling and wireless data broadcast. This paper presents algorithms with different levels of complexity aiming at this problem which include a hybrid ratio cut greedy sort algorithm and a equivalent edge clustering algorithm. The hybrid ratio cut greedy sort algorithm, using the two-way greedy sort and recursive bipartition, is a highly efficient local search algorithm with global optimization. The equivalent edge clustering algorithm uses equivalent edge technique to replace edges, and uses the directed HAC process to merge vertices into a segment. With the equivalent edge set technique we can improve the solution quality of clustering vertices in directed graph.
