On the faulty sensor identification algorithm of wireless sensor networks under the PMC diagnosis model

Diagnosis is an essential subject for the reliability of a network system. Under the PMC diagnosis model, Dahbura and Masson (1984) proposed a polynomial-time algorithm with time complexity O(N^2.5) to identify all the faulty nodes in an N-node network. In this paper we present a novel method to diagnose a wireless sensor network by applying the concept behind the local diagnosability, first introduced by Hsu and Tan (2007). The local diagnosability can be thought of as a local strategy toward the global system diagnosis. There is a strong relationship between the local diagnosability and the traditional diagnosability. The goal of local diagnosis is to identify the fault status of any single node correctly. Under the PMC diagnosis model, we give a sufficient condition to estimate the local diagnosability of any given sensor in a wireless sensor network. Furthermore, we use a helpful structure, called extending star, to determine the fault status of each sensor in the network. For a given sensor s whose degree is d in the network, the proposed algorithm takes time O(d) pointing out its fault status under the PMC model, provided that there is an extending star of order d rooted at s and that the time for a sensor to test another one is constant.