Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Genetic local search for conflict-free minimum-latency aggregation scheduling in wireless sensor networks. / Plotnikov, Roman; Erzin, Adil; Zalyubovskiy, Vyacheslav.
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, 2019. стр. 216-231 (Communications in Computer and Information Science; Том 974).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Genetic local search for conflict-free minimum-latency aggregation scheduling in wireless sensor networks
AU - Plotnikov, Roman
AU - Erzin, Adil
AU - Zalyubovskiy, Vyacheslav
PY - 2019/1/1
Y1 - 2019/1/1
N2 - 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.
AB - 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.
KW - Aggregation
KW - Genetic local search
KW - Minimum latency
KW - Simulation
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=85061208608&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-10934-9_16
DO - 10.1007/978-3-030-10934-9_16
M3 - Conference contribution
AN - SCOPUS:85061208608
SN - 9783030109332
T3 - Communications in Computer and Information Science
SP - 216
EP - 231
BT - Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
A2 - Kochetov, Yury
A2 - Khachay, Michael
A2 - Evtushenko, Yury
A2 - Malkova, Vlasta
A2 - Posypkin, Mikhail
A2 - Jacimovic, Milojica
PB - Springer-Verlag GmbH and Co. KG
T2 - 9th International Conference on Optimization and Applications, OPTIMA 2018
Y2 - 1 October 2018 through 5 October 2018
ER -
ID: 18506991