Source-linked AI summary
Towards Hierarchical Mobile Edge Computing: An Auction-Based Profit Maximization Approach
Abbas Kiani, Nirwan Ansari
TL;DR
The paper addresses how to allocate computing, storage, and communications resources efficiently in a resource-constrained edge environment. It proposes HI-MEC with field, shallow, and deep cloudlets, using two-timescale optimization for auction-based computing allocation and QoS-oriented communications allocation. Simulations and the proposed model demonstrate effective resource allocation for MEC subscribers.
Problem
Efficiently offering computing, storage, and communications resources remains challenging when edge facilities are resource-poor.
Method
HI-MEC introduces field, shallow, and deep cloudlets in an LTE-Advanced-inspired hierarchy and uses two-timescale optimization for computing and communications resources.
Results
The hierarchical model and two-timescale optimization platform are demonstrated to effectively facilitate resource allocation to MEC subscribers.
Takeaways & Limitations
The proposed architecture combines hierarchical cloudlet placement with auction-based computing allocation and QoS-oriented communications allocation.
Abstract
from arXiv · showhide
The multi-tiered concept of Internet of Things (IoT) devices, cloudlets and clouds is facilitating a user-centric IoT. However, in such three tier network, it is still desirable to investigate efficient strategies to offer the computing, storage and communications resources to the users. To this end, this paper proposes a new hierarchical model by introducing the concept of field, shallow, and deep cloudlets where the cloudlet tier itself is designed in three hierarchical levels based on the principle of LTE-Advanced backhaul network. Accordingly, we explore a two time scale approach in which the computing resources are offered in an auction-based profit maximization manner and then the communications resources are allocated to satisfy the users' QoS.
I. INTRODUCTION
The paper addresses resource allocation in user-centric IoT and MEC, where edge facilities are resource-constrained and users need computing, storage, and communications resources. It proposes HI-MEC, a hierarchical architecture with auction-based computing allocation and two-timescale resource management.
- MEC places computing capabilities near mobile users to reduce latency and improve QoS for IoT applications.
- Edge resource poverty makes it necessary to develop efficient strategies for offering computing, storage, and communications resources.
- HI-MEC introduces field, shallow, and deep cloudlets in three hierarchical levels based on LTE-Advanced backhaul principles.
- The paper uses two timescales: computing-resource prices and distributions change over longer frames, while bandwidth allocations update in shorter slots.
- Computing allocation is formulated as a Binary Linear Programming profit-maximization problem, while bandwidth allocation uses convex optimization.
- Heuristic algorithms are evaluated through extensive simulations, alongside a centralized solution for bandwidth allocation.
II. SYSTEM MODEL
The HI-MEC system model organizes edge resources into field, shallow, and deep cloudlets connected through an LTE-Advanced-inspired hierarchy. Its operation uses frames for profit optimization and shorter slots for delay-sensitive objectives.
- Network structure: The architecture provisions mobile edge computing services through cloudlets connected to access points and backhaul infrastructure.
- Cloudlet hierarchy: Field cloudlets are resource-poor facilities co-located with SCeNBs, shallow cloudlets are resource-middle facilities at PoPs, and deep cloudlets are resource-rich facilities at mobile backhaul.
- Network structure: Each SCeNB connects to one PoP through a dedicated last-mile link, while PoPs use dedicated aggregation links.
- Timescales: A time frame T is divided into equal-length time slots τ, such as five-minute frames and few-second slots.
- Timescales: The model seeks to maximize provider profit over each frame and minimize user delay over each slot.
A. Provider Side
The provider supplies VMs and communications bandwidth through cloudlet facilities, using demand-responsive auction pricing. Users submit willingness-to-pay bids, and bids above the spot price receive service and guaranteed bandwidth.
- Provider resources: The provider offers VM-based computing and communications facilities as an augmentation to mobile-device capabilities.
- Pricing: Flexible pricing is used to manage fluctuating demand under limited edge resources, following an auction-based model similar to EC2 spot pricing.
- Pricing: VM prices are updated at the beginning of each time frame according to available resources and demand.
- Pricing: The minimum computing-resource granularity is one VM instance during one time frame.
- User bids: Users submit bids stating their maximum willingness price for a desired VM type, informed by spot-price history.
- User bids: At each auction, bids above the spot price are served and bids below it are rejected, with bandwidth guaranteed for served bids.
- User bids: Multiple requested instances of one VM type are treated as separate bids with the same maximum willingness price.
III. PROBLEM FORMULATION
The provider jointly chooses VM prices, bid service decisions, and VM locations to maximize profit while satisfying communications requirements. The formulation uses local equilibrium pricing and accounts for costs and delay-related lost revenue.
- III. PROBLEM FORMULATION: The provider determines final VM prices based on served bids and assigns VMs among cloudlet locations while guaranteeing communications requirements.
- III. PROBLEM FORMULATION: The resulting optimization is an auction-based profit-maximization problem solved by the service provider.
- III. PROBLEM FORMULATION: Provider profit equals service revenue minus electricity costs and revenue lost because of network delay.
- A. Revenue: Revenue depends on the spot price selected for each VM type and the bids served at that price.
- A. Revenue: At each AP, all served bids for a VM type pay an identical local equilibrium price determined by demand and supply.
- A. Revenue: The revenue formulation sums willingness prices for served bids while accounting for the selected bid position and service decisions.
B. Electricity Cost
The framework models electricity cost from VM and physical-machine power consumption, while incorporating network delay and QoS into lost revenue. It prioritizes serving bids closer to the edge and updates bandwidth allocations according to traffic loads.
- Electricity-cost model: Electricity cost includes VM power consumption and physical-machine idle power consumption.The cost depends on active physical machines and VM distribution across them.
- QoS and lost revenue: The architecture represents low-latency service as a trade-off between network delay and profit through lost revenue.Lost revenue accounts for delay-related QoS effects and is weighted by provider-selected coefficients.
- Hierarchical service priority: Field cloudlets receive first priority, followed by shallow and deep cloudlets when local capacity is insufficient.The policy serves bids as close to the edge as possible and uses more distant tiers for high demand.
- Hierarchical service priority: A bid served at a deep cloudlet receives bandwidth on every traversed last-mile, aggregation, and mobile backhaul link.The allocated bandwidth is treated as a dedicated capacity between the bid’s AP and assigned cloudlet location.
- QoS and lost revenue: Bandwidth allocation is updated each time slot from the traffic loads of served bids.The profit maximization process uses an upper-bound utilization model before updating allocations.
IV. PROFIT MAXIMIZATION
The profit-maximization model responds to changing bids and user locations by optimizing service decisions at each time frame. Its objective balances revenue, electricity cost, and lost revenue under connectivity, capacity, bandwidth, priority, and binary-choice constraints.
- Model objective: The provider updates auction-based serving decisions periodically because users may submit, cancel, or revise bids and change AP locations.The auction-based profit is maximized at the beginning of each time frame.
- Model objective: The optimization objective maximizes Revenue−ElectricityCost−LostRevenue.This objective captures service income together with power and delay-related costs.
- Feasibility constraints: Constraint C1 requires each served bid to use a physical machine at a cloudlet connected to its AP.This enforces feasible AP-to-cloudlet placement.
- Feasibility constraints: Constraint C2 ensures assigned bids’ total resource demands do not exceed the hosting physical machine’s supply.The constraint limits resource allocation at each machine.
- Feasibility constraints: Constraints C3–C5 bound aggregate bid bandwidth on last-mile, aggregation, and backhaul links.The three constraints correspond to the network’s three link levels.
- Feasibility constraints: Constraints C6–C10 enforce revenue requirements, lower-index machine priority, and binary decision variables.C7 prioritizes lower-index physical machines at the same cloudlet location.
B. Heuristics
The paper replaces the computationally difficult binary linear optimization with two heuristics for VM pricing and distribution. These heuristics estimate profitable bid counts, then iteratively assign served bids to physical machines and cloudlets using utility and packing constraints.
- Motivation: The binary linear programming model offers flexibility but has computational complexity when solved optimally.The heuristic design targets high-quality solutions within a reasonable time.
- Complexity: The VM-distribution complexity is O(|B|^2 * |P| * |C|).The complexity grows with the number of bids and physical machines.
- Two-phase heuristic: The approach uses separate VM pricing and VM distribution phases.The pricing phase is Algorithm 1 and the distribution phase is Algorithm 2.
- VM pricing: VM pricing estimates serving cost from weighted physical-machine costs across connected field, shallow, and deep cloudlets.The estimate includes electricity cost and lost revenue before selecting a profitable number of bids.
- VM distribution: VM distribution creates a packing list for each feasible machine and computes its utility for the candidate bids.Packing depends on resource constraints and whether a bid can be served at that machine.
- VM distribution: The algorithm selects the favorite machine and cloudlet by comparing utilities, assigns the associated bids, and repeats after removing them from the served set.The process stops when all served bids are assigned or no suitable machine and location remain.
V. BANDWIDTH ALLOCATION
After VM assignment, the paper allocates bandwidth to served bids by minimizing total network delay across AP-to-cloudlet links. The model represents which links each bid traverses and includes capacity and allocation variables for the hierarchical network.
- Optimization objective: The bandwidth-allocation problem minimizes total network delay for served users between their APs and cloudlets.The allocated bandwidth for each served bid is the optimization variable.
- Scope: User-to-AP radio delay is outside this paper’s scope because radio resource allocation has been addressed elsewhere.The modeled delay concerns the network path from APs to cloudlets.
- Network representation: The model indexes served bids and network links, including last-mile, aggregation, and mobile backhaul links.Each bid has a corresponding AP and cloudlet location.
- Network representation: The binary variable v_mb equals 1 when bid b’s traffic traverses link m.This variable records each bid’s link path in the hierarchical network.
A. Convex Optimization
The paper formulates bandwidth allocation as a convex optimization with link-capacity and bid-level bounds, then derives a centralized solution using Lagrange multipliers. The optimal bandwidth for each bid depends on multipliers associated with its traversed links, although scaling to many bids and links remains a future challenge.
- Optimization objective: Bandwidth allocation minimizes total delay for served users while accounting for each user’s traffic load at the beginning of the time slot.The optimization applies to users served at shallow cloudlets or the deep cloudlet location.
- Constraints: Constraints bound each bid’s bandwidth between provider-selected lower and upper values and enforce physical link capacities.The bounds may reflect VM types and traffic loads, while each link’s total allocation cannot exceed R_m.
- Convex formulation: The bandwidth allocation problem is a convex optimization with 2N + M constraints.Its solution is derived using Lagrange multipliers and Kuhn–Tucker conditions, which are necessary and sufficient under the stated conditions.
- Optimal solution: Theorem 1 states that each bid’s optimal bandwidth can be obtained from optimal multipliers associated with its traversed links.For a deep-cloudlet bid, these include the last-mile, aggregation, and mobile backhaul links.
- Limitation: Distributed solution for scaling numbers of bids and links is left for future work.The paper notes that computational complexity may increase as served bids and links increase.
VI. SIMULATION RESULTS
The simulations compare heuristic and optimal auction-based resource-allocation approaches across two bid-demand cases. The heuristic achieves near-optimal profit and served-bid counts while requiring substantially less computation time, though its pricing can serve fewer bids.
- Simulation setup: The HI-MEC simulation uses five AP locations, 1Gbps link capacities, three VM types, and CPU, memory, and storage resources.The cloudlets have the same PM type but different numbers of PMs across hierarchical levels.
- Profit and runtime: The heuristic algorithm provides a suboptimal solution within a few seconds, whereas optimal BLP computation time grows rapidly with the number of bids.The comparison uses CVX, Gurobi, and MATLAB to simulate the BLP and two-phase heuristic approach.
- Profit and runtime: In both cases, the heuristic profit is quite close to the optimal profit.Figures 2 and 3 report profit gained in one time frame for cases 1 and 2.
- Served bids: The heuristic serves nearly the same number of bids as the optimal approach in both cases.The served-bid ratio is defined as served bids divided by total submitted bids.
- VM pricing: For the most demanded VM in each case, heuristic pricing is slightly higher than optimal pricing in most scenarios and serves fewer bids.The examples use m3 for case 1 and r3 for case 2; the served-bid difference is also reflected in Figures 4 and 5.
VII. CONCLUSION
The conclusion presents HI-MEC, a hierarchical mobile edge architecture with field, shallow, and deep cloudlets aligned with LTE-Advanced backhaul principles. It combines two-time-scale optimization for auction-based computing-resource profit maximization and bandwidth allocation, and is demonstrated to facilitate MEC resource allocation.
- Architecture: HI-MEC introduces field, shallow, and deep cloudlets in three hierarchical levels following LTE-Advanced mobile backhaul principles.Field, shallow, and deep cloudlets form the proposed hierarchical architecture.
- Optimization approach: The proposed platform uses a two-time-scale resource-allocation approach.The computing-resource and communications-resource allocation stages are formulated as separate optimization problems.
- Optimization approach: A BLP maximizes auction-based profit for concurrent VM pricing and VM distribution, while heuristic algorithms solve it in reasonable time.Bandwidth allocation is formulated as a convex optimization problem with a centralized solution.
- Conclusion: The hierarchical model and two-time-scale optimization platform are demonstrated to effectively facilitate resource allocation to MEC subscribers.