Search

Self-monitoring is a simple and effective mechanism for surveilling wireless sensor networks, especially to cope against faulty or compromised nodes. A node v can monitor the communication over a link e if both end-nodes of e are neighbors of v . 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. [ABSTRACT FROM AUTHOR]

In this paper, we study the complexity of the edge monitoring problem. A vertex v monitors an edge e if both endpoints together with v form a triangle in the graph. Given a graph G = (V , E) and a weight function on edges c where c (e) is the number of monitors that needs the edge e , the problem is to seek a minimum subset of monitors S such that every edge e in the graph is monitored by at least c (e) vertices in S. Therefore, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices. [ABSTRACT FROM AUTHOR]