PaperlayerView exact revision on arXiv

Source-linked AI summary

Virtualization of 5G Cellular Networks as a Hierarchical Combinatorial Auction

Kun Zhu, Ekram Hossain

arXiv:1511.08256v1cs.GTcs.NI

TL;DR

Wireless virtualization requires two-level resource allocation that preserves efficient allocation, strict inter-slice isolation, and intra-slice customization while participants may act selfishly. The paper designs hierarchical combinatorial auctions with WDP algorithms and pricing schemes, achieving allocation efficiency and incentive compatibility at each level, while numerical results expose a welfare gap relative to general sharing.

  • Problem

    Wireless virtualization must allocate shared base-station resources between InPs, MVNOs, and users while satisfying efficiency, strict inter-slice isolation, and intra-slice customization.

  • Method

    The paper designs hierarchical combinatorial auctions with upper- and lower-level markets, WDP solution algorithms, and pricing schemes.

  • Results

    The proposed mechanism achieves allocation efficiency and incentive compatibility at each level for truthful bidders, with numerical results showing a welfare gap relative to general sharing.

  • Takeaways & Limitations

    The framework supports efficient per-level allocation, strict inter-slice isolation, intra-slice customization, and computationally tractable resource allocation for virtualized massive-MIMO 5G networks.

Abstract

from arXiv · show

Virtualization has been seen as one of the main evolution trends in the forthcoming fifth generation (5G) cellular networks which enables the decoupling of infrastructure from the services it provides. In this case, the roles of infrastructure providers (InPs) and mobile virtual network operators (MVNOs) can be logically separated and the resources (e.g., subchannels, power, and antennas) of a base station owned by an InP can be transparently shared by multiple MVNOs, while each MVNO virtually owns the entire BS. Naturally, the issue of resource allocation arises. In particular, the InP is required to abstract the physical resources into isolated slices for each MVNO who then allocates the resources within the slice to its subscribed users. In this paper, we aim to address this two-level hierarchical resource allocation problem while satisfying the requirements of efficient resource allocation, strict inter-slice isolation, and the ability of intra-slice customization. To this end, we design a hierarchical combinatorial auction mechanism, based on which a truthful and sub-efficient resource allocation framework is provided. Specifically, winner determination problems (WDPs) are formulated for the InP and MVNOs, and computationally tractable algorithms are proposed to solve these WDPs. Also, pricing schemes are designed to ensure incentive compatibility. The designed mechanism can achieve social efficiency in each level even if each party involved acts selfishly. Numerical results show the effectiveness of the proposed scheme.

I. INTRODUCTION

The paper frames wireless virtualization as a two-level resource-allocation problem involving InPs, MVNOs, and users, then proposes a hierarchical combinatorial auction to address it. The framework targets efficient allocation, strict inter-slice isolation, intra-slice customization, incentive compatibility, and tractable computation.

  • Motivation: Wireless virtualization separates infrastructure provision from services by partitioning base-station resources into isolated slices that MVNOs share and manage for their users.The shared resources include infrastructure, spectrum, power, backhaul/fronthaul, and antennas.
  • Problem: Resource allocation must accommodate dynamic user demands while preserving efficient allocation, inter-slice isolation, intra-slice customization, and social efficiency under self-interested agents.The challenge becomes hierarchical when InPs allocate slices to MVNOs and MVNOs allocate resources to their users.
  • Approach: The paper designs a hierarchical combinatorial auction with upper-level MVNO bidding to InPs and lower-level user bidding to MVNOs.MVNOs act as middlemen whose resource valuations depend on user demand and resale gains.
  • Trade-off: The hierarchical mechanism is sub-efficient because its allocation welfare can fall below the global optimum of direct general sharing.The gap is identified as a cost of introducing middlemen and trading global efficiency for intra-slice flexibility.
  • Mechanism properties: Winner determination problems, allocation algorithms, and pricing schemes jointly support incentive compatibility and efficient allocation at each auction level.The design also distributes computation between InPs and MVNOs and uses tractable algorithms for the WDPs.
  • Scope: The framework jointly addresses feasibility, admission control, and allocation while considering frequency, power, and spatial resources and both single-minded and general valuations.These design choices extend beyond schemes limited to one resource dimension or single-minded bidders.

B. Wireless Virtualization Model

The virtualization model treats isolation at the physical-resource level and adopts a hybrid scheme combining reserved resources with dynamic sharing. It describes auction procedures through bidding, allocation, and pricing stages.

  • Isolation model: Physical-resource isolation operates over subchannels, power, and antennas, trading implementation complexity against allocation efficiency and strictness.Higher-level isolation is simpler, whereas lower-level isolation can improve utilization at higher computational cost.
  • Isolation model: The hybrid isolation scheme reserves resources for each MVNO under service agreements while dynamically sharing leftover resources through auctions.The model can also accommodate MVNOs that already own certain resources.
  • Auction procedure: Auction participants are bidders, sellers, and an auctioneer, with procedures for submitting bids, allocating requested items, and charging winning bidders.A bid reflects a bidder’s private valuation of the requested item or bundle.
  • Auction procedure: The proposed wireless-virtualization mechanism uses two hierarchical combinatorial auction models with corresponding allocation and pricing procedures.The models are introduced for the two-level resource-allocation setting.

1) Single-seller multiple-buyer hierarchical auction model:

The single-seller hierarchical auction has two linked levels: the InP allocates physical resources to MVNOs, and each MVNO allocates its slice to subscribed users. Combinatorial allocation and pricing are used to support efficiency and truthful bidding.

  • Upper- and lower-level auctions: The upper-level auction treats the InP as seller and auctioneer, with MVNOs bidding for physical resources.The lower level contains one sub-auction per MVNO, where subscribed users bid for resources.
  • Resource isolation and availability: Each MVNO reserves resources and makes the resulting available resources accessible to its users in the lower-level auction.The available slice combines reserved resources with resources obtained in the upper-level auction.
  • Interdependence between levels: MVNOs are middlemen whose demands and valuations depend on resale revenue, so the two auctions must be designed jointly rather than as separate auctions.Unlike users, MVNOs do not have intrinsic demands or valuations for the resources.
  • Combinatorial valuation: Combinatorial auctions let bidders express preferences over resource bundles such as subchannels, power, and antennas.A bidder receives its valuation only when the requested bundle is fully allocated.
  • Mechanism properties: The mechanism targets individual rationality, incentive compatibility, and allocation efficiency through coordinated allocation and pricing schemes.Truthful bidding is a dominant strategy under the incentive-compatibility definition, and efficiency maximizes the sum of accepted-bid valuations.

2) Multiple-seller multiple-buyer hierarchical auction model:

The multiple-seller extension allows bidders to choose among sellers at each level, adding service selection and user association to the hierarchical auction. It specifies distinct bid representations for users and MVNO middlemen.

  • Multiple-seller extension: The multiple-seller model lets each bidder acquire resources from one of multiple sellers, increasing service-selection flexibility.At the lower level, users can associate with the MVNO that satisfies their resource requirement.
  • Auction administration: External service brokers act as auctioneers for MVNOs and InPs, determining allocation and pricing from submitted bids.The sellers themselves do not act as auctioneers in this model.
  • Auction formulation: The auction formulation addresses how users and MVNOs bid and how winning bids are determined in virtualized OFDMA-based 5G networks.The model is presented for wireless resources in networks using massive MIMO.
  • User bids: Single-minded users may submit a requested resource bundle and bid value, with valuation modeled linearly through achievable rate.The valuation is expressed as vk(rk(Sk)) = δkrk(Sk).
  • User bids: Users may instead state an intrinsic target rate, leaving the MVNO to determine the resource combination needed to meet it.The implicit bid is represented by the target rate and its associated bid value.
  • MVNO bids: MVNOs submit general valuations over possible resource bundles because they are middlemen without intrinsic demands or valuations.An XOR-bid restricts each MVNO to having at most one accepted bid.

B. How to Determine the Winning Bids?

The paper formulates winner determination problems for both auction levels and develops algorithms that allocate feasible resource bundles while maximizing accepted bid value. The solution approach combines exact dynamic programming with lower-complexity approximate methods under massive-MIMO-oriented assumptions.

  • WDP formulation: WDPs are formulated for the InP and MVNOs to determine accepted resource bundles while respecting available capacities and bidder allocation constraints.The InP’s constraints limit subchannels, power, and antennas, while ensuring each bidder receives at most one bundle.
  • WDP formulation: The MVNO-level WDP maximizes accepted bid value subject to total-power and subchannel-sharing constraints.For explicit requests, users are single-minded, making the MVNO problem simpler than the InP’s WDP.
  • WDP formulation: The implicit-request MVNO WDP jointly represents feasibility, admission control, and resource allocation through rate constraints and allocation-profile selection.Each user can have at most one accepted allocation profile, and the rate constraint determines whether the requested demand is satisfied.
  • Model assumptions: The formulation assumes homogeneous subchannels per user and rate independence from other users sharing a channel.These assumptions are motivated as practical for massive MIMO because channel decorrelation and averaged fading simplify the allocation model.
  • Solution algorithms: The reformulated WDP remains NP-hard, creating a tradeoff between social efficiency and computational complexity.Exact methods target small problems, whereas low-complexity algorithms seek approximate solutions for large-scale instances.
  • Solution algorithms: Dynamic programming partitions allocation across users and resource states to obtain an exact solution for the explicit-request MVNO WDP.The state records available subchannels and power at each stage, and the recurrence evaluates alternative allocations recursively.

2) Solving the WDP in the upper-level auction:

At the upper level, MVNOs submit XOR combinations of resource bundles, with valuations determined by resale gains from lower-level allocation. The InP can reduce computational complexity by restricting feasible bid combinations, at a cost to social efficiency.

  • Upper-level WDP: Upper-level MVNO bids are XOR combinations because MVNOs are not single-minded over resource bundles.Each bundle’s valuation depends on the resale gain obtained by solving the corresponding lower-level auction.
  • Upper-level WDP: The upper-level solution partitions allocation across MVNO stages and tracks available subchannels, power, and antennas as state variables.The stage allocation vector contains the quantities of each resource assigned to an MVNO.
  • Complexity control: Restricting bid combinations can reduce the complexity of finding exact optimal solutions when the number of MVNOs and resource groups is limited.The paper gives practical examples of few MVNOs and grouped subchannel sales as ways to shrink the bid space.
  • Complexity control: Restricting bid combinations introduces a tradeoff between computational complexity and social efficiency.The paper treats bid-space restrictions as a source of potentially lower efficiency.

D. How to Price the Winning Bidders?

The pricing design combines VCG pricing with a base access price to preserve incentive compatibility while addressing weak seller revenue under VCG alone. The resulting scheme supports approximate optimal seller revenue while maintaining incentive compatibility.

  • Pricing rationale: With truthful bids, maximizing the sum of accepted bids achieves social optimality at each auction level when bids equal valuations.The pricing scheme is therefore central to making truthful participation compatible with the allocation objective.
  • VCG pricing: VCG pricing charges a winning bidder for the welfare loss imposed on other bidders.VCG preserves incentive compatibility, but its revenue can be zero when all bidders’ requirements can be satisfied.
  • VCG pricing: VCG revenue can be inadequate for MVNOs because an MVNO’s valuation may decrease as the requested resource bundle grows.This issue arises when resale-based valuations depend on revenue generated from leased resources.
  • Combined pricing: The proposed scheme charges each admitted bidder the larger of a known base access price and the VCG price.The base price provides revenue protection, while the VCG component reflects the effect of serving one user on others.
  • Combined pricing: The combined pricing scheme preserves incentive compatibility and achieves approximate optimal seller revenue while auctioneers maximize social welfare.Under intense resource competition, larger requests can generate higher VCG prices because they may exclude more other users.

