许建秋,黄火荣
(南京航空航天大学 计算机科学与技术学院,南京 210016)
近年来,多种运动方式成为一个新的研究问题[1-3],它针对不同环境下的移动对象,例如城市道路网、步行区域、公共交通系统等.驾车是移动对象常见的运动方式,除此之外还有很多其他形式.由于城市公共交通系统的快速发展,地铁、城市快速公交成为大多数人出行的主要交通方式,其优点在于廉价、快速、免停车.此外,智能手机的发展带来了出租车叫车软件(例如滴滴和快的)的发展,用户可以随时发送叫车请求,使得选择出租车出行的用户不断增加.目前,主要通过分析打车软件记录、公交车刷卡记录、地铁进出站刷卡等获取用户的运动方式.此外,也有学者通过对原始GPS数据进行分析并结合背景地图数据(例如道路网、公交线路),推测出室外运动方式,准确率高达93.5%[4].
基于位置服务的隐私保护是数据库隐私保护的一种,国内外已有不少相关研究工作[5-9].但是已有的工作主要侧重于位置,尚没有针对运动方式的隐私保护工作.对移动用户而言,除了空间、时间信息,运动方式也是个人信息的一种.一方面,它可以丰富移动对象信息的描述;另一方面,作为个人隐私数据对用户行为分析具有重要参考价值.例如,如果某用户经常采用公共交通方式,那么可以推测该用户很可能不属于高收入人群;如果某用户周末的运动方式以步行和自行车为主,可以推测此用户有运动爱好;对经常使用打车软件的用户群,可以对他们的路线进行分析以推荐拼车方案.运动方式数据反映用户个人行为,从数据隐私角度应当提供一种有效的保护方法以避免被非法获取.
本文在移动对象通用模型基础之上[10],提出了一种针对室外和室内的多种运动方式的隐私保护方法,用于支持包含运动方式的范围查询.这类查询侧重移动对象在不同环境的变化(位置和运动方式)[11],例如“张三何时在公交车站X上车”(步行-公交车),“张三何时离开办公大楼之后乘坐出租车去火车站”(室内-步行-出租车).
本文针对包含多种运动方式的移动对象,提出了一种用于范围查询的运动方式数据保护,包含位置模糊和查询重设两种措施.该方法对移动对象精确运动方式保护,以避免将真实准确的数据返回给非法用户.对两种措施进行了分析对比,并介绍了如何在现有的系统中实现该方法.此外,提出了具有不同保护粒度的方法以适应不同的应用需要.文章结构如下:章节1介绍了相关研究现状,章节2定义了运动方式隐私保护问题,章节3给出了解决方法,包含位置模糊和查询重设,并进行了分析.章节4介绍了不同保护粒度,章节5总结全文.
图1给出了两条包含多种运动方式的移动对象轨迹,详细内容如下:
(a)A步行到B(停车场),驾车到C(办公大楼),进入室内;
(b)A步行到B(公交车站),坐公交车到C(地铁站),乘坐地铁到D,步行到E(办公大楼),然后进入室内.
上述运动过程涉及多个环境,包含道路网、步行区域、公交系统和室内,用户信息包含时间、位置和运动方式.由于环境特性不同,在位置表示、运动函数定义和数据管理上都有不同的要求,需要有效的方法能对多种类型数据处理.移动对象通用位置模型[10]定义了一个统一的结构表示移动对象在不同环境下的精确位置和运动方式,包括:道路网、公交系统(公交车和地铁)、行人步行区域、室内环境等.每一种环境对应相应的运动方式,例如道路网包含驾车、出租车、自行车.定义1给出了运动方式集合.
图1 多种运动方式移动对象示例Fig.1 Example of moving objects with multiple transportation modes
定义1 运动方式:TM={驾车,公交车,地铁,自行车,步行,出租车,室内}
多种环境移动对象的位置定义方法是基于环境建模和引用表示法.首先,对不同移动对象环境划分并建模,定义相应数据类型表示不同空间对象.其次,采用引用法将位置表示映射到底层空间对象,图2给出了通用位置定义示例图.原始位置数据有多种形式,例如GPS数据、公交刷卡数据,通用位置表示将他们在统一模型下定义.该方法将位置映射到空间对象上,空间对象由不同的数据类型定义,表示各环境中的实体对象,例如道路、地铁线路等.运动方式隐私保护建立在通用位置之上,将位置映射到空间对象,但是不给出精确信息.
图2 通用位置表示Fig.2 Generic location representation
多种运动方式移动对象涉及多个环境,每个环境下的空间对象由不同的数据类型定义.定义2给出了不同空间对象的通用表示.
定义2 空间对象
空间对象由三元组构成o(id,T,V),其中id是唯一对象标识,T是数据类型,V是值.
o(id,T,V)可支持二维和三维空间对象.具体来说,线表示道路、多边形表示步行区域,在三维室内环境定义相应数据类型表示房间、走廊等,详细数据类型见文献[10].所有空间对象可由集合O=∪oi表示.
位置隐私是数据隐私的一种,对用户位置提供一种有效的保护方法[12-13].已有不少关于保护用户位置隐私的策略,如删除标识性信息(例如人名)、公布部分数据、位置模糊表示等.常见的k-匿名方法根据查询属性返回至少k-1个符合条件的记录,使得所查找的精确结果不能够在这k-1个记录中被区分出[14].这种方法已经被应用到基于位置服务中,k-匿名条件的关键技术是迷惑方法[15],即对用户的敏感时空信息增加不确定性使得非法者无法辨别重要的时空数据.文献[16]通过定义用户频繁路径和非频繁路径向服务请求提供特定的k-匿名轨迹.
位置模糊是位置隐私保护的一种常见方法[9,17],目的是避免将真实的准确数据返回给非法用户.通过发送真实位置邻近的某个位置,或者用一个区域、一组位置来表示.图3给出了通过区域模糊表示位置的方法.
图3 位置隐私保护示例Fig.3 Example of location privacy preserving
文献[9]采用地图数据匿名方法,组合一组兴趣点用于在敏感位置周围创建模糊区域对数据进行保护.由于基于匿名和模糊位置的方法会增加计算和通信的代价,且不能提供一种严格的隐私机制,有学者提出了基于隐私信息获取的方法处理范围和最近邻查询[18].在没有使用模糊区域的情况下,用户的位置也可以得到保护[19].
常见的基于位置隐私保护的查询有范围查询[20-22]和k-近邻[23-24],主要是提供了一种保护措施对敏感位置实施保护.文献[13]提出了基于位置隐私保护的三类新查询,①公共数据的私有查询;②私有数据的公共查询;③私有数据的私有查询,从数据和查询用户两个方面考虑隐私保护.针对轨迹数据,有不同的保护方法,例如通过组合取样和差分[25],对查询审计阻止隐私攻击[26].
已有的工作主要从用户匿名、时空/空间模糊表示等方面提供隐私保护,处理的数据包含时间和空间两种,但是没有提供对运动方式的保护方法.与传统的移动对象轨迹不同,包含多种运动方式的移动对象在不同环境下运动,需要一种有效方法在保证查询效率的情况下对各种环境统一处理.
在已有的模糊位置保护措施下,如果恶意用户得到了准确的运动方式数据,借助此信息结合背景地图数据同样可以精确定位用户位置,这使得现有的保护技术失效.考虑图1(a)的运动轨迹,采用位置模糊表示给出一个区域表示用户位置.如果运动方式“驾车”给出,可以搜索这个范围内所有的停车场以确定用户的位置.图4(a)显示了这个区域里的停车场,只包含2个.对于公交车和地铁这两种公共交通方式,由于用户的位置及行为变化受特殊位置影响(车站),因此很容易定位用户位置.对于图3的模糊位置定义(用一个区域估计表示),通过搜索这个区域里所有的公交车站,并结合分析下一个时间的位置几乎可以准确定位用户位置,见图4(b).
图4 结合背景地图和运动方式Fig.4 Combine underground maps and transportation modes
多种运动方式范围查询由三元组表示Q(t,s,m),t表示时间,s为空间范围,m为运动方式.该查询返回在t时间位置在s区域里且运动方式符合m的移动对象.运动方式可为单个、多个或者一个序列,举例如下:
·单个Qsin(查询1) 返回在t时间以m={步行}通过区域s的移动对象;
·多个Qmul(查询2) 返回在t时间以m={公交车,步行}通过区域s的移动对象;
·序列Qseq(查询3)
返回t时间内区域s中具有这种顺序的移动对象 m=〈出租车,步行,室内〉.
与传统的范围查询不同,新查询需同时对时间、空间和运动方式检测,只有3个条件同时满足的才符合查询要求.其中,当运动方式定义为一个序列时,需要符合时间先后顺序.序列范围查询可以反映移动对象不同运动方式的转换,有很多应用实例,例如:
·查询4
返回t时间在公交车站(地铁站)X乘坐线路A的对象m=〈步行,公交车〉.
·查询5
返回t时间离开办公大楼坐出租车去火车站的对象m=〈室内,步行,出租车〉.
运动方式范围查询反映移动对象位置和运动方式的变化,能够深入分析用户行为.从数据隐私角度需要一种有效的保护方式避免将精确数据返回给非法查询用户.
采用位置模糊法,可对通用移动对象位置进行粗糙表示.通用移动对象位置定义由两部分构成:①空间对象;②相对位置.前者定义移动对象的环境和范围,后者表示精确位置.位置模糊表示将相对位置省略,只通过引用空间对象定义位置.空间对象具体可为某条道路、某个步行区域、某条公交线路等,这样查询用户只得到一个范围而非精确结果.
定义3 通用位置模糊定义
具有隐私保护的位置由Gloc(id,m)表示,id空间对象标识,依赖函数f: → int O完成从标识到对象的映射,m∈TM为运动方式.
通用位置模糊法将位置表示映射到一个空间对象,由数据类型线、区域、室内三维区域定义,这不同于传统的用矩形框估计表示位置.提出的方法适用于多个环境,通过记录空间对象标识完成定位.当需要获取此空间对象的位置范围时,对标识进行解析访问相应对象集合获取数据.图5给出了一个示例图,位置模糊表示分为两个步骤:①已知对象标识,定义解析函数分析标识对应的空间环境,即这个标识是对应道路、公交线路、步行区域还是室内环境;②根据对象标识在相应的空间对象集合中查找并获取数据.例如已知该标识对应某条公交线路,可访问公交线路对象集合.每条公交线路由一个序列构成,每个元素表示两个相邻站点的线路(折线表示).通过对所有元素进行“并”操作可获取这条线路完整信息,用于确定对象所在位置范围.
图5 位置模糊定义Fig.5 Cloak location definition
范围查询对运动方式进行了准确定义,如果将查询结果返回给非法查询则泄露了用户个人行为.问题的关键是查询对运动方式进行了准确的定义.针对这一问题,本文设计了一种方法对运动方式进行保护.在用户发出查询后,将查询递交给数据库系统执行引擎之前,增设一个保护层用于对查询运动方式进行重新设定.图6给出了基于运动方式保护的方法示例图.
图6 运动方式保护Fig.6 Transportation modes preserving
在用户提交一个查询后,为避免将精确的运动方式返回,对查询中的运动方式参数进行重新设定以模糊化运动方式或者变化运动方式之间的关系.之后,将保护后的运动方式作为参数传递给执行引擎.保护处理过程先提取运动方式参数,判断是单个、多个还是序列查询.依据不同的参数,具体方法如下.
·单个
将单个运动方式扩展为两个运动方式,返回的结果中除包含用户指定的运动方式还有一个新增的运动方式.以查询1为例,可将Qsin={步行}扩展为{步行}∪{自行车},即返回在t时间以步行或者自行车方式通过区域s的移动对象.这个新增的运动方式称为伪造运动方式.
·多个
将包含多个运动方式的查询分解为多个查询,每个查询包含一个运动方式.以查询2为例,Qmul={公交车,步行}被重设为Qsin={公交车}∪Qsin={步行}.返回的移动对象运动方式包含公交车或者步行,同时也存在包含两个运动方式的移动对象.
·序列
查询中的运动方式满足时间先后顺序,为避免将此信息暴露给非法查询用户,序列查询将被重设为多个运动方式查询,即只考虑指定的运动方式是否存在,不对时间顺序关系加以限定.以查询3为例,Qseq=〈出租车,步行,室内〉重设后的结果为Qmul={出租车,步行,室内}.
根据文献[2]对运动方式的分析,不同运动方式一般通过步行进行连接,例如〈公交车,步行〉、〈步行,地铁〉、〈室内,步行,驾车〉.但是,〈公交车,驾车〉和〈地铁,室内〉的运动方式很少,不同环境之间都会存在一段步行完成不同运动方式的转换.因此,序列查询可以用如下形式描述.
定义4 序列查询
Qseq=〈方式1,步行,方式2〉,方式1,方式2∈TM\{步行}或者方式1、方式2为空.
方式1和方式2之间不会直接发生转换,需要借助步行方式连接.对序列查询重设后,返回的移动对象运动方式将会如下两种形式出现:①〈方式1,步行,方式2〉;②〈方式2,步行,方式1〉.返回的移动对象中包含了查询指定的运动方式,但是在顺序上给出了两种可能,使非法用户不能精确获取顺序关系从而对用户行为进行了保护.综合上述3种不同运动方式查询,图7给出了运动方式重设算法.
图7 运动方式重设算法Fig.7 The algorithm of resetting transportation modes
针对位置模糊和运动方式重设两种数据保护方法,从数据保护层次、应用性、查询通用性等几个方面进行分析比较,见表1.
表1 数据保护方法比较Tab.1 Comparison of data preserving methods
通过表1的分析,位置模糊方法需要对数据进行预处理,将精确位置隔离给查询用户,普遍适用于基于多个环境的位置隐私保护.但是这种方法侧重位置信息保护,没有对运动方式保护.另一方面,通用环境下的模糊位置表示方法受底层空间对象影响,模糊位置有较大的伸缩空间.具体来说,在道路网中存在较短的道路,如果模糊区域在一个较短的道路上,结合速度、方向信息可以较准确定位移动对象位置.如果模糊区域位于室内环境,在选取模糊位置时选用整个建筑范围还是某个房间的空间范围是一个有待定义的问题.
运动方式重设针对多种运动方式范围查询,此类查询是多种运动方式移动对象的常见查询,并已有相应的索引和查询算法[11].数据库管理系统在对原始数据管理不变的情况下,通过增加一个保护层对用户查询重设使得返回的移动对象中既包含了查询条件的对象也包含了类似运动方式的对象.这使得非法查询用户不能够准确得知运动方式关系.从系统实现角度,这种方法可以和已有的机制匹配且不影响查询效率,从而构成完整的具有隐私保护功能的多种运动方式移动对象数据库管理系统.
基于位置的数据隐私保护方法将用户准确位置用一个区域表示,区域的大小反映出数据保护程度.一方面需要对用户信息隐藏,另一方面也要保证一定有效质量的服务.因此,这个区域的大小决定了隐私保护度和服务质量的关系.依据本文3.1提出的方法,通过空间对象标识获取被引用的空间对象,从而确定对象所在位置范围.在此基础之上,提出具有不同保护度的位置模糊表示法.
定义5 位置保护度
具有不同隐私保护度的位置由Gloc(id,m,off1,off2)(off1,off2为实数)表示,[off1,off2]表示相对于空间对象的位置范围,即准确位置在off1和off2之间.
依据不同的空间对象,[off1,off2]具有不同的语义,下面解释每个环境的含义.
·道路网
此环境下的运动方式包含{驾车、出租车、自行车},在已知道路标识的条件下,off1(off2)表示相对于道路起始位置的距离,通过添加[off1,off2]可知移动对象位于该道路的位置.存在两个极限情况:①off1=0,off2为道路长度;②off1=off2.情况①对位置进行高度保护,将整条道路用于表示位置.情况②没有保护机制,因为已经精确得知位置信息.除①和②两种极限情况,其他取值的[off1,off2]决定着对用户位置的保护程度.|off2-off1|越小,保护度越低,反之亦然.
·公交车/地铁
在公共交通系统下,[off1,off2]有两种含义.第一种,当off1和off2取值为整型时,其值表示在这条公交线路的站点,如off1=3,off2=5,表示位置位于第3站和第5站之间,与道路网相同,|off2-off1|越小,保护度越低,反之亦然.第二种,当off1和off2取值为实数时,表示距离这条线路起始位置的距离,与道路网含义一致.
·步行区域
用一个多边形表示城市中可供行人步行的区域.为有效管理这个复杂的多边形,采用多边形三角划分方法,将此多边形分解为一组三角形.每个空间对象标识对应着一个三角形.这种环境下的off1和off2有两种取值:①off1和off2表示在这个三角形内的相对位置,此时可精确获取位置;②off1和off2均没有定义,则用这个三角形区域估计表示移动对象位置.
·室内
与其他环境不同,室内环境的保护程度由id和off1、off2共同决定.采用高度保护方法,id对应某个建筑,off1和off2为空,用这个建筑的范围表示对象位置.如果将保护度降低,id对应建筑内的某个房间,可以是办公室、走廊、会议室等,这种方法将位置限定在某个房间.如果需要精确定位位置,则用off1和off2表示在某个房间的相对位置.具体设定方法为:用一个矩形框表示房间的二维空间范围,将off1和off2设定为相对此矩形框左下角在x和y轴上的距离.
运动方式的数据保护度关键在如何对运动方式进行重设,针对不同的运动方式查询有不同的重设方法,产生的保护度也不同,均可由算法ResetMode实现,下面逐一介绍.
·单一
依据章节3.2的方法,通过对运动方式扩充以返回包含指定运动方式和伪造运动方式的移动对象.以运动方式的平均速度作为比较参数,如果这个伪造运动方式接近指定运动方式,则为高度保护.如果这个伪造运动方式远离指定运动方式,则为低度保护.依据平均速度分析数据可以很容易判断不同运动方式的轨迹.以查询1为例,运动方式扩展为{步行}∪{室内}为高度保护,而扩展为{步行}∪{驾车}为低度保护.
·多个
当多个运动方式作为查询条件时,采用分解方法使其成为多个集合.高度保护下,分解后的每个集合仅包含一个运动方式.假设|Qmul|=m,分解后为且||=1.采用这种方法,只要移动对象包含任意一个都作为结果返回.以查询2为例,只要包含公交车或者步行方式的都将被返回.低度保护下,分解后的每个集合可包含多个运动方式.例如,Qmul={公交车、步行、地铁},一种重设后的结果为={公交车、步行}∪={步行、地铁}.与高度保护方法相比返回对象数目减小,同时每个对象同时包含两种指定的运动方式.极限情况下分解后的集合中元素数目等于m,此时将以用户指定的运动方式执行查询,没有保护度.
·序列
此查询下运动方式需要符合时间先后顺序.高度保护方式将忽略顺序,即章节3.2中的方法.低度保护方式将该序列拆分成若干个子序列,将这些子序列作为查询条件.以查询3为例,Qseq=〈出租车,步行,室内〉,可分解为=〈出租车,步行〉和=〈步行,室内〉.在极端情况下,拆分后的序列和用户指定序列相同,则没有保护机制.
本文给出了一种针对多种运动方式的移动对象保护方法,用于处理范围查询,可对单一方式、多个方式和序列方式查询提供保护,避免将用户准确的运动方式提供给非法查询者.此方法包含位置模糊和查询重设两个方面,并进行了分析比较,并给出了具有不同保护程度的数据隐藏方法.
[1]ZHENG Y,LIU L,WANG L,et al.Learning transportation mode from raw GPS data for geographic applications on the web[C]//Proceedings of the 17th International Conference on World Wide Web.New York:ACM,2008:247-256.
[2]ZHENG Y,CHEN Y,XIE X,et al.Understanding transportation modes based on GPS data for Web applications[J].ACM Transactions on the Web,2010,4(1):495-507.
[3]REDDY S,MUN M,BURKE J,et al.Using mobile phones to determine transportation modes[J].ACM Transactions on Sensor Networks(TOSN),2010,6(2):article 13.
[4]STENNETH L,WOLFSON O,YU P S,et al.Transportation mode detection using mobile phones and GIS information[C]//Proceedings of the 19th ACM SIGSPATIAC International Conference on Advances in Geographic Information Systems.New York:ACM,2011:54-63.
[5]BETTINI C,WANG X S,JAJODIA S.Protecting privacy against location-based personal identification[C]//2nd VLDB Workshop Secure Data Management.Berlin:Springer-Verlag,2005:185-199.
[6]薛娇,刘向宇,杨晓春,等.一种面向公路网络的位置隐私保护方法[J].计算机学报,2011,34(5):865-878.
[7]霍峥,孟小峰.轨迹隐私保护技术研究[J].计算机学报;2011,34(10):1820-1930.
[8]田秀霞,王晓玲,高明,等.数据库服务—安全与隐私保护[J].软件学报,2010,21(5):991-1006.
[9]CICEK A E,NERGIZ M E,SAYGIN Y.Ensuring location diversity in privacy-preserving spatio-temporal data publishing[J].the VLDB J,2014,23(4):609-625.
[10]XU J,GÜTING R H.A generic data model for moving objects[J].Geoinformatica,2013,17(1):125-172.
[11]XU J,GÜTING R H,QIN X.et al.Benchmarking generic moving objects[J].Geoinformatica,2015,19(2):227-276.
[12]LIU L.From data privacy to location privacy:Models and algorithms[C]//Proceedings of the 33rd International Conference on Very Large Data Bases.Seoul:VLDB Endowment.2007:1429-1430.
[13]MOKBEL M F,CHOW C Y,AREF W G.The new casper:Query processing for location services without compromising privacy[C]//Proceeding of the 32nd International Conference on Very Large Data Bases.Seoul:VLDB Endowment,2006:763-774.
[14]SAMARATI P.Protecting respondent’s privacy in microdata release[J].IEEE Trans.on Knowl.and Data Eng,2011,13(6):1010-1027.
[15]GHINITA G,DAMIANI M L,BERTINO E,et al.Interactive location cloaking with the PROBE obfuscator[C]//Mobile Data Management:System,Services and Middleware.Tenth International Conference on IEEE.[s.l.]:IEEE,2009:355-356.
[16]GKOULALAS-DIVANIS A,VERYKIOS V S.A Free Terrain Model for Trajectory K-Anonymity[M]//Data-base and Expert Systems Applications.New York:Springer,2008:49-56.
[17]GRUTESER M,GRUNWALD D.Anonymous usage of location-based services through spatial and temporalcloaking[C]//Proceedings of the 1st International Conference on Mobile Systems,Applications and Services.New York:ACM,2003:31-42.
[18]KHOSHGOZARAN A,SHAHABI C,MEHR H S.Location privacy:Going beyond k-anonymity,cloaking and anonymizers[J].Knowl.and Inf.Syst,2011,26(3):435-46.
[19]GONG Z Q,SUN G Z,XIE X.Protecting privacy in location-based services using k-anonymity without cloaked region[C]//11th International Conference on Mobile Data Management.USA:DBLP,2010:366-371.
[20]YUNG D,LO E,YIU M L.Authentication of moving range queries[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management.New York:ACM,2012:1372-1381.
[21]XU J L,CHEN Q,HU H B.VERDICT:Privacy-preserving authentication of range queries in location-based services[C]//Proceedings of the 2013 IEEE International Conference on Data Engineering.Washington,DC:IEEE,2013:1312-1315.
[22]HU H B,XU J L,CHEN Q,et al.Authenticating location-based services without compromising location privacy[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.New York:ACM,2012:301-312.
[23]YAO B,LI F F,XIAO X K.Secure nearest neighbor revisited[M]//29th International Conference on Data Engineering(ICDE).[s.l.]:IEEE,2013:733-744.
[24]YI X,PAULET R,BERTINO E,et al.Practical k nearest neighbor queries with location privacy[M]//30th International Conference on Data Engineering(ICDE)[s.l.]:IEEE,2014:640-651.
[25]SHAO D X,JIANG K F,KISTER T,et al.Publishing trajectory with differential privacy:A priori vs.A posteriori sampling mechanisms[M]//Database and Expert Systems Applications.New York:Springer,2013:357-365.
[26]PELEKIS N,DIVANIS A G,VODAS M,et al.Privacy-aware querying over sensitive trajectory data[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management.New York:ACM,2011:895-904.