Work by NSU Scientists won an Award at the Largest European Conference on Algorithms

Two articles presenting work by the Laboratory of Algorithms at the NSU Mechanics and Mathematics Department (NSU MMD) were given at the 13th International Conference on Algorithms and Wireless Sensor Network Experiments (ALGOSENSORS) in Vienna (Austria).

The Conference was held in conjunction with the largest European Congress on algorithms, ALGO. The articles featured work conducted in collaboration with colleagues from Berlin and the S.L. Sobolev Institute of Mathematics SB RAS. One of the articles, authored by the Head of the NSU MMD Laboratory of Algorithms, René van Bevern, and a team lead by Professor Rolf Niedermayer at the Berlin Technical University, won the award for the best article at ALGOSENSORS. The article explores building an energy efficient communication network between wireless sensors.

Van Bevern, described the work:

Wireless sensor networks have numerous uses including monitoring weather conditions and environmental pollution. Of course, the sensors must transmit the information collected to a base station for further processing. Our task was to determine the power and, correspondingly, the transmission range for each sensor in such a way that an associated communication network is created between them and energy costs are minimal. The easiest algorithm solves the problem for n sensors in time n ^ (n-2) so if we miraculously build a supercomputer that can solve the task for 1000 sensors per day, then it will take about 7.5 years to solve the problem for 1001 sensors. Our article contains, among other things, a more efficient algorithm that relies on the obvious fact that the transmission power of each sensor must be large enough to exchange information with at least the closest sensor to it. If you assign this necessary power to each sensor some sensors will already be connected, but the communication network can still consist of several unrelated components. One of our main results is that we proved the problem is effectively solved when there are only a few of these components.

The joint work of the Laboratory of Algorithms with the Berlin Technical University continues on this subject. Currently, a fourth-year MMD student and Pavel Smirnov from the Laboratory of Algorithms, are engaged in programming and experimentally testing the theoretical algorithm. Also, in August 2017, co-author of the article Professor Rolf Niedermayer visited Novosibirsk State University for further research in the field of energy efficient sensor networks with Renee van Bevern and Alexander Kononov, an associate at the Laboratory of Algorithms and the S.L. Sobolev Mathematics Institute SB RAS.

The second article presented in Vienna looks at the next level, when the communication network between the sensors is built and it is required to transfer information from the sensors to the base station as quickly as possible, ie, to find the shortest data transfer schedule. The authors of the article are Adil Erzin, Head of the MMD Department of Theoretical Cybernetics, employee at the Laboratory of Algorithms and the S.L. Sobolev Mathematics Institute and Roman Plotnikov, a researcher at the Mathematics Institute.Altogether more than 170 reports were presented at the ALGO Congress. The largest delegations of scientists came from Germany, Poland, France, Britain, Israel, Japan and China. Russia was represented in Vienna by Adil Erzin and Vladimir Shenmaier from the NSU MMD Department of Theoretical Cybernetics and S.L. Soboleva Mathematics Institute.

This is the second time a joint article from the MMD Laboratory of Algorithms and the Berlin Technical University has been awarded a prize at the ALGO Congress. In 2015 René van Bevern won for the best article at the international ATMOS transport conference.