路網環境下基于星圖的位置隱私保護技術研究＊

侯士江，劉國華，候 英

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

1 引言

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

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

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

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

2 概念和模型

本節對路網模型、位置隱私模型以及相關概念進行闡述。

2.1 路網模型

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

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

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

Figure 1 A road network model圖1 路網模型

2.2 位置隱私模型

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

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

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

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

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

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

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

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

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

3 位置匿名操作過程

位置匿名操作包含兩個主要階段，匿名星選擇和超星構建。簡單來說，在第一個階段，依據低成本星選擇策略，將一組鄰近查詢群組在匿名星結構中；在第二個階段，合并鄰近星形成超星結構滿足個體的隱私需求。

3.1 匿名星選擇

首先介紹位置匿名的基本結構——匿名星的概念。

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

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

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

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

Figure 2 A star－graph network model圖2 星圖網絡模型

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

對于某個活動段s上的查詢，如果選擇星φ作為匿名位置，就稱為φ“被選擇”，s被分配給φ，記為s←φ。考慮段s有兩個節點和，如 果和都成立，那么s與兩個匿名星和相關聯，對圖1 中而言，即和。在這種情況下，需要確定將s分配給或中的哪一個。對于整個網絡而言，需要選擇一組星集Φ涵蓋所有活動段。

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

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

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

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

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

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

3.2 超星的構建

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

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

現在，描述合并星形成超星結構的過程（MergeStar）：從最初的星 開始，逐步增加鄰近星，直到超星內的所有用戶的隱私需求得到滿足。具體來說，首先檢查星 是否已經滿足用戶的隱私需求；如果沒有，迭代添加鄰近的活動星（如果可能）。如果存在這樣的星，依據一定的規則進行合并，形成新的超星。這種擴張過程迭代進行，直到滿足其內所有用戶的隱私需求，或報告失敗（所有相關查詢將會推遲到隊列，等待新到來的查詢觸發匿名化）。

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

基于Hilbert 序列的空間隱匿算法HSGCloaking通過五個步驟創建匿名區：構建星形網絡，使用Hilbert排序將星節點映射Hilbert ID，從最高k－匿名度要求的用戶位置起始選擇星，擴展網絡直到滿足用戶的需求和重置網絡中其他用戶條件。

4.1 匿名步驟

步驟1構建星形網絡。

在此階段，為每個dG（n）≥3的節點n都與一個唯一的星φn相關聯，Gφ中的每個星節點都對應G中的一個節點。

步驟2星節點映射Hilbert ID。

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

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

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

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

步驟4網絡擴展。

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

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

步驟5重置條件。

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

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

4.2 隱匿算法HSGCloaking

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

算法1 隱匿算法HSGCloaking

5 性能分析

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

Table 1 Experiment parameters表1 實驗參數

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

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

Figure 5 Average execution time圖5 平均執行時間

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

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

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

Figure 7 Anonymization areas圖7 匿名區大小

6 結束語

本文提出了適用于路網環境的隱匿算法HSGCloaking，保護用戶隱私。通過將一般網絡轉換為星形網絡，并進行Hilbert排序、隱匿星選擇合并操作滿足每個用戶的匿名要求。框架支持k－NN 和范圍查詢，在實際道路網絡上的實驗驗證了該隱匿模型的有效性。

［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－hop 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.