Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network - Drones and Autonomous Vehicles - Full-Text HTML

<!DOCTYPE html> <html class="no-js" lang="en"> <head> <meta charset="utf-8" /> <meta http-equiv="x-ua-compatible" content="ie=edge" /> <title>Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network - Drones and Autonomous Vehicles - Full-Text HTML - SCIEPublish</title> <meta name="keywords" content="SCIE Publishing, SCIEPublish, open access, fast publication" /> <meta name="description" content="SCIEPublish is an international open-access journal publishing service provider run by SCIE Publishing Limited, dedicated to supporting and inspiring scientists or institutions/societies who aspire to publish high-quality journals." /> <meta name="viewport" content="width=device-width,user-scalable=no,initial-scale=1.0,maximum-scale=1.0,minimum-scale=1.0"> <meta name="title" content="Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network"> <link rel="image_src" href="https://www.sciepublish.com/uploads/2024/05/28/17168749452jfd.jpg"> <meta name="dc.title" content="Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network"> <meta name="dc.creator" content="Ramkumar Ganapathy"> <meta name="dc.creator" content="Christopher Thron"> <meta name="dc.type" content="Article"> <meta name="dc.source" content="Drones and Autonomous Vehicles 2024, Vol. 1, Page 10007"> <meta name="dc.date" content="2024-06-12"> <meta name="dc.identifier" content="10.35534/dav.2024.10007"> <meta name="dc.publisher" content="SCIEPublish"> <meta name="dc.rights" content="http://creativecommons.org/licenses/by/4.0/"> <meta name="dc.format" content="application/pdf"> <meta name="dc.language" content="en"> <meta name="dc.description" content="We consider a remote sensing system in which fixed sensors are placed in a region, and a single drone flies over the region to collect information from cluster heads. We assume that the drone has a fixed maximum range and that the energy consumption for information transmission from the cluster heads increases with distance according to a power law. Given these assumptions, we derive local optimum conditions for a drone path that either minimizes the total or maximum energy required by the cluster heads to transmit information to the drone. We show how a homotopy approach can produce a family of solutions for different drone path lengths so that a locally optimal solution can be found for any drone range. We implement the homotopy solution in Python and demonstrate the tradeoff between drone range and cluster head power consumption for several geometries. Execution time is sufficiently rapid for the computation to be performed in real time so that the drone path can be recalculated on the fly. The solution is shown to be globally optimal for sufficiently long drone path lengths. A proof of concept implementation in Python is available on GitHub. For future work, we indicate how the solution can be modified to accommodate moving sensors."> <meta name="dc.subject" content="Wireless sensor network"> <meta name="dc.subject" content="Drone"> <meta name="dc.subject" content="Path planning"> <meta name="dc.subject" content="Information collection"> <meta name="dc.subject" content="Power-efficient"> <meta name="dc.subject" content="Extended lifetime"> <meta name="dc.subject" content="Optimization"> <meta name="prism.issn" content="2958-7689"> <meta name="prism.publicationName" content="Drones and Autonomous Vehicles"> <meta name="prism.publicationDate" content="2024-06-12"> <meta name="prism.volume" content="1"> <meta name="prism.number" content="3"> <meta name="prism.section" content="Article"> <meta name="prism.startingPage" content="10007"> <meta name="citation_issn" content="2958-7689"> <meta name="citation_journal_title" content="Drones and Autonomous Vehicles"> <meta name="citation_publisher" content="SCIEPublish"> <meta name="citation_title" content="Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network"> <meta name="citation_publication_date" content="2024/06"> <meta name="citation_online_date" content="2024/06/12"> <meta name="citation_volume" content="1"> <meta name="citation_issue" content="3"> <meta name="citation_firstpage" content="10007"> <meta name="citation_author" content="Ganapathy, Ramkumar "> <meta name="citation_author" content="Thron, Christopher "> <meta name="citation_doi" content="10.35534/dav.2024.10007"> <meta name="citation_abstract_html_url" content="https://www.sciepublish.com/article/pii/209"> <meta name="citation_pdf_url" content="https://www.sciepublish.com/index/article/view_full_text/id/209"> <link rel="alternate" type="application/pdf" title="PDF Full-Text" href="https://www.sciepublish.com/index/article/view_full_text/id/209"> <meta name="fulltext_pdf" content="https://www.sciepublish.com/index/article/view_full_text/id/209"> <link rel="alternate" type="text/html" title="HTML Full-Text" href="https://www.sciepublish.com/article/pii/209"> <meta name="citation_fulltext_html_url" content="https://www.sciepublish.com/article/pii/209"> <meta name="fulltext_html" content="https://www.sciepublish.com/article/pii/209"> <meta property="og:site_name" content="SCIEPUBLISH" /> <meta property="og:type" content="Article" /> <meta property="og:url" content="https://www.sciepublish.com/article/pii/209" /> <meta property="og:title" content="Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network" /> <meta property="og:description" content="We consider a remote sensing system in which fixed sensors are placed in a region, and a single drone flies over the region to collect information from cluster heads. We assume that the drone has a fixed maximum range and that the energy consumption for information transmission from the cluster heads increases with distance according to a power law. Given these assumptions, we derive local optimum conditions for a drone path that either minimizes the total or maximum energy required by the cluster heads to transmit information to the drone. We show how a homotopy approach can produce a family of solutions for different drone path lengths so that a locally optimal solution can be found for any drone range. We implement the homotopy solution in Python and demonstrate the tradeoff between drone range and cluster head power consumption for several geometries. Execution time is sufficiently rapid for the computation to be performed in real time so that the drone path can be recalculated on the fly. The solution is shown to be globally optimal for sufficiently long drone path lengths. A proof of concept implementation in Python is available on GitHub. For future work, we indicate how the solution can be modified to accommodate moving sensors." /> <meta property="og:image" content="https://www.sciepublish.com/uploads/2024/06/12/0fe3c2eb112e8259bf5b994c458cfd90.png" /> <meta property="og:image:secure_url" content="https://www.sciepublish.com/uploads/2024/06/12/0fe3c2eb112e8259bf5b994c458cfd90.png" /> <meta name="twitter:site" content="@sciepublish"> <meta name="twitter:image" content="https://www.sciepublish.com/uploads/2024/06/12/0fe3c2eb112e8259bf5b994c458cfd90.png" /> <meta name="twitter:card" content="summary_large_image"> <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" /> <link rel="stylesheet" href="/static/css/bootstrap.css" /> <link rel="stylesheet" href="/static/font/bootstrap-icons.css"> <link rel="stylesheet" href="/static/css/lightbox.css" /> <link rel="stylesheet" href="/static/css/theme.css?74" /> <link rel="stylesheet" href="/static/css/common.css?90" /> <link rel="stylesheet" href="/static/css/ckeditorStyle.css?2" /> <link rel="stylesheet" href="/static/css/select-mania.min.css" /> <script src="/static/js/jquery-3.7.1.min.js"></script> <script src="/static/js/lightbox.js"></script> <script src="/static/js/bootstrap.bundle.min.js"></script> <script src="/static/js/select-mania.js"></script> <link rel="stylesheet" href="/static/katex/katex.min.css"> <script src="/static/katex/katex.min.js"></script> <script src="/static/katex/contrib/auto-render.min.js"></script> <style> .katex{ font-size: 1.5rem!important; } .tooltip-inner{ /* min-width: 40rem; */ width: auto; max-width: 40rem; padding: 1rem; text-align: left; } .tooltip-inner .html-fig_img, .tooltip-inner .html-figpopup-table { padding: 1.5rem 1.5rem 1rem; background-color: #FFFeFa; border: 1px solid #e9ded8; border-radius: 5px; margin: 1.5rem 0 2rem; } .tooltip-inner .html-figpopup-table{margin-top:1rem;} .tooltip-inner .html-fig_img img, .tooltip-inner .html-figpopup-table img{ width: 100%; } .centered-div { max-width: 60%; position: fixed; top: 50%; left: 50%; transform: translate(-50%, -50%); z-index: 1000; background-color: rgba(255, 255, 255, 1); padding: 20px; border: 1px solid #ccc; box-shadow: 0 2px 5px rgba(0,0,0,0.2); } .topic-collection a{ display: block; font-size: .85rem; line-height: 1.5; } topic-collection h6.article-menu-collapse{ font-weight: 700; } .popover-content { width: 500px; } .popover { max-width:95%; } </style> </head> <body class="header-no-fixed"> <header> <nav class="navbar navbar-expand-lg navbar-light my-body-container"> <div class="navbar-left"> <a href="/" class="uk-navbar-item" alt="Back to the homepage"> <svg xmlns="http://www.w3.org/2000/svg" class="navbar-logo" xml:space="preserve" version="1.0" viewBox="0 0 5.08 1.933"> <path d="M1.021 1.245a.29.29 0 0 1-.211-.054l-.027-.023-.003-.003.056-.066.003.004a.3.3 0 0 0 .043.033.2.2 0 0 0 .128.027l.024-.007.019-.01a.07.07 0 0 0 .022-.032.1.1 0 0 0 0-.036l-.004-.014a.1.1 0 0 0-.016-.02.1.1 0 0 0-.027-.017L.994 1.01.919.98a.3.3 0 0 1-.076-.05.14.14 0 0 1-.034-.067.2.2 0 0 1 0-.06.13.13 0 0 1 .027-.056.2.2 0 0 1 .049-.041A.2.2 0 0 1 .95.683a.3.3 0 0 1 .07-.001.2.2 0 0 1 .06.017.3.3 0 0 1 .075.05l.003.003-.05.061L1.103.81a.2.2 0 0 0-.053-.034.2.2 0 0 0-.063-.013.1.1 0 0 0-.046.008L.925.78a.06.06 0 0 0-.023.047l.001.015.006.012a.1.1 0 0 0 .018.02.1.1 0 0 0 .027.017L.97.899l.016.006.074.032a.3.3 0 0 1 .058.033.14.14 0 0 1 .051.08.2.2 0 0 1 0 .07.15.15 0 0 1-.048.081.2.2 0 0 1-.062.035zm.527-.002a.24.24 0 0 1-.1 0 .23.23 0 0 1-.125-.069.2.2 0 0 1-.051-.089.3.3 0 0 1-.019-.119.4.4 0 0 1 .02-.12.3.3 0 0 1 .052-.09.23.23 0 0 1 .176-.076.3.3 0 0 1 .064.01.3.3 0 0 1 .053.025.2.2 0 0 1 .04.034l.002.003-.052.061L1.605.81A.2.2 0 0 0 1.56.776a.2.2 0 0 0-.037-.012.15.15 0 0 0-.082.013.13.13 0 0 0-.049.039l-.018.029a.2.2 0 0 0-.022.073.4.4 0 0 0 .002.104.2.2 0 0 0 .014.05.2.2 0 0 0 .023.04.14.14 0 0 0 .066.047.15.15 0 0 0 .107-.009l.028-.017.025-.023.003-.004.051.06-.002.003a.3.3 0 0 1-.076.059.2.2 0 0 1-.045.015m.314-.004h-.09V.69h.095v.549zm.485 0h-.331V.69h.328v.08H2.11v.141h.198v.082H2.11v.165h.242v.08zm.215 0h-.09V.69h.169a.4.4 0 0 1 .083.008L2.76.71l.031.016a.13.13 0 0 1 .044.053q.009.015.012.036a.22.22 0 0 1-.012.121l-.018.03a.176.176 0 0 1-.09.057.3.3 0 0 1-.084.011h-.076v.205zm.005-.472v.19h.068a.2.2 0 0 0 .056-.006.1.1 0 0 0 .038-.018.1.1 0 0 0 .022-.031.1.1 0 0 0 .007-.045l-.003-.03a.07.07 0 0 0-.028-.04L2.703.776 2.671.769 2.633.767zm.539.48a.2.2 0 0 1-.067-.003.1.1 0 0 1-.075-.07.3.3 0 0 1-.013-.09V.827h.093v.248a.3.3 0 0 0 .007.055l.008.017.012.012.016.007.02.002a.1.1 0 0 0 .033-.006.1.1 0 0 0 .03-.019.2.2 0 0 0 .03-.032V.826h.093v.413h-.078l-.006-.057a.2.2 0 0 1-.078.057zm.548-.002-.034.003-.03-.003-.029-.01A.2.2 0 0 1 3.51 1.2l-.007.039h-.075V.645h.093q0 .11-.002.219l.01-.008A.2.2 0 0 1 3.59.823a.2.2 0 0 1 .043-.007.2.2 0 0 1 .07.015.15.15 0 0 1 .07.074.2.2 0 0 1 .022.076.4.4 0 0 1 0 .095.3.3 0 0 1-.029.082.2.2 0 0 1-.079.075zm-.07-.077a.1.1 0 0 0 .046-.002.1.1 0 0 0 .043-.032l.015-.028a.2.2 0 0 0 .01-.036.3.3 0 0 0-.006-.114A.1.1 0 0 0 3.68.93.07.07 0 0 0 3.64.9.1.1 0 0 0 3.59.899l-.023.008-.023.015-.023.02v.193a.2.2 0 0 0 .043.027zm.424.08h-.015a.1.1 0 0 1-.051-.013l-.017-.016-.011-.022-.007-.026-.002-.031V.645h.093v.5L4 1.16l.003.004.003.003.008.002h.008l.005-.001h.004l.013.071-.004.002-.009.002zm.22-.01H4.14V.827h.093v.413zm-.026-.48L4.187.76q-.009 0-.016-.002L4.157.753a.05.05 0 0 1-.02-.02.1.1 0 0 1-.008-.027L4.13.69a.05.05 0 0 1 .027-.032L4.17.653a.07.07 0 0 1 .045.005.05.05 0 0 1 .03.048.1.1 0 0 1-.009.028.1.1 0 0 1-.02.019zm.315.488a.25.25 0 0 1-.19-.054l-.004-.003.045-.062.004.003a.3.3 0 0 0 .053.034.13.13 0 0 0 .058.012l.022-.002.016-.005.013-.008.009-.01a.05.05 0 0 0 .007-.025q0-.006-.002-.012l-.005-.01-.008-.009-.011-.008-.028-.014-.016-.006-.017-.007a.4.4 0 0 1-.079-.041.1.1 0 0 1-.028-.034L4.348.964 4.345.939a.12.12 0 0 1 .023-.07.1.1 0 0 1 .038-.033A.2.2 0 0 1 4.46.82a.2.2 0 0 1 .13.022l.037.024.003.003-.045.059-.003-.003A.2.2 0 0 0 4.54.9a.1.1 0 0 0-.065-.008.1.1 0 0 0-.027.012l-.007.01a.04.04 0 0 0-.007.022q0 .006.002.01l.005.01a.1.1 0 0 0 .017.015l.027.013.016.006.016.006.063.028.019.013a.1.1 0 0 1 .029.035l.008.023a.13.13 0 0 1-.008.077.1.1 0 0 1-.03.04.14.14 0 0 1-.05.027zm.307-.007h-.088V.645h.092q0 .115-.002.229a.3.3 0 0 1 .05-.038.2.2 0 0 1 .048-.017.2.2 0 0 1 .068.002.1.1 0 0 1 .057.038q.01.014.018.033A.314.314 0 0 1 5.08.98v.258h-.093V.99L4.985.96 4.98.936 4.97.92 4.96.907 4.943.9a.1.1 0 0 0-.037 0 .1.1 0 0 0-.03.011l-.016.01-.032.03v.288z" /> <path d="M1.844 1.377a.97.97 0 0 1-.878.563A.963.963 0 0 1 0 .974.964.964 0 0 1 .966.007a.96.96 0 0 1 .865.536l-.048.024A.92.92 0 0 0 .966.062a.91.91 0 0 0-.912.912.91.91 0 0 0 .912.912.91.91 0 0 0 .83-.532z" class="logo-circle" /> </svg> </a> </div> <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <div class="btn-menu"> <span></span> <span></span> <span></span> </div> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <div class="nav-form-search"> <form class="form-search" method="get" action="/index/search/index.html"> <input class="search-input" type="text" name="search" placeholder="What are you looking for?" autofocus /> <button type="submit">Search</button> </form> </div> <ul class="navbar-nav uk-navbar-nav"> <li class="nav-item "> <a class="nav-link" href="/">Home</a> </li> <li class="nav-item "> <a class="nav-link" href="/About_SCIEPublish">About</a> </li> <li class="nav-item uk-active"> <a class="nav-link" href="/index/journals/index">Journals</a> </li> <li class="nav-item "> <a class="nav-link" href="/news/list">News</a> </li> </ul> <a class="js-navbar-toggle sc-icon-button sc-transition" title="Search" href="#"> <svg xmlns="http://www.w3.org/2000/svg" width="20" height="20" fill="currentColor" class="bi bi-search" viewBox="0 0 16 16"> <path d="M11.742 10.344a6.5 6.5 0 1 0-1.397 1.398h-.001c.03.04.062.078.098.115l3.85 3.85a1 1 0 0 0 1.415-1.414l-3.85-3.85a1.007 1.007 0 0 0-.115-.1zM12 6.5a5.5 5.5 0 1 1-11 0 5.5 5.5 0 0 1 11 0z"/> </svg> <svg xmlns="http://www.w3.org/2000/svg" width="20" height="20" fill="currentColor" class="bi bi-x-lg" viewBox="0 0 16 16"> <path d="M2.146 2.854a.5.5 0 1 1 .708-.708L8 7.293l5.146-5.147a.5.5 0 0 1 .708.708L8.707 8l5.147 5.146a.5.5 0 0 1-.708.708L8 8.707l-5.146 5.147a.5.5 0 0 1-.708-.708L7.293 8 2.146 2.854Z"/> </svg> </a> <a class="uk-button sc-transition" href="/my/submitting">Publish with us</a> <a class="text-login" title="Sign in" href="/index/user/login.html"> Sign in </a> </div> </nav> </header> <section class="breadcrumbs pt-3"> <div class="my-body-container"> <nav aria-label="breadcrumb"> <ol class="breadcrumb p-0 mb-0"> <li class="breadcrumb-item" title="Home"> <a href="/">Home</a> <svg xmlns="http://www.w3.org/2000/svg" width="12" height="12" fill="currentColor" class="bi bi-chevron-right ml-1 mr-1" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M4.646 1.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1 0 .708l-6 6a.5.5 0 0 1-.708-.708L10.293 8 4.646 2.354a.5.5 0 0 1 0-.708z"/> </svg> </li> <li class="breadcrumb-item" title="Journals"> <a href="/index/journals/index">Journals</a> <svg xmlns="http://www.w3.org/2000/svg" width="12" height="12" fill="currentColor" class="bi bi-chevron-right ml-1 mr-1" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M4.646 1.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1 0 .708l-6 6a.5.5 0 0 1-.708-.708L10.293 8 4.646 2.354a.5.5 0 0 1 0-.708z"/> </svg> </li> <li class="breadcrumb-item" title="dav"> <a href="/journals/dav">dav</a> <svg xmlns="http://www.w3.org/2000/svg" width="12" height="12" fill="currentColor" class="bi bi-chevron-right ml-1 mr-1" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M4.646 1.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1 0 .708l-6 6a.5.5 0 0 1-.708-.708L10.293 8 4.646 2.354a.5.5 0 0 1 0-.708z"/> </svg> </li> <li class="breadcrumb-item" title="Volume 1"> <a href="/journals/dav/roll/1">Volume 1</a> <svg xmlns="http://www.w3.org/2000/svg" width="12" height="12" fill="currentColor" class="bi bi-chevron-right ml-1 mr-1" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M4.646 1.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1 0 .708l-6 6a.5.5 0 0 1-.708-.708L10.293 8 4.646 2.354a.5.5 0 0 1 0-.708z"/> </svg> </li> <li class="breadcrumb-item" title="Issue 3"> <a href="/journals/dav/roll/1/3">Issue 3</a> <svg xmlns="http://www.w3.org/2000/svg" width="12" height="12" fill="currentColor" class="bi bi-chevron-right ml-1 mr-1" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M4.646 1.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1 0 .708l-6 6a.5.5 0 0 1-.708-.708L10.293 8 4.646 2.354a.5.5 0 0 1 0-.708z"/> </svg> </li> <li class="breadcrumb-item active" aria-current="page" title='10.35534/dav.2024.10007'>10.35534/dav.2024.10007</li> </ol> </nav> </div> </section> <section class="fixed-title"> <div class="my-body-container d-flex align-items-center border-bottom border-dark pt-2 pb-2"> <div class="item-img"> <a class="d-flex align-items-center" href="/journals/dav"> <div class="cover-img"> <img src="/uploads/2024/05/28/17168749452jfd.jpg" alt="Drones and Autonomous Vehicles-logo" /> </div> <h6 class="flex-grow-1 pl-2" title="Drones and Autonomous Vehicles">Drones and Autonomous Vehicles</h6> </a> </div> <h2 class="journals-text" title="Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network">Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network</h2> </div> </section> <section class="page-items mt-3"> <div class="d-flex my-body-container border-dark border-top pt-4 collapse show" id="rightCollapse"> <div class="left-items-260 mr-3"> <div class="left-content d-flex"> <div class="left-content-item"> <div class="item-img"> <a class="d-flex align-items-center" href="/journals/dav"> <div class="cover-img"> <img src="/uploads/2024/05/28/17168749452jfd.jpg" alt="Drones and Autonomous Vehicles-logo" /> </div> <h6 class="flex-grow-1 pl-2">Drones and Autonomous Vehicles</h6> </a> </div> <div class="btn-bottom"> <a class="sc-btn-submit d-flex align-items-center justify-content-center mt-3" href="/my/submitting/journal/27"> Submit to DAV <svg xmlns="http://www.w3.org/2000/svg" width="12" height="12" fill="currentColor" class="bi bi-chevron-double-right ml-1" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M3.646 1.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1 0 .708l-6 6a.5.5 0 0 1-.708-.708L9.293 8 3.646 2.354a.5.5 0 0 1 0-.708z"></path> <path fill-rule="evenodd" d="M7.646 1.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1 0 .708l-6 6a.5.5 0 0 1-.708-.708L13.293 8 7.646 2.354a.5.5 0 0 1 0-.708z"></path> </svg> </a> <a class="sc-cite-modal sc-btn-submit d-flex align-items-center justify-content-center mt-2" href="/index/article/download_article/id/209.html"> <span>Download PDF</span> </a>  <div class="sc-cite-modal sc-btn-submit d-flex align-items-center justify-content-center border-0 mt-2" data-toggle="modal" data-target="#citeModal"> Cite This Article </div> </div>  <div class="article-menu-collapse d-flex justify-content-between mt-2"> <h6 class="mb-0 d-flex align-items-center">Contents</h6> <div class="btn-collapse pt-2 pb-2 pl-2" data-toggle="collapse" data-target="#articleMenuCollapse" aria-expanded="true" aria-controls="articleMenuCollapse"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-chevron-up" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M7.646 4.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1-.708.708L8 5.707l-5.646 5.647a.5.5 0 0 1-.708-.708l6-6z"/> </svg> </div> </div> <div class="articleMenuCollapse-column p-0" id="articleMenuCollapse"> <div class="menu pt-2"> <div class="list-group" id="article-menu-float"> <a class="list-group-item list-group-item-action" href="#link-introduction">1. Introduction</a> <a class="list-group-item list-group-item-action" href="#link-materials-and-methods">2. Methodology</a> <a class="list-group-item list-group-item-action" href="#link-theory-calculation">3. Results</a> <a class="list-group-item list-group-item-action" href="#link-results">4. Conclusions</a> <a class="list-group-item list-group-item-action" href="#link-discussion">5. Future Work</a> <a class="list-group-item list-group-item-action" href="#link-appendix">Appendix A. Python Implementation</a> <a class="list-group-item list-group-item-action" href="#link-appendix-b">Appendix B. Mathematical Proof of Global Optimality</a> <a class="list-group-item list-group-item-action" href="#link-acknowledgments">Acknowledgments</a> <a class="list-group-item list-group-item-action" href="#link-author-contributions">Author Contributions</a> <a class="list-group-item list-group-item-action" href="#link-ethics-statement">Ethics Statement</a> <a class="list-group-item list-group-item-action" href="#link-informed-consent-statement">Informed Consent Statement</a> <a class="list-group-item list-group-item-action" href="#link-funding">Funding</a> <a class="list-group-item list-group-item-action" href="#link-declaration-competing-interest">Declaration of Competing Interest</a> <a class="list-group-item list-group-item-action" href="#html-references_list">References</a> </div> </div> </div> </div> <span class="btn-out" data-toggle="collapse" data-target="#rightCollapse" aria-expanded="true" aria-controls="rightCollapse"> <svg xmlns="http://www.w3.org/2000/svg" width="26" height="26" fill="currentColor" class="bi bi-chevron-bar-left" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M11.854 3.646a.5.5 0 0 1 0 .708L8.207 8l3.647 3.646a.5.5 0 0 1-.708.708l-4-4a.5.5 0 0 1 0-.708l4-4a.5.5 0 0 1 .708 0zM4.5 1a.5.5 0 0 0-.5.5v13a.5.5 0 0 0 1 0v-13a.5.5 0 0 0-.5-.5z"/> </svg> </span> </div> </div> <div class="blog-detailss-wrap flex-grow-1"> <div class="details__content pb-30"> <div class="articlelei access-tags d-flex justify-content-between"> <p class="mb-0 d-flex align-items-center"> <span class="btn-text classdise mr-1">Article</span> <span class="btn-text textdise">Open Access</span> </p> <div class="share-buttons social-share d-flex align-items-center mb-2" data-initialized="true"> Share This Article： <a href="" class="share-btn social-share-icon twitter-btn icon-twitter d-flex align-items-center justify-content-center" title="Share on Twitter"> <svg t="1713929395475" class="icon" viewBox="0 0 1399 1024" fill="currentColor" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="8742" width="20" height="20"> <path d="M282.021569 119.281213l323.998199 433.216256-326.044203 352.222995h73.379441l285.451142-308.376452 230.636674 308.376452h249.713149l-342.227762-457.583832 303.479459-327.855419h-73.379441l-262.886398 284.008876-212.407111-284.008876h-249.713149z m107.909957 54.051408h114.71879l506.578928 677.328049h-114.718791l-506.578927-677.328049z" p-id="8743"></path> </svg> </a> <a href="" class="share-btn social-share-icon facebook-btn icon-facebook d-flex align-items-center justify-content-center" title="Share on Facebook"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-facebook" viewBox="0 0 16 16"> <path d="M16 8.049c0-4.446-3.582-8.05-8-8.05C3.58 0-.002 3.603-.002 8.05c0 4.017 2.926 7.347 6.75 7.951v-5.625h-2.03V8.05H6.75V6.275c0-2.017 1.195-3.131 3.022-3.131.876 0 1.791.157 1.791.157v1.98h-1.009c-.993 0-1.303.621-1.303 1.258v1.51h2.218l-.354 2.326H9.25V16c3.824-.604 6.75-3.934 6.75-7.951z"/> </svg> </a> <a href="mailto:?subject=Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network&body=https%3A%2F%2Fwww.sciepublish.com%2Farticle%2Fpii%2F209" class="share-btn social-share-icon email-btn icon-email d-flex align-items-center justify-content-center" id="email-share-btn" title="Share on Email"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-envelope-fill" viewBox="0 0 16 16"> <path d="M.05 3.555A2 2 0 0 1 2 2h12a2 2 0 0 1 1.95 1.555L8 8.414.05 3.555ZM0 4.697v7.104l5.803-3.558L0 4.697ZM6.761 8.83l-6.57 4.027A2 2 0 0 0 2 14h12a2 2 0 0 0 1.808-1.144l-6.57-4.027L8 9.586l-1.239-.757Zm3.436-.586L16 11.801V4.697l-5.803 3.546Z"/> </svg> </a> <a href="" class="share-btn social-share-icon LinkedIn-btn icon-linkedin d-flex align-items-center justify-content-center" id="email-LinkedIn-btn" title="Share on LinkedIn"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-linkedin" viewBox="0 0 16 16"> <path d="M0 1.146C0 .513.526 0 1.175 0h13.65C15.474 0 16 .513 16 1.146v13.708c0 .633-.526 1.146-1.175 1.146H1.175C.526 16 0 15.487 0 14.854V1.146zm4.943 12.248V6.169H2.542v7.225h2.401zm-1.2-8.212c.837 0 1.358-.554 1.358-1.248-.015-.709-.52-1.248-1.342-1.248-.822 0-1.359.54-1.359 1.248 0 .694.521 1.248 1.327 1.248h.016zm4.908 8.212V9.359c0-.216.016-.432.08-.586.173-.431.568-.878 1.232-.878.869 0 1.216.662 1.216 1.634v3.865h2.401V9.25c0-2.22-1.184-3.252-2.764-3.252-1.274 0-1.845.7-2.165 1.193v.025h-.016a5.54 5.54 0 0 1 .016-.025V6.169h-2.4c.03.678 0 7.225 0 7.225h2.4z"/> </svg> </a> <a href="" class="share-btn social-share-icon wechat-btn icon-wechat d-flex align-items-center justify-content-center" id="wechat-share-btn" title="Share on WeChat"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-wechat" viewBox="0 0 16 16"> <path d="M11.176 14.429c-2.665 0-4.826-1.8-4.826-4.018 0-2.22 2.159-4.02 4.824-4.02S16 8.191 16 10.411c0 1.21-.65 2.301-1.666 3.036a.324.324 0 0 0-.12.366l.218.81a.616.616 0 0 1 .029.117.166.166 0 0 1-.162.162.177.177 0 0 1-.092-.03l-1.057-.61a.519.519 0 0 0-.256-.074.509.509 0 0 0-.142.021 5.668 5.668 0 0 1-1.576.22ZM9.064 9.542a.647.647 0 1 0 .557-1 .645.645 0 0 0-.646.647.615.615 0 0 0 .09.353Zm3.232.001a.646.646 0 1 0 .546-1 .645.645 0 0 0-.644.644.627.627 0 0 0 .098.356Z"/> <path d="M0 6.826c0 1.455.781 2.765 2.001 3.656a.385.385 0 0 1 .143.439l-.161.6-.1.373a.499.499 0 0 0-.032.14.192.192 0 0 0 .193.193c.039 0 .077-.01.111-.029l1.268-.733a.622.622 0 0 1 .308-.088c.058 0 .116.009.171.025a6.83 6.83 0 0 0 1.625.26 4.45 4.45 0 0 1-.177-1.251c0-2.936 2.785-5.02 5.824-5.02.05 0 .1 0 .15.002C10.587 3.429 8.392 2 5.796 2 2.596 2 0 4.16 0 6.826Zm4.632-1.555a.77.77 0 1 1-1.54 0 .77.77 0 0 1 1.54 0Zm3.875 0a.77.77 0 1 1-1.54 0 .77.77 0 0 1 1.54 0Z"/> </svg> </a> </div> </div> <h1 class="mb-2 acquiesce-title">Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network</h1> <div class="affiliation mb-1"> <div class="affiliation_author"> <span class="mr-2"> <a href="https://scholar.google.com/scholar?q=Ramkumar Ganapathy" target="_blank">Ramkumar Ganapathy</a> <sup></sup> </span> <span class="mr-2"> <a href="https://scholar.google.com/scholar?q=Christopher Thron" target="_blank">Christopher Thron</a> <sup>*</sup> <a href="mailto:thron@tamuct.edu"> <sup><i class="bi bi-envelope-fill"></i></sup> </a> </span> </div> </div> <div class="d-flex mb-1"> <div class="information-collapse mr-4"> Author Information </div>  </div> <div class="articledz"> <div class="affiliation_zt"> <div class="information-item affiliation_at collapse pl-2 pr-2 pb-2"> <div class="affiliation d-flex"> <div class="affiliation_nameno"> Texas A&M University-Central Texas, Killeen, TX 76549, USA </div> </div> <div class="affiliation d-flex"> <div class="affiliation_sup mr-2"><sup>*</sup></div> <div class="affiliation_name flex-grow-1"> Authors to whom correspondence should be addressed. </div> </div> </div> </div> <div class="d-flex align-items-center"> <div class="mr-2 d-flex align-items-center"><span>Views:</span><b class="ml-2">840</b></div> <div class="mr-2 d-flex align-items-center"><span>Downloads:</span><b class="ml-2">135</b></div> <a tabindex="0" class="mr-2 align-items-center cursor-pointer" style="display: none;" data-bind="popover1" data-container="body" data-toggle="popover" data-trigger="focus" data-placement="bottom"> <span>Citations:</span> <b class="ml-2">0</b> </a> </div> <div class="information-item pb-3"> <div class="articledoi"> <em>Drones and Autonomous Vehicles</em> <b>2024</b>, <em>1</em> (3), 10007;  <a href="https://doi.org/10.35534/dav.2024.10007" target="_blank">https://doi.org/10.35534/dav.2024.10007</a> </div> <p class="d-flex fal-title mb-0"> <i class="fal fa-calendar-alt"></i> <span class="mr-3">Received: 12 January 2024</span> <span class="mr-3">Accepted: 30 May 2024</span> <span class="mr-3">Published: 12 June 2024</span> </p> </div> <div class="articleneir pull-item d-flex"> <a href="http://creativecommons.org/licenses/by/4.0/" itemprop="license" rel="license" data-license="by" class="pull-left pt-1"> <img src="/style/image/iconby.png" alt="Creative Commons"> </a> <p class="flex-grow-1 ml-2"> © 2024 The authors. This is an open access article under the Creative Commons Attribution 4.0 International License (<a href="https://creativecommons.org/licenses/by/4.0/" target="_blank">https://creativecommons.org/licenses/by/4.0/</a>). </p> </div> <div class="meta-info text-break border-top border-dark pt-3 mt-3"> <div class="articleneir abstract"> <span>ABSTRACT:</span> We consider a remote sensing system in which fixed sensors are placed in a region, and a single drone flies over the region to collect information from cluster heads. We assume that the drone has a fixed maximum range and that the energy consumption for information transmission from the cluster heads increases with distance according to a power law. Given these assumptions, we derive local optimum conditions for a drone path that either minimizes the total or maximum energy required by the cluster heads to transmit information to the drone. We show how a homotopy approach can produce a family of solutions for different drone path lengths so that a locally optimal solution can be found for any drone range. We implement the homotopy solution in Python and demonstrate the tradeoff between drone range and cluster head power consumption for several geometries. Execution time is sufficiently rapid for the computation to be performed in real time so that the drone path can be recalculated on the fly. The solution is shown to be globally optimal for sufficiently long drone path lengths. A proof of concept implementation in Python is available on GitHub. For future work, we indicate how the solution can be modified to accommodate moving sensors. </div> <div class="articleneir mt-2 keywords"> <span>Keywords:</span> Wireless sensor network; Drone; Path planning; Information collection; Power-efficient; Extended lifetime; Optimization </div> <div class="article-item pt-4"> <h2 class="border-bottom"> <a id="link-introduction" class="anchor-66"></a> 1. Introduction </h2> <div class="link-introduction article-item-text pt-2">There are many critical applications for remote sensing in low-resourced areas. Some of these include agricultural monitoring of crops and/or forests for fire and/or disease; wildlife monitoring to track wildlife movement and detect poachers; free-range livestock monitoring to track herd movement and to prevent cattle rustling; and early warning of terrorist or bandit activity. In low-resourced situations especially, the system cost is of huge importance and spells the difference as to whether or not the system may be implemented. Sensors in area-monitoring networks typically are battery-powered and must be replaced when their batteries are exhausted. This can be both difficult and costly, particularly in inaccessible locations. For this reason, reducing the power consumption of sensors in the field is a key factor in designing such remote sensing systems. One possible approach to reducing power consumption, which has been investigated by a number of researchers, is to supplement the WSN with unmanned aerial vehicles (UAV) such as drones fitted with receiving antennas and either information storage or transmit capabilities. Such drones can serve as moveable sinks or relays, travelling to or near the transmitting elements within the network in order to reduce transmission distance, hence power expenditure. Previous authors have investigated practical use cases for using drones to collect information from WSN’s. [<a href='#B1' class='html-bibr' title='1'>1</a>,<a href='#B2' class='html-bibr' title='2'>2</a>] have provided comprehensive surveys of drone-assisted data collection from wireless sensor networks. The integration of UAVs into surveillance systems involving WSNs and other technologies is discussed in [<a href='#B3' class='html-bibr' title='3'>3</a>]. Several previous papers have dealt specifically with drone path planning in various scenarios. References [<a href='#B4' class='html-bibr' title='4'>4</a>,<a href='#B5' class='html-bibr' title='5'>5</a>] assess several metaheuristic algorithms for path planning in the context of disaster management and pre-planning. [<a href='#B6' class='html-bibr' title='6'>6</a>] gives a heuristic algorithm to decide which node within a cluster to fly to so as to gather information from the cluster. [<a href='#B7' class='html-bibr' title='7'>7</a>] uses a boustrophedon-type (i.e., back-and-forth) flight path for a sensor network located in a region divided into square cells. [<a href='#B8' class='html-bibr' title='8'>8</a>] considers the problem of minimizing the flight time of an information-gathering drone in the case where sensors are in a straight line, and the time required for information transfer from each sensor is an important consideration. [<a href='#B9' class='html-bibr' title='9'>9</a>] considers the impact of drone path shape on information transmission from sensors to drones. [<a href='#B10' class='html-bibr' title='10'>10</a>] uses particle-swarm optimization to arrive at an optimal path. [<a href='#B11' class='html-bibr' title='11'>11</a>] presents an efficient joint data collection and sensor positioning scheme for WSN supported by multiple UAVs. In low-resource situations, expense is a paramount concern in systems design. Systems with multiple drones may not be feasible because of the expense. On the other hand, systems with a single drone must accommodate the limiteddrone range. If the drone takes several trips to reach all sensors, this delays the receipt of information and reduces the thoroughness of coverage. In such cases, it may be preferable to design a drone tour of all sensors that approaches the sensors as closely as possible. In this paper, we consider a hybrid WSN-drone system for remote sensing, in which a single drone of limited range is used to collect information from wireless sensors that have fixed locations in the field (see <a href='#Figure1' class='html-fig html-figpopup'>Figure 1</a>). The drone harvests information from all sensors during a single tour. The system design is posed as a constrained optimization problem. Our novel solution approach involves using a Lagrange multiplier to construct a differential equation in which the Lagrange multiplier is the independent variable. Since our approach reduces the problem to the numerical solution of a multivariate ordinary differential equation (ODE), it can make use of efficient, highly developed algorithms for solving ODEs, thus reducing execution time and making it possible to compute optimal trajectories on-the-fly for very large WSNs.<div class='html-fig-wrap'><div class='html-fig_img'><div class='html-figpopup html-figpopup-link' href='#Figure1'><img data-large='/uploads/2024/06/12/0fe3c2eb112e8259bf5b994c458cfd90.png' data-original='/uploads/2024/06/12/0fe3c2eb112e8259bf5b994c458cfd90.png' src='/uploads/2024/06/12/0fe3c2eb112e8259bf5b994c458cfd90.png'><a class='html-expand html-figpopup' href='#Figure1'></a></div></div><div class='html-fig_description'><b><a href='#Figure1' class='html-fig html-figpopup'>Figure 1</a>. </b>Schematic of remote sensing system in which a drone harvests information from fixed sensors (copied from Reference [<a href='#B1' class='html-bibr' title='1'>1</a>]—open access, no permission required https://www.mdpi.com/openaccess).</div></div> </div> <h2 class="border-bottom"> <a id="link-materials-and-methods" class="anchor-66"></a> 2. Methodology </h2> <div class="link-materials-and-methods article-item-text"><i>2.1. System Assumptions</i> We consider a remote sensing system that satisfies the following assumptions: (<i>A</i><sub>1</sub>) The system includes a wireless sensor network with predetermined cluster heads. Each sensor in the field transmits its information (either directly or indirectly) to one of the cluster heads. (<i>A</i><sub>2</sub>) The system also includes a drone that flies on a specific trajectory (to be determined) so that each cluster head transmits its energy to the drone when it is nearby. (<i>A</i><sub>3</sub>) The drone’s energy consumption is determined entirely by the length of the drone’s trajectory. (This is the case for example, if the drone flies at a constant velocity, and there is no wind or other conditions that would affect the flight of the drone.) (<i>A</i><sub>4</sub>) The drone has a fixed maximum path length, which is determined by the energy capacity of the battery and the rate of energy consumption. (<i>A</i><sub>5</sub>) The drone’s location is approximately constant while receiving information from a particular cluster head. This assumption is satisfied in either of the following scenarios: (a) the information transmission from the cluster head occupies only a brief period of time, so that the distance the drone moves during the transmission period is negligible; or (b) the drone slows, hovers, or lands during transmission, and consumes no energy during the transmission period. (<i>A</i><sub>6</sub>) The energy expended by the cluster head in information transmission is proportional to the distance between the cluster head and drone raised to a power law exponent. We also consider two alternative criteria for optimization: (<i>O</i><sub>1</sub>) Minimize the total energy expended by cluster heads in information transmission. (<i>O</i><sub>2</sub>) Minimize the maximum energies expended by cluster heads in information transmission. The choice of suitable optimization criterion will depend on the particular circumstances of the WSN. For example, in a system with many potential alternative cluster heads, then the maximum consumption among cluster heads may be less important than overall power consumption, so criterion <i>O</i><sub>1</sub> may be appropriate. On the other hand, if there are few choices for cluster head, then the cluster head with maximum energy expended will need frequent replacement, so criterion <i>O</i><sub>2</sub> may be a better option. We note that other criteria besides <i>O</i><sub>1</sub> and <i>O</i><sub>2</sub> are possible, with minimal changes to the solution, as we indicate in Section 5. Under assumptions (<i>A</i><sub>1</sub>)–(<i>A</i><sub>6</sub>) and criteria (<i>O</i><sub>1</sub>)–(<i>O</i><sub>2</sub>), it follows that an optimum path for the drone will consist of straight-line segments joining the drones’ locations where it harvests energy from the different cluster heads. This conclusion is reflected in the mathematical description in subsequent sections. <i>2.2. System Parameters and Variables</i> The system parameters include: <ul> <li>(<i>x<sub>j</sub></i>, <i>y<sub>j</sub></i>), <i>j</i> = 1...<i>J</i>: positions of the cluster heads that are sending the information;</li> <li><i>L</i>: Maximum path length for the drone;</li> <li><i>p</i>: Power loss exponent. </li></ul> The system variables include: <ul><li>(<i>u<sub>j</sub></i>,<i>v<sub>j</sub></i>), <i>j</i> = 1...<i>J</i> : Drone positions for harvesting information from cluster heads. Here, the order of points the drone takes is assumed to be (<i>u<sub>j</sub></i>,<i>v<sub>j</sub></i>) to (<i>u</i><sub><i>j</i>+1</sub>,<i>v</i><sub><i>j</i>+1</sub>) for <i>j</i> = 1 ...<i>J</i> − 1.</li> <li>(<i>u</i><sub>0</sub>,<i>v</i><sub>0</sub>), (<i>u</i><sub><i>J</i>+1</sub>,<i>v</i><sub><i>J</i>+1</sub>): Drone starting and ending position, respectively.</li> </ul> <i>2.3. Mathematical Formulation of the Optimization Problem</i> Information transmission from cluster head (<i>x<sub>j</sub></i>, <i>y<sub>j</sub></i>) takes place when the drone is at position (<i>u<sub>j</sub></i>, <i>v<sub>j</sub></i>). The total energy consumption required for information transfer is the sum of the energies from the J cluster heads, which following assumption (<i>A</i><sub>6</sub>), can be represented as a function $$f(\vec{u},\vec{v}){:}$$ <div class='html-disp-formula-info'><div class='html_pics'>```latexf(\vec{u},\vec{v})=\sum_{j=1}^J\left(\left(x_j-u_j\right)^2+\left(y_j-v_j\right)^2\right)^{p/2},```</div><div class='formula'><label>(1)</label></div></div> where $$\vec{u}:=\begin{bmatrix}u_1,....u_J\end{bmatrix}$$ and $$\vec{v}:=\begin{bmatrix}v_1,....v_J\end{bmatrix}$$. The distance the drone travels is given by $$g(\vec{u},\vec{v})$$, where <div class='html-disp-formula-info'><div class='html_pics'><img style='max-width:%' data-large='/uploads/2024/06/12/2519c8c90f9934f686a98c21d5a437f9.png' data-original='/uploads/2024/06/12/2519c8c90f9934f686a98c21d5a437f9.png' src='/uploads/2024/06/12/2519c8c90f9934f686a98c21d5a437f9.png'></div><div class='formula'><label>(2)</label></div></div> The drone’s limited range imposes the constraint $$g(\vec{u},\vec{v})$$ ≤ <i>L</i>, where <i>L</i> is the maximum distance the drone can travel. In the case where <i>L</i> is large enough so that the drone is capable of making a complete tour of the cluster heads, then any such complete tour will give $$g(\vec{u},\vec{v})$$ = 0 and is thus an optimal solution to the problem. So we consider instead the more difficult problem where <i>L</i> is smaller than the smallest tour distance, so $$g(\vec{u},\vec{v})$$ = 0 is impossible. In this case, we may replace the inequality with an equality constraint. This can be seen as follows. Suppose a drone path includes the point (<i>u<sub>j</sub></i>, <i>v<sub>j</sub></i>) where $$|(u_j,v_j)-(x_j,y_j)|>0.$$ For simplicity, we define: <div class='html-disp-formula-info'><div class='html_pics'>```latex\vec{w}_{j}{:}=\vec{w}_{j}\big(u_{j},v_{j}\big)\,and\,\vec{z}_{J}{:}=\big(x_{j},y_{j}\big).```</div><div class='formula'><label>(3)</label></div></div> Then, for any δ with 0 < δ ≤ 1, we have <div class='html-disp-formula-info'><div class='html_pics'>```latex\left|\vec{w}_j+\delta\big(\vec{z}_j-\vec{w}_j\big)-\vec{z}_j\right|=(1-\delta)\big|\vec{w}_j-\vec{z}_j\big|<\big|\vec{w}_j-\vec{z}_j\big|,```</div><div class='formula'><label>(4)</label></div></div> so replacing $$\vec{w}_{j}$$ with $$\vec{w}_{j}+\delta(\vec{z}_{j}-\vec{w}_{j})$$ will reduce the energy function (1). Now, if the drone path length is less than <i>L</i>, then <i>δ</i> > 0 can be chosen sufficiently small such that replacing $$\vec{w}_{j}$$ with $$\vec{w}_{j}+\delta(\vec{z}_{j}-\vec{w}_{j})$$ still yields total drone path length of less than <i>L</i>. Thus, any drone path with a length less than <i>L</i> can be improved—so no drone path with a length less than <i>L</i> can be optimal. We may now formulate the optimization problem. In case (<i>O</i><sub>1</sub>), we have <div class='html-disp-formula-info'><div class='html_pics'>```latex\text{Minimize }f(\vec{u},\vec{v})\text{subject to }g(\vec{u},\vec{v})=L.```</div><div class='formula'><label>(5)</label></div></div> In case (<i>O</i><sub>2</sub>), minimizing the maximum transmission energy is equivalent to minimizing $$|\vec{w}_{j}-\vec{z}_{j}|$$ over all <i>j</i>. Using the equality <div class='html-disp-formula-info'><div class='html_pics'>```latex\lim_{p\to\infty}\bigl(a_{1}^{p}+\cdots+a_{J}^{p}\bigr)^{1/p}=\max_{j}a_{j}\quad if \,a_{j}>0\,\forall \,j,```</div><div class='formula'><label>(6)</label></div></div> with $$a_{j}:=|\vec{w}_{j}-\vec{z}_{j}|$$, we conclude that by taking <i>p</i> sufficiently large, we can approach the solution to (<i>O</i><sub>2</sub>) with arbitrary precision. <i>2.4. Local Optimization Conditions</i> The minimization problem (5) leads to the following Lagrange multiplier condition for a local minimum: <div class='html-disp-formula-info'><div class='html_pics'>```latex\nabla f(\vec{u},\vec{v})=\lambda\nabla(g(\vec{u},\vec{v})-L),```</div><div class='formula'><label>(7)</label></div></div> where ∇<i>h</i> denotes the gradient of <i>h</i> with respect to $$(\vec{u},\vec{v})$$: <div class='html-disp-formula-info'><div class='html_pics'>```latex\nabla h(\vec{u},\vec{v}){:}=\left(\frac{\partial f}{\partial u_{1}},...\frac{\partial f}{\partial u_{j}},\frac{\partial f}{\partial v_{1}},...\frac{\partial f}{\partial v_{j}}\right),```</div><div class='formula'><label>(8)</label></div></div> and <i>λ</i> is a Lagrange multiplier. Writing the vector Equation (7) out in terms of components, we have: <div class='html-disp-formula-info'><div class='html_pics'>```latex\frac{\partial f}{\partial u_{j}}=\lambda\frac{\partial g}{\partial u_{j}};\frac{\partial f}{\partial v_{j}}=\lambda\frac{\partial g}{\partial v_{j}},\quad(j=1\ldots J)```</div><div class='formula'><label>(9)</label></div></div> For notational simplicity, we define new variables. For <i>j</i> = 1….<i>J</i>, let <div class='html-disp-formula-info'><div class='html_pics'>```latexa_j:=u_j-x_j;b_j:=v_j-y_j;A_j:=a_j^2+b_j^2,```</div><div class='formula'><label>(10)</label></div></div> <div class='html-disp-formula-info'><div class='html_pics'>```latexm_j:=u_j-u_{j+1};n_j:=v_j-v_{j+1};M_j:=\left(m_j^2+n_j^2\right)^{\frac{1}{2}}.```</div><div class='formula'><label>(11)</label></div></div> Then we have: <div class='html-disp-formula-info'><div class='html_pics'><img style='max-width:%' data-large='/uploads/2024/06/12/8c9023fe70930ed8f79c08c2935450a8.png' data-original='/uploads/2024/06/12/8c9023fe70930ed8f79c08c2935450a8.png' src='/uploads/2024/06/12/8c9023fe70930ed8f79c08c2935450a8.png'></div><div class='formula'><label>(12)</label></div></div> Using this notation, we have: <div class='html-disp-formula-info'><div class='html_pics'>```latex\frac{\partial f}{\partial u_{j}}=\frac{\partial f}{\partial A_{j}}\times\frac{\partial A_{j}}{\partial a_{j}}\times\frac{\partial a_{j}}{\partial u_{j}}=(\left(\frac{p}{2}\right)A_{j}^{\frac{p}{2}-1}\times2a_{j}=pa_{j}A_{j}^{q}```</div><div class='formula'><label>(13)</label></div></div> where $$q{:}=\frac{p}{2}-1$$, and <div class='html-disp-formula-info'><div class='html_pics'>```latex\frac{\partial g}{\partial u_{j}}=\frac{\partial g}{\partial M_{j-1}}\times\frac{\partial M_{j-1}}{\partial m_{j-1}}\times\frac{\partial m_{j-1}}{\partial u_{j}}+\frac{\partial g}{\partial M_{j}}\times\frac{\partial M_{j}}{\partial m_{j}}\times\frac{\partial m_{j}}{\partial u_{j}}=\\\left(\frac12\right)M_{j-1}^{-1}\big(2m_{j-1}\big)(-1)+\bigg(\frac12\bigg)M_j^{-1}\big(2m_j\big)=\frac{m_j}{M_j}-\frac{m_{j-1}}{M_{j-1}}.```</div><div class='formula'><label>(14)</label></div></div> Similarly, we have: <div class='html-disp-formula-info'><div class='html_pics'>```latex\frac{\partial f}{\partial v_{j}}=pb_{j}A_{j}^{q};\frac{\partial g}{\partial v_{j}}=\frac{n_{j}}{M_{j}}-\frac{n_{j-1}}{M_{j-1}}.```</div><div class='formula'><label>(15)</label></div></div> It follows that we may rewrite the equations in (9) as: <div class='html-disp-formula-info'><div class='html_pics'>```latexpa_{j}A_{j}^{q}=\lambda\left(\frac{m_{j}}{M_{j}}-\frac{m_{j-1}}{M_{j-1}}\right);pb_{j}A_{j}^{q}=\lambda\left(\frac{n_{j}}{M_{j}}-\frac{n_{j-1}}{M_{j-1}}\right)\quad(j=1\ldots J).```</div><div class='formula'><label>(16)</label></div></div> Equations (16) are required for local optimality and are necessary for global optimality but not sufficient. Thus, the solutions that we provide in this paper may not be optimal for all global situations. We return to this issue in Section 2.8. <i>2.5. Homotopy Approach to Local Optimization for a Given Path Length</i> Solutions of the fundamental optimization problem (5) for different values of <i>L</i> correspond to solutions of (16) with different values of <i>λ</i>. As <i>L</i> is varied continuously, the value of <i>λ</i> will also vary continuously, and the components of $$\vec{u}$$ and $$\vec{v}$$ will vary continuously as well. This suggests that if we have a solution to (5) for a given value of <i>L</i>, we may be able to perturb that solution differentially to obtain solutions for different values of <i>L</i>. In fact, we do have a solution for a particular value of <i>L</i>: namely <i>f</i>( $$\vec{u}$$, $$\vec{v}$$) = 0 when <i>u<sub>j</sub></i> = <i>x<sub>j</sub></i> and <i>v<sub>j</sub></i> = <i>y<sub>j</sub></i>, which solves the constraint $$g(\vec{u},\vec{v})$$ = <i>L</i> when <i>L</i> is equal to the length of the tour that connects the points $$({\vec{x}}_{j},{\vec{y}}_{j})$$ in consecutive order. The smallest value of <i>L</i> for this type of solution occurs when the points $$({\vec{x}}_{j},{\vec{y}}_{j})$$ are ordered so that $$(u_{0},v_{0}),(x_{1},y_{1}),(x_{2},y_{2}),...(x_{J},y_{J}),(u_{J+1},v_{J+1})$$ forms a “travelling salesman” tour that connects all points $$({\vec{x}}_{j},{\vec{y}}_{j})$$ with the smallest possible total length. In practice, we want to find solutions corresponding to <i>L</i> values that are smaller than the length of a full tour. So we start with the full tour and successively “nudge” the solutions so they correspond to smaller and smaller values of <i>L</i>. This is an example of a <i>homotopy approach</i>: start with a solution that is optimal for a different set of conditions and generate a smooth curve of solutions that joins this solution to a solution that satisfies desired conditions. In practice, this smooth curve of solutions is often specified parametrically as the solution to a set of ordinary differential equations. In the next section, we will derive differential equations that can be used to find the parametrized curve that leads to our desired optimal solution. <i>2.6. Derivation of Differential Equations for Parametrized Homotopy Curve</i> First, we parametrize solutions to (16) using the parameter s, so that <i>a<sub>j</sub></i>, <i>b<sub>j</sub></i>, <i>A<sub>j</sub></i>, <i>m<sub>j</sub></i>, <i>M<sub>j</sub></i>, and λ are all functions of <i>s</i>. As <i>s</i> changes, the equalities cannot change, so we have <div class='html-disp-formula-info'><div class='html_pics'>```latexp\frac{d}{ds}\big(a_{j}A_{j}^{q}\big)=\frac{d}{ds}\bigg(\lambda\frac{m_{j}}{M_{j}}-\lambda\frac{m_{j-1}}{M_{j-1}}\bigg),\\p\frac{d}{ds}\big(b_{j}A_{j}^{q}\big)=\frac{d}{ds}\bigg(\lambda\frac{n_{j}}{M_{j}}-\lambda\frac{n_{j-1}}{M_{j-1}}\bigg).```</div><div class='formula'><label>(17)</label></div></div> Since we want to find solutions for smaller values of <i>L</i>, we want to ensure that <i>L</i> decreases as <i>s</i> increases. We may ensure this by adding the condition: <div class='html-disp-formula-info'><div class='html_pics'>```latex\frac{dg}{ds}=-1\Rightarrow\sum_{j=0}^J\frac{dM_j}{ds}=-1.```</div><div class='formula'><label>(18)</label></div></div> Recall that the variables <i>a<sub>j</sub></i>, <i>b<sub>j</sub></i>, <i>A<sub>j</sub></i>, <i>m<sub>j</sub></i>, <i>M<sub>j</sub></i>, in (17) are all functions of $$\vec{u}$$ and $$\vec{v}$$, so the derivatives in (17) can all be expressed in terms of the derivatives $$\frac{du_{j}}{ds}$$ and $$\frac{dv_{j}}{ds}$$ for <i>j</i> = 1,…..<i>J</i>. As a result, we obtain a system of 2<i>J</i> + 1 differential equations for the variables {<i>u<sub>j</sub></i>,<i>v<sub>j</sub></i>},<i>j</i> = 1….<i>J</i> and λ. We may rewrite the first equation in (17) as (<i>j</i> = 1….<i>J</i>): <div class='html-disp-formula-info'><div class='html_pics'>```latex0=pA_{j}^{q}\frac{da_{j}}{ds}+pqa_{j}A_{j}^{q-1}\frac{dA_{j}}{ds}-\frac{\lambda}{M_{j}}\frac{dm_{j}}{ds}+\frac{\lambda}{M_{j-1}}\frac{dm_{j-1}}{ds}+\\\frac{\lambda m_{j}}{M_{j}^{2}}\frac{dM_{j}}{ds}-\frac{\lambda m_{j-1}}{M_{j-1}^{2}}\frac{dM_{j-1}}{ds}-\frac{m_{j}}{M_{j}}\frac{d\lambda}{ds}+\frac{m_{j-1}}{M_{j-1}}\frac{d\lambda}{ds}```</div><div class='formula'><label>(19)</label></div></div> The derivatives in (19) may be expressed in terms of { $$\frac{du_k}{ds}$$} and { $$\frac{dv_j}{ds}$$} using the formulas (<i>j</i> = 0…..<i>J</i>): <div class='html-disp-formula-info'><div class='html_pics'>```latex\begin{gathered}\frac{da_{j}}{ds}=\frac{du_{j}}{ds}; \\\frac{dA_{j}}{ds}=2a_{j}\frac{du_{j}}{ds}+2b_{j}\frac{dv_{j}}{ds}; \\\frac{dm_{j}}{ds}=\frac{du_{j}}{ds}-\frac{du_{j+1}}{ds}; \\\frac{dM_{j}}{ds}=M_{j}^{-1}\left(m_{j}\left(\frac{du_{j}}{ds}-\frac{du_{j+1}}{ds}\right)+n_{j}\left(\frac{dv_{j}}{ds}-\frac{dv_{j+1}}{ds}\right)\right) \end{gathered}```</div><div class='formula'><label>(20)</label></div></div> It follows that (19) with index <i>j</i> will depend on the derivatives $$\frac{du_k}{ds}$$, $$\frac{dv_k}{ds}$$ and $$\frac{dλ}{ds}$$ for <i>k</i> = <i>j</i> $$-$$ <i>1</i>,<i>j</i>,<i>j</i> + 1 (noting that $${\frac{du_{0}}{ds}}={\frac{dv_{0}}{ds}}={\frac{du_{j+1}}{ds}}={\frac{dv_{j+1}}{ds}}=0$$. By collecting terms corresponding to each derivative, we find (<i>j</i> = 1…..<i>J</i>) <div class='html-disp-formula-info'><div class='html_pics'><img style='max-width:%' data-large='/uploads/2024/06/12/19c2e41593506c6718feba2b1c58e3ee.png' data-original='/uploads/2024/06/12/19c2e41593506c6718feba2b1c58e3ee.png' src='/uploads/2024/06/12/19c2e41593506c6718feba2b1c58e3ee.png'></div><div class='formula'><label>(21)</label></div></div> Using various algebraic manipulations and the fact that: <div class='html-disp-formula-info'><div class='html_pics'>```latex1-\frac{m_j^2}{M_j^2}=\frac{n_j^2}{M_j^2}```</div><div class='formula'><label>(22)</label></div></div> The Equations (19) may be simplified to: <div class='html-disp-formula-info'><div class='html_pics'>```latex\begin{gathered} 0=\frac{du_{j}}{ds}\left(pA_{j}^{q}\left(1+\frac{2qa_{j}^{2}}{A_{j}}\right)-\frac{\lambda n_{j-1}^{2}}{M_{j-1}^{3}}\right)-\frac{\lambda n_{j}^{2}}{M_{j}^{3}} \\+\frac{du_{j-1}}{ds}\biggl(\frac{\lambda n_{j-1}^{2}}{M_{j-1}^{3}}\biggr)+\frac{du_{j+1}}{ds}\biggl(\frac{\lambda n_{j}^{2}}{M_{j}63}\biggr) \\+\frac{dv_{j}}{ds}(2pqa_{j}b_{j}A_{j}^{q-1}+\frac{\lambda m_{j-1}n_{j-1}}{M_{j-1}^{3}}+\frac{\lambda m_{j}n_{j}}{M_{j}^{3}}) \\-\frac{dv_{j-1}}{ds}\biggl(\frac{\lambda m_{j-1}n_{j-1}}{M_{j-1}^{3}}\biggr)-\frac{dv_{j+1}}{ds}\biggl(\frac{\lambda m_{j}n_{j}}{M_{j}^{3}}\biggr) \\+\frac{d\lambda}{ds}\biggl(-\frac{m_{j}}{M_{j}}+\frac{m_{j-1}}{M_{j-1}}\biggr),j=1\ldots J \end{gathered}```</div><div class='formula'><label>(23)</label></div></div> The <i>J</i> equations associated with the second equation in (17) may be obtained from (23) by exchanging $$u_{k}\leftrightarrow v_{k}$$, $$a_{k}\leftrightarrow b_{k}$$, and $$m_{k}\leftrightarrow n_{k}$$. Finally, (18) can be expressed in terms of derivatives of {<i>u<sub>j</sub></i>,<i>v<sub>j</sub></i>} as: <div class='html-disp-formula-info'><div class='html_pics'><img style='max-width:%' data-large='/uploads/2024/06/12/d929642c7f40170912c4992e7379e061.png' data-original='/uploads/2024/06/12/d929642c7f40170912c4992e7379e061.png' src='/uploads/2024/06/12/d929642c7f40170912c4992e7379e061.png'></div><div class='formula'><label>(24)</label></div></div> The entire system of 2<i>J</i> +1 equations can be represented in matrix form as: <div class='html-disp-formula-info'><div class='html_pics'>```latexH\frac{d\mathbf{u}}{ds}=z\Rightarrow\frac{d\mathbf{u}}{ds}=H^{-1}\vec{z}```</div><div class='formula'><label>(25)</label></div></div> where <i>H</i> is a (2<i>J</i> + 1) × (2<i>J</i> + 1) matrix, and <b>u</b>,<b>z</b> are column vectors of length 2<i>J</i> + 1, given by the formulas: <div class='html-disp-formula-info'><div class='html_pics'>```latex\mathbf{u}:=[\vec{u},\vec{v},\lambda]^{T};\\\mathbf{z}:=[0,....0,-1]^{T}```</div><div class='formula'><label>(26)</label></div></div> (i.e., <b>z</b> has a single nonzero entry of −1 in the last component). The matrix <i>H</i> can be decomposed into blocks: <div class='html-disp-formula-info'><div class='html_pics'>```latexH=\begin{bmatrix}H_{11}&H_{12}&\overrightarrow{h_1}\\H_{21}&H_{22}&\overrightarrow{h_2}\\\overrightarrow{h_1^T}&\overrightarrow{h_2^T}&0\end{bmatrix}```</div><div class='formula'><label>(27)</label></div></div> The blocks <i>H<sub>ij</sub></i> can be expressed in terms of diagonal and subdiagonal matrices. First, we introduce some abbreviated notations. Let diag(<i>c<sub>j</sub></i>) denote the <i>J</i> × <i>J</i> diagonal matrix with entries <i>c</i><sub>1</sub>,...<i>c<sub>J</sub></i> on the diagonal; and let <i>D</i> denote the discrete forward derivative matrix with −1’s on the diagonal and 1’s on the first superdiagonal. Then we have: <div class='html-disp-formula-info'><div class='html_pics'><img style='max-width:%' data-large='/uploads/2024/06/12/808aec4b90d26b71a430c12d1dd119af.png' data-original='/uploads/2024/06/12/808aec4b90d26b71a430c12d1dd119af.png' src='/uploads/2024/06/12/808aec4b90d26b71a430c12d1dd119af.png'></div><div class='formula'><label>(28)</label></div></div> <i>2.7. Initial Conditions for Differential Equation</i> In Section 2.5, we suggested that by starting with a complete tour by the drone that visits all sensors and “nudging” the drone’s path, we can find optimal solutions for shorter and shorter path lengths. Unfortunately, the matrix <i>H</i> in (25) is singular when $$(u_{j},v_{j})=(x_{j},y_{j}),j=1....J$$, which corresponds exactly to the case of a complete tour. So, we cannot use this solution as an initial condition. Fortunately, we can address this problem by choosing a solution where the (<i>u<sub>j</sub></i>, <i>v<sub>j</sub></i>) is slightly offset from (<i>x<sub>j</sub></i>, <i>y<sub>j</sub></i>) for all <i>j</i>, i.e., <div class='html-disp-formula-info'><div class='html_pics'>```latex\begin{pmatrix}u_j,v_j\end{pmatrix}=\begin{pmatrix}x_j,y_j\end{pmatrix}+\vec{\epsilon}_j.```</div><div class='formula'><label>(29)</label></div></div> We need to choose the { $$\vec{\epsilon}_{J}$$ } in such a way that the Lagrange multiplier conditions (7) are satisfied. We also need to choose { $$\vec{\epsilon}_{J}$$} such that the path joining the {(<i>u<sub>j</sub></i>, <i>v<sub>j</sub></i>)} is smaller than the full tour. The gradient of <i>f</i>($$\vec{u},\vec{v}$$) evaluated at the point for the initial point given by (29) is given by: <div class='html-disp-formula-info'><div class='html_pics'>```latex\begin{gathered}\nabla f(u_{j},v_{j})=p\left(\left(x_{j}-u_{j}\right)^{2}+\left(y_{j}-v_{j}\right)^{2}\right)\left[(x_{j}-u_{j}),\left(y_{j}-v_{j}\right)\right] \\=p\big|\overrightarrow{\epsilon}_{j}\big|^{p-2}\overrightarrow{\epsilon}_{j} \\=p\big|\overrightarrow{\epsilon}_{j}\big|^{p-1}\widehat{\epsilon}_{j} \end{gathered}```</div><div class='formula'><label>(30)</label></div></div> where $$\widehat{\epsilon}_{J}$$ is the unit vector in the direction of $$\vec{\epsilon}$$. The Lagrange multiplier condition (7) gives: <div class='html-disp-formula-info'><div class='html_pics'>```latexp\big|\vec{\epsilon}_{j}\big|^{p-1}\widehat{\epsilon}_{j}=\lambda\nabla_{j}g(\vec{u},\vec{v}),```</div><div class='formula'><label>(31)</label></div></div> where <div class='html-disp-formula-info'><div class='html_pics'>```latex\nabla_{j}g(\vec{u},\vec{v}):=(\frac{\partial g}{\partial u_{j}},\frac{\partial g}{\partial v_{j}})```</div><div class='formula'><label>(32)</label></div></div> Since $$g(\vec{u},\vec{v})$$ is smooth in the vicinity of $$(\vec{u},\vec{v})\approx(\vec{x},\vec{y})$$, we may approximate: <div class='html-disp-formula-info'><div class='html_pics'>```latex\nabla_{j}g(\vec{u},\vec{v})\approx\nabla_{j}g(\vec{u},\vec{v})|_{\vec{u}=\vec{x}},```</div><div class='formula'><label>(33)</label></div></div> Which may be evaluated using (14) and (15). Denoting the right-hand side of (33) as $$\vec{g_{J}}$$, we have from (31) <div class='html-disp-formula-info'><div class='html_pics'>```latexp\left|\overrightarrow{\epsilon_{j}}\right|^{p-1}\widehat{\epsilon_{j}}=\lambda\overrightarrow{g_{j}}\\\Rightarrow\widehat{\epsilon_{J}}=\pm\widehat{g_{J}}\mathrm{~and}\left|\epsilon_{j}\right|=\left|\frac{\lambda}{p}\right|^{(\frac{1}{p-1})}\left|\overline{g_{J}}\right|^{(\frac{1}{p-1})}```</div><div class='formula'><label>(34)</label></div></div> Since we are interested in solutions for which g is reduced, we choose the negative sign in (34). Then $$\vec{\epsilon}_{J}$$ is uniquely determined by the values of $$\vec{g_{J}}$$ and λ. By choosing a small value of λ, we may obtain initial values for $$(\vec{u},\vec{v})$$ that are very close to $$(\vec{x},\vec{y})$$, so that the approximation in (33) holds a very high degree of accuracy. In this way, we obtain initial conditions for our differential Equation (25) for which <i>H</i> is not singular and can then apply standard numerical methods for solution. <i>2.8. Global Optimality for Sufficiently Long Drone Ranges</i> In Section 2.4, we posed the local optimality condition (7) from which the vector differential Equation (25) is derived. To show that a locally optimal solution is globally optimal, we would need to show that it improves over all other locally optimal solutions. We may establish this for the solutions described in Sections 2.5–2.7 for drone ranges that are less than but close to the travelling salesman tour length as follows. Here we give a brief outline of the proof; a more extended presentation is given in Appendix B. Every local optimal solution for a given drone path length will be part of a homotopy of solutions that may be parametrized by path length. As path length increases in the homotopy, the energy consumption decreases until a minimum energy consumption is reached for the entire homotopy. This minimum energy is necessarily nonnegative—and if it is 0, then the homotopy must terminate at a tour that joins all of the cluster heads. The shortest cluster head tour (i.e., the travelling salesman solution) will be the unique optimum in the case when the drone path length is equal to this shortest tour. It follows that for sufficiently long drone path lengths, the solution that belongs to the homotopy that includes the travelling salesman solution will be the unique global optimum. This justifies our claim that the solution of (5) calculated using the homotopy approach outlined in Sections 2.5–2.7 is optimal for sufficiently long drone ranges. The limited nature of this proof does not necessarily mean that the solution we have presented is not globally optimal for shorter drone ranges: global optimality is notoriously difficult to establish rigorously, except in the case where the function to be optimized has nice properties such as convexity. Nonetheless, the proof adds credibility to the expectation that the obtained solution has a strong likelihood of being not just locally optimal but also globally optimal. <i>2.9. Implementation in Python</i> As described above, the algorithm has two phases. First, an initial ordering of cluster heads is determined, such that the length of a tour joining the cluster heads in this order is minimized among all possible orderings. Once the ordering is set, the homotopy of solutions is computed using the initial conditions and system of differential equations described in Sections 2.7 and 2.5. The final path with the desired path length is selected from the homotopy. For the first phase, the shortest tour joining cluster heads is found using the travelling salesman algorithm as implemented in the python-tsp package. This gives a set of ordered cluster head points, that is, (<i>x<sub>j</sub></i>,<i>y<sub>j</sub></i>) re-arranged appropriately. For the second phase, the homotopy solution is computed according to the following steps: Step 0: Initialize cluster head locations, initial value of λ, and step size h (typically on the order of 0.1), Step 1: Find a minimal initial path joining the cluster head points using a travelling salesman algorithm. Step 2: Determine the initial points of the closest approach to be a small distance away from the cluster head points, according to the algorithm described in Section 2.7. Step 3: Solve the homotopy Equations (25) numerically. Initially, we used the odeint solver from the scipy package but encountered instabilities when the path vertices began to merge. We succeeded better using a Runge Kutta-4 code obtained from the web and modified for our purpose. Appendix A gives a more detailed description of the code as well as a link to a Github page where the code can be downloaded. <i>2.10. Specification of Test Cases</i> The Python implementation of the algorithm was tested by simulating a number of different cluster head configurations, with various numbers of cluster heads and drone starting positions. The test configurations used have the following cluster head position: <i>Case 1:</i> [(2, 1), (2, 4), (6, 4), (6, 1)] <i>Case 2:</i> [(2, 1), (2, 4), (8, 2), (6, 4), (6, 1)] <i>Case 3:</i> [(2, 1), (2, 4), (8, 2), (6, 4), (6, 1)] <i>Case 4:</i> [(2, 1), (2, 4), (8, 2), (6, 4), (6, 1), (7, 3.5), (1, 2.5)] <i>Case 5:</i> [(2,1), (2, 4), (8, 2), (6, 4), (6, 1), (7, 3.5), (1, 2.5), (3,6)] <i>Case 6:</i> [(2,1), (2, 4), (8, 2), (6, 4), (6.5, 1.5), (7, 3.5), (1, 2.5), (3,6), (3,1), (5,0.5)] <i>Case 7:</i> [(0.5,1), (2, 4), (8, 2), (9, 4), (6.5, 1.5), (7, 3.5), (1, 2.5), (3,6), (3,1), (5,0.5),(7.5,6), (4,8.5), (5.5,10)] <i>Case 8:</i> [(0.5,1), (2, 4), (8, 2), (9, 4), (6.5, 1.5), (7, 3.5), (1, 2.5), (3,6), (3,1), (5,0.5),(7.5,6), (4,8.5), (5.5,10), (3.5,12)] <i>Case 9:</i> [(0.5,1), (2, 4), (8, 2), (9, 4), (6.5, 1.5), (7, 3.5), (1, 2.5), (3,6), (3,1), (5,0.5),(7.5,6), (4,8.5), (5.5,10), (3.5,12), (2.25,10)] <i>Case 10:</i> [(0.5,1), (2, 4), (8, 2), (9, 4), (6.5, 1.5), (7, 3.5), (1, 2.5), (3,6), (3,1), (5,0.5),(7.5,6), (4,8.5), (5.5,10), (3.5,12), (2.25,10), (6.25,16)] <i>Case 11: </i>[(0.5,1), (2, 4), (8, 2), (9, 4), (6.5, 1.5), (7, 3.5), (1, 2.5), (3,6), (3,1), (5,0.5),(7.5,6), (4,8.5), (5.5,10), (3.5,12), (2.25,10), (6.25,16), (7,11)] These configurations were chosen manually so as to have homotopy solutions that are easily visible as well as to be sufficiently similar so that trends in the homotopy as the number of points increases are also visible. All cases used a transmission power loss exponent of 2, with the finishing position of drone equal to (0,0). The drone path starting point is (0,0), except for Case 3 in which the starting point is (3,1). For each configuration, the travelling salesman tour was computed, as well as the homotopy of solutions obtained when the drone path length <i>L</i> is decreased from the travelling salesman tour length down to the minimum path joining the tour starting and ending point. A step size of 0.1 was used for the numerical solution for all cases. </div> <h2 class="border-bottom"> <a id="link-theory-calculation" class="anchor-66"></a> 3. Results </h2> <div class="link-theory-calculation article-item-text"><a href='#Figure2' class='html-fig html-figpopup'>Figure 2</a>, <a href='#Figure3' class='html-fig html-figpopup'>Figure 3</a> and <a href='#Figure4' class='html-fig html-figpopup'>Figure 4</a> display results from simulations of the test cases described in Section 2.10 using the Python code described in Appendix A. <a href='#Figure2' class='html-fig html-figpopup'>Figure 2</a> contains a 6 × 2 grid of plots that shows results from the test scenarios listed above. Each plot shows solutions in the homotopy corresponding to different drone path lengths. The longest path in each homotopy is the travelling-salesman path that joins the cluster heads; while the shortest is the straight-line path that joins starting and ending points. The algorithm computes the vertices from longest path to shortest, according to the ODE in equation (25) with initial conditions $$(\vec{u},\vec{v})=(\vec{x},\vec{y})$$, where the (<i>x<sub>j</sub></i>,<i>y<sub>j</sub></i> ) are in travelling salesman order. Initially, the paths roughly preserve the original shape as they shrink (in fact, it can be shown that as the path shrinks, the path vertices always move in the direction of the angle bisectors of the path polygon.) After several iterations, path vertices merge: for example, the first figure in the first row starts with a path containing 5 segments, which eventually becomes 4 and then 3 segments as the path length shrinks. Similar changes occur in the other figures. The left-hand graph in <a href='#Figure3' class='html-fig html-figpopup'>Figure 3</a> plots the difference between the travelling salesman tour length and the length of the drone’s path (which for simplicity, we denote as the “path defect”) as a function of the iteration number in the ODE solution, for each of the test cases. The initial path length is equal to the tour length; hence, all graphs start from (0,0). The path defect increases more rapidly for scenarios with more cluster heads and longer travelling salesman tour lengths. For all scenarios, the rate of increase of path defect slows as the number of iterations increases. Eventually, the curves become flat when the homotopy reaches the minimum path that joins (<i>u</i><sub>0</sub>,<i>v</i><sub>0</sub> ) and (<i>u</i><sub><i>J</i>+1</sub>,<i>v</i><sub><i>J</i>+1</sub>). The right-hand graph in <a href='#Figure3' class='html-fig html-figpopup'>Figure 3</a> shows the WSN’s energy expenditure as a function of step number. As expected, this increases with iteration number as the path length decreases. There are noticeable bends in both graphs, which occur at the same iteration number. For example, in the curves for test-7, test-8 and test-9 there are concurrent bends in both the defect curve and the total energy curve, which occur near iteration numbers 75, 125, and 150, respectively. In the homotopy, the bend indicates the merger of two path vertices so that two cluster heads both correspond to a single vertex. This shows that vertex mergers slow down the algorithm’s progress. The tradeoff between drone path length and energy expenditure is more clearly shown in <a href='#Figure4' class='html-fig html-figpopup'>Figure 4</a>, which plots the <i>p</i>’th root of cluster head energy consumption on the vertical axis versus cluster head tour length minus drone path length on the horizontal axis. In our simulations <i>p</i> = 2, so the <i>p</i>’th root of energy is the ℓ<sup>2</sup> norm of the vector $$[|\vec{z}_{1}-\vec{w}_{1}|,\ldots,|\vec{z}_{J}-\vec{w}_{J}|]$$ consisting of distances between cluster heads and corresponding drone path vertices. In the case where all distances $$|\vec{z}_{j}-\vec{w}_{j}|$$ are approximately equal, then the <i>ℓ</i><sup>2</sup> norm is nearly proportional to the mean distance between the cluster head and the corresponding drone vertex. The linear section of the graphs in <a href='#Figure4' class='html-fig html-figpopup'>Figure 4</a> indicates an initial linear dependence of the distance between cluster heads and drone vertices as the path defect increases. However, as the path defect increases (corresponding to a decrease in drone range), the dependence of total energy on path length becomes noticeably convex. Unlike the energy versus iteration and path defect versus iteration curves in <a href='#Figure3' class='html-fig html-figpopup'>Figure 3</a>, there are no bends in these curves. This indicates that the bends reflect convergence issues for the numerical solution for the homotopy rather than a change in the trends in energy over the homotopy as the drone range is varied. <a href='#Figure5' class='html-fig html-figpopup'>Figure 5</a> represents different runtime characteristics associated with the numerical solution of equation (15) for different numbers of cluster heads and different drone ranges. The three panels in <a href='#Figure5' class='html-fig html-figpopup'>Figure 5</a> represent the total runtime, number of Runge-Kutta iterations, and runtime per iteration for the 12 scenarios shown in <a href='#Figure2' class='html-fig html-figpopup'>Figure 2</a> for four different drone ranges, plotted as a function of the number of vertices in the solution path. For each of the 12 scenarios, we chose four evenly-spaced drone ranges of 0.2, 0.4, 0.6, and 0.8 times the minimum range required to reduce the objective function $$f(\vec{u},\vec{v})$$ to 0, which is equal to the length of the travelling salesman path joining the points {(<i>x<sub>j</sub></i>,<i>y<sub>j</sub></i>)}. The graphs show gradual increases in runtime as the number of cluster heads increases. The runtime per iteration does increase for more cluster heads (as expected, since more variables must be solved for), but this increase is offset by a concurrent general decrease in the number of iterations required for each drone range. Although the full algorithm requires the initial solution of a travelling salesman problem in addition to the solution of (15), we do not include the runtimes for the travelling salesman problem in <a href='#Figure5' class='html-fig html-figpopup'>Figure 5</a>. It is well known that an exact solution depends exponentially on the number of vertices. However, there are many algorithms with lower complexity (including both stochastic and heuristic algorithms) that can be used to obtain near-optimal tours. <div class='html-fig-wrap'><div class='html-fig_img'><div class='html-figpopup html-figpopup-link' href='#Figure2'><img data-large='/uploads/2024/06/12/a5109c54f4a2ce6fdf4e7318a7173592.jpg' data-original='/uploads/2024/06/12/a5109c54f4a2ce6fdf4e7318a7173592.jpg' src='/uploads/2024/06/12/a5109c54f4a2ce6fdf4e7318a7173592.jpg'><a class='html-expand html-figpopup' href='#Figure2'></a></div></div><div class='html-fig_description'><b><a href='#Figure2' class='html-fig html-figpopup'>Figure 2</a>. </b>Drone path homotopy solutions for 1 different test scenarios. The cluster head positions are indicated by X’s. The different colored lines are drone path solutions for different values of maximum drone range, with the drone start and end points as indicated.</div></div><div class='html-fig-wrap'><div class='html-fig_img'><div class='html-figpopup html-figpopup-link' href='#Figure3'><img data-large='/uploads/2024/06/12/f1d96297becc99ae521c96526f0c4955.png' data-original='/uploads/2024/06/12/f1d96297becc99ae521c96526f0c4955.png' src='/uploads/2024/06/12/f1d96297becc99ae521c96526f0c4955.png'><a class='html-expand html-figpopup' href='#Figure3'></a></div></div><div class='html-fig_description'><b><a href='#Figure3' class='html-fig html-figpopup'>Figure 3</a>. </b>(<b>a</b>) Path defect (defined as the length of a tour of the cluster heads minus the length of the drone path) plotted as a function of number of iterations in the numerical solution of the matrix differential Equation (25). (<b>b</b>) Total energy expended by sensors for a single tour, as a function of iteration number. Both graphs show results for 2000 iterations for the 12 test scenarios shown in <a href='#Figure2' class='html-fig html-figpopup'>Figure 2</a>.</div></div><div class='html-fig-wrap'><div class='html-fig_img'><div class='html-figpopup html-figpopup-link' href='#Figure4'><img data-large='/uploads/2024/06/12/3c3e3e6e5a713aa5874ea9b94856f64f.png' data-original='/uploads/2024/06/12/3c3e3e6e5a713aa5874ea9b94856f64f.png' src='/uploads/2024/06/12/3c3e3e6e5a713aa5874ea9b94856f64f.png'><a class='html-expand html-figpopup' href='#Figure4'></a></div></div><div class='html-fig_description'><b><a href='#Figure4' class='html-fig html-figpopup'>Figure 4</a>. </b>(total energy)<sup>1/<i>P</i></sup> plotted as a function of path defect (defined as the TSP tour length minus the drone path length) for the 12 scenarios shown in <a href='#Figure2' class='html-fig html-figpopup'>Figure 2</a>.</div></div><div class='html-fig-wrap'><div class='html-fig_img'><div class='html-figpopup html-figpopup-link' href='#Figure5'><img data-large='/uploads/2024/06/12/c5df438e6a809d9c9682f739d044244a.png' data-original='/uploads/2024/06/12/c5df438e6a809d9c9682f739d044244a.png' src='/uploads/2024/06/12/c5df438e6a809d9c9682f739d044244a.png'><a class='html-expand html-figpopup' href='#Figure5'></a></div></div><div class='html-fig_description'><b><a href='#Figure5' class='html-fig html-figpopup'>Figure 5</a>. </b>(<b>a</b>) Run times for the Runge-Kutta ODE for the 12 scenarios shown in <a href='#Figure2' class='html-fig html-figpopup'>Figure 2</a>, plotted as a function of the number of cluster heads (equal to the number of path vertices), for different drone ranges. The drone range for each scenario is specified as a fraction of the length of the travelling salesman path joining the cluster heads. The four curves correspond to drone ranges equal to 20%, 40%, 60%, and 80% of the travelling salesman path (longer drone ranges take less time to compute). (<b>b</b>) Number of iterations (with step size <i>h</i> = 0.1) required for the Runge-Kutta algorithm to compute solutions with the specified drone ranges. (<b>c</b>) Execution time per iteration for the same set of solutions as the other two graphs. All simulations were performed using Google Colab.</div></div></div> <h2 class="border-bottom"> <a id="link-results" class="anchor-66"></a> 4. Conclusions </h2> <div class="link-results article-item-text">The solution described above for finding optimal drone information-harvesting paths is locally and globally optimal for sufficiently long drone ranges. The numerical solution algorithm executes quickly enough that it can be implemented in real-time, and execution time grows slowly with the size of the system. The solution can be used either to optimize total transmit power consumption and maximum power consumption by cluster heads. However, there are limitations in that the speed of execution slows considerably when the drone range decreases below a certain point (i.e., when path vertices begin to merge), and global optimality for comparatively short drone ranges is uncertain.</div> <h2 class="border-bottom"> <a id="link-discussion" class="anchor-66"></a> 5. Future Work </h2> <div class="link-discussion article-item-text">The following future work is proposed in order to improve upon this research. <ul><li>The proposed algorithm supposes that the cluster head positions are predetermined. Alternatively, it is possible to use the algorithm as a component in a more comprehensive algorithm that does co-optimization of cluster head positions and drone path in systems where alternative cluster heads are a possibility.</li> <li>Equation (5) does not take into account various environmental factors such as obstacles or wind speed. It is also not robust to possible sensor node failures. The equation would need to be elaborated to include terms that reflect these factors. Also, the equations are limited to optimization criteria <i>O</i><sub>1</sub> and <i>O</i><sub>2</sub>. Different optimization criteria can be accommodated by modifying the Equation (1) for the function $$f(\vec{u},\vec{v})$$, which then requires recalculation of the partial derivatives $$\frac{\partial f}{\partial u_{j}}$$ and $$\frac{\partial f}{\partial v_{j}}$$ which appear in Equations (9) and following. </li> <li>The numerical homotopy solution code has not been fully optimized to decrease execution times. In particular, existing solver packages and/or variable step-size solution algorithms may be explored. In addition, we have remarked that the algorithms slow down after drone path vertex mergers. Future work may explore ways to avoid this slowdown. One possibility is to modify the algorithm so that when path vertices merge, the two associated cluster heads may be replaced by a single virtual cluster head that produces the same power loss. Then, the homotopy solution can be continued with vectors $$\vec{u}$$, $$\vec{v}$$ that each have one less component.</li> <li>The algorithm can be modified to accommodate moving cluster heads, by expressing $$\vec{x}$$,$$\vec{y}$$,$$\vec{u}$$, and $$\vec{v}$$ as functions of time <i>t</i>, and then inverting the time dependence of $$\vec{u}$$ and $$\vec{v}$$ to obtain $$\vec{x}$$ and $$\vec{y}$$ as functions of $$\vec{u}$$ and $$\vec{v}$$. Then the same homotopy approach can be used with modified equations for the derivatives of $$\left\{a_{j}\right\}_{j=1...J}$$ and $$\{b\}_{j=1...J}$$ in (13) and following.</li> <li>Further explorations of the question of global optimality may be pursued. As the proof in Appendix B shows, any globally optimal solution must be part of a homotopy that includes some ordering of the cluster head points. It follows that in some cases, better solutions may be found by computing homotopies for different orderings of the cluster heads.</li></ul> </div> <div class="link-conclusions article-item-text"></div> <div class="link-supplementary-materials article-item-text"></div> <h2 class="border-bottom"> <a id="link-appendix" class="anchor-66"></a> Appendix A. Python Implementation </h2> <div class="link-appendix article-item-text"><i>Appendix A.1. Link to Code</i> The Python code used to generate the figures shown in Section 3 is available at: https://github.com/ganap-ram/drone. <i>Appendix A.2. Implemented Equations</i> This section describes the differential equations used to solve as implemented in the Python code. Although the implementation is mathematically equivalent to the description in Section 2.5, the notation used is somewhat different. For notational and coding simplicity, we define some intermediate variables: <div class='html-disp-formula-info'><div class='html_pics'>```latexu_{j},v_{j}=j^{th}\mathrm{turning~point~of~drone~j=1~...J}\\a_{j}=u_{j}-x_{j}\\b_{j}=v_{j}-y_{j}\\A_{j}=a_{j}^{2}+b_{j}^{2}\\m_{j}=u_{j}-u_{j+1}\\n_{j}=v_{j}-v_{j+1}\\M_{j}=m_{j}^{2}+n_{j}^{2}\\H_{j}=M_{j}^{3/2}\\q=\frac{p}{2}-1\\r=1/2```</div><div class='formula'></div></div> The following are the various coefficient values of the derivatives in the matrix: <div class='html-disp-formula-info'><div class='html_pics'>```latex\begin{gathered}S_{j1}=\lambda\frac{M_{j-1}-m_{j-1}^{2}}{H_{j-1}} \\S_{j2}=-\lambda\frac{m_{j-1}n_{j-1}}{H_{j-1}} \\S_{j3}=2pqa_{j}^{2}A_{j}^{q-1}+pA_{j}^{q-1}-\lambda\frac{H_{j}\Big(M_{j-1}-m_{j-1}^{2}\Big)+H_{j-1}(M_{j}-m_{j}^{2})}{H_{j-1}H_{j}} \\S_{j4}=2pqa_{j}b_{j}A_{j}^{q-1}+\lambda\frac{m_{j-1}n_{j-1}H_{j}+m_{j}n_{j}H_{j-1}}{H_{j-1}H_{j}} \\S_{j5}=\lambda\frac{M_{j}-m_{j}^{2}}{H_{j}} \\S_{j6}=-\lambda\frac{m_{j}n_{j}}{H_{j}} \end{gathered}```</div><div class='formula'></div></div> <div class='html-disp-formula-info'><div class='html_pics'>```latex\begin{gathered}w_{j}= \frac{-m_{j-1}\sqrt{M_{j}}+m_{j}\sqrt{M_{j-1}}}{\sqrt{M_{j-1}M_{j}}} \\t_{j1}=-\lambda\frac{m_{j-1}n_{j-1}}{H_{j-1}} \\t_{j2}=\lambda\frac{M_{j-1}-n_{j-1}^{2}}{H_{j-1}} \\t_{j3}=2pqa_{j}b_{j}A_{j}^{q-1}+\lambda\frac{m_{j-1}n_{j-1}H_{j}+m_{j}n_{j}H_{j-1}}{H_{j-1}H_{j}} \\t_{j4}=2pqb_{j}^{2}A_{j}^{q-1}+pA_{j}^{q}-\lambda\frac{H_{j}\big(M_{j-1}-n_{j-1}^{2}\big)+H_{j-1}(M_{j}-n_{j}^{2})}{H_{j-1}H_{j}} \\t_{j5}=-\lambda\frac{m_{j}n_{j}}{H_{j}} \\t_{j6}=\lambda\frac{M_{j}-n_{j}^{2}}{H_{j}} \\z_{j}=\frac{-n_{j-1}\sqrt{M_{j}}+n_{j}\sqrt{M_{j-1}}}{\sqrt{M_{j-1}M_{j}}} \end{gathered}```</div><div class='formula'></div></div> And the differential equations have the form (j = 1 . . . J): <div class='html-disp-formula-info'><div class='html_pics'>```latex\begin{gathered}s_{j1}\frac{du_{j-1}}{ds}+s_{j2}\frac{dv_{j-1}}{ds}+s_{j3}\frac{du_{j}}{ds}+s_{j4}\frac{dv_{j}}{ds}+s_{j5}\frac{du_{j+1}}{ds}+s_{j6}\frac{dv_{j+1}}{ds}-c1\frac{d\lambda}{ds}=0 \\t_{j1}\frac{du_{j-1}}{ds}+t_{j2}\frac{dv_{j-1}}{ds}+t_{j3}\frac{du_{j}}{ds}+t_{j4}\frac{dv_{j}}{ds}+t_{j5}\frac{du_{j+1}}{ds}+t_{j6}\frac{dv_{j+1}}{ds}-c2\frac{d\lambda}{ds}=0 \\\frac{dg}{ds}=-1\Rightarrow\sum_{j=1}^{J}\left(\frac{\partial g}{\partial u_{j}}\frac{du_{j}}{ds}+\frac{\partial g}{\partial u_{j}}\frac{dv_{j}}{ds}\right)=-1 \end{gathered}```</div><div class='formula'></div></div> This is represented in the matrix notation as: <div class='html-disp-formula-info'><div class='html_pics'>```latexKD=C```</div><div class='formula'></div></div> where: <div class='html-disp-formula-info'><div class='html_pics'><img style='max-width:%' data-large='/uploads/2024/06/12/ca1e2262255466537e43ee848cc2aadb.png' data-original='/uploads/2024/06/12/ca1e2262255466537e43ee848cc2aadb.png' src='/uploads/2024/06/12/ca1e2262255466537e43ee848cc2aadb.png'></div><div class='formula'></div></div> </div> <h2 class="border-bottom"> <a id="link-appendix-b" class="anchor-66"></a> Appendix B. Mathematical Proof of Global Optimality </h2> <div class="link-appendix-b article-item-text">In this appendix, we give a more extended presentation of the argument outlined in Section 2.8, which asserts that the homotopy solution found in Sections 2.5–2.7 is a globally optimal solution of (5) for drone ranges that are less than but close to the travelling salesman tour length. A completely rigorous mathematical argument would be tedious to present, but a step-by-step outline is as follows. Suppose first we restrict to drone path solutions such that (<i>u<sub>j</sub></i>,<i>v<sub>j</sub></i>) is in the same order of (<i>x<sub>j</sub></i>,<i>y<sub>j</sub></i> ), <i>j</i> = 1,…<i>J</i> where (<i>x<sub>j</sub></i>,<i>y<sub>j</sub></i>) is the travelling salesman order of cluster heads. Suppose also that $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ is a globally optimal solution for the drone path satisfying the constraint $$g\big(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\big)$$ = <i>L</i>. Any globally optimal solution of (5) is also locally optimal: so $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ is also locally optimal. Then $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ is part of a homotopy of solutions using the same construction we showed in Sections 2.5–2.7. The homotopy consists of locally optimal solutions $$\left(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\right)$$ satisfying $$g\big(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\big)$$ = <i>s</i>, where <i>s</i> can take values in a closed interval containing <i>L</i>. Define the function $$f_{(ts)}(s)=f\big(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\big)$$. The function <i>f</i><sub>(<i>ts</i>)</sub> decreases strictly as s increases, because if the drone path is lengthened, it is always possible to move closer to the cluster heads; and as long as <i>f</i><sub>(<i>ts</i>)</sub> (<i>s</i>) is positive, it is always possible to decrease <i>f<sub>I</sub></i> by increasing the path length. It follows that the minimum value of <i>f</i><sub>(<i>ts</i>)</sub> (<i>s</i>) on the homotopy cannot be positive, so $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ must be connected by a homotopy to ( $$\vec{x},\vec{y}$$) where the components of $$\vec{x}$$ and $$\vec{y}$$ are in travelling salesman order. So the solution in this homotopy whose length is equal to the travelling salesman tour length of cluster heads (denoted by $$L^{(ts)}$$) corresponds to a value of $$f_{(ts)}\big(L^{(ts)}\big)$$ = 0. Now, we consider solutions where (<i>u<sub>j</sub></i>,<i>v<sub>j</sub></i> ) receives the information from $$(x_{\sigma(j)},y_{\sigma(j)})$$ where <i>σ</i> is a permutation of (1,…<i>J</i>). By similar arguments as in the previous paragraph, any locally optimal solution corresponding to a path length <i>L</i> is part of a homotopy $$\left(\vec{u}^{(\sigma)}(s),\vec{v}^{(\sigma)}(s)\right)$$ with associated strictly decreasing function $$f_{\sigma}(s):=f\big(\vec{u}_{\sigma}(s),\vec{v}_{\sigma}(s)\big)$$, which includes a solution $$\left(\vec{u}^{(\sigma)}\big(L^{(\sigma)}\big),\vec{v}^{(\sigma)}\big(L^{(\sigma)}\big)\right)$$ for path length $$L^{(\sigma)}>L$$ such that $$f_{\sigma}\big(L^{(\sigma)}\big)=0$$. But this implies that $$\left(\vec{u}^{(\sigma)}\big(L^{(\sigma)}\big)_{j^{\prime}},\vec{v}^{(\sigma)}\big(L^{(\sigma)}\big)_{j}\right)=\big(x_{\sigma(j)},y_{\sigma(j)}\big)$$,<i>j</i> = 1,…<i>J</i>, which in turn implies that $$L^{(\sigma)}$$ is the length of the tour of the points $$\left\{\left(x_{j},y_{j}\right)\right\}_{j=1...J}$$ in the order given by <i>σ</i>. This means that $$L^{(\sigma)}\geq L^{(ts)}$$, and $$L^{(\sigma)}=L^{(ts)}$$ if and only if <i>σ</i> gives a travelling salesman ordering of the nodes in $$\vec{x},\vec{y}$$. Since the function <i>f</i><sub>σ</sub>(<i>s</i>) is strictly decreasing, it follows that $$f_\sigma(L^{(ts)})$$ > $$f_{opt}(L^{(ts)}$$ for all permutations σ for which $$(x_{\sigma(j)},y_{\sigma(j)})$$ is not a travelling salesman permutation. Let $$\tilde{f}:=\min_{\sigma\neq I}f_\sigma $$, where the minimum is taken over all non-travelling salesman permutations. Then we also have $$\tilde{f}\big(L^{(ts)}\big)>f_{(ts)}(L^{(ts)})$$. It follows by continuity that there is an $$\tilde{L}$$ with 0 < $$\tilde{L}$$ < $$L^{(ts)}$$ such that $$\tilde{f}(s)>f_{(ts)}(s)$$ for $$\tilde{L}\leq s\leq L$$. In other words, the solution $$\begin{pmatrix}\vec{u}^{(I)}(s),\vec{v}^{(I)}(s)\end{pmatrix}$$ is a local optimum such that $$f\left(\vec{u}^{(I)}(s),\vec{v}^{(I)}(s)\right)$$ is less than the value of f for any other local optimum. It follows that $$\left(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\right)$$ is a global optimum for $$\tilde{L}$$ < s $$\leq L^{(ts)}$$. Note that this proof does not give a practical, constructive method for finding $$\tilde{L}$$ it only shows that it exists. However, the proof does indicate that any global optimum will be part of some homotopy that includes the points {(<i>x<sub>j</sub></i>,<i>y<sub>j</sub></i>)},<i>j</i> = 1…<i>J</i> in some order. This fact indicates that other candidate global optimal solutions can be found by creating homotopies starting from other (non-travelling salesman) tours of the cluster heads points. </div> <h2 class="border-bottom"> <a id="link-acknowledgments" class="anchor-66"></a> Acknowledgments </h2> <div class="link-acknowledgments article-item-text">The authors wish to thank Dr. Aristide Tsemo for his thorough review of the equations in Section 2.6, which resulted in several corrections. We also wish to thank the reviewers of this paper, who made several valuable suggestions for improvements.</div> <h2 class="border-bottom"> <a id="link-author-contributions" class="anchor-66"></a> Author Contributions </h2> <div class="link-author-contributions article-item-text">Conceptualization, R.G. and C.T.; Methodology, R.G. and C.T.; Software, R.G.; Validation, R.G. and C.T.; Formal Analysis, R.G. and C.T.; Investigation, R.G. and C.T.; Writing—Original Draft Preparation, R.G. and C.T.; Writing—Review & Editing, R.G. and C.T.; Visualization, R.G. and C.T.; Supervision, C.T.</div> <h2 class="border-bottom"> <a id="link-ethics-statement" class="anchor-66"></a> Ethics Statement </h2> <div class="link-ethics-statement article-item-text">Not applicable.</div> <h2 class="border-bottom"> <a id="link-informed-consent-statement" class="anchor-66"></a> Informed Consent Statement </h2> <div class="link-informed-consent-statement article-item-text">Not applicable.</div> <h2 class="border-bottom"> <a id="link-funding" class="anchor-66"></a> Funding </h2> <div class="link-funding article-item-text">This research received no external funding.</div> <h2 class="border-bottom"> <a id="link-declaration-competing-interest" class="anchor-66"></a> Declaration of Competing Interest </h2> <div class="link-declaration-competing-interest article-item-text">The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.</div> <h2 class="border-bottom"> <a id="html-references_list" class="anchor-66"></a> References </h2> <div class="references_zt"> <div class="references_at"> <div class="references html-x" id='B1'> <div class="references_sup">1.</div> <div class="references_name"> Nguyen MT, Nguyen CV, Do HT, Hua HT, Tran TA, Nguyen AD, et al. UAV-assisted data collection in wireless sensor networks: A comprehensive survey.<i> Electronics</i><b> 2021</b>,<i> 10,</i> 2603. <span class="tages-text">[<a href="https://scholar.google.com/scholar_lookup?title=UAV-assisted data collection in wireless sensor networks: A comprehensive survey.&publication_year=2021&author=Nguyen MT&author=Nguyen CV&author=Do HT&author=Hua HT&author=Tran TA&author=Nguyen AD&author=et al. " target="_blank">Google Scholar</a>]</span> </div> </div> <div class="references html-x" id='B2'> <div class="references_sup">2.</div> <div class="references_name"> Wei Z, Zhu M, Zhang N, Wang L, Zou Y, Meng Z, et al. UAV-assisted data collection for internet of things: A survey.<i> IEEE Int. Things J.</i><b> 2022</b>,<i> 9,</i> 15460–15483. <span class="tages-text">[<a href="https://scholar.google.com/scholar_lookup?title=UAV-assisted data collection for internet of things: A survey.&publication_year=2022&author=Wei Z&author=Zhu M&author=Zhang N&author=Wang L&author=Zou Y&author=Meng Z&author=et al. " target="_blank">Google Scholar</a>]</span> </div> </div> <div class="references html-x" id='B3'> <div class="references_sup">3.</div> <div class="references_name"> Memos VA, Psannis KE. UAV-based smart surveillance system over a wireless sensor network.<i> IEEE Commun. Stand. Mag.</i><b> 2021</b>,<i> 5,</i> 68–73. <span class="tages-text">[<a href="https://scholar.google.com/scholar_lookup?title=UAV-based smart surveillance system over a wireless sensor network.&publication_year=2021&author=Memos VA&author=Psannis KE. " target="_blank">Google Scholar</a>]</span> </div> </div> <div class="references html-x" id='B4'> <div class="references_sup">4.</div> <div class="references_name"> Qadir Z, Zafar MH, Moosavi SKR, Le KN, Tam VW. Optimizing UAV path for disaster management in smart cities using metaheuristic algorithms. In <i>Computational Intelligence for Unmanned Aerial Vehicles Communication Networks</i>; Springer International Publishing: Cham, Switzerland, 2022; pp. 225–244. </div> </div> <div class="references html-x" id='B5'> <div class="references_sup">5.</div> <div class="references_name"> Qadir Z, Zafar MH, Moosavi SKR, Le KN, Mahmud MP. Autonomous UAV path-planning optimization using metaheuristic approach for predisaster assessment.<i> IEEE Int. Things J. </i><b> 2021</b>,<i> 9,</i> 12505–12514. <span class="tages-text">[<a href="https://scholar.google.com/scholar_lookup?title=Autonomous UAV path-planning optimization using metaheuristic approach for predisaster assessment.&publication_year=2021&author=Qadir Z&author=Zafar MH&author=Moosavi SKR&author=Le KN&author=Mahmud MP. " target="_blank">Google Scholar</a>]</span> </div> </div> <div class="references html-x" id='B6'> <div class="references_sup">6.</div> <div class="references_name"> Dac-Tu H, Esten IG, Tor AJ. Heuristic algorithm and cooperative relay for energy efficient data collection with a UAV and WSN. In Proceedings of the 2013 International Conference on Computing, Management and Telecommunications (ComManTel), Ho Chi Minh City, Vietnam, 21–24 January 2013, pp. 346–351. </div> </div> <div class="references html-x" id='B7'> <div class="references_sup">7.</div> <div class="references_name"> Liu S, Wei Z, Guo Z, Yuan X, Feng Z,  Performance analysis of UAVs assisted data collection in wireless sensor network. In Proceedings of the 2018 IEEE 87th Vehicular Technology Conference (VTC Spring), Porto, Portugal, 3–6 June 2018, pp. 1–5. </div> </div> <div class="references html-x" id='B8'> <div class="references_sup">8.</div> <div class="references_name"> Gong J, Chang TH, Shen C, Chen X. Flight time minimization of UAV for data collection over wireless sensor networks.<i> IEEE J. Sel. Areas Commun. </i><b> 2018</b>,<i> 36,</i> 1942–1954. <span class="tages-text">[<a href="https://scholar.google.com/scholar_lookup?title=Flight time minimization of UAV for data collection over wireless sensor networks.&publication_year=2018&author=Gong J&author=Chang TH&author=Shen C&author=Chen X. " target="_blank">Google Scholar</a>]</span> </div> </div> <div class="references html-x" id='B9'> <div class="references_sup">9.</div> <div class="references_name"> Skiadopoulos K, Giannakis K, Tsipis A, Oikonomou K. Impact of drone route geometry on information collection in wireless sensor networks.<i> Ad. Hoc. Netw. </i><b> 2020</b>,<i> 106,</i> 102220. <span class="tages-text">[<a href="https://scholar.google.com/scholar_lookup?title=Impact of drone route geometry on information collection in wireless sensor networks.&publication_year=2020&author=Skiadopoulos K&author=Giannakis K&author= Tsipis A&author=Oikonomou K." target="_blank">Google Scholar</a>]</span> </div> </div> <div class="references html-x" id='B10'> <div class="references_sup">10.</div> <div class="references_name"> Ho DT, Grøtli EI, Sujit PB, Johansen TA, De Sousa JB.Performance evaluation of cooperative relay and Particle Swarm Optimization path planning for UAV and wireless sensor network. In Proceedings of the 2013 IEEE Globecom Workshops (GC Wkshps), Atlanta, GA, USA, 9–13 December 2013, pp. 1403–1408. </div> </div> <div class="references html-x" id='B11'> <div class="references_sup">11.</div> <div class="references_name"> Zhu M, Wei Z, Qiu C, Jiang W, Wu H, Feng Z. Joint data collection and sensor positioning in multi-UAV-assisted wireless sensor network.<i> IEEE Sens. J.</i><b> 2023</b>,<i> 23,</i> 23664–23675. <span class="tages-text">[<a href="https://scholar.google.com/scholar_lookup?title=Joint data collection and sensor positioning in multi-UAV-assisted wireless sensor network.&publication_year=2023&author=Zhu M&author=Wei Z&author=Qiu C&author=Jiang W&author=Wu H&author=Feng Z. " target="_blank">Google Scholar</a>]</span> </div> </div> </div> </div> </div> </div> </div> </div> </div> </div> </section> <div class="modal fade cite-modal" id="citeModal" tabindex="-1" aria-labelledby="exampleModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-centered"> <div class="modal-content border-0"> <div class="modal-body pt-5 pl-5 pr-5 pb-4"> <h3 class="pb-2 border-bottom border-dark">Cite This Article</h3> <h6 class="mt-4 d-flex justify-content-between"> SCIEPublish Style </h6> <p class="modal-text2 text-justify">Ganapathy R, Thron C. Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network. <i>Drones and Autonomous Vehicles</i> <b>2024</b>, <i>1</i>, 10007. https://doi.org/10.35534/dav.2024.10007</p> <h6 class="mt-3 d-flex justify-content-between text-justify"> AMA Style </h6> <p class="modal-text2 text-justify">Ganapathy R, Thron C. Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network. <i>Drones and Autonomous Vehicles</i>. 2024; 1(3):10007. https://doi.org/10.35534/dav.2024.10007</p> </div> <button type="button" class="btn btn-close" data-dismiss="modal"> <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" fill="currentColor" class="bi bi-x-lg" viewBox="0 0 16 16"> <path d="M2.146 2.854a.5.5 0 1 1 .708-.708L8 7.293l5.146-5.147a.5.5 0 0 1 .708.708L8.707 8l5.147 5.146a.5.5 0 0 1-.708.708L8 8.707l-5.146 5.147a.5.5 0 0 1-.708-.708L7.293 8 2.146 2.854Z"></path> </svg> </button> </div> </div> </div> <div class="modal modal-amplification-img" id="imgModal" tabindex="-1" aria-labelledby="imgModal" aria-hidden="true"> <div class="modal-dialog modal-xl modal-dialog-centered modal-dialog-scrollable modal-dialog-img"> <div class="modal-content"> <button type="button" class="btn btn-close" data-dismiss="modal"> <svg xmlns="http://www.w3.org/2000/svg" width="20" height="20" fill="currentColor" class="bi bi-x-lg" viewBox="0 0 16 16"> <path d="M2.146 2.854a.5.5 0 1 1 .708-.708L8 7.293l5.146-5.147a.5.5 0 0 1 .708.708L8.707 8l5.147 5.146a.5.5 0 0 1-.708.708L8 8.707l-5.146 5.147a.5.5 0 0 1-.708-.708L7.293 8 2.146 2.854Z"></path> </svg> </button> <div class="modal-body"> </div> </div> </div> </div> <link rel="stylesheet" href="/static/css/share.min.css?3" /> <script src="/static/js/social-share.min.js"></script> <script> var $config = { image:"https://www.sciepublish.com/uploads/2024/06/12/0fe3c2eb112e8259bf5b994c458cfd90.png", origin:'', wechatQrcodeTitle: "WeChat Share", // WeChat QR code prompt text wechatQrcodeHelper: '<p>Scan QR code</p> <p>This article can be shared to your WeChat.</p>', }; socialShare('.social-share', $config); </script> <script> document.addEventListener("DOMContentLoaded", function() { /**/ var stopScroll = $(document).scrollTop(), column = $('.left-content'), fixedTitle = $('.fixed-title'), acquiesceTitle = $('.acquiesce-title'), acquiesceTitleTop = acquiesceTitle.offset().top; $(window).scroll(function(){ var scrollTop = $(this).scrollTop(); if(scrollTop > acquiesceTitleTop){ column.addClass('fixed'); fixedTitle.addClass('fixed'); }else{ column.removeClass('fixed'); fixedTitle.removeClass('fixed'); } }) if (stopScroll > acquiesceTitleTop ){ column.addClass('fixed'); fixedTitle.addClass('fixed'); } //Anchor navigation $('body').scrollspy({ target: '#article-menu-float' }) //tab switch $('.information-collapse').each(function(){ $(this).click(function(){ $(this).toggleClass('active').siblings().removeClass('active'); $(".information-item").eq($(this).index()).slideToggle().siblings().slideUp(); }) }) function markdownReplace(text) { // Replace the oblique body, bold it to HTML // /article/pii/21 text = text.replace(/</g, '<'); //article/pii/166 text = text.replace(/>/g, '>'); // text = text.replace(/\*\*(.+?)\*\*/g, "<b>$1</b>"); text = text.replace(/\*(.+?)\*/g, "<i>$1</i>"); // article/pii/18 text = text.replace(/&/g, '&');//* /article/pii/181#Figure5 中的* // text = text.replace(/\\\$/g, '$'); //article/pii/19 return text; } // Treatment of non -serial list function replaceConsecutiveBulletsWithList(text) { // Regular expression matching continuously with • starting line const regex = /^(?:•\s.*\n?)+/gm; // Replace the matching line, convert it to <ul> and <li> elements return text.replace(regex, (match) => { // Remove the • and the subsequent blank characters at the beginning of each line, and convert it to <li> element const listItems = match.split('\n').map(line => { return line.replace(/^•\s/, '').trim() ? `<li>${line.replace(/^•\s/, '').trim()}</li>` : ''; }).join(''); // If there is a list item, the package is wrapped in the <ul> label return `<ul>${listItems}</ul>`; }); } // Pre -predetermined formula rendering global indexes window.formula = {}; // Treatment to find a third -level and four -level title, sort out the P label that is not available in the text document.querySelectorAll('.article-item-text').forEach(element => { element.innerHTML = replaceConsecutiveBulletsWithList(element.innerHTML); // Forwards <em> 3.1. Serine Integrase-Mediated DNA Assembly Between Two Plasmids </em> element.innerHTML = element.innerHTML.replace(/(<h[1-6].+?>)/gi, '\r\n$1'); //TODO There is a change in the middle of the H tag to cause problems element.innerHTML = element.innerHTML.replace(/(<\/h[1-6]\s*>)/gi, '$1\r\n'); element.innerHTML = element.innerHTML.replace(/<(em|i)>(\d+\.\d+\..+?)<\/(em|i)>/gi, '\r\n<h4 class="value4">$2</h4>\r\n'); // Processing replacement of level 4 title element.innerHTML = element.innerHTML.replace(/>\s*(\d+\.\d+\.\d+\.\s*.*?)(?=\s*\n|$)/g, '>\r\n<h5 class="value5">$1</h5>\r\n'); element.innerHTML = element.innerHTML.replace(/^\s*(\d+\.\d+\.\d+\.\s*.*?)(?=\s*\n|$)/gm, '\r\n<h5 class="value5">$1</h5>\r\n'); // Processing replacement three -level title element.innerHTML = element.innerHTML.replace(/\*+(\d+\.\d+\..+?)\*+\s+/g, '\r\n<h4 class="value4">$1</h4>\r\n'); // Treatment P tag element.innerHTML = element.innerHTML.replace(/<p.+?>(.+?)<\/p>/gi, '\r\n$1\r\n'); let lastP = document.createElement('p'); Array.from(element.childNodes).forEach(node=> { if (node.childElementCount == 0 && node.textContent.trim().length == 0){ // Delete the empty node element.removeChild(node); } // Handle the title if (/H[1-6]/i.test(node.nodeName)){ if (lastP.childElementCount > 0 || lastP.textContent.trim().length > 0){ // Lastp is not an empty node. element.appendChild(lastP); lastP = document.createElement('p'); } element.appendChild(node); return; } // Check the HTML-Disp-Formula-Info node if (node.classList && node.classList.contains('html-disp-formula-info')){ if (lastP.childElementCount > 0 || lastP.textContent.trim().length > 0){ element.appendChild(lastP); lastP = document.createElement('p'); } element.appendChild(node); // Treatment of the text formula in the chapter renderMathInElement(node, { delimiters: [ {left: '```latex', right: '```', display: true}, ], throwOnError : false }); const label = node.querySelector('.formula > label'); if (label === null){ return; } var numMatch = label.textContent.match(/\d+/g) if (!numMatch){ return; } const html_pics = node.querySelector('.html_pics') if (html_pics){ formula["Equation"+numMatch[0]]=html_pics.innerHTML; } return; } // Treatment textbooks if (node.nodeType === 3) { var lines = node.nodeValue.split(/\r?\n/); if (lines.length == 1){ // No change, it may be the content of the previous P tag if (node.nodeValue.trim().length > 0){ lastP.appendChild(node); } return; } lines.forEach((line, index)=> { if (index >0){ // Other changes may be the new P tag, the old P label is moved in if (lastP.childElementCount > 0 || lastP.textContent.trim().length > 0){ element.appendChild(lastP); lastP = document.createElement('p'); } } if (line.trim().length > 0){ lastP.appendChild(document.createTextNode(line)); } }); element.removeChild(node); return; } if (node.classList.contains('html-fig-wrap')){ if (lastP.childElementCount > 0 || lastP.textContent.trim().length > 0){ element.appendChild(lastP); lastP = document.createElement('p'); } } //Other situations are the content of the previous P tag lastP.appendChild(node); }); if (lastP.childElementCount > 0 || lastP.textContent.trim().length > 0){ element.appendChild(lastP); } if (element.childElementCount == 0 && element.textContent.trim().length == 0){ // Delete the empty node element.parentNode.removeChild(element); } function capitalizeFirstLetter(str) { return str.charAt(0).toUpperCase() + str.slice(1); } // Find the picture form formula without setting the A tag, and give a tag element.innerHTML = element.innerHTML.replace(/(?<!<a.+?>\s*|[a-zA-Z])(Figure|Table|Scheme|Equation)\s+($([A-Z]?\d+)$|([A-Z]?\d+))(?<!\s*<\/a>)/gi, function(match, $2,$3) { match = capitalizeFirstLetter(match); return '<a href="#'+ capitalizeFirstLetter($2) + $3.replace(/$|$/g,'') +'">'+ match +'</a>'; }); // Remove Markdown element.innerHTML = markdownReplace(element.innerHTML); // Find a super -text link without setting A tags, give a tagnk without setting A tags, give a tagnk without setting A tags, give a tag element.innerHTML = element.innerHTML.replace(/(?<!<a.+?>\s*)https?:\/\/[^\s\/]+(\/[^\s<.]*)*(?<!\s*<\/a>)/gi, function(match) { return '<a href="'+ match.replace(/[.,，。;\s]+$/, '') +'" target="_blank">'+ match +'</a>'; } ); // Add a box to the formula quotation element.querySelectorAll('a[href^="#Equation"]').forEach(auchor=>{ const id= auchor.getAttribute('href').slice(1); if (formula[id]){ $(auchor).tooltip({ html: true , delay: { "show": 200, "hide": 200 },title:$('<div class="formulaTip">').html(formula[id])}); } }); // Handling in -line formula renderMathInElement(element, { delimiters: [ {left: '$$', right: '$$', display: false}, ], throwOnError : false }); }); document.querySelectorAll("div.articleneir.abstract").forEach(element => { renderMathInElement(element, { delimiters: [ {left: '$$', right: '$$', display: false}, ], throwOnError : false }); }); // Processing reference document.querySelectorAll(".html-bibr").forEach(link => { link.removeAttribute('title'); const target = document.querySelector(link.getAttribute('href')+'.references > .references_name'); if (target){ $(link).tooltip({ html: true , delay: { "show": 200, "hide": 200 },title:target.innerHTML}); } }); document.querySelectorAll(".references").forEach(ref => { if (ref.id){ const a = document.createElement("a"); a.name=ref.id; a.classList.add("anchor-abs-66"); ref.removeAttribute("id"); ref.insertBefore(a, ref.firstChild); } }); // Treat the display area of the formula formula of the picture form, remove the A tag, set the anchor point document.querySelectorAll('.html-fig-wrap .html-fig_description,.html-fig-wrap .html-table_wrap_discription').forEach(element => { element.innerHTML = markdownReplace(element.innerHTML); const match = element.firstChild.textContent.match(/(Figure|Table|Scheme) [A-Z]?\d+/g); if (match){ element.firstChild.textContent = element.firstChild.textContent let id= match[0].replace(" ","") const target = document.createElement("a"); target.name=id; target.classList.add("anchor"); element.parentNode.insertBefore(target, element.parentNode.firstChild); document.querySelectorAll("a[href='#"+id+"']").forEach(auchor => { $(auchor).tooltip({ html: true , delay: { "show": 1000, "hide": 100 },title:$(element.parentNode).html()}); }); } }); // Processing keywords const keywordsContainer = document.querySelector('.keywords') if (keywordsContainer){ let title; while(child = keywordsContainer.firstChild){ // Take out the first non -empty element in Keywords if (child.textContent.trim().length>0){ title = child; title.appendChild(document.createTextNode(' ')); keywordsContainer.removeChild(child); break; } keywordsContainer.removeChild(child); } let listLinks = []; let link = document.createElement('a'); Array.from(keywordsContainer.childNodes).forEach(node=> { // Treatment text nodes if (node.nodeType === 3) { var ks = node.nodeValue.split(/(?<!&#(?:x[0-9a-fA-F]{1,5}|\d{1,6}))[;]|,/); if (ks.length == 1){ // There is no separatist, no new link is created if (link.lastChild && link.lastChild.nodeType === 3){ //Condented text nodes link.lastChild.nodeValue += ks[0]; }else{ link.appendChild(node); } return; }else{ ks.forEach((k, index)=> { if (index==0){ // In the first paragraph, do not create a new LINK, and the merger with the previous merger if (link.lastChild && link.lastChild.nodeType === 3){ //Condented text nodes link.lastChild.nodeValue += k; return; } }else{ // Means encounter; create a new link listLinks.push(link); link = document.createElement('a'); } link.appendChild(document.createTextNode(k.trim())); }); return; } }else{ link.appendChild(node); } }); if (link.innerText.trim().length>0){ listLinks.push(link); } keywordsContainer.innerHTML = ""; keywordsContainer.appendChild(title); listLinks.forEach((link, index, array)=> { link.href = "/index/search/index.html?search="+link.innerHTML.trim().replace(/ /g, '+');// TODO :Angle/lowering/small capitalization keywordsContainer.appendChild(link); if (index !== array.length - 1) { keywordsContainer.appendChild(document.createTextNode(', ')); } }); } // Treatment reference copy document.querySelectorAll('.cite-modal h6 ').forEach(h6 => { let a = document.createElement('a'); let h6Text = h6.textContent.trim(); h6.appendChild(a); a.href = "#"; a.textContent = "Copy"; a.onclick = function(e) { if (h6.nextElementSibling) { navigator.clipboard.writeText(h6.nextElementSibling.textContent.replace(/\r\n|\n|\r/g, '')).then(function() { $('#citeModal').modal('hide'); // showToast(h6Text + ' copied to clipboard!'); }, function() { showToast('Failed to copy '+h6Text+' to clipboard.'); }); } e.preventDefault(); }; }); //Picture amplification var $imgModal = $('#imgModal'), $imgModalBody = $imgModal.find('.modal-body'); $(".html-figpopup-link").each(function(){ var dataSrc = $(this).children('img').attr('data-large'); $(this).attr({ 'data-toggle': 'modal', 'data-target': '#imgModal' }) $(this).on('click', function () { $imgModalBody.append(`<img src="`+dataSrc+`" class="amplification-img">`); }) }); $imgModal.on('hidden.bs.modal', function (event) { $imgModalBody.children('img').remove(); }) //The picture is enlarged again $imgModal.on('shown.bs.modal', function (event) { $imgModalBody.children('img').on('click', function () { $(this).parent().parent().toggleClass('toggle-img'); }) }) // Process doi // Doi reference the magazine $.ajax({ type: 'GET', url: '/api/article/doi/id/209', dataType:"json", success: function(data){ var doiEL =""; $.each(data.doi_list, function(k, v) { doiEL += "<p>" + v.title + "." + " <em>" + v.source + "</em>" + " " + "<b>" + v.year + "</b>. " + "[" + "<a target='_blank' href='http://dx.doi.org/" + v.doi + "'>CrossRef</a>" + "]" +"</p>"; }) if (data.doi_count > 0) { $("[data-bind='popover1'] > b").text(data.doi_count); $("[data-bind='popover1']").addClass('d-flex'); $("[data-bind='popover1']").popover({ trigger: 'focus', html: true, delay: { "show": 100, "hide": 500 }, content: function(){ return doiEL; }, }); } }, timeout: 5000, error: function(jqXHR,textStatus){ } }) }) function showToast(message) { var toast = document.createElement('div'); toast.classList.add('toast', 'centered-div', 'show'); toast.setAttribute('role', 'alert'); toast.setAttribute('aria-live', 'assertive'); toast.setAttribute('aria-atomic', 'true'); var toastBody = document.createElement('div'); toastBody.classList.add('toast-body'); toastBody.textContent = message; toast.appendChild(toastBody); document.body.appendChild(toast); setTimeout(function () { toast.classList.remove('show'); toast.classList.add('hide'); setTimeout(function () { document.body.removeChild(toast); }, 500); }, 3000); } </script>  <footer class="mt-1"> <div class="my-body-container pt-4 pb-4"> <div class="fotter-top"> <div> <div class="item-text"> <h3>About</h3> <ul> <li> <a href="/About_SCIEPublish" title="About SClEPublish">About SClEPublish</a> </li> <li> <a href="/Management_Team" title="Management Team">Management Team</a> </li> <li> <a href="/Careers" title="Careers">Careers</a> </li> <li> <a href="/Contact" title="Contact">Contact</a> </li> </ul> </div> <div class="item-text"> <h3>Policies</h3> <ul> <li> <a href="/Peer_Review_Policy" title="Peer Review Policy">Peer Review Policy</a> </li> <li> <a href="/Open_Access_Policy" title="Open Access Policy">Open Access Policy</a> </li> <li> <a href="/Licensing_and_Copyright" title="Licensing and Copyright">Licensing and Copyright</a> </li> <li> <a href="/Editorial_Policy" title="Editorial Policy">Editorial Policy</a> </li> <li> <a href="/Advertising_Policy" title="Advertising Policy">Advertising Policy</a> </li> </ul> </div> <div class="item-text"> <h3>Information</h3> <ul> <li> <a href="/For_Authors" title="For Authors">For Authors</a> </li> <li> <a href="/For_Reviewers" title="For Reviewers">For Reviewers</a> </li> <li> <a href="/For_Editors" title="For Editors">For Editors</a> </li> </ul> </div> <div class="item-text item-text-membership"> <h3>A Member of</h3> <ul> <li class="membership-img1"> <a href="https://stm-assoc.org/" target="_blank" rel="nofollow"> <img src="/style/image/stm2024-logo.png"> </a> </li> <li class="membership-img2"> <a href="https://www.alpsp.org/" target="_blank" rel="nofollow" title=""> <img src="/style/image/alpsp-logo.png" alt=""> </a> </li>  </ul> </div> </div> <div class="item-text item-text-right"> <h3> <svg xmlns="http://www.w3.org/2000/svg" class="navbar-logo" xml:space="preserve" version="1.0" viewBox="0 0 5.08 1.933"> <path d="M1.021 1.245a.29.29 0 0 1-.211-.054l-.027-.023-.003-.003.056-.066.003.004a.3.3 0 0 0 .043.033.2.2 0 0 0 .128.027l.024-.007.019-.01a.07.07 0 0 0 .022-.032.1.1 0 0 0 0-.036l-.004-.014a.1.1 0 0 0-.016-.02.1.1 0 0 0-.027-.017L.994 1.01.919.98a.3.3 0 0 1-.076-.05.14.14 0 0 1-.034-.067.2.2 0 0 1 0-.06.13.13 0 0 1 .027-.056.2.2 0 0 1 .049-.041A.2.2 0 0 1 .95.683a.3.3 0 0 1 .07-.001.2.2 0 0 1 .06.017.3.3 0 0 1 .075.05l.003.003-.05.061L1.103.81a.2.2 0 0 0-.053-.034.2.2 0 0 0-.063-.013.1.1 0 0 0-.046.008L.925.78a.06.06 0 0 0-.023.047l.001.015.006.012a.1.1 0 0 0 .018.02.1.1 0 0 0 .027.017L.97.899l.016.006.074.032a.3.3 0 0 1 .058.033.14.14 0 0 1 .051.08.2.2 0 0 1 0 .07.15.15 0 0 1-.048.081.2.2 0 0 1-.062.035zm.527-.002a.24.24 0 0 1-.1 0 .23.23 0 0 1-.125-.069.2.2 0 0 1-.051-.089.3.3 0 0 1-.019-.119.4.4 0 0 1 .02-.12.3.3 0 0 1 .052-.09.23.23 0 0 1 .176-.076.3.3 0 0 1 .064.01.3.3 0 0 1 .053.025.2.2 0 0 1 .04.034l.002.003-.052.061L1.605.81A.2.2 0 0 0 1.56.776a.2.2 0 0 0-.037-.012.15.15 0 0 0-.082.013.13.13 0 0 0-.049.039l-.018.029a.2.2 0 0 0-.022.073.4.4 0 0 0 .002.104.2.2 0 0 0 .014.05.2.2 0 0 0 .023.04.14.14 0 0 0 .066.047.15.15 0 0 0 .107-.009l.028-.017.025-.023.003-.004.051.06-.002.003a.3.3 0 0 1-.076.059.2.2 0 0 1-.045.015m.314-.004h-.09V.69h.095v.549zm.485 0h-.331V.69h.328v.08H2.11v.141h.198v.082H2.11v.165h.242v.08zm.215 0h-.09V.69h.169a.4.4 0 0 1 .083.008L2.76.71l.031.016a.13.13 0 0 1 .044.053q.009.015.012.036a.22.22 0 0 1-.012.121l-.018.03a.176.176 0 0 1-.09.057.3.3 0 0 1-.084.011h-.076v.205zm.005-.472v.19h.068a.2.2 0 0 0 .056-.006.1.1 0 0 0 .038-.018.1.1 0 0 0 .022-.031.1.1 0 0 0 .007-.045l-.003-.03a.07.07 0 0 0-.028-.04L2.703.776 2.671.769 2.633.767zm.539.48a.2.2 0 0 1-.067-.003.1.1 0 0 1-.075-.07.3.3 0 0 1-.013-.09V.827h.093v.248a.3.3 0 0 0 .007.055l.008.017.012.012.016.007.02.002a.1.1 0 0 0 .033-.006.1.1 0 0 0 .03-.019.2.2 0 0 0 .03-.032V.826h.093v.413h-.078l-.006-.057a.2.2 0 0 1-.078.057zm.548-.002-.034.003-.03-.003-.029-.01A.2.2 0 0 1 3.51 1.2l-.007.039h-.075V.645h.093q0 .11-.002.219l.01-.008A.2.2 0 0 1 3.59.823a.2.2 0 0 1 .043-.007.2.2 0 0 1 .07.015.15.15 0 0 1 .07.074.2.2 0 0 1 .022.076.4.4 0 0 1 0 .095.3.3 0 0 1-.029.082.2.2 0 0 1-.079.075zm-.07-.077a.1.1 0 0 0 .046-.002.1.1 0 0 0 .043-.032l.015-.028a.2.2 0 0 0 .01-.036.3.3 0 0 0-.006-.114A.1.1 0 0 0 3.68.93.07.07 0 0 0 3.64.9.1.1 0 0 0 3.59.899l-.023.008-.023.015-.023.02v.193a.2.2 0 0 0 .043.027zm.424.08h-.015a.1.1 0 0 1-.051-.013l-.017-.016-.011-.022-.007-.026-.002-.031V.645h.093v.5L4 1.16l.003.004.003.003.008.002h.008l.005-.001h.004l.013.071-.004.002-.009.002zm.22-.01H4.14V.827h.093v.413zm-.026-.48L4.187.76q-.009 0-.016-.002L4.157.753a.05.05 0 0 1-.02-.02.1.1 0 0 1-.008-.027L4.13.69a.05.05 0 0 1 .027-.032L4.17.653a.07.07 0 0 1 .045.005.05.05 0 0 1 .03.048.1.1 0 0 1-.009.028.1.1 0 0 1-.02.019zm.315.488a.25.25 0 0 1-.19-.054l-.004-.003.045-.062.004.003a.3.3 0 0 0 .053.034.13.13 0 0 0 .058.012l.022-.002.016-.005.013-.008.009-.01a.05.05 0 0 0 .007-.025q0-.006-.002-.012l-.005-.01-.008-.009-.011-.008-.028-.014-.016-.006-.017-.007a.4.4 0 0 1-.079-.041.1.1 0 0 1-.028-.034L4.348.964 4.345.939a.12.12 0 0 1 .023-.07.1.1 0 0 1 .038-.033A.2.2 0 0 1 4.46.82a.2.2 0 0 1 .13.022l.037.024.003.003-.045.059-.003-.003A.2.2 0 0 0 4.54.9a.1.1 0 0 0-.065-.008.1.1 0 0 0-.027.012l-.007.01a.04.04 0 0 0-.007.022q0 .006.002.01l.005.01a.1.1 0 0 0 .017.015l.027.013.016.006.016.006.063.028.019.013a.1.1 0 0 1 .029.035l.008.023a.13.13 0 0 1-.008.077.1.1 0 0 1-.03.04.14.14 0 0 1-.05.027zm.307-.007h-.088V.645h.092q0 .115-.002.229a.3.3 0 0 1 .05-.038.2.2 0 0 1 .048-.017.2.2 0 0 1 .068.002.1.1 0 0 1 .057.038q.01.014.018.033A.314.314 0 0 1 5.08.98v.258h-.093V.99L4.985.96 4.98.936 4.97.92 4.96.907 4.943.9a.1.1 0 0 0-.037 0 .1.1 0 0 0-.03.011l-.016.01-.032.03v.288z" /> <path d="M1.844 1.377a.97.97 0 0 1-.878.563A.963.963 0 0 1 0 .974.964.964 0 0 1 .966.007a.96.96 0 0 1 .865.536l-.048.024A.92.92 0 0 0 .966.062a.91.91 0 0 0-.912.912.91.91 0 0 0 .912.912.91.91 0 0 0 .83-.532z" class="logo-circle" /> </svg> </h3> <div class="text-share"> <a href="https://x.com/SCIEPublish" class="share-btn twitter-btn" title="Share on Twitter" target="_blank"> <svg t="1713929395475" class="icon" width="32" height="32" viewBox="0 0 1399 1024" fill="#000000" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="8742"> <path d="M282.021569 119.281213l323.998199 433.216256-326.044203 352.222995h73.379441l285.451142-308.376452 230.636674 308.376452h249.713149l-342.227762-457.583832 303.479459-327.855419h-73.379441l-262.886398 284.008876-212.407111-284.008876h-249.713149z m107.909957 54.051408h114.71879l506.578928 677.328049h-114.718791l-506.578927-677.328049z" p-id="8743"></path> </svg> </a> <a href="" class="share-btn LinkedIn-btn" id="email-LinkedIn-btn" title="Share on LinkedIn" target="_blank"> <svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" fill="#000000" class="bi bi-linkedin" viewBox="0 0 16 16"> <path d="M0 1.146C0 .513.526 0 1.175 0h13.65C15.474 0 16 .513 16 1.146v13.708c0 .633-.526 1.146-1.175 1.146H1.175C.526 16 0 15.487 0 14.854V1.146zm4.943 12.248V6.169H2.542v7.225h2.401zm-1.2-8.212c.837 0 1.358-.554 1.358-1.248-.015-.709-.52-1.248-1.342-1.248-.822 0-1.359.54-1.359 1.248 0 .694.521 1.248 1.327 1.248h.016zm4.908 8.212V9.359c0-.216.016-.432.08-.586.173-.431.568-.878 1.232-.878.869 0 1.216.662 1.216 1.634v3.865h2.401V9.25c0-2.22-1.184-3.252-2.764-3.252-1.274 0-1.845.7-2.165 1.193v.025h-.016a5.54 5.54 0 0 1 .016-.025V6.169h-2.4c.03.678 0 7.225 0 7.225h2.4z"/> </svg> </a> <a href="javaScript:void(0)" class="share-btn wechat-btn" id="wechat-share-btn"> <svg xmlns="http://www.w3.org/2000/svg" width="26" height="26" fill="#000000" class="bi bi-wechat" viewBox="0 0 16 16"> <path d="M11.176 14.429c-2.665 0-4.826-1.8-4.826-4.018 0-2.22 2.159-4.02 4.824-4.02S16 8.191 16 10.411c0 1.21-.65 2.301-1.666 3.036a.324.324 0 0 0-.12.366l.218.81a.616.616 0 0 1 .029.117.166.166 0 0 1-.162.162.177.177 0 0 1-.092-.03l-1.057-.61a.519.519 0 0 0-.256-.074.509.509 0 0 0-.142.021 5.668 5.668 0 0 1-1.576.22ZM9.064 9.542a.647.647 0 1 0 .557-1 .645.645 0 0 0-.646.647.615.615 0 0 0 .09.353Zm3.232.001a.646.646 0 1 0 .546-1 .645.645 0 0 0-.644.644.627.627 0 0 0 .098.356Z"/> <path d="M0 6.826c0 1.455.781 2.765 2.001 3.656a.385.385 0 0 1 .143.439l-.161.6-.1.373a.499.499 0 0 0-.032.14.192.192 0 0 0 .193.193c.039 0 .077-.01.111-.029l1.268-.733a.622.622 0 0 1 .308-.088c.058 0 .116.009.171.025a6.83 6.83 0 0 0 1.625.26 4.45 4.45 0 0 1-.177-1.251c0-2.936 2.785-5.02 5.824-5.02.05 0 .1 0 .15.002C10.587 3.429 8.392 2 5.796 2 2.596 2 0 4.16 0 6.826Zm4.632-1.555a.77.77 0 1 1-1.54 0 .77.77 0 0 1 1.54 0Zm3.875 0a.77.77 0 1 1-1.54 0 .77.77 0 0 1 1.54 0Z"/> </svg> <div class="cord"> <div class="img"> <img src="/style/image/wechat.jpg" alt="SCIEPublish wechat" /> </div> </div> </a> <a href="mailto:office@sciepublish.org" class="share-btn email-btn" id="email-share-btn" title="Share on Email" target="_blank"> <svg xmlns="http://www.w3.org/2000/svg" width="26" height="26" fill="#000000" class="bi bi-envelope-fill" viewBox="0 0 16 16"> <path d="M.05 3.555A2 2 0 0 1 2 2h12a2 2 0 0 1 1.95 1.555L8 8.414.05 3.555ZM0 4.697v7.104l5.803-3.558L0 4.697ZM6.761 8.83l-6.57 4.027A2 2 0 0 0 2 14h12a2 2 0 0 0 1.808-1.144l-6.57-4.027L8 9.586l-1.239-.757Zm3.436-.586L16 11.801V4.697l-5.803 3.546Z"/> </svg> </a> </div> </div> </div> <div class="copyright-box mt-4 mb-0 pt-3 pb-0"> <p class="text-left">Copyright © 2021-2024 SCIE Publishing Ltd. unless otherwise stated.</p> <p class="text-right"> <a href="/Privacy" title="Privacy">Privacy</a>  <a href="/Terms_of_Use" title="Terms of Use">Terms of Use</a> </p> </div> </div> </footer>  <div class="back-top"> <div class="d-flex justify-content-center align-items-center flex-wrap"> <svg xmlns="http://www.w3.org/2000/svg" width="20" height="20" fill="currentColor" class="bi bi-chevron-up" viewBox="0 0 16 16"> <path fill-rule="evenodd" d="M7.646 4.646a.5.5 0 0 1 .708 0l6 6a.5.5 0 0 1-.708.708L8 5.707l-5.646 5.647a.5.5 0 0 1-.708-.708l6-6z"/> </svg> <span>TOP</span> </div> </div>  <div class="toast-container"> <div class="toast" id="liveToast" role="alert" data-delay="3000" aria-live="assertive" aria-atomic="true"> <div class="toast-header"> <strong class="mr-auto">Message</strong> <button type="button" class="ml-2 mb-1 close" data-dismiss="toast" aria-label="Close"> <span aria-hidden="true">×</span> </button> </div> <div class="toast-body"> </div> </div> </div> <script> $(function () { $('.js-navbar-toggle').on('click', function () { $('header nav').toggleClass('nav-search-active'); }); var windowHeight = $(window).height(), header = $('header'), backTop = $('.back-top'); $(window).scroll(function(){ var scrollTop = $(this).scrollTop(); scrollTop > 0 ? header.addClass('fixed') : header.removeClass('fixed'); scrollTop > windowHeight ? backTop.addClass('fixed') : backTop.removeClass('fixed'); }) backTop.click(function(){ $("body,html").animate({scrollTop:0},300); }) $(".article-abseract.clamp").each(function () { $(this).click(function () { $(this).toggleClass("clamp-open"); }); }); //初始化select $('select.select-mania').selectMania(); }) $('.logout').click(function () { $.get('/index/user/login_out', function (res) { if (res.err == 0) { window.location.href = res.data layer.msg('exit successfully!') } else { layer.msg('Exit failed!') } }) }) </script> </body> </html>

CINXE.COM

Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network - Drones and Autonomous Vehicles - Full-Text HTML - SCIEPublish