Известия РАН. Теория и системы управления, 2022, № 6, стр. 56-64

Введение. В настоящее время автономные системы используются в различных областях науки и техники. Обсуждение этих вопросов занимает важное место и в современной научно-технической литературе [1–5]. Нередко применение подобных систем связано с работой в опасных или вредных для человека условиях, вплоть до боевого применения. Они работают не только на земле, но и в космосе, воздухе и под водой. Функциональное разнообразие автономных систем весьма велико. Среди них системы обработки информации, управления, робототехнические системы. Понятно, что в случае применения сети из автономных систем (абонентов) круг решаемых задач существенно шире, нежели в случае использования одиночной системы. В связи с этим разработке таких систем специалисты уделяют наибольшее внимание, фокусируясь обычно на исследовании подвижных систем, которые, как правило, основываются на некоторой мультиагентной концепции. Ясно, что работа мультиагентной системы предполагает необходимость обмена информацией между агентами для координации совместных действий. В этом случае встает вопрос об использовании сети из автономных абонентов (АА). Информационное взаимодействие между АА может осуществляться в разных условиях. Прежде всего, может быть различной среда распространения, например, воздушная или водная [6–10]. Для каждой среды справедлива своя скорость распространения информации, своя помехосигнальная обстановка, скорость затухания информационного сигнала и т.п. Так, например, скорость обмена информацией в водной среде через гидроакустический канал существенно ниже скорости обмена в воздушной среде через радиоканал. Понятно, что в общем случае сообщение будет достигать по сети узла-адресата не напрямую, а через цепочку узлов-ретрансляторов, но ограничение на радиус обмена в каждом случае будет свое. Кроме того, при движении АА маршрут доставки сообщения может меняться из-за изменения топологии сети. В этих условиях существенно возрастают требования к организации информационных обменов, что делает необходимым оптимизацию для передаваемых сообщений не только используемых маршрутов, но и последовательности этих сообщений.

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

1. Постановка задачи. Далее предполагается, что рассматриваемая сеть имеет вид неориентированного графа и состоит из одинаковых узлов, функционирующих по одному и тому же алгоритму. Сеть стационарна, что гарантирует постоянство средних значений интенсивностей потоков обменов (заявок), обслуживаний и очередей [11]. В результате взаимного обмена сообщениями каждому узлу известны координаты всех остальных узлов, что позволяет ему строить минимальные по расстоянию маршруты (пути в неориентированном графе) доставки сообщений. Доставка сообщений происходит с помощью некоторого известного алгоритма маршрутизации, опирающегося на таблицы маршрутизации [12]. Для любого сообщения маршрут всегда существует, т.е. аппараты не расходятся слишком далеко друг от друга. В простейшем случае, когда узел-адресат находится на допустимом расстоянии, маршрут доставки одношаговый (не использующий ретранслирующих узлов). Каждый узел периодически излучает сформированную в нем последовательность сообщений, которая состоит из собственных сгенерированных в узле сообщений, а также из сообщений, поступивших в данный узел извне для ретрансляции к другому адресату. Понятно, что в общем случае различным упорядоченностям сообщений, передаваемых узлом, будет соответствовать различная оперативность доставки сообщений. Далее в качестве критерия оперативности используем либо суммарное время ${{\Delta }_{s}}$ доставки всех сообщений из передаваемой последовательности, либо среднее по сообщениям время $\bar {\Delta }$ доставки. Для удобства изложения будем сопровождать параметры сообщения, расположенного на k-й позиции в очереди рассматриваемого узла, нижним индексом $[k]$. В результате для такого сообщения время ожидания в очереди и время переноса имеют обозначения $e_{{[k]}}^{w}$ и $e_{{[k]}}^{t}$ соответственно. При этом под временем переноса будем понимать время от момента начала передачи сообщения до момента конца его приема, а под временем доставки ${{\Delta }_{{[k]}}}$ сообщения между передающим узлом и узлом-адресатом – сумму

Для одношагового маршрута получаем

