{'fraction_non_alphanumeric': 0.03781879194630872, 'fraction_numerical': 0.01238255033557047, 'mean_word_length': 4.450073152889539, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Resilient UAV Traffic Congestion Control using Fluid Queuing Models

In this paper, we address the issue of congestion in future Unmanned Aerial Vehicle (UAVs) traffic system in uncertain weather. We treat the traffic of UAVs as fluid queues, and introduce models for traffic dynamics at three basic traffic components: single link, tandem link, and merge link. The impact of weather uncertainty is captured as fluctuation of the saturation rate of fluid queue discharge (capacity). The uncertainty is assumed to follow a continuous-time Markov process. We define the resilience of the UAV traffic system as the long-run stability of the traffic queues and the optimal throughput strategy under uncertainties. We derive the necessary and sufficient conditions for the stabilities of the traffic queues in the three basic traffic components. Both conditions can be easily verified in practiceB. The optimal throughput can be calculated via the stability conditions. Our results offer strong insight and tool for designing flows in the UAV traffic system that is resilient against weather uncertainty.


Introduction
Unmanned Aerial Vehicles (UAVs) are undergoing a vast development in recent years. By January 2018, over one million UAVs had been registered [1]. Commercial UAVs, for both commodity and passenger transport, are being developed and tested. Amazon has issued its patent on UAV package delivery service [2]. Uber has initiated a project on urban aerial taxi [3]. With the increasing number of UAVs applied to various tasks in urban areas, there is an urgency to integrate the UAVs into current traffic systems [4,5]. Current transportation researches have been focused on UAVs assisted traffic [6][7][8], to name a few. However, UAVs themselves can form traffic in the urban airspace, and congestion can happen when the inflow exceed the capacity in the airway. UAVs, by nature, are more sensitive to weather changes. Congestion control under weather uncertainty make the UAV traffic management more challenging than other traffic.
In this paper, the problem of resilient congestion control of future UAV traffic system in urban airspace under weather uncertainty is considered. The goal of this paper is to develop a system-theoretic framework for modeling, analyzing and designing of a resilient congestion control strategy for future UAV traffic system. The main tasks of this paper are: (1) developing realistic and tractable models for UAV traffic flow, (2) analyzing the system level performance of UAV traffic in the merits of resilience. The modeling is split into three parts of work: model the UAV traffic at macro scope(system-level) for single link, integrate the single link model into traffic networks, model the weather uncertainty and its impact on the UAV traffic. For analyzing, we introduce the definition of resilience for UAV traffic, and we derive the necessary and sufficient conditions for the UAV traffic in each traffic link model to satisfy the definition.
We adopt one class of traditional system-level model for air traffic dynamics that has been used in air transportation community, that is, the stochastic queuing model to capture the traffic dynamics in the airway. In a single queue model, each UAV is considered as a 'customer', the airway (link) the UAVs travel and stay in is consider as 'buffer', and finally the UAVs departure from a link at the end of the link called 'server'. The number of UAVs leaving a queue at any time instance is upper bounded by the saturation discharge rate (capacity) of the link. The level of congestion is characterized as the queue length. In particular, we will be using the fluid queuing model. We do realize that other queuing models(e.g., M/M/1, D/E/1) [9] are used in air traffic management [10], the major part of these models focus on modeling the arrival of individual customer [11,12]. Our focus is the system-level behavior of the traffic, which is the evolution of aggregated flow. Thus, fluid queuing model better fits our purpose. The stochastic differential form of the fluid queue dynamics also offers tractability in analysis.
To extend the result from single link/queue to general queuing network, we pay our attention to modeling traffic dynamics in two additional link models: tandem link, and merge link. Tandem link, merge link, and split link are three basic link models in traffic networks. Any possible network is combinations of these three link models [13]. For the split link, routing policy or different destinations need to be considered, which is outside the scope of the paper. In the single link or tandem link, no control action need to be taken under the default setting. In the merge link model, we considered proportional capacity allocation control policy. Based on our models, we derive necessary and sufficient conditions for stability under constant inflow. Apart from the existing results on fluid queuing models [14,15], we considered state dependent discharge rate when modeling the traffic dynamics in tandem link and merge link. This is motivated by the observation that the amount of traffic in the upstream link discharged into downstream link can be affected by the existing amount of traffic already in the links. The rule describing this observation is sometimes referred as fundamental diagram of traffic flow [16].
Properly modeling the weather uncertainty and the impact of weather uncertainty is crucial to decision making in UAV traffic management. High resolution ensemble model based weather are utilized in predicting the weather for strategic planning in aviation systems [17]. However, such model is infeasible for our purpose for three reasons. First, we are considering UAV traffic in the urban area, where weather measurements/predictions is coarse spatially. The urban area can be considered as a single weather zone, in which the weather condition can be considered uniform. Ensemble model is simply not necessary for our case. Second, the statistical properties of the weather dynamics, such as the frequency of weather change, are lost in the ensemble model. The statistical property is critical to provide tractable system-theoretical analyze for the UAV traffic. Third, the ensemble model is simply to expensive to compute. To address these issues, continuous-time Markov chain model is used to model the switching of weather conditions. Despite the fact that the weather dynamics evolves according to complex partial differential equations, we are interested in only a few nominal weather conditions, such as sunny, windy, rainy etc,., which are meaningful for UAV traffic management system. Therefore, the continuoustime Markov chain model is further modeled to be a finite-state one.
Simple first-order Markov chain model is able to closely predict the weather pattern [18]. Some articles argue that the memory-less first order Markov chain model is not enough for accurate weather prediction, and proposed second-order Markov chain to achieve more accurate predictions [19]. That being addressed, higher order finite-state Markov chain model can be transfered in to a first order one by expanding the state space [20]. Therefore, in this paper, we assume that a first order Markov chain weather model is obtained to closely predict the weather pattern, so that we can focus on the analysis for the traffic dynamics under weather uncertainty. The Markovian formulation of the weather uncertainty in air traffic study can also be found in [21,22]. The impact of the weather on the UAV traffic flow is modeled as the fluctuations in the capacities of traffic queues. Bad weather reduces the the maximum number of UAVs can departure from a traffic queue. Thus we let each of the weather conditions corresponds to an operational mode of the traffic queues, each operational mode defines the capacities of the queues in the traffic system. The queue length does not jump during mode switching. The resulting queuing model is called piecewisedeterministic queuing model [23]. Since the mode is switching according to a finite state Markov chain, our model also belongs to the class of piecewisedeterministic Markov Process [24].
The term of resiliency has various meanings in control system context. The resilience considered under UAV traffic setting is defined as: (1) robust against random perturbations, (2) efficiency with robustness. The random perturbation for UAV operation will mainly come from the weather uncertainty. Based on the stochastic queuing models, the questions we try to answer is: (1) under what conditions will the traffic queue be bounded under capacity fluctuation?
(2) How can we improve the throughput of aforementioned traffic link mod-els? To answer the first question, we first introduce the notion of stability in term of bounded moment generating function of queue length. This general notion of stability guarantees the boundedness of the first moment (expectation), which is the quantity of interest, as well as higher order moments. Other stability notion may be used such as asymptotic stability, which implies that the queue will converge to equilibrium point with probability 1 [25]. However, we stress the fact that converging to a certain equilibrium may not have practical meaning in traffic applications. The necessary condition for each model is intuitive; it states that the inflow rate must be less or equal to the time average of the capacity of each queue. The derivation for sufficient conditions is based on well-known Foster-Lyapunov drift condition on stability analysis for Markov processes [26,27]. Based on the form of the Lyapunov function we choose, we end up with sufficient conditions in bilinear inequality form which can be solved numerically. Same stability analysis considering different models in ground traffic management setting can be found in [23,28]. With the stability results we derived, we are able to answer the second question. We show that the a sequence of bilinear inequality can be solved to maximize the throughput of each model when stability is guaranteed. Feedback control or stochastic inflow can be considered under the same framework in future research.
Note that our models in differential equation form is based on the underlying fluid queuing model. This is motivated by the vast number of UAVs that will put into service in the urban airspace [5,29], and the dense traffic they will create [4]. The continuous-time model can capture the fast evolution of aggregated flow in UAV traffic system. Our definition of resilience and analysis are not limited to the continuous-time model. Discrete-time models can be proposed and stability conditions can be derived under discrete version of Foster-Lyapunov drift condition [30]. The main contribution of this paper is summarized in the following: 1. We develop models for the UAV traffic dynamics under weather uncertainty in three basic components in traffic networks: single link, tandem link, and merge link, based on fluid queuing model. The weather uncertainty is modeled as continuous-time Markov process. The uncertainty impact is captured by fluctuation of capacity for each queue.
2. We introduce the notion of resilience in terms of the stability and optimality of the queuing system under uncertainty. The stability is defined as boundedness of moment generating function of the queue length. We derive the necessary and sufficient conditions for the traffic queues to be stable in the three traffic models. The necessary condition for each model is intuitive; it states that the inflow rate must be less or equal to the time average of the capacity of each queue. The sufficient conditions are in bilinear inequality form, which can be checked by optimization softwares. Optimality is defined as maximum constant inflow rate with stability guarantee. We show that the optimal flow rate can be calculated by solving a sequence of bilinear inequality problems. Numerical examples verify our theoretical results, and illustrate the impact of uncertainty on optimal flow.

Preliminaries
We first introduce mathematical notations used throughout this paper. Denote R n ≥0 as real vector space with dimension n, with each element greater or equal to 0. Denote operator | · | as the cardinality if a set is considered, as 1-norm if vector space is consider unless otherwise specified. Let E(X) be the expectation of random variable X, exp(X) as the exponential function of X.
We introduce basic notations for fluid queuing model for UAV traffic. The most basic element in queuing system is a single queue, consisting of a buffer and a server. The buffer stores queue, and may have finite or infinite buffer size. Fluid queue receives the traffic at nonnegative inflow rate r(i, q, t) [veh/hr] (vehicles per hour) and the server discharge the traffic flow at nonnegative rate is the existing traffic in the buffer. Let set of the modes be I and |I| = m. The discharge rate is minimum of the sending flow rate s(i, q, t) [veh/hr] and the mode dependent capacity c i . Let uppercase Q ∈ Q and I ∈ I denote the continuous and discrete stochastic state of the stochastic process, where feasible Q is defined on R ≥0 . The state space of the queuing system is the Cartesian product: Q × I. Dynamics of the queue length is then defined in an ordinary differential equation This is a general description of fluid queue dynamics. This can also be used to describe the queuing system of multiple queues by considering Q as a vector. Figure 1 demonstrates single fluid queue model. In the rest of this paper, all the traffic queue system will be one or combination of the single fluid queuing models. The uncertainty of system comes from the weather change, This is captured by the jump of mode I. Jumping between operation modes is assumed follow a continuous-time Markov process. Let the governing transition matrix be: where λ ij , i, j ∈ I, i = j are the time invariant jumping rate, We make further assumption that the process is ergodic and irreducible. This admits that the Markov process has a unique steady state distribution that satisfies the linear system: where p = [p 1 , p 2 , . . . , p m ] ∈ R m + ,and |p| = 1 [31]. To define the resilient performance of the queue under uncertainty, we adopt the notion of stability in the sense of the bounded moment generating function of queue length. The formal definition is following: This notion of stability is first introduced by Dai and Meyn [32]. Note that expanding the exponential term using Taylor series yields boundedness for the time average of expected queue length, which shows more practical meaning.

Main Results
In this section, we will derive the necessary and sufficient conditions for single queue, tandem queue, and merge queue. For latter two queuing models, we adopt the fundamental diagram of traffic to model state dependent discharge rate of queue and study the spillback effect.

Single Queue
Here we consider the simplest case where UAVs are congested at one point. Such case is very common in the traffic system; it can be at the ground station/warehouse where there is high volume of take off demand. In this case, we assume that the discharge of single fluid queue is simple on/off process, which is described below. We do not impose any more complicated model for single congestion because for ground station, the discharge rate is less affected by the amount of demand/inflow at ground station, UAVs can always be released at capacity at each mode. The flow diagram is: where c i is the discharge rate configuration for mode i ∈ I with unit of vehicles per hour, a is the constant inflow rate of UAVs. Then the UAVs queue at single point evolves according the dynamics: Under this model, there are rich theoretical literatures discussing the behavior of the queue, and we apply the results in following: Theorem 1. The sufficient and necessary conditions for (5) to hold is: Proof. See Appendix .1.
The queue of UAVs is stable if and only if the inflow rate is less or equal to the time average of capacity for piecewise constant discharge rate, which follows the intuition. For single fluid queue, we are able to present the steady state distribution for the queue length based on previous works [33] [14]. Denote probability: and let F (q) = [P (q, 1), P (q, 2), . . . , P (q, m))]. The spectral representation of F (q) is given by: where finding l ∈ R, φ ∈ R m is associated with a generalized eigenproblem [33]. This shows that single queue model serves as a strong tool not only in deriving conditions for bounded queue, but also giving estimations for the queue length.

