（计算机软件与理论专业论文）基于多边形隐匿区域的定位服务研究.pdf

基于多边形隐匿区域的定位服务研究 摘要 论文题目：基于多边形隐匿区域的定位服务研究 专业：计算机软件与理论 硕士生：陈修伟 指导教师：刘玉葆副教授 摘要 无线通信和移动数据库技术的快速发展，使得移动用户在任何时间、地点查 询任意信息的设想成为现实。位置探测设备( 例如便携式电话、g p s 、r f i d 等) 的 出现更引发了一个新的研究领域：定位服务或基于位置的服务( l o c a t i o nb a s e d s e r v i c e ，简称l b s ) ，例如基于位置的商店或餐厅的查找( 离我最近的餐厅在哪 里) 、交通报告( 哪条道路最通畅) 和基于位置的广告等。l b s 给移动用户带来 方便的同时，也带来了隐私泄漏的风险。因为l b s 服务器需要先获取移动用户的 位置信息才能为移动用户提供相应的服务。已有的隐私保护策略通过位置泛化， 把用户所在的位置坐标泛化为一个圆形或者矩形的隐匿区域，使得用户的位置很 好地隐藏在这个区域中。通常来说，用户实际需要的隐匿区域往往是和地形相关 的，如一条街道、一个城市，并不一定是矩形或者圆形，使用圆形或矩形作为隐 匿区域会增加无效区域的比例，降低位置信息的精度。 论文着眼于隐私安全与数据精度之间的权衡关系，希望在保护用户位置隐私 的同时，尽可能保留位置数据的精度。文中结合电子地图、k a n o n y m i t y ( k 匿 名) 、区域最邻近查询等技术设计了一个基于多边形隐匿区域的l b s 系统。系统 允许用户在电子地图中自定义多边形隐匿区域，然后通过使用l b s 中心服务器结 构，对用户的位置隐私进行双重保护。论文还基于多边形隐匿区域，设计了一种 区域最邻近查询算法p - r n n ，从点、线、面三个层次逐步求解查询的结果区域， 我们证明了结果区域必然包含了查询的实际结果，且面积尽可能的小。最后论文 通过实验与已有的c a s p e r 系统做比较，说明基于多边形隐匿区域的l b s 系统在 性能上确实更优。 关键词：定位服务、位置隐私保护、多边形隐匿区域、最邻近查询 基于多边形隐匿区域的定位服务研究a b s t r a e t t i t l e ： m a j o r ： n a m e ： l o c a t i o nb a s e ds e r v i c er e s e a r c ho r lp o l y g o nc l o a k i n gr e g i o n c o m p u t e rs o f t w a r ea n dt h e o r y x i u w e ic h e n s u p e r v i s o r ：a s s o c i a t ep r o f y u b a ol i u a b s t r a c t d u et ot h ed e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o na n dm o b i l ed a t a b a s e t e c h n o b g y , m o b i l eu s e r sc a l ls e a r c ha n yi n f o r m a t i o na ta n y t i m ea n da n y w h e r e l o c a t i o nd e t e c t e dd e v i c e ，s u c ha sm o b i l ep h o n e ，g p sa n dr f i d ，a l s ol e dar o wf i e l d o fs t u d y ：l o c a t i o nb a s e ds e r v i c e ( l b s ) i tp r o v i d er r a n ys e r v i c e sa b o u tl o c a t i o n , s u c ha sn e a r e s tn e i g h b o rq u e r y ( w h e r ei st h en e a r e s th o t e l , 臼i a f f i cr e p o r t ( w h i c hw a y i sb e s oa n dl o c a t i o na d v e r t i s e m e n t t h o u g hl b sb r m gc o n v e n i e n c et ou s ，i tr i s e s 印 t h er i s ko fp r i v a c y - b e c a u s ey o um u s tp r o v i d ey o u rl o c a t i o ni n f o r m a t i o nb e f o r ey o u e n j o yt h el b s t h ee x i s t i n gl o c a t i o np r i v a c yp o l i c ya a m f o r m st h ec o o r d i n a t eo f u s e r i n t oar e c t a n g l eo rc i r c l ec l o a k i n gr e g i o nb yb c a t i o ng e n e r a l i z a t i o n t h e n , t h er i s e r s l o c a t i o ni sh i d d e ni nab i gr e g i o n t h eb i g g e rt h ec b a k i n gr e g i o ni s ，t h es a f e rt h e l o c a t i o np r i v a c yc a nh e ，b u tn o ti st h eq u a l i t yo fs e r v i c e ( q o s ) t h eb e s tc l o a k i n g r e g i o ns h a p eu s u a ym e e t st h eh y o u to f c i t yo rh n d s c a p c ，s u c ha sh i d i n gi nar o a d , a c i t y , e t c t h e s er e g i o ma r en o to far e c t a n g l eo rc i r c l es h a p e i tw i l li n c r e a s et h e u s e l e s sr e g i o na n dr e d u c et h ed a t aa c c t r a c yi f w ec o v e rt h e mw i t hr e c t a n g l eo rc i r c l e t h i sp a p e rf o c u s e so nt h et r a d eo f fb e t w e e nt h el o c a t i o np r i v a c ya n dd a t a a c c u r a c y , a n ds t u d yh o wt op r o t e c tt h eb c a t i o np r i v a c yw h i l eh o u i n gt h ed a t a a c c u r a c y t h e n , ap o l y g o nc b a k i n gr e g i o nb a s e dl b ss y s t e mc o m b i n i n gt h e t c c b _ m b g yo f e l e c t r o m cm a p ，k - a n o n y m i t y , r a n g en e a r e s tm i g h b o ri sp r o p o s e d t h e n e ws y s t e ma l l o w su s e rt od e f i n et h ep o l y g o nc b a k i n gr e g i o na l o n gt h eh y o u t0 1 1t h e e - m a p a n dp m v j d ead o u b l ep r o t e c t i o nt o u s e r sb c a t m n p r i v a c ym o r e o v e r , t h i s p a p e rp r o p o s e sam n g en e a r e s tn e i g h b o ra l g o r i t h mb a s e d0 1 1t h ep o l y g o nc l o a k i n g 基于多边形隐匿区域的定位服务研究 a b s t r a c t r e g i o n , c a l l e dp - r n n i t c a l lg e tt h er e s u l tr e g i o nb yt h el e v e lo f p o i n t , l i n ea n dp h n e s t e pb ys t e p w ea l s op r o v et h a tt h er i g h tq u e r yo b j e c tm u s tl i ei nt h er e s u l tr e g i o n a t h a s t , w ec o m p a r ew i t ht h ec a s p e rs y s t e mw h i c hi sf a m o u sp r i v a c yl b ss y s t e m , a n d t h ee x p e r i m e n t a lr e s u l ts h o wt h a to u rs y s t e mi sb e t t e ri np e r f o r m a m e k e yw o r d s ：l o c a t i o nb a s e ds e r v i c e ，l o c a t i o np r i v a c yp r o t e c t i o n , p o l y g o nc b a k i n g r e g i o n , n e a r e s tn e i g h b o rq u e r y i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：! 堡! ：兰堡 日 期：堡生鱼：圣 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：p 寺 乌伟 i e i 势i ：p j 。年占月2 - e t 导师签名： 冰莆 日期：弘1 年6 月乙e l 基于多边形隐匿区域的定位服务研究第1 章引言 1 1 选题背景与意义 第1 章绪论 由于社会经济的高速发展，人们的活动范围越来越大，频率和速度也越来越 高，而且不确定性越来越大。这种趋势给人们出行带来了极大的不便，人们难以 掌握越来越庞大的位置信息。因此出现了能随时随地获取位置信息的需求。自 2 0 世纪9 0 年代以来，移动通信、无线网络、移动定位和空间信息技术等多种信 息技术的快速发展和相互集成应用，以及各种移动终端功能的日趋完善，为实时 位置服务提供了技术保障j 为“获得便利、快捷的个性化位置服务”提供可能。 在上述需求和技术的双重驱动下，移动定位服务，又称为基于位置的服务 ( l o c a t i o nb a s e ds e r v i c e ，简称l b s ) ，应运而生，成为了各学科领域的研究 热点，广泛用于交通导航1 m 射、出租车警员自动派遣5 、目标位置查询7 3 8 3 和高智能的物流配送系统网中。 l b s 是通过电信移动运营商的网络( 如g s m 网、c d m a 网) 、卫星信号等方式， 获取移动终端用户的位置信息( 经纬度坐标) ，在电子地图的支持下，通过空间 数据的查询和挖掘，提取用户需要的与其他地理位置相关的服务信息，并以适合 的方式返回给用户，以此为用户提供相应服务的一种增值业务n 们n 。如查询“离 我最近的酒店”，“到达公司的最近路径 等。这些功能能为用户提供极便利的出 行服务，深受用户喜爱。市场研究公司a b ir e s e a r c h 预测在2 0 1 1 年，全球享 受定位服务的人数将由2 0 0 6 年的1 2 千万增长到3 1 5 千万；越来越多的手机 嵌入g p s 功能将极大地促进l b s 的繁荣；在未来几年里，l b s 服务的收入将从5 1 5 亿美元增长到1 3 3 亿美元，有着极为广泛的用途和广阔的市场前景，并必将会成 为未来计算环境中非常重要的一部分，渗入到未来生活的各个方面。 尽管l b s 的诸多新型应用承诺了安全、方便，并提供新的商机，然而精确定 位的能力却引起了一种新的担忧：位置隐私的侵扰。位置隐私是指“防止他人获 得用户当前或者过去位置信息的能力 。如果在l b s 中查询“离我最近的加油站 在哪里，用户需要先向l b s 服务供应商提供自己的准确位置信息，那么l b s 服 务供应商就能追踪用户的位置，知道用户经常去什么地方，了解用户的行为习惯， 基于多边形隐匿区域的定位服务研究第1 章引言 然后转卖这些敏感信息给第三方以谋利益。因此，移动对象的位置信息的保护是 非常重要的，尤其对于重要的军事领域，这种位置隐私的泄露往往是致命的。国 家中长期科学和技术发展规划纲要( 2 0 0 6 2 0 2 0 年) 将信息安全研究列为重要的 主题和重点支持的研究领域。最近，国家将3 g 及相关的通讯应用作为重要支持 的产业领域，随着3 g 应用的不断深入，用户对位置隐私进行保护的要求也会越 来越强烈n 2 | 。 论文所研究的基于隐私保护的l b s 系统能有效解决用户的位置隐私问题，向 用户提供一个具有完善的隐私保护能力的移动位置服务应用系统，使得用户能放 心地使用l b s 服务。同时新的隐私保护机制能有效控制数据质量，使得l b s 服务 提供商也乐意使用，有利于位置隐私保护的推广。形成用户和定位服务提供商互 利互惠的状况，在给用户的生活带来变化的同时也给社会创造了巨大的价值。 1 2 研究目标与内容 1 2 1 研究目标 1 ) 在l b s 中保护移动对象位置隐私。如在查询“离我最近的加油站 时， 不向l b s 服务商提供精确的位置信息，而只是提供一个范围区域信息。服务商只 知道用户可能位于该区域内的任何一点上，而不知道具体是哪个点，从而起到保 护用户位置隐私的作用。 2 ) 在保护移动对象位置隐私的同时；尽可能保留用户位置信息的精度。l b s 的隐私保护机制将会把用户的位置信息进行泛化，如把点坐标转化为区域，这大 大地降低了数据的精度，给数据分析带来困难。l b s 服务供应商并不希望把这种 隐私机制用于自己的l b s 系统中，因而使得位置隐私保护的推广受到阻碍。本论 文将研究新的隐私保护机制，同时兼顾隐私保护和数据质量。使得在保护用户隐 私的同时，又能降低数据精度的损失。 3 ) 在保护移动对象位置隐私的同时，提供高效的l b s 服务。当移动用户向 服务器提出服务请求时，用户向l b s 服务器不断发送自己的位置信息，服务器根 据接收到的位置信息对该用户的服务请求进行处理。一般来说，用户的位置信息 越准确，服务器提供的服务质量越高。在定位服务中，用户的位置信息是否准确， 2 基于多边形隐匿区域的定位服务研究 第1 章引言 决定了l b s 的查询结果是否精确有效。由于位置隐私保护机制的作用，用户的位 置信息往往由点坐标被泛化成区域，导致查询得到不准确的服务结果。所以论文 将研究r 种与隐私保护兼容的查询算法，在保护位置隐私的同时，提供有效的 l b s 服务。 1 2 2 研究内容 1 ) 研究移动电子地图的存储、调用和显示，以及在n e t 平台上的实现。 2 ) 研究l b s 的系统架构，如何设计客户端、中间件、服务器的结构以及通 信方式，以保证用户的位置隐私不会泄漏给第三方。 3 ) 研究与隐私保护相兼容的最邻近查询算法，在仅知道用户所在区域的情 况下，也能提供正确、高效的最邻近查询服务。 1 3 论文结构 1 ) 第1 章介绍论文的研究背景与意义，并概括全篇的研究内容以及研究目标。 2 ) 第2 章介绍了定位服务的研究现状，包括定位技术、传输与显示技术、隐私 保护技术等，并对各技术进行了对比分析。 3 ) 第3 章提出了一种基于多边形隐匿区域的l b s 系统。首先从隐私安全、数据 精度、服务质量3 个方面进行分析，确定系统的总体架构；然后分别对每个 模块进行详细设计。 4 ) 第4 章基于我们的l b s 系统，提出一种基于多边形隐匿区域的最邻近查询算 法，在仅知道用户所在多边形区域的情况下，快速查找用户的最邻近目标集 合。 5 ) 第5 章对我们的l b s 系统进行演示，并通过实验对其性能进行评估。 6 ) 第6 章对我们的l b s 系统的优缺点进行总结，并确定将来进一步研究的目标 和方向。 3 基于多边形隐匿区域的定位服务研究第2 章研究进展 第2 章研究现状 2 1 定位服务研究现状 l b s 首先是从美国发展起来。1 9 9 6 年，美国联邦通信委员会( f c c ) 要求移动 运营商为手机用户提供e 9 11 紧急求助服务，即要求其提供紧急呼叫者的位置信息， 以便及时救援，这实际上就是移动位置服务l b s 的开始n 引。此后德国、法国、瑞 典、芬兰等国家纷纷推出各具特色的商用l b s 系统，再后来由于g p s ( 全球卫星定 位系统) 、通讯技术和g i s ( 地理信息系统) 领域的发展刺激了各行业对l b s 的想 象力，许多国家的电信公司开始广泛利用该项服务，依照移动用户的地理位置为 其提供量身定制的服务n 们。从全球来看，韩国和日本是全球移动定位业务应用最 为广泛的国家，发展情况最好。虽然移动位置服务经历了2 0 0 0 年至2 0 0 7 年的低潮 期，但手机用户界面的改进以及应用程序分销渠道更易获取，引起了移动位置应 用服务提供商的极大兴趣。例女 1 i p h o n e 的出现，更方便消费者获得想要的应用程 序，而更多的分销渠道使手机用户更愿意使用移动位置服务。同时，经济增长正 在进一步推动高容量的网络基础设施和随之而来的移动互联网应用增加，这为以 浏览器为基础的服务提供了更多的机会。 与发达国家相比，中国的l b s 业务市场起步比较晚，但中国有一个巨大的l b s 用户群，拥有广阔的市场前景。国内以面向个人业务为主的l b s 业务可归纳为以 下几种：1 ) 个人定位；2 ) 黄页信息查询；3 ) 路径查找服务；4 ) 地址查找服务； 5 ) 广告；6 ) 基于位置的手机游戏。在行业应用方面，主要分布在公安、消防、 交通、地理、企业、新闻媒体等领域，这类的l b s 应用就是随时获取员工和资产 的位置信息及用户组详细的业务状态，业务主要在人员跟踪、物品跟踪、交通监 控等方面。在社会公益类应用方面，为公众提供基于位置的公共安全业务，例如 1 1 0 、1 1 9 、1 2 0 、1 2 2 等紧急业务；还可以向危险地区的移动用户发布洪水、山体 滑坡、道路危险等信息。l b s 服务涵盖了几乎社会生活的各方面，市场潜力巨大 【1 4 】 o 近年来，l b s 在技术上日臻成熟，主要包括3 个方面：1 ) 基于网络的定位技 术：2 ) 空间数据的传输和显示技术；3 ) g i s 相关技术n 叼。 4 基于多边形隐匿区域的定位服务研究第2 章研究进展 2 1 1 定位技术 l b s 定位的过程大致分为两步：第步是测量；第二步是计算。根据测量和 计算的实体不同，定位技术分为基于网络的定位技术( 反向链路定位) 和基于移 动终端的定位技术( 前向链路定位) 口3 。 2 1 1 1 基于无线网络的定位技术 1 ) 起源蜂窝小区c 0 0 ( c e l lo fo ri g i n ) 定位技术 该技术是根据移动终端所在的区域编号( c e l l - i d ) 来确定用户的大致位置。 移动终端在当前区域连接后，系统的数据库中就会有相对应的c e l l i d 区域编号 n 即。c 0 0 的定位精度是所有定位技术中精度最低的，主要取决于终端所在基站小 区的半径。但是优点是c 0 0 技术无需对移动终端和网络进行修改就能直接使用。 2 ) 到达角度a o a ( a n g l eo fa r r i v a l ) 定位技术 该技术在多个坐标点处放置信号接收站，监视移动终端的无线电波信号，并 根据信号计算它们的角度信息，然后通过多角度直线求交计算终端的准确位置。 这种方法在平坦宽阔、没有障碍物的情况下，可以获得较高的定位精度，但在地 表环境复杂的环境中，由于无线电波的传输有多径效应而使得误差增大n 钉。 3 ) 抵达时间t o a ( t i m eo fa r r iv a l ) 定位技术 该技术通过电波信号的传输时间，来确定移动终端到多个基站的距离，从而 获得用户的准确位置。移动目标处于以基站为圆心，传播距离为半径的圆形上。 只需要获得三个这样的圆，就可以由三圆的交点来确定用户的位置。t o a 的定位 精度较高，不过它为了准确测量电波信号的到达时间，需要移动终端和各个基站 之间进行同步。 4 ) 抵达时间差异t d o a ( t i m ed i f f e r e n c eo fa r r i v a l ) 定位技术 该技术与t o a 类似，不过它不是检测各个信号到达的具体时间，而是检测信 号到达最近两个基站的时间差，以计算移动目标的位置信息。相对于t o a ，t d o a 不要求在时间上进行同步。为了检测两个t d o a ，该技术需要使用三个不同的信号 基站，通过计算两个t d o a 形成的双曲线的焦点，可以确定用户的准确位置。该定 位技术的优点是定位精度高，缺点是所需要的响应时间较长，不适用于实时环境。 s 基于多边形隐匿区域的定位服务研究第2 章研究进展 5 ) 增强观测时间差分e - o t d ( e n h a n c e do b s e r v e dt i m ed i f f e r e n c e ) 定位 技术 该技术在服务区域内放置一些参考点，每个参考点各自拥有一个精确的时间 源，当具有e o t d 功能的移动终端设备接收到来自至少3 个基站的信号时，开始计 算每个基站到移动目标的时间差，这些差值将产生几组交叉双曲线，并由此可以 估计出移动目标的位置口3 。与其他定位技术相比，e - o t d 技术的定位更高，但缺 点是它的实现成本比较高，兼容性差，需要对网络和移动终端设备的结构进行修 改后才能使用。而且它的响应速度比较慢。 6 ) 高级前向链路三角a f l t ( a d v a n c e df o r w a r dl i n kt r i l a t e r a t i o n ) 定位 技术 该技术在进行定位操作时，使用码片的时间延迟来测量移动终端到基站的距 离，然后通过三角定位法计算用户的准确位置n 羽。高通公司的g p s o n e 定位解决方 案就是使用这种技术配合g p s 来实现的。 7 ) 信号强度分析定位技术 该技术的关键是将基站与移动终端之间的信号强度转化为距离，以确定移动 目标的位置。但是这种方法并不常用，因为干扰问题的影响，导致这种技术的信 号强度总是不断变化，呈现不稳定状态。 2 1 1 2 基于卫星的定位技术 1 ) g p s 定位技术 g p s 全球定位系统利用多个定位卫星向移动终端设备发送无线电波，终端设 备根据无线信号来计算自己与各个卫星之间的距离，从而确定移动目标的位置。 由于卫星距离位于地球轨道上，它的信号覆盖面积很广，可以为地球表面绝大部 分地区提供准确的定位、测速和高精度的时间标准。移动用户要确定其在地球上 的位置以及海拔高度，至少需要获取3 颗卫星以上的信号。所连接的卫星数越多， 解码出来的位置越精确。一般来说，民用g p s 的定位精度大概在是i 0 0 米左右。但 由于g p s 接收终端由于启动时间长、耗电量大、且部分区域( 如室内) 无法接收 到卫星信号，这种方法在l b s 中的应用有限。 2 ) a - g p s 定位技术 6 基于多边形陋匿区域的定位服务研究第2 章研究进展 辅助g p s 定位技术通过建立一个与移动通信网相连接的g p s 参考网络，结合网 络基站信息和g p s 信息对移动终端进行定位，如图2 1 所示1 。在定位时，网络与 g p s 卫星进行连接，获取g p s 的导航辅助信息，然后将这些信息传送给移动终端， 移动终端再根据这些辅助信息快速找出有用的卫星，并接收这些卫星的信号来计 算目标位置“”。此技术的优势主要在其定位精度上，在室外等空旷地区，正常情 况下其精度可达5 一l o m ，堪称目前定位精度最高的一种定位技术。另一方面，利 用网络传来的辅助信息可以增强t t f f ( t i m et of i r s tf i x ) ，其首次捕获g p s 信 号的时间大大减小，一般仅需几秒，而不像6 p s 的首次捕获时间可能需要23 m i n 。 a - g p s 定位响应时间仅在3 一i o s 之间。但a - g p s 的主要缺点是在室内，可能由于建 筑物的遮挡，而接收不到卫星的导航信号，从而导致定位失败。因此一般的a g p s 技术解决方案还考虑y c 0 0 定位技术作为备用方案这样就大大提升了a - g p s 的定 位能力。 穆动辟薯 图21a _ 6 p s 工作原理 在基于无线网络和卫星的定位技术中，没有一种定位方式能在所有情况下满 足有效性和精度需求。在市区峡谷和室内，g p s 的有效性和精度受到影响：而多 路径、衍射、微弱信号情况以及性能较差的发射站也会降低无线髓结定位的精度 和有效性。针对这个问题，出现了一种更可靠和稳健的解决方案：混合定位。这 基于多边形隐匿区域的定位服务研究 第2 章研究进展 一技术独立于特定的定位技术，并具有可扩展性。允许在凡种定位方式之间进行 智能切换，在特定状况下使用最合适的方法，并能以一种定位技术为辅助，以加 强另一种定位技术。以最低成本改善了定位的有效性、灵敏度秘精度。通过多种 定位信息资源的联合，混合定位解决方案在只有一个卫星或一个发射站的情况下 都可以提供位置定位。鏊外有缀多混合定佼解决方案，妇m o t o r o l a 公司的l o v e u s 解决方案、i n t e l 公司的u l f 解决方案、意大利电信实验室的n a v j c o m 解决方案等 担l 】 o 以上介绍的几种定位技术，它们的定位精度各不相同，所适用的环境也大相 径庭。在选择定位技术时，我们疲尽可能地根据不同的定位业务需求，并结合终 端、网络等设备的实际情况来考虑，以选取最适合自己的定位技术解决方案： 2 1 2 空间数据的传输和显示技术 在l b s 中，空间数据在服务器与客户端之间流转，快速地处理地理空间信息， 包括存储、传输、显示等，是l b s 应用的关键技术，也是制约l b s 应用的瓶颈。x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 即可扩展标记语言，是当前在网络传输方面非 常优秀的一种语言。它具有自我描述功熊，可以创建自定义标记，英有跨平螽、 内容与表现形式相分离等特点。x m l 在网络数据交换方面，允许结构不同的应用 之间进行数据交换，而显这种交换并不需要提前约定数据结构的定义，通过自我 描述功能，它把数据的定义也作为数据交换的一部分进行传输，具有很强的开放 性帮 枣缩性。 g m l 、s v g 和v m l 正是基于x m l 的可用来描述矢量图形的标记语言回。它们作为 空闯数据豹传输格式，其有各自的特点。 2 。1 。2 1g m l 地理标记语言 g m l ( g e o g r a p h ym a r k u pl a n g u a g e ) 是由o p e n g i sc o n s o r t i u m ( o g o 提_ 出 的基于x m l 的空间信息编码标准，得到o r a c l e 、g a l d o s 、m a p i n f o 、c u b e w e r x 等国际大企业的支持。在g m l 中，地理对象的属性数据和图形数据是分离开来的。 h t t p ：粥g i s s k y 。n e t k r t i c l e 1 8 1 。h t m 8 基于多边形隐匿区域的定位服务研究第2 章研究进展 它包括以下几个特点： 1 ) g m l 基于x m l 用文本表示地理信息 g m l 是基于x m l 的描述语言，它以文本的方式来描述地理对象，比较简单、 直观，容易理解和编辑。和二进制描述的不可读性形成对比。 2 ) g m l 封装了地理信息及其属性 g m l 基于地理信息抽象模型，对地理对象的f e a t u r e ( 特征) 及其属性进行 了封装。地理对象的f e a t u r e 包括属性和相应的g e o m e t r y ( 几何信息) 。属性通 常是由文本类型的数据，由名字、类型和值组成；g e o m e t r y 则是一系列几何图 形的组合，包括点、线、面以及一些高级图形。6 m l 允许复杂的f e a t u r e 描述， 包括f e a t u r e 间的嵌套、f e a t m ：e 集合等。例如学校由教学楼、宿舍组成。目前 g m l 目前在二维平面上有广阔的应用前景，同时自身也在不断改进，逐步加入对 三维地理对象的支持。 3 ) g m l 封装了空间地理坐标系统 空间地理坐标系统是描述地理对象位置的基础，如每个地理对象都有一个坐 标来描述它的位置；同时也是地理信息系统( g i s ) 处理数据的基础，在计算对 象间距离时，需要知道计算的是地球表面坐标距离，还是平面坐标距离。g m l 封 装了空间地理坐标系统，让每个地理对象都携带自己的坐标系统，使得其在分布 式处理方面具有很好的扩展性和灵活性。 4 ) g m l 可以实现地理数据的分布式存储 g m l 由于使用了文本来表示地理信息，且封装了空间f e a t u r e 、坐标系统等 对象，具有优秀的自我描述功能，在地理数据的分发上非常便利，因此可以成为 地理数据分布式存储的重要手段。 从上述特点可以看出，g m l 作为描述空间信息的元语言，它虽然具有良好的 可读性和可交换性，但其只能描述空间实体的矢量信息和属性，具体显示时需要 对g 儿数据进行解析：或者把g 札转换为相应的图形格式数据，例如s v g 、v m l 和x 3 d 等，然后通过已有的支持这些图形格式的软件进行显示。 2 1 2 2v m l 矢量标记语言 v m l ( v e c t o r l a r k u pl a n g u a g e ) 是一个最初由l ic r o s o f t 开发的x m l 词表， 9 基于多边形隐匿区域的定位服务研究第2 章研究进展 m i c r o s o f t 在工e 中加入了对v m l 的支持，允许用户在i e 中使用v m l 来绘制矢量 图形。下面介绍一下v m l 的优点： 1 ) 易于扩展 v m l 同样是使用捌l 标准，具有天生的自我描述能力，表示方法简单，易于扩 展。 2 ) 支持高质量的矢量图形显示 v m l 支持大部分的矢量图形f e a t u r e ，它们使用相互连接的直线、曲线来描述 地图中的路径、形状等。在v m l 中，s h a p e 和g r o u p 是两个基本的元素，这两个元 素囊括了整个w l 结构。其中s h a p e 描述的是一个矢量图形元素，g r o u p 贝j j 作为一 个集合，将这些图形元素结合起来，而且它们又可以当成是一个整体来处理。组 织形式类似于树状体系。v m l 支持多种不同矢量图形f e a t u r e 的元素，包括s h a p e 、 p a t h 、l i n e 、p o l y g o n 、c u r v e 、r e c t 、r o u n d r e c t 、o v a l 、a r c 、g r o u p 等。 3 ) 支持交互与动画 v m l 不仅支持绘图功能，它还支持通过脚本语言来实现动画显示，例如地理 对象的移动、旋转等。并支持在图形中嵌入文本，实现超链接，在很大程度上丰 富了v m l 的内容。 2 1 2 3s v g 可缩放矢量图形 s v g ( s c a l a b l ev e c t o rg r a p h i c s ) 是一种基于x m l 的开放的矢量图形描述语 言，是一种专门为空间数据在网络上传输而设计的基于文本的图像格式。它直接 继承了x m l 的特性，通过自我描述功能，能以简单的方式处理异构系统间的数据 交换问题。s v g 可以看作一个由多个组件合成的整体，每个组件有自己独特的功 能。如s v g 图像相当于文档，s v g 元素则是绘制图像的指令，s v g 阅读器( v i e w e r ) 负责解释这些指令，把s v g 图像绘制成地理对象。在图形特效方面，s v g 有着强大 的优越性，它支持嵌套变换、路径的矩形框裁剪、地图透明以及多种滤镜效果等， 具有较好的绘制功能。 由于s v g 是在v m l 的基础上改进而来，所以s v g 也具有v m l 的优点，除此之外s v g 还独自拥有一些其他特点： 1 ) 支持文字图层 基于多边形隐匿区域的定位服务研究 第2 章研究进展 般来说，图像中的文本由于已经转换为像素，因此不能对文本进行删除、 修改等处理。而s v g 则通过对已有的图像格式进行扩展，把文本作为一个独立图 层存储起来。因此它的文件结构除了包括矢量图形、位图外，还包括文字。这样， 使用s v g 就可以随意地对文字图层进行删改，制作出一般图像格式无法达到的效 果。 2 ) 支持字符串查找 由于s v g 把文本图层分开存储，对图片中的文字进行查找也就成为很简单的 问题了。但这在其他格式的图形文件中却无法实现。 3 ) 支持x l i n k 和x p o i n t e r 通过支持x l i n k 和x p o i n t e r ，s v g 在x m l 的文件结构中可以通过指针来快速定 位内容，并允许在s v g 文档之间进行超链接。以制作出更加个性化的空间数据显 示方式。 s v g 是w 3 c 组织正式推荐使用的图像格式，相比g m l 、v m l 等技术，它拥有众多 的支持机构。例如微软和n e t s c a p e 两家公司在浏览器产品方面，加入了对s v g 的 支持。a d o b e 公司也称在未来的a d o b e 图像处理套件中将集成s v g 的全部功能，这 些都表明了s v g 将来会有更好的发展。 g m l 、s v g 、v m l 都可以作为l b s 应用中的空间数据格式：g m l 在描述地理对象 的同时，加入了对象的其他属性信息，在数据编码方面具有优势，但它不支持直 接显示图形，显示时需要进行解析或者格式转换。而v m l 和s v g 是在描述地理对象 矢量信息的同时，还描述了图形的样式信息，告诉系统应该如何显示图形元素， 旋转多少度、平移多少距离等，是显示矢量图形的两种比较好的格式。相比之下， s v g 是在v m l 的基础上产生的，吸收了v m l 的优点，且是由w 3 c 组织正式推荐的国际 标准，它有众多的公司支持，前景更加广阔。因此在l b s 中可以把服务请求转换 成s v g 格式进行传输、处理和显示：或者先使用g m l 的格式进行传输，再解释为s v g 进行处理和显示。具体要根据网络性能以及移动终端设别的情况而定。 1 l 基于多边形隐匿区域的定位服务研究第2 章研究进展 2 1 3 g i s 相关技术 g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) 称为“地理信息系统 ，它是在计 算机硬件、软件系统支持下，对整个或者部分地球表层( 包括大气层) 空间中的 有关地理分布数据进行采集、存储、管理、运算、分析、显示和描述的技术系统 嘲。l b s 的核心主要是位置以及地理信息，定位技术解决了移动终端的位置问题， 空间数据的传输和显示技术使l b s b 艮务网络化成为可能，而要提供实际的服务， 如导航、最邻近查询服务等，必须依赖于g i s 的相关技术，包括动态数据库管理、 空间分析、电子地图等。 1 ) 在导航服务中，g p s 等定位设备仅仅是以数字的形式提供坐标，为了让用 户能对数字形式的坐标有进一步的认识，需要通过与地图上附近道路进行匹配鼢1 ， 在地图中显示坐标位置。因此需要对地图匹配算法进行深入研究，在交通道路的 连通性、多路径、最短路径等要求下，实现l b s 中车载导航的高效服务。 2 ) 在定位服务中，如车辆导航、计算两点间距离等，都有着最短路径的服 务要求。路径规划就是研究在道路网结构中，如何寻找实时、动态地寻找两点间 的最短路径。当前的路径规划研究已经得到了一套完整的体系心钔，但这些方法都 是在假设在理想的状况下，并没有考虑蛰j l b s 中移动终端设备的性能、传输、信 号好坏度等问题，因此不能直接用于l b s 中，还需要继续研究改进。 3 ) 在l b s 中，用户处于不断移动的状态，位置信息需要频繁更新，因此需要 一种动态数据库技术来管理地理对象以及用户的位置。移动数据库的作用就是要 对移动目标进行建摸，通过道路动态分段、路网拟合等技术。通过使用空间索引 结构瞄矧3 ，如r 树等，加速空间对象的查询、处理。 4 ) 电子地图是和用户直接交互的界面，用于显示用户需要的地理信息，展 现l b s 的查询结果。它主要解决l b s 环境中的地图显示速度、存储容量以及信息查 询速度等问题。目前市面上已经有多种电子地图开发产品，女i m a p l n f o 公司的 m a p x t r e m e 。m a p x t r e m e 是一套开发工具包，通过它用户能够开发丰富w e b 电子地 图应用，并且能够充分利用电子地图的最新成果，包括半透明、功能增强标记、 曲线标记和抗锯齿等。 m a p x t r e m e2 0 0 8v 6 8d e v e l o p e rg u i d e 基于多边形隐匿区域的定位服务研究第2 章研究进展 2 2 隐私保护研究现状 2 2 1 关系数据的隐私保护 关系数据库技术是目前发展最成熟的数据库技术，它的出现使得大量数据以 记录的形式存储在数据库中。数据是信息的来源，利用数据挖掘，可以从海量的 数据中挖掘出有用的信息，这就需要对关系数据库中的数据进行整合，并向数据 挖掘人员进行发布。但是，这些发布的数据中往往含有大量的、敏感的个人隐私 信息，因此在发布前需要对数据进行一些处理，以保护数据中的个人隐私啪1 。当 前对大规模待发布数据的隐私保护研究主要集中在，以记录形式存储的关系数据 的隐私保护汹列m 儿捌，例如医院数据中的病例隐私、银行的金融数据等。使用隐 私保护方法对数据进行保护后，必然会对数据质量造成影响。研究关系数据的隐 私保护方法的目的，就是在不泄露个人隐私信息的同时，还要尽可能保留数据的 可用性，否则保护后的数据无法用于数据挖掘处理。目前，针对这个问题已经提 出了大量数据隐私保护方法圳删3 叼啪1 。 k - a n o n y m it y ( k 匿名) 方法是s w e e n e y 侧在2 0 0 2 年最先提出的，在隐私保 护中比较常见的一种方法。该方法的思想是对每一条记录的非敏感属性进行泛化， 要求泛化后，原数据集中的每一条记录都至少有另外k - 1 条记录和它一模一样， 让恶意攻击者无法从中辨别出某个个体的信息侧啪1 ，那么也就难以推测出某个个 体的敏感属性值。其中具有相同非敏感属性值的k 条记录称为一个等价类。 k - a n o n y m it y 方法通过对数据进行泛化，使得个体与数据库记录之间的联系模糊 了，那么隐私的安全程度就高了。然而该方法并不能完全解决隐私泄露的问题， 例如当某个等价类的所有敏感属性都是同一个值时，恶意的攻击者也可以从一张 经过k - a n o n y m i t y 处理的表中得到出某个个体的真实敏感信息。同时， k - a n o n y m i t y 方法以数据精度为代价，把用户的位置信息进行泛化1 ，从而也将 严重威胁到数据分析的准确性。 为解决k - a n o n y m i t y 中，等价类敏感值相同的问题，m a c h a n a v a j j h a l a 等 提出了一种新的隐私保护标准：l - d i v e r s i t y 。这种方法和k - a n o n y m i t y 一样， 将原始数据分割成多个等价类，但不同的是，它要求得每个等价类中至少有l 个不同的敏感值。因此，恶意的攻击者即使通过一些已有知识得知用户属于某个 基于多边形隐匿区域的定位服务研究 第2 章研究进展 等价类，也无法推断用户的敏感信息。这种方法的隐私暴露的概率仅为：l ，其 中l 是可调参数，l 越大，隐私安全程度越高。文献 3 7 通过实验证明了 l - d i v e r s i t y 比k - a n o n y m