научная статья по теме АЛГОРИТМЫ ФОРМИРОВАНИЯ РЕКОМЕНДАЦИЙ ПРИ ПЛАНИРОВАНИИ ИНФОРМАЦИОННОГО ОБМЕНА ПО КАНАЛУ С ЦЕНТРАЛИЗОВАННЫМ УПРАВЛЕНИЕМ Кибернетика

Текст научной статьи на тему «АЛГОРИТМЫ ФОРМИРОВАНИЯ РЕКОМЕНДАЦИЙ ПРИ ПЛАНИРОВАНИИ ИНФОРМАЦИОННОГО ОБМЕНА ПО КАНАЛУ С ЦЕНТРАЛИЗОВАННЫМ УПРАВЛЕНИЕМ»

цепочка работ резерв

подцикл

Рис. 1. Фрагмент расписания информационного обмена.

0 Т 2 * Т 3 * Т

Рис. 2. Директивные интервалы работ сообщения.

жет повторить те работы из цепочки, выполнение которых было неуспешным, например из-за помех в канале. Интервал времени [к*ЬС; (к + 1)*ХЖС). называется подциклом с номером к (к = 0, 1, ...), а значение - длиной подцикла. В некоторых подциклах может не присутствовать ни одной цепочки работ.

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

1.2. Требования к информационному обмену по каналу. Для современных ВСРВ характерна циклическая организация вычислительного процесса, при которой абонент канала на каждой итерации своего цикла подготавливает порцию выходных данных для передачи по каналу в виде одного или нескольких сообщений [5]. Типичной рабочей нагрузкой для канала является набор сообщений, предназначенных для периодической передачи; для каждого сообщения задана длительность и требуемая частота передачи. Конкретные значения данных, транслируемые по каналу при очередной передаче сообщения, определяются в процессе функционирования ВСРВ.

Специфика архитектуры конкретной ВСРВ задает набор технологических ограничений на расписание обмена по каналу. Далее будем рассматривать следующий их набор, применяемый в реальной ВСРВ: 1) максимально допустимое число работ в цепочке (далее - длина цепочки работ); 2) максимально допустимая длительность цепочки работ (суммарное время выполнения работ из цепочки); 3) длина подцикла; 4) доля длины подцикла, зарезервированная для повторных обменов; 5) максимально допустимое отклонение расстояния между работами по передаче одного и того же сообщения от периода этого сообщения

(период - число, обратное частоте передачи сообщения).

На рис. 1 показан фрагмент расписания информационного обмена, включающий две цепочки работ. Работы одного и того же сообщения выделены одинаковой штриховкой. Набор сообщений и набор технологических ограничений на расписание в совокупности формируют набор требований к информационному обмену по каналу. Каждому требованию в составе такого набора соответствует числовая характеристика - значение требования. Например, значение требования "длина подцикла" может быть равно 1000 (тактов канала). Под изменением требования будем понимать изменение его значения. Некоторые требования могут принимать только целые значения (например, максимальная длина цепочки работ - положительные целые значения); другие требования - вещественные значения (например, зарезервированная доля длины подцикла - вещественные значения из диапазона [0; 1)).

1.3. Общая схема планирования информационного обмена по каналу с централизованным управление м. Перед построением расписания вычисляется длина Ь1гА интервала планирования, в течение которого расписание должно быть полностью отработано, и по завершении начата следующая итерация выполнения расписания. Как правило, Ьы полагается равной наименьшему общему кратному периодов сообщений. Каждому сообщению сопоставляется набор из Уь^/Т] работ по его передаче, где Т - период сообщения; 7-й работе, 1 = 1, ..., \_ЬтХ1Т\, соответствует директивный интервал [Т*(1 - 1); Т*1), в течение которого работа должна быть завершена.

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

1) расписание включает все работы всех сообщений;

2) каждая работа выполняется в пределах своего директивного интервала;

3) соблюдены все технологические ограничения на расписание.

2. Задача формирования рекомендаций по изменению требований к информационному обмену. 2.1. Формальная постановка задачи формирования рекомендаций. Пусть задан алгоритм планирования информационного обмена А и набор требований к информационному обмену (в том числе значения всех требований). Если алгоритм А не решает приведенную в

разд. 1.3 задачу построения расписания для данного набора требований, будем называть последний несовместимым относительно алгоритма А.

