KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficient Algorithms for Distributed Detection of Holes and Boundaries in Wireless Networks

Schieferdecker, Dennis 1; Völker, Markus 1; Wagner, Dorothea 1
1 Karlsruher Institut für Technologie (KIT)


We propose two novel algorithms for distributed and location-free boundary recognition in wireless sensor networks. Both approaches enable a node to decide autonomously whether it is a boundary node, based solely on connectivity information of a small neighborhood. This makes our algorithms highly applicable for dynamic networks where nodes can move or become inoperative.

We compare our algorithms qualitatively and quantitatively with several previous approaches. In extensive simulations, we consider various models and scenarios. Although our algorithms use less information than most other approaches, they produce significantly better results. They are very robust against variations in node degree and do not rely on simplified assumptions of the communication model. Moreover, they are much easier to implement on real sensor nodes than most existing approaches.

DOI: 10.1007/978-3-642-20662-7_33
Zitationen: 3
Zitationen: 7
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2011
Sprache Englisch
Identifikator ISBN: 978-3-642-20662-7
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000097646
Erschienen in Experimental Algorithms. 10th International Symposium, SEA 2011 Kolimpari, Chania, Crete, Greece, May 5-7, 2011. Proceedings Ed.: P. Pardalos
Verlag Springer-Verlag
Seiten 388–399
Serie Lecture Notes in Computer Science ; 6630
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page