Алгоритмы выбора путей для подключения базовых станций беспроводной связи к центрам питания в шахте

Полный текст

Введение

Обеспечение энергоснабжения для многофункциональной системы безопасности и управления технологическими процессами (МСБ и УТП) на горнодобывающих предприятиях является необходимым условием их функционирования [1]. Требования к подобным системам содержатся в федеральных нормах и правилах [2] и госстандартах [3, 4]. Одним из подходов к их построению является использование единой подземной сети передачи данных. В свою очередь, ее работоспособность напрямую зависит от подачи электроэнергии и наличия резервных аккумуляторных источников питания. Как правило, в целях экономии оборудование систем безопасности и систем управления технологическими процессами зачастую имеют общие точки подключения к сети энергоснабжения.

На угольных шахтах используется однолинейная система распределения энергии. Поскольку на опасных производственных объектах должно проходить две независимых линии питания, на каждой шахте имеется две независимые энергоподстанции. К ним подключены различные комплексы горно-шахтного оборудования (комбайны, насосы, др.) и подземная осветительная сеть. От осветительной сети получает питание и оборудование МСБ и УТП.

Различные аспекты построения и анализа электротехнических и телекоммуникационных сетей в шахтах являются предметом интенсивных исследований [2–5]. Одним из используемых подходов к организации сети энергоснабжения является выстраивание её структуры иерархичным способом [6]. К автоматам осветительным шахтным (АОШ) подключают контроллеры питания (КП), которые преобразуют искроопасное переменное напряжение 127 В в искробезопасное постоянное напряжение 60 В для питания основных элементов системы – базовых станций (БС). Базовые станции, в свою очередь, обеспечивают беспроводную связь на территории шахты [7–11]. Для их подключения к КП используются многожильный кабель, который проходит через несколько БС и запитывает каждую БС через отдельную жилу. Каждый КП имеет ограниченные возможности для подключения БС, поэтому для подключения их всех необходимо использовать некоторое количество контроллеров.

Задача проектирования сети электроснабжения в шахте является комплексной и содержит ряд математических подзадач большой вычислительной сложности. Правила для построения сети энергоснабжения шахты изложены в [5]. В [12] изучается задача точного позиционирования шахтеров с помощью станций беспроводной связи и предложены рекомендации по расстановке таких станций. Не только задачи проектирования актуальны для шахт, также важной проблемой является нахождение оптимальных путей в уже существующих шахтах. В [13, 14] описана задача поиска оптимального пути для робота с помощью генетических алгоритмов (алгоритма муравьиной колонии, метода роя частиц). В [15] для построения пути робота также использованы алгоритмы решения задачи коммивояжера.

В данной статье рассматривается одна из таких подзадач в рамках описанного выше иерархичного подхода организации структуры сети. Предполагается, что в шахте уже размещены БС и АОШы, имеющие возможности для подключения к ним определённого числа КП. Таким образом, необходимо выбрать места для размещения КП и опередить, как по штрекам прокинуть многожильные кабели для подключения всех БС. При этом схема подключения, которая определяется из стоимости используемого кабеля, должна быть оптимальной по стоимости. В качестве параметров задачи выступает максимально возможное число подключаемых БС на одной линии (т. е. количество жил в кабеле) и максимально возможное число таких подключаемых кабелей к одному КП.

Ниже мы предлагаем несколько подходов к решению данной задачи. Большинство алгоритмов являются улучшенными версиями алгоритмов, ранее опубликованных в [11]. Также проводится численный анализ соответствующих алгоритмов на различных входных данных.  

Постановка задачи и подходы к её решению

Рассматриваемую прикладную задачу можно по-разному сформулировать математически. В [6] мы её сформулировали как задачу дискретной оптимизации на графе. В [11] приведена формулировка с использованием аппарата гиперсетей [16]. Ниже мы приводим именно эту формулировку. Отметим, что изложение задачи и методов её решения в терминах гиперсетей не является необходимым, и вполне можно обойтись и более простым аппаратом теории графов. Однако гиперсетевая формулировка является более наглядной, как показано ниже. Также это позволяет в компактной форме учитывать развитие и усложнение данной прикладной задачи, например, учёт надёжности и живучести проектируемых сетей, так как в явном виде будет информация о проходящих через каждый штрек линий связи. Аппарат гиперсетей позволяет также описывать и решать и другие задачи, связанные в том числе и с добычей и транспортировкой георесурсов [9, 17, 18].

Гиперсетью называется объект 𝐻𝑁=(𝑋, 𝑉, 𝑅, 𝐹), включающий в себя: 𝑋=(𝑥₁, 𝑥₂, ..., 𝑥_𝑛) – множество вершин; 𝑃𝑁=(𝑋, 𝑉) – граф первичной сети, где 𝑉=(𝑣₁, 𝑣₂, ..., 𝑣_𝑔) – множество рёбер (ветвей) первичной сети; 𝑊𝑁=(𝑋,𝑅 ) – граф вторичной сети, где 𝑅=(𝑟₁, 𝑟₂, ..., 𝑟_𝑚) – множество ребер вторичной сети; 𝐹: 𝑅→2^𝑉 – отображение, сопоставляющее каждый элемент 𝑟∈𝑅 и маршрут из ветвей в графе 𝑃𝑁; 𝑐(𝑣) – стоимость ветви 𝑣∈𝑉 первичной сети.

Стоимость ребер вторичной сети равна сумме стоимостей их ветвей.

Графы первичной и вторичной сетей являются не ориентированными.

На рис. 1 представлен пример первичной сети 𝑃𝑁 (графа выработок) в виде решетки и вторичной сети WN (графа линий связи в шахте) для описания топологий шахты и коммуникаций в ней. Зелёным цветом отмечены БС, красным – КП.

Постановка задачи:

Пусть задан граф первичной сети 𝑃𝑁=(𝑋, 𝑉), 𝐴⊆𝑋 – множество «возможных» начальных вершин для ребер (АОШ), 𝐵⊆𝑋 – множество вершин (БС), через которые должны пройти ребра вторичной сети, 𝐴∩𝐵=∅. Требуется построить вторичную сеть минимальной стоимости:

${\sum }_{r\in R}c\left(r\right)\to min$,

такую, что выполнены следующие ограничения;

1) число начальных вершин ребер 𝐴′:|𝐴′|≤𝐾_𝐴, где 𝐴′⊆𝐴 (ограничение на количество задействованных КП);

2) каждая вершина из 𝐴′ может быть началом ограниченного числа рёбер вторичной сети, по умолчанию этот параметр равен 2 (т. е. максимальное число многожильных кабелей, которые могут исходить из одного КП), однако предлагаемые алгоритмы работают и с другими его значениями;

3) в каждом ребре 𝑟 должно быть не больше 𝐾_𝐵 вершин из множества 𝐵.

 

Рис. 1. Пример гиперсети: граф выработок (слева) и граф линий связи в проложенных выработках (справа)

Fig. 1. Example of a hypernet: a graph of mine tunnels (left) and a graph of communication lines in a mine (right)

 

Рис. 2. Пример работы жадного алгоритма для случая, когда длины всех ветвей совпадают

Fig. 2. Example of the greedy algorithm result for the case, when the lengths of all branches are the same

 

На рис. 2 приведен пример, где множество «возможных» начальных вершин 𝐴={1, 8, 10}, ограничения 𝐾_𝐴=2, 𝐾_𝐵=3, в построенной гиперсети множество начальных вершин 𝐴′={1, 8}.

Без ограничения общности будем считать, что граф первичной сети 𝑃𝑆 является связным и поставленная задача является разрешимой.

В экспериментах ниже предполагается, что стоимость подключения пропорциональна длине прокладываемого кабеля, т. е. геометрическому расстоянию. В противном случае вместо матрицы расстояний может быть использована матрица стоимости подключения БС с номером i до АОШ с номером j без каких-либо изменений в предлагаемых алгоритмах.

В базовом варианте задачи предполагается, что КП уже размещены и требуется оптимальным образом прокинуть кабели от них для запитывания всех БС. Тогда 𝐴=A′. В общем же случае в дополнение этой задаче контроллеры питания также необходимо расставить по потенциальным местам размещения, т. е. АОШ.

Другой подход математического описания подобных прикладных задач – это их формулировка в терминах задачи коммивояжёра (Travelling salesman problem (TSP)), одной из классических задач теории графов [19, 20], которая является NP-трудной. Для задач коммивояжёра используются разные подходы: метод ветвей и границ, жадный алгоритм, биоинспирированные техники, метод имитации отжига [21] и другие, а также комбинации методов, что позволяет за приемлемое время получить решение с заданной погрешностью [22–24].

