This paper establishes that random access scheduling schemes, and more specifically CSMA-CA, yield exceptionally good performance in the context of wireless multihop networks. While it is believed that CSMA-CA performs significantly worse than optimal, this belief is usually based on experiments that use rate allocation mechanisms that grossly underutilize the available capacity that random access provides. To establish our thesis, we first compare the achievable rate region of CSMA-CA and optimal in a number of carefully constructed multihop topologies and find that CSMA-CA is always within 48% of the optimal. Motivated by this result, we next characterize the worst-case performance of CSMA-CA in neighborhood topologies representing the congested regions of larger multihop topologies by deriving the neighborhood topology that yields the worst-case throughput ratio for CSMA-CA and find that in neighborhood topologies with less than 20 edges: 1) CSMA-CA is never worse than 16% of the optimal when ignoring physical-layer constraints; and 2) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal. Considering that maximal scheduling achieves much lower bounds than the above, and greedy maximal scheduling, which is one of the best known distributed approximation of an optimal scheduler, achieves similar worst-case bounds, CSMA-CA is surprisingly efficient.

Estimating link capacity in a wireless network is a complex task because the available capacity at a link is a function of not only the current arrival rate at that link, but also of the arrival rate at links which interfere with that link as well as of the nature of interference between these links. Models which accurately characterize this dependence are either too computationally complex to be useful or lack accuracy. Further, they have a high implementation overhead and make restrictive assumptions, which makes them inapplicable to real networks. In this paper, we propose CapEst, a general, simple yet accurate, measurement-based approach to estimating link capacity in a wireless network. To be computationally light, CapEst allows inaccuracy in estimation; however, using measurements, it can correct this inaccuracy in an iterative fashion and converge to the correct estimate. Our evaluation shows that CapEst always converged to within 5 percent of the correct value in less than 18 iterations. CapEst is model-independent; hence, it is applicable to any MAC/PHY layer and works with autorate adaptation. Moreover, it has a low implementation overhead, can be used with any application which requires an estimate of residual capacity on a wireless link and can be implemented completely at the network layer without any support from the underlying chipset.

This paper studies the problem of distributed computation over a network of wireless sensors. While this problem applies to many emerging applications, to keep our discussion concrete, we will focus on sensor networks used for structural health monitoring. Within this context, the heaviest computation is to determine the singular value decomposition (SVD) to extract mode shapes (eigenvectors) of a structure. Compared to collecting raw vibration data and performing SVD at a central location, computing SVD within the network can result in significantly lower energy consumption and delay. Using recent results on decomposing SVD, a well-known centralized operation, we seek to determine a near-optimal communication structure that enables the distribution of this computation and the reassembly of the final results, with the objective of minimizing energy consumption subject to a computational delay constraint. We show that this reduces to a generalized clustering problem and establish that it is NP-hard. By relaxing the delay constraint, we derive a lower bound. We then propose an integer linear program (ILP) to solve the constrained problem exactly as well as an approximate algorithm with a proven approximation ratio. We further present a distributed version of the approximate algorithm. We present both simulation and experimentation results to demonstrate the effectiveness of these algorithms .

Complex interference in static multihop wireless mesh networks can adversely affect transport protocol performance. Since TCP does not explicitly account for this, starvation and unfairness can result from the use of TCP over such networks. In this paper, we explore mechanisms for achieving fair and efficient congestion control for multihop wireless mesh networks. First, we design an AIMD-based rate-control protocol called Wireless Control Protocol (WCP), which recognizes that wireless congestion is a neighborhood phenomenon, not a node-local one, and appropriately reacts to such congestion. Second, we design a distributed rate controller that estimates the available capacity within each neighborhood and divides this capacity to contending flows, a scheme we call Wireless Control Protocol with Capacity estimation (WCPCap). Using analysis, simulations, and real deployments, we find that our designs yield rates that are both fair and efficient. WCP assigns rates inversely proportional to the number of bottlenecks a flow passes through while remaining extremely easy to implement. An idealized version of WCPCap is max-min fair, whereas a practical implementation of the scheme achieves rates within 15% of the max-min optimal rates while still being distributed and amenable to real implementation.

This paper formally establishes that random access scheduling schemes, and, more specifically CSMA-CA, yields exceptionally good performance in the context of wireless multihop networks. While it is believed that CSMA-CA performs significantly worse than optimal, this belief is usually based on experiments that use rate allocation mechanisms which grossly underutilize the available capacity that random access provides. To establish our thesis we compare the max-min rate allocation achieved by CSMA-CA and optimal in multi-hop topologies and find that: (i) CSMA-CA is never worse than 16% of the optimal when ignoring physical layer constraints, (ii) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal. Considering that maximal scheduling achieves much lower bounds than the above, and greedy maximal scheduling, which is one of the best known distributed approximation of an optimal scheduler, achieves similar worst case bounds, CSMA-CA is surprisingly efficient.

A large body of work has theoretically analyzed the performance of mobility-assisted routing schemes for intermittently connected mobile networks. But the vast majority of these prior studies have ignored wireless contention. Recent papers have shown through simulations that ignoring contention leads to inaccurate and misleading results, even for sparse networks. In this paper, we analyze the performance of routing schemes under contention. First, we introduce a mathematical framework to model contention. This framework can be used to analyze any routing scheme with any mobility and channel model. Then, we use this framework to compute the expected delays for different representative mobility-assisted routing schemes under random direction, random waypoint and community-based mobility models. Finally, we use these delay expressions to optimize the design of routing schemes while demonstrating that designing and optimizing routing schemes using analytical expressions which ignore contention can lead to suboptimal or even erroneous behavior.

