A self-stabilizing algorithm for edge monitoring in wireless sensor networks

Self-monitoring is a simple and effective mechanism for surveilling wireless sensor networks, especially to cope against faulty or compromised nodes. A node nu can monitor the communication over a link e if both end-nodes of e are neighbors of nu. Finding a set of monitoring nodes satisfying all monitoring constraints is called the edge-monitoring problem. The minimum edge-monitoring problem is known to be NP-complete. In this paper, we present a novel self-stabilizing algorithm for computing a minimal edge-monitoring set under the unfair distributed scheduler. For sparse networks the time complexity of this new algorithm is much lower than the currently best known algorithm. (C) 2016 Elsevier Inc. All rights reserved.