位置隱私保護(hù)的虛擬軌跡填充算法

付宇 王紅

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

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

中圖分類號(hào)：?TP309.2

文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

1 問(wèn)題描述

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

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

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

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

2 虛擬軌跡填充算法

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

2.1 離線預(yù)處理階段

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

2.2 匯聚點(diǎn)提取階段

在圖2中，用戶user首先發(fā)出的一個(gè)POIA興趣點(diǎn)服務(wù)請(qǐng)求給隱私保護(hù)服務(wù)器LPPS。

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

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

（2）初步預(yù)測(cè)軌跡并對(duì)之分段，對(duì)原始ID和POI進(jìn)行混淆保護(hù);

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

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

（5）進(jìn)行分區(qū)綁定，確定路徑關(guān)鍵匯聚點(diǎn)list_of_candidate_point;

（6）根據(jù)起始時(shí)間、運(yùn)動(dòng)速度，對(duì)user關(guān)鍵匯聚點(diǎn)預(yù)置時(shí)序（算法1）;

（7）將主軌跡的起點(diǎn)、關(guān)鍵匯聚點(diǎn)序列、興趣點(diǎn)填入new_query_list;

（8）進(jìn)行主軌跡填充，將匯聚點(diǎn)按時(shí)序放入待混淆列表mix_list;

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

（10）對(duì)填充中產(chǎn)生的匯聚點(diǎn)預(yù)置時(shí)序;

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

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

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

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

（15）為所有請(qǐng)求計(jì)算并返回〈LOC_F_user，POIX〉.route;

（16）恢復(fù)用戶user真實(shí)請(qǐng)求的POI與路徑;

（17）將恢復(fù)后的結(jié)果返回給終端用戶。

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

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

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

算法1? route_timing。

程序前

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

//用戶id，關(guān)鍵匯聚點(diǎn)列表，基準(zhǔn)節(jié)點(diǎn)，基準(zhǔn)時(shí)間

輸出?? route_list[ ] with timing slot filled

//填充了時(shí)序域的關(guān)鍵匯聚點(diǎn)列表

BEGIN：

步驟1

1）

route ← route_list.get_route（user_id）;

//從關(guān)鍵匯聚點(diǎn)列表中得到當(dāng)前用戶的路徑

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

//得到當(dāng)前基準(zhǔn)點(diǎn)的前序路徑

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

//得到當(dāng)前基準(zhǔn)點(diǎn)的后繼路徑

步驟2

2）

cur_node ← base_node;

//得到基準(zhǔn)節(jié)點(diǎn)

while（pre_node ← get_next_pre（cur_node））

{?? //基于基準(zhǔn)時(shí)間，對(duì)前序路徑填充時(shí)序

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

cur_node ← pre_node;

//將前一個(gè)節(jié)點(diǎn)作為當(dāng)前待填充節(jié)點(diǎn)

}

步驟3

3）

cur_node ← base_node;

//回到基準(zhǔn)節(jié)點(diǎn)，開(kāi)始填充后繼節(jié)點(diǎn)的時(shí)序

while（post_node ← get_next_post（cur_node））

{?? //基于基準(zhǔn)時(shí)間，對(duì)后繼路徑填充時(shí)序

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

cur_node ← post_node;

}

END

程序后

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

2.3 虛擬軌跡填充階段

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

算法2? trace_mixing。

程序前

輸入?? route[base_user.id]

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

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

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

//針對(duì)每個(gè)匯聚點(diǎn)的填充軌跡

BEGIN：

步驟1??? ?1）

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

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

b）隨機(jī)選擇一個(gè)與待混淆興趣點(diǎn)區(qū)域不同的相鄰周邊區(qū)域作為虛擬軌跡X的目的區(qū)域（AREA_ ENDX），選取其區(qū)域內(nèi)一匯聚點(diǎn)作為虛擬軌跡X的后繼節(jié)點(diǎn);此時(shí)虛擬路徑不通過(guò)中央?yún)^(qū)域，且當(dāng)前匯聚點(diǎn)CURRENT_ RENDEZVA所在區(qū)域?yàn)槁窂絏的起始區(qū)，需在該區(qū)生成一個(gè)虛擬起始點(diǎn)START_ NODEX（對(duì)應(yīng)算法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）對(duì)應(yīng)算法2步驟2.3）與圖5，選擇另一中央?yún)^(qū)域內(nèi)匯聚點(diǎn)（如圖5中分區(qū)C1的節(jié)點(diǎn)n5）為虛擬軌跡X的前序節(jié)點(diǎn)，此時(shí)虛擬軌跡X通過(guò)中央?yún)^(qū)域（圖5分區(qū)C1），且當(dāng)前匯聚點(diǎn)CURRENT_ RENDEZVA所在區(qū)域（圖5分區(qū)SE）為虛擬軌跡X的目的區(qū)（AREA_ENDX），其虛擬興趣點(diǎn)POIX在CURRENT_ RENDEZVA所在區(qū)域選擇（圖5中的n8）。

d）選擇另一中央?yún)^(qū)域（如圖3中的分區(qū)1）內(nèi)匯聚點(diǎn)為虛擬軌跡X的后繼節(jié)點(diǎn)，此時(shí)虛擬軌跡通過(guò)中央?yún)^(qū)域，且當(dāng)前匯聚點(diǎn)（CURRENT_RENDEZVA）所在區(qū)域?yàn)樘摂M軌跡X的起始區(qū)（AREA_ STARTX），需在該區(qū)生成一個(gè)虛擬起始點(diǎn)START _NODEX（對(duì)應(yīng)算法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）當(dāng)CURRENT_RENDEZVA屬于中央?yún)^(qū)域時(shí)（如圖6分區(qū)C2）：

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

b）在與起始區(qū)對(duì)應(yīng)（相對(duì)于中央?yún)^(qū)域）的另一個(gè)半?yún)^(qū)隨機(jī)選擇一個(gè)周邊區(qū)域（如圖6中分區(qū)W）作為虛擬軌跡目的區(qū)（AREA_ENDX），并在該區(qū)域內(nèi)隨機(jī)選擇虛擬軌跡興趣點(diǎn)POIX（如圖6中節(jié)點(diǎn)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）步對(duì)交匯軌跡數(shù)較少的匯聚點(diǎn)進(jìn)行補(bǔ)充填充，稱為均衡填充。該過(guò)程與主軌跡填充算法相似，但只針對(duì)出入度較少的匯聚點(diǎn)。填充的過(guò)程中所產(chǎn)生新的軌跡匯聚點(diǎn)是否繼續(xù)放入mix_list列表取決于填充的終止條件。若需要終止，則新產(chǎn)生的匯聚點(diǎn)不加入mix_list中，該列表中的節(jié)點(diǎn)取空后填充過(guò)程將終止。判斷是否終止填充的依據(jù)可以是一個(gè)給定的總填充軌跡數(shù)量上限，也可以根據(jù)填充所達(dá)到的隱私保護(hù)度。除了mix_list列表，新產(chǎn)生虛擬軌跡的中間匯聚點(diǎn)和虛擬興趣點(diǎn)也會(huì)在圖2的第（12）步中加入到new_query_list列表，并最終會(huì)被發(fā)往LBS服務(wù)提供端。

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

算法3? id_mixing。

程序前

步驟?? current_rendez， route_list[ ]， time_margin

//當(dāng)前匯集點(diǎn)，路由列表，時(shí)間窗

步驟?? 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)過(guò)當(dāng)前節(jié)點(diǎn)的所有路徑

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

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

步驟2.1

2.1）

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

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

//軌跡，分別得到此軌跡的用戶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結(jié)構(gòu)里的用戶X和A）與興趣點(diǎn)請(qǐng)求之間的對(duì)應(yīng)關(guān)系將會(huì)被修改，從而通過(guò)①軌跡分段和②ID混淆，實(shí)現(xiàn)了對(duì)原始用戶信息和POI請(qǐng)求信息對(duì)應(yīng)關(guān)系的隱藏。在圖2的第（14）步至（15）步，這些錯(cuò)亂的信息通過(guò)new_query_list被傳遞給了LBS服務(wù)提供者;后者不能分辨哪些是真實(shí)用戶，哪些是虛擬用戶，所有請(qǐng)求都被視為正常請(qǐng)求并返回這些請(qǐng)求的興趣點(diǎn)位置和路由。

在圖2的第（16）步，LPPS從收到的LBS服務(wù)端回復(fù)中，過(guò)濾出真實(shí)用戶的興趣點(diǎn)坐標(biāo)和路徑，并將這些結(jié)果在第（17）步返回給終端用戶。而對(duì)終端用戶而言，就如同直接從LBS服務(wù)者拿到請(qǐng)求結(jié)果一樣。隱私保護(hù)服務(wù)器LPPS所做的虛擬軌跡注入等保護(hù)措施對(duì)終端用戶而言是透明的。

3 隱私保護(hù)度

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

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

（1）

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

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

TD= 1 Tn+k

（2）

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

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

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，軌跡隱私披露風(fēng)險(xiǎn)TD的值為1/（8+0）=0.125，遠(yuǎn)小于沒(méi)有經(jīng)過(guò)任何位置隱私保護(hù)處理時(shí)的值1/3。

4 算法性能評(píng)估

1）計(jì)算復(fù)雜度。

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

2）可擴(kuò)展性與隱私保護(hù)度。

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

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

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

3）通信開(kāi)銷與負(fù)荷。

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

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

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

5 結(jié)語(yǔ)

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

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

參考文獻(xiàn)

[1]?劉成.LBS定位技術(shù)研究與發(fā)展現(xiàn)狀[J].導(dǎo)航定位學(xué)報(bào)，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]?趙軍，車紅巖.基于位置服務(wù)的應(yīng)用技術(shù)和發(fā)展趨勢(shì)[J].測(cè)繪科學(xué)，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]?張學(xué)軍，桂小林，伍忠東.位置服務(wù)隱私保護(hù)研究綜述[J].軟件學(xué)報(bào)，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]?許明艷，趙華，季新生.位置服務(wù)隱私保護(hù)技術(shù)研究綜述[J].信息工程大學(xué)學(xué)報(bào)，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]?萬(wàn)盛，李鳳華，牛犇，等.位置隱私保護(hù)技術(shù)研究進(jìn)展[J].通信學(xué)報(bào)，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]?熊婉竹，李曉宇.基于匿名路由的移動(dòng)位置隱私保護(hù)[J].計(jì)算機(jī)科學(xué)，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]?孫丹丹，羅永龍，范國(guó)婷，等.基于軌跡形狀多樣性的隱私保護(hù)算法[J].計(jì)算機(jī)應(yīng)用，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ǐn)_動(dòng)的均衡增量近鄰查詢位置隱私保護(hù)方法[J].小型微型計(jì)算機(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]?周長(zhǎng)利，馬春光，楊松濤.路網(wǎng)環(huán)境下保護(hù)LBS位置隱私的連續(xù)KNN查詢方法[J].計(jì)算機(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)隱私保護(hù)連續(xù)近鄰查詢的安全區(qū)域構(gòu)建[J].計(jì)算機(jī)學(xué)報(bào)，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]?周長(zhǎng)利，田暉，馬春光，等.路網(wǎng)環(huán)境下基于偽隨機(jī)置換的LBS隱私保護(hù)方法研究[J].通信學(xué)報(bào)，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.）