Genetic local search for conflict-free minimum-latency aggregation scheduling in wireless sensor networks

Roman Plotnikov, Adil Erzin, Vyacheslav Zalyubovskiy

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

1 Цитирования (Scopus)

Аннотация

We consider a Minimum-Latency Aggregation Scheduling problem in wireless sensor networks when aggregated data from all sensors are required to be transferred to the sink. During one time slot (time is discrete) each sensor can either send or receive one message or be idle. Moreover, only one message should be sent by each sensor during the aggregation session, and the conflicts caused by interference of radio waves must be excluded. It is required to find a min-length conflict-free schedule for transmitting messages along the arcs of the desired spanning aggregation tree (AT) with the root in the sink. This problem is NP-hard in a general case, and also remains NP-hard in a case when AT is given. In this paper, we present a new heuristic algorithm that uses a genetic algorithm and contains the local search procedures and the randomized mutation procedure. The extensive simulation demonstrates a superiority of our algorithm over the best of the previous approaches.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
РедакторыYury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
ИздательSpringer-Verlag GmbH and Co. KG
Страницы216-231
Число страниц16
ISBN (печатное издание)9783030109332
DOI
СостояниеОпубликовано - 1 янв 2019
Событие9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Черногория
Продолжительность: 1 окт 20185 окт 2018

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том974
ISSN (печатное издание)1865-0929

Конференция

Конференция9th International Conference on Optimization and Applications, OPTIMA 2018
СтранаЧерногория
ГородPetrovac
Период01.10.201805.10.2018

Fingerprint Подробные сведения о темах исследования «Genetic local search for conflict-free minimum-latency aggregation scheduling in wireless sensor networks». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Plotnikov, R., Erzin, A., & Zalyubovskiy, V. (2019). Genetic local search for conflict-free minimum-latency aggregation scheduling in wireless sensor networks. В Y. Kochetov, M. Khachay, Y. Evtushenko, V. Malkova, M. Posypkin, & M. Jacimovic (Ред.), Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers (стр. 216-231). (Communications in Computer and Information Science; Том 974). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-10934-9_16