基于差分隱私的LBS用戶位置隱私保護方案

于乃文 楊少杰 陳振國 張光華

摘 要：為了兼顧共享位置數據的可用性和隱私保護需求，針對第三方收集的用戶共享位置信息，提出了一種基于差分隱私的LBS用戶位置隱私保護方案。首先，對共享位置數據集進行預處理，使用字典查詢方式構建位置事務數據庫，采用Trie樹結構存儲位置數據和頻率，提高查詢效率，減少加噪次數;其次，在Trie樹上進行頻繁位置選取，并使用差分隱私下的拉普拉斯機制擾動位置頻率;最后，基于向上后置處理和一致性約束后置處理2種技術對擾動后的數據進行優化，并通過理論證明所提方案滿足ε-差分隱私。結果表明，與已有方法相比，差分隱私保護方案提高了數據處理效率，泛化了敏感位置同時具有較高的精確率和較低的拒真率。所提方案能夠有效保護用戶的位置隱私，同時在共享位置數據可用性方面具有一定的參考價值。

關鍵詞：數據安全與計算機安全;位置數據;隱私保護;差分隱私;可用性

中圖分類號：TP309.2 文獻標識碼：A

doi：10.7535/hbkd.2021yx03003

Location privacy protection scheme for LBS users based on differential privacy

YU Naiwen1， YANG Shaojie1， CHEN Zhenguo2， ZHANG Guanghua1，3

（1.School of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang，Hebei 050018，China;

2.Hebei Engineering Technology Research Center for IoT Data Acquisition & Processing，North China Institute of Science and Technology，Langfang，Hebei 065201，China;

3.State Key Laboratory of Integrated Services Networks，Xidian University，Xi'an，Shaanxi 710071，China）

Abstract：In order to take into account the availability of shared location data and privacy protection requirements，aiming at the shared location information collected by the third party，a location privacy protection scheme of LBS users was proposed based on differential privacy.Firstly，the shared location data set was preprocessed，the dictionary query mode was used to build the location transaction database，and the trie tree structure was adopted to store the location data and frequency，so as to improve the query efficiency and reduce the number of noise.Secondly，frequent location selection was carried out in the Trie tree，and Laplacian mechanism under differential privacy was used to disturb the location frequency.Finally，the perturbed data was optimized based on the two techniques of upward post-processing and consistency constrained post-processing，and theoretically prove that the proposed scheme satisfies ε-differential privacy.The experimental results show that，compared with the existing methods，this scheme improves the efficiency of data processing，generalizes the sensitive locations，and has higher accuracy and lower rejection rate.This scheme has a certain reference value in user location privacy protection and shared location data availability.

Keywords：

data security and computer security;location data;privacy protection;differential privacy;availability

隨著GPS、無線通信等技術的飛速發展，基于位置服務（LBS，location-based service）[1]給人們的生活起居、外出工作和社交活動帶來了巨大變化。用戶通過智能設備從應用商店可以下載基于位置的應用程序，如百度地圖、谷歌地圖等，在提交的位置信息和查詢內容基礎上獲取所需的服務數據[2]。功能多樣化的LBS應用遍及人們的日常生活，其應用場景主要有導航服務、社交網絡服務、興趣點推薦服務。然而，位置服務給用戶帶來諸多便利的同時，各種隱私泄露問題也層出不窮[3-4]。服務器獲取了用戶所使用的位置信息，進一步分析用戶的居住地點、身體狀況和日常行為規律，甚至跟蹤用戶，并將用戶信息發布給第三方[5]。相對于LBS應用提供的便利，用戶更關注個人的隱私安全。個人隱私保護水平影響用戶使用LBS應用的積極性，因此設計強有力的位置隱私保護機制顯得尤為重要。

首先，現有的LBS用戶位置隱私保護機制大都通過K匿名模型[6]的擴展達到保護位置隱私的目的。然而匿名是從外部保護用戶的身份而非用戶位置信息本身，所以在背景知識攻擊下會造成用戶個人隱私的泄露[7]。差分隱私[8]給出了一種嚴格可證明的數據隱私保護模型，其并不關心攻擊者擁有的背景知識，而是通過對輸出結果進行隨機擾動在保護數據隱私安全的同時，又可兼顧數據的可用性。其次，用戶使用位置服務時需授權LBS應用以獲取位置信息，這些被收集的用戶位置信息經過第三方處理并發布用于數據分析[9]。常用的處理方法是匿名或使用擴展技術對位置數據集進行處理，然而此類技術難以抵御背景知識的攻擊，從而造成用戶隱私泄露[10]。DWORK[11]最早提出了差分隱私概念，其優勢在于不受背景知識和某條數據變化的影響。此外，將差分隱私運用到位置隱私保護場景中，可通過隱私預算控制添加噪聲的大小[12]。再次，待發布的共享位置數據集為LBS用戶的頻繁位置數據集。對于此類頻繁模式數據挖掘問題，采用差分隱私技術合理分配隱私預算來兼顧頻繁數據的可用性和隱私保護[13]。文獻[14]基于廣義差分隱私技術添加噪聲以擾動用戶的位置信息，實現了用戶敏感漸進不可區分。文獻[15]和文獻[16]提出了一個2階段的隱私預算分配策略保護頻繁數據的隱私。此類方案單獨處理數據效率過低，且破壞了事務數據間的聯系，而頻繁位置數據的項集之間存在獨立且相聯的數據特性。最后，頻繁模式樹[17]、Trie樹[18]等數據結構在處理頻繁數據挖掘中，能有效維持數據項間的關系，常用于頻繁數據挖掘。文獻[19]使用Trie樹存儲事務數據，基于壓縮感知技術對事務數據的支持度計數添加滿足差分隱私約束的噪聲。文獻[20]在文獻[19]的基礎上運用差分隱私設計了工業物聯網中位置大數據的隱私保護方案。文獻[21]將差分隱私引入興趣點推薦系統，保護用戶位置隱私的同時，又提供了較好的興趣點推薦效果。上述方案雖然能夠兼顧位置數據的隱私保護和可用性，但均存在一個問題，即沒有對擾動后的位置數據支持度計數進行后置處理，而第三方發布的LBS用戶共享位置數據集中位置數據的支持度計數應為整數。

綜上所述，第三方發布的共享位置數據集，經差分隱私后能夠兼顧LBS用戶位置數據的可用性和隱私保護，但未考慮頻繁位置數據的項集之間存在獨立且相聯的數據特性。目前，雖然已有將Trie樹結構引入隱私保護以維持事務數據獨立且相聯的特性，但在位置隱私保護方案中構建位置搜索樹的效率不高，且因未對擾動后的位置數據支持度計數進行后置處理使得可用性降低。本方案引入Trie樹結構存儲位置數據和頻率，基于字典的查詢方式提高處理位置數據的效率。基于一致性約束后置處理對擾動后的數據進行優化，提高位置數據的可用性，使得共享位置數據更加安全。

1 基于差分隱私的位置保護方案

1.1 總體框架

近年來，互聯網和通信技術的飛速發展，使得LBS普遍應用于人們的日常生活中。用戶在使用這些應用時產生的位置信息被LBS應用收集，用于數據分析，如頻繁位置挖掘、出行規律分析等，甚至發布給第三方獲取額外收益。本研究基于差分隱私設計了一種LBS用戶位置隱私保護方案，實現用戶敏感位置保護。

所提方案中，定義用戶被收集的地理位置信息為共享位置數據，方案總體框架如圖1所示。首先，對用戶共享位置數據集進行預處理，匿去用戶身份、查詢內容等信息，將位置信息進行編號并構建位置事務數據庫。位置事務數據庫是包含標志符、位置項集和頻繁次數共3列的表格形式，行表示不同位置屬性的集合。其次，基于位置事務數據庫建立Trie樹，并完成頻繁位置的選取，其中頻繁位置表示用戶此階段經常使用的位置信息，包含用戶的敏感位置。再次，采用差分隱私下的拉普拉斯機制對頻繁位置的支持度進行擾動，泛化用戶的敏感位置達到隱私保護的效果。最后，對擾動后的數據進行后置處理以提高位置數據的可用性，并返回處理后的數據進行查詢分析。

