Convex approximation algorithms for back-pressure power control

Evaggelia Matskani, Nicholas D. Sidiropoulos, Leandros Tassiulas

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Throughput-optimal multihop wireless network operation entails a key physical-layer optimization problem: maximizing a weighted sum of link rates, with weights given by the differential queue backlogs. This emerges in joint back-pressure routing and power control, which is central in cross-layer wireless networking. We begin by showing that the core problem is not only nonconvex, but also NP-hard. This is a negative result, which however comes with a positive flip side: drawing from related developments in the digital subscriber line (DSL) literature, we propose effective ways to approximate it. Exploiting quasi-periodicity of the power allocation in stable setups due to the push-pull nature of the solution, we derive two custom algorithms that offer excellent throughput performance at reasonable, worst-case polynomial complexity. Judicious simulations illustrate the merits of the proposed algorithms.

Original languageEnglish (US)
Article number6129545
Pages (from-to)1957-1970
Number of pages14
JournalIEEE Transactions on Signal Processing
Issue number4
StatePublished - Apr 2012

Bibliographical note

Funding Information:
Manuscript received October 20, 2010; revised April 28, 2011 and November 27, 2011; accepted December 18, 2011. Date of publication January 12, 2012; date of current version March 06, 2012. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Josep Vidal. This work was co-financed by the European Union (European Social Fund—ESF) and Greek National Funds through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF)—Research Funding Program: Heracleitus II, investing in knowledge society through the European Social Fund. This work was also supported in part by ARL/ERO, under contract W911NF-09-1-0004 and EC FP7 project N-CRAVE. Part of this work has appeared in Proc. IEEE ICASSP 2011 Conference.


  • Back-pressure routing
  • NP-hard problems
  • convex approximation
  • cross-layer design
  • digital subscriber line (DSL)
  • dynamic spectrum management
  • network optimization
  • power control
  • utility maximization


Dive into the research topics of 'Convex approximation algorithms for back-pressure power control'. Together they form a unique fingerprint.

Cite this