Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial Vehicles
This paper proposes a framework for the wireless sensor data acquisition using a team of Unmanned Aerial Vehicles (UAVs). Scattered over a terrain, the sensors detect information about their surroundings and can transmit this information wirelessly over a short range. With no access to a terrestrial...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/21/20/6851 |
| _version_ | 1797513154412937216 |
|---|---|
| author | Vincent Roberge Mohammed Tarbouchi |
| author_facet | Vincent Roberge Mohammed Tarbouchi |
| author_sort | Vincent Roberge |
| collection | DOAJ |
| description | This paper proposes a framework for the wireless sensor data acquisition using a team of Unmanned Aerial Vehicles (UAVs). Scattered over a terrain, the sensors detect information about their surroundings and can transmit this information wirelessly over a short range. With no access to a terrestrial or satellite communication network to relay the information to, UAVs are used to visit the sensors and collect the data. The proposed framework uses an iterative k-means algorithm to group the sensors into clusters and to identify Download Points (DPs) where the UAVs hover to download the data. A Single-Source–Shortest-Path algorithm (SSSP) is used to compute optimal paths between every pair of DPs with a constraint to reduce the number of turns. A genetic algorithm supplemented with a 2-opt local search heuristic is used to solve the multi-travelling salesperson problem and to find optimized tours for each UAVs. Finally, a collision avoidance strategy is implemented to guarantee collision-free trajectories. Concerned with the overall runtime of the framework, the SSSP algorithm is implemented in parallel on a graphics processing unit. The proposed framework is tested in simulation using three UAVs and realistic 3D maps with up to 100 sensors and runs in just 20.7 s, a 33.3× speed-up compared to a sequential execution on CPU. The results show that the proposed method is efficient at calculating optimized trajectories for the UAVs for data acquisition from wireless sensors. The results also show the significant advantage of the parallel implementation on GPU. |
| first_indexed | 2024-03-10T06:13:40Z |
| format | Article |
| id | doaj.art-b1eadd0aca1749cea5265796dc74e0d6 |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T06:13:40Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-b1eadd0aca1749cea5265796dc74e0d62023-11-22T19:58:28ZengMDPI AGSensors1424-82202021-10-012120685110.3390/s21206851Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial VehiclesVincent Roberge0Mohammed Tarbouchi1Department of Electrical and Computer Engineering, Royal Military College of Canada, Kingston, ON K7K 7B4, CanadaDepartment of Electrical and Computer Engineering, Royal Military College of Canada, Kingston, ON K7K 7B4, CanadaThis paper proposes a framework for the wireless sensor data acquisition using a team of Unmanned Aerial Vehicles (UAVs). Scattered over a terrain, the sensors detect information about their surroundings and can transmit this information wirelessly over a short range. With no access to a terrestrial or satellite communication network to relay the information to, UAVs are used to visit the sensors and collect the data. The proposed framework uses an iterative k-means algorithm to group the sensors into clusters and to identify Download Points (DPs) where the UAVs hover to download the data. A Single-Source–Shortest-Path algorithm (SSSP) is used to compute optimal paths between every pair of DPs with a constraint to reduce the number of turns. A genetic algorithm supplemented with a 2-opt local search heuristic is used to solve the multi-travelling salesperson problem and to find optimized tours for each UAVs. Finally, a collision avoidance strategy is implemented to guarantee collision-free trajectories. Concerned with the overall runtime of the framework, the SSSP algorithm is implemented in parallel on a graphics processing unit. The proposed framework is tested in simulation using three UAVs and realistic 3D maps with up to 100 sensors and runs in just 20.7 s, a 33.3× speed-up compared to a sequential execution on CPU. The results show that the proposed method is efficient at calculating optimized trajectories for the UAVs for data acquisition from wireless sensors. The results also show the significant advantage of the parallel implementation on GPU.https://www.mdpi.com/1424-8220/21/20/6851data acquisitiongenetic algorithmgraphics processing unitspath planningparallel computingunmanned aerial vehicle |
| spellingShingle | Vincent Roberge Mohammed Tarbouchi Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial Vehicles Sensors data acquisition genetic algorithm graphics processing units path planning parallel computing unmanned aerial vehicle |
| title | Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial Vehicles |
| title_full | Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial Vehicles |
| title_fullStr | Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial Vehicles |
| title_full_unstemmed | Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial Vehicles |
| title_short | Parallel Algorithm on GPU for Wireless Sensor Data Acquisition Using a Team of Unmanned Aerial Vehicles |
| title_sort | parallel algorithm on gpu for wireless sensor data acquisition using a team of unmanned aerial vehicles |
| topic | data acquisition genetic algorithm graphics processing units path planning parallel computing unmanned aerial vehicle |
| url | https://www.mdpi.com/1424-8220/21/20/6851 |
| work_keys_str_mv | AT vincentroberge parallelalgorithmongpuforwirelesssensordataacquisitionusingateamofunmannedaerialvehicles AT mohammedtarbouchi parallelalgorithmongpuforwirelesssensordataacquisitionusingateamofunmannedaerialvehicles |