Throughput-optimal multi-hop 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 non-convex, 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 adaptive algorithms that offer excellent throughput performance at reasonable, worst-case polynomial complexity. Judicious simulations illustrate the merits of the proposed algorithms.
Nikos Sidiropoulos received the Diploma degree from the Aristotle University of Thessaloniki, Greece, and the M.S. and Ph.D. degrees from the University of Maryland at College Park (UMCP), in 1988, 1990, and 1992, respectively, all in electrical engineering. He has been a Postdoctoral Fellow (1994–1995) and Research Scientist (1996–1997) with the Institute for Systems Research, UMCP, and has held positions as Assistant Professor, Department of Electrical Engineering, University of Virginia, Charlottesville (1997–1999), and Associate Professor, Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis (2000–2002). Since 2002, he has been a Professor with the Department of Electronic and Computer Engineering, Technical University of Crete, Chania, Crete, Greece, and Adjunct Professor with the University of Minnesota. His current research interests are primarily in signal processing for communications, convex optimization, crosslayer resource allocation for wireless networks, and multiway analysis. Prof. Sidiropoulos has served as Distinguished Lecturer (2008-2009) of the IEEE Signal Processing Society (SPS), Chair of the Signal Processing for Communications and Networking Technical Committee (2007-2008), and member of the Sensor Array and Multichannel Processing Technical Committee (2004-2009) of the IEEE SPS. He has also served as an Associate Editor for the IEEE TRANSACTIONS ON SIGNAL PROCESSING (2000-2006) and the IEEE SIGNAL PROCESSING LETTERS (2000-2002). He currently serves on the editorial board of the IEEE SIGNAL PROCESSING MAGAZINE. He is IEEE Fellow. He received the U.S. NSF/CAREER award in June 1998, and the IEEE SPS Best Paper Award twice (in 2001 and 2007).