Skip to main content
main-content

Über dieses Buch

This book constitutes thoroughly refereed and revised selected papers from the 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2014, held in Wroclaw, Poland, on September 12, 2014.

The 10 papers presented in this volume were carefully reviewed and selected from 20 submissions. They are organized in topical sections named: robot planning; algorithms and data structures on graphs; and wireless networks.

Inhaltsverzeichnis

Frontmatter

Robot Planning

Frontmatter

The Multi-source Beachcombers’ Problem

Abstract
The Beachcombers’ Problem (c.f. [1]) is an optimization problem in which a line segment is to be searched by a set of mobile robots, where each robot has a searching speed \(s_i\) and a walking speed \(w_i\), such that \(s_i < w_i\). We explore a natural generalization of the Beachcombers’ Problem, the \(t\)-Source Beachcombers’ Problem (\(t\)-SBP), where the robots are not constrained to start at a single source: Consider \(n\) mobile robots labelled \(1,2,\ldots , n\). We choose \(t\) sources and we assign each robot to one of them. The problem is to choose the sources and develop mobility schedules (algorithms) for the robots which maximizes the speed of the fleet, or minimize the time that the robots need to collectively search the domain. We propose several algorithms for solving problems of this nature. We prove that \(2\)-SBP is NP-hard even when the robots have identical walking speeds. This contrasts with the case when the robots have identical search speeds, where we give a polynomial time algorithm for \(t\)-SBP. We also give a \(0.5569\)-approximation for \(2\)-SBP with arbitrary walking and searching speeds. For \(t\)-SBP with arbitrary walking and searching speeds, we give an oblivious randomized algorithm and prove that it provides an expected \(1 - 1/e\) approximation, asymptotically in \(t\).
Jurek Czyzowicz, Leszek Gąsieniec, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie

Multi-Robot Foremost Coverage of Time-Varying Graphs

Abstract
In this paper we demonstrate the application of time-varying graphs (TVGs) for modeling and analyzing multi-robot foremost coverage in dynamic environments. In particular, we consider the multi-robot, multi-depot Dynamic Map Visitation Problem (DMVP), in which a team of robots must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during navigation. We analyze DMVP in the context of the \(\mathcal {R} \supset \mathcal {B} \supset \mathcal {P}\) TVG hierarchy. We present exact offline algorithms for \(k\) robots on edge-recurrent TVGs (\(\mathcal {R}\)) over a range of topologies motivated by border coverage: an \(O(Tn)\) algorithm on a path and an \(O(T\frac{n^2}{k})\) algorithm on a cycle (where \(T\) is a time bound that is linear in the input size), as well as polynomial and fixed parameter tractable solutions for more general notions of border coverage. We also present algorithms for the case of two robots on a tree (and outline generalizations to \(k\) robots), including an \(O(n^5)\) exact algorithm for the case of edge-periodic TVGs (\(\mathcal {P}\)) with period 2, and a tight poly-time approximation for time-bounded edge-recurrent TVGs (\(\mathcal {B}\)). Finally, we present a linear-time \(\frac{12 \varDelta }{5}\)-approximation for two robots on general graphs in \(\mathcal {B}\) with edge-recurrence bound \(\varDelta \).
Eric Aaron, Danny Krizanc, Elliot Meyerson

Strategies for Parallel Unaware Cleaners

Abstract
We investigate the parallel traversal of a graph with multiple robots unaware of each other. All robots traverse the graph in parallel forever and the goal is to minimize the time needed until the last node is visited (first visit time) and the time between revisits of a node (revisit time). We also want to minimize the visit time, i.e. the maximum of the first visit time and the time between revisits of a node. We present randomized algorithms for uncoordinated robots, which can compete with the optimal coordinated traversal by a small factor, the so-called competitive ratio.
For ring and path graph simple traversal strategies allow constant competitive factors even in the worst case. For grid and torus graphs with \(n\) nodes there is a \(\mathcal{O}(\log n)\)-competitive algorithm for both visit problems succeeding with high probability, i.e. with probability \(1-n^{-\mathcal{O}(1)}\). For general graphs we present an \(\mathcal{O}(\log ^2 n)\)-competitive algorithm for the first visit problem, while for the visit problem we show an \(\mathcal{O}(\log ^3 n)\)-competitive algorithm both succeeding with high probability.
Christian Ortolf, Christian Schindelhauer

