路網(wǎng)環(huán)境下的語(yǔ)義多樣性位置隱私保護(hù)方法

曾海燕，左開(kāi)中，王永錄，劉 蕊

1.安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖241002

2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖241002

1 引言

隨著移動(dòng)設(shè)備和社交網(wǎng)絡(luò)的廣泛使用，基于位置的服務(wù)（Location Based Service，LBS）已得到了廣泛關(guān)注[1]。然而，在用戶(hù)提交位置以獲取相關(guān)服務(wù)的過(guò)程中必然會(huì)導(dǎo)致隱私泄露問(wèn)題[2]。因此，如何保護(hù)LBS中用戶(hù)隱私已成為眾多學(xué)者關(guān)注的焦點(diǎn)。

現(xiàn)有的LBS隱私保護(hù)研究主要針對(duì)自由空間[3-6]，但在現(xiàn)實(shí)生活中，用戶(hù)的移動(dòng)會(huì)受到道路網(wǎng)絡(luò)的限制。直接將自由空間中的隱私保護(hù)技術(shù)應(yīng)用到路網(wǎng)環(huán)境下會(huì)造成不同程度的隱私泄露。如圖1（a）所示，將用戶(hù)與其他4 個(gè)用戶(hù)匿名在一起，滿(mǎn)足用戶(hù)的5-匿名條件，混淆用戶(hù)真實(shí)位置。但是在路網(wǎng)環(huán)境下，路網(wǎng)結(jié)構(gòu)已知，由于該區(qū)域中只包含一條路段，并且該路段上只有一個(gè)用戶(hù)，因此，該區(qū)域不滿(mǎn)足匿名條件，無(wú)法滿(mǎn)足用戶(hù)的隱私需求，使得攻擊者追蹤到用戶(hù)。

圖1 用戶(hù)運(yùn)動(dòng)空間

現(xiàn)有的針對(duì)路網(wǎng)環(huán)境下的位置隱私保護(hù)方法主要是基于K-匿名和路段L-多樣性，即匿名集中不僅要滿(mǎn)足用戶(hù)的位置K-匿名需求，還至少包含L 條不同的路段[7]。文獻(xiàn)[8-11]均采用上述方法構(gòu)建匿名集，以滿(mǎn)足用戶(hù)的隱私要求，但是無(wú)法抵御語(yǔ)義推斷攻擊[12]。針對(duì)路網(wǎng)環(huán)境下的語(yǔ)義推斷攻擊，Yigitoglu等人[13]針對(duì)敏感語(yǔ)義位置泄露問(wèn)題，將整個(gè)地圖網(wǎng)絡(luò)劃分成若干個(gè)不相交的匿名集，實(shí)現(xiàn)隱私保護(hù)。但該方法構(gòu)造的匿名集過(guò)大。Li 等人[14]提出將路網(wǎng)進(jìn)行Voronoi 劃分，解決路網(wǎng)環(huán)境下語(yǔ)義位置隱私泄露問(wèn)題。然而，上述方法中語(yǔ)義位置和道路交叉口在路網(wǎng)中均以節(jié)點(diǎn)表示，當(dāng)某處包含多個(gè)語(yǔ)義位置時(shí)，則無(wú)法在路網(wǎng)中表示，且構(gòu)造的匿名集中語(yǔ)義位置類(lèi)型差異性較大，易于區(qū)分。陳慧等[15]針對(duì)路網(wǎng)環(huán)境下由位置語(yǔ)義分析造成敏感位置信息泄露問(wèn)題，充分考慮了位置普及度與敏感度，提出了一種滿(mǎn)足用戶(hù)個(gè)性化隱私需求的位置隱私保護(hù)方法。該方法將語(yǔ)義位置分布在路段上，構(gòu)建的路網(wǎng)模型符合實(shí)際，但是可能造成用戶(hù)所處語(yǔ)義位置類(lèi)型所占比例過(guò)大，造成隱私泄露。

綜上所述，路網(wǎng)環(huán)境下，針對(duì)語(yǔ)義推斷攻擊的隱私保護(hù)方案主要有以下不足：

（1）匿名集中包含的語(yǔ)義位置類(lèi)型差異性較大，攻擊者可根據(jù)相關(guān)背景知識(shí)，縮小匿名集范圍，從而推測(cè)出用戶(hù)當(dāng)前所處位置。

（2）匿名集中用戶(hù)所處語(yǔ)義位置類(lèi)型所占比例較大，增加攻擊者推測(cè)出用戶(hù)所處語(yǔ)義位置的概率。

針對(duì)上述問(wèn)題，提出了一種路網(wǎng)環(huán)境下的語(yǔ)義多樣性位置隱私保護(hù)方法，通過(guò)添加與用戶(hù)所處語(yǔ)義位置類(lèi)型相似的語(yǔ)義位置，提高用戶(hù)所處語(yǔ)義位置的不可區(qū)分性和不確定性，可更有效地抵御語(yǔ)義推斷攻擊。

2 預(yù)備知識(shí)

2.1 語(yǔ)義路網(wǎng)模型

本文將道路網(wǎng)絡(luò)抽象成無(wú)向圖，無(wú)向圖中的頂點(diǎn)表示道路交叉口，無(wú)向圖中的邊表示道路網(wǎng)絡(luò)中的路段。將地圖上的語(yǔ)義位置分布在無(wú)向圖中的邊上。

定義1（語(yǔ)義位置（Semantic Location））路段上的語(yǔ)義位置用SL(slid,eid,x,y,sltype,Vsltype)表示，其中：slid表示語(yǔ)義位置編號(hào)；eid 表示語(yǔ)義位置所在路段的編號(hào)；(x,y)表示語(yǔ)義位置的坐標(biāo)；sltype表示語(yǔ)義位置所屬的類(lèi)型，所有語(yǔ)義位置劃分成m 種類(lèi)型，則SLtype=是所有語(yǔ)義位置類(lèi)型的集合；Vsltype表示該類(lèi)型語(yǔ)義位置在不同時(shí)間段的用戶(hù)訪問(wèn)數(shù)，，其中，表示在tn時(shí)間段內(nèi)該類(lèi)語(yǔ)義位置的用戶(hù)訪問(wèn)數(shù)。

定義2（語(yǔ)義路網(wǎng)）語(yǔ)義路網(wǎng)用無(wú)向圖G=(V,E,SL)表示，其中：V 是圖中頂點(diǎn)集合，V={v1, v2,…,vn}，表示道路交叉口；E是圖中邊的集合，E={e1,e2,…,en}，表示路段；SL 是圖中語(yǔ)義位置的集合，SL={sl1,sl2,…,sln}。如圖2所示。

圖2 語(yǔ)義路網(wǎng)

2.2 相關(guān)定義

定義3（隱私需求）對(duì)一個(gè)發(fā)出LBS 請(qǐng)求的用戶(hù)u，其隱私需求用PD(NU,NS,NE,MAXNE)表示，其中，NU 為匿名集中用戶(hù)需求的用戶(hù)數(shù)；NS 為匿名集中用戶(hù)需求的語(yǔ)義位置類(lèi)型數(shù)；NE 為匿名集中用戶(hù)需求的路段數(shù)；MAXNE 為匿名集中用戶(hù)可容忍的最大路段數(shù)。

定義4（匿名集）匿名集是由用戶(hù)所在路段及其若干條相鄰路段組成，用AS 表示，AS={e1,e2,…,en} 。匿名集滿(mǎn)足用戶(hù)定義的各項(xiàng)隱私需求。

為了獲取不同類(lèi)型語(yǔ)義位置在不同時(shí)間段的用戶(hù)訪問(wèn)情況，利用微軟亞洲研究院提供的Geolife 數(shù)據(jù)集提取用戶(hù)的停留點(diǎn)數(shù)據(jù)。該數(shù)據(jù)集可通過(guò)http：//research.microsoft.com/en-us/projects/geolife/下載獲取。Geolife數(shù)據(jù)集收集了182位用戶(hù)在北京的軌跡數(shù)據(jù)，將提取的停留點(diǎn)數(shù)據(jù)與地圖上獲取的興趣點(diǎn)數(shù)據(jù)進(jìn)行匹配。不同時(shí)間段各類(lèi)語(yǔ)義位置的用戶(hù)訪問(wèn)分布情況如圖3所示。

圖3 用戶(hù)訪問(wèn)分布

由圖3可以看出，不同類(lèi)型語(yǔ)義位置一天的用戶(hù)訪問(wèn)數(shù)量變化趨勢(shì)大體相似，因此采用歐氏距離作為語(yǔ)義位置類(lèi)型相似度度量方法。

定義5（語(yǔ)義位置類(lèi)型相似度）假設(shè)兩個(gè)語(yǔ)義位置類(lèi)型分別為sltypep和和分別表示類(lèi)型為sltypep和sltypeq的語(yǔ)義位置在不同時(shí)間段的用戶(hù)訪問(wèn)數(shù)。根據(jù)歐式距離計(jì)算公式計(jì)算兩個(gè)語(yǔ)義位置類(lèi)型的相似度。

歐式距離越小，兩個(gè)語(yǔ)義位置類(lèi)型的用戶(hù)訪問(wèn)數(shù)差距越小，意味著兩個(gè)語(yǔ)義位置類(lèi)型的相似度越高，攻擊者能夠區(qū)分的概率越小。

定義6（最優(yōu)語(yǔ)義位置類(lèi)型集）最優(yōu)語(yǔ)義位置類(lèi)型集BESTsltype是指在所有語(yǔ)義位置類(lèi)型中，與用戶(hù)當(dāng)前所處語(yǔ)義位置所屬類(lèi)型相似度較高的前NS個(gè)語(yǔ)義位置類(lèi)型（不包含用戶(hù)當(dāng)前所處語(yǔ)義位置類(lèi)型），表示為，其中，表示與用戶(hù)當(dāng)前所處語(yǔ)義位置類(lèi)型相似度較高的語(yǔ)義位置類(lèi)型。

定義7（最優(yōu)路段）最優(yōu)路段是指候選路段中最能滿(mǎn)足用戶(hù)隱私需求的路段。通過(guò)計(jì)算屬于最優(yōu)語(yǔ)義位置類(lèi)型的語(yǔ)義位置數(shù)占該路段上語(yǔ)義位置總數(shù)的比例，選擇比例值最大的路段作為最優(yōu)路段。該比例由以下公式計(jì)算：

2.3 系統(tǒng)結(jié)構(gòu)

LBS 中，現(xiàn)有的隱私保護(hù)系統(tǒng)主要分為三種：獨(dú)立結(jié)構(gòu)、中心服務(wù)器結(jié)構(gòu)和分布式結(jié)構(gòu)。本文采用中心服務(wù)器結(jié)構(gòu)[2]。該結(jié)構(gòu)由移動(dòng)用戶(hù)、匿名服務(wù)器和LBS服務(wù)器三部分組成，如圖4所示。匿名服務(wù)器包含匿名模塊、通信模塊和查詢(xún)結(jié)果求精模塊。其中，匿名模塊是負(fù)責(zé)對(duì)用戶(hù)位置進(jìn)行匿名處理；通信模塊是負(fù)責(zé)與其他實(shí)體進(jìn)行通信；查詢(xún)結(jié)果求精模塊是負(fù)責(zé)對(duì)LBS服務(wù)器返回的結(jié)果進(jìn)行求精。當(dāng)用戶(hù)發(fā)出請(qǐng)求時(shí)，將自己的位置、查詢(xún)內(nèi)容和隱私需求發(fā)送給匿名服務(wù)器。匿名服務(wù)器根據(jù)隱私保護(hù)算法進(jìn)行匿名處理，并將處理后的信息發(fā)送給LBS 服務(wù)器。LBS 服務(wù)器計(jì)算出候選查詢(xún)結(jié)果集并返回給匿名服務(wù)器。匿名服務(wù)器對(duì)LBS 服務(wù)器返回的結(jié)果進(jìn)行篩選，并將精確結(jié)果返回給用戶(hù)。本系統(tǒng)中，匿名服務(wù)器需要保存當(dāng)前的地圖信息，語(yǔ)義位置信息和不同語(yǔ)義位置類(lèi)型的用戶(hù)訪問(wèn)分布情況。

圖4 中心服務(wù)器系統(tǒng)結(jié)構(gòu)

在本文系統(tǒng)中，對(duì)攻擊者做出如下假設(shè)：

（1）攻擊者可以獲得地圖數(shù)據(jù)，了解各類(lèi)語(yǔ)義位置的詳細(xì)信息，包括位置分布情況和用戶(hù)訪問(wèn)分布情況。

（2）攻擊者了解道路上用戶(hù)的數(shù)量。

（3）攻擊者可以截得匿名服務(wù)器發(fā)送給LBS服務(wù)器的信息。

2.4 攻擊模式

語(yǔ)義推斷攻擊是指通過(guò)分析用戶(hù)所使用的匿名集中各類(lèi)語(yǔ)義位置信息，推測(cè)用戶(hù)所在的精確位置或行為習(xí)慣[12]。如圖5 所示，圖中虛線框內(nèi)的路段構(gòu)成用戶(hù)的匿名集。圖5（a）所示的匿名集S1 中只包含一種語(yǔ)義位置類(lèi)型，則可認(rèn)為用戶(hù)當(dāng)前所處位置為醫(yī)院，進(jìn)而推測(cè)出用戶(hù)的身體狀況可能不佳。圖5（b）所示的匿名集S2中包含兩種語(yǔ)義位置類(lèi)型，滿(mǎn)足語(yǔ)義多樣性，但是如果用戶(hù)在夜里12 點(diǎn)發(fā)出LBS 請(qǐng)求，考慮到此時(shí)學(xué)校人數(shù)較少，便可將語(yǔ)義位置類(lèi)型為學(xué)校的用戶(hù)排除，進(jìn)而排除該用戶(hù)所在的路段，并推斷用戶(hù)當(dāng)前處于醫(yī)院；并且，S2 中醫(yī)院面積約占匿名集面積的2/3，則用戶(hù)被認(rèn)為在醫(yī)院的可能性更大。

圖5 語(yǔ)義推斷攻擊

3 基于語(yǔ)義位置多樣性算法

3.1 算法設(shè)計(jì)

根據(jù)上述分析，在路網(wǎng)環(huán)境下構(gòu)造匿名集時(shí)，不僅要考慮匿名集中的用戶(hù)位置數(shù)和路段多樣性，還需考慮匿名集中的語(yǔ)義信息。而只考慮語(yǔ)義位置類(lèi)型多樣性往往并不能保證匿名集的安全性，還需考慮匿名集中語(yǔ)義位置類(lèi)型相似性，提高用戶(hù)語(yǔ)義位置的不可區(qū)分性，使得攻擊者在一定背景知識(shí)下，無(wú)法推斷出用戶(hù)所在語(yǔ)義位置信息。因此，本文提出了一種語(yǔ)義多樣性的位置隱私保護(hù)算法，既滿(mǎn)足了用戶(hù)的K-匿名、路段L-多樣性和語(yǔ)義多樣性需求，又可抵御語(yǔ)義推斷攻擊。該算法的主要思想流程如圖6所示。

算法主要步驟為：

（1）將用戶(hù)所在路段加入到匿名集AS 中。

（2）根據(jù)用戶(hù)所在語(yǔ)義位置類(lèi)型，通過(guò)計(jì)算語(yǔ)義位置類(lèi)型相似度構(gòu)造最優(yōu)語(yǔ)義位置類(lèi)型集BS。

圖6 算法思想流程

（3）將當(dāng)前匿名集AS 的所有相鄰路段加入到候選路段集CS 中。

（4）從候選路段集CS 中選擇最優(yōu)路段加入到匿名集AS 中。

（5）匿名集AS 滿(mǎn)足隱私需求，返回AS；否則，重復(fù)執(zhí)行步驟（3）～（5）直至匿名成功。

算法1 給出了語(yǔ)義多樣性算法（Semantic Diversity Algorithm，SDA）的偽代碼。首先對(duì)一些變量進(jìn)行初始化（第1行），將用戶(hù)所在路段加入到匿名集AS 中（第2行），并根據(jù)用戶(hù)當(dāng)前所屬的語(yǔ)義位置類(lèi)型sltype和隱私需求PD(NS)，根據(jù)公式（1）計(jì)算結(jié)果構(gòu)建最優(yōu)語(yǔ)義位置類(lèi)型集BS（第3 行）；然后找到當(dāng)前AS 的所有相鄰路段，加入到候選路段集CS 中，并從CS 中找到最優(yōu)的一條路段加入到AS 中（第4～7 行）；判斷當(dāng)前匿名集AS 是否滿(mǎn)足隱私需求。滿(mǎn)足，則返回當(dāng)前匿名集AS；不滿(mǎn)足，則循環(huán)執(zhí)行（第4～9 行），直至AS 滿(mǎn)足隱私需求。

算法1 語(yǔ)義多樣性算法

