Сочинение на тему Модель диспетчеризации математических задач в сетях акторов беспроводных датчиков

В этой статье мы предлагаем математическую модель диспетчеризации задач, чтобы сократить общее время выполнения задач, т. е. время выполнения, в сетях акторов беспроводных датчиков. Мы формулируем распределение задач как задачу смешанного целочисленного нелинейного программирования (MINLP) с целью минимизации времени завершения задач, которые были распределены между участниками, но еще не были отправлены субъектам для выполнения в сетях. Предложенный подход рассчитывает оптимизированную скорость диспетчеризации задач, которые приводят к минимальному циклу обработки. Показано, что эта скорость диспетчеризации также может увеличить время жизни сети. Экспериментальные результаты с моделированием прототипа предложенного подхода показывают более короткий рабочий диапазон и более длительное время жизни сети по сравнению с тем, когда один из трех известных алгоритмов распределения задач, а именно, минимальное-минимальное, оппортунистическое распределение нагрузки (OLB) и стохастические алгоритмы распределения, используется.

<Р> 1. Введение

Группа беспроводных коммуникативных сенсорных узлов и акторных узлов, которые соответственно собирают информацию об окружающей среде и ведут себя в ответ на сенсорную информацию, создают отдельный тип беспроводной сети, называемой беспроводными сенсорными актерными сетями (WSAN). Составные части WSAN могут быть настроены по-разному в соответствии с требованиями приложений и существующих технологий. В этой статье мы рассматриваем только WSAN с полуавтоматической архитектурой, в которой все сенсорные узлы передают свою сенсорную информацию одному узлу в сети, который называется сетевой приемник. Этот одноэлементный узел является более мощным, чем сенсорные узлы и узлы актеров, и он отвечает за получение сенсорной информации и определение соответствующих задач (действий), которые должны быть выполнены актерами.

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

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

Мин-мин, оппортунистическая балансировка нагрузки (OLB) и стохастическое распределение – три популярных примера алгоритмов распределения задач, которые обычно используются в распределенных системах, таких как WSAN. Балансировка нагрузки – главная цель OLB, которая достигается за счет того, что все участники максимально заняты. Этот алгоритм планирует задачи на основе минимального предполагаемого времени выполнения задач в произвольном порядке. Алгоритм min-min учитывает приблизительное время выполнения и завершения всех задач на каждом действующем субъекте и только затем периодически назначает задачу с наименьшим временем завершения действующему субъекту с минимальным временем выполнения. Алгоритм стохастического распределения очень прост и стохастически распределяет задачи по доступным ресурсам (субъектам). Этот алгоритм не учитывает привязку, такую ​​как время выполнения задач и текущее состояние ресурсов (бездействующий / занятый). Основным преимуществом этого алгоритма является его простота и может быть реализован очень быстро.

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

<Р> 2. Связанные работы

<Р> М. Шарифи и др. представили подход, учитывающий энергию и время, для назначения задач участникам WSAN. Они выясняют способность актеров выполнять задачи и используют эту информацию для назначения задач актерам таким образом, чтобы уменьшить объем задач. Они сообщили о 45% улучшении разметки сети по сравнению с использованием алгоритма OLB. Их подход обеспечивает подходящий компромисс между временем выполнения всех задач и сбалансированной нагрузкой на участников, но игнорирует ограничение размера буферов участников.

Farias et al. предложил алгоритм планирования задач для WSAN, чтобы повысить энергоэффективность и, таким образом, увеличить время жизни сети. Чтобы достичь этой цели, их алгоритм пытается использовать характеристики приложений с общими задачами и избежать ненужного повторения задач. Тем не менее, их подход может увеличить общую оставшуюся энергию исполнительных механизмов, но ни их допуск, ни надежность услуг не учитывались в их алгоритме.

Шу и соавт. представил алгоритм планирования с учетом энергопотребления, чтобы максимизировать время жизни сети, обеспечивая при этом строгие гарантии обнаружения в WSN. Чтобы проверить свой алгоритм, они выполнили углубленную оценку его производительности с помощью крупномасштабного моделирования и сообщили о среднем увеличении срока службы сети на 39,2% по сравнению с базовым методом. Основным недостатком их алгоритма является то, что в их работе не учитывались ни надежность служб, ни сроки выполнения приложений.

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

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

Бьюн и Со предложили эпидемиологический алгоритм для распространения данных в WSAN, который учитывает требования к задержке и пытается снизить потребление энергии. Они использовали математический анализ для прогнозирования и поддержки требуемой производительности приложения. Их подход контролирует уровень инфекционности, что приводит к адаптивному количеству активных / спящих узлов. Они утверждали, что их подход может снизить потребление энергии при достижении требований задержки приложения.

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

<Р> 3. Предположения

Мы рассмотрели полуавтоматический WSAN с одним приемником сети и m субъектами Aj (j = 1,…, m), которые должны выполнять n задач Ti (i = 1, …, n). В такой сети расписание для каждой задачи – это выделение одного или нескольких временных интервалов одному или нескольким участникам. Эта проблема планирования известна как NP-полная проблема. В этой статье цель нашего подхода определена, чтобы уменьшить время выполнения задач, назначенных каждому действующему субъекту, чтобы минимизировать время выполнения. Эта цель достигается путем расчета возможностей каждого действующего лица во время назначения задач, таких как его текущая нагрузка и скорость выполнения задач.

Мы также предположили, что задачи независимы, и датчики передают свои собранные данные из физической среды в приемник. Раковина вычисляет соответствующие действия (задачи) и затем отправляет их действующим лицам. Задачи не являются приоритетными, и процесс их генерации следует распределению Пуассона.

<Р> 4. Предлагаемый подход

Мы вычисляем время выполнения как сумму времени выполнения выделенных задач для актеров. Каждый из акторов моделируется системой массового обслуживания M / M / 1 / K, в которой задачи поступают актеру Ai со скоростью λi и выполняются со скоростью µi. Чтобы уменьшить время выполнения, мы должны правильно настроить скорость выполнения задач для актера. Поскольку мы предполагали, что очередь каждого субъекта имеет ограниченную емкость K, система достигнет стационарного состояния, и, следовательно, нет необходимости рассматривать отношение λ <µ, которое необходимо учитывать, если очереди предполагали быть безграничными. < / р>

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

Предполагается, что скорость генерации задач (λ) следует пуассоновскому процессу, и на основе расщепляющего распределения Пуассона распределенные акторы получают задачи со скоростью λi. Это показано соотношением (4.1) для n актеров:

<Р> (4.1)

Поскольку основной целью представленного подхода является минимизация времени выполнения задач, которые должны выполнять субъекты, скорость распределения задач для каждого субъекта должна быть оценена соответствующим образом. Фактически, наш подход направлен на то, чтобы найти наилучшую скорость диспетчеризации λi (i = 1 – n), чтобы минимизировать время завершения задач, ожидающих выполнения участниками. Таким образом, каждый субъект моделируется как очередь M / M / 1 / k, в которой интервал времени между распределениями двух последовательных задач, а также время обслуживания является экспоненциальным процессом. На рисунке 2 показана модель актора Ai с непрерывной временной цепью Маркова (CTMC) в виде очереди M / M / 1 / K. Каждый эллипс обозначает состояние актера Ai, а число внутри каждого эллипса показывает количество существующих задач в очереди актера Ai.

Чтобы получить устойчивый анализ состояния CTMC, показанного на рисунке 2, мы используем следующие соотношения, где πi обозначает вероятность устойчивого состояния существующих задач в состоянии i. В этих отношениях λi обозначает скорость поступления задач в состояние i, а µi – уровень обслуживания субъекта Ai. В таблице 1 приведены обозначения, которые мы использовали при определении соотношений (4.2) – (4.19).

λi¬ .π0 = µi.π1

π1 (λi¬ + µi) = λi¬ .π0 + µi.π2

π2 (λi¬ + µi) = λi¬ .π1 + µi.π3 (4.2)

<Р>.
<Р>.
<Р>.
<Р>

λi¬ .πk-1 = µi.πk

Таблица 1. Обозначения, используемые в отношениях

Определение термина Определение термина