張 琳，張鴻剛，劉茜萍

1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023

2.南京郵電大學(xué)江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023

隨著智能手機(jī)，平板電腦和其他物聯(lián)網(wǎng)（Internet of Things，IoT）設(shè)備的激增，基于位置的服務(wù)（Location?Based Services，LBS） 已變得越來越流行，并開始改變使用互聯(lián)網(wǎng)的方式，在社會生活中發(fā)揮著極其重要的作用。

然而，LBS為用戶提供便利的同時也帶來了隱私泄露的風(fēng)險(xiǎn)，用戶獲取LBS服務(wù)后，需要提交位置信息。通過收集用戶的位置信息，攻擊者可以用獲取到的用戶位置數(shù)據(jù)來跟蹤用戶的移動，或者進(jìn)一步推知出用戶的工作場所、家庭住址、社會關(guān)系、身體狀況和愛好等私人信息，將其賣給第三方以獲取經(jīng)濟(jì)利益［1］。

因此，用戶在使用LBS時必須保護(hù)其位置隱私。近年來，世界各地的研究人員已經(jīng)提出了許多解決位置隱私保護(hù)問題的技術(shù)，例如位置擾動和混淆［2－3］、區(qū)域匿名［4－6］和假位置［7］。 較為常用的區(qū)域匿名技術(shù)將一塊包含k個用戶的匿名區(qū)域發(fā)送給LBS服務(wù)器，使得識別真實(shí)用戶的概率降低到1/k，然而，這種方法過于依賴可信第三方（Trusted Third Party，TTP），容易造成單點(diǎn)故障，而且大量查詢信息也會造成性能瓶頸。而假位置技術(shù)則沒有這些限制和問題，該技術(shù)依賴客戶端生成額外的假位置來隱匿用戶真實(shí)位置，實(shí)現(xiàn)了位置匿名，因此很好地彌補(bǔ)了空間匿名技術(shù)的各種不足。而現(xiàn)有研究中基于假位置的隱私保護(hù)技術(shù)在選擇假位置時，或者沒有充分考慮到背景知識等輔助信息，或者只能工作在特定的環(huán)境下，不具備一般通用性，用戶的位置隱私也因此很難得到預(yù)期的隱私保護(hù)效果。

本文充分考慮訪問概率、位置語義等地理位置的信息特征，提出了一種基于多元數(shù)據(jù)的假位置選擇 （Multidata?based Dummy Location Selection，MDLS）算法。該方案首先基于大頂堆初步篩選出與用戶真實(shí)位置相似的位置，構(gòu)成假位置候選集，然后根據(jù)候選位置與用戶真實(shí)位置語義信息的Jaro?Winkler相似度篩除掉語義相似的位置，最后綜合考慮候選位置與真實(shí)位置的物理距離以及語義距離選擇假位置。在保證提交的假位置間物理距離盡量分散，以及用戶實(shí)際位置訪問概率相似的同時，還要保證提交的假位置集合盡量分散且位置語義信息盡量豐富。本文使用真實(shí)軌跡數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，從生成時間、位置熵、物理距離、語義相似度以及識別率5個方面評估了提出的假位置生成方案，并將其與已有的其他算法相比較，結(jié)果表明，提出的算法能夠快速有效地生成物理分散且語義多樣的假位置集合。

1 相關(guān)工作

為了解決基于位置服務(wù)的隱私問題，國內(nèi)外學(xué)者在先前的工作中已經(jīng)提出了數(shù)種不同的方法。現(xiàn)有的大多數(shù)研究都關(guān)注于通過位置擾動和混淆［8－10］的方法來保護(hù)用戶的位置隱私，這些方法通常采用諸如k?匿名［11］之類的隱私度量。 Gruteser 等［12］首次將k?匿名這一概念引入了位置隱私領(lǐng)域并提出了一種自適應(yīng)隱匿算法，該算法可以將用戶位置隱匿于至少包含k個用戶的區(qū)域中，使攻擊者難以從至少包含k個用戶的隱藏區(qū)域中識別出真實(shí)的用戶位置。Bamba等［13］提出了一種網(wǎng)格劃分方法，該方法提供了兩種算法：自上而下的網(wǎng)格隱藏算法和自下而上的網(wǎng)格算法，可以根據(jù)用戶的需要進(jìn)行選擇。Xu等［14］證明了k?匿名區(qū)域的大小對查詢結(jié)果的一致性有很大影響，為匿名區(qū)域劃分的研究提供了指導(dǎo)。在此基礎(chǔ)上，文獻(xiàn)［15－18］提出了多種幾何形狀的匿名區(qū)域構(gòu)造方法。但是，這些方法過于依賴TTP［19－20］，容易造成單點(diǎn)故障，而且大量查詢信息也會造成性能瓶頸。

