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

Roman Plotnikov, Adil Erzin, Vyacheslav Zalyubovskiy

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Number of pages23
JournalOptimization Methods and Software
DOIs
Publication statusPublished - 8 Jan 2020

Keywords

  • data aggregation
  • memetic algorithm
  • minimum latency
  • simulation
  • variable neighbourhood search
  • Wireless sensor networks
  • TIME PROBLEM
  • VARIABLE NEIGHBORHOOD SEARCH
  • ALGORITHM

Fingerprint Dive into the research topics of 'GLS and VNS based heuristics for conflict-free minimum-latency aggregation scheduling in WSN'. Together they form a unique fingerprint.

Cite this