The distributed coordination function (DCF) for 802.11 medium access control (MAC) leads to poor spatial spectral reuse and results in low user throughput in dense user settings. In this paper, we consider simple modifications to the carrier sense mechanism that substantially improve the bits/sec/Hz/area, without increasing transceiver complexity. For 802.11g and 802.11ac, we augment the CTS with channel gain information and modify the virtual and physical carrier sense for the duration of NAV in the CTS. In addition, we consider a roughly synchronized network with alternate control and data transmission phases. During the control phase, a carrier sense multiple access with collision avoidance (CSMA-CA) MAC is used to exchange a few RTS-CTS messages in a local network neighborhood to determine the transmission scheme in the ensuing data phase. Our methods enable the application of signal to interference and noise (SINR) based scheduling algorithms to WiFi networks resulting in tremendous increase in throughput and QoS/fairness.

Interference coordination is a fundamental challenge in emerging femtocellular deployments. This paper considers a broad class of interference coordination and resource allocation problems for wireless links based on utility maximization with a general linear mixing interference model suitable for complex femtocellular systems. The resulting optimization problems are typically hard to solve optimally even using centralized algorithms but are an essential computational step in implementing rate-fair and queue stabilizing scheduling policies in wireless networks. We consider a belief propagation framework to solve such problems approximately. In particular, we construct approximations to the belief propagation iterations to obtain computationally simple and distributed algorithms with low communication overhead. Notably, our methods are very general and apply to, semi-static and dynamic interference coordination problems including the optimization of transmit powers, transmit beamforming vectors, fractional frequency reuse (FFR) and sub-band allocations to maximize the above objective. Numerical results for femtocell deployments demonstrate that such algorithms compute a very good operating point in typically just a couple of iterations.

We consider the allocation of spectral and power resources every subframe (1 ms) on the uplink of the Long Term Evolution (LTE) wideband orthogonal frequency division multiple access (OFDMA) cellular network. System bandwidth is divided into multiple sub-bands. The fractional power control to manage interference is allowed to be sub-band dependent. Moreover, the channel gains from the base-station to the mobiles (user equipment (UE) in LTE) can vary with the sub-band. The power and spectral resources are to be allocated among different UEs in a cell based on channel conditions, desired fairness/QoS, and constraints on power due to interference and power limitation at a UE. For N UEs and M sub-bands, we exploit the structure of the underlying optimization problem to obtain an interior point method for optimal resource allocation where each Newton step has complexity O(NM). To implement this in an OFDMA system, we delineate a simple control signalling structure where the UE computes in O(M) time a waterfllling solution every subframe it is assigned resources. When the allocation is restricted to contiguous allocation in frequency due to single carrier constraint in LTE, we convert the solution computed above into a feasible solution in O(NM) time. For typical network scenarios, the solution thus computed is numerically shown to be very close to the optimal solution without the contiguous constraint.

We consider a broad class of interference coordination and resource allocation problems for wireless links where the goal is to maximize the sum of functions of individual link rates. Such problems arise in the context of, for example, fractional frequency reuse (FFR) for macro-cellular networks and dynamic interference management in femtocells. The resulting optimization problems are typically hard to solve optimally even using centralized algorithms but are an essential computational step in implementing rate-fair and queue stabilizing scheduling policies in wireless networks. We consider a belief propagation framework to solve such problems approximately. In particular, we construct approximations to the belief propagation iterations to obtain computationally simple and distributed algorithms with low communication overhead. Notably, our methods are very general and apply to, for example, the optimization of transmit powers, transmit beamforming vectors, and sub-band allocation to maximize the above objective. Numerical results for femtocell deployments demonstrate that such algorithms compute a very good operating point in typically just a couple of iterations.

We consider wireless femtocell networks where scheduling of transmissions is coordinated across multiple cells to mitigate interference and deliver fairness and quality of service (QoS). Coordination across multiple cells entails (i) exchange of (serving and interfering) channel information and traffic priority (which is a function of packet delays, average rate, queue length), and (ii) signalling of transmission powers over pilots so that neighboring cells can determine the expected SINR to pick the right modulation and coding scheme. Such an exchange entails delay in coordination, resulting in scheduling decisions being made on the basis of stale information received from other cells. In this paper, we study aspects of practical signalling and algorithm design to account for such coordination delay and study its impact. When the coordination across cells is done over a high latency backhaul, we design a hybrid signalling mechanism where minimal amount of additional over-the-air (OTA) signalling enhancement can lead to tremendous performance improvement. We numerically demonstrate the benefits of our approach via comparison to a centralized scheduler and reuse one scheme using system simulations based on 3GPP evaluation methodology.

