Streamlined security: Optimizing sensor placement with mathematics

Researchers have conducted many studies on sensor placement and utilized multiple techniques -- including graph-based approaches, computational geometry, and Bayesian methods -- to generate setups of varying success. But despite past efforts, this optimization problem remains complicated. In a paper published in the SIAM Journal on Scientific Computing, Sung Ha Kang, Seong Jun Kim, and Haomin Zhou propose a computational level set method to optimally position a sensor-based security system for maximum surveillance of a complex environment. "In optimal sensor positioning, the covered and non-covered regions can be accurately classified using the level set, and the dynamics of the coverage with respect to a sensor position can be derived and tracked conveniently," Kim said. "Over the years, the level set method has proven to be a robust numerical technique for this purpose."

The authors begin by identifying the ongoing challenges of effective sensor optimization, including high demand for computational resources. Obstacles obstructing sensor view and range are frequently of arbitrary shape, making their positions difficult to locate. Additionally, maximizing coverage area is a costly problem of infinite dimensions, and finding the global optimal solution often becomes computationally intractable. "Many previous works are solved by combinatorial approaches, while our setup is more continuous," Kang said. "This offers more flexibility in handling complicated regions and different configurations, such as limited viewing range and directions."

Kang, Kim, and Zhou combine and modify existing algorithms to yield more accurate sensory constraints from a practical viewpoint. While past studies have assumed that sensors have an infinite coverage range and/or a 360-degree viewing angle, the authors extend existing formulations to acknowledge the finite range, limited viewing angle, and nonzero failure rate of realistic sensors. "Sensors, regardless how well they are manufactured, can fail to acquire targeted information," Zhou said. "Modeling those constraints effectively is crucial when one wants to solve the practical sensor positioning problem. In general, those constraints make the problem harder to solve -- they naturally demand sophisticated computational algorithms."

Their model employs a level set formulation, a flexible conceptual framework often used in the numerical analysis of shapes and spaces. This mechanism offers a number of advantages. "Level sets conveniently represent the visible and invisible regions as well as obstacles of arbitrary shape, and handle topological changes in the regions automatically," Zhou said. "In addition, the extensive literature on level set methods provides solid theoretical foundation as well as abundant computation techniques when it comes to implementation." The authors solve a system of ordinary differential equations (ODEs), then convert the ODEs to stochastic differential equations via a global optimization strategy called intermittent diffusion. These steps yield the optimal viewing directions and locations of all the sensors, as well as the largest possible surveillance region -- the global optimum. "Without being limited to polygonal environments that are typically assumed in sensor positioning, like combinatorial approaches, our method can be applied to more general setups and approximate a globally optimal position due to the level set framework and intermittent diffusion," Kim said.

By acknowledging and accounting for finite range, limited viewing angle, and nonzero failure rate, Kang, Kim, and Zhou create a unique sensor optimization model. "To the best of our knowledge, viewing sensor placement problems from a probabilistic prospective in the level set framework is novel," Zhou said. "Yet there is room to further improve the computational complexity. We theoretically analyzed the basic situation in the paper, but more needs be done to better understand the probability issues related to the sensor positioning problem."

Nevertheless, the authors are pleased with the implications of their current computational method, which could improve surveillance at nearly a myriad of monitored areas, from neighborhood gas stations to mall parking lots. "We hope that our sensor positioning approaches can be a cornerstone to directly improve the performance of surveillance systems as well as the efficiency of allocated monitoring resources," Kim said.