An Efficient Tasks Offloading Procedure for an Integrated Edge-Computing Architecture

I. INTRODUCTION

THE upcoming sixth-generation (6G) networks has to support a wide plethora of disruptive applications, typically demanding for high rate, high reliability, low latency, and requiring seamless coverage. In such a context, the exclusive use of classical cellular networks seems to be not enough to handle the huge amount of data expected to be injected in the network by the new generation applications, and simultaneously guaranteeing the corresponding high-flying quality of service (QoS) constraints. Within this challenging context, the exclusive exploitation of terrestrial networks cannot meet the far-reaching traffic demand and service quality level, mainly in terms of delay constraints, of the emerging applications. In particular, it appears to date that it is through a synergism carefully orchestrated between terrestrial and non-terrestrial computational resources, that services delay mitigation can be reached [1].

In particular, this offers the promising opportunity to extend and empower the emerging edge computing paradigm [2] in an integrated heterogeneous scenario by considering flying unmanned aerial vehicles (UAVs) able to provide edge computing close to the end-users functionally integrated with ground edge nodes (ENs). This feature is of special interest whenever a quick and temporary computation resource update is needed in contexts where a permanent expansion of the ground ENs infrastructure is not advisable or viable, e.g., performing monitoring and control operations in a remote area under an unpredictable overload of computational demands. More generally, it can be stated that this novel edge computing paradigm aims at overcomes the limits of a classical ground edge computing system in any congested areas, providing faster computation and hosting processing of tasks stemmed from devices in an efficient and flexible manner by enabling tasks offloading towards different ENs locations, e.g., ground or air. In such a context, it becomes of paramount importance to provide a suitable tasks offloading procedure in order to select the most convenient computation site between a set of ground ENs or UAV-ENs. Furthermore, the end-to-end task delay, expressing the time elapsed since a device demanding for task computation submits its request until the device receives the processing outcome, represents a crucial metric to be investigated here. This holds particular significance in multimedia services, ensuring a predefined service quality target. However, it also proves beneficial for critical applications, especially when assessing the risk level associated with potentially surpassing a specific deadline in data delivery, is considered as a key performance indicator.

As a consequence, it has become mandatory to have adequate methodologies to perform a suitable tasks offloading and to predict the achievable performance. During years, Markovian analysis has been extensively applied to this regard, providing results in network performance evaluation in an easy way. Nevertheless, in order to provide accurate network performance predictions in the novel application contexts, the assumption of Markovian models may represent a too simplistic hypothesis. In fact, even if a more general system characterization such as G/G/1 model increases the complexity of the theoretical study, the corresponding analysis typically fits better the actual system dynamic, giving rise to a more effective system design [3].

In this reference, the main contributions of the paper can be summarized as follows

· Analysis of the queue behavior at the computation nodes in an integrated gound-air computation system by resorting to the G/G/1 model and use of the Lindley’s integral equation, solved by means of spectrum factorization [4] method;

· Design and development of an algorithm to perform tasks offloading with the aim at minimizing the task outage probability, i.e., the probability that a task experiences a completion time greater than the corresponding deadline, based on the queue state conditions of the selected computation nodes, i.e., ground EN or an unmanned aerial vehicles-mounted ENs (UAV-ENs);

· Numerical simulations to test the performance of the framework proposed and validate its effectiveness in comparison with different tasks allocation schemes.

The rest of the paper is organized as follows. In Section II an in-depth review of the related literature is provided. Section III presents both the system model and the problem formulation, whereas Section IV details the proposed framework. Performance evaluations are presented in Section V. Finally, our conclusions are outlined in Section VI.

II. RELATED WORKS

