🔢 mathematics

Joint Service Placement and Resource Optimization in Hierarchical Edge-Cloud Networks

This paper proposes a joint optimization framework for hierarchical edge-cloud IoT networks that simultaneously addresses service placement, edge-cloud cooperation, task offloading, and bandwidth allocation to minimize end-to-end latency and system costs, utilizing relaxation and successive convex approximation techniques to solve the resulting non-convex mixed-integer nonlinear programming problem.

Original authors: Vo Phi Son, Van-Dinh Nguyen, Minh-Tuong Nguyen, Tuan-Vu Truong, Toan D. Gian, Dinh Thai Hoang, Diep N. Nguyen, Symeon Chatzinotas

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vo Phi Son, Van-Dinh Nguyen, Minh-Tuong Nguyen, Tuan-Vu Truong, Toan D. Gian, Dinh Thai Hoang, Diep N. Nguyen, Symeon Chatzinotas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling city where millions of people (IoT devices) need to get things done instantly—like ordering food, playing a game, or monitoring their health. In this city, there are two types of kitchens: local neighborhood cafes (Edge Servers) and a massive central industrial kitchen (the Cloud).

The paper you provided is about how to run this city's "kitchen network" so that everyone gets their order fast, without the system crashing or the city running out of money.

Here is the breakdown of the problem and the solution, using simple analogies:

The Problem: A Chaotic Kitchen

In a Hierarchical Edge-Cloud network, things get messy very quickly:

The Menu Problem (Service Placement): The neighborhood cafes have limited shelf space. They can't stock every single ingredient (service) for every possible dish. If a customer wants a dish the cafe doesn't have, they have to wait for the central kitchen to send it, or ask a neighbor cafe. Deciding which ingredients to keep on the shelves is hard.
The Delivery Problem (Task Offloading): When an order comes in, who cooks it? The customer's own microwave (local device)? The local cafe? A neighbor's cafe? Or the big central kitchen? If everyone sends their orders to the central kitchen, the delivery trucks get stuck in traffic (latency). If they all go to one small cafe, that cafe burns out.
The Cost Problem: Keeping a cafe open, stocking ingredients, and paying for delivery trucks costs money. If you change the menu too often (installing and uninstalling services constantly), you waste a fortune on setup fees.

The Goal: The authors want to find the perfect balance to make two things happen simultaneously:

Speed: Get the "food" to the customer as fast as possible.
Savings: Keep the total cost of running the network low.

The Solution: A Two-Step Management Plan

The authors realized that trying to solve everything at once is like trying to plan a year's worth of menus while simultaneously cooking a single meal. It's too complicated. So, they broke it down into two different time scales:

1. The Long-Term Plan (The "Menu Strategy")

Timeframe: This happens rarely (e.g., once a day or week).
The Action: The system decides what services to install on which servers.
The Analogy: Think of this as the cafe manager deciding which ingredients to stock on the shelves for the next week. They look at the neighborhood's habits and decide, "We need to keep the pizza oven here, but we don't need the sushi station." They also decide which cafes should help each other (Edge-Edge cooperation) and which should rely on the big kitchen (Edge-Cloud cooperation).
Why? This ensures the network is stable. You don't want to change the entire menu every time a customer walks in.

2. The Short-Term Plan (The "Order Taker")

Timeframe: This happens constantly (every few seconds).
The Action: Once the menu is set, the system decides how to handle the current orders.
The Analogy: A customer walks in. The manager looks at the current traffic, the speed of the delivery trucks, and the energy of the staff. They decide: "Okay, since the pizza oven is busy, let's send this specific order to the neighbor cafe," or "Let's split this order: cook the dough here, send the sauce to the cloud." They also decide how much bandwidth (delivery truck space) to give to each customer.
Why? This adapts to real-time chaos, like a sudden rush of customers or a traffic jam on the road.

How They Solved the Math

The math behind this is incredibly difficult (described as "non-convex mixed-integer nonlinear programming"). In plain English, it's a puzzle where you have to choose between "Yes/No" options (install this service or not?) and "How much" options (how much bandwidth?) all at the same time, and the rules keep changing.

To solve this, the authors used a clever trick called Successive Convex Approximation (SCA):

The Analogy: Imagine trying to walk down a steep, jagged mountain path in the dark. It's dangerous and hard to find the bottom.
The Trick: Instead of seeing the whole jagged path, they pretend the path is a smooth, gentle slope for a few steps. They walk down that smooth slope, then stop, look at the real path again, and pretend it's a new smooth slope. They repeat this process, taking small, safe steps until they reach the bottom (the optimal solution).
The Penalty: They also added a "penalty" system. If the math suggests a weird "half-installed" service (like 0.5 of a pizza oven), the system adds a heavy fine to force the decision to be a clear "Yes" (1) or "No" (0).

The Results: Why It Works Better

The authors tested their method against other common strategies (like randomly assigning customers to cafes or always sending everything to the cloud).

Speed: Their method significantly reduced the time it took to get results (latency). It was much faster than just sending everything to the cloud or using random assignments.
Cost: It saved money by avoiding unnecessary service installations and reducing the need for expensive cloud data transfers.
Stability: By separating the long-term "menu" decisions from the short-term "order" decisions, the system didn't get overwhelmed by constant changes.

Summary

