位置服務(wù)與隱私保護(hù)課件

位置服務(wù)（LBS）中的隱私保護(hù)位置服務(wù)（LBS）中的隱私保護(hù)位置服務(wù)（LBS）位置服務(wù)簡言之，就是基于地理位置數(shù)據(jù)而展開的服務(wù)。是指通過移動終端和無線通訊網(wǎng)絡(luò)（或衛(wèi)星定位系統(tǒng)）的相互配合，以空間數(shù)據(jù)庫為基礎(chǔ)，確定移動用戶的實際地理位置或坐標(biāo)，并將其與其他信息整合起來，為用戶提供所需要的與位置相關(guān)的增值服務(wù)。LBSLBS：LocationBasedServiceServicesthatintergrateamobiledevice’slocationorpositionwithotherinformationsoastoprovideaddedvaluetoauser位置服務(wù)（LBS）位置簡言之，就是基于地理位置數(shù)據(jù)而展GPSSENSORRFID緊急救援服務(wù)信息娛樂服務(wù)分發(fā)服務(wù)交通導(dǎo)航跟蹤服務(wù)定位最近的救援者位置查找距離我百米內(nèi)最近的銀行向我餐館500米范圍內(nèi)的用戶發(fā)送電子優(yōu)惠券查找到達(dá)目的地的最優(yōu)路徑對航空物流進(jìn)行追蹤GPSSENSORRFID緊急救援服務(wù)信息娛樂服務(wù)分發(fā)服務(wù)交位置服務(wù)前景廣闊…...2007年以來中國位置服務(wù)市場規(guī)模及增長市場規(guī)模位置服務(wù)前景廣闊…...2007年以來中國位置服務(wù)市場規(guī)模及位置服務(wù)前景廣闊…...用戶數(shù)量2007年以來中國位置服務(wù)用戶規(guī)模及增長全球及國內(nèi)移動位置服務(wù)市場發(fā)展階段對比位置服務(wù)前景廣闊…...用戶數(shù)量2007年以來中國位置服務(wù)用

位置服務(wù)（LBS）軍事產(chǎn)業(yè)政府事務(wù)求助服務(wù)追蹤監(jiān)控定位導(dǎo)航休閑娛樂分發(fā)服務(wù)Formoracle位置服務(wù)前景廣闊…...使用領(lǐng)域位置服務(wù)軍事產(chǎn)業(yè)政府事務(wù)求助服務(wù)追蹤監(jiān)控定位導(dǎo)航休閑娛

1432也許某天，當(dāng)你經(jīng)過熟悉的星巴克，打開手機(jī)記錄你的位置，卻驚喜地發(fā)現(xiàn)一位好友也正在這里享用咖啡。而在不遠(yuǎn)處的商場內(nèi)，某件你關(guān)注了很久的名牌襯衫正在打折……又或者你去一個遙遠(yuǎn)的城市旅行，打開手機(jī)，卻發(fā)現(xiàn)自己瞬間對這個陌生的地方變得如此熟悉，想去哪兒就能隨心所欲，想玩什么立馬就能朝著目標(biāo)出發(fā)……此時，你肯定會為位置服務(wù)所帶來的便捷生活方式而興奮！可是你又是否設(shè)想過，未來，無論你走到哪里，上班，下班，旅行亦或是散步，都會有漫天飛舞的各種廣告鋪天蓋地向你席卷而來，你無處躲藏，只能被淹沒在信息的垃圾中煩惱嘆息……甚至有一天，對你而言，無論是熟悉的親朋還是陌生人，都沒有了秘密，每天無論你走到哪兒，干了什么，將要去哪，甚至你最近喜歡什么，想要計劃什么，大家都能知道的時候，你會不會又對這一新興的服務(wù)產(chǎn)生恐懼呢。。。隱私問題??！1432也許某天，當(dāng)你經(jīng)過熟悉的星巴克，打開手機(jī)記錄你如何解決位置服務(wù)中堪憂的隱私保護(hù)問題呢？如何解決位置服務(wù)中堪憂的隱私保護(hù)問題呢？內(nèi)容導(dǎo)覽導(dǎo)引：隱私保護(hù)問題隱私保護(hù)的系統(tǒng)結(jié)構(gòu)隱私保護(hù)模型與匿名技術(shù)隱私保護(hù)的算法實現(xiàn)內(nèi)容導(dǎo)覽導(dǎo)引：隱私保護(hù)問題隱私保護(hù)的系統(tǒng)結(jié)構(gòu)隱私保護(hù)模4隱私問題舉例生活中這樣的例子很常見：張某利用自己帶有GPS的手機(jī)提出了“尋找距離我（現(xiàn)在所在位置）最近的腫瘤醫(yī)院”的查詢。這是導(dǎo)航系統(tǒng)中一個普通的最近鄰查詢（即NN查詢）。此查詢被提交給服務(wù)提供商，比如GoogleMaps，再由服務(wù)提供商通過查詢空間數(shù)據(jù)庫返回給用戶查詢結(jié)果。此時涉及到的隱私問題包含兩個方面：一是用戶不想讓人知道他此刻所在的位置,比如銀行。二是用戶不想讓任何人知道自己提出了某方面的查詢，如張某不想讓人知道自己將去腫瘤醫(yī)院。4隱私問題舉例生活中這樣的例子很常見：張某利用自己帶有GPS4位置服務(wù)中的隱私泄露查詢隱私泄露其他人以任何方式獲知對象過去或現(xiàn)在的位置。位置隱私泄露