Many works are available from the literature regarding the use of UAVs to enable advanced services and applications. In particular, authors in [5] proposed a heuristic to maximize the cellular users coverage optimizing the drones deployment, as long as minimizing the communication cost among UAVs. A drone-as-a-service market model has been developed in [6], in which a service algorithm has been designed, in order to properly meet the quality requirements in terms of cost and delay, expressed by users. Moreover, this paper deals with the improvement of security for delivery drones. In particular, the authors propose a consumer authentication hybrid computing framework for drone delivery as a service, the effectiveness of which is demonstrated through experimental results. In [7] the main focus is the limited UAVs resources. In fact, the authors analyzed the feasibility of overcoming these constraints by combining and controlling multiple UAVs. In this reference, the paper explores programmable crowd-powered drones to create a federated cloud. Moreover, a scripting language is applied to coordinate flight trajectories of multiple drones, as well as multi-drone service management. Differently, in [8], a mixed integer programming problem has been formulated considering the traveling salesman problem with a drone station. The route distortion problem has been defined, and a lower bound of the number of drones needed to solve it has been proposed. Furthermore, the paper [9] proposes an UAV-assisted MEC network with air–ground cooperation, in which both UAV and ground access points exhibit a direct link towards devices and cooperate to execute tasks computation, aiming at minimizing the worst delay and optimizing the resource allocation by jointly controlling UAV-device matching, UAV horizontal and vertical position, bandwidth selection, and task splitting. A two-layered decision-making framework for the cooperation between one or more stations and one or more drones is presented in [10], maximizing profit, and minimizing the travel distance.

G/G/1 queuing systems have been the object of the analysis proposed in [11], in which a shift parameter has been introduced to model the time lag under the assumption of exponential, hyperexponential, and Erlang distributions. Furthermore, paper [12] addresses multiple vehicle-to-vehicle (V2V) connections sharing spectrum with multiple capacity-hungry links. The main goal of the paper has been the resource allocation and packet sampling rate optimization of V2V connections, aiming maximizing the sum ergodic capacity of the network, as well as guaranteeing the age-of-information outage probability of V2V links. Authors in [13] propose an online optimization of both the UAV trajectory and the user association, in order to reach finite queueing delay minimizing UAVs energy consumption. In paper [14], a G/D/1 queuing model for the analysis of network-on-chip has been proposed and studied by resorting to a Jackson queuing network. Authors in [15] consider a hybrid aerial-ground scenario, where the offloading is exploited to perform UAV visual target tracking. Such a deep learning task is sent to an EC node, to meet the constraints on the computational resource and energy capacity typical of UAVs. The aerial-terrestrial communication links are also studied in paper [16], where the multi-task learning is adopted in combination with the reflecting intelligent surfaces (RIS) to improve coverage. An adaptive RIS-assisted transmission protocol, where the channel estimation, the transmission policy, and the data transmission are independently implemented in a frame, is designed. Differently, in [17], a multi-task resource scheduling framework exploiting the deep reinforcement learning has been designed with the objective to minimize the energy consumption of all users and UAVs in the system. Authors in [18] integrate horizontal federated learning with double deep Q-network to solve the problem of the computation offloading and relay communication in air-ground integrated networks, considering emergency scenarios. In reference to the offloading problem, the objective is the minimization of the weighted sum of both delay and energy consumption. For the data transmission, the main goal is to maximize the minimum rate of relay links.

An autonomous network resource demand prediction scheme has been proposed in [19], exploiting queuing theory. More in depth, the analysis addressed in [19], accurately measures the mathematical expectation of queuing length experienced by packets, and the average occupied resources usage in nodes, taking into account the success rate of communication resource transmission and the limited caching availability on nodes. Then, paper [20] focuses on multipath technology within the context of Internet of things (IoT) monitoring and control applications. Two paths with different strategies have been considering, exploit redundancy and coding to enhance timing performance of wireless communications. In this picture, data blocks have been modeled via a Markovian and a deterministic process, respectively. Then, the packet delay and the peak age of information metrics have been analyzed. While there is a wide range of works that deal with studying computational offloading scenarios where UAVs and edge computing coexist, and other works extensively apply the results of queuing theory, our work combines Lindley’s analysis with this kind of landscape. In fact, for the best of authors’ knowledge, this is the first paper introducing the Lindley’s analysis to obtain a measure of the outage probability within an offloading problem.

III. PROBLEM STATEMENT

A. System Scenario

As depicted in Fig. 1, in this paper, we mainly focus on a scenario where we have an edge computing system devotes to monitoring and control a process in a remote area to face an unpredictable overload of computation requests, e.g., related to the management of an emergency situation. In this case, an efficient and flexible approach is to resort to the deployment of a swarm of UAVs having on board computation capabilities in order to enable an integrated ground-air edge computing infrastructure (ECI), where computation capabilities are located at the ground ENs or on the UAV-ENs. In particular, we have a set [TeX:] $$\mathcal{C}$$ of processing nodes formed by a set of ground ENs [TeX:] $$\mathcal{S}=\{1, \cdots, S\}$$ able to perform computation, and a swarm of UAVs [TeX:] $$\mathcal{V}=\{1, \cdots, V\}$$, each one having on-board computation capabilities and linked to almost one SBS of the ground cellular network. Hence, we have an overall set [TeX:] $$\mathcal{C}=\{1, \cdots, S\} \cup\{1, \cdots, V\}$$ of possible computation nodes. Note that the elements of both sets [TeX:] $$\mathcal{S} \text{ and } \mathcal{V}$$ are heterogeneous in terms of computational capabilities, i.e., mean computation time, with UAV-ENs less powerful in terms of processing speed than the ground ENs.

