俞望年，宣占祥，馬小明，岳威，左開中,2

（1.安徽師范大學(xué)計(jì)算機(jī)與信息學(xué)院，蕪湖 241002；2.安徽師范大學(xué)網(wǎng)絡(luò)與信息安全安徽省重點(diǎn)實(shí)驗(yàn)室，蕪湖 241002）

0 引言

近年來，隨著移動(dòng)智能設(shè)備的普及和定位技術(shù)的發(fā)展，人們的海量軌跡數(shù)據(jù)被收集、存儲(chǔ)、挖掘和分析[1-4]。然而軌跡數(shù)據(jù)含有大量的個(gè)人隱私信息，例如社會(huì)身份、家庭住址、身體健康狀況、工作場所以及日常行程等，若不經(jīng)處理直接發(fā)布軌跡數(shù)據(jù)，將會(huì)泄露個(gè)人隱私信息[5-6]。因此，如何保證發(fā)布的軌跡數(shù)據(jù)具有較高數(shù)據(jù)可用性的同時(shí)，保護(hù)用戶的敏感隱私信息，已成為國內(nèi)外學(xué)者關(guān)注的熱點(diǎn)。

常用的軌跡隱私保護(hù)方法有K 匿名法[7-10]、假軌跡法[11-12]、抑制法[13-14]和差分隱私法[15-16]。文獻(xiàn)[7]提出（K，δ）-隱私保護(hù)算法，利用軌跡數(shù)據(jù)不確定性進(jìn)行軌跡聚類，對(duì)軌跡位置進(jìn)行隱私保護(hù)。文獻(xiàn)[8]利用網(wǎng)格技術(shù)對(duì)軌跡位置點(diǎn)進(jìn)行空間泛化以滿足K 匿名，進(jìn)而將軌跡轉(zhuǎn)換為連續(xù)網(wǎng)格序列。文獻(xiàn)[9]認(rèn)為并非軌跡上的所有采樣位置都要進(jìn)行匿名處理，通過停留位置提取算法獲取軌跡數(shù)據(jù)中的停留位置，再利用網(wǎng)格劃分技術(shù)和K 匿名構(gòu)建匿名區(qū)域，進(jìn)一步保護(hù)用戶敏感隱私信息。文獻(xiàn)[10]利用挖掘到的真實(shí)興趣點(diǎn)數(shù)據(jù)，提出（K，L）-隱私模型，利用網(wǎng)格劃分技術(shù)為停留位置構(gòu)建匿名區(qū)域，使得匿名區(qū)域滿足K 匿名和L 語義差異性。文獻(xiàn)[11]通過計(jì)算虛假軌跡和真實(shí)軌跡的K 個(gè)交叉點(diǎn)，隨機(jī)生成交叉點(diǎn)間軌跡。文獻(xiàn)[12]隨機(jī)選擇軌跡采樣位置點(diǎn)，將用戶真實(shí)軌跡進(jìn)行不同角度旋轉(zhuǎn)生成潛在虛假軌跡。文獻(xiàn)[13]通過對(duì)軌跡數(shù)據(jù)中的敏感或者頻繁訪問位置進(jìn)行抑制處理，保護(hù)隱私信息。文獻(xiàn)[14]提出一種基于單點(diǎn)收益的軌跡隱私保護(hù)方法，通過計(jì)算收益結(jié)果，在軌跡數(shù)據(jù)集中抑制位置或者添加假軌跡，減少信息損失率。文獻(xiàn)[15]利用隱馬爾科夫模型度量用戶位置相關(guān)性，通過設(shè)計(jì)滿足差分隱私的拉布拉斯噪聲機(jī)制保護(hù)用戶隱私信息。文獻(xiàn)[16]利用四叉樹和R樹數(shù)據(jù)結(jié)構(gòu)，提出兩種滿足差分隱私的軌跡數(shù)據(jù)發(fā)布方法。然而，這些方法存在信息損失率過大導(dǎo)致的數(shù)據(jù)可用性較低問題，同時(shí)沒有充分考慮用戶所處語義位置信息，存在語義推斷攻擊[17-18]，導(dǎo)致用戶敏感隱私泄露。

