賈媛媛　史志才　方凱

摘 要： 針對(duì)用戶連續(xù)位置查詢請(qǐng)求服務(wù)中未考慮語(yǔ)義信息而導(dǎo)致用戶敏感語(yǔ)義泄露問(wèn)題，為了實(shí)現(xiàn)對(duì)道路網(wǎng)絡(luò)上客戶端的查詢隱私、位置隱私和語(yǔ)義位置隱私保護(hù)，本文提出一種離線軌跡聚類和語(yǔ)義位置圖相結(jié)合的算法來(lái)進(jìn)行隱藏用戶的選擇，使隱藏用戶的位置具有明顯的多樣性和不同的語(yǔ)義以及多樣化的服務(wù)請(qǐng)求，有效保護(hù)客戶端的語(yǔ)義和位置隱私。在具有2個(gè)定義指標(biāo)的真實(shí)地圖上評(píng)估了該算法的有效性，整個(gè)連續(xù)查詢道路網(wǎng)絡(luò)服務(wù)的過(guò)程中，有很好的成功率和查詢處理時(shí)間。同時(shí)與現(xiàn)有的其他可信第三方模型算法進(jìn)行了對(duì)比分析，驗(yàn)證了本文算法的有效性。

關(guān)鍵詞： 位置隱私保護(hù); 連續(xù)查詢; 軌跡聚類; 語(yǔ)義位置圖; 語(yǔ)義位置隱私

文章編號(hào)： 2095-2163（2021）07-0156-07中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼： A

Semantic location privacy protection algorithm based on continuous query

JIA Yuanyuan1， SHI Zhicai1，2 ， FANG Kai1

（1 School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China;

2 Shanghai Key Laboratory of Integrated Administration Technologies for Information Security， Shanghai 200240， China）

【Abstract】Since the user's continuous location query request service without considering semantic information ， to realize the protection of query privacy， location privacy and semantic location privacy of the client on the road network， this paper proposes an algorithm of offline trajectory clustering and semantic location map to choose hidden users， so that the hidden users' locations have obvious diversity， different semantics and diversified service requests effectively protect the semantics and location privacy of the client. The effectiveness of the algorithm is evaluated on a real map with two defined indicators， the entire process of continuously querying road network services has a very good success rate and query processing time. At the same time， compared with other trusted third-party model algorithms， the validity of this algorithm is verified.

【Key words】location privacy-preserving; continuous query; trajectory clustering algorithm; semantic location graph; semantic location privacy

0 引 言

位置大數(shù)據(jù)為人們的生活帶來(lái)了巨大的改變，在給人們帶來(lái)顯著收益的同時(shí)，也帶來(lái)了個(gè)人信息泄露的危險(xiǎn)。2014年，iPhone用戶隱私泄露事件披露出蘋(píng)果公司曾私自記錄每次使用LBS（基于位置的信息服務(wù)）應(yīng)用時(shí)的位置信息，從而造成用戶的大量位置信息泄露[1]。因此，在用戶使用LBS應(yīng)用時(shí)，如何保護(hù)用戶的個(gè)人隱私成為一個(gè)待解決的問(wèn)題。

現(xiàn)有的隱私保護(hù)方法擴(kuò)展了查詢客戶端的范圍，一些研究者們將k-1個(gè)其他用戶也包括進(jìn)來(lái)[2-4];但在這個(gè)過(guò)程中，會(huì)將具有不同移動(dòng)趨勢(shì)的其他請(qǐng)求結(jié)果移動(dòng)對(duì)象包括起來(lái)，這可能是攻擊的來(lái)源。2007年，Liu借鑒數(shù)據(jù)發(fā)布隱私處理中的l-差異性模型的思想，提出了位置l-差異性模型，以防止位置同質(zhì)性攻擊[5]。但最初提出的位置差異性模型忽略了用戶的位置語(yǔ)義。直觀上來(lái)講，用戶位置帶有語(yǔ)義信息，如用戶現(xiàn)在位于早餐店，說(shuō)明用戶可能在吃早餐;用戶在醫(yī)院，則該用戶很大概率有某種疾病。為了保護(hù)用戶的語(yǔ)義位置，Damiani等人[6]采用了語(yǔ)義位置隱藏方法，該方法允許用戶定義個(gè)性化的隱私配置文件，該配置文件說(shuō)明了指定的敏感場(chǎng)所類型和每種類型所需的隱私程度。但是這種語(yǔ)義位置掩蓋方法僅被設(shè)計(jì)為在不受限制、不受約束的空間中工作移動(dòng);但在現(xiàn)實(shí)環(huán)境中，移動(dòng)用戶大部分在道路網(wǎng)絡(luò)上，因此可能導(dǎo)致隱私泄露。Lee等人[7]提出了一種位置隱私保護(hù)技術(shù)，該技術(shù)可以保護(hù)位置語(yǔ)義免受對(duì)手的攻擊，采用第三方可信匿名服務(wù)器，該服務(wù)器使用位置語(yǔ)義信息來(lái)掩蓋用戶的語(yǔ)義位置。同樣，研究時(shí)只考慮了歐幾里得空間，在路網(wǎng)限制下會(huì)導(dǎo)致隱私泄漏。又有一些學(xué)者提出多樣化的服務(wù)請(qǐng)求[8]，從而滿足k-匿名性和l-多樣性隱私條件。然而，確定移動(dòng)用戶在線的語(yǔ)義位置是一個(gè)挑戰(zhàn)，這使得絕對(duì)隱私保護(hù)的實(shí)現(xiàn)更具挑戰(zhàn)性。

