  We study the optimal scheduling problem where n source nodes attempt to
transmit updates over L shared wireless on/off fading channels to optimize
their age performance under energy and age-violation tolerance constraints.
Specifically, we provide a generic formulation of age-optimization in the form
of a constrained Markov Decision Processes (CMDP), and obtain the optimal
scheduler as the solution of an associated Linear Programming problem. We
investigate the characteristics of the optimal single-user multi-channel
scheduler for the important special cases of average-age and violation-rate
minimization. This leads to several key insights on the nature of the optimal
allocation of the limited energy, where a usual threshold-based policy does not
apply and will be useful in guiding scheduler designers. We then investigate
the stability region of the optimal scheduler for the multi-user case. We also
develop an online scheduler using Lyapunov-drift-minimization methods that do
not require the knowledge of channel statistics. Our numerical studies compare
the stability region of our online scheduler to the optimal scheduler to reveal
that it performs closely with unknown channel statistics.
