路網(wǎng)環(huán)境中基于Voronoi圖的位置隱私保護算法

檀童和　重慶郵電大學通信與信息工程學院碩士研究生李志立　重慶郵電大學通信與信息工程學院碩士研究生蘇艷濤　重慶郵電大學通信與信息工程學院碩士研究生

?

路網(wǎng)環(huán)境中基于Voronoi圖的位置隱私保護算法

檀童和重慶郵電大學通信與信息工程學院碩士研究生
李志立重慶郵電大學通信與信息工程學院碩士研究生
蘇艷濤重慶郵電大學通信與信息工程學院碩士研究生

摘要：位置隱私保護和基于位置的服務的查詢服務質(zhì)量是矛盾的，在實際的路網(wǎng)環(huán)境下，需要考慮到諸多的影響因素對位置隱私保護算法的影響。在追求位置隱私保護的過程中，如何在提供用戶隱私保護的同時保證查詢服務質(zhì)量是近年來的研究熱點。利用泰森多變形（Voronoi）劃分平面區(qū)域的方法對路網(wǎng)圖進行劃分，可以在減小匿名區(qū)域的同時提高抗邊權(quán)攻擊能力；采用匿名區(qū)域擴展和生成啞元的融合方式來構(gòu)造匿名框。只有在劃分單元內(nèi)用戶數(shù)量嚴重不足的情況下，才進行劃分區(qū)域擴展。仿真結(jié)果表明本文算法在保護用戶位置隱私方面和抗邊權(quán)攻擊方面有明顯的優(yōu)勢。

關(guān)鍵詞：基于位置的服務；V圖；邊權(quán)攻擊；路網(wǎng)

1　引言

隨著無線通信技術(shù)和移動終端的迅速發(fā)展，移動終端給人們的生活帶來了很大的便利。定位技術(shù)（GPS、Wi-Fi、蜂窩網(wǎng)）的成熟，使得移動終端（智能手機、平板電腦）能夠及時、準確地獲得自己的位置信息。因此，基于位置的服務得到廣泛的應用。在享受位置服務的時候，移動用戶必須將自己的準確位置信息以及自己的查詢內(nèi)容提供給位置服務提供商，但是不能保證位置服務提供商是可信的，一旦位置信息暴露必然會導致其余相關(guān)信息的泄露。

近年來，在路網(wǎng)環(huán)境下，研究者提出了很多的位置隱私保護算法，TingWang等提出了路網(wǎng)環(huán)境下的“路段多樣性”思想，構(gòu)造的匿名框需要包含l條路段，從而增強抗路段推斷攻擊的能力。為了能夠提高抗路段推斷攻擊的能力，提出了“匿名蜂窩模型”，先對路網(wǎng)進行蜂窩劃分，然后根據(jù)相鄰路徑優(yōu)先成組的方式構(gòu)成匿名集合。蜂窩劃分存在以下缺點：蜂窩是根據(jù)到其它節(jié)點的距離來構(gòu)造的，如果路段過長，匿名區(qū)域過大就會過大，這就造成服務質(zhì)量下降；存在蜂窩區(qū)域相互覆蓋，用戶在進行匿名時，需要進行蜂窩的選擇，增加搜索成本；蜂窩劃分，存在死角，有部分用戶不屬于任何蜂窩，造成匿名失敗。本文提出了“匿名環(huán)”和“匿名森林”圖的結(jié)構(gòu)，構(gòu)造匿名環(huán)路和匿名森林，并將其發(fā)送給匿名服務器。但是構(gòu)造匿名環(huán)和匿名森林存在以下缺點：每條路徑上的用戶數(shù)分布不均勻，容易導致邊權(quán)攻擊的發(fā)生；部分路段過長，會匿名區(qū)域過大，增大系統(tǒng)開銷，降低服務質(zhì)量。在星型擴展模型的基礎上，提出了XStar算法模型，XStar模型能夠很好地平衡服務質(zhì)量和抗攻擊能力之間的關(guān)系，但是該算法有以下缺點：沒有密集的路段分叉結(jié)構(gòu)，不能很好地保證匿名集內(nèi)路段的多樣性；搜索用戶時，沒有考慮用戶分布情況。另外，本文提出了匿名算法，該方法能夠很好地保障路段多樣性，不存在V區(qū)重合和部分用戶不在V區(qū)的情況，但是存在以下缺點：對V區(qū)用戶進行整體匿名，匿名框用戶數(shù)過多，影響匿名服務質(zhì)量；算法只考慮到空間容忍度，沒有考慮到邊權(quán)攻擊的情況。本文還提出了基于Voronoi劃分的V-W隱私保護算法，該算法利用Voronoi圖劃分法構(gòu)造V區(qū)，這在減小搜索區(qū)域和抗邊權(quán)攻擊方面有比較明顯的優(yōu)勢，但是該算法在形成匿名框時并未考慮到個別路段跨越多個V區(qū)，這將會增加后期的搜索成本，該算法在本V區(qū)用戶數(shù)不夠的情況下，采用V區(qū)擴展方式來達到高的匿名成功率，這將造成匿名框區(qū)域過大，造成后期較大的搜索成本。

