面向路网的空间众包隐私保护任务分配算法.pdf

面向路网的空间众包隐私保护任务分配算法*侯占伟1,李 鑫1,王 辉2,申自浩1,刘 琨2,刘沛骞2(1.河南理工大学计算机科学与技术学院,河南 焦作 4 5 4 0 0 0;2.河南理工大学软件学院,河南 焦作 4 5 4 0 0 0)摘 要:隐私保护和任务分配是空间众包的2个核心问题。现有研究大多基于欧氏空间使用地理不可区分性保护位置隐私,但忽略了底层的路网信息,由此带来了众包工人的隐私泄露和效用损失。为了保护工人位置隐私,同时产生较小的效用损失,提出了面向路网的隐私保护批处理任务分配算法。首先,提出了图指数机制优化问题,并设计了一种贪心算法寻找近似最优解,同时引入边缘服务器作为工人的隐私保护代理。然后,将任务分配问题转化为以工人旅行距离为权值的二分图最大流问题,采用KM算法得到最优解。最后,通过实验验证了所提算法在隐私保护程度和效用上均有明显提升。关键词:空间众包;路网;图指数机制;任务分配;KM算法中图分类号:T P 3 9 3 文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 3.0 8.0 1 1A s p a t i a l c r o w d s o u r c i n g p r i v a c y p r e s e r v a t i o n t a s k a l l o c a t i o n a l g o r i t h m f o r r o a d n e t w o r kHOU Z h a n-w e i1,L I X i n1,WANG H u i2,S HE N Z i-h a o1,L I U K u n2,L I U P e i-q i a n2(1.S c h o o l o f C o m p u t e r S c i e n c e a n d T e c h n o l o g y,H e n a n P o l y t e c h n i c U n i v e r s i t y,J i a o z u o 4 5 4 0 0 0;2.S c h o o l o f S o f t w a r e,H e n a n P o l y t e c h n i c U n i v e r s i t y,J i a o z u o 4 5 4 0 0 0,C h i n a)A b s t r a c t:P r i v a c y p r o t e c t i o n a n d t a s k a l l o c a t i o n a r e t w o c o r e i s s u e s i n s p a t i a l c r o w d s o u r c i n g.B a s e d o n E u c l i d e a n s p a c e,m o s t o f e x i s t i n g r e s e a r c h e s u s e g e o-i n d i s t i n g u i s h a b i l i t y(G e o I)t o p r o t e c t l o c a t i o n p r i v a c y,w h i l e i g n o r i n g t h e u n d e r l y i n g r o a d n e t w o r k i n f o r m a t i o n,w h i c h l e a d s t o p r i v a c y l e a k a g e a n d u-t i l i t y l o s s o f c r o w d s o u r c i n g w o r k e r s.I n o r d e r t o p r o t e c t t h e l o c a t i o n p r i v a c y o f w o r k e r s a n d p r o d u c e s m a l l u t i l i t y l o s s,a p r i v a c y-p r e s e r v i n g b a t c h t a s k a l l o c a t i o n a l g o r i t h m f r a m e w o r k f o r r o a d n e t w o r k i s p r o p o s e d.F i r s t l y,t h e g r a p h-e x p o n e n t i a l m e c h a n i s m o p t i m i z a t i o n p r o b l e m i s p r o p o s e d,a n d a g r e e d y a l-g o r i t h m i s d e s i g n e d t o f i n d t h e a p p r o x i m a t e o p t i m a l s o l u t i o n.A t t h e s a m e t i m e,t h e e d g e s e r v e r i s i n t r o-d u c e d a s t h e p r i v a c y p r o t e c t i o n a g e n t o f w o r k e r s.T h e n,t h e t a s k a l l o c a t i o n p r o b l e m i s t r a n s f o r m e d i n t o a b i p a r t i t e g r a p h m a x i m u m f l o w p r o b l e m w i t h t h e w e i g h t o f w o r k e r s t r a v e l d i s t a n c e,a n d t h e o p t i m a l s o l u t i o n i s o b t a i n e d b y u s i n g K u h n M u n k r a s(KM)a l g o r i t h m.F i n a l l y,t h e e x p e r i m e n t r e s u l t s s h o w t h a t t h e p r o p o s e d a l g o r i t h m s s i g n i f i c a n t l y i m p r o v e s b o t h p r i v a c y p r o t e c t i o n a n d u t i l i t y.K e y w o r d s:s p a t i a l c r o w d s o u r c i n g;r o a d n e t w o r k;g r a p h-e x p o n e n t i a l m e c h a n i s m;t a s k a l l o c a t i o n;K u h n M u n k r a s(KM)a l g o r i t h m1 引言众包(C r o w d s o u r c i n g)是一种把过去由专职员工执行的工作任务通过公开的W e b平台,以自愿的形式外包给非特定解决方案提供者群体来完成的分布式问题求解模式1。随着移动互联网的发展和智能移动设备的普及,基于W e b的传统众包*收稿日期:2 0 2 2-0 9-0 9;修回日期:2 0 2 3-0 1-1 6基金项目:国家自然科学基金(6 1 3 0 0 2 1 6);河南理工大学博士基金(B 2 0 2 2-1 6,B 2 0 2 0-3 2);河南省教育厅重点研发项目(2 0 A 5 2 0 0 1 4)通信作者:刘沛骞(l i u p e i q i a n h p u.e d u.c n)通信地址:4 5 4 0 0 0 河南省焦作市河南理工大学软件学院A d d r e s s:S c h o o l o f S o f t w a r e,H e n a n P o l y t e c h n i c U n i v e r s i t y,J i a o z u o 4 5 4 0 0 0,H e n a n,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 5卷第8期2 0 2 3年8月 V o l.4 5,N o.8,A u g.2 0 2 3 文章编号:1 0 0 7-1 3 0 X(2 0 2 3)0 8-1 4 2 4-0 9已经转向空间众包S C(S p a t i a l C r o w d s o u r c i n g)2。空间众包被定义为将一组空间任务(即与某个地点相关的任务)众包给一组工人的过程,并要求工人在物理空间上移动到这些地点完成众包任务。例如,在空间众包应用滴滴出行服务中,用户向平台提交具体的上车位置,被分配到该订单的司机需要到该位置接到乘客并载乘客到达目的地。任务分配是空间众包的核心问题,按照任务分配模式,可分为服务器分配任务(S e r v e r A s s i g n e d t a s k s)模 式 和 工 人 选 择 模 式(W o r k e r S e l e c t e d t a s k s)3。现有的空间众包系统大多使用服务器分配任务模式,本文也采用这种模式。在此模式下由服务器将任务分配给适当的工人,工人需要向众包平台上传自己的位置。用户的位置属于高度敏感信息,敌手可以通过工人位置推断出工人的个人隐私(如健康状况、宗教信仰、工作地址等)。若工人的位置隐私泄露,将极大地降低工人参与空间众包的兴趣和积极程度,导致众多空间众包任务无法完成。因此,保证工人的位置隐私在空间众包中尤为重要。目前大多数研究采用地理不可区分性G e o I(G e o-I n d i s t i n g u i s h a b i l i t y)4扰动工人位置,即将位置扰动到二维平面中的任意一点。如果被扰动后的位置是不可能到达的,例如在湖泊上、在海面上或在江河上,敌手可以根据该位置的不可达性,使用推断模型来预测用户的实际位置,这无疑加大了用户位置隐私泄露的风险。此外,地理不可区分性使用欧氏距离测量2个位置之间的距离。当用户受到现实路网环境限制时,这种方法会造成较大的效用损失。最近,T a k a g i等人5通过实验证明了地理不可区分性在路网环境下会导致隐私泄露和较差的服务质量,因此提出了一种满足差分隐私的位置隐私概念,即地理图不可区分性G e o G I(G e o-G r a p h-I n d i s t i n g u i s h a b i l i t y),并设计了 满足该概 念 的 隐 私 保 护 机 制 图 指 数 机 制G EM(G r a p h-E x p o n e n t i a l M e c h a n i s m)。地理图不可区分性将路网环境考虑在内,是一种比地理不可区分性更适合路网的基于位置 服务L B S s(L o c a t i o n-B a s e d S e r v i c e s)的隐私保护概念。目前,关于空间众包的任务分配研究大多数是在线设置,众包任务到达平台后立即被分配给合适的工人。在线设置的任务分配方法按照任务到达的时间进行分配,当新任务到达时,以前的任务已经被分配,是不能被改变的。这种方法可能会产生次最优分配方案,产生更大的工人平均旅行距离。目前,尚无专门针对面向路网的隐私保护批处理任务分配研究。实际上,基于批处理的设置在众包行业已经被广泛应用。例如,国内领先的打车平台滴滴出行在一段时间内积累订单(任务),并分批分配给司机(工人)6。考虑到现有工作的不足,本文研究了面向路网的隐私保护批处理任务分配问题。该问题研究的是在路网环境下,以保护工人位置隐私为前提,以最小化工人平均旅行距离为目标,将任务分批次分配给工人。为了解决上述问题,本文考虑将地理图不可区分性和图指数机制引入空间众包保护工人位置隐私。首先提出的是图指数机制并被应用于面向路网的L B S s中。若将其直接应用于空间众包的隐私保护,可能会产生较大的工人平均旅行距离,造成更多的效用损失。为了在保护工人位置隐私的同时产生较小的效用损失,本文提出了面向路网的隐私保护批处理任务分配算法框架。该框架由图指数机制优化算法和以最小化工人平均旅行距离为目标的任务分配算法组成,同时引入边缘服务器作为工人的隐私保护代理,工人的真实位置经过边缘服务器扰动后上传至众包服务器,防止不受信任的众包服务器泄露工人位置隐私,同时边缘服务器的去中心化特性有效避免了潜在的隐私泄露。本文的工作如下:(1)提出了面向路网的空间众包隐私保护批处理任务分配问题。该问题在保护工人位置隐私的同时,以最小化工人平均旅行距离为目标进行批处理任务分配。并介绍了一种适用于路网的位置隐私保护概念和机制 地理图不可区分性和图指数机制。(2)提出了面向路网的隐私保护批处理任务分配算法框架。设计了一种贪心算法,解决了其中图指 数 机 制 的 优 化 问 题,并 采 用KM(K u h n M u n k r a s)算法解决以工人旅行距离为权值的二分图最大流问题。(3)为了评估本文算法的性能,在真实数据集上进行了实验。对比其他算法,本文提出的算法隐私保护程度更高、效用损失更小。2 相关工作现有研究大多面向欧氏空间,仅有少部分研究考虑了路网信息,以下将从这2个方面介绍与本文相关的研究工作。2.1 面向欧氏空间的空间众包研究为了保护众包工人的位置隐私,现有研究大多5241侯占伟等:面向路网的空间众包隐私保护任务分配算法采用地理不可区分性保护位置隐私。目前有2种机制实现地理不可区分性,分别为拉普拉斯机制和优化机制。为了同时保护任务和工人的位置隐私,T o等 人7提 出 了 一 个 隐 私 保 护 框 架S C G u a r d(S p a t i a l C r o w d s o u r c i n g G u a r d)。该框架用地理不可区分性的拉普拉斯机制扰动任务和工人的位置,并基于扰动位置量化了工人到任务的可达概率,最后将任务分配给合适的工人。X i a等人8提出了一种实时隐私保护、在线分配任务的方案R e-p o t(R e a l-t i m e a n d p r i v a c y-p r e s e r v i n g o n l i n e t a s k a s s i g n m e n t s c h e m e)。该方案使用拉普拉斯机制扰动工人的实际位置,众包服务器动态地接收工人的扰动位置和任务的实际位置并将接收到的任务分配给当前最优工人,未匹配的工人和任务继续保留在众包服务器等待分配。为了将任务实时分配给最合适的工人,该文献还设计了一种基于概率的方法衡量工人和任务之间的可达概率。W a n g等人9研究了基于优化机制的位置隐私保护方案。该方案首先由众包服务器生成满足地理不可区分性的位置混淆函数,每个工人根据函数中的混淆概率扰动真实位置并上传至众包服务器,众包服务器根据工人的扰动位置将任务分配给合适的工人。为了最小化工人的预期旅行距离,该方案以最小化工人的预期旅行距离为目标,使用线性规划得到最优位置混淆函数。T a o等人1 0提出了基于层次分离树H S T(H i e r a r c h i c a l l y w e l l-S e p a r a t e d T r e e s)的隐私保护方案。该方案中的众包服务器使用预定义的位置点集构建H S T,并计算满足地理不可区分性的位置混淆函数。每个工人从众包服务器下载得到H S T和位置混淆函数,通过位置混淆函数中的概率将真实位置映射到H S T上的一个节点,并 将 该 节 点 提 交 给 众 包 服 务 器。X i o n g等人1 1利用地理不可区分性和指数机制提供了更强的隐私保障,由于更高的隐私级别会导致额外的旅行距离成本,进而提出了一种路径优化算法,以减少空间众包的总旅行距离。L i等人1 2研究了批处理模式下的位置隐私保护任务分配问题,以最大化任务分配的成功率为目标,提出了k-s w i t c h解决方案。该方案使用拉普拉斯机制扰动任务和工人的位置,并根据扰动位置进行任务分配。为了增加任务分配成功率,将距离较近的任务工人对划分到一组并在组内使用同态加密优化任务分配方案。以上工作都是基于地理不可区分性保护位置隐私且没有考虑路网因素,工人的位置隐私有泄露风险且将造成较大的效用损失。2.2 面向路网的空间众包研究面向欧氏空间的空间众包研究使用欧氏距离衡量任务与工人之间的可达性,但在实际生活中工人的行动轨迹受到路网环境限制,因此面向路网的空间众包研究更贴近现实。L i a n g等人1 3研究了面向路网的在线多技能任务分配问题,并证明了该问题是N P难问题,提出了基于固定批处理和动态批处理的算法框架。C o s t a 等人1 4研究了面向路网的单工人任务调度问题,为工人推荐多条互相非支配的执行任务路线。钱勤红等人1 5研究了路网场景下的群组任务匹配和调度问题,提出了基于网格索引的群组任务匹配和调度算法框架。为了避免大量的无效最短路径计算,该框架首先通过网格索引存储的路网信息和工人信息快速过滤掉不满足时间和预算约束的工人;然后,利用基于剪枝策略的搜索算法搜索满足任务约束的有效工人集;最后,通过组建团队算法迭代地选择有效工人加入团队。朱菲等人1 6研究了面向路网的任务点选址问题,通过给工人和用户指定任务点,在节约工人旅行成本的同时减少了用户等待时间。针对传统任务分配方法存在计算速度慢、适用范围小等问题,纪苗苗等人1 7研究了面向路网的空间众包任务分配问题,以任务完成时间最短为目标,提出了基于多智能体强化学习的QM I X-A*算法。以上研究虽然都考虑了路网信息,但他们研究的问题与本文不同,本文研究的是面向路网的空间众包隐私保护批处理任务分配问题,旨在保护工人在路网环境中的位置隐私,并以最小化工人平均旅行距离为目标进行批处理任务分配。3 预备知识和问题定义3.1 地理图不可区分性给定图G=(V,E)代表一个路网,设 为一个扰动机制K输出的节点集合,当给定一个节点vV时,扰动机制K根据概率分布返回一个随机节点,给定隐私参数R+,-地理图不可区分性(-G e o-G r a p h-I n d i s t i n g u i s h a b i l i t y)定义如下:定义1(-地理图不可区分性)给定一个在路网G=(V,E)上的扰动机制K满足式(1):dp(P r(K(v)W),P r(K(v)W)ds(v,v)(1)则称机制K满足-地理图不可区分性。其中,6241C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 3,4 5(8)v,v V,W,ds(v,v)表示2个位置v和v 之间的路网距离。上述定义也可以表述为式(2):v,v V,W,P r(K(v)W)P r(K(v)W)e ds(v,v)(2)地理图不可区分性保证了对于任意的2点v,v V,v和v 的路网距离越短,K(v)和K(v)的概率分布就越相似。另外需要注意的是,地理图不可区分性的定义包含一个表示路网的图,这意味着即使隐私参数相同,隐私保护水平也会随路网的变化而变化。3.2 图指数机制给定隐私参数R+和图G=(V,E),用户的真实位置vV和扰动位置,图指数机制定义如下:定义2(图指数机制)输入真实位置v,输出扰动位置的概率如式(3)所示:P r(G EM(v)=)=(v)e-2ds(v,)(3)其中,为标准因子,(v)=1/e-2ds(v,w)。3.3 隐私保护级别和效用损失S h o k r i等人1 8定义了一个使用距离度量dq的扰动机制K的隐私和效用。一个机制K的效用损失被定义 为如式(4)所示 的服务质量 损失S Q L(S e r v i c e Q u a l i t y L o s s):S Q L(u,K,dq)=r,r u(r)P r(K(r)=r)dq(r,r)(4)其中,r是原始真实位置;r 是机制K扰动后的虚假位置;u(r)是用户的先验分布,表示用户位于位置r的概率。机制K的隐私级别被定义为如式(5)所示的敌手误差A E(A d v e r s a r i a l E r r o r):A E(u,K,h,dq)=r,r,r u(r)P r(K(r)=r)P r(h(r)=r)dq(r,r)(5)其中,h表示敌手推断的映射函数,P r(h(r)=r)表示当敌手观察到扰动位置r 时,估计r为用户真实位置的概率。由上述定义可知,S Q L通过计算真实位置和扰动位置之间的期望距离得到,A E通过计算真实位置和敌手推断位置之间的期望距离得到。由于S Q L和A E可以同时增大和减小,所以本文使用性能指标P C(P e r f o r m a n c e C r i t e-r i a)衡 量 一 个 隐 私 保 护 机 制 的 效 果,且P C=A E/S Q L,P C越大,表示一个机制的效果越好。3.4 问题定义定义3(路网)本文将路网定义为带权无向图G=(V,E),其中节点集合V中的每个节点vi表示路网节点,边集合E中的每条边e=(vi,vj)表示节点vi到vj的路段,边e=(vi,vj)的权值为节点vi到节点vj的最短路网距离ds(vi,vj)。定义4(众包任务)众包任务ti由任务请求者在众包平台上发布,在本文中被定义为ti=(lti,pti,dti)。其中,lti是任务ti的地理坐标即任务所处位置,pti和dti分布表示任务的发布时间和截止时间。定义5(众包工人)在本文中被定义为hj=(lhj,l hj,rhj)。其中,lhj和l hj分别表示工人真实位置和扰动后的位置,rhj表示工人可接收任务的范围半径。定义6(面向路网的隐私保护批处理任务分配问题)给定一个城市的路网信息并将其建模为带权无向图G=(V,E),在一段时间内有工人集合H和任务集合T,每个众包工人的扰动位置为l hj,工人的旅行距离为路网距离ds。在保护工人位置隐私的前提下,执行批处理任务的分配,以最小化工人旅行距离为目标,m i ntiT hjHds(lti,l hj)x(ti,hj)且满足以下约束:(1)x(ti,hj)0,1,tiT,hjH,x取0或1,表示众包平台根据工人扰动位置生成的任务分配方案,即任务ti是否被分配给工人hj。(2)空间约束:d(l hj,lti)rhj,工人扰动位置和任务位置间的欧氏距离d(l hj,lti)不能大于工人的可接收任务范围半径rhj。(3)不变性约束:一个任务分配方案x一旦确定,则不能改变。(4)唯一性约束:tiTx(ti,hj)1,hjHx(ti,hj)1,即一个众包工人一次只能执行一个任务,一个众包任务只能分配给一个工人。4 算法框架4.1 算法框架结构本文提出的算法框架主要包含3个实体:众包服务器、众包工人和边缘服务器。众包服务器通常被认为是不可信的,在本文中众包服务器的功能是7241侯占伟等:面向路网的空间众包隐私保护任务分配算法根据工人扰动位置和任务位置执行任务分配,并将任务分配结果返回给众包工人。众包工人非常重视位置隐私,他们不信任众包服务器,认为其是攻击者。为了保护工人位置隐私,本文引入边缘服务器作为工人的隐私保护代理,工人将真实位置和隐私要求上传至边缘服务器,边缘服务器根据隐私保护要求扰动工人位置并上传至众包服务器。基于此,本文提出了面向路网的隐私保护批处理任务分配算法框架P B T A-R N(P r i v a c y-p r e s e r v i n g B a t c h-b a s e d T a s k A s s i g n m e n t f o r R o a d N e t w o r k)。框架流程如图1所示:(1)众包工人上传自己的真实位置和隐私保护需求到最近的边缘服务器;(2)边缘服务器根据隐私保护需求优化图指数机制并生成位置扰动概率矩阵;(3)边缘服务器作为工人的隐私保护代理上传扰动位置到众包服务器;(4)众包服务器根据工人扰动位置和任务位置执行带权二分图任务分配算法;(5)众包服务器向边缘服务器返回任务分配结果;(6)边缘服务器将分配结果分发给对应工人。F i g u r e 1 F l o w c h a r t o f t h e p r o p o s e d s c h e m e图1 本文框架流程图4.2 图指数机制优化算法地理图不可区分性是一种面向路网的位置差分隐私保护概念,它可以确保对手无法根据用户发布的扰动位置推断出用户真实位置。图指数机制是满足地理图不可区分性的一种机制,用于保护面向路网的位置隐私。但是,在空间众包中,不仅要保护工人位置隐私也要考虑因位置扰动而造成的服务质量损失。如何在保护众包工人位置隐私的前提下控制服务质量损失,从而减小众包工人的平均旅行距离,是本节要解决的一个问题。由于图指数机制G EM的输出范围可以是节点集合V的任意子集,因此可以通过求V的子集得到最佳输出范围,提高图指数机制的性能指标。为了在保护位置隐私的同时控制服务质量损失,为服务质量损失添加最大约束,并提出如式(6)和式(7)所示的优化问题:m a xUV P C(6)s u b j e c t t o S Q L(7)其中,V代表未优化的扰动机制输出范围,U代表优化后的输出范围,为S Q L最大约束。由于一个扰动机制输出范围的组合数为2|V|,根据评价输出范围的性能指标选出一个最优输出范围的计算量过大。因此,本文提出了一种贪心算法来寻找近似最优解,其伪代码如算法1所示。算法1 图指数机制优化算法输入:隐私参数,图G=(V,E),性能指标函数f,约束函数c。输出:输出范围U。S t e p 1 UV;S t e p 2 w h i l e T r u e d oS t e p 3 U0U;S t e p 4 P Cf(G EMU0);S t e p 5 f o r v i n V d oS t e p 6 U Uv;/移除点vS t e p 7 P C f(G EMU);S t e p 8 S Q Lc(G EMU);S t e p 9 i f(P C-P C)0 a n d S Q LS t e p 1 0 UU;S t e p 1 1 P CP C;S t e p 1 2 e n d i fS t e p 1 3 i f U0=US t e p 1 4 b r e a k;S t e p 1 5 e n d f o rS t e p 1 6 e n d w h i l eS t e p 1 7 r e t u r n U;其中,G EMU表示优化后输出范围为UV的图指数机制。首先,算法将输出范围初始化为所有节点的集合。接下来,对于每一个节点,对比从当前输出范围移除该节点前后发生的变化。如果值增加且满足约束函数,则将此节点从当前输出范围移除,重复以上操作直到收敛。与指数机制类似,图指数机制通过控制输出结果的概率实现差分隐私。图2给出了一个经过算8241C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 3,4 5(8)法优化后的概率矩阵示例,其中工人的可能位置为v1,v2,v3,v4,v5,v6,v7,v8,优化后的输出范围为 v1,v3,v5,v6,v8。边缘服务器作为工人的隐私保护代理,负责图指数机制的优化和概率矩阵的生成。由于优化算法不需要交互操作,因此在对工人位置扰动之前可以先执行优化算法。图指数机制优化算法中性能指标的计算需要使用点v与其他节点的路网距离,当工人第一次向边缘服务器发送真实位置v与隐私参数,边缘服务器使用堆优化的迪杰斯特拉算法计算从节点v到其他节点的路网距离,此操作的计算复杂度为O(|E|+|V|l o g|V|),其中V为节点数,E为边数。图指数机制优化算法的关键在于计算服务质量损失S Q L和对手攻击误差A E。根据S Q L和A E的定义,S Q L的计算复杂度为O(|V|),A E的计算复杂度为O(|V|2)。某一节点距离节点v越远,输出该节点的概率就越低,因此可以舍弃较远的节点。可见,图指数机制优化算法的整体时间复杂度小于O(|V|3),大于O(|V|2)。v1v3v5v6v8v1v2v3v4v5v6v7v80.2 0.1 0.2 0.3 0.20.1 0.3 0.1 0.1 0.40.4 0.1 0.2 0.2 0.10.3 0.2 0.3 0.1 0.10.2 0.2 0.1 0.2 0.30.2 0.1 0.3 0.1 0.30.1 0.3 0.2 0.2 0.20.2 0.1 0.1 0.1 0.4F i g u r e 2 E x a m p l e o f p r o b a b i l i t y m a t r i x图2 概率矩阵示例4.3 带权二分图任务分配算法本文提出以最小化工人平均旅行距离为目标的任务分配问题,可以视为是一种以工人旅行距离为权值的二分图最大流问题。本文假设工人和任务位置都可以映射到一个路网节点上。众包服务器首先根据空间约束舍弃不满足条件的工人,之后采用堆优化的迪杰斯特拉算法计算任务和工人扰动位置的路网距离,最后以路网距离(工人旅行距离)为权值构建二分图并执行KM算法。KM算法是一种在多项式时间内查找二分图中最大权值匹配问题的算法。本文带权二分图任务分配算法的伪代码如算法2所示。算法2 带权二分图任务分配算法输入:工人扰动位置集合LH=l h1,l hj,l hn,任务位置集合LT=lt1,lti,ltm。输出:任务工人分配方案X=xk(ti,hj),。S t e p 1 f o r l hj i n LHS t e p 2 f o r lti i n LTS t e p 3 i f d(l hj,lti)rhjS t e p 4 迪杰斯特拉算法计算ds(lti,l hj);S t e p 5 e(ti,hj)ds(lti,l hj);S t e p 6 e n d i fS t e p 7 e n d f o rS t e p 8 e n d f o rS t e p 9 构造二分图;S t e p 1 0 执行标准KM算法;S t e p 1 1 r e t u r n X=,xk(ti,hj),;在执行标准KM算法之前需要做一些预处理,包括根据空间约束去除不符合条件的工人,计算任务和工人扰动位置间的路网距离,这部分的时间复杂度为O(n2)。KM算法的时间复杂度为O(n3)。所以,算法整体的时间复杂度为O(n3)。5 实验及结果分析5.1 实验数据与环境为验证本文算法的有效性,使用位于罗马的公开真实出租车轨迹数据集进行实验,该数据集来自C R AWD A D社区1 9。出租车服务属于空间众包应用的一种,出租车可视为众包工人,乘客可视为众包任务。该数据集包含了近3 0 0辆出租车在3 0天内的G P S坐标。通过分析数据集发现,不同出租车形成的轨迹数量差别较大,选取轨迹数量较多的出租车进行实验。为了评估本文算法的性能,设置了 不 同 的 实 验 参 数,隐 私 参 数的 取 值 在l n(2),l n(8)。在每一批次的任务分配中,工人数量|H|的取值在1 5,4 0,任务数量|T|的取值在5 0,1 0 0。根据众包任务位置分布将分布情况分为3种类型:密集型、散点型及混合型。密集型众包任务分布较为密集,任务间距离较小;散点型众包任务分布更加分散,任务间距离较远;混合型为部分区域分布密集,其余区域分布分散。本文实验在处理器为1.6 GH z I n t e l C o r e i 5-8 2 5 0 U,内存为8 G B的计算机上运行,操作系统为W i n d o w s 1 0。实验使用的编程语言为P y t h o n,使用的集成开发环境为P y C h a r m。5.2 实验评价标准(1)平均旅行距离A TD(A v e r a g e T r a v e l D i s-9241侯占伟等:面向路网的空间众包隐私保护任务分配算法t a n c e)。先前已有大量工作将工人到任务地点的旅行距离作为任务分配的一个重要参考,并以最小化工人平均旅行距离为目标进行任务分配。不同于先前的工作,本文的旅行距离不是简单的欧氏距离,而是工人到达任务点的路网距离。平均旅行距离A TD的计算如式(8)所示:A TD=xi(ti,hi)Xds(ti,hi)/X(8)其中,X表示分配给工人的任务总数,ds(ti,hi)表示工人和任务点之间的路网距离。平均旅行距离越小,效用损失越少。(2)敌手误差A E(A d v e r s a r i a l E r r o r)。敌手只需要知道工人的上传位置、工人的位置分布和工人位置扰动机制,就可以通过贝叶斯方程推断出工人的实际位置。本文使用式(4)量化一个机制的隐私级别。敌手误差越小,隐私保护机制的隐私级别越低。5.3 对比算法(1)拉 普 拉 斯 机 制L A P(L A P l a c e m e c h a-n i s m)1 2。拉普拉斯机制是一种传统并被广泛使用的差分隐私机制,它以较高的概率将一个位置扰动到邻近位置。它的概率分布由二维的平面拉普拉斯机制推出,如式(9)所示:Pl a p(u|u)e-de(u,u)D(R)(9)其中,de为欧氏距离,D(R)为区域R内任意2个位置的最大距离。(2)指 数 机 制E X P(E X P o n e n t i a l m e c h a-n i s m)2 0。指数机制也经常被用来实现差分隐私。在指数机制中需要设计评分函数。给定一个位置,扰动效果越好,评分函数给出的得分越高。在空间众包中,评分函数应该与效用损失成反比,基于此,设计了式(1 0)所示的指数机制:Pe x p(u|u)e2 1-ds(u,u)m a xu*Rds(u,u*)(1 0)(3)图 指 数 机 制G EM(G r a p h E x p o n e n t i a l M e c h a n i s m)5。图指数机制采用指数机制的思想,并进一步考虑了路网,可以得到更高的效用。同时,该机制满足G e o G I,保证了隐私保护效果,扰动概率如式(1 1)所示:Pg e m(u|u)e-2ds(u,u)(1 1)(4)无隐私保护。无隐私保护意味着空间众包平台使用工人的原始位置进行任务分配,其A TD是基于扰动位置进行任务分配的下界。5.4 实验结果分析5.4.1 效用本文将工人平均旅行距离作为任务分配效用,工人平均旅行距离越接近于没有隐私保护的下界,其任务分配效用就越高。图3描述了隐私预算与工人平均旅行距离之间的关系。从图3可以看出,除了没有隐私保护的任务分配算法,其他的算法随着隐私预算的增加,工人旅行距离都随之减少。根据差分隐私的定义,越大隐私保护程度越低,工人位置以更大的概率扰动到更近的位置。因此,工人旅行距离都呈现出下降趋势。在4种隐私保护机制中,拉普拉斯机制产生的工人平均旅行距离最大,这是因为拉普拉斯机制使用欧氏距离且没有考虑路网因素,扰动后的位置在路网上产生的效用损失更大。图指数机制和指数机制在设计过程中使用路网距离,即考虑了路网因素,其效用损失低于拉普拉斯机制的。对于指数机制,本文为其设计了打分函数,使工人位置以更高的概率扰动到效用损失更小的位置。图指数机制并没有采用类似的方法减小效用损失,因此其效用损失更大。本