Двухкритериальный метод обеспечения ресурсосбережения в краевом и туманном слоях сети

Введение. В настоящее время широкое применение нашли приложения, использующие краевой и туманный сегменты сети [1–5]. Распределенные вычисления, выполняемые на узлах этих сегментов, имеют существенное отличие от распределенных вычислений, выполняемых в облачных структурах, а именно — относительно высокую динамику топологии и, помимо этого, наличие определенных расстояний между используемыми узлами. Это приводит к необходимости учета данного параметра при моделировании времени информационных обменов между исполняемыми задачами. Существование динамики топологии объясняется тем, что устройства края сети — это, как правило, пользовательские устройства (включая разного рода датчики, смартфоны, ноутбуки и т.д.), которые принадлежат определенным людям и могут быть перемещены, выключены, доступ к данным/ресурсам может быть запрещен. Все они при этом находятся в зависимости от наличия заряда батареи (источника питания) [6][7]. Туманный слой сети менее динамичен, однако и для него характерно все перечисленное в той или иной степени: наличие определенного расстояния между узлами с присутствием транзитных участков сети, возможная мобильность самих узлов. Например, в случае обработки данных группами мобильных устройств. Интересным примером в этом смысле являются группы низкоорбитальных спутников, которые к настоящему времени используются для обработки данных, но при этом узлы смещаются относительно поверхности Земли с достаточно высокой скоростью (время доступа — порядка нескольких минут) и, следовательно, возникает вопрос о маршрутизации и передаче результатов обработки на наземные станции [8].

В рамках вопросов ресурсосбережения используемых устройств в динамичных слоях сети был опубликован ряд работ [9–11], в которых внимание акцентируется на энергосбережении. Как правило, модель предполагает наличие зависимости потребляемой энергии устройства от его загруженности [12]. При этом вне фокуса исследований остался такой важный фактор как сбережение остаточного вычислительного ресурса устройства [13].

Остаточный вычислительный ресурс устройства — это величина, тесно связанная с такими надежностными характеристиками, как вероятность безотказной работы и гамма-процентная наработка на отказ. Также средний остаточный ресурс, с учетом использования экспоненциального закона распределения интенсивности отказов, характеризуется следующим выражением:

(1)

где P (x) — вероятность безотказной работы (ВБР) объекта в течение времени x .

Для экспоненциального закона распределения ресурса ВБР определяется как:

(2)

где — интенсивность отказов,  > 0 .

Тогда согласно формуле (1), средний остаточный ресурс определяется по следующей формуле:

(3)

При этом имеются работы, посвященные связи величин ВБР, гамма-процентной наработки на отказ и среднего остаточного ресурса от температуры вычислительного элемента устройства, которая, в свою очередь, описана как функция от загруженности устройства [14–16]. Задача ресурсосбережения устройства также может быть поставлена как задача максимизации среднего остаточного ресурса устройства.

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

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

• электроэнергия — восполняемый, но критичный для выполнения миссии устройства ресурс, будь то датчик информационно-управляющей системы или управляемое мобильное устройство;
• остаточный вычислительный ресурс определяет длительность целесообразной эксплуатации устройства, а время эксплуатации, соответственно, складывается из миссий, выполненных устройством.

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

Материалы и методы. Определим понятие «миссия группы устройств» как заранее определенную последовательность решения группой устройств комплекса вычислительных задач, связанных информационными обменами. Миссия группы устройств может быть описана ациклическим графом, вершины которого будут взвешены трудоемкостями задач, а дуги, соответственно, будут определять ограничения следования и объемы данных, передаваемых задачами. Пусть миссия описывается графом W = {wl , zl , I }, где wl — трудоемкость задачи, zl — доля задачи, выполненная к моменту смены топологий, I — матрица объемов данных, передаваемых между задачами. Группа устройств в динамическом слое сети описывается набором графов, каждый из которых определяет топологию сети в момент времени ti . Будем считать, что время выполнения миссии включает некоторый временной интервал с дискретными моментами времени [t0, t1, …tk], каждому из которых соответствует граф топологии Gi={, H}, j=1…m, pij — производительность j-го узла i-й топологии, eij — энергоресурс j-го узла i-й топологии, Rij — средний остаточный вычислительный ресурс j-го узла i-й топологии, m — число устройств в группе, H — матрица сетевых соединений между узлами. Также примем допущение о том, что в каждый последующий момент времени t_i+1 для графов G_i+1 и Gi справедливо следующее: по меньшей мере одна из вершин, принадлежащая Gi , будет содержаться в G_i+1, что необходимо для продолжения выполнения миссии.

Также будем считать, что обеспечивается, в случае изменения графа топологии в момент времени t_i+1, возможность переназначения задач, которые в i-й топологии выполнялись на узлах, переставших существовать в _i+1 момент времени, на любые из узлов топологии _i+1, имеющиеся в наличии. При этом сделаем допущение о том, что перенесенные на новые узлы задачи начинают выполняться на том же месте, где было прервано их исполнение.

Оценивание остаточного вычислительного ресурса будет реализовано следующим образом: для оценки ВБР устройства туманного слоя будем использовать выражения, предложенные в [17][18]:

(4)

где D — загрузка вычислителя (в долях).

(5)

где wi — трудоемкость выполняемой работы.

Соответственно может быть оценена ВБР (t), а также средний остаточный ресурс:

(6)

где t_constraint — ограничение по времени, за которое должна быть выполнена задача узлом, чтобы уложиться в ограничение по времени выполнения миссии t_m.

При оценивании остаточного энергетического ресурса также будем полагать, что расход энергии пропорционален загруженности вычислительного узла и больше энергетических затрат не имеется:

(7)

где Ej0 — исходный уровень энергии в наличии; Ejm — остаточный уровень; — коэффициент, выражающий зависимость между нагрузкой вычислительного элемента и его энергозатратами.

Результатом работы двухкритериального метода обеспечения ресурсосбережения будет последовательность распределений нерешенных еще задач миссии за время [t0, ti-1] по топологии Gi с учетом того, что часть задач, находящихся в процессе решения на узлах, наследуемых из топологии Gi-1, остаются на своих местах и не переносятся:  A = { A_i } ;

(8)

Матрица А описывает распределение нерешенных задач, для которых zl<1. При этом количество узлов соответствует новой топологии Gi. Узлы, унаследованные от топологии Gi-1, перенумеровываются и занимают индексы, начиная с 1. Поскольку выполнение миссии может включать более одной топологии, проведем декомпозицию задачи следующим образом: воспользуемся «жадной» стратегией и будем полагать, что удовлетворяющее решение (минимизация ресурсопотребления, оцениваемое двумя выбранными критериями) может быть получено, если для каждой топологии мы будем выбирать наилучшее решение.

Рассмотрим возможную приоритетность сформулированных целевых функций. Для каждой отдельно взятой топологии необходимо минимизировать как расход электроэнергии, так и расход вычислительного ресурса. В некоторых частных случаях может быть достигнуто совпадение целей оптимизации для двух критериев. Например, задача распределяется на узел таким образом, что обеспечит ему минимальную загруженность вычислительного элемента и при этом минимальный расход энергопотребления.

Однако, такая ситуация возможна не всегда. Например, имеется узел, загруженный менее прочих вычислениями, но при этом его энергоресурс практически исчерпан. Назначая на него задачу, мы ставим выполнение миссии под угрозу (либо необходима смена топологий по мере окончания запаса электроэнергии), а назначая задачу на узел более загруженный, мы ухудшаем значение критерия остаточного вычислительного ресурса. Противоположная ситуация также может иметь место: узел с большим остаточным энергоресурсом может иметь низкий остаточный вычислительный ресурс как результат участия в предыдущих миссиях устройств.

Поэтому целесообразно провести ранжирование целевой функции (ЦФ) по важности, на основе чего выбрать дальнейший метод решения.

Для миссий, критически важных к выполнению, ведущую роль играет ресурс батареи устройства [19–21]. Соответственно, ЦФ, определяющая остаточный вычислительный ресурс, может быть сведена к дополнительному ограничению. Невыполненные задачи миссии будут дораспределяться в зависимости от остаточного заряда батареи.

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

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

Результаты исследования. Многокритериальные задачи оптимизации, как правило, сводят к решению одной и более однокритериальных задач. В данном случае более целесообразно оставить одну ЦФ, а вторую представить в качестве ограничения.

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

Опишем основные этапы двухкритериального метода обеспечения ресурсосбережения, как основного результата проведенного исследования:

• на имеющейся Gi-топологии выбрать узлы, обладающие достаточным для завершения миссии без смены топологии энергоресурсом;
• произвести распределение задач миссии по выбранным узлам таким образом, чтобы для незанятых узлов, к которым будут прикреплены нерешенные еще задачи, минимизировать расход вычислительного ресурса.

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

Проиллюстрируем зависимость значений ВБР устройств от выбора узла для решения задачи (в данном эксперименте сравниваем состояния узлов при передаче поступающих данных и при их обработке). Топология представлена на рис. 1.

Эксперимент проводится для 10 временных отрезков, каждый из которых по 100 часов при следующих значениях параметров: Wreceive (объем получаемых задачей данных) — 500 ед., Wsend (объем отправляемых задачей данных) — 100 ед., Wprocess (трудоемкость обработки данных) — 150 ед., Tdecl (время, отводимое на решение задачи) — 50 ед.

Далее приведены графики ВБР-узлов в зависимости от того, обрабатывает ли узел данные или только передает их (рис. 2–5).

Далее на рис. 6 представлено сравнение различий в значениях среднего остаточного вычислительного ресурса.

Обсуждение и заключения. В статье предложен двухкритериальный метод обеспечения ресурсосбережения в краевом и туманном слоях сети, который отличается от ранее представленных в предметной области организации распределенных вычислений в динамических слоях сети тем, что учитывает одновременно состояние батареи устройства (что критично для выполнения миссии) и остаточный ресурс вычислительного устройства (что влияет на длительность целесообразного использования устройства за пределами выполняемой миссии).

В основу разработанного метода положена сформулированная задача двухкритериальной оптимизации, которую затем предлагается свести к однокритериальной, переведя ЦФ остатка энергоресурса в ограничение.

Отсекая узлы, заранее не подходящие по уровню заряда батареи, далее распределение задач происходит по критерию остаточного вычислительного ресурса.

Проведенный эксперимент позволяет сравнить результаты распределения задачи по узлам при наличии информационных взаимодействий между задачами. Наглядно показано, что способ распределения задач существенно влияет на величину остаточного ресурса вычислительного устройства (до 25 %). Таким образом, возможны улучшения показателей ресурсопотребления устройств, участвующих в вычислениях в краевом и туманном слоях сети.