文獻(xiàn)［10］和文獻(xiàn)［21］中提出的解決方案通過在對等（P2P）用戶網(wǎng)絡(luò)中傳輸信息來避免通過TTP隱藏位置。然而，移動設(shè)備交換信息所需的額外資源花銷使得該方案難以實(shí)施。為了解決這個問題，Kido等［22］提出在一組虛擬位置中隱藏用戶位置的方法。Lu等［23］提出類似的方法，該方法在覆蓋用戶位置的虛擬圓或網(wǎng)格內(nèi)生成k－1個虛擬位置，同時考慮隱藏區(qū)域的面積。Niu等［24］通過位置熵度量假位置集的不確定性，通過最大化位置熵實(shí)現(xiàn)了假位置集的構(gòu)建。Sun等［25］針對統(tǒng)計(jì)攻擊，根據(jù)隱私需求將地圖區(qū)域分為不同的保護(hù)要求等級，通過概率估計(jì)選擇虛擬位置，可以防止攻擊者通過分析歷史記錄判斷真實(shí)位置信息。夏興有等［26］基于半可信第三方服務(wù)的隱私保護(hù)系統(tǒng)結(jié)構(gòu)，提出了一種根據(jù)用戶歷史查詢概率分布選擇假位置的匿名算法，并基于Stackelberg博弈對匿名結(jié)果進(jìn)行優(yōu)化。然而以上方案都沒有考慮到用戶位置的語義信息，不能保證構(gòu)造假位置集的語義多樣性。王潔等［27］在構(gòu)造假位置集時則綜合考慮了假位置的語義信息、查詢概率以及地理位置，但是該方案需要提前構(gòu)造好地區(qū)的位置語義樹，而且只適用于POI類型較多的地區(qū)，實(shí)現(xiàn)匿名的條件較為苛刻，也很難達(dá)到預(yù)期的隱私保護(hù)效果。

本文將在這些文獻(xiàn)的基礎(chǔ)上進(jìn)行改進(jìn)和完善，提出的算法在充分考慮用戶位置背景知識的同時，還可以適用于不同的環(huán)境，有效抵御基于位置語義等信息的背景知識攻擊，保護(hù)用戶的位置隱私。

2 預(yù)備知識

2.1 系統(tǒng)架構(gòu)

首先，用戶使用移動設(shè)備或本地網(wǎng)絡(luò)基礎(chǔ)結(jié)構(gòu)來確定他們的位置，用戶的位置信息使用二維坐標(biāo)（x，y）表示，即用戶的緯度和經(jīng)度。LBS請求由位置信息（x，y）提交請求的日期和時間以及請求內(nèi)容的查詢內(nèi)容組成。用戶將這些信息發(fā)送到LBS服務(wù)器，最終收到適當(dāng)?shù)幕谖恢玫捻憫?yīng)，完整的過程如圖1所示。

圖1 系統(tǒng)架構(gòu)

基于位置的服務(wù)可以通過在LBS請求中使用的通信機(jī)制直接向用戶分發(fā)歷史查詢概率等背景信息。由于歷史查詢概率之類的背景信息不會隨著時間變化太多，傳播之間的間隔可能會很長，因此開銷不會很大。在文獻(xiàn)［24］的另一種方法中，用戶能夠通過WiFi接入點(diǎn)（Access Point，AP）彼此共享各自的信息。AP收集他們通信范圍內(nèi)的歷史查詢概率，然后用戶可以下載這些信息并與他們連接的其他接入點(diǎn)共享。本文采用后一種方法，通過AP共享AP覆蓋范圍內(nèi)位置的歷史查詢概率以及語義信息。

2.2 攻擊模型

