Application of Graph Theory to Sensor Placement in Water Distribution Systems

Water distribution systems are one of the most vulnerable civil infrastructures having crucial consequences on public health and the environment. Degradation of water quality in the distribution system farther away from the treatment plant may occur as a result of intentional or unintentional events, such as microbial growth within the pipes and injection of hazardous contaminants at system's cross-connections. It has been agreed that a key component in contamination warning systems is real-time monitoring of water quality using online sensors, which can provide an earlier indication of a potential contamination incidences. Most work related to placement of such sensors relies on available and well-calibrated hydraulic and water quality models (e.g., EPANET) integrated with optimization techniques (e.g., MIP, GA). In reality, these well-calibrated simulation models are rarely available from water utilities and typically include only partial information such as network topology and representative demand loadings. This work adopts algorithms from graph theory to suggest the location of sensors in a water distribution system given accessible information. The proposed approach can provide a more realistic decision support to water utilities in real application.