賈宗璞 劉 雯

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

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

賈宗璞 劉 雯

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

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

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

0 引 言

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 SASTNHN算法描述

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

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

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

2.2 相關(guān)定義

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

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

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

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

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

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

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

2.3 算法描述

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

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

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

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

1 If 節(jié)點為查詢節(jié)點

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

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

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

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

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

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

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

9 End if

10 Return 下一跳節(jié)點

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

整個過程如算法2所示。

算法2SASTBHN算法

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

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

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

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

5 初始化查詢請求

6 搜索鄰居節(jié)點

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

8 end if

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

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

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

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

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

13 if跳數(shù)為1

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

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

上一跳的節(jié)點

15 else

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

16 跳數(shù)減1

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

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

19 end if

20 end if

3 性能分析

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

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

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

3.1.1k-匿名保護(hù)

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

3.1.2 空間覆蓋域

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

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

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

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

(1)

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

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

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

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

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

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

3.2 能耗分析

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

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

3.2.2 建鏈消耗

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

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

表1 能量消耗比較

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

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

4 實 驗

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

表2 實驗數(shù)據(jù)參數(shù)值

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

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

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

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

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

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

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

4.2 匿名效果

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

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

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

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

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

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

4.3 能量消耗

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

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

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

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

5 結(jié) 語

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

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

[2] 李泰成.一種滿足查詢結(jié)果完整性和數(shù)據(jù)保密性的位置隱私保護(hù)方案[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ī)應(yīng)用與軟件,2013,30(2):312-314.

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

[7] 魏瓊,盧炎生.位置隱私保護(hù)技術(shù)研究進(jìn)展[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ī)應(yīng)用研究,2016,33(8):1-5.

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

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

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

[18] 張建軍,吳啟武.物聯(lián)網(wǎng)中的隱私保護(hù)問題研究[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ī)網(wǎng)絡(luò)技術(shù)，計算機(jī)測控技術(shù)，信息系統(tǒng)。劉雯，碩士生。

TP393

A

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