宋國超，初廣輝，武紹欣

山東科技大學(xué) 計算機科學(xué)與工程學(xué)院，山東 青島266590

1 引言

目前，基于個人消費者需求的智能化，LBS（Location Based Services）[1-2]將伴隨無線通信技術(shù)和GPS 技術(shù)（Global Positioning System）的發(fā)展，需求呈大幅度增長趨勢。用戶通過提供位置服務(wù)的APP 連接無線通信可以隨時隨地定位自己的位置來獲取相應(yīng)的服務(wù)[3-4]。例如，出行時獲取的導(dǎo)航服務(wù)（高德地圖），查找娛樂餐飲場所的生活服務(wù)（百度糯米），以及查找附近的人的社交服務(wù)（微信）等。據(jù)報告顯示[5]，全球LBS（Location Based Service）和RTLS（Real-Time Location Systems）市場規(guī)模預(yù)計將從2015 年的113.6 億美元增長到2020 年的549.5 億美元，CAGR（Compound Annual Growth Rate）為37.1%。

具體來說，用戶實時請求LBS 服務(wù)時，將自己的精確位置和查詢請求發(fā)送給LSP（Location Service Providers），LSP將查詢到的符合用戶需求的結(jié)果返回給用戶。盡管LSP能夠提供各種位置感知的優(yōu)質(zhì)服務(wù)，但是LSP可能會為了自己的利益泄露用戶的信息給其他不法分子，威脅用戶的人身和財產(chǎn)安全[6-7]。LBS服務(wù)存在著很大的安全隱患，而用戶對位置服務(wù)的使用規(guī)模還在不斷地增長，所以位置隱私的安全問題成為一個巨大的挑戰(zhàn)[8-10]。

目前，一種被廣泛采用的位置保護機制是k -匿名[11-13]。該機制采用集中式系統(tǒng)架構(gòu)，借助匿名服務(wù)器選取k-1 個其余位置，連同用戶位置一同發(fā)送給LBS服務(wù)器，保證用戶真實位置被識別出來的概率為1/k。

在實際方案中，匿名服務(wù)器需要查詢歷史請求記錄構(gòu)建候選匿名位置集。這樣保證了選取的位置的合理性。然而，現(xiàn)有的大多數(shù)研究工作沒有考慮到檢索龐大的歷史記錄帶來的時間開銷問題。并且，隨著用戶請求位置服務(wù)數(shù)目的增加，檢索歷史記錄中的數(shù)據(jù)會越來越耗時，影響匿名保護效果，降低了位置服務(wù)的即時優(yōu)越性。

幸運的是，本文構(gòu)建區(qū)間區(qū)域，將其進行Geohash編碼[14]，這樣做既考慮了選取位置的相似性，又借助編碼檢索避免了時間滯后性，加快檢索速度，給用戶提供更加快速安全的位置服務(wù)。另外，本文還考慮了用戶的隱私需求，為用戶提供了個性化的隱私保護的位置服務(wù)。借助Geohash編碼生成候選匿名位置集，如果候選匿名位置集中的位置點個數(shù)不滿足用戶要求的隱私保護程度k 值時，采用虛假位置生成技術(shù)。而且在生成虛假位置時，均勻地將區(qū)間區(qū)域分成k 份，在每一塊區(qū)間區(qū)域內(nèi)進行隨機選擇。這樣既保證了生成虛假位置的均勻分布，又增加了攻擊者識別出真實用戶的難度，很好地保護了用戶的位置隱私。如果候選匿名位置集中的位置點個數(shù)大于k 值，使用位置篩選算法來選取k 個位置點，該算法加快了選取位置點的速度，減少了時間開銷。

本文的貢獻總結(jié)如下：

（1）本文借助Geohash 編碼原理，提出了基于區(qū)間區(qū)域用來構(gòu)建候選匿名位置集，采用了集中式服務(wù)架構(gòu)實現(xiàn)個性化k-匿名模型來進行位置隱私保護。

（2）本文提出了全覆蓋的虛假位置生成算法來解決候選匿名位置集中的位置點個數(shù)不滿足用戶的隱私保護需求k 值。這里，全覆蓋意味著將用戶所在的區(qū)間區(qū)域劃分為k-1 等份，在每一個劃分的子區(qū)域內(nèi)隨機選擇一個位置，而且選擇與道路最近的交叉點來避開不合理的位置（河流、湖泊等），保證了選取的位置覆蓋了整個區(qū)間區(qū)域。

（3）當(dāng)候選匿名位置集超過k 值，采用位置篩選算法來選取位置點構(gòu)成匿名位置集發(fā)送給LSP。

2 相關(guān)工作

本章介紹了空間隱身技術(shù)和Geohash 編碼應(yīng)用的相關(guān)工作。

2.1 空間隱身技術(shù)

空間隱身技術(shù)[15]通過擴大空間區(qū)域來降低用戶的真實位置精度。最具影響力的技術(shù)是位置k -匿名，使用區(qū)域內(nèi)其他k-1 個位置來隱藏用戶真實位置。

Gruteser和Grunwald[16]提出了一種自適應(yīng)的空間隱身算法來實現(xiàn)位置k -匿名，該算法利用四叉樹進行時空隱身。但是，這種方法有幾個假設(shè)，比如它對所有請求都設(shè)定相同的k 值，這在實際中是不現(xiàn)實的，因為大多數(shù)用戶在不同的情景下會有不同的隱私需求。

為了解決以上缺陷，Mokbel等人[17]提出了具有代表性的基于Casper 模型的空間隱身方法。該模型通過傳輸用戶定義的k 值來提供用戶對位置隱私的偏好。并通過四叉樹將空間劃分為H 層，每一層都保留了整個空間結(jié)構(gòu)的信息，有效地提高了匿名性能。然而該模型需要過多的協(xié)作、可信的用戶，因此在用戶較少的區(qū)域，由于缺少足夠的虛擬位置而導(dǎo)致匿名區(qū)域的構(gòu)建失敗成為一個主要缺陷。

為了解決用戶較少區(qū)域的位置隱私問題，Ni等人[18]提出了一種在稀疏區(qū)域內(nèi)構(gòu)造匿名區(qū)域的K-SDCA 算法。該算法通過選擇歷史查詢概率高、地理分布相對均勻、匿名服務(wù)器請求內(nèi)容差異較大的虛擬用戶來實現(xiàn)k-匿名，具有較高的安全性和較高的效率。但是，該方法不考慮檢索歷史查詢記錄的開銷。因此，該算法耗時較長，影響了LBS的服務(wù)質(zhì)量。

文獻[19]提出了兩個生成虛假位置的規(guī)則：（1）每個虛假位置的查詢頻率應(yīng)與用戶真實位置的查詢頻率相似；（2）在這些位置的查詢頻率保持不變的前提下，這些位置應(yīng)盡可能地分散。然而，由于算法的過程發(fā)生在移動客戶端上，計算量相對較大，并且對移動客戶端的計算能力和存儲空間要求很高。

文獻[20]考慮到查詢概率和匿名區(qū)域的面積，將位置隱私泄露問題表示成多目標優(yōu)化問題，運用低復(fù)雜度的虛假位置選擇方案生成k-1 個虛假位置實現(xiàn)k -匿名。雖然該方法降低了某些位置點被過濾掉的可能性，但由于算法的過程發(fā)生在移動客戶端上，計算開銷大。

文獻[21]提出了基于聚類的k-匿名位置隱私算法來消除異常值，構(gòu)造匿名集保護用戶位置。該算法平衡了隱私保護安全性與位置服務(wù)查詢質(zhì)量之間的沖突。然而，由于聚類算法的迭代過程，時間開銷沒有得到優(yōu)化。

SpaceTwist[22]是經(jīng)典的不借助第三方匿名服務(wù)器的位置隱私保護算法，它使用錨來代替用戶的真實位置。此外，用戶可以根據(jù)他們的位置信息獲得準確的結(jié)果。雖然該算法實現(xiàn)了保護位置隱私，但隱私保護水平不高。

文獻[23]提出了一種基于映射的位置隱私信息檢索技術(shù)稱為MaPIR，該技術(shù)使用位置降維函數(shù)將用戶真實位置映射到地理空間內(nèi)生成冗余位置，保護用戶隱私信息。根據(jù)地球赤道周長40 400 km，位置上的每個有效數(shù)字代表相應(yīng)的距離范圍，從而將位置的經(jīng)緯度映射成了一維的數(shù)字，實現(xiàn)了位置降維。該技術(shù)可以提高檢索速度，但是卻不能提供個性化的位置隱私保護。

而本文借助以二分法原理為核心的Geohash 編碼技術(shù)，可以快速檢索歷史請求記錄數(shù)據(jù)庫。同時，運用虛假位置生成算法和位置篩選算法為用戶提供快速的自主的個性化的位置隱私保護。

2.2 Geohash編碼應(yīng)用

Geohash編碼是將二維的經(jīng)緯度坐標點轉(zhuǎn)換為一維的字符串，某一個字符串表示了某一個矩形區(qū)域。也就是說在這個矩形區(qū)域中的所有經(jīng)緯度點都共享一套編碼也就是字符串。

Liu 等人[24]提出了地理哈希方法，用于構(gòu)建GIS（Geographical Information System）領(lǐng)域分布式內(nèi)存的分布式空間索引。該技術(shù)提高了空間數(shù)據(jù)的讀寫性能，為高性能地理空間計算提供了堅實的技術(shù)基礎(chǔ)。

Li等人[25]提出了一種基于NoSQL 數(shù)據(jù)庫系統(tǒng)的位置感知WBAN數(shù)據(jù)監(jiān)測系統(tǒng)，該系統(tǒng)基于Geohash空間索引，能夠高效地處理基于位置的醫(yī)療信號監(jiān)測查詢。這種新穎的數(shù)據(jù)分析方法有利于促進醫(yī)療分析服務(wù)的快速發(fā)展。

Guo等人[26]提出了自適應(yīng)Hilbert-Geohash編碼方法叫做AHG 地理網(wǎng)格系統(tǒng)。AHG 通過網(wǎng)格劃分層次結(jié)構(gòu)，可以直接表示被編碼對象的位置和近似大小以及相應(yīng)的編碼長度。該方法除了具有加速空間查詢的能力外，還具有良好的穩(wěn)定性和可擴展性，已成功地應(yīng)用于高性能地理信息系統(tǒng)HiGIS中的多個空間查詢工具中。

由于Geohash編碼技術(shù)通過將地理坐標編碼，可以進行快速的空間近鄰點檢索功能，避免了復(fù)雜空間計算的時間開銷，能夠加快檢索速度，常常被運用于地理空間數(shù)據(jù)檢索領(lǐng)域內(nèi)。另外，通過編碼將用戶精準位置映射到空間區(qū)域中，可以有效地保護用戶的位置隱私信息，非常實用。所以，采用Geohash 編碼技術(shù)既可以減少時間開銷，又可以提供安全的位置服務(wù)。

目前，提出的位置隱私保護方案都各有特點，為了抵御攻擊者的背景攻擊，通常借助匿名服務(wù)器檢索歷史請求記錄來構(gòu)造虛假位置實現(xiàn)k -匿名機制，雖然這種策略取得了很好的匿名保護效果，但是大多數(shù)策略忽略了檢索歷史數(shù)據(jù)帶來的時間開銷，從而導(dǎo)致提供位置服務(wù)的速度變慢，影響了用戶的體驗度。

針對這樣的問題，本文結(jié)合Geohash 編碼的便捷性，提出了一種能夠快速檢索的位置隱私保護方案，該方案將用戶真實位置泛化到區(qū)間區(qū)域內(nèi)，對區(qū)間區(qū)域坐標轉(zhuǎn)換成漢明碼。通過對漢明碼進行檢索比較，篩選出相同編碼的候選匿名位置集。為了給用戶提供私人定制的匿名保護，對候選匿名位置集中的位置根據(jù)k 值進行不同的處理，提交滿足用戶要求的匿名位置集。仿真實驗證明，本文方法不但能夠加快匿名處理時間，而且還可以給用戶提供個性化的隱私保護，更加符合實際情景，具有很大的應(yīng)用前景。

3 預(yù)備知識

本章描述了相關(guān)定義和系統(tǒng)架構(gòu)。

3.1 相關(guān)定義

首先，介紹位置k-匿名的概念。

定義1（位置k -匿名[16]）位置k 匿名，將用戶位置與其他k-1 個無法區(qū)分的位置發(fā)送給LSP，使得用戶真實位置被識別成功的概率低于1/k 。這個概念是由Gruteser等人提出的。這里，k 代表了隱私要求，由用戶定義。

本文中，用戶發(fā)送的位置查詢信息定義如下。

定義2（位置請求信息LQU） 位置查詢信息是由用戶發(fā)送的，用來請求位置服務(wù)的信息。它是一個四元組LQU＜Uid,Uloc,T,QC ＞，分別代表用戶ID，用戶位置，當(dāng)前查詢時間和查詢內(nèi)容。這里的Uloc是個二元組＜lat,lng ＞，分別表示用戶位置的經(jīng)度和緯度。

匿名服務(wù)器對用戶真實位置Uloc進行保護，構(gòu)造匿名位置集代替位置查詢信息LQU發(fā)送給LBP。匿名位置集定義如下。

定義3（匿名位置集AS） 匿名位置集是由k 個位置構(gòu)成的集合，包含用戶真實位置和其余k-1 個由匿名服務(wù)器產(chǎn)生的位置。它是一個多元組，經(jīng)過匿名服務(wù)器匿名處理構(gòu)造AS,LQU變成了匿名請求AQU＜Uid,AS,T,QC ＞發(fā)送給LSP來請求服務(wù)。

為了保護位置隱私信息，將一個位置坐標擴展成區(qū)間區(qū)域，利用區(qū)域內(nèi)的歷史請求位置信息來進行保護。具體地，區(qū)間區(qū)域定義如下。

定義4（區(qū)間區(qū)域）將位置的經(jīng)緯度坐標分別映射到一個區(qū)間范圍所表示的區(qū)域稱為區(qū)間區(qū)域。

如圖1 所示，假設(shè)一用戶位置經(jīng)緯度坐標為（50，30），其紅線部分為區(qū)間區(qū)域為（[40，57]，[23，40]），其中50屬于區(qū)間[40，57]，該區(qū)間稱為經(jīng)度區(qū)間，30屬于區(qū)間[23，40]，該區(qū)間稱為緯度區(qū)間。

圖1 區(qū)間區(qū)域例子

根據(jù)地球投影坐標系原理，將地球上的任意一點都能使用經(jīng)緯度來表示。由于地球的橢球形狀的特點，不同地區(qū)的經(jīng)緯度變化所覆蓋的區(qū)域大小也不盡然相同。而且，據(jù)計算，1 緯度大約能表示111 km 的距離。為了減少通信開銷，本文中，區(qū)間的變化范圍不會超過1。

將用戶發(fā)送請求時的精準位置映射到區(qū)間區(qū)域之后，利用Geohash 編碼來檢索區(qū)域內(nèi)的歷史查詢位置，現(xiàn)將Geohash編碼定義如下。

定義5（Geohash編碼）Geohash編碼是將二維的經(jīng)緯度坐標轉(zhuǎn)換成一維的字符串的過程。該字符串稱為geohash 碼，表示某一個矩形區(qū)域。也就是說在某個矩形區(qū)域內(nèi)，所有的二維經(jīng)緯度坐標共享相同的編碼。

將位置坐標進行編碼之后，會按照反向檢索的方式來查找相近的位置。

定義6（反向檢索[24]）反向檢索是，根據(jù)某用戶的geohash 碼，查找第三方的歷史查詢記錄，找出與之相同編碼對應(yīng)位置的過程。

如圖2 所示，用戶所在的區(qū)間區(qū)域的geohash 編碼為“wtw3v”，反向檢索數(shù)據(jù)庫，對應(yīng)的第一個和最后一個的位置編碼是完全相同的。

圖2 反向檢索例子

3.2 系統(tǒng)架構(gòu)

本文采用了中心式系統(tǒng)架構(gòu)。該架構(gòu)包含的部件有位置請求用戶、可信的匿名服務(wù)器[22]和位置服務(wù)提供商，如圖3所示。請求過程為：

（1）需要進行位置請求的用戶通過移動終端來發(fā)送位置請求信息給匿名服務(wù)器。

（2）匿名服務(wù)器將信息通過匿名算法變成匿名請求信息。

（3）匿名服務(wù)器將匿名請求信息發(fā)送給位置服務(wù)提供商。

（4）位置服務(wù)提供商根據(jù)發(fā)送來的請求信息通過查詢位置數(shù)據(jù)庫返回查詢結(jié)果給匿名服務(wù)器。

（5）匿名服務(wù)器將結(jié)果進行過濾處理。

（6）匿名服務(wù)器將過濾結(jié)果返回給用戶。

其中，起到保護用戶位置隱私的關(guān)鍵部件是可信的匿名服務(wù)器，其功能為：

（1）能夠快速響應(yīng)位置查詢請求，減輕移動用戶端的計算開銷，提高服務(wù)質(zhì)量。

（2）通過匿名算法構(gòu)造隱身區(qū)域保護用戶隱私，避免隱私泄露。

圖3 系統(tǒng)架構(gòu)圖

（3）過濾LBS返回的查詢結(jié)果，減少通信開銷。

4 算法設(shè)計

本章詳細描述了算法的實現(xiàn)過程。本文算法實現(xiàn)需要借助可信的匿名服務(wù)器。

4.1 位置泛化階段

用戶發(fā)送請求位置服務(wù)時，會將自己的精準位置發(fā)送給匿名服務(wù)器。根據(jù)區(qū)間區(qū)域的原則，匿名服務(wù)器首先將用戶的經(jīng)緯度位置泛化到區(qū)間區(qū)域內(nèi)。借助隨機數(shù)，隨機產(chǎn)生4 個0 到0.025 隨機數(shù)，將用戶位置的經(jīng)度和緯度分別減去和加上任意一個隨機數(shù)，最終構(gòu)成用戶區(qū)間區(qū)域。例如：假設(shè)用戶位置為(lat,lng)，四個隨機數(shù)分別為r1,r2,r3,r4，那么用戶區(qū)間區(qū)域為([lat-r3,lat+r1],[lng-r4,lng+r2])。

對于位置泛化，需要說明以下三點：

（1）產(chǎn)生隨機數(shù)的范圍設(shè)定在0到0.025的原因是，地理位置1 緯度大約對應(yīng)111 km 的距離，0.025 大約對應(yīng)2.5 km，對于最大范圍是經(jīng)緯度前后波動各0.025°，則表示的區(qū)域范圍大約是：（0.05/0.025）×2.5 km×（0.05/0.025）×2.5 km=25 km2，相當(dāng)于250個100平的房子占地面積的大小，這個范圍也是相當(dāng)客觀的。

（2）隨機產(chǎn)生四個隨機數(shù)，是為了防止攻擊者預(yù)測出用戶的精準位置，對用戶精準位置進行了保護。若設(shè)置一個隨機數(shù)，經(jīng)度和緯度分別向前，向后波動，根據(jù)其區(qū)間的對稱性，該波動的幅度很容易推算出來，從而用戶的經(jīng)緯度坐標也就暴露了。同樣地，如果設(shè)置兩個隨機數(shù)，經(jīng)緯度根據(jù)同樣的方法也是可以推算出來的，所以這里會隨機產(chǎn)生4個隨機數(shù)，成功地避開了區(qū)間對稱的特性，使得用戶的位置不容易被預(yù)測出來。

（3）通常，隨機數(shù)的產(chǎn)生是服從正態(tài)分布，也就是說產(chǎn)生的數(shù)值大部分是在0.012 5 左右波動的，接近0 和0.025 的隨機數(shù)占的比例較少。按照數(shù)值平均波動0.012 5來計算，則區(qū)間區(qū)域的平均大小為：（0.025/0.025）×2.5 km×（0.025/0.025）×2.5 km=6.25 km2。

4.2 Geohash編碼階段

用戶的區(qū)間區(qū)域確定了之后，計算該區(qū)域的Geohash編碼。下面是其編碼生成的偽代碼。

算法1 Geohash 編碼算法（Geohash coding algorithm）

輸入：區(qū)間區(qū)域([lat1,lat2],[lng1,lng2])

輸出：geohash 編碼，geohash 碼長度

1. lat range=[-90,90],lng range=[-180,180]；

2. geohash=φ,code=φ；

3. lat mid=sum(lat range)/2；

4. lng mid=sum(lng range)/2；

5. While TRUE

6. if lng1 ＜=lng mid and lng2 ＜=lng mid //經(jīng)度

7. code ←code ∪{0}；

8. lng range[1]=lng mid；

9. else if lng1 ＞lng mid and lng2 ＞lng mid

10. code ←code ∪{1}；

11. lng range[0]=lng mid；

12. else break

13. end if

14. if lat1 ＜=lat mid and lat2 ＜=lat mid //緯度

15. code ←code ∪{0}；

16. lat range[1]=lat mid；

17. else if lat1 ＞lat mid and lat2 ＞lat mid

18. code ←code ∪{1}；

19. lat range[0]=lat mid；

20. else break

21. end if

22. End While

23. 根據(jù)表1 中base32 映射表，將code 中的0，1 編碼成geohash；

24. Return geohash,geohash 碼的長度

Geohash 編碼算法首先按照Geohash 編碼的原則，對區(qū)間區(qū)域進行編碼。一旦區(qū)間區(qū)域表示的范圍不被劃分區(qū)間完全覆蓋時，跳出編碼過程。這樣做的原因有兩個：（1）位置數(shù)據(jù)是浮點數(shù)類型，一般保留小數(shù)點后5到7 位的精度；（2）預(yù)處理階段得到的區(qū)間區(qū)域本身就是一個數(shù)值范圍，并且數(shù)值波動小，最大的上下浮動也只是0.05，在迭代的過程中限制的精度。滿足這兩個條件，區(qū)間區(qū)域的編碼自身便有精度的限制，不需要用戶去自定義設(shè)定，而且，編碼產(chǎn)生的長度不會過長，也不會過短，避免區(qū)域過大或過小。

另外，返回geohash 碼的長度是為了進行下一階段位置檢索，用來保護用戶的位置隱私。

4.3 反向檢索位置階段

用戶真實位置進行了Geohash編碼之后，反向檢索位置首先根據(jù)真實用戶geohash 碼長度，對第三方歷史記錄中的單個位置經(jīng)緯度進行相同精度的Geohash 編碼。然后進行檢索，選出與之相同編碼的位置，并進行去重操作，即重復(fù)的位置、將與用戶真實位置相同的位置刪除掉，最后統(tǒng)計位置個數(shù)，并與用戶指定的k 值進行比較，若與k 值相同，則將其位置點構(gòu)成匿名位置集AS，發(fā)送給LSP；若小于k 值，則執(zhí)行4.4節(jié)虛假位置生成階段；若大于k 值，則執(zhí)行4.5 節(jié)位置篩選階段，篩選合理的k 個位置，滿足用戶隱私需求。

4.4 虛假位置生成階段

通過Geohash 編碼檢索出來的位置點個數(shù)小于用戶隱私需求k 值時，采用虛假位置生成算法，生成k 個位置進行位置隱私保護。虛假位置生成算法的主要思路是在用戶區(qū)間區(qū)域內(nèi)均勻地生成k 個位置，其偽代碼如下。

算法2 虛假位置生成算法（Dummy locations generating algorithm）

輸入：用戶區(qū)間區(qū)域([lat1,lat2],[lng1,lng2])，隱私需求k，用戶真實位置Uloc(lat,lng)

輸出：匿名位置集AS

1. D1=(lat2-lat1)；

2. D2=(lng2-lng1)；

3. Dmax=max(D1,D2)；

4. d1=lat1,d2=ln g1；

5. AS=φ

6. if k%2==0

7. if Dmax==D1

8. for m=0 to k-1 do

9. Lat=random(d1,d1+(D1/(k-1)))；

//從區(qū)間(d1,d1+(D1/(k-1)))任選一數(shù)賦值給Lat

10. Lng=random(lng1,lng2)；

//從區(qū)間(lng1,lng2)任選一數(shù)賦值給Lng

11. AS ←AS ∪{(Lat,Lng)}；

12. Lat=d1+(D1/(k-1))；

13. end for

14. else

15. for m=0 to k-1 do

16. Lat=random(lat1,lat2)；

17. Lng=random(d2,d2+(D2/(k-1)))；

18. AS ←AS ∪{(Lat,Lng)}；

19. d2=d2+(D2/(k-1))；

20. end for

21. end if

22. else

23. if Dmax==D1

24. for j=0 to 2 do

25. for i=0 to (k-1)/2 do

26. Lat=random(d1,d1+(D1/(k-1)))；

27. Lng=random(d2,d2+(D2/2))

28. AS ←AS ∪{(Lat,Lng)}；

29. d1=d1+(D1/(k-1))；

30. end for

31. d2=d2+(D2/2)；

32. end for

33. else

34. for j=0 to 2 do

35. for i=0 to (k-1)/2 do

36. Lat=random(d1,d1+(D1/2))；

37. Lng=random(d2,d2+(D2/(k-1)))；

表1 十進制數(shù)值對應(yīng)的base32碼

38. AS ←AS ∪{(Lat,Lng)}；

39. d2=d2+(D2/(k-1))；

40. end for

41. d1=d1+(D1/2)；

42. end for

43. end if

44. end if

45. AS ←AS ∪{(lat,lng)}；

46. Return AS

首先，該算法分別計算經(jīng)度區(qū)間和緯度區(qū)間的長度D1和D2，并取出兩者的最大值Dmax，接著，判斷k 值的奇偶性，若為偶數(shù)，根據(jù)Dmax分為兩種情況，若經(jīng)度區(qū)間的長度較大的話，經(jīng)度區(qū)間均分為k-1 份，在每一份里隨機選取一個位置，緯度取的緯度區(qū)間內(nèi)的任意值，高度與用戶位置高度相同。否則的話，將經(jīng)度區(qū)間均分為k-1 份。若k 為奇數(shù)的話，區(qū)間長度長的緯度上均分(k-1)/2 份，短的區(qū)間內(nèi)均分2份，在每一子區(qū)域內(nèi)分別隨機選取一個位置點。最后成功構(gòu)造包含k 個位置的匿名位置集AS。

4.5 位置篩選階段

當(dāng)反向檢索出來的位置個數(shù)大于隱私需求k 值時，要對區(qū)間區(qū)域內(nèi)的位置進行篩選。位置篩選算法的偽代碼如下所示。

算法3 位置篩選算法（Locations filtering algorithm）

輸 入：候 選 位 置 集LS ＜(lat1,lng1),(lat2,lng2),…,(latnum,lngnum)＞，用戶真實位置(lat,lng)

輸出：匿名位置集AS

1. 候選位置集中的位置個數(shù)為num；

2. A=B=C=D=φ；

3. for i=1 to num do

4. If lati＞lat and lngi＞lng

5. A ←A ∪{(lati,lngi)}；

6. Else if lati＜=lat and lngi＞lng

7. B ←B ∪{(lati,lngi)}；

8. Else if lati＞lat and lngi＜=lng

9. C ←C ∪{(lati,lngi)}；

10. Else

11. D ←D ∪{(lati,lngi)}；

12. End if

13. End for

14. 分別統(tǒng)計列表A、B、C、D 中的位置個數(shù)a,b,c,d；

15. 分別從列表A、B、C、D 中隨機選取a(k-1)/num 、b(k-1)/num 、c(k-1)/num 、d(k-1)/num 個位置點添加到匿名位置集AS 中；

16. AS ←AS ∪{(lat,lng)}；

17. Return匿名位置集AS

該算法首先將候選位置集中的位置根據(jù)用戶真實位置經(jīng)緯度分為四類，再根據(jù)相應(yīng)的比例來選取各類中的位置點，最后連同用戶位置添加到匿名位置集AS，發(fā)送給LSP，請求位置服務(wù)。

4.6 安全性分析

在某些情況下，攻擊者可能會與某些惡意用戶或位置服務(wù)提供商進行合作，以獲取合法用戶的位置請求信息。幸運的是，本文的方法可以成功地抵制攻擊者的共謀攻擊。

通常，如果成功推斷真實用戶位置的概率不隨著共謀團體數(shù)目的增加而增加，則說明該方法可以抵抗共謀攻擊。

下面對本文提出的方法進行了詳細的安全性分析。

定理本文提出的方法可以抵制共謀攻擊。

證明首先，若攻擊者與某一惡意用戶謀和，攻擊者猜測出真實用戶的概率也是1/k 。因為本文將用戶的經(jīng)緯度位置擴展到區(qū)間區(qū)域內(nèi)，并進行編碼，在歷史請求記錄中選擇與用戶區(qū)間區(qū)域編碼相同的位置來進行匿名保護，而且，攻擊者只擁有與謀和用戶的歷史請求記錄，卻不清楚被攻擊用戶的歷史請求記錄。所以，攻擊者只能隨機猜測真實用戶的位置，這樣，識別出真實用戶的概率為1/k。甚至，當(dāng)攻擊者與多個用戶進行謀和時，也不能降低猜測出真實用戶的概率。因為，在本文方法中，用戶與用戶之間是相互獨立的，互不影響，所以本文方法可以抵制攻擊者與惡意用戶的謀和攻擊。

然后，若攻擊者與位置服務(wù)提供商進行共謀，由于本文方法在產(chǎn)生區(qū)間區(qū)域時使用了隨機數(shù)，虛假位置的產(chǎn)生和位置篩選都存在隨機的因素，而匿名集的產(chǎn)生是沒有規(guī)律可循的，所以攻擊者無法根據(jù)匿名集來推測出用戶的真實位置，猜測概率仍然是1/k。

綜上所述，本文提出的方法是可以成功地抵御謀和攻擊的。

5 仿真實驗驗證與分析

為驗證本文所提位置隱私保護方法的有效性，使用Python 編程語言實現(xiàn)算法來進行仿真實驗驗證。位置數(shù)據(jù)來自Geolife 數(shù)據(jù)集[27]，該數(shù)據(jù)集收集了從2007 年4月到2012年8月182個用戶的軌跡數(shù)據(jù)。這些數(shù)據(jù)包含了一系列以時間為序的點，每一個點包含經(jīng)緯度、海拔等信息。包含了17 621 個軌跡，總距離120 多萬公里，總時間48 000多小時。這些數(shù)據(jù)不僅僅記錄了用戶在家和在工作地點的位置軌跡，還記錄了大范圍的戶外活動軌跡，比如購物、旅游、遠足、騎自行車。仿真實驗主要關(guān)注算法處理數(shù)據(jù)的時間開銷以及生成匿名區(qū)域的匿名保護效果。

5.1 處理數(shù)據(jù)時間開銷

目前，大多數(shù)的技術(shù)通過距離計算來挑選候選匿名位置集。圖4比較了本文使用的Geohash編碼技術(shù)與曼哈頓距離[28]以及歐氏距離[29]處理數(shù)據(jù)的時間開銷。歐氏距離公式為：

圖4 候選位置數(shù)據(jù)量與時間開銷關(guān)系圖

實驗中，將某一用戶的第一條位置數(shù)據(jù)作為該用戶真實位置，其余的作為歷史數(shù)據(jù)用來挑選匿名位置集，運行100次取平均值作為輸出結(jié)果進行比較。

如圖4 所示，隨著數(shù)據(jù)量的增加，三種方法的時間開銷都會增加，而Geohash編碼明顯在時間開銷方面具有卓越的優(yōu)勢。當(dāng)數(shù)據(jù)量達到900條時，花費的時間還不足0.2 s。由于編碼只是將二維的數(shù)據(jù)變成一維的字符串，不需要進行計算。而基于距離的檢索，則需要進行距離計算，花費的時間就會大大增大。尤其是，采用歐式距離計算時，存在乘法運算，更是加大了時間開銷。因此，通過Geohash 編碼檢索，可以快速地進行匿名處理，從而給用戶提供快速便捷的服務(wù)。

5.2 算法執(zhí)行效率分析

圖5 分別比較了本文的匿名算法、Casper 算法[17]、DLS 算法[19]、SpaceTwist 算法[22]和基于聚類的k-匿名算法[21]執(zhí)行時間隨k 值變化的趨勢。這里，待處理的歷史請求記錄為500條。

圖5 算法執(zhí)行時間與k 值的關(guān)系圖

如圖5 所示，隨著k 值的增加，所有的算法執(zhí)行時間都會增加，而本文算法時間開銷是最少的。具體地，由于不借助第三方匿名服務(wù)器，SpaceTwist算法使用客戶端附近的錨點來替換用戶的真實位置，客戶端計算壓力大，算法執(zhí)行時間最長。Casper算法在生成虛假位置時，產(chǎn)生的匿名區(qū)域過大，并且會產(chǎn)生大量冗余的位置，時間開銷要大于其余算法?；诰垲惖膋-匿名算法與Casper算法的匿名處理時間類似，因為該算法使用了聚類算法，時間開銷較大。而DLS算法在匿名處理時，借助歷史記錄數(shù)據(jù)庫和查詢概率，充分考慮背景信息，需要進行一輪的2k 個虛假位置候選匿名位置集選擇，算法時間復(fù)雜度要優(yōu)于Casper 算法。而本文實現(xiàn)匿名保護時，借助Geohash編碼檢索、生成虛假位置算法和位置篩選算法，可以快速地提供安全的個性化的位置服務(wù)。總之，在匿名算法時間開銷上，本文算法占極大的優(yōu)勢。

5.3 匿名保護效果分析

匿名熵常用來表示位置匿名保護的程度[30]，公式如下：

其中，pi表示真實用戶被識別出來的概率，H(R)代表匿名熵，匿名熵的值越大，表明匿名保護的效果越好。

圖6 表示的是不同算法的匿名熵與k 值的關(guān)系。算法包含隨機算法、Casper算法[17]、DLS算法[19]、MOS算法[20]和區(qū)間區(qū)域算法。

圖6 匿名熵與k 值的關(guān)系圖

如圖6 所示，隨著k 值的增加，所有算法的匿名熵都會增加，而本文算法的匿名熵始終是最大的。隨機算法在指定區(qū)域內(nèi)隨機選擇位置，時間開銷最小，但是匿名保護效果很差。隨機產(chǎn)生的虛假位置不考慮位置的合理性，攻擊者可以過濾掉許多位置，導(dǎo)致匿名保護失敗。Casper算法的匿名保護程度要好一點，因為Casper算法借助第三方匿名服務(wù)器的歷史請求信息，能夠增大真實用戶不被識別出來的概率，但是，該算法會產(chǎn)生許多冗余區(qū)域，所以它的匿名效果也并不是最優(yōu)的。而DLS 算法考慮了背景信息，同時，產(chǎn)生的虛假位置都是借助歷史上查詢概率相近的位置，所以匿名熵能高一點。MOS 算法生成的虛假位置盡可能遠離真實用戶，攻擊者不能輕易識別出真實用戶，匿名保護程度要優(yōu)于DLS算法。而本文的機制在產(chǎn)生虛假位置時，在區(qū)間區(qū)域內(nèi)均勻產(chǎn)生虛假位置，并且考慮到位置的合理性，根據(jù)實際道路情景信息進行位置調(diào)整。在位置篩選時，也選擇了與真實用戶相似的位置點，所以本文的匿名算法比前面算法的匿名保護都要好。

6 結(jié)束語

對于現(xiàn)有的k-匿名機制借助匿名服務(wù)器檢索數(shù)據(jù)庫時間開銷大的問題，本文提出了借助Geohash編碼的區(qū)間區(qū)域位置隱私保護策略。該策略首先將用戶的真實位置泛化到區(qū)間區(qū)域中，然后根據(jù)Geohash編碼原理來檢索相同編碼的位置，再根據(jù)用戶的隱私需求，為用戶提供個性化的k-匿名隱私保護服務(wù)。仿真實驗表明，本文提出的方法在匿名處理時間具有更好的優(yōu)越性，同時生成虛假位置算法和位置篩選算法保證了虛假位置的分布盡可能均勻，保證了用戶真實位置被識別出來的概率降低，達到了很好的匿名保護效果。由于挖掘大量的位置信息能夠分析用戶的社會屬性，未來的工作將充分考慮用戶請求位置服務(wù)的時間維度，并分析和預(yù)測用戶行為模型來完善目前的工作，對不確定的不安全因素提前預(yù)防，為用戶提供可預(yù)測的動態(tài)位置隱私保護。