We design novel mechanisms and algorithms for fast, simple, and distributed interference management and scheduling in wireless femto networks via exchange of information over-the-air (OTA). We focus on Long Term Evolution (LTE) of the 3GPP standard and on the downlink; we leverage the existing signalling in LTE and delineate additional signals that are needed. Key aspects of our work include: (1) the design is based on only one round of exchange of very few bits of information in each subframe (of 1 ms), (2) the algorithm is a heuristic derived from the maximum weight scheduling algorithm for a realistic interference model, and (3) the framework allows for easy control of fairness for best effort flows, control of delay tails for delay sensitive QoS flows, and relative prioritization between best effort and QoS flows. The performance of the mechanisms and algorithms is validated using system simulations based on 3GPP evaluation methodology.

Embedding pico/femto base-stations and relay nodes in a macro-cellular network is a promising method for achieving substantial gains in coverage and capacity compared to macro-only networks. These new types of base-stations can operate on the same wireless channel as the macro-cellular network, providing higher spatial reuse via cell splitting. However, these base-stations are deployed in an unplanned manner, can have very different transmit powers, and may not have traffic aggregation among many users. This could potentially result in much higher interference magnitude and variability. Hence, such deployments require the use of innovative cell association and inter-cell interference coordination techniques in order to realize the promised capacity and coverage gains. In this paper, we describe new paradigms for design and operation of such heterogeneous cellular networks. Specifically, we focus on cell splitting, range expansion, semi-static resource negotiation on third-party backhaul connections, and fast dynamic interference management for QoS via over-the-air signaling. Notably, our methodologies and algorithms are simple, lightweight, and incur extremely low overhead. Numerical studies show that they provide large gains over currently used methods for cellular networks.

We consider a scheduled orthogonal frequency division multiplexed (OFDM) wireless cellular network where the channels from the base-station to the n mobile users undergo flat fading. Spectral resources are to be divided among the users in order to maximize total user utility. We show that this problem can be cast as a nonlinear convex optimization problem, and describe an O(n) algorithm to solve it. Computational experiments show that the algorithm typically converges in around 25 iterations, where each iteration has a cost that is O(n), with a modest constant. When the algorithm starts from an initial resource allocation that is close to optimal, convergence typically takes even fewer iterations. Thus, the algorithm can efficiently track the optimal resource allocation as the channel conditions change due to fading. We also show how our techniques can be extended to solve resource allocation problems that arise in wideband networks with frequency selective fading and when the utility of a user is also a function of the resource allocations in the past.

We provide a tight approximate characterization of then-dimensional product multicommodity flow (PMF) region for a wireless network ofnnodes. Separate characterizations in terms of the spectral properties of appropriate network graphs are obtained in both an information-theoretic sense and for a combinatorial interference model (e.g., protocol model). These provide an inner approximation to then2-dimensional capacity region. Our results hold for general node distributions, traffic models, and channel fading models. We first establish that the random source-destination model assumed in many previous results on capacity scaling laws, is essentially a one-dimensional approximation to the capacity region and a special case of PMF. We then build on the results for a wireline network (graph) that relate PMF to its spectral (or cut) properties. Specifically, for a combinatorial interference model given by a network graph and a conflict graph, we relate the PMF to the spectral properties of the underlying graphs resulting in simple computational upper and lower bounds. These results show that the 1/radicnscaling law obtained by Gupta and Kumar for a geometric random network can be explained in terms of the scaling law of the conductance of a geometric random graph. For the more interesting random fading model with additive white Gaussian noise (AWGN), we show that the scaling laws for PMF can again be tightly characterized by the spectral properties of appropriately defined graphs-such a characterization for general wireless networks has not been available before. As an implication, we obtain computationally efficient upper and lower bounds on the PMF for any wireless network with a guaranteed approximation factor.