Minimum-Traveled-Distance Gathering of Oblivious Robots over Given Meeting Points

Abstract
The paper considers a new variant of the gathering problem of oblivious and asynchronous robots moving in the plane. Robots operate in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of robots distribution (Look), decides whether to move toward some direction (Compute), and in the positive case it moves (Move). Cycles are performed asynchronously for each robot. Robots are anonymous and execute the same distributed algorithm that must guarantee to move all robots to meet at some point among a predetermined set. During the Look phase robots perceive not only the relative positions of the other robots, but also the relative positions of a set of points referred to as meeting points where gathering must be finalized.
We are interested in designing a gathering algorithm that solves the problem by also minimizing the total distances covered by all robots. We characterize when this gathering problem can be optimally solved, and we provide a new distributed algorithm along with its correctness.
Serafino Cicerone, Gabriele Di Stefano, Alfredo Navarra

Algorithms and Data Structures on Graphs

Frontmatter

Fast Rendezvous with Advice

Abstract
Two mobile agents, starting from different nodes of an \(n\)-node network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set \(\{1,\ldots ,L\}\), which it can use in the execution of the algorithm, but it does not know the label of the other agent.
The main efficiency measure of a rendezvous algorithm’s performance is its time, i.e., the number of rounds from the start of the later agent until the meeting. If \(D\) is the distance between the initial positions of the agents, then \(\varOmega (D)\) is an obvious lower bound on the time of rendezvous. However, if each agent has no initial knowledge other than its label, time \(O(D)\) is usually impossible to achieve. We study the minimum amount of information that has to be available a priori to the agents to achieve rendezvous in optimal time \(\varTheta (D)\). Following the standard paradigm of algorithms with advice, this information is provided to the agents at the start by an oracle knowing the entire instance of the problem, i.e., the network, the starting positions of the agents, their wake-up rounds, and both of their labels. The oracle helps the agents by providing them with the same binary string called advice, which can be used by the agents during their navigation. The length of this string is called the size of advice. Our goal is to find the smallest size of advice which enables the agents to meet in time \(\varTheta (D)\). We show that this optimal size of advice is \(\varTheta (D\log (n/D)+\log \log L)\). The upper bound is proved by constructing an advice string of this size, and providing a natural rendezvous algorithm using this advice that works in time \(\varTheta (D)\) for all networks. The matching lower bound, which is the main contribution of this paper, is proved by exhibiting classes of networks for which it is impossible to achieve rendezvous in time \(\varTheta (D)\) with smaller advice.
Avery Miller, Andrzej Pelc

Computing the Dynamic Diameter of Non-Deterministic Dynamic Networks is Hard

Abstract
A dynamic network is a communication network whose communication structure can evolve over time. The dynamic diameter is the counterpart of the classical static diameter, it is the maximum time needed for a node to causally influence any other node in the network. We consider the problem of computing the dynamic diameter of a given dynamic network. If the evolution is known a priori, that is if the network is deterministic, it is known it is quite easy to compute this dynamic diameter. If the evolution is not known a priori, that is if the network is non-deterministic, we show that the problem is hard to solve or approximate. In some cases, this hardness holds also when there is a static connected subgraph for the dynamic network.
In this note, we consider an important subfamily of non-deterministic dynamic networks: the time-homogeneous dynamic networks. We prove that it is hard to compute and approximate the value of the dynamic diameter for time-homogeneous dynamic networks.
Emmanuel Godard, Dorian Mazauric

Improved Spanners in Networks with Symmetric Directional Antennas

