王鑫 余翔湛

摘要：隨著基于位置的服務(wù)（location-based services，簡(jiǎn)稱LBS）的廣泛應(yīng)用，個(gè)人位置信息的保護(hù)越來(lái)越受到人們關(guān)注。在LBS服務(wù)中，常常會(huì)遇到“誰(shuí)附近有什么資源”的問(wèn)題，“誰(shuí)”代表實(shí)體位置，“什么”代表服務(wù)請(qǐng)求。在“誰(shuí)附近有什么”的信息查詢服務(wù)過(guò)程中，如何在保護(hù)“誰(shuí)”的基礎(chǔ)上提供相對(duì)可靠的服務(wù)，將是本文的研究重點(diǎn)。針對(duì)這一問(wèn)題，用模糊集來(lái)實(shí)現(xiàn)對(duì)“誰(shuí)”的保護(hù)，并針對(duì)模糊集，提出一種基于位置隱私保護(hù)的模糊查詢方法，在模糊位置信息的基礎(chǔ)上提供相對(duì)可靠的服務(wù)，并在一定程度上實(shí)現(xiàn)了位置隱私保護(hù)和位置服務(wù)質(zhì)量之間的平衡。最后，通過(guò)相關(guān)實(shí)驗(yàn)來(lái)評(píng)估該方法的性能。

關(guān)鍵詞：模糊集； 位置隱私保護(hù)； 模糊查詢； 服務(wù)質(zhì)量

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2013）06-0021-04

0引言

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

在LBS服務(wù)中，主要有三大目標(biāo)：你在哪里（空間信息）、你和誰(shuí)在一起（社會(huì)信息）、誰(shuí)附近有什么資源（信息查詢）。本文主要解決“誰(shuí)附近有什么資源”的問(wèn)題，首先要明確兩個(gè)參數(shù)：“誰(shuí)”和“什么”，“誰(shuí)”代表實(shí)體位置，“什么”代表服務(wù)請(qǐng)求。

在“誰(shuí)附近有什么”的信息查詢服務(wù)過(guò)程中，如何在保護(hù)“誰(shuí)”的基礎(chǔ)上提供相對(duì)可靠的服務(wù)，將是本文的研究重點(diǎn)。針對(duì)這一問(wèn)題，本文提出一種基于位置隱私保護(hù)的模糊查詢方法，在模糊位置信息的基礎(chǔ)上提供相對(duì)可靠的服務(wù)，并于一定程度上實(shí)現(xiàn)了位置隱私保護(hù)和位置服務(wù)質(zhì)量之間的平衡。

1位置隱私保護(hù)服務(wù)結(jié)構(gòu)

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

該結(jié)構(gòu)中模糊服務(wù)器工作如下：

（1）收集用戶發(fā)送來(lái)的位置服務(wù)請(qǐng)求信息，將這些信息存儲(chǔ)在服務(wù)器中；

（2）對(duì)用戶發(fā)送過(guò)來(lái)的位置服務(wù)請(qǐng)求信息中的真實(shí)位置信息進(jìn)行模糊，用空間模糊集進(jìn)行代替，從而保護(hù)實(shí)體位置信息，最后將模糊過(guò)后的位置服務(wù)請(qǐng)求發(fā)送給第三方的LBS提供商的位置服務(wù)器；

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

根據(jù)位置隱私保護(hù)服務(wù)結(jié)構(gòu)的要求，首先需要對(duì)用戶真實(shí)位置信息進(jìn)行模糊。本文采用已有的k-匿名技術(shù)[3]來(lái)構(gòu)造實(shí)體模糊集，以達(dá)到模糊效果。

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

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

利用K-匿名算法構(gòu)造完實(shí)體位置模糊集之后，LBS服務(wù)器需要針對(duì)整個(gè)模糊集來(lái)提供“附近有什么”的查詢服務(wù)，而如何在模糊集基礎(chǔ)上提供盡可能良好的服務(wù)即成為問(wèn)題關(guān)鍵。針對(duì)這一問(wèn)題，本文提出一種基于位置隱私保護(hù)的模糊查詢方法—FCM方法，該方法可以嵌入到LBS服務(wù)器當(dāng)中，通過(guò)計(jì)算模糊集到附近服務(wù)請(qǐng)求點(diǎn)的最短路徑長(zhǎng)度來(lái)提供相對(duì)可靠的查詢服務(wù)，使得在保護(hù)實(shí)體真實(shí)位置的同時(shí)，又提供了較為良好的服務(wù)。

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

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

3.1模糊集劃分

對(duì)模糊集O進(jìn)行劃分，需要構(gòu)建對(duì)于請(qǐng)求點(diǎn)集合Q在關(guān)系δ上的劃分△。

關(guān)系δ定義如下：δ∈O*O，對(duì)任意o1，o2∈O，o1δ o2當(dāng)且僅當(dāng)min（o1）=min（o2）。o1δ o2可以理解為對(duì)于某個(gè)請(qǐng)求來(lái)說(shuō)，o1和o2的最短路徑距離是相等的。其中函數(shù)min描述如下：min：O→Q，min（o） →q1表示對(duì)任意o∈O，滿足d（o， q1）< d（o， q1），假設(shè)q1，q2∈Q，而且d（o， q1）≠d（o， q1）。其中d表示最短路徑長(zhǎng)度。

根據(jù)關(guān)系δ，可以得到劃分△：

（1）計(jì)算實(shí)體位置模糊集O中各點(diǎn)到請(qǐng)求集合Q的最短路徑距離，得到序?qū)?，即oi的最短路徑距離的終點(diǎn)是qj；

（2）遍歷所有的序?qū)?，將終點(diǎn)相同的起點(diǎn)歸為一類；

