A framework for extending the synergy between MAC layer and query optimization in sensor networks

ABSTRACT

Queries in sensor networks are expected to produce results in a timely manner and for long periods, as needed. This implies that sensor queries need to be optimized with respect to both response time and energy consumption. With these requirements in mind, we develop novel cross-layer optimization techniques that utilize information about how the medium access control (MAC) layer operates while processing queries in large scale sensor network environments. The central framework of our approach is a Data Transmission Algebra that uniformly captures the structure of data transmissions along with their constraints and requirements. Our framework enables both qualitative analysis and quantitative cost-based optimization of sensor queries. We illustrate the effectiveness of our framework by developing a collision-aware scheduler and evaluating it experimentally.

REFERENCES

• 1: Atheros Communications. Whitepaper: 802.11 Wireless LAN Performance. (available at http://atheros.com/), April 2003.
• 2: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 3: J. Beaver, M. A. Sharaf, A. Labrinidis, and P. K. Chrysanthis. Location-Aware Routing for Data Aggregation for Sensor Networks. Proc. of Geo Sensor Networks Workshop, 2003.
• 4: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 5: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 6: Ugur Cetintemel , Andrew Flinders , Ye Sun, Power-efficient data dissemination in wireless sensor networks, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940923.940925]
• 7: P. K. Chrysanthis and V. Zadorozhny. From Location Databases to Pervasive Catalog. Proc. of MDDS Workshop, 2002.
• 8: A. Demers, J. Gehrke, R. Rajaraman, N. Trigoni and Y. Yao. Energy-Efficient Data Management for Sensor Networks: A Work-In-Progress Report. Proc. of 2nd IEEE Upstate New York Workshop on Sensor Networks, 2003.
• 9: Firetide Inc. Specifications of the HotPoint 1000S Wireless Mesh Router, Datasheet. (available at: http://www.firetide.com/images/User_FilesImages/documents/HP 1000S_DS_al04.pdf).
• 10: Samir Goel , Tomasz Imielinski, Prediction-based monitoring in sensor networks: taking lessons from MPEG, ACM SIGCOMM Computer Communication Review, v.31 n.5, October 2001 [doi>10.1145/1037107.1037117]
• 11: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 12: John Heidemann , Fabio Silva , Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , Deepak Ganesan, Building efficient wireless sensor networks with low-level naming, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 13: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• 14: Christine E. Jones , Krishna M. Sivalingam , Prathima Agrawal , Jyh Cheng Chen, A Survey of Energy Efficient Network Protocols for Wireless Networks, Wireless Networks, v.7 n.4, p.343-358, 08/01/2001 [doi>10.1023/A:1016627727877]
• 15: 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]
• 16: 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]
• 17: www.opnet.com.
• 18: Kaveh Pahlavan , Allen H. Levesque, Wireless information networks, Wiley-Interscience, New York, NY, 1995
• 19: Kaveh Pahlavan , Prashant Krishnamurthy, Principles of Wireless Networks: A Unified Approach, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 20: J. Proakis. Digital Communications. McGraw Hill, 2001.
• 21: Mohamed A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , Panos K. Chrysanthis, TiNA: a scheme for temporal coherency-aware in-network aggregation, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940923.940937]
• 22: C. Schurgers, V. Tsiatsis and M. Srivastava. STEM: Topology Management for Energy Efficient Sensor Network. Prov. of IEEE Aerospace Conf., 2002.
• 23: 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]
• 24: W. Ye, J. Heidemann and D. Estrin. An Energy-Efficient MAC Protocol for Wireless Sensor Networks. Proc. of IEEE INFOCOM, 2002.
• 25: M. Younis , M. Youssef , K. Arisha, Energy-Aware Routing in Cluster-Based Sensor Networks, Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS'02), p.129, October 11-16, 2002
• 26: V. Zadorozhny and P. K. Chrysanthis. Location-Based Computing. In Telegeoinformatics: Location-Based Computing and Services, Taylor and Francis Books, 2003.
• 27: Rong Zheng , Jennifer C. Hou , Lui Sha, Asynchronous wakeup for ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778420]
• 28: R. Zheng and R. Kravets. On-demand Power Management for Ad-Hoc Networks. Proc. of IEEE INFOCOM Conf., 2003.
• 29: IEEE Std 802.15.4. Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs). IEEE Computer Society, October 2003.