key: cord-0661272-i1cswmew
authors: LiWang, Minghui; Gao, Zhibin; Wang, Xianbin
title: Energy-Aware Graph Task Scheduling in Software-Defined Air-Ground Integrated Vehicular Networks
date: 2020-08-03
journal: nan
DOI: nan
sha: b3ad26ff901493acdb3d6a8cb2410cbb61ea1613
doc_id: 661272
cord_uid: i1cswmew

The Software-Defined Air-Ground integrated Vehicular (SD-AGV) networks have emerged as a promising paradigm, which realize the flexible on-ground resource sharing to support innovative applications for UAVs with heavy computational overhead. In this paper, we investigate a vehicular cloud-assisted task scheduling problem in SD-AGV networks, where the computation-intensive tasks carried by UAVs, and the vehicular cloud are modeled via graph-based representation. To map each component of the graph tasks to a feasible vehicle, while achieving the trade-off among minimizing UAVs' task completion time, energy consumption, and the data exchange cost among moving vehicles, we formulate the problem as a mixed-integer non-linear programming problem, which is Np-hard. Moreover, the constraint associated with preserving task structures poses addressing the subgraph isomorphism problem over dynamic vehicular topology, that further complicates the algorithm design. Motivated by which, we propose an efficient decoupled approach by separating the template (feasible mappings between components and vehicles) searching from the transmission power allocation. For the former, we present an efficient algorithm of searching for all the isomorphic subgraphs with low computation complexity. For the latter, we introduce a power allocation algorithm by applying $p$-norm and convex optimization techniques. Extensive simulations demonstrate that the proposed approach outperforms the benchmark methods considering various problem sizes.

B ENEFITING from the considerable support in military, public and civil services [1] , unmanned aerial vehicles (UAVs, also known as drones) [2] are emerged as one of the fastest growing techniques owing to their freedom of movement, on-demand deployment, and hardware cost reduction [3] . Last five years have witnessed an exponential growth of UAV applications, presently driving business close to 1 billion US Dollars in the USA, while with an upwards growth targeted to reach 46 billion US Dollars by 2025 [4] . Specifically, innovative applications such as transportation management, disaster relief (e.g., rescue missions and target detection) and smart surveillance (e.g., tracking mobile targets, etc.) have facilitated both safety and convenience to people's work and life. Besides, UAVs have realized significant values in popular incidents such like the radiation leakages of the Fukushima nuclear power plant in 2011 [5] , and the search work during the basketball legend Kobe Bryant's helicopter crush, in 2020 [6] .

Computational overhead required by the aforementioned UAV applications and use cases pose major challenges to UAVs with limited on-board processing capabilities, resources, and battery lives (e.g., up to 90 minutes flight duration even for high-performance battery-powered multirotor UAVs) [7] , [8] , which calls for responsive and flexible computing services. Thus, promoted by extensive development efforts on connected smart cars, vehicular cloud computing (VCC) technology [9] - [11] facilitates a revolution of the resource sharing among on-ground vehicles with surplus resources, and the UAVs with heavy workloads. Specifically, vehicles (service providers, SPs) form a cloud (vehicular cloud, VC) via vehicle-to-vehicle (V2V) communications to support efficient collaborative computing, while UAVs (service requestors) are encouraged to offload application data to SPs through air-to-ground (A2G) links [12] - [14] .

Nevertheless, traditional network architecture can hardly meet different QoS requirements imposed by diverse services and various communication techniques in networks containing both air segment (UAVs) and ground segment (vehicles) [15] , [16] . To enable a dynamic and adaptable airground integrated network with cost-effectivity, software defined networking (SDN) has been applied as an emerging architecture. Specifically, SDN separates the control plane and the data plane, introduces a logically centralized control with a global view of the network, while facilitating network programmability/reconfiguration through open interfaces [12] , [16] , [17] . Motivated by which, we consider the software defined air-ground integrated vehicular (SD-AGV) network architecture, to implement agile and flexible support for heterogenous applications. Under such a framework, graph-based-representation [8] - [10] , [18] , [19] is utilized in this paper to characterize the non-negligible internal structures associated with the applications of UAVs. Each application 1 is modeled as an undirected graph, where the vertices (named as "components" in this paper) represent either data sources or data processing units, while weighted edges describe the dependency among the vertices. Specifically, components can be processed on different SPs in parallel while intermediate data exchanges may happen among these vehicles (associated edges in each task). Moreover, virtual machine (VM)-based representation is utilized to quantify available resources on SPs. Fig. 1 shows an example of multi-target recognition application in smart public transportation which is popular nowadays [8] (e.g., masked face recognition smart buses), especially during the COVID-19 epidemic [20] to trace the close contacts of patients who are tested positive. Specifically, a task is modeled as an undirected graph where data of multiple targets, e.g., faces, can be analyzed on different servers in parallel. Meanwhile, edges represent the interdependency among components such as outline and color information, etc (e.g., to indicate close contacts during epidemic). Thus, each edge in the graph task may require intermediate data exchange between the two SPs who are handling components associated with this edge. Similar paradigm also refers to image segmentation-based parallel processing, VR video stream processing [8] , as well as federated learning-based applications (e.g., clients share a global model and train their own models via local data sets in parallel) 2 . 

In this paper, we study an interesting energy-aware graph task scheduling problem in a SD-AGV network architecture. Concretely, the components of graph tasks carried by UAVs can be mapped to feasible on-ground SPs, while achieving the trade-off upon minimizing the task completion time and the energy consumption of UAVs, as well as the data exchange cost (e.g., energy) among SPs which incurred by the required data interactions among task components. Major challenges are summarized below, a) Obtaining feasible mappings between the components of graph tasks and the moving SPs requires solving the subgraph isomorphism problem under contact constraints, which is NP-hard [21] , [22] . Moreover, avoiding the conflict of premium resources (e.g., some vehicles are at the core of vehicular cloud topology) can further pose challenges.

2. Note that the most common bit-stream-based computationintensive application [13] , [23] , [24] can also be seen as a specific graph task with one divisible component, with no edges. b) Considering UAVs' energy consumption requires addressing the transmission power optimization problem, which is generally formulated with non-convex feature; c) The energy-aware graph task scheduling problem stands for a coupling of obtaining the mappings between the components and the SPs, as well as solving the transmission power optimization problem, which are challenging to be solved in parallel.

Addressing the above-mentioned challenges represents our main motivation in this paper. Specifically, we investigate a novel decoupled approach to solve the energy-aware graph task scheduling problem, by separating components mapping from power allocation. For the former, an efficient template search algorithm is proposed, where each template stands for a feasible mapping between the components of graph tasks and the SPs. For the latter, a power allocation algorithm is introduced via applying p-norm and convex optimization techniques.

Existing studies devoted to the task scheduling/allocation problem can be roughly divided into two categories based on task models: a) tasks that are represented by bit streams without concerning the inherent dependencies, such as [1] , [13] , [23] - [27] ; b) tasks under graph-based representation upon considering the inner dependencies among components such like [9] , [10] , [18] , [19] , [22] , [28] - [34] , which stands for our main focus. The bit stream-represented task scheduling problem has been widely discussed in UAV networks. Messous et al. in [1] focused on the computation offloading problem in a mobile edge computing (MEC)assisted UAV network, by establishing a non-cooperative theoretical game with multi-players and three pure strategies. In [13] , Wang et al. introduced a vehicular fog computing (VFC) system where vehicles perform computation tasks offloaded from UAVs. Specifically, a stable matching algorithm was proposed to avoid the transmission competitions yet enabling cooperations among UAVs and vehicles. Bai et al. [23] conceived an energy-efficient computation offloading technique for UAV-MEC systems, with an emphasis on physical-layer security. Sacco et al. [24] addressed the problem of task offloading from UAV to the closest edge cloud via introducing a simple yet effective formalization that enables a learning process, while reducing the required information and training time.

Studies associated with graph task scheduling can be further classified into two types according to the dependency among task components: a) directed acyclic graph (DAG) task scheduling [19] , [30] , [32] - [34] ; and b) undirected graphrepresented task scheduling [9] , [10] , [18] , [22] , [28] , [29] , [31] . Regarding DAG-based task models, Sahni et al. in [30] formulated the problem of jointly offloading multiple DAG tasks and network flow (considering start time of network flow) scheduling in collaborative edge computing to minimize the average task completion time. Goudarzi et al. [32] proposed a fast hybrid multi-site computation offloading algorithm by modeling each application as a weighted related graph. Geng Fig. 2 . a). The framework of VC-assisted graph task scheduling in the SD-AGV network; b). The related coordinate system, and various graph task types considered in simulation.

programming problem and applying a heuristic algorithm. In [34] , Sun et al. studied a VC-based computation offloading mechanism where computing missions were modeled as tasks with interdependency and executed in different vehicles to minimize overall response time, and thus alleviates the heavy workloads of edge clouds. Considering static data center networks, Shafiee et al. in [19] proposed a polynomial-time algorithm while proving an optimality gap for scheduling coflows with general DAGs.

For un-directed graph models, considering static topologies of both computing servers and users in cloud computing context, Ghaderi et al. [18] proposed a randomized graph job scheduling algorithm by considering job arrivals/departures, which facilitated a smooth trade-off between the average execution cost and queue length. An energy-efficient graph job allocation framework in geo-distributed cloud networks was proposed by Hosseinalipour et al. [28] , where solutions were obtained for data center networks of various scales. In [31] , aiming to minimize the job completion time while considering energy consumption, the problem of scheduling embarrassingly parallel jobs composed of a set of independent tasks was studied by Shi et al. In general, parallel processing of components of un-directed graph tasks greatly require servers to maintain all the communication links in supporting intermediate data sharing, which is fundamentally different from the processing of DAG models [19] , [33] that are sequential in nature. Besides, considering mobile devices as computing servers can further pose challenges to protect the structure of graph tasks over dynamic service topology.

We are among the few works that study the undirected graph task scheduling problem considering dynamic service providers (e.g., vehicles). A randomized graph task allocation mechanism based on hierarchical tree decomposition was proposed in our previous work [9] , through which, feasible mappings between components and SPs were obtained. In [10] , we presented a novel multi-task offloading problem under graph-representation by considering the potential inter-component competition due to task concurrency. In [22] , we studied a truthful auction-based graph task allocation problem in vehicular cloud-assisted networks while considering the resource reutilization. However, concerning energy consumption especially for batteryconscious devices are not yet considered in the abovementioned previous researches. To conform green computing [35] , an energy-aware graph task allocation problem in VC-assisted IoV was studied in our latest study [29] . Specifically, a hierarchical tree based random matching approach was applied to determine the assignment of a single graph task over service topology; while a structurepreserved simulated annealing algorithm was proposed to solve the power allocation problem.

This paper studies the energy-aware allocation problem of mapping the components of multiple graph tasks carried by UAVs to on-ground SPs. Factors such as multiple concurrent tasks and complicated A2G channels present additional challenges related to the problem size and algorithm efficiency. Moreover, the potential competitions among UAVs caused by communication overlaps are necessarily considered. To the best of our knowledge, this paper is among the first to study the energy-aware graph task scheduling problem under the SD-AGV network architecture. Major contributions are summarized below:

