Skip to main content

About this book

This book constitutes revised selected papers from the 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2020, held in Pisa, Italy*, in September 2020.

The 12 full papers presented in this volume were carefully reviewed and selected from 27 submissions. ALGOSENSORS is an international symposium dedicated to the algorithmic aspects of wireless networks.

*The conference was held virtually due to the COVID-19 pandemic.

Table of Contents


Minimizing Total Interference in Asymmetric Sensor Networks

The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common model is the receiver-centric, in which the interference of a node p is defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized.
For the one-dimensional case, we show how to solve the problem optimally in \(O(n^3)\) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem.
A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz

Distributed Localization of Wireless Sensor Network Using Communication Wheel

We study the network localization problem, i.e., the problem of determining node positions of a wireless sensor network modeled as a unit disk graph. In an arbitrarily deployed network, positions of all nodes of the network may not be uniquely determined. It is known that even if the network corresponds to a unique solution, no polynomial-time algorithm can solve this problem in the worst case, unless RP = NP. So we are interested in algorithms that efficiently localize the network partially. A widely used technique that can efficiently localize a uniquely localizable portion of the network is trilateration: starting from three anchors (nodes with known positions), nodes having at least three localized neighbors are sequentially localized. However, the performance of trilateration can substantially differ for different choices of the initial three anchors. In this paper, we propose a distributed localization scheme with a theoretical characterization of nodes that are guaranteed to be localized. In particular, our proposed distributed algorithm starts localization from a strongly interior node and provided that the subgraph induced by the strongly interior nodes is connected, it localizes all nodes of the network except some boundary nodes and isolated weakly interior nodes.
Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, Buddhadeb Sau

Covering Users by a Connected Swarm Efficiently

In this paper we study covering problems that arise in wireless networks with Unmanned Aerial Vehicles (UAVs) swarms. In the general setting we want to place a set of UAVs that should cover a given set of planar users under some constraints and we want to maintain the solution efficiently in a static and dynamic fashion. Specifically, for a set S of n non-negative weighted points in the plane, we consider a set P of m disks (or squares) of radius \(R_{COV}\) where the goal is to place (and maintain under dynamic updates) their location such that the sum of the weights of the points in S covered by disks from P is maximized. In the connected version, we also require that the graph imposed on P should be connected. Moreover, for the static connected version we improve the results from [1] and we obtain a constant factor approximation algorithm. In order to solve our problem under various requirements, we use a variety of techniques including dynamic grid, a reduction to Budgeted Subset Steiner Connected Dominating Set problem, tree partition, and others. We present several simple data structures that maintain an O(1)-approximate solution efficiently, under insertions and deletions of points to/from S where each update operation can be performed in logarithmic time.
Kiril Danilchenko, Michael Segal, Zeev Nutov

VectorTSP: A Traveling Salesperson Problem with Racetrack-Like Acceleration Constraints

We study a new version of the Euclidean TSP called VectorTSP (VTSP for short) where a mobile entity is allowed to move according to a set of physical constraints inspired from the pen-and-pencil game Racetrack (also known as Vector Racer). In contrast to other versions of TSP accounting for physical constraints, such as Dubins TSP, the spirit of this model is that (1) no speed limitations apply, and (2) inertia depends on the current velocity. As such, this model is closer to typical models considered in path planning problems, although applied here to the visit of n cities in a non-predetermined order.
We motivate and introduce the VectorTSP problem, discussing fundamental differences with previous versions of TSP. In particular, an optimal visit order for ETSP may not be optimal for VTSP. We show that VectorTSP is NP-hard, and in the other direction, that VectorTSP reduces to GroupTSP in polynomial time (although with a significant blow-up in size). On the algorithmic side, we formulate the search for a solution as an interactive scheme between a high-level algorithm and a trajectory oracle, the former being responsible for computing the visit order and the latter for computing the cost (or the trajectory) for a given visit order. We present algorithms for both, and we demonstrate and quantify through experiments that this approach frequently finds a better solution than the optimal trajectory realizing an optimal ETSP tour, which legitimates the problem itself.
Arnaud Casteigts, Mathieu Raffinot, Jason Schoeters

Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory Robots