B. General System Assumptions

To complete the definition of the system scenario, we have made the following assumptions.

· Any device can access the ground-air ECI by means of the most suitable SBS station of cellular network in order to offload its task computation request to any possible EN site belonging to [TeX:] $$\mathcal{C};$$

· Any ground EN can be reached by a device through the ground cellular network to offload its task independently from the access SBS, i.e., the SBS directly linked to it;

· Any UAV assigned to the service area of interest can be linked¹, to almost one SBS, i.e., it belongs to [TeX:] $$\mathcal{V}$$ and, hence, to [TeX:] $$\mathcal{C}$$, with a given probability [TeX:] $$p_c;$$

¹ This simple Bernoulli statistical model takes into account the fact that, due to the UAVs motion, it may not always be possible to have connectivity with at least one ground SBS. For simplicity, without loosing generality of our analysis, we have assumed that the UAVs connection conditions does not change during the completion of the tasks allocation planning and that the UAV connection probability, [TeX:] $$p_c$$, with almost one ground SBS is the same for all UAVs.

· All the SBSs of the access cellular network form a full connected network, i.e., the task offloading to a given UAV-EN can be routed to the most suitable SBS (if any), linked to the UAV-EN of interest, independently of the access SBS. However, in such a context we have to take into account that each element [TeX:] $$c \text{ in } \mathcal{C}$$ is involved in providing computation service, according to a first-infirst- out (FIFO) policy, to previously allocated task flows related to control and monitoring procedures already activated in the operation area. In particular, such task flows (nominal flows in what follows) are characterized by independent general arrival and service processes with mean rate [TeX:] $$\lambda_c$$ tasks/s, [TeX:] $$\mu_c$$ tasks/s, respectively, with [TeX:] $$\mu_c \gt \lambda_c$$ in order to guarantee the stability at each computation node.

In such a context, we have to provide a suitable computation allocation for an additional set [TeX:] $$\mathcal{U}=\{1, \cdots, U\}$$ of tasks, related to new needs to make current procedures more specific to the context of interest. Each additional tasks is associated to only one device so that devices and tasks are cited interchangeably in what follows. Furthermore, in our model we have assumed that each task u requires computation completion with a given soft-deadline delay constraint [TeX:] $$t_{d, u}, u \in \mathcal{U} .$$ Such a constraint means that tasks are allocate even if their deadline is not satisfied. In fact, soft-deadline applications prefer to receive a delayed service rather than not receiving it at all. Moreover, all tasks in [TeX:] $$\mathcal{U},$$ allocated to a given node in [TeX:] $$\mathcal{C},$$ due to the adopted FIFO policy, access the service according to their allocation order and first with respect to any tasks belonging to the nominal flows arrived at that node after their allocation. However, all the nominal flows arrived before and waiting for service in the ground EN or UAV-EN queue maintain the acquired FIFO priority for access the service facility with respect to new computation arrivals.

C. Analytical Approach

The initial step in our analysis aims to determine the waiting time experienced by tasks in the set [TeX:] $$\mathcal{U}=\{1, \cdots, U\},$$ at the computation nodes due to the workload already allocated (i.e., nominal flows). Hence, our goal is to derive the probability density function (pdf) of the waiting time at a given computation node, modeled as a G/G/1 system, due to the presence of previously arrived tasks belonging to the nominal flow of that node.

