基于位置隱私保護的模糊查詢方法

王鑫 余翔湛

摘要：隨著基于位置的服務（location-based services，簡稱LBS）的廣泛應用，個人位置信息的保護越來越受到人們關注。在LBS服務中，常常會遇到“誰附近有什么資源”的問題，“誰”代表實體位置，“什么”代表服務請求。在“誰附近有什么”的信息查詢服務過程中，如何在保護“誰”的基礎上提供相對可靠的服務，將是本文的研究重點。針對這一問題，用模糊集來實現對“誰”的保護，并針對模糊集，提出一種基于位置隱私保護的模糊查詢方法，在模糊位置信息的基礎上提供相對可靠的服務，并在一定程度上實現了位置隱私保護和位置服務質量之間的平衡。最后，通過相關實驗來評估該方法的性能。

關鍵詞：模糊集； 位置隱私保護； 模糊查詢； 服務質量

中圖分類號：TP393 文獻標識碼：A文章編號：2095-2163（2013）06-0021-04

0引言

近年來，基于位置的服務（location-based services，簡稱LBS[1]）不斷發(fā)展，用以實現物聯網中的實時、快速、可擴展的物體位置搜索。但是，由于用戶在使用LBS服務時，需要向LBS服務器提供自身的位置信息，而LBS服務器又不是絕對可靠的，有可能將收集的用戶位置信息泄露給攻擊者，所以在使用LBS服務的同時，服務泄露或非法使用用戶位置信息的情況也接踵而來，基于位置的服務給用戶的位置隱私帶來了極大的威脅。

在LBS服務中，主要有三大目標：你在哪里（空間信息）、你和誰在一起（社會信息）、誰附近有什么資源（信息查詢）。本文主要解決“誰附近有什么資源”的問題，首先要明確兩個參數：“誰”和“什么”，“誰”代表實體位置，“什么”代表服務請求。

在“誰附近有什么”的信息查詢服務過程中，如何在保護“誰”的基礎上提供相對可靠的服務，將是本文的研究重點。針對這一問題，本文提出一種基于位置隱私保護的模糊查詢方法，在模糊位置信息的基礎上提供相對可靠的服務，并于一定程度上實現了位置隱私保護和位置服務質量之間的平衡。

1位置隱私保護服務結構

由于LBS服務器是不可信任的，因此需要在用戶和LBS服務器之間添加一個可信任的模糊服務器，該模糊服務器在用戶和LBS服務器之間可起到防火墻的作用。由用戶、模糊服務器和LBS服務器所組成的位置隱私保護服務結構[2]如圖1所示。

該結構中模糊服務器工作如下：

（1）收集用戶發(fā)送來的位置服務請求信息，將這些信息存儲在服務器中；

（2）對用戶發(fā)送過來的位置服務請求信息中的真實位置信息進行模糊，用空間模糊集進行代替，從而保護實體位置信息，最后將模糊過后的位置服務請求發(fā)送給第三方的LBS提供商的位置服務器；

（3）對第三方LBS提供商的位置服務器發(fā)回的基于模糊集的服務應答結果集進行接收，并根據用戶需求對應答結果集進行過濾，找到相對合理的應答結果，再將此結果發(fā)送給用戶。

根據位置隱私保護服務結構的要求，首先需要對用戶真實位置信息進行模糊。本文采用已有的k-匿名技術[3]來構造實體模糊集，以達到模糊效果。

k-匿名通過概括和隱匿技術[4]，發(fā)布精度較低的數據，使得每條記錄至少與數據表中其他k-1條記錄具有完全相同的標識屬性值，從而減少鏈接攻擊所導致的隱私泄露。k-匿名技術可以保證每一個體的敏感屬性隱藏在規(guī)模為k的群體中，這樣，個體能夠得到確認的幾率將不會超過1/k。目前的k-匿名技術主要是利用兩種方法來實現匿名：泛化[5]和隱匿技術。本文采用Datafly泛化算法[6]，根據k-匿名的要求，計算得到每個屬性出現的概率，然后對不滿足要求的屬性做泛化處理，直到該屬性滿足 k-匿名的要求為止，從而得到規(guī)模為k的模糊集。

3基于位置隱私保護的模糊查詢方法

利用K-匿名算法構造完實體位置模糊集之后，LBS服務器需要針對整個模糊集來提供“附近有什么”的查詢服務，而如何在模糊集基礎上提供盡可能良好的服務即成為問題關鍵。針對這一問題，本文提出一種基于位置隱私保護的模糊查詢方法—FCM方法，該方法可以嵌入到LBS服務器當中，通過計算模糊集到附近服務請求點的最短路徑長度來提供相對可靠的查詢服務，使得在保護實體真實位置的同時，又提供了較為良好的服務。

FCM計算方法是針對模糊集進行計算的，傳統(tǒng)Dijkstra算法[7]是針對點進行計算，與其有相似之處，所以本文FCM計算方法借鑒了傳統(tǒng)的Dijkstra算法，但是由于Dijkstra算法以起點為中心向外層層擴展，需要遍歷計算所有節(jié)點，過于繁瑣。在實際應用當中，面對大量節(jié)點，使用Dijkstra算法查找最短路徑時需耗費大量的時間進行數據的比較，搜索速度較慢，效率較低，FCM計算方法對此進行了改進，以降低搜索復雜程度。

由于FCM需要計算模糊集合到服務請求點的最短路徑距離，而對于模糊集合O中的不同點，到附近服務點（如附近餐廳）的最短路徑長度也是不一樣的，如何在眾多的附近服務點中選擇合適的服務點返回給用戶就成為求解的關鍵，考慮到服務質量問題，需要首先對模糊集進行劃分。

3.1模糊集劃分

對模糊集O進行劃分，需要構建對于請求點集合Q在關系δ上的劃分△。

關系δ定義如下：δ∈O*O，對任意o1，o2∈O，o1δ o2當且僅當min（o1）=min（o2）。o1δ o2可以理解為對于某個請求來說，o1和o2的最短路徑距離是相等的。其中函數min描述如下：min：O→Q，min（o） →q1表示對任意o∈O，滿足d（o， q1）< d（o， q1），假設q1，q2∈Q，而且d（o， q1）≠d（o， q1）。其中d表示最短路徑長度。

根據關系δ，可以得到劃分△：

（1）計算實體位置模糊集O中各點到請求集合Q的最短路徑距離，得到序對，即oi的最短路徑距離的終點是qj；

（2）遍歷所有的序對，將終點相同的起點歸為一類；

（3）得到劃分結果△，其中o∈[o]，對任意o∈O 。

3.2FCM計算方法

在劃分的基礎上，FCM可以在眾多附近服務點中選擇最適合的點返回給用戶，由此使得服務的可靠性有所提升。

為了便于研究，如圖2所示，設置一個虛擬點s，將s和請求集合Q中的點以權重為0.0的邊連接起來。

在實際計算中，可以先計算點s到模糊集O中各點的最短路徑距離，然后將最短路徑逆序，轉化為從集合O中各點到虛擬點s的最短路徑距離，則逆序后的最短路徑中倒數第二個點必然是集合Q中的點。

FCM計算方法描述如下：

算法輸入：用來表示二維空間的邊權值圖G = （V， E）；模糊點集合OV，且實體位置 l∈O；請求點集合 QV

算法輸出：

（1）關系δO×O，o1，o2∈O，o1 δ o2當且僅當min（o1） = min（o2）；

（2）序對，C∈（0.0，1.0]表明q為實體請求點的可能程度。

1. 構建圖G′=（V′，E′），其中S={s}×QV′=V∪{s}，E′=E∪S 。

2. 假設G′中任意兩節(jié)點間總會有一條通路，即使不可直達，也可以繞路到達。

3.從s出發(fā)，利用貪心策略選擇一條可達o1的路徑，記錄路徑長度，作為限界bound。

