A self-stabilizing algorithm for edge monitoring problem

B Neggazi, M Haddad, V Turau… - Stabilization, Safety, and …, 2014 - Springer
B Neggazi, M Haddad, V Turau, H Kheddouci
Stabilization, Safety, and Security of Distributed Systems: 16th International …, 2014Springer
Self-monitoring is a simple and effective mechanism for the security of wireless sensor
networks (WSNs), especially to cope against compromised nodes. A node v can monitor an
edge e if both end-nodes of e are neighbors of v; ie, e together with v forms a triangle in the
graph. Moreover, some edges need more than one monitor. Finding a set of monitoring
nodes satisfying all monitoring constraints is called the edge-monitoring problem. The
minimum edge-monitoring problem is long known to be NP-complete. In this paper, we …
Abstract
Self-monitoring is a simple and effective mechanism for the security of wireless sensor networks (WSNs), especially to cope against compromised nodes. A node v can monitor an edge e if both end-nodes of e are neighbors of v; i.e., e together with v forms a triangle in the graph. Moreover, some edges need more than one monitor. Finding a set of monitoring nodes satisfying all monitoring constraints is called the edge-monitoring problem. The minimum edge-monitoring problem is long known to be NP-complete. In this paper, we present a novel silent self-stabilizing algorithm for computing a minimal edge-monitoring set. Correctness and termination are proven for the unfair distributed daemon.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果