Article

Article title A SHORTEST PATH ALGORITHM FOR DISTRIBUTED MICROSYSTEMS WITH PREFRACTAL TOPOLOGY
Authors L. A. Zinchenko, V. A. Verstov, B. S. Sorokin, I. V. Nikitin, A. S. Bachurin, M. V. Gusev, V. E. Dmitriev
Section SECTION I. DESIGN AUTOMATION
Month, Year 04, 2018 @en
Index UDC 519.17
DOI
Abstract The article presents design features of distributed microsystems, which can be used to implement the Internet of Things. It should be mentioned that for solving practically important problems the weight of a graph edge depends on an application. It is shown that in hierarchical distributed microsystems the issues of reliability of individual nodes, which are information transmitters for individual nodes of the system, are extremely important. It is noted that the use of distributed microsystems in labyrinth structures, for example, in urban environments, using the natural channels of information transmission, requires calculations of multipath radio wave propagation. To increase the reliability of a system under external damage it is suggested to use self-similar sets, in particular fractals, to synthesize the topology of distributed microsystems. The use of prefractal graphs, which are finite analogs of fractal graphs, is discussed. Results of computational experiments are presented to compare the time complexity of the most effective shortest path search algorithms. A shortest path search algorithm is proposed that is oriented to application in distributed microsystems with prefractal topology, taking into account the features of the selected design solution. It is a combination of the Dijkstra’s algorithm and the hierarchy contraction algorithm. It is shown that the use of knowledge allows reducing the computational costs in the search for the shortest path. The features of the proposed algorithm application in the search for a path in distributed microsystems with prefractal topology in labyrinth structures are discussed.

Download PDF

Keywords Distributed microsystems; predfractal graph; shortest path.
References 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, pp. 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, pp. 484-489.
4. Shakhnov V.A., Zinchenko L.A., Terekhov V.V., Mikhaylichenko S.S. Radiatsionnaya stoykost' mikroelektromekhanicheskikh sistem [Radiation Tolerant Microsystems], Nanoinzheneriya [Nanoengineering], 2015, No. 9, pp. 13-17.
5. Mandel'brot B. Fraktal'naya geometriya prirody [Fractal Geometry of nature]. Moscow: Institut komp'yuternykh issledovaniy, 2002, 656 p.
6. Krön B. Growth of self-similar graphs, Journal of Graph Theory, 2004, Vol. 45, No. 3,
pp. 224-239.
7. Kochkarov A.A., Kochkarov R.A. Parallel'nyy algoritm poiska kratchayshego puti na predfraktal'nom grafe [Parallel shortest path search algorithm for predfractal graph], Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki [Computation mathematics and mathematical physics], 2004, No. 6, pp. 1147-1152.
8. P'etronero L., Tozatti E. (red.). Fraktaly v fizike [Fractals in Physics]. Moscow: Mir, 1988, 672 p.
9. Sorokin B.S. Ispol'zovanie lemmy Lorentsa dlya rascheta mnogoluchevogo rasprostraneniya radiovoln v labirintnykh sistemakh [Application of Lorenz’s lemma for multipaths radiowave propagation in urban areas], Trudy XV Vserossiyskoy shkoly-seminara «Fizika i primenenie mikrovoln» [Proc. XV Workshop Waves], 2015, pp. 32-34.
10. Kormen T., Leyzerson Ch., Rivest R., Shteyn K. Algoritmy: postroenie i analiz [Introduction to Algorithms]. Vil'yams, 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, No. 2,
pp. 100-107.
12. Dechter R, Pearl J. Generalized best-first search strategies and the optimality of A*, Journal of the ACM, 1985, Vol. 32, No. 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, pp. 479-490.
15. Zinchenko L.A., Kosolapov I.A., SHakhnov V.A. Osobennosti mnogomasshtabnogo modeliro-vaniya mikrooptoelektromekhanicheskikh sistem s uchetom tekhnologicheskikh pogreshnostey [Features of multiscale modeling of micro-opto-electromechanical systems for DFM], Datchiki i sistemy [Sensors and systems], 2013, No. 9 (172), pp. 29-37.
16. Zinchenko L.A., Sorokin B.S. Bionicheskie informatsionnye sistemy v proektirovanii mikro- i nanosistem [Bionic information systems in the design of micro- and nanosystems], V sb.: KII-2008 Odinnadtsataya natsional'naya konferentsiya po iskusstvennomu intellektu s mezhdunarodnym uchastiem: trudy konferentsii. Rossiyskaya assotsiatsiya iskusstvennogo intellekta [Proc. KII-2008 Eleventh National Conference on Artificial Intelligence with International Participation. Russian Association of Artificial Intelligence], 2008, pp. 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, pp. 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, pp. 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, pp. 97-99.
20. Glushko A.A. Priborno-tekhnologicheskoe modelirovanie v sisteme TCAD Sentaurus. Me-todicheskie ukazaniya k vypolneniyu laboratornykh rabot po distsipline "Avtomatizatsiya proektirovaniya elektronnykh sredstv" [Instrument-technological modeling in TCAD Sentaurus system. Methodical instructions to performance of laboratory works on discipline" automation of design of electronic means"]. Moscow, 2015.

Comments are closed.