動(dòng)態(tài)P2P網(wǎng)絡(luò)中基于扇形區(qū)域的位置隱私保護(hù)

賈宗璞 劉 雯

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)

動(dòng)態(tài)P2P網(wǎng)絡(luò)中基于扇形區(qū)域的位置隱私保護(hù)

賈宗璞 劉 雯

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 河南 焦作 454000)

目前，已有的動(dòng)態(tài)P2P網(wǎng)絡(luò)環(huán)境中位置隱私保護(hù)的方法容易使相互協(xié)作的用戶之間的位置過于集中，空間覆蓋域較小，抗中心攻擊能力較弱。針對這個(gè)問題，提出一種基于扇形區(qū)域的動(dòng)態(tài)P2P位置隱私保護(hù)方法。通過移動(dòng)用戶之間的相互協(xié)作構(gòu)建一條匿名鏈來轉(zhuǎn)發(fā)查詢信息，完成精確查詢的同時(shí)在匿名鏈中隱藏了查詢用戶的真實(shí)位置。在匿名鏈建立的過程中，利用扇形區(qū)域限定匿名鏈的方向，同時(shí)考慮節(jié)點(diǎn)之間的連接穩(wěn)定性，保證了匿名鏈的空間覆蓋域及穩(wěn)定性，從而提高了算法的匿名度及抗中心攻擊能力。實(shí)驗(yàn)結(jié)果表明該算法在不同用戶密度情況下，匿名性能及計(jì)算能耗均能取得較好的結(jié)果。

位置隱私 P2P網(wǎng)絡(luò) 扇形區(qū)域 空間覆蓋域

0 引 言

近年來，隨著無線通信技術(shù)和空間定位技術(shù)的不斷發(fā)展，開拓了一個(gè)新的研究領(lǐng)域——基于位置的服務(wù)LBS(Location Based Services)?；谖恢梅?wù)的廣泛應(yīng)用在給人們的生活帶來極大便利的同時(shí)，也給個(gè)人的位置隱私帶來了嚴(yán)重威脅。例如，查找附近最近的一個(gè)加油站，怎樣能快捷地到達(dá)目的地，當(dāng)用戶發(fā)送當(dāng)前位置給服務(wù)提供方時(shí)，不可避免地會(huì)造成用戶位置信息泄露[1]。隨著用戶對個(gè)體信息隱私安全的日益關(guān)注，如何在保護(hù)用戶位置隱私安全的前提下提供基于位置的查詢服務(wù)成為研究的熱點(diǎn)[2-4]。

從目前已經(jīng)取得的研究成果來看，位置匿名系統(tǒng)大致可分為三種結(jié)構(gòu)：中心服務(wù)器結(jié)構(gòu)、獨(dú)立結(jié)構(gòu)和分布式點(diǎn)對點(diǎn)結(jié)構(gòu)[5-7]。

中心服務(wù)器結(jié)構(gòu)引入可信第三方——匿名服務(wù)器來完成匿名過程，但匿名服務(wù)器易成為系統(tǒng)瓶頸。高峰期時(shí)，需要處理大量的用戶數(shù)據(jù)，這對匿名服務(wù)器來說是一個(gè)極大的負(fù)擔(dān)。此外，匿名服務(wù)器也容易成為攻擊者攻擊的目標(biāo)，一旦匿名服務(wù)器被攻破，所有用戶的查詢信息和位置信息就會(huì)被泄露。

獨(dú)立結(jié)構(gòu)需要用戶端自行完成匿名區(qū)域的組建和匿名過程的計(jì)算，此外所有的通信都是由用戶端和服務(wù)器端完成的。這種結(jié)構(gòu)對移動(dòng)設(shè)備的要求比較高，要求移動(dòng)設(shè)備具有充足的存儲(chǔ)空間和較強(qiáng)的計(jì)算能力，且終端負(fù)擔(dān)較重。

分布式點(diǎn)對點(diǎn)體系結(jié)構(gòu)，即指某個(gè)區(qū)域中的移動(dòng)用戶通過自行組織形成局部匿名網(wǎng)絡(luò)，互相幫助完成匿名保護(hù)工作，與服務(wù)器端進(jìn)行 LBS 交互。節(jié)點(diǎn)相互平等，徹底解決了單點(diǎn)攻擊的威脅，提高了匿名的效率，也能夠享受較好的位置服務(wù)。

本文采用分布式點(diǎn)對點(diǎn)體系結(jié)構(gòu)，并提出一種基于扇形區(qū)域選擇下一跳節(jié)點(diǎn)的SASTNHN(Sector area select the next hop node)算法，其優(yōu)勢在于：1) 限制匿名鏈的方向。移動(dòng)用戶在尋找下一跳節(jié)點(diǎn)時(shí)，以自身位置為圓心，以自身和上一跳節(jié)點(diǎn)的連線為中心軸，根據(jù)相鄰節(jié)點(diǎn)密度確定扇形的圓心角大小，以最大通信距離為半徑，在背離上一跳節(jié)點(diǎn)的方向上確定一個(gè)扇形區(qū)域。2) 最小距離限制。在該扇形區(qū)域內(nèi)選取下一跳節(jié)點(diǎn)時(shí)，下一跳節(jié)點(diǎn)的位置和上一跳節(jié)點(diǎn)的位置之間的距離要大于設(shè)定的最小距離。通過以上兩個(gè)方面確保匿名鏈中節(jié)點(diǎn)位置分散，增大匿名鏈的空間覆蓋域，減小查詢節(jié)點(diǎn)被攻擊者攻擊成功的概率。

1 相關(guān)工作

