# UAV-Assisted Data Dissemination in Delay-Constrained VANETs

Authors: Xiying Fan; Chuanhe Huang; Bin Fu; Shaojie Wen; Xi Chen
Journal: Mobile Information Systems
 (2018)

---

## Abstract

Due to the high mobility of vehicles, the frequent path failures caused by dynamic network topology, and a variety of obstructions, efficient data dissemination with delay constraint in vehicular ad hoc networks (VANETs) is a challenging issue. To address these problems, a novel mobile relaying technique by employing unmanned aerial vehicles (UAVs) is considered to facilitate data dissemination in vehicular environments where the communication infrastructures are not available or the network connectivity is poor. This paper studies and formulates the throughput maximization problem in UAV-assisted VANETs, which aims to achieve high throughput while guarantee the delay constraint of data flows to the vehicles in the area. To maximize the network throughput, the maximization problem tries to find an optimal delivery strategy for data dissemination by optimizing the transmission rate. To solve the problem, the knapsack problem can be reduced to the maximization problem, which is proved NP-hard. A polynomial time approximation scheme is proposed to achieve an approximate solution. Detailed theoretical analysis including time complexity and approximation ratio of the proposed algorithm is presented. Simulation results demonstrate the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

As important components of Intelligent Transportation System (ITS), vehicular ad hoc networks (VANETs) are large-scale mobile ad hoc networks composed of vehicles with communication functions and roadside infrastructures, which aim to provide services for autonomous driving and high-speed information sharing [1, 2]. In VANETs, drivers mainly obtain real-time road conditions and safety information sent by other vehicles through wireless communication technology. In this way, traffic accidents and road congestion can be effectively avoided while travel time and energy consumption can be reduced. Meanwhile, VANETs can provide information services, such as news and entertainment, which can add fun to the boring journey.However, VANETs have some unique characteristics that other ad hoc networks do not share, such as high vehicle mobility, dynamic network topology, and intermittent network connectivity. These features bring a variety of challenges to data dissemination. To deal with the issues, unmanned aerial vehicles (UAVs) can be utilized to cooperate with VANETs. Compared to traditional terrestrial wireless communications, UAV-enabled communications are significantly less affected by channel impairments such as shadowing and fading and in general possess more reliable air-to-ground channels due to higher possibility of having line-of-sight (LoS) links with ground users [3]. Additionally, in the areas where the infrastructures are difficult or too costly to install and maintain to provide ideal network coverage, UAVs can serve as a viable option, as they can collect information from an area of interest and transmit the information to ground VANETs [4, 5]. They can also act as relays to ground networks when direct multihop communications are not available.Considering the advantages of UAVs, a cooperative hybrid network framework is proposed, integrating UAVs with ground vehicles for data dissemination in VANETs. In the studied scenario, a vehicle carries a message and aims to transmit the message to a target area where exist a number of vehicles and UAVs. To complete the transmission, the message can be either transmitted over vehicle-to-vehicle (V2V) links, vehicle-to-infrastructure (V2I), or air-to-ground (A2G) communication links. To improve the performance of data dissemination, it should transmit data as much as possible in a specific period, which means to maximize the network throughput. Transmission rate and transmission delay of the links over which data is transmitted are utilized to reflect the throughput. Therefore, to achieve the maximum throughput is equivalent to maximize the sum of transmission rate of selected links on data delivery path. As there may exist more than one path from source to destination, the study aims to select a path with the maximum throughput while satisfying a predefined delay threshold.Graph theory is applied to abstract the network as a connected graph, then the well-known 0/1 knapsack problem can be reduced to the throughput maximization problem. Due to the property of transmission in VANETs, the problem is regarded as the graph knapsack problem which is one of the classical NP-complete problems [6]. Then, a polynomial time approximation algorithm for the graph knapsack problem is derived based on the approximation scheme for subset sum problem [7]. Since the throughput maximization problem can be reduced from the graph knapsack problem, the proposed approximation algorithm can be applied to the maximization problem and to obtain an end-to-end path with the maximum throughput.The main contributions of this paper are described as below.(i)
A throughput maximization problem in delay-constrained UAV-assisted VANETs is formulated, which considers the tradeoff of data transmission rate and transmission delay. Then, a multiedge graph knapsack problem is constructed based on 0/1 knapsack problem and reduced to the throughput maximization problem, which is proved to be NP-hard.(ii)
A polynomial time approximation scheme is developed for the multiedge graph knapsack problem to obtain the approximate solution. In the proposed scheme, the edges and vertices are assigned with values to indicate their weight. To select a path with the maximum weight, a trim procedure is applied to remove the unnecessary values. Theoretical analysis proves that the algorithm runs in polynomial time with a bound which is polynomial in the size of the input and1/ϵ, where ϵ denotes the approximation parameter. Additionally, the approximation ratio caused by trimming the unnecessary edges in path selection is also derived as 1+ϵ. The results can be applied to general graph knapsack problem.(iii)
An efficient data dissemination algorithm based on the approximate scheme for the graph knapsack problem is proposed to solve the throughput maximization problem. The values of edges in the graph knapsack problem correspond to the transmission rate and delay of the links. Considering the approximation in the knapsack problem, the proposed algorithm for the maximization problem has a quadratic approximation, which is the combination of the approximation to obtain the optimal transmission rate of links and the approximation to trim the unnecessary edges when selecting the path with the maximum throughput. The time complexity and approximation ratio of the proposed algorithm are also given.The remainder of the paper is organized as follows. Section2 overviews the related work. Section 3 describes system model and problem formulation. Section 4 develops a polynomial time approximation scheme for the graph knapsack problem, based on which an algorithm for the throughput maximization problem is proposed. Performance evaluation is presented in Section 5. Section 6 concludes the paper. Finally, Section 7 discusses the tradeoff between the benefit and cost of employing UAVs and gives the direction of future work.


## 2. Related Work

Lots of research has been done to achieve data dissemination with high efficiency in vehicular networks, most of which is devoted to analyzing the performance of delay, throughput and utility of data dissemination [8]. In this section, data dissemination in ground VANETs and UAV-assisted VANETs is mainly discussed.


### 2.1. Data Dissemination in Ground VANETs

Tan et al. [9] proposed an analytical model to characterize the downlink average throughput and distribution achieved for each vehicle during the sojourn time by the Markov reward model. Zhang et al. [10] proposed an analytical model to facilitate the real-time data delivery as well as delay-tolerant data delivery, in which the theoretical per-vehicle throughput was derived. Lin et al. [11] developed an analytical model that accurately characterized the maximum throughput rate performance achievable under a prescribed outage probability constraint. As the first study on reliable transmission for bulk or stream-like data in DTNs (delay tolerant networks) [12], Zeng et al. proposed a dynamic segmented network coding scheme to efficiently exploit the transmission opportunity. Xing et al. [13] formulated the multimedia scheduling problem to maximize the utility and designed a heuristic algorithm. As continuous research, the authors [14] investigated multimedia dissemination for large-scale VANETs considering the tradeoff of delivery delay, the quality of service (QoS) of delivered data, and the storage cost.As an emergent paradigm, some research work has applied SDN (Software Defined Network) to support applications in DTNs while reduce the operating costs [15] as it separates the control and data communication layers to simplify the network management. Liu et al. [16] described the application of SDN concept in VANETs and studied data scheduling problem. Nobre et al. [17] defined an architecture that adapted SDN to battlefield networking (BN), which integrated BN and SDN into dynamic and heterogeneous network-centric environments. Zacarias et al. [18] combined SDN and DTN concepts to address the needs of tactical-operational networks, which could support the diverse range of strict requirements for applications.


### 2.2. UAV-Assisted Wireless Communications

