Fault Tolerant Positioning using WLAN Signal Strength Fingerprints

FaultTolerantPositioningusingWLAN

SignalStrengthFingerprints

C.Laoudias,M.P.MichaelidesandC.G.Panayiotou

KIOSResearchCenterforIntelligentSystemsandNetworks

DepartmentofElectricalandComputerEngineering,UniversityofCyprus

Kallipoleos75,P.O.Box20537,1678,Nicosia,Cyprus

Email:laoudias@ucy.ac.cy,michalism@ucy.ac.cy,christosp@ucy.ac.cy

Abstract—Accurateandreliablelocationestimatesusingwire-lessnetworksareimportantforenablingindoorlocationorientedservicesandapplications,suchasin-buildingguidanceandassettracking.Providingadequatelevelofaccuracyincaseoffaultsorattackstothepositioningsystemisequallysignificant,thusourmaininterestisonthefaulttoleranceofpositioningmethods,ratherthantheabsoluteaccuracyinthefault-freecase.Weintroduceseveralfaultmodelstocapturetheeffectoffailuresinthewirelessinfrastructureormaliciousattacksanddiscusshowthesemodelscansimulatethecorruptionofsignalstrengthvaluesduringpositioning.Themodelsareusedtoinvestigatethefaulttoleranceofpositioningmethodsandevaluatethemintermsoftheirperformancedegradationasthepercentageofcorruptedsignalstrengthmeasurementsincreases.Experimentalresultsusingourfaultmodelsarealsopresented.

I.INTRODUCTION

Theuseofwirelessnetworkstoinfertheunknownlocationofindividualsorequipment,especiallyinindoorenviron-ments,hasattractedresearchinterestoverthelastdecade.Thisismainlyduetotheincreasingdemandforlocation-basedservicesandapplications,suchasin-buildingguid-ance,assettrackinginhospitalsorwarehouses,eventdetec-tionandautonomousrobotnavigation.Differentpositioningtechnologieshavebeendiscussedintheliteratureincludinginfrared,Bluetooth,Radio-frequencyidentification(RFID),Ultra-wideband(UWB),ultrasoundandWirelessLocalAreaNetwork(WLAN);see[1],[2]foranoverviewoftechnologiestodeterminelocationandcommercialpositioningsystems.AwiderangeofpositioningmethodsrelyonWLANs,owingtothewideavailabilityofrelevantinfrastructure.TheWLANAccessPoints(AP)maybelongtotheprivatefully-controllednetworkofasingleoperatorthatprovidestheposi-tioningservice.Alternatively,publicWLAN-basedpositioningsystems,suchasSkyhook[3],relyonpubliclyavailableAPsandexploitinformationaboutallAPsthatcanbedetectedintheareaofinterest.UsuallyWLAN-basedmethodsexploitReceivedSignalStrength(RSS)samplesfromAPs,whichcanbeeasilycollectedwithoutspecializedequipment.Inthiscontext,severalapproachesutilizeanumberofRSSfingerprintscollectedaprioriatsomepredefinedreferencelocations.Locationcanthenbeestimatedusingthecurrentlymeasuredfingerprinttofindthebestmatchbetweenthecurrentandreferencefingerprints[4]–[8].

978-1-4244-58-6/10$26.00󰀂

cIEEEThefocusofpositioningmethodssofarhasbeenon

improvingaccuracy.Inrealworld,however,WLANAPscanfailorexhibiterroneousbehaviour,thuscompromisingtheperformanceofthesemethods.Forinstance,someAPsmaybeunavailableduringpositioningduetorandomandunpre-dictedfailures,suchaspoweroutages.Fingerprintpositioningsystemsarealsosusceptibletonon-cryptographicattacksthatrenderasetofAPsuselessorcorrupttheexpectedRSSvaluesbyalteringthepropagationenvironment.Wetreatthesefailuresandattacksinaunifiedframework,becausetheybothinjectfaultsthatmayleadtoperformancedegradationduringpositioning,andinvestigatethefaulttoleranceofpositioningmethods.Faulttoleranceisanimportantissuethathasreceivedlittleattentionintheliterature.Ourmaincontributionistodefinerealisticfaultmodels,studytheperformanceofpositioningalgorithmsinthepresenceoffaultsandmotivatefutureresearchinthisdirection.

Therestofthepaperisstructuredasfollows.SectionIIisasurveyofpreviousworkonfaultorRSSattackmodels,detectionschemesandfaulttolerantpositioningmethods.InSectionIII,weintroduceseveralfaultmodelsthatcapturetheeffectofAPmalfunctionsormaliciousattacksduringpositioning.InSectionIV,westudythewell-knownNearestNeighbormethod.OurmeasurementsetupisdescribedinSectionV,followedbytheexperimentalresultsinSectionVI.Finally,theconclusionsandsomeideasforfutureworkarediscussedinSectionVII.

II.RELATEDWORK

A.FaultandAttackModels

Someearlyworksinvestigatetheperformanceofposi-tioningalgorithmswhenasingleAPisshutdowneitherintentionallyoraccidentally.Authorsin[9]evaluateseveralNNvariantsandweightingschemesinamulti-floorareacoveredby10APstodeterminetheirrobustnesswhentheAP,thatisclosesttothemobiledeviceduringpositioningbecomesunavailable.In[10]theeffectofeliminatingoneoutoffiveAPsinthepositionestimationaccuracyisstudiedusingMonteCarlosimulationsbasedonIEEE802.11channelmodels.BothworksreachtheconclusionthatNNapproaches,especiallyifmorethanoneneighborsareused,arequiterobusttosingleAPfailures.