• Framework of energy-aware graph task scheduling under SD-AGV network is introduced, where the SDN controller achieves the efficient orchestration of undeveloped onground resources. The reliable integration of air segment and ground segment enables resource sharing between the UAVs with computation-intensive graph tasks and the ve-hicles with idle resources, under the logically centralized control of the SDN controller. • An interesting graph task scheduling problem under SD-AGV network architecture is studied, where each task is modeled as an undirected graph with components and weighted edges. Besides, VC (topology of SPs) is modeled as a service graph where probabilistic representation is utilized to evaluate the communications among SPs. Through solving the problem, the components of graph tasks on UAVs can be efficiently mapped to feasible on-ground vehicles, while achieving the trade-off upon minimizing the task completion time and energy consumption of UAVs, as well as the data exchange cost (e.g., energy consumption of SPs) among SPs.

• The afore-mentioned problem is formulated as a mixed integer non-linear programming (MINLP) problem, which is NP-hard. Moreover, one of the constraints associated with preserving the graph task structures requires addressing the subgraph isomorphism problem, which further complicates the algorithm design. Thus, we propose an ingenious decoupled approach by separating the template search stage from the power allocation stage. The problem in the former stage is formulated as searching for all the isomorphic subgraphs between the graph tasks and the VC, for which we present an efficient template search algorithm. For the latter stage, we introduce a practical power optimization algorithm by applying convex optimization techniques.

• Based on thorough numerical analysis and comparative evaluations, we demonstrate that the performance of the proposed decoupled approach can outperform the baseline methods considering various problem sizes, while providing a low computation complexity in most cases.

The rest of this paper is organized as follows. The system model is introduced in Section 2. We formulate the energyaware graph task scheduling problem as a MINLP problem in Section 3. In Section 4, we propose an efficient decoupled approach. The performance evaluation through comprehensive simulations is introduced in Section 5 before drawing the conclusion in Section 6.

The SD-AGV networks is seen as an emerging network architecture of the late years. Specifically, SDN 3 decouples the control plane from the data plane [12] , introduces logically centralized control with a global view of networks, while facilitating network programmability/reconfiguration through open interfaces. Combine with the VCC technology, a manageable and cost-effective marketplace is established to orchestrate on-ground resources for the UAVs with computing requirements, achieving an efficient collaborative computing system. The framework of VC-assisted graph task scheduling in SD-AGV networks and the relevant coordinate system are shown in Fig. 2 (a) and Fig. 2(b) , respectively. Data plane and available resources: In this framework, each UAV or vehicle serves as an SDN switch that abided by unified scheduling and follows the Openflow protocol commonly used in SDN [17] . The UAVs are service requestors with heavy workloads, while vehicles serve as service providers with available resources. Both parties are following the schedule of the SDN controller. Decoupling data transmission and processing from control stands for one of the key features in this framework, which enables efficient orchestration of undeveloped resources. Control plane and the SDN controller: This framework effectively facilitates the independency between the physical communication channels of control plane and that of the data plane, where the SDN controller can capture the status information [15] reported periodically by UAVs and vehicles (e.g., channel state information, locations, computing service requirements, current available resources, etc). Specifically, a feasible energy-aware graph task scheduling decision generated by the SDN controller will be distributed to the related mobile devices. Then, the data of graph tasks will be transmitted from UAVs to on-ground vehicles according to the allocation decision via data plane.

Suppose a VC covers a region containing SP set S = {s k |k ∈ {1, 2, · · · , |S|}}, where each s k ∈ S owns different number of fully connected idle VMs for leasing, and every VM provides the computational capability related to the execution time t exec for processing one component of a graph task. Notably, an available VM can only process one component at a time. Correspondingly, the VC is represented as a graph G s = {S, E s , W s }, where S is the set of SPs and each s k ∈ S can provide a set of available VMs denoted by V k . E s = {e s k,k |s k , s k ∈ S, s k = s k } represents the edge set where e s k,k indicates the edge between s k and s k , namely, a one-hop V2V communication link between these SPs. Moreover, W s = {w s k,k |s k , s k ∈ S, s k = s k } denotes the associated weight of the edge set describing the corresponding parameters of the exponential distribution of V2V connections, which will be introduced in the following Section 2.5.

Consider set of UAVs U = {u m |m ∈ {1, 2, · · · , |U |}} hovered in the sky, where each u m ∈ U carries a computationintensive graph task 4 requires to be offloaded to onground SPs for execution. The task of u m is modeled as a graph G um = {V um , E um , W um }, where V um = {v n,m |n ∈ {1, 2, · · · , |V um |}} denotes the components set in the graph task, and v n,m indicates the n th component of the graph task of u m , with data size D n,m = D (bit) 5 . E um = {e um n,n |n, n ∈ {1, 2, · · · , |V um |}, n = n } and W um = {w um n,n |n, n ∈ {1, 2, · · · , |V um |}, n = n } represent the edge set and the related weight set respectively, 4 . Here, each UAV can also carry multiple graph tasks. This case is regarded as a scenario with multiple virtual UAVs with limited transmission powers, where the proposed approach in this paper is feasible to be implemented. 5 . In this paper, we assume that components have the same data size for analytical simplicity. Notably, the proposed approach can also be applied when considering different data sizes of components. the k th SP, the edge and weight between SPs s k and s k U , um, Rm the set of UAVs, the m th UAV, the SPs set covered by um G um , V um , E um , W um the graph task of um, the set of components, edges, and weights of G um vn,m, e um n,n , w um n,n the n th components in V um , the edge and weight between components vn,m and v n ,m x n,m k , q k,m the indicator of mapping vn,m to s k , the allocated power of um to s k x, q the matrix of x n,m k and q k,m d k,k , d A2G k,m the distance between s k and s k the distance between um and s k C n,n ,m k,k indicator of the data exchange cost g k,m , r k,m the channel gain and the data transmission rate between um and s k Dn,m, t exec the data size of component vn,m, the execution time of each VM α1, α2 the probabilistic parameters X, Xz the template set, the z th template in set X (used in stage 1) Sz, E s,z , W s,z the set of SPs, edges and weights associated with template Xz (used in stage 1) where e um n,n and w um n,n denote the required data flow, and connect duration between components v n,m and v n ,m . A graph task G um describes the internal dependencies of how the computation split among the components in V um . For notational simplicity, let V U um∈U V um be the union set of the components of graph tasks.

Observe that for any graph task, there exist several ways (an exponential large number) in which the task can be distributed over SPs. Note that multiple graph tasks may exist in the network, a template X corresponds to a feasible mapping from the components set V U to a subset of S in the related VC. An example of the template is given in Fig. 2(a) . Notably, a mapping fails to preserve the structures or meet the weight requirements among edges of the graph tasks cannot be a template.

For analytical simplicity, let binary indicator x n,m k = 1 denote the assignment where component v n,m is mapped to SP s k ; otherwise, x n,m k = 0. Note that different UAVs may have various communication ranges, let R m be the set of SPs that are covered by the communication radius of UAV u m , and the components of G um can only be mapped to the SPs in R m . Also, we assume that each UAV stays hovering or moves slightly in the sky, which enables the SPs in each set R m remaining unchanged during graph task scheduling. V2V channel model: The contact duration between SPs s k and s k obeys an exponential distribution [9] , [10] , [36] with parameter w s k,k . Thus, the probability of the contact duration ∆τ k,k between s k and s k exceeding a certain period ∆t is given by prob(∆τ k,k ≥ ∆t|w s k,k ) = e −∆t×w s k,k , where the larger prob(∆τ k,k ≥ ∆t|w s k,k ) can bring more assurance for the required data exchange duration between different SPs 6 .

The path loss of a V2V communication link is considered by following the dual-slope model [37] , which is defined as a piece-wise function of the distance d k,k between s k and s k .

where d 0 is the reference distance, pl 0 is the path loss at d 0 , X σ denotes a zero-mean normally distributed random variable with a standard deviation of σ. Notation η 1 and η 2 denote the path loss exponent before and after distance d B , respectively, and d B indicates the breakpoint distance which is calculated as (2) .

where h t and h r are the transmitter's and the receiver's height, and w denotes the wavelength. Here, let h t = h r owing to the possible intermediate data exchange that makes s k and s k into both transmitter and receiver. Rely on the 6 . Regarding moving vehicles, we consider an soft assurance by using probabilistic representation, which is also close to real-life networks. uncertain channel conditions of V2V communication links, the case where two connected components are mapped to different SPs can bring intermediate data exchange cost, which captures the cost incurred from traffic exchange among different SPs in a VC. Correspondingly, c cost k,k is defined in (3).

where f () is a monotone increasing function. Apparently, a larger value of pl(d k,k ) will bring a higher cost for intermediate data exchange among different vehicles. Let c n,n ,m k,k describe the data exchange cost (e.g., energy consumption, etc.) incurred when two connected components v n,m and v n ,m of G um are assigned to different SPs, which is given in (4) .

A2G channel model: As shown in Fig. 2 (a), we consider several multi-antenna UAVs capable for offloading the components of a graph task to SPs. Moreover, each SP relies on full-duplex techniques 7 and the self-interference is ignored. Denote the channel gain between u m and s k ∈ R m as g k,m , which is assumed to be dominated by the line of sight (LoS) path [38] , shown in (5).

where g 1 corresponds to the channel gain at the reference distance of 1 meter, d A2G k,m indicates the A2G distance between u m and s k , and η 3 denotes the path loss exponent of the LoS path. The data transmission rate r k,m between UAV u m and SP s k is a function of the transmission power q k,m that u m allocates to SP s k , calculated by (6) 8 where B denotes the channel bandwidth and N 0 represents the background noise power.

The completion time t m of graph task G um is composed by the time of data transmission, execution and the resulting feedback. Notably, the delay on resulting feedback from the SP to the UAV can be ignored owing to a much smaller output data size [9] , [10] . Apparently, t m relies on the slowest processed component of graph task G um .

where |V um | n=1 represent the total amount of data, and the relevant transmission 7 . Each SP can receive task data from UAVs while exchanging the intermediate data results with other SPs [40] . 8. Interference during task data transmission procedure (from UAVs to vehicles) is neglected in this paper for analytical simplicity, while technologies such as OFDMA can also support this assumption [8] , [22] , [23] , [30] . time of components from u m to s k , respectively. Moreover, the UAV would incur extra overhead in terms of energy when transmitting data to SPs via wireless access. Thus, the energy consumption c m of u m is calculated as:

where indicates the tail energy [39] given that the UAV will hold the channel for a while even after data transmission. We summarize the major notations and the related definitions in Table 1 .

Consider a network containing a set of vehicles S as service providers and a set of UAVs U as service requestors, the relevant constraints are listed below.

• Available resource limitation imposes restrictions on idle VMs for each SP:

• Soft opportunistic V2V connection poses a soft constraint that if two connected components v n,m and v n ,m of u m with weight w um n,n are mapped to different SPs s k and s k , the probability of the contact duration between s k and s k being larger than (9), we formulate the proposed optimization problem of energy-aware graph task scheduling as P in (10).

F(x, q) stands for the weighted sum of task completion time, energy consumption and data exchange cost, where ω 1 , ω 2 and ω 3 , represent the non-negative coefficients.

|U | m=1 t m and |U | m=1 c m denote the overall task completion time and energy consumption of UAVs, respectively.

indicates the total data exchange cost among SPs in the VC, where the normalization factor 1/2 is considered since the cost will be calculated twice due to the un-directed graph model. Notably, P stands for a non-trivial MINLP problem which is NP-hard with coupled binary variables x n,m k ∈ x and consecutive variables q k,m ∈ q, that both needed to be optimized. Moreover, constraint (C2) requires solving the subgraph isomorphism problem, which further poses challenges to the algorithm design [9] , [21] , [28] , [29] . In principle, solutions can be obtained through exhaustive search, which, however, is practically infeasible due to high complexity. For example, determining templates of mapping components of UAVs to SPs through exhaustive search results in high computational complexity of O(2 (|V U |)× |S| k=1 |V k | ); and for each feasible mapping, the optimization problem of power allocation needs to be solved. Consequently, the system can rarely identify the optimal solutions to reconfigure the IoV extemporaneously, as the running time required to solve large and real-life network cases increases sharply with increasing vehicular and UAV's density. As a result, we propose an efficient decoupled approach for solving P in the next section, which can offer a low computation complexity.

