Inspect a General Framework for On-Line Detection and Diagnosis of Sensor Faults

Abstract—We propose an on-line fault detection and diagnosis framework in sensor networks, called Inspect, which is based on a hybrid tiered approach to integrity checking. Inspect tiered design combines the benefits of distributed and centralized approac

Inspect:aGeneralFrameworkforOn-LineDetectionandDiagnosisofSensorFaults

DanielaTulone

UniversityofCalifornia,LosAngeles

tulone@ee.ucla.edu

Abstract—Weproposeanon-linefaultdetectionanddiagnosisframeworkinsensornetworks,calledInspect,whichisbasedonahybridtieredapproachtointegritychecking.Inspecttiereddesigncombinesthebene tsofdistributedandcentralizedapproaches,thusimprovingtheresponsivenessandef ciencyofthefaultdetection.Moreprecisely,Inspectconsistsofalocaltierbuiltateachsensornodeandcapableofdetectinganomalies,andacentralizedtierbuiltatthesinkandcapableofdistinguishingbetweensensorfaultsandunexpectedtemporal-spatialvariationsinthephenomenon,anddetectingmorecomplextypesoffaults.Inspectsoffersseveraldesirablefeatures:on-linedetection,ap-plicationindependence,andincreasedrobustnesstotemporal-spatialvariations.Moreover,Inspectprovidescon denceboundsthatcanbedynamicallytunedaccordingtotheuserrequirementsforabetterresourcemanagement,andaddressestheproblemofdetectingmorecomplextypesoffaults.

I.INTRODUCTION

Embeddednetworkedsensorsarepowerfulnewtypeofinstrumentwiththepotentialofadvancingknowledgebymonitoringthephysicalworldatunprecedentedscalesandresolutions.However,foraninstrumenttobeuseful,theinformationitprovidesmustbeofhighintegrity.Inthecaseofsensornetworks,theintegrityofreturnedinformationmaybecompromisedduetofaults,failures,andimperfectionsinthesensors,asshowninsomesensordeployments[21],[17],[16].Whilepriorresearchhasledtotremendousprogressinthetasksofef cientlyacquiring,querying,processing,andcommunicatingsensordata(e.g.,DirectedDiffusion[8],TinyDb[13]),farlessattentionhasbeenpaidtotheintegrityissues.Theoverallintegrityproblemhasseveralaspects:(i)techniquesfordetectinganddiagnosingsensorfaults,failures,andimperfectionssoastotakeremedialactionssuchareplac-ingorrepairingasensor,(ii)proceduresforrepairingsensormeasurementsbyreversingtheeffectofsensorimperfectionssuchasmis-calibration,and(iii)algorithmsforfusingandaggregatingsensormeasurementsthatareinherentlyrobusttocorruptedandmissingsensormeasurements.

Thefocusofthispaperisonon-linesensorfaultdetectionanddiagnosisproblemwithoutusingextrinsicreferencesen-sorsandknownstimulitovalidatesensorfunctionality.On-linefaultdetectionanddiagnosisareusuallybasedondataqualityanalysisofsensormeasurementsmadebythenetworkusingstatisticalmodelsofsensordataandphysicalphenomenon,andonredundanciesinsensormeasurementsinspace,time,andsensingmodality.Previouson-linedetectionmechanisms,suchas[9],useacentralizedapproach:thesinkdetectsfaultsbased

ManiSrivastava

UniversityofCalifornia,LosAngeles

mbs@ee.ucla.edu

onstatisticalmodelbuiltatthesinkbasedonthecollectedsensordata.Theintegritycheckingatthebackendiscertainlyareasonableapproachforapplicationscenarioswhereallthesensordataneedstobeextractedanyways.Suchisthecaseformanyscienceapplicationswherethegoalistodevelopamodel,aswellasindeploymentstagesofotherapplicationswhenthesystemis ne-tunedtoitsoperationalenvironment.However,inmanyotherapplicationscenariosthismaynotbethecase.Forexample,thesystemmayonlyneedtoreporttheoccurrenceofsomeeventorthepresenceofsomefeaturetotheenduser.Insuchsystemsundernormalconditionstherewouldbenoneedtoextractallthesensorinformationtotheback-end.Havingtoextractallthesensorsamplestotheback-endwillimposeneedlessenergyoverheadsandalsocausecommunicationscalabilityproblems.Insomesystemswhiledataisindeedextractedtothebackend,itisonlyforlong-termarchivalandauditingpurposes.Real-timecommunicationstotheback-endinthesesystemsarelimitedtosummariesandeventreports,andthebulksensordataisstoredlocallyatthesensornodeinpersistentstorageandisextractedlaterinadelaytolerantfashionuponavailabilityofhigherbandwidthormoreenergyef cientcommunicationlinksorperhapsbyahumanvisitor.Moreover,thedetectionlatencyassociatedwithacentralizedon-linemechanismmightnotbesuitableforapplicationsrequiringafastresponseduetodataloss.Clearly,inboththeseclassesofsystems(wherethebulksensordataiseithernotneededatthebackend,ornotneededimmediately),theintegritychecksstillneedtobeperformedinreal-timeasotherwisefaultysensorswillleadtofalsepositivesorfalsenegativesineventreportingorresultinfaultyresponsestouserqueries.Thisarguesforintegritycheckmechanismsthatareeitherlight-weightenoughtobeperformedlocallyatthenode,orwhichcanbeperformedatthebackendbutusesensordatasummariesandevenreportsasinputsasopposedtorawsensordata.Boththeseapproachesaresub-optimal:localin-nodemechanismslacktheinfor-mationfromothernodesthatcanhelpdisambiguatefaultsfromunexpectedphenomena,whilemechanismsoperatingonsummariesandeventreportsatthebackendoperatewithoutthebene toffullinformationonthecurrentmeasurementsatthesensors.Therefore,ahybridtieredapproachtointegritycheckingwouldbeneeded,andwillneedtobecloselyintegratedwiththemechanismneededforextractingandqueryingthesensors.ThispaperpresentsInspect,anon-linefaultdetectionanddiagnosissystembasedonsuchatiered