查詢請求的內(nèi)容，可能透露用戶的行為模式（如經(jīng)常走的道路及經(jīng)過的頻率）、興趣愛好（如喜歡去哪個商店、哪種俱樂部）、健康狀況（如經(jīng)常去的心理咨詢診所）以及政治傾向等個人隱私信息。4位置服務(wù)中的隱私泄露查詢隱私泄露其他人以任何方式獲知對象過4隱私泄露的三種途徑觀察（Observation）攻擊者從位置設(shè)備或者位置服務(wù)器中直接獲取用戶的位置信息。（如利用手機(jī)內(nèi)置GPS定位導(dǎo)致的位置信息泄露）直接交流（DirectCommunication）攻擊者通過“位置”連接外部的數(shù)據(jù)源（或者背景知識）從而確定在該位置或者發(fā)送該消息的用戶。（如查詢信息A是從別墅B發(fā)出的，當(dāng)攻擊者知道別墅B的主人是C這一背景時，那么就能確定A是由C發(fā)出的）攻擊者通過觀察被攻擊者的行為直接獲取位置信息。（如攻擊者跟蹤被攻擊者）連接泄露（LinkAttack）4隱私泄露的三種途徑觀察（Observation）攻擊者從位4位置服務(wù)中的隱私保護(hù)查詢隱私保護(hù)避免用戶與某一精確位置匹配。。位置隱私保護(hù)

避免用戶與某一敏感查詢匹配。4位置服務(wù)中的隱私保護(hù)查詢隱私保護(hù)避免用戶與某一精確位置匹配4尋找一種狀態(tài)，在這種狀態(tài)下很多對象組成一個集合（匿名集），從集合的外面向里看，組成集合的各個對象無法被區(qū)分，使得某一個位置的信息無法與確切的個人/組織/機(jī)構(gòu)相匹配。位置信息經(jīng)過匿名處理后不再是用戶的真實位置，可能是多個位置的集合或者一個模糊化的位置，查詢系統(tǒng)應(yīng)該對應(yīng)地返回包含真實查詢信息的模糊信息集隱私保護(hù)的工作位置匿名查詢處理4尋找一種狀態(tài)，在這種狀態(tài)下很多對象組成一個集合（匿名集），4位置服務(wù)VS隱私保護(hù)魚與熊掌可否兼得？位置服務(wù)隱私保護(hù)提供精確位置隱藏用戶位置不能兼得??！只能尋找平衡點！在最少的位置暴露下獲得最好的服務(wù)，使隱私暴露處于“可控狀態(tài)”！4位置服務(wù)VS隱私保護(hù)魚與熊掌可否兼得？位置服務(wù)隱私保護(hù)提供隱私保護(hù)的特點保護(hù)位置隱私與享受服務(wù)是一對矛盾位置信息的多維性特點位置匿名的即時性特點基于位置匿名的查詢處理位置隱私需求個性化隱私保護(hù)的特點保護(hù)位置隱私與享受服務(wù)是一對矛盾位置信息的多維

隱私保護(hù)的系統(tǒng)結(jié)構(gòu)Non-cooperativeArchitecture獨立結(jié)構(gòu)中心服務(wù)器結(jié)構(gòu)CentralizedArchitecture分布式點對點結(jié)構(gòu)Peer-to-peerArchitecture僅有客戶端與位置數(shù)據(jù)庫服務(wù)器的C/S結(jié)構(gòu)。該結(jié)構(gòu)需要移動用戶擁有具有強(qiáng)大定位、計算、存儲能力的設(shè)備，自己完成位置匿名和查詢結(jié)果求精。在用戶和位置數(shù)據(jù)庫服務(wù)器之間加入第三方可信中間件——位置匿名服務(wù)器，并由位置匿名服務(wù)器完成匿名處理和查詢結(jié)果求精。由客戶端和位置數(shù)據(jù)庫服務(wù)器組成，移動客戶端根據(jù)匿名算法找到其他一些移動用戶組成一個匿名組，以此進(jìn)行位置匿名。同時組內(nèi)的客戶端之間的節(jié)點具有平等性，共同協(xié)調(diào)完成查詢結(jié)果求精。隱私保護(hù)的系統(tǒng)結(jié)構(gòu)Non-cooperative獨立結(jié)獨立結(jié)構(gòu)缺點：對客戶端要求高；缺乏全局信息，隱蔽性弱優(yōu)點：結(jié)構(gòu)簡單，易于配置處理流程：將匿名后的位置連帶查詢一起發(fā)送給位置數(shù)據(jù)庫服務(wù)器；位置服務(wù)器根據(jù)匿名的位置進(jìn)行查詢處理并將候選結(jié)果集返回給用戶；用戶根據(jù)真實位置挑選出真正的結(jié)果。獨立結(jié)構(gòu)示意圖獨立結(jié)構(gòu)缺點：對客戶端要求高；優(yōu)點：結(jié)構(gòu)簡單，易于配置優(yōu)點缺點中心服務(wù)器結(jié)構(gòu)處理過程：（1）用戶發(fā)送包含精確位置的查詢請求給位置匿名服務(wù)器。（2）匿名服務(wù)器使用某種匿名算法完成位置匿名后，將匿名后的請求發(fā)送給位置數(shù)據(jù)庫服務(wù)器。（3）位置數(shù)據(jù)庫服務(wù)器根據(jù)匿名區(qū)域進(jìn)行查詢處理，并將查詢結(jié)果的候選集返回給位置匿名服務(wù)器。（4）位置匿名服務(wù)器從候選結(jié)果集中挑出真正的結(jié)果返回給移動用戶。具有全局信息，隱私保護(hù)效果好。位置匿名服務(wù)器成為系統(tǒng)的瓶頸；位置匿名服務(wù)器還可以成為隱私泄露的唯一攻擊點。優(yōu)點缺點中心服務(wù)器結(jié)構(gòu)處理過程：（1）用戶發(fā)送包含精分布式點對點結(jié)構(gòu)ThemeGalleryisaDesignDigitalContent&ContentsmalldevelopedbyGuildDesignInc.優(yōu)點：擁有全局信息，隱私效果好；消除了系統(tǒng)瓶頸；消除了唯一攻擊點。缺點：網(wǎng)絡(luò)通訊代價高。處理過程：（1）移動客戶端根據(jù)匿名算法建立一個匿名組，進(jìn)行位置匿名。（2）根據(jù)實際的網(wǎng)絡(luò)通訊情況選擇一個合適的頭結(jié)點，頭結(jié)點將匿名后的查詢請求發(fā)送給位置數(shù)據(jù)庫服務(wù)器。（3）位置數(shù)據(jù)庫服務(wù)器根據(jù)匿名區(qū)域進(jìn)行查詢處理，并將查詢結(jié)果的候選集返回給頭結(jié)點。（4）頭結(jié)點可以選擇出真實結(jié)果發(fā)送給提出查詢的用戶，也可以將查詢結(jié)果的候選集發(fā)送給用戶，由用戶自己挑選出真實的結(jié)果。頭結(jié)點平衡網(wǎng)絡(luò)負(fù)載?。?！分布式點對點結(jié)構(gòu)ThemeGalleryisaDesi位置K-匿名模型（LocationK-AnonymityModel）隱私保護(hù)模型模型描述模型定義

