Topics
features
Publications
Issue Archive
Efficient Method for Optimizing Placement of Sensors
 Created: Thursday, 01 January 2009
This systematic method supplants ad hoc placement and exhaustivesearch optimization methods.
A computationally efficient method has been developed to enable optimization of the placement of sensors for the purpose of diagnosis of a complex engineering system (e.g., an aircraft or spacecraft). The method can be used both in (1) designing a sensor system in which the number and positions of sensors are initially not known and must be determined and (2) adding sensors to a preexisting system to increase the diagnostic capability.
The optimalsensorplacement problem can be summarized as involving the following concepts, issues, and subproblems:
 Degree of Diagnosability — This is a concept for characterizing the set of faults that can be discriminated by use of a given set of sensors.
 Minimal Sensor Set — The idea is one of finding a minimal set of sensors that guarantees a specific degree of diagnosability.
 MinimalCost Sensors — In a case in which different sensors are assigned with different costs, it is desired to choose the least costly set of sensors that affords a specific degree of diagnosability.
It was observed that in an algorithmic sense, the sensorplacement problem is an extension of the diagnosis problem and that both problems can be mapped to a special case of the 0/1 integerprogramming (IP) problem. The only difference is that in the optimalsensorplacement problem, the objective function, in the most general case, is no longer linear. However, the constraints are still linear and defined by a 0/1 matrix.
The solution of the sensorplacement problem starts with the formulation of a structural model of the system to be diagnosed. The structural analysis of the system and the potential information to be collected by each sensor are combined into a set of equations usually called the analytical redundant relations (ARRs). One also takes account of additional sensors and the ARRs of those sensors that, if used, would provide a desired degree of diagnosability. The information from all the ARRs is summarized in a signature matrix (see figure). Then the optimalsensorplacement problem can be formulated as an IP problem involving the signature matrix.
In the present method, the IP problem is solved by a variant of the traditional branchandbound algorithm, which is among the algorithms heretofore commonly used to solve the IP problem. Briefly, the traditional branchandbound algorithm includes finding lower and upper bounds on solutions, successively dividing (branching) the IP problem into subproblems on the basis of the bounds, and eliminating any subproblem, the lower bound of which exceeds the upper bound of another subproblem. The branching, bounding, and elimination are repeated until all subproblems are eliminated. The present new variant of the branchandbound algorithm is similar to the one used in the aforementioned method for solving the diagnosis problem and offers ordersofmagnitude speedup over prior exhaustivesearch algorithms.
This work was done by Amir Fijany and Farrokh Vatan of Caltech for NASA’s Jet Propulsion Laboratory.
In accordance with Public Law 96517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to:
Innovative Technology Assets Management
JPL
Mail Stop 202233
4800 Oak Grove Drive
Pasadena, CA 911098099
(818) 3542240
Email: This email address is being protected from spambots. You need JavaScript enabled to view it.
Refer to NPO42481, volume and number of this NASA Tech Briefs issue, and the page number.
This Brief includes a Technical Support Package (TSP).
Efficient Method for Optimizing Placement of Sensors (reference NPO42481) is currently available for download from the TSP library.
Please Login at the top of the page to download.
White Papers

