Accepted Papers

Adil Erzin and Roman Plotnikov: Conflict-Free Data Aggregation on a Square Grid When Transmission Distance is Not Less Than 3

In this paper a Convergecast Scheduling Problem on a unit square grid, in each node of which there is a sensor with transmission distance d which is not less than 3, is considered. For the cases d = 1 and d = 2, polynomial algorithms, which construct the optimal solution to the problem, are known. For an arbitrary d, an approximate algorithm is proposed, the application of which gives an upper bound on the length of the conflict-free data aggregation schedule, depending on d. We conducted a priori and a posteriori analysis of the accuracy of this algorithm for various d comparing either with the optimal length of the schedule, or with a lower bound, the value of which we improved.

Matthias Fischer, Daniel Jung, and Friedhelm Meyer auf der Heide: Gathering Anonymous, Oblivious Robots on a Grid

We consider a swarm of n autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: All robots have to gather at one (not predefined) place. A common local model for extremely simple robots is the following: The robots do not have a common compass, only have a constant viewing radius, are autonomous and indistinguishable, can move at most a constant distance in each step, cannot communicate, are oblivious and do not have flags or states. The only gathering algorithm under this robot model, with known runtime bounds, needs O(n2) rounds and works in the Euclidean plane. The underlying time model for the algorithm is the fully synchronous FSYNC model. On the other side, in the case of the 2-dimensional grid, the only known gathering algorithms for the same time and a similar local model additionally require a constant memory, states and flags to communicate these states to neighbors in viewing range. They gather in time O(n).
In this paper we contribute the (to the best of our knowledge) first gathering algorithm on the grid that works under the same simple local model as the above mentioned Euclidean plane strategy, i.e., without memory (oblivious), flags and states. We prove its correctness and an O(n2) time bound in the fully synchronous FSYNC time model. This time bound matches the time bound of the best known algorithm for the Euclidean plane mentioned above. We say gathering is done if all robots are located within a 2 × 2 square, because in FSYNC such configurations cannot be solved.

Pavel Podlipyan, Shouwei Li, Christine Markarian and Friedhelm Meyer Auf der Heide: A Continuous Strategy for Collisionless Gathering

Huda Chuangpishit , Kostantinos Georgiou and Evangelos Kranakis: Querying with Uncertainty

We introduce and study a new optimization problem on querying with uncertainty. k robots are required to locate a hidden item that is placed uniformly at random in one of n different locations, each associated with a probability pi, i = 1,…,n. If the item is placed in location i, a query trial by any of the robots reveals the item with probability pi. Each robot j is assigned a subset Aj of the locations, and is allowed to perform a random walk among them, each time step querying the current location (being visited) for the item. We are interested in determining sets {Aj}j=1,…,k so as to minimize the expected discovery time of the item. We measure the cost by the number of queries, while there is no cost for hopping from node to node.
Our first contribution is to prove a closed formula for the expected number of steps until the treasure is found when the robots execute unanimous queries. Then we focus on querying problems where the sets Aj are restricted to be either pairwise disjoint or identical. Our findings allow us to obtain optimal solutions, when sets Aj are exclusively pair- wise disjoint, requiring time nO(k). In our second contribution, we devise an optimal polynomial time algorithm for querying with k = 2 robots even when the sets A1,A2 are allowed to overlap. All our algorithms are based on special concavity-type properties of the expected termination time when the robots execute unanimous queries, thus inducing special structural properties of optimal solutions for the general problem.

Joshua J. Daymude, Robert Gmyr, Andrea W. Richa, Christian Scheideler, and Thim Strothmann: Improved Leader Election for Self-Organizing Programmable Matter

We consider programmable matter that consists of computationally limited devices (called particles) that are able to self-organize in order to achieve some collective goal without the need for central control or external intervention. We use the geometric amoebot model to describe such self-organizing particle systems, which defines how particles can actively move and communicate with one another. In this paper, we present an efficient local-control algorithm which solves the leader election problem in O(n) asynchronous rounds with high probability, where n is the number of particles in the system. Our algorithm relies only on local information — particles do not have unique identifiers, any knowledge of n, or any sort of global coordinate system — and requires only constant memory per particle.

Pavan Sangha, Prudence W. H. Wong, and Michele Zito: Independent Sets in Restricted Line of Sight Networks

Line of Sight (LoS) networks were designed to model wireless networks in settings which may contain obstacles restricting visibility of sensors. A graph G = (V, E) is a 2-dimensional LoS network if it can be embedded in an n × k rectangular point set such that a pair of vertices in E are adjacent if and only if the embedded vertices are placed on the same row or column and are at a distance less than ω. We study the Maximum Independent Set (MIS) problem in restricted LoS networks where k is a constant. It has been shown in the unrestricted case when n = k and n → ∞ that the MIS problem is NP-hard when ω ≥ 2 is fixed or when ω = O(n1−ε) grows as a function of n for fixed 0 < ε < 1. In this paper we develop a dynamic programming (DP) algorithm which shows that in the restricted case the MIS problem is solvable in polynomial time for all ω. We then generalise the DP algorithm to solve three additional problems which involve two versions of the Maximum Weighted Independent Set (MWIS) problem and a scheduling problem which exhibits LoS properties in one dimension. We use the initial DP algorithm to develop an efficient polynomial time approximation scheme (EPTAS) for the MIS problem in restricted LoS networks. This has important applications, as it provides a semi-online solution to a particular instance of the scheduling problem. Finally we extend the EPTAS result to the MWIS problem.

Menachem Poss and Dror Rawitz: Maximizing Barrier Coverage Lifetime with Static Sensors

We study variants of the Strip Cover problem (SC) in which sensors with limited battery power are deployed on a line barrier, and the goal is to cover the barrier as long as possible. The energy consumption of a sensor depends on its sensing radius: energy is drained in inverse proportion to the sensor radius raised to a constant exponent α ≥ 1. In the Set Once Strip Cover (OnceSC) the radius of each sensor can be set once, and the sensor can be activated at any time. SCk and OnceSCk are variants of SC and OnceSC, resp., in which each sensor is associated with a set of at most k predetermined radii.
It was previously known that OnceSC is NP-hard when α = 1, and the complexity of the case where α > 1 remained open. We extend the above mentioned NP-hardness result in two ways: we show that OnceSC is NP-hard for every α > 1 and that OnceSC is strongly NP-hard for α = 1. In addition, we show that OnceSCk, for k ≥ 2, is NP-hard, for any α ≥ 1, even for uniform radii sets. On the positive side, we present (i) a 5γα-approximation algorithm for OnceSCk, for k ≥ 1, where γ is the maximum ratio between two radii associated with the same sensor; (ii) a 5-approximation algorithm for SCk, for every k ≥ 1; and (iii) a 5 · 2α -approximation algorithm for Strip Cover. Finally, we present an O(n log n)-time algorithm for a variant of OnceSCk in which all sensors must be activated at the same time.

Keren Censor-Hillel, Rina Levy, and Hadas Shachnai: Fast Distributed Approximation for Max-Cut

Finding a maximum cut is a fundamental task in many computational settings, with a central application in wireless networks. Surprisingly, Max-Cut has been insufficiently studied in the classic distributed settings, where vertices communicate by synchronously sending messages to their neighbors according to the underlying graph, known as the LOCAL or CONGEST models. We amend this by obtaining almost optimal algorithms for Max-Cut on a wide class of graphs in these mod- els. In particular, for any ε > 0, we develop randomized approximation algorithms achieving a ratio of (1 − ε) to the optimum for Max-Cut on bipartite graphs in the CONGEST model, and on general graphs in the LOCAL model.
We further present efficient deterministic algorithms, including a 1/3- approximation for Max-Dicut in our models, thus improving the best known (randomized) ratio of 1/4. Our algorithms make non-trivial use of the greedy approach of Buchbinder et al. (SIAM Journal on Computing, 2015) for maximizing an unconstrained (non-monotone) submodular function, which may be of independent interest.

Evangelos Bampas, Shantanu Das, Dariusz Dereniowski, and Christina Karousatou: Collaborative delivery by energy-sharing low-power mobile robots

We study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one unit and the robot can only perform such move initially having at least one unit of energy. There are two distinguished nodes s and t in the graph and the goal for the robots is to deliver the package initially present on s to the node t. The package can be passed from one robot to another when they are colocated. In the first problem we study, the robots are initially placed at some given nodes of the graph and the question is whether the delivery is feasible. We prove that this problem is NP-complete. In the second problem, the initial positions of the robots are not fixed but a subset of nodes H of the graph is given as input together with an integer k, and the question is as follows: is there a placement of k robots at nodes in H such that the delivery is possible? We prove that this problem can be solved in polynomial time.