4.返回s根節(jié)點，構建解空間樹，定義活節(jié)點表PT，解向量為X=（x1，…，xn），xi的取值范圍為Si，|Si|=ri。

5.從根結點出發(fā)，擴展根結點的r1個孩子節(jié)點，從而構成分量x1的r1種可能的取值方式。

6.對每一個孩子結點x，計算根結點到其的路徑長度。

7.若某孩子結點的路徑長度權值超出bound，則將該孩子結點丟棄，剪掉分支；否則，將該孩子結點加入表PT中。

8.繼續(xù)擴展，不斷重復7過程，直到rn為葉子節(jié)點時，檢查其路徑長度，如果小于bound，則更新bound值。

9.取PT表中的第一個節(jié)點作為擴展的根節(jié)點，重復5。直到得到一個最優(yōu)解X=（x1，…，xn），記錄最短路徑長度，為最終bound′。

10.重復上述過程，可得s到O中其它各點的最短路徑距離。

11. 定義second：O→Q，second（o）→vq，其中vq是從s到o的最短路徑上的第二個點，這個點必在集合Q中。

12.o1，o2∈O，o1 δ o2當且僅當second（o1） = second（o2），此時劃分O/δ構建完畢。

13. if O∈O/δ then（最多的劃分是|O|）

14.return ，其中，o∈O ，q=min（o） 。

15. else

16.（if 用戶同意標識位置l所在的分類[l]∈O/δ then

17.return ，其中，o∈[l] ，t=min（o） 。

18. else

19.return ，對于不同的Δ， o∈O，使得q=min（o）且 Ci=Area[oi]/Area[O]最大。

FCM方法中3-10步驟計算虛擬點s到模糊集O中各點的最短路徑距離，11-12步驟將模糊集O按照關系δ進行劃分，13-19步驟在請求集合Q中選擇合適的點返回，如果劃分O/δ只有一個，那么必然是O（line 13），說明任意o1，o2∈O，o1δ o2，O中任何一個點均可代替實體位置，選擇q=min（o） （line 14）成立的點返回。當存在多個劃分結果時，如果用戶同意標識自己所在的分類[l]屬于O/δ （line 16），那么實體所在類中的任意一點可以代替用戶位置，選擇t=min（o）成立的點返回（line 17）。如果實體不同意標識自己的位置，則返回面積最大類中的任意一點來代替實體位置，即q=min（o）（line 19）。在19步中，Ci =Area（[oi]）/ Area（[O]）表示q為合適請求點的可能性，由于對于模糊集來說，Area（[O]）是恒定的，只需要計算Area（[oi]）來決定Ci的大小，Area（[oi]）表示劃分[oi]中對應q點的點的數量。

4仿真實驗與結果分析

基于位置隱私保護的模糊查詢方法中需要用到FCM算法，該方法在不確定條件下為用戶提供盡可能可靠的服務，并利用最短路徑長度來作為衡量的標準。通過與傳統(tǒng)算法作對比，來驗證FCM的運算效率和實用性。

4.1FCM計算方法的實現

設圖G =（V， E）中有68個點，580條邊，設置模糊測試集如下：Q1={14，21，22，23，24，27，29，30，32，35}， Q2={50，52，54，56，57，58，59，63}，Q3={8，10，11，15，18，19，24，30，32，33，34，36，37，43，47，53，55，62，65，68}設置請求集合為：Q1={67，38，24，65，35，62，31，27，14，11，5，59}。其中， Q1和Q2為相對聚集的點，Q3為隨機產生的點，較為分散。在圖中加入虛擬點s，由于Q中存在12個點，那么整個圖形變?yōu)?9個點，592條邊。根據設定的邊權值矩陣來計算s到O1，O2，O3中各點的最短路徑。結果如表1，表2，表3所示。結果表明，即便在點數量較多和隨機情況下，14和27號請求點依然可以作為結果返回給用戶，表明在點數量更大，隨機比例更高的情況下FCM算法依然可以保持一定有效性。

綜合以上測試結果，表明算法可以在不確定條件下有效返回相關結果，由此達到預期目標。

