Consider a set of probes, called “agents”, who sample, based on opportunistic contacts, a population moving between a set of discrete locations. An example of such agents are Bluetooth probes that sample the visible Bluetooth devices in a population. Based on the obtained measurements, we construct a parametric statistical model to jointly estimate the total population size (e.g., the number of visible Bluetooth devices) and their spatial density. We evaluate the performance of our estimators by using Bluetooth traces obtained during an open-air event and Wi-Fi traces obtained on a university campus.

We study the dynamic aspects of the coverage of a mobile sensor network resulting from continuous movement of sensors. As sensors move around, initially uncovered locations may be covered at a later time, and intruders that might never be detected in a stationary sensor network can now be detected by moving sensors. However, this improvement in coverage is achieved at the cost that a location is covered only part of the time, alternating between covered and not covered. We characterize area coverage at specific time instants and during time intervals, as well as the time durations that a location is covered and uncovered. We further consider the time it takes to detect a randomly located intruder and prove that the detection time is exponentially distributed with parameter 2\lambda r \bar{v}_s where \lambda represents the sensor density, r represents the sensor's sensing range, and \bar{v}_s denotes the average sensor speed. For mobile intruders, we take a game theoretic approach and derive optimal mobility strategies for both sensors and intruders. We prove that the optimal sensor strategy is to choose their directions uniformly at random between [0, 2\pi ). The optimal intruder strategy is to remain stationary. This solution represents a mixed strategy which is a Nash equilibrium of the zero-sum game between mobile sensors and intruders.

The connectivity graph of wireless networks, under many models as well as in practice, may contain unidirectional links. The simplifying assumption that such links are useless is often made, mainly because most wireless protocols use per-hop acknowledgments. However, two-way communication between a pair of nodes can be established as soon as there exists paths in both directions between them. Therefore, instead of discarding unidirectional links, one might be interested in studying the strongly connected components of the connectivity graph. In this paper, we look at the percolation phenomenon in some directed random geometric graphs that can be used to model wireless networks. We show that among the nodes that can be reached from the origin, a non-zero fraction can also reach the origin. In other words, the percolation threshold for strong connectivity is equal to the threshold for one-way connectivity.

Most current mobile devices are able to determine their location, which has become part of the contextual information available to applications. However, in many cases, the exact position of the device in terms of longitude and latitude is not necessary. On the contrary, applications might benefit more from a discrete context variable that indicates the ``place'' in which the device currently is. To realize this, the continuous device's trajectory needs to be clustered into discrete locations. Besides, the device's location is often not measured directly, but rather inferred from other measurements, such as the list of available WiFi access points. Since similar WiFi measurements lead to similar estimates of the position, it appears that the conversion into geographical coordinates is an unnecessary step in the identification of places. In this paper, we describe a density-based clustering approach that allows to learn significant places directly from a set of raw WiFi measurements.

We conduct an experiment where ten attendees of an open-air music festival are acting as Bluetooth probes. We then construct a parametric statistical model to estimate the total number of visible Bluetooth devices in the festival area. By comparing our estimate with ground truth information provided by probes at the entrances of the festival, we show that the total population can be estimated with a surprisingly low error (1.26% in our experiment), given the small number of agents compared to the area of the festival and the fact that they are regular attendees who move randomly. Also, our statistical model can easily be adapted to obtain more detailed estimates, such as the evolution of the population size over time.

We show that CSMA is able to spontaneously synchronize transmissions in a wireless network with constant-size packets, and that this property can be used to devise efficient synchronized CSMA scheduling mechanisms without message passing. Using tools from queuing theory, we prove that for any connected wireless networks with arbitrary interference constraints, it is possible to implement self-synchronizing TDMA schedules without any explicit message passing or clock synchronization besides transmitting the original data packets, and the interaction can be fully local in that each node decides when to transmit next only by overhearing its neighbors' transmissions. We also provide a necessary and sufficient condition on the emergence of self-synchronization for a given TDMA schedule, and prove that such conditions for self-synchronization can be checked in a finite number of steps for a finite network topology.

Wireless networks are fundamentally limited by the intensity of the received signals and by their interference. Since both of these quantities depend on the spatial location of the nodes, mathematical techniques have been developed in the last decade to provide communication-theoretic results accounting for the networks geometrical configuration. Often, the location of the nodes in the network can be modeled as random, following for example a Poisson point process. In this case, different techniques based on stochastic geometry and the theory of random geometric graphs -including point process theory, percolation theory, and probabilistic combinatorics-have led to results on the connectivity, the capacity, the outage probability, and other fundamental limits of wireless networks. This tutorial article surveys some of these techniques, discusses their application to model wireless networks, and presents some of the main results that have appeared in the literature. It also serves as an introduction to the field for the other papers in this special issue.

We characterize the fairness of decentralized medium access control protocols based on CSMA/CA, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of these protocols in small network topologies does not always persist in large topologies. In regular networks, this unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel. In large 1D lattice networks these border effects do not propagate inside the network, and nodes sufficiently far away from the border have equal access to the channel; as a result the protocol is long-term fair. In 2D lattice networks, we observe a phase transition. If the access intensity of the protocol is small, the border effects remain local and the protocol behaves similarly as in one-dimensional networks. However, if the access intensity of the protocol is large enough, the border effects persist independently of the size of the network and the protocol is strongly unfair. In irregular networks, the topology is inherently unfair. This unfairness increases with the access intensity of the protocol, but in a much smoother way than in regular two-dimensional networks. Finally, in situations where the protocol is long-term fair, we provide a characterization of its short-term fairness.

The one tutorial and 22 papers in this special issue focus on geometry and random graph for the analysis and design of wireless networks. The papers are organized into five groups: Topology; Outage, throughput, capacity, and scaling laws; Connectivity and coverage; Co-existence of disparate wireless networks and cognitive radio; and Distributed algorithms.

Decentralized medium access control schemes for wireless networks based on CSMA/CA, such as the IEEE 802.11 protocol, are known to be unfair. In multihop networks, they can even favor some links to such an extent that the others suffer from virtually complete starvation. This observation has been reported in quite a few works, but the factors causing it are still not well understood. We find that the capture effect and the relative values of the receive and carrier sensing ranges play a crucial role in the performance of these protocols. Using a simple Markovian model, we show that an idealized CSMA/CA protocol suffers from starvation when the receiving and sensing ranges are equal, but quite surprisingly that this unfairness is reduced or even disappears when these two ranges are sufficiently different. We also show that starvation has a positive counterpart, namely organization. When its access intensity is large the protocol organizes the transmissions in space in such a way that it maximizes the number of concurrent successful transmissions. We obtain exact formula for the so-called spatial reuse of the protocol on large line networks.

We characterize the fairness of decentralized medium access control protocols based on CSMA/CA, such as IEEE 802.11, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of the protocol in small network topologies does not always persist in large topologies. This unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel. In large one-dimensional networks these border effects do not propagate inside the network, and nodes sufficiently far away from the border have equal access to the channel; as a result the protocol is long-term fair. In two-dimensional networks, we observe a phase transition. If the access intensity of the protocol is small, the border effects remain local and the protocol behaves similarly as in one- dimensional networks. However, if the access intensity of the protocol is large enough, the border effects persist independently of the size of the network and the protocol is strongly unfair. Finally, in situations where the protocol is long-term fair, we provide a characterization of its short-term fairness.

Constructing sensor barriers to detect intruders crossing a randomly-deployed sensor network is an important problem. Early results have shown how to construct sensor barriers to detect intruders moving along restricted crossing paths in rectangular areas. We present a complete solution to this problem for sensors that are distributed according to a Poisson point process. In particular, we present an efficient distributed algorithm to construct sensor barriers on long strip areas of irregular shape without any constraint on crossing paths. Our approach is as follows: We first show that in a rectangular area of width w and length l with w = Ω(log l), if the sensor density reaches a certain value, then there exist, with high probability, multiple disjoint sensor barriers across the entire length of the area such that intruders cannot cross the area undetected. On the other hand, if w = o(log l), then with high probability there is a crossing path not covered by any sensor regardless of the sensor density. We then devise, based on this result, an efficient distributed algorithm to construct multiple disjoint barriers in a large sensor network to cover a long boundary area of an irregular shape. Our algorithm approximates the area by dividing it into horizontal rectangular segments interleaved by vertical thin strips. Each segment and vertical strip independently computes the barriers in its own area. Constructing "horizontal" barriers in each segment connected by "vertical" barriers in neighboring vertical strips, we achieve continuous barrier coverage for the whole region. Our approach significantly reduces delay, communication overhead, and computation costs compared to centralized approaches. Finally, we implement our algorithm and carry out a number of experiments to demonstrate the effectiveness of constructing barrier coverage.

