In this paper, we consider CSMA policies for scheduling packet transmissions in multihop wireless networks with one-hop traffic. The main contribution of the paper is to propose a novel CSMA policy, called Unlocking CSMA (U-CSMA), that enables to obtain both high throughput and low packet delays in large wireless networks. More precisely, we show that for torus interference graph topologies with one-hop traffic, U-CSMA is throughput optimal and achieves order-optimal delay. For one-hop traffic, the delay performance is defined to be order-optimal if the delay stays bounded as the network-size increases. Simulations that we conducted suggest that (a) U-CSMA is throughput-optimal and achieves order-optimal delay for general geometric interference graphs and (b) that U-CSMA can be combined with congestion control algorithms to maximize the network-wide utility and obtain order-optimal delay. To the best of our knowledge, this is the first time that a simple distributed scheduling policy has been proposed that is both throughput/utility optimal and achieves order-optimal delay.

In this paper, we consider the problem of optimal control for throughput utility maximization in cognitive radio networks with dynamic user arrivals and departures. The cognitive radio network considered in this paper consists of a number of heterogeneous sub-networks. These sub-networks may be power-constrained and are required to operate in such a way that the average total interference received on primary channels are kept below given thresholds. We develop a control policy that performs joint admission control and resource scheduling. Through Lyapunov optimization techniques, we show that the proposed policy achieves a utility performance within O(¿) of optimality for any positive ¿. We further show that this arbitrarily closeness to optimality comes at the price of having a delay that is O(1/¿) in admitting users. We also propose constant factor approximations of the policy for distributed implementation.

It is well known that the generalized max-weight matching (GMWM) scheduling policy, and in general throughput-optimal scheduling policies, often require the solution of a complex optimization problem, making their implementation prohibitively difficult in practice. This has motivated many researchers to develop distributed sub-optimal algorithms that approximate the GMWM policy. One major assumption commonly shared in this context is that the time required to find an appropriate schedule vector is negligible compared to the length of a timeslot. This assumption may not be accurate as the time to find schedule vectors usually increases polynomially with the network size. On the other hand, we intuitively expect that for many sub-optimal algorithms, the schedule vector found becomes a better estimate of the one returned by the GMWM policy as more time is given to the algorithm. We thus, in this paper, consider the problem of scheduling from a new perspective through which we carefully incorporate channel variations and time-efficiency of sub-optimal algorithms into the scheduler design. Specifically, we propose a dynamic control policy (DCP) that works on top of a given sub-optimal algorithm, and dynamically but in a large time-scale adjusts the time given to the algorithm according to queue backlog and channel correlations. This policy does not require the knowledge of the structure of the given sub-optimal algorithm, and with low-overhead can be implemented in a distributed manner. Using a novel Lyapunov analysis, we characterize the stability region induced by DCP, and show that our characterization can be tight. We also show that the stability region of DCP is at least as large as the one for any other static policy. Finally, we provide two case studies to gain further intuition into the performance of DCP.

Recently wireless sensor networks featuring direct sink access have been studied as an efficient architecture to gather and process data for numerous applications. We focus on the joint effect of clustering and data correlation on the performance of such networks. We propose a novel cluster-based data collection scheme for sensor networks with direct sink access (CDC-DSA), and provide an analytical framework to evaluate its performance in terms of energy consumption, latency, and robustness. In our scheme, CHs use a low-overhead and simple medium access control (MAC) conceptually similar to ALOHA to contend for the reachback channel to the data sink. Since in our model data is collected periodically, the packet arrival is not modeled by a continuous random process and, therefore, our framework is based on transient analysis rather than a steady state analysis. Using random geometry tools, we study how the optimal average cluster size and energy savings vary in a response to various data correlation levels under the proposed MAC. Extensive simulations for various protocol parameters show that our analysis is fairly accurate for a wide range of parameters. Our results suggest that despite the tradeoff between energy consumption and latency, both of which can be substantially reduced by proper clustering design.

Throughput optimal scheduling policies in general require the solution of a complex optimization problem. The past literature has shown that the complexity of this optimization problem can be greatly reduced, but at the expense of memory requirement that is exponential with the number of users. In this paper, we study the stability region of a class of linear-memory scheduling policies for time varying channels, and investigate how the channel memory impacts the supportable input rates. The set of scheduling policies in this paper covers a wide spectrum of resource allocation algorithms, which allows us to study policies with different complexity levels. In particular, we are able to model a class of low-complexity scheduling policies with linear memory, which are suitable for practical implementation.

Wireless sensor networks with mobile access points are effective tools for collecting data in a variety of environments. Mobile agents are powerful hardware units with sophisticated transceivers. Low-cost and low-power sensors in the reachback operation contend for the channel to transmit their own data packets to the mobile agent. This data communication should be designed to ensure energy efficiency and low latency. We propose a clustering scheme for wireless sensor networks with reachback mobile agents (C-SENMA). C-SENMA groups sensors into clusters such that nodes communicate only with the nearest clusterhead (CH) and the CH takes the task of data aggregation and communication with the mobile agent. CHs use a low-overhead medium access control (MAC) mechanism, similar to the conventional ALOHA, to contend for the channel. Using results from random geometry theory, we analyze the clustering performance under the realistic MAC algorithm. Our analysis enables us to obtain the optimal average cluster size which minimizes energy consumption. We justify our analysis results by extensive simulations according to various clustering parameters. Furthermore, we study the effect of underlying physical layer characteristics on the amount of energy reduction achievable by the proposed clustering architecture.

In wireless sensor networks, clustering allows the aggregation of sensor data. It is well known that leveraging the correlation between different samples of the observed data will lead to better utilization of energy reserve. However, no previous work has analyzed the effect of non-ideal data aggregation in multi-hop sensor networks. In this paper, we propose a novel analytical framework to study how partially correlated data affect the performance of clustering algorithms. We analyze the behavior of multi-hop routing and, by combining random geometry techniques and rate distortion theory, predict the total energy consumption and network lifetime. We show that when a moderate amount of correlation is available, the optimal probabilities that lead to minimum energy consumption are far from optimality in terms of network lifetime. In addition, we study the sensitivity of the total energy consumption and network lifetime to the amount of correlation and compression distortion constraint.