Статья

Название статьи АЛГОРИТМ ПОИСКА КРАТЧАЙШЕГО ПУТИ В РАСПРЕДЕЛЕННЫХ МИКРОСИСТЕМАХ С ПРЕДФРАКТАЛЬНОЙ ТОПОЛОГИЕЙ
Автор Л. А. Зинченко, В. А. Верстов, Б. С. Сорокин, И. В. Никитин, А. С. Бачурин, М. В. Гусев, В. Е. Дмитриев
Рубрика РАЗДЕЛ I. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 04, 2018
Индекс УДК 519.17
DOI
Аннотация Рассмотрены особенности проектирования распределенных микросистем, которые могут быть использованы при создании Интернета вещей. Отмечено, что при решении практически важных задач задание веса ребра графа зависит от конкретного приложения. Показано, что в иерархических распределенных микросистемах вопросы обеспечения работоспособности отдельных узлов, являющих ретрансляторами информации для отдельных узлов системы, являются крайне важными. Отмечено, что при использовании распределенных микросистем в лабиринтных структурах, например, в условиях городской застройки, при использовании естественных каналов передачи информации также необходимо учитывать многолучевой характер распространения радиоволн. Для повышения вероятности сохранения работоспособности проектируемых устройств при внешних помехах предложено при синтезе топологии распределенных микросистем использовать самоподобные множества, в частности фракталы. Для одного из возможных вариантов реализации предложенного подхода рассмотрено использование предфрактальных графов, являющихся конечными аналогами фрактальных графов. Были проведены вычислительные эксперименты по исследованию временной сложности наиболее эффективных алгоритмов поиска кратчайшего пути. Анализ полученных результатов позволяет сделать вывод, что алгоритм сжатия иерархий в общем случае показывает лучшую по сравнению с другими алгоритмами производительность только для графов с небольшим количеством вершин, при этом алгоритм Дейкстры обладает лучшей асимптотической временной сложностью по сравнению с алгоритмом сжатия иерархий. Алгоритм A* показал свою асимптотическую эффективность, однако пространственная сложность алгоритма ограничивает его применение при исследовании распределенных микросистем. На основе анализа полученных экспериментальных результатов предложен алгоритм поиска кратчайшего пути, ориентированный на применение в распределенных микросистемах с предфрактальной топологией, учитывающий особенности выбранного проектного решения. Он является комбинацией алгоритма Дейкстры и алгоритма сжатия иерархий. Показано, что использование знаний позволяет снизить вычислительные затраты при поиске кратчайшего пути. Обсуждены особенности применения предложенного алгоритма при поиске пути в распределенных микросистемах с предфрактальной топологией в лабиринтных структурах.

Скачать в PDF

Ключевые слова Распределенные микросистемы; поиск кратчайшего пути; предфрактальные графы; лабиринтные структуры.
Библиографический список 1. Bourgeois J., Goldstein S. Distributed intelligent MEMS: progresses and perspectives. ICT Innovations 2011. Vol. 150. Advances in Intelligent and Soft Computing. – Springer Berlin, Heidelberg, 2012. – P. 15-25.
2. Shakhnov V.A., Zinchenko L.A., Kosolapov I.A. Simulation of distributed MOEMS for smart environments // Proc. 10th International Conference on Advanced Semiconductor Devices and Microsystems, ASDAM 2014. – 2014.
3. Shakhnov V., Zinchenko L., Kosolapov I., Filippov I. Modeling and Optimization of Radiation Tolerant Microsystems // EMS '14 Proceedings of the 2014 European Modelling Symposium. – 2014. – P. 484-489.
4. Шахнов В.А., Зинченко Л.А., Терехов В.В., Михайличенко С.С. Радиационная стойкость микроэлектромеханических систем // Наноинженерия. – 2015. – № 9. – C. 13-17.
5. Мандельброт Б. Фрактальная геометрия природы. – М.: Институт компьютерных исследований, 2002. – 656 с.
6. Krön B. Growth of self-similar graphs // Journal of Graph Theory. – 2004. – Vol. 45, No. 3.
– P. 224-239.
7. Кочкаров А.А., Кочкаров Р.А. Параллельный алгоритм поиска кратчайшего пути на предфрактальном графе // Журнал вычислительной математики и математической физики. – 2004. – № 6. – C. 1147-1152.
8. Пьетронеро Л., Тозатти Э. (ред.). Фракталы в физике. – М.: Мир, 1988. – 672 c.
9. Сорокин Б.С. Использование леммы Лоренца для расчёта многолучевого распространения радиоволн в лабиринтных системах // Труды XV Всероссийской школы-семинара «Физика и применение микроволн». – 2015. – C. 32-34.
10. Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. Алгоритмы: построение и анализ.
– Вильямс, 2006.
11. Hart P. E., Nilsson N. J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics. – 1968. – № 2.
– P. 100-107.
12. Dechter R, Pearl J. Generalized best-first search strategies and the optimality of A* // Journal of the ACM. – 1985. – T. 32, № 3.
13. Geisberger R., Sanders P., Schultes D., Delling D. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks // LNCS. – 2008. – Vol. 5038.
14. Funke S., Storandt S. Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing // LNCS. – 2015. – Vol. 9472. – P. 479-490.
15. Зинченко Л.А., Косолапов И.А., Шахнов В.А. Особенности многомасштабного моделирования микрооптоэлектромеханических систем с учетом технологических погрешностей // Датчики и системы. – 2013. – № 9 (172). – С. 29-37.
16. Зинченко Л.А., Сорокин Б.С. Бионические информационные системы в проектировании микро- и наносистем // В сб.: КИИ-2008 Одиннадцатая национальная конференция по искусственному интеллекту с международным участием: труды конференции. Российская ассоциация искусственного интеллекта. – 2008. – С. 17-25.
17. Bova V.V., Kureichik V.V., Lezhebokov A.A. The integrated model of representation of problem-oriented knowledge in information systems // В сб.: 8th IEEE International Conference on Application of Information and Communication Technologies, AICT 2014 - Conference Proceedings 8. – 2014. – P. 7035923.
18. Kureichik V.V., Kureichik V.M. A fractal algorithm for graph partitioning // Journal of Computer and Systems Sciences International. – 2002. – Vol. 41, No. 4. – P. 568-578.
19. Luchinin V., Afanasjev A., Ilyin V., Korlyakov A., Petrov A. Family of micro switches based on silicon carbide for extreme conditions and duty // В сб.: Proceedings of the 2017 11th International Workshop on the Electromagnetic Compatibility of Integrated Circuits, EMCCompo 2017 11. – 2017. – P. 97-99.
20. Глушко А.А. Приборно-технологическое моделирование в системе TCAD Sentaurus. Методические указания к выполнению лабораторных работ по дисциплине "Автоматизация проектирования электронных средств". – М., 2015.

Comments are closed.