  In a wireless network, the efficiency of scheduling algorithms over
time-varying channels depends heavily on the accuracy of the Channel State
Information (CSI), which is usually quite ``costly'' in terms of consuming
network resources. Scheduling in such systems is also subject to stringent
constraints such as power and bandwidth, which limit the maximum number of
simultaneous transmissions. In the meanwhile, communication channels in
wireless systems typically fluctuate in a time-correlated manner. We hence
design schedulers to exploit the temporal-correlation inherent in channels with
memory and ARQ-styled feedback from the users for better channel state
knowledge, under the assumption of Markovian channels and the stringent
constraint on the maximum number of simultaneously active users. We model this
problem under the framework of a Partially Observable Markov Decision
Processes.
  In recent work, a low-complexity optimal solution was developed for this
problem under a long-term time-average resource constraint. However, in real
systems with instantaneous resource constraints, how to optimally exploit the
temporal correlation and satisfy realistic stringent constraint on the
instantaneous service remains elusive. In this work, we incorporate a stringent
constraint on the simultaneously scheduled users and propose a low-complexity
scheduling algorithm that dynamically implements user scheduling and dummy
packet broadcasting. We show that the throughput region of the optimal policy
under the long-term average resource constraint can be asymptotically achieved
in the stringent constrained scenario by the proposed algorithm, in the many
users limiting regime.
