基于歷史查詢概率的K-匿名啞元位置選取算法

楊 洋，胡曉輝，杜永文

（蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 730070）

0 概述

隨著物聯(lián)網(wǎng)和移動(dòng)定位技術(shù)的發(fā)展，基于位置的服務(wù)（Location Based Service，LBS）被廣泛應(yīng)用于導(dǎo)航、查找附近的服務(wù)、接收基于位置的廣告等領(lǐng)域［1-2］。用戶使用基于位置的應(yīng)用向不可信的LBS服務(wù)器發(fā)送包含用戶的地理位置信息、興趣點(diǎn)等內(nèi)容的服務(wù)請求，LBS 服務(wù)器根據(jù)用戶發(fā)送的服務(wù)請求為用戶提供基于位置的服務(wù)［3］。用戶提供的位置越精確，獲得的服務(wù)質(zhì)量越高；位置越模糊，服務(wù)質(zhì)量越低［5］。如果不可信的服務(wù)提供商掌握用戶的真實(shí)位置信息，與用戶相關(guān)聯(lián)的個(gè)人信息會(huì)進(jìn)一步泄露，如家庭住址、社會(huì)關(guān)系等。

針對位置隱私保護(hù)中存在的問題，研究人員提出多種解決方案［6］，其中，最常用的位置隱私保護(hù)技術(shù)是基于歷史查詢概率的K-匿名技術(shù)［8-9］。K-匿名技術(shù)最早出現(xiàn)在數(shù)據(jù)庫領(lǐng)域，對于準(zhǔn)標(biāo)識(shí)符屬性，任意一條記錄無法與至少k-1 條記錄區(qū)分［11］。啞元位置是一種與用戶位置極相似的虛假查詢位置，普遍采用K-匿名集的方式。K-匿名集技術(shù)的原理是將用戶的真實(shí)位置與K-1 個(gè)啞元位置組合形成包含k個(gè)位置的匿名集［12］。用戶使用匿名集代替真實(shí)位置發(fā)起查詢，LBS 提供商響應(yīng)查詢并返回每個(gè)查詢位置需要的服務(wù)列表，用戶則根據(jù)其真實(shí)位置篩選查詢結(jié)果，獲取屬于自己的服務(wù)［14］。

啞元位置作為位置泛化的重要方法，具有部署簡單且不影響服務(wù)質(zhì)量的優(yōu)點(diǎn)［15］。現(xiàn)有的啞元選取方案都聚焦在如何能合理有效地選取啞元位置以防止攻擊者從匿名集中獲取用戶的真實(shí)位置［16］。攻擊者如果獲取了用戶位置相關(guān)的邊信息并過濾一些不合理啞元，例如位于湖泊、海洋、沙漠等特殊的地理位置的啞元，則能夠大幅增加攻擊者獲取用戶真實(shí)位置的概率，降低匿名集的隱私級別。針對此類問題，文獻(xiàn)［16］提出虛假位置選擇（Dummy Location Selection，DLS）算法，該算法通過將地圖上位置單元的歷史查詢概率作為一種邊信息劃分用戶的位置隱私等級，并使用位置熵選擇合適的啞元位置構(gòu)造K-匿名集。但是DLS 算法需要消耗大量的算力來選取具有最大熵值的匿名集，算法時(shí)間復(fù)雜度高，不適用于資源受限的物聯(lián)網(wǎng)設(shè)備，同時(shí)算法也未考慮啞元位置的離散度問題。文獻(xiàn)［17］通過分析DLS 算法存在的問題，設(shè)計(jì)了DLS 攻擊（Attack for Dummy Location Selection，ADLS）算法，并驗(yàn)證ADLS 攻擊算法的有效性，進(jìn)而提出一種新的啞元選取DLP 算法，該算法具有較好的隱私保護(hù)效果，卻忽略了歷史查詢概率為零的特殊位置情況。文獻(xiàn)［18］根據(jù)DLP 算法提出改進(jìn)的Enhanced-DLP 算法，引入增強(qiáng)型貪心算法，使其具有較高的匿名集生成效率和較強(qiáng)的隱私保護(hù)效果。文獻(xiàn)［19］提出基于虛擬網(wǎng)格的GridDummy 算法和基于虛擬圓的CircleDummy 算法。這兩種算法將K-匿名需要的K個(gè)位置全部用啞元位置代替，即提交的所有位置都不包含用戶的真實(shí)位置，雖然提高了攻擊者推測用戶真實(shí)位置的難度，但是降低了服務(wù)質(zhì)量，同時(shí)也未考慮到啞元匿名集的位置離散度問題，無法有效保證啞元位置在地理上均勻離散分布。

