Gathering Information in Sensor Networks for Synchronized Freshness

Elahe Vahdani, Amotz Bar-Noy, Matthew P. Johnson, Tarek Abdelzaher

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509065998
DOIs
StatePublished - Jun 30 2017
Event14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017 - San Diego, United States
Duration: Jun 12 2017Jun 14 2017

Publication series

Name2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017

Other

Other14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017
CountryUnited States
CitySan Diego
Period6/12/176/14/17

    Fingerprint

ASJC Scopus subject areas

  • Media Technology
  • Computer Networks and Communications
  • Hardware and Architecture
  • Safety, Risk, Reliability and Quality
  • Instrumentation

Cite this

Vahdani, E., Bar-Noy, A., Johnson, M. P., & Abdelzaher, T. (2017). Gathering Information in Sensor Networks for Synchronized Freshness. In 2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017 [7964937] (2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SAHCN.2017.7964937