基于網(wǎng)格和密度的匿名空間查找算法

施洪潔

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

【關(guān)鍵詞】位置服務(wù) 查詢隱私 k-匿名 網(wǎng)格和密度 最小匿名空間

【中圖分類號】TP309 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2016）11-0249-01

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

一、算法原理

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

二、剝離冗余邊緣

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

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

三、敏感度約束

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

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

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

四、總結(jié)

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

參考文獻(xiàn)：

[1]劉洋.位置服務(wù)：冬去春未來[J]. 環(huán)球財經(jīng)， 2011， 12（7）： 99-101.

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

[3]魏瓊，盧炎生.位置隱私保護(hù)技術(shù)研究進(jìn)展[J]. 計算機(jī)科學(xué)， 2008， 35（9）： 21-25.

[4]談嶸， 顧君忠， 林欣， 等. 基于用戶隱私保護(hù)的區(qū)域多對象聚集問題[J]. 計算機(jī)應(yīng)用， 2011.