攻擊者的目標(biāo)是獲取有關(guān)特定用戶的敏感信息，按照攻擊的類型可將其分為被動攻擊者和主動攻擊者。被動攻擊者可以通過監(jiān)視和竊聽用戶之間的無線渠道，獲取用戶的敏感信息。主動攻擊者可能會破壞LBS服務(wù)器并獲取該服務(wù)器存儲的所有信息，這些信息包括用戶發(fā)送的當(dāng)前查詢假位置集以及該用戶的歷史查詢數(shù)據(jù)。攻擊者根據(jù)獲取的用戶發(fā)送的假位置集，并結(jié)合有關(guān)背景知識，可以嘗試推斷有關(guān)用戶的其他敏感信息。常見的背景知識攻擊方式包括同源攻擊、概率分布攻擊和位置相似性攻擊，這些攻擊通過分析用戶歷史請求數(shù)據(jù)、查詢概率分布以及語義信息，不難推斷出用戶的真實(shí)位置。

2.3 篩選準(zhǔn)則

令Rlocal＝｛n×n，Slocal｝表示實(shí)驗(yàn)中所選取的矩形區(qū)域，該區(qū)域由n×n個大小相同的網(wǎng)格組成，Slocal表示該區(qū)域的所有位置點(diǎn)集合。lreal表示用戶當(dāng)前所處真實(shí)位置，dque表示與真實(shí)位置歷史查詢概率之差，dphy表示兩位置之間的物理距離，即歐式距離，dsem表示兩位置之間的語義距離，本文中則是由兩位置之間的Jaro?Winkler相似度計(jì)算得出。

定義 2Jaro?Winkler相似度［28］是一種度量兩個字符串序列之間編輯距離的指標(biāo)。給定字符串s1和s2之間的Jaro相似度simj定義為

Jaro?Winkler相似性進(jìn)一步考慮了字符串的公共前綴長度對字符串語義的影響，給定字符串s1和s2之間的 Jaro?Winkler相似度 simw， 定義為

式中，simj為字符串s1和s2之間的Jaro相似度；l為字符串公共前綴長度，最大值為4；p為一個常量因子，不超過0.25，默認(rèn)為0.1。

2.4 評估指標(biāo)

定義3 熵H表示系統(tǒng)內(nèi)部的混亂和不確定程度，可以用來度量包含k個位置的假位置集Sdummy的不確定性，其定義為

定義4匿名區(qū)域面積D表示假位置集中k個位置點(diǎn)中最外層點(diǎn)圍成的凸包（凸多邊形）面積。凸包的面積可以根據(jù)鞋帶公式［29］求出，表示為

式中，c表示假位置集Sdummy中最外層位置點(diǎn)的個數(shù)。假位置集凸包面積示意圖見圖2。

圖2 假位置集凸包面積

定義5θ－安全值是用來度量生成假位置集語義差異性的一個指標(biāo)。其定義為

3 MDLS算法

本文提出了一種基于多元數(shù)據(jù)的假位置選擇（MDLS）算法，該算法根據(jù)位置查詢概率、位置語義等地理位置的信息特征篩選出與用戶真實(shí)位置查詢概率相近且物理與語義距離較遠(yuǎn)的位置。MDLS算法采用了邊篩選邊判斷的策略，首先基于大頂堆選擇查詢與用戶真實(shí)位置查詢概率接近的位置構(gòu)成假位置候選集，然后分別考慮候選位置與真實(shí)位置的物理距離以及語義距離篩選假位置，最后生成一個包含用戶真實(shí)位置且大小為k的假位置集Sdummy。算法1給出了MDLS算法的偽代碼表示。

算法1MDLS算法

該算法除需要輸入選取區(qū)域地理信息和用戶所處位置外，還需要提前定義好隱私需求相關(guān)的參數(shù)匿名度k以及比例系數(shù)r。 匿名度k表示生成結(jié)果集Sdummy的大小，k越大，攻擊者越難從結(jié)果集Sdummy中確定用戶的真實(shí)位置，隱私保護(hù)效果也越好；比例系數(shù)r用來調(diào)整綜合距離中語義距離的占比，r越大，語義距離在選擇假位置時越重要。

1～15步構(gòu)建了一個大頂堆Sc，篩選出與用戶真實(shí)位置查詢概率差距最小的4k個位置，作為候選集。首先，2～8步依次將位置集合Slocal的前4k個位置加入候選集Sc，添加完后從最底層的雙親節(jié)點(diǎn)開始根據(jù)每個位置的dque自上而下地進(jìn)行堆調(diào)整，直到根節(jié)點(diǎn)結(jié)束，至此，初始大頂堆就構(gòu)建完成了。10～13步將小于堆頂位置dque的待添加位置與堆頂位置進(jìn)行替換，并從根節(jié)點(diǎn)開始自上而下地堆調(diào)整。

17～34步綜合考慮候選位置之間的物理距離和語義距離，記錄并篩選出分散且多樣的假位置。最后返回結(jié)果集Sdummy。 18～25步分別算出lcandi與用戶所處位置lreal，最近添加位置llast以及隨機(jī)候選位置lrand之間的物理距離dphy，語義距離dsem以及綜合距離并使用dsmin，dmin記錄dsem和d的最小值。

26～32步分別使用lbest和lworst表示最佳候選位置以及最差候選位置，lworst是上文記錄的最小語義距離dsmin對應(yīng)的位置，該位置與假位置集中用戶真實(shí)位置以及其他位置的語義距離最近，容易被攻擊者獲知位置語義信息，需要從候選集中刪除；lbest則是上文記錄的最小綜合距離dmin對應(yīng)的位置，該位置與假位置集中用戶真實(shí)位置以及其他位置的綜合距離最遠(yuǎn)，將其加入假位置集Sdummy中，能使集合中的位置最為分散且多樣。經(jīng)過k輪篩選后，返回假位置集Sdummy。

其中，兩個位置之間的語義距離dsem可以用位置之間的 Jaro?Winkler距離來計(jì)算和表示。由于Jaro?Winkler距離既考慮了一定范圍內(nèi)的匹配字符個數(shù)，又考慮了字符串的公共前綴長度對字符串語義的影響，能夠僅從地名較為準(zhǔn)確地度量不同位置的語義距離，同時又避免了在POI較少的環(huán)境下匿名失敗的可能。位置語義距離范圍為［0，1］，其偽代碼如算法2所示。

算法2getJWDistance算法

由式（1，2）可知，決定兩字符串語義距離大小的是匹配窗口內(nèi)的匹配字符數(shù)matches、匹配字符換位數(shù)transposition以及匹配前綴長度prefix，對3個變量的計(jì)數(shù)操作分別對應(yīng)算法2的12～21步、25～35步以及36～41步。

3.1 復(fù)雜度分析

算法首先構(gòu)造了一個大小為4k的大頂堆，用來篩選與用戶真實(shí)位置歷史查詢概率最為相近的4k個位置。假設(shè)選取區(qū)域包含n個位置，在遍歷這些位置的同時，還需要調(diào)整堆，而調(diào)整堆的時間復(fù)雜度為O（logk），因此，通過最大堆篩選候選集的復(fù)雜度為O（nlogk）。然后將用戶真實(shí)位置lreal加入結(jié)果集，遍歷大小為4k的候選集，綜合考慮候選位置之間的物理距離和語義距離，記錄并篩選假位置。因?yàn)閚?k，所以后面從大小為4k的候選集篩選假位置的時間可以忽略不計(jì)。因此，該算法的時間復(fù)雜度為O（nlogk）。由于本算法中間只構(gòu)建了大小為4k的候選集，因此，該算法空間復(fù)雜度為O（k）。

3.2 安全度分析

當(dāng)算法生成的假位置集中在一小塊區(qū)域，假位置構(gòu)成的匿名區(qū)域面積也相應(yīng)地變小，使得用戶的真實(shí)位置更難隱藏。此時，k匿名只能滿足數(shù)量上的要求，而不能真正達(dá)到匿名的效果。本文提出的算法盡可能選擇與用戶真實(shí)位置距離較遠(yuǎn)的位置加入假位置集，使得生成的假位置盡量分散，從而使攻擊者難以確定用戶的真實(shí)位置。

類似地，當(dāng)算法生成的假位置集只含有一兩種語義信息，即使不能確定用戶所處的真實(shí)位置，用戶所處位置的語義信息也很容易推知，假位置集中單一的位置類型同樣也難以保證用戶的位置隱私安全。本文提出的算法篩除了與用戶真實(shí)位置的語義信息幾乎相同的位置，從而保證了假位置集語義信息的多樣，使得攻擊者難以確定用戶所處位置的語義信息。

另外，本算法生成假位置的查詢概率幾乎相同，分布均勻，每個位置能被區(qū)分于其他位置的概率均為1/k，使得攻擊者難以從假位置的概率分布上推測出用戶真實(shí)位置。而且，即使攻擊者已經(jīng)直接得知本文的算法，結(jié)果集的隨機(jī)性也使攻擊者難以確定用戶真實(shí)位置。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)使用真實(shí)數(shù)據(jù)集Geolife［30］來模擬地圖不同區(qū)域內(nèi)的用戶歷史查詢概率，該數(shù)據(jù)集是微軟亞洲研究院在2007年4月到2012年8月期間記錄的軌跡數(shù)據(jù)，包含了182名用戶這5年內(nèi)的17 621條GPS軌跡。

圖3中的熱圖（heatmap）顯示了Geolife數(shù)據(jù)集大部分的軌跡數(shù)據(jù)，其中較亮的區(qū)域代表人口密度相對較高的地區(qū)。實(shí)驗(yàn)選取的模擬區(qū)域的緯度坐標(biāo)范圍為 39.95°N至 40.00°N，經(jīng)度坐標(biāo)范圍為116.30°E，至116.35°E，位于北京五環(huán)內(nèi)的一個面積約為23.7平方千米的方形區(qū)域（圖3方框區(qū)域）。該區(qū)域被劃分為200×200 的網(wǎng)格（c1，c2，…，c40000），分為100組，每個網(wǎng)格用每個網(wǎng)格中心的（緯度，經(jīng)度）坐標(biāo)表示。數(shù)據(jù)集中每名用戶的軌跡數(shù)據(jù)都包含位置點(diǎn)的緯度、經(jīng)度和時間數(shù)據(jù)，將每條軌跡數(shù)據(jù)都統(tǒng)計(jì)到最近的網(wǎng)格，計(jì)算用戶在每個網(wǎng)格中花費(fèi)的時間，從而得到所有網(wǎng)格的歷史查詢概率。此外，由于Geolife數(shù)據(jù)集并沒有提供位置相關(guān)的語義信息，本實(shí)驗(yàn)還通過百度地圖API獲取所有網(wǎng)格的語義信息。

圖3 Geolife軌跡數(shù)據(jù)熱圖

實(shí)驗(yàn)采用 Java語言編程實(shí)現(xiàn)，運(yùn)行環(huán)境為Windows 10操作系統(tǒng)，2.30 GHz Intel Core i5處理器，8 GB內(nèi)存。實(shí)驗(yàn)?zāi)J(rèn)參數(shù)配置如表1所示。

表1 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)配置

4.2 結(jié)果分析

實(shí)驗(yàn)從假位置集生成效率、物理分散性、語義多樣性、不確定性以及識別率這5個方面評估本文提出的算法，并將其與同樣使用假位置技術(shù)的DLS算法［24］、enhanced?DLS 算法［25］、MMDS 算法［27］在這 5個方面的表現(xiàn)進(jìn)行比較。

4.2.1 生成效率

從圖4（a）可以看出，隨著k值的增加，4種算法生成假位置的時間都呈現(xiàn)緩慢上升的總體趨勢，而MMDS算法和本文提出的MDLS算法生成假位置集的花時卻遠(yuǎn)小于DLS和enhanced?DLS算法。這主要是因?yàn)楹髢煞N算法都需要對區(qū)域內(nèi)每個位置的查詢概率進(jìn)行排序，而另外兩個算法并不是通過排序篩選與用戶真實(shí)位置查詢概率相近的位置：MMDS算法定義了查詢概率距離，并作為選擇假位置公式的分母；本文提出的MDLS算法則是通過定義的用戶位置查詢概率差距小頂堆篩選出概率相近的位置，用空間換時間，在充分考慮背景知識的同時大大提升了假位置集生成的效率。

作為圖4（a）的補(bǔ)充，圖 4（b）展示了當(dāng)k值進(jìn)一步增加時，各個算法生成假位置時間不同的上升趨勢。當(dāng)k≥10時，由于POI類別的數(shù)目有限，MMDS算法能夠匿名成功的幾率特別低，因此圖4（b）只對比了另外3種算法生成假位置集的時間。

