В.А. Костенко, А.В. Плакунов - Алгоритм построения одноприборных расписаний, основанный на схеме муравьиных колоний (статья)

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2013, № 6, с. 87–96СИСТЕМНЫЙ АНАЛИЗИ ИССЛЕДОВАНИЕ ОПЕРАЦИЙУДК 517.977.5АЛГОРИТМ ПОСТРОЕНИЯ ОДНОПРИБОРНЫХ РАСПИСАНИЙ,ОСНОВАННЫЙ НА СХЕМЕ МУРАВЬИНЫХ КОЛОНИЙ© 2013 г. В. А. Костенко, А. В. ПлакуновМосква, МГУПоступила в редакцию 29.04.13 г., после доработки 26.06.13 г.Приведена математическая постановка задачи построения расписания обменов по каналу сцентрализованным управлением. Данная задача возникает при проектировании информационноуправляющих систем реального времени.

Проведен анализ возможных подходов к построению алгоритмов, основанных на схеме муравьиных колоний, и приведены результатыэкспериментального сравнения предложенного алгоритма с жадными алгоритмами.DOI: 10.7868/S0002338813060085Введение. В бортовых системах реального времени широко используется архитектура, основанная на каналах с централизованным управлением. Примерами каналов с централизованнымуправлением являются MIL STD1553B (МКИО ГОСТ Р520702003) [1], STANAG 3910 [2],FCAE1553 [3].Канал обеспечивает обмен данными между устройствами, присоединенными к каналу (далее –оконечные устройства).

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

В отличие от задач о выборе максимального числа совместимых заявок, рассматриваемых в теории расписаний, в задаче построения обменов по каналу с централизованнымуправлением накладываются дополнительные ограничения на корректность расписания, которые обусловлены особенностями программных и аппаратных средств бортовой системы [4–6].Основной проблемой при использовании алгоритмов, основанных на жадных стратегиях истратегиях ограниченного перебора, является их настройка на решение частных задач (наложены ограничения на возможные значения входных данных) [7, 8]. Это связано с проблемой формирования ограничений на исходные данные таким образом, чтобы “четко” выделить частнуюзадачу, для которой алгоритм будет гарантировано находить решение с приемлемой точностью исложностью. В большинстве случаев возможно получение лишь статистических оценок точностии сложности алгоритма.

Муравьиные алгоритмы [9, 10] позволяют автоматически настраиватьсяна пример задачи (заданы конкретные значения исходных данных) путем дополнительной разметки исходных данных, которая используется для построения решения на каждой итерации алгоритма и уточняется по мере увеличения числа итераций. Другими словами, при использовании муравьиных алгоритмов не возникает проблема “четкого” выделения частной задачи.Алгоритмы, основанные на использовании схемы муравьиных колоний, были успешноприменимы для решения таких комбинаторных задач, как квадратичная задача о назначениях[11], задача упаковки в контейнеры [12], задачи построения расписаний [13–15]. В данной работе предлагается алгоритм, основанный на использовании схемы муравьиных колоний, для решения задачи построения расписания обменов по каналу с централизованным управлением.В первом разделе данной работы рассматривается задача построения расписания обменов поканалу с централизованным управлением, во втором разделе приведена общая схема муравьиных алгоритмов и сформулированы задачи, которые надо решить при построении муравьиных8788КОСТЕНКО, ПЛАКУНОВСледующеесообщениеKCKCt1OCCДCД...CДt1OCt2KCaСледующеесообщениеKCKCt1OCCДCД...CДt2KCбРис.

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

Эти оконечные устройства лишь выполняют адресованные им команды контроллера.Обмен информацией осуществляется асинхронно путем поочередной передачи информации попринципу “команда–ответ”. Информация передается в виде сообщений, которые могут состоять из командных слов, слов данных и ответных слов.Рассмотрим пример работы шины в соответствии со стандартом MIL STD [1]. Стандарт допускает основные и групповые форматы сообщений. Форматы основных сообщений используются для передачи информации одному из оконечных устройств и предусматривают выдачу имответного слова.

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