輸入：用戶(hù)u 位置(x,y)，隱私需求PD。

輸出：匿名集AS。

1.初始化變量：匿名集AS={?}，候選路段集CS={?},最優(yōu)語(yǔ)義位置類(lèi)型集BS={?}；

2.根據(jù)用戶(hù)位置確定所在路段e1，AS={e1}，當(dāng)前位置所屬的語(yǔ)義類(lèi)型sltype；

3.根據(jù)sltype和PD(NS)，根據(jù)公式（1）計(jì)算結(jié)果構(gòu)建最優(yōu)語(yǔ)義位置類(lèi)型集BS；

4.While AS ≠?

5.將AS 的所有相鄰路段加入候選路段集合CS 中；

6.bestedge=OSLTR（AS，CS，BS）；//調(diào)用算法2（OSLTR），選擇最優(yōu)路段

7.將bestedge 加入AS 中；

8.if（Numberuser（AS）>PD（NU）and

NumberNS（AS）>PD（NS）and

（NumberNE（AS）>PD（NE）

&&NumberNE（AS）

9.return AS

10.break

11.end if

12.end while

在最優(yōu)路段的選擇問(wèn)題上本文提出了一種基于最優(yōu)語(yǔ)義位置類(lèi)型比（Optimal Semantic Location Type Ratio，OSLTR）路段選擇算法。該算法的主要思想是：計(jì)算候選路段集CS中每條路段上屬于最優(yōu)語(yǔ)義位置類(lèi)型集的語(yǔ)義位置在該路段上所占的比例，選擇比例值最大的路段作為最優(yōu)路段，加入匿名集AS中。算法2給出了OSLTR算法的偽代碼。

算法2 基于最優(yōu)語(yǔ)義位置類(lèi)型比路段選擇算法

輸入：當(dāng)前匿名集AS，候選路段集CS，最優(yōu)語(yǔ)義位置類(lèi)型集BS。

輸出：最優(yōu)路段bestedge。

1.計(jì)算AS 中不包含的最優(yōu)語(yǔ)義位置類(lèi)型集BS′AS；

2.if(BS′AS?)

3.for each ei∈CS

5.for each ej∈CS′

6. 根據(jù)公式（2）計(jì)算W(ej)，并將結(jié)果存入Max 集合中；

7.end for

8.將Max 中最大值所對(duì)應(yīng)的ej賦給bestedge；

9.end for

10.else

11.for each ei∈CS

12.根據(jù)公式（2）計(jì)算W(ei)，并將結(jié)果存入Max 集合中；

13.end for

14.將Max 中最大值所對(duì)應(yīng)的ei賦給bestedge；

15.end if

16.return bestedge

算法2首先將匿名集AS 中不包含的最優(yōu)語(yǔ)義位置類(lèi)型加入到BS′AS（第1行）；如果BS′AS不為空，則從候選匿名集CS 中找到包含BS′AS中語(yǔ)義位置類(lèi)型的路段，加入到CS′，根據(jù)公式（2）計(jì)算CS′中每條路段上屬于最優(yōu)語(yǔ)義位置類(lèi)型集的語(yǔ)義位置所占的比例，并將結(jié)果存入Max 集合中，將Max 中最大值所對(duì)應(yīng)的路段賦給bestedge（第2～8 行）；如果BS′AS為空，則根據(jù)公式（2）計(jì)算CS 中的每條路段上屬于最優(yōu)語(yǔ)義位置類(lèi)型集的語(yǔ)義位置所占的比例，并將結(jié)果存入Max 集合中，將Max 中最大值所對(duì)應(yīng)的路段賦給bestedge（第11～14行）；最后返回最優(yōu)路段bestedge。

3.2 算法分析

SDA 算法生成的匿名集采用降低位置信息粒度的方法保護(hù)用戶(hù)位置隱私。匿名集同時(shí)滿(mǎn)足了隱私需求中對(duì)位置、路段和語(yǔ)義多樣性要求。隱私需求中NU滿(mǎn)足K-匿名模型，保護(hù)用戶(hù)身份標(biāo)識(shí)；NS滿(mǎn)足路段L-多樣性，將用戶(hù)真實(shí)位置隱藏在NS 條的不同路段中；NE 滿(mǎn)足語(yǔ)義多樣性，保護(hù)用戶(hù)真實(shí)語(yǔ)義位置信息。