4.2FCM算法與傳統(tǒng)算法的比較

建立5張圖G =（V， E），分別用Dijkstra算法、遺傳算法[8]和FCM方法計算最短路徑，統(tǒng)計各自的搜索速度，如圖3所示。

由圖3可以看出，當節(jié)點數為16時，Dijkstra算法、遺傳算法和FCM方法計算最短路徑所花費的時間幾乎相同，當節(jié)點個數為32時，三種方法的響應時間開始有略微差別，當節(jié)點數為48時，三種方法開始有明顯差別，并且隨著節(jié)點數的增多，三種方法的響應時間都有大幅提升，但是同等條件下，Dijkstra算法和遺傳算法的響應時間的上升幅度明顯大于FCM方法，而且這種差距將隨節(jié)點數的增多而變得更加明顯。由此可以得出如下結論：當節(jié)點數較少時，三種方法計算最短路徑的響應時間差別不大；當節(jié)點數目較多時，FCM方法的響應時間更少，具有更好的性能。

5結束語

本文基于位置隱私保護服務結構，實現了在不確定條件下為用戶提供相對可靠的位置隱私保護服務請求。在模糊集基礎上，利用最短路徑長度來作為衡量的標準，解決了在不確定條件下“誰附近有什么”的查詢問題，其中“誰”代表實體位置模糊集，然后，本文提出一種基于位置隱私保護的模糊查詢方法—FCM，使得在保護了用戶位置信息之后，仍舊可以提供較為可靠的服務，實現了位置隱私保護和服務質量的有效平衡。最后，經過實驗驗證，FCM方法在一定程度節(jié)省了存儲空間，提高了運行效率，具有一定實用價值。

參考文獻：

[1]ASHTON K. That ‘Internet of Things Thing[C]// RFID Journal， 2009.

[2]XIAO Z， MENG X， XU J. Quality-aware privacy protection for location-based services[C]//Proceedings of the International Conference on Database Systems for Advanced Applications.Bangkok.Thailand，2007：113-120.

[3]SAMARATI P， SWEENEY L. Protecting privacy when disclosing information：k- anonymity and its enforcement through generalization and suppression[J]. International Journal on Uncertainty， Fuzziness and Knowledge-based Systems，2002，10（5）：557-570.

[4]MACHANAVAJJHALA A，GEHRKE J， KIFER D. l-diversity： Privacy beyond K-Anonymity[C]//Proceedings of the 22nd International Conference on Data Engineering Atlanta. GA.USA：ACM Press， 2006： 3-8.

[5]ANCO H， LEON W. U-argus and t-argus：software for statistical disclosure control[C]//Proceedings of the Third International Seminar. Statistical Confidentiality，1996：156-163.

[6]SWEENEY L. Computational disclosure control： a primer on data privacy protection[D]. PhD dissertation，： Computer Science Dept. Massachusetts Institute of Technology， 2001.

[7]ZHANG Yonglong. Dijkstra shortest path algorithm optimization [J]. Journal of nanchang institute，2005，1（2）：23-25.

[8]張寧.遺傳算法的特點及其應用[J].北京：中國科技論文，2005，3（4）：107-111.

[2]PANDIT N， KALBARCZYK Z， IYER R K. Effectiveness of machine checks for error diagnostics[C]//Lisbon， Portugal： Proceedings of IEEE/IFIP International Conference on Dependable System & Networks， 2009， 7：578-583.

[3]ZHENG Z， LAN Z， PARK B H. System log pre-processing to improve failure prediction[C]//Lisbon， Portugal： Proceedings of IEEE/IFIP International Conference on Dependable System & Networks， 2009， 7：572-577.

[4]HILLER M， JHUMKA A， SURI N. An approach for analysing the propagation of data errors in software[C]//Goteborg， Sweden： International Conference on Dependable System & Networks， 2001， 7：161-170.

[5]李秀敏. 極值統(tǒng)計模型族的參數估計及其應用研究[D]. 天津：天津大學，2007： 13-29.