  We consider the problem of minimizing age of information in multihop wireless
networks and propose three classes of policies to solve the problem -
stationary randomized, age difference, and age debt. For the unicast setting
with fixed routes between each source-destination pair, we first develop a
procedure to find age optimal Stationary Randomized policies. These policies
are easy to implement and allow us to derive closed-form expression for average
AoI. Next, for the same unicast setting, we develop a class of heuristic
policies, called Age Difference, based on the idea that if neighboring nodes
try to reduce their age differential then all nodes will have fresher updates.
This approach is useful in practice since it relies only on the local age
differential between nodes to make scheduling decisions. Finally, we propose
the class of policies called Age Debt, which can handle 1) non-linear AoI cost
functions; 2) unicast, multicast and broadcast flows; and 3) no fixed routes
specified per flow beforehand. Here, we convert AoI optimization problems into
equivalent network stability problems and use Lyapunov drift to find scheduling
and routing schemes that stabilize the network. We also provide numerical
results comparing our proposed classes of policies with the best known
scheduling and routing schemes available in the literature for a wide variety
of network settings.
