Illicit Intrusion Characterisation

worden de multi objective probleem opgelost met gebruik van het Non-Dominating Sorting Genetic Algorithm-II (NSGA-II). Als derde alternatief, is een single objective Greedy based optimisation tool getest. De reeds beschouwde objectieven zijn ook gebruikt in andere combinaties. Het Mass Lubrese riool system is gebruikt om de prestaties van de voorgestelde procedures te testen. Een genormaliseerde vergelijking tussen de benadering laat zien dat de Greedy based benadering een handig alternatief kan zijn voor de optimalisatie van sensor plaatsing in een riool systeem.

Objectives

The main objective of this research is twofold.

To develop a methodology to identify a pollution source with its characteristics in sewer systems.

To explore different methodologies for identifying the optimal placement of a limited number of sensors in sewer network.

analysis of different parameters. The application is tested on two different sewer networks (one from the literature while the other is a real network).

Chapter 5 explains the developed methodology, based on the information theory, for optimising the monitoring networks in the sewer systems. The methodology is tested on a real sewer system, and the outcome is compared with the existing monitoring network of that system.

Chapter 6 compares five different methodologies, proposed, for optimising the monitoring networks in the sewer systems.

Chapter 7 investigates the applicability of the use of greedy-based algorithms over the genetic algorithm during the optimisation process in designing the monitoring networks in the sewer systems.

Chapter 8 summarises the main outcomes of the research and provides some recommendations for the future works.

I would like to start with my deepest gratitude to the Almighty God. It is thy will that have made the research materialised.

I am profoundly grateful to the European Commission for their financial support provided through the Erasmus Mundus joint doctorate programme, namely ETeCoS 3 (Environmental Technologies for Solids, Soils and Sediments), under the grant FPA n° 2010-0009. The research was also partially supported by the project SIMonA, financed by the Campania Region (Italy) in the Campus Campania Programme.

I would like to thank my supervisor Dr. Cristiana Di Cristo for her sincere support, invaluable suggestions, above all giving me an enormous amount of her valuable time throughout the entire period of my research.

I would also like to express my thankfulness to my co-supervisor Dr. Angelo Leopardi for his thoughtful comments and insightful suggestions, especially at the beginning of my research. At the same time my sincere acknowledgement to Professor Arthur Mynett for his invaluable supports during my six months mobility period at the UNESCO-IHE, Delft, The Netherlands. My gratitude is further extended to my thesis examination committee members, Professor Avi Ostfeld and Professor Orazio Giustolisi, for their valuable comments and suggestions.

A very special thanks to Dr. Giovanni Esposito, coordinator of the ETeCoS 3 programme, for his generous kindness that he showed to me throughout last three years, starting from the very first day. I am also grateful to Professor Piet Lens for his kind support during my mobility and to Dr. Eric van Hullebusch for his kind support. I am highly indebted to Dr. Leonardo Alfonso, who was my mentor during the mobility at UNESCO-IHE, for his kind support, priceless suggestions, insightful thoughts and continuous encouragements during last one year. I am also thankful to Dr. Arlex Sanchez Torres for his support at UNESCO-IHE. I am grateful to GORI for providing us all the necessary data to accomplish the research, also grateful to ENEA for providing us some technical supports. Last but not least, deepest gratitude to my parents and family for their unconditional support.

Special thanks to all my colleagues in

Summary

Improper wastewater management could result in significant damage to the treatment plants and the final recipient aquatic ecosystem. In the past, wastewater management did not get much attention from different stakeholders. However, recently a paradigm shift of wastewater and stormwater management is evolving from a simple sanitary and flood control, respectively, to a whole environmental protection function. In many countries (such as USA and EU members), operators have to require a permit from the regulatory authority to discharge their wastewater into the sewer systems. In this context, a very important aspect of the sewer systems management policy is to detect and eliminate an illicit intrusion, which can be intentional, such as unauthorised industrial effluent, or accidental spills. This PhD research is consisting of two main pillars. In the first pillar, the issues regarding the identification of an illicit intrusion in a sewer system have been addressed, proposing a source identification (SI) methodology. In the second pillar, different innovative methodologies have been proposed to find the optimal placement of a limited number of sensors in the sewer system for an early warning in case of a contaminant intrusion.

In the thesis, the SI is solved through a simulation-optimisation model, combining the hydraulic and quality simulation tool Storm Water Management Model (SWMM) with a genetic algorithm code (GALib) as an optimiser. It requires online measurements from some sensors placed on the network. The SWMM is considered one of the standard tools for modelling sewer systems, but it does not have the programmer's toolkit. To integrate the SWMM simulator with the proposed automated SI methodology, an ad-hoc toolkit has been developed. Another aspect is represented by the computational effort required to perform the SI methodology, which is a major concern for the large systems. To comply with that a pre-screening procedure, based on the pollution matrix concept and considering the topology of sewers, has been implemented. The procedure selects a limited group of candidate nodes, cutting all the unnecessary nodes and their associated links from the scheme, to reduce the simulation time.

The SI methodology has been tested on two different networks. One is a literature network taken from the SWMM example manual while the other is one sub-catchment of the real sewer network of Massa Lubrense, a town located near Naples, Italy. The results show that the pre-screening procedure reduces the computational effort significantly, and it has a crucial role on large systems. In investigating the performances of the SI methodology, its sensitivity respect to the genetic algorithm parameters has been verified.

Moreover, the influence of the uncertainty of the inflows values and the measurement errors on the results have been investigated. The analysis suggests that the uncertainty of inflows influences the success rate of the SI, even if satisfactory results are also obtained with significant uncertainty levels. The sensor measurement has less influence on the SI performances.

Another core problem associated with the water quality monitoring of sewers is represented by the optimal placement of a limited number of sensors for the early detection of an illicit source. In the thesis, the sensor location is expressed as a single or multi-objective optimisation problem and the SWMM is used to extract the water quality data. Different formulations have been proposed and tested. First, an Information Theory (IT) based multi-objective optimisation methodology is presented. The IT approach considers two objectives: the Joint entropy, the information content of a set of sensors, which is kept as high as possible; the Total correlation, a measure of redundancy, which is kept as low as possible. In the second multi-objective approach Detection time, to be minimised, and Reliability, to be maximised, are considered. In both cases, the multiobjective problems are solved using the Non-Dominating Sorting Genetic Algorithm-II (NSGA-II). As a third alternative, a single objective Greedy based optimisation tool has been tested. The previously considered objectives are also used with different combinations. The Massa Lubrense sewer network is used to test the performances of various proposed procedures. A normalised comparison among all approaches shows that the Greedy based approach could be a handy alternative for optimising the sensor locations in sewer systems.

Résumé

La gestion incorrecte des eaux usées peut entraîner des dommages importants sur les stations de traitement et sur le récepteur. Dans le passé, la gestion des eaux usées n'a pas obtenu beaucoup d'attention de la part des différentes parties prenantes. Toutefois, récemment, le changement de modèle de gestion des eaux usées et des eaux pluviales, a évolué du simple contrôle sanitaire et des inondations, à une protection globale de l'environnement. Dans de nombreux pays (tels que les Etats-Unis et les pays membres de l'Union Européenne) les opérateurs exigent habituellement une autorisation de l'autorité réglementaire pour décharger leurs eaux usées dans les réseaux d'assainissement. Dans ce contexte, un aspect très important, dans la politique de gestion des systèmes d'assainissement, est de détecter et d'éliminer une intrusion illicite, qui peut être intentionnelle, comme les effluents industriels non autorisée ou des déversements accidentels.

Ce travail thèse de doctorat est constitué de deux parties principales. Dans la première partie les problèmes relatifs à l'identification d'une intrusion illicite dans un système d'assainissement ont été abordés, proposant une méthodologie d'identification de la source (IS). Dans la deuxième partie, différentes méthodologies innovantes ont été proposées pour trouver l'emplacement optimal d'un nombre limité de capteurs dans le système d'assainissement, pour une alerte précoce en cas d'une intrusion de contaminants.

Dans cette thèse, le IS est résolu grâce à un modèle de simulation-optimisation, combinant l'outil de simulation Storm Water Management Model (SWMM) avec un code d'optimisation basé sur un algorithme génétique (Galib). Ceci nécessite des mesures en ligne de certains capteurs placés sur le réseau. Le SWMM est considéré comme l'un des outils standard pour la modélisation de systèmes d'assainissement, mais il ne possède pas l'outil de programmation. Afin d'intégrer le simulateur SWMM à la méthodologie de IS automatisé proposée, un outil ad-hoc a été développé. Un autre aspect est soulevé concernant l'effort de calcul requis pour effectuer la méthodologie IS. Ceci représente une préoccupation majeure pour les grands systèmes d'assainissement. Pour se conformer, une procédure de pré-sélection basée sur le concept de la matrice de la pollution, compte tenu de la topologie des égouts, a été mis en oeuvre. La procédure sélectionne un groupe limité de noeuds, élimine tous les noeuds inutiles et leurs liens associés dans le schéma, afin de réduire le temps de simulation.

La méthodologie IS a été testée sur deux réseaux différents. L'un est un réseau connu dans la littérature, extrait du manuel de SWMM, tandis que l'autre réseau est un sous-bassin versant du réseau d'assainissement de Massa Lubrense, village situé près de Naples, en Italie. Les résultats montrent que les procédures de présélection réduisent considérablement l'effort de calcul, avec un rôle crucial pour les grands systèmes. En enquêtant sur la performance de la méthodologie IS, sa sensibilité par rapport aux paramètres de l'algorithme génétique a été vérifiée. En outre, l'influence de l'incertitude des flux entrés et des erreurs de mesure sur les résultats ont été approfondi. L'analyse suggère que l'incertitude des flux d'entrées influence le taux de succès de l'SI, même si des résultats satisfaisants sont obtenus avec un niveau d'incertitude importante. La mesure du senseur a moins d'influence sur les performances du SI.

Un autre problème fondamental, associé à la surveillance de la qualité de l'eau des égouts, est le placement optimal d'un nombre limité de capteurs pour la détection précoce d'une source illicite. Dans la thèse l'emplacement du capteur est exprimé avec un problème d'optimisation mono ou multi-objectif. Le SWMM est utilisé pour extraire les données de qualité de l'eau. Différentes formulations ont été proposées et testées. Tout d'abord, la Théorie de l'Information (TI) basée sur la méthodologie d'optimisation multi-objectif est présentée. La TI considère deux objectifs: l'entropie conjointe, le contenu de l'information dans un ensemble de capteurs, qui est maintenu aussi haut que possible; la corrélation totale, une mesure de la redondance, qui est maintenue aussi faible que possible. Dans la seconde approche multi-objectifs le temps de détection doit être minimisé et la fiabilité qui doit être maximisée. Les deux cas, les problèmes multi-objectifs sont résolues en utilisant l'algorithme Non-Dominating Sorting Genetic Algorithm-II (NSGA-II). Comme troisième alternative, un outil d'optimisation mono-objectif (Greedy) a été testé. Les objectifs précédemment considérées sont utilisés avec différentes combinaisons. Le réseau d'assainissement de Massa Lubrense a été utilisé pour tester les performances des différentes procédures proposées. Une comparaison normalisée entre toutes les approches montre que l'approche basée sur Greedy pourrait être une alternative pratique pour l'optimisation des emplacements de capteurs dans les systèmes d'assainissement.

Sommario

Una cattiva gestione delle acque reflue può risultare molto dannosa per gli impianti di trattamento e per l'ecosistema acquatico (i.e. il recettore finale). In passato, la gestione delle acque reflue e metoriche non ha probabilmente ricevuto l'adeguata attenzione dalle autorità competenti. Attualmente la gestione delle acque sta evolvendo verso una gestione integrata, non più solo legata al semplice controllo delle piene e al rischio sanitario. In molti Paesi (come gli USA o gli stati UE) gli operatori generalmente sono obbligati a richiedere un permesso alle autorità competenti per scaricare i loro reflui all'interno dei sistemi fognari. In questo contesto un aspetto molto importante della gestione del sistema fognario è quello di individuare e eliminare scarichi illegali, immessi intenzionalmente, come apporti industriali non autorizzati, oppure accidentalmente come sversamenti.

Questa tesi di Dottorato si sviluppa su due principali temi. Nel primo i risultati riguardano l'identificazione di immissioni illecite nei sistemi fognari, proponendo una metodologia di identificazione del punto di immissione (Source Identification, SI). In un secondo tema, differenti tecnologie innovative sono proposte per trovare il posizionamento ottimale di un limitato numero di sensori nel sistema fognario, per ottenere un pre-allarme in caso di presenza di immissioni illegali.

Nella tesi il problema inverso dell'identificazione del punto di immissione (SI) è impostato come un problema di ottimo, risolto combinando il tool di simulazione Storm Water Management Model (SWMM) con l'algoritmo genetico (GALib). La metodologia proposta richiede misure online da sensori installati nel sistema. L'SWMM,considerato uno dei tool standard per la modellazione di sistemi fognari, non possedeva un toolkit di programmazione, necessario per integrare il simulatore nella metodologia. Un altro aspetto è rappresentato dall'onere computazionale richiesto per applicare la metodologia SI a sistemi grandi. Per questo, è stata implementata una procedura di pre-screening, che seleziona un limitato gruppo di nodi possibili candidati a essere il punto di immissione eliminando gli altri e i relativi tratti dallo schema.

La metodologia SI è stata verificata su due differenti reti. La prima è una rete di letteratura, presa dall'esempio 8 del manuale di SWMM, mentre l'altra è una porzione del reale sistema fognario di Massa Lubrense, una località vicino Napoli, Italia. I risultati mostrano che la procedura di pre-screening riduce l'impegno computazionale significativamente e gioca un ruolo cruciale per sistemi grandi. E' stata verificata la sensitività dei risultati rispetto ai parametri da assegnare all'algoritmo genetico. Inoltre, è stata studiata l'influenza dell'incertezza dei valori di portate entranti e degli errori di misura sulla percentuale di successo nell'identificazione della sorgente. Risultati soddisfacenti sono stati ottenuti anche con significativi livelli di incertezza. Gli errori di misura hanno meno influenza sui risultati SI.

Un altro problema cruciale associato con il monitoraggio della qualità delle acque e il riconoscimento di sostanze illecite nelle fognature, è rappresentato dalla disposizione ottimale di un limitato numero di sensori. Nella tesi sono proposte diverse procedure che individuano la localizzazione ottimale usando funzioni a singolo o un multi-obiettivo. Il simulatore SWMM è usato per estrarre i dati di qualità delle acque. La prima procedura, basata sull'Information Teory (IT), considera due obiettivi: la Joint Entropy, l'informazione contenuta in un set di sensori, da massimizzare; la Total Correlation, una misura della ridondanza delle misure, da minimizzare.Nel seconda procedura multiobiettivo sono considerati il Detection Time, tempo di rilevamento di una contaminazione, che deve essere minimizzato; la Reliability, l'affidabilità del sistema di misura, che deve essere massimizzata. In entrambi i casi, i problemi multi-obiettivo sono risolti usando l'Algoritmo Genetico NSGA-II. Come terza alternativa, è stato proposta una procedura a singolo obiettivo, risolta con un algoritmo Greedy. Ulteriori procedure basate su differenti combinazioni degli obiettivi considerati in precedenza sono state in aggiunta provate. La rete di fognatura di Massa Lubrense è stata usata per verificare i risultati delle differenti procedure proposte. Una comparazione normalizzata mostra che quella Greedy rappresenta una pratica alternativa per l'ottimizzazione dell'ubicazione dei sensori nei sistemi fognari.

Samenvatting

Ongeschikt afvalwater management kan leiden tot significante schade aan de verwerkings centrale en het uiteindelijke aquatisch milieu. In het verleden kreeg afvalwaterverwerking weinig aandacht van verschillende belanghebbende, maar recentelijk paradigmaverschuiving van afvalwater en regenwater management evolueert van simpele sanitaire en hoogwaterbescherming, respectivelijk, tot een gehele milieu beschermende functie. In veel landen (waaronder de VS en EU leden) hebben operators een vergunning nodig van de regelgevende instantie om afvalwater te mogen lozen in het riool systeem.

In deze context, een erg belangrijk aspect van het riool systeem management is het detecteren en elimineren van illegale lozing, zowel opzettelijk, zoals ongeoorloofd industrieel effluent, of accidentele lozingen.

Dit PhD onderzoek bestaat uit twee delen. In het eerste deel worden problemen rond de identificatie van illegale lozingen in het riool besproken en een bron identificatie (BI) methode wordt voorgesteld. In het tweede deel worden verschillende innovatieve methodes voorgesteld om de optimale plaatsing van een beperkt aantal sensoren in het riool systeem voor een vroege waarschuwing in het geval van een verontreiniging.

In deze thesis, de BI is opgelost door een simulatie-optimalisatie model, een combinatie van de hydraulische en kwalitatieve simulatie tool Storm Water Management Model (SWMM) met generieke algoritme code (GALib) als optimalisator. Het vereeist online meetingen van enkele sensoren geplaats in een netwerk. Het SWMM wordt beschouwd als een van de standaard tools om een riool systeem te modeleren, maar het mist een programmers toolkit. Om het voorgestelde geautomatiseerde BI methode te kunnen integreren in de SWMM simulator, is er een ad-hoc toolkit ontwikkeld. Een ander aspect, vertegenwoordigd door de rekentijd die nodig is om de BI methode uit te voeren, is een groet zorg voor grote systemen. Om te voldoen aan een pre-screening procedure geïmplementeerd, gebaseerd op het vervuilings matrix concept en gelet op de topologie van riolen. De procedure selecteert een gelimiteerd groep kandidaat knooppunten en verwijderd alle overbodige knooppunten en bijbehorende koppelingen uit het schema, om de rekentijd te reduceren.

De BI methode is getest op twee verschillende netwerken. Een theoretisch netwerk uit het SWMM handleiding en een sub-stroomgebied van een bestaan riool netwerk van Massa Lubrense, een dorp in de buurt van Napels, Italië. De resultaten laten zien dat prescreening procedure de rekentijd significant reduceert en speelt een cruciale rol voor grote systemen. In het onderzoek naar de prestaties van de BI methode, zijn gevoeligheid met respect tot de generieke algoritme parameter geverifieerd. Bovendien, zijn de invloed van de onzekerheid van de toevloed waarden en van meet fouten op het resultaat onderzocht.

De analyse sugereert de the onzekerheid of toevloed de slaagkans van de BI methode beinvloed, zelfs als bevredigende resultaten worden verkregen met significante onzekerheden. De meet fouten hebben minder invloed op de BI prestaties.

Een ander kern probleem geassocieerd met water kwaliteitsmanagement van riolen wordt gerepresenteerd door de optimale plaatsing van een gelimiteerd aantal sensors voor de vroege waarschuwing van illegale bron. In deze thesis wordt de sensor locatie uitgedrukt als een single of multi-objective optimalistatie probleem en het SWMM wordt gebruikt om de waterkwaliteit data af te leiden. Verschillende formuleringen zijn voorgesteld en getest. Eerst wordt er een op informatie theory (IT) gebaseerde multi objective optimalisatie benadering gepresenteerd. De IT benadering beschouwd twee objectieve:

de gezamenlijke entropie, de informatie inhoud van een set sensoren, welke zo hoog mogelijk word gehouden; de totale correlatie, een meeting van de overtolligheid, welke zo laag mogelijk word gehouden. In tweede multi-objective benadering, waar detectie tijd wordt geminimaliseerd en de betrouwbaarheid wordt gemaximaliseerd. In beide gevallen

CHAPTER 1 Introduction Chapter 1

Nowadays, wastewater and drinking water systems are considered as the part of the critical infrastructure of a country. The wastewater infrastructure is vulnerable to accidental, deliberate or purposeful incidence. According to Bahadur and Samuels (2011), improper wastewater management could contaminate drinking water, result in catastrophic damage to the aquatic ecosystem and even life loss. In addition, the consequences could lead to the shutdown of the treatment plant, long-term public health impacts, distraction to commerce and economy, which may result in the overall disruption of the nation's way of life.

To protect the wastewater infrastructure and the workers, the manager may want to establish an early warning system (EWS). A proper placement of a limited number of sensors could minimise the complex risks associated with any contamination event.

Unlike drinking water, currently, the EWS in wastewater is still in its initial stage of development but a rapid change is evident. The current sensor technologies might not be sufficient to establish an EWS for the wastewater facilities sufficiently capable and secure enough in detecting an accidental or deliberate contamination event. However, due to revolutionary advancement in communications, information technologies and nanotechnologies the new emerging sensor technologies can be boosted up with spatial and temporal resolution and accuracy. It is more likely that in the coming year, the EWS in wastewater facilities will go beyond "merely warning the system" to identify precisely the contamination source with its characteristics.

Problem Statement

Wastewater systems in urban areas can be different in typology and size, but they all include a collection system, which can be combined or sanitary sewers. Many types of research have been done for developing different methodologies for both warnings against contaminant intrusion and contamination source detection in water distribution systems (WSSs). The identification of the contamination source in urban drainage systems (UDSs) is of particular interest because the pollutant can generate problems to wastewater treatment plant and/or the final recipient water body. Despite this fact, not many efforts have been spent on studying these phenomena in UDSs. The reasons for not having the same research in the field of UDSs are manifold. The main reason behind is the lack of immediate impact on human health as well as the complexity of the system itself which hinder to get a scenario close to the reality. In particular, in an urban drainage system, a contaminant event is represented by the intrusion of a pollutant substance, different from the usual composition of the wastewater.

In Europe, the European Commission Water Framework Directive has created a legal requirement for sewer operators to predict the flow quality as well as the quantity of the effluents of sewer systems (Schellart et al., 2008). Sewer systems can be managed and maintained either by the government or by private water companies but in each case it should be subjected to assessment by some water or environmental agency in the respective country. Generally, the regulators set two types of effluent limitations for municipalities: technology-based standards and water quality-based limits. A technologybased standard compels the authority of the municipal treatment plant to have a minimum level of technology and pollution control performance. On the other hand, water qualitybased limit, which is more stringent than technology-based standards, consider the water quality standards of the receiving water. These limits are set such a way that the discharged effluents will not exceed the assimilative capacity of the receiving waterbody [START_REF] Jining | Municipal effluent disposal standards[END_REF]. The Water Framework Directive (Directive 2000/60/EC) sets a "good ecological and chemical status of surface waterways and groundwater (implementation of the first management cycle ) by 20l5 and implementation of the third management cycle by 2027" as an objective. A sufficiently reliable sewer flow quantity and quality modelling procedures may provide relevant evidence that the sewer system is meeting accepted environmental standards to the governing bodies (Schellart et al., 2008).

For a more adequate control, different sensor technologies [START_REF] Barraud | Implementation of a monitoring system to measure impact of stormwater runoff infiltration[END_REF]Veldkamp et al., 2002;[START_REF] Grning | Investigations of the dynamic behaviour of the composition of combined sewage using on-line analyzers[END_REF][START_REF] Gruber | Continuous monitoring in sewer networks an approach for quantification of pollution loads from CSOs into surface water bodies[END_REF][START_REF] Hochedlinger | Assessment of CSO loads-Based on UV/VIS-spectroscopy by means of different regression methods[END_REF][START_REF] Bertrand-Krajewski | The OTHU case study: integrated monitoring of stormwater in Lyon, France (Chapter 23)[END_REF]Aumond & Joannis, 2008;Lacour et al., 2009;Schilperoort, 2011) have been recently developed for online monitoring of urban wastewater system. Those technologies can be a handy tool to provide vital information for detecting pollution events [START_REF] Pouet | Quality survey of wastewater discharges[END_REF] which will eventually improve the response time in case of those events. Furthermore, online monitoring allows the accomplishment of pollution load reduction policies (Fleichmann, 2007). It improves the control of industrial discharges to the sewer network [START_REF] Pouet | Quality survey of wastewater discharges[END_REF] and thus shields the wastewater treatment plant and network facilities. However, the main drawback of these methodologies is the acceptability of the performances and the maintenance of the sensors that are used for taking the measurements. Different law enforcement agencies, like EC or US-EPA, are still not very convinced on those techniques and, therefore, recommend the laboratory-based analytical techniques for wastewater monitoring.

Although, at present, none of the regulations demands a continuous monitoring of the wastewater, online monitoring systems are time demand not only just for the regulatory needs, but also for a better management of the sewer systems in general. For instance, wastewater monitoring is essential for protecting the treatment plant from malfunctioning that could be originated from an unauthorised industrial discharge or an accidental spill.

So, if somehow there exists a system that is capable of detecting any illicit intrusion in the network, an immediate action can be made by stopping that particular flow or diverting that flow into temporary reservoirs.

For the regulatory body, a paradigm shift is needed from a time intensive laboratorybased analytical procedure to an online continuous monitoring system that is capable of identifying the source of an illicit intrusion and being able to respond immediately.

Another important aspect of the sewer system management is to design the optimal placement of a limited number of sensors in the network.

This study has proposed a methodology to identify the contamination source along with its characteristics (i.e. concentration, starting time and duration of release) in a sewer network, provided that an accidental or deliberate contamination event has been detected.

At the same time, different methodologies have been proposed for the optimal placement of some limited number of sensors in the sewer systems.

Perspective of the Research

This research basically focuses on two areas of sewer system management. The first one is the Source Identification (SI) of an illicit intrusion while the other is optimal placement of a limited number of sensors. The proposed SI methodology is based on the online continuous sensor measurement. To the best of the author's knowledge no such work has been done in the field of sewer system management. This part of the study conceptually originated from a quite similar area, water distribution systems (WDS). The study of source identification in the WDS has been deeply studied in last two decades and the field is quite saturated. Most of the studies in WDS have focused on the source identification methods that use continuous sensor measurements. The inverse problem has been solved by using different optimization approaches such as, Non-linear programming (Waanders et al., 2003;[START_REF] Laird | Contamination source determination for water networks[END_REF]Laird et al., , 2006)), reduced gradient method (Guan et al., 2006), genetic algorithm [START_REF] Preis | A contamination source identification model for water distribution system security[END_REF], 2008).

The second part of this study is indebted to two distinct research areas. Some proposed methodologies are originated from the optimal sensor placement in river networks (Telci et al., 2009;[START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF] while the others derived from the water distribution networks [START_REF] Aral | Optimal Design of Sensor Placement in Water Distribution Networks[END_REF]Dorini et al., 2010). The sewer system shares similarity with the river network in terms of the flow and the topology of the network. While the flow in the river system is solely gravity driven, in the sewer system the flow is also primarily govern by gravity and in both cases the network is primarily a branched one. The main similarity among the water distribution and sewer network lies in the structural formation of the network. WDS is fully piped network while the most part of the sewer network is piped.

The specific objectives are:

 To build an ad-hoc SWMM toolkit for implementing the pollution Source

Identification (SI) methodology

 To develop a pre-screening method for reducing the computational burden during the optimisation process in SI methodology  To justify the robustness of the SI procedure through sensitivity and uncertainty analysis of different parameters  To develop a methodology for optimising water quality monitoring network of sewer systems using Information Theory (IT)

 To develop a hybrid methodology for optimising water quality monitoring network of sewer systems  To evaluate the applicability of some greedy-based algorithms, as an alternative of genetic algorithms in solving the optimisation problem, for designing the optimal location of wastewater quality monitoring network in sewer systems

Thesis Outline

Eight interconnecting chapters furnish this dissertation. The following paragraphs explain the structure of the thesis as well as the contents of each chapter.

Chapter 1 provides a general overview of the research work including the background, the problem statement, the objectives and the outline of the thesis.

Chapter 2 gives the description of newly developed SWMM Toolkit. It explains how different functions work in performing the SI methodology.

Chapter 3 presents a pre-screening method before the optimisation procedure to reduce the computation burden. It addresses both the time issue and the error associated with the implementation of the pre-screening procedure.

Chapter 4 demonstrates the proposed SI methodology with particular attention to the justification of the robustness of the methodology through sensitivity and uncertainty

Chapter 2

The Storm Water Management Model (SWMM) is considered one of the standard tools for modeling sewer systems, but it does not have the programmer's Toolkit. In this work, a Toolkit library is presented, which has been built for running wastewater quality simulations from an outside environment. An example of the developed Toolkit's use is furnished applying it to a pollution Source Identification (SI) problem, expresses as an optimisation problem. The presented example shows the capability of the Toolkit in providing a useful tool for performing network analysis from other applications and demonstrates the good performance of the proposed SI methodology.

Introduction

Wastewater systems in urban areas can be different in typology and size, but they all include a collection system, which can be combined or sanitary sewers. The good functioning of the wastewater treatment plant (WWTP) strongly depends on the quality of the wastewater. Moreover, watercourses are more susceptible to contamination when they are linked with sewer systems, because stormwater outfalls can discharge pollution from various catchment sources, such as vehicle emission, building and road corrosion and erosion, animal faeces, street litter deposition, fallen leaves and grass residues and spills. Serious short-term pollution can arise from Combined Sewer Overflows (CSOs) too.

To control those situations, modelling wastewater hydraulic and quality in sewer systems is an important basic requirement for adequate management strategies (Butler & Davies, 2004). Simplified quality models have been linked to hydraulic flow models of sewer systems for some time. By in the mid-1980s, deterministic flow models have become so popular and widespread in their use, such natural tools for the drainage engineer, that they seemed an appropriate step to developing deterministic quality models of sewer flow.

Physically-based deterministic models have become available for general use, also for quality modelling. In water distribution systems (WDSs), starting from water quality modelling, many efforts have been spent on studying the detection of contamination events (Di Cristo & Leopardi, 2008;Preis & Ostfeld, 2011;Liu et al., 2012). This topic has not been addressed in sewer systems, even though the identification and the elimination of illicit intrusions is a very important aspect of wastewater management policy. Recently, the wastewater and stormwater management is evolving from a simple sanitary and flood control to a whole environmental protection function. In many countries, such as EU and US states, operators are required to obtain a permit for discharges in sewer systems from the regulatory authority. So, a very important aspect of the sewer system management policy is represented by the detection and the elimination of illicit intrusions. Those events may generate problems to wastewater treatment plant and/or to the final recipient water body.

Moreover, for combined sewer systems intrusions are more probable as they are realised through open channel flow networks and also because the collection networks are geographically dispersed and have multiple access points, which are generally not monitored. For all these reasons, in urban drainage systems (UDSs) the identification of the source of the illicit intrusion, along with the inflow characteristics is of particular interest. A first difference in treating the contamination source identification in UDSs respect to WDSs is in the definition of a contaminant event. In the present research work, it is assumed that contamination is represented by the intrusion of a pollutant substance, different from the usual composition of the wastewater of the network. In that case, the detection of contamination in a UDS is becoming a real possibility, since the implementation in the recent years of new real-time monitoring sensor systems instead of the standard analytical procedure measurements (Al-Dasoqi et al., 2011). Assumed that, based on monitoring system measurements, an event detection procedure indicates a contamination is in act, in this paper a methodology to identify the contaminant source characteristics in a sewer network is proposed. This pollution source identification (SI) methodology is formulated as an optimisation problem, which minimises an objective function. In particular, it has been developed to identify the contamination source location, along with its main characteristics, represented by the input concentration, starting time and intrusion duration. The SWMM is used as hydraulic and water quality simulator, while a Genetic Algorithm (GA) code is adopted for solving the optimisation problem. One of the major limitations in using the SWMM software in the SI methodology is the unavailability of a complete programmer's Toolkit as the hydraulic network simulator EPANET (Rossman, 1999) does. Several researchers (Morley et al., 2000;Van Zyl et al., 2003;Guidolin et al., 2010) have made their effort to improve the existing EPANET Toolkit, but no such effort have been seen so far in the case of SWMM.

The current SWMM dynamic link library (DLL) consists of just nine functions, which are insufficient to perform any simulation from another platform (e.g. C++). To integrate the SWMM simulator with the proposed automated SI methodology, an ad-hoc SWMM-TOOLKIT is necessary to establish communication from an outside environment.

In doing that, some 33 additional functions have been created for retrieving information about network nodes and time patterns, as well as for setting new values for the extended period simulation from a C++ platform. An application of the SWMM-Toolkit for running the proposed SI methodology is presented performing an example test considering the literature network Example 8 of SWMM manual (Gironás et al., 2009) in dry weather condition.

The Source Identification Methodology

To date, most of the researches on contamination event detection are primarily focused on WDSs due to high concern about the public health in case a pollutant is introduced into the system either deliberately or accidentally. The current literature reflects how

WDSs security related research has evolved in two seemingly separate directions (Tryby et al., 2010): (1) the contamination detection with optimal sensors displacement for an early warning (Ostfeld & Salomons, 2004;Ostfeld et al., 2004;Cozzolino et al., 2006;[START_REF] Edthofer | Reliable online water quality monitoring as basis for fault tolerant control[END_REF][START_REF] Cozzolino | Stochastic approaches for sensors placement against intentional contaminations in water distribution systems[END_REF] and ( 2) the pollution source identification problem. The studies that deal with the SI problem (Laird et al., 2006;Di Cristo & Leopardi, 2008;Preis & Ostfeld, 2008;[START_REF] Huang | Data mining to identify contaminant event locations in water distribution systems[END_REF]Zechman & Ranjithan, 2009;[START_REF] De Sanctis | Real-time identification of possible contamination sources using network backtracking methods[END_REF][START_REF] Di Cristo | Closure to "Pollution Source Identification of Accidental Contamination in Water Distribution Networks" by Cristiana Di Cristo and Angelo Leopardi[END_REF]Tryby et al., 2010) are devoted to identify essentially the intrusion point location, along with the main characteristics of the inflow. In particular, Preis and Ostfeld (2011) proposed a genetic algorithm-based contamination source detection model that was further embedded in a statistical framework for quantifying the uncertainty of a contamination source detection outcome.

Very rare efforts have been made in studying the effect of an illicit injection in a UDS (Field et al., 1994;Irvine et al., 2011), and in particular for the pollution source identification problem. The primary goal of a SI problem is to estimate quickly the source characteristics that best explain the observed contamination data. In the following an original SI methodology for UDS is presented, which involves the recognition of the injection location, the input start time, duration and magnitude. However, the use of such kind of methodology requires sensor measurements and a strategy to detect that an event is occurring, like the one proposed for WDS in [START_REF] Oliker | A coupled classification-Evolutionary optimisation model for contamination event detection in water distribution systems[END_REF]. In this preliminary presentation, it is assumed that input pollutant is a conservative substance,

The SWMM Toolkit Description

The idea of making a SWMM Toolkit derived from the necessity of implementing the for each reporting period and writes out selected values to a formatted report file (.RPT).

Any error or warning messages generated during the run are also written to this file.

Different Toolkit functions have been generated to carry out all of these steps under the programmer's control, including the ability to read or modify some of the most important system's global data, related to the SI problem. In particular, the newly built Toolkit functions can be classified into six types according to the tasks they perform. The first type, which consists of two functions, is basically for opening and closing the SWMM The main Toolkit functions used in performing the SI methodology are:

 Calling OWNswmm_open function to open the Toolkit system along with the SWMM input file and the SENSOR text file, which contain the measurements of the time series concentration of the pollutants observed through the sensors.

 Using SWMMsetXXX series of functions to change system characteristics.

 Running a simulation time step using the OWNswmm_step function. If needed, SWMMsetXXX series of functions can be used to reset system characteristics.

Finally calling OWNswmm_close function to close all files and release system memory.

Application and Results

To show an application of the proposed SI methodology with the SWMM-Toolkit the literature network reported in Example 8 of the SWMM application manual (Gironás et al., 2009) has been considered, even though some characteristics have been modified. Two input files are mandatory to accomplish the SI methodology. One is the SWMM input file (.INP), with all data describing the network; the second is a text file SENSOR having the time series concentration measurements from the monitoring stations. In the presented test, 6 sensors are assumed in the nodes J1, JI2, JI3, JI4, JI5 and JI7 (Figure 2.3). The synthetic measured data have been generated through a SWMM quality simulation considering as "true" contamination scenario an injection of a conservative contaminant at node J1 with a concentration of 2 mg/l starting at 8 a.m. with duration of 3 hours. The simulation was run from 6:00 to 14:00, with a routing time step of 30 s. This duration was fixed considering the wastewater traveling time in the network. The first detection of the contamination was revealed by sensor J1 at 10:00. The generated synthetic sensor text file, along with the SWMM input file was used for running the SI methodology. The following GA parameters were chosen: number of population =100; number of generation = 100; mutation probability = 0.01 and crossover probability = 0.9.

Applying the SI methodology presented in section 2.

Conclusions

The chapter is focused on the presentation of newly built Toolkit functionality for SWMM, realised to perform more complex applications related to wastewater hydraulic and quality simulations, such as optimisation methodologies that require running many system analyses with modified input parameters. Different Toolkit functions have been generated, including the ability to read or modify some of the most important system's global data. In particular, the new Toolkit functions can be classified into six types according to the tasks they perform. The first type is basically for opening and closing the SWMM Toolkit system while the second one is for retrieving information about network nodes. The third type retrieves information about the used time pattern and the fourth group is for getting other relevant information of the network like number of network components of a specified object type, flow unit, starting/ending/reporting time and step, duration, etc. The penultimate group of functions can set new values for node parameters and time pattern, and then the last group is for customising a simulation or for doing some specific tasks such as screening of a network.

The idea of making a SWMM Toolkit is derived from the necessity of implementing a methodology for solving a pollution source identification (SI) problem in sewer systems.

The proposed methodology expresses the SI as an optimisation problem that was solved using a Genetic Algorithm code combined with SWMM. Moreover, a preliminary test in applying the proposed SI methodology to a literature sewer system is presented, showing the capability of the Toolkit in providing a useful tool for performing network analysis from other applications. The results also demonstrate a good performance of the SI methodology. More detailed study on the SI methodology is demonstrated in chapter 2 and 3.

Al Ostfeld, A., Kessler, A., & Goldberg, I. (2004). A contaminant detection system for early warning in water distribution networks. Eng. Optimiz.,36(5), 525-538. [START_REF] Preis | A contamination source identification model for water distribution system security[END_REF]. A contamination source identification model for water distribution system security. Eng. Optimiz., 39 (8), 941-947. Preis, A., & Ostfeld, A. (2008). Genetic algorithm for contaminant source characterisation using imperfect sensors. Civ. Eng. Environ. Syst.,25(1), 29-39. Preis, A., & Ostfeld, A. (2011). Hydraulic uncertainty inclusion in water distribution systems contamination source identification. Urban Water J., 8(5), 267-277. Illicit intrusions in Sewer Systems (SSs), modifying the wastewater characteristics, may create problems in the treatment plant and/or the final recipient water body. For this reason, the source identification (SI) problem is becoming an important issue also in SSs.

Appendix

For large systems, the computational burden might make the SI methodologies impractical. In this chapter, a pre-screening procedure, based on the pollution matrix concept, is introduced and applied before the SI methodology. Selecting a group of possible candidate nodes and cutting consequently the scheme, a significant improvement both in terms of time and the accuracy is obtained.

Introduction

Nowadays, wastewater and drinking water systems are considered as the part of the critical infrastructure of a country. According to Bahadur and Samuels (2011) improper management of wastewater facilities could result in loss of life; catastrophic damage to flora and fauna; and contamination of drinking water supplies. In addition, the consequences could result in long-term public health impacts, disruption to commerce and economy, which may lead to the overall disruption of the nation's way of life.

Although in past the wastewater and stormwater management have not got much attention from the researchers, a paradigm shift is evident evolving from simple sanitary and flood controls to overall environmental protection function. In many countries permit is mandatory for the operator to discharge their wastewater into the sewer systems (SSs).

The security has been made top priority in some country, like USA, where the SSs have been determined to be at risk to accidental and deliberate intrusion events. In this context, a very important aspect of the SSs management policy is to set up an early warning system for reliably identifying high-impact illicit intrusion events. With the newly available methodologies, which permit on-line monitoring in SSs (e.g. [START_REF] Llopart-Mascaró | Guidelines for on-line monitoring of wastewater and stormwater quality[END_REF][START_REF] Qin | Wastewater quality monitoring system using sensor fusion and machine learning techniques[END_REF], the development of these tools will provide the operational staffs to take corrective action to minimise the impact of such intrusions.

An important aspect of a good SSs management policy is represented by the identification of the input source and its characteristics. Source identification in water distribution system has got enormous attention to the researchers in the last decades. The same topic has not attained the same pace in the case of SSs mainly due to the lack of immediate and direct influence on public health. Few rare efforts have been reported in the literature. Field et al. (1994) and Irvine et al. (2011) have proposed methodologies to identify the illicit discharges in a separate storm drainage system, where the injection source is identified through sampling and analytical laboratory analysis. To the best of the authors' knowledge, the methodology proposed by Banik et al. (2014) is the first effort made based on online sensor measurements to characterise illicit intrusion in a combined sewer system. Banik et al. (2014) have proposed a methodology for the identification of the source location, along with its characterisation, represented through released input concentration, starting time and duration, in SSs. They have used the storm water management model (SWMM) to perform the hydraulics and water quality simulations and genetic algorithm for solving the source identification (SI) problem. The method (Banik et al., 2014) works fine with small networks as it takes a tiny amount of time to run a single simulation. However, in real life the size of the network is much larger, and so the needed computational effort will eventually make the method impractical. So, developing a methodology for solving the SI problem within a reasonable time is a challenging but important engineering problem.

This chapter presents an original research of a newly developed pre-screening procedure to apply before the SI methodology. The proposed procedure uses the pollution matrix (Kessler et al., 1998;Di Cristo & Leopardi, 2008) concept to identify a set of ʻCandidate' nodes. Once the possible candidates are identified the unnecessary elements of the network are removed by cutting some parts of the scheme. The flow coming from the cut parts are added to the next node of the remaining scheme, assigning a new average inflow and a new time pattern. The inflow is estimated from the last link of the cut portion while the time pattern is estimated from the downstream link next to the node, where the value has to be assigned. In the subsequent SI optimisation process, only the ʻCandidate' nodes are considered. So the computational time is reduced in two ways: i) reduced number of genetic parameters, being the search domain smaller; ii) less time require for an individual SWMM simulation, being the considered scheme smaller.

The chapter is organised as follows. It starts with the formulation of the SI methodology, along with the presentation of the optimisation procedure. The third section is devoted to the detailed description of the proposed pre-screening methodology. In the application and result section, the methodology is tested on two sewer systems, with increasing complexity: a literature scheme from the SWMM manual and a real combined sewer. In the final section, some concluding remarks and recommendations are drawn.

Source Identification (SI) Methodology

The main goal of a SI methodology is to characterise the source of an illicit intrusion when it is detected in a sanitary or combined sewer system. The SI methodology proposed by Banik et al. (2014) is formulated as an optimisation problem that uses sensor measurements through on-line monitoring. For its solution, two vital components are required: a model for hydraulic and quality simulations in sewer systems and an optimisation problem solver. In particular, the USEPA's SWMM (Rossman, 2010) is used to perform the hydraulic and water quality simulations, whereas the genetic algorithm library, GALib [START_REF] Wall | GAlib: A C++ library of genetic algorithm components[END_REF], is used to solve the optimisation problem.

In the present chapter, a third component is introduced: a pre-screening procedure, to reduce the computational effort in case of large schemes. The proposed SI methodology consists of two main parts, as depicted in Figure 3.1:

 In the first part a group of candidate nodes, a subset of all nodes in the system, are selected through a pre-screening procedure, which is explained in more details in section 3.3.

 In the second part, among the candidate nodes the approximate location of the intrusion point with its characteristics (input concentration, starting time and duration) is determined through a SWMM-GA optimisation tool.

SI problem formulation

The SI problem is formulated minimizing a dimensionless objective function, F, defined as the normalised square difference between the simulated and the measured contaminant concentration values. The adopted mathematical form of F is:

𝐹 = ∑ ∑ ( 𝐶 𝑖𝑡 𝑜𝑏𝑠 -𝐶 𝑖𝑡 (𝐿, 𝐶 0 , 𝑇 0 , 𝐷) (𝐶 𝑖𝑡 𝑜𝑏𝑠 + 𝐶 𝑖𝑡 (𝐿, 𝐶 0 , 𝑇 0 , 𝐷))/2 ) 2 𝑁 𝑠 𝑖=1 𝑡 𝑐 𝑡=𝑡 0 (3.

SWMM-GA simulation optimisation procedure

As mentioned above, the USEPA's SWMM is used to perform the hydraulic and water quality simulations, whereas the genetic algorithm library, GALib, is used to solve the optimisation problem. Genetic Algorithms (GAs) are already widely used in optimisation problems related to water resources planning and management researches [START_REF] Nicklow | State of the art for genetic algorithms and beyond in water resources planning and management[END_REF]. Thus, many of their technical details are not reported herein. Briefly, GAs are a heuristic combinatorial search technique that mimics the natural evolution process of

The Pre-screening Procedure

The simulation-optimisation procedure, based on a number of consecutive simulations, is computationally expensive and not easily applicable for a large network. Using the measured concentrations, the pre-screening procedure selects a limited group of possible candidate nodes, excluding from the search domain the nodes that cannot be the location of the source. All the unnecessary nodes and their associated links are then cut from the scheme, to apply the SI methodology on a smaller system. In this way, due to the small number of candidate nodes, the simulation time is reduced because the GA parameters can be set to smaller values, which means a small number of runs. At the same time, being the "cut" network small, the required time for each single simulation is less. The corresponding inflows coming from the cut portion of the network are successively integrated with the remaining network.

The proposed pre-screening procedure, based on the pollution matrix concept, assumes that all wastewater passing through the intrusion point is considered contaminated. Di

Cristo and Leopardi ( 2008) have used this concept along with the water fraction matrix (Kumar et al., 1997) one to select a group of candidate nodes before applying a pollution source location methodology in water distribution networks. The main difference of the presented pre-screening procedure with the one proposed by Di Cristo and Leopardi ( 2008) are twofold. First of all in the current procedure the SWMM run is done only once, whereas for the previous procedure a total number of EPANET runs equals to the number of nodes in the network is required. Secondly, while in the previous method the network has the same size after pre-screening, in the current procedure the unnecessary part of the network is cut from the original scheme.

The pre-screening procedure, as schematically shown in Figure 3.1 (top right corner), starts with reading the sensor input file, which contains the sensor node indices and the corresponding time series of concentration measurements. The following paragraphs describe the four main steps of the proposed pre-screening procedure.

Step1: adjacency matrix

The first step of the pre-screening procedure consists of formulating the adjacency matrix, which is a N×N matrix having 0-1 coefficients, where N is the number of nodes, including tanks and reservoirs. The adjacency matrix (A) contains the information of whether the water directly travels from a particular node to another node (not via another node). If water travels directly from node i to node j then the coefficient of the element of the adjacency matrix is "1", otherwise it is "0". The pollution matrix is then formed from it.

Step2: pollution matrix

Once the adjacency matrix (A) is formed, the pollution matrix (P) can be constructed by using slightly modified Floyd-Warshall algorithm (Floyd, 1962), which has been used

extensively for finding the shortest path in a network. The pollution matrix is also a N×N matrix of 0-1 coefficients, where N is the number of nodes with "1" and "0" values corresponds to polluted and unpolluted nodes, respectively. The i th row of the pollution matrix represents the situation of the nodes in case of a pollution event in node i. The "1" values in the j th column represent all the nodes that can pollute node j (domain of coverage of node j). The pollution matrix P is formed using the following pseudo code: Finally, all diagonal elements are assigned as "1".

1. P = A 2. For k = 1 to

Step 3: candidate nodes

Once a nonzero measurement is read from a monitoring station in a node, the nodes of its domain of coverage are probable candidates. The final group of candidate nodes will be formed from the intersection of the domain of coverage of all sensor nodes with a nonzero measurement. Conversely, all zero measurements in a sensor node mean that the nodes of its domain of coverage have to be excluded from the group of candidates.

Mathematically the array of the candidate nodes S can be expressed as:

𝑆 𝑗 = ∏ 𝑃 𝑗𝑘 𝑓𝑜𝑟 𝑗 = 1 𝑡𝑜 𝑁 𝑀 𝑘=1 (3.2)
where N = number of nodes in the network; M = number of sensor nodes having at least one nonzero measurement; and k = node equipped with the k th sensor. Pjk is the j th row and k th column element in the pollution matrix which is either "0" or "1". If S is "1", the node j is assigned to the candidates. The number of candidate nodes will guide to fix the genetic algorithm parameters. The pseudo code for getting candidate nodes are shown below:

1. End for loop at row 1

For i = 1 to

Step 4: cut unnecessary network

Once the candidate nodes are known, the next task is to find which nodes are linked with them to all the ways to the outfall or treatment plant. They are connecting nodes, and they cannot be cut. As shown in the example scheme reported in Figure 3.2, the "nodes to be cut" are then simply formulated by subtracting the connecting nodes from the total nodes.

Those nodes and their associated links are cut from the original network, but the associated flow coming from that part needs to be integrated with the remaining network.

Two other arrays namely "last link of cut part" and "next link" are created to compute the average inflow and the new hourly time pattern of the immediate next downstream node "N( 7)" (Figure 3.2), respectively.

The array "last link of cut part" consists of all downstream links of each cut portion that were connected to the original network before the screening operation. The flow within those links is put into the corresponding next downstream node "N( 7)". At the same time the pattern factors at "N( 7)" has to be changed. These new pattern factors are calculated based on the flow within the next link (Figure 3.2) of node "N( 7)". Then the average inflow to add at node "N( 7)" is calculated as follows:

𝐷𝑊𝐹 𝑎𝑣𝑔 = 1 𝑛 ∑ 𝑥 𝑖 𝑙𝑎𝑠𝑡 𝑛 𝑖=1 1 𝑚 ∑ (𝑝𝑓) 𝑗 𝑛𝑒𝑥𝑡 𝑚 𝑗=1 (3.3)
where, n is the total number of flow data at last link; x i last is the i th flow data in the last link; m is the number of pattern factors during the simulation period; (pf) j next is the new j th pattern factor calculated from the next link.

Once the new inflows and the new time pattern are added to node "N( 7)" all the unnecessary part of the network is cut and a new input file is prepared for the next SWMM run.

Example of the pre-screening procedure

The entire pre-screening procedure is applied considering the simplified scheme in Figure The domains of coverage of two sensors are represented by the elements having value "1" of the corresponding columns in the pollution matrix. So, the domains of coverage of two sensors are:

3 → {1, 2, 3} 7 → {1, 2, 3, 4, 5, 6, 7}
The candidate nodes are furnished from the intersection of the domain of coverage among two sensors: {1, 2 and 3}.

Then, the connecting nodes are calculated by taking the union of the corresponding rows of the candidate nodes (i.e. rows 1, 2 and 3) in the pollution matrix. So, the connecting nodes are {1, 2, 3, 7 and 8} and the nodes to be cut are {4, 5 and 6}. The arrays of "last link of cut part" and "next link" are formed. For this particular case, both arrays have only one element, and they are {last link} and {next link} respectively. The average flow in "last link", computed through Eq. (3.3), is added to the inflow of node N( 7), while the flow in "next link" is used to calculate the new time pattern factors of node N [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]. Then all the unnecessary part (nodes in "nodes to be cut" array and their corresponding links) is removed from the original network, and a new input file will be ready for the next part of SI methodology.

Application and Results

The applicability of the proposed methodology has been tested on two different schemes:

the literature system Example 8 from the SWMM5 application manual (Gironás et al., 2009) and the existing sewer Massa Lubrense11, located near Naples, Italy. In both cases, only dry weather flow (DWF) is considered and a conservative pollutant is assumed. A six-hour simulation time starting from 8:00 a.m. is applied, and the entire procedure is replicated 50 times to observe the success percentage in identifying the correct node. The GA parameters are chosen as: Population = 100, Generation = 40, Mutation Probability = 0.01 and Crossover Probability = 0.9. All the simulations have been performed on an

Intel Core i7-4700MQ CPU @ 2.40 GHz processor, 20 GB RAM machine. It must be noted that five executables have been run simultaneously in the case of Massa Lubrense11 to save the overall simulation time. So, one replication will refer to a set of five parallel simulations for this case.

SWMM example 8 system

The SWMM Example 8 system is presented in Figure 3.3. It is a combined sewer network, which serves an area of 0.12 km 2 , and consists of 31 nodes (28 junctions, two outlets and a storage unit), 35 links (29 conduits, one pump, one orifice and four weirs). There are two outlets, the wastewater treatment plant (WWTP) and the outfall for discharging the combined sewer overflow, in the system. In

Massa Lubrense11 system

The system Massa Lubrense11, presented in Figure 3.4(a), is one of the 12 subcatchment of the real sewer system of Massa Lubrense, a town located near Naples, Italy. It is a combined sewer system, covering an area of 0.75 km 2 . The scheme consists of 242 circular conduits connecting 241 junctions, one pump, two storage units and one outfall.

The DWF distribution is also depicted in Figure 3.4(a).

The "true" pollution scenario is a three hours continuous injection of a pollutant at node "N16" with a concentration of 20 mg/l starting from 9 a.m. The system is analyzed with a routing time step of 10 seconds and a reporting time step of 10 minutes. Three monitoring stations are arbitrarily chosen at nodes N42, N241 and N219 [Figure 3.4(a)],

and the synthetic sensor measurements are generated through a SWMM quality simulation.

Results

In applying the pre-screening procedure, two schemes are reduced as shown in Table 3.2 reports a summary of the SI methodology results for the two considered test cases obtained with and without applying the pre-screening procedure. Column (2) and ( 6) report the success percentage in identifying the correct node while column (3) and ( 7)

show the estimated average input concentration. Column ( 4) and ( 8) present the total simulation time consumed due to all SWMM runs associated with one replication, whereas column ( 5) and ( 9) indicates the time consumption due to the GA optimisation in one replication. Using the pre-screening procedure described in this chapter a significant reduction in computational effort, is observed, especially in the case of the large network. For the network Massa Lubrense11, a set of five complete SWMM-GA optimisations (one replication) has taken 2:34:31 hours, which compared with the 10:01:30 hours requirement without the pre-screening produces the 75% reduction in the overall computational effort. It is interesting to note, from Table 3.2, that the success percentage remains same after applying the pre-screening procedure for the SWMM example, whereas an improvement is observed for the system Massa Lubrense11. This change is due to the reduction of the search domain used for the optimisation procedure. The improvement is also noticed in estimating the source concentration for the case of Massa Lubrense11. A more detailed study on this methodology along with sensitivity analysis on GA parameters as well as the uncertainty analysis on inflows and sensor measurement can be found in chapter 4 [START_REF] Banik | Evaluation of different formulations to optimally locate pollution sensors in sewer systems[END_REF].

Conclusions

Computational burden is a critical issue in applying a Source Identification (SI) methodology to sewer systems. A pre-screening procedure, based on pollution matrix concept, has been developed to apply it prior to a previously proposed SI methodology in which the SI is expressed as an optimisation problem. Starting from sensor measurements, the pre-screening procedure selects a group of candidate nodes, which constitute the search domain in the optimisation procedure, removing all the unnecessary parts of the scheme and producing a significantly small network. The flow associated with the removed part is integrated with the remaining one. The SI methodology performance with the pre-screening procedure is tested on two different schemes: a small literature system and a real large sewer. It is observed that the introduction of the prescreening produces a significant improvement both in terms of time and the success percentage in identifying the correct location, especially for the large network.

The position of the sensors could be a vital issue for the effectiveness of the pre-screening procedure. In the present study, the sensor placement in both networks is done randomly, and no optimality test has been performed regarding their locations. The optimal placement of the monitoring stations in a sewer network is demonstrated in chapter 5, 6

and 7 (Banik et al., 2015a(Banik et al., , 2015b;;Banik et al., 2015c).

Chapter 4

A very important aspect in sewer systems management is represented by the detection of illicit intrusions, which can be intentional, such as unauthorised industrial effluent, or accidental spills. This increasing need, along with the requirement of pollution load reduction strategies, has supported the development of online sensors for wastewater quality monitoring. A new methodology for characterising an illicit intrusion in a sanitary or combined sewer system has already been described in chapter 2 and 3. The methodology uses online pollutant concentration measurements, and the source identification (SI) problem is formulated as an optimisation problem, solved combining the hydraulic and quality simulation tool storm water management model (SWMM) with a Genetic Algorithm (GA) code. It also coupled with a pre-screening method prior to the optimisation procedure. This chapter demonstrates a more in-depth study of the methodology with the particular attention to the robustness of the procedure through sensitivity and uncertainty analysis.

Introduction

Wastewater and stormwater management are evolving from a simple sanitary and flood control to an overall environmental protection function. The knowledge of the quality of the collected wastewater in both dry and wet weather conditions is a vital basic requirement for adequate management strategies. In fact, wastewater quality not only influences the good functioning of the system but in combined sewers, when discharge exceeds the treatment capacity, raw effluents are spilled directly to water bodies. Many studies (Gromaire et al., 2001;Diaz-Ferros et al., 2002;Even et al., 2004) have shown the severe impact of the pollution on the receiving water bodies due to the presence of combined sewer overflows. For this reason, models for the characterisation of the wastewater have been widely studied for assessing the pollution load overflowed and/or transferred to the wastewater treatment plant (Obropta & Kardos, 2007). On the other side, a control on the kinds of the system inputs is crucial.

Operators have to require usually a permit for discharging in sewer systems from the regulatory authority and some countries, such as Italy (e.g. Italian Legislative Decree 152/06), the service price has to take into account both the quantity and the quality of discharged wastewater. In this context, a crucial aspect of the sewer systems management policy is the detection and the elimination of illicit intrusions, which can be intentional, such as unauthorised industrial effluent, or accidental spills. Moreover, in combined sewers illicit discharges are more probable as they are realised through open channel flow systems and also because the collection networks are geographically dispersed and have multiple access points, generally not monitored. Uncontrolled discharges could severely damage the sewer's facilities and the wastewater treatment plant, along with the impact mentioned above on the water bodies.

The problem of the contamination detection in water distribution systems (WDS) has been deeply studied in last decades, due to the high concern about the direct effect on the public health. Researches related to drinking water quality in distribution systems have investigated different aspects: identification of a pollution source (Laird et al., 2006;Di Cristo & Leopardi, 2008;Preis & Ostfeld, 2008;Huang & McBeanl, 2009;Zechman & Ranjithan 2009;[START_REF] De Sanctis | Real-time identification of possible contamination sources using network backtracking methods[END_REF]Tryby et al., 2010), optimal sensors displacement for an early warning (Ostfeld & Salomons, 2004;Ostfeld et al., 2004;[START_REF] Cozzolino | Stochastic approaches for sensors placement against intentional contaminations in water distribution systems[END_REF][START_REF] Edthofer | Reliable online water quality monitoring as basis for fault tolerant control[END_REF] The problem of the identification of illicit intrusions in sewers shares similarities respect to the application to water distribution systems, but it also presents strong differences. In particular, since the collected liquid is a complex heterogeneous mixture, the contamination event has to be properly detected denoting differences in the usual composition of the wastewater. The identification of an anomalous behaviour has been an almost impossible task before that continuous monitoring of pollutant loads becomes feasible, thanks to the development of new sensors technologies (e. g. Bourgeois et al., 2001). Pollution concentrations have been traditionally measured extracting samples manually or automatically and then analysing them in the standardised laboratory.

However, this method contains major drawbacks represented by the high costs, which usually imposes short-duration campaigns with limited information obtained at insufficient time intervals, not completely representative of the wastewater pollutant dynamics.

Recently, many on-line quality continuous measurement systems with in-sewer sensors have been developed mainly for storm water monitoring (Metadier & Bertrand-Krajewski, 2012;Lacour et al., 2009). For wastewater, the complex pollutant matrix, the generally hostile environment, the necessity of resistant sensors, along with the costeffectiveness represent serious problems in developing the on-line monitoring systems.

However, the increasing need for detecting contamination events [START_REF] Pouet | Quality survey of wastewater discharges[END_REF] and the implementation of pollution load reduction strategies have supported the development of online sensors for wastewater quality monitoring [START_REF] Llopart-Mascaró | Guidelines for on-line monitoring of wastewater and stormwater quality[END_REF]. Many options are available, using different technologies [START_REF] Thomas | Wastewater quality monitoring[END_REF][START_REF] Qin | Wastewater quality monitoring system using sensor fusion and machine learning techniques[END_REF]. Specific methodologies have been also realised for detecting harmful substances, for example biosensors for heavy metals detection (e.g. [START_REF] Olaniran | Whole-cell bacterial biosensors for rapid and effective monitoring of heavy metals and inorganic pollutants in wastewater[END_REF] or chemical sensor array for checking the presence of organic compounds in domestic wastewater (Burgeois & Stuetz, 2002). The new option of continuous on-line wastewater monitoring opens the possibility of applying pollution source identification procedures to sewer systems, to identify any illicit intrusions.

Few rare efforts have been made to identify illicit injections in a separate storm drainage system (Field et al., 1994;Irvine et al., 2011), using essentially sampling and analytical laboratory analyses. In fact, despite the many methodologies developed for pollution source identification in water distribution networks, no one has been applied to a sewer system. The main novelty of the presented work is represented by the use of a source identification methodology for characterizing an illicit intrusion in sewers. In particular, the new proposed methodology uses on-line pollutant concentration measurements and formulates the source identification as an optimisation problem. It is solved combining a hydraulic and quality simulation tool with an optimisation problem solver. Even if the proposed procedure shares similarities with other methodologies developed for water distribution networks, it is original in both the formulation and the software structure.

In applying the source identification procedure to real systems, the computational effort, which significantly increases with the system size, may represent a serious limitation [START_REF] Di Cristo | Closure to "Pollution Source Identification of Accidental Contamination in Water Distribution Networks" by Cristiana Di Cristo and Angelo Leopardi[END_REF]. For this reason, the first part of the proposed methodology is represented by a pre-screening procedure to reduce the number of nodes before the optimisation routine. Moreover, other important aspects that make the source identification problem a challenging task are the presence of measurement errors and the uncertainty in estimating some input parameters such as the inflows (Propato et al., 2010).

In the presented work an uncertainty analysis using the Latin Hypercube Samples (LHSs) method is performed for checking the robustness of the methodology respect to inflows uncertainty and in the presence of measurement errors. Besides, a sensitivity analysis is also performed on the GA parameters.

The methodology is applied to two different networks with increasing size and complexity: the literature network Example 8 of the SWMM application manual (Gironás et al., 2009) and the real test-case represented by the sewer system Massa Lubrense11.

The chapter is organised in the following way: in the first part the proposed SI methodology is presented, including the SWMM-GA optimisation and pre-screening procedures; in the second part the two considered test cases are described, along with the results obtained; finally some concluding remarks are drawn.

Methodology

The main objective of the proposed methodology is to characterise the source of an illicit intrusion when it is detected in a sanitary or combined sewer system. Despite having the complex heterogeneous nature of the wastewater, an anomalous contamination event in it is assumed to be identified by the presence of kinds and/or quantity of substances, different from the usual composition of the wastewater. The use of the proposed methodology requires sensor measurements and a strategy to detect that an anomalous contamination is occurring, like the one proposed for WDS by [START_REF] Oliker | A coupled classification-Evolutionary optimisation model for contamination event detection in water distribution systems[END_REF].

The source identification problem, which includes the finding of the input location and the contaminant release history, is formulated as an optimisation problem. For its solution, two main components are required: a model for hydraulic and quality simulations in sewer systems and an optimisation problem solver.

Since an important drawback in solving the SI problem can be the computational effort, a pre-screening procedure is herein coupled to select a subset of all nodes in the system, named candidate nodes, which are the only possible intrusion points.

Source identification problem

The intrusion source is herein characterised regarding injection location and contaminant loading history, including the intrusion starting time, the release duration, and magnitude.

In the present version of the proposed methodology, the following basic hypotheses have been made:

 the contaminant, also named pollutant, is conservative, such as a heavy metal, because the absence of decay makes the contamination problem more dangerous  the intrusion is assumed to happen at only one node, even if an extension to multiple sources could be successively performed  the contaminant intrusion is continuous in the release time interval with constant concentration  some monitoring stations, able of furnishing contaminant concentration measurements, are installed in fixed positions of the system

The injection point can be any of the system input nodes while the intrusion can start at any time during the simulation period.

The source identification problem is formulated minimizing a dimensionless objective function, F, defined as the normalised square difference between the simulated and the measured contaminant concentration values. The adopted mathematical form of F is: (4.1)] is obtained modifying the values of these variables. For solving the optimisation problem the linked simulation-optimisation procedure, described in the following, has been developed.

𝐹 = ∑ ∑ ( 𝐶 𝑖𝑡 𝑜𝑏𝑠 -

SWMM-GA simulation-optimisation procedure

Among the different modelling packages available, the USEPA's SWMM model (Rossman, 2010) is used to perform the hydraulic and water quality simulations, whereas the genetic algorithm library GALib [START_REF] Wall | GAlib: A C++ library of genetic algorithm components[END_REF] is used to solve the optimisation problem.

Genetic Algorithms (GAs) are already widely used in optimisation problems related to water resources planning and management researches [START_REF] Nicklow | State of the art for genetic algorithms and beyond in water resources planning and management[END_REF]. Thus, many of their technical details are not reported herein. Briefly, GAs are a heuristic combinatorial search technique that mimics the natural evolution process of chromosomes. A typical GA, like the one incorporated into the methodology, starts with the generation of a random set of strings (population), then the objective function score is evaluated for each string (individual). Then the algorithm generates a new set of strings through selection, crossover and mutation. The above steps are repeated until the selected stopping criterion is attained.

In the present study applying the GA, a binary-to-decimal mapping (counting in base 2)

is used to represent a string, with a single binary-to-decimal phenotype (variable), that contains the number of bits used to represent its decimal value. For each considered variable (N, C0, T0, D) the length of the variable in bits along with minimum and maximum values are defined. C0 is codified as floating number while the other three as integers. The variable N varies between 0 and the number of candidate nodes in the scheme while the minimum and maximum values of C0 are selected according to the measurement instrument thresholds. The minimum (maximum) value of T0 is selected as the time in which the first non-zero concentration is measured by a sensor minus the maximum (respectively minimum) path time for reaching the measurement point from another node. The minimum of the release duration, D, is the time step while the maximum value is considered equal to the maximum among the time intervals in which sensors reveal a non-zero concentration.

About the genetic operators, the Roulette wheel method with the scaled (fitness) scores is used for selecting an individual. A flip mutation operator is adopted for flicking the bits in the string with a given mutation probability while one point crossover is used with parents generating two children. The GA search stops when the number of generations reaches the predefined values, fixed through a sensitivity analysis, as usually done in the literature [START_REF] Preis | A contamination source identification model for water distribution system security[END_REF].

The SWMM tool, used for hydraulic and quality simulation, is a well documented and widely used public software for the sewer system. In performing the hydraulic and quality simulations, the dynamic wave, and the water quality routing models, described in the SWMM manual, have been used, respectively. For the quality simulation the contaminant is defined, assuming that it is not generated by land use, and it is introduced into the source node with a fixed constant concentration during the release duration. No transformation during the transport process is considered, coherently with the assumed basic hypothesis of conservative contaminant. To integrate the SWMM simulator within the proposed methodology, an ad-hoc SWMM-TOOLKIT has been developed, because the SWMM does not have a programmer's Toolkit, as available for the hydraulic network simulator EPANET [START_REF] Rossman | EPANET 2: users manual[END_REF]VanZyl et al., 2003). The Toolkit is a Dynamic Link Library (DLL) of functions, which allows the software solution engine to perform specific applications and needs from an external platform (e.g. C++). The new SWMM.DLL used in this study has 33 additional functions for retrieving information about network nodes and time patterns, as well as for setting new values for the extended period simulation from a C++ platform. The developed functions are reported in Banik et al. (2014) with a description of their characteristics.

Pre-screening procedure

The simulation-optimisation procedure, based on a number of consecutive simulations, is computationally expensive and not easily applicable to a large network. Using the measured concentrations, the pre-screening procedure selects a limited group of possible candidate nodes, excluding from the search domain the nodes that cannot be the location of the source. All the unnecessary nodes and their associated links are then cut from the scheme, to apply the methodology to a smaller system. In this way, considering only the scheme with candidate nodes, the simulation time is reduced because the GA parameters can be set to smaller values, which means a small number of run. At the same time, being the "cut" network small, the required time for each SWMM simulation is less.

The proposed pre-screening procedure, based on the pollution matrix concept (Kessler et al., 1998;Di Cristo & Leopardi, 2008), assumes that all wastewater passing through the intrusion point is considered contaminated. The pollution matrix is constructed by using a modified version of the Floyd-Warshall algorithm (Floyd, 1962). It is a N x N matrix of 0-1 coefficients, where N is the number of nodes, which contains information about the hydraulic behaviour of the system: nodes of the jth column having value "1" represent sources of pollution that can contaminate node j (domain of coverage of node j). If a non-zero concentration is read in a node equipped with a sensor, then all nodes of its domain of coverage represent a possible source of pollution and have to be included in the candidate nodes group. Considering all nodes with a non-zero concentration reading, only nodes in the intersection among their domains of coverage can be the pollution source and have to be considered as candidates. Alternatively, a zero concentration reading in a node means that all nodes of its domain of coverage have to be excluded from the group of candidate nodes.

After the identification of the candidate nodes, the non-candidate ones, and their associated links are cut by studying the flow paths, which is a simple task due to the treelike structure of a sewer scheme. Identifying the ways linking the candidate nodes to the outfalls or treatment plants, all nodes along these paths represent connecting nodes, which cannot be cut. The "nodes to be cut" are obtained by subtracting the connecting nodes from the total nodes. When cutting a part of the scheme, the flow coming from it has to be added to the next downstream node of the remaining scheme. This is done by assigning a new average inflow and a new time pattern to this node, estimated through the hourly time flow values at the last link of the cut portion. A detailed description of the cutting procedure is reported in Banik et al. (2015), along with a more in-depth analysis of its correctness and efficacy.

Example Applications and Results

The presented methodology is firstly applied to the literature scheme Example 8 from the SWMM5 application manual (Gironás et al., 2009), which is a combined sewer. Dry and wet weather flow tests are performed, to investigate the applicability of the methodology in both conditions. The sensitivity of the results on the GA parameters is presented, along with an uncertainty analysis respect to inflows variability and measurement errors.

Successively, the procedure is applied to a real test case, representing a part of the combined sewer system of Massa Lubrense, Italy.

Synthetic sensor measurements are generated, fixing the unknown source characteristics.

In both examples, the monitoring stations are placed in a random way, even though an ad hoc analysis could be used for the sensors design [START_REF] Liu | Optimal sensor placement for event detection and source identification in water distribution networks[END_REF].

SWMM example 8 system

The scheme of the SWMM Example 8 system is represented in Figure 4.1(a), and all geometric data are available in the SWMM example manual (Gironás et al., 2009). It is a combined sewer network and consists of 31 nodes (28 junctions, two outlets and one storage unit), 35 links (29 conduits, one pump, one orifice and four weirs). The served area is 0.12 km 2 . The two outlets are the wastewater treatment plant (WWTP) and the overflow (O1) during wet weather. In Figure 4.1(a), the lines with the C label represents 4.1), representing a 2-year return period storm within the seven subcatchments of the system (Gironás et al., 2009). The string length for representing the problem variables is initially fixed equals to 20; then it is reduced to18 when applying the pre-screening procedure. The GA parameters chosen in the initial base run (BR) are reported in Table 4.3. The number of generation has been fixed through a preliminary sensitivity analysis, more detailed reported in the following section.

Results

The two tests, considering dry and wet weather conditions, are firstly performed without applying the pre-screening procedure. For each test, the methodology is repeated 50 times to check the consistency of results. In the dry weather test, the source node is successfully identified in 48 cases over 50 (success percentage 96%), but in the two wrong matches the identified point is the node JI1, close to the real source. The average of the estimated input concentration values is 19.75 mg/l with a standard deviation of 0.62 mg/l. Both the starting time and the duration of the pollution event are correctly identified in all tests.

In the wet weather test, the source node is correctly identified in all runs (success percentage 100%), and the estimated concentration is 19.90 mg/l with a standard deviation of 0.43 mg/l. The other two decision variables, starting time and duration, are exactly estimated. These results demonstrate the applicability of the procedure also in wet weather condition. Repeating the dry weather test applying the pre-screening procedure, the system scheme is reduced not in a significant manner [ 19.59 0.52 9:00:00 0:00:00 3:00:00 0:00:00 0:07:16 0:00:34

19.59 mg/l with a standard deviation of 0.36 mg/l. The other two decision variables, starting time and duration, are estimated perfectly too. This test essentially confirms that the results quality does not change with the pre-screening procedure. It also shows that for small-sized systems the pre-screening procedure does not represent an essential element, with a limited modification of the scheme and a consequently small computational time reduction.

The sensitivity of the results respect to the GA parameters is also investigated. On the reduced scheme [Figure 4.1(b)], a preliminary analysis to select the number of generations has been conducted, considering seven different values, namely 10, 20, 30, 40, 50, 60 and 70, and keeping the other GA parameters fixed at the base run values. For each case, the procedure is repeated for 50 times and the success percentage in identifying the correct source has been evaluated. For a number of generations lower than 40, a significant influence on the source identification performance is found while for higher values only a slightly better performance is observed (Figure 4.3). In particular, at 40 generations the success percentage is 96% while at 70 it is 99%, but this small improvement has a significant increase of the computational time as a counterpart. Three other tests have been realised changing one of the other GA parameters (population, mutation probability, and crossover probability) and keeping the others fixed to the base run values, as indicated in Table 4.3. For each test, the entire procedure is repeated 50 times and Table 4.3 reports the percentage of success in identifying the source node (column "Success"), the average and the standard deviation (SD) of the estimated input concentration, the starting time, the duration of the event and the computational time required for each run. The results show a relatively larger influence of the population size (test SA1) on the success percentage of the source identification. The changes of the other parameters do not substantially affect the results. However, even in the SA1 case the source node is correctly identified with a percentage of 86%. This analysis demonstrates the robustness of the algorithm used for solving the optimisation problem and the consistency of the presented results respect to the GA parameters.

Effect of inflows uncertainty and error measurements

Being the solution of inverse problems, like the one presented in this chapter, strongly dependent on the quality of the input data (Polis & Goodson, 1976), the robustness of the methodology respect to input data uncertainties has to be verified by checking the applicability to real situations [START_REF] Grayman | Incorporating uncertainty and variability in engineering analysis[END_REF]. Among the input data, the presented methodology requires wastewater inflows and pollutant concentration measurements.

Both in dry and wet weather conditions the water inflows are strongly affected by uncertainty, while measurements are always susceptible to errors. In this section, the uncertainty analysis respect to both wastewater inflows and measurements errors is performed using the Latin Hypercube Sampling (LHS) method.

As described in detail in Iman et al. (1981a, b), the LHS requires a smaller number of samples compared to a Montecarlo procedure with random extraction. In the present analysis, it is assumed that no correlation exists among the uncertain variables. The analysis is performed on the reduced scheme of the SWMM Example 8, using the same values of GA parameters used in the base run case. Two dry weather tests are performed:

in the former the effect of the uncertainty of dry weather inflows on the results is studied while the latter considers errors in concentration measurements.

The number of Latin hypercube sample is fixed to 150 based on a preliminary convergence analysis. The tests are performed imposing coefficients of variation values of the uncertain input data, inflows and concentration measurements, ranging from 0.1 to 0.5. The coefficient of variation, CV, is expressed as:

𝐶𝑉 = 𝜎 𝜇 (4.2)
where σ = Standard deviation and μ = Mean. The means are assumed equal to the inflows and the concentration values, then, fixing the CV value, the corresponding standard deviation is calculated and used for preparing the Latin hypercube samples.

In the reduced scheme [Figure 4.1(b)], the number of uncertain inflows is six while in considering measurements errors the uncertain parameters are 38 (Table 4.2). Figure 4.4 reports the percentage of success in identifying the source node for the different considered CV values, for both analyses. About inflow uncertainty, the results show that there is a decrease in the success rate in increasing CV, but the percentage is still 62% for CV = 0.5, which represents a quite satisfactory result. For the uncertainty analysis on sensor measurements, a gradual decrease in the success rate is observed as CV increases (Figure 4.4), but with minor effect compare to the inflows uncertainty case. The same tendency is also found in the case of concentration estimation (Figure 4.5), showing a lower standard deviation as compared to inflow uncertainty, starting time and duration estimation. These results suggest that errors in sensor measurements have less influence in identifying the source node compare to inflows uncertainty. So, it can be said that the performances of the proposed methodology are quite satisfactory even with high uncertainty levels of the inflows and concentration measurements.

The Massa Lubrense test-case

The system Massa Lubrense, schematically shown in Figure 4. 6(a), is one of the 12 subcatchment of the real sewer of Massa Lubrense, a town located near Naples, Italy. It is a combined sewer system, covering an area of 0.75 km 2 . The scheme consists of 242 circular conduits connecting 241 junctions, one pump, two storage units and one outfall.

All geometric data will be available on the SIMonA website (www.progettosimona.it), at the end of the project (December 2015). The daily mean values of the dry weather inflows, depicted in Figure 4. 6(a), are assigned considering the population connected to each node. The 24 hourly pattern factors, showed in Figure 4.2, are assumed equal for all nodes, including the source.

The synthetic sensor measurements are generated through a SWMM quality simulation, considering as "true" pollution scenario a continuous injection of a conservative pollutant at node "N16", with a concentration of 20 mg/l starting at 9 a.m. with a 3 hours duration.

The

Results

Considering the monitoring stations of Test A, the sensor at node N241 always has a zero reading, which is useful information for applying the pre-screening procedure. In fact, after the pre-screening, a significant cut of the scheme is noticed [ the larger number of candidate nodes respect to the Test A produces a lower success rate in identifying the source. In particular, the success rate is equal to 32% for the correct node (N16) and 28% for node N17, which is the closest one to the true source. The corresponding mean and standard deviation of estimated initial concentration are 20.34 mg/l and 0.97 mg/l, respectively. For the release starting time and the duration the estimated means are 9:00:00 and 3:00:00, respectively.

The monitoring stations disposition influences the pre-screening procedure results and consequently the performances of the source identification methodology. This suggests the need for the adoption of an ad hoc sensor location procedure for the source identification problem [START_REF] Liu | Optimal sensor placement for event detection and source identification in water distribution networks[END_REF].

Conclusions

The chapter presents a methodology for characterizing an illicit intrusion in sewer systems, formulated as a source identification optimisation problem, which uses on-line pollutant concentration measurements. The present version of the methodology deals with the intrusion in one node of the system of a conservative contaminant with a constant input concentration during the release time interval. It is also considered that some monitoring stations, installed in fixed positions of the system, provide the concentration measurements. The source identification problem is solved combining the hydraulic and quality simulation tool SWMM with the GALib code. The presented methodology is first applied to the literature scheme Example 8 from the SWMM5 manual, performing dry and wet weather flow tests, to demonstrate its applicability in both conditions. Moreover, the sensitivity of the results on the GA parameters is presented, along with an uncertainty analysis respect to inflows variability and measurement errors. The inflows uncertainty influences the success rate of the source identification, even though satisfactory results are also obtained with significant uncertainty levels. Measurement error has a minor influence on the source node identification.

The methodology also includes a pre-screening procedure for selecting a limited group of candidate nodes, cutting all the unnecessary nodes and their associated links from the scheme, to reduce the simulation time. The crucial role of the pre-screening procedure for large networks is shown in applying it to the real test case, representing a part of the Massa Lubrense sewer system. The results of this second example confirm the good performances of the proposed methodology for real systems. Finally, the comparison of two tests with a different monitoring stations disposition shows the influence of the sensors displacement on the methodology performances. This suggests the adoption of an ad hoc procedure for their location, taking into account the application of the prescreening method. (2000). EPANET 2: users manual.

Chapter 5

A core problem associated with the water quality monitoring in the sewer system is the optimal placement of a limited number of monitoring sites. A methodology is provided for optimally design water quality monitoring stations in sewer networks. The methodology is based on information theory, formulated as a multi-objective optimisation problem and solved using NSGA-II. Computer code is written to estimate two entropy quantities, namely Joint Entropy, a measure of information content, and Total

Correlation, a measure of redundancy, which are maximised and minimised, respectively.

The test on a real sewer network suggests the effectiveness of the proposed methodology.

Introduction

Improper management of wastewater could result in significant damage to the flora and fauna of the ecosystem, long-term impacts on public health, distraction to commerce and economy, which in turns lead to the overall disruption of the nation's way of life. In past, the wastewater management has not got much attention to the stockholders mainly due to the lack of immediate and direct impact on public health. However, recently wastewater and stormwater management is evolving from a simple sanitary and flood control to a whole environmental protection function. In many countries (such as USA and EU members) operators usually require a permit from the regulatory authority to discharge their wastewater into the sewer systems (SSs). In this context, a very important aspect of the SSs management policy is to establish an early warning monitoring system to detect and eliminate an illicit intrusion (Banik et al., 2015), which can be intentional, such as unauthorised industrial effluent, or accidental spills. Ideally the most efficient monitoring network should have the number of monitoring stations equals to the number of nodes in the system. However, some practical limitations, such as budget constraints, force the manager to install only a limited number of monitoring stations. Therefore, assessing the wastewater quality in the SSs through a limited number of monitoring stations is an important engineering problem.

The design of an effective monitoring system has been addressed to various fields of water resource engineering, such as water distribution systems (WDSs), river systems, polder systems, etc. Currently, after the terrorist attack on 2001, a lot of research is going on in the drinking water sector for optimal location of the monitoring stations in WDSs.

Although a large number of methodologies are available in this sector, there is no consensus amongst the researchers on the objectives and methodologies used (Rathi & Gupta, 2014). The methodologies in WDSs can be broadly classified into two groups: i) methodologies with single objective [START_REF] Lee | Optimal locations of monitoring stations in water distribution system[END_REF]Kumar et al., 1997;Kessler et al., 1998;Ostfeld & Salomons, 2004, etc.) symposium can be found in [START_REF] Aral | Optimal Design of Sensor Placement in Water Distribution Networks[END_REF]. In the case of river systems monitoring, among the used approaches there are statistical methods (e.g. Moss & Tasker, 1991), direct survey (e.g. [START_REF] Davar | Hydrometric network evaluation: audit approach[END_REF], methods adapted from the WDSs (e.g. Telci et al., 2009) and information theory applications (e.g. [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]. A comprehensive review of the available methods for designing the monitoring networks in the river system is presented by Mishra and Coulibaly (2009).

Although [START_REF] Ridolfi | Artificial Neural Networks and Entropy-based Methods to Determine Pressure Distribution in Water Distribution Systems[END_REF] used Information Theory to optimally locate pressure sensors in WDS, evidence of research done for finding the optimal location of monitoring stations in sewer networks is not found. The practical use suggests of placing monitoring stations early enough before the treatment process to allow mitigation steps or positioning them to minimise fouling (Bahadur & Samuels, 2011).

This chapter presents an original research to identify the optimal position of a limited number of monitoring stations in sewer networks based on information theory (Shannon, 1948). The principle idea behind is to reduce the amount of uncertainty associated with the estimation of the variables of interest at the unmonitored locations of the network.

Traditionally, the concept of uncertainty has been linked to the statistical variance.

However, Amorocho and Espildora (1973) have showed that the statistical variance is not an objective index of quality when comparing predicted values of a hydrologic model with the series of data records. They have introduced the Information Theory (IT) to the water resource field. The IT provides useful expressions to measure information, such as entropy, which can be denoted as the reduction of uncertainty. Entropy increases as the probability distribution of a variable approaches to the uniform distribution. In other words, the theoretically maximum entropy value will be achieved when all the measurements of a variable are different from each other. In that case, all the measurements have the same probability which means all the information is known, and therefore uncertainty is zero. Different researchers have used the concepts of IT in designing the monitoring network for different purposes. Singh (1997) has done a comprehensive review on the use of IT in water resources application.

This chapter is organised as follows. It starts with a brief introduction about the IT, followed by the description of the methodology used, where data extraction procedure along with the description of a multi-objective optimisation method is presented. In the application section the case-study, represented by the real sewer system Massa Lubrense, a town located near Napoli, Italy is described. Then, the design contamination scenario, generation of data and a screening procedure are shown. The result section analyzes the multi-objective optimisation outcomes, the assessment of the existing monitoring network as well as two other possible configurations of monitoring stations. At the end of the result section, a sensitivity analysis respect to a parameter used in estimating the entropy is presented. Finally, some conclusions and recommendations are drawn. Shannon (1948) has introduced the information theory to measure the information content, also known as entropy, of a variable X. The physical significance of entropy can be realised as the reduction of uncertainty. Mathematically, the entropy of a discrete random variable X, which comprise of the discrete values x1, x2, ..., xn with probabilities p(x1), p(x2), ..., p(xn), where n is the number of elementary events, can be expressed as:

Information theory

𝐻(𝑋) = -∑ 𝑝(𝑥 𝑖 ) 𝑛 𝑖=1 𝑙𝑜𝑔𝑝(𝑥 𝑖 ) (5.1)
In the present study, the random variable X is the monitoring station and x1, x2, ..., xnare n number of discrete concentration measuremnts at node X.

The amount of information that is available within two variables X1, X2 is given by the Joint Entropy,

𝐽𝐻(𝑋 1 , 𝑋 2 ) = -∑ ∑ 𝑝(𝑥 1𝑖 , 𝑥 2𝑗 ) 𝑙𝑜𝑔𝑝(𝑥 1𝑖 , 𝑥 2𝑗 ) 𝑚 𝑗=1 𝑛 𝑖=1
(5.2) in which p(x1i, x2j) is the joint probability of the variables X1 and X2 , n and m are the number of elementary events in X1 and X2 respectively.

A significant number of variables influence the natural processes. The relationship among the variables can be a good way to understand those processes. The concept of Total Correlation (McGill, 1954;Watanabe, 1960) can be used to assess the dependencies among the N variables, which gives the amount of information shared by all those N variables at the same time, taking into account the dependencies between their partial combinations, is given by:

𝑇𝐶(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 ) = (∑ 𝐻(𝑋 𝑖 ) 𝑁 𝑖=1 ) -𝐽𝐻(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 ) (5.3)
Although the term JH(X1, X2, ..., XN) is difficult to compute as it requires the estimation of the joint distribution p(x1, x2, ..., xN), it can be solved by using the grouping property of mutual information (Kraskov et al., 2005) in which the new variables are built up by agglomerating pairs of variables in such a way that the entropy of each new variable is equivalent to the Joint Entropy of the original pair. A detailed explanation of the agglomeration procedure with an example can be found in [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]. The concept of Total Correlation has been widely used in the field of medicine, neurology, psychology, clustering, feature selection, genetics and recently in water resources (Alfonso et al., 2010b(Alfonso et al., , 2010c;;[START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF].

Methodology

The proposed methodology is composed of two important steps: (i) Determination of the dynamic behavior of a contamination event in a sewer network. The data that are generated will be utilised in the second step; and (ii) determination of the optimal location of the monitoring stations based on an optimisation model. Both steps are described below. The model generated data has been quantised prior to its use in the optimisation procedure. The quantisation is a process of compiling a continuous set of data to a discrete set. It rounds a value z to its nearest lowest integer multiple of k namely zq, can be expressed as:

Data extraction through hydrodynamic and contaminant

z q = floor (kz + 1 2 ) (5.4)
where, "floor" is the Microsoft Excel function that round down a decimal number to the nearest integer. The value of the parameter k is related to the detection threshold of a sensor, considering that their product has to be equal to 1. In the result section, a sensitivity analysis has been done on the parameter k for verifying whether the entropyrelated quantities are sensitive to it.

Optimisation model

In this study, the optimal placement of the monitoring stations has been done through evaluating two objectives: (i) maximum information content attain by a group of monitoring stations (ii) minimum dependency among the monitoring stations. The first objective can be achieved by maximising the Joint Entropy of the selected monitoring stations (Eq. ( 5.2), in the case of N variables) while the second one can be accomplished by minimising the Total Correlation, in Eq. ( 5.3), among the monitoring stations of concern. As most of the sewer systems are topologically branched network, the node just before the treatment plant will have the most entropy and the node at the periphery of the network will have the least entropy. Consider two different solutions having two sensors.

Solution1 consists one sensor at the inlet of the treatment plant and the other somewhere in the middle of the network. Solution2 consists one sensor at the inlet of the treatment plant and the other at the periphery of the network. In the fist solution, both the JH and TC will be higher than the second solution. So, choosing solution1 will result higher JH but having also higher TC, which we do not want. Similarly, for solution2 TC will be less but JH will also be less. In that case, during the optimisation, both solutions will be treated as non-dominating solutions and they will stay on the Pareto front. Mathematically the optimisation problem can be formulated as:

𝑚𝑎𝑥{𝐽𝐻(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 )} 𝑚𝑖𝑛{𝑇𝐶(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 )} F (5.5)
Subject to: H(X1), H(X2), ..., H(XN) > Hmin.

where H(Xi) is the marginal entropy of the node Xi and Hmin is the minimum acceptable entropy value (i.e., information content of a single monitoring station). In this chapter, the optimisation problem of Eq. (5.5) is solved by using NSGA-II (Deb et al., 2002).

NSGA-II is an elitist, non-dominated sorting genetic algorithm which utilises Simulated Binary Crossover (SBN) and Polynomial Mutation as genetic operators.

Application

The proposed methodology is applied to a real sewer system, located in Massa Lubrense a town near Naples, Italy. First of all, the hydrodynamic setup of the real network has been made in SWMM and then by using the SWMM Toolkit, time series of concentration data have been extracted. After performing the quantisation, the extracted data have been filtered out based on the marginal entropy values. The filtering is done simply to reduce the enormous search space associated with the optimisation procedure.

Massa Lubrense sewer system

The sewer network of Massa Lubrense is schematically shown in Figure 5.1. It is a combined sewer system, covering an area of 19.71 km 2 and serving a population of 14,087 (2011). The scheme consists of 1909 circular conduits connecting 1902 junctions, 14 pumps, 14 storage units and one treatment plants. The area is divided into 12 subcatchments. The distribution of dry weather flow (DWF) is also depicted in Figure 5.1. Among the 1916 nodes (junctions, storage units and treatment plant) 1866 nodes receives the DWF. Among the nodes that receive the DWF, the maximum, minimum and the average values are 0.0803 l/s, 0.0006 l/s and 0.0099 l/s respectively. As the network has few loops, the hydrodynamic behaviour makes the system more complex to be analysed. A possible set of monitoring stations could be intuitively placed at the pumping stations. However, the author demonstrates that this alternative is not optimal from the information content point of view.

Contaminant scenarios, data generation and screening

An automated 'C' code has been developed to run the SWMM simulations for different contaminant scenarios and to extract the relevant time series of the concentration data for using those in the optimisation procedure. In this study, single conservative continuous events are considered for the contamination scenarios. The contamination scenario is chosen as a continuous injection of a conservative pollutant at one of the 1916 nodes, one at a time, with a concentration of 1.0 g/l starting from 9 a.m. with 5 hours duration.

Eventually, all the nodes in the system have been contaminated. an order of magnitude of 1000 with respect to the previous node (210) while before that point it is within an order of magnitude of 100 respect to its previous node. This significant reduction has happened due to the fact that a huge amount of wastewater, produced from the subcatchments 6-12, passes through the node 224 on the way to the treatment plant. Based on this observation, it is important to note that the detection threshold can play a significant role. So, a detection threshold value less than 0.00001 mg/l would have been a practical choice. However, as the entropy calculation is extremely sensitive to the higher number of digits in a measurement, the detection threshold is kept as 0.0001 mg/l (or k = 10000) in this chapter.

Based on the previously generated time-series of concentrations and after quantisation, the entropy of each node of the network has been calculated, as shown in Figure 5.3. It can be noted that the entropy changes significantly at points where the branches meet. If the entropy of a node is relatively high, it will be regarded as an informative node. In other words, if a monitoring station is placed in that node, it will provide information that can reduce uncertainty. It is observed that 50% of the nodes have an entropy value less than 0.12 bit (<1.5% of the maximum value) while the maximum entropy in the network is 6.89 bits. Therefore, based on the entropy values, two least informative quartiles (50%) have been eliminated. In this way, the constraint of the optimisation problem posed in Eq.

(5.5) is accounted for.

Results

Multi-objective optimisation approach

The formulated multi-objective optimisation procedure in Eq. (5.5) is solved using the Non-Dominated Sorting Genetic Algorithm, NSGA-II (Deb et al., 2002), for which the number of populations (P), the number of generations (G) as well as the number of decision variables have to be specified. To reduce the impact of those (population and generation) GA parameters in the optimisation procedure, a number of experiments have been carried out, in which three different combinations of P and G are tested, namely (P,

Comparison with existing monitoring stations

In the Massa Lubrense network there are currently 12 monitoring stations installed. It must be noted that they have been temporarily placed for the testing purpose of an ongoing project, and their location is decided on the basis of consideration on the availability of electrical power supply in nodes as well as of the needed GSM (Global System for Mobiles) coverage for transmitting the recorded data. The performance of this set of placement has been evaluated from the perspective of information theory, obtaining a value of Joint Entropy = 12.81 bits and a value of Total Correlation = 12.12 bits. This performance is compared with the outcomes from the multi-objective optimisation procedure where 12 monitoring stations are considered (Figure 5.6). It is evident that the existing set of monitoring stations is only a sub-optimal solution and there exist better solutions. The placement of the existing monitoring stations along with the proposed optimal solution is presented in Figure 5.7.

Comparison with monitoring stations before and after pump stations

To date, the author has found no evidence of mathematical models or methodology for optimal location of monitoring stations in a sewer network. The current practice is to place them in pumping stations, wet wells and at the key facilities, but no guidance or explanatory information is available on the optimal selection of these locations (Bahadur & Samuels, 2011). There are 14 pump stations available in the Massa Lubrense network.

Considering this suggestion, the placement of the monitoring stations before and after a pump station is also evaluated from an information theory perspective. From Figure 5.6 it was clear that those sets again produce a sub-optimal solution. Although both sets are outperformed by the multi-objective solutions, it is interesting to note that the guided set of solution (placement at pumping stations) has performed at least better than the existing one. Therefore, if there is no methodology or model exists it might be better to place the monitoring stations before the pumping stations. The placement of two guided sets of

Sensitivity analysis on the parameter "k"

The parameter k may change the outcome of an entropy-related quantity. In order to see if any significant change in the entropy has encountered due to the change in parameter k, the entropy map is redrawn for three other values of k. Figure 5.9 shows that the entropy values decrease with increasing k. This is expected as the bin size increases with the increase of k, which in turns implies more number of sums to assess the Eq. ( 5.1).

However, the relative value of any point with respect to the others in the same map is remained almost same in all four cases. That means, although the Eq. ( 5.2) and ( 5.3) will produce different values during the optimisation process, the sensor locations will remain the same. This concludes that the resultant monitoring networks obtained using the presented methodology do not change due to different value of k.

Conclusions

An Information theory based approach is introduced in this chapter to design the optimal placement of a set of monitoring stations in a real sewer network Massa Lubrense. The first decision on selecting the potential locations of setting a monitoring station comes from the analysis of the entropy map of the network. It is observed that the entropy values change significantly where the new branches meet. The selection of high entropy points leads to redundant information, whereas the selection of low-entropy points will produce less information. This dilemma leads to use the multi-objective optimisation approach.

The decision on the final network configuration from the Pareto front is, however, not a straightforward task. To do so, the decision maker has to take into consideration some other constraints, such as geographical convenience, accessibility, safety, etc., to assess the relative importance of the Joint Entropy and Total Correlation.

The methodology is compared with the existing monitoring stations and two other guided configurations (before and after the pump stations). All three scenarios are sub-optimal solutions of the multi-objective optimisation. However, in the absence of any methodology or model to assess the optimality, it is a good idea to place the monitoring stations before the pumping stations. Moreover, it has been also noticed that although the quantisation parameter k is not sensitive to the optimisation results, an extreme or irrational value (such as 0.0001 or 1000000) of k will produce a useless entropy map.

Alfonso, L., He, L., Lobbrecht, A., & Price, R. (2013). Information theory applied to evaluate the discharge monitoring network of the Magdalena River. J. Hydoinform., 15, 211-228. Alfonso, L., Jonoski, A., & Solomatine, D. (2010a). Multiobjective optimisation of operational responses for contaminant flushing in water distribution networks. J. Water Resour. Plan. Manage., 136(1), 48-58. Alfonso, L., Lobbrecht, A., & Price, R. (2010b). Information theory-based approach for location of monitoring water level gauges in polders. Water Resour. Res.,46(3), W03528. Alfonso, L., Lobbrecht, A., & Price, R. (2010c). Optimization of water level monitoring network in polder systems using information theory. Water Resour. Res., 46(12), W12553. Amorocho, J., & Espildora, B. (1973). Entropy in the assessment of uncertainty in hydrologic systems and models. Water Resour. Res., 9, 1511-1522. Aral, M. M., [START_REF] Aral | Optimal Design of Sensor Placement in Water Distribution Networks[END_REF]. Optimal Design of Sensor Placement in Water Distribution Networks. J. Water Resour. Plan. Manage., 136, 5-18. Bahadur, R., & Samuels, W. B. (2011). Wastewater Critical Infrastructure Security and Protection. In R. M. Clark et al.,(Eds.),. New York: Springer. Singh, V. P. (1997). The use of entropy in hydrology and water resources. Hydrol. Processes,11(6), 587-626.

Telci, I. T., Nam, K., Guan, J., & Aral, M. M. (2009). Optimal water quality monitoring network design for river systems. J. Environ. Manage., 90(10), 2987-2998. Watanabe, S. (1960). Information theoretical analysis of multivariate correlation. IBM J. Res. Dev.,4(1),[66][67][68][69][70][71][72][73][74][75][76][77][78][79][80][81][82] This chapter was submitted for publication as: Banik, B. K., [START_REF] Banik | Greedy algorithms for designing optimal sensor network for contamination detection in sewer systems[END_REF]. Evaluation of different formulations to optimally locate pollution sensors in sewer systems. J. Water Resour. Plan. Manage. (Submitted)

CHAPTER 6 Different Formulations for Optimal Sensor Placement Chapter 6

Optimal placement of sensors in sewer systems is a challenging problem. In this chapter, five different procedures have been proposed, tested and compared with a real system.

The first two multi-objective procedures consist of two objectives Joint entropy (JH), Total Correlation (TC) (IT procedure) and Detection time (D), Reliability (R) (DR procedure), respectively. The third procedure (DR_IT) represents an enhancement of the DR one by introducing an IT filtering method. In the fourth procedure, the three objectives, JH, D and R are considered separately using a single objective rank-based Greedy algorithm. A further improvement on the DR_IT procedure is made by incorporating the Greedy solutions into the optimisation (DR_IT_GR). The NSGA-II is used to solve the multi-objective optimisation procedures. The results show that an ITbased method can be effectively used as a filtering technique. Likewise, a Greedy-like procedure is found very efficient in finding the most Pareto extreme solution while the DR_IT_GR procedure shows promising solutions.

Introduction

An efficient management of sewer systems requires control on the conveyed wastewater quality for an adequate protection of the receiving water bodies. In fact, wastewater quality not only influences the good functioning of treatment plants, but, in combined systems, when discharge exceeds the treatment capacity, raw effluents are spilled directly to water bodies with possible acute impacts on the environment (Gromaire et al., 2001;Diaz-Ferros et al., 2002;Even et al., 2004). In this context, the characterisation of the collected wastewater is very important (Obropta & Kardos, 2007), along with the detection of illicit intrusions. Sewer systems are very vulnerable to accidental spills or intentional intrusion, such as unauthorised effluent, because of their distributed geography and multiple points of access. The detection of illicit intrusions in sewers is a challenging task due to the heterogeneous nature of the collected liquid, and the contamination event has to be properly identified denoting differences in the usual composition of the wastewater. However, the development of online sensors for measuring wastewater quality, based on different technologies [START_REF] Thomas | Wastewater quality monitoring[END_REF]Bourgeois et al., 2001;[START_REF] Qin | Wastewater quality monitoring system using sensor fusion and machine learning techniques[END_REF], made possible the identification of anomalous behaviors and the application of source identification methodologies in sewer systems [START_REF] Banik | Evaluation of different formulations to optimally locate pollution sensors in sewer systems[END_REF]. An important element for illicit intrusion detection is the monitoring network, which has to be designed adequately, to locate the limited number of sensors optimally.

The sensor placement problem has been widely studied for monitoring rivers and for designing contamination warning systems in drinking distribution networks. In the more recent and efficient strategies, the sensor placement design is automated solving an optimisation problem. In this framework, numerous researches have been developed for sensor placement in rivers (e.g. Telci et al., 2009;[START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF][START_REF] Lee | Efficient method for optimal placing of water quality monitoring stations for an ungauged basin[END_REF] and in drinking water networks, for which a critical review may be found in [START_REF] Hart | Review of sensor placement strategies for contamination warning systems in drinking water distribution systems[END_REF], where over 90 papers are considered.

The many sensor placement optimisation methodologies presented in the literature differ from the proposed formulations, which represent the mathematical definition of the optimisation problem, including decision variables, objectives, constraints and modeling assumptions. Different design objectives have been considered and implemented in single and multi-objective functions. The performances in using multiple objectives have been investigated in the Battle for the Water Sensors Networks [START_REF] Ostfeld | The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms[END_REF], where 15 different methodologies for water distribution network are compared. Different possibilities are available for choosing the optimisation problem solver, such as integer programming (e.g. [START_REF] Banik | Illicit intrusion characterization in sewer systems. Urban water J[END_REF], genetic algorithms (e.g. Guan et al., 2006), which has to be selected considering not only the performance guarantee for the final solution but also the required computer capacity. The detection of pollution sources is required, also, to optimise the operational interventions in distribution networks (Alfonso et al., 2010a).

In sewer systems, monitoring networks have traditionally been designed considering operators experience and their practical preferences, placing stations in proximity of critical facilities, in more accessible areas and/or assuring a good spatial displacement, rather than using a systematic design and specified objectives. In this chapter, a methodology for optimally locate sensors in sewers for early warning in case of illicit intrusion is presented. The sensor location is expressed as a single or multi-objective optimisation problem. The main novelty is represented by the comparison of five different proposed procedures, which use different objective functions and/or combined formulations. Their performances are tested on a real case study, represented by the sewer system of Massa Lubrense, a town located near Naples, Italy.

Sensor Location Methodology with Different Optimisation

Formulations

In the proposed methodology, sensor location is optimised to detect any possible contamination scenario. The considered scenarios are represented by the intrusion of a conservative contaminant at any time of the simulation period with constant concentration during the release period, in a single point of the system, which can be any nodes of the scheme. In each methodology run, the number of sensors is fixed, even if increasing it in different applications may suggest the optimal quantity. The methodology is formulated as an optimisation problem, expressed adopting five different procedures listed in Table 6.1. The performances of all the procedures are compared. As detailed described in the following paragraphs, the first procedure considers a multi-objective approach derived from the Information Theory, defined as IT, where Joint entropy (JH) and Total Correlation (TC) are used to maximise sensor information content and minimise redundancy, respectively. Detection time (D) and the Reliability (R) are considered as objectives in the second multi-objective procedure, named as DR. A combination of the previous two procedures, named DR_IT, is also tested, in which the IT is applied as a filtering method prior to the DR procedure. As an alternative formulation, a rank based greedy approach, indicated as GR, is used for solving the optimisation problem, and formulated as a single objective function, considering singly JH, D and the R. In the last procedure, named DR_IT_GR, the DR_IT procedure is improved by incorporating the greedy solutions in the optimisation process.

The multi-objective optimisation procedures (IT, DR, DR_IT and DR_IT_GR) are solved using the Non-Dominating Sorting Genetic Algorithm-II (NSGA-II), developed by Deb et al. (2002). NSGA-II is an elitist, non-dominated sorting genetic algorithm which utilises Simulated Binary Crossover (SBN) and Polynomial Mutation as genetic operators. The output of NSGA-II consists of sets of quasi-optimal, non-dominated solutions that defines the Pareto front. The Pareto front describes a series of possibly best outcomes regarding all objectives. The single objective procedure (GR) is solved using a rank-based Greedy algorithm.

Greedy D Greedy R DR_IT_GR NSGA-II D, R
The required data for evaluating the objective functions of the different proposed procedures are obtained through hydrodynamic and quality simulations, performed using the well documented and widely used public software Storm Water Management Model (SWMM). SWMM (Rossman, 2010) is a dynamic rainfall-runoff simulation model that computes runoff quantity and quality from, primarily, urban areas. Telci et al. (2009) have used this model to generate water quality data for the optimal placement of monitoring stations in a river system while Banik et al. (2015aBanik et al. ( , 2015c) ) have introduced it in a pollution source identification methodology for the sewer systems. For the hydraulic simulation, SWMM solves the conservation of mass and momentum equations (St.

Venant Equations), using the Manning's equation. In the performed quality simulations the contaminant is considered conservative, with no biochemical reaction, and transported through the links respecting the assumption that conduits behave as a continuously stirred tank reactor (CSTR). To integrate the SWMM simulator within the methodology, an ad-hoc SWMM-Toolkit has been developed, as detailed described in Banik et al. (2014). In particular, the Toolkit is applied for extracting the time series of the concentration data in each node, required for evaluating the objective functions of the proposed procedures.

Procedure 1 (IT)

Shannon (1948) introduced Information Theory to measure the information content, defined as entropy that physically represents the decrease of uncertainty. Mathematically, the entropy or marginal entropy of a discrete random variable X, which comprise of the discrete values x1, x2, ..., xn with probabilities p(x1), p(x2), ..., p(xn), can be expressed as:

𝐻(𝑋) = -∑ 𝑝(𝑥 𝑖 ) 𝑛 𝑖=1 𝑙𝑜𝑔𝑝(𝑥 𝑖 ) (6.1)
where n is the number of elementary events or records. In the presented application, n is the number of records related to a concentration value xi in a particular node X. The entropy unit is nats if e base logarithm is used or bits if the base of the logarithm is 2. In this chapter, the latter is used. The probabilities p(xi) are estimated by the histogram-based (relative frequency) method with a given bin size or number of classes (intervals) as used by [START_REF] Markus | Entropy and generalized least square methods in assessment of the regional value of streamgages[END_REF], Mishra et al. (2009) and Alfonso et al. (2010bAlfonso et al. ( , 2010c[START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF].

The amount of information that is available within two variables X1, X2 is given by the Joint entropy, JH, defined as:

𝐽𝐻(𝑋 1 , 𝑋 2 ) = -∑ ∑ 𝑝(𝑥 1𝑖 , 𝑥 2𝑗 ) 𝑙𝑜𝑔𝑝(𝑥 1𝑖 , 𝑥 2𝑗 ) 𝑚 𝑗=1 𝑛 𝑖=1 (6.2) in which p(x1i, x2j
) is the joint probability of the variables X1 and X2 , n and m are the number of elementary events or records for X1 and X2 respectively.

Investigated processes are usually influenced by a significant number of variables and the relationship among them is crucial for a good representation. The concept of Total Correlation (McGill, 1954;Watanabe, 1960), TC, can be used to assess the dependencies among the N variables, which gives the amount of information shared by all those N variables, at the same time taking into account the dependencies between their partial combinations, is defined as:

𝑇𝐶(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 ) = (∑ 𝐻(𝑋 𝑖 ) 𝑁 𝑖=1
) -𝐽𝐻(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 ) (6.3)

The term JH(X1, X2, ..., XN) is difficult to compute, as it requires the estimation of the joint probability distribution p (x1, x2, ..., xN). It is solved by using the grouping property of mutual information (Kraskov et al., 2005), in which the new variables are built up by agglomerating pairs of variables in such a way that the entropy of each new variable is equivalent to the Joint entropy of the original pair, as detailed explained in [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]. The concept of Total Correlation has been widely used in the field of medicine, neurology, psychology, clustering, feature selection, genetics and recently in water resources (Alfonso et al., 2010a;Alfonso et al., 2010b;[START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]Banik et al., 2015b).

In the current IT procedure, the optimal placement of the monitoring sensors is formulated evaluating the following two objectives: (i) maximum information content attain by a group of monitoring sensors; (ii) minimum dependency among the monitoring sensors.

The first objective is achieved by maximizing the JH [Eq. ( 6.

2)] of the N selected monitoring sensors (variables) while the second one can be accomplished by minimizing the TC [Eq. ( 6.

3)], among them. Mathematically the optimisation problem can be formulated as:

𝑓 1 = 𝑚𝑎𝑥{𝐽𝐻(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 )} 𝑓 2 = 𝑚𝑖𝑛{𝑇𝐶(𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 )} Subject to: H(X1), H(X2), ..., H(XN) > Hmin. F (6.4)
with N is the number of sensors that has to be placed and H(Xi) the marginal entropy of the sensor Xi. Moreover, a constraint is set based on the minimum acceptable marginal entropy value Hmin to exclude all the nodes having lower values in the optimisation process. The process of fixing the threshold value Hmin is addressed in the result section (Procedure IT).

In the case of IT procedure, the concentration measurements in each node have to be quantised to convert all the records to integer values for computing JH and TC through the histogram-based probability method. The quantisation is a process of compiling a continuous set of data to a discrete one, also used to remove noisy signals (Alfonso et al., 2010b). It rounds a value z to its nearest lowest integer multiple of k namely zq, can be expressed as:

𝑧 𝑞 = 𝑓𝑙𝑜𝑜𝑟 (𝑘𝑧 + 1 2 ) (6.5)
where, "floor" is the typical Microsoft Excel function that round down a decimal number to the nearest integer. The value of the parameter k is related to the threshold concentration detectable by a sensor, considering that their product has to be equal to 1.

Procedure 2 (DR)

In this procedure, the two considered objectives are the Detection time (D) and the Reliability (R), or detection likelihood, of the sensors (e.g. Ostfeld & Solomon, 2004;Kumar et al., 1997;Telci et al., 2009;Rathi & Gupta, 2014). D is defined as the time between the beginning of a pollution event and the first non-zero concentration measurement by a sensor. R is related to the number of detected scenarios. In particular, higher the number of detected scenarios by a given disposition of monitoring stations, higher will be its Reliability. In this procedure, the purpose of the monitoring system is to detect the contamination event as quickly as possible with the smallest failure rate. To achieve this goal, average Detection time has to be as small as possible, and the Reliability of the monitoring system should be as high as possible.

Mathematically, having M number of potential candidate nodes and N number of sensors to install, with M ≥ N, the solution vector is Y=[y1,y2,...yi,...yN], where yi is the original node index of the i th monitoring station. The overall Detection time of the i th sensor for a contamination scenario s, 𝑑 𝑠 𝑖 (𝑌), is defined as the time (in minutes) elapsed between the starting time of a contamination event and the time at which the measured concentration is exceeded the threshold at yi. The Detection time of the monitoring network for the scenario s, 𝐷 𝑠 (𝑌), is defined as the shortest time among the Detection times of the monitoring sensors y1 to yN for a contamination event, can be expressed as follows:

𝐷 𝑠 (𝑌) = 𝑚𝑖𝑛{𝑑 𝑠 1 (𝑌), 𝑑 𝑠 2 (𝑌), … , 𝑑 𝑠 𝑖 (𝑌), … . 𝑑 𝑠 𝑁 (𝑌)} (6.6)

No penalty term is considered for the non-detected scenarios. Then, the average Detection time of the monitoring network Y, D(Y), is calculated as the average of Ds(Y) over all detected scenarios:

𝐷(𝑌) = 1 𝑆 𝑑 ∑ 𝐷 𝑠 (𝑌) 𝑆 𝑑 𝑠=1 (6.7)
where Sd is the total number of detected scenarios.

The Reliability of the solution Y, R(Y), is defined as the ratio of detected contaminated scenarios to the total scenarios tested. R is expressed as percentage, calculated as: 6.8) where, 𝛿 𝑠 =1 if the scenario s is detected, otherwise 𝛿 𝑠 =0, with S the total number of considered scenarios.

𝑅(𝑌) = 1 𝑆 ∑ 𝛿 𝑠 𝑆 𝑠=1 (
The optimisation problem is mathematically formulated as:

𝑓 1 = 𝑚𝑖𝑛{𝐷(𝑌)}
𝑓 2 = 𝑚𝑎𝑥{𝑅(𝑌)} (6.9)

Procedure 3 (DR_IT)

When the search space is enormous, the possibility of the solutions from a genetic algorithm code to converge to the real Pareto front is reduced, which represents a concern for large networks. One possible way to cope up with this situation is to reduce the search space in a logical manner. With this objective, DR_IT combines the two previous procedures by introducing a filtering method based on the marginal Entropy concept prior to the DR procedure. According to the information theory, nodes having low marginal entropy will not provide sufficient information to be chosen as sensor location. In particular, in the filtering phase a fixed percentage of nodes having lower marginal

Entropy are discarded from the potential candidates prior to the DR optimisation.

Mathematically the optimisation problem is formulated as:

𝑓 1 = 𝑚𝑖𝑛{𝐷(𝑌)} 𝑓 2 = 𝑚𝑎𝑥{𝑅(𝑌)}
Subject to: H(y1), H(y2), ..., H(yN) > Hmin (6.10) where H(y i ) is the marginal entropy of the node y i and H min is a fixed minimum entropy threshold. The Hmin value is fixed as specified in the Results section for the Procedure IT.

Procedure 4 (GR)

As a further alternative, a single objective rank-based greedy algorithm is used to locate the optimal placement of sensors sequentially. For a wider analysis, three different objectives are singly considered: JH, D and R. The first monitoring location in the GR algorithm is chosen at the point with maximum JH, minimum D or maximum R depending on which objective is considered. After choosing the first location, the second one is selected based on the maximum marginal variation of the objective, represented by an increment of JH, R or decrement of D, depending on which objective is under consideration. The same procedure is repeated for the successive ones, evaluating the marginal variation considering the sensors already placed. A more detailed study of the applicability of greedy algorithms in the optimisation of sensor locations in sewer systems can be found in Banik et al. (2015a).

In GR, when the single objective D is considered, a penalty term Dsim (total simulation time in minutes) is applied for the non-detected scenarios. This is crucial to avoid dispositions with a high number of non-detected cases. In fact, as D is going to be minimised, all the peripheral (upstream) nodes having a low average time would have been selected, resulting a less reliable monitoring network. The average Detection time of the monitoring network Y, D(Y), is calculated as: 6.12) where S is the total number of scenarios considered in the analysis.

𝐷 𝑠 (𝑌) = { 𝑚𝑖𝑛{𝑑 𝑠 1 (𝑌), 𝑑 𝑠 2 (𝑌), … , 𝑑 𝑠 𝑖 (𝑌), … , 𝑑 𝑠 𝑁 (𝑌)} if scenario s is detected 𝐷 𝑠𝑖𝑚 otherwise (6.11) 𝐷(𝑌) = 1 𝑆 ∑ 𝐷 𝑠 (𝑌) 𝑆 𝑠=1 (

Procedure 5 (DR_IT_GR)

Alfonso et al. ( 2013) demonstrate that the Greedy algorithm may be a good option to find the extremes in the Pareto front of a multi-objective optimisation formulation. This concept is used in this formulation to improve the extremes of Pareto front. Functionally this procedure is similar to the DR_IT with the only exception of manipulation of the initial population of NSGA-II. This is done by putting the solutions coming from the GR procedure (with objectives JH and D) into the randomly generated initial population of NSGA-II. The goal is to start from the extremes of the Pareto front to get trade-off solutions when adding the conflicting objectives D and R.

The Massa Lubrense Case-Study

The system scheme

The proposed methodology is applied to a real sewer network, located in Massa Lubrense, a town near Naples, Italy. The Massa Lubrense system is schematically shown in Figure In the system, 12 monitoring stations are installed for realizing preliminary tests of an ongoing project (www.progettosimona.it). Their actual location has been decided based on practical considerations, mainly related to the availability of electrical power supply and the need for the GSM (Global System for Mobiles) coverage for transmitting the recorded data.

Contaminant scenarios and data generation

An ad hoc developed "C" code, which integrates the SWMM simulator with its Toolkit, generates the contaminant scenarios and extracts the time series of the concentration data for the optimisation procedures. In this study, each contamination scenario is represented by a continuous injection of a conservative pollutant at one node of the scheme, one at a time, with a concentration of 1.0 g/l starting at 9 a.m. with five hours duration. SWMM hydraulic and quality simulations are realised with a time step of two seconds. The time series of the concentration values in each node are collected for six hours, with a reporting time step of five minutes. Therefore, the size of the extracted time series is 137952 at each one of the 1916 nodes.

Results

The NSGA-II is used to solve the multi-objective optimisation procedures (IT, DR, DR_IT and DR_IT_GR) with the parameters: crossover probability 90%, mutation probability 10%. Moreover, after a sensitivity analysis, the number of populations and generations are fixed to 200 and 2000, respectively. Increasing those values do not improve the optimisation outcome significantly, with an increase of the computational burden, especially for an IT-based approach where the entropy calculation is quite computationally expensive.

The presented tests investigate the optimal solutions considering a number of sensors variable between 7 and 14. In the study, the concentration threshold value detected from sensors is fixed to 0.0001 mg/l. However, additional tests for studying the effect of different threshold values on the methodology results is reported in the DR_IT_GR procedure. For better readability, in the plots related to the multi-objective procedures, some intermediate points are eliminated from the Pareto fronts, although they have been considered in the optimisation process.

Procedure IT

The IT procedure assumes that nodes with high entropy are much informative, and hence they are more suitable for sensor location. Then Eq. ( 6.4) poses a constraint Hmin, on the marginal entropy values to filter out low entropy nodes. In particular, the two least informative quartiles (50%) of nodes are eliminated. Figure 6.2 depicts the entropy in each node of the system for the quantisation parameter z = 10000. It can be seen that entropy changes significantly at the points where the branches meet. The maximum entropy in the network is 6.89 bits while in the 50% of the nodes it is less than 0.12 bits (<1.5% of the maximum value), which is the value assigned to Hmin. It is worth mentioning that the total Joint entropy of the system is JHsys=H(X1, X2,…,X1916)=16.71 bits, which represents the amount of information that the ideal monitoring network should provide. After filtering 50% of the nodes, total Joint entropy become JHfilter=H(X1, X2,…,X958)=16.65 bits, which means that the eliminated points provide only the 0.35% of the total Joint entropy of the system. This suggests that the filtering process provides a significant reduction of the computational cost with a minor loss of information content. The optimal solutions obtained solving the optimisation problem of Eq. ( 6.4) with a different number of sensors are reported in Figure 6.3. It can be observed that after 10 monitoring station, an additional sensor does not produce a notable increment of the JH while the Total Correlation remains same or increases because of the effect of sensors redundancy. Moreover, for all the cases (sensors 7-14) the Pareto fronts near the vertical axis (up to 3 bits of Total Correlation) follow almost the same pattern, whereas the differences are evident near the horizontal axis. Another important observation is that for all the sensors [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF](8)(9)(10)(11)(12)(13)(14) the Pareto fronts near Y-axis (up to 3 bits of Total Correlation) almost follow the same pattern, whereas the differences are evident near the X-axis. This is because during the optimisation process the objective TC plays only a subordinate role, just to avoid redundancy while the JH plays the main role. This implies, TC as a single objective will not produce a good optimisation outcome. It is interesting to note from given by the Pareto fronts. The trade-off between information content and redundancy may imply that the ideal network configuration would be located at the origin of any Pareto graph, also called utopia point [START_REF] Pandey | Limitations of Pareto Front in Design Under Uncertainty and Their Reconciliation[END_REF]. In the considered test case, the utopia point is (0, 16.71), representing an ideal solution that has the JH equals to the system's JH (JHsys=16.71 bits) and zero redundancy. In the following, two methods are used for choosing a single solution from each particular Pareto front corresponding to a fixed number of the sensor. Firstly, the maximum JH (most informative solution) is chosen as the optimal one while with the second method the one closest to the utopia point is selected (compromised solution). In this second case, to obtain the compromised solution the optimisation problem is converted into a single-objective formulation, ascribing equal weight to both objectives. Figure 6.4 shows the values of the two objectives for the optimal solutions selected from the Pareto fronts corresponding to the considered sensor numbers using two methods. For method 1 (most informative solution), after 9 sensors the JH is mildly increasing, with a significant increase in the redundancy. In fact, from sensor 10 to sensor 14 the increment of JH is 1% (from 14.99 bits to 15.14 bits) while the TC increases more than 27% (from 14.43 bits to 18.34 bits). Then 10 and 14 sensors provide about 90% and 91% of the total information of the system, respectively. In the case of method 2 (compromised solution), both JH and TC are showing an almost constant trend. For all considered number of sensors, the JH is around 13 bits, which represents the 78% of the total information of the system, with a TC slightly larger than 2 bits. For instance, node 703 and nodes 892, 1372 are redundant in case of 12 and 14 sensors, respectively. In all solutions, three selected points are the two entry points to the treatment plant (1901 and 1902) or their immediate upstream nodes (719 and 1915) and node 1646 (or its immediate upstream node 1911). Furthermore, for 10, 12 and 14 sensors cases eight almost common spots (near 1901, 1902, 766, 94, 794, 266, 1335 and 1911) are selected.

In Figure 6.6, the placement of 12 sensors derived from two methods (most informative solution and compromised solution) are compared with the existing network. In the compromised solution, most of the sensors are located in the upstream part of the scheme where the information contents are relatively low, which produces less redundancy. The placement of sensors based on the practical considerations and experience is partially supported by the location obtained through the maximum JH (most informative solution).

In fact, seven (1902, 772, 92, 1335, 668, 1069 and 1911) out of twelve sensors are very close to the existing monitoring stations. In the Massa Lubrense system, 1866 out of 1916 nodes receive inflows (DWF) while the remaining 50 (2.61% of total nodes) are connecting nodes, and then the maximum Reliability is 97.39%. This is because the contamination events created in those 50 nodes, having no DWF, will always remain undetected.

Using the multi-objective DR procedure, the Pareto fronts obtained for a number of sensors from 7 to 14 are reported in Figure 6.7. It can be noted that after 9 sensors the differences among the Pareto fronts is marginal. The comparison with existing sensor network demonstrates that it is sub-optimal. for a different number of sensors. This also states that after 9 sensors the increment of R, as well as the decrement of D is not significant. Moreover, none of the 8 sensor configurations [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF](8)(9)(10)(11)(12)(13)(14) achieve the maximum R (97.39%). .9 presents the optimisation results for 7 to 14 sensors using the DR_IT procedure. It can be deduced from the figure that the optimisation results are much better than the ones obtained from Figure 6.7 using DR procedure. For instance, using the DR procedure for 14 sensors with a Detection time 10 and 15 minutes the maximum Reliability achieved are less than 60% and 80% respectively (Figure 6.7). However, in the case of the DR_IT procedure with the same sensor number and Detection times the maximum Reliability achieved are about 70% and 90%, respectively. Needless to mention that the existing sensor network is only a sub-optimal in the Pareto fronts obtained using the DR_IT procedure.

Figure 6.10 shows the changes in the objectives with the increment of a number of sensors for the solutions having maximum Reliability in the Pareto fronts. It is observed that with 13 sensors the maximum Reliability achieved is 97.39% (the theoretical maximum Reliability).

Procedure GR

The main goal of using this procedure is to get an idea about the proximity of the Pareto front obtained by IT and DR_IT procedures from the ideal extremes. For the same range of sensor number [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF](8)(9)(10)(11)(12)(13)(14), the single objective rank-based GR procedure is applied using the three different objectives: Joint Entropy (JH), Detection time (D) with penalty and Reliability (R).

Figure 6.11 shows the JH, D and R objective values for a different number of sensors. It is interesting to note that at 6 sensors R has achieved the theoretical maximum (97.39%) while using the DR_IT procedure it is achieved at 13 sensors. JH and D show a very similar pattern, with no significant variations after 6 sensors. Moreover, the maximum JH achieved for 14 sensors by using IT and GR procedures are about 91% (15.14 bits) and 95% (15.85 bits) of the system's JH (16.71 bits), respectively. These results confirm that the Greedy algorithm is a useful alternative to finding the extreme solutions in the Pareto front [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]. The new Pareto fronts obtained for the different number of sensors are reported in Figure 6.12, showing an improvement in the extreme of R with respect to the DR and DR_IT procedures. For instance, for 12 sensors, at D=15 min the R achieved in the DR procedure is about 65% while the maximum Reliability (97.39%) is achieved using the DR_IT_GR.

These results are more clearly shown in Figure 6.13, where the solutions for 12 sensors of all procedures are compared. The DR_IT_GR solutions outperform all the previous multi-objective ones, in particular to the extreme of R. So, the improvement is evident in DR_IT_GR procedure due to the incorporation of two greedy solutions (GR (JH) and GR (D) in Figure 6.13) into the initial population. To investigate the effect of dilution on the results, the whole DR_IT_GR procedure is repeated for four other threshold values (0.001, 0.01, 0.1 and 1 mg/l) and a number of sensors from 4 to 14. In particular, with 4 sensor and 0.0001 mg/l, 0.001 mg/l and 0.01 mg/l detection thresholds, the optimal sensor placements are almost equivalent. At 0.1 mg/l, there are some differences, with one isolated sensor, meaning in a different position respect to the placement obtained with the other threshold values. With 14 sensors increasing the detection threshold, the number of isolated sensors is 3, 2, 4 and 8

respectively. This reveals that with less number of sensors and within a certain range of detection threshold (0.01 to 0.0001 mg/l) the dilution has less influence on the optimisation procedure. At the same time, the diverse placement of sensors in the case of higher configurations is derived from the fact that the search space for the optimisation becomes larger as the number of sensors increase. Another interesting observation is that there is consistency in the outcome of the optimisation procedure for different detection threshold over the number of sensors. The analysis shows that for a particular detection threshold the placement of sensors in lower configuration is kept almost intact for the successive configuration with a higher sensor number. For instance, the same sensor location that is optimised for 4 sensors is also found in the solution with 8 sensors. This is due to the incorporation of the greedy solutions in the initial population of the NSGA-II. As the sensor placement shown in Figure 6.15 is based on the extreme solution (maximum R) and in most cases, the solution derived from the greedy algorithm dictates the other solutions, the consistency of the sensor location in the successive optimisation is expected.

Discussion

In this chapter, five different procedures to optimising a limited number of sensors are presented and tested on the Massa Lubrense sewer system. Four (IT, DR, DR_IT and DR_IT_GR) of them use multi-objective optimisation approach while one uses single objective greedy approach (GR). In the case of GR procedure, three solutions are obtained derived from three objectives (JH, D and R). In the solutions obtained from the GR procedure using R as the objective, the maximum R is reached with less than 14 sensors.

For instance, for detection thresholds 0.0001 mg/l and 0.001 mg/l the maximum R is reached with 6 sensors. For this reason, these solutions are not considered in the analysis. Although the objectives used in the optimisation procedure are different in each approach, a weighted average score is used to compare their performances. For this purpose, first of all, four different objectives (JH, TC, R and D) values are computed, where necessary, from the optimal solution obtained from each approach for four different sensor configuration (Table 6.2-6.5). It must be noted that the solution considered for IT procedure is based on the maximum JH value while for DR, DR_IT and DR_IT_GR it is based on the maximum R. Then the outcome is normalised to a range [0 1]. The normalised objective value Wi is calculated as:

W i = { (O i_max -O i ) (O i_max -O i_min )
if objective i has to be minimised

(O i -O i_min ) (O i_max -O i_min )
if objective i has to be maximised (6.13) where Oi_max and Oi_min are maximum and minimum objective values among all compared procedures.

Estimation of the overall performance of each procedure is calculated by taking the arithmetic average of four objectives, computed as: Score = (W1+W2+W3+W4)/4 (6.14) The score obtained from Eq. ( 6.14) weighs all four measures equally. Higher the score, better the approach is. The obtained overall performance for the five different procedures with 8, 10, 12 and 14 sensor configurations are reported in Table 6.6. In all cases, the Greed approach using the Detection time as objective rank first. It is quite surprising that the solutions obtained from the GR procedures are derived from a single objective that in turns best representing all four measures (JH, TC, R and D). It should be noted that all the solutions considered in different procedures are based on the extreme Pareto solutions, and it is already discussed that Greedy algorithm is very effective in searching the extremes in the Pareto fronts. The DR procedure gets improved with the incorporation of the Greedy solutions in the initial population of NSGA-II, being the DR_IT_GR ranked second. It can be said that DR_IT_GR represents a good choice for developing the optimal sensor placement in the sewer systems not only because it outplays other multi-objective approaches described but also it can be comparable to the extreme solutions obtained from the greedy approach.

Conclusions

Five different procedures with single and multi-objective approaches, for designing optimal monitoring networks, have been proposed and tested on Massa Lubrense sewer system. It is observed that, as expected, a large search domain for optimisation process deteriorates the optimisation outcomes. Information theory-based screening approach is found to be promising to reduce the search space prior to the optimisation procedures. In IT procedure, it is observed that for most cases the sensors are placed where a significant change of entropy takes place. Also, the existing monitoring network in Massa Lubrense is found to be sub-optimal for all the procedures. However, it is interesting to note that seven out of twelve existing sensors are found to be very close to the solution obtained by IT procedure considering the highest JH. Furthermore, eliminating the least informative nodes has significantly improved the solutions of DR_IT procedure. Results from three greedy-based cases have shown that they can be effectively used to find the extreme Pareto solutions. Comparison of all the proposed procedures in terms of extremes reveals that the GR procedure, having Detection time as objective, is the most effective.

The reason is, all the compared procedures are based on the extreme solutions, and it is already shown that greedy algorithms are very efficient in finding the extremes. Finally, DR_IT_GR outperforms all the multi-objective optimisation formulations, especially at the extreme values of Reliability.

This chapter was submitted for publication as: Banik, B. K., [START_REF] Banik | Greedy algorithms for designing optimal sensor network for contamination detection in sewer systems[END_REF]. Greedy algorithms for designing optimal sensor network for contamination detection in sewer systems. J. Hydoinform. (Submitted)

CHAPTER 7

Greedy Algorithms as Optimisation Tool

Introduction

In recent time, wastewater management is receiving growing interest among different stakeholders due to the paradigm shift from simple sanitary and flood control systems to systems with an overall environmental management function [START_REF] Falconer | Global water security: an introduction, Science in Parliament[END_REF]. In this context, many countries (e.g. USA and EU members) are enforcing new policies for regulating the discharges coming from wastewater into sewer systems. To minimise the vulnerability of sewer systems the implementation of early warning sensor networks is required which will be able to (1) quickly identify any illicit intrusion in the system and

(2) rapidly assess the possible impacts on the treatment plant. Banik et al. (2014Banik et al. ( , 2015c[START_REF] Banik | Evaluation of different formulations to optimally locate pollution sensors in sewer systems[END_REF] have proposed a contamination source identification methodology without considering the optimality issue of the sensor network. The design of a sensor network is influenced by several factors, such as Reliability, Detection time, redundancy, cost. Such a network design starts from the premise that an appropriate sensor network would be composed of sensors that can compromise all these factors.

The design of an effective monitoring system has been addressed in various fields of water resources engineering, such as water distribution systems (WDSs) (e.g. [START_REF] Aral | Optimal Design of Sensor Placement in Water Distribution Networks[END_REF], river systems (e.g. [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF][START_REF] Ridolfi | An entropy approach for the optimization of cross-section spacing for river modelling[END_REF], polder systems (e.g. Alfonso et al., 2010a), etc. In the case of WDSs, researchers have chosen different optimisation parameters such as Detection time, the volume of contaminated water consumed, the population exposed to contamination, the extent of contamination, associated risk, detection likelihood, the probability of failed detection, sensor response time and sensor detection redundancy. A comprehensive review can be found in Rathi and Gupta (2014) while a comparison of 14 different methodologies presented during the WDSA 2006 symposium can be found in [START_REF] Aral | Optimal Design of Sensor Placement in Water Distribution Networks[END_REF]. In the case of river systems monitoring, among the used approaches, there are statistical methods (e.g. Moss & Tasker, 1991), direct survey (e.g. [START_REF] Davar | Hydrometric network evaluation: audit approach[END_REF], methods adapted from the WDSs (e.g. Telci et al., 2009) and information theory applications (e.g. [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]. A comprehensive review of the available methods for designing monitoring networks in river systems is presented by Mishra and Coulibaly (2009). Recently, Banik et al. (2015a, 2015b) have proposed some methodologies in designing the monitoring network in a sewer system.

Genetic algorithm, NSGA-II (Deb et al., 2002) The chapter is organised as follows. First, a description of the methodology is presented, including the data extraction procedure and the description of different optimisation models. Second, the case study section, the sewer system of Massa Lubrense, a town located near Napoli, Italy is described. Third, results of various outcomes from different optimisation models are presented and analysed. Fourth, a comparative analysis of different models is discussed. Finally, some concluding remarks are drawn.

Methodology

The proposed methodology consists of two major parts. The first part is the model data generation where data required to evaluate the objective functions is extracted using a hydraulic and water quality simulator (SWMM, Rossman, 2010) with the help of a newly developed Toolkit (Banik et al., 2014). The second part corresponds to the optimisation method, which uses the data generated in the first part. Here, the optimal placement of some limited number of sensors is explored through three simple greedy-based algorithms that optimise different objective functions. The first and second greedy approaches (GR1 and GR2) consider single objectives while the third one (GR3) incorporates multiple objectives into a single fitness function.

Different formulations have been proposed based on the objective function considered.

Objective functions have been classified into two groups, to account for different conceptual aspects. The first group (DR group) consists of traditional objectives for contamination detection, namely Detection time (D) and the Reliability (R). The second group considers Information Theory (IT group) quantities (Shannon, 1948) and consists of two objectives, namely Joint entropy (JH) and Total Correlation (TC). As reported in Table 7.1, eight different formulations have been proposed and tested. First three formulations are solved by GR1 and derived from objectives D, R and JH while the fourth and fifth formulations are solved by GR2 having objectives D and R, respectively.

Besides, GR3 is used to solve the last three formulations derived from a combination of two objective groups. The two main parts of the methodology are described in detail below.

Part 1 -model data generation

The USEPA's Storm Water Management Model (SWMM) is used to estimate the hydrodynamic and contaminant fate and transport analysis of a single entry conservative contaminant. Many applications of this software have been reported in the water resources management field. For instance, Telci et al. (2009) and Banik et al. (2015aBanik et al. ( , 2015b) ) have used this model to generate water quality data for the optimal placement of monitoring stations in river and sewer systems, respectively. Banik et al. (2014Banik et al. ( , 2015c[START_REF] Banik | Evaluation of different formulations to optimally locate pollution sensors in sewer systems[END_REF] have introduced a contamination source identification methodology in the sewer system using this software. SWMM uses the conservation of mass and momentum equations in computing the flow within a conduit, and the contaminants are transported through the conduit link respecting the assumption that conduit behaves as a continuously stirred tank reactor (CSTR). To extract the relevant time series of the concentration data for using those in the greedy optimisation procedure a previously developed automated C language code is used to run the SWMM simulations for different contaminant scenarios. In this study, for the sake of simplicity, the contamination scenario is chosen as a continuous injection of a conservative pollutant at one of the nodes in the system (in total 1916 nodes, as specified in the case description), one at a time, with a concentration of 1.0 g/l starting from 9:00 a.m. during a period of five hours. However, different scenarios could be considered.

Eventually, all the nodes in the system have been contaminated. Six hours SWMM simulation time has been taken for the concentration data extraction process, with a routing time step of two seconds and a reporting time step of five minutes. In this way, each node has an associated concentration time series of 137952 records. A complete dry weather flow condition (i.e. without rain) is assumed during the simulation process.

Datasets are generated for both DR and IT groups. In particular, for the IT group, the model generated data has been quantised before applying the greedy optimisation procedure, to convert all the records to an integer number. The integer number is essential to do the histogram-based probability calculations during computing JH and TC.

Quantisation can be used for other purposes, such as [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF] have used it to filter out noise in the data. The quantisation is a process to compile a continuous set of data to a discrete set. It rounds a value z to its nearest lowest integer multiple of k, namely zq, can be expressed as:

z q = floor (kz + 1 2 ) (7.1)
where, the function "floor" is rounding down any decimal number to its nearest integer.

The value of the parameter k is related to the detection threshold of a sensor, considering that their product has to be equal to 1.

Part 2 -optimisation method

Three greedy-based algorithms have been tested as the optimisation method. The basic idea behind the greedy approach is that a globally optimal solution can be achieved by making a locally optimal choice. The algorithms make a choice of the decision variable value that appears to achieve the best immediate objective function value. For instance, there are 1, 2, 5, 10 and 20 cents of coins available and from where we need to make a change of 46 cents with a minimum number of coins. In this case, the greedy algorithm will choose the sequence {20, 20, 5 and 1} in four steps to giving the solution that is eventually the optimal solution. One important aspect of greedy-based methods is that it is sensitive to the sensor location that is selected to start the algorithm. Different studies have proposed several solutions to commence the algorithm. For instance, [START_REF] Krstanovic | Evaluation of rainfall networks using entropy: I. Theoretical development[END_REF] have suggested choosing the first location based on the highest reduction of uncertainty while [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF] have considered an enumerative approach to determine the optimal set. [START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF] also showed that choosing the first sensor based on the highest reduction of uncertainty might not always be the optimal solution.

However, all these greedy approaches have considered only single objective at a time. To the best of the knowledge of the author, no study has been reported which has considered multiple objectives in a greedy optimisation. Before going into the details of three greedy approaches, the construction of four separate objectives (D, R, JH and TC) are described first.

Detection characteristics objective functions (DR group)

According to Rathi and Gupta (2014), Detection time (D) and Reliability (R) are two frequently used objectives in locating the optimal placement of sensors in water distribution networks. Some authors also have used the same objectives in designing the optimal monitoring networks in the river systems (e.g. Telci et al., 2009) and sewer systems (Banik et al., 2015a). The main principle of these objectives is that a good monitoring system will reduce the Detection time of a contamination event and at the same time it will increase the probability of a contamination scenario to be detected. The Reliability of the monitoring system reduces as the number of non-detected scenarios increases.

The sewer network is assumed to contain M potential candidate nodes for N number of desired monitoring sensors, where M ≥ N and the solution vector Y, consists of monitoring sensors, denoted as, Y=[y1,y2,...yi,...yN], where yi is the original node index of i th monitoring sensor in vector Y. The Detection time of i th monitoring sensor in solution vector Y for a contamination scenario s, d s i (Y), is defined as the time elapsed between the starting time of a contamination event and the time at which a concentration threshold at yi is exceeded. The Detection time of the monitoring network for the scenario s, Ds(Y), without considering a penalty on the non-detected scenarios, is defined as the shortest time among the Detection times of the monitoring sensors y1 to yN for a contamination event s, which can be expressed as follows:

D s (Y)=min{d s 1 (Y),d s 2 (Y),…,d s i (Y),….d s N (Y)} (7.2)
If a penalty term Dsim, total simulation time in minutes, is assigned to the Detection time for a non-detected scenario, the term Ds(Y) can be defined as Eq. ( 7.3).

D s (Y)= { min{d s 1 (Y),d s 2 (Y),…, d s i (Y),…,d s N (Y)} if scenario s is detected D sim otherwise (7.3)
The average Detection time of the monitoring network Y, D(Y), can be calculated by taking an average of Ds(Y) over all detected scenarios for the no penalty case, shown in Eq. (7.4),

𝐷(Y)= 1 S d ∑ D s (Y)
S d s=1 (7.4) where Sd is the total number of detected scenarios in the analysis. While for the penalty case the term D(Y) is calculated by taking an average of Ds(Y), derived from Eq. ( 7.3), over all possible scenarios, as shown in Eq. ( 7.5):

𝐷(Y) = 1 S ∑ D s (Y)
S s=1 (7.5) where S is the total number of scenarios considered in the analysis.

The Reliability of the solution Y, R(Y), defined as the ratio of detected contaminated scenarios to the total scenarios considered, can be calculated as, (7.6) where, δs = 1 if contamination scenario s is detected and δs = 0 otherwise. S is the total number of scenarios used in the analysis. Shannon (1948) introduced Information Theory (IT) to measure the information content, also known as entropy, of a discrete random variable. The physical significance of entropy can be realised as the reduction of uncertainty. Mathematically, the entropy of a discrete random variable X, which comprise of the discrete values x1, x2, ..., xn with probabilities p(x1), p(x2), ..., p(xn), where n is the number of elementary events, can be expressed as:

𝑅(Y) = 1 S ∑ δ s S s=1

Information theory objective functions (IT group)

𝐻(X) = -∑ p(x i ) n i=1 logp(x i ) (7.7)
In this chapter, the 2-base logarithm is used and hence entropy measurements have a unit calls bits.

The amount of information that is available within two variables X 1 , X 2 is given by the Joint Entropy, JH, 𝐽𝐻(X 1 , X 2 ) = -∑ ∑ p(x 1i , x 2j ) logp(x 1i , x 2j ) m j=1 n i=1 (7.8) in which p(x1i, x2j) is the joint probability of the variables X1 and X2 , n and m are the number of elementary events in X1 and X2 respectively.

Natural processes are always influenced by a large number of variables. To understand these processes properly, the dependencies among different variables need to be addressed properly. One way to assess the dependencies among N variables is given by the concept of Total Correlation, TC, (McGill, 1954;Watanabe, 1960) which gives the amount of information shared by all those N variables, at the same time taking into account the dependencies between their partial combinations, is given by:

𝑇𝐶(X 1 , X 2 ,…, X N ) = (∑ H(X i ) N i=1 ) -JH(X 1 , X 2 ,…, X N ) (7.9)
The concept of Total Correlation has been widely used in the field of medicine, neurology, psychology, clustering, feature selection, genetics and recently in water resources (Alfonso et al., 2010a(Alfonso et al., , 2010b;;[START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF]Banik et al., 2015aBanik et al., , 2015b)).

Greedy algorithms (GR) for optimal sensor network design

In this chapter, three greedy algorithms are proposed for optimal sensor network design for contamination detection in sewer systems. A description of each algorithm is presented in this section.

Approach 1 (GR1)

As depicted in Figure 7.1a, this is the classical greedy algorithm [START_REF] Greco | Greedy algorithms in Datalog[END_REF][START_REF] Tallam | A concept analysis inspired greedy algorithm for test suite minimization[END_REF][START_REF] Kumar | Fast greedy algorithms in mapreduce and streaming[END_REF][START_REF] Alfonso | Information theory applied to evaluate the discharge monitoring network of the Magdalena River[END_REF] using single objective.

In this algorithm, the decision variable that provides the best objective function value be chosen first. In a second step, the decision variable that gives the most convenient value for the objective function, in combination with the first selected, is chosen. The procedure continues until a predefined number of decision variables have been chosen. For the case of sensor networks, the sensor with the maximum reduction of uncertainty could be chosen as the starting point, as suggested by [START_REF] Krstanovic | Evaluation of rainfall networks using entropy: I. Theoretical development[END_REF]. The successive sensors can then be chosen, one at a time, based on the highest marginal decrease in uncertainty at each step.

Mathematically, first three formulations are shown in Eqs. (7.10), (7.11) and (7.12), respectively.

f 1 = min{D(Y)} (7.10) f 2 = max{R(Y)} (7.11) f 3 = max{JH(X 1 , X 2 ,…, X N )} (7.12)

Approach 2 (GR2)

This algorithm, as shown in Figure 7.1b, can be interpreted as the enumerative version of the first greedy algorithm. The main difference with the first algorithm is the selection process of the first sensor. In this algorithm, all the potential candidates will be tested as the first sensor. After selecting the first sensor, the remaining sensors will be chosen same way as in GR1. So, if there are M candidate nodes from where N sensors need to be selected, the algorithm will first produce M number of solutions each one having N number of sensors and finally the solution having a maximum or minimum objective value, for maximisation and minimisation problem respectively, will be chosen as the optimal solution. That means GR2 is about M times as computationally expensive as GR1. Moreover, in GR1 the successive selection of sensors remains exactly the same for any sensor configuration. For instance, for two configurations with a different number of sensors (say, 5 and 10) optimisation has performed separately. In this case, the five optimised sensors that are found in the first configuration are also found as part of the second configuration (10 sensors). However, this does not necessarily hold true for GR2, because any sensor configuration must run separately to get the optimal solution. The reason for using GR2 is to check the justification of the less computational expensive algorithms GR1 and GR3. The fourth and fifth formulations are mathematically shown in Eqs. (7.10) and (7.11), respectively.

Approach 3 (GR3)

It is important to recognise that emphasising on one objective over the others will result in a different sensor placement patterns. This dilemma can be eliminated by introducing multiple objectives in the optimisation approach. However, a multi-objective solution approach (such as in, e.g., Deb et al., 2001) will eventually be associated with a trade-off methodology in the final selection of the network. Here, the idea is to identify an objective function that would strike a balance between different objectives without any artificial control that will eventually lead to the preferred choice of the decision maker during the selection of final sensor network from many feasible optimal solutions. More than formulating a multi-objective problem, the goal is to combine different objectives into However, different weights can be assigned to different variables to give importance of one variable to others. For instance, the decision maker could give more importance to R than TC in Eq. ( 7.15).

Case Study

As an application example, the sewer network of Massa Lubrense, a small town close to Napoli, Italy, is used. The sewer network of Massa Lubrense, schematically shown in For the IT group, quantisation of the data, using Eq. ( 7.1), has been done to get an integer data set for histogram-based probability calculation. Once two sets of data series are ready, the greedy-based optimisation approaches are applied to the real sewer network.

Results

For all three greedy approaches (having eight formulations), the methodology is performed for five different detection thresholds, ranging from 0.1 to 0.00001 mg/l, to understand the effect of dilution in the optimisation procedure. In all cases, the optimisation is done for 1-14 numbers of sensors. During the evaluation of the objective D, a penalty term of 360 minutes (total simulation period) is applied to any non-detected contamination scenario. However, in the case of evaluating the sixth and eighth formulations, using GR3, the tests have also been performed without considering the penalty for non-detected scenarios. The results obtained using all three greedy algorithms are discussed as follows.

Approach 1 (GR1)

First three formulations having separate objectives, D, R and JH, have been tested using this algorithm to find the optimal placement of 14 sensors for five different detection threshold cases. The first sensor is chosen based on minimum D, maximum R and Maximum JH while the successive sensors are chosen as the marginal decrement of D, the increment of R and increment of JH for objectives D, R and JH, respectively. Fifteen tests have been carried out (five for each formulation with five different detection thresholds) for three formulations.

Formulation 1 (D)

Formulation 2 (R)

The maximum Reliability (R) that can be achieved by the current Massa Lubrense network with the existing data is 97.39%. This is simply because out of 1916 nodes in the system, 1866 nodes receive the DWF. So, a contamination scenario at those remaining nodes (50) will always remain undetected. 7.7 that in the case of optimal placement of sensors for detection threshold 0.001, 0.0001 and 0.00001 mg/l, 12 out of 14 places are exactly same or very close to each other. So, after analysing three objectives using GR1, it seems that within the range of 0.001-0.00001 mg/l the dilution has no significant influence on the optimal placement of sensors.

Approach 2 (GR2)

This algorithm can be realised as an enumerative approach of GR1. Several tests have been carried out for 1-14 sensor configurations with five different detection thresholds using two separate objectives D and R. The objective JH is not considered during the analysis as it is computationally too expensive for this algorithm. Nevertheless, an idea about JH can be gained from the comparative analysis of other two objectives.

Formulation 4 (D)

With GR2 using D as objective, a total number of 70 tests have been performed (14 sensor configurations and each with five detection threshold). For the sake of brevity, only six of them are shown in Figure 7.8. observation is that in the case of approach 2 (GR2), the successive selection of sensor positions does not remain same for all sensor configurations. For instance, the 1 st , 2 nd , ..., 5 th locations in the five sensor configurations are not same in the 14 sensor configuration.

Final and most important observation is that despite not maintaining the order of selecting the sensors, in the final design the placements obtained from both procedures are very similar to each other. Moreover, the comparison of average Detection time attained from two formulations also shows that the solutions obtained from both approaches (GR1 and GR2) are almost identical.

Formulation 5 (R)

It is already observed from GR1, using R as objective, that the maximum R is achieved with a different number of sensors for different detection thresholds. A fascinating observation is that the optimal solutions obtained from both algorithms for all sensor configurations and for all detection thresholds are exactly same, even regarding successive order.

So, from the analysis of the approach GR2, it can be stated that applying some heuristics in choosing the first sensor to reduce the computational burden does not compromise much on the quality of the optimal solution.

Approach 3 (GR3)

The 7.2.

Formulation 6 (DR)

Figure 7.9 is showing the change in two objectives (D and R) with a number of sensors for both with and without considering penalty on non-detected scenarios. The trend of Figure 7.9b is very similar to those obtained from the GR1 using D and R as objectives.

However, the plots of D in Figure 7.9a show some irregularities. It can be seen from Figure 7.9a that for the first sensor the D is increasing from detection threshold 0.1 mg/l to 0.00001 mg/l. This is because as no penalty is considered for this case, with decreasing the detection thresholds more and more contamination from the distant part of the network are likely to be detected by the sensor under consideration and hence the average time is also increasing. This effect continues until five sensors are added, and then D follows the same trend as in Figure 7.9b. The effect of dilution on optimal placement of 14 sensors is shown in Figure 7.10. Figure 7.10a is showing placements without considering the penalty while a penalty is considered in Figure 7.10b. It is worth mentioning that 13 out 14 places are located exactly same or very close to each other in both cases (with either penalty or no penalty).

Another interesting observation is that the sensor placements for detection threshold 0.0001 and 0.00001 mg/l both the cases with and without considering penalty are exactly same. Moreover, the effect of the penalty on the optimisation process is shown in Figure 7.11. It can be deduced from Figure 7.11 that with the decrease of detection thresholds the placements in both penalty and no penalty cases are coming closer and even in the case of highest detection threshold both placements are pretty close to each other (13 out of 14 places).

Formulation 7 (JHTC)

The change in objectives JH and TC with respect to the number of sensors for different detection thresholds are shown in Figure 7.12. It is clear that JH shows a very similar pattern as in Figure 7.6. It can also be seen that an increase in the number of sensors with low detection thresholds, JH flattens, and TC sharply increases, meaning that the system is heading towards the actual optima. This is because a small increase in JH is compensated by a large increment of TC.

The effect of dilution is depicted in Figure 7.13. Figure 7.13 shows no significant influence of dilution on the optimisation outcome within the detection threshold range of 0.001 to 0.00001 mg/l, as 13 out of 14 places are very close to each other for three detection thresholds. thresholds (0.001 to 0.00001 mg/l) in the case of both with and without considering a penalty. It is remarkable to note that both penalty and no penalty cases produce exactly same solutions. Moreover, to get a more clear idea about the effect of the penalty on the optimisation process, the placements are also shown for other two detection thresholds (Figure 7.17). It can be said from Figure 7.17 that even with higher detection thresholds the placements considering penalty and no penalty are very similar to each other.

From the analysis of GR3 approach, it can be concluded that within the detection threshold range of 0.001 to 0.00001 mg/l the dilution has very little impact on the optimisation procedure while penalty has almost no significant impact on the optimisation process in the entire dilution range (0.1 to 0.00001 mg/l). Before moving to the discussion section, a comparison among two greedy algorithms (GR1 and GR3) regarding final sensor locations is shown in Figure 7.18. These are the optimal placements of 14 sensors with three different detection thresholds for five different formulations using GR1 (Formulation 1 and 3) and GR3 (Formulation 6, 7 and 8). The Figure shows that in all formulations there is a considerable number of places that coincide with each other.

Discussions

Three greedy algorithms with different objectives have been presented in this chapter to design the optimal placement of 1-14 sensors for five different detection thresholds. It is very interesting to observe that penalty has not played a significant influence while within a detection threshold of 0.001 to 0.00001 mg/l dilution has an trivial role in the optimisation procedure.

A comparative analysis has been performed in this section among nine different solutions (three from a previous study (Banik et al., 2015a), six from this study), considering four criteria (D, R, JH and TC) for three sensor configurations (8,12 The first measure is calculated as:

W i = { (O i_max -O i ) (O i_max -O i_min )
if objective i has to be minimised

(O i -O i_min ) (O i_max -O i_min )
if objective i has to be maximised (7.16) The second measure is calculated as:

W i = { 1 - O i O i_max
if objective i has to be minimised

O i O i_max
if objective i has to be maximised (7.17) The third measure is calculated as:

W i = { O min O i
if objective i has to be minimised

O i O max
if objective i has to be maximised (7.18) where O i_max and O i_min are respectively the maximum and minimum value of objective i among all considered solutions. Omax and Omin are the overall maximum and minimum value of objective i. In this analysis, maximum values of R and JH are used as 97.39%

and 16.71 bits while the minimum values of D and TC are taken as 5 minutes and 1 bit respectively.

Estimation of the overall performance of each approach is calculated by Eq. (7.19).

Score = 1 𝑁 𝑐 ∑ W i 𝑁 𝑐 i=1 (7.19) where Nc is the number of criteria = 4. 39 33.67 15.67 22.26 97.39 26.24 15.85 30.20 97.39 23.94 S4 14.71 7.54 97.34 31.38 15.31 15.79 97.34 24.53 15.59 16.68 97.34 22.36 S5 15.07 15.06 97.39 33.67 15.67 22.26 97.39 26.24 15.85 30.20 97.39 23.94 S6 14.70 8.32 97.39 31.27 15.32 15.78 97.39 24.40 15.60 16.66 97.39 22.22 S7 14.72 7.53 97.39 31.31 15.32 15.77 97.39 24.40 15.60 16.66 97.39 22.22 S8 15.24 15.76 97.39 33.67 15.67 22.26 97.39 26.24 15.84 24.26 97.39 23.67 S9 15.04 15.08 97.39 33.45 15.60 20.94 97.39 24.53 15.76 23.12 97.39 22.43 The score obtained from Eq. (7.19) weighs all four measures equally. Higher the score, better the solution is. The overall scores of all nine solutions for three different configurations are shown in Table 7.4. From Table 7.4 several remarks can be made. First of all, it is observed that regardless of the measures or configurations, the solution S7

(sixth formulation) always rank first. Second interesting observation is that incorporation of multiple objectives into one single objective has improved the solution. For instance solution obtained from first (S4) and third formulations (S5) is outperformed by the sixth (S7) and seventh (S8) formulations, respectively. The solution obtained from sixth formulation (S7) is as good as or even better regarding some measures than the fourth formulation (S6). Thirdly, incorporation of all four criteria (S9) seems produces slightly less overall score than the S7 solutions. However, it does not mean that S7 is clearly superior to S9. An example can be seen in Figure 7.19a where S7 and S9 are two nondominating solutions. Last but not least observation is that all the greedy solutions are at least as good as the solutions derived from multi-objective approaches proposed by Banik et al. (2015a). A graphical comparison of all nine solutions along with the existing sensor network, regarding four objectives, for 12 sensor configurations and 0.0001 mg/l detection threshold is also shown in nodes having same objective value, in a particular state the greedy algorithm will take the node that appears first and during the successive selections the other candidates in the previous tie is not checked, where might have other better solution. For GR1 and GR2, using the objective R, it is observed that even with a lower number of sensors (compared to other formulations) the network reaches its maximum achievable Reliability. This is because the measurement of R does not depend on the time of detection of a contaminant or the concentration of that contaminant at Detection time. Comparison among GR1 and GR2 shows that applying some heuristics in choosing the first sensor to reduce the computational burden does not compromise the quality of the optimal solution.

All three greedy approaches, in particular, the sixth formulation using the GR3, show the promising result. It is interesting to observe that the penalty has no significant influence

Chapter 8

This research is solely devoted to the management and protection of the sewer systems.

In particular, the focus was to develop a methodology to identify the source of an illicit intrusion with its characteristics. At the same time, some methodologies were proposed to design the optimal monitoring network in the sewer systems. This chapter is going to summarise some of the major findings from the research and then to give some recommendations for the future works.

Conclusions

Sustainable water resources management largely depends on the proper manoeuvre of the wastewater. The best management practice of wastewater is to monitor it, online if possible, not only just at the inlet or outlet of the treatment plant but also within the network. Advancement of new sensor technologies is going to make online monitoring of the wastewater at ease. Although at present the regulatory agencies do not demand an online monitoring of the wastewater, this should be done for the own sake of the operators of the treatment plant. Provided that an online monitoring network exist in a sewer system then it is possible to detect and eliminate any illicit intrusion into the system, thus saving the treatment plant from malfunctioning. In the case of the illicit intrusion coming from an unauthorised discharge of an industry, the corresponding regulatory agencies can make an immediate response. This way the operators can work integrally with the regulatory agencies.

In this study, two major aspects of the sewer system management are covered. The first one is the identification of the source of an illicit intrusion with its characteristics while the other is the optimal design of a monitoring network in the sewer systems. Some major findings obtained studying those two aspects are summarised below.

Source identification (SI)

Very few works have been done on SI in wastewater systems. Field et al. (1994) and Irvine et al. (2011) proposed a methodology for identifying the illicit intrusion in a separate storm sewer. In both cases, the methodology was implemented using a laboratory-based sample analysis. Besides, in this research the SI methodology is implemented on a combined sewer, based on online sensor measurements. The SI methodology is formulated as an optimisation model solved by using a single objective optimiser GAlib [START_REF] Wall | GAlib: A C++ library of genetic algorithm components[END_REF]. SWMM (Rossman, 2010) is used to perform the hydraulic and water quality simulations. The absence of any SWMM programmer's Toolkit was making it impossible to interact with SWMM from C++ environment. So, an ad-hoc Toolkit to accomplish the SI methodology was inevitable. The newly built Toolkit (Banik et al., 2014) is a dynamic link library of 33 new functions that can retrieve and set the required parameters to implement the SI methodology. Four of those functions are developed to perform the pre-screening procedure while three to extract SWMM-induced concentration data to accomplish the optimal design of monitoring network.

It is observed that computational burden is a vital concern for a large system. The computational effort is almost linearly proportional to the number of nodes in the system.

To cope up with that, a pre-screening procedure (Banik et al., 2015a) was introduced before the optimisation procedure. The methodology is based on the pollution matrix concept that try to find a significantly reduced number of candidate nodes. The noncandidate nodes and their associated links are removed from the network after the inclusion of the adjusted flow and time pattern into the network. The optimisation is done on those limited number of nodes of the significantly reduced network. It is established that introduction of the pre-screening methodology can reduce the computational burden significantly without deteriorating the optimisation outcome.

The uncertainty analysis of inflows and sensor measurements were performed to justify the robustness of the SI methodology. It is noticed that errors in sensor measurement have less influence on the success rate in identifying the correct source while inflows have more influence on the SI success, even though success percentage was considerable at significantly high uncertainty level. It was interesting to observe that the sensor placement can play a substantial role in both the success rate and computational time of the SI methodology (Banik et al., 2015b). That is why the author also proposed some methodologies to design a monitoring network optimally.

Optimal design of monitoring network

Online sensors can deliver an early warning to a pollution event. Based on the early warning, the operational staff will have an opportunity to respond to the event by taking the corrective action to minimise the impact. The corrective actions can be made through shutting the influent of the treatment plant, diverting polluted flow to a storage basin or neutralising the flow by chemical treatment. Unlike drinking water sector or river systems, in literature, there are no mathematical models or methodology for designing the optimal location of monitoring stations in sewer systems. The current practice is to place those sensors at the key facilities, such as pump station, wet wells, and manholes (Bahadur & Samuels, 2011). In this research, different methodologies have been tested

to design the optimal placement of sensors in sewer systems.

First, an Information Theory (IT)-based (Shannon, 1948) methodology has been adapted to find the optimal placement of a limited number of sensors (Banik et al., 2015c). The selection of high entropy points leads to redundant information, whereas the selection of lower entropy points will produce less information. This dilemma leads to using the multiobjective optimisation approach. Two objectives: Joint entropy (JH) and Total Correlation (TC) are maximised and minimised, respectively using NSGA-II (Deb et al., 2002). The test was performed on real sewer systems Massa Lubrense, a town near Naples, Italy. The optimisation outcomes were compared with the existing monitoring network in the Massa Lubrense sewer systems and with common practice (placing sensors before and after pump stations). The comparison shows all three scenarios are only a suboptimal solutions of the IT-based optimisation outcome. However, in the case of unavailability of any models or method to design a monitoring network, placing sensors before the pump station would be a good choice.

In the next multi-objective optimisation approach [START_REF] Banik | Evaluation of different formulations to optimally locate pollution sensors in sewer systems[END_REF], Detection time, to be minimised, and Reliability, to be maximised, are considered as objectives and the optimisation problem is again solved by using the NSGA-II. Apart from the end of Pareto front all the solutions were promising. Then two improvements was made in the methodology. First, a screening procedure, based on the entropy value, was introduced before the optimisation process. Afterwards, the NSGA-II was guided by putting some good solutions obtained from a Greedy-based approach into the initial population. The entire Pareto front improved significantly upon implementation of those two improvements. It is well known that the search space of an optimisation problem plays a significant role in the outcome. So, in the case of large networks, the application of the IT as a screening method to reduce the search domain has huge potentiality.

At the end, the applicability of a less computational expensive Greedy-based optimisation technique over NSGA-II is tested [START_REF] Banik | Greedy algorithms for designing optimal sensor network for contamination detection in sewer systems[END_REF]. Greedy-based approaches are only applicable for single objective problems. However, in the case of more than one objective those objectives were formulated into a single fitness function, a replication of single objective. It is worth mentioning that, in the case of a large system, the Greedybased optimisation heuristics could be a good alternative to other computationally expensive optimisation approaches, such as a genetic algorithm.

Recommendations

As a young field, there are lot to do than what have been done. There is huge space for making improvement of both aspects that have been presented in this thesis. Despite having the good performance of the SI methodology, different other possibilities could be explored. The possibilities could be: using a different objective function, a different optimisation algorithm, even using a hydraulic and water quality simulator other than SWMM. Some strong assumptions have been made in developing methodologies for both aspects that might cause deviation of the results, to some extent, from the reality.

Although it is not trivial, elimination of those assumptions will certainly improve the representativeness of those methodologies. Some of the important recommendations for future works are listed below.

 The placement of monitoring stations largely influences both the pre-screening procedure and the SI outcome. In this research, the monitoring stations are randomly placed. It would be nice to perform the SI methodology on an optimally designed sensor network and afterwards to perform a rigorous sensitivity analysis on the SI performance for a different point of intrusion. In that case, the monitoring network should be designed not only considering the SI methodology but also taking into account the pre-screening procedure.

 It is observed that online monitoring could be beneficial for both the operator and the regulatory agency. However, first and foremost, the sensor technologies should be accepted by both the operator and the regulator. With the advancement of new sensor technologies, the acceptance will be obvious in near future. The law enforcement agencies could have think of shifting from time-consuming laboratory-based monitoring techniques to real-time online monitoring.

 The ad-hoc SWMM Toolkit presented in this thesis is developed just for the purpose of performing the SI and optimal sensor placement methodologies. It would be good to have a complete programmer's Toolkit of SWMM like the one for EPANET [START_REF] Rossman | EPANET 2: users manual[END_REF].

 A bold assumption, the contaminant is a single source conservative one, is made in producing the synthetic contamination events. A huge amount of work could be done on that issue. First of all, although not trivial, the dispersion and biochemical transformation of a chemical could be considered for a specific contaminant. Secondly, multiple source of same chemical or different chemicals with interaction among each other could have been analysed. At this point, all focus is on the point source but inclusion of non-point source during the storm event can make the methodology even more complicated.

 Computational burden is one of the biggest challenges of working with a large sewer systems. In this thesis, a pre-screening procedure is introduced before the optimisation process that can reduce the computational effort significantly.

Besides, some other possibilities could be explored along with the pre-screening method. Skeletonisation of the large network into a relatively small network having less number of nodes, by removing some intermediate nodes, could be a good option. The calibration of the new network has to be done very carefully.

However, in that case instead of identifying the exact point, a small region will be spotted.

 Moreover, integration of parallel computing such as Parallel Virtual Machine (PVM) or Message Passing Interface (MPI) can reduce the computation burden significantly.

 In the current source identification methodology, both hydraulic and water quality simulations are run for each iteration in the optimization procedure. As hydraulic simulation is independent in each iteration, this part could be seperated from the water quality simulation. So, the strategy is to run one hydraulic simulation at the beginning of the optimization procedure and in the subsequent step the optimization will be done just running the water quality simulator. In that case, a code has to be written, perhaps based on the Graph theory, to simulate the contaminant in the sewer network once the hydraulic simulation is completed.

This will significantly reduce the computational burden.

 Although no sensitivity study has been done, the Author's opinion, in the source identification methodology among the four decision variables (Location, Concentration, Starting time and Duration) the last two are less significant than the first two as we can speculate the later two variables based on the sensor measurements. The reduction of two variables will further reduce the computational effort and will also improve the quality of the source identificaton procedure, at least in terms of location. This simplification is relevent as the methodology should be implemented online. However, as an offline measure other two variables might also be considered to get a more detailed picture.

 In the Information Theory, the information is measured as the entropy unit. Using this concept along with another concept "Value of information" (Alfonso et al., 2010), the information could have been quantified as the monetary unit that will be more plausible to the respective authorities.

  University of Cassino and Southern Lazio, Italy: Caterina, Claudia, Dr. A. Evangilesti, Dr. F. Di Palma, Dr. M. Albano, Dr. S. Papirio, Dr. R. Pignatelli, Dr. R. Spacagna, Enza, Erminio, Lorenzo, Mario, Michele, Roberta and Simone. At the same time thanks to all my ETeCoS 3 colleagues. Thanks to Chiara and Rick for doing the Dutch translation of my abstract. Thanks to Dr. Rashed and Saiful for providing a lot of research articles.

  and regulators are operated by the routing portion. SWMM tracks the quantity of runoff generated within each subcatchment, evaluating the flow rate and depth in each pipe and channel during a simulation period comprised of multiple time steps. SWMM also has the ability to analyze the buildup, washoff, transport and treatment of a number of water quality constituents during either wet or dry weather flow conditions.

  Figure 2.1.

Figure 2 . 1 .

 21 Figure 2.1. Schematic representation of the SI methodology [adapted from Preis and Ostfeld (2007)]

  of the SI problem having only one argument "elapsed time". In the new function another argument, "objective function score", has been added as in each time step the SI methodology demands the score of an objective function. All the Toolkit functions can be found in Appendix 2.1.

Figure 2 . 2 .

 22 Figure 2.2. Data flow diagram of SWMM-SI Toolkit

  1) where i = sensor index; t = time step; C it obs and Cit = measured and simulated concentration at sensor i at time step t, respectively; L = intrusion node index; C0 = release concentration (mg/l); T0 = release starting time; D = release duration (h); t0 = time of the first detection of the contaminant at the sensor i; tc = ending time of simulation; Ns = total number of sensors. The simulated concentrations are computed through a forward quality simulation, fixing the values of the unknown source characteristics, which are herein represented by the four decision variables: (1) Pollution injection node, L; (2) Pollutant concentration at the source, C0; (3) Injection starting time, T0; and (4) Injection duration, D. Then, the optimal value of the objective function F [Eq. (3.1)] is obtained modifying the values of these variables. For solving the optimisation problem, the linked simulationoptimisation procedure described in the next section is used.

  chromosomes. A typical GA, like the one incorporated into the methodology, starts with the generation of a random set of the population, then the objective function score is evaluated for each individual in the population. Afterwards, the algorithm generates a new set of the population through selection, crossover and mutation. The above steps are repeated until a prescribed objective function threshold value is reached or if a predefined number of generations is attained.

Figure 3 . 1 .

 31 Figure 3.1. Pre-screening procedure and SI methodology scheme

  End of for loop at row 2

3. 2 .

 2 The network consists of eight nodes and seven links. Two sensors are placed at node 3 and 7 and both have at least one nonzero pollutant measurement. The adjacency matrix (A) and the corresponding pollution matrix (P) for this network are reported on the right side of Figure3.2.

Figure 3 . 2 .

 32 Figure 3.2. Example scheme and application of the pre-screening procedure

  Figure 3.3(a) the lines with the C label represents the natural stream while the sewer pipes are reported with thick black lines, with the P label. The interceptor, indicated with thin black lines with the I label, are pipes designed to capture the sanitary flows during dry weather periods and convey them to the WWTP. The flow regulators (weirs and orifices) and the pump station are also depicted, along with the eight nodes in which the DWF are present.Two monitoring stations are considered and arbitrarily placed at node JI3 and JI13 (Figure3.3). Synthetic measurements are generated through a SWMM quality simulation assuming a continuous three hours injection of a pollutant at node "J1" with a concentration of 20 mg/l starting from 9 a.m. The routing time step is 30 seconds and the reporting time step is 10 minutes.

Figure 3 . 3 .

 33 Figure 3.3. Scheme of SWMM example 8 network

Figure 3 .

 3 3(b) and Figure 3.4(b) for the two considered test cases. While not a big difference is observed for the Example 8 scheme, [Figure 3.3(b)] the Massa Lubrense system is modified with the 69% reduction of nodes, after the application of pre-screening procedure [Figure 3.4(b)].

Figure 3 . 4 .

 34 Figure 3.4. Scheme of existing sewer network Massa Lubrense11

  i = sensor index; t = time step; C it obs and Cit = measured and simulated concentration at sensor i at time step t, respectively; L = intrusion node index; C0 = release concentration (mg/l); T0 = release starting time; D = release duration (h); t0 = time of the first detection of the contaminant at the sensor i; tc = ending time of simulation; Ns = total number of sensors. In case of the same percentage error for two different measurement values, the adopted formulation of the fitness function gives a larger weight to the larger one. In fact, the same percentage error is less important in the case of a measurement close to the threshold instrumentation, which has low Reliability. The square of the differences is used to have only positive values. Measured concentrations are input data of the problem, furnished by the sensor stations placed in fixed positions in the system. Other input data are represented by the system geometry, along with the external inflows. The simulated concentrations are computed through a forward quality simulation, fixing the values of the unknown source characteristics, which are herein represented by the four decision variables: (1) Pollution injection node, L; (2) Pollutant concentration at the source, C0; (3) Injection starting time, T0; and (4) Injection duration, D. Then, the optimal value of the objective function F [Eq.

Figure 4 . 1 .

 41 Figure 4.1. Scheme of the SWMM Example 8 network

Figure 4 . 2 .

 42 Figure 4.2. Hourly dry weather inflows pattern factors for SWMM Example 8 and Massa Lubrense system

  Figure 4.1(b)], with five nodes have been cut, two of them with the inflow. The flow coming from the cut sections is added to nodes JI4 and JI5. The success percentage of 50 runs in identifying the correct source is the same (96%) of the test without the pre-screening. The average of the estimated input concentration is

Figure 4 . 3 .

 43 Figure 4.3. Preliminary analysis for fixing number of generation

  Figure 4.5 reports in a box plot the results related to the estimate of the initial concentration for different CV values. In particular, assuming that the estimated values follow a Gaussian distribution, the middle line is the mean while the upper and lower limits of the box represent the 75th percentile and 25th percentile, respectively. Finally, the whiskers (the lines above and below the box) indicate the mean plus/minus the standard deviation, respectively. Considering the inflow effect, the uncertainty in evaluating the input concentrations increases with CV but the mean value is still close to the exact one. A similar trend of the result is also found for the starting time and the duration.

  system is analyzed over a 6 hour simulation period (8 a.m.-2 p.m.), with a routing time step of 10 seconds and a reporting time step of 10 minutes. The computational time required for a single SWMM run without considering pre-screening is 3 s. Two tests with different monitoring stations disposition are presented, to show its influence on the source identification results. Three monitoring stations are arbitrarily chosen at nodes N42, N241 and N219 (Test A) [Figure 4.6(a)] and nodes N242, N150 and N181 (Test B) [Figure 4.7(a)]. The synthetic measurements of concentration values are listed in Table4.2 for both tests. For the GA parameters, the same values adopted for the base run of the SWMM Example are considered (Table4.3).

Figure 4 . 4 .

 44 Figure 4.4. Percentages of identification of the correct source for different CV values considering inflow uncertainty and error measurements

  Figure 4.6(b)], with the elimination of the 69% of the nodes. The string length for representing the problem variables has been initially fixed equals to 23, and then it is reduced to 21 when applying the pre-screening procedure.The methodology is repeated 100 times, with a success rate of identifying the right node equal to 86%. However, for the unsuccessful cases the identified nodes are close to the right source: N1 (10%), N45 (2%), N17 (2%). The corresponding mean and standard deviation of estimated initial concentration are 19.86 mg/l and 0.84 mg/l, respectively.For the release starting time and the duration the estimated means are 8:55:49 and 3:04:11, respectively while the standard deviation value for both parameters is 00:15:23.The results confirm the good performances of the proposed methodology, suggesting the important role of the pre-screening procedure in case of large networks. In fact, the elimination of non-candidate nodes with the significant modification of the scheme[Figure 4.6(b)] produces a consequent minor request of the computational effort, with the Page | 64 reduction of the computation time for each SWMM-GA simulation, estimated equal to the 75%.

Figure 4 . 6 .

 46 Figure 4.6. Scheme of the Massa Lubrense system (Test A)

Figure 4 . 7 .

 47 Figure 4.7. Scheme of the Massa Lubrense system (Test B)

  transport simulation USEPA's Storm Water Management Model (SWMM) along with a SWMM Toolkit developed byBanik et al. (2014) has been used for the hydrodynamic and contaminant fate and transport analysis of a conservative contaminant. SWMM(Rossman, 2010), a well documented and widely used public software, is a dynamic rainfall-runoff simulation model that computes runoff quantity and quality from, primarily, urban areas. It has been used in diverse sectors of water resource management. For instance,Telci et al. (2009) have used this model to generate water quality data in introducing a methodology for the optimal placement of monitoring stations in a river system whileBanik et al. (2015) have introduced a pollution source identification methodology in the sewer system using this software. It uses the Manning's equation to calculate the depth of flow in conduits and in computing the flow within a conduit SWMM uses the conservation of mass and momentum equations. The contaminants are transported through the conduit link respecting the assumption that conduit behaves as a continuously stirred tank reactor (CSTR).

  Six hours SWMM simulation time has been taken for the data extraction process, with a routing time step of two seconds and a reporting time step of five minutes. So, the size of the extracted time series is 137952 at each one of the 1916 nodes. The peak contaminant concentration profile obtained from one of these instantaneous events (intrusion at node 1) is shown as a typical outcome profile along one sewer path in Figure 5.2.

Figure 5 . 1 .

 51 Figure 5.1. Scheme of Massa Lubrense Sewer System

Figure 5 . 2 .Figure 5 . 3 .

 5253 Figure 5.2. Typical transport and dilution of a contaminant event along a sewer path of Massa Lubrense (Intrusion at Node 1)

  (100,100),(100,200),(200,200). The experiments are carried out varying the number of monitoring stations from 7 to 14. The crossover and mutation probabilities have been fixed to 0.9 and 0.1 respectively. The final solutions for each configuration of monitoring stations are determined from three Pareto fronts considering high Joint Entropy and less Total Correlations (Figure5.4).

Figure 5 . 4 .

 54 Figure 5.4. Solutions from multi-objective optimisation approach

Figure 5 . 5 .Figure 5 . 6 .

 5556 Figure 5.5. Change of two objectives with the number of monitoring stations for most informative solution

Figure 5 . 7 .Figure 5 . 8 .Figure 5 . 9 .

 575859 Figure 5.7. Location of existing monitoring stations and corresponding optimised location

  with the most informative solution, in terms of Joint Entropy in the Pareto front, obtained from the multi-objective optimisation is shown in Figure 5.8.

6. 1 .

 1 It is a combined sewer system, covering an area of 19.71 km 2 , divided into 12 subcatchments, serving a population of 14,087 (the year 2011) with an approximate amount of yearly produced wastewater of 1.13 × 10 6 m 3 (2011). The scheme consists of 1909 circular conduits connecting 1902 junctions, 14 pumps, 14 storage units and 1 treatment plant. The wastewater arrives at the treatment plant through two entry points, 1901 and 1902. In dry weather condition, 1866 nodes receive inflows. The daily mean values of the Dry Weather Flows (DWF) are depicted in Figure6.1.

Figure 6 . 1 .

 61 Figure 6.1. Scheme of Massa Lubrense Network

Figure 6 . 2 .

 62 Figure 6.2. Entropy map of the system in bits (k = 10000)

Figure 6 .

 6 Figure 6.3 that the network of existing sensors is sub-optimal, and there exist better solutions even with less number of sensors.

Figure 6 . 3 .

 63 Figure 6.3. Procedure 1 (IT): Pareto front with a different number of sensors

Figure 6 . 4 .

 64 Figure 6.4. Procedure 1 (IT): objectives values for the optimal solutions selected from the Pareto fronts using two methods (most informative and compromised solution) corresponding to the different number of sensors

Figure 6 . 5 .

 65 Figure 6.5. Procedure 1 (IT): placements of the optimal solutions selected from the Pareto fronts using the maximum Joint entropy method correspond to 8, 10, 12 and 14 sensors

Figure 6 . 6 .Figure 6 . 7 .

 6667 Figure 6.6. Procedure 1 (IT): optimal placement of 12 sensors using two methods (Most informative solution and compromised solution) along with the existing network

Figure 6 .

 6 8 shows the D and R values corresponding to the selected solution

Figure 6 . 8 .

 68 Figure 6.8. Procedure 2 (DR): objectives values for the most reliable solution selected from the Pareto fronts corresponding to the different number of sensors

Figure 6 . 9 .Figure 6 .Figure 6 . 11 .

 696611 Figure 6.9. Procedure 3 (DR_IT): Pareto front with a different number of sensors

Figure 6 .Figure 6 . 13 .

 6613 Figure 6.12. Procedure 5 (DR_IT_GR): Pareto front for the optimal solutions selected for different number of sensors

Figure 6 .

 6 14 reports the objective values for the different number of sensors and different detection thresholds for the most reliable solutions obtained from the Pareto fronts. The left axis is denoting the Reliability (R) while the right axis is showing the corresponding Detection time (D). It can be observed that the R increases with increase in a number of sensors and with a decrease in the detection threshold (dilution). However, the trend of increment has two distinct patterns, one before 7 sensors where R increases at a faster rate, and the other is after the 7 sensors where it increases mildly. Moreover, the line with the highest threshold value (1 mg/l, red line with an open circle) has a very low Reliability compare to the immediate next threshold line. The 1 mg/l threshold is, in fact, unrealistic and even with 100 sensors only 93% of the Reliability can be achieved. The average Detection time decreases with the increase of a number of sensors as well as decrease in the detection threshold.

Figure 6 .

 6 Figure 6.14. Procedure 5 (DR_IT_GR): change of objectives with the number of sensors for most reliable solution considering different detection thresholds

Figure 6 .

 6 Figure 6.15. Procedure 5 (DR_IT_GR): optimal sensor placement of four different configurations for most reliable solutions with different detection thresholds

  or heuristic algorithms have been used to solve the associated optimisation problem by most of the researchers. Greedy algorithms are usually simpler and computationally less expensive than other heuristics such as a genetic algorithm. Although not much evidence of the application of greedy algorithms has been reported in the current literature on water resources, Alfonso et al. (2013) have highlighted the promising outcome from a rank-based greedy algorithm in designing the discharge monitoring network of a river. Although, they have used this algorithm for checking the quality of the Pareto optimal solutions derived from a multi-objective approach at its extreme ends, the potentiality of the algorithm as a design tool is hinted there. This chapter presents original research to identify the optimal position of a limited number of monitoring stations in sewer networks founded on the Greedy algorithms (GR). Three different greedy algorithms with eight formulations are proposed and compared in this chapter. Four different design objectives [Joint entropy (JH), Total Correlation (TC), Reliability (R) and Detection time (D)] with different combinations have been used for constructing different formulations.

  . for both with and without penalty

Figure 7 .

 7 Figure 7.2, is a combined sewer system, having 12 subcatchments that covers an area of 19.71 km 2 and serving a population of 14,087 (2011). The scheme consists of 1909 circular conduits connecting 1902 junctions, 14 pumps, 14 storage units and one treatment plant. There are two entry points, marked as 1901 and 1902 in Figure 7.2, to the treatment plant.Figure 7.2 also depicts the distribution of dry weather flow (DWF).

  Figure 7.2 also depicts the distribution of dry weather flow (DWF). Out of 1916 nodes (junctions, storage units) 1866 nodes receive DWF. Approximate amount of wastewater produce in Massa Lubrense is 1.13 × 10 6 m 3 /year (2011).

Figure 7 . 2 .

 72 Figure 7.2. Scheme of Massa Lubrense Network

Figure 7 .

 7 Figure 7.3 shows the change in average Detection time D with the varying number of sensors and different detection thresholds. It can be observed that for a small number of sensors, average Detection time sharply decreases as new sensors are added to the monitoring network. However, for a network with a large number of sensors, a more gradual decrease in average Detection time is obtained. Another interesting observation

Figure 7 .

 7 Figure 7.4 is showing the optimal placement of 14 sensors for three different detection thresholds (0.001 mg/l, 0.0001 mg/l and 0.00001 mg/l). It is worth mentioning that, even with different detection thresholds, 13 out 14 sensors are located either in the same site or very close to each other in the final design. This means, within that detection limit (0.001-0.00001 mg/l), dilution does not have a significant influence in the optimisation process. For other two thresholds, not shown here, slightly different placements are observed which can be perceived from Figure7.3, where those two threshold lines are quite distant away from the remaining lines.

Figure 7 . 3 .

 73 Figure 7.3. Formulation 1: change of average Detection time (D) with the number of sensors respect to different detection thresholds ranging from 0.1 to 0.00001 mg/l

Figure 7 .

 7 5 is reflecting the change of R of the sensor network with the number of sensors for different detection thresholds. It shows that for a small number of sensors the R increases more sharply with the addition of new sensors. The maximum R achieves for detection threshold 0.1, 0.01, 0.001, 0.0001 and 0.00001 mg/l are with 11, 8, 6, 6 and 5 sensors, respectively. This is because, R is computed through a simple binary measure (0 or 1) which only considers whether the network detects a contaminant within the simulation period. The computation of R does not depend on which time contamination is detected or what is the concentration at detection.

Figure 7 . 4 .Figure 7 . 5 .Figure 7 .

 74757 Figure 7.4. Formulation 1: optimal sensor placements for three different detection thresholds ranging from 0.001 to 0.00001 mg/l

Figure 7 . 6 .

 76 Figure 7.6. Formulation 3: change of Joint entropy (JH) with the number of sensors respect to different detection thresholds ranging from 0.1 to 0.00001 mg/l

Figure 7 .Figure 7 . 7 .Figure 7 . 8 .

 77778 Figure 7.7. Formulation 3: optimal sensor placements for three different detection thresholds ranging from 0.001 to 0.00001 mg/l

  sixth formulation consists of D and R where the first monitor is chosen based on the node with highest R. The seventh formulation combines two objectives of IT group (JH and TC) and maximum entropy is used for choosing the first sensor. All four objectives are considered in the final formulation, and a combined score of entropy and R is taken as the selection criteria of the first sensor. Besides, sixth and eighth formulations are analysed both with and without considering penalty on non-detected scenarios. For all cases, the tests have been performed for 1-14 sensors and five detection thresholds (0.1 to 0.00001 mg/l). To evaluate Eqs. (7.13) to (7.15), the maximum and minimum values of D, R, JH and TC are required. The maximum D and R are used as 360 minutes and 97.39% while the minimum D and R are 5 minutes and 0, respectively. The maximum and minimum values of other two objectives are presented in Table

Figure 7 . 9 .

 79 Figure 7.9. Formulation 6: change in objectives with the number of sensors for different detection thresholds (0.1 to 0.00001 mg/l). a) No penalty considered for non-detected scenarios b) Penalty of 360 minutes is considered for non-detected scenarios

Figure 7 . 10 .Figure 7 .Figure 7 . 12 .Figure 7 . 13 .Figure 7 .

 71077127137 Figure 7.10. Formulation 6: sensor placement for different detection thresholds (0.001 to 0.00001 mg/l). a) No penalty considered for non-detected scenarios b) Penalty of 360 minutes is considered for non-detected scenarios

Figure 7 .Figure 7 . 15 .Figure 7 . 16 .Figure 7 . 17 .

 7715716717 Figure 7.14. Formulation 8: change in objectives [Reliability (R) and Detection time (D)] with the number of sensors for different detection thresholds (0.1 to 0.00001 mg/l). a) No penalty considered for non-detected scenarios b) Penalty of 360 minutes is considered

Figure 7 . 18 .

 718 Figure 7.18. Comparison of optimal sensor placements for five formulations associated with GR1 and GR3 for three detection thresholds (0.001 to 0.00001 mg/l). 1 = Formulation 1; 2 = Formulation 3; 3 = Formulation 6; 4 = Formulation 7 and 5 = Formulation 8

  and 14 sensors) with a detection threshold of 0.0001 mg/l. The values of all four criteria are recomputed, where necessary, for all nine solutions considering penalty on the non-detected scenarios. The solutions taken fromBanik et al. (2015a) are obtained from multi-objective optimisation using NSGA-II. The first solution (S1) is obtained considering two objectives JH and T C. In the second solution (S2), the authors have used D and R as the objectives. The third solution (S3) is also derived from two objectives D and R but an improvement is made in the optimisation procedure by introducing a guided NSGA-II approach where two solutions derived from the single objective greedy approach (D and JH as objectives) have been inserted into the initial population of NSGA-II. For each case, 50% of the data have been filtered before the optimisation process. The first optimal solution chosen from the Pareto front is based on maximum JH while for other two cases the selection criterion is Maximum R. Out of six solutions considered from the present study two are taken from GR1 (first (S4) and third (S5) formulations), one from GR2 (fourth (S6) formulation) and three from the GR3 (sixth (S7), seventh (S8) and eighth (S9) formulations). The results of four criteria for all nine solutions are shown in Table7.3. Three different normalised measures, all ranging [0, 1], are taken into consideration during the evaluation process.

Figure 7 .

 7 19. It is clear from the Figure that the solution with existing sensors (S10) is only a sub-optimal solution as it has highest TC and D at the same time lowest JH and R.

Figure 7 .

 7 Figure 7.19. Comparison of 10 solutions for 12 sensors configuration and with a detection threshold of 0.0001 mg/l

6 Conclusions

 6 Note: M1 = First measure; M2 = Second measure ; M3 = Third measure7.Greedy algorithms are optimisation techniques that are usually simpler and computationally less expensive than other techniques such as NSGA-II. Three greedy based algorithms with different combinations of four objectives (JH, TC, D and R) and different detection thresholds have been discussed to evaluate the optimal placement of wastewater quality sensors in the Massa Lubrense sewer system.

  Rossman, 2010) is a dynamic rainfall-runoff simulation model that computes runoff quantity and quality from, primarily, urban areas. Runoff and pollutant loads generated from precipitation in different subcatchments are functioned by the runoff component of SWMM. This runoff transported through a system of pipes, channels, storage/treatment

	Nomenclature
	C0	concentration of the contaminant at the source
	C it obs	measured concentration at sensor i at time step t
	Cit	simulated concentration value at sensor i at time step t
	D	duration of the contamination event
	F	objective function
	i	sensor index
	L	node index of the contaminant source
	Ns	total number of sensors
	t	time step
	T 0	start time of the contamination event
	t0	time of the first detection of the contamination at sensors

There is a greater variety of modelling packages for simulating both flow and quality in sewers, such as SWMM (Storm Water Management Model), MOUSE TRAP, Wallingford packages, etc.

(Butler & Davies, 2004)

. The USEPA's SWMM (

  methodology, described in the previous section, for solving a SI problem in sewer systems. So it is definitely not a complete SWMM programmer's Toolkit, but it responds to the main requirements for performing a wastewater quality simulation. The programmer's Toolkit is a DLL of functions that allows developers to customise SWMM's

	The data flow
	diagram for performing the SI problem with the proposed methodology is shown in
	Figure 2.2. In detail, the input processor module receives a description of the simulated
	network from a SWMM input file (.INP). Then, a second input file is represented by the
	SENSOR text file (.TXT), containing the information about the time series of the
	pollutant concentration measured in different sensor nodes. The file's contents are parsed,
	interpreted, and stored in a shared memory area. Both SWMM hydraulics and water
	quality solver modules carry out an extended period simulation. During this process both
	the computed hydraulic and water quality results for each pre-set reporting interval are
	written to an unformatted (binary) output file (.OUT). Finally, if requested, a report writer
	module reads back the computed simulation results from the binary output file (.OUT)

computational engine for their specific needs. It provides a series of functions that allows programmers to perform the SWMM's (the engine consists of 46 C-code file and 19 header files) water quality solution engine to their application. The functions were written in ANSI standard C, in the file swmm5.c, which provides supervisory control over the program. They can be incorporated into 32-bit Windows applications written in C/C++ or in any other language that can call functions within a Windows DLL. The Toolkit DLL file is named SWMM5.DLL. The Toolkit comes with one header file and one SWMM5.lib file that simplify the task of interfacing it with C/C++ code.

Table 2 .1. Average

 2

		DWF in different nodes
	Node	J1	J2a	J10	J11	J12	J13	Aux3	JI1
	Flow (l/s)	2.27	2.83	0	0	3.54	3.48	2.27	3.48

Figure 2.3. Scheme of the example network Table 2.2. Hourly variable

				DWF pattern
	Hour	1	2	3	4	5	6	7	8	9	10	11	12
	Multiplier 0.4	0.3	0.2	0.2	0.5	0.8	1.0	1.8	1.6	1.4	1.2	1.0
	Hour	13	14	15	16	17	18	19	20	21	22	23	24
	Multiplier 1.1	1.1	1.2	1.3	1.3	1.4	1.4	1.5	1.3	1.0	0.6	0.5

Table 2

 2

	.3. SI results.
	Solution	Node	Concentration	Starting Time	Duration
			(mg/l)	(hr)	(hr)
	Exact Solution	J1	2.0	8:00	3
	Case 1	J1	2.03529	8:00	3

Table 3

 3

.1 reports the percentage of mean absolute error and the corresponding standard deviation in computing the flow in five links after the prescreening procedure in the Massa Lubrense11 network. The reported values demonstrate that the errors introduced by cut are tiny, without any significant influence on the simulation results. In fact, the highest mean absolute error in flow measurement is only 1.76% at link L5.

Table 3

 3

	screening

.1. Error associated with link flows in Massa Lubrense11 network due to the pre-

Table 3 .

 3 2. SI result for the two test cases with and without considering pre-screening

		Without pre-screening		With pre-screening		Time reduction (%)
	Network	Success (%)	Conc. (mg/l)	Simulation Time SWMM GA opti.	Success (%)	Conc. (mg/l)	Simulation Time SWMM GA opti.	SWMM GA opti. Overall
	(1)	(2)	(3)	(4)	(5)	(6)	(7)	(8)	(9)	(10)	(11)	(12)
	SWMM Ex. 8	96	19.75 00:06:08 00:00:17 96	19.59 00:05:01 00:00:15 19	8	18
	Massa Lubrense11	66	20.59 09:43:14 00:18:16 86	19.86 02:32:18 00:02:13 74	89	75

  𝐶 𝑖𝑡 (𝐿, 𝐶 0 , 𝑇 0 , 𝐷)

	𝑡 𝑐	𝑁 𝑠	2
	𝑡=𝑡 0	𝑖=1	(𝐶 𝑖𝑡 𝑜𝑏𝑠 + 𝐶 𝑖𝑡 (𝐿, 𝐶 0 , 𝑇 0 , 𝐷))/2 )

Table 4

 4

		.1. SWMM Example 8: 2-year storm event data
	Time	11:00 11:05 11:10 11:15 11:20 11:25 11:30 11:35 11:40 11:45 11:50 11:55
	Intensity	7.37	8.38	9.65	16.26 20.57 39.88 72.39 29.97 18.03 10.67 8.89	7.62
	(mm/h)
	Time	12:00 12:05 12:10 12:15 12:20 12:25 12:30 12:35 12:40 12:45 12:50 12:55
	Intensity	5.08	4.83	4.57	4.32	4.32	4.06	3.81	3.81	3.56	3.56	3.30	3.30
	(mm/h)

Two monitoring stations are considered, arbitrarily placed at node JI3 and JI13

[Figure 4.1(a)

]. The same contamination scenario is considered for both dry and wet weather tests, with synthetic measurements generated through a SWMM quality simulation adding in the source node "J1" a continuous injection of a conservative pollutant with a concentration of 20 mg/l starting at 9 a.m. with 3 hours duration. The simulation runs from 8:00 a.m. to 2:00 p.m., with a routing time step of 30 seconds for both hydraulic water quality analyses. The computational time required for a single SWMM run is less than 1 s. The obtained synthetic measurements are listed for both dry and wet weather tests in Table

4

.2, with a reporting time step of 10 minutes.

Table 4 .

 4 2. Measured concentrations (mg/l) at sensor nodes

			SWMM Example 8				Massa Lubrense
	Time		Dry Weather JI3 JI13	Wet Weather JI3 JI13	N42	Test A N241 N219 N181 N150 Test B	N242
	11:00:00 3.9409 0.5811 3.9409 0.5811 0.1696	0	0.0597	0	0.0972 0.0206
	11:10:00 3.9035 0.6553 2.3518 0.6554 0.1713	0	0.0675	0	0.0963 0.0286
	11:20:00 3.9397 0.7252 0.6309 0.7281 0.1729	0	0.0732	0	0.0955 0.0367
	11:30:00 3.9409 0.7904 0.1619 0.8141 0.1722	0	0.0771	0	0.0952 0.0443
	11:40:00 3.9409 0.8508 0.0921 0.8658 0.1704	0	0.0797	0	0.0952 0.0511
	11:50:00 3.9409 0.9069 0.3025 0.7955 0.1695	0	0.0811	0	0.0950 0.0569
	12:00:00 3.9409 0.9589 0.4533 0.6453 0.1692	0	0.0819	0	0.0946 0.0616
	12:10:00 3.8904 1.0074 0.525 0.5185 0.1692	0	0.0823	0	0.0941 0.0652
	12:20:00 3.9388 1.0523 0.9084 0.4466 0.1562	0	0.0824	0	0.0938 0.0680
	12:30:00 3.9408 1.094 0.9588 0.4126 0.0825	0	0.0824	0	0.0930 0.0700
	12:40:00 3.9409 1.1325 1.0274 0.3989 0.0232	0	0.0823	0	0.0860 0.0714
	12:50:00 3.9409 1.1682 1.0816 0.3958 0.0044	0	0.0821	0	0.0674 0.0724
	13:00:00 3.9409 1.2014 1.1394 0.3983 0.0007	0	0.0816	0	0.0438 0.0730
	13:10:00 0.1818 1.2325 0.0375 0.4037 0.0001	0	0.0797	0	0.0245 0.0733
	13:20:00 0.0022 1.2617 0.0004 0.4099	0	0	0.0749	0	0.0123 0.0732
	13:30:00	0	1.287	0	0.4136	0	0	0.0663	0	0.0057 0.0722
	13:40:00	0	1.305	0	0.4133	0	0	0.055	0	0.0025 0.0699
	13:50:00	0	1.313	0	0.4097	0	0	0.043	0	0.0011 0.0659
	14:00:00	0	1.3099	0	0.404	-	-	-	0	0.0004 0.0601
	Table 4.3. SWMM Example 8: results of the sensitivity respect to GA parameters
						Success	Concentration	Starting time	Duration	Computational
	Case Population Generation Mutation Crossover	(%)	(mg/l)				time
							Mean SD	Mean	SD	Mean	SD	Mean	SD
	BR		40	0.01	0.9	96	19.59 0.36 9:00:00 0:00:00 3:00:00 0:00:00 0:07:08 0:00:12
	SA1	50	40	0.01	0.9	86	19.90 1.53 8:59:00 0:09:09 3:01:24 0:09:09 0:04:13 0:00:08
	SA2		40	0.02	0.9	98	19.69 0.37 9:00:00 0:00:00 3:00:00 0:00:00 0:07:45 0:00:40
	SA3		40	0.01	0.8	96

  Ostfeld, A., & Salomons, E. (2004). Optimal layout of early warning detection stations for water distribution systems security. J. WaterResour. Plann. Manage., 130(5),

	385.
	Ostfeld, A., Kessler, A., & Goldberg, I. (2004). A contaminant detection system for early
	warning in water distribution networks. Eng. Optimiz., 36(5), 525-538.
	Perelman, L., Arad, J., Housh, M., & Ostfeld, A. (2012). Event detection in water
	distribution systems from multivariate water quality time series. Environ. Sci. Technol.,
	46(15), 8212-8219.
	Plann. Manage., 136(4), 483-492.
	Qin, X., Gao, F., & Chen, G. (2012). Wastewater quality monitoring system using sensor
	fusion and machine learning techniques. Water Res., 46(4), 1133-1144.

Al-Omari, A., Fayyad, M., & Qader, A. A. (2005)

. Modeling trihalomethane formation for Jabal Amman water supply in Jordan. Environ.

Model. Assess., 9(4), 245-252. Polis, M. P., & Goodson, R. E. (1976)

. Parameter identification in distributed systems: A synthesizing overview. Proceedings of the IEEE, 64(1), 45-61.

Pouet, M. F.,

[START_REF] Pouet | Quality survey of wastewater discharges[END_REF]

. Quality survey of wastewater discharges. In P. Quevauviller et al., (Eds.), Wastewater quality monitoring and treatment

(pp. 275-288)

. Chichester: J. Wiley & Sons.

[START_REF] Preis | A contamination source identification model for water distribution system security[END_REF]

. A contamination source identification model for water distribution system security. Eng. Optimiz., 39

(8)

, 941-947.

Preis, A., & Ostfeld, A. (2008)

. Genetic algorithm for contaminant source characterisation using imperfect sensors. Civ.

Eng. Environ. Syst., 25(1), 29-39. Propato, M., Sarrazy, F., & Tryby, M. (2010)

. Linear algebra and minimum relative entropy to investigate contamination events in drinking water systems. J. Water Resour.

Rossman, L. A.

Table 6 .

 6

	1. Notation for different procedures
	Procedure	Optimiser Objective
	IT	NSGA-II	JH, TC
	DR	NSGA-II	D, R
	DR_IT	NSGA-II	D, R
		Greedy	JH
	GR

Table 6 .2.

 6 Performance of Massa Lubrense network with 8 optimal sensors

	Procedure	JH (bits)	TC (bits)	R (%)	D (min)
	IT	14.44 7.64 95.04 23.75
	DR	14.08 9.44 94.99 28.96
	DR_IT	13.47 5.99 96.45 36.13
	GR (JH)	15.07 15.06 97.39 24.93
	GR (D)	14.71 7.54 97.34 22.40
	DR_IT_GR 15.07 15.06 97.39 24.93

Table 6 .

 6 3. Performance of Massa Lubrense network with 10 optimal sensors

	Procedure	JH (bits)	TC (bits)	R (%)	D (min)
	IT	14.99 14.43 96.66 21.32
	DR	14.30 8.73 94.99 26.51
	DR_IT	13.61 5.42 96.61 34.75
	GR (JH)	15.42 18.26 97.39 22.04
	GR (D)	15.14 13.64 97.34 17.98
	DR_IT_GR 15.22 11.92 97.39 21.40
	Table 6.4. Performance of Massa Lubrense network with 12 optimal sensors
	Procedure	JH (bits)	TC (bits)	R (%)	D (min)
	IT	14.81 13.77 95.09 21.65
	DR	14.75 14.23 95.09 20.97
	DR_IT	14.88 10.54 96.61 18.71
	GR (JH)	15.67 22.26 97.39 17.30
	GR (D)	15.31 15.79 97.34 15.35
	DR_IT_GR 15.67 22.26 97.39 17.30

Table 6 .5.

 6 Performance of Massa Lubrense network with 14 optimal sensors

	Procedure	JH (bits)	TC (bits)	R (%)	D (min)
	IT	15.14 18.34 95.09 17.02
	DR	14.25 13.22 96.87 27.76
	DR_IT	13.75 14.60 97.39 35.35
	GR (JH)	15.85 30.20 97.39 14.93
	GR (D)	15.59 16.68 97.34 15.17
	DR_IT_GR 15.85 30.20 97.39 14.93

Table 6 .

 6

	6. Performance of all procedures [Eqs. (6.13) and (6.14)]
	Procedure	8	Number of Sensors 10 12	14
	IT	0.59	0.64	0.20	0.57
	DR	0.38	0.40	0.20	0.60
	DR_IT	0.40	0.42	0.57	0.48
	GR (JH)	0.70	0.69	0.67	0.75
	GR (D)	0.90	0.80	0.79	0.91
	DR_IT_GR 0.70	0.79	0.67	0.75

Table 7 .

 7 1. Three approaches with different formulations

	Approach Formulation	Objective # of Tests	Remarks

  Massa Lubrense system for detection threshold of 0.1, 0.01, 0.001, 0.0001 and 0.00001 mg/l are15.70, 16.40, 16.64, 16.71 and 16.74 bits, respectively. So, by using 14 sensors the percentage of system's JH achieved are60.69, 70.08, 88.56, 94.84 and 97.50% for detection threshold 0.1, 0.01, 0.001, 0.0001 and 0.00001 mg/l, respectively. It is observed from Figure

Table 7

 7

	.2. System's JH and TC in bits for different detection thresholds
			Detection threshold (mg/l)
		0.00001 0.0001	0.001	0.01	0.1
	JHsys (bits)	16.74	16.71	16.64	16.40	15.70
	TCsys (bits)	1895.16 1601.84 1270.35 948.65	685.80

Note: JH sys = System's JH; TC sys = System's TC

Table 7 .3.

 7 The values of four criteria (JH, TC, R and D) for nine solutions

			8 Sensors			12 Sensors			14 Sensors
	Solution	JH	TC	R	D	JH	TC	R	D	JH	TC	R	D
		(bits)	(bits)	(%)	(min)	(bits)	(bits)	(%)	(min)	(bits)	(bits)	(%)	(min)
	S1	14.44	7.64	95.04 40.42 14.81 13.77 95.09 38.25 15.14 18.34 95.09 33.85
	S2	13.47	5.99	96.45 47.62 14.88 10.54 96.61 30.29 13.75 14.60 97.39 43.82
	S3	15.07 15.06 97.

Table 7 .

 7 4. Performance score obtained from three different measures

	Solution	M1	8 Sensors M2	M3	M1	12 Sensors M2	M3	M1	14 Sensors M2	M3
	S1	0.4552 0.6476 0.5237 0.1811 0.5757 0.5165 0.4715 0.6380 0.5212
	S2	0.4000 0.6236 0.5172 0.5795 0.6690 0.5356 0.5000 0.5960 0.5013
	S3	0.7073 0.5816 0.5292 0.7167 0.5785 0.5433 0.7301 0.6134 0.5476
	S4	0.8777 0.7067 0.5429 0.7772 0.6566 0.5458 0.9293 0.7303 0.5540
	S5	0.7073 0.5816 0.5292 0.7167 0.5785 0.5433 0.7301 0.6134 0.5476
	S6	0.8648 0.6951 0.5400 0.7168 0.6578 0.5463 0.9378 0.7314 0.5547
	S7	0.8867 0.7077 0.5433 0.7883 0.6578 0.5463 0.9378 0.7314 0.5547
	S8	0.7132 0.5732 0.5309 0.7167 0.5785 0.5433 0.8277 0.6640 0.5501
	S9	0.7057 0.5819 0.5289 0.7550 0.6033 0.5462 0.8509 0.6793 0.5523

Acknowledgements ................................................................................. xi Summary............................................................................................... xiii Acknowledgements

. Storm water management model user's manual. Version 5.0.

National Risk Management Research Laboratory, Office of Research and Development:

US Environmental Protection Agency. Thomas, O., Théraulaz, F., Cerdà, V., Constant, D., & Quevauviller, P. (1997).

Wastewater quality monitoring. 16(7), 419-424.

Tryby, M. E., Propato, M., & Ranjithan, S. R. ( 2010). Monitoring design for source identification in water distribution systems. J. Water Resour. Plann. Manage., 136 (6), 637-646.

Van Zyl, J. E., Borthwick, J., & Hardy, A. (2003). Ooten: An object-oriented programmers toolkit for epanet. Advances in Water Supply Management (CCWI 2003). Wall, M. (1996). GAlib: A C++ library of genetic algorithm components. Mechanical Engineering Department, Massachusetts Institute of Technology, 87, 54.

Zechman, E. M., & Ranjithan, S. R. ( 2009). Evolutionary computation-based methods for characterizing contaminant sources in a water distribution system. J. Water Resour. Plann. Manage., 135(5),[334][335][336][337][338][339][340][341][342][343] This chapter has been published as: Banik, B. K., Alfonso, L., Torres, A. S., Mynett, A., Di Cristo, C., & Leopardi, A. (2015). Optimal placement of water quality monitoring stations in sewer systems: an information theory approach. Procedia Eng., 119C, 1308-1317.

CHAPTER 5

Optimal Sensor Placement: an IT Approach Chapter 7

In this chapter, a methodology for the optimal placement of wastewater quality monitoring sensors in sewer systems is presented. Storm water management model (SWMM) is used to perform the hydraulic and water quality simulations. Three greedy algorithms have been utilised as an optimiser to solve eight proposed formulations derived from different combinations of four objectives (Joint entropy, Total Correlation, Reliability and Detection time). The methodology is tested on a real sewer network. A comparative study of all formulations along with three previously developed multiobjective optimisation approaches has been performed. The comparison shows that the proposed methodology can effectively be used in solving the optimal sensor placement problem in sewer network.

one function and obtain a single optimal solution with the expectation of having better solutions than those including separate objectives. Structurally, this algorithm, as depicted in Figure 7.1c, is closer to GR1. The differences between these two algorithms lie in choosing the first sensor and in the objective functions. In GR3, the objective function for choosing the sensors is a combination of three different objectives into a normalised single fitness function. These fitness functions are formulated in such a way that must be minimised.

The last three formulations are solved by GR3. The sixth one comprise of a fitness function DR, composed of two objectives, namely D and R and are formulated as shown in Eq. ( 7.13).

End Yes X is a discrete random variable consists of N number of sensors. S is the set of all candidate nodes as potential sensor location. M is the number of candidate nodes Obj will be used for first and second approach where only one objective will be optimized.

Obj1 will be used for designing the first sensor in the third approach. The objective will be either maximizing Reliability (R) or maximizing Information (JH) or combination of both.

Obj2 will be used to design other sensors in third approach. This objective function consists of a combination of two or four separate objectives (JH, TC, D, R)

where, Dmax and Dmin are the maximum Detection time (total simulation time) and the minimum Detection time (reporting time step considered for SWMM during the data extraction process), respectively. Similarly, Rmax and Rmin are the maximum and minimum Reliability of the system, respectively. In this formulation, the most reliable sensor (the one having highest R) is chosen as the first sensor.

The seventh formulation consists of a fitness function JHTC, where two objectives JH and TC are combined as shown in Eq. (7.14).

where TCmax and TCmin are the maximum and minimum Total Correlation of the system, respectively while JHmax and JHmin are the maximum and minimum Joint entropy of the system, respectively. In this formulation, the most informative sensor (the one with maximum entropy) is chosen as the starting sensor.

The last formulation contains the fitness function JHTCDR that combines all four objectives, as shown in Eq. (7.15). (7.15) In this formulation, the starting sensor is the one having the highest score regarding both Reliability and information content. Both sixth and eighth formulations are examined with and without considering penalty on the non-detected contamination scenarios.

The fitness functions mentioned in Eqs. (7.13) to (7.15) will provide a score in the range of 0 to 1. For a particular approach, closer the score to 0 better the solution is. In this chapter, all the variables in Eqs. (7.13) to (7.15) are considered having the same weight.

on the optimisation process while within detection thresholds of 0.001 to 0.00001 mg/l the dilution also has a trivial impact on the optimisation process. This also in line with the practical effect that such small concentrations may have in the treatment process.

Greedy approaches use some heuristics to guide the searching process that produce closeto-optimal solutions. In fact, it is not possible to attain the "real" optimal solution for the kind of problem that has been discussed in this chapter with the current technologies due to the size of the search space. However, a relative comparison with respect to some previously developed multi-objective approaches using NSGA-II shows the goodness of the greedy approaches in the optimal sensor design.

CHAPTER 8

Conclusions and Recommendations