Timely Execution on Intermittently Powered Batteryless Sensors

ABSTRACT

Tiny intermittently powered computers can monitor objects in hard to reach places maintenance free for decades by leaving batteries behind and surviving off energy harvested from the environment--- avoiding the cost of replacing and disposing of billions or trillions of dead batteries. However, creating programs for these sensors is difficult. Energy harvesting is inconsistent, energy storage is scarce, and batteryless sensors can lose power at any point in time--- causing volatile memory, execution progress, and time to reset. In response to these disruptions, developers must write unwieldy programs attempting to protect against failures, instead of focusing on sensing goals, defining tasks, and generating useful data in a timely manner. To address these shortcomings, we have designed Mayfly, a language and runtime for timely execution of sensing tasks on tiny, intermittently-powered, energy harvesting sensing devices. Mayfly is a coordination language and runtime built on top of Embedded-C that combines intermittent execution fragments to form coherent sensing schedules---maintaining forward progress, data consistency, data freshness, and data utility across multiple power failures. Mayfly makes the passing of time explicit, binding data to the time it was gathered, and keeping track of data and time through power failures. We evaluated Mayfly against state-of-the art systems, conducted a user study, and implemented multiple real world applications across application domains in inventory tracking, and wearables.

References

1. Domenico Balsamo, Alex S Weddell, Geoff V Merrett, Bashir M Al-Hashimi, Davide Brunelli, and Luca Benini. 2015. Hibernus: Sustaining computation during intermittent supply for energy-harvesting systems. Embedded Systems Letters, IEEE 7, 1 (2015), 15--18.
2. Gérard Berry and Georges Gonthier. 1992. The Esterel synchronous programming language: Design, semantics, implementation. Science of computer programming 19, 2 (1992), 87--152.
3. Naveed Bhatti and Luca Mottola. 2016. Efficient State Retention for Transiently-powered Embedded Sensing. In Proceedings of the 13th ACM International Conference on Embedded Wireless Systems and Networks (EWSN) Graz (Austria).
4. Naveed Anwar Bhatti and Luca Mottola. 2017. HarvOS: Efficient Code Instrumentation for Transiently-powered Embedded Sensing. In Proceedings of the 16th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN '17). ACM, New York, NY, USA, 209--219.
5. Michael Buettner, Ben Greenstein, and David Wetherall. 2011. Dewdrop: An Energy-Aware Task Scheduler for Computational RFID. In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation.
6. Michael Buettner, Richa Prasad, Matthai Philipose, and David Wetherall. 2009. Recognizing daily activities with RFID-based sensors. In Proceedings of the 11th international conference on Ubiquitous computing. ACM, 51--60.
7. Brendan Burns, Kevin Grimaldi, Alexander Kostadinov, Emery D Berger, and Mark D Corner. 2006. Flux: A Language for Programming High-Performance Servers. In In Proceedings of USENIX Annual Technical Conference.
8. Alexei Colin, Graham Harvey, Brandon Lucia, and Alanson P. Sample. 2016. An Energy-interference-free Hardware-Software Debugger for Intermittent Energy-harvesting Systems. In Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '16). ACM, New York, NY, USA, 577--589.
9. Alexei Colin and Brandon Lucia. 2016. Chain: Tasks and Channels for Reliable Intermittent Programs. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016). ACM, New York, NY, USA, 514--530.
10. Roland Flury and Roger Wattenhofer. 2010. Slotted Programming for Sensor Networks. In Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN '10). ACM, New York, NY, USA, 24--34.
11. D. Gay, P. Levis, R. von Behren, M. Welsh, E. Brewer, and D. Culler. 2003. The nesC Language: A Holistic Approach to Networked Embedded Systems. In Proc. ACM SIGPLAN 2003 Conf. Programming Language Design and Implementation (PLDI'03). ACM, San Diego, CA, USA, 1--11.
12. Nicholas Halbwachs, Paul Caspi, Pascal Raymond, and Daniel Pilaud. 1991. The synchronous data flow programming language LUSTRE. Proc. IEEE 79, 9 (1991), 1305--1320.
13. Josiah Hester, Nicole Tobias, Amir Rahmati, Lanny Sitanayah, Daniel Holcomb, Kevin Fu, Wayne P. Burleson, and Jacob Sorber. 2016. Persistent Clocks for Batteryless Sensing Devices. ACM Trans. Embed. Comput. Syst. 15, 4, Article 77 (Aug. 2016), 28 pages.
14. Matthew Hicks. 2017. Clank: Architectural Support for Intermittent Computation. In Proceedings of the 44th Annual International Symposium on Computer Architecture. ACM, 228--240.
15. Harishankar Jayakumar, Arnab Raha, and Vijay Raghunathan. 2014. QuickRecall: A low overhead HW/SW approach for enabling computations across power cycles in transiently powered computers. In VLSI Design and 2014 13th International Conference on Embedded Systems, 2014 27th International Conference on. IEEE, 330--335.
16. Paul LeGuernic, Thierry Gautier, Michel Le Borgne, and Claude Le Maire. 1991. Programming real-time applications with SIGNAL. Proc. IEEE 79, 9 (1991), 1321--1336.
17. Logic-less templates. 2017. Mustache Logic-less templates. http://mustache.github.io/. (2017). Last Viewed March 22, 2017.
18. Konrad Lorincz, Bor-rong Chen, Jason Waterman, Geoff Werner-Allen, and Matt Welsh. 2008. Resource Aware Programming in the Pixie OS. In Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems (SenSys '08). ACM, New York, NY, USA, 211--224.
19. Brandon Lucia and Benjamin Ransford. 2015. A Simpler, Safer Programming and Execution Model for Intermittent Systems. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2015). ACM, New York, NY, USA, 575--585.
20. Brandon Lucia and Benjamin Ransford. 2015. A Simpler, Safer Programming and Execution Model for Intermittent Systems. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '15). ACM, New York, NY, USA, 575--585.
21. Geoffrey Mainland, Greg Morrisett, and Matt Welsh. 2008. Flask: Staged functional programming for sensor networks. In ACM Sigplan Notices, Vol. 43. ACM, 335--346.
22. Geoff V Merrett and Bashir M Al-Hashimi. 2017. Energy-driven computing: Rethinking the design of energy harvesting systems. In 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 960--965.
23. Azalia Mirhoseini, Ebrahim M Songhori, and Farinaz Koushanfar. 2013. Automated checkpointing for enabling intensive applications on energy harvesting devices. In Proceedings of the 2013 International Symposium on Low Power Electronics and Design. IEEE Press, 27--32.
24. Luca Mottola and Gian Pietro Picco. 2011. Programming Wireless Sensor Networks: Fundamental Concepts and State of the Art. ACM Comput. Surv. 43, 3, Article 19 (April 2011), 51 pages.
25. Amir Rahmati, Mastooreh Salajegheh, Dan Holcomb, Jacob Sorber, Wayne P. Burleson, and Kevin Fu. 2012. TARDIS: Time and Remanence Decay in SRAM to Implement Secure Protocols on Embedded Devices without Clocks. In Presented as part of the 21st USENIX Security Symposium (USENIX Security 12). USENIX, Bellevue, WA, 221--236. https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/rahmati
26. Benjamin Ransford, Jacob Sorber, and Kevin Fu. 2011. Mementos: System Support for Long-Running Computation on RFID-Scale Devices.. In Proceedings of the 16th Intl. Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
27. A. Rodriguez, D. Balsamo, Z. Luo, S. P. Beeby, G. V. Merrett, and A. S. Weddel. 2017. Intermittently-powered energy harvesting step counter for fitness tracking. In 2017 IEEE Sensors Applications Symposium (SAS). 1--6.
28. A. P. Sample, D. J. Yeager, P. S. Powledge, A. V. Mamishev, and J. R. Smith. 2008. Design of an RFID-Based Battery-Free Programmable Sensing Platform. IEEE Trans. Instrumentation and Measurement 57, 11 (Nov. 2008), 2608--2615.
29. Jacob Sorber, Alexander Kostadinov, Matthew Garber, Matthew Brennan, Mark D. Corner, and Emery D. Berger. 2007. Eon: A Language and Runtime System for Perpetual Systems. In Proceedings of ACM Conference on Embedded Networked Sensor Systems (SenSys).
30. Peter Wägemann, Tobias Distler, Heiko Janker, Phillip Raffeck, and Volkmar Sieh. 2016. A Kernel for Energy-Neutral Real-Time Systems with Mixed Criticalities. (2016).
31. Joel Van Der Woude and Matthew Hicks. 2016. Intermittent Computation without Hardware Support or Programmer Intervention. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). USENIX Association, GA, 17--32. https://www.usenix.org/conference/osdi16/technical-sessions/presentation/vanderwoude
32. Hong Zhang, Jeremy Gummeson, Benjamin Ransford, and Kevin Fu. 2011. Moo: A Batteryless Computational RFID and Sensing Platform. Technical Report UM-CS-2011-020. UMass Amherst Department of Computer Science.
33. Pengyu Zhang, Deepak Ganesan, and Boyan Lu. 2013. QuarkOS: Pushing the Operating Limits of Micro-powered Sensors. In Proceedings of the 14th USENIX Conference on Hot Topics in Operating Systems (HotOS'13). USENIX Association, Berkeley, CA, USA, 7--7. http://dl.acm.org/citation.cfm?id=2490483.2490490
34. Ting Zhu, Abedelaziz Mohaisen, Yi Ping, and Don Towsley. 2012. DEOS: Dynamic energy-oriented scheduling for sustainable wireless sensor networks. In INFOCOM, 2012 Proceedings IEEE. IEEE, 2363--2371.

Index Terms

• Computer systems organization

  • Architectures

  • Embedded and cyber-physical systems

    • Embedded systems

• Human-centered computing

  • Ubiquitous and mobile computing

    • Ubiquitous and mobile computing systems and tools

• Software and its engineering

  • Software notations and tools

    • Context specific languages