本文提出了一種保護(hù)用戶語(yǔ)義位置隱私的連續(xù)查詢道路網(wǎng)絡(luò)服務(wù)隱私保護(hù)算法，貢獻(xiàn)如下：

（1）提出一種離線聚類移動(dòng)用戶軌跡的算法，并使用在線導(dǎo)出的移動(dòng)趨勢(shì)來(lái)幫助選擇匿名用戶，提高客戶端的隱私保護(hù)程度。

（2）提出一個(gè)生成語(yǔ)義位置圖的算法，以幫助確定在線用戶的語(yǔ)義位置，利用導(dǎo)出的離線軌跡聚類算法與語(yǔ)義位置圖相結(jié)合來(lái)保護(hù)用戶在路網(wǎng)下連續(xù)查詢的語(yǔ)義位置隱私。

1 系統(tǒng)架構(gòu)及相關(guān)知識(shí)

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

為了避免客戶端計(jì)算量過(guò)大，本文采用由移動(dòng)客戶端（MC）、匿名服務(wù)器（AS）和基于位置的服務(wù)器（LBS）組成的可信第三方體系結(jié)構(gòu)[9]。蜂窩服務(wù)提供商為匿名服務(wù)器提供了用戶的初始軌跡和服務(wù)請(qǐng)求（查詢內(nèi)容）數(shù)據(jù)庫(kù)。位置和服務(wù)請(qǐng)求數(shù)據(jù)庫(kù)可以通過(guò)客戶端定期電話呼叫和LBS查詢服務(wù)進(jìn)行獲取，如果沒(méi)有初始數(shù)據(jù)，匿名服務(wù)器會(huì)收集幾天的位置服務(wù)請(qǐng)求數(shù)據(jù)，在移動(dòng)用戶請(qǐng)求LBS的過(guò)程中，將從用戶那里獲得更多的位置數(shù)據(jù)。同時(shí)允許MC使用隱私配置文件k，即期望匿名的用戶數(shù)。

系統(tǒng)的核心是AS，AS由隱藏存儲(chǔ)庫(kù)（CR）和離線軌跡聚類引擎（TCE）組成。系統(tǒng)的功能可以定義為：

（1）隱藏存儲(chǔ)庫(kù)保存一些以前隱藏的結(jié)果，并使用其來(lái)生成新的隱藏區(qū)域。

（2）軌跡聚類引擎對(duì)移動(dòng)用戶的軌跡數(shù)據(jù)庫(kù)進(jìn)行聚類，結(jié)構(gòu)如圖1所示。

1.2 路網(wǎng)模型