2) Pricing scheme with approximate solution for the WDP:

The mechanism combines VCG-like pricing with a base access price for approximate WDP solutions, while exact dynamic-programming solutions use VCG pricing. Its guarantees include incentive compatibility, individual rationality, and level-wise allocation efficiency, with stated limits for greedy and approximate cases.

  • Pricing scheme with approximate solution for the WDP: VCG pricing preserves incentive compatibility only when the WDP is solved exactly; approximate solutions generally require a different pricing design.The paper therefore proposes combining a base access price with VCG-like pricing for greedy allocation.
  • Pricing scheme with approximate solution for the WDP: The VCG-like price charges a winning bidder according to the highest normalized value among bidders it uniquely blocks.The final charge is the larger of this VCG-like price and the base access price.
  • Properties of the hierarchical auction mechanism: The proposed mechanism is individually rational for truthful bidders in both upper- and lower-level auctions.The proof considers whether a winning bidder blocks no bidder or at least one bidder under the pricing rule.
  • Properties of the hierarchical auction mechanism: With exact dynamic-programming WDP algorithms, the mechanism achieves allocation efficiency with truthful bidders at each level.The paper notes that allocation efficiency is not preserved for the entire hierarchical auction because of the hierarchy.
  • Properties of the hierarchical auction mechanism: Monotone allocation and critical-value payment yield incentive compatibility for the auction mechanism.A bidder’s winning chance increases by raising its bid or reducing its requested resource bundle.
  • Properties of the hierarchical auction mechanism: The dynamic-programming mechanism with VCG pricing and base access price is incentive compatible for single-minded and general valuations, while the greedy result is limited to single-minded users.The entire hierarchical auction is incentive compatible when each sub-auction is incentive compatible.

IV. EXTENSION TO A MULTIPLE-SELLER MULTIPLE-BUYER HIERARCHICAL AUCTION MODEL

The model is extended to multiple sellers and multiple buyers, allowing users to choose among MVNOs and MVNOs to choose among InPs.

  • IV. Extension to a Multiple-Seller Multiple-Buyer Hierarchical Auction Model: In the extended hierarchical auction, users can freely choose among several MVNOs, while MVNOs can choose among different InPs.This generalizes the single-seller multiple-buyer model to multiple sellers and buyers.

A. WDP Formulations

The extended model formulates upper- and lower-level WDPs for multiple InPs, MVNOs, and users, then uses relaxations and exact or approximate algorithms to make these problems tractable. Pricing schemes are matched to the solution method to retain the mechanism’s level-wise properties.

  • A. WDP Formulations: The upper-level WDP models whether each MVNO’s requested resource bundle is accepted by an InP, with each MVNO leasing from at most one InP.The formulation uses InPs as sellers and MVNOs as buyers in the extended auction.
  • A. WDP Formulations: The lower-level WDPs represent service-broker allocation for explicit and implicit user resource requests.The explicit-request formulation aggregates users across MVNOs, while the implicit-request formulation uses binary acceptance variables.
  • B. Allocation and Pricing Schemes: The resulting WDPs are equivalent to multiple multidimensional knapsack problems, for which dynamic programming may require huge memory.Branch-and-bound is proposed for exact solutions, with tight upper bounds identified as its key challenge.
  • B. Allocation and Pricing Schemes: Surrogate relaxation produces an upper bound for the WDP using a nonnegative multiplier vector, and the bound is tightened by minimizing the relaxed problem’s optimal value.The relaxed problem is introduced using positive multipliers, and its optimum upper-bounds the original problem.
  • B. Allocation and Pricing Schemes: Unlike Lagrangian relaxation, the optimal surrogate-relaxation multipliers for the formulated problem can be obtained directly rather than numerically.This follows the paper’s comparison between the two relaxation approaches.
  • B. Allocation and Pricing Schemes: For the multiple-knapsack formulation, an optimal multiplier vector sets every multiplier to the same positive constant.The paper states this result as Lemma 4.1.
  • B. Allocation and Pricing Schemes: With optimal multipliers, surrogate relaxation becomes a single larger-capacity knapsack that can be solved using the proposed dynamic-programming structure.The relaxation can also support a polynomial-time O(n^2) heuristic approximation algorithm.
  • B. Allocation and Pricing Schemes: For exact branch-and-bound solutions, VCG pricing with a base access price preserves incentive compatibility, individual rationality, and allocation efficiency at each level.Corresponding pricing schemes are also applied when approximate solutions are used.

