Toward Hierarchical Mobile Edge Computing: An Auction-Based Profit Maximization Approach

Abbas Kiani, Nirwan Ansari

TL;DR

This paper proposes a novel hierarchical mobile edge computing (HI-MEC) architecture that leverages a two-time scale auction-based approach to maximize service provider profit while efficiently allocating computing and communication resources to mobile users. By introducing field, shallow, and deep cloudlets, the system dynamically prices and distributes resources, ensuring user Quality of Service (QoS) and optimizing resource utilization in a resource-constrained edge environment.

What Problem Does This Paper Address?

The proliferation of Internet of Things (IoT) devices and mobile applications has led to an explosion in data generation and computation demands. While cloud computing offers vast resources, its latency and bandwidth limitations are problematic for real-time, user-centric applications. Mobile Edge Computing (MEC) aims to address this by bringing computation closer to the user. However, existing MEC solutions often struggle with efficiently managing the limited and heterogeneous resources available at the edge, particularly in a dynamic environment with mobile users. This paper tackles the challenge of resource poverty at the edge by proposing a hierarchical MEC architecture and an auction-based mechanism to maximize the service provider's profit while ensuring user QoS. The core problem is how to optimally price, allocate, and distribute computing (VMs) and communication (bandwidth) resources among mobile users in a multi-tiered edge environment, considering both the provider's profit and the users' demands and QoS requirements.

Methods

The paper introduces a Hierarchical Mobile Edge Computing (HI-MEC) architecture with three tiers of cloudlets: field cloudlets (resource-poor, at the edge), shallow cloudlets (resource-middle, at aggregation points), and deep cloudlets (resource-rich, at the mobile backhaul). This hierarchy is designed based on LTE-Advanced backhaul principles.

The core of the proposed solution is a two-time scale optimization approach:

  • Longer Time Frame (e.g., minutes): VM Pricing and Distribution. This phase uses an auction-based profit maximization model. The service provider acts as an auctioneer, setting prices for Virtual Machines (VMs) based on demand and available resources. A Binary Linear Programming (BLP) model is formulated to maximize the provider's profit, considering revenue from served bids, electricity costs, and lost revenue due to network delay. To handle the complexity of the BLP, two heuristic algorithms are proposed:
  • VM Pricing Algorithm: Estimates the serving cost of VMs and determines the optimal local price and the number of bids to serve.
  • VM Distribution Algorithm: Assigns served bids to the most suitable Physical Machines (PMs) across the hierarchical cloudlets.
  • Shorter Time Slot (e.g., seconds): Bandwidth Allocation. This phase focuses on minimizing user delay by optimizing bandwidth allocation. A convex optimization problem is formulated to allocate bandwidth to served bids, considering link capacities and user QoS requirements. A centralized optimal solution is derived using Lagrange multipliers and Kuhn-Tucker conditions.

Datasets

Not discussed in the paper. The paper uses simulated data generated for evaluation purposes.

Key Insights and Ideas

  • Hierarchical Cloudlets for Edge Resource Management: The proposed field, shallow, and deep cloudlet hierarchy effectively models the heterogeneous resource availability at different levels of the edge network, allowing for a more granular and efficient resource allocation strategy.
  • Two-Time Scale Optimization: Separating VM pricing/distribution (longer time scale) from bandwidth allocation (shorter time scale) is crucial. This acknowledges that computing resource prices and availability change slower than dynamic traffic loads and user demands, leading to a more stable and efficient system.
  • Auction-Based Profit Maximization: Employing an auction mechanism for VM pricing allows the service provider to dynamically adjust prices based on real-time demand and supply, maximizing profit while ensuring that bids above a certain price are served.
  • Heuristics for Scalability: The complexity of the optimal BLP solution necessitates heuristic algorithms. The proposed VM pricing and distribution heuristics provide near-optimal solutions in a reasonable time, making the system practical for real-world deployment.
  • QoS-Aware Bandwidth Allocation: Minimizing network delay through optimal bandwidth allocation is directly linked to user satisfaction and is treated as a critical objective, especially for users served at deeper cloudlet tiers.

Key Results

  • Profit Maximization: The heuristic approach achieves profits very close to the optimal BLP solution, with the gap generally increasing with the number of bids but remaining within acceptable bounds. For instance, in case 1, with 2000 bids, the heuristic profit is approximately 12 dollars, while the optimal is around 13.5 dollars.
  • High Bid Serving Ratio: The heuristic algorithms serve a high percentage of submitted bids, comparable to the optimal approach. For example, in case 1 with 2000 bids, both heuristic and optimal approaches serve around 70-75% of bids.
  • Computational Efficiency: The heuristic algorithms are significantly faster than the optimal BLP solution, especially as the number of bids increases. For 2000 bids, the heuristic computation time is around 5.55 seconds, while the optimal approach takes approximately 458.86 seconds.
  • Price Estimation Accuracy: The heuristic VM pricing algorithm provides prices that are slightly higher than the optimal prices, leading to a slightly lower number of served bids, which is consistent with the observed profit and serving ratio results.

Limitations and Future Work

  • Distributed Bandwidth Allocation: The paper derives a centralized optimal solution for bandwidth allocation. Future work could investigate distributed bandwidth allocation mechanisms to further enhance scalability and resilience.
  • Network Model Simplification: The paper assumes an optimally designed network in terms of link connections. Future research could explore dynamic network topology and resource management in more complex and dynamic network environments.
  • User Mobility: While the system is designed for mobile users, the current model might not fully capture the complexities of highly dynamic user mobility and its impact on resource allocation and handoff.
  • Real-World Deployment: The results are based on simulations. Future work should focus on validating the proposed approach through real-world testbeds and deployments.

Summary updated

BibTeX
@article{kiani2017toward,
  author = {Abbas Kiani and Nirwan Ansari},
  title = {{Toward Hierarchical Mobile Edge Computing: An Auction-Based Profit Maximization Approach}},
  journal = {IEEE Internet of Things Journal},
  year = {2017},
  doi = {10.1109/jiot.2017.2750030},
}
Figure