To provide wireless communications to a given geographical area, Mozaffari et al. [19] analyzed the deployment of an UAV as a flying base station and derived an analytical framework for the coverage and rate analysis for the device-to-device communication network. Then they investigated the optimal 3D deployment of multiple UAVs [20] to maximize the downlink coverage performance with a minimum transmit power. Orfanus et al. [21] utilized the self-organizing paradigm to design efficient UAV relay networks, to provide robust connections to the devices on the military field. Oubbati et al. [22] proposed a UAV-assisted routing protocol to assist data dissemination and improve the reliability of data delivery by filling the communication gap. Wang et al. [23] studied hybrid VANETs that utilized on-vehicle drones and proposed a distributed location-based routing protocol. Xiao et al. [24] employed UAVs to improve network performance against smart jammers and formulated the interaction between UAVs and jammers as an antijamming UAV relay game. Seliem et al. [25] proposed a mathematical framework to obtain the minimum drone density, which was equivalent to the maximum separation distance between two adjacent drones, to limit the worst delay of vehicle-drone packet transmissions. Shilin et al. [26] considered a drone-aided communication network model in an isolated VANET segment to enhance network connectivity. Fawaz et al. [27] developed a mathematical model that utilized drones to evaluate the impact of non-cooperative vehicles on forwarding path availability.Most of the related work did not consider maximizing the network throughput taking consideration of delay constraint in UAV-aided vehicular networks, which motivates this research.


## 2.1. Data Dissemination in Ground VANETs

Tan et al. [9] proposed an analytical model to characterize the downlink average throughput and distribution achieved for each vehicle during the sojourn time by the Markov reward model. Zhang et al. [10] proposed an analytical model to facilitate the real-time data delivery as well as delay-tolerant data delivery, in which the theoretical per-vehicle throughput was derived. Lin et al. [11] developed an analytical model that accurately characterized the maximum throughput rate performance achievable under a prescribed outage probability constraint. As the first study on reliable transmission for bulk or stream-like data in DTNs (delay tolerant networks) [12], Zeng et al. proposed a dynamic segmented network coding scheme to efficiently exploit the transmission opportunity. Xing et al. [13] formulated the multimedia scheduling problem to maximize the utility and designed a heuristic algorithm. As continuous research, the authors [14] investigated multimedia dissemination for large-scale VANETs considering the tradeoff of delivery delay, the quality of service (QoS) of delivered data, and the storage cost.As an emergent paradigm, some research work has applied SDN (Software Defined Network) to support applications in DTNs while reduce the operating costs [15] as it separates the control and data communication layers to simplify the network management. Liu et al. [16] described the application of SDN concept in VANETs and studied data scheduling problem. Nobre et al. [17] defined an architecture that adapted SDN to battlefield networking (BN), which integrated BN and SDN into dynamic and heterogeneous network-centric environments. Zacarias et al. [18] combined SDN and DTN concepts to address the needs of tactical-operational networks, which could support the diverse range of strict requirements for applications.


## 2.2. UAV-Assisted Wireless Communications

To provide wireless communications to a given geographical area, Mozaffari et al. [19] analyzed the deployment of an UAV as a flying base station and derived an analytical framework for the coverage and rate analysis for the device-to-device communication network. Then they investigated the optimal 3D deployment of multiple UAVs [20] to maximize the downlink coverage performance with a minimum transmit power. Orfanus et al. [21] utilized the self-organizing paradigm to design efficient UAV relay networks, to provide robust connections to the devices on the military field. Oubbati et al. [22] proposed a UAV-assisted routing protocol to assist data dissemination and improve the reliability of data delivery by filling the communication gap. Wang et al. [23] studied hybrid VANETs that utilized on-vehicle drones and proposed a distributed location-based routing protocol. Xiao et al. [24] employed UAVs to improve network performance against smart jammers and formulated the interaction between UAVs and jammers as an antijamming UAV relay game. Seliem et al. [25] proposed a mathematical framework to obtain the minimum drone density, which was equivalent to the maximum separation distance between two adjacent drones, to limit the worst delay of vehicle-drone packet transmissions. Shilin et al. [26] considered a drone-aided communication network model in an isolated VANET segment to enhance network connectivity. Fawaz et al. [27] developed a mathematical model that utilized drones to evaluate the impact of non-cooperative vehicles on forwarding path availability.Most of the related work did not consider maximizing the network throughput taking consideration of delay constraint in UAV-aided vehicular networks, which motivates this research.


## 3. System Model and Problem Formulation

In this section, the system model is presented while the maximization problem is formulated.


### 3.1. System Model

To improve the reliability and efficiency of data dissemination in VANETs, UAVs are employed to form a cooperative air-to-ground network. By exploiting the UAV-aided VANETs, UAVs can help ground vehicles explore the area of interest and enhance network connectivity.As stated in [22], most urban applications that use UAVs like small Quad-Copters do not fly at high altitudes [28]. Thus, this study assumes that UAVs have a low and constant altitude during the flight in order to communicate with vehicles on the ground. IEEE 802.11p MAC protocol is adopted for both V2V and A2G communications. UAVs in the network use a large transmission range (i.e., up to 1000 m [29]) and have a global view of the network. Vehicles and UAVs are equipped with GPS and digital maps to obtain their geographical positions. UAVs can also act as relay nodes to forward data packets when direct multihop V2V links are not available.The cooperative network architecture of the UAV-assisted VANETs is depicted as Figure1, which is composed of the UAV network and the ground vehicular network. The scenario includes A2G and V2V communication links, which is a hybrid mode that allows the network to apply both A2G and V2V communications for data dissemination in VANETs.Figure 1
An overview of the cooperative air-to-ground network architecture.The network can be abstracted as an edge-weighted graphGV,E (see Definition 1), where V is a set of vehicles and UAVs, E is a set of edges to indicate the communication links for data dissemination. The weight of each edge is represented by the transmission condition of the corresponding link.Definition 1. Given a weighted network graph GV,E, where V is the set of vertices and E is the set of edges. Let we,de denotes the value of edge e, where we indicates the transmission rate of e, and de indicates the transmission delay. The tuple Wi,Di denotes the value of node i∈G⋅V, where Wi and Di indicates the total transmission rate and transmission delay from source node s to i, respectively.Note thatGV,E only considers the edges over which two nodes can communicate, which means no silent edges are included.


### 3.2. Problem Formulation

Assume a packet with sizeK carried by vehicle s needs to be transmitted to a specific area. There may exist more than one end-to-end path from source node s to other nodes in V, which can be denoted by Ps and p indicates a path in Ps. It is important to note that the paths may only exist among vehicles through V2V links or they may contain a hybrid of A2G and V2V communications. For simplicity, the A2G and V2V links are considered as common links with different properties hereinafter. The differences of the links are reflected by their transmission rate and delay.As the network throughput can be mapped by the transmission rate of the end-to-end path, this study discusses how to optimize the transmission rate of each individual path to achieve the maximum throughput. To guarantee the real-time transmission, the end-to-end delay is limited to a predefined threshold. A continuous convex functionfrl=logrl with the transmission rate as parameter is utilized to depict the throughput, where l denotes a link on path p and rl denotes the transmission rate of link l. The reason to consider frl instead of rl is that the logarithmic utility function logrl can better reflect the transmission rate of the delivery path and guarantee the maximum transmission rate. Meanwhile, the logarithm is concave and, hence, has diminishing returns. Here, it seeks a utility for that naturally achieves the maximum throughput and some level of fairness among the links.To optimize the transmission rate of links and improve the network throughput, the throughput maximization problem can be formulated as below:(1)max∑l∈Lfrl⋅xl,s.t.∑l∈Ldl⋅xl≤δ,where rl∈1,cl, cl indicates the maximum capacity of link l, dl is the transmission delay of link l, and δ is the predefined delay threshold. If link l is selected, xl is equal to 1, otherwise, xl is 0. Transmission delay dl can be calculated by the following equation according to the channel model [30]:(2)dl=K/cl−rl.The problem can be stated as follows. Given a delay thresholdδ and n pairs of positive values rl,dl to indicate the transmission rate and transmission delay of link l, it aims to select a delivery path which contains a few links to maximize the transmission rate while satisfying the delay constraint. The well-known 0/1 knapsack problem can be reduced to the throughput maximization problem. Then, a polynomial time approximation scheme is proposed to solve the problem.


### 3.3. An Example

An example is given to illustrate how to derive an approximation solution for the maximization problem. An undirected graphGV,E with six vertices is shown in Figure 2. In graph G, each edge has a pair of values we,de and each node has Wi,Di as its weight. The goal is to find a path from source node s to node d, such that the path has the maximum transmission rate Wd while the transmission delay Dd does not exceed δ. The procedure to obtain the path utilizing the approximation method is described.Figure 2
An example of an undirected graphGV,E with six vertices, each edge connecting the nodes is assigned with weight we,de, which helps illustrate how to find a path from s to d.First, the weight of each edge is given aswsa,dsa, wsb,dsb, wab,dab, wac,dac, wbe,dbe, wae,dae, wce,dce, wcd,dcd, and wed,ded. The initial value of node s is 0,0 and other nodes is 0,∞. The values of the nodes are recorded, and a list of values for each node will be generated. There might be quite a few values if there are a large number of nodes. To eliminate redundant values, a trim procedure will be executed if two values in L are close to each other since there is no need to keep both of them. More accurately, a trimming parameter α is utilized such that 0<α<1. When trimming a list by α, remove as many elements as possible, in such a way if L′ is the result of trimming L, then for every element y that was removed from L, there is still an element z still in L′ that approximates y, that is,(3)y1+α≤z≤y.Through the trim procedure, the approximate valuesWd,Dd of node d can be obtained; thus, an approximate path from s to d will be achieved.Before explaining the details of the proposed scheme, a list of variables that will be used throughout this research is provided as Table1.Table 1
Variables used in this paper.
Variable
Definition
N
e
i
g
h
b
o
r
i
List of neighbors of nodei
δ
Predefined delay threshold
ϵ
A positive real number used for approximation
l
Link between two nodes
L
Set of links on the path for data delivery
r
l
Transmission rate of linkl
x
l
X
l = 1 means links l is selected otherwise not
s
Source node that carries the information
u
,
v
Nodes active in the network
W
v
Total weighted transmission rate at nodev
D
v
Total transmission delay at nodev
w
e
Weighted transmission rate of link betweenu and v
d
e
Transmission delay of linke between u and v
w
l
Weighted transmission rate of linkl, calculated by frl
d
l
Transmission delay of linkl
Y
Set of pair valuesWv,Dv of vehicle v
Y
′
Trimmed list ofWv,Dv of vehicle v
P
∗
Optimal solution of the maximization problem
P
Approximate solution of the maximization problem


## 3.1. System Model

To improve the reliability and efficiency of data dissemination in VANETs, UAVs are employed to form a cooperative air-to-ground network. By exploiting the UAV-aided VANETs, UAVs can help ground vehicles explore the area of interest and enhance network connectivity.As stated in [22], most urban applications that use UAVs like small Quad-Copters do not fly at high altitudes [28]. Thus, this study assumes that UAVs have a low and constant altitude during the flight in order to communicate with vehicles on the ground. IEEE 802.11p MAC protocol is adopted for both V2V and A2G communications. UAVs in the network use a large transmission range (i.e., up to 1000 m [29]) and have a global view of the network. Vehicles and UAVs are equipped with GPS and digital maps to obtain their geographical positions. UAVs can also act as relay nodes to forward data packets when direct multihop V2V links are not available.The cooperative network architecture of the UAV-assisted VANETs is depicted as Figure1, which is composed of the UAV network and the ground vehicular network. The scenario includes A2G and V2V communication links, which is a hybrid mode that allows the network to apply both A2G and V2V communications for data dissemination in VANETs.Figure 1
An overview of the cooperative air-to-ground network architecture.The network can be abstracted as an edge-weighted graphGV,E (see Definition 1), where V is a set of vehicles and UAVs, E is a set of edges to indicate the communication links for data dissemination. The weight of each edge is represented by the transmission condition of the corresponding link.Definition 1. Given a weighted network graph GV,E, where V is the set of vertices and E is the set of edges. Let we,de denotes the value of edge e, where we indicates the transmission rate of e, and de indicates the transmission delay. The tuple Wi,Di denotes the value of node i∈G⋅V, where Wi and Di indicates the total transmission rate and transmission delay from source node s to i, respectively.Note thatGV,E only considers the edges over which two nodes can communicate, which means no silent edges are included.


## 3.2. Problem Formulation

Assume a packet with sizeK carried by vehicle s needs to be transmitted to a specific area. There may exist more than one end-to-end path from source node s to other nodes in V, which can be denoted by Ps and p indicates a path in Ps. It is important to note that the paths may only exist among vehicles through V2V links or they may contain a hybrid of A2G and V2V communications. For simplicity, the A2G and V2V links are considered as common links with different properties hereinafter. The differences of the links are reflected by their transmission rate and delay.As the network throughput can be mapped by the transmission rate of the end-to-end path, this study discusses how to optimize the transmission rate of each individual path to achieve the maximum throughput. To guarantee the real-time transmission, the end-to-end delay is limited to a predefined threshold. A continuous convex functionfrl=logrl with the transmission rate as parameter is utilized to depict the throughput, where l denotes a link on path p and rl denotes the transmission rate of link l. The reason to consider frl instead of rl is that the logarithmic utility function logrl can better reflect the transmission rate of the delivery path and guarantee the maximum transmission rate. Meanwhile, the logarithm is concave and, hence, has diminishing returns. Here, it seeks a utility for that naturally achieves the maximum throughput and some level of fairness among the links.To optimize the transmission rate of links and improve the network throughput, the throughput maximization problem can be formulated as below:(1)max∑l∈Lfrl⋅xl,s.t.∑l∈Ldl⋅xl≤δ,where rl∈1,cl, cl indicates the maximum capacity of link l, dl is the transmission delay of link l, and δ is the predefined delay threshold. If link l is selected, xl is equal to 1, otherwise, xl is 0. Transmission delay dl can be calculated by the following equation according to the channel model [30]:(2)dl=K/cl−rl.The problem can be stated as follows. Given a delay thresholdδ and n pairs of positive values rl,dl to indicate the transmission rate and transmission delay of link l, it aims to select a delivery path which contains a few links to maximize the transmission rate while satisfying the delay constraint. The well-known 0/1 knapsack problem can be reduced to the throughput maximization problem. Then, a polynomial time approximation scheme is proposed to solve the problem.


## 3.3. An Example

An example is given to illustrate how to derive an approximation solution for the maximization problem. An undirected graphGV,E with six vertices is shown in Figure 2. In graph G, each edge has a pair of values we,de and each node has Wi,Di as its weight. The goal is to find a path from source node s to node d, such that the path has the maximum transmission rate Wd while the transmission delay Dd does not exceed δ. The procedure to obtain the path utilizing the approximation method is described.Figure 2
An example of an undirected graphGV,E with six vertices, each edge connecting the nodes is assigned with weight we,de, which helps illustrate how to find a path from s to d.First, the weight of each edge is given aswsa,dsa, wsb,dsb, wab,dab, wac,dac, wbe,dbe, wae,dae, wce,dce, wcd,dcd, and wed,ded. The initial value of node s is 0,0 and other nodes is 0,∞. The values of the nodes are recorded, and a list of values for each node will be generated. There might be quite a few values if there are a large number of nodes. To eliminate redundant values, a trim procedure will be executed if two values in L are close to each other since there is no need to keep both of them. More accurately, a trimming parameter α is utilized such that 0<α<1. When trimming a list by α, remove as many elements as possible, in such a way if L′ is the result of trimming L, then for every element y that was removed from L, there is still an element z still in L′ that approximates y, that is,(3)y1+α≤z≤y.Through the trim procedure, the approximate valuesWd,Dd of node d can be obtained; thus, an approximate path from s to d will be achieved.Before explaining the details of the proposed scheme, a list of variables that will be used throughout this research is provided as Table1.Table 1
Variables used in this paper.
Variable
Definition
N
e
i
g
h
b
o
r
i
List of neighbors of nodei
δ
Predefined delay threshold
ϵ
A positive real number used for approximation
l
Link between two nodes
L
Set of links on the path for data delivery
r
l
Transmission rate of linkl
x
l
X
l = 1 means links l is selected otherwise not
s
Source node that carries the information
u
,
v
Nodes active in the network
W
v
Total weighted transmission rate at nodev
D
v
Total transmission delay at nodev
w
e
Weighted transmission rate of link betweenu and v
d
e
Transmission delay of linke between u and v
w
l
Weighted transmission rate of linkl, calculated by frl
d
l
Transmission delay of linkl
Y
Set of pair valuesWv,Dv of vehicle v
Y
′
Trimmed list ofWv,Dv of vehicle v
P
∗
Optimal solution of the maximization problem
P
Approximate solution of the maximization problem


## 4. Proposed Solution

In this section, the knapsack problem is reduced to the throughput maximization problem first. Then, a polynomial time approximation scheme is proposed to solve the graph knapsack problem, which can return an approximate solution. Finally, a throughput maximization algorithm is presented based on the approximate scheme for graph knapsack. The approximation ratio and the running time of the proposed algorithm are also analyzed.


### 4.1. Problem Reduction

To maximize the network throughput, this study optimizes the transmission raterl while the sum of dl does not exceed δ is satisfied. The relation between the transmission rate rl and transmission delay dl is presented as dl=K/cl−rl, subject to ∑l∈Ldl≤δ. From the equation, it can be seen that the transmission delay dl will increase when rl increases. There should exist an optimal transmission rate rl∗ with corresponding dl∗, so the selected path could achieve the maximum throughput while the total delay is within delay constraint. To reduce the complexity of obtaining the optimal values, the approximate values for rl, dl are derived.According to the equationdl=K/cl−rl, rl=cl−K/dl holds. When rl⟶1, dl has the minimum value, that is dl⟶K/cl−1. Hence, the range of dl is K/cl−1,δ, while the range of rl is 1,cl. To achieve the approximate values of rl and dl, let rl increase 1+ϵ each time until it reaches the largest value, where 0<ϵ<1 is the parameter used for approximation. Then a list of values for rl is obtained, which is shown as 1,1+ϵ,1+ϵ2,⋯,1+ϵt. According to 1+ϵt≤cl, it has t≤log1+ϵcl, and t is the largest integer satisfying the inequality, which means 1+ϵt+1>cl. dl may have different values according to different rl calculated by dl=K/cl−rl, satisfying the condition that dl∈K/cl−1,δ. Therefore, t pairs of rl,dl can be derived. After frl, t pairs of corresponding values wl,dl are generated. Consequently, the approximation ratio to obtain the approximate value of rl is 1+ϵ.Different pairs of values for each link can be treated as different weights of corresponding edges between two nodes. Accordingly, there may exist multiple edges between two nodes. Then Definition 2 is described.Definition 2. Given a weighted graph GV,E, there may exist multiple tuples of values for each edge, which can be treated that there are multiple edges with different values between the corresponding nodes. Accordingly, GV,E becomes a multiedge-weighted graph.As each link is represented by an edge ofGV,E, the graph knapsack problem can be reduced to the throughput maximization problem. The study aims to select a set of links over which the maximum throughput can be achieved while the delay constraint is satisfied.


### 4.2. Approximation Scheme for the Graph Knapsack Problem

As there may exist more than one path from source nodes to node i, node i could have different pairs of weighted values Wi,Di. Let Y denote the set of values. Assume Y is sorted into monotonically increasing order of Wi. A procedure trim (see Algorithm 1) is designed to remove unnecessary values of node i, based on the idea of approximation. The procedure scans the elements of Y in monotonically increasing order. An element is appended onto the returned list Y′ only if it is the first element of Y or if it cannot be represented by the most recent values placed into Y′. The output of the procedure trim described as Algorithm 1 is a trimmed, sorted list.Algorithm 1: Trim (Y,δ,ϵ).
Input: Y: a list of Wi,Di,∀i∈V;
δ: the predefined delay threshold;
ϵ: a real number
Output: Y′: a trimmed list of Y(1)
LetY′ be empty;(2)
Remove every tupleW,D in Y with D>δ;(3)
Partition the tuples ofY into A1,⋯,At such that for every two tuples W,D,W′,D′, in the same As, they satisfy W≤1+ϵ/2nW′ and W′≤1+ϵ/2nW;(4)
for i=1 to tdo(5)
Select one tupleW,D from Ai with the least D;(6)
AppendW,D to Y′;(7)
end for(8)
return Y′Given the trim procedure, a polynomial time approximation scheme can be constructed for the graph knapsack problem, which is described as Algorithm2. The approximation procedure takes as input a set of values for node u, Q=Wu1,Du1,Wu2,Du2,⋯,Wun,Dun (in arbitrary order), the delay threshold δ, and the approximation parameter ϵ. Algorithm 2 calls Algorithm 1 to trim the input list. An approximate solution denoted by P within a 1+ϵ factor of the optimal solution will be returned by the scheme. Lemma 1 is developed to prove that the proposed scheme runs in polynomial time. Meanwhile, Theorem 1 is derived to show that there is a polynomial time approximation algorithm for the multiedge graph knapsack problem.Algorithm 2: Polynomial time approximation scheme for graph knapsack.
Input: Q: a list of Wu,Du for node u, every u∈G.V;
δ: the predefined delay threshold
Output: approximation solution P(1)
INITIALIZEGV,E, set up the value of we,de for corresponding link;(2)
LetYu=∅ for every u∈G.V;(3)
for i=1 to G⋅V - 1 do(4)
for each edge e=u,v∈G⋅E do(5)
for each Wu,Du∈Yu do(6)
CalculateWv,Dv = Wu,Du + we,de;(7)
AddWv,Dv to Yv;(8)
end for(9)
Trim(Yv);(10)
end for(11)
end for(12)
returnP, which contains the set of links selectedLemma 1.
The algorithm for the multiedge graph knapsack problem runs inO3n2mlnW∗/ϵ time, where m, n denotes the number of edges and vertices of graph G, respectively.Proof.
It will show that the running time of the proposed scheme is polynomial in both1/ϵ and the size of the input. The first part of the algorithm runs in time Onm, since the initialization in line 1 takes Θn time, each of the V−1 passing over the edges takes Θm time, where n=V,m=E.
Now the running time of trim process will be analyzed. AssumeW∗ is the optimal weighted transmission rate of link l and y.W<y.W∗. After trimming, successive elements y and Y′ of Y have the relationship Y′.W/y.W>1+ϵ/2n; that is, they differ by a factor of at least 1+ϵ/2n. Thus, each list contains possibly the value 1 and up to log1+ϵ/2nW∗ values. It can be deduced that the number of elements in each list Y is at most(4)log1+ϵ/2nW∗+1=lnW∗ln1+ϵ/2n+1≤2n1+ϵ/2nlnW∗ϵ+1<3nlnW∗ϵ+1.
In summary, the overall running time of the algorithm isO3n2mlnW∗/ϵ. This bound is polynomial in the size of the input n and 1/ϵ.Theorem 1.
The proposed algorithm for the multiedge graph knapsack problem is a polynomial time approximation scheme with an approximation ratio1+ϵ.Proof.
LetP∗ denote the optimal solution of the problem. From the proposed scheme, it is easily seen that P≤P∗. It needs to show that P∗/P≤1+ϵ.
After trimming, successive tuples y andy′ of Y′ have the relationship y⋅W/y⋅W>1+ϵ/2n, where n indicates the number of nodes in G. Scan all the edges, find the path from source node s to destination node u, and let v1v2⋯vt denote the path, s=v1,u=vt. Due to the trim process executed at the receiver node of each edge, there exists a 1+ϵ/2n factor approximation.
As tovi, there are i−1 edges between s to vi; therefore, the approximation ratio should be 1+ϵ/2ni−1. Then, vi reaches vi+1 through edge vivi+1, the approximation ratio at vi after trimming should be 1+ϵ/2ni−1⋅1+ϵ/2n, which is equal to 1+ϵ/2ni. Since there are totally n nodes, the number of edges on the path is at most n−1. From the induction of the above procedure, an overall approximation ratio can be expressed as 1+ϵ/2nn−1, which can be presented as below:(5)P∗/P≤1+ϵ/2nn−1.
Now, it needs to show thatP∗/P≤1+ϵ, by proving(6)1+ϵ/2nn−1≤1+ϵ.
Sincelimn⟶∞1+x/nn=ex, the equation limn⟶∞1+ϵ/2nn−1=eϵ/2 holds. Since d/dn1+ϵ/2nn−1>0, function 1+ϵ/2nn−1 is monotonically increasing, which means the function increases with n as it approaches the limit eϵ/2. Thus, the following inequality stands:(7)1+ϵ/2nn−1≤eϵ/2≤1+ϵ/2+ϵ/22≤1+ϵ.
Combine withP∗/P≤1+ϵ/2nn−1, it has(8)P∗/P≤1+ϵ,and the analysis of the approximation ratio is completes.
Combined with Lemma 1, it proves that the proposed scheme is a polynomial time approximation scheme.


### 4.3. Proposed Algorithm for Throughput Maximization Problem

As the graph knapsack problem is reduced to the throughput maximization problem, a throughput maximization algorithm is proposed based on the approximation scheme for the graph knapsack problem in this section.Givenn items, the ith item is worth wi and di pounds in weight. The 0/1 knapsack problem aims to find a subset of items that the total value is maximum while the total weight is limited to a value. Assume that di is at most δ and the items are indexed in monotonically increasing order of their values, that is, w1≤w2≤⋯≤wn. Theorem 2 is derived to show that the throughput maximization problem with delay constraint is NP-hard.Theorem 2.
The throughput maximization problem is NP-hard.Proof. Reduce the 0/1 knapsack problem to the throughput maximization problem. Consider Q is a list of n items, denoted by v1,v2,⋯,vn, with corresponding values w1,d1,w2,d2,⋯,wn,dn, where wi,di indicates the value of the ith item.Construct a graphGV,E with V=s,t,v1,⋯,vn, where s and t denote the source node and destination node, respectively. For every node vi∈V, there is a pair of values wi,di for every edge v,vi that goes from v to vi for any v≠vi and v≠t. There is a pair of values 0,0, for every edge v,t that goes from v to t for any v≠s and v≠t. The knapsack problem aims to select a subset U⊆v1,v2,⋯,vn of items such that ∑vi∈Uwi is maximized and the total weight ∑vi∈Udi≤δ. A subset U is a feasible solution for the knapsack problem if and only if there is a path that goes from s to the vertex vi with vi∈U and then to t. It is easy to see that the time of construction is in polynomial time.Select items satisfying the required conditions and add them to the knapsack, which is also the way to select the path for the problem. Therefore, if there exists a solution for the knapsack problem, the maximization problem can be solved. Vice Versa, existence of a solution to the maximization problem means there is a solution to the knapsack problem. Thus, the maximization problem is NP-hard.After reducing the graph knapsack problem to the throughput maximization problem, a Throughput Maximization algoRithm (TMR) is proposed based on Algorithm2, shown as Algorithm 3. Assume source node s intends to disseminate information to a specific area, an approximate delivery path is desired to achieve the maximum throughput and satisfy the delay constraint.To be more clearer, a detailed description on how the proposed TMR works on the throughput maximization problem to solve the path-finding issue is presented as follows.In the initialization process, letNv represent a set of v's neighbors. Starting from source node s, execute the following steps to each edge e∈G⋅E.(1)
To find the neighbor vehiclesNv for node v, exchange information and obtain the corresponding values WNi,DNi of the neighbors.(2)
To obtain the links connecting node v with its neighbors, calculate the channel capacitycl according to the channel condition. Then, get the transmission rate and delay of the corresponding link. Calculate Wv,Dv∈Yv for v by adding the value of its neighbor u, Wu,Du with we,de of the corresponding link e. Therefore, a list Yv for v can be achieved.(3)
According to the previous step, several pairs of valuesWv,Dv may exist for node v. First, remove the values with delay that are larger than the delay threshold δ. Then, if there are values with the same delay, keep those with larger transmission rate. Also, remove the values with larger delay and smaller transmission rate. In the following case, such as Yvi∈Yv with values of Wvi,Dvi, Yvj∈Yv with Wvj,Dvj, if Wvi>Wvj and Dvi>Dvj, which means item Yvi is with larger transmission rate but also with larger delay compared with Yvj, a trim procedure will be executed to determine whether to remove an element. If Wvi>1+ϵ/2n⋅Wvj, append Yvi onto list Y′; otherwise, remove Yvi and append Yvj onto list Y′.After the iterative operations, paths containing a set of selected links are obtained. If there are more than one path from the source to the destination, choose the one with the largest transmission rate, which is the approximate solution intended to achieve for data delivery.Theorem 3 is presented to show that the proposed TMR is a polynomial approximation algorithm with an approximation ratio of1+γ, where 0<γ<1.Algorithm 3: Throughput Maximization Algorithm.
Input: A list V containing all the vehicles and UAVs in the network
Output: The selected path(1)
LetNv denote the neighbor of node v;(2)
a=0, which denotes the number of executions;(3)
for each node v do(4)
Send a request to its neighbors;(5)
Receive the channel information (CI) from its neighbors;(6)
Calculatecl according to CI;(7)
Calculate the approximate values ofrl and dl according to dl=K/cl−rl;(8)
Obtain the transmission rate and delay of the link between each neighbor and nodev, denoted as we,de;(9)
end for(10)
repeat(11)
Calculate the transmission rate and delay for each nodev in the network, by adding the neighbor’s corresponding values to we,de, denoted as Wv,Dv;(12)
Apply the trim procedure to remove unnecessary values of nodev;(13)
a=a+1;(14)
until a=G⋅V−1(15)
return A path containing a set of selected linksTheorem 3.
The throughput maximization algorithm can achieve an approximation ratio1+γ within running time On2mlnC/γ, where m denotes the number of edges, C=∑i=1mci, ci indicates the transmission capacity of link i.Proof.
The input of the proposed maximization algorithm iswl,dl. As stated in 4.1, the value of wl,dl is within a 1+ϵ factor approximation of the optimal value. Considering the approximation in the multiedge knapsack problem, the throughput maximization problem should have a quadratic approximation. According to theorem 1, the comprehensive approximation ratio is(9)1+ϵ2=1+2ϵ+ϵ2.
Assumeγ=ϵ/3, the inequality 1+ϵ2=1+2ϵ+ϵ2<1+γ holds.
Hence, an approximation solution within a1+γ factor of the optimal solution can be achieved.
Asrl∈1,cl, assume there are m edges on the path. Let C=∑i∈mci, then ∀ y∈m,C. From Lemma 1, it has(10)log1+ϵ/2nC+1<3nlnCϵ+1=nlnCγ+1.
Therefore, the total running time isOn2mlnC/γ.


## 4.1. Problem Reduction

To maximize the network throughput, this study optimizes the transmission raterl while the sum of dl does not exceed δ is satisfied. The relation between the transmission rate rl and transmission delay dl is presented as dl=K/cl−rl, subject to ∑l∈Ldl≤δ. From the equation, it can be seen that the transmission delay dl will increase when rl increases. There should exist an optimal transmission rate rl∗ with corresponding dl∗, so the selected path could achieve the maximum throughput while the total delay is within delay constraint. To reduce the complexity of obtaining the optimal values, the approximate values for rl, dl are derived.According to the equationdl=K/cl−rl, rl=cl−K/dl holds. When rl⟶1, dl has the minimum value, that is dl⟶K/cl−1. Hence, the range of dl is K/cl−1,δ, while the range of rl is 1,cl. To achieve the approximate values of rl and dl, let rl increase 1+ϵ each time until it reaches the largest value, where 0<ϵ<1 is the parameter used for approximation. Then a list of values for rl is obtained, which is shown as 1,1+ϵ,1+ϵ2,⋯,1+ϵt. According to 1+ϵt≤cl, it has t≤log1+ϵcl, and t is the largest integer satisfying the inequality, which means 1+ϵt+1>cl. dl may have different values according to different rl calculated by dl=K/cl−rl, satisfying the condition that dl∈K/cl−1,δ. Therefore, t pairs of rl,dl can be derived. After frl, t pairs of corresponding values wl,dl are generated. Consequently, the approximation ratio to obtain the approximate value of rl is 1+ϵ.Different pairs of values for each link can be treated as different weights of corresponding edges between two nodes. Accordingly, there may exist multiple edges between two nodes. Then Definition 2 is described.Definition 2. Given a weighted graph GV,E, there may exist multiple tuples of values for each edge, which can be treated that there are multiple edges with different values between the corresponding nodes. Accordingly, GV,E becomes a multiedge-weighted graph.As each link is represented by an edge ofGV,E, the graph knapsack problem can be reduced to the throughput maximization problem. The study aims to select a set of links over which the maximum throughput can be achieved while the delay constraint is satisfied.


## 4.2. Approximation Scheme for the Graph Knapsack Problem

As there may exist more than one path from source nodes to node i, node i could have different pairs of weighted values Wi,Di. Let Y denote the set of values. Assume Y is sorted into monotonically increasing order of Wi. A procedure trim (see Algorithm 1) is designed to remove unnecessary values of node i, based on the idea of approximation. The procedure scans the elements of Y in monotonically increasing order. An element is appended onto the returned list Y′ only if it is the first element of Y or if it cannot be represented by the most recent values placed into Y′. The output of the procedure trim described as Algorithm 1 is a trimmed, sorted list.Algorithm 1: Trim (Y,δ,ϵ).
Input: Y: a list of Wi,Di,∀i∈V;
δ: the predefined delay threshold;
ϵ: a real number
Output: Y′: a trimmed list of Y(1)
LetY′ be empty;(2)
Remove every tupleW,D in Y with D>δ;(3)
Partition the tuples ofY into A1,⋯,At such that for every two tuples W,D,W′,D′, in the same As, they satisfy W≤1+ϵ/2nW′ and W′≤1+ϵ/2nW;(4)
for i=1 to tdo(5)
Select one tupleW,D from Ai with the least D;(6)
AppendW,D to Y′;(7)
end for(8)
return Y′Given the trim procedure, a polynomial time approximation scheme can be constructed for the graph knapsack problem, which is described as Algorithm2. The approximation procedure takes as input a set of values for node u, Q=Wu1,Du1,Wu2,Du2,⋯,Wun,Dun (in arbitrary order), the delay threshold δ, and the approximation parameter ϵ. Algorithm 2 calls Algorithm 1 to trim the input list. An approximate solution denoted by P within a 1+ϵ factor of the optimal solution will be returned by the scheme. Lemma 1 is developed to prove that the proposed scheme runs in polynomial time. Meanwhile, Theorem 1 is derived to show that there is a polynomial time approximation algorithm for the multiedge graph knapsack problem.Algorithm 2: Polynomial time approximation scheme for graph knapsack.
Input: Q: a list of Wu,Du for node u, every u∈G.V;
δ: the predefined delay threshold
Output: approximation solution P(1)
INITIALIZEGV,E, set up the value of we,de for corresponding link;(2)
LetYu=∅ for every u∈G.V;(3)
for i=1 to G⋅V - 1 do(4)
for each edge e=u,v∈G⋅E do(5)
for each Wu,Du∈Yu do(6)
CalculateWv,Dv = Wu,Du + we,de;(7)
AddWv,Dv to Yv;(8)
end for(9)
Trim(Yv);(10)
end for(11)
end for(12)
returnP, which contains the set of links selectedLemma 1.
The algorithm for the multiedge graph knapsack problem runs inO3n2mlnW∗/ϵ time, where m, n denotes the number of edges and vertices of graph G, respectively.Proof.
It will show that the running time of the proposed scheme is polynomial in both1/ϵ and the size of the input. The first part of the algorithm runs in time Onm, since the initialization in line 1 takes Θn time, each of the V−1 passing over the edges takes Θm time, where n=V,m=E.
Now the running time of trim process will be analyzed. AssumeW∗ is the optimal weighted transmission rate of link l and y.W<y.W∗. After trimming, successive elements y and Y′ of Y have the relationship Y′.W/y.W>1+ϵ/2n; that is, they differ by a factor of at least 1+ϵ/2n. Thus, each list contains possibly the value 1 and up to log1+ϵ/2nW∗ values. It can be deduced that the number of elements in each list Y is at most(4)log1+ϵ/2nW∗+1=lnW∗ln1+ϵ/2n+1≤2n1+ϵ/2nlnW∗ϵ+1<3nlnW∗ϵ+1.
In summary, the overall running time of the algorithm isO3n2mlnW∗/ϵ. This bound is polynomial in the size of the input n and 1/ϵ.Theorem 1.
The proposed algorithm for the multiedge graph knapsack problem is a polynomial time approximation scheme with an approximation ratio1+ϵ.Proof.
LetP∗ denote the optimal solution of the problem. From the proposed scheme, it is easily seen that P≤P∗. It needs to show that P∗/P≤1+ϵ.
After trimming, successive tuples y andy′ of Y′ have the relationship y⋅W/y⋅W>1+ϵ/2n, where n indicates the number of nodes in G. Scan all the edges, find the path from source node s to destination node u, and let v1v2⋯vt denote the path, s=v1,u=vt. Due to the trim process executed at the receiver node of each edge, there exists a 1+ϵ/2n factor approximation.
As tovi, there are i−1 edges between s to vi; therefore, the approximation ratio should be 1+ϵ/2ni−1. Then, vi reaches vi+1 through edge vivi+1, the approximation ratio at vi after trimming should be 1+ϵ/2ni−1⋅1+ϵ/2n, which is equal to 1+ϵ/2ni. Since there are totally n nodes, the number of edges on the path is at most n−1. From the induction of the above procedure, an overall approximation ratio can be expressed as 1+ϵ/2nn−1, which can be presented as below:(5)P∗/P≤1+ϵ/2nn−1.
Now, it needs to show thatP∗/P≤1+ϵ, by proving(6)1+ϵ/2nn−1≤1+ϵ.
Sincelimn⟶∞1+x/nn=ex, the equation limn⟶∞1+ϵ/2nn−1=eϵ/2 holds. Since d/dn1+ϵ/2nn−1>0, function 1+ϵ/2nn−1 is monotonically increasing, which means the function increases with n as it approaches the limit eϵ/2. Thus, the following inequality stands:(7)1+ϵ/2nn−1≤eϵ/2≤1+ϵ/2+ϵ/22≤1+ϵ.
Combine withP∗/P≤1+ϵ/2nn−1, it has(8)P∗/P≤1+ϵ,and the analysis of the approximation ratio is completes.
Combined with Lemma 1, it proves that the proposed scheme is a polynomial time approximation scheme.


## 4.3. Proposed Algorithm for Throughput Maximization Problem