SDA 算法在考慮K-匿名、路段L-多樣性和語(yǔ)義多樣性的基礎(chǔ)上，還考慮到匿名集中語(yǔ)義位置類(lèi)型的相似性和不同類(lèi)型的語(yǔ)義位置在匿名集中占比情況。利用語(yǔ)義位置類(lèi)型的用戶(hù)訪問(wèn)分布來(lái)計(jì)算相似性，選擇最優(yōu)語(yǔ)義位置類(lèi)型，使得匿名集中語(yǔ)義位置類(lèi)型不易區(qū)分，當(dāng)攻擊者根據(jù)語(yǔ)義位置類(lèi)型訪問(wèn)情況進(jìn)行攻擊時(shí)，可以保證用戶(hù)語(yǔ)義位置類(lèi)型被推測(cè)出的概率不大于1/NE。每次添加的最優(yōu)路段是屬于最優(yōu)語(yǔ)義位置類(lèi)型的語(yǔ)義位置數(shù)最多的路段，增加匿名集中屬于最優(yōu)語(yǔ)義位置類(lèi)型的語(yǔ)義位置所占比例，從而降低屬于用戶(hù)語(yǔ)義位置類(lèi)型的語(yǔ)義位置所占比例，使得攻擊者在根據(jù)匿名集中語(yǔ)義位置類(lèi)型分布情況進(jìn)行攻擊時(shí)，減小推測(cè)出用戶(hù)語(yǔ)義位置類(lèi)型的概率。

因此，相比K-匿名、路段L-多樣性等方法，SDA 算法能夠針對(duì)語(yǔ)義推斷攻擊，提供更有效的隱私保護(hù)。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

本文對(duì)比了陳慧等人[15]提出的基于位置語(yǔ)義的路網(wǎng)環(huán)境下位置隱私保護(hù)算法（LSBASC），LSBASC 算法與本文算法構(gòu)造匿名集方式相似，都是通過(guò)網(wǎng)絡(luò)擴(kuò)張的方式，采用貪心策略，每次選取使匿名集隱私條件最優(yōu)的路段加入匿名集中。

本文實(shí)驗(yàn)的算法均采用Java 實(shí)現(xiàn)，硬件平臺(tái)為Intel Core?2 Quad CPU 2.83 GHz，2 GB內(nèi)存，操作系統(tǒng)為Microsoft Windows 7。實(shí)驗(yàn)數(shù)據(jù)采用真實(shí)數(shù)據(jù)集，北京市的公路網(wǎng)絡(luò)數(shù)據(jù)，共包括83 884個(gè)頂點(diǎn)，109 773條道路。該數(shù)據(jù)集可通過(guò)https：//figshare.com/articles/Urban_Road_Network_Data/2061897下載獲取。并從北京地圖上提取361 916 個(gè)語(yǔ)義位置（興趣點(diǎn)）包含10 種類(lèi)型，假設(shè)每個(gè)興趣點(diǎn)發(fā)送LBS 請(qǐng)求。實(shí)驗(yàn)設(shè)置了1 000 個(gè)發(fā)出查詢(xún)請(qǐng)求的用戶(hù)。表1 列出了本文實(shí)驗(yàn)參數(shù)設(shè)置。

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

本文從相對(duì)匿名度、平均匿名時(shí)間、隱私泄露程度和相對(duì)空間粒度4個(gè)方面對(duì)算法的性能進(jìn)行評(píng)估。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

（1）相對(duì)匿名度

相對(duì)匿名度是指執(zhí)行算法后匿名集中所包含的用戶(hù)數(shù)與隱私需求中用戶(hù)數(shù)的比值。相對(duì)匿名度越大，可提供的隱私保護(hù)度越高。如圖7 給出了相對(duì)匿名度與隱私需求中用戶(hù)數(shù)的關(guān)系。由圖7可以看出，隨著隱私需求中用戶(hù)數(shù)的增加，相對(duì)匿名度逐漸減小，但是相對(duì)匿名度都大于1，而SDA算法的相對(duì)匿名度一直高于LSBASC 算法。因此，SDA 算法所提供的隱私保護(hù)度更高。

圖7 相對(duì)匿名度

（2）平均匿名時(shí)間