Рассматриваемая задача может быть сформулирована как задача нескольких коммивояжёров (Multiple TSP), к тому же незамкнутых, в условиях ряда ограничений. Во-первых, наличие нескольких «депо», когда коммивояжёры могут выезжать из одного или нескольких пунктов, такие задачи также изучаются (например, [23]). В нашем случае такие пункты – это набор КП. Во-вторых, ограничение на число пунктов в маршруте (но не на длину маршрута), то есть на количество жил в кабеле. В‑третьих, ограничение на число коммивояжеров, выезжающих из одного депо, то есть на количество кабелей, исходящих из одного КП. В-четвертых, мы также рассматриваем задачу оптимального размещения КП и прокладки кабелей от них к БС. В этом случае цель не только в оптимизации пути каждого коммивояжера в условиях ряда ограничений, но и в оптимизации размещения депо с ограничениями на их расположение, а также на количество депо, которые могут быть размещены в одном пункте, что соответствует возможному числу подключаемых КП к одному АОШ (то есть мощности АОШ). Подобных задач, описанных в литературе, нами найдено не было, поэтому предлагается ряд алгоритмов для их решения.

Алгоритмы основаны на известных подходах, модифицированных и адаптированных для учета указанной выше специфики. Одним из основных подходов для решения задач MTSP является жадный алгоритм, реализующий стратегию «иди в ближайший пункт». Другой популярный подход – метод имитации отжига, имитирующий соответствующий физический процесс [21].

Жадный алгоритм для нахождения путей подключения объектов к центрам питания

Жадный алгоритм основан на принципе «иди в ближайший пункт», далее будем обозначать его как 𝑁𝑒𝑎𝑟𝑒𝑠𝑡. Данный алгоритм можно использовать лишь в случае, когда |𝐴|=|𝐴′|, либо когда множество 𝐴′ заранее найдено и зафиксировано каким-либо образом. Модификация алгоритма для решения рассматриваемой задачи реализуется тремя шагами:

Шаг 1. Алгоритмом Флойда найти матрицу расстояний для множества вершин 𝐴’∪𝐵.

Шаг 2. Среди всех ребер (𝑎, 𝑏) 𝑎∈𝐴’, 𝑏∈𝐵 найти наименьшее и включить его в путь.

Шаг 3. Среди всех ребер, еще не включенных в пути (𝑥, 𝑥′), 𝑥, 𝑥′ ∈ 𝐴’∪𝐵 (причем вершина 𝑥 уже является крайней в каком либо пути, либо вершина 𝑥∈𝐴’, из которой еще выходил ни один путь) найти наименьшее (по стоимости) ребро и включить его в соответствующий путь. Повторить Шаг 3, пока все вершины не будут включены в какой-либо путь.

Пример работы алгоритма для случая, когда длины 𝑐(𝑣)=1 ∀𝑣, приведен на рис. 3. Зелёным цветом отмечены БС, красным – КП.

 

Рис. 3. Изменение путей в алгоритме имитации отжига в пунктах a–c шага 3

Fig. 3. Changing the paths in the simulated annealing algorithm in a–c points of the step 3

 

Очевидно, что в случае, когда все стоимости ребер равны, путь, найденный жадным алгоритмом, будет не более чем в два раза хуже оптимального. Отношение стоимостей найденного алгоритма и оптимального стремится к 2 при больших 𝑛: 𝑄=𝐶/𝐶𝑜𝑝𝑡=2.

В случае, когда стоимости ребер близки по значению друг к другу, можно использовать дополнительную балансировку. Для этого на Шаге 3 алгоритма 𝑁𝑒𝑎𝑟𝑒𝑠𝑡 при наличии нескольких наименьших ребер выбирается ребро, принадлежащее к самому короткому на данный момент пути. Далее эту вариацию алгоритма будем обозначать 𝑁𝑒𝑎𝑟𝑒𝑠𝑡+𝐵𝑎𝑙𝑎𝑛𝑐𝑒. Подобный подход ниже также используется и для других алгоритмов, что обозначено аналогичной пометкой в названии.

Часто число контроллеров питания и мест их размещения гораздо меньше, чем количество подключаемых БС. В этом случае можно перебрать все возможные варианты расположения контроллеров. Если же число комбинаций всё ещё велико, можно воспользоваться каким-либо приближённым алгоритмом направленного перебора. Далее для каждого варианта можно воспользоваться уже описанным жадным алгоритмом, обозначать этот алгоритм будем как 𝑃𝑒𝑟𝑒𝑏𝑜𝑟 𝑁𝑒𝑎𝑟𝑒𝑠𝑡 (т. е. перебираем подходящие комбинации множества 𝐴′ и для каждого варианта жадным алгоритмом 𝑁𝑒𝑎𝑟𝑒𝑠𝑡 находим решение).

Нахождение путей подключения объектов к центрам питания с использованием подхода имитации отжига

