Drone Data Collection Path Planning with Large Neighborhood and Multiple Constraints

doi:10.3778/j.issn.1673-9418.2401011

Abstract

Abstract: In emergency environments with limited public networks, utilizing drones to assist the Internet of things can promote transmission of sensing data timely. In the context of wireless communication range, devising the optimal path for a drone as a mobile collector to collect as much sensor data as possible can be modeled to the close enough orienteering problem (CEOP). Current algorithms for CEOP involve the sequential calculation of the access order of nodes and the collection points in their neighborhood, which is inefficient when the node neighborhood is large and covers multiple surrounding nodes. These approaches also do not take into account constraints such as data transmission duration and drone remote control distance. Therefore, a mathematical model for drone data collection path planning with large neighborhood and multiple constraints is established, and a novel algorithm named GRASP-LN grounded in the greedy randomized adaptive search procedure (GRASP) is proposed to solve it. This algorithm does not calculate overlapping collection points repeatedly, but maintains the set of nodes collected at each waypoint of the path. The drone hovers at each waypoint for a period of time to collect data from nodes within the set. In the experiment conducted in the public CEOP dataset, GRASP-LN shows better solution quality and shorter computation time than GSOA, VNS, and GRASPopt; Compared with the baseline algorithm GRASPopt, the path reward of GRASP-LN has an average increase of 5.86%, a maximum increase of 14.91%, and the average execution time decreased by 69%; Especially when the node neighborhood covers an average of 4.67 or more nodes, the path reward and stability of GRASP-LN are better than GRASPopt. Experiments considering data transmission duration and drone remote control distance limitation verify the effectiveness of GRASP-LN for drone data collection path planning problems with these constraints.

Key words: drone, greedy randomized adaptive search procedure, data collection, close enough orienteering problem, path planning, Internet of things

摘要： 在公网受限的应急环境中，利用无人机辅助物联网能促进传感数据的及时传递。当考虑无线通信距离时，无人机作为移动收集器在有限续航时间内收集尽可能多的传感数据的路径规划可建模为足够近定向问题（CEOP）。现有求解CEOP的算法是逐个计算目标节点的访问顺序及其邻域内的采集点，这在节点邻域较大并覆盖周围多个节点时效率低下，这些方法也没有考虑数据传输时间和无人机遥控距离等约束。为此，建立了大邻域多约束无人机数据收集路径规划的数学模型，提出了基于贪婪随机自适应搜索过程（GRASP）的GRASP-LN算法进行求解。该算法不重复计算重合的采集点，而是维护路径每个航点采集的节点集合，无人机在每个航点悬停一段时间以收集集合内节点的数据。公开的CEOP数据集的实验结果表明，GRASP-LN比GSOA、VNS和GRASPopt具有更好的求解质量和更短的计算时间。与基线算法GRASPopt相比，GRASP-LN的路径奖励平均提高了5.86%，最大提高了14.91%，执行时间平均减少了69%，特别在节点邻域平均覆盖4.67个以上节点时，GRASP-LN的路径奖励和稳定性均优于GRASPopt。考虑数据传输时间和无人机遥控距离约束的实验验证了GRASP-LN算法对考虑这些约束的无人机数据收集路径规划问题的有效性。

关键词: 无人机, 贪婪随机自适应搜索过程, 数据收集, 足够近定向问题, 路径规划, 物联网