In[11]anattackissimulatedbyrandomlychoosingtheRSSreadingsofoneortwooutofsixAPsandmultiplyingthemwithaconstant.Authorsin[12]considerasimilarlinearattackmodelwhichissimulatedbyperturbingtheoriginalRSSvaluesoverallAPsbyaconstantattenuationoramplificationconstant.Itwasobservedthatusingarealmaterial,suchasglass,metal,foil,booksetc,causesaconstantpercentagepowerlossindependentofdistance.Thistypeofattacksiseasytolaunchwithlowcostmaterialsandatthesametimetheadversarymaycontroltheeffectoftheattackbyselectingtheappropriatematerial[13].Ontheotherhand,amplificationattackscanbeperformedbydeliberatelyincreasingtheAPtransmitpower.

Themodelemployedin[14]assumesthatRSSmeasure-mentsarecorruptedbyadditiveGaussiannoise.Thisismo-tivatedbythestandardlog-distancesignalpropagationmodel[15]thatprovidesthereceivedsignallevelasafunctionofthetransmittedpower,thedistancetothetransmitterandthepathlossexponent.Underthismodel,anRSSattackiscausedbyalteringthepropagationenvironmentandissimulatedbyaddingGaussiannoisetothecollectedtestdata.B.FaultandAttackDetection

Faulttolerantpositioningsystemscouldbesupportedbyfault(attack)detectionmechanismsthatareefficient,i.e.exhibithighdetectionandlowfalsepositiverates.Forin-stance,adetectioncomponentcouldtriggeranalertforthesecuritypersonneleachtimethereisafault(attack)indication.Furthermore,thepositioningcomponentcouldalsoswitchtoafaulttolerantcounterpartinordertomitigatetheeffectofthefault(attack)andstillprovideadequatelevelofaccuracyuntiltheproblemisresolved.

Attackdetectioninwirelesslocalizationisstudiedin[13],[16]foravarietyofpositioningmethods,includingrange-basedandRSSfingerprinting,anddetectionreliesonstatisticalsignificancetesting.Forexample,inthecaseofNearestNeighborRSSfingerprintpositioning,theminimumdistancebetweenthefingerprintobservedduringpositioningandthefingerprintsinthepre-constructedradiomap,denotedasDs,isusedastheteststatistic.ThedistributionofthetrainingdatacontainedintheradiomapisusedtoselectanappropriatethresholdτandsubsequentlyanattackissignifiedduringpositioningincaseDs>τ.Akeyobservationinthisworkisthattheperformanceoftheproposeddetectionmethodisbetterundersignalamplification,comparedtoattenuationattacks.Forprobabilisticpositioningtechniquesequivalentteststatisticsarestudied,includingthelikelihoodofthelocationwiththehighestvalueorthesumofthelikelihoodsoveralllocations.Bothteststatisticsarefoundtodecreasesignificantlyunderattack.

Authorsin[17]exploitthecommunicationcapabilitiesamongtransmittersinaWSNsetupbasedonMicaZbeaconnodestodecidewhethertherearenodefailuresinthesystem.Inthisapproach,beaconnodesperiodicallymeasuretheirlocalneighborhood,definedasthesetofotherbeaconnodesthattheycanhear.Thisneighborhoodiscomparedtotheoriginal

neighborhood,whichismeasuredshortlyafterthesystemhasbeeninstalled.Iftheintersectionbetweenthecurrentandoriginalneighborhoodsislarge,thesystemisassumedtobefault-free.Ontheotherhand,ifthefractionoffailednodesexceedssomethreshold,thenfailure(orsimilarlyanattack)isdetected.However,thisapproachassumesadequateconnectivitybetweenbeaconnodesthatdoesnotchangesubstantiallyovertime.Moreover,duetothenodecommu-nicationrequirement,thisapproachcannotbedirectlyappliedtopositioningmethodsthatrelyonWLANAPinfrastructure.C.FaultTolerantPositioningMethods

ThefaulttoleranceofpositioningmethodshasbeenmainlyexploredinthecontextofWSNs,wherenodefailurescanbefrequent,andfocusedparticularlyonrange-basedtechniques;see[18]foranoverviewandexperimentalevaluation.Thesearealsoknownasmultilaterationtechniquesinwhichlocationisestimatedinaleastsquaressenseusingasetofdistancesfromatleastthreelandmarkswithknownlocations.Severaltypesofmeasurementscanbeusedtoobtaintherequireddistances,includingTimeofArrival(TOA),TimeDifferenceofArrival(TDOA)andRSS.In[19]asetofstaticandmobilehiddenbasestationsareusedforsecurepositioninginrange-basedsystems.Theresistanceofthisclassoftechniquestodistancespoofingattacks,e.g.byalteringtheRSSlevelthatleadstoerroneousdistancecalculation,isanalyzedin[20]andamechanismforsecurepositioning,coinedverifiablemultilateration,isdescribed.

