Network utility maximization over partially observable Markovian channels

We study throughput utility maximization in a multi-user network with partially observable Markovian channels. Here, instantaneous channel states are unavailable and all controls are based on partial channel information provided by ACK/NACK feedback from past transmissions. Equivalently, we formulate a restless multi-armed bandit problem in which we seek to maximize concave functions of the time average reward vector. Such problems are generally intractable and in our problem the set of all achievable throughput vectors is unknown. We use an achievable region approach by optimizing the utility functions over a non-trivial reduced throughput region, constructed by randomizing well-designed round robin policies. Using a new ratio MaxWeight rule, we design admission control and channel scheduling policies that stabilize the network with throughput utility that is near-optimal within the reduced throughput region. The ratio MaxWeight rule generalizes existing MaxWeight-type policies for the optimization of frame-based control systems with policy-dependent frame sizes. Our results are applicable to limited channel probing in wireless networks, dynamic spectrum access in cognitive radio networks, and target tracking of unmanned aerial vehicles.