鄭 淼，王 斌，楊曉春

（東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110819）

0 引 言

在日常生活中，移動(dòng)網(wǎng)絡(luò)的應(yīng)用變得越來越廣泛，人們使用移動(dòng)終端發(fā)送查詢請(qǐng)求也變得越來越頻繁，基于位置的服務(wù)所帶來的隱私保護(hù)問題也越來越受到人們的關(guān)注．移動(dòng)用戶使用移動(dòng)終端發(fā)送查詢請(qǐng)求，既希望得到高質(zhì)量的服務(wù)，又希望可以保證位置查詢中不泄露位置隱私和查詢隱私，所以需要高效的隱私保護(hù)模型來更好地服務(wù)于用戶．

在公路網(wǎng)絡(luò)中，隱私保護(hù)有著其特殊性和統(tǒng)一性．統(tǒng)一性在于路網(wǎng)的隱私保護(hù)模型是在基于位置服務(wù)隱私保護(hù)的基礎(chǔ)上建立起來的，是一種特殊的隱私保護(hù)．特殊性在于路網(wǎng)上的移動(dòng)用戶的空間范圍受限，歐氏空間下的隱私保護(hù)方法無法很好地應(yīng)用于公路網(wǎng)絡(luò)．例如，移動(dòng)用戶大多沿著道路移動(dòng)且查詢的興趣點(diǎn)也多在道路上，此時(shí)用戶的位置隱私泄露的風(fēng)險(xiǎn)就會(huì)加大，而且公路上的用戶大多是移動(dòng)用戶，攻擊者通過獲知用戶行車導(dǎo)航服務(wù)中發(fā)送的連續(xù)查詢請(qǐng)求，可以推斷出用戶的行車速度，甚至可以推測出用戶的位置信息．

以往存在很多路網(wǎng)的隱私保護(hù)模型，都可以高效地保護(hù)用戶的位置隱私和查詢隱私，但是又存在著一定的缺點(diǎn)．其一，同一匿名集內(nèi)的用戶，構(gòu)造的匿名集不具有相互性．在理想情況下，兩個(gè)用戶在發(fā)送查詢請(qǐng)求時(shí)分別構(gòu)造的匿名空間彼此之間完全相同，我們稱這兩個(gè)用戶構(gòu)造的匿名集具有相互性．但是，在現(xiàn)有方法中，用戶在發(fā)送查詢請(qǐng)求時(shí)構(gòu)造的匿名集并不完全相同，不完全具有相互性．在這種情況下，如果攻擊者知道路段的背景信息，知道用戶的位置，通過背景推斷，用戶的查詢隱私就會(huì)遭到泄露．其二，如果單純地用路段人數(shù)或者路段長度來設(shè)定隱私度的話，則可能形成的匿名區(qū)域只包括一條路徑．匿名度即為各匿名集內(nèi)包含的移動(dòng)用戶人數(shù)的最低要求．在這種情況下，匿名區(qū)域?qū)τ脩舻谋Ｗo(hù)強(qiáng)度就會(huì)降低，用戶被攻擊者攻擊的概率將會(huì)變大．所以設(shè)計(jì)出符合公路網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)的位置隱私保護(hù)模型是一個(gè)亟需解決的問題．

本文的貢獻(xiàn)在于設(shè)計(jì)出了新的路網(wǎng)隱私保護(hù)模型，即在網(wǎng)絡(luò)擴(kuò)張技術(shù)方法的基礎(chǔ)上，形成一個(gè)內(nèi)部含有環(huán)的無向圖，可以防止匿名區(qū)域內(nèi)只包含單一路徑情況的發(fā)生，同時(shí)，可以結(jié)合環(huán)和樹的結(jié)構(gòu)特點(diǎn)，為移動(dòng)用戶提供更隱秘的匿名空間．并且，本文首次提出了對(duì)匿名空間的精煉，檢測同一匿名集內(nèi)的用戶是否完全相同或者每兩個(gè)匿名集去掉交集后是否是單一路徑，目的是使匿名集具有相互性或者增加匿名集的差異性，防止隱私泄露．

本文第1節(jié)主要介紹了位置隱私保護(hù)技術(shù)、查詢隱私保護(hù)技術(shù)和公路網(wǎng)絡(luò)環(huán)境下的隱私保護(hù)技術(shù)及相關(guān)工作；第2節(jié)介紹了相關(guān)的背景知識(shí)和相關(guān)的定義；第3節(jié)介紹了公路網(wǎng)絡(luò)下帶環(huán)無向圖的最小匿名空間的構(gòu)造；第4節(jié)介紹了對(duì)帶環(huán)無向圖的最小匿名空間的精煉；第5節(jié)介紹了系統(tǒng)的實(shí)驗(yàn)結(jié)果與分析；第6節(jié)總結(jié)全文．

1 相關(guān)工作

公路網(wǎng)絡(luò)中，用戶的位置隱私和查詢隱私［1］是相關(guān)聯(lián)的．現(xiàn)有的隱私保護(hù)方法中，位置隱私的保護(hù)方法主要有假位置［2－3］、時(shí)空匿名［4－11］和數(shù)據(jù)加密［12］．Marco Gruteser等［4］提出了位置k－匿名模型，即當(dāng)一個(gè)移動(dòng)用戶的位置無法與其他（k－1）個(gè)用戶的位置相區(qū)別時(shí)，此時(shí)滿足位置k－匿名．此方法通過對(duì)用戶位置進(jìn)行時(shí)空模糊，降低其分辨率，增加了攻擊者跟蹤用戶的難度，其不僅適用于位置隱私保護(hù)，而且適用于查詢隱私保護(hù)．文獻(xiàn)［13］提出了一種星形的位置隱私模型X－star，并基于該模型設(shè)計(jì)了具有網(wǎng)絡(luò)約束的移動(dòng)模型下位置隱私保護(hù)的一般框架，能很好地實(shí)現(xiàn)相互性和差異性．文獻(xiàn)［14］中，Kim等人對(duì)X－star進(jìn)行了擴(kuò)展，提出了H－star算法．潘曉等［15］發(fā)表了位置服務(wù)中的連續(xù)查詢隱私保護(hù)研究，提出了δp－隱私模型和δq－質(zhì)量模型，可以更好地應(yīng)用于連續(xù)位置查詢，同時(shí)保護(hù)了位置隱私和查詢隱私．只有文獻(xiàn)［4］和文獻(xiàn)［15］將查詢隱私和位置隱私連接起來，文獻(xiàn)［15］還將其應(yīng)用在連續(xù)查詢當(dāng)中．而文獻(xiàn)［13－14，16－20］皆只單一地考慮了用戶的位置隱私，沒有考慮用戶的查詢隱私．薛嬌、劉向宇等［16］針對(duì)路網(wǎng)的獨(dú)特結(jié)構(gòu)，提出了隱匿環(huán)和隱匿樹的概念，防止了公路網(wǎng)絡(luò)下攻擊者將用戶定位在某一條單一路徑內(nèi)，阻止了路網(wǎng)環(huán)境下用戶的隱私泄露．文獻(xiàn)［17］提出了網(wǎng)絡(luò)擴(kuò)張的位置隱私保護(hù)方法，用路段長度和人數(shù)來設(shè)定隱私度，方式簡單易于實(shí)現(xiàn)，查詢開銷也比較?。遣痪哂邢嗷バ?，且有單一路徑問題的存在．文獻(xiàn)［18－20］在網(wǎng)絡(luò)擴(kuò)張的基礎(chǔ)上進(jìn)行了改進(jìn)，最主要的方法是將路網(wǎng)圖的序號(hào)進(jìn)行有序排列，然后按序號(hào)進(jìn)行分裝．文獻(xiàn)［17－20］都是用路段上的人數(shù)來設(shè)置隱私度，缺點(diǎn)就是在人數(shù)密集區(qū)域匿名集可能只包含一條路段，用戶被攻擊的概率變大．

以上提到的隱私保護(hù)方法，大多都是基于位置隱私的保護(hù)方法．但是在實(shí)際應(yīng)用中，查詢隱私和位置隱私都是相互關(guān)聯(lián)的．本文將查詢隱私和位置隱私聯(lián)系起來，首次應(yīng)用于公路網(wǎng)絡(luò)中，同時(shí)，應(yīng)用帶環(huán)無向圖的匿名結(jié)構(gòu)，可以防止單一路徑的匿名區(qū)域出現(xiàn)，可以更好地防止路網(wǎng)中用戶的隱私泄露．

2 背景知識(shí)及相關(guān)定義

本文采用中心服務(wù)器結(jié)構(gòu)，除了包括移動(dòng)用戶和基于位置的數(shù)據(jù)庫服務(wù)器之外，在二者之間加入了第三方可信中間件即位置匿名服務(wù)器．移動(dòng)用戶向位置匿名服務(wù)器發(fā)送包含確切位置信息的查詢請(qǐng)求，匿名服務(wù)器使用某種匿名算法完成位置匿名后，將匿名后的查詢請(qǐng)求發(fā)送給提供位置服務(wù)的數(shù)據(jù)庫服務(wù)器，數(shù)據(jù)庫服務(wù)器將根據(jù)匿名區(qū)域進(jìn)行查詢處理，并將查詢結(jié)構(gòu)的候選集返回給位置匿名服務(wù)器，位置匿名服務(wù)器從候選結(jié)果集中挑選出真正的結(jié)果返回給移動(dòng)用戶，這樣便完成了一次查詢請(qǐng)求．

2．1 現(xiàn)有公路網(wǎng)絡(luò)模型及其存在的缺點(diǎn)

公路網(wǎng)絡(luò)可以被看作是一個(gè)帶權(quán)無向圖G（V，E，W）［16］，其中V表示節(jié)點(diǎn)集，代表公路網(wǎng)絡(luò)中公路的交叉口，如果一個(gè)節(jié)點(diǎn)v的度為1，代表此節(jié)點(diǎn)只連接一條公路；如果一個(gè)節(jié)點(diǎn)的度大于等于2，代表此節(jié)點(diǎn)是兩條甚至多條公路的交叉路口；E表示邊集，代表公路網(wǎng)絡(luò)中已經(jīng)存在的公路；W表示邊e的權(quán)值的集合，本文中代表公路網(wǎng)絡(luò)中各條邊上的移動(dòng)用戶的數(shù)量．

如圖1所示，V＝｛v1，…，v7｝表示公路網(wǎng)絡(luò)中的交叉路口，交叉路口之間的連線代表公路網(wǎng)絡(luò)中的公路，U1，…，U5表示公路網(wǎng)絡(luò)中發(fā)送查詢請(qǐng)求的移動(dòng)用戶，邊上的權(quán)重值代表此條公路上的移動(dòng)用戶人數(shù)．

圖1 公路網(wǎng)絡(luò)模型Fig．1 A model on road network

現(xiàn)有的支持路網(wǎng)的隱私保護(hù)模型主要采用匿名技術(shù)保護(hù)用戶的位置隱私和查詢隱私，但存在以下的問題：

（1）同一匿名集中的用戶，構(gòu)造的匿名集不具有相互性，即同一匿名集內(nèi)，兩個(gè)用戶在發(fā)送查詢請(qǐng)求時(shí)分別構(gòu)造的匿名空間彼此之間不完全相同．圖2是一條在匿名度人數(shù)k為6時(shí)的匿名化公路網(wǎng)絡(luò)，其中（v5，v6）路段上用戶U1的匿名集AS1＝｛（v5，v6），（v6，v7），（v6，v3），（v3，v7）｝，如圖2中（a）所示．同理，（v6，v3）或者（v6，v7）路段上任意用戶U2的匿名集AS2＝｛（v6，v7），（v6，v3），（v3，v7）｝，（v3，v7）路段上任意用戶U3的匿名集AS3＝｛（v6，v7），（v6，v3），（v3，v7）｝，如圖2中（b）所示．如果匿名集AS1中發(fā)出查詢請(qǐng)求，只能是（v5，v6）路段上用戶U1發(fā)出的查詢請(qǐng)求，因?yàn)槿绻荱2或者U3發(fā)出查詢請(qǐng)求的話，匿名集應(yīng)該是AS2或者是AS3．最壞的情況下，如果攻擊者知道路段的背景信息，知道用戶的位置，則用戶U1的查詢隱私泄露．

圖2 不同用戶的匿名集不具有相互性Fig．2 Different users have different anonymous spaces

（2）如果單純地用移動(dòng)用戶人數(shù)或路段長度來設(shè)定隱私度的話，則形成的匿名區(qū)域可能只包括一條路徑．例如，圖3是在匿名度人數(shù)k為6時(shí)的匿名化公路網(wǎng)絡(luò)匿名空間對(duì)比圖，如果用戶U5發(fā)出查詢請(qǐng)求，匿名集是AS5＝｛（v3，v5）｝，只包含一條路段，匿名區(qū)域?qū)τ脩舻谋Ｗo(hù)強(qiáng)度將會(huì)降低，用戶被攻擊者攻擊的概率變大．所以設(shè)計(jì)出符合公路網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)的位置隱私保護(hù)模型是一個(gè)亟需解決的問題．

圖3 單一路徑匿名空間的缺點(diǎn)Fig．3 Disadvantages of anonymous space with one road

2．2 相關(guān)定義

定義1位置隱私 位置隱私是指任意用戶Uj在某一條公路ei上，ei∈E，用戶Uj發(fā)送一個(gè)查詢請(qǐng)求，在為用戶提供高質(zhì)量服務(wù)的同時(shí)，防止用戶的位置信息發(fā)生泄漏．

定義2查詢隱私 查詢隱私是指任意用戶Uj在某一條公路ei上，ei∈E，用戶Uj發(fā)送一個(gè)查詢請(qǐng)求，在為用戶提供高質(zhì)量服務(wù)的同時(shí)，防止用戶的查詢信息發(fā)生泄露．

一個(gè)移動(dòng)用戶通過手機(jī)移動(dòng)終端在三好街發(fā)送查詢請(qǐng)求“距離三好街最近的醫(yī)院在哪？”，移動(dòng)用戶既不想讓別人知道他是在三好街發(fā)送的查詢請(qǐng)求，也不想讓別人知道他想要去醫(yī)院，用戶在三好街發(fā)送查詢請(qǐng)求是用戶的位置隱私，查詢最近的醫(yī)院是用戶的查詢隱私．保護(hù)用戶的隱私信息，就要保證用戶的位置隱私和查詢隱私皆不遭到泄露．

定義3匿名集的相互性 匿名集的相互性是指同一匿名集內(nèi)的任意兩個(gè)用戶Ui和Uj，其構(gòu)造的匿名集分別是ASi和ASj．存在如下公式：ASi＝ASj，則代表用戶Ui和Uj分別構(gòu)造的匿名集具有相互性，即用戶Ui和用戶Uj分別構(gòu)造的匿名集中包含完全相同的邊．

定義4匿名集的差異性 匿名集的差異性是指在定義3中，ASi≠ASj，則用戶Ui和Uj分別構(gòu)造的匿名集具有差異性，即用戶Ui和用戶Uj分別構(gòu)造的匿名集中包含不完全相同的邊．

定義5查詢?nèi)蝿?wù) 查詢?nèi)蝿?wù)是指用戶通過移動(dòng)終端等設(shè)備向位置匿名服務(wù)器發(fā)送查詢請(qǐng)求，并從服務(wù)器接收查詢的結(jié)果，這一過程，便是一個(gè)查詢?nèi)蝿?wù)．

3 最小匿名空間的構(gòu)造

本章主要介紹帶環(huán)無向圖的匿名空間的構(gòu)造方法，包括以下4個(gè)部分：①路網(wǎng)隱私泄露的原因分析；②具體介紹如何能夠成功地構(gòu)造帶環(huán)無向圖的最小匿名空間并且使構(gòu)造的帶環(huán)無向圖的匿名空間最小化最高效；③最小匿名的具體構(gòu)造方法：結(jié)合環(huán)和樹的結(jié)構(gòu)特點(diǎn)，形成一個(gè)內(nèi)部帶有環(huán)的匿名空間；④具體事例分析，帶環(huán)無向圖的應(yīng)用和優(yōu)點(diǎn)．

3．1 路網(wǎng)中用戶隱私泄露的原因分析

如圖2和圖3所示，現(xiàn)有的隱私保護(hù)模型不僅不具有相互性而且還存在單一路徑問題．由于單一路徑問題的存在，匿名區(qū)域?qū)τ脩舻谋Ｗo(hù)強(qiáng)度將會(huì)降低，用戶被攻擊者攻擊的概率將會(huì)變大．如圖3所示，用戶U5的匿名集｛（v3，v5）｝對(duì)用戶的保護(hù)強(qiáng)度就很低．一旦此匿名集發(fā)送查詢請(qǐng)求，攻擊者就會(huì)確定用戶U5一定在路段（v3，v5）上，用戶U5的位置隱私就被泄露了．

為了防止單一路徑問題的出現(xiàn)，本文提出了帶環(huán)無向圖的結(jié)構(gòu)作為用戶查詢的匿名空間．因?yàn)橛协h(huán)的存在，匿名空間一定不存在單一路徑化的問題．這樣，多條路徑的存在，就會(huì)降低用戶被攻擊者攻擊的概率，增強(qiáng)對(duì)用戶的保護(hù)強(qiáng)度．如圖3所示，匿名集｛（v3，v6），（v6，v5），（v3，v5）｝對(duì)用戶U5的保護(hù)強(qiáng)度就會(huì)大于匿名集｛（v3，v5）｝對(duì)用戶U4的保護(hù)強(qiáng)度．

通過以上分析可知：在路網(wǎng)環(huán)境下，匿名空間中只要有環(huán)的存在，就能保證用戶的隱私不發(fā)生泄漏．所以，本文提出帶環(huán)無向圖的匿名空間，防止單一路徑的存在，確保用戶的隱私不被泄漏．

3．2 帶環(huán)無向圖的最小匿名空間

根據(jù)公路網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)，在路網(wǎng)圖中構(gòu)建足夠小的帶環(huán)無向圖，能夠結(jié)合環(huán)和樹的結(jié)構(gòu)特點(diǎn)，充分保證用戶匿名空間的隱秘性．在帶環(huán)圖上的某一條邊上，用戶發(fā)送查詢請(qǐng)求時(shí)，攻擊者無法判斷用戶是在哪一條邊上發(fā)出的查詢請(qǐng)求，即攻擊者推測用戶在各個(gè)邊上的概率都相同，那么用戶的位置隱私就將會(huì)得到很好的保護(hù)．同時(shí)，也可以防止在人流密集的道路上，因?yàn)槿肆髁窟^大而造成的匿名空間太小甚至只包含一條路徑的情況發(fā)生，從而降低了用戶被攻擊者攻擊的概率．所以，帶環(huán)無向圖的匿名空間，在避免上述缺點(diǎn)的同時(shí)，能夠更好地保護(hù)用戶的隱私信息．

如何能夠成功地構(gòu)造帶環(huán)無向圖的匿名空間，并且使構(gòu)造的帶環(huán)無向圖的匿名空間能夠最小化最高效是最大的挑戰(zhàn)．

首先，根據(jù)現(xiàn)代公路網(wǎng)絡(luò)的特點(diǎn)可知，公路網(wǎng)絡(luò)是一個(gè)無向連通圖，那么公路網(wǎng)絡(luò)中一定會(huì)有環(huán)的存在．所以，帶環(huán)無向圖的匿名空間一定會(huì)構(gòu)造成功；其次，為了使構(gòu)造的帶環(huán)無向圖能夠最小最高效，我們采用路網(wǎng)上的移動(dòng)用戶人數(shù)k來設(shè)置隱私度，在保證有環(huán)存在的情況下，只要匿名集內(nèi)移動(dòng)用戶數(shù)量達(dá)到隱私度要求，匿名集便構(gòu)造成功．通過控制移動(dòng)用戶人數(shù)，可以防止匿名集內(nèi)移動(dòng)用戶人數(shù)過多的情況發(fā)生，也可以防止匿名空間內(nèi)路段數(shù)過多的情況發(fā)生．最小匿名空間的構(gòu)造過程中，本文采用寬度優(yōu)先搜索的方法，時(shí)間復(fù)雜度為O（n＋e）．因此，能夠成功構(gòu)造帶環(huán)無向圖的匿名集，并且使構(gòu)造的帶環(huán)無向圖能夠最小化最高效．

3．3 最小匿名空間的構(gòu)造

在帶環(huán)無向圖的構(gòu)造中，用匿名空間中路段上移動(dòng)用戶總?cè)藬?shù)來設(shè)置匿名度，即匿名空間中預(yù)先設(shè)定的最少移動(dòng)用戶人數(shù)為此匿名空間的匿名度．用每一條路段上的移動(dòng)用戶數(shù)量作為考量，匿名空間內(nèi)所有路段上的總?cè)藬?shù)要求滿足匿名空間中預(yù)先設(shè)定的最少移動(dòng)用戶人數(shù)，滿足匿名空間的匿名度，從路網(wǎng)上的某一點(diǎn)出發(fā)，將用戶U所在的路段（v1，v2）作為匿名集，在滿足k的匿名度要求的條件下，首先選擇能夠使匿名空間構(gòu)成環(huán)的路段，其次選擇路段人數(shù)最少的邊加入匿名集，以此條件進(jìn)行網(wǎng)絡(luò)擴(kuò)張，直到形成一個(gè)內(nèi)部含有環(huán)的無向圖．若此時(shí)滿足k的匿名度，則匿名空間構(gòu)建成功；若不滿足k的匿名度，則繼續(xù)選擇人數(shù)最少的邊加入匿名集，直到滿足k的匿名度．但此時(shí)已不需要考慮是否存在環(huán)的問題，因?yàn)榄h(huán)已存在．所以，只需要考慮邊的人數(shù)問題．

算法1 帶環(huán)無向圖的生成

輸入：無向圖G，用戶U和用戶U所在邊（vi，vj），vi，vj分別為此邊的兩個(gè)端點(diǎn)輸出：構(gòu)成匿名集的所有邊，以及所有邊的用戶總數(shù)1．根據(jù)輸入信息，得到匿名集AS＝｛（vi，vj）｝，匿名頂點(diǎn)集VAS＝｛vi，vj｝，假設(shè)i＜j；2．while 匿名集AS內(nèi)無環(huán)3．if 存在vk1，vh1∈VAS，……，vkn，vhn∈VAS，（vk1，vh1）……（vkn，vhn）不屬于AS 4．if（vk1，vh1）……（vkm，vhm），各邊權(quán)重相同，并且權(quán)重最小，m＜n 5．（vki，vhi）加入匿名集AS．vki，vhi是所有權(quán)重最小的邊中序號(hào)最小節(jié)點(diǎn)；6．else 7．（vki，vhi）加入匿名集AS．vki，vhi是所有邊中的權(quán)重最小邊；8．else 9．從匿名頂點(diǎn)集VAS中節(jié)點(diǎn)出發(fā)，尋找權(quán)重最小的邊（v，vk），v∈VAS；10．if存在n條權(quán)重最小邊，vi＋1，vi＋2，……，vi＋n 11．（vk，vi＋g）加入匿名集AS，vi＋g加入匿名頂點(diǎn)集VAS中，其中vk是匿名頂點(diǎn)集VAS 12．中最小的節(jié)點(diǎn)，vi＋g是所有權(quán)重最小邊中序號(hào)最小的節(jié)點(diǎn)；13．while 匿名集AS內(nèi)有環(huán)且不滿足匿名度14．從集合VAS中節(jié)點(diǎn)出發(fā)，尋找權(quán)重最小邊（v，vk），v∈VAS；15．if存在n條權(quán)重最小邊，vi＋1，vi＋2，……，vi＋n 16．（vk，vi＋g）加入匿名集AS，vi＋g加入匿名頂點(diǎn)集VAS中，其中vk是匿名頂點(diǎn)集VAS中最小的節(jié)點(diǎn)，vi＋g是所有權(quán)重最小邊中序號(hào)最小的節(jié)點(diǎn)；17．return AS；

通過算法1，已經(jīng)知道了帶環(huán)圖的構(gòu)造過程，如圖1所示，設(shè)置隱私度為k＝6，用戶U1所在的邊為（v5，v6），匿名集AS1＝｛（v5，v6）｝，匿名頂點(diǎn)集VAS＝｛v5，v6｝，從v5，v6出發(fā)，尋找人數(shù)最小邊，且序號(hào)最小邊，（v6，v3）加入匿名集，匿名頂點(diǎn)集VAS＝｛v5，v6，v3｝，之后（v3，v7）加入匿名集，匿名頂點(diǎn)集VAS＝｛v5，v6，v3，v7｝，此時(shí)v6，v7在匿名頂點(diǎn)集VAS中，（v6，v7）邊卻不在匿名集中，將（v6，v7）加入匿名集，環(huán)已存在，此時(shí)k＝7，滿足隱私度，帶環(huán)圖的匿名集構(gòu)造成功，AS1＝｛（v5，v6），（v6，v3），（v3，v7），（v6，v7）｝．而當(dāng)用戶U4構(gòu)造匿名集時(shí)，當(dāng)環(huán)（v1，v2），（v4，v2），（v1，v4）構(gòu)造成功時(shí)，此時(shí)k＝3，不滿足k的隱私度，繼續(xù)添加人數(shù)最小邊，（v2，v3）和（v4，v5）人數(shù)同為3人，選擇序號(hào)較小的邊（v2，v3），此時(shí)匿名集滿足k的隱私度k＝6，帶環(huán)圖的匿名集構(gòu)造成功，AS4＝｛（v1，v2），（v4，v2），（v1，v4），（v2，v3）｝．用戶U1和用戶U4在算法1的方法下，成功構(gòu)造出了帶環(huán)圖的匿名集．此帶環(huán)圖結(jié)合環(huán)和樹的結(jié)構(gòu)特征，能夠有效地保護(hù)用戶的位置信息，而且能夠防止人數(shù)較多路徑下的單一路徑化．

因?yàn)楝F(xiàn)在的公路網(wǎng)絡(luò)可以看成是一個(gè)無向連通圖，在此方法下，帶環(huán)無向圖的匿名空間一定會(huì)構(gòu)造成功，而且本文又是用k設(shè)置的隱私度，匿名空間也一定會(huì)滿足k的隱私度，所以此方法不存在隱私泄露的情況．

4 最小匿名空間的精煉

本章節(jié)主要介紹帶環(huán)無向圖匿名集的精煉，包括以下2個(gè)部分：①最小匿名空間不足之處的原因分析，通過對(duì)最小匿名空間的精煉，防止查詢隱私的泄露；②最小匿名空間的具體精煉方法；使匿名集具有相互性，在不能保證相互性的情況下，增大匿名集之間的差異性，并且通過具體實(shí)例，分析帶環(huán)圖匿名集精煉的具體過程和優(yōu)點(diǎn)．

4．1 最小匿名空間精煉的原因分析

在第3章中，構(gòu)建了帶環(huán)無向圖的匿名空間，有效防止了單一路徑的問題．但是，帶環(huán)無向圖仍然不具有相互性，即同一匿名集內(nèi)的兩個(gè)用戶分別構(gòu)造的匿名集并不完全相同．因?yàn)椴痪哂邢嗷バ裕粽邔?duì)用戶的背景信息進(jìn)行推測，用戶的查詢隱私將會(huì)很容易被泄露．而當(dāng)差異性很小的情況下，攻擊者通過背景推測，對(duì)用戶進(jìn)行背景攻擊，同樣將會(huì)造成用戶的查詢隱私泄露．

所以，本文提出，在不能保護(hù)相互性的情況下，通過對(duì)帶環(huán)無向圖匿名集的精煉，增加用戶匿名集的差異性，即同一匿名集的兩個(gè)用戶分別構(gòu)造的匿名集的差異性增大，就可以防止攻擊者對(duì)用戶的背景攻擊，防止用戶依據(jù)道路背景推斷用戶的查詢隱私．通過精煉，不僅可以保護(hù)用戶的位置隱私，還可以保護(hù)用戶的查詢隱私．本文首次提出對(duì)匿名集的精煉，并將其應(yīng)用在公路網(wǎng)絡(luò)中．

4．2 最小匿名空間的精煉

匿名集的檢測，目的是防止用戶的查詢隱私泄露．本文的解決方案是使匿名集具有相互性或者是增大匿名集的差異性．相互性可以保證同一匿名集內(nèi)的用戶所構(gòu)造的匿名集完全相同，這樣，當(dāng)某一用戶發(fā)送查詢請(qǐng)求時(shí)，無法確定查詢是從哪一個(gè)用戶構(gòu)造的匿名集中發(fā)出，進(jìn)而無法確定哪一個(gè)用戶發(fā)送的查詢請(qǐng)求．差異性是指同一匿名集內(nèi)的用戶所構(gòu)造的匿名集存在差異性，為了不存在圖2中例子的情況，本文的解決方案是增大匿名集的差異性，即同一匿名集內(nèi)任意兩個(gè)用戶構(gòu)造的匿名集要存在至少兩個(gè)邊的差異性，可降低用戶隱私泄露的風(fēng)險(xiǎn)．

算法2 帶環(huán)圖匿名集的精煉

輸入：同一匿名集內(nèi)任意兩個(gè)用戶所構(gòu)造的匿名集輸出：優(yōu)化的匿名集1．根據(jù)輸入信息，得到兩個(gè)用戶的匿名集ASi和ASj．2．令A(yù)Sij＝ASi－ASi∩ASj，ASji＝ASj－ASi∩ASj；3．if ASij∪ASji＝?或者ASij∪ASji存在大于等于2條邊4．輸出匿名集；／／滿足相互性 或者 差異性5．else 6．if ASij為空7．向ASi加入一條權(quán)重最小邊且此邊不在匿名集ASj內(nèi)，將用戶Ui的匿名集重新與同一匿名集內(nèi)的其他用戶的匿名集進(jìn)行精煉；8．輸出匿名集；9．else 10．向ASj加入一條權(quán)重最小邊且此邊不在匿名集ASi內(nèi)，將用戶Uj的匿名集重新與同一匿名集內(nèi)的其他用戶的匿名集進(jìn)行精煉；11．輸出匿名集；

通過算法2，完成了對(duì)匿名集的檢測和優(yōu)化．如圖2所示，用戶U1構(gòu)造的匿名集為AS1＝｛（v5，v6），（v6，v3），（v3，v7），（v6，v7）｝，用戶U3構(gòu)造的匿名集為AS3＝｛（v6，v3），（v3，v7），（v6，v7）｝．此時(shí)匿名集AS1和匿名集AS3只有一條邊（v5，v6）的差異性，不滿足本文對(duì)匿名集差異性的要求，為了防止引言中例子情況的發(fā)生，所以要對(duì)匿名集AS3加入一條邊，由圖可知，添加的一條邊為（v2，v3），此時(shí)匿名集AS3＝｛（v2，v3），（v6，v3），（v3，v7），（v6，v7）｝，滿足差異性的要求，這樣攻擊者就無法通過背景攻擊得知U1的查詢隱私．

5 實(shí)驗(yàn)測試及分析

本文算法使用Java編程語言實(shí)現(xiàn)，編程環(huán)境為Eclipse 4．4．1，實(shí)驗(yàn)硬件環(huán)境為CPU：Intel i5－4590，內(nèi)存：4GB，操作系統(tǒng)平臺(tái)是Windows 7（32位）．

5．1 實(shí)驗(yàn)數(shù)據(jù)集和參數(shù)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)集采用丹麥奧爾堡公路網(wǎng)絡(luò)數(shù)據(jù)，基于奧爾堡地圖隨機(jī)產(chǎn)生了移動(dòng)用戶對(duì)象，數(shù)據(jù)集大小如表1所示．

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)Tab．1 Parameters of experimental data set

5．2 實(shí)驗(yàn)測試與分析

（1）平均查詢響應(yīng)時(shí)間，指對(duì)每一個(gè)匿名位置進(jìn)行查詢所花費(fèi)的時(shí)間．對(duì)匿名位置進(jìn)行最近鄰查詢，就是對(duì)匿名空間進(jìn)行最近鄰查詢，如圖4所示，隨著k的增加，路段數(shù)也會(huì)隨之增加，匿名空間內(nèi)的查詢敏感點(diǎn)也會(huì)隨之增加，其可以作為結(jié)果直接返回，所以查詢花費(fèi)的時(shí)間反而會(huì)隨之減?。S之查詢敏感點(diǎn)的數(shù)量增加，查詢花費(fèi)的時(shí)間會(huì)隨之增加．與網(wǎng)絡(luò)擴(kuò)張的方法相比較，從查詢?nèi)藬?shù)和查詢敏感點(diǎn)兩方面來考慮，帶環(huán)圖的查詢響應(yīng)時(shí)間都比網(wǎng)絡(luò)擴(kuò)張的查詢響應(yīng)時(shí)間?。?/p>

圖4 平均查詢響應(yīng)時(shí)間Fig．4 Average time of query

（2）平均匿名構(gòu)造時(shí)間，指對(duì)每一個(gè)用戶的精確位置進(jìn)行匿名空間構(gòu)造的時(shí)間．帶環(huán)無向圖的匿名空間的構(gòu)造，采用了寬度優(yōu)先搜索的方法，時(shí)間復(fù)雜度為O（n＋e），而在匿名集的精煉中，同一匿名集內(nèi)的每兩個(gè)匿名集進(jìn)行一次精煉，如果對(duì)其中一個(gè)匿名集進(jìn)行優(yōu)化，其余的匿名集需要重新進(jìn)行精煉，所以需要花費(fèi)較多的時(shí)間代價(jià)．

如圖5所示，隨著匿名人數(shù)的增加，匿名執(zhí)行時(shí)間也隨著增大．因?yàn)殡S著匿名人數(shù)的增加，匿名空間包含的路段也會(huì)隨之增加，導(dǎo)致了構(gòu)造帶環(huán)無向圖的匿名執(zhí)行時(shí)間增大．而且，與傳統(tǒng)的網(wǎng)絡(luò)擴(kuò)張方法相比較，帶環(huán)無向圖的匿名空間花費(fèi)的時(shí)間會(huì)比較多一些，多出的時(shí)間主要花費(fèi)在匿名集合的精煉上．為了保證安全性，同一匿名集內(nèi)的每兩個(gè)匿名集都需要進(jìn)行一次精煉，所以花費(fèi)時(shí)間較多．

圖5 平均匿名執(zhí)行時(shí)間Fig．5 Time of average anonymous space

（3）查詢成功率，指查詢結(jié)果中真實(shí)結(jié)果所占的比例．本實(shí)驗(yàn)中，通過比較匿名集返回的查詢結(jié)果與真實(shí)位置的查詢結(jié)果，可以看到查詢結(jié)果中真實(shí)結(jié)果的比例，即匿名空間的有效性．如圖6所示，隨著查詢敏感點(diǎn)和匿名集內(nèi)人數(shù)的增加，查詢成功率一直接近于1．與網(wǎng)絡(luò)擴(kuò)張的方法相比較，無論是從匿名集內(nèi)的匿名人數(shù)方面來說，還是從查詢敏感點(diǎn)的個(gè)數(shù)方面來說，帶環(huán)無向圖的查詢成功率都比其略高．可以推斷出，帶環(huán)無向圖的匿名空間的可用性非常高，可以更好地保護(hù)用戶的隱私信息．

圖6 查詢成功率Fig．6 Query success rate

（4）匿名集內(nèi)各參數(shù)，從匿名集內(nèi)的邊數(shù)，發(fā)送查詢的邊數(shù)，用戶數(shù)，發(fā)送查詢的用戶數(shù)和節(jié)點(diǎn)數(shù)五方面考慮，帶環(huán)無向圖匿名集內(nèi)的參數(shù)都比網(wǎng)絡(luò)擴(kuò)張方法匿名集內(nèi)的參數(shù)大，這與匿名集內(nèi)部帶有環(huán)的本身結(jié)構(gòu)相關(guān)．如圖7所示，因?yàn)閮?nèi)部含有環(huán)，導(dǎo)致匿名集會(huì)比較大，所以各參數(shù)會(huì)比較大．所以，帶環(huán)無向圖的匿名空間適用于十字路口較多、路段縱橫交錯(cuò)的公路網(wǎng)絡(luò)．

圖7 匿名集內(nèi)各參數(shù)Fig．7 Parameters of anonymous space

6 結(jié)束語

本文將焦點(diǎn)關(guān)注到公路網(wǎng)絡(luò)的位置服務(wù)隱私保護(hù)上，首次在路網(wǎng)中將位置隱私與查詢隱私聯(lián)系起來．結(jié)合公路網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)，本文提出了構(gòu)建帶環(huán)無向圖的方法，并對(duì)構(gòu)建的帶環(huán)無向圖進(jìn)行精煉，這是一種新的基于位置服務(wù)的隱私保護(hù)方法．在真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)檢測結(jié)果中，此基于位置服務(wù)的隱私保護(hù)方法在隱私保護(hù)和服務(wù)質(zhì)量方面皆具有高效性．

［1］CHOW C，MOKBEL M F．Enabling privacy continuous queries for revealed user locations［C］／／LNCS4605：Proc of the Int Symp on Advances in Spatial and Temporal Databases（SSTD）．Berlin：Springer－Verlag，2007：258－272．

［2］KIDO H，YANAGISAWA Y，SATOH T．An anonymous communication technique using dummies for locationbased services［C］／／Proceeding of the 2nd International Conference on Pervasive Services．Santorini，Greece：IEEE，2005：88－97．

［3］YIU M L，JENSEN C S，HUANG X G，et al．Space twist：Managing the trade－offs among location privacy，query performance，and query accuracy in mobile services［C］／／Proceeding of the 24th International Conference on Data Engineering．Cancun，Mexico：IEEE，2008：366－375．

［4］GRUTESER M，GRUNWAL D．Anonymous usage of location－based services through spatial and temporal cloaking［C］／／Proc of the Int Conference on Mobile Systems，Applications，and Services（MobiSys），New York：ACM，2003：163－168．

［5］GEDIK B G，LIU L．A customizable k－anonymity model for protecting location privacy［C］／／Proceeding of the International Conference on Distributed Computing Systems．USA：Icdcs，2005：620－629．

［6］MOKBEL M F，CHOW C Y，AREF W G．The new Casper：Query processing for location services with out compromising pravicy［C］／／Proceeding of the 32nd International Conference on VLDB．Seoul，Korea：ACM，2006：763－774．

［7］KALNIS P，GHINITA G，MOURATIDIS K．Preventing location－based identify inference in anonymous spatial queries［J］．Knowledge and Data Engineering，IEEE Transactions on．2007，19（12）：1719－1733．

［8］GHINITA G，KALNIS P，SKIADOPUSLOS S．PRIVE：Anonymous location－based queries in distributed mobile systems［C］／／Proceedings of the 16th International World Wide Web Conference．New York：ACM，2007：1－10．

［9］XIAO Z，MENG X，XU J．Quality aware privacy protection for location－based services［J］．Advances in Database：Concepts，Systems and Applications，2007，10（33）：434－446．

［10］BAMBA B，LIU L，PESTI P，WANG T．Supporting anonymous location queries in mobile environments with privacygrid［C］／／Proceeding of the 17th International World Wide Web Conference．New York：ACM，2008：237－246．

［11］CHOW C Y，MOKBEL M F，LIU X．A peer－to－peer spatial cloaking algorithm for anonymous locate－on－based services［C］／／Proceedings of the 14th annual ACM International Symposium on Advances in Geographic International Systems．New York：ACM，2006：171－178．

［12］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 International Conference on Management of Data．New York：ACM．2008：121－132．

［13］WANG T，LIU L．Privacy－aware mobile services over road networks［C］／／Proceeding of the 35th International Conference on Very Large Data Bases．Lyon，F(xiàn)rance：VLDB Endownment，2009：1042－1053．

［14］KIM K，HOSSAIN A．Hilbert－order based spatial cloaking algorithm in road network［J］．Concurrency and Computation：Practice and Experience，2013，25（1）：143－158．

［15］潘曉，郝興，猛小峰．基于位置服務(wù)中的連續(xù)查詢隱私保護(hù)研究［J］．計(jì)算機(jī)研究與發(fā)展．2010，47（1）：121－129．．

［16］薛嬌，劉向宇，楊曉春，等．一種面向公路網(wǎng)絡(luò)的位置隱私保護(hù)方法［J］．計(jì)算機(jī)學(xué)報(bào)．2011，34（5）：865－878．．

［17］李敏，秦志光．路網(wǎng)環(huán)境下位置隱私保護(hù)技術(shù)研究進(jìn)展［J］．計(jì)算機(jī)應(yīng)用研究．2014，31（9）：3－7．

［18］CHOW Y，MOKBEL F，BAO J，et al．Query－aware location anonymous for road networks［J］．Geolnformatica，2011，15（3）：571－607．

［19］MOURATIDIS K，YIU L．Anonymous query processing in road network［J］．Knowledge and Data Engineering，IEEE Trans on．2010，22（1）：2－15．

［20］PAOADIAS D，ZHANG J，MANOULIS N，et al．Query processing in spatial network data－bases［C］／／Proc of the 29th International Conference on Very Large Data Bases．New York：ACM，2003：802－813．