基于多邊形隱匿區(qū)域的LBS系統(tǒng)

曹 伍，徐 葎，劉玉葆，印 鑒

（中山大學(xué) 計(jì)算機(jī)系，廣州 510006）

0 引 言

隨著社會(huì)經(jīng)濟(jì)的發(fā)展，人類(lèi)的活動(dòng)范圍不斷擴(kuò)大，地理區(qū)域的擴(kuò)展給人們出行帶來(lái)極大的不便．在這樣的情況下，基于位置服務(wù)（LBS）應(yīng)運(yùn)而生，為人們提供各種各樣的位置服務(wù)．比如，基于LBS，駕駛員可以查找離自己最近的加油站．隨著位置探測(cè)設(shè)備（例如便攜式電話、GPS、RFID等）的廣泛使用，使得基于位置的服務(wù)日益受到人們的關(guān)注．文獻(xiàn)［1］介紹了LBS系統(tǒng)的架構(gòu)和各個(gè)組成部分的關(guān)鍵技術(shù)以及LBS的研究進(jìn)展．然而LBS在為用戶帶來(lái)便利的同時(shí)，也威脅著用戶的隱私安全．因?yàn)長(zhǎng)BS需要以用戶的位置信息作為輸入，在用戶向服務(wù)器發(fā)送位置信息時(shí)，也意味著用戶的位置隱私有可能被LBS服務(wù)供應(yīng)商惡意利用，如通過(guò)位置信息推斷用戶的工作地點(diǎn)、行為習(xí)慣等．因此，出于用戶對(duì)位置隱私保護(hù)的需求，相關(guān)的研究也陸續(xù)出現(xiàn)：文獻(xiàn)［2］提出了一種面向公路網(wǎng)絡(luò)的位置隱私保護(hù)方法；文獻(xiàn)［3］提出了一種用戶協(xié)作無(wú)匿名區(qū)域的位置隱私保護(hù)方法；基于很多匿名算法不能適用于連續(xù)查詢的情況，文獻(xiàn)［4］提出了一種適用于連續(xù)查詢的貪心匿名算法．

隨著數(shù)據(jù)庫(kù)技術(shù)、網(wǎng)絡(luò)技術(shù)的發(fā)展，人們?cè)贚BS的隱私保護(hù)上不斷提出新的方法，如Casper［5］、TinyCasper［6］、PRIVE［7］等．此外，文獻(xiàn)［8］提出了一種有效的隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘方法，提高了對(duì)隱私數(shù)據(jù)的保護(hù)程度和挖掘結(jié)果的準(zhǔn)確性；文獻(xiàn)［9］是關(guān)于鄰域隱私保護(hù)的論文，研究了在云端的最短距離計(jì)算，用以防止外包圖來(lái)自鄰域的攻擊；文獻(xiàn)［10］介紹了位置大數(shù)據(jù)的概念以及位置大數(shù)據(jù)的隱私威脅．通常來(lái)說(shuō)，這些隱私保護(hù)技術(shù)首先把地圖劃分為網(wǎng)格狀，每個(gè)用戶可以自由設(shè)置自己的隱私要求，包括隱匿區(qū)域的大小和K－Anonymity參數(shù)．其中，隱匿區(qū)域大小是指用戶需要把自己的點(diǎn)坐標(biāo)轉(zhuǎn)換的區(qū)域面積；而K－Anonymity參數(shù)用來(lái)描述用戶所處的隱匿區(qū)域至少覆蓋的在線用戶數(shù)．接著，根據(jù)用戶的位置信息以及隱私要求，位置匿名器將用戶映射到對(duì)應(yīng)的網(wǎng)格中，并將該網(wǎng)格作為用戶的隱匿區(qū)域傳送給LBS服務(wù)器．最后服務(wù)器根據(jù)網(wǎng)格的位置信息來(lái)處理用戶的服務(wù)請(qǐng)求．因此，服務(wù)器只知道用戶所屬的網(wǎng)格而不是具體位置，且該網(wǎng)格內(nèi)有至少K個(gè)用戶，惡意攻擊無(wú)法辨別個(gè)體的身份，從而保護(hù)了用戶的位置隱私．

已有方法和系統(tǒng)從不同角度解決了LBS隱私保護(hù)中具有挑戰(zhàn)的問(wèn)題，然而也存在著一些不足：①網(wǎng)格形狀的隱匿區(qū)域在某些地形下存在過(guò)多的無(wú)效區(qū)域，如某用戶位于沙漠中的公路上，最佳的隱藏區(qū)域應(yīng)該是條帶狀的公路區(qū)域，而使用網(wǎng)格狀的隱匿區(qū)域會(huì)導(dǎo)致無(wú)效區(qū)域的出現(xiàn)并增加服務(wù)器的計(jì)算開(kāi)銷(xiāo)或者無(wú)效的返回結(jié)果．②僅靠隱私參數(shù)的設(shè)置而自動(dòng)生成的隱匿區(qū)域無(wú)法完整地表達(dá)用戶的查詢意圖．一般來(lái)說(shuō)，用戶總是希望自己位于隱匿的中心附近，但由于網(wǎng)格是預(yù)先劃分好的，無(wú)法隨意平移，因此當(dāng)用戶位于某個(gè)網(wǎng)格邊緣時(shí)，該方法無(wú)法達(dá)到預(yù)期的效果．③位置數(shù)據(jù)的精度損失太大．位置數(shù)據(jù)精度對(duì)LBS供應(yīng)商非常有用，因?yàn)槲恢脭?shù)據(jù)經(jīng)過(guò)數(shù)據(jù)挖掘后可以獲得許多具有價(jià)值的信息，如哪個(gè)區(qū)域查詢的酒店次數(shù)最多、哪里最需要加油站等．在LBS的實(shí)際應(yīng)用中，用戶的需求趨向于隱匿區(qū)域和實(shí)際的地形、城市布局相吻合，如用戶希望隱藏于某條街道或者某個(gè)大廈內(nèi)．這種相吻合的隱匿區(qū)域最大程度地保留了數(shù)據(jù)精度，同時(shí)也滿足了用戶的隱私要求，是隱私安全程度和數(shù)據(jù)精度之間的最佳平衡點(diǎn)．然而網(wǎng)格狀的劃分并不考慮地形、城市布局等因素，因此所生成的矩形隱匿區(qū)域也就導(dǎo)致了位置數(shù)據(jù)精度的降低．

針對(duì)已有系統(tǒng)的不足，本文根據(jù)文獻(xiàn)［11］和文獻(xiàn)［12］中的理論，設(shè)計(jì)和實(shí)現(xiàn)了一種基于多邊形隱匿區(qū)域的LBS系統(tǒng)．本文余下部分組織如下：第1節(jié)是系統(tǒng)目標(biāo)；第2節(jié)是系統(tǒng)設(shè)計(jì)；第3節(jié)是系統(tǒng)實(shí)現(xiàn)；第4節(jié)是系統(tǒng)性能測(cè)試；第5節(jié)是全文的總結(jié)．

1 系統(tǒng)目標(biāo)

本系統(tǒng)的設(shè)計(jì)目標(biāo)是在保護(hù)用戶位置隱私的同時(shí)，盡量保留位置數(shù)據(jù)的精度，并提供良好的服務(wù)質(zhì)量，即兼顧位置隱私安全、數(shù)據(jù)精度和服務(wù)質(zhì)量3個(gè)方面．

1．1 隱私安全

保護(hù)用戶的位置隱私，是設(shè)計(jì)LBS系統(tǒng)的首要原則．本系統(tǒng)將使用“Location Cloaking”和“K－Anonymity”作為主要的隱私保護(hù)技術(shù)，從位置信息和身份信息兩方面進(jìn)行保護(hù)．

