Approximate distributed Kalman filtering in sensor networks(5)

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-