LBS中面向K_匿名服务资源约束的匿名度调节算法

45720117浙江大学学报()JournalofZhejiangUniversity(EngineeringScience)Vol.45No.7Jul.2011:20100129.()::(60773180,60903169);(AGK2008004).:(1979-),,,.Email:[e-mail]:,,.Email:[e-mail]:10.3785/j.issn.1008973X.2011.07.003LBSK杨朝晖1,李善平1,林欣1,2(1.,310027;2.,200241):(LBS)K(QoS),,QoSR*,LBS,.,.,,QoS.:(LBS);K;;(QoS):TP393:A:1008973X(2011)07115407AnonymityleveladaptationalgorithmtomeetresourceconstraintofKanonymityserviceinLBSYANGZhaohui1,LIShanping1,LINXin1,2(1.CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027,China;2.DepartmentofComputerScienceandTechnology,EastChinaNormalUniversity,Shanghai200241,China)Abstract:AlimitationincurrentdesignofKanonymityservicesforlocationbasedservices(LBS)isthattheyonlyprovideagivenminimumlevelofanonymityasQoSguaranteeandcantimprovetheanonymitylevelforuserswhenserviceresourcesarecapable.TheanonymousqueryresultsizewasproposedasanewQoStargetinordertomeasureandconstrainresourceconsumptionontheKanonymityserviceandLBSperuserquery.Thenappropriateanonymitylevelcanbeselectedundersuchconstraint.Theoreticalanalysiswasperformedtofindmathematicalrelationbetweenanonymousqueryresultsizeandanonymitylevel,leadingtotheconstructionofanonymityleveladaptationalgorithm.Thesimulationresultsaccordedwellwiththetheoreticalrelation.TheanonymityleveladaptationalgorithmcancontrolanonymousqueryresultsizetostayaroundthespecifiedQoStarget.Keywords:locationbasedservices(LBS);Kanonymity;anonymitylevel;qualityofservice(QoS)K(locationbasedservice,LBS),KK,K-1,LBS().K,.K,CliqueCloak[1]Casper[2]kNNCloak[3]HilbertCloak[3].,kNNCloakK,.HilbertCloakHilbert.K,K,Chow[4]P2PKGhinita[5]hilbASR.K,.[6]LBSK.Xu[7]MaxAccu_CloakMinComm_Cloak,.KQoS,KLBS.,,,,.,QoSR*,.kNN,,R*.1R*KLBS,LBS,.LBS,.1)LBS.LBS(Rtree),[89],.().2).LBS,.(k),,.3).LBS4:a);b);c)LBS;d).a)b);c),d),.P2P,();,LBS,.,,,R*.1qRq,RqE(|Rq|)=R*,R*,R*.R*R*.1KFig.1Kanonymityserviceaugmentedwithanonymityleveladaptation2R*,,.1.R*,()K|R|,KK0(KK,KK0,.)K0|R|,1155第7期杨朝晖,等:LBS中面向K匿名服务资源约束的匿名度调节算法,,.|R|K0.,,|R|K0.k(knearestneighborquery,kNN,k)(rangequery,)2LBS.kNN|RkNN||Rran|.|RkNN||Rran|K0.2.1|RkNN|K,[7],|RkNN|:|RkNN|=(A+PdkNN+d2kNN).(1):AP,dkNNk,.[10],N,dkNNdkNN=k/N.,N=,dkNN=k/.(2),,,AP:P=4A.(3)(2)(3)(1),|RkNN|=A+4kA+k.(4)u,K=Au,A=K/u,(4)|RkNN|=Ku+4kKu+k.(5)2.2|Rran|K[7],Rran=A+Pd+d2.:d.,Rran=Ku+4dKu+d2.(6)(5)(6)|RkNN||Rran|K,u.:Ku,;.,u.,u,|R|(|RkNN||Rran|),(5)(6)|R|u().u,(5)(6).2.3KK0KKK0,..K0K,KK0K=f(K0).2KK0Fig.2KtoK0relationofdifferentanonymityalgorithmsandtheirlinearfit2(a)(b)kNNCloakHilbertCloakKK0.,K=a+bK0.,kNN1156浙江大学学报(工学版)第45卷K,HilbertCloakK,.2(b)K=25K0(),,KK0.,HilbertCloak,fHilbertCloak.FUNCTIONfHilbert_Cloak(K0,Q):K0-Q-(ID)T-,HilbertCloak:C-K-CBEGINt0;K0K0+1;K;REPEATtt+1;K0K0-1;(C,K)Hilbert_Cloak(K0,Q);IF(K/K0K/K0)CC;KK;ENDIFUNTIL(tT)or(K25K0)RETURN(C,K)ENDK25K0HilbertCloak(K0),K25K0T;K/K0.fHilbertCloakHilbertCloak,K.2(c)fHilbertCloakK(T=5).HilbertCloak,K,.KHilbertCloak,,fHilbertCloakHilbertCloak12(T=5),.kNNCloakfHilbertCloak,f(K0)=a+bK0K.()K,f:K0=f-1K=K-ab.(7)ab:(K0,K),ab.,n(K0i,Ki),ab:b=ni=1K0iKi-nK0Kni=1K20i-nK02,a=K-bK0.(8):K0KK0iKi.2.4|RkNN||Rran|K0(7)(5)(6),|RkNN||Rran|K0:|RkNN|=a+bK0u+4ka+bK0u+k,(9)Rran=a+bK0u+4da+bK0u+d2.(10)3R*,|R|R*(|R||RkNN||Rran|).,|R|=R*K0,K0.K0:FUNCTIONadjusted_anonymity()BEGIN1)|R|=R*K;2)(8)ab;3)K0(K-a)/b;(7);4)RETURNK0;END,1)(5)(6)K.kNN,(5)R*,K:Ku+4kKu+k-R*=0,K=-2k+4-1k+R*2u.u,,u.K.(6)(7)R=AK+BK+C,ABCK.,,ABC.K1,|R1|,1157第7期杨朝晖,等:LBS中面向K匿名服务资源约束的匿名度调节算法R1=AK1+BK1+C.=R*/|R1|,K=K1,R=AK+BK+C=AK1+BK1+C.1,AK1+BK1+CAK1+BK1+CAK1+BK1+C,R1RR1=R*;1,R1RR*.K=K1,|R||R1|R*,|R1|R*(|1-|),.,|R|=R*K:K=K1=R*K1R1.(11)(11)K,(5)(6)K,2:1)u,;2)u.,(11)K.44.1.,Brinkhoff[11]GeneratorofNetworkbasedMovingObjects(Generator),Oldenburg.100,30005319;5000,3258.,,.Gernerator,,.350.4.,Nu,No.,10%,K0(2)(8)ab,n=1000),QoSR*.350Fig.3Userdistributionat50thperiod4Fig.4Numberofusersandobjectsovertime4.21|R|K0u(9)(10).kNN2kNNCloakfHilbertCloak24,.,QoSKmin=10,R*[50,150]().kNN,|RkNN|(a+bK0)/u,5(a)(b)(a+bK0)/u,|RkNN||RkNN|.,u.,(10),|Rran|(a+bK0)/u,5(c)(d)=10-5,(a+bK0)/u|Rran|.5,4,|R|,..1).1158浙江大学学报(工学版)第45卷5|R|Fig.5Comparisonofsimulation|R|samplesandtheoreticalcurve,,,5.,u,.u,.2).P=4A((3)),.,(9)(10).,P4A(P-4A)/P1%,.3).23,K0K.2,kNNCloak,K(a+bK0)20%,fHilbertCloak,40%,.5(a)5(c)5(b)5(d),,(5)(6)2.fHilbertCloak,|R|kNN,,K0,fHilbertCloakKkNN,2.4.32|R|(R*).224,QoSKmin=10,R*=100.R*,|R|,|R|T(6).6R*=100,K.1,Kmin,(9)K1|R1|;2,,K,|R|R*;,,K,|R|R*.,|R|R*.4,2,,fHilbertCloak2|R|.,fHilbertCloakK,|R|.fHilbertCloak|R|R*50%,LBS,(,HilbertCloak|R|R*80%,|R|,fHilbertCloak;,HilbertCloak.)6|R|KFig.6Simulationsseriesof|R|andKovertime5KLBS1159第7期杨朝晖,等:LBS中面向K匿名服务资源约束的匿名度调节算法,QoS,..,,QoSR*.kNN2kNNHilbert2,.,,.LBS,LBS,LBS,.(),,,,.(References):[1]GEDIKB,LIUL.Locationprivacyinmobilesystems:apersonalizedanonymizationmodel[C]Proceedingsofthe25thInternationalConferenceonDistributedComputingSystems.Columbus:IEEE,2005:620629.[2]MOKBELM,CHOWC,AREFW.ThenewCasper:queryprocessingforlocationserviceswithoutcompromisingprivacy[C]Proceedingsofthe32ndInternationalConferenceon