Tandem Queue with State Dependent Processing Rate
In the air traffic system, aircrafts travel in virtual paths called links. Links define the allowable space the aircrafts can travel in. It is common that links are connected to each other. Here we pay our attention to two connected link, and study the spillback effect. In [34], Jin et al. studied the spillback effect in traffic with tandem fluid queuing model. The tandem fluid queue consists of two connecting queue where the outflow of the upstream queue is the input of the downstream queue. The discharge rates in [34] is piecewise constant. In this section, we establish a new model to closer describe the nature of traffic behavior at congestion point by adopting the fundamental diagram [16] and study its stability conditions. Consider a system with two queue connected in series. Traffic arrives at the upstream link with constant flow rate a. The outflow of upstream queue then becomes the inflow of downstream queue. The continuous stochastic state variable of the system is Q(t) = [Q 1 (t), Q 2 (t)] T , and q = [q 1 , q 2 ] T is the realization of Q or existing queue length in the system. By convention, Q ∈ Q, Q = R 2 ≥0 defines the state space for continuous stochastic state. The diagram of tandem fluid queue is shown in Figure 2.
More about fundamental diagram of traffic can be found in [16]. We assume that the maximum discharge rates among all modes for both queues are the same, that is: And denote c min j = min i∈I c ji . Follow from [35] [36], we also assume: along with (10), this gives: Thus, by mass conservation, the evolution of system states is: It can be seen that, the system is piecewise affine and continuous at each mode therefore locally Lipschitz continuous. Given the switching signal follows a irreducible and ergodic Markov process, therefore nonexplosive, unique solution for (14) exists [37]. Let the solution for system (14) be q(t), (14) can be written as:Q where at the derivative at jumping instance are defined as right limit. The queue is said to be stable if (5) holds. Note that the described system is continuous, hence is also right continuous with left limit (RCLL). Therefore, the infinitesimal generator of V (i, q) is given by: for any smooth function V in the continuous argument [24]. In order to derive the stability conditions, we first construct the invariant set for continuous state variables, and show the sufficient condition for stability for all initial conditions in the invariant set. A setQ ⊆ Q is invariant if: The construction of the invariant set follows the following idea. Let the invariant set be Cartesian productQ = [q 1 , ∞] × [q 2 , q 2 ], such that the states governed by (7) is non-decreasing when q 1 ≥ q 1 , q 2 ≥ q 2 and non increasing when q 2 ≤ q 2 .
We further split the invariant set into two parts, such thatQ =Q 1 ∪Q 2 , whereQ ∞ = [q c , ∞] × [q 2 ,q 2 ],Q ∈ = [q 1 , q c ] × [q 2 ,q 2 ], and define Now we are ready to establish the necessary and sufficient conditions for the system (15) to be stable.
This follows the intuition that if the upstream traffic queue does not grow to infinity, one must have the average capacity greater than the input traffic rate at each end of the queue. The sufficient condition (21) can be understood in two parts. The first term in the inequality is the effect from the dynamics of the system, and the second term is the effect from the mode transition.