把某一用戶的真實位置點擴(kuò)大為一個模糊的位置范圍，使得該范圍覆蓋k個用戶的位置，此時無法將該用戶與其他（k-1）個用戶相區(qū)別，稱此位置滿足位置k-匿名。

將任意用戶的位置以一個三元組([x1,x2],[y1,y2],[t1,t2])表示，其中([x1,x2],[y1,y2])描述了對象所在的二維空間區(qū)域，[t1,t2]表示一個時間段。([x1,x2],[y1,y2],[t1,t2])表示用戶在這個時間段的某一個時間點出現(xiàn)在([x1,x2],[y1,y2])所表示的二維空間中的某一點。除此用戶外，還有其他至少（k-1）個用戶也在此時間段內(nèi)的某個時間出現(xiàn)在([x1,x2],[y1,y2])的二維空間的某一點，這樣的用戶集合滿足位置k-匿名。位置K-匿名模型（LocationK-Anonymity原始查詢匿名后查詢K=3隱私保護(hù)需求的四個參數(shù)：

k：即

k-匿名，用戶要求返回的匿名集中至少包含的用戶數(shù)。Amin：匿名空間的最小值，返回的匿名空間必須要超過此值，可以是面積或半徑等。Amax：匿名空間的最大值，返回的匿名空間必須不能超過此值，也可以是面積或半徑等。Tmax：可容忍的最長匿名延遲時間。即從用戶提出請求的時刻起需要在Tmax的時間范圍內(nèi)完成用戶的匿名。原始查詢匿名后查詢K=3隱私保護(hù)需求的四個參數(shù)：隱私保護(hù)技術(shù)假位置空間匿名時空匿名DummySpatialCloakingSpatio-TemporalCloaking隱私保護(hù)技術(shù)假位置空間匿名時空匿名DummySpatial一、假位置位置匿名查詢處理不公開真實服務(wù)請求的位置，而是公布假位置，即啞元(Dummy)。用戶發(fā)送多個不同的位置信息給服務(wù)器，而這些位置信息中只有一個是該用戶的真實準(zhǔn)確位置，其他的都是錯誤的或假的位置信息。這樣即使惡意的攻擊者獲取了某個用戶的位置信息，也不能推測出該用戶的準(zhǔn)確位置?；诩傥恢玫哪涿樵儯恢脭?shù)據(jù)庫中的查詢處理器無需作任何修改，因為發(fā)送給位置數(shù)據(jù)庫服務(wù)器的仍是一些明確的位置點，可以直接利用已有的數(shù)據(jù)庫查詢處理技術(shù)完成各種查詢，。只是返回的結(jié)果不一定是真實結(jié)果，存在一定的誤差。一、假位置位置匿名查詢處理不公開真實服務(wù)請求的位置，而是公布二、空間匿名降低對象的空間粒度，用一個空間區(qū)域來表示用戶的真實精確位置，區(qū)域的形狀不限，普遍使用圓和矩形。同時結(jié)合

k-匿名的思想來構(gòu)造，即用戶提供給服務(wù)器的位置區(qū)域不僅需要包含該用戶的準(zhǔn)確位置，并且還需要包含其他k-1個移動用戶。這樣用區(qū)域表示位置之后，用戶在此區(qū)域內(nèi)每一個位置上出現(xiàn)的概率相同。攻擊者僅能知道用戶在這個空間區(qū)域內(nèi)，卻無法確定具體的位置。二、空間匿名降低對象的空間粒度，用一個空間區(qū)域來表示用戶的真三、時空匿名時空匿名就是在空間匿名的基礎(chǔ)上，增加一個時間軸。在擴(kuò)大位置區(qū)域的同時，延遲響應(yīng)時間，可以在這段時間中出現(xiàn)更多的用戶、提出更多的查詢，隱私匿名度更高。三、時空匿名時空匿名就是在空間匿名的基礎(chǔ)上，增加一個時間軸?；诳臻g匿名與時空匿名的查詢處理用戶發(fā)送給位置服務(wù)器的不再是精確的位置點，而是一個匿名框。用戶在框內(nèi)的每一個位置出現(xiàn)的概率相同，查詢處理器無法獲知移動用戶的確切位置。傳統(tǒng)的查詢方式不再適用。查詢處理器查詢的類別基于位置數(shù)據(jù)庫服務(wù)器中的數(shù)據(jù)可以分為兩種：公開數(shù)據(jù)和隱私數(shù)據(jù)。相應(yīng)的，根據(jù)查詢點和被查詢點是否隱私，可以將查詢分為四種。查詢結(jié)果一、在候選結(jié)果集中隨機(jī)挑選一個對象作為結(jié)果返回給用戶；二、返回整個候選集，用戶或第三方可信件求精；三、以概率查詢處理技術(shù)處理查詢結(jié)果。基于空間匿名與時空匿名的查詢處理用戶發(fā)送給位置服務(wù)器的不再是查詢類型被查詢點公開數(shù)據(jù)隱私數(shù)據(jù)查詢點公開數(shù)據(jù)基于公開數(shù)據(jù)的公開查詢?nèi)纾耗畴娪霸?00米內(nèi)所有的餐館基于隱私數(shù)據(jù)的公開查詢?nèi)纾杭佑驼?00米內(nèi)的所有出租車隱私數(shù)據(jù)基于公開數(shù)據(jù)的隱私查詢?nèi)纾壕嚯x我最近的加油站基于隱私數(shù)據(jù)的隱私查詢?nèi)纾弘x我最近的朋友某加油站500米內(nèi)的所有出租車※將所有與查詢范圍相交的匿名區(qū)域都作為候選集?！鶎⒛涿蚺c圓形框的重疊區(qū)域面積大小表示查詢結(jié)果是真正結(jié)果的概率。查詢結(jié)果：（B，50%）（C，90%）（D，1）（E，60%）示例查詢被查詢點公開數(shù)據(jù)隱私數(shù)據(jù)公開基于公開三種匿名技術(shù)的對比假位置空間匿名時空匿名DummySpatialCloakingSpatio-TemporalCloaking三種匿名技術(shù)的對比假位置空間匿名時空匿名DummySpati基于P2P的位置匿名算法實現(xiàn)

