Algorithms for Sensor Systems

We propose a new task called \(\delta \)-local gossip, which can be viewed as a variant of both gossiping and geocasting. We motivate its study by showing how the tasks of discovering and maintaining neighbourhood information reduce to solving \(\delta \)-local gossip. We then provide a deterministic algorithm that solves \(\delta \)-local gossip when nodes travel on a line along arbitrary continuous trajectories with bounded speed.

Routing is a challenging problem for wireless ad hoc networks, especially when the nodes are mobile and spread so widely that in most cases multiple hops are needed to route a message from one node to another. In fact, it is known that any online routing protocol has a poor performance in the worst case, in a sense that there is a distribution of nodes resulting in bad routing paths for that protocol, even if the nodes know their geographic positions and the geographic position of the destination of a message is known. The reason for that is that radio holes in the ad hoc network may require messages to take long detours in order to get to a destination, which are hard to find in an online fashion.

In this paper, we assume that the wireless ad hoc network can make limited use of long-range links provided by a global communication infrastructure like a cellular infrastructure or a satellite in order to compute an abstraction of the wireless ad hoc network that allows the messages to be sent along near-shortest paths in the ad hoc network. We present distributed algorithms that compute an abstraction of the ad hoc network in \(\mathcal {O}\left( \log ^2 n\right) \) time using long-range links, which results in c-competitive routing paths between any two nodes of the ad hoc network for some constant c if the convex hulls of the radio holes do not intersect. We also show that the storage needed for the abstraction just depends on the number and size of the radio holes in the wireless ad hoc network and is independent on the total number of nodes, and this information just has to be known to a few nodes for the routing to work.

In the problem of minimum connected dominating set with routing cost constraint, we are given a graph \(G=(V,E)\) and a positive integer \(\alpha \), and the goal is to find the smallest connected dominating set D of G such that, for any two non-adjacent vertices u and v in G, the number of internal nodes on the shortest path between u and v in the subgraph of G induced by \(D \cup \{u,v\}\) is at most \(\alpha \) times that in G. For general graphs, the only known previous approximability result is an \(O(\log n)\)-approximation algorithm (\(n=|V|\)) for \(\alpha = 1\) by Ding et al. For any constant \(\alpha > 1\), we give an \(O(n^{1-\frac{1}{\alpha }}(\log n)^{\frac{1}{\alpha }})\)-approximation algorithm. When \(\alpha \ge 5\), we give an \(O(\sqrt{n}\log n)\)-approximation algorithm. Finally, we prove that, when \(\alpha =2\), unless \(NP \subseteq DTIME(n^{poly\log n})\), for any constant \(\epsilon > 0\), the problem admits no polynomial-time \(2^{\log ^{1-\epsilon }n}\)-approximation algorithm, improving upon the \(\varOmega (\log \delta )\) bound by Du et al., where \(\delta \) is the maximum degree of G (albeit under a stronger hardness assumption).

In this paper, we define a new problem called the Maximum Connectivity Improvement (MCI) problem: given a directed graph \(G = (V,E)\), a weight function \(w:V \rightarrow \mathbb {N}_{\ge 0}\), a profit function \(p:V \rightarrow \mathbb {N}_{\ge 0}\), and an integer B, find a set S of at most B edges not in E that maximises \(f(S)=\sum _{v\in V}w_v\cdot p(R(v,S))\), where p(R(v, S)) is the sum of the profits of the nodes reachable from node v when the edges in S are added to G. We first show that we can focus on Directed Acyclic Graphs (DAG) without loss of generality. We prove that the MCI problem on DAG is \( NP \)-Hard to approximate to within a factor greater than \(1-1/e\) even if we restrict to graphs with a single source or a single sink, and MCI remains \( NP \)-Complete if we further restrict to unitary weights. We devise a polynomial time algorithm based on dynamic programming to solve the MCI problem on trees with a single source. We propose a polynomial time greedy algorithm that guarantees \((1-1/e)\)-approximation ratio on DAGs with a single source or a single sink.

The problem of evacuating two robots from the disk in the face-to-face model was first introduced in [16], and extensively studied (along with many variations) ever since with respect to worst case analysis. We initiate the study of the same problem with respect to average case analysis, which is also equivalent to designing randomized algorithms for the problem. First we observe that algorithm \(\mathscr {B}_{2}\) of [16] with worst case cost \(\mathrm {Wrs}\left( \mathscr {B}_{2}\right) :=5.73906\) has average case cost \(\mathrm {Avg}\left( \mathscr {B}_{2}\right) :=5.1172\). Then we verify that none of the algorithms that induced worst case cost improvements in subsequent publications has better average case cost, hence concluding that our problem requires the invention of new algorithms. Then, we observe that a remarkable simple algorithm, \(\mathscr {B}_{1}\), has very small average case cost \(\mathrm {Avg}\left( \mathscr {B}_{1}\right) :=1+\pi \), but very high worst case cost \(\mathrm {Wrs}\left( \mathscr {B}_{1}\right) :=1+2\pi \). Motivated by the above, we introduce constrained optimization problem \(_2{\textsc {Evac}}_{F2F}^w\), in which one is trying to minimize the average case cost of the evacuation algorithm given that the worst case cost does not exceed w. The problem is of special interest with respect to practical applications, since a common objective in search-and-rescue operations is to minimize the average completion time, given that a certain worst case threshold is not exceeded, e.g. for safety or limited energy reasons.

