耿雪冬

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

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

DOI：10. 11907/rjdk. 192030 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP309.7 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

1 軌跡隱私保護(hù)模型及相關(guān)定義

1.1 系統(tǒng)模型

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

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

攜帶智能終端設(shè)備的用戶可通過多種方式接入網(wǎng)絡(luò)，并通過響應(yīng)設(shè)備在不同時(shí)間、不同地點(diǎn)請(qǐng)求不同的服務(wù)。

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

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

1.2 相關(guān)定義

（2） 軌跡間距離。設(shè)軌跡泛化完成后[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匿名。設(shè)有多條軌跡的集合S，當(dāng)集合S中某條軌跡與其它k-1條軌跡不可分時(shí)，則集合S滿足軌跡k匿名。

2 隱私保護(hù)方法

2.1 MDF-Nearest 匿名集生成方法

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

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

MDF-Nearest算法

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

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

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

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

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

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

3 實(shí)驗(yàn)及分析

3.1 試驗(yàn)設(shè)備參數(shù)

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

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

本文通過試驗(yàn)驗(yàn)證算法有效性，從響應(yīng)時(shí)間和隱私保護(hù)度兩方面與不同k值的傳統(tǒng)k-匿名算法進(jìn)行比較，傳統(tǒng)k-匿名保護(hù)算法的隱私保護(hù)度指標(biāo)僅與k值有關(guān)。兩種算法對(duì)比結(jié)果如圖2所示。

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

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

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

4 結(jié)語

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

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

參考文獻(xiàn)：

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

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

[3] 趙婧，張淵，李興華，等. 基于軌跡頻率抑制的軌跡隱私保護(hù)方法[J]. 計(jì)算機(jī)學(xué)報(bào)，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： 一種移動(dòng)社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法[J]. 計(jì)算機(jī)學(xué)報(bào)， 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] 李鳳華，張翠，牛犇，等. 高效的軌跡隱私保護(hù)方案[J]. 通信學(xué)報(bào)，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-匿名隱私保護(hù)算法[J]. 計(jì)算機(jī)應(yīng)用研究，2017 （11）： 3421-3423+3427.

[17] 周凱，彭長根，何建瓊，等. 可證明安全的 LBS 中連續(xù)查詢的軌跡隱私保護(hù)方案[J]. 信息網(wǎng)絡(luò)安全， 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] 張少波，劉琴，王國軍. 基于位置混淆的軌跡隱私保護(hù)方法[J]. 通信學(xué)報(bào)，2018，39（7）：81-91.

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

[21] 吳云乘，陳紅，趙素云，等. 一種基于時(shí)空相關(guān)性的差分隱私軌跡保護(hù)機(jī)制[J]. 計(jì)算機(jī)學(xué)報(bào)，2018， 41（2）：309-322.

（責(zé)任編輯：江 艷）