Passive diagnosis for wireless sensor networks

ABSTRACT

Network diagnosis, an essential research topic for traditional networking systems, has not received much attention for wireless sensor networks. Existing sensor debugging tools like sympathy or EmStar rely heavily on an add-in protocol that generates and reports a large amount of status information from individual sen-sor nodes, introducing network overhead to a resource constrained and usually traffic sensitive sensor network. We report in this study our initial attempt at providing a light-weight network diag-nosis mechanism for sensor networks. We propose PAD, a prob-abilistic diagnosis approach for inferring the root causes of ab-normal phenomena. PAD employs a packet marking algorithm for efficiently constructing and dynamically maintaining the inference model. Our approach does not incur additional traffic overhead for collecting desired information. Instead, we introduce a prob-abilistic inference model which encodes internal dependencies among different network elements, for online diagnosis of an operational sensor network system. Such a model is capable of additively reasoning root causes based on passively observed symptoms. We implement the PAD design in our sea monitoring sensor network test-bed and validate its effectiveness. We further evaluate the efficiency and scalability of this design through ex-tensive trace-driven simulations.

REFERENCES

• 1: "IBM Tivoli," http://www.ibm.com/software/tivoli/
• 2: "HP Openview," http://www.openview.hp.com/
• 3: "Microsoft Operations Manager," http://www.microsoft.com/mom/
• 4: "OceanSense: Sensor Network for Sea Monitoring," http://www.cse.ust.hk/~liu/Ocean/index.html
• 5: Paramvir Bahl , Ranveer Chandra , Albert Greenberg , Srikanth Kandula , David A. Maltz , Ming Zhang, Towards highly reliable enterprise network services via inference of multi-level dependencies, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 6: Xiaole Bai , Dong Xuan , Ziqiu Yun , Ten H. Lai , Weijia Jia, Complete optimal deployment patterns for full-coverage and k-connectivity (k≤6) wireless sensor networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374672]
• 7: Jiannong Cao , Liang Zhang , Jin Yang , Sajal K. Das, A Reliable Mobile Agent Communication Protocol, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.468-475, March 24-26, 2004
• 8: G. Cooper, "Probabilistic Inference using Belief Networks is NP-Hard," Stanford Knowledge Systems Laboratory, Technical Report 1987.
• 9: Paul Dagum , Michael Luby, Approximating probabilistic inference in Bayesian belief networks is NP-hard, Artificial Intelligence, v.60 n.1, p.141-153, March 1993 [doi>10.1016/0004-3702(93)90036-B]
• 10: Q. Fang, J. Gao, and L. Guibas, "Locating and Bypassing Routing Holes in Sensor Networks," In Proc. of IEEE INFOCOM, 2004.
• 11: Raghu K. Ganti , Praveen Jayachandran , Haiyun Luo , Tarek F. Abdelzaher, Datalink streaming in wireless 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.1182829]
• 12: Bu˘gra Gedik , Ling Liu , Philip S. Yu, ASAP: An Adaptive Sampling Approach to Data Collection in Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.18 n.12, p.1766-1783, December 2007 [doi>10.1109/TPDS.2007.1110]
• 13: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using wireless 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.990096]
• 14: Srikanth Kandula , Dina Katabi , Jean-Philippe Vasseur, Shrink: a tool for failure diagnosis in IP networks, Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080173.1080178]
• 15: Kevin Klues , Gregory Hackmann , Octav Chipara , Chenyang Lu, A component-based architecture for power-efficient media access control in wireless sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322270]
• 16: Ramana Rao Kompella , Jennifer Yates , Albert Greenberg , Alex C. Snoeren, IP fault localization via risk modeling, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.57-70, May 02-04, 2005
• 17: Sunho Lim , Chansu Yu , Chita R. Das, Rcast: A Randomized Communication Scheme for Improving Energy Efficiency in MANETs, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.123-132, June 06-10, 2005 [doi>10.1109/ICDCS.2005.64]
• 18: H. Liu, P. Wan, C. Yi, X. Jia, S. Makki, and N. Pissinou, "Maximal Lifetime Scheduling in Sensor Surveillance Networks," In Proc. of IEEE INFOCOM, 2005.
• 19: Yunhuai Liu , Qian Zhang , Lionel Ni, Opportunity-Based Topology Control in Wireless Sensor Networks, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.421-428, June 17-20, 2008 [doi>10.1109/ICDCS.2008.91]
• 20: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 21: 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]
• 22: M. Steinder and A. Sethi, "Increasing Robustness of Fault Localization Through Analysis of Lost, Spurious, and Positive Symptoms," In Proc. of IEEE INFOCOM, 2002.
• 23: Małgorzata Steinder , Adarshpal S. Sethi, Probabilistic fault localization in communication systems using belief networks, IEEE/ACM Transactions on Networking (TON), v.12 n.5, p.809-822, October 2004 [doi>10.1109/TNET.2004.836121]
• 24: Maneesh Varshney , Defeng Xu , Mani Srivastava , Rajive Bagrodia, SenQ: a scalable simulation and emulation environment for 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.1236387]
• 25: J. Wu and S. Yang, "SMART: A Scan-Based Movement-Assisted Sensor Deployment Method in Wireless Sensor Networks," In Proc. of IEEE INFOCOM, 2005.
• 26: Ning Xu , Sumit Rangwala , Krishna Kant Chintalapudi , Deepak Ganesan , Alan Broad , Ramesh Govindan , Deborah Estrin, A wireless sensor network For structural monitoring, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031498]
• 27: Jing Yang , Mary Lou Soffa , Leo Selavo , Kamin Whitehouse, Clairvoyant: a comprehensive source-level debugger for wireless sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322282]
• 28: Zheng Yang , Mo Li , Yunhao Liu, Sea Depth Measurement with Restricted Floating Sensors, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.469-478, December 03-06, 2007 [doi>10.1109/RTSS.2007.45]
• 29: Hongqiang Zhai , Yuguang Fang, Impact of Routing Metrics on Path Capacity in Multirate and Multihop Wireless Ad Hoc Networks, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.86-95, November 12-15, 2006 [doi>10.1109/ICNP.2006.320201]
• 30: Q. Zhang, "Probabilistic Reasoning Based on Dynamic Causality Trees/Diagrams," Reliability Engineering and System Safety, vol. 46, pp. 202--220, 1994.
• 31: J. Zhao, R. Govindan, and D. Estrin, "Residual Energy Scan for Monitoring Sensor Networks," In Proc. of IEEE WCNC, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Experimentation, Management, Measurement

Keywords:
diagnosis, wireless sensor networks