Performance aware tasking for environmentally powered sensor networks

ABSTRACT

The use of environmental energy is now emerging as a feasible energy source for embedded and wireless computing systems such as sensor networks where manual recharging or replacement of batteries is not practical. However, energy supply from environmental sources is highly variable with time. Further, for a distributed system, the energy available at its various locations will be different. These variations strongly influence the way in which environmental energy is used. We present a harvesting theory for determining performance in such systems. First we present a model for characterizing environmental sources. Second, we state and prove two harvesting theorems that help determine the sustainable performance level from a particular source. This theory leads to practical techniques for scheduling processes in energy harvesting systems. Third, we present our implementation of a real embedded system that runs on solar energy and uses our harvesting techniques. The system adjusts its performance level in response to available resources. Fourth, we propose a localized algorithm for increasing the performance of a distributed system by adapting the process scheduling to the spatio-temporal characteristics of the environmental energy in the distributed system. While our theoretical intuition is based on certain abstractions, all the scheduling methods we present are motivated solely from the experimental behavior and resource constraints of practical sensor networking systems.

REFERENCES

• 1: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 2: A Distributed Computation Platform for Wireless Embedded Sensing, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.220, September 16-18, 2002
• 3: J. Rabaey , J. Ammer , J. L. da Silva Jr. , D. Patel, PicoRadio: Ad-Hoc Wireless Networking of Ubiquitous Low-Energy Sensor/Monitor Nodes, Proceedings of the IEEE Computer Society Annual Workshop on VLSI (WVLSI'00), p.9, April 27-28, 2000
• 4: Andrew Blanchard, Andrew Cilia, and James Cai. High bandwidth mega-mesh sensor networks. In High-Speed Networking Workshop IEEE HSN (in conjunction with INFOCOM 2003), San Francisco, California, USA, March 2003.
• 5: Mani Srivastava , Richard Muntz , Miodrag Potkonjak, Smart kindergarten: sensor-based wireless networks for smart developmental problem-solving enviroments, Proceedings of the 7th annual international conference on Mobile computing and networking, p.132-138, July 2001, Rome, Italy [doi>10.1145/381677.381690]
• 6: Philipp Steurer , Mani B. Srivastava, System Design of Smart Table, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.473, March 23-26, 2003
• 7: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 8: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 9: Jeff Burke, Eitan Mendelowitz, Joseph Kim, and Rex Lorenzo. Networking with knobs and knats: Towards ubiquitous computing for artists. In Ubiquitous Computing, Concepts and Models Workshop, Gothenburg, Sweden, 2002.
• 10: Darpa energy harvesting projects. http://www.darpa.mil/dso/trans/energy/projects.html.
• 11: Werner Weber, Ambient intelligence: industrial research on a visionary concept, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871567]
• 12: Chris Melhuish. The ecobot project. www.ias.uwe.ac.uk/energy autonomy/EcoBot web page.html.
• 13: Jan M. Rabaey , M. Josie Ammer , Julio L. da Silva , Danny Patel , Shad Roundy, PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking, Computer, v.33 n.7, p.42-48, July 2000 [doi>10.1109/2.869369 ]
• 14: Joseph A. Paradiso , Mark Feldmeier, A Compact, Wireless, Self-Powered Pushbutton Controller, Proceedings of the 3rd international conference on Ubiquitous Computing, p.299-304, September 30-October 02, 2001, Atlanta, Georgia, USA
• 15: Scott Meninger , Jose Oscar Mur-Miranda , Rajeevan Amirtharajah , Anantha Chandrakasan , Jeffrey Lang, Vibration-to-electric energy conversion, Proceedings of the 1999 international symposium on Low power electronics and design, p.48-53, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313840]
• 16: Mica, mica2 motes and sensors. http://www.xbow.com/.
• 17: Andreas Savvides. Medusa mk-2 node. http://nesl.ee.ucla.edu/projects/ahlos/hardware.htm.
• 18: John Kymissis , Clyde Kendall , Joseph Paradiso , Neil Gershenfeld, Parasitic Power Harvesting in Shoes, Proceedings of the 2nd IEEE International Symposium on Wearable Computers, p.132, October 19-20, 1998
• 19: Nathan S. Shenck , Joseph A. Paradiso, Energy Scavenging with Shoe-Mounted Piezoelectrics, IEEE Micro, v.21 n.3, p.30-42, May 2001 [doi>10.1109/40.928763 ]
• 20: T. Starner, Human-powered wearable computing, IBM Systems Journal, v.35 n.3-4, p.618-629, 1996
• 21: Mohammed Rahimi, Hardik Shah, Gaurav S. Sukhatme, John Heidemann, and D. Estrin. Studying the feasibility of energy harvesting in a mobile sensor network. In IEEE Int'l Conference on Robotics and Automation, 2003.
• 22: William J. Kaiser, Gregory J. Pottie, Mani Srivastava, Gaurav S. Sukhatme, John Villasenor, and Deborah Estrin. Networked infomechanical systems (nims) for ambient intelligence. Technical Report CENS Technical Report 31, Center of Embedded and Networked Sensing, UCLA, 2003.
• 23: S.E. Wright, D.S. Scott, J.B. Haddow, and M.A. Rosen. The upper limit to solar energy conversion. volume 1, pages 384--392, July 2000.
• 24: Pravin Bhagwat, Bhaskaran Raman, and Dheeraj Sanghi. Turning 802.11 inside-out. In Workshop on Hot Topics in Networks (HotNets-II), November 2003.
• 25: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 26: V. Raghunathan, C. Schurgers, S. Park, and M. Srivastava. Energy aware wireless microsensor networks. IEEE Signal Processing Magazine, 19(2):40--50, March 2002.
• 27: R. Min, M. Bhardwaj, S. Cho, A. Sinha, E. Shih, A. Wang, and A. Chandrakasan. An architecture for a power-aware distributed microsensor node. In IEEE Workshop on Signal Processing Systems (SiPS '00), October 2000.
• 28: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 29: M. Younis , M. Youssef , K. Arisha, Energy-Aware Routing in Cluster-Based Sensor Networks, Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'02), p.129, October 11-16, 2002
• 30: Rahul C. Shah and Jan M. Rabaey. Energy aware routing for low energy ad hoc sensor networks. In Proc. IEEE Wireless Communications and Networking Conference (WCNC), volume 1, pages 350--355, Orlando, FL, March, 17-21 2002.
• 31: Qun Li , Javed Aslam , Daniela Rus, Online power-aware routing in wireless Ad-hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.97-107, July 2001, Rome, Italy [doi>10.1145/381677.381687]
• 32: Jae-Hwan Chang and Leandros Tasiulas. Maximum lifetime routing in wireless sensor networks. In Advanced Telecommunications and Information Distribution Research Program (ATIRP), College Park, MD, USA, March 2000.
• 33: Morteza Maleki, Karthik Dantu, and Massoud Pedram. Lifetime prediction routing in mobile ad hoc networks. In Wireless Communication and Networking Conference, New Orleans, FL, USA, March 2003.
• 34: V. Rodoplu and Teresa H. Meng. Minimum energy mobile wireless networks. In IEEE International Conference on Communications, volume 3, pages 1633--1639, Atlanta, GA, USA, June 1998.
• 35: R.G. Gallager, P.A. Humblet, and P.M. Spira. A distributed algorithm for minimum weight spanning trees. Technical Report LID-P-906-A, Lab. Information Decision Systems, Massachusetts Institute of Technology, October 1979.
• 36: Konstantinos Kalpakis, Koustuv Dasgupta, and Parag Namjoshi. Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Technical Report UMBC-TR-02-13, Department of Computer Science and Electrical Engineering,University of Maryland, Baltimore County, August 2002. Accepted for publication in Computer Networks.
• 37: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 38: L. Shang, R. P. Dick, and N. K. Jha. An economics-based power-aware protocol for computation distribution in mobile ad-hoc networks. In 14th IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS), November 2002.
• 39: Peng Rong , Massoud Pedram, Extending the lifetime of a network of battery-powered mobile devices by remote processing: a markovian decision-based approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776060]
• 40: Jerry Zhao, Ramesh Govindan, and Deborah Estrin. Residual energy scans for monitoring wireless sensor networks. In IEEE Wireless Communications and Networking Conference (WCNC'02), volume 1, pages 356--362, Orange County Convention Center, Orlando, FL, USA, 17-21 March 2002.
• 41: Raquel A. F. Mini, Badri Nath, and Antonio A. F. Loureiro. A probabilistic approach to predict the energy consumption in wireless sensor networks. In IV Workshop de Comunicao sem Fio e Computao Mvel, So Paulo, Brazil, October 23-25 2002.
• 42: Aman Kansal , Mani B. Srivastava, An environmental energy harvesting framework for sensor networks, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871624]
• 43: Thiemo Voigt , Hartmut Ritter , Jochen Schiller, Utilizing Solar Power in Wireless Sensor Networks, Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks, p.416, October 20-24, 2003
• 44: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 45: Manish Bhardwaj and A. P. Chandrakasan. Bounding the lifetime of sensor networks via optimal role assignments. In INFOCOM 2002, pages 1587--1596, New York, USA, June 2002.
• 46: M. Bhardwaj, T. Garnett, and A.P. Chandrakasan. Upper bounds on the lifetime of sensor networks. In IEEE International Conference on Communications, June 2001.
• 47: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 48: Abhay K. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. PhD thesis, Massachusetts Institute of Technology, February 1992.
• 49: R.L. Cruz. A calculus for network delay, part I: Network elements in isolation. IEEE Transactions on Information Theory, 37:114--131, 1991.
• 50: R.L. Cruz. A calculus for network delay, part II: Network analysis. IEEE Transactions on Information Theory, 37:132--141, 1991.
• 51: C. Dovrolis, Maruthy Vedam, and Parmesh Ramanathan. The selection of the token bucket parameters in the ietf guaranteed service class. Technical report, Georgia Institute of Technology, 1998.
• 52: S. Low and P. Varaiya. A simple theory of traffic and resource allocation in atm. In IEEE Infocom, pages 1633--1637, 1994.
• 53: Rex Min , Travis Furrer , Anantha Chandrakasan, Dynamic Voltage Scaling Techniques for Distributed Microsensor Networks, Proceedings of the IEEE Computer Society Annual Workshop on VLSI (WVLSI'00), p.43, April 27-28, 2000
• 54: Panasonic solar cells technical handbook. http://www.solarbotics.net/library/datasheets/sunceram.pdf.
• 55: Low power thermoelectric generators. http://www.dts-generator.com/main-e.htm.
• 56: D. Rakhmatov, S. Vrudhula, and D.A. Wallach. A model for battery lifetime analysis for organizing applications on a pocket computer. IEEE Transactions on VLSI systems, to appear.
• 57: Daler Rakhmatov , Sarma Vrudhula, Energy management for battery-powered embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.3, p.277-324, August 2003 [doi>10.1145/860176.860179]
• 58: A.L. Andrady, S.H. Hamid, X. Hu, and A. Torikai. Effects of increased solar ultraviolet radiation on materials. http://www.gcrio.org/UNEP1998/UNEP98p60.html.
• 59: Energgizer no. NH15. http://data.energizer.com/. AA Rechargeable NiMH battery Datasheet.
• 60: Overview of 1-wire technology and its use. http://www.maxim-ic.com/appnotes.cfm/appnote number/1796/ln/en.
• 61: Tinyos: a component based os for the networked sensor regime. http://webs.cs.berkeley.edu/tos/.
• 62: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Optimizing Sensor Networks in the Energy-Latency-Density Design Space, IEEE Transactions on Mobile Computing, v.1 n.1, p.70-80, January 2002 [doi>10.1109/TMC.2002.1011060 ]
• 63: Bluetooth core specification ver 1v102. http://www.bluetooth.org.
• 64: Ieee p802.11 wireless LAN standard. http://grouper.ieee.org/groups/802/11/main.html.
• 65: Wei Ye, John Heidemann, and Deborah Estrin. An energy-efficient mac protocol for wireless sensor networks. In 21st International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), New York, NY, USA, June 2002.
• 66: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
energy harvesting, performance guarantees, process scheduling