孫丹丹，羅永龍，范國婷，郭良敏 ，鄭孝遙

SUN Dandan1，2,LUO Yonglong1，2,FAN Guoting1，2,GUO Liangmin1，2,ZHENG Xiaoyao1，2

1.安徽師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，安徽 蕪湖 241003

2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全工程技術(shù)研究中心，安徽 蕪湖 241003

1.Department of Computer Science and Technology,Anhui Normal University,Wuhu,Anhui 241003,China

2.Engineering Technology Research Center of Network and Information Security,Anhui Normal University,Wuhu,Anhui 241003,China

1 引言

移動通信的通訊質(zhì)量不斷提高以及移動定位技術(shù)越來越精確，使得基于位置的服務(wù)（Location-Based Service，LBS）得到高速發(fā)展。移動用戶只需提供自身準(zhǔn)確、實(shí)時(shí)的位置信息給位置服務(wù)器，便可獲得相關(guān)服務(wù)，例如：查找離我最近的餐廳、休閑場所、購物場所等。然而盲目地發(fā)送位置信息給服務(wù)器必然會造成自身信息的泄露，將給用戶帶來巨大的風(fēng)險(xiǎn)。因此，位置隱私保護(hù)越來越受到人們的重視。

在位置隱私保護(hù)研究領(lǐng)域中，Gruteser等[1]首先引入k-匿名模型：通過搜索查詢用戶周邊的k-1個(gè)相互之間不能區(qū)別的用戶，用覆蓋它們的匿名區(qū)域代替查詢用戶真實(shí)的位置，即使發(fā)送的位置信息被攻擊者獲取，也不能準(zhǔn)確地從k個(gè)用戶中定位到該用戶，從而達(dá)到保護(hù)真實(shí)用戶位置隱私的目的?，F(xiàn)有很多方法都是以k-匿名為基礎(chǔ)。

多數(shù)研究通常采用第三方中心服務(wù)器架構(gòu)[2-4]，但作為核心的位置匿名服務(wù)器容易成為受攻擊的對象，且該架構(gòu)還存在如下不足：（1）需通過大量用戶的注冊使用，才能實(shí)現(xiàn)匿名區(qū)域的構(gòu)建，并且要求注冊用戶誠實(shí)可信；（2）僅支持靜態(tài)快照定位；（3）匿名服務(wù)器承擔(dān)生成匿名區(qū)和過濾結(jié)果集的工作，若大量用戶頻繁請求查詢，必然導(dǎo)致計(jì)算量急劇上升，造成系統(tǒng)瓶頸，限制了位置服務(wù)更好的發(fā)展。

針對中心服務(wù)器存在的上述不足，諸多研究者開始采用無中心服務(wù)器的結(jié)構(gòu)。文獻(xiàn)[5]首先提出一種分布式算法，但效率并不高；Chow等[6]率先提出P2P模式下使用匿名算法的思想，通過對等點(diǎn)查詢算法構(gòu)建匿名區(qū)域。用戶自組織通信形成用戶組，然后計(jì)算組內(nèi)最小邊界矩形，查詢節(jié)點(diǎn)隨機(jī)選取組內(nèi)成員作為代理，由代理代替查詢節(jié)點(diǎn)發(fā)起查詢，最后返回結(jié)果。但Chow在匿名組選擇成員時(shí)沒有考慮用戶的移動性，且往往導(dǎo)致查詢節(jié)點(diǎn)位于匿名區(qū)中心處，導(dǎo)致區(qū)域中心攻擊。文獻(xiàn)[7]對文獻(xiàn)[6]作了改進(jìn)，通過隨機(jī)擴(kuò)大匿名區(qū)來避免匿名區(qū)中心攻擊，但仍存在查詢節(jié)點(diǎn)分布不隨機(jī)等問題。Pingley等[8]提出一種不需要可信第三方的方法，該方法避免攻擊者從查詢內(nèi)容中推斷用戶的興趣和習(xí)慣。

另外，傳統(tǒng)方法由于使用匿名區(qū)域易受攻擊[9]，因此部分研究不再使用匿名區(qū)域。Yiu等[10]提出了SpaceT-wist方法，用戶使用錨點(diǎn)代替自身真實(shí)位置向服務(wù)器發(fā)起增量近鄰查詢，直至供應(yīng)空間包含需求空間為止。但該方法無法達(dá)到位置k-匿名，隱私保護(hù)度不高。Gong等[11]在文獻(xiàn)[10]基礎(chǔ)上提出了一種改進(jìn)算法，能達(dá)到k-匿名，但使用了中心服務(wù)器。黃毅等[12]提出了一種用戶協(xié)作無匿名區(qū)域的CoPrivacy方法，通過用戶協(xié)作形成匿名組，組內(nèi)用戶用該組的密度中心代替真實(shí)位置，增量地從服務(wù)器獲得近鄰查詢結(jié)果，再通過近鄰查詢結(jié)果與自身位置之間的距離計(jì)算得到精確的查詢結(jié)果。但該方法要求周邊用戶全部誠實(shí)可信，無法防止惡意攻擊者冒充用戶節(jié)點(diǎn)發(fā)起攻擊的情況。張國平等[13]使用了代理轉(zhuǎn)發(fā)查詢的方法，避免了用戶隱私在服務(wù)器端泄露，但無法避免攻擊者偽裝成代理用戶獲取用戶隱私；楊松濤等[14]提出了一種位置隱私保護(hù)模型并設(shè)計(jì)了一種基于偽隨機(jī)置換的位置隱私保護(hù)方案，實(shí)現(xiàn)了完美匿名和位置盲查詢，但無法抵抗惡意節(jié)點(diǎn)的主動攻擊；徐建等[15]提出了在動態(tài)P2P環(huán)境下基于匿名鏈的位置隱私保護(hù)算法，但不能有效抵御連續(xù)查詢攻擊[16-17]。以上基于用戶協(xié)作的方法通常無法抵御不誠實(shí)用戶的攻擊行為。近年來，還出現(xiàn)了基于私有信息檢索的位置隱私保護(hù)方法[18-20]，雖然隱私保護(hù)度較高且可避免多種攻擊，但此類方法預(yù)計(jì)算開銷和運(yùn)行時(shí)計(jì)算開銷比較大，還無法廣泛應(yīng)用。

綜合上述問題，本文提出一種對等通信輔助下抗攻擊的位置隱私保護(hù)方法（以下簡稱P2P AG算法）。該方法不使用中心服務(wù)器，未生成匿名區(qū)域，解決P2P結(jié)構(gòu)中用戶不誠實(shí)協(xié)作問題。它在k-匿名思想的基礎(chǔ)上使用構(gòu)建匿名組的方式混淆身份信息與位置信息的對應(yīng)關(guān)系，以此隱藏用戶身份與位置信息的關(guān)聯(lián)性，達(dá)到隱私保護(hù)的目的；將速度引入匿名組的構(gòu)建，并通過緩存機(jī)制增加匿名組的可重用性，以此抵御一般惡意攻擊和連續(xù)查詢攻擊，且減少系統(tǒng)開銷。

2 P2P AG位置隱私保護(hù)方法

2.1 相關(guān)定義

定義1（速度夾角θ）兩個(gè)移動節(jié)點(diǎn)的當(dāng)前速度矢量所形成的夾角（規(guī)定大小為0的速度矢量以其所在道路方向?yàn)樗俣确较颍?，如圖1所示，n1和n2是兩個(gè)移動節(jié)點(diǎn)，速度分別為V1、V2，則當(dāng)前的速度夾角θ為：

圖1 速度夾角

定義2（速度分類）指以速度為標(biāo)準(zhǔn)的分類方法，具體而言，以查詢用戶的速度方向?yàn)橹行妮S，周邊區(qū)域邊界夾角為90°的區(qū)域范圍為移動用戶的類別，速度方向與查詢用戶速度方向的夾角在這個(gè)范圍內(nèi)的節(jié)點(diǎn)均為查詢用戶的同類節(jié)點(diǎn)，如圖2所示。

圖2 速度分類

定義3（節(jié)點(diǎn)Node）在一定范圍內(nèi)的移動用戶，可用數(shù)據(jù)結(jié)構(gòu)Node(IP,Loc,vec,k,List,Lt,t0,v)加以表示，其中：

IP為節(jié)點(diǎn)唯一的身份標(biāo)識；

Loc表示當(dāng)前位置坐標(biāo)；

vec為當(dāng)前速度，由節(jié)點(diǎn)自身設(shè)定一個(gè)時(shí)間片不停更新；

k為節(jié)點(diǎn)要求的匿名度，即匿名組內(nèi)節(jié)點(diǎn)的個(gè)數(shù)，由節(jié)點(diǎn)決定，顯然k越大，匿名組內(nèi)成員個(gè)數(shù)越多，隱私保護(hù)程度越高[21]；

List為緩存內(nèi)周邊節(jié)點(diǎn)的信息表，包含周邊k-1個(gè)節(jié)點(diǎn)的信息，該信息包括序號、位置坐標(biāo)以及速度，初始為空；

Lt表示匿名組的生存時(shí)間，超過這個(gè)時(shí)間段，緩存內(nèi)的List將不能再被使用；

t0表示記錄下來的上一次構(gòu)建List表時(shí)的時(shí)間點(diǎn)；

v表示記錄下來的上一次構(gòu)建List表時(shí)的節(jié)點(diǎn)速度。

定義4（查詢節(jié)點(diǎn)）查詢節(jié)點(diǎn)q指發(fā)起位置查詢服務(wù)請求的移動節(jié)點(diǎn)。

定義5（代理節(jié)點(diǎn)）代理節(jié)點(diǎn)a指代替查詢節(jié)點(diǎn)向位置服務(wù)提供商發(fā)出查詢請求、并將返回的結(jié)果集返回給查詢節(jié)點(diǎn)的節(jié)點(diǎn)，它是查詢節(jié)點(diǎn)從產(chǎn)生的匿名組中隨機(jī)選擇出的一個(gè)節(jié)點(diǎn)。

定義6（組內(nèi)節(jié)點(diǎn)）組內(nèi)節(jié)點(diǎn)I指除查詢節(jié)點(diǎn)、代理節(jié)點(diǎn)以外的匿名組內(nèi)節(jié)點(diǎn)。

定義7（偽代理節(jié)點(diǎn)）偽代理節(jié)點(diǎn)w由于查詢節(jié)點(diǎn)q在匿名組中選中的代理節(jié)點(diǎn)a可能是其他周邊節(jié)點(diǎn)p的List表中的節(jié)點(diǎn)，查詢節(jié)點(diǎn)q無法與這類節(jié)點(diǎn)（即a）建立通信連接，所以選擇List表中含a的這個(gè)周邊節(jié)點(diǎn)p作為偽代理節(jié)點(diǎn)，由它承擔(dān)代理節(jié)點(diǎn)a的任務(wù)。

定義8（匿名組）匿名組ano_group指一個(gè)由查詢節(jié)點(diǎn)、代理節(jié)點(diǎn)（或偽代理節(jié)點(diǎn)）、若干組內(nèi)節(jié)點(diǎn)組成的節(jié)點(diǎn)集合。可形式化地表示為：

ano_group(q,a,I1,I2,…,In)，q為查詢節(jié)點(diǎn)，a為代理節(jié)點(diǎn)，Ii為第i個(gè)組內(nèi)節(jié)點(diǎn)。

定義9構(gòu)建匿名組的請求信息Req查詢節(jié)點(diǎn)廣播至周邊節(jié)點(diǎn)的信息，用以請求協(xié)助構(gòu)建匿名組，可形式化地表示為Req(RID,vec,min)，其中RID為請求序列號，是由節(jié)點(diǎn)唯一身份標(biāo)識IP和自身當(dāng)前請求信息的序號數(shù)N（指第N次請求）確定；vec為當(dāng)前查詢節(jié)點(diǎn)的速度；min為請求回復(fù)信息數(shù)，初始時(shí)為1。

定義10查詢信息Query代理節(jié)點(diǎn)（或偽代理節(jié)點(diǎn)）代替查詢節(jié)點(diǎn)向位置服務(wù)器發(fā)送的查詢信息，可形式化地表示為Query(ano_group,Q_Info)，其中Q_Info為查詢節(jié)點(diǎn)輸入的查詢內(nèi)容。

定義11（位置更新）當(dāng)緩存中的List可用時(shí)，查詢節(jié)點(diǎn)使用該List中各個(gè)節(jié)點(diǎn)的歷史位置信息和速度估算當(dāng)前的位置信息，并構(gòu)成匿名組，如圖3所示，將當(dāng)前所有節(jié)點(diǎn)的新位置坐標(biāo)近似表示為List內(nèi)歷史位置坐標(biāo)加上其速度和時(shí)間差的乘積的和，即：

圖3 位置的近似估算

其中L1(x,y)為某節(jié)點(diǎn)歷史位置坐標(biāo)，V為該節(jié)點(diǎn)的速度，t為當(dāng)前時(shí)間，t0為List創(chuàng)建時(shí)間。

定義12（結(jié)果集）結(jié)果集R指位置服務(wù)器返回給代理節(jié)點(diǎn)（或偽代理節(jié)點(diǎn)）的查詢結(jié)果，對應(yīng)ano_group內(nèi)k個(gè)節(jié)點(diǎn)的位置，即生成的k個(gè)結(jié)果。

2.2 系統(tǒng)框架

本文采用的系統(tǒng)結(jié)構(gòu)如圖4所示，由兩個(gè)部分組成，即位置服務(wù)器和移動節(jié)點(diǎn)。位置服務(wù)器是提供位置服務(wù)的服務(wù)器，要求有計(jì)算功能，可完成大量的定位、查詢并返回結(jié)果。移動節(jié)點(diǎn)是具備定位、計(jì)算功能的移動設(shè)備。系統(tǒng)主體主要包括兩個(gè)模塊：通信模塊及查詢模塊。

圖4 系統(tǒng)框架

在通信模塊中，每個(gè)移動節(jié)點(diǎn)需要支持兩種通信方式，一種用于與位置服務(wù)提供商之間的通信，包括發(fā)起查詢及獲得查詢結(jié)果，可使用2G、3G或4G網(wǎng)絡(luò)；另一種用于用戶之間進(jìn)行自組織的P2P通信，可采用無線局域網(wǎng)（WLAN），例如IEEE 802.11等方式實(shí)現(xiàn)[22-23]。顯然，無線局域網(wǎng)覆蓋范圍越廣，可搜索到的節(jié)點(diǎn)就越多，匿名成功率越高，匿名效果越好。

在查詢模塊中，移動節(jié)點(diǎn)被分為三類：查詢節(jié)點(diǎn)、組內(nèi)節(jié)點(diǎn)和代理節(jié)點(diǎn)（或偽代理節(jié)點(diǎn)）。首先，查詢節(jié)點(diǎn)q構(gòu)建匿名組，利用匿名組內(nèi)節(jié)點(diǎn)的位置來隱匿q的真實(shí)位置，以此實(shí)現(xiàn)k-匿名；然后由q從匿名組中選出代理節(jié)點(diǎn)（或偽代理節(jié)點(diǎn)）A，并將匿名組和查詢信息發(fā)給A，由A向位置服務(wù)器完成查詢；最后當(dāng)A從位置服務(wù)器獲得結(jié)果集R后，會將R返回給q，q通過R獲得自己所需要的信息。

2.3 查詢過程

移動節(jié)點(diǎn)請求一次位置服務(wù)就是一次查詢過程，包括發(fā)起請求、響應(yīng)階段、匿名處理和查詢處理4個(gè)步驟。

步驟1發(fā)起請求

當(dāng)查詢節(jié)點(diǎn)q需要請求位置服務(wù)時(shí)，首先查看自身緩存內(nèi)的List表是否可用，即檢查如下兩個(gè)條件：（1）當(dāng)前系統(tǒng)時(shí)間與上一次參與匿名的時(shí)間差t是否小于其自身規(guī)定的緩存生存時(shí)間；（2）當(dāng)前節(jié)點(diǎn)速度vec與上一次匿名時(shí)記錄下的節(jié)點(diǎn)速度v的類別是否一致（可用classify()函數(shù)進(jìn)行判斷，若返回1，表示速度一致，否則表示速度不一致），然后根據(jù)檢查結(jié)果分為以下兩種情況進(jìn)行處理：

（1）q.Lt≥t-t0and classify(q.vec,q.v)==1，此時(shí)直接調(diào)用自身List表并進(jìn)行處理（見算法1中第3～6行）。由于此時(shí)List表內(nèi)各個(gè)節(jié)點(diǎn)的新位置未知，且考慮多數(shù)節(jié)點(diǎn)是移動的，因此需要計(jì)算出各個(gè)節(jié)點(diǎn)的近似位置來代替新位置，即位置更新（見定義11）。處理完所有的節(jié)點(diǎn)后，節(jié)點(diǎn)q將自身位置信息隱匿于上述節(jié)點(diǎn)的位置信息中，構(gòu)成一個(gè)包含k個(gè)節(jié)點(diǎn)的匿名組，并直接轉(zhuǎn)向步驟4。

對于List表的生存時(shí)間，節(jié)點(diǎn)可自行規(guī)定它的大?。荷鏁r(shí)間越短，新位置估算的越精確，越符合實(shí)際情況，但可重復(fù)使用的次數(shù)越少，再次搜索及構(gòu)建的可能性增大，增加系統(tǒng)的負(fù)荷；生存時(shí)間越長，使用List表越多，可減少搜索及構(gòu)建的次數(shù)，減輕運(yùn)算負(fù)載。由于節(jié)點(diǎn)移動方向的不確定性，計(jì)算所得的新位置可能與真實(shí)位置存在少許偏差，會使真實(shí)位置模糊化，可更好地保護(hù)匿名組內(nèi)用戶的真實(shí)位置，但生存時(shí)間不可過長，否則也會導(dǎo)致與實(shí)際情況差別太大，可能使部分估算的位置信息不合理，降低隱私保護(hù)度[24]。

（2）q.Lt＜t-t0or classify(q.vec,q.v)!=1，此時(shí)需要重新構(gòu)建匿名組（見算法1中第5～11行）。首先，節(jié)點(diǎn)q清空List、初始化構(gòu)建請求信息Req(RID,vec,min)，并廣播Req，然后等待周邊節(jié)點(diǎn)的回應(yīng)，接收到Req的合適節(jié)點(diǎn)最終將返回響應(yīng)，（響應(yīng)階段處理過程具體見步驟2），搜索過程結(jié)束。

算法1描述了查詢節(jié)點(diǎn)請求構(gòu)建匿名組時(shí)的初始處理過程，具體如下：

算法1 Initial processing of query node

步驟2響應(yīng)階段

當(dāng)周邊節(jié)點(diǎn) p收到查詢節(jié)點(diǎn)q發(fā)送的構(gòu)建請求消息時(shí)，它檢查此請求是否為新的請求，若不是新請求，則拋棄該消息，否則，繼續(xù)檢查速度類別，若q的類別與 p的類別不一致，則拋棄，否則就檢查q.Req.min的值，根據(jù)q.Req.min的值來返回響應(yīng)結(jié)果（一般情況下，節(jié)點(diǎn) p首先是為了滿足自身查詢需求而開啟位置服務(wù)，因此p.List通常不會為空），響應(yīng)結(jié)果用于查詢節(jié)點(diǎn)構(gòu)建匿名組：

當(dāng)q.Req.min==1時(shí)，節(jié)點(diǎn) p將隨機(jī)抽取 p.List內(nèi)的一條節(jié)點(diǎn)信息，即 p.List內(nèi)某個(gè)節(jié)點(diǎn) p′的速度及位置信息（見算法2第4～6行），然后返回給q；

當(dāng)q.Req.min!=1，則從 p.List中隨機(jī)抽取 Minist(number(p.List),q.Req.min)（表示 p.List中的節(jié)點(diǎn)數(shù)值和q.Req.min值相比較，返回最小值）條節(jié)點(diǎn)信息，返回給q（見算法2第7～14行）。算法2描述了在構(gòu)建匿名組時(shí)，構(gòu)建請求信息接收端的處理過程，具體如下：

算法2 Response of receiver

步驟3匿名處理

當(dāng)返回的節(jié)點(diǎn)信息總數(shù)不小于k-1時(shí)，查詢節(jié)點(diǎn)q便可從中隨機(jī)挑選k-1個(gè)節(jié)點(diǎn)作為匿名組的成員，并將自身信息隱匿其中，形成一個(gè)有k個(gè)節(jié)點(diǎn)的匿名組，并存入List中，其中保存了所有組內(nèi)節(jié)點(diǎn)的位置信息和速度。若返回響應(yīng)的節(jié)點(diǎn)總數(shù)小于k-1，說明一次單跳搜索無法滿足查詢節(jié)點(diǎn)q的匿名需求。此時(shí)節(jié)點(diǎn)q將修改Req中的min值：

其中，q.k為查詢節(jié)點(diǎn)q的匿名度，k'為首次請求返回的節(jié)點(diǎn)個(gè)數(shù)，并再次向周邊節(jié)點(diǎn)發(fā)出構(gòu)建請求，以此獲得更多周邊節(jié)點(diǎn)List表中的節(jié)點(diǎn)信息來完成此次匿名。若再次返回的節(jié)點(diǎn)信息數(shù)目仍不足k-1，說明當(dāng)前周邊節(jié)點(diǎn)過少，構(gòu)建匿名組失敗，這時(shí)節(jié)點(diǎn)q需要等待一段時(shí)間，待網(wǎng)絡(luò)覆蓋范圍內(nèi)的節(jié)點(diǎn)數(shù)增多時(shí)再重新構(gòu)建。為防止惡意攻擊，查詢節(jié)點(diǎn)q將List做了如下處理：表內(nèi)不使用移動節(jié)點(diǎn)的真實(shí)IP，而是使用編號用以標(biāo)識區(qū)分，這樣即使該表被惡意攻擊者截獲，由于表內(nèi)采用的編號標(biāo)識使其無法準(zhǔn)確定位到某個(gè)用戶，為保持通信，查詢節(jié)點(diǎn)q還需保留組內(nèi)節(jié)點(diǎn)的通信地址與編號的對應(yīng)關(guān)系。構(gòu)建ano_group時(shí)，為了防止將q暴露于表頭或表尾，節(jié)點(diǎn)的順序是隨機(jī)打亂的，如表1所示。

表1 構(gòu)建完成的匿名組

算法3描述了構(gòu)建過程中節(jié)點(diǎn)q的匿名處理過程：

算法3 Anonymity Processing

步驟4查詢處理

經(jīng)過步驟3后，ano_group已經(jīng)構(gòu)成。為防止被惡意攻擊者追蹤定位，查詢節(jié)點(diǎn)不直接發(fā)起查詢，而是在ano_group內(nèi)隨機(jī)挑選一個(gè)節(jié)點(diǎn)作代理節(jié)點(diǎn)，由代理節(jié)點(diǎn)實(shí)現(xiàn)轉(zhuǎn)發(fā)查詢。不失一般性，查詢節(jié)點(diǎn)自身也有可能會被選中，因而，在排除自身節(jié)點(diǎn)的集合中隨機(jī)選擇代理節(jié)點(diǎn)。另外，由于被選中的代理節(jié)點(diǎn)可能是周邊節(jié)點(diǎn)pi(i=1,2,…,n)中List表中存儲的節(jié)點(diǎn)，而它可能沒有與查詢節(jié)點(diǎn)q建立通信連接，此時(shí)，依據(jù)定義7，用偽代理節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢請求，也就是說偽代理節(jié)點(diǎn)可能未被歸入匿名組內(nèi)，但是充當(dāng)了代理節(jié)點(diǎn)的角色。查詢節(jié)點(diǎn)將ano_group和Q_Info發(fā)送給代理節(jié)點(diǎn)（或偽代理節(jié)點(diǎn)）a，a再將已被匿名化的查詢信息發(fā)送給位置服務(wù)器。位置服務(wù)器接收到查詢信息后經(jīng)過計(jì)算返回一系列結(jié)果集。代理節(jié)點(diǎn)（或偽代理節(jié)點(diǎn)）接收到結(jié)果集后將其轉(zhuǎn)發(fā)給查詢節(jié)點(diǎn)，查詢節(jié)點(diǎn)篩選出所需要的結(jié)果，整個(gè)查詢過程結(jié)束。由上文可知，不論ano_group是通過步驟1直接獲得、還是經(jīng)過步驟2及步驟3重新構(gòu)建的，查詢用戶得到的都是準(zhǔn)確的結(jié)果。

2.4 算法復(fù)雜度及服務(wù)質(zhì)量分析

移動客戶端計(jì)算能力有限，因此算法不能過于復(fù)雜。而直接在查詢端生成一組假位置的方法將導(dǎo)致大量的計(jì)算開銷，且生成的假位置可能受語義攻擊[24]，因此利用多個(gè)真實(shí)的接收端協(xié)作完成匿名，且使用的是其List表內(nèi)更接近真實(shí)情況的位置信息，以避免語義攻擊帶來的危害。在整個(gè)過程中，發(fā)起查詢的節(jié)點(diǎn)需要選擇多個(gè)其他節(jié)點(diǎn)信息以構(gòu)成包含k個(gè)成員的匿名組，因此查詢端的時(shí)間復(fù)雜度為O()k，k為查詢端指定的匿名度；其他節(jié)點(diǎn)接收消息，經(jīng)選擇后發(fā)出消息，因此接收端的時(shí)間復(fù)雜度為O()k*，k*為接收端指定的匿名度。

服務(wù)質(zhì)量方面，本文使用隱匿的位置信息向位置服務(wù)器發(fā)起查詢。在緩存中已有的List表不可用時(shí)，節(jié)點(diǎn)是使用當(dāng)前真實(shí)位置進(jìn)行構(gòu)建匿名組并查詢，查詢結(jié)果是精確的；當(dāng)緩存中已有的List表可用時(shí)，將查詢節(jié)點(diǎn)的真實(shí)位置混在一系列虛假位置中進(jìn)行查詢，查詢結(jié)果也是精確的，因此，在保護(hù)用戶位置隱私的情況下并未犧牲服務(wù)質(zhì)量。

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)環(huán)境

模擬實(shí)驗(yàn)采用Java實(shí)現(xiàn)，在Q9500 2.83 GHz處理器、2 GB內(nèi)存的Windows 7平臺上運(yùn)行。移動節(jié)點(diǎn)的位置模擬數(shù)據(jù)由移動數(shù)據(jù)管理研究業(yè)界廣泛使用的Thomas Brinkhoff路網(wǎng)數(shù)據(jù)生成器[25]生成。取城市Oldenburg的交通路網(wǎng)中一塊1 000 m×1 000 m的空間作為模擬器的輸入，如圖5所示，從而生成模擬的移動節(jié)點(diǎn)數(shù)據(jù)集。

圖5 城市Oldenburg交通路網(wǎng)及節(jié)點(diǎn)的仿真

實(shí)驗(yàn)中假設(shè)每個(gè)移動節(jié)點(diǎn)在組內(nèi)使用半雙工無線通道進(jìn)行通信，帶寬為2 Mb/s。當(dāng)某節(jié)點(diǎn)發(fā)出通信請求時(shí)，需要等待其他成員的回應(yīng)，若響應(yīng)節(jié)點(diǎn)數(shù)不足，它將再次發(fā)出請求，若多次請求無果且超過節(jié)點(diǎn)可容忍的等待時(shí)間，則該節(jié)點(diǎn)請求失敗。首先使用該模擬器產(chǎn)生1 000個(gè)不同節(jié)點(diǎn)的運(yùn)動信息，模擬器各項(xiàng)參數(shù)設(shè)置如表2所示，為列出的表示為默認(rèn)值。其中，obj./begin（M）為初始狀態(tài)下產(chǎn)生的運(yùn)動對象數(shù)，obj./begin（E）則為外部對象數(shù)；obj./time（M）為每個(gè)時(shí)間戳下產(chǎn)生的移動對象數(shù)，obj./time（E）則為外部對象數(shù)；classe（sM）為移動對象類的個(gè)數(shù)，classe（sE）則為外部對象類的個(gè)數(shù)。

表2 參數(shù)設(shè)置

3.2 結(jié)果分析

規(guī)定N為當(dāng)前無線網(wǎng)覆蓋范圍內(nèi)的節(jié)點(diǎn)總數(shù)，n為請求查詢的節(jié)點(diǎn)數(shù)目，即查詢節(jié)點(diǎn)數(shù)，k為節(jié)點(diǎn)要求的匿名度，緩存生存時(shí)間設(shè)置為30 s。接下來將從算法性能和安全性兩個(gè)方面來評估。

3.2.1 算法性能

本文從匿名成功率、平均響應(yīng)時(shí)間及消息數(shù)量三方面分析算法性能，并與文獻(xiàn)[12]的CoPrivacy方法做了一定比較。

（1）匿名成功率

匿名成功率是指在查詢過程中實(shí)現(xiàn)成功匿名的節(jié)點(diǎn)在發(fā)起查詢的節(jié)點(diǎn)中所占的比例，計(jì)算公式為：匿名成功率=匿名成功節(jié)點(diǎn)數(shù)/查詢節(jié)點(diǎn)數(shù)。

圖6是節(jié)點(diǎn)總數(shù)相同N=1 000，n和k值不同的情況下P2P AG方法的匿名成功率。隨機(jī)選擇50～200個(gè)節(jié)點(diǎn)作為查詢節(jié)點(diǎn)，并在隨機(jī)的時(shí)間戳下發(fā)起查詢。查詢分為四類：k=10、20、30和40，每類執(zhí)行100次后記錄匿名成功的節(jié)點(diǎn)數(shù)，計(jì)算出平均成功率。如圖所示，當(dāng)k和n越小，匿名成功率越高且越穩(wěn)定，最佳情況幾乎達(dá)到100%，當(dāng)k和n增大，匿名成功率將有所降低，但整體成功率仍較高。

圖6 基于不同n和k值的匿名成功率（N=1 000）

圖7為k和n相同、N不同時(shí)，P2P AG方法與CoPrivacy方法匿名成功率的對比結(jié)果。分別產(chǎn)生50～400個(gè)節(jié)點(diǎn)，隨機(jī)定義20個(gè)節(jié)點(diǎn)發(fā)起k=10的查詢，各自模擬10次查詢。從圖中可看出，前者在節(jié)點(diǎn)總數(shù)較少時(shí)，匿名成功率較低，這是由于此時(shí)符合構(gòu)建匿名組條件的節(jié)點(diǎn)數(shù)較少。節(jié)點(diǎn)數(shù)越多，匿名成功率就越高，當(dāng)N=400時(shí)，已基本達(dá)到100%。對于后者，匿名成功率也是隨節(jié)點(diǎn)總數(shù)的增加而增加，但并不是很穩(wěn)定，當(dāng)請求查詢的次數(shù)增加，匿名成功率會降低，特別是節(jié)點(diǎn)總數(shù)較少時(shí)，下降是明顯的，這是因?yàn)椴樵兇螖?shù)增多時(shí)周邊可用的節(jié)點(diǎn)會越來越少。而P2P AG方法一直保持著波動不大的匿名成功率，因此比較穩(wěn)定，且在多數(shù)節(jié)點(diǎn)同時(shí)進(jìn)行查詢時(shí)匿名效果較好，符合實(shí)際需求。

（2）平均響應(yīng)時(shí)間及消息數(shù)量

圖8是P2P AG方法關(guān)于平均響應(yīng)時(shí)間及消息數(shù)量與CoPrivacy方法對比的結(jié)果。實(shí)驗(yàn)中，設(shè)n=20，k=10，節(jié)點(diǎn)總數(shù)N=50～400。如圖8（a）所示，隨著節(jié)點(diǎn)總數(shù)增加，CoPrivacy方法的系統(tǒng)響應(yīng)時(shí)間出現(xiàn)較大增長，而P2P AG方法雖有所增加，但較平緩，未出現(xiàn)很大幅度的增長，說明系統(tǒng)是穩(wěn)定的。從圖8（b）可以看出，隨著節(jié)點(diǎn)總數(shù)增加，兩者的平均消息數(shù)量會逐漸降低。對CoPrivacy方法而言，節(jié)點(diǎn)總數(shù)增加使其不需要通過多跳搜索其他節(jié)點(diǎn)；而對于P2P AG方法，隨著節(jié)點(diǎn)總數(shù)增加，匿名成功率也會增加，不需要多次廣播構(gòu)建請求消息，且由于緩存的使用，會減少消息數(shù)量。但CoPrivacy方法需要搜索節(jié)點(diǎn)且實(shí)現(xiàn)增量近鄰查詢，導(dǎo)致大量的通信，因此平均消息數(shù)量的總趨勢高于P2P AG方法。

3.2.2 安全性分析

本文主要分析一般惡意攻擊和連續(xù)查詢攻擊的情況。攻擊者感興趣的信息是節(jié)點(diǎn)與其位置信息的對應(yīng)關(guān)系，即確定某一個(gè)節(jié)點(diǎn)及其所在的位置，因此需要對節(jié)點(diǎn)與位置信息之間的關(guān)聯(lián)關(guān)系進(jìn)行保護(hù)。

（1）一般惡意攻擊

主要考慮兩種一般惡意攻擊：一是惡意節(jié)點(diǎn)是匿名組內(nèi)節(jié)點(diǎn)，獲取匿名組信息；二是竊聽者監(jiān)聽匿名組內(nèi)的通信或代理節(jié)點(diǎn)與LBS服務(wù)器之間的通信。

由于構(gòu)建匿名組時(shí)組內(nèi)節(jié)點(diǎn)和代理節(jié)點(diǎn)的選擇是隨機(jī)的，即使存在惡意節(jié)點(diǎn)，其被選中的可能性也很小。若整個(gè)區(qū)域內(nèi)的響應(yīng)節(jié)點(diǎn)數(shù)為p，匿名度為k(k＜p)，惡意節(jié)點(diǎn)數(shù)為c（一般情況下，參與構(gòu)建的用戶都是誠實(shí)或半誠實(shí)的，因此可假設(shè)c?p），則整個(gè)過程中查詢節(jié)點(diǎn)選中惡意節(jié)點(diǎn)的概率為：

圖7 不同節(jié)點(diǎn)總數(shù)的匿名成功率（n=20，k=10）

圖8 平均響應(yīng)時(shí)間及消息數(shù)量（n=20，k=10）

當(dāng)c遠(yuǎn)小于 p時(shí)，這個(gè)概率值將很小。此外，即使惡意節(jié)點(diǎn)是組內(nèi)節(jié)點(diǎn)，它只能獲取查詢節(jié)點(diǎn)的速度類別，并不能獲取其位置信息。只有惡意節(jié)點(diǎn)是代理節(jié)點(diǎn)時(shí)，才會獲取一張包括組內(nèi)節(jié)點(diǎn)信息的ano_group。但是，ano_group中的用戶名是使用編號進(jìn)行隱匿的，即使惡意節(jié)點(diǎn)獲得了ano_group，只能得到一系列位置信息和速度信息，是無法將位置信息與某個(gè)確定的用戶關(guān)聯(lián)起來的，即保護(hù)了用戶與其位置信息的關(guān)聯(lián)關(guān)系；另一方面，代理節(jié)點(diǎn)充當(dāng)?shù)氖遣樵児?jié)點(diǎn)與位置服務(wù)器間的中間件，且每次請求查詢時(shí)都會隨機(jī)選出一個(gè)用來實(shí)現(xiàn)轉(zhuǎn)發(fā)查詢，即便知曉誰是查詢節(jié)點(diǎn)，但這是在查詢節(jié)點(diǎn)進(jìn)行搜索周邊節(jié)點(diǎn)時(shí)就已經(jīng)知曉的，而搜索過程中查詢節(jié)點(diǎn)廣播的Req只包括RID、vec和min，并沒有確切的位置信息，因此查詢節(jié)點(diǎn)的位置信息并未暴露。

若惡意節(jié)點(diǎn)偽裝成查詢節(jié)點(diǎn)期望獲得大量其他節(jié)點(diǎn)的信息。然而在算法2中，其他節(jié)點(diǎn)返回的響應(yīng)信息是其List內(nèi)的某一條節(jié)點(diǎn)信息，即并不是自身的信息，即使惡意節(jié)點(diǎn)偽裝成查詢節(jié)點(diǎn)獲取了這些信息，也無法準(zhǔn)確判斷與某個(gè)節(jié)點(diǎn)的對應(yīng)關(guān)系。同理，若竊聽者截獲到查詢節(jié)點(diǎn)發(fā)送給代理節(jié)點(diǎn)的ano_group或代理節(jié)點(diǎn)發(fā)送至LBS服務(wù)器的查詢信息，也是無法將位置信息與確切的用戶IP關(guān)聯(lián)起來，保護(hù)了匿名組內(nèi)節(jié)點(diǎn)的隱私。

通過抵御以上兩類惡意攻擊，P2P AG算法便可避免受到傳統(tǒng)k-匿名方法中的多數(shù)攻擊[26]。例如對于區(qū)域密度攻擊：當(dāng)查詢節(jié)點(diǎn)周邊的用戶較多時(shí)構(gòu)建的匿名區(qū)域較小，導(dǎo)致直接縮小查詢用戶的真實(shí)位置范圍，增加了位置暴露的風(fēng)險(xiǎn)。而P2P AG算法構(gòu)建的匿名組內(nèi)的位置信息是真實(shí)信息和虛假信息的混合，攻擊者并不能有效定位到查詢用戶的真實(shí)位置范圍，因此可較好地抵御區(qū)域密度攻擊。

（2）連續(xù)查詢攻擊

此類攻擊主要由查詢節(jié)點(diǎn)在連續(xù)查詢周期內(nèi)匿名集合的頻繁變化引起。一種簡單的解決方案就是保持查詢節(jié)點(diǎn)的匿名集合盡可能的不變[27]，然而這會使匿名區(qū)域隨集合內(nèi)成員的分散移動而逐漸增大或減小。若匿名區(qū)域過大，則降低了服務(wù)質(zhì)量；若匿名區(qū)域過小，則較容易泄露隱私。本文舍棄匿名區(qū)域，并使用緩存，使匿名組盡量保持不變。假設(shè)緩存中的List生存時(shí)間較長，連續(xù)的幾次查詢中都將使用同一組節(jié)點(diǎn)構(gòu)成的匿名組，使得攻擊者無法確定真實(shí)的查詢節(jié)點(diǎn)。為盡可能保證節(jié)點(diǎn)不會出現(xiàn)大量的添加、刪除且保持組內(nèi)通信順暢，將速度分類，組內(nèi)節(jié)點(diǎn)屬于同一個(gè)類。由于節(jié)點(diǎn)沿著道路移動，短時(shí)間內(nèi)發(fā)生類別變化的可能性不大，ano_group將保持不變，當(dāng)發(fā)起連續(xù)查詢時(shí)，即使攻擊者截獲了ano_group，仍無法準(zhǔn)確確定查詢節(jié)點(diǎn)及其位置信息。

圖9說明了保持匿名組不變的可行性。實(shí)驗(yàn)中記錄了節(jié)點(diǎn)總數(shù)N=1 000時(shí)在不同的情況下使用緩存所占成功匿名節(jié)點(diǎn)數(shù)的比例。分別隨機(jī)使100、200、300個(gè)節(jié)點(diǎn)發(fā)出匿名度k=20～100的查詢?？梢钥闯觯寒?dāng)查詢節(jié)點(diǎn)數(shù)較多或要求匿名度較大時(shí)，使用緩存的可能性較大，因此占比例較大，符合實(shí)際應(yīng)用，可有效滿足隱私需求且節(jié)省系統(tǒng)開銷。

圖9 緩存使用率（N=1 000）

由于多數(shù)位置隱私保護(hù)方法的研究重點(diǎn)各異，因此本文與用戶協(xié)作的位置隱私保護(hù)經(jīng)典算法P2P Spatial Cloaking[6]（簡稱P2P SC）做比較。若在多個(gè)匿名度為k的匿名集合內(nèi)連續(xù)出現(xiàn)的節(jié)點(diǎn)個(gè)數(shù)為m，則查詢節(jié)點(diǎn)被暴露的概率為：

對于P2P SC算法，當(dāng)某個(gè)或某幾個(gè)成員在多個(gè)匿名區(qū)域內(nèi)連續(xù)出現(xiàn)，則說明查詢節(jié)點(diǎn)必是該成員或存在于這多個(gè)成員中，使算法無法達(dá)到位置k-匿名，增大暴露的可能性，即受到連續(xù)查詢攻擊的威脅。而P2P AG利用緩存，盡可能使連續(xù)構(gòu)建的匿名組不變，降低了暴露的可能性。實(shí)驗(yàn)使40個(gè)節(jié)點(diǎn)在連續(xù)的多個(gè)時(shí)間戳t內(nèi)發(fā)出查詢請求，匿名度k=10，匿名組生存時(shí)間不小于1個(gè)時(shí)間戳，記錄節(jié)點(diǎn)暴露率，并計(jì)算平均值。結(jié)果如圖10所示，P2P SC的查詢節(jié)點(diǎn)暴露率基本高于P2P AG，且前者隨連續(xù)時(shí)間戳的增加而大幅增長?？紤]到P2P AG會在節(jié)點(diǎn)速度類別發(fā)生改變時(shí)構(gòu)建新的匿名組，為了模糊新舊匿名組間的聯(lián)系，算法將組內(nèi)的用戶名用編號代替，且隨機(jī)產(chǎn)生順序，使攻擊者無法識別出兩次查詢是否為同一個(gè)查詢節(jié)點(diǎn)發(fā)出，即一次構(gòu)建，多次使用，再次構(gòu)建，全組更名，以更好地抵御連續(xù)查詢攻擊。因此P2P AG方法在連續(xù)查詢時(shí)的安全性優(yōu)于P2P SC方法。

圖10 安全性比較（N=1 000，n=40，k=10）

4 結(jié)束語

大部分傳統(tǒng)的位置隱私保護(hù)方法是基于第三方可信中心服務(wù)器結(jié)構(gòu)而建立的，因此必然導(dǎo)致中心服務(wù)器成為整個(gè)系統(tǒng)性能的瓶頸。本文提出一種在對等通信輔助下可抗攻擊的位置隱私保護(hù)方法，該方法通過多用戶協(xié)作實(shí)現(xiàn)位置k-匿名，未生成匿名區(qū)域，避免傳統(tǒng)k-匿名模型常見的攻擊?？紤]用戶的移動性，引入速度作為構(gòu)建匿名組的要素之一，組內(nèi)成員保持模糊的連通性，以此解決組內(nèi)成員不可信問題，并可抵御一般惡意攻擊。同時(shí)，加入了緩存機(jī)制，增加匿名組的可重用性，使匿名組在一段時(shí)間內(nèi)保持不變，以此抵御連續(xù)查詢攻擊，并可減少系統(tǒng)開銷。該方法保證了用戶的隱私，在降低系統(tǒng)開銷的基礎(chǔ)上滿足了匿名需求，并能夠較好地抵御一般性惡意攻擊和連續(xù)查詢攻擊。由于用戶協(xié)作的模式需要建立在用戶相對集中且用戶數(shù)多的基礎(chǔ)上，當(dāng)周圍可搜索到的用戶較少或可協(xié)助進(jìn)行查詢的用戶較少時(shí)，該方法的實(shí)現(xiàn)將可能會受到一定影響。因此，該方法較適用于用戶相對集中且足夠多的密集區(qū)域，未來的工作可以在松散用戶或少量用戶上展開。

參考文獻(xiàn)：

[1]Gruteser M，Grunwald D.Anonymous usage of locationbased services through spatial and temporal cloaking[C]//Proceedings of the 1st International Conference on Mobile Systems，Applications and Services，2003：31-42.

[2]Gedik B，Liu L.Protecting location privacy with personalized k-anonymity：Architecture and algorithms[J].IEEE Transactions on Mobile Computing，2008，7（1）：1-18.

[3]Xu T，Cai Y.Feeling-based location privacy protection for location-based services[C]//ACM Conference on Computer and Communications Security（CCS 2009），Chicago，Illinois，USA，November 2009：348-357.

[4]Wang Y，Xu D，He X，et al.L2P2：Location-aware location privacy protection for location-based services[J].Proceedings-IEEE INFOCOM，2012，131（5）：1996-2004.

[5]Kido H，Yanagisawa Y，Satoh T.An anonymous communication technique using dummies for location-based services[C]//ProceedingsInternationalConferenceon Pervasive Services，2005（ICPS’05），2005：88-97.

[6]Chow C Y.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]//Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems，2006：171-178.

[7]Chow C Y，Mokbel M F，Liu X.Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J].GeoInformatica，2011，15（2）：351-380.

[8]Pingley A，Zhang N，F(xiàn)u X，et al.Protection of query privacy for continuous location based services[C]//IEEE INFOCOM，2011：1710-1718.

[9]Wernke M，Skvortsov P，Dürr F，et al.A classification of location privacy attacks and approaches[J].Personal and Ubiquitous Computing，2014，18（1）：163-175.

[10]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]//IEEE International Conference on Data Engineering，2008：366-375.

[11]Gong Z，Sun G Z，Xie X.Protecting privacy in locationbased services using K-anonymity without cloaked region[C]//2010 Eleventh International Conference on Mobile Data Management（MDM），2010：366-371.

[12]黃毅，霍崢，孟小峰.CoPrivacy：一種用戶協(xié)作無匿名區(qū)域的位置隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1976-1985.

[13]張國平，樊興，唐明，等.面向LBS應(yīng)用的隱私保護(hù)模型[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2010（9）：45-49.

[14]楊松濤，馬春光，周長利.面向LBS的隱私保護(hù)模型及方案[J].通信學(xué)報(bào)，2014，35（8）：116-124.

[15]徐建，黃孝喜，郭鳴，等.動態(tài)P2P網(wǎng)絡(luò)中基于匿名鏈的位置隱私保護(hù)[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2012，46（4）：712-718.

[16]Dewri R，Ray I，Whitley D.Query m-invariance：Preventing query disclosures in continuous location-based services[C]//2010 Eleventh International Conference on Mobile Data Management（MDM），2010：95-104.

[17]Chen X，Pang J.Exploring dependency for query privacy protection in location-based services[C]//Proceedings of the Third ACM Conference on Data and Application Security and Privacy，2013：37-48.

[18]Ghinita G，Kalnis P，Khoshgozaran A，et al.Private queries in location based services：Anonymizers are not necessary[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，2008：121-132.

[19]Papadopoulos S，Bakiras S，Papadias D.Nearest neighbor search with strong location privacy[J].PVLDB，2010，3（1）：619-629.

[20]Khoshgozaran A，Shahabi C，Shirani-Mehr H.Location privacy：Going beyond K-anonymity，cloaking and anonymizers[J].Knowledge and Information Systems，2011，26（3）：435-465.

[21]張建明，趙玉娟，江浩斌，等.車輛自組網(wǎng)的位置隱私保護(hù)技術(shù)研究[J].通信學(xué)報(bào)，2012（8）：180-189.

[22]Chow C Y，Leong H V，Chan A T S.Distributed groupbased cooperative caching in a mobile broadcast environment[C]//Proceedings of the 6th International Conference on Mobile Data Management，2005：97-106.

[23]Papadopouli M，Schulzrinne H.Effects of power conservation，wireless coverage and cooperation on data dissemination among mobile devices[C]//Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking&Computing，2001：117-127.

[24]Brinkhoff T.A framework for generating network-based moving objects[J].GeoInformatica，2002，6（2）：153-180.

[25]Damiani M L，Bertino E，Silvestri C.The PROBE framework for the personalized cloaking of private locations[J].Transactions on Data Privacy，2010，3（2）：123-148.

[26]司超.基于Casper的位置隱私保護(hù)模型與算法研究[D].廣州：華南理工大學(xué)，2012.

[27]Chow C Y，Mokbel M F.Enabling private continuous queries for revealed user locations[M]//Advances in Spatial and Temporal Databases.Berlin Heidelberg：Springer，2007：258-275.