We consider Internet of Things (IoT) sensors deployed inside an area to be monitored. Not all the sensors are connected via single-hop to the depot that requires the data. Inversely, a multi-hop implementation can bring the network connectivity at risk because the sensors closer to the depot consume more energy when relaying the aggregated data. Therefore, a viable solution is to use a drone that collects the data from the sensors flying close to them. A drone moves faster than a ground robot, and it is not affected by eventual obstacles on the terrain, but it is constrained in both the energy (when flying and hovering), and the storage (when collecting data). Moreover, a drone cannot transmit the collected data to the cloud because the Internet connectivity can be absent. Therefore, the drone needs to select a subset of sensors whose data is the most relevant to be acquired. Such a relevance is modeled by assigning a reward to that data based on its freshness and suitability. We present an optimization problem called Single-drone Data-collection Maximization Problem (SDMP) whose objective is to plan a drone’s mission aimed at maximizing the overall reward from the collected data, and such that the mission’s energy cost and the total collected data are within the energy and storage limits. Since SDMP is NP-hard, we give an optimal Integer Linear Programming formulation, and also devise an approximation and two time-efficient heuristic algorithms. Finally, we test our algorithms on randomly generated synthetic data.

Optimal and Heuristic Algorithms for Data Collection by Using an Energy- and Storage-Constrained Drone / Francesco Betti Sorbelli, Alfredo Navarra, Lorenzo Palazzetti, Cristina M Pinotti, Giuseppe Prencipe. - ELETTRONICO. - 13707:(2022), pp. 0-0. (Intervento presentato al convegno 18th International Symposium on Algorithmics of Wireless Networks, ALGOSENSORS 2022) [10.1007/978-3-031-22050-0_2].

Optimal and Heuristic Algorithms for Data Collection by Using an Energy- and Storage-Constrained Drone

Francesco Betti Sorbelli;Alfredo Navarra;Lorenzo Palazzetti
;
2022

Abstract

We consider Internet of Things (IoT) sensors deployed inside an area to be monitored. Not all the sensors are connected via single-hop to the depot that requires the data. Inversely, a multi-hop implementation can bring the network connectivity at risk because the sensors closer to the depot consume more energy when relaying the aggregated data. Therefore, a viable solution is to use a drone that collects the data from the sensors flying close to them. A drone moves faster than a ground robot, and it is not affected by eventual obstacles on the terrain, but it is constrained in both the energy (when flying and hovering), and the storage (when collecting data). Moreover, a drone cannot transmit the collected data to the cloud because the Internet connectivity can be absent. Therefore, the drone needs to select a subset of sensors whose data is the most relevant to be acquired. Such a relevance is modeled by assigning a reward to that data based on its freshness and suitability. We present an optimization problem called Single-drone Data-collection Maximization Problem (SDMP) whose objective is to plan a drone’s mission aimed at maximizing the overall reward from the collected data, and such that the mission’s energy cost and the total collected data are within the energy and storage limits. Since SDMP is NP-hard, we give an optimal Integer Linear Programming formulation, and also devise an approximation and two time-efficient heuristic algorithms. Finally, we test our algorithms on randomly generated synthetic data.
2022
Algorithmics of Wireless Networks: 18th International Symposium on Algorithmics of Wireless Networks, ALGOSENSORS 2022, Potsdam, Germany, September 8–9, 2022, Proceedings
18th International Symposium on Algorithmics of Wireless Networks, ALGOSENSORS 2022
Francesco Betti Sorbelli, Alfredo Navarra, Lorenzo Palazzetti, Cristina M Pinotti, Giuseppe Prencipe
File in questo prodotto:
File Dimensione Formato  
ALGOSENSORS_2022___Data_Collection_with_Drones.pdf

Accesso chiuso

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Tutti i diritti riservati
Dimensione 486.67 kB
Formato Adobe PDF
486.67 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1347490
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 2
social impact