Merge Link with State Dependent Processing Rate
It often shows in the traffic system that two links merge into one, or one link splits into two. Here we pay our attention to the situation where traffic comes from two sources and merge in to one link in the traffic. We will derive necessary and sufficient conditions for the merge queue. It is an extension of tandem fluid queuing model. Two upstream links are connected to one downstream link. Upstream links are modeled as infinite buffer size queue, and the downstream link is modeled as finite buffer size queue. The continuous stochastic state is  The control action of the merging link is the inflow allocation of the downstream queue; the fraction of downstream intake allocated to a upstream discharge is proportional to the amount of traffic in the queue. The flow diagram in short-hand thus is: The evolution of states, by mass conservation, is: Similarly, we can derive the stability conditions for system (23) in the sense of (5). We follow the same strategy for proving stability condition for tandem fluid queue. We first construct the invariant setQ = [q 1 , ∞] × [q 1 , ∞] × [q 3 , q 3 ], and use the monotonic property of Lyapunov function with respect to continuous argument to prove the sufficient condition for initial condition in the invariant set. The proofs for necessary and sufficient conditions are very similar. The construction for the invariant set is slightly different. We present the construction and proof for invariant set in following: Proposition 2. For fluid queue system (23) with constant inflow vector a 1 , a 2 ∈ R the setQ = [q 1 , ∞] × [q 2 , ∞] × [q 3 , q 3 ] is invariant with boundaries defined as follows: Proof. See Appendix .4.
Solving above minimization problem can be easy. By definition: It is not hard to see that f 13 (i, q) + f 23 (i, q) + f 3 (i, q) is monotonously increasing function with respect to q 1 , q 2 , and concave function with respect to q 3 . Therefore, minimum can be found by checking the boundaries of the sets.
Theorem 3. The necessary condition for (5) to hold for system (23) is a j ≤ m i=1 c ji p i , for j = 1, 2, and a 1 + a 2 ≤ m i=1 c 3i p i . If there exist positive constants α 1 , α 2 . . . α m and β such that: (23) is stable in sense of (5) The proof for necessary condition is very similar to the one for tandem queue. Define Lyapunov function as: where α i , β ∈ R + , h = [2 2 1] T . We can prove sufficient condition for merge link with same argument in proving sufficient condition for stability in tandem queue. Therefore omitted. The sufficient condition not only provides the method for checking if a pair of inflow rates will be stabilizing, it also offers insight for traffic flow allocation. In our model, the sufficient condition guaranteed stability for the merge queue system if the downstream intake allocation follows a proportional priority rule. Some other allocation rule may be analyzed under the same framework.

