摘要
隐私保护和任务分配是空间众包的2个核心问题。现有研究大多基于欧氏空间使用地理不可区分性保护位置隐私,但忽略了底层的路网信息,由此带来了众包工人的隐私泄露和效用损失。为了保护工人位置隐私,同时产生较小的效用损失,提出了面向路网的隐私保护批处理任务分配算法。首先,提出了图指数机制优化问题,并设计了一种贪心算法寻找近似最优解,同时引入边缘服务器作为工人的隐私保护代理。然后,将任务分配问题转化为以工人旅行距离为权值的二分图最大流问题,采用KM算法得到最优解。最后,通过实验验证了所提算法在隐私保护程度和效用上均有明显提升。
Privacy protection and task allocation are two core issues in spatial crowdsourcing.Based on Euclidean space,most of existing researches use geo-indistinguishability(GeoI)to protect location privacy,while ignoring the underlying road network information,which leads to privacy leakage and utility loss of crowdsourcing workers.In order to protect the location privacy of workers and produce small utility loss,a privacy-preserving batch task allocation algorithm framework for road network is proposed.Firstly,the graph-exponential mechanism optimization problem is proposed,and a greedy algorithm is designed to find the approximate optimal solution.At the same time,the edge server is introduced as the privacy protection agent of workers.Then,the task allocation problem is transformed into a bipartite graph maximum flow problem with the weight of workers travel distance,and the optimal solution is obtained by using Kuhn Munkras(KM)algorithm.Finally,the experiment results show that the proposed algorithms significantly improves both privacy protection and utility.
作者
侯占伟
李鑫
王辉
申自浩
刘琨
刘沛骞
HOU Zhan-wei;LI Xin;WANG Hui;SHEN Zi-hao;LIU Kun;LIU Pei-qian(School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000;School of Software,Henan Polytechnic University,Jiaozuo 454000,China)
出处
《计算机工程与科学》
CSCD
北大核心
2023年第8期1424-1432,共9页
Computer Engineering & Science
基金
国家自然科学基金(61300216)
河南理工大学博士基金(B2022-16,B2020-32)
河南省教育厅重点研发项目(20A520014)。
关键词
空间众包
路网
图指数机制
任务分配
KM算法
spatial crowdsourcing
road network
graph-exponential mechanism
task allocation
Kuhn Munkras(KM)algorithm