基于此，本文提出一種基于敏感語義位置的軌跡數(shù)據(jù)隱私保護(hù)算法，通過對(duì)用戶敏感的語義位置進(jìn)行匿名處理，構(gòu)建語義安全匿名區(qū)域，提高位置隱私保護(hù)程度，同時(shí)減少對(duì)非敏感語義位置的匿名處理，降低信息損失率，提高軌跡數(shù)據(jù)可用性。

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

1.1 相關(guān)定義

定義1（語義位置）是指具有坐標(biāo)、語義位置類型（如學(xué)校、商場等）和流行度等特征的位置，記為loc={address，type，（lon，lat），P（loc）}。其中：address 為語義地址；type 表示語義位置類型；（lon，lat）表示語義位置經(jīng)緯度；P（loc）表示語義位置流行度。本文根據(jù)地理標(biāo)簽將語義位置類型分為10 種，如圖1 所示。此外，語義位置是否敏感由用戶定義，例如醫(yī)院，部分患者認(rèn)為是敏感的，醫(yī)生則認(rèn)為是非敏感的。

圖1 語義位置地理標(biāo)簽分類

定義2（語義位置流行度）是指用戶訪問該語義位置的概率。 設(shè) loc 是一個(gè)語義位置，U(loc)={u1,u2,…,um} 是訪問過該語義位置的用戶集合，并設(shè)nj是用戶uj對(duì)loc 的訪問次數(shù)，該語義位置被訪問的總數(shù)記為因此該語義位置的流行度定義為P(loc)=2H(loc)，其中：它表示該語義位置的信息熵，即被用戶訪問的可能性。

圖2 語義位置Voronoi圖

定義3（語義位置Voronoi 圖）是指以語義位置為生成元構(gòu)建的Voronoi 圖，如圖2 所示。每個(gè)語義位置的 Voronoi 單 元 滿 足Voronoi(loci)={x：d(x,loci)≤d(x,locj),loci≠locj}，其中：d（x，loci）表示 x 到語義位置 loci的歐式距離；x 表示任意位置。

定義4（語義軌跡）是指將原始軌跡上的采樣位置按時(shí)間順序語義化為移動(dòng)對(duì)象停留位置序列，記為其中：表示第 i 個(gè)用戶身份標(biāo)識(shí)符，表示STi的第j 個(gè)停留位置。為了簡便，系統(tǒng)會(huì)自動(dòng)將停留位置轉(zhuǎn)化為最近鄰語義位置。

定義5（隱私需求）是指用戶的隱私保護(hù)需求，記為PR={θ,senstype}，其中：θ表示用戶定義的語義安全閾值；senstype 表示用戶定義的敏感語義位置類型集。

定義6（匿名區(qū)域）是指一個(gè)用來隱藏用戶語義位置的空間區(qū)域，記為CR={Voronoi(loc1),…,Voronoi(loci),...,Voronoi(locm)}，其中：ioVoronoi(loci)表示語義位置loci所處的Voronoi 單元。

定義7（θ-語義安全匿名區(qū)域）已知一個(gè)匿名區(qū)域CR 和一個(gè)用戶u，CR 中屬于u 的敏感語義位置用senslocsu表示，則匿名區(qū)域敏感語義位置總流行度記為POP（senslocsu），匿名區(qū)域語義位置總流行度記為POP（all），匿名區(qū)域語義安全程度用d（CR）表示：

若匿名區(qū)域的語義安全程度d(CR)≤u.PR.θ，我們就稱CR 對(duì)用戶u 來說是一個(gè)θ-語義安全匿名區(qū)域。

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

本文系統(tǒng)架構(gòu)如圖3 所示。

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