1.2 方案設計

設計一種基于差分隱私的LBS用戶位置隱私保護方案，在保護共享位置數據隱私安全的同時較好地維持了數據可用性。將位置數據預處理后構建Trie位置樹，并使用指數機制進行頻繁位置選取;對選取的頻繁位置采用拉普拉斯機制，擾動其真實支持度，泛化敏感位置信息;對擾動后的數據進行后置處理，增強數據的可用性。

1.2.1 基于指數機制的頻繁位置選取共享位置數據集包含用戶的身份、訪問時間、當前位置信息、經緯度和查詢條件等內容，LBS應用在用戶授權下對位置信息進行分析處理或向第三方發布，需要考慮用戶的隱私安全和位置數據的可用性。本方案兼顧隱私保護和位置數據可用性，首先對共享位置數據集進行預處理，為集合中的位置數據分配編號，將共享位置數據集轉化為只包含編號和位置數據的集合。將此集合內容轉化為位置事務數據庫，并用Trie數據結構存儲位置事務數據庫的內容，位置事務數據庫如表1示。

當用戶的位置處于字典中時，其頻繁次數上升一次;

當字典中查找不到該位置時，將該位置添加進字典中，并令該位置頻繁次數取值為1。之后，只需掃描一次即可構建位置事務數據庫，避免了在原有數據庫中對位置信息的多次查找，提高了處理效率。基于表1構建位置數據的Trie樹如圖2示。

圖2包含了位置事務數據庫的全部項集，節點表示位置數據，節點中的支持度表示頻繁位置次數。位置Trie樹維持了事務數據的相聯特性，在Trie樹上進行頻繁位置選取效率更高。此外，拉普拉斯機制擾動的是節點的頻繁次數而非共享數據集中的單個位置數據，可有效降低拉普拉斯加噪的頻率并提高數據的處理效率。在頻繁位置選取中，以頻繁次數劃分用戶的敏感位置。實際應用中可融入多個參數，如使用當前位置的時間按照用戶敏感時間段分配不同的權值，從而更好地區分敏感位置。基于差分隱私指數機制的頻繁位置選取過程如下。

令按層遍歷選出的頻繁次數不小于m的位置數據為N個，其構成頻繁位置集S={FL1，FL2，…，FLN}。差分隱私下的指數機制隱私預算為ε1，則前k個頻繁位置中每次選取所分配的隱私預算為ε1/k。本方案中，影響位置敏感性的因素僅由位置頻繁次數決定，故指數機制中打分函數可定義為位置頻繁次數，如式（1）所示：

u（S，FLi）=CLi（FLi）。（1）

式中：u（S，FLi）為指數機制的打分函數;CLi（FLi）表示位置FLi的頻繁次數。

打分函數u（S，FLi）的敏感度Δu為1。而每次選取所分配的隱私預算為ε1/k，指數機制如式（2）所示：

Pr（FLi）∝exp（εu（S，FLi）2Δu）=exp（ε1u（S，FLi）2k）。（2）

根據式（2）計算位置數據的歸一化概率，如式（3）所示：

Pr（FLi）=exp（ε1u（S，FLi）2k）∑Ni=1exp（ε1u（S，FLi）2k），（3）

式（3）是位置數據歸一化后的指數機制輸出概率值，該值與位置頻繁次數成正比，通過指數機制選取前k個位置數據可有效保護位置的頻繁次數，不被數據分析人員獲取。

1.2.2 基于拉普拉斯機制的加噪處理

