利用概率的位置匿名算法

閆玉雙,譚示崇,趙大為

(西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071)

利用概率的位置匿名算法

閆玉雙,譚示崇,趙大為

(西安電子科技大學綜合業務網理論及關鍵技術國家重點實驗室,陜西西安 710071)

k匿名模型是一種有效的位置隱私保護技術,通過構造包含需要保護的用戶在內的k個正在發送請求的用戶的匿名區域,達到保護用戶位置的目的.但是現有的k匿名模型僅能利用當前正在發送請求的用戶,當同時發送請求用戶較少時,就會導致匿名區域過大.為此,提出一種利用概率的位置匿名算法來保護路網中的移動用戶的位置,利用當前時刻的不活躍用戶的歷史位置軌跡,計算出進入匿名路段的概率,可明顯減小匿名路段長度.實驗結果證明,基于概率的位置匿名算法與一般的k匿名模型相比較,提高了匿名效率.

k匿名;不活躍用戶;概率;基于概率的位置匿名算法

利用位置的服務（Location-Based Service,LBS)給人們提供各種服務的同時也不可避免地產生了位置隱私泄露的問題.近年來,人們提出了很多利用位置服務的方法來保護移動用戶的位置隱私方法.它大體可分為兩類:一類是利用策略的[1]位置隱私方法,另一類是利用匿名的[2].其中利用匿名的位置隱私方法應用更為廣泛.

k匿名模型是一種有效的位置隱私保護技術[3],它要求發布的數據中至少有k-1個個體與需要隱私保護的個體具有完全相同的準標識屬性,從攻擊者看來這些個體完全相同而無法區分,從而達到保護個體隱私信息的目的.文獻[4]提出了位置匿名的概念,通過匿名的方法保護用戶的隱私信息.直觀上,很容易想到用假名來代替用戶的真實身份[5].隨著技術的不斷發展,人們逐漸轉移到對用戶的軌跡信息的研究上來,發現移動用戶的位置在時間上具有相關性[6-8].于是,如何有效地保護用戶的軌跡信息成為人們關注的焦點.雖然如何把握位置與時間的相關性具有一定的難度,但是利用軌跡的啟發式隱私度量方法仍然得到了人們的青睞,例如位置數據隨機化[9-10]和對空間[11]或時間[12]數據的模糊化等方法.

在位置隱私的k匿名中,匿名區域的大小是衡量服務質量和通信開銷的一個重要指標.現在的技術大多是借助于用戶的位置更新來達到匿名隱私的目的,而不關心這些用戶是否正在發送位置請求.這些沒有發送請求的用戶沒有義務向服務器提交并更新他們的位置信息,所以這些用戶不能得到很好的利用.文中將用戶劃分為活躍用戶和不活躍用戶.當前時刻向服務器發出請求的用戶就是活躍用戶,而不活躍用戶是指當前時刻沒有向服務器發送請求,但是之前發送過請求并且服務器有其請求記錄的用戶.匿名服務器僅僅知道活躍用戶的當前位置信息,而不能獲知不活躍用戶的當前位置信息,這樣就起到了保護不活躍用戶隱私的目的.在k匿名中,若匿名值k比較大或者活躍用戶的位置比較分散,那么匿名區也會比較大,從而增加了經濟開銷,同時降低了服務質量.之前的研究主要利用的是活躍用戶,不活躍用戶沒有得到充分利用.若是可以利用不活躍用戶,那么匿名區肯定會明顯減小.在路網中,用戶只能沿著道路移動,所以匿名區域就是路段的長度.例如圖1所示,匿名值k=4,當僅僅利用活躍用戶時,匿名的路段長度是dAB,而利用不活躍用戶后,匿名路段長度變為dCD,顯然比dAB小得多.可見,利用不活躍用戶可以顯著減小匿名路段長度.

圖1 利用不活躍用戶進行匿名的示意圖

系統模型如圖2所示.當匿名服務器接收到移動用戶的位置請求時,匿名服務器生成一個用戶匿名來代替用戶的真實身份,也就是路段長度.接著匿名服務器生成匿名化的位置請求集合R,ri=（ui,RLi,ci,t,k),表示單個用戶的請求,其中ui代表用戶的匿名身份,RLi代表用戶在時刻t的匿名路段,ci代表當前時刻用戶的請求內容,t代表用戶請求的時刻,k代表匿名值.所有用戶的請求都被存儲在匿名服務器的數據庫F中.然后匿名服務器將請求r′i=（ui,RLi,ci,t)發送給LBS位置服務器,LBS位置服務器接收到信息后就會查詢,并且返回所有的結果候選集給匿名服務器.最終匿名服務器會根據用戶的精確位置信息挑選最合適的結果,并發送給用戶.其中匿名服務器是可信的,而位置服務器是半可信的.

圖2 系統模型

1 算法模型

文中提出了一種利用概率的位置匿名（Probability-based Location Anonymity,PLA)算法,充分利用不活躍用戶使匿名路段的長度減小,從而達到節省通信開銷和提高通信質量的目的.通過研究在路網中的移動用戶的行駛路徑,發現移動用戶的位置具有馬爾科夫的特性,也就是說移動用戶當前時刻的位置僅與前一時刻的位置有關.不活躍用戶的分布特性可以根據匿名服務器所記錄的這些用戶的歷史位置信息得到.根據歷史數據和馬爾科夫特性進一步計算概率,推知不活躍用戶在某一路段的可能性大小,適當地選擇匿名路段.

1.1 PLA算法流程

PLA算法的流程如下:

步驟1 可信服務器將整個路網進行劃分直到最小的路段小于某一值,生成S,同時設置閾值vth0.

步驟2 在每個路網的交叉點處,匿名服務器通過F計算出相關的矩陣H（v,t)和C（v,t-1).

步驟3 匿名服務器不斷更新F并根據用戶請求找到一個初始目標路段ei,則,表示用戶位于若ei滿足隱私要求,則將ei二等分,此時用戶位于,判斷用戶所在的小路段是否滿足隱私要求;滿足就繼續分割,不滿足就以大路段Lgi作為匿名路段.最終匿名路段用表示,對用戶進行定位.

步驟4 在k匿名下,將初始匿名路段ei中活躍用戶的數目與k值進行比較,匿名服務器決定是否進行定位的擴展運算.當活躍用戶的數目不能滿足隱私要求時,接著進行步驟5;否則,直接跳到步驟6.

步驟5 概率位置擴展匿名（Probability-based Location Extension Anonymity,PLEA)算法:當匿名服務器根據請求找到的初始目標路段ei卻不能滿足隱私要求時,路段需要進行擴展.這里在原路段的終端隨機選取一條路段進行擴展.

隨機選取的路段作為ei+1,使得路段ei+ei+1滿足隱私要求,則,表示用戶位于大路段然后將ei+1劃分,選取前半段,也就是路段ei+ei+1-0并且,表示用戶位于小路段,判斷是否滿足隱私要求.若滿足就繼續分割,不滿足就以大路段作為匿名路段.選取最短路段作為最終的匿名路段,并且用RLi表示.

步驟6 服務器用RLi代替用戶的位置將請求發送給LBS位置服務器.當匿名服務器收到請求結果時,會從中選擇最優的結果,即最接近用戶的位置發送給用戶.

1.2 PLA算法具體過程

1.2.1 初始化過程

（1)路段的劃分和表示方法.用S={E,V},表示整個路網的集合,其中E和V分別是邊和頂點的集合,邊表示路段,頂點表示路的交叉點,其中E={e1,e2,e3,…},v={v1,v2,v3,…}.采用二叉樹的方法將路段進行劃分.首先將目標路段進行二等分,前半段用0表示,后半段用1表示;然后再將前半段和后半段分別二等分,分別用00、01、10、11表示.以此類推,將路段繼續劃分直到長度小于某一閾值.用2表示整條路段.假設路段未劃分時設為Grade 0,第1次劃分過程為Grade 1,則第g次劃分為Grade g,用Lgi表示用戶處于Grade g時的一個單元路段.

用起點和終點坐標以及相應的二進制數來表示一條具體路段.將路段ei進行劃分,若起點和終點坐標分別是（x1,y1)和（x2,y2),那么段路ei可以由它兩端的交叉點和二進制數表示,例如（（x1,y1),（x2,y2))-2、（（x1,y1),（x2,y2))-0和（（x1,y1),（x2,y2))-11.

（2)設置vth0.設在t時刻路段ei上除目標用戶uk之外還有kt個活躍用戶,則在k匿名下,此路段還需要包括k-1個活躍或不活躍用戶.為了滿足k匿名要求,則

其中,d為活躍用戶的個數,mia會在式（3)中介紹.安全系數（PS)表示用RLj進行用戶請求定位的安全程度.

當vth0＜PS時,說明用RLj進行用戶請求匿名不會暴露用戶的位置隱私.

1.2.2 計算不活躍用戶進入路段ei的概率

定義兩個矩陣,分別是行為預測概率矩陣C（v,t-1)[13]和歷史行為矩陣H（v,t-1).

C（v,t-1)表示用戶從路段ei轉到路段ej的概率分布,其中t-1表示時刻,v表示交叉點的速率,e1,e2,…,em表示與此交叉點直接相連的路段,p（e2|e1)表示用戶在路段e1上轉到e2上的概率.

匿名服務器會記錄發送過請求的用戶的所有歷史行為信息形成矩陣H（v,t-1),也就是路段行駛的次數以及轉向的情況.