道路網(wǎng)由一個(gè)有向圖G=（V，E）表示，由交叉點(diǎn)V=（n0，n1，...，nn）和定向邊E=（（Sid，ninj）| ni，nj∈V）表示。Edge =（Sid，w0，w1，con，ninj）∈e表示連接實(shí)際道路網(wǎng)絡(luò)中2個(gè)交叉點(diǎn)ni和nj的路段，其屬性包括路段標(biāo)識(shí)符Sid、路段分類w0、交通密度w1和服務(wù)請(qǐng)求類型con（sr1，sr2，…，srn∈con，其中每個(gè)sr是一個(gè)服務(wù)請(qǐng)求）。研究中將根據(jù)路段的速度限制對(duì)其進(jìn)行分類。路段分為主要路段（限速<40 km/hr）、普通路段（40 km/hr≤限速<70 km/hr）、公路（70 km/hr≤限速<100 km/hr）、高速公路（限速≥100 km/hr），分別用p、a、h、ex表示。因此，路段分類w0可用p、a、h或ex表示。例如，w0=ex表示快速路分類。將用戶在時(shí)間戳為t和坐標(biāo)為（x，y）的路段S上的位置表示為l =（Sid，x，y，t）

定義1 軌跡 由TR={tid，l0，l1，…，ln}表示的軌跡，是道路網(wǎng)絡(luò)上用戶隨時(shí)間變化的位置l0，l1，…，ln的時(shí)間順序序列，由軌跡標(biāo)識(shí)符tid唯一標(biāo)識(shí)。對(duì)于一個(gè)移動(dòng)用戶來(lái)說(shuō)，對(duì)應(yīng)的行程與起始位置和目的地位置形成一條軌跡。

定義2 語(yǔ)義位置 語(yǔ)義位置是一個(gè)區(qū)域，在該區(qū)域中聚集的用戶具有相似的情景信息，如年齡、性別、活動(dòng)等。學(xué)校、醫(yī)院、公司等都可以是語(yǔ)義位置[10]。

定義3 類簇 對(duì)于給定的軌跡集T={TR1，...，TRn}在道路網(wǎng)絡(luò)上，類簇cw0是在具有相似段分類w0的所有段中的所有段簇csid的集合。因此，類簇是cp、ca、ch、cex，其中每個(gè)類簇通?？梢员硎緸閏w0。

定義4 集群 對(duì)于給定的軌跡集T={TR1，...，TRn}在道路網(wǎng)絡(luò)上，集群C是所有類簇的集合，即C={cp，ca，ch，cex}。因此，C表示具有段分類w0的所有類簇。

2 軌跡聚類算法及語(yǔ)義位置圖

2.1 軌跡聚類算法

聚類算法將數(shù)據(jù)庫(kù)對(duì)象分組為一組有意義的子類，所以根據(jù)用戶在同一路段上的相似運(yùn)動(dòng)特征，離線將其軌跡聚類成子類[11]。在一個(gè)網(wǎng)段內(nèi)的用戶可以被認(rèn)為是網(wǎng)絡(luò)接近的，因此在移動(dòng)中將顯示一組子類特征，這些特征將反映該路段上任何在線移動(dòng)對(duì)象的特征。因此，可以從離線特性中估計(jì)該對(duì)象的加入是否會(huì)在將用戶偽裝成在線特性之前保護(hù)客戶端的隱私。根據(jù)路段id、服務(wù)請(qǐng)求、流向、速度、時(shí)間、路段長(zhǎng)度及其速度限制，將離線移動(dòng)用戶的軌跡聚類成沿路段的子類。利用這一先驗(yàn)信息，提出了一種基于用戶軌跡的軌跡聚類算法?？紤]一組由T={TR1，...，TRn}表示的一組軌跡在TCE中，檢查從第一個(gè)位置l0到最后一個(gè)位置ln的單個(gè)軌跡TRi={tid，l0，l1，…，ln}。取軌跡中每?jī)蓚€(gè)連續(xù)點(diǎn)，例如li? and? li+1，并使用地圖匹配方法檢查以獲得與2個(gè)路段相交的道路交叉點(diǎn)[12]。將獲得的連接節(jié)點(diǎn)作為新點(diǎn)插入正在檢查的軌跡中的li和li+1之間。在檢查給定軌跡TRi中的每個(gè)點(diǎn)之后，TRi中添加的連接節(jié)點(diǎn)序列將作為軌跡分割點(diǎn)，用于沿段將軌跡分割為軌跡碎片（tf）。例如，在圖2中，軌跡C具有沿段2和段3斷裂的2個(gè)軌跡碎片。分析單個(gè)軌跡碎片所經(jīng)過(guò)的時(shí)間段，并將其分為一天中的不同時(shí)間段（tb）。對(duì)T中的所有軌跡集重復(fù)此過(guò)程。

