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

Publikationstyp
Journal Article
Date Issued
2016-09-20
Sprache
English
Author(s)
Neggazi, Brahim  
Haddad, Mohammed  
Turau, Volker  
Kheddouci, Hamamache  
Institut
Telematik E-17  
TORE-URI
http://hdl.handle.net/11420/3609
Journal
Information and computation  
Volume
254
Start Page
367
End Page
376
Citation
Information and Computation (254): 367-376 (2017-06-01)
Publisher DOI
10.1016/j.ic.2016.09.003
Scopus ID
2-s2.0-84994476351
Publisher
Elsevier
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.
Subjects
Self-monitoring
Self-stabilization
Wireless sensor networks
DDC Class
380: Handel, Kommunikation, Verkehr
600: Technik
Funding(s)
Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken  
More Funding Information
This work is supported by PHC PROCOPE 2015 Program, project id: 33394TD. Research of the third author was partially funded by the Deutsche Forschungsgemeinschaft (DFG), contract number TU 221/6-1.