Abstract
Consider a set \(S\) of sensors in a plane, each equipped with a directional antenna of beamwidth \(\frac{\pi }{2}\) and radius \(r\in O(1)\). The antennas are symmetric, i.e. for two sensors \(u\) and \(v\) to communicate, \(u\) has to be covered by the antenna of \(v\) and vice versa. Assuming the Unit Disc Graph (\(\mathrm{UDG}\)) of \(S\) is connected, the problem we attack is: How to orient the antennas so that the resulting connectivity graph is a \(k\)-spanner of the \(\mathrm{UDG}\), while minimizing the radius used?
We provide two results: (a) \(7\)-spanner using radius \(33\), and (b) \(5\)-spanner, still using \(O(1)\) radius. This significantly improves the previous state of the art (\(8\)-spanner), even improving upon the pre previous best result (\(6\)-spanner) for beamwidth \(\frac{2\pi }{3}\).
Stefan Dobrev, Milan Plžík

Wireless Networks

Frontmatter

Exploiting Geometry in the SINR $$_k$$ Model

Abstract
We introduce the SINR\(_k\) model, which is a practical version of the SINR model. In the SINR\(_k\) model, in order to determine whether \(s\)’s signal is received at \(c\), where \(s\) is a sender and \(c\) is a receiver, one only considers the \(k\) most significant senders w.r.t. to \(c\) (other than \(s\)). Assuming uniform power, these are the \(k\) closest senders to \(c\) (other than \(s\)). Under this model, we consider the well-studied scheduling problem: Given a set \(L\) of sender-receiver requests, find a partition of \(L\) into a minimum number of subsets (rounds), such that in each subset all requests can be satisfied simultaneously. We present an \(O(1)\)-approximation algorithm for the scheduling problem (under the SINR\(_k\) model). For comparison, the best known approximation ratio under the SINR model is \(O(\log n)\). We also present an \(O(1)\)-approximation algorithm for the maximum capacity problem (i.e., for the single round problem), obtaining a constant of approximation which is considerably better than those obtained under the SINR model. Finally, for the special case where \(k=1\), we present a PTAS for the maximum capacity problem. Our algorithms are based on geometric analysis of the SINR\(_k\) model.
Rom Aschner, Gui Citovsky, Matthew J. Katz

Interference Minimization in Asymmetric Sensor Networks

Abstract
A fundamental problem in wireless sensor networks is to connect a given set of sensors while minimizing the receiver interference. This is modeled as follows: each sensor node corresponds to a point in \({\mathbb R}^d\) and each transmission range corresponds to a ball. The receiver interference of a sensor node is defined as the number of transmission ranges it lies in. Our goal is to choose transmission radii that minimize the maximum interference while maintaining a strongly connected asymmetric communication graph.
For the two-dimensional case, we show that it is NP-complete to decide whether one can achieve a receiver interference of at most \(5\). In the one-dimensional case, we prove that there are optimal solutions with nontrivial structural properties. These properties can be exploited to obtain an exact algorithm that runs in quasi-polynomial time. This generalizes a result by Tan et al. to the asymmetric case.
Yves Brise, Kevin Buchin, Dustin Eversmann, Michael Hoffmann, Wolfgang Mulzer

Minimum Latency Aggregation Scheduling in Wireless Sensor Networks

Abstract
In wireless sensor networks, sensor nodes are used to collect data from the environment and send it to a data collection point or a sink node using a converge cast tree. Considerable savings in energy can be obtained by aggregating data at intermediate nodes along the way to the sink.
We study the problem of finding a minimum latency aggregation tree and transmission schedule in wireless sensor networks. This problem is referred to as Minimum Latency Aggregation Scheduling (MLAS) in the literature and has been proven to be NP-Complete even for unit disk graphs. For sensor networks deployed in a linear domain, that are represented as unit interval graphs, we give a 2-approximation algorithm for the problem. For \(k\)-regular unit interval graphs, we give an optimal algorithm: it is guaranteed to have a latency that is within one time slot of the optimal latency. We also give tight bounds for the latency of aggregation convergecast for grids and tori.
Jonathan Gagnon, Lata Narayanan

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise