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

.