Decentralized medium access control schemes for wireless networks based on CSMA/CA, such as the 802.11 protocol, are known to be unfair. In multi-hop networks, they can even favor some connections to such an extent that the others suffer from virtually complete starvation. This observation has been reported in quite a few works, but the factors causing it are still not well understood. We find that the capture effect and the relative values of the receiving and carrier sensing ranges play a crucial role in the unfairness of these protocols. We show that an idealized 802.11 protocol does suffer from starvation when the receiving and sensing ranges are equal, but quite surprisingly this unfairness is reduced or even disappears when these two ranges are sufficiently different. Using a Markovian model, we explain why apparently benign variations in these ranges have such a dramatic impact on the 802.11 protocol performance.

An achievable bit rate per source-destination pair in a wireless network of n randomly located nodes is determined adopting the scaling limit approach of statistical physics. It is shown that randomly scattered nodes can achieve, with high probability, the same 1/radicn transmission rate of arbitrarily located nodes. This contrasts with previous results suggesting that a 1/radicnlogn reduced rate is the price to pay for the randomness due to the location of the nodes. The network operation strategy to achieve the result corresponds to the transition region between order and disorder of an underlying percolation model. If nodes are allowed to transmit over large distances, then paths of connected nodes that cross the entire network area can be easily found, but these generate excessive interference. If nodes transmit over short distances, then such crossing paths do not exist. Percolation theory ensures that crossing paths form in the transition region between these two extreme scenarios. Nodes along these paths are used as a backbone, relaying data for other nodes, and can transport the total amount of information generated by all the sources. A lower bound on the achievable bit rate is then obtained by performing pairwise coding and decoding at each hop along the paths, and using a time division multiple access scheme

In this paper we consider sensor networks for intrusion detection, such that node deployment, node failures and node behavior result in coverage gaps and a fraction of disconnected nodes in an otherwise dense and well-connected network. We focus on the time delay for a mobile intruder to be detected by a sensor with a connected path to the sink, in contrast to existing results for the detection time by a sensor with arbitrary connectivity. We model our network using a supercritical percolation model on the plane, implying the existence of a unique unbounded connected component, and we assume that the sink belongs to this component. We analyze the distribution of the distance traveled by a moving target until it comes within sensing range of a node in the giant component, providing analytical bounds for linear intruder mobility and thorough simulation results for other mobility models. We show that the probability that the intruder proceeds undetected exhibits non-memoryless behavior over shorter distances and an exponentially decreasing tail. We also show that the time of contact with the giant component incurs considerably more delay than the time of first contact with any node, in networks with less than 10% of nodes without a path to the sink, which means that even a small percentage of node failures may have a drastic impact on the performance of intrusion detection by a wireless sensor networ.

The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional (2-D) network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. As a converse bound, we show that communications occurring at a fixed nonzero rate imply a fraction of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.

The throughput of wireless networks is known to scale poorly when the number of users grows. The rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. One of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. We show that this requirement can be responsible for the lack of throughput scalability. We consider a two-dimensional network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. Allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. This result relies on percolation theory arguments and does not hold for one-dimensional networks, where a non-vanishing rate is impossible even if we allow an arbitrary large fraction of nodes to be disconnected. A converse bound is obtained using an ergodic property of shot noises. We show that communications occurring at a fixed nonzero rate imply a fraction of the nodes to be disconnected. Our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.

Previous work on the coverage of mobile sensor networks focuses on algorithms to reposition sensors in order to achieve a static configuration with an enlarged covered area. In this paper, we study the dynamic aspects of the coverage of a mobile sensor network that depend on the process of sensor movement. As time goes by, a position is more likely to be covered; targets that might never be detected in a stationary sensor network can now be detected by moving sensors. We characterize the area coverage at specific time instants and during time intervals, as well as the time it takes to detect a randomly located stationary target. Our results show that sensor mobility can be exploited to compensate for the lack of sensors and improve network coverage. For mobile targets, we take a game theoretic approach and derive optimal mobility strategies for sensors and targets from their own perspectives.

