位置隱私保護的虛擬軌跡填充算法

付宇 王紅

摘 要：針對位置隱私保護中路網(wǎng)環(huán)境和歐氏空間環(huán)境對移動對象不同的約束限制，提出一種適用于這兩類不同空間約束特點的虛擬軌跡填充算法。該算法接管了用戶與位置服務提供者之間的交互，并構建了虛擬用戶軌跡對真實軌跡進行混淆填充，從而實現(xiàn)了真實軌跡的隱藏和保護。首先，對目標區(qū)域進行分區(qū)和匯聚點提取;隨后，以匯聚點為基礎進行軌跡分段和虛擬軌跡的生成;最后，通過構建時序預置算法和軌跡混淆填充算法實現(xiàn)了虛擬軌跡的合理分布，增加了將軌跡信息關聯(lián)到特定目標對象的難度。實驗結果表明，所提算法能夠在每用戶15次以內(nèi)的填充后將位置隱私披露風險概率從60%下降并穩(wěn)定在10%左右，軌跡隱私披露概率從50%下降并穩(wěn)定在6%左右，能達到較好的位置隱私保護的效果。

關鍵詞：基于位置的服務;路網(wǎng)環(huán)境;位置隱私保護;虛擬軌跡;匯聚點

中圖分類號：?TP309.2

文獻標志碼：A

Virtual trajectory filling algorithm for location privacy protection

FU Yu*， WANG Hong

College of Computer Science and Technology， Civil Aviation University of China， Tianjin 300300， China

Abstract：?In view of the different constraints on the moving objects between road network environment and Euclidean space environment， a virtual trajectory filling algorithm was proposed， which was applicable to both constraints. The interaction between the user and the provider of Location-Based Services （LBS） was taken over by the algorithm， and virtual user trajectory was constructed to confuse and fill the real trajectory， realizing the hiding and protection of the real trajectory. Firstly， the target region was partitioned and the points of convergence were extracted. Then， the trajectory segmentation and virtual trajectory were generated based on the convergence points. Finally， the reasonable distribution of the virtual trajectory was achieved by constructing the timing preset algorithm and the trajectory confusion filling algorithm， which increased the difficulty of associating the trajectory information with a specific target object. Experimental results show that after less than 15 virtual trajectories per user being filled， the probability of the location privacy disclosure of the target object is dropped from 60% to and stabilizes at around 10%， and the trajectory privacy disclosure probability is decreased from 50% to and stabilizes at about 6%， achieving good effect of location privacy protection.

Key words：?Location-Based Service （LBS）; road network environment; location privacy protection; virtual trajectory; convergence point

0 引言

基于位置的服務（Location-Based Service，LBS）是智能交通系統(tǒng)中各項綜合性交通運輸管理服務的基礎，其基本形式是客戶端將用戶身份標志號（IDentity，ID）、當前時刻、當前位置、將要前往的興趣點（Point Of Interest，POI）等數(shù)據(jù)發(fā)往LBS的服務提供端，然后期待后者返回興趣點的位置和導航路徑等[1-2]。攻擊者如果獲得這些信息則能夠挖掘出用戶的興趣、愛好、健康狀況等私人敏感信息，從而造成隱私泄露[3-5]。對于部分人員和場合而言，位置隱私泄露甚至超過定位精度成為客戶在接受智能交通服務時最為關心的問題。

目前的位置隱私保護方法主要包括K-匿名法和L-多樣性法等[6-8]。K-匿名法[9-10]將K個鄰近的移動對象泛化為 一個整體區(qū)域從而使得攻擊者無法將這K個對象單個區(qū)分開來;但該方法的位置服務精度不高，而且當區(qū)域內(nèi)對象過于集中時較易暴露目標對象的大概位置。

L-多樣性法[11-12]是將泛化技術作用于查詢內(nèi)容，使攻擊者不能將其與特定對象關聯(lián)起來。這兩類方法主要適用于歐氏空間，而現(xiàn)實中的LBS應用更多地存在于路網(wǎng)空間。對象的運動方向在歐氏空間中幾乎不受限，而路網(wǎng)環(huán)境下只能沿路徑方向。若將上述方法直接用于路網(wǎng)環(huán)境，由于可供猜測的空間大為減少，先前有效的方法在路網(wǎng)環(huán)境下被破解的可能性會增加[13-14]。本文提出的虛擬軌跡填充算法能夠在避免位置服務精度損失的同時，實現(xiàn)路網(wǎng)與歐氏空間通用環(huán)境下的位置隱私保護。

1 問題描述

路網(wǎng)模型可表示為一個無向圖 G 〈 V ，? E 〉。其中： V 包括了路網(wǎng)中的端點和交叉點，起始點和興趣點屬于其子集; E 代表邊集，e=〈vi， vj〉∈ E ，指兩點間的路段。通常基于位置的服務涉及客戶端user和服務提供端LBS provider?？蛻舳讼认蚍斩税l(fā)送興趣點位置請求，服務端則發(fā)回從當前位置到興趣點的路徑;運行一段時間后，LBS服務端能夠積累大量的與用戶ID關聯(lián)的足跡信息，如圖1（a）所示。假定攻擊者對LBS服務端的用戶軌跡信息具有持續(xù)觀察能力，則攻擊者較容易從中抽取出某個ID的軌跡，如圖1（b）所示。

本文的出發(fā)點是盡可能增加攻擊者通過歷史軌跡信息挖掘出真實用戶身份的難度。對攻擊者而言，在LBS服務端能夠得到的數(shù)據(jù)包括：1）某ID在地圖上在某時刻的位置以及其關心的興趣點;2）某ID形成的軌跡;3）不同時刻興趣點所形成的目標集合。

然而即便擁有這些信息，攻擊者能否正確關聯(lián)出目標對象，仍存在以下不確定性：1）通過ID不能簡單對應到某個真實用戶;2）服務端收到的位置點坐標可能經(jīng)過了刻意模糊或干擾;3）軌跡可能是雜亂無章的——軌跡和ID的對應關系經(jīng)過了某種變換。

K-匿名法就是利用了上述中的第2）點，位置信息經(jīng)過了匿名后成為模糊的信息，從而不再能夠通過位置來區(qū)分不同的用戶[15-16]。但對于用戶密度較高的區(qū)域，經(jīng)匿名后，其位置信息并沒有獲得足夠的模糊化。本文提出的虛擬軌跡填充算法綜合利用了另外兩種不確定性來避免這一缺陷。

2 虛擬軌跡填充算法

如圖2所示，整個虛擬軌跡填充系統(tǒng)涉及三個對象：客戶端user、位置隱私保護服務器（Location Privacy Protection Server，LPPS）和LBS服務端， 主要的虛擬軌跡填充功能由介于客戶端和LBS服務端之間的位置隱私保護服務器LPPS完成。算法總體分為離線預處理、匯聚點提取和軌跡填充三個階段。

2.1 離線預處理階段

離線預處理為數(shù)據(jù)訓練階段，主要完成以下三項工作：1）為隱私保護服務器LPPS建立目標區(qū)域的基本路網(wǎng)結構;2）根據(jù)歷史交通流量信息產(chǎn)生交通匯聚點列表;3）針對目標區(qū)域生成分區(qū)模板。圖3給出了一個針對圖1的分區(qū)示例，空間劃分為兩個中央分區(qū)（分區(qū)1和2）以及4至8個周邊分區(qū)（圖中的分區(qū)3至8）。每個分區(qū)包含一個分區(qū)匯聚點，分區(qū)及分區(qū)匯聚點的確定在匯聚點提取階段進行綁定。中央分區(qū)一般包含流量較大的匯聚點，并且對周邊分區(qū)具有較好的可達性。兩個中央分區(qū)中的一個為真實對象所經(jīng)過，而另一個中央分區(qū)為填充的虛擬對象匯聚所用。兩個中央分區(qū)的設置增加了攻擊者破解真實軌跡的難度。

2.2 匯聚點提取階段

在圖2中，用戶user首先發(fā)出的一個POIA興趣點服務請求給隱私保護服務器LPPS。

圖2中各步驟具體操作如下：

（1）發(fā)送查詢q=〈IDuser， T， LOCuser， POI〉;

（2）初步預測軌跡并對之分段，對原始ID和POI進行混淆保護;

（3）發(fā)送保護后的q′=〈ID_temporary_user， T， LOC_temporary_user， POI′〉;

（4）返回POI′的路徑信息;

（5）進行分區(qū)綁定，確定路徑關鍵匯聚點list_of_candidate_point;

（6）根據(jù)起始時間、運動速度，對user關鍵匯聚點預置時序（算法1）;

（7）將主軌跡的起點、關鍵匯聚點序列、興趣點填入new_query_list;

（8）進行主軌跡填充，將匯聚點按時序放入待混淆列表mix_list;

（9）從mix_list取出表頭節(jié)點進行虛擬軌跡填充（算法2）;

（10）對填充中產(chǎn)生的匯聚點預置時序;

（11）判斷是否需要進行均衡填充，若是，則將新產(chǎn)生的匯聚點按時序放入mix_list;

（12）將虛擬軌跡的起點、關鍵匯聚點序列、興趣點填入new_query_list，并返回（9）進行循環(huán)，直到mix_list列表被取空;

（13）依次取出new_query_list中的每個節(jié)點，對進入該節(jié)點的軌跡進行ID混淆（算法3），隨后根據(jù)這些節(jié)點對構造新的〈LOC， POIX〉請求;

（14）發(fā)送新請求fq=〈ID_F_user， T， LOC_F_user，POIX〉;

（15）為所有請求計算并返回〈LOC_F_user，POIX〉.route;

（16）恢復用戶user真實請求的POI與路徑;

（17）將恢復后的結果返回給終端用戶。

對LPPS而言，在接到請求后先對用戶ID和POI進行保護，見圖2中第（1）、（2）步，保護措施包括初步預測用戶軌跡并進行原始請求變換。隨后在第（3）步將變換后的請求轉發(fā)給LBS服務者。在得到返回的相關興趣點位置后，LPPS將根據(jù)客戶端當前位置、興趣點目的地位置以及預處理階段建立起來的路網(wǎng)結構和匯聚點信息，在第（5）步進行分區(qū)綁定，并確立目標軌跡的候選匯聚點列表list_of_candidate_point。

分區(qū)綁定時將根據(jù)候選匯聚點列表中的真實對象軌跡對預處理時生成的分區(qū)模板進行調(diào)整，使得真實軌跡中除起始節(jié)點和目標節(jié)點外的中間匯聚點至少有一個落在中央分區(qū)（如圖3的分區(qū)1或2）中，而其他匯聚點按時間先后順序分別落入不同的周邊分區(qū)。綁定過程中，從真實軌跡在每個分區(qū)的候選匯聚點中選擇一個作為分區(qū)匯聚點，并最終形成待混淆列表mix_list，其內(nèi)容為list_of_candidate_point的子集，是虛擬軌跡注入并發(fā)生ID交換的地方。這里的中央分區(qū)是針對真實軌跡的中間段而言的，非地理中央概念。當真實軌跡偏置于地圖某一邊角地區(qū)時，中央分區(qū)亦需跟隨調(diào)整，此時可能在某個方向沒有周邊分區(qū)。

隨后在圖2第（6）步中依據(jù)移動對象的起始時間和運動速度調(diào)用route_timing算法（算法1）設定候選匯集點的到達時序，這里list_of_candidate_point列表作為輸入，與算法中的route_list列表進行合一。算法流程如下：待填充的路徑放在route_list路由列表中，并且從基準點開始，分別向前填充前序路徑（算法1步驟2））和向后填充后繼路徑（算法1步驟3））。填充需要以當前節(jié)點（cur_node）、到達當前節(jié)點時刻（node.time）和目標對象的運動速度speed[user_id]為輸入，得到對象到達下一節(jié)點的時刻。

算法1? route_timing。

程序前

輸入?? user_id， route_list[ ]， base_node， base_time

//用戶id，關鍵匯聚點列表，基準節(jié)點，基準時間

輸出?? route_list[ ] with timing slot filled

//填充了時序域的關鍵匯聚點列表

BEGIN：

步驟1

1）

route ← route_list.get_route（user_id）;

//從關鍵匯聚點列表中得到當前用戶的路徑

pre_route_list ← ???route.get_pre_route_list（node_base）;

//得到當前基準點的前序路徑

post_route_list ← ???route.get_post_route_list（node_base）;

//得到當前基準點的后繼路徑

步驟2

2）

cur_node ← base_node;

//得到基準節(jié)點

while（pre_node ← get_next_pre（cur_node））

{?? //基于基準時間，對前序路徑填充時序

route[pre_node（cur_node）].time ← base_time-distance（pre_node，cur_node）/speed[user_id]

cur_node ← pre_node;

//將前一個節(jié)點作為當前待填充節(jié)點

}

步驟3

3）

cur_node ← base_node;

//回到基準節(jié)點，開始填充后繼節(jié)點的時序

while（post_node ← get_next_post（cur_node））

{?? //基于基準時間，對后繼路徑填充時序

route[post_node].time ← time_base+ distance（post_node，cur_node）/speed[user_id]

cur_node ← post_node;

}

END

程序后

在本階段的最后（圖2的第（7）步）將會產(chǎn)生輸出工件new_query_list，其內(nèi)容為替換后的新興趣點列表。這樣原用戶的一個興趣點（對應完整的一條軌跡）替換為多個興趣點（對應多個分段軌跡）。在算法的最后，該列表中所有的興趣點請求將會發(fā)往LBS服務端（但原有用戶與興趣點之間的對應關系已被破壞）。在算法隨后的步驟中，new_query_list將進一步加入新的虛擬對象興趣點請求。

2.3 虛擬軌跡填充階段

從圖2的第（8）步開始，LPPS針對真實對象軌跡進行虛擬軌跡的注入，稱為主軌跡填充。填充方法是不斷從mix_list中取出表頭節(jié)點作為注入點調(diào)用trace_mixing算法（算法2）進行填充。算法調(diào)用時，作為參數(shù)的mix_list列表與算法內(nèi)的list_of_rendezv列表合一。第（9）、（10）步的虛擬軌跡注入并配置新節(jié)點時序的工作將會被反復進行，直到判斷為不再需要注入新的虛擬軌跡。

算法2? trace_mixing。

程序前

輸入?? route[base_user.id]

//用戶id的待混淆軌跡，內(nèi)容為關鍵匯聚點序列

//〈start_node， {list_of_rendezv[ ]}， end_note〉

輸出?? fake_trace[i] for each rendezv[i]

//針對每個匯聚點的填充軌跡

BEGIN：

步驟1??? ?1）

1）當CURRENT_RENDEZVA屬于周邊區(qū)域時（如圖4、圖5中的分區(qū)SE），從以下四種情況中任選其一進行填充（由于相似性，算法2只列出了步驟2.1）和步驟2.3）的偽碼）：

a）對應算法2步驟2.1）與圖4，假定當前注入點為〈n1：t1〉，隨機選擇當前匯聚點相鄰周邊區(qū)域作為虛擬軌跡X的起始區(qū)域（圖4中AREA_STARTX），選取其區(qū)域內(nèi)一匯聚點（如圖4中n5）為虛擬軌跡X的前序節(jié)點;此時虛擬路徑不通過中央?yún)^(qū)域，且當前匯聚點CURRENT_ RENDEZVA所在區(qū)域為路徑X的目的區(qū)，虛擬興趣點POIX（步驟2.1）中的poi_fake，圖4中的n7）在CURRENT_ RENDEZVA 所在區(qū)域（圖4中分區(qū)SE）。

b）隨機選擇一個與待混淆興趣點區(qū)域不同的相鄰周邊區(qū)域作為虛擬軌跡X的目的區(qū)域（AREA_ ENDX），選取其區(qū)域內(nèi)一匯聚點作為虛擬軌跡X的后繼節(jié)點;此時虛擬路徑不通過中央?yún)^(qū)域，且當前匯聚點CURRENT_ RENDEZVA所在區(qū)域為路徑X的起始區(qū)，需在該區(qū)生成一個虛擬起始點START_ NODEX（對應算法2步驟2.2））。

圖4示例填充虛擬軌跡之前：

mix_list： {n1：t1; n2：t2; n3：t3; …}

new_query_list： {〈A， n0→n1， t0〉; 〈A， n1→n2， t1〉; …}

圖4示例填充虛擬軌跡之后：

mix_list： {n5：（t1-s0）; n2：t2; n3：t3; …}

new_query_list： {〈X， n5→n1， （t1-s0）〉; 〈A， n0→n1， t0〉; 〈A， n1→n2， t1〉; 〈X， n1→n7， t1〉; …}

c）對應算法2步驟2.3）與圖5，選擇另一中央?yún)^(qū)域內(nèi)匯聚點（如圖5中分區(qū)C1的節(jié)點n5）為虛擬軌跡X的前序節(jié)點，此時虛擬軌跡X通過中央?yún)^(qū)域（圖5分區(qū)C1），且當前匯聚點CURRENT_ RENDEZVA所在區(qū)域（圖5分區(qū)SE）為虛擬軌跡X的目的區(qū)（AREA_ENDX），其虛擬興趣點POIX在CURRENT_ RENDEZVA所在區(qū)域選擇（圖5中的n8）。

d）選擇另一中央?yún)^(qū)域（如圖3中的分區(qū)1）內(nèi)匯聚點為虛擬軌跡X的后繼節(jié)點，此時虛擬軌跡通過中央?yún)^(qū)域，且當前匯聚點（CURRENT_RENDEZVA）所在區(qū)域為虛擬軌跡X的起始區(qū)（AREA_ STARTX），需在該區(qū)生成一個虛擬起始點START _NODEX（對應算法2步驟2.4））。

圖5示例填充虛擬軌跡之前：

mix_list： {n1：t1; n2：t2; n3：t3; …}

new_query_list： {〈A， n0→n1， t0〉; 〈A， n1→n2， t1〉; …}

圖5示例填充虛擬軌跡之后：

mix_list： {n5：（t1-s0）; n6：（t1-s1）; n2：t2; n3：t3; …}

new_query_list： {〈X， n5→n1， （t1-s0）〉; 〈A， n0→n1， t0〉; 〈A， n1→n2， t1〉; 〈X， n1→n8， t1〉; …}

2）當CURRENT_RENDEZVA屬于中央?yún)^(qū)域時（如圖6分區(qū)C2）：

a）隨機選擇一個與待混淆用戶A起始區(qū)域不同但相鄰的周邊區(qū)域（圖6中分區(qū)E）作為虛擬軌跡X的起始區(qū)域（AREA _STARTX），并在該區(qū)域內(nèi)隨機選擇虛擬軌跡起始點START_NODEX（如圖6中節(jié)點n6）;

b）在與起始區(qū)對應（相對于中央?yún)^(qū)域）的另一個半?yún)^(qū)隨機選擇一個周邊區(qū)域（如圖6中分區(qū)W）作為虛擬軌跡目的區(qū)（AREA_ENDX），并在該區(qū)域內(nèi)隨機選擇虛擬軌跡興趣點POIX（如圖6中節(jié)點n9）。

圖6示例填充虛擬軌跡之前：

mix_list： {n2：t2; n3：t3; …}

new_query_list： {〈A， n1→n2， t1〉; 〈A， n2→n3， t2〉; …}

圖6示例填充虛擬軌跡之后：

mix_list： {n5：（t2-s0）; n6：（t1-s1）; n2：t2; n3：t3; …}

new_query_list： {〈X， n5→n2， （t2-s0）〉; 〈A， n1→n2， t1〉; 〈A， n2→n3， t2〉; 〈X， n2→n7， t2〉; …}

主軌跡填充完畢后可能出現(xiàn)干擾軌跡依然數(shù)量不多的情況，因而在圖2的第（11）步對交匯軌跡數(shù)較少的匯聚點進行補充填充，稱為均衡填充。該過程與主軌跡填充算法相似，但只針對出入度較少的匯聚點。填充的過程中所產(chǎn)生新的軌跡匯聚點是否繼續(xù)放入mix_list列表取決于填充的終止條件。若需要終止，則新產(chǎn)生的匯聚點不加入mix_list中，該列表中的節(jié)點取空后填充過程將終止。判斷是否終止填充的依據(jù)可以是一個給定的總填充軌跡數(shù)量上限，也可以根據(jù)填充所達到的隱私保護度。除了mix_list列表，新產(chǎn)生虛擬軌跡的中間匯聚點和虛擬興趣點也會在圖2的第（12）步中加入到new_query_list列表，并最終會被發(fā)往LBS服務提供端。

接下來在圖2的第（13）步調(diào)用id_mixing過程（算法3）對時間窗time_margin范圍內(nèi)近似同時進入?yún)R聚點的軌跡進行ID混淆。此過程使得進入?yún)R聚點的軌跡-ID對應關系在離開匯聚點時發(fā)生錯亂，從而使得攻擊者追蹤識別某條完整軌跡的難度大為增加。

算法3? id_mixing。

程序前

步驟?? current_rendez， route_list[ ]， time_margin

//當前匯集點，路由列表，時間窗

步驟?? route_list[ ] with user_id has been changed at current_ rendez

//ID混淆后的路由列表

BEGIN：

步驟1

1）

cur_node ← current_rendez.get_node;

cur_time ← current_rendez.get_time;

步驟2

2）

for each route[i] ∈ route_list[ ] that cur_node ∈ route[i]

//經(jīng)過當前節(jié)點的所有路徑

if route[i].get_time（cur_node）- cur_time

//在時間窗內(nèi)到達可視為交匯

步驟2.1

2.1）

arriv_list[i].user_id←route[i]. user_id;

//arriv_list為在時間窗內(nèi)進入此匯集點的所有用戶

//軌跡，分別得到此軌跡的用戶ID和軌跡ID

步驟2.2

2.2）

arriv_list[i].route_id←route[i]. route_id;

}

步驟3

3）

depart_ list[ ] ← Collections.shuffle（arriv_list[ ]. user_ id， arriv_list[i].route_id）;

// depart_ list為用戶ID混淆后的輸出路由

END

程序后

在算法3的步驟3執(zhí)行完后，new_query_list列表中用戶ID（如圖4至圖6中new_query_list結構里的用戶X和A）與興趣點請求之間的對應關系將會被修改，從而通過①軌跡分段和②ID混淆，實現(xiàn)了對原始用戶信息和POI請求信息對應關系的隱藏。在圖2的第（14）步至（15）步，這些錯亂的信息通過new_query_list被傳遞給了LBS服務提供者;后者不能分辨哪些是真實用戶，哪些是虛擬用戶，所有請求都被視為正常請求并返回這些請求的興趣點位置和路由。

在圖2的第（16）步，LPPS從收到的LBS服務端回復中，過濾出真實用戶的興趣點坐標和路徑，并將這些結果在第（17）步返回給終端用戶。而對終端用戶而言，就如同直接從LBS服務者拿到請求結果一樣。隱私保護服務器LPPS所做的虛擬軌跡注入等保護措施對終端用戶而言是透明的。

3 隱私保護度

位置隱私保護的度量體現(xiàn)在位置隱私披露風險LD（Lacation Disclosure）和軌跡隱私披露風險TD（Trajectory Disclosure）兩個層面上。當攻擊者沒有關于用戶特別的背景信息時（比如用戶經(jīng)常訪問的路徑或區(qū)域），則針對某個位置攻擊者只能以等概率猜測方式猜測其和某個特定對象的關聯(lián)關系。若整個軌跡觀測期共m個時間片，位置隱私披露風險可以定義為：

LD= 1 m ∑ m i=1? 1 Si

（1）

其中Si為第i個時間片內(nèi)觀測到的可區(qū)分位置個數(shù)。

同樣，在沒有過多的背景信息下，攻擊者也只能以等概率猜測方式猜測某條軌跡可能對應于某個特定對象。假定n為LBS服務端看到的至少存在一個與其他軌跡交點的軌跡數(shù)，在經(jīng)過位置隱私保護算法處理后，因為沒有特別的背景知識，只能等概率從這n條相交的軌跡所可能形成的軌跡形態(tài)總數(shù)中進行猜測。設Tn為這樣的軌跡總數(shù)，且另有k條軌跡不與任何其他軌跡相交，則軌跡隱私披露風險可定義為：

TD= 1 Tn+k

（2）

以圖7（a）所示場景為例，攻擊者需要猜測A、B、C三個用戶的軌跡哪條可能是目標對象的，其位置隱私披露概率計算如表1所示。根據(jù)式（1），在t1、t3和t6時刻，因為能區(qū)分3個不同對象，因而S1、S3、S6均為3;而在t2、t4、t5時刻因為軌跡相交的原因，S2、S4、S5均為2。就這6個時間片而言，其平均位置隱私披露風險LD為（1/3+1/2+1/3+1/2+1/2+1/3）/6=0.417，大于1/3。

圖7（b）顯示了整個軌跡被匯聚點分割成片段后多條軌跡相互混淆的情況。初始的A、B、C三個移動對象經(jīng)過交匯點R[1]、R[2]和R[3]后因為發(fā)生了ID混淆，若沒其他背景信息，攻擊者只能從以下可能軌跡中進行等概率猜測：

1）A： E[1]→E[4]→E[7]，B： E[2]→E[5]→E[8]，C： E[3]→E[6]→E[9]。

2）A： E[1]→E[4]→E[7]，B： E[2]→E[5]→E[9]，C： E[3]→E[6]→E[8]。

3）A： E[1]→E[5]→E[8]，B： E[2]→E[4]→E[7]，C： E[3]→E[6]→E[9]。

4）A： E[1]→E[5]→E[8]，B： E[2]→E[4]→E[6]→ E[9]，C： E[3]→E[7]。

5）A： E[1]→E[5]→E[9]，B： E[2]→E[4]→E[6]→ E[8]，C： E[3]→E[7]。

6）A： E[1]→E[5]→E[9]，B： E[2]→E[4]→E[7]，C： E[3]→E[6]→E[8]。

7）A： E[1]→E[4]→E[6]→ E[8]，B： E[2]→E[5]→E[9]，C： E[3]→E[7]。

8）A： E[1]→E[4]→E[6]→ E[9]，B： E[2]→E[5]→E[8]，C： E[3]→E[7]。

一共8種可能的軌跡，根據(jù)式（2），Tn=8，k=0，軌跡隱私披露風險TD的值為1/（8+0）=0.125，遠小于沒有經(jīng)過任何位置隱私保護處理時的值1/3。

4 算法性能評估

1）計算復雜度。

在匯聚點提取階段中匯聚點的確定和地圖分區(qū)主要依據(jù)積累的熱點歷史信息，其時間復雜度與所關注地區(qū)的面積相關，可以作為預處理放在系統(tǒng)主循環(huán)之外。算法主體的時間復雜度由主軌跡填充和均衡填充過程決定，其時長取決于對路徑經(jīng)過的匯聚點和關聯(lián)分區(qū)的遍歷。若n為路徑經(jīng)過的匯聚點數(shù)，q為目標區(qū)域分區(qū)數(shù)，算法時間復雜度可表示為Ο（n×q）。

2）可擴展性與隱私保護度。

為考察算法實現(xiàn)位置隱私保護的效果，以及待保護對象的數(shù)量和填充的虛擬軌跡的數(shù)量對算法性能的影響，在運行環(huán)境為Intel Core i5-4300M CPU、8GB PC3-12800 RAM的64位Windows 10機器上，以圖3所示的路網(wǎng)環(huán)境對算法進行了驗證。簡單起見，路網(wǎng)被劃分為固定的2個中央分區(qū)和6個邊緣分區(qū);待保護用戶的服務發(fā)起點和興趣點也固定為在路由中有適中出入度的節(jié)點。圖8（a）給出了分別為單個用戶、3個待保護并發(fā)用戶和5個待保護并發(fā)用戶的情況下，位置隱私披露概率隨填充虛擬用戶數(shù)變化的對比結果;圖8（b）為相應的軌跡隱私披露概率的對比情況。鑒于算法2中生成虛擬軌跡的隨機性，實驗中位置隱私披露概率值和軌跡隱私披露概率值為3次實驗的平均值。

從圖8可以看出，對于單個待保護用戶而言，經(jīng)過大約10次虛擬用戶的注入后，位置隱私披露概率從62%下降到12%左右，軌跡隱私披露概率從50%下降到7%左右，兩者下降效果顯著，且之后趨于平穩(wěn)。考慮到算法生成的虛擬請求對LBS服務端造成的載荷增長，可以認為多于10個虛擬用戶之后的填充不是必要的。

對于多個用戶需求位置隱私保護情況，當多個用戶之間時間間隔比較大，即不能看作是并發(fā)時，每個用戶的軌跡填充可看作是獨立、互不影響的，算法效果等同于單用戶。當多個用戶可看作并發(fā)時，對某個用戶填充的軌跡會對其他用戶的隱私披露概率產(chǎn)生影響。從圖8的實驗結果看到，3個并發(fā)用戶填充5輪15次后，以及5個并發(fā)用戶填充4輪20次后，其保護效果與單用戶14次的填充相當，總體上節(jié)省了填充開銷。不過由于算法是針對每個用戶逐次進行填充，當并發(fā)用戶過多時，新生成的虛擬軌跡在地圖中的路徑重疊現(xiàn)象會造成算法的保護性能下降。

3）通信開銷與負荷。

算法中一次興趣點POI請求的消息格式為q=〈IDuser， time， Location（x， y）， POI〉，LBS回復消息格式為〈IDuser， time， start_node（x，y）， {list_of_route}， end_note（x，y）〉。算法的Java版本中這些消息使用JSON-Gzip壓縮格式傳送，單個請求消息大小約為5KB量級，平均包含3個中間路由節(jié)點的回復消息大小約為20KB量級。

實驗中，一條真實用戶軌跡大多被分為初始分區(qū)、中央分區(qū)和目的分區(qū)三段，主軌跡填充階段會有3條虛擬軌跡與主軌跡相交，而均衡填充階段會有6至10條的虛擬軌跡相互進行填充（假設均衡填充的結束條件為所有8個分區(qū)的匯聚點至少有2條軌跡交匯）。因此在沒有加入隱私保護功能前，客戶端和LBS服務端之間的通信在路網(wǎng)信息每個更新周期內(nèi)只有一個POI請求和返回組成的通信開銷，而在加入隱私保護服務器LPPS后，LPPS與LBS提供者之間的通信開銷上升為每更新周期約9至13個POI請求和返回消息對;相應的LBS服務提供端在單更新周期內(nèi)，原本只需為每個客戶提供1次POI定位和導航服務的工作負荷，現(xiàn)在變成了需進行9至13次的定位和導航服務。

與近期同樣針對路網(wǎng)結構的位置隱私保護算法相比較，文獻[14] 使用錨點的概念實現(xiàn)路網(wǎng)環(huán)境下位置服務的間接查詢，在連續(xù)查詢時利用緩存信息減少查詢的次數(shù)，通信開銷要低于本文的方法。但組織用戶共用錨點的操作其實與構造匿名框的優(yōu)缺點是相似的，從錨點到用戶本地的導航需要更多的支撐數(shù)據(jù)和計算量。文獻[17] 專門針對連續(xù)查詢中查詢發(fā)起時間的設置問題進行了研究，通過構建匿名子網(wǎng)和k近鄰安全區(qū)對達成匿名區(qū)時占用的計算資源進行了優(yōu)化。該方法隨著查詢者運動速度和POI興趣點密度的增加，匿名保護服務器端處理時間增幅越大。本文方法POI的定位是在算法開始時一次性計算完成，不會出現(xiàn)隱私保護服務器的工作負荷隨著POI數(shù)目的增長而發(fā)生激增的現(xiàn)象。文獻[18] 對興趣點記錄和查詢結果進行了加密，以路網(wǎng)頂點作為基礎進行相對位置查詢，其特點是對LBS服務的基本模式進行了改動，需要修改原有的LBS服務方代碼來加入加密和解密模塊。本文的方法LBS服務方代碼無需任何變化。

5 結語

本文提出的虛擬軌跡填充算法

通過注入一定數(shù)量的虛擬用戶、虛擬請求和虛擬軌跡，并將它們與真實軌跡混雜在一起，降低了LBS服務端的攻擊者追蹤和關聯(lián)到正確移動對象的概率。該算法首先對真實軌跡進行分段，并對初始ID和POI進行混淆和保護;在生成新的虛擬軌跡后與原軌跡分別進行主軌跡混淆填充和多輪均衡填充，并在LBS服務端形成干擾性的虛擬用戶和虛擬請求。這些虛擬請求與真實軌跡請求混雜在一起，增加了攻擊者追蹤真實軌跡的難度。驗證實驗結果表明，本文算法能夠以不大的計算開銷實現(xiàn)位置隱私披露概率和軌跡隱私披露概率的顯著下降并趨于穩(wěn)定。由于算法基于針對每個用戶作為單獨的個案逐例進行虛擬軌跡的填充，因而適合針對少量VIP用戶實現(xiàn)無位置服務精度損失的隱私保護;而對于大量并發(fā)用戶的保護需求，本文算法生成合理虛擬路徑的計算開銷較大，同時也面臨著虛擬路徑重疊問題，此時需要考慮與其他算法相結合，并解決如何降低對LBS服務精度的影響以及如何適用于路網(wǎng)環(huán)境等問題。

參考文獻

[1]?劉成.LBS定位技術研究與發(fā)展現(xiàn)狀[J].導航定位學報，2013，1（1）：78-83. （LIU C. Research and development status of LBS positioning technology[J]. Journal of Navigation and Positioning， 2013， 1（1）： 78-83.）

[2]?趙軍，車紅巖.基于位置服務的應用技術和發(fā)展趨勢[J].測繪科學，2016，41（4）： 171-176， 189. （ZHAO J， CHE H Y. Application techniques and development trends of LBS[J]. Science of Surveying and Mapping， 2016， 41（4）： 171-176， 189.）

[3]?ANDRS M E， BORDENABE N E， CHATZIKOKOLAKIS K， et al. Geo-indistinguishability： differential privacy for location-based systems [C]// Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. New York： ACM， 2013： 901-914.

[4]?WERNER M. Privacy protected communication for location based services [J]. Security and Communication Networks， 2016， 9： 130-138.

http：//xueshu.baidu.com/s？wd=paperuri%3A%282c39078868f290710a285aaa8668c2cf%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fonlinelibrary.wiley.com%2Fdoi%2F10.1002%2Fsec.330%2Fpdf&ie=utf-8&sc_us=5825488878314576246&sc_as_para=sc_lib%3A

[5]?ZHOU T. Understanding location-based services users privacy concern： an elaboration likelihood model perspective [J]. Internet Research， 2017， 27（3）： 506-519.

[6]?張學軍，桂小林，伍忠東.位置服務隱私保護研究綜述[J].軟件學報，2015，26（9）：2373-2395. （ZHANG X J， GUI X L， WU Z D. Privacy preservation for location-based services： a survey[J]. Journal of Software， 2015， 26（9）： 2373-2395.）

[7]?許明艷，趙華，季新生.位置服務隱私保護技術研究綜述[J].信息工程大學學報，2015，16（5）：543-551. （XU M Y， ZHAO H， JI X S. Survey of location privacy protection technology [J]. Journal of Information Engineering University， 2015， 16（5）： 543-551.）

[8]?萬盛，李鳳華，牛犇，等.位置隱私保護技術研究進展[J].通信學報，2016，37（12）：1-18. （WAN S， LI F H， NIU B， et al. Research progress on location privacy-preserving techniques [J]. Journal on Communications， 2016， 37（12）： 1-18.）

[9]?HE Z Q， CHEN G. Improvement of K-anonymity location privacy protection algorithm based on hierarchy clustering [J]. Applied Mechanics and Materials， 2014， 3360（599/600/601）： 1553-1557.

[10]?熊婉竹，李曉宇.基于匿名路由的移動位置隱私保護[J].計算機科學，2018，45（10）：142-149. （XIONG W Z， LI X Y. Mobile location privacy protection based on anonymous routing [J]. Compuer Science， 2018， 45（10）： 142-149.）

[11]?孫丹丹，羅永龍，范國婷，等.基于軌跡形狀多樣性的隱私保護算法[J].計算機應用，2016，36（6）：1544-1551. （SUN D D， LUO Y L， FAN G T， et al. Privacy protection algorithm based on trafectory shape diversity[J]. Journal of Computer Applications， 2016， 36（6）： 1544-1551.）

[12]?胡德敏，詹涵.差分擾動的均衡增量近鄰查詢位置隱私保護方法[J].小型微型計算機系統(tǒng)，2018，39（7）：1482-1486. （HU D M， ZHAN H. Homogeneous incremental nearest neighbor query method based on differential perturbation for location privacy protection [J]. Journal of Chinese Computer Systems， 2018， 39（7）： 1482-1486.）

[13]?LIU K G， ZHANG J P， YANG J. Privacy preserving for location-based services in road networks [J]. Advanced Materials Research， 2014， 3349（998/999）： 1165-1168.

[14]?周長利，馬春光，楊松濤.路網(wǎng)環(huán)境下保護LBS位置隱私的連續(xù)KNN查詢方法[J].計算機研究與發(fā)展，2015，52（11）：2628-2644. （ZHOU C L， MA C G， YANG S T. Location privacy-preserving method for LBS continuous KNN query in road networks [J]. Journal of Computer Research and Development， 2015， 52（11）： 2628-2644.）

[15]?PALANISAMY B， LIU L， LEE K， et al. Anonymizing continuous queries with delay-tolerant mix-zones over road networks [J]. Distributed and Parallel Databases， 2014， 32（1）： 91-118.

[16]?KIM J-S， LI K-J. Location K-anonymity in indoor spaces [J]. GeoInformatica， 2016， 20（3）： 415-451.

[17]?倪巍偉，馬中希，陳蕭.面向路網(wǎng)隱私保護連續(xù)近鄰查詢的安全區(qū)域構建[J].計算機學報，2016，39（3）：628-642. （NI W W， MA Z X， CHEN X. Safe region scheme for privacy-preserving continuous nearest neighbor query on road networks[J]. Chinese Journal of Computers， 2016， 39（3）： 628-642.）

[18]?周長利，田暉，馬春光，等.路網(wǎng)環(huán)境下基于偽隨機置換的LBS隱私保護方法研究[J].通信學報，2017，38（6）：19-29. （ZHOU C L， TIAN H， MA C G， et al. Research on LBS privacy preservation based on pseudorandom permutation in road network[J]. Journal on Communications， 2017， 38（6）： 19-29.）