Abstract—We propose an on-line fault detection and diagnosis framework in sensor networks, called Inspect, which is based on a hybrid tiered approach to integrity checking. Inspect tiered design combines the benefits of distributed and centralized approac

approach.

Asdetailedlaterinthepaper,Inspect’stieredapproachisaprobabilisticonethatreliesonlocalforecastingmodelstopredictdatasensedateachnode,andonestimatingspatialcorrelationstocomputeexpectedmaximumdeviationsamongnearbynodes.Torealizethis,wemakeuseofaclassoflightweightandadaptabletimeseriesmodelsandacentral-izedmodel-basedsimilaritymechanismthatwereproposedbyTuloneandMadden[19],[20]foref cientlyansweringapproximatesensorqueriesintheSAFframework.TheInspectdetectionanddiagnosisframeworkcompriseslocaltimeseriesmodelsembeddedateachnode,andasuiteofnoveldetectionanddiagnosisalgorithmsthatrunatthesensornodesandatthebackendsinkinatieredhierarchy.Thelocalcomponentrunningateachnodeusesfault-speci cdetectorsbasedonthelocalmodelstoidentifysuspectedfaultsandgeneratealerts,whilethecentralizedcomponentrunningatthesinkdoesthede nitivedetectionanddiagnosisbasedonthesensorforecastingmodels,onthealerts,onthegeographicalcorrelationsamongnodes.ThecentralizedcomponentisatthecoreofInspectasitneedstodistinguishbetweenfaultsandunexpectedbehaviorinthephenomenon,whichcanbepar-ticularlychallengingasrealphenomenaevolveovertimeandarenotnecessaryuniformlydistributedoverthegeographicalsystemregion.Theseelementsalongwiththesensibilityofthesensornodetotheenvironment,makethedetectionofsensorfaultsmuchharderastheyrepresentanadditionalsourceofuncertainty.

Toaccomplishthis,InspectusestheconceptofaVirtualReferenceSensor(VRS)thatexploitstemporal-geographicalcorrelationstoestimatethegroundtruthforsensormeasure-mentstoagivenaccuracyusinglow-coststatisticaltechniques.Ineffect,theVRSplaystheroleofatrustedsensorinsidethenetwork.ThecomputationofVRSdoesnotrelyonnodeagreementbutcombinesmultipletechniquestoenhance exibilityandaccuracy(e.g.,timeseriesmodels,run-timemonitoringoferrorestimate,accountingfornodereliability,andclusteringbasedmodelsimilarity).ThesetechniquesallowInspecttoadaptthecomputationforVRSasafunctionoftheelapsedtimesinceinitializationanduserrequirements,whichenhancesrobustnessandleadstotunableaccuracy.Theresultingalgorithmdoesnotsufferfromproblemssufferedbyapproachesbasedonagreementamongamajorityofnodes,suchaseitheralossofprobabilityofdetectionorincreasedfalsepositives/negativesdependingonnodereliability.

Inspect’sgeneralitycomesfromitsindependencefromanyspeci cspatio-temporaldistributionoftheunderlyingphysicalphenomenon,andfromanyspeci capplication.Itsrobustnesscomesitsrelianceonaweakersetofassumptionsabouttheoperationalenvironment,anditsabilitytomonitorthequalityofthelocalsensormodels.Finally,Inspect’stunabilitycomesfromalgorithmsthatprovidecontrolknobsforspecifyingdesiredcon denceboundsonthefaultdetectionanddiagnosisperformance(falsepositiveandfalsenegative).

Thispaperisstructuredasfollows:inSectionIIweprovideanoverviewoftheInspectsystemanditsmaincomponents.In

SectionIIIwede neoursystemmodel,ourfaultclassi cationandproblemstatement,andinSectionIVweoverviewsomeofthetechniquesproposedinSAFandusedinInspect.InSectionVweillustratethetieredInspectapproach,andthenconcludethepaper.

II.FRAMEWORKOVERVIEW

TheInspectsystemconsistsoftwotiers:alocaltierbuiltateachsensornode,andacentralizedtierbuiltatthesink,whichrepresentsthecoreoftheInspectframework.Thelocaltierincludesatimeseriesmodelcomputedlocallyandthealgorithmsformonitoringthequalityofthemodel,foradaptingitwhenneeded,andfordetectingsuspectedfaults.Thecentralizedtiercomprisesalgorithmsforestimatingthegroundtruthandfordetectinganddiagnosingsensorfaults.Eachsensornodecommunicateswiththesinkonlywhenthelocalmodelchangesandwhenthesensornodedetectsanomaliesthatmightindicateasensorfault.Figure1.(a)illustratesthelocaltier(thelowerblock),thecentralizedone(theupperblock),andtheirinteractions(e.g.,thesinkcandynamicallytunetheusercon denceandthestreamdatarate).AsshowninFigure1.(a),afaultrepairingcomponentcanbebuiltontopoftheInspectsystem.

(a)Inspectcomponentsandtheir

interactions.

(b)Inspectoverview.Fig.1.

Frameworkoverview.

Localtier.SimilarlytoSAF,eachsensornodemaintainsatimeseriesmodel,whichislightweightandisabletoaccuratelypredictthephenomenonwithboundeduncertaintyanderrorprobability.Eachnodeperiodicallysamplesits

Abstract—We propose an on-line fault detection and diagnosis framework in sensor networks, called Inspect, which is based on a hybrid tiered approach to integrity checking. Inspect tiered design combines the benefits of distributed and centralized approac

sensorvaluesandusesthesevaluestocontinuouslymonitorthequalityofitsmodelandtodetectanomaliesthatmightindicateafault.Upondetectinganomaliesthenodeinformsthesink.Werefertotheselocalanomaliesassuspectedfaultsbecausetheyarenotnecessaryfaultsastheymightshowanunexpectedvariationintheunderlyingphenomenon(e.g.,out-of-rangetemperaturevaluesmightindicatea re).Asaresult,thedetectionoffaultsrequiresadeeperanalysisonthegeographicalcorrelationofnodes,anditiscarriedoutbythesinktoreducetheamountoftransmissionsandtoimprovetheaccuracyoftheframeworksincethesinkhasacompleteviewofthesystem.

Centralizedtier.Thelocalmodelsandthenoti cationsofsuspectedfaultstransmittedbyeachnodetothesinkprovidethesinkwithasnapshotofthesensordataproducedfromthenetworkduringatimewindow(sincelocalmodelscanvaryovertime).Suchasnapshotallowsthesinktodetectanddiagnosisfaultswithgivencon dencebydetectingtemporal-spatialcorrelationsofsensordata,andmorespeci callybycomputingtheVRS.ThecomputationoftheVRSisacrucialbuildingblockfordetectinganddiagnosingfaults.Itiscom-putedbasedonthelocaltimeseries,ontheestimationoftheexpectedmaximumdeviationbetweennodeswithinagivendistance(computedatrun-time),andonthecomputationofsimilarnodes.Itcanbetunedaccordingtotheusercon denceandvariesovertimeasthereliabilityofthesensordevicedecay.TheVRSiscrucialtodistinguishbetweenasensorfaultandanunexpectedvariationinthedatadistribution,andtodetectcalibrationfaults.Aswediscusslaterinthepaper,Inspectisabletodetectmorecomplextypesoffaultsbymeansofascorefunctionthatkeepstrackpreviousanomalies,theirfrequency,duration,anddetectioncon dence.Figure1.(b)summarizesthebasicactionsperformedatthesinkandateachsensornode.

III.SYSTEMMODEL

OurnetworkconsistsofadynamicsetSofsensornodesplacedinageographicsystemregionG,andacentralizedbasestationcalledthesink.Weassumethateachnodeislocation-aware,andthatisequippedwithsomesensingca-pability,performingperiodicreadingsonmphysicalphenom-ena,F1,F2,...,Fm,eachofwhichevolvesovertime(e.g.,F1=temperature,andF2=light).TosimplifyourdiscussionwewillfocusonasinglephenomenonF.Similarlytopreviousworkweassumenoderedundancy,thatis,foreachnodethereexistafewnodesthatarein uencedbythesamesetofsources.Notethatthisassumptionisweakerthanassumingthatthephenomenonisdistributedhomogenously,orthateachnodehasaminimumnumberofneighbors.Weassumethatmostsensornodesareinitiallycorrect,whichisarealisticassumption.Inspectcanworkalsoinmulti-hopnetworkswithseveralradiohopsbetweenanypairofnodesinthenetwork.A.Faultclassi cation

Wefocushereonhardwaresensorfaultsandanalyzefaultsaccordingtothefollowingthreeattributes:(1)causesoffaults,(2)geographicscopeoffaults,(3)temporalscopeoffaults.Sensorfaultsarestrictlyrelatedtoaspeci capplication,environmentwheretheyoperate,andhardware.Asaresult,itishardtoembraceandclassifyalltypesofsensorfaults.However,groupingsensorfaultsintoclassesiscrucialinunderstandingthemandindesigningaccuratefaultdetectionmethods.Itisimportanttonotethatthecauseandmanifesta-tionofsensorfaultsisoftencomplexastheymightrelatedtoseveralfactorswhoserelationishardtoexpressinananalyticalformasdiscussedin[7].Inthispaperwemakea rststeptowardsunderstandingandanalyzingthesecomplextypesoffaults.Ourpreliminaryclassi cationoffaultsconsistsofthefollowingthreecategoriesandincludesbothtransientandpersistentfaults:-F1:Stuck-atfaults.-F2:Calibrationfaults.

-F3:Morecomplextypesoffaults.

NotethatclassF3embracesallfaultsthatcannotbeclassi edasastuck-atorcalibrationfaults,andwillbeprobablyre nedaswegainabetterunderstandingofthecausesofsensorfaults.Wede nehereourclassesoffaults.LetusdenotethemeasurementsofthephenomenonFsensedatanodeiattimetbyfi(t),andthegroundtruth(error-free)valueatlocationibySi(t).

De nition1:Anodeishowsastuck-atfaultifthevariationoffi(t)duringatimeinterval[t1,t2]witht2 t1≥Φisnegligible,andiffi(t)deviatesfromthesourceSi(t)during[t1,t2]bymorethan units,where andΦareparameterstunedaccordingtothesensorhardware.

De nition2:Anodeishowsacalibrationfaultiffi(t)=α(t)·Si(t)+β(t)duringatimeinterval[t1,t2],wheret2 t1≥Φanddriftα(t)andoffsetβ(t)mayvaryovertime.

