基于博弈分析的众包交通监测隐私保护机制

何云华　　孙利民*　　杨卫东　　李 红(西安电子科技大学计算机学院　西安　710071)(中国科学院信息工程研究所北京市物联网安全重点实验室　北京　100093)



基于博弈分析的众包交通监测隐私保护机制

何云华①②孙利民*①②杨卫东②李 红②
①(西安电子科技大学计算机学院西安710071)
②(中国科学院信息工程研究所北京市物联网安全重点实验室北京100093)

摘要：众包交通监测利用移动终端上传的GPS位置信息实时感知交通状况，具有广阔的应用前景。然而，上传的GPS信息会泄露用户隐私。该文基于博弈论分析用户上传行为，提出隐私保护的优化上传机制。首先建立用户上传行为与路况服务质量和隐私泄露之间的关系，据此构建不完全信息博弈模型，以便分析用户上传行为；然后，根据用户上传博弈纳什均衡，提出用户终端可控的隐私保护优化上传机制。理论分析表明，该文提出的上传机制最大化用户效用，具有激励相容特性；通过真实数据实验验证，上传机制能够提高用户的隐私保护度，以及算法的激励相容特性。

关键词：众包监测；位置隐私；不完全信息博弈；均衡

1　引言

智能手机在人们生活中迅速发展，预计2015年全球智能手机用户持有量将达到98.2亿。智能手机大都嵌入GPS、摄像头、加速度等传感器，能够采集人类活动和周围环境多类数据。利用大量的个人智能手机和无线网络基础设施，来收集和分析超大规模感知数据的方式，称为众包[1]。众包方式将颠覆传统的实时路况信息采集技术。例如，Google服务器利用Android手机上的地图软件，获取GPS抽样信息，估计道路上的交通状况。相对于传统路况感知方式，如探测车辆、地感线圈、交通照相机等，众包交通监测具有低代价、无需部署、高覆盖区域的特点，有望成为未来交通监测的主要手段。

众包交通监测的广泛应用必须考虑以下3个方面：(1)用户隐私；(2)交通状况预测准确性；(3)用户上传激励机制。其中用户隐私与交通状况预测是一对矛盾体，即道路上上传用户越多，且每个用户上传次数越多，路况估计越准确；但是用户上传越频繁，也越容易泄露自己的位置隐私。

然而，目前的众包交通监测系统，如文献[2，3]都采用匿名技术保护用户隐私。MONTJOYE等人[4]和CHRIS等人[5]对移动用户轨迹的研究表明，尽管匿名消除了明显的标识符，但利用用户移动特性和上传数据的时空特性仍然能够跟踪用户。跟踪攻击防御方法可分为集中式和分布式两种。集中式防御由中心服务器对轨迹数据做处理，如减少记录数据[6]、添加噪声数据[7]、空间混淆[8]等。然而，一旦中心服务器受到攻击，用户隐私将会泄露[6]。分布式防御方法，不依赖于中心隐私服务器。Mix域方法让用户进入Mix域时更新假名，不发送位置信息到服务器，使得攻击者难以区分Mix域中的用户，PPLANISAMY等人[9]考虑车辆密度、Mix形状、位置粒度、移动限制等因素，建立适应于道路网的Mix域模型。LIU等人[10]提出了最优放置Mix域的方法。然而，Mix域中的用户不上传位置信息，严重影响了路况估计质量。文献[11]提出节点在路段上设定的标记点更新位置，标记点的放置确保了节点隐私保护的最小需求距离，并且避免一些隐私特别敏感的位置。由于不同节点在同一位置的隐私级别不同，而且节点隐私随时间和位置变化，因此标记点很难满足所有用户隐私的要求。

本文兼顾路况服务质量和用户个性化隐私需求，基于博弈理论分析了终端用户上传行为与路况服务质量和隐私泄露之间的联系，提出了终端用户隐私保护的优化上传机制。由于用户通常不知道周围道路上其他用户的隐私保护度，因此我们采用不完全信息博弈对位置隐私泄漏建模。根据博弈纳什均衡存在性与唯一性和服务器提供的路况服务反馈信息，提出了移动用户的优化上传策略。该机制不依赖中心隐私服务器，每个用户权衡路况估计准确性和位置隐私，独立地决定是否上传。该机制在满足基本路况估计需求的情况下，最大化用户效用，为用户提供强隐私保护机制。

2　模型假定与问题描述

图1为实时路况监测系统的架构。移动终端用户实时将GPS抽样信息＜location，speed，direction，timestamp＞上传服务器；服务器根据用户上传信息估计当前交通状况，并为用户提供实时路况信息和导航服务。系统将路网分成单个路段，特别划分了直道、岔口、十字路口等3种典型路段。服务器对路况估计的准确性Q，依赖于路段上移动终端用户上传的数量k[11]。假定用户集愿意提供GPS抽样，因为它们期望得到较好的Q值。由于移动终端被不同的个体拥有，假定用户具有不同的隐私级LP是合理的，并且用户上传GPS抽样会带来一定的位置隐私损失c。

图1　众包交通监测模型

2.1 路况服务

路况估计准确性Q与对应路段的上传用户数量k相关，k越大，Q值越大。通过真实数据[12]的实验发现，某一路段i上速度估计的均方差(RMS)与该路段的车辆上传数量ki呈单调递减关系。令路段i上的路况估计准确性，其中1RMS表示归一化的速度均方差，Qi与ki的关系可表示为

其中，α，β的值可根据实验获取的ki和Qi值，通过log函数拟合得到。如图2所示，直道α=5.949×105，β=1.858×104，岔口α=9.397×105，β=1.855×104，十字路口α=1.330×106，β=1.855×104。

我们建立上传策略与服务质量之间的关系式。每个用户有2种可能的策略si：上传(Y)或不上传(N)，根据式(1)，得到路况服务质量：

其中当x=y时，I(x，y)=1，否则I(x，y)=0。

2.2 位置隐私

2.2.1跟踪攻击 攻击者从多个用户的匿名GPS抽样序列中，提取由同一用户产生的GPS抽样序列。攻击者关联先前的上传和下一次上传，找出最接近于预测或者最有可能的上传数据，可表示为[5]

次上传位置为x的条件概率。

2.2.2身份标识攻击 攻击者在给定的某条轨迹情况下，根据边信息[5]推断出发布该轨迹的用户。给定某条轨迹L，可计算[5]

2.2.3 位置隐私量化用户面临着跟踪攻击和身份标识攻击，因此位置隐私可量化为跟踪攻击不正确性[13]和身份标识的不确定性[14，15]。采用正确位置xi与基于的估计值之间的期望距离，来量化跟踪攻击的不正确性(uncorrectness)[13]。表示如式(5)：

熵H给出了在P中查明唯一结果IDi的难易程度。熵值越高，攻击者的确定性(certainty)越低。当满足均匀分布时，熵值达到最大值。

归一化得到，用户i在决定上传与否前的位置隐私：

用户上传数据会带来一定的位置隐私损失。假设用户i上传带来的隐私损失为ci，用户隐私度可表示为

2.3 问题描述

(1)用户i可能不知道路段上其他用户的隐私度；

(2)如何估计路段上的最低服务质量需求Qmin。

针对因素(1)，我们采用不完全信息博弈[14]引入自然作为参与者，为路段上用户分配一个类型θ，服从同一概率分布f(θ)，类型θ表示用户在该路段上的隐私度。每个用户知道路段上其他用户的隐私度分布，但不知道某个用户的隐私度。针对因素(2)问题，我们利用服务器的全局视角，根据路段类型和GPS抽样的平均速度，实时估算各路段的最低服务质量需求。虽然我们能够采用全局算法使得用户隐私度达到整体最优，但可能存在某个用户为增加其效用而改变上传策略，因此所设计的机制需满足激励相容特性[1]。

3　博弈建模

博弈论适合描述、预测和解释参与者的行为，逐渐被应用于解决移动网络中的安全与隐私问题[14，16，17]。黄等人[16]基于演化博弈研究无线网络物理层的安全协作方法。Freudiger等人[14]采用不完全信息博弈，研究Ad hoc网络中的位置隐私保护机制Mix-zone中节点的非合作行为。SHOKRI等人[17]采用STACKELBERG博弈优化设计LBS位置隐私保护机制。本文则采用不完全信息博弈论研究众包交通监测中终端用户的上传行为，优化设计终端用户的隐私保护上传机制。

3.1 纳什均衡

由于用户上传博弈是不完全信息博弈，因此，首先引入节点上传行为博弈的贝叶斯纳什均衡[14]的概念：

用户上传博弈的贝叶斯均衡，可以通过比较上传和不上传的平均收益得到，如式(11)所示。

4　上传机制

本节设计强隐私保护的位置信息上传机制UploadGame，不仅提供需求的路况估计质量Q，而且提供强隐私保护LP，达到用户隐私保护度和路况质量的整体最优性。该机制利用服务器为用户提供路况质量需求反馈，实时调整路况估计质量，避免了因节点自由决定是否上传不能满足路况估计需求的缺陷。另外，该算法以用户为中心，节点能够自主决定是否上传，满足其个性化的隐私需求。UploadGame算法分为2个阶段，服务器反馈阶段和节点选择上传阶段。

(1)服务器反馈阶段：服务器根据历史交通状况，确定当前路况估计需求，为路段上用户提供上传数量需求的反馈。服务器首先计算最低路况估计质量需求Qmin，然后由式(4)可求得需要上传节点数。假定Qmin与历史估计的平均速度v之间的关系满足正态分布，那么Qmin可由式(14)给出：其中ρ＞0为系统参数，μ和σ分别表示速度v的平均值和标准差。式(14)反映了节点速度很低时，路况估计质量需求不高，这是由于拥塞时速度不会产生很大的变化；速度很高，路况估计质量需求也不高，因为此时交通顺畅，不需要进行精确估计。当然也可采用其他函数关系进行估计，如用户更关心交通事故发生时，可采用Q与Δv之间的函数关系来捕捉路况变化。

(2)节点选择上传阶段：节点基于服务器的反馈，计算隐私损失阈值cmax，然后根据该阈值来决定是否上传。如果节点知道其他节点的隐私损失，如，容易得到隐私损失阈值。然而，节点通常不知道其他节点的隐私度和隐私损失，因而需要估计出ck的值。假定隐私度与隐私损失满足，该式反映了用户隐私保护度越高其上传隐私损失越小，也即长时间未上传的节点上传所带来的隐私损失低。由节点隐私度服从概率分布可得到

算法1UploadGame算法。

//阶段1服务器确定上传用户数量k

(2)计算上传用户数量k。 根据式(1)以及当前的服务质量需求Q(v)，计算。

//阶段2用户上传决策

(3)根据式(16)以及阶段1求得的上传用户数k，计算上传阈值。

(5)else si=N。否则节点不上传位置信息。

4.1博弈分析

4.1.1纳什均衡纳什均衡的存在性和唯一性，能够说明算法1的收敛性，由定理1给出。

定理1算法1存在唯一的纳什均衡。

因此函数g(x)单调递减。设c(x)为[1，n]上的连续函数，且满足。函数的一阶导数。由算法1得到，根据介值定理，存在，使得。

所以不上传总为最优策略。

4.1.2激励相容下面将证明算法1具有激励相容特性[1]。激励相容是机制设计中最基本的概念，保证参与者根据真实类型作出决策是其最优反应策略，消除用户对其他用户操纵市场给其带来较大损失的担忧。

定义2一个机制是激励相容的，如果直接显示机制存在纯策略均衡，其中。

换句话说，每个用户通过报道真实隐私损失，能够最大化其效用。

定理2算法1具有激励相容特性。

证明设节点隐私损失为ci，节点选择隐私损失。当时，如果或，将不会影响用户的上传策略，其效用不变；如果，节点将不上传，其效用

此时节点能够改变其策略来增加效用，因此节点谎报隐私损失会降低其效用。

此时节点能够改变其策略来增加效用，因此节点谎报隐私损失会降低其效用。

综上所述，算法1具有激励相容特性。

5　仿真实验

本文采用北京2009年3月出租车收集的GPS轨迹数据[12]作为仿真数据集，选取交通高峰期和交通空闲期2种场景。我们将研究的地理区域递归分为4个方格，每个方格用三元组＜level，x，y＞表示，其中level表示递归层数，x，y分别表示相对左上角的偏移量。这里我们取level=3，也即将区域分为8 ×8个块。

