請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9370
標題: | 資料傳輸排程之能耗與成本最佳化 Energy and Cost Optimization for Data Communication Scheduling |
作者: | Pi-Cheng Hsiu 修丕承 |
指導教授: | 郭大維(Tei-Wei Kuo) |
關鍵字: | 高能效,低成本,路由協定,排程演算法,資料傳輸,網路嵌入式系統, Energy Efficiency,Cost Efficiency,Routing Protocols,Scheduling Algorithms,Data Communication,Networked Embedded Systems, |
出版年 : | 2009 |
學位: | 博士 |
摘要: | 過去十年,高能效與低成本一直是消費性電子產品設計上相當熱門的議題。有鑑於裝置之間以及裝置內部資料傳輸的快速成長,本論文針對可攜式裝置的傳輸元件進行能耗與成本最佳化之研究。
傳輸子系統方面之研究,著重於設計路由協定以達到剩餘電量之最大化。提出多項式時間之最佳演算法對群播路由做最小剩餘電量之最大化。證明最大化叢聚路由之最小剩餘電量為NP-hard之問題,且除非P=NP,否則其對應之最小化問題不存在優於2倍之近似演算法。再針對群播路由,提出分散式演算法及其實踐之路由協定。該協定中,群播路由樹之形成是依照網路中各裝置獨立自主之決定,不需仰賴事先收集整個網路路由資訊。所形成之路由樹被證明不具迴路,且理論上能夠最大化最小剩餘之電量。該協定實作於NS2進行效能評估,結果顯示該協定於各項重要評估指標皆具優越之效能。 傳輸架構方面之研究,在於提出理論之方法以達到匯流排層數之最小化。探討具鏈式優先次序限制之即時工作於多層匯流排系統上最小化傳輸成本之排程問題。首先證明該問題為NP-hard,且除非P=NP,否則不存在優於1.5倍之近似演算法。針對考慮單一多層匯流排以及單位執行與傳輸時間之子問題,提出多項式時間之最佳演算法。再衍生該方法為擬似多項式時間之最佳演算法解決通例問題,以考慮多個多層匯流排、任意執行與傳輸時間、以及不同之時間限制與目標函式。並基於AMBA之系統拓撲,比較最佳演算法與其他啟發式演算法之效能以提供更多有助於系統設計開發之觀點。 Energy- and cost-efficiency designs in consumer electronics have been active research topics in the past decades. This dissertation is highly motivated by the rapid growth of data exchanges for both inter-device and intra-device communication, thus addressing energy conservation and cost reduction by targeting the communication components of portable devices. The study on communication subsystems aims at the design of a routing protocol for residual-energy maximization. A polynomial-time optimal algorithm is proposed for the multicast case. The aggregate case is proved to be NP-hard and, unless P=NP, its minimization version cannot be approximated within a ratio better than 2. A distributed algorithm and its realization, referred to as the Maximum-Residual Multicast Protocol (MRMP), are then developed. In MRMP, a transient multicast tree is derived based on the autonomous decisions of devices in the network, where no global information needs to be collected a priori. The derived tree is proved to be loop-free and theoretically optimal in the maximization of minimum residual energy. The capability of MRMP was evaluated over NS2, for which we have very encouraging results in essential performance metrics adopted for routing protocol evaluation. The study on communication architectures focuses on the proposing of a theoretical methodology for bus-layer minimization. Real-time tasks with chain-based precedence constraints are explored on multi-layer bus systems with an objective to minimize the communication cost. The target problem is proved to be NP-hard and, unless P=NP, it cannot be approximated within a ratio better than 1.5. A polynomial-time optimal algorithm is first proposed for a restricted case in which one multi-layer bus, and unit execution and communication time are considered. The result is then extended as a pseudo-polynomial-time optimal algorithm in the considerations of multiple multi-layer buses, arbitrary execution and communication time, and different timing constraints and objective functions. The capability of the proposed algorithm was evaluated over an AMBA-like system topology to provide more insights in system designs, compared to some popular heuristics. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9370 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf | 1.8 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。