Decentralized control of adaptive sampling in wireless sensor networks

ABSTRACT

The efficient allocation of the limited energy resources of a wireless sensor network in a way that maximizes the information value of the data collected is a significant research challenge. Within this context, this article concentrates on adaptive sampling as a means of focusing a sensor's energy consumption on obtaining the most important data. Specifically, we develop a principled information metric based upon Fisher information and Gaussian process regression that allows the information content of a sensor's observations to be expressed. We then use this metric to derive three novel decentralized control algorithms for information-based adaptive sampling which represent a trade-off in computational cost and optimality. These algorithms are evaluated in the context of a deployed sensor network in the domain of flood monitoring. The most computationally efficient of the three is shown to increase the value of information gathered by approximately 83%, 27%, and 8% per day compared to benchmarks that sample in a naïve nonadaptive manner, in a uniform nonadaptive manner, and using a state-of-the-art adaptive sampling heuristic (USAC) correspondingly. Moreover, our algorithm collects information whose total value is approximately 75% of the optimal solution (which requires an exponential, and thus impractical, amount of time to compute).

REFERENCES

• 1: Yaakov Bar-Shalom , Xiao-Rong Li, Estimation with Applications to Tracking and Navigation, John Wiley & Sons, Inc., New York, NY, 2001
• 2: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 3: Cardell-Oliver, R., Smettem, K., Kranz, M., and Mayer, K. 2005. A reactive soil moisture sensor network: Design and field evaluation. Int. J. Distrib. Sensor Netw. 1, 2 (Apr.--June), 149--162.
• 4: Chen, C. S., Kang, M. S., Hwang, J. C., and Huang, C. W. 2000. Application of binary integer programming for load transfer of distribution systems. In Proceedings of the International Conference on Power System Technology (PowerCon) . Vol. 1. 305--310.
• 5: Chevaleyre, Y., Dunne, P., Endriss, U., Lang, J., Lemaitre, M., Maudet, N., Padget, J., Phelps, S., Rodriguez-Aguilar, J., and Sousa, P. 2006. Issues in multiagent resource allocation. Informatica 30, 3--31.
• 6: Krishna Chintalapudi , Tat Fu , Jeongyeup Paek , Nupur Kothari , Sumit Rangwala , John Caffrey , Ramesh Govindan , Erik Johnson , Sami Masri, Monitoring Civil Structures with a Wireless Sensor Network, IEEE Internet Computing, v.10 n.2, p.26-34, March 2006 [doi>10.1109/MIC.2006.38]
• 7: Chu, M., Haussecker, H., and Zhao, F. 2002. Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks. Int. J. High Perf. Comput. Appl. 16, 3, 293--313.
• 8: Cressie, N. A. C. 1991. Statistics for Spatial Data. John Wiley & Sons.
• 9: Thanh Dang , Nirupama Bulusu , Wu-chi Feng , Sergey Frolov , Antonio Baptista, Adaptive sampling in the COlumbia RIvEr observation network, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322330]
• 10: De Roure, D. 2005. Floodnet: A new flood warning system. Ingenia 23, 49--51.
• 11: Emre Ertin, Gaussian Process Models for Censored Sensor Readings, Proceedings of the 2007 IEEE/SP 14th Workshop on Statistical Signal Processing, p.665-669, August 26-29, 2007 [doi>10.1109/SSP.2007.4301342]
• 12: Frieden, B. 2004. Science from Fisher Information: A Unification. Cambridge University Press.
• 13: Girard, A. 2004. Approximate methods for propagation of uncertainty with Gaussian process models. Ph.D. thesis, University of Glasgow, Scotland, UK.
• 14: Carlos Guestrin , Andreas Krause , Ajit Paul Singh, Near-optimal sensor placements in Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.265-272, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102385]
• 15: Tian He , Sudha Krishnamurthy , Liqian Luo , Ting Yan , Lin Gu , Radu Stoleru , Gang Zhou , Qing Cao , Pascal Vicaire , John A. Stankovic , Tarek F. Abdelzaher , Jonathan Hui , Bruce Krogh, VigilNet: An integrated sensor network system for energy-efficient surveillance, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.1-38, February 2006 [doi>10.1145/1138127.1138128]
• 16: Heeks, R. 1999. Centralised versus decentralised management of public information systems: A core-periphery solution. Tech. rep., Institute of Development Policy and Management, Paper 7, Manchester, UK.
• 17: Aman Kansal , Jason Hsu , Sadaf Zahedi , Mani B. Srivastava, Power management in energy harvesting sensor networks, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.32-es, September 2007 [doi>10.1145/1274858.1274870]
• 18: Naoto Kimura , Shahram Latifi, A Survey on Data Compression in Wireless Sensor Networks, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume II, p.8-13, April 04-06, 2005 [doi>10.1109/ITCC.2005.43]
• 19: Andreas Krause , Carlos Guestrin , Anupam Gupta , Jon Kleinberg, Near-optimal sensor placements: maximizing information while minimizing communication cost, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127782]
• 20: Kroc, S. and Delic, V. 2003. Personal wireless sensor network for mobile health care monitoring. In Proceedings of the 6th International Conference on Telecommunications in Modern Satellite, Cable and Broadcasting Services (TELSIKS). Vol. 2. 471--474.
• 21: Ákos Lédeczi , András Nádas , Péter Völgyesi , György Balogh , Branislav Kusy , János Sallai , Gábor Pap , Sebestyén Dóra , Károly Molnár , Miklós Maróti , Gyula Simon, Countersniper system for urban warfare, ACM Transactions on Sensor Networks (TOSN), v.1 n.2, p.153-177, November 2005 [doi>10.1145/1105688.1105689]
• 22: Lo, B. P. L. and Yang, G. Z. 2005. Key technical challenges and current implementations of body sensor networks. In Proceedings of the 2nd International Workshop on Wearable and Implantable Body Sensor Networks (BSN). 1--5.
• 23: Mackay, D. J. C. 1998. Introduction to Gaussian process. In Proceedings of Neural Networks and Machine Learning. 133--165.
• 24: Geoffrey Mainland , David C. Parkes , Matt Welsh, Decentralized, adaptive resource allocation for sensor networks, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.315-328, May 02-04, 2005
• 25: 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]
• 26: Makarenko, A. and Durrant-Whyte, H. 2004. Decentralized data fusion and controls in active sensor network. In Proceedings of the 7th International Conference on Information Fusion (FUSION). Stockholm, Sweden, 479--486.
• 27: M. A. Osborne , S. J. Roberts , A. Rogers , S. D. Ramchurn , N. R. Jennings, Towards Real-Time Information Processing of Sensor Network Data Using Computationally Efficient Multi-output Gaussian Processes, Proceedings of the 7th international conference on Information processing in sensor networks, p.109-120, April 22-24, 2008 [doi>10.1109/IPSN.2008.25]
• 28: Paritosh Padhy , Rajdeep K. Dash , Kirk Martinez , Nicholas R. Jennings, A utility-based sensing and communication model for a glacial sensor network, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160885]
• 29: Padhy, P., Martinez, K., Riddoch, A., Hart, J. K., and Ong, R. 2005. Glacial environment monitoring using sensor networks. In Proceedings of Real-World Wireless Sensor Networks (REALWSN). 10--14.
• 30: Rabinowitz, P. and Davis, P. J. 2006. Methods of Numerical Integration, 2nd Ed. Dover Publications.
• 31: Rahimi, M., Pon, R., Kaiser, W. J., Sukhatme, G. S., Estrin, D., and Srivastava, M. 2004. Adaptive sampling for environmental robotics. In Proceedings of the IEEE International Conference on Robotics and Automation. Vol. 4. 3537--3544.
• 32: Rasmussen, C. E. 2004. Gaussian processes in machine learning. AI 3176, 63--71.
• 33: Carl Edward Rasmussen , Christopher K. I. Williams, Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning), The MIT Press, 2005
• 34: Seeger, M. 2004. Gaussian processes for machine learning. Int. J. Neural Sys. 14, 2 69--106.
• 35: Geoffrey Werner-Allen , Konrad Lorincz , Matt Welsh , Omar Marcillo , Jeff Johnson , Mario Ruiz , Jonathan Lees, Deploying a Wireless Sensor Network on an Active Volcano, IEEE Internet Computing, v.10 n.2, p.18-25, March 2006 [doi>10.1109/MIC.2006.26]
• 36: Rebecca Willett , Aline Martin , Robert Nowak, Backcasting: adaptive sampling for sensor networks, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984641]
• 37: Yong, B. C., Kurokawa, T., Takefuji, Y., and Hwa, S. K. 1993. An o(1) approximate parallel algorithm for the n-task-n-person assignment problem. In Proceedings of the International Joint Conference on Neural Networks (IJCNN). Vol. 2. 1503--1506.
• 38: Feng Zhao , Leonidas Guibas, Wireless Sensor Networks: An Information Processing Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Value of information

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents; Multiagent systems

General Terms:
Algorithms, Management, Measurement

Keywords:
Adaptive sampling algorithm, Gaussian process regression, decentralized decision mechanism, information metric