吳 雷， 潘 曉， 彭志平

(1.石家莊鐵道大學(xué) 經(jīng)濟(jì)管理學(xué)院，河北 石家莊 050043;2.石家莊鐵路運(yùn)輸學(xué)院基礎(chǔ)教學(xué)系，河北 石家莊 050043)

0 引言

伴隨著移動計算技術(shù)和無限設(shè)備的蓬勃發(fā)展，基于位置服務(wù)LBS中的位置隱私保護(hù)研究受到了學(xué)術(shù)界的廣泛關(guān)注。為保護(hù)位置隱私，Gruteser等人提出了位置K－匿名模型［1］。為滿足位置K－匿名，用戶的確切位置被擴(kuò)展為一個匿名區(qū)域，使得區(qū)域中至少包含K個用戶。后來出現(xiàn)了很多基于位置K－匿名的工作?？梢苑譃閮蓚€方向:第一，如何修正位置K－匿名模型并根據(jù)用戶隱私需求快速尋找匿名集［2－4］;第二，如何高效回答感知位置隱私的位置查詢(如最近鄰查詢和范圍查詢)［5］。本文關(guān)注的是第一個方向。

位置K－匿名模型是大眾普遍接受的位置隱私保護(hù)模型。為滿足該模型，采用降低用戶位置時空粒度的方法。為達(dá)到此目的，大部分現(xiàn)有方法均假設(shè)存在一個可信實(shí)體，網(wǎng)絡(luò)中的所有用戶向該實(shí)體發(fā)送真實(shí)位置?？尚艑?shí)體根據(jù)接收到的真實(shí)位置為查詢請求用戶尋找位置鄰近的用戶并形成匿名集，匿名集的最小邊界矩形作為匿名區(qū)域發(fā)布。這里存在一個很強(qiáng)的假設(shè)，即“所有用戶均可信”。但在實(shí)際應(yīng)用中并非如此:第一，網(wǎng)絡(luò)中不存在任何可信實(shí)體。每一個用戶都可能成為惡意用戶，向第三方提供他人真實(shí)位置或其它敏感信息。第二，由于不存在任何可信實(shí)體，所以不是所有用戶愿意共享真實(shí)位置。為尋找鄰近用戶而利用的“精確位置”正是用戶想要保護(hù)的對象。所以現(xiàn)有的利用確切位置尋找匿名集的方法應(yīng)用領(lǐng)域有限。亟待尋找一種在不提供確切位置的前提下為半可信用戶尋找匿名集的方法。

由于網(wǎng)絡(luò)中不存在任何可信實(shí)體，本文采用主從分布式結(jié)構(gòu)，為半可信用戶提供位置隱私保護(hù)。在基于位置服務(wù)中為半可信用戶匿名的問題可分解為兩個子問題:第一，在無位置信息的前提下，如何尋找空間位置鄰近的用戶形成匿名集;第二，匿名集中用戶如何在不暴露精確位置的情況下計算空間匿名區(qū)域。為解決上述兩個問題，本文提出了一種基于k*最近鄰圖的匿名方法，并通過“協(xié)作”的方式生成匿名區(qū)域。具體來講，每一個用戶通過無線信號強(qiáng)弱維護(hù)一個當(dāng)?shù)豮*最近鄰，并發(fā)送給第三方，如基站。第三方通過每一個注冊用戶的發(fā)來k*NN維護(hù)一個k*最近鄰圖。為保證最近鄰一致性，把圖劃分為若干個極大團(tuán)，并通過極大團(tuán)擴(kuò)展尋找匿名集。在找到的匿名集中，每個用戶均根據(jù)自己的隱私需求向匿名區(qū)貢獻(xiàn)一點(diǎn)位置，基于這種思想?yún)f(xié)作生成匿名位置。

圖1 主從分布式系統(tǒng)結(jié)構(gòu)

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

本文采用主從分布式系統(tǒng)結(jié)構(gòu)，包括客戶端、基站和服務(wù)提供商，如圖1所示。具體工作流程如下:第一，用戶首先在基站注冊LBS服務(wù)，然后打開無線傳感設(shè)備，本地維護(hù)k*NN信息?；靖鶕?jù)所有注冊用戶發(fā)來的k*NN信息，更新、維護(hù)近鄰圖關(guān)系圖。第二，用戶向基站發(fā)送匿名請求。基站利用匿名集生成算法將所有用戶分組，并為查詢提出用戶尋找合適的匿名組。攜帶組內(nèi)成員列表給相應(yīng)成員發(fā)送通知信號。組內(nèi)成員通過自組織的方式利用匿名區(qū)域生成算法協(xié)作計算匿名位置。組內(nèi)其他用戶在更新k*NN之前，如果提出任何查詢均以該匿名區(qū)域?yàn)闇?zhǔn)。第三，請求匿名的用戶將帶有匿名區(qū)域的查詢發(fā)送給服務(wù)提供商。服務(wù)提供商回答該查詢后，將候選結(jié)果集返回給用戶。用戶根據(jù)自己真實(shí)的位置挑選出確切結(jié)果。第四，當(dāng)用戶離開系統(tǒng)時，向基站提出請求，從鄰近關(guān)系圖中刪除該結(jié)點(diǎn)，以及與該結(jié)點(diǎn)鄰接的所有邊。

2 基本定義

定義1(p－同謀隱私模型) 設(shè)每個移動用戶u的最小隱私度需求為p。系統(tǒng)中任意兩個或兩個以上的半可信實(shí)體，通過交換各自的以及共同擁有的背景知識，推算用戶u敏感信息的概率記為P(u)。對于系統(tǒng)中的任意用戶u，如果P(u)≤p，則稱用戶u滿足p-同謀隱私模型。本文主要關(guān)注的是敏感位置信息，故每一個半可信用戶的精確位置泄露概率不能超過p。

定義2(匿名集) 用戶集合CR是匿名集，當(dāng)且僅當(dāng)

(1)|CR|≥K，|CR|表示集合CR的大小，即集合包含的元素個數(shù)，K即用戶的匿名度需求;

(2)?u∈CR，滿足p-同謀隱私模型;

(3)maxT是用戶可容忍的最差服務(wù)質(zhì)量，匿名集CR匿名區(qū)域大小Area(CR)≤maxT。

位置隱私保護(hù)基本任務(wù)即將服務(wù)空間中的用戶分組，每一個分組中的每一個用戶的隱私需求均得以滿足，同時該分組組成的匿名集集合匿名代價最小。本質(zhì)上，該問題是一個組合優(yōu)化問題。形式化表示如下:

定義3(用戶劃分) V是服務(wù)空間中所有等待匿名的對象組成的集合，將V中用戶按某種規(guī)則分組，則 CU={CS1，CS2，…，CSn}，其中

(1)CS1∪CS2∪…∪CSn=V;

(2)對于任意 i，j，CSi∩CSj= ?;

(3)cost(CU)最小。

如前所述，由于用戶間不可信，每一位用戶均不發(fā)布精確位置，而是通過判斷對等點(diǎn)間的信號強(qiáng)弱判定用戶的鄰近關(guān)系［4］。利用帶權(quán)無向圖表示用戶間的鄰近關(guān)系，并證明了在該圖上尋找匿名集等價于在圖中尋找K－簇的問題。所以定義3在鄰近關(guān)系圖上修正為定義4。

定義4(圖劃分) V是圖中所有頂點(diǎn)組成的集合，P={P1，P2，…，Pn}，其中

(1)P1∪P2∪…∪ Pn=V，其中Pi是一個連通子圖;

(2)對于任意的 i，j，Pi∩Pj= ?;

(3)costG最小，這里圖的劃分代價用所有連通子圖的邊權(quán)值和表示。

3 匿名算法

匿名算法的基本思想是首先將用戶分組，每一個組中任意兩個對象都相互鄰近，從而使得匿名集的總代價最小。進(jìn)而，在每一個匿名組中，利用“協(xié)作”的方式生成匿名區(qū)域。

3.1 尋找匿名集

在鄰近關(guān)系圖上，為把用戶分組，最直觀的方式是尋找最近鄰，即依次針對每一個用戶，尋找其(K－1)NN，將此K個用戶聚集在一起。圖2給出了一個根據(jù)用戶信號得到的鄰近關(guān)系圖，其中邊的權(quán)重代表信號強(qiáng)弱(值越小代表越近)。假設(shè)K=3，首先掃描用戶P1，利用尋找最近鄰的方法可以獲得匿名集合{P1，P2，P3}和{P4，P5，P6}，劃分后的結(jié)果如圖3(a)所示。很明顯，此圖存在另外一種更優(yōu)的劃分方法，如圖3(b)所示。產(chǎn)生這種現(xiàn)象的原因是，對象的最近鄰關(guān)系沒有對稱性［6］。用實(shí)驗(yàn)證明了對象相互最近鄰一致性可以改善聚類質(zhì)量，受到此點(diǎn)的啟發(fā)，我們旨在尋找滿足最近鄰一致性的匿名集。

圖2 鄰近關(guān)系圖PG

圖3 鄰近關(guān)系圖PG的兩種劃分

定義5(k*相互近鄰一致性) 設(shè)用戶集合U，如果 ?vi，vj∈U，并且 vi∈ lNN(vj)同時vj∈l'NN(vi)，其中l(wèi)NN(vi)表示vi的lNN組成的集合。令k=max(l，l')，則稱該集合用戶滿足k*相互最近鄰一致性。

為找到滿足k*相互近鄰一致性的匿名集，本文采用k*最近鄰圖表示服務(wù)空間中用戶間的鄰近關(guān)系。

定義6(k* 最近鄰圖) k*最近鄰圖(k* nearest neighbor graph，k*NNG)是一個無向帶權(quán)圖G(V，E，ω)。其中

(1)V是活動用戶組成的集合;

(2)E 是無向邊組成的集合 E={(vi，vj)| ?vi，vj∈ V，vj∈ k*NN(vi) 并且 vi∈ k*NN(vj)}，其中kNN(vi)是vi的kNN組成的集合;

(3)ω表示對象間的鄰近度。值越小說明兩個點(diǎn)的距離越近，反之說明距離較遠(yuǎn)。

現(xiàn)在的問題是要從k*NNG中尋找滿足最近鄰一致性的用戶集。很明顯，這些用戶集正好組成了k*NNG的團(tuán)。所以首先計算圖k*NNG G的補(bǔ)圖ˉG，然后利用經(jīng)典的WP著色算法［7］在ˉG上尋找所有極大獨(dú)立子集，這些極大獨(dú)立子集正是圖G的極大團(tuán)集合。受篇幅的限制，經(jīng)典的WP著色算法被省略。本文將所有的極大團(tuán)集合分為兩類:正團(tuán)和負(fù)團(tuán)。

定義7(正團(tuán)和負(fù)團(tuán)) CS是有極大團(tuán)組成的集合。對于任意極大團(tuán)C∈CS，如果|C|≥K，則成該團(tuán)為正團(tuán);否則，稱此團(tuán)為負(fù)團(tuán)。

當(dāng)K值較大時，由WP著色算法生成的可能大部分是負(fù)團(tuán)，不能滿足隱私度K的需求。為了解決此問題，提出擴(kuò)展策略?；舅枷胧侨〕鲐?fù)團(tuán)中的每一個頂點(diǎn)，進(jìn)行寬度優(yōu)先搜索，將與該負(fù)團(tuán)鄰接、合并后權(quán)值和最小的團(tuán)選擇出來合并。重復(fù)上述過程，直至負(fù)候選的數(shù)量為零。具體算法如圖4(a)所示。

3.2 尋找匿名區(qū)域

在定義1中給出了p－同謀隱私模型。在此節(jié)，簡單起見，將此模型具體化為:設(shè)匿名集合為CS，u為CS中的任意用戶，當(dāng)CS中|CS|－1個用戶相互串通時，他們根據(jù)中間結(jié)果和背景知識推測u在一維空間上的位置范圍為［loc1l，loc1r］，則|loc1r－loc1l|的長度不能小于P(=p*min(width，height))，其中p是用戶的最小隱私需求，width/height為系統(tǒng)的寬/高)。如果一維情況下的x(y)軸方向上，用戶位置隱私分別得到了滿足，則用戶的精確位置也不存在泄露的危險。

匿名區(qū)域生成的基本思想是:作為提出查詢的觸發(fā)用戶，首先做出犧牲，提出一個滿足觸發(fā)用戶最小隱私度的候選匿名區(qū)域。將候選匿名區(qū)域依次傳遞給匿名集中的其他用戶，其中每一個用戶選取候選匿名區(qū)域Top/Down(Right/Left)方向中的一個，根據(jù)自身隱私需求，生成適當(dāng)?shù)碾S機(jī)數(shù)δ。在選取的擴(kuò)展方向上，將候選匿名區(qū)域的長和寬擴(kuò)展δ。

下面在具體說明如何選取擴(kuò)展方向和擴(kuò)展度δ之前，首先將一個用戶相對于一個矩形的位置分為4種。

定義8 設(shè)矩形R和點(diǎn)V，計算由R和V形成的最小邊界矩形MBR。如果V僅對MBR邊界的x(y)值有貢獻(xiàn)，則稱V是x(y)型點(diǎn);如果V對MBR邊界的x和y值同時有貢獻(xiàn)，則稱V是xy型點(diǎn);如果V被R覆蓋，則稱V是內(nèi)型點(diǎn)。

下面根據(jù)用戶點(diǎn)的位置類型，設(shè)計不同的擴(kuò)展規(guī)則。

規(guī)則1 觸發(fā)用戶從［P，maxT］范圍內(nèi)分別取隨機(jī)取兩個數(shù)R1和R2，其中maxT是系統(tǒng)值，說明了用戶可接受服務(wù)質(zhì)量的最差值。分別以R1和R2作為長和寬，生成一個覆蓋用戶當(dāng)前位置的矩形R。用戶真實(shí)位置隨機(jī)出現(xiàn)在該矩形內(nèi)的任意一點(diǎn)。

觸發(fā)用戶將此候選區(qū)域R發(fā)送給匿名集中的其他用戶，接收用戶根據(jù)自己位置點(diǎn)的類型選擇擴(kuò)展規(guī)則。方便起見，設(shè)wid為候選區(qū)域R的寬，hgt為候選區(qū)域R的高。

規(guī)則2 如果接收用戶u是x型點(diǎn)，設(shè)從［bn，maxT－wid］范圍中按照高斯分布取隨機(jī)數(shù)rn，其中

式中，Cx是用戶u在x軸方向上對邊界的貢獻(xiàn)。設(shè)擴(kuò)展長度為δn，則

從Top/Down方向上隨機(jī)選取一個方向dir，則在用戶貢獻(xiàn)Cx的方向和選取的方向dir上擴(kuò)展δn。

規(guī)則3 如果接收用戶是y型點(diǎn)，設(shè)從［bn，maxT－h(huán)gt］范圍中按照高斯分布取隨機(jī)數(shù)rn，其中

設(shè)擴(kuò)展長度為δn，則

從Right/Left方向上隨機(jī)選取一個方向dir，則在用戶貢獻(xiàn)Cy的方向和選取的方向dir上擴(kuò)展δn。

結(jié)合規(guī)則2和規(guī)則3，可得xy型點(diǎn)的擴(kuò)展規(guī)則。

規(guī)則4 設(shè)利用規(guī)則2計算x方向的擴(kuò)展度δx，利用規(guī)則3計算y方向的擴(kuò)展度δy，候選匿名區(qū)域的擴(kuò)展度 δn=max(δx，δy)。從 Cx和 Cy貢獻(xiàn)的方向上均擴(kuò)展 δn。

規(guī)則5 如果接收用戶是內(nèi)型點(diǎn)，并且候選匿名區(qū)域R的寬或高小于用戶最小隱私需求V.P，則按從［V.P－min(wid，hgt)，maxT－min(wid，hgt)］范圍內(nèi)按照高斯分布取隨機(jī)數(shù)δn。并隨機(jī)的從Top/Down和Left/Right方向上任取一個方向dir1和dir2。在dir1和dir2方向上同時擴(kuò)展δn。

由規(guī)則2～規(guī)則5，可以發(fā)現(xiàn)雖然是根據(jù)不同用戶類型，選擇不同的擴(kuò)展隨機(jī)數(shù)和方向，但是從攻擊者的角度，用戶均是從候選匿名區(qū)域x和y方向上分別擴(kuò)展了δn。不同位置的用戶類型在外界看來無異，維護(hù)了用戶的位置隱私。圖4(b)給出了匿名區(qū)域生成算法。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

圖4 匿名算法

為不提供真實(shí)位置用戶尋找匿名集，直觀上容易想到的方法是:每一位用戶均發(fā)布滿足個人隱私需求的模糊位置，通過尋找基于模糊位置的KNN形成匿名集，簡稱該算法KNNCloak。本節(jié)用實(shí)驗(yàn)的方式評估KNNCloak和本文提出算法(簡稱NNClique)在不同系統(tǒng)設(shè)置下效率和質(zhì)量。使用著名的Thomas Brinkhoff移動對象生產(chǎn)器［8］生成模擬數(shù)據(jù)。由于NNClique算法假設(shè)用戶通過信號強(qiáng)弱判斷位置鄰近，所以首先計算出每一個用戶的20NN，并形成一個最近鄰圖。為適應(yīng)KNNCloak，在進(jìn)行匿名前首先將所有用戶的位置按照用戶最低隱私度需求p生成一個矩形代表模糊位置。所有用C++實(shí)現(xiàn)，運(yùn)行于1.83 GHz處理器、2 GB內(nèi)存的臺式機(jī)上。模擬之初，生成10 000個移動對象，實(shí)驗(yàn)?zāi)J(rèn)隱私度K為10，最差服務(wù)質(zhì)量maxT為1 000個系統(tǒng)單元，最低隱私需求p是從［0.08%，0.2%］的系統(tǒng)寬度中取的隨機(jī)數(shù)，在為對象尋找匿名區(qū)域擴(kuò)展時擴(kuò)展寬度的隨機(jī)數(shù)滿足數(shù)學(xué)期望為2p、標(biāo)準(zhǔn)方差為1的高斯分布。

4.2 性能評測

圖5顯示了匿名成功率隨著隱私度和最差服務(wù)質(zhì)量變化的變化趨勢。隱私度K增加說明在一個匿名集中包含的用戶的增多。但是，隱私度的變化對KNNCloak無影響，其匿名成功率基本保持在98%～99%。而NNClique的成功率隨著K的增加而直線降低，這與用戶臨近用戶數(shù)有關(guān)。在圖5(b)中僅評測了NNClique在不同maxT下成功率的變化趨勢。最差服務(wù)質(zhì)量降低，即用戶對服務(wù)質(zhì)量的要求提升了。所以從圖5中可以看出，匿名成功率逐漸降低，但是當(dāng)maxT降低到100時，匿名成功率依然在96%以上。

平均匿名代價指的是對于每一個匿名集合來說，匿名區(qū)域的平均面積。圖6中的TightMBR是根據(jù)匿名集用戶的真實(shí)位置計算的最小邊界矩形MBR的面積。把它包括在這里是為了比較顯示，由于用戶半可信犧牲的匿名代價。如圖6(a)所示，隨著隱私度的增加，NNClique和KNNCloak的匿名代價均上升，因?yàn)槟涿懈采w了更多的用戶。但是從圖6(a)中依然可以看出，NNClique為了保護(hù)半可信用戶隱私，與精確位置隱私保護(hù)相比犧牲了多于2倍的服務(wù)質(zhì)量。如圖6(b)所示，隨著最差服務(wù)質(zhì)量的降低，平均匿名代價也急劇降低。當(dāng)最差服務(wù)質(zhì)量降低到600時，犧牲的服務(wù)質(zhì)量節(jié)省了一倍。

NNClique的匿名時間包括兩部分:尋找匿名集的時間(圖7中的黑色柱)和計算匿名區(qū)域的時間(圖7中的白色柱)。無論是隨著隱私度的升高還是隨著最差服務(wù)質(zhì)量的降低，尋找匿名集和匿名區(qū)域的時間均逐漸增加，但是后者增長緩慢。而在匿名區(qū)域生成部分，隨著匿名集中保護(hù)用戶數(shù)的增多，候選匿名區(qū)域需要征詢更多人的意見方可決定，故尋找匿名區(qū)域的時間也增加的，但是增加幅度不大。二者結(jié)合即為本工作中查詢的匿名時間，可以看出匿名時間中尋找合適用戶占去將近2/3的時間。最差服務(wù)質(zhì)量變化趨勢與圖7(a)類似，其原理也相同，故這里不贅述。

圖5 匿名成功率

圖6 平均匿名代價

圖7 平均匿名時間

5 結(jié)論

提出了一種在主從分布式環(huán)境下，為半可信用戶提供位置隱私保護(hù)的方法。觀察到現(xiàn)存的大部分位置匿名方法均假設(shè)用戶可信，但是這在網(wǎng)絡(luò)中并不現(xiàn)實(shí)的。為解決此問題，本工作根據(jù)用戶信號強(qiáng)弱判斷位置鄰近性，提出了一種在K*NNG上的匿名算法，并通過“協(xié)作”的方式完成的匿名區(qū)域生成過程。在不同的系統(tǒng)設(shè)置下對算法進(jìn)行實(shí)驗(yàn)，結(jié)果表明基于半可信用戶的方法雖然犧牲了大致2倍的服務(wù)質(zhì)量，但是與在模糊位置上直接尋找KNN的匿名算法相比，在效率和服務(wù)質(zhì)量上取得了較好的平衡。

［1］SWEENEY L.K－anonymity:a model for protecting privacy［J］.International Journal on Uncertainty.Fuzziness and Knowledgebased Systems，2002，10:557－570.

［2］PAN X，MENG X，XU J.Distortion－based anonymity for continuous query in location－based mobile services［C］//In Proc of ACM SIGSPATIAL GIS.Washington，2009:256－265.

［3］PAN X，XU J，MENG X.Protecting location privacy against location－dependent attacks in mobile services［J］.IEEE Trans.Knowl.Data Eng，2012，24(8):1506－1519.

［4］HU H ，XU J.Non－exposure location anonymity［C］//Proceedings of the 25th International Conference on Data Engineering(ICDE).Washington:IEEE Computer Society，2009:1120－1131.

［5］MOKBEL M F，CHOW C，AREF W G.The New Casper:query processing for location services without compromising privacy［C］//Proceedings of the 32nd international conference on Very large data bases(VLDB).Seoul:VLDB Endowment，2006:763－774.

［6］DING C H，HE X.K－nearest－neighbor consistency in data clustering:incorporating local information into global optimization［C］//Proceedings of the ACM symposium on Applied computing(SAC).New York:ACM Press，2004:584－589.

［7］WELSH D J A，POWELL M B.An upper bound for the chromatic number of a graph and its application to timetabling problems［J］.The Computer Journal，1967，10:85－86.

［8］BRINKHOFF T.Thomas Brinkhoff Network － based Generator of Moving Objects［R/OL］.Oldenburg:Jade University，2013.http://www.fhoow.de/institute/iapg/personen/brinkhoff.