We provide algorithmic methods for reconfiguration of lattice-based cellular structures by finite-state robots, motivated by large-scale constructions in space. We present algorithms that are able to detect and reconfigure arbitrary polyominoes, while also preserving connectivity of a structure during reconfiguration; we also provide mathematical proofs and performance guarantees. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.
Sándor P. Fekete, Eike Niehs, Christian Scheffer, Arne Schmidt

On Efficient Connectivity-Preserving Transformations in a Grid

We consider a discrete system of n devices lying on a 2-dimensional square grid and forming an initial connected shape \(S_I\). Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step. We study the problem of transforming \(S_I\) into a given connected target shape \(S_F\) of the same number of devices, via a finite sequence of line moves. Our focus is on designing centralised transformations aiming at minimising the total number of moves subject to the constraint of preserving connectivity of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the associated graphs of \( S_I \) and \( S_F \) are isomorphic to a Hamiltonian line. In particular, our transformations make \( O(n \log n \)) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving universal transformation that can transform any initial connected shape \( S_I \) into any target connected shape \( S_F \), through a sequence of \(O(n\sqrt{n})\) moves.
Abdullah Almethen, Othon Michail, Igor Potapov

Live Exploration with Mobile Robots in a Dynamic Ring, Revisited

The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One important requirement of exploration is the termination condition, i.e., the robots must know that exploration is completed. The problem of live exploration of a dynamic ring using mobile robots was recently introduced in [Di Luna et al., ICDCS 2016]. In it, they proposed multiple algorithms to solve exploration in fully synchronous and semi-synchronous settings with various guarantees when 2 robots were involved. They also provided guarantees that with certain assumptions, exploration of the ring using two robots was impossible. An important question left open was how the presence of 3 robots would affect the results. In this paper, we try to settle this question in a fully synchronous setting and also show how to extend our results to a semi-synchronous setting.
In particular, we present algorithms for exploration with explicit termination using 3 robots in conjunction with either (i) unique IDs of the robots and edge crossing detection capability (i.e., two robots moving in opposite directions through an edge in the same round can detect each other), or (ii) access to randomness. The time complexity of our deterministic algorithm is asymptotically optimal. We also provide complementary impossibility results showing that there do not exist any explicit termination algorithms for 2 robots even when each robot has a unique ID, edge crossing detection capability, and access to randomness. We also present an algorithm to achieve exploration with partial termination using 3 robots with unique IDs in the semi-synchronous setting.
Subhrangsu Mandal, Anisur Rahaman Molla, William K. Moses

Asynchronous Filling by Myopic Luminous Robots

We consider the problem of filling an unknown area represented by an arbitrary connected graph of n vertices by mobile luminous robots. In this problem, the robots enter the graph one-by-one through a specific vertex, called the Door, and they eventually have to cover all vertices of the graph while avoiding collisions. The robots are anonymous and make decisions driven by the same local rule of behavior. They have limited persistent memory and limited visibility range. We investigate the Filling problem in the asynchronous model.
We assume that the robots know an upper bound \(\varDelta \) on the maximum degree of the graph before entering. We present an algorithm solving the asynchronous Filling problem with robots having 1 hop visibility range, \(O(\log \varDelta )\) bits of persistent storage, and \(\varDelta +4\) colors, including the color when the light is off. We analyze the algorithm in terms of asynchronous rounds, where a round means the smallest time interval in which each robot, which has not yet finished the algorithm, has been activated at least once. We show that this algorithm needs \(O(n^2)\) asynchronous rounds. Our analysis provides the first asymptotic upper bound on the running time in terms of asynchronous rounds.
Then we show how the number of colors can be reduced to O(1) at the cost of the running time. The algorithm with 1 hop visibility range, \(O(\log \varDelta )\) bits of persistent memory, and O(1) colors needs \(O(n^2\log \varDelta )\) rounds. We show how the running time can be improved by robots with a visibility range of 2 hops, \(O(\log \varDelta )\) bits of persistent memory, and \(\varDelta + 4\) colors (including the color when the light is off). We show that the algorithm needs O(n) asynchronous rounds. Finally, we show how to extend our solution to the k-Door case, \(k\ge 2\), by using \(\varDelta + k + 4\) colors, including the color when the light is off.
Attila Hideg, Tamás Lukovszki

