Near Optimal Route Association With Shannon Model in Multi-Drone WSNs

In this paper, we develop a wireless data gathering model for a multi-drone system in traditional wireless sensor networks (WSNs), where each drone serves as a data collector in the extremely large and densely deployed area. Previous solutions usually consider how to schedule the traveling route among nodes, but fail to optimize the data transmission time. We focus on extending the data collection issue over Shannon model which involves the factors such as the transmission bandwidth and the SNR between a drone and a sensor node. A novel and typical system model is formulated and we investigate the corresponding Route Selection and Communication Association (RSCA) problem, that is, given a set of candidate flight routes and a fixed number of deployed nodes, we determine which routes should be selected for traveling and which nodes should be associated such that the overall energy consumption for data gathering could be minimized. We prove the RSCA problem is NP-hard by reduction from the Vertex Cover problem and then devise an efficient and accessible $O(\log \log n)$ approximation algorithm within the time complexity bound by $O(p^{2}\log n\log \log n)$ , where $n$ is the number of sensor nodes and $p$ is the number of routes in WSNs. Extensive simulations are carried out to investigate the performance of our designed algorithm by comparing with the brute-force and random methods. The proposed algorithm achieves 54% more energy consumption at most and 45% more on average comparing with the optimal solution. Furthermore, real-world trace-driven evaluations have been conducted to show that our obtained solution would hold 34% more at most and 25% more on average comparing with the optimal energy consumption and eventually validate our algorithm.