Assigning Real-Time Tasks in Environmentally Powered Distributed Systems

Jian Lin, Albert M. K. Cheng

Department of Computer Science, University of Houston, Houston, USA.
Department of Management Information Systems, University of Houston, Clear Lake, Houston, USA.

DOI: 10.4236/cs.2014.54012                

Abstract

Harvesting energy for execution from the environment (e.g., solar, wind energy) has recently emerged as a feasible solution for low-cost and low-power distributed systems. When real-time responsiveness of a given application has to be guaranteed, the recharge rate of obtaining energy inevitably affects the task scheduling. This paper extends our previous works in [1] [2] to explore the real-time task assignment problem on an energy-harvesting distributed system. The solution using Ant Colony Optimization (ACO) and several significant improvements are presented. Simulations compare the performance of the approaches, which demonstrate the solutions effectiveness and efficiency.

Keywords

Distributed Systems, Energy Harvesting, Real-Time Scheduling, Task Assignment

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Lin, J. and Cheng, A.M.K. (2008) Real-Time Tasks Assignment in Rechargeable Multiprocessor Systems. Proceedings of IEEE-CS International Conference on Embedded and Real-Time Computing Systems and Applications, Kaohsiung, 25-27 August 2008, 279-284.
[2]	Lin, J. and Cheng, A.M.K. (2009) Real-Time Task Assignment in Heterogeneous Distributed Systems with Rechargeable Batteries. Proceedings of IEEE-CS International Conference on Advanced Information Networking and Applications, Bradford, 6-29 May 2009, 82-89.
[3]	Wang, L., Siegel, H.J., Roychowdhury, V.P. and Maciejewski, A.A. (1997) Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach. Journal of Parallel and Distributed Computing, 47, 8-22.
[4]	Funk, S. and Baruah, S. (2005) Task assignment on Uniform Heterogeneous Multiprocessors. Proceedings of the 17th Euromicro Conference on Real-Time Systems, 6-8 July 2005, 219-226. http://dx.doi.org/10.1109/ECRTS.2005.31
[5]	Baruah, S.K. (2004) Partitioning Real-Time Tasks among Heterogeneous Multiprocessors. Proceedings of the 2004 International Conference on Parallel Processing, 15-18 August 2004, 467-474.
[6]	Braun, T.D., Siegel, H.J. and Beck, N. (2001) A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing, 61, 810-837.
[7]	Luo, J. and Jha, N.K. (2007) Power-Efficient Scheduling for Heterogeneous Distributed Real-Time Embedded Systems. IEEE Transactions on Computer-Aided Designs of Integrated Circuits and Systems, 26, 1161-1170.
[8]	Mishra, R., Rastogi, N., Zhu, D., Mosse, D. and Melhem, R. (2003) Energy Aware Scheduling for Distributed RealTime Systems. International Parallel and Distributed Processing Symposium. http://dx.doi.org/10.1109/IPDPS.2003.1213099
[9]	Kumar, G., Manimaran, G. and Wang, Z. (2008) End-to-End Energy Management in Networked Real-Time Embedded Systems. IEEE Transactions on Parallel and Distributed Systems, 19, 1498-1510. http://dx.doi.org/10.1109/TPDS.2008.124
[10]	Raghunathan, V., Kansal, A., et al. (2005) Design Considerations for Solar Energy Harvesting Wireless Embedded Systems. Proceedings of the International Symposium on Information Processing in Sensor Networks, 15 April 2005, 457462.
[11]	Jiang, X., Polastre, J. and Culler, D.E. (2005) Perpetual Environmentally Powered Sensor Networks. Proceedings of the International Symposium on Information Processing in Sensor Networks, Piscataway.
[12]	Lin, L., Shroff, N.B. and Srikant, R. (2007) Asymptotically Optimal Power-Aware Routing for Multihop Wireless Networks with Renewable Energy Sources. ACM/TEEE Transactions on Networking, 15.
[13]	Allavena, A. and Mosse, D. (2001) Scheduling of Frame-Based Embedded Systems with Rechargeable Batteries, in Workshop on Power Management for Real-Time and Embedded Systems (In Conjunction with RTAS 2001).
[14]	Moser, C., Brunelli, D., Thiele, L. and Benini, L. (2006) Real-Time Scheduling with Regenerative Energy. Proceedings of the Euromicro Conference on Real-Time Systems, Dresden, 2006, 10-270. http://dx.doi.org/10.1109/ECRTS.2006.23
[15]	Liu, S., Lu, J., Wu, Q. and Qiu, Q. (2012) Harvesting-Aware Power Management for Real-Time Systems with Renewable Energy. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 20, 1473-1486.
[16]	Chetto, M. and Queudet, A. (2013) A Note on EDF Scheduling for Real-Time Energy Harvesting Systems. IEEE Transactions on Computers, 63, 1037-1040.
[17]	Garey, M. and Johnson, D. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York.
[18]	Dorigo, M. and Stutzle, T. (2004) Ant Colony Optimization. MIT Press. http://dx.doi.org/10.1007/b99492
[19]	Stutzle, T. and Hoos, H. (1999) Maxmin Ant System. Future Generation Computer Systems, 16, 889-914.