Inourpreviouswork[21]weinvestigatedfaulttoleranceusinganetworkofwirelesssensorsthatmakebinaryobserva-tions.Suchsimplesensorsareabletoreportthepresenceofaneventorintruder,whenthemeasuredsignalattheirlocationisaboveathreshold(positiveobservations),orotherwiseremainsilent(negativeobservations).WeintroducedtheSubtractonNegativeAddonPositive(SNAP)algorithmthatexploitsthesebinarysensorbeliefsinordertoestimatetheevent/intruderlocationinanefficientandfaulttolerantmanner,evenwhenalargenumberofsensorsreporterroneousobservations.AsafirststeptoimprovingsystemrobustnesstoRSS-basedattacks,authorsin[11]suggestincreasingtheredundancybyusingmoresensorsorAPs.Moreover,theeffectofoutlierAPsisreducedwiththeintroductionofamedian-based,insteadoftheEuclidean,distancemeasurethatisapplicableinbothrange-basedandfingerprint-basedpositioningmethods.Similarly,inthecontextofMoteTrackpositioningsystem[17],theEuclideandistanceintheNNalgorithmisreplacedbyanadaptivefingerprintdistancemeasuretocaterforfaultynodes.Underthepresenceoffaults,theadaptivemeasurepenalizesonlyRSSvaluesfoundinthecurrentlyobservedfingerprintsandnotinareferencefingerprintr,soastominimizetheerrorsintroducedfromfailednodes.Inthefault-freecase,thealgorithmrevertstothestandardmeasure,thuspenalizingRSSvaluesfromallnodesnotfoundincommonbetweenrands.Onadifferentline,Kushkietal.[14]describeasensorselectionmethodology,basedonanonparametricestimateoftheFisherInformation,forincreasingtheresilienceof

fingerprinting-basedpositioningsystemstoRSSattacks.Es-sentially,thismethodselectsonlyanumberofreliableAPsfromthesetofavailableAPstomitigatetheattack.

III.FAULTMODELS

Inthecontextoffingerprint-basedpositioning,weuseasetofpredefinedreferencelocations{L:ℓi=(xi,yi),i=1,...,l}tocollectRSSvaluesfromnAPsdeployedintheareaofinterest(offlinephase).Areferencefingerprintri=[ri1,...,rin]Tassociatedwithlocationℓi,isavectorofRSSsamplesandrijdenotestheRSSvaluerelatedtothej-thAP.Usually,riisaveragedovermultiplefingerprintscollectedatℓitoalleviatetheeffectofnoiseinRSSmeasurementsandoutliervalues.Duringpositioning(onlinephase),wethereferencedatatoobtainalocationestimatefingerprints=[s󰀄exploit

ℓ

,givenanewℓ.

1,...,sn]TmeasuredattheunknownlocationInthiswork,weassumethatthereferenceRSSdatacol-lectedintheofflinephasearenotcorrupted.Thisassumptionisnotrestrictingbecausereferencedatacanbevalidatedusingsecurityandattackpreventionordetectionmechanisms[22]priortodeployingthepositioningsystem.Thus,wefocusonnon-cryptographicRSS-basedattacksandfailuresthatmayoccurduringtheonlinephase.InthefollowingweintroduceseveralfaultmodelstocapturetheeffectofAPmalfunctionsormaliciousattacksduringpositioning.Then,wedescribehowthesenewmodelscanbesimulatedusingtheoriginaltestdatatoallowextensiveevaluationandcomparisonoffingerprintingalgorithms.Eachmodelisfollowedbyashortdiscussiononthefeasibilityoftheunderlyingattackortheoccurrenceprobabilityoftherelevantfailure,inbothprivateandpublicWLAN-basedpositioningsystems.

BeforedescribingthefaultmodelsletusdefinetheRegionofCoverage(RoC)ofanAP,asthesubsetofreferencelocationswherethatparticularAPisdetectedduringthecollectionofreferenceRSSfingerprints.Forinstance,allreferencelocationsinourexperimentalsetup(smallblackdots),thelocationsinsidetheRoC(largerdots)oftheAPnamed2CUandtheAPlocation(blacktriangle)aredepictedinFig.1,whilethegrayscalecolorbarindicatesthemeanRSSlevelfromthespecificAPateachlocation;seeSectionVformoredetailsonthesetup.A.APFailureModel

First,weconsiderthecasewhereseveralAPsusedintheofflinephasearenotavailableduringpositioning.ThiscanbecausedbyrandomAPfailures,suchaspoweroutages,WLANsystemmaintenance,APfirmwareupgradesetc.RegardingpublicpositioningsystemsanAPlistedinthedatabasemaybetemporarilyshutdownorpermanentlyremovedbyitsowner.ThelattercaseconstitutesanAPfailureduringpositioningfromtheuserperspectiveuntilthedatabaseisupdated.Whenanattackisassumed,anadversarycaneasilycutoffthepowersupplyofsomeAPsorusespecializedequipmenttoseverelyjamthecommunicationchanneltomaketheattackedAPsunavailable.Jammingattackscanbeeasilylaunched,as

reportedin[23].WesimulatethismodelbyremovingtheRSSvaluesofthefaultyAPsintheoriginaltestfingerprints.B.FalseNegativeModel

Inthismodel,theassumptionisthatanAPmaynolongerbedetectedinsomelocationsinsideitsoriginalRoC.Thiscanhappenaccidentallyiffurnitureorequipmentismoved,sothatthepropagationpathisblockedandtheAPsignalcannotbedetectedinlocationswhereitwaspreviouslyweak.PublicWLANpositioningsystemsthatcoverlargerurbanareasoutdoors,canalsobeaffectedbythistypeoffaults,e.g.constructionofabuildinginthevicinityofthatAP.WesimulatethismodelbyignoringvalidRSSreadingsforasetofAPsinanumberoftestfingerprints.C.FalsePositiveModel

AnotherscenarioiswhenanAPisdetectedduringposi-tioninginlocationsoutsideitsoriginalRoC.ContrarytotheFalseNegativemodel,thiscanhappenunintentionallyincaseaheavyobjectorequipment,whichwaspreviouslyobstructingthepropagationpath,wasmovedaftercollectingthereferencedata.Essentially,thetransmissionsignalscantravelfurtherandmakethatAPhearableinlocationsoutsideitsoriginalRoC.AnattackscenariothatmanifestsinasimilarmanneriswhenarogueAPisdeployedandprogrammedtoreplicateanexistingAP.Inthisfashion,thecorruptedAPisthereafterdetectedduringpositioninginlocationspossiblyfarbeyonditsoriginalRoC.TheFalsePositivemodelissimulatedbyinjectingrandomRSSvaluestothetestdataforasetofAPsthatwouldotherwisebeundetectedinthoselocationsthattherespectivetestfingerprintswerecollected.D.APRelocationModel