In particular, the system under consideration is one where all the possible computation nodes exhibit independent interarrival times between tasks belonging to the relative nominal flow, with a general pdf [TeX:] $$A_c(t) \text {, for } \forall c \in \mathcal{C} \text {. }$$ Similarly, the task computation service times are independent with a general pdf [TeX:] $$B_c(t) \text {, for } \forall c \in \mathcal{C} \text {. }$$ In addition to this, we have assumed that only one server is available at each processing node and that the computation service, as stated before, is performed according to the FIFO policy. Understanding the behavior of a such G/G/1 system, even if under the FIFO queuing policy, typically poses a non-trivial challenge, requiring an appropriate methodology. Among various alternatives, the analytical approach outlined in this paper leads to the Lindley’s integral equation with solution obtained by resorting to the spectral factorization method [4]. Towards this end, by focusing on a given node [TeX:] $$c \in \mathcal{C}$$, we have that [TeX:] $$Q_c^{(n+1)}$$ is the waiting time (in queue) experienced by the (n+1)th task of the nominal data flow allocated on node c, given by

where [TeX:] $$x_c^{(n)}$$ is the computation (i.e., service) time of the task [TeX:] $$O_c{(n)}$$ belonging to the nominal data flow allocated at node c, whereas [TeX:] $$h_c^{(n)}$$ represents the interarrival time between two consecutive computation requests, i.e., [TeX:] $$O_c{(n)}, O_c(n+1)$$[4]. Denoting with [TeX:] $$d_c^{(n)}$$ the difference [TeX:] $$x_c^{(n)}-h_c^{(n)},$$ i.e., [TeX:] $$d_c^{(n)}=x_c^{(n)}-h_c^{(n)},$$ and considering the stochastic process [TeX:] $$\left\{Q_c^{(n)}, n=0,1, \cdots\right\},$$ we have that

Furthermore, being [TeX:] $$\mu_c\gt\lambda_c$$ for all [TeX:] $$c\in\mathcal{C}$$ we have that the stability condition is verified for all the processing nodes, hence, we have :

with [TeX:] $$W_c(t)$$ the stationary cumulative probability distribution (CDF) for the waiting time in the queue at node c. Likewise, the stationary CDF for the random variable [TeX:] $$d_c$$ assumed independent of n, results in :

Being, [TeX:] $$x_c$$ independent of [TeX:] $$h_c$$, we have:

where [TeX:] $$C_c(u)$$ is the pdf of the random variable [TeX:] $$d_c.$$ Hence, through some algebraic manipulations detailed in [4], skipped here due to space limitation, we obtain the Lindley’s integral equation in the following form:

and [TeX:] $$W_c(t)=0$$ for [TeX:] $$t \lt 0.$$

For the purpose of our analysis, we introduce the function [TeX:] $$\phi_{+c}(s)$$ defined as:

that can be easily recognized ad the Laplace transform of [TeX:] $$W_c(t).$$ In solving (6) with respect to [TeX:] $$W_c(t),$$ we resort here to the use of the spectrum factorization approach [4]. In particular, being [TeX:] $$\mathcal{A}_c(s) \text { and } \mathcal{B}_c(s)$$ the Laplace transform of [TeX:] $$A_c(t) \text { and } B_c(t),$$ respectively, the goal of the spectrum factorization approach, as detailed in [4], is to define two rational functions of [TeX:] $$s, \Psi_{+c}(s), \Psi_{-c}(s),$$ so that we have:

Moreover, the factorization provided in (8) has to respect the following properties [4]:

· For [TeX:] $$\operatorname{Re}(s)\gt 0, \Psi_{+c}(s)$$ results to be analytic with no zeros in the half-plane;

· [TeX:] $$\exists D$$ such that for [TeX:] $$\operatorname{Re}(s)\lt D, \Psi_{-c}(s)$$ results to be analytic with no zeros in the half-plane.

Once the factorization is provided, by resorting to the application of the Liouville’s theorem (see [4] for more details) the Laplace transform of the waiting time CDF, [TeX:] $$\phi_{+c}(s),$$ results in

Moreover, being by definition :

from (9) we have:

Therefore, [TeX:] $$W_c(t)$$ can be obtained by anti-transforming [TeX:] $$\phi_{+c}(s)$$ defined in (9) as

Hence, the pdf of the waiting time at node c can be derived as:

which completes our analysis concerning the waiting time characterization at each computation node due to the presence of the nominal flows.

D. Problem Formulation

