Energy and Cost Optimization for Data Communication Scheduling

過去十年，高能效與低成本一直是消費性電子產品設計上相當熱門的議題。有鑑於裝置之間以及裝置內部資料傳輸的快速成長，本論文針對可攜式裝置的傳輸元件進行能耗與成本最佳化之研究。輸子系統方面之研究，著重於設計路由協定以達到剩餘電量之最大化。提出多項式時間之最佳演算法對群播路由做最小剩餘電量之最大化。證明最大化叢聚路由之最小剩餘電量為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.he 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.he 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.Contentsbstract in Chinese ivbstract vcknowledgment viontents viiiist of Figures xiiist of Tables xiii Introduction 1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Energy-Efficient Routing . . . . . . . . . . . . . . . . . . . . . 2.1.2 Cost-Efficient Scheduling . . . . . . . . . . . . . . . . . . . . . 3.2 Objectives and Contributions . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Residual-Energy Maximization . . . . . . . . . . . . . . . . . 4.2.2 Bus-Layer Minimization . . . . . . . . . . . . . . . . . . . . . 6.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Related Work 9.1 Energy-Efficient Routing . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Cost-Efficient Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 14 Residual-Energy Maximization 17.1 Network Model and Problem Formulation . . . . . . . . . . . . . . . 18.2 An Optimal Algorithm for Maximum-Residual Multicasting . . . . . 21.3 A (2−ε)-Inapproximability Result for Maximum-Residual Aggregating 24.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 28.4.1 Algorithms for Comparison . . . . . . . . . . . . . . . . . . . 28.4.2 Experimental Setups and Performance Metrics . . . . . . . . . 29.4.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 31.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Distributed Residual-Energy Maximization 36.1 Network Model and Problem Formulation . . . . . . . . . . . . . . . 37.2 A Distributed Optimal Algorithm for Maximum-Residual Multicasting 40.2.1 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . 40.2.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44.3 A Maximum-Residual Multicast Protocol . . . . . . . . . . . . . . . . 50.3.1 Routing Tables . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3.2 Route Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . 53.3.3 Route Establishment . . . . . . . . . . . . . . . . . . . . . . . 55.3.4 Data Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . 57.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 58.4.1 Experimental Setups and Performance Metrics . . . . . . . . . 58.4.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 63.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Bus-Layer Minimization 69.1 System Model and Problem Formulation . . . . . . . . . . . . . . . . 70.1.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 70.1.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . 72.2 A (1.5−ε)-Inapproximability Result . . . . . . . . . . . . . . . . . . 74.3 A Dynamic-Programming Approach . . . . . . . . . . . . . . . . . . . 77.3.1 A Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 77.3.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80.4 Extension of the Basic Algorithm . . . . . . . . . . . . . . . . . . . . 82.4.1 Arbitrary Execution and Communication Time . . . . . . . . 82.4.2 Multiple Multi-Layer Buses and Non-Preemptiveasks/Transactions . . . . . . . . . . . . . . . . . . . . . . . . 86.4.3 Different Timing Constraints and Objective Functions . . . . . 87.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 89.5.1 Experimental Setups and Performance Metrics . . . . . . . . . 89.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 91.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Concluding Remarks 97.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97.2 Future Research Directions . . . . . . . . . . . . . . . . . . . . . . . . 100.2.1 Residual-Energy Maximization . . . . . . . . . . . . . . . . . 100.2.2 Bus-Layer Minimization . . . . . . . . . . . . . . . . . . . . . 101ibliography 102urriculum Vitae 113ublication List 11