{'fraction_non_alphanumeric': 0.02473617560151963, 'fraction_numerical': 0.004178978471929084, 'mean_word_length': 4.967506297229219, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Mobility-assisted adaptive routing for intermittently connected FANETs

Flying Ad Hoc Network (FANET), a self-configuring network consisting of Unmanned Aerial Vehicles (UAVs), can undertake different kinds of civilian and military tasks. As a particular instance of FANETs, intermittently connected FANETs (IC-FANETs) are characterized by a highly dynamic network topology and intermittent connectivity. Existing routing algorithms have been proposed for FANETs given that the underlying network is well connected, which are not suitable for such network environments. In this paper, we present a geographic routing algorithm called mobility-assisted adaptive routing (MAAR) targeting IC-FANETs. Different from conventional geographic routing protocols exploiting other location services to obtain the location information, MAAR combines routing strategy with location service in order to reduce the packet latency and routing overhead. MAAR updates the information of neighbour nodes dynamically according to nodal mobility and introduces a new metric called IDM to update the positions of other nodes in the network adaptively. In addition, we use a store-carry-and-forward paradigm to handle the technical issues of networks suffering from communication interruptions. When the forwarder node does not have any solution to find an appropriate relay node, mobility is exploited. Simulation results demonstrate that the MAAR scheme performs remarkably in terms of packet delivery ratio, throughput and routing overhead.


Introduction
The last decade has witnessed the widely use of Unmanned Aerial Vehicles (UAVs) in various civilian and military applications [1]. In most cases, such as reconnaissance operation, mapping, search and rescue, several UAVs form an ad hoc connected group to complete difficult tasks in a large area. Due to the high degree of UAVs' mobility and the low density, the network is not fully connected, and a contemporaneous path can never be assured to exist between any two nodes. We call this class of network intermittently connected Flying Ad Hoc Network (IC-FANET), which is a type of Delay/Disruptive Tolerant Network (DTN) [2].
In IC-FANETs, the sparse and highly dynamic topology results in frequent link disconnections, which makes the design of routing mechanism more challenging. Existing routing algorithms in FANETs [3][4][5] assume that there usually exists at least one complete path between source and destination, which may be well suited for fully connected environment. However, they are not able to forward packets efficiently in intermittent, partially connected network environments. Consequently, a routing layer with high efficiency and resilience is of critical importance for IC-FANETs. Compared to topology-based routing scheme, position-based routing scheme is more suitable for this kind of networks. The scheme utilizes the geographic position of mobile nodes to forward data packets, and eliminates the need to consider whether there exists a contemporaneous sourcedestination path. Previous works usually use routing and location services separately. The location information is maintained by extra location-based services in a distributed manner. When routing packets, to obtain the destination position, the source node launches a request to the location services. This approach increases end-to-end delay. What is more, the overhead produced by inquiring the location service is not considered when evaluating the performance of a protocol.
To this end, in this paper, we propose a geographic routing protocol called mobility-assisted adaptive routing (MAAR) specific to IC-FANETs, which combines routing strategy with location service effectively. In order to achieve high accuracy with low overhead, MAAR updates the information of neighbour nodes and the positions of all nodes in the network using different adaptive strategies respectively. Specifically, based on nodal mobility, it adjusts the frequency of beacons dynamically, which is used to update the positions and velocities of neighbours. At the same time, in order to maintain the positions of all nodes in the network, the Position Update messages recording the updated location information of other nodes are broadcast. We define a new metric IMP to measure the importance degree of the Position Update message. When IMP reaches a certain threshold, the message is propagated to its neighbours. In this way, not only the source node is able to obtain the destination's position immediately, but also forwarder nodes can update the destination's position in a packet if they own fresher location about the destination.
To route packets, MAAR adopts the store-carry-forward paradigm to overcome intermittent connections. When failing to find any node to forward data packet according to movement direction and location, the forwarder nodes are allowed to carry the packet for a certain distance until the suitable node or destination emerges within its communication range. In other words, nodal mobility is exploited to help transmitting data packets.
The remainder of this paper is organized as follows. Section 2 reviews the related work. Section 3 gives details on the proposed routing protocol specific to IC-FANETs. Simulation setup and results are discussed in Section 4. Finally, the paper is concluded in Section 5.

Related works
A massive body of studies have been dedicated in ad hoc networks. In this section, we briefly give an overview of relevant research in two categories of routing protocols, geographic routing and delaytolerant network routing.

Geographic routing
Brad Karp et al. [6] propose Greedy Perimeter Stateless Routing (GPSR) that makes greedy forwarding decisions using only information about forwarder node's immediate neighbours in the network topology. Once the greedy forwarding is impossible, the algorithm switches to the perimeter mode. Seung Hyeon el at. [7] propose a new geographic routing protocol called Geographic Routing Protocol for Aircraft Ad Hoc Network (GRAA), which update the whole topology of network by the information sent from base station. In order to choose the best intermediate nodes during routing, GRAA predicts the neighbours' location before forwarding data packets. In[8], the Location-Aided Routing (LAR) is presented which limits the search for a new route to a small request zone of the network. However, GPSR, LAR, and the routing protocols in [9][10][11] need the help of some kinds of location service to retrieve the destination position before routing packets. Both [12] and [13] propose adaptive position update schemes for geographic routing protocol. However, the schemes are insufficient for IC-FANETs to handle the disruptive connections effectively.

Delay-tolerant networking (DTN)
In most basic routing algorithms of DTN Networks like Epidemic algorithm [14], PRoPHET algorithm [15], the overhead is one of the most considerable issues. Spyropoulos et al. [16] introduce a limited flooding-based routing scheme called Spray and Wait, including two phases: spray phase and wait phase. In spray phase, a source node generates L packet copies, then spreads these copies to L different relaying nodes. In wait phase, these L relaying nodes carry the packet copy and forward it only to its destination. The mechanism is popular owing to its simplicity, but at the same time a large number of copies generated in spray phase do not make the overhead performance improved obviously. Furthermore, spreading packet copies without accurate direction increases the end-to-end delay. In [17], Plankton considers to dynamically reduce the number of copies that a message can be replicated. [18] combines multi-hop and mobility-assisted routing protocols from a resource allocation point of view.
The mechanisms in [19][20][21] take routing decisions based on geographical location data designed for Vehicular delay-tolerant network (VDTN), but they are evaluated using vehicles that move along streets with static destinations, which are inadequate for IC-FANETs. Kuiper et al. [22] present a location-aware routing for delay-tolerant networks (LAROD). A beacon-less strategy is used to achieve low overhead. However, the setting of delay timer for selecting new custodian introduces substantial delay, the discussion about which is missing.

Mobility-assisted adaptive routing protocol
The aim of Mobility-assisted Adaptive Routing Protocol (MAAR) is to adapt the intermittent networks, enhancing the packet delivery ratio while not generating too high overhead. MAAR integrates location service into routing mechanism, the advantage of which is to reduce the delay at the packet source. At the same time, the destination's position in a packet is capable to be updated during the transmission, which makes the information more accurate and thus increases the delivery rate. In this section, we detail the two main components of MAAR: dynamic location update strategy and mobility-assisted forwarding strategy.
Like other geographic routing protocols, MAAR makes routing decisions based on location information. Due to the high mobility of the nodes in IC-FANETs, the topology changes frequently.
The key issue is how to maintain the accurate information about other nodes. Period broadcasting of beacons is not satisfied for this kind of networks. Because beaconing in a fixed short interval wastes a great deal of communication overhead for those nodes that do not exhibit significant dynamism. On the other hand, if beacons are propagated in a fixed long interval, it is very likely that outdated locations are utilized, which is adverse to routing packets effectively. Consequently, MAAR employs a dynamic location update strategy, which consists of adaptive beacon update and global position update. The former provides position and velocity information to one-hop neighbours while the latter is destined to make nodes known the positions of all possible destination.

Adaptive beacon update
Assume that all nodes are aware of their own positions and velocities. Each node broadcasts beacons to notify neighbours of its updated position and velocity information. Similar to [11], in order to achieve both position accuracy and low overhead simultaneously, the transmission frequency of beacons is adapted to the nodes' motion. That is to say, highly mobile nodes are required to sending updates frequently since their positions are changing rapidly. On the contrary, for those nodes that move slowly, the beacon generation rate does not need to be frequent due to the relative stable topology.
Denote (x In a real world, UAVs cannot move in a random trajectory because of the kinematic and dynamic constraints. Thus, the estimated location at current time t can be predicted based on the existing information, by using the following equations: Then node N is able to compute the location estimation error, that is the distance between the actual and predicted positions: If the deviation d is greater than an acceptable threshold DTH, it can be concluded that the nodal motion (speed or direction) has changed to a great extent. A new beacon needs to be sent to broadcast its current actual position and velocity. In the same way, when a node intends to acquire the current positions of neighbours, it can be predicted according to equation (1).
However, if node N moves at a constant speed for a long time, there is no difference between the actual position and the estimated value. According to above rule, a new beacon update will not be sent from node N. This gives rise to the problem that the new neighbour which enters into the transmission range of node N after last broadcast, is unaware of the existence of node N. Therefore, MAAR specifies that if mobile nodes have not broadcast its information in a certain period of time TTH, a new beacon also needs to be sent.

Global position update
In an IC-FANET environment, the topology is prone to be partitioned. This condition means that inquiring destination's position by any extra location service will bring lots of delay and offer outdated information. Thus, MAAR integrates the location service with routing mechanism. In MAAR, all nodes are regarded as location servers, convenient for gaining the destination's position when needed. Each node owns a global position table, which maintains positions of other nodes in the network it knows. Since the nodes in IC-FANETs move very quickly, the position data often needs to be updated. If every node exchanges all known position information with others, the size of the message would be quite large while valid information may be small. The reason is that most positions are very likely to be duplicate with last delivered message.
Hence, in MAAR, each UAV uses a waiting queue to store the information of those nodes that positions have been updated since last broadcast, including the id, position and updated time. Then the Position Update message containing such information is propagated to neighbours when certain conditions are satisfied. The amount of information in the waiting queue not only depends on the time, but equally on the nodal mobility and other factors. Periodical broadcast cannot guarantee low overhead and high accuracy at the same time. Consequently, MAAR transmits the Position Update messages dynamically according to the quantity of information.
We present a metric called Importance Degree of Message (IDM) to measure the quantity of message, synthetically considering the timeliness, effectiveness and amount of the information, which can be expressed as follows: where k and n are the node and the number of nodes in the waiting queue, is the number of the neighboring nodes fulfilling the condition that the distance between which and node k is greater than the transmission range, shows the time difference between current time and the update time of node k.
Suppose that the current node is node i, node k is one of the nodes in its waiting queue. Among node i's neighbors, the nodes beyond the transmission scope of node k probably hold outdated information about node k. If broadcasting the update message lets these nodes have access to update the position of node k, then this broadcast is deemed as useful. Consider the simple example in figure  1. Current node I has the updated position of node P in the waiting queue. Among its neighbours, node A and B are without the transmission range of node P while node M can communicate with P directly. Thus, the value of is 2. The larger the value of is, the more useful the message becomes. Thus, reflects the effectiveness of the information. In equation (3) timeliness of information, which shows the freshness of the information about node k. A great value of indicates that the information is getting older, the position update message is more prone to be sent. If there are more nodes in the waiting queue, the message is more informative. That is to say, the value of n represents the amount of information. The main goal of the global position update mechanism is to provide a rough position about destination at source node, which may be more or less inaccurate. Furthermore, during the packet transmission, the destination also keeps moving. Actually, as long as the location provided by source node points to the right direction, we consider the mechanism to play a significant role. In addition, the mechanism also makes it possible to update the destination's position in the packet when forwarded. Obviously, the nodes nearer to destination may have more precise information of the destination with high probability. In MAAR, the destination in the data packet would be replaced when the forwarding nodes have more recent information. In this way, the accuracy of the destination's location will increase as the distance from destination decreases.

Mobility-assisted forwarding strategy
Due to the frequent disruption and sparse network density in IC-FANETs, communication interruptions often emerge when the data packets are in transit. The node holding the packet sometimes fails to find an appropriate forwarding node. Under such a situation, adopting the storeforward routing paradigm will make massive data packets discarded, which is inappropriate for IC-FANETs. To this end, MAAR designs a forwarding strategy, which combines the improved greedy forwarding scheme with the store-carry-forward paradigm, to increase the efficiency of data transmission with the help of mobility.
MAAR makes improved greedy forwarding decisions and selects the forwarding nodes among the current node and its neighbours, taking distance and moving direction into account simultaneously. We give preference to those neighbours that are close to destination and move towards destination. The reason for this is that there exist frequent disconnections in IC-FANETs. If we consider the distance between nodes as the only metric and forward the packets to the neighbour which is closet to destination but moves away from destination, once a suitable forwarding node is impossible for it, the data packets will be carried to farther region by the neighbour.
We prioritize current node holding the packet and its neighbours according to distance and direction when choosing next hop. Those nodes close to destination and move roughly towards destination own the highest priority to be chosen as next hop, and the second is current node if its moving orientation directs the region of destination. If there is no nodes that satisfy the above conditions, nodes at closer range from destination will be chosen. Otherwise, current node will carry the data packet itself. In order to better expound the mobility-assisted forwarding strategy, we use figure 2 to explain some notations used in the rest of the discussion. Assume that node I holds the data packet, node N is one of its neighbors. Denote t as the distance between node N and destination node D.
refers to the velocity of node N and Θ is the angle deviation, i.e., the angle between the moving direction of node N and the line segment of ND. All the above data can be obtained or computed using the information in node I's neighbor table easily. When a node has data to forward, we use Algorithm 1 to make forwarding decision.
When current node I has data to transmit, it checks whether there are neighbours close to and move towards destination or not firstly. Θ is a certain threshold, which is the maximum angle that allows the motion to deviate. If exists, the data packet will be forwarded to the node having the shortest estimated time among those nodes. Otherwise, node I computes its own angle deviation. If it is smaller than Θ , node I will carry the packet by itself and the forwarding operation will not be triggered. Making the most of node I's mobility, packet gets close to destination. If not, it indicates nodes meeting the requirements of distance and moving direction simultaneously are unavailable. Next, we only take the distance into consideration to settle for second best. The node closest to destination is chosen as next hop. If fails to find any node close to destination, node I carry the packet until an appropriate forwarder appears.

Simulation environments
Simulation study is conducted on the NS-3 simulator. We evaluate the performance results of MAAR, in comparison to GRAA. UAVs are deployed in a region of size 3000m*3000m. The total number of mobile nodes is in the range of [20,50]. The Random Walk Model without pause time is used to model nodes' mobility. We use two-ray ground model as the radio model and select IEEE 802.11 DCF as the medium access control (MAC) layer protocol. Radio communication range is set to 250m. The MAC layer data rate is set to 2Mbps. We randomly select 10 source-destination pairs in each scenario. The To evaluate the performance of MAAR, the following evaluation metrics are used: • Packet Delivery Ratio: the ratio of the number of data packets delivered to the total number of data packets generated.
• Overhead: the ratio of protocol packets and data packets.
• Average Throughput: the average bytes of data packets of network received in one second.

Simulation results and discussions
To evaluate the impact of parameter IDM, we evaluate MAAR with different values of ITH firstly. Table 1 shows the delivery ratio and overhead under different settings. As the value of IDM increases, the transmission interval of Position Update message increases, and the information in the global position table become older. This incurs less accurate positions provided when forwarded, which results in the performance degradation in terms of packet delivery ratio. On the other hand, the overhead ratio decreases owing to the less-frequent transmission interval. It is a trade-off between delivery ratio and overhead. In the following-up experiments, we set the value of IDM to 200.  Figure 3 studies the performance of MAAR compared with GRAA while varying the mobility of nodes in the network. The maximum moving speed is set in the range of [5,35] m/s and the number of nodes is 30. Figure 3(a) shows that, MAAR outperforms GRAA in delivery ratio under same mobility, increasing by 15%-51%. Note that for both protocols, packet delivery ratio accordingly decreases with the increase of moving speed in the definite velocity range. This is because when the network is sparse and intermittent, the high nodal mobility leads to less opportunities that both forwarder and receiver in their communication range while they have each other's location information. Therefore, when the maximum speed exceeds some extent, which is 20m/s for both MAAR and GRAA in this experiment, the performance degrades faster. In figure 3(b), we observe that the overhead of both MAAR and GRAA decrease with the increase of nodal velocity. The reason is the same as why packet delivery ratio decreases in high nodal velocity. It is notable that the overhead of MAAR is always much lower than GRAA. Because MAAR adopt the adaptive beacon update strategy, which decrease the number of beacon packets significantly when the location of nodes changes slowly. Figure 3(c) shows the average throughput of whole networks in one second. The simulation result is similar to packet delivery ratio.
In figure 4, we vary the number of nodes from 20-50 with maximum moving speed fixed at 20m/s. Owing to the use of store-carry-forward mechanism, MAAR holds the packet delivery ratio at high level, regardless of the number of nodes. While the performance of GRAA increases slowly and reach top in 40 nodes, and rapidly degrade with larger number of nodes. The reason is that, as the number of nodes increase, the protocol packets for neighbour information update increase simultaneously, which occupy the wireless channel and influent the transmission of data packets. However, MAAR adopt the adaptive beacon update strategy, which dramatically degrade overhead and consequently improve the performance of packet delivery ratio.

Conclusion
IC-FANETs suffer from recurrent disconnections due to the high degree of nodes' mobility and low node density. In this paper, we present the mobility-assisted adaptive routing(MAAR) for IC-FANETs, which combines routing strategy and location service. Different self-adaptive strategies are used to update the information of neighbor nodes and other nodes of the network respectively. Besides, we use the combination of the improved greedy forwarding method and store-carry-forward paradigm to make effective forwarding decisions. The simulation results show that MAAR can efficiently adapt to the networks with disruptive connectivity and perform better than GRAA.