t-kernel: providing reliable OS support to wireless sensor networks

ABSTRACT

The development of a reliable large-scale wireless sensor network (WSN) is very difficult because of resource constraints, energy budget, and demanding application requirements. Three OS features-OS protection, virtual memory, and preemptive scheduling-can significantly improve the reliability of WSN systems and facilitate developing complex WSN software. However, due to the lack of hardware support for privileged execution and address translation, it is impossible to implement these features with traditional OS design techniques. To solve this problem, we design a new OS kernel, the t-kernel, to perform extensive code modification at load time. The modified code and the OS work in a collaborative way supporting the aforementioned features. Having implemented the t-kernel on MICA2 motes, we evaluate its performance by measuring the overhead and execution speed. We analyze the CPU utilization of sensor network applications, and verify that, though CPU-bound tasks execute 1.5-3 times as long as in native mode, application performance under typical workloads does not noticeably degrade. The t-kernel significantly enhances developers' ability to design reliable and sophisticated sensor networks, and includes several new design techniques, such as efficient binary translation on highly constrained sensor nodes, differentiated virtual memory without repeatedly writable swapping devices, and the protection of the OS from application errors without privileged execution hardware.

REFERENCES

• 1: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, ACM SIGPLAN Notices, v.35 n.5, p.1-12, May 2000
• 2: Rimon Barr , John C. Bicket , Daniel S. Dantas , Bowei Du , T. W. Danny Kim , Bing Zhou , Emin Gün Sirer, On the need for system-level support for ad hoc and sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.2, p.1-5, April 2002 [doi>10.1145/509526.509528]
• 3: J. Beutel, O. Kasten, F. Mattern, K. R02mer, F. Siegemund, and L. Thiele. Prototyping wireless sensor networks with BTnodes. In Proc. of 1st European Workshop on Wireless Sensor Networks (EWSN 2004), pages 323--338, Berlin, Germany, Jan. 2004.
• 4: Shah Bhatti , James Carlson , Hui Dai , Jing Deng , Jeff Rose , Anmol Sheth , Brian Shucker , Charles Gruenwald , Adam Torgerson , Richard Han, MANTIS OS: an embedded multithreaded operating system for wireless micro sensor platforms, Mobile Networks and Applications, v.10 n.4, p.563-579, August 2005 [doi>10.1145/1160162.1160178]
• 5: Athanassios Boulis , Chih-Chieh Han , Mani B. Srivastava, Design and implementation of a framework for efficient and programmable sensor networks, Proceedings of the 1st international conference on Mobile systems, applications and services, p.187-200, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066121]
• 6: L.T. Clark, E.J. Hoffman, J. Miller, M. Biyani, Y. Liao, S. Strazdus, M. Morrow, K.E. Velarde, and M.A. Yarch. An embedded 32-b microprocessor core for low-power and high-performance applications. IEEE Journal of Solid-State Circuits, 36(11):1599--1608, Nov. 2001.
• 7: James C. Dehnert , Brian K. Grant , John P. Banning , Richard Johnson , Thomas Kistler , Alexander Klaiber , Jim Mattson, The Transmeta Code Morphing™ Software: using speculation, recovery, and adaptive retranslation to address real-life challenges, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 8: L. Doherty, B.A. Warneke, B. Boser, and K.S.J. Pister. Energy and performance considerations for smart dust. In Intl. Journal of Parallel and Distributed Sensor Networks, pages 121--133, Dec. 2001.
• 9: Adam Dunkels , Bjorn Gronvall , Thiemo Voigt, Contiki - A Lightweight and Flexible Operating System for Tiny Networked Sensors, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), p.455-462, November 16-18, 2004 [doi>10.1109/LCN.2004.38]
• 10: Prabal Dutta , Mike Grimmer , Anish Arora , Steven Bibyk , David Culler, Design of a wireless sensor network platform for detecting rare, random, and ephemeral events, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 11: Kemal Ebcioglu , Erik Altman , Michael Gschwind , Sumedh Sathaye, Dynamic Binary Translation and Optimization, IEEE Transactions on Computers, v.50 n.6, p.529-548, June 2001 [doi>10.1109/12.931892 ]
• 12: Virantha Ekanayake , Clinton Kelly, IV , Rajit Manohar, An ultra low-power processor for sensor networks, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 13: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 14: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 15: Lin Gu , John A. Stankovic, Radio-Triggered Wake-Up for Wireless Sensor Networks, Real-Time Systems, v.29 n.2-3, p.157-182, March 2005 [doi>10.1007/s11241-005-6883-z]
• 16: L. Guand J.A. Stankovic. t-kernel: A translative OS kernel for sensor networks. In UVA CS Tech. Report CS-2005-09, 2005.
• 17: Chih-Chieh Han , Ram Kumar , Roy Shea , Eddie Kohler , Mani Srivastava, A dynamic operating system for sensor nodes, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067188]
• 18: Tian He , Sudha Krishnamurthy , Liqian Luo , Ting Yan , Lin Gu , Radu Stoleru , Gang Zhou , Qing Cao , Pascal Vicaire , John A. Stankovic , Tarek F. Abdelzaher , Jonathan Hui , Bruce Krogh, VigilNet: An integrated sensor network system for energy-efficient surveillance, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.1-38, February 2006 [doi>10.1145/1138127.1138128]
• 19: J. Heidemann and W. Ye. Energy conservation in sensor networks at the link and network layers. USC/ISI Tech. Report ISI-TR-2004-599, 2004.
• 20: Mark Hempstead , Matt Welsh , David Brooks, TinyBench: The Case For A Standardized Benchmark Suite for TinyOS Based Wireless Sensor Network Devices, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), p.585-586, November 16-18, 2004 [doi>10.1109/LCN.2004.129]
• 21: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 22: Wen Hu , Van Nghia Tran , Nirupama Bulusu , Chun Tung Chou , Sanjay Jha , Andrew Taylor, The design and evaluation of a hybrid sensor network for Cane-Toad monitoring, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 23: YoungMin Kwon , Sameer Sundresh , Kirill Mechitov , Gul Agha, ActorNet: an actor platform for wireless sensor networks, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160871]
• 24: Jean J. Labrosse, Microc/OS-II, R & D Books, 1998
• 25: P. Levis, D. Gay, and D. Culler. Active sensor networks. In Proc. of the 2nd USENIX/ACM Symp. on Network Systems Design and Implementation (NSDI), Boston, MA, May 2005.
• 26: Joshua Lifton , Michael Broxton , Joseph A. Paradiso, Experiences and directions in pushpin computing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 27: 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]
• 28: C.B. Margi, V. Petkov, K. Obraczka, and R. Manduchi. Characterizing energy consumption in a visual sensor network testbed. In Proc. of the 2nd Int. IEEE/Create-Net Conf. on Testbeds and Research Infrastructures for the Development of Networks and Communities (TridentCom 2006), March 2006.
• 29: Gaurav Mathur , Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, Ultra-low power data storage for sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127833]
• 30: Lama Nachman , Ralph Kling , Robert Adler , Jonathan Huang , Vincent Hummel, The Intel® Mote platform: a Bluetooth-based sensor network for industrial monitoring, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 31: Parveen Patel , Andrew Whitaker , David Wetherall , Jay Lepreau , Tim Stack, Upgrading transport protocols using untrusted mobile code, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 32: Niels Reijers , Koen Langendoen, Efficient code distribution in wireless sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941359]
• 33: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 34: Robert Wahbe , Steven Lucco , Thomas E. Anderson , Susan L. Graham, Efficient software-based fault isolation, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.203-216, December 05-08, 1993, Asheville, North Carolina, United States

INDEX TERMS

General Terms:
Design, Performance, Reliability

Keywords:
OS protection, binary translation, low-power systems, virtual memory, wireless sensor networks