Routing Protocol for Heterogeneous FANETs with Mobility Prediction

Qihui Wu,Min Zhang,*,Chao Dong,*,Yong Feng,Yanli Yuan,Simeng Feng,Tony Q.S.Quek

1 The Key Laboratory of Dynamic Cognitive System of Electromagnetic Spectrum Space,Ministry of Industry and Information Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

2 The Shell Eastern Petroleum Pte.Ltd.,Singapore 903808,Singapore

3 The Dept.of Information Systems Technology and Design,Singapore University of Technology and Design,Singapore 487372,Singapore

Abstract: In recent years, with the growth in Unmanned Aerial Vehicles (UAVs), UAV-based systems have become popular in both military and civil applications.In these scenarios, the lack of reliable communication infrastructure has motivated UAVs to establish a network as flying nodes, also known as Flying Ad Hoc Networks (FANETs).However, in FANETs, the high mobility degree of flying and terrestrial users may be responsible for constant changes in the network topology, making end-to-end connections in FANETs challenging.Mobility estimation and prediction of UAVs can address the challenge mentioned above since it can provide better routing planning and improve overall FANET performance in terms of continuous service availability.We thus develop a Software Defined Network (SDN)-based heterogeneous architecture for reliable communication in FANETs.In this architecture, we apply an Extended Kalman Filter (EKF) for accurate mobility estimation and prediction of UAVs.In particular,we formulate the routing problem in SDN-based Heterogeneous FANETs as a graph decision problem.As the problem is NP-hard, we further propose a Directional Particle Swarming Optimization (DPSO)approach to solve it.The extensive simulation results demonstrate that the proposed DPSO routing can exhibit superior performance in improving the goodput,packet delivery ratio,and delay.

Keywords: routing; unmanned aerial vehicles(UAVs); flying ad hoc networks (FANETs); mobility prediction;particle swarming optimization(PSO)

I.INTRODUCTION

Recently, unmanned aerial vehicle(UAV)technology attracted significant popularity in both military and civilian domains for various applications and services,such as aerial photograph[1],5G communication[2],agriculture and forest fire monitoring [3], search and rescue[4].In these applications,reliable and fast wireless communication among UAVs through the network is critical, which motivates the collaborative applications of Unmanned Aerial Vehicles(UAVs),so-called Flying Ad Hoc Network(FANETs)[5,6].Coordination and collaboration of FANETs can create a system that is beyond the capability of only one UAV in terms of cost,scalability,survivability and speed-up[7-9].

Nevertheless, FANETs have several challenging issues distinguishing them from other mobile ad hoc networks (MANETs).According to [10], a UAV has a speed of 30-460 km/h,and this situation results in several challenging communication design problems[11].On the one hand, the high mobility characteristic of UAVs leads to intermittent connectivity among the UAVs or between the UAVs and cluster heads,and communication links in a FANET may have frequent outages when exchanging information.On the other hand, the routing path may not be applicable in the next moment because of the highly dynamic network topology, and FANETs need fast and timely routing protocol.However, the conventional routing protocol can no longer meet the needs of the routing discovery, maintaining, and decision [12] [13].First, for topology-based routing protocols, it may be tremendously hard to maintain and update routing path or table timely owing to FANETs with numerous nodes, complex connections, and dynamic topology[12][1][14].Second, a geographic protocol may fail in data routing because one UAV cannot percept the real-time position of each UAV,whether by the satellite or cluster heads.[15-17].Finally, most channelbased routing cannot timely estimate channel information and cannot furtherly make timely routing decisions[18,19].

To this end,a Software Defined Network(SDN)has emerged as a solution to control the networks with low communication cost[20,21].SDN is a paradigm in networking and computing, which separates the data communication and control planes to simplify the network management and expedite system evolution[22].Therefore, SDN-based homogeneous FANET can provide lots of advantages for the management of mobility in FANETs scenario.First of all, homogeneous structure FANETs suffer from numerous problems such as difficulty to manage, easy to lose,poor coordination, and weak end-to-end communication.Then,with the development of UAV technology and the reduction of manufacturing costs,SDN-based heterogeneous FANETs have now come within reach but have been an essentially under-explored domain.Finally,such SDN-based heterogeneous FANETs can help against isomorphic FANETs’ huge routing table,inefficient path discovery,excessively many hops,lengthy path,etc[23].In addition,the SDN controller can make the optimal routing decision based on the global information, which is not easy to achieve.Besides,highly dynamic mobility is the main reason for causing intermittent and episodic connections, which would bring unique challenges such as frequently routing failure[24].Thus routing protocols can not ignore the mobility of UAVs, and before designing the routing protocols, UAVs’ mobility needs to be evaluated first.However,mobility prediction,which is used for fast and timely routing decisions,is challenging to obtain due to fast-moving UAVs and dynamic topology.

In this paper, a centralized routing scheme with mobility estimation and prediction is proposed for FANETs assisted by Swarm Intelligence(SI)powered Software Defined Network (SDN) controller.Specifically, the SDN controller can perform accurate mobility estimation and prediction through an advanced optimal estimation technique.Then, based on the mobility estimation and prediction, the transmission Routing Estimated Cost(REC)of each UAV’s request under frequent network topology changes can be estimated by the Cluster Head UAVs (CHUs) or Centralized Controller(CC).Based on the global network information, the SDN controller or CHUs compute optimal routing paths for CHUs.While the source UAV and destination UAV are located in the coverage area of the same CHU, further routing decisions will be made by the CHUs independently to minimize the overall REC.Simulation results demonstrate that our proposed centralized routing scheme outperforms others regarding goodput, delay, and packet delivery ratio.The main contributions of this paper are listed as follows.

• We develop an effective SDN-based heterogeneous FANETs architecture to carry the exchange of information and propose a DPSO routing scheme using Extended Kalman Filter(EKF)plus Particle Swarm Optimization to overcome the dynamic mobility and untimely decisions, and ultimately improve the Quality of Service for heterogenous FANETs.

• DPSO routing protocol uses the Extended Kalman Filter (EKF) to estimate and predict the UAV position,reaping the powerful real-time capability of EKF.Based on the accurate position,the Centralized Center(CC)or Cluster Head UAV(CHU)can do the link evaluation by building the Routing Estimated Cost(REC)function.

• We formulate the SDN-based heterogeneous FANETs routing problem aiming to minimize overall REC into a graph decision problem NPhard.We solve the NP-hard routing problem by performing the Directional Particle Swarm Optimization algorithm and designing a routing timeout timer mechanism to improve network performance.Meanwhile, we take the serving capability of CC/CHUs into consideration.

• We evaluate the various performance of DPSO routing protocol through simulations.The results show that the DPSO routing protocol can improve the Packet Delivery Ratio (PDR), goodput, and delay performance of FANETs significantly,compared with the other protocols,including GPMOR and AFP.

The rest of this paper is organized as follows: Section II introduces the related works in terms of routing protocol for FANETs.Section III is the system model.Section IV indroduces the mobility estimation and prediction and formulates the routing problem.In Section V, the proposed DPSO routing protocol is introduced in detail, including mobility estimation and prediction,problem formulation,routing decision method, and routing scheme.Section VI presents the simulation and performance evaluation.Section VII is the conclusion of the paper.Beside, Table 1 lists several main abbreviations.

Table 1. A list of abbreviations.

II.RELATED WORKS

Over the past years, with the development of UAVs,several routing protocols have been proposed for FANETs[5,25].From a decision point of view,most protocols can make a routing decision based on topology,mobility,channel,etc[26,27].

2.1 Topology-based Routing Protocols

Topology-based routing protocol uses the current node information and connection to transfer packets within the network[26,27].They includes static routing protocols[28,29],proactive routing protocols[30],reactive routing protocols [31] and hybrid routing protocols[29].However,the old-fashioned topology-based routing protocol cannot follow the dynamic topology of FANETs, because UAVs’ mobility and topology change are both tremendously fast[28].

2.2 Position-based Routing Protocols

Position-based routing protocols are based on the knowledge of geographical positions,where GPS can define nodes [26, 32].For example, GMPR routing protocol [33] can predict the location of Neighbouring UAVs (NUs) and considers the connection qual-ity of neighbor UAVs and the shortest distance from the destination node to route packets.However, its link quality only considers the link’s duration, and the position prediction is two-dimensional.DTN/georouting [34] combines forwarding routing and carrying routing,transmits packets to the Base Station(BS)along the shortest path.Otherwise, UAVs will physically carry it to the BS for transmission.However,the source UAVs need to maintain a big routing table,which can cause delays in the fast-moving UAVs scenario.Consequently, the routing fails.Location-Aided Delay Tolerant Routing (LADTR) [35] protocol can be used in post-disaster operations, which exploits location-aided forwarding combined with a store-carry-forward (SCF) technique.However, the acquisition of location information about all UAVs is challenging to implement.Furthermore, the singlefunction ferry UAVs lack adaptability and result in more UAVs overhead,especially on the battlefield.

2.3 Channel-based Routing Protocols

Channel-based routing protocols are based on the knowledge of channel information [26, 36].For example, Cognitive Heterogeneous Routing (CHR)[36] select the appropriate transmission technology based on channel parameters from each network.Cellular/multi-hop Wi-Fi architecture[19]relays data packets for clients that suffer from low channel quality or to offload a congested cell by forwarding the traffic from this cell to other non-congested cells.ACO Look-Ahead Approach[37]measures various QoS parameters, but without mobility, characteristics to calculate path preference probability.

In conclusion,although numerous works have been done towards FANETs routing protocol, these works cannot meet the routing need of dynamic and high mobility FANETs well.How to make appropriate routing decisions and resolve the routing failure issues need to be studied further.

III.SYSTEM MODEL

In this paper,we present the network model of a twolayer joint UAVs network, upper UAVs layer, and lower UAVs layer for FANETs, as shown in Figure 1.We consider SDN-based heterogeneous FANETs,with the upper UAVs layer comprised of Cluster Head UAVs (CHUs) and the lower UAVs layer comprised of Cluster Member UAVs (CMUs).At the top of Figure 1, the Swarming Intelligence (SI) empowered Centralized Controller (CC) is deployed to control all the UAVs, estimate and predict mobility, and run routing decisions, especially routing between CHUs.But routing within UAVs cluster is decided by corresponding CHUs, also with the SI empowered controller.Besides, CHUs can also control their corresponding CMUs, estimate and predict their corresponding CMUs mobility, and run routing decisions for their corresponding CMUs.In practice,CHUs are generally larger and higher, while CMUs are generally smaller and lower[27].High-performance CHUs can run mobility estimation and prediction operations and make routing decisions, and low-cost CMUs can search or provide service for ground or air[38].Thus,our two-layer joint UAVs architecture can take advantage of all the UAVs and save UAVs manufacture cost.

Figure 1. The UAVs is grouped into 2 layers, upper UAVs layer and lower UAVs layer.Centralized controller (CC)controls all the UAVs but CHU controls only its CMUs.

Figure 2. Illustration of FZ.

We consider CMUs can move freely,and each UAV can obtain its position with noise by equipping with Global Navigation Satellite Systems (GNSS), e.g.,Global Position System (GPS) or Beidou Navigation System (BNS).Following the practical UAVs flight progress,the trajectory of UAV flight is assumed to be smooth, and there are no sharp turns or U-turns [39].Since our main scope is packet routing,we assume theUAV’s flight is mission-driven and not routing-driven,UAVs can always access CHUs,and the coverage area of CHUs does not overlap [40].Since energy consumed by routing control is far smaller than that consumed by flight,for better illustration,we leave energy consumed by routing control out of consideration[13].Additionally,Table 2 shows major notations.

Table 2. A list of major notations.

3.1 MAC Model

Following a widely used architecture[22],both IEEE 802.11p and LTE interfaces are adopted in our system.The hybrid system can effectively balance the low-cost of IEEE 802.11p and wide-range of LTE cellular[41],and details are as follows.

1.CMU to CMU (M2M) communicates by IEEE 802.11p with EDCF standard, where a 75 MHz band is allocated with seven channels, each with 10 MHz bandwidth[22].

2.CHU to CMU (H2M) communicates by LTE,where multiple UAVs can share the spectrum resources by Orthogonal Frequency Division Multiple Access(OFDMA)[22].

3.CHU to CHU (H2H) communicates by IEEE 802.11p with the dedicated channel, where can carry high-qualified communications[42].

Swarming Intelligence(SI)empowered Centralized Controller(CC),which can communicate with CHUs directly and with CMUs by their CHU, is generally deployed in the Base Station(BS),satellite,giant airplane,etc.[43].We denote MHM as cross-CHU communication, which means packets will be delivered one by one in the following ways: M2H, H2H, and M2H.Remarkably,the proposed network architecture can also apply to the other MANETs composed of vehicles,underwater sensors,smartphones and so forth.We may also replace the mobility prediction and decision methods with the varying mobile object and mission targets to fit those variations.

3.2 Mobility Model

We assume the location of UAViat timetbe represented as(xi,t,yi,t,zi,t)and given by

where (xi,t,yi,t,zi,t) represents location of UAViat timet.represents the speed of UAViat timet-1.θi,t-1andφi,t-1represent the horizontal direction and pitch angle of UAViat timet-1,respectively.θi,tandφi,trepresent the horizontal direction and pitch angle of UAViat timet,respectively.In practice,these parameters are invariably determined by their missions or control commands.Therefore, the Euclidean distance between UAVcand its neighbor UAVican be represented as Eq.(4).

3.3 Channel Model

We definePMas the transmission power of the CMU,PHas the transmission power of CHU,Wuas the bandwidth allocated for uplink M2H,Wdas the bandwidth allocated for downlink M2H,WMas the bandwidth allocated for M2M.N0is the power of additive white Gaussian noise (AWGN), andδis the lognormal shadowing component, with a mean of 0 dB and standard deviationδS[22].duis the uplink distances from the source CMUMto CHUH,ddis the download distance from CHUHto the destination CMUM,dkis the distance between CMUs.λis the path fading exponent,which is typically chosen within[2,4].|h|u,H,|h|H,dand|h|kare the Rayleighdistributed fading magnitude with=1.Thus the upload transmission rateand the download transmission ratefor M2H are described by

Likewise, the transmission rate of per hop M2M communication is presented by

In Eq.(5)～Eq.(7),we assume CHUs and CMUs share the samePHandPM,respectively,because the energy consumed by routing control is far smaller than that consumed by flight.Moreover,bandwidth can be allocated by our MAC architecture, and we assume all the UAVs are in the same electromagnetic environment as they usually fly in the same air space.Therefore,transmission rateRand distancedin Eq.(4)are strong correlative [22].Also, in practice, great distance error may occur as severe noise.Thus mobility estimation and prediction are both significant for high mobility UAV routing.

IV.MOBILITY ESTIMATION AND PREDICTION AND PROBLEM FORMULATION

In this section,we first apply Extended Kalman Filter to the mobility estimation and prediction process of CMUs,then formulate the routing problem as a graph decision problem.

4.1 Extended Kalman Filter Based Mobility Estimation and Prediction

Currently, since three-axis accelerometers and gyroscopes are mostly low-cost, low-weight, and highperformance in positioning, more and more UAVs are equipped with them besides GNSS.However,noise and imprecise positioning,especially in dynamic FANETs, will cause various routing difficulties [44].Also, with LTE communication, CHU’s communication range can reach up to 5 km (3.1 miles) with the optimal cell size[45].Hence each CMU can transmit mobility measurement to their service CHU for mobility estimation and prediction.Furthermore, based on mobility and topology,M2M routing decisions can also be made by CHU.

If the UAVs are in thexyz3-D coordinates, we define UAVs as particles[46],and the dynamic mobility model withnxstates andnymeasurements taken at time slotkcan be written as

and

where

where

Eq.(11)is the current UAV’s position state estimation,and Eq.(12)is the one-step prediction of UAV’s position state.Besides,Kkrepresents gain matrix,Pkrepresents error variance matrix,Qkis the covariance of the process noise,Rkrepresents the covariance of the observation noise,more detailed description can be found in[46].With this prediction procedure,we can obtain UAV’s mobility estimation xk|kand prediction xk+1|k.

4.2 Problem Formulation