We consider a cooperative wireless network where a set of nodes cooperate to relay in parallel the information from a source to a destination using a decode-and-forward approach. The source broadcasts the data to the relays, some or all of which cooperatively beamform to forward the data to the destination. We generalize the standard approaches for cooperative communications in two key respects: (i) we explicitly model and factor in the cost of acquiring channel state information (CSI), and (ii) we consider more general selection rules for the relays and compute the optimal one among them. In particular, we consider simple relay selection and outage criteria that exploit the inherent diversity of relay networks and satisfy a mandated outage constraint. These criteria include as special cases several relay selection criteria proposed in the literature. We obtain expressions for the total energy consumption for general relay selection and outage criteria for the non-homogeneous case, in which different relay links have different mean channel power gains, and the homogeneous case, in which the relay links statistics are identical. We characterize the structure of the optimal transmission scheme. Numerical results show that the cost of training and feedback of CSI is significant. The optimal strategy is to use a varying subset (and number) of relay nodes to cooperatively beamform at any given time. Depending on the relative location of the relays, the source, and the destination, numerical computations show energy savings of about 16% when an optimal relay selection rule is used. We also study the impact of shadowing correlation on the energy consumption for a cooperative relay network.

The general joint design of the physical, MAC, and routing layers to minimize network energy consumption is complex and hard to solve. Heuristics to compute approximate solutions and high-complexity algorithms to compute exact solutions have been previously proposed. In this paper, we focus on synchronous small-scale networks with interference-free link scheduling and practical MQAM link transmission schemes. We show that the cross-layer optimization problems can be closely approximated by convex optimization problems that can be efficiently solved. There are two main contributions of this paper. First of all, we minimize the total network energy that includes both transmission and circuit energy consumptions, where we explore the tradeoff between the two energy elements. Specifically, we use interference-free TDMA as the medium access control scheme. We optimize the routing flow, TDMA slot assignment, and MQAM modulation rate and power on each link. The results demonstrate that the minimum energy transmission scheme is a combination of multihop and single-hop transmissions for general networks; including circuit energy favors transmission schemes with fewer hops. Secondly, based on the solved optimal transmission scheme, we quantify the best trade-off curve between delay and energy consumption, where we derive a scheduling algorithm to minimize the worst-case packet delay.

We consider a cooperative wireless network where the source broadcasts data to relays, some or all of which cooperatively beamform to forward the data to the destination. The network is subject to an overall outage constraint. We generalize the standard approaches for cooperative communications in two respects: (i) we explicitly model and factor in the cost of acquiring channel state information (CSI), and (ii) we consider more general, yet simple, selection rules for the relays and compute the optimal one among them. These rules include as special cases several relay selection criteria proposed in the literature. We present analytical results for the homogeneous case, where the links have identical mean channel gains. For this case, we show that the optimal transmission scheme is simple and can be computed efficiently. Numerical results show that while the cost of training and feedback of CSI is significant, relay cooperation is still beneficial.

Starting with the seminal work of Gupta and Kumar (2000), there have been many interesting results that give information theoretic outer and inner approximations to the rate region for wireless networks. While these bounds are almost tight for geometric random networks, not much is known about their tightness for arbitrary wireless networks. In contrast, Leighton and Rao (1988) established a powerful result that uniform multi-commodity flow (UMCF) is within a factor of log n of the natural min-cut capacity for any graph (equivalent to a wireline network) of n nodes. Our motivation is to obtain a similar simple and general characterization for UMCF (shown to be equivalent to the characterization for a much wider class of traffic models) for any wireless network. In this paper, we apply and extend known results to obtain such characterization for networks with Gaussian fading channels. For channel state information (CSI) only at the receivers, we establish that UMCF is within a Delta2log n factor of the information theoretic min-cut capacity of a wireless network, where Delta is the max-degree of a sub-graph induced by the underlying wireless network. For deterministic AWGN channels, we show that UMCF is within square root of the min-cut bound for any network