Our main contribution is the design and analysis of families of new evacuation parameterized algorithms \(\mathscr {A}(p)\) which can solve \(_2{\textsc {Evac}}_{F2F}^w\), for every \(w \in [\mathrm {Wrs}\left( \mathscr {B}_{1}\right) ,\mathrm {Wrs}\left( \mathscr {B}_{2}\right) ]\). In particular, by letting parameter(s) p vary, we obtain parametric curve \(\left( \mathrm {Avg}\left( \mathscr {A}(p)\right) , \mathrm {Wrs}\left( \mathscr {A}(p)\right) \right) \) that induces a continuous and strictly decreasing function in the mean-worst case space, and whose endpoints are \(\left( \mathrm {Avg}\left( \mathscr {B}_{1}\right) , \mathrm {Wrs}\left( \mathscr {B}_{1}\right) \right) \), \(\left( \mathrm {Avg}\left( \mathscr {B}_{2}\right) , \mathrm {Wrs}\left( \mathscr {B}_{2}\right) \right) \). Notably, the worst case analysis of the problem, since it’s introduction, has been relying on technical numerical, computer-assisted, calculations, following tedious robots trajectories’ analysis. Part of our contribution is a novel systematic procedure, which, given any evacuation algorithm, can derive it’s worst and average case performance in a clean and unified way.

Consider a set of autonomous, identical, opaque point robots in the Euclidean plane. The Mutual Visibility problem asks the robots to reposition themselves, without colliding, to a configuration where they all see each other, i.e., no three of them are collinear. In this paper, we consider the problem in a grid based terrain where the movements of the robots are restricted only along grid lines and only by a unit distance in each step. We consider the luminous robots model, in which each robot is equipped with an externally visible light which can assume a constant number of predefined colors. These colors serve both as internal memory and as a form of communication. The robots operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not have any common global coordinate system or chirality and do not have the knowledge of the total number of robots. Our proposed distributed algorithm solves the problem for any arbitrary initial configuration and guarantees collision-free movements.

We consider the problem of gathering a set of autonomous, identical, oblivious, asynchronous, mobile robots at a vertex of an anonymous hypercube. The robots operate in Look-Compute-Move cycles. In each cycle, a robot takes a snapshot of the current configuration (Look), then based on the perceived configuration, decides whether to stay idle or to move to an adjacent vertex (Compute), and in the later case makes an instantaneous move accordingly (Move). We have shown that the problem is unsolvable if the robots do not have multiplicity detection capability. With weak multiplicity detection capability, the problem is solvable in an oriented hypercube for any initial configuration of \(2k+1 (k > 0)\) number of robots. For \(4k (k > 0)\) number of robots, the problem is solvable under the same assumptions if and only if the group of automorphism of the configuration is trivial. Our proposed algorithms are optimal with respect to the total number of moves executed by the robots.

This paper deals with the NP-hard problem of covering a line segment by n initially arbitrarily arranged circles on the plane by moving their centers to the segment in such a way that the sum of the Euclidean distances between the initial and final positions of the centers of the disks would be minimal. In the case of identical circles, a dynamic programming algorithm is known, which constructs a \(\sqrt{2}\)–approximate solution to the problem with \(O(n^4)\)–time complexity. In this paper, we propose a new algorithm that has the same accuracy, but the complexity of which is reduced by \(n^2\) times to \(O(n^2)\).

In the past years, the capabilities and thus application scenarios of Wireless Sensor Networks (WSNs) increased: higher computational power and miniaturization of complex sensors, e.g. fine dust, offer a plethora of new directions. However, energy supply still remains a tough challenge because the use of batteries is neither environmentally-friendly nor maintenance-free. Although energy harvesting promises uninterrupted operation, it requires adaption of the consumption—which becomes even more complex with increased capabilities of WSNs. In existing literature, adaption to the available energy is typically rate-based. This ignores that the underlying physical phenomena are typically related in time and thus the corresponding sensor tasks cannot be scheduled independently. We close this gap by defining task graphs, allowing arbitrary task relations while including time constraints. To ensure uninterrupted operation of the sensor node, we include energy constraints obtained from a common energy-prediction algorithm. Using a standard Integer Linear Programming (ILP) solver, we generate a schedule for task execution satisfying both time and energy constraints. We exemplarily show, how varying energy resources influence the schedule of a fine dust sensor. Furthermore, we assess the overhead introduced by schedule computation and investigate how the size of the task graph and the available energy affect this overhead. Finally, we present indications for efficiently implementing our approach on sensor nodes.

