Algorithms for Sensor Systems

We consider a scenario with a set of autonomous mobile robots having initial positions in the plane. Their goal is to move in such a way that they eventually reach a prescribed formation. Such a formation may be a straight line between two given endpoints (Robot Chain Problem), a circle or any other geometric pattern, or just one point (Gathering Problem). In this survey, we assume that there is no central control that guides the robot’s decisions, thus the robots have to self-organize in order to accomplish global tasks like the above-mentioned formation problems. Moreover, we restrict them to simple local strategies: the robots are limited to ”see” only robots within a bounded viewing range; their decisions where to move next are solely based on the relative positions of robots within this range.

We survey recent results on local strategies for short robot chains and gathering, among them the first that come with upper and lower bounds on the number of rounds needed and the maximum distance traveled. Finally we present a continuous local strategy for short robot chains, and present a bound for the ”price of locality”: for every configuration of initial robot positions, the maximum distance traveled by the robots is at most by a logarithmic (in the number of robots) factor away from the maximum distance of the initial robot positions to the straight line.

We present two distributed, constant factor approximation algorithms for the metric facility location problem. Both algorithms have been designed with a strong emphasis on applicability in the area of wireless sensor networks: in order to execute them, each sensor node only requires limited local knowledge and simple computations. Also, the algorithms can cope with measurement errors and take into account that communication costs between sensor nodes do not necessarily increase linearly with the distance, but can be represented by a polynomial. Since it cannot always be expected that sensor nodes execute algorithms in a synchronized way, our algorithms are executed in an asynchronous model (but they are still able to break symmetry that might occur when two neighboring nodes act at exactly the same time). Furthermore, they can deal with dynamic scenarios: if a node moves, the solution is updated and the update affects only nodes in the local neighborhood. Finally, the algorithms are robust in the sense that incorrect behavior of some nodes during some round will, in the end, still result in a good approximation. The first algorithm runs in expected \(\mathcal{O}(\log_{1+\epsilon} n)\) communication rounds and yields a μ ⁴(1 + 4μ ²(1 + ε)^1/p ) ^p approximation, while the second has a running time of expected \(\mathcal{O}(\log_{1+\epsilon}^2 n)\) communication rounds and an approximation factor of μ ⁴(1 + 2(1 + ε)^1/p ) ^p . Here, ε > 0 is an arbitrarily small constant, p the exponent of the polynomial representing the communication costs, and μ the relative measurement error.

Given n sensors on a line, each of which is equipped with a unit battery charge and an adjustable sensing radius, what schedule will maximize the lifetime of a network that covers the entire line? Trivially, any reasonable algorithm is at least a \(\frac{1}{2}\)-approximation, but we prove tighter bounds for several natural algorithms. We focus on developing a linear time algorithm that maximizes the expected lifetime under a random uniform model of sensor distribution. We demonstrate one such algorithm that achieves an average-case approximation ratio of almost 0.9. Most of the algorithms that we consider come from a family based on RoundRobin coverage, in which sensors take turns covering predefined areas until their battery runs out.

Consider the two related problems of sensor selection and sensor fusion. In the first, given a set of sensors, one wishes to identify a subset of the sensors, which while small in size, captures the essence of the data gathered by the sensors. In the second, one wishes to construct a fused sensor, which utilizes the data from the sensors (possibly after discarding dependent ones) in order to create a single sensor which is more reliable than each of the individual ones.

In this work, we rigorously define the dependence among sensors in terms of joint empirical measures and incremental parsing. We show that these measures adhere to a polymatroid structure, which in turn facilitates the application of efficient algorithms for sensor selection. We suggest both a random and a greedy algorithm for sensor selection. Given an independent set, we then turn to the fusion problem, and suggest a novel variant of the exponential weighting algorithm. In the suggested algorithm, one competes against an augmented set of sensors, which allows it to converge to the best fused sensor in a family of sensors, without having any prior data on the sensors’ performance.