Base on the above, we can formulate the networks as graphG(V,E), whereVdenotes UAVs set andEdenotes connection set [48][22].Considering our MAC model,we category routing path inG(V,E)into M2M, M2H, and MHM routing.Thereinto, MHM is an integration of M2H and H2H,and M2H routing is a complement to M2M routing and is only used when M2M channel resources are occupied.As cross-CHU communication, MHM works in the following steps:M2H,H2H,and M2H.For H2H,the transmission rate or delay of H2H routing are generally fixed and highly qualified because they share the high-priority channel and can communicate with Centralized Controller(CC) directly [22].Hence, according to their characteristics, only the path whose hops are minimum is considered in the H2H decision-making process[22].

InG(V,E),we present the Routing Estimated Cost(REC) for each connectionvto jointly make routing decisions considering velocity and position.With xk|kand xk+1|k,CHU can obtain each CMU’s mobility estimation and prediction,respectively.Indeed,mobility state x consisting of position and velocity make it possible to estimate and predict transmission rate by Eq.(5) ～Eq.(7) for upload M2H, download M2H and M2M,respectively.In general,there are many considered costs while evaluating any routing protocol, including delay,flow,distance,etc[49].However,UAVs route better in low-velocity value deference and high transmission rate links in FANETs.To better reflect them,we write M2M’s RECcijof one connection as

where

• andξMandψMdenotes the factors to balance transmission rate and velocity, respectively.And the factors can be set according to the practical mission scenario.

With the RECcijof a single hopij,the overall REC of a multi-hop path of M2M from sourcesto destinationdis given by

whereci-1,irepresents the REC from CMUi-1 to CMUi,nmhopsrepresents the number of hops.Since high velocity and low transmission rate will both causes routing failure,UAVs need to route by a low velocity and high transmission path.A REC in one hop is betweenψandξ, whereψrepresents a bad routing path andξrepresents a good routing path in Eq.(16).Likewise, the uploadcsHand M2H downloadcHdREC are written as

and

wheredenotes the maximum transmission rate for ideal M2H channel,andrepresents the maximum velocity value of CHU.

Considering H2H communication with dedicated channel generally performs high-qualified service,we can write the overall path REC from sourcesto destinationdat time slottas

However, there may exist several paths fromstod,especially between CMUs.We let P represents the set of all optional paths, and the objective of routing decision is to find the pathp∗∈P whose REC is the lowest fromstodat time slott[50],written as

wheredijanddmdenotes the distance between CMUiandj,and the communication range of CMU,respectively.midenotes forwarding CMUs.And F denotes forwarding CMUs set within Forwarding Zone (FZ)determined by union region of Transmission Zone(TZ) and Reception Zone (RZ) illustrating in Figure 2, in whichsdenotes source CMU anddmeans destination CMU.We assume the communication range plane perpendicular to the line segmentSDis a circle, then the conical space formed by the circle and pointDis called a TZ.Likewise,we can draw an RZ.In Figure 2, dark-colored UAVs located in the FZ are considered to relay a packet, but light-colored UAVs not located in FZ are not considered for forwarding a packet.We develop the FZ to constrain the routing path not to extend too much and ensure connectivity.Although some works propose different FZ schemes[51],they cannot constrain FZ or alter FZ size in relationship to communication range or mission scenario adaptively.When the UAVs density changes or the mission scenario transforms, CMU or CC can adaptively adjust the Forwarding Angle (FA), that is, the TZ (∠EDFin Figure 2) and RZ (∠GSHin Figure 2).

V.DPSO ROUTING SCHEME

Apparently, routing problem in graphG(V,E) is Non-deterministic Polynomial-time hardness (NPhard)problem[52,53,48].Since H2M routing is usually fixed paths and MHM routing is high-qualified,we mainly focus on M2M routing.Owing to the fact that Particle Swarm Optimization (PSO) is a population-based optimization technique and applied in the design of many engineering real-time problems[54], for M2M routing, we propose Directional Particle Swarm Optimization(DPSO)algorithm to solve the NP-hard problem and propose DPSO routing protocol.

Algorithm 1. Particles generation algorithm.Require: Source CMU s,destination CMU d,all the CMUs in one cluster;Ensure: Initial path;1: Set the Current UAV(CU):CU =s;2: Put CU to the set V;3: Create the queue Q[m1,m2,···mnd], nd =length(Q),and set m1 =CU;4: Create final CMU M, which is the prior neighbouring CMU of CU;5: Construct potential F;6: if CU =d then 7: Remove the duplicate CMUs in sequence Q,get p=Q;8: else 9: if M ∩FV ̸=Φ then 10: Randomly select a CMU in M ∩FV;11: Put the CMU in set V and queue Q;12: else 13: while M ∩FV=Φ do 14: Up back to the last CU along the Q;15: end while 16: end if 17: end if

5.1 Generation of Particles

We first model each particle as a feasible path[m1,m2,···mnd], wheremi(i= 1,2,···nd) denotes each CMUs,m1denotes source CMU,mnddenotes destination CMU andndrepresents the path length.To fast generate a single particle, we set potential FZ illustrated in Figure 2 as F, path queue asQ[m1,m2,···mnd],the detailed operation is as illustrated in Algorithm 1.

5.2 Update of Particles

The movement process of a particle is considered as an update process of routing path,and the fitness function is considered as REC function as shown in Eq.(20)[48].For better path update, we import⊕operator,which is the extension of addition.For example, if there exists common CMUiand CMUi+ηbetween pathPAand pathPB, thenPA ⊕PBoperation is as follow:firstly,randomly interceptηlength ofPBfrom CMUito CMUi+ηto construct sub-pathPB-sub,then perform the same operation forPAto construct sub-pathPA-sub, then compare fitness function value forPA-subandPB-sub, insert the larger one toPA.Moreover,the update operation can be written by

whereLi(t)represents the history best solution,G(t)represent the global best solution,c1andc2are positive constants called acceleration coefficients[55].

5.3 Implementation of Routing

The routing decision operation is summarized in Algorithm 2.If SI empowered CHU receives a routing request and determines the source UAV, CHU would generate initial particles by Algorithm 1.Then if the initial particles do not satisfy the termination conditions, CHU will continue to calculate each particle’s fitness function value, determine neighbor optimal particlesG(t)and history optimalP(t),and update each particle by Eq.(22).

For H2H routing, the SI empowered CC can similarly make the fast shortest-path decision based on the simplified DPSO algorithm.That is to say, CC evaluates each path by the fitness function of hops due to each hop’s communication is generally high-qualified.CC can generate,calculate and update particles similar to M2M routing.

To make DPSO routing clear, Figure 3 shows the routing work flow chart for typical M2M.The EKFbased mobility estimation and prediction module provide essential support for generating particles, calculating fitness value, and updating each particle.The forwarding zone provides path constraining for the generating and updating process.Thus, if we set termination conditions,like REC for each hop is less than 1.5,the optimal routing can be generated when the fitness value satisfies termination conditions.

Figure 3. Work flow of DPSO protocol(taking M2M as an example).

VI.PERFORMANCE EVALUATION

This section introduces the simulation setting and then presents a performance comparison of DPSO, GPMOR, and AFP with the impacts of the number of UAVs and velocity.

Algorithm 2. DPSO routing decision algorithm.Require: CMUs set,routing request;Ensure: Optimal path;1: Start routing if receive routing request;2: Generate initial particles by Algorithm 1;3: while Termination conditions are not satisfied do 4: Calculate each particle’s fitness function value;5: Determine global optimal particles G(t) and history optimal l(t);6: Update each particles by Eq.(22);7: end while 8: Calculate and output the global optimum, which is the optimal path;

6.1 Simulation Setting

The simulation model is built based on the system architecture described in Section III.A wide range of CMUs speeds is simulated to evaluate the system performance under different scenarios[56].The communication characteristics are simulated based on DSRCfor M2M communication and LTE for M2H communications [22].The scheduling period is the same as the maximum waiting time.Each UAV can submit a request to the SDN controller at any time.The total number of submitted requests varies from 10% to 90% out of the total number of CMUs in each cluster.We setup FANET which consists of 10～200 UAVs,with 1～to 20 CHUs[57].All CMUs are at the same packet arrival rate, buffer size, transmitting and receiving power,path fading exponent,and Rayleigh-Distributed fading Point, respectively.In this simulation, the packet arrival model of UAV is the Poisson packet arrival model, and the movement model is the Gauss-Markov model.All CMUs can connect to a CHU, all CHUs can communicate directly with the CC,and all CMUs can communicate with the CC through the CHU.Considering CMU’s MAC architecture and transmission power, we set the communication range to 300 meters.The main simulation parameters are summarized in Table 3.Besides,we leverage the following three metrics to evaluate these routing protocols.

Table 3. Simulation Parameters.

•PDR: Packet Delivery Ratio (PDR) refers to the ratio of data packets that were delivered to the destination to the data packets that were generated by the Source UAV(SU).The packet delivery ratio analysis is mathematically evaluated by

whereρallrepresents the number of all the packets,andρlossdenotes the number of packet loss.

•Delay: in this paper,the delay is defined as

whererepresents thei-th packet delay caused by M2M routing,andrepresents thej-th packet delay caused by M2H routing.Besides,mrepresents the number of M2M packets,andnrepresents the number of M2H packets.Note that only the packets that have successfully transmitted are analyzed statistically for the average delay, and the packets that failed to transmit are not analyzed.

•Goodput: goodput is defined as the applicationlevel throughput,i.e.the number of useful bits per unit of time forwarded by the network from a particular UAV to a destination, excluding protocol overhead and excluding retransmitted data packets.In our simulation,goodput is given by

whereρalldenotes all the packets,ρprtdenotes the control and protocol packets,ρrtsdenotes the retransmission packets,ρiallrepresents thei-th common packets,ρiprtrepresents thei-th control and protocol packets,ρirtsrepresents thei-th retransmission packets andTrepresents the observation duration time.

Before the performance comparison,we first evaluated the accuracy of the EKF-based positioning within the proposed DPSO protocol.As shown in Figure 4,the position error in the DPSO protocol is no exceeding 0.8m,and the error in the initial stage is also not beyond this range.On the contrary, the GPS position error is usually around 4.9m[58].Thus, it can be seen that our EKF-based mobile positioning error is evidently reduced compared with the original GPS data,which provides a solid foundation for subsequent particles generation,calculation,update,etc.

Figure 4. Positioning error(in units of meters)of EKF estimation in DPSO protocol.

We vary the number of UAVs and the average speed to see how our approach performs.Different routing protocols are investigated and run on the same simulation environment with our proposed protocol, and we compare the DPSO routing protocol with the other three protocol schemes as follows.

• Geographic Position Mobility Oriented Routing(GPMOR) [33] uses the Gauss-Markov mobility model to predict the movement of UAVs to eliminate the impact of highly dynamic movement.Then it selects the next hop according to the mobility relationship and Euclidean distance to make more accurate decisions.

• Adaptive Forwarding Protocol (AFP) [59] applies an adaptive forwarding scheme based on forwarding probability and forwarding zone criterion.The forwarding probability is calculated adaptively to reduce the redundant rebroadcast.

6.2 Impact of Number of UAVs

First, the average velocity of UAVs is set to 60 km/h.As the number of UAVs increases from 10 to 200,the Packet Arrival Rate (PDR) trends of three protocols are shown in Figure 5.The maximum PDR will be improved by 61.32%at most,with the proposed protocols marked as DPSO because of fast routing decisions and accurate mobility estimation and prediction.To be specific,the mobility prediction of GPMOR is inferior to our EKF with the increasing number of UAVs,and GPMOR’s mobility prediction is not real-time.Plus,routing decisions according to only mobility information will cause inappropriate routing decisions.Besides,routing decisions made by only forwarding zone in AFP will also cause inappropriate routing decisions.The PDRs of all three protocols reduce with the number of UAV increasing from 10 to 200 because the path hops become more with the increasing number of UAVs.

Figure 5. PDR comparison under different number of UAVs.

Figure 6 illustrates that the DPSO protocol will reduce 52.38%at most of the average delay,which suggests that the proposed protocol will also be able to reduce the average delay of all UAVs.Compared with the results of GPMOR and AFP, our proposed protocols perform better in routing decision problems.

Figure 6. Delay (in units of seconds) comparison under different number of UAVs.

Figure 7 reveals goodput trends of all UAVs.As illustrated in this figure, the curves of the three protocols increased significantly with the increase of the number of UAVs, among which the proposed DPSO