Numerical Examples
In this section, we validate our theoretical findings through numerical simulations, and we show that the optimal throughput under uncertainty can be solved via solving sequence of bilinear inequality.

Stability Conditions
The stability conditions is verified in the merge link model. The modes are set to be one normal mode and one reduced capacity mode (congested mode), thus, The parameters for simulations are listed in the table below: The parameters for numerical illustrations for tandem fluid queue is shown in Table  1. Let the governing transition matrix for mode switching to be: The steady state distribution for given transition matrix is p = [0.5 0.5]. To verify the necessary condition in Theorem 3, we set the inflow to be a 1 = 300[veh/hr], a 2 = 500[veh/hr]. Therefore, a 1 + a 2 > p T c 3 = 600; the necessary condition is violated. It can be seen in Figure 4 that the downstream queue q 3 reaches its buffer size and the upstream queues, q 1 and q 2 grows unbounded. To see the sufficiency in Theorem 3, we let a 1 = 200[veh/hr], a 2 = 250[veh/hr], then the bilinear inequality is solved with YALMIP, a Matlab based optimization package [38]. The solution is α 1 = 9.1956, α 2 = 12.6839, b = 0.1891. The response is shown in Figure 5.

Optimality under Uncertainty
In this subsection, we show how to improve the traffic throughput under weather uncertainty, and how the parameters of uncertainty will affect the throughput in the tandem fluid queuing model. Based on the form of bilinear inequality (27), the analysis for throughput of merge link is very similar to the one in tandem link. Namely, we try to find the maximum constant inflow rate to yield stabilizing queue via sufficient condition with different parameters. This will be important for decision makers to assign traffic to each link. We claim that with the sufficient condition we derived, stability for constant inflow can be verified. We will be studying the impact of transition intensity and fluctuation on the maximum stabilizing inflow for tandem fluid queue. This problem can be reformulate as: maximize a a, subject to (21).
The maximization problem can be solved using bisection search. In each iteration of the bisection search, we solved the bilinear inequality (21). The parameters v, w, θ for numerical illustrations for tandem fluid queue is same as the ones in Table 1. We consider two operational modes, one normal, and one congested, therefore, I = {1, 2}. The capacity of downstream link is reduced in the congested mode. Let upstream capacity be c 1 = [800, 800], downstream capacity be c 2 = [800, 400]. Elements are corresponding with normal and congested mode respectively. Let the governing transition matrix for discrete state Markov jump be: The larger µ is, the more frequent the mode of tandem fluid queue will switch to congested mode. The steady state distribution is p = 1 1+µ [1 µ] T , with which we can compute the inflow rate for necessary condition (43). Denote a n and a s the maximum inflow rate for necessary condition to hold and the maximum inflow rate for sufficient condition to hold respectively.  Figure 6: The change of inflow for necessary condition to hold an and inflow for sufficient condition to hold as with respect to transition intensity parameter µ. Figure 6 shows a n and a s with varying transitional intensity. It follows the intuition that when congested mode is visited more frequently, both inflow rate for necessary condition to hold and inflow rate for sufficient condition to hold will decrease. Different magnitude of capacity fluctuation under same transitional intensity may yield the same necessary bound for inflow rate, however, this is not true for inflow rate for sufficient condition to hold. We demonstrate this property by numerical example. Let state transition matrix be: Let the capacity fluctuation be c 1 = [800, 800], c 2 = [600 − δ c , 600 + δ c ]. The steady state distribution of mode is p = [0.5 0.5]. Thus, the a n = 600 for any δ c . Figure 7 shows that the stabilizing inflow rate decrease with the magnitude of the fluctuation.

Conclusion
In this paper, we consider the congestion in future UAV traffic system under weather uncertainty from a system-theoretical perspective. We developed models for UAV traffics dynamics in three basic traffic link components. Based on our models, we derived the necessary and sufficient conditions on the inflow rates for the long run stability. We show that the necessary condition is intuitive, and the sufficient condition can be numerically verified. With our results, future UAV traffic designer can have insight and method on designing the flows in UAV traffic network and improve performance with stability guarantees.

Proof for Theorem 2
We first prove necessity for stability. Integrating (15), we get: Therefore, (5) is essentially the bound for the moment generating function of |Q(t)|, we have P (lim t→∞ Q j (t)) = 0, j = 1, 2. Thus, For each mode i, define the total duration time at each mode to t: By [26]: Thus, From (45), we can also get 0 ≥ a − m i=1 c 2i p i . The proof for sufficient condition is derived based on a general results from Meyn and Tweedie [27]. The result states follow: If there exists a radially unbounded function 1 V : I ×Q → R ≥0 , such that for then, for any initial condition (i, q) ∈ I ×Q, lim sup where V : I × Q → R + is called Lyapunov function, and condition (49) is called drift condition. By defining Lyapunov function as V (i, q) = a i exp(bh T q), where h is element-wise positive. It can be seen that (50) implies stability (5). Consider the Lyapunov function: where s = [2, 1] T .By (16) and (49) gives: Maximizing left hand side of second equation in (52) over q ∈Q: max q∈Q (LV (i, q) + cV (i, q)) = max q∈Q cα i + 2α i βa − α i βf 12 (i, q) − α i βf 2 (i, q) We first consider for q ∈Q 1 . Minimization onQ 1 can be easily done since the solution of this problem must lie on the boundaries ofQ 1 . To see this, by definition (10) f 12 (i, q) + f 2 (i, q) = min{vq 1 , c 1i , w(θ − q 2 )} + min{vq 2 , c 2i }.
This is a piecewise linear function with respect to q 1 with positive coefficient, therefore monotonously increasing with respected to q 1 with upper bound; we have arg min q1∈[qc,∞] (f 12 (i, q) + f 2 (i, q)) = q c . The above function is a sum of two upper bounded concave function with respect to q 2 , therefore the arg min q2∈[q2,q2] (f 12 (i, q) + f 2 (i, q)) ∈ {q 2 ,q 2 }. Thus the minimization problem can be solved by enumeration. Let c = 1 max αi , d = 0, then (49) is satisfied. For q ∈Q 2 , we have: max q∈Q2 (LV (i, q) + cV (i, q)) Define: then (49) is satisfied. V and F 2 are bounded onQ 2 , therefore maximizations are well defined.