This paper aims at minimizing the outage probability for the additional set of tasks [TeX:] $$\mathcal{U}$$ needing to be offloaded on the pool of heterogeneous computation nodes [TeX:] $$\mathcal{C}$$ previously committed to provide computation service to nominal data flows. Towards this end, we have to take into account that the set [TeX:] $$\mathcal{S}$$ of SBS nodes offer a fast service time with respect to set [TeX:] $$\mathcal{V}$$ of UAVs alternatives, mainly due to the different energy constraints. In performing our analysis, we have overlooked the set-up time required to acquire exclusive use of a communication channel by users. This assumption is obviously valid in the case of systems with dedicated channels (i.e., safety-critical applications) but it may be considered reasonable also for a random contention set-up phase, in particular, for the case under consideration, where we have a relatively low to moderate number of users linked to a same SBS. In addition, we did not consider transmission times in defining the deadlines, as according to [21], these times are negligible in our scenario. Nevertheless, as communication times usually represent a constant delay contribution, the proposed analysis can readily extend to encompass scenarios where their impact cannot be deemed negligible by a proper definition of the actual time deadline.

In particular, we propose in the next section an offloading scheme based on a matching algorithm to produce as outcome the allocation matrix [TeX:] $$\mathbf{A} \in\{0,1\}^{U \times(S+V)},$$ whose generic element [TeX:] $$\alpha_{u, c}=1$$ if the task of the generic user u belonging to [TeX:] $$\mathcal{U}$$ is allocated on the network node c, zero otherwise. The aim of our offloading scheme is to minimizing the outage probability for any task [TeX:] $$u \in \mathcal{U}$$ whose computation service time² [TeX:] $$s_{c,u}$$ at node c is assumed known. Hence, the outage probability for the generic task u with deadline [TeX:] $$t_{d,u}$$, offloaded on node c, hence, having computation time [TeX:] $$s_{c,u}$$ and suffering of a waiting time with pdf [TeX:] $$w_c{t}$$ due to the nominal flow perviously allocated on c , results in:

² The resulting computation service time at node c depends on the computation node capabilities and dimension of u in bytes, however assumed known.

where we have:

In this reference, the main objective of the paper is represented by the minimization of the mean outage probability of tasks belonging to [TeX:] $$\mathcal{U}$$, i.e.,

In this reference, in the next section a proper tasks allocation procedure on network nodes, heterogeneous in computational capability, is designed, in order to provide a tasks assignment arrangement able to minimize the number of offloaded tasks in outage, on the basis of the queue congestion at all the possible computation nodes.

In summary, the functional requirements of the proposed systems revolve around executing an effective allocation policy to minimize the outage probability of incoming tasks. This objective is achieved by employing a matching algorithm that considers task deadlines, the workload assigned to each computation node, and applies the Lindley’s equation. Additionally, the system ensures FIFO priority for tasks previously accepted by computation nodes, while newly allocated tasks take service priority over those arriving later.

IV. TASKS OFFLOADING SCHEME

A. Matching Game for Task Assignment

Recently, matching theory (MT) [22] has gained momentum to provide effective solutions to assignment problems. More specifically, the MT establishes mutually beneficial relations between the elements belonging to two opposite sets, taking into consideration the preferences of each element in being assigned to each element of the opposite set. In order to consider the level of satisfaction of each element in being assigned to the element of the opposite set, a list of preferences is created by each element belonging to the two sets. Therefore, the matching game has been formulated between the set of tasks to be offloaded in [TeX:] $$\mathcal{U}$$ and the set [TeX:] $$\mathcal{C}$$. Consequently, the metrics of the preferences lists have to be defined, in order to build both the tasks to be offloaded and the network nodes preferences lists. In this reference, the preference lists of each task u in [TeX:] $$\mathcal{U}$$ on each network node c are created considering the following metric

where [TeX:] $$s_{u,c}$$ is the service time experienced by task u on node c. Therefore, on the basis of (17), each [TeX:] $$u \in \mathcal{U}$$ sorts in ascending order the network nodes [TeX:] $$c \in \mathcal{C}.$$ Differently, the preferences lists of each network nodes c is built considering the deadline associated to each element of [TeX:] $$\mathcal{U}.$$ In fact, each network node c builds its preferences list by sorting in descending order tasks belonging to [TeX:] $$\mathcal{U},$$ considering their deadlines, i.e.,

The matching algorithm, reported in Fig. 2, acts as follows

1) Both the elements in [TeX:] $$\mathcal{U} \text{ and } \mathcal{C}$$ create their own preferences lists;