De nition3:Anodeishowsacomplextypeoffaultiffi(t)=Fi(t,S(t),E)+A(t,E)whereFiisafunctionofthetime,ofthedatasourceandoftheenvironmentE,andAisanagingfactorthatincreasesovertimeasthenodereliabilitydecays.

Thedetectionofthesecomplextypesoffaultsisachalleng-ingproblembecauseoftheirarbitrarytemporalpatternsandoftencomplexdependenciesontheenvironment,datasensedandaging.Inabsenceofananalyticalformrepresentingsuchdependencies,thebestwecandoistoaccuratelymonitorfunctionfi(t)andanalyzeanomaliesthatmightindicatethepresenceofacomplextypeoffault.InInspecteachnodeanalyzesitssensorreadingsanddetectanomalousonesthatmightindicateasensormalfunctioning,andreportsthemtothesink.Weprovideherealistofanomaliesdetectedatthesensornode.Notethatthislistisnotexhaustiveanditvariesaccordingtothespeci capplicationandphenomenonunderanalysis.

-A1:Frequentoutliervalues.Thesearevaluesthatsub-stantiallydeviatefromthesensordatamodel(expectedvalues)andwhosedurationislimitedintime.

-A2:Abruptvariationsinthedatadistributionconsistingofrapidvariationsinthedatatrend,discontinuitiesinthe

Abstract—We propose an on-line fault detection and diagnosis framework in sensor networks, called Inspect, which is based on a hybrid tiered approach to integrity checking. Inspect tiered design combines the benefits of distributed and centralized approac

sensordatacapturedbymonitoringthedatagradient,andothertypesofmodel-basedanomalies.

-A3:Noisydata:sensordatathatcannotbemodeledasatime-varyingfunctionandastationarymodelwithgivenaccuracy.ThatincludesGaussianandnon-Gaussiannoise.

-A4:Out-of-range.Thisanomalyoccurswhenthesensordatafallconsistentlyoutsidetheexpectedrangeforthephenomenon,whichisestimatedusingtemporal-spatialcorrelations.Notethatthisrangeisdifferentthantheoperationalrangeofasensornodeasitreferstothesensorreadings(outputs)andnottotheinputs.Anout-of-rangeanomalymightindicateasensorfaultorotherproblems,suchasanunexpectedinputsignal.B.Problemstatement

ThefocusofInspectistodetectanddiagnosissensorfaultsandprovidecon denceboundstotheend-user,thusofferingqualitymetricsonthedatasensedatsinglenodes.Wede neheretherequirementsfortheInspectsystem.

TheInspectsystemoutputsatanytimetalistoffaultysensornodes,denotedbyfaulty(t)={d1,...,dr},suchthateachdjisarecordcontainingtheidenti cationofthefaultynodedj.idandthetypeoffaultsdj.fdetectedattimet.Therefore,itmustsatisfythefollowingrequirementsinordertodetectanddiagnosisfaultsandprovidecon dencebounds:1)Theprobabilityoferroneouslydetectinganodeasfaulty(falsepositive)issmallerthanΦp;

2)Theprobabilityoferroneouslydetectingnodedj.idasfaultyoftypeFkinsteadoftypeFj,withk=j,issmallerthanΦd;

3)Theprobabilityoferroneouslydetectingafaultynodeasacorrectone(falsenegative)issmallerthanΦn.whereΦp,Φd,Φnarecon denceboundsde nedbytheuser.The rstconditionboundstheprobabilityoffalsepositive,thatistheerrorprobabilitythatacorrectsensorisdetectedasfaulty.Thesecondconditionboundstheprobabilitythatthediagnosisalgorithmismistaken.Thisoccurswhenasensornodeisfaultybutthediagnosisalgorithmoutputsoneormoreincorrecttypeoffault.Thethirdconditionboundstheprobabilityoffalsenegative,thatistheprobabilitythatanodeisfaultybutismistakenlydetectedascorrect.Thesethreecasesexhausttheerrorscenariosrelativetothedetectionanddiagnosisalgorithm.Therefore,theprobabilitythatInspectoutputssomewronginformationrelativelytoasensornodeissmallerthanΦp+Φd+Φn.

IV.PRELIMINARIES

Inthissectionwebrie ydescribesometechniquesproposedinSAF[19]thatareadaptedandemployedinInspect.Moreprecisely,weprovideanoverviewofSAFlightweighttimeseriesmodelsanditslocalmonitoringandadaptingalgorithms,andofSAFsimilarityapproach.

A.Localtimeseriesmodelandalgorithms

TheclassoflightweighttimeseriesmodelsproposedinSAFprovidesatrade-offbetweenaccuracyoftheforecastingmodelforthephysicalphenomenonsensedateachnode,andef ciency(computationalcostandmemorystorage).Moreprecisely,themodelbuiltateachnodedoesnotmodelthephysicalphenomenaduringtheentiresystemlifetimebutduringatimewindowusinganautoregressivemodelAR(q),whichisasubclassofARMAmodelswhosepredictionisgivenbyalinearcombinationofthepreviousqvalues.Moreprecisely,eachnodeusesasub-historyofthetimeseriesgeneratedfromitsperiodicreadingstomodelaphenomenonFasF(t)=mt+X(t),whereF(t)denotesthevalueofFattimet,mtisthevalueofapolynomialtime-varyingfunctionattimetwhosedegreevariesin[0,3],andX(t)isaweaklystationaryAR(q)timeseries(meaningthatitsmeanandcovariancearetime-invariant[1])withazero-meanGaussiannoiseandq∈[1,7].Thisdesignensurescheaplearning/re-learningandlowmemoryrequirements.ThestationarycomponentX(t)isde nedasfollows:X(t)=α1X(t 1)+...+αqX(t q)+b(ω)N(0,1)