This paper presents a smart, two-layer management system for IoT networks. It separates the strategic decisions (what services to keep where) from the tactical decisions (how to route data right now). By using advanced math to approximate the best path through a complex maze, the authors created a system that is faster, cheaper, and more reliable than previous methods, ensuring that our connected devices get the low-latency services they need without breaking the bank.

Technical Summary: Joint Service Placement and Resource Optimization in Hierarchical Edge-Cloud Networks

Problem Statement
Hierarchical Edge-Cloud Computing (HECC) aided Internet of Things (IoT) networks face significant challenges in balancing low-latency requirements with system costs. The core difficulty lies in the joint optimization of service placement (determining where to deploy services), user association, edge-edge and edge-cloud cooperation, task offloading strategies, and bandwidth allocation. These decisions are complicated by heterogeneous computational resources, limited storage at edge servers (ESs), dynamic user mobility, and unstable wireless channel conditions.

The problem is formulated as a non-convex Mixed-Integer Nonlinear Programming (MINLP) problem. The objective is to minimize a weighted sum of the overall end-to-end (e2e) latency and the total system monetary cost (including service installation, uninstallation, operation, and cloud request fees). The problem is classified as NP-hard due to the strong coupling between binary decision variables (service placement, offloading paths) and continuous variables (bandwidth allocation, task partitioning), making it difficult to even find a feasible solution.

Methodology
To address the complexity of the MINLP formulation, the authors propose a hierarchical optimization framework that decouples the problem into two sub-problems operating at different timescales:

Long-Term Optimization (Service Placement & Cooperation): Executed over long-term time slots, this sub-problem optimizes binary decisions regarding service placement ( $g_s^k$ ), user association ( $\sigma_{m,s}^k$ ), and edge-edge/edge-cloud cooperation paths. To handle the binary constraints, the authors employ a Successive Convex Approximation (SCA) method combined with a penalty function. The binary variables are relaxed to continuous values in $[0, 1]$ , and a penalty term is added to the objective function to enforce convergence to binary values (0 or 1). The non-convex penalty function is iteratively approximated by a convex surrogate.
Short-Term Optimization (Task Offloading & Resource Allocation): Executed over short-term time slots within the long-term frame, this sub-problem optimizes continuous variables: the portion of tasks processed locally versus offloaded ( $\phi$ ) and bandwidth allocation ( $b$ ). The binary variables determined in the long-term phase are treated as fixed parameters. The non-convex constraints related to latency, energy, and data rates are convexified using SCA techniques, specifically by constructing lower-bound concave approximations for the rate and energy functions.

The overall algorithm (Algorithm 1) iterates between these two timescales. If the short-term optimization fails to meet latency requirements or if new service requests arrive, the system triggers a re-optimization of the long-term configuration.

Key Contributions

Unified Optimization Framework: The paper presents a comprehensive framework that jointly optimizes service placement, user association, edge-edge/edge-cloud cooperation, task offloading, and bandwidth allocation. Unlike prior works that often assume pre-installed services or focus on single-timescale optimization, this approach integrates long-term stability with short-term adaptability.
Novel Problem Transformation: The authors introduce three lemmas to simplify the complex coupling between service availability, connectivity, and task transfer conditions. These lemmas allow the reformulation of the original non-convex MINLP into a more tractable form.
Efficient Iterative Algorithms: By combining SCA and penalty-based techniques, the paper develops algorithms (Algorithm 2 for long-term and Algorithm 3 for short-term) that guarantee convergence to at least a local optimum. The complexity is analyzed, showing polynomial time complexity per iteration.
Cost-Aware Modeling: The objective function explicitly incorporates monetary costs for service deployment (installation/uninstallation) and operational expenses, alongside latency minimization, providing a more realistic system cost metric.

Numerical Results
Extensive simulations were conducted to evaluate the proposed framework against several benchmark schemes, including Branch-and-Bound (BnB), Fixed/Random User Association, schemes without edge-edge or edge-cloud cooperation, and fixed offloading rates.

Convergence: The proposed algorithms demonstrate fast convergence. Algorithm 2 (long-term) typically converges within 4-5 iterations, while Algorithm 3 (short-term) shows stable convergence even as network size increases.
Performance vs. Benchmarks: The proposed approach achieves performance within 1-2% of the optimal BnB solution but with significantly lower computational complexity.
Impact of Cooperation: Results indicate that disabling edge-edge or edge-cloud cooperation leads to system cost surges of 200-250% and significantly higher e2e latency.
Joint Optimization Benefits: Schemes that fix offloading rates or allocate equal bandwidth perform sub-optimally. The proposed joint optimization of offloading and bandwidth allocation consistently yields the lowest e2e latency.
Resource Sensitivity: Increasing the processing rate of edge servers reduces latency and system costs by enabling more local processing, though the proposed framework maintains stable costs even under varying user loads compared to fixed association schemes.

Significance and Claims
The paper claims that its primary significance lies in demonstrating the necessity of joint service placement and resource allocation to enhance system performance and efficiency in HECC-aided IoT networks. It argues that optimizing these components separately or ignoring the interplay between long-term service configuration and short-term resource dynamics leads to suboptimal QoS and inflated costs.

The authors emphasize that their hierarchical approach effectively balances system stability with adaptability to real-time demands, addressing the limitations of existing two-timescale approaches that often assume infrequent service placement updates. The results suggest that the proposed framework is a scalable and cost-effective solution for dynamic, resource-constrained IoT environments, offering a robust alternative to complex optimal solvers like BnB while outperforming heuristic or static benchmark schemes.