Drones Path Planning for WSN Data Gathering: A Column Generation Heuristic Approach

被引：0

作者：

Garraffa, Michele ^{[1
]}

Bekhti, Mustapha ^{[2
]}

Letocart, Lucas ^{[1
]}

Achir, Nadjib ^{[2
]}

Boussetta, Khaled ^{[2
]}

机构：

[1] Univ Paris 13, LIPN CNRS UMR7030, Sorbonne Paris Cite, 99 Ave JB Clement, F-93430 Villetaneuse, France

[2] Univ Paris 13, L2TI, Sorbonne Paris Cite, EA 4303, 99 Ave JB Clement, F-93430 Villetaneuse, France

来源：

2018 IEEE WIRELESS COMMUNICATIONS AND NETWORKING CONFERENCE (WCNC) | 2018年

关键词：

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we investigate the use of a swarm of drones as mobile data gathering sinks for scattered wireless sensors over large areas. Precisely, we address the path planning issue with the objective of minimizing the drones' travel duration. Several criteria are also considered, such as: 1) energy autonomy of the drones, 2) a good fairness regarding route lengths, 3) collision avoidance and 4) drones' tracking enabled by the transmission of their positions to terrestrial base stations. These base stations, and consequently the drones' paths, must be carefully determined in the aim to statistically guarantee a minimum threshold on the delivery ratio of drones' position packets. The problem is formalized as a multiple Traveling Salesman problem, which is known to be NP-Hard. To cope with the computational complexity that rises for realistic parameters, we propose a heuristic approach based on a column generation approach.

引用

页数：6

共 10 条

[1] The multiple traveling salesman problem: an overview of formulations and solution procedures
Bektas, T
[J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2006, 34 (03): : 209 - 219
[2] EXACT ALGORITHMS FOR THE VEHICLE-ROUTING PROBLEM, BASED ON SPANNING TREE AND SHORTEST-PATH RELAXATIONS
CHRISTOFIDES, N
MINGOZZI, A
TOTH, P
[J]. MATHEMATICAL PROGRAMMING, 1981, 20 (03) : 255 - 282
[3] An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
Feillet, D
Dejax, P
Gendreau, M
Gueguen, C
[J]. NETWORKS, 2004, 44 (03) : 216 - 229
[4] Joncour C., 2010, Electron. Notes Discrete Math., V36, P695
[5] A Comprehensive Study of Data Collection Schemes Using Mobile Sinks in Wireless Sensor Networks
Khan, Abdul Waheed
Abdullah, Abdul Hanan
Anisi, Mohammad Hossein
Bangash, Javed Iqbal
[J]. SENSORS, 2014, 14 (02) : 2510 - 2548
[6] Ma XY, 2016, INT WIREL COMMUN, P995, DOI 10.1109/IWCMC.2016.7577194
[7] INTEGER PROGRAMMING FORMULATION OF TRAVELING SALESMAN PROBLEMS
MILLER, CE
TUCKER, AW
ZEMLIN, RA
[J]. JOURNAL OF THE ACM, 1960, 7 (04) : 326 - 329
[8] Stirling T., 2013, ENERGY TIME EFFICIEN, P5
[9] Sugihara R, 2008, LECT NOTES COMPUT SC, V5067, P386, DOI 10.1007/978-3-540-69170-9_26
[10] Wang C., 2016, INT J DISTRIB SENS N, V2015

← 1 →