南華大學機構典藏系統:Item 987654321/20556
English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 18278/19583 (93%)
造訪人次 : 1071420      線上人數 : 745
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧：
  • 您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料
    •  進階搜尋


    請使用永久網址來引用或連結此文件: http://nhuir.nhu.edu.tw/handle/987654321/20556


    題名: 應用雙向拓樸排序與比例削減法於有向性最佳化排序
    其他題名: Two-Way Greedy Sort and Ratio Cut Technique for Optimal Linear Arrangement
    作者: 吳昭勳
    Wu, Chao-hsun
    貢獻者: 資訊管理學系碩士班
    蔡德謙
    Te-chien Tsai
    關鍵詞: 有向性排序;貪婪搜尋
    Greedy Search;Directed Linear Arrangement
    日期: 2008
    上傳時間: 2015-05-10 15:50:46 (UTC+8)
    摘要: 　　無線廣播的環境中，頻寬的使用仍是目前熱門的議題之一。因此在有限的頻寬下如何讓資料廣播更有效率亦為無線網路研究的主題之一。然而伺服器端(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.
    顯示於類別:[資訊管理學系] 博碩士論文

    文件中的檔案:

    檔案 描述 大小格式瀏覽次數
    096NHU05396036-001.pdf870KbAdobe PDF20檢視/開啟
    index.html0KbHTML193檢視/開啟


    在NHUIR中所有的資料項目都受到原著作權保護.

    TAIR相關文章

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回饋