Jerzy Czyzowicz, Krzysztof Diks, Jean Moussi, and Wojciech Rytter: Energy-Optimal Broadcast in a Tree with Mobile Agents

A set of k mobile agents is deployed at the root r of a weighted, n-node tree T . The weight of each tree edge represents the distance between the corresponding nodes along the edge. One node of the tree, the source s, possesses a piece of information which has to be communicated (broadcasted) to all other nodes using mobile agents. An agent visiting a node, which already possesses the information, automatically acquires it and communicates it to all nodes subsequently visited by this agent. The process finishes when the information is transferred to all nodes of the tree.
The agents spend energy proportionally to the distance traversed. The problem considered in this paper consists in finding the minimal total energy, used by all agents, needed to complete the broadcasting. We give an O(n log n) time algorithm solving the problem. If the number of agents is sufficiently large (at least equal to the number of leaves of T), then our approach results in an O(n) time algorithm. When the source of information s is initially at the root r, our algorithm solves the problem of searching the tree (exploring it) by a set of agents using minimal energy. It is known that, even if the tree is a line, the broadcasting problem and the search problem are NP-complete when the agents may be initially placed at possibly many distinct arbitrary positions.

Jurek Czyzowicz, Stefan Dobrev, Maxime Godon, Evangelos Kranakis, Toshinori Sakai, and Jorge Urrutia: Searching for a Non-adversarial, Uncooperative Agent on a Cycle

Assume k robots are placed on a cycle–the perimeter of a unit (radius) disk–at a position of our choosing and can move on the cycle with maximum speed 1. A non-adversarial, uncooperative agent, called bus, is moving with constant speed s along the perimeter of the cycle. The robots are searching for the moving bus but do not know its exact location; during the search they can move anywhere on the perimeter of the cycle. We give algorithms which minimize the worst-case search time required for at least one of the robots to find the bus.
The following results are obtained for one robot. 1) If the robot knows the speed s of the bus but does not know its direction of movement then the optimal search time is shown to be exactly 1a) 2π/s, if s ≥ 1, 1b) 4π/(s+1), if 1/3 ≤ s ≤ 1, and 1c) 2π/(1−s), if s ≤ 1/3. 2) If the robot does not know neither the speed nor the direction of movement of the bus then the optimal search time is shown to be 2π(1 + 1 ). Moreover, s+1 for all ε > 0 there exists a speed s such that any algorithm knowing neither the bus speed nor its direction will need time at least 4π − ε to meet the bus.
These results are also generalized to k ≥ 2 robots and analogous tight upper and lower bounds are proved depending on the knowledge the robots have about the speed and direction of movement of the bus.

Joffroy Beauquier, Janna Burman, Shay Kutten, Thomas Nowak, and Chuan Xu: Data Collection in Population Protocols with Non-uniformly Random Scheduler

Contrary to many previous studies on population protocols using the uniformly random scheduler, we consider a more general non-uniform case. Here, pair-wise interactions between agents (moving and communicating devices) are assumed to be drawn non-uniformly at ran- dom. While such a scheduler is known to be relevant for modeling many practical networks, it is also known to make the formal analysis more difficult.
This study concerns data collection, a fundamental problem in mobile sensor networks (one of the target networks of population protocols). In this problem, pieces of information given to the agents (e.g., sensed values) should be delivered eventually to a predefined sink node without loss or duplication. Following an idea of the known deterministic protocol TTF solving this problem, we propose an adapted version of it and perform a complete formal analysis of execution times in expectation and with high probability (w.h.p.).
We further investigate the non-uniform model and address the important issue of energy consumption. The goal is to improve TTF in terms of energy complexity, while still keeping good time complexities (in expectation and w.h.p.). Namely, we propose a new parametrized protocol for data collection, called lazy TTF, and present a study showing that a good choice of the protocol parameters can improve energy performances (compared to TTF), at a slight expense of time performance.

Matthias Bentert, Rene van Bevern, Andre Nichterlein, and Rolf Niedermeier: Parameterized algorithms for power-efficient connected symmetric wireless sensor networks