（1）Location Cloaking

Location Cloaking的原理是將準(zhǔn)確的點(diǎn)坐標(biāo)信息進(jìn)行Cloaking處理，泛化為包含該點(diǎn)的一個(gè)區(qū)域，即對(duì)應(yīng)的隱匿區(qū)域．在使用LBS時(shí)，僅向服務(wù)商提供用戶對(duì)應(yīng)的區(qū)域．該區(qū)域的大小可以由用戶根據(jù)自己的隱私需求來(lái)設(shè)定，以調(diào)整其位置的隱匿程度．

（2）K－Anonymity

K－Anonymity是指在一個(gè)數(shù)據(jù)集中，任何一個(gè)條記錄都至少和其他K－1（K≥2）條記錄不可區(qū)別，K越大，則安全程度越高．在這樣的數(shù)據(jù)集中，用戶能處于真正的匿名狀態(tài)，避免隱私泄露的侵?jǐn)_．本系統(tǒng)不僅采用用戶點(diǎn)位置的隱匿區(qū)域泛化，還要求泛化區(qū)域中的用戶數(shù)量超過(guò)閾值K，從而保證用戶的隱私安全．

由于進(jìn)行K－Anonymity處理需要收集大量的用戶位置信息，因此，需要引入可信的第三方中間件．一般來(lái)說(shuō)，用戶先將位置信息發(fā)送給中間件，讓中間件來(lái)生成隱匿區(qū)域；然后，再由中間件向服務(wù)器轉(zhuǎn)發(fā)用戶的服務(wù)請(qǐng)求．但是，如果中間件不可信或者受到黑客攻擊而泄露數(shù)據(jù)，則用戶的隱私安全可能會(huì)受到威脅．因此，本系統(tǒng)使用雙重位置隱私保護(hù)，將Location Cloaking和K－Anonymity兩個(gè)保護(hù)技術(shù)分開(kāi)，分別在客戶端和中間件中執(zhí)行，從而進(jìn)一步保證了用戶的位置隱私安全．

1．2 數(shù)據(jù)精度

數(shù)據(jù)精度是平衡用戶隱私要求與服務(wù)質(zhì)量的重要因素．適當(dāng)?shù)奈恢脭?shù)據(jù)精度在LBS中可謂至關(guān)重要．本系統(tǒng)采用Location Cloaking方法對(duì)用戶位置進(jìn)行泛化，因此，隱匿區(qū)域的大小則是衡量位置數(shù)據(jù)精度的依據(jù)．隱匿區(qū)域越大，精度越低；反之區(qū)域越小，則精度越高．在實(shí)際應(yīng)用中，最理想的精度平衡點(diǎn)是隱匿區(qū)域恰好滿足用戶的隱私要求，如用戶希望隱藏于某個(gè)公園中，則隱匿區(qū)域剛好是包圍該公園的多邊形；用戶希望隱藏于某條街道中，則隱匿區(qū)域剛好是沿著該街道的條帶狀．這樣，數(shù)據(jù)精度不僅滿足了用戶隱私要求，且最大程度地保留了位置數(shù)據(jù)精度．因此，本系統(tǒng)將采用自定義的方式，讓用戶自己指定多邊形隱匿區(qū)域，如在移動(dòng)終端設(shè)備屏幕上勾畫(huà)隱匿區(qū)域的輪廓．

1．3 服務(wù)質(zhì)量

LBS的服務(wù)質(zhì)量包括服務(wù)響應(yīng)時(shí)間和服務(wù)結(jié)果的有效性．服務(wù)響應(yīng)時(shí)間是指從用戶發(fā)出服務(wù)請(qǐng)求，到接收服務(wù)返回結(jié)果之間的時(shí)間．如果服務(wù)響應(yīng)時(shí)間太長(zhǎng)，會(huì)嚴(yán)重影響用戶的體驗(yàn)．服務(wù)結(jié)果的有效性則是指返回的結(jié)果是否正確、有效結(jié)果的比例等．如果LBS返回很多不相關(guān)的結(jié)果，不僅會(huì)增加服務(wù)器的運(yùn)算和網(wǎng)絡(luò)的負(fù)擔(dān)，而且用戶也難以從中獲取有用的信息，導(dǎo)致服務(wù)質(zhì)量的降低．

