Research output: Contribution to journal › Article › peer-review
Convergecast with Unbounded Number of Channels. / Plotnikov, Roman; Erzin, Adil; Zalyubovskiy, Vyacheslav.
In: MATEC Web of Conferences, Vol. 125, 03001, 04.10.2017.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Convergecast with Unbounded Number of Channels
AU - Plotnikov, Roman
AU - Erzin, Adil
AU - Zalyubovskiy, Vyacheslav
PY - 2017/10/4
Y1 - 2017/10/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85032871770&partnerID=8YFLogxK
U2 - 10.1051/matecconf/201712503001
DO - 10.1051/matecconf/201712503001
M3 - Article
AN - SCOPUS:85032871770
VL - 125
JO - MATEC Web of Conferences
JF - MATEC Web of Conferences
SN - 2261-236X
M1 - 03001
ER -
ID: 9721723