Approximate distributed Kalman filtering in sensor networks with quantifiable performance

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

DISTRIBUTEDKALMANFILTERINGINSENSORNETWORKSWITHQUANTIFIABLE

PERFORMANCE

DemetriP.Spanos,RezaOlfati-Saber,RichardM.Murray

ControlandDynamicalSystemsMC107-81

CaliforniaInstituteofTechnology1200EastCaliforniaBlvd.Pasadena,CA91125

{demetri,olfati,murray}@cds.caltech.edu

ABSTRACT

Positions and Estimates

True Positions and Centralized Kalman Filter

0.60.40.20 0.2 0.4 0.6 0.8

200

400600Time Index

800

1000

Time Index

WeanalyzetheperformanceofadistributedKalman l-terproposedinrecentworkondistributeddynamicalsys-tems.Thisapproachtodistributedestimationisnovelinthatitadmitsasystematicanalysisofitsperformanceasvar-iousnetworkquantitiessuchasconnectiondensity,topol-ogy,andbandwidtharevaried.Ourmaincontributionisafrequency-domaincharacterizationofthedistributedesti-mator’sperformance;thisisquanti edintermsofaspecialmatrixassociatedwiththeconnectiontopologycalledthegraphLaplacian,andalsotherateofmessageexchangebe-tweenimmediateneighborsinthecommunicationnetwork.Wepresentsimulationsforanarrayofsonar-likesensorstoverifyouranalysisresults.

1.INTRODUCTION

Thepossibilityoflargedecentralizedsensornetworkshasrenewedinterestinparallelanddistributedsignalprocess-ing,especiallyasregardstrackingandestimation.Kalman ltersformthemainstayoftheseapplications,andadmitvariouslevelsofdecentralizationunderappropriateassump-tions.However,classicalworkondistributedKalman l-terstypicallyassumesperfectinstantaneouscommunicationbetweeneverynodeonthenetworkandeveryothernode.Whiletheresultingalgorithmsremainimmenselyusefulevenforpracticalnetworks,theydonotallowanystraightfor-wardanalysisofthedegradationoftheirperformancewhencommunicationislimited.

RecentworkinthecontrolandsystemscommunityhasexaminedastrategyfordynamiciterativeKalman ltering.Thisapproachimplementsadistributed lterinwhicheachnodedynamicallytrackstheinstantaneousleast-squaresfu-sionofthecurrentinputmeasurements.ThisallowsthenodestorunindependentlocalKalman ltersusingtheglob-allyfusedinput,and(asymptotically)obtaintheperformanceofacentralizedKalman lter.Thefactthatonlyinputs(not

Time Index

Positions and Estimates

Positions and Estimates

Time Index

Fig.1.TypicalbehaviorofthedistributedKalman lterasthenumberofmessageexchangesincreases.

estimates)aresharedallowsafrequency-domainanalysisoftheperformanceofthisdistributedestimationscheme.Themaincontributionofthisarticleisatransferfunc-tiondescribingtheerrorbehaviorofthedistributedKalman lterinthecaseofstationarynoiseprocesses.Themag-nitudeofthistransferfunctiongoestozeroexponentiallyasthespeedofthecommunicationnetworkrelativetothespeedoftheestimatedprocessbecomeslarge.Speci cally,wewillshowthatthefollowingquantityisparticularlyrel-evant:

n λ2 1 . dmax+1 Here,dmaxisthemaximalnode-degree,λ2isthealge-braicconnectivityofthenetwork,andnisthenumberof

neighbor-to-neighbormessageexchangesallowedperup-dateoftheestimationprocess.

Positions and Estimates

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

2.BACKGROUNDANDPREVIOUSWORKDistributedanddecentralizedestimationhasattractedmuchattentioninthepast,andthereisalargeassociatedlitera-ture.TheclassicworkofRaoandDurrant-Whyte[1]presentsanapproachtodecentralizedKalman lteringwhichac-complishesgloballyoptimalperformanceinthecasewhereallsensorscancommunicatewithallothersensors.Further,thisdesign“failsgracefully”asindividualsensorsarere-movedfromthenetworkduetoitsdistributeddesign.How-ever,itisdif culttounderstandtheperformanceofthisal-gorithmwhenpoint-to-pointcommunicationbetweeneachpairofnodesisunavailable,asislikelytobethecaseinalarge-scalesensornetwork.

Muchrecentresearchefforthasbeendedicatedtoun-derstandingthenetworkingandcomputationalchallengesassociatedwithlargesensornetworkshavingonlylimitedcommunicationandroutingcapabilities.TheworkofEs-trin,Govindan,Heidemann,andKumarin[2],aswellasthatofAkyildiz,Su,Sankarasubramniam,andCayirci[3]presentexcellentsurveysofthechallengesassociatedwiththisnewtechnology.TheworkofZhao,Shin,andReich[4]addressessimilarchallengesindynamicallyfusingtheinformationcollectedbyalargenetworkofsensors,whileincorporatingthecostsassociatedwithexcessivecommuni-cationandcomputation.Thisproblemhassigni cantimpli-cationsfornetworkingprotocols;thisaspectofsensornet-worksisaddressedintheworkofHeinzelman,Kulik,andBalakrishnan[5].

Thedynamicsofcoordinationmechanismsinnetworkshasattractedmuchattentioninthecontrolandsystemscom-munity;wereferthereadertotheworksofOlfati-SaberandMurray[6],Jadbabaie,Lin,andMorse[7],andreferencesthereinforanintroductiontorecentdevelopmentsinthisarea.Theformerarticlepresentsadecentralized“diffusion”mechanismforobtainingweightedaveragesofindividualagentinputsinthefaceofdelaysandlinkloss.TheworkofMehyaretal.[8]showsthatthiscanbesuccessfullytrans-latedtoatrulyasynchronouspeer-to-peersystemoperatingonaTCP/IPnetwork.Finally,theaveragingmechanismisgeneralizedtodevelopreal-timetrackingofoptimallyfusedleast-squaresestimatesandanassociateddecentral-izedKalman lterinSpanos,Olfati-Saber,andMurray[9].

Theconvergenceperformanceofthesediffusion-baseddesignsdependsonthealgebraicconnectivityofthenet-work,whichisthesmallestpositiveeigenvalueoftheasso-ciatedLaplacianmatrix(seethearticlebyMerris[10]forgraph-theoreticfundamentalsregardingtheLaplacian).Inthecasewherecentralizedtopologyinformationisavailableapriori,theworkofXiaoandBoyd[11]providesveryuse-fulresultsforoptimizingthisconvergencerate.AdditionalworkbyXiao,Boyd,andLall[12]providesananalogousrateoptimizationforthestaticleast-squaresfusionproblem.

Input Measurementsand Covariance

DynamicLS Fusion

NonlinearMapping

Instantaneous LS Fusion

Fused Measurementand Covariance

LocalEstimators

Fig.2.ThestructureofthedistributedKalman lterpro-posedinSpanos,Olfati-Saber,andMurray[9].

3.NOTATIONANDASSUMPTIONS

WeconsiderasetVofNsensornodes,eachlabeledi=1,2,...,N.Thesesensorscommunicateonanetworkmod-eledasagraphG=(V,E),wheretheedge(i,j)isinEifandonlyifnodesiandjcanexchangemessageswitheachother.WedenotetheneighborhoodofnodeibyNi.Notethatthisgraphmayrepresenteitherthephysicalcommuni-cationnetworkorsomeoverlaynetworkimplementedwithrouting;weonlyrequirethatthisgraphencodewhichnodescanexchangemessages.

WeassumethatthegraphGisconnected,andforthesakeofthispaper,static.Seetheworkin[6],[13],[8],and[14]forextensionsofthismechanismtoswitching-topologies,randomlyfailinglinks,asynchronouspeer-to-peeroperation,andarbitrarysplittingandmergingofsub-networks.

Aglobalphysicalprocesswithstatep∈Rmevolvesaccordingtothediscrete-timesystem

p(t+1)=Ap+w(t)

whereA∈Rm×mandw(t)iszero-meanGaussiannoisewithcovariancematrixQw.TheprocessinitialconditionisalsodistributedasamultivariateGaussianwithexpectationp0andcovarianceQ0.Wesupposethattheprocessparam-etersA,Qw,Q0andp0areallavailabletoeverymemberofthenetwork,inordertorunlocalKalman lters.

Eachsensortakesmeasurementsofthephysicalprocessaccordingtotheequation

yi(t)=p(t)+ni(t).

Thenoiseprocessesni(t)∈Rm×mareeachindependentzero-meanGaussianwithcovarianceQi(t).

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

Ourcentralassumptionisthatthenetworkis“fasterthanthephysicalprocess”,inthesensethatforeachphys-icalupdateindext,thenetworkcarriesoutn>1messageexchangesoneachedge.Theworkin[9]presentsamech-anismformessageexchangeanddecentralizedestimationthatisequivalenttoapurelylocalKalman lterforn=0,andachievestheperformanceoftheglobalKalman lterinthelimitasnbecomeslarge.Thisresultstemsfromtheindependenceofthenoiseprocesses,whichimpliesthatitissuf cienttoperformthespatialfusionbeforethetime-propagation.Itisthussuf cientforeachsensortorunalocalKalman lter,takingasinputstheinstantaneousspa-tialleast-squaresfusionoftheinputmeasurements

1 yt)= LS(Q 1(t)

Q 1

ii(t)yi(t)

i∈V

i∈V

andtheassociatedspatially-fusedcovariance

1Q(t)=

LSQ 1

i(t)

.i∈V

Thedistributed lterproposedin[9]providesamech-anismfortrackingtheaverageoftheinverse-covariance-weightedmeasurements

¯y(t)=1 N

Q 1

i(t)yi(t)i∈V

andthetime-varyingaverage inverse-covariance

Q¯(t)=1

N

Q 1i(t).i∈V

Clearly,thesetwoquantitiesaresuf cienttoreconstruct

yLS(t)bysolvingalinearsystemofequationsateachtimet.Further,knowledgeofthenumberofnodes(available,forexample,fromadistributedminimumspanningtree)allowsoneto ndtheassociatedcovariancesignal.

Thealgorithmrequireseachnodetomaintainavec-torvariablexi(t)∈RmandamatrixvariableMi(t)∈

Rm×m.TheseareallinitializedtoQ 1 1

Thealgorithmrunateachi(0)yi(0)andQnodeisasfollows:

i(0)respectively.foreachtimet

xi←xi+Q 1yi(t) Q 1

i(t)i(t 1)yi(t 1)

Mi←Mi+Q 1t) Q 1

i(i(t 1)fork=1,2,...,n

x←x

ii+γ j∈Ni(xj xi)

M

i←Mi+γj∈Ni(Mj Mi)

endend

Itwasshownin[9]andMitrack¯y

andQ¯thatthisalgorithmmakeseachxi

respectivelyandsoeachnodecanthuslocallycomputeM 1ixiand(NMi) 1,treatingtheseasapproximationstoyLSandQLS.Thealgorithmde-scribedtracks¯y

andQ¯withzeroerrorin“steady-state”1.Thisasymptoticresultholdsforarbitrarynetworkintercon-nectionandforarbitraryn,butthetransientperformanceofthesystemdependsonthenetworktopology,connec-tiondensity,andthenumberofmessagesperunittimen(aproxyforbandwidth).

Theparameterγisastepsize,andmustbechosentoensurestabilityoftheupdatingscheme.Thisissomewhattrickyinthatstabilitycan,inprinciple,dependonthegraphstructureofthenetwork.Anecessaryandsuf cientcon-ditionforstabilityunderarbitraryinterconnectionofthesensorsisγdmax<1,wheredmaxisthemaximumnode-degreeinthenetwork.Thereisa“natural”choice

γ=

1dmax+1

whichhasthepropertythatifeverysensorisconnectedto

everyothersensor,theglobalKalman lterperformanceisrecoveredwithasinglemessageexchangeperunittime,i.e.evenwithn=1.Thus,withγasaboveandcompletein-terconnectionthisschemeisequivalenttothatofRaoandDurrant-Whyte[1].Wewillassumehereafterthatγischo-seninthisway.Thiswillonlyaffecttheconstantsenteringtheexpressionstocome,andnotanyofthequalitativere-sults.

Finally,wewillmakeuseoftheLaplacianmatrixasso-ciatedwiththegraphG.TheLaplacianisde nedasfol-lows:

Lij= 1L if(i,j)∈E,else0ii

=Lij.

j=i

Thisisasymmetricpositive-semi-de nitematrix,andthe

assumptionthatGisconnectedimpliesthatLhasexactlyonezeroeigenvalueandassociatedeigenvector1(thevec-torofallones).Thus,repeatedmultiplicationofavectorby(I γL),whereIistheN×Nidentity,driveseachcomponentofthevectortotheaverageofthecomponentsoftheinitialvector(see[6]).

NotethateachcomponentofthexiandMivariablesisupdatedindependently.Ifforanyonesuchcomponent,weconsideralltheassociatedvaluesacrossthenetworkstacked

1Here

“steady-state”meansthatboththemeasurementsandthecovari-ancematricesapproachalimitast→∞.Forexample,thisassumptionisreasonablewhenestimatingmovingobjectsthatoccasionallyhaltforsigni cantperiodsoftime.

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

inavectorv∈RN,thentheactionoftheinnerupdateloopcanbeviewedasthefollowingmultiplication:

v←(I γL)n

v.

(1)

TheinnerloopispreciselyaLaplacianupdatingscheme

fortrackingtheinstantaneousaverageofthecovariance-weightedmeasurementsandtheinverse-covariancematri-ces.Thus,theeigenvaluesoftheLaplacianmatrixdeter-minetheconvergencepropertiesoftheinnerupdateloop.Inparticular,thesmallestpositiveeigenvalueoftheLaplacian,denotedλ2,allowsustoderiveaboundontheworst-caseconvergencerate.Thisquantityisknowningraphtheoryasthealgebraicconnectivity,andisstronglytiedtoconnec-tivitypropertiesofthegraph(see[10]foracomprehensiveexposition).

4.PERFORMANCEANALYSIS

Inthissectionwewillshowatransferfunctioncharacteriz-ingtheperformanceofthedistributedestimatorinthecasewherethenoisecovariancehasreachedsteady-state,i.e.allthecovariancematricesQi(t)arehereafterassumedcon-stant,andweassumethattheupdateloopfortheMimatri-ceshasconverged.Thismayseematrivializingassumptioninthecontextofsensornetworkswhereestimatedprocessesarelikelytoexhibitnon-stationarystatistics,andsosomecommentsareinorder.

First,letusprovidesomeintuitionforthedistributedestimationscheme.Ateachtimeinstant,eachnodehasanestimateofthegloballyfusedmeasurementinputs,andthegloballyfusedcovariance.Thisallowsthesensortoimple-mentanapproximationtotheglobalKalman lter.Forsta-tionarynoise,theglobalKalman lterisjustaLinearTime-Invariant(LTI)systemparametrizedbythecovariancema-trixandtheprocessparameters.Ifthecovariancematricesreachalimit,thematricesMiconvergeexponentially(intime)totheaverageinversecovariance,andsoeachnoderapidly“discovers”thecovariancematrixassociatedwiththeglobalsteady-stateKalman lter.

Thedistributed lterisinherentlyadaptive;ifthecovari-ancematricesbeginchangingagain,approachinganothersteady-statevalue,thealgorithmautomaticallytracksthischangeand ndsthenewcovariancematrixtobeusedintheKalman lter.Thus,analysisofthesteady-statecaseisjus-ti ed,eitherforslowly-varyingerrorstatistics,orforpro-cesseswherethetime-variationofthestatisticsis“bursty”,remainingconstantforlargeperiodsoftime(relativetotheupdatetime-scaleofthenetwork).

Now,letusdenotethetransferfunctionoftheglobalsteady-stateKalman lterK(z),anm×mmatrixoftransferfunctions(determinedbyQLS);undertheassumptionsofthissection,eachsensorhasalreadycalculatedQLSandcanthusimplementthis lterlocally.Thenominalinput

tothe lterisyLS(t),buteachnodemustinsteadusethefollowinglocalestimateasinput:

M 1ixi(t)=NQLSxi(t).

SincethequantityNQLSisjustaconstantmatrix-gainforthesteady-state lter,itsuf cestoexaminethedynamicsofthelocalestimatesxi(t),andhowthesevariablesrelatetothe“desiredvalue”(NQLS) 1yLS.Inordertodoso,letus

introducethenotation andx denotingthestackedvectorsoftheyi(t)andM 1

yixi(t)vectors,i.e.

y

=

yTTT T

x

= 1,y2...yN

M 1T

1T 1 1x1,M2

x2...MTT

NxN.HerethesuperscriptTdenotestransposition.Notethatwhen

thecovariancematricesareconstantintime,thenominal

inputyLSisrelatedtothevector y

byaconstantmatrixmultiplication:

yLS=PLS y=Q LSQ 1 1

1

1Q2...QN y.Now,thelocalestimatesM 1ixiarejusttheoutputsof

thespatialaveraging lterdescribedintheprevioussection.Speci cally,theinputstothis lterarethelocalcovariancematricesandthelocalmeasurements;ingeneralthespa-tialaveraging lterisnonlinearinaninput-outputsensebe-causeoftheinputnonlinearityQ 1

i(t)yi(t)andtheoutputnonlinearityM 1ixi(t).

However,whenthecovariancematricesareconstantandtheupdateoftheMimatriceshasconverged,theoverallinput-outputbehaviorofthespatialaveraging lterislinearasamappingfromthelocalmeasurementsignalsyi(t)tothelocalestimatesignalsM 1ixi(t).Thus,thereissomeNm×Nmmatrixoftransferfunctions,callitH(z),suchthat

x(z)=H(z) y(z).Thisletsusmakeasimplebutintuitivelyusefulstatement:

Insteady-state,theperformancelossasso-ciatedwiththedistributedestimationdesignis

equivalenttopremultiplicationoftheglobalKalman lterbyalow-pass lterdeterminedbythenet-worktopologyandspeed.

ThissituationisdepictedinFigure3.Inordertoquantifytheperformanceloss,wesimplyneedtounderstandthefre-quencyresponseofthislow-pass lter.Wewilldosobycharacterizingtheerrortransferfunction,whichisahigh-pass lter.

Todoso,letusrecallthateachM 1ixitracksyLSwithzerosteady-stateerror.ThisimpliesthattheDCgainofHisjust

H(1)= PLSTPLST...PLST T

.

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

Determined by distributed calculationof yLS

Local KF outputs

Fig.3.Thesteady-statebehaviorofthedistributed lterisequivalenttoaglobalKalman lterwithapre lteredinput.Theperformanceanalysisofthisisbasedonquantifyinghowclosethepre lteristounity.

Now,wewanttoconsiderthetheerrorsignal

e= x yTLSyTLS...yT

T

LS,

andthetransferfunctionfrom y

toe(z)H e y(z)=H(z) PLSTPLST...PLS

T T

.Notethatthistransferfunctioniszeroatz=1bycon-struction.Furthermore,weknowthatthissystemhasthe

structureofmdecoupledsubsystems(oneforeachcompo-nentofxi).Uptoaconstantmatrixscalingdeterminedbythecovariancematrices,eachsuchsubsystemhastransferfunctionofthefollowingform

G(z)=

1N

11T (1 z 1)(I γL)n I z 1(I γL)n 1

.

Thisfollowsfromtheinner-loopLaplacianupdateopera-tion(1),andthe rst-orderdifferencingoperationinthe

outerloop.WewillfurtherdecomposethesesubsystemsbyexploitingthefactthattheLaplacianisasymmetricmatrix,andadmitsaspectraldecomposition

L=0·11T

+ λiPi

i>1

wherethePitermsareorthogonalprojectionsontomutually

orthogonalsubspacesandtheλitermsarestrictlypositiveeigenvalues(orderedfromsmallesttolargest).Recallthatthe rstterm,correspondingtothenullspaceofL,isknown

aprioribecauseofthestructureoftheLaplacianmatrix.ApplyingthisformulaforLintheaboveequation,weob-tain

(1 γλi)nG(z)=(z 1)

nPi.i>1z (1 γλi)Notethatallofthesetermsarezeroatz=1,inaccordance

withourpreviousstatementregardingHe y(z).

Wehavenowdecomposedtheerrortransferfunction(uptoablock-diagonalmatrixscaling)intoNmindepen-dentsubsystems,eachwithtrivialpole-zerostructure.Specif-ically,theyallshareacommonzeroatz=1,andeachhaveasinglepoleoftheformz=(1 γλi)n.Ourassumptionregardingγimpliesthatthelargestsuchtermis(1 γλ2)n.Thisallowsustoboundtheerrortransferfunctionasfol-lows: H(z) ≤ C(1 γλ)n(z 1)

2 e y z (1 γλ (2)2)n whereCisaconstantdeterminedbythecovariancematri-ces.

5.THEIMPACTOFTHENETWORK:TOPOLOGY,

DENSITY,ANDBANDWIDTHTheboundwehavederivedintheprevioussectionallowsustoquantifytheperformanceofthedistributedestimationschemeasafunctionofthenetworkparametersλ2,γ,andn.Asasimpleveri cationofourclaimthatthedistributedschemereducestoperfectestimationundercompleteinter-connection,wewillmakeuseofthefactthatforacompletegraph

λi=dmax+1foralli>biningthisfact,ourchoiceofγfrombefore,andtheboundfromtheprevioussection,weobtain

He y=0

foralln>1,whichimpliesthattheglobalKalman lter

performanceisachievedwithasinglemessageexchangeoneachlinkperunittime.

Ingeneral,wecanunderstandtheperformanceofthissystembythefollowingquantity:

n λ 1 2 1+d .max Asthisquantitytendstozero,theperformanceofthedis-tributedestimatorapproachesthatofacentralizedKalman

lter.Speci callywecanstudythisquantityasafunctionofthethreefactorsthatarelikelytovaryacrossreal-worldsensornetworks:topology,connectiondensity,andband-width.The rstaspectiscapturedintheeigenvaluesoftheLaplacianmatrix,andinparticularthealgebraicconnec-tivityλ2.Acomprehensiveexplanationofthisquantityis

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

λ2 = .1λ2 = .28

λ2 = .34

λ2 = .4

Fig.4.Thealgebraicconnectivityλ2forafewgraphs.Thisquantityplaysacentralrolesinanalyzingtheperformanceofthedistributedestimator.

beyondthescopeofthispaper(weagainreferthereadertoMerris[10]),butwecanbuildsomeintuitionwithasim-pleexample:aringtopologytowhichwesequentiallyaddlong-distancelinks.Asmorelong-distancelinksareadded,thealgebraicconnectivitygrows,indicatingbetterperfor-manceforthedistributedKalman lter(seeFigure4).Thissuggestsaninterestinguseforroutinginsensornetworks,relativetothedistributedestimationscheme:routingcanbeusedtoimplementafewlong-distanceconnectionsinordertoimproveλ2.Inaddition,fortopologiesthatare xedandknownapriori,wealsoremindthereaderoftheresultsin[11]and[12]whichallowonetooptimizeλ2usingsemi-de niteprogramming.

Thesecondaspectonemustconsiderinthenetworkisthedensityofconnections.Thishasadualeffectonthedistributedestimator.First,highconnection-densityin u-encestheeigenvaluesoftheLaplacianmatrixinrelativelycomplicatedways,butoverallittendstoin uencethelargeeigenvaluesmorethanthesmallones.Second,itlimitsthestepsizeparameterγduetostabilityconcerns.Thus,ifonehascontroloverthetopologyonwhichthisdistributedesti-mationschemewillbeimplemented,careshouldbetakentobalance“high-connectivity”inthesenseofλ2againstsmallstepsize,asparametrizedbythereciprocalofthemaximumdegree.

Finally,weseethedominatingin uenceoftheconnec-tionbandwidth,asrepresentedbyn.Asnincreases,themagnitudeoftheerrortransferfunctionshrinksexponen-tially.Consideredinthelightofalow-passpre ltermul-tiplyingtheKalman lter,asnbecomeslarge,thepre lterrapidlyapproachesunityforall

frequencies.

Fig.5.Asolidobjectmovingthroughanarrayofsonar-likesensors.Thelinesindicatecommunicationlinksbetweentheindividualsensors.Thevarianceofthemeasurementstakenbyeachsensorincreaseswithdistance.

6.SIMULATIONEXAMPLE:ASONARARRAY

Thissectionpresentssimulationsforthedistributed lteronanarrayofsonar-likesensors.Thesensorsreportrangeandbearingateachtimeinstant,withthevarianceofthebear-ingmeasurementsetattentimesthevarianceintherangemeasurement.Therangevarianceincreasesquadraticallywithdistancefromthetarget.Thetargetmovesinacir-clecenteredatthecentralsensor,andeachsensorusesasecond-ordermodelforthedynamicsoftheprocess.Themeasurementstakenbythesensorsaredeliberatelymadeverynoisy(seeFigure6)toillustratetheperformanceofthisalgorithminanadversarialsetting.

Thesimulationsarecarriedoutusingthenine-nodesornetworkdepictedinFigure5,withγchosenas1

sen-Weshowtheresultsfortwotopologies,oneasshowninmax.Fig-ure5,andonewhereweaddallthe“diagonal”connections(i.e.verylimitedlocalrouting).Wesimulatethealgorithmforn=5,10,20messageexchangesperestimatorupdate,andshowtheseresultsalongsidetheresultsfromacentral-izedimplementationoftheKalman lter.TheseareshowninFigures7and8(thetrajectoriesshownineach gurearechosenfromthesensorwiththeworstmean-squareerror).Figures9and10showtheassociatedboundsontheerror,basedontheanalysisinSection4.

7.SUMMARYANDCONCLUSIONS

WehaveexaminedtheperformanceofadistributedKalman lterbasedonaniterativespatialaveragingalgorithm.Thisalgorithmisofparticularinterestbecauseparallelworkhasdemonstratedthatithasexcellentrobustnesspropertiesre-gardingvariousnetworkimperfections,includingdelay,linkloss,andnetworkfragmentation.Thisspatialaveragingprocedurehasalsobeenveri edonareal-worldTCP/IPnet-

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

Typical Measurement History

432

t

ne1merus0aeM 1dna n 2oitisoP 3 4 5

6

01002003004005006007008009001000

Time Index

Fig.6.Ameasurementhistoryusedinoursimulation.Themeasurementnoiseisdeliberatelysetveryhigh,withvari-ance vetimestheamplitudeofthesignal.

True Positions and Centralized Kalman Filter1

s

etam0.5itsE dna0 snoitiso 0.5P 1

0200

4006008001000

Time Index

Fig.7.ThesimulationresultsfromthetopologyshowninFigure5.Thetrajectoryshownistheworstamongallsen-sors,inthemean-squareerrorsense.Evenwithrelativelyfewmessagesperunittime,thedistributedestimatesdifferfromthecentralizedestimatebytento ftypercent,despitetheextremelynoisymeasurements(comparethescalesoftheseplotstothescaleofFigure6).Asthenumberofmes-sagesperunittimeincreases,theperformanceofthedis-tributedestimatorimprovesdramatically.

True Positions and Centralized Kalman Filter1

s

etam0.5itsE dna0 snoitiso 0.5P 1

0200

4006008001000

Time Index

Fig.8.ThesimulationresultsfromthetopologyshowninFigure5withall“diagonal”connectionsadded.Notethattheimprovedcommunicationtopologyhassigni cantlyimprovedtheperformanceofthedistributedestimationscheme.

H bound: λ = 1

10

10

10

|Hey|

10

10

10

ω (normalized)

Fig.9.Theboundontheerrortransferfunctionforthenet-workdepictedinFigure5,inlogarithmicscale.Notethedrasticimprovementintrackinglow-frequencysignalsasnincreases.

We analyze the performance of a distributed Kalman filter proposed in recent work on distributed dynamical systems. This approach to distributed estimation is novel in that it admits a systematic analysis of its performance as various network quantities su

H bound: λ = 2

10

10

10

|Hey|10

10

10

10

ω (normalized)

Fig.10.Theboundontheerrortransferfunctionforthenet-workwith“diagonal”connections.Weseethesamequali-tativedependenceonthenumberofmessageexchanges,butthisnetworkhassigni cantlylargerλ2.Thisisveri edbyimprovedperformanceinthesimulationresults,asshowninFigure8

work,andthissuggeststhattheproposedKalman ltercanbetranslatedtoapracticalimplementation.

Ourperformanceanalysisshowsasimpleboundfortheerrortransferfunctionwhichincorporatesthenetworktopol-ogy,connectiondensity,andcommunicationbandwidth.Wehaveshownsimulationsdemonstratingthisdependence,along-sidetheboundsforthiserrortransferfunction.Thisis,webelieve,anovelcontributiontodistributedestimation,whichtypicallydoesnotallowsystematicanalysisofper-formanceundernon-idealizednetworkconditions.

Thesimulationresultsdonotspeaktothefullpowerofthisapproach,inthatthisdistributed lteringmecha-nismisnaturallyandsimplyscalabletoarbitrarilylargenetworks,whilemaintaininganalyticalperformanceboundsthataredirectlyrelatedtotheunderlyingsensornetwork.Ofcourse,boundsontheerrortransferfunctionarenotnec-essarilyappropriateforallapplicationsofdistributedesti-mation,butitislikelythatthiswillbeusefulfordistributedcontrolapplicationswherequantitativeperformancemea-suresareessential.Nonetheless,itremainstobeseenwhetherapracticalversionofthisdesigncancompetewithmorees-tablishedapproachestodistributedestimation.

8.REFERENCES

[1]B.S.RaoandH.F.Durrant-Whyte,“Fullydecen-tralisedalgorithmformultisensorkalman ltering,”IEEEProceedings-D,1991.[2]D.Estrin,R.Govindan,J.Heidemann,andS.Ku-

mar,“Nextcenturychallenges:scalablecoordinationinsensornetworks,”p.andNet.,1999.

[3]I.Akyildiz,W.Su,Y.Sankarasubramniam,and

E.Cayirci,“Asurveyonsensornetworks,”IEEECommunicationsMagazine,pp.102–114,August2002.[4]F.Zhao,JaewonShin,andJamesReich,“Information-drivendynamicsensorfusion,”IEEESignalProcess-ing,2002.[5]W.R.Heinzelman,J.Kulik,andH.Balakrishnan,

“Adaptiveprotocolsforinformationdisseminationinwirelesssensornetworks,”p.andNet.,1999.[6]R.Olfati-SaberandR.M.Murray,“Consensusprob-lemsinnetworksofagentswithswitchingtopologyandtime-delays,”IEEETransactionsonAutomaticControl,2004.[7]A.Jadbabaie,J.Lin,andA.S.Morse,“Coordination

ofgroupsofmobileautonomousagentsusingnearestneighborrules.,”ProceedingsoftheConferenceonDecisionandControl,2002.[8]M.Mehyar,D.P.Spanos,J.Pongsajapan,S.H.Low,

andR.M.Murray,“Distributedaveragingonapeer-to-peernetwork,”Preprint(SubmittedtoIPSN05),2005.[9]D.P.Spanos,R.Olfati-Saber,andR.M.Murray,

“Distributedsensorfusionusingdynamicconsensus,”2005.[10]R.Merris,“Laplacianmatricesofagraph:Asurvey,”

LinearAlgebraanditsApplications,1994.[11]L.XiaoandS.Boyd,“Fastlineariterationsfordis-tributedaveraging,”ProceedingsoftheCDC,2003.[12]L.Xiao,S.Boyd,ll,“Aschemeforasyn-chronousdistributedsensorfusionbasedonaverageconsensus,”IPSN,2005(submitted).[13]Y.HatanoandM.Mesbahi,“Consensusoverrandom

networks,”ProceedingsoftheCDC,2004.[14]D.P.Spanos,R.Olfati-Saber,andR.M.Murray,“Dy-namicconsensusonmobilenetworks,”Preprint(Sub-mittedtoIFAC05),2005.

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