  A delay-constrained scheduling problem for point-to-point communication is
considered: a packet of $B$ bits must be transmitted by a hard deadline of $T$
slots over a time-varying channel. The transmitter/scheduler must determine how
many bits to transmit, or equivalently how much energy to transmit with, during
each time slot based on the current channel quality and the number of unserved
bits, with the objective of minimizing expected total energy. In order to focus
on the fundamental scheduling problem, it is assumed that no other packets are
scheduled during this time period and no outage is allowed. Assuming
transmission at capacity of the underlying Gaussian noise channel, a
closed-form expression for the optimal scheduling policy is obtained for the
case T=2 via dynamic programming; for $T>2$, the optimal policy can only be
numerically determined. Thus, the focus of the work is on derivation of simple,
near-optimal policies based on intuition from the T=2 solution and the
structure of the general problem. The proposed bit-allocation policies consist
of a linear combination of a delay-associated term and an opportunistic
(channel-aware) term. In addition, a variation of the problem in which the
entire packet must be transmitted in a single slot is studied, and a
channel-threshold policy is shown to be optimal.
