A methodology for in-network evaluation of integrated logical-statistical models

ABSTRACT

Synthesizing high-level semantic knowledge from low-level sensor data is an important problem in many sensor network applications. Programming a network to perform such synthesis in situ is especially difficult due to the stringent resource constraints, unreliable wireless communication, and complex distributed algorithms and network protocols required to manipulate the data. Recently, a declarative programming language called Snlog [5] has been developed to address this problem. However, statistical reasoning for modeling noise in the context of sensor networks has not been addressed in Snlog. In this paper, we develop a methodology based on the PRISM [36] framework, which integrates logical and statistical reasoning, for specifying sensor network programs that deal with noisy data and tolerate faults in the network. The relationship between high-level (synthesized) and low-level (observed) data is captured by logical rules, while statistical models are used to specify computations in the presence of noise and faults. We illustrate our methodology with three examples: (i) estimating temperature at various points in a region, (ii) evaluating the trajectory of an object observed by a sensor network, based on the Hidden Markov Model, and (iii) evaluating most reliable communication paths between sensor nodes. We analyze the results of simulations as well as an experimental deployment to evaluate the practical feasibility of our approach.

REFERENCES

• 1: Fahiem Bacchus , Adam J. Grove , Joseph Y. Halpern , Daphne Koller, From statistical knowledge bases to degrees of belief, Artificial Intelligence, v.87 n.1-2, p.75-143, Nov. 1996 [doi>10.1016/S0004-3702(96)00003-3]
• 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: David Chu , Amol Deshpande , Joseph M. Hellerstein , Wei Hong, Approximate Data Collection in Sensor Networks using Probabilistic Models, Proceedings of the 22nd International Conference on Data Engineering, p.48, April 03-07, 2006 [doi>10.1109/ICDE.2006.21]
• 4: David Chu , Arsalan Tavakoli , Lucian Popa , Joseph Hellerstein, Entirely declarative sensor network systems, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 5: David Chu , Lucian Popa , Arsalan Tavakoli , Joseph M. Hellerstein , Philip Levis , Scott Shenker , Ion Stoica, The design and implementation of a declarative sensor network system, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322281]
• 6: David Chu , Arsalan Tavakoli , Lucian Popa , Joseph Hellerstein, Entirely declarative sensor network systems, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: D. Culler et al. TinyOS. http://www.tinyos.net, 2004.
• 8: J. Cussens. Loglinear models for first-order probabilistic reasoning. In Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 126--133, 1999.
• 9: James Cussens, Parameter Estimation in Stochastic Logic Programs, Machine Learning, v.44 n.3, p.245-271, September 2001 [doi>10.1023/A:1010924021315]
• 10: C. M. D. Heckerman and D. Koller. Probabilistic entity-relationship models, PRMs, and plate models. In ICML-2004 Workshop on Statistical Relational Learning and its Connections to Other Fields, pages 55--60, 2004.
• 11: A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Royal Statistical Society, 39(1):1--38, 1977.
• 12: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 13: 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
• 14: Lisa Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning probabilistic models of link structure, The Journal of Machine Learning Research, 3, 3/1/2003
• 15: Ramakrishna Gummadi , Nupur Kothari , Ramesh Govindan , Todd Millstein, Kairos: a macro-programming system for wireless sensor networks, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom [doi>10.1145/1095810.1118600]
• 16: Joseph Y. Halpern, An analysis of first-order logics of probability, Artificial Intelligence, v.46 n.3, p.311-350, Dec. 1990 [doi>10.1016/0004-3702(90)90019-V]
• 17: Yoshitaka Kameya , Taisuke Sato, Efficient EM Learning with Tabulation for Parameterized Logic Programs, Proceedings of the First International Conference on Computational Logic, p.269-284, July 01, 2000
• 18: Yoshitaka Kameya , Nobuhisa Ueda , Taisuke Sato, A Graphical Method for Parameter Learning of Symbolic-Statistical Models, Proceedings of the Second International Conference on Discovery Science, p.264-276, December 01, 1999
• 19: D. Koller and A. Pfeffer. Learning probabilities for noisy first-order rules. In 15th International Joint Conference on Artificial Intelligence, pages 1316--1321, 1997.
• 20: Laks V. S. Lakshmanan , Fereidoon Sadri, Probabilistic deductive databases, Proceedings of the 1994 International Symposium on Logic programming, p.254-268, November 1994, Symposia, Melbourne
• 21: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 22: Boon Thau Loo , Tyson Condie , Joseph M. Hellerstein , Petros Maniatis , Timothy Roscoe , Ion Stoica, Implementing declarative overlays, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
• 23: Boon Thau Loo , Joseph M. Hellerstein , Ion Stoica , Raghu Ramakrishnan, Declarative routing: extensible routing with declarative queries, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005
• 24: S. R. Madden, J. M. Hellerstein, and W. Hong. TinyDB: In-network query processing in TinyOS. http://telegraph.cs.berkeley.edu/tinydb, 2003.
• 25: B. Milch, B. Marthi, S. J. Russell, D. Sontag, D. L. Ong, and A. Kolobov. BLOG: probabilistic models with unknown objects. In IJCAI, pages 1352--1359, 2005.
• 26: S. Muggleton. Stochastic logic programs. In L. De Raedt, editor, Advances in inductive logic programming, pages 254--264, 1996.
• 27: Ryan Newton , Matt Welsh, Region streams: functional macroprogramming for sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052213]
• 28: Raymond Ng , V. S. Subrahmanian, Probabilistic logic programming, Information and Computation, v.101 n.2, p.150-201, Dec. 1992 [doi>10.1016/0890-5401(92)90061-J]
• 29: Nils J. Nilsson, Probabilistic logic, Artificial Intelligence, v.28 n.1, p.71-88, Feb. 1986 [doi>10.1016/0004-3702(86)90031-7]
• 30: Mark Paskin , Carlos Guestrin , Jim McFadden, A robust architecture for distributed inference in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 31: A. Pfeffer. IBAL: A probabilistic rational programming language. In IJCAI, pages 733--740, 2001.
• 32: 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
• 33: David Poole, Probabilistic Horn abduction and Bayesian networks, Artificial Intelligence, v.64 n.1, p.81-129, Nov. 1993 [doi>10.1016/0004-3702(93)90061-F]
• 34: Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 35: Matthew Richardson , Pedro Domingos, Markov logic networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [doi>10.1007/s10994-006-5833-1]
• 36: T. Sato and Y. Kameya. Prism: A symbolic-statistical modeling language. In Fifteenth International Joint Conference on Artificial Intelligence, pages 1330--1335, 1997.
• 37: Jeremy Schiff , Dominic Antonelli , Alexandros G. Dimakis , David Chu , Martin J. Wainwright, Robust message-passing for statistical inference in sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236375]
• 38: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 39: Adam Silberstein , Gavino Puggioni , Alan Gelfand , Kamesh Munagala , Jun Yang, Suppression and failures in sensor networks: a Bayesian approach, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 40: Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies, W. H. Freeman & Co., New York, NY, 1990
• 41: Matt Welsh , Geoff Mainland, Programming sensor networks using abstract regions, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.3-3, March 29-31, 2004, San Francisco, California
• 42: Kamin Whitehouse , Cory Sharp , Eric Brewer , David Culler, Hood: a neighborhood abstraction for sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990079]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming
  D.2 SOFTWARE ENGINEERING
        D.2.10 Design**

General Terms:
Design, Experimentation, Languages

Keywords:
in-network analysis, logical-statistical models, sensor networks