這些算法存在以下問題：沒有考慮到可能存在的邊權(quán)攻擊；只是一味地擴大匿名區(qū)域來達到匿名需求，沒有考慮到服務質(zhì)量與匿名需求之間的平衡。

結(jié)合現(xiàn)有的路網(wǎng)位置隱私保護算法存在的一些問題，本文算法在位置隱私保護方面，將k-匿名模型和l-匿名相結(jié)合，k-匿名實現(xiàn)集體匿名，形成匿名框；l-匿名能夠保證匿名框內(nèi)路段的多樣性。本算法有以下特征：采用數(shù)學上的泰森多邊形方法（Voronoi）對路網(wǎng)圖進行劃分，形成一個個小的V圖區(qū)域，這就有效保證匿名框內(nèi)路段的多樣性；采用平均信息熵來衡量抗邊權(quán)攻擊能力，在算法中通過構(gòu)造候選匿名集的方法來提高抗邊權(quán)攻擊的能力；通過仿真驗證了本算法具有很好的匿名成功率并且能很好地保護用戶隱私。

2　Voronoi劃分理論

Voronoi是最早由荷蘭氣候?qū)W家A·H·Thiessen提出的根據(jù)離散分布的氣象站的降雨量來計算平均降雨量的方法。后期被用于平面的劃分，設某平面區(qū)域Q包括n個點，表示為集合P=｛P1，P2，…Pn｝，以這n個點為中心對平面進行劃分形成一個個的Voronoi區(qū)域（簡稱V區(qū)）V（P1），V（P1）為平面內(nèi)所有到P1距離最近的點的集合：，P1為V圖的生成元。

3　系統(tǒng)模型

位置隱私保護模型中，中心匿名服務器結(jié)構(gòu)應用最為廣泛。中心匿名服務器結(jié)構(gòu)能夠處理能力強，能降低移動終端的負擔。系統(tǒng)包括用戶端、中心匿名服務器、LBS服務器3部分，具體參見圖1。

圖1　中心服務器結(jié)構(gòu)系統(tǒng)模型

匿名過程如下：移動終端提交請求信息（＜ID，Loc（x，y），k，l，query＞）到中心匿名服務器；中心匿名服務器運行EVW匿名算法，產(chǎn)生匿名集合S。中心匿名服務器將用戶ID、S、query發(fā)送到LBS服務器；LBS服務器將查詢結(jié)果返回給中心匿名服務器，中心匿名服務器完成結(jié)果的求精；中心匿名服務器將求精結(jié)果發(fā)送給請求用戶，完成整個匿名過程。

4　匿名算法

為了解決V-W算法形成匿名框過大導致查詢復雜度增高的問題，本文對V-W算法進行改進。不同于V-W算法，EVW算法在添加路段加入匿名框時，不再是將整條路段加入匿名框，而是將V區(qū)內(nèi)部分路段加入匿名框；在需要進行V區(qū)擴展時，EVW算法需要對V區(qū)用戶的數(shù)目進行一個判斷，只有在嚴重缺少用戶時才進行V區(qū)擴展。EVW算法這兩點改進均能在保證匿名成功率的情況下有效的減輕后期K近鄰（KNearest Neighbors，KNN）搜索的難度，從而提高基于位置服務的查詢質(zhì)量。匿名算法參見表1。

5　仿真分析

為了證明所提算法的性能，給出算法的匿名成功率、匿名時間、相對匿名率、邊權(quán)推斷攻擊平均信息熵，并與傳統(tǒng)的匿名蜂窩算法、匿名環(huán)算法、V-W算法作比較。

（1）試驗環(huán)境及參數(shù)設置（見表2）

本文采用重慶市主城區(qū)路網(wǎng)圖作為仿真對象（見圖2），試驗用戶數(shù)據(jù)由Thomas Brinkhoff移動對象生成器產(chǎn)生，重慶市主城路網(wǎng)用戶的分布情況參見圖3。