Figure 7. Goodput (in units of Mbit/s) comparison under different number of UAVs.

consistently outperformed the other two.When the number of UAVs is relatively small, the gap between the three curves is relatively small;however,when the number of UAVs is relatively large, the gap is rather large.Figure 7 proves the more stable performance of DPSO than the pure mobility-prediction based routing and forwarding zone based routing,and DPSO can improve goodput at most 128.56% comparing with the worst-performing protocol.

6.3 Impact of Velocity

Then,we set the UAVs to 50 and vary the average velocity of UAVs to see how the average velocity affects these protocols’performance.As the number of UAV groups increases from 20 to 200 km/h, it is shown in Figure 8 that the PDR has a trend to decrease and in Figure 8 that DPSO outperforms AFP and GPMOR obviously.Whenv, the average velocity of UAVs, is under 50 km/h,the PDR of all protocols drops highly,and their gap is relatively big with the increase ofv.But whenvreaches 150 km/h, the three curves drop slowly, and their gaps are tremendously near.As the average velocity increases,the connections between UAVs become fragile, and the network topology changes rapidly,resulting in a decline in PDR performance.Besides, DPSO can improve PDR at most 36.24% comparing with the worst-performing protocol.However,the DPSO performance relatively overcame the negative impact of the velocity increase due to two other reasons: high-performance mobility estimation and prediction and fast routing decisions.

Figure 8.PDR comparison under different velocity(in units of km/h).

Figure 9 reveals the delay trends of the three protocols.As illustrated in this figure,the three curves obviously increase with the increasing average velocity due to intermittent connection for high velocity.Besides, DPSO can improve delay performance at most 152.94%comparing with the worst-performing protocol.DPSO outperforms the other two protocols significantly because its EFF-based module can estimate and predict the velocity of UAVs, and the routing decision module can make a fast routing decision.

Figure 9. Delay (in units of seconds) comparison under different velocity(in units of km/h).

Figure 10 illustrates that the goodput has a trend to decrease.Whenvis small, the three curves decline faster, while whenvreaches around 125 km/h,the goodput of the three curves is relatively stable and close to 0.Besides, DPSO can improve goodput at most 53.28% comparing with the worst-performing protocol.The reasons for these changes are strongly related to the changes of PDR and delay.

Figure 10. Goodput(in units of Mbit/s)comparison under different velocity(in units of km/h).

6.4 Angle Setting

In DPSO,changing Forwarding Angle(FA)(see Section 4.2)notably affects the routing path’s success rate;namely, an over-large FA will lead to an over-long path.By contrast, an over-small FA results in almost none forwarding UAV.In this simulation,we vary the FA from 0 toπto observe Packet Loss Rate (PLR)and goodput trends.µis the ratio of the number of particles to the total number of possible particles in initialization.For example,µ= 10% means that the initial particles will take up 10% of the total number of particles.As shown in Figure 11,when FA does not reachπ/2,PLR(µ=10%)and PLR(µ=20%)drop dramatically, while goodput (µ= 10%) and goodput(µ= 20%)increase evidently.The grounds included the following, too small FA makes it challenging to have a suitable forwarding UAV,while a slightly larger FA can cover more forwarding UAVs.However,when FA approachedπ,PLR gradually increased,and goodput gradually decreased for the reason of overlong and overextended path.Therefore, we are not supposed to setµto a middle one for high reliability.In practice, we should chooseµappropriately according to the density of UAVs.At last, in our simulation settings, the appropriate FA that can perform well is approximatelyπ/2.

Figure 11. PDR and goodput (in units of Mbit/s) performance under different angle.

VII.CONCLUSIONS

This paper has proposed a routing protocol for UAVs that perform routing decisions on SDN-based heterogenous FANETs.The proposed routing scheme has the estimation and prediction capability of mobility and selects the optimal routing path based on the global information.The proposed routing scheme can combine M2M, M2H, H2H, and MHM communication to adapt to the dynamic changing network topology.Simulation results have demonstrated that DPSO routing exhibits outstanding performance improvements on Goodput,packet delivery ratio,and delay,compared to other routing protocols in FANETs.