Gathering Information in Sensor Networks for Synchronized Freshness

Sensor networks and the Internet of Things motivate novel classes of job scheduling problems where each "job" corresponds to downloading some data object from the sensor network, i.e., querying the network for some portion of its current state. The purpose of scheduling a set of jobs may be to support decision tasks, where the user will make a choice, prior to a deadline, informed by all the data obtained about the current situation or state. Because different aspects of the state will tend to change over time, rendering previously downloaded measurements of them "stale", we want all the data jobs to be still fresh when the last one completes. This leads to scheduling constraints much more complex than simply meeting a deadline. We investigate such freshness scheduling problems under several scenarios. We give a polynomial-time optimal algorithm for the problem of maximizing the (weighted) number of jobs scheduled via a single download channel, and an O(log n)- approximation algorithm for the (NP-hard) problem of scheduling all jobs via a minimum number of channels. The optimal algorithm exploits a shared structure between (single-deadline) freshness scheduling and ordinary scheduling with jobs-specific deadlines. Finally, we compare our approximation algorithm with natural heuristics in simulation.