Optimal Sensor Placement Problems Under Uncertainty: Models and Applications
thesisposted on 2019-10-17, 14:41 authored by Todd ZhenTodd Zhen
The problem of optimally placing sensors can often be formulated as a facility location problem. In the literature of operations research, facility location problems are mathematical optimization problems where one or more facilities must be placed in relation to a given number of demand points or customers. Within the context of sensor placement, for example, this translates to placing wireless communication nodes that connect to a set of users or placing smoke detectors to adequately cover a region for safety assurances. However, while the classical facility location problem has been extensively studied, its direct applicability to and eﬀectiveness for the optimal sensor placement problem can be diminished when real-world uncertainties are considered. In addition, the physics of the underlying systems in optimal sensor placement problems can directly impact the eﬀectiveness of facility location formulations. Extensions to existing location formulations that are tailored for the system of interest are necessary to ensure optimal sensor network design.
This dissertation focuses on developing and applying problem-specific optimal sensor placement methods under uncertainty in sensor performance. With the classical discrete facility location problems as a basis, our models are formulated as mixed-integer linear and nonlinear programs that, depending on the specific application, can also be in the form of a stochastic program, a robust optimization framework, or require probability distributions for uncertain parameters. We consider optimal placement problems from three different areas, particularly the optimal placement of data concentrators in Smart Grid communications networks, the optimal placement of flame detectors within petrochemical facilities, and the optimal selection of infectious disease detection sites across a nation. For each application, we carefully consider the underlying physics of the system and the uncertainties and then develop extensions of previous sensor placement formulations that effectively handle these qualities. In addition, depending on the degree of nonlinear complexity of the problem, specific relaxations and iterative solution strategies are developed to improve the ability to find tractable solutions. All proposed models are implemented in Pyomo, a Python-based optimization modeling language, and solved with state-of-the-art optimization solvers, including IPOPT, Gurobi, and BARON for nonlinear, mixed-integer, and mixed-integer nonlinear programs, respectively. Numerical results show that our tailored formulations for the problems of interest are effective in handling uncertainties and provide valuable sensor placement design frameworks for their respective industries. Furthermore, our extensions for placement of sensors under probabilistic failure are appropriately general for application in other areas.