Utility-optimal scheduling in time-varying wireless networks with delay constraints
- 20 September 2010
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
Clients in wireless networks may have per-packet delay constraints on their traffic. Further, in contrast to wireline networks, the wireless medium is subject to fading. In such a time-varying environment, we consider the system problem of maximizing the total utility of clients, where the utilities are determined by their long-term average rates of being served within their delay constraints. We also allow for the additional fairness requirement that each client may require a certain minimum service rate. This overall model can be applied to a wide range of applications, including delay-constrained networks, mobile cellular networks, and dynamic spectrum allocation. We address this problem through convex programming. We propose an on-line scheduling policy and prove that it is utility-optimal. Surprisingly, this policy does not need to know the probability distribution of system states. We also design an auction mechanism where clients are scheduled and charged according to their bids. We prove that the auction mechanism restricts any selfish client from improving its utility by faking its utility function. We also show that the auction mechanism schedules clients in the same way as that done by the on-line scheduling policy. Thus, the auction mechanism is both truthful and utility-optimal. Finally, we design specific algorithms that implement the auction mechanism for a variety of applications.Keywords
This publication has 15 references indexed in Scilit:
- Wireless Network Utility MaximizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Index Policies for Real-Time Multicast Scheduling for Wireless Broadcast SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- A General Framework for Wireless Spectrum AuctionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Opportunistic transmission scheduling with resource-sharing constraints in wireless networksIEEE Journal on Selected Areas in Communications, 2001
- Rate control for communication networks: shadow prices, proportional fairness and stabilityJournal of the Operational Research Society, 1998
- Charging and rate control for elastic trafficEuropean Transactions on Telecommunications, 1997
- Stochastic Approximation Algorithms and ApplicationsPublished by Springer Science and Business Media LLC ,1997
- Incentives in TeamsEconometrica, 1973
- Multipart pricing of public goodsPublic Choice, 1971
- COUNTERSPECULATION, AUCTIONS, AND COMPETITIVE SEALED TENDERSThe Journal of Finance, 1961