(1)

whereα1,...,αqarerealconstantsandX(t i)indicatestheithpreviousreadingwithi∈[1,q],andb(ω)isthestandarddeviationofthewhitenoisesinceitspreviousreading.ThepredictorP(t)ofvalueF(t)attimetisgivenbythevalueofthecurrenttrendmtplusthepredictorofX(t),whichisalinearcombinationoftheincrementsordecrementsofthelastqreadingswithrespecttotheirtrendcomponent.SAFprovidesboundsonthepredictionerror(thedeviationofthepredictionvaluefromthesensorreading)thatarecrucialtomonitorthequalityofthemodelanddistinguishbetweenisolatedanomaliesandpersistentvariationinthedatadistribution[19].Thelocalmodeliscomputedattheendofthelearningphase,afterperformingNperiodicreadings,whereNisthesizeofthelearningset.Thisisdonebycomputing rstthecoef cientsofthetime-varyingfunctionmt,andthenthecoef cientsα1,...,αqofthestationarycomponentandthemaximumstandarddeviationofthenoise.Thesecoef cientsuniquelyidentifythemodel.Afterlearningthemodel,thenodetransmitsthesecoef cientstothesink.

Asmentionedabove,thelocalmodelmustbeadaptableinordertoeffectivelypredictnon-linearphenomena.Thetaskofmonitoringthequalityofthepredictionmodelandadaptingthemodelincaseofapersistentvariationinthedatadistributionisleftatthesensor.Eachnodestartsmonitoringthequalityofitsmodeljustafterthelearningphase.Ittakesaperiodicreading,updatesitslocalqueueofmostrecentreadingsandveri esifthatvaluebelongstothemodeldistribution.Themonitoringalgorithmisabletodistinguishbetweenpersistentvariationsinthedatadistributionandisolatedanomalies.Incaseofpersistentvariationsthenodeadaptsthemodelbycomputingthenewmodelcoef cients.However,theremightbecases,inwhichthenodeisunabletocomputeastationarycomponentAR(q)forq∈[1,7]with

Abstract—We propose an on-line fault detection and diagnosis framework in sensor networks, called Inspect, which is based on a hybrid tiered approach to integrity checking. Inspect tiered design combines the benefits of distributed and centralized approac

givenaccuracybecauseofhighdatanoise.Inthatcasethenodenoti esthesinkthatthesensordataisnoisyrelativelytotherequireduseraccuracy,andattemptstore-learnthemodelaftersometime.B.Similarityapproach

ThesimilarityapproachproposedinSAFisbasedonthelo-calmodels.Moreprecisely,twosensornodesareθ-similaratagivenpointintimeiftheirpredictionvaluesdeviatebyatmostθunits,whereθiscalledsimilarityparameter.Thenotionofmodel-basedsimilarityallowsthesinktogroupintoclustersnodesthataresimilar,basedonthelocalmodelsitstoresandatnoadditionalcost.Notethattheclusterformationcanvarydynamicallyaccordingtothedistributionoftheunderlyingsensordata.SAFapproachtransformsthecomplexproblemofclusteringsimilarnodesintoaninterval-basedproblemusingtheboundsderivedforeachlocalmodel.Moreprecisely,itestablishesforeachsensoriacorrespondencebetweenitslocalmodelattimetandarealintervalI=[li,Li],whereliandLiarethelowerandupperboundsofthepredictionvalueofSimodelattimet.Moreprecisely,li=mt νσiandLi=mt+νσi,wheremt=a+btandσiisthestandarddeviationofX(t).TheseboundsarerelevantinInspectwhencomputingtheVRS.

V.THEINSPECTSYSTEM

Thelocalmodelsandthenoti cationsofsuspectedfaultstransmittedbysensorsprovidethesinkwithasnapshotofthesensordataproducedduringatimewindowaslocalmodelscanvaryovertime.Notethatsuchamodel-basedsnapshotismorerobusttonoiseandmoreexpressivethanavalue-basedsnapshotsinceitprovidesadditionalinformationsuchasthetrendofthesensorreadingsandtheirrange,anditiscrucialtocomputetheVRSanddetectfaultswithgivencon dence.AsmentionedintheIntroduction,anomaliesdetectedatsensorsdonotnecessaryindicatesensorfaultsastheymightbecausedbyanunexpectedvariationinthephysicalphenomenon(e.g.,anodesensingout-of-rangetemperaturevaluesmightindicateeitherafaultora re).Theanalysisoftemporal-geographicalcorrelationsisthereforeneededtodetectsensorfaults.Thisisachallengingtaskespeciallyincasethesta-tisticaltemporal-spatialdistributionofthephenomenonisnothomogeneous,whichoftenoccursinrealdeployments.ThistaskiscarriedoutatthesinkbycomputingtheVRS,whichapproximatesthegroundtruth(error-free)valuessensedateachsuspectednode.

A.Localdetectionofsuspiciousfaults

EachsensornoderunsarevisedversionofthemonitoringandadaptingalgorithmssummarizedinSectionIV.Itisabletodetectsuspectedstuck-atfaultsoftypeF1,andanomaliesoftypesA1–A4thatcanindicateatypeF3fault.Sincethenodeisnotabletodetectfaults(i.e.,astuck-atfaultmightre ectavariationinthephenomenonasinthecaseoflightsensors),wedenotetheseanomaliesassuspectedfaults.Upondetectingasuspectedfault,thenodemonitorsitsdurationandnoti es

thesinkwhenitrecoversfromsuchanomaly.Figure2showsgraphicallythemainstepstakenbyeachsensor.We

brie y

During monitoring and

upon adapting the model detect:

F1 suspected faultA1 …A4 types of anomalies

Notify sink upon detecting

anomalies and upon recovering

<Recover A2>

Fig.2.Overviewoflocalfaultdetection.

summarizeherehoweachnodeisabletodetectsuspectedfaultsoftypeF1andanomaliesoftypesA1 A4.

Stuck-atfault.Weadaptthemonitoringalgorithmtodetectifthesensorreadingsareinvariant(oritsvariationisnegligible)anddeviatesubstantiallybytheexpecteddistribution.Upondetectingastuck-atfault,thenodeinformsthesinkandmonitorsitsduration.Itimmediatelynoti esthesinkwhenthesensorrecovers.

AnomaliesoftypeA1-A4.Similarlytothestuck-atfaultcase,themonitoringalgorithmcanbeadaptedtodetectwhensensorreadingsexceedtheexpectedrange(anomaliesoftypeA4).Thesinkcomputestheexpectedrangebasedonthehistoryofthelocalmodelsstoredlocallyandadaptsitincaseofasubstantialshiftinthedistribution(e.g.,in[16]asubstantialshiftinthechemicaldistributionwasobservedrightafterirrigation).Anexampleofexpectedrangeforatemperature-controlledroomatnightduringsummercanbe[17 C,25 C];valuesoutsidethisrangemightindicateasensorfault,orafaultintheairconditioningsystem,oranunexpectedinputsignal,orasubstantialvariationintheenvironmentalconditions.ItisimportanttonotethatanincorrectrangecomputedbythesinkdoesnottriggerfaultpositivesinInspectsincesimilarnodeswillreportthatanomalybutanupdateoftheexpectedrange,whichwillbetransmittedbythesinktosensornodes.

Asensornodeisalsoabletodetectfrequentoutliers(anomaliesoftypeA1),whicharereadingsthatdeviatefromthepredictedvaluebymorethanνstandarddeviationsofthenoise.Sinceourfocusisondetectinganomaliesthatcanindicatethepresenceofacomplextypeoffault,thenodenoti esthesinkanomaliesthatoccurredwithagivenfrequency,thatismorethanιtimesduringamonitoringwindow,whereιisapercentagethresholddependingonthehardwareandthephenomenonsensed(e.g.,incaseoflightsensingitisprobablydesirabletodiscardoutliersastheymightdependtootherfactorssuchasre ections,thatarenotrelevanttotheapplication).

Inaddition,asensornodeisabletodetectabruptvariationsinthedatadistributionrelativelytoatimeseriesmodel(anomaliesoftypeA2).Thistypeofanomalyincludesabruptshiftsinthedatatrendandvariationsinthedatagradient.

Abstract—We propose an on-line fault detection and diagnosis framework in sensor networks, called Inspect, which is based on a hybrid tiered approach to integrity checking. Inspect tiered design combines the benefits of distributed and centralized approac

Moreover,asensornodeisabletodetectperiodsofnoisydataduringwhichitisnotpossibletocomputeaweaklystationaryAR(q)componentforq∈[1,7].ThatincludesbothGaussianandnotGaussiannoise.Inthatcase,thenodenoti esthisanomalytothesinkandwaitsforthenextfewreadingsbeforeattemptingtore-computethemodel.

ItisimportanttonotethatInspectisabletoprovidecon denceboundsonthelocaldetectionandqualitymetricsforthelocalmodels.Thisisimportantforthesinktoprovidecon denceboundsonthecentralizeddetectionandmostimportantlytomonitorthedegreeoffaultofasensornodeandcomputethescorefunction,putingtheVRS

Thecomputationofareferencesourceforasensornodeplaysacrucialroleindetectinganddiagnosingfaultsintheabsenceofhigh-precisionsensorsthatprovideinformationregardingthegroundtruthvalues.Thereferencesourceisusu-allyestimatedbyexploitingnoderedundancy,whichassumesgeographicalcorrelationsamongnodes.ItallowsInspecttodetectcalibrationfaultsandtodistinguishbetweenasensorfaultandanunexpectedvariationinthephysicalphenomenon.Thetaskofdistinguishingbetweenafaultandanunex-pectedvariationinthephysicalphenomenoniscarriedoutbythesinkusingthemodelcoef cientsstoredatthesinkandthenoti cationsofsuspectedfaultssentbynodes,asdescribedintheprevioussection.LetussupposethatanodeNdetectsananomaly,eventE,andnoti esittothesink.InordertodetectifEindicatesafaultthesinkveri esifthereexistxsensornodesthatareexpectedtobesimilartoNandthathavedetectedthesametypeofanomaly.InspectdetectsnodeNasfaultyifitdoesnot ndaquorumofxsimilarsensorsthatreportedthesametypeofanomaly.ThisquorumofxsensorsrepresentstheVRSsourceandhastosatisfythefollowingproperties:

1)Accuracy:theVRSofanodeNcomputedattimetestimatesthegroundtruthvaluesensedatNattimetwithboundeduncertaintyandboundederrorprobability;

2)Robustness:itisrobusttodatanoiseandtotemporal-spatialvariationsoftheunderlyingphenomenon.