Здесь ${{e}_{{{\text{[k]}}}}}$ – длительность сообщения на k-й позиции в очереди, $e_{{[k]}}^{d} = {{{{d}_{{[k]}}}} \mathord{\left/ {\vphantom {{{{d}_{{[k]}}}} v}} \right. \kern-0em} v}$ – время прохождения сигнала между передающим узлом и узлом-адресатом, ${{d}_{{[k]}}}$ – расстояние между передающим узлом и узлом-адресатом для сообщения на k-й позиции в очереди, $v$ – скорость распространения звука в заданной акватории.

В случае многошагового маршрута выражение для времени доставки сообщения принимает вид

где ${{r}_{{[k]}}}$ – общее число шагов маршрута, по которому передается сообщение, находящееся на k-й позиции в очереди, i – порядковый номер шага маршрута.

Преобразуем это выражение, выделив из общей суммы слагаемое, характеризующее первый шаг:

Ясно, что в случае многошагового маршрута предсказать размер и содержание очередей сообщений в узлах-ретрансляторах на маршруте следования передаваемого сообщения невозможно. В связи с этим при дальнейшем анализе воспользуемся не точным значением для ${{\Delta }_{{[k]}}}$, а его оценкой ${{\hat {\Delta }}_{{[k]}}}$, где время ожидания на каждом последующем шаге, кроме первого, заменим на его верхнюю границу. Для этого обозначим через $\bar {n}$ верхнюю границу для длины очередей, а через E – верхнюю границу длительности сообщений. В результате их произведение составит верхнюю границу времени ожидания на любом шаге для рассматриваемого сообщения. Тогда получаем

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

Итак, задача состоит в разработке алгоритмов субоптимального упорядочения (планирования) выходной очереди сообщений, построенных с помощью прогнозных оценок для времен доставки сообщений. При передаче сообщения по многошаговому маршруту алгоритм упорядочения применяется на каждом его шаге во всех ретранслирующих узлах сети с формированием новых прогнозов. Для этого далее предлагается идти по пути использования известных [13–17] и разработки новых алгоритмов планирования.

2. Планирование неупорядоченных сообщений. Рассмотрим сначала случай, когда на множестве передаваемых сообщений отсутствует какая-либо предварительная упорядоченность. В качестве критерия будем применять оценку (верхнюю границу) ${{\hat {\Delta }}_{s}}$ для суммарного времени доставки всех сообщений, выражение для которой можно получить из (1.5):

Тогда справедливо утверждение.

Утверждение 1. Верхняя граница ${{\hat {\Delta }}_{s}}$ для суммарного времени доставки в системе связи n неупорядоченных сообщений минимальна, если сообщения упорядочены по неубыванию длительностей:

Доказательства этого и последующих утверждений приведены в Приложении.

Теперь предположим, что на множестве сообщений нужно задавать некоторые приоритеты. Тогда можно использовать в качестве критерия верхнюю границу $\hat {\Delta }_{s}^{w}$ для суммарного взвешенного времени доставки сообщений:

где ${{w}_{{[k]}}}$ – вес сообщения, расположенного на k-й позиции в очереди.

Утверждение 2. Верхняя граница $\hat {\Delta }_{s}^{w}$ для суммарного взвешенного времени доставки неупорядоченных сообщений в системе связи минимальна, если выполняется