該架構(gòu)包括客戶端、軌跡收據(jù)收集服務(wù)器、原始軌跡數(shù)據(jù)庫、隱私保護(hù)算法服務(wù)器、可發(fā)布軌跡數(shù)據(jù)庫4個(gè)組件?？蛻舳素?fù)責(zé)記錄用戶軌跡數(shù)據(jù)，并將記錄的軌跡數(shù)據(jù)發(fā)送給軌跡數(shù)據(jù)收集服務(wù)器，軌跡數(shù)據(jù)收集服務(wù)器接收客戶端發(fā)送的軌跡數(shù)據(jù)，原始軌跡數(shù)據(jù)庫存儲(chǔ)軌跡數(shù)據(jù)收集服務(wù)器接收到的軌跡數(shù)據(jù)，隱私保護(hù)算法服務(wù)器對(duì)原始軌跡數(shù)據(jù)進(jìn)行停留位置提取、匿名區(qū)域生成和軌跡匿名處理處理，匿名后的數(shù)據(jù)存儲(chǔ)在可發(fā)布軌跡數(shù)據(jù)庫中。

2 基于敏感語義位置的軌跡數(shù)據(jù)隱私保護(hù)算法

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

本文充分考慮用戶的隱私需求和軌跡數(shù)據(jù)可用性問題，提出一種基于敏感語義位置的軌跡數(shù)據(jù)隱私保護(hù)算法，主要思想如圖4 所示。

圖4 算法流程圖

具體步驟如下：

（1）利用語義位置進(jìn)行Voronoi 圖劃分。

（2）從原始軌跡的采樣位置數(shù)據(jù)中提取用戶停留位置。

（3）若停留位置處于非敏感語義位置的Voronoi 單元中，則不進(jìn)行匿名處理；若處于敏感語義位置的Voronoi 單元中，則將該Voronoi 單元加入匿名區(qū)域，執(zhí)行步驟（4）。

（4）遍歷所有與匿名區(qū)域相鄰近的語義位置，根據(jù)用戶設(shè)置的敏感語義位置類型，優(yōu)先添加流行度最大的非敏感語義位置，其次選擇流行度最小的敏感語義位置。

（5）將該語義位置對(duì)應(yīng)的Voronoi 單元加入匿名區(qū)域，若匿名區(qū)域語義安全程度滿足用戶設(shè)定的語義安全閾值，返回該匿名區(qū)域；否則，執(zhí)行步驟（4）。

算法1 給出了基于敏感語義位置的軌跡數(shù)據(jù)隱私保護(hù)算法（Sensitive Semantic Location Privacy Protection Algorithm for Trajectory Data，SSLPP）的偽代碼。首先將原始軌跡traj 轉(zhuǎn)換為語義軌跡ST（第3 行），遍歷ST 中的每一個(gè)停留的語義位置loc（第4 行），若處在敏感語義位置（第5 行），將該語義位置所在Voronoi 單元加入匿名區(qū)域（第6 行）；其次根據(jù)PR.senstype 添加匿名區(qū)域鄰近Voronoi 單元，直至滿足語義安全閾值（第7-16行），并用該匿名區(qū)域替換loc（第17 行）；然后掃描原始軌跡traj 中的每一個(gè)采樣位置，將敏感的停留位置轉(zhuǎn)換為ST 中的相應(yīng)匿名區(qū)域，同時(shí)若有采樣位置被ST 中的相應(yīng)匿名區(qū)域覆蓋，則使用該匿名區(qū)域替代采樣位置，形成可安全發(fā)布的軌跡traj*，并將traj*放入軌跡數(shù)據(jù)庫 D*（第 20-21 行）；最后返回 D*（第 23 行）。

算法1 基于敏感語義位置的軌跡隱私保護(hù)算法

輸入：語義位置Voronoi 圖、原始軌跡數(shù)據(jù)庫D、隱私需求PR

輸出：可發(fā)布的軌跡數(shù)據(jù)庫D*

1）D*=? ；

2）For traj∈Ddo

3）轉(zhuǎn)換為語義軌跡ST={loc1,loc2,...,locn}；

4）Forloc∈STdo

5） Ifloc.type∈PR.senstypethen

6）CR=GetVoronoi(loc)；∕∕獲 取 loc 所 在 Voronoi單元

7） While（d(CR)>PR.θ）do

8）NSset=GetNSLinks(CR,PR.senstype)；∕∕記錄非敏感語義位置

9）SNset=GetSNLinks(CR,PR.senstype)；∕∕記 錄 敏感語義位置

10） IfNSset≠ ? then

11）loclink=SelectMaxpop(NSset)；∕∕選擇流行度最大的語義位置

12） Else

