DOC PREVIEW
Distributing the Kalman Filter for Large-Scale Systems

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 56, NO. 10, OCTOBER 2008 4919Distributing the Kalman Filter forLarge-Scale SystemsUsman A. Khan, Student Member, IEEE, and José M. F. Moura, Fellow, IEEEAbstract—This paper presents a distributed Kalman filter toestimate the state of a sparsely connected, large-scale,-dimen-sional, dynamical system monitored by a network ofsensors.Local Kalman filters are implemented on-dimensional subsys-tems,, obtained by spatially decomposing the large-scalesystem. The distributed Kalman filter is optimal under anthorder Gauss–Markov approximation to the centralized filter. Wequantify the information loss due to thisth-order approximationby the divergence, which decreases asincreases. The order ofthe approximationleads to a bound on the dimension of thesubsystems, hence, providing a criterion for subsystem selection.The (approximated) centralized Riccati and Lyapunov equationsare computed iteratively with only local communication andlow-order computation by a distributed iterate collapse inversion(DICI) algorithm. We fuse the observations that are commonamong the local Kalman filters using bipartite fusion graphs andconsensus averaging algorithms. The proposed algorithm achievesfull distribution of the Kalman filter. Nowhere in the network,storage, communication, or computation of-dimensional vectorsand matrices is required; onlydimensional vectors andmatrices are communicated or used in the local computationsat the sensors. In other words, knowledge of the state is itselfdistributed.Index Terms—Distributed algorithms, distributed estimation,information filters, iterative methods, Kalman filtering, large-scalesystems, matrix inversion, sparse matrices.I. INTRODUCTIONCENTRALIZED implementation of the Kalman filter[1], [2], although possibly optimal, is neither robustnor scalable to complex large-scale dynamical systems withtheir measurements distributed on a large geographical region.The reasons are twofold: i) the large-scale systems are veryhigh-dimensional, and thus require extensive computationsto implement the centralized procedure; and ii) the span ofthe geographical region, over which the large-scale system isdeployed or the physical phenomenon is observed, poses a largecommunication burden and thus, among other problems, addslatency to the estimation mechanism. To remove the difficultiesManuscript received July 31, 2007; revised April 22, 2008. First publishedJune 20, 2008; current version published September 17, 2008. The associateeditor coordinating the review of this manuscript and approving it for publi-cation was Dr. Aleksandar Dogandzic. This work was partially supported bythe DARPA DSO Advanced Computing and Mathematics Program IntegratedSensing and Processing (ISP) Initiative under ARO Grant DAAD 19-02-1-0180,by the NSF under Grants ECS-0225449 and CNS-0428404, and by an IBM Fac-ulty Award.The authors are with the Department of Electrical and Computer Engineering,Carnegie Mellon University, Pittsburgh, PA 15213 USA (e-mail: [email protected]; [email protected]).Color versions of one or more of the figures in this paper are available onlineat http://ieeexplore.ieee.org.Digital Object Identifier 10.1109/TSP.2008.927480posed by centralization, we decompose the large-scale systeminto-dimensional subsystems and distribute the estimationalgorithm with a low order Kalman filter implemented at eachof these subsystems. To account for the processing, commu-nication, and limited resources at the subsystems, the localKalman filters involve computations and communications withlocal quantities only, i.e., vectors and matrices of low dimen-sions,, where is the dimension of the state vector—nosensor computes, communicates, or stores any-dimensionalquantity.Much of the existing research on distributed Kalman filtersfocuses on sensor networks monitoring low dimension systems.This research replicates anth-order Kalman filter at eachsensor, which is only practical, when the dimension of the stateis small, for example, when multiple sensors mounted on asmall number of robot platforms are used for target tracking[3]–[5]. The problem in such scenarios reduces to how toefficiently incorporate the distributed observations, which isalso referred to in the literature as “data fusion”; see also[6]. Data fusion for Kalman filters over arbitrary communi-cation networks is discussed in [7], using iterative consensusprotocols provided in [8]. The consensus protocols in [8] areassumed to converge asymptotically; thus, between any twotime steps of the Kalman filter, the consensus protocols requirean infinite number of iterations to achieve convergence. It isworth mentioning that, with a finite number of iterations (truefor any practical implementation), the resulting Kalman filterdoes not remain optimal. References [4] and [9] incorporatepacket losses, intermittent observations, and communicationdelays in the data fusion process. Because they replicate an-dimensional Kalman filter at each sensor, they communicateand invertmatrices locally, which, in general, is ancomputation. This may be viable for low-dimensional systems,as in tracking, but unacceptable in the problems we considerwhere the state dimensionis very large, for example, in therange ofto . In such problems, replication of the globaldynamics in the local Kalman filters is either not practical ornot possible.Kalman filters with reduced-order models have been studiedin, e.g., [10] and [11] to address the computation burden posedby implementingth-order models. In these works, the reducedmodels are decoupled, which is suboptimal, as important cou-pling among the system variables is ignored. Furthermore, thenetwork topology is either fully connected [10] or is close tofully connected [11], requiring long-distance communicationthat is expensive. We are motivated by problems where thelarge-scale systems, although sparse, cannot be decoupled andwhere, due to the sensor constraints, the communication andcomputation should both be local.1053-587X/$25.00 © 2008 IEEEAuthorized licensed use limited to: Carnegie Mellon Libraries. Downloaded on January 16, 2010 at 17:55 from IEEE Xplore. Restrictions apply.4920 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 56, NO. 10, OCTOBER 2008We present a distributed Kalman filter that addresses boththe computation and communication challenges posed by com-plex large-scale dynamical systems, while preserving its cou-pled structure; in particular, nowhere in our


Distributing the Kalman Filter for Large-Scale Systems

Download Distributing the Kalman Filter for Large-Scale Systems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Distributing the Kalman Filter for Large-Scale Systems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Distributing the Kalman Filter for Large-Scale Systems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?