Автоматический анализ, декомпозиция и параллельная оптимизация больших однородных сетей

Жизнь современного мира во многом зависит от функционирования больших однородных сетей, таких как проводные и безпроводные коммуникационные системы, сети дорог и трубопроводов. Поддержание их эффективной работы требует автоматического контроля, постоянной оптимизации, включающей обработку больших объемов данных с использованием высокопроизводительных распределенных систем. Предложен новый мета-алгоритм для анализа больших однородных сетей, их альтернативного разбиения на слабосвязанные подсети и параллельной оптимизации наиболее независимых элементов подсетей. Данный подход основан на специфической для сети корреляционной функции, алгоритме имитации отжига и адаптирован для работы в вычислительном кластере. На примере безпроводной коммуникационной сети показано, что предложенный алгоритм существенно увеличивает скорость многопоточной оптимизации. Разработанный общий подход может быть использован для анализа и оптимизации широкого спектра сетей, включая такие специфические типы как искусственные нейронные сети или организованные в виде сетей физиологические системы живых организмов.

однородные сети, декомпозиция, оптимизация, распределенные вычисления

1. Awerbuch B., Goldberg A.V., Luby M., Plotkin S. Network decomposition and locality in distributed computation. Proc. of the 30th Annual Symposium on the Foundations of Computer Science (FOCS 89), 1989, pp. 364-369. doi: 10.1109/SFCS.1989.63504

2. Fantauzzi F., Gaivoronski A.A., Messina E. Decomposition Methods for Network Optimization Problems in the Presence of Uncertainty. Network Optimization, 1997, vol. 450, pp. 234-248. doi: 10.1007/978-3-642-59179-2_12

3. An automatic Sector Planning Method. Patent 104581745 A. Application CH 201510069770, filed February 10 2015, issued April 29 2015, 8 p.

4. Friesen A.L., Domingos P. Recursive Decomposition for Nonconvex Optimization. Proceedings of the 24th International Joint Conference on Artificial Intelligence, 2015, pp. 253-259.

5. Li M., Andersen D.G., Smola A.J. Graph Partitioning via Parallel Submodular Approximation to Accelerate Distributed Machine Learning, 2015, preprint arXiv:1505.04636. https://arxiv.org/abs/1505.04636

6. Singha T., Arbogasta J.E., Neagu N. An incremental approach using local-search heuristic for inventoryrouting problem in industrial gases. Computers and Chemical Engineering, 2015, vol. 80, pp. 199-210.

7. Aarts E., Korst J., Michiels W. Simulated Annealing / Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques. Springer Science, New York, 2013, pp. 265-285. doi: 10.1007/978-1-4614-6940-7_10

8. Lotfollahzadeh T., Kabiri S., Kalbkhani H., Shayesteh M.G. Femtocell base station clustering and logistic smooth transition autoregressive-based predicted signal-to-interference-plus-noise ratio for performance improvement of two-tier macro / femtocell networks. IET Signal Processing, 2016, vol. 10, issue: 1, pp. 1-11. doi: 10.1049/iet-spr.2014.0265

9. Kumar P., Patil B., Ram S. Selection of Radio Propagation Model for Long Term Evolution (LTE) Network. International Journal of Engineering, 2015, vol. 3, issue 1, pp. 373-379.

10. Kifle D.W., Wegmann B., Viering I., Klein A. Impact of Antenna Tilting on Propagation Shadowing Model. IEEE Conference on Vehicular Technology VTC, 2013, pp. 1-5. doi: 10.1109/VTCSpring.2013.6692585