Consider a network of n directional antennae in the plane. We consider the problem of efficient neighbor discovery in a (synchronous) network of sensors employing directional antennae. In this setting sensors send messages and listen for messages by directing their antennae towards a specific direction (which is not necessarily known in advance). In our model the directional antennae can be rotated by the sensors as required so as to discover all neighbors in their vicinity. In this paper we will limit ourselves to the (D,D) communication model whereby sensors employ directional antennae with identical transmission/reception beam widths. Our methodology is based on techniques for symmetry breaking so as to enable sender/receiver communication. We provide 1) deterministic algorithms that introduce delay in the rotation of the antennae and exploit knowledge of the existence of a vertex coloring of the network, and 2) randomized algorithms that require knowledge only of an upper bound on the size of the network so as to accomplish neighbor discovery. In both instances we study tradeoffs on the efficiency of the algorithms proposed.

We present LiMoSense, a fault-tolerant live monitoring algorithm for dynamic sensor networks. This is the first asynchronous robust average aggregation algorithm that performs live monitoring, i.e., it constantly obtains a timely and accurate picture of dynamically changing data. LiMoSense uses gossip to dynamically track and aggregate a large collection of ever-changing sensor reads. It overcomes message loss, node failures and recoveries, and dynamic network topology changes. We formally prove the correctness of LiMoSense; we use simulations to illustrate its ability to quickly react to changes of both the network topology and the sensor reads, and to provide accurate information.

Network localization is important for networks with no prefixed positions of network nodes such as sensor networks. We are given a subset of the set of \(\binom{n}{2}\) pairwise distances among n sensors in some Euclidean space. We want to determine the positions of each sensors from the (partial) distance information. The input can be seen as an edge weighted graph. In this paper, we present some efficient algorithms that solve this problem using the structures of input graphs, which we call the cores of them. For instance, we present a polynomial-time algorithm solving the network localization problem for graphs with connected dominating sets of bounded size. This algorithm allows us to have an FPT algorithm for some restricted instances such as graphs with connected vertex covers of bounded size.

Reducing interference is one of the main challenges in wireless communication. To minimize interference through topology control in wireless sensor networks is a well-known open algorithmic problem. In this paper, we answer the question of how to minimize the average interference when a node is receiving a message. We assume the receiver-centric interference model where the interference on a node is equal to the number of the other nodes whose transmission ranges cover the node. For one-dimensional (1D) networks, we propose a fast polynomial exact algorithm that can minimize the average interference. For two-dimensional (2D) networks, we give a proof that the maximum interference can be bounded while minimizing the average interference. The bound is only related to the distances between nodes but not the network size. Based on the bound, we propose the first exact algorithm to compute the minimum average interference in 2D networks. Optimal topologies with the minimum average interference can be constructed through traceback in both 1D and 2D networks.

Various notions of coverage have been introduced as basic quality-of-service measures for wireless sensor networks. One natural measure of coverage is referred to as resilience: given a starting region S and a target region T, the resilience a sensor configuration with respect to S and T is the minimum number of sensors that need to be deactivated before an S − T path can exist that does not cross any active sensor region. We demonstrate that determining resilience of a network of unit-line-segment sensors is NP-hard. Furthermore, we can extend our proof to show that the resilience problem remains NP-hard for other types of non-symmetric sensor coverage regions.

In multi-hop radio networks, such as wireless ad-hoc and sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of close-by transmissions. These protocols can be implemented using standard node coloring. The (Δ + 1)-coloring problem is to color all nodes in as few timeslots as possible using at most Δ + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Δ is the maximum degree of the modeled unit disk graph using the scaling factor R. Being one of the most fundamental problems in distributed computing, this problem is well studied and there are a long chain of algorithms for it. However, all previous work are based on models that are highly abstract, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice.

In this paper, for the first time, we consider the distributed Δ + 1-coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized (Δ + 1)-coloring algorithm with time complexity O(Δlogn + log² n). For the case where nodes can not adjust their transmission power, we give an O(Δlog² n) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead.