TheVRSaddressesrobustnessbyrelyingonweakerassump-tions.Moreprecisely,itdoesnotassumethatthephenomenonvarieshomogeneouslyandthatitsunderlyingstatisticaldis-tributionisstatic.Notethataphenomenonisde nedashomogeneousifitisintrinsicallystationaryandisotropic,meaningthatthevariancebetweenthephenomenonsensedatequidistantpointsinthesystemregionisinvariantsinceitvariesaccordingtoafunctionf(h)oftheirEuclideandistanceh.Thatis,var{Z(s1) Z(s2)}=f(h)foranypoints1ands2inthesystemregion[18].Clearly,thisassumptiondoesnotalwaysholdinrealdeploymentsbecauseofthepresenceofexternalfactorsorobstaclesthatin uencethespatialdistributionofthephenomenon.

ItisimportanttonotethattheVRSvariesaccordingtothetimeelapsedasthereliabilityofsensornodesdecayovertime,andtothecurrentuserrequirementstoenhanceaccuracyand exibility.Thisdesignenhancesrobustnesssincestaticcriteriacaneasilytriggerfalsepositivesandfalsenegativesoverthesystemlifetime(e.g.,ifxequaltothehalfoftheneighborsofN).AcrucialstepindetectingifasuspectedsensorNattimetisfaultyconsistsofcomputingnodesthataresimilartoNatthattime.Notethatsincethephenomenoncanevolveovertimesensorsmightshowdifferentsimilaritypatternsduringthesystemlifetime.ThesinkdetectsifasensornodeNisfaultybycomputingnodesthatareexpectedtobesimilartoNandbycheckingiftheysensedthesametypeofanomaly.Moreprecisely,sensorsthataresimilararein uencedbythesamesetofsources.Bydoingthatweassumethatnearbynodesusually(butnotalways)sensesimilarvalues,whichisarealisticassumption.However,thissimpleideabringsupthefollowingquestions:

1)HowcanwecomputenodesthatareexpectedtobesimilartoNifthephysicalphenomenonvariesovertimeandspaceandsensorscanbefaulty?

2)Howcanwede nethethresholdxasafunctionofthetimeandoftheusercon dence?

Weanswerthe rstquestionbydetectinggeographicalsimilaritiesamongnodesusingthemodel-basedsimilarityapproachsummarizedinSectionIV.Wechoosethissimilarityapproachbecauseitismorerobusttodatanoiseandallowsthesinktoclustersimilarnodesatthesinkatnoadditionalcommunicationcost.TheideaunderlyingourapproachistodetectneighborsofNthatareδN–similartoN,whereδNistheexpectedmaximumaveragedivergencebetweenthevaluessensedatNandatitsneighbors.ThecomputationofthesimilarityparameterδNisrelevantfortheaccuracyandrobustnessoftheVRS.Itiscomputedinitiallyinadistributedfashionbyeachnodeastheytransmittheirperiodicreadingsduringtheinitiallearningphase.EachnodecomputesatableTNcontaininganentry di, i foreachneighborSi∈RN,wherediistheEuclideandistancebetweenNandSi,and iistheaveragedivergencebetweentheirvaluessensedduringthelearningphase(e.g.,N=30).Attheendoftheinitiallearningphasethenodetransmitstothesinkthemodelcoef cientsandvalues iofTN.These ivaluesallowthesinktocomputetableTNforeachnodeNandwhenneededtoextendsuchatablebyincludingfarthernodes,andmostimportantlytocomputeδNasfollows

δN:=Smax{ j| j<δmax}

j∈RN

whereδmaxisanupperboundsofδNthatdetectsthepresenceofaninitiallyfaultyorun-calibratednode.ThesinkmonitorsvariationsofthesimilarityparameterδNandupdatesitwhenneeded.

ThecomputationoftheVRSreliesonthecomputationoftheδN–clustercenteredatnodeN,whichcontainsneighborsofNthatareδN–similartoN.Thiscomputationisrunatthesinkandusesarevisedversionoftheclusteringalgorithm

Abstract—We propose an on-line fault detection and diagnosis framework in sensor networks, called Inspect, which is based on a hybrid tiered approach to integrity checking. Inspect tiered design combines the benefits of distributed and centralized approac

summarizedinSectionIV.Moreprecisely,thesinkorderstheupperboundsofthepredictionvaluesofthenodesinRN,andstartingfromtheupperboundofNitparsesthesortedlistinbothdirectionsto ndnodesthatareδNsimilarandreturnsasetCofnodesinRNthatareδN–similartoN.Figure3showsanexampleofTNtablewithtemperaturevalues,andδN–cluster,whereδmin=0.3,δmax=0.5andthemaximumwidthofallnodeintervals(differencebetweenupperandlowerboundofthepredictionvalueforanodeinRN)isequalto0.3.InourexamplenodesS1,S2,S4formsaδN

< 0.5-0.3

< 0.5-0.3

Cluster of N = { S2, S4, S1 }

Fig.3.Exampleofcomputingsimilarnodes.

Inspectaddressesnon-homogeneousspatialdistributionofthephysicalphenomenoninRNbyassigningdifferentweightstonodesintheδN-cluster,dependingontheirvalue i.Itgivesmoreweighttonodesthathaveahigherdegreeofsimilarity(smaller i).Asmentionedbefore,thethresholdxfortheVRSisafunctionofthetimetandoftheusercon denceµanditiscomputedbyconsideringthereliabilityofasensornodeatthattimeprovidedafaultdistribution(e.g.,exponentialdistribution)andbylimitingtheprobabilityoffalsepositivesandfalsenegativesbyµ.

