Source-linked AI summary
Efficiency Resource Allocation for Device-to-Device Underlay Communication Systems: A Reverse Iterative Combinatorial Auction Based Approach
Chen Xu, Lingyang Song, Zhu Han, Qun Zhao, Xiaoli Wang, Xiang Cheng, Bingli Jiao
TL;DR
D2D underlay spectrum sharing must improve system performance while managing interference and allocation complexity. The paper proposes a reverse iterative combinatorial auction for cellular-resource allocation, and reports good system-sum-rate performance with finite convergence, cheat-proofness, and lower complexity than exhaustive search.
Problem
Allocating cellular resources to D2D transmissions is highly complex, while spectrum sharing introduces interference between D2D and cellular communication.
Method
The paper uses a reverse iterative combinatorial auction to allocate cellular resources between cellular users and D2D pairs.
Results
The auction algorithm provides good system-sum-rate performance and high system efficiency with lower complexity than exhaustive-search allocation.
Takeaways & Limitations
The proposed mechanism offers a resource-allocation approach for improving system sum rate in D2D underlay networks.
Abstract
from arXiv · showhide
Peer-to-peer communication has been recently considered as a popular issue for local area services. An innovative resource allocation scheme is proposed to improve the performance of mobile peer-to-peer, i.e., device-to-device (D2D), communications as an underlay in the downlink (DL) cellular networks. To optimize the system sum rate over the resource sharing of both D2D and cellular modes, we introduce a reverse iterative combinatorial auction as the allocation mechanism. In the auction, all the spectrum resources are considered as a set of resource units, which as bidders compete to obtain business while the packages of the D2D pairs are auctioned off as goods in each auction round. We first formulate the valuation of each resource unit, as a basis of the proposed auction. And then a detailed non-monotonic descending price auction algorithm is explained depending on the utility function that accounts for the channel gain from D2D and the costs for the system. Further, we prove that the proposed auction-based scheme is cheat-proof, and converges in a finite number of iteration rounds. We explain non-monotonicity in the price update process and show lower complexity compared to a traditional combinatorial allocation. The simulation results demonstrate that the algorithm efficiently leads to a good performance on the system sum rate.
I. INTRODUCTION
D2D underlay communication can improve spectral efficiency and system capacity by reusing cellular resources, but spectrum sharing creates interference and allocation complexity. The paper addresses this with a reverse iterative combinatorial auction for allocating cellular resources among D2D pairs and cellular users.
- Spectrum reuse can improve spectral efficiency and system performance, but it also causes interference to cellular communication.
- D2D users communicate directly over cellular resources while remaining controlled by the base station.
- Efficient interference coordination is required to preserve a target cellular performance level during D2D spectrum sharing.
- The paper maximizes system sum rate by allowing multiple D2D pairs to share one cellular user’s spectrum resource.
- The proposed reverse iterative combinatorial auction treats resources as bidders and D2D links as goods auctioned in each round.
- The auction is analyzed as cheat-proof, convergent in finite iterations, and lower-complexity than exhaustive-search allocation.
II. SYSTEM MODEL
The system model describes D2D communication underlaying a cellular network and defines the resulting system sum rate.
- The model considers multiple D2D and cellular users in a cellular-network underlay scenario.
- The section gives the expression used for the system sum rate.
- The system model provides the basis for the primary optimization problem formulated later.
A. Scenario Description
The scenario models a single-cell downlink with cellular users and multiple D2D pairs sharing licensed resources. Resource sharing creates intra-cell interference, while the base station controls D2D setup, power, and allocation using channel information.
- Scenario: A single-cell scenario contains a cellular user and multiple D2D pairs whose locations are randomly distributed subject to D2D distance constraints.
- D2D session setup: D2D session setup includes detecting same-subnet traffic, checking throughput gains, and establishing a D2D bearer when both UEs are capable.
- Resource control: The base station maintains radio-resource control for cellular and D2D communication, using feedback and control signaling for power and spectrum allocation.
- Downlink sharing: During downlink transmission, cellular resource blocks may be shared with multiple D2D pairs, producing interference in both directions.
- Channel model: The channel model uses Rayleigh fading and a free-space path-loss model, with received power determined by transmit power, channel coefficient, and distance.
B. System Sum Rate
The system sum rate is computed from SINR-based cellular and D2D channel rates under interference from shared transmissions. The allocation variables are then optimized to maximize the downlink system sum rate.
- SINR is used as an indicator for evaluating cellular and D2D link performance.
- Channel rates are calculated from SINR using the Shannon capacity formula.
- The optimization designs β_cd for each D2D pair to maximize the downlink system sum rate ℜ.
III. PROBLEM FORMULATION
This section formulates D2D resource sharing as a reverse iterative combinatorial auction, defining valuations from channel-rate gains and interference-aware resource assignments.
- III. PROBLEM FORMULATION: The section introduces valuation and utility concepts as the basis of the reverse iterative combinatorial auction.
- A. Valuation Model: D2D and cellular communications share spectrum, so resource assignments must account for channel fading, transmit power, spatial distance, and interference.
- A. Valuation Model: The channel-rate value function evaluates allocations by relating shared-channel rates to the assigned cellular resources and D2D packages.
- A. Valuation Model: A D2D package Dk contains D2D pairs sharing resources with cellular user c, whose corresponding channel rates are formulated for the shared channel.
- A. Valuation Model: Cellular resource c acts as a bidder seeking D2D packages to maximize channel rate, with gains determined by D2D signal contributions relative to interference.
- A. Valuation Model: The private valuation vc(k) is the positive performance gain for bidder c receiving package Dk, relative to its channel rate without co-channel interference.
- A. Valuation Model: The valuation model V contains private valuations for every bidder c and package Dk among the possible D2D package assignments.
B. Utility Function
This section defines bidder payments, utilities, allocations, and efficiency for evaluating the reverse auction formulation of D2D spectrum sharing.
- B. Utility Function: A bidder’s gain from receiving package Dk is represented through its utility, while control-signal transmission and information feedback are modeled as costs.
- B. Utility Function: The pay price Pc(k) is the amount bidder c pays for package Dk, while pc(d) denotes the unit price of item d.
- B. Utility Function: Linear anonymous pricing makes a package price equal to the sum of its item prices and assigns equal prices for the same package across bidders.
- B. Utility Function: The bidder utility Uc(k) expresses satisfaction from obtaining package Dk and is derived from valuation and payment terms.
- B. Utility Function: An allocation X assigns packages to bidders using binary variables xc(k), with XOR bidding allowing multiple bids but at most one winning bid.
- B. Utility Function: The auction’s total utility and auctioneer revenue are computed from allocated bidder utilities and pay prices, respectively.
- B. Utility Function: The reverse I-CA game allocates D2D packages to spectrum resources to improve channel rates through iterative bid and price updates.
- B. Utility Function: Overall gain equals the sum of allocated package valuations, and efficient allocation maximizes this gain through the combinatorial allocation problem.
B. Algorithm for Resource Allocation
The algorithm uses linear descending prices with discrete upward fine-tuning when demand exceeds supply, iterating until D2D packages or channels are fully allocated.
- B. Algorithm for Resource Allocation: The proposed mechanism is a reverse iterative combinatorial auction using ask-price-based allocation and linear prices.
- B. Algorithm for Resource Allocation: Discrete price reductions can create simultaneous bids for overlapping packages, which are detected through demand conditions.
- B. Algorithm for Resource Allocation: Linear prices are chosen because they are easy for bidders to understand and convenient to communicate each round.
- B. Algorithm for Resource Allocation: Because D2D links interfere with cellular operation, cellular channels must preserve cellular-system performance before permitting D2D access.
- B. Algorithm for Resource Allocation: The base station initializes locations, round index t = 0, item ask prices p0(d), and a fixed reduction ∆ > 0 before announcing prices.
- B. Algorithm for Resource Allocation: Spectrum-resource bidders submit desired packages and pay prices at current prices; jump bidding above current prices is prohibited.
- B. Algorithm for Resource Allocation: When supply exceeds demand, the base station increments t and decreases the price of the oversupplied item by ∆.
- B. Algorithm for Resource Allocation: Once a package price falls below a bidder’s valuation, the package is allocated and its item prices are fixed; XOR bidding then excludes that bidder from later rounds.
V. ANALYSIS OF THE PROPOSED RESOURCE ALLOCATION ALGORITHM
This section introduces the analysis of the proposed auction-based resource allocation mechanism.
- V. ANALYSIS OF THE PROPOSED RESOURCE ALLOCATION ALGORITHM: The paper investigates important properties of the proposed auction-based resource allocation mechanism.
A. Cheat-Proof
The reverse iterative combinatorial auction is cheat-proof because truthful demand maximizes each bidder’s utility, and it converges after finitely many iterations.
- Proposition 1 states that the reverse I-CA resource allocation algorithm is cheat-proof.
- Bidder utility depends on package valuation, unit prices, and interference between cellular and D2D communications.
- Utility decreases with the relevant channel gains, so the optimal strategy bids the D2D link with lower gain to the cellular transmitter and receiver.
- Truthful demand is optimal because quitting when utility is nonnegative loses a useful package, while bidding with negative valuation produces negative surplus.
- Proposition 2 states that the reverse I-CA converges in a finite number of iterations.With finitely many packages, price updates eventually produce a converged allocation; larger Δ speeds convergence, while smaller Δ slows it.
C. Price Monotonicity
The reverse I-CA uses non-monotonic descending prices: prices generally fall but may rise to resolve competition, while retaining finite convergence and lower stated complexity than exhaustive allocation.
- The proposed descending-price auction may raise item prices within a round to reflect competition and improve efficiency.
- Fine-tuning with δ makes bidders reinspect utility, and bidders quit once their utility becomes negative.
- Finite iterations leave one winner, and the ascending-price process maximizes auctioneer revenue, yielding higher efficiency than random allocation in that situation.
- The proposed scheme is reported to have lower complexity for sufficiently large m and n, with O(n · m + p0(d)/Δ) under one D2D pair per channel.
E. Overhead
The reverse I-CA operates centrally at the base station and requires global CSI, without additional signaling overhead beyond existing scheduling schemes, though CSI acquisition remains complicated.
- The base station remains the control center, receiving feedback and conducting the iteration process centrally.
- The scheme requires global CSI at the base station and does not need additional signaling overhead beyond existing resource scheduling schemes.
- The reverse I-CA requires more complicated CSI because of interference between D2D and cellular communications.
- CSI is obtained through detection signals sent in initial packets and then acquired at D2D or cellular receivers.
- The simulations use a single-cell WINNER II setting with indoor D2D and urban-microcellular channel models.
- System sum rate increases with both the number of D2D pairs and the number of resource units, partly because more resources increase the chance of lower-interference assignments.
B. System Efficiency
The auction achieves high, generally stable efficiency relative to exhaustive search, while remaining approximate because it follows a local or approximate global optimum.
- System efficiency is defined as η = ℜ/ℜopt, where ℜopt represents the exhaustive optimal sum rate.
- The reported lowest efficiency is around 0.7, occurring when both the number of resource units and D2D pairs are small.
- Efficiency is stable above 0.9 in the reported comparisons, indicating a small gap between the proposed algorithm and exhaustive search.
- The gap from exhaustive optimality cannot be avoided because the algorithm follows a local or approximate global optimum.
- The proposed reverse I-CA allocates spectrum using D2D-pair valuations, a utility-based non-monotonic descending-price process, and finite-round convergence.
- The auction algorithm is much superior to random allocation, and its system efficiency remains stable across user and resource parameters.