Dynamic connectivity and path formation time in Poisson networks

The connectivity of wireless networks is commonly analyzed using static geometric graphs. However, with half-duplex radios and due to interference, static or instantaneous connectivity cannot be achieved. It is not necessary, either, since packets take multiple time slots to propagate through the network. For example, if a packet traverses a link in one time slot, it is irrelevant if the next link is available in that time slot also, but it is relevant if the next hop exists in the next time slot. To account for half-duplex constraints and the dynamic changes in the transmitting set of nodes due to MAC scheduling and traffic loads, we introduce a random multi-digraph that captures the evolution of the network connectivity in a dynamic fashion. To obtain concrete results, we focus on Poisson networks, where transmitters form a Poisson point process on the plane at all time instants. We first provide analytical results for the degree distribution of the graph and derive the distributional properties of the end-to-end connection delay using techniques from first-passage percolation and epidemic processes. Next, we prove that under some assumptions, the delay scales linearly with the source–destination distance even in the presence of interference. We also provide simulation results in support of the theoretical results.     

Stochastic Geometry and Random Graphs for the Analysis and Design of Wireless Networks

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 network?s 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.     

Spatial and temporal correlation of the interference in ALOHA ad hoc networks

Interference is a main limiting factor of the performance of a wireless ad hoc network. The temporal and the spatial correlation of the interference makes the outages correlated temporally (important for retransmissions) and spatially correlated (important for routing). In this letter we quantify the temporal and spatial correlation of the interference in a wireless ad hoc network whose nodes are distributed as a Poisson point process on the plane when ALOHA is used as the multiple-access scheme.     

Design of a wireless assisted pedestrian dead reckoning system - the NavMote experience

In this paper, we combine inertial sensing and sensor network technology to create a pedestrian dead reckoning system. The core of the system is a lightweight sensor-and-wireless-embedded device called NavMote that is carried by a pedestrian. The NavMote gathers information about pedestrian motion from an integrated magnetic compass and accelerometers. When the NavMote comes within range of a sensor network (composed of NetMotes), it downloads the compressed data to the network. The network relays the data via a RelayMote to an information center where the data are processed into an estimate of the pedestrian trajectory based on a dead reckoning algorithm. System details including the NavMote hardware/software, sensor network middleware services, and the dead reckoning algorithm are provided. In particular, simple but effective step detection and step length estimation methods are implemented in order to reduce computation, memory, and communication requirements on the Motes. Static and dynamic calibrations of the compass data are crucial to compensate the heading errors. The dead reckoning performance is further enhanced by wireless telemetry and map matching. Extensive testing results show that satisfactory tracking performance with relatively long operational time is achieved. The paper also serves as a brief survey on pedestrian navigation systems, sensors, and techniques.     

Bandwidth- and power-efficient routing in linear wireless networks

The goal of this paper is to establish which practical routing schemes for wireless networks are most suitable for power-limited and bandwidth-limited communication regimes. We regard channel state information (CSI) at the receiver and point-to-point capacity-achieving codes for the additive white Gaussian noise (AWGN) channel as practical features, interference cancellation (IC) as possible, but less practical, and synchronous cooperation (CSI at the transmitters) as impractical. We consider a communication network with a single source node, a single destination node, and N-1 intermediate nodes placed equidistantly on a line between them. We analyze the minimum total transmit power needed to achieve a desired end-to-end rate for several schemes and demonstrate that multihop communication with spatial reuse performs very well in the power-limited regime, even without IC. However, within a class of schemes not performing IC, single-hop transmission (directly from source to destination) is more suitable for the bandwidth-limited regime, especially when higher spectral efficiencies are required. At such higher spectral efficiencies, the gap between single-hop and multihop can be closed by employing IC, and we present a scheme based upon backward decoding that can remove all interference from the multihop system with an arbitrarily small rate loss. This new scheme is also used to demonstrate that rates of O(logN) are achievable over linear wireless networks even without synchronous cooperation.     

Geometric analysis of distributed power control and Möbius MAC design

This paper presents a geometric analysis of the convergence condition for the Foschini–Miljanic power control algorithm. The Möbius transform is exploited for the first time to analyze the convergence condition of the power control algorithm. A novel MAC scheme based on the Möbius transform is proposed for the link scheduling problem and proven to improve spatial reuse by scheduling links in pairs if possible. The peak power constraint of wireless networks is analyzed theoretically, and applications to random networks are explored in detail. Observations from the analysis of peak power constraints are also applied to the design of the MAC scheme (Möbius MAC) to improve the convergence speed and system performance. Simulation results show that our Möbius MAC can roughly double the performance of CSMA in terms of transport density. Applications to cognitive networks and heterogeneous networks are discussed. Copyright © 2014 John Wiley & Sons, Ltd.     

Rethinking information theory for mobile ad hoc networks

The subject of this article is the long standing open problem of developing a general capacity theory for wireless networks, particularly a theory capable of describing the fundamental performance limits of mobile ad hoc networks. A MANET is a peer-to-peer network with no preexisting infrastructure. MANETs are the most general wireless networks, with single-hop, relay, interference, mesh, and star networks comprising special cases. The lack of a MANET capacity theory has stunted the development and commercialization of many types of wireless networks, including emergency, military, sensor, and community mesh networks. Information theory, which has been vital for links and centralized networks, has not been successfully applied to decentralized wireless networks. Even if this was accomplished, for such a theory to truly characterize the limits of deployed MANETs it must overcome three key roadblocks. First, most current capacity results rely on the allowance of unbounded delay and reliability. Second, spatial and timescale decompositions have not yet been developed for optimally modeling the spatial and temporal dynamics of wireless networks. Third, a useful network capacity theory must integrate rather than ignore the important role of overhead messaging and feedback. This article describes some of the shifts in thinking that may be needed to overcome these roadblocks and develop a more general theory.     

Analogy between data networks and electric networks

It is shown that two fundamental laws, Ohm's law in electric circuits and Little's theorem for queueing systems, are highly analogous. For both single nodes and networks, there is a striking equivalence between the two laws that facilitates the teaching and understanding of the related concepts of current flow in a resistor network and data flow in a communication network     

Analysis and design of diversity schemes for ad hoc wireless networks

Diversity schemes permit efficient communication over fading channels but are often hard to analyze and design in networks with many nodes. For Rayleigh-fading channels, there exists an interesting relationship between resistive circuits and time and path diversity mechanisms in wireless ad hoc networks. A resistor-like network element, the erristor, representing the normalized noise-to-signal ratio, is introduced. Given an end-to-end packet delivery probability, the logarithmic mapping from link reception probabilities to erristor values greatly simplifies the problems of power allocation and the selection of time and path diversity schemes, which is illustrated in a number of examples. We focus on transmission strategies with selection combining and simple noncoherent "decode-and-forward" strategies, which is motivated by their practicality. Thanks to its conceptual simplicity, the formalism that is developed provides valuable insight into the benefits of diversity mechanisms.