本文提出基于歷史查詢概率的K-匿名啞元位置選取算法，考慮用戶歷史查詢概率為零的特殊情況，在保證用戶位置信息不被泄露的同時(shí)，從地理分散度和零查詢用戶兩個(gè)維度增強(qiáng)匿名集的隱私性，從而提高位置隱私保護(hù)的安全性。

1 相關(guān)理論

1.1 基本概念

本節(jié)主要介紹文中使用的相關(guān)概念。

1）位置查詢概率

位置查詢概率（Location Query Probability，LQP）將地圖劃分成N×N的網(wǎng)格，每個(gè)網(wǎng)格代表一個(gè)位置，單元，對于網(wǎng)格地圖上的位置單元i均有一個(gè)對應(yīng)的歷史查詢次數(shù)ni，地圖上所有位置單元的查詢次數(shù)總和為，則i位置單元的歷史查詢概率如式（1）所示：

2）零查詢用戶

在網(wǎng)格化的地圖位置單元中，歷史查詢概率為零的位置稱為零查詢位置。在零查詢位置發(fā)起服務(wù)請求的用戶稱為零查詢用戶（Zero-Query Users，ZQU）。

3）用戶最大偏移距離

用戶u選取其位置附近的某個(gè)位置單元l′代替其真實(shí)位置l，l′稱為l的偏移位置。位置偏移會(huì)造成用戶服務(wù)質(zhì)量的損失，用戶服務(wù)質(zhì)量由偏移位置與用戶真實(shí)位置的數(shù)學(xué)期望表示。在用戶可接受的最大服務(wù)質(zhì)量損失時(shí)，用戶與偏移位置的歐氏距離為用戶最大位置偏移距離（User Maximum Offset Distance，UMOD），如式（2）、式（3）所示：

其中：pl為用戶真實(shí)位置的歷史查詢概率；f(l′/l)為在用戶位置l的情況下獲得偏移位置l′的概率，位置隱私的保護(hù)算法需要保證Qloss＜，因?yàn)槌^該值時(shí)，所得到的位置服務(wù)請求結(jié)果就無法滿足用戶最低服務(wù)質(zhì)量的要求。

1.2 LBS 架構(gòu)

LBS 架構(gòu)如圖1所示。

圖1 LBS 架構(gòu)Fig.1 Framework of LBS

LBS 架構(gòu)主要包括GPS 衛(wèi)星、具有定位功能和處理能力的終端、通信基站和位置服務(wù)提供商4 個(gè)部分。

1）GPS 衛(wèi)星為移動(dòng)終端提供當(dāng)前的地理位置信息，位置隱私保護(hù)算法認(rèn)為此過程是可靠的，默認(rèn)在位置獲取的過程中是安全的。

2）用戶通過具有定位功能和處理能力的終端對請求服務(wù)的位置進(jìn)行匿名保護(hù)，將用戶的真實(shí)位置隱藏在啞元匿名集中發(fā)送至通信基站。

3）通信基站將接收到的服務(wù)請求發(fā)送至相應(yīng)的LBS 提供商的服務(wù)器，通信基站只對用戶的服務(wù)請求進(jìn)行轉(zhuǎn)發(fā)，不對服務(wù)請求進(jìn)行修改。通信基站在收到服務(wù)器響應(yīng)后將其轉(zhuǎn)發(fā)至用戶終端，不對響應(yīng)信息進(jìn)行修改。但在通信過程中，相關(guān)的信息可能會(huì)被惡意攻擊者獲取，故本階段是不安全的。

