  We consider a star-topology wireless network for status update where a
central node collects status data from a large number of distributed
machine-type terminals that share a wireless medium. The Age of Information
(AoI) minimization scheduling problem is formulated by the restless multi-armed
bandit. A widely-proven near-optimal solution, i.e., the Whittle's index, is
derived in closed-form and the corresponding indexability is established. The
index is then generalized to incorporate stochastic, periodic packet arrivals
and unreliable channels. Inspired by the index scheduling policies which
achieve near-optimal AoI but require heavy signaling overhead, a
contention-based random access scheme, namely Index-Prioritized Random Access
(IPRA), is further proposed. Based on IPRA, terminals that are not urgent to
update, indicated by their indices, are barred access to the wireless medium,
thus improving the access timeliness. A computer-based simulation shows that
IPRA's performance is close to the optimal AoI in this setting and outperforms
standard random access schemes. Also, for applications with hard AoI deadlines,
we provide reliable deadline guarantee analysis. Closed-form achievable AoI
stationary distributions under Bernoulli packet arrivals are derived such that
AoI deadline with high reliability can be ensured by calculating the maximum
number of supportable terminals and allocating system resources proportionally.
