  We consider a base station (BS) that receives version update packets from
multiple exogenous streams and broadcasts them to corresponding users over a
fading broadcast channel using a non-orthogonal multiple access (NOMA) scheme.
Sequentially indexed packets arrive randomly in each stream, with new packets
making the previous ones obsolete. In this case, we consider the version age of
information (VAoI) at a user, defined as the difference in the version index of
the latest available packet at the BS and that at the user, as a metric of
freshness of information. Our objective is to minimize a weighted sum of
average VAoI across users subject to an average power constraint at the BS by
optimally scheduling the update packets from various streams for transmission
and transmitting them with sufficient powers to guarantee their successful
delivery. We consider the class of channel-only stationary randomized policies
(CO-SRP), which rely solely on channel power gains for transmission decisions.
We solve the resulting non-convex problem optimally and show that the VAoI
achieved under the optimal CO-SRP is within twice the optimal achievable VAoI.
We also obtained a Constrained Markov Decision Process (CMDP)-based solution
and its structural properties. Numerical simulations show a close performance
between the optimal CO-SRP and CMDP-based solutions. Additionally, a time
division multiple access (TDMA) scheme, which allows transmission to at most
one user at a time, matches NOMA's performance under tight average power
constraints. However, NOMA outperforms TDMA as the constraint is relaxed.