Complex interference in static multi-hop wireless mesh networks can adversely affect transport protocol performance. Since TCP does not explicitly account for this, starvation and unfairness can result from the use of TCP over such networks. In this paper, we explore mechanisms for achieving fair and efficient congestion control for multi-hop wireless mesh networks. First, we design an AIMD-based rate-control protocol called Wireless Control Protocol (WCP) which recognizes that wireless congestion is a neighborhood phenomenon, not a node-local one, and appropriately reacts to such congestion. Second, we design a distributed rate controller that estimates the available capacity within each neighborhood, and divides this capacity to contending flows, a scheme we call Wireless Control Protocol with Capacity estimation (WCPCap). Using analysis, simulations, and real deployments, we find that our designs yield rates that are both fair and efficient, and achieve near optimal goodputs for all the topologies that we study. WCP achieves this level of performance while being extremely easy to implement. Moreover, WCPCap achieves the max-min rates for our topologies, while still being distributed and amenable to real implementation.

Epidemic routing has been proposed as a robust transmission scheme for sparse mobile ad hoc networks. Under the assumption of no contention, epidemic routing has the minimum end-to-end delay amongst all the routing schemes proposed for such networks. The assumption of no contention was justified by arguing that since the network is sparse, there will be very few simultaneous transmissions. Some recent papers have shown through simulations that this argument is not correct and that contention cannot be ignored while analyzing the performance of routing schemes, even in sparse networks.Incorporating contention in the analysis has always been a hard problem and hence its effect has been studied mostly through simulations only. In this paper, we find analytical expressions for the delay performance of epidemic routing with contention. We include all the three main manifestations of contention, namely (i) the finite bandwidth of the link which limits the number of packets two nodes can exchange, (ii) the scheduling of transmissions between nearby nodes which is needed to avoid excessive interference, and (iii) the interference from transmissions outside the scheduling area. The accuracy of the analysis is verified via simulations.

The physical phenomena monitored by sensor networks, for example, forest temperature or water contamination, usually yield sensed data that are strongly correlated in space. With this in mind, researchers have designed a large number of sensor network protocols and algorithms that attempt to exploit such correlations.There is an increasing need to synthetically generate large traces of spatially correlated data representing a wide range of conditions to carefully study the performance of these algorithms. Further, a mathematical model for generating synthetic traces would provide guidelines for designing more efficient algorithms. These reasons motivate us to obtain a simple and accurate model of spatially correlated sensor network data.The proposed model is Markovian in nature and can capture correlation in data irrespective of the node density, the number of source nodes, or the topology. We describe a rigorous mathematical procedure and a simple practical method to extract the model parameters from real traces. We also show how to efficiently generate synthetic traces on a given topology using these parameters. The correctness of the model is verified by statistically comparing synthetic and real data. Further, the model is validated by comparing the performance of algorithms whose behavior depends on the degree of spatial correlation in data, under real and synthetic traces. The real traces are obtained from remote sensing data, publicly available sensor data, and sensor networks that we deploy. We show that the proposed model is more general and accurate than the commonly used jointly Gaussian model. Finally, we create tools that can be easily used by researchers to synthetically generate traces of any size and degree of correlation.

The physical phenomena monitored by sensor net- works, e.g. forest temperature, usually yield sensed data that are strongly correlated in space. We have recently introduced a mathematical model for such data, and used it to generate synthetic traces and study the performance of algorithms whose behavior depends on this spatial correlation (1). That work studied sensor networks with grid topologies. This work extends our modeling methodology to sensor networks with irregular topologies. We describe a rigorous mathematical procedure and a simple practical method to extract the model parameters from real traces. We also show how to efficiently generate synthetic traces that correspond to sensor networks with arbitrary topologies using the proposed model. The correctness of the model is verified by statistically com- paring synthetic and real data. Further, the model is validated by comparing the performance of algorithms whose behavior depends on the degree of spatial correlation in data, under real and synthetic traces. The real traces are obtained from both publically available sensor data, and sensor networks that we deploy. Finally, we augment our existing trace-generation tool with new functionality suited for sensor networks with irregular topologies.

The physical phenomena monitored by sensor networks, e.g. forest temperature, water contamination, usually yield sensed data that are strongly correlated in space. With this in mind, researchers have designed a large number of sensor network protocols and algorithms that attempt to exploit such correlations. To carefully study the performance of these algorithms, there is an increasing need to synthetically generate large traces of spatially correlated data representing a wide range of conditions. Further, a mathematical model for generating synthetic traces would provide guidelines for designing more efficient algorithms. These reasons motivate us to obtain a simple and accurate model of spatially correlated sensor network data. The model can capture correlation in data irrespective of the node density, the number of source nodes or the topology. We describe a mathematical procedure to extract the model parameters from real traces and generate synthetic traces using these parameters. Then, we validate our model by statistically comparing synthetic data and experimental data, as well as by comparing the performance of various algorithms whose performance depends on the degree of spatial correlation. Finally, we create a tool that can be easily used by researchers to synthetically generate traces of any size and degree of correlation.

Wireless sensor networks are characterized by dense deployment of sensor nodes which collectively communicate sensed data to the sink. However, due to the spatial correlation between sensor observations, it is not necessary for every node to transmit its data. We propose a clustering method which exploits the above observation. We do not make any assumption on the nature of data, and hence the algorithm will be valid for a broad range of conditions. The paper shows how to calculate the optimal cluster size. We also discuss the structure of the complete architecture which is still under development.