Approximate distributed Kalman filtering in sensor networks

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,theworkofXiaoandBoy …… 此处隐藏：5333字，全部文档内容请下载后查看。喜欢就下载吧 ……