PAN Miaoxin, CHEN Chongcheng. Drone Data Collection Path Planning with Large Neighborhood and Multiple Constraints[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(1): 158-168.

潘淼鑫, 陈崇成. 大邻域多约束无人机数据收集路径规划[J]. 计算机科学与探索, 2025, 19(1): 158-168.

References

[1] BEISHENALIEVA A, YOO S J. Multiobjective 3-D UAV movement planning in wireless sensor networks using bioinspired swarm intelligence[J]. IEEE Internet of Things Journal, 2023, 10(9): 8096-8110.
[2] WEI Z, ZHU M, ZHANG N, et al. UAV-assisted data collection for Internet of things: a survey[J]. IEEE Internet of Things Journal, 2022, 9(17): 15460-15483.
[3] 张薇, 何若俊. 面向物联网数据收集的无人机自主路径规划[J/OL]. 航空学报 (2023-11-17) [2024-02-14]. https://link.cnki.net/urlid/11.1929.V.20231116.1509.008.
ZHANG W, HE R J. Autonomous trajectory design for IoT data collection by UAV[J/OL]. Acta Aeronautica et Astronautica Sinica (2023-11-17) [2024-02-14]. https://link.cnki.net/urlid/11.1929.V.20231116.1509.008.
[4] 张庭溢, 汪弘健. 路灯人影和离家出走改进的黑猩猩优化算法[J]. 计算机科学与探索, 2024, 18(6): 1491-1512.
ZHANG T Y, WANG H J. Street lamp shadow imaging and running away from home strategy for improved chimpanzee optimization algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(6): 1491-1512.
[5] 付澍, 杨祥月, 张海君, 等. 物联网数据收集中无人机路径智能规划[J]. 通信学报, 2021, 42(2): 124-133.
FU S, YANG X Y, ZHANG H J, et al. UAV path intelligent planning in IoT data collection[J]. Journal on Communications, 2021, 42(2): 124-133.
[6] LV C, REN Y, LI X, et al. Unmanned aerial vehicle-assisted sparse sensing in wireless sensor networks[J]. IEEE Wireless Communications Letters, 2023, 12(6): 977-981.
[7] LUO C, SATPUTE M N, LI D, et al. Fine-grained trajectory optimization of multiple UAVs for efficient data gathering from WSNs[J]. IEEE/ACM Transactions on Networking, 2021, 29(1): 162-175.
[8] MILAROKOSTAS C, TSOLKAS D, PASSAS N I, et al. A comprehensive study on LPWANs with a focus on the potential of LoRa/LoRaWAN systems[J]. IEEE Communications Surveys and Tutorials, 2023, 25(1): 825-867.
[9] FAIGL J. Data collection path planning with spatially correlated measurements using growing self-organizing array[J]. Applied Soft Computing, 2019, 75: 130-147.
[10] FAIGL J, VÁŇA P, PĚNIČKA R. Multi-vehicle close enough orienteering problem with bézier curves for multi-rotor aerial vehicles[C]//Proceedings of the 2019 International Conference on Robotics and Automation. Piscataway: IEEE, 2019: 3039-3044.
[11] GUNAWAN A, LAU H C, VANSTEENWEGEN P. Orienteering problem: a survey of recent variants, solution approa-ches and applications[J]. European Journal of Operational Research, 2016, 255(2): 315-332.
[12] VANSTEENWEGEN P, SOUFFRIAU W, OUDHEUSDEN D V. The orienteering problem: a survey[J]. European Journal of Operational Research, 2011, 209(1): 1-10.
[13] FAIGL J, PĚNIČKA R, BEST G. Self-organizing map-based solution for the orienteering problem with neighborhoods[C]//Proceedings of the 2016 IEEE International Conference on Systems, Man, and Cybernetics. Piscataway: IEEE, 2016: 1315-1321.
[14] FAIGL J. GSOA: growing self-organizing array-unsupervised learning for the close-enough traveling salesman problem and other routing problems[J]. Neurocomputing, 2018, 312: 120-134.
[15] PĚNIČKA R, FAIGL J, VANA P, et al. Dubins orienteering problem with neighborhoods[C]//Proceedings of the 2017 International Conference on Unmanned Aircraft Systems.Piscataway: IEEE, 2017: 1555-1562.
[16] PĚNIČKA R, FAIGL J, SASKA M. Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants[J]. European Journal of Operational Research, 2019, 276(3): 816-825.
[17] PĚNIČKA R, FAIGL J, SASKA M, et al. Data collection planning with non-zero sensing distance for a budget and curvature constrained unmanned aerial vehicle[J]. Autonomous Robots, 2019, 43(8): 1937-1956.
[18] FAIGL J. Unsupervised learning-based solution of the close enough dubins orienteering problem[J]. Neural Computing & Applications, 2020, 32(24): 18193-18211.
[19] ŠTEFANÍKOVÁ P, VÁŇA P, FAIGL J. Greedy randomized adaptive search procedure for close enough orienteering problem[C]//Proceedings of the 35th ACM/SIGAPP Symposium on Applied Computing. New York:ACM, 2020: 808-814.
[20] DECKEROVÁ J, FAIGL J. Hopfield neural network in solution of the close enough orienteering problem[C]//Proceedings of the 20th Conference Information Technologies-Applications and Theory, Oravská Lesná, Sep 18-22, 2020: 169-175.
[21] QIAN Q, WANG Y, BOYLE D. On solving close enough orienteering problem with overlapped neighborhoods[EB/OL]. (2023-10-06) [2024-02-14]. https://doi.org/10.48550/arXiv.2310.04257.
[22] PAN M, CHEN C, YIN X, et al. UAV-aided emergency environmental monitoring in infrastructure-less areas: LoRa mesh networking approach[J]. IEEE Internet of Things Journal, 2022, 9(4): 2918-2932.