2 系統(tǒng)設(shè)計(jì)

本系統(tǒng)的架構(gòu)如圖1所示，包括客戶端、中間件和服務(wù)器3個(gè)層次．客戶端包括臺(tái)式計(jì)算機(jī)、筆記本電腦、手機(jī)、GPS等移動(dòng)設(shè)備，它提出基于位置隱私保護(hù)的查詢請(qǐng)求．中間件位于客戶端和服務(wù)器端之間，并與存儲(chǔ)用戶位置信息的移動(dòng)數(shù)據(jù)庫(kù)進(jìn)行交互．服務(wù)器處理來(lái)自客戶端的基于位置隱私保護(hù)的服務(wù)請(qǐng)求．一般地，在隱私保護(hù)的LBS系統(tǒng)中，傳統(tǒng)的基于點(diǎn)的位置查詢算法已經(jīng)不能適用，需要設(shè)計(jì)新的算法來(lái)支持基于隱匿區(qū)域的位置查詢．如在傳統(tǒng)的LBS中，原來(lái)的用戶位置是一個(gè)精確的查詢點(diǎn)，利用最鄰近查詢算法可以找出一個(gè)準(zhǔn)確的答案，比如離用戶最近的加油站等．但是，在隱私保護(hù)的LBS中，當(dāng)用戶位置是一個(gè)區(qū)域的時(shí)候，服務(wù)器不知道用戶具體在哪個(gè)點(diǎn)中，有可能會(huì)產(chǎn)生很多個(gè)結(jié)果，這就需要設(shè)計(jì)一種高效的基于隱匿區(qū)域的最鄰近查詢算法．不過(guò)，已有系統(tǒng)采用的查詢算法大都是基于圓形或矩形之類(lèi)的簡(jiǎn)單隱匿區(qū)域，無(wú)法支持本系統(tǒng)的多邊形隱匿區(qū)域．針對(duì)這點(diǎn)，我們提出了一種基于多邊形隱匿區(qū)域的查詢算法P－RNN［11］（Polygon－Range Nearest Neighbor）．本系統(tǒng)將采用該算法來(lái)支持基于多邊形隱匿區(qū)域的隱私保護(hù)查詢．

圖1 LBS系統(tǒng)架構(gòu)Fig．1 Framework of LBS system

為了同時(shí)支持Location Cloaking和K－Anonymity兩種位置隱私保護(hù)技術(shù)，進(jìn)一步保證用戶的隱私安全，本系統(tǒng)將使用雙重位置保護(hù)方法，分別在客戶端和中間件進(jìn)行一次位置保護(hù)．如圖2所示，在客戶端，通過(guò)Location Cloaking方法生成隱匿區(qū)域CR（Cloaking Region）；而在中間件層，則根據(jù)CR和K－Anonymity的參數(shù)K生成KCR（K－Anonymity Cloaking Region）．

圖2 LBS系統(tǒng)的序列UMLFig．2 Sequential UML of LBS system

（1）客戶端

