無線センサネットワークにおける最小露出経路問題への半ラグランジュ解法
A Semi-Lagrangian Approach for the Minimal Exposure Path Problem in Wireless Sensor Networks
無線センサネットワークの最小露出経路(MEP)を最適制御問題として定式化し、半ラグランジュ法で解くことで、様々なセンサモデルや障害物に対応しつつ最適解への収束を保証する手法を提案した。
著者: Armando Alves Neto, Víctor C. da Silva Campos, Douglas G. Macharet
分類: cs.RO, cs.SY, eess.SY
原文アブストラクト
A critical metric of the coverage quality in Wireless Sensor Networks (WSNs) is the Minimal Exposure Path (MEP), a path through the environment that least exposes an intruder to the sensor detecting nodes. Many approaches have been proposed in the last decades to solve this optimization problem, ranging from classic (grid-based and Voronoi-based) planners to genetic meta-heuristics. However, most of them are limited to specific sensing models and obstacle-free spaces. Still, none of them guarantee an optimal solution, and the state-of-the-art is expensive in terms of run-time. Therefore, in this paper, we propose a novel method that models the MEP as an Optimal Control problem and solves it by using a Semi-Lagrangian approach. This framework is shown to converge to the optimal MEP while also incorporates different homogeneous and heterogeneous sensor models and geometric constraints (obstacles). Experiments show that our method dominates the state-of-the-art, improving the results by approximately 10% with a relatively lower execution time.