（3）得到劃分結(jié)果△，其中o∈[o]，對(duì)任意o∈O 。

3.2FCM計(jì)算方法

在劃分的基礎(chǔ)上，F(xiàn)CM可以在眾多附近服務(wù)點(diǎn)中選擇最適合的點(diǎn)返回給用戶，由此使得服務(wù)的可靠性有所提升。

為了便于研究，如圖2所示，設(shè)置一個(gè)虛擬點(diǎn)s，將s和請(qǐng)求集合Q中的點(diǎn)以權(quán)重為0.0的邊連接起來(lái)。

在實(shí)際計(jì)算中，可以先計(jì)算點(diǎn)s到模糊集O中各點(diǎn)的最短路徑距離，然后將最短路徑逆序，轉(zhuǎn)化為從集合O中各點(diǎn)到虛擬點(diǎn)s的最短路徑距離，則逆序后的最短路徑中倒數(shù)第二個(gè)點(diǎn)必然是集合Q中的點(diǎn)。

FCM計(jì)算方法描述如下：

算法輸入：用來(lái)表示二維空間的邊權(quán)值圖G = （V， E）；模糊點(diǎn)集合OV，且實(shí)體位置 l∈O；請(qǐng)求點(diǎn)集合 QV

算法輸出：

（1）關(guān)系δO×O，o1，o2∈O，o1 δ o2當(dāng)且僅當(dāng)min（o1） = min（o2）；

（2）序?qū)?q，c>，C∈（0.0，1.0]表明q為實(shí)體請(qǐng)求點(diǎn)的可能程度。

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

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

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

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

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

6.對(duì)每一個(gè)孩子結(jié)點(diǎn)x，計(jì)算根結(jié)點(diǎn)到其的路徑長(zhǎng)度。

7.若某孩子結(jié)點(diǎn)的路徑長(zhǎng)度權(quán)值超出bound，則將該孩子結(jié)點(diǎn)丟棄，剪掉分支；否則，將該孩子結(jié)點(diǎn)加入表PT中。

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

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

10.重復(fù)上述過(guò)程，可得s到O中其它各點(diǎn)的最短路徑距離。

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

12.o1，o2∈O，o1 δ o2當(dāng)且僅當(dāng)second（o1） = second（o2），此時(shí)劃分O/δ構(gòu)建完畢。

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

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

15. else

16.（if 用戶同意標(biāo)識(shí)位置l所在的分類[l]∈O/δ then

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

18. else

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

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

4仿真實(shí)驗(yàn)與結(jié)果分析

基于位置隱私保護(hù)的模糊查詢方法中需要用到FCM算法，該方法在不確定條件下為用戶提供盡可能可靠的服務(wù)，并利用最短路徑長(zhǎng)度來(lái)作為衡量的標(biāo)準(zhǔn)。通過(guò)與傳統(tǒng)算法作對(duì)比，來(lái)驗(yàn)證FCM的運(yùn)算效率和實(shí)用性。

4.1FCM計(jì)算方法的實(shí)現(xiàn)

設(shè)圖G =（V， E）中有68個(gè)點(diǎn)，580條邊，設(shè)置模糊測(cè)試集如下：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}設(shè)置請(qǐng)求集合為：Q1={67，38，24，65，35，62，31，27，14，11，5，59}。其中， Q1和Q2為相對(duì)聚集的點(diǎn)，Q3為隨機(jī)產(chǎn)生的點(diǎn)，較為分散。在圖中加入虛擬點(diǎn)s，由于Q中存在12個(gè)點(diǎn)，那么整個(gè)圖形變?yōu)?9個(gè)點(diǎn)，592條邊。根據(jù)設(shè)定的邊權(quán)值矩陣來(lái)計(jì)算s到O1，O2，O3中各點(diǎn)的最短路徑。結(jié)果如表1，表2，表3所示。結(jié)果表明，即便在點(diǎn)數(shù)量較多和隨機(jī)情況下，14和27號(hào)請(qǐng)求點(diǎn)依然可以作為結(jié)果返回給用戶，表明在點(diǎn)數(shù)量更大，隨機(jī)比例更高的情況下FCM算法依然可以保持一定有效性。

綜合以上測(cè)試結(jié)果，表明算法可以在不確定條件下有效返回相關(guān)結(jié)果，由此達(dá)到預(yù)期目標(biāo)。

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

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

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

5結(jié)束語(yǔ)

本文基于位置隱私保護(hù)服務(wù)結(jié)構(gòu)，實(shí)現(xiàn)了在不確定條件下為用戶提供相對(duì)可靠的位置隱私保護(hù)服務(wù)請(qǐng)求。在模糊集基礎(chǔ)上，利用最短路徑長(zhǎng)度來(lái)作為衡量的標(biāo)準(zhǔn)，解決了在不確定條件下“誰(shuí)附近有什么”的查詢問(wèn)題，其中“誰(shuí)”代表實(shí)體位置模糊集，然后，本文提出一種基于位置隱私保護(hù)的模糊查詢方法—FCM，使得在保護(hù)了用戶位置信息之后，仍舊可以提供較為可靠的服務(wù)，實(shí)現(xiàn)了位置隱私保護(hù)和服務(wù)質(zhì)量的有效平衡。最后，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，F(xiàn)CM方法在一定程度節(jié)省了存儲(chǔ)空間，提高了運(yùn)行效率，具有一定實(shí)用價(jià)值。

參考文獻(xiàn)：

[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]張寧.遺傳算法的特點(diǎn)及其應(yīng)用[J].北京：中國(guó)科技論文，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)計(jì)模型族的參數(shù)估計(jì)及其應(yīng)用研究[D]. 天津：天津大學(xué)，2007： 13-29.