Skip to main content
main-content

Über dieses Buch

This book constitutes revised selected papers from the 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2016, held in Aarhus, Denmark, in August 2016.

The 9 full papers presented in this volume were carefully reviewed and selected from 19 submissions. This year papers were solicited into three tracks: Distributed and Mobile, Experiments and Applications, and Wireless and Geometry.

Inhaltsverzeichnis

Frontmatter

Multi-message Broadcast in Dynamic Radio Networks

We continue the recent line of research studying information dissemination problems in adversarial dynamic radio networks. We give two generic algorithms which allow to transform generalized version of single-message broadcast algorithms into multi-message broadcast algorithms. Based on these generic algorithms, we obtain multi-message broadcast algorithms for dynamic radio networks for a number of different dynamic network settings. For one of the modeling assumptions, our algorithms are complemented by a lower bound which shows that the upper bound is close to optimal.

Mohamad Ahmadi, Fabian Kuhn

Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC

Global synchronization is an important prerequisite to many distributed tasks. Communication between processors proceeds in synchronous rounds. Processors are woken up in possibly different rounds. The clock of each processor starts in its wakeup round showing local round 0, and ticks once per round, incrementing the value of the local clock by one. The global round 0, unknown to processors, is the wakeup round of the earliest processor. Global synchronization (or establishing a global clock) means that each processor chooses a local clock round such that their chosen rounds all correspond to the same global round t.We study the task of global synchronization in a Multiple Access Channel (MAC) prone to faults, under a very weak communication model called the beeping model. Some processors wake up spontaneously, in possibly different rounds decided by an adversary. In each round, an awake processor can either listen, i.e., stay silent, or beep, i.e., emit a signal. In each round, a fault can occur in the channel independently with constant probability $$0<p<1$$0<p<1. In a fault-free round, an awake processor hears a beep if it listens in this round and if one or more other processors beep in this round. A processor still dormant in a fault-free round in which some other processor beeps is woken up by this beep and hears it. In a faulty round nothing is heard, regardless of the behaviour of the processors. An algorithm working with error probability at most $$\epsilon $$ϵ, for a given $$\epsilon >0$$ϵ>0, is called $$\epsilon $$ϵ-safe. Our main result is the design and analysis, for any constant $$\epsilon >0$$ϵ>0, of a deterministic $$\epsilon $$ϵ-safe global synchronization algorithm that works in constant time in any fault-prone MAC using beeps.As an application, we solve the consensus problem in a fault-prone MAC using beeps. Processors have input values from some set V and they have to decide the same value from this set. If all processors have the same input value, then they must all decide this value. Using global synchronization, we give a deterministic $$\epsilon $$ϵ-safe consensus algorithm that works in time $$O(\log w)$$O(logw) in a fault-prone MAC, where w is the smallest input value of all participating processors. We show that this time cannot be improved, even when the MAC is fault-free.

Kokouvi Hounkanli, Avery Miller, Andrzej Pelc

Vertex Coloring with Communication and Local Memory Constraints in Synchronous Broadcast Networks

This paper considers the broadcast/receive communication model in which message collisions and message conflicts can occur because processes share frequency bands. (A collision occurs when, during the same round, messages are sent to the same process by too many neighbors. A conflict occurs when a process and one of its neighbors broadcast during the same round.) More precisely, the paper considers the case where, during a round, a process may either broadcast a message to its neighbors or receive a message from at most m of them. This captures communication-related constraints or a local memory constraint stating that, whatever the number of neighbors of a process, its local memory allows it to receive and store at most m messages during each round. The paper defines first the corresponding generic vertex multi-coloring problem (a vertex can have several colors). It focuses then on tree networks, for which it presents a lower bound on the number of colors K that are necessary (namely, $$K=\lceil \frac{\varDelta }{m}\rceil +1$$K=⌈Δm⌉+1, where $$\varDelta $$Δ is the maximal degree of the communication graph), and an associated coloring algorithm, which is optimal with respect to K.

