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

scheduling
Sensor networks
Scheduling
sensors
Approximation algorithms
approximation
Computational complexity
Polynomials
polynomials

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

Gathering Information in Sensor Networks for Synchronized Freshness. / Vahdani, Elahe; Bar-Noy, Amotz; Johnson, Matthew P.; Abdelzaher, Tarek.

2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017. Institute of Electrical and Electronics Engineers Inc., 2017. 7964937 (2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017).

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

Vahdani, E, Bar-Noy, A, Johnson, MP & 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., 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017, San Diego, United States, 6/12/17. https://doi.org/10.1109/SAHCN.2017.7964937
Vahdani E, Bar-Noy A, Johnson MP, Abdelzaher T. Gathering Information in Sensor Networks for Synchronized Freshness. In 2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017. Institute of Electrical and Electronics Engineers Inc. 2017. 7964937. (2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017). https://doi.org/10.1109/SAHCN.2017.7964937
Vahdani, Elahe ; Bar-Noy, Amotz ; Johnson, Matthew P. ; Abdelzaher, Tarek. / Gathering Information in Sensor Networks for Synchronized Freshness. 2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017. Institute of Electrical and Electronics Engineers Inc., 2017. (2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017).
@inproceedings{87a32de84bb14314a8e19322d7022898,
title = "Gathering Information in Sensor Networks for Synchronized Freshness",
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.",
author = "Elahe Vahdani and Amotz Bar-Noy and Johnson, {Matthew P.} and Tarek Abdelzaher",
year = "2017",
month = "6",
day = "30",
doi = "10.1109/SAHCN.2017.7964937",
language = "English (US)",
series = "2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking, SECON 2017",
address = "United States",

}

TY - GEN

T1 - Gathering Information in Sensor Networks for Synchronized Freshness

AU - Vahdani, Elahe

AU - Bar-Noy, Amotz

AU - Johnson, Matthew P.

AU - Abdelzaher, Tarek

PY - 2017/6/30

Y1 - 2017/6/30

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85031681528&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031681528&partnerID=8YFLogxK

U2 - 10.1109/SAHCN.2017.7964937

DO - 10.1109/SAHCN.2017.7964937

M3 - Conference contribution

AN - SCOPUS:85031681528

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

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

PB - Institute of Electrical and Electronics Engineers Inc.

ER -