2019/04/22 by Roman Plotnikov, Plotnikov, Roman, Adil Erzin +3
Computer Science · #Energy Efficient Wireless Sensor Networks #Security in Wireless Sensor Networks #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1904.09802
We consider a conflict-free minimum latency data aggregation problem that\noccurs in different wireless networks. Given a network that is presented as an\nundirected graph with one selected vertex (a sink), the goal is to find a\nspanning aggregation tree rooted in the sink and to define a conflict-free\naggregation minimum length schedule along the arcs of the tree directed to the\nsink. Herewith, at the same time slot, each element of the network can either\nsend or receive at most one message. Only one message should be sent by each\nnetwork element during the whole aggregation session, and the conflicts caused\nby signal interference should be excluded. This problem is NP-hard and remains\nNP-hard even in the case when the aggregation tree is given. Therefore, the\ndevelopment of efficient approximate algorithms is very essential for this\nproblem. In this paper, we present new heuristic algorithms based on the\ngenetic local search and the variable neighborhood search metaheuristics. We\nconducted an extensive simulation that demonstrates the superiority of our\nalgorithms compared with the best of the previous approaches.\n