35ARIADNE A Dynamic Indoor Signal Map Construction and Localization System ABSTRACT
上亿文档资料，等你来发现
35ARIADNE A Dynamic Indoor Signal Map Construction and Localization System ABSTRACT
ARIADNE:ADynamicIndoorSi；LocalizationSystem；ComputerScienceandSoftwa；AuburnUniversity；{jiyimin,；YimingJi,Sa?adBiazSantos；ElectricalandComputerEng；AuburnUniversity；{pandesg,pagrawal
ARIADNE:ADynamicIndoorSignalMapConstructionandLocalizationSystemComputerScienceandSoftwareEngineeringAuburnUniversity{jiyimin,YimingJi,Sa?adBiazSantoshPandey,PrathimaAgrawalElectricalandComputerEngineeringAuburnUniversity{pandesg,pagrawal}@auburn.edusbiaz}@auburn.eduABSTRACTLocationdeterminationofmobileuserswithinabuildinghasat-tractedmuchattentionlatelyduetoitsmanyapplicationsinmobilenetworkingincludingnetworkintrusiondetectionproblems.How-ever,itischallengingduetothecomplexitiesoftheindoorradiopropagationcharacteristicsexacerbatedbythemobilityoftheuser.Acommonpracticeistomechanicallygenerateatableshowingtheradiosignalstrengthatdifferentknownlocationsinthebuilding.Amobileuser’slocationatanarbitrarypointinthebuildingisdeter-minedbymeasuringthesignalstrengthatthelocationinquestionanddeterminingthelocationbyreferringtotheabovetableusingaLMSE(leastmeansquareerror)criterion.Obviously,thisisaverytediousandtimeconsumingtask.ThispaperproposesanovelandautomatedlocationdeterminationmethodcalledARIADNE.Usingatwodimensionalconstruction?oorplanandonlyasingleactualsignalstrengthmeasurement,ARIADNEgeneratesanesti-matedsignalstrengthmapcomparabletothosegeneratedmanuallybyactualmeasurements.Giventhesignalmeasurementsforamo-bile,aproposedclusteringalgorithmsearchesthatsignalstrengthmaptodeterminethecurrentmobile’slocation.TheresultsfromARIADNEarecomparableandmayevenbesuperiortothosefromexistinglocalizationschemes.Figure1:SignalStrengthMeasurementCategoriesandSubjectDescriptorsC.2[Computer-CommunicationNetworks]:NetworkOperations,MiscellaneousGeneralTermsDesign,AlgorithmsKeywordsLocalization,indoorradiopropagationmodels,clustering1.INTRODUCTIONRecently,thedemandforwirelesscommunicationshasgrowntremendously.Theincreasingmarketfor“informationanywherePermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforpro?torcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthe?rstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspeci?cpermissionand/orafee.MobiSys’06,June19C22,2006,Uppsala,Sweden.Copyright2006ACM1-/06/0006...$5.00.anytime”hasbeenadrivingforceforincreasingadvancesinmo-bilewirelesscommunications.Locationmanagementandmobilitymanagementarecriticalissuesforprovidingseamlessandubiq-uitouscomputingenvironmentformobileusers.Foroutdoorenvi-ronments,satellitepositioningsystems(e.g.,theGlobalPositioningSystem[1])offerscalable,ef?cient,andcost-effectivelocationser-vicesthataretodayavailabletothelargepublic.Unfortunately,thesatelliteemittedsignalscannotbeexploitedindoortoeffectivelydeterminethelocation.Thedesignandimplementationofaconve-nient,scalable,andcost-effectiveindoorlocationsystemremainstothisdayachallengefortheresearchcommunity.PriortothewidespreadandpopulardeploymentofRF802.11wirelessnetworks,locationsystemsweredesignedusingaspeci?ctechnologyindependentlyfromdatacommunicationnetworks.Suchlocationsystemsexploitinfra-red(IR)(ActiveBadge[2]),ultra-sound[3,4,5],magnetic?eld[6],orlight(cameras)[7].Suchearlylocationsystemsrequirespecializedhardwareusedonlyforthelocationdeterminationandincuringeneralahighdeploymentandmaintenancecost.Inrecentyears,thepopularsuccessandwidespreaddeploymentofRF802.11wirelessnetworksenticedmanyresearcherstoexploitexistingRF802.11wirelessnetworkinfrastructuretobuildlocationsystems.Oversimplifying,iftheradiopropagationsignalstrengthistightlycorrelatedwiththedistancebetweenemitterandreceiver,thenlo-cationdeterminationwouldbeatrivialproblemthatcouldbesolvedbyoneofthefollowingtwoapproachesasillustratedinFigure1.Figure1(a)illustratesaclient-basedschemewherethreeemittersA,B,andCareatknownpositions.Amobile(client)wouldlis-tensuccessivelytothethreeemittersandwouldmeasurethesignalstrength.Ifthemeasuredsignalstrengthyieldsthedistancefromeachemittertothemobile,thelocationofthemobilereducestothesolutionofasimplesystemofthreequadraticequationswithtwounknowns(assumingthemobilemovesinaplan).NotethatFigure2:ARIADNEsurementsmadebythethreesniffersasonesignalstrengthmea-surementtripletM(SA,SB,SC)(L,t)whereSA,SB,andSCarethesignalstrengthsmeasuredforpacketsreceivedbyrespec-tivelysniffersA,B,andCfrommobileMatlocationLandtimet.ARIADNEconsistsoftwomodules:(1)the?rstMAPGEN-ERATIONmoduleestimatesasignalstrengthmapSS-MAPwhengivenasinputatopviewCAD?oorplanandONEsignalstrengthmeasurementtripletM(SA,SB,SC)(LR,t)foramobileMlo-catedatsomereferencelocationLRinthebuildingatsometimet,and(2)thesecondSEARCHmoduledeterminesthelocationofamobileMwhengivenasinputtheestimatedsignalstrengthmapSS-MAPandthecurrentsignalstrengthmeasurementtripletM(SA,SB,SC)(L,Now)ofmobileMatsomelocationL.Thecontributionsofthisworkaddressthetwomodules:1.MAPGENERATION:asoundradiopropagationmodelisdevelopedandvalidated.Theparametersofthismodelareidenti?edusingraytracingandsimulatedannealingalgo-rithm.ThegenerationofanaccuratesignalstrengthmapSS-MAPrequiresonlyonesignalstrengthmeasurementtriplet.2.SEARCH:Aclusteringbasedalgorithmisproposed.Thisclusteringbasedalgorithmoutperforms,toourknowledgeatthistime,allsearchalgorithmsusedsofarbythecommunityinthesearchphase.TheaccuracyofARIADNEis,toourknowledge,betterthantheaccuracyreportedsofarforRF802.11basedlocationsystems.Mapgenerationandthelocationsearchwereextensivelytestedandvalidated:simulationresultsillustratethatsignalstrengthesti-mates?twellwithactualmeasurements,withamaximumaveragedifferencearound1.4%ofmaximumReceivedSignalStrengthIn-dicator(RSSI),andamaximummeansquareerrorMSEaround0.75.Withtheestimatedsignalstrengthmapusingonlythreesnif-fersona?oorplanof45.72m×36.57m,theproposedlocalizationschemeworkscomparablewithmostreportedlocalizationmethodswithmaximummeanerrorwithin3.0metersandstandarddeviationbelow2.5metersforatypicalof?ceenvironment.Theremainderofthepaperisorganizedasfollows:Section2describespreviousworkdoneonlocationestimationoverindoor802.11networks.Section3introducesARIADNEsystem.Sim-ulationandexperimentalcomparisonarepresentedinSection4.Section5discussestheperformanceimprovementandmobileuserlocalization.AndSection6concludesthepaperandoutlinesfutureresearch.inthisscheme,theclienthasanactivepartinthelocationprocess:itmeasuresthesignalsandinfersitslocation.Adualapproach,thenetwork-basedscheme,isillustratedinFigure1(b):threesnif-fersatknownpositionslistentothemobileandmeasurethesignalstrengthofreceivedpackets.Itsuf?cestocollectthesignalstrengthmeasurements(overthenetwork!)fromthethreesnifferstode-terminethelocationusingbasiccalculations.Unfortunately,therelationshipbetweensignalstrengthanddistanceisnotstraightfor-wardandisdynamicinnature:evenifamobiledoesnotmove,thesniffersinFigure1(b)willmeasurethesignalstrengththatvariesovertime.Moreover,twomobilesthatarequiteclosemaygeneratesignalsofsigni?cantlydifferentstrengthatthesamesniffer.Thesedif?cultiesmakeasolutiontolocationdeterminationquiteelusive.Inordertoaddressthisproblem,researchersproposedatwostepsolution:First,establishasignalstrengthmapSS-MAPwherethesignalstrengthatknownandpredeterminedlocationsiseitherman-uallymeasuredortheoreticallyestimated,andSecond,measuresignalstrengthforamobileatagivenlocationandSEARCHthesignalstrengthmapSS-MAPforthe“closest”locationthatwiththebestsignalstrengthmeasurementmatch.TheRADAR[8]sys-temproposedbyBahlandPadmanabhanisexemplaryofsuchanapproach:theauthorsadoptaclient-basedscheme,collectand,recordtheradiosignalstrengthreceivedatamobile(methodinFigure1(a))fromthreebasestationsasafunctionoflocationataselectedsetofpredeterminedandknownlocations.SuchrecordsconstitutewhatwecallasignalstrengthmapSS-MAP.Thismea-suredsignalstrengthmapwasusedbytheauthorsintwodifferentstrategies:(1)the?rststrategy(theydubbed“empiricalmethod”)consistsofthemobilesensingthesignalstrengthfromthethreebasestationsandsearchingforarecordinthemeasuredSS-MAPforthebestsignalstrenand(2)thesecondstrategyconsistsofusingasimplepropagationmodeltoconstructanestimatedSS-MAPthatisvalidatedusingthemeasuredSS-MAP.EstimatingismoreconvenientthanmeasuringaSS-MAPespeciallyforalargebuilding.TheestimatedSS-MAPisusedthesamewayasthemeasuredSS-MAPinstrategy1.Unfortunately,theauthors[8]reportthatthe?rststrategy(i.e.,the“empiricalmethod”)outper-formedthesecondstrategythatusestheestimatedSS-MAP.ThekeyweaknessofthesecondstrategyisthattheradiopropagationmodelresultsinanestimatedSS-MAPdoesnot?twellthemea-suredone.Thisworkproposesaconvenientandscalablelocationsystem(Please,seeFigure2),dubbedARIADNE.ARIADNEisanetwork-basedlocationschemethatrequiresthreesnifferstocovera?oorplanasshowninFigure1(b).Eachsnif-ferlistenstoamobileunderconsiderationandmeasurestheaver-agesignalstrengthofpacketsemittedbythemobile.Intherestofthepaper,werefertothethreeaveragesignalstrengthmea-2.2.1RELATEDWORKMapGenerationThissectionwillseparatelysurveyrelatedworkformapgener-ationandlocationsearch.Researchonindoorradiopropagationisanactive?eld.Astudyofindoorradiopropagationcharacteristicscanbefoundin[9,10].Adetaileddescriptionofearlierradiopropagationmodelscanbefoundin[11].Basedontheraytracingtechnique,severalstatisticalmodelshavebeenanalyzedrecently[12,13,14].Whenconsider-ingthelarge-scaleattenuationmodel,mostresearchersmodeltheradiopropagationpathlossasafunctionoftheattenuationexpo-nentn(Please,seeEquation1),whichistwoforfreespacebutgreaterthantwoforanindoorenvironment.P(d)[dB]=P(d0)[dB]?10×n×log10(d)d0(1)whereP(d)isthepoweratdistancedtothP(d0)isthepoweratareferencedistanced0,usuallysetto1.0meter.nistheattenuationexponent,whichisoftenstatisticallydeterminedtoprovideabest?twithmeasurementreadings.Basedontheconsideredparametersintheradiopropagationmodel,allradiopropagationmodelscangrosslybegroupedintothreecategories:(1)Si(2)Pand(3)Site-speci?cmodel.SimpleattenuationmodelisintheformofEquation1,anditisthebasemodelfortheothermodels.Hills,Schelegel,andJenkins[14]usedthismodelaspartofanautomateddesigntooltoestimatethecoverageareasforasetofAPs.Differentfromthesimpleattenuationmodel,thepartitionmodelreducesthepasslosseffectfromtheattenuationexponentbyaddi-tionalconsiderationoftheattenuationeffectsfromtheindoorparti-tions,likewallsand?oors.Manysuccessfulmodelsbelongtothisgroup.AcoupleoffamousexamplesincludePhaiboon’sstatisticalmodel[13],andwallattenuationfactormodelinRADAR[8].TheRADARsystemconsidersattenuationeffectsfromwallsalongthedirectpathbetweenthetransmitterandthereceiveronthesame?oor.RADAR’slocationsearchintheestimatedsignalstrengthmapSS-MAPyieldsanaverageresolutionofabout4.3m[8].Site-speci?cmodelissimilartothepartitionmodelexceptthatitrelatestopathlosswithsite-speci?cparameters(geometrics,ma-terials,andthickness).TworepresentativemodelsincludeHassan-AliandPahlavan’sprobabilitymodel[12],andLottandForkel’smulti-wall-and-?oormodel[15].Comparedwiththeothermod-els,thesite-speci?cmodeldoesnotdependonspecialassumption,soitworksonmostgeneralbuildingenvironment.However,itiscomplexandrequiresdetailedsite-speci?cparameters.Alltheseradiopropagationmodelshavethefollowingshortcom-ings:1.Tediousandextensivemeasurementsarerequiredinordertodeterminethebuilding-speci?cattenuationexponentandtheattenuationcoef?cientsofindoorpartitions.2.Themeasurementsdonotconsiderthedynamicbehavioroftheindoorradiopropagation.3.Theyonlyconsiderthepathlossalongthedirectpathbe-tweenthetransmitterandthereceiver4.Detailedmaterialcharacteristicsandgeometrypropertiesarerequiredifsite-speci?cmodelistobeused.Theabovemodelsarenotconvenientorscalableinrealsettings.Incontrast,ARIADNErequiresonlyONEsignalstrengthmeasure-mentandatopview?oormaptoestimatethesignalstrengthmap(Please,seeFigure2).Iftheenvironmentishighlydynamic,ARI-ADNEcanbeusedtomonitorauniquepointofmeasurementandgenerateondemandanupdatedsignalstrengthmap.Simulatedannealing(SA)algorithmisusedtodynamicallydeterminetheat-tenuationparameters.Consequently,withrealtimemeasurement,thesignal-strengthmaptablecoulddynamicallybebuilt.2.2LocationSearchAspointedearlier,inordertolocateamobileuserinsidethebuilding,asimplemethodistosearchtheSS-MAPforthesignalstrengthofthemobileuser.Ifthereisamatchinthetable,thecorrespondinglocationisusedtodenotethemobileuser’sposi-tion.Otherwise,ifanexactmatchisnotobtained,thelocationwithclosestsignalstrengthtothemeasurementisselectedastheesti-mate.Ageneralcomparisonmetricistheleastmeansquareerror(LMSE).D=1minNk=1{(nn??i=1whereDistheleastmeansquareerror,Nisthetotalnumberofrecordsinthesignalstrengthmaptable,kdenotesthekthrecordintheSS-MAPnisthenumberofsniffers.ssm,i,kdenotesmeasuredsignalstrengthatsnifferiofthemobileuser,andssi,kisthesignalstrengthrecordatasnifferiinSS-MAPtable.Thenear-estneighborsinsignalspacemethodbyBahlandPadmanabhan[16]isessentiallythisapproach.AproblemwithLMSEisthattwoormoreverydifferentloca-tionscouldpotentiallyhavesamesignalstrength,thusadditionalprocessingmustbecarriedoutinordertoselectamoreaccuratees-timate.Therefore,moreadvancedlocalizationmethodsarehighlydesirable.Prasithsangaree,Krishnamurthy,andChrysanthis[17]proposedaclosenesseliminationscheme.Themainpurposeisto?ndmorethanthreelocationsfromtheSS-MAPtablewithsignalstrengthclosetothemeasurement.Fromthese,thethreeclosestpo-sitionsareselectedandtheirpositionaverageisusedtodenotetheestimatedlocationforthemobileuser.Similarly,in[18],Pandeyetal.usedthesecondlowestMSEtoassisttheestimation.TheyfoundthatiftheLMSEandthesecondlowestmeansquareerrorarephysicallyadjacent,thenthemiddleoftheirlocationsyieldsbetterestimates.HatamiandPahlavan[19]alsoproposedamodi?edLMSEalgo-rithm,dubbedprioritizedmaximumpower.Thismethodsortsmea-suredsignalstrengthindescendingorderforallsnifferssothatacontributionpriorityofeachsnifferinthemappingprocedureisob-tained.Accordingtothepriority,theestimatesarerestrictedtoasetofreferencepoints.ThenLMSEorclosenesseliminationschemeisusedtodeterminethe?nalestimates.Youssef,Agrawala,andShankar[20]clusteredthepositionsintheSS-MAPwiththeobjectiveofreducingthecomputationrequire-mentandtoimproveestimationaccuracy.Inthemethod,theclus-terisde?nedasasetoflocationssharingacommonsetofaccesspoints(calledclusterkey).Consequently,theSS-MAPissortedac-cordingtotheclusterkeys.Todeterminethemobileuser’slocation,asmallsetofaccesspoints(withstrongestsignalstrengthmapping)areusedtodetermineaclusterforthemostprobablelocation.In[21],Agiwaletal.appliedthesimilarideaintheLOCATORsys-tem.Insummary,tolocateamobileuser,existingsignalstrengthbasedlocalizationmechanismsassumepreciseSS-MAPwithwhichtheLMSEtechnique(anditssimplederivatives)isusedto?ndamatch.TheclusteralgorithmfromYoussefetal.[20]isusedtoop-timizethecomputationperformanceandenhanceestimates.ARI-ADNEproposesanothermodi?cationofLMSE,dubbedclustering-basedsearchmethod.ThismethodissimilartoPrasithsangareeetal.[17]withthedifferencethatthe?nalpositionsarenotnecessar-ilythree.TheproposedmethodisspeciallydesignedforimpreciseSS-MAPtables,andisdifferentfromYoussef’sclusteringapproachbecausethismethoddoesnotsortorclusterreferencepositionsac-cordingtocommonaccesspoints,butinstead,itselectandclusterasetofcandidatepositionswithsmallermeansquareerrors.Thelargestclusterischosenanditscenterispickedasthelocationes-timate.2.3SimilarSystems(ssm,i,k?ssi,k)2)}(2)TheRADARsystem[8,16],theclosesttoARIADNE,proposesanindoorradiopropagationmodelforlocalizationandtracking.Althoughthesystemrequiresextensivemeasurementsandcalibra-tion,theachievedlocalizationperformanceisnotsatisfactory.TheRADARradiopropagationmodeldoesnotfullycapturethemulti-pathphenomenonasitonlyconsidersradiopropagationalongthedirecttransmissionpath.Similarly,Hatamietal.[19]usedraytracingsoftwaretogener-ateareferencesignalstrengthmapSS-MAP.Theproposedsystemuses?veAPsdeployedinabuildingof65×48meter.Tolo-cateamobileuser,twodifferentlocalizationmethod(LMSEandprioritizedmaximumpower)areevaluatedandcompared.There-sultsshowthattheLMSEmethodprovidesbetterestimationper-formanceforuserswithinthebuilding.However,prioritizedmaxi-mumpowerislesssusceptibletoreferencegridresolutionandcanachievebetterestimateswhenmobileuserresideswithinthevicin-ityareaoutsideofthebuilding.TheresultsfromHatami(Figure3in[19])showarelationof10meterscomplementarycumula-tivepositioningerrorwith54%probabilityforprioritizedmaxi-mumpowermethod.TheresearchbyHatami[19]mainlyfocusedonlocalizationalgorithmstargetedatintruderdetection.ItusesraytracingsoftwaretoconstructsignalstrengthmapSS-MAPwithoutintroducingtheindoorradiopropagationmodel.Differentfromthesesystems,thispaperintroducesARIADNE,anewindoorlocalizationsystem.Itcontainstwomodules,the?rstmoduleismapgeneration,anditincludesanewindoorradiopropa-gationmodel.Thesecondmoduleissearchmodule,anditpresentsaclustering-basedlocalizationalgorithmthatworksonimpreciseradiopropagationmaptables.Theradiopropagationmodeliseval-uatedbycomparingestimatesagainstactualsignalstrengthmea-surements.ThispaperreportsthelocalizationperformanceoftheARIADNEsystem,andfurthercomparestheproposedlocalizationalgorithmwithotherexistingalgorithms.Figure3:Radiopropagationwithraytracing3.1.2Raytracing3.ARIADNEARIADNEconsistsoftwomodulesasillustratedinFigure2-namelymapgenerationandsearch-thataredevelopedinSec-tion3.1andSection3.2,respectively.3.1MapGenerationModuleMapgenerationincludesmultiplesteps:Subsection3.1.1devel-opsthe?rststepthatconsistsofcapturingthecharacteristicsofthe?oorplanandproducea3-Dmodelnecessaryforraytracing.Sub-section3.1.2explainshowraytracingisusedforthedeterminationoftheindividualraycontributiontothesignalstrengthonagridofpoints.Apropagationmodelisproposedinsubsection3.1.3,anditsparametersissolvedinSubsection3.1.4andSubsection3.1.5usingsimulatedannealing.Raytracing(RT)approximatestheradiopropagationwitha?-nitenumberofisotropicraysemittedfromatransmittingantenna[23].Foranomnidirectionalantenna,eachrayisassumedtotrans-mitwiththesameamountofenergyatthetransmitter,andtheen-ergyoftherayswillbeattenuatedatwallsor?oorsduetore?ec-tionsandtransmissions.Raytracingtechniquehasbeenwidelyusedtosimulatetheindoorradiopropagationcharacteristicsandtopredictthesite-speci?cfeaturesoftheindoorradiochannels[22,24,25].Rayimagingtechniquesareusedtorecordeachrayfromthetransmittertothereceiver.Intherayimagingtechnique,thetrans-mitterisassumedtobere?ectedateachsurfacearoundittopro-duceimagetransmitters,there?ectedraystothereceiverfromtherealtransmitterareconsideredasdirectpathsfromthemirrorim-agesofthetruetransmitter.Basedongeometricaloptics(GO),eachrayfromthetransmittertothereceivercanbeexactlydeter-mined.Thedetailedraytechniqueisomittedhereforlackofspace(agoodreferencecanbefoundin[24,26,27]),butinstead,severalkeypointsofARIADNEareemphasized.?SimilartotheresearchbyHassan-AliandPahlavanin[12]andBertonietal.in[28],thediffractionandscatteringeffectareneglectedintheproposedpropagationmodelbecauseoftheminorcontribution?Onlyrayswithpowerabovea?xedthreshold[29]areconsid-eredbecausehighlyattenuatedraysdonotreachthereceiverinrealityeventhoughatransmissionpathexistsintheory.?Similarto[12],themultipathpoweratreceiverisdeterminedasthesumofallindividualpowersregardlessofthephaseofeachpath.Figure3depictsasimplescenariowherethreeraysareshownfromthetransmitterTtothereceiverR.Eachrayriiscomposedbymultiplesegmentswheredistanceofthejthsegmentisdij.Di-rectpath(rayr1)isdenotedbyasolidline.Theothertwopaths(rayr2andr3)areindirectandcontainre?ections.Thefaintdashedline(rayr2)hasonere?ectionanddottedline(rayr3)hastwore-?ections,respectively.Thedistancestraversedbyeachrayisalsodepictedinthe?gure.3.1.1FloorplaninterpretationThemainpurposeofthe?oorplaninterpretationistointegratethegeometryacquisitionprocessasanautomaticprocedure.ThemajortaskoftheinterpretationprocessistoextractthestructuralparametersfromconstructionCAD?lesor?oorplanimage?les.Structuralinformationisextractedfromthepictureusingbasicimageprocessingtechniques,inwhichapictureisdenotedasamatrix.Eachelementinthematrixhasavaluecorrespondingtothebrightnessofthepixelatthecorrespondingposition,whichisanintegerbetween0and255.The0correspondstoblackand255towhite.Ifthepixelvalueofthelinesinthepictureisdenotedby0,thenthegroupingofasetofconnected0valuepixels,verticallyorhorizontally,yieldsaline.Thewallgeometryinformationisconstructedbyextendingthelinesverticallyin2Dimagewithbasecoordinatesandthe?oorheight.Bystackingthewallinformationateach?oor,overallstruc-turalrepresentationofthebuildingisobtained.Similartomostpre-viousresearch[22],awall/?oorismodelledasasingleplaneinthemiddle.Theoffsetbetweenrefractedandincidentraysisignored.3.1.3RadiopropagationmodelAsexplainedinSection3.1.2,thesignalpoweratthereceiveristheaccumulatedmultipathpowerfromallindividualraysfromthesametransmitter.Foreachray,theattenuationpathlossincludesthreecomponents:1.Thedistance-dependentpathloss,whichisassumedasfree2.Theattenuationduetore?ections,whichistheproductofthere?ectioncoef?cientandthetotalnumberofre?ectionsfromtran3.Theattenuationduetotransmission,whichistheproductofthetransmissioncoef?cientandthetotalnumberoftransmis-sionwalls.Consequently,themodelisde?nedas:Nr,jsomechangesthatincreaseit.Thus,SAmethodcanachieveglobaloptimizationwithoutgettingtrappedatalocalminima[32].TheoriginalMetropolisscheme[30]indicatesthataninitialstateofathermodynamicsystemischosenatenergyEandadesiredtemperatureT.HoldingatthattemperatureT,theinitialcon?gu-rationisperturbedandthechangeinenergydEiscomputed.Ap-plyingMonteCarlosamplingtechniques,thephysicalannealingprocessismodelledsuccessfullybycomputersimulationmethods.Aconvenientformulacanbeborrowedfromthermodynamics:E??)P(E)=exp(?kT(4)P=??i=1(P0?20log10(di)?γ?Ni,ref?α?Ni,trans)(3)wherePisthepower(indB)atreceiver,Nr,jisthetotalnum-berofraysreP0isthepower(indB)atadistanceof1di,Ni,ref,andNi,transrepresentthetotaltransmissiondistance,thetotalnumberofre?ectionsandthetotalnumberof(wall)transmissionsoftheithray,respectively.γisthere?ectioncoef?cient,andαisthetransmissioncoef?cient.InFigure3,thetransmissiondistancesforthreerays(r1,r2,andr3)ared1,1,d2,1+d2,2,andd3,1+d3,2+d3,3,respectively.Rayr2hasonere?ection,andrayr3hastwore?ections.Allthreerayshavetwowalltransmissions.WhenstartingfromtransmitterT,allthreeraysareassumedtoholdthesameamountofpower.Withdifferenttransmissionconditions,the?nalsignalpowerofeachindividualrayobservedatthereceiverRaredifferent.AndtheoverallsignalpoweratthereceiverRisthesumofthepowersfromallreceivedrays.Thesitespeci?cparameters(Nray,di,Ni,ref,andNi,trans)inEquation3canbeobtaineddirectlyfromraytracingasdescribedintheSection3.1.2.Theotherthreeparameters(P0,γ,andα),inothersimilarresearch,areusuallyderivedfromtediousmea-surements.ARIADNEdoesnotrequireextensiveonsitemeasure-ments.Instead,simulatedannealing(SA)techniqueisusedtode-termineoptimalvaluesforthethreeparametersoftheproposedmodel.ONEreferencemeasurementonlyisrequired.??whichexpressestheannealingprobabilityP(E)ofachangeonenergyEattemperatureT,wherekisBoltzmann’sconstant.Giveninitialvaluesofx=[P0γα]TatatemperatureT,thepowerofeachindividualraycanbecomputed(Equation3).(Theinitialvaluescanbeanypositivenumbers,however,bettervalueswillminimizethesearchtime.Generally,bettervaluescanbede-rivedfromliterature.)Neglectingthoserayswithpowerbelowthethreshold,andsummingthepowersofallothers,yieldthemulti-pathpoweratthereceiver.Theleastminimumsquarederror(Equa-tion2)allowsthecomparisonofthepowerestimates?tnesswiththemeasurements,andhenceforththeadjustmentoftheparametersofxaccordingly.Toadjusttheparameters,arandommovementisgeneratedbyaddingadeviatefromtheCauchydistributiontoeachparameterofx=[P0γα]T:??),i=1,2,3xi+1=xi+T?tan(P(5)ThecoolingscheduleforthetemperatureTcanuseasimplemethodsimilarto[31]:Ti+1=a?Ti,a∈(0,1)(6)Consequently,theSimulatedannealingsearchalgorithmcanbede-tailedbelow:1)De?neinitialvaluesforx=[P0γα]T.2)De?nethetemperature,TmaxforhighesttemperatureandTminfo3)CalculatetheannealingprobabilityfromEquation4;4)UpdatethedisplacementfortheparametersusingEquation5;5)Calculatethe?tnessbetweentheestimatesandthemeasure-mentsusingequation2:ifabetteragreementisobtained,keepthedisplaceelse,keepthedisplacementwi6)UpdatethetemperatureTbyequation6,andrepeatsteps3,4,and5untilT&Tminorspeci?edminimumerrorsisachieved.Simulatedannealingmethodcaneffectivelyestimateparametertriplex=[P0γα]TwithonlyONEreferencemeasurement.3.1.4ParametersEstimationToestimatetheradiopropagationparameters(referencepoweroftherayP0,re?ectioncoef?cientγ,andtransmissioncoef?cientα),somemeasurementsatreferencepositionsinsidethebuildingareneeded.Ifamaximumofnreferencemeasurementsareavail-able,alinearsystemofAx=b(derivedfromequation3)canbeusedtodeterminethethreeunknownsx=[P0γα]T.Tosolvethelinearequations,themethodofleastsquarescouldbeused.However,itisdif?cult.Asstatedearlier,onlyrayswithpowerabovecertainthresholdareconsideredintheradiopropaga-tionmodel.Orinotherwords,fromraytracingsimulation,amax-imumnumberofNraysmayexist,theoretically,fromthetrans-mittertothereceiver.Inreality,onlyn(n&N)raysareactuallyreceivedbecauseofthedifferentattenuationalongeachindividualpath.Sincesomeraysaretooweaktocontributetheenergyatre-ceiver,theymustbeeliminatedfromthelinearsystem.Suchaneliminationprocessisverydif?cultatthisstagebecauseofthelackoftheenergyinformation(again,theChickenandEggDilemma).Inthisresearch,weusesimulatedannealingalgorithmtosearchtheoptimalvalueofx=[P0,γ,α]T.3.23.1.5SimulatedAnnealingSearchAlgorithmSearchmodule:Clustering-basedSearchAlgorithmSimulatedAnnealing(SA)[30,31]isamethodusedtosearchforaminimuminageneralsystem.Itisbasedontheprocessofthewayametalcoolsdowntotheoptimalstate(theannealingpro-cess).SA’smajoradvantageisanabilityofarandomsearchwhichnotonlyacceptschangesthatdecreaseobjectivefunction,butalsoTolocateamobileuser,thecurrentuser’ssignalstrengthmea-surementtripletissearchedfromthesignalstrengthmapSS-MAPforamatch.Currently,mostsearchalgorithmsarebasedontheLMSEandselectasinglelocationastheestimate.ThismethodworksifadetailedandpreciseSS-MAPforthebuildingisavail-able.Asindicatedinmanypapers,thesignalstrengthisobserved包含各类专业文献、外语学习资料、专业论文、生活休闲娱乐、中学教育、高等教育、35ARIADNE A Dynamic Indoor Signal Map Construction and Localization System ABSTRACT等内容。