Collecting LoRa Data with an Energy-Budgeted UAV: A Bi-Criteria Approximate Solution

For large-scale LoRa-based Internet-of-Things (IoT) systems, using UAVs to collect data is a promising method, which not only leverages the long-range communication advantages of LoRa but also avoids the high costs associated with deploying fixed-location LoRa gateways. In this paper, we take into account the concurrent data reception capability inherent to LoRa, and propose an innovative algorithm that provides a bi-criteria approximation solution for UAV-assisted LoRa data collection, maximizing the sensor coverage under the UAV's energy budget. Our algorithm is twofold: first, we formulate the problem within a constrained submodular maximization framework incorporating sensor allocation and a Traveling Salesman Problem. Second, proving the NP-hardness of this sensor allocation problem, we develop a constant-factor approximation algorithm for energy-minimum sensor allocation. We present a bi-criteria approximation algorithm that employs a greedy strategy to maximize sensor coverage while adhering to the UAV's energy budget. We evaluate our designs through extensive numerical experiments, demonstrating their efficiency and effectiveness.