13）loclink=SelectMinpop(SNset)；∕∕選擇流行度最小的語義位置

14） End if

15）CR=CR?Voronoi(loclink)；

16） End while

17） 用 CR 替換 loc；

18）End if

19）End for

20）根據(jù) ST 將 traj 轉(zhuǎn)換為 traj*；

21）D*=D*?traj*；

22）End for

23）Return D*；

2.2 算法分析

在軌跡數(shù)據(jù)發(fā)布中，真正泄露用戶隱私的是用戶停留的語義位置。因此，SSLPP 算法在此基礎(chǔ)上，考慮到用戶對(duì)不同語義位置的訪問具有差異性，利用真實(shí)數(shù)據(jù)計(jì)算各語義位置流行度。充分考慮用戶的隱私需求，根據(jù)用戶設(shè)置的敏感語義位置類型和語義安全閾值對(duì)停留的語義位置進(jìn)行有選擇的構(gòu)建θ-語義安全匿名區(qū)域，保護(hù)用戶敏感隱私信息。因?yàn)楫?dāng)用戶處于敏感語義位置時(shí)，構(gòu)建的匿名區(qū)域CR 至少還包含一個(gè)非敏感語義位置，這是因?yàn)槿魶]有非敏感語義位置，CR的語義安全程度d（CR）=1，無法滿足用戶設(shè)置的θ閾值，因此增加攻擊者推測用戶敏感隱私信息的難度。

在軌跡數(shù)據(jù)可用性方面，SSLPP 算法使用信息損失率[19]來進(jìn)行衡量，計(jì)算公式如下：

其中：ILAave表示停留位置轉(zhuǎn)化為匿名區(qū)域后的平均信息損失率；n 表示軌跡條數(shù)，m 表示每條軌跡上的采樣位置數(shù)，Asp 表示所有軌跡上的采樣位置數(shù)，Area（Zone（Ti，Sampij））表示第i 條軌跡的第j 個(gè)采樣位置所屬的匿名區(qū)域面積。信息損失率越低，數(shù)據(jù)可用性越高；反之，數(shù)據(jù)可用性越差。由于SSLPP 算法僅針對(duì)用戶敏感的停留位置進(jìn)行隱私保護(hù)，減少匿名處理規(guī)模。因此，SSLPP 算法可以降低信息損失率，提高軌跡數(shù)據(jù)可用性。

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

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

本文對(duì)比了文獻(xiàn)[7]的（K，δ）算法、文獻(xiàn)[9]的 Grid-Partition 算法和文獻(xiàn)[10]的 SSAC 算法。其中：（K，δ）算法是對(duì)軌跡數(shù)據(jù)中的所有采樣位置進(jìn)行匿名處理，K 默認(rèn)設(shè)置為 6，δ取值為 500，1000，1500，2000；GridPartition算法對(duì)軌跡數(shù)據(jù)中的停留位置進(jìn)行K 匿名處理，K 默認(rèn)設(shè)置為6；SSAC 算法對(duì)軌跡數(shù)據(jù)中的停留位置進(jìn)行（K，L）匿名處理，K 默認(rèn)設(shè)置為 6，L 默認(rèn)設(shè)置為 3。

所有的匿名算法均用Java 實(shí)現(xiàn)，并運(yùn)行在一臺(tái)配置為 Intel Core i5-4200M CPU@2.5GHz，12GB 內(nèi)存的Windows 10 計(jì)算機(jī)上。實(shí)驗(yàn)數(shù)據(jù)采用北京PoI（Point of Interest）數(shù)據(jù)[10]作為語義位置，敏感語義位置類型設(shè)置為{休閑娛樂，住宿，科教文化}，隨機(jī)選取Geolife 數(shù)據(jù)[9]中 100 個(gè)用戶的 10129 條軌跡，共計(jì) 16021938 個(gè)采樣位置。經(jīng)過停留位置提取算法[9]后得到27116 個(gè)停留位置，具體分布如圖5 所示。表1 列出了實(shí)驗(yàn)參數(shù)具體信息。

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

圖5 停留位置可視化

圖6 θ值變動(dòng)

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

（1）θ值變動(dòng)的影響

圖6 描述θ值變動(dòng)對(duì)信息損失率和運(yùn)行時(shí)間的影響，其中語義位置數(shù)為50000，敏感語義位置類型為{休閑娛樂，住宿，科教文化}。由于（K，δ）算法、GridPartition 算法和SSAC 算法不考慮語義安全性，因此只對(duì)SSLPP 算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。

由圖 6（a）可知，隨著θ值的增加，SSLPP 算法的信息損失率不斷降低，這是因?yàn)棣戎翟龃?，?gòu)建語義安全匿名區(qū)域需要添加的相鄰語義位置越少，使得匿名區(qū)域面積相應(yīng)減小，降低信息損失率。

由圖 6（b）可知，隨著θ值的增加，SSLPP 算法的執(zhí)行時(shí)間不斷減少，這是因?yàn)棣戎翟龃?，匿名區(qū)域擴(kuò)展添加Voronoi 單元次數(shù)逐漸減少，降低算法執(zhí)行時(shí)間。

（2）敏感語義位置類型數(shù)量的影響

圖7 描述敏感語義位置類型數(shù)量的變動(dòng)對(duì)信息損失率和運(yùn)行時(shí)間的影響，其中語義位置數(shù)量為50000，θ值為0.6。

由圖7（a）可知，隨著敏感語義位置類型數(shù)量的增加，SSLPP 算法的信息損失率不斷增加，但始終低于（K，δ）算法、GridPartition 算法和 SSAC 算法。這是因?yàn)槊舾姓Z義位置類型數(shù)量增多，SSLPP 算法需要匿名處理的停留位置增多，相應(yīng)信息損失率逐漸增加。但GridPartition 算法和SSAC 算法對(duì)所有停留位置進(jìn)行匿名處理區(qū)域；（K，δ）算法是對(duì)軌跡數(shù)據(jù)中的所有采樣位置進(jìn)行匿名處理，因此信息損失率始終高于SSLPP算法。

由圖7（b）可知，隨著敏感語義位置類型數(shù)量的增加，SSLPP 算法匿名時(shí)間不斷增加，但始終低于（K，δ）算法、GridPartition 算法和 SSAC 算法。這是因?yàn)镾SLPP 算法僅對(duì)停留的敏感語義位置進(jìn)行匿名處理，減少匿名處理規(guī)模，減少算法運(yùn)行時(shí)間。

（3）語義位置數(shù)量的影響

圖8 描述語義位置數(shù)量的變動(dòng)對(duì)信息損失率，其中敏感語義位置類型為{休閑娛樂，住宿，科教文化}，θ值為0.6。

由圖8 可知，隨著語義位置數(shù)量的增加，SSLPP 算法信息損失率不斷降低，且始終低于（K，δ）算法、Grid-Partition 算法和SSAC 算法。這是因?yàn)檎Z義位置數(shù)量越多，非敏感語義位置數(shù)量相應(yīng)增加，使得擴(kuò)展添加Voronoi 單元次數(shù)減少，縮減匿名區(qū)域面積，從而降低信息損失率。（K，δ）算法不考慮語義位置，因此信息損失率不受語義位置數(shù)量變化的影響。隨著語義位置數(shù)量的增加，GridPartition 算法和SSAC 算法信息損失率不斷降低，但降低幅度較小。

4 結(jié)語

本文針對(duì)利用軌跡數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘的場景，提出一種基于敏感語義位置的軌跡隱私保護(hù)算法。該算法根據(jù)移動(dòng)對(duì)象設(shè)置的敏感語義位置類型和語義安全閾值對(duì)停留位置進(jìn)行泛化處理，不僅可以避免語義推斷攻擊，而且可以降低信息損失率，從而提高軌跡數(shù)據(jù)可用性和敏感隱私信息保護(hù)程度。

圖7 敏感語義位置類型數(shù)量變動(dòng)

圖8 語義位置數(shù)量變動(dòng)

然而，本文算法沒有充分考慮城市交通路網(wǎng)和語義位置的時(shí)間維度。因此，下一階段的研究可以結(jié)合城市路網(wǎng)和時(shí)間維度構(gòu)建匿名區(qū)域，進(jìn)一步增強(qiáng)隱私保護(hù)程度。