Projects / Programmes
Graph models and algorithms applied to parameterizing base stations of fourth generation
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| P170 |
Natural sciences and mathematics |
Computer science, numerical analysis, systems, control |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
frequency assignment, max-k-cut, self-organized-networks, 4G base stations, LTE
Researchers (24)
Organisations (5)
Abstract
The objective of this project is to use mathematical modeling, properties and algorithms to optimize the configuration parameters and design of the wireless networks of 4th generation, maximizing the bandwidth and therefore the efficiency of the network.
The need for this research was identified through the patent-yielding project "Pico base stations of the fourth generation" [LPK, LVS, LKM] of two partners who discovered that several mathematical problems related to the network configuration management have been investigated in the mathematical bibliography, however, there are no known attempts at exploiting this knowledge for the particular problem at hand, as well as there is no mathematical investigation into some specific aspects of the problem.
The consortium of world-reputed scientists and entrepreneurs joined in this project will focus on bridging this interdisciplinary gap. We will study the max-k-cut problem, which is the mathematical model behind frequency assignment optimization in the case of a prescribed number of allowed frequencies, in relation to particular families of disk graphs related to parameterizing a wireless network of fourth generation. Besides knowing that the problem is NP hard for general disk graphs, not much is known regarding the specific disk graphs that arise from modeling interferences in the wireless networks of the fourth generation. We hope to reveal structural insights, related both to the geometric structure of the problem, as well as to the families of graphs obtained by incremental changes of the network's parameters, and to exploit these structural findings in design of novel, efficient approximation algorithms and heuristics. We will evaluate these algorithms on both simulated and real data. The theoretical knowledge acquired in the project will be disseminated through publications at international conferences and journals, and the intellectual property will be assessed for its business potential and protected through patents.
In the project, we will focus on the following goals: (i) develop structural understanding of the problem of max-k-cut on specific families of disk intersection graphs that result from 4G wireless network configuration problems, and investigate implications on 4G wireless network design; (ii) design approximation and heuristic algorithms for the max-k-cut problem on specific families of graphs and prove their feasibility; (iii) evaluate the performance of these algorithms on simulated data and real-world instances of the problem; (iv) integrate the best of the developed algorithms into current state-of-the-art
4G wireless network configuration systems and replace existing algorithms that do not use the mathematical structure of the problem.
These goals will be addressed in three work packages, WP1 led by IMFM to address goal (i), WP2 led by FNM to address goal (ii), and WP3 led by LTFE to address goals (iii) and (iv). The work packages will be executed through four project phases: 1) project setup, devoted to establishing collaboration infrastructure and gather the most recent bibliography, 2) benchmark prototype phase, devoted to establishing the complete data flow from input instances to output network configurations, 3) agile research phase, a series of consecutive research-develop-verify cycles devoted to testing implications of theoretical findings to new algorithms and their performance on data, 4) the wrap-up phase, devoted to finalizing the project.
The results of the project can have significant impact on the efficiency of the next generation wireless networks. Through this, the partners expect to benefit from mutual collaboration and exchange of ideas, as well as benefit the society by assisting sustained development of next generation wireless networks and promoting applications of basic and technological scientific achievements for improvement of the quality of life.
Significance for science
We presented a difference between between investigating frequency assigment with minimum interference and that with maximum throughput. We presented a taxonomy of realistic problem instances related to configuring WiFi routers. It is important for the users as it presents easier way for choosing the best known method. It enables researchers better control on the scientific development of this research area.
Significance for the country
During the project we investigated in great detaile various challenges that the researchers and practitioners are facing when trying to apply their knowledge. In particular, we investigated and contextualized the concept of technology readiness levels, which was initially developed for NASA Space Technologies projects and DARPA military applications, and has recently been adopted in Horizon 2020 European projects. We applied our findings in our lectures on applied mathematics, mathematical modeling and operation research, and presented them in several public engagement talks, as well as in discussion with Chamber of Commerce and Industry Slovenia regarding recent misinterpretations of research tax relief for R&D oriented businesses by slovenian tax and revenue agency. The extent to which the concept of technology readiness levels needs promotion in Slovenia is best illustrated by Google image search: in English, it turns exclusively images, related to hi-tech knowledge being pushed from basics sciences towards marketable applications, whereas in Slovenian, Google image search for »stopnja tehnološke zrelosti« returns almost exclusively images refering to agricultural meaning of the term, and even »stopnja zrelosti tehnologije«-»level of tipeness of technology« does not produce much different results. We will engage in further communications of popularizing this concept as well as sharing our experience on increasing technology readiness levels of technologies in Slovenian business and academia.
Most important scientific results
Annual report
2013,
2014,
2015,
final report
Most important socioeconomically and culturally relevant results
Annual report
2013,
2014,
2015,
final report
