The localization of devices is a key ingredient of Internet of Things (IoT). However, localization requires deploying many anchor nodes that are nodes whose location is known a-priori. Anchor nodes are expensive and their utilization may be unfeasible in some cases, such as in search-and-rescue operations. In this work, we propose a range-free localization algorithm that replaces the anchor nodes with an off-the-shelf drone. During the mission, the drone scans the deployment area and regularly broadcasts a beacon consisting of the current drone's position projected on the ground. The sensors simply listen to the drone until they hear three special beacons and, after that, they locally compute their position. Our algorithm is able to ensure any user-defined localization precision just varying the distance betweenthe beacons. Differently from the other range-based localization algorithms proposed for drones, our algorithm guarantees the localization precision without requiring any specific hardware technology, except the ability to communicate. Since our algorithm does not take any measure, the height of the drone only affect the receiving area of the sensor. Due to the simplicity of the interaction between the drone and the sensors during the algorithm, this solution can localize very high dense networks, even using a slightly shorter drone's trajectory than the previous algorithms.

Radio networks (RN) are distributed systems consisting in n active stations. Assuming the number n unknown, we consider the model of RN without collision detection and design distributed randomized protocol that allows to compute a stochastic estimate N of the number n of active stations. Our algorithms are shown to run in expected time O(log n) with no station being awake for more than O(log log n) time slots. Our protocols can be parametrized in such a way that they end with all participants being aware of the value of N whose expectation can be made arbitrarily close to n.

We analyze the cost used by a naive exhaustive search algorithm for finding a maximum independent set in random graphs under the usual $\mathscr{G}_{n,p}$-model where each possible edge appears independently with the same probability $p$. The expected cost turns out to be of the less common asymptotic order $n^{c\log n}$, which we explore from several different perspectives. Also we collect many instances where such an order appears, from algorithmics to analysis, from probability to algebra. The limiting distribution of the cost required by the algorithm under a purely idealized random model is proved to be normal. The approach we develop is of some generality and is amenable for other graph algorithms.

A k-cut of a graph G = (V, E) is a partition of its vertex set into k parts; the size of the k-cut is the number of edges with endpoints in distinct parts. MAX-k-CUT is the optimization problem of finding a k-cut of maximal size and the case where k = 2 (often called MAX-CUT) has attracted a lot of attention from the research community. MAX-CUT—more generally, MAX-k-CUT— is NP-hard and it appears in many applications under various disguises. In this paper, we consider the MAX-CUT problem on random connected graphs ℂ(n, m) and on Erdős-Rényi random graphs G(n, m). More specifically, we consider the distance from bipartiteness of a graph G = (V, E), the minimum number of edge deletions needed to turn it into a bipartite graph. If we denote this distance DistBip(G), the size of the MAX-CUT of a graph G = (V, E) is clearly given by |E| − DistBip(G). Fix ε > 0. For random connected graphs, we prove that asymptotically almost surely (a.a.s) (DistBip whenever m = n + O(n1−ε). For sparse random graphs we show that DistBip ( (n, m)) is a.a.s about .

In this work, we consider a large-scale geographic area populated by tiny sensors and some more powerful devices called actors, authorized to organize the sensors in their vicinity into short-lived, actor-centric sensor networks. The tiny sensors run on miniature nonrechargeable batteries, are anonymous, and are unaware of their location. The sensors differ in their ability to dynamically alter their sleep times. Indeed, the periodic sensors have sleep periods of predefined lengths, established at fabrication time; by contrast, the free sensors can dynamically alter their sleep periods, under program control. The main contribution of this work is to propose an energy-efficient location training protocol for heterogeneous actor-centric sensor networks where the sensors acquire coarse-grain location awareness with respect to the actor in their vicinity. Our theoretical analysis, confirmed by experimental evaluation, shows that the proposed protocol outperforms the best previously known location training protocols in terms of the number of sleep/awake transitions, overall sensor awake time, and energy consumption.

Exploiting high density features of wireless sensor networks represents a challenging issue. In this context, anonymous, asynchronous and randomly distributed sensors are considered along with few devices, called actors, which are more powerful than sensors in terms of energy and transmission capabilities. The paper proposes a new distributed training protocol for coarse-grain localization purposes in high density environments. The aim is to auto-organize the sensors with respect to a virtual infrastructure centered at actors and constituted of concentric rings divided into sectors. Analytical study as well as experiments on the proposed protocol are provided. The obtained results show under which theoretical and practical settings the training process can be performed in a fast and high quality way with respect to the granularity of the required localization and the energy consumption.

In this paper, we investigate the fundamental limits of sensor network lifetime that any algorithm can achieve. In our settings, n nodes are deployed as a Poisson point process with density lambda in a region of size S and each sensor node can cover a unit-area disk. For any k and lambda, let V(k, lambda) be the random variable (r.v.) of the size of the region that is covered by at most k - 1 nodes. Under these assumptions, we first show that for any function omega satisfying 1 Gtomega (k) Lt k1/2the r.v. V(k, k- omega(k)k1/2) converges almost surely to S. In contrast, if the intensity is set to lambda = k + omega(k)k1/2we obtain that V(k, k +omega(k)k1/2) converges almost surely to 0. These limit theorems extend the results of Zhang and Hou in [21], [22] where the authors worked with fixed degree of coverage (k = O(1)) and lambda = log S+O(k) log log S. Assume that each sensor has the same lifetime T. As consequences of our analytical results, we derive randomized algorithms (working with high probability) that can maintain constantly high degrees of coverage while prolonging the lifetime of the network.

We analyze various critical transmitting/sensing ranges for connectivity and coverage in three-dimensional sensor networks. As in other large-scale complex systems, many global parameters of sensor networks undergo phase transitions. For a given property of the network, there is a critical threshold, corresponding to the minimum amount of the communication effort or power expenditure by individual nodes, above (respectively, below) which the property exists with high (respectively, a low) probability. For sensor networks, properties of interest include simple and multiple degrees of connectivity/coverage. First, we investigate the network topology according to the region of deployment, the number of deployed sensors, and their transmitting/sensing ranges. More specifically, we consider the following problems: assume that n nodes, each capable of sensing events within a radius of r, are randomly and uniformly distributed in a 3-dimensional region R of volume V, how large must the sensing range R/sub SENSE/ be to ensure a given degree of coverage of the region to monitor? For a given transmission range R/sub TRANS/, what is the minimum (respectively, maximum) degree of the network? What is then the typical hop diameter of the underlying network? Next, we show how these results affect algorithmic aspects of the network by designing specific distributed protocols for sensor networks.

Abstract We propose two randomized protocols by which n (n not known) initially identical stations of a Packet Radio Network (PRN) are assigned ID numbers from 1 to n to distinguish them. They run regardless of the number of stations per channel. The first one is a naive protocol and is derived from recursive probabilistic divide‐and‐conquer techniques. It requires n/lnk broadcast rounds, where k is the number of communication channels. The second solution needs the well‐known prefix sums algorithm and we show that in this scenario the described protocol terminates in O(n/k) broadcast rounds on the average case whenever k ≤ n/lnn. These results are obtained by means of the average case analysis of algorithms, using probabilistic generating functions and formal methods. Surprisingly, our last protocol performs as well as the efficiency‐oriented protocol of Hayashi et al. in 1 , 2 , which depends on the number of stations per channel. And moreover, it can handle the case where k∈[n/3lnn, n/lnn]. Copyright © 2003 John Wiley & Sons, Ltd.