V. PERFORMANCE EVALUATION

The evaluation compares hierarchical auction algorithms with fixed and general sharing across social welfare, resource utilization, and user satisfaction. Results show tradeoffs between efficiency, flexibility, complexity, and the number of MVNOs.

  • Evaluation setup: The evaluation uses average social welfare, resource utilization, and user satisfaction as its main performance metrics.The simulations compare fixed sharing, general sharing, dynamic-programming, greedy, and multiple-seller approaches.
  • Social welfare: DPA1 outperforms DPA2, while general sharing achieves the largest social welfare benchmark.The group sizes are 1 for DPA1 and 5 for DPA2.
  • Social welfare: Hierarchical auction welfare remains below general sharing, reflecting a tradeoff between global social efficiency and intra-slice customization.The multiple-seller setting achieves higher welfare than the single-seller setting because dynamic user association adds flexibility.
  • Resource utilization: All proposed dynamic resource-sharing schemes outperform fixed sharing, indicating resource-utilization gains from wireless virtualization.The resource-utilization comparison uses average subchannel utilization as an example.
  • User satisfaction: Implicit resource requests achieve better user satisfaction than explicit requests because general valuation provides benefits over the single-minded model.User satisfaction is evaluated across the two request models.
  • Impact of MVNO count: Average resource utilization decreases as the number of MVNOs increases when total resources and users remain fixed.The paper attributes this to fewer resources and users per MVNO, which reduces statistical multiplexing gains.

APPENDIX B: HEURISTIC ALGORITHM FOR SOLVING THE MULTI-SELLER MULTI-BUYER PROBLEM

The appendix presents a low-complexity heuristic for the multi-seller multi-buyer problem. It initializes a feasible allocation, applies greedy assignment, and uses rearrangement to improve the solution.

  • Algorithm overview: The heuristic has complexity O(n^2) and extends a single-dimensional-item algorithm to multiple dimensions.The extension handles multiple resource dimensions in the multi-seller multi-buyer problem.
  • Initialization: Initialization re-indexes users and MVNOs and constructs an initial feasible solution with the greedy algorithm.The initialization also sets weighted user and MVNO resource quantities for ordering.
  • Greedy allocation: The greedy procedure assigns users to MVNOs while tracking remaining subchannel and power capacities.Assignment indices distinguish unassigned users from users assigned to a particular MVNO.
  • Rearrangement: The rearrangement stage iterates through assignments, moves users when capacity constraints permit, updates residual resources, and invokes the greedy algorithm again.The procedure processes users in reverse order and maintains an assignment index for each user.

Algorithm 8 First improvement

The first-improvement procedure examines assigned users and seeks beneficial exchanges or reallocations while maintaining subchannel and power feasibility.

  • First improvement: For an assigned user, the procedure restores the MVNO capacity consumed by that user before testing alternative assignments.It initializes a candidate set for users that may be considered in the improvement.
  • Candidate construction: The procedure builds a candidate set by subtracting users’ resource demands from available subchannel and power capacities.The candidate set is expanded iteratively during the search.
  • Improvement update: When an improvement is found, users are reassigned, residual capacities are updated, and the objective value is increased by the exchange gain.The update records the new assignment and adds the net bid difference to the objective.
Loading 1511.08256v1…