根據(jù)路段id、流向、速度（v）、路段長(zhǎng)度、行程時(shí)間（tb）和該路段的速度限制vL對(duì)軌跡碎片進(jìn)行分組，形成一組基簇。然后，計(jì)算出一個(gè)段中每個(gè)基簇上產(chǎn)生的交通密度w1作為軌跡碎片的數(shù)量。交通密度給出一天中給定時(shí)間段內(nèi)具有特定特征用戶的可能數(shù)量。例如，在圖2中，如果所有軌跡片段具有相似的特性，那么段2將具有3的交通密度，而段1具有2的密度。同一段id下的一組基簇構(gòu)成一個(gè)段簇csid。該算法根據(jù)b=（Sid，w0，sr，v，w1，tb，ninj）的段id輸出一個(gè)基本簇，作為tb時(shí)該段上的用戶特征組。最后，將相似道路分類w0下的所有路段簇抽象表示為cp、ca、ch、cex∈C的類簇，根據(jù)路段分類進(jìn)行抽象，將有助于隱藏具有不同位置語(yǔ)義的用戶。一組類簇構(gòu)成一個(gè)C簇，具體描述如算法1所示。

算法1 軌跡聚類算法

輸入 <有向圖G>， ，

0輸出 <集群C = cp，ca，ch，cex>

1：有向圖G 由節(jié)點(diǎn) V（ni，nj∈V） 和邊E （e∈ E）組成;

2： for TRi，i=1...n do

3：檢查每個(gè)li和 li+1以獲得路口節(jié)點(diǎn)ni;

4：將獲得的節(jié)點(diǎn)作為新點(diǎn)插入li和li+1之間;

5：使用新的節(jié)點(diǎn)將TR分解為tf;

6：為每個(gè)e分配唯一標(biāo)識(shí)Sid;

7：將所有tf的tb進(jìn)行分類;

8：根據(jù)Sid， v ， vL， tb， ninj和|ninj|將所有tf 沿著e分組成b;

9： end for

10：在每個(gè)b中評(píng)估w1;

11：將每個(gè)e中的所有b分組為csid;

12：對(duì)所有csid 分組 w0和cw0相同;

13：將所有cw0輸出為C

2.2 語(yǔ)義位置圖

本節(jié)中，建立一種語(yǔ)義位置圖的算法，以幫助選擇要隱藏的用戶，從而保護(hù)語(yǔ)義位置隱私。將語(yǔ)義位置隱私定義為不同時(shí)間點(diǎn)用戶訪問(wèn)量，采用用戶到訪時(shí)間作為定義語(yǔ)義位置的標(biāo)準(zhǔn)。例如晚上十點(diǎn)，用戶可能訪問(wèn)酒吧、但是不可能訪問(wèn)早餐店，這里可以采用一個(gè)時(shí)間點(diǎn)來(lái)標(biāo)識(shí)一個(gè)語(yǔ)義位置。但是晚上九點(diǎn)，用戶可能訪問(wèn)娛樂(lè)場(chǎng)所、醫(yī)院等等，僅僅采用一個(gè)時(shí)間點(diǎn)的用戶訪問(wèn)量是不夠的，因此采用一個(gè)24維的向量來(lái)表示語(yǔ)義位置[13]。一個(gè)語(yǔ)義位置即如式（1）所示：

其中，L0，L1，...，L23分別表示某一個(gè)小時(shí)內(nèi)某個(gè)語(yǔ)義位置的用戶訪問(wèn)數(shù)，其中u是在L0，L1，...，L23提供的服務(wù)類別，例如，將診所、衛(wèi)生站、醫(yī)院、牙科診所等歸為“健康”類別，其中“健康”是指提供的服務(wù)類別，進(jìn)行分類是為了避免用類似的服務(wù)隱藏用戶位置，以增強(qiáng)其語(yǔ)義位置的l-多樣性。每個(gè)語(yǔ)義位置都有一個(gè)特定的區(qū)域，比如學(xué)校有對(duì)應(yīng)的區(qū)域，不在這個(gè)區(qū)域的位置，就屬于別的語(yǔ)義位置，利用語(yǔ)義位置集SL，采用地圖匹配的方法在路網(wǎng)模型的各個(gè)路段上精確定位相關(guān)的位置。然后，生成一個(gè)語(yǔ)義位置圖G來(lái)描述各種語(yǔ)義位置及其提供的服務(wù)。語(yǔ)義位置算法如算法2所示。

算法2 語(yǔ)義位置圖算法

輸入 <有向圖G >，

