On exploiting logical dependencies for minimizing additive cost metrics in resource-limited crowdsensing

Shaohan Hu, Shen Li, Shuochao Yao, Lu Su, Ramesh Govindan, Reginald Hobbs, Tarek Abdelzaher

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

Abstract

We develop data retrieval algorithms for crowd-sensing applications that reduce the underlying network bandwidth consumption or any additive cost metric by exploiting logical dependencies among data items, while maintaining the level of service to the client applications. Crowd sensing applications refer to those where local measurements are performed by humans or devices in their possession for subsequent aggregation and sharing purposes. In this paper, we focus on resource-limited crowd sensing, such as disaster response and recovery scenarios. The key challenge in those scenarios is to cope with resource constraints. Unlike the traditional application design, where measurements are sent to a central aggregator, in resource limited scenarios, data will typically reside at the source until requested to prevent needless transmission. Many applications exhibit dependencies among data items. For example, parts of a city might tend to get flooded together because of a correlated low elevation, and some roads might become useless for evacuation if a bridge they lead to fails. Such dependencies can be encoded as logic expressions that obviate retrieval of some data items based on values of others. Our algorithm takes logical data dependencies into consideration such that application queries are answered at the central aggregation node, while network bandwidth usage is minimized. The algorithms consider multiple concurrent queries and accommodate retrieval latency constraints. Simulation results show that our algorithm outperforms several baselines by significant margins, maintaining the level of service perceived by applications in the presence of resource-constraints.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages189-198
Number of pages10
ISBN (Electronic)9781479988563
DOIs
StatePublished - Jul 22 2015
Event11th IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2015 - Fortaleza, Brazil
Duration: Jun 10 2015Jun 12 2015

Publication series

NameProceedings - IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2015

Other

Other11th IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2015
CountryBrazil
CityFortaleza
Period6/10/156/12/15

    Fingerprint

Keywords

  • Cost optimization
  • Crowd sensing
  • Logical dependency
  • Resource limitation

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

Cite this

Hu, S., Li, S., Yao, S., Su, L., Govindan, R., Hobbs, R., & Abdelzaher, T. (2015). On exploiting logical dependencies for minimizing additive cost metrics in resource-limited crowdsensing. In Proceedings - IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2015 (pp. 189-198). [7165037] (Proceedings - IEEE International Conference on Distributed Computing in Sensor Systems, DCOSS 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DCOSS.2015.26