Joint sensing duty cycle scheduling for heterogeneous coverage guarantee

Kin Sum Liu, Tyler Mayer, Hao Tsung Yang, Esther Arkin, Jie Gao, Mayank Goswami, Matthew P. Johnson, Nirman Kumar, Shan Lin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations


In this paper we study the following problem: given a set of m sensors that collectively cover a set of n target points with heterogeneous coverage requirements (target j needs to be covered every fj slots), how to schedule the sensor duty cycles such that all coverage requirements are satisfied and the maximum number of sensors turned on at any time slot is minimized. The problem models varied real-world applications in which sensing tasks exhibit high discrepancy in coverage requirements - critical locations often need to be covered much more frequently. We provide multiple algorithms with best approximation ratio of O (log n + log m) for the maximum number of sensors to turn on, and bi-criteria algorithm with (α, β)-approximation factors with high probability, where the number of sensors turned on is an α = O(δ(log (n) + log(m))/β)-approximation of the optimal (satisfying all requirements) and the coverage requirement is a β-approximation; δ is the approximation ratio achievable in an appropriate instance of set multi-cover. When the sensor coverage exhibits extra geometric properties, the approximation ratios can be further improved. We also evaluated our algorithms via simulations and experiments on a camera testbed. The performance improvement (energy saving) is substantial compared to turning on all sensors all the time, or a random scheduling baseline.

Original languageEnglish
Title of host publicationINFOCOM 2017 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509053360
StatePublished - 2 Oct 2017
Event2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States
Duration: 1 May 20174 May 2017

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Conference2017 IEEE Conference on Computer Communications, INFOCOM 2017
Country/TerritoryUnited States


Dive into the research topics of 'Joint sensing duty cycle scheduling for heterogeneous coverage guarantee'. Together they form a unique fingerprint.

Cite this