GLS and VNS based heuristics for conflict-free minimum-latency aggregation scheduling in WSN

ABSTRACT

We consider a conflict-free minimum latency data aggregation problem that occurs in different wireless networks. Given a network that is presented as an undirected graph with one selected vertex (a sink), the goal is to find a spanning aggregation tree rooted in the sink and to define a conflict-free aggregation minimum length schedule along the arcs of the tree directed to the sink. Herewith, at the same time slot, each element of the network can either send or receive at most one message. Only one message should be sent by each network element during the whole aggregation session, and the conflicts caused by signal interference should be excluded. This problem is NP-hard and remains NP-hard even in the case when the aggregation tree is given. Therefore, the development of efficient approximation algorithms is very important for this problem. In this paper, we present new heuristic algorithms based on genetic local search and variable neighbourhood search metaheuristics. We conducted an extensive simulation that demonstrates the superiority of our algorithms compared with the best of the previous approaches.

Keywords:

• Wireless sensor networks
• data aggregation
• minimum latency
• variable neighbourhood search
• memetic algorithm
• simulation

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The research is partially supported by the Russian Science Foundation (project 18–71–00084, Sections 4, 5, 6, and 7) and by the program of fundamental scientific researches of the SB RAS -Siberian Branch, Russian Academy of Sciences (project 0314–2019–0014, Sections 1, 2, and 3).

Notes on contributors

Roman Plotnikov

Roman Plotnikov graduated from the Faculty of Mechanics and Mathematics of Novosibirsk State University, Novosibirsk, Russia, and received his M.S. degree in applied mathematics and computer science from Novosibirsk State University in 2010. In 2013 he defended his Ph.D. thesis from the Institute of Computational Mathematics and Mathematical Geophysics, Siberian Branch of the Russian Academy of Sciences. From 2016 to the present, he holds the position of researcher at the Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences. He is a specialist in the development and software implementation of approximate algorithms for discrete optimization problems.

Adil Erzin

Prof. Adil Erzin graduated from the Faculty of Mechanics and Mathematics of Novosibirsk State University, Novosibirsk, Russia, in 1978. From 1978 to 1980, he taught higher mathematics at the Novosibirsk Electro-Technical Institute, Novosibirsk. In 1980 he entered the graduate school of Novosibirsk State University and in 1984 he defended his thesis. In 2004 he defended his doctoral dissertation. Since 1984 he has been working at the Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences. Currently, he is the main researcher and member of the academic council of the institute. He is also a professor (part-time) at Novosibirsk State University. Since 2010, he has headed the Department of Theoretical Cybernetics and is a member of the academic council of the faculty. His areas of expertise are algorithms design in discrete optimization, structure optimization of complex systems, routing and computational geometry.

Vyacheslav Zalyubovskiy

Vyacheslav Zalubovskiy received the M.S. degree in mathematics from Novosibirsk State University, Russia, in 1984, and the Ph.D. degree in mathematics from the Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, in 2006. Over three decades, he has been a scientific researcher with the Sobolev Institute of Mathematics. His recent research focuses on the design and analysis of optimal and approximation algorithms for combinatorial optimization problems and their applications, particularly in the areas of networking, planning and scheduling.