MATEC Web Conf.
Volume 125, 201721st International Conference on Circuits, Systems, Communications and Computers (CSCC 2017)
|Number of page(s)||8|
|Published online||04 October 2017|
Convergecast with Unbounded Number of Channels
1 Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, Novosibirsk, Russia
2 Novosibirsk State University, 2 Pirogova Str., Novosibirsk, Russia
* Corresponding author: email@example.com
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.
© The Authors, published by EDP Sciences, 2017
This is an Open Access article distributed under the terms of the Creative Commons Attribution License 4.0, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.