Adaptive reverse task offloading in edge computing for AI processes

Contents lists available at ScienceDirect Computer Networks journal homepage: www.elsevier.com/locate/comnet Adaptive reverse task offloading in edge computing for AI processes Petros Amanatidis a,Dimitris Karampatzakis a,Georgios Michailidis a,Thomas Lagkas a,∗, George Iosifidis b aDepartment of Informatics, Democritus University of Thrace, Kavala 65404, Greece bDelft University of Technology, Delft 2628 XE, Netherlands ARTICLE INFO Keywords: Task offloading Optimization Edge computing Resource allocation AI processes ABSTRACT Nowadays, we witness the proliferation of edge IoT devices, ranging from smart cameras to autonomous vehicles, with increasing computing capabilities, used to implement AI-based services in users’ proximity, right at the edge. As these services are often computationally demanding, the popular paradigm of offloading their tasks to nearby cloud servers has gained much traction and been studied extensively. In this work, we propose a new paradigm that departs from the above typical edge computing offloading idea. Namely, we argue that it is possible to leverage these end nodes to assist larger nodes (e.g., cloudlets) in executing AI tasks. Indeed, as more and more end nodes are deployed, they create an abundance of idle computing capacity, which, when aggregated and exploited in a systematic fashion, can be proved beneficial. We introduce the idea of reverse offloading and study a scenario where a powerful node splits an AI task into a group of subtasks and assigns them to a set of nearby edge IoT nodes. The goal of each node is to minimize the overall execution time, which is constrained by the slowest subtask, while adhering to predetermined energy consumption and AI performance constraints. This is a challenging MINLP (Mixed Integer Non-Linear Problem) optimization problem that we tackle with a novel approach through our newly introduced EAI-ARO (Edge AI-Adaptive Reverse Offloading) algorithm. Furthermore, a demonstration of the efficacy of our reverse offloading proposal using an edge computing testbed and a representative AI service is performed. The findings suggest that our method optimizes the system’s performance significantly when compared with a greedy and a baseline task offloading algorithm. 1. Introduction The rapid development of computing resources and the increasing storage capacities of IoT devices has helped to develop as well as improve many applications. This has the effect of moving data processing from centralized cloud environments to decentralized edge computing [1,2]. Today there is an increasing number of services that require the collection and processing of data so as to extract valuable information. Indeed, the term edge intelligence has been recently coined to describe a gamut of applications that follow this paradigm [3–6]. Given the computation load and the need for specialized ML libraries, a prominent paradigm for the implementation of these services is edge computing, where the end devices (far edge) offload the most demanding of these tasks to nearby servers, e.g., cloudlets. In the last several years a remarkable number of studies explored the potential, and the different facets, of such computation offloading architectures [7–10]. One aspect that has started to gain a lot of traction is that these far-edge devices when in large numbers, can also serve as computation offloading terminals [11]. In fact, as more and more of ∗Corresponding author. E-mail address: [email protected] (T. Lagkas). these devices are deployed (billions of IoT nodes are expected) it is only reasonable to consider scenarios where larger nodes (at the edge or farther) send their tasks (perhaps after splitting them) to the far-edge for execution. Several researchers have worked on task offloading [12–14], most of them offloading tasks from end devices to servers for processing. Moreover, contributions in the development of different optimization methods to minimize power consumption and latency while maximizing the performance of edge computing applications have been presented [15–17]. On the contrary, ‘‘reverse’’ offloading, i.e., offloading tasks from the cloudlets to the end devices (see Fig. 1) has not been thoroughly studied. In this work, this reverse offloading idea, namely offloading from the server to the end devices, is proposed based on the formulation of an optimization problem for the overall performance. Our goal is to minimize the task completion time, which is defined as the longest subtask time, while considering accuracy and energy constraints. Considering that the end devices have heterogeneous computing times https://doi.org/10.1016/j.comnet.2024.110844 Received 18 April 2024; Received in revised form 1 September 2024; Accepted 3 October 2024 Computer Networks 255 (2024) 110844 Available online 9 October 2024 1389-1286/© 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ ). P. Amanatidis et al. Fig. 1. Reverse task offloading proposal. because of the dynamic network parameters and different deep learning models implemented, our optimization problem becomes challenging. To provide a more specific definition of our optimization problem, we first optimize the task distribution percentage to minimize the latency under energy consumption constraints. Then, we enrich the optimization problem providing the flexibility to end-devices to choose from a set of available deep learning models that are used for object detection services on images. This choice affects the latency, the consumed energy, as well as the mean accuracy of the system which is added as a constraint in the optimization problem. Numerically, this extra degree of freedom inserts a discrete variable in the optimization problem, thus making continuous optimization algorithms unsuitable. We solve this optimization problem using a novel adaptive offloading approach that combines stochastic algorithms, namely Genetic Algorithms (GA), with Linear Programming (LP). Finally, we also examine the behavior of the algorithms in large-scale scenarios and propose dedicated strategies. The outcomes demonstrate significant cost savings and improvements in performance. 1.1. Methodology and contributions We examine a wireless edge computing network model featuring nodes with diverse object detector models and a single access point. Within this network, each end device generates computer vision tasks, capable of local execution with specific accuracy and delay requirements. The end devices are interconnected via links with different capacities, consuming energy for the computation tasks. To be more precise, we investigate a method where an edge server distributes the workload among several end devices to optimize the processing speed of AI workloads. To illustrate this service, we focus on processing images (e.g., videos with a specific duration) that are sent from edge servers to the end devices, on which an object detector is applied to locate the objects of interest. Each end device possesses an object detector with a different characteristic, namely the neural network size, which practically means that every device disposes different performance and efficiency. The edge server algorithm decides the distribution or splitting of the images to the end devices. Making this decision involves evaluating the potential performance gains, which are measured in terms of latency. For this purpose, we suggest employing different optimization algorithms implemented in the edge server, to improve the performance of such IoT networks. Taking the conducted evaluation a step further, we develop comprehensive solutions implemented as ‘‘reverse’’ offloading algorithms. These solutions are evaluated through a series of experiments conducted on a wireless testbed consisting of 4 Raspberry Pis (RPis), along with the use of state-of-the-art object detector applications. Additionally, we leverage these experimental measurements to simulate larger networks, or more specifically we perform a numerical validation in a large-scaled testbed to illustrate the efficiency of the proposed methods. The results prove that the latency has been significantly reduced by our implemented strategy when compared to a greedy algorithm as used in [18–20] and a fixed task offloading baseline algorithm [21]. Moreover, our offloading method, which we call EAI-ARO, tailors its operation by taking resource availability into account. Therefore, this work adds the following contributions: •Performance Optimization. We propose the idea of reverse offloading where powerful edge nodes split their tasks and assign the subtasks to far-edge nodes. This is of great importance when it comes to edge computing services and IoT networks. The contribution of this paper consists in the formulation of optimization problems for finding the minimum-time assignment strategy while respecting accuracy and energy constraints. We design an adaptive reverse offloading algorithm (EAI-ARO) for the above problem which is adaptable to various AI tasks, diverse edge devices with varying hardware and processing capabilities, as well as resource limitations. •Distribution Strategies. We propose strategies for the distribution of the total task load based on the dynamic network conditions and the number of end devices. More specifically, when the number of end-devices turns the solution of the optimization problem to become too costly, we split the end-devices into clusters or more specifically into groups of devices and we optimize the distribution in each of these clusters separately. Moreover, we examine how the network conditions impact the frequency of optimization runs, i.e., the batch-splitting step. Computer Networks 255 (2024) 110844 2 P. Amanatidis et al. The proposed architecture and decision framework is evaluated in our wireless testbed with a common deep learning (object detection) task and a benchmark COCO dataset [22]. The experiments show that our proposed methods achieve considerable cost savings and performance gains. Furthermore, the results also illustrate that the EAI-ARO algorithm can be implemented in various edge computing topologies with many end devices, different processing capabilities and different kinds of AI tasks. The rest of the paper is structured as follows: In Section 2, we focus on exploring the literature. An introduction to the formulation of the optimization problems along with the proposed algorithms is provided in Section 3. Then, we present the results of our distribution mechanisms in Section 4. Last, in Section 5we conclude our work. 2. Related work This section presents different task offloading optimization approaches in edge computing networks used in recent literature. Computation Offloading. Task offloading involves identifying specific tasks or workloads that can be transferred from one device to another, ‘‘traditionally’’ from far edge to edge nodes. For instance the study [23] explored the domain of Multi-Access Edge Computing (MEC) enhanced by 5G technology. One effective method according to the authors in reducing latency was to offload computing tasks from end devices to edge servers within the edge network. This work introduced a Particle Swarm Optimization (PSO) based task offloading technique, which provided low latency and energy efficiency by optimizing the offloading process. In [24], the problem of optimizing computation offloading and resource allocation in a dynamic multi-user (MEC) system was tackled. The authors want to minimize the total energy consumption while taking into account the uncertain resource demands of different tasks and delay constraints. They formulate the problem as a MINLP problem and propose a Q-learning-based reinforcement learning method to solve it. To address the performance limitations of mobile devices (MDs) with limited battery and computing resources, the authors in [25] addressed the problem of optimizing computational offloading in MEC networks. By offloading tasks to neighboring mobile edge servers (MES), the authors’ fast and energy-efficient deep learningbased offloading technique (EFDOT) seeks to minimize overall costs, including service delay e and energy consumption. Real-time mobile application processing by investigating a MEC network opened new possibilities by Unmanned Aerial Vehicles (UAVs) [26]. The authors emphasize on minimizing system-wide computation costs in a dynamic environment where users generate tasks with time-varying probabilities by optimizing both edge server deployment and multi-user computation offloading. All these studies show the gains of the ‘‘traditional’’ offloading approaches attempted to optimize some of the objectives our work tries to optimize like minimizing the latency of the task execution, all with different algorithms like the PSO or with deep learning approaches. An approach that has been overlooked is the ‘‘reverse’’ offloading namely offloading from cloudlets to far edge devices. Furthermore, our work introduced a novel optimization method designed to enhance the efficiency of this reverse offloading approach. Cooperative offloading. This approach emphasizes collaboration between the far edge and edge nodes. Collaborative caching in an EC context has been the subject of several researchers [27], with the goal of reducing the overall system cost, which includes costs for quality of service (QoS) and data migration overhead. To address this complex problem, an online solution based on Lyapunov optimality conditions was devised, called the collaborative edge data caching problem (CEDC). In [28] the issue of computational complexity and resource constraints associated with artificial intelligence (AI) algorithms, which present many difficulties in augmented reality systems, was studied. However, the rise of MEC offers a potentially effective way to tackle these problems. In order to improve recognition accuracy, minimize inference delays, and consume less energy, this paper introduced a framework for video-based AI inference processes in MEC systems. To this end, a MINLP problem was formulated. The inference complexity model and the accuracy model were derived and improved through experimentation, leading to an iterative solution approach using alternating optimization. In [29] an attempt to address privacy concerns in MEC systems by increasingly adopting federated learning (FL) is presented. The challenge lies in finding a balance between the learning accuracy of FL and energy consumption usage. To address this trade-off, this paper presented the FL-TD3 framework, specifically designed for large spaces of states and energies in a continuous domain. A framework [15] was introduced to enable collaborative task execution in Internet of Things (IoT) networks with limited resources, specifically addressing challenges in edge data analytics. The authors proposed an auction-based algorithm to optimize task-node assignments, ensuring optimal execution accuracy and minimal delays. Another, cooperative task execution approach in [30] ensures the effective transfer of edge tasks to nearby IoT devices and the efficient execution of local IoT tasks. The authors highlighted the significance of two conditions for IoTassisted edge computing to succeed: maintaining the integrity of local IoT tasks and maximizing the use of computing resources to increase edge service throughput. Finally, all the above works execute different tasks like AI tasks or augmented reality tasks in a collaborative fashion while offloading from the far edge to the edge nodes (eg., edge servers). Our work has a different approach while having a non-cooperative fashion by executing the AI tasks sent from the cloudlet locally on the far edge device. The key component of this approach lies in finding the optimal task splitting decision according to the current dynamic systems parameters. Reverse offloading. Offloading from cloudlets to far-edge devices has not been thoroughly studied, although some attempts to implement reverse offloading have been conducted especially in VEC (Vehicular Edge Computing). In [11] a reverse offloading framework was presented to reduce the amount of computational workloads on VEC servers by offloading the vehicular computations to Cooperative Vehicle-Infrastructure Systems (CVIS). This framework attempted to minimize the latency of processing the workloads by optimizing the reverse offloading and resource allocation. To address the challenge of limited computational resources of VEC servers, because of the growing amount of sensor data generated, another reverse computing offloading framework making use of the computer power of vehicles was introduced [31]. In this method offloading decision-making and resource allocation have been studied, including Q-Learning-based algorithms and constrained Markov decision processes. It is clear that not many studies have been conducted which highlight the reverse offloading approach, especially when handling AI workloads. In this work, we try to enhance this approach for AI applications, such as Deep Learning, which have not been examined thoroughly in the last years. In conclusion, while recent literature provides valuable information on various aspects of edge computing, task offloading, and optimization methods, a particular need that our work studies derives from the gaps in the literature on reverse offloading. Our work contributes significantly to filling these gaps by presenting new reverse task offloading algorithms that specifically address the challenges of latency minimization while taking into account accuracy and energy consumption constraints in the context of artificial intelligence tasks, showing their effectiveness in practical scenarios through experimentation in a wireless testbed. 3. Model and problem formulation 3.1. Optimal task distribution We introduce our system model and the mathematical formulation of the respective problem. In Table 1, we show all the key parameters and decision variables we use. The system consists of a set of 𝑁 devices for which a batch of images 𝐵or else the Batch step is sent for Computer Networks 255 (2024) 110844 3 P. Amanatidis et al. processing from the edge server. The task to be executed by the devices is an AI task or more precisely an object detection task. Every device 𝑖 in our system implements a deep learning model (neural network) for object detection. The models may be of different size, thus differ in their computational performance, average accuracy and energy consumption (see Table 3). For every device 𝑖∈, the neural network used is described via its index 𝑦𝑖∈, where = {1,2,…, 𝑀}is a set of 𝑀neural networks. Our purpose is to obtain a system with different processing capabilities to reveal sharp trade-offs. In more detail, the devices of our system implement the Yolov8 [32] object detector. The devices with different characteristics and configurations provide in real-time the confidence (accuracy) of the detection executed on the transmitted images by the edge server. For each end device 𝑖, we introduce an optimization variable 𝑥𝑖∈ [0,1], which represents the portion of 𝐵sent to the end device 𝑖∈ [1, 𝑁]. We gather all these variables in a vector 𝐱= [𝑥1,…, 𝑥𝑁] ∈ [0,1]𝑁. Our goal is to minimize the maximum latency, i.e., the time to process all the images sent from the server to the end devices. For each device the latency is defined here as the total time needed for the communication with the server (𝑇𝑖 𝑡𝑥) and the execution of the object detection process (𝑇𝑖 𝑑𝑙), i.e.,: 𝐿𝑖(𝑥) = 𝑥𝑖𝐵𝑇 𝑖 𝑡𝑥 +𝑥𝑖𝐵𝑇 𝑖 𝑑𝑙(𝑦𝑖) = 𝐶𝑖𝑥𝑖, where: 𝐶𝑖=𝐵(𝑇𝑖 𝑡𝑥 +𝑇𝑖 𝑑𝑙(𝑦𝑖)). Moreover, in real-life applications, one further needs to take into account the available energy of each device to ensure that the device has actually the capacity to perform the attributed tasks. This adds an extra constraint for each device, s.t.: 𝐸𝑖(𝑥𝑖, 𝑦𝑖)≤𝐸𝑖 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒, where: 𝐸𝑖(𝑥𝑖, 𝑦𝑖) = 𝑥𝑖𝐵 𝐸(𝑦𝑖) and 𝐸(𝑦𝑖)represents the energy consumed for the object detection process of one image by the neural network 𝑦𝑖. Then, the optimization problem can be expressed as follows: min 𝑥max 𝑖𝐶𝑖𝑥𝑖 s.t. 𝐸𝑖(𝑥𝑖, 𝑦𝑖)≤𝐸𝑖 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒, 𝑖 = 1,…, 𝑁 ∑𝑁 𝑖=1 𝑥𝑖= 1 𝑥𝑖∈ [0,1], 𝑖 = 1,…, 𝑁 (1) To avoid the non-differentiability of the 𝑚𝑎𝑥 operator in (1), we reformulate the optimization problem according to Taylor and Bendsøe [33]. We introduce a positive auxiliary optimization variable, denoted 𝑥0∈ [0,∞), which serves both as the cost function and as a uniform bound for all devices’ latency. The new optimization problem reads: min 𝑥,𝑥0 𝑥0(2.1) s.t. 𝐶𝑖𝑥𝑖≤𝑥0, 𝑖 = 1,…, 𝑁 (2.2) 𝐸𝑖(𝑥𝑖, 𝑦𝑖)≤𝐸𝑖 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒, 𝑖 = 1,…, 𝑁 (2.3) ∑𝑁 𝑖=1 𝑥𝑖= 1 (2.4) 𝑥𝑖∈ [0,1], 𝑖 = 1,…, 𝑁 (2.5) 𝑥0≥0(2.6), (2) which is a linear programming (LP) problem and can be solved via standard dedicated algorithms (SIMPLEX, etc.) [34–36]. In more detail, the objective function (2.1) contains merely the auxiliary variable 𝑥0. The additional constraints due to the problem reformulation are shown in (2.2). Then, the energy constraints, ensuring that each device disposes the required energy to perform the attributed tasks, are shown in (2.3). Eq. (2.4) imposes the sum of portions {𝑥𝑖}𝑖=1,…,𝑁 of 𝐵sent to Table 1 Key parameters and variables. Description Parameters/Variables 𝑥𝑖Percentage of the total number of images for every device 𝑖. 𝐵Batch of images for processing (Batch step). 𝑇𝑖 Tx Time to send a single image to device 𝑖. 𝑇𝑖 dl(𝑦𝑖) Time for executing the object detector on a transmitted image on device 𝑖, using the neural network 𝑦𝑖. the end device to be equal to 1. Finally, Eqs. (2.5) and (2.6) are bound constraints for the optimization variables. Our optimization method is an adaptive offloading technique that monitors the device and network characteristics and optimally distributes tasks among devices based on the current condition of the system. Remark. In the above formulation for the latency, a major assumption is made. The network characteristics (𝑇𝑖 Tx) are assumed to remain constant until the end of the task execution process. This reasonable assumption simplifies significantly the formulation and the solution of the optimization problem. Our experimental results, presented in the sequel, validate that this does not affect significantly the expected performance, as long as the network speed fluctuates within some expected interval. 3.2. Optimal task distribution and neural network selection In Section 3.1, the neural network index 𝑦𝑖for each device is considered to be fixed, i.e., each device implements a predetermined object detector. In this Section, we add a discrete optimization variable, denoted as 𝑦= [𝑦1,…, 𝑦𝑁], that represents the neural network selection used for the object detection at each end device. In more detail, this variable represents the object detector model files which have different sizes and are located on every end device. The edge server in this case not only provides the splitting of the images but further decides for every end device which model it should use in order to optimize the overall performance. For problem (2), which does not include a predefined object detection accuracy constraint the optimal choice of neural network is trivial, since the fastest neural network is also the less energy consuming and constitutes evidently the optimal choice. However, this choice produces the worst possible mean accuracy, which is also a critical performance parameter to consider. To obtain a meaningful problem, we define the normalized mean accuracy of the whole object detection process as: 𝐴(𝑥, 𝑦) = 𝑚𝐴𝑃 (𝑥, 𝑦) − 𝑚𝐴𝑃𝑚𝑖𝑛 𝑚𝐴𝑃𝑚𝑎𝑥 −𝑚𝐴𝑃𝑚𝑖𝑛 ,(3) where: 𝑚𝐴𝑃 (𝑥, 𝑦) = ∑ 𝑖 𝑚𝐴𝑃 (𝑦𝑖)𝑥𝑖(4) and 𝑚𝐴𝑃𝑚𝑖𝑛, 𝑚𝐴𝑃𝑚𝑎𝑥 represent the minimum and maximum mean Average Precision possible, i.e., the average precision provided by the smallest and largest neural network correspondingly. Then, we add an accuracy constraint stating that the minimum normalized accuracy achieved in the processing procedure must be greater than a threshold value defined by the user. The new optimization problem reads: min 𝑥,𝑥0,𝑦 𝑥0 s.t. 𝐶𝑖𝑥𝑖≤𝑥0, 𝑖 = 1,…, 𝑁 𝐸𝑖(𝑥𝑖, 𝑦𝑖)≤𝐸𝑖 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒, 𝑖 = 1,…, 𝑁 𝐴(𝑥, 𝑦)≥𝐴𝑚𝑖𝑛, 𝐴𝑚𝑖𝑛 ∈ [0,1] ∑𝑁 𝑖=1 𝑥𝑖= 1 𝑥𝑖∈ [0,1], 𝑖 = 1,…, 𝑁 𝑥0≥0 (5) Computer Networks 255 (2024) 110844 4 P. Amanatidis et al. 3.3. Solution of the mixed integer non-linear optimization problem The optimization problem (5) is a MINLP which is not suited for gradient-based algorithms. Treating the discrete variables as continuous and then rounding the optimized values to the closest integers does not guarantee the optimality nor the satisfaction of the constraints. An alternative option consists in adopting stochastic algorithms, which can be adjusted to treat both discrete and continuous variables. However, several limitations emerge under this perspective. First, the computational complexity increases exponentially with the number of discrete optimization variables and it is even worse for continuous variables. Second, handling several constraints in stochastic algorithms is tricky and it can lead to poor convergence. Consequently, since the speed of the algorithm is a crucial parameter for the practical applicability of our method, using purely stochastic algorithms is not relevant. To circumvent the aforementioned inconveniences we propose a mixture of a stochastic algorithm and linear programming, that is able to handle problem (5) efficiently. We exploit the fact that, for a fixed choice of neural network indices 𝑦, problem (5) is a linear programming problem in low dimension and can be solved rapidly using dedicated algorithms. Therefore, we delegate to the stochastic algorithm only the search of the optimal 𝑦, while all the rest information (optimal task distribution, constraints satisfaction) derives from solving, for fixed 𝑦, the following linear programming problem: min 𝑥,𝑥0 𝑥0 s.t. 𝐶𝑖𝑥𝑖≤𝑥0, 𝑖 = 1,…, 𝑁 𝐸𝑖(𝑥𝑖, 𝑦𝑖)≤𝐸𝑖 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒, 𝑖 = 1,…, 𝑁 𝐴(𝑥, 𝑦)≥𝐴𝑚𝑖𝑛, 𝐴𝑚𝑖𝑛 ∈ [0,1] ∑𝑛 𝑖=1 𝑥𝑖= 1 𝑥𝑖∈ [0,1], 𝑖 = 1,…, 𝑁 𝑥0≥0 (6) To the best of our knowledge, this approach is novel in literature, at least in the framework of Reverse Task Offloading. For the numerical implementation of our approach, we have used a standard ‘‘𝜇+𝜆’’ Genetic Algorithm (GA) [37–39]. GA is a populationbased algorithm, where a set of candidate solutions (population) evolves during the iterations of the algorithm (generations) until a termination criterion is satisfied. The population evolution is principally determined by two nature-inspired operations: recombination and mutation. The recombination operation combines randomly chosen members of the current population (parents) to create ancestors for the next generation (offsprings), while mutation introduces random changes in a small portion of the ancestors. For the next generation, the best-performing members among parents and children are chosen, such that the total population size remains constant. Iterating this procedure is expected to overwrite characteristics of dominant solutions over the population, such that after some point no further improvement is achieved, indicating algorithmic convergence. The pseudo-code of the EAI-ARO algorithm is shown in Algorithm 1. In line 1, the initial population 𝐵(0) 𝑝is created. It is composed of 𝜇 𝑦vectors containing combinations of the neural network indices. Lines 2–13 contain the optimization loop that iterates until some convergence criterion is satisfied. In every iteration, steps 3–12 are repeated. More precisely, lines 3–9 describe the creation of the offsprings population. In line 4, two members of 𝐵(𝑔) 𝑝are randomly chosen to become parents 𝑃𝑖for the new offspring. Applying the recombination (via crossover) operator on 𝑃𝑖we create the offspring 𝑂𝑖in line 5. Then, for a small percentage of offsprings, randomly chosen, we apply mutation in line 6 to obtain the final offspring  𝑂𝑖. In order to compute the fitness function for  𝑂𝑖, we solve the LP problem (6) in line 7, then compute the latency in line 8. Once the loop has been completed, we gather all offsprings and their corresponding performance in the offspring population 𝐵(𝑔) 𝑜 Table 2 Genetic Algorithm parameters. Optimization parameters Values Population size 100 Number of parents (𝜇) 50 Number of children (𝜆) 50 Number of mutants 10 max number of iterations 500 max number of successive refused iterations 100 in line 10. In line 11, we apply the so-called ‘‘𝜇+𝜆’’ selection operator to chose the best 𝜇members among the parents and ancestors. In line 12, we update the generation index before starting the new iteration. Algorithm 1 Mixed GA-LP algorithm (EAI-ARO) 1: g:=0, create initial population 𝐵(0) 𝑝 2: loop: 3: for 𝑖∶= 1 to 𝜆 4: random choice of parents 𝑃𝑖 5: 𝑂𝑖= recombination(𝑃𝑖) 6:  𝑂𝑖= mutation(𝑂𝑖) 7: solve LP problem (6) for  𝑂𝑖 8: calculate fitness 𝐹𝑖for  𝑂𝑖 9: end 10: 𝐵(𝑔) 𝑜= {  𝑂𝑖, 𝐹𝑖}𝑖=1,...,𝜆 11: (𝜇+𝜆):𝐵(𝑔) 𝑝= best(𝐵(𝑔) 𝑝, 𝐵(𝑔) 𝑜, 𝜇); 12: g:=g+1 13: until convergence criterion; After extensive numerical experiments, our choice of parameters for Algorithm 1appears in Table 2. Concerning convergence criteria, we terminate our algorithm after a maximum number of successive refused iterations, i.e., where the objective function does not reduce, or after some total number of iterations. 3.4. Greedy reverse task offloading algorithm We follow the methodology adopted in [18] and compare our proposed solution with a greedy algorithm, adjusted to fit the setup of our scenario. The used greedy algorithm assumes a fixed choice of neural network indices 𝑦and determines the task distribution variables 𝑥𝑖based on some notion of optimality [40]. It is composed of two steps detailed in the sequel. First, the task distributions 𝑥𝑖are determined to be optimal for the latency objective, neglecting the accuracy and energy constraints, i.e., they solve the optimization problem: min 𝑥max 𝑖𝐶𝑖𝑥𝑖 𝑠.𝑡. ∑𝑁 𝑖=1 𝑥𝑖= 1 (7) The analytical solution of (7) reads (see Appendix): 𝑥𝑖=𝐶 𝐶𝑖 ,where: 𝐶=1 ∑𝑛 𝑖=1 1 𝐶𝑖 .(8) Then, we apply a heuristic step to handle the accuracy and energy constraints. In case the initial task distribution violates the accuracy constraint, the algorithm gradually redistributes tasks by assigning fewer tasks to devices with lower accuracy and more tasks to devices with higher accuracy, until the accuracy constraint is satisfied. Finally, the algorithm ensures that the energy constraint for each device is respected by setting an upper bound for each variable 𝑥𝑖as: 𝑥𝑚𝑎𝑥 𝑖= 𝐸𝑖 𝑎𝑣𝑎𝑖𝑙𝑎𝑏𝑙𝑒 𝐵𝐸(𝑦𝑖), which is the highest task distribution respecting the energy constraint for each device. Computer Networks 255 (2024) 110844 5 P. Amanatidis et al. Fig. 2. Testbed topology. 4. Results In this section, we present both experimental and numerical results using the proposed adaptive offloading approach. Numerical results derive from solving numerically the optimization problem at stake using artificial network values for each link between the edge server and end device. On the other hand, experimental results correspond to the findings of our method when implemented in our testbed under real-world network conditions. In the first step, we present our testbed and compare the EAI-ARO with the fixed offloading baseline and greedy algorithm. The fixed offloading baseline algorithm offloads a predetermined percentage or portion of the task to each end device, regardless of its current network condition. More specifically, we evenly distribute tasks among devices in our testbed. Then, we examine how the expected gain in time varies with the characteristics of the network. Finally, we examine the efficiency of our approach for large-scale systems and propose a clustering technique that maximizes the gain in latency. 4.1. Testbed We present an edge computing setup that consists of four end devices, an edge server and a Wi-Fi access point, as shown in Fig. 2. The end devices correspond to Raspberry Pi’s 4 Model B with 4 GB of RAM along with the corresponding wireless network connections. They perform object detection tasks using YOLOv8, a deep-learning object detector. They use YOLOv8, a deep-learning object detector, to carry out object detection tasks. In more detail, the input for the YOLOv8 model corresponds to a 𝑛×𝑛× 3 array of image pixels, each of which can be represented as an integer or floating-point value. After downsampling this input array, a grid of cells is produced that suggests labels and bounding boxes for the objects in the dataset. As a result, a set of bounding boxes for the identified objects is produced, completed with labels and confidence values. Each end device may dispose several Table 3 Characteristics of object detection models. 𝑦𝑖index Input image size 𝑚𝐴𝑃 (𝑦𝑖)𝐸(𝑦𝑖)(W/image) 1 224 ×224 ×3 0.325 0.6 2 320 ×320 ×3 0.415 1.22 3 480 ×480 ×3 0.481 2.16 4 640 ×640 ×3 0.531 4.8 YOLOv8 models, implemented with different input image sizes, energy consumption values and mAP values, as shown in Table 3. The edge server, which is essentially a laptop powered by an i712700H CPU processor equipped with 32 GB of RAM, distributes batches of images (picked from the COCO dataset) for object detection to the four end devices simultaneously. The results, which include labels for every processed image and the corresponding bounding boxes, are then transmitted back by the end devices, the device that finishes the processing of the images last is considered as the latency. The total batch corresponds to 20 000 images of about 150 KB and every batch step equals 2000 images, i.e., the process completes after 10 batch steps. At the end of every task execution process, an optimization problem is solved taking into account the current network state (see Fig. 3), i.e., the inherent dynamic problem is approximated as a series of static problems. To better explain the imbalance between devices, each device in the network due to distance to the access point has a different range of network speed values. Specifically, those located closer to the access point benefit from a stronger connection and consequently higher network speeds, whereas devices situated further away experience weaker connections and reduced network speeds. The whole distribution mechanism is coded in Python. 4.2. Optimal task distribution In our first example, each end device 𝑖is attributed the corresponding object detector with index 𝑖, i.e., 𝑦= [1,2,3,4] is considered Computer Networks 255 (2024) 110844 6 P. Amanatidis et al. Fig. 3. Network status at every batch step. Fig. 4. Comparison of latency at each batch step between the fixed offloading, the greedy and the EAI-ARO algorithm. as constant. Moreover, the available energy is assumed to be equal to 20 000 (mAh) for all end devices. We search to optimize the task distribution between the devices solving the optimization problem (2) at every batch step for the testbed described in Section 4.1. In Fig. 4, we plot the numerical evolution of the latency at every batch step for the fixed offloading, the greedy, and the EAI-ARO algorithm. First, let us note that as long as the energy constraints remain inactive, both the used greedy and the EAI-ARO algorithms solve the optimization problem (2), i.e., the provided solutions are equivalent. Moreover, one can observe that their solution outperforms significantly the fixed task offloading at every batch step. In average, the gain in latency equals 73.5% for the numerical results and 72.3% for the experimental results (see Table 4). In Fig. 5, we also provide the corresponding evolution of 𝑥𝑖, i.e., the task distribution for each device at every batch step. It is obvious that due to the fact that device 1 has nearly 50% better network connection on average compared to the other devices, this leads to receiving almost 56% on average more task load at each batch step. The above gain highlights the importance of employing the EAIARO algorithm when handling time-sensitive applications. In fact, in case of a very bad connection between the server and some end device, which additionally may be provided with a slow object detection model, the fixed offloading algorithm may result in excessive processing time. This situation is avoided in the EAI-ARO approach by providing a sufficiently low task percentage to the corresponding device. Computer Networks 255 (2024) 110844 7 P. Amanatidis et al. Fig. 5. Evolution of distributions at every batch step and device. Table 4 Average latency for the results in Fig. 4. Results Fixed offloading (s) Greedy (s) EAI-ARO (s) Gain (%) Numerical 785 208 208 73.5 Experimental 779 215 215 72.3 4.3. Optimal task distribution and neural network selection In the following example, beyond optimizing the task distribution, each end device is further provided with the complete set of the available object detectors and the selection at each batch step, using the EAI-ARO method, is determined by the solution of the optimization problem (5). We examine the gains of our proposed method for two different thresholds (𝐴𝑚𝑖𝑛) of the accuracy constraint, which correspond to different fixed selections of neural networks for the greedy and the fixed offloading methods. More specifically, we examine the case of 𝑦= [1,1,1,1] and 𝑦= [2,2,3,4] that provide 𝐴𝑚𝑖𝑛 = 0 and 𝐴𝑚𝑖𝑛 = 0.47 correspondingly. Once more, we test our approach both numerically and experimentally. The obtained results (see Table 5) show that the proposed approach provides significant gains in terms of latency, compared to the greedy and fixed task distribution method. In Fig. 6, we plot the evolution of the latency at every batch step for all methods. As expected, the gain depends strongly on the specified accuracy threshold. In more detail, setting 𝐴𝑚𝑖𝑛 = 0 turns the optimal solution of 𝑦to become trivial and equal to [1,1,1,1], i.e., all three methods use the same neural networks. As we mentioned before if all devices dispose of the needed energy to perform the attributed tasks, the EAI-ARO and greedy approach results coincide. On the other hand, when the accuracy threshold is set to 𝐴𝑚𝑖𝑛 = 0.47, the optimal 𝑦choice is nontrivial, therefore there is margin for further gain. This is reflected in the results in Table 5. As expected the gain of the EAI-ARO method with respect to the greedy approach is smaller compared to the fixed task offloading algorithm. Finally, in Fig. 6(b) one may observe a sudden increase in latency for all methods at different batch steps. This increase corresponds to instances when some energy constraint becomes active, i.e., some device runs out of battery. It is clear from the latency evolution that the EAI-ARO algorithm is more robust since it is less affected compared to the other two methods. 4.4. Impact of network characteristics In this section, we test numerically the efficiency of our approach under different network conditions. In more detail, instead of a network that varies for each connection between the server and the end devices, we consider uniform network conditions. Three different scenarios are examined, shown in Table 6. For each scenario, we first optimize the task distribution considering fixed the Neural Network selection (see Section 4.2). The results are shown in Table 7. As expected, the gain is reduced for slower networks, since the object detection task becomes more significant than the image transmission for the latency. Then, we also provide the possibility to optimize the choice of the Neural Network used. The results appear in Table 8. One may verify therein the expected tendencies concerning the network speed, as well as the accuracy limit. 4.5. Large-scale testbed In the previous sections, we validated the efficiency of our proposal using a testbed comprised of four end devices. In order for the method (EAI-ARO) to be applicable for real-life applications, we need to further examine the efficiency of the approach in large-scale testbeds. This is achieved in a numerical framework described in the sequel of this section. 4.5.1. Clustering technique For small testbeds, as the one in Section 4.1, the time for the resolution of the MINLP problem can be assumed negligible compared to the processing time of the task. However, as the number of end devices increases, the cost of the Genetic Algorithm is expected to increase exponentially, in accordance to the possible combinations of indices composing the 𝑦vector. It shall be expected that the total time (processing +solution of MINLP problem) increases after some limit value of end devices, which also depends on the characteristics of the particular application (network status, batch step, testbed, etc.). When the number of end devices exceeds this limit value, devices shall be clustered to maximize the possible gain. For each cluster, a separate MINLP problem is solved. In our numerical test for detecting the optimal cluster size, we consider a testbed composed of 128 end devices. For the network status, Computer Networks 255 (2024) 110844 8 P. Amanatidis et al. Fig. 6. Evolution of latency for different accuracy thresholds for all task distribution methods. Table 5 Average latency and gain for the results in Fig. 6. Experiments Accuracy threshold Fixed offloading (s) Greedy (s) EAI-ARO (s) Gain (Fixed) (%) Gain (Greedy) (%) Numerical 0 238.6 238.6 169.1 29.1 0 Experimental 0 268 268 200 25.3 0 Numerical 0.47 707 555.7 397.7 43.7 28.4 Experimental 0.47 740.1 592 438.3 40 28.9 Table 6 Uniform network scenario characteristics. Network average speed (MB/s) Network speed interval (MB/s) 5.9 4.8–7 3.0 2.2–3.8 0.35 0.2–0.5 Table 7 Average latency for the uniform network scenario. Inteval (MB/s) Fixed offloading (s) EAI-ARO (s) Gain (%) 4.8–7 610 178 70.1 2.2–3.8 745 285.2 65.3 0.2–0.5 824 400 51.4 we consider random values varying between the limit measurements in Fig. 3. Provided the stochastic nature of our algorithm, to achieve reliable results, we execute the process 200 times for each cluster size in the set {4,8,16,32,64,128}. The outcomes of the calibration procedure are illustrated in Fig. 7. The cluster latency reduces as the number of devices in each cluster increases. This is expected since the degrees of freedom in the MINLP problem increases and the optimization algorithm (EAI-ARO) can achieve more efficient distributions and 𝑦combinations. However, gains are not significant for more than 16 end devices. On the contrary, the curve representing the total time presents a minimum value that is achieved for 32 end devices. This value is considered as the optimal configuration for the numerical tests in Section 4.5.2. 4.5.2. Numerical validation In this section, we create numerically testbeds in our heterogeneous scenario for 32 end devices which is the optimal configuration according to Section 4.5.1 and compare our EAI-ARO distribution proposal with the greedy and the uniform task offloading algorithm. The creation of the testbeds is performed by replicating the characteristics of the architecture described in Section 4.1. As in Section 4.5.1, the artificial network status is constructed by considering random values varying between the limit measurements in Fig. 3. First, we examine the optimal task distribution for fixed object detection models, solving the optimization problem (2) for different testbeds. The results appear in Table 9, validating a significant gain of 57.2% compared to the fixed task offloading algorithm. We highlight here that the solution of the optimization problem (2), which is a Linear Programming problem, requires negligible time to reach the global optimum and it can be extended without problem for much larger testbeds. Then, we provide the possibility for every device to implement any of the Neural Networks described in Table 3, solving the MINLP problem (5) for different testbeds and two accuracy limits. We highlight that for more than 32 end devices, which is the optimal cluster size found in Section 4.5.1, the clustering technique is applied. For the trivial 𝑦selection corresponding to 𝐴𝑚𝑖𝑛 = 0 the results are shown in Table 10. One can verify that our proposed method provides a gain in terms of latency of 39.2% compared to the fixed task offloading algorithm. For the non-trivial case of 𝐴𝑚𝑖𝑛 = 0.58 the results are also shown in Table 10. The gain in latency increases to 40% when compared to the fixed algorithm and 13.5% compared to the greedy algorithm, which verifies once more that the additional optimization variables corresponding to the object detection models enhance the performance of the system without reducing the mean accuracy. Reverse offloading can be beneficial in scenarios where the computational resources of edge devices are either idle or more effective for specific tasks than centralized cloud servers. In such cases, the adoption of reverse offloading is recommended. This method minimizes latency and prevents bottlenecks by reducing the requirement for continuous data transmission to the cloud, which is especially helpful in situations where network bandwidth is limited. To achieve faster response times, reverse offloading is particularly helpful for tasks requiring real-time processing or when the edge devices are located closer to the data source. Furthermore, by utilizing local processing power, this technique can increase energy efficiency by lowering the total energy consumption related to cloud computing and data transfer. Systems that use reverse offloading instead of the traditional task offloading in some circumstances can achieve better load balancing, improve reliability through localized processing, and provide more immediate feedback. 5. Conclusion We developed an effective optimization-based distribution mechanism for reverse task execution of AI applications in resourceconstrained IoT networks. The motivation behind this work derives from the rapid increase of computational power and the improved Computer Networks 255 (2024) 110844 9