1.2.3 計算過程

當路段ei上的活躍用戶數目小于k值時,可以利用ei上的不活躍用戶來完成k匿名.如圖3所示,與路段ei直接相連的其他路段（ei-3,ei-2,ei-1)上的用戶在t-1時刻發出請求,而在t時刻未發出請求定義為不活躍用戶,這部分用戶的集合用Una表示,t時刻在路段ei上的不活躍用戶用Uia來表示,mi和mia分別表示集合Una和Uia的用戶數量.容易得出Uia?Una,且mia≤mi.

圖3 用戶進入路段

（1)計算單個不活躍用戶進入路段ei的概率.若用戶uk∈Una,根據歷史行為矩陣H（v,t-1),服務器會找到所有可能進入路段ei的路徑.

在PLA算法中,不需要知道在時刻t用戶uk的位置是否活躍,但是需要關心是否在路段ei上或者行駛進ei的可能性.即使知道用戶在哪條路段上,也不能確定用戶是否在ei上.對于用戶uk∈Una,服務器會計算出此用戶的速率范圍表示在時刻t-1到時刻t的速率范圍,即

其中,D（·)表示路段上兩點的距離.

如圖3所示,在時刻t用戶在點A處,點C和B表示路段ei的起點和終點,若用戶能夠進入路段ei,則在時刻t,要求

則表示當用戶uk在t時刻選擇路段emk時,能夠進入路段ei時的速率范圍.

所以,計算出速度的變化量為

為了方便計算,將Ek變換為E

則用戶uk能夠進入路段ei的概率為

表示每個用戶進入路段ei中的概率.

（2)計算m個不活躍用戶uk∈Una進入路段ei的概率

其中,bk∈bI,mi是bI中元素的個數,注意m并不是冪指數,指的是m個形式為bk的數相乘,mi-m的意義與m相同,表示mi-m個形式的1-bk相乘.

例如 bI={b1,b2,b3},則

如圖1所示,路段e3上僅有2個活躍用戶,采用PLA算法則還需要選取兩個不活躍用戶,若p=大于某一概率值如0.9時,就可以將dCD作為匿名路段.

2 實驗仿真

2.1 實驗數據及參數

（1)實驗環境.假設每個移動用戶在結點處的初始速度是30 km/h,且只能沿著道路行駛,他的主要屬性包括速率、轉向和加速度（本實驗中即速率的變化量).移動用戶在一個時間戳內會改變速率也就是加速度,加速度符合正態分布,設均值和方差分別是0 km/h和15 km/h.

使用基于網絡的移動對象發生器[14]產生移動點,并且模擬它們在15 km×15 km德國的奧爾登堡的4種道路上的行駛狀況,包括高速公路、國道、一般公路和街道.路網仿真器產生隨機分布的5 000個移動用戶,將這些用戶的歷史信息存入數據庫F,并且生成一個請求集合,包括移動用戶的ID、地理位置、請求內容和請求時刻t以及匿名值k.

（2)實驗參數.本實驗通過與沒有用預測矩陣的利用路網的k匿名方法做比較,根據路段長度的平均減少率dm來評估PLA算法的性能.

2.2 實驗分析

路段長度的減少率用來評價PLA算法的服務質量.假設未使用PLA算法時得到用戶請求定位的路段長度為,而PLA算法得到的路段長度為RL,則路段長度的減少率可定義為.分別選取不活躍用戶數量與活躍用戶數量比例為1∶1或2∶1進行實驗.每個活躍用戶的匿名值k范圍選取3～7.所有請求用戶在不同的匿名值下取平均減少率dm.設置不同的時刻t和匿名值k來驗證匿名路段長度的平均減少率dm的變化趨勢.

圖4 實驗結果示意圖

由圖4（a)可知,使用PLA算法后,在相同時刻t,用戶匿名路段的平均減少率dm在不同匿名值k下可高達0.5以上,并且k值越大,匿名路段的dm值越小,這是因為隨著匿名值k的增大,增大了不活躍用戶滿足k匿名的難度.由圖4（b)同樣可看出用戶在相同匿名值k的情況下,其匿名路段的平均減少率dm在不同時刻t的條件下同樣可達到0.5左右,而50 s處相比40 s的dm值出現了較大的增長,可能是50 s時不活躍用戶在此路段上比較密集,所以較容易滿足k匿名,使得匿名路段較短.從圖4還可看出,當不活躍用戶增多時,路段長度的平均減少率dm就越大,因為不活躍用戶越多,其分布會越密集,就越容易滿足用戶的隱私需求,匿名路段長度的平均減少率dm也就越小,PLA算法也就越精確.實驗證明,PLA算法可以在一般的k匿名算法的基礎上很大程度地減小匿名路段長度,從而更好地保護用戶的隱私,減小通信開銷.

