Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.10.2016 | Ausgabe 5/2016

Distributed Computing 5/2016

Distributed algorithms for barrier coverage using relocatable sensors

Zeitschrift:
Distributed Computing > Ausgabe 5/2016
Autoren:
Mohsen Eftekhari, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce, Lata Narayanan, Jaroslav Opatrny, Sunil Shende
Wichtige Hinweise
An abbreviated version of this paper is published in the proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2013), July 22–24, Montreal, Canada.

Abstract

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study a barrier coverage problem in the distributed and discrete setting. We assume that we have n identical sensors located at grid positions on the barrier, and that each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within \(\varTheta (n^2)\) steps with the barrier fully covered, while the constant-memory algorithm is shown to take \(\varTheta (n)\) steps to terminate in the worst case. Since any algorithm in which a sensor can only move a constant distance in one step requires \(\varOmega (n)\) steps on some inputs, our second algorithm is asymptotically optimal.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe​​​​​​​​​​​​​​

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 5/2016

Distributed Computing 5/2016 Zur Ausgabe

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise