## Abstract

In this paper, we consider packet scheduling for the downlink in a wireless network, where each packet's service preferences are captured by a utility function that depends on the total delay incurred. The goal is to schedule packet transmissions to maximize the total utility. In this setting, we examine a simple gradient-based scheduling algorithm called the U̇R-rule, which is a type of generalized cμ-rule (Gcμ) that takes into account both a user's channel condition and derived utility when making scheduling decisions. We study the performance of this scheduling rule for a draining problem, where there is a given set of initial packets and no further arrivals. We formulate a "large system" fluid model for this draining problem where the number of packets becomes large while the packet-size decreases to zero, and give a complete characterization of the behavior of the U̇R scheduling rule in this limiting regime. Comparison with simulation results show that the fluid limit accurately predicts the corresponding behavior of finite systems of interest. We then give an optimal control formulation for finding the optimal scheduling policy for the fluid draining model. Using Pontryagin's minimum principle, we show that, when the user rates are chosen from a TDM-type of capacity region, the U̇R rule is in fact optimal in many cases. Sufficient conditions for optimality are also given. Finally, we consider a general capacity region and show that the U̇R rule is optimal only in special cases.

Original language | English (US) |
---|---|

Pages (from-to) | 2872-2889 |

Number of pages | 18 |

Journal | IEEE Transactions on Information Theory |

Volume | 52 |

Issue number | 7 |

DOIs | |

State | Published - Jul 2006 |

### Funding

Manuscript received June 30, 2004. This work was supported by the North-western-Motorola Center for Communications, and by the NSF under Grants CCR-9903055 and CAREER award CCR-0238382. This paper was presented in part at the 40th Annual Allerton Conference on Communications, Control, and Computing, Monticello, IL, and the 2004 IEEE Conference on Decision and Control, Paradise Island, the Bahamas. The work of P. Liu was performed while she was with the Department of Electrical Engineering and Computer Science, Northwestern University.

## Keywords

- Fluid model
- Optimal control
- Packet scheduling
- Utility function
- Wireless scheduling

## ASJC Scopus subject areas

- Information Systems
- Computer Science Applications
- Library and Information Sciences