TY - GEN

T1 - Wireless scheduling for network utility maximization with optimal convergence speed

AU - Li, Bin

AU - Eryilmaz, Atilla

AU - Li, Ruogu

PY - 2013

Y1 - 2013

N2 - In this paper, we study the design of joint flow rate control and scheduling policies in multi-hop wireless networks for achieving maximum network utility with provably optimal convergence speed. Fast convergence is especially important in wireless networks which are dominated by the dynamics of incoming and outgoing flows as well as the time sensitive applications. Yet, the design of fast converging policies in wireless networks is complicated by: (i) the interference-constrained communication capabilities, and (ii) the finite set of transmission rates to select from due to operational and physical-layer constraints. We tackle these challenges by explicitly incorporating such discrete constraints to understand their impact on the convergence speed at which the running average of the received service rates and the network utility converges to their limits. In particular, we establish a fundamental fact that the convergence speed of any feasible policy cannot be faster than Ω (1/T) under both the rate and utility metrics. Then, we develop an algorithm that achieves this optimal convergence speed in both metrics. We also show that the well-known dual algorithm can achieve the optimal convergence speed in terms of its utility value. These results reveal the interesting fact that the convergence speed of rates and utilities in wireless networks is dominated by the discrete choices of scheduling and transmission rates, which also implies that the use of higher-order flow rate controllers with fast convergence guarantees cannot overcome the aforementioned fundamental limitation.

AB - In this paper, we study the design of joint flow rate control and scheduling policies in multi-hop wireless networks for achieving maximum network utility with provably optimal convergence speed. Fast convergence is especially important in wireless networks which are dominated by the dynamics of incoming and outgoing flows as well as the time sensitive applications. Yet, the design of fast converging policies in wireless networks is complicated by: (i) the interference-constrained communication capabilities, and (ii) the finite set of transmission rates to select from due to operational and physical-layer constraints. We tackle these challenges by explicitly incorporating such discrete constraints to understand their impact on the convergence speed at which the running average of the received service rates and the network utility converges to their limits. In particular, we establish a fundamental fact that the convergence speed of any feasible policy cannot be faster than Ω (1/T) under both the rate and utility metrics. Then, we develop an algorithm that achieves this optimal convergence speed in both metrics. We also show that the well-known dual algorithm can achieve the optimal convergence speed in terms of its utility value. These results reveal the interesting fact that the convergence speed of rates and utilities in wireless networks is dominated by the discrete choices of scheduling and transmission rates, which also implies that the use of higher-order flow rate controllers with fast convergence guarantees cannot overcome the aforementioned fundamental limitation.

UR - http://www.scopus.com/inward/record.url?scp=84883106798&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883106798&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2013.6567013

DO - 10.1109/INFCOM.2013.6567013

M3 - Conference contribution

AN - SCOPUS:84883106798

SN - 9781467359467

T3 - Proceedings - IEEE INFOCOM

SP - 2112

EP - 2120

BT - 2013 Proceedings IEEE INFOCOM 2013

T2 - 32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013

Y2 - 14 April 2013 through 19 April 2013

ER -