ELF: an efficient log-structured flash file system for micro sensor nodes

ABSTRACT

An efficient and reliable file storage system is important to micro sensor nodes so that data can be logged for later asynchronous delivery across a multi-hop wireless sensor network. Designing and implementing such a file system for a sensor node faces various challenges. Sensor nodes are highly resource constrained in terms of limited runtime memory, limited persistent storage, and finite energy. Also, the flash storage medium on sensor nodes differs in a variety of ways from the traditional hard disk, e.g. in terms of the limited number of writes for a flash memory unit. We present the design and implementation of ELF, an efficient log-structured flash-based file system tailored for sensor nodes. ELF is adapted to achieve memory efficiency, low power operation, and tailored support for common types of sensor file operations such as appending data to a file. ELF's log-structured approach achieves wear levelling across flash memory pages with limited write lifetimes. ELF also uniquely provides garbage collection capability as well as reliability for micro sensor nodes. A performance evaluation of an implementation of ELF based on TinyOS and MICA2 sensor motes is presented.

REFERENCES

• 1: I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. In IEEE Communications Magazine, Aug 2002.
• 2: 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
• 3: 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]
• 4: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 5: 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]
• 6: The smart-its project, http://www.smart-its.org/.
• 7: The eyes project, http://eyes.eu.org/.
• 8: 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]
• 9: 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]
• 10: James reserve extensible sensing system, http://www.cens.ucla.edu/ eoster/tinydiff/.
• 11: New computing frontiers - the wireless vineyard, http://www.intel.com/labs/features/rs01031.htm.
• 12: Crossbow motes, http://www.xbow.com/.
• 13: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, 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.1060303]
• 14: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 15: P. Levis, N. Patel, D. Culler, and S. Shenker. Trickle: A self-regulating algorithm for code propagation. In Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI), 2004.
• 16: 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]
• 17: A. Kawaguchi, S. Nishioka, and H. Motoda. A flash-memory based file system. In USENIX Winter, pages 155--164, 1995.
• 18: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 19: M. I. Seltzer, K. Bostic, M. McKusick, and C. Staelin. An implementation of a log-structured file system for UNIX. In USENIX Winter, pages 307--326, 1993.
• 20: Michael Wu , Willy Zwaenepoel, eNVy: a non-volatile, main memory storage system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.86-97, October 05-07, 1994, San Jose, California, United States
• 21: Flash memory, intel corporation, 1994.
• 22: F. Douglis, R. Caceres, M. Frans Kaashoek, K. Li, B. Marsh, and J. A. Tauber. Storage alternatives for mobile computers. In Proceedings of the First Symposium on Operating Design and Implementation (OSDI), November 1994.
• 23: D. Woodhouse. Jffs : The journalling flash file system.
• 24: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 25: Deepak Ganesan , Ben Greenstein , Denis Perelyubskiy , Deborah Estrin , John Heidemann, An evaluation of multi-resolution storage for 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.958502]
• 26: D. Ganesan, D. Estrin, and J. Heidemann. Dimensions: Why do we need a new data handling architecture for sensor networks. In First Workshop on Hot Topics in Networks (Hotnets-I), 2002.
• 27: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 28: 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
• 29: P. Levis, S. Madden, D. Gay, J. Polastre, R. Szewczyk, A. Woo, E. Brewer, and D. Culler. The emergence of networking abstractions and techniques in tinyos. In NSDI, 2004.
• 30: Scott Shenker , Sylvia Ratnasamy , Brad Karp , Ramesh Govindan , Deborah Estrin, Data-centric storage in sensornets, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.137-142, January 2003 [doi>10.1145/774763.774785]
• 31: Deepak Ganesan , Ben Greenstein , Denis Perelyubskiy , Deborah Estrin , John Heidemann, An evaluation of multi-resolution storage for 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.958502]

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

General Terms:
Design, Management, Reliability

Keywords:
eeprom, file system, flash, log structured, reliability, sensor