張偉媛　湯文兵　陳彥杰

摘 要：移動(dòng)計(jì)算設(shè)備的快速發(fā)展導(dǎo)致了基于位置的服務(wù)（LBS）得到了各領(lǐng)域的應(yīng)用，但同時(shí)給用戶隱私安全帶來威脅。針對用戶位置信息上傳共享第三方的問題，提出了融合聚類與差分隱私的位置保護(hù)方案。首先，根據(jù)位置信息的密集程度將周邊位置點(diǎn)進(jìn)行排序劃分，采用k-means聚類對其進(jìn)行泛化處理；在滿足地理不可區(qū)分性的前提下通過平面拉普拉斯機(jī)制對簇中心進(jìn)行加噪，得到每個(gè)位置點(diǎn)的擾動(dòng)位置，進(jìn)而保護(hù)位置隱私。實(shí)驗(yàn)結(jié)果證明，在保障位置隱私安全的前提下，本文算法具有更高的數(shù)據(jù)利用率。

關(guān)鍵詞：差分隱私；k-means聚類；位置隱私；基于位置的服務(wù)

中圖分類號：TP309.2? 文獻(xiàn)標(biāo)識碼：A? 文章編號：1673-260X（2023）11-0001-05

1 引言

傳感器和移動(dòng)設(shè)備的快速發(fā)展在市場上為用戶提供了廣泛的選擇，便利了用戶的生活。然而，這些設(shè)備的處理和存儲能力會導(dǎo)致用戶一些隱私信息的泄漏。例如使用基于位置的服務(wù)LBS會獲取用戶的位置信息[1]。用戶將準(zhǔn)確的位置信息上傳到LBS以獲得相應(yīng)的服務(wù)，但上傳未經(jīng)處理的位置數(shù)據(jù)將直接導(dǎo)致用戶隱私信息泄露。訂外賣、外出交通或與其他用戶會面，必須將他們的位置發(fā)布到LBS服務(wù)器，這些被收集的位置信息將有可能會暴露有關(guān)用戶的一些基本信息，利用這些信息，廣告商可以推送廣告，犯罪分子也可能進(jìn)行犯罪活動(dòng)[2]。用戶一些敏感位置信息的泄露可能對其造成大量損失，保護(hù)用戶的信息安全，建立安全有效的模型已經(jīng)成為當(dāng)前研究的重點(diǎn)。

關(guān)于LBS隱私保護(hù)方案國內(nèi)外已經(jīng)有大量研究成果[3-6]。Song等人提出了一種基于雙線性配對理論和k-匿名性的改進(jìn)隱私保護(hù)方案，根據(jù)位置信息選擇最佳假位置，從而實(shí)現(xiàn)隱私保護(hù)[7]。隨后，Zhang等人提出了一種新的基于地理語義的位置隱私保護(hù)方法，同時(shí)滿足k-匿名性，其中使用最大和最小距離多中心聚類算法構(gòu)建候選集，并根據(jù)其語義相似性生成虛擬位置結(jié)果集[8]。然而l-多樣性和k-匿名的概念受到數(shù)據(jù)分布和背景知識攻擊的極大限制，因此隱私保護(hù)的程度無法得到很好的保證。除上述方法外，LBS隱私保護(hù)結(jié)構(gòu)主要包括位置樹結(jié)構(gòu)、馬爾可夫模型和聚類。位置樹的主要思想是根據(jù)一定的規(guī)則構(gòu)造樹結(jié)構(gòu)，引用前綴樹和差分隱私來保護(hù)軌跡數(shù)據(jù)隱私，樹的節(jié)點(diǎn)用于存儲軌跡段[9]。馬爾可夫模型主要用于模擬用戶實(shí)際位置之間的時(shí)間相關(guān)性，并根據(jù)每個(gè)位置的轉(zhuǎn)移概率預(yù)測下一個(gè)可能的位置[10]。聚類可以展現(xiàn)用戶在一定時(shí)間內(nèi)的活動(dòng)規(guī)則，去除訪問頻率較低的位置，因此具有很高的靈活性。Tareqd等人提出了一種基于密度網(wǎng)格的在線數(shù)據(jù)流聚類方法，采用基于網(wǎng)格的方法來減少距離函數(shù)的調(diào)用次數(shù)，從而提高聚類質(zhì)量[11]。Sabarish等人提出了一種基于圖形的軌跡數(shù)據(jù)表示模型，使用基于邊和頂點(diǎn)的測量方法計(jì)算軌跡之間的相似度，并基于路徑對相似軌跡進(jìn)行聚類和識別從而對位置隱私提供了隱私保障[12]。