在位置匿名處理中使用最多的模型是位置k-匿名模型。Gruteser[8]等人最先將關(guān)系數(shù)據(jù)庫中k-匿名的概念應(yīng)用到保護(hù)位置隱私上，提出了基于位置隱私保護(hù)的k-匿名模型，由于所有用戶擁有一樣的隱私需求參數(shù)k，該算法無法滿足用戶的個(gè)性化隱私需求。Gedik[9]等人提出了CliqueCloak方法，用戶可以根據(jù)自身的需求指定個(gè)性化的隱私需求參數(shù)k，但CliqueCloak方法只適用于隱私需求參數(shù)k比較小的情況。Xu[10]等人提出基于圓形匿名空間的匿名算法，圓形的匿名空間能夠生成較小的查詢結(jié)果集，從而提高算法的精度，但這些采用中心服務(wù)器結(jié)構(gòu)的位置隱私保護(hù)方法存在兩個(gè)弊端：1) 中心服務(wù)器可能會(huì)成為服務(wù)性能的瓶頸；2) 該中心服務(wù)器中儲(chǔ)存了大量的用戶身份信息和位置信息，一旦被攻破，后果非常嚴(yán)重。

針對中心服務(wù)器的缺陷，ChowCY[11]在2006年首次提出了針對點(diǎn)到點(diǎn)模式下使用匿名算法的思想，通過對等點(diǎn)查詢算法來構(gòu)建匿名區(qū)域。這種算法的優(yōu)點(diǎn)在于分散了匿名工作和計(jì)算量到初始終端的鄰居節(jié)點(diǎn)，在保證達(dá)到匿名度的同時(shí)平均分配損耗，缺點(diǎn)是同一時(shí)刻同一地點(diǎn)有較多LBS請求時(shí)，網(wǎng)絡(luò)中有大量的數(shù)據(jù)包在特定的終端間流動(dòng)，可能產(chǎn)生延時(shí)或網(wǎng)絡(luò)擁塞等情況。為了提高查詢效率，ChowCY于2011年提出了一些改進(jìn)[12]，即提出一種基于k-anonymity模型的P2P解決方案，通過對計(jì)算得到的匿名區(qū)進(jìn)行隨機(jī)擴(kuò)大來規(guī)避匿名區(qū)中心攻擊，但該方法仍無法從根本上杜絕查詢發(fā)起者在匿名區(qū)內(nèi)分布隨機(jī)的問題，且抗查詢采樣攻擊的能力較弱。李泰成[2]利用希爾伯特函數(shù)的單向性性質(zhì)，提出了基于希爾伯特空間填充曲線和基于錨點(diǎn)的增量查詢方法。YiuML[13]提出了一種SpaceTwist方法，用戶在自己真實(shí)位置附近隨機(jī)選取一個(gè)點(diǎn)作為錨點(diǎn)，然后使用該錨點(diǎn)代替自己的真實(shí)位置向LBS服務(wù)器發(fā)起增量近鄰查詢。但是此類增量查詢方法缺少用戶之間的協(xié)助合作，可能無法達(dá)到k匿名，且抗中心攻擊能力較弱。胡德敏[14]等對SpaceTwist方法進(jìn)行了改進(jìn)，提出了基于SpaceTwist的k-匿名增量近鄰查詢位置隱私保護(hù)算法，該算法根據(jù)路網(wǎng)中的人口密度，形成滿足用戶k-匿名需求的匿名區(qū)域提交給服務(wù)器，服務(wù)器返回k個(gè)查詢結(jié)果，該方法雖然能較好地保護(hù)查詢用戶的位置隱私，但得到的查詢結(jié)果卻是不精確的，并且增加了服務(wù)器和查詢用戶的檢索能耗。黃毅[15]等提出了一種基于用戶協(xié)作的隱私保護(hù)方法Coprivacy，主要通過用戶之間相互協(xié)作，無中心服務(wù)器及無匿名區(qū)域而能達(dá)到k-匿名的效果。但是Coprivacy方法中的所有協(xié)作的用戶都是可信的，無法解決協(xié)作用戶中出現(xiàn)惡意用戶的情況。劉學(xué)軍[16]等提出了基于不可信環(huán)境的移動(dòng)位置隱私保護(hù)算法來解決移動(dòng)用戶不可信的問題，該算法通過構(gòu)建匿名樹，并從下到上，進(jìn)行子與父節(jié)點(diǎn)的層層遞歸博弈算出錨點(diǎn)代替真實(shí)位置，進(jìn)而保護(hù)查詢用戶的位置信息，但該算法在計(jì)算出最終錨點(diǎn)的過程比較繁瑣，而且還要通過概率統(tǒng)計(jì)篩選出候選位置，這樣不僅計(jì)算能耗增加，并且也得不出最精確的查詢結(jié)果。

徐建[17]等提出了Peer-to-Peer(P2P)的匿名鏈位置隱私保護(hù)算法，在協(xié)作用戶不可信的情況下，其模型通過在轉(zhuǎn)發(fā)信息的過程中構(gòu)造一條匿名鏈來混淆位置信息與身份信息的一一對應(yīng)關(guān)系。這種方法在很大程度上解決了用戶位置隱私保護(hù)存在的問題，但存在兩個(gè)問題：1) 該算法使得匿名鏈中的節(jié)點(diǎn)僅通過連通穩(wěn)定性在周圍查找下一跳的節(jié)點(diǎn)；2) 沒有規(guī)定下一跳節(jié)點(diǎn)和上一跳節(jié)點(diǎn)之間的最小距離。這就導(dǎo)致匿名鏈上的節(jié)點(diǎn)位置比較集中，其空間覆蓋域很難達(dá)到最小匿名面積。此時(shí)，若攻擊者將代理節(jié)點(diǎn)的位置作為查詢節(jié)點(diǎn)的位置也能獲得較高的精度。

本文提出的基于扇形區(qū)域選擇下一跳節(jié)點(diǎn)的SASTNHN方法，不使用第三方的中心服務(wù)器，無匿名區(qū)域，用戶之間通過多跳協(xié)議形成一條匿名鏈來轉(zhuǎn)發(fā)查詢信息，并返回精確的查詢結(jié)果。本文主要有以下幾方面的貢獻(xiàn)：

(1) 提出了一種新的SASTNHN位置隱私保護(hù)方法，該方法使用分布式點(diǎn)對點(diǎn)結(jié)構(gòu)進(jìn)行通信，克服了中心服務(wù)器的性能瓶頸和中心攻擊。

(2) 通過使用扇形區(qū)域和限定節(jié)點(diǎn)之間最小距離來控制下一跳節(jié)點(diǎn)的選擇，避免了匿名鏈中用戶節(jié)點(diǎn)位置過于集中的情況并增大了匿名鏈的空間覆蓋域，減小了查詢節(jié)點(diǎn)位置泄露的風(fēng)險(xiǎn)。

(3) 在分布式點(diǎn)對點(diǎn)的體系結(jié)構(gòu)中，在扇形區(qū)域中尋找下一跳節(jié)點(diǎn)，系統(tǒng)中的節(jié)點(diǎn)可以以較小的通信代價(jià)構(gòu)建匿名鏈。

2 SASTNHN算法描述

2.1 系統(tǒng)結(jié)構(gòu)

如圖1所示，本文對分布式點(diǎn)對點(diǎn)體系結(jié)構(gòu)的位置隱私保護(hù)模型展開研究。系統(tǒng)模型由移動(dòng)用戶、基站和服務(wù)器LBS三部分組成。查詢用戶通過用戶之間的相互協(xié)作構(gòu)建一條匿名鏈轉(zhuǎn)發(fā)查詢信息，并通過控制扇形角度的大小來控制匿名鏈的方向，增大匿名鏈的空間覆蓋域，最后由鏈尾的節(jié)點(diǎn)即代理節(jié)點(diǎn)向LBS發(fā)起查詢，并返回精確的查詢結(jié)果。在通信過程中，移動(dòng)用戶支持兩種通信方式：P2P通信和基站通信。其中，P2P通信是用于與其他移動(dòng)用戶之間的通信，基站通信是借助代理節(jié)點(diǎn)經(jīng)由基站使用無線互聯(lián)網(wǎng)絡(luò)用來向LBS發(fā)起查詢并取得查詢結(jié)果的通信。

圖1 基于扇形區(qū)域的匿名鏈結(jié)構(gòu)示意圖

2.2 相關(guān)定義

定義1 (查詢請求q)查詢用戶rq初始化一個(gè)查詢請求信息q(uid，hop，Time，l(x，y)，query)通過代理用戶向服務(wù)器LBS發(fā)起查詢。

其中uid表示一個(gè)全局唯一的假名標(biāo)識；hop表示跳數(shù)，一般設(shè)置hop的值大于等于k，k(k小于滿足匿名鏈穩(wěn)定性的最大長度的值)是由查詢用戶自己設(shè)定的需求匿名度；Time表示查詢用戶可等待的時(shí)間，即從查詢信息發(fā)出到收到返回結(jié)果所用的時(shí)間要小于用戶可等待的時(shí)間；l(x，y)表示轉(zhuǎn)發(fā)查詢信息用戶的位置，其中x表示橫坐標(biāo)，y表示縱坐標(biāo)；query表示查詢內(nèi)容。

定義2 (中間節(jié)點(diǎn)) 中間節(jié)點(diǎn)在確定自身成為中間節(jié)點(diǎn)之后，根據(jù)自身的屬性信息修改查詢信息q中的uid，并將原信息存儲(chǔ)在自己的本地鏈表中，并幫助查找匿名鏈的下一跳節(jié)點(diǎn)。中間節(jié)點(diǎn)只知與其相連的上一跳和下一跳節(jié)點(diǎn)的相關(guān)信息，并不能確定查詢節(jié)點(diǎn)的身份。

定義3 (代理節(jié)點(diǎn))節(jié)點(diǎn)收到查詢請求信息時(shí)，檢查hop字段，當(dāng)hop值等于1時(shí)，該節(jié)點(diǎn)將成為代理節(jié)點(diǎn)，負(fù)責(zé)向LBS發(fā)送查詢信息并返回結(jié)果。

定義4 (空間覆蓋域)空間覆蓋域是指匿名鏈中，以兩節(jié)點(diǎn)之間最長距離為直徑所形成的覆蓋整個(gè)匿名鏈的圓形區(qū)域。

定義5 (連通穩(wěn)定性)移動(dòng)節(jié)點(diǎn)在路網(wǎng)中處于不斷運(yùn)動(dòng)的狀態(tài)，節(jié)點(diǎn)間的相對位置動(dòng)態(tài)變化，連通穩(wěn)定性用于衡量節(jié)點(diǎn)間的通信質(zhì)量和保持時(shí)間。與它們之間的距離、相對運(yùn)動(dòng)方向、速度及通信半徑有關(guān)。參數(shù)化連通穩(wěn)定性：

其中，d為節(jié)點(diǎn)之間的距離，rmax為最大通信半徑，θ為兩節(jié)點(diǎn)運(yùn)動(dòng)方向的夾角。

2.3 算法描述

在用戶協(xié)作位置隱私保護(hù)系統(tǒng)中，查詢用戶有三種狀態(tài)：不在任何匿名鏈中；已在匿名鏈中但不滿足其隱私保護(hù)度；已在匿名鏈中并且滿足其隱私保護(hù)度。不在任何匿名鏈中的用戶通過多跳通信方式尋找可協(xié)作的中間用戶節(jié)點(diǎn)，構(gòu)造一條匿名鏈，來轉(zhuǎn)發(fā)查詢信息，最終由代理用戶向LBS服務(wù)器發(fā)起查詢并返回查詢結(jié)果。已在匿名鏈中但不滿足其隱私保護(hù)度時(shí)，需重新設(shè)置滿足其需求的hop值，發(fā)起查詢。在匿名鏈的構(gòu)造過程中，每一個(gè)被選中的節(jié)點(diǎn)都需檢查hop和Time字段，并根據(jù)hop和Time的值進(jìn)行相應(yīng)的處理。當(dāng)Time的值小于可等待時(shí)間，并且hop>1時(shí)，在本地列表中選擇一個(gè)合適的節(jié)點(diǎn)，與之建立連接，將hop減1，并轉(zhuǎn)發(fā)請求信息；否則，丟棄之。具體來說，上述過程主要包括搜索鄰居節(jié)點(diǎn)、下一跳節(jié)點(diǎn)的選擇、代理節(jié)點(diǎn)查詢?nèi)齻€(gè)操作。

操作1 搜索鄰居節(jié)點(diǎn)。在這一步中，首先不在任何匿名鏈中或所在匿名鏈不能滿足其匿名需求的查詢用戶rq初始化一個(gè)查詢請求信息q。查詢用戶節(jié)點(diǎn)rq向它的相鄰節(jié)點(diǎn)廣播查詢請求消息，愿意幫忙的鄰居節(jié)點(diǎn)將自己的身份ID，當(dāng)前運(yùn)動(dòng)速度，位置等信息發(fā)送給rq，rq將所有熱心的鄰居節(jié)點(diǎn)信息存儲(chǔ)在本地路由表List中。rq需要周期性的檢查本地路由表，保證列表不為空，以此提高構(gòu)造匿名鏈的效率。相鄰節(jié)點(diǎn)通過加密通信[18]，使用公鑰機(jī)制對通信的內(nèi)容進(jìn)行加密來提高匿名鏈構(gòu)造的安全性。

操作2 下一跳節(jié)點(diǎn)的選擇。在這一步中，移動(dòng)用戶若無上一跳節(jié)點(diǎn)，則在本地路由鏈表中，在移動(dòng)用戶按自身需求規(guī)定的最小距離dmin之外和其最大通信距離rmax范圍內(nèi)，保證節(jié)點(diǎn)間連通穩(wěn)定性的同時(shí)，選擇距離自己最遠(yuǎn)的一個(gè)移動(dòng)用戶作為下一跳的中間節(jié)點(diǎn)。若移動(dòng)節(jié)點(diǎn)是中間結(jié)點(diǎn)，則移動(dòng)用戶以自身位置為圓心，以自身位置與上一跳節(jié)點(diǎn)的位置的連線為中心軸，根據(jù)廣播獲得的周圍鄰居節(jié)點(diǎn)密度，在背離上一跳節(jié)點(diǎn)的方向上確定一個(gè)圓心角度為α，半徑為節(jié)點(diǎn)最大通信距離的扇形區(qū)域。在該區(qū)域中選擇連通性合適并距離自身最遠(yuǎn)的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)，其中下一跳節(jié)點(diǎn)dnext滿足dmin≤dnext≤rmax，下一跳節(jié)點(diǎn)選擇操作如算法1所示。

算法1 下一跳節(jié)點(diǎn)選擇算法

1 If 節(jié)點(diǎn)為查詢節(jié)點(diǎn)

2 計(jì)算所有相鄰節(jié)點(diǎn)的連通穩(wěn)定性

3 根據(jù)連通穩(wěn)定性對相鄰節(jié)點(diǎn)進(jìn)行排序

4 選擇距離自身最遠(yuǎn)，滿足最小距離且連通穩(wěn)定性最好的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)

5 Else if 節(jié)點(diǎn)為中間節(jié)點(diǎn)

6 根據(jù)上一跳節(jié)點(diǎn)的位置及最大通信距離確定扇形區(qū)域

7 僅計(jì)算扇形區(qū)域內(nèi)相鄰節(jié)點(diǎn)的連通穩(wěn)定性，并排序

8 選擇該扇形區(qū)域內(nèi)，距離自身最遠(yuǎn)、滿足最小距離且連通穩(wěn)定性最好的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)

9 End if

10 Return 下一跳節(jié)點(diǎn)

操作3 代理節(jié)點(diǎn)提交查詢請求。收到查詢信息的節(jié)點(diǎn)，檢查hop和Time字段，當(dāng)hop=1時(shí)，該節(jié)點(diǎn)被確定為代理節(jié)點(diǎn)。即匿名鏈構(gòu)造完成，查詢節(jié)點(diǎn)發(fā)送的查詢信息沿匿名鏈發(fā)送給了代理節(jié)點(diǎn)，由代理節(jié)點(diǎn)負(fù)責(zé)向LBS發(fā)起查詢，并將查詢的結(jié)果沿著匿名鏈返回給查詢用戶，完成查詢。

整個(gè)過程如算法2所示。

算法2SASTBHN算法

1 If節(jié)點(diǎn)自身具有查詢需求

2 設(shè)置隱私保護(hù)最低需求度

3 設(shè)置跳數(shù)

4 if查詢節(jié)點(diǎn)不在匿名鏈上或不滿足匿名需求

5 初始化查詢請求

6 搜索鄰居節(jié)點(diǎn)

7 選擇下一跳節(jié)點(diǎn)(算法1)

8 end if

9 發(fā)送查詢請求給下一跳節(jié)點(diǎn)

10 else if節(jié)點(diǎn)接收到上一跳節(jié)點(diǎn)發(fā)送的廣播請求

11 將自身的uid，l(x,y)等信息發(fā)送給上一跳的節(jié)點(diǎn)，

并將上一跳的節(jié)點(diǎn)保存到本地緩存中

12 else if節(jié)點(diǎn)接收到上一跳節(jié)點(diǎn)的查詢請求

13 if跳數(shù)為1

//跳數(shù)為1，該節(jié)點(diǎn)成為代理節(jié)點(diǎn)

14 向LBS提交查詢請求并將返回的結(jié)果發(fā)送給

上一跳的節(jié)點(diǎn)

15 else

//跳數(shù)不為1，則該節(jié)點(diǎn)為中間節(jié)點(diǎn)

16 跳數(shù)減1

17 選擇下一跳節(jié)點(diǎn)(算法1)

18 將查詢請求發(fā)送給下一跳節(jié)點(diǎn)

19 end if

20 end if

3 性能分析

本節(jié)主要針對基于扇形區(qū)域構(gòu)建匿名鏈算法的匿名隱私保護(hù)度及能耗進(jìn)行分析。假設(shè)攻擊者是一個(gè)全局攻擊者，不僅可以獲得服務(wù)器LBS的數(shù)據(jù)信息，在移動(dòng)節(jié)點(diǎn)內(nèi)還有惡意同伙，即攻擊者可以從惡意節(jié)點(diǎn)處獲得查詢信息q的相關(guān)內(nèi)容。

3.1 匿名保護(hù)度分析

本文算法從兩個(gè)方面保證了匿名隱私保護(hù)度：k-匿名和空間覆蓋域。

3.1.1k-匿名保護(hù)

查詢用戶在發(fā)送查詢信息時(shí)按自己的隱私需求設(shè)置跳數(shù)值k，即用k個(gè)用戶構(gòu)成匿名鏈來隱藏自己的真實(shí)位置信息。假設(shè)攻擊者可以從LBS和惡意節(jié)點(diǎn)處獲得數(shù)據(jù)信息，即攻擊者可獲知查詢節(jié)點(diǎn)的具體位置信息和查詢的內(nèi)容，但卻不能獲得查詢節(jié)點(diǎn)全局唯一假名標(biāo)識uid。并且當(dāng)且僅當(dāng)查詢節(jié)點(diǎn)后的第一個(gè)中間節(jié)點(diǎn)是惡意節(jié)點(diǎn)時(shí)，攻擊者才有機(jī)會(huì)獲得查詢節(jié)點(diǎn)的全局唯一假名標(biāo)識uid。

3.1.2 空間覆蓋域

攻擊者除了有惡意節(jié)點(diǎn)幫助來推測查詢節(jié)點(diǎn)的位置以外，若匿名鏈的空間覆蓋域過小，導(dǎo)致代理節(jié)點(diǎn)的位置與查詢節(jié)點(diǎn)的位置相近，那么攻擊者把代理節(jié)點(diǎn)位置作為查詢節(jié)點(diǎn)的位置，也會(huì)導(dǎo)致查詢節(jié)點(diǎn)的位置有泄露的風(fēng)險(xiǎn)。

本文采用基于扇形區(qū)域選取下一跳節(jié)點(diǎn)的SASANHN算法，從兩個(gè)方面保證擴(kuò)大覆蓋匿名鏈的空間覆蓋域：1) 距離。限定了兩個(gè)節(jié)點(diǎn)之間最小距離dmin，在保證下一跳節(jié)點(diǎn)dnext滿足dmin≤dnext≤rmax的條件下，根據(jù)節(jié)點(diǎn)之間的連通穩(wěn)定性，來選擇距離最遠(yuǎn)的一個(gè)節(jié)點(diǎn)作為下一跳的節(jié)點(diǎn)。2) 方向。采用上一跳和下一跳節(jié)點(diǎn)所在直線為中心軸，在背離上一跳節(jié)點(diǎn)的方向上，根據(jù)相鄰節(jié)點(diǎn)的密度確定一個(gè)扇形區(qū)域，在此區(qū)域中選擇下一跳的節(jié)點(diǎn)。這樣可以有效地避免匿名鏈中節(jié)點(diǎn)之間的位置過于集中，使代理節(jié)點(diǎn)與查詢節(jié)點(diǎn)的位置相近而導(dǎo)致查詢節(jié)點(diǎn)位置有泄露的風(fēng)險(xiǎn)。增大了匿名鏈的空間覆蓋域，從而進(jìn)一步減小了攻擊者攻擊成功的概率。

兩節(jié)點(diǎn)之間的連通穩(wěn)定性受兩節(jié)點(diǎn)間的距離、運(yùn)動(dòng)方向和速度的影響。同向，速度大小相近，距離越短的兩節(jié)點(diǎn)之間的連通穩(wěn)定性越強(qiáng)。本文算法鏈路上的下一跳節(jié)點(diǎn)均是在背離上一跳節(jié)點(diǎn)的方向，滿足dmin≤dnext≤rmax的條件，然后根據(jù)節(jié)點(diǎn)間的連通穩(wěn)定性來選擇的。

假設(shè)在移動(dòng)用戶分布均勻的網(wǎng)絡(luò)中，以查詢節(jié)點(diǎn)為原點(diǎn)建立直角坐標(biāo)系，為了方便計(jì)算，假設(shè)每一個(gè)扇形的夾角度數(shù)均為α，則下一跳節(jié)點(diǎn)的選取區(qū)域滿足：

(1)

即匿名鏈中中間節(jié)點(diǎn)的選擇在式(1)包含的區(qū)域內(nèi)，其中h=1,2,…,k，X表示節(jié)點(diǎn)的橫坐標(biāo)，Y表示節(jié)點(diǎn)的縱坐標(biāo)，α滿足α∈[0,π]，下一跳節(jié)點(diǎn)位置dnext滿足dmin≤dnext≤rmax，如圖2所示。

圖2 最小空間覆蓋域時(shí)匿名鏈結(jié)構(gòu)示意圖

匿名鏈中的節(jié)點(diǎn)均在滿足式(1)的α=0極限位置選取，形成直線形狀，如圖3所示，此時(shí)形成的覆蓋圓域面積Smax：

圖3 最大空間覆蓋域時(shí)匿名鏈的結(jié)構(gòu)示意圖

而文獻(xiàn)[17]采用優(yōu)先考慮節(jié)點(diǎn)之間連通穩(wěn)定性構(gòu)建匿名鏈的算法的空間覆蓋域滿足

，節(jié)點(diǎn)間的距離越小，其連通穩(wěn)定性越強(qiáng)。因此，僅使用連通穩(wěn)定性作為選擇下一跳節(jié)點(diǎn)的依據(jù)，將使得匿名鏈的空間覆蓋域以極大的概率趨向于最小空間覆蓋域。由上述分析可知，采用本文算法構(gòu)建的具有相同節(jié)點(diǎn)數(shù)的匿名鏈的空間覆蓋域的面積要大于文獻(xiàn)[17]的算法的。

3.2 能耗分析

3.2.1 服務(wù)質(zhì)量

由于查詢節(jié)點(diǎn)提供其真實(shí)的位置坐標(biāo)信息給LBS服務(wù)器并返回精確的查詢結(jié)果，與傳統(tǒng)的提供假位置或一定區(qū)域面積的位置隱私保護(hù)算法相比較，本文算法在保護(hù)查詢節(jié)點(diǎn)位置隱私的同時(shí)并沒有犧牲用戶的任何服務(wù)質(zhì)量。減小了LBS服務(wù)器端的查詢能耗和數(shù)據(jù)傳輸中的網(wǎng)絡(luò)能耗，查詢用戶接收到的是精確的查詢結(jié)果，不需要進(jìn)一步篩選，從而也減小了查詢用戶端的能耗。

3.2.2 建鏈消耗

建成匿名鏈的能量消耗由兩部分組成：廣播后接收并存儲(chǔ)鄰居節(jié)點(diǎn)反饋信息能耗和計(jì)算選擇下一跳節(jié)點(diǎn)能耗。在構(gòu)建匿名鏈時(shí)，本文算法與文獻(xiàn)[17]中的算法均是每個(gè)用戶都向周圍鄰居廣播請求消息，收集鄰居節(jié)點(diǎn)信息，根據(jù)節(jié)點(diǎn)間的連通穩(wěn)定性選擇下一跳節(jié)點(diǎn)。但在選擇下一跳節(jié)點(diǎn)時(shí)，本文算法并不是把該廣播請求節(jié)點(diǎn)和每個(gè)鄰居節(jié)點(diǎn)間的連通穩(wěn)定性都計(jì)算一遍，而是接收到鄰居節(jié)點(diǎn)的反饋之后，根據(jù)算法的需求，選擇一個(gè)扇形區(qū)域，只需要計(jì)算和扇形區(qū)域內(nèi)每個(gè)節(jié)點(diǎn)之間的連通穩(wěn)定性，最終選擇一個(gè)合適的下一跳節(jié)點(diǎn)，完成信息的轉(zhuǎn)發(fā)就可以。所以本文算法與文獻(xiàn)[17]算法的能耗差別就在于計(jì)算連通性時(shí)節(jié)點(diǎn)個(gè)數(shù)的多少。

扇形區(qū)域內(nèi)的移動(dòng)用戶數(shù)為n′=δm。長度為k的匿名鏈中k個(gè)節(jié)點(diǎn)計(jì)算能量消耗，同文獻(xiàn)[17]的比較如表1所示。

表1 能量消耗比較

因此，本文算法建鏈成功的能量消耗與文獻(xiàn)[17]的能耗差為ΔE：

與文獻(xiàn)[17]的算法相比較，本文算法在保證查詢節(jié)點(diǎn)安全性的情況下，能耗方面的優(yōu)勢在于下一跳節(jié)點(diǎn)的選擇是受最小距離dmin和角度α控制的，而不是毫無方向的隨機(jī)選擇，這樣可以很大程度地減少節(jié)點(diǎn)間的計(jì)算次數(shù)導(dǎo)致的能耗損失。

4 實(shí) 驗(yàn)

實(shí)驗(yàn)使用德國Oldenburg的實(shí)際道路地圖，算法使用Java語言，在4210M2.6GHz處理器、8GB內(nèi)存的Windows7的平臺(tái)上運(yùn)行。在ThomasBrinkhoff路網(wǎng)數(shù)據(jù)生成器上模擬不同交通狀況，生成模擬的移動(dòng)用戶數(shù)據(jù)。實(shí)驗(yàn)中使用的用戶數(shù)據(jù)參數(shù)值如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)參數(shù)值

4.1 覆蓋域優(yōu)化效果

首先通過實(shí)驗(yàn)驗(yàn)證本文算法對不同長度的匿名鏈空間覆蓋域大小的影響，再通過與隨機(jī)算法對比，研究在不同移動(dòng)用戶數(shù)量和匿名鏈長度的條件下，對匿名鏈空間覆蓋域大小的影響。

在移動(dòng)用戶總數(shù)為20 000人的模擬網(wǎng)絡(luò)環(huán)境中，不同匿名鏈長度條件下，研究本文算法對匿名鏈空間覆蓋域的影響。由圖4的數(shù)據(jù)結(jié)果顯示可以看出，匿名鏈的長度對其空間覆蓋域的影響顯著。隨著匿名鏈長度的增加，不同長度的匿名鏈的空間覆蓋域與其最大覆蓋空間的比率有所減小，但匿名鏈的空間覆蓋域在不斷增大。

圖4 匿名鏈長度對覆蓋域的影響

使用長度為3-hops的匿名鏈，在不同用戶密度條件下進(jìn)行實(shí)驗(yàn)，比較本文算法與隨機(jī)算法對匿名鏈空間覆蓋域大小影響效果。由圖5可知，隨著移動(dòng)用戶數(shù)量的不斷增加，隨機(jī)算法的空間覆蓋域的大小隨機(jī)，毫無規(guī)律可循，而本文算法的匿名鏈的空間覆蓋域在不斷增大，并且一直大于隨機(jī)算法的。

圖5 移動(dòng)用戶數(shù)對覆蓋域的影響

圖4和圖5的實(shí)驗(yàn)結(jié)果表明本文算法能顯著增大匿名鏈的空間覆蓋域。與隨機(jī)算法相比較，在匿名鏈長度一定時(shí)，隨著移動(dòng)用戶總數(shù)的增加，本文算法的匿名鏈空間覆蓋面積持續(xù)增大，并且明顯大于隨機(jī)算法的。

4.2 匿名效果

在移動(dòng)用戶總數(shù)為12 000人的模擬網(wǎng)絡(luò)環(huán)境條件下，逐次增加惡意節(jié)點(diǎn)的比例，比較匿名鏈長度為2、3、4、5hops時(shí)，根據(jù)出現(xiàn)惡意節(jié)點(diǎn)的匿名鏈數(shù)目以及第一個(gè)惡意節(jié)點(diǎn)出現(xiàn)的位置，計(jì)算本文算法匿名成功的平均概率。

如圖6所示，橫坐標(biāo)表示惡意節(jié)點(diǎn)占移動(dòng)用戶總數(shù)的比例，縱坐標(biāo)為系統(tǒng)的匿名成功率。隨著網(wǎng)絡(luò)中惡意節(jié)點(diǎn)數(shù)目的增加，系統(tǒng)的整體匿名成功率有所下降。但增加匿名鏈的長度，可以顯著提高系統(tǒng)的匿名成功率。

圖6 不同鏈長的匿名成功率

在匿名鏈長度為3-hops，移動(dòng)用戶為12 000人的網(wǎng)絡(luò)環(huán)境條件下，依次增加惡意節(jié)點(diǎn)的比例，對比本文算法與文獻(xiàn)[17]算法的匿名成功率，實(shí)驗(yàn)結(jié)果如圖7所示。圖7中，隨著網(wǎng)絡(luò)中惡意節(jié)點(diǎn)數(shù)目的增加，系統(tǒng)的整體匿名效果均下降，但本文算法的匿名成功率卻顯著高于文獻(xiàn)[17]的。這是由于本文算法擴(kuò)大了匿名鏈的空間覆蓋域，減小了攻擊者的攻擊成功概率，提高了系統(tǒng)的匿名成功率。

圖7 3-hops匿名鏈的匿名成功率對比

由此可以看出，增大匿名鏈的空間覆蓋域，可以提高系統(tǒng)的匿名成功率，進(jìn)而更好地保護(hù)查詢節(jié)點(diǎn)的位置隱私。

4.3 能量消耗

模擬網(wǎng)絡(luò)中，移動(dòng)用戶總數(shù)為10 000人，研究建鏈時(shí)扇形圓心角度的大小對節(jié)點(diǎn)平均計(jì)算次數(shù)的影響。如圖 8所示，隨著扇形角度的增大，扇形區(qū)域中移動(dòng)用戶個(gè)數(shù)增加，本文SASTNHN算法中每個(gè)節(jié)點(diǎn)的平均計(jì)算次數(shù)增加。這是因?yàn)楫?dāng)α增大時(shí)，扇形面積增大，扇形區(qū)域中包含的移動(dòng)用戶數(shù)量也會(huì)增多。增大扇形面積，移動(dòng)用戶數(shù)量增加，導(dǎo)致節(jié)點(diǎn)間的計(jì)算次數(shù)增加，進(jìn)而增加了能量消耗。

圖8 扇形角度對計(jì)算次數(shù)的影響

圖9中，實(shí)驗(yàn)是將本文的SASTNHN方法與優(yōu)先考慮節(jié)點(diǎn)間連通性的方法在計(jì)算能耗方面進(jìn)行了比較。在實(shí)驗(yàn)中使用匿名鏈長度為3-hops，統(tǒng)計(jì)了在不同用戶密度下兩種算法成功完成一次匿名，節(jié)點(diǎn)之間需要計(jì)算的平均次數(shù)。圖9所示，隨著移動(dòng)用戶數(shù)量的增加，兩種算法的平均計(jì)算次數(shù)均有所增加，但優(yōu)先考慮節(jié)點(diǎn)間連通性的算法的平均計(jì)算次數(shù)幾乎成線性增長，增長速度較快，本文算法的計(jì)算次數(shù)雖有所增長，但相對平穩(wěn)。由于構(gòu)造匿名鏈的能量消耗幾乎等于節(jié)點(diǎn)之間計(jì)算的消耗，由此可見，隨著移動(dòng)用戶總數(shù)的增加，兩種算法的能耗均增加。但本文SASTNHN算法的能耗增加相對緩慢，移動(dòng)用戶越多，SASTNHN算法在減少能耗方面更具優(yōu)勢。

圖9 成功建鏈一次的平均計(jì)算次數(shù)

5 結(jié) 語

針對動(dòng)態(tài)P2P網(wǎng)絡(luò)環(huán)境中，查詢用戶使用不可信的服務(wù)器LBS提供的基于位置的服務(wù)，而導(dǎo)致查詢用戶的位置隱私有泄漏的風(fēng)險(xiǎn)問題。一般的P2P位置隱私保護(hù)方法使用錨點(diǎn)代替查詢用戶真實(shí)位置或者通過節(jié)點(diǎn)間的連通穩(wěn)定性構(gòu)建匿名鏈來隱藏查詢用戶的真實(shí)位置，但沒有考慮到協(xié)作用戶間的空間覆蓋域的大小對位置隱私保護(hù)的影響。本文提出的基于扇形區(qū)域的擴(kuò)大匿名鏈空間覆蓋域的位置隱私保護(hù)方法，通過使用一個(gè)扇形區(qū)域來控制節(jié)點(diǎn)選擇的范圍和方向來擴(kuò)大匿名鏈的空間覆蓋域，使代理節(jié)點(diǎn)盡可能地遠(yuǎn)離查詢節(jié)點(diǎn)，避免中心攻擊。通過隱藏身份信息與位置信息的對應(yīng)關(guān)系來保護(hù)查詢用戶的位置隱私。本文通過實(shí)驗(yàn)驗(yàn)證了算法的可行性，證明了該方法的優(yōu)越性。

[1] 劉雅輝,張鐵贏,靳小龍,等.大數(shù)據(jù)時(shí)代的個(gè)人隱私保護(hù)[J].計(jì)算機(jī)研究與發(fā)展,2015,52(1):229-247.

[2] 李泰成.一種滿足查詢結(jié)果完整性和數(shù)據(jù)保密性的位置隱私保護(hù)方案[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(1):310-314.

[3]BarkhuusL,DeyAK.Location-basedservicesformobiletelephony:astudyofusers'privacyconcerns[C]//ProceedingofInteract.Zurich,Switzerland,2003:702-712.

[4]KarimW.Privacyimplicationsofpersonallocators:whyyoushouldthinktwicebeforevoluntarilyavailingyourselftoGPSmonitoring[J].Wash.UJL&Pol’y,2004,14(1):485-515.

[5] 武朋輝,楊百龍,毛晶,等.一種WSN位置隱私保護(hù)方案分析和改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(2):312-314.

[6] 潘曉,肖珍,孟小峰.位置隱私研究綜述[J].計(jì)算機(jī)科學(xué)與探索,2007,1(3):268-281.

[7] 魏瓊,盧炎生.位置隱私保護(hù)技術(shù)研究進(jìn)展[J].計(jì)算機(jī)科學(xué),2008,35(9):21-25.

[8]GruteserM,GrunwaldD.Anonymoususageoflocation-basedservicesthroughspatialandtemporalcloaking[C]//Proceedingsofthe1stinternationalconferenceonMobilesystems,applicationsandservices.SanFrancisco,CA,USA,2003:31-42.

[9]GedikB,LiuL.Acustomizablek-anonymitymodelforprotectinglocationprivacy[C]//ProceedingsoftheIEEEInternationalConferenceonDistributedComputingSystems(ICDCS’05).Columbus,Ohio,USA,2005:620-629.

[10]XuJ,TangX,HuH,etal.Privacy-consciouslocation-basedqueriesinmobileenvironments[J].ParallelandDistributedSystems,IEEETransactionson,2010,21(3):313-326.

[11]ChowCY,MokbelMF,LiuX.Apeer-to-peerspatialcloakingalgorithmforanonymouslocation-basedservice[C]//Proceedingsofthe14thannualACMinternationalsymposiumonAdvancesingeographicinformationsystems.Arlington,VA,USA,2006:171-178.

[12]ChowCY,MokbelMF,LiuX.Spatialcloakingforanonymouslocation-basedservicesinmobilepeer-to-peerenvironments[J].GeoInformatica,2011,15(2):351-380.

[13]YiuML,JensenCS,HuangX,etal.Spacetwist:Managingthetrade-offsamonglocationprivacy,queryperformance,andqueryaccuracyinmobileservices[C]//ProceedingsoftheIEEEInternationalConferenceonDataEngineering(ICDE’08).Cancun,Mexico,2008:366-375.

[14] 胡德敏,鄭霞.基于SpaceTwist的k-匿名增量近鄰查詢位置隱私保護(hù)算法[J].計(jì)算機(jī)應(yīng)用研究,2016,33(8):1-5.

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

[16] 劉學(xué)軍,陳玉鳳,李斌.基于不可信環(huán)境的移動(dòng)位置隱私保護(hù)[J].計(jì)算機(jī)科學(xué),2015,42(2):108-141.

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

[18] 張建軍,吳啟武.物聯(lián)網(wǎng)中的隱私保護(hù)問題研究[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(6):278-279.

LOCATION PRIVACY PROTECTION IN DYNAMIC P2P NETWORKBASED ON SECTOR REGION

Jia Zongpu Liu Wen

(SchoolofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

At present, the existing methods of location privacy protection in dynamic peer-to-peer (P2P) network frequently tend to make the cooperative users’ locations to be too concentrated and the spatial covering domain to be relatively small. Their ability of anti-center-attack is also quite weak. Aiming at this problem, a method of location privacy protection based on sector region is proposed. An anonymous chain is constructed by the cooperation between mobile stations to forward inquired information and hide the users’ real locations as completing accurate inquiries. The direction of anonymous chain is restricted by the sector region, and the stability of the link between the nodes has been taken into consideration while constructing the anonymous chain, so that its spatial covering domain and stability can be ensured. Then, the degree of anonymity and the ability of anti-center-attack can be improved. Experimental result shows that this algorithm performs relatively well in different density of users, whether the anonymity performance or computing consumption.

Location privacy P2P network Sector region Spatial covering domain

2016-02-17。賈宗璞，教授，主研領(lǐng)域：物聯(lián)網(wǎng)技術(shù)與應(yīng)用，計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)，計(jì)算機(jī)測控技術(shù)，信息系統(tǒng)。劉雯，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2017.03.057