OurlastmodelcapturestheeffectofrelocatingasetofAPsandthusafaultyAPisdetectedduringpositioninginsideanareathatcanbedifferentthantheexpectedone.ThismayhappenincasethattheAPismovedtoanewlocation,e.g.fornetworkoperationreasons,andthereferencedataarenotupdatedbycollectingadditionalfingerprintstocaterfortheaffectedareas.Inpublicpositioningsystems,thatexpandoverseveralofficebuildingsandWLAN-equippedprivateproperties,thismayhappenquiteoften.Ontheother

Average RSS of 2CU −3040−4035−5030−60]m25[ −70Y2015−8010−905−100 20406080100−110X [m]Fig.1.ExampleRoCofanAPinourexperimentalsetup.

hand,anadversarymaylaunchanattackwiththesameeffectbyphysicallyrelocatinganAP.Alternatively,theattackercanimpersonateaspecificAP(Sybilattack),whileatthesametimeeliminatetheAPsignalsthroughjamming.WesimulatetheAPRelocationmodelbyreplacingtheRSSreadingsofthecorruptedAPinthetestdatawiththevaluesofanotherrandomlyselectedAP.

APimpersonationcanbeeasilyimplemented,especiallyinpublicpositioningsystems,becauserogueAPscanforgetheMACaddressesoflegitimateAPsandtransmitatarbitrarypowerlevelswithintheirphysicalcapabilities.Detailsonthefeasibilityofimpersonationandreplicationattackscanbefoundin[24],wheretheapplicationoftheseattacksontheSkyhook[3]publicWLANpositioningsystemisreported.

IV.NEARESTNEIGHBORMETHOD

NearestNeighbor(NN)methodestimateslocationbymin-imizingadistancemetricDi,suchasthesquaredEuclideandistance,betweentheobservedfingerprintduringpositioningsandthereferencefingerprintsri

󰀄ℓ

(s)=argminℓDi,Di=󰀃nrij−sj.(1)

i

󰀁󰀂2

j=1

Essentially,allreferencelocationsareorderedaccordingtoDi

andthelocationℓiwiththeshortestdistancebetweenriandsinthen-dimensionalRSSspaceisreturnedasthelocationestimate.TheKNearestNeighbors(KNN)methodestimateslocationasthemeanofKreferencelocationswiththeshortestdistancesandhasbeenreportedtoprovidehigherlevelofaccuracycomparedtoNN[4].

Inpracticalimplementations,WLANAPsprovideonlypartialcoverageintheareaofinterestanditisnotexpectedthatthesetsofAPsinfingerprintsriandswillbeidentical.Thus,handlingmissingRSSvaluesinonefingerprintortheotherisapracticalproblem.Assumingfault-freepositioning,aspecificAPfoundinafingerprintriandnotinscanbeduetothefactthatsisrecordedinalocationℓthatisfarfromℓi.Evenifℓandℓiarespatiallycorrelated,smaynotcontainaRSSreadingfromthatAPbecauseofatransienteffectintheWLANadapterofthemobiledevice.Alternatively,iffaultsarealsoconsidered,thenthemissingAPcanbetheresultofarandomfailureoramaliciousattackduringpositioning.OurobjectiveistostudytheperformanceofNNmethodundervariousfaultmodelsinordertogetaninsightofitsinherentfaulttolerance.Tothisend,wedefineRiandSasthesetsofAPsthatarepresentinfingerprintsriands,respectively.Usingthesedefinitions,Diin(1)canbeviewedasadistancemetricthatcomprisestheerrorcontributionsofthreecomponents

Di=󰀃dij+󰀃dij+󰀃

dij(2)

j∈Ri∩S

j∈Ri\\S

j∈S\\Ri

wheredij=󰀁rij−sj󰀂2

.ThefirsttermreferstotheintersectionofRiandSandrepresentsthedistancewithrespecttothoseAPsthatarecommoninfingerprintsriands.Thesecondterm

employsthoseAPsthataredetectedinriandnotins,whilethelasttermincreasesthedistanceDifurtherbyconsideringthoseAPsthatarefoundinsandnotinri.

WhenonlyfewAPsarecommoninriands,i.e.|Ri∩S|issmallcomparedto|Ri\\S|or|S\\Ri|,thenthisisastrongindicationthatthesefingerprintsarecollectedindistantloca-tions.Thus,thesecondandthirdtermsin(2)shouldbetakenintoaccounttoincreaseDiandreflectthestrongdissimilaritybetweenfingerprintsriands.Thiscanbehandledbyusingasmallconstant,e.g.belowthesensitivityleveloftheWLANadapter,toreplacethemissingRSSvaluessjandrijinthesecondandthirdtermof(2),respectively.

Thedistancemetricin(2)iseffectiveinthefault-freecasebecauseitpenalizesallAPsthatarenotfoundincommonbetweenriands.However,whenAPfaultsorRSSattacksareconsidered,thenthismetricmaynotbeabletoguaranteetherequiredfaulttolerance.Theeffectoffaultscanbealleviatedbyusingamedian-baseddistancemetric[11],insteadoftheEuclideanmetricin(1).Inthiscase,giventheobservedfingerprintsandthereferencefingerprintsri,locationisestimatedby

󰀄ℓ(s)=argminDi,Di=medn󰀁rij−sj󰀂

2ℓ.(3)i

j=1

V.MEASUREMENTSETUP

Wecollectedourreferencedatainatypicalmodernoffice

environmentonthesecondfloorofathreestoreybuildingatVTTTechnicalResearchCentreofFinland.Thefloorconsistsofeightwingscontainingofficesandmeetingroomsconnectedwithcorridors.Thereare31CiscoAironetAPsinstalledthroughoutthebuildingthatusetheIEEE802.11b/gstandard.WeusedaFujitsu-SiemensPocketLooxsmartphonewithWindowsMobileoperatingsystemtocollectRSSmeasure-mentsfromallAPsat107distinctreferencelocationsonthesecondfloor.Theselocationsareseparatedby2-3metersandformagridthatcoversallpublicplacesandmeetingrooms.Atotalof3210referencefingerprints,correspondingto30fingerprintsperreferencelocation,werecollectedattherateof1sample/sec.Duetotheopenplaninteriordesign,theAPscanbepartiallydetectedonthesecondfloor,andtheaveragenumberis9.7APsperreferencelocation.ThefloorplanoftheexperimentationareaandthereferencelocationsaredepictedinFig.2,whilethegrayscalecolorbarindicatesthenumberofAPsdetectedateachlocation.RSSvaluesrangefrom−101dBmto−34dBmandweusedthevalue−101dBmtohandlethemissingRSSvaluesinthefingerprints.Fortestingpurposes,wecollectedadditionalfingerprintsonthesecondfloorbywalkingataconstantspeedoverapaththatconsistsof192locations.Onefingerprintisrecordedateachlocation,andthesamepathissampled3timesforatotalof576testfingerprints.

VI.EXPERIMENTALRESULTS

WeusethecollectedRSSdatatoevaluatethefaulttoleranceofpositioningmethodsandfocusparticularlyontheNNmethod.Inoursetup,wefoundthatusingK=3neighbors

22402035183016]14m25[ 12Y2010158106 204060801002X [m]

Fig.2.ReferencelocationsandnumberofdetectedAPs.

providesbetterperformanceinthefault-freecaseandthisvalueisusedthroughouttheexperiments.Forcomparison,weconsiderthemedian-basedKNNapproachof[11],usingK=3neighbors,denotedasmedKNNhereafter.Moreover,weuseaversionofSNAPalgorithm[21]adaptedtotheWLANsetupbyutilizinginformationofwhetheranAPisdetectedduringpositioningornot.Wealsoevaluatetheprob-abilisticMinimumMeanSquareError(MMSE)positioningalgorithm,whichisbasedontheKernelmethoddescribedin[6].

Theperformanceofthepositioningmethodsisquantifiedusingthemeanpositioningerror(Me)overalltestfingerprints,i.e.themeandistancebetweentheactualandestimatedloca-tionspertainingtothetestdata.Weinvestigatefaulttolerancewithrespecttotheperformancedegradation,asthepercentageoffaulty(orattacked)APsisincreased.Essentially,amethodthatexhibitssmootherperformancedegradationismorefaulttolerant.Fromanotherperspective,wemayselectadesirableupperboundontheperformance,e.g.Me=5m,andexaminewhatisthepercentageofcorruptedAPsthateachpositioningmethodcantolerate.WeapplythefaultmodelsdetailedinSectionIIItocorrupttheoriginaltestdataandtheresultsforMeareaveragedover20runsusingrandomlyselectedsubsetsoffaultyAPsineachrun.ForcompletenesswealsoconsidertheRSSattackmodelsdiscussedinearlierworks[12],[14]andstudytheresilienceofthepositioningmethods.

Inthefault-freecase,MMSEmethodprovidesthebestaccuracy(Me=2.46m),followedbyKNNforwhichMeis2.70m.FormedKNN,Meis3.30mwhichindicatesthatthemedian-basedmetricisnotagoodoptionwhennofaultsarepresent.SNAPmethodhastheworstperformance(Me=5.61m),howeverthisisexpectedbecauseSNAPonlyconsiderswhetheranAPisdetectedornotintheobservedfingerprintanddoesnotutilizeitsRSSlevel.A.PerformanceundertheAPFailuremodel

InFig.3a,MeisplottedasafunctionofthepercentageofAPsthathavefailed.Inthisscenario,medKNNprovidesthebestperformanceintermsoffaulttolerance,whileKNNisonlyslightlyworse.If50%oftheavailableAPsarecompromised,thenMeis7.39mand8.42mformedKNNand

KNN,respectively.ThesearefollowedbyMMSEandSNAPmethodsforwhichMeis9.61mand12.80m,respectively.SNAPprovestobeverysensitivetothistypeoffaultsandMeincreasesrapidly.Ontheotherhand,medKNNcantolerateupto30%failedAPs,assumingMe=5m,followedbyKNNandMMSEthatcantolerateupto20%failedAPs.Noticethatevenwhen100%oftheAPshavefailed,i.e.noAPisdetectedinanyoftheobservedfingerprints,eachpositioningmethodcanstillprovidealocationestimatebecauseweusethevalue−101dBmtohandlethemissingRSSvalues.Inthiscaseofcoursetheestimateprovidedbyeachmethodcannotchangetoreflecttheactualtraveledpath.

B.PerformanceundertheFalseNegativemodel

ThisfaultmodelcanbeviewedasamoderatecaseoftheAPFailuremodel,inthesensethatfaultyAPsmaynotbedetectedinsomelocationsinsidetheiroriginalRoCsduringpositioning,butarenottotallyunavailable.WesimulatethisscenariobyignoringvalidRSSvaluesforasubsetoftheAPsin70%ofthetestlocations(randomlyselected),wheretheAPswerepreviouslydetected.TheperformanceofpositioningmethodsforincreasingnumberoffaultyAPsisillustratedinFig.3b.Incase50%oftheAPsarecorrupted,thenMeis5.14m,6.04mand6.40mforthemedKNN,KNNandMMSEmethods,respectively.ForSNAPmethodresultsindicatethatMe=9.74m.Moreover,iftheupperboundontheperformanceis5m,thenmedKNNexhibitshigherfaulttoleranceasitcantolerateupto45%faultyAPs,comparedto35%fortheKNNandMMSEmethods.C.PerformanceundertheFalsePositivemodel

Thisfaultmodelhasexactlytheoppositeeffect,i.e.anAPisdetectedduringpositioninginlocationsoutsideitsoriginalRoC.WesimulatethisscenariobyinjectingrealisticrandomRSSvaluestoasubsetoftheAPsin70%ofthetestlocations(randomlyselected),wherethoseAPswouldotherwisebeundetected.KNNandMMSEmethodsexhibitsimilarbehaviourandtheirperformancedegradesrapidlyasthepercentageoffaultyAPsincreases;seeFig.3c.Forinstance,when50%oftheAPsareaffectedthenMeisaround15.50mforbothKNNandMMSE.Inthiscase,medKNNprovidesthebestperformance(Me=5.51m),followedbytheSNAPmethod(Me=7.93m).ThemedKNNmethodcantolerate45%faultyAPs,comparedtoonly15%forKNNandMMSE,whilekeepingthemeanerrorbelow5m.

AninterestingobservationisthatmedKNNprovidessimilarperformanceandhasthesameleveloffaulttoleranceforboththeFalsePositiveandFalseNegativemodels.Incontrast,iftheFalsePositivemodelisassumed,KNNandMMSEmethodsprovetobesignificantlylessfaulttolerantcomparedtotheFalseNegativemodel.

D.PerformanceundertheAPrelocationmodel

FaultsinjectedaccordingtotheAPrelocationmodelseemtocausesimilarperformancedegradationtoallpositioningmethods.Experimentalresultsunderthisfaultmodelare

illustratedinFig.3d.Allmethodsperformequallywellwhenlessthan30%oftheAPsarecompromised.However,ifthepercentageoffaultyAPsexceeds40%,thenthemedKNNmethodprovidesslightlybetterperformance.Specifically,ifhalfoftheAPsarecorrupted,thenMeis9.20m,11.46m,11.70mand10.70mformedKNN,KNN,MMSEandSNAPmethods,respectively.ResultsindicatethatmedKNN,KNNandMMSEcantoleratearound25%corruptedAPswithoutviolatingthe5mupperboundontheperformance.

E.PerformanceundertheLinearAttackmodel

TheLinearAttackmodel[12]capturestheeffectofper-turbingtheRSSvaluesduringpositioningbyaconstantfactor.Interestingly,wefoundthatKNNprovestobethemostfaulttolerantmethod,followedbyMMSE,forbothattenuationandamplificationattacks.IfthetestRSSvaluesareattenuatedby20dBmfor50%oftheAPs,thenMe=5.15mandMe=5.55mforKNNandMMSE,comparedtoMe=7.03mformedKNN,asshowninFig.4a.Moreover,KNNandMMSEcantolerateupto45%corruptedAPs,comparedto30%formedKNN,incaseMe=5misacceptable.TheperformanceofSNAPdegradessmoothlyandwhenthepercentageofcorruptAPsincreasesbeyond60%,SNAPprovestobemorefaulttolerantcomparedtomedKNN.

IfRSSvaluesareamplifiedby20dBm,thenMeremainsbelow5mforbothKNNandMMSEmethodsevenwhenallAPsarecorrupted;seeFig.4b.SNAPalsoretainsahighlevelofperformance.Ontheotherhand,medKNNmethodperformspoorlyandMeincreasessharply,especiallyasthepercentageofcorruptedAPsincreasesbeyond50%,forbothattenuationandamplificationattacks.Forinstance,undertheattenuationattackmodel,Meincreasesatarateof7.5%whenlessthanhalfoftheAPsarecorrupted,whiletherateisapproximately20%whenthepercentageofcorruptedAPsexceeds50%.F.PerformanceundertheAdditiveGaussianNoisemodelInourexperiments,thismodelissimulatedbyaddingGaussiannoisewithvarianceσntotheoriginaltestRSSdata.Whenσn=10dBm,thereisonlymarginalperformancedegradationforKNN,andMMSEmethods.ForthesemethodsresultsindicatethatMeisincreasedaround1mwhenallAPsarecorruptedcomparedtothefault-freecase,contrarytomedKNNforwhichMeisdoubled;seeFig.4c.Forhighernoisevariance(σn=20dBm),performancedegradesfasterforKNNandMMSE,howeverMeremainsbelow6mevenwhenallAPsarecorrupted.FormedKNNmethod,MeincreasesrapidlywhenmorethanhalfoftheAPsarecorrupted,asshowninFig.4d.Forinstance,when80%oftheAPsarecorruptedMe=7.94mformedKNN,comparedtoMe=5.27mandMe=5.42mforKNNandMMSE,respectively.WhenthepercentageoffaultyAPsincreasesbeyond70%,thenmedKNNisoutperformedbySNAPmethodaswell.

G.Discussion

Ourexperimentalresultsindicatethatthereisnotasinglepositioningmethodthatprovidesoverallahighleveloffault

tolerance.ItseemsthatvarioustypesoffaultsorRSSattackstrategiesrequiredifferentapproachestomaintainanadequatelevelofpositioningperformance.TheSNAPmethodexhibitssmoothperformancedegradationunderalmostallfault/attackmodels,howeveritisnotagoodcandidatesolutionwhenfewAPsarecorrupted,becausethepositioningerrorisratherhighinthefault-freecase.TheprobabilisticMMSEmethodexhibitsslightlyworseperformancecomparedtoKNNmethodanddoesnotprovidehigherfaulttoleranceinanyscenario.

ThemedKNNmethodisfaulttolerantinsomecasesandprovidesthebestperformanceundertheFalseNegative,FalsePositiveandAPRelocationfaultmodels.However,itsper-formancedegradessignificantlyincasemorethanhalfoftheAPsarecorrupted,especiallyundertheRSSattackmodels,duetothemedian-baseddistancemetric.Ontheotherhand,thestandardKNNmethodisveryrobusttoRSSattacks;seeFig.4.Moreover,KNNoutperformsmedKNNinthefault-freecase.However,KNNdoesnotperformequallywellwhenthefaultmodelsintroducedinSectionIIIareconsidered.ThisimpliesthatwecouldbuildanadaptiveKNNmethodthatselectseithertheEuclideanorthemediandistancemetric.Inthiscase,adetectionmechanismisrequiredinordertodecidethetypeoffault(attack)andthentriggerKNNalgorithmtoswitchtotheappropriatemetric.Thisispartofourongoingresearchonfaulttolerantpositioning.

AnotherdirectionistomodifytheEuclideanmetricoftheKNNmethodinordertoimproveitsfaulttolerance.Thedistancemetricin(2)iseffectiveinthefault-freecase,howeverwhenAPfaultsorRSSattacksareconsidered,thenthismetricmaynotbeabletoprovideanadequatelevelofpositioningaccuracy.Forinstance,whenAPfailuresoccurduringpositioning,thenasubsetoftheAPsthatwouldotherwisebepresentintheobservedfingerprints,arenolongerdetected.Inthiscase,|Ri\\S|becomeslargeranderrorsindistancesDiareincreasedduetothesecondtermin(2).Thisleadstothewrongorderingofcandidatelocationsandintroduceshigherrorsintheestimatedlocation.Thus,thistermcouldberemovedfromthedistancemetricin(2)toignorefaultyAPsinRi\\S.

VII.CONCLUSION

Ourfocusisonthefaulttoleranceofpositioningmethods,ratherthantheabsoluteaccuracyinthefault-freecase.APmalfunctionsormaliciousattacksleadtofaultsthatmanifestthemselvesinasimilarfashionbycorruptingRSSvaluesdur-ingpositioning.Tothisend,weintroducedseveralmodelsfortheevaluationofRSSfingerprintingmethodsunderthepres-enceoffaultsorattacks.WeinvestigatedthefaulttoleranceofcertainpositioningmethodsandpresentedexperimentalresultsusingrealRSSmeasurements.

OurfutureworkincludesthemodificationofthedistancemetricinthestandardKNNmethodinordertobuildKNNvariantsthatwillbetoleranttospecificfaults.Wealsoplantostudyanddeveloprobustdetectionschemestodecidethetypeoffault(attack)andselecttheappropriatedistancemetric.OurobjectiveistobuildanadaptiveKNNmethodthatwill

45 40Mean Positioning Error (m) 35 30 25 20 15 10 5 0 0

10

20

30

40 50 60Corrupt APs (%)

70

80

90

100

medKNN

KNNMMSESNAP

24 22Mean Positioning Error (m) 20 18 16 14 12 10 8 6 4 2 0 0

10

20

30

40 50 60Corrupt APs (%)

70

80

90

100

medKNN

KNNMMSESNAP

(a)APFailuremodel.

35 30Mean Positioning Error (m) 25 20 15 10 5 0

medKNN

KNNMMSESNAP

35 30Mean Positioning Error (m) 25 20 15 10 5 0

medKNN

KNNMMSESNAP

(b)FalseNegativemodel.

0 10 20 30 40 50 60 70 80 90 100 0 10 20 30 40 50 60 70 80 90 100

Corrupt APs (%)Corrupt APs (%)

(c)FalsePositivemodel.

Fig.3.

(d)APRelocationmodel.

Performanceevaluationundervariousfault/attackmodels.

18 16Mean Positioning Error (m)Mean Positioning Error (m) 14 12 10 8 6 4 2 0 0

10

20

30

40

50

60

70

80

90

100

medKNN

KNNMMSESNAP

22 20 18 16 14 12 10 8 6 4 2 0 0

10

20

30

40

50

60

70

80

90

100

medKNN

KNNMMSESNAP

Corrupt APs (%)Corrupt APs (%)

(a)LinearAttackmodelwithconstantattenuation(−20dBm).

11 10Mean Positioning Error (m) 9 8 7 6 5 4 3 2 1 0 0

10

20

30

40 50 60Corrupt APs (%)

70

80

90

100

medKNNKNNMMSESNAP

(b)LinearAttackmodelwithconstantamplification(+20dBm).

11 10Mean Positioning Error (m) 9 8 7 6 5 4 3 2 1 0 0

10

20

30

40 50 60Corrupt APs (%)

70

80

90

100

medKNNKNNMMSESNAP

(c)AdditiveGaussianNoisemodel(σn=10dBm).Fig.4.

(d)AdditiveGaussianNoisemodel(σn=20dBm).

PerformanceevaluationunderRSSattackmodels:(a)and(b)constantnoise,(c)and(d)additiveGaussiannoise.

befaulttolerantandperformadequatelyunderdifferenttypesoffaultsorRSSattacks.

ACKNOWLEDGMENT

ThisworkissupportedbytheCyprusResearchPromotionFoundation.AuthorswouldliketothankP.KemppiandY.LiatVTTTechnicalResearchCentreofFinland(www.vtt.fi)fortheprovisionofexperimentalWLANRSSdata.

REFERENCES

[1]K.Pahlavan,X.Li,andJ.Makela,“Indoorgeolocationscienceand

technology,”IEEECommunicationsMagazine,vol.40,no.2,pp.112–118,2002.

[2]Y.Gu,A.Lo,andI.Niemegeers,“Asurveyofindoorpositioning

systemsforwirelesspersonalnetworks,”IEEECommunicationsSurveys&Tutorials,vol.11,no.1,pp.13–32,2009.[3]Skyhook,Inc.http://www.skyhookwireless.com.

[4]P.BahlandV.Padmanabhan,“RADAR:anin-buildingRF-baseduser

locationandtrackingsystem,”inProceedingsIEEEINFOCOM,vol.2,2000,pp.775–784.

[5]M.YoussefandA.Agrawala,“TheHorusWLANlocationdetermination

system,”in3rdACMInternationalConferenceonMobilesystems,applications,andservices,2005,pp.205–218.

[6]T.Roos,P.Myllymaki,H.Tirri,P.Misikangas,andJ.Sievanen,“A

probabilisticapproachtoWLANuserlocationestimation,”InternationalJournalofWirelessInformationNetworks,vol.9,no.3,pp.155–1,Jul.2002.

[7]M.BrunatoandR.Battiti,“Statisticallearningtheoryforlocation

fingerprintinginwirelessLANs,”ComputerNetworks,vol.47,no.6,pp.825–845,Apr.2005.

[8]C.Laoudias,P.Kemppi,andC.G.Panayiotou,“Localizationusingra-dialbasisfunctionnetworksandsignalstrengthfingerprintsinWLAN,”inIEEEGlobalTelecommunicationsConference(GLOBECOM),2009,pp.1–6.

[9]P.Prasithsangaree,P.Krishnamurthy,andP.Chrysanthis,“Onindoor

positionlocationwithwirelessLANs,”inIEEEInternationalSymposiumonPersonal,IndoorandMobileRadioCommunications(PIMRC),vol.2,2002,pp.720–724.

[10]A.HatamiandK.Pahlavan,“Acomparativeperformanceevaluation

ofRSS-basedpositioningalgorithmsusedinwlannetworks,”inIEEEWirelessCommunicationsandNetworkingConference(WCNC),vol.4,2005,pp.2331–2337.

[11]Z.Li,W.Trappe,Y.Zhang,andB.Nath,“Robuststatisticalmethods

forsecuringwirelesslocalizationinsensornetworks,”inInternationalSymposiumonInformationProcessinginSensorNetworks(IPSN),2005,pp.91–98.

[12]Y.Chen,K.Kleisouris,X.Li,andR.P.Martin,“Therobustnessof

localizationalgorithmstosignalstrengthattacks:acomparativestudy,”inInternationalConferenceonDistributedComputinginSensorSystems(DCOSS),2006,pp.6–563.

[13]Y.Chen,W.Trappe,andR.Martin,“Attackdetectioninwireless

localization,”in26thIEEEInternationalConferenceonComputerCommunicationsINFOCOM,2007,pp.19–1972.

[14]A.Kushki,K.Plataniotis,andA.Venetsanopoulos,“Sensorselection

formitigationofRSS-basedattacksinwirelesslocalareanetworkpositioning,”inIEEEInternationalConferenceonAcoustics,SpeechandSignalProcessing(ICASSP),2008,pp.2065–2068.

[15]T.Rappaport,Wirelesscommunications.PrenticeHallPTRNewJersey,

2002.

[16]Y.Chen,W.Xu,W.Trappe,andY.Zhang,“Attackdetectioninwireless

localization,”SecuringEmergingWirelessSystems,pp.1–22,2009.[17]K.LorinczandM.Welsh,“MoteTrack:arobust,decentralizedapproach

toRF-basedlocationtracking,”PersonalandUbiquitousComputing,vol.11,no.6,pp.4–503,Aug.2007.

[18]D.Liu,P.Ning,A.Liu,C.Wang,andW.K.Du,“Attack-resistant

locationestimationinwirelesssensornetworks,”ACMTransactionsonInformationandSystemSecurity(TISSEC),vol.11,no.4,pp.1–39,2008.

[19]S.Capkun,K.Rasmussen,M.Cagalj,andM.Srivastava,“Secure

locationverificationwithhiddenandmobilebasestations,”IEEETransactionsonMobileComputing,vol.7,no.4,pp.470–483,2008.

[20]S.CapkunandJ.-P.Hubaux,“Securepositioninginwirelessnetworks,”

IEEEJournalonSelectedAreasinCommunications,vol.24,no.2,pp.221–232,2006.

[21]M.MichaelidesandC.Panayiotou,“SNAP:Faulttoleranteventlocation

estimationinsensornetworksusingbinarydata,”IEEETransactionsonComputers,vol.58,no.9,pp.1185–1197,2009.[22]L.Butty´anandJ.Hubaux,Securityandcooperationinwirelessnet-works.CambridgeUniversityPress,2007.

[23]W.Xu,W.Trappe,Y.Zhang,andT.Wood,“Thefeasibilityoflaunching

anddetectingjammingattacksinwirelessnetworks,”in6thACMInternationalSymposiumonMobileadhocnetworkingandcomputing,2005,pp.46–57.

[24]N.O.Tippenhauer,K.B.Rasmussen,C.P¨opper,andS.Capkun,

ˇ“AttacksonpublicWLAN-basedpositioningsystems,”in7thACMInternationalConferenceonMobilesystems,applications,andservices(MobiSys),2009,pp.29–40.