平均匿名時(shí)間是指算法成功匿名所用的時(shí)間。平均匿名時(shí)間越少，算法執(zhí)行效率越好。如圖8 給出了平均匿名時(shí)間與隱私需求中用戶(hù)數(shù)的關(guān)系。由圖8 可以看出，當(dāng)用戶(hù)數(shù)小于40 時(shí)，SDA 算法的時(shí)間要高于LSBASC 算法，大于40 時(shí)要低于LSBASC 算法，這是由于LSBASC算法在添加路段時(shí)，只要求加入構(gòu)成區(qū)域隱私度最大的路段，這時(shí)用戶(hù)數(shù)少的路段可能構(gòu)成的隱私度最大，因此需要添加更多的路段來(lái)滿(mǎn)足用戶(hù)數(shù)隱私需求，算法執(zhí)行次數(shù)增加導(dǎo)致匿名時(shí)間增加。

（3）隱私泄露程度

圖8 平均匿名時(shí)間

本文隱私泄露程度采用匿名集中用戶(hù)真實(shí)位置所屬類(lèi)型的語(yǔ)義位置數(shù)在匿名集中所占的比例來(lái)度量。由圖9 可以看出，SDA 算法的隱私泄露程度一直小于LSBASC 算法，且波動(dòng)程度小于LSBASC，這是由于SDA算法在生成匿名集時(shí)，添加的最優(yōu)路段是相似語(yǔ)義位置數(shù)多的路段，盡量減小真實(shí)語(yǔ)義位置類(lèi)型所占的比例，而LSBASC 算法只考慮的區(qū)域的隱私度，并未考慮到該語(yǔ)義位置類(lèi)型，因此波動(dòng)較大。所以，由圖可知SDA 算法的隱私泄露程度要低于LSBASC 算法3%，SDA算法的隱私保護(hù)效果更好。

圖9 隱私泄露程度

（4）相對(duì)空間粒度

相對(duì)空間粒度是指隱私需求中可容忍的最大路段數(shù)MAXNE 與執(zhí)行算法后匿名集中路段數(shù)的比值[15]。相對(duì)空間粒度越大，匿名空間越小，越接近最優(yōu)解，所提供的服務(wù)質(zhì)量越高。如圖10 給出了相對(duì)空間粒度與隱私需求中用戶(hù)數(shù)的關(guān)系。由圖10 可以看出，隨著用戶(hù)數(shù)的增加，相對(duì)空間粒度逐漸下降，這是由于用戶(hù)數(shù)的增加會(huì)導(dǎo)致匿名集中路段數(shù)的增加，從而降低相對(duì)空間粒度。當(dāng)用戶(hù)數(shù)大于20 時(shí)，SDA 算法的相對(duì)空間粒度一直大于LSBASC 算法，這是由于LSBASC 算法在添加路段時(shí)，并沒(méi)有考慮到路段上用戶(hù)數(shù)，每次添加的路段上人數(shù)可能較少，導(dǎo)致添加的路段增多，造成匿名空間較大。由圖10 可知，SDA 算法所構(gòu)建的匿名集空間比LSBASC 算法減小了21%，所提供的服務(wù)質(zhì)量更高。

圖10 相對(duì)空間粒度

5 結(jié)論

本文針對(duì)路網(wǎng)環(huán)境下的語(yǔ)義推斷攻擊問(wèn)題，提出了一種語(yǔ)義多樣性的位置隱私保護(hù)方法。該方法針對(duì)匿名集中語(yǔ)義位置類(lèi)型易區(qū)分問(wèn)題，通過(guò)計(jì)算語(yǔ)義位置類(lèi)型相似度，選擇相似度較高的語(yǔ)義位置類(lèi)型構(gòu)建最優(yōu)語(yǔ)義類(lèi)型集，增加用戶(hù)所處語(yǔ)義位置類(lèi)型的不確定性；通過(guò)選擇屬于最優(yōu)語(yǔ)義位置類(lèi)型集的語(yǔ)義位置占比最大的路段來(lái)構(gòu)造匿名集，降低推測(cè)用戶(hù)所處語(yǔ)義位置類(lèi)型的概率。采用真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了本文所提方法的有效性。本文研究是針對(duì)快照查詢(xún)中的語(yǔ)義位置隱私保護(hù)，因此，下一步研究工作是如何保護(hù)連續(xù)查詢(xún)中的語(yǔ)義位置隱私。