4）服務(wù)位置服務(wù)器在收到用戶的服務(wù)請求后，解析請求內(nèi)容，產(chǎn)生匿名集所有位置的查詢結(jié)果，然后通過通信基站將結(jié)果返回給用戶。由于惡意的服務(wù)提供商可能會(huì)通過泄露用戶的隱私信息來獲取利益，攻擊者也可以通過攻擊服務(wù)器獲取用戶相關(guān)的隱私信息，故本階段也是不安全的。

1.3 隱私度量

隱私度量主要有基于歷史查詢概率K-匿名的隱私度量、基于信息熵的隱私度量、位置離散度。

1）基于歷史查詢概率K-匿名的隱私度量

根據(jù)啞元選取方案得到的啞元匿名集為C，C={l1，l2，…，lk-1，lk}，即|C|=k。攻擊者從 匿名集中獲取用戶的真實(shí)位置概率Q，如式（4）所示：

2）基于信息熵的隱私度量

位置查詢概率經(jīng)過地圖網(wǎng)格化處理以后，生成N×N個(gè)單元，從中選取包含用戶真實(shí)位置在內(nèi)的k個(gè)位置，根據(jù)位置單元的歷史查詢概率pi確定匿名集k中每個(gè)位置單元?dú)w一化后的查詢概率qi如式（5）所示，熵值如式（6）所示：

隱私度量使用信息熵來度量匿名集的隱私程度［19］。熵值越大，表示集合中元素的區(qū)分度越低，攻擊者從匿名集中識(shí)別用戶的真實(shí)位置概率就越小，匿名集的隱私級別就越高。匿名集中位置單元的歷史查詢概率越相似，熵值越大。當(dāng)歷史查詢概率相等時(shí)，熵值取得最大值。

3）位置離散度

啞元匿名集的位置離散度（PPD）通過計(jì)算匿名集中所有位置單元之間的距離來獲得，如式（7）所示：

PPD值越大，表示對于同一個(gè)位置數(shù)據(jù)集選取的啞元位置地理分布越離散，匿名集隱私效果越好；相反，啞元位置越聚集，越容易被攻擊者縮小隱私區(qū)域，啞元匿名集隱私保護(hù)效果越差。

1.4 啞元位置選取

啞元位置選取方法的主要目的是使匿名用戶選擇合適的啞元位置構(gòu)建K-匿名集，使得用戶真實(shí)位置和其他K-1 個(gè)啞元位置無法區(qū)分，將地圖網(wǎng)格化為5×5 的位置單元，根據(jù)每個(gè)網(wǎng)格的歷史查詢次數(shù)，計(jì)算各個(gè)位置單元的查詢概率，用不同灰度代表位置單元查詢概率的大小，顏色越深，歷史查詢概率越大，顏色越淺，歷史查詢概率越低，白色代表該位置單元的歷史查詢概率為零。

1.4.1 未充分考慮特殊查詢概率位置單元

啞元K-匿名集經(jīng)過地圖網(wǎng)格化處理后存在零查詢的位置單元。如果直接對零查詢用戶的位置單元進(jìn)行啞元選取，則可能會(huì)生成含有多個(gè)零查詢位置單元的匿名集。零查詢位置單元在地理語義上可能是一些無人區(qū)、河流、沙漠等特殊位置。如果啞元匿名集含有這些特殊位置，則攻擊者結(jié)合地理信息分析過濾這些特殊位置單元，從而降低啞元K-匿名集的規(guī)模。