圖4 假位置生成時間

從圖 4（b）可以看出，DLS、enhanced?DLS 以及本文提出的MDLS算法呈現(xiàn)不同幅度的上升趨勢：DLS算法的上升趨勢最為平緩，幾乎沒有變化；enhanced?DLS算法的上升幅度最大，前后相差40 ms之多；本文提出的MDLS算法上升速度則介于兩者之間。DLS算法生成假位置集的花時主要在于排序，之后選擇假位置只需要花費(fèi)常數(shù)級的時間，所以k值的增加對于DLS算法生成假位置集幾乎沒有影響；enhanced?DLS算法除了排序花時，因?yàn)榭紤]到覆蓋面積的大小，需要多次反復(fù)遍歷候選集和結(jié)果集來計(jì)算權(quán)值，因此k值的增加對于enhanced?DLS算法生成假位置集影響較大；而本文提出的MDLS算法采用了邊選擇邊判斷的策略，只需要遍歷k次候選集按照公式篩選假位置，所以生成假位置的漲幅較為緩慢。

4.2.2 物理分散性

評估算法生成假位置集的物理分散程度可以從兩個方面入手：匿名區(qū)域面積和最小距離。生成假位置間的最小距離和構(gòu)成的匿名區(qū)域面積越大，表示生成的假位置分布越均勻分散。

圖5是4種算法生成結(jié)果集中假位置間的最小距離，可以發(fā)現(xiàn)，這4種算法都是隨著k值增加而逐漸下降并趨于平緩。當(dāng)k≤4時，本文提出的MDLS算法生成假位置間的最小距離明顯大于DLS和enhanced?DLS算法，前后者的區(qū)別主要在于除了最小距離是否還考慮了語義信息。MDLS算法和MMDS算法都綜合考慮了位置間的物理距離和語義距離，這說明保證位置語義的多樣性也能在一定程度上使得生成的假位置更加分散。

圖5 假位置間最小距離

不過隨著k值進(jìn)一步增加，4種算法生成假位置間的最小距離的差距也越來越小。這時最小距離也難以評估這些算法生成假位置分散程度，而匿名區(qū)域面積依然能很清楚地比較出4種算法生成假位置的分散程度差異。如圖6所示，當(dāng)k＞5時 MMDS算法假位置集構(gòu)成的匿名區(qū)域面積遠(yuǎn)遠(yuǎn)大于其他算法，這主要因?yàn)樵撍惴ㄊ紫刃枰ＷC生成的假位置的興趣點(diǎn)POI類別不同，這也保證了位置之間的距離，而其他3個算法都優(yōu)先考慮了位置的歷史查詢概率。不過，與另外兩種算法相比，本文提出算法生成的假位置依然具有較好的物理分散性。

圖6 覆蓋假位置的匿名區(qū)域面積

4.2.3 語義多樣性

實(shí)驗(yàn)采用θ－安全值評估算法生成假位置的語義多樣性，θ－安全值越大就表示生成假位置集的語義信息越豐富多樣，攻擊者越難確定用戶所處位置的語義信息。

從圖7可以看出，MMDS算法生成假位置的語義信息最為豐富多樣，θ－安全值都在0.9以上，接近于1。而本文提出的MDLS算法同樣考慮了位置的語義信息，但θ－安全值卻處于0.8～0.9之間，稍低于MMDS算法，主要原因在于兩種算法優(yōu)先考慮的因素不同。MMDS算法首先就篩除了POI類型接近的位置，在此基礎(chǔ)上再進(jìn)行選擇，從而保證了位置語義的多樣性。但隨著k值不斷增加，由于POI類型有限，MMDS算法匿名失敗的幾率越來越大，最終根本無法進(jìn)行匿名。DLS和enhanced?DLS算法都沒有考慮過位置的語義信息，θ－安全值在0.7左右，遠(yuǎn)低于前兩種算法。而enhanced?DLS算法的θ－安全值略高于DLS算法，DLS算法和enhanced?DLS算法的主要區(qū)別在于enhanced?DLS算法額外考慮了匿名面積這一因素，因此，可以發(fā)現(xiàn)物理分散性和語義多樣性呈正相關(guān)。

圖7 假位置集的θ－安全值

4.2.4 不確定性

熵代表了系統(tǒng)內(nèi)部的混亂程度，而位置熵是由位置集合內(nèi)位置的歷史查詢概率分布決定的，可以用來度量用戶所處位置的不確定性。位置熵越大，位置集合內(nèi)位置的歷史查詢概率越接近，用戶所處位置就越難以確定。

4種算法生成假位置集在不同k值下的位置熵如圖8所示，除了MMDS算法，其他3種算法的位置熵都隨著k增加而穩(wěn)步上升，而且都接近位置熵的最大值log2k。 一方面，因?yàn)?DLS、enhanced?DLS以及本文提出的MDLS算法都是優(yōu)先將位置歷史查詢概率相近的位置篩選出再選擇，另一方面，MMDS算法優(yōu)先篩除POI類型相近的位置，隨著k增加反而更難找到與用戶真實(shí)位置歷史查詢概率類似的位置。

圖8 假位置集位置熵

通過以上實(shí)驗(yàn)可以發(fā)現(xiàn)，本文提出的MDLS算法能夠快速生成物理分散且語義多樣的假位置集，從而有效地防范攻擊者的各種背景知識攻擊，保護(hù)用戶的位置隱私安全，使其獲得更安全更優(yōu)質(zhì)的服務(wù)。

4.2.5 識別率

雖然 DLS、enhanced?DLS以及本文提出的MDLS算法由于優(yōu)先考慮位置的歷史查詢概率都有著接近最大值的熵，攻擊者很難僅僅通過位置的歷史查詢概率推知用戶的真實(shí)位置，但是一旦攻擊者知道生成假位置集所用的算法，攻擊者就能針對算法的特點(diǎn)進(jìn)行推斷，使得用戶真實(shí)位置的識別率大大提升。文獻(xiàn)［31］通過分析DLS算法，設(shè)計(jì)了一種專門針對攻擊的算法ADLS。

ADLS算法通過反復(fù)遍歷用戶提交的假位置集和本地地圖的位置集，根據(jù)位置的歷史查詢概率查找本地地圖位置集中與假位置構(gòu)成集合熵最大的組合，最后根據(jù)式（6），（7）選出與用戶提交假位置集最為接近的組合假位置，推斷出用戶的真實(shí)位置。

式中，ri表示用戶提交的假位置，ci表示ADLS算法預(yù)測的假位置，根據(jù)與提交假位置集差距最小的集合確定用戶真實(shí)位置。

由于MMDS算法在k值較大時匿名成功的幾率特別低，圖9只比較了ADLS算法對DLS、enhanced?DLS以及MDLS 3種算法不同的識別率：3種算法被ADLS識別的概率都隨著k的增加而減小，其中DLS算法的識別率最高，enhanced?DLS算法和本文提出的MDLS算法的識別率則低了不少，這是因?yàn)閑nhanced?DLS算法除了位置的歷史查詢概率外還考慮了其他因素，并隨機(jī)選擇比較，使得ADLS算法更難通過生成的假位置集確定用戶真實(shí)位置。

圖9 假位置集識別率

5 結(jié)束語

針對當(dāng)前大多數(shù)假位置隱私保護(hù)方案沒有充分考慮攻擊者具有的背景知識這一問題，本文綜合考慮位置的查詢概率、語義信息以及物理分布，提出了一種基于多元數(shù)據(jù)的位置隱私保護(hù)方案MDLS。首先基于大頂堆選擇查詢與用戶真實(shí)位置查詢概率接近的位置構(gòu)成假位置候選集；然后通過計(jì)算候選位置與真實(shí)位置的物理距離以及語義距離篩選出物理分散且語義多樣的假位置；最后生成一個包含用戶真實(shí)位置且大小為k的假位置集。實(shí)驗(yàn)分別從假位置集生成效率、物理分散性、語義多樣性、不確定性以及識別率這5個維度將本文提出的算法與另外幾種位置隱私保護(hù)方案進(jìn)行比較，證明了本文提出算法不僅能快速生成假位置集，而且能在很大程度上滿足用戶的位置隱私保護(hù)需求。然而本文只研究了快照位置隱私保護(hù)，沒有考慮時間這一因素，而短時間內(nèi)用戶位置具有相關(guān)性，因此關(guān)于連續(xù)時間的位置隱私保護(hù)還有待進(jìn)一步研究。