[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Minimizing age of information in multi-UAV-assisted IoT networks: a graph theoretical approach

  • Original Paper
  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

This paper discusses trajectory planning for multiple UAVs in IoT networks to minimize the average Age of Information (AoI). First, using a graph theoretical approach, we present an explicit formula for the average AoI in both Hamiltonian and non-Hamiltonian cycles. These relations tie the upper bound of average AoI with Traveling Salesman Problem (TSP) as well as provide a mechanism to improve AoI in a given flight trajectory by means of creating new cycles around a specific set of IoT devices. Further, we give a lower bound for the average AoI. Secondly, we propose a heuristic algorithm for trajectory planning based on unsupervised clustering. The IoT networks are divided into k subsets and for each of them, a tour is found by a greedy algorithm. Then, the tours are merged together to find the best set of tours for each UAV in terms of average AoI. Moreover, some optimizations are applied on each flight trajectory to improve the average AoI. The evaluation results show that our scheme is efficient compared to both the baseline greedy approach and TSP optimal tour.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

References

  1. 3GPP. (2018). Enhancement for Unmaned Aerial Vehicles (UAVs) Technical Report 22.829. ETSI.

  2. Ergezer, H., & Leblebicioğlu, K. (2014). 3D path planning for multiple uavs for maximum information collection. Journal of Intelligent and Robotic Systems, 73(1), 737–762.

    Article  Google Scholar 

  3. Yang, Z., Pan, C., Shikh-Bahaei, M., Wei, X., Chen, M., Elkashlan, M., & Nallanathan, A. (2018). Joint altitude, beamwidth, location, and bandwidth optimization for UAV-enabled communications. IEEE Communications Letters, 22(8), 1716–1719.

    Article  Google Scholar 

  4. Tong, P., Liu, J., Wang, X., Bai, B. & Dai, H. (2020). Deep reinforcement learning for efficient data collection in UAV-aided Internet of things. In 2020 IEEE International Conference on Communications Workshops (ICC Workshops), pp. 1–6. IEEE.

  5. Yi, M., Wang, X., Liu, J., Zhang, Y. & Bai, B. (2020). Deep reinforcement learning for fresh data collection in UAV-assisted IoT networks. In IEEE INFOCOM 2020-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 716–721. IEEE.

  6. Kaul, S., Gruteser, M., Rai, V. & Kenney, J. (2011). Minimizing age of information in vehicular networks. In 2011 8th Annual IEEE communications society conference on sensor, mesh and ad hoc communications and networks, pp. 350–358. IEEE.

  7. Zhou, C., He, H., Yang, P., Lyu, F., Wu, W., Cheng, N. & Shen, X. (2019). Deep RL-based trajectory planning for aoi minimization in UAV-assisted IoT. In 2019 11th International Conference on Wireless Communications and Signal Processing (WCSP), pp. 1–6. IEEE.

  8. Hu, H., Xiong, K., Qu, G., Ni, Q., Fan, P., & Letaief, K. B. (2020). AoI-minimal trajectory planning and data collection in UAV-assisted wireless powered IoT networks. IEEE Internet of Things Journal, 8(2), 1211–1223.

    Article  Google Scholar 

  9. Abd-Elmagid, M. A., & Dhillon, H. S. (2018). Average peak age-of-information minimization in UAV-assisted IoT networks. IEEE Transactions on Vehicular Technology, 68(2), 2003–2008.

    Article  Google Scholar 

  10. Sun, M., Xiaodong, X., Qin, X., & Zhang, P. (2021). AoI-energy-aware UAV-assisted data collection for IoT networks: A deep reinforcement learning method. IEEE Internet of Things Journal, 8(24), 17275–17289.

    Article  Google Scholar 

  11. Samir, M., Assi, C., Sharafeddine, S., & Ghrayeb, A. (2020). Online altitude control and scheduling policy for minimizing AoI in UAV-assisted IoT wireless networks. IEEE Transactions on Mobile Computing, 21(7), 2493–2505.

    Google Scholar 

  12. Eldeeb, E., de Souza Sant’Ana, J. M., Echevarría Pérez, D., Shehab, M., Mahmood, N. H., & Alves, H. (2022). Multi-UAV path learning for age and power optimization in IoT with uav battery recharge. IEEE Transactions on Vehicular Technology, 72(4), 5356–5360.

    Article  Google Scholar 

  13. Abedin, S. F., Munir, M. S., Tran, N. H., Han, Z., & Hong, C. S. (2020). Data freshness and energy-efficient UAV navigation optimization: A deep reinforcement learning approach. IEEE Transactions on Intelligent Transportation Systems, 22(9), 5994–6006.

    Article  Google Scholar 

  14. Garraffa, M., Bekhti, M., Létocart, L., Achir, N. and Boussetta, K. (2018). Drones path planning for WSN data gathering: A column generation heuristic approach. In 2018 IEEE Wireless Communications and Networking Conference (WCNC), pp. 1–6. IEEE.

  15. Misevicius, A., Blazinskas, A. (2011). Combining 2-opt, 3-opt and 4-opt with k-swap-kick perturbations for the traveling salesman problem. In 17th International Conference on Information and Software Technologies.

  16. Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    Article  MathSciNet  Google Scholar 

  17. Qiang, D., Emelianenko, M., & Lili, J. (2006). Convergence of the Lloyd algorithm for computing centroidal voronoi tessellations. SIAM Journal on Numerical Analysis, 44(1), 102–119.

    Article  MathSciNet  Google Scholar 

  18. Rahimi, O. (2023). Minimizing Age of Informaion. https://github.com/omidrahimi1375/Minimizing-Age-of-Information-in-multi-UAV-assisted-IoT-networks-a-Graph-Theoretical-Approach.git.

  19. Reinelt, G. (1991). TSPLIB-A traveling salesman problem library. ORSA Journal on Computing, 3(4), 376–384.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, Tarbiat Modares University, Jalale Al Ahmad, Tehran, 14115-111, Iran

    Omid Rahimi & Alireza Shafieinejad

Authors
  1. Omid Rahimi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alireza Shafieinejad
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alireza Shafieinejad.

Ethics declarations

Conflict of interest

Omid Rahimi, as the first author, declares that he has no conflict of interest. Further, Alireza Shafieinejad, as the second author, declares that he has no conflict of interest.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rahimi, O., Shafieinejad, A. Minimizing age of information in multi-UAV-assisted IoT networks: a graph theoretical approach. Wireless Netw 30, 533–555 (2024). https://doi.org/10.1007/s11276-023-03492-5

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-023-03492-5

Keywords

Search

Navigation