Sensor Selection Cost Optimization for Tracking Structurally Cyclic Systems: a P-Order Solution

TitleSensor Selection Cost Optimization for Tracking Structurally Cyclic Systems: a P-Order Solution
Publication TypeJournal Article
Year of Publication2017
AuthorsDoostmohammadian, M., H. Zarrabi, and H. R. Rabiee
JournalInternational Journal of Systems Science
Volume48
Issue11
Start Page2440
Pagination2440-2450
Date Published08/2017
ISSN14645319; 00207721
KeywordsConvex Programming, Linear Systems, Observability, Sensor Selection, State Estimation, State-Space Models
AbstractMeasurements and sensing implementations impose certain cost in sensor networks. The sensor selection cost optimization is the problem of minimizing the sensing cost of monitoring a physical (or cyber-physical) system. Consider a given set of sensors tracking states of a dynamical system for estimation purposes. For each sensor assume different costs to measure different (realizable) states. The idea is to assign sensors to measure states such that the global cost is minimized. The number and selection of sensor measurements need to ensure the observability to track the dynamic state of the system with bounded estimation error. The main question we address is how to select the state measurements to minimize the cost while satisfying the observability conditions. Relaxing the observability condition for structurally cyclic systems, the main contribution is to propose a graph theoretic approach to solve the problem in polynomial time. Note that, polynomial time algorithms are suitable for large-scale systems as their running time is upper-bounded by a polynomial expression in the size of input for the algorithm. We frame the problem as a linear sum assignment with solution complexity of O(m 3 ).