客戶端是用戶進(jìn)行LBS操作的人機(jī)交互層，它結(jié)合MapInfo格式的電子地圖，安裝在手機(jī)、筆記本電腦、GPS等移動(dòng)終端設(shè)備上．客戶端軟件支持電子地圖的縮放、移動(dòng)和定位操作，并且提供用戶自定義隱匿區(qū)域功能．用戶可以通過(guò)觸摸屏、鼠標(biāo)等方式在移動(dòng)終端設(shè)備的屏幕上繪制所需要的隱匿區(qū)域CR，并選擇相應(yīng)的查詢服務(wù)類(lèi)型，如最鄰近查詢等；然后與K－Anonymity參數(shù)一起發(fā)送給LBS中間件．當(dāng)查詢完成，返回結(jié)果集時(shí)，客戶端會(huì)根據(jù)用戶的準(zhǔn)確位置對(duì)結(jié)果進(jìn)行篩選，只有符合查詢要求的結(jié)果才會(huì)顯示到電子地圖中．LBS客戶端處理流程如圖3所示．

圖3 LBS客戶端流程圖Fig．3 Diagram of LBS dient

（2）中間件

中間件作為一個(gè)可信的第三方平臺(tái)，位于客戶端和服務(wù)器之間，主要是使用K－Anonymity方法對(duì)用戶的CR進(jìn)行進(jìn)一步處理．為此，中間件需要收集用戶大量的CR信息，且由于用戶是處于不斷移動(dòng)的狀態(tài)，其CR會(huì)經(jīng)常改變，如進(jìn)行第二次查詢時(shí)用戶重新繪制了CR等．本系統(tǒng)在中間件內(nèi)部建立一個(gè)移動(dòng)數(shù)據(jù)庫(kù)，用于保存移動(dòng)用戶的CR位置信息，并利用R－Tree等空間索引結(jié)構(gòu)對(duì)數(shù)據(jù)庫(kù)進(jìn)行索引，加速用戶位置的更新，提供快速查找某區(qū)域內(nèi)用戶信息的功能．在移動(dòng)數(shù)據(jù)庫(kù)的幫助下，中間件就可以根據(jù)用戶的CR以及K－Anonymity參數(shù)生成KCR，然后把KCR作為用戶新的位置信息，連同服務(wù)請(qǐng)求一起，轉(zhuǎn)發(fā)給LBS服務(wù)器．

（3）服務(wù)器

LBS服務(wù)器負(fù)責(zé)處理客戶端提出的用戶LBS請(qǐng)求．其內(nèi)部包含一個(gè)位置信息數(shù)據(jù)庫(kù)，用于存儲(chǔ)查詢目標(biāo)（如加油站、酒店等）的地理位置相關(guān)信息．當(dāng)接收到用戶的查詢請(qǐng)求時(shí)，服務(wù)器調(diào)用相應(yīng)的查詢算法進(jìn)行處理，并根據(jù)用戶的KCR計(jì)算出該次查詢的結(jié)果區(qū)域RR（Result Region）．RR保證無(wú)論用戶位于KCR的任何一點(diǎn)上，其查詢的正確結(jié)果都位于RR內(nèi)．因此服務(wù)器從地理信息數(shù)據(jù)庫(kù)中找出所有位于RR內(nèi)的對(duì)象，作為結(jié)果集返回給用戶．LBS服務(wù)器端的處理流程如圖4所示．

圖4 LBS服務(wù)器端流程圖Fig．4 Diagram of LBS server

為了加快最鄰近查詢的速度，保證LBS服務(wù)的有效性，系統(tǒng)為服務(wù)器端的查詢處理器設(shè)計(jì)了一種基于多邊形隱匿區(qū)域的最鄰近查詢算法：P－RNN．P－RNN算法的主要思路是對(duì)于一個(gè)多邊形區(qū)域R的最鄰近查詢，計(jì)算一個(gè)結(jié)果區(qū)域RR［11－12］，使得R中每個(gè)點(diǎn)的最鄰近目標(biāo)都位于RR中，且RR盡可能小，查詢的結(jié)果就是RR中所有目標(biāo)的集合．其中最大的困難是如何計(jì)算RR，為此算法使用點(diǎn)、線、面逐層擴(kuò)展的方式來(lái)進(jìn)行計(jì)算．

3 系統(tǒng)實(shí)現(xiàn)