為了最大化查詢結(jié)果的準(zhǔn)確性，提高算法的效率，在滿足差分隱私的條件下本文提出一種融合聚類與差分隱私的位置隱私算法。將差分隱私與k-means聚類算法相結(jié)合，選取聚類集合的質(zhì)心點(diǎn)，使用平面拉普拉斯機(jī)制對其進(jìn)行處理得到擾動(dòng)位置，并使用擾動(dòng)位置代替原始位置進(jìn)行查詢。本文的貢獻(xiàn)有兩個(gè)方面。

（1）本文結(jié)合k-means聚類和差分隱私提出了可以有效保護(hù)用戶位置隱私的機(jī)制。

（2）使用真實(shí)數(shù)據(jù)集測試所提出方案的效率和有效性，驗(yàn)證本文提出的算法優(yōu)于其他算法，數(shù)據(jù)可用性得到了較好的提高。

2 定義及相關(guān)概念

2.1 差分隱私

2.1.1 差分隱私定義

2.1.2 隱私保護(hù)預(yù)算

參數(shù)ε稱為隱私預(yù)算。如公式（1）所示，較小的ε會使算法M生成的查詢結(jié)果的概率分布在一對相鄰的數(shù)據(jù)集上越相似，攻擊者更難判斷數(shù)據(jù)集中是否存在某個(gè)元素。隱私保護(hù)的程度會更高。因此，ε的值通常要與具體的要求結(jié)合，以完成結(jié)果的隱私性和利用率之間的平衡。

2.1.3 敏感度

2.2 地理不可區(qū)分性

差分隱私通常用于數(shù)據(jù)聚合問題中的隱私保護(hù)，使攻擊者無法確定元素是否屬于某個(gè)數(shù)據(jù)集。考慮到某一地理空間中特定位置數(shù)據(jù)點(diǎn)的隱私保護(hù)，引用地理不可區(qū)分的機(jī)制，此機(jī)制擴(kuò)展差分隱私到地理位置數(shù)據(jù)，并將差分隱私中相鄰數(shù)據(jù)集的概念轉(zhuǎn)換為兩個(gè)地理上接近的位置。當(dāng)兩個(gè)相鄰位置彼此靠近時(shí)，它們生成相同查詢位置的概率相似。因此，攻擊者無法根據(jù)用戶提交的查詢位置來確定用戶的真實(shí)位置。具體定義如下：

其中，參數(shù)ε是單位距離的隱私預(yù)算，εr代表半徑為r的任意圓內(nèi)的隱私預(yù)算。從公式（3）中可以看出，εr越小，同一輸出位置的概率分布越相似，攻擊者就越難判斷用戶的真實(shí)位置，隱私保護(hù)程度越高。同樣，通過在真實(shí)位置點(diǎn)上添加拉普拉斯噪聲來實(shí)現(xiàn)地理上的不可辨性，用戶的真實(shí)位置被保護(hù)在一個(gè)半徑為r的圓內(nèi)。

2.3 實(shí)現(xiàn)機(jī)制

2.4 k-means聚類

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

針對位置隱私保護(hù)機(jī)制數(shù)據(jù)利用率低問題，本文將k-means聚類加入差分隱私位置保護(hù)機(jī)制中。該機(jī)制能夠很好地保護(hù)單個(gè)位置的隱私，并通過k-means算法和差分隱私性使擾動(dòng)位置與真實(shí)位置相似，從而提高位置數(shù)據(jù)的可用性。其基本思想如下，對于每個(gè)位置點(diǎn)，將距離小于r的興趣點(diǎn)劃入該位置所在的聚類簇。該算法使用聚類中心點(diǎn)來代表一定距離內(nèi)的用戶活動(dòng)區(qū)域，區(qū)域內(nèi)的其他位置點(diǎn)被移除，以避免位置冗余。最后，為了進(jìn)一步保護(hù)用戶的隱私，原始位置被質(zhì)心所取代[14]。

3.1 位置點(diǎn)預(yù)處理模塊

3.2 位置數(shù)據(jù)聚類模塊

3.3 算法安全性分析

4 實(shí)例分析

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

實(shí)驗(yàn)所用硬件環(huán)境為11th Gen Intel（R） Core（TM） i5 2.40GHz，16GB內(nèi)存，使用python編程語言實(shí)現(xiàn)，操作系統(tǒng)平臺為Windows10。使用的數(shù)據(jù)集為Gowalla，一個(gè)收集位置數(shù)據(jù)的社交網(wǎng)絡(luò)，允許用戶通過簽到來分享他們的位置。該數(shù)據(jù)集使用公共API收集信息，具有196591個(gè)站點(diǎn)和950327個(gè)域，并在2009年2月至2010年10月時(shí)間范圍內(nèi)收集了用戶的6442890次簽到。

4.2 實(shí)驗(yàn)分析