運用差分隱私下的指數機制思想選取前k個頻繁位置數據，有效保護了頻繁位置選取過程中的頻繁次數隱私安全。然而，指數機制只用于頻繁項選取，并未對位置數據進行擾動，若作為最終結果輸出會造成嚴重的用戶隱私泄露問題。因此，在頻繁位置選取后，仍需采用拉普拉斯機制對選出的前k個頻繁位置加噪，擾動其真實頻繁次數，從而保護用戶的隱私安全。拉普拉斯函數的概率密度如式（4）所示：

Pr（x，b）=12bexp（-xb）。（4）

令拉普拉斯機制加噪所分配的隱私預算為ε2，則對選取的k個頻繁位置次數加噪，每次所分配的隱私預算為ε2/k。查詢函數Q（FL）的敏感度為ΔQ，當用Q（FL）表示位置頻繁次數時，ΔQ的值為1。定義b=ΔQ/（ε2/k）=k/ε2。則在式（4）的基礎上，拉普拉斯噪聲的定義如式（5）所示：

Lap（kε2）=ε22kexp（-ε2xk）。（5）

每次加噪擾動后的查詢函數Q（FLi）如式（6）所示：

Q（FLi）=Q（FLi）+Lap（kε2）。（6）

通過拉普拉斯機制對k個頻繁位置的次數進行擾動，泛化了用戶敏感位置，從而保護了用戶的隱私安全。然而，加噪后的頻繁位置次數可能不為整數，若直接覆蓋原位置數據會降低數據的可用性。因此，需要對其進行后置處理，以提高數據的可用性。

1.2.3 后置處理

采用一致性對數據進行后置處理，以提高數據的可用性。一致性約束將后置處理轉化為一個保序回歸問題，不妨令CL（FL）={CL1（FL1），CL2（FL2），…，CLk（FLk）}表示擾動后的位置頻繁次數集合，同時令CL（FΔL）={CL1（FΔL1），CL2（FΔL2），…，CLk（FΔLk）}表示一致性約束處理后位置頻繁次數集合。即在CLi（FΔLi）≥CLi+1（FΔLi+1）條件下，對式（7）進行求解

min∑ki=1（CL（FL）-CL（FΔL））2。（7）

定理1 令Lk=minj∈[t，k]maxi∈[1，j]M[i，j]，Ut=maxi∈[1，t]mini∈[i，k]M[i，j]，則在式（7）和其一致性條件約束下的解為CL（FDL）={L1，L2，…，Lk}={U1，U2，…，Uk}。其中，M[i，j]=∑jt=iCLt（FΔLt）/（j-i+1）。

基于定理1[20]求解出一致性約束處理后的位置頻繁次數集合，再對其進行向上取整處理，以滿足頻繁位置次數為整數的性質。例如，擾動后的位置頻繁次數集合為CL（FL）={14.8，12.5，13.3}，經過一致性約束處理后位置頻繁次數集合為CL（FΔL）={14.8，12.9，12.9}，采用向上取整處理后位置頻繁次數集合為{15，13，13}。將后置處理的結果更新到共享位置數據集中進行發布，保護敏感位置的同時具有較好的位置數據可用性。

2 安全性分析

對方案的安全可行性進行分析，證明其滿足ε-差分隱私[11]。首先對指數機制進行差分隱私分析，證明其滿足ε1-差分隱私;其次對拉普拉斯機制進行差分隱私分析，證明其滿足ε2-差分隱私。綜合以上2點，本方案滿足ε-差分隱私。

定理2 令S={FL1，FL2，…，FLN}為頻繁位置集合，差分隱私下的指數機制隱私預算為ε1，采用均勻分配每次選取所分配的隱私預算為ε1/k。指數機制的打分函數為u（S，FLi），打分函數u（S，FLi）的敏感度Δu為1。則指數機制滿足ε1-差分隱私。

證明 令M（S，i）（1≤i≤k）表示第i次從頻繁位置集合S中選取頻繁位置FLi;S表示集合S的相鄰數據集。則指數機制的概率比值如式（8）所示：

Pr[M（S，i）=FLi]Pr[M（S，i）=FLi]=exp（ε1u（S，FLi）2k）∑Ni=1exp（ε1u（S，FLi）2k）exp（ε1u（S，FLi）2k）∑Ni=1exp（ε1u（S，FLi）2k）= exp（ε1（u（S，FLi）-u（S，FLi））2k）×∑Ni=1exp（ε1u（S，FLi）2k）∑Ni=1exp（ε1u（S，FLi）2k）≤exp（ε12k）∑Ni=1exp（ε1u（S，FLi）2k）∑Ni=1exp（ε1u（S，FLi）2k）。（8）

由敏感度定義對式（8）化簡，結果如式（9）所示：

Pr[M（S，i）=FLi]Pr[M（S，i）=FLi]≤exp（ε12k）×∑Ni=1exp（ε1u（S，FLi）2k）∑Ni=1exp（ε1u（S，FLi）2k）≤ exp（ε12k）×∑Ni=1exp（ε1（u（S，FLi）+1）2k）∑Ni=1exp（ε1u（S，FLi）2k）=exp（ε12k）×exp（ε12k）=exp（ε1k）。（9）

即每一次頻繁位置選取均滿足ε1/k-差分隱私。由差分隱私的串行性質可知，本指數機制滿足ε1-差分隱私。

定理3 令S={FL1，FL2，…，FLN}表示頻繁位置集合，差分隱私下的拉普拉斯機制隱私預算為ε2，采用均勻分配每次添加拉普拉斯噪聲所分配的隱私預算為ε2/k。則添加噪聲的過程滿足ε2-差分隱私。

證明：不妨令擾動后的位置頻繁次數集合為CL（FL）={CL1（FL1），CL2（FL2），…，CLk（FLk）}。同時，不妨令擾動前的頻繁次數集合為CL（FL）={CL1（FL1），CL2（FL2），…，CLk（FLk）}。S表示集合S的相鄰數據集，Q（FL）表示查詢函數。對于每一次向FLi的頻繁次數CL1（FLi）添加噪聲擾動而言，拉普拉斯機制的概率比值如式（10）所示：

Pr[Q（S，FLi）=CL（FLi）]Pr[Q（S，FLi）=CL（FLi）]=exp（-ε2|CL（FLi）S-CL（FLi）|k）exp（-ε2|CL（FLi）S-CL（FLi）|k）= exp（ε2k×（|CL（FLi）S-CL（FLi）|-|CL（FLi）S-CL（FLi）|））≤ exp（ε2k×|CL（FLi）S-CL（FLi）S|）≤exp（ε2k）。（10）

綜上所述，每一次加噪均滿足ε2/k-差分隱私。由差分隱私的串行性質可知，拉普拉斯加噪過程滿足ε2-差分隱私。故從整體上而言，滿足ε-差分隱私。

3 仿真實驗及結果分析

在Intel（R） Core（TM） i5-4210U CPU @ 1.70 GHz2.40 GHz處理器、4 GB內存、Windows 10操作系統下進行仿真實驗。實驗代碼采用Python 3.7編寫，并于PyCharm上運行，所用的數據集為Foursquare dataset[22]，該數據集經過處理后，包含24 941個用戶，28 593個位置興趣點和1 196 248個用戶的位置簽到數據。以下從時間和效用性2個方面分析討論方案的敏感隱私保護和數據可用性。

3.1 時間分析

時間是衡量算法效率的因素之一，從建立Trie樹的時間和挑選出前k個頻繁位置的時間2個角度進行計算分析，并與LPT-DP-K[20]的算法進行對比分析。先對原數據集進行預處理，使預處理后的數據集僅包含位置編號和位置信息。從預處理后的數據集中選取100，200，500，1 000行數據，本方案（Trie）和LPT-DP-K方案（ergod）建立Trie樹的時間如圖3所示。

從圖3可看出，本方案和LPT-DP-K方案建立Trie樹的時間效率都很高，且本方案優于LPT-DP-K方案。通過新建字典的方式構建位置數據庫，當數據集位置在字典中，則位置頻繁次數加1，否則添加位置進字典中，位置頻繁次數值取1。通過查詢字典，只需遍歷一次數據集。而LPT-DP-K方案通過先選出數據集中不同的項集N，再對每一個項集遍歷數據集統計每一項的頻率次數。