現(xiàn)有系統(tǒng)區(qū)域被劃分成網(wǎng)格的形式，要求移動用戶通過與其他用戶的通信查找到k-1個用戶，將自己真實的位置點擴(kuò)大為一個模糊的匿名空間，使得該范圍覆蓋了k個用戶的位置，同時還必須滿足Amin。假定匿名空間是一個矩形，用一個左下-右上的二元（[xl,yb][xr,yu]）表示。如何實現(xiàn)這一過程呢？？基于P2P的位置匿名算法實現(xiàn)現(xiàn)有系統(tǒng)區(qū)域被劃算法一：FunctionP2PAnonymity-Requestor(k,d)1、初始化：令已找到用戶的集合S′={?}，已經(jīng)找到用戶的個數(shù)k′=│s′│=0，跳數(shù)的初始值h=1，d為用戶的度，k為匿名度，hmax為最大跳數(shù)，flag為標(biāo)志位。2、if(d≥k-1)then{

以單跳形式廣播查找請求，尋找k-1用戶；

}else{

hmax=最大跳數(shù)；

flag=0；

do

{

以多跳形式開始廣播查找請求；

S

是經(jīng)過多跳形式返回的已找到的用戶集合，則k′=│s│；度是指與該用戶在一個通訊范圍內(nèi)用戶的數(shù)目。單跳指由發(fā)站直接到收站的一次性傳輸；多跳指由發(fā)站到收站經(jīng)過多次轉(zhuǎn)發(fā)的方式。移動用戶m如果想要獲得服務(wù)，首先將已找到用戶的集合S′置為空集，已找到用戶的個數(shù)k′賦為0。然后，用戶m通過比較隱私檔案中k值和自身度d的大小，選擇相應(yīng)的方式（單跳或多跳）向其周圍的用戶發(fā)送一個消息序號ID來廣播查找請求，用戶m監(jiān)聽網(wǎng)絡(luò)，等待周圍用戶的響應(yīng)?；赑2P的位置匿名算法實現(xiàn)算法一：FunctionP2PAnonymity-Req算法二:FunctionP2PAnonymity-Receiver(h)1、if（一個請求是重復(fù)的）then

通過一個ACK消息回應(yīng)服務(wù)的請求者；

return；2、if(h=1)then

發(fā)送一個元組(ID，[xr,yr]，vmax，tr，h)

回應(yīng)服務(wù)的請求者；

else

{

h=h-1；廣播查找請求；

S

是查找到的用戶的集合；

forSi∈SdoSi.h=Si.h+1;S=S∪(ID，[xr,yr]，vmax，tr，h);

返回S

到服務(wù)的請求者；

}

（1）當(dāng)請求的接收者r接收到來自服務(wù)請求者m（可能是請求的發(fā)起者，也可能是請求的轉(zhuǎn)發(fā)者）的查找請求后：首先基于消息序號ID請求的接收者r檢查該請求是否為一個重復(fù)的請求。若是，則返回一個ACK消息。否則，基于h的大小處理請求。（2）當(dāng)h=1（單跳）時，r返回一個包含ID、當(dāng)前位置、最大運動速度、時間戳和跳數(shù)的元組(ID，[xr,yr]，vmax，tr，h)給請求者；（3）當(dāng)h>1（多跳）時，r遞減h的值，再向周圍用戶發(fā)送原始的消息序號ID來廣播查找請求。r監(jiān)聽整個網(wǎng)絡(luò)，等待周圍用戶的響應(yīng)，直到收集到所有其周圍用戶的回復(fù)。最后，r分別遞增收集到的元組中的h值，同時將自己的元組信息一起添加到已收集的元組中構(gòu)成集合S，返回給請求的發(fā)起者或轉(zhuǎn)發(fā)者r?；赑2P的位置匿名算法實現(xiàn)算法二:FunctionP2PAnonymity-Redo

{

以多跳形式開始廣播查找請求；

S

是經(jīng)過多跳形式返回的已找到的用戶集合，則k′=│s′│；

if(flag==0)then

{

服務(wù)請求者中心位置的調(diào)整；

flag=1；

}

if(k′<k-1)then

if(S=S′||h=hmax)then

請求掛起；

h=h+1；

S′=S；

}while(k′=

k-1)；

}·當(dāng)請求的發(fā)起者m經(jīng)過一次查找請求后得到的用戶數(shù)小于k-1時，它將繼續(xù)遞增h的值，并且以一個新的消息序號ID重新廣播請求，重復(fù)此過程，直到找到k-1個用戶?！ぶ档米⒁獾氖?，如果在兩次連續(xù)的廣播后得到的結(jié)果集相同，或者，當(dāng)跳數(shù)h的值超過規(guī)定的最大跳數(shù)時，m則需要釋放他的隱私檔案，選擇一個更小的k值，或是將請求掛起一段時間，隨即再次發(fā)出查找請求服務(wù)。當(dāng)用戶只是通過單跳的形式就可以查找到滿足匿名要求的用戶數(shù)時，即d≥k-1，這說明用戶處于一個相對密集的區(qū)域，用戶的移動對其位置匿名影響不大。但當(dāng)用戶采用多跳的形式查找用戶時，即用戶所處的區(qū)域相對稀疏時，必須考慮用戶位置的調(diào)整?；赑2P的位置匿名算法實現(xiàn)do·當(dāng)請求的發(fā)起者m經(jīng)過一次查找請求后得到3、forallSi′∈S′do

調(diào)整集合中每個用戶的位置范圍；4、形成一個包含這k個用戶的最小匿名空間A；5、if(A<Amin)then

擴(kuò)大區(qū)域A

到Amin；

算法結(jié)束?。?！如果所形成的匿名空間A<Amin，則擴(kuò)大空間A到Amin。最后，服務(wù)的請求者m將包含匿名空間A的查詢發(fā)送到基于位置的社會性網(wǎng)絡(luò)數(shù)據(jù)庫服務(wù)器。經(jīng)過處理之后，返回給用戶一個查詢結(jié)果的候選集，用戶根據(jù)自己的精確位置對候選結(jié)果集求精?；赑2P的位置匿名算法實現(xiàn)3、forallSi′∈S′do如果所形成的匿名空間位置服務(wù)與隱私保護(hù)課件位置服務(wù)（LBS）中的隱私保護(hù)位置服務(wù)（LBS）中的隱私保護(hù)位置服務(wù)（LBS）位置服務(wù)簡言之，就是基于地理位置數(shù)據(jù)而展開的服務(wù)。是指通過移動終端和無線通訊網(wǎng)絡(luò)（或衛(wèi)星定位系統(tǒng)）的相互配合，以空間數(shù)據(jù)庫為基礎(chǔ)，確定移動用戶的實際地理位置或坐標(biāo)，并將其與其他信息整合起來，為用戶提供所需要的與位置相關(guān)的增值服務(wù)。LBSLBS：LocationBasedServiceServicesthatintergrateamobiledevice’slocationorpositionwithotherinformationsoastoprovideaddedvaluetoauser位置服務(wù)（LBS）位置簡言之，就是基于地理位置數(shù)據(jù)而展GPSSENSORRFID緊急救援服務(wù)信息娛樂服務(wù)分發(fā)服務(wù)交通導(dǎo)航跟蹤服務(wù)定位最近的救援者位置查找距離我百米內(nèi)最近的銀行向我餐館500米范圍內(nèi)的用戶發(fā)送電子優(yōu)惠券查找到達(dá)目的地的最優(yōu)路徑對航空物流進(jìn)行追蹤GPSSENSORRFID緊急救援服務(wù)信息娛樂服務(wù)分發(fā)服務(wù)交位置服務(wù)前景廣闊…...2007年以來中國位置服務(wù)市場規(guī)模及增長市場規(guī)模位置服務(wù)前景廣闊…...2007年以來中國位置服務(wù)市場規(guī)模及位置服務(wù)前景廣闊…...用戶數(shù)量2007年以來中國位置服務(wù)用戶規(guī)模及增長全球及國內(nèi)移動位置服務(wù)市場發(fā)展階段對比位置服務(wù)前景廣闊…...用戶數(shù)量2007年以來中國位置服務(wù)用

位置服務(wù)（LBS）軍事產(chǎn)業(yè)政府事務(wù)求助服務(wù)追蹤監(jiān)控定位導(dǎo)航休閑娛樂分發(fā)服務(wù)Formoracle位置服務(wù)前景廣闊…...使用領(lǐng)域位置服務(wù)軍事產(chǎn)業(yè)政府事務(wù)求助服務(wù)追蹤監(jiān)控定位導(dǎo)航休閑娛

1432也許某天，當(dāng)你經(jīng)過熟悉的星巴克，打開手機(jī)記錄你的位置，卻驚喜地發(fā)現(xiàn)一位好友也正在這里享用咖啡。而在不遠(yuǎn)處的商場內(nèi)，某件你關(guān)注了很久的名牌襯衫正在打折……又或者你去一個遙遠(yuǎn)的城市旅行，打開手機(jī)，卻發(fā)現(xiàn)自己瞬間對這個陌生的地方變得如此熟悉，想去哪兒就能隨心所欲，想玩什么立馬就能朝著目標(biāo)出發(fā)……此時，你肯定會為位置服務(wù)所帶來的便捷生活方式而興奮！可是你又是否設(shè)想過，未來，無論你走到哪里，上班，下班，旅行亦或是散步，都會有漫天飛舞的各種廣告鋪天蓋地向你席卷而來，你無處躲藏，只能被淹沒在信息的垃圾中煩惱嘆息……甚至有一天，對你而言，無論是熟悉的親朋還是陌生人，都沒有了秘密，每天無論你走到哪兒，干了什么，將要去哪，甚至你最近喜歡什么，想要計劃什么，大家都能知道的時候，你會不會又對這一新興的服務(wù)產(chǎn)生恐懼呢。。。隱私問題??！1432也許某天，當(dāng)你經(jīng)過熟悉的星巴克，打開手機(jī)記錄你如何解決位置服務(wù)中堪憂的隱私保護(hù)問題呢？如何解決位置服務(wù)中堪憂的隱私保護(hù)問題呢？內(nèi)容導(dǎo)覽導(dǎo)引：隱私保護(hù)問題隱私保護(hù)的系統(tǒng)結(jié)構(gòu)隱私保護(hù)模型與匿名技術(shù)隱私保護(hù)的算法實現(xiàn)內(nèi)容導(dǎo)覽導(dǎo)引：隱私保護(hù)問題隱私保護(hù)的系統(tǒng)結(jié)構(gòu)隱私保護(hù)模4隱私問題舉例生活中這樣的例子很常見：張某利用自己帶有GPS的手機(jī)提出了“尋找距離我（現(xiàn)在所在位置）最近的腫瘤醫(yī)院”的查詢。這是導(dǎo)航系統(tǒng)中一個普通的最近鄰查詢（即NN查詢）。此查詢被提交給服務(wù)提供商，比如GoogleMaps，再由服務(wù)提供商通過查詢空間數(shù)據(jù)庫返回給用戶查詢結(jié)果。此時涉及到的隱私問題包含兩個方面：一是用戶不想讓人知道他此刻所在的位置,比如銀行。二是用戶不想讓任何人知道自己提出了某方面的查詢，如張某不想讓人知道自己將去腫瘤醫(yī)院。4隱私問題舉例生活中這樣的例子很常見：張某利用自己帶有GPS4位置服務(wù)中的隱私泄露查詢隱私泄露其他人以任何方式獲知對象過去或現(xiàn)在的位置。位置隱私泄露

查詢請求的內(nèi)容，可能透露用戶的行為模式（如經(jīng)常走的道路及經(jīng)過的頻率）、興趣愛好（如喜歡去哪個商店、哪種俱樂部）、健康狀況（如經(jīng)常去的心理咨詢診所）以及政治傾向等個人隱私信息。4位置服務(wù)中的隱私泄露查詢隱私泄露其他人以任何方式獲知對象過4隱私泄露的三種途徑觀察（Observation）攻擊者從位置設(shè)備或者位置服務(wù)器中直接獲取用戶的位置信息。（如利用手機(jī)內(nèi)置GPS定位導(dǎo)致的位置信息泄露）直接交流（DirectCommunication）攻擊者通過“位置”連接外部的數(shù)據(jù)源（或者背景知識）從而確定在該位置或者發(fā)送該消息的用戶。（如查詢信息A是從別墅B發(fā)出的，當(dāng)攻擊者知道別墅B的主人是C這一背景時，那么就能確定A是由C發(fā)出的）攻擊者通過觀察被攻擊者的行為直接獲取位置信息。（如攻擊者跟蹤被攻擊者）連接泄露（LinkAttack）4隱私泄露的三種途徑觀察（Observation）攻擊者從位4位置服務(wù)中的隱私保護(hù)查詢隱私保護(hù)避免用戶與某一精確位置匹配。。位置隱私保護(hù)

避免用戶與某一敏感查詢匹配。4位置服務(wù)中的隱私保護(hù)查詢隱私保護(hù)避免用戶與某一精確位置匹配4尋找一種狀態(tài)，在這種狀態(tài)下很多對象組成一個集合（匿名集），從集合的外面向里看，組成集合的各個對象無法被區(qū)分，使得某一個位置的信息無法與確切的個人/組織/機(jī)構(gòu)相匹配。位置信息經(jīng)過匿名處理后不再是用戶的真實位置，可能是多個位置的集合或者一個模糊化的位置，查詢系統(tǒng)應(yīng)該對應(yīng)地返回包含真實查詢信息的模糊信息集隱私保護(hù)的工作位置匿名查詢處理4尋找一種狀態(tài)，在這種狀態(tài)下很多對象組成一個集合（匿名集），4位置服務(wù)VS隱私保護(hù)魚與熊掌可否兼得？位置服務(wù)隱私保護(hù)提供精確位置隱藏用戶位置不能兼得??！只能尋找平衡點！在最少的位置暴露下獲得最好的服務(wù)，使隱私暴露處于“可控狀態(tài)”！4位置服務(wù)VS隱私保護(hù)魚與熊掌可否兼得？位置服務(wù)隱私保護(hù)提供隱私保護(hù)的特點保護(hù)位置隱私與享受服務(wù)是一對矛盾位置信息的多維性特點位置匿名的即時性特點基于位置匿名的查詢處理位置隱私需求個性化隱私保護(hù)的特點保護(hù)位置隱私與享受服務(wù)是一對矛盾位置信息的多維

隱私保護(hù)的系統(tǒng)結(jié)構(gòu)Non-cooperativeArchitecture獨立結(jié)構(gòu)中心服務(wù)器結(jié)構(gòu)CentralizedArchitecture分布式點對點結(jié)構(gòu)Peer-to-peerArchitecture僅有客戶端與位置數(shù)據(jù)庫服務(wù)器的C/S結(jié)構(gòu)。該結(jié)構(gòu)需要移動用戶擁有具有強(qiáng)大定位、計算、存儲能力的設(shè)備，自己完成位置匿名和查詢結(jié)果求精。在用戶和位置數(shù)據(jù)庫服務(wù)器之間加入第三方可信中間件——位置匿名服務(wù)器，并由位置匿名服務(wù)器完成匿名處理和查詢結(jié)果求精。由客戶端和位置數(shù)據(jù)庫服務(wù)器組成，移動客戶端根據(jù)匿名算法找到其他一些移動用戶組成一個匿名組，以此進(jìn)行位置匿名。同時組內(nèi)的客戶端之間的節(jié)點具有平等性，共同協(xié)調(diào)完成查詢結(jié)果求精。隱私保護(hù)的系統(tǒng)結(jié)構(gòu)Non-cooperative獨立結(jié)獨立結(jié)構(gòu)缺點：對客戶端要求高；缺乏全局信息，隱蔽性弱優(yōu)點：結(jié)構(gòu)簡單，易于配置處理流程：將匿名后的位置連帶查詢一起發(fā)送給位置數(shù)據(jù)庫服務(wù)器；位置服務(wù)器根據(jù)匿名的位置進(jìn)行查詢處理并將候選結(jié)果集返回給用戶；用戶根據(jù)真實位置挑選出真正的結(jié)果。獨立結(jié)構(gòu)示意圖獨立結(jié)構(gòu)缺點：對客戶端要求高；優(yōu)點：結(jié)構(gòu)簡單，易于配置優(yōu)點缺點中心服務(wù)器結(jié)構(gòu)處理過程：（1）用戶發(fā)送包含精確位置的查詢請求給位置匿名服務(wù)器。（2）匿名服務(wù)器使用某種匿名算法完成位置匿名后，將匿名后的請求發(fā)送給位置數(shù)據(jù)庫服務(wù)器。（3）位置數(shù)據(jù)庫服務(wù)器根據(jù)匿名區(qū)域進(jìn)行查詢處理，并將查詢結(jié)果的候選集返回給位置匿名服務(wù)器。（4）位置匿名服務(wù)器從候選結(jié)果集中挑出真正的結(jié)果返回給移動用戶。具有全局信息，隱私保護(hù)效果好。位置匿名服務(wù)器成為系統(tǒng)的瓶頸；位置匿名服務(wù)器還可以成為隱私泄露的唯一攻擊點。優(yōu)點缺點中心服務(wù)器結(jié)構(gòu)處理過程：（1）用戶發(fā)送包含精分布式點對點結(jié)構(gòu)ThemeGalleryisaDesignDigitalContent&ContentsmalldevelopedbyGuildDesignInc.優(yōu)點：擁有全局信息，隱私效果好；消除了系統(tǒng)瓶頸；消除了唯一攻擊點。缺點：網(wǎng)絡(luò)通訊代價高。處理過程：（1）移動客戶端根據(jù)匿名算法建立一個匿名組，進(jìn)行位置匿名。（2）根據(jù)實際的網(wǎng)絡(luò)通訊情況選擇一個合適的頭結(jié)點，頭結(jié)點將匿名后的查詢請求發(fā)送給位置數(shù)據(jù)庫服務(wù)器。（3）位置數(shù)據(jù)庫服務(wù)器根據(jù)匿名區(qū)域進(jìn)行查詢處理，并將查詢結(jié)果的候選集返回給頭結(jié)點。（4）頭結(jié)點可以選擇出真實結(jié)果發(fā)送給提出查詢的用戶，也可以將查詢結(jié)果的候選集發(fā)送給用戶，由用戶自己挑選出真實的結(jié)果。頭結(jié)點平衡網(wǎng)絡(luò)負(fù)載！??！分布式點對點結(jié)構(gòu)ThemeGalleryisaDesi位置K-匿名模型（LocationK-AnonymityModel）隱私保護(hù)模型模型描述模型定義

把某一用戶的真實位置點擴(kuò)大為一個模糊的位置范圍，使得該范圍覆蓋k個用戶的位置，此時無法將該用戶與其他（k-1）個用戶相區(qū)別，稱此位置滿足位置k-匿名。

將任意用戶的位置以一個三元組([x1,x2],[y1,y2],[t1,t2])表示，其中([x1,x2],[y1,y2])描述了對象所在的二維空間區(qū)域，[t1,t2]表示一個時間段。([x1,x2],[y1,y2],[t1,t2])表示用戶在這個時間段的某一個時間點出現(xiàn)在([x1,x2],[y1,y2])所表示的二維空間中的某一點。除此用戶外，還有其他至少（k-1）個用戶也在此時間段內(nèi)的某個時間出現(xiàn)在([x1,x2],[y1,y2])的二維空間的某一點，這樣的用戶集合滿足位置k-匿名。位置K-匿名模型（LocationK-Anonymity原始查詢匿名后查詢K=3隱私保護(hù)需求的四個參數(shù)：

k：即

k-匿名，用戶要求返回的匿名集中至少包含的用戶數(shù)。Amin：匿名空間的最小值，返回的匿名空間必須要超過此值，可以是面積或半徑等。Amax：匿名空間的最大值，返回的匿名空間必須不能超過此值，也可以是面積或半徑等。Tmax：可容忍的最長匿名延遲時間。即從用戶提出請求的時刻起需要在Tmax的時間范圍內(nèi)完成用戶的匿名。原始查詢匿名后查詢K=3隱私保護(hù)需求的四個參數(shù)：隱私保護(hù)技術(shù)假位置空間匿名時空匿名DummySpatialCloakingSpatio-TemporalCloaking隱私保護(hù)技術(shù)假位置空間匿名時空匿名DummySpatial一、假位置位置匿名查詢處理不公開真實服務(wù)請求的位置，而是公布假位置，即啞元(Dummy)。用戶發(fā)送多個不同的位置信息給服務(wù)器，而這些位置信息中只有一個是該用戶的真實準(zhǔn)確位置，其他的都是錯誤的或假的位置信息。這樣即使惡意的攻擊者獲取了某個用戶的位置信息，也不能推測出該用戶的準(zhǔn)確位置?；诩傥恢玫哪涿樵儯恢脭?shù)據(jù)庫中的查詢處理器無需作任何修改，因為發(fā)送給位置數(shù)據(jù)庫服務(wù)器的仍是一些明確的位置點，可以直接利用已有的數(shù)據(jù)庫查詢處理技術(shù)完成各種查詢，。只是返回的結(jié)果不一定是真實結(jié)果，存在一定的誤差。一、假位置位置匿名查詢處理不公開真實服務(wù)請求的位置，而是公布二、空間匿名降低對象的空間粒度，用一個空間區(qū)域來表示用戶的真實精確位置，區(qū)域的形狀不限，普遍使用圓和矩形。同時結(jié)合

k-匿名的思想來構(gòu)造，即用戶提供給服務(wù)器的位置區(qū)域不僅需要包含該用戶的準(zhǔn)確位置，并且還需要包含其他k-1個移動用戶。這樣用區(qū)域表示位置之后，用戶在此區(qū)域內(nèi)每一個位置上出現(xiàn)的概率相同。攻擊者僅能知道用戶在這個空間區(qū)域內(nèi)，卻無法確定具體的位置。二、空間匿名降低對象的空間粒度，用一個空間區(qū)域來表示用戶的真三、時空匿名時空匿名就是在空間匿名的基礎(chǔ)上，增加一個時間軸。在擴(kuò)大位置區(qū)域的同時，延遲響應(yīng)時間，可以在這段時間中出現(xiàn)更多的用戶、提出更多的查詢，隱私匿名度更高。三、時空匿名時空匿名就是在空間匿名的基礎(chǔ)上，增加一個時間軸?；诳臻g匿名與時空匿名的查詢處理用戶發(fā)送給位置服務(wù)器的不再是精確的位置點，而是一個匿名框。用戶在框內(nèi)的每一個位置出現(xiàn)的概率相同，查詢處理器無法獲知移動用戶的確切位置。傳統(tǒng)的查詢方式不再適用。查詢處理器查詢的類別基于位置數(shù)據(jù)庫服務(wù)器中的數(shù)據(jù)可以分為兩種：公開數(shù)據(jù)和隱私數(shù)據(jù)。相應(yīng)的，根據(jù)查詢點和被查詢點是否隱私，可以將查詢分為四種。查詢結(jié)果一、在候選結(jié)果集中隨機(jī)挑選一個對象作為結(jié)果返回給用戶；二、返回整個候選集，用戶或第三方可信件求精；三、以概率查詢處理技術(shù)處理查詢結(jié)果?；诳臻g匿名與時空匿名的查詢處理用戶發(fā)送給位置服務(wù)器的不再是查詢類型被查詢點公開數(shù)據(jù)隱私數(shù)據(jù)查詢點公開數(shù)據(jù)基于公開數(shù)據(jù)的公開查詢?nèi)纾耗畴娪霸?00米內(nèi)所有的餐館基于隱私數(shù)據(jù)的公開查詢?nèi)纾杭佑驼?00米內(nèi)的所有出租車隱私數(shù)據(jù)基于公開數(shù)據(jù)的隱私查詢?nèi)纾壕嚯x我最近的加油站基于隱私數(shù)據(jù)的隱私查詢?nèi)纾弘x我最近的朋友某加油站500米內(nèi)的所有出租車※將所有與查詢范圍相交的匿名區(qū)域都作為候選集。※將匿名框與圓形框的重疊區(qū)域面積大小表示查詢結(jié)果是真正結(jié)果的概率。查詢結(jié)果：（B，50%）（C，90%）（D，1）（E，60%）示例查詢被查詢點公開數(shù)據(jù)隱私數(shù)據(jù)公開基于公開三種匿名技術(shù)的對比假位置空間匿名時空匿名DummySpatialCloakingSpatio-TemporalCloaking三種匿名技術(shù)的對比假位置空間匿名時空匿名DummySpati基于P2P的位置匿名算法實現(xiàn)

現(xiàn)有系統(tǒng)區(qū)域被劃分成網(wǎng)格的形式，要求移動用戶通過與其他用戶的通信查找到k-1個用戶，將自己真實的位置點擴(kuò)大為一個模糊的匿名空間，使得該范圍覆蓋了k個用戶的位置，同時還必須滿足Amin。假定匿名空間是一個矩形，用一個左下-右上的二元（[xl,yb][xr,yu]）表示。如何實現(xiàn)這一過程呢？？基于P2P的位置匿名算法實現(xiàn)現(xiàn)有系統(tǒng)區(qū)域被劃算法一：FunctionP2PAnonymity-Requestor(k,d)1、初始化：令已找到用戶的集合S′={?}，已經(jīng)找到用戶的個數(shù)k′=│s′│=0，跳數(shù)的初始值h=1，d為用戶的度，k為匿名度，hmax為最大跳數(shù)，flag為標(biāo)志位。2、if(d≥k-1)then{

以單跳形式廣播查找請求，尋找k-1用戶；

}else{

hmax=最大跳數(shù)；

flag=0；

do

{

以多跳形式開始廣播查找請求；

S

是經(jīng)過多跳形式返回的已找到的用戶集合，則k′=│s│；度是指與該用戶在一個通訊范圍內(nèi)用戶的數(shù)目。單跳指由發(fā)站直接到收站的一次性傳輸；多跳指由發(fā)站到收站經(jīng)過多次轉(zhuǎn)發(fā)的方式。移動用戶m如果想要獲得服務(wù)，首先將已找到用戶的集合S′置為空集，已找到用戶的個數(shù)k′賦為0。然后，用戶m通過比較隱私檔案中k值和自身度d的大小，選擇相應(yīng)的方式（單跳或多跳）向其周圍的用戶發(fā)送一個消息序號ID來廣播查找請求，用戶m監(jiān)聽網(wǎng)絡(luò)，等待周圍用戶的響應(yīng)?；赑2P的位置匿名算法實現(xiàn)算法一：FunctionP2PAnonymity-Req算法二:FunctionP2PAnonymity-Receiver(h)1、if（一個請求是重復(fù)的）then

通過一個ACK消息回應(yīng)服務(wù)的請求者；

return；2、if(h=1)then

發(fā)送一個元組(ID，[xr,yr]，vmax，tr，h)

回應(yīng)服務(wù)的請求者；

else

{

h=h-1；廣播查找請求；