# Presentation: 008346

## Sensor Placement for Contaminant Source Identification

- Jonathan Berry (SNL)
- Michael Collins (SNL)
- William E. Hart (SNL)
- Jim G. Uber (UC)
- Jean-Paul Watson (SNL)

## A New Performance Metric for Sensor Placement

- Sensor placement is a key step in the design of a contaminant warning system (CWS)
- Existing performance measures used for sensor placement can be broken into two categories
- Detection measures
- Time to detection
- Number of failed detections
- Exposure measures
- Population exposed
- Volume of contaminant consumed
- IDEA: define measures that ensure that contaminant sources can be readily identified

- WDSA 2006 Poster - SP for Inversion

## Contaminant Source Identification

- Goal: predict where the contaminant entered the distribution network
- Impact:
- Enable termination of ongoing contamination events
- Facilitate contamination cleanup
- Method:
- Numerical source inversion
- Use contaminant concentrations through time
- CHALLENGE: this requires *enough* sensors that are *well distributed* throughout the distribution network

- WDSA 2006 Poster - SP for Inversion

## Topological Uncertainty

- Observation: for a given set of sensor locations, the topology of the distribution network induces fundamental uncertainties about the contaminant location
- IDEA: consider whether contamination events are distinguishable for a given set of sensors
- For a given set of sensor locations, every contamination event generates a *detection pattern*: the temporal sequence of detections
- Two contamination events are *distinguishable* if they have different *detection patterns*

- WDSA 2006 Poster - SP for Inversion

## 

Note: box indicates the location of a sensor

Contaminant introduced at any junction will be detected

Cannot distinguish contaminant sources

Could distinguish sources if you knew the initial concentration levels and amount of decay ... be that’s cheating!

- Note: box indicates the location of a sensor
- Contaminant introduced at any junction will be detected
- Cannot distinguish contaminant sources
- Could distinguish sources if you knew the initial concentration levels and amount of decay ... be that’s cheating!

**EXAMPLES**

- WDSA 2006 Poster - SP for Inversion

## A Sensor Placement Model

- Assumptions
- Sensors placed at junctions
- Contamination introduced at junctions
- Hydraulic simulation defines the flow of contamination for a contamination event
- Ideal sensors (always detect if contaminant is above a concentration threshold)
- Sensor Placement Objective:Maximize the number of pairs of contamination events that can be distinguished

- WDSA 2006 Poster - SP for Inversion

## Integer Programming Formulation

- Where
- NOTE: the contaminant detection sets *D**ij* are determined from water quality simulations

- WDSA 2006 Poster - SP for Inversion

## Heuristic Methods

- A simple greedy approach
- Let *U**t* be the number of undistinguished pairs after *t* iterations
- Let *U**v* be the number of undistinguished pairs if the next sensor is placed at *v*
- Place a sensor at the junction v that maximizes *U**v**/U**t*
- Satisfiability heuristic
- Treat *D**ij* as a clause:
- Reformulate bound on sensors as a clause (nontrivial...)
- Not all events may be distinguishable for a given sensor budget, so we formulate a weighted max-SAT problem
- Can solve with standard solvers: zChaff, Walksat

- WDSA 2006 Poster - SP for Inversion

## Solver Performance

- Note: the memory requirements for the IP scales with the square of the number of contamination events
- Problem size is also an issue for heuristics, but perhaps less so...
- For example, you can iteratively optimize over subsets of contamination events

- WDSA 2006 Poster - SP for Inversion