We investigate the interesting impact of mobility on the problem of efficient wireless power transfer in ad hoc networks. We consider a set of mobile agents (consuming energy to perform certain sensing and communication tasks), and a single static charger (with finite energy) which can recharge the agents when they get in its range. In particular, we focus on the problem of efficiently computing the appropriate range of the charger with the goal of prolonging the network lifetime. We first demonstrate (under the realistic assumption of fixed energy supplies) the limitations of any fixed charging range and, therefore, the need for (and power of) a dynamic selection of the charging range, by adapting to the behavior of the mobile agents which is revealed in an online manner. We investigate the complexity of optimizing the selection of such an adaptive charging range, by showing that two simplified offline optimization problems (closely related to the online one) are NP-hard. To effectively address the involved performance trade-offs, we finally present a variety of adaptive heuristics, assuming different levels of agent information regarding their mobility and energy.

The context of this paper is programmable matter, which consists of a set of computational elements, called particles, in an infinite graph. The considered infinite graphs are the square, triangular and king grids. Each particle occupies one vertex, can communicate with the adjacent particles, has the same clockwise direction and knows the local positions of neighborhood particles. Under these assumptions, we describe a new leader election algorithm affecting a variable to the particles, called the k-local identifier, in such a way that particles at close distance have each a different k-local identifier. For all the presented algorithms, the particles only need a O(1)-memory space.

To demonstrate the algorithmic nature of our model, we consider a fundamental problem of reaching consensus by nodes: in the beginning each node has some initial value, e.g., the reading from its sensor, and the goal is that each node outputs the same value.

Our deterministic distributed algorithm runs at every node and outputs the consensus value equal to the sum of inputs divided by the sum of the channel coefficients of each cells. For a node v consensus is reached in \(\mathcal {O}\left( \log _{\rho }\left( \frac{1}{2} \sqrt{\frac{d_{min}}{d_{max}}} \cdot \frac{d_{v}}{b\sum _{i} d_{i}}\right) \right) \) communication rounds, where \( d_{v} \) is the sum of molecule reachability ratios to node v in the medium, \(d_{min}=\min _i d_i\), \(d_{max}=\max _i d_i\), and b is the sum of the initial values. \( \rho \) represents the second largest eigenvalue of a matrix of normalised molecule reachability ratios, that we analyze together with an associated Markov Chain.

We study the uniform dispersal problem (also called the filling problem) in arbitrary connected areas. In the filling problem robots are injected one-by-one at \(k \ge 1\) Doors into an unknown area, subdivided into cells. The goal is to cover the area, i.e. each cell must be occupied by a robot. The robots are homogeneous, anonymous, autonomous, have limited visibility radius, limited persistent memory, and silent, i.e. do not use explicit communication. A fundamental question is how ‘weak’ those robots can be in terms of hardware requirements and still be able to solve the problem, which was initiated by Barrameda et al. [4]. In our previous paper [11] we presented an algorithm which solves the filling problem for orthogonal areas with O(1) bits of persistent memory, 1 hop visibility range and without explicit communication. The algorithm utilized the timing of movements and had O(n) runtime, where n is the number of cells in the area. In this paper, we generalize the problem for silent robots for an arbitrary connected area represented by a graph, while maintaining the 1 hop visibility range. The algorithm is collision-free, it terminates in \(O(k \cdot \varDelta \cdot n)\) rounds, and requires \(O(\varDelta \cdot \log k)\) bits of persistent memory, where \(\varDelta \) is the maximum degree of the graph.

Telecommunication (Telco) localization is an important complementary technique of Global Position System (GPS). Traditional Telco localization approaches requires radio signal strength indicator (RSSI) of mobile devices with the connected base stations (BSs). Unfortunately, many of real-world signal measurement could miss RSSI values, and Telco operators typically will not record RSSI information, e.g., due to the major departure from current operational practices of Telco operators [6]. To address this problem, we design a novel BS ID-based coarse-to-fine Telco localization model, namely BSLoc, which requires only the connected BS IDs, time and speed information of mobile devices. BSLoc consists of two layers: (1) a sequence localization model via Hidden Markov Model (HMM) to localize the mobile devices with coarse-grained locations, and (2) a machine learning regression model with engineered features to acquire the fine-grained locations of mobile devices. Our experiments verify that, on a 2G dataset, BSLoc achieves a median error 26.0 m, which is almost comparable with two state-of-art RSSI-based techniques [9] 17.0 m and [20] 20.3 m.

In this article, the Kalman filter, Mahony filter and Madgwick filter are implemented to estimate the orientation from inertial data, using an IMU called 9 × 3 of the MoMoPa3 project which contain various sensors including a gyroscope, an accelerometer and a magnetometer, each one of them, equipped with three perpendicular axes, in the magnetometer the measurement was modified to correct the distortions by hard metals, demonstrating improvements in the accuracy of the orientation estimates. In addition, the Kinovea video analyzer software is used as reference and gold standard to calculate the Root-Mean-Square Error (RMSE) with each filter. When comparing the angles estimated by the filters with those obtained from Kinovea, it was observed that one of the filters was better in performance. The information obtained in this article can be involved in several fields of science, one of the most important in the field of medicine, helping to control Parkinson’s disease since it allows to evaluate and recognize when a patient suffers a fall or presents Freezing of the gait (FOG).