我们比较了UploadGame与简单的自主上传机制在隐私保护和路况估计质量上的性能。在简单的自主上传机制中，用户根据具有固定w值的上传阈值来决定是否上传。在交通空闲期，用户1沿着路径1行驶从＜3，8，1＞到＜3，2，7＞，用户2沿着路径2行驶从＜3，1，8＞到＜3，8，3＞；在交通高峰期，用户3沿着路径1行驶，用户4沿着路径2行驶。用户隐私级和路况估计质量每隔2 min计算一次，结果在图3、图4中给出。观察到，用户隐私级在交通高峰期比交通空闲期要高，因为交通高峰期有更多的用户在道路上，增加了跟踪和身份识别的难度。正如所期望的，在交通高峰期，UploadGame机制下用户的隐私保护度高于简单机制(＞25%)；在交通空闲期，UploadGame机制提供的隐私保护度与简单机制相当。图3中的突然上升的点表示用户正经过高度混淆区域，如十字路口；突然下降点，表示用户在此时上传了自己的位置，其隐私泄露风险增加。

图3　不同交通场景下用户的隐私级

图4　不同交通场景下用户获取的路况估计质量

图4阐述了图3对应的交通高峰期和交通空闲期，用户获得的路况估计质量变化。交通高峰期的路况估计质量高于交通空闲期，因为交通高峰期更多用户上传。虽然交通空闲期，路况估计质量达不到83%，但是此时用户仅关心交通是空闲的，不关心估计的准确性。但为了处理一些意外事件，UploadGame机制鼓励用户上传。因此图4中的UploadGame机制的路况估计质量高于简单机制。在交通高峰期，UploadGame机制能够满足最低路况估计质量需求(QoS=0.83)。

我们还验证了UploadGame机制的激励相容特性。分别在交通空闲和交通高峰期的＜3，3，4＞块中随机选取了4个用户，并允许隐私损失不同于其真实隐私损失。如图5所示，用户根据真实隐私损失进行决策时，其效用达到最优。图5中标记点是用户真实隐私损失所对应的效用值，从图中可以看出用户选取其他隐私损失时，不能增加其效用。

6　总结

图5　UploadGame的激励相容特性

本文基于博弈论分析设计众包监测系统的隐私保护机制，满足基本路况估计质量的同时，提高用户隐私保护度，最大化用户效用。首先建立用户上传行为与路况服务质量和隐私泄露之间的关系，构建终端用户上传博弈模型；然后，根据博弈纳什均衡，设计用户终端可控的隐私保护优化上传机制UploadGame，理论分析该机制的收敛性和激励相容特性。最后通过真实数据的仿真实验分析Upload-Game的性能优势，验证了UploadGame的激励相容特性。

参考文献

[1]YANG D J，XUE G L，FANG X，et al.Incentive mechanisms for crowdsensing:crowdsourcing with smartphones[J].IEEE/ACM Transactions on Networking，2015，99:1-13.

[2]GAO S，MA J F，SHI W S，et al.TrPF:A trafectory privacy-preserving framework for participatory sensing[J].IEEE Transactions on Information Forensics and Security，2013，8(6):874-887.

[3]MOHAN P，PADMANABHAN V N，and RAMJEE R.Nericell:rich monitoring of road and traffic conditions using mobile smartphones[C].Proceedings of the ACM Conference on Embedded Networked Sensor Systems，North Carolina，2008:323-336.

[4]MONTJOYE Y A，HIDALGO C A，VERLEYSEN M，et al.Unique in the crowd:The privacy bounds of human mobility[R].Nature Science Report，Cambridge，2013.

[5]CHRIS M，DAVID Y，and NUNG Y.Privacy vulnerability of published anonymous mobility traces[J].IEEE Transactions on Networking，2013，21(3):720-733.

[6]孙利民，李红，王笑寒，等.物联网位置隐私保护综述[J].软件学报，2014，25(s1):1-10.SUN Limin，LI Hong，WANG Xiaohan，et al.Survey on the location privacy preservation in the internet of things[J].Journal of Software，2014，25(s1):1-10.

[7]SHI E，CHAN T H，RIEFFEL E，et al.Privacy-preserving aggregation of time-series data[C].Proceedings of 18th Network ＆ Distributed System Security Symposium，California，2011:1-17.

[8]HOH B，GRUTESER M，XIONG H，et al.Achieving guaranteed anonymity in gps traces via uncertainty-aware path cloaking[J].IEEE Transactions on Mobile Computing，2010，9(8):1089-1107.

[9]PALANISAMY B and LIU L.Attack-resilient mix-zones over road networks:architecture and algorithms[J].IEEE Transactions on Mobile Computing，2015，14(3):495-508.

