  We consider a mobile network where a mobile device is running an application
that requires timely information. The information at the device can be updated
by downloading the latest information through neighboring access points. The
freshness of the information at the device is characterized by the recently
proposed age of information. However, minimizing the age of information by
frequent downloading increases power consumption of the device. In this
context, an energy-efficient scheduling algorithm for timely information
downloads is critical, especially for power-limited mobile devices. Moreover,
unpredictable movement of the mobile device causes uncertainty of the channel
dynamics, which is even non-stationary within a finite amount of time for
running the application. Thus, in this paper we devise a randomized online
scheduling algorithm for mobile devices, which can move arbitrarily and run the
application for any amount of time. We show that the expected total cost
incurred by the proposed algorithm, including an age cost and a downloading
cost, is (asymptotically) at most e/(e-1) ~ 1.58 times the minimum total cost
achieved by an optimal offline scheduling algorithm.
