Energy and Cost Optimization for Data Communication Scheduling
Date Issued
2009
Date
2009
Author(s)
Hsiu, Pi-Cheng
Abstract
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.
Subjects
Energy Efficiency
Cost Efficiency
Routing Protocols
Scheduling Algorithms
Data Communication
Networked Embedded Systems
SDGs
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D93922014-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):6e6a6c16c4b99001a7cdd41392cafa8b