基于LBS的軌跡隱私保護研究

◆蒙絨娟 高玉琢

（寧夏大學信息工程學院 寧夏 750021）

1 引言

隨著移動終端和無線定位技術的迅速發展，在人們日常生活中有許多領域都應用到基于位置的服務（Location-Based Services，LBS）。LBS 主要分為：瞬時LBS 和連續LBS。從2003年學術界開始對位置隱私保護進行了相關研究，但是，多數研究僅考慮瞬時LBS的情形，對連續LBS的隱私保護相對較少。近些年，學術者發現僅對每一時刻的位置進行保護，攻擊者仍然可以分析出用戶的興趣愛好、生活習慣、身體缺陷等信息。因此，在確保服務質量的同時，保護用戶的軌跡隱私安全是如今亟待解決的問題。

2 軌跡隱私泄露對象

用戶在應用位置服務時，給服務器上傳了一定信息，包括用戶身份、地理位置坐標、軌跡以及請求內容。根據位置服務包含的容的不同，將隱私保護對象分為：單點位置隱私、軌跡位置隱私與查詢隱私。

2.1 單點位置隱私

根據身份信息和地理位置坐標，如果二者相匹配，就可以確定具體用戶，一旦泄露用戶的具體信息，就可以推斷出其他信息。用戶的身份信息和位置坐標信息形成單點隱私。身份信息包括用戶的身份證號、工號、MAC 地址等，位置坐標信息包括用戶經緯度位置坐標和時間。單點位置用三元組可以表示為：。從三元組中可以獲得用戶是“是誰，在什么位置，在什么時間”該類信息。

2.2 軌跡位置隱私

軌跡是指移動個體從開始到結束為止所經過的路線。通常情況下，軌跡T 可以表示為T={qi，（x1，y1，t1），（x2，y2，t2），……，（xn，yn，tn）}。其中，qi 表示移動個體形成的軌跡信息，（xn，yn，tn）表示在tn 時刻移動用戶所在的地理位置坐標是（xn，yn）。移動的個體現在的狀態如果是靜止的，則采集的數據是靜態數據；移動的個體如果還在運動當中，則采集的數據是逐漸增加的，是一個動態的數據收集。

用戶軌跡數據包含的信息量要比單點位置隱私多。通常，用戶每天往返于住處和工作單位之間上下班，形成軌跡數據。軌跡位置隱私可以通過大數據技術分析出軌跡數據中包含的個人信息。攻擊者擁有軌跡數據就能分析出用戶的家庭住址、興趣愛好等信息，也能夠推測用戶下一時間出現的地址，這威脅著用戶的人身安全。

2.3 查詢隱私

用戶查詢的內容中包含了個人信息，可能會導致個人隱私的泄露。查詢內容本身不具有用戶隱私信息，但是可以通過關聯技術，挖掘出用戶的個人信息。用戶如果將查詢內容進行模糊處理，則無法得到準確的結果，從而造成服務質量下降。

3 軌跡隱私保護系統結構

由于軌跡數據的特征和軌跡隱私保護的內涵，造成了軌跡隱私保護方法只能采用集中式架構和分布式架構[1]。同時，軌跡隱私保護系統對位置服務器的存儲、計算性能要求較高。下面對各種結構分別進行描出，并討論優缺點。

3.1 集中式架構

集中式架構也稱為中心服務器架構，它有三個部分：用戶端、位置匿名服務器（可信的第三方）和LBS 服務平臺（location-based services platform，LSP）組成，集中式架構示意圖如圖1所示。

圖1 集中式架構

用戶端將位置信息和查詢內容發送給位置匿名服務器，位置匿名服務器按照特定的隱私保護規則對用戶端的查詢請求進行保護，并將隱私保護后的查詢內容發送到LSP，LSP 根據接收到內容進行查詢，并將結果集發送到位置匿名服務器，位置匿名服務器將該用戶的查詢結果求精后發送給用戶。集中式架構具有很好的隱私保護效果，且減小了用戶端隱私保護和數據處理的負擔。缺點：無法保證引入第三方的可信度；大量的計算分布在匿名服務器上，可能會成為系統性能瓶頸；在現實生活中，部署大量的匿名服務器具有一定的難度。

3.2 分布式架構

分布式架構由用戶端和LSP 構成，分布式架構示意圖如圖2所示。

圖2 分布式架構

用戶端使用點對點協議進行通信，形成滿足要求的匿名集，并以匿名集的形式發送到LSP，LSP 接收到某個固定用戶端的查詢請求，隨后將結果集返回給固定用戶端。分布式架構具有較好的隱私效果，無須依賴第三方，但是，對匿名組內的用戶信任度較高，一旦其中一個用戶是惡意用戶，則整個匿名組的信息都會被泄露。

4 軌跡隱私保護技術

軌跡隱私保護根據用戶查詢請求到達LSP 方式的不同，將隱私保護技術分為：假軌跡、軌跡泛化、軌跡抑制、軌跡擾亂。在此將針對各類方法進行闡述與分析。

4.1 假軌跡

假軌跡隱私保護方法指的是由用戶的客戶端生成k-1 條假軌跡，與真實軌跡構成軌跡集進行發布。文獻[2]根據某一時刻位置和軌跡數量，提出了隨機法和旋轉法的假軌跡生成方案。當生成假軌跡沒有考慮到路網環境和移動對象的運行模式，假軌跡則不能保護軌跡數據的隱私安全。針對上述問題，文獻[3]提出了基于時空關聯的假軌跡隱私保護方法，從時間可達性、方向相似性和出入度3 個方面綜合考慮相鄰位置請求的時空關系。針對未考慮到用戶所處的背景信息，文獻[4]和文獻[5]提出根據歷史查詢概率通過重力模型和萬有引力定律模型計算出用戶位置轉移概率，充分地考慮到移動用戶的行為模式。假軌跡隱私保護方法機制簡單，計算量小，不需要第三方代理，且能保留完整的軌跡信息。

4.2 軌跡泛化

軌跡泛化中最流行的方法是軌跡k 匿名方法。軌跡k-匿名指的是由匿名服務器篩選出k-1 條其他用戶軌跡與真實軌跡組成軌跡集，使得k-1 條軌跡與真實軌跡無法區分，實現保護真實軌跡。文獻[6]在每個時刻選擇泛化區域時需要滿足該區域中有其他k-1 個用戶存在，以達到k-匿名保護。文獻[7]在文獻[6]的基礎上，考慮了用戶的移動方向和速度來最小化泛化區域。文獻[8]提出NWA（Never Walk Alone，NWA）方法，利用軌跡聚類和空間轉移實現（k，δ）-anonymity。NWA 方法在形成軌跡K 匿名集，要求軌跡的起始點都相同，在現實生活中很少能滿足這樣的要求，文獻[9]對此進行了改進，提出了W4M 方法，采用EDR 距離計算兩軌跡之間的距離。文獻[10]結合路網環境，使用貪心算法將軌跡k-匿名問題轉換成為無向圖k-node 劃分問題。該方法使用戶可個性化定義隱私保護度，實現比較簡單，但是計算量比較大，容易遭受推理攻擊。

4.3 軌跡抑制

軌跡抑制隱私保護方法指的是根據真實位置的敏感程度或者頻繁地、選擇性地刪除或者抑制發布。主要分為兩個方面：實時發布位置抑制和歷史軌跡發布抑制。文獻[11]基于軌跡頻率提出了兩種解決方案，對有問題的軌跡添加假數據或者抑制有問題的軌跡；以及對有問題的軌跡采用特定局部抑制法。文獻[12]基于網絡環境抑制軌跡數中位置的發布，提高軌跡數據的利用率。文獻[13]通過抑制敏感位置的發布以及通過統計用戶訪問率，選擇用戶訪問率最大的非敏感位置替代敏感位置發布。該類方法實現簡單、易造成信息丟失、數據的可用性降低的問題，具有局限性，因此不能保證發布的數據具有一定的價值。

4.4 軌跡擾亂

以上三種隱私保護模型都是基于一定的背景知識，若背景知識改變或已被攻擊者掌握，那么這些方法將不再適用于隱私保護。因此，亟須一種不受背景知識影響，且具有良好隱私保護效果的技術。Dwork[14]首次提出差分隱私（differential privacy，DP），差分隱私保護技術不需要考慮攻擊者所擁有的背景知識，也不受某條數據變化的影響。因此，迅速成為學者們關注的重點，并成為隱私保護領域的研究熱點。

軌跡擾動隱私保護指的是利用差分隱私將軌跡上的真實位置擾動后發布。文獻[15]在前綴樹結構的基礎上，首次提出了差分隱私和軌跡隱私相結合的發布。為了提高軌跡數據的可用性，文獻[16]提出基于變長n-grams 模型。文獻[17]將馬爾科夫博弈與差分隱私相結合，為了更準確地找出需要保護的位置點，并采取相應的保護措施。文獻[18]考慮到地理空間分布，采用馬爾科夫概率轉移矩陣計算兩位置之間的聯系，提出了一種基于時空相關性的保護方法。

5 LBS 應用領域

位置服務的應用在人們生活中已經變得無處不在，目前，主要分為以下幾類：

5.1 定位服務

基于位置服務通過定位獲得用戶的具體位置，才可以實現相應的增值服務。如車載GPS 定位、新浪微博、釘釘打卡簽到、位置導航等都采用了定位服務。

5.2 興趣點推薦

該服務主動或被動向用戶提供有價值的信息。當用戶到達陌生的地點時，可通過該服務查詢附近餐館、電影院、停車場等興趣點，或者由服務提供商給用戶主動推送消息。

5.3 社交軟件

隨著移動設備的普及，社交軟件成為人與人之間溝通的主要方式。如QQ、微信、抖音等軟件根據位置查找附近好友功能，甚至好友出現在附近時會提示用戶。

5.4 智慧管理服務

智慧管理服務主要體現在智慧交通和智慧城市。智慧交通可根據車載GPS 定位，分析出車輛分布情況，使得用戶及時了解道路現狀，并提出更好的出行路線。智慧城市通過對人群和物流的位置信息監控，在發現異常后，可及時采取行動。

5.5 公共安全服務

對用戶的實時位置進行統計分析，提前捕捉危險信息，及時向用戶提供避險方式，而當緊急情況發生后，公共安全服務主動并準確地提供受害人的位置，以便實施救援。如發現洪水、地震、臺風等惡劣天氣，則會向周圍群眾預警；110、119、120 等緊急救援。

6 總結

隨著移動終端及其無線定位技術的快速發展，LBS 在多個領域產生了軌跡數據，由于軌跡數據中包含很多個人隱私信息。因此，研究者對軌跡數據的保護越來越關注，提出不少的軌跡隱私保護方法，在一定程度上起到了對軌跡隱私的保護作用，但是，越來越多的攻擊方法同樣被開發出來，使得軌跡隱私保護方法需要不斷進行改進。文章分析并討論了軌跡隱私泄露的對象、系統架構，隱私保護方法、應用領域等方面。總的來說，要徹底保護軌跡隱私不被攻擊者攻擊，還需進一步的研究與探索。