5-匿名啞元位置選擇如圖2 所示，從圖2 可以看出，右側(cè)的數(shù)值代表對應(yīng)位置的歷史查詢概率，位于新開發(fā)區(qū)的用戶u1通過熵度量的算法取得匿名度K=5 的最佳隱私保護(hù)效果，需要選擇4 個(gè)與其能形成最大熵值的位置單元{u2，u3，u4，u5}。獲取該匿名集的攻擊者通過分析相關(guān)位置信息可過濾{u3，u4，u5}，用戶的隱私泄露概率由1/5 增加到1/2，增加了隱私泄露的風(fēng)險(xiǎn)。

圖2 5-匿名啞元位置選擇Fig.2 Location selection of five-anonymous dummy

1.4.2 未充分考慮啞元位置離散度

由于一些基于歷史查詢概率進(jìn)行啞元選取的算法沒有考慮位置單元的地理分布情況。對于一個(gè)給定k匿名規(guī)模的啞元匿名集，構(gòu)造啞元匿名集的位置離散度應(yīng)該盡可能大。

3-匿名啞元位置選擇如圖3 所示。右側(cè)數(shù)值代表對應(yīng)位置的歷史查詢概率，位于新開發(fā)區(qū)的用戶u1通過熵度量的算法取得匿名度K=3的最佳隱私保護(hù)效果，從與用戶具有相同歷史查詢概率的{u2，u3，u4，u5，u6}中隨機(jī)選擇2 個(gè)位置單元，即pu1=pu2=pu3，構(gòu)造位置匿名集C1={u1，u2，u3}。在地理上用戶{u1，u2，u3}不是均勻離散分布，攻擊者可以將匿名集劃分成不同部分進(jìn)行攻擊，最壞的情況是攻擊者第一次攻擊就選擇了用戶所在的部分，識(shí)別用戶的概率則由1/3 增加到1/2，增加了隱私泄露的風(fēng)險(xiǎn)。

圖3 3-匿名啞元位置選擇Fig.3 Location selection of three-anonymous dummy

如果構(gòu)造的匿名集過于聚集，且位于某個(gè)特定的區(qū)域，攻擊者可以通過地圖信息獲取與用戶相關(guān)的隱私信息。同一區(qū)域啞元位置如圖4 所示，右側(cè)數(shù)值代表對應(yīng)位置的歷史查詢概率，根據(jù)3 個(gè)位置都處在大學(xué)可以推測出用戶的身份信息和相關(guān)學(xué)校，進(jìn)一步推測更多的隱私信息。

圖4 同一區(qū)域啞元位置選擇Fig.4 Dummy location selection in the same region

因此，單一考慮位置單元的歷史查詢概率通過熵度量的方式構(gòu)造啞元匿名集，無法抵御攻擊者針對零查詢用戶的特殊地理信息攻擊，同時(shí)無法避免由于匿名集中的位置分布不均造成離散的啞元位置易被過濾的問題。為了保證匿名度K，本文在基于熵度量的啞元選取原則上，加入了對零查詢概率以及位置離散度兩個(gè)方面的考量，設(shè)計(jì)一種改進(jìn)算法。

2 攻防模型

位置隱私保護(hù)算法的設(shè)計(jì)也需要加入對常用攻擊模型的考量，基于相應(yīng)的攻擊方式設(shè)計(jì)保護(hù)算法的防御思路。

2.1 攻擊方式

攻擊方式主要有邊信息攻擊和位置同質(zhì)攻擊。

1）邊信息攻擊

在位置隱私領(lǐng)域，邊信息與真實(shí)位置不直接相關(guān)聯(lián)，但是攻擊者能利用它們篩選出更有價(jià)值的位置服務(wù)數(shù)據(jù)，達(dá)到輔助攻擊的效果［21］。邊信息攻擊［22］是指攻擊者根據(jù)已知邊信息篩除一些不合理位置，增加獲取用戶真實(shí)位置信息的概率。假設(shè)位置匿名度為K，當(dāng)選擇的K-1 個(gè)啞元位置中有多個(gè)啞元位置被攻擊者過濾，則不滿足K-匿名要求，降低隱私保護(hù)水平。

2）位置同質(zhì)攻擊

