### Skapa referens, olika format (klipp och klistra)

**Harvard**

Eftekhari, M., Kranakis, E., Kriz̧anc, D., Morales-Ponce, O., Narayanan, L. och Opatrný, J. (2013) *Distributed algorithms for barrier coverage using relocatable sensors*.

** BibTeX **

@conference{

Eftekhari2013,

author={Eftekhari, Mohsen and Kranakis, Evangelos and Kriz̧anc, Danny and Morales-Ponce, Oscar and Narayanan, Lata and Opatrný, Jaroslav},

title={Distributed algorithms for barrier coverage using relocatable sensors},

booktitle={Proceedings of the Annual ACM Symposium on Principles of Distributed Computing},

isbn={9781450320658},

pages={383-392},

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 the problem in the distributed setting. We assume 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 rang e 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 θ(n2) steps with the barrier fully covered, while the constant-memory algorithm is shown to take θ(n) steps to terminate in the worst case. Since any algorithm that can only move a constant distance in one step requires ω(n) steps on some inputs, our second algorithm is asymptotically optimal. Finally, both our algorithms are self-stabilizing, and can be easily extended to the case of non-homogeneous sensors, and for the case when the barrier is a circle. Copyright 2013 ACM.},

year={2013},

keywords={Autonomous mobile robots, Barrier coverage, Distributed algorithms, Optimal algorithms, Wireless mobile sensors},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 190050

A1 Eftekhari, Mohsen

A1 Kranakis, Evangelos

A1 Kriz̧anc, Danny

A1 Morales-Ponce, Oscar

A1 Narayanan, Lata

A1 Opatrný, Jaroslav

T1 Distributed algorithms for barrier coverage using relocatable sensors

YR 2013

T2 Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SN 9781450320658

SP 383

OP 392

AB 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 the problem in the distributed setting. We assume 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 rang e 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 θ(n2) steps with the barrier fully covered, while the constant-memory algorithm is shown to take θ(n) steps to terminate in the worst case. Since any algorithm that can only move a constant distance in one step requires ω(n) steps on some inputs, our second algorithm is asymptotically optimal. Finally, both our algorithms are self-stabilizing, and can be easily extended to the case of non-homogeneous sensors, and for the case when the barrier is a circle. Copyright 2013 ACM.

LA eng

DO 10.1145/2484239.2484258

LK http://dx.doi.org/10.1145/2484239.2484258

OL 30