We study the impact of interferences on the connectivity of large-scale ad hoc networks, using percolation theory. We assume that a bi-directional connection can be set up between two nodes if the signal to noise ratio at the receiver is larger than some threshold. The noise is the sum of the contribution of interferences from all other nodes, weighted by a coefficient /spl gamma/, and of a background noise. We find that there is a critical value of /spl gamma/ above which the network is made of disconnected clusters of nodes. We also prove that if /spl gamma/ is nonzero but small enough, there exist node spatial densities for which the network contains a large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops. Since small values of /spl gamma/ cannot be achieved without efficient CDMA codes, we investigate the use of a very simple TDMA scheme, where nodes can emit only every nth time slot. We show that it achieves connectivity similar to the previous system with a parameter /spl gamma//n.

We study the connectivity and capacity of finite area ad hoc wireless networks, with an increasing number of nodes (dense networks). We find that the properties of the network strongly depend on the shape of the attenuation function. For power law attenuation functions, connectivity scales, and the available rate per node is known to decrease like 1//spl radic/n. On the contrary, if the attenuation function does not have a singularity at the origin and is uniformly bounded, we obtain bounds on the percolation domain for large node densities, which show that either the network becomes disconnected, or the available rate per node decreases like 1/n.

We consider the problem of how throughput in a wireless network with randomly located nodes scales as the number of users grows. Following the physical model of Gupta and Kumar, we show that randomly scattered nodes can achieve the optimal 1/(n)/sup 1/2/ per-node transmission rate of arbitrarily located nodes. This contrasts with previous achievable results suggesting that a 1/(n log n)/sup 1/2/ reduced rate is the price to pay for the additional randomness introduced into the system. Our results rely on percolation theory arguments. In the high density regime the network is fully connected but generates excessive interference. In the low density regime the network loses connectivity. Percolation theory ensures that a wireless backbone forms in the transition region between this two extreme scalings. This backbone does not cover all the nodes, nevertheless it is sufficiently rich in crossing paths so that it can transport all the traffic in the network. By operating the network in this transition region between order and disorder, we are able to prove our tight bound.

We consider a wireless sensor network, where nodes switch between an active (on) and a sleeping (off) mode, to save energy. Their switching on/off schedules are completely non-coordinated. Their positions are distributed according to a Poisson process, and their connectivity range is larger or equal to their sensing range. The durations of active and sleeping periods are such that the number of active nodes at any particular time is so low that the network is always disconnected. Is it possible to use such a network for time-critical monitoring of an area? Such a scenario requires indeed to have bounds on the latency, which is the delay elapsed between the time at which an incoming event is sensed by some node of the network, and the time at which this information is retrieved by the data collecting sink. A positive answer is provided to this question under some assumptions discussed in the paper. More precisely, we prove that the messages sent by a sensing node reach the sink with a fixed asymptotic speed, which does not depend on the random location of the nodes, but only on the network parameters (node density, connectivity range, duration of active and sleeping periods). The results are obtained rigorously by using an extension of first passage percolation theory.

The impact of interferences on the connectivity of large-scale ad-hoc networks is studied using percolation theory. We assume that a bi-directional connection can be set up between two nodes if the signal to noise ratio at the receiver is larger than some threshold. The noise is the sum of the contribution of interferences from all other nodes, weighted by a coefficient /spl gamma/, and of a background noise. We find that there is a critical value of /spl gamma/ above which the network is made of disconnected clusters of nodes. We also prove that if /spl gamma/ is nonzero but small enough, there exist node spatial densities for which the network contains a large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops. Since small values of /spl gamma/ cannot be achieved without efficient CDMA codes, we investigate the use of a very simple TDMA scheme, where nodes can emit only every n-th time slot. We show qualitatively that it even achieves a better connectivity than the previous system with a parameter /spl gamma//n.

We consider a large-scale wireless network, but with a low density of nodes per unit area. Interferences are then less critical, contrary to connectivity. This paper studies the latter property for both a purely ad-hoc network and a hybrid network, where fixed base stations can be reached in multiple hops. We assume here that power constraints are modeled by a maximal distance above which two nodes are not (directly) connected. We find that the introduction of a sparse network of base stations does significantly help in increasing the connectivity, but only when the node density is much larger in one dimension than in the other. We explain the results by percolation theory. We obtain analytical expressions of the probability of connectivity in the 1D case. We also show that at a low spatial density of nodes, bottlenecks are unavoidable. Results obtained on actual population data confirm our findings.