V.I. Terekhov – Ph. D. (Eng.), Associate Professor, Department «Information Processing and Control Systems», Bauman Moscow State Technical University
M.P. Myalkin – Post-graduate Student, Department «Information Processing and Control Systems», Bauman Moscow State Technical University
Nowadays there are about two devices of the Internet of things (IoT) per person and this number is constantly increasing. According to the Norwegian research organization SINTEF 90% of the information in the world has been formed during the last two years. Analyzing the smart home market Gartner predicts that the number of connected devices to the Internet will double by 2020.
The increasing of the number of IoT devices goes along with the growth of their productivity. The most popular microcontrollers which are often used as a hardware platform for IoT devices are Raspberry Pi and Arduino. Analysis of the development of these devices shows that the annual productivity growth is 15%.
Considering the rapid growth of the number of distributed IoT devices and the computing power everybody understands the importance of the using of such devices to solve problems requiring a large amount of resources and time as optimization problems of large dimension, where the size of the initial data of the problem. Tens of vertices of the graph is meant by large dimension. The article reviews the travelling salesman problem as an optimization problem. Its optimization formulation belongs to the class of NP-hard problems. The solution of this problem seems to be advisable with the help of the methods of distributed computing.
Analyzing the distributed bruteforce method, it was proved that in the nearest future this method would solve the travelling salesman problem with less than 15 nodes in a time not exceeding 10 minutes. Therefore, the article points out other algorithms for solving travelling salesman problem: the branch and bounds method, the genetic algorithm, the ant colony optimization algorithm.
The dependence of the time for solving the travelling salesman problem on the productivity of the device is shown using various methods in the paper. Using distributed methods on IoT-devices predicts the solution of the travelling salesman problem in the nearest future.
- Evans D. Internet veshchey: kak sleduyushchaya evolyutsiya Interneta menyayet vse // Belaya kniga CISCO. 2011. T. 1. S. 1−11.
- Problema optimizatsii. Rezhim dostupa: https://en.wikipedia.org/wiki/Optimization_problem (data obrashcheniya 05.09.2017).
- Internet magaziny: kratkiy obzor. Rezhim dostupa: https://www.internetsociety.org/sites/default/files/report-InternetOfThings-20151221-ru.pdf (data obrashcheniya 08.09.2017).
- Obzor noutbukov / noutbukov. Rezhim dostupa: http://www.notebookcheck.net (data obrashcheniya: 15.10.2017).
- Zadacha kommivoyazhera. Rezhim dostupa: https://ru.wikipedia.org/wiki/Zadacha_kommivoyazhera (data obrashcheniya 15.10.2017).
- Naseleniye Rossii: chislennost', dinamika, statistika. Rezhim dostupa: http://www.statdata.ru/russia (data obrashcheniya 15.10.2017).
- Goroda Rossii. Rezhim dostupa: https://ru.wikipedia.org/wiki/Goroda_Rossii (data obrashcheniya 15.10.2017).
- Geekbench 4. Kross-platformennyy test. Rezhim dostupa: http://geekbench.com/ (data obrashcheniya 20.10.2017).