從預處理后的數據集中選取前1 000行位置數據建立Trie樹，使用無放回取最大值的思想和指數機制頻繁位置選取2種方法分別從Trie樹上選取前k=[10，20，50，100]個頻繁位置。2種方法選擇前k個頻繁位置的時間如圖4所示。

從圖4可看出，使用無放回取最大值的時間效率優于指數機制頻繁位置選取。第1種是基于無放回取最大值的思想，取k次后即可獲取前k個頻繁位置數據;第2種是基于差分隱私下的指數機制思想，先按層遍歷選出頻繁次數不小于m的位置數據，再運用指數機制進行篩選獲取前k個頻繁位置數據。第1種方法獲取前k個頻繁位置數據時間效率高，第2種方法可在選取前k個頻繁位置數據時保護位置的頻繁次數不被數據分析人員獲取。

3.2 效用性分析

效用性可用來衡量算法的隱私保護有效性和位置數據的可用性。

3.2.1 有效性分析

對有效性而言，對隱私保護前后的敏感位置進行分析。從預處理后的數據集中選取前1 000行位置數據，取k頻繁位置分別為10，20，50和100時對隱私保護前后的敏感位置進行對比分析，從而驗證位置隱私保護方案的有效性。算法中定義訪問頻率h劃分敏感位置和非敏感位置。當位置的頻繁次數值不小于h時，則將此位置劃分為敏感位置;否則，則將此位置劃分為非敏感位置。通過實驗可得無差分隱私[9]和差分隱私后的敏感位置對比如表2所示。

為了更直觀地對比分析，基于表2的數據繪制隱私保護前后的敏感位置對比圖，如圖5所示。由圖5可知，采用差分隱私對頻繁位置進行保護后敏感位置變多了，從而對原敏感位置進行泛化。當k為10時，敏感位置從2個變為4個;當k為20時，敏感位置從4個變為8個;當k為50時，敏感位置從11個變為23個;當k為100時，敏感位置從21個變為51個。

圖6更為直觀地顯示了50個模式隱私保護前后的敏感位置數量，其中藍點表示非敏感位置，紅點表示敏感位置。可見，采用拉普拉斯機制對頻繁位置的次數加噪后，使得部分非敏感位置轉變成敏感位置，泛化了最初的敏感位置，從而保護了用戶的位置隱私。此外，經過泛化后的敏感位置集合仍包含用戶敏感位置，使得第三方對位置數據集的分析依然有著較高的可用性。

3.2.2 可用性分析

對于可用性而言，采用精確率和拒真率作為本方案的評價標準。設A為選取的原前k個頻繁位置的集合，B為拉普拉斯加噪后的前k個頻繁位置的集合。精確率定義為算法輸出的頻繁位置出現在集合A和集合B中的數量與集合B中的數量的比值，如式（11）所示。拒真率定義為算法輸出的頻繁位置出現在集合A中卻未在集合B中的比值，如式（12）所示：

精確率=A∩BB，（11）

拒真率=A∪B-BK。（12）

采用向上后置處理和一致性約束后置處理2種手段對加噪的位置頻率進行處理。將從精確率和拒真率2個評價指標對無后置處理[19-20]、向上后置處理[21]和一致性約束后置處理3種方法進行對比分析。通過給定確切ε的值和變化k的取值計算3種方法的精確率和拒真率。實驗中設ε=1，參數k的取值分別為20，40，60，80，100。則參數k值變化時，3種方法的精確率和拒真率分別如圖7和圖8所示。

