Self-monitoring for sensor networks

ABSTRACT

Local monitoring is an effective mechanism for the security of wireless sensor networks (WSNs). Existing schemes assume the existence of sufficient number of active nodes to carry out monitoring operations. Such an assumption, however, is often difficult for a large scale sensor network. In this work, we focus on designing an efficient scheme integrated with good self-monitoring capability as well as providing an infrastructure for various security protocols using local monitoring. To the best of our knowledge, we are the first to present the formal study on finding optimized self-monitoring topology for WSNs. We show the problem is NP-complete even under the unit disk graph (UDG) model, and give the upper bound on the approximation ratio. We further propose two distributed polynomial algorithms with provable approximation ratio to address this issue. Through comprehensive simulations, we evaluate the effectiveness of this design.

REFERENCES

• 1: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 2: C. Karlof and D. Wagner, "Secure routing in wireless sensor networks: attacks and countermeasures," Elsevier AdHoc Networks, vol. 1, 2003.
• 3: H. Chan and A. Perrig, "Security and privacy in sensor networks," in IEEE Computer, vol. 36, 2003, pp. 103--105.
• 4: Issa Khalil , Saurabh Bagchi , Cristina Nina-Rotaru, DICAS: Detection, Diagnosis and Isolation of Control Attacks in Sensor Networks, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.89-100, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.17]
• 5: Issa Khalil, LITEWORP: A Lightweight Countermeasure for the Wormhole Attack in Multihop Wireless Networks, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.612-621, June 28-July 01, 2005 [doi>10.1109/DSN.2005.58]
• 6: Saurabh Ganeriwal , Mani B. Srivastava, Reputation-based framework for high integrity sensor networks, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029115]
• 7: Suk-Bok Lee , Yoon-Hwa Choi, A resilient packet-forwarding scheme against maliciously packet-dropping nodes in sensor networks, Proceedings of the fourth ACM workshop on Security of ad hoc and sensor networks, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1180345.1180353]
• 8: Ana Paula R. da Silva , Marcelo H. T. Martins , Bruno P. S. Rocha , Antonio A. F. Loureiro , Linnyer B. Ruiz , Hao Chi Wong, Decentralized intrusion detection in wireless sensor networks, Proceedings of the 1st ACM international workshop on Quality of service & security in wireless and mobile networks, October 13-13, 2005, Montreal, Quebec, Canada [doi>10.1145/1089761.1089765]
• 9: K. Ioannis, T. Dimitriou, and F. C. Freiling, "Towards intrusion detection in wireless sensor networks," In Proc. of the 13th European Wireless Conference, 2007.
• 10: Sergio Marti , T. J. Giuli , Kevin Lai , Mary Baker, Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.255-265, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345955]
• 11: Sonja Buchegger , Jean-Yves Le Boudec, Performance analysis of the CONFIDANT protocol, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513828]
• 12: Yi-an Huang , Wenke Lee, A cooperative intrusion detection system for ad hoc networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986877]
• 13: Pietro Michiardi , Refik Molva, Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks, Proceedings of the IFIP TC6/TC11 Sixth Joint Working Conference on Communications and Multimedia Security: Advanced Communications and Multimedia Security, p.107-121, September 26-27, 2002
• 14: 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
• 15: 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]
• 16: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 17: Issa Khalil , Saurabh Bagchi , Ness B. Shroff, SLAM: Sleep-Wake Aware Local Monitoring in Sensor Networks, Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, p.565-574, June 25-28, 2007 [doi>10.1109/DSN.2007.88]
• 18: C. Hsin and M. Liu, "Self-monitoring of wireless sensor networks," Elsevier Computer Communications, vol. 29, pp. 462--476, 2006.
• 19: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 20: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 21: M. R. Garey and D. S. Johnson, "The rectilinear Steiner tree problem is NP-complete," SIAM Journal on Applied Mathematics, vol. 32, pp. 826--834, 1977.
• 22: R. Tamassia and I. G. Tollis, "Planar grid embedding in linear time," IEEE Transactions on Circuits and Systems, vol. 36, pp. 1230--1234, 1989.
• 23: L. G. Valiant, "Universality considerations in VLSI circuits," IEEE Transaction on Computers, vol. C-30, pp. 135--140, 1981.
• 24: S. Schmid and R. Wattenhofer, "Algorithmic models for sensor networks," In Proc. of the 14th International Workshop on Parallel and Distributed Real-Time Systems, 2006.
• 25: A. Schrijver, Combinatorial optimization - polyhedra and efficiency (Part III): Spring, 2003.
• 26: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 27: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 28: P.-J. Wan, K. M. Alzoubi, and O. Frieder, "Distributed construction of connected dominating set in wireless ad Hoc networks," In Proc. of IEEE INFOCOM, 2002.
• 29: B. Liang and Z. J. Haas, "Virtual backbone generation and maintenance in ad hoc network mobility management," In Proc. of IEEE INFOCOM, 2000.
• 30: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Algorithms, Security, Theory

Keywords:
np-complete, security, self-monitoring, wireless sensor network