Protecting Neighbor Discovery Against Node Compromises in Sensor Networks

The neighborhood information has been frequently used by protocols such as routing in sensor networks. Many methods have been proposed to protect such information in hostile environments. However, these methods can only protect neighbor relations between benign nodes. A compromised node can easily circumvent them and setup false neighbor relations with sensor nodes in many places, impacting the network at a large scale. This paper presents a theoretic model for neighbor discovery in sensor networks and describes a fundamental security limitation and a generic attack against this model. The paper then proposes an efficient and localized solution based on a security property achievable during sensor deployment. This technique provides a threshold security guarantee in dealing with compromised sensor nodes. The analytical and simulation studies show that the technique is practical and effective for sensor networks.