解杉杉,劉海龍,趙國生

(哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院,哈爾濱 150025)

0 引 言

伴隨科技的迭代更新,萬物互聯(lián)已經(jīng)成為時(shí)代發(fā)展趨勢,由車輛、行人以及周圍環(huán)境構(gòu)建的車聯(lián)網(wǎng),極大的推動(dòng)了未來智慧城市的建設(shè).在車聯(lián)網(wǎng)中,用戶獲取基于位置服務(wù)(Location Based Service,LBS)時(shí),需要提供真實(shí)的位置信息.用戶的請求內(nèi)容中包含大量敏感信息,隱私數(shù)據(jù)在多方不可信設(shè)備之間的來回傳輸,為不法分子的惡意攻擊提供了條件,對(duì)用戶安全問題構(gòu)成極大的威脅.因此解決車聯(lián)網(wǎng)中車輛軌跡隱私問題,對(duì)車聯(lián)網(wǎng)的發(fā)展和推廣具有積極意義[1].

針對(duì)車聯(lián)網(wǎng)中存在的軌跡隱私問題,眾多學(xué)者提出了不同的解決思路.Jia等人[2]從用戶社交的角度出發(fā),基于用戶屬性、用戶行為和用戶關(guān)系將車聯(lián)網(wǎng)中主流的軌跡隱私保護(hù)方法劃分為4類:泛化思想是將敏感信息模糊化,其中代表方法是K-匿名,Zhang等人[3]提出了一種雙K機(jī)制,通過將K個(gè)位置的查詢信息發(fā)送到K不同的匿名區(qū)保護(hù)用戶在進(jìn)行連續(xù)位置查詢時(shí)的軌跡隱私;混合區(qū)思想是將十字路口、停車場和商場等熱門區(qū)域建組,用戶在組內(nèi)交換假名,切斷軌跡之間的時(shí)空相關(guān)性,避免持續(xù)暴露自己的位置信息[4].Palanisamy等人[5]針對(duì)時(shí)空條件和位置屬性對(duì)混合區(qū)構(gòu)建進(jìn)行優(yōu)化,提出基于路網(wǎng)的混合區(qū)構(gòu)建方法;抑制的思想是采用間斷性的服務(wù)請求策略,通過在敏感地區(qū)選擇不發(fā)送信息,來避免隱私泄露.Li等人[6]提出了一種兩階段隱私保護(hù)抑制算法,通過控制車輛在行駛過程中抑制部分?jǐn)?shù)據(jù)的傳輸,來減少連續(xù)位置之間的時(shí)空相關(guān)性;位置擾動(dòng)的思想是發(fā)布擾亂或加噪的虛假位置代替真實(shí)位置,該類型方法的研究核心在于虛假位置的生成方式.Dai等人[7]參照路網(wǎng)環(huán)境將軌跡分段,針對(duì)不同時(shí)間段生成虛假軌跡,并按照時(shí)間順序進(jìn)行連接,以降低整條軌跡面臨的隱私暴露風(fēng)險(xiǎn).

差分隱私[8,9]的提出,為軌跡隱私保護(hù)提供了新思路,符合差分隱私的位置擾動(dòng)算法逐漸成為軌跡隱私保護(hù)的研究熱點(diǎn)[10].差分隱私的主要思想是在原始查詢結(jié)果中添加隨機(jī)噪聲,使輸出內(nèi)容不會(huì)因數(shù)據(jù)的某些修改而發(fā)生變化,防止攻擊者通過多次查詢推理或者利用背景知識(shí)進(jìn)行暴力破解.按照添加噪聲時(shí)間不同,可以將差分隱私分為中心化和本地化兩類[11]:中心化差分隱私是先將用戶數(shù)據(jù)收集到受信任的服務(wù)器中,然后再進(jìn)行加噪處理;本地化差分隱私是在數(shù)據(jù)上添加噪聲后再將其收集到數(shù)據(jù)中心.由于中心化差分隱私對(duì)可信單位要求高不具普適性,因此利用不可信的邊緣節(jié)點(diǎn)探索本地化差分隱私成為當(dāng)下研究熱點(diǎn)[12].

基于本地化的差分隱私在軌跡隱私保護(hù)上可以分為2個(gè)方向:歷史數(shù)據(jù)發(fā)布和實(shí)時(shí)位置發(fā)布,在車聯(lián)網(wǎng)中道路狀況多變,實(shí)時(shí)位置發(fā)布極具研究價(jià)值[13].Andrés等人[14]提出了地理不可區(qū)分性,不僅保護(hù)了用戶所在位置的隱私安全,還保障了服務(wù)質(zhì)量,Bordenabe等人[15]在此基礎(chǔ)上從線性角度進(jìn)行優(yōu)化,提出了δ-spanner模型.Xiao等人[16]通過馬爾科夫鏈表示位置的分布信息并結(jié)合相鄰數(shù)據(jù)集概念,提出隱私保護(hù)方法(Planar Isotropic Mechanism,PIM).Cui等人[17]提出一種基于實(shí)時(shí)位置數(shù)據(jù)的隱私保護(hù)方案,通過獲取周圍車輛的行駛狀態(tài)為用戶動(dòng)態(tài)生成虛假位置.

軌跡數(shù)據(jù)具有時(shí)空相關(guān)性,不僅包含時(shí)序信息,也包含位置信息.Huo等人[18]認(rèn)為相較軌跡中經(jīng)過的地點(diǎn),用戶的訪問位置更需要保護(hù).通過保護(hù)軌跡上的停留點(diǎn)可以降低整條軌跡的暴露概率,減少保護(hù)過程中的信息損失.為了滿足位置語義安全,Wang等人[19]利用語義位置和攻擊歷史,提出了一種基于強(qiáng)化學(xué)習(xí)的差分隱私機(jī)制.Chen等人[20]針對(duì)車聯(lián)網(wǎng)中連續(xù)時(shí)間戳泄露隱私問題,提出了一種模糊處理機(jī)制,保護(hù)車輛不會(huì)暴露精確位置.上述方法中并未考慮數(shù)據(jù)的可用性,車聯(lián)網(wǎng)中的差分隱私保護(hù)方法仍存在以下問題:

1)隱私預(yù)算分配問題.在隱私保護(hù)上,服務(wù)質(zhì)量和保護(hù)強(qiáng)度之間一直存在矛盾.車聯(lián)網(wǎng)中車輛處于動(dòng)態(tài)運(yùn)動(dòng)中,不合理的隱私預(yù)算分配,會(huì)導(dǎo)致服務(wù)質(zhì)量和保護(hù)需求失衡,從而降低可用性,最終難以實(shí)現(xiàn)隱私保護(hù).現(xiàn)有軌跡隱私保護(hù)方法沒有考慮不同位置對(duì)隱私保護(hù)需求不同,需要針對(duì)不同敏感位置分配不同的隱私預(yù)算.

2)數(shù)據(jù)可用性低.受位置語義和地理拓?fù)溆绊?在車聯(lián)網(wǎng)中即使單個(gè)位置滿足隱私安全,基于連續(xù)位置生成的虛假軌跡也會(huì)遭受背景信息攻擊.假設(shè)攻擊者獲取到用戶請求內(nèi)容是住宅到醫(yī)院的行駛路線,在發(fā)布的虛假軌跡中,終點(diǎn)經(jīng)加噪后變?yōu)獒t(yī)院附近的超市,與用戶的實(shí)際需求沖突.攻擊者根據(jù)請求內(nèi)容排除不滿足用戶行為模式的虛假軌跡,提高暴力破解概率,使保護(hù)方法的數(shù)據(jù)可用性急劇下降.

針對(duì)以上兩種問題,本文提出了基于位置語義的差分隱私(Differential Privacy Based on Semantic Location,DPSL)軌跡保護(hù)方法,根據(jù)語義位置和用戶喜好設(shè)置相應(yīng)的隱私保護(hù)等級(jí),滿足不同用戶的定制化需求;在保障隱私保護(hù)程度的前提下,以用戶的行為模式和軌跡曲線相似度為標(biāo)準(zhǔn),對(duì)待發(fā)布的位置進(jìn)行篩選,提高虛假軌跡的可用性.

1 預(yù)備知識(shí)

本文中常用符號(hào)如表1所示.

表1 常用符號(hào)Table 1 Common symbols

1.1 攻擊模型

車聯(lián)網(wǎng)又稱車輛自組織網(wǎng)絡(luò)(Vehicular Ad-hoc Network,VANET)通過車輛與路側(cè)單元(Road Side Unit,RSU)、車輛、行人不同單位之間的通訊功能,為用戶提供導(dǎo)航、事故預(yù)警、安全駕駛、尋找行車路線等基于位置服務(wù)[1].在車聯(lián)網(wǎng)中,車輛為了獲取實(shí)時(shí)位置服務(wù)需將其真實(shí)數(shù)據(jù)發(fā)送給RSU再由其將數(shù)據(jù)轉(zhuǎn)發(fā)給LBS,數(shù)據(jù)包括用戶的請求內(nèi)容以及當(dāng)前所在地等.在本文研究背景中,認(rèn)定以上所有服務(wù)器都是不可信單位,結(jié)合圖1信息,對(duì)攻擊者模型做出假設(shè):攻擊者使用設(shè)備算力強(qiáng),可利用背景知識(shí)暴力破解;服務(wù)器不可信,攻擊者可以獲取用戶模糊的發(fā)布位置信息和請求內(nèi)容.

圖1 攻擊者模型Fig.1 Attacker model

1.2 位置語義信息

在地圖上包含著不同的功能區(qū)域,按照應(yīng)用場景可以劃分成不同的語義區(qū),車輛軌跡通常就是由一個(gè)語義區(qū)前往另一個(gè)語義區(qū).語義區(qū)的隱私敏感度往往受兩種因素影響,分別是位置語義和興趣點(diǎn)(Point of Interest,POI).其中位置語義是指位置本身包含的隱私信息,如超市附近可能泄漏的是購物習(xí)慣,在醫(yī)院則是關(guān)于健康問題,明顯后者更為敏感;POI則是根據(jù)用戶的訪問頻率確定,攻擊者可以通過收集用戶歷史軌跡,推斷出用戶的出行習(xí)慣獲取隱私信息.因此,不同語義區(qū)對(duì)隱私保護(hù)的需求程度也會(huì)不同,本文采用Voronoi圖對(duì)地圖上的語義區(qū)進(jìn)行劃分.

定義1.位置語義地圖.Voronoi圖是由一組連續(xù)多邊形組成,假設(shè)X表示任意一個(gè)多邊形,x是從X中的隨機(jī)選取的一點(diǎn),U={u1,u2,…,uη}是平面上η個(gè)點(diǎn)的集合,則在Voronoi圖區(qū)域中任意一點(diǎn),都滿足?ua,ub∈U,x∈X存在d(x,ua)

圖2 位置語義地圖Fig.2 Map with location semantics

定義2.語義流行度.通過計(jì)算歷史軌跡中位置的重復(fù)次數(shù),來統(tǒng)計(jì)車輛行駛過程中對(duì)不同位置語義的訪問概率.

(1)

公式(1)中qi表示位置i的語義流行度,φ×γ是歷史軌跡中的位置總數(shù),ni是位置i的訪問次數(shù).由于在軌跡數(shù)據(jù)中交叉路口出現(xiàn)頻繁,為了降低影響,此類型位置的語義流行度不計(jì)入統(tǒng)計(jì)范疇.

定義3.用戶行為模式.在車聯(lián)網(wǎng)中,根據(jù)用戶的服務(wù)請求可以分析出車輛的前進(jìn)方向,再結(jié)合位置語義和地理拓?fù)浔憧蓪?duì)用戶前進(jìn)方向進(jìn)一步精確,這種帶有目的性的模糊路線,本文將其描述為用戶的行為模式.如圖2中的軌跡E所表示的用戶行為模式可以描述為:從住宅到公司途中經(jīng)過商場.符合用戶行為模式的虛假軌跡,可以防止攻擊者利用背景信息攻擊,保障敏感位置的語義安全性.

1.3 信息熵

信息熵通常用來表示系統(tǒng)的穩(wěn)定程度,當(dāng)系統(tǒng)越趨于穩(wěn)定時(shí)熵值變小,相反系統(tǒng)混亂時(shí)熵值隨之變大.熵的值可由公式(2)計(jì)算得出,其中p(xi)是事件發(fā)生的概率.在p(xi)取0.5時(shí)熵值最大,p(xi)的值越接近0或1時(shí)熵值越小.

(2)

1.4 差分隱私

當(dāng)數(shù)據(jù)集D和D′中有且只有一個(gè)數(shù)據(jù)不同時(shí),可將其稱為相鄰數(shù)據(jù)集[8,9].當(dāng)隨機(jī)算法A在相鄰數(shù)據(jù)集D和D′上滿足公式(3)時(shí),表示算法A符合ε差分隱私保護(hù).

Pr[A(D)=β]≤Pr[A(D′)=β]eε

(3)

當(dāng)eε=1時(shí),算法A在式中的輸出概率一致,表示該算法對(duì)相鄰數(shù)據(jù)集沒有隱私威脅.其中ε是差分隱私預(yù)算,表示隱私保護(hù)程度.ε越小,隱私保護(hù)效果越好,隱私數(shù)據(jù)越安全,相反ε值越大,表示隱私保護(hù)效果越差.

定義4.軌跡差分隱私.差分隱私的相鄰數(shù)據(jù)集都是相對(duì)于傳統(tǒng)數(shù)據(jù)庫而言,然而軌跡上每個(gè)位置都會(huì)涉及到隱私安全.因此原有的差分隱私模型并無法直接應(yīng)用到軌跡隱私保護(hù)中[16].當(dāng)t時(shí)刻真實(shí)位置為zt,發(fā)布的虛假位置為ot時(shí),zt的先驗(yàn)概率可表示為Pr(zt),由ot反推測出zt的后驗(yàn)概率可表示為Pr(zt|ot).將貝葉斯模型與差分隱私模型結(jié)合后,如果后驗(yàn)概率與先驗(yàn)概率的比值滿足公式(4),則表示其滿足軌跡差分隱私定義,其中εt表示zt的隱私預(yù)算[21].

(4)

1.5 虛假軌跡可用性

在虛假軌跡發(fā)布過程中可能存在誤差,若虛假軌跡中出現(xiàn)語義不合理位置,則會(huì)影響生成軌跡的可用性[22].本文通過對(duì)比軌跡之間的曲線相似度,對(duì)虛假軌跡進(jìn)行篩選.

定義5.軌跡曲線相似度.假設(shè)發(fā)布的虛假位置集合和真實(shí)位置集合分別是O和Z,本文采用Hausdorff距離來衡量位置集合O和Z之間的相似度.根據(jù)公式(5)可求出兩組集合之間的距離,HD(O,Z)的值越大表示曲線相似度越低.

HD(O,Z)=max(hd(O,Z),hd(Z,O))

(5)

其中:

hd(O,Z)=maxot∈ominzt∈z‖ot-zt‖

hd(Z,O)=maxzt∈zminot∈o‖zt-ot‖

定義6.軌跡誤差.虛假軌跡與真實(shí)軌跡之間的誤差距離是評(píng)判虛假軌跡可用性的依據(jù).長度為w的真實(shí)軌跡和虛假軌跡之間的誤差平均值MTD可由公式(6)計(jì)算得出:

(6)

其中dis(zt,ot)=‖zt,ot‖2是t時(shí)刻虛假位置ot和真實(shí)位置zt之間的距離.Hausdorff距離值越大時(shí)虛假軌跡與真實(shí)軌跡相似性越低,相反值越小時(shí)相似性越高.當(dāng)軌跡相似性越高、軌跡誤差越小時(shí)虛假軌跡的可用性越強(qiáng).

2 DPSL軌跡隱私保護(hù)算法

DPSL算法主要應(yīng)用場景是解決車輛存在的軌跡隱私安全問題,防止攻擊者發(fā)動(dòng)針對(duì)性的背景信息攻擊,對(duì)用戶的隱私安全構(gòu)成威脅.算法的主要思路是在滿足隱私安全的基礎(chǔ)上,選擇符合用戶的行為模式且與真實(shí)軌跡曲線相似度高的位置集合進(jìn)行發(fā)布,從而增強(qiáng)虛假軌跡的可用性.

2.1 隱私等級(jí)計(jì)算

車聯(lián)網(wǎng)中由于地理位置屬性不同,其對(duì)應(yīng)的敏感程度也會(huì)不一樣,合理的隱私預(yù)算分配方案需要同時(shí)兼顧保護(hù)效果和服務(wù)質(zhì)量.根據(jù)以上需求,提出一種基于位置語義的隱私等級(jí)實(shí)時(shí)計(jì)算方法,使用信息熵值來評(píng)判隱私等級(jí).

根據(jù)熵值的分布規(guī)律可知,當(dāng)事件概率越接近0.5時(shí)熵值越大,過高或過低的概率都會(huì)使得熵值變低.因此,根據(jù)歷史軌跡得出的語義流行度qi不具普適性,如果低頻訪問位置恰好是敏感位置,為其分配過低的隱私等級(jí)并不合理.針對(duì)不同用戶隱私需求,在qi基礎(chǔ)上加入語義相關(guān)度si來調(diào)控敏感位置的熵值,則位置i處的隱私等級(jí)可描述為公式(7):

(7)

在計(jì)算位置的隱私等級(jí)時(shí),語義相關(guān)度的默認(rèn)值設(shè)為1,用戶可根據(jù)自己需求設(shè)置不同位置的語義相關(guān)度.

算法1.隱私等級(jí)計(jì)算

輸入:歷史軌跡集合W,位置語義相關(guān)度集合S

輸出:隱私位置集合SP,隱私等級(jí)集合PL

1.initializeSP,PL;

2.whilei∈W:

3.q[i]= get_Location Frequency(i);//公式(1)得出

4. ifS[i]= 1:

5.p[i]=q[i];

6. else:

7.p[i]=q[i]*S[i]

8. end if;

9.PL[i]=H(p[i]);//由公式(7)得出

10. ifPL[i]>0:

11.SP[i]=W[i];

12.i++;

13.returnSP,PL.

2.2 虛假軌跡發(fā)布

計(jì)算得出的隱私等級(jí)并無法直接使用,只能用作分配隱私預(yù)算的參考依據(jù).完整的虛假軌跡發(fā)布流程為:生成虛假位置、建立隱私模型、軌跡可用性優(yōu)化以及發(fā)布虛假軌跡.

2.2.1 生成虛假位置

在車聯(lián)網(wǎng)中,用戶能使用專用短程通信技術(shù)(Dedicated Short Range Communications,DSRC)獲取周邊車輛運(yùn)行信息,內(nèi)容包括目標(biāo)車輛的方向、速度以及經(jīng)度和緯度.為了抵抗隱私攻擊,收集的位置可以作為虛假位置來獲取基于位置服務(wù).用戶同時(shí)向LBS發(fā)送多條請求服務(wù),在收到所有的響應(yīng)消息后,丟棄無用信息選擇真實(shí)位置對(duì)應(yīng)響應(yīng)內(nèi)容.

用戶發(fā)布請求信息可表示為REQ={req1(ID,Mes,Loc1),req2(ID,Mes,Loc2),…,reqnum(ID,Mes,Locnum)},這些請求信息中除位置外其他內(nèi)容均保持一致,num為發(fā)送請求信息的數(shù)量,ID表示請求編號(hào),Mes表示信息內(nèi)容,Loc表示位置.LBS收到服務(wù)請求后會(huì)在Tr時(shí)間段內(nèi)進(jìn)行響應(yīng),通常是1～3s[17],REQ中的位置信息可以用來構(gòu)建虛假位置集合,即RL={rl1,rl2,…,rlm},其中rl和m分別對(duì)應(yīng)的是REQ集合中的Loc和num.為了防止背景信息攻擊,在目標(biāo)車輛的選擇上要符合用戶的行為模式,保障用戶和目標(biāo)所在語義區(qū)相同.考慮到GPS和DSRC系統(tǒng)存在的定位誤差,因此用戶與目標(biāo)車輛之間的距離需滿足一定偏差量.本文通過公式(8)選擇虛假位置,其中Vi表示目標(biāo)車輛運(yùn)行速度,locu表示用戶當(dāng)前所在地,dis(locu,loci)表示用戶與目標(biāo)車輛i之間的距離.本文將距離偏差量Dgap值設(shè)定為10～15米.

Dgap=dis(locu,loci)-ViTr,i∈[1,num]

(8)

2.2.2 差分隱私模型

通過算法1成功獲取各個(gè)位置的隱私等級(jí)后,為滿足不同用戶的隱私需求,本文結(jié)合本地化差分隱私建立δ-隱私模型[21].由于車輛的位置實(shí)時(shí)更新,在計(jì)算車輛隱私預(yù)算時(shí),對(duì)時(shí)間要求嚴(yán)格,因此模型設(shè)計(jì)不能過于復(fù)雜.

定義7.δ-隱私模型.當(dāng)一個(gè)發(fā)布位置對(duì)應(yīng)的差分隱私預(yù)算ε與隱私等級(jí)pl滿足公式(9)時(shí),表示其滿足δ-隱私模型.給定δ值時(shí),隱私等級(jí)pl越高,為其分配的隱私預(yù)算ε越低,對(duì)應(yīng)的隱私保護(hù)程度越高,相反則保護(hù)程度越低.

(9)

2.2.3 選擇虛假位置

由定義4可知,通過先驗(yàn)概率和后驗(yàn)概率便能夠計(jì)算出隱私預(yù)算,其中先驗(yàn)概率和后驗(yàn)概率可以使用馬爾可夫鏈[21]獲取.求出各個(gè)擾動(dòng)位置的隱私預(yù)算并與δ-隱私模型中隱私預(yù)算進(jìn)行對(duì)比,便能篩選出符合隱私需求的發(fā)布位置.本文通過馬爾可夫鏈模擬車輛位置之間的關(guān)系,首先通過歷史軌跡求出一個(gè)二維狀態(tài)轉(zhuǎn)移矩陣M,然后使用mij表示在車輛行駛過程中從i區(qū)域到j(luò)區(qū)域的轉(zhuǎn)移概率.

(10)

2.2.4 提高虛假軌跡可用性

通過2.2.2節(jié)得到發(fā)布位置對(duì)應(yīng)的先驗(yàn)概率與后驗(yàn)概率后,可以使用公式(4)求出隱私預(yù)算.將其與預(yù)先設(shè)定的隱私預(yù)算(由δ-隱私模型和隱私等級(jí)計(jì)算得出)進(jìn)行對(duì)比,便可在RL中篩選出符合差分隱私機(jī)制的待發(fā)布位置集合DPRL.為了提高虛假軌跡的可用性,還需要對(duì)發(fā)布位置進(jìn)行再次優(yōu)化.主要思路是將相同語義區(qū)的位置進(jìn)行聚類操作,使生成的虛假軌跡符合用戶的行為模式,并對(duì)比軌跡曲線相似度,以高相似度為標(biāo)準(zhǔn)選擇出最佳的發(fā)布位置.

本文使用無監(jiān)督聚類算法K-means,選擇出滿足語義安全的虛假位置[23].K-means算法是將樣本按一定規(guī)律分為K組,在樣本劃分過程中,首先根據(jù)預(yù)設(shè)定的簇心數(shù)量分布簇心,通過比較未分配樣本與不同簇心的歐氏距離,將樣本分入距離較近的簇中,然后更新簇心繼續(xù)對(duì)下一個(gè)樣本數(shù)據(jù)進(jìn)行分類.整個(gè)樣本劃分過程,不斷重復(fù)操作,直到樣本數(shù)據(jù)劃分完畢.在K-means聚類算法中,K的取值是需要提前給定,本文中K的值取決于真實(shí)軌跡中所包含的語義區(qū)數(shù)量,初始的聚類簇心以位置語義Voronoi圖中GLI為準(zhǔn).

經(jīng)過上述推導(dǎo),虛假軌跡的發(fā)布流程大致可描述為:第1步構(gòu)建位置語義Voronoi圖;第2步生成虛假位置;第3步篩選滿足差分隱私的虛假位置;第4步進(jìn)一步選擇滿足位置語義的虛假位置;第5步將滿足語義和隱私的位置進(jìn)行聚類操作;第6步計(jì)算虛假位置與真實(shí)位置的Hausdorff距離;第7步對(duì)距離進(jìn)行排序,選擇距離最小的點(diǎn)作為發(fā)布位置.

算法2.虛假軌跡發(fā)布算法

輸入:狀態(tài)轉(zhuǎn)移矩陣M,地理信息GLI,隱私等級(jí)PL,隱私模型δ,t時(shí)刻用戶真實(shí)位置Zt,t-1時(shí)刻用戶真實(shí)位置Zt-1,t-1時(shí)刻的擾動(dòng)位置dlt-1,距離偏差量Dgap.

輸出:t時(shí)刻的發(fā)布位置,與真實(shí)位置的誤差距離Dis.

1.initializeWr,RL,R,HD,Dis;

2.Voronoi=Delaunay(GLI);

3.RL=get_location(REQ,Dgap,Zt);//由公式(8)生成

4.ε=δ/PL;//由公式(9)生成

5.DP_RL=select_location(M,RL,Zt,ε,R);

6.a=get_location_semantic(Zt);

7.CC=select_clustering_center(GLI);

8.whilei∈DP_RL:

9.b=get_location_semantic(i);

10. ifa=b:

11. returnLS_DP_RL;//滿足語義和隱私

12. whilei∈LS_DP_RL:

13.Wr=get_clustering(CC);

14.i++;

15.forj∈Wr,j++:

16.HD[j]=get_hd(dlt-1,Wr[j],Zt-1,Zt);

17.end for;

18.Sort min(HD,Wr);//將Wr按HD最小排序

19.Dis=get_distance(Wr,Zt);

20.Res=get_result(Wr,Dis);

21.returnRes.

3 仿真分析

本文采用真實(shí)的公開數(shù)據(jù)集T-Drive[24]和Roma Taxi[25]對(duì)DPSL進(jìn)行仿真實(shí)驗(yàn)分析.T-Driver數(shù)據(jù)集包含2008年2月2日～2月8日期間,北京內(nèi)10357輛出租車的GPS軌跡,數(shù)據(jù)集中總點(diǎn)數(shù)約為1500萬,采樣間隔在30s～300s之間,平均采樣間隔為177s.Roma Taxi數(shù)據(jù)集包含2014年2月1日～3月2日期間,意大利羅馬內(nèi)大約320輛出租車的GPS軌跡,數(shù)據(jù)集中總點(diǎn)數(shù)約為2100萬,平均采樣間隔為7s.由于原數(shù)據(jù)集中使用的時(shí)間戳不一致,導(dǎo)致無法直接進(jìn)行實(shí)驗(yàn),因此需要對(duì)原數(shù)據(jù)集進(jìn)行預(yù)處理,抽取車輛編號(hào)、時(shí)間、經(jīng)度和緯度構(gòu)建成新的數(shù)據(jù)集.

實(shí)驗(yàn)環(huán)境配置為3.6GHz CPU,16GB RAM,Microsoft Windows 10操作系統(tǒng),實(shí)驗(yàn)平臺(tái)為Pycharm 2020.實(shí)驗(yàn)內(nèi)容圍繞三方面展開:通過對(duì)比不同算法的隱私保護(hù)程度評(píng)測算法的隱私保護(hù)性能;分析不同的隱私預(yù)算及語義區(qū)(聚類簇頭)數(shù)量SAn對(duì)軌跡誤差距離的影響,評(píng)測算法的軌跡可用性;對(duì)比軌跡數(shù)量Tran對(duì)生成虛假位置的影響以及分析SAn對(duì)算法運(yùn)算時(shí)間的影響,評(píng)估算法性能.實(shí)驗(yàn)對(duì)比算法為PIM[16],該算法采用基于差分隱私的實(shí)時(shí)軌跡保護(hù)方法.

3.1 隱私性能評(píng)測

在衡量隱私預(yù)算δ對(duì)隱私保護(hù)程度影響時(shí),相同條件下ε′值越小表示隱私保護(hù)程度越高.本次實(shí)驗(yàn)參數(shù)設(shè)定為:SAn=3,Tran=90,δ=[0.2,1],步長為0.2.

從圖3中可以看出,ε′隨著δ增加而增加,但ε′的值總是小于δ;對(duì)比不同算法,PIM與DPSL對(duì)應(yīng)的值基本一致,最大誤差是在T-Driver數(shù)據(jù)集中,當(dāng)δ=1時(shí)DPLM的ε′值為0.9284,PIM的ε′值為0.8975,DPLM的隱私保護(hù)性能僅比PIM低3.3%.最小誤是在T-Driver數(shù)據(jù)集中,當(dāng)δ=0.4時(shí),DPLM的ε′值為0.36589而PIM的ε′值為0.3659,僅相差0.03%.這是因?yàn)镈PLM側(cè)重點(diǎn)在于優(yōu)先考慮的軌跡的可用性,雖然相比PIM保護(hù)程度略低但是相差不多,能夠滿足用戶的隱私安全需求;對(duì)比不同數(shù)據(jù)集,當(dāng)δ相同時(shí)Roma Taxi數(shù)據(jù)集中的ε′均大于T-Driver數(shù)據(jù)集.這是因?yàn)镈PSL和PIM都是基于馬爾可夫的模型,受軌跡相關(guān)性影響大.Roma Taxi數(shù)據(jù)集采樣間隔穩(wěn)定,相較之下軌跡中的位置之間時(shí)空相關(guān)性比T-Driver數(shù)據(jù)集更強(qiáng).

圖3 隱私保護(hù)程度Fig.3 Degree of privacy protection

隱私性能實(shí)驗(yàn)結(jié)果表明,DPSL的隱私保護(hù)程度與PIM基本一致,當(dāng)軌跡相關(guān)性較強(qiáng)時(shí),隱私保護(hù)程度會(huì)有所下降.但是在所有應(yīng)用場景中,DPSL均能滿足用戶的隱私需求.

3.2 軌跡可用性評(píng)測

在衡量隱私預(yù)算δ對(duì)生成的虛假軌跡可用性影響時(shí),MTD數(shù)值越低,表明軌跡可用性越好.本次實(shí)驗(yàn)參數(shù)設(shè)定為:SAn=3,Tran=90,δ取值范圍為[0.2,1],步長為0.2.

圖4從整體上看,MTD隨著隱私預(yù)算δ的增加而減少,且減少幅度也在變小,當(dāng)δ接近1時(shí),MTD逐漸趨于穩(wěn)定.這是因?yàn)楦唠[私預(yù)算降低了位置擾動(dòng)幅度,減少了虛假位置與真實(shí)位置之間的誤差距離,使MTD變小;對(duì)比不同算法,在給定δ時(shí),PIM算法對(duì)應(yīng)的MTD均大于DPSL,這是因?yàn)镈PSL算法在位置發(fā)布之前,從用戶行為模式和軌跡曲線相似度兩方面入手,提高虛假軌跡與真實(shí)軌跡的相似度,降低了軌跡之間的誤差距離,PIM算法更注重于位置隱私的保護(hù)質(zhì)量并未對(duì)軌跡做出優(yōu)化,最終導(dǎo)致相同條件下DPSL的MTD較小,軌跡可用性高;對(duì)比不同數(shù)據(jù)集,相同隱私預(yù)算下的PIM和DPSL算法,在Roma Taxi數(shù)據(jù)集MTD值均小于T-Driver數(shù)據(jù)集,這是因?yàn)門-Driver采樣間隔不穩(wěn)定,且采用頻率低于Roma Taxi.同時(shí)受到數(shù)據(jù)采集地的地理因素影響,最終導(dǎo)致在Roma Taxi數(shù)據(jù)集上MTD值整體偏小.

圖4 δ對(duì)軌跡的可用性的影響Fig.4 Effect of δ on the availability of the trajectory

圖5是評(píng)測SAn對(duì)軌跡可用性影響的實(shí)驗(yàn)結(jié)果,本次實(shí)驗(yàn)參數(shù)設(shè)定為:δ=0.6,Tran=90,SAn=[3,18],步長為3.從整體上看,伴隨著SAn的增長,MTD也在逐漸增加,但是觀察縱坐標(biāo)軸可發(fā)現(xiàn)MTD的增加幅度并不大,增加趨勢緩慢而且有個(gè)別區(qū)域并未出現(xiàn)增長.如在T-Driver數(shù)據(jù)集中SAn為9和12時(shí),對(duì)應(yīng)的MTD值相同.以上結(jié)果是因?yàn)殡S著軌跡中語義區(qū)域的數(shù)量增加使得軌跡復(fù)雜度變高,為了保障軌跡的相似度導(dǎo)致部分語義區(qū)無法選擇最佳發(fā)布位置,從而增大位置之間的距離.此外,由于劃分的語義區(qū)面積大小不一致,所以會(huì)出現(xiàn)SAn增加但是MTD不變的現(xiàn)象.

圖5 語義區(qū)數(shù)量對(duì)軌跡的可用性的影響Fig.5 Effect of SAn on the availability of the trajectory

軌跡可用性評(píng)測實(shí)驗(yàn)表明,發(fā)布軌跡前對(duì)虛假軌跡進(jìn)行曲線相似度優(yōu)化,能有效減少真實(shí)軌跡與虛假軌跡之間的誤差,提高軌跡的可用性;軌跡的可用性會(huì)受到軌跡數(shù)據(jù)的時(shí)空相關(guān)性影響;隨著軌跡中語義區(qū)數(shù)量增加導(dǎo)致軌跡的復(fù)雜程度變高后,生成的虛假軌跡可用性也會(huì)有所下降.

3.3 運(yùn)算性能評(píng)測

本文從兩方面對(duì)算法運(yùn)算性能進(jìn)行評(píng)測,分別是分析虛假位置的生成效率和對(duì)比不同聚簇?cái)?shù)目下算法的運(yùn)算時(shí)間.圖6(a)是虛假位置生成效率的實(shí)驗(yàn)結(jié)果,在本文2.2.1節(jié)中描述的虛假位置生成方式需要參照周圍車輛,為了驗(yàn)證該算法的運(yùn)算性能,將實(shí)驗(yàn)內(nèi)容設(shè)定為:首先選取一條軌跡作為用戶當(dāng)前位置,然后使用其他軌跡作為參照物來源,通過對(duì)比不同軌跡數(shù)量下生成虛假位置的速率,對(duì)虛假位置生成算法的性能進(jìn)行評(píng)測.本次實(shí)驗(yàn)參數(shù)設(shè)定為:SAn=1,Tran分別為30、90和180,記錄時(shí)間為0.1s～1s,步長0.1s,服務(wù)響應(yīng)時(shí)間Tr=3s,Dgap為10～15米,數(shù)據(jù)集為T-Driver.

圖6 算法性能評(píng)測Fig.6 Evaluation of algorithm performance

圖6(a)中,0.1s～0.3s區(qū)間內(nèi)不同軌跡數(shù)量生成的虛假位置基本一致,在0.3s～0.6s區(qū)間內(nèi),Tran=180時(shí),虛假位置數(shù)量增加迅速;Tran=90時(shí)緩慢增加;Tran=30時(shí),虛假位置數(shù)量增加不明顯.在0.6s～1s區(qū)間內(nèi),Tran=180時(shí),虛假位置已經(jīng)不再增加;Tran=90時(shí),虛假位置數(shù)量增加速度減緩并于0.9s處停滯不再增加;Tran=30時(shí),虛假位置數(shù)量開始有明顯的提升.3組軌跡數(shù)據(jù)中,生成的虛假位置均低于軌跡數(shù)量.實(shí)驗(yàn)結(jié)果表明,參照軌跡中存在噪聲并非所有位置都符合虛假位置要求;提高參照軌跡數(shù)量能有效增加虛假位置生成的效率.應(yīng)用到車聯(lián)網(wǎng)使用場景中,用戶當(dāng)前位置的車流量會(huì)影響虛假位置的生成效率,高車流量的路段能有效提高虛假位置的生成速率.

圖6(b)是評(píng)測SAn對(duì)DPSL算法運(yùn)行時(shí)間影響的實(shí)驗(yàn)結(jié)果,實(shí)驗(yàn)參數(shù)設(shè)定為:δ=0.6,Tran=90,SAn=[3,18],步長為3.觀察結(jié)果可知,伴隨著語義區(qū)域數(shù)量的增加,運(yùn)算時(shí)間也在不斷增加,但是增加速率逐漸趨于平緩.對(duì)比不同數(shù)據(jù)集,T-Driver數(shù)據(jù)集與Roma Taxi數(shù)據(jù)集之間的差距基本保持一致,且發(fā)展趨勢相同.運(yùn)算性能實(shí)驗(yàn)結(jié)果表明DPSL有良好的運(yùn)算性能,在軌跡復(fù)雜度變化時(shí)能有效保障算法運(yùn)算時(shí)間的穩(wěn)定性,適用于車聯(lián)網(wǎng)中復(fù)雜多變的道路狀況.

4 結(jié) 論

為了滿足車聯(lián)網(wǎng)中軌跡隱私的保護(hù)需求,本文在差分隱私基礎(chǔ)上引入位置語義概念,提出基于位置語義的隱私等級(jí)計(jì)算方法并結(jié)合隱私預(yù)算搭建了δ-隱私模型;為了提高軌跡可用性,使用K-means對(duì)滿足隱私需求的位置基于位置語義進(jìn)行聚類,并使用Hausdorff距離衡量軌跡相似度,篩選出最佳發(fā)布位置.仿真實(shí)驗(yàn)結(jié)果表明,本文方法在保障軌跡隱私需求的前提下,有效提高了生成虛假軌跡的可用性.在實(shí)際場景中,車輛的停留點(diǎn)、方向以及周邊車輛和環(huán)境都可能影響隱私安全.因此,今后的研究重點(diǎn)將圍繞車輛的運(yùn)行狀態(tài)展開,進(jìn)一步完善車聯(lián)網(wǎng)的軌跡隱私保護(hù)模型.