Multi-Worker Multi-task Selection Framework in Mobile Crowd Sourcing

Student thesis: Master's Thesis


The proliferation of smart phones has initiated new business models known as mobile crowd sourcing (MCS). Mobile users utilize their smart devices and their numerous embedded sensors to provide services that contribute to the development of MCS. One of the main aspects that influence the performance of an MCS system is the selection of the ideal set of service providers that fulfill the task's requirements. In large-scale MCS systems, multi-task oriented allocation provide higher efficiency for the service requesters than the traditional single-task oriented allocation. The existing solutions for multi-task selection are mainly sequential assignments and/or focus on solely minimizing the traveling distance for the workers. Hence, these solutions fall short in allocating the workers that maximize the Quality of Service (QoS) of the tasks. In this thesis, we propose two novel approaches that solve the multi-worker multi-task allocation problem, which is known to be NP-hard. The first approach, Gale-Shapley Matching Game Selection (GSMS), is a game-theoretical approach which allocates workers to multiple tasks based on two-sided preferences. While this approach maximizes the level of satisfactions for both the tasks and the mobile workers, it falls short in minimizing the distance traveled for workers for large number of tasks available. Hence, another approach that considers QoS, user satisfaction, and traveled distance is investigated. The second approach, Group-based multi-task Worker Selection (GMWS), allocates group of workers that maximize the collective QoS of the tasks, and minimize their completion time. The proposed approach relies on - i) clustering tasks based on their geographic locations using k-mediods algorithm, ii) selecting group of workers to a cluster of tasks, using genetic algorithm (GA), and iii) delegating workers to individual tasks within a cluster using tabu search algorithm. The two approaches are grouped together to form a two-layer selection approach, Group-based Multi-task Worker Selection Using Gale-Shapley (GMWS-GS). The two-layer approach aims at maximizing iii the QoS of the tasks while keeping the costs of workers allocation minimal. Simulations based on real-life dataset show that the proposed approaches outperform other multi-task and single-task allocation benchmarks.
Date of AwardJul 2018
Original languageAmerican English
SupervisorRabeb Mizouni (Supervisor)


  • Mobile crowd sourcing (MCS)
  • multi-tasking
  • worker recruitment
  • Quality of service (QoS)
  • task clustering
  • Gale-Shapley.

Cite this