位置同質(zhì)攻擊［22］是指攻擊者通過分析匿名集中的多個(gè)位置信息來縮小匿名區(qū)域。如果位置間非常接近，即使可以達(dá)到K匿名度，但是隱匿區(qū)域太小，攻擊者就能獲取相關(guān)的隱私信息；其次攻擊者可以通過位置聚類的方法進(jìn)行分類推理來增加推測用戶真實(shí)位置的概率。

2.2 位置概率模型

對于含攻擊者的位置隱私保護(hù)模型，隱私源為網(wǎng)格化地圖的概率分布l，隨機(jī)變量l的取值表示用戶u的真實(shí)位置是網(wǎng)格化地圖中某個(gè)啞元位置li，{l1，l2，…，lm}表示網(wǎng)格化的地圖位置集。假設(shè)每個(gè)啞元位置對應(yīng)的概率為pi，則l概率模型如式（8）所示：

用戶的真實(shí)位置分布信息是隱私信息，為了防止攻擊者直接獲取用戶的真實(shí)位置信息，需要對用戶的位置進(jìn)行匿名處理，將用戶的位置泛化成可被攻擊者直接觀察到的位置分布l′，則l′的概率模型如式（9）所示：

攻擊者獲得用戶的可觀察位置分布l'后，結(jié)合相關(guān)的邊信息對用戶u進(jìn)行位置攻擊，攻擊者得到用戶的推斷位置分布表示攻擊者推測的位置為用戶真實(shí)位置的概率，^對應(yīng)的概率模型如式（10）所示：

具有邊信息攻擊者的攻防模型結(jié)構(gòu)如圖5 所示。

圖5 攻防模型結(jié)構(gòu)Fig.5 Structure of attack and defense model

3 本文算法設(shè)計(jì)

本文算法將位置隱私保護(hù)的用戶分為兩種類型：1）用戶發(fā)起位置服務(wù)請求所在位置單元的歷史查詢概率為零的零查詢用戶，零查詢用戶在進(jìn)行啞元位置匿名集構(gòu)造之間，根據(jù)偏移算法進(jìn)行位置偏移，選擇合適的偏移位置；2）用戶發(fā)起位置服務(wù)請求所在位置單元的歷史查詢概率不為零，通過此位置單元的歷史查詢概率構(gòu)造匿名集，無論是零查詢用戶還是非零查詢用戶，最后的匿名集要保證啞元位置地理上盡可能的均勻離散分布，構(gòu)造啞元匿名集形成匿名區(qū)域要盡可能大。

3.1 最優(yōu)啞元匿名候選集算法

啞元選取算法的目標(biāo)是保護(hù)用戶的位置信息不被泄露。攻擊者通過重構(gòu)匿名集與用戶匿名集最相似的位置單元作為用戶的真實(shí)位置，從而獲取用戶隱私信息。

最優(yōu)的啞元匿名候選集算法是基于熵度量考慮攻擊者可能掌握邊信息的情況下，根據(jù)輸入網(wǎng)格化的數(shù)據(jù)集S，用戶的真實(shí)位置l，以及隱私匿名度K，利用增強(qiáng)型貪心算法高效地選取啞元位置，最后構(gòu)造具有最大熵值啞元匿名集。

算法1最優(yōu)啞元匿名候選集算法

最優(yōu)啞元匿名候選集Ch。

3.2 零查詢用戶位置偏移算法

零查詢用戶位置偏移算法主要針對零查詢用戶發(fā)起服務(wù)請求時(shí)，根據(jù)用戶給定的位置偏移距離DDis(l，l′)，選擇合適的偏移位置l′代替用戶的真實(shí)位置l。用戶在進(jìn)行請求時(shí)，通過最大服務(wù)質(zhì)量損失，給定算法最大的位置偏移距離DDis(l，l′)。首 先算法根據(jù)用戶給定的最大位置偏移距離，構(gòu)造符合條件的偏移位置候選區(qū)C′；其次通過候選區(qū)構(gòu)造候選偏移位置集，篩除候選集中歷史查詢概率為零的位置；最后隨機(jī)在候選集中選擇一個(gè)位置l'作為用戶的替代位置，增加偏移位置的隨機(jī)性。

算法2零查詢用戶位置偏移算法

3.3 K-匿名啞元位置選取算法

算法1 構(gòu)造的匿名集雖具有最大的熵值，但其啞元位置的地理離散度沒有得到保障。攻擊者即使沒有獲取用戶的真實(shí)位置，也能根據(jù)該區(qū)域相關(guān)信息推測用戶的隱私信息。除此之外，啞元位置的選取在地理上如果出現(xiàn)明顯的分類，也不利于隱私保護(hù)。

離散度最大啞元匿名集構(gòu)造算法的目的是盡可能選取距離較遠(yuǎn)的位置單元，保證啞元匿名集的位置離散度盡可能高。在選取啞元位置的過程中，計(jì)算兩個(gè)位置之間的距離實(shí)現(xiàn)位置離散分布和，但這種方法在某些情況下無法獲得最優(yōu)的離散度。離散啞元位置選取示意圖如圖6 所示。

圖6 離散啞元位置選取示意圖Fig.6 Schematic diagram of discrete dummy location selection

用戶的位置為點(diǎn)B，當(dāng)已經(jīng)選擇A作為啞元位置以后，選擇C點(diǎn)和D點(diǎn)與A點(diǎn)、B點(diǎn)構(gòu)成的啞元匿名集的熵值相同，如式（11）所示：

啞元位置的選取考慮到地理分布對于隱私的影響，選擇D點(diǎn)優(yōu)于選擇C點(diǎn)加入啞元匿名集，如式（12）所示：

所以相對于選擇兩個(gè)位置的距離和，本文算法選擇距離積作為構(gòu)造匿名集的啞元選取方法。

本文構(gòu)造離散度最大啞元匿名集Clist={l1，l2，…，lk}，描述為一個(gè)多目標(biāo)優(yōu)化問題，如式（13）所示：

其中：Pi、Pj分別為li、lj對應(yīng)的歷史查詢概率。由于啞元位置的選取同時(shí)滿足上述兩個(gè)目標(biāo)非常困難，本文將上述問題分解成兩個(gè)部分，首先根據(jù)熵度量構(gòu)造具有最大熵值的最優(yōu)的2K啞元匿名候選集Ch，如式（14）所示：

基于熵度量構(gòu)造具有最大熵值的最優(yōu)的2K啞元匿名候選集Ch，通過位置距離乘積選擇K個(gè)最離散的啞元位置匿名集Clist，如式（15）所示：

基于以上分析，本文首先根據(jù)用戶的真實(shí)位置，綜合使用算法1 和算法2。通過算法1 判斷是否進(jìn)行位置偏移，然后通過算法2 選擇2K個(gè)具有最大熵值的匿名候選集，最后選擇K個(gè)具有最大離散度的啞元匿名集，從而構(gòu)建基于歷史查詢概率的啞元選取算法。

本文進(jìn)行K個(gè)最大離散度啞元匿名集的構(gòu)造時(shí)，首先將用戶的真實(shí)位置或者偏移位置加入匿名集Clist，然后通過輪選擇K-1 個(gè)啞元位置加入匿名集Clist。

針對每一輪，本文對于候選集Ch中所有的位置單元都要計(jì)算其到Clist所有位置的乘積，然后計(jì)算每個(gè)位置單元占候選集Ch中所有的位置單元到Clist所有位置乘積之和的比率，最后構(gòu)造候選集對應(yīng)的候選概率矩陣，根據(jù)概率矩陣中的概率選擇一個(gè)啞元位置加入匿名集。

本文每選擇一個(gè)啞元位置都要對應(yīng)計(jì)算一個(gè)概率矩陣，經(jīng)過K-1 輪形成包含K個(gè)用戶的匿名集。在第一輪時(shí)，概率矩陣是通過候選集所有位置到用戶位置的距離計(jì)算形成，其他輪則都是通過計(jì)算距離乘積。

算法3基于歷史查詢概率的K-匿名啞元選取算法

4 安全性分析

假設(shè)匿名集Clist中的匿名度為K，因此攻擊者從匿名集中推測出用戶偏移位置的概率為pex=1/K。設(shè)用戶歷史查詢概率分布中的位置總數(shù)為n，攻擊者通過偏移位置確定用戶真實(shí)位置是可能發(fā)生的事件，但存在小概率函數(shù)o(n)使得攻擊者確定用戶的真實(shí)位置的概率為preal，滿足preal≤o(n)。攻擊者在獲取用戶的匿名集合Clist的情況下獲得確切的用戶位置信息的概率p=pexpreal≤o(n)×(1/K)。

攻擊者根據(jù)已獲得的地圖信息和歷史查詢概率數(shù)據(jù)來推測啞元匿名集中用戶的真實(shí)位置信息，本文算法能夠有效應(yīng)對此類進(jìn)行攻擊。在進(jìn)行啞元位置的選取過程中，本文算法每次都選擇與用戶真實(shí)位置歷史查詢概率最相似或相等的位置單元作為啞元，即滿足pi≈pj（其中i表示用戶，j表示啞元，pi表示用戶的歷史查詢概率，pj表示匿名集中任一啞元的歷史查詢概率），根據(jù)式（6）可知，啞元位置的歷史查詢概率越接近，熵值越大，匿名集的信息混亂程度越高。本文算法在選擇啞元時(shí)，將考慮熵值和地理離散度較高的位置選為啞元位置。因此，本文算法生成的啞元匿名集能抵抗攻擊者基于歷史查詢概率的位置同質(zhì)攻擊和邊信息攻擊，有效控制攻擊者推測出用戶真實(shí)位置的概率約為1/K。

5 仿真實(shí)驗(yàn)

為驗(yàn)證本文算法的有效性，本文設(shè)計(jì)一系列仿真實(shí)驗(yàn)。實(shí)驗(yàn)采用Python3.8 軟件在PC 機(jī)（Windows10 操作系統(tǒng)，2.40 GHz Intel i7 CPU，12 GB 內(nèi)存）上進(jìn)行模擬仿真。數(shù)據(jù)集為北美路網(wǎng)NA 數(shù)據(jù)集，該數(shù)據(jù)集包含175 812個(gè)真實(shí)的位置記錄，NA數(shù)據(jù)集分布如圖7所示。實(shí)驗(yàn)將數(shù)據(jù)集網(wǎng)格化為100×100 的網(wǎng)格地圖，用戶的最大偏移距離均設(shè)置為2。

圖7 NA 數(shù)據(jù)集分布Fig.7 Distribution of NA data set

5.1 離散度對比

離散度越大，啞元位置越分散。實(shí)驗(yàn)通過統(tǒng)計(jì)不同隱私度K下啞元匿名集位置單元的距離總和來衡量啞元匿名集的離散度。本文K-匿名啞元選取算法K-DLS、DLS算法、DLP算法、Enhanced_DLP 算法、Optimal 算法、CircleDummy 算法、GridDummy 算法在不同隱私度K下啞元匿名集的離散度對比如圖8 所示。

圖8 不同算法的匿名集離散度對比Fig.8 Anonymity set dispersion comparison among different algorithms

從圖8 可以看出，所有算法生成啞元匿名集的離散度都呈現(xiàn)上升趨勢，在相同隱私度K下K-DLS算法構(gòu)造的啞元匿名集離散度大于其他兩種算法。隨著K值增大，本文算法的匿名集離散度均高于其他算法。因?yàn)楸疚乃惴ㄔ谶x擇啞元位置時(shí)，引入侯選位置集與啞元位置集所有位置元素距離乘積作為指標(biāo)，通過位置概率候選矩陣選擇啞元位置，每次都選擇了能構(gòu)成最大離散度的位置作為啞元，保障生成的啞元匿名集具有最大的離散度。

5.2 啞元匿名集生成效率對比

