The maximum differential backlog (MDB), or “backpressure” control policy of Tassiulas and Ephremides has been shown to adaptively maximize the stable throughput of multihop wireless networks with random traffic arrivals and queueing. The practical implementation of the MDB policy in wireless networks with mutually interfering links, however, requires the development of distributed optimization algorithms. Within the context of code-division multiple-access (CDMA)-based multihop wireless networks, we develop a set of node-based scaled gradient projection power control algorithms which solves the MDB optimization problem based on the high-signal-to-interference-plus-noise ratio (SINR) approximation of link capacities using low communication overhead. We investigate the impact of the high-SINR approximation and the nonnegligible convergence time required by the power control algorithms on the throughput region achievable by the iterative MDB policy. We show that the policy can achieve at least the stability region induced by the high-SINR capacity region.

We study pricing games in multi-hop relay networks where nodes price their services and route their traffic selfishly and strategically. Each node (1) makes a bid to each of its customers, specifying a charging function and a proposed traffic share, and (2) allocates its received traffic to its service providers. A node aims to maximize its profit from forwarding traffic. We show that the socially optimal routing can always be induced by an equilibrium where no node can increase its profit by unilaterally changing its bids. Inefficient equilibria arise in oligopolies due to the monopolistic pricing power of a superior relay. It results in finite price of anarchy if marginal cost functions are concave, but unbounded price of anarchy when they are convex. Pricing games of general topology suffer from the intrinsic multi-hop network structure, which gives rise to infinite price of anarchy.

In wireless networks, important network functionalities such as power control, rate allocation, routing, and congestion control must be optimized in a coherent and integrated manner. In this work, an interference-limited wireless network is considered, whereby power control and routing variables are chosen to minimize the sum of link costs which depend on both link capacities and link flow rates. The necessary conditions for optimality are established. These conditions are sufficient for optimality if link cost functions are jointly convex, and imply Pareto optimality if link costs are strictly quasi-convex. Network algorithms based on the scaled gradient projection method, where power control and routing are performed on a node-by-node basis, are presented. For these algorithms, explicit scaling matrices and stepsizes are found which lead to more distributed implementation, and which guarantee fast convergence to a network configuration satisfying the optimality conditions, starting from any initial configuration with finite cost. Refinements of the algorithms for more accurate link capacity models are presented, and the results are extended to wireless networks where the physical-layer rate region is given by an arbitrary convex set. Finally, it is shown that the power control and routing algorithms can naturally be extended to incorporate congestion control.

A new spectrum allocation scheme is developed to satisfy the fundamental duplexing constraint in wireless networks. A feasible spectrum allocation is achieved through dividing the whole spectrum into multiple sub-bands and activating conflict-free links on each sub-band. It is found that the minimum number of sub-bands needed to yield a feasible spectrum allocation grows asymptotically at a logarithmic rate with the chromatic number. We design a simple distributed and asynchronous algorithm which yields a feasible spectrum allocation given enough sub-bands.

We develop distributed algorithms to allocate resources in multi-hop wireless networks with the aim of minimizing the total cost. In order to observe the fundamental duplexing constraint that co-located transmitters and receivers cannot operate simultaneously on the same frequency band, we first devise a spectrum allocation scheme that divides the whole spectrum into multiple sub-bands and activates conflict-free links on each sub-band. We show that the minimum number of required sub-bands grows asymptotically at a logarithmic rate with the chromatic number of network connectivity graph. A simple distributed and asynchronous algorithm is developed to feasibly activate links on the available sub-bands. Given a feasible spectrum allocation, we then develop node-based distributed algorithms for optimally controlling the transmission powers on active links for each sub-band, jointly with traffic routes and user input rates in response to channel states and traffic demands. We show that under specified conditioans, the algorithms asymptotically converge to the optimal operating point.

We present a unified analytical framework within which power control and routing for wireless networks can be optimized on a node-by-node basis. We consider a multicommodity flow model for an interference-limited wireless network in which power control and routing variables are chosen to minimize convex link costs. Distributed scaled gradient projection algorithms are developed to iteratively adjust power control and routing schemes at individual nodes. We specify appropriate scaling matrices with which the algorithms quickly converge to the global optimum from any initial point. These scaling matrices can be computed locally at each node with limited control message overhead

We present a unified analytical framework within which capacity allocation, routing, and congestion control for wireless networks can be optimized in a coherent and integrated manner. We consider a multi-commodity flow model and examine wireless networks with general coding/modulation schemes represented by convex physical-layer capacity regions. Within this framework, capacity variables and routing variables are chosen to minimize convex link costs reflecting, for instance, average queueing delay. For problems with jointly convex cost functions, the necessary and sufficient conditions for optimality are derived. These results are then extended to the more general case where link costs are quasi-convex. Finally, we demonstrate that congestion control can be seamlessly incorporated into our framework

The Maximum Differential Backlog (MDB) control policy of Tassiulas and Ephremides has been shown to adaptively maximize the stable throughput of multi-hop wireless networks with random traffic arrivals and queueing. The practical implementation of the MDB policy in wireless networks with mutually interfering links, however, requires the development of distributed optimization algorithms. Within the context of CDMA-based multi-hop wireless networks, we develop a set of node-based scaled gradient projection power control algorithms which solves the MDB optimization problem in a distributed manner using low communication overhead. As these algorithms require time to converge to a neighborhood of the optimum, the implementation of the MDB policy must be done with delayed queue state information. For this, we show that the MDB policy with delayed queue state information remains throughput optimal.