Ad Hoc Networks. 10th EAI International Conference, ADHOCNETS 2018, Cairns, Australia, September 20-23, 2018, Proceedings

Research Article

Task Assignment for Semi-opportunistic Mobile Crowdsensing

Download
160 downloads
  • @INPROCEEDINGS{10.1007/978-3-030-05888-3_1,
        author={Wei Gong and Baoxian Zhang and Cheng Li},
        title={Task Assignment for Semi-opportunistic Mobile Crowdsensing},
        proceedings={Ad Hoc Networks. 10th EAI International Conference, ADHOCNETS 2018, Cairns, Australia, September 20-23, 2018, Proceedings},
        proceedings_a={ADHOCNETS},
        year={2018},
        month={12},
        keywords={Mobile crowdsensing Task assignment Semi-opportunistic sensing},
        doi={10.1007/978-3-030-05888-3_1}
    }
    
  • Wei Gong
    Baoxian Zhang
    Cheng Li
    Year: 2018
    Task Assignment for Semi-opportunistic Mobile Crowdsensing
    ADHOCNETS
    Springer
    DOI: 10.1007/978-3-030-05888-3_1
Wei Gong1,*, Baoxian Zhang1,*, Cheng Li,*
  • 1: University of Chinese Academy of Sciences
*Contact email: gongwei11@mails.ucas.ac.cn, bxzhang@ucas.ac.cn, licheng@mun.ca

Abstract

In this paper, we propose a novel crowdsensing paradigm called semi-opportunistic sensing, which is aimed to achieve high task quality with low human involvement. In this paradigm, each mobile user can provide multiple path choices to reach her destination, which largely broadens the task assignment space. We formulate the task assignment problem in this paradigm of maximizing total task quality under incentive budget constraint and user travel time constraints. We prove this problem is NP-hard and then propose two efficient heuristic algorithms. First, we propose a Best Path/Task first algorithm (BPT) which always chooses current best path and current best task into the assignment list. Second, we propose an LP-relaxation based algorithm (LPR), which greedily assigns paths and tasks with the largest values in LP relaxation solution. We deduce the computational complexities of the proposed algorithms. We evaluate the performance of our algorithms using real-world traces. Simulation results show that our proposed crowdsensing paradigm can largely increase overall task quality compared with the opportunistic sensing paradigm where each user has only one fixed path. Simulation results also show that our proposed algorithms are efficient and their performance is close to the optimal solution.