Netidee Blog Bild
Formulating Edge Offloading Optimization Problem
Finding an optimized and feasible offloading solution (27.05.2024)
Förderjahr 2023 / Stipendien Call #18 / ProjektID: 6851 / Projekt: Reliability of Edge Offloadings

This blog is about formulating edge offloading as a constraint optimization problem and finding an optimized and feasible solution.

In our last blog, we described edge offloading queueing system that estimates application response time on edge-cloud infrastructure under a multi-device workload. Although response time is the most important objective in latency-sensitive applications, it is not the only one. In edge offloading, mobile devices are usually battery-powered and resource-limited for executing resource-intensive applications. Hence, they offload application tasks on remote edge-cloud servers to conserve battery supplies. However, executing application tasks on remote servers imposes resource utilization costs on mobile users because resources are rented by resource providers for executing offloaded applications. Therefore, it is vital to provide models of energy and resource utilization costs so that the derived offloading solution can optimize them effectively.

Device Energy Model

The purpose of the device energy consumption model is to estimate the device battery level and guide offloading decisions to minimize its depletion. We employ a multi-core smartphone energy model since the most common contemporary mobile devices are smartphones equipped with multiple CPU cores. The model incorporates various energy factors such as a number of active cores, utilization per core, CPU power baseline for several active cores, base, and utilization energy coefficients, and idling power-saving modes.

Resource Utilization Cost Model

The resource utilization cost model estimates monetary expenses imposed by utilizing remote resources owned by resource providers for offloading purposes. The first pricing option is to execute tasks locally on a device which is free of charge. The second option is offloading tasks on cloud data centers where cost is proportional to the time consumption of CPU cores and disk storage capacities. The third pricing option is offloading on edge where pricing incorporates extra penalty because edge resources provide low-latency response. Optimizing the resource utilization cost objective should guide offloading decisions towards minimal expences.

Constraint Optimization Offloading Problem

However, the aforementioned objectives are mutually conflicting where minimizing one objective can lead to exacerbation of other objectives. For instance, offloading a task from a mobile device to a remote edge server can speed up response time and save device energy but can lead to excessive monetary expenses. That is why we want to combine all three aforementioned objectives into a single consistent optimization problem where a solution will be a policy that is a trade-off between multiple objectives. Therefore, we formulated edge offloading as a constraint optimization problem to optimize and guarantee the feasibility of offloading policy. We illustrated the abstract constraint optimization problem in Figure 1.

Figure 1 Constraint Optimization Offloading Problem
Figure 1. Constraint Optimization Offloading Problem

The constraint optimization offloading problem consists of objectives, constraints, and variables. The optimization objectives are application response time, device energy consumption, and resource utilization cost which we want to optimize. The optimization constraints model edge characteristics such as limited resource capacities (CPU, memory, etc.) and tight application deadlines (e.g. response time) that have to be satisfied. The variables are adjusted or controlled to achieve the desired output, and that is finding a solution that will satisfy constraints and minimize objective functions. The solution will be an offloading policy that balances between different objectives and respects constraints. To achieve that, we transform a multiple-objective problem into a single-objective problem so that multiple objective values will be weighted and summed up. In this manner, the final solution will be a balanced one between the objectives.

Satisfiability Modulo Theory

To solve the formulated optimization offloading problem and output a feasible and optimized solution, we employ satisfiability modulo theory (SMT). The SMT is a formal method that expresses constraints and deadlines of real-time systems with constraint programming. The benefit of using SMT over other methods such as machine or deep learning is that it can provide a formal guarantee of the feasibility of a solution that satisfies constraints and objectives. Providing a guaranteed feasible solution is essential for applications that are latency-sensitive where response time deadlines should not be violated. The presented optimization offloading problem will be encoded into SMT formulas and solved by SMT solver which is a tool for solving logical formulas. The output of solving SMT formulas should be feasible offloading decisions that satisfy all constraints and objectives.

Future Steps

Our future steps are to try model failed and unavailable edge servers and integrate them into the offloading system model, and prototype the experiment where we evaluate our solution.

Josip Zilic

Profile picture for user Josip Zilic


Formal Methods
edge computing
Supervised Machine Learning
Markov Processes
Diese Frage dient der Überprüfung, ob Sie ein menschlicher Besucher sind und um automatisierten SPAM zu verhindern.
    Der datenschutzrechtliche Verantwortliche (Internet Privatstiftung Austria - Internet Foundation Austria, Österreich würde gerne mit folgenden Diensten Ihre personenbezogenen Daten verarbeiten. Zur Personalisierung können Technologien wie Cookies, LocalStorage usw. verwendet werden. Dies ist für die Nutzung der Website nicht notwendig, ermöglicht aber eine noch engere Interaktion mit Ihnen. Falls gewünscht, treffen Sie bitte eine Auswahl: