Выберу задачу: оптимальное размещение беспроводных антенн в помещении (Wi‑Fi / базовые станции). Кратко опишу геометрическую модель, формулировку и способы решения.
Геометрическая модель и физика сигнала
- Область обслуживания — компактное множество $D\subset {\mathbb{R}}^2$ (план этажа) с возможными препятствиями (стены) задаваемыми как подмножества, влияющие на затухание.
- Антенны расположены в точках $a_i\in D$, $i=1\dots k$. Передаваемая мощность $P_{t_i}$ считается заданной или оптимизируемой.
- Модель затухания на расстоянии (популярная лог‑нормальная / логарифмическая):
$$PL(d)=P{L}_0+10\alpha {\log }_{10}\frac{d}{d_0}+X_{\sigma },$$ где $\alpha$ — показатель затухания, $X_{\sigma }$ — случайная компонента (можно усреднить). При отсутствии multipath модель упрощается до зависимости от евклидова расстояния.
- Приёмная мощность в точке $x$ от антенны $i$:
$$P_{r,i}(x)=P_{t_i}-PL(\Vert x-a_i\Vert ).$$ Совокупная полезная мощность (приём от сильнейшей станции):
$$P_r(x)=\underset{i}{\max }{P}_{r,i}(x).$$
Цели оптимизации (варианты)
1. Максимизировать долю покрытой площади выше порога $P_{\min }$: максимизировать меру множества $\{x\in D:P_r(x)\ge P_{\min }\}$.
2. Максимизировать минимальную приёмную мощность (робастность):
$$\underset{a_1,\dots ,a_k}{\max }\underset{x\in D}{\min }{P}_r(x).$$ 3. Минимизировать число антенн $k$, чтобы обеспечить полное покрытие: найти минимальный $k$ и позиции $a_i$ такие, что $D\subset \{x:P_r(x)\ge P_{\min }\}$.
4. Минимизировать суммарную передаваемую мощность при заданных требованиях по SINR (добавляет интерференцию и шум).
Дискретизация для численной постановки
- Разбить $D$ на конечную сетку точек $\{x_j{\}}_{j=1}^N$. Тогда цель 2 записывается как
$$\underset{a_i}{\max }\underset{j}{\min }\underset{i}{\max }{P}_{t_i}-PL(\Vert x_j-a_i\Vert ).$$ - Для задачи покрытия с фиксированным радиусом $r_i$ (из условия $P_{t_i}-PL(r_i)=P_{\min }$) задача сводится к классической задаче покрытия множества дисками: найти положения центров $a_i$ так, чтобы ${\bigcup }_{i}B(a_i,r_i)\supset D$.
Связь с известными задачами геометрии и оптимизации
- Задача 2 близка к проблеме минимакс (minimax) размещения и к проблеме наилучшего покрытия/фермации; приближенно решается через картографирование на k‑means / centroidal Voronoi tessellation (приближение средней ошибки расстояния).
- Задача покрытия — дисковое покрытие (NP‑полная при дискретном выборе центров).
- При учёте интерференции и SINR — неконвексная задача с комбинацией позиционирования и распределения мощностей.
Способы решения
1. Градиентные локальные методы:
- Для дифференцируемого аппроксимированного функционала использовать замену $\max$ через smooth max (log‑sum‑exp):
$$\underset{i}{\max }{f}_i\approx \frac{1}{\beta }\log \sum _i{e}^{\beta f_i}.$$ Затем применять градиентный спуск / BFGS по координатам $a_i$. Подходит для задач максимизации средней или минимальной мощности (с несколькими стартами для выхода из локальных экстремумов).
2. Lloyd / k‑means (для минимизации средней квадратичной ошибки расстояния):
- Использовать итерации: построить Вороного разбиение по текущим $a_i$, перенести $a_i$ в центры масс своих ячеек; даёт хорошее приближение при оптимизации средней мощности (когда сигнал зависит монотонно от расстояния).
3. Комбинаторные и эвристические методы:
- Генетические алгоритмы, simulated annealing, particle swarm — для глобальной оптимизации позиций и мощностей при сложном ландшафте и препятствиях.
4. Дискретизация + MILP / SCP:
- Если допустимы лишь дискретные кандидатные позиции, задача покрытия превращается в задачу множества покрытий (set cover), которую можно решать жадным алгоритмом (оптимальная аппроксимация $\ln N$) или MILP‑решателем.
5. Оптимизация мощности при фиксированных позициях:
- При фиксированных позициях и линейной модели SINR задачи минимизации мощностей при ограничениях SINR часто приводят к выпуклым программам или решаются итеративными методами контроля мощности (Yates).
6. Учёт препятствий и многолучевости:
- Применить геометрический трейсинг лучей (ray tracing) или модель видимости (visibility polygons); в численной оптимизации включить взвешенное расстояние $d_w(x,a_i)$ вместо евклидова (штраф за прохождение через стены).
Рекомендованный практический план
1. Смоделировать помещение и препятствия; выбрать модель затухания.
2. Дискретизировать область $D$ в точки $x_j$.
3. Запустить два этапа: быстрый эвристический (Lloyd / k‑means + greedy покрытие) для начальной расстановки, затем локальную донастройку градиентным/эволюционным методом с учётом точной модели (ray tracing, интерференция).
4. Верифицировать результат симуляцией покрытия и, при необходимости, уточнить модель (учесть отражения, шум).
Краткая математическая сводка (основные формулы)
- Приём от ант. $i$: $P_{r,i}(x)=P_{t_i}-(P{L}_0+10\alpha {\log }_{10}\frac{\Vert x-a_i\Vert }{d_0}).$
- Совокупный уровень: $P_r(x)={\max }_i{P}_{r,i}(x).$
- Робастная цель: ${\max }_{a_1,\dots ,a_k}{\min }_{x\in D}{P}_r(x).$
- Покрытие по порогу: максимизировать $\mu \{x\in D:P_r(x)\ge P_{\min }\}$ или требовать $D\subset \{x:P_r(x)\ge P_{\min }\}.$
Если нужно, могу привести конкретную численную постановку (дискретизация, пример кода оптимизации, выбор параметров модели) для вашего типа помещения.