  In this paper, we consider transmission scheduling in a status update system,
where updates are generated periodically and transmitted over a Gilbert-Elliott
fading channel. The goal is to minimize the long-run average age of information
(AoI) at the destination under an average energy constraint. We consider two
practical cases to obtain channel state information (CSI): (i) \emph{without
channel sensing} and (ii) \emph{with delayed channel sensing}. For case (i),
the channel state is revealed when an ACK/NACK is received at the transmitter
following a transmission, but when no transmission occurs, the channel state is
not revealed. Thus, we have to design schemes that balance tradeoffs across
energy, AoI, channel exploration, and channel exploitation. The problem is
formulated as a constrained partially observable Markov decision process
problem (POMDP). To reduce algorithm complexity, we show that the optimal
policy is a randomized mixture of no more than two stationary deterministic
policies each of which is of a threshold-type in the belief on the channel. For
case (ii), (delayed) CSI is available at the transmitter via channel sensing.
In this case, the tradeoff is only between the AoI and energy consumption and
the problem is formulated as a constrained MDP. The optimal policy is shown to
have a similar structure as in case (i) but with an AoI associated threshold.
Finally, the performance of the proposed structure-aware algorithms is
evaluated numerically and compared with a Greedy policy.
