# Distributed Congestion Control via Outage Probability Model for Delay-Constrained Flying Ad Hoc Networks

Authors: Shaojie Wen; Lianbing Deng; Shuo Shi; Xiying Fan; Hao Li
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Drastic changes in network topology of Flying Ad Hoc Networks (FANETs) result in the instability of the single-hop delay and link status accordingly. Therefore, it is difficult to implement the congestion control with delay-sensitive traffic according to the instantaneous link status. To solve the above difficulty effectively, we formulate the delay-aware congestion control as a network utility maximization, which considers the link capacity and end-to-end delay as constraints. Next, we combine the Lagrange dual method and delay auxiliary variable to decouple the link capacity and delay threshold constraints, as well as to update single-hop delay bound with the delay-outage mode. Built on the methods above, a distributed optimization algorithm is proposed in this work by considering the estimated single-hop delay bound for each transmission, which only uses the local channel information to limit the end-to-end delay. Finally, we deduce the relationship between the primal and dual solutions to underpin the advantages of the proposed algorithm. Simulation results demonstrate that the proposed algorithm effectively can improve network performances in terms of packet time-out rate and network throughput.


---

## Body

## 1. Introduction

The unique characteristics of unmanned aerial vehicle (UAV), such as easy deployment, high flexibility, and low cost, make it be more and more applied to military and civil fields [1–3]. However, single-UAV system cannot be extended to more applications due to its simple functions and limited coverage. In order to overcome the shortcomings of the single-UAV system and expand its application range, it can increase the number of UAVs to establish a multi-UAV system [4] in ad hoc way, called Flying Ad Hoc Networks (FANETs). In FANETs, each UAV can communicate with destinations through single-hop or multihop mode. At the same time, each UAV can be used as a source node or a relay node to help other UAVs transfer data packets. Compared with the multi-UAV system in cellular mode, FANETs have better flexibility and scalability, which allows UAVs to choose different communication modes according to actual needs and also allows UAVs to fly freely in a certain range to expand the working range. In addition, FANETs enable the UAV network to get rid of the regional restrictions on the deployment of ground base stations, and a small number of base stations can cover a large area. When it is inconvenient to deploy base stations in desert, ocean, disaster areas, or the ground base stations cannot work normally; FANETs can provide full coverage communication services to meet the needs of the terminals.In wired and wireless networks, congestion is always an undesirable situation since it can deteriorate the communication environment, especially in the delay-constrained applications. Congestion can lead to packet drops and retransmission either at the MAC or upper layers. Designing and implementing a congestion control algorithm [5] is a challenging task, since many factors need to be taken into account. The congestion control mechanism cannot handle the properties of a shared wireless multihop channel well [6]. Various situations may lead to packet loss and retransmissions like path break due to mobility, hidden terminal problem, or high error-prone wireless links. Dramatic changes in network topology and the poor wireless channel result in unsteady packet delivery delays and packet loss rate, which brings challenges to delay-aware congestion control in FANETs. In addition, it is difficult to limit the total transmission delay in a given threshold due to the unpredictable link status caused by high mobility of UAVs. Therefore, it is required to design a delay-aware congestion control method that can adapt to the time-varying link status and ensure the delay requirements.In order to propose a reasonable solution, the framework of network utility maximization [7] is regarded as the mathematical form of the delay-aware congestion control problem. To this end, we use a Lagrange dual method [8] to decouple the link capacity constraint and a delay-outage model [9] to estimate the single-hop delay bound, after that the primal problem can be solved in a distributed way. Further, we propose a distributed optimization method with the consideration of the dramatic changes in network topology and unpredictable link status. Finally, we analyse the performances of the proposed optimization method and its convergence.To the best of our knowledge, few previous works consider delay-aware congestion control problem in FANETs. In summary, our contributions are two-folds:(i)
We formulate a network utility maximization framework with end-to-end delay constraint for FANETs. To match with the dynamic network topology, the Lagrangian dual method is exploited to decouple the link capacity constraint and a delay-outage model to estimate the single-hop delay bound. Then, the primal problem is transformed into a distributed solvable problems, which allows the senders to implement congestion control with delay-outage model(ii)
We propose a distributed delay-aware congestion control algorithm that incorporates the single-hop delay bound to achieve the optimal solution. To maximize the network utility and reduce the transmission delay in distributed way, we introduce a delay auxiliary variable for all links and update the single-hop delay bound jointly combining the aggregated incoming flow and delay-outage probability. Finally, we analyse the performances of the optimization method and prove its convergenceThe remainder of this paper is organized as follows. In Section2, we introduce some previous work researched by others. In Section 3, we present the network model and some preparatory works for the design of the optimization method. In Section 4, we provide the detailed implementation process and the performance analysis of given optimization method. In Section 5, we show some simulation results for the proposed optimization algorithm. Finally, we conclude the paper and discuss the future work in Section 6.


## 2. Related Work

Congestion control has been studied a lot in traditional wired and wireless networks, and the previous works mainly used the framework of network utility maximization to adjust the rate of packets generated by nodes. In some research work, congestion control problem is formalized as utility maximization problem [10] and then solved by optimization tools to reduce network congestion. Based on the theory of network utility maximization, Mehta and Lobiyal [11] proposed a framework for wireless multihop networks considering scheduling, routing, congestion control, and power control jointly by considering the long-term or short-term random attenuation of wireless channels. D’Aronco et al. [10] proposed a new cross-layer framework to jointly optimize congestion control, routing, competition control, and power control in ad hoc networks, so as to overcome the performance limitations caused by the lack of cooperation between layers. Khodaian and Khalaj [12] analysed the delay in random access multihop networks, solved the delay-constrained utility maximization problem, and worked on achieving an optimal trade-off between delay, rate, and energy. Li et al. [5] considered congestion control with delay-sensitive/insensitive traffic and formulated a new network utility maximization problem which can be solved in a decentralized way. Zhang et al. [13] studied the joint optimization of congestion and power control in cognitive radio ad hoc networks under predictable contact constraints. At the same time, a distributed cross-layer optimization framework is proposed to achieve the joint design goal of hop by hop congestion control at the transport layer and power control at the physical layer. Rangisetti et al. [14] designed a centralized software-defined LTE wireless access network framework and proposed a new QoS aware load-balancing algorithm to solve the problem of load imbalance in the network. Kafi et al. [15] proposed a congestion control-based scheduling algorithm to solve the problem of throughput maximization. Hajiesmaili et al. [16] solved the rate allocation problem in heterogeneous QoS aware applications to maximize the network utility of convergence within a fixed time interval and make each data stream meet the requirements of long-term average end-to-end delay constraints. To solve the congestion problem in wireless multimedia sensor networks, Alaei et al. [17] proposed a distributed congestion control method. When congestion is detected, a local binary tree is established at the congestion node to eliminate congestion. In the next possible congestion node, the established tree is used to send their packets, while when the established tree cannot eliminate congestion, the mobile sink node is used to assist communication. Silva et al. [18] studied the congestion control in delay and disruption tolerant networks (DTNs) and introduced Smart-DTN-CC, a novel DTN congestion control framework that adjusts its operation automatically based on the dynamics of the underlying network. Leon et al. [19] proposed a new fair and distributed congestion control mechanism for Neighborhood Area Networks to provide fairness in the access to the network. Lubna et al. [20] considered to improve the throughput by implementing a novel technique to dynamically control the decrease factor of the congestion control algorithm depending on the interval between packet losses in multipath TCP. Verma and Kumar [21] introduced a new congestion control policy to adapt the transmission rate quickly whenever the available bandwidth and delay changes for Internet of Things, which is aimed at reducing packet drops and improving throughput.


## 3. System Model and Problem Formulation

### 3.1. Network Model

The notationV is a finite set containing all the UAVs that freely fly in the specific space, l is a link connecting a pair of UAVs, and L represents the set ∀l∈L, as shown in Figure 1. If the distance between UAV j and UAV i is less than communication radius, j∈Ni, where Ni is a neighbor set of UAV i. The notation s denotes a session initialized by a source UAV, and S is a set of all executing sessions. The path Ls is a set of links travelled by session s, and a set containing all sources that use link l represents Sl=s∈S∣l∈Ls.Figure 1
The FANET model.The single-hop delay over the linkl represents dl, and the total delay along the path Ls, denoted by ∑l∈Lsdl, should be less than the delay threshold Is. We assume that all sessions have the same delay threshold, and all UAVs have common power level. According to our previous work, the capacity of link l, namely cl, can be regarded as invariant in specific time interval Δt. The definitions of notations or parameters can be found in Table 1.Table 1
List of notations.
NiOne-hop neighbor set of nodeisThe identifier of the sessionLsA set of all links or a path travelled by sessionsSlA set of all sessions that use linklSThe set that includes all sessionsIsDelay threshold for sessionsN0The variance of environmental noiseclThe link capacity of linklrsThe generation rate at sourcesdlThe transmission delay over link (i,j)KThe length of data packet


### 3.2. Single-Hop Delay Model

Each link is modeled as an M/G/1 queue, and all packets have an exponentially distributed length with a mean ofK bits. According to the results in [22, 23], we can get an approximate single-hop delay value for link l during interval Δt.
(1)dl=Kcl−∑s∈Slrs,where ∑s∈Slrs is the aggregated rate of all the sessions over the link l.


### 3.3. Problem Formulation

Assume that each source can attain an utility functionUrs [24] by generating data flow at the rate of rs, where Urs=ωslogrs and ωs are constant. It is noted that Urs is a smooth, strictly concave, monotonically nondecreasing and one-order continuously differentiable function of rs. This work aims at maximizing the total utility functions of all sources under the link capacity constraint and the total delay along the path constraint; hence, the problem can be formulated as a utility maximization problem P1, which is described as
(2)P1:max∑s∈SUrs,(3)s.t∑s∈Srs≤cl∀l∈L,(4)∑l∈Lsdl≤Ts∀s∈S.According to the concavity of utility functionUrs, the aggregated function in (2) is also concave. Due to the linear relationships of the constraints (3) and (4), the optimization problem P1 is also a concave optimization.


## 3.1. Network Model

The notationV is a finite set containing all the UAVs that freely fly in the specific space, l is a link connecting a pair of UAVs, and L represents the set ∀l∈L, as shown in Figure 1. If the distance between UAV j and UAV i is less than communication radius, j∈Ni, where Ni is a neighbor set of UAV i. The notation s denotes a session initialized by a source UAV, and S is a set of all executing sessions. The path Ls is a set of links travelled by session s, and a set containing all sources that use link l represents Sl=s∈S∣l∈Ls.Figure 1
The FANET model.The single-hop delay over the linkl represents dl, and the total delay along the path Ls, denoted by ∑l∈Lsdl, should be less than the delay threshold Is. We assume that all sessions have the same delay threshold, and all UAVs have common power level. According to our previous work, the capacity of link l, namely cl, can be regarded as invariant in specific time interval Δt. The definitions of notations or parameters can be found in Table 1.Table 1
List of notations.
NiOne-hop neighbor set of nodeisThe identifier of the sessionLsA set of all links or a path travelled by sessionsSlA set of all sessions that use linklSThe set that includes all sessionsIsDelay threshold for sessionsN0The variance of environmental noiseclThe link capacity of linklrsThe generation rate at sourcesdlThe transmission delay over link (i,j)KThe length of data packet


## 3.2. Single-Hop Delay Model

Each link is modeled as an M/G/1 queue, and all packets have an exponentially distributed length with a mean ofK bits. According to the results in [22, 23], we can get an approximate single-hop delay value for link l during interval Δt.
(1)dl=Kcl−∑s∈Slrs,where ∑s∈Slrs is the aggregated rate of all the sessions over the link l.


## 3.3. Problem Formulation

Assume that each source can attain an utility functionUrs [24] by generating data flow at the rate of rs, where Urs=ωslogrs and ωs are constant. It is noted that Urs is a smooth, strictly concave, monotonically nondecreasing and one-order continuously differentiable function of rs. This work aims at maximizing the total utility functions of all sources under the link capacity constraint and the total delay along the path constraint; hence, the problem can be formulated as a utility maximization problem P1, which is described as
(2)P1:max∑s∈SUrs,(3)s.t∑s∈Srs≤cl∀l∈L,(4)∑l∈Lsdl≤Ts∀s∈S.According to the concavity of utility functionUrs, the aggregated function in (2) is also concave. Due to the linear relationships of the constraints (3) and (4), the optimization problem P1 is also a concave optimization.


## 4. The Solution of Problem

It is noted that the constraint (4) is end-to-end tightly coupled, which makes the formulation P1 more complicated. Therefore, to decompose the relationship of the constraint (4), it is feasible to transform the primal complicated problem into local solvable problem. To achieve the goal, an auxiliary variable [12] is introduced, defined by d¯l, as the single-hop delay bound for each link l. Hence, the following inequality holds, ∑l∈Lsd¯l≤Ts. Therefore, constraint (4) can be represented as dl≤d¯l and ∑l∈Lsd¯l≤Ts. To replace dl with the right side of the (1), the single-hop delay constraint over the link l can be denoted as K/cl−∑s∈Slrs≤d¯l, and to rearrange the inequality, it can obtain the other form as
(5)∑s∈Slrs≤cl−Kd¯l.Because the value ofK/d¯l is greater than zero, thus the relation cl−K/d¯l≤cl is hold. Analyzing from the structure of (3) and (5), the former is a more compact constraint than the latter; hence, we can use (5) instead of constraint (3) in formulation P1, and the details can be denoted as
(6)P2:max∑s∈SUrs,s.t∑s∈Slrs≤cl−Kd¯l,(7)∑i,j∈Lsd¯l≤Ts.


### 4.1. Lagrangian Solution

Due to the decentralized structure of FANETs, it is difficult to solve the congestion control problems with link capacity and delay constraints in a centralized way. Fortunately, the Lagrangian dual method [8] can overcome this obstacle by introducing a Lagrange multiplier vectors for constraint (6) to simplify the optimization process, denoted as γ. The Lagrangian form of P2 can be presented as
(8)D=max∑s∈SUrs+∑l∈Lγl⋅cl−Kd¯l+∑s∈Slrs.By rearranging equation (8), a new form can be obtained as
(9)D=max∑s∈SUrs−rs⋅∑l∈Lsγl−∑l∈Lγl⋅Kd¯l.As we all know, the expressions −max and min are equivalence. Therefore, the equation (9) can be divided into two optimization problems as follows
(10)D1=max∑s∈SUrs−rs⋅∑l∈Lsγl,(11)D2=min∑l∈Lγl⋅Kd¯l,s.t.∑l∈Lsd¯l≤Ts∀s∈S.According to the feature ofUrs, D1 is regarded as an unconstrained concave optimization; hence, the gradient decent method can be used to solve it. The optimal value of rs is calculated as
(12)rs∗=argmaxUrs−rs⋅∑l∈Lsγl.The notationγln denotes the value of Lagrange multiplier γl at nth iteration [25].
(13)γln+1=γln−β∂D∂γl+,where β is a step-size factor, the operation [·]+ denotes x=max0,x, and
(14)∂D∂γl=cl−Kd¯l+∑s∈Slrs.In dynamic environments, the drastic changes in network topology result in unstable channel states, and the choice of constant step size is of practical importance to guarantee the convergence and speed up the calculation [26, 27].We can see that the optimal values ofrs only relate to the aggregated step-size ∑l∈Lsγl from (12); however, the update of step-size γl is related to both rs and d¯l as shown in (13). Based on this, it is necessary to further calculate the value of single-hop delay bound d¯l. From the structures of D2, it can be seen that the end-to-end information is required for the optimal value of d¯l due to the presence of constraint (4). In order to keep the performance not degraded in terms of delay caused by the collection of all channel information on the path, a solution that considers only local information needs to be found. Fortunately, we can use the results derived from [9], the probability of a packet being discarded at link l due to the excessive single-hop delay threshold d¯l(15)Pth=Prdl>d¯l=exp−cl−∑s∈Slrs⋅d¯l.The definitions of three parameters shown in (15) can be found in Table 1. From (15), we can see that the probability Pth is proportional to the aggregated rate ∑s∈Slrs, but an inverse case to the link capacity cl and delay bound d¯l. The relationship in (15) meets our expectation, which proposes a method to derive the value of d¯l by limiting the size of probability Pth. Assume that constant 0<ε<1 is the upper bound of Pth allowed by the communication system for all the links and replace Pth with ε (15) can be converted into
(16)ε=exp−cl−∑s∈Slrs⋅d¯l.Use mathematical method to derive the expression ofd¯l as
(17)d¯l=−1nεcl−∑s∈Slrs+εl,where εl is the delay cumulative errors on the links passed by the packet before arriving at link l. We define the initial value of the single-hop delay bound, namely d¯lint=T/Ls, and the initial value of ε is calculated by replacing d¯l with d¯lint. The single-hop error ε¯l can be expressed as ε¯l=d¯l−d¯lint. The notation ∣Hl∣ denotes the total hops passed by the packet from source s to l excluding the link l; hence, εl=∑l=sHlε¯l/Hl. Assume that the network system will trend to a steady-state in the limited time, the condition ∑l∈Lsε¯l≤0 must be met for all sessions due to the presence of delay threshold Js. Next, substitute (17) into the objective of (11), we can see that the optimization D2 trends to an optimal solution with the increase of ∑s∈Slrs. In addition, the solution of (17) can be used to update the iterations shown in (13). Therefore, when the rate rs of each source and Lagrange multiplier vector γ achieve optimality, the single-hop delay bound d¯l also has an optimal solution for each link l.Until now, we propose an effective method to solve the optimization problemP2, which allows the update processes of each parameter consider only local information. Nevertheless, the presence of the constraint in (11) would cause the sum of single-hop delay on the path to exceed the total delay threshold Js.It is obvious that the challenge can be tackled by adjusting the value ofε; if more packets are discarded due to the excessive threshold Js, a greater ε is required. The implementation processes can be found in Algorithm 1.


### 4.2. Algorithm Analysis

Before analyzing the performance of Algorithm1, some basic relations should be provided to illustrate the obtained results. Let |·| denotes the Euclidean norm, and N denotes the total iterations of Algorithm 1. The brief expression of ∂D/∂γl is defined by ϕγl, namely ∂D/∂γl=φγl. Assume that there are two constantsAlgorithm 1: Congestion control algorithm.
1: Initialize the parametersγ,rs,ε,ε=0;2: If the packet arrive at linkl3:  calculates the value ofd¯l based on (17);4:  calculates the value ofε¯l;5:ε+=ε¯l;6:  updatesγl with ∑s∈Slrs and d¯l;7: For each sources8:  collectsγl of all the links on the path L(s);9:  calculatesrs based on (12);10: update processes ends until vectorγ remains unchanged.Gmax and ε¯max=ε¯l∀l∈Ls are the upper bounds of cl−∑s∈Slrs and εl, respectively.To simplify the representations, we use the notationsF· and Q· to denote the total primal and dual functions. Also, both primal and dual functions of each link l are denoted by frs=Ursandqγl=Urs+∑l∈Lsγl⋅φγl respectively. According to the above definitions, we can create two relations: Fr=∑s∈SfrsandQγ=∑s∈Sqγl. Through analysing Algorithm 1, we can obtain the following results.Lemma 1.
Jointly considering two constants,Gmax and ε¯max, the upper bound of ϕ(γ) is given by
(18)φγl≤Gmaxη,where η=1−K/−lnε+Gmaxε¯max.Proof.
According to the expression of∂D/∂γ1,
(19)∂D∂γ1=φγl≤Gmax−Kd¯l.
Substitutingd¯l for the relation (17), we can obtain
(20)φγl≤Gmax−K−lnε/Gmax+εl.
Reorganize inequality to get(21)φγl≤Gmax1−K−lnε+Gmaxεl.
Based on the formεl=∑l=sH1ε¯l/Hl, it is easy to get εl≤∑l=sH1ε¯max/Hl=ε¯max. Combining the form (21), the inequality can be modified as
(22)φγl≤Gmax1−K−lnε+Gmaxε¯max.
For each single-hop transmission, inequalitydl≤d¯l holds, we can get 1≤(K/−lnε+Gmaxε¯max and the right side of inequality (22) is greater than 0. Jointly considering inequality (5) and η=1−(K/−lnε+Gmaxε¯max, the result (18) in Lemma 1 is proved.To obtain the difference between primal and dual functions, letΦ be a convex hull of all feasible transmission rates, rl∈Φ.Theorem 2.
If a feasible delay bound setd¯l∣∀l∈Ls exists for all traffics, the total differences between average dual value and optimal primal value with considering the result derived in Lemma 1 can be given as
(23)Fr∗≥Q^γ−Sγ1022Nβ+βGmax2η22,where γ0=maxl∈Lγl0andSis the number of all sources.Proof.
Based on the concavity of the local gain functionfrl,pl, the following inequality holds
(24)frs∗≥frsn=frln−γln⋅φrln+γln⋅φrln,where Yn refers to the value of Y at nth iteration. Using the relation between the primal and dual functions in (8) and the convexity of the dual function, (24) can be modified as
(25)frs∗≥qγln+γln⋅φr1n.
Summing all the terms from 0 toN−1 and divided by 1/N can get
(26)frs∗≥1N∑n=0N−1qγln+1N∑n=0N−1γ1n⋅φr1n.
Because the value offrs∗ is constant, the left side of inequality remain unchanged. Given the iterative relation of the dual multiplier γln in (13), we have
(27)γln+12≤γln2+2βγln⋅φr1n+β2φrln2,which implies that
(28)γln⋅φrln≥γln+12−γln22β−βφrln22.
Combining the result in Lemma1, we can obtain
(29)1N∑n=0N−1γln⋅φrln≥γlN2−γl022Nβ−gbGmax2η22.
Combining (26) and (29), it follows that
(30)frs∗≥1N∑n=0N−1qγln+1N∑n=0N−1γln⋅φrln≥q^γln+γlN2−γl022Nβ−βGmax2η22.
IfN approaches an enormous number, from (13) we can see that λlN≪λl0, and (30) has a new form
(31)frs∗≥q^γln−γl022Nβ−βGmax2η22.
Taking the total gains for all sourcesS(32)∑s∈Sfrs∗≥∑s∈Sq^γln−γl022Nβ−βGmax2η22.
Referring to the preceding definitions, we have(33)Fr∗≥Q^γl−Sγl022Nβ−βGmax2η22.
If we letγ0=maxl∈Lγl0, the final result can be concluded.


## 4.1. Lagrangian Solution

Due to the decentralized structure of FANETs, it is difficult to solve the congestion control problems with link capacity and delay constraints in a centralized way. Fortunately, the Lagrangian dual method [8] can overcome this obstacle by introducing a Lagrange multiplier vectors for constraint (6) to simplify the optimization process, denoted as γ. The Lagrangian form of P2 can be presented as
(8)D=max∑s∈SUrs+∑l∈Lγl⋅cl−Kd¯l+∑s∈Slrs.By rearranging equation (8), a new form can be obtained as
(9)D=max∑s∈SUrs−rs⋅∑l∈Lsγl−∑l∈Lγl⋅Kd¯l.As we all know, the expressions −max and min are equivalence. Therefore, the equation (9) can be divided into two optimization problems as follows
(10)D1=max∑s∈SUrs−rs⋅∑l∈Lsγl,(11)D2=min∑l∈Lγl⋅Kd¯l,s.t.∑l∈Lsd¯l≤Ts∀s∈S.According to the feature ofUrs, D1 is regarded as an unconstrained concave optimization; hence, the gradient decent method can be used to solve it. The optimal value of rs is calculated as
(12)rs∗=argmaxUrs−rs⋅∑l∈Lsγl.The notationγln denotes the value of Lagrange multiplier γl at nth iteration [25].
(13)γln+1=γln−β∂D∂γl+,where β is a step-size factor, the operation [·]+ denotes x=max0,x, and
(14)∂D∂γl=cl−Kd¯l+∑s∈Slrs.In dynamic environments, the drastic changes in network topology result in unstable channel states, and the choice of constant step size is of practical importance to guarantee the convergence and speed up the calculation [26, 27].We can see that the optimal values ofrs only relate to the aggregated step-size ∑l∈Lsγl from (12); however, the update of step-size γl is related to both rs and d¯l as shown in (13). Based on this, it is necessary to further calculate the value of single-hop delay bound d¯l. From the structures of D2, it can be seen that the end-to-end information is required for the optimal value of d¯l due to the presence of constraint (4). In order to keep the performance not degraded in terms of delay caused by the collection of all channel information on the path, a solution that considers only local information needs to be found. Fortunately, we can use the results derived from [9], the probability of a packet being discarded at link l due to the excessive single-hop delay threshold d¯l(15)Pth=Prdl>d¯l=exp−cl−∑s∈Slrs⋅d¯l.The definitions of three parameters shown in (15) can be found in Table 1. From (15), we can see that the probability Pth is proportional to the aggregated rate ∑s∈Slrs, but an inverse case to the link capacity cl and delay bound d¯l. The relationship in (15) meets our expectation, which proposes a method to derive the value of d¯l by limiting the size of probability Pth. Assume that constant 0<ε<1 is the upper bound of Pth allowed by the communication system for all the links and replace Pth with ε (15) can be converted into
(16)ε=exp−cl−∑s∈Slrs⋅d¯l.Use mathematical method to derive the expression ofd¯l as
(17)d¯l=−1nεcl−∑s∈Slrs+εl,where εl is the delay cumulative errors on the links passed by the packet before arriving at link l. We define the initial value of the single-hop delay bound, namely d¯lint=T/Ls, and the initial value of ε is calculated by replacing d¯l with d¯lint. The single-hop error ε¯l can be expressed as ε¯l=d¯l−d¯lint. The notation ∣Hl∣ denotes the total hops passed by the packet from source s to l excluding the link l; hence, εl=∑l=sHlε¯l/Hl. Assume that the network system will trend to a steady-state in the limited time, the condition ∑l∈Lsε¯l≤0 must be met for all sessions due to the presence of delay threshold Js. Next, substitute (17) into the objective of (11), we can see that the optimization D2 trends to an optimal solution with the increase of ∑s∈Slrs. In addition, the solution of (17) can be used to update the iterations shown in (13). Therefore, when the rate rs of each source and Lagrange multiplier vector γ achieve optimality, the single-hop delay bound d¯l also has an optimal solution for each link l.Until now, we propose an effective method to solve the optimization problemP2, which allows the update processes of each parameter consider only local information. Nevertheless, the presence of the constraint in (11) would cause the sum of single-hop delay on the path to exceed the total delay threshold Js.It is obvious that the challenge can be tackled by adjusting the value ofε; if more packets are discarded due to the excessive threshold Js, a greater ε is required. The implementation processes can be found in Algorithm 1.


## 4.2. Algorithm Analysis

Before analyzing the performance of Algorithm1, some basic relations should be provided to illustrate the obtained results. Let |·| denotes the Euclidean norm, and N denotes the total iterations of Algorithm 1. The brief expression of ∂D/∂γl is defined by ϕγl, namely ∂D/∂γl=φγl. Assume that there are two constantsAlgorithm 1: Congestion control algorithm.
1: Initialize the parametersγ,rs,ε,ε=0;2: If the packet arrive at linkl3:  calculates the value ofd¯l based on (17);4:  calculates the value ofε¯l;5:ε+=ε¯l;6:  updatesγl with ∑s∈Slrs and d¯l;7: For each sources8:  collectsγl of all the links on the path L(s);9:  calculatesrs based on (12);10: update processes ends until vectorγ remains unchanged.Gmax and ε¯max=ε¯l∀l∈Ls are the upper bounds of cl−∑s∈Slrs and εl, respectively.To simplify the representations, we use the notationsF· and Q· to denote the total primal and dual functions. Also, both primal and dual functions of each link l are denoted by frs=Ursandqγl=Urs+∑l∈Lsγl⋅φγl respectively. According to the above definitions, we can create two relations: Fr=∑s∈SfrsandQγ=∑s∈Sqγl. Through analysing Algorithm 1, we can obtain the following results.Lemma 1.
Jointly considering two constants,Gmax and ε¯max, the upper bound of ϕ(γ) is given by
(18)φγl≤Gmaxη,where η=1−K/−lnε+Gmaxε¯max.Proof.
According to the expression of∂D/∂γ1,
(19)∂D∂γ1=φγl≤Gmax−Kd¯l.
Substitutingd¯l for the relation (17), we can obtain
(20)φγl≤Gmax−K−lnε/Gmax+εl.
Reorganize inequality to get(21)φγl≤Gmax1−K−lnε+Gmaxεl.
Based on the formεl=∑l=sH1ε¯l/Hl, it is easy to get εl≤∑l=sH1ε¯max/Hl=ε¯max. Combining the form (21), the inequality can be modified as
(22)φγl≤Gmax1−K−lnε+Gmaxε¯max.
For each single-hop transmission, inequalitydl≤d¯l holds, we can get 1≤(K/−lnε+Gmaxε¯max and the right side of inequality (22) is greater than 0. Jointly considering inequality (5) and η=1−(K/−lnε+Gmaxε¯max, the result (18) in Lemma 1 is proved.To obtain the difference between primal and dual functions, letΦ be a convex hull of all feasible transmission rates, rl∈Φ.Theorem 2.
If a feasible delay bound setd¯l∣∀l∈Ls exists for all traffics, the total differences between average dual value and optimal primal value with considering the result derived in Lemma 1 can be given as
(23)Fr∗≥Q^γ−Sγ1022Nβ+βGmax2η22,where γ0=maxl∈Lγl0andSis the number of all sources.Proof.
Based on the concavity of the local gain functionfrl,pl, the following inequality holds
(24)frs∗≥frsn=frln−γln⋅φrln+γln⋅φrln,where Yn refers to the value of Y at nth iteration. Using the relation between the primal and dual functions in (8) and the convexity of the dual function, (24) can be modified as
(25)frs∗≥qγln+γln⋅φr1n.
Summing all the terms from 0 toN−1 and divided by 1/N can get
(26)frs∗≥1N∑n=0N−1qγln+1N∑n=0N−1γ1n⋅φr1n.
Because the value offrs∗ is constant, the left side of inequality remain unchanged. Given the iterative relation of the dual multiplier γln in (13), we have
(27)γln+12≤γln2+2βγln⋅φr1n+β2φrln2,which implies that
(28)γln⋅φrln≥γln+12−γln22β−βφrln22.
Combining the result in Lemma1, we can obtain
(29)1N∑n=0N−1γln⋅φrln≥γlN2−γl022Nβ−gbGmax2η22.
Combining (26) and (29), it follows that
(30)frs∗≥1N∑n=0N−1qγln+1N∑n=0N−1γln⋅φrln≥q^γln+γlN2−γl022Nβ−βGmax2η22.
IfN approaches an enormous number, from (13) we can see that λlN≪λl0, and (30) has a new form
(31)frs∗≥q^γln−γl022Nβ−βGmax2η22.
Taking the total gains for all sourcesS(32)∑s∈Sfrs∗≥∑s∈Sq^γln−γl022Nβ−βGmax2η22.
Referring to the preceding definitions, we have(33)Fr∗≥Q^γl−Sγl022Nβ−βGmax2η22.
If we letγ0=maxl∈Lγl0, the final result can be concluded.


## 5. Analysis of the Experiment Result

In this paper, we use OMNET++5.0 to simulate the network scenario. In the initialization phase, nodes are distributed randomly and uniformly in an area of1000m×1000m×80m and move with a random way-point mobility model [28]. The transmission radius of each UAV is 250 m, and the value of delay constraint for each session is set to 0.02 s. The sources can generate at most 25 packets per second, and the size of each packet is K=20Kb. In addition, we use the Rayleigh model to simulate wireless channel and estimate the link quality, respectively. The detailed definitions of simulation parameters can be found in Table 2. We compare the proposed method with delay-constrained congestion control (DCCC) algorithm proposed in [10] and delay-constrained utility maximization (DCUM) in [12]. To get more accurate results, we perform the experiment twenty times for each parameter under the same network configuration, and the final results are collected by calculating the mean values based on the twenty groups of results.Table 2
Simulation parameters.
ParametersValueArea size1000m×1000m×80mThe number of UAVs(40,70)The number of sources(3, 6)Transmission radius250 mDelay threshold0.02 sPacket generation rate at sourcesAt most 25 packets/sPacket size20 KbPower level0.37 WChannel modelRayleigh modelSimulation time400 sBefore comparing with other similar algorithms, it is interesting to get an intuitive view on the relationship between the estimated delaydl in (1) and the single-hop delay bound calculated in (17). If the aggregated rates over the links are constant, we obtain the delay bound d¯l and estimated delay dl with different values of ε. Upon the structure of equation (16), we can see that there is an inverse proportion between ε and d¯l; hence, the values of d¯l decrease with the increasing of ε; the results are displayed in Figure 2. This work aims at controlling the congestion level of entire network with the satisfaction of end-to-end delay constraint. Thus, the aggregated rates over the links are the main optimization objectives and different sizes of which impact on the amount of delay for single-hop transmission. Assume that the number of average hops travelled by each packet is defined as 7 and the size of ε sets to 0.08, we can obtain the results as shown in Figure 3. The purple dotted line denotes that the total delay threshold Is is assigned equally to each link on path Ls, and other two lines denote the trends of variables dl and d¯l. From Figure 3, we can see that the sizes of dl and d¯l are proportional to the aggregated rate ∑s∈Slrs; the results fit in with the expressions (1) and (17). With the increasing of the aggregated rate ∑s∈Slrs, the sizes of dl and d¯l gradually approach the average delay bound d¯linit.Figure 2
The comparison ofd¯l and dl with the different values of ε and invariant aggregated rate.Figure 3
The comparison ofd¯l and dl with the different values of aggregated rate and fixed ε.Therefore, we need to limit the size of∑s∈Slrs to avoid the sum of single-hop delay dl along the path Ls exceeding the threshold Is.The delay constraint condition is an important factor to be considered in the design process of proposed optimization algorithm. Hence, each iteration at relay nodes not only considers the different network metrics but also takes attention to the delay requirement. If a node has received the packet correctly, it estimates the one-hop delaydl for its neighbors according to (1) and adjusts local delay bound d¯l with a given ε and current aggregated rate. DCCC and DCUM differ from our method; both methods only optimize an end-to-end delay without considering the dynamics in link status as in the proposed method. From Figure 4, it is noted that the value of the time-out ratio increases with faster speeds in three methods; the reason is that fast movement causes worse link quality, which introduces more retransmissions and delays. More nodes in the network can provide more chances for each relay node to make a wise transmitting decision. Hence, the time-out ratio decreases with the increasing number of nodes, as in Figure 5.Figure 4
Packet time-out rate under different speeds.Figure 5
Packet time-out rate under the number of UAVs.For adapting to the changes in network topology, we estimate the delay bound (17) with delay-outage model (16) for single-hop transmissions and use the delay bound as a single-hop constraint to optimize the congestion level of end-to-end transmission. Different from our method, DCCC and DCUM optimize the aggregated rate with an end-to-end mode, which is not suitable for FANETs. The time-varying link status in FANETs will cause the algorithm in DCCC and DCUM to obtain suboptimal network utility with inaccurate delay information and create more delays in transmitting packets. Depending on the above analysis, we can infer that the average end-to-end delay in the proposed method is less than in DCCC and DCUM. Therefore, the destination will receive more packets within delay constraint in our work. We can conclude that the average throughput achieved by the proposed method is greater than by DCCC and DCUM. Because the throughput is opposite to the total delay, faster speed is accompanied by smaller throughput and more nodes generate greater throughput as shown in Figures 6 and 7.Figure 6
Average throughput under different number of speeds.Figure 7
Average throughput under different number of nodes.


## 6. Conclusion

This work presents a distributed delay-aware congestion control algorithm for FANETs by using the Lagrange dual method, which can improve network throughput and limit the end-to-end delay to a given threshold. Specifically, the framework of network utility maximization is used as the mathematical form of primal problem. Further, the single-hop delay is estimated with delay-outage model to decouple the end-to-end delay constraint, which is combined with dual technique to solve the optimization problem in a distributed way. The simulation results demonstrate that the proposed algorithm significantly improves network throughput and effectively reduces packet time-out rate. Note that some open issues still exist, such as the link connectivity problem and the void region problem. In the future, more effort will be made to consider these problems and relevant techniques in the optimization framework and transmission strategy.



---

*Source: 8811840-2020-09-21.xml*