Drones and Autonomous Vehicles-logo
Drones and Autonomous Vehicles

A Position-based Hybrid Routing Protocol for Clustered Flying Ad Hoc Networks

Drones and Autonomous Vehicles-logo
Drones and Autonomous Vehicles
Submit to DAV Download PDF
Cite This Article
Contents

Article Open Access

A Position-based Hybrid Routing Protocol for Clustered Flying Ad Hoc Networks

Godwin Asaamoning 1,2,* Paulo Mendes 3
Author Information
1
Liberal Studies Department, Bolgatanga Technical University, Sumbrungu UB-0964-8505, Ghana
2
COPELABS, Universidade Lusofona, 1749-024 Lisbon, Portugal
3
Airbus Central Research and Technology, Taufkirchen, 82024 Munich, Germany
*
Authors to whom correspondence should be addressed.
Views:1036
Downloads:149
Drones and Autonomous Vehicles 2024, 1 (2), 10001;  https://doi.org/10.35534/dav.2024.10001

Received: 15 September 2023 Accepted: 10 January 2024 Published: 16 January 2024

Creative Commons

© 2024 by the authors; licensee SCIEPublish, SCISCAN co. Ltd. This article is an open access article distributed under the CC BY license (https://creativecommons.org/licenses/by/4.0/).

ABSTRACT: Unmanned aerial vehicles (UAVs) have been used to establish flying ad hoc networks (FANETs) to support wireless communication in various scenarios, from disaster situations to wireless coverage extensions. However, the operation of FANETs faces mobility, wireless network variations and topology challenges. Conventional mobile ad hoc network and vehicular ad hoc network routing concepts have rarely been applied to FANETs, and even then they have produced unsatisfactory performance due to additional challenges not found in such networks. For instance, position-based routing protocols have been applied in FANET, but have failed to achieve adequate performance in large networks. Clustering solutions have also been used in large networks, but with a significant overhead in keeping track of the complete topology. Hence, to solve this problem, we propose a hybrid position-based segment-by-segment routing mechanism for clustered FANETs. This approach facilitates traffic engineering across multiple wireless clusters by combining position-based inter-cluster routing with a rank-based intra-cluster routing approach capable of balancing traffic loads between alternative cluster heads. Simulation results show that our solution achieves, on average, a lower power consumption of 72.5 J, a higher throughput of 275 Mbps and a much lower routing overhead of 17.5% when compared to other state-of-the-art end-to-end routing approaches.
Keywords: UAV-FANETs; Cluster Networks; Position-based Routing; Segment-based Routing

1. Introduction

Due to the malleable, versatile, and adaptable characteristics of UAVs, FANETs have emerged as the new paradigm for establishing self-organizing wireless networks for all types of usage scenarios. The scope of FANETs covers the most critical aspects of military and civic scenarios, such as real-time traffic surveillance [1], disaster support services [2], public safety monitoring [3], wireless coverage extension [4], and UAV swarms as networked control systems [5]. However, routing protocols designed to support the operations of traditional networks, such as MANETs and VANETs, are not capable of satisfying the characteristic needs of FANETs [6], largely due to fluctuating topologies, varying distances between flying nodes, and environmental uncertainties that result in intermittent wireless disconnections. Besides, UAV-FANETs have limited processing capacity for the execution of prolonged tasks and varying quality of service needs, such as low latency, high reliability and robust network requirements, mostly for application in emergency rescue situations [7]. Fortunately, several routing approaches integrating different strategies have been designed to address the concerns of transmission reliability, delay and network partitioning in FANETs, although most of these solutions typically result in high packet losses and communication overhead. With such kind of complex attributes, UAV-FANETs may require the design of joint routing schemes capable at fulfilling their special characteristic needs [8], since it is difficult to understand which existing protocol has the best performance, as they all follow different evaluation methods and cannot solve the overall challenge of achieving efficient packet transmission while ensuring low levels of delay and packet loss [9]. In general, routing schemes for UAV-FANETs are classified according to topology-based, position-based, hybrid and bio-inspired routing [10]. Topology-based routing requires obtaining the topological information of the nodes in the network to facilitate packet transmission. The position-based routing approach involves forwarding data packets from a source node to a destination node based on information about the geographical position of the nodes. The hybrid routing approach, on the other hand, combines position-based and topology-based routing approaches to facilitate packet transmission, while the bio-inspired routing approach is driven by the social behaviours of insects to precede packet transmission [10]. It is evident that, despite the penetration of these routing strategies, the characteristic needs of UAV-FANETs have not been adequately addressed, thus requiring further research. Based on that, in pursuit of efficient operation of UAV-FANETs, Gupta et al. [11] investigated various metric factors in the routing approaches, focusing especially on analyzing their applicability in UAV-FANETs. The static routing approach was found to be unsuitable for dynamic networks, along with bandwidth wastage characteristics and network scalability challenges, while proactive routing proved slow to counter topology changes, resulting in network delays. Reactive routing also exhibits non-scalability factors along with high communication costs. Finally, the hybrid routing approach was found to be complex to implement, while the position-based routing approach presented resilience factors capable of handling dynamic network scenarios, but requires information about the nodes’ location to facilitate packet forwarding. Based on this, the authors reiterated the use of Global Positioning System (GPS) [8] services on board the flying nodes to address the challenge of providing location information in position-based routing to facilitate the reliability of packet transmission [12]. Similarly, the studies by Lakew et al. [10], compared the capabilities of position-based routing with other approaches in supporting FANET operations with guaranteed packet forwarding reliability. The study observed that position-based routing provides a sufficient concession to packet forwarding reliability due to its resilience to topology changes and the ability to explore various routing possibilities by selecting the best next hop forwarders. In the analysis, the authors used a dynamic application scenario and important benchmark requirements of memory and bandwidth utilization, signaling overhead, power consumption, latency and network size to account for the selection of next hop forwarders. The result showed that the position-based routing approach provided significant gains in the mentioned benchmark factors compared to other approaches. With regard to scalability challenges anticipated from high node mobility, topology and environmental dynamics, the comparative studies of Bujari et al. [13] showed that deterministic routing strategies implemented using the greedy-based approach offer exceptional network scalability properties in highly dynamic scenarios and are suitable for the deployment of cluster-based UAV-FANETs. A representative example is the cluster-based FANET approach implemented in Asaamoning et al. [14], which may allow the creation of large-scale UAV-FANETs capable of sustaining end-to-end communications in different clusters that may have varying network factors. Therefore, in an attempt to address the various anticipated network dynamics that may exist within and between each set of clusters to ensure that the overall network adapts to UAV mobility and wireless susceptibility influences, which are not prevalent in the much-researched MANET and VANET scenarios. We argue in this paper that the best approach to ensure a scalable and interoperable solution in clustered FANETs is to exploit a combination of position-based greedy and right-hand-rule routing approaches across multiple cluster heads (CHs) to address network scalability, stability and fault tolerance constraints, while a rank-based routing approach utilized within clusters to mitigate transmission reliability challenge in large UAV-FANETs. Our solution is independent of any clustering mechanism and, based on the literature, our approach is unique as it is the first proposal to apply a combination of the concept of segment-based and position-based routing in FANETs in an attempt to address the additional challenges faced in large cluster-based FANETs. We summarize our contributions in this article as follows: • An intra-cluster beaconless routing approach able to avoid unsuitable forwarding paths based on a simple ranking method. • An inter-cluster position-based routing approach able of reducing message overheads and to escape from void node situation. • An inter-operable end-to-end cluster-based routing mechanism able to forward traffic over a set of segments, the source cluster, the destination cluster, and the inter-cluster path. • Simulations show that the proposed segment-by-segment routing approach is able to significantly improve performance metrics related to average waiting time, packet drop count, routing overhead, transmission throughput and power consumption. The rest of this article is organized as follows: Section 2 presents related work on the performance and challenges of position-based routing protocols for FANETs. In Section 3, we present a background of the mechanisms and algorithms used to develop the proposed solution. Section 4 describes the proposed Position-based Hybrid routing protocol for clustered FANETs, detailing how packet forwarding within and between clusters is carried out to guarantee end-to-end communication. Section 5 presents the simulation and performance evaluation of the proposed protocol. Finally, section 6 presents our concluding remarks and future research direction.

2. Related Work

The design of routing schemes for highly dynamic networks such as UAV-FANETs needs to deal with challenges of frequent link interruptions, topology changes and node mobility constraints to provide for network robustness, self-organizing abilities and fault tolerance [15]. Position-based routing protocols [16] utilize both reactive and greedy-based forwarding strategies to establish paths for packets forwarding to target destinations. They are best known for having resilience properties capable of dealing with the dynamic factors present in FANETs to establish routing paths based on node location information [16]. Hence, to enable the effective utilization of position-based routing in FANET, the location information of nodes could be obtained from GPS on board the UAVs to help in estimating the shortest distance to a packet destination [8]. To this end, we can point to the existence of position-based routing solutions in the literature which have been proposed to support the requirements of different FANET scenarios. For instance, a geographic position-based routing protocol for UAV networks is proposed [17]. The protocol, which is a variant of position-based routing and hop-less routing, exploits both features to the benefit of utilizing all communication opportunities within the network, regardless of hop distances and link qualities. In addition, each node uses its location information to calculate its routing precedence in a distributed manner to reduce communication overheads. However, this protocol may be prone to accruing transmission losses and high power expenses. Another geographic-based routing protocol is proposed in [18] where the location of nodes are exploited to estimate the stability of link quality and node mobility. Hence, to ensure efficient discovery and routing, the protocol selects only those paths with sufficient connection to other nodes, while ignoring all disjoint paths. Though the protocol is favored by lower transmission delay, it is limited in terms of packet delivery losses and large routing overheads. Similarly, a genetic algorithm based on UAV-FANET performance optimization is suggested in [19], where the UAV positions are optimized with the aim of improving the transmission performance. The study considered the numbering area, correlation matrix, adjacency matrix and movement of UAV positions to significantly improve throughput performance. However, the supposed measure of throughput is questionable as it is merely estimated based on the distances between nodes and sensors. Yin et al. [20] proposed the design of Fountain-code routing approach for flying UAV networks by considering the geolocation information of nodes. In this protocol, the impacts from packet accumulation due to transmission delays are mitigated using a power allocation and routing strategy. Thus propelling the protocol to attain reliable end-to-end packets delivery under low delays, but, at the expense of raising forwarding costs. Recently, Hussen et al. [21] also proposed a stateless and predictive geographic multicast routing strategy. The algorithm reactively predicts the positions of neighboring nodes to allow for selecting neighboring relay capable of forwarding packets to multicast locations. The main goal being to improve transmission rates but, at the expense of high routing overhead. Similarly, Bousbaa et al. [22] introduced a novel geo-cast forwarding approach for UAV swarms. The protocol seeks to improve end-to-end packet delivery rate under low delays for a set of specific nodes, by taking into account the geographical locations and 3D motion of the nodes. This led to improved throughput rates but, at higher processing and power costs. In order to preserve the robustness and resilience of network links between aerial vehicles and between UAVs and the ground base station, a geolocation-based multi-hop routing protocol is proposed for FANETs [23]. For which each UAV periodically broadcast its position, direction and speed and based on that information, each UAV in the network select their next hop routers and proceed with routing using the greedy routing approach to reduce the impacts resulting from topology dynamics so as to ensure the reliability of packet delivery. Nevertheless, this protocol accrues higher communication and routing overhead due to constant broadcast of node navigation information for link prediction purpose. From analyzing the above literature, it is clear that the exclusive use of position-based routing approaches for FANET scenarios may not effectively meet their natural characteristic needs, hence our proposed solution aims to address these drawbacks. On the other hand, we can also trace the concept of position-based routing applied in both MANET and VANET scenarios. For example, the authors in [24] proposed a routing protocol based on a combination of geographic routing and location-based service for VANET. The aim of the protocol is to make it easier to reduce routing and communication costs. In [25] the authors proposed a position-based routing approach for MANETs. The goal being to influence communication in sparse MANETs by reducing routing cost and communication delay. Overall, based on the analyzed literature, we can state that due to the unique properties of FANETs, routing protocols designed for both MANET and VANET cannot directly be applied in FANET scenarios. It is on this basis that we are motivated to propose the design of a FANET routing protocol that encompasses a combination of the concepts of segment-based routing, position-based routing and SIR-based routing. While segment-based routing is used to influence traffic engineering and the processing of packets in transit through adjacent segments that support the chaining of service functions, position-based routing is used to incorporate the specific location information of the interconnected node into each adjacent segment. And finally, the SIR-based approach is used within segments to facilitate the selection of the best-positioned link to forward a packet towards the destination node.

3. Background

In this section, we present our proposed Position-based Hybrid Routing Protocol for Clustered Flying Ad Hoc Networks, which is based on the concepts of Segment-by-Segment based routing (SR) and Superiority and Inferiority rank-based (SIR) routing approaches. In general, SR is a concept that uses location information and node-specific designated routes to steer a packet across routing segments until the packet reaches its destination address [26]. The main reason is to ensure that only stable routing segments are selected, with the aim of reducing routing overheads while at the same time increasing throughput rates. The SIR-based approach, on the other hand, is a concept from information theory that seeks to analyze diversity in two flows (i.e., conditions in adjacent nodes) to ensure that the most capable node is selected with the aim of ensuring reliable packet transmission [27]. Basically, segment based routing is a traffic engineering mechanism that allows a routing packet to be encoded with a header extension known as a segment routing header (SRH). This encoding is called an SR policy and can be instantiated in Internet Protocol version 6 (IPv6) planes [28]. The information encoded in each segment list contains the routing tables and segment identifier (SID) information which, together, are used to steer a packet through specific topological routes, so that the information is extracted at the designated end of segment lists to facilitate the routing of a packet until it reaches it reaches its destination address (DA). Studies by Abdelsalam et al. [29] has shown that SRH provides sufficient support for various routing engines, including routers. To this end, packet forwarding in an SR policy can be instantiated as an ordered list of IPv6 SIDs in the SR extension header encoded at the source node. This means that the SRH, which contains the ordered list of segments along with the intermediate routes, is used to facilitate the forwarding of packets to the DA [28]. As can be seen in Figure 1, the SRH compared to the traditional IPv6 header, contains extra field attributes.
Figure 1. Segment Routing Extension Header [28].
The first field, known as “Next header”, is an 8-bit selector which function is to identify the type of header that follows the routing header. The adjacent field is the header extension length (Hdr Ext Len), which is an 8-bit unsigned integer with a routing header length in octet units. This is followed by the routing type, which is an 8-bit field attribute used to specify the type of routing variant to be executed. The “segment left” field is also an unsigned 8-bit integer that contains the exact number of segments remaining for the packet to navigate through till the DA. The “Last Entry” field contains the index zero and points to the last element in the list of segments. Flags are used to create a register to define new flags, such as unused or for future use, and are assigned a value of zero to be ignored during transmission. Meanwhile, the “Segment List” (SL) is 128-bits long and holds pointer SIDs defined up to the last segment of the SR policy (i.e., the DA). Segment lists are coded in reverse, starting with the first segment list to be processed (i.e., segment list [(n)]), while the next holds the segment list [(n-1)] [30]. Finally, the “Type Length Value” (TLV) is responsible for providing the metadata used for segment routing procedures. Many TLVs can be encoded in an SRH to define the format and semantics of the information contained in each one. Two bit (0 and 1) are used to specify whether or not the data encoded in the TLV can be modified during its motion. Data assigned to (0) cannot be modified, while data assigned to (1) can be modified. The studies in [30] also revealed that routing based on IPv6 segments supports dynamic network scenarios. As defined in Figure 1, the information to be encoded in each segment list includes IP addresses, however, our scenario, which is dynamic, requires GPS location information of the nodes. Thus, given that each packet segment list contains a 128-bit IPv6 address space, it sufficient to explicitly encode routes along with functions to be performed, such as the associated routing type at the end of a segment list. It is necessary to encode routing routes along with an intra and inter-cluster aligned routing function at the end of each segment list which is extracted to facilitate packet forwarding. In this case, we define and inversely code three types of information namely, (i) segment list [(2)] assigned as the position of the source node, (ii) segment list [(1)] assigned as the position of source CH, and (iii) segment list [(0)] assigned as the position of the destination CH. The information encoded at the end of each segment list, is extracted from the packet and, based on the information, intra-cluster or inter-cluster routing is carried out. It should be noted that each segment list contains a 128-bit address space, so, based on the studies by Navas et al. [31], eight bytes of floating point number address space is enough to optimally store a node’s GPS positioning information. Thus, the 128-bit address space of each segment list is sufficient to encode the GPS location information of a node to be used to facilitate position-based routing between CHs using the advanced Greedy Perimeter Stateless Routing (AGPSR) approach [32]. On the other hand, we explore the use of the Superiority and Inferiority ranking (SIR) method [27] for intra-cluster routing. SIR is a multiple criteria decision method (MCDM) implemented to analyze various conditions in the nodes with the aim of choosing an optimal solution (i.e., the best node capable of forwarding a packet). This ranking approach, as described in (c.f., Section: 4.1), is based on different priority levels and evaluates the alternatives using superiority and inferiority scoring notations to reflect the differences. This process is suitable for checking alternative factors with the aim of filtering out biases to arrive at a coherent and robust decision. It thus facilitates the selection of the best ranked node capable of providing reliability intra-cluster packet forwarding.

4. The Proposed Solution

This section presents the detailed explanation of the building blocks used to design the proposed position-based hybrid routing protocol, namely AGPSR routing between CHs and SIR-based intra-cluster routing. Due to the evolution of technologies such as GPS [8] mounted on UAVs, node geolocation information can be obtained and used to facilitate packet routing reliability, scalability and fault tolerance in a FANET scenario. In this context, the application of position-based routing, which uses the location information of nodes to perform routing, has become necessary as it can lead to the design of potent routing schemes capable of enabling the smooth operation of FANETs [33]. As revealed in [34] and [35], routing strategies that do not use the geo-location information of nodes to make routing decisions are potentially unreliable and do not scale well. Furthermore, as FANET deployments are largely mission-orientated they are often faced with wireless disconnections, scalability and resilience challenges studied in [36]. Thus, our motivation is to design the first interoperable hybrid routing protocol capable of traffic engineering a packet across segments, while at the same time executing instructions to select optimal routes to improve overall network performance. In the studies by Oubbati et al. [16], it was shown that the design of routing strategies using information on the position of the nodes allows for easy scaling and integration of the network based on an image of the nodes’ geographical locations. Thus, on this basis, we argue in this article that the design of FANET protocols based on hybrid position-based routing allows for greater inter-cluster connectivity capable of mitigating the frequent challenges of network partitioning and scalability, while transmission reliability challenges are solved through a rank-based routing approach. Mainly, the goal of CH-to-CH position-based routing is to harmonize the routed packets in a resilient way to ensure higher packet delivery rates. Thus, to support end-to-end communication between nodes in different clusters, the proposed routing solution follows a segment-by-segment routing approach, covering: i) intra-cluster routing within the sending node’s cluster, ii) inter-cluster routing between the source node’s CH and the destination node’s CH; and iii) intra-cluster routing from the destination node’s CH to the destination address. In the proposed solution, the rank-based scheme and the position-based routing approaches are mainly considered to ensure that the mobility attributes and the 3D structure of the FANET are taken into account to improve transmission reliability and scalability factors. In the initial configuration, all deployed nodes are configured with the base station’s geographic information, allowing the UAVs to periodically update their positions, speed and direction using position-based routing. The flowchart in Figure 2 describes the path of a packet from a source node, through intra-cluster routing to inter-cluster routing and back to intra-cluster routing, until the packet reaches the destination node. In our implementation, as indicated above, each segment list is encoded with GPS positioning information, along with the association of the segments with an intra-cluster or inter-cluster routing function, which is extracted at the end of each segment list and used for routing purposes.
Figure 2. Intra-and Inter-cluster forwarding flowchart.
4.1. Intra-Cluster Routing As indicated earlier, the intra-cluster beaconless forwarding is facilitated by the SIR-based method, allowing for the MCDM to analyze diverse conditions in the nodes towards the choice of an ideal node capable of forwarding the packet. Therefore, to carry out intra-cluster routing, the source node uses the beaconless SIR procedure to broadcast the packet to be sent. All neighboring nodes receive the packet and each node calculates a rank based on link quality lq, distance di, speed si, queue length Ql, location loc and direction dir in relation to the destination node. All nodes are configured to the sliding windows of the transmission protocol to delay their transmission based on the calculated rank thereby permitting only the highest ranked nodes to transmit the packet while the lower-rated nodes stop transmitting after hearing the transmission from the higher-rated node, which helps to reduce wasted bandwidth. 4.2. Inter-Cluster Routing On the other hand, inter-cluster routing between CH and CH is carried out using two techniques, namely the AGPSR and right hand rule routing approaches. Greedy routing is used at any feasible location to discover paths for packet forwarding, but fails only when a void node situation is reached. So, to facilitate greedy routing, using Figure 3 as an example, we assume that nodes B, C, D and E are elected CH’s of a group of clusters in a FANET scenario. The transmission radius of CH D does not cover any other CH. However, the transmission radius of CH E encompasses CH D, as illustrated by the dashed lines in an arc. In addition, the transmission radius of node B encompasses C and E. It is also assumed that node C’s coverage radius encompasses B and E, which means that E can only receive from C but cannot do the reverse for C. On the other hand, B’s radius encompasses both C and E, as shown in the thick circle. So, in a scenario like this, if node A, a member of CH B, wants to forward a packet to node F, a member of CH E, intra-cluster forwarding is carried out by node A to B. Then, to start CH-to-CH routing, node B extracts the coded information from the embedded GPS position along with the type of function to be performed at the end of segment list A and, based that information, starts to perform greedy inter-cluster routing to the CH closest to the destination node (i.e., CH E). At node E, the information at the end of segment list B is extracted and used to perform intra-cluster routing to the destination address (i.e., F), as illustrated in Figure 3.
Figure 3. Greedy forwarding example.
However, when faced void situation during CH-to-CH inter-cluster routing, where the CH carrying the packet is closer to the destination node’s CH but unable to navigate further, the right hand rule mode approach is used to traverse the packet through the edges of the void regions in search of paths to forward to the destination CH. But in the unlikely event that no route is found, the packet is discarded. 4.3. End-to-End Segment-based Routing Operation In our implementation, the basic assumption is that a packet is expected to be sent and received by cluster members in separate clusters in a FANET scenario. Thus, to ensure efficient end-to-end communication, we exploit our novel Position-based Hybrid routing protocol in which a rank-based routing technique is used to perform intra-cluster routing, while a greedy-based routing, in synchronization with the right hand rule, performs inter-cluster CH-to-CH routing. We describe below how a source node composes a packet to be sent through multiple clusters using the concept of segment-based routing until the packet reaches its destination. For the purpose of end-to-end routing, our network is grouped into separate clusters each of which has a known elected CH and a group of cluster members. Since the GPS location of the base station is known, the nodes periodically use position-based routing to update their position information with the base station. Then, to perform segment-by-segment routing [28], the source node composes the packet to be send by assigning to each end of the segment list the updated position information of the expected routing routes needed to forward the packet to the destination node. For this reason, like the packet encodings in Figure 1, the position of the source node is assigned to the segment list [(2)] and its address space is encoded with the GPS location information of the source CH. For this purpose, beaconless intra-cluster routing is carried out and the SIR-based method is implemented to select the best node to forward the packet to the source node’s CH. When the packet reaches the position of the source CH (i.e., segment list [(1)], information is extracted at the end of the segment list [(2)] to provide the routing type information. From then on, inter-cluster routing using the AGPSR approach facilitates the forwarding of the packet to the CH of the destination node (i.e., the position of segment list [(0)]). However, if during the CH-to-CH AGPSR routing process a void node situation is reached, where the CH carrying the packet is closest to the destination CH but cannot reach it, the right hand rule approach is used to forward the packet to the destination CH, but if a route is unlikely to be found, the packet can be discarded. Finally, at the destination node’s CH (i.e., segment list [(0)]), the destination node’s GPS positioning information is extracted from the end of the segment list [(1)] along with information on the type of routing to be carried out and based on the information switches to beaconless intra-cluster routing using the SIR-based method to select the best node to forward the packet to the destination address.

5. Performance Evaluation

This section evaluates the proposed Position-based Hybrid Routing Protocol for Clustered Flying Ad Hoc Networks (Position-based hybrid routing), with the aim of validating its effectiveness with respect to the impact of the average end-to-end waiting time of the number of UAVs, the impact of the average packet drop count, the impact of the average routing overhead, as well as the impact of the average throughput with respect to the number of UAVs. The SIR (i.e., intra-cluster) approach aims to ensure the selection of the best-ranked adjacent node to facilitate the efficient routing of packets to the connecting nodes in the direction of an intra-cluster head, in order to reduce routing overhead and to influence throughput rates. The SR (i.e., Inter Cluster) approach aims to guarantee network scalability and resilient routing from CH-to-CH, while avoiding transmission congestion. The overall goal of our proposed Position-based hybrid routing is to couple the intra-cluster and inter-cluster segments of the protocol to ensure robust network performance. 5.1. Simulation Model We implemented the performance evaluation of our proposed solution using the NS-3 simulator, in which various performance metrics were evaluated. The 2.4 GHz frequency range of the IEEE 802.11n standard [37] was used to perform the communication. The Rayleigh channel model was used with the aim to allow for calculating channel fading characteristics. Our simulation environment is set to 1000 m × 1000 m × 880 m. The UAVs are placed in 3D spaces and have bi-direction communication capability to a ground base station. The mobility of the nodes is based on the random way point (RWP) motion model. Thus, in order to obtain the most realistic configuration of the progressive variations of the speed and direction of the nodes, the JAVA code of the RWP model was imported to allow the setting of motion parameters on the nodes [38]. The packet size is set to 600 bytes while simulation duration is 100 seconds. In Table 1 and Table 2, we further provide the summaries of the system configurations and the simulation parameters. To investigate the end-to-end routing performance of the proposed protocol, we considered a simulation scenario with an increasing number of nodes (i.e., between 10 and 100). We assume that cluster members communicate with adjacent nodes towards a CH and that any communication outside the cluster is done via the CH. Each CH aggregates the packets from the member nodes and forwards them to the CH where the destination node is located.
Table 1. System Configuration.
Table 2. Simulation Parameters.
5.2. Results To effectively evaluate the end-to-end routing efficacy of our routing mechanism, we compared it with two end-to-end routing protocols, namely the Energy-Efficient Opportunistic Routing Protocol (EEOR) [38], which utilizes the positions of nodes in the network to predict their trajectories to address packet re-transmission and power consumption challenges, and the Smart IoT Control-Based Nature Inspired Energy Efficient Routing Protocol (NIEEOR) [39], which uses an power stabilizing limit in FANET aiming to select only nodes with higher power than the threshold to ensure for forwarding reliability and enhance throughput. (a) Impact of Average Waiting Time: The average waiting time of our solution is compared with the existing approaches regarding number of UAVs. The waiting time represents the time taken for the packet to be queue until the source node receives an acknowledgement to start transmitting. Our approach outperformed the compared protocols with an average waiting time of 0.18 seconds compared to the worst performance of the existing approaches in terms of average waiting time of 0.35 seconds, shown in Table 3.
Table 3. Analysis of Average Waiting Time in Seconds.
As shown in Figure 4, the average waiting time increases when the number of UAVs increase. The average waiting time of our approach is minimal due to the use of the intra-cluster best ranked forwarding strategy, thus facilitating a fast discovery process to select the best ranked node to help forward packets without delays.
Figure 4. Number of UAVs vs. Average Waiting Time (s).
(b) Impact of Average Packet Drop Count: The packet drop count represents a percentage of the total number of unsuccessful packet deliveries caused by unavailable routes for packet forwarding to the destination node. Factors that can contribute to packet drops in FANETs include topology changes, network traffic overload and fast node mobility attributes. The network size and the average packets dropped are illustrated in Figure 5, which illustrate the reliability of our approach compared to other existing protocols.
Figure 5. Time vs. Average Packet Drop Count.
The average packet drop count in our approach is lower mainly due to implementing beaconless rank-based intra-cluster routing aiming to ensure for fast selection of the best ranked node to facilitate in packet forwarding to reduce traffic flooding, while the execution of AGPSR inter-cluster routing aims to use the location of nodes to facilitate accurate route discovery for reliable CH-to-CH packet forwarding. Thus, the results presented in Table 4 provides an average percentage packet dropped count of 13.7% in our solution, which is much lower and better than the average dropped packet count of 23.8% and 32.5%, respectively, obtained by the existing compared approaches. This implies that use of beaconless ranked-based intra-cluster routing and position-based inter-cluster routing stimulates good routing performance. While the increased packet drop count in the existing protocols may be attributed to inefficient convergence arising from scalability challenges leading to packet re-transmission and congestion. (c) Impact of Average Routing Overhead: Routing overhead constitute the ratio of all generated messages including the control packets transmitted by the routing protocol. Control messages comprise of Hello packets and the node location information inserted in packet headers for topology construction and routing decisions. Figure 6 represents a comparison of our approach to the existing approaches concerning the effect of routing overheads as a function of network density. Notice that, as number of nodes expands, the overhead also increases as a result of large numbers of exchanged control messages. The average routing overhead on our approach is lower than the existing approaches due to the performance of beaconless intra-cluster routing which helps to reduce message flooding. Also, use of GPS on-board the UAVs facilitated in obtaining node location information for reliable inter-cluster routing hence, contributed in reducing routing overhead in our approach.
Figure 6. Number of UAVs vs. Average Routing Overhead.
Table 4. Analysis of Average Packet Drop Count in Percentage.
The average routing overhead on our approach is lower than the existing approaches due to the performance of beaconless intra-cluster routing hence reduced message flooding. Also, use of GPS on-board the UAVs facilitated in obtaining node location information for reliable inter-cluster routing hence, contributed in reducing routing overhead in our approach. Table 5 provides the analysis of the average routing overhead of our approach and existing approaches concerning the number of UAVs. The existing protocols attained an average routing overhead of 25% and 30% respectively, which is worse than our solution, which obtained an average routing overhead of 17.5%. The reason is that the existing protocols generated huge topology control messages and HELLO messages to manage the routing table, which results in packet flooding and congestion. Thus, increasing the routing overhead.
Table 5. Analysis of Average Routing Overhead in Percentage.
(d) Impact of Average Throughput: Throughput is the measure of the quantity of data packets successfully transmitted from source to destination megabytes per second (Mbps). The comparison of the average throughput between our solution and the existing approaches with respect to the number of UAVs is presented in Figure 7.
Figure 7. Number of UAVs vs. Average Throughput (Mbps).
The average throughput of our approach is higher due to the efficient intra-and inter-cluster routing of packets to overcome bandwidth wastage, delays and packet retransmissions caused by congestion. Thus, our approach facilitated the fast and reliable transmission of packets from source to destination, achieving a higher throughput compared to the existing approaches, as shown in Table 6.
Table 6. Analysis of Average Throughput in (Mbps).
Our approach achieved an average transmission rate of 275 Mbps, while the existing approaches achieved a much lower average transmission rate of 227.5 and 202.5 Mbps, respectively. (e) Impact of Average Power Consumption: Power utilization by nodes is a critical measure that affects the performance of FANETs as the UAVs have power limitations. We have considered cumulative power consumption for packets to be transmitted against increasing UAVs consumption. Figure 8 shows that our approach consumes averagely a less cumulative power compared to the existing protocols.
Figure 8. Number of UAVs vs. Average Power Consumption (J).
This is attributed to the efficient execution of ranked-based beaconless intra-cluster routing and AGPSR inter-cluster routing which ensured the reliability of packet transmission. In contrast, the EEOR and NIEEOR protocols are based on beacon routing which floods the network with control and HELLO messages in their quest to discover routing routes. This leads to bandwidth wastage and network congestion. To that effect, as the nodes persist to re-transmit dropped packets, they are faced with excess processing and routing demand leading to a drain on each UAVs energy. Table 7 presents a comparison of the average power consumed in joules (J) by our routing approach and the existing approaches. As observed, when the number of nodes increases, the cumulative power consumption of UAVs also increases. However, comparatively, the average cumulative power consumed by our routing protocol amounts to 72.5 J, which is lower than the 98 J and 122.5 J energies respectively consumed by the existing protocols. This shows that our proposed solution far outperformed the existing protocols in the dynamic FANET scenarios analyzed.
Table 7. Analysis of Average Power Consumption in Joules.

6. Conclusions and Future Work

In this paper, a position-based hybrid routing protocol for large UAV-FANETs is proposed to improve routing performance in clustered networks. The proposed mechanism has succeeded in improving routing with respect to performance metrics such as the average waiting time, average dropped packets, average routing overhead, average throughput and average power consumption by the UAVs. This was achieved by effectively cementing the rank-based intra-cluster routing in synchronization with greedy, right-hand rule-based inter-cluster routing, using the concept of segment-based routing to reduce route discovery delays for packet forwarding reliability, while addressing the situation of void node for stable and resilient packet transmission. This is demonstrated in the simulation results, which show that our proposed solution outperformed the compared existing approaches in all metrics measured. Our future research focus will be to implement our solution using a real-world testbed.

Author Contributions

Both authors contributed as follows: Conceptualization, G.A. and P.M.; Data curation, G.A.; Formal analysis, G.A. and P.M.; Funding acquisition, P.M.; Investigation, G.A and P.M.; Methodology, G.A. and P.M.; Project administration, P.M.; Resources, P.M.; Software, G.A.; Supervision, P.M.; Validation, G.A and P.M.; Visualization, G.A. and P.M.; Writing—original draft, G.A. and P.M.; Writing—review & editing, G.A. and P.M.

Ethics Statement

Not applicable.

Informed Consent Statement

Not applicable.

Funding

This work was supported by H2020-MSCA-RISE under grant No 101006411; and by national funds through FCT, Fundação para a Ciência e a Tecnologia, under project UIDB/04111/2020.

Declaration of Competing Interest

The authors declare no conflict of interest.

References

1.
Yanmaz E, Yahyanejad S, Rinner B, Hellwagner H, Bettstetter C. Drone networks: Communications, coordination, and sensing. Ad Hoc Netw. 2018, 68, 1–15. [Google Scholar]
2.
Chen X, Tang J, Lao S. Review of unmanned aerial vehicle swarm communication architectures and routing protocols. Appl. Sci. 2020, 10, 3661. [Google Scholar]
3.
Agrawal J, Kapoor M. A comparative study on geographic-based routing algorithms for flying ad-hoc networks. Concurr. Comput. Pract. Exp. 2021, 33, e6253. [Google Scholar]
4.
Zeng Y, Zhang R, Lim TJ. Wireless communications with unmanned aerial vehicles: Opportunities and challenges. IEEE Commun. Magazine 2016, 54, 36–42. [Google Scholar]
5.
Asaamoning G, Mendes P, Rosário D, Cerqueira E. Drone swarms as networked control systems by integration of networking and computing. Sensors 2021, 21, 2642. [Google Scholar]
6.
Perumal SR, Muthumanikandan V, Sushmitha J. Flying Ad hoc Networks Routing Constraints and Challenge Perspectives. In Modelling and Simulation of Fast-Moving Ad-Hoc Networks (FANETs and VANETs); IGI Global: Hershey, PA, USA, 2023.
7.
Magaia N, Mastorakis G, Mavromoustakis CX, Pallis E, Markakis EK. Intelligent Technologies for Internet of Vehicles; Springer: Berlin/Heidelberg, Germany, 2021.
8.
Rosati S, Kruzelecki K, Heitz G, Floreano D, Rimoldi B. Dynamic routing for flying ad hoc networks. IEEE Trans. Veh. Technol. 2015, 65, 1690–1700. [Google Scholar]
9.
Moreira W, Mendes P, Sargento S. Assessment model for opportunistic routing. In Proceedings of IEEE Latincom, Belem, Brazil, 24–26 October 2011.
10.
Lakew DS, Sa’ad U, Dao NN, Na W, Cho S. Routing in flying ad hoc networks: A comprehensive survey. IEEE Commun. Surv. Tutor. 2020, 22, 1071–1120. [Google Scholar]
11.
Gupta L, Jain R, Vaszkun G. Survey of important issues in UAV communication networks. IEEE Commun. Surv. Tutor. 2015, 18, 1123–1152. [Google Scholar]
12.
Hayat S, Yanmaz E, Muzaffar R. Survey on unmanned aerial vehicle networks for civil applications: A communications viewpoint. IEEE Commun. Surv. Tutor. 2016, 18, 2624–2661. [Google Scholar]
13.
Bujari A, Palazzi CE, Ronzani D. A comparison of stateless position-based packet routing algorithms for FANETs. IEEE Trans. Mob. Comput. 2018, 17, 2468–2482. [Google Scholar]
14.
Asaamoning G, Mendes P, Magaia N. A dynamic clustering mechanism with load-balancing for flying ad hoc networks. IEEE Access 2021, 9, 158574–158586. [Google Scholar]
16.
Oubbati OS, Lakas A, Zhou F, Güneş M, Yagoubi MB. A survey on position-based routing protocols for Flying Ad hoc Networks (FANETs).  Veh. Commun. 2017, 10, 29–56. [Google Scholar]
17.
Pang X, Liu M, Li Z, Gao B, Guo X. Geographic position based hopless opportunistic routing for UAV networks.  Ad Hoc Netw. 2021, 120, 102560. [Google Scholar]
18.
Cantú-Paz E, Foster JA, Deb K, Lawrence D, Roy R, O’Reilly U, et al. Genetic and Evolutionary Computation-GECC: Genetic and Evolutionary Computation Conference Chicago; Springer: Chicago, IL, USA, 2003. 
19.
Liu J, Huo S, Wang Y. Throughput optimization for flying ad hoc network based on position control using genetic algorithm. Int. J. Metrol. Qual. Eng. 2020, 11, 11. [Google Scholar]
20.
Yin C, Xiao Z, Cao X, Xi X, Yang P, Wu D. Enhanced routing protocol for fast flying UAV network. In Proceedings of the 2016 IEEE international conference on communication systems (ICCS), Shenzhen, China, 14–16 December 2016.
21.
Hussen HR, Choi S, Kim J, Park J. Stateless and predictive geographic multicast scheme in flying ad-hoc networks. In Proceedings of the 2017 Ninth International Conference on Ubiquitous and Future Networks (ICUFN), Milan, Italy, 4–6 July 2017.
22.
Bousbaa FZ, Kerrache CA, Mahi Z, Tahari AEK, Lagraa N, Yagoubi MB. GeoUAVs: A new geocast routing protocol for fleet of UAVs.  Comput. Commun. 2020, 149, 259–269. [Google Scholar]
23.
Choi S, Hussen HR, Park J, Kim J. Geolocation-based routing protocol for flying ad hoc networks (FANETs). In Proceedings of the 2018 Tenth international conference on ubiquitous and future networks (ICUFN), Prague, Czech, 3–6 July 2018.
24.
Ayaida M, Barhoumi M, Fouchal H, Ghamri-Doudane Y, Afilal L. Joint routing and location-based service in VANETs. J. Parallel Distribut. Comput. 2014, 74, 2077–2087. [Google Scholar]
25.
Hu CL, Sosorburam C. Enhanced geographic routing with two-hop neighborhood information in sparse MANETs. Wirel. Pers. Commun. 2019, 107, 417–436. [Google Scholar]
26.
Filsfils C, Nainar NK, Pignataro C, Cardona JC, Francois P. The Segment Routing Architecture. In Proceedings of the 2015 IEEE Global Communications Conference (GLOBECOM), San Diego, CA, USA, 6–10 December 2015. 
27.
Xu X. The SIR method: A superiority and inferiority ranking method for multiple criteria decision making. Eur. J. Oper. Res. 2001, 131, 587–602. [Google Scholar]
28.
IPv6 Segment Routing Header (SRH). Available online: https://tools.ietf.org/html/draft-ietf-6man-segment-routing-header-18 (accessed on 20 November 2021).
29.
Abdelsalam A, Ventre PL, Scarpitta C, Mayer A, Salsano S, Camarillo P, et al. SRPerf: A performance evaluation framework for IPv6 segment routing. IEEE Trans. Netw. Serv. Manag. 2020, 18, 2320–2333. [Google Scholar]
30.
Ventre PL, Salsano S, Polverini M, Cianfrani A, Abdelsalam A, Filsfils C, et al. Segment routing: a comprehensive survey of research activities, standardization efforts, and implementation results.  IEEE Commun. Surv. Tutor. 2020, 23, 182–221. [Google Scholar]
31.
Navas JC, Imielinski T. GeoCast—Geographic addressing and routing. In Proceedings of the 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking, Budapest, Hungary, 26–30 September 1997.
32.
Laanaoui D, Raghay S. A new Advanced Greedy perimeter stateless routing for Vehicular Ad Hoc Networks. J. Phys. Conf. Ser. 2021, 1743, 012022. [Google Scholar]
33.
Stojmenovic I. Position-based routing in ad hoc networks. IEEE Commun. Mag. 2002, 40, 128–134. [Google Scholar]
34.
Meng X, Wang W, Leong B. SkyStitch: A cooperative multi-UAV-based real-time video surveillance system with stitching. In Proceedings of the 23rd ACM international conference on Multimedia. Brisbane, Australia, 26–30 October 2015. 
35.
Sun Z, Wang P, Vuran MC, Al-Rodhaan MA, Al-Dhelaan AM, Akyildiz IF.  BorderSense: Border patrol through advanced wireless sensor networks.  Ad Hoc Netw. 2011, 9, 468–477. [Google Scholar]
36.
Karp B, Kung H. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. Boston, MA, USA, 6–11 August 2000. 
37.
Paul T, Ogunfunmi T. Wireless LAN comes of age: Understanding the IEEE 802.11 n amendment.  IEEE Circuits Syst. Mag. 2008, 8, 28–54. [Google Scholar]
38.
Sang Q, Wu H, Xing L, Ma H, Xie P. An energy-efficient opportunistic routing protocol based on trajectory prediction for FANETs. IEEE Access 2020, 8, 192009–192020. [Google Scholar]
39.
Khan IU, Qureshi IM, Aziz MA, Cheema TA, Shah SBH. Smart IoT control-based nature inspired energy efficient routing protocol for flying ad hoc network (FANET).  IEEE Access 2020, 8, 56371–56378. [Google Scholar]
TOP