Каждый формат определяет количество и порядокследования командных слов, ответных слов и слов данных. Ниже приведены примеры форматоводиночного (а) и группового (б) сообщений (рис. 1). Здесь КС – командное слово, ОС – ответноеслово, СД – слово данных, t1, t2 – паузы.Контроллер должен без паузы передать команду обмена данными с адресом оконечногоустройства А на прием данных и команду обмена данными с адресом оконечного устройства Б напередачу данных. Оконечное устройство Б после установления факта достоверности принятойкоманды должно передать без пауз ответное слово и указанное в команде количество слов данных. Оконечное устройство А после установления факта достоверности адресованной ему информации должно передать ответное слово.Контроллер должен передать без паузы групповую команду обмена данными на прием данных и команду обмена данными с адресом одного оконечного устройства на передачу данных.Это оконечное устройство после установления факта достоверности принятого командного слова должно передать без пауз ответное слово и указанное в команде количество слов данных.В качестве исходных данных для задачи построения расписания обменов задается множествопериодических сообщений SM = {M i = t i , ri } , где i = 1, n , ti – время передачи сообщения, ri – частота передачи сообщения.

Период передачи сообщения обозначим за τ i = 1 ri . Для каждого сообщения формируется множество соответствующих ему работ J i = { j = t j , s j , f j } , где j = 1, ni ,ni = ⎢⎡rscl τi ⎥⎤ – количество экземпляров сообщения, которые надо передать в интервале планирования, rscl – длительность интервала планирования, s j = ( j − 1) ⋅ τi ; f j = j ⋅ τi – соответственно левая и правая границы директивного интервала сообщения j. Для некоторых сообщений могутИЗВЕСТИЯ РАН.

ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ№62013АЛГОРИТМ ПОСТРОЕНИЯ ОДНОПРИБОРНЫХ РАСПИСАНИЙϕ1s1f1ϕ1s2f2ϕ1s389f3... t0ϕ2τiϕ22τiϕ23τiРис. 2. Директивные интервалы работбыть заданы левый и правый фазовые сдвиги, обозначаемые ϕ1 и ϕ2 соответственно, которыесужают директивный интервал сообщения, вычисляемый в зависимости от номера сообщения ипериода его передачи (рис. 2). Множество работ определяется как объединение множества работ соответствующих заданным сообщениямnJ =∪J .ii =1Шина может рассматриваться как одноприборное устройство, обслуживающее исходно заданNный набор работ J = { j} j =j1, которые должны выполняться без прерываний.

Для каждой работы заданы t j > 0 – время выполнения, [s j , f j ) – директивный интервал, и верно условие f j − s j ≥ t j .Расписание представляет собой упорядоченное по критерию момента старта работы множествоH = { j k , s *j }kN=k1, j ∈ J , где k – порядковый номер jй работы в расписании, Nk – количество работ,s *j – момент старта jй работы в расписании H, f j* = s *j + t j – момент завершения jй работы.Множество корректных расписаний H'* определим набором основных ограничений:g1: (∀j ∈ H ) ⇒ ((s *j ≥ s j ) ∧ ( f j* ≤ f j )),g 2: (∀j ∈ H ) ⇒ ( f j* − s *j = t j ),g 3: (∀( j, l ) ∈ H , j ≠ l ) ⇒ (((s *j < sl*) ∨ (s *j ≥ f l*)) ∧ (( f j* ≤ sl*) ∨ ( f j* > f l*))).Ограничения g1, g2, g3 являются обязательными для одноприборных расписаний без прерываний и соответственно означают:1) интервал выполнения каждой работы располагается в рамках ее директивного интервала;2) не допустимы прерывания;3) интервалы выполнения работ не пересекаются.Для расписания обменов по каналу с централизованным управлением присутствуют дополнительные к основным ограничения на корректность расписания, которые обусловлены особенностями аппаратных и программных средств конкретной системы реального времени.

Длясхемы организации обменов с подциклами (интервал планирования разбивается на отрезки равной длины – подциклы, см. рис. 3) возможны следующие дополнительные ограничения gi:4) в каждом подцикле может находиться не более одной цепочки работ и работы в цепочкеследуют друг за другом без пауз;5) время выполнения работ не должно пересекать границы подцикла;6) время начала цепочки работ относительно начала соответствующего подцикла не должнобыть меньше заданного значения;7) в конце подцикла должен быть зарезервирован интервал времени, длительность которогоне меньше, чем заданная доля длительности подцикла;8) число работ в цепочке не должно превышать заданного значения;9) сдвиг работы “вправо” по временной оси на время, не превышающее значение, равное заданному проценту от интервала “время начала выполнения работы минус время начала цепочИЗВЕСТИЯ РАН.