侯士江，劉國華，候 英

（1.燕山大學(xué)工業(yè)設(shè)計系，河北 秦皇島066004；2.東華大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海201600）

1 引言

目前，基 于 位 置 的 服 務(wù)LBS（Location－Based Services）［1，2］吸引了眾多的移動用戶。常見的例子包括興趣點POI（Points Of Interest）查找，它幫助用戶找到POI，如酒店和電影院等，并能提供豐富的訊息，如特別優(yōu)惠或代金券等。然而，與此同時，人們也對使用LBS時導(dǎo)致敏感信息泄露的問題倍加關(guān)注。

在任意路徑點移動模型［3，4］中，用戶可以在任意方向以任何速度移動，大多數(shù)現(xiàn)有的解決方案無法解決用戶在路網(wǎng)中移動的約束，即路網(wǎng)中用戶的移動和基于位置的服務(wù)處理受制于底層的道路網(wǎng)絡(luò)。

更具體地說，任意路徑點模型下所提供的保護對網(wǎng)絡(luò)約束移動模型是不充分的。例如，空間隱匿技術(shù)［5～10］通過空間隱匿區(qū)域來模糊精確位置，保護用戶的隱私，并用面積的大小作為度量指標。然而，這樣的指標不適用于路網(wǎng)模型，因為一個非常大的區(qū)域可能僅包含一個路段，使得攻擊者很容易追蹤移動用戶。此外，路網(wǎng)狀況，即網(wǎng)絡(luò)拓撲對查詢代價和通信效率也會產(chǎn)生重大影響，這是位置隱私保護解決方案中應(yīng)該重點關(guān)注的問題。例如，基于地理位置的查詢處理的最基本的操作——計算網(wǎng)絡(luò)中兩個點距離的復(fù)雜程度會隨底層網(wǎng)絡(luò)結(jié)構(gòu)的變化顯著不同。因此，通常采用基于路段的隱匿方法。

基于路段的隱匿方法減少了計算開銷，因為基于路段的隱匿區(qū)域比矩形隱匿區(qū)域返回更少的候選結(jié)果［11］。Kolahdouzan M 和Shahabi C［12］提出了基于泰森多邊形的網(wǎng)絡(luò)圖，將大的網(wǎng)絡(luò)分為小的泰森多邊形。它預(yù)計算中間結(jié)果并基于緩存的結(jié)果構(gòu)建查詢答案。Papadias D 等［13］提出了網(wǎng)絡(luò)擴展算法，從查詢點開始隱匿并通過邊擴展隱匿范圍，直到滿足用戶的隱私需求。該算法無法向用戶提供完全的保護，因為它遵循的最佳優(yōu)先搜索擴展過程，很容易被攻擊者加以利用。Wang T 和Liu L［14］提出了基于X－Star的隱匿算法，為用戶實現(xiàn)查詢處理成本和高隱私保護的平衡。另外，文獻［15，16］也對路網(wǎng)環(huán)境的隱私保護問題做了研究。

2 概念和模型

本節(jié)對路網(wǎng)模型、位置隱私模型以及相關(guān)概念進行闡述。

2.1 路網(wǎng)模型

路網(wǎng)模型為無向圖G（vG，εG），節(jié)點集vG和邊集εG分別代表道路接口和直接道路連接。路網(wǎng)模型如圖1 所示。dG（n）表示圖G中節(jié)點n的度。具體來說，如果dG（n）≥3，n被稱為交叉節(jié)點；如果dG（n）＝2，n被稱為中間節(jié)點；如果dG（n）＝1，n被稱為端節(jié)點。

為了模型化用戶移動所受的底層路網(wǎng)約束，引入了路段的概念：路段是邊的序列，這里每個都是不同的，并且對于i＝0或者i＝L，節(jié)點ni的度要么為1要么dG（ni）≥3，其余的節(jié)點dG（ni）＝2。即n0和nL要么是交叉節(jié)點要么是端節(jié)點，其余節(jié)點均為中間節(jié)點。

注意，每條邊要么自身就是一個路段要么唯一地屬于某條路段的一部分，也就是說可以將路網(wǎng)分割為路段集。因此，可以做如下假設(shè)：每個移動用戶沿著路段移動，并將其基于位置的查詢連同當前位置信息提供給LBS服務(wù)商，然后LBS基于提供的位置信息執(zhí)行查詢。

Figure 1 A road network model圖1 路網(wǎng)模型

2.2 位置隱私模型

考慮網(wǎng)絡(luò)約束移動模型下的兩種類型的隱私問題，即位置匿名和位置多樣性。第一個要求保證了一個特定的移動用戶在一組用戶（匿名集）中的不可分辨性，通常利用位置k－匿名［5，8］的概念。

定義1（位置k－匿名） 用戶提交的位置是k－匿名的，如果至少k－1個其他活動用戶提交相同的位置。

單純確保位置匿名的研究［5～9］未考慮底層的路網(wǎng)約束，所以在路網(wǎng)環(huán)境下不能提供足夠的保護。例如，在圖1中，假設(shè)用戶u3和u4發(fā)布k－匿名位置分別為A1和A2。假設(shè)A1和A2是大小相同且包含相同數(shù)量的活動用戶，依照標準的位置匿名概念，u3和u4被認為享受同等質(zhì)量的隱私保護。然而，對于攻擊者而言，追蹤u3要比u4容易得多，因為u3僅與單個路段有關(guān)，而u4與段集相關(guān)。直觀地說，從攻擊者的角度來看跟蹤用戶的難度與路段的數(shù)量成正比。這也促使引入第二個隱私度量標準——位置多樣性［17］。

定義2（路段l－多樣性） 用戶發(fā)布的位置是l－多樣性的，如果它滿足位置k－匿名且至少包含l個不同的路段。

為了滿足這些需求，提出了位置匿名化操作。

定義3（位置匿名化） 令q表示移動用戶u提交的基于位置的查詢。位置匿名化將q的精確位置信息用一個滿足u的服務(wù)配置的匿名位置來代替。

在路網(wǎng)環(huán)境下，假設(shè)匿名化操作在路段上進行，匿名位置由一組路段集組成。需要指出的是，為了便于描述，路段的長度因素未加討論；若要處理路段長度的非均勻性，也很簡單，如為短路段指定高多樣性要求，或?qū)㈤L路段劃分為一組短路段。

同時，引入可信的第三方位置匿名引擎LAE（Location Anonymization Engine），作為移動用戶與LBS提供商之間的中間層，并執(zhí)行位置匿名化操作。與其它方案相比，這種集中式LAE 架構(gòu)有更多的優(yōu)勢：（1）相比大量的個體LBS提供商與復(fù)雜的商業(yè)利益沖突，它更容易提供安全保護和操作規(guī)則；（2）在LAE的幫助下，用戶可以實現(xiàn)基于客戶端或P2P 對等架構(gòu)［10，18］所無法達到的隱私保證，如位置匿名性和多樣性；（3）此外，這種體系結(jié)構(gòu)已經(jīng)成功地應(yīng)用于各種位置私有化系統(tǒng)［5～8，19］。

LAE具體負責(zé)：（1）接收查詢和移動用戶的具體位置信息；（2）根據(jù)用戶的隱私需求，匿名化位置信息，并將其傳送到LBS提供者；（3）通過過濾假的信息，從服務(wù)提供者給出的候選結(jié)果集中提取準確的查詢結(jié)果；（4）傳遞給客戶確切的答案。

3 位置匿名操作過程

位置匿名操作包含兩個主要階段，匿名星選擇和超星構(gòu)建。簡單來說，在第一個階段，依據(jù)低成本星選擇策略，將一組鄰近查詢?nèi)航M在匿名星結(jié)構(gòu)中；在第二個階段，合并鄰近星形成超星結(jié)構(gòu)滿足個體的隱私需求。

3.1 匿名星選擇

首先介紹位置匿名的基本結(jié)構(gòu)——匿名星的概念。

定義4（匿名星） 對于網(wǎng)絡(luò)G中的交叉節(jié)點n，匿名星n是G的子圖，由n和所有與n相連接的路段組成。

根據(jù)這個定義，每個dG（n）≥3的節(jié)點n與一個唯一的匿名星φn相關(guān)聯(lián)。例如，在圖1中，匿名星由節(jié)點n4和段組成。

匿名星結(jié)構(gòu)具有一些優(yōu)異的特性：（1）它保留鄰近段的位置，將它作為匿名的基本單元，將會使匿名位置具有高度緊湊的結(jié)構(gòu)；（2）能夠索引，因為節(jié)點標識符可以代表一個星而沒有信息損失，用它代表匿名位置可以減少通信成本，并簡化實現(xiàn)。

給定路網(wǎng)G＝（vG，εG），可以構(gòu)建相應(yīng)的星形網(wǎng)絡(luò)，其中的每個節(jié)點代表G中的一個星，兩個節(jié)點是相鄰的如果G中相應(yīng)的星分享共同的段。圖2是圖1相應(yīng)的星圖網(wǎng)絡(luò)。需要指出的是，在Gφ中，所有邊都是單位長度，路網(wǎng)G中φi和φj的距離定義為在Gφ中的網(wǎng)絡(luò)距離，稱之為跨步（Hop），表示為hG(φi,φj)。例如，在圖1中，，因為它們在Gφ中的最短路徑由和組成。

Figure 2 A star－graph network model圖2 星圖網(wǎng)絡(luò)模型

如果路段上有活躍查詢，則這條路段被標記為是活動的。為了使模型抗推理攻擊和能夠適應(yīng)多查詢共享處理，在同一段上的所有查詢共享同一匿名位置。

對于某個活動段s上的查詢，如果選擇星φ作為匿名位置，就稱為φ“被選擇”，s被分配給φ，記為s←φ?？紤]段s有兩個節(jié)點和，如 果和都成立，那么s與兩個匿名星和相關(guān)聯(lián)，對圖1 中而言，即和。在這種情況下，需要確定將s分配給或中的哪一個。對于整個網(wǎng)絡(luò)而言，需要選擇一組星集Φ涵蓋所有活動段。

為了實現(xiàn)低查詢處理成本，希望將成本模型合并到選擇過程。令cost（φ）表示執(zhí)行匿名位置為φ的查詢處理成本，AS表示路網(wǎng)中當前活動段集，Φ是選定的星集，那么總成本最小化的問題可以表示為：

s.t.?s∈AS，? ∈Φ，s←φ

低成本段—星分配方案旨在找到一組涵蓋所有活動段的最低成本的星集。遺憾的是，這個優(yōu)化問題沒有有效的解決方案，除非P＝NP。

因此，代替試圖找到全局最優(yōu)解，提出一種有效的隨機算法，可以找到高質(zhì)量的近似解，并且對推理攻擊具有很好的魯棒性。

具體來說，插入新查詢及段s的操作（InsertQuery）分為以下四種情況：（1）如果某個星已經(jīng)覆蓋了s，該算法停止；（2）如果兩個星和都已經(jīng)選定而s未被覆蓋，則s分配給兩顆星之一的概率與相應(yīng)成本成反比；（3）如果只有一個或者被選中，s就分配給這個星；（4）如果沒有和被選中，則分配到其中一個星的概率與對應(yīng)的成本成反比。

本質(zhì)上，該方法將活動段s分配給的概率為，反之，分配給

3.2 超星的構(gòu)建

在前一階段，依據(jù)查詢處理成本，選擇一組星集覆蓋活動段。在這個階段，滿足移動用戶的隱私需求。這一目標通過合并相鄰的星形成超星結(jié)構(gòu)，充當其內(nèi)部查詢的匿名位置。

如圖2所示，假定用戶u3和u4分配給星用戶u2分配給星，用戶u1和u10分配給星。然而，單獨的包含的活躍用戶數(shù)并不能滿足用戶u3的的隱私需求。通過合并和，獲得一個超星ψ，滿足了所有用戶的需求。

現(xiàn)在，描述合并星形成超星結(jié)構(gòu)的過程（MergeStar）：從最初的星 開始，逐步增加鄰近星，直到超星內(nèi)的所有用戶的隱私需求得到滿足。具體來說，首先檢查星 是否已經(jīng)滿足用戶的隱私需求；如果沒有，迭代添加鄰近的活動星（如果可能）。如果存在這樣的星，依據(jù)一定的規(guī)則進行合并，形成新的超星。這種擴張過程迭代進行，直到滿足其內(nèi)所有用戶的隱私需求，或報告失?。ㄋ邢嚓P(guān)查詢將會推遲到隊列，等待新到來的查詢觸發(fā)匿名化）。

4 基于Hilbert序列的空間隱匿算法

基于Hilbert 序列的空間隱匿算法HSGCloaking通過五個步驟創(chuàng)建匿名區(qū)：構(gòu)建星形網(wǎng)絡(luò)，使用Hilbert排序?qū)⑿枪?jié)點映射Hilbert ID，從最高k－匿名度要求的用戶位置起始選擇星，擴展網(wǎng)絡(luò)直到滿足用戶的需求和重置網(wǎng)絡(luò)中其他用戶條件。

4.1 匿名步驟

步驟1構(gòu)建星形網(wǎng)絡(luò)。

在此階段，為每個dG（n）≥3的節(jié)點n都與一個唯一的星φn相關(guān)聯(lián)，Gφ中的每個星節(jié)點都對應(yīng)G中的一個節(jié)點。

步驟2星節(jié)點映射Hilbert ID。

在此步驟中，利用如圖3所示Hilbert空間填充曲線對星節(jié)點進行排序。

Figure 3 Hilbert filling curves圖3 Hilbert填充曲線

步驟3隱匿起始位置選擇。

隱匿的主要過程從這一步開始。當查詢位于段s上，s被分配給星 ，即s← ，那么 被選為匿名區(qū)域。如果星節(jié)點 包含最高k－匿名度要求的用戶，那么它被選為起始隱匿星。如圖4a所示，星節(jié)點（虛線）包含的用戶u3具有最高的k－匿名度要求因此星節(jié)點被選為匿名過程的起始位置。

步驟4網(wǎng)絡(luò)擴展。

在前一步，包含最高k－匿名度要求的星被選擇。在此步驟中，從所選擇的星開始擴展，擴大隱匿區(qū)域，直到滿足用戶的隱私需求。例如，在選星節(jié)點后，該算法擴展隱匿區(qū)域（虛線），直到它滿足用戶的要求，即覆蓋了u1、u2、u4和u10區(qū)域（如圖4a所示）。最后，它將這一區(qū)域作為匿名區(qū)，發(fā)送給LBS。

在網(wǎng)絡(luò)擴展之前，算法要檢查兩個屬性：（1）所包含的用戶數(shù)量；（2）所選星節(jié)點與鄰近星節(jié)點的Hilbert ID 差值。檢查后，算法決定擴展的方向。同時，逐步增加鄰近星，直到組中所有用戶的隱私需求得到滿足。

步驟5重置條件。

HSGCloaking算法重復(fù)步驟3和步驟4，直到網(wǎng)絡(luò)中其他用戶也形成組。在圖4b和圖4c中，另兩組的形成也基于最高k－匿名度要求的用戶的位置（虛線和點劃線）。

Figure 4 Illustration of forming groups圖4 形成組的過程表示

4.2 隱匿算法HSGCloaking

主要匿名過程如算法HSGCloaking所示。算法第1行首先生成星形網(wǎng)絡(luò)，在第2 行生成Hilbert曲線，在第3行合并Hilbert ID 與生成的星節(jié)點，第4行找出k－匿名度最高的用戶。第5～18行處理滿足用戶需求。如果在一個匿名星內(nèi)用戶的要求得到滿足，那么算法執(zhí)行第6～8 行。在第9～19行，算法根據(jù)用戶的需求擴展網(wǎng)絡(luò)。

算法1 隱匿算法HSGCloaking

5 性能分析

實驗在Windows系統(tǒng)，Pentium 4 2.81GHz處理器和2 GB 內(nèi)存上進行，用真實的路網(wǎng)驗證HSGCloaking 算法的性能。對HSGCloaking 方法在執(zhí)行成本、匿名成功率、平均匿名段數(shù)方面進行廣泛的實驗和性能測試。執(zhí)行成本指服務(wù)器端執(zhí)行整個匿名過程的時間。成功率指用戶的請求得到滿足的情況，平均匿名段數(shù)意味著根據(jù)用戶需求生成的匿名位置的平均尺寸。如表1所示，使用San Francisco路 網(wǎng)，其 中 包 含175 350 個 節(jié) 點 和223 200條邊。在這張地圖上，使用基于網(wǎng)絡(luò)的移動 對象生 成 器Brinkoff［20］生 成10 000 個 移 動 對象，模擬交通情況。

Table 1 Experiment parameters表1 實驗參數(shù)

將所提出的HSGCloaking算法與文獻［14］中的X－Star算法在平均執(zhí)行時間、匿名成功率、匿名區(qū)大小等方面做了比較。實驗結(jié)果顯示，所提出的HSGCloaking算法比X－Star算法具有更大的優(yōu)勢。

圖5顯示了兩種算法的平均執(zhí)行時間，顯示HSGCloaking 平 均 執(zhí) 行 時 間 低 于X－Star 幾 乎30%。起始時與X－Star的時間差異不太明顯，但隨著k－匿名度的增長，HSGCloaking能節(jié)約50%的執(zhí)行時間。表明X－Star的執(zhí)行時間隨k－匿名度的增加線性增長。然而，對于HSGCloaking，開始時執(zhí)行時間逐步增加，但k－匿名度達到一定值之后反而會降低，之后一直保持穩(wěn)定的狀態(tài)。

Figure 5 Average execution time圖5 平均執(zhí)行時間

如圖6 所示，X－Star的匿名成功率比HSGCloaking低很多。圖6中顯示匿名成功率隨匿名度的增加而降低。因為大的k－匿名度需要在特定的網(wǎng)絡(luò)區(qū)域有更多的用戶數(shù)，很難滿足大k－匿名度要求。

Figure 6 Anonymization success rates圖6 匿名成功率

實驗比較了X－Star和HSGCloaking 算法的平均路段數(shù)與k－匿名度的關(guān)系。圖7顯示X－Star隨著k－匿名度的增加，平均路段數(shù)線性增加。然而，當k－匿名度達到某個值后，它保持不變。HSGCloaking開始時平均路段數(shù)增加，達到一定k－匿名度之后反而會減少。當k－匿名度數(shù)值很高時，很難滿足用戶的需求，創(chuàng)建匿名區(qū)域?？紤]邊界節(jié)點，用戶查詢可能不執(zhí)行這些邊界星節(jié)點。因為一些節(jié)點不包含任何用戶，網(wǎng)絡(luò)需要擴展。因為邊界星節(jié)點選擇限制，會顯著地降低匿名成功率和減少匿名面積。

Figure 7 Anonymization areas圖7 匿名區(qū)大小

6 結(jié)束語

本文提出了適用于路網(wǎng)環(huán)境的隱匿算法HSGCloaking，保護用戶隱私。通過將一般網(wǎng)絡(luò)轉(zhuǎn)換為星形網(wǎng)絡(luò)，并進行Hilbert排序、隱匿星選擇合并操作滿足每個用戶的匿名要求?？蚣苤С謐－NN 和范圍查詢，在實際道路網(wǎng)絡(luò)上的實驗驗證了該隱匿模型的有效性。

［1］ Beresford A R，Stajano F.Location privacy in pervasive computing［J］.IEEE Pervasive Computing，2003，2（1）：46－55.

［2］ Bettini C，Wang S，Jagodia S.Protecting privacy against location－based personal identification［C］∥Proc of VLDB Workshop on Secure Data Management，2005：185－199.

［3］ Broch J，Maltz D A，Johnson D B.et al.A performance comparison of multi－h(huán)op wireless ad hoc network routing protocols［C］∥Proc of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking，1998：85－97.

［4］ Hyyti?E，Virtamo J.Random waypoint mobility model in cellular networks［J］.Wireless Networks，2007，13（2）：177－188.

［5］ Gruteser M，Grunwald D.Anonymous usage of location－based services through spatial and temporal cloaking［C］∥Proc of the 1st International Conference on Mobile Systems，Applications and Services，2003：31－42.

［6］ Mokbel M F，Chow C Y，Aref W G.The new casper：Query processing for location services without compromising privacy［C］∥Proc of the 32nd International Conference on Very Large Data Bases，2006：763－774.

［7］ Bamba B，Liu L，Pesti P，et al.Supporting anonymous location queries in mobile environments with privacy grid［C］∥Proc of the 17th International Conference on World Wide Web，2008：237－246.

［8］ Gedik B，Liu L.A customizableK－anonymity model for protecting location privacy［C］∥Proc of the 25th International Conference on Distributed Computing Systems，2005：620－629.

［9］ Ghinita G，Kalnis P，Skiadopoulos S.Prive：Anonymous location based queries in distributed mobile systems［C］∥Proc of the 16th International Conference on World Wide Web，2007：371－380.

［10］ Yiu M，Jensen C，Huang X，et al.Spacetwist：Managing the trade－offs among location privacy，query performance，and query accuracy in mobile services［C］∥Proc of IEEE 24th International Conference on Data Engineering，2008：366－375.

［11］ Peng W C，Wang T W，Ku W S，et al.A cloaking algorithm based on spatial networks for location privacy［C］∥IEEE International Conference on Sensor Networks，Ubiquitous and Trustworthy Computing，2008：90－97.

［12］ Kolahdouzan M，Shahabi C.Voronoi－basedknearest neighbor search for spatial network databases［C］∥Proc of the 30th International Conference on Very Large Data Bases，2004：840－851.

［13］ Papadias D，Zhang J，Mamoulis N，et al.Query processing in spatial network databases［C］∥Proc of the 29th International Conference on Very Large Data Bases，2003：802－813.

［14］ Wang T，Liu L.Privacy－aware mobile services over road networks［J］.Proceedings of the VLDB Endowment，2009，2（1）：1042－1053.

［15］ Palanisamy B，Ravichandran S，Liu L，et al.Road network mix－zones for anonymous location based services［C］∥Proc of IEEE 29th International Conference on Data Engineering（ICDE），2013：1300－1303.

［16］ Domenic M K，Wang Y，Zhang F，et al.Preserving users’privacy for continuous query services in road networks［C］∥Proc of IEEE 6th International Conference on Information Management，Innovation Management and Industrial Engineering（ICIII），2013：352－355.

［17］ Machanavajjhala A，Kifer D，Gehrke J，et al.L－diversity：Privacy beyondk－anonymity［J］.ACM Transactions on Knowledge Discovery from Data，2007，1（1）：1－36.

［18］ Ghinita G，Kalnis P，Skiadopoulos S.Prive：Anonymous location－based queries in distributed mobile systems［C］∥Proc of the 16th International Conference on World Wide Web，2007：371－380.

［19］ Beresford A R，Stajano F.Mix zones：User privacy in location－aware services［C］∥Proc of PerCom Workshops，2004：127－131.

［20］ Ku W S，Chen Y，Zimmermann R.Privacy protected spatial query processing for advanced location based services［J］.Wireless Personal Communications，2009，51（1）：53－65.