### Topics

### features

### Publications

### Issue Archive

# Efficient Method for Optimizing Placement of Sensors

- Created on Thursday, 01 January 2009

### This systematic method supplants *ad hoc* placement and exhaustive-search 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 pre-existing system to increase the diagnostic capability.

The optimal-sensor-placement 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.*Minimal-Cost 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.

The development of the present
method for solving the optimal-sensor-placement
problem began with a rigorous
mathematical description of the problem,
leading to a very efficient algorithm for its
solution. This method incorporates elements
of a method, developed by the same
innovators, for solving the diagnosis problem.
Aspects of this diagnostic method
and developments leading up to it were
reported in several previous *NASA Tech
Briefs* articles, the most recent and relevant
being “High-Performance Algorithm for
Solving the Diagnosis Problem” (NPO-41456), on the preceding page.

It was observed that in an algorithmic sense, the sensor-placement problem is an extension of the diagnosis problem and that both problems can be mapped to a special case of the 0/1 integer-programming (IP) problem. The only difference is that in the optimal-sensor-placement 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 sensor-placement 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 optimal-sensor-placement 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 branch-and-bound algorithm, which is among the algorithms heretofore commonly used to solve the IP problem. Briefly, the traditional branch-and-bound 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 branch-and-bound algorithm is similar to the one used in the aforementioned method for solving the diagnosis problem and offers orders-of-magnitude speedup over prior exhaustive-search algorithms.

*This work was done by Amir Fijany and
Farrokh Vatan of Caltech for NASA’s Jet
Propulsion Laboratory.*

*In accordance with Public Law 96-517,
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 202-233
4800 Oak Grove Drive
Pasadena, CA 91109-8099
(818) 354-2240
E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.*

*Refer to NPO-42481, 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 NPO-42481) is currently available for download from the TSP library.

Please Login at the top of the page to download.

### White Papers

| ||||||