TL;DR
This paper proposes a novel hierarchical mobile edge computing (HI-MEC) architecture that leverages an auction-based approach to maximize service provider profits while ensuring user quality of service (QoS). By introducing field, shallow, and deep cloudlets, the system efficiently allocates computing and communication resources through a two-time scale optimization, balancing long-term resource pricing with short-term bandwidth allocation.
What Problem Does This Paper Address?
The proliferation of Internet of Things (IoT) devices and the increasing demand for real-time, computation-intensive applications necessitate efficient resource management at the network edge. Traditional cloud computing models struggle with latency and bandwidth limitations for mobile users. Mobile Edge Computing (MEC) aims to address this by bringing computation closer to users, but effectively managing and monetizing these edge resources, especially in a hierarchical setup with varying resource capabilities (from resource-poor field cloudlets to richer deep cloudlets), remains a challenge. This paper tackles the problem of how a service provider can optimally allocate these heterogeneous edge resources to maximize profit while guaranteeing user QoS, considering the dynamic nature of user demands and resource availability.
Methods
The paper introduces a Hierarchical Mobile Edge Computing (HI-MEC) architecture comprising three tiers of cloudlets: field, shallow, and deep, inspired by LTE-Advanced backhaul. A two-time scale optimization approach is employed:
- Longer Time Scale (Time Frame T): Focuses on VM pricing and distribution. This is formulated as a Binary Linear Programming (BLP) problem to maximize the service provider's profit. The profit is defined as Revenue minus Electricity Cost and Lost Revenue (due to QoS violations).
- Revenue: Determined by an auction-based pricing model, similar to EC2 spot pricing, where prices are set based on demand and supply.
- Electricity Cost: Accounts for both VM power consumption and idle PM power consumption.
- Lost Revenue: Penalizes the provider for network delay, prioritizing bids closer to the edge.
- Shorter Time Scale (Time Slot τ): Focuses on bandwidth allocation. This is formulated as a Convex Optimization problem to minimize user delay.
To handle the computational complexity of the BLP, two heuristic algorithms are proposed: one for VM pricing and another for VM distribution. A centralized optimal solution is derived for the bandwidth allocation problem using Lagrange multipliers.
Datasets
Not discussed in the paper. The authors use simulated data generated for their experiments.
Key Insights and Ideas
- Hierarchical Edge for Heterogeneous Resources: The HI-MEC architecture effectively models the reality of edge environments, where resources vary significantly from the "edge" (field cloudlets) to more aggregated points (shallow and deep cloudlets). This allows for a more nuanced and efficient resource allocation strategy.
- Two-Time Scale Optimization: Separating resource pricing/distribution (longer term) from bandwidth allocation (shorter term) is crucial. This acknowledges that VM prices and availability are more stable than immediate traffic demands, leading to a more practical and efficient system.
- Auction-Based Profit Maximization: Using an auction mechanism for VM pricing allows the service provider to dynamically adjust prices based on real-time demand and supply, maximizing revenue while also incentivizing users to bid based on their willingness to pay.
- QoS-Aware Resource Allocation: The inclusion of "lost revenue" in the profit function directly penalizes the provider for network delays, ensuring that QoS is a critical factor in resource allocation decisions, especially for latency-sensitive applications.
- Heuristics for Scalability: The development of heuristic algorithms for VM pricing and distribution is vital. The optimal BLP approach becomes computationally intractable with a large number of bids, making these heuristics essential for practical deployment in real-world scenarios.
Key Results
- Profitability: The heuristic algorithms achieve profits very close to the optimal solution, demonstrating their effectiveness in practical scenarios. For instance, in case 1, the heuristic profit is only slightly lower than the optimal profit across various bid numbers.
- Efficiency: The heuristic approach significantly reduces computation time compared to the optimal BLP solution, making it feasible for real-time decision-making. The heuristic solution is obtained in seconds, while the optimal approach's computation time grows rapidly with the number of bids.
- Bid Serving Ratio: The heuristic algorithms maintain a high ratio of served bids, comparable to the optimal approach, indicating that they effectively allocate resources to a substantial portion of user demands.
- Pricing Accuracy: The heuristic VM pricing algorithm provides prices that are generally close to the optimal prices, with slight variations that lead to a slightly lower number of served bids in some scenarios, as expected from a heuristic.
Limitations and Future Work
- Distributed Bandwidth Allocation: While a centralized solution for bandwidth allocation is derived, the paper suggests that investigating a distributed manner for bandwidth allocation, especially as the number of bids and links scales up, would be a valuable future research direction.
- Network Model Simplification: The paper assumes an optimally designed network in terms of connections and capacities. Future work could explore how the proposed HI-MEC architecture and resource allocation strategies perform under sub-optimally designed network conditions.
- User Mobility and VM Handoff: While the paper touches upon mobile users, a more in-depth study of how VM handoffs are managed across different cloudlet tiers during user mobility could be explored.
- Dynamic Network Conditions: The current model might assume relatively stable network conditions within a time frame. Investigating the impact of highly dynamic network conditions on the proposed algorithms would be beneficial.
Summary updated