MANTIS OS: an embedded multithreaded operating system for wireless micro sensor platforms

ABSTRACT

The MANTIS MultimodAl system for NeTworks of In-situ wireless Sensors provides a new multithreaded cross-platform embedded operating system for wireless sensor networks. As sensor networks accommodate increasingly complex tasks such as compression/aggregation and signal processing, preemptive multithreading in the MANTIS sensor OS (MOS) enables micro sensor nodes to natively interleave complex tasks with time-sensitive tasks, thereby mitigating the bounded buffer producer-consumer problem. To achieve memory efficiency, MOS is implemented in a lightweight RAM footprint that fits in less than 500 bytes of memory, including kernel, scheduler, and network stack. To achieve energy efficiency, the MOS power-efficient scheduler sleeps the microcontroller after all active threads have called the MOS sleep() function, reducing current consumption to the µA range. A key MOS design feature is flexibility in the form of cross-platform support and testing across PCs, PDAs, and different micro sensor platforms. Another key MOS design feature is support for remote management of in-situ sensors via dynamic reprogramming and remote login.

REFERENCES

• 1: H. Abrach , S. Bhatti , J. Carlson , H. Dai , J. Rose , A. Sheth , B. Shucker , J. Deng , R. Han, MANTIS: system support for multimodAl NeTworks of in-situ sensors, 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.941358]
• 2: Atul Adya , Jon Howell , Marvin Theimer , William J. Bolosky , John R. Douceur, Cooperative Task Management Without Manual Stack Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.289-302, June 10-15, 2002
• 3: [3] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, A Survey on Sensor Networks, IEEE Communications Magazine, (August 2002).
• 4: David H. Albonesi , Rajeev Balasubramonian , Steven G. Dropsho , Sandhya Dwarkadas , Eby G. Friedman , Michael C. Huang , Volkan Kursun , Grigorios Magklis , Michael L. Scott , Greg Semeraro , Pradip Bose , Alper Buyuktosunoglu , Peter W. Cook , Stanley E. Schuster, Dynamically Tuning Processor Resources with Adaptive Processing, Computer, v.36 n.12, p.49-58, December 2003 [doi>10.1109/MC.2003.1250883]
• 5: [5] Atmel AVR 8-bit RISC processor, http://www.atmel.com/products/AVR
• 6: [6] AVRX Real-Time Multitasking Kernel for the Atmel AVR series of micro controllers, http://www.barello.net/avrx/index.htm.
• 7: [7] A. Bookstein and S.T. Klein, Is Huffman coding dead?. Computing 50 (1993) 279-296.
• 8: [8] J. Carlson, R. Han, S. Lao, C. Narayan and S. Sanghani, Rapid Prototyping Of Mobile Input Devices Using Wireless Sensor Nodes, in: 5th IEEE Workshop On Mobile Computing Systems and Applications (WMCSA) (2003).
• 9: J. D. Case , M. Fedor , M. L. Schoffstall , J. Davin, Simple Network Management Protocol (SNMP), RFC Editor, 1990
• 10: [10] Crossbow, http://www.xbow.com/.
• 11: [11] Crossbow motes, http://www.xbow.com.
• 12: Hui Dai , Richard Han, TSync: a lightweight bidirectional time synchronization service for wireless sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.1, January 2004 [doi>10.1145/980159.980173]
• 13: [13] B. Deb, S. Bhatnagar and B. Nath, A Topology Discovery Algorithm for Sensor Networks with Applications to Network Management, DCS Technical Report DCS-TR-441, Rutgers University (May 2001).
• 14: [14] J. Deng, R. Han and S. Mishra, A Performance Evaluation of Intrusion-Tolerant Routing in Wireless Sensor Networks, IEEE 2nd International Workshop on Information Processing in Sensor Networks (IPSN '03), (2003), Palo Alto, California, pp. 349-364.
• 15: Jeremy Elson , Deborah Estrin, Time Synchronization for Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.186, April 23-27, 2001
• 16: [16] J. Elson and K. Rmer, Wireless Sensor Networks: A New Regime for Time Synchronization, in: proceedings of the First Workshop on Hot Topics In Networks (HotNets-I), Princeton, New Jersey, October 28-29 (2002).
• 17: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 18: [18] J. Elson, S. Bien, N. Busek, V. Bychkovskiy, A. Cerpa, D. Ganesan, L. Girod, B. Greenstein, T. Schoellhammer, T. Stathopoulos and D. Estrin, EmStar: An Environment for Developing Wireless Embedded Systems Software, CENS Technical Report 0009, (March 24) 2003.
• 19: [19] D. Ely, S. Savage, and D. Wetherall, Alpine: A User-level Infrastructure For Network Protocol Development," in: Proc. 3rd USENIX Symposium on Internet Technologies and Systems (March 2001) pp. 171-183.
• 20: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 21: [21] S. Ganeriwal, R. Kumar, S. Adlakha and M. Srivastava, Network-wide Time Synchronization in Sensor Networks, Technical report, UCLA, Dept of Electrical Engineering (2002).
• 22: [22] L. Girod, J. Elson, A. Cerpa, T. Stathopoulos, N. Ramanathan and D. Estrin, EmStar: A Software Environment for Developing and Deploying Wireless Sensor Networks, to appear in the Proceedings of USENIX 04.
• 23: [23] D. Grunwald, C.B. Morrey III, P. Levis, M. Neufeld and K. Farkas, Policies for Dynamic Clock Scheduling, Operating Systems Design and Implementation (2000).
• 24: William R. Hamburgen , Deborah A. Wallach , Marc A. Viredaz , Lawrence S. Brakmo , Carl A. Waldspurger , Joel F. Bartlett , Timothy Mann , Keith I. Farkas, Itsy: Stretching the Bounds of Mobile Computing, Computer, v.34 n.4, p.28-36, April 2001 [doi>10.1109/2.917534]
• 25: 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
• 26: 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]
• 27: [27] H.K. Jerry Chu, Zero-Copy TCP in Solaris, in: Proceedings of the USENIX 1996 Annual Technical Conference, San Diego, California (January 1996).
• 28: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 29: Jean Kumagai, The secret life of birds, IEEE Spectrum, v.41 n.4, p.42-48, April 2004 [doi>10.1109/MSPEC.2004.1279193]
• 30: [30] J. Labrosse, MicroC/OS-II: The Real-Time Kernel, 2nd edition, CMP Books, (November 1998).
• 31: [31] H.C. Lauer and R.M. Needham, On the Duality of Operating System Structures, in Second International Symposium on Operating Systems, IR1A (October 1978).
• 32: [32] J. Larus and M. Parkes, Using Cohort Scheduling to Enhance Server Performance, Technical Report MSR-TR-2001-39, Microsoft Research, (March 2001).
• 33: [33] P. Levis and N. Lee, Simulating Tinyos Networks. http://www. cs.berkeley.edu/pal/research/tossim.html.
• 34: Philip Levis , David Culler, Maté: a tiny virtual machine for sensor networks, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 35: Martin Leopold , Mads Bondo Dydensborg , Philippe Bonnet, Bluetooth and sensor networks: a reality check, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958504]
• 36: Charles Lefurgy , Karthick Rajamani , Freeman Rawson , Wes Felter , Michael Kistler , Tom W. Keller, Energy Management for Commercial Servers, Computer, v.36 n.12, p.39-48, December 2003 [doi>10.1109/MC.2003.1250880]
• 37: Jiong Luo , Niraj K. Jha, Battery-aware static scheduling for distributed real-time embedded systems, Proceedings of the 38th conference on Design automation, p.444-449, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378553]
• 38: 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]
• 39: F. Martin , B. Mikhak , B. Silverman, MetaCricket: a designer's kit for making computational devices, IBM Systems Journal, v.39 n.3-4, p.795-815, July 2000
• 40: F. Martin , B. Mikhak , B. Silverman, MetaCricket: a designer's kit for making computational devices, IBM Systems Journal, v.39 n.3-4, p.795-815, July 2000
• 41: [41] R. Min, M. Bhardwaj, S. Cho et al., An Architecture for a Power-Aware Distributed Microsensor Node, in: IEEE Workshop on Signal Proc. Systems (Oct 2000) pp. 581-590.
• 42: [42] Ning Xu, Implementation of Data Compression and FFT on TinyOS, Embedded Networks Laboratory, Computer Science Dept. USC. Los Angeles, http://enl.usc.edu/ningxu/papers/lzfft.pdf.
• 43: [43] J.K. Ousterhout, Why Threads Are A Bad Idea (for most purposes), Presentation given at the 1996 Usenix Annual Technical Conference, (January 1996).
• 44: Sung Park , Andreas Savvides , Mani B. Srivastava, SensorSim: a simulation framework for sensor networks, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.104-111, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346870]
• 45: Luiz Felipe Perrone , David M. Nicol, Network modeling and simulation: a scalable simulator for TinyOS applications, Proceedings of the 34th conference on Winter simulation: exploring new frontiers, December 08-11, 2002, San Diego, California
• 46: [46] Portable Operating System Interface(POSIX)-Part 1: System Application Programming Interface (API)[C Language] ISO/IEC 9945-1:1996, IEEE.
• 47: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 48: [48] R.L. Rivest, the RC5 Encryption Algorithm, in: Proceedings of the 1994 Leuven Workshop on Fast Software Encryption, pp. 86-96.
• 49: [49] Single chip ultra low power RF transceiver http://www.chipcon.com/ files/CC1000_Data_Sheet_2_1.pdf, 2001.
• 50: [50] Simple Network Time Protocol, (SNTP) version 4. IETF RFC 2030.
• 51: [51] A. Sheth, B. Shucker and R. Han, VLM2: A Very Lightweight Mobile Multicast System for Wireless Sensor Networks, IEEE Wireless Communications and Networking Conference ( WCNC) (2003), New Orleans, Louisiana.
• 52: [52] The Smart-Its project, http://www.smart-its.org/.
• 53: [53] The Eyes project, http://eyes.eu.org/.
• 54: Sameer Tilak , Nael B. Abu-Ghazaleh , Wendi Heinzelman, A taxonomy of wireless micro-sensor network models, ACM SIGMOBILE Mobile Computing and Communications Review, v.6 n.2, p.28-36, April 2002 [doi>10.1145/565702.565708]
• 55: [55] R. von Behren, J. Condit and E. Brewer, Why Events Are A Bad Idea (for High-concurrency Servers), 9th Workshop on Hot Topics in Operating Systems (HotOS IX) (2003).
• 56: [56] E. Welsh, W. Fish and P. Frantz, GNOMES: A Testbed for Low-Power Heterogeneous Wireless Sensor Networks, IEEE International Symposium on Circuits and Systems (ISCAS), Bangkok, Thailand, (2003).
• 57: [57] Wei Ye, John Heidemann and Deborah Estrin, An Energy-Efficient MAC Protocol for Wireless Sensor Networks, in: Proceedings INFOCOM , New York, NY, USA, (June 2002).
• 58: [58] WINE, http://www.winehq.com/.
• 59: [59] J. Zhao, R. Govindan and D. Estrin, Computing Aggregates for Monitoring Wireless Sensor Networks, First IEEE International Workshop on Sensor Network Protocols and Applications, Anchorage, AK. (May 2003).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.0 General

General Terms:
Design, Performance

Keywords:
cross-platform, dynamic reprogramming, embedded operating system, lightweight, low power, multithreaded, sensor networks