We study the Continuous Monitoring problem providing bounds on performance for several protocols that differ in the use of mobility and the placement of the devices. Our objective is to analyze formally the computational resources needed to solve the Continuous Monitoring in a dynamic context. For doing so, we consider a particular scenario in which communication devices and data sensors move on top of a squared terrain discretized by a mobility grid. We also consider two scenarios, the static data setting in which sensors are placed at fixed but unknown positions and the dynamic data setting in which sensors are placed on dynamic targets and follow a passive mobility pattern.

In traditional multihop network broadcast problems, in which a message beginning at one node is efficiently relayed to all others, cost models typically used involve a charge for each unicast or each broadcast. These settings lead to a minimum spanning tree (MST) problem or the Connected Dominating Set (CDS) problem, respectively. Neglected, however, is the study of intermediate models in which a node can choose to transmit to an arbitrary subset of its neighbors, at a cost based on the number of recipients (due e.g. to acknowledgements or repeat transmissions). We focus in this paper on a transmission cost model of the form 1 + A k ^b , where k is the number of recipients, b ≥ 0, and A ≥ 0, which subsumes MST, CDS, and other problems.

We give a systematic analysis of this problem as parameterized by b (relative to A), including positive and negative results. In particular, we show the problem is approximable with a factor varying from 2 + 2H _Δ down to 2 as b varies from 0 to 1 (via a modified CDS algorithm), and thence with a factor varying from 2 to 1 (i.e., optimal) as b varies from 1 to \(\log_2 (\frac{1}{A}+2)\), and optimal thereafter (both via spanning tree).

For arbitrary cost functions of the form 1 + Af(k), these algorithms provide a 2 + 2H _Δ-approximation whenever f(k) is sublinear and a (1 + A)/A-approximation whenever f(k) is superlinear, respectively. We also show that the problem is optimally solvable for any b when the network is a clique or a tree.

We deal with the problem of streaming multiple video streams between pairs of nodes in a multi-hop wireless ad hoc network. The nodes are static, know their locations, and are synchronized (via GPS). We introduce a new interference model that uses variable interference radiuses. We present an algorithm for computing a frequency assignment and a schedule whose goal is to maximize throughput over all the video streams. In addition, we developed a localized flow-control mechanism to stabilize the queue lengths.

Our algorithm partitions the links into buckets. Every bucket consists of a set of links that have nearly equivalent reception powers. We denote the number of nonempty buckets by σ. Our algorithm obtains an approximation ratio of O(σ·logn), where n denotes the number of nodes. For the case of linear powers σ = 1, hence the approximation ratio of the algorithm is O(logn). This is the first practical approximation algorithm for linear powers with an approximation ratio that depends only on n (and not on the max-to-min distance ratio).

If the transmission power of each link is part of the input (and arbitrary), then σ ≤ logΓ + logΔ, where Γ denotes the ratio of the max-to-min power, and Δ denotes the ratio of the max-to-min distance. Hence, the approximation ratio is O(logn ·(logΓ + logΔ)).

Finally, we consider the case that the algorithm needs to assign powers to each link in a range [P _min ,P _max ]. An extension of the algorithm to this case achieves an approximation ratio of O[(logn + loglogΓ) ·(logΓ + logΔ)].

Given a set of wireless links, a fundamental problem is to find the largest subset that can transmit simultaneously, within the SINR model of interference. Significant progress on this problem has been made in recent years. In this note, we study the problem in the setting where we are given a fixed set of arbitrary powers each sender must use, and an arbitrary gain matrix defining how signals fade. This variation of the problem appears immune to most algorithmic approaches studied in the literature. Indeed it is very hard to approximate since it generalizes the max independent set problem. Here, we propose a simple semi-definite programming approach to the problem that yields constant factor approximation, if the optimal solution is strictly larger than half of the input size.

We consider the problem of capacity in wireless networks in the physical model. The goal of this paper is to compare different power assignments and models from the perspective of this problem. We show a family of power assignments, including the mean power assignment, which yield larger capacity than uniform and linear power assignments, for each network instance. On the other hand, uniform and linear power assignments are not worse (in the same sense) than any power assignment, which is decreasing as a function of link-length, or increasing faster than linear power assignment. We also compare the directed and bidirectional communication models, and show upper and lower bounds on the gap between optimal capacities using any power assignment in these communication models.