International Journal of High Performance Computing Applications, 2002, to appear. Scalable

HeterogeneousSensorNetworks

MauriceChu,HorstHaussecker,andFengZhao

XeroxPaloAltoResearchCenter

3333CoyoteHillRoad

PaloAlto,California94304,U.S.A.Abstract

Thispaperdescribestwonoveltechniques,information-drivensensorquerying(IDSQ)andconstrainedanisotropicdiffusionrouting(CADR),forenergy-efficientdataqueryingandroutinginadhocsensornetworksforarangeofcollabora-tivesignalprocessingtasks.Thekeyideaistointroduceaninformationutilitymeasuretoselectwhichsensorstoqueryandtodynamicallyguidedatarouting.Thisallowsustomaximizeinfor-mationgainwhileminimizingdetectionlatencyandbandwidthconsumptionfortaskssuchaslocalizationandtracking.Oursimulationresultshavedemonstratedthattheinformation-drivenqueryingandroutingtechniquesaremoreenergyefficient,havelowerdetectionlatency,andprovideanytimealgorithmstomitigaterisksoflink/nodefailures.

1Introduction

Advancesinwirelessnetworking,microfabrication(e.g.MEMS),andembeddedmicroprocessorshaveenabledanewgenerationoflargesensornetworkspotentiallyappli-cabletoarangeoftrackingandidentificationproblemsinbothcivilianandmilitaryapplications.Examplesincludehuman-awareenvironments,intelligenttransportationgrids,factorycondition-basedmonitoringandmaintenance,andbattlefieldsituationalawareness.Withsuchadvancescomenewchallengesforinformationprocessingwhichnecessitatethedevelopmentofnovelroutingandcollaborativesignalprocessing(CSP)algorithmstohandlethedistributeddatagatheredbythenetworkandprocesstheinformationforthegiventask.

Distributedsensornetworksarecharacterizedbylimitedbatterypower,frequentnodeattrition,andvariabledataandcommunicationquality.Toscaleuptorealistictrackingandclassificationapplicationsinvolvingtensofthousandsofsen-sors,heterogeneoussensingmodalities,multipletargets,andnon-uniformspatio-temporalscales,thesesystemshavetorelyprimarilyonintelligentcollaborationamongdistributed

Correspondingauthor.Email:zhao@parc.xerox.com,Tel:650-812-5078.

sensorstosignificantlyimprovetrackingaccuracyandreducedetectionlatency.

Sincesensorsoftenmustcollaborateinordertoperformagivensensingtaskabouttheenvironment,determiningtheutilityofaremotesensor’sdataisimportantinconservingpowerduetothenecessityofcommunication.Thus,theprob-lemweareaddressinginthispaperishowtodynamicallyquerysensorsandroutedatainanetworksothatinformationgainismaximizedwhilelatencyandbandwidthconsumptionisminimized.Ourapproachreliesontwokeyideas:infor-mationdrivensensorquerying(IDSQ)tooptimizesensorse-lectionandconstrainedanisotropicdiffusionrouting(CADR)todirectdataroutingandincrementallycombinesensormea-surementssoastominimizeanoverallcostfunction.Dy-namicsensortaskingandcollaborationhasthefollowingad-vantages.Itiskeytothescalabilityoflarge-scalesensornet-worksthroughselectivesensortasking.Itcandrasticallyre-ducelatencyindetectionandtrackingbyapplication-awareoptimalrouting.Itenablesprogressiveaccuracybyincremen-talbeliefupdate.Itensuresgracefuldegradationinperfor-manceduetolinkfailureorsensorattritionbyprovidingany-timealgorithms.

Usinginformationutilitymeasurestooptimizesensorse-lectionandincrementalbeliefupdatetocombineinforma-tion[inacentralizedsystem]isnotnew(e.g.,activetest-ingGeman&Jedynak1996andKalmanfilter),noriscost-baseddata[routinginadhocnetworks(e.g.,directeddiffusionroutingIntanagonwiwatetal.2000]).WhatisnewaboutIDSQ/CADRistheuseofageneralformofinformationutil-itythatmodelstheinformationcontentaswellasthespatialconfigurationofanetworkinadistributedway;withthisfor-mulation,eachnodecanevaluateaninformation/costobjec-tive,makeadecision,updateitsbeliefstate,androutedatabasedonthelocalinformation/costgradientandend-userre-quirement.Existingapproachestosensorqueryinganddataroutingforadhocheterogeneoussensornetworkstypicallyemployapublish-subscribescheme[Huang&Garcia-Molina2001],wherepublishersadvertisetheirdata“attributes”,sub-scriberssubmit“interests”,andaneventbrokeringsystemmatches“interests”with“attributes”.Thedirecteddiffu-sion[Intanagonwiwatetal.2000]isonesuchexample,wheretheroutingpathsareestablishedusingthedistanceinforma-tionbetweenneighboringnodestominimizethenumberofhopsinRFcommunication.IDSQ/CADRcanbeconsidered

asageneralizationofdirecteddiffusionrouting.Weusebothinformationgainandcommunicationcosttodirectthedatadiffusion,andhencecanbemoreenergyawareandefficientthandirecteddiffusionroutingwheretypicallyonlycommu-nicationcostisofconcern.

Ourapproachallowssensorstobecomeactivatedwhenthereare“interesting”eventstoreport,andonlythosepartsofthenetworkwiththemostusefulinformationbalancedbythecommunicationcostneedtobeactive.Thetypeofnetworkscanbestealthyandisadvantageousforsecurityreasons.Thenetworkscouldalsoactivelyseekoutinfor-mation,basedonpredictionsofwhenandwhere“interest-ing”eventswillbe.Anentiresensornetwork,withitsin-networkprocessingpowerforprocessing,routing,andcom-biningdistributedsensordata,isanextremelypowerfuldis-tributedcomputingsystem.Onenotablefeatureofthisdis-tributed“supercomputer”isthatitsI/Oisalsodistributedandcanmatchwellwiththeimpedanceofthesensingapplicationdomainbydesign.

Therestofthepaperisstructuredasfollows.Section2introducesageneralformulationoftheproblemintermsofaninformationutilitymeasureandmentionsissuesofrepre-sentingandincrementallyupdatingthebeliefstate.Section3presentsthealgorithmsforinformationdrivensensorquery-ingandconstrainedanisotropicdiffusionrouting.Section4describesexperimentalevidenceandcomparesourapproachwithexistingworkinuncertaintymanagementanddatadiffu-sionrouting.Section5elaboratesonotherroutingprotocolsandissuesofbeliefrepresentation,andSection6discussesre-latedwork.

2ProblemFormulation

2.1SensingModelandMeasureofUncertainty

Wewillmodelourestimationproblemusingstandardestima-tiontheory.Thetime-dependentmeasurement,sor,with,ofsen-thatcharacteristics,,isrelatedtotheparameters,

tion(ormeasurement)wewishtoestimatemodel

throughthefollowingobserva-(1)

whereisa(possiblynon-linear)functiondependingonandparameterizedbytimedependent),whichrepresentsthereferstowhat,aboutknowledgekindsensoraboutofsensorincludesensoris,sensing.Typical(possiblysensorpositionmodality,character-istics,which,andotherparameters,suchasthenoisemodelofsensorandnodepowerreserve.Thereasonforexplicitlyrepresentingthesesensorcharacteristicsisduetothedistributedandheteroge-neousnatureofthesensorprocessingtasks.

In(1),weconsiderageneralformoftheobservationmodelthataccountsforpossiblynon-linearrelationsbetweenthesensortype,sensorposition,noisemodel,andtheparameterswewishtoestimate.Aspecialcaseof(1)wouldbe

whereisa(possiblynon-linear)observationfunction,andisadditive,zeromeannoisewithknowncovariance.

Incaseisalinearfunctionontheparameters,(1)reducestothelinearequation

(2)

Inordertoillustrateourtechnique,wewilllaterconsidertheproblemofstationarytargetlocalizationwithstationarysensorcharacteristics.Here,weassumethatallsensorsareacousticsensorsmeasuringonlytheamplitudeofthesound

signalsothattheparametervector

istheunknowntargetposition,and

(3)

whereistheknownsensorposition,andistheknownadditivenoisevariance.Notethereisnolongeratimedepen-denceforand.Assumingthatacousticsignalspropagateisotropically,theparametersarerelatedtothemeasurementsby

(4)

whereisagivenrandomvariablerepresentingtheamplitudeofthetarget,isaknownattenuationcoefficient,andistheEuclideannorm.isazeromeanGaussianrandomvariablewithvariance.

Intheremainderofthispaper,wedefinethebeliefasarep-resentationofthecurrentaposterioridistributionofgivenmeasurements:

Typically,theexpectationvalueofthisdistribution

isconsideredtheestimate(i.e.,theminimummeansquarees-timate),andweapproximatetheresidualuncertaintybythecovariance:

Whatstandardestimationtheorydoesnotconsiderandisofgreatimportancetodistributedsensornetworks,however,isthatknowledgeofthemeasurementvalueandsensorcharacteristicsnormallyresidesonlyinsensor.Inordertocomputethebeliefbasedonmeasurementsfromseveralsensors,wemustpayacostforcommunicatingthatinforma-tion.Thus,maintainingwhatinformationeachsensornodehasaboutothersensornodesisanimportantdecision.Thisiswhythesensorcharacteristicsbecauseitisimportanttoknowwhatareinformationexplicitlyrepresentedisavailableforvariousinformationprocessingtasks.

Sinceincorporatingmeasurementsintothebeliefarenowassignedcosts,theproblemistointelligentlychooseasub-setofsensormeasurementswhichprovide“good”informa-tionforconstructingabeliefstateaswellasminimizingthecostofhavingtocommunicatesensormeasurementstoasin-glenode.Inordertochoosesensorstoprovide“good”up-datestothebeliefstate,itisnecessarytointroduceameasureoftheinformationasensormeasurementcanprovidetoabe-liefstate.Wewillrefertothisastheinformationcontentofa

particularsensor.Theformalizationofthecriterionforselect-ingthenextbestsensoristhemaincontributionofthispaper.Section2.2willmakethisintuitivenotionofinformationcon-tentmathematicallyrigorous,Section2.3willproposeseveralinstancesofinformationcontentmeasuresthatcanbeprac-ticallyimplemented,andSection2.4willcombinethemea-sureswithcommunicationcoststoprovideacompositeutilityfunction.

2.2SensorSelection

InSection2.1weformulatedthedistributedsensingmodel.Giventhecurrentbeliefstate,wewishtoincrementallyup-datethebeliefbyincorporatingmeasurementsofpreviouslynotconsideredsensors.However,amongallavailablesen-sorsinthenetwork,notallprovideusefulinformationthatim-provestheestimate.Furthermore,someinformationmightbeuseful,butredundant.Thetaskistoselectanoptimalsubsetandtodecideonanoptimalorderofhowtoincorporatethesemeasurementsintoourbeliefupdate.

Figure1illustratesthebasicideaofoptimalsensorselec-tion.Theillustrationisbasedupontheassumptionthatesti-mationuncertaintycanbeapproximatedbyaGaussiandistri-bution,illustratedbyuncertaintyellipsoidsinthestatespace.Inbothfigures,thesolidellipsoidindicatesthebeliefstateattime,andthedashedellipsoidistheincrementallyupdatedbeliefafterincorporatinganadditionalsensoratthenexttimestep.Althoughinbothcases,aandb,theareaofhighuncer-taintyisreducedbythesameamount,theresidualuncertaintyincaseamaintainsthelargestprincipalaxisofthedistribu-tion.Ifweweretodecidebetweenthetwosensors,wemightfavorcasebovercasea,basedupontheunderlyingmeasure-menttask.

Ithastobeemphasizedthat,duetothedistributednatureofthesensornetwork,thisselectionhastobedonewithoutexplicitknowledgeofthemeasurementresidingateachindi-vidualsensor,inordertoavoidcommunicatinguselessinfor-mation.Hence,thedecisionhastobemadesolelybaseduponthesensorcharacteristics,andthepredictedcontributionofthesesensors.

Althoughdetailsoftheimplementationdependonthenet-workarchitecture,thefundamentalprinciplesderivedinthissectionholdforboth,theselectionofaremotesensorbyaclusterhead,aswellasthedecisionofanindividualsensortocontributeitsdataandtorespondtoaquerytravelingthroughthenetwork.Thetaskistoselectthesensorthatprovidesthebestinformationamongallavailablesensorsthathavenotbeenincorporated.Aswillbeshownintheexperimen-talresults,thisprovidesafasterreductioninestimationun-certainty,andusuallyincurslowercommunicationoverheadformeetingagivenestimationerrorrequirement,comparedtoblindornearest-neighborsensorselectionschemes.

Toderiveamathematicalformulationofthesensorselec-tionprocessweassumetherearesensorslabeledfromandthe.Letcorrespondingmeasuredbevaluesthesetofofthetosensorssensorswhose

are

measurementshavebeenincorporatedintothebelief.Thatis,thecurrentbeliefis

abFigure1:Illustrationofsensorselectioncriteriabasedupontheinformationgainofindividualsensorcontributions.Here,theinformationgainismeasuredbythereductionintheerrorellipsoid.

Thesensorselectiontaskistochooseasensorwhichhasnotbeenincorporatedintothebeliefyetwhichprovidesthemostinformation.Tobeprecise,letusdefineaninformationutilityfunction

whichactsontheclassonandreturnsarealnumberofwithallprobabilitybeingthedistributionsdimensionof.Thebutionwhichroleis.Smallerindicatesofistovalueshowassignrepresentspreadavalueoutamoreortouncertaineachelement

spreadtheoutdistri-distri-butionwhilelargervaluesrepresentatighterdistribution.WewilldeferdiscussionofdifferentchoicesoftoSection2.3.

Incorporatingameasurement,where,intothecur-rentbeliefstateconditioningthebeliefwiththenewismeasurement.accomplishedHence,byfurtherthenewbeliefstateis

Fromestimationtheory,thisdistributioncanbecomputed

withknowledgeof,,andandsomeappropriateinde-pendenceassumptions.Incorporatingameasurementhastheeffectofmappinganelementofof.Sincegivesameasureofhowtoanother“tight”elementadistri-butionintois,chooseitisclearis

thatthebestsensor

However,inpractice,weonlyhaveknowledgeofandtodeterminewhichsensortochoose.Inotherwords,wedon’tknowthemeasurementvaluebeforeitisbeingsent.Nevertheless,wewishtoselectthe“mostlikely”bestsensor.Hence,itisnecessarytomarginalizeouttheparticularvalueof.Notethatforanygivenvalueofforsensor,wegetaparticularvalueforsetofallvaluesof.forNow,actingonthenewbeliefstate

choicesforeachof.sensorHereare,considersomepossi-the

bilitiesforsummarizingthesesetofvaluesofbyasinglequantity:

Bestaveragecase:

Foraparticular,utilityoverthesetofnewrepresentsbeliefstatestheaverageweightedinformation

by

information.Theutility.

sensorchosenistheonewithbestaverage

Maximizingworstcase:

Inthiscase,foraparticular,wetakethepessimisticviewthatnaturewillpresentuswithameasurementvaluethatwouldgiveustheworstpossibleinformationutility.Hence,wearemaximizingourworstsuspicions.

Maximizingbestcase:

Inthiscase,foraparticular,wetaketheoptimisticviewthatnaturewillprovideuswithameasurementvaluethatwouldgiveusthebestpossibleinformationutility.Hence,wearemaximizingourmostoptimisticbeliefs.

Section2.3willpresentsomepossibilitiesoftheparticularformoftheinformationutility.

2.3InformationUtilityMeasures

Inordertoquantifytheinformationgainprovidedbyasensormeasurement,itisnecessarytodefineameasureofinforma-tionutility.Theintuitionwewouldliketoexploitisthatin-formationcontentisinverselyrelatedtothe“size”ofthehighprobabilityuncertaintyregionoftheestimateof.Thissec-tionwilldefineseveralsuchmeasures.

Covariance-Based

Inthesimplestcaseofauni-modalposteriordistributionthatcanbeapproximatedbyaGaussian,wecanderiveutilitymea-suresbasedonthecovarianceofthedistributionThedeterminantisproportionaltothevolumeofthe.rectangularregionenclosingthecovarianceellipsoid.Hence,theinformationutilityfunctionforthisapproximationcanbechosenas:

Althoughthevolumeofthehighprobabilityregionseemstobeausefulmeasure,therearecasesinwhichthismeasureisunderestimatingtheresidualuncertainty.Incasethesmallestprincipalaxisshrinkstozero,thevolumeoftheuncertaintyellipsoidiszero,whiletheuncertaintiesalongtheremainingprincipalaxesmightremainlarge.

Analternativemeasureusingonlythecovarianceportionaltothecircumferencebetheoftracetherectangular,whichregionispro-ofadistributionwoulden-closingthecovarianceellipsoid.Hence,theinformationutil-ityfunctionwouldbe

FischerInformationMatrix

AnalternativemeasureofinformationistheFisherinforma-tionmatrixdefinedoveraclassoflikelihooddensities

,wherereferstothesequence

andtakesvaluesfromspace.Thecomponentofis

whereisthecomponentof.TheCramer-Raoboundstatesthattheerrorcovarianceofanysatisfies

unbiasedestimatorofItcanbeshownthatFisherinformationisrelatedtothesur-faceareaofthehighprobability[regionwhichisanotionofthe“size”oftheregionCover&Thomas1991].Similartothecovariance-basedmeasures,possibleformsoftheinformationutilityfunctionusingtheFisherinformationare

quantifyingtheinverseofthevolumeofhighprobabilityun-certaintyregion,or

However,calculationoftheFisherinformationmatrixre-quiresexplicitknowledgeofthedistribution.ForthecasewhenaGaussiandistributioncanapproximatetheposterior,theFisherinformationmatrixistheinverseoftheerrorco-variance:

IfadditionallytheMarkovassumptionforconsecutiveestima-tionstepsholds,wecanincrementallyupdatetheparameterestimateusingaKalmanfilterforlinearmodels.Inthiscase,theFisherinformationmatrixcanbeupdatedrecursivelyandindependent[ofmeasurementvaluesusingtheKalmanequa-tionsMutambara1998]:

(5)

whereand,aretheobservationmatrix,(2),andthe

measurementnoisecovarianceatestimationstep,respec-tively.

Fornonlinearsystems,apopularapproachistousetheex-tendedKalmanFilter,whichisalinearestimatorfornonlinearsystems,obtainedbylinearizationofthenonlinearstateandobservationequations.Inthiscase,theinformationmatrixcanberecursivelyupdatedby[Mutambara1998]:

(6)

whereistheJacobianofthemeasurementmodelin(1).Theinformationgaincanthenbemeasuredbythe“size”ofthisinformationmatrixsuchasthedeterminantortrace.

EntropyofEstimationUncertainty

Ifthedistributionoftheestimateishighlynon-Gaussian(e.g.,multi-modal),thenthecovarianceisapoorstatisticoftheuncertainty.Inthiscase,onepossibleutilitymeasureistheinformation-theoreticnotionofinformation:theentropyofarandomvariable.Foradiscreterandomvariabletakingval-uesinafiniteset,theShannonentropyisdefinedtobe

Foracontinuousrandomvariabletakingvaluesinacon-tinuousspace,theequivalentnotionisthedifferentialen-tropy

Theentropycanbeinterpretedasthelogofthevol-ume[ofthesetoftypicalvaluesforrandomvariableCover&Thomas1991].Whilethismeasurerelatestothevolumeofthehighprobabilityuncertaintyregion,thecom-putationoftheentropyrequiresknowledgeofthedistribu-tioneralandcanonlyandnot.Noteafunctionthatbeentropycomputationallyoftheisparticularafunctionintensivevaluesofthethatdistributionforagen-random

variable

takes.Furthermore,entropyisameasureofun-certaintywhichisinverselyproportionaltoournotionofin-formationutility,andwecandefinetheinformationutilityas

forwithprobabilitymassfunction

and

discreterandomvariableforacontinuousrandomvariablewithprobabilitydensity.Notethatthenotationfortheentropyhasbeenchangedabovefromtheoriginaldefinitiontoreflectthefactthaten-tropyisafunctionofdistributiononly.

VolumeofHighProbabilityRegion

Anothermeasurefornon-Gaussiandistributionscouldbethevolumeofthehighprobabilityregionofprobability

definedtobe

whereischosensothatitymeasureon,andrepresentsthe.correspondingisaprobabil-den-sity.Therelationbetweenthismeasureofthevolumeandentropy[isthatentropydoesnotarbitrarilypickavalueofCover&Thomas1991].Theinformationutilityfunctionforthisapproximationis

SensorGeometryBasedMeasures

Insomecases,theutilityofasensormeasurementisafunc-tionofthegeometriclocationofthesensorsonly.Forexam-ple,ifthesignalmodelassumestheform(4),thecontributionofeachindividualsensorintermsofthelikelihoodfunctionisanannuluscenteredaboutthepositionofthesensor.If,atagiventimestep,thecurrentestimateofthetargetlocationisaGaussianwithmeansensoralongthelongestandprincipalcovarianceaxisof,thethencovarianceintuitively,ellip-thesoidprovidesbetterdiscriminationonthelocationofthetar-getthanthoselocatedalongtheshortestprincipalaxisoftheuncertaintyellipsoid.Thisisduetothefactthateachampli-tudemeasurementprovidesadistanceconstraint(intheshapeoftheannulus)onthelocationofthetarget,andincorporatingthatconstraintamountstointersectingtheannuluswiththeel-lipsoid.Hence,wewouldgetlessuncertaintyabouttheposi-tionofthetargetifthemajoraxisoftheellipsoidwereperpen-diculartothetangentoftheannulus.Furthermore,itisdesir-ablethatthesensorbeclosertothemeanofthecurrentbeliefwhichaffectsthethicknessoftheannulusduetotheadditivenatureofthenoisetermin(4).

Inthisspecialcase,thegeometricmeasure

basedontheMahalanobisdistanceofthesensorunderconsid-erationtothecurrentpositionestimateisanappropriateutil-itymeasure.TheMahalanobisdistancemeasuresthedistancetothecenteroftheerrorellipsoid,normalizedbythecovari-ance.BychoosingthesensorwiththesmallestMaha-lanobisdistance,weareincorporatingtheamplitudemeasure-mentwhichwebelievewillprovidethemostreductionintheuncertaintyofthecurrentbelief.

Certainly,forothertypesofsensors,choosingthesensorbasedonminimizingMahalanobisdistanceisnotappropriate.Forexample,forsensorsmeasuringbearing(e.g.,bybeam-forming),thebestsensortochooseisthesensoralongtheshortestaxisoftheerrorellipsoidwhenthebearingsensorispointingtowardstheellipsoid.

2.4CompositeObjectiveFunction

Uptillnow,wehaveignoredthecommunicationcostoftrans-mittinginformationacrossthenetwork,andwehavealsoig-noredwhichsensoractuallyholdsthecurrentbelief.Inthere-mainderofthispaperwewillrefertothesensor,,whichholdsthecurrentbelief,astheleadernode.Thisnodemightactasarelaystationtotheuser,inwhichcasethebeliefresidesatthisnodeforanextendedtimeinterval,andallinformationhastotraveltothisleader.Inanotherscenario,thebeliefit-selftravelsthroughthenetwork,andnodesaredynamicallyassignedasleaders.Dependingonthenetworkarchitectureandthemeasurementtask,bothoramixtureofbothcasescanbeimplemented.Withoutlossofgenerality,weassumethattheleadernodetemporarilyholdsthebeliefstateandthatin-formationhastotravelacertaindistancethroughthenetworktobeincorporatedintothebeliefstate.

Inordertoincorporatetheactualcostofinformationtrans-port,theobjectivefunctionforsensorqueryingandroutingisafunctionofbothinformationutilityandcostofbandwidthandlatency.Thiscanbeexpressedbyacompositeobjective

function,

,oftheform(7)

whereityfunctionsdefinedinSectionisone2.2,ofandtheinformationmeasuresutil-thecostofthebandwidth,andlatencyofcommunicatinginfor-mationbetweenTheobjectivebalancessensoristomaximize

thecontributionandsensorfrom.Thetradeoffparameter

byselectingthetwoasensortermsinfrom(7).

theremainingsensorsby

Toillustratethisbyanexample,letusassumethattheun-certaintyinthepositionestimatecanbeapproximatedbyaGaussianprobabilitydistributionaboutappropriate,i.e.,informationutilityfunction.Astheattheoutlinedestimatedsensorabove,positionposition

anisgivenbytheMahalanobisdistanceforamplitude

measuringsensors.Ifweimposeanadditionalconstraintonthedistancebetweenthequeryingsensor()andthequeriedsensor(),thecompositeobjectivefunctioncomprisesthefol-lowingtwoterms:

(8)

(9)

3Algorithms

where

representsthepositionofthequeryingsensor.

2.5RepresentationandIncrementalUpdateof

BeliefState

Recallthatthebeliefisdefinedastheposteriorprobabilityoftherandomvariablegiventhemeasurements,,...,.Assumingdensitiesexist,thisisLetusassumethatapriori,isuniformlydistributed.

over

somecompactsubset

,andareconditionallyin-dependentwithrespectto.Then,thelikelihoodcanbefac-toredas

Andthebeliefisequivalenttothelikelihooduptosomemultiplicativeconstant:

whereisanormalizingconstantandthesecondequalityfol-lowsfromthefactthatisuniformlydistributedin.Duetothisequivalencebytheassumptionsabove,wecanusethetermbeliefandlikelihoodinterchangeably.Sinceitisdiffi-culttorepresenttheexactbeliefwhenthebeliefissomearbi-trarydensity,itisnecessarytoapproximatethebelief.Sincethebeliefneedstobecommunicatedtoremotesensorsincer-tainscenarios,acompactrepresentationisdesirable.Detailsofthetradeoffsbetweenparametricandnonparametricrepre-sentationswillbepostponeduntilSection5.

Anotherdesirablecharacteristicoftherepresentationofthebeliefisiftherepresentationcanbeincrementallyupdated.Undertheassumptionsabove,thebelief

canbecomputedfromthepreviousbeliefandthenewmeasurementby

whereisanormalizingconstant.

ForthespecialcaseofalinearsystemwithGaussiandistur-bances,thewell-knownKalmanfilterisanalgorithmwhichincrementallycomputesthemeanandcovarianceofthees-timate.SinceitisknownthattheestimateisGaussian,thefiltercomputestheoptimalestimates.Fornonlinearsystems,theextendedKalmanfilterhasbeensuccessfullyapplied.An-otherincrementalalgorithmisthesequentialMonteCarlomethod(alsoknownasparticlefilterorcondensationalgo-rithm)[Doucetetal.2000].Withoutgettingintothedetailsoftheseincrementaltechniques,thepointisthatsuchincre-mentalupdatemechanismsaredesirableinordertoeasilyfusenewmeasurementswiththecurrentbelief.Furthermore,inordertopassthebeliefaroundeasily,itisdesirablethattherepresentationofthebeliefbeacompactone.

Wedescribetwoclassesofalgorithms,onebasedonthefixedbeliefcarrierprotocolinwhichadesignatednodesuchasaclusterleaderholdsthebeliefstate,andanotherbasedonthedynamicbeliefcarrierprotocolinwhichthebeliefissucces-sivelyhandedofftosensornodesclosesttolocationswhere“useful”sensordataarebeinggenerated.Inthefirstcase,thequeryingnodeselectsoptimalsensorstorequestdatafromusingtheinformationutilitymeasures.Forexample,usingtheMahalanobisdistancemeasure,thequeryingnodecande-terminewhichnodecanprovidethemostusefulinformationwhilebalancingtheenergycost,withouttheneedtohavethesensordatafirst.Inthedynamiccase,thecurrentsensornodeupdatesthebeliefwithitsmeasurementandsendstheestima-tiontothenextneighborthatitdeterminescanbestimprovetheestimation.Althoughthealgorithmspresentedhereas-sumethereisasinglebeliefcarriernodeactiveatatime,thebasicideasalsoapplytoscenarioswheremultiplebeliefcar-rierscanbeactivesimultaneously.

3.1Information-DrivenSensorQuery

Thissectionoutlinesasensorselectionalgorithmbasedontheclusterleadertypeofdistributedprocessingprotocol.Al-thoughthealgorithmispresentedusingtheclusterleaderprotocol,theideasofguidingsensorselectionusinganinformation-drivencriterioncanbeequallywellsupportedbyothermethodssuchasthedirecteddiffusionrouting.Thede-scriptionofthealgorithmbelowwillexplicitlydiscusswhatinformationeachsensornodehas,eventhoughthispartofthealgorithmisauxiliarytothesensorselectionaspectoftheal-gorithm.Assumewehaveaclusterofsensorseachlabelledbyauniqueintegerin.Apriori,eachsensoronlyhasknowledgeofitsownposition.Figure2showstheflowchartofthisalgorithmwhichisidenticalforeverysensorinthecluster.Thealgorithmworksasfollows:1InitializationAssumingallsensorsaresynchronizedso

thattheyarerunningtheinitializationroutineatthesametime,thefirstcomputationistopickaleaderfromtheclusterofsensors.Dependingonhowtheleaderisdetermined,thesensorswillhavetocommunicateinfor-mation]abouttheirposition.Forexample,[Gaoetal.2001describesaclusteringalgorithmwithmobilecen-ters.Leavingoutthedetailsofthisleaderselection,letusassumethesensornodelabelledistheleader.Assumealsothattheleadernodehasknowledgeofcertainchar-acteristicsofthesensorsinthenetworksuchasthepositionsofthesensornodes.

2aFollowerNodesIfthesensornodeisnottheleader,then

thealgorithmfollowstheleftbranchinFigure2.Thesenodeswillwaitfortheleadernodetoquerythem,andiftheyarequeried,theywillprocesstheirmeasurementsandtransmitthequeriedinformationbacktotheleader.2bInitialSensorReadingIfthesensornodeistheleader,

thenthealgorithmfollowstherightbranchinFigure2.Whenatargetispresentintherangeofthesensorclus-ter,theclusterleaderwillbecomeactivated(e.g.theam-plitudereadingattheleadernodeisgreaterthansomethreshold).Theleadernodewillthen

1.calculatearepresentationofthebeliefstateownmeasurement,

,andwithits

2.begintokeeptrackofwhichsensors’measurementshavebeenincorporated.

intothebeliefstate,

Again,itisassumedthattheleadernodehasknowledge

ofthecharacteristics

ofallthesensorswithinthecluster.

3BeliefQualityTestIfthebeliefisgoodenough,basedon

somemeasureofgoodness,theleadernodeisfinishedprocessing.Otherwise,itwillcontinuewithsensorse-lection.4SensorSelectionBasedonthebeliefstate,andsensorcharacteristics,,pickasensornode,

fromwhichsatisfiessomeinformationcriterion.Saythatnodeis.Then,theleaderwillsendarequestforsensor’smeasurement,andwhentheleaderreceivestherequestedinformation,itwill

1.updatethebeliefstatewithtogetarepresentation

of

2.addtothesetofsensorswhosemeasurementshavealreadybeenincorporated

Now,gobacktostep3untilthebeliefstateisgoodenough.

Attheendofthisalgorithm,theleadernodecontainsalltheinformationaboutthebelieffromthesensornodesbyintelli-gentlyqueryingasubsetofthenodeswhichprovidethema-jorityoftheinformation.Thisreducesunnecessarypowerconsumptionbytransmittingonlythemostusefulinformationtotheleadernode.Thiscomputationcanbethoughtofasalo-calcomputationforthiscluster.Thebeliefstoredbytheleadercanthenbepassedupforprocessingathigherlevels.

Notethatthisalgorithmcontainsthegeneralideasdis-cussedearlierinthispaper.Insteps2band4,somerepre-sentationofthebeliefnode.ConsiderationsfortheparticularisrepresentationstoredattheleaderofthebeliefwasmentionedinSection2.5andisdiscussedindetailinSection5.Instep4,aninformationcriterionisusedtose-lectthenextsensor.DifferentmeasuresofinformationutilitywerediscussedinSection2.3,eachwiththeirowncomputa-tionalcomplexityissuesandnotionsofinformationcontent.

3.2ConstrainedAnisotropicDiffusionRouting

WhiletheInformation-DrivenSensorQueryalgorithmpro-videsuswithawayofselectingtheoptimalorderofsensors

toprovidemaximumincrementalinformationgain,itdoesnotspecificallydefinehowboth,thequeryandtheinformation,areroutedbetweenthequeryingandthequeriedsensor.Thissectionoutlinesanumberofalgorithmsthatexploitthecom-positeobjectivefunctiontodynamicallydeterminetheopti-malroutingpath.

StartInitialization1noleadernode?yes2aWaitforrequestWaitforactivationprompt2bCalculateinformationCalculateandusedinitialsensorsbeliefSendinformation3yesbeliefenough?goodnoSensorselectionalgorithm4SendinformationrequestWaitforinformationUpdatebeliefandusedsensorsFinishFigure2:Flowchartoftheinformation-drivensensorquery-ingalgorithmforeachsensor.

Globalknowledgeofsensorpositions

Ifthequeryingsensorhasglobalknowledgeofallsensorpo-sitionsinthenetwork,theroutingcanbedirectlyaddressedtothesensorclosesttotheoptimalposition.Theoptimalposi-tioncanbecomputedbythequeryingsensorbyevaluating

thecompositeobjectivefunction,

:(10)

Iftheunderlyingroutingprotocollayersupportsabsolutesen-soraddresses,thequeryingsensorcandirectlyrequestinfor-mationfromthesensorlocatedclosesttotheoptimumposi-tion.

Routingwithoutglobalknowledgeofsensorpositions

Heretheinformationqueryisdirectedbylocaldecisionsofindividualsensornodesandguidedintoregionssatisfyingtheconstraintsdefinedby.Notethatisincrementallyup-datedasthebeliefisupdatedalongtheroutingpath.Thelocaldecisionscanbebasedupondifferentcriteria:

1.Foreachsensorlocatedat,evaluatetheobjectivefunctionatthepositionsofthesensorswithinalo-calneighborhooddeterminedbythecommunicationdis-tance,andpickthesensorthatmaximizestheobjectivefunctionlocallywithintheneighborhood:

whereisthepositionofthecurrentroutingnode.2.Choosethenextroutingsensorinthedirectionofthegra-dientoftheobjectivefunction,

.Amongallsensorswithinthelocalcommunicationneighborhood,choosethesensorsuchthat

wheredenotesthepositionofthecurrentroutingnode.

3.Insteadoffollowingthelocalgradientsoftheobjectivefunctionthroughouttheroutingpath,thechosendirec-tionatanyhopcanbebiasedtowardsthedirectionaim-ingattheoptimumposition,.Thisvariationofthegradientascentalgorithmismostusefulinregionsofsmallgradientsoftheobjectivefunction,i.e.,wheretheobjectivefunctionisflat.Thedirectiontowardsthemin-imumoftheobjectivefunctioncanbefoundbyevaluat-ing(10)atanyroutingstep.Thisallowstolocallycom-putingthedirectiontowardstheoptimumposition,i.e.,

routingsensor.,wheredenotesthepositionofthecurrent

Theoptimaldirectiontowardsthenextsensorcanbechosenaccordingtoaweightedaverageofthegradientoftheobjectivefunctionandthedirectcon-nectionbetweenthecurrentsensorandtheoptimumpo-sition:

wheretheparametercanbechosen,forexample,asafunctionofthedistancebetweenthecurrentandtheop-timumsensorposition:mechanismallowsadaptingtheroutingdirection.Thisroutingtothedistancefromtheoptimumposition.Forlargedistancesitmightbebettertofollowthegradientoftheobjectivefunctionforthesteepestascent,i.e.,thefastestinforma-tiongain.Forsmalldistancesabouttheoptimumposi-tion,theobjectivefunctionisflatanditisfastertodi-rectlygotowardstheminimumthanfollowingthegra-dientascent.

Inordertolocallyevaluatetheobjectivefunctionanditsderivatives,thequeryneedstobetransmittedtogetherwithin-formationonthecurrentbeliefstate.Thisinformationshouldbeacompactrepresentationofthecurrentestimateanditsun-certainty,andhastoprovidecompleteinformationtoincre-mentallyupdatethebeliefstategivenlocalsensormeasure-ments.FortheaboveexampleofquantifyingtheinformationutilitybytheMahalanobisdistance,weneedtotransmitthetripletoftheestimatedtargetwithposition,thequery,whereisthepositionofisthecurrentthequery-stateingsensor,andtaintycovariance.

isthecurrentestimateofthepositionuncer-In-networkprocessing

Theabove-mentionedroutingmechanismscanbeusedtoes-tablisharoutingpathtowardsthepotentiallybestsensoralongwhichthemeasurementfromthesensorclosesttotheoptimalpositionisshippedback.Inthecaseofglobalknowledgeof

sensorpositions,theroutingpathisoptimal.Inthecaseoflo-calsensorknowledge,thepathisonlylocallyoptimalastheroutingalgorithmisagreedyalgorithm.Theestimateandtheestimationuncertaintycanbedynamicallyupdatedalongtheroutingpath.Themeasurementcanalsobeshippedbacktothequeryoriginatingnode.Sincetheinformationutilityob-jectivefunctionalongthepathismonotonicallyincreasing,theinformationprovidedbysubsequentsensorsisgettingin-crementallybettertowardstheglobaloptimum.Whenthein-formationiscontinuouslyshippedbacktothequeryingsen-sor,theinformationarrivinginsequentialorderprovidesanincrementalimprovementtotheestimate.Oncepredefinedestimationaccuracyisreached,thequeryingsensorcantermi-natethequeryevenifithasnotyetreachedtheoptimalsensorposition.Alternatively,insteadofshippinginformationbacktothequeryingsensor,theresultcouldbereadoutfromthenetworkatthesensorwheretheinformationresides.Incorporatetargetdynamicsintoquery

Formovingtargets,duringthelocaldynamicupdateofthebe-lievestateandtheobjectivefunction,amodelonthetargetdy-namicscanbeusedtopredictthepositionofthetargetinthenexttimestep.Thispredictedtargetpositionandtheassoci-ateduncertaintycanbeusedtodynamicallyaimtheinforma-tiondirectedqueryatfuturepositionstooptimallytrackthetarget.

4ExperimentalResults

Thissectiondescribestwosetsofexperimentsaimedatvali-datingtheIDSQandCARDalgorithmspresentedearlier.

4.1Information-DrivenSensorQuerying(IDSQ)

WewillapplythesensorselectionalgorithmpresentedintheSection3.1totheproblemofspatiallocalizationofastation-arytargetbasedonamplitudemeasurementsfromanetworkofsensors.

Themeasurementmodelforeachsensoris

(11)

for

where

theisintervaltheamplitudeofthetargetuniformlydistributed,

inistheunknowntargetposition,istheknownsensorposition,

istheknownattenuationcoefficient,and

zero-meanGaussiannoisewithvariance

iswhite,.

Thepurposeoftheseexperimentsistocomparedifferentsen-sorselectioncriteria.Issuesofcompactlyrepresentingthebe-liefmentsofstatethewillbepostponedtoSection5.3.Therepresentationfrombeliefthewillsensors.betheThus,historytheoftruethebeliefcollectedmeasure-andanystatisticsthereofcanbecalculated.

LetusfillinthedetailsofthealgorithmpresentedinSec-tion3.1.

1InitializationTherelevantcharacteristicsofeachsensor

are

whereisthepositionandisthevarianceofthead-ditivenoiseterm.Forsimplicity,theleaderischosentobetheonewhosepositionisclosesttothecentroidofthesensors,thatis,

Todeterminetheleader,allsensorscommunicatetheir

characteristicstoeachother.

2aFollowerNodesWhenafollowernodeisqueriedbythe

leader,itwilltransmittotheleader.

2bInitialSensorReadingFortheexperiments,theleader

nodewasactivatedwhenitsamplitudereadingsatisfied

Thisessentiallymeanstheleadernodebecomesacti-vatedwhenthetargetislessthansomegivendistanceawayfromtheleadernode,assumingthereisnoothersoundsourcepresent.Theleaderwillthen

1.storeitsamplitudevalue,whichisitsrepre-sentationofthebelief,and

2.keeptrackofwhichsensors’measurementshavebeenincorporatedintothebeliefstate,

3BeliefQualityTestInthegeneralcase,atesttodetermine

whenthequalityofthebeliefisgoodenoughisneededhere;however,forthepurposesoftheexperiments,wewillcontinuetoincorporatemeasurementsuntilallsen-sorsintheclusterhavebeenincorporated.Allclustersintheexperimentsconsistofsensors.

4SensorSelectionTheinformationwhichisutilizedtocom-putethenextsensortoqueryisthebeliefstateandsen-sorcharacteristics

.Wehavefourdifferentcrite-riaforchoosingthenextsensor:

ANearestNeighborDataDiffusion

BMahalanobisdistanceFirst,calculatethemeanand

covarianceofthebeliefstate:

andchooseby

CMaximumlikelihoodThisisanadhocgeneraliza-tionoftheMahalanobisdistancecriterionfordis-tributionsthataremulti-modal.ForthespecialcasewhenthetruedistributionisGaussian,thiscriterioncorrespondsexactlywiththeMahalanobisdistancecriterion.

DBestFeasibleRegionThisisanuncomputable

methodsincethisrequiresknowledgeofthesensorvalueinordertodeterminethesensortouse.However,thishasbeenimplementedtoserveasabasisforcomparisonoftheothercriteria.

where

Viewingthe’sasavectorofindependentnormalvariableswithstandarddeviation,isthestan-dardstances.thendeviationcontrolsofThesetthethisofmaximummultivariateenergyrandomvariable.isthesetofofthetargetnoiseposi-in-tionswhichcouldhavegeneratedthemeasurements

Afternodehasbeendetermined,arequesttransmittedtonode,andreceived,theleadernodewill

1.updatetherepresentationofthebeliefstate

2.updatethesetofusedsensors

Forthesimulations,.Thesensorwevariancehavechosenissetto,whichand

is

aboutofthesignalamplitudewhentheamplitudeofthetargetisandthetargetisatadistanceofunitsfromthesensor.ischosentobesincethisvaluecoversofallpossiblenoiseinstances.Forthefirstsimulation,wassettowhichconsidersreflectionsfromthegroundsurface.issettoforthesecondsimulationwhichistheattenuationexponentinfreespacewithnoreflectionsorabsorption.Theshapeoftion;however,uncertaintyalgorithmtheforcomparativeregionisdifferentselectionperformancesensitivetodifferentcriteriaofgenerallythesensorchoicesofbehaveselec-similarlyfordifferent.

Notethathereweusethestringconcatenationoperatorasa

shorthandtodenotethebeliefupdatewithoutgettingintodetailsofspecificupdatealgorithms.MorediscussiononthiscanbefoundlaterinSection5.

Thefirstsimulationisapedagogicalexampletoillustratetheusefulnessofincorporatingasensorselectionalgorithm

intothesensornetwork.Figure3showsthelayoutof

mi-crophones,ofwhichareinalineararrayandonewhichisperpendicularlyofffromtheleadernodeofthelineararray.Theonemicrophonenotinthelineararrayisplacedsothatitisfartherfromtheleadernodethanthefarthestmicrophoneinthelineararray.Withsensormeasurementsgeneratedbyastationaryobjectinthemiddleofthesensornetwork,sensorselectioncriteriaAandBarecompared.Thedifferenceinthetworunsistheorderinwhichthesensors’measurementsareincorporatedintothebelief.

Figure4showsaplotofthenumberofsensorsincorporatedversusthelogarithmofthedeterminantoftheerrorcovarianceofthebeliefstate.Indeed,thevolumeoftheerrorcovarianceunderselectioncriterionBislessthanthevolumeoftheerrorcovarianceunderselectioncriterionAforthesamenumberofsensors,exceptduringtheinitialphaseorafterallthesensorshavebeenaccountedfor.

AplotoftheamountofthecommunicationdistanceversusthenumberofsensorsincorporatedisshowninFigure5.Cer-tainly,thecurveforselectioncriterionAisthelowerboundforanyothercriterion.Aoptimizesthenetworktousetheminimumamountofcommunicationenergywhenincorporat-ingsensorinformation;however,itlargelyignorestheinfor-mationcontentofthesesensors.Amoreinformativeinterpre-tationofthefigureistocomparetheamountofenergyittakesforcriterionAandcriterionBtoachievethesamelevelofac-curacy.ExaminingFigure6,weseethatundercriterion,inorderforthelogdeterminantofthecovariancevaluetobelessthan,criterionrequiresallsensorstobetasked.Ontheotherhand,criterionrequiresonlysensorstobetasked.Now,comparingthetotalcommunicationdistanceforthislevelofaccuracyfromFigure7,weseethatcriterionre-quireslessthanunitsofcommunicationdistancefortask-ingsensorsasopposedtonearlyunitsofcommunicationdistancefortaskingallsensors.Indeed,foragivenlevelofaccuracy,BgenerallyrequireslesscommunicationdistancethanA.Withthiscomparison,criterionBperformsbetter.Theabovesimulationwastherunofaspecificlayoutofthesensors,andthestrikingimprovementoftheerrorwaslargelyduetothefactthatmostofthesensorswereinalineararray.Thus,thenextsimulationwillexplorewhichonedoesbetterontheaveragewithrandomlyplacedsensors.

MicrophonesareplaceduniformlyinagivensquareregionasshowninFigure8.Thetargetisplacedinthemiddleofthesquareregionandgivenarandomamplitude.Then,thesensoralgorithmforthedifferentsensorselectioncriteriade-scribedabovewasrunforruns.Figure9showsacom-parisonbetweenselectioncriterionAandB.Therearethreesegmentineachbar.Thebottomsegmentrepresentstheper-centageofrunswhentheerrorforBwasstrictlylessthantheerrorforAaftersensorshavebeenincorporated.Themiddlerepresentsatie.TheuppersegmentrepresentsthepercentageofrunswhentheerrorforBwaslargerthantheerrorforA.Sincethebottomsegmentislargerthantheupperone(exceptfortheinitialandfinalcases),thisshowsBperformsbetterthanAonaverage.

Figure10andFigure11showcomparisonsofsensorcrite-40200−20−40−60−40−20020406080Figure3:Layoutofall-but-one-colinearsensors(squares)andtarget(asterisk).Theleadernodeisdenotedbyan.

rionCandDversusB.TheperformanceofCiscomparabletoB,andasexpected,DisbetterthanB.ThereasonDisnotalwaysbetterthanBisbecausethethbestsensorischosenincrementallywiththefirstsensorsfixedfrombefore.

Fixingtheprevious

sensorswhenchoosingthethsen-soriscertainlysuboptimaltochoosingsensorsallatoncetomaximizetheinformationcontentofthebelief.

4.2ConstrainedAnisotropicDiffusionRouting

(CADR)

Figure12illustratestheideaofConstrainedAnisotropicDif-fusionRouting(CADR)bynumericalsimulationsofadhocsensornetworksofrandomlyplacedsensors.Theobjectivefunctionwaschosenaccordingto(7),withtheinformationutilityandenergycosttermsaccordingto(8)and(9),respec-tively.Thecurrenttargetposition,werearbitrarilychosenandremained,fixedanditsforuncertainty,therun,i.e.,no,incrementalupdateofthebeliefstatehasbeenimplemented.Thevalueoftheobjectivefunctionacrossthesensornetworkisshownasacontourplotwithpeaksoftheobjectivefunctionlocatedatthecenterofellipses.Thecircleindicatedby’?’depictsthepositionofthequeryingsensor(queryorigin),andthecircleindicatedby’T’depictstheestimatedtargetposi-tion,depicted.Theas90-percentilecurrentuncertaintyellipsoidintheenclosingpositiontheestimate,position’T’.,isThegoaloftheConstrainedAnisotropicDiffusionRoutingistoguidethequeryascloseaspossibletowardsthemaxi-mumoftheobjectivefunction,followingthelocalgradientstomaximizedistancerepresentsincrementalfromthequeryingmaximuminformationsensorinformationgain.Whilethecaseof

(andhencegain,theenergyignoringcost),the

thecaseminimizestheenergycost,ignoringtheinfor-mationgain.Forotherchoicesof

,thecompositeobjectivefunctionrepresentsatradeoffbetweeninformationgainandenergycost.

1210ecnairav8Criterion A oC fo tnanim6reteD goL4Criterion B (IDSQ)202468101214Number of sensors usedFigure4:DeterminantoftheerrorcovarianceforselectioncriteriaAandB(IDSQ)fortheall-but-one-colinearsensorlayout.

450400350ecnatsid300 noitacin250Criterion B (IDSQ)ummoc200 latoT150Criterion A1005002468101214Number of sensors usedFigure5:Totalcommunicationdistancevs.thenumberofsensorsqueriedforselectioncriteriaAandB(IDSQ)fortheall-but-one-colinearsensorlayout.

1210ecnaiCriterion A rav8oC fo tnanim6reteD goL4Criterion B (IDSQ)202468101214Number of sensors usedFigure6:DeterminantoftheerrorcovarianceforselectioncriteriaAandB(IDSQ)fortheall-but-one-colinearsensorlayout.AtaskssensorswhileBtaskssensorstobebelowanerrorthresholdof5units.

450400350ecnatsid300 noitacin250Criterion B (IDSQ)ummoc200 latoT150Criterion A1005002468101214Number of sensors usedFigure7:Totalcommunicationdistancevs.thenumberofsensorsqueriedforselectioncriteriaAandB(IDSQ)fortheall-but-one-colinearsensorlayout.Forachievingthesamethresholdoftheerror,AtaskssensorsandusesnearlyunitsofcommunicationdistancewhereasBtaskssensorsanduseslessthanunitsofcommunicationdistance.

10090807060504030201000102030405060708090100Figure8:Layoutofsevenrandomlyplacedsensors(squares)withtargetinthemiddle(asterisk).

1.5B strictly worse than AB same as AB strictly better than A1snur fo egatnecreP0.501234567Number of sensors usedFigure9:PercentageofrunswhereBperformsbetterthanAforsevenrandomlyplacedsensors.

1.5B strictly worse than CB same as CB strictly better than C1snur fo egatnecreP0.501234567Number of sensors usedFigure10:PercentageofrunswhereBperformsbetterthanCforsevenrandomlyplacedsensors.

1.5B strictly worse than DB same as DB strictly better than D1snur fo egatnecreP0.501234567Number of sensors usedFigure11:PercentageofrunswhereBperformsbetterthanDforsevenrandomlyplacedsensors.

Figure12showshowvariationofthetradeoffparametermorphstheshapeoftheobjectivefunction.Asdecreasesfrom1to0,thepeaklocationmovesfrombeingcenteredatthepredictedtargetposition()tothepositionofthequeryingsensor(=0);atthesametime,thecontourschangefrombeingelongated,shapedaccordingtotheuncertaintyel-lipsoidrepresentedbytheestimatedcovariance,towardsisotropic.Anotherinterestingaspectofthecombinedobjec-tivefunctionisthatthespatialpositionofitsminimumdoesnotshiftlinearlybetweentheestimatedtargetposition’T’andthequeryorigin’?’,withvarying.Thiscanbeobservedinthecaseof,wheretheminimumislocatedoffthelineconnecting’T’and’?’.

InallthreecasesshowninFigure12theestimatedtargetpositionandresidualuncertaintyarethesame.Variationsinshapeandoffsetoftheobjectivefunctionarecausedbyvaria-tionsofthetradeoffparameter.Inordertovisualizehowthequeryisroutedtowardsthemaximumoftheobjectivefunc-tionbylocaldecisions,boththeestimatedpositionasitsuncertainty,areleftunalteredduringtherouting.aswellItisimportanttonotethatincrementalbeliefupdateduringtheroutingbyin-networkprocessingwoulddynamicallychangeboththeshapeandtheoffsetoftheobjectivefunctionaccord-ingtotheupdatedvaluesofroutingpath.Astheupdatedvaluesandofateverynodealongthetothenextnode,allroutingdecisionsareandstillmadearepassedlocally.onHence,theplottedobjectivefunctionrepresentsasnapshotoftheobjectivefunctionthatanactiveroutingnodelocallyeval-uatesatagiventimestep,asopposedtotheoverlaidroutingpathwhichillustratesthetemporalevolutionofthemulti-hoprouting.

TheroutinginFigure12wasterminatedafterreachingaspatialregionwherethevalueoftheobjectivefunctionisaboveapresetthreshold.Inrealapplications,theterminationcriterioncanbechosenbaseduponothercriteria,suchasathresholdontheresidualuncertaintyorpresettimeoutsthatarepassedalongwiththequery.

Thesmallcirclessurroundingthedotsalongtheroutingpathillustratethesubsetofsensorstheroutingsensors(onthepath)considerduringsensorselection.Amongthesesensorstheonesthatlocallymaximizetheobjectivefunctionhavebeenselectedasthenextroutingnodes.Thefractionofse-lectednodesamongallnodesindicatestheenergysavingsbyusingCADR,asopposedtothetotalenergycostoffloodingthenetwork.

5Discussion

Thissectionaddressesseveralissuesconcerningpracticalim-plementationsoftheIDSQ/CADRalgorithms.

5.1OtherNetworkRoutingSupportfor

IDSQ/CADR

WehavedescribedhowCADRcaneffectivelysupportintel-ligentsensorqueryingsuchasIDSQ.Existingdatadiffusionprotocolssuchas[Intanagonwiwatetal.2000]couldbeusedtoimplementIDSQ/CADR.Forsimplicity,wewillcontinuetousethelocalizationofasinglestationarytargetasanexam-ple.

?1 T ?1 T ?1 TFigure12:ConstrainedAnisotropicDiffusionRoutingparametersensors,.Fromandtopvaryingtobottom:information,vs.cost,tradeoff

for.Forcomparison,thepositionestimateofthetarget,’T’,andthepositionofthequeryorigin,’?’,arefixedinallexamples.

Asdescribedearlier,inaclusterbasednetworkorganiza-tionauserqueryentersintothenetworkatthenodecalledqueryproxy,oftentheclusterheaditself.Theproxyperformsestimationoftargetstates,usinginformationfromitssensorsaswellassensorsfromthenodesinthecluster.Ifatargetmovesoutoftherangeofthesensorsinthecluster,thenahand-offneedstotakeplacesoastogetthecurrentstatees-timationtothenextclusterwherethetargetismostlylikelygoingtobeat.

UsingtheinformationutilitymeasuresuchastheMaha-lanobisdistancedescribedearlier,thequeryproxyselectsanodeintheclusterthatcanbestimprovethecurrentbeliefstate.SincethecomputationofMahalanobisdistanceonlyre-quirestheknowledgeofthecurrentbeliefstateandtheloca-tionofasensor,thiscanbeaccomplishedattheproxynodeifthenodehaslocationinformationforallthesensorsinthecluster.Torequestthedatafromtheselectedsensor,theproxycanperformapoint-to-pointcommunicationusingtheaddressoftheselectedsensornode,ortheproxycanturnononlytheselectednode(andwhenanodeisturnedonitsendsmeasure-mentbacktotheproxybydefault).

Inthemoregeneralcase,thenodeselectionmustbebasedonthreepiecesofinformation:beliefstate(e.g.,mean,covari-anceforaGaussiandistribution),sensorlocation,andmea-surementatthesensor.Weexploitthefiltermechanismavail-ableinthedirecteddiffusionroutingprotocol.Eachnodehasafilterthatactsoninformationitreceivesfromaneighboraswellasitsownmeasurementsignalanddecidestoeithersendbackthesignal(traversingtheinformationdiffusionroutesbacktotheproxyviacallbacks),orchangethedataroutinggradientsithasalreadysetup,orforwardtheinformationitreceivestoachosennextnode.

Inonescenario,thequeryproxybroadcastsitscurrentbe-liefstatetoallnodeswithinitsinfluenceregion.Somenodesmayrequiremorethanasinglehoptoreach,usingforex-ampleanunderlyingdiffusionroutingtree.Therearetwocasesinwhichthesensorselectioncanbeaccomplishedin-network:(1)Eachsensornodethatreceivesthebroadcastedbeliefstatecomputesaqualityfactorindicatinghowwellthecurrentmeasurementcanimprovethecurrentestimateusingmeasuressuchasvolumeoferrorcovariance,andthosethatmeetcertainthresholdsendstheirdataback.Forexample,ev-erynodethatcanreducetheestimateuncertaintyby50%ormoresendsdatabacktotheproxy.(2)Eachnodesendsatu-pledata,backtotheproxy,traversingthediffusionrout-ingtree.Ateachjunctionofthetreewheremultiplemessagescollide,onlythemessagewithmaxgetsforwardedtothenextnode.Thiswaythequeryproxyreceivesonlythebestmeasurement.Alternatively,inboth(1)and(2),inadditiontoin-networksensorselection,theestimationcanbeaccom-plishedin-network.For[example,usingtheindependentlike-lihoodpoolprincipleManyika&Durrant-Whyte](assumingconditionedontargetlocationandamplitude),thenlocalesti-matescanbecombinedincrementallywhensignalsflowbacktotheproxy.However,thishastobalancewiththeamountofinformationtotransmitsinceinsomecasestheencodingofthebeliefstatemighttakemorebitsthanthemeasurementitself(e.g.inthenon-parametricform).

5.2BeliefRepresentation

Thereareseveralwaystoapproximateanarbitrarybeliefstate:

1.Approximatebyafamilyofdistributionswhichisparameterizablebyafinitedimensionalparam-,eter,wheredistributionsover.AnexampleisthesetofofallisprobabilitythefamilyofGaussiandistributionsonwherethefinitedimen-sionalparameterspaceincludesthemeanandcovari-anceoftheGaussiandistributions.

2.Approximatebypointsamples.Thisisabruteforcemethodofapproximatingthedensityofacontinuousran-domvariablebyaprobabilitymassfunctionwithsupport

inafinitenumberofpointsof.Let

finitesetofpointsof.Then,wecanapproximatebesomethedensitybyaPMFwithmassateachpointoftionaltothedensityatthatpoint.Twoexamplespropor-ofthisapproximationarediscretizingthesubsetofbyagridandtheparticlefilterapproximationofdistributions.Avariantofthispointsamplehistogramandassigntypeaprobabilityapproach.

valueapproximationtoeachregion;istopartitionthisisaWeshouldmentionthatthefirstapproximationisreferredtoasaparametricapproximationwhereasthesecondapprox-imationisreferredtoasanonparametricapproximation.Al-thoughthetermsparametricandnonparametricmayseemtorefertotwocompletelydifferentwaysofapproximation,wewouldliketopointoutthatthedistinctionisnotsoclear.Inthesecondcase,ifweconsiderthepointsofsociatedprobabilityvalueasthesetofallparameterswiththeir,thenas-wecanconsiderthesecondapproximationaparametricap-proachaswell.Thedistinctionbetweenaparametricapprox-imationandanonparametriconedependsonwhatwemeanbytheterm“parameter”.

5.3ImpactofChoiceofRepresentation

Therepresentationofthebeliefwillimpacttheamountofcommunicationpowerconsumedwhensendingthebeliefstatetoaremotesensor.Ifwemustpassthebelieftoaremotesensor,wearefacedwiththefollowingtradeoff:

1.Representingthetruebeliefbyanonparametricapprox-imationwillresultinamoreaccurateapproximationofthebeliefatthecostofmoretransmittedbits.

2.Representingthetruebeliefbyaparametricapproxi-mationwithrelativelyfewparameterswillresultinapoorapproximationofthebeliefbutwiththebenefitthatfewerbitsneedtobetransmitted.

Theabovetwotradeoffsaregeneralstatements.However,thereisanotherfactorthatisunderlyingthetradeoffsabove.Thatfactorisbackgroundknowledgeofthepossiblesetofbe-liefs.Letuselaborate.

Parametriccase(e.g.Gaussianapproximation)

Thereasonweareabletotransmitrelativelyfewbitsundertheparametriccaseisthatitisassumedthatallsensorsareawareoftheparametricclassofbeliefs.Knowledgeofthisparamet-ricclassisthebackgroundknowledgewhichallowsforthe

smallnumberofbitstobetransmitted.InthecasewhereweapproximatethebeliefbyaGaussian,allsensorsknowthatthebeliefisrepresentedbytheparametricclassofGaussiandistributions.Hence,onlythemeanandcovarianceneedtobetransmitted.TheKalmanfilterequationsarerecursiveupdateequationsofthemeanandcovarianceoftheGaussiandistri-bution.

Nonparametriccase(e.g.discretization)

Forthenonparametriccase,thereisnoconstant-sizeparam-eterizationofthebeliefingeneral.However,assumingthatthemodelofthemeasurementsisknown,wecanparameter-izethebeliefbystoringahistoryofallmeasurements.Inthis

case,theparameterspaceis

,thesetofallfinitelengthstringsofrealnumbers.Ifistheparameterforthelikelihoodfunction

thentheparameterfor

isupdatedfrom

by

where“”denotesstringconcatenation.Thisupdateequationistrivialandsuffersfromincreasingdimensionality.Butifwearegivenknowledgeofahighlynonlinearmodelforthemea-surementsoftheunknownvariable,itmaybethatcollectingahistoryofthemeasurementsisamorecompactrepresenta-tioninitially.Toelaborate,aGaussianapproximationofthelikelihoodfunction

wouldrequirestoringthemeanandthecovariancewhichforthisparticularcasewouldrequire2realnumbersforthemeanand3realnumbersforthecovarianceforatotalof5realnum-bers.However,tostoretheexactlikelihood,weonlyrequire2realnumberscorrespondingtoand,withtheimplicitbackgroundknowledgeoftheformofthelikelihoodfunction.If,forexample,itturnsoutthataftersomenumberofmea-surements,thetruelikelihoodfunctionbecomesunimodaland,hence,canbeapproximatedwellbyaGaussian,thismo-tivatesahybridrepresentation:

1.Initially,thebeliefisparameterizedbyahistoryofmea-surements.

2.Oncethebeliefbeginstolookunimodal,wewillapprox-imatethebeliefbyaGaussianand,hence,theparameter-izationofthebeliefincludesthemeanandcovariance.SinceaGaussianapproximationispoorinitially,thecostofmaintainingahistoryofmeasurementsisjustified.OncetheGaussianapproximationbecomesreasonable,wecanconverttosucharepresentationandcontroltheparameterdimension-ality.

6RelatedWork

Researchersinroboticshavedevelopedanumberofalgo-rithmsforquantifyingandestimatinguncertaintiesinsensingandestimationapplications.Inparticular,[Nakamura1992]

usesageometriccharacterizationofuncertaintyintermsoferrorellipsoidsanddevelopedaKalman-filterlikeincremen-talestimationalgorithm,assumingGaussiandistributions,forminimizingtheuncertaintyellipsoidsforarobotic]positiones-timationproblem.[Manyika&Durrant-Whyteand[Mutam-bara1998]developedageneralinformationfilterformulationfortheincrementalestimationproblem,similartotheKalmanfilter.IDSQdiffersfromtheseinthatIDSQusesasetofin-formationcriteriatoselectwhichsensorstogetdatafromandthenincrementallycombinethedata.ThebeliefupdateinIDSQcoulduseeitheraninformationfilteroramoregeneralnon-GaussiantechniquesuchasthesequentialMonteCarlomethod(alsoknownasparticlefilter)[Doucetetal.2000].IDSQisrelatedtoworkonactivevisionoractivetest-ingincomputervisionresearch.[Geman&Jedynak1996]de-scribedamethodforselectingtestsusinganentropymeasureonthecurrentsetofhypothesesforasatelliteimagebasedroadtrackingproblem.Intheirmethod,atestisselectedifitminimizestheresidualuncertaintyaboutthelocationoftheroad,usinganonlineimplementationofadecisiontreealgo-rithm.Whilesharingthesamephilosophyofminimizingun-certaintyinanestimationviaactivetestselection,IDSQmod-elstheuncertaintyinageometricsensesothatactivesensorselectioncanbeguidedusingthespatialconfigurationofthesensors.

DistributedKalmanfilterexploitsthefactthatmeasure-mentsareincorporatedintotheestimatebyaweightedlin-earcombinationofestimateandmeasurement[Mutambara1998].Hence,estimatesbasedondifferentclustersofmea-surementscanbecombinedlinearlytocreateanestimatebasedonallthemeasurements.CADRworksbasedonthisin-crementalnatureofincorporatingmeasurementsintotheesti-mate,butunlikethedistributedKalmanfilter,CADRdiscrim-inatesbetweenusefulmeasurementsandredundantmeasure-mentstominimizeunnecessarycommunicationcosts.

WirelesslynetworkedsensorsoftendeployamultihopRFcommunicationstrategytoconserveenergy[Pottie&Kaiser2000].Recentworkindatadiffusionroutingandmoregenerallyenergy-awarecommunicationattemptstominimizepowerconsumptionbyexploitingnetworkparameterssuchastopologiesornodepowerlevels.[Intanagonwiwatetal.2000]describesadirecteddiffusionroutingprotocolthatusesdiffusioncoupledwithreinforcementtoestablishshort-estpathsbetweendatasourcesanddatasinksinapublish-subscribeframework.Thediffusionproceedsinanisotropicfashion,reachingnearestneighborsfirst.In[Sohrabi2000],sensorsinanetworkself-organizebasedonsignal-noise-ratiostoperformcooperativeprocessingtasks.Energycostfordatatransmissionisexplicitlyusedtoplanpathsforsend-ingdata.Similarly,[Singhetal1998]determinesminimummetricpathsthatminimizeenergyperpacketaswellasweigh-ingtheenergyconsumptionbyenergyreserveonanode.Thiswaycommunicationtrafficcanbesteeredawayfromlow-energynodes.Bycomparison,CADRusesbothcommunica-tionorenergycost(e.g.expressedasafunctionofthedis-tance)andinformationutilitytoanisotropicallydiffusedata,generalizingthecostmodelusedbythediffusionroutingpro-tocol.CADRallowsestimationtoeithercenterataqueryproxynodeordynamicallymigrateamongnodes.Inanother

relatedwork,[Brooksetal.2001]usespredictionsfromtrack-ingtoinvokesensornodeswithinterestinaparticulardirec-tionorregion.Incontrast,IDSQ/CADRusesthemoregen-eralinformationutilitymeasureandcostfunctiontolocallyselectthebestsensorstoqueryorroutedatato.

IDSQ/CADRiscloselyrelatedto[Byers&Nasser2000]thatusesautilityfunctiontooptimizenodeselection.Intheirformulation,theutilityfunctionmappingasetofnodestorealvaluesissimplyasteporsigmoidfunction,withoutexplicitmodelingofnetworkspatialconfiguration.IDSQ/CADR,incontrast,modelstheuncertaintyfromageneralinformation-theoreticformulationandderivesspecificformsoftheutilityfunctionsforlocalizationandtrackingproblemssothatrout-ingalgorithmscanexploitthespatialconfigurationofthenet-worktooptimizenodeselection.

7Conclusion

Thispaperpresentsanewapproachtodistributed,collabo-rativesignalprocessinginheterogeneousadhocsensornet-works.Thetwokeyideasthatareoutlinedinthispaperareinformation-drivensensorquerying(IDSQ)andconstrainedanisotropicdiffusionrouting(CADR).Introducinganinfor-mationutilitymeasureallowstodynamicallyselectthebestsubsetofsensorsamongallpossiblesensorswithinthesen-sornetwork.

Thesensorselectionisbaseduponconstraintsontheinfor-mationgain,subjecttoadditionalconstraintsonenergycostandinter-nodecommunicationdistance.Defininganincre-mentalalgorithmfortheestimationproblem,andcommuni-catingacompactrepresentationofthebeliefstatetogetherwiththesensorquery,allowstoincrementallyupdatethebe-liefduringtheroutingofthequery.Furthermore,allroutingdecisionsarebaseduponlocalcomputationsintheroutingnodesexploitingthepropagatedbeliefstate.

Wepresentedexperimentalresultsonsimulatedsensornet-worksforthetaskoflocalizationofstationarytargetsgivenasoundamplitudebasedmeasurementmodel.Theresultsshowthattheinformation-drivensensorqueriesproposedinthispaperaremoreenergyefficient,havelowerlatency,andprovidedistributedanytimealgorithmstomitigatetheriskoflink/nodefailures.

Acknowledgment

ThisworkissupportedinpartbytheDefenseAdvancedResearchProjectsAgency(DARPA)undercontractnumberF30602-00-C-0139throughtheSensorInformationTechnol-ogyProgram.Theviewsandconclusionscontainedhereinarethoseoftheauthorsandshouldnotbeinterpretedasrepresent-ingtheofficialpolicies,eitherexpressedorimplied,oftheDe-fenseAdvancedResearchProjectsAgencyortheUSGovern-ment.

References

[Brooksetal.2001]R.R.Brooks,C.Griffin,andD.S.Fried-lander,Self-organizeddistributedsensornetworkentitytracking,thisissue.

[Byers&Nasser2000]J.ByersandG.Nasser,Utility-BasedDecision-MakinginWirelessSensorNetworks(Extended

Abstract),ProceedingsofIEEEMobiHOC2000,Boston,MA,August2000.

[Cover&Thomas1991]T.M.CoverandJ.A.Thomas,Ele-mentsofInformationTheory.JohnWiley&Sons,Inc.,NewYork,NY,1991.[Doucetetal.2000]A.Doucet,J.F.G.deFreitas,andN.J.Gordon.SequentialMonte-CarloMethodsinPractice.Springer-Verlag,2000.[Estrinetal.1999]D.Estrin,R.Govindan,J.Heidemann,S.Kumar,NextCenturyChallenges:scalablecoordinationinsensornetworks.InProceedingsoftheFifthAnnualInter-nationalConferenceonMobileComputingandNetworks(MobiCOM’99),Seattle,Washington,August1999.[Gaoetal.2001]J.Gao,L.J.Guibas,J.Hershburger,L.Zhang,andA.Zhu.DiscreteMobileCenters.Proc.of17thSymposiumonComputationalGeometry,TuftsUniver-sity,MA,June,2001.[Geman&Jedynak1996]D.GemanandB.Jedynak,Anac-tivetestingmodelfortrackingroadsfromsatelliteimages,IEEETrans.PatternAnal.Mach.Intell.,18,1-14,1996.[Huang&Garcia-Molina2001]Y.HuangandH.Garcia-Molina,Publish/SubscribeinaMobileEnvironment.Proc.MobiDE-01,2001.[Intanagonwiwatetal.2000]C.Intanagonwiwat,R.Govin-dan,D.Estrin,Directeddiffusion:ascalableandrobustcommunicationparadigmforsensornetworks.InProceed-ingsoftheSixthAnnualInternationalConferenceonMo-bileComputingandNetworks(MobiCOM2000),Boston,Massachusetts,August2000.[Manyika&Durrant-Whyte]J.ManyikaandH.Durrant-Whyte,Datafusionandsensormanagement:adecen-tralizedinformation-theoreticapproach.EllisHorwood,1994.[Mutambara1998]A.G.O.Mutambara,Decentralizedesti-mationandcontrolformulti-sensorsystems.CRCPress,1998.[Nakamura1992]Y.Nakamura,GeometricFusion:Mini-mizinguncertaintyellipsoidvolumes.InDataFusioninRoboticsandMachineIntelligence,M.A.AbidiandR.C.Conzalez(eds),AcademicPress,1992.[Pottie&Kaiser2000]G.J.PottieandW.J.Kaiser,“Wirelessintegratednetworksensors.”Comm.ACM,43(5):51-58,May2000.[Singhetal1998]S.Singh,M.Woo,andC.S.Raghaven-dra,Power-awareroutinginmobileadhocnetworks.Proc.MOBICOM’98,1998.[Sohrabi2000]K.Sohrabi,J.Gao,V.Ailawadhi,andG.J.Pottie,Protocolsforself-organizationofawirelesssensornetwork.IEEEPersonalCommunications,7(5):16-27,Oct2000.

A

MeasurementLikelihoodFunctionDerivation

Basedonthemeasurementmodel(11)ofSection4,aclosedformexpressionforthelikelihoodcanbederivedas

where

and

Assumingthat,,,,andaregivenapriori,

thelikelihoodfunction(viewedasafunctionof)isparam-eterizedbythemeasurementvalues.