系統(tǒng)的客戶端、中間件和服務(wù)器3個(gè)部分作為3個(gè)獨(dú)立子系統(tǒng)，分別使用．Net平臺(tái)中的WPF（Windows Presentation Foundation）實(shí)現(xiàn)，其中電子地圖的部分使用了MapXtreme 2008提供的編程控件．實(shí)驗(yàn)所用的地圖是廣東省的MapInfo格式電子地圖，包含了32個(gè)圖層．

3．1 客戶端

圖5 客戶端操作過(guò)程Fig．5 Operating procedure in client

客戶端是LBS系統(tǒng)進(jìn)行人機(jī)交互的界面．其通過(guò)簡(jiǎn)單的操作，為用戶提供快捷的LBS．圖5演示了操作流程：①首先要使用LBS，必須先輸入經(jīng)過(guò)注冊(cè)的用戶名，圖5例子中所使用的用戶名是“Lisya”．②點(diǎn)擊“Login”按鈕，客戶端則與服務(wù)器進(jìn)行連接，并驗(yàn)證用戶的有效性．③用戶需要設(shè)置查詢的類(lèi)型，包括最鄰近查詢和全局查詢兩種：第一，如果用戶選擇的是“Nearest”最鄰近查詢，則還需要輸入?yún)?shù)M，表示要查詢最鄰近的M個(gè)目標(biāo)；第二，如果用戶選擇的是“All”，則表示查詢所有目標(biāo)．此外，為了達(dá)到K－Anonymity的隱私保護(hù)效果，用戶還需要輸入K－Anonymity的參數(shù)K以傳遞給中間件位置隱匿器，從而將自己隱藏在一個(gè)至少有K個(gè)用戶的區(qū)域中．④通過(guò)電子地圖的移動(dòng)和縮放操作，用戶在地圖上進(jìn)行瀏覽，以顯示繪制自定義隱匿區(qū)域時(shí)的合適視圖．⑤在左側(cè)的電子地圖處，通過(guò)鼠標(biāo)或者觸控方式，結(jié)合電子地圖中的地形位置信息，繪制所需要的多邊形隱匿區(qū)域．圖5（a）電子地圖中的綠色圖釘是用戶現(xiàn)在所處的準(zhǔn)確位置，紅色的不規(guī)則多邊形是用戶所繪制的隱匿區(qū)域．⑥在搜索欄輸入查詢關(guān)鍵詞，如要搜索最鄰近的酒店，則輸入“酒店”．最后按下按鈕“Search Map”，則用戶的LBS請(qǐng)求將經(jīng)過(guò)中間件發(fā)送給服務(wù)器．⑦如圖5（b）所示，當(dāng)客戶端接收到LBS的服務(wù)結(jié)果后，會(huì)在結(jié)果欄中顯示，如例子中搜索“醫(yī)院”關(guān)鍵詞后，服務(wù)返回5個(gè)和“醫(yī)院”相關(guān)的結(jié)果，并在結(jié)果欄中顯示出來(lái)．用戶通過(guò)電子地圖可以查詢查詢目標(biāo)的位置分布（圖5（b）中的紅色圖釘）．用戶若需要進(jìn)一步了解相關(guān)結(jié)果的信息，還可以通過(guò)圖5（b）中的“第7部分”對(duì)目標(biāo)進(jìn)行定位．

3．2 中間件

中間件的主要功能是在隱匿區(qū)域的基礎(chǔ)上，為用戶生成一個(gè)具有K－Anonymity性質(zhì)的隱匿區(qū)域．以圖6為例，在用戶Lisya發(fā)送LBS請(qǐng)求前，用戶的在線情況如圖6（a）所示．當(dāng)請(qǐng)求發(fā)送給中間件后，移動(dòng)數(shù)據(jù)庫(kù)記錄下Lisya的位置，并對(duì)Lisya所在區(qū)域放大后得到圖6（b）．可見(jiàn)Lisya處于一個(gè)較繁華的地方，附近有很多其他用戶，如User039、User040、User053等．由于Lisya的K－Anonymity參數(shù)為5，中間件通過(guò)使用貪心策略，合并擴(kuò)展耗費(fèi)最小的另外4個(gè)用戶區(qū)域作為L(zhǎng)isya的KCR．圖6（c）中的藍(lán)色區(qū)域就是Lisya與User039、User040、User041、User053進(jìn)行合并得到的KCR．在生成KCR后，中間件就為用戶轉(zhuǎn)發(fā)LBS請(qǐng)求給服務(wù)器．

3．3 服務(wù)器

服務(wù)器在接收到中間件轉(zhuǎn)發(fā)的LBS請(qǐng)求后，調(diào)用基于多邊形隱匿位置的查詢算法處理相關(guān)請(qǐng)求．把圖6（c）中Lisya所在位置縮小后，得到圖7．本算法根據(jù)Lisya的位置以及請(qǐng)求參數(shù)，為L(zhǎng)isya生成一個(gè)結(jié)果區(qū)域RR，區(qū)域內(nèi)有很多醫(yī)院，其中包含了滿足Lisya要求的前5個(gè)最鄰近的醫(yī)院，但是不知道具體是哪5個(gè)．最后服務(wù)器將深綠色區(qū)域內(nèi)的所有醫(yī)院都返回給Lisya，讓Lisya的客戶端程序自動(dòng)篩選（如圖5（b）所示）．至此，一次LBS請(qǐng)求的處理完成．

4 系統(tǒng)性能測(cè)試

我們對(duì)系統(tǒng)性能進(jìn)行了評(píng)估，收集了1 000個(gè)LBS的測(cè)試數(shù)據(jù)，其中用戶的多邊形隱匿區(qū)域的平均頂點(diǎn)個(gè)數(shù)為16個(gè)，平均K－Anonymity參數(shù)是3，網(wǎng)絡(luò)平均延遲為20 ms．實(shí)驗(yàn)分別對(duì)數(shù)據(jù)傳輸、KCR生成以及P－RNN算法等部分進(jìn)行了測(cè)試，結(jié)果如表1所示．

圖6 中間件KCR生成過(guò)程Fig．6 Generating procedure of KCR middleware

圖7 LBS請(qǐng)求處理Fig．7 Answer of LBS request

表1 系統(tǒng)各部分測(cè)試Tab．1 Tests on each part of system

圖8 LBS系統(tǒng)各部分用時(shí)百分比Fig．8 Percentages of each part of LBS system

與大多數(shù)網(wǎng)絡(luò)應(yīng)用一樣，系統(tǒng)中數(shù)據(jù)傳輸部分耗費(fèi)時(shí)間最多，成為性能的主要瓶頸．如圖8所示，網(wǎng)絡(luò)耗費(fèi)占了整個(gè)LBS過(guò)程的65%，其中客戶端與中間件之間、中間件與服務(wù)器之間的數(shù)據(jù)傳輸量較小，主要是多邊形隱匿區(qū)域以及服務(wù)請(qǐng)求參數(shù)的傳輸，它們的耗費(fèi)時(shí)間大部分用于建立TCP網(wǎng)絡(luò)連接．而服務(wù)器與客戶端之間是以搜索結(jié)果中的位置信息為傳輸對(duì)象，傳輸量較大，耗時(shí)較多，傳輸耗費(fèi)時(shí)間與搜索結(jié)果集的大小成正相關(guān)．KCR的生成相對(duì)于網(wǎng)絡(luò)數(shù)據(jù)傳輸來(lái)說(shuō)，所耗費(fèi)的時(shí)間比較小，原因是中間件使用了R－Tree空間索引，加速了鄰近用戶的查找．同樣是使用了索引進(jìn)行加速的查詢處理算法則耗費(fèi)較高，主要是因?yàn)椴樵兯惴ㄐ枰獙?duì)每個(gè)頂點(diǎn)進(jìn)行一次點(diǎn)最鄰近查詢操作．在本實(shí)驗(yàn)中，平均每次查詢算法都要進(jìn)行16次點(diǎn)最鄰近查詢．當(dāng)KCR的多邊形頂點(diǎn)個(gè)數(shù)增多時(shí)，算法所耗費(fèi)的時(shí)間也將按比例增加．與已有的矩形隱匿區(qū)域相比，這是多邊形隱匿區(qū)域的缺點(diǎn)，同時(shí)多邊形隱匿區(qū)域也有著矩形隱匿區(qū)域無(wú)法替代的優(yōu)點(diǎn)．在查詢算法生成結(jié)果區(qū)域RR后，服務(wù)器需要獲取RR中的所有查詢目標(biāo)，RR越大，目標(biāo)數(shù)量也越多．因此這部分消耗時(shí)間與RR的大小成正相關(guān)．總體來(lái)看，本系統(tǒng)能夠有效支持基于多邊形隱匿區(qū)域的LBS查詢．

5 總 結(jié)

本文針對(duì)已有隱私保護(hù)的LBS系統(tǒng)的不足，設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)基于多邊形隱匿區(qū)域的LBS系統(tǒng)．該系統(tǒng)采用客戶端、中間件與服務(wù)器3層結(jié)構(gòu)，在客戶端和中間件分別進(jìn)行一次位置泛化，對(duì)用戶的位置隱私進(jìn)行雙重保護(hù)．其中，客戶端支持自定義的隱匿區(qū)域，服務(wù)器端則支持處理基于多邊形隱匿區(qū)域的查詢處理．最后，對(duì)系統(tǒng)性能進(jìn)行了測(cè)試，結(jié)果表明了系統(tǒng)的有效性．

［1］周傲英，楊彬，金澈清，馬強(qiáng)．基于位置的服務(wù)：架構(gòu)與進(jìn)展［J］．計(jì)算機(jī)學(xué)報(bào)，2011，34（7）：1155－1171．

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

［3］黃毅，霍崢，孟小峰．CoPrivacy：一種用戶協(xié)作無(wú)匿名區(qū)域的位置隱私保護(hù)方法［J］．計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1977－1985。

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

［5］MOKBEL M F，CHOW C，AREF W G．The new casper：Query processing for location services without compromising privacy［C］／／Proceedings of the 32nd Internationl Conference on Very Large Date Bases．ACM，2006：763－774．

［6］CHOW C Y，MOKBEL M F，HE T．Tinycasper：A privacy－preserving aggregate location monitoring system in wireless sensor networks［C］／／Proceedings of the 2008 ACM SIGMOD Internationl Conference on Management of Date．ACM，2008：1307－1310．

［7］GHINITA G，KALNIS P，SKIADOPOULOS S．PRIVE：Anonymous location－based queries in distributed moblile systems［C］／／Proceedings of the 16th International Conference on World Wide Web．ACM，2007：371－380．

［8］張鵬，童云海，唐世渭，等．一種有效的隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘方法［J］．軟件學(xué)報(bào)，2006，17（08）：1164－1774．

［9］GAO J，YU J X，JIN R M，et al．Neighborhood－privacy protected shortest distance computing in cloud［C］／／Proceedings of the 2011 ACM SIGMOD Internationl Conference on Management of Date．ACM，2011：409－420．

［10］王璐，孟小峰．位置大數(shù)據(jù)隱私保護(hù)研究綜述［J］．軟件學(xué)報(bào)，2014，25（4）：693－712．

［11］LIU Y，CHEN X，LI Z，et al．An efficient method for privacy preserving location queries［J］．Frontiers of Computer Science，2012，6（4）：409－420．

［12］陳修偉．基于多邊形隱匿區(qū)域的定位服務(wù)研究［D］．廣州：中山大學(xué)，2010．