獨立架構下自適應情境的位置隱私保護方法

毛 典 輝 ， 蔡 強 ， 李 海 生 ， 曹 健

（1.北京工商大學 計 算機與信息工程學院，北京 100048；2.北京工商大學 國 有資產管理協同創新中心，北京 100048）

當前基于位置的服務（Location－based Service，LBS）應用中，大部分采用可信第三方匿名服務器（Trusted Third Party，TTP）與k匿名模型的架構模式來保護用戶的位置隱私，但是并沒有一個權威機構來評估TTP的可信度，而且TTP容易成為系統性能瓶頸和集中攻擊點[1].另外，以用戶合作為基礎的k匿名模型，因用戶時空情境變化影響了協作的穩定性，使得隱私保護方法的匿名穩定性無法得到保證，因此，無TTP、非用戶合作的獨立架構模式成為當前LBS中位置隱私保護方法的研究熱點[2].

移動用戶在獨立架構模式下保護位置隱私，最直接方法是發送假位置至LBS服務器進行查詢，由服務器通過增量近鄰查詢返回查詢結果，如SpaceTwist方法[3].但是，隨機或者主觀設定查詢點容易導致位置隱私保護效果與通信開銷失衡[4].因此，查詢點的選取應視用戶的時空情境而定[5].該思想在實際應用中存在3個難點終端的位置情境信息如何表征？終端如何實時獲取位置情境信息？如何根據用戶的位置情境選擇合適的查詢點？本文針對上述問題，通過在服務器端建立多粒度抽象路網以及位置情境模型，并以此為基礎，提出一種自適應情境的位置隱私保護方法.該方法不僅能實現終端與LBS服務器的直接通信以及準確的位置查詢服務，而且通過自適應情境感知技術可實現位置隱私保護度與通信開銷的平衡.

1 位置隱私保護方法介紹

1.1 時空位置情境建模

移動用戶在LBS服務中，當其處于路網密集區域時，該區域內交叉路口多、人流量大（通常情況下，路網密集程度與人口密度成正比），較小的位置偏移量（假位置與真實位置間距離）即可獲得較高的位置隱私保護；反之，在路網稀疏區域內時，交叉路口少、人口密度低，較大的位置偏移量才能保證一定的隱私保護效果[6].因此，用戶所處位置的路網密集程度直接決定了位置隱私保護效果.另外，用戶的通信開銷主要包括服務器返回的查詢興趣點（POIs）以及路網拓撲結構，當用戶所處區域的POIs分布較為密集時，較小區域的子路網拓撲結構即可滿足查詢要求.因此，POIs的空間分布狀況決定了用戶的通信開銷.

基于上述思想，引入路網密度、POIs密度等指標表征用戶的位置情境.

定義1 路網G：定義無向圖G＝（V，E），來表示交通公路網絡，其中V為網絡節點集合，E為網絡邊集合，dG（n）表示圖G中節點n的度.

定義2 抽象路網G′：給定圖G的某一分割方案P＝｛G1，G2，…，Gp｝，定義圖G的抽象網絡G′＝｛V′，E′，W′｝，則 G ′ 中 的 每 個 節 點 均 代 表G 中 對 應 的 分 割 子 圖，且 邊 集 合 （ i，j）∈E′ 滿 足 ｛ （i′，j′）∈E｜Sub（i′）＝i∧Sub（j′）＝j｝.

定義3 路網密度λ：設C為路網G的一個子區域，s為C的面積，l為C內道路總長度，則定義λ＝l s為區域C的路網密度.

定義4 POIs密度ε：設C為路網G的一個子區域，m為區域C中POIs的總數，s為C的面積，則定義ε＝m s為區域C的POIs密度.

基于上述定義，移動用戶在某一時刻t的時空位置情境可表示為三元組〈p，λ，ε〉｜t，其中，p為用戶在t時刻的空間位置，λ為用戶所處區域的路網密度，ε為用戶所處區域的POIs密度.

1.2 自適應情境的位置隱私保護方法

終端的位置隱私保護效果由查詢點偏移距離與用戶期望的查詢結果在POIs集合中返回次序決定，當該次序越靠后時，攻擊者推測的難度越大，用戶的位置隱私保護效果就越好.用戶的位置隱私保護效果與所處位置情境信息之間關系滿足定理1.

定理1 對于任意用戶，當路網密度λ足夠小時，用戶期望查詢結果在候選結果集中的返回次序E（k）中.查詢點偏移距離σ、POIs密度ε滿足：E（k）≤λεσ[6].