Hicham Lakhlef, Michel Raynal, François Taïani

A New Kind of Selectors and Their Applications to Conflict Resolution in Wireless Multichannels Networks

We investigate the benefits of using multiple channels of communications in wireless networks, under the full-duplex multi-packet reception model of communication. The main question we address is the following: Is a speedup linear in the number of channels achievable, for some interesting communication primitive? We provide a positive answer to this interrogative for the Information Exchange Problem, in which k arbitrary nodes have information they intend to share with the entire network. To achieve this goal, we devise and exploit a combinatorial structure that generalizes well known combinatorial tools widely used in the area of data-exchange in multiple access channels (i.e., strongly selective families, selectors, and related mathematical objects). For our new combinatorial structures we provide both existential results, based on the Lovász Local Lemma, and efficient constructions, leveraging on properties of error correcting codes. We also prove non existential results, showing that our constructions are not too far from being optimal.

Annalisa De Bonis, Ugo Vaccaro

The Impact of the Gabriel Subgraph of the Visibility Graph on the Gathering of Mobile Autonomous Robots

In this work, we reconsider the well-known Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita [2] for gathering in the plane n autonomous mobile robots with limited viewing range. The above authors have introduced it as a discrete, round-based algorithm and proved its correctness. In [8], by Degener et al. it is shown that the algorithm gathers in $$\varTheta \left( n^2\right) $$Θn2 rounds. Remarkably, this algorithm exploits the fact, that during its execution, many collisions of robots occur. Such collisions are interpreted as a success because it is assumed that such collided robots behave the same from now on. This is o.k. under the assumption, those robots have no extent. Otherwise, collisions should be avoided.In this paper, we consider a continuous Go-To-The-Center (GTC) strategy in which the robots continuously observe the positions of their neighbors and adapt their speed (assuming a speed limit) and direction. Our first results are time bounds of $$O\left( n^2\right) $$On2 for gathering in two-dimensional Euclidean space, and $$\varTheta \left( n\right) $$Θn for the one-dimensional case.Our main contribution is the introduction and evaluation of a continuous algorithm which performs Go-To-The-Center considering only the neighbors of a robots w.r.t. the Gabriel subgraph of the visibility graph (GTGC). We show that this modification still correctly executes gathering in one and two dimensions, with the same time bounds as above. Simulations exhibit a severe difference of the behavior of the GTC and the GTGC strategy: Whereas lots of collisions occur during a run of the GTC strategy, typically only one, namely the final collision occurs during a run of the GTGC strategy. We can prove this “collisionless property” of the GTGC algorithm for the one-dimensional case. In the case of the two-dimensional Euclidean space, we conjecture that the “collisionless property” holds for almost every initial configuration.

Shouwei Li, Friedhelm Meyer auf der Heide, Pavel Podlipyan

Search-and-Fetch with One Robot on a Disk

(Track: Wireless and Geometry)

A robot is located at a point in the plane. A treasure and an exit, both stationary, are located at unknown (to the robot) positions both at distance one from the robot. Starting from its initial position, the robot aims to fetch the treasure to the exit. At any time the robot can move anywhere on the disk with constant speed. The robot detects an interesting point (treasure or exit) only if it passes over the exact location of that point. Given that an adversary controls the locations of both the treasure and the exit on the perimeter, we are interested in designing algorithms that minimize the treasure-evacuation time, i.e. the time it takes for the treasure to be discovered and brought to the exit by the robot.In this paper we differentiate how the robot’s knowledge of the distance between the two interesting points affects the overall evacuation time. We demonstrate sthe difference between knowing the exact value of that distance versus knowing only a lower bound and provide search algorithms for both cases. In the former case we give an algorithm which is off from the optimal algorithm (that does not know the locations of the treasure and the exit) by no more than $$\frac{4 \sqrt{2}+3 \pi +2}{6 \sqrt{2}+2 \pi +2}\le 1.019$$42+3π+262+2π+2≤1.019 multiplicatively, or $$\frac{\pi }{2}-\sqrt{2}\le 0.157$$π2-2≤0.157 additively. In the latter case we provide an algorithm which is shown to be optimal.

Konstantinos Georgiou, George Karakostas, Evangelos Kranakis

A 2-Approximation Algorithm for Barrier Coverage by Weighted Non-uniform Sensors on a Line

Barrier coverage is an approach to the intruder detection problem that relies on monitoring a perimeter, or barrier, of an area of interest using sensors placed around it. In this paper, we propose a weighted generalization of the unweighted line segment barrier coverage problem studied in [5] for which the authors demonstrate an FPTAS. We develop a fast, simple 2-approximation algorithm for the weighted case likely to be of interest to practitioners, and show that the FPTAS developed in [5] can be adapted to the weighted problem.

Robert Benkoczi, Daya Ram Gaur, Mark Thom

Flexible Cell Selection in Cellular Networks

We introduce the problem of Flexible Scheduling on Related Machines with Assignment Restrictions (FSRM). In this problem the input consists of a set of machines and a set of jobs. Each machine has a finite capacity, and each job has a resource requirement interval, a profit per allocated unit of resource, and a set of machines that can potentially supply the requirement. A feasible solution is an allocation of machine resources to jobs such that: (i) a machine resource can be allocated to a job only if it is a potential supplier of this job, (ii) the amount of machine resources allocated by a machine is bounded by its capacity, and (iii) the amount of resources that are allocated to a job is either in its requirement interval or zero. Notice that a job can be serviced by multiple machines. The goal is to find a feasible allocation that maximizes the overall profit. We focus on r-FSRM in which the required resource of a job is at most an r-fraction of (or r times) the capacity of each potential machine. FSRM is motivated by resource allocation problems arising in cellular networks and in cloud computing. Specifically, FSRM models the problem of assigning clients to base stations in 4G cellular networks. We present a 2-approximation algorithm for 1-FSRM and a $$\frac{1}{1-r}$$11-r-approximation algorithm for r-FSRM, for any $$r \in (0,1)$$r∈(0,1). Both are based on the local ratio technique and on maximum flow computations. We also present an LP-rounding 2-approximation algorithm for a flexible version of the Generalized Assignment Problem that also applies to 1-FSRM. Finally, we give an $$\varOmega (\frac{r}{\log r})$$Ω(rlogr) lower bound on the approximation ratio for r-FSRM (assuming P $$\ne $$≠ NP).

Dror Rawitz, Ariella Voloshin

The Euclidean k-Supplier Problem in

In this paper, we consider k-supplier problem in . Here, two sets of points $$\mathcal{P}$$P and $$\mathcal{Q}$$Q are given. The objective is to choose a subset $$Q_{opt} \subseteq \mathcal{Q}$$Qopt⊆Q of size at most k such that congruent disks of minimum radius centered at the points in $$Q_{opt}$$Qopt cover all the points of $$\mathcal{P}$$P.We propose a fixed-parameter tractable (FPT) algorithm for the k-supplier problem that produces a 2-factor approximation result. For $$|P|=n$$|P|=n and $$|Q|=m$$|Q|=m, the worst case running time of the algorithm is $$O(6^k (n+m) \log (mn))$$O(6k(n+m)log(mn)), which is an exponential function of the parameter k. We also propose a heuristic algorithm based on Voronoi diagram for the k-supplier problem, and experimentally compare the result produced by this algorithm with the best known approximation algorithm available in the literature [Nagarajan, V., Schieber, B., Shachnai, H.: The Euclidean k-supplier problem, In Proc. of 16th Int. Conf. on Integ. Prog. and Comb. Optim., 290–301 (2013)]. The experimental results show that our heuristic algorithm is slower than Nagarajan et al.’s $$(1+\sqrt{3})$$(1+3)-approximation algorithm, but the results produced by our algorithm significantly outperforms that of Nagarajan et al.’s algorithm.

Manjanna Basappa, Ramesh K. Jallu, Gautam K. Das, Subhas C. Nandy

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise