1、 位置位置 服務服務 簡言之，就是簡言之，就是基于地理位置數據基于地理位置數據而展開的服務。是指通而展開的服務。是指通 過移動終端和無線通訊網絡（或衛星定位系統）的相互過移動終端和無線通訊網絡（或衛星定位系統）的相互 配合，以空間數據庫為基礎，確定移動用戶的實際地理配合，以空間數據庫為基礎，確定移動用戶的實際地理 位置或坐標，并將其與其他信息整合起來，為用戶提供位置或坐標，并將其與其他信息整合起來，為用戶提供 所需要的與位置相關的增值服務。所需要的與位置相關的增值服務。 LBS LBS：Location Based Service Services that intergrate a mobi

2、le devices location or position with other information so as to provide added value to a user GPS SENSOR RFID 緊急救援服務緊急救援服務 信息娛樂服務信息娛樂服務 分發服分發服 務務 交通導航交通導航 跟蹤服務跟蹤服務 定位最近的救援者位置定位最近的救援者位置 查找距離我百米內最近的銀行查找距離我百米內最近的銀行 向我餐館向我餐館500500米范圍內的用戶發送電子優惠券米范圍內的用戶發送電子優惠券 查找到達目的地的最優路徑查找到達目的地的最優路徑 對航空物流進行追蹤對航空物流進行追蹤 位

3、置服務前景廣闊位置服務前景廣闊. 20072007年以來中國位置服務市場規模及增長年以來中國位置服務市場規模及增長 市場規模市場規模 位置服務前景廣闊位置服務前景廣闊. 用戶數量用戶數量 20072007年以來中國位置服務用戶規模及增長年以來中國位置服務用戶規模及增長 全球及國內移動位置服務市場發展階段對比全球及國內移動位置服務市場發展階段對比 位置服務位置服務 （LBS） 軍事產業軍事產業 政府事務政府事務 求助服務求助服務 追蹤監控追蹤監控 定位導航定位導航 休閑娛樂休閑娛樂 分發服務分發服務 Form oracle 位置服務前景廣闊位置服務前景廣闊. 使用領域 也許某天，當你經過熟悉的星

4、巴克，也許某天，當你經過熟悉的星巴克， 打開手機記錄你的位置，卻驚喜地發打開手機記錄你的位置，卻驚喜地發 現一位好友也正在這里享用咖啡。而現一位好友也正在這里享用咖啡。而 在不遠處的商場內，某件你關注了很在不遠處的商場內，某件你關注了很 久的名牌襯衫正在打折久的名牌襯衫正在打折 又或者你去一個遙遠的城市旅行，打又或者你去一個遙遠的城市旅行，打 開手機，卻發現自己瞬間對這個陌生開手機，卻發現自己瞬間對這個陌生 的地方變得如此熟悉，想去哪兒就能的地方變得如此熟悉，想去哪兒就能 隨心所欲，想玩什么立馬就能朝著目隨心所欲，想玩什么立馬就能朝著目 標出發標出發此時，你肯定會為位置服此時，你肯定會為位置服

5、 務所帶來的便捷生活方式而興奮！務所帶來的便捷生活方式而興奮！ 可是你又是否設想過，未來，無可是你又是否設想過，未來，無 論你走到哪里，上班，下班，旅論你走到哪里，上班，下班，旅 行亦或是散步，都會有漫天飛舞行亦或是散步，都會有漫天飛舞 的各種廣告鋪天蓋地向你席卷而的各種廣告鋪天蓋地向你席卷而 來，你無處躲藏，只能被淹沒在來，你無處躲藏，只能被淹沒在 信息的垃圾中煩惱嘆息信息的垃圾中煩惱嘆息 甚至有一天，對你而言，無論是熟甚至有一天，對你而言，無論是熟 悉的親朋還是陌生人，都沒有了秘悉的親朋還是陌生人，都沒有了秘 密，每天無論你走到哪兒，干了什密，每天無論你走到哪兒，干了什 么，將要去哪，甚至