輸出 <語(yǔ)義位置圖G′>和< SLu>

1：有向圖G 由節(jié)點(diǎn) V（ni，nj∈V） 和邊E （e∈ E）組成;

2： for Li，i=1，...，n do

3：根據(jù)u進(jìn)行標(biāo)記L0， L1， L2，.....，L23

4：使得同一組L0， L1， L2，.....，L23在相同u下

5：將每個(gè)組輸出為SLu

6： end for

7： for Li，i=1...n do

8：插入到G

9：返回G

10： end for

3 隱私保護(hù)算法

在這一部分中，使用軌跡聚類算法和語(yǔ)義位置圖來(lái)開(kāi)發(fā)隱私保護(hù)算法。移動(dòng)客戶端（MC）以q=（qid，l，ti，tf，k，sr）的形式發(fā)送新的查詢q，其中l(wèi)是位置坐標(biāo)，ti是查詢啟動(dòng)時(shí)間，tf是過(guò)期時(shí)間。服務(wù)請(qǐng)求是sr，隱私配置文件k，qid是客戶端id。當(dāng)接收到新的查詢q時(shí)，AS確定了q的時(shí)間，并使用該位置來(lái)查找將其發(fā)出的段、段的分類、與G中的q相關(guān)聯(lián)的語(yǔ)義位置L以及其所屬的服務(wù)提供的SLU的類別。

定義一個(gè)交通密度閾值σ，低于這個(gè)閾值就不適合執(zhí)行在線隱藏。w1≥σ意味著會(huì)在tb時(shí)間段找到足夠的移動(dòng)用戶。交通密度閾值σ由AS根據(jù)歷史確定。

為了在線查找匿名MC的用戶，TCE搜索除包含MC的類簇cw0以外的所有類簇，隨機(jī)查找k-1個(gè)其他類簇，并從所選類簇中選擇一個(gè)時(shí)間tb滿足q時(shí)間的基簇。選擇的基簇必須滿足設(shè)計(jì)的隱藏條件，以幫助實(shí)現(xiàn)采用隨機(jī)段采樣方法的絕對(duì)隱私保護(hù)。隱藏C條件：全部選定的基簇必須滿足以下幾方面：

（1）數(shù)量是k-1。

（2）第（k-1）個(gè)選擇的基簇bk-1時(shí)間段tbk-1必須滿足查詢q的時(shí)間t和第一個(gè)選擇的基本簇b1的時(shí)間tb1，即t∈tb1;t∈tbk-1。

（3）任何選定的基簇交通密度滿足w1（b） ≥σ， w1（b1）≥σ， w1（bk-1）≥σ。

（4）所選基簇sr（bk-1）的服務(wù)請(qǐng)求sr（bk-1）不能與q和第一個(gè)所選基簇b1的服務(wù)請(qǐng)求相同，sr（b1）≠sr（bk-1） ≠sr（q）。

（5）第（k-1）個(gè)所選基簇中，由所選段上語(yǔ)義位置L服務(wù)提供SLU（bk-1）的類別不應(yīng)與q和第一個(gè)所選基簇b1的類別相同，即SLU（b1）≠SLU（bk-1）≠SLU（q）。

（6）第（k-1）個(gè)選擇的基簇的段分類cw0（bk-1）不應(yīng)與q和第一個(gè)選定的基簇b1相同，即cw0（bk-1） ≠ cw0 （b1） ≠ cw0（q）。

當(dāng)滿足隱藏條件時(shí)，AS將k-1個(gè)其他在線用戶q'偽裝成具有k-1個(gè)選定基本簇的特征，這些特征從其各自的段轉(zhuǎn)移到q個(gè)隱藏區(qū)域，如果不滿足這些條件那么所有查詢都將被抑制。用戶id被刪除，并替換為準(zhǔn)id，然后將其放入隱藏區(qū)域Ri中，其中i代表具有隱藏區(qū)域標(biāo)識(shí)Rid的第i個(gè)快照。然后將包含k個(gè)用戶的隱藏區(qū)域Ri轉(zhuǎn)發(fā)到LBS。