Weighted Group Search on a Line

(Extended Abstract)
We introduce and study a new search-type problem on the line with 2 searchers. As in so-called evacuation search problems with multiple searchers, we require that all searchers reach a hidden item (the exit), placed in an unknown location on a line. The novelty of our problem, weighted group search on a line, pertains to the cost function of a search trajectory, which is defined as the weighted average (1 for the light searcher and \(w\ge 1\) for the heavy searcher) of the times that each searcher reaches the exit and stays there indefinitely. For that problem, and for every \(w\ge 1\), we design searchers’ trajectories (algorithms) that aim to perform well under the lens of (worst case) competitive analysis.
Konstantinos Georgiou, Jesse Lucier

Fast Byzantine Gathering with Visibility in Graphs

We consider the gathering task by a team of m synchronous mobile robots in a graph of n nodes. Each robot has an identifier (ID) and runs its own deterministic algorithm, i.e., there is no centralized coordinator. We consider a particularly challenging scenario: there are f Byzantine robots in the team that can behave arbitrarily, and even have the ability to change their IDs to any value at any time. There is no way to distinguish these robots from non-faulty robots, other than perhaps observing strange or unexpected behaviour. The goal of the gathering task is to eventually have all non-faulty robots located at the same node in the same round. It is known that no algorithm can solve this task unless there at least \(f+1\) non-faulty robots in the team. In this paper, we design an algorithm that runs in polynomial time with respect to n and m that matches this bound, i.e., it works in a team that has exactly \(f+1\) non-faulty robots. In our model, we have equipped the robots with sensors that enable each robot to see the subgraph (including robots) within some distance H of its current node. We prove that the gathering task is solvable if this visibility range H is at least the radius of the graph, and not solvable if H is any fixed constant.
Avery Miller, Ullash Saha

Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots

The problem of dispersion of mobile robots on a graph asks that n robots initially placed arbitrarily on the nodes of an n-node anonymous graph, autonomously move to reach a final configuration where exactly each node has at most one robot on it. This problem has been relatively well-studied when robots are non-faulty. In this paper, we introduce the notion of Byzantine faults to this problem, i.e., we formalize the problem of dispersion in the presence of up to f Byzantine robots. We then study the problem on a ring while simultaneously optimizing the time complexity of algorithms and the memory requirement per robot. Specifically, we design deterministic algorithms that attempt to match the time lower bound (\(\varOmega (n)\) rounds) and memory lower bound (\(\varOmega (\log n)\) bits per robot).
Our main result is a deterministic algorithm that is both time and memory optimal, i.e., O(n) rounds and \(O(\log n)\) bits of memory required per robot, subject to certain constraints. We subsequently provide results that require less assumptions but are either only time or memory optimal but not both. We also provide a primitive that takes robots initially gathered at a node of the ring and disperses them in a time and memory optimal manner without additional assumptions required .
Anisur Rahaman Molla, Kaushik Mondal, William K. Moses

Conic Formation in Presence of Faulty Robots

Pattern formation is one of the most fundamental problems in distributed computing, which has recently received much attention. In this paper, we initiate the study of distributed pattern formation in situations when some robots can be faulty. In particular, we consider the well-established look-compute-move model with oblivious, anonymous robots. We first present lower bounds and show that any deterministic algorithm takes at least two rounds to form simple patterns in the presence of faulty robots. We then present distributed algorithms for our problem which match this bound, for conic sections: in at most two rounds, robots form lines, circles and parabola tolerating \(f=2,3\) and 4 faults, respectively. For \(f=5\), the target patterns are parabola, hyperbola and ellipse. We show that the resulting pattern includes the f faulty robots in the pattern of n robots, where \(n \ge 2f+1\), and that \(f< n < 2f+1\) robots cannot form such patterns. We conclude by discussing several relaxations and extensions.
Debasish Pattanayak, Klaus-Tycho Foerster, Partha Sarathi Mandal, Stefan Schmid


Additional information

Premium Partner

    Image Credits