A Personalized Task Allocation Strategy in Mobile Crowdsensing for Minimizing Total Cost

Abstract

Mobile crowdsensing utilizes the devices of a group of users to cooperatively perform some sensing tasks, where finding the perfect allocation from tasks to users is commonly crucial to guarantee task completion efficiency. However, existing works usually assume a static task allocation by sorting the cost of users to complete the tasks, where the cost is measured by the expense of time or distance. In this paper, we argue that the task allocation process is actually a dynamic combinational optimization problem because the previous allocated task will influence the initial state of the user to finish the next task, and the user’s preference will also influence the actual cost. To this end, we propose a personalized task allocation strategy for minimizing total cost, where the cost for a user to finish a task is measured by both the moving distance and the user’s preference for the task, then instead of statically allocating the tasks, the allocation problem is formulated as a heterogeneous, asymmetric, multiple traveling salesman problem (TSP). Furthermore, we transform the multiple-TSP to the single-TSP by proving the equivalency, and two solutions are presented to solve the single-TSP. One is a greedy algorithm, which is proved to have a bound to the optimal solution. The other is a genetic algorithm, which spends more calculation time while achieving a lower total cost. Finally, we have conducted a number of simulations based on three widely-used real-world traces: roma/taxi, epfl, and geolife. The simulation results could match the results of theoretical analysis.

Keywords

• mobile crowdsensing
• personalized task allocation
• minimizing cost
• traveling salesman problem