對(duì)于連續(xù)查詢LBS，查詢將由AS在周期內(nèi)（tf-ti）周期性地發(fā)出。如果用戶請(qǐng)求連續(xù)服務(wù)，則AS將請(qǐng)求第一個(gè)快照的連續(xù)服務(wù)的用戶隱藏起來(lái)，以便在整個(gè)查詢期間保持相同的隱藏用戶，從而始終確保隱藏條件。此外，保留一個(gè)存儲(chǔ)庫(kù)，其中包含已隱藏的用戶請(qǐng)求，以便在以后與同一段相關(guān)時(shí)使用。滿足隱藏條件匿名集的數(shù)目用n表示。隱私保護(hù)算法如算法3所述。

算法3 隱私保護(hù)算法

輸入 <查詢q = qid， l， k ， ti， tf， sr>， <類簇cw0= （cp，ca，ch，cex） >， < G>， < SLU>

輸出 <隱藏區(qū)域>

1： for q在t=ti=i發(fā)布;

2：確定q的ti， e， cw0， L和SLU;

3：在cw0（b1）≠cw0（q）和ti∈ tb1的e中隨機(jī)輸出基簇 （b1）;

4：確保w1（b1）≥σ， SLU（b1）≠SLU（q）且sr（b1）≠sr（q）;

5：轉(zhuǎn)到10行;

6：for k >2 do

7：使得w1（bk-1）≥σ;cw0（bk-1）≠cw0（b1）≠cw0（q）;sr（b1）≠sr（bk-1）≠sr（q）;SLU（b1）≠SLU（bk-1）≠SLU（q）;

8： end for;

9： if滿足7行條件then

10：在各自的e上選擇特征為b1到bk-1的在線q';

11：用k-1個(gè)其他q'將q隱藏到匿名區(qū)Ri中;

12：用準(zhǔn)id替換qid;

13：分配區(qū)域標(biāo)識(shí)Rid;

14：否則禁止查詢;

15： end if

16：將Ri轉(zhuǎn)發(fā)到LBS;

17： for t>ti=i do

18：重復(fù)執(zhí)行 2-17;

19： end for

4 安全性分析

本文使用軌跡聚類和語(yǔ)義位置圖的算法能夠抵御查詢同質(zhì)性攻擊、位置同質(zhì)性攻擊。查詢同質(zhì)性攻擊指的是攻擊者通過(guò)當(dāng)前匿名集發(fā)起的相同查詢語(yǔ)義來(lái)推斷出用戶的敏感信息。為了避免查詢同質(zhì)性攻擊，由于本文算法避免相同服務(wù)的2個(gè)用戶在同一個(gè)匿名集中，所以攻擊者推出用戶的概率為1/k。對(duì)于位置相似攻擊，本文算法使用不同的分類來(lái)隱藏不同位置的用戶，保證客戶端語(yǔ)義位置鏈接到用戶的概率為1/k。

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

5.1 實(shí)驗(yàn)數(shù)據(jù)

本節(jié)主要通過(guò)實(shí)驗(yàn)驗(yàn)證用戶在連續(xù)查詢時(shí)與LBS服務(wù)器的交互情況、在相關(guān)參數(shù)變化下對(duì)本文算法性能的影響以及與Kamenyi等人[14]提出一種隱私保護(hù)算法VD-DCA（Authenticated Velocity-Distance based Dynamic Cloaking Algorithm）方法進(jìn)行仿真實(shí)驗(yàn)比較。

本文實(shí)驗(yàn)算法均采用 JAVA 實(shí)現(xiàn)，硬件平臺(tái)為 Intel （R）Core （TM） i5-8265U CPU 1.80 GHz，8 GB內(nèi)存，操作系統(tǒng)為Microsoft Windows10。實(shí)驗(yàn)數(shù)據(jù)采用真實(shí)數(shù)據(jù)：上海市的公路網(wǎng)絡(luò)數(shù)據(jù)[15]，共包括 106 867 個(gè)頂點(diǎn)（結(jié)點(diǎn)），213 734條道路（邊）并從地圖上提取20 148個(gè)POI，其中包括上海市50個(gè)不同類別的服務(wù)，作為語(yǔ)義位置。每隔5 s記錄了100個(gè)快照。實(shí)驗(yàn)設(shè)置了10 000個(gè)發(fā)出查詢請(qǐng)求的用戶，并在上海地圖上以不同的速度移動(dòng)，對(duì)其分配了不同的服務(wù)請(qǐng)求。根據(jù)本文的分類和路段id，對(duì)所有路段進(jìn)行速度限制。

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

本文從成功率、查詢處理時(shí)間對(duì)算法的性能進(jìn)行評(píng)估。對(duì)此擬做研究分述如下。