啞元匿名集的生成效率是通過CPU 的運(yùn)行時(shí)間表示。為驗(yàn)證本文算法的啞元匿名集生成效率，K-DLS、DLP 和Enhanced_DLP 算法在不同隱私度K下生成時(shí)間對比如圖9 所示。

圖9 隱私度K 與匿名集生成時(shí)間Fig.9 Privacy K and generation time of anonymity set

從圖9 可以看出，本文算法在構(gòu)造啞元匿名集時(shí)，需要驗(yàn)證用戶的歷史查詢概率，同時(shí)進(jìn)行離散選擇，故其運(yùn)行時(shí)間比DLP 和Enhanced_DLP 算法的運(yùn)行時(shí)間略高。本文算法在保證取得最大熵值的情況下，考慮了啞元位置的地理離散性，啞元匿名集的生成效果整體較好。

5.3 隱私保護(hù)熵值對比

在LBS 的位置隱私保護(hù)方案中，位置熵可以衡量用戶位置信息的不確定性，熵值越大表示啞元匿名集的隱私度越高。圖10 表示本文K-匿名啞元選取算法K-DLS、DLS算法、DLP算法、enhanced_DLP算法、Optimal 算法、CircleDummy 算法、GridDummy 算法在不同隱私度K下生成啞元匿名集的熵值對比。

圖10 不同隱私度K 對匿名集熵值影響Fig.10 The entropy of anonymity set versus different privacy K

從圖10 可以看出，隨著K值不斷增大，7 種算法生成啞元匿名集的熵值整體呈現(xiàn)上升趨勢。但是DLS、DLP、Enhanced_DLP、Optimal 和K-DLS 算法生成的熵值明顯大于CircleDummy、GridDummy 算法。K-DLS算法在保證啞元匿名集離散度最大的情況下，匿名集熵值也取得了最優(yōu)的效果，能夠有效保證用戶的隱私。

5.4 攻擊算法識(shí)別概率對比

攻擊者獲得用戶的啞元匿名集C后，結(jié)合相關(guān)的邊信息對用戶進(jìn)行位置攻擊，攻擊者得到用戶的推斷位置分布，根據(jù)分布概率確定用戶的真實(shí)位置。K-DLS、DLS、DLP 和Enhanced_DLP 算法在不同隱私度K下生成啞元匿名集的位置識(shí)別率對比如圖11 所示，其中每個(gè)算法重復(fù)實(shí)驗(yàn)1 000 次。

圖11 不同隱私度K 對位置識(shí)別率的影響Fig.11 Location recognition probability versus different privacy K

從圖11 可以看出，K-DLS 算法的位置識(shí)別率略低于其他算法，因?yàn)橛脩粼谶M(jìn)行位置隱私保護(hù)時(shí)，考察了歷史查詢概率為零的用戶，對其進(jìn)行位置偏移，隨機(jī)在候選集中選擇用戶位置的偏移位置，增加匿名集的隨機(jī)性；其次算法考量了位置離散度，生成啞元匿名集在地圖上盡可能的均勻離散分布，攻擊者很難通過位置聚類等特殊方法增加推測概率，能夠有效提升用戶位置的隱私保護(hù)效果。

6 結(jié)束語

本文分析現(xiàn)有位置隱私保護(hù)算法存在的不足，提出基于歷史查詢概率的K-匿名啞元位置選取算法。利用熵度量選擇啞元位置，使得啞元匿名集熵值最大，并根據(jù)距離對匿名結(jié)果進(jìn)行優(yōu)化。仿真結(jié)果表明，與DLP、DLS 等算法相比，K-DLS 算法在保證匿名集離散度最大的情況下，匿名集熵值為最優(yōu)，能夠提高位置隱私保護(hù)的安全性。本文算法主要針對基于快照查詢的LBS 服務(wù)位置隱私保護(hù)，下一步將對用戶連續(xù)查詢移動(dòng)軌跡的位置隱私保護(hù)進(jìn)行研究。