Мобильные агенты и исследования с их помощью

Ключевые слова и синонимы

Распределенные алгоритмы; исследование графов; мобильный агент; навигация; рандеву; маршрутизация; соотношение времени и памяти

Постановка задачи

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

Мобильные агенты

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

Модель сети

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

Меры эффективности, подлежащие исследованию

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

Основные задачи

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

Основные результаты

Считается, что Клод Шеннон [ ] первым предложил алгоритм на базе конечных автоматов для исследования произвольного лабиринта (размером 5 x 5 квадратов) методом проб и ошибок. Задачи об исследованиях с помощью мобильных агентов широко изучались в научной литературе; полезное историческое введение можно найти в работе Фрейньо и др. [11].

Исследование в графах общего вида

Сеть моделируется в виде графа, агент может перемещаться от вершины к вершине только по ребрам графа. Параметры графа могут задаваться двумя разными способами. В работе Денга и Пападимитриу [ ] агент исследует сильно связные ориентированные графы, перемещаясь только в направлении от начала к концу каждого ребра, но не наоборот. В любой момент времени у агента имеется карта всех посещенных вершин и ребер, и он способен распознать их, если попадет в них вновь. Алгоритм минимизирует отношение общего количества посещенных ребер к оптимальному количеству обходов, имеющему место в случае, если граф известен агенту. Панет и Пельц [ ] исследовали неориентированный граф, в котором агенты могли обходить ребра в обоих направлениях. В графовой формулировке задачи нередко требуется, чтобы помимо исследования агент строил карту графа, т.е. выводил его изоморфную копию. Исследование изоморфных графов, предполагающих наличие меток, выполнили Альберс и Хенцингер [ ], а также Денг и Пападимитриу [8]. В работе Панета и Пельца [ ] был представлен алгоритм исследования с временем работы e + O(n), где n – количество вершин, а e – количество связей. Фрейньо и др. [ ] изучали требования к памяти при исследовании неизвестных графов (неизвестного размера) с непомеченными вершинами и локально помеченными ребрами при каждой вершине. Для исследования всех графов диаметра D с максимальной степенью мобильному агенту необходимо Q(D\ogd) бит памяти в случае, если исследование ограничивается планарными графами. Некоторые исследователи также выполняют изучение анонимных графов, в которых агентам позволяется поднимать и бросать камни. Например, Бендер и др. [ ] показали, что для исследования достаточно одного камня, если агенту известна верхняя граница размера графа, и 0 (log log n) камней необходимо и достаточно в противном случае.

Исследование на деревьях

В этой формулировке предполагается, что агент может различать порты в вершине (локально), однако не предусматривается глобальной ориентации ребер и не имеется маркеров. Процесс исследования останавливается, когда мобильный агент обойдет все ребра и остановится на некоторой вершине. Если исследование должно вернуть значение, мобильный агент должен обойти все ребра и остановиться в начальной вершине. Если выполняется бессрочное исследование, мобильный агент должен обойти все ребра, но не обязательно должен остановиться. Верхняя и нижняя границы памяти исследовательских алгоритмов, проанализированные Диксом и др. [ ], представлены в таблице. Они зависят от знаний, которыми обладает мобильный агент. Здесь n – количество вершин дерева, N > n – верхняя граница, известная мобильному агенту, а d – максимальная степень вершины дерева.

Таблица. Исследование в геометрической формулировке

Исследование в геометрической формулировке с неизвестными плоскими и выпуклыми препятствиями осуществили Блюм и др. [5]. Они сравнивали расстояние, пройденное агентом (или роботом) с длиной кратчайшего пути, свободного от препятствий, в конкретной ситуации и описывали и анализировали стратегии деятельности робота, минимизировавшие это соотношение для двух различных типов ситуаций. Исследованию в более общей формулировке с препятствиями в виде полигонов и прямоугольников посвящены работы Денга и др. [7] и Бар-Али и др. [ ], соответственно. Для исследования беспроводных сетей важна формулировка задачи, в которой вершины сети знают о своем местоположении. Для такого случая Кранакис и др. [12] предложили эффективные алгоритмы навигации, а именно маршрутизацию по циркулю и маршрутизацию по грани, которые гарантируют получение результата в графах Делоне и в произвольных планарных геометрических графах, соответственно, используя только локальную информацию.

Рандеву

Задача поиска рандеву отличается от задачи исследования в том, что она рассматривает два поисковых инструмента, расположенных в разных вершинах графа, и стремится минимизировать время, необходимое для их встречи (рандеву) в одной вершине. В любое заданное время мобильные агенты занимают вершину графа и могут оставаться в ней либо перемещаться от вершины к вершине. Нашей задачей является минимизация времени, необходимого для рандеву. Естественным расширением задачи является исследование мобильных систем с несколькими агентами. Говоря в более общем контексте, пусть даны конкретная модель агентов и модель сети; мы говорим, что множество агентов, произвольным образом распределенных по вершинам сети, встречаются (имеют рандеву), если при выполнении своих программ по прошествии некоторого конечного времени все они занимают одну и ту же вершину сети в одно и то же время. Нас особо интересует высокосимметричный случай с анонимными агентами в анонимной сети, простейшим вариантом которого является случай с двумя агентами, стремящимися обеспечить рандеву в кольцевой сети. В частности, в модели, изучавшейся Савчуком [ ], агенты не могут различать вершины, вычисление выполняется посредством синхронных шагов, а ребра при каждой вершине имеют глобальную ориентацию. В таблице 2 приведены соотношения времени и памяти, известные для шести алгоритмов (см. Кранакис и др. [13], а также Флоччини и др. [ ]) в случае, когда k мобильных агентов используют неразличимые камни (по одному на каждого мобильного агента) для обозначения своей позиции в кольце, состоящем из n вершин.