6、你最近喜歡什么，將要去哪，甚至你最近喜歡什 么，想要計劃什么，大家都能知道么，想要計劃什么，大家都能知道 的時候，你會不會又對這一新興的的時候，你會不會又對這一新興的 服務產生恐懼呢。服務產生恐懼呢。 如何解決位置服務如何解決位置服務 中堪憂的隱私保護中堪憂的隱私保護 問題呢？問題呢？ 內內 容容 導導 覽覽 導引：隱私保護問題導引：隱私保護問題 隱私保護的系統結構隱私保護的系統結構 隱私保護模型與匿名技術隱私保護模型與匿名技術 隱私保護的算法實現隱私保護的算法實現 4 隱私問題舉例隱私問題舉例 生活中這樣的例子很常見：張某利用自己 帶有GPS的手機提出了“尋找距離我（現在 所在位置）最近的腫

7、瘤醫院”的查詢。這 是導航系統中一個普通的最近鄰查詢（即 NN查詢）。此查詢被提交給服務提供商， 比如Google Maps，再由服務提供商通過查 詢空間數據庫返回給用戶查詢結果。 此時涉及到的隱私問題包含兩個方面：一是用此時涉及到的隱私問題包含兩個方面：一是用 戶不想讓人知道他此刻所在的位置戶不想讓人知道他此刻所在的位置, ,比如銀行。比如銀行。 二是用戶不想讓任何人知道自己提出了某方面二是用戶不想讓任何人知道自己提出了某方面 的查詢，如張某不想讓人知道自己將去腫瘤醫的查詢，如張某不想讓人知道自己將去腫瘤醫 院。院。 4 位置服務中的隱私泄露位置服務中的隱私泄露 查詢隱私泄露查詢隱私泄露 其

8、他人以任何方式獲知對象過去或現在的位置。 位置隱私泄露位置隱私泄露 查詢請求的內容，可能透露用戶的行為模式（如經常走的 道路及經過的頻率）、興趣愛好（如喜歡去哪個商店、哪 種俱樂部）、健康狀況（如經常去的心理咨詢診所）以及 政治傾向等個人隱私信息。 4 隱私泄露的三種途徑隱私泄露的三種途徑 觀察（觀察（Observation） 攻擊者從位置設備或者位置服務器中直接獲取用戶的位置信 息。（如利用手機內置GPS定位導致的位置信息泄露） 直接交流（直接交流（Direct Communication） 攻擊者通過“位置”連接外部的數據源（或者背景知識） 從而確定在該位置或者發送該消息的用戶。（如查詢信

9、息A 是從別墅B發出的，當攻擊者知道別墅B的主人是C這一背景 時，那么就能確定A是由C發出的） 攻擊者通過觀察被攻擊者的行為直接獲取位置信息。（如 攻擊者跟蹤被攻擊者） 連接泄露（連接泄露（Link Attack） 4 位置服務中的隱私保護位置服務中的隱私保護 查詢隱私保護查詢隱私保護 避免用戶與某一精確位置匹配。避免用戶與某一精確位置匹配。 位置隱私保護位置隱私保護 避免用戶與某一敏感查詢匹配。避免用戶與某一敏感查詢匹配。 4 尋找一種狀態，在這種尋找一種狀態，在這種 狀態下很多對象組成一狀態下很多對象組成一 個集合（匿名集），從個集合（匿名集），從 集合的外面向里看，組集合的外面向里看，組

10、 成集合的各個對象無法成集合的各個對象無法 被區分，使得某一個位被區分，使得某一個位 置的信息無法與確切的置的信息無法與確切的 個人個人/ /組織組織/ /機構相匹配機構相匹配 。 位置信息經過匿名處理位置信息經過匿名處理 后不再是用戶的真實位后不再是用戶的真實位 置，可能是多個位置的置，可能是多個位置的 集合或者一個模糊化的集合或者一個模糊化的 位置，查詢系統應該對位置，查詢系統應該對 應地返回包含真實查詢應地返回包含真實查詢 信息的模糊信息集信息的模糊信息集 隱私保護的工作隱私保護的工作 位置匿名位置匿名查詢處理查詢處理 4 位置服務位置服務VS隱私保護隱私保護 魚與熊掌可否兼得？魚與熊掌

