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

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

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

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

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

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

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

Модель сети

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

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

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

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

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