Алгоритм поиска оптимального расположения сенсоров для решения задачи мониторинга пространства

Программные продукты и системы. 2016. № 3. С. 60–66.

Кочкаров А. А., Яцкин Д. В.

Рассмотрена задача мониторинга пространства, осуществляется переход к задаче обнаружения, а затем – к задаче геометрического расположения сенсоров. Предлагается использовать децентрализованную сеть сенсоров для решения поставленной задачи. Устанавливаются отграничения и допущения, приводящие к задаче покрытия пространства. Проводится дискретизация задачи, обосновывается ее необходимость. Задача подробно рассматривается с математической точки зрения, разрабатывается алгоритм ее решения, оценивается его сложность. Проводится математическое и программное моделирование задачи. Разрабатывается программный комплекс, реализующий указанный алгоритм. По заданной карте местности и параметрам среды, а также с использованием ряда начальных условий, определяющимися физическими характеристиками сенсоров, программный комплекс, позволяющий рассчитать точки пространства, при размещении в которых устройств – обнаружителей задача мониторинга будет считаться решенной. На данном программном комплексе произведен ряд испытаний, показавший работоспособность, корректность и оптимальность разработанных подходов и алгоритма. Благодаря невысокой полиномиальной вычислительной сложности алгоритма, программный комплекс может находить решение задачи мониторинга в частном конкретном случае для больших зон мониторинга с одной стороны и сотен устройств-обнаружителей – с другой.

Ключевые слова: мониторинг, monitoring, программный комплекс, software package, теория множеств, mobile robot, sensor, set theory, UAV, БПЛА, сенсор, detection, coverage algorithm, алгоритмы покрытия, покрытие пространства, space coverage, robotic network, group management, обнаружение, мобильный сенсор, сеть сенсоров, групповое управление