面向位置服務(wù)的用戶隱私保護(hù)

裴媛媛，石潤(rùn)華，仲 紅，張 順

（1.安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230039；2.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601）

面向位置服務(wù)的用戶隱私保護(hù)

裴媛媛1，2，石潤(rùn)華1，2，仲 紅1，2，張 順1，2

（1.安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230039；2.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601）

傳感器技術(shù)和移動(dòng)通信設(shè)備的發(fā)展使位置服務(wù)（LBS）得到廣泛應(yīng)用。與此同時(shí)，在服務(wù)過(guò)程中所產(chǎn)生的隱私問(wèn)題也成為關(guān)注的焦點(diǎn)。為此，針對(duì)LBS位置隱私的保護(hù)問(wèn)題，構(gòu)造一個(gè)用戶協(xié)作的分布式模型，并設(shè)計(jì)一種新的隱私保護(hù)方案。在構(gòu)建匿名區(qū)時(shí)，使用貝葉斯Nash均衡思想以及安全多方求和技術(shù)以保證用戶信息的隱私。在處理查詢結(jié)果時(shí)，引入Voronoi圖的方法以提高查詢效率。分析結(jié)果表明，該方案考慮了用戶節(jié)點(diǎn)自私和不可信的情況，并且簡(jiǎn)化了查詢過(guò)程，在保護(hù)隱私的同時(shí)可提高服務(wù)的整體性能。

位置隱私；用戶協(xié)作；貝葉斯Nash均衡；安全多方求和；Voronoi圖

DO I：10.3969/j.issn.1000-3428.2015.10.005

1 概述

隨著無(wú)線通信和移動(dòng)技術(shù)的飛速發(fā)展，位置服務(wù)（Location-based Service，LBS）應(yīng)運(yùn)而生。LBS就是將移動(dòng)設(shè)備（如智能手機(jī)、平板電腦等）的位置和其他信息整合起來(lái)，為用戶提供增值服務(wù)［1］，其主要的應(yīng)用背景有：緊急救援服務(wù)，如“查詢離我最近的醫(yī)院”；信息娛樂(lè)服務(wù)，如“查詢離我最近的 KTV”；交通導(dǎo)航服務(wù)，如“根據(jù)行駛道路的擁擠狀況選擇最優(yōu)路徑”；廣告分發(fā)服務(wù)，如“向某超市餐館外100 m的用戶發(fā)送電子優(yōu)惠券”。顯而易見(jiàn)，這些服務(wù)能給人們的生活帶來(lái)便利，但人們?cè)谙硎芨咂焚|(zhì)服務(wù)的同時(shí)，也可能泄露了部分個(gè)人隱私。例如，攻擊者通過(guò)竊聽(tīng)，獲取用戶的位置和查詢內(nèi)容推斷出用戶的身份，進(jìn)而獲得更多的用戶隱私信息。換言之，人們的隱私和安全受到了威脅。一般地，服務(wù)質(zhì)量和隱

私保護(hù)程度是一對(duì)矛盾體，提供精確位置可享受高質(zhì)量的服務(wù)，而隱私保護(hù)又要求不能暴露確定位置。因此，如何在這兩點(diǎn)之間達(dá)到一個(gè)平衡，是多數(shù)研究者所要思考的問(wèn)題。除此之外，文獻(xiàn)［1］還列出了在研究位置隱私保護(hù)過(guò)程中面臨的其他挑戰(zhàn)，也都是在設(shè)計(jì)方案時(shí)需要考慮的。

近年來(lái)，關(guān)于位置隱私保護(hù)的研究最經(jīng)典的模型當(dāng)屬k-匿名模型，多數(shù)研究也是基于此基礎(chǔ)之上，且采用中心服務(wù)器結(jié)構(gòu)。該結(jié)構(gòu)就是在用戶和服務(wù)提供商之間加入了一個(gè)可信第三方，即可信匿名服務(wù)器，用于將用戶精確的位置模糊處理，產(chǎn)生一個(gè)保護(hù)用戶位置的區(qū)域。

中心服務(wù)器結(jié)構(gòu)降低了客戶端的負(fù)擔(dān)，但其缺點(diǎn)也很明顯：（1）位置匿名服務(wù)器可能成為系統(tǒng)處理上的瓶頸；（2）當(dāng)位置匿名服務(wù)器變得不可信時(shí)，將會(huì)導(dǎo)致極為嚴(yán)重的后果。為此，本文提出一個(gè)無(wú)可信第三方，通過(guò)用戶之間協(xié)作完成的分布式位置隱私保護(hù)方案。

2 研究進(jìn)展

在位置隱私保護(hù)中有3種常見(jiàn)的設(shè)計(jì)思想：k-匿名，混合區(qū)，虛擬節(jié)點(diǎn)。

（1）k-匿名：使用包含 k個(gè)節(jié)點(diǎn)的一塊區(qū)域來(lái)代替某一具體位置發(fā)送給服務(wù)提供者，以使得攻擊者沒(méi)有辦法確定用戶的真實(shí)位置。文獻(xiàn)［2］提出k-匿名的概念，使用到關(guān)系數(shù)據(jù)庫(kù)的數(shù)據(jù)隱私保護(hù)中。文獻(xiàn)［3］將 k-匿名的概念應(yīng)用到位置隱私上來(lái)，提出位置k-匿名。文獻(xiàn)［4］提出個(gè)性化 k-匿名算法，針對(duì)不同應(yīng)用背景的隱私需求，但它只簡(jiǎn)單介紹個(gè)性化位置 k-匿名的基本概念和設(shè)計(jì)的基本思想。所以，文獻(xiàn)［5］繼續(xù)完善，提出一套完整的體系結(jié)構(gòu)。文獻(xiàn)［6］使用博弈論的方法獲取 k-匿名，解決了節(jié)點(diǎn)密度低時(shí)如何保證達(dá)到 k-匿名的問(wèn)題。

（2）混合區(qū)：指定一個(gè)區(qū)域作為混合區(qū)，在進(jìn)入該區(qū)域內(nèi)所有節(jié)點(diǎn)同時(shí)改變自己的假名，之后，監(jiān)聽(tīng)者則不能再繼續(xù)跟蹤下去，因?yàn)樗鼪](méi)有辦法確定新舊假名之間的映射。關(guān)于這方面的研究最初是文獻(xiàn)［7-8］提出混合區(qū)的結(jié)構(gòu)，并使用熵的概念來(lái)分析其隱私性。文獻(xiàn)［9］提出了一個(gè)時(shí)空數(shù)據(jù)的 k-匿名模型，它將混合區(qū)思想與k-匿名結(jié)合起來(lái)，對(duì)前面的混合區(qū)模型進(jìn)行完善，但它們都沒(méi)考慮實(shí)際的道路網(wǎng)絡(luò)分布情況。文獻(xiàn)［10］提出基于道路網(wǎng)絡(luò)的一個(gè)混合區(qū)方案，它將混合區(qū)由理論矩形變化到道路網(wǎng)絡(luò)并加入了多種影響因素。文獻(xiàn)［11］提出流量感知多混合區(qū)的放置算法，考慮了道路流量分布不均勻情況下，在何處安放混合區(qū)，以使其效益達(dá)到最大的問(wèn)題。文獻(xiàn)［12］提出分布式混合區(qū)算法，它是從用戶角度出發(fā)，根據(jù)博弈論的思想，決定是否加入某混合區(qū)，使自已利益最大化。

（3）虛擬節(jié)點(diǎn)：指產(chǎn)生假的位置信息，代替真實(shí)位置發(fā)送給LBS，或者與真實(shí)位置一起發(fā)送過(guò)去，達(dá)到混淆的目的。文獻(xiàn)［13］提出虛擬節(jié)點(diǎn)的匿名技術(shù)，但它沒(méi)有具體考慮虛擬節(jié)點(diǎn)移動(dòng)軌跡的限制。文獻(xiàn)［14］使用虛擬節(jié)點(diǎn)保護(hù)移動(dòng)軌跡，解決了上面的問(wèn)題，且提出了 2種生成虛擬軌跡的方案。2010年，文獻(xiàn)［15］把虛擬節(jié)點(diǎn)應(yīng)用到一個(gè)混合匿名系統(tǒng)中，這樣減少了用戶操作并提高系統(tǒng)性能。文獻(xiàn)［16］提出一個(gè)關(guān)于隱私保護(hù)的混合算法，在模糊區(qū)域產(chǎn)生過(guò)程中加入虛擬節(jié)點(diǎn)以達(dá)到k-匿名。目前多數(shù)關(guān)于虛擬節(jié)點(diǎn)的方法，是與 k-匿名或混合區(qū)的思想結(jié)合起來(lái)，以達(dá)到更為滿意的位置隱私保護(hù)的效果。

另外，還有基于PIR的位置隱私保護(hù)算法，如文獻(xiàn)［17-18］，通過(guò)對(duì)查詢進(jìn)行加密以及數(shù)據(jù)庫(kù)記錄置亂等方式進(jìn)行。但由于其加解密過(guò)程中產(chǎn)生的計(jì)算和通信代價(jià)都很大，因此進(jìn)一步的研究并不多。

上述3種主要思想在已有研究中都存在一些問(wèn)題。如混合區(qū)中每個(gè)用戶假名的變換、保存狀態(tài)信息以及通知應(yīng)用服務(wù)器新用戶的到達(dá)等，需要花費(fèi)不少代價(jià)，而且可能導(dǎo)致服務(wù)質(zhì)量的下降。單個(gè)節(jié)點(diǎn)產(chǎn)生虛擬節(jié)點(diǎn)，利用假位置查詢，則隱私性不高。k-匿名的使用大多需要借助可信第三方。因此，本文在k-匿名方法的基礎(chǔ)上，通過(guò)用戶協(xié)作的方式，并以虛擬節(jié)點(diǎn)為輔助，彌補(bǔ)了上述設(shè)計(jì)思想中的不足，并且使隱私匿名度得到提高。

3 本文方案

本文提出的方案是基于分布式結(jié)構(gòu)，包括客戶端和服務(wù)提供商兩部分。具體如圖1所示，不同于原先的獨(dú)立式結(jié)構(gòu)，它考慮了全局信息，通過(guò)用戶之間的協(xié)作來(lái)完成，主要涉及三方面內(nèi)容：（1）如何找到滿足用戶匿名需求的節(jié)點(diǎn)數(shù)；（2）怎樣求取多個(gè)節(jié)點(diǎn)的密度中心作為錨點(diǎn)；（3）怎樣才能方便地獲得用戶的查詢結(jié)果候選集以及最后篩選出精確解。

圖1 分布式用戶查詢服務(wù)模型

（1）用戶模型：對(duì)于用戶來(lái)說(shuō)，需要保證攻擊者是沒(méi)有辦法把他的位置以及查詢結(jié)果與其標(biāo)識(shí)符具體的對(duì)應(yīng)起來(lái)。本文通過(guò)選取一個(gè)錨點(diǎn)，以此隱藏用戶真實(shí)的位置信息。進(jìn)而，所有用戶的查詢內(nèi)容都與錨點(diǎn)的坐標(biāo)位置對(duì)應(yīng)起來(lái)。例如，假設(shè)用戶U1，U2，…，Un，各點(diǎn)真實(shí)位置坐標(biāo)分別為（χ1，y1），（χ2，y2），…，（χn，yn），其中所有用戶協(xié)作選取的錨點(diǎn)U0坐標(biāo)為（χ0，y0）。假定原查詢請(qǐng)求分別為：U1：（（χ1，y1），Initial-Q1），U2：（（χ2，y2），Initial-Q2），…，Un：（（χn，yn），Initial-Qn）。則有了錨點(diǎn) U0后實(shí)際查詢請(qǐng)求分別為：U1：（（χ0，y0），Q1），U2：（（χ0，y0），Q2），…，Un：（（χ0，y0），Qn）。其中Qi定義如下：

定義1 查詢Qi定義為：Qi=｛（χ0，y0），t，reqi，mi｝，其中，（χ0，y0）表示查詢輸入的位置信息，在本文方案中指的是錨點(diǎn)坐標(biāo)；t表示提出查詢的時(shí)刻；reqi表示第i個(gè)用戶請(qǐng)求查詢的內(nèi)容；mi表示查詢處理過(guò)程中返回的候選集內(nèi)節(jié)點(diǎn)個(gè)數(shù)，mi的值越大，返回的節(jié)點(diǎn)個(gè)數(shù)越多，也越有利于用戶找到最優(yōu)的結(jié)果，但處理效率會(huì)降低，這由用戶具體權(quán)衡。

定義2 關(guān)于匿名區(qū)k-AR的表示如下：k-AR=｛gid，k，anchor｝，其中，gid表示匿名組的編號(hào)；k表示匿名區(qū)內(nèi)用戶節(jié)點(diǎn)的個(gè)數(shù)；anchor表示匿名區(qū)的錨點(diǎn)，是通過(guò)求取區(qū)域的密度中心獲得的，每個(gè)用戶都可使用該位置提出服務(wù)請(qǐng)求。

（2）攻擊者模型：攻擊者可以在網(wǎng)絡(luò)中竊聽(tīng)到節(jié)點(diǎn)的查詢內(nèi)容和返回的查詢結(jié)果，但不可以篡改。然后再根據(jù)事先獲取的一些知識(shí)，以一定的概率推理出某個(gè)查詢對(duì)應(yīng)的用戶隱私信息。

3.1 查詢預(yù)處理

假定用戶U1作為算法的發(fā)起者，發(fā)出尋找用戶節(jié)點(diǎn)共同構(gòu)建匿名組的請(qǐng)求Discoνer，如算法1所示。U1首先生成新的組編號(hào) gid，發(fā)送廣播消息＜gid，h＞，h初始設(shè)為一個(gè)最大值，表示路由轉(zhuǎn)發(fā)的最大跳數(shù)。之后，等待鄰居節(jié)點(diǎn)的響應(yīng)＜res，Ui＞，把發(fā)回響應(yīng)消息的用戶節(jié)點(diǎn) Ui加入集合 S中且跳數(shù)更改為h-1，繼而判斷或者h(yuǎn)=0時(shí)，查找用戶節(jié)點(diǎn)的步驟完成，否則利用其相鄰節(jié)點(diǎn)進(jìn)行下一跳的廣播。

初始基于信息熵理論將匿名性進(jìn)行量化，如式（1）所示：

建立博弈模型，經(jīng)過(guò)一系列的統(tǒng)計(jì)和推理，得到如式（2）中所示的策略選擇：

其中，si表示節(jié)點(diǎn)Ui選擇的策略；｛C，D｝為供選擇的集合，C是合作，即生成剩下的個(gè)節(jié)點(diǎn)；D是拒絕，即不產(chǎn)生任何虛擬節(jié)點(diǎn)；Gi（C）表示節(jié)點(diǎn)Ui選擇合作所獲取的利益；Gi（D）表示節(jié)點(diǎn)Ui選擇拒絕所獲取的利益，詳細(xì)求解見(jiàn)式（3）和式（4）。

其中，dj（θj）表示每一節(jié)點(diǎn)在θj情形下選擇D的可能性；ηj表示節(jié)點(diǎn)選擇D的期望值。

算法1查詢預(yù)處理

3.2 錨點(diǎn)計(jì)算

在一般k-匿名算法中，用一個(gè)區(qū)域坐標(biāo)代替某一點(diǎn)位置坐標(biāo)發(fā)送給服務(wù)提供商用于查詢。而在本文中用區(qū)域的錨點(diǎn)來(lái)替代。這樣，不僅達(dá)到了 k-匿名的效果，而且降低了通信代價(jià)。在計(jì)算錨點(diǎn)時(shí)，使用如下公式：

其中，（χ0，y0）是所求錨點(diǎn)的坐標(biāo)；（χi，yi）為用戶節(jié)點(diǎn)Ui的坐標(biāo)。

由式（5）很容易求取錨點(diǎn)的坐標(biāo)，但為保護(hù)用戶隱私，本文引入了安全多方計(jì)算技術(shù)，設(shè)計(jì)了算法2。這樣就可以在不知道每個(gè)點(diǎn)的準(zhǔn)確坐標(biāo)情況下，求取所有節(jié)點(diǎn)坐標(biāo)之和，繼而得到筆者想要的結(jié)果，并且很好地抵御了攻擊者竊取位置信息的威脅。

算法2計(jì)算錨點(diǎn)

圖2 錨點(diǎn)計(jì)算過(guò)程

假定有6個(gè)用戶參與錨點(diǎn)計(jì)算，根據(jù)安全多方求和策略，這些用戶秘密選擇的計(jì)算次序?yàn)?U1-U3-U4-U2-U6-U5，每個(gè)用戶分別對(duì)應(yīng)計(jì)算一次，當(dāng)U5計(jì)算完成返回結(jié)果給U1，進(jìn)而 U1便可得到錨點(diǎn)的坐標(biāo)。

3.3 查詢處理

前面匿名的過(guò)程已處理完畢，而如何用錨點(diǎn)坐標(biāo)去查詢用戶所想要的結(jié)果仍很關(guān)鍵。本文采用了 Voronoi圖的方法，該方法更加清晰簡(jiǎn)便。Voronoi圖的作用在于當(dāng)平面中有N個(gè)查詢結(jié)果（對(duì)應(yīng)查詢空間內(nèi)的 N點(diǎn)），對(duì)于每個(gè)點(diǎn) Pi，可以很容易找到平面內(nèi)距離點(diǎn) Pi比距離其他點(diǎn)更近的區(qū)域。據(jù)此可以利用它作為查找最優(yōu)結(jié)果的工具?？赏ㄟ^(guò)對(duì)查詢返回結(jié)果構(gòu)造一個(gè)Voronoi圖，具體如圖3所示。圖中圓點(diǎn)表示對(duì)應(yīng)查詢的多個(gè)結(jié)果，菱形表示錨點(diǎn)U0。

圖3 基于Voronoi圖的查詢結(jié)果

當(dāng)返回候選結(jié)果時(shí)，選擇錨點(diǎn)所在區(qū)域的生成點(diǎn)以及周邊相鄰的結(jié)果作為候選集合發(fā)送回去。而對(duì)于每個(gè)用戶節(jié)點(diǎn)收到候選結(jié)果時(shí)，使用同樣的方法，判斷節(jié)點(diǎn)具體落在哪個(gè)區(qū)域內(nèi)，就可找到想要的結(jié)果。例如，圖中五角星表示一用戶節(jié)點(diǎn) Ui，明顯可以看出，它要查詢的精確結(jié)果就是 Pi。在該查詢處理部分考慮了2種方法，具體如算法3所示（對(duì)于查詢服務(wù)器來(lái)說(shuō)，Ui是未知的，而所有 Pi是已知的）。

算法3查詢結(jié)果處理

上述2種方法的優(yōu)缺點(diǎn)如下：（1）從用戶本身要求考慮，mi值越大，返回的解也就越多，這樣有利于用戶挑選出一個(gè)較為接近的結(jié)果，但同時(shí)服務(wù)效率可能就不高，反之亦然；（2）確定能為用戶找到最精確的結(jié)果，但查詢時(shí)間也許會(huì)變長(zhǎng)。

4 算法分析

本節(jié)主要對(duì)本文方案的算法從如下方面來(lái)進(jìn)行分析：

（1）隱私保護(hù)度：算法的前2個(gè)步驟都保證了隱私度：一是構(gòu)建匿名區(qū)，二是計(jì)算錨點(diǎn)。初始時(shí)，查找另外k-1個(gè)節(jié)點(diǎn)，共同組建匿名區(qū)，并考慮在節(jié)點(diǎn)不足的情況下，使用博弈論的思想產(chǎn)生虛擬節(jié)點(diǎn)予以補(bǔ)充，以滿足k-匿名。之后，計(jì)算錨點(diǎn)時(shí)，引入安全多方計(jì)算技術(shù)保護(hù)各節(jié)點(diǎn)隱私，不僅對(duì)于外部攻擊者，而且對(duì)于內(nèi)部偽裝在用戶間的攻擊者，也同樣能確保安全傳輸，不暴露位置。另外，該算法的安全性可以控制，即在節(jié)點(diǎn)不足時(shí)可以生成虛擬節(jié)點(diǎn)補(bǔ)充，而且可以通過(guò)生成虛擬節(jié)點(diǎn)距離的遠(yuǎn)近，調(diào)控節(jié)點(diǎn)到錨點(diǎn)的平均距離（Δχ，Δy），這樣就可以根據(jù)網(wǎng)絡(luò)環(huán)境的好壞，動(dòng)態(tài)地保護(hù)隱私。

（2）匿名成功率：考慮用戶節(jié)點(diǎn)密度低時(shí)，要想找到滿足匿名需求的節(jié)點(diǎn)就會(huì)變得很困難。所以，生成虛擬節(jié)點(diǎn)是個(gè)不錯(cuò)的辦法，但虛擬節(jié)點(diǎn)由誰(shuí)生成是個(gè)問(wèn)題。在考慮節(jié)點(diǎn)自私的情況，引入博弈論的思想，這樣就保證了算法的成功實(shí)行，顯然在這種情況下，匿名成功率比其他算法明顯要高。

（3）效率：就整個(gè)查詢過(guò)程來(lái)說(shuō)，算法 1是節(jié)點(diǎn)搜索構(gòu)建匿名區(qū)的過(guò)程，所牽涉到的計(jì)算都是輕量級(jí)的，計(jì)算復(fù)雜度低。算法2是一個(gè)高效的安全多方算法，其通信代價(jià)及輪次均為 O（n）。在算法 3中，用Voronoi進(jìn)行查詢處理時(shí)，主要分兩步，第1步的V圖已通過(guò)離線過(guò)程構(gòu)造好，直接定位就可找到返回的候選結(jié)果，所以復(fù)雜度為 O（1），第2步則需根據(jù)返回的候選結(jié)果集合用戶自己構(gòu)造Voronoi圖，復(fù)雜度為O（m lb m），m為返回的候選結(jié)果個(gè)數(shù)。所以，查詢處理效率較高。

進(jìn)一步，將本文方案與其他主流方案進(jìn)行了詳細(xì)比較，其結(jié)果如表1所示。

表1 方案性能比較

由表1可以明顯看出本文方案綜合性能較強(qiáng)：

（1）安全性：表1中第1種方案，需要一個(gè)可信的第三方。而當(dāng)?shù)谌阶兊貌豢尚艜r(shí)，它的隱私將受到嚴(yán)重威脅。第 2種方案選取一個(gè)錨點(diǎn)用于查詢，但它沒(méi)有達(dá)到k-匿名。第3種方案獲得了 k-匿名，但沒(méi)有考慮計(jì)算錨點(diǎn)時(shí)位置信息的泄露問(wèn)題。

（2）匿名成功率：這主要針對(duì)在用戶節(jié)點(diǎn)密度低的情況下，第 1種方案顯然沒(méi)有考慮這種情況，第2種不需生成匿名區(qū)。

（3）公平性：表1中前3種方案都沒(méi)有考慮到用戶的公平性問(wèn)題，針對(duì)不同用戶的主觀需求應(yīng)付出不同的代價(jià)?？尚诺谌剑褐挥械?種需要可信第三方。

（4）效率：第1種方案由于需要返回一個(gè)結(jié)果集合交給匿名服務(wù)器處理，當(dāng)查詢用戶過(guò)多時(shí)，效率會(huì)很低。第2種和第3種查詢方法一樣，都是使用增量近鄰查詢，能確保找到精確解，需要查詢時(shí)先對(duì)數(shù)據(jù)庫(kù)中查詢結(jié)果按照與錨點(diǎn)的遠(yuǎn)近進(jìn)行排序，之后多次提出查詢，且每次都需構(gòu)造供應(yīng)空間和需求空間進(jìn)行比較，這些都是在線過(guò)程，因而影響了查詢效率。

5 結(jié)束語(yǔ)

本文采用了分布式的思想，通過(guò)用戶之間協(xié)作，并考慮節(jié)點(diǎn)不足情況下，使用貝葉斯Nash均衡算法產(chǎn)生虛擬節(jié)點(diǎn)，以完成 k-匿名區(qū)域的構(gòu)建。匿名區(qū)生成后，計(jì)算錨點(diǎn)，用它來(lái)代替區(qū)域進(jìn)行查詢處理。在計(jì)算錨點(diǎn)坐標(biāo)值時(shí)，引入安全多方求和技術(shù)，避免了各點(diǎn)坐標(biāo)值的泄露。最后，利用Voronoi圖思想進(jìn)行LBS查詢，與傳統(tǒng)的查詢算法相比，更加便利。分析結(jié)果表明，本文方案達(dá)到了k-匿名的效果，保證了隱私，可使服務(wù)質(zhì)量以及整體系統(tǒng)性能得到提升。

未來(lái)研究工作將考慮多服務(wù)提供商的情況。此外，目前多數(shù)研究方法都是從客戶端進(jìn)行處理，因此，下一步將研究從服務(wù)提供者的數(shù)據(jù)庫(kù)入手提高安全性和效率。

［1］ 潘 曉，肖 珍，孟小峰.位置隱私研究綜述［J］.計(jì)算機(jī)科學(xué)與探索，2007，1（3）：268-281.

［2］ Sweeney L.k-anonymity：A Model for Protecting Privacy［J］.International Journal on Uncertainty，F(xiàn)uzziness and Know ledge-based Systems，2002，10（5）：557-570.

［3］ Gruteser M，Grunwald D.Anonymous Usage of Locationbased Services Through Spatial and Temporal Cloaking［C］//Proceedings of the 1st International Con-ference on Mobile Systems，Applications and Services.San Francisco，USA：ACM Press，2003：31-42.

［4］ Gedik B，Liu Ling.A Customizable k-anonymity Model for Protecting Location Privacy［C］//Proceedings of the 1st International Conference on Distributed Computing System s.Columbus，USA：IEEE Com puter Society，2005：620-629.

［5］ Gedik B，Liu Ling.Protecting Location Privacy with Personalized k-anonymity：Architecture and Algorithms［J］.Mobile Computing，2008，7（1）：1-18.

［6］ Liu Xinxin，Liu Kaikai，Guo Linke，et al.A Gametheoretic Approach for Achieving k-anonymity in Location Based Services［C］//Proceedings of INFOCOM’13. Turin，Italy：IEEE Press，2013：2985-2993.

［7］ Beresford A R，Stajano F.Location Privacy in Pervasive Com puting［J］.Pervasive Computing，2003，2（1）：46-55.

［8］ Beresford A R，Stajano F.M ix Zones：User Privacy in Location-aware Services［C］//Proceedings of Pervasive Computing and Communications Workshops.Vienna，Austria：IEEE Press，2004：127-131.

［9］ Zacharouli P，Gkoulalas-Divanis A，Verykios V S.A kanonymity Model for Spatio-temporal Data［C］//Proceedings of ICDEW’07.Washington D.C.，USA：IEEE Press，2007：555-564.

［10］ Palanisamy B，Liu L.Mobimix：Protecting Location Privacy with Mix-zones over Road Networks［C］// Proceedings of ICDE’11.Hannover，Germany：IEEE Press，2011：494-505.

［11］ Liu Xinxin，Zhao Han，Pan Miao，et al.Traffic-aware Multiple Mix Zone Placement for Protecting Location Privacy［C］//Proceedings of INFOCOM’12.Orlando，USA：IEEE Press，2012：972-980.

［12］ Du Suguo，Zhu Haojin，Li Xiaolong，et al.M ix Zone in Motion：Achieving Dynamically Cooperative Location Privacy Protection in Delay-tolerant Networks［J］.IEEE Transactions on Vehicular Technology，2013，62（9）：4565-4575.

［13］ Kido H，Yanagisawa Y，Satoh T.An Anonymous Communication Technique Using Dummies for Locationbased Services［C］//Proceedings of Conference on Pervasive Services.Santorini，Greece：IEEE Press，2005：88-97.

［14］ You T H，Peng W C，Lee W C.Protecting Moving Trajectories with Dummies［C］//Proceedings of Conference on Mobile Data Management.Mannheim，Germany：IEEE Press，2007：278-282.

［15］ Tran M T，Echizen I，Duong A D.Binomial-mix-based Location Anonymizer System with Global Dummy Generation to Preserve User Location Privacy in Locationbased Services［C］//Proceedings of Conference on Availability，Reliability，and Security.Krakow，Poland：IEEE Press，2010：580-585.

［16］ Miura K，Sato F.A Hybrid Method of User Privacy Protection for Location Based Services［C］//Proceedings of CISIS’13.W ashington D.C.，USA：IEEE Press，2013：434-439.

［17］ Khoshgozaran A，Shirani-Mehr H.SPIRAL：A Scalable Private Inform ation Retrieval Approach to Location Privacy［C］//Proceedings of M obile Data Management Workshops.Washington D.C.，USA：IEEE Press，2008：55-62.

［18］ Mouratidis K.Strong Location Privacy：A Case Study on Shortest Path Queries［C］//Proceedings of ICDEW’13. Brisbane，Australia：IEEE Press，2013：136-143.

［19］ Yiu M L，Jensen C S，Huang Xuegang，et al.Spacetwist：Managing the Trade-offs Among Location Privacy，Query Performance，and Query Accuracy in Mobile Services［C］//Proceedings of ICDEW’08.Cancun，Mexico：IEEE Press，2008：366-375.

［20］ 黃 毅，霍 崢，孟小峰.CoPrivacy：一種用戶協(xié)作無(wú)匿名區(qū)域的位置隱私保護(hù)方法［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1976-1985.

編輯 金胡考

User Privacy Protection for Location-based Service

PEI Yuanyuan1，2，SHI Runhua1，2，ZHONG Hong1，2，ZHANG Shun1，2
（1.Key Laboratory of Intelligent Computing&Signal Processing，Ministry of Education，Anhui University，Hefei 230039，China；2.School of Computer Science and Technology，Anhui University，Hefei 230601，China）

With the development of sensor technology and mobile communication equipments，there appears Locationbased Service（LBS），which is widely used.However，privacy issues，which arise in the enjoyment of the services at the same time，are becoming the focus of research.For privacy protection issues in LBS，this paper proposes a distributed model with users’cooperation and designs a new privacy protection scheme.In this scheme，when constructing the anonymous area，it uses Bayesian Nash equilibrium and secure multiparty summation technologies to ensure the user information privacy.When processing the query results，it introduces the Voronoi map method to increase the query efficiency.Analysis experimental result shows that the proposed scheme gives full consideration to the selfishness and unreliability of users.Hence it not only can provide the protection of user privacy，but also can improve the performance of the services.

location privacy；user collaboration；Bias Nash equilibrium；secure multiparty summation；Voronoi map

裴媛媛，石潤(rùn)華，仲 紅，等.面向位置服務(wù)的用戶隱私保護(hù)［J］.計(jì)算機(jī)工程，2015，41（10）：20-25.

英文引用格式：Pei Yuanyuan，Shi Runhua，Zhong Hong，et al.User Privacy Protection for Location-based Service［J］. Computer Engineering，2015，41（10）：20-25.

1000-3428（2015）10-0020-06

A

TP309

國(guó)家自然科學(xué)基金資助項(xiàng)目（61173187，61173188，11301002）；安徽省自然科學(xué)基金資助項(xiàng)目（11040606M 141，1408085QF107）；安徽大學(xué)博士科研啟動(dòng)經(jīng)費(fèi)基金資助項(xiàng)目（33190187）；安徽大學(xué)“信息安全”新專業(yè)基金資助項(xiàng)目（17110099）。

裴媛媛（1991-），女，碩士研究生，主研方向：信息安全；石潤(rùn)華、仲 紅，教授、博士生導(dǎo)師；張 順，講師、博士。

2014-11-04

2014-12-05E-m ail：992755870@qq.com