吳宣夠 王朋飛 鄭 嘯 樊 旭 王小林

(安徽工業(yè)大學計算機科學與技術(shù)學院 安徽馬鞍山 243032)

(wuxgou@ahut.edu.cn)

基于路徑上報的車聯(lián)網(wǎng)軌跡隱私保護

吳宣夠 王朋飛 鄭 嘯 樊 旭 王小林

(安徽工業(yè)大學計算機科學與技術(shù)學院 安徽馬鞍山 243032)

(wuxgou@ahut.edu.cn)

車載自組織網(wǎng)絡(vehicular ad hoc networks, VANETs)(也稱車聯(lián)網(wǎng))數(shù)據(jù)收集與應用為智能交通、城市規(guī)劃、降低車輛污染等問題提供有效的技術(shù)和數(shù)據(jù)保障. 在車聯(lián)網(wǎng)數(shù)據(jù)收集中通常需要車載用戶上報連續(xù)路段位置信息，這給車載用戶個人軌跡隱私帶來嚴重的威脅. 然而現(xiàn)有用戶軌跡保護算法主要基于單點位置保護，不能有效保護基于路徑上報的用戶軌跡隱私.針對車聯(lián)網(wǎng)中用戶移動軌跡易泄露問題，提出一種基于路徑隱私保護的位置信息上報方案. 該方案給出用戶軌跡隱私保護定義和路徑隱私限制下的問題模型，同時證明了該問題是NP-hard問題. 此外，還給出該問題的具體近似算法的實現(xiàn). 仿真實驗結(jié)果表明：提出的算法具有良好的車載用戶隱私保護功能和數(shù)據(jù)收集覆蓋性能.

車聯(lián)網(wǎng)；數(shù)據(jù)收集；軌跡隱私保護；NP-hard問題；任務分配

近年來，隨著汽車數(shù)目的急劇增長，城市交通擁堵、交通事故頻發(fā)、燃油過度消耗造成的環(huán)境污染等問題日趨嚴重，現(xiàn)已成為重要的全球問題[1].車載自組織網(wǎng)絡(vehicular ad hoc networks, VANETs)(也稱車聯(lián)網(wǎng))旨在提供車與車(vehicle to vehicle, V2V)的通信和車與基礎設施(vehicle to infrastruc-ture, V2I)之間的通信，其可用于解決城市交通擁塞、交通事故頻發(fā)、城市規(guī)劃等問題，同時提高人們的出行效率[2-3].車聯(lián)網(wǎng)是由車輛位置、速度、行駛方向及附近環(huán)境狀況等信息構(gòu)成的網(wǎng)絡，是汽車和無線網(wǎng)絡的融合[4]，其系統(tǒng)主要包括車載通信設備(on board unit, OBU)、應用單元(application unit, AU)和道路基本單元(road side unit, RSU)等組成.OBU主要用于與其他車輛中的OBU或者與RSU之間交換信息；AU主要是利用OBU的通信能力來實現(xiàn)通信功能的設備；RSU是沿道路兩側(cè)或?qū)Ｓ霉潭ㄎ恢玫臒o線接入設備[5-6].車聯(lián)網(wǎng)中通過無線接入技術(shù)實現(xiàn)數(shù)據(jù)傳輸和共享等操作[7-8].同時，車聯(lián)網(wǎng)具有避免傳統(tǒng)數(shù)據(jù)收集中需要部署大量無線傳感器節(jié)點等優(yōu)點，從而有效減少人力物力的投入，降低信息收集成本.

盡管車聯(lián)網(wǎng)可以進行各種信息的收集和融合，為控制交通擁擠、城市規(guī)劃和人們的出行帶來方便，但車聯(lián)網(wǎng)的信息收集通常都伴隨用戶的位置信息，而這些位置信息如果得不到合理的保護，其勢必給汽車用戶帶來嚴重的安全威脅.現(xiàn)有研究表明，用戶的移動軌跡具有高度的唯一性，根據(jù)5個時空位置信息能夠成功識別出95%的用戶軌跡[9-10].如攻擊者通過對用戶軌跡的數(shù)據(jù)挖掘分析，能夠推斷出個人的家庭或工作地址、個人愛好等隱私信息[11-12].因此，針對車聯(lián)網(wǎng)用戶進行軌跡隱私保護具有重要的意義，為車聯(lián)網(wǎng)的用戶安全參與提供技術(shù)保證.

