TY - JOUR

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

AU - Plotnikov, Roman

AU - Erzin, Adil

AU - Zalyubovskiy, Vyacheslav

N1 - Publisher Copyright: © 2020 Informa UK Limited, trading as Taylor & Francis Group.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - data aggregation

KW - memetic algorithm

KW - minimum latency

KW - simulation

KW - variable neighbourhood search

KW - Wireless sensor networks

KW - TIME PROBLEM

KW - VARIABLE NEIGHBORHOOD SEARCH

KW - ALGORITHM

UR - http://www.scopus.com/inward/record.url?scp=85077855225&partnerID=8YFLogxK

U2 - 10.1080/10556788.2019.1710836

DO - 10.1080/10556788.2019.1710836

M3 - Article

AN - SCOPUS:85077855225

VL - 36

SP - 697

EP - 719

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 4

ER -