Addressing the Return Visit Challenge in Autonomous Flying Ad Hoc Networks Linked to a Central Station Authors: Ercan Erkalkan, Vedat Topuz, Ali Buldu Published: 2024 ABSTRACT Unmanned Aerial Vehicles (UAVs) have become essential tools across various sectors due to their versatility and advanced capabilities in autonomy, perception, and networking. Despite over a decade of experimental efforts in multi-UAV systems, substantial theoretical challenges concerning coordination mechanisms still need to be solved, particularly in maintaining network connectivity and optimizing routing. Current research has revealed the absence of an efficient algorithm tailored for the routing problem of multiple UAVs connected to a central station, especially under the constraints of maintaining constant network connectivity and minimizing the average goal revisit time. This paper proposes a heuristic routing algorithm for multiple UAV systems to address the return visit challenge in flying ad hoc networks (FANETs) linked to a central station. Our approach introduces a composite valuation function for target prioritization and a mathematical model for task assignment with relay allocation, allowing any UAV to visit various objectives and gain an advantage or incur a cost for each. We exclusively utilized a simulation environment to mimic UAV operations, assessing communication range, connectivity, and routing performance. Extensive simulations demonstrate that our routing algorithm remains efficient in the face of frequent topological alterations in the network, showing robustness against dynamic environments and superior performance compared to existing methods. This paper presents different approaches to efficiently directing UAVs and explains how heuristic algorithms can enhance our understanding and improve current methods for task assignments. 1. Introduction Unmanned Aerial Vehicles (UAVs), commonly known as drones, have rapidly evolved and become indispensable tools across various sectors due to their versatility, affordability, and ease of deployment. Their influence is widely acknowledged in fields such as agricultural sensing [1], coastal zone management [2], disaster relief coordination [3], military operations [4], and UAV counteraction strategies [5]. UAVs are essential for performing dangerous, time-consuming, or impossible tasks for humans, including event monitoring and reconnaissance. As UAV technology advances, there is increasing interest in coordinating multiple UAVs to work collaboratively, forming multi-UAV systems. Such systems can perform complex missions more efficiently than single UAVs by covering larger areas, providing redundancy, and enabling simultaneous data collection [6]. This shift toward multi-UAV coordination introduces significant challenges, particularly in maintaining network connectivity, optimizing routing, and ensuring timely revisits to critical targets. One of the primary challenges in multi-UAV systems is routing UAVs in dynamic environments, where connectivity and task allocation must adapt to changing conditions. Traditional routing approaches often fall short in these settings, as static protocols need more flexibility to respond to network changes. In contrast, dynamic protocols require intensive computational resources to adjust routes in real time [7,8]. In this context, heuristic and meta-heuristic algorithms have emerged as practical tools to cope with sophisticated routing problems. Through employing machine learning and bio-inspired approaches, they provide adaptable solvers that can reconcile computational complexity with the flexibility required for real-time network modifications [9,10]. Coordinating multiple UAVs presents three fundamental challenges: scalability concerning the size and functionality of a swarm, handling task diversity and heterogeneity, and improving intra-UAV connectivity and communication. Solutions addressing these challenges aim to enhance coordination and communication between UAVs to improve multi-UAV efficiency. The revisit problem is a critical challenge in FANETs [11]. UAVs need to return to predefined targets for data collection and updating. This introduces another challenge of maintaining constant contact with a central base that coordinates missions and collects data. Recent works have attempted to address these challenges. For example, studies related to routing algorithms for FANETs focus on constructing advanced communication systems capable of supporting multi-UAV operations [12]. Wang et al. [13] proposed a heuristic algorithm to minimize energy consumption while effectively coordinating UAVs in underwater data collection. New approaches have also been adopted to extend mission duration and revisit efficiency. For example, a reinforcement learning-based algorithm allows UAVs to perform battery swaps at fixed stations, prolonging mission durations [14]. A unified framework considering interference management and trajectory optimization increases the effectiveness of data gathering by enhancing communication throughput while reducing mission time [15]. Recognizing the need for perpetual observation, route optimization techniques that consider fuel constraints allow for improved target revisit efficiency [16]. These works provide current perspectives toward improving mission coordination and data gathering effectiveness in multi-UAV setups using FANETs. However, algorithms for the dynamic routing of multiple UAVs tethered to a central station still need optimization. Existing methods often struggle to maintain network connectivity or minimize the average revisit time of targets under dynamic FANET conditions. Many proposals focus on static routing solutions, single-UAV path optimization, or simplified connectivity protocols that do not respond effectively to frequent topological changes in multi-UAV networks [6,17]. Therefore, a proper solution is required to emphasize node connectivity and revisit efficiency in centrally coordinated FANET architectures. This paper proposes a novel heuristic routing algorithm for multi-UAV systems to address the revisit challenge in FANETs connected to a central station. The contributions of this work can be summarized as follows:Composite Valuation Function: We introduce a composite valuation function that prioritizes target revisitation based on factors such as time since the last visit and distance to the target, ensuring efficient task allocation among UAVs and reducing average revisit time.Heuristic Algorithm for Connectivity and Efficiency: To address the challenges posed by dynamic changes in network nodes, we developed a heuristic algorithm to ensure constant connectivity while minimizing the average revisit time, accommodating frequent topological changes commonly encountered in FANET environments.Mathematical Model for Task Assignment and Relay Allocation: We provide a comprehensive mathematical model for UAV task assignment with relay allocation, ensuring continuous network connectivity by strategically positioning relay UAVs where needed.Extensive Validation through Simulation: To assess the robustness and efficiency of our algorithm, we performed extensive simulations, demonstrating superior performance and adaptability compared to existing methods in the literature. Composite Valuation Function: We introduce a composite valuation function that prioritizes target revisitation based on factors such as time since the last visit and distance to the target, ensuring efficient task allocation among UAVs and reducing average revisit time. Composite Valuation Function: We introduce a composite valuation function that prioritizes target revisitation based on factors such as time since the last visit and distance to the target, ensuring efficient task allocation among UAVs and reducing average revisit time. Heuristic Algorithm for Connectivity and Efficiency: To address the challenges posed by dynamic changes in network nodes, we developed a heuristic algorithm to ensure constant connectivity while minimizing the average revisit time, accommodating frequent topological changes commonly encountered in FANET environments. Heuristic Algorithm for Connectivity and Efficiency: To address the challenges posed by dynamic changes in network nodes, we developed a heuristic algorithm to ensure constant connectivity while minimizing the average revisit time, accommodating frequent topological changes commonly encountered in FANET environments. Mathematical Model for Task Assignment and Relay Allocation: We provide a comprehensive mathematical model for UAV task assignment with relay allocation, ensuring continuous network connectivity by strategically positioning relay UAVs where needed. Mathematical Model for Task Assignment and Relay Allocation: We provide a comprehensive mathematical model for UAV task assignment with relay allocation, ensuring continuous network connectivity by strategically positioning relay UAVs where needed. Extensive Validation through Simulation: To assess the robustness and efficiency of our algorithm, we performed extensive simulations, demonstrating superior performance and adaptability compared to existing methods in the literature. Extensive Validation through Simulation: To assess the robustness and efficiency of our algorithm, we performed extensive simulations, demonstrating superior performance and adaptability compared to existing methods in the literature. This study contributes a robust solution to a significant gap in FANET-based multi-UAV systems by balancing connectivity maintenance and revisiting efficiency, ultimately enhancing mission coordination and operational reliability. The rest of this paper is organized as follows: Section 2 reviews related work on multi-UAV system routing and the challenges associated with maintaining network connectivity and efficient task allocation. Section 3 introduces the revisit problem and our target valuation functions. In Section 4, we present our proposed heuristic algorithm and the underlying mathematical model. Section 5 details the experimental setup and discusses the results. Section 6 provides a comprehensive discussion on the implications of our findings, highlighting the algorithm’s strengths in addressing connectivity, task efficiency, energy usage, and adaptability, along with its real-world applicability and limitations. Finally, Section 7 concludes the paper and suggests directions for future research. 2. Related Work Over the past few years, researchers have paid significant attention to issues regarding maintaining connectivity and optimizing dynamic task allocation in Unmanned Aerial Vehicle (UAV) systems. UAVs have proven advantageous in military applications, precision agriculture, disaster management, and surveillance. However, ensuring continuous communication and frequent revisits to critical targets to maintain robust connectivity in multi-UAV systems presents significant challenges [18,19,20]. This necessity has made latency minimization and path planning of central interest, driven by the need to maintain network connectivity while allowing UAVs to revisit critical locations in the shortest possible time. 2.1. Latency Minimization in Multi-Agent Systems Minimizing the time between visits to critical nodes, also widely known as latency minimization, has been considered one of the central issues in multi-agent and multi-UAV systems. This is particularly important for enabling agents to revisit critical nodes quickly for continuous monitoring and task coordination in applications like FANETs. Recent algorithmic and framework developments have aimed to address this challenge. For instance, Gao et al. [21] proposed a role-switching framework for secure communications in multi-UAV systems by optimizing mission completion time through adaptive role taking and trajectory design. This study demonstrated that the dynamic assignment of system roles enhances efficiency in low-latency applications within multi-agent systems. Qiu et al. [22] further presented an adaptive consensus protocol for multi-agent systems with indefinite communication delays. Their adaptive coupling mechanism balances latency and stability, achieving more effective consensus to meet the required timing needs in real-time networks. Xue et al. [23] introduced the Multi-Agent Dynamic Algorithm Configuration (MA-DAC) framework, applying cooperative reinforcement learning to dynamic hyperparameter adjustments. This approach offers a direction for decreasing revisit times in multiple network topologies and increases flexibility in latency-sensitive systems. Zou et al. [24] presented a decentralized algorithm for UAV applications. Their algorithm achieves minimum-time consensus using an augmented graph to represent agents, accelerating consensus despite intrinsic time delays within connected systems. The decentralized mechanism is fundamental in applications where fast coordination is required. Furthermore, Moon et al. [25] explored latency minimization in a deep learning-aided multimodal tracking system for UAV contexts. They demonstrated practical latency reduction in real-world experiments by adopting a BiLSTM network to enhance responsiveness. These studies enrich the theory and practice of latency reduction in multi-agent and multi-UAV systems, whether through adaptive algorithms or efficient coordination strategies. 2.2. Dynamic Task Allocation and Challenges in Routing and Connectivity for Multi-UAV Systems Beyond latency optimization, some recent research has been conducted on UAV systems’ dynamic task allocations and network connectivity. Extensions to communication range with persistent connectivity and path optimizations in MANETs and FANETs have been carried out in [26,27,28]. The main challenge that multi-UAV routing brings is a trade-off between stable connectivity and real-time adaptability, given the system’s variations during a mission. Static routing methodologies are simple and require low computational power; therefore, they are suitable for stable conditions [7]. However, they may not work effectively under dynamic or unpredictable conditions where network topologies change frequently. Dynamic routing protocols can meet the challenge of frequent network variation but involve higher computational demands. Recently, with the integration of artificial intelligence (AI), dynamic routing can better adapt to shifts in networks, as AI-based algorithms facilitate decisions and route adjustments in real time over changes in network topology [8,10]. Cao et al. [29] studied a hybrid dynamic task allocation approach for FANETs using an improved Particle Swarm Optimization (PSO) algorithm and a decentralized auction algorithm. Their approach copes with unexpected tasks while minimizing communication overhead. Fei et al. [30] proposed a dynamic task allocation approach by leveraging spectral clustering to optimize mission delay and energy consumption in urban settings, considering the constrained energy of UAVs. Heuristic and meta-heuristic algorithms are practical approaches to these routing issues. While heuristic methods provide efficient solutions for well-defined problems with limited computational requirements, meta-heuristic approaches, which include nature-inspired algorithms, present more effective solutions for complex multi-objective routing issues [31]. Bekmezci et al. [6] highlighted that FANET topologies are subject to change, thus requiring adaptation and support to maintain efficient communication and coordination among flying UAVs. Fundamentally, these understandings provide a basis for adaptive and decentralized task allocation in UAV systems. Hybrid models combining heuristic, meta-heuristic, and machine learning techniques have shown potential for achieving optimal routing solutions across a range of multi-UAV applications [9]. While these techniques advance the field, gaps remain in balancing efficiency and adaptability under real-world constraints. Further research into hybrid approaches and machine learning-based dynamic routing could address computational limitations and adapt to the increasing scale and complexity of multi-UAV networks. 2.3. Comparison with Existing Methods While the studies above provide significant advancements in latency minimization and dynamic task allocation, they often do not fully address the challenges posed by highly dynamic network topologies common in FANETs connected to a central station. For instance, Gao et al. [21] proposed a role-switching framework that optimizes mission completion time but does not explicitly handle frequent topological changes. Similarly, Qiu et al. [22] and Xue et al. [23] presented adaptive consensus protocols and dynamic algorithm configurations that enhance latency reduction but primarily focus on communication delays and hyperparameter optimization, respectively, without addressing the unique connectivity challenges in FANETs. Zou et al. [24] introduced a decentralized algorithm leveraging augmented graphs to minimize consensus time, but this approach fails to guarantee robust connectivity in rapidly changing topologies. Moon et al. [25] focused on deep learning-aided latency minimization, showcasing practical benefits but with limited applicability in dynamic multi-UAV networks requiring continuous connectivity to a central station. In the context of routing and task allocation, studies like those of Cao et al. [29] and Fei et al. [30] explored hybrid and clustering-based methods to optimize communication overhead and mission delay. While effective in specific use cases, these methods were not designed for the high mobility and dynamic topologies characteristic of FANETs. Yalcin et al. [9] suggest hybrid models combining machine learning and heuristic approaches, but these lack continuous revisit scheduling and latency minimization integration. Our approach explicitly targets these challenges by proposing a heuristic algorithm that accounts for the frequent topological changes inherent in FANETs. We aim to ensure continuous network connectivity and efficient revisit scheduling by integrating latency minimization with connectivity maintenance. This work provides a practical solution tailored to real-world multi-UAV applications, addressing the need for robust coordination and adaptability in dynamic environments. 3. Revisiting Problem and Target Valuation in FANETs In the context of FANETs, the revisiting problem is essential for enabling UAVs to visit target nodes at predetermined time intervals or in the shortest time possible. As crucial data carriers, UAVs collect real-time information from targets and forward it to the central repository. Overall performance and efficiency depend on the consistency of network connectivity and timely data updates within operational FANET activities. Unlike the classic visiting problem, revisiting embodies a perpetual aspect. UAVs must complete multiple revisits of the targets to refresh the information constantly. At the end of any circuit that covers all assigned targets, UAVs have only a limited time before returning and beginning another engagement cycle. Addressing the re-task planning challenge involves integrating target valuations into the post-initial-visit planning. One of the main issues is determining which targets should be prioritized for revisitation and quantifying their importance. This prioritization is based on two primary factors:Time since last visit: The duration that has elapsed since the target was last visited.Distance to the target: The proximity of the target to the UAV’s current position. Time since last visit: The duration that has elapsed since the target was last visited. Time since last visit: The duration that has elapsed since the target was last visited. Distance to the target: The proximity of the target to the UAV’s current position. Distance to the target: The proximity of the target to the UAV’s current position. To effectively prioritize targets, we define valuation functions that quantify the importance of revisiting each target based on these factors. 3.1. Time-Based Valuation Function The time-based valuation function reflects the increasing importance of revisiting a target as more time elapses since its last visit. We define this function as (1)U1(t)=0if t≤tthreshold1t−tthreshold1if tthreshold1tthreshold2 wheret is the time elapsed since the target was last visited.tthreshold1 and tthreshold2 are predefined time thresholds that determine how the valuation increases over time. t is the time elapsed since the target was last visited. t is the time elapsed since the target was last visited. tthreshold1 and tthreshold2 are predefined time thresholds that determine how the valuation increases over time. tthreshold1 and tthreshold2 are predefined time thresholds that determine how the valuation increases over time. Explanation of Parameters:tthreshold1 represents the minimum time after which a target starts to gain value. Before this time, the target does not require immediate revisitation.tthreshold2 marks the time after which the urgency to revisit the target increases more rapidly (quadratically), indicating a critical need for revisitation. tthreshold1 represents the minimum time after which a target starts to gain value. Before this time, the target does not require immediate revisitation. tthreshold1 represents the minimum time after which a target starts to gain value. Before this time, the target does not require immediate revisitation. tthreshold2 marks the time after which the urgency to revisit the target increases more rapidly (quadratically), indicating a critical need for revisitation. tthreshold2 marks the time after which the urgency to revisit the target increases more rapidly (quadratically), indicating a critical need for revisitation. Behavior of the Function:For t≤tthreshold1, the valuation is zero, implying that the target does not need immediate revisitation shortly after the last visit.For tthreshold1tthreshold2, the valuation increases quadratically with time, indicating an urgent need to revisit the target since a significant amount of time has passed. For t≤tthreshold1, the valuation is zero, implying that the target does not need immediate revisitation shortly after the last visit. For t≤tthreshold1, the valuation is zero, implying that the target does not need immediate revisitation shortly after the last visit. For tthreshold1tthreshold2, the valuation increases quadratically with time, indicating an urgent need to revisit the target since a significant amount of time has passed. For t>tthreshold2, the valuation increases quadratically with time, indicating an urgent need to revisit the target since a significant amount of time has passed. Choice of Thresholds: The values of tthreshold1 and tthreshold2 are determined based on mission requirements and the acceptable maximum interval between visits to a target, for example,tthreshold1=10 min: No need to revisit within the first 10 min.tthreshold2=30 min: After 30 min, the urgency to revisit increases significantly. tthreshold1=10 min: No need to revisit within the first 10 min. tthreshold1=10 min: No need to revisit within the first 10 min. tthreshold2=30 min: After 30 min, the urgency to revisit increases significantly. tthreshold2=30 min: After 30 min, the urgency to revisit increases significantly. 3.2. Distance-Based Valuation Function The distance-based valuation function accounts for the UAV’s proximity to the target. We define this function as (2)U2(u,g)=1d(u,g)+ϵ whereu represents the current position of the UAV.g represents the position of the target.d(u,g) is the Euclidean distance between the UAV and the target.ϵ is a small positive constant added to avoid division by zero when the distance is very small. u represents the current position of the UAV. u represents the current position of the UAV. g represents the position of the target. g represents the position of the target. d(u,g) is the Euclidean distance between the UAV and the target. d(u,g) is the Euclidean distance between the UAV and the target. ϵ is a small positive constant added to avoid division by zero when the distance is very small. ϵ is a small positive constant added to avoid division by zero when the distance is very small. Explanation of Variables:d(u,g)=(xu−xg)2+(yu−yg)2, where (xu,yu) and (xg,yg) are the coordinates of the UAV and the target, respectively.ϵ ensures numerical stability; a typical value might be ϵ=0.0001. d(u,g)=(xu−xg)2+(yu−yg)2, where (xu,yu) and (xg,yg) are the coordinates of the UAV and the target, respectively. d(u,g)=(xu−xg)2+(yu−yg)2, where (xu,yu) and (xg,yg) are the coordinates of the UAV and the target, respectively. ϵ ensures numerical stability; a typical value might be ϵ=0.0001. ϵ ensures numerical stability; a typical value might be ϵ=0.0001. Behavior of the Function:The valuation inversely correlates with the distance: the closer the UAV is to the target, the higher the valuation.This encourages the UAV to prioritize nearby targets, optimizing travel time and energy consumption. The valuation inversely correlates with the distance: the closer the UAV is to the target, the higher the valuation. The valuation inversely correlates with the distance: the closer the UAV is to the target, the higher the valuation. This encourages the UAV to prioritize nearby targets, optimizing travel time and energy consumption. This encourages the UAV to prioritize nearby targets, optimizing travel time and energy consumption. 3.3. Composite Valuation Function To comprehensively evaluate the priority of revisiting a target, we combine the time-based and distance-based valuation functions. The composite valuation function is defined as (3)U(u,g,t)=U1(t)×U2(u,g) whereU(u,g,t): The composite valuation of target g for UAV u at time t.U1(t): The time-based valuation function, reflecting the urgency to revisit the target based on the time elapsed since the last visit.U2(u,g): The distance-based valuation function, representing the UAV’s proximity to the target. U(u,g,t): The composite valuation of target g for UAV u at time t. U(u,g,t): The composite valuation of target g for UAV u at time t. U1(t): The time-based valuation function, reflecting the urgency to revisit the target based on the time elapsed since the last visit. U1(t): The time-based valuation function, reflecting the urgency to revisit the target based on the time elapsed since the last visit. U2(u,g): The distance-based valuation function, representing the UAV’s proximity to the target. U2(u,g): The distance-based valuation function, representing the UAV’s proximity to the target. Conditions for Combining U1(t) and U2(u,g): The composite valuation function U(u,g,t) is applicable for the following:When the target g requires revisitation, i.e., U1(t)>0.When the UAV u is operational and capable of reaching the target g. When the target g requires revisitation, i.e., U1(t)>0. When the target g requires revisitation, i.e., U1(t)>0. When the UAV u is operational and capable of reaching the target g. When the UAV u is operational and capable of reaching the target g. Interpretation of the Multiplication Result: Multiplying U1(t) and U2(u,g) integrates the urgency of revisiting a target with the feasibility of the UAV reaching it:A higher U1(t) indicates a greater need to revisit the target due to the elapsed time.A higher U2(u,g) suggests that the UAV is closer to the target.The product U(u,g,t) thus represents the overall priority of assigning UAV u to revisit target g at time t. A higher U1(t) indicates a greater need to revisit the target due to the elapsed time. A higher U1(t) indicates a greater need to revisit the target due to the elapsed time. A higher U2(u,g) suggests that the UAV is closer to the target. A higher U2(u,g) suggests that the UAV is closer to the target. The product U(u,g,t) thus represents the overall priority of assigning UAV u to revisit target g at time t. The product U(u,g,t) thus represents the overall priority of assigning UAV u to revisit target g at time t. Behavior of the Composite Function:If U1(t)=0, then U(u,g,t)=0, regardless of U2(u,g). This means that the target does not currently require revisitation.If U2(u,g) is small (UAV is far from the target), U(u,g,t) will be low even if U1(t) is high, indicating lower priority due to distance.The highest priority is when both U1(t) and U2(u,g) are high, meaning that the target is overdue for revisitation and the UAV is nearby. If U1(t)=0, then U(u,g,t)=0, regardless of U2(u,g). This means that the target does not currently require revisitation. If U1(t)=0, then U(u,g,t)=0, regardless of U2(u,g). This means that the target does not currently require revisitation. If U2(u,g) is small (UAV is far from the target), U(u,g,t) will be low even if U1(t) is high, indicating lower priority due to distance. If U2(u,g) is small (UAV is far from the target), U(u,g,t) will be low even if U1(t) is high, indicating lower priority due to distance. The highest priority is when both U1(t) and U2(u,g) are high, meaning that the target is overdue for revisitation and the UAV is nearby. The highest priority is when both U1(t) and U2(u,g) are high, meaning that the target is overdue for revisitation and the UAV is nearby. By combining these functions multiplicatively, we ensure that both time urgency and spatial proximity are simultaneously considered, leading to the efficient and effective prioritization of tasks. Implementation Considerations: When assigning tasks to UAVs based on U(u,g,t), the system should perform the following:Continuously update U1(t) and U2(u,g) as time progresses and UAV positions change.Recalculate U(u,g,t) at each decision point to reflect the most current priorities. Continuously update U1(t) and U2(u,g) as time progresses and UAV positions change. Continuously update U1(t) and U2(u,g) as time progresses and UAV positions change. Recalculate U(u,g,t) at each decision point to reflect the most current priorities. Recalculate U(u,g,t) at each decision point to reflect the most current priorities. 3.4. Algorithmic Implementation Algorithm 1 provides the procedural steps to compute the composite valuation for each target and reset the visitation status when a target is revisited. Algorithm 1: Priority-Based Target Revisitation Algorithm Function Descriptions:TimeBasedValuation(t): Calculates the time-based valuation U1(t) based on the elapsed time t since the last visit to the target.DistanceBasedValuation (u,g): Calculates the distance-based valuation U2(u,g) based on the current position of the UAV u and the target g.CompositeValuation (u,g,t): Computes the overall valuation U(u,g,t) by multiplying the time-based and distance-based valuations.ResetVisit (g): Updates the target’s last visit time, effectively resetting the time-based valuation component. TimeBasedValuation(t): Calculates the time-based valuation U1(t) based on the elapsed time t since the last visit to the target. TimeBasedValuation(t): Calculates the time-based valuation U1(t) based on the elapsed time t since the last visit to the target. DistanceBasedValuation (u,g): Calculates the distance-based valuation U2(u,g) based on the current position of the UAV u and the target g. DistanceBasedValuation (u,g): Calculates the distance-based valuation U2(u,g) based on the current position of the UAV u and the target g. CompositeValuation (u,g,t): Computes the overall valuation U(u,g,t) by multiplying the time-based and distance-based valuations. CompositeValuation (u,g,t): Computes the overall valuation U(u,g,t) by multiplying the time-based and distance-based valuations. ResetVisit (g): Updates the target’s last visit time, effectively resetting the time-based valuation component. ResetVisit (g): Updates the target’s last visit time, effectively resetting the time-based valuation component. 3.5. Graphical Representation Figure 1, Figure 2 and Figure 3 illustrate the behavior of the valuation functions as follows:Time-Based Valuation Function U1(t) (Figure 1): This function shows how valuation grows over time, starting from zero. The increase is gradual at first (linear) before accelerating quadratically after a certain threshold. This design reflects the importance of revisiting targets based on time delays, giving higher priority to targets as they become overdue for action.Distance-Based Valuation Function U2(u,g) (Figure 2): The distance valuation is inversely proportional to the distance d(u,g). Closer targets receive significantly higher valuation, while farther targets contribute less to the overall prioritization. This guides UAVs to prioritize nearby targets efficiently while still accounting for more distant ones with lower weights.Composite Valuation Function U(u,g,t) (Figure 3): This function integrates both time and distance considerations. As seen in the figure, high valuation is assigned to targets that are both overdue for revisitation (high t) and within close proximity (low d(u,g)). This combined approach effectively balances the urgency of action with operational efficiency. Time-Based Valuation Function U1(t) (Figure 1): This function shows how valuation grows over time, starting from zero. The increase is gradual at first (linear) before accelerating quadratically after a certain threshold. This design reflects the importance of revisiting targets based on time delays, giving higher priority to targets as they become overdue for action. Time-Based Valuation Function U1(t) (Figure 1): This function shows how valuation grows over time, starting from zero. The increase is gradual at first (linear) before accelerating quadratically after a certain threshold. This design reflects the importance of revisiting targets based on time delays, giving higher priority to targets as they become overdue for action. Distance-Based Valuation Function U2(u,g) (Figure 2): The distance valuation is inversely proportional to the distance d(u,g). Closer targets receive significantly higher valuation, while farther targets contribute less to the overall prioritization. This guides UAVs to prioritize nearby targets efficiently while still accounting for more distant ones with lower weights. Distance-Based Valuation Function U2(u,g) (Figure 2): The distance valuation is inversely proportional to the distance d(u,g). Closer targets receive significantly higher valuation, while farther targets contribute less to the overall prioritization. This guides UAVs to prioritize nearby targets efficiently while still accounting for more distant ones with lower weights. Composite Valuation Function U(u,g,t) (Figure 3): This function integrates both time and distance considerations. As seen in the figure, high valuation is assigned to targets that are both overdue for revisitation (high t) and within close proximity (low d(u,g)). This combined approach effectively balances the urgency of action with operational efficiency. Composite Valuation Function U(u,g,t) (Figure 3): This function integrates both time and distance considerations. As seen in the figure, high valuation is assigned to targets that are both overdue for revisitation (high t) and within close proximity (low d(u,g)). This combined approach effectively balances the urgency of action with operational efficiency. Each function plays a crucial role in dynamic decision making, enabling the UAV to optimize its tasks based on varying constraints and priorities. These graphs illustrate how the valuation functions evolve over time and distance, providing insight into the underlying prioritization mechanism. 3.6. Summary The precise definition of parameters such as tthreshold1 and tthreshold2 and variables u, g, and t enhances readability for the valuation functions. The clarity is intended to ease the interpretation of the functions and their correct application within UAV task prioritization in FANETs. In the next section, we introduce the proposed heuristic algorithm for optimal multi-UAV routing and connectivity, which leverages these valuation functions. 4. Heuristic Algorithm for Multi-UAV Routing and Connectivity Our goal is to optimize multi-UAV routing within FANETs, ensuring constant connectivity with a central station while minimizing the average revisit time for targets. The algorithm dynamically allocates relay UAVs to maintain a connected network topology and leverages the composite valuation function introduced in Section 3 to prioritize effective task allocation. 4.1. Problem Formulation The primary objective is to minimize the average revisit time of a set of targets G={g1,g2,…,gn} with a fleet of UAVs U={u1,u2,…,um}, while maintaining network connectivity to a central station S. This can be represented mathematically as a dynamic undirected graph G(V,E), where we have the following:V=U∪{S} represents the set of nodes, including all UAVs and the central station.E={(vi,vj)∣vi,vj∈V, d(vi,vj)≤Rc} represents the set of edges, with d(vi,vj) denoting the Euclidean distance between nodes vi and vj, and Rc as the maximum communication range between any two nodes, including UAVs and the central station. V=U∪{S} represents the set of nodes, including all UAVs and the central station. V=U∪{S} represents the set of nodes, including all UAVs and the central station. E={(vi,vj)∣vi,vj∈V, d(vi,vj)≤Rc} represents the set of edges, with d(vi,vj) denoting the Euclidean distance between nodes vi and vj, and Rc as the maximum communication range between any two nodes, including UAVs and the central station. E={(vi,vj)∣vi,vj∈V, d(vi,vj)≤Rc} represents the set of edges, with d(vi,vj) denoting the Euclidean distance between nodes vi and vj, and Rc as the maximum communication range between any two nodes, including UAVs and the central station. To ensure continuous connectivity, G(V,E) must form a single connected component at all times. If a situation arises where G(V,E) is not connected (i.e., it splits into multiple connected components), relay UAVs are assigned to maintain the network’s connectivity. This approach guarantees that there is always a communication path between each UAV and the central station S. 4.1.1. Assumptions All UAVs are homogeneous in terms of speed, communication range, and capabilities.Communication between UAVs is bidirectional and reliable within the range Rc.The positions of the targets and the central station are known and stationary.UAVs can act either as data collectors or as relay nodes to facilitate communication.UAVs have sufficient energy resources for the duration of the mission. All UAVs are homogeneous in terms of speed, communication range, and capabilities. All UAVs are homogeneous in terms of speed, communication range, and capabilities. Communication between UAVs is bidirectional and reliable within the range Rc. Communication between UAVs is bidirectional and reliable within the range Rc. The positions of the targets and the central station are known and stationary. The positions of the targets and the central station are known and stationary. UAVs can act either as data collectors or as relay nodes to facilitate communication. UAVs can act either as data collectors or as relay nodes to facilitate communication. UAVs have sufficient energy resources for the duration of the mission. UAVs have sufficient energy resources for the duration of the mission. 4.1.2. Variables and Notations U: Set of UAVs.G: Set of targets.S: Central station.UC⊆U: Set of UAVs acting as collectors.UR⊆U: Set of UAVs acting as relays (UR=U∖UC).d(u,v): Euclidean distance between UAV u and UAV v.d(u,g): Euclidean distance between UAV u and target g.Rc: Communication range of UAVs.U(u,g,t): Composite valuation function for UAV u and target g at time t, as defined in Equation (3).F(u,g,t): Binary decision variable; F(u,g,t)=1 if UAV u is assigned to target g at time t, and 0 otherwise.X(u,v,t): Binary variable; X(u,v,t)=1 if there is a communication link between UAV u and UAV v at time t, and 0 otherwise.Eu: Remaining energy of UAV u. U: Set of UAVs. U: Set of UAVs. G: Set of targets. G: Set of targets. S: Central station. S: Central station. UC⊆U: Set of UAVs acting as collectors. UC⊆U: Set of UAVs acting as collectors. UR⊆U: Set of UAVs acting as relays (UR=U∖UC). UR⊆U: Set of UAVs acting as relays (UR=U∖UC). d(u,v): Euclidean distance between UAV u and UAV v. d(u,v): Euclidean distance between UAV u and UAV v. d(u,g): Euclidean distance between UAV u and target g. d(u,g): Euclidean distance between UAV u and target g. Rc: Communication range of UAVs. Rc: Communication range of UAVs. U(u,g,t): Composite valuation function for UAV u and target g at time t, as defined in Equation (3). U(u,g,t): Composite valuation function for UAV u and target g at time t, as defined in Equation (3). F(u,g,t): Binary decision variable; F(u,g,t)=1 if UAV u is assigned to target g at time t, and 0 otherwise. F(u,g,t): Binary decision variable; F(u,g,t)=1 if UAV u is assigned to target g at time t, and 0 otherwise. X(u,v,t): Binary variable; X(u,v,t)=1 if there is a communication link between UAV u and UAV v at time t, and 0 otherwise. X(u,v,t): Binary variable; X(u,v,t)=1 if there is a communication link between UAV u and UAV v at time t, and 0 otherwise. Eu: Remaining energy of UAV u. Eu: Remaining energy of UAV u. 4.2. Mathematical Model Our goal is to assign UAVs to targets in a way that maximizes the total composite valuation while ensuring network connectivity to the central station S. The optimization problem can be formulated as follows. 4.2.1. Objective Function (4) maxF ∑t∑u∈U∑g∈GU(u,g,t)·F(u,g,t) In this equation, we have the following:U(u,g,t): The composite valuation function for UAV u and target g at time t.F(u,g,t): A binary decision variable, where F(u,g,t)=1 if UAV u is assigned to target g at time t, and 0 otherwise. U(u,g,t): The composite valuation function for UAV u and target g at time t. U(u,g,t): The composite valuation function for UAV u and target g at time t. F(u,g,t): A binary decision variable, where F(u,g,t)=1 if UAV u is assigned to target g at time t, and 0 otherwise. F(u,g,t): A binary decision variable, where F(u,g,t)=1 if UAV u is assigned to target g at time t, and 0 otherwise. The objective is to maximize the total valuation of the assignments over all UAVs, targets, and time steps. 4.2.2. Constraints C1: Assignment Constraint: Each UAV can be assigned to at most one target at any given time. (5)∑g∈GF(u,g,t)≤1, ∀u∈U, ∀tC2: Coverage Constraint: Each target may be assigned to multiple UAVs but must be visited by at least one UAV over time to minimize revisit time.C3: Connectivity Constraint: For every UAV u∈U, there must exist a communication path to the central station S. (6)For all u∈U, there exists a sequence {u0=u,u1,…,uk=S} such that X(ui,ui+1,t)=1,∀i,tC4: Communication Range Constraint: Communication links between UAVs are established only if they are within the communication range Rc. (7)X(u,v,t)=1,if d(u,v)≤Rc,0,otherwise, ∀u,v∈U∪{S}, ∀tC5: Relay Assignment Constraint: When critical connections are at risk, UAVs not assigned to targets act as relays to maintain network connectivity. The set of relay UAVs at any time t is defined as (8)UR(t)=U∖u∈U∣∑g∈GF(u,g,t)=1, ∀tCritical connections can arise in two cases: Between UAVs: In this situation, relay UAVs are allocated based on established methods from the literature (e.g., Bekmezci et al. [32]).Between UAV and Central Station: A custom relay assignment algorithm is utilized, as detailed in Section 4.5.C6: Energy Constraint: UAVs have limited energy resources. (9)Eu(t+1)=Eu(t)−eu(t), ∀u∈U,∀t where eu(t) is the energy consumption of UAV u at time t.C7: Movement Constraint: UAVs move either toward their assigned targets or adjust their positions dynamically to act as relays. Relay UAVs actively reposition themselves based on the states and movements of the UAVs assigned to targets, ensuring continuous connectivity and maintaining the network as a single connected component.C8: Initial Conditions: At t=0, the initial positions of UAVs and the central station are known, and the network is connected. C1: Assignment Constraint: Each UAV can be assigned to at most one target at any given time. (5)∑g∈GF(u,g,t)≤1, ∀u∈U, ∀t Assignment Constraint: Each UAV can be assigned to at most one target at any given time. (5)∑g∈GF(u,g,t)≤1, ∀u∈U, ∀t C2: Coverage Constraint: Each target may be assigned to multiple UAVs but must be visited by at least one UAV over time to minimize revisit time. Coverage Constraint: Each target may be assigned to multiple UAVs but must be visited by at least one UAV over time to minimize revisit time. C3: Connectivity Constraint: For every UAV u∈U, there must exist a communication path to the central station S. (6)For all u∈U, there exists a sequence {u0=u,u1,…,uk=S} such that X(ui,ui+1,t)=1,∀i,t Connectivity Constraint: For every UAV u∈U, there must exist a communication path to the central station S. (6)For all u∈U, there exists a sequence {u0=u,u1,…,uk=S} such that X(ui,ui+1,t)=1,∀i,t C4: Communication Range Constraint: Communication links between UAVs are established only if they are within the communication range Rc. (7)X(u,v,t)=1,if d(u,v)≤Rc,0,otherwise, ∀u,v∈U∪{S}, ∀t Communication Range Constraint: Communication links between UAVs are established only if they are within the communication range Rc. (7)X(u,v,t)=1,if d(u,v)≤Rc,0,otherwise, ∀u,v∈U∪{S}, ∀t C5: Relay Assignment Constraint: When critical connections are at risk, UAVs not assigned to targets act as relays to maintain network connectivity. The set of relay UAVs at any time t is defined as (8)UR(t)=U∖u∈U∣∑g∈GF(u,g,t)=1, ∀tCritical connections can arise in two cases: Between UAVs: In this situation, relay UAVs are allocated based on established methods from the literature (e.g., Bekmezci et al. [32]).Between UAV and Central Station: A custom relay assignment algorithm is utilized, as detailed in Section 4.5. Relay Assignment Constraint: When critical connections are at risk, UAVs not assigned to targets act as relays to maintain network connectivity. The set of relay UAVs at any time t is defined as (8)UR(t)=U∖u∈U∣∑g∈GF(u,g,t)=1, ∀t Critical connections can arise in two cases: Between UAVs: In this situation, relay UAVs are allocated based on established methods from the literature (e.g., Bekmezci et al. [32]).Between UAV and Central Station: A custom relay assignment algorithm is utilized, as detailed in Section 4.5. Between UAVs: In this situation, relay UAVs are allocated based on established methods from the literature (e.g., Bekmezci et al. [32]). Between UAVs: In this situation, relay UAVs are allocated based on established methods from the literature (e.g., Bekmezci et al. [32]). Between UAV and Central Station: A custom relay assignment algorithm is utilized, as detailed in Section 4.5. Between UAV and Central Station: A custom relay assignment algorithm is utilized, as detailed in Section 4.5. C6: Energy Constraint: UAVs have limited energy resources. (9)Eu(t+1)=Eu(t)−eu(t), ∀u∈U,∀t where eu(t) is the energy consumption of UAV u at time t. Energy Constraint: UAVs have limited energy resources. (9)Eu(t+1)=Eu(t)−eu(t), ∀u∈U,∀t where eu(t) is the energy consumption of UAV u at time t. C7: Movement Constraint: UAVs move either toward their assigned targets or adjust their positions dynamically to act as relays. Relay UAVs actively reposition themselves based on the states and movements of the UAVs assigned to targets, ensuring continuous connectivity and maintaining the network as a single connected component. Movement Constraint: UAVs move either toward their assigned targets or adjust their positions dynamically to act as relays. Relay UAVs actively reposition themselves based on the states and movements of the UAVs assigned to targets, ensuring continuous connectivity and maintaining the network as a single connected component. C8: Initial Conditions: At t=0, the initial positions of UAVs and the central station are known, and the network is connected. Initial Conditions: At t=0, the initial positions of UAVs and the central station are known, and the network is connected. 4.3. Heuristic Algorithm Description Given the NP-hardness of the problem, we propose a heuristic algorithm that operates in discrete time steps. At each time step, the algorithm performs the following:Calculate Composite Valuation: For each UAV u and each target g, compute U(u,g,t) using Equation (3).Assign UAVs to Targets: Assign UAVs to targets based on the highest composite valuation, ensuring that each UAV is assigned to at most one target, in compliance with Constraint C1.Identify Relay UAVs: UAVs not assigned to targets become relay UAVs to maintain network connectivity.Relay UAV Allocation: Allocate relay UAVs to maintain network connectivity, as detailed in Section 4.5.Update Positions: Move UAVs toward their assigned targets or relay positions, considering their movement constraints and communication range.Update Energy Levels: Decrease the energy levels of UAVs based on their movement and communication activities, as per Constraint C6.Update Time Since Last Visit: For each target, update the time since it was last visited. If a UAV reaches a target, reset the time for that target.Repeat: Proceed to the next time step and repeat the process until the mission duration is reached or all targets have been sufficiently revisited. Calculate Composite Valuation: For each UAV u and each target g, compute U(u,g,t) using Equation (3). Calculate Composite Valuation: For each UAV u and each target g, compute U(u,g,t) using Equation (3). Assign UAVs to Targets: Assign UAVs to targets based on the highest composite valuation, ensuring that each UAV is assigned to at most one target, in compliance with Constraint C1. Assign UAVs to Targets: Assign UAVs to targets based on the highest composite valuation, ensuring that each UAV is assigned to at most one target, in compliance with Constraint C1. Identify Relay UAVs: UAVs not assigned to targets become relay UAVs to maintain network connectivity. Identify Relay UAVs: UAVs not assigned to targets become relay UAVs to maintain network connectivity. Relay UAV Allocation: Allocate relay UAVs to maintain network connectivity, as detailed in Section 4.5. Relay UAV Allocation: Allocate relay UAVs to maintain network connectivity, as detailed in Section 4.5. Update Positions: Move UAVs toward their assigned targets or relay positions, considering their movement constraints and communication range. Update Positions: Move UAVs toward their assigned targets or relay positions, considering their movement constraints and communication range. Update Energy Levels: Decrease the energy levels of UAVs based on their movement and communication activities, as per Constraint C6. Update Energy Levels: Decrease the energy levels of UAVs based on their movement and communication activities, as per Constraint C6. Update Time Since Last Visit: For each target, update the time since it was last visited. If a UAV reaches a target, reset the time for that target. Update Time Since Last Visit: For each target, update the time since it was last visited. If a UAV reaches a target, reset the time for that target. Repeat: Proceed to the next time step and repeat the process until the mission duration is reached or all targets have been sufficiently revisited. Repeat: Proceed to the next time step and repeat the process until the mission duration is reached or all targets have been sufficiently revisited. 4.4. Algorithm Steps Algorithm 2 outlines the heuristic procedure. Algorithm 2: Heuristic Algorithm for Multi-UAV Routing and Connectivity 4.5. Relay UAV Allocation The allocation of relay UAVs is critical to maintaining network connectivity in dynamic environments. Relay UAVs act as communication bridges between UAVs and the central station S or between UAVs at risk of losing connection due to distance constraints. The relay UAV allocation algorithm operates iteratively by updating UAV positions and roles to adapt to changing network conditions, ensuring mission success and optimal network performance. 4.5.1. Initialization of Variables and Structures At the beginning of each update cycle, critical variables and data structures are initialised:UAV Role Lists: –ULeader: UAVs assigned to targets (Leader UAVs).–URelay: UAVs assigned as communication relays.Adjacency Matrix (adj): –Represents the connections between UAVs and the central station.–Calculated based on UAV positions and the communication threshold Rc.At-Risk Links (Eatrisk): –Represents edges with distances satisfying 0.9·Rc