A General Framework for Sensor Placement in Source Localization

When an epidemic spreads in a given network of individuals or communities, can we detect its source using only the information provided by a small set of nodes? We propose a general framework that incorporates two dimensions. First, we can either rely exclusively on a set of selected nodes (i.e., sensors) which always reveal their state independently of any particular epidemic (these are called static), or we can add some sensors (called dynamic) as an epidemic spreads, depending on which additional information is required. Second, the method can either localizes the source after an epidemic has spread through the entire network (offline), or while the epidemic is ongoing (online). We empirically study the performance of offline and online localization both with and without dynamic sensors. Our analysis shows that, by using dynamic sensors, the number of sensors necessary to localize the source is reduced by up to a factor of 10 and that, even with high-variance transmission delays, the source can be localized by using fewer than 5% of the nodes as sensors.

Localizing the Source of an Epidemic Using Few Observations

Brunella Marta Spinelli

Localizing the source of an epidemic is a crucial task in many contexts, including the detection of malicious users in social networks and the identification of patient zeros of disease outbreaks. The difficulty of this task lies in the strict limitations on the data available: In most cases, when an epidemic spreads, only few individuals, who we will call sensors, provide information about their state. Furthermore, as the spread of an epidemic usually depends on a large number of variables, accounting for all the possible spreading patterns that could explain the available data can easily result in prohibitive computational costs. Therefore, in the field of source localization, there are two central research directions: The design of practical and reliable algorithms for localizing the source despite the limited data, and the optimization of data collection, i.e., the identification of the most informative sensors. In this dissertation we contribute to both these directions. We consider network epidemics starting from an unknown source. The only information available is provided by a set of sensor nodes that reveal if and when they become infected. We study how many sensors are needed to guarantee the identification of the source. A set of sensors that guarantees the identification of the source is called a double resolving set (DRS); the minimum size of a DRS is called the double metric dimension (DMD). Computing the DMD is, in general, hard, hence estimating it with bounds is desirable. We focus on G(N,p) random networks for which we derive tight bounds for the DMD. We show that the DMD is a non-monotonic function of the parameter p, hence there are critical parameter ranges in which source localization is particularly difficult. Again building on the relationship between source localization and DRSs, we move to optimizing the choice of a fixed number K of sensors. First, we look at the case of trees where the uniqueness of paths makes the problem simpler. For this case, we design polynomial time algorithms for selecting K sensors that optimize certain metrics of interest. Next, turning to general networks, we show that the optimal sensor set depends on the distribution of the time it takes for an infected node u to infect a non-infected neighbor v, which we call the transmission delay from u to v. We consider both a low- and a high-variance regime for the transmission delays. We design algorithms for sensor placement in both cases, and we show that they yield an improvement of up to 50% over state-of-the-art methods. Finally, we propose a framework for source localization where some sensors (called dynamic sensors) can be added while the epidemic spreads and the localization progresses. We design an algorithm for joint source localization and dynamic sensor placement; This algorithm can handle two regimes: offline localization, where we localize the source after the epidemic spread, and online localization, where we localize the source while the epidemic is ongoing. We conduct an empirical study of offline and online localization and show that, by using dynamic sensors, the number of sensors we need to localize the source is up to 10 times less with respect to a strategy where all sensors are deployed a priori. We also study the resistance of our methods to high-variance transmission delays and show that, even in this setting, using dynamic sensors, the source can be localized with less than 5% of the nodes being sensors.

EPFL2018

Back to the Source: an Online Approach for Sensor Placement and Source Localization

Laura Elisa Celis, Brunella Marta Spinelli, Patrick Thiran

Source localization, the act of finding the originator of a disease or rumor in a network, has become an important problem in sociology and epidemiology. The localization is done using the infection state and time of infection of a few designated sensor nodes; however, maintaining sensors can be very costly in practice. We propose the first online approach to source localization: We deploy a priori only a small number of sensors (which reveal if they are reached by an infection) and then iteratively choose the best location to place new sensors in order to localize the source. This approach allows for source localization with a very small number of sensors; moreover, the source can be found while the epidemic is still ongoing. Our method applies to a general network topology and performs well even with random transmission delays.

2017

Contribution à l'étude des modes de rayonnement acoustique d'une structure

Olivier Schevin

Noise radiated by different industrial structures that surround us in daily life are more and more considered as environmental pollution. Standards defining a tolerable sound level for each of these noise sources are regularly called into question and respecting them becomes an additional constraint for manufacturers. The last decades have seen the increasing development of means used to fight these noise disturbances. The wide diversity of noises perceived as harmful has contributed to the progressive increase in specificity and efficiency of solutions proposed to reduce the disturbances. For some applications, passive solutions, based on the use of materials capable of absorbing or deviating acoustic or vibratory waves, have progressively been replaced by "active" solutions, based on the generation of an acoustic wave of opposite phase to the disturbing one radiated by the noise source. Power transformers are sources for which passive solutions (anti-noise walls) are usually expensive and not very efficient, particularly at low frequency. Furthermore, characteristics of noise radiated by transformers (low frequency tone noise) are such that they are particularly well suited for the implementation of an active solution. Typically, an active control system dedicated to transformers (feedforward) is composed of actuators, used to generate the anti-noise and usually located near the tank, sensors, used to measure the attenuation obtained and to provide a reference signal, and a controller used to drive the actuators as a function of the information collected by the sensors. When the sensors are microphones, they are usually moved away from the noise source, in such a way that they pick up acoustic pressure that is representative of the noise propagated far away. In the vicinity of the source, local acoustic phenomena can occur which are not propagated far away. A microphone located near the noise source would therefore pick up an acoustic pressure that did not necessarily represent the one that effectively exists far away, the area where we are in fact seeking to reduce the noise. These phenomena, frequently grouped under the term "nearfield" tend to decrease the performance of the control system, owing to the fact that the controller seeks in this case to reduce an acoustic pressure which is not representative of the noise to be reduced. In practice, the significant amount of wiring required as a result of the positioning of the microphones in the far field, has a non-negligible effect on the cost of the system. The possibility of bringing the sensors closer to the source is sufficiently advantageous to envisage to studying the feasibility and the resulting consequences. The present approach consists in representing the primary field radiated by a vibrating structure in terms of a set of "acoustic radiation modes". The use of radiation modes to characterise the behaviour of a structure has received increasing attention since the beginning of 90's, especially for active control applications. Usually, this approach consists in representing the radiated power in terms of a set of surface velocity distributions, called radiation modes, that have the property of radiating independently of each other. Radiation modes result from diagonalization of a discrete expression of the radiation operator. We propose here to study the consequences on the radiation modes of a structure from bringing the microphones closer to it. We will study how the acoustic field varies with the distance and how this can be used to obtain a model, the complexity of which is adapted to the observation distance.