侯 堯，陶 洋，楊 理，熊 煉

重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶400065

1 引言

隨著智能手機(jī)的發(fā)展，獲取用戶位置提供相關(guān)服務(wù)的應(yīng)用程序得到了快速發(fā)展。這些基于位置的應(yīng)用程序其主要關(guān)注點(diǎn)之一是位置隱私[1-2]。要使用這些應(yīng)用程序，用戶必須將其位置提供給各自的服務(wù)提供商（或其他第三方）。這種位置泄露引起了嚴(yán)重的隱私問題，因?yàn)橛脩粑恢每赡軙?huì)受到攻擊，使其接受不想要的基于位置的垃圾郵件、敲詐勒索，甚至是人身危險(xiǎn)。

在過去的研究中，提出的大多數(shù)解決方案都是基于位置混淆，即泛化[3-4]（將軌跡上每個(gè)時(shí)刻的真實(shí)位置泛化到一個(gè)區(qū)域）、抑制[5-6]（根據(jù)真實(shí)位置所在區(qū)域的敏感程度有選擇的抑制發(fā)布）或擾動(dòng)[7-9]（對(duì)每個(gè)時(shí)刻的真實(shí)位置添加隨機(jī)噪聲生成擾亂位置）。大多數(shù)空間變換都依賴于語(yǔ)義上的隱私模型，比如k-匿名[10-11]，或是特定的不確定性模型，并且沒有提供嚴(yán)格的隱私。為此，研究人員將廣義的差分隱私概念引入了位置信息保護(hù)中，這是一個(gè)能夠提供嚴(yán)格數(shù)學(xué)證明的隱私保護(hù)模型[12]。簡(jiǎn)單地來(lái)說(shuō)，差分隱私意味著：一定距離內(nèi)的任何兩個(gè)位置進(jìn)行擾動(dòng)會(huì)產(chǎn)生相似的發(fā)布位置，因此攻擊者無(wú)法知道用戶的真實(shí)位置。

在本文中，給出了一種后置映射平面拉普拉斯機(jī)制。考慮一個(gè)具有敏感位置流的移動(dòng)用戶，該用戶需要將位置提供給基于位置的應(yīng)用程序（或其他第三方）。首先，根據(jù)每個(gè)位置設(shè)置的隱私級(jí)別生成擾動(dòng)位置，再利用后置映射機(jī)制將生成的擾動(dòng)位置映射到附近的位置，并使其服務(wù)質(zhì)量損失最小。后置映射平面拉普拉斯機(jī)制可以在滿足相同的隱私級(jí)別同時(shí)改善其平均服務(wù)質(zhì)量。最后結(jié)合真實(shí)數(shù)據(jù)，對(duì)機(jī)制進(jìn)行了仿真分析，證明了機(jī)制的服務(wù)質(zhì)量損失低于平面拉普拉斯機(jī)制。

2 理論分析

2.1 差分隱私和空間不可區(qū)分

差分隱私[13]是統(tǒng)計(jì)數(shù)據(jù)庫(kù)領(lǐng)域中的隱私概念。它的目標(biāo)是在發(fā)布關(guān)于數(shù)據(jù)庫(kù)的聚合信息時(shí)保護(hù)個(gè)人數(shù)據(jù)。差分隱私要求修改單個(gè)用戶的數(shù)據(jù)對(duì)查詢結(jié)果的影響可以忽略不計(jì)?？臻g不可區(qū)分的定義是基于廣義的差分隱私，可以定義在任意一組位置集X 上，并配備一個(gè)度量d[14]。歐幾里德距離度量d(x,x′)表示位置x和x′之間的可區(qū)分程度，距離小表示位置是不可區(qū)分的，距離大表示允許攻擊者區(qū)分它們。

設(shè)Z 是提供給服務(wù)提供商的一組值，P(Z)表示Z 上的概率測(cè)量集。P(Z)上的乘法距離dP定義為：

機(jī)制被設(shè)計(jì)為概率函數(shù)K:X →P(Z)，在發(fā)布位置集Z 上分配每個(gè)真實(shí)位置x 的概率分布K(x)。差分隱私的廣義變體，稱為d-隱私，被定義為[4]：

定義1（d-隱私）機(jī)制K:X →P(Z)滿足d-隱私，當(dāng)且僅當(dāng)：或等價(jià)于：

d 的選擇不同產(chǎn)生的隱私概念也不同，并可以通過隱私參數(shù)ε 來(lái)縮放本文的度量。本文主要考慮位置隱私，在這種情況下，真實(shí)位置X 和發(fā)布位置Z 都是位置集合，K 是一種干擾機(jī)制。采用歐幾里德距離度量d，得到的εd-隱私，稱為ε-空間不可區(qū)分[12]。即當(dāng)實(shí)際位置為x 時(shí)，與x 相距d(x,x′)的位置x′都發(fā)布位置z 的概率幾乎相同，則這種機(jī)制提供了空間上的不可區(qū)分性。其中“幾乎相同”表示概率的比率受exp(ε·d(x,x′)的約束，其中ε表示單位距離實(shí)現(xiàn)的不可區(qū)分的程度。兩個(gè)位置越近，生成相同發(fā)布位置z 的概率應(yīng)該越相似。通過K 機(jī)制，服務(wù)提供商無(wú)法準(zhǔn)確推斷用戶的位置，但可以獲得提供服務(wù)所需的近似信息。

從另外的角度來(lái)看，這個(gè)概念提供了用戶在任意半徑r 內(nèi)的隱私，并具有與r 成正比的可區(qū)分性εr。因此，在較小的半徑范圍內(nèi)，用戶享有很強(qiáng)的隱私，而他的隱私會(huì)隨著r 的增大而減小。此外，還可以靈活地在不同地點(diǎn)之間選擇不同的度量標(biāo)準(zhǔn)，例如曼哈頓或基于地圖的距離。文獻(xiàn)[12]給出了兩個(gè)特征結(jié)果，并詳細(xì)地解釋了空間不可區(qū)分。最后，通過在二維拉普拉斯分布中加入噪聲來(lái)實(shí)現(xiàn)這一概念。在本文中，主要假設(shè)d 是歐幾里德度量。

2.2 服務(wù)質(zhì)量損失

實(shí)現(xiàn)位置隱私的常用方法是采用位置擾動(dòng)機(jī)制，即概率函數(shù)K:X →P(Z)，其中X 是可能的位置集合，P(Z)表示Z 上的概率分布集合。K將位置x作為輸入，并產(chǎn)生一個(gè)發(fā)布位置z，p(z|x)表示真實(shí)位置為x 發(fā)布位置z 的概率。

從用戶的角度來(lái)看，希望量化由機(jī)制K 產(chǎn)生的服務(wù)質(zhì)量損失（Service Quality Loss，SQL）。給出位置集X的先驗(yàn)概率P-和度量d，其P-可視為對(duì)用戶的行為模型或攻擊者獲取的用戶背景知識(shí)，d(x,z)表示真實(shí)位置x與發(fā)布位置z的質(zhì)量損失度量，用于衡量發(fā)布z而不是x 時(shí)服務(wù)質(zhì)量損失的程度。所以可以將服務(wù)質(zhì)量損失定義為真實(shí)和發(fā)布位置之間的期望距離[15]，換句話說(shuō)，服務(wù)提供商應(yīng)該提供與其接收到的位置的準(zhǔn)確性成比例的質(zhì)量。故服務(wù)質(zhì)量損失可以被定義為位置的先驗(yàn)概率和機(jī)制的條件概率的函數(shù)：

2.3 平面拉普拉斯機(jī)制

平面拉普拉斯機(jī)制是滿足ε-空間不可區(qū)分的機(jī)制，這種機(jī)制是從以真實(shí)位置x 為中心的二維拉普拉斯分布中得出干擾位置。給定參數(shù)ε ∈R+，真實(shí)位置x ∈R2，在任意位置z ∈R2，機(jī)制的概率密度函數(shù)為：

其中，ε2/2π 是歸一化因子。根據(jù)文獻(xiàn)[12]中提出的將笛卡爾坐標(biāo)系轉(zhuǎn)換為極坐標(biāo)系更方便計(jì)算上式，轉(zhuǎn)換為極坐標(biāo)后的形式為：

干擾位置z可以使用點(diǎn)(r,θ)來(lái)表示，r表示x與z之間的距離，θ是r與笛卡爾坐標(biāo)系橫坐標(biāo)的夾角。根據(jù)文獻(xiàn)[12]可推導(dǎo)出真實(shí)位置為x時(shí)滿足“ε-空間不可區(qū)分”性質(zhì)的干擾位置z的極坐標(biāo)點(diǎn)(r,θ)的半徑計(jì)算公式：

其中，W-1(x)函數(shù)表示朗伯W 函數(shù)的區(qū)間(-∞,-1)分支，ρ是服從[0，1]均勻分布的隨機(jī)數(shù)。θ 是服從[0,2π]均勻分布的隨機(jī)數(shù)。最后得出干擾位置z=x+(r·cos(θ),r·sin(θ))。

獲得的位置z是對(duì)應(yīng)于z周圍的R2子集，由于R2具有對(duì)稱性，故平面拉普拉斯機(jī)制采用歐幾里德度量的服務(wù)質(zhì)量損失與P-無(wú)關(guān)，對(duì)任意P-∈P(X)有SQL(K,P-)=2/ε。

3 發(fā)布機(jī)制

3.1 后置映射機(jī)制

顯然，用戶總是希望服務(wù)質(zhì)量損失是最優(yōu)的，即最小化服務(wù)質(zhì)量損失，為此給出了一種后置映射的方法來(lái)達(dá)到目的。后置映射機(jī)制可以在滿足相同的隱私級(jí)別同時(shí)改善其平均服務(wù)質(zhì)量?？臻g不可區(qū)分要求x 附近的位置x′以相同的概率發(fā)布z，z 不必離x 很遠(yuǎn)。例如，靠近湖邊的兩個(gè)地點(diǎn)，使用平面拉普拉斯機(jī)制在所有方向上對(duì)稱地增加噪聲，則z 很有可能在湖中。現(xiàn)實(shí)中用戶在湖中的概率很小，可以將其映射到湖的邊緣，使其更接近真實(shí)位置。當(dāng)然，如果用戶確實(shí)在湖中，映射則會(huì)降低服務(wù)質(zhì)量，但這種可能性很小，所以總體上可以改善服務(wù)質(zhì)量。

給定機(jī)制K:X-P(Z)，真實(shí)位置為x，首先使用K 產(chǎn)生干擾位置z，然后使用后置映射函數(shù)M:Z →Z 將z 映射到新位置z*=M(z)，最后發(fā)布z*。

在Z ?Z 中，KM 發(fā)布觀測(cè)位置的概率與K 發(fā)布觀測(cè)位置的概率相同，則：

其中，M-1(Z)={z ∈Z:M(z)∈Z}。由此可以看出若K 滿足εd-隱私，那么KM 也同樣滿足。

若后置映射M 對(duì)于所有其他后置映射M′有SQL(KM,P-)＜SQL(KM',P-)，則稱M 為最優(yōu)映射。可以通過后置映射實(shí)現(xiàn)其最優(yōu)性，即選擇出最小服務(wù)質(zhì)量損失的位置z*。利用貝葉斯規(guī)則，將能從先驗(yàn)概率P-和機(jī)制K 得到后驗(yàn)概率P+∈P(x)，即：

若后置映射：

從上式易看出，對(duì)于所有z，z*∈Z

即：SQL(KM',P-)≥SQL(KM,P-) （11）

則式（11）為最優(yōu)映射。

3.2 最優(yōu)后置映射

后置映射第一步是計(jì)算后驗(yàn)，然后找到最小化服務(wù)質(zhì)量損失的點(diǎn)z*∈Z。如果X，Z 是有限的，則可以使用公式（10）直接計(jì)算后置映射。

通過迭代所有Z 來(lái)找到最小化服務(wù)質(zhì)量損失的點(diǎn)z*是不現(xiàn)實(shí)的，則可以通過僅考慮以z 為中心的某個(gè)圓Or(z)內(nèi)的位置來(lái)近似映射，即用argmin z*∈Or(z)替代argmin z*∈Z。直觀上來(lái)說(shuō)，Or(z)包含的點(diǎn)越多（半徑越大），服務(wù)質(zhì)量損失越接近最小值，故其中半徑r 可以選擇為包含所有K(x)(Or(x))≥0.99 點(diǎn)圓的半徑。

在許多情況下，用戶希望能夠靈活地將自己定位在平面上的任何位置，以及發(fā)布任意位置，因此可以將X，Z 看為完整的R2平面。此時(shí)Z 是連續(xù)的，則問題變得困難，因?yàn)榧词乖谟薪鐓^(qū)域Or(z)中，仍然需要考慮許多不可忽略的點(diǎn)。

該情況下的首要問題是計(jì)算后驗(yàn)。雖然用戶可能位于任何位置，但由于先驗(yàn)是過去訪問服務(wù)的位置或興趣點(diǎn)等一系列有限數(shù)據(jù)集構(gòu)成的，所以可以假設(shè)能被構(gòu)造的后驗(yàn)P+∈P(R2)也是有限的。盡管P+是有限的，但最小化服務(wù)質(zhì)量損失的z*不一定是后驗(yàn)點(diǎn)中的位置，所以仍然有無(wú)數(shù)的z*候選者。

直觀地，z*應(yīng)該在有限后驗(yàn)P+之間的點(diǎn)，即在后驗(yàn)構(gòu)成的凸包中。因此從幾何角度來(lái)看，本文的問題轉(zhuǎn)化為要在平面中找到一個(gè)點(diǎn)，該點(diǎn)到給定集合的加權(quán)距離最小，則該問題是位置理論中的韋伯問題。故對(duì)于歐幾里德度量的情況，可以有效地構(gòu)造最優(yōu)z*。采用Weiszfeld算法解決，其迭代公式修改為：

用Weiszfeld(P+)表示其迭代結(jié)果，并可以設(shè)置一些停止條件（例如，當(dāng)期望距離下降到ε 以下時(shí)，或者運(yùn)行時(shí)間為1 s）。

經(jīng)分析易知z*應(yīng)該在有限后驗(yàn)P+構(gòu)成的凸包中，且應(yīng)該靠近質(zhì)心附近，故為了更有效的計(jì)算，迭代公式中y0可以從質(zhì)心開始，其質(zhì)心的計(jì)算由公式（13）給出。

3.3 后置映射拉普拉斯機(jī)制

在R2平面上使用連續(xù)的先驗(yàn)概率是困難的，因此假設(shè)關(guān)于位置服務(wù)的先驗(yàn)概率信息采用以前使用的數(shù)據(jù)集形式提供，甚至以有關(guān)感興趣點(diǎn)信息的形式提供。令Q ∈R2是一個(gè)可能性很大的有限位置集合，集合中每個(gè)q ∈Q 與權(quán)重w(q)＞0相關(guān)聯(lián)。例如，Q 表示過去訪問位置服務(wù)的位置集合，則w(q)表示該位置訪問服務(wù)的用戶數(shù)?；蛘逹 可以是與位置服務(wù)相關(guān)的興趣點(diǎn)列表，其中w(q)表示捕獲每個(gè)興趣點(diǎn)的流行度。

給定平面拉普拉斯機(jī)制生成了干擾位置z，然后為了構(gòu)造一個(gè)有限且合理的后驗(yàn)概率P+∈P(R2)，則需要將Q（可能非常大）限制在z周圍的有限區(qū)域。本文設(shè)置r=C-1（0.99），其中C-1是平面拉普拉斯機(jī)制的半徑累積分布函數(shù)的倒數(shù)，讓Qr=Q ∩Or(z)。也就是說(shuō)，平面拉普拉斯機(jī)制以99%的概率生成x 與r 之間的點(diǎn)，因此將z 重新映射到距z 不遠(yuǎn)的z*（即“附近位置”）是合理的。

注意，可以使用k-d 樹的空間數(shù)據(jù)結(jié)構(gòu)來(lái)地計(jì)算Qr。0.99閾值可用于轉(zhuǎn)換效率以獲得準(zhǔn)確性，較小的值將導(dǎo)致較小的Qr，但可能導(dǎo)致最佳點(diǎn)位于區(qū)域之外。如果Q 密集，則可以使用預(yù)處理階段來(lái)減小Qr的大小，將點(diǎn)合并為小群集，并將w(q)設(shè)置為群集的權(quán)重。

權(quán)重w(q)，q ∈Qr可以（在歸一化之后）作為R2上的有限先驗(yàn)概率。采用貝葉斯定律（公式（9））和平面拉普拉斯的概率密度函數(shù)（公式（5））來(lái)計(jì)算先驗(yàn)概率，可以得出有限的后驗(yàn)P+：

最后，通過Weiszfeld(P+)計(jì)算后置映射的點(diǎn)z*。注意，實(shí)際上數(shù)據(jù)集Q 可能不夠詳細(xì)，無(wú)法為每個(gè)位置提供足夠的信息。新用戶可能在過去沒有或很少有其他用戶訪問過的位置訪問服務(wù)，此時(shí)認(rèn)為映射的數(shù)據(jù)質(zhì)量很低會(huì)降低用戶的隱私，因此可以使用簡(jiǎn)單的啟發(fā)式方法來(lái)評(píng)估數(shù)據(jù)的質(zhì)量：如果Qr的大?。ɑ蛘呖傊亓浚┑陀谀硞€(gè)閾值qmin，那么就跳過重映射并直接報(bào)告z，整個(gè)機(jī)制發(fā)布數(shù)據(jù)的算法1如下所示。

算法1后置映射拉普拉斯機(jī)制

輸入：x ∈R2，ε ＞0，qmin≥0，Q ?R2，w

輸出：z*

1.通過平面拉普拉斯機(jī)制生成干擾位置z；

2.設(shè)r=C-1（0.99）；

3.計(jì)算Qr=Q ∩Or(z)；

4.if(|Qr|＜qmin)

5.z*=z；

6.else

7.通過公式（14）計(jì)算后驗(yàn)P+(x)；

8.z*=Weiszfeld(P+)；

9.end if；

10.return z*；

4 實(shí)驗(yàn)評(píng)估

對(duì)本文方法進(jìn)行了實(shí)驗(yàn)評(píng)估。所有算法都在MATLAB上進(jìn)行了測(cè)試，使用的是2.9 GHz英特爾i7 CPU和8 GB內(nèi)存的PC 機(jī)。數(shù)據(jù)集使用Geolife 數(shù)據(jù)，Geolife 數(shù)據(jù)是通過182 位用戶且超過三年時(shí)間所收集的真實(shí)數(shù)據(jù)。移動(dòng)軌跡由一系列包含緯度、經(jīng)度和時(shí)間戳的記錄。提取了北京五環(huán)內(nèi)的軌跡，證明了有效的后置映射可以不受感興趣區(qū)域的任何限制。

為了保證所提出機(jī)制的可用性，將訓(xùn)練和評(píng)估數(shù)據(jù)分開。更準(zhǔn)確地說(shuō)，將整個(gè)位置數(shù)據(jù)集分成兩個(gè)不重疊的部分。第一部分包含了大約80%用戶的位置數(shù)據(jù)，作為訓(xùn)練集。在這一部分中，構(gòu)造出了一個(gè)全局先驗(yàn)，作為訪問該區(qū)域所有用戶的個(gè)體先驗(yàn)概率的平均值，然后將其用于后置映射機(jī)制得到最優(yōu)服務(wù)質(zhì)量損失的位置。請(qǐng)注意，此后置映射是針對(duì)全局先驗(yàn)優(yōu)化的，而不是針對(duì)特定用戶的。

數(shù)據(jù)集的另一部分，包含其余20%用戶的數(shù)據(jù)，被看作是評(píng)估機(jī)制的測(cè)試集。更準(zhǔn)確地說(shuō)，為至少20 個(gè)用戶構(gòu)造了一個(gè)用戶專用的先驗(yàn)，并度量用戶使用自己的先驗(yàn)時(shí)機(jī)制的服務(wù)質(zhì)量損失。雖然機(jī)制只針對(duì)數(shù)據(jù)集訓(xùn)練部分的用戶進(jìn)行了訓(xùn)練，但是發(fā)現(xiàn)它們也為測(cè)試集的用戶提供了較低的服務(wù)質(zhì)量損失。

注意，分割是對(duì)用戶執(zhí)行的：訓(xùn)練數(shù)據(jù)集中沒有測(cè)試用戶的任何數(shù)據(jù)。這種非常保守的方法旨在模擬一個(gè)新用戶的情況，對(duì)于這個(gè)新用戶，除了關(guān)于整個(gè)服務(wù)的一般可用信息之外，沒有其他任何信息。在這種情況下，改善服務(wù)質(zhì)量損失是一個(gè)強(qiáng)有力的結(jié)果；顯然，如果對(duì)用戶自己的部分?jǐn)?shù)據(jù)進(jìn)行訓(xùn)練，結(jié)果可以得到進(jìn)一步的大幅度改進(jìn)。

所有的評(píng)估機(jī)制都是為了滿足ε-空間不可區(qū)分而構(gòu)造的，使用ε=l/r，其中r=0.1 km，且l 的范圍為ln（1.4）到ln（2.6）。同時(shí)評(píng)估平面拉普拉斯機(jī)制本身和后置映射拉普拉斯機(jī)制。數(shù)據(jù)集Q 是由48 000 用戶和超過5 MB的訪問服務(wù)位置點(diǎn)組成的訓(xùn)練集。在訪問服務(wù)位置點(diǎn)列表中，構(gòu)造了一個(gè)k-d 樹，可以快速構(gòu)建Qr，為了避免單個(gè)用戶對(duì)后驗(yàn)產(chǎn)生較大影響，取w(x)=1/u，其中u為該用戶在Qr中的訪問服務(wù)次數(shù)，并設(shè)置qmin=20。在實(shí)驗(yàn)評(píng)估中，盡管數(shù)據(jù)集很大，但每次映射只需要幾毫秒。機(jī)制在12 000 用戶的整個(gè)測(cè)試數(shù)據(jù)集中對(duì)這兩種機(jī)制進(jìn)行了實(shí)驗(yàn)評(píng)估。

圖1 顯示了不同l 值下各用戶平均的服務(wù)質(zhì)量損失。注意，平面拉普拉斯機(jī)制的平均服務(wù)質(zhì)量損失總是相同的為2/ε。另一方面，使用后置映射時(shí)的平均服務(wù)質(zhì)量損失取決于用戶：由于映射是使用全局先驗(yàn)概率計(jì)算的，因此它可能并不總是能夠提供改進(jìn)。不過，雖然沒有使用用戶數(shù)據(jù)進(jìn)行訓(xùn)練，但實(shí)驗(yàn)評(píng)價(jià)表明，大多數(shù)用戶的服務(wù)質(zhì)量損失有很大的改善。ln（1.4）的結(jié)果表明，后置映射拉普拉斯機(jī)制的平均服務(wù)質(zhì)量損失為499 m，而平面拉普拉斯機(jī)制的平均服務(wù)質(zhì)量損失為594.4 m，高出19%。

圖1 隱私級(jí)別l對(duì)SQL的影響

圖2 顯示了圖1 中l(wèi)=ln（1.4）時(shí)的100 個(gè)時(shí)間戳測(cè)試數(shù)據(jù)，由圖可以看出并不是所有用戶的服務(wù)質(zhì)量損失都能被改善，但是只有8.17%的用戶服務(wù)質(zhì)量損失有所增加，其中僅有1.27%的用戶服務(wù)質(zhì)量損失增加了10%（59.4 m）或更多。

圖2 軌跡的SQL

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

在本文中，提出了一種后置映射平面拉普拉斯機(jī)制?？紤]一個(gè)具有敏感位置流的移動(dòng)用戶，該用戶需要將位置提供給基于位置的應(yīng)用程序。首先，根據(jù)每個(gè)位置設(shè)置的隱私級(jí)別生成擾動(dòng)位置，然后利用后置映射機(jī)制將生成的擾動(dòng)位置映射到附近的位置，并使其服務(wù)質(zhì)量損失最小。后置映射平面拉普拉斯機(jī)制可以在滿足相同的隱私級(jí)別同時(shí)改善其平均服務(wù)質(zhì)量。最后結(jié)合真實(shí)數(shù)據(jù)，對(duì)機(jī)制進(jìn)行了仿真分析，結(jié)果顯示機(jī)制的服務(wù)質(zhì)量損失低于平面拉普拉斯機(jī)制。