The significance of preserving the structures of both the VC and the graph tasks complicates the simultaneous allocation of task components and transmission power among SPs. In this section, we propose an efficient approach by decoupling the template search problem from the power allocation problem, which mainly contains two stages. For the former stage, an efficient template search algorithm is proposed aiming to search for all the feasible mappings between the graph tasks and the SPs. Then, given the templates obtained from stage 1, a power allocation algorithm is presented via applying convex optimization techniques.

The template stands for one of the key concerns in this paper, which is formalized as the search for all the subgraph isomorphisms [21] between the graph tasks and the VC. For analytical simplicity, let X = {X z |z ∈ {1, 2, · · · |X|}} be the set of templates, where X z is the z th template in set X. Note that not every SP can be selected, we define S z ⊆ S as a subset of S associated with template X z . Specifically, lets z k ∈ S z be the k th SP in set S z , and V z k be the related VM set ofs z k . The edge and weight set corresponding to S z are denoted as E s,z = {ẽ s,z k,k |s z k ,s z k ∈ S z } and W s,z = {w s,z k,k |s z k ,s z k ∈ S z }, where E s,z ⊆ E s and W s,z ⊆ W s . Thus, each template X z ∈ X can be represented as X z = {x n,m k (z)|u m ∈ U , v n,m ∈ V um ,s z k ∈ S z }, where x n,m k (z) indicates the assignment from component v n,m to SPs z k ∈ S z , in template X z . The problem of searching for the templates is formulated as P 1 in (11).

if ∃e um n,n ∈ E um and x n,m

Similar with (C1), constraint (C5) imposes restrictions on available VMs of eachs z k ∈ S z . Constraint (C6) refers to the coverage limitation of each UAV, that is similar with (C4). Constraint (C7) poses a hard restriction that every template preserves the graph task structures; and a soft restriction which ensures that the probability of the contact duration between different SPss z k ands z k (processing connected components v n,m and v n ,m , respectively) being larger than w um n,n should be greater than a threshold α 2 (0 < α 2 < 1). Notably, the air-to-ground data transmission time is not concerned in P 1 owing to the unknown power allocation solution (which is introduced in the following Stage 2).

The coverage overlaps may bring competitions among UAVs of available VMs. Thus, an efficient template search algorithm is proposed to solve P 1 , while achieving conflict avoidance of re-occupations of the same VM among different UAVs. Our proposed algorithm is divided into two steps: preprocess for obtaining the component exploration sequence, and search for the templates. The first step stands for a preprocessing of the graph tasks, aiming to obtain an exploration sequence to determine the next candidate component during mapping. The second step aims to obtain the set of templates X under an efficient manner.

Step 1. Preprocess for obtaining the component exploration sequence: to prioritize the components that are more rare and constrained in graph tasks [21] , step 1 defines the order relationship by generating the component exploration sequence N . Specifically, an exploration sequence N denotes a permutation of the components in set V U , and is applied in step 2 to determine the next candidate Table 2 depicts an example of the component exploration sequence related to the graph tasks given in Fig. 2(a) , and the pseudocode of the preprocessing step is detailed in Algorithm 1.

Step 2. Search for the templates: the exploration sequence obtained by step 1 enables a criterion of selecting the next candidate component during the template search procedure. Given an exploration sequence N , the template set X can be obtained by searching for all the subgraph isomorphisms between the graph tasks and the VC, through step 2. To describe the interdependencies among components, we first define the predecessor P red(v n,m ) of a component v n,m as below, several examples of which are given in Table 2 (the third column). Definition 3 (the predecessor of component): the predecessor P red(v n,m ) of component v n,m is defined as a set of components that have one-hop connection with v n,m , and located before v n,m in N . Notably, some of the components may have no predecessor, such as the first component in sequence N .

To preserve task structures, while ensuring the efficiency Algorithm 1: Preprocess for obtaining the component exploration sequence (Step 1) Table 2 , the current available degree D s (s 6 ) of s 6 before graph task allocation is D s (s 6 ) = |V 6 |+|V 3 |+|V 5 |+|V 7 | = 2+2+3+1 = 8. After allocate component F to s 6 , the current available degree of Step {A, B, C, D, E, F, G, H, I} → {s5, s2, s4, s5, s7, s6, s5, s6, s3} which is computed as D s (s 6 ) = (2 − 1) + 2 + 3 + 1 = 7. Similarly, after component E is assigned to s 7 , the value of D s (s 6 ) is updated as D s (s 6 ) = 1 + 2 + 3 + (1 − 1) = 6 due to that the VM of s 7 has been occupied by E. Accordingly, D s (s 7 ) = 0.

Given an exploration sequence N , the major steps of the proposed template search algorithm are given in Algorithm 2. The main idea is to sequentially assign each component in set N to an unmapped candidate at a time, until all the templates are searched out. Notably, the computation complexity also relies on both the graph task and the VC structures. For example, consider the VC structure as a complete graph (there exist an edge between any two SPs), the computation complexity of the proposed algorithm may rise to the same level with exhaustive search. Thus, the proposed template search algorithm can provide a best computation complexity performance of O(|V U |), but a worst case equals to the exhaustive search algorithm. However, the proposed algorithm works on both the preprocess of graph tasks, and the selection of candidate SPs for each component, which greatly reduces the searching space during mapping. Owing to the flexible topologies of the graph tasks as well as the VCs in real-life applications and networks, we can make a weak assumption that in most cases, the proposed algorithm will offer a low computation complexity.

Rm, ∀um ∈ U , G s Output: X 1 Initialization: get P red(vn,m) for all vn,m ∈ V U , 2 in each iteration z, To better analyze our proposed template search algorithm, a walk through example is provided in Table 2 (from the forth column to the seventh colunm), showing how a template is generated given the graph task and VC structures shown in Fig. 2(a) , under the given exploration sequence N = [F, E, H, G, I, A, B, C, D].

In this section, we study an effective transmission power allocation algorithm under the given templates obtained from stage 1. Owing to that the proposed algorithm works indistinguishably for various templates, and the transmission power allocation is independent among different UAVs, the indexes z and m referring to a unique template X z and UAV u m are ignored. Hereafter, symbols x n k , D n , r k , q k and Q are as the substitutions of x n,m k (z), D n,m , r k,m , q k,m and Q m ; and V u = {v n |n ∈ {1, 2, · · · , |V u |}}, E u = {e u n,n |n, n ∈ {1, 2, · · · , |V u |}, n = n }, and W u = {w u n,n |n, n ∈ {1, 2, · · · , |V u |}, n = n } are utilized instead of V um , E um , and W um . Similarly, we apply S = {s k |k ∈ {1, 2, · · · , | S|}}, E s = {ẽ s k,k |s k ,s k ∈ S,s k =s k } and W s = {w s k,k |s k ,s k ∈ S,s k =s k } to differentiate the SP set S z of template X z from the total SP set S, regardless of the index z of a certain template.

The power allocation in stage 2 is formulated as an optimization problem P 2 given by (12) , where q = [q k ] 1≤k≤| S| denotes the power allocation vector that needs to be optimized. Notably, the value of data exchange is fixed under any given template, and thus not considered in P 2 .

s.t. x n k × x n k = 1 and ∀e u n,n ∈ E u and ∀s k ,s k ∈ S, (C8)

where D total k |V u | m=1 x n k × D n denotes the total size of the data transmitted from the UAV to s k , which is known for any given template. Same with (C2), constraint (C8) provide a soft restriction on preserving the edges and weights of the graph task. Constraint (C9) guarantees that the upper limit of a UAV's transmission power will not be exceeded. Apparently, P 2 refers to a min-max problem, which is challenging to be solved. For analytical simplicity, let T = is applied to approximate the optimal solution of P 2 .

Apparently, (13) indicates that a larger value of p enables the value of T p to approach T ∞ , and correspondingly brings a lower peak value of vector T . To facilitate the analysis, we consider

. Thus, P 2 is rewritten as P 3 shown in (14) , where constants ω 1 t exec and ω 2 can be ignored.

s.t. (C8), (C9). Although we may concentrate on obtaining the optimal solution of P 3 , there still remaining difficulties featured by non-convexity shown in the following lemma. Lemma 1: P 3 represents a non-convex optimization problem.

Proof. According to equation (6) , the data transmission rate r k is a function of q k . Thus, the proof can be obtained by verifying the concavity of q k r k (q k ) [41] , which makes P 3 nonconvex.

In consequence, the change-of-variable technique is applied to transform P 3 into a convex optimization problem P 4 , by introducing a set of substitutive variables ρ = {ρ k |ρ k = 1/r k }.

|ρ k − ρ k | + C n,n k,k ≤ 0, ∀s k =s k and x n k × x n k = 1 and ∀e u n,n ∈ E u and ∀s k ,s k ∈ S,

where is also fixed (namely, each C n,n k,k is a constant). Thus, (C11) can be rewritten as (C12) owning to C n,n k,k ≤ 0.

(ρ k − ρ k ) 2 − (C n,n k,k ) 2 ≤ 0, ∀s k =s k and x n k × x n k = 1 and ∀e u n,n ∈ E u and ∀s k ,s k ∈ S (C12)

Due to that there may exists multiple pairs of connected components being mapped to different SPs, constraint (C12) is thus represented as a inequality constraints set C, shown as (C13): C = f i ρ k , ρ k , C n,n k,k ≤ 0|i ∈ {1, · · · , |C|}, ∀s k =s k and x n k × x n k = 1 and ∀e u n,n ∈ E u and ∀s k ,s k ∈ S ,

where i denotes the index of the inequality, f i (ρ k , ρ k , C n,n k,k ) = (ρ k − ρ k ) 2 − (C n,n k,k ) 2 and each pair of n, n , k, k can be known under a given template. |C| denotes the number of inequalities in set C, which equals to the number of connected component pairs been mapped to different SPs. Notably, various templates 9 can have different C. Correspondingly, the problem P 4 represents a convex optimization problem, as proved in Lemma 2. Lemma 2: P 4 represents a convex optimization problem. Proof. Let function y(ρ) = y 1 (ρ) + y 2 (ρ), where y 1 (ρ) = W 1,k (ρ) p and y 2 (ρ) = W 2,k ρ(2 1 B×ρ − 1). The second-order 9 . For example, the constraint set C of UAV 1 shown in Fig. 1 (a) derivative of y(ρ) can be given by:

where y 1 (ρ) = p(p − 1)W 1 ρ p−2 ≥ 0, and y 2 (ρ) is calculated as:

B×ρ × ρ −2 . Thus, we have y 2 (ρ) shown in (18) .

Apparently, d 2 y(ρ) d 2 ρ > 0, ∀ρ > 0, and y(ρ) represents a convex function of variable ρ. Since P 4 aims at minimizing a summation of convex functions y(ρ k ), where the constraint (C10) is convex with (2 1 B×ρ ) > 0(∀ρ > 0). Moreover, each inequality constraint in (C13) is convex, P 4 is proved to be a convex optimization problem.

In consequence, the power allocation vector can be obtained numerically by using convex optimization solvers such as MATLAB function fmincon and CVX [42] .

