# A New Lightweight Watchdog-Based Algorithm for Detecting Sybil Nodes in Mobile WSNs
## 2 Related Works
In random key pre-distribution \"a random set of keys or key-related information is assign to each sensor node, so that in the key set-up phase, each node can discover or compute the common keys it shares with its neighbors; the common keys will be used as a shared secret session key to ensure node-to-node secrecy\". So the technique involves associating the node identity with the keys assigned to the node, and thereafter Key validation of an claimed identity. As [6] claims himself, \"the problem with this approach is that if an attacker compromises multiple nodes, he can use every combination of the compromised keys to generate new identities\". He presents the solution to beindirect node validation. however, it should be mentioned that indirect node validation imposes a large operational overhead on the network. Another problem with all authentication-based techniques, as is the case with this one, is the requirement of secure code pre-distribution channels which are not addressed clearly. Another authentication-based approach is a light-weight identity certificate method which uses one-way key chains and Merkle hash trees to defeat Sybil attacks [13]. This method requires a significant amount of memory for storing information. The authors claim to have overcome this issue by means of the low level Merkle hash tree cryptographic. The last authentication-based approaches to be reviewed, use puzzle solving techniques to detect Sybil attackers [12; 22]. Another way of authentication is using puzzle-based computational mechanisms [12; 22]. The main idea, herein, is that the attacker should not be able to solve a subject puzzle. There is an inherent communication overhead due to puzzle dissemination and receiving puzzle solutions back. As to the best of our knowledge, the puzzle solving techniques have not been reported in WSNs so far. Identity registration is an centralized approach which is introduced in [6]. All nodes are registered in a trusted central authority (such as a base station) and the list of legitimate IDs are distributed amongst all nodes. To prevent the Sybil attack, each ID should be checked against the list of legitimate IDs. An important concern is that list of legitimate nodes must be protected from being maliciously modified. If the attacker is able to add IDs to this list, he will be able to add Sybil nodes to the network. The last category of Sybil attack detection algorithms to be reviewed is the neighborhood-based methods. This category is of special interest to us since our proposed algorithm belongs to it. [PERSON] et al. [8] propose a neighborhood-based method for detecting Sybil nodes which uses the fact that a malicious node produces similar neighbors lists corresponding to its different Sybil IDs. Each node constructs a critical set of neighboring IDs using similarities of different neighbor lists that it receives. IDs which transmit neighbors lists containing the critical set are labeled as Sybil. In the case of mobile nodes, the neighbors lists will change so often that they result in high communicational overhead. In [23] a Sybil attack detection method is proposed for MANETs based on cooperative monitoring. The packet receiver or forwarder can provide a proof that the sender transmitted the packet at the claimed location and time using a signature field that is unique for a non-malicious node. The results of these observations are periodically communicated between nodes. From these observations path similarities for packets originating from Sybil IDs are extracted and acted upon. The proposed algorithm involves computationally intensive procedures for signature operations, communication overhead for communicating observations, and hardware cost associated with employing directional antennas. Therefore, it seems not to be suitable for WSNs. Another neighborhood-based method which can serve as a comparison basis for our proposed algorithm is stated in [24]. In [24] a Sybil attack detection method is proposed based on observed transmissions.