基于網格和密度的匿名空間查找算法

施洪潔

【摘要】LBS匿名模型中的關鍵問題在于如何尋找滿足匿名條件的匿名空間，匿名空間越大，空間內用戶數越多，攻者能判斷出目標用戶的概率越小，即匿名度越好，但是同時，增大的匿名空間也增大了用戶位置精確度的損失，服務器返回的候選結果集與用戶的真實請求結果之間的差距越大，即服務質量就越差，反之，較小的匿名空間服務質量增強，而匿名度較弱。因此，匿名空間查找方法的原則是在匿名度和服務質量之間需找一個最佳的平衡點，本文首先指出了目前最典型的匿名空間查找算法過程中產生的大量的空間冗余現象是因為空間劃分精度太粗，而且沒有考慮用戶分布情況，因此，本文引入網格和密度的概念，提出了基于網格和密度的匿名空間查找算法。

【關鍵詞】位置服務 查詢隱私 k-匿名 網格和密度 最小匿名空間

【中圖分類號】TP309 【文獻標識碼】A 【文章編號】2095-3089（2016）11-0249-01

Interval Cloak產生的大量的空間冗余現象是由于空間劃分精度太粗和沒有考慮用戶分布情況，體現用戶分布不均勻的狀態就是密度的概念，而空間網格化是為了提高空間劃分的精度。本節將在地理信息系統中應用比較成熟的網格技術，對空間進行網格劃分，以網格為一個計算單元，再根據用戶分布密度，在用戶分布相對密度最大的范圍內尋找合適的匿名集。

一、算法原理

在地理信息系統中，網格數據模型被用來分析空間特征，由于其數據結構簡單，且成本低廉等優勢，在地理空間分析中得到了廣泛應用。網格數據模型中，空間被規則的劃分為網格，每個網格的位置由網格的行列號來表示，網格的值表示這個位置上物體的類型或狀態。本節提出的基于網格和密度的（GDB， Grid and Density？鄄Based）匿名空間查找算法基本思想是首先將整個空間映射為m×n網格，提高空間計算的精度，再利用空間用戶分布相對密度公式，計算用戶分布相對密度，在用戶分布密度最大的范圍內尋找滿足匿名條件的匿名集，根據密度概念，容易得知，同一k匿名要求下，用戶分布密度越大，匿名空間越小，正是利用這個原理，GDB在用戶分布密度最大的范圍內尋找滿足匿名條件的最小匿名空間。

二、剝離冗余邊緣

對于最小包含空間S2的空間冗余部分，本小節定義了用戶分布相對密度公式，根據此公式，計算各網格用戶分布相對密度，然后由遠及近用戶分布密度由小到大依次剝離其冗余邊緣，為避免用戶過于密集，匿名空間過小導致的位置隱私泄露，限定條件匿名空間的最小粒度為Smin。

根據用戶分布相對密度矩陣，以用戶u為中心，由遠及近依次刪除用戶分布相對密度最小的行或列，直到剝離某條邊緣后，得到的匿名空間不滿足匿名條件。

三、敏感度約束

為了滿足LBS（p， k）匿名條件，需在MASSA算法過程中加入p敏感約束，稱為p-MASSA算法，針對一般LBS（p， k）匿名提出的算法稱為p1-MASSA算法，針對增強的LBS（p， k）匿名提出的算法稱為p2-MASSA算法。

與空間用戶分布矩陣類似，對于用戶提交的敏感查詢和非敏感查詢，分別用1和0來表示，構建匿名區域內用戶查詢敏感度矩陣，矩陣每個坐標的值表示對應網格內敏感查詢的個數，為了簡化計算，將匿名集中敏感查詢所占比例不超過p的條件修改為匿名集中敏感查詢個數不超過floor（k×p），仍以上面的例子為例，假設查詢敏感度矩陣如矩陣Sid，若用戶敏感度要求為0.3，即空間內敏感查詢的個數不超過floor（4×0.3）=1，根據矩陣Sid可知陰影區域內敏感查詢個數為1，滿足匿名條件，則直接將該空間返回。

算法描述了基于增強的LBS（p， k）匿名空間查找算法。1行，Q集狀態初始化，4～8行，在匿名度條件、匿名空間最小粒度條件滿足的前提下，若敏感查詢個數大于floor（k×p），則根據用戶分布密度矩陣和敏感度矩陣依次刪除用戶分布密度最小，敏感度最大的網格內的查詢，9～12行，若While循環退出時敏感查詢個數不超過floor（k×p），則將此時Q內的所有查詢標記flag修改為true，表示該集合內的查詢滿足敏感度條件，查詢都能被處理，之后算法過程不需考慮查詢敏感性，與MASSA算法過程相同，找到合適的匿名空間并將其返回，13～15行，否則，表示匿名失敗，拒絕此次查詢請求。

四、總結

本文分析了目前最典型的匿名空間查找算法在查找過程中產生的大量的空間冗余現象，提出了基于網格和密度的最小k匿名空間查找算法，首先將空間劃分為m×n網格，其次，根據用戶所處網格鄰域空間內的用戶數對空間進行迭代分割，找到最小包含空間，然后根據用戶分布密度矩陣一次剝離用戶分布密度最小的邊，找到最小匿名空間。最后，在MASSA算法內加入了p敏感約束，并構建了查詢敏感度矩陣，根據第3章提出的一般LBS（p， k）匿名模型和增強的LBS（p， k）匿名模型，分別提出了p1-MASSA算法和p2-MASSA算法，p1-MASSA算法最小以空間邊緣為一個處理單位，p2-MASSA算法最小以一個網格為處理單位，先刪除敏感度最大的網格，在敏感度要求較高的情況下，提高了匿名成功的可能性。

參考文獻：

[1]劉洋.位置服務：冬去春未來[J]. 環球財經， 2011， 12（7）： 99-101.

[2]潘曉，肖珍，孟小峰.位置隱私研究綜述[J]. 計算機科學與探索， 2007， 1（3）： 268-281.

[3]魏瓊，盧炎生.位置隱私保護技術研究進展[J]. 計算機科學， 2008， 35（9）： 21-25.

[4]談嶸， 顧君忠， 林欣， 等. 基于用戶隱私保護的區域多對象聚集問題[J]. 計算機應用， 2011.