This section presents numerical results that illustrate the validity of the proposed decoupled approach (abbreviate to "Proposed" for simplicity). In the following, the performance of the proposed template search and power allocation algorithms comparing with several baseline methods, are analyzed in detail. Moreover, various problem sizes are investigated considering different graph task types and VC structures, as well as various numbers of UAVs and SPs.

We consider a simulation space of 1000m × 1000m × 100m (length×width×height), wherein the height of the UAV is randomly chosen from 80m to 100m. The graph task types considered in this simulation are depicted in Fig.  2 

This section presents performance comparisons of the running time, and the number of templates (use "templates count" instead for notational simplicity) between the proposed template search algorithm and baseline methods listed below: The running time and the template count performance comparisons in small problem size containing one UAV and a couple of SPs, are shown in Fig. 3 and Table 3 , respectively. The 10-based logarithm representation is applied in Fig. 3 , since the gap between the running time of various algorithms becomes large as the graph task and VC structures become more complicated (e.g., upon increasing the number of components, SPs/VMs and edges). As can be seen in Fig. 3 , the running time of ESA rises sharply owing to that ESA relies heavily on the number of components, available VMs and the complexity of graph task as well as VC structures, which makes the ESA inappropriate for fast-changing and large-scale networks. Comparatively, the running time of the proposed algorithm remains approximately at a certain order of magnitude of 10 −2 ∼ 1 seconds when considering small problem sizes. Since the running time of the RSA mainly depends on the number of iterations, the performance of which remains slightly fluctuant near 0.5 seconds (RSA1), 1 seconds (RSA2) and 1.5 seconds (RSA3). Table 3 presents the comparisons of templates count between different algorithms in small problem size cases. Apparently, our proposed algorithm can search for all the subgraph isomorphisms between the graph tasks and the VC, while offering a much lower computation complexity than ESA according to Fig. 3 . The templates count of RSA under different numbers of iteration are far less than that of the proposed algorithm due to the randomness. In fact, failures and repetitions of mappings are common during the RSA procedure, owing to the structure preservation constraint. Fig. 4 presents the performance comparisons of running time and templates count in large problem size cases with multiple UAVs, increasing number of SPs and VMs, as well as more complicated VC structures (e.g., more edges between SPs). Here, we do not consider the baseline method RSA, since the running time of which relies mainly on the number of iterations, and the corresponding templates count is heavily influenced by the randomness factor. Notably, the number besides each mark in Fig. 4 indicates the number of templates related to the VC. Fig. 4 (a) and Fig. 4(b) show the performance comparisons between ESA and the proposed template algorithm considering various scenarios with two graph tasks, and increasing number of SPs, VMs, and edges. As can be seen from these two figures, the proposed algorithm can reach the same templates count with ESA, while offering a much lower running time. Due to the too large running time of ESA, we only present the performance of the proposed algorithm in Fig. 4(c) , under cases considering three graph tasks and more SPs/VMs/edges. It is observed from Fig. 4 , the proposed template search algorithm offers an average running time of 0.013 seconds for searching one template, rather than averagely 0.298 seconds of ESA, in large problem size cases.

To investigate the factors that influence the running time of our proposed algorithm, we focus on two UAVs with the same signal coverage as service requestors, each carries a graph task (type 2). Based on which, Fig. 5 presents the performance comparisons of running time and templates count between three VCs with the same number of SPs and VMs, but different topologies (e.g., different number of edges). Specifically, each red dotted rectangle indicates a possible candidate of the component with D c = 5 in graph task type 2. Fig. 5 (a) and Fig. 5(b) focus on the VCs with the same number of SPs/VMs/edges (12/14/13), and the different topologies reflected by edge 4 and edge 4 (the yellow edges). Apparently, the same amount of resources (SPs/VMs) and V2V connections (edges) can bring various number of possible candidates to components during mapping, which leads to significant differences of both the running time, and the templates count. Theoretically, the more candidates of a component will bring a larger searching space during mapping, and thus leads to higher running time and more templates even under the same amount of resources (e.g., the same number of SPs and VMs). Comparatively, Fig. 5(c) shows a further complicated VC structure containing 12 SPs, 14 VMs and 22 edges, which enables more candidates of the component with D c = 5 in graph task type 2. Correspondingly, obtaining all the templates of mapping the considered graph tasks to the VC in Fig. 5(c) results in a larger running time. Compared with the proposed algorithm, the running time of ESA in Fig. 5(a) , Fig. 4 . Performance comparisons of running time and templates count in large problem size cases: a). considering graph task type 1 and type 2; b). considering graph task type 2 and type 3; c). considering graph task type 1, type 2 and type 3. 

Given the templates obtained from the proposed template search algorithm, Fig. 6 presents the performance compari-son of the value of the objective function F(x, q) given in (9) , between the proposed power allocation algorithm, and several baseline methods listed below.

1) Uniform allocation (UA): for each given template, the transmission power is uniformly allocated to each SP. The algorithm fails when cannot meet constraint (C13).

2) Random allocation (RA): for each given template, the Fig. 7(a) ; b). associated with VC1 in Fig.7 (c).

transmission power is randomly allocated to each SP, until find a feasible allocation solution that meets constraint (C13).

3) Channel condition preferred allocation (CCPA): for each given template, a A2G channel with better condition (e.g, larger SNR) is allocated with more transmission power, while meeting constraint (C13). 4) Structure-preserved simulated annealing (SPSA) [18] : for each given template, the transmission power is allocated to each SP via simulated annealing algorithm, while meeting constraint (C13).

In various small problem size cases where each considers one UAV and a couple of SPs, Fig. 6 (a), Fig. 6 (b) and Fig.  6 (c) reveal that the performance of the value of F(x, q) greatly outperform the baseline methods UA, RA, CCPA, and SPSA, when applying the proposed power allocation algorithm with different values of p. Particularly, the cases where p = 3 achieve better performance of the value of F(x, q) than those consider p = 1, which commendably prove the theoretical idea of (13) (given in Section 4.2). Namely, a larger p enables the value of a vector's p-norm to approach that of the ∞-norm. The values of F(x, q) of RA fluctuate irregularly owing to the randomness factor; while that of CCPA often stay at high values due to the deficiency of balancing various A2G channel conditions, which thus leads to larger data transmission rates and unsatisfactory task completion time. Furthermore, our proposed algorithm obtains far better performance than SPSA since the process of generating a new state in SPSA only considers discrete values of power, which pose difficulties searching for the whole solution space. The performance comparisons considering large problem size cases with more UAVs and SPs, as well as complicated VC structures are depicted in Fig. 6(d) , Fig. 6 (e) and Fig. 6(f) . Similarly, our proposed algorithm can approach better performance than the baseline methods under both situations when p = 1 and p = 3.

As mentioned in Section 4.2, the larger value of p will bring a better performance on power allocation. Concretely, since a vector's ∞-norm describes the largest value (peak value) in this vector, while a vector's p-norm can approach the relevant ∞-norm upon increasing the value of p. Correspondingly, this section depicts the impact on F(x, q) when considering various p. Note that the proposed power allocation algorithm works indistinguishably and independently among different templates and UAVs, we focus on single UAV scenarios as examples. Fig. 7 demonstrates that for different graph task types and VC structures, upon increasing the value of p can always bring a better solution for problem P 2 given in (12) , and thus achieve a satisfying performance of the objective function F(x, q). Fig. 8 shows two examples of the changing process on the value of F(x, q), upon having various p and different templates. Fig. 8 (a) is associated with graph task type 1 and VC3 of Fig. 7(a) , where 48 templates are obtained from applying the proposed template search algorithm. Apparently, under each given template, a larger p achieves a lower F(x, q), and the best graph task and power allocatipon solution can be obtained by comparing through all the templates. Similar conclusion can be found from Fig. 8 (b) under 36 templates, which is related to graph task type 3 and VC1 shown in Fig. 7 (c).

This paper studies the energy-aware graph task scheduling problem in SD-AGV networks. To achieve the tradeoff upon minimizing the task completion time and energy consumption, as well as the data exchange cost, the problem is formulated as a MINLP problem which is NP-hard. An efficient decoupled approach is proposed by separating the template search stage from the power allocation stage. In the former stage, an effective algorithm is presented to search for all the subgraph isomorphisms between the graph tasks and the VC structure. For the latter stage, we introduce an applicable power allocation optimization algorithm by applying convex optimization techniques. The effectiveness of the proposed approach is revealed through comprehensive simulations. Several future research directions could involve improving the computation efficiency of the template search algorithm, and considering the optimization of the UAV's path trajectory to achieve better task scheduling performance.

A game theory based efficient computation offloading in an UAV network

Distributed Joint Power, Association and Flight Control for Massive-MIMO Self-Organizing Flying Drones

Persistent Crowd Tracking Using Unmanned AerIal Vehicle Swarms: A Novel Framework for Energy and Mobility Management

FOCUS: Fog Computing in UAS Software-Defined Mesh Networks

Fukushima Plants Radiation Levels Monitored with an UAV

Pilot: The mystery of Kobe Bryant's chopper crash

Modeling, Control System Design and Preliminary Experimental Verification of a Hybrid Power Unit Suitable for Multirotor UAVs

Let's Trade in the Future! A Futures-Enabled Fast Resource Trading Mechanism in Edge Computing-Assisted UAV Networks

Allocation of computation-intensive graph jobs over vehicular clouds in IoV

Multi-task offloading over vehicular clouds under graph-based representation

Enhancing Reliability and Availability through Redundancy in Vehicular Clouds

Software defined space-air-ground integrated vehicular networks: challenges and solutions

Task Offloading for Post-Disaster Rescue in Unmanned Aerial Vehicles Networks

Service-Oriented Dynamic Resource Slicing and Optimization for Space-Air-Ground Integrated Vehicular Networks

Enabling collaborative edge computing for software defined vehicular networks

Reliable Computation Offloading for Edge-Computing-Enabled Software-Defined IoV

Software defined cooperative data sharing in edge computing assisted 5G-VANET

Scheduling storms and streams in the cloud

Scheduling Coflows With Dependency Graph

Boosting Fairness for Masked Face Recognition

Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3

A truthful auction for graph job allocation in vehicular cloud-assisted networks

Energy-efficient computation offloading for secure uav-edge-computing systems

A Self-Learning Strategy for Task Offloading in UAV Networks

Two-Dimensional Task Offloading for Mobile Networks: An Imitation Learning Framework

Multi-Persona Mobility: Joint Cost-Effective and Resource-Aware Mobile-Edge Computation Offloading

Risk-Aware Data Offloading in Multi-Server Multi-Access Edge Computing Environment

Power-aware allocation of graph jobs in geo-distributed cloud networks

Energy-aware allocation of graph jobs in vehicular cloud computing-enabled software-defined IoV

Multihop Offloading of Multiple DAG Tasks in Collaborative Edge Computing

Energy-aware scheduling of embarrassingly parallel jobs and resource allocation in cloud

A fast hybrid multi-site computation offloading for mobile cloud computing

Energy-efficient computation offloading for multicore-based mobile devices

Cooperative task scheduling for computation offloading in vehicular cloud

Green computing

Contact-aware optimal resource allocation for mobile data offloading in opportunistic vehicular networks

Joint beamforming and power allocation for UAV-enabled full-duplex relay

A survey of channel modeling for uav communications

Efficient multi-user computation offloading for mobile-edge cloud computing

Enhancing cooperative driving in IEEE 802.11 vehicular networks through full-duplex radios

Joint task offloading scheduling and transmit power allocation for mobile-edge computing systems

CVX: Matlab software for disciplined convex programming, version 2.0 (beta)