基于網(wǎng)格偏移的分散位置隱私保護(hù)方法

徐俊儀

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州 510006）

0 引言

隨著移動(dòng)通信技術(shù)的快速發(fā)展，用戶能夠通過(guò)移動(dòng)設(shè)備精確定位所在的位置，基于位置的服務(wù)（LBS，Location-Based Service）將移動(dòng)通信設(shè)備的位置和其他信息整合起來(lái)，為用戶提供增值服務(wù)[1]。用戶獲得位置服務(wù)的過(guò)程[2]，將自身的位置信息泄露給了LBSs，或者攻擊者在這個(gè)過(guò)程中截獲用戶的請(qǐng)求獲取相應(yīng)的信息[3]。

目前針對(duì)位置服務(wù)的隱私保護(hù)方法主要有2種結(jié)構(gòu)：分布式點(diǎn)對(duì)點(diǎn)結(jié)構(gòu)和第三方匿名服務(wù)器結(jié)構(gòu)[4]。分布式點(diǎn)對(duì)點(diǎn)結(jié)構(gòu)是用戶之間進(jìn)行協(xié)作，在用戶端實(shí)現(xiàn)位置隱匿，將隱匿請(qǐng)求信息發(fā)送給LBSs獲取服務(wù)；第三方匿名服務(wù)器結(jié)構(gòu)是在用戶和LBSs之間添加一個(gè)匿名服務(wù)器（AS，Anonymous Server），用戶只需要將請(qǐng)求信息發(fā)送給AS，AS負(fù)責(zé)對(duì)用戶的請(qǐng)求進(jìn)行匿名處理，AS向LBSs獲取信息后，篩選符合用戶需求的內(nèi)容，發(fā)送給用戶[5]。

根據(jù)隱私保護(hù)方案技術(shù)的不同，主要分為群體協(xié)作技術(shù)[6-9]、空間匿名技術(shù)[10-11]、位置偏移和模糊技術(shù)[12-13]，以及基于密碼學(xué)技術(shù)[14-17]的隱私保護(hù)方案。模糊技術(shù)和位置偏移的方法比較簡(jiǎn)單，具有較好的服務(wù)質(zhì)量，安全性比較低；密碼學(xué)技術(shù)能夠保證較高的安全性，但是需要有比較強(qiáng)大的計(jì)算處理能力；群體協(xié)作技術(shù)對(duì)區(qū)域的人群和網(wǎng)絡(luò)有一定的要求。

當(dāng)需要使用第三方匿名服務(wù)器的時(shí)候，現(xiàn)有的多是采用密碼學(xué)工具來(lái)確保用戶請(qǐng)求的安全性，使得LBSs和AS難以獲得用戶的個(gè)人身份信息和查詢信息。但是加密操作存在比較大的計(jì)算量，查詢請(qǐng)求的過(guò)程比較長(zhǎng)，容易導(dǎo)致用戶服務(wù)質(zhì)量下降，如響應(yīng)時(shí)間的延長(zhǎng)。其次，現(xiàn)有的AS對(duì)用戶的請(qǐng)求進(jìn)行的k匿名，是在請(qǐng)求位置的附近搜索k-1個(gè)位置，k個(gè)位置滿足l-多樣性，在人群稀少的地圖區(qū)域，需要搜索較大的范圍才能確定匿名區(qū)域或者直接匿名失敗，因?yàn)樾枰獫M足k匿名的要求。因此本文提出一種基于網(wǎng)格偏移的分散位置隱私保護(hù)方法，使LBSs和AS難以獲得用戶的確切信息，并且在進(jìn)行查詢請(qǐng)求的時(shí)候有較低的時(shí)間開銷。為了有較高的位置分散度，在AS進(jìn)行匿名的時(shí)候，根據(jù)歷史查詢數(shù)據(jù)，選取查詢內(nèi)容不一樣的k-1個(gè)網(wǎng)格位置，并且保證選擇的位置盡量偏移匿名集合中的位置，將構(gòu)成匿名集合發(fā)送給LBSs進(jìn)行查詢。

1 系統(tǒng)結(jié)構(gòu)

本文所提方法的系統(tǒng)結(jié)構(gòu)如圖1所示，包含了四個(gè)部分，分別是用戶user，匿名服務(wù)器AS，功能服務(wù)器（Function Server，F(xiàn)S）和位置服務(wù)器 LBSs。

User是具備定位功能的移動(dòng)設(shè)備的用戶，能夠通過(guò)GPS獲取user所在的位置loc，user以loc為基礎(chǔ)，構(gòu)造一個(gè)矩形區(qū)域，計(jì)算偏移網(wǎng)格區(qū)域后將請(qǐng)求信息發(fā)送給AS。user向FS獲取周期更新的基礎(chǔ)網(wǎng)格Grid，Grid 可以表示為{（x0，y0）,r,TIME}，（x0,y0）表示了Grid的起始真實(shí)坐標(biāo)，r表示單個(gè)網(wǎng)格的寬度，TIME是Grid的標(biāo)識(shí)。

圖1基于不可信匿名服務(wù)器的系統(tǒng)結(jié)構(gòu)

AS是第三方匿名服務(wù)器，其收集和保存了用戶的請(qǐng)求信息，對(duì)于用戶的請(qǐng)求，負(fù)責(zé)在歷史查詢數(shù)據(jù)中搜索符合條件的請(qǐng)求信息構(gòu)造k匿名集合發(fā)送給LBSs，同時(shí)也負(fù)責(zé)對(duì)LBSs返回的數(shù)據(jù)進(jìn)行篩選。在本方法中，AS不可信。

FS的作用是周期更新基礎(chǔ)網(wǎng)格Grid的信息，對(duì)于User和LBSs獲取Grid的請(qǐng)求，獲取身份信息，響應(yīng)基礎(chǔ)網(wǎng)格信息Grid。

LBSs是一個(gè)大型的位置服務(wù)器，記錄了興趣點(diǎn)（Point Of Interest，POI）信息，負(fù)責(zé)對(duì)請(qǐng)求信息進(jìn)行響應(yīng)，將搜索的結(jié)果信息發(fā)送給AS進(jìn)行篩選。

2 方法的原理

本文方法包括了四個(gè)過(guò)程：user網(wǎng)格化處理、AS匿名處理、LBSs查詢結(jié)果、篩選結(jié)果。以下就每個(gè)過(guò)程進(jìn)行詳細(xì)說(shuō)明。

2.1 User網(wǎng)格化處理

User設(shè)定進(jìn)行查詢請(qǐng)求的參數(shù)，包括最小匿名區(qū)域MIN_AREA，查詢內(nèi)容類型type，隱私保護(hù)度k，查詢半徑radius。隱私保護(hù)度k指示了AS進(jìn)行匿名操作的時(shí)候總共需要k個(gè)查詢內(nèi)容不同的位置點(diǎn)，type說(shuō)明了查詢的類型，MIN_AREA規(guī)定了user需要生成的矩形區(qū)域面積應(yīng)不小于該值，radius表明了以查詢位置點(diǎn)為中心進(jìn)行搜索的范圍大小。

user向FS發(fā)送消息獲取基礎(chǔ)網(wǎng)格信息Grid。user通過(guò)移動(dòng)設(shè)備獲得自身準(zhǔn)確的位置loc，隨機(jī)生成一個(gè)值范圍為 0～1的數(shù)b，將 loc向隨機(jī)方向偏移 sqrt（MIN_AREA）*b 得到位置 loc’，根據(jù) loc’生成矩形區(qū)域Rect=（{x1,y1）（,x2,y2）}，（x1,y1）表示了矩形區(qū)域左下角的坐標(biāo)，（x2,y2）表示了矩形區(qū)域右上角的坐標(biāo)。

根據(jù)基礎(chǔ)網(wǎng)格Grid，位置（xi,y）i計(jì)算偏移網(wǎng)格坐標(biāo)（ci,r）i如公式（1）所示，其中r為基礎(chǔ)網(wǎng)格中的單個(gè)網(wǎng)格寬度。Rect根據(jù)公式（1）計(jì)算得到偏移網(wǎng)格坐標(biāo)Rect'，Rect'={（c1,r1）（,c2,r2）}。

將Rect'，用戶隱私保護(hù)度k，用戶請(qǐng)求類型type以及匿名化id，基礎(chǔ)網(wǎng)格標(biāo)識(shí)TIME和查詢半徑radius組成消息Mu_as發(fā)送給AS進(jìn)行匿名處理，Mu_as={id,Rect',type,k,TIME,radius}。

2.2 AS匿名處理

AS對(duì)收到的Mu_as消息提取偏移網(wǎng)格坐標(biāo)Rect'，隱私保護(hù)度k，用戶類型type，根據(jù)Rect'計(jì)算請(qǐng)求的中心坐標(biāo)（cu,ru），將[（cu,ru）,typeu]添加到γ，γ表示匿名后的位置集合。

在歷史數(shù)據(jù)庫(kù)中搜索與type不同的k-1個(gè)請(qǐng)求類型typei，0

任意一個(gè)n邊形都可以劃分為n-2個(gè)三角形，多邊形的面積通過(guò)計(jì)算每個(gè)三角形的面積求和來(lái)獲得，三角形的面積s根據(jù)公式（2）求得，p是三角形的半周長(zhǎng)，a,b,c分別是三角形的三條邊。

對(duì)typei（0

經(jīng)過(guò)計(jì)算可以得到k-1個(gè)請(qǐng)求類型不同的最分散的網(wǎng)格坐標(biāo)（ci,ri）,0

構(gòu)造 Mas_sp消息，Mas_sp={γ，TIME}，發(fā)送給 LBSs進(jìn)行查詢。

2.3 LBSs查詢結(jié)果

LBSs收到消息Mas_sp后，根據(jù)TIME向FS發(fā)送請(qǐng)求，獲取基礎(chǔ)網(wǎng)格信息Grid，將γ中每個(gè)typei的網(wǎng)格坐標(biāo)（ci，ri）還原為真實(shí)坐標(biāo)。

根據(jù)每個(gè)坐標(biāo)（xi，yi）和typei以及查詢半徑檢索s個(gè)POI結(jié)果，POIi={（xj,yj）,infoj}，0<=j

2.4 篩選結(jié)果

AS接收到Msp_as消息后，在歷史請(qǐng)求列表中找到請(qǐng)求用戶user所請(qǐng)求的類型typeu，將該類型的查詢結(jié)果網(wǎng)格集βu發(fā)送給 user，Mas_u={βu}。

User從Mas_u中提取POI的信息，根據(jù)基礎(chǔ)網(wǎng)格Grid，對(duì)偏移網(wǎng)格坐標(biāo)（ci,ri）根據(jù)公式（4）轉(zhuǎn)換為真實(shí)坐標(biāo)（xi,yi），由于提交給AS的是偏移后的位置坐標(biāo)，因此存在部分的POI是不符合user需求的，因此需要根據(jù)用戶的所在的位置（xu,yu）計(jì)算（xi,yi）距離用戶的遠(yuǎn)近，將不在radius范圍的POI舍棄，將符合的POI結(jié)合相關(guān)info展示給user。

3 安全性和實(shí)驗(yàn)結(jié)果分析

3.1 安全性分析

本文假設(shè)LBSs和AS會(huì)提供正常的服務(wù)響應(yīng)用戶的請(qǐng)求并且具備良好的對(duì)外安全性，但是會(huì)收集用戶的查詢請(qǐng)求，試圖通過(guò)數(shù)據(jù)挖掘的方法探索用戶的隱私信息。

對(duì)于AS而言，其能夠獲取的是用戶的id和網(wǎng)格偏移信息Rect’={（c1,r1）,（c2,r2）}，根據(jù)該網(wǎng)格信息，AS難以直接得知用戶的位置信息，只知道用戶id的請(qǐng)求內(nèi)容以及相對(duì)基礎(chǔ)網(wǎng)格的網(wǎng)格坐標(biāo)。如果AS惡意獲取了基礎(chǔ)網(wǎng)格Grid，由于user對(duì)位置進(jìn)行了偏移，并且發(fā)送給AS的是矩形區(qū)域，user可以在任何一個(gè)網(wǎng)格位置內(nèi)，因此AS能夠識(shí)別用戶所在位置的概率為，當(dāng)基礎(chǔ)網(wǎng)格劃分得越細(xì)，也即是r越小，用戶端的生成匿名區(qū)域相比MIN_AREA夠大，那么攻擊者需要更高的成本來(lái)識(shí)別用戶的準(zhǔn)確位置。

對(duì)于LBSs而言，由于AS對(duì)用戶id進(jìn)行了變換，其難以知道用戶的身份信息。由于請(qǐng)求信息經(jīng)過(guò)了AS的匿名處理，LBSs能夠確定用戶的請(qǐng)求內(nèi)容的概率為1/k。經(jīng)過(guò)了user的匿名區(qū)域生成和AS的匿名處理，LBSs識(shí)別用戶位置的概率為，當(dāng)k增大，能夠識(shí)別用戶位置的概率會(huì)逐漸變小，保護(hù)用戶的隱私信息。

3.2 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)使用Thomas Brinkhoff的移動(dòng)對(duì)象生成器（Network-based Generator of Moving Object）[18-19]，以城市Oldenburg生成隨機(jī)移動(dòng)對(duì)象，本文所提的方法和OPEG方法[14]以及ELPP[16]方法就時(shí)間開銷、網(wǎng)絡(luò)通信開銷和匿名位置分散度進(jìn)行實(shí)驗(yàn)比較。

本文方法使用Java語(yǔ)言實(shí)現(xiàn)，運(yùn)行在Windows 10操作系統(tǒng)上，CPU為Intel Core i7-7700。內(nèi)存為8G，默認(rèn)參數(shù)值如表1所示。

表1實(shí)驗(yàn)?zāi)J(rèn)參數(shù)

城市Oldenburg包含6105個(gè)節(jié)點(diǎn)，7035條邊，長(zhǎng)為23572，寬為26915。在該區(qū)域內(nèi)生隨機(jī)生成7326個(gè)POI位置?；谠搮^(qū)域生成3200個(gè)隨機(jī)位置，每個(gè)位置模擬請(qǐng)求位置服務(wù)。

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

（1）時(shí)間消耗

實(shí)驗(yàn)對(duì)比了本文方法和OPEG以及ELPP方法所需的時(shí)間。時(shí)間指的是用戶發(fā)送查詢請(qǐng)求到用戶獲取查詢結(jié)果所消耗的時(shí)間。如圖2所示，隨著k值的增加，本文方法消耗的時(shí)間逐漸上升，而ELPP方法并沒(méi)有隨著k值的增加而增加，原因是ELPP方法在AS端進(jìn)行用戶匿名操作的時(shí)候，只需要在歷史查詢數(shù)據(jù)中選擇相同Hilbert值的其他位置即可，而本文方法需要計(jì)算多邊形的面積確定位置之間的分散度，隨著k值的增加需要計(jì)算更多的三角形面積。而OPEG方法使用保序加密，沒(méi)有使用k匿名，因此其時(shí)間消耗和k不相關(guān)，需要使用更多的時(shí)間來(lái)加解密信息。

圖2時(shí)間開銷的對(duì)比

（2）網(wǎng)絡(luò)通信消耗

網(wǎng)絡(luò)通信消耗指的是網(wǎng)絡(luò)上傳輸信息的數(shù)據(jù)量大小，由于是模擬位置請(qǐng)求過(guò)程和查詢過(guò)程，而數(shù)據(jù)量主要指的是LBSs對(duì)查詢結(jié)果返回的POI數(shù)量，因此對(duì)比不同方法返回給AS的POI數(shù)量。

圖3網(wǎng)絡(luò)通信開銷對(duì)比

如圖3所示，由于本文方法生成的k匿名區(qū)域是分散的，因此之間的距離更遠(yuǎn)，對(duì)于每個(gè)位置都需要在搜索半徑之內(nèi)進(jìn)行POI的查找，搜索的結(jié)果會(huì)更多；而ELPP方法匿名位置點(diǎn)比較集中，因此有重復(fù)的查詢結(jié)果，能夠有相對(duì)較少查詢結(jié)果；OPEG方法的并不使用k匿名，而是對(duì)查詢結(jié)果直接加密來(lái)保護(hù)隱私信息，其網(wǎng)絡(luò)通信開銷小。

（3）匿名位置分散度

本文方法在構(gòu)造k匿名的時(shí)候，考慮了匿名位置點(diǎn)的分散程度，分散度越高的位置集合具有更高的面積，所選出來(lái)的位置能夠分散在各個(gè)地方，而不是聚簇在一個(gè)范圍之內(nèi)，從而能夠提高用戶的隱私保護(hù)程度，由于OPEG并沒(méi)有k匿名的過(guò)程，因此就匿名面積和ELPP進(jìn)行比較。計(jì)算比值，SM和 SMELPP分別是本文方法和ELPP方法形成的匿名區(qū)域面積，β值越大，表示本文方法比ELPP匿名產(chǎn)生的位置更分散。

圖4位置分散度比值

如圖4所示，隨著k的值逐漸增大，β值逐漸增大，表明本文方法生成的匿名集合相比ELPP方法有更大的面積，本文方法匿名位置的分布相對(duì)ELPP更加分散，而不是聚簇在一個(gè)較小的區(qū)域內(nèi)，當(dāng)k的值為10的時(shí)候，本文方法比ELPP的匿名面積提高了11%，說(shuō)明本文方法相對(duì)ELPP方法能夠產(chǎn)生更加分散的匿名位置集合。

4 結(jié)語(yǔ)

本文提出一種基于網(wǎng)格偏移的分散位置隱私保護(hù)方法。文獻(xiàn)[14]和文獻(xiàn)[16]為了防止用戶的隱私信息泄露給匿名服務(wù)器和位置服務(wù)器，需要較大的時(shí)間開銷，產(chǎn)生的匿名位置集合是集中的且容易匿名請(qǐng)求內(nèi)容單一。本文所提方法根據(jù)周期更新的網(wǎng)格信息計(jì)算偏移網(wǎng)格區(qū)域，匿名服務(wù)器根據(jù)用戶查詢請(qǐng)求選擇分散的、請(qǐng)求內(nèi)容多樣的網(wǎng)格坐標(biāo)構(gòu)成集合，使匿名服務(wù)器進(jìn)行匿名處理和位置服務(wù)器進(jìn)行匿名查詢的時(shí)候，難以得知用戶的隱私信息，并且有較低的時(shí)間開銷和分布更加分散的匿名位置集合。