（2）匿名成功率

表1　算法1

匿名成功率表示用戶向系統(tǒng)提交匿名申請時，匿名服務器能為其成功匿名的概率，匿名成功率越高，系統(tǒng)性能越好。圖4所示為系統(tǒng)匿名成功率曲線圖，圖4（a）顯示了系統(tǒng)匿名成功率隨平均k匿名需求變化情況。由圖4可知，隨著k值增大，匿名成功率稍微有點下降，這是由于隨著系統(tǒng)匿名需求的增大，即使選中所有路段，用戶數(shù)目還是不能滿足匿名需求，與V-W算法相比，本文算法匿名成功率稍低，這是由于在選擇路段時，只選擇V區(qū)內(nèi)用戶，這樣在k匿名指標上更不容易達到，但是本文算法匿名成功率總體維持在90%；圖4（b）顯示了系統(tǒng)匿名成功率隨l值變化的情況，很顯然隨著路段要求的提高匿名成功率下降很快，這是由于隨著用戶路段數(shù)要求的提高，即使將附近V區(qū)都擴展后仍然無法滿足路段數(shù)要求。本文算法為了保證服務質(zhì)量，盡量不進行V區(qū)擴展，因此在匿名成功率上稍微低于其它3種算法。

表2　試驗環(huán)境及參數(shù)設置

圖2　重慶市主城路網(wǎng)V圖

圖3　重慶市主城路網(wǎng)用戶分布

（3）平均匿名時間

平均匿名時間平均完成一次匿名所消耗的系統(tǒng)時間，時間越短，系統(tǒng)的性能越好。圖5所示為系統(tǒng)平均匿名時間曲線圖，圖5（a）為平均匿名時間隨k值的變化情況，平均系統(tǒng)匿名時間隨著k值的增大而增大，這是由于k需求增大，系統(tǒng)需要花費更多的時間去搜索匿名路段，甚至是進行V區(qū)擴展。圖5（b）為平均匿名時間隨l值的變化情況，隨著l值的增加平均匿名時間逐漸增加，這與圖5（a）這種趨勢的原因是一樣的。由圖5可知，本文算法在平均匿名時間上比匿名環(huán)算法和匿名蜂窩算法顯著減少，這是由于本文算法并未一味的追求匿名成功率，而是在保證匿名成功率的同時，不進行區(qū)域的再一步擴大，這樣從另一方面提高了服務質(zhì)量。與V-W算法相比，平均匿名時間稍高，這是由于在生成假用戶后，后面的匿名條件仍然不能滿足匿名需求，還是需要進行V區(qū)擴展，這就浪費了一部分時間。但是時間相差并不是很多。

圖4　系統(tǒng)匿名成功率曲線圖

圖5　系統(tǒng)平均匿名時間

（4）相對匿名度

相對匿名度分相對k匿名度Relk和相對l匿名度Rell。Relk表示匿名成功時，匿名集內(nèi)用戶數(shù)nk與用戶提出的k匿名需求ki的比值，相應的Rell表示匿名集內(nèi)路段數(shù)ni與用戶提出的l匿名需求li的比值。很顯然，Relk、Rell的值越接近1則表明匿名效果最好，Relk、Rell值的偏大會導致匿名區(qū)域的擴大，降低服務質(zhì)量，圖6顯示了本文算法的Relk、Rell值與匿名蜂窩算法相似，明顯優(yōu)于匿名環(huán)算法和V-W算法。本文算法相比V-W算法之所以能在相對匿名度上有明顯改進，原因是在向匿名集添加用戶時，本文算法沒有采取整條路段的添加方法。

圖6　系統(tǒng)相對匿名率

（5）邊權(quán)攻擊平均信息熵

邊權(quán)攻擊平均信息熵表示系統(tǒng)抗邊權(quán)推斷攻擊的能力，攻擊者利用背景知識及獲取的匿名集信息推斷出用戶分布于每條路段上的概率Pib如公式（1）所示，式中ei.w表示第i條路段上的用戶數(shù)目，用邊權(quán)推斷平均信息熵He表示推斷出用戶所在路段的不確定度，如公

圖7所示為平均邊權(quán)推斷攻擊信息熵曲線圖，圖7 （a）為平均邊權(quán)推斷攻擊信息熵隨k值的變化情況。隨著k值的變化平均邊權(quán)推斷攻擊信息熵變化不大，這是由于各路段用戶數(shù)目均足夠多；隨著k值的變化，路段數(shù)并不會出現(xiàn)明顯的變化。圖7（b）為平均邊權(quán)推斷攻擊信息熵隨l值的變化情況，隨著l值的增大，平均邊權(quán)推斷攻擊信息熵顯著增大，這是由于路段數(shù)的增加會直接增加用戶路段分布的隨機性。由于V-W算法和本文算法都考慮到選擇用戶數(shù)目相等的路段來構(gòu)造匿名框，所以平均邊權(quán)推斷攻擊信息熵明顯高于匿名環(huán)算法和匿名蜂窩算法。本文算法由于在構(gòu)造匿名框時，只選擇V區(qū)內(nèi)路段構(gòu)造匿名框，相近路段用戶分布情況類似，所以這能夠稍微提高平均邊權(quán)推斷攻擊信息熵。

6　結(jié)束語

本文算法針對V-W算法進行改進，構(gòu)造匿名框時，僅選擇V區(qū)內(nèi)部分加入準匿名集，在V區(qū)用戶缺少不是很多情況下生成啞元。仿真試驗證明，本文算法相比V-W算法在匿名成功率和平均匿名時間方面相差不大，但在相對匿名率方面和抗邊權(quán)攻擊方面有較大優(yōu)勢，因此本文算法更適合路網(wǎng)位置隱私保護環(huán)境。

參考文獻

［1］徐健，徐明，林欣.路網(wǎng)限制環(huán)境下基于匿名蜂窩的位置隱私保護［J］.浙江大學學報，2011，45（3）:429-434.

［2］薛姣，劉向宇，楊曉春.一種面向公路網(wǎng)絡的位置隱私保護方法［J］.計算機學報，2011，34（5）:865-878.

［3］Al-Amin Hossain，Amina Hossain，Hye-KyeomYoo，Jae-Woo Chang.H-star:Hilbert-orderbasedstarnetworkexpansioncloaking algorithm in road networks［C］. Computational Science and Engineering（CSE 2011），2011 International Conference on. IEEE，2011:81-88.

［4］T Wang，L Liu. Privacy- aware mobile services over road networks［J］. Proceedings of the VLDB Endowment，2009，2（1）: 1042-1053.

［5］趙平，馬春光，高訓兵.路網(wǎng)環(huán)境下基于Voronoi圖的位置隱私保護方法［J］.計算機科學，2013，40（7）:116-120.

［6］Xinyue Fan， Jin Tu， Chaolong Ye， Fei Zhou. The research for protecting location privacy based on V-W algorithm［J］. Eurasip Journal on Wireless Communications and Networking，2014（1）: 1686-1706.

［7］Jung- Ho Um， Mi- Young Jang， Kyoung- Jin Jo， Jae- Woo Chang.Anew cloaking method supporting both K-anonymity and L-diversity for privacy protection in location-based services［C］. Parallel Distributed Processing with Applications， 2009 InternationalSymposiumon. IEEE，2009:79-85.

［8］Xinxin Liu， Xiaolin Li. Privacy preserving techniques for location based services in mobile networks［C］. Parallel and Distributed Processing Symposium Workshops PhD Forum （IPDPSW）， 2012 International Conference on. IEEE， 2012:2474- 2477.

［9］Chunguang Ma， Changli Zhou， and Songtao Yang.Avoronoibased location privacy-preserving method for continuous query in LBS［J］.International Journal of Distributed Sensor Networks， 2015，2015:1-17.

［10］Chow Chi-Yin， Mokbel Mohamed， Bao Jie， Liu Xua. Queryaware location anonymization for road networks［J］. GeoInformatica， 2011，15（3）:571-607.

［11］Atsuyuki Okabe， Barry Boots， Kokichi Sugihara. Spatial tessellations concepts and applications of voronoi diagrams［M］. Tokyo:Wiley，2000:65-115.

Location privacy protection through voronoimapcells in road network

TanTonghe， Li Zhili ，SuYantao

Abstract：Location privacy protection and query service quality of location based services is contradictory， in the actual network environment， many factors on the influence of location privacy protection algorithm should be considered. How to provide user privacy protection and ensure the quality of the query service at the same time is a hot research topic in recent years. The method of using voronoi map to divide network diagram can reduce the anonymous area and improve the edge weight attack resistance at the same time， the fusion way using of the anonymous regional extension and generating dummy is used to generate anonymous frame structure. The way of voronoi cell extension can be used under the condition of serious shortage of the number of users.The simulation results show the obvious advantage of the algorithm at location privacy protection and edge weight attack resistance.

Keywords：location based service（LBS）； voronoimap；edge weight inference； road network

收稿日期：（2016-02-20）