As the graph knapsack problem is reduced to the throughput maximization problem, a throughput maximization algorithm is proposed based on the approximation scheme for the graph knapsack problem in this section.Givenn items, the ith item is worth wi and di pounds in weight. The 0/1 knapsack problem aims to find a subset of items that the total value is maximum while the total weight is limited to a value. Assume that di is at most δ and the items are indexed in monotonically increasing order of their values, that is, w1≤w2≤⋯≤wn. Theorem 2 is derived to show that the throughput maximization problem with delay constraint is NP-hard.Theorem 2.
The throughput maximization problem is NP-hard.Proof. Reduce the 0/1 knapsack problem to the throughput maximization problem. Consider Q is a list of n items, denoted by v1,v2,⋯,vn, with corresponding values w1,d1,w2,d2,⋯,wn,dn, where wi,di indicates the value of the ith item.Construct a graphGV,E with V=s,t,v1,⋯,vn, where s and t denote the source node and destination node, respectively. For every node vi∈V, there is a pair of values wi,di for every edge v,vi that goes from v to vi for any v≠vi and v≠t. There is a pair of values 0,0, for every edge v,t that goes from v to t for any v≠s and v≠t. The knapsack problem aims to select a subset U⊆v1,v2,⋯,vn of items such that ∑vi∈Uwi is maximized and the total weight ∑vi∈Udi≤δ. A subset U is a feasible solution for the knapsack problem if and only if there is a path that goes from s to the vertex vi with vi∈U and then to t. It is easy to see that the time of construction is in polynomial time.Select items satisfying the required conditions and add them to the knapsack, which is also the way to select the path for the problem. Therefore, if there exists a solution for the knapsack problem, the maximization problem can be solved. Vice Versa, existence of a solution to the maximization problem means there is a solution to the knapsack problem. Thus, the maximization problem is NP-hard.After reducing the graph knapsack problem to the throughput maximization problem, a Throughput Maximization algoRithm (TMR) is proposed based on Algorithm2, shown as Algorithm 3. Assume source node s intends to disseminate information to a specific area, an approximate delivery path is desired to achieve the maximum throughput and satisfy the delay constraint.To be more clearer, a detailed description on how the proposed TMR works on the throughput maximization problem to solve the path-finding issue is presented as follows.In the initialization process, letNv represent a set of v's neighbors. Starting from source node s, execute the following steps to each edge e∈G⋅E.(1)
To find the neighbor vehiclesNv for node v, exchange information and obtain the corresponding values WNi,DNi of the neighbors.(2)
To obtain the links connecting node v with its neighbors, calculate the channel capacitycl according to the channel condition. Then, get the transmission rate and delay of the corresponding link. Calculate Wv,Dv∈Yv for v by adding the value of its neighbor u, Wu,Du with we,de of the corresponding link e. Therefore, a list Yv for v can be achieved.(3)
According to the previous step, several pairs of valuesWv,Dv may exist for node v. First, remove the values with delay that are larger than the delay threshold δ. Then, if there are values with the same delay, keep those with larger transmission rate. Also, remove the values with larger delay and smaller transmission rate. In the following case, such as Yvi∈Yv with values of Wvi,Dvi, Yvj∈Yv with Wvj,Dvj, if Wvi>Wvj and Dvi>Dvj, which means item Yvi is with larger transmission rate but also with larger delay compared with Yvj, a trim procedure will be executed to determine whether to remove an element. If Wvi>1+ϵ/2n⋅Wvj, append Yvi onto list Y′; otherwise, remove Yvi and append Yvj onto list Y′.After the iterative operations, paths containing a set of selected links are obtained. If there are more than one path from the source to the destination, choose the one with the largest transmission rate, which is the approximate solution intended to achieve for data delivery.Theorem 3 is presented to show that the proposed TMR is a polynomial approximation algorithm with an approximation ratio of1+γ, where 0<γ<1.Algorithm 3: Throughput Maximization Algorithm.
Input: A list V containing all the vehicles and UAVs in the network
Output: The selected path(1)
LetNv denote the neighbor of node v;(2)
a=0, which denotes the number of executions;(3)
for each node v do(4)
Send a request to its neighbors;(5)
Receive the channel information (CI) from its neighbors;(6)
Calculatecl according to CI;(7)
Calculate the approximate values ofrl and dl according to dl=K/cl−rl;(8)
Obtain the transmission rate and delay of the link between each neighbor and nodev, denoted as we,de;(9)
end for(10)
repeat(11)
Calculate the transmission rate and delay for each nodev in the network, by adding the neighbor’s corresponding values to we,de, denoted as Wv,Dv;(12)
Apply the trim procedure to remove unnecessary values of nodev;(13)
a=a+1;(14)
until a=G⋅V−1(15)
return A path containing a set of selected linksTheorem 3.
The throughput maximization algorithm can achieve an approximation ratio1+γ within running time On2mlnC/γ, where m denotes the number of edges, C=∑i=1mci, ci indicates the transmission capacity of link i.Proof.
The input of the proposed maximization algorithm iswl,dl. As stated in 4.1, the value of wl,dl is within a 1+ϵ factor approximation of the optimal value. Considering the approximation in the multiedge knapsack problem, the throughput maximization problem should have a quadratic approximation. According to theorem 1, the comprehensive approximation ratio is(9)1+ϵ2=1+2ϵ+ϵ2.
Assumeγ=ϵ/3, the inequality 1+ϵ2=1+2ϵ+ϵ2<1+γ holds.
Hence, an approximation solution within a1+γ factor of the optimal solution can be achieved.
Asrl∈1,cl, assume there are m edges on the path. Let C=∑i∈mci, then ∀ y∈m,C. From Lemma 1, it has(10)log1+ϵ/2nC+1<3nlnCϵ+1=nlnCγ+1.
Therefore, the total running time isOn2mlnC/γ.


## 5. Performance Evaluation

In this section, simulation settings and results are presented and analyzed.


### 5.1. Simulation Settings

To evaluate the performance of the proposed algorithm, TMR is implemented and compared with other algorithms. In the simulations, the following default settings are used.The simulations select a 2000 m× 2000 m rectangle street area on the map of Los Angeles and extract the area using openstreetmap [31], the satellite map of which is presented as Figure 3(a). Then, Simulation of Urban Mobility (SUMO) [32] is used to convert the extracted area to the road topology layout, shown in Figure 3(b). The realistic mobility trace of vehicles is generated by the open-source microscopic space-continuous and time-discrete vehicular traffic generator package SUMO. SUMO uses a collision-free car-following model to determine the speeds and the positions of the vehicles. The simulations deploy a number of UAVs which can cooperatively form a full coverage of the simulated area. The speed of UAVs varies from 0 to 15 m/s, and the UAVs maintain a constant altitude that does not exceed 200 m during the flight. The random walk mobility model is applied for the UAVs covering the area. Table 2 gives a list of simulation parameters.Figure 3
Selected area of Los Angeles, CA, USA.
(a)
(b)Table 2
Simulation setup.
Parameters
Settings
Simulation area
2000 m× 2000 m
MAC protocol
IEEE 802.11p
Communication range of vehicles
300 m
Communication range of UAVs
1000 m
Vehicle velocity
0–13 m/s
UAV velocity
0–15 m/s
Number of vehicles
50–400
Number of UAVs
10–40The simulations implement the proposed algorithm and two other algorithms which are UVAR [33] and VBN [11], respectively. Extensive simulations are conducted to thoroughly investigate the efficiency of the proposed algorithm in aspect of delivery ratio, throughput, and number of hops when the number of vehicles varies and the deployed UAVs are set to 20. Additionally, the performance of the proposed algorithm with different UAV densities is evaluated when the number of vehicles is set to 300. A comparison between the proposed solution and optimal solution in terms of throughput is also presented.


### 5.2. Impact of Number of Vehicles on Delivery Ratio

Delivery ratio is defined as the percentage of packets that are successfully delivered, that is, the ratio of the total number of data packets received by the target destinations to the total number of data packets generated from the sources. A higher delivery ratio means better performance.In Figure4, the delivery ratio under different number of vehicles for the compared algorithms is compared. As shown in the figure, the evaluated schemes achieve higher delivery ratio when there are more vehicles in the network. Besides, it can be seen that the proposed scheme and UVAR have better delivery ratio, due to the advantage of UAVs that applied to maintain better network connectivity and guarantee a significant accuracy of path selection. VBN mainly chooses the delivery paths based on cooperation among RSUs and vehicles, which cannot be accurate all the time and may select the paths that are not appropriate for data transmission, resulting in lower delivery ratio.Figure 4
Data delivery ratio comparison when the number of nodes increases from 50 to 400.


### 5.3. Impact of Number of Vehicles on Throughput

An important performance indicator of the algorithms is the throughput of the path from the source to the destination nodes.In Figure5, the throughput is plotted versus the number of vehicle nodes. It is observed that the proposed algorithm TMR outperforms the other two algorithms and has the highest network throughput. When the number of vehicles is 50, the throughput of TMR is 1.48 Mbps, higher than that of UVAR and VBN. It also shows that all the compared algorithms achieve higher network throughput as the vehicle density level increases. As the number of vehicles increases to 400, the corresponding throughput of the three schemes increases to 3.45, 3.3, and 3.1 Mbps.Figure 5
Throughput comparison when the number of nodes increases from 50 to 400.


### 5.4. Impact of Number of Vehicles on Number of Hops

Number of hops can be obtained from the total number of hops performed by disseminating the message to the target area.The trend of required hops with the increasing number of vehicle nodes is shown in Figure6. The proposed algorithms TMR and UVAR perform fewer hops than VBN. This is because that with the help of employed UAVs, available delivery paths from the source node to the destination area can be quickly found by avoiding unnecessary transmissions among vehicle nodes, such that the number of hops consumed is smaller. As the network size becomes larger, the number of hops increases for all the compared schemes. This is mainly because that as the number of vehicles in the target area increases, more hops are needed to deliver the message to the vehicles and complete the dissemination.Figure 6
Consumed hops comparison when the number of nodes increases from 50 to 400.


### 5.5. Evaluating the Throughput Maximization Algorithm

Figure7 shows the impact of the number of UAVs on data delivery ratio and delivery delay. As more UAVs participate in data transmission, the delivery ratio increases while the delivery delay tends to decrease. This is because that the UAVs can serve relay nodes in data dissemination when there are no available vehicles to carry and forward the data. When more UAVs participate in the communications, the vehicle nodes could select a better UAV relay with a higher probability, which results in the changing data delivery delay and delivery ratio shown in the figure.Figure 7
Impact of number of UAVs on data delivery efficiency, illustrated by delivery ratio and delivery delay.To show the difference between the proposed solution and the best possible solution, Figure8 compares the proposed and optimal solutions in terms of throughput, considering the UAV-assisted vehicular environment. Comparing the simulation throughput with the optimal throughput in Figure 8, it can be seen that the simulation result consists with the optimal throughput to a great extent. Meanwhile, the approximation ratio is smaller than 1.1, which also verifies the effectiveness of the proposed algorithm. Observing the changing trends of the throughput, it is easy to find that the system throughput improves when the number of nodes in the network increases.Figure 8
Throughput comparison between the proposed solution and the optimal solution, the approximation ratio reflects the throughput difference and the effectiveness of the proposed solution.


## 5.1. Simulation Settings

To evaluate the performance of the proposed algorithm, TMR is implemented and compared with other algorithms. In the simulations, the following default settings are used.The simulations select a 2000 m× 2000 m rectangle street area on the map of Los Angeles and extract the area using openstreetmap [31], the satellite map of which is presented as Figure 3(a). Then, Simulation of Urban Mobility (SUMO) [32] is used to convert the extracted area to the road topology layout, shown in Figure 3(b). The realistic mobility trace of vehicles is generated by the open-source microscopic space-continuous and time-discrete vehicular traffic generator package SUMO. SUMO uses a collision-free car-following model to determine the speeds and the positions of the vehicles. The simulations deploy a number of UAVs which can cooperatively form a full coverage of the simulated area. The speed of UAVs varies from 0 to 15 m/s, and the UAVs maintain a constant altitude that does not exceed 200 m during the flight. The random walk mobility model is applied for the UAVs covering the area. Table 2 gives a list of simulation parameters.Figure 3
Selected area of Los Angeles, CA, USA.
(a)
(b)Table 2
Simulation setup.
Parameters
Settings
Simulation area
2000 m× 2000 m
MAC protocol
IEEE 802.11p
Communication range of vehicles
300 m
Communication range of UAVs
1000 m
Vehicle velocity
0–13 m/s
UAV velocity
0–15 m/s
Number of vehicles
50–400
Number of UAVs
10–40The simulations implement the proposed algorithm and two other algorithms which are UVAR [33] and VBN [11], respectively. Extensive simulations are conducted to thoroughly investigate the efficiency of the proposed algorithm in aspect of delivery ratio, throughput, and number of hops when the number of vehicles varies and the deployed UAVs are set to 20. Additionally, the performance of the proposed algorithm with different UAV densities is evaluated when the number of vehicles is set to 300. A comparison between the proposed solution and optimal solution in terms of throughput is also presented.


## 5.2. Impact of Number of Vehicles on Delivery Ratio

Delivery ratio is defined as the percentage of packets that are successfully delivered, that is, the ratio of the total number of data packets received by the target destinations to the total number of data packets generated from the sources. A higher delivery ratio means better performance.In Figure4, the delivery ratio under different number of vehicles for the compared algorithms is compared. As shown in the figure, the evaluated schemes achieve higher delivery ratio when there are more vehicles in the network. Besides, it can be seen that the proposed scheme and UVAR have better delivery ratio, due to the advantage of UAVs that applied to maintain better network connectivity and guarantee a significant accuracy of path selection. VBN mainly chooses the delivery paths based on cooperation among RSUs and vehicles, which cannot be accurate all the time and may select the paths that are not appropriate for data transmission, resulting in lower delivery ratio.Figure 4
Data delivery ratio comparison when the number of nodes increases from 50 to 400.


## 5.3. Impact of Number of Vehicles on Throughput

An important performance indicator of the algorithms is the throughput of the path from the source to the destination nodes.In Figure5, the throughput is plotted versus the number of vehicle nodes. It is observed that the proposed algorithm TMR outperforms the other two algorithms and has the highest network throughput. When the number of vehicles is 50, the throughput of TMR is 1.48 Mbps, higher than that of UVAR and VBN. It also shows that all the compared algorithms achieve higher network throughput as the vehicle density level increases. As the number of vehicles increases to 400, the corresponding throughput of the three schemes increases to 3.45, 3.3, and 3.1 Mbps.Figure 5
Throughput comparison when the number of nodes increases from 50 to 400.


## 5.4. Impact of Number of Vehicles on Number of Hops

Number of hops can be obtained from the total number of hops performed by disseminating the message to the target area.The trend of required hops with the increasing number of vehicle nodes is shown in Figure6. The proposed algorithms TMR and UVAR perform fewer hops than VBN. This is because that with the help of employed UAVs, available delivery paths from the source node to the destination area can be quickly found by avoiding unnecessary transmissions among vehicle nodes, such that the number of hops consumed is smaller. As the network size becomes larger, the number of hops increases for all the compared schemes. This is mainly because that as the number of vehicles in the target area increases, more hops are needed to deliver the message to the vehicles and complete the dissemination.Figure 6
Consumed hops comparison when the number of nodes increases from 50 to 400.


## 5.5. Evaluating the Throughput Maximization Algorithm

Figure7 shows the impact of the number of UAVs on data delivery ratio and delivery delay. As more UAVs participate in data transmission, the delivery ratio increases while the delivery delay tends to decrease. This is because that the UAVs can serve relay nodes in data dissemination when there are no available vehicles to carry and forward the data. When more UAVs participate in the communications, the vehicle nodes could select a better UAV relay with a higher probability, which results in the changing data delivery delay and delivery ratio shown in the figure.Figure 7
Impact of number of UAVs on data delivery efficiency, illustrated by delivery ratio and delivery delay.To show the difference between the proposed solution and the best possible solution, Figure8 compares the proposed and optimal solutions in terms of throughput, considering the UAV-assisted vehicular environment. Comparing the simulation throughput with the optimal throughput in Figure 8, it can be seen that the simulation result consists with the optimal throughput to a great extent. Meanwhile, the approximation ratio is smaller than 1.1, which also verifies the effectiveness of the proposed algorithm. Observing the changing trends of the throughput, it is easy to find that the system throughput improves when the number of nodes in the network increases.Figure 8
Throughput comparison between the proposed solution and the optimal solution, the approximation ratio reflects the throughput difference and the effectiveness of the proposed solution.


## 6. Conclusion

In this paper, efficient data dissemination in cooperative UAV-assisted VANETs is investigated. To optimize the network throughput, this study formulates a network throughput maximization problem to find the best delivery strategy and select the optimal paths for data delivery, with consideration of the transmission rate of links and the delay constraint for data dissemination. Then reduce the graph knapsack problem to the throughput maximization problem, and a polynomial time approximation scheme is proposed to solve the graph knapsack problem. As to the maximization problem, a throughput maximization algorithm is developed based on the approximation scheme. Theoretical analysis including the approximation ratio and running time of the proposed solution is provided. Finally, simulations are conducted to evaluate the performance of the proposed algorithm.


## 7. Discussions and Future Work

While the utilization of UAVs brings significant advantages, it also faces the cost problem. UAV communications are subjected to the additional energy consumption to fly at high altitudes, which is more significant than the communication energy consumption due to signal processing. Nevertheless, the limited on-board energy due to high propulsion energy consumption of UAVs poses critical limits on their communication performance and endurance.It can be seen that there exists a fundamental tradeoff between the achievable utility benefit and system cost in UAV-assisted communication networks. Using UAVs can increase the network throughput and improve quality of service, which is important to users, especially to the applications with high quality of service requirements. Although the use of UAVs increases the system cost, UAVs have significant advantages over common roadside infrastructure. The tradeoff between the benefit and cost can be achieved by energy-efficient design to enhance the performance of UAV-assisted communication, which is a promising future work direction, such that the deployment and trajectory of UAVs can be carefully designed to save the energy consumption and improve the quality of communications (improved transmission rate and transmission delay).Despite the contributions presented in this work, many challenges remain to be solved by academia and industry. Future work will focus on the frequent handover problem and interference caused by the high mobility of UAVs and vehicles. Also, energy efficiency of the UAVs remains a relevant topic to be explored to achieve fully utilization of UAVs and improve data dissemination in cooperative network. Further, the integration of the proposed architecture with the concept of SDN and the development of envisaged applications which can adapt to more complicated scenarios might be considered as another future work direction.



---

*Source: 8548301-2018-10-25.xml*