TECHNICAL FIELD The invention relates to a method for determining sensor positions in a supply network, the supply network comprising interconnected nodes and/or junctions and/or sources and/or consumers and the supply network transporting a medium. Furthermore, the present invention relates to a corresponding control system. BACKGROUND

Although applicable to any network that transports a medium, like water networks, gas networks, petrol networks, electrical networks, and the like the present invention will mostly be described in combination with water supply networks.

In modern networks which supply a medium, like e.g. water supply networks, gas supply networks or the like, it is important to constantly monitor the status of the network and to identify possible leaks as quick as possible. To monitor a network a plurality of sensors can be used which also can be used to control the network and provide a database for further network analysis.

The number of sensors that can be used in a supply network is limited by the complexity of interfacing a huge amount of sensors and for economic reasons. Therefore, when using sensors in a supply network it is important to consider dependencies between different elements, like e.g. pipes, consumers, pump stations, or the like of the supply network when placing the sensors in the network.

Sensors can e.g. be placed based on empirical methods where the positions for the sensors are determined by expert knowledge and different recommendations or placement guidelines. Alternatively sensor positions in the network can be determined based on optimization problems which can be solved with specialized computer solvers for optimization problems. These methods provide near optimal sensor placement but require a huge amount of computing power. Another method uses hydraulic models of the network to simulate the network behaviour. But for some networks the hydraulic model is not available.

Accordingly, there is a need for easily defining sensor positions in networks with little computational effort.

SUMMARY

The present invention solves this problem with the features of a method according to claim 1 and the features of a control system according to claim 12.

Consequently, the present invention provides a method for determining sensor positions in a supply network, the supply network comprising interconnected nodes and/or junctions and/or sources and/or consumers and the supply network transporting a medium, the method comprising providing a graph representing the supply network where nodes and/or junctions and/or sources and/or sinks of the supply network are represented by vertices of the graph and connections between the nodes and/or junctions and/or sources and/or sinks are represented by edges of the graph, simulating signal propagation throughout the supply network based on the graph, and determining sensor positions in the graph at vertices and/or edges with the highest propagated signal values.

Furthermore, the present invention provides a control system for determining sensor positions in a supply network, the supply network comprising interconnected nodes and/or junctions and/or sources and/or consumers and the supply network providing a medium, comprising a memory configured to store a graph representing the supply network where nodes and/or junctions and/or sources and/or sinks of the supply network are represented by vertices of the graph and connections between the nodes and/or junctions and/or sources and/or sinks are represented by edges of the graph, a simulation unit configured to simulate signal propagation throughout the supply network based on the graph, and a position determination unit configured to determine sensor positions in the graph at vertices and/or edges with the highest propagated signal values. The present invention is based on the conclusion that no complex model or optimization problem has to be solved to place sensors optimally in a network.

Therefore, the present invention uses this knowledge and provides a method which uses assumptions about signal propagation in the network to find positions in the network with the highest propagated signal values.

Every network can be represented as a graph comprising vertices and edges. In such a graph every node, junction, sources, sinks or the like of the network can be represented by vertices. The edges in the graph can represent e.g. the pipes of the network.

With the help of the graph signal propagation from different signal sources in the network can be calculated and the sensor can be placed at the vertices or edges which show the highest value for the accumulated propagated signal. A signal in this regard can be any measurable value of the medium which is transported in the network. A signal in a water supply network can e.g. be an anomaly signal like an unsuspected pressure drop or a high pressure wave, an abnormal water consumption, or the like. In electrical networks the signal can e.g. be an overvoltage or overcurrent, undervoltage or undercurrent or the like. By determining the signal propagation throughout the network the most pertinent positions for sensor in the network can be defined without the need of complex optimizations, physical models of the network or extensive expert knowledge.

By choosing optimal sensor positions the present invention allows reducing the number of sensors needed to supervise and control a supply network and therefore reduces complexity of a control system for supply networks. The results of the method according to the present invention furthermore have a clearly visible physical meaning and allow simple interpretation by a user.

Further embodiments of the present invention are subject of the further subclaims and of the following description, referring to the drawings.

In a possible embodiment determining sensor positions can comprise determining sensor positions at predefined mandatory vertices and/or edges in the graph. This allows placing sensors at e.g. pump stations for supervising those stations, even if the signal propagation to that node, e.g. the pump station, is not strong enough.

In another embodiment determining sensor positions can comprise determining a predetermined number of sensor positions in the graph at vertices and/or the edges in a sequence defined by the magnitude of the propagated signal values starting at the node and/or edge with the highest propagated signal value. By defining a number of sensor the total amount of sensor can be limited and by choosing sensor positions starting with the vertex and/or edge with the highest propagated signal value the most notorious spots for sensor can be selected in the supply network. In one embodiment determining sensor positions can comprise determining sensor positions in the graph only in consumer vertices which consume the medium. This refers to the sensor positions chosen based on the propagated signal value und doesn't contradict the placement of sensors at mandatory vertices like e.g. pump stations. In one embodiment providing a graph representing the supply network can comprise providing generalized consumer vertices in the graph, wherein a generalized consumer vertex represents an aggregation of separate consumers of the supply network. Furthermore, a value characterising the respective consumption of the medium can be assigned to every node in the graph. This greatly simplifies the generation of the graph.

In another embodiment simulating signal propagation can comprise providing a network attenuation matrix which provides attenuation coefficients for the signal propagation for all pairs of vertices in the graph which are directly connected to each other via edges.

In one embodiment providing a network attenuation matrix comprises calculating for every pair of vertices a value of the network attenuation based on a constant amplitude multiplied with the natural exponential function of the negative weight or negative length of the edge coupling the respective vertices divided by a characteristic attenuation length. This can be done using the following formula:

A(i,j)=A*exp (-w(ij)/R) In one embodiment simulating signal propagation can comprise assigning every vertex in the graph a relative importance coefficient, especially with a value of 1.

In another embodiment simulating signal propagation can comprise additively combining faults from different fault sources in the supply network, and calculating the mean relative signal perception level for all vertices of the graph based on the inverted network attenuation matrix and a vector of all the relative importance coefficients, e.g. based on the following formula:

S(L) = A ^_1 *L In one embodiment determining sensor positions in the graph comprises determining a predefined number of sensor positions at the vertices with the highest relative signal perception levels starting at the vertex with the highest relative signal perception level.

The above mathematical definitions allow quick and easy computations of the propagated signal values.

In another embodiment determining sensor positions in the graph can comprise determining sensor positions only at vertices which are located at least at a predefined distance from the mandatory vertices and/or mandatory edges in the graph. This prevents sensors from being placed to near together where they might be redundant. BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention and advantages thereof, reference is now made to the following description taken in conjunction with the accompanying drawings. The invention is explained in more detail below using exemplary embodiments which are specified in the schematic figures of the drawings, in which:

Fig. 1 shows a flow diagram of an embodiment of a method according to the present invention;

Fig. 2 shows a block diagram of a control system according to the present invention; Fig. 3 shows a flow diagram of another embodiment of a method according to the present invention; and

Fig. 4 shows a graph which can be used with an embodiment of a method according to the present invention.

In the figures like reference signs denote like elements unless stated otherwise.

DETAILED DESCRIPTION OF THE DRAWINGS Fig. 1 shows a flow diagram of an embodiment of a method according to the present invention for determining sensor positions 4-1 - 4-n in a supply network. A supply network can comprise interconnected nodes and/or junctions and/or sources and/or consumers and the supply network transports a medium, like water, gas, petrol or petroleum.

The method comprises providing, SI, a graph 1-1 ; 1-2 which represents the supply network. In the graph 1-1 ; 1-2 nodes and/or junctions and/or sources and/or sinks of the supply network are represented by vertices 2-1 - 2-10 of the graph 1-1; 1-2. At the same time connections between the nodes and/or junctions and/or sources and/or sinks are represented by edges 3-1 - 3-9 of the graph 1-1 ; 1-2.

To define the most appropriate sensor positions 4-1 - 4-n signal propagation throughout the supply network is simulated, S2, based on the graph 1-1; 1-2. Finally, the sensor positions 4-1 - 4-n are determined, S3, in the graph 1-1 ; 1-2 at vertices 2-1 - 2-10 and/or edges 3-1 - 3-9 with the highest propagated signal values.

In e.g. supply networks it can be necessary to place sensors at specific nodes of the network, like e.g. pump stations or the like. The method according to the present invention allows such placement by determining sensor positions 4-1 - 4-n at such predefined mandatory vertices 2-1 - 2-10 and/or mandatory edges 3-1 - 3-9 in the graph 1-1 ; 1-2. Furthermore, the present invention allows limiting the number of sensors to a predetermined maximum number of sensors, where determining sensor positions 4-1 - 4-n comprises determining only a predetermined number of sensor positions 4-1 - 4-n in the graph 1-1 ; 1-2 at vertices 2-1 - 2-10 and/or edges 3-1 - 3-9. To select the most appropriate sensor positions 4-1 - 4-n the sensor positions 4-1 - 4-n are defined in a descending sequence according to the magnitude of the propagated signal values starting at the vertex 4-1 - 4-n and/or edge 3-1 - 3-9 with the highest propagated signal value.

If sensor positions 4-1 - 4-n are defined at predefined mandatory vertices 2-1 - 2-10 and/or mandatory edges 3-1 - 3-9 this number of sensor positions 4-1 - 4-n can be subtracted from the predetermined maximum number of sensors.

In one embodiment the placement of the sensors can be limited to sensor positions 4-1 - 4-n in the graph 1-1 ; 1-2 which represent consumer vertices 2-1 - 2-10 which consume the medium.

To simplify providing the graph 1-1 ; 1-2 when providing a graph 1-1; 1-2 representing the supply network at least some generalized consumer vertices 2-1 - 2-10 can be provided in the graph 1-1 ; 1-2. Every generalized consumer vertex 2-1 - 2-10 represents an aggregation of separate consumers of the supply network, wherein a value characterising the respective consumption of the medium can be assigned to every generalized consumer vertex 4-1 - 4-n in the graph 1-1 ; 1-2. This value can e.g. be calculated as the sum of the consumption of all consumers represented by the respective generalized consumer vertex 2-1 - 2-10.

To simplify the calculation and simulation of the signal propagation a network attenuation matrix A can be provided which provides attenuation coefficients for the signal propagation for all pairs of vertices 2-1 - 2-10 in the graph 1-1 ; 1-2 which are directly connected to each other via edges 3-1 - 3-9. In the network attenuation matrix A a single entry is addressed by A(i j) which represents the attenuation coefficient for the signal travelling from vertex i to vertex j if these vertices 4-1 - 4-n are connected by an edge 3-1 - 3-9. If the vertices j, j are not connected by an edge 3-1 - 3-9 this value is zero.

The network attenuation matrix A is not necessarily symmetric, i.e. A(i, j) may be different than A(j, i). This reflects the fact that the graph 1-1 ; 1-2, and the network, may have prevailing signal propagation directions. For example in a water supply network a pressure drop mainly propagates in the flow direction of the water and only slightly in the other direction.

For every pair of vertices 2-1 - 2-10 in one embodiment the value A(i, j) of the network attenuation can be calculated based on a constant amplitude multiplied with the natural exponential function of the negative weight or negative length w(ij)of the edge 3-1 - 3- 9 coupling the respective vertices 2-1 - 2-10 divided by a characteristic attenuation length R. The following formula can be applied:

A(ij)=A*exp (-w(ij)/R)

Furthermore every vertex 2-1 - 2-10 in the graph 1-1 ; 1-2 can be assigned a relative importance coefficient L. This relative importance coefficient L can be defined based on expert knowledge. For example it can be known that certain nodes of the network are more prone to failure than other. By default the relative importance coefficient L can be set to a value of 1 for al vertices 2-1 - 2-10.

According to the present invention the signal propagation is additive, i.e. the signals contribute to each vertex 2-1 - 2-10 where they come together. In other words the overall propagated signal is a superposition of signals propagated from all signal sources. If a signal arrives at a vertex 2-1 - 2-10 a signal is re-propagated to the neighbouring vertices 2-1 - 2-10 according to the network attenuation matrix A.

Given initial signal levels f in the signal sources the signal equilibrium equation can be defined as:

A*s = f

where s is the resulting equilibrium signal. Supposing that A is invertible, which is true if the attenuation is sufficiently strong, the equilibrium signal is given by:

The initial signal levels f can be the vector of the relative importance coefficients L. After the above matrices and values have been defined simulating signal propagation can easily be done by additively combining fault signals from different fault sources in the supply network. This can be done by simple matrix calculations according to the formula:

S(L) =V*L where S(L) is the mean relative signal perception level S(L) for all vertices 2-1 - 2-10 of the graph 1-1 ; 1-2 based on the inverted network attenuation matrix A ^"1 and a vector of all the relative importance coefficients L.

The sensor positions 4-1 - 4-n can then simply be defined at the vertices 2-1 - 2-10 with the highest calculated relative signal perception levels S(L) starting at the vertex 2-1 - 2-10 with the highest relative signal perception level in descending order. If sensor positions 4-1 - 4-n have been defined for mandatory vertices 2-1 - 2-10 and/or mandatory edges 3-1 - 3-9 in the graph 1-1 ; 1-2 a predefined distance r can be defined and sensor positions 4-1 - 4-n in the graph 1-1 ; 1-2 can be determined only at vertices

2- 1 - 2-10 which are located at least at the predefined distance r from the vertices 2-1 - 2-10 which represent the vertices 2-1 - 2-10 and/or mandatory edges 3-1 - 3-9.

Fig. 2 shows a block diagram of a control system 10 for determining sensor positions 4- 1 - 4-n in a supply network according to the present invention. The control system 10 comprises a memory 11 configured to store a graph representing the supply network where nodes and/or junctions and/or sources and/or sinks of the supply network are represented by vertices 2-1 - 2-2 of the graph 1-1 and connections between the nodes and/or junctions and/or sources and/or sinks are represented by edges

3- 1 of the graph 1-1. The memory 11 is coupled to a simulation unit 12 which is configured to simulate signal propagation throughout the supply network based on the graph 1-1 as described above with reference to Fig. 1. The simulation unit 12 is coupled to a position determination unit 13 which is configured to determine sensor positions 4- 1 - 4-n in the graph 1-1 at vertices 2-1 - 2-2 and/or edges 3-1 starting with the highest propagated signal values in descending order.

The elements of the control system 10 can be configured to execute every embodiment of the method as described in conjunction with Fig. 1.

The control system 10 can e.g. be embodied in a computer system, and especially as a computer program product or a non-transitory computer readable medium comprising computer readable instructions which when executed by a processor of a computer lead the processor and/or the computer system to execute any embodiment of the method according to the present invention. Fig. 3 shows a flow diagram of another embodiment of a method according to the present invention. In Blocks S10, Sl l and SI 2 the graph 1-1 ; 1-2, the network attenuation matrix A, and the relative importance coefficients L are provided, respectively. In block S13 the mean relative signal perception level s(L) is calculated based on the graph 1-1 ; 1-2, the network attenuation matrix A, and the relative importance coefficients L.

In block S 14 the lengths of the edges are determined, e.g. from the graph 1-1; 1-2. In block SI 5 characteristic attenuation lengths R are defined.

In block SI 6 sensor positions 4-1 - 4-n are defined at predefined mandatory vertices 2-1 - 2-10 and/or edges 3-1 - 3-9.

In block SI 7 all vertices 2-1 - 2-10 are excluded from the pool of vertices 2-1 - 2-10 where sensor positions 4-1 -4-n can be defined if they are within the predefined distance r from already defined sensor positions 4-1 - 4-n.

In block SI 8 a sensor position 4-1 - 4-n is defined at a vertex 2-1 - 2-10 which has the maximum value S(L). This vertex 2-1 - 2-10 is then removed from the list of available vertices 2-1 - 2-10. Therefore, in the next iteration the vertex 2-1 - 2-10 with the second highest value for S(L) is the vertex 2-1 - 2-10 which has the maximum value S(L).

If in block S 19 all available sensor positions 4-1 - 4-n are defined the method exits with block S20, where all sensor positions 4-1 - 4-n are stored and can e.g. be visually output to a user. If further sensor positions 4-1 - 4-n are available the method returns to block 18.

Fig. 4 shows a graph 1-2 which can be used with an embodiment of a method according to the present invention.

The graph comprises vertices 2-3 - 2-10 and edges 3-2 - 3-9. Further possible vertices and edges are indicated by three dots.

The vertices 2-3 - 2-10 in the graph 1-1 are depicted as squares which are connected by lines, i.e. the edges 3-2 - 3-9.

The vertex 2-3 is defined as a sensor position 4-2. Furthermore, the vertex 2-7 and the vertex 2-10 are chosen as sensor positions 4-3 and 4-4.

To demonstrate the embodiment in which a radius r is defined around a sensor position 4-2 - 4-4, wherein no further sensor may be positioned within that radius r, a circle with the radius r is drawn around vertex 2-7. This is just exemplary and a circle could as well be drawn around vertices 2-3 and 2-10.

It can be seen that no further sensor could be positioned e.g. at vertex 2-5 or vertex 2-6 because they both are within the radius r around vertex 2-7.

Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that a variety of alternate and/or equivalent implementations exist. It should be appreciated that the exemplary embodiment or exemplary embodiments are only examples, and are not intended to limit the scope, applicability, or configuration in any way. Rather, the foregoing summary and detailed description will provide those skilled in the art with a convenient road map for implementing at least one exemplary embodiment, it being understood that various changes may be made in the function and arrangement of elements described in an exemplary embodiment without departing from the scope as set forth in the appended claims and their legal equivalents. Generally, this application is intended to cover any adaptations or variations of the specific embodiments discussed herein.

Specific nomenclature used in the foregoing specification is used to provide a thorough understanding of the invention. However, it will be apparent to one skilled in the art in light of the specification provided herein that the specific details are not required in order to practice the invention. Thus, the foregoing descriptions of specific embodiments of the present invention are presented for purposes of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed; obviously many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated. Throughout the specification, the terms "including" and "in which" are used as the plain-English equivalents of the respective terms "comprising" and "wherein," respectively. Moreover, the terms "first," "second," and "third," etc., are used merely as labels, and are not intended to impose numerical requirements on or to establish a certain ranking of importance of their objects.