目前，針對用戶位置隱私保護方面的研究主要包括基于單點位置保護和多點位置保護[13]，其中比較著名的有K-匿名[14]、空間轉(zhuǎn)換[15]、泛化[16]、加密[17]和假數(shù)據(jù)法[18]等.k-匿名方法主要是將用戶真實路徑用多個位置來代表，在匿名化過程中，每個位置都被泛化為一個區(qū)域，通過對路徑中每個位置實現(xiàn)k-匿名來實現(xiàn)路徑的k-匿名.但是現(xiàn)已有研究表明，該匿名化對于一系列連續(xù)查詢將會泄露用戶的真實路徑[19].文獻[8]將用戶整個路徑與其他k-1個相似路徑進行匿名化，并加入時間混淆技術(shù)降低了攻擊者推斷出用戶路徑的可能性.其主要是通過可信匿名服務器來實現(xiàn)整個路徑的匿名化，但實際上服務器并不是足夠安全可靠，因此仍存在用戶隱私泄露的風險.在文獻[20]中，Kido等人利用用戶軌跡來產(chǎn)生虛假軌跡，從而掩蓋用戶的真實路徑.在文獻[21]中，針對數(shù)據(jù)發(fā)布導致的用戶隱私泄露問題提出了相關解決方案，主要是在數(shù)據(jù)發(fā)布之前對用戶軌跡進行裁剪工作，使其能夠?qū)崿F(xiàn)k-匿名，從而保證了用戶的真實路徑不會被擁有部分路段信息的攻擊者推測出來.在文獻[22-23]中，針對車聯(lián)網(wǎng)中用戶位置隱私泄露提出了相關解決方案，主要是利用混合區(qū)思想，通過在路口變換車輛的假名來應對攻擊者的追蹤.

上述方法雖然能有效保護用戶位置隱私，但并不能直接應用于車聯(lián)網(wǎng)中用戶軌跡隱私保護，其主要原因在于車聯(lián)網(wǎng)中用戶上報的位置信息通常按一段行駛路段為單位，而非孤立的位置點.為了有效解決車聯(lián)網(wǎng)中基于路徑上報的用戶軌跡隱私安全，本文提出一種最大化路徑覆蓋的用戶路徑隱私保護數(shù)據(jù)上報框架，在滿足用戶路徑隱私需求下最大化所有路徑覆蓋.

1 隱私保護定義與問題描述

1.1車載用戶數(shù)據(jù)上報模型

Fig. 1 Data gathering framework of VANET圖1 車聯(lián)網(wǎng)數(shù)據(jù)收集框架

車聯(lián)網(wǎng)主要功能之一就是收集車載與交通相關數(shù)據(jù)，為智能交通、城市規(guī)劃等應用提供數(shù)據(jù)支持.本文假設車聯(lián)網(wǎng)數(shù)據(jù)收集應用框架如圖1所示，主要包括車載網(wǎng)絡、任務分發(fā)與收集服務器和車聯(lián)網(wǎng)應用請求服務器3個部分.車載網(wǎng)絡負責進行車聯(lián)網(wǎng)數(shù)據(jù)采集與上報；任務分配服務器可以是交通管理部門或網(wǎng)絡服務提供商，其負責響應應用服務器的任務請求并將任務分發(fā)下去，同時進行數(shù)據(jù)的響應；應用服務器負責根據(jù)收集到的數(shù)據(jù)進行應用提供.在該框架中，假設任務分配服務器是可信的.由于云端的開放性和應用多樣性特點，導致云端車載數(shù)據(jù)存在泄露風險[24].因此，云端應用服務器認為是不可靠的.

1.2隱私保護定義

由于車聯(lián)網(wǎng)中，車載用戶上報的數(shù)據(jù)通常是以道路上的一段路徑為單位.事實上，可以將汽車的行駛地圖轉(zhuǎn)換為對應的邏輯地圖，如圖2所示.圖2(a)為汽車行駛的地圖，圖2(b)為其對應的邏輯地圖.在汽車行駛地圖轉(zhuǎn)化為邏輯地圖是以交通道路中的路徑為單位，其中路與路的交點為邏輯地圖中的頂點，路的交點之間的路徑為邏輯圖中的邊，則車載用戶行駛的軌跡為邏輯圖中的一條包含頂點和邊的軌跡，而邏輯圖中的邊可以看成是用戶上報位置信息的基本單位.

Fig. 2 Driving map and its logical map圖2 車載行駛地圖與其邏輯地圖

針對邏輯地圖中以邊為單位的位置信息上報，如何實現(xiàn)用戶軌跡隱私安全？一個簡單的方法就是上報邏輯圖上的孤立邊，而非連續(xù)的邊.當然可以采用不同方法來保護車載用戶路徑隱私安全.在本文中，我們僅考慮通過上報不同孤立邊來實現(xiàn)車載用戶的軌跡隱私保護.首先，假設用戶和攻擊者擁有相同的地圖，因為地圖是可以公開獲取的.我們對用戶軌跡隱私保護進行如下定義.

定義1. 給定邏輯地圖G=(V,E), V={v1,v2,…,vt}為地圖中的頂點，E={e1,e2,…,em}為地圖中的邊.假設車載用戶的移動軌跡為行駛軌跡R={e1,e2,…,ek},其上報路徑集合為P(P?R),如果P中所有路徑滿足以下2個條件：

1) P中任意2條路徑之間的連接路徑數(shù)目均大于C或者等于0；

2) P中任意2條路徑之間的連接跳數(shù)小于H.

其中C和H為用戶給定的常數(shù)，則P認為是安全.為了便于表示，用Γ()表示安全需求函數(shù)，則滿足用戶的上報路徑P可表示為：Γ(ei,ej)≥C或Γ(ei,ej)=0,?ei, ej∈P, i≠j.

在定義1中，給定條件2是因為隨著2條路徑之間連接跳數(shù)的增加，其之間的連接線路數(shù)目可能也會不斷增加.而通常情況下，在用戶行駛軌跡上距離較近的2個路徑之間用戶不會繞行太多跳數(shù).2個路徑之間的連接數(shù)目為0表明這2個路段之間的跳數(shù)大于閾值H，這就表明2個上報路徑已經(jīng)足夠遠，攻擊者很難推導出之間的連接線路.不同的用戶可以根據(jù)自己的安全需求進行C和H的設置.

1.3問題描述

由定義1，我們可以給出問題的描述：假設汽車行駛的邏輯圖為G=(V,E)，E={e1,e2,…,em}為G中的路徑，V={v1,v2,…,vt}為G中路徑與路徑的交點.同時，假設有N個車聯(lián)網(wǎng)用戶參與到數(shù)據(jù)收集中來，其數(shù)據(jù)上報按邏輯圖上的邊為單位，每個用戶的行駛軌跡為Ri={ei 1,ei 2,…,ei k}, ?i=1,2,…,N.則在保證用戶路徑隱私需求下的最大化地圖路徑上報覆蓋為其目標函數(shù)，目標函數(shù)表示為

s.t.Γ(ei,ej)≥CorΓ(ei,ej)=0,

?ei,ej∈Pi,i≠j,Pi?Ri,

其中，Pi為第i個用戶上報的徑集合；|·|為給定集合的勢；Γ( )為隱私保護函數(shù)，即上報集合中任意2條邊之間的連接線路數(shù)目.

2 問題分析

根據(jù)1.2節(jié)給出的隱私保護定義和1.3節(jié)給出的問題(P)可知，每個車載用戶可以上傳的安全路徑集合并不唯一，而服務器端需要最大化路徑上報覆蓋率.事實上針對問題(P)，我們可以將其看成2個子問題：子問題(1)為求解車載用戶軌跡上的所有符合用戶安全需求的可上報路徑集合；子問題(2)為從所有參與用戶上報數(shù)據(jù)中選擇最大路徑覆蓋子集.為了便于對問題(P)的分析，下面給出對2個子問題的定義和理論分析.

定義2. 給定車載用戶行駛道路邏輯圖G=(V,E)和一個車載用戶i所行駛路徑軌跡R={ei 1,ei 2,…,ei k}, ei j∈E, j=1,2,…,k.尋找R所有的子集P={ P1,P2,…,Pr}，使其每一個元素Pi均滿足以定義1中給定的H,C下的隱私定義需求.便于表示，我們稱該問題為(H,C,k)-PRSS問題.

定理1. (H,C,k)-PRSS問題為NP-hard問題.

證明. 要證明(H,C,k)-PRSS是一個NP問題，首先證明給定任一解都可在多項式時間內(nèi)驗證該解是否正確.對于給定G=(V,E)，假定集合P?E是該問題的一個解，欲在多項式時間內(nèi)檢驗P是否正確，只需對P中任意2個路段ei, ej在H跳內(nèi)之間的路徑連接數(shù)是否大于C或者等于0.顯然，這可以在多項式時間內(nèi)完成.

Fig. 3 Undirected graph transformation圖3 無向圖轉(zhuǎn)換

證畢.

其中c為常數(shù).為了便于表示，我們稱上述問題為地圖最大覆蓋問題.

定理2. 上述地圖最大覆蓋問題為NP-hard問題.

證畢.

綜合定理1和定理2可知，問題(P)是一個NP-hard問題.

3 基于用戶軌跡隱私保護的位置上報方案

3.1車載用戶路徑上報框架

本文所提出的基于路徑上報的車聯(lián)網(wǎng)數(shù)據(jù)收集系統(tǒng)包括車載設備終端、可信第三方和應用服務器3部分，如圖4所示:

Fig. 4 Blocks diagram of system圖4 系統(tǒng)模塊框圖

車輛終端部分主要包括邏輯地圖生成、路徑隱私評估、數(shù)據(jù)采樣收集以及數(shù)據(jù)信息上報功能.當接收到第三方發(fā)布的任務時，將通過隱私評估模塊進行判斷該路段是否滿足用戶設置的安全需求，滿足時將當前路段信息并上報至可信第三方.

可信第三方對應于系統(tǒng)框架中的任務分配服務器，其主要是最大化數(shù)據(jù)覆蓋概率的同時進一步提高車載用戶軌跡安全.可信第三方在實際情況中可以是具體的交通管理部門或者是車聯(lián)網(wǎng)網(wǎng)絡運營商.由于車聯(lián)網(wǎng)應用的多樣性，交通管理部門或網(wǎng)絡運營商不可能考慮全部具體應用.可信第三方只負責任務的發(fā)布與用戶上傳數(shù)據(jù)過濾，同時滿足用戶和應用服務的要求.用戶將安全上報路段集發(fā)送可信第三方，然后可信第三方選擇根據(jù)定義3中目標函數(shù)將用戶的路段集上報至服務器.

應用服務器根據(jù)其應用需求向可行第三方進行任務請求，并根據(jù)可信第三方返回的數(shù)據(jù)構(gòu)建其具體應用.

3.2算法實現(xiàn)

針對車載用戶軌跡隱私保護問題(P)，我們將子問題(1)和子問題(2)分別在車載端和可信第三方(任務分配服務器)中實現(xiàn)，以達到車載用戶軌跡隱私得以保護的目的.

根據(jù)定理1，在多項式時間內(nèi)無法求解(H,C,k)-PRSS問題，我們采用貪心算法思想進行相應的安全路徑選擇如算法1所示.算法1所表示第i個車載用戶滿足其軌跡隱私需求的安全路徑選擇，G=(V,E)是實際地圖對應的邏輯地圖，H和C為其隱私需求參數(shù)，Pi是用戶安全上報路段集，Γ()是定義1中對應的隱私計算函數(shù)，pcon用來記錄在用戶設定閾值C和H的情況下兩路段之間路徑的連接數(shù)目.

算法1. 車載用戶i的安全上報路徑選擇算法.

輸入：G,H,C,Pi；

① flag=true；

② ev=fun_rand(Pi);

④ Pi=Pi-{ev};

⑤foreacheu∈Pido

⑦ pcon=fun_safes(G,H,C,ev,eu);

⑧ifpcon≥Corpcon=0then

⑩endif

在算法1中，行②為從用戶i的軌跡中隨機選擇一個路徑，行⑦函數(shù)fun_safes()為計算2個路徑之間的符合條件的連接線路數(shù)目.

針對可信第三方，其重要功能是為應用服務器提供最大化的數(shù)據(jù)覆蓋，同時進一步減少用戶上報路徑信息，并提高車載用戶軌跡安全.根據(jù)定理2可知，在車載用戶路徑安全限制下最大化數(shù)據(jù)覆蓋是一個NP-hard問題，故結(jié)合算法1給出如下最大覆蓋算法如算法2所示.

算法2. 最大化路徑覆蓋算法.

輸入：G,P={P1,P2,…,Pm}；

輸出：P*.

① P*=P;

②foreache∈Edo

③ P′=?;

④whileP*=?do

⑤ P=fun_rand(P*);

⑥ P′=P′+P;

⑦ife∈Pthen

⑧break;

⑨endif

⑩endwhile

在算法2中，P為所有用戶安全上報路段集，Pi(1≤i≤m)代表第i個用戶安全上報路段集，P*是可信第三方最終將上報至應用服務器的路段集.行⑤是從用戶上報的路徑集中隨機選擇一個.事實上，算法2是除去車載用戶重復上報的路徑信息，因此P和P*具有相同的路徑覆蓋率.

4 性能評估

4.1實驗數(shù)據(jù)

在本文實驗中，我們利用Matlab作為仿真軟件進行地圖生成， 并隨機選取100個點當作地圖中路的交點，每個頂點所連接的邊為隨機生成1～5條邊.設置每個頂點的度為1～5，因為真實道路上路口所連接的道路經(jīng)常也是1～5條.用戶移動軌跡為邏輯圖中部分連續(xù)的邊，并以邊的數(shù)目來表示其路徑長度.圖5為模擬生成的部分邏輯地圖.

Fig. 5 Simulation logical map圖5 實驗仿真地圖

4.2路徑安全性能評估

在實驗中，我們分別評價單個車載用戶在不同H和C情況下安全用戶上報路徑情況，其中用戶軌跡長度為30(即用戶行駛30條路徑長度的軌跡).如圖6所示，粗體虛線表示用戶移動軌跡，實線為滿足用戶安全需求的上報路段.其中圖6(a)為H=4，C=2時路段上報情況，圖6(b)(c)分別為H=4,C=3和H=5,C=3時路段上報情況.根據(jù)結(jié)果圖能夠發(fā)現(xiàn)圖中所有上報路段之間在設置閾值H之內(nèi)至少有C條路徑，并且單獨上報孤立路段相當于移除了各路段之間的時間序列關系，使得攻擊者更難恢復出用戶的真實軌跡.

Fig. 6 The reported road segments with different privacy requirements圖6 不同安全等級路段上報情況

4.3路徑覆蓋性能評估

Fig. 7 Coverage rate comparison with different H and C. 圖7 不同H和C值下的路徑覆蓋率對比圖

在本節(jié)，我們給出多用戶經(jīng)可信第三方運行算法2后的地圖數(shù)據(jù)覆蓋情況.實驗分別設置不同用戶、不同軌跡長度和不同安全等級下車載用戶上報地圖覆蓋情況，其具體性能如圖7所示.圖7(a)顯示了H=4，C=2時不同用戶數(shù)量、軌跡長度與覆蓋情況的對比圖，圖7(b)和圖7(c)分別為H=5，C=3和H=8,C=5時的覆蓋率對比情況.圖7(a)中顯示路徑長度為20、用戶數(shù)量為100時覆蓋率將近80%，用戶路徑長度為40、用戶數(shù)量為100時覆蓋率達到90%，用戶路徑長度為50、用戶數(shù)量為100時覆蓋率已有95%.同樣，在圖7(b)和(c)中,用戶路徑長度為50、用戶數(shù)量為80時覆蓋率可達90%.隨著用戶數(shù)量的增加，在用戶數(shù)量接近100時覆蓋率亦可達到95%.從圖7中可以看出，本文提出的路徑上報算法具有較高的覆蓋率.

5 結(jié)束語

本文針對基于車聯(lián)網(wǎng)信息收集過程中用戶軌跡隱私易泄露問題，提出了一種基于路徑的用戶數(shù)據(jù)上報方案.其主要是利用孤立路段上報思想來保證用戶軌跡隱私，并給出了相關的隱私保護定義、模型建立、問題分析與證明以及近似算法實現(xiàn).最后，通過仿真實驗展示了本文提出的算法能夠有效地保護用戶軌跡隱私，且不需要大量用戶參與的情況下即可實現(xiàn)有效的數(shù)據(jù)收集覆蓋率.

[1]Zheng K, Zheng Q, Chatzimisios P, et al. Heterogeneous vehicular networking: A survey on architecture, challenges, and solutions[J]. IEEE Communications Surveys amp; Tutorials, 2015, 17(4): 2377-2396

[2]Hartenstein H, Laberteaux K P. A tutorial survey on vehicular ad hoc networks[J]. IEEE Communications Magazine, 2008, 46(6): 164-171

[3]Lu N, Cheng N, Zhang N, et al. Connected vehicles: Solutions and challenges[J]. IEEE Internet of Things Journal, 2014, 1(4): 289-299

[4]Su Jing, Wang Dong, Zhang Feifei. Review of vehicle networking technology application[J]. Internet of Things Technologies, 2014, 4(6): 69-72 (in Chinese)(蘇靜, 王冬, 張菲菲. 車聯(lián)網(wǎng)技術(shù)應用綜述[J]. 物聯(lián)網(wǎng)技術(shù), 2014, 4(6): 69-72)

[5]Al-Sultan S, Al-Doori M M, Al-Bayatti A H, et al. A comprehensive survey on vehicular ad hoc network[J]. Journal of Network amp; Computer Applications, 2014, 37(1): 380-392

[6]Wang Jingxin, Wang Yue, Geng Junwei, et al. Secure and privacy-preserving scheme based on pseudonyms exchanges for VANET[J]. Journal of Tsinghua University (Science and Technology), 2012, 52(5): 592-597 (in Chinese)(王景欣, 王鉞, 耿軍偉, 等. 基于匿名互換的車聯(lián)網(wǎng)安全與隱私保護機制[J]. 清華大學學報: 自然科學版, 2012, 52(5): 592-597)

[7]Du R, Chen C, Yang B, et al. Effective urban traffic monitoring by vehicular sensor networks[J]. IEEE Trans on Vehicular Technology, 2015, 64(1): 273-286

[8]Yang Nan, Kang Rongbao. Security-threat analysis and defense strategy of IoV[J]. Communications Technology, 2015, 48(12): 1421-1426 (in Chinese)(楊南, 康榮保. 車聯(lián)網(wǎng)安全威脅分析及防護思路[J]. 通信技術(shù), 2015, 48(12): 1421-1426)

[9]Zhang Xuejun, Gui Xiaolin, Wu Zhongdong. Privacy preservation for location-based services: A survey[J]. Journal of Software, 2015, 26(9): 2373-2395 (in Chinese)(張學軍, 桂小林, 伍忠東. 位置服務隱私保護研究綜述[J]. 軟件學報, 2015, 26(9): 2373-2395)

[10]Montjoye Y A D, Hidalgo C A, Verleysen M, et al. Unique in the crowd: The privacy bounds of human mobility[J]. Scientific Reports, 2013, 3(6): 1376-1380

[11]Hwang R H, Hsueh Y L, Chung H W. A novel time-obfuscated algorithm for trajectory privacy protection[J]. IEEE Trans on Services Computing, 2014, 7(2): 126-139

[12]Xiao Y, Xiong L. Protecting locations with differential privacy under temporal correlations[C]Proc of the 22nd ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2015: 1298-1309

[13]Chow C Y, Mokbel M F. Trajectory privacy in location-based services and data publication[J]. ACM SIGKDD Explorations Newsletter, 2011, 13(1): 19-29

[14]Xu T, Cai Y. Exploring historical location data for anonymity preservation in location-based services[C]Proc of the 27th Conf on Computer Communications. Piscataway, NJ: IEEE, 2008: 547-555

[15]Ghinita G, Kalnis P, Khoshgozaran A, et al. Private queries in location based services: Anonymizers are not necessary[C]Proc of the 2008 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2008: 121-132

[16]Zhang C, Huang Y. Cloaking locations for anonymous location based services: A hybrid approach[J]. GeoInformatica, 2009, 13(2): 159-182

[17]Du W, Atallah M J. Secure multi-party computation problems and their applications: A review and open problems[C]Proc of the 2001 Workshop on New Security Paradigms. New York: ACM, 2001: 13-22

[18]Yiu M L, Jensen C S, Huang X, et al. Spacetwist: Managing the trade-offs among location privacy, query performance, and query accuracy in mobile services[C]Proc of the 24th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2008: 366-375[

19]Chow C Y, Mokbel M F. Enabling private continuous queries for revealed user locations[C]Proc of the Int Symp on Spatial and Temporal Databases. Berlin: Springer, 2007: 258-275

[20]Kido H, Yanagisawa Y, Satoh T. An anonymous communication technique using dummies for location-based services[C]Proc of the 5th Int Conf on Pervasive Services. Piscataway, NJ: IEEE, 2005: 88-97

[21]Terrovitis M, Mamoulis N. Privacy preservation in the publication of trajectories[C]Proc of the 9th Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2008: 65-72

[22]Freudiger J, Raya M, Félegyházi M, et al. Mix-zones for location privacy in vehicular networks[C]Proc of the 1st ACM Workshop on Wireless Networking for Intelligent Transportation Systems. New York: ACM, 2007 [2017-04-20]. https:www.researchgate.netpublication37450059_Mix-Zones_for_Location_Privacy_in_Vehicular_Networks

[23]Palanisamy B, Liu L. Mobimix: Protecting location privacy with mix-zones over road networks[C]Proc of the 27th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2011: 494-505

[24]Wang Guofeng, Liu Chuanyi, Pan Hezhong, et al. Survey on insider threats to cloud computing[J]. Chinese Journal of Computers, 2017, 40(2): 296-316 (in Chinese)(王國峰, 劉川意, 潘鶴中, 等. 云計算模式內(nèi)部威脅綜述[J]. 計算機學報, 2017, 40(2): 296-316)

[25]Hochbaum D S. Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems[M]. Boston, MA: PWS, 1996: 94-143

WuXuangou, born in 1979. PhD, associate professor. Member of CCF. His main research interests include wireless sensor networks, crowdsourcing and privacy protection.

WangPengfei, born in 1994. Master candidate. His main research interests include security protection and VANETs.

ZhengXiao, born in 1975. PhD, professor. Senior member of CCF. His main research interests include service computing and mobile cloud computing.

FanXu, born in 1985. PhD. His main research interests include network coding and crowdsensing networks.

WangXiaolin, born in 1964. Master. Professor. His main research interests include information processing.

TrajectoryPrivacyProtectionBasedonRoadSegmentReportinVANETs

Wu Xuangou, Wang Pengfei, Zheng Xiao, Fan Xu, and Wang Xiaolin

(School of Computer Science and Technology, Anhui University of Technology, Ma’anshan, Anhui 243032)

Vehicular ad hoc networks (VANETs) provide the related techniques and solutions for intelligent transportation, urban planning, pollution reduction and other issues. VANET applications usually require vehicle users to report continuous road location information, which brings a serious threat to personal trajectory privacy. However, the existing trajectory protection techniques are mainly focused on location-based protection, which cannot be applied to road segment based trajectory privacy protection effectively. In this paper, we propose a new road segment data gathering framework with trajectory privacy protection consideration in VANETs. In our framework, we give the trajectory privacy protection definition, formulate the problem model of road segment based data report, and prove that the problem is a NP-hard problem. In addition, we also present approximated algorithms to solve the problem. The experimental results show that our algorithms have good performance in both user’s trajectory protection and coverage rate of data gathering.

vehicular ad hoc networks (VANETs); data gathering; trajectory privacy protection; NP-hard problem; task assignment

2017-05-31；

2017-08-09

國家自然科學基金項目(61672038,61402009)；安徽省高校優(yōu)秀青年人才支持計劃；安徽省高校自然科學研究重大項目(KJ2014ZD05)；安徽省重點研究與開發(fā)計劃面上科技攻關項目(1704a0902033)

This work was supported by the National Natural Science Foundation of China (61672038, 61402009), the Program for Excellent Young Talents in the Anhui Higher Education Institutions of China, the Major Project of Anhui Provincial Natural Science Research (KJ2014ZD05), and the Key Research and Development Plan of Anhui Province (1704a0902033).

TP393