Если исходный набор требований к информационному обмену несовместим относительно применяемого алгоритма планирования, разработчику ВСРВ следует изменить значения некоторых требований из этого набора для обеспечения его совместимости. Возможность применения другого алгоритма планирования в работе не рассматривается; необходимо отметить, что выбор алгоритма планирования и настройка его на конкретный набор технологических ограничений является трудоемкой задачей [2]. Далее под изменением требования будем понимать изменение его значения - например увеличение максимальной длины цепочки работ.

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

Пусть некоторые требования в составе заданного набора допустимо изменять. Упорядочим требования так, чтобы вначале следовали эти требования (пронумеруем их от 1 до NR), а затем все остальные (пронумеруем их от NR + 1 до MAXR). Набором значений требований к информационному обмену будем называть вектор, элементами которого являются значения требований, и порядок следования элементов соответствует нумерации требований.

Введем функцию CompA(Y), определенную на множестве всевозможных наборов значений требований к информационному обмену и принимающую значения: 1 - если набор совместим относительно алгоритма A; 0 - в противном случае. Формальное представление требований к информационному обмену, необходимое для математически строгого задания функции CompA(Y), дано в [6]. Введем следующие обозначения:

R - требование с номером i;

initb ..., initMAXR - значения требований из исходного несовместимого набора;

limb limNR - значения, до которых допустимо изменять требования с номерами i = 1.NR (initi Ф limi, i = 1..NR);

INIT- вектор с элементами (init1, ..., initNR);

LIM - вектор с элементами (limb ..., limNR);

FIX - вектор с элементами (initNR+1, ..., initMAXR), содержащий значения требований, изменение которых недопустимо;

X = (хх, ..., xNR) - вектор текущих значений требований, значения которых можно изменять

(например, х1 может соответствовать максимально допустимой длине цепочки работ);

X < FIX - вектор с элементами (х1, ..., xNR, initNR + 1, ..., initMAXR); здесь "<" - операция конкатенации векторов;

INIT* = (INIT < FIX) = {initx, initMAXR) - вектор значений всех требований из исходного несовместимого набора;

LIM* = (LIM < FIX) = (lim1, ..., limNR, initNR + 1, ..., initMAXR) - вектор значений требований, в котором все требования, изменение которых допустимо, максимально изменены.

Задачу формирования рекомендаций по изменению несовместимого набора требований к информационному обмену будем рассматривать в следующей постановке.

Дано:

1) алгоритм A статического планирования информационного обмена;

2) несовместимый относительно A набор значений требований к информационному обмену INIT* : CompA (INIT*) = 0;

3) интервалы, в которых допустимо варьировать значения требований: [initi; lim], i = 1..NR;

4) номера тех требований, изменение которых допустимо и значения которых должны быть целочисленными: {ib ..., iNZ} (ik< NR, k = 1..NZ);

5) весовые коэффициенты, отражающие предпочтительность изменения требований: creli G R+, i = 1..NR.

Требуется: найти в допустимых диапазонах такие значения требований, при которых набор требований будет совместимым: CompA (X < FIX) = 1.

Минимизируемый критерий (целевая функция): суммарный "вес" изменений

Cost(X) = = crel* |(xi - initi)/(limi - initi)|.

Задача может быть представлена в форме задачи математического программирования [6]:

min Cost (X)

X G P

CompA(X < FIX) = 1

xt G Z, i G {ii, ..., z'nz}

xi G R, i G {1, ..., NR}\{i1,..., iNZ}, где P = [init1; lim1] X ... X [initNR ; limNR].

2.2. Анализ задачи формирования рекомендаций. Поставленная в разд. 2.1 задача относится к классу дискретно-непрерывных задач математического программирования с линейной целевой функцией. Примером дискретного оптимизируемого параметра может служить максимальная длина цепочки работ, а непрерывного параметра - доля длины подцикла, зарезервированная для повторных обменов.

Ограничение задачи X [ P является линейным, так как P представляет собой ^К-мерный параллелепипед. Ограничение CompA (X < FIX) = 1 (далее - ограничение совместимости) нелинейно. Автору не известно аналитическое представление функции CompA для эвристических алгоритмов A статического планирования информационного обмена по каналу с централизованным управлением (в том числе алгоритмам из [2]), учитывающее наборы технологических ограничений на обмен в реальных ВСРВ (например, набор из разд. 1.2). Следовательно, единственным доступным способом вычисления значения функции CompA(Y) в общем случае остается построение расписания по набору требований Y при помощи алгоритма A. В отдельных случаях для оценки сверху или снизу значения функции CompA могут быть использованы предложенные в [7] аналитические условия совместимости наборов требований для схемы с динамическим планированием обменов, которые расширяют условия, предложенные в [8].

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

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком