Predicting link quality using supervised learning in wireless sensor networks

ABSTRACT

Routing protocols in sensor networks maintain information on neighbor states and potentially many other factors in order to make informed decisions. Challenges arise both in (a) performing accurate and adaptive information discovery and (b) processing/analyzing the gathered data to extract useful features and correlations. To address such challenges, this paper explores using supervised learning techniques to make informed decisions in the context of wireless sensor networks.

We investigate the design space of both offline learning and online learning and use link quality estimation as a case study to evaluate their effectiveness. For this purpose, we present MetricMap, a metric-based collection routing protocol atop MintRoute that derives link quality using classifiers learned in the training phase, when the traditional ETX approach fails. The offline learning approach is evaluated on a 30-node sensor network testbed, and our results show that MetricMap can achieve up to 300% improvement over MintRoute in data delivery rate for high data rate situations, with no negative impact on other performance metrics. We also explore the possibility of using online learning in this paper.

REFERENCES

• 1: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 2: Alec Woo , Terence Tong , David Culler, Taming the underlying challenges of reliable multihop routing in 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.958494]
• 3: Hongwei Zhang, Anish Arora, and Prasun Sinha. Learn on the fly: Data-driven link estimation and routing in sensor network backbones. In Proc. IEEE INFOCOM, 2006.
• 4: Jeongyeup Paek , K. Chintalapudi , R. Govindan , J. Caffrey , S. Masri, A wireless sensor network for structural health monitoring: performance and experience, Proceedings of the 2nd IEEE workshop on Embedded Networked Sensors, p.1-9, April 30-May 01, 2005
• 5: Lakshman Krishnamurthy , Robert Adler , Phil Buonadonna , Jasmeet Chhabra , Mick Flanigan , Nandakishore Kushalnagar , Lama Nachman , Mark Yarvis, Design and deployment of industrial sensor networks: experiences from a semiconductor plant and the north sea, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098926]
• 6: 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]
• 7: Tian He , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, AIDA: Adaptive application-independent data aggregation in wireless sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.426-457, May 2004 [doi>10.1145/993396.993406]
• 8: 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]
• 9: S. Sandeep Pradhan, Julius Kusuma, and Kannan Ramchandran. Distributed compression in a dense microsensor network. IEEE Signal Processing, March 2002.
• 10: Mistlab. http://mistlab.csail.mit.edu/.
• 11: IEEE Standard 802, part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low Rate Wireless Personal Area Networks (LR-WPANs). 2003.
• 12: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 13: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 14: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 15: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 16: Chieh-Yih Wan , Shane B. Eisenman , Andrew T. Campbell, CODA: congestion detection and avoidance in 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.958523]
• 17: Chieh-Yih Wan , Shane B. Eisenman , Andrew T. Campbell , Jon Crowcroft, Siphon: overload traffic management using multi-radio virtual sinks in sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098931]
• 18: William W. Cohen. Fast effective rule induction. In Proc. the International Conference on Machine Learning (ICML), 1995.
• 19: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 20: Raj Jain. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation and Modeling. John Wiley & Sons, Inc., 1991.
• 21: Geoffrey Werner-Allen , Patrick Swieskowski , Matt Welsh, MoteLab: a wireless sensor network testbed, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 22: Bret Hull , Kyle Jamieson , Hari Balakrishnan, Mitigating congestion in wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031512]
• 23: Omprakash Gnawali , Ki-Young Jang , Jeongyeup Paek , Marcos Vieira , Ramesh Govindan , Ben Greenstein , August Joki , Deborah Estrin , Eddie Kohler, The Tenet architecture for tiered sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182823]
• 24: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 25: VFML Toolkit, http://www.cs.washington.edu/dm/vfml/main.html.
• 26: Nithya Ramanathan , Kevin Chang , Rahul Kapur , Lewis Girod , Eddie Kohler , Deborah Estrin, Sympathy for the sensor network debugger, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098946]
• 27: Gilman Tolle and David Culler. Design of an application-cooperative management system for wireless sensor networks. In Proc. EWSN, 2005.
• 28: Brad Calder , Dirk Grunwald , Michael Jones , Donald Lindsay , James Martin , Michael Mozer , Benjamin Zorn, Evidence-based static branch prediction using machine learning, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.1, p.188-222, Jan. 1997 [doi>10.1145/239912.239923]
• 29: Ira Cohen , Moises Goldszmidt , Terence Kelly , Julie Symons , Jeffrey S. Chase, Correlating instrumentation data to system states: a building block for automated diagnosis and control, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.16-16, December 06-08, 2004, San Francisco, CA
• 30: Alice X. Zheng , Jim Lloyd , Eric Brewer, Failure Diagnosis Using Decision Trees, Proceedings of the First International Conference on Autonomic Computing, p.36-43, May 17-18, 2004
• 31: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 32: Justin A. Boyan and Michael L. Littman. Packet routing in dynamically changing networks: A reinforcement learning approach. In Advances in Neural Information Processing Systems, volume 6. Morgan Kaufmann Publishers, 1994.
• 33: Venkata N. Padmanabhan , Lili Qiu , Helen J. Wang, Passive network tomography using Bayesian inference, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637214]
• 34: Carlos Guestrin , Peter Bodik , Romain Thibaux , Mark Paskin , Samuel Madden, Distributed regression: an efficient framework for modeling sensor network data, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984624]
• 35: Andreas Krause , Carlos Guestrin , Anupam Gupta , Jon Kleinberg, Near-optimal sensor placements: maximizing information while minimizing communication cost, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127782]
• 36: Joseph Polastre , Jonathan Hui , Philip Levis , Jerry Zhao , David Culler , Scott Shenker , Ion Stoica, A unifying link abstraction for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098928]
• 37: Can Emre Koksal and Hari Balakrishnan. Quality-aware routing metrics for time-varying wireless mesh networks. IEEE Journal on Selected Areas of Communication Special Issue on Multi-hop Wireless Mesh Networks, 24(11), November 2006.
• 38: Alberto Cerpa , Jennifer L. Wong , Louane Kuang , Miodrag Potkonjak , Deborah Estrin, Statistical model of lossy links in wireless sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 39: Alberto Cerpa , Jennifer L. Wong , Miodrag Potkonjak , Deborah Estrin, Temporal properties of low power wireless links: modeling and implications on multi-hop routing, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062741]
• 40: Hung X. Nguyen and Patrick Thiran. Using end-to-end data to infer lossy links in sensor networks. In Proc. IEEE INFOCOM, 2006.
• 41: Qing Cao, Tian He, Lei Fang, Tarek Abdelzaher, John Stankovic, and Sang Son. Efficiency centric communication model for wireless sensor networks. In Proc. IEEE INFOCOM, 2006.
• 42: Kannan Srinivasan, Prabal Dutta, Arsalan Tavakoli, and Philip Levis. Understanding the causes of packet delivery success and failure in dense wireless sensor networks. Technical Report SING-06-00, Stanford University, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design