Efficient tracing of failed nodes in sensor networks

ABSTRACT

In sensor networks, nodes commonly rely on each other to route messages to a base station. Although this practice conserves power it can obscure the cause of a measurement outage in a portion of the network. For example, when a base station ceases to receive measurements from a region of nodes it can't immediately determine whether this is because of the destruction of all the nodes in that region (due to an enemy attack, for example) or merely the result of the failure of a few nodes bearing much of the routing load. Previous solutions to this problem typically consist of re-running the route-discovery protocol, a process that can be quite expensive in terms of the number of messages that must be exchanged. We demonstrate that the topology of the network can be efficiently conveyed to the base station allowing for the quick tracing of the identities of the failed nodes with moderate communication overhead. Our algorithms work in conjunction with the existing functions of the network, requiring the nodes to send no additional messages.

REFERENCES

• 1: Omer Berkman , Michal Parnas , Jiři Sgall, Efficient dynamic traitor tracing, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.586-595, January 09-11, 2000, San Francisco, California, United States
• 2: P. Buonadonna, J. Hill, and D. Culler. Active message communication for tiny networked sensors. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'01), April 2001.
• 3: A. Cerpa and D. Estrin. Ascent: Adaptive self-configuring sensor networks topologies. In Proceedings of the 21th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'02), New York, NY, June 2002.
• 4: D. Du and F. Hwang. Combinatorial Group Testing and its Applications. World Scientific Publishing, Singapore, 1993.
• 5: Amos Fiat and Tamir Tassa. Dynamic traitor tracing. Journal of Cryptology, 14(3):211--223, 2001.
• 6: Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In HICSS, 2000.
• 7: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 8: Yih-Chun Hu, Adrian Perrig, and David~B. Johnson. Wormhole detection in wireless ad hoc networks. Technical Report TR01-384, Rice University Department of Computer Science, June 2002.
• 9: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 10: H. Krawczyk, M. Bellare, and R. Canetti. RFC 2104: HMAC: Keyed-hashing for message authentication, February 1997. Status: INFORMATIONAL.
• 11: Q. Li, J. Aslam, and D. Rus. Hierarchical power-aware routing in sensor networks. In Proceedings of the DIMACS Workshop on Pervasive Networking, May 2001.
• 12: Arati Manjeshwar , Dharma P. Agrawal, TEEN: ARouting Protocol for Enhanced Efficiency in Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.189, April 23-27, 2001
• 13: 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]
• 14: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 15: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor netowrks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Wireless communication
      C.2.2 Network Protocols
          Subjects: Routing protocols

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Security, Theory

Keywords:
routing, security, tracing