摘要：隨著移動(dòng)通信技術(shù)的不斷發(fā)展，人們?cè)谑褂梦恢梅?wù)（Location Based Services，LBS）的同時(shí)，用戶的位置軌跡等敏感信息也會(huì)發(fā)生泄露。為了保護(hù)包含用戶敏感信息的位置軌跡數(shù)據(jù)的安全，文章設(shè)計(jì)了一種滿足差分隱私位置軌跡發(fā)布方法。首先，利用軌跡數(shù)據(jù)構(gòu)造位置軌跡流量圖，在流量圖中添加差分隱私噪聲；其次，使用滿足一致性特性的后置調(diào)節(jié)算法對(duì)包含噪聲的軌跡數(shù)據(jù)進(jìn)行一致性調(diào)節(jié)。通過真實(shí)的路網(wǎng)驗(yàn)證可以看出，該方法能夠滿足處理大規(guī)模路網(wǎng)的能力，且經(jīng)過一致性調(diào)節(jié)算法優(yōu)化之后，發(fā)布誤差縮小了約20%。

關(guān)鍵詞：位置服務(wù)；位置軌跡；差分隱私；一致性調(diào)節(jié)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

0 引言

隨著移動(dòng)通信技術(shù)的不斷發(fā)展，LBS得到廣泛應(yīng)用。人們?cè)谑褂肔BS的過程中，往往需要和LBS提供商進(jìn)行信息交互，這些交互的信息包含的內(nèi)容涉及大量用戶的隱私，例如：位置、軌跡、時(shí)間等［1］。在用戶和LBS提供商進(jìn)行信息交互的過程中，用戶的數(shù)據(jù)可能會(huì)在交互的過程中泄露，隱私數(shù)據(jù)中隱含了用戶的日常的出行、位置和一些行為習(xí)慣等數(shù)據(jù)［2］。因此，為了保護(hù)用戶的隱私，我們需要對(duì)數(shù)據(jù)進(jìn)行保護(hù)后發(fā)布。

Qardaji等［3］通過構(gòu)建分區(qū)層次結(jié)構(gòu)來選擇正確的分區(qū)粒度，以平衡噪聲誤差和非均勻性誤差，同時(shí)使用一種新的自適應(yīng)網(wǎng)格方法來改善網(wǎng)格粒度優(yōu)化機(jī)制，但無法從根本上解決該矛盾。Hay等［4］為了解決直方圖發(fā)布場景中的不一致性問題，提出了一種后置處理方案，但由于場景不同，無法適用于本文的路網(wǎng)環(huán)境。

因此，本文在以往研究的基礎(chǔ)上，將實(shí)際城市路網(wǎng)抽象成有向圖模型，并向圖中引入了多個(gè)輔助虛擬節(jié)來中和網(wǎng)格粒度不均勻的情況；結(jié)合拉普拉斯機(jī)制，通過改變隱私預(yù)算配額，降低總體節(jié)點(diǎn)方差，同時(shí)提出滿足差分隱私流量圖生成算法和一致性調(diào)節(jié)算法。通過在真實(shí)路網(wǎng)上驗(yàn)證本文提出的算法，結(jié)果表明本文的算法能夠有效解決路網(wǎng)軌跡發(fā)布的隱私保護(hù)問題。

1 研究背景

Cao等［5］提出了軌跡差分隱私模型，根據(jù)用戶的隱私需求保護(hù)任意長度L的軌跡數(shù)據(jù)，并提供個(gè)性化的隱私保護(hù)。Shokri等［6］的攻擊者貝葉斯模型旨在優(yōu)化隱私和效用之間的權(quán)衡，提出了一種計(jì)算最優(yōu)噪聲產(chǎn)生機(jī)制的方法，將效用約束和隱私目標(biāo)形式化為線性優(yōu)化問題。研究人員使用線性規(guī)劃計(jì)算最佳噪聲機(jī)制，并考慮在給定隱私級(jí)別優(yōu)化效用的反向問題。此外，Hay 等［4］使用分層方法回答直方圖查詢，并使用約束推理技術(shù)調(diào)查噪聲添加導(dǎo)致的數(shù)據(jù)不一致問題。Ma等［7］提出RPTR機(jī)制是一種基于差異隱私的實(shí)時(shí)跟蹤信息發(fā)布機(jī)制。在預(yù)測(cè)計(jì)算中，使用了基于用戶位置轉(zhuǎn)移概率矩陣的集合卡爾曼濾波器，以額外的時(shí)間代價(jià)換取數(shù)據(jù)精度。

Chen等［8］使用原始軌跡構(gòu)建了帶噪前綴樹，通過在前綴樹節(jié)點(diǎn)的計(jì)數(shù)值中加入了滿足拉普拉斯分布的噪聲數(shù)據(jù)，從而確保用戶的軌跡隱私。然而，由于前綴樹的特點(diǎn)，隨著樹的增大，樹中的節(jié)點(diǎn)也會(huì)猛增，導(dǎo)致數(shù)據(jù)的可用性嚴(yán)重降低。Chen等［9］為了消除軌跡數(shù)據(jù)中的公共前綴，利用指數(shù)機(jī)制對(duì)軌跡進(jìn)行隱私保護(hù)，很好地解決了公共前綴對(duì)軌跡數(shù)據(jù)發(fā)布的影響。張雙越等［10］通過將路網(wǎng)信息構(gòu)造一個(gè)帶權(quán)有向圖，通過向軌跡流量圖中加入滿足拉普拉斯分布的噪聲數(shù)據(jù)，實(shí)現(xiàn)差分隱私，最后利用后置調(diào)節(jié)使得發(fā)布數(shù)據(jù)滿足一致性特征，減少了發(fā)布誤差。

2 滿足差分隱私的位置軌跡流量發(fā)布方法

通過使用有向圖G=（V，E，Q）模擬路網(wǎng)空間，V是路網(wǎng)中路口集合，E表示路網(wǎng)中的街道集合，Q是邊的權(quán)重集合，軌跡流量圖中要確保每個(gè)起止節(jié)點(diǎn)的出入度相等，即每個(gè)起止路口的出入流量相同。同時(shí)，為了保證路網(wǎng)的粒度平衡，本文通過引入若干個(gè)虛擬節(jié)組成虛擬路口集合，集合中的虛擬節(jié)點(diǎn)出入流量相等，確保不影響真實(shí)流量，最后對(duì)加噪后的流量圖進(jìn)行改進(jìn)的最小二乘法后置優(yōu)化。

2.1 基本概念

定義1（軌跡流量圖）：將城市道路抽象成一個(gè)有向圖G=（V，E，Q），其中V代表道路網(wǎng)絡(luò)中所有交叉口的集合，E代表道路網(wǎng)絡(luò)所有相鄰交叉口之間的路段集合，Q代表道路網(wǎng)絡(luò)內(nèi)所有軌跡的集合。根據(jù)軌跡集合Q得出每條邊的權(quán)值，然后構(gòu)成有向加權(quán)圖，流量矩陣記為X∈R|V|×|V|，X為軌跡流量圖。

定義2（差分隱私）：假設(shè)存在兩個(gè)相鄰數(shù)據(jù)集（D和D′）和一個(gè)隨機(jī)算法M，若算法M滿足Pr［M（D）∈S］≤exp（ε）×Pr［M（D′）∈S］，則稱算法M滿足ε-差分隱私保護(hù)。其中，S表示算法M所有可能的輸出構(gòu)成的集合，參數(shù)ε稱為隱私保護(hù)預(yù)算。從定義可知，ε越小，標(biāo)識(shí)隱私保護(hù)級(jí)別越高，數(shù)據(jù)效用越高。

定義4（拉普拉斯機(jī)制）：拉普拉斯作一種最為常見也是最基本的差分隱私的噪聲機(jī)制之一，對(duì)于任意函數(shù)f：D→Rd，拉普拉斯機(jī)制實(shí)現(xiàn)差分隱私保護(hù)的過程可表示如下：

2.2 滿足差分隱私的軌跡流量圖發(fā)布方法

差分隱私流量圖發(fā)布算法過程如算法1所示。

算法1：差分隱私軌跡流量發(fā)布

輸入：A，D，ε //路網(wǎng)鄰接矩陣A，軌跡數(shù)據(jù)集D，隱私預(yù)算ε

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

本文使用Thomas Brinkhoff路網(wǎng)生成器將oldenburgGen路網(wǎng)結(jié)構(gòu)中的一小片區(qū)域抽象成有向圖，圖中的交叉點(diǎn)為路口，各路口之間的邊即為有向圖的邊，如圖1所示。

由圖1展示的oldenburgGen路網(wǎng)可以看出，路網(wǎng)網(wǎng)格粒度分布不均勻，這會(huì)導(dǎo)致兩種極端現(xiàn)象。一是網(wǎng)格粒度過大時(shí)，查詢結(jié)果的精確度就會(huì)降低，難以滿足應(yīng)用需求。二是網(wǎng)格的粒度過小時(shí)，大多數(shù)網(wǎng)格數(shù)據(jù)稀疏，導(dǎo)致誤差累積嚴(yán)重，查詢精度會(huì)受覆蓋面積影響，覆蓋面積越大，查詢精度越差。同時(shí)，圖中抽象出的包含6個(gè)節(jié)點(diǎn)的有向圖結(jié)構(gòu)，有向圖的邊權(quán)值代表每個(gè)路口之間的軌跡流量，為了保護(hù)每個(gè)路段的軌跡流量數(shù)據(jù)，通過將軌跡流量添加噪聲，得到加噪的有向圖。然而，添加噪聲會(huì)導(dǎo)致有向圖路口的出入流量也會(huì)產(chǎn)生不一致的問題，如圖2所示。

圖2中B路口添加噪聲之前B點(diǎn)的出度和入度都是4，當(dāng)添加噪聲之后，該點(diǎn)的入度是2，出度是4。然而這種與實(shí)際不符的情況往往會(huì)增大軌跡流量發(fā)布誤差。所以，本文通過使用增加虛擬節(jié)點(diǎn)集合來動(dòng)態(tài)調(diào)整路網(wǎng)的網(wǎng)格粒度，從而解決數(shù)據(jù)使用誤差大的問題；同時(shí)參考求解凸優(yōu)化問題，采用最小二乘法對(duì)滿足差分隱私的軌跡流量進(jìn)行后置處理來解決節(jié)點(diǎn)出入度在加噪前后不符的問題。

實(shí)驗(yàn)環(huán)境：Inter（R） CoreTMi5-8250U @ 1.6GHz（8 CPUs）， 16G，64位Windows操作系統(tǒng)，使用MATLAB實(shí)現(xiàn)。本實(shí)驗(yàn)中使用的數(shù)據(jù)集是Oldenburg、San Joaquin、San Francisco Bay Area 3個(gè)城市。通過由Brinkhoff基于路網(wǎng)的軌跡生成器生成對(duì)應(yīng)3個(gè)城市的軌跡數(shù)據(jù)。其中，本實(shí)驗(yàn)3個(gè)城市的路網(wǎng)數(shù)據(jù)信息如表1所示。

3個(gè)城市的實(shí)驗(yàn)結(jié)果表明，標(biāo)準(zhǔn)誤差隨著隱私預(yù)算的增加而減少，隨著隱私預(yù)算的增加，軌跡流量添加的噪聲也會(huì)隨之減少。同時(shí)能夠看出，經(jīng)過一致性調(diào)節(jié)后的誤差也有明顯的變化，比調(diào)節(jié)前相比減少了20%左右的誤差。

4 結(jié)語

本文根據(jù)路網(wǎng)的特點(diǎn)，用帶權(quán)的有向圖來構(gòu)造路網(wǎng)流量圖，然后對(duì)路網(wǎng)中的軌跡添加服從拉普拉斯分布的噪聲。將單一的結(jié)果轉(zhuǎn)變成概率結(jié)果，從而保證了路網(wǎng)軌跡發(fā)布的差分隱私。最后本文利用最小二乘法來抑制噪聲的輸出，提高了數(shù)據(jù)的可用性。然而，最小二乘法一致性約束帶來的計(jì)算開銷較大，無法滿足對(duì)時(shí)效性有極高要求的實(shí)時(shí)軌跡發(fā)布場景。下一步，筆者將繼續(xù)研究更好、更合適的算法。

參考文獻(xiàn)

［1］BAO J， HE T F， RUAN S J， et al. Planning bike lanesbased on sharing-bikes’ trajectories： The 23rd ACMSIGKDD International Conference on Knowledge Discoveryand Data Mining， August 13-17， 2017［C］. New York： ACM， 2017.

［2］YUAN J， ZHENG Y， ZHANG C Y， et al. T-drive： driving directions based on taxi trajectories： The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems，November 2-5， 2010［C］.New York： ACM， 2010.

［3］QARDAJI W， YANG W N， LI N H. Differentially private grids for geospatial data： The 29th IEEE International Conference on Data Engineering， April 8-12， 2013［C］. New York： IEEE， 2013.

［4］HAY M， RASTOGI V， MIKLAU G， et al. Boosting the accuracy of differentially private histograms through consistency［J］. Proceedings of the VLDB Endowment， 2010（1/2）： 1021- 1032.

［5］CAO Y， YOSHIKAWA M. Differentially private real-time data release over infinite trajectory streams： 16th IEEE International Conference on Mobile Data Management， June15-18， 2015 ［C］. New York： IEEE， 2015.

［6］SHOKRI R，THEODORAKOPOULOS G， TRONCOSO C， et al. Protecting location privacy： optimal strategy against localization attacks： Proceedings of the 2012 ACM Conference on Computer and Communications Security，October 16-18 ，2012 ［C］. Raleigh： ACM， 2012.

［7］MA Z， ZHANG T， LIU X. Real-time privacy-preserving data release over vehicle trajectory ［J］. IEEE Transactions on Vehicular Technology， 2019（8）： 8091-8102.

［8］CHEN R， FUNG B， DESAI B. Differentially private trajectory data publication：Computer Science，10.48550/ arXiv：1112.2020［P］. 2011.

［9］CHEN R， CS G， CASTELLUCCIA C. Differentially private sequential data publication via variable-length n-grams： Proceedings of the ACM Conference on Computer and Communications Security， October 16-18， 2012［C］. New York： ACM， 2012.

［10］張雙越，蔡劍平，田豐，等.差分隱私下滿足一致性的軌跡流量發(fā)布方法［J］.計(jì)算機(jī)科學(xué)與探索，2018（12）：11.

Traffic publishing method of location trajectories satisfying differential privacy

PanHongzhi

（School of Information and Artificial Intelligence， Anhui Business College of Vocational Technology， Wuhu 241002， China）

Abstract：With the continuous development of mobile communication technology， when people use Location Based Services （LBS）， sensitive information such as user’s location track will also be leaked. In order to protect the security of the location track data containing user sensitive information， a location track publishing method satisfying differential privacy is designed. First， we use the trajectory data to construct the position trajectory flow chart， add differential privacy noise to the flow chart， and then use the post-adjustment algorithm that meets the consistency characteristics to adjust the consistency of the trajectory data containing noise. Finally， through the real road network verification， it can be seen that this method can meet the ability to deal with large-scale road network， and after the consistency adjustment algorithm optimization， the publishing error is reduced by about 20%.

Key words： location service; position track; differential privacy; consistency adjustment