Dali: a communication-centric data abstraction layer for energy-constrained devices in mobile sensor networks

ABSTRACT

Communications in mobile and frequently-disconnected sensor networks are characterized by low-bandwidth radios, unreliable links, and disproportionately high energy costs compared to other system operations. Therefore, we must use as efficiently as possible any periods of connectivity that we have. For this reason, nodes in these networks need mechanisms that organize data to streamline search operations, local computation, and communications.

This work proposes a Data Abstraction Layer (DALi), which is inserted between the application layer and the file system. DALi organizes data with networking in mind to facilitate the development of services for Data Search, Naming, and Reduction that combine to make communications more efficient. From the resulting two-tiered data hierarchy, we develop a multi-layer drill-down search structure that can locate data multiple orders of magnitude faster (and with much lower energy) than simpler data storage structures. Additionally, DALi conserves energy and bandwidth through a mechanism that acknowledges and removes specific data segments from a mobile sensor network. Finally, it seamlessly integrates in a lossless compression algorithm specifically designed for sensor networks to save additional energy.

REFERENCES

• 1: Aleph One. Yet Another Flash File System. öhttp://www.aleph1.co.uk/yaffs.
• 2: Appalachian Trail Conservancy. Appalachian Trail GIS and GPS Data. http://www.appalachiantrail.org/, Mar. 2002.
• 3: ATMEL. AT45DB041B, 4M bit, 2.7--Volt Only Serial--Interface Flash with Two 264--Byte SRAM Buffers data sheet. http://www.atmel.com/, June 2003.
• 4: D. Carlson. Sensor Networks in Polar Regions: Urgent Needs, Difficult Challenges. Keynote Presentation, ACM Conf. on Embedded Networked Sensor Systems (SenSys), Nov. 2006.
• 5: B. Cohen. Incentives Build Robustness in BitTorrent. http://www.bittorrent.org/bittorrentecon.pdf, May 2003.
• 6: Hui Dai , Michael Neufeld , Richard Han, ELF: an efficient log-structured flash file system for micro sensor nodes, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031516]
• 7: C. Decker, M. Beigl, and A. Krohn. A File System for System Programming in Ubiquitous Computing. In Intl. Conf. on the Architecture of Computing Systems, Mar. 2005.
• 8: 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]
• 9: Deepak Ganesan , Ben Greenstein , Deborah Estrin , John Heidemann , Ramesh Govindan, Multiresolution storage and search in sensor networks, ACM Transactions on Storage (TOS), v.1 n.3, p.277-315, August 2005 [doi>10.1145/1084779.1084780]
• 10: D. Gay. Design of Matchbox, the Simple Filing System for Motes. http://www.tinyos.net, Aug. 2003.
• 11: J. Gehrke and S. Madden. Query Processing in Sensor Networks. Pervasive Computing, Jan. 2004.
• 12: Joanna Kulik , Wendi Heinzelman , Hari Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks, v.8 n.2/3, p.169-185, March-May 2002 [doi>10.1023/A:1013715909417 ]
• 13: 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]
• 14: 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
• 15: Joanna Kulik , Wendi Heinzelman , Hari Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks, v.8 n.2/3, p.169-185, March-May 2002 [doi>10.1023/A:1013715909417 ]
• 16: Song Lin , Demetrios Zeinalipour-Yazti , Vana Kalogeraki , Dimitrios Gunopulos , Walid A. Najjar, Efficient indexing data structures for flash-based sensor devices, ACM Transactions on Storage (TOS), v.2 n.4, p.468-503, November 2006 [doi>10.1145/1210596.1210601]
• 17: A. Lindgren, A. Doria, and O. Schelen. Probabilistic Routing in Intermittently Connected Networks. In Intl. Wksp. on Service Assurance with Partial and Intermittent Resources, Sept. 2004.
• 18: Ting Liu , Margaret Martonosi, Impala: a middleware system for managing autonomic, parallel sensor systems, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 19: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 20: Gaurav Mathur , Peter Desnoyers , Deepak Ganesan , Prashant Shenoy, Capsule: an energy-optimized object storage system for memory-constrained sensor devices, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182827]
• 21: 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]
• 22: Maxstream, Inc. XTend OEM RF Module: Product Manual v1.2.4. http://www.maxstream.net/, Oct. 2005.
• 23: S. Rajagopalan and C.-C. Shen. A Cross--Layer, Decentralized BitTorrent for Mobile Ad hoc Networks. In Proc. of MOBIQUITOUS'06, July 2006.
• 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: Christopher M. Sadler , Margaret Martonosi, Data compression algorithms for energy-constrained devices in delay tolerant networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182834]
• 26: R. C. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a Three--tier Architecture for Sparse Sensor Networks. In Proc. of IEEE Workshop on Sensor Network Protocols and Applications, May 2003.
• 27: ST. M45PE40: 8 Mbit, Low Voltage, Page--Erasable Serial Flash MemoryWith Byte--Alterability and a 33 MHz SPI Bus Interface. http://www.st.com/, Feb. 2006.
• 28: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 29: Texas Instruments. MSP430x161x Mixed Signal Microcontroller Datasheet. http://www.ti.com/, Mar. 2005.
• 30: Sameer Tilak , Bhanu Pisupati , Kenneth Chiu , Geoffrey Brown , Nael Abu-Ghazaleh, A file system abstraction for sense and respond systems, Proceedings of the 2005 workshop on End-to-end, sense-and-respond systems, applications and services, June 05-05, 2005, Seattle, Washington
• 31: Toshiba America Electronic Components, Inc. (TAEC). Datasheet: TC58DVG02A1FT00. http://www.toshiba.com/taec, Jan. 2003.
• 32: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. In Technical Report CS--200006, Duke University, Apr. 2000.
• 33: Padmini Vellore , Paul Gillard , Ramachandran Venkatesan, Delivery analysis of multicasting in BitTorrent enabled ad hoc network (MBEAN) routing, Proceedings of the 2006 international conference on Wireless communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada [doi>10.1145/1143549.1143776]
• 34: Y. Wang, S. Jain, M. Martonosi, and K. Fall. Erasure--Based Routing for Opportunistic Networks. In Proc. of the Special Interest Group on Data Communications Conf. (SIGCOMM), Aug. 2005.
• 35: D. Woodhouse. Journalling Flash File System. http://sources.redhat.com/jffs2/jffs2.pdf.
• 36: C.-H. Wu, L.-P. Chang, and T.-W. Kuo. An Efficient B-Tree Layer for Flash-Memory Storage Systems. In Intl. Conf. on Real-Time and Embedded Computing Systems and Applications, 2003.
• 37: Chin-Hsien Wu , Li-Pin Chang , Tei-Wei Kuo, An efficient R-tree implementation over flash-memory storage systems, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.17-24, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956679]
• 38: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]
• 39: Pei Zhang , Christopher M. Sadler , Stephen A. Lyon , Margaret Martonosi, Hardware design experiences in ZebraNet, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031522]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization

  E. Data
  E.5 FILES
      Subjects: Sorting/searching

General Terms:
Algorithms, Management, Performance

Keywords:
data search and storage, energy efficient communications, mobile ad hoc sensor networks