Convergecast with Unbounded Number of Channels

Roman Plotnikov, Adil Erzin, Vyacheslav Zalyubovskiy

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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