Convex approximation algorithms for back-pressure power control

Evaggelia Matskani, Nicholas D. Sidiropoulos, Leandros Tassiulas

Research output: Contribution to journalArticlepeer-review

10 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


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

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

Cite this