基于MDF-Nearest算法的軌跡隱私保護方法

耿雪冬

摘 要：傳統(tǒng)軌跡匿名方法在匿名集生成時沒有考慮用戶多種特征屬性，在信息攻擊下無法有效保護真實位置;在軌跡形成方面因沒有將余弦角度和軌跡間距離作為形成的依據(jù)，導致某些虛假軌跡無法有效保護真實軌跡。為改善以上問題，構建一種依據(jù)用戶多重特征信息構建的匿名集以保證匿名有效性;采用協(xié)作用戶的真實軌跡并計算相似性，從而生成虛假軌跡相似性高的MDF-Nearest算法。實驗結果表明，該方法隨著k值的變大與生成軌跡數(shù)量的增多，隱私保護效果逐漸改進;與傳統(tǒng)k匿名方法相比，該算法時間開銷降低41.7%，而隱私保護程度可提高至97.1%。因此該方法能以較低的時間開銷，提供質量可靠的位置服務，保護用戶信息。

關鍵詞：軌跡匿名;多重特征;余弦角度;軌跡間距離;MDF-Nearest算法

DOI：10. 11907/rjdk. 192030 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP309.7 文獻標識碼：A 文章編號：1672-7800（2019）009-0188-04

Trajectory Privacy Protection Method Based on MTF-Nearest+Algorithm

GENG Xue-dong

（College of Computer Science and Engineering， Shandong University of Science and Technology， Qingdao 266590， China）

Abstract：The traditional trajectory anonymity method does not take the users multiple feature attributes into account when generating the anonymous set， which leads to inefficient protection of the real position under the information attack. Whats more， the angle and the inter-track distance are not formed in the trajectory formation， and thus real trajectory cannot be effectively protected. This paper proposes an anonymous set based on the users multiple feature information to ensure the validity of the anonymity. The real trajectory of the collaborative user is used and the similarity is calculated to generate a false trajectory with high similarity. The experimental results show that with the value of k and the number of generated trajectories increases， the effect of privacy protection is better. Compared with the traditional k-anonymous method， the time cost of the algorithm is reduced by about 41.7%， while the degree of privacy protection is increased to about 97.1%. The method can provide high quality location services and protect user information with low time overhead.

Key Words： trajectory anonymity; multiple feature; cosine angle; distance between tracks; MDF-Nearest algorithm

0 引言

隨著全球定位和無線通信技術的快速發(fā)展，公眾享受到更便捷的出行方式，接觸到更多陌生的場景，也因此催生了日益頻繁的基于位置的服務（Location Based Service，LBS）請求;然而在享受服務的同時，用戶位置信息容易被不法分子獲取，帶來安全隱患。因此，如何兼顧良好的位置服務及高效的位置隱私保護成為當前研究熱點與重點。

目前軌跡隱私保護方法主要有3種類型：①基于生成假軌跡的方法[1-2];②基于抑制信息發(fā)布的方法[3-4];③基于信息泛化的方法[5-6]。常用典型方法是k匿名方法[7]。文獻[8-9]提出一種劃分區(qū)域的保護方法，將用戶活動區(qū)域分為兩部分區(qū)域，但導致用戶很難獲得高質量的服務，且需防御各種攻擊，如位置鏈接攻擊[10]等;文獻[11]利用差分算法完成了l-軌跡隱私保護;文獻[12]提出一個擁有k個用戶的k-匿名區(qū)域共享方案，通過加入其它k-1個相似用戶連續(xù)查詢請求達到保護的目的;文獻[13]提出一種高效的軌跡隱私保護方法，基于用戶真實地圖背景及行為模式的相關特征構建其余k-1條虛假協(xié)作軌跡，保證軌跡隱私安全;文獻[14]提出一種新的用戶集匿名區(qū)域算法，但因算法實現(xiàn)需要知道用戶未來位置，但未來位置難以有效預測，所以該算法并不具有現(xiàn)實性;文獻[15]通過真假軌跡條件共同生成軌跡集;文獻[16-17]利用連續(xù)查詢中的需求建模，通過加密方式保證安全;文獻[18]通過生成虛擬假人估計生成虛擬軌跡以保護真實軌跡;文獻[19]通過預測和假位置機制獲得k-1個混淆位置，將其匿名發(fā)送實現(xiàn)隱私保護;文獻[20]選出多個滿足時間關系的匿名候選者，用其軌跡代替真實軌跡以請求服務，實現(xiàn)保護目的;文獻[21]通過基于差分隱私發(fā)布機制實現(xiàn)隱私信息保護。

以上方法在選擇匿名用戶集時，沒有考慮用戶相關屬性，導致用戶匿名集中，除了位置相近之外，其它屬性不能完美掩蓋，所以無法完成對用戶的相似保護;另外單服務器的方式容易造成隱私信息泄露，攻擊者可通過竊取消息獲得用戶大致范圍請求。

針對以上問題，本文在雙中間處理器的架構下，引入MDF-Nearest（Multi-dimensional Feature）算法，將用戶多重屬性轉化為相應特征值，運用矩陣運算方法選取最相近用戶匿名集合，并通過角度與距離的聯(lián)合計算選擇相似軌跡，將協(xié)作用戶與用戶真實軌跡結合，實現(xiàn)用戶軌跡匿名隱私保護。雙服務器的應用可有效解決單一服務器隱私泄露的風險，而MDF-Nearest方法的匿名選擇和軌跡生成可實現(xiàn)對用戶軌跡的有效保護。

1 軌跡隱私保護模型及相關定義

1.1 系統(tǒng)模型

系統(tǒng)運行過程包括：①用戶首先通過MDF-Nearest方法聚合除用戶外的k-1個用戶，將真實用戶位置與協(xié)作用戶位置一同發(fā)送到中間服務器上;②用戶將k個用戶位置和服務請求分別發(fā)送到不同服務器上，兩個服務器分別接收部分信息，并通過隨機生成的編號保持其相同編號屬于同一用戶;③LBS服務器在接收中間服務器轉發(fā)來的信息后，將相應請求的應答信息返回至中間處理器，中間處理器將其原封不動地返回;④用戶端只接收自己在相應位置的結果信息，將信息求精后返回給用戶。

該系統(tǒng)模型的優(yōu)點是攻擊者不能從單個中間處理器上獲得任何有效信息，即使中間服務器共謀，在獲得信息后，由于采用的是假名，在沒有經過用戶端處理之前，無法得知真實用戶位置信息。同時，LBS服務器在服務器端也無法整合兩個服務器傳來的數(shù)據(jù)，保證了用戶信息數(shù)據(jù)安全。該系統(tǒng)由用戶、中間處理器和LBS服務器構成。

攜帶智能終端設備的用戶可通過多種方式接入網絡，并通過響應設備在不同時間、不同地點請求不同的服務。

中間處理器指介于用戶和LBS服務器之間的處理器實體，任務是接受用戶傳來的信息，發(fā)送數(shù)據(jù)到LBS服務器，保證用戶信息隱私。

LBS服務器是一個服務提供者，該服務器可以根據(jù)發(fā)送來的請求信息，搜尋結果后返回給發(fā)送方。

1.2 相關定義

（2） 軌跡間距離。設軌跡泛化完成后[T′]={T1，T2，…，T3}，則T和[T′]在[ti，ti+1]的距離為：[D（Tti，ti+1，Tti，ti+1）=][mti-nti2+mti+1-nti+12]。軌跡T和[T′]之間的距離為：

（3） 軌跡k匿名。設有多條軌跡的集合S，當集合S中某條軌跡與其它k-1條軌跡不可分時，則集合S滿足軌跡k匿名。

2 隱私保護方法

2.1 MDF-Nearest 匿名集生成方法

使用用戶匿名集的目的是為了防止中間處理器被攻擊者攻擊造成隱私泄露，同時增加中間處理器可防止用戶端直接與LBS服務器進行通訊，以免造成LBS服務器隱私泄露。因此，用戶端在發(fā)送位置時，首先要進行混淆處理。用戶端匿名集生成主要思想包括：①用戶通過定位設備獲得自己真實位置所在區(qū)域;② 依據(jù)該區(qū)域，通過用戶端混淆算法生成符合要求的位置點集合;③ 隨機給集合中的位置點編號，然后發(fā)送至中間處理器，再經由中間處理器處理后發(fā)送至LBS服務器。

2.2 基于多特征的MDF-Nearest偽代碼

MDF-Nearest算法

輸入：用戶位置點[P（xi，yi）]，查詢內容[（Content）]，用戶所在區(qū)域[（GUD）]，時間[（Ti）]

輸出：根據(jù)用戶需求及其它多個特征屬性結合生成的最相近位置點集合

算法前3步為用戶端選擇的協(xié)作用戶在真實用戶區(qū)域內與在可信時間內能夠到達的用戶集合算法步驟，步驟4-11表示將每一個符合區(qū)域與時間的用戶進行多維特征計算，首先獲取相同可達時間內協(xié)作用戶位置及相關特征或屬性，建立一個矩陣，矩陣行列分別表示協(xié)作用戶及其屬性，將全部屬性作為列值，某一協(xié)作用戶若有該屬性，則加注標記;若沒有，不加標記。該矩陣每加入一條新的用戶，便對其進行一次隨機行變換，該過程可以在[O（n）]時間內完成。步驟12指將結果集發(fā)送給中間處理器。

2.3 中間處理器多軌跡生成方法

中間處理器根據(jù)用戶端發(fā)來的軌跡點匿名集合，根據(jù)中間處理器存儲的歷史軌跡消息處理集合點，根據(jù)時間可達性、余弦角度和軌跡距離公式實現(xiàn)多軌跡匿名生成;然后將生成的k條軌跡發(fā)送給LBS服務器，LBS服務器根據(jù)中間處理器發(fā)來的信息提供服務，再將請求應答信息發(fā)送至中間處理器，由中間處理器下發(fā)至用戶端，用戶從用戶端接受自己真實的請求應答信息。

2.4 基于中間處理器的軌跡生成保護算法

3 實驗及分析

3.1 試驗設備參數(shù)

實驗主要從查找最匹配用戶的協(xié)作用戶、中間處理器進行匿名與軌跡生成處理， 以及向LBS服務器發(fā)送查詢請求等方面進行測試，再與k匿名算法進行仿真實驗比較。實驗數(shù)據(jù)集由Brinkhoff隨機生成器生成，以英國紐卡斯爾市交通網絡圖（區(qū)域面積為27km*29km）作為輸入，生成了1 000條軌跡數(shù)據(jù)。查詢對象數(shù)據(jù)隨機分布，本實驗隨機選擇一個點作為模擬用戶的點，對算法相關屬性進行測試。實驗硬件環(huán)境為：AMD ?A8-5550m ?CPU@2.1GHz ?4 Cores，4.00GB內存，操作系統(tǒng)為Microsoft Windows 10 64 bit操作系統(tǒng)，采用Anaconda平臺，用Python語言實現(xiàn)。

3.2 實驗結果分析

本文通過試驗驗證算法有效性，從響應時間和隱私保護度兩方面與不同k值的傳統(tǒng)k-匿名算法進行比較，傳統(tǒng)k-匿名保護算法的隱私保護度指標僅與k值有關。兩種算法對比結果如圖2所示。

從圖2可以看出，當用戶在選擇自己相近匿名協(xié)作用戶時，隨著k值的不斷增大，系統(tǒng)響應時間隨之增加。隨著k的變化，傳統(tǒng)k-匿名算法在選擇用戶時，由于數(shù)據(jù)增多，計算量不斷攀升;而本文采取的算法雖然隨著k值增大，開銷時間也在增長，但增長幅度比較緩慢，與傳統(tǒng)k-匿名方法相比，本文算法在響應時間上時耗較少。

在不同方式的軌跡隱私保護算法中，系統(tǒng)響應時間與相應用戶隱私保護程度是一對矛盾體。因此，在保證系統(tǒng)響應時間的前提下提升隱私保護程度是反映算法優(yōu)劣的重要指標。圖3展示的是本文算法與傳統(tǒng)k-匿名算法在隱私保護度上的對比。

由圖3可以看出，本文提出的MDF-Nearest算法與傳統(tǒng)k-匿名算法在k值較小時相比，二者差距并不是很大，但是隨著用戶數(shù)量的增多，MDF-Nearest算法對用戶的保證程度明顯增大。這是因為到達一定數(shù)量時，根據(jù)角度及軌跡距離等多種條件生成的相似性高的軌跡數(shù)量不斷增多，所以，k值越大，MDF-Nearest算法對于用戶軌跡保護程度越好。

4 結語

本文主要針對傳統(tǒng)軌跡匿名算法在匿名區(qū)域形成和軌跡聚合混淆時，由于未能考慮用戶特征及軌跡形成條件，容易造成攻擊者識別出用戶軌跡的問題，提出了一種利用集合用戶多重特征屬性、角度和軌跡距離生成虛假軌跡的方法，提高了用戶可分辨難度，并根據(jù)余弦角度和軌跡距離進一步生成更加接近真實軌跡的虛假軌跡，使攻擊者無法重構用戶真實軌跡，從而提高軌跡保護性。同時，通過用戶軌跡保護度還可衡量虛假軌跡隱私泄露程度。試驗表明，該方法能夠獲得較好的軌跡隱私保護。

下一步將考慮在構造用戶軌跡方面，如何更好地將用戶歷史軌跡特征與真實位置點請求結合起來，還將充分考慮時空關聯(lián)性以便生成迷惑性更高的虛假軌跡，以及如何提高用戶位置點匿名集合的可信性、混淆性與可用性，更有效地提高用戶服務質量。

參考文獻：

[1] 董玉蘭，皮德常. 一種基于假數(shù)據(jù)的新型軌跡隱私保護模型[J]. 計算機科學， 2017， 44（8）： 124-128.

[2] 雷凱躍，李興華，劉海，等. 軌跡發(fā)布中基于時空關聯(lián)性的假軌跡隱私保護方案[J]. 通信學報， 2016， 37（12）： 156-164.

[3] 趙婧，張淵，李興華，等. 基于軌跡頻率抑制的軌跡隱私保護方法[J]. 計算機學報，2014，37（10）： 2096-2106.

[5] KOMISHANI E G，ABADI M，DELDAR F. PPTD： preserving personalized privacy in trajectory data publishing by sensitive attribute generalization and trajectory local suppression[J]. Knowledge-Based Systems， 2016， 94： 43-59.

[6] CHEN R，F(xiàn)UNG B C M，MOHAMMED N，et al. Privacy-preserving trajectory data publishing by local suppression[J]. Information Sciences， 2013， 231： 83-97.

[7] EL OUAZZANI Z， El Bakkali H. A new technique ensuring privacy in big data： k-anonymity without prior value of the threshold k[J]. Procedia Computer Science， 2018， 127： 52-59.

[8] 霍崢，孟小峰，黃毅. PrivateCheckIn： 一種移動社交網絡中的軌跡隱私保護方法[J]. 計算機學報， 2013， 36（4）： 716-726.

[9] HUANG L，MATSUURA K，YAMANE H，et al. Enhancing wireless location privacy using silent period[C]. IEEE Wireless Communications and Networking Conference， 2005： 1187-1192.

[10] HUANG L， YAMANE H， MATSUURA K， et al. Silent cascade： enhancing location privacy without communication QoS degradation[C]. International Conference on Security in Pervasive Computing， 2006： 165-180.

[11] DING Y，PEDDINTI S T，ROSS K W. Stalking Beijing from Timbuktu： a generic measurement approach for exploiting location-based social discovery[C]. Proceedings of the 4th ACM Workshop on Security and Privacy in Smartphones & Mobile Devices， 2014： 75-80.

[12] CAO Y，YOSHIKAWA M. Differentially private real-time data release over infinite trajectory streams[C]. The 16th IEEE International Conference on Mobile Data Management， 2015： 68-73.

[13] CHOW C Y，MOKBEL M F. Enabling private continuous queries for revealed user locations[C]. International Symposium on Spatial and Temporal Databases， 2007： 258-275.

[14] 李鳳華，張翠，牛犇，等. 高效的軌跡隱私保護方案[J]. 通信學報，2015，36（12）：114-123.

[15] WANG Y，XU D，HE X，et al. L2P2： location-aware location privacy protection for location-based services[C]. Proceedings of IEEE INFOCOM， 2012： 1996-2004.

[16] 胡德敏，鄭霞. 基于連續(xù)查詢的用戶軌跡 k-匿名隱私保護算法[J]. 計算機應用研究，2017 （11）： 3421-3423+3427.

[17] 周凱，彭長根，何建瓊，等. 可證明安全的 LBS 中連續(xù)查詢的軌跡隱私保護方案[J]. 信息網絡安全， 2017 （1）： 43-47.

[18] HAYASHIDA S，AMAGATA D， HARA T， et al. Dummy generation based on user-movement estimation for location privacy protection[J]. IEEE Access， 2018， 6： 22958-22969.

[19] 張少波，劉琴，王國軍. 基于位置混淆的軌跡隱私保護方法[J]. 通信學報，2018，39（7）：81-91.

[20] 宋成，張亞東，王磊，等. 基于 DTW 交換查詢的軌跡隱私保護方案[J]. 北京郵電大學學報， 2018 （6）： 16.

[21] 吳云乘，陳紅，趙素云，等. 一種基于時空相關性的差分隱私軌跡保護機制[J]. 計算機學報，2018， 41（2）：309-322.

（責任編輯：江 艷）