2) Each user [TeX:] $$u \in \mathcal{U}$$ proposes to be served by the most preferred [TeX:] $$c_u^*,$$ in accordance with its preference list;

3) Each network node receiving more than one computation requests selects the most preferred c among those proposing. Then, it rejects the other requests;

4) Repeat steps 1)–4) until all the users in [TeX:] $$\mathcal{U}$$ have been allocated.

Note that the proposed approach does not drop tasks in outage since we assumed as working hypothesis that requests have soft-deadline constraints. It is important to pose the emphasis on the fact that, in our problem, the quantity [TeX:] $$\epsilon_{c, i}$$ with [TeX:] $$c \in \mathcal{U},$$ decreases with respect to the original time deadline value as the matching algorithm proceeds, giving rise to preferences lists which dynamically change during the tasks assignment procedure. Such a variation of preferences lists during assignment process implies that the matching game here formulated results to be a matching game with externalities, i.e., a game in which the preference lists change in dependence on the allocations performed during the algorithm execution [22]. For this reason, since existing interdependencies and relations among the players’ preferences lists exist in the game, preferences lists need to be updated after each algorithm assignment.

Firstly, crucial property of the matching procedure developed requiring investigation is the algorithm termination. With the aim at performing the termination analysis, we focus on a worst case scenario, in which the following assumptions have been considered: i) There is only one network node c; ii) during each iteration, only one task is allocated on the c; In reference to steps 1)–4) of the algorithm previously introduced, and on the basis of working hypothesis i) and ii), the algorithm reaches termination in a number of iteration [TeX:] $$\iota$$ equal to the number of tasks, i.e., in [TeX:] $$\iota = |\mathcal{U}|$$ steps. Removing hypothesis i) and ii), the corresponding scenario is not worst case, and the algorithm terminates in a number of steps [TeX:] $$\iota = |\mathcal{U}|$$.

B. Complexity Analysis

In order to discuss the complexity of the proposed task offloading strategy, it is important to note that the proposed matching strategy has a computational complexity mainly related to the preference lists creation process of both the parts involved in the game, i.e., the tasks [TeX:] $$\mathcal{U}$$ and the network nodes [TeX:] $$\mathcal{C}$$ respectively. Therefore, to build its own preference list, each task orders the elements in the [TeX:] $$\mathcal{C}$$ set, according to (17), exhibiting a computational complexity, for each task, given by

that considering all the tasks in [TeX:] $$\mathcal{U}$$ results to be

Similarly, the computational complexity required by [TeX:] $$\mathcal{C}$$ for sorting elements of [TeX:] $$\mathcal{U}$$ is

Since in the proposed matching game, the preference lists building processes are the heaviest parts, in terms of temporal complexity. As a consequence, the overall computational complexity is

Generally, the number of network nodes is lower than the number of tasks. Then, due to the behavior of the proposed matching algorithm, the network nodes preference lists are built only once, since tasks deadlines do not change over time. Therefore, we have that the overall computational complexity results to be

C. Stability of the Proposed Matching Game

Due to the presence of dependencies among the players’ preferences, i.e., externalities, this class of matching games represents a kind of games for which there not exists any matching algorithm able to guarantee convergence to a stable matching [22], [23].

Before stability discussion and analysis, the following strictly-two-sided exchange-stability (S2ES) definition is given as a modified version of that originally proposed in [24].

Definition 1. Let [TeX:] $$\mathcal{Z}$$ be the final matching produced by the algorithm developed. Let [TeX:] $$\mathcal{Z}(u)$$ be the network node matched with the task u in the matching [TeX:] $$\mathcal{Z}.$$ The outcome matching [TeX:] $$\mathcal{Z}$$ is a S2ES matching if there not exists a pair of customers [TeX:] $$\left(u_1, u_2\right)$$ s.t.:

1) [TeX:] $$H_{u_1}\left(\mathcal{Z}\left(u_2\right)\right) \leq H_{u_1}\left(\mathcal{Z}\left(u_1\right)\right)$$ and

2) [TeX:] $$H_{u_2}\left(\mathcal{Z}\left(u_1\right)\right) \leq H_{u_2}\left(\mathcal{Z}\left(u_2\right)\right)$$ and

3) [TeX:] $$E_{\mathcal{Z}\left(u_1\right)}\left(u_2\right) \leq E_{\mathcal{Z}\left(u_1\right)}\left(u_1\right)$$ and

