Search

Mobile crowdsensing has become a new way to perceive and collect information due to the widespread of smart devices. In this paper, we study the task assignment problem in mobile crowdsensing systems, which is aimed to reducing the average and largest makespan of all tasks. We consider scenarios where task requester needs the help of mobile users for task completion when they encounter directly or through AP cloud (i.e., several APs connected via wired/wireless links) in an opportunistic manner. We describe the mobile crowdsensing system and formulate the problems under study. We first derive the conditional expected encountering time between requester and different users by jointly considering the opportunities via direct encountering and indirect encountering via AP cloud. Then we propose an AP-assisted average makespan sensitive online task assignment (AP-AOTA) algorithm and an AP-assisted largest makespan sensitive online task assignment (AP-LOTA) algorithm. We present detailed design for both algorithms. We deduce the computational complexities of both algorithms to be O(mn2), where m represents the number of tasks and n represent the number of users. We conduct simulations on a real trace data set and a synthetic trace data set and the results show that our proposed algorithms significantly outperform existing work. [ABSTRACT FROM AUTHOR]

Based on the problem of task communication overhead being higher than the task execution time has a direct negative impact on the makespan of task scheduling in the current scheduling algorithms. In this paper, we propose a novel hybrid task scheduling algorithm based on task clustering (HTSTC). The algorithm uses task clustering technology to integrate tasks that meet the conditions into one cluster and uses task duplication method in the phase of processor selection. The algorithm effectively reduces the task communication overhead, and advances the start time of the successor tasks. In the layering and task priority calculation phase, HTSTC takes into account both the task communication overhead and task execution cost on different processors. The proposed algorithm effectively shortens the makespan of task scheduling. Experiments show that HTSTC has superior performance when compared to HEFT and CPOP, two of the currently leading algorithms. [ABSTRACT FROM AUTHOR]

Mobile crowdsensing has emerged as a new sensing paradigm which has many advantages over traditional sensing paradigms. In this paper, we focus on the task allocation problem for eco-friendly mobile crowdsensing which aims to minimize carbon emissions under various constraints such as task deadline and road traffic constraints. We first describe the system model of eco-friendly mobile crowdsensing and formulate the task allocation problem in offline scenario and online scenario, respectively. Then we propose Eco-Friendly Task Allocation algorithm (EFTA) to address the allocation problem in offline scenario. This algorithm consists of two processes including transportation selection and worker-task matching. After this, we propose Online Eco-Friendly Task Allocation algorithm (OEFTA) to tackle the allocation problem in online scenario. The algorithm adopts greedy online task assignment/reassignment upon arrival of a new task or a new worker. Extensive simulation results show our proposed algorithms have much better performance than baseline algorithms. [ABSTRACT FROM AUTHOR]

Mobile crowdsensing paradigms can be categorized into two classes: opportunistic sensing and participatory sensing, each of which has its advantage and disadvantage. The high flexibility of worker mobility in participatory sensing leads to high task coverage but also high worker employment fee. The little human involvement in opportunistic sensing results in low worker employment fee but also low task coverage. In this paper, we propose a new mobile crowdsensing paradigm, named semi-opportunistic sensing, aiming to achieve both high task coverage and low worker employment fee. In this paradigm, each worker can provide multiple candidate moving paths for his/her trip, among which the service platform chooses one for the worker to undertake task(s). The platform selects workers and assigns tasks to them with an objective to optimize total task quality under the platform's incentive budget and workers' task performing time constraints. In this paper, we formulate the task allocation problem, prove its NP-hardness, and present two efficient heuristic algorithms. The first heuristic, named Best Path/Task first algorithm (BPT), always chooses the best path and task in a greedy manner. The second heuristic, named LP-Relaxation based algorithm (LPR), assigns paths and tasks with the largest values according to the LP-relaxation. We conduct extensive experiments on synthetic dataset and real-life traces. Experiment results show that the proposed semi-opportunistic sensing paradigm can significantly improve total task quality compared with opportunistic sensing. Moreover, the experiment results also validate the high efficiency of our proposed task allocation algorithms. [ABSTRACT FROM AUTHOR]