外文原文-使用多种无线技术的室内定位 Indoor Location Using Multiple Wireless Technologies

IndoorLocalizationUsingMultipleWirelessTechnologiesA.K.M.MahtabHossain,HienNguyenVan,YunyeJin,Wee-SengSohDepartmentofElectrical&ComputerEngineeringNationalUniversityofSingapore,SingaporeEmail:g0500774,u0303567,jinyunye,.sgAbstractIndoorlocalizationtechniquesusingloca-tionfingerprintsaregainingpopularitybecauseoftheircost-effectivenesscomparedtootherinfrastructure-basedlocationsystems.However,theirreportedaccuracyfallshortoftheircounterparts.Inthispaper,weinvestigatemanyaspectsoffingerprint-basedlocationsystemsinordertoenhancetheiraccuracy.First,wederiveanalyticallyarobustlocationfingerprintdefinition,andthenver-ifyitexperimentallyaswell.Wealsodeviseawaytofacilitateunder-trainedlocationsystemsthroughsimplelinearregressiontechnique.Thistechniquereducesthetrainingtimeandeffort,andcanbeparticularlyusefulwhenthesurroundingorsetupofthelocalizationareachanges.Wefurthershowexperimentallythatbecauseofthepositionsofsomeaccesspointsortheenvironmentalfactorsaroundthem,theirsignalstrengthcorrelatesnicelywithdistance.Wearguethatitwouldbemorebeneficialtogivespecialconsiderationtotheseaccesspointsforlocationcomputation,owingtotheirabilitytodistinguishlocationsdistinctlyinsignalspace.Theprobabilityofencounteringsuchaccesspointswillbeevenhigherwhenwedenotealocationssignatureusingthesignalsofmultiplewirelesstechnologiescollectively.Wepresenttheresultsoftwowell-knownlocalizationalgorithms(K-NearestNeighborandBayesianProbabilisticModel)whentheabovefactorsareexploited,usingBluetoothandWi-Fisignals.Wehaveobservedsignificantimprovementintheiraccuracywhenourideasareimplemented.Keywords:LocationFingerprint,SSD,Interpolation,Anchors,Localization,Bluetooth,WiFi,LocationSys-tems.I.INTRODUCTIONRecently,therehavebeenconsiderableinterestsinin-doorlocalizationtechniques.Itisgenerallyagreedthatadesirableindoorlocationsystemshouldbecharacterizedbyhighaccuracy,shorttrainingphase,cost-effectiveness(preferablyusingoff-the-shelfhardware),androbustnessinthefaceofpreviouslyunobservedconditions.Ourworkhereinaimstoachievealocationsystemthataccomplishesalltheserequirements.Infutureubiquitouscomputingenvironment,locationservicesforhandheldsarelikelytobeinhighdemand.However,thesehandheldsareexpectedtocomeinwithmanydifferenthardwaresolutions,evenforthesamewirelesstechnology.Asaresult,alocationsystemthatreliessolelyonabsolutesignalstrengthmeasurementstodefinelocationfingerprintswouldnotperformwell.Re-gardlessofwhetheradevicessignalstrengthsperceivedattheaccesspoints(APs)areusedtodenotethedeviceslocationfingerprint,orthattheAPssignalstrengthsperceivedatthedeviceareused,suchfingerprintsmaydiffersignificantlywiththedeviceshardwareevenunderthesamewirelessconditions.Thiscaneasilybeobservedinexistingpopularwirelesstechnologies,suchasWi-FiorBluetooth.Thepresenceofpowercontrolinsomewirelesstechnologiesfurthercomplicatethematter.Theneedforrobustlocationfingerprintisobligatoryforanylocalizationalgorithmthatutilizesit,nomatterhowsophisticatedthealgorithmis.Inthispaper,wehaveanalyticallyshownthatthedifferenceofsignalstrengthsperceivedatAPsprovideamorerobustlocationfin-gerprint,ratherthanabsolutesignalstrengthvalues.Wealsoverifyourclaimwithdetailedexperimentalfindings.Anearlierwork1onlyprovidedexperimentalresultsexploitingthisideainordertofindaroguemachine,withoutproperanalysisaboutwhysignalstrengthdiffer-enceshouldbecategorizedasstablelocationfingerprint.Fewpriorworks2,3haveattemptedtoshortenthetrainingphaseofalocationsystem.Theycontendthat,ratherthanperforminganexhaustivesurveytocreatealocationfingerprintdatabasethatrequiressubstantialcostandlabor,onecouldsimplycollectalimitednumberofreadings.Haebarlenetal.3achievesthisgoalbydividingthewholeareaintorooms/cells,therebylimitingthelocationestimatestoroom-levelgranularity.Onthecontrary,Lietal.2triestocompletethedatabaseusinginterpolationofreadingstakenatothertrainingpoints.Ourworkhasadoptedthelatterapproach.Weholdtheviewthataninterpolation-basedtrainingapproachmaystandoutwhentheenvironmentorsetupchanges.Normally,insuchscenarios,thelocationservicesmaybesuspended,whilewaitingforthecreationofanappropriatelocationfingerprintdatabasethatmodelsthechange.Thisprocedureisbothtimeandlaborintensive.Onthecontrary,thelocationsystemadministratormaychoosetocontinuelocationserviceprovisioningby1-4244-1455-5/07/$25.00c2007IEEEperformingaroughsurvey(i.e.,takingafewsamples)inthechangedenvironmentorsetup,andfillupthevoidsinthetrainingsetdatabasewiththehelpofinterpolation-basedtechniques.Thedatabasemaythenbeaugmentedincrementallybytakingmoresamplesuntilthelocationsystemachievesareasonableaccuracy.Lietal.2haveonlyusedsomeintuitiveguidelinestogeneratethesefaketrainingpoints.Inthispaper,wehaveusedweightedlinearregressioninordertoobtainabetterfitforthosefictitioustrainingpointsexploitingspatialsimilarity4ofsignalstrengthdistribution.Today,amyriadofdevicesincorporatemultiplewire-lesstechnologies;suchatrendisexpectedtothriveinthenearfutureaswell.Subsequently,theremaybeasubstantiallylargenumberofAPsfromdifferenttechnologiesservingthesedevices.Ifweconsiderallthedifferenttechnologiessignalscollectivelytodenotealocationssignature,manyAPssignalsneedtobeconsideredforanyparticularlocation.Priorworks5haveshownthatincreasingthenumberofAPstodenoteaparticularlocationssignaturedoesnotnecessarilyincreasetheaccuracymonotonically.ItmaybewisetouseasmallernumberofgoodAPstodenotesignature,asitreducesthestoragerequirementsandcomputationaloverhead.Inthispaper,wehavedevisedsomesimplecriteriatodistinguishgoodAPs,whichwetermasan-chors.WeclaimthattheconsiderationoftheseanchorssignalsalonewouldachievesimilaraccuracytoasystemthatusesallAPssignalscollectivelyasasignature.Therestofthepaperisorganizedasfollows.InSectionII,weprovideabriefdescriptionofrelatedworks.SectionIIIsketchesourcontributingideasinthefieldoffingerprint-basedlocationsystems.InSectionIV,wepresentexperimentalfindingssupportingourclaims.Finally,wedepictinSectionVtheconclusionsdrawn,andfuturework.II.RELATEDWORKAlthoughGPSisthemostpopularoutdoorlocalizationsystem,itdoesnotworkwellindoorsbecauseitssignalsarenotdesignedtopenetratemostconstructionmateri-als.Theresearcheffortsforindoorlocalizationsystemscanlargelybedividedintotwomaincategories:Thosethatrelyonspecializedhardware(e.g.,IRorRFtags,ultrasoundreceiver)andrequireextensivedeploymentofinfrastructuresolelyforlocalizationpurpose69.Thosethatarebuiltontopofexistinginfrastructure(e.g.,Wi-FiorBluetoothnetworks)anduseoff-the-shelfwirelessnetworkinghardware1016.Ourresearchfocusesonthesecondcategoryabove,asthesesystemsaregainingpopularityduetotheireaseofintegrationandcost-effectiveness.Inthefollowing,weprovideabriefdiscussionaboutsomeexistingap-proachesunderthiscategory.Interestedreadersmayreferto17,18formorein-depthdiscussions.Thesecondcategoryabovemainlydependsonloca-tionfingerprints;theseschemestrytouniquelyidentifyalocationbasedontheperceivedsignalstrengthsatthatpoint.ThisfamilyoflocalizationtechniquesarosewithRADAR10mainlybecauseoftheunavailabilityofappropriateradiosignalpropagationmodelsindoors.Itopenedthedoorformanydifferenttechniquestobeappliedforthelocalizationproblem.Forexam-ple,Nibble11isoneofthefirstsystemstouseaprobabilisticapproachforlocationestimation.Todate,EkahausPositioningEngineSoftware12claimstobethemostaccuratelocationsystembasedonprobabilisticmodel;theyclaimaone-meteraverageaccuracywithashorttrainingtime.Statisticallearningtheory15andneuralnetworks16havealsobeeninvestigatedforlocalization.Someworks13,14alsotrytoaggregatelocalizationdatafromdifferenttechnologies(e.g.,Wi-FiandBluetooth)inordertoachievefineraccuracy.III.INVESTIGATEDAREASFORFINGERPRINT-BASEDLOCALIZATIONInshort,ourpaperaddressesthefollowingareasofatypicalfingerprint-basedlocationsystemRobustLocationFingerprint:Ratherthanutilizingabsolutesignalstrengthaslocationfingerprint,wearguebothanalyticallyandexperimentallythatdif-ferencesofsignalsperceivedatAPswouldprovideamorestablesignatureforanymobiledeviceirrespectiveofitshardwareused.FictitiousTrainingPoints:Withthehelpofproperinterpolationtechniques,weshowthatonlyafewrealtrainingsamplesshouldbesufficienttoachieveareasonableaccuracyforalocationsystem.Anchors:ByintelligentlyselectinggoodAPs(i.e.,anchors),alocationsystemcanbenefitasdis-cussedpreviously.Wehaveformalizedverysimpleguidelinestodenotetheseanchorsinthispaper.Futuremobiledeviceswillinvariablyincorporatemultiplewirelesstechnologies,thereby,increasingthenumberofAPsservicingthemataparticulararea.Thisideawillbeevenmorerelevanttothattypeofscenario.InSectionIII-A,wediscussourideaofdefiningarobustfingerprintforaparticularlocationirrespectiveofthehardwareusedatthemobiledevice.Then,weelaborateonourideaofusingsimplelinearregressiontechniquestoimprovelocalizationmodelswithveryfewtrainingsamplesinSectionIII-B.Inbothcases,webasedouranalysisupontheshadowingmodel19.WeprovidesomeintuitiveguidelinesinordertochooseanchorsinSectionIII-C.A.DifferenceofSignalsasFingerprintsSupposePr(d)andPr(d0)denotethereceivedpowerofadeviceatanarbitrarydistancedandaclose-inreferencedistanced0fromatransmitter,respectively.Fromthelog-normalshadowingmodel,weget,Pr(d)Pr(d0)dB=10log(dd0)+XdB(1)ThefirstpartofEqn.1definesthepathlosscomponent(isthepathlossexponent)andthesecondpartreflectsthevariationofthereceivedpoweratacertaindistance(XdBN(0,dB).Eqn.1canberewrittenas,Pr(d)|dBm=Pr(d0)|dBm10log(dd0)+XdB(2)Eqn.2denotesthat,thereceivedsignalataparticularlocation(i.e.treatedaslocationfingerprinttraditionally)canbeinterpretedasanexpressionofclose-inrefer-encepower(whichincorporatesvariousdevicespecificparameters,e.g.,antennagains)andthepathlossandshadowingvariation.DependingonthehardwareusedbothattheAPandmobiledevice,theperceivedpoweratareferencedistance,i.e.,Pr(d0)variessodoestheresultinglocationfingerprint.Wearguethat,ratherthanusingabsolutesignalstrengthvaluesaslocationfingerprints,thedifferenceoftwoAPsreceivedsignalsfromamobiledevicecanbeusedtodefineamorerobustsignaturewhichwetermasSignalStrengthDifferenceorSSD.Toexplainanalytically,letusassume,Pr(d1)andPr(d2)denotethereceivedsignalstrength(RSS)attwodifferentAPsfromamobiledevicewhichared1andd2distancesawayfromit,respectively.Weassumethat,alltheAPsareofsametype,i.e.,theirhardware(e.g.antennas)usedaresimilar.Consequently,usingEqn.2,wecanwrite,ForAP1,Pr(d1)|dBm=Pr(d0)|dBm101log(d1d0)+X1dB(3)andforAP2,Pr(d2)|dBm=Pr(d0)|dBm102log(d2d0)+X2dB(4)CombiningEqn.3and4,weobtain,Pr(d1)Pr(d2)dB=101log(d1d0)+102log(d2d0)+X1X2dB(5)Eqn.5denotesSSDsexpressionwhichisfreefromPr(d0),thereby,specifiesamorerobustlocationfinger-printthanabsoluteRSS.B.FictitiousTrainingPointsWeknowthatsignalstrengthvarieslinearlywithlog(distance).Inaccordancewiththistestament,Eqn.1canfurtherberewritteninthefollowingwayPr(d)|dBm=10log(d)+Pr(d0)|dBm+10log(d0)+XdBFictitiousPoint(a)Upper2shadedtrainingpointscontributeheavilyFictitiousPoint(b)Lower2shadedtrainingpointscontributeheavilyFig.1.4trainingpointsinordertoinfer2differentfictitiouspoints.ShadedonesaremoreimportantforthecorrespondingfictitiouspointbecauseofspatialsimilarityofsignalstrengthdistributionTheprecedingequationcanbeinterpretedas,y=ax+bwherey=Pr(d)|dBm,a=10,x=log(d)andweassume,b=Pr(d0)|dBm+10log(d0)+XdB=constant.ThestandarddeviationofRSSatanypointinourtestbedismeasuredtobemaximumofonly8dB.SinceourRSSfingerprintisanaverageofmanysamples,XdBcanbeconsideredasconstant.Additionally,withinasmallareawhichincludesthemoreimportanttrainingpointsinordertospecifyafictitiouspoint,islikelytohavesimilarcharacteristicsforallthepointsconcerned.Wetermfictitioustrainingpointsasthosetrainingpointsinthedatabasethataregeneratedusinginter-polationfromtheactualtrainingpointsamplesets.Inordertodeduceafictitioustrainingpoint,eachAPsRSSoverthewholelocalizationareaisformulatedaccordingtotheabovelinearregressionequationbasedontheirsignaturesatthetrainingpoints.Forexample,ifthereare4APs,4differentregressionequationswillbeformed.Theunknownparameters,i.e.,aandbforeachAPareapproximatedusingweightedleastmeansquaremethod.Ourtargetistominimizesummationtextiwi(yiyi)2whereyiandyirepresenttheactualandpredictedsignaturerespectivelyforaparticularAPatithtrainingpoint.Wehavechosentheweighttobeinverselyproportionaltothedistancebetweenacertainfictitiouspointjandtheactualtrainingpointsi(inourexperiments,simply,1dji).Consequently,werealizethat,foreachfictitiouspoint,theclosertrainingpointscontributemoreheavilyinformulatingtheAPsregressionequationswhichcomplieswiththespatialsimilarityofsignalstrengthdistribution(SeeFig.1(a)and1(b).Themainpurposeoftheweightwiistomakethecontributionofthetrainingpointswhichareclosertofictitiouspointshigher.Notethat,inordertoobtainadifferentfictitiouspoint,theregressionequationsforthe4APswillbechanged.Inotherwords,forinferringeachfictitiouspoint,wewillbegetting4differentregressionequationsforthe4APseverytime.OncewehaveapproximatedthesignalpatternsoverthewholelocalizationareafromtheAPsusingtheregressionmodel,wewouldjustpluginthedistancesoftheparticularfictitiouspointfromthecorrespondingFig.2.OurExperimentalTestbedAPsinordertoobtainitssignature.C.AnchorsYoussefetal.20usedclusteringtechniquesinordertorelievethecomputationaloverheadincomputinglocationestimate.TheypickedlocationsthatseethesamekAPswiththestrongestsignalstrengthvaluestoidentifyaparticularcluster.SincewewanttoselectAPswhichcanbeusedtodifferentiatedistinctlocationsbasedonitssignals,ourmotivationforchoosingthekAPsoranchorsissomewhatdifferent.WetermanAPasanchorifitshowsgreatervariabilityofitssignalsoverthewholelocalizationarea.Wehaveusedtwointuitiveguidelinesinordertochoosetheseanchors:Distinctiveness:Supposethemodeofthesig-nalstrengthsamplescollectedataparticularlo-cationcharacterizethelocationsfingerprint.Letmj1,mj2,.,mjMdenotethemodesofsignalstrengthsamplesofthejthAPovertheMlo-cations.AmongtheMmodes,assumeonlylaredistinct,S=mj1,mj2,.,mjl.Now,distinc-tivenessmetricforjthAPcanbedefinedas,distj=|S|.ThisAPcanbeconsideredasanchorifdistj,whereisasystem-definedparameterdependentonthelocalizationareasizeandthenumberofdifferenttraininglocationgrids.Variability:AnotherparametercanbetakenintoaccountindefininganchorsisthevariabilityofanAPsfingerprintsoverthewholelocalizationarea.Ifmodeischosentodenotelocationfinger-printasstatedinthepreviousguideline,wehave,j=summationtextMi=1mjiMandj=radicalBigsummationtextMi=1(mjij)2M,wherejandjrepresentstheaverageandstandarddeviationofthejthAPsmodesorfingerprintsoverthewholelocalizationarea.Similarly,thisAPcanbecategorizedasanchorifjwhereagainisalocationsystemdependentthreshold.IV.EXPERIMENTALSTUDYInthissection,wefirstdescribeourexperimentaltestbedanddatacollectionprocess.Then,weproceed716968676665646362616000.05SignalStrength(indBm)ProbabilityFig.3.HistogramofsignalstrengthataparticulartrainingpointregardinganAPanditsGaussianapproximationtoprovideourexperimentalresultsandfindings.A.TestbedSetupOurexperimentaltestbedislocatedinsidealecturetheaterofourschoolwhichspansoveranareaof540m2.WehaveusedfourAopenMP945MiniPCstoserveasouraccesspointswhichareplacedneartheceilings.ThelocationsoftheseAPsareshowninFig.2,markedasstarswhilethetrainingpointsareindicatedbydots.EachMP945isinstalledwithAopenWN2302AminiPCIWLANadapterinordertopassivelydetectWi-FidevicesandmeasuretheirRSS.TheyarealsoincorporatedwithBT-2100Class1BluetoothadapterswhichkeeponscanningforBluetoothpacketsbyissuinginquiryperiodically.EachMiniPCorAPisconnectedtoourschoolsintranetforcommunicatingwiththeserverbymeansofawiredLANconnection.AllourminiPCsrunSuSe10.1Linuxdistributionwiththelatestlibpcaplibraries21andBlueZprotocolstack22.B.DataCollectionProcedureInourtestbed,thereare62trainingpointsorgrids.Thetrainingprocessstartsbyplacingthemobiledeviceataparticulartrainingpoint.Sincealocationsystemwhichrequireslittleparticipationfromthemobiledeviceismoredesirable,ourAPscollectRSSinformation.TheWLANdeviceatthemobiledevicesendsproberequestcontinuouslyforsometimeperiodinordertogatherenoughpacketsattheAPslistening,whiletheAPsissueBluetoothinquiryfromtimetotimewhichthemobiledevicerespondsto.Ineithercases,thepacketinformationisimmediatelytransferredtoourcentralserverdatabase.OurBluetoothadaptersprovideabsoluteRSSmetricwhichwehaveusedtodenotealocationsfingerprintregardingBluetoothtechnologysinceothersignalstrengthvalues(e.g.,relativeRSSI,linkquality-80-75-70-65-60-55-50-45-402468101214161820AbsoluteSignalStrength(indBm)20ArbitraryTrainingPositionsBluetoothRSSLaptopPDA(a)AbsoluteSignalStrengthperceivedataBluetoothAP-80-70-60-50-40-302468101214161820AbsoluteSignalStrength(indBm)20ArbitraryTrainingPositionsWi-FiRSSLaptopPDA(b)AbsoluteSignalStrengthperceivedataWi-FiAP-20-15-10-5051015202468101214161820SignalStrengthDifference(indB)20ArbitraryTrainingPositionsBluetoothSSDLaptopPDA(c)SignalStrengthDifferencebetween2BluetoothAPs-20-10010202468101214161820SignalStrengthDifference(indB)20ArbitraryTrainingPositionsWi-FiSSDLaptopPDA(d)SignalStrengthDifferencebetween2Wi-FiAPsFig.4.RSSandSSDconsidering2differentdevices(e.g.,LaptopandPDA)incorporatedwithbothBluetoothandWi-Fietc.)madeavailableinBluetoothCorespecification23havealreadybeenprovenunsatisfactoryforlocalizationpurpose13.Finally,wehavechosen44testingpointswhicharecompletelydifferentfromourtrainingloca-tions.Thecentralserverisresponsibleforcalculatingthelocationestimateduringthetestingphase.C.ExperimentalResultsandFindingsFirst,welisttheassumptionswehavemadecorre-spondingtoourexperimentsperformed:Inourpaper,wheneverwehaveusedRSSaslocationfingerprintforcertainexperiments,weas-sumedittobenormallydistributed.Thoughsomeworksdefythisphenomenon,otherslendsupporttoit4.OurexperimentalresultsalsosuggestittobeareasonableapproximationwehavenotachievedsignificantimprovementconsideringahistogramrepresentationofRSS.Fig.3showsRSSdistributionatoneparticularpointforacertainAPanditsGaussianapproximationcurve.Wehavechosentwowell-knownalgorithmsinlocalizationliterature,namely,KNNandBayesianprobabilisticmodelinordertotestourideas.Thereasonbehindselectingthesetwowell-know