11、可否兼得？ 位置服務位置服務隱私保護隱私保護 提供精確位置提供精確位置隱藏用戶位置隱藏用戶位置 不能兼得！只能尋找平衡點！不能兼得！只能尋找平衡點！ 在最少的位置暴露下獲得最好的服務，使在最少的位置暴露下獲得最好的服務，使 隱私暴露處于隱私暴露處于“可控狀態可控狀態”！ 隱私保護的特點隱私保護的特點 保護位置隱私與享受服務是一對矛盾保護位置隱私與享受服務是一對矛盾 位置信息的多維性特點位置信息的多維性特點 位置匿名的即時性特點位置匿名的即時性特點 基于位置匿名的查詢處理基于位置匿名的查詢處理 位置隱私需求個性化位置隱私需求個性化 隱私保護的系統結構隱私保護的系統結構 Non-cooperati

12、ve Architecture 獨立結構獨立結構 中心服務器結構中心服務器結構 Centralized Architecture 分布式點對點結構分布式點對點結構 Peer-to-peer Architecture 僅有客戶端與位置數據庫服務器的僅有客戶端與位置數據庫服務器的C/SC/S結構。該結構需結構。該結構需 要移動用戶擁有具有強大定位、計算、存儲能力的設要移動用戶擁有具有強大定位、計算、存儲能力的設 備，自己完成位置匿名和查詢結果求精。備，自己完成位置匿名和查詢結果求精。 在用戶和位置數據庫服務器之間加入第三方可信中間在用戶和位置數據庫服務器之間加入第三方可信中間 件件位置匿名服務器，

13、并由位置匿名服務器完成匿位置匿名服務器，并由位置匿名服務器完成匿 名處理和查詢結果求精。名處理和查詢結果求精。 由客戶端和位置數據庫服務器組成，移動客戶端根據由客戶端和位置數據庫服務器組成，移動客戶端根據 匿名算法找到其他一些移動用戶組成一個匿名組，以匿名算法找到其他一些移動用戶組成一個匿名組，以 此進行位置匿名。同時組內的客戶端之間的節點具有此進行位置匿名。同時組內的客戶端之間的節點具有 平等性，共同協調完成查詢結果求精。平等性，共同協調完成查詢結果求精。 獨獨 立立 結結 構構 缺點：缺點：對客戶端要求高；對客戶端要求高； 缺乏全局信息，隱蔽性弱缺乏全局信息，隱蔽性弱 優點：優點：結構簡單

14、，易于配置結構簡單，易于配置 處理流程：處理流程：將匿名后的位置連帶查詢一起發送將匿名后的位置連帶查詢一起發送 給位置數據庫服務器；位置服務器根據匿名的給位置數據庫服務器；位置服務器根據匿名的 位置進行查詢處理并將候選結果集返回給用戶；位置進行查詢處理并將候選結果集返回給用戶； 用戶根據真實位置挑選出真正的結果。用戶根據真實位置挑選出真正的結果。 獨立結構示意圖獨立結構示意圖 優優 點點缺缺 點點 中心服務器結構中心服務器結構 處理過程處理過程：（：（1 1）用戶發送包含精確位置的查詢請求給位置匿名服務器。（用戶發送包含精確位置的查詢請求給位置匿名服務器。（2 2）匿）匿 名服務器使用某種匿名

15、算法完成位置匿名后，將匿名后的請求發送給位置數據庫名服務器使用某種匿名算法完成位置匿名后，將匿名后的請求發送給位置數據庫 服務器。（服務器。（3 3）位置數據庫服務器根據匿名區域進行查詢處理，并將查詢結果的）位置數據庫服務器根據匿名區域進行查詢處理，并將查詢結果的 候選集返回給位置匿名服務器。（候選集返回給位置匿名服務器。（4 4）位置匿名服務器從候選結果集中挑出真正）位置匿名服務器從候選結果集中挑出真正 的結果返回給移動用戶。的結果返回給移動用戶。 具有全局信息，具有全局信息， 隱私保護效果好。隱私保護效果好。 位置匿名服務器位置匿名服務器 成為系統的瓶頸；成為系統的瓶頸； 位置匿名服務器位

16、置匿名服務器 還可以成為隱私還可以成為隱私 泄露的唯一攻擊泄露的唯一攻擊 點。點。 分布式點對點結構分布式點對點結構 ThemeGallery is a Design Digital Content S=S (ID，xr,yr，vmax，tr，h) ; 返回S 到服務的請求者； （1 1）當請求的接收者）當請求的接收者 r r 接收到來自服接收到來自服 務請求者務請求者m m（可能是請求的發起者，也可（可能是請求的發起者，也可 能是請求的轉發者）的查找請求后：首能是請求的轉發者）的查找請求后：首 先基于消息序號先基于消息序號 ID ID 請求的接收者請求的接收者 r r檢檢 查該請求是否為一個

17、重復的請求。若是，查該請求是否為一個重復的請求。若是， 則返回一個則返回一個 ACK ACK 消息。否則，基于消息。否則，基于 h h 的大小處理請求。的大小處理請求。 （2 2）當）當 h=1h=1（單跳單跳） 時，時，r r 返回一個返回一個 包含包含 IDID、當前位置、最大運動速度、時、當前位置、最大運動速度、時 間戳和跳數的元組間戳和跳數的元組(ID(ID，xxr r,y,yr r ，v vmax max， ， t tr r，h)h)給請求者；給請求者； （3 3）當）當 h1 h1 （多跳多跳）時，）時，r r 遞減遞減 h h 的的 值，再向周圍用戶發送原始的消息序號值，再向周圍

18、用戶發送原始的消息序號 ID ID 來廣播查找請求。來廣播查找請求。r r 監聽整個網絡，監聽整個網絡， 等待周圍用戶的響應，直到收集到所有等待周圍用戶的響應，直到收集到所有 其周圍用戶的回復。最后，其周圍用戶的回復。最后，r r 分別遞增分別遞增 收集到的元組中的收集到的元組中的 h h 值，同時將自己的值，同時將自己的 元組信息一起添加到已收集的元組中構元組信息一起添加到已收集的元組中構 成集合成集合 S S，返回給請求的發起者或轉發，返回給請求的發起者或轉發 者者 r r。 基于基于P2P的位置匿名算法實現的位置匿名算法實現 do 以以多跳多跳形式開始廣播查找請求；形式開始廣播查找請求；

19、 S 是經過多跳形式返回的已找到的用戶集合，則是經過多跳形式返回的已找到的用戶集合，則 k=s； if (flag = = 0) then 服務請求者服務請求者中心位置的調整中心位置的調整； flag=1； if ( k k-1) then if (S = S| h=hmax) then 請求掛起；請求掛起； h = h+1； S =S； while (k= k-1)； 當請求的發起者當請求的發起者 m 經過一次查經過一次查 找請求后得到的用戶數小于找請求后得到的用戶數小于 k-1 時，時， 它將繼續遞增它將繼續遞增 h的值，并且以一個的值，并且以一個 新的消息序號新的消息序號 ID 重新廣播請求，重新廣播請求， 重復此過程，直到找到重復此過程，直到找到 k-1 個用戶。個用戶。 值得注意的是，如果在兩次連值得注意的是，如果在兩次連 續的廣播后得到的結果集相同，或續的廣播后得到的結果集相同，或 者，當跳數者，當跳數 h 的值超過規定的最大的值超過規定的最大 跳數時，跳數時，m 則需要釋放他的隱私檔則需要釋放他的隱私檔 案，選擇一個更小的案，選擇一個更小的 k 值，或是將值，或是將 請求掛起一段時間，隨即再次發出請求掛起一