本文采用MSE衡量數(shù)據(jù)可用性，對比了單純使用差分隱私算法的數(shù)據(jù)可用性，分析了隱私預(yù)算ε對數(shù)據(jù)利用率的影響，其中誤差越低，代表數(shù)據(jù)可用性越高，隱私預(yù)算ε對算法誤差的影響分析如圖1所示。

根據(jù)拉普拉斯概率密度函數(shù)推斷，隱私保護(hù)程度隨ε的增加而降低，該實(shí)驗(yàn)結(jié)果也反映了這一理論。而且從實(shí)驗(yàn)結(jié)果中不難看出本文算法的隱私保護(hù)程度較好于傳統(tǒng)的差分隱私算法，這是由于k-means聚類生成了一個(gè)質(zhì)心，所有位置都被一個(gè)唯一的質(zhì)心替換，因此本文的隱私保護(hù)程度更好，數(shù)據(jù)可用性更高。

圖2則分析了待保護(hù)位置的數(shù)量N對隱私保護(hù)程度的影響，從實(shí)驗(yàn)結(jié)果中可以看出隱私保護(hù)程度隨著待保護(hù)位置數(shù)量N的減少而增加。N越大，隱私保護(hù)程度越差。同樣，對比傳統(tǒng)的差分隱私方法，可以看出本文算法的數(shù)據(jù)可用性更高。

5 總結(jié)

本文針對位置數(shù)據(jù)中的隱私問題提出了一種新的解決方案，設(shè)計(jì)了一個(gè)融合k-means聚類與差分隱私的算法來干擾用戶的位置數(shù)據(jù)。通過理論分析與實(shí)驗(yàn)證明，本文算法能夠在有效保護(hù)用戶數(shù)據(jù)安全性的同時(shí)提高數(shù)據(jù)的利用率。

參考文獻(xiàn)：

〔1〕姜海洋，曾劍秋，韓可，等.5G環(huán)境下移動(dòng)用戶位置隱私保護(hù)方法研究[J].北京理工大學(xué)學(xué)報(bào)，2021， 41（01）：84-92.

〔2〕楊洋，王汝傳.增強(qiáng)現(xiàn)實(shí)中基于位置安全性的LBS位置隱私保護(hù)方法[J].計(jì)算機(jī)應(yīng)用，2020，40（05）：1364-1368.

〔3〕XIONG J B， REN J， CHEN L， et al. Enhancing privacy and availability for data clustering in intelligent electrical service of IoT， IEEE Internet of Things Journal， 2019， 6（02）：1530-1540.

〔4〕XIONG J B， MA R， CHEN L， et al. A personalized privacy protection framework for mobile crowdsensing in IIoT， IEEE Transactions on Industrial Informatics， 2020， 16（06）：4231-4241.

〔5〕HE J S， Du J H， ZHU N F. Research on k-anonymity Algorithm for Personalized Quasi-identifier Attributes [J]. Information network security， 2020， 20（10）：19-26.

〔6〕LIU Q， YU J， HAN J， et al. Differentially private and utility-aware publication of trajectory data[J]. Expert Systems with Applications， 2021， 180（07）：115120.

〔7〕SONG C， ZHANG YD， WANG L， et al. Research on k-anonymity privacy protection scheme based on bilinear pairings [J]. The Journal of China Universities of Posts and Telecommunications， 2018， 25（05）：12-19.

〔8〕ZHANG Y B， ZHANG Q Y， LI Z Y， et al. A k-anonymous Location Privacy Protection Method of Dummy Based on Geographical Semantics [J]. International Journal of Network Security， 2019， 21（06）：937-946.

〔9〕ZHAO X， PI D， CHEN J. Novel trajectory privacy-preserving method based on prefix tree using differential privacy [J]. Knowledge-Based Systems， 2020， 198（05）：105940.

〔10〕YUAN T A， MMK A， MAR A， et al. A privacy preserving location service for cloud-of-things system-Science Direct [J]. Journal of Parallel and Distributed Computing， 2019， 123： 215-222.

〔11〕TAREQ M， SUNDARARAJAN E A， MOHD M， et al. Online clustering of evolving data streams using a density grid-based method.IEEE Access 2020， 8， 166472-166490.

〔12〕SABARISH BA， KARTHI R， KUMAR T G. Graph Similarity-based Hierarchical Clustering of Trajectory Data [J]. Procedia Computer Science， 2020， 171：32-41.

〔13〕SINAGA K P， YANG M S. Unsupervised K-means clustering algorithm[J]. IEEE access， 2020， 8： 80716-80727.

〔14〕任曉宇.基于差分隱私的位置隱私保護(hù)技術(shù)研究[D].山西師范大學(xué)，2021.