|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
АЛГОРИТМ ПОИСКА КРАТЧАЙШЕГО ПУТИ В РАСПРЕДЕЛЕННЫХ МИКРОСИСТЕМАХ С ПРЕДФРАКТАЛЬНОЙ ТОПОЛОГИЕЙстатья
Дата последнего поиска статьи во внешних источниках: 26 июня 2019 г.
- Авторы: Зинченко Л.А., Верстов В.А., Сорокин Б.С., Никитин И.В., Бачурин А.С., Гусев М.В., Дмитриев В.Е.
- Журнал: Известия ЮФУ. Технические науки
- Номер: 4
- Год издания: 2018
- Издательство: Федеральное государственное автономное образовательное учреждение высшего образования "Южный федеральный университет"
- Местоположение издательства: Ростов-на-Дону
- Первая страница: 47
- Последняя страница: 58
- DOI: 10.23683/2311-3103-2018-4-47-58
- Аннотация: Рассмотрены особенности проектирования распределенных микросистем, которые могут быть использованы при создании Интернета вещей. Отмечено, что при решении практически важных задач задание веса ребра графа зависит от конкретного приложения. Показано, что в иерархических распределенных микросистемах вопросы обеспечения работоспособности отдельных узлов, являющих ретрансляторами информации для отдельных узлов системы, являются крайне важными. Отмечено, что при использовании распределенных микросистем в лабиринтных структурах, например, в условиях городской застройки, при использовании естественных каналов передачи информации также необходимо учитывать многолучевой характер распространения радиоволн. Для повышения вероятности сохранения работоспособности проектируемых устройств при внешних помехах предложено при синтезе топологии распределенных микросистем использовать самоподобные множества, в частности фракталы. Для одного из возможных вариантов реализации предложенного подхода рассмотрено использование предфрактальных графов, являющихся конечными аналогами фрактальных графов. Были проведены вычислительные эксперименты по исследованию временной сложности наиболее эффективных алгоритмов поиска кратчайшего пути. Анализ полученных результатов позволяет сделать вывод, что алгоритм сжатия иерархий в общем случае показывает лучшую по сравнению с другими алгоритмами производительность только для графов с небольшим количеством вершин, при этом алгоритм Дейкстры обладает лучшей асимптотической временной сложностью по сравнению с алгоритмом сжатия иерархий. Алгоритм A* показал свою асимптотическую эффективность, однако пространственная сложность алгоритма ограничивает его применение при исследовании распределенных микросистем. На основе анализа полученных экспериментальных результатов предложен алгоритм поиска кратчайшего пути, ориентированный на применение в распределенных микросистемах с предфрактальной топологией, учитывающий особенности выбранного проектного решения. Он является комбинацией алгоритма Дейкстры и алгоритма сжатия иерархий. Показано, что использование знаний позволяет снизить вычислительные затраты при поиске кратчайшего пути. Обсуждены особенности применения предложенного алгоритма при поиске пути в распределенных микросистемах с предфрактальной топологией в лабиринтных структурах.
- Добавил в систему: Сорокин Борис Сергеевич