3 結束語

針對位置隱私保護的需求,文中提出了一種在路網中利用概率的位置匿名PLA算法.該方法可充分利用不活躍用戶,通過計算不活躍用戶進入匿名路段的概率,達到提高匿名區域用戶數量的目的.實驗證明,PLA算法可以在一般的k匿名算法的基礎上很大程度地減小匿名路段長度,從而更好地保護用戶的隱私,減小通信開銷.

[1]Duri S,Gruteser M,Liu X,et al.Framework for Security and Privacy in Automotive Telematics[C]//Proceedings of the 2nd International Workshop on Mobile Commerce.New York:ACM,2002:25-32.

[2]Wang Y,Xu D,He X.L2P2:Location-aware Location Privacy Protection for Location-based Services[C]//Proceedings of IEEE INFOCOM.Piscataway:IEEE,2012:1996-2004.

[3]Wang Q,Xu Z,Qu S.An Enhanced K-Anonymity Model Against Homogeneity Attack[J].Journal of Software,2011,6(10):1945-1952.

[4]Gruteser M,Grunwald D.Anonymous Usage of Location-based Services through Spatial and Temporal Cloaking[C]// Proceedings of the 1st International Conference on Mobile Systems,Applications and Services.New York:ACM,2003: 31-42.

[5]Beresford A R,Stajano F.Location Privacy in Pervasive Computing[J].IEEE Pervasive Computing,2003,2(1):46-55.

[6]Kim M,Fielding J J,Kotz D.Risks of Using AP Locations Discovered through War Driving in Pervasive Computing [M].Berlin:Springer,2006:67-82.

[7]Xu T,Cai Y.Exploring Historical Location Data for Anonymity Preservation in Location-based Services[C]// Proceedings of the 27th IEEE Communications Society Conference on Computer Communications.Piscataway:IEEE,2008:1220-1228.

[8]Chow C Y,Mokbel M F.Trajectory Privacy in Location-based Services and Data Publication[J].ACM SIGKDD Explorations Newsletter,2011,13(1):19-29.

[9]Suzuki A,Iwata M,Arase Y,et al.A User Location Anonymization Method for Location Based Services in a Real Environment[C]//Proceedings of the 18th ACM International Symposium on Advances in Geographic Information Systems.New York:ACM,2010:398-401.

[10]Kato R,Iwata M,Hara T,et al.A Dummy-based Anonymization Method Based on User Trajectory with Pauses[C]// Proceedings of the 20th ACM International Symposium on Advances in Geographic Information Systems.New York: ACM,2012:249-258.

[11]Yigitoglu E,Damiani M L,Abul O.Privacy-preserving Sharing of Sensitive Semantic Locations under Road-network Constraints[C]//Proceedings of the 13th IEEE International Conference on Mobile Data Management.Washington: IEEE Computer Society,2012:186-195.

[12]Pan X,Xu J,Meng X.Protecting Location Privacy against Location-dependent Attacks in Mobile Services[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(8):1506-1519.

[13]Karimi H A,Liu X.A Predictive Location Model for Location-based Services[C]//Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems.New York:ACM,2003:126-133.

[14]Thomas Brinkhoff:Network-based Generator of Moving Objects[EB/OL].[2014-05-20].http://iapg.jade-hs.de/ personen/brinkhoff/generator/.

（編輯:李恩科)

Probability-based location anonymity algorithm

YAN Yushuang,TAN Shichong,ZHAO Dawei
(State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

As one of the most effective location privacy preservation technologies,the k-anonymity model provides safeguards for location privacy of the mobile client against vulnerabilities for abuse by constructing an anonymous area of k users including the protected one.However,most existing k-anonymity models only utilize the users who are sending requests at recent time.If there are not enough requesting users,the generated anonymous area of the k-anonymity model will be larger than expected.In this paper,a Probability-based Location Anonymity(PLA)algorithm is proposed for protecting location privacy of the mobile users in a road network.The PLA model takes advantage of the historical path track of the users who are not sending the request currently,and then computes the probability into the anonymous section so that it can greatly reduce the size of the anonymous area.Experimental results show that the PLA algorithm is superior to the k-anonymity and it increases its anonymous efficiency enormously.

k-anonymity;inactive users;probability;PLA algorithm

TP918.91

A

1001-2400（2015)06-0075-06

10.3969/j.issn.1001-2400.2015.06.014

2014-07-13

時間:2015-03-13

中央高?；究蒲袠I務費專項資金資助項目（K5051201027);高等學校學科創新引智計劃資助項目（B08038)

閆玉雙（1987-),女,西安電子科技大學博士研究生,E-mail:yushuangy15@163.com.

譚示崇（1979-),男,副教授,E-mail:sctan@mail.xidian.edu.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20150313.1719.014.html