NDLI: Distributed algorithms for barrier coverage using relocatable sensors

Please wait, while we are loading the content...

On deterministic abortable objects

Compact routing schemes with improved stretch

Fast byzantine agreement

How to meet asynchronously at polynomial cost

Brief announcement: self-stabilizing resource discovery algorithm

Stone age distributed computing

Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors

Upper bound on the complexity of solving hard renaming

Fair and resilient incentive tree mechanisms

Early-deciding consensus is expensive

Leaplist: lessons learned in designing tm-supported range queries

Randomized broadcast in radio networks with collision detection

The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks

Athena lecture: distributed computing theory for wireless networks and mobile systems

Pragmatic primitives for non-blocking data structures

Optimal deterministic routing and sorting on the congested clique

Byzantine vector consensus in complete graphs

On the complexity of universal leader election

Brief announcement: parameterized model checking of fault-tolerant distributed algorithms by abstraction

Feedback from nature: an optimal distributed algorithm for maximal independent set selection

Highly dynamic distributed computing with byzantine failures

Randomized loose renaming in o(log log n) time

What's a little collusion between friends?

On the complexity of asynchronous agreement against powerful adversaries

A programming language perspective on transactional memory consistency

Maximal independent sets in multichannel radio networks

Efficient distributed source detection with limited bandwidth

Programming models for extreme-scale computing

The SkipTrie: low-depth concurrent search without rebalancing

Brief announcement: fair maximal independent sets in trees

Fast byzantine agreement in dynamic networks

Brief announcement: a simple stretch 2 distance oracle

Brief announcement: on minimum interaction time for continuous distributed interactive computing

What can be decided locally without identifiers?

Brief announcement: constructing fault-tolerant overlay networks for topic-based publish/subscribe

Byzantine renaming in synchronous systems with t < N

A distributed algorithm for gathering many fat mobile robots in the plane

Introducing speculation in self-stabilization: an application to mutual exclusion

Brief announcement: an asymmetric flat-combining based queue algorithm

The cost of radio network broadcast for different models of unreliable links

Distributed algorithms for barrier coverage using relocatable sensors

Brief announcement: threshold load balancing in networks

Synchronous byzantine agreement with nearly a cubic number of communication bits: synchronous byzantine agreement with nearly a cubic number of communication bits

Brief announcement: pareto optimal solutions to consensus and set consensus

Brief announcement: deterministic self-stabilizing leader election with O(log log n)-bits

Brief announcement: byzantine agreement with a strong adversary in polynomial expected time

An O(1)-barriers optimal RMRs mutual exclusion algorithm: extended abstract

Stable and scalable universal swarms

Brief announcement: resettable objects and efficient memory reclamation for concurrent algorithms

Connectivity and aggregation in multihop wireless networks

Delegation of computation with verification outsourcing: curious verifiers

Brief announcement: scalable anonymous communication with byzantine adversary

Brief announcement: a shorter and stronger proof of an Ω(d log(n/d)) lower bound for broadcast in radio networks

Brief announcement: brokerage and closure in a strategic model of social capital

Brief announcement: a local approximation algorithm for MDS problem in anonymous planar networks

Brief announcement: techniques for programmatically troubleshooting distributed systems

Distributed algorithms for barrier coverage using relocatable sensors

Content Provider	ACM Digital Library
Author	Narayanan, Lata Shende, Sunil Kranakis, Evangelos Opatrny, Jaroslav Morales-Ponce, Oscar Eftekhari, Mohsen Krizanc, Danny
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 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 $Θ(n^{2})$ 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.
Starting Page	383
Ending Page	392
Page Count	10
File Format	PDF
ISBN	9781450320658
DOI	10.1145/2484239.2484258
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-07-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Wireless mobile sensors Barrier coverage Autonomous mobile robots Distributed algorithms Optimal algorithms
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in