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

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

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

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

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

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

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

Модель сети

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

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