Coverage and workload cost balancing in spatial crowdsourcing

Ning Wang, Jie Wu, Pouya Ostovari

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

4 Scopus citations

Abstract

This paper addresses the coverage and workload-balancing requirements of worker recruiting in spatial crowdsourcing. That is, the recruited workers should be able to visit all the crowdsourcing locations to satisfy a certain quality, e.g., traffic monitoring or climate forecast. In addition, each crowdsourcing operation has a cost, e.g., data traffic or energy consumption, and each crowdsourcing location might have a crowdsourcing budget for the visited workers. The objective of this paper is to find a worker recruiting algorithm, which ensures the coverage requirement and minimizes the maximal crowdsourcing cost for any crowdsourcing location. We gradually discuss the problem from the 1-D scenario to the general 2-D scenario. In the 1-D scenario, we propose a bounded directional greedy algorithm first. Then, we propose a PTAS extension. A dynamic programming solution is further proposed with a higher computation complexity. In the 2-D scenario, we propose a randomized rounding algorithm with an O(log n/log log n) approximation ratio in a high probability. Extensive experiments on realistic traces demonstrate the effectiveness of the proposed algorithms.

Original languageEnglish (US)
Title of host publication2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI 2017 - Conference Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-8
Number of pages8
ISBN (Electronic)9781538604342
DOIs
StatePublished - Jun 26 2018
Externally publishedYes
Event2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI 2017 - San Francisco, United States
Duration: Apr 4 2017Apr 8 2017

Publication series

Name2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI 2017 - Conference Proceedings

Conference

Conference2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI 2017
Country/TerritoryUnited States
CitySan Francisco
Period4/4/174/8/17

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems
  • Information Systems and Management
  • Energy Engineering and Power Technology
  • Safety, Risk, Reliability and Quality
  • Urban Studies

Fingerprint

Dive into the research topics of 'Coverage and workload cost balancing in spatial crowdsourcing'. Together they form a unique fingerprint.

Cite this