The optimal sensors placement problem in drinking water distribution networks : a graph theory-based approach

The optimal sensors placement for contamination events detection is one of the most promising fields of research in the management and protection of drinking water distribution systems. The number and location of water quality sensors are key decisions in creating an efficient and cost effective network warning system. In this work the Optimal Sensors Placement Problem is addressed by means of a Graph Theory-based approach, which involves the mapping of the network as different types of graphs, the use clustering algorithms to divide them into smaller subgraphs, and the use of centrality measures to identify the most central nodes as potential sensors locations. Four different graph types, five clustering algorithms and eight centrality measures are tested on two real existing mid-to-large scale networks. The proposed method is computationally effortless and only requires topological information about the distribution system. The detection performance of the identified sensors layouts are evaluated against a set of stochastically generated contamination events, by means of an hydraulic simulations-based procedure. However such hydraulic simulations, which require well-calibrated models and great computational effort, are used here only as a one-off validation tool, aiming to identify the graph theoretic tools that provide the most performing sensors layouts, so that to make their application straight forward in other future case studies. The graph-theoretic approach proved to be a versatile option in addressing the optimal sensors placement problem, due to the ease of implementation and the large number of placements that can be obtained by combining different graph types, algorithms and measures. Among them, the validation procedure allowed to identify the Edge Betweenness Algorithm and the Spectral Algorithm as the best clustering tools, while Jordan Center and Betweenness Centrality as the best centrality measures. As for the graph types, considering an unweighted graph and weighting graph edges with geometric parameters of the real network’s pipes, proved to be equally good options. Finally, the adopted contamination events sampling scheme proved to be an effective tool for selecting events starting points and times, with good spatial and temporal variability.

Il posizionamento ottimale dii sensori per il rilevamento di eventi di contaminazione è uno dei campi di ricerca più promettenti nella gestione e protezione dei sistemi di distribuzione dell'acqua potabile. Il numero e la posizione dei sensori di qualità dell'acqua sono decisioni cruciali nella creazione di un sistema di allarme di rete efficiente e conveniente. Nel presente lavoro il problema del posizionamento ottimale dei sensori viene affrontato mediante un approccio basato sulla Teoria dei Grafi, che prevede la mappatura della rete tramite diversi tipi di grafi, l'uso di algoritmi di clustering per suddividerli in grafi più piccoli, e l'uso di misure di centralità per identificare i nodi più centrali come potenziali ubicazioni dei sensori. Quattro diversi tipi di grafi, cinque algoritmi di clustering e otto misure di centralità sono stati testati su due reti realmente esistenti, di media e grande scala. Il metodo proposto è poco oneroso dal punto di vista computazionale e richiede solo informazioni topologiche sul sistema di distribuzione. Le performance di individuazione dei layout di sensori identificati sono state valutate, per mezzo di una procedura basata su simulazioni idrauliche, rispetto ad un insieme di eventi di contaminazione generati stocasticamente. Tuttavia tali simulazioni idrauliche, che richiedono modelli ben calibrati e un grande onere computazionale, sono usate qui solo come strumento di validazione una tantum, con l'obiettivo di identificare i tipi di grafi, gli algoritmi e le misure che forniscono i layout dei sensori più performanti, in modo da rendere la loro applicazione immediata in altri casi di studio futuri. L'approccio adottato si è dimostrato una versatile opzione nell'affrontare il problema del posizionamento ottimale dei sensori, grazie alla facilità di implementazione e al gran numero di posizionamenti che possono essere ottenuti combinando diversi tipi di grafi, algoritmi e misure. Tra questi, la procedura di validazione ha permesso di identificare l' Edge Betweenness Algorithm e lo Spectral Algorithm come i migliori strumenti di clustering, mentre Jordan Center e Betweenness Centrality come le migliori misure di centralità. Per quanto riguarda i tipi di grafi, considerare un grafo non pesato e pesare gli spigoli del grafo con parametri geometrici dei tubi della rete reale, si sono dimostrate opzioni altrettanto valide. Infine, il metodo di estrazione degli eventi di contaminazione adottato si è rivelato uno strumento efficace per selezionare i punti e i tempi di origine degli eventi, con una buona variabilità spaziale e temporale.