4) [TeX:] $$E_{\mathcal{Z}\left(u_2\right)}\left(u_1\right) \leq E_{\mathcal{Z}\left(u_2\right)}\left(u_2\right)$$ and

5) [TeX:] $$\exists \psi \in\left\{u_1, u_2\right\}$$ s.t. at least one of the conditions 1)−2) is strictly verified or

6) [TeX:] $$\exists \phi \in\left\{\mathcal{Z}\left(u_1\right), \mathcal{Z}\left(u_2\right)\right\}$$ s.t. at least one of the conditions 3) − 4) is strictly verified.

In other words, Definition 1 means that a swap is allowed if it implies an improvement to at least one between the players involved, and all the rest of the elements do not worsen. In order to discuss the stability of the proposed matching algorithm, we suppose the existence of a pair of tasks [TeX:] $$(u_1, u_2),$$ for which the conditions 1) − 2) of Definition 1 results to be satisfied. Furthermore, let [TeX:] $$u_1, \text{ and } u_2$$ be s.t. [TeX:] $$\mathcal{Z}\left(u_1\right)=c_1$$ and [TeX:] $$\mathcal{Z}\left(u_2\right)=c_2,$$ respectively. This necessarily means that

Focusing on condition 5) of Definition 1, by (24) and (25), and since the proposed assignment policy does not include any discard strategy, the probability of experiencing a completion time lower than the deadline cannot decrease during the assignment process. Therefore, the preference list of each already matched task cannot change after its assignment. Therefore, we have that at the most [TeX:] $$H_{u_1}\left(c_1\right)=H_{u_1}\left(c_2\right)$$ and [TeX:] $$H_{u_2}\left(c_2\right)=H_{u_2}\left(c_1\right) .$$ As a consequence, condition 5) is not verified. In the same way, supposing that the following conditions are true

we have that [TeX:] $$u_2=u_{c_1}^{\star} \text { and } u_1=u_{c_2}^{\star} \text {. }$$ Since [TeX:] $$\mathcal{Z}\left(u_1\right)=c_1$$ and [TeX:] $$\mathcal{Z}\left(u_2\right)=c_2,$$ this means that at the assignment instant conditions [TeX:] $$u_1=u_{c_1}^{\star} \text { and } u_2=u_{c_2}^{\star}$$ were true. Due to the fact that once a task is matched its deadline cannot change, (26) and (27) can be verified only if [TeX:] $$E_{c_1}\left(u_2\right)=E_{c_1}\left(u_1\right)$$ and [TeX:] $$E_{c_2}\left(u_1\right)=E_{c_2}\left(u_2\right) .$$ Therefore, the condition 6) is not verified and the proposed matching game reaches a configuration satisfying the S2ES property.

V. PERFORMANCE ANALYSIS

This section deals with the performance evaluation of the proposed tasks offloading scheme for the ECI system under the working conditions detailed in Section III-A. We start our analysis by validating the accuracy of the proposed G/G/1 system analysis based on the Lindley’s integral in comparison to a classical and more affordable Markov approach based on the assumption of both arrival and service processes as two independent memoryless processes with same mean values as those of the original processes. Furthermore, with the aim at validating the good behavior of the proposed matching algorithm (PMA), we provide performance comparisons with two alternative algorithms: The kolkata paise restaurant game (KPRG) [25], and the random algorithm (RA). In particular, in the RA case, for each task, the network node on which computation is performed is randomly selected with a uniform probability. Conversely, the KPRG game consists of a repeated game in which tasks simultaneously offer to network nodes to be supported for computation, on the basis of the preferences exhibited. Therefore, each task u proposes to the most preferred network EN, i.e., ground EN or UAVEN, on the basis of its preference list. Then, each network EN, receiving more than one proposal, randomly chooses one of the proposing tasks [22]. As for the system parameters definition, in compliance with [26], we have assumed, without loss of generality, for both arrival and service processes hypoexponential distributions, with pdfs and mean values given in Table I, considering, if not differently specified, 3 ground ENs and 3 UAV-ENs . Moreover, the deadlines associated to tasks belonging to [TeX:] $$\mathcal{U}$$ have been assumed heavy tailed distributed within the interval [30, 110] ms. Finally, we have assumed the probability that one UAV can be connected to almost one ground SBS, i.e., pc, equal to 0.8 and that the network topologies considered in deriving our simulation results are formed by ground ENs and UAV-ENs uniformly selected from the appropriate EN configuration alternatives as reported in Table I. Hence, with the ambition to highlight the advantages of the proposed analytical framework based on the G/G/1 model and Lindley’s analysis, we compare in Fig. 3, the obtained analytical predictions in terms of tasks outage probability with simulation results and analytical predictions obtained by resorting to the equivalent M/M/1 model (i.e., where the memoryless arrival an service processes have the same mean values of the actual ones) for which the the waiting time CDF can be derived in a closed form as [4]:

where [TeX:] $$\rho_c$$ is the ratio between the mean arrival and service rates of the equivalent memoryless processes for node c, with [TeX:] $$c \in \mathcal{C}.$$ Finally, in deriving these results we have assumed, as stated before, [TeX:] $$p_c=0.8 \text {. }$$ Fig. 3 clearly exhibits the better accuracy of the G/G/1 model based on the Lindley’s integral in comparison with the Markov approximation. Moreover, this figure highlights a very good fitting between the obtained analytical predictions and the simulation results that further validates the proposed analysis. As it is evident to note, the outage probability gets worse as the number of tasks increases. This is due to the fact that a higher number of tasks means a greater mean completion time, since the proposed approach does not drop any request. Furthermore, with the aim at confirming the goodness of the proposed PMA task offloading approach in comparison with the RA and KPRG alternatives, (all based on the G/G/1 model), Fig. 4 shows the outage probability as the number of tasks in [TeX:] $$\mathcal{U}$$ increases and [TeX:] $$p_c=0.8$$ As it is evident to note in the figure, the PMA approach exhibits better performance in comparison with the two considered alternatives. Such a trend is due to the fact that the PMA, through the preference lists metrics, minimizes the tasks completion time, that directly impacts the minimization of the outage probability. Differently, both the KPRG and the PMA introduce in the decision-making process a randomness which negatively impacts the system performance. In addition to this, Fig. 5 shows the outage probability as the number of ground ENs grows keeping the number of UAV-ENs fixed at 3 for [TeX:] $$p_c=0.8$$ Also in this case, the PMA results to be the best strategy in comparison to the alternative schemes taken into account. From Fig. 5, we can note that the outage probability decreases as the number of network nodes increases. This is a consequence of the fact that, as the number of network nodes grows, the computation capability of the system improves, impacting positively on the outage probability behavior. Likewise, Fig. 6 depicts the worst completion time as a function of the number of tasks. Once again, the PMA achieves lower values of the worst completion time, denoting that the proposed matching strategy actually provides a suitable tasks allocation discipline for the problem addressed. The same trend is confirmed in Fig. 7, where the worst completion time is shown as a function of the number of ground ENs, for a number UAV-ENs equal to 3 and [TeX:] $$p_c=0.8.$$ In addition, Fig. 8 depicts the system performance when we have an additional number of UAVs equal to the value reported in the x-axis. In the same way, Fig. 9 exhibits the performance behavior when an additional number of ECs equal to the value reported in the x-axis is introduced in the network. Consequently, the crossed analysis of Figs. 8 and 9 highlight that to increase the number of ECs lower the outage probability faster than the introduction of the same number of UAVs. This is evident since ECs have a greater computational capability than UAVs.

VI. CONCLUSIONS

This paper has focused on a scenario of a hybrid network environment, where computational capabilities are available at the ground ENs and on-board of UAVs. Such network infrastructure has to host computation of a newly arrived set of delay sensitive tasks, assuming the presence of existing nominal flows on the network. The focus of the paper is the minimization of the outage probability of a set of newly arrived tasks under the assumption that the involvement of all the computation nodes in serving nominal data flows are characterized by general independent arrival and service processes. As a consequence, each network node has been modeled as a G/G/1 system and the Lindley’s integral analysis, conducted on the basis of the spectrum factorization method [4], has been used in defining the proposed tasks allocation approach based on matching theory principles. Then, the stability of the proposed matching tasks allocation procedure has been also theoretically proved. Finally, with the aim at validating the proposed solution, different allocation procedures have been considered for comparison purposes. The better behavior of the proposed approach has resulted clearly evident from all the results provided here. Future works may include different scheduling policies, also introducing preemption disciplines to prioritize tasks based on the deadline. In addition, another interesting development for this research may be the investigation of per-flow performance bounds involving martingale envelopes theory.