We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless sensor communication network. Given an edge-weighted n-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. We provide an algorithm that works in polynomial time if one can find a set of obligatory edges that yield a spanning subgraph with O(log n) connected components. We also provide a linear-time algorithm that reduces any input graph that consists of a tree together with g additional edges to an equivalent graph with O(g) vertices. Based on this, we obtain a polynomial-time algorithm for g ∈ O(log n). On the negative side, we show that o(log n)-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard and that there are presumably no exact algorithms running in 2o(n) time or in f(d)·nO(1) time for any computable function f.

Attila Hideg and Tamas Lukovszki: Uniform dispersal of robots with minimum visibility range

We consider the filling problem, in which autonomous mo- bile robots enter a connected orthogonal area from several entry points and have to disperse in order to reach full coverage. The entry points are called doors. The area is decomposed into cells. The robots are autonomous, anonymous, they have a limited visibility range of one unit, and do not use explicit communication. Collision of the robots is not allowed. First we describe an algorithm solving the filling problem for the single door case in O(n) time steps in the synchronous model, where n is the number of cells in the area. This algorithm is optimal in terms of visibility range, and asymptotically optimal in running time and size of persistent memory used by the robots. Moreover, we show that our algorithm solves the multiple door filling problem in O(n) time, as well. For the multiple door case, our algorithm is asymptotically worst-case optimal, and its running time is at most k times the running time of the optimal algorithm for any input, where k is the number of doors.

Huda Chuangpishit, Jurek Czyzowicz, Evangelos Kranakis, and Danny Krizanc: Rendezvous on a Line by Location-Aware Robots Despite the Presence of Byzantine Faults

A set of mobile robots is placed at points of an infinite line. The robots are equipped with GPS devices and they may communicate their positions on the line to a central authority. The collection contains an unknown subset of “spies”, i.e., byzantine robots, which are indistinguishable from the non-faulty ones. The set of the non-faulty robots need to rendezvous in the shortest possible time in order to perform some task, while the byzantine robots may try to delay their rendezvous for as long as possible. The problem facing a central authority is to determine trajectories for all robots so as to minimize the time until the non-faulty robots have rendezvoused. The trajectories must be determined without knowledge of which robots are faulty. Our goal is to minimize the competitive ratio between the time required to achieve the first rendezvous of the non-faulty robots and the time required for such a rendezvous to oc- cur under the assumption that the faulty robots are known at the start. We provide a bounded competitive ratio algorithm, where the central authority is informed only of the set of initial robot positions, without knowing which ones or how many of them are faulty. When an upper bound on the number of byzantine robots is known to the central authority, we provide algorithms with better competitive ratios. In some instances we are able to show these algorithms are optimal.

Jacek Cichon, Mirosław Kutyłowski, Kamil Wolny: Braid Chain Radio Communication

We consider data transmission in a wireless multi-hop network,where node failures may occur and it is risky to send over a single path. As the stations may transmit at the same time, we apply the Cai-Lu-Wang collision avoidance scheme. We assume that the nodes know only their neighbors and there is no global coordination. The routing strategy is to transmits to all nodes that are in some sense closer to the destination node.
We analyze propagation strategy for the case that the nodes know only the nodes in their propagation range and there is no global coordination of the network. Instead, a node transmits to all nodes that appear in some sense closer to the destination node. We investigate data propagation speed in such networks, namely the delay due to conflict resolution.
In order to understand the phenomena arising there we focus on a fundamental case called a braid chain. We prove that for a braid chain of n layers the normalized delay due to anti-collision mechanism is ≈ 0.28n · ∆ (while the expected time for a chain of single stations is 0.5n · ∆), where ∆ stands for the time interval length of Cai-Lu-Wang scheme. We also show that the behavior of the braid chain rapidly converges to its stationary distribution with the length of the chain. For these results we develop analytical methods that can be applied for other networks, e.g. for the case when the forwarding delays are chosen with exponential distribution.

Andrew Cherry, Joachim Gudmundsson, and Julian Mestre: Barrier coverage with uniform radii in 2D

Given a set B of disjoint line segments in the plane, the so-called barriers, and a set of n sensors with uniform range in the plane, the barrier coverage problem is to move the sensors so that they cover the segments in B, while minimizing the total movement of the sensors. In the 1D case when B contains a single barrier and all the sensors lie on B then the problem can be solved in O(n log n) time. In 2D very little is known about the complexity of the problem.
We consider the 2D setting and give a sqrt(2)-approximation algorithm when B contains a single barrier, or a set of parallel barriers. We also give an approximation algorithm for arbitrarily oriented disjoint barriers.