Метод имитации отжига для поставленной задачи предлагается реализовывать следующим алгоритмом:

Шаг 1. Алгоритмом Флойда найти матрицу расстояний для множества вершин 𝐴∪𝐵.

Шаг 2. Случайным образом сформировать пути (𝑎′_𝑖, 𝑏′₁, 𝑏′₂, ...), удовлетворяющие ограничениям. Задать некоторое начальное значение температуры 𝑇₀.

Шаг 3. Совершить одно из действий (рис. 4):

1. a) в случайно выбранном пути поменять местами две случайно выбранные его вершины;

б)  в случайно выбранных двух путях случайно выбранную вершину из одного пути перенести в другой, вставив ее случайным образом;

в)  случайный путь отцепить от первой вершины и присоединить к другой, ранее не использованной вершине из множества 𝐴.

Шаг 4. Если стоимость новой конфигурации путей меньше, чем изначальная, то принять изменения. Иначе, пусть 𝐷𝑖𝑠𝑡𝐷𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑐𝑒 – разница стоимостей конфигураций путей. Принять новые пути с вероятностью 𝑒𝑥𝑝(−𝐷𝑖𝑠𝑡𝐷𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑐𝑒/𝑡𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒). Уменьшить температуру: 𝑡𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒=𝑡𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒 * (1−𝑇′). Если 𝑡𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒>1, то перейти на Шаг 3.

В классической реализации алгоритма имитации отжига Шаг 3 состоит только из пункта (a). С учётом специфики рассматриваемой задачи были добавлены пункты (b) и (c). Этот алгоритм будем обозначать как 𝑂𝑡𝑧𝑖𝑔.

Также была рассмотрена вариация данного алгоритма, в которой Шаг 3 в пунктах (a), (с) производит разворот пути или части пути, т. е. выстраивает узлы в обратном порядке. Далее будем называть эту вариацию 𝑂𝑡𝑧𝑖𝑔𝑅𝑒𝑣𝑒𝑟𝑠𝑒.

Результаты численных экспериментов

Сравнение результатов работы алгоритмов проводилось на графе-решетке |𝑋|=100, стоимость ветвей – случайные числа от 1 до 10 условных единиц. Число вершин (БС), которые необходимо подключить к КП, отражено на оси абсцисс (|𝐵|) на рис. 4. На этом рисунке по оси ординат представлено среднее значение стоимости найденных путей для 50 запусков программы.

На рис. 4, a показан случай, когда |𝐴|=|𝐴′|=5. Видно, что для небольших значений |𝐵| лучший результат дает алгоритм 𝑂𝑡𝑧𝑖𝑔𝑅𝑒𝑣𝑒𝑟𝑠𝑒. Для больших значений |𝐵| лучший результат дает алгоритм 𝑁𝑒𝑎𝑟𝑒𝑠𝑡.

На рис. 4, b показан случай, когда |𝐴|=10 и |𝐴′|=5. В этом случае лучший результат дает алгоритм 𝑂𝑡𝑧𝑖𝑔𝑅𝑒𝑣𝑒𝑟𝑠𝑒.

На рис. 5 слева показаны результаты работы алгоритма 𝑁𝑒𝑎𝑟𝑒𝑠𝑡 с добавлением балансировки (𝐵𝑎𝑙𝑎𝑛𝑐𝑒) в условиях |𝐴|=|𝐴′|=5. То есть при наличии нескольких наименьших ребер выбирается ребро, принадлежащее к самому короткому на данный момент пути.

На рис. 5 справа показаны результаты работы жадного алгоритма с переборным алгоритмом (𝑃𝑒𝑟𝑒𝑏𝑜𝑟 𝑁𝑒𝑎𝑟𝑒𝑠𝑡). В этом случае можно использовать алгоритм Nearest. Алгоритм 𝑃𝑒𝑟𝑒𝑏𝑜𝑟 𝑁𝑒𝑎𝑟𝑒𝑠𝑡 показывает лучшие результаты при больших |𝐵|. Данный алгоритм целесообразно использовать при небольших значениях |𝐴| и |𝐴′|.

 

Рис. 4. Сравнение результатов работы алгоритмов при условии, что стоимости ветвей – случайные числа от 1 до 10 для |𝐴|=|𝐴′|=5 (a) и |𝐴|=10, |𝐴′|=5 (b)

Fig. 4. Comparison of the results of the algorithms under assumption that the cost of the branches are random numbers from 1 to 10 for |𝐴|=|𝐴′|=5 (a) and |𝐴|=10, |𝐴′|=5 (a)

 