We consider the joint optimal design of the physical, medium access control (MAC), and routing layers to maximize the lifetime of energy-constrained wireless sensor networks. The problem of computing lifetime-optimal routing flow, link schedule, and link transmission powers for all active time slots is formulated as a non-linear optimization problem. We first restrict the link schedules to the class of interference-free time division multiple access (TDMA) schedules. In this special case, we formulate the optimization problem as a mixed integerconvex program, which can be solved using standard techniques. Moreover, when the slots lengths are variable, the optimization problem is convex and can be solved efficiently and exactly using interior point methods. For general non-orthogonal link schedules, we propose an iterative algorithm that alternates between adaptive link scheduling and computation of optimal link rates and transmission powers for a fixed link schedule. The performance of this algorithm is compared to other design approaches for several network topologies. The results illustrate the advantages of load balancing, multihop routing, frequency reuse, and interference mitigation in increasing the lifetime of energy-constrained networks. We also briefly discuss computational approaches to extend this algorithm to large networks

A sensor network of nodes with wireless transceiver capabilities and limited energy is considered. We propose distributed algorithms to compute an optimal routing scheme that maximizes the time at which the first node in the network drains out of energy. The problem is formulated as a linear programming problem and subgradient algorithms are used to solve it in a distributed manner. The resulting algorithms have low computational complexity and are guaranteed to converge to an optimal routing scheme that maximizes the network lifetime. The algorithms are illustrated by an example in which an optimal flow is computed for a network of randomly distributed nodes. We also show how our approach can be used to obtain distributed algorithms for many different extensions to the problem. Finally, we extend our problem formulation to more general definitions of network lifetime to model realistic scenarios in sensor networks

We consider sensor networks where energy is a limited resource so that energy consumption must be minimized while satisfying given throughput requirements. Moreover, energy consumption must take into account both the transmission energy and the circuit processing energy for short-range communications. We emphasize that the energy efficiency must be supported across all layers of the protocol stack through a cross-layer design. In this context, we analyze energy-efficient joint routing, scheduling, and link adaptation strategies that maximize the network lifetime. We propose variable-length TDMA schemes where the slot length is optimally assigned according to the routing requirement while minimizing the energy consumption across the network. We show that the optimization problems can be transformed into or approximated by convex problems that can be efficiently solved using known techniques. The results show that multihop routing schemes are more energy-efficient when only transmission energy is considered, but single-hop transmissions may be more efficient when the circuit processing energy is considered.

We consider a wireless sensor network where the nodes have limited energy. We first analyze the delay performance of a transmission scheme based on time division multiple access (TDMA). We propose a simple link scheduling algorithm to find the minimum-delay schedule given the slot lengths for all the links. We then combine these results with our previous work on energy-optimal cross-layer design to minimize the delay in transferring a fixed number of bits from the source nodes to the sink, in an energy-constrained manner. We also study the tradeoff between the total energy consumption and delay. Pareto optimal energy-delay curves are computed by solving a series of convex optimization problems where each objective function is a weighted sum of the delay and the total energy consumption. The computation is done for networks with and without link adaptation capabilities.

We consider the joint optimal design of physical, medium access control (MAC), and routing layers to maximize the lifetime of energy-constrained wireless sensor networks. The problem of computing a lifetime-optimal routing flow, link schedule, and link transmission powers is formulated as a non-linear optimization problem. We first restrict the link schedules to the class of interference-free time division multiple access (TDMA) schedules. In this special case we formulate the optimization problem as a mixed integer-convex program, which can be solved using standard techniques. For general non-orthogonal link schedules, we propose an iterative algorithm that alternates between adaptive link scheduling and computation of optimal link rates and transmission powers for a fixed link schedule. The performance of this algorithm is compared to other design approaches for several network topologies. The results illustrate the advantages of load balancing, multihop routing, frequency reuse, and interference mitigation in increasing the lifetime of energy-constrained networks. We also describe a partially distributed algorithm to compute optimal rates and transmission powers for a given link schedule.

A sensor network of nodes with wireless transceiver capabilities and limited energy is considered. We propose distributed algorithms to compute an optimal routing scheme that maximizes the time at which the first node in the network drains out of energy. The problem is formulated as a linear programming problem and subgradient algorithms are used to solve it in a distributed manner. The resulting algorithms have low computational complexity and are guaranteed to converge to an optimal routing scheme that maximizes the network lifetime. The algorithms are illustrated by an example in which an optimal flow is computed for a network of randomly distributed nodes.