Convergecast with Unbounded Number of Channels

Roman Plotnikov, Adil Erzin, Vyacheslav Zalyubovskiy

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

We consider a problem of minimum length scheduling for the conflict-free aggregation convergecast in wireless networks in a case when each element of a network uses its own frequency channel. This problem is equivalent to the well-known NP-hard problem of telephone broadcasting since only the conflicts between the children of the same parent are taken into account. We propose a new integer programming formulation and compare it with the known one by running the CPLEX software package. Based on the results of a numerical experiment, we concluded that our formulation is more preferable in practice to solve the considered problem by CPLEX than the known one. We also propose a novel heuristic algorithm, which is based on a genetic algorithm and a local search metaheuristic. The simulation results demonstrate the high quality of the proposed algorithm compared to the best known approaches.

Original languageEnglish
Article number03001
JournalMATEC Web of Conferences
Volume125
DOIs
Publication statusPublished - 4 Oct 2017

Fingerprint Dive into the research topics of 'Convergecast with Unbounded Number of Channels'. Together they form a unique fingerprint.

Cite this