3. Планирование частично упорядоченных сообщений. Пусть планируемые для передачи сообщения частично упорядочены путем разбиения на p непересекающихся групп со строгим упорядочением сообщений внутри них и размером ${{n}_{i}}\;i = \overline {1,p} $. Подобное упорядочение может потребоваться в силу разных дополнительных соображений, связанных с управлением передачей информации через сеть. Предполагается, что при составлении общего плана должен сохраняться зафиксированный в группе порядок передачи сообщений, а прерывания групп сообщений запрещены. Обозначим через $e_{i}^{'}$ суммарную длительность i-й группы сообщений:

Утверждение 3. Верхняя граница $\hat {\Delta }_{s}^{w}$ для суммарного времени доставки сообщений в системе связи с p строго упорядоченными группами при запрете прерываний групп минимальна, если группы в плане упорядочены по неубыванию длительностей:

Пусть необходимо задать приоритеты на множестве групп сообщений. Тогда если ${{\hat {\Delta }}_{{g[k]}}}$ – верхняя граница времени доставки для группы, находящейся на k-й позиции в очереди, то следует минимизировать критерий

а группы сообщений с учетом утверждения 2 должны быть упорядочены по правилу

Очевидно, что все описанные выше результаты остаются справедливыми, если в качестве критерия оптимальности использовать не верхнюю границу суммарного времени доставки, а среднюю по сообщениям верхнюю границу $\bar {\hat {\Delta }}$ (утверждения 1 и 2) или среднюю по группам сообщений верхнюю границу ${{\bar {\hat {\Delta }}}_{g}}$ (утверждение 3, а также (3.2)).

Ситуация усложняется, когда в условиях утверждения 3 требуется минимизировать среднюю по сообщениям верхнюю границу $\bar {\hat {\Delta }}$ времени доставки. Тогда если ${{n}_{{[k]}}}$ – размер группы, находящейся на k-й позиции в очереди, то справедливо следующее утверждение.

Утверждение 4. Верхняя граница $\bar {\hat {\Delta }}$ среднего времени доставки сообщений в системе связи с p строго упорядоченными группами при запрете прерываний групп минимальна, если группы в плане упорядочены по неубыванию длительностей:

Наконец, рассмотрим наиболее сложную ситуацию, когда прерывание процесса передачи группы разрешено.

Утверждение 5. Верхняя граница $\bar {\hat {\Delta }}$ среднего времени доставки сообщений в системе связи с p строго упорядоченными группами при разрешении прерываний групп минимальна, если группы в плане упорядочены по правилам.

1. Для каждого сообщения  j в i-й группе вычисляется условная верхняя граница среднего времени доставки (верхняя граница среднего времени доставки при условии размещения подгруппы сообщений, предшествующей (j + 1)-му сообщению в i-й группе, в начале формируемой очереди):

2. Для каждой i-й группы вычисляется

3. Выбирается такая группа $i{\kern 1pt} *$, что

и первые ${{h}_{{i*}}}$ сообщений составляют начало очереди.

4. Снова вычисляются величины ${{\bar {\tilde {\Delta }}}_{{i,{{h}_{i}}}}}$, но без учета сообщений, размещенных в очереди.

5. Третий и четвертый шаги повторяются до упорядочения всех сообщений.

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

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

Пример. Сформируем очереди, используя алгоритмы из утверждений 4 и 5, для трех упорядоченных групп сообщений: ${{M}_{1}} = \{ {{m}_{{11}}},{{m}_{{12}}},{{m}_{{13}}}\} $, ${{M}_{2}} = \{ {{m}_{{21}}},{{m}_{{22}}}\} $, M₃ = $\{ {{m}_{{31}}},{{m}_{{32}}},{{m}_{{33}}},{{m}_{{34}}}\} $. Верхние границы для времен доставки сообщений приведены в табл. 1.

Прерывания запрещены. Средние времена доставки сообщений для групп: ${{\bar {\hat {\Delta }}}_{1}} = 8,$ ${{\bar {\hat {\Delta }}}_{2}} = 8.5,$ ${{\bar {\hat {\Delta }}}_{3}} = 6$.

Результирующая очередь: ${{Q}_{1}} = {{M}_{3}}\,{{M}_{1}}\,{{M}_{2}} = {{m}_{{31}}},{{m}_{{32}}},{{m}_{{33}}},{{m}_{{34}}},{{m}_{{11}}},{{m}_{{12}}},{{m}_{{13}}},{{m}_{{21}}},{{m}_{{22}}}$.

Прерывания разрешены. Действуя в соответствии с алгоритмом из утверждения 5, последовательно за 8 шагов размещаем в очереди фрагменты групп. Условные средние времена доставки фрагментов групп для всех шагов приведены в табл. 2.

Результирующая очередь: ${{Q}_{2}} = {{m}_{{21}}},{{m}_{{11}}},{{m}_{{31}}},{{m}_{{32}}},{{m}_{{33}}},{{m}_{{34}}},{{m}_{{12}}},{{m}_{{13}}},{{m}_{{22}}}$.

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