Y.S. Vintenkova – Assistant, Chair of Radioelectronic and Telecommunication Systems, Kazan National Research Technical University named after A.N. Tupolev (KNRTU-KAI)
The previously proposed method of collective dynamic routing allows to increase wideband radio access networks efficiency. However, in order to use the method in a real network, it is necessary to reduce the computational complexity of the algorithm used to select the optimal routes. Since the problem of finding a set of optimal routes is an integer linear programming task, an optimal solution can be obtained using exact methods, for example, branch and bound method, which is characterized by high computational complexity. Therefore, the actual problem is to design an algorithm that would make it possible to obtain a solution as close to optimal as possible for a relatively short calculation time. In addition to exact methods, it is possible to use various meta-heuristic approaches and one of the most effective among them is the ant colony optimization algorithm. The canonical version of this algorithm cannot be used in the collective dynamic routing method because of calculations of multiple agents positions, but its recurrent algorithm modification with a probabilistic rule of route selection makes its application possible.
Moreover, a transition from integer linear programming to non-integer linear programming is possible with the use of the simplex me-thod. But in this case resulting solution is rounding up which causes the errors in obtained solutions. The values obtained by the simplex method without rounding are optimal.
Based on the computational experiment, the analysis of the developed recurrent algorithm and the simplex method with rounding based on the obtained solutions and the execution time was carried out for three different network options. It is shown that there are conditions for the collective dynamic routing application, when the solutions obtained with the recurrent algorithm become closer to optimal than solutions obtained by the simplex method with rounding.
- Shherbina O.A. Metajevristicheskie algoritmy dlja zadach kombinatornoj optimizacii (Obzor) // Tavricheskij vestnik informatiki i matematiki. 2014. № 1(24). S. 5672.
- Spirina E.A. Optimizacija raspredelenija informacii v fiksirovannyh setjah shirokopolosnogo radiodostupa s uchetom vnutrisistemnyh pomeh.// Zhurnal radiojelektroniki [jelektronnyj zhurnal]. 2015. No 9. URL: http://jre.cplire.ru/jre/sep15/ 5/text.pdf. (Data obrashhenija: 29.11.2017).
- Vintenkova Ju.S., Kozlov S.V., Spirina E.A. Analiz jeffektivnosti metoda sovmestnoj dinamicheskoj marshrutizacii v setjah shirokopolosnogo radiodostupa s trafikom protokolov TCP, HTTP, FTP // Zhurnal radiojelektroniki [jelektronnyj zhurnal]. 2016. № 1. URL: http://jre.cplire.ru/jre/jan16/5/text.pdf. (Data obrashhenija: 29.11.2017).
- Shevchenko V.N., Zolotyh N.Ju. Linejnoe i celochislennoe linejnoe programmirovanie. Nizhnij Novgorod: Izd-vo Nizhegorodskogo gosudarstvennogo un-ta im. N.I. Lobachevskogo. 2004. 154 s.
- Shtovba S.D. Murav'inye algoritmy // Exponenta Pro. Matematika v prilozhenijah. 2003. № 4. S. 7075.
- Ondřej Míča. Comparison Metaheuristic Methods by Solving Travelling Salesman Problem // The International Scientific Conference INPROFORUM 2015 Proceedings. Р. 161165.
- Mukhairez Hosam H.A., Maghari Ashraf Y.A. Performance Comparison of Simulated Annealing, GA and ACO Applied to TSP // International Journal of Intelligent Computing Research (IJICR). December 2015. V. 6. Is. 4. Р. 647654.
- Marco Dorigo, Thomas Stuetzle. Ant Colony Optimization. MIT Press. 2004. 305 c.
- Svidetel'stvo o gosudarstvennoj registracii programmy dlja JeVM №2016663493. Programma OFDM Analyzer – Zajavka №2016661064; Zaregistrirovana v Reestre programm dlja JeVM 8.12.2016 / Kozlov S.V., Spirina E.A., Vintenkova Ju.S.
- Chernikov Ju.G. Sistemnyj analiz i issledovanie operacij. M.: Izd-vo Moskovskogo gosudarstvennogo gornogo un-ta. 2006. 370 s.