（1）成功率。 定義為活動(dòng)查詢期間內(nèi)成功隱藏快照的數(shù)量n與所有隱藏區(qū)域數(shù)之比。成功率是衡量一個(gè)位置隱私保護(hù)算法的有效性的指標(biāo)，成功率越大，說(shuō)明隱私保護(hù)度越好[16]。其數(shù)學(xué)公式可寫(xiě)為：

（2）查詢處理時(shí)間。查詢處理時(shí)間是算法查找k-1其他用戶所需的時(shí)間。對(duì)于由n個(gè)快照組成的活動(dòng)周期的連續(xù)查詢，平均隱藏時(shí)間T avg可以計(jì)算為;

平均隱藏時(shí)間越短，說(shuō)明算法越高效。其中，TRi是查詢?cè)趨^(qū)域R中的隱藏時(shí)間。

5.2.1 參數(shù)變化對(duì)性能的影響

通過(guò)對(duì)k個(gè)用戶和l個(gè)不同段（k-l）值的隱藏區(qū)域的快照查詢，研究了本文的定義度量效果?？煺諗?shù)與查詢處理時(shí)間如圖3所示。從圖3可以看出，第一個(gè)快照的處理時(shí)間很長(zhǎng)，這是因?yàn)樘幚硇枰芏鄷r(shí)間來(lái)滿足初始隱藏條件。從最初的快照到前十個(gè)快照，查詢處理時(shí)間急劇減少，減少原因可能是隱藏用戶在初始查詢時(shí)請(qǐng)求連續(xù)服務(wù)，因?yàn)闀?huì)涉及相同的用戶，所需時(shí)間則會(huì)較少。從第10個(gè)快照到第20個(gè)快照的處理時(shí)間略有增加，這可能是由于用戶更改了路段，因此需要進(jìn)行一些處理。此后，處理時(shí)間緩慢減少，這種趨勢(shì)可能是由于引入了存儲(chǔ)庫(kù)查詢，從而減少了處理時(shí)間。一般來(lái)說(shuō)，即使k-l值增加，查詢處理時(shí)間也會(huì)隨著快照的增加而減少。

快照數(shù)與成功率的關(guān)系曲線如圖4所示。從圖4可以看出，前10個(gè)快照的匿名化成功率幾乎保持不變，這是因?yàn)橛脩粼趖i時(shí)查詢一直隱藏，因此大多數(shù)快照都符合隱藏原則。在第10個(gè)快照到第20個(gè)快照之間，成功率急劇下降，這是由于移動(dòng)對(duì)象改變了具有不同分類和不同語(yǔ)義位置的片段，因此大多數(shù)快照無(wú)法滿足隱藏條件。此后，由于逐漸引入存儲(chǔ)庫(kù)查詢，成功率穩(wěn)步提高，因此大多數(shù)查詢都滿足隱藏條件。當(dāng)k-l增加時(shí)，也出現(xiàn)類似的趨勢(shì)。一般情況下，本文算法在評(píng)估的100個(gè)快照中，每個(gè)快照的平均成功率高達(dá)為87.8%。

5.2.2 匿名器的性能對(duì)比

本節(jié)主要從匿名的查詢處理時(shí)間和匿名成功率兩方面將本文方法與 Kamenyi等人[14]提出的隱私保護(hù)算法VD-DCA方法進(jìn)行仿真實(shí)驗(yàn)比較，移動(dòng)客戶端將其隱私配置文件設(shè)置為k-l=3。

匿名器的性能對(duì)比如圖5所示。由圖5可知，在匿名器的查詢處理時(shí)間和匿名成功率上，隨著快照數(shù)增大，本文算法在所有快照值下的性能都優(yōu)于VD-DCA。因?yàn)閂D-DCA算法是基于用戶的安全特性、速度上的相似性以及采用基于最小生成樹(shù)的掩蔽機(jī)制保護(hù)用戶隱私。然而，采用基于最小生成樹(shù)的掩蔽機(jī)制會(huì)增加掩蔽時(shí)間，從而影響系統(tǒng)性能。所以在單個(gè)匿名器的查詢處理時(shí)間和成功率上，本文方法相對(duì)于Kamenyi等人[14]的VD-DCA方法有很大優(yōu)勢(shì)。

6 結(jié)束語(yǔ)

本文通過(guò)離線軌跡聚類算法和語(yǔ)義位置圖來(lái)保護(hù)用戶當(dāng)前絕對(duì)隱私，同時(shí)在真實(shí)地圖上評(píng)估算法的有效性，在整個(gè)連續(xù)查詢道路網(wǎng)絡(luò)服務(wù)的過(guò)程中，一定查詢處理時(shí)間內(nèi)取得較高的匿名成功率。然而，為了確保這些技術(shù)開(kāi)發(fā)能夠有效地工作，必須制定有利于保護(hù)用戶隱私的政策。政策發(fā)展與技術(shù)考慮同樣重要，以便做出必要改變適應(yīng)技術(shù)進(jìn)步，因此在下一步工作中將會(huì)考慮制定隱私保護(hù)政策。

參考文獻(xiàn)

[1]李志鵬. 位置隱私保護(hù)技術(shù)的研究[D]. 哈爾濱：哈爾濱理工大學(xué)，2018.

[2]PINGLEY A， ZHANG Nan， FU Xinwen， et al. Protection of query privacy for continuous location based services[C]//2011 Proceedings IEEE INFOCOM. Shanghai， China：IEEE， 2011： 1710-1718.

[3]穆良，程良倫. 基于k-匿名位置隱私保護(hù)的自適應(yīng)學(xué)習(xí)模型[J]. 計(jì)算機(jī)工程與應(yīng)用，2017，53（18）：89-94，101.

[4]TRIPATHY B K，MITRA A. An algorithm to achieve k-anonymity and l-diversity anonymisation in social networks[C]//2012 Fourth International Conference on Computational Aspects of Social Networks. Sao Carlos， Brazil：IEEE，2012：126-131.

[5]PAN Xiao， CHEN Weihang， WU Lei， et al. Protecting personalized privacy against sensitivity homogeneity attacks over road networks in mobile services[J]. Frontiers of Computer Science，2016， 10（2）： 370-386.

[6]DAMIANI M L ， SILVESTRI C， BERTINO E.Fine-grained cloaking of sensitive positions in location-sharing applications[J]. IEEE Pervasive Computing， 2011， 10（4）：64-72.

[7]LEE B， OH J， YU H， et al. Protecting location privacy using location semantics[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego， California， USA：ACM，2011： 1289-1297.

[8]曹敏姿， 張琳琳， 畢雪華，等. 個(gè)性化（[WT6BZ]α[WT6B1]，l）-多樣性k-匿名隱私保護(hù)模型[J]. 計(jì)算機(jī)科學(xué)， 2018， 45（11）：180-186.

[9]XIAO P， XING H， XIAOFENG M. Privacy preserving towards continuous query in location-based services[J]. Journal of computer research and development， 2010， 1： 18.

[10]XUE M， KALNIS P， PUNG H K. Location diversity： Enhanced privacy protection in location based services[C]//International Symposium on Location-and Context-Awareness. Berlin/ Heidelberg：Springer， 2009： 70-87.

[11]HAN B， LIU L ， OMIECINSKI E . Road-network aware trajectory clustering： Integrating locality， flow， and density[J]. Mobile Computing， IEEE Transactions on， 2015， 14（2）：416-429.

[12]GUSTAV Y H ， WANG Y ， KAMENYI D M，et al. Query privacy preservation in location based services on road networks[J]. Journalof Computational Information Systems， 2014，10（12）：5255-5263.

[13]黎孟. 基于語(yǔ)義多樣性的位置隱私保護(hù)算法研究[D]. 長(zhǎng)沙：湖南大學(xué)，2018.

[14]Figshare.[2018-12-06]. https：//figshare.com/articles/Urban_Road_Network_Data/2061897.

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

[16]KAMENYI D M， WANG Yong， ZHANG Fengli， et al. Authenticated privacy preserving for continuous query in location based services[J]. Journal of Computational Information Systems， 2013， 9（24）：9857-9864.

基金項(xiàng)目： 上海市信息安全綜合管理技術(shù)研究重點(diǎn)實(shí)驗(yàn)室開(kāi)放研究課題基金（AGK2019004）。

作者簡(jiǎn)介： 賈媛媛（1995-），女，碩士研究生，主要研究方向：隱私保護(hù)、網(wǎng)絡(luò)信息安全; 史志才（1964-），男，博士，教授，CCF高級(jí)會(huì)員（No.06601S），主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與信息安全、隱私保護(hù)。

收稿日期： 2021-04-06