基于虛擬區域劃分的位置隱私保護算法*

李金龍，彭珊珊，馬程鵬，湛達昕，王安幫，李鳳銀

（曲阜師范大學，山東 日照 276826）

0 引言

近年來，隨著通信技術的進步以及手機等智能終端的應用，基于位置的服務（Location-Based Service，LBS）已被廣泛應用在社會生活的各個領域，如智能交通、應急救援、娛樂交友、廣告推送、興趣點（Points of Interest）查詢等[1]。雖然LBS 給個人和社會帶來了巨大的便利，但也引發了嚴重的隱私問題[2]。這是因為移動用戶在享受LBS 提供的服務的同時，需要向不可信的位置服務提供商（Location Service Provider，LSP）提供其所在的位置數據，這給用戶的隱私帶來了潛在的泄露風險[2]。為了讓用戶放心地使用LBS，需要添加隱私保護機制來防止用戶個人隱私被泄露。然而，添加隱私保護機制必然會導致LBS 可用性的降低和資源開銷的增加。因此，如何在隱私保護度、LBS 服務可用性以及資源開銷三者之間取得更好的平衡是LBS 隱私保護面臨的一個核心問題。

基于位置模糊的LBS 隱私保護技術主要有假名（刪除或者用一個臨時標志來替代用戶）、隨機化（添加啞元）、模糊化（泛化用戶查詢過程中的時空信息）和隱蔽化（隱蔽用戶的整個查詢）[3-4]。Kido 等人[5]認為提交給LBS 服務器的是一個包含k個位置的匿名區域而非精確的位置，但這無疑增加了服務器的負載、響應時間等負擔，降低了服務質量。Shokri等人[6]提出隱蔽化的方法，即擁有一些具體信息的用戶可以將這些信息傳遞給附近的用戶，用戶請求不是向LBS 發起查詢，而是由附近的用戶來請求查詢信息，實現對LBS 的隱蔽查詢。而這些傳統的方法無不極大地犧牲了服務質量，而且在實用性方面有很大的缺陷。此外，這些算法并未考慮到不同用戶有不同的隱私需求，不能有針對性地提供保護。

魏禮奇[7]、王輝[8]、王潔[9]等的研究以Stackelberg 博弈模型為基礎，放棄了采取線性規劃的傳統解法，結合語義特性生成假位置，使得假位置滿足語義上的有效性。康海燕[10]、崔淵博[11]、賈金營[12]等整理了常見的隱私保護策略的體系結構，展望了未來的發展方向，探討了不依靠可信第三方的隱私保護方案。賈媛媛[13]、張學軍[14]、王東偉[15]和萬交龍[4]等研究人員對現有的研究工作進行了分類歸納和闡述，重點闡述當前LBS 隱私保護研究的主流技術，指出了LBS 隱私保護研究存在的問題及可能的解決方法。

基于現有研究的情況，本文決定開發一種簡單的、最大限度保護服務質量的算法。本算法對不同用戶的隱私需求進行分級，對不同需求劃分不同等級的區域，從而獲得不同的保護效果。

1 算法概述

基于位置的服務（LBS）包括兩層含義：首先是確定移動設備或用戶所在的地理位置；其次是提供與位置相關的各類信息服務。它指的是與定位相關的各類服務系統，簡稱“定位服務”，還有另外一種叫法為“移動定位服務（Mobile Position Services，MPS）”系統。在LBS 服務盛行的今天，人們的手機應用基本都需要開啟定位功能，因此各大廠商可以輕松獲取用戶的位置信息。基于這種情況，本文設計了一種幫助用戶掩蓋真實位置的算法。

2 算法實現

2.1 算法思想

在位置隱私保護算法中，用戶的真實位置被一個擁有同等效力的虛擬位置所替代，這個虛擬位置處在根據真實位置劃分的方格區域中，如圖1 所示。實際上，這個方格區域就是針對真實位置的匿名區域，用戶的真實位置在這個匿名區域的保護下。一般的匿名保護算法所產生的虛假位置不具備用戶真實位置的同等效力，而基于虛擬區域產生的虛假位置，具有與真實位置相近的效力。當用戶在相應位置發送請求時，本文根據隱私保護程度，創造出匿名區域，在其中利用隨機算法生成一個虛擬位置。當然，根據用戶隱私保護需求的不同，產生的虛擬區域大小也有所不同，效力也有差別。最后通過打亂用戶身份信息與位置信息的組合，作為查詢請求發出，以此實現混淆的效果，最終達到更進一步的保護。

圖1 區域劃分

2.2 算法流程

基于虛擬區域劃分的位置隱私保護算法的流程如圖2 所示。該算法先輸入用戶的真實位置，將用戶的位置進行抽象，轉化成數據坐標，再根據隱私保護程度劃分虛擬區域，通過隨機算法生成代替位置，系統將不同用戶的身份和位置信息存儲起來，打亂其對應的組合，發出查詢請求。

圖2 算法流程

2.3 算法實現

2.3.1 坐標抽象

將用戶位置的經緯度（可通過GPS 獲取）直接轉化為數據信息，如（東經119°32′17″，北緯35°26′44″）可轉化為（1193217，352644）的x,y坐標值。同理，西經、南緯也可轉化為負數坐標。

2.3.2 區域劃分

區域劃分的具體步驟如下文所述。

步驟一：先根據用戶的隱私保護需求選擇要劃分的范圍，然后取范圍內任一地標的坐標為原點，將范圍內的位置坐標轉換為相對坐標，存儲在系統中，由此可得出一個區域坐標系，其中，選取的范圍可以是省、市、縣、街道等，此范圍決定混淆用戶信息的多少，需求的量化見下一步。

步驟二：通過用戶選擇的保護程度，計算概率要求，即通過虛擬區域查詢到用戶所在范圍的概率，如概率要求1/1 000，則選取用戶位置范圍S0（默認100 m2）÷區域面積S=1/1 000，即可解出區域面積S，區域長度d。

步驟三：用區域長度d和區域坐標系得出區域劃分圖。

2.3.3 代替位置生成

通過隨機數生成算法，分別輸入真實位置所在虛擬區域的x,y坐標范圍，生成代替位置的x,y坐標，將得到的新坐標轉化為經緯度信息，即產生代替位置。

其中隨機數算法采用時間作為發生器種子，可根據給出的范圍生成隨機數，所以不易復現。

2.3.4 混淆信息組合

將系統中不同用戶的身份信息與其產生的替代位置存儲起來，同時打亂原本順序，產生新的身份-位置組合用于查詢請求。

算法的偽代碼如下。

2.4 算法分析

2.4.1 安全性

隨機數的生成比較合理，不易被攻擊者找到規律，而且生成的替代位置并無語義聯系，攻擊者難以針對替代位置進行有效的語義攻擊。此外，隨機數的算法可從原理上證明難以復現，所以攻擊者很難通過替代位置找到用戶的真實位置，安全性可以得到保障。

2.4.2 效 率

算法的空間復雜度取決于參數n，時間復雜度為O(nz/2k)。本算法實現簡單，計算并不復雜，所以與其他數學模型相比效率較高，且算法所需資源較少。

2.4.3 可執行性

算法通過對應參數的輸入即可得到合適的輸出，虛擬區域的劃分及替代位置生成均由算法自動完成，因此算法的可行性很高。

3 結語

本文提出了一種基于虛擬區域劃分的位置隱私保護方案。該方案通過將傳統的隨機化算法方法與虛擬區域劃分相結合，使用位置混淆策略，對用戶在請求LBS 時的真實位置進行模糊處理，防止暴露真實位置。本機制在保證隱私性和實用性的前提下，較高地提升了服務質量，且相比其他保護算法縮短了計算時間，使隱私保護算法更具備實用性。