從圖7可看出，隨著k值的增加，3種后置處理方案的準確率均有所下降。使用向上后置處理和一致性約束后置處理后的準確率明顯優于無后置處理的準確率。此外，隨著k值的增加，經過一致性約束后置處理后的數據準確率的變化曲線較為平緩。當k取值為100時，一致性約束后置處理后的準確率依然在80%左右，從另一方面驗證了對加噪數據采用后置處理，可提高數據的可用性。從圖8可看出，隨著k值的增加，3種后置處理方案的拒真率均有所提升。拒真率用來衡量算法的效用性，拒真率越小，效用性越高。使用向上后置處理和一致性約束后置處理的數據拒真率較低，具有很好的效用性。

通過給定確切的k值和變化ε取值范圍計算3種方法的精確率和拒真率。實驗中設k=200，參數ε的取值為0.05，0.10，0.50，0.75，1.00，1.50。則參數ε值變化時3種方法的精確率和拒真率分別如圖9和圖10所示。從圖9可看出，隨著ε值的增加，3種后置處理方案的精確率均有所上升。使用向上后置處理和一致性約束后置處理后的精確率明顯優于無后置處理的精確率。隨著隱私預算的增加，數據可用性越高，但隱私保護力度降低。此外，當ε取值為1時，一致性約束后置處理后的準確率在85%左右，從另一方面驗證了對加噪數據采用后置處理，可提高數據的可用性。從圖10可看出，隨著ε值的增加，3種后置處理方案的拒真率有所下降。拒真率用來衡量算法的效用性，拒真率越小，效用性越高。從圖10可發現，固定k值和改變ε取值時，使用向上后置處理和一致性約束后置處理的數據拒真率較低，具有很好的效用性。因此，本方案能有效保護用戶的隱私安全，并具有較好的數據可用性。

4 結 語

為了解決共享位置數據的隱私保護和可用性不足的問題，提出了一種基于差分隱私的位置隱私保護方案。首先，采用Trie數據結構存儲位置數據和其支持度，保持了頻繁位置數據特性，提高了位置數據處理效率。其次，使用差分隱私下的拉普拉斯機制擾動頻繁位置支持度，保護了用戶的敏感位置。最后，對擾動后的數據進行后置處理，并通過不同的后置處理方法進行對比，提高了數據的可用性。

未來工作將圍繞快速建立Trie樹提高算法效率和考慮多因素篩選敏感位置2個方面開展研究，首先使用hash表完成位置事務數據庫的統計構建，基于堆結構進行查找并完成頻繁位置指數機制選取;其次綜合考慮頻繁次數和時間等多個位置因素，通過不同的權重，從可信計算的角度更為準確地篩選敏感位置，設計出更適用于LBS用戶的位置隱私保護方案。

參考文獻/References：

[1] WANG Jinbao，CAI Zhipeng，LI Yingshu，et al.Protecting query privacy with differentially private k-anonymity in location-based services[J].Personal and Ubiquitous Computing，2018，22（3）：453-469.

[2] DARGAHI T，AMBROSIN M，CONTI M，et al.ABAKA：A novel attribute-based k-anonymous collaborative solution for LBSs[J].Computer Communications，2016，85（1）：1-13.

[3] 劉海，李興華，雒彬，等.基于區塊鏈的分布式K匿名位置隱私保護方案[J].計算機學報，2019，42（5）：942-960.

LIU Hai，LI Xinghua，LUO Bin，et al.Distributed K-anonymous location privacy protection scheme based on blockchain[J].Chinese Journal of Computers，2019，42（5）：942-960.

[4] WANG Shengling， HU Qin，SUN Yunchuan，et al.Privacy preservation in location-based services[J].IEEE Communications Magazine，2018，56（3）：134-140.

[5] 萬盛，李鳳華，牛犇，等.位置隱私保護技術研究進展[J].通信學報，2016，37（12）：124-141

WAN Sheng，LI Fenghua，NIU Ben，et al.Research progress on location privacy-preserving techniques[J].Journal on Communications，2016，37（12）：124-141.

[6] SWEENEY L.K-anonymity：A model for protecting privacy[J].International Journal of Uncertainty Fuzziness & Knowledge Based Systems，2002，10 （5）：557-570.

[7] 張嘯劍，孟小峰.面向數據發布和分析的差分隱私保護[J].計算機學報，2014，37（4）：927-949.

