A Study Of The Maximum Sensing Data Collection Routing Problem By Multiple UAVS With Sensing Idleness And Latency Constraints

Rozaliya, Baiq Zuyyina Hilyatur (2021) A Study Of The Maximum Sensing Data Collection Routing Problem By Multiple UAVS With Sensing Idleness And Latency Constraints. Masters thesis, Institut Teknologi Sepuluh Nopember.

[thumbnail of 05211950010025-Master_Thesis.pdf] Text
05211950010025-Master_Thesis.pdf - Accepted Version
Restricted to Repository staff only until 1 October 2023.

Download (1MB) | Request a copy

Abstract

We discuss a multi-UAV surveillance routing problem that routes a UAV fleet from a base station (i.e., depot) to repeatedly collect data from sensing locations during a specific planning horizon. The data in a sensing area is generated and ready to be collected periodically in a store-and-forward fashion. A UAV has to pass through some nodes within the communication range to collect data from a sensing location. It then carries the data and wirelessly transfers it to another UAV as long as that UAV is located within its communication range. We seek the maximum collected data that the base station can receive during the planning horizon. Specifically, we calculate the optimal flight paths for UAVs over the space and time necessary to transfer the maximum amount of collected data. Furthermore, it is hoped that the idleness and latency, defined as the maximum length of time between consecutive data collected from a sensing location and the length of time (i.e., freshness) required for the data traveling from a sensing location to the base station, respectively, necessary to satisfy the given upper bounds. We proposed an integer programming model on a time-space network to track how the generated surveillance data is collected and transferred. Implementation of the model is provided and compared to an uncooperative data transport model. Each UAV has to transfer the data individually to demonstrate the applicability of the proposed model and possible extensions. The results show that the cooperative data transport model can transfer more collected data with less latency than the uncooperative data transport model. Although a mathematical model can be used to calculate an optimal solution, it is quite time-consuming. To calculate a good solution in a shorter time, we proposed a heuristic algorithm that evenly distributes UAVs on a short Hamiltonian cycle connecting the depot and all sensing locations. Computational experiments indicate that the proposed algorithm calculates good solutions and can deal with larger cases but still has room to improve in terms of its solution quality.
===============================================================================================
Kami membahas masalah perutean pengawasan multi-UAV yang mengarahkan armada UAV dari stasiun pangkalan (yaitu, depot) untuk mengumpulkan data berulang kali dari lokasi penginderaan selama cakrawala perencanaan tertentu. Data di area penginderaan dihasilkan dan siap untuk dikumpulkan secara berkala dalam mode store-and-forward. Sebuah UAV harus melewati beberapa node dalam jangkauan komunikasi untuk mengumpulkan data dari lokasi penginderaan. Kemudian membawa data dan secara nirkabel mentransfernya ke UAV lain selama UAV tersebut berada dalam jangkauan komunikasinya. Kami mencari data yang dikumpulkan maksimum yang dapat diterima stasiun pangkalan selama cakrawala perencanaan. Secara khusus, kami menghitung jalur penerbangan optimal untuk UAV di atas ruang dan waktu yang diperlukan untuk mentransfer jumlah maksimum data yang dikumpulkan. Selanjutnya, diharapkan bahwa idleness dan latency, yang didefinisikan sebagai jangka waktu maksimum antara data berurutan yang dikumpulkan dari lokasi penginderaan dan lamanya waktu (yaitu, kesegaran) yang diperlukan untuk perjalanan data dari lokasi penginderaan ke stasiun pangkalan, masing-masing, diperlukan untuk memenuhi batas atas yang diberikan. Kami mengusulkan model pemrograman integer pada jaringan ruang-waktu untuk melacak bagaimana data pengawasan yang dihasilkan dikumpulkan dan ditransfer. Implementasi model disediakan dan dibandingkan dengan model transportasi data yang tidak kooperatif. Setiap UAV harus mentransfer data secara individual untuk menunjukkan penerapan model yang diusulkan dan kemungkinan ekstensi. Hasilnya menunjukkan bahwa model transportasi data kooperatif dapat mentransfer lebih banyak data yang dikumpulkan dengan latensi yang lebih sedikit daripada model transportasi data yang tidak kooperatif. Meskipun model matematika dapat digunakan untuk menghitung solusi optimal, itu cukup memakan waktu. Untuk menghitung solusi yang baik dalam waktu yang lebih singkat, kami mengusulkan algoritma heuristik yang mendistribusikan UAV secara merata pada siklus Hamiltonian pendek yang menghubungkan depot dan semua lokasi penginderaan. Eksperimen komputasi menunjukkan bahwa algoritma yang diusulkan menghitung solusi yang baik dan dapat menangani kasus yang lebih besar tetapi masih memiliki ruang untuk ditingkatkan dalam hal kualitas solusinya.

Item Type: Thesis (Masters)
Uncontrolled Keywords: Integer Programming, Time-Space Network, Multi-UAV surveillance routing, idleness, latency, Pesawat Tanpa Awak, Waktu Tunggu, Latensi
Subjects: T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming
T Technology > T Technology (General) > T57.74 Linear programming
T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions: Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 59101-(S2) Master Thesis
Depositing User: Baiq Zuyyina Hilyatur Rozaliya
Date Deposited: 24 Aug 2021 04:57
Last Modified: 24 Aug 2021 04:57
URI: http://repository.its.ac.id/id/eprint/88104

Actions (login required)

View Item View Item