ThelocaldetectionandtheVRSsourceenablethesinktodetectcalibrationfaults(faultsoftypeF2)andmorecomplextypesoffault.Thisisobtainedbykeepingtrackofthesensoranomalies,theirfrequencyandtheirdetectioncon dence.Moreprecisely,every timeunits,thesinkcomputesascorefunctionforeachnoderelativelytothattimewindow,andusesthesevaluesasatimeserieswhichindicatesthefaultydegreeofnodesoverthetime.Suchatimeseriesenablethesinktodetecteitheranincreaseinthetransientfaultsofanode,andperiodicfaultpatterns.

VI.CONCLUSION

Wehaveproposedanon-linefaultdetectionanddiagnosisframework,calledInspect,forsensornetworksthatisbasedonahybridtiereddesigntoimprovetheresponsivenessandtheef ciencyofthefaultdetection.Inspectconsistsofalocaltierbuiltateachsensornodeandcapableofdetectinganomalies,andacentralizedtierbuiltatthesinkandcapa-bleofdistinguishingbetweensensorfaultsandunexpected

temporal-spatialvariationsinthephenomenon,anddetectingmorecomplextypesoffaults.

Inspectusesacombinationofstatisticalandclusteringtech-niquestechniquessuchastimeseriesmodel,simplegeograph-icalcorrelations,model-basedsimilarityandthereliabilityofthenode,thatenhanceits exibilityandrobustness.Inspectsoffersseveraldesirablefeatures:itprovideson-linedetection,itisgeneralandmorerobusttotemporal-spatialvariationsofthephenomenon.Moreover,Inspectprovidescon denceboundsthatcanbedynamicallytunedaccordingtotheuserrequirementsforabetterresourcemanagement,andaddressestheproblemofdetectingmorecomplextypesoffaults.

REFERENCES

[1]P.BrockwellandR.Davis.IntroductiontoTimeSeriesandForecasting.

Springer,1994.

[2]J.Chen,S.Kher,andA.Somani.Distributedfaultdetectionofwireless

sensornetworks.InDIWANS,2006.

[3]E.ElnahrawyandB.Nath.Cleaningandqueryingnoisysensors.InIn

Proc2ndWorkshoponSensorNetworksandApplications,September2003.

[4]A.S.-V.F.Koushanfar,M.Potkonjak.Errormodelsforlightsensors

bynon-parametricstatisticalanalysisofrawsensormeasurements.InIEEESensors,October2004.

[5]M.P.F.Koushanfar.Markov-chainbasedmodelsformissingandfaulty

datainmica2sensormotes.InIEEESensors,October2005.

[6]J.Feng,Megerian,andM.Potkonjak.Model-basedcalibrationforsensor

networks.InIEEEInternationalConferenceonSensors,October2003.[7]Y.H.HuandB.Benson.Sensornetworkdataqualityassurance.

Technicalreport,UniversityofWisconsin,Madison,2005.

[8]C.Intanagonwiwat,R.Govindan,andD.Estrin.Directeddiffusion:A

scalableandrobustcommunicationparadigmforsensornetworks.InMobiCOM,2000.

[9]F.Koushanfar,M.Potkonjak,andA.Sangiovanni-Vincentelli.On-line

faultdetectionofsensormeasurements.IEEESensors,pages974–980,October2003.

[10]B.KrishnamachariandS.Iyengar.Distributedbayesianalgorithmsfor

fault-toleranteventregiondetectioninwirelesssensornetworks.IEEETrans.onComputers,53(3):241–250,2004.

[11]uraBalzano.Blindcalibrationofsensornetworks.InInProc.

rmationProcessinginSensorNetworks,April2007.[12]X.Luo,M.Dong,andY.Huang.Ondistributedfault-tolerantdetection

inwirelesssensornetworks.IEEETrans.onComputers,55(1):58–60,2006.

[13]S.Madden,W.Hong,J.M.Hellerstein,andM.Franklin.TinyDBweb

page.http://telegraph.cs.berkeley.edu/tinydb.

[14]R.NiuandP.K.Varshney.Distributeddetectionandfusioninalarge

wirelesssensornetworkofransomsize.EurasipJournalonWirelessComm.andNetworking,4:462–472,2005.

[15]N.Ramanathan,L.Balzano,M.Burt,D.Estrin,E.Kohler,T.Harmon,

C.Harvey,J.Jay,S.Rothenberg,andM.Srivastava.Rapiddeploymentwithcon dence:Calibrationandfaultdetectioninenvironmentalsensornetworks.TechnicalReport62,CENS,April2006.

[16]N.Ramanathan,T.Schoellhammer,D.Estrin,M.Hansen,T.Harmon,

E.Kohler,andM.Srivastava.The nalfrontier:Embeddingnetworkedsensorsinthesoil.TechnicalReport68,CENS,UCLA,Nov2006.[17]A.Sharma,L.Golubchik,andR.Givindan.Ontheprevalenceofsensor

faultsinreal-worlddeployments.InInProc.ofSECON,June2007.[18]R.Smith.Environmentalstatistics.June2001.Preprint:http://www.

stat.unc.edu/postscript/rs/envnotes.pdf.

[19]D.TuloneandS.Madden.Anenergy-ef cientqueryingframeworkin

sensornetworksfordetectingnodesimilarities.

[20]D.TuloneandS.Madden.Saf:asimilarity-basedadaptableframework

forapproximatequeryinginsensornetworksbasedontimeseriesforecasting.Technicalreport,August2006.Submittedtojournal.

[21]G.Werner-Allen,K.Lorincz,J.Johnson,J.Lees,andM.Welsh.Fidelity

andyieldinavolcanomonitoringsensornetwork.In7thUSENIXSymposiumonOperatingSystemsDesignandImplementation,2006.

本文来源：https://www.bwwdw.com/article/naqm.html