ZHANG Xiaojian，MENG Xiaofeng.Differential privacy in data publication and analysis[J].Chinese Journal of Computers，2014，37（4）：927-949.

[8] WANG Yue，YANG Lin，CHEN Xiaoyun，et al.Enhancing social network privacy with accumulated non-zero prior knowledge[J].Information Sciences，2018，445/446：6-21.

[9] ZHANG P，DURRESI M，DURRESI A.Internet network location privacy protection with multi-access edge computing[J].Computing，2021，103：473-490.

[10]付鈺，俞藝涵，吳曉平.大數據環境下差分隱私保護技術及應用[J].通信學報，2019，40（10）：157-168.

FU Yu，YU Yihan，WU Xiaoping.Differential privacy protection technology and its application in big data environment[J].Journal on Communications，2019，40（10）：157-168.

[11]DWORK C.Differential privacy[C]// Proceedings of the 33rd International Conference on Automata，Languages and Programming （ICALP 2006）.Berlin：Springer，2006：1-12.

[12]GENG Q，VISWANATH P.The optimal noise-adding mechanism in differential privacy[J].IEEE Transactions on Information Theory，2016，62（2）：925-951.

[13]丁麗萍，盧國慶.面向頻繁模式挖掘的差分隱私保護研究綜述[J].通信學報，2014，35（10）：200-209.

DING Liping，LU Guoqing.Survey of differential privacy in frequent pattern mining[J].Journal on Communications，2014，35（10）：200-209.

[14]王斌，張磊，張國印.敏感漸進不可區分的位置隱私保護[J].計算機研究與發展，2020，57（3）：616-630.

WANG Bin，ZHANG Lei，ZHANG Guoyin.A gradual sensitive indistinguishable based location privacy protection scheme[J].Journal of Computer Research and Development，2020，57（3）：616-630.

[15]盧國慶，張嘯劍，丁麗萍，等.差分隱私下的一種頻繁序列模式 挖掘方法[J].計算機研究與發展，2015，52（12）：2789-2801.

LU Guoqing，ZHANG Xiaojian，DING Liping，et al.Frequent sequential pattern mining under differential privacy[J].Journal of Computer Research and Development，2015，52（12）：2789-2801.

[16]張嘯劍，王淼，孟小峰.差分隱私保護下一種精確挖掘top-k頻繁模式方法[J].計算機研究與發展，2014，51（1）：104-114.

ZHANG Xiaojian，WANG Miao，MENG Xiaofeng.An accurate method for mining top-k frequent pattern under differential privacy[J].Journal of Computer Research and Development，2014，51（1）：104-114.

[17]BODON F.A fast apriori implementation[J].Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations，2003，90：654-667.

[18]LE P，VO B，HONG P，et al.Incremental mining frequent itemsets based on the trie structure and the pre-large itemsets[C]// IEEE International Conference on Granular Computing.Taiwan：IEEE，2012：369-373.

[19]歐陽佳，印鑒，劉少鵬，等.一種有效的差分隱私事務數據發布策略[J].計算機研究與發展，2014，51（10）：2195-2205.

OUYANG Jia，YIN Jian，LIU Shaopeng，et al.An effective differential privacy transaction data publication strategy[J].Journal of Computer Research and Development，2014，51（10）：2195-2205.

[20]LI C，PALANISAMY B，JOSHI J.Differentially private trajectory analysis for points-of-interest recommendation[C]// 2017 IEEE International Congress on Big Data （BigData Congress）.Honolulu：IEEE，2017：49-56.

[21]YIN Chunyong，XI Jinwen，SUN Ruxia，et al.Location privacy protection based on differential privacy strategy for big data in industrial internet of things[J].IEEE Transactions on Industrial Informatics，2018，14（8）：3628-3636.

[22]LI Huayu，GE Yong，HONG R，et al.Point-of-interest recommendations：Learning potential check-ins from friends[C]//The 22nd ACM SIGKDD International Conference.[S.l]：ACM，2016：975-984.