Task Allocation with Profit Maximization Under Geo-indistinguishability via Q-learning
Pengfei Zhang, Yibo Zhu, Ximeng Liu, Bin Wu, Li Yan Sun, Shoufei Han, Xianjin Fang, Ji Zhang · 2024
Task allocation, a core component of mobile crowd-sensing systems, facilitates the collection, analysis, and sharing of diverse data. While existing studies often employ planar Laplacian (PL) distribution to achieve Geo-indistinguishability (Geo-I) for worker location protection, the randomness and boundlessness of PL distribution, coupled with greedy allocation strategies, often lead to excessive noise and incomplete task assignments. Moreover, these approaches typically overlook the equilibrium between worker and server benefits. To address these challenges under Geo-I, we present the Kitty approach, which adopts Q-learning to achieve superior task allocation after formalizing a constrained optimization problem that maximizes profits for both parties. Kitty operates through three key mechanisms: 1) formalizing a constrained optimization problem based on a comprehensive analysis of both parties’ profits and a pre-defined equilibrium parameter, 2) implementing adaptive adjustment of the Q-learning greedy parameter to balance exploration and exploitation, and 3) designing two conflict resolution strategies to mitigate potential distance conflicts after location perturbation. Experiments on two real-world datasets demonstrate that Kitty outperforms the state-of-the-art by at least 15% in average travel distance reduction and 1% in task completion rate improvement.