Рис. 5. Сравнение результатов работы алгоритмов с использованием балансировки и перебора для |𝐴|=|𝐴′|=5 (слева) и |𝐴|=10, |𝐴′|=5 (справа)

Fig. 5. Comparison of the results of the algorithms using balancing and enumeration for |𝐴|=|𝐴′|=5 (left) and |𝐴|=10, |𝐴′|=5 (right)

 

Также были проведены численные эксперименты на структуре шахты, приведённой на рис. 6. Требуется разместить 38 БС, из каждого КП может выходить 2 многожильных провода. Стоимость равна геометрическому расстоянию.

В первом случае (рис. 6, слева) полагается, что уже размещены 2 КП, т. е. |𝐴|=|𝐴′|=2 и 𝐾_𝐵=10, т. е. в кабеле 10 жил. Решение, найденное алгоритмом 𝑁𝑒𝑎𝑟𝑒𝑠𝑡, имеет стоимость 104,9 условных единиц, алгоритмом 𝑂𝑡𝑧𝑖𝑔 – 102, 𝑂𝑡𝑧𝑖𝑔𝑅𝑒𝑣𝑒𝑟𝑠𝑒 – 97,1.  Цветными линиями показаны пути, найденные лучшим алгоритмом (𝑂𝑡𝑧𝑖𝑔𝑅𝑒𝑣𝑒𝑟𝑠𝑒). Как видно из рисунка, обратный метод отжига, в силу того что он является эвристическим, нашел не самые оптимальные пути: синий путь заканчивается вершинами {..,6,23,24}, хотя эффективнее было бы пройти вершины в другом порядке {..,6,24,23}. Это произошло из-за того, что алгоритм имитации отжига всё-так является приближенным алгоритмом.

 

Таблица. Стоимости путей, найденные разными алгоритмами для |𝐴|=3, |𝐴′|=2

Table. Path costs found by various algorithms for |𝐴| = 3, |𝐴′| = 2

Алгоритм/Algorithm	Стоимость/Cost
	(KB=10)	(KB=15)	(KB=20)
Otzig	101,4	101,8	101,7
OtzigReverse	98,4	100,8	98
PereborNearest	104,9	96,7	96,7
PereborNearest+Balance	103,1	95,9	93,6

 

Рис. 6. Лучшие из найденных маршрутов прокладки кабелей при разных условиях: 2 КП, 𝐾_𝐵=10 (слева) и 2 КП в 3 возможных АОШ, 𝐾_𝐵=15 (справа)

Fig. 6. The best of the found cable laying routes under different conditions: 2 PСs, 𝐾_𝐵=10 (left) and 2 PСs in 3 possible locations, 𝐾_𝐵=15 (right)

 

Во втором случае (рис. 6, справа) полагается, что имеется три АОШ для размещения 2 КП, т. е. |𝐴|=3, |𝐴′|=2. Рассматривались три варианта, когда 𝐾_𝐵=10 (в кабеле 10 жил), а также 15 и 20. Из КП может также выходить два провода. В таблице приведены результаты работы разных алгоритмов для данного графа. Цветными линиями показаны пути, найденные для пятнадцатижильного провода лучшим методом (𝑃𝑒𝑟𝑒𝑏𝑜𝑟 𝑁𝑒𝑎𝑟𝑒𝑠𝑡 𝐵a𝑙𝑎𝑛𝑐𝑒), со стоимостью 95,9. Отметим также, что для разных значения 𝐾_𝐵 оптимальные решения даются разными алгоритмами.

Заключение

Для задачи поиска путей минимальной стоимости для подключения базовых станций беспроводной связи к источникам питания в шахте многожильными кабелями предложено и протестировано несколько приближённых методов. Количество жил является параметром задачи, предполагается также, что из источника питания может исходить два таких кабеля. Кроме того, рассмотренная математическая постановка при введении дополнительных ограничений может быть полезной при решении других прикладных задач.

Об авторах

Денис Александрович Мигов

Институт вычислительной математики и математической геофизики СО РАН

Автор, ответственный за переписку.
Email: mdinka@rav.sscc.ru
ORCID iD: 0000-0003-3386-4641

кандидат физико-математических наук, старший научный сотрудник 

Россия, Новосибирск

Анастасия Николаевна Юргенсон

Институт вычислительной математики и математической геофизики СО РАН

Email: nastya@rav.sscc.ru
ORCID iD: 0009-0009-3743-1393

кандидат физико-математических наук, научный сотрудник 

Россия, Новосибирск

Список литературы

Дополнительные файлы