This paper studies a multi-source “age of information”
problem in multi-hop wireless networks with packetized
status updates and explicit channel contention. Specifically, the
scenario considered in this paper assumes that each node in the
network is a both a source and a monitor of information. Nodes
take turns broadcasting their information to other nodes in the
network while also maintaining tables of status updates for the
information received from all other nodes in the network. Lower
bounds on the peak and average age of information are derived
and are found to be a function of fundamental graph properties
including the connected domination number of the graph and the
average shortest path length. In addition to these converse results,
achievability results are developed through the presentation of
an explicit algorithm for constructing near-optimal status update
schedules along with an analytical upper bound for the average
and peak age of these schedules. Finally, numerical results are
presented that compute the bounds, construct schedules, and
compute the achieved average and peak ages of these schedules
exhaustively over every connected network topology with nine or
fewer nodes. The results show that the the developed schedules
achieve a peak age exactly matching the lower bounds and an
average age within a multiplicative factor of 1.035 of the lower
bound in all tested cases.