[10]LIU X X，ZHAO H，PAN M，et al.Traffic-aware multiple mix zone placement for protecting location privacy[C].Proceedings of the 31rd Annual IEEE International Conference on Computer Communications，Florida，2012:972-980.

[11]HOH B，IWUCHUKWU T，JACOBSON Q，et al.Enhancing privacy and accuracy in probe vehicle based traffic monitoring via virtual trip lines[J].IEEE Transactions on Mobile Computing，2012，11(5):849-864.

[12]DATATANG Company.Taxi GPS data of one city in north of china(200903)[OL].http://dx.doi.org/10.1287/mnsc.1040.0270.2014.12.

[13]SHOKRI R，THEODORAKOPOULOS G，BOUDEC J L，et al.Quantifying location privacy[C].Proceedings of IEEE Symposium on Security and Privacy，California，2011:247-262.

[14]FREUDIGER J，MANSHAEI M H，HUBAUX J P，et al.Non-cooperative location privacy[J].IEEE Transactions on Dependable and Secure Computing，2013，10(2):84-98.

[15]葛国栋，郭云飞，刘彩霞，等.内容中心网络中面向隐私保护的协作缓存策略[J].电子与信息学报，2015，37(5):1220-1226.doi:10.11999/JEIT140874.GE Guodong，GUO Yunfei，LIU Caixia，et al.A collaborative caching strategy for privacy protection in content centric networking[J].Journal of Electronics ＆ Information Technology，2015，37(5):1220-1226.doi:10.11999/JEIT-140874.

[16]黄开枝，洪颖，罗文宇，等.基于演化博弈机制的物理层安全协作方法[J].电子与信息学报，2015，37(1):193-199.doi:10.11999/JEIT140309.HUANG Kaizhi，HONG Ying，LUO Wenyu，et al.A method for physical layer security cooperation based on evolutionary game[J].Journal of Electronics ＆ Information Technology，2015，37(1):193-199.doi:10.11999/JEIT140309.

[17]SHOKRI R，THEODORAKOPOULOS G，TRONCOSO C，et al.Protecting location privacy:Optimal strategy against localization attacks[C].Proceedings of 19th ACM Conference on Computer and Communications Security，California，2012:617-627.

何云华：男，1987年生，博士生，研究方向为车载网安全与隐私.

孙利民：男，1966年生，研究员，研究方向为物联网安全、工业控制安全及位置隐私等.

杨卫东：男，1977年生，副教授，研究方向为车载网安全.

李红：男，1989年生，博士生，研究方向为位置隐私.

Enhancing Privacy Preserving for Crowdsourced Monitoring——A Game Theoretic Analysis Based Approach

HE Yunhua①②SUN Limin①②YANG Weidong②LI Hong②
①(School of Computer Science，Xidian University，Xi’an 710071，China)
②(Beijing Key Laboratory of Internet of Things Security，Institute of Information Engineering，Chinese Academy of Sciences，Beijing 100093，China)

Abstract:Crowdsourcing traffic monitoring is a promising application，which exploits ubiquitous mobile devices to upload GPS samples to obtain live road traffic.However，uploading the sensitive location information raises significant privacy issues.By analyzing the upload behavior of mobile users，this paper designs a privacy preserving traffic data collection mechanism.Using the relationships among the traffic service quality，privacy loss and the upload behavior，an incomplete information game is built to analyze the upload behavior of users.Based on the existence and uniqueness of Nash equilibrium in this game，a user-centric privacy preserving traffic data collection mechanism is proposed，which can maximize the utilities of users，and this mechanism has a feature of incentive compatible.Finally，the experimental results on real world traffic data confirm the effectiveness of privacy protecting and the feature of incentive compatible.

Key words:Crowdsourced monitoring; Location privacy; Incomplete information game; Equilibrium

基金项目：国家自然科学基金(61472418，61202099)，中国科学院先导专项基金(XDA06040100)

*通信作者：孙利民sunlimin@iie.ac.cn

收稿日期：2015-06-15；改回日期：2015-09-17；网络出版：2015-11-19

DOI:10.11999/JEIT150721

中图分类号：TP309.2

文献标识码：A

文章编号：1009-5896(2016)02-0340-07

Foundation Items:The National Natural Science Foundation of China(61472418，61202099)，The Strategic Priority Research Program of the Chinese Academy of Sciences(XDA06040100)