根據上述定理，文中自適應情境的位置隱私保護方法為：首先在服務器端構建多粒度抽象路網以及對應的時空位置情境模型，終端僅發送不包含真實位置的查詢主題（如銀行、醫院等）至服務器，服務器返回粗粒度抽象路網以及對應的查詢主題POIs空間分布信息，若抽象路網精度不能滿足用戶要求，則重復該過程，直至返回的路網粒度滿足用戶要求為止；移動用戶根據個人風險偏好以及通信開銷承受力，預設通信成本（期望返回的候選結果集總數）與位置隱私保護強度（期望查詢結果在候選結果集中的返回次序），并以上述位置情境信息為基礎，估算查詢區域范圍與查詢點位置；終端發送查詢點與查詢區域至服務器，服務器在限定條件下進行增量近鄰查詢，依次返回查詢區域對應的高精度地圖以及候選結果集，終端根據真實位置進行增量計算，直至完成位置服務.

2 位置隱私保護方法實現

2.1 多粒度抽象路網重構

移動終端因通信開銷與性能局限無法實時下載完整高精度路網拓撲結構，而位置情境感知則以全局路網信息為基礎，為了解決此矛盾，在服務器端引入路網粗糙化技術構建多粒度的抽象路網.由于實際路網中拓撲結構呈現非均勻性，為了保證抽象路網重構后信息的一致性，即抽象路網節點具有相同的路網密度，且重構前后節點的空間鄰近近性保持不變，引入非均勻Hilbert映射技術以及Voronoi圖技術實現抽象路網重構.這樣，不僅粗糙化了原始路網的拓撲信息，減少了終端的實時下載開銷，而且保證了終端位置情境信息的實時獲取.

抽象路網重構算法實現過程為：對高精度的實際路網設置某一路網密度λ值，依據空間層次分解方法，將路網空間分為4個子空間C0、C1、C2、C3，如果Ci（i∈ [0，3]）內路網密度λi＞λ，則對Ci繼續迭代劃分，直到λi≤λ為止（如圖1（a）所示）.對于劃分后的子空間集合，選擇區域Ci的中心Pi作為該區域的投影點，這樣二維的空間區域投影為離散的空間點集P＝｛p1，p2，…，pn｝[7]，引入Voronoi圖技術進行空間近鄰判斷（如圖1（b）所示），保證重構前后的節點間空間鄰近性不變.判斷Voronoi圖中近鄰點間的連通性，形成節點鄰接矩陣，即

節點矩陣W中，元素wij取值均為0或1.其中，0表示相鄰區域無路網交點，1表示相鄰區域存在路網交點，形成最終的抽象路網（如圖1（c）所示）.

圖1 抽象路網重構示意圖

2.2 位置情境信息感知

上述抽象路網重構保證了情境信息表達的一致性，同時解決了終端情境感知的實時通信，為了進一步控制終端查詢過程中的通信開銷，用戶需取得POIs密度分布信息.該信息的處理過程為：終端發送不包含位置信息的查詢主題至服務器，服務器端以抽象路網節點對應的子區域為單位，統計每個區域內POIs數量形成空間分布直方圖[8]返回至用戶.POIs空間分布直方圖數據量一般極小（KB級），對終端的通信開銷的影響有限，但服務器端的計算較為費時，為了降低服務器端的計算開銷，可將常用的查詢主題（如銀行、餐廳等）進行預處理，形成數據包以供用戶下載，避免服務器端重復實時計算.

2.3 自適應情境的位置查詢服務

3 位置隱私保護方法分析

3.1 位置隱私保護度分析

在終端與LBS服務器直接通信模式下，攻擊者可能獲取的信息途徑為：

（1）從用戶終端處直接獲取查詢信息，由于用戶作為位置隱私的持有者對位置信息具有絕對的控制權，在非合作模式下，攻擊者無法直接與用戶聯系，因此也無法獲取位置信息.

（2）從服務器端截取用戶查詢內容以及服務器返回結果等信息，在該情形下，攻擊者推測用戶準確位置的可能性為：假定q為終端實際位置，q′為查詢點位置，pj為終端取得的第j個查詢結果，λ為用戶所在區域的路網密度，ε為對應的POIs密度.攻擊者獲取的信息包括：路網區域C、查詢點q′、以q′為中心的有序結果集｛p1，p2，p3，…，pm｝，并且已知用戶采取增量近鄰查詢.

假定攻擊者認為pk為用戶的期望查詢結果，根據增量查詢結束條件[9]可知，攻擊者推測的用戶位置q滿足如下不等式方程：其中，dist（·，·）代表攻擊者推測用戶位置與用戶查詢點之間的距離，不等式方程的解代表攻擊者推測用戶可能存在的位置區域.

上述不等式方程解代表用戶可能存在的一個位置區域，由于用戶真實查詢結果保存于終端，攻擊者無法得到.因此，上述不等式方程存在多個解，即多種可能區域，故攻擊者無法確定用戶的具體位置.

3.2 隱私保護度與通信開銷分析

終端的位置隱私保護效果是由用戶期望查詢結果在返回的POIs集合中出現的順序E（k）決定的，E（k）越靠后，攻擊者推測難度越大，用戶的位置隱私保護效果越好.同時，終端的查詢通信開銷滿足M＝min｛j∈N｜Dj?Sj｝，其中，Dj＝Θ（q，），為需求空間，為前j個查詢結果與q間距離的最小值；Sj＝Θ（q′，Rj），為供應空間，Rj為pj與q′ 間的距離.

由于q、q′、POIs均是獨立的，且σ＝ q′－q 變化值服從正態分布，則通信開銷M滿足概率分布[8]：

其中，M 的均值E（M）＝α2＋2αs1/2＋2，方差V（M）＝ （5－π）α2＋π1/2α，α＝ （πρ）1/2l.

由上述隱私保護度與通信開銷的分析可知：用戶根據個人風險偏好設置的E（k）值較大時，其通信開銷會呈指數增大.因此，用戶在可承受的隱私保護強度范圍內盡可能設置較少的E（k）與POIs返回數量.

4 實驗及結果分析

為了評價位置隱私保護方法的性能，實驗平臺選用業界認可的Thomas Brinkhoff路網數據生成器仿真平臺[9]，算法采用Java實現，實驗機器配置為Intel雙核1.73GHz CPU、2GB內存，路網數據為Oldenburg城市道路結構（區域面積為23.57km×26.92km），500個POIs由路網數據生成器隨機生成.

4.1 隱私保護算法性能分析

為了分析路網密度λ對用戶的通信開銷影響，實驗中設置返回POIs數量R＝10，針對同一R值，分別取不同的λ值，比較不同λ取值下系統據此估算出最小路網區域，每組參數算法運算100次，統計每組參數對應的路網區域Ce的平均大小，比較結果如圖2（a）所示.

為了分析路網密度λ對用戶位置隱私保護強度的影響，在上述實驗參數條件下，同時設置用戶期望查詢

圖2 位置隱私保護方法性能示意圖

結果的返回次序k，k分別取值為1、2、3、4、5，每組參數設置下算法計算100次，統計每組參數對應的查詢點平均偏移距離σ，統計結果如圖2（b）所示.

從圖2（a）的分析可知：在用戶通信開銷預算下，終端實際通信開銷與路網密度λ正相關，但λ取值大于6后，用戶實際通信開銷趨于穩定.這是因為當λ值較小時，增大λ值可使得單個投影點對應的路網區域面積增大，故包含相同POIs數的路網范圍也相對增大，當該范圍面積增大到一定程度后，滿足最小通信成本路網空間區域趨于不變.因此，該方法保證了服務器能以最小通信開銷返回用戶所需情境信息.

從圖2（b）的分析可知：用戶的位置隱私保護效果與用戶風險意識、路網密度正相關，當路網密度值較大時，終端存儲粗粒度的位置情境信息，而據此設置較高隱私保護強度將導致查詢點偏移量相對較大，從而使得通信開銷增大.因此，用戶可下載粒度相對較細的情境信息，實現通信開銷與位置隱私保護的平衡.

4.2 隱私保護方法性能比較

為了比較自適應情境位置隱私保護方法性能，進行了兩組相關實驗.

試驗1 不同系統架構下位置保護方法對比.

實驗中分別選取基于TTP的PrivacyGrid方法[10]和無TTP基于用戶協作的CoPrivacy方法[11]與文中方法進行對比.實驗參數為：PrivacyGrid方法與CoPrivacy方法的移動用戶數量為4 000，匿名參數m為5～25，用戶近鄰查詢需要的近鄰個數為10.文中方法中λ取值為6，用戶設置返回的POIs數量為10，期望查詢結果返回次序為3.以上方法均查詢100次，統計服務器端查詢結果平均值Savg和平均響應時間Tavg.算法比較結果如圖3所示.

圖3 不同系統架構下位置隱私保護方法比較圖

從圖3的分析可知：PrivacyGrid方法因匿名個數增長，其查詢區域、查詢結果、響應時間均顯著增長；CoPrivacy方法雖然因P2P多跳通信使得網絡通信代價增大，但是增量近鄰查詢減少了查詢結果，因此也降低了響應時間；自適應情境的位置隱私保護方法采取了增量近鄰查詢的優點，同時在系統架構上使得終端直接與服務器直接通信，減少了中間通信環節，因此該方法在通信開銷與響應時間均優于前兩種方法.

試驗2 相同系統架構下位置保護方法對比.

實驗中分別選取自適應情境位置隱私保護方法與隨機選取查詢點的SpaceTwist隱私保護方法進行對比分析.實驗參數為：前者的參數設置與不同系統架構下位置隱私保護方法對比實驗中的參數保持一致；后者的設置查詢點偏移距離l為1、5、10.以上實驗均查詢100次，統計平均通信開銷Savg值和平均響應時間Tavg.算法比較結果如圖4所示.

圖4 相同系統架構下位置隱私保護方法比較圖

從圖4的分析可知：隨機選取查詢點的SpaceTwist方法通信開銷與查詢點偏移距離正相關，當查詢點偏移真實位置較遠時，移動終端獲得較高的位置隱私保護強度，但是增大了與服務器的通信開銷，而且查詢點的隨機選取導致通信開銷不可控；而文中提出的位置隱私保護方法通信開銷與用戶設置的期望值基本一致，因此用戶的通信開銷可控，而且還保證了一定的隱私保護強度，故該方法對用戶具有較高的可控性與自主性.從移動終端的平均響應時間來看，當SpaceTwist方法查詢點偏移距離較近時，該方法較文中方法計算開銷要小，這是由于后者在情境感知與查詢點估算時需要一定的時間與計算開銷，但是前者的計算開銷優勢是以犧牲用戶位置隱私保護效果為代價的.由此可得，文中提出的方法較SpaceTwist方法實現了隱私保護度與通信開銷、計算開銷的平衡.

5 結束語

在不改變現有LBS系統架構的條件下，提出了一種自適應情境的位置隱私保護方法來實現終端與服務器的直接通信.該方法不僅通過服務器端構建了多粒度抽象路網與位置情境模型，解決了終端位置情境信息感知時交互通信的難點，而且終端根據用戶的個性化設置，實現了位置隱私保護度與通信開銷、計算開銷的平衡.但是文中提出的位置隱私保護方法的性能主要由路網密度決定的，而該值的選取一般依據經驗.因此，如何提高終端性能與路網密度選取的自適應性將是下一步研究的重點.

[1] Berker A Thanasis G.P，Rammohan N，et al.User－side Adaptive Protection of Location Privacy in Participatory Sensing[J].Geoinformatica，2014，18（1）：165－191.

[2] 周傲英，楊彬，金澈清，等.基于位置的服務：架構與進展[J].計算機學報，2011，34（7）：1155－1171.Zhou Aoying，Yang Bin，Jin Cheqing，et al.Location－based Services：Architecture and Progress[J].Chinese Journal of Computers，2011，34（7）：1155－1171.

[3] Yiu M L，Jensen C S，Jesper M，et al.Design and Analysis of a Ranking Approach to Private Location－Based Services[J].ACM Transactions on Database Systems，2011，36（2）：1－46.

[4] Wang Yu，Xu Dingbang He Xiao.L2P2：Locationaware Location Privacy Protection for Location－based Services[C]//Proceeding of the 31st Annual IEEE International Conference on Computer Communications.Piscataway：IEEE，2012：1996－2004.

[5] Skvortsov P，Dürr F，Rothermel K.Map－Aware Position Sharing for Location Privacy in Non－trusted Systems[C]//Proceedings of the 10th International Conference Pervasive Computing Newcastle.Berlin：Springer－Verlag，2012：388－405.

[6] Pingley A，Yu Wei，Zhang Nan，et al.A Context－aware Scheme for Privacy－preserving Location－based Services[J].Computer Networks，2012，56（11）：2551－2568.

[7] 毛典輝，蔡強，李海生，等.用戶協作模式下自適應情境的LBS隱私保護方法[J].四川大學學報（工程科學版），2013，45（4）：75－80.Mao Dianhui，Cai Qiang，Li Haisheng，et al.An Adaptive Context－aware LBS Privacy Protection Method Based on Users Collaboration[J].Journal of Sichuan University（Engineering Science Edition），2013，45（4）：75－80.

[8] Brinkhoff T.A Framework for Generating Network Based Moving Objects[J].GeoInformatica，2000，6（2）：153180.

[9] M?ller J，Yiu M L.Probabilistic Results for a Mobile Service Scenario[J].Advances in Applied Probability，2011，43（2）：322－334.

[10] Bamba B，Liu L，Pesti P，Wang T.Supporting Anonymous Location Queries in Mobile Environments with Privacygrid[C]//Proceedings of the International World Wide Web Conference.New York：ACM，2008：237－246.

[11] 黃毅，霍崢，孟小峰.CoPrivacy：一種用戶協作無匿名區域的位置隱私保護方法[J].計算機學報，2011，34（10）：1975－1985.Huang Yi，Huo Zheng，Meng Xiaofeng.CoPrivacy：A Collaborative Location Privacy Preserving Method without Cloaking Region[J].Chinese Journal of Computers，2011，34（10）：1975－1985.