基于網格偏移的分散位置隱私保護方法

徐俊儀

（廣東工業大學計算機學院，廣州 510006）

0 引言

隨著移動通信技術的快速發展，用戶能夠通過移動設備精確定位所在的位置，基于位置的服務（LBS，Location-Based Service）將移動通信設備的位置和其他信息整合起來，為用戶提供增值服務[1]。用戶獲得位置服務的過程[2]，將自身的位置信息泄露給了LBSs，或者攻擊者在這個過程中截獲用戶的請求獲取相應的信息[3]。

目前針對位置服務的隱私保護方法主要有2種結構：分布式點對點結構和第三方匿名服務器結構[4]。分布式點對點結構是用戶之間進行協作，在用戶端實現位置隱匿，將隱匿請求信息發送給LBSs獲取服務；第三方匿名服務器結構是在用戶和LBSs之間添加一個匿名服務器（AS，Anonymous Server），用戶只需要將請求信息發送給AS，AS負責對用戶的請求進行匿名處理，AS向LBSs獲取信息后，篩選符合用戶需求的內容，發送給用戶[5]。

根據隱私保護方案技術的不同，主要分為群體協作技術[6-9]、空間匿名技術[10-11]、位置偏移和模糊技術[12-13]，以及基于密碼學技術[14-17]的隱私保護方案。模糊技術和位置偏移的方法比較簡單，具有較好的服務質量，安全性比較低；密碼學技術能夠保證較高的安全性，但是需要有比較強大的計算處理能力；群體協作技術對區域的人群和網絡有一定的要求。

當需要使用第三方匿名服務器的時候，現有的多是采用密碼學工具來確保用戶請求的安全性，使得LBSs和AS難以獲得用戶的個人身份信息和查詢信息。但是加密操作存在比較大的計算量，查詢請求的過程比較長，容易導致用戶服務質量下降，如響應時間的延長。其次，現有的AS對用戶的請求進行的k匿名，是在請求位置的附近搜索k-1個位置，k個位置滿足l-多樣性，在人群稀少的地圖區域，需要搜索較大的范圍才能確定匿名區域或者直接匿名失敗，因為需要滿足k匿名的要求。因此本文提出一種基于網格偏移的分散位置隱私保護方法，使LBSs和AS難以獲得用戶的確切信息，并且在進行查詢請求的時候有較低的時間開銷。為了有較高的位置分散度，在AS進行匿名的時候，根據歷史查詢數據，選取查詢內容不一樣的k-1個網格位置，并且保證選擇的位置盡量偏移匿名集合中的位置，將構成匿名集合發送給LBSs進行查詢。

1 系統結構

本文所提方法的系統結構如圖1所示，包含了四個部分，分別是用戶user，匿名服務器AS，功能服務器（Function Server，FS）和位置服務器 LBSs。

User是具備定位功能的移動設備的用戶，能夠通過GPS獲取user所在的位置loc，user以loc為基礎，構造一個矩形區域，計算偏移網格區域后將請求信息發送給AS。user向FS獲取周期更新的基礎網格Grid，Grid 可以表示為{（x0，y0）,r,TIME}，（x0,y0）表示了Grid的起始真實坐標，r表示單個網格的寬度，TIME是Grid的標識。

圖1基于不可信匿名服務器的系統結構

AS是第三方匿名服務器，其收集和保存了用戶的請求信息，對于用戶的請求，負責在歷史查詢數據中搜索符合條件的請求信息構造k匿名集合發送給LBSs，同時也負責對LBSs返回的數據進行篩選。在本方法中，AS不可信。

FS的作用是周期更新基礎網格Grid的信息，對于User和LBSs獲取Grid的請求，獲取身份信息，響應基礎網格信息Grid。

LBSs是一個大型的位置服務器，記錄了興趣點（Point Of Interest，POI）信息，負責對請求信息進行響應，將搜索的結果信息發送給AS進行篩選。

2 方法的原理

本文方法包括了四個過程：user網格化處理、AS匿名處理、LBSs查詢結果、篩選結果。以下就每個過程進行詳細說明。

2.1 User網格化處理

User設定進行查詢請求的參數，包括最小匿名區域MIN_AREA，查詢內容類型type，隱私保護度k，查詢半徑radius。隱私保護度k指示了AS進行匿名操作的時候總共需要k個查詢內容不同的位置點，type說明了查詢的類型，MIN_AREA規定了user需要生成的矩形區域面積應不小于該值，radius表明了以查詢位置點為中心進行搜索的范圍大小。

user向FS發送消息獲取基礎網格信息Grid。user通過移動設備獲得自身準確的位置loc，隨機生成一個值范圍為 0～1的數b，將 loc向隨機方向偏移 sqrt（MIN_AREA）*b 得到位置 loc’，根據 loc’生成矩形區域Rect=（{x1,y1）（,x2,y2）}，（x1,y1）表示了矩形區域左下角的坐標，（x2,y2）表示了矩形區域右上角的坐標。

根據基礎網格Grid，位置（xi,y）i計算偏移網格坐標（ci,r）i如公式（1）所示，其中r為基礎網格中的單個網格寬度。Rect根據公式（1）計算得到偏移網格坐標Rect'，Rect'={（c1,r1）（,c2,r2）}。

將Rect'，用戶隱私保護度k，用戶請求類型type以及匿名化id，基礎網格標識TIME和查詢半徑radius組成消息Mu_as發送給AS進行匿名處理，Mu_as={id,Rect',type,k,TIME,radius}。

2.2 AS匿名處理

AS對收到的Mu_as消息提取偏移網格坐標Rect'，隱私保護度k，用戶類型type，根據Rect'計算請求的中心坐標（cu,ru），將[（cu,ru）,typeu]添加到γ，γ表示匿名后的位置集合。

在歷史數據庫中搜索與type不同的k-1個請求類型typei，0

任意一個n邊形都可以劃分為n-2個三角形，多邊形的面積通過計算每個三角形的面積求和來獲得，三角形的面積s根據公式（2）求得，p是三角形的半周長，a,b,c分別是三角形的三條邊。

對typei（0

經過計算可以得到k-1個請求類型不同的最分散的網格坐標（ci,ri）,0

構造 Mas_sp消息，Mas_sp={γ，TIME}，發送給 LBSs進行查詢。

2.3 LBSs查詢結果

LBSs收到消息Mas_sp后，根據TIME向FS發送請求，獲取基礎網格信息Grid，將γ中每個typei的網格坐標（ci，ri）還原為真實坐標。

根據每個坐標（xi，yi）和typei以及查詢半徑檢索s個POI結果，POIi={（xj,yj）,infoj}，0<=j

2.4 篩選結果

AS接收到Msp_as消息后，在歷史請求列表中找到請求用戶user所請求的類型typeu，將該類型的查詢結果網格集βu發送給 user，Mas_u={βu}。

User從Mas_u中提取POI的信息，根據基礎網格Grid，對偏移網格坐標（ci,ri）根據公式（4）轉換為真實坐標（xi,yi），由于提交給AS的是偏移后的位置坐標，因此存在部分的POI是不符合user需求的，因此需要根據用戶的所在的位置（xu,yu）計算（xi,yi）距離用戶的遠近，將不在radius范圍的POI舍棄，將符合的POI結合相關info展示給user。

3 安全性和實驗結果分析

3.1 安全性分析

本文假設LBSs和AS會提供正常的服務響應用戶的請求并且具備良好的對外安全性，但是會收集用戶的查詢請求，試圖通過數據挖掘的方法探索用戶的隱私信息。

對于AS而言，其能夠獲取的是用戶的id和網格偏移信息Rect’={（c1,r1）,（c2,r2）}，根據該網格信息，AS難以直接得知用戶的位置信息，只知道用戶id的請求內容以及相對基礎網格的網格坐標。如果AS惡意獲取了基礎網格Grid，由于user對位置進行了偏移，并且發送給AS的是矩形區域，user可以在任何一個網格位置內，因此AS能夠識別用戶所在位置的概率為，當基礎網格劃分得越細，也即是r越小，用戶端的生成匿名區域相比MIN_AREA夠大，那么攻擊者需要更高的成本來識別用戶的準確位置。

對于LBSs而言，由于AS對用戶id進行了變換，其難以知道用戶的身份信息。由于請求信息經過了AS的匿名處理，LBSs能夠確定用戶的請求內容的概率為1/k。經過了user的匿名區域生成和AS的匿名處理，LBSs識別用戶位置的概率為，當k增大，能夠識別用戶位置的概率會逐漸變小，保護用戶的隱私信息。

3.2 實驗環境

本文實驗使用Thomas Brinkhoff的移動對象生成器（Network-based Generator of Moving Object）[18-19]，以城市Oldenburg生成隨機移動對象，本文所提的方法和OPEG方法[14]以及ELPP[16]方法就時間開銷、網絡通信開銷和匿名位置分散度進行實驗比較。

本文方法使用Java語言實現，運行在Windows 10操作系統上，CPU為Intel Core i7-7700。內存為8G，默認參數值如表1所示。

表1實驗默認參數

城市Oldenburg包含6105個節點，7035條邊，長為23572，寬為26915。在該區域內生隨機生成7326個POI位置?；谠搮^域生成3200個隨機位置，每個位置模擬請求位置服務。

3.3 實驗結果與分析

（1）時間消耗

實驗對比了本文方法和OPEG以及ELPP方法所需的時間。時間指的是用戶發送查詢請求到用戶獲取查詢結果所消耗的時間。如圖2所示，隨著k值的增加，本文方法消耗的時間逐漸上升，而ELPP方法并沒有隨著k值的增加而增加，原因是ELPP方法在AS端進行用戶匿名操作的時候，只需要在歷史查詢數據中選擇相同Hilbert值的其他位置即可，而本文方法需要計算多邊形的面積確定位置之間的分散度，隨著k值的增加需要計算更多的三角形面積。而OPEG方法使用保序加密，沒有使用k匿名，因此其時間消耗和k不相關，需要使用更多的時間來加解密信息。

圖2時間開銷的對比

（2）網絡通信消耗

網絡通信消耗指的是網絡上傳輸信息的數據量大小，由于是模擬位置請求過程和查詢過程，而數據量主要指的是LBSs對查詢結果返回的POI數量，因此對比不同方法返回給AS的POI數量。

圖3網絡通信開銷對比

如圖3所示，由于本文方法生成的k匿名區域是分散的，因此之間的距離更遠，對于每個位置都需要在搜索半徑之內進行POI的查找，搜索的結果會更多；而ELPP方法匿名位置點比較集中，因此有重復的查詢結果，能夠有相對較少查詢結果；OPEG方法的并不使用k匿名，而是對查詢結果直接加密來保護隱私信息，其網絡通信開銷小。

（3）匿名位置分散度

本文方法在構造k匿名的時候，考慮了匿名位置點的分散程度，分散度越高的位置集合具有更高的面積，所選出來的位置能夠分散在各個地方，而不是聚簇在一個范圍之內，從而能夠提高用戶的隱私保護程度，由于OPEG并沒有k匿名的過程，因此就匿名面積和ELPP進行比較。計算比值，SM和 SMELPP分別是本文方法和ELPP方法形成的匿名區域面積，β值越大，表示本文方法比ELPP匿名產生的位置更分散。

圖4位置分散度比值

如圖4所示，隨著k的值逐漸增大，β值逐漸增大，表明本文方法生成的匿名集合相比ELPP方法有更大的面積，本文方法匿名位置的分布相對ELPP更加分散，而不是聚簇在一個較小的區域內，當k的值為10的時候，本文方法比ELPP的匿名面積提高了11%，說明本文方法相對ELPP方法能夠產生更加分散的匿名位置集合。

4 結語

本文提出一種基于網格偏移的分散位置隱私保護方法。文獻[14]和文獻[16]為了防止用戶的隱私信息泄露給匿名服務器和位置服務器，需要較大的時間開銷，產生的匿名位置集合是集中的且容易匿名請求內容單一。本文所提方法根據周期更新的網格信息計算偏移網格區域，匿名服務器根據用戶查詢請求選擇分散的、請求內容多樣的網格坐標構成集合，使匿名服務器進行匿名處理和位置服務器進行匿名查詢的時候，難以得知用戶的隱私信息，并且有較低的時間開銷和分布更加分散的匿名位置集合。