Sage Journals: Discover world-class research

Abstract

Cognitive small cell networks consisting of macro- and small cells are foreseen as a candidate solution to meet ever increasing requirements of broadband services and new applications. However, the traditional fixed spectrum allocation policy makes available spectrum resources for small cells insufficient. Therefore, an efficient spectrum allocation method is urgently needed that allows a large number of small cells to share spectrum resources with macro-cells. In this article, a real-time spectrum auction model is presented which aims at assigning the scarce spectrum resources to small cells quickly. The co-win situation is constructed, and the trade-off between spectrum utilization and revenues is controlled. Such a problem is formulated as an NP-hard optimization problem for which a low-complexity multi-greedy algorithm is proposed to obtain prices and spectrum allocations. The proposed algorithm can achieve conflict-free spectrum allocations that maximize the utility and spectrum allocation efficiency. Compared with the Vickrey–Clarke–Groves algorithm, simulation results show the higher utility and spectrum allocation efficiency of the proposed algorithm.

Keywords

Small cells spectrum auction multi-greedy algorithm spectrum allocation

Introduction

In recent years, the proliferation of high-specification handsets, in particular smart phones, has led the amount of data traffic in cellular networks to dramatically increase.¹ Although many efforts by researchers have been made to enhance wireless channel capacity, they are far from solving the spectrum scarcity problem. Such explosive demands for mobile data have imposed the need to respond to the challenging requirements of modern cellular networks such that more mobile users and new applications can be accommodated with satisfied performances. Conventional cellular networks based on the careful deployment of mobile base stations are efficient in providing large area coverage and better at handling user mobility in cellular networks. However, macro-cells usually suffer from poor signal quality for indoor and cell-edge users and they are not efficient in providing high data rates for multimedia applications. Furthermore, the explosive surge in mobile data traffic accelerates the need for novel cellular architectures to meet such demands.² Reducing cell size is one of the most effective approaches to enhance the network capacity and support pervasive broadband services.³ Therefore, the deployment of heterogeneous networks based on small cells is an important technique for increasing the energy efficiency of mobile cellular networks.^4–6

Deployment of small-cell base stations has a great capability to improve the spatial reuse of spectrum resources and also enhance transmit power efficiency.^7,8 Small cells can be deployed both with macro-cell coverage and stand alone, both indoor and outdoor, sparsely or densely, and support both ideal and non-ideal backhauls. Small cells can be deployed by either operators or independent mobile users such as an organization in an office building. Automatic mechanisms such as plug-and-play provisioning to support flexible configuration and lower cost for operation and maintenance can be used.¹ It is foreseen that the next-generation mobile networks will consist of heterogeneous macro- and small cells with different capabilities including transmit power and coverage range.⁹ Therefore, as a potential technology to meet these requirements, a great majority of researchers showed interest in small cell networks. Nevertheless, most of the current literature studies the energy efficiency in small cell networks. In Wildemeersch et al.,¹⁰ the author evaluated a distributed sleep-mode strategy for cognitive small cell access points and analyzed the trade-off between traffic offloading from the macro-cells and the energy consumption of the small cells. Wu et al.¹¹ proposed an energy-efficient small cells’ on/off approach that allows small cells to activate or deactivate based on estimated traffic load and user equipment preference requirements that aim to maximize the network energy efficiency by deactivating such under-utilized cells, subjecting to the rate fairness constraints among users. Other articles such as Hasan et al.¹² presented a solution to an energy-efficient resource allocation problem for maximizing the cognitive radio (CR) link capacity in small cells, while Gan et al.¹³ proposed a single Q-learning-based probabilistic policy to obtain the optimal on/off switch policy in small cells. However, this approach needs a long time for exploration, so as to get the optimal pattern. In this article, different from most research on the energy efficiency, we mainly focus on the optimal allocation of spectrum resources and improve spectral efficiency in the small cell networks.

The study supported by the Federal Communications Commission has shown that traditional fixed spectrum allocation policy is inadequate in addressing today’s rapidly growing wireless communications.¹⁴ The fixed spectrum allocation policy in the traditional mode makes the spectrum resources be vacant most of the time, which results in a large number of spectrum resources being wasted. It means very limited spectrum resources can be allocated to small cells (especially the characteristics that limiting small cells optimize network coverage and reduce spectrum utilization).

Reliable and efficient spectrum access is vital for the growth and innovation of wireless technologies. Therefore, to realize efficient spectrum usage, we must migrate from the current static spectrum access to dynamic spectrum access. Dynamic spectrum access/sharing is based on the technology of CRs.¹⁵ In this article, we assume that each small cell is equipped with the technology of dynamic spectrum access which can detect the vacant spectrum in the surrounding environment anytime and opportunistically access vacant licensed spectrum without imposing significant impact on services of spectrum holders. The spectrum allocation method based on auction is considered to be an effective method to solve the problem of spectrum resource allocation with its less requirement of information and good distribution effect. It can make full use of the vacant spectrum and achieve effective sharing and dynamic management of spectrum, which fundamentally solve the problem of low spectral efficiency. Spectrum auction that applies pricing-based incentives to stimulate users to sell and lease under-utilized spectrum.¹⁶ Auction theory as a branch of economics has been introduced to spectrum sharing between supplier and purchasers, which can date back to more than a decade ago.¹⁷ Over the past few years, a number of auction mechanisms have been proposed for spectrum management techniques to improve the spectrum utilization while benefiting both the primary user (PU) and the secondary user (SU) in a spectrum market. Pan et al.¹⁸ proposed a session-based spectrum auction system called spectrum cloud in multi-hop CR networks. Combinatorial auction has been considered in Zhu et al.,¹⁹ which means buyers can bid for combinations of spectrum bands. Li et al.²⁰ proposed a novel multi-round service-oriented combinatorial spectrum auction with two-tier framework support. Huang et al.²¹ developed an auction-based spectrum sharing framework to allow a single spectrum manager to share its spectrum with a group of users, subject to the interference temperature constraint at the measurement point. Wu et al.²² proposed an efficient mechanism for multi-winner spectrum auction, which is a novel concept and can efficiently improve spectrum utilization with collusion-resistant pricing strategies between the service provider and SUs. Chen et al.²³ formulated a non-cooperative multiple-PU multiple-SU auction game and studied the structure of the resulting equilibrium by solving a non-continuous two-dimensional optimization problem. Teng et al.²⁴ presented a novel Q-learning-based auction algorithm for dynamic spectrum access in a single-PU multiple-SU scenario. A novel scheduling algorithm is proposed in Pal et al.²⁵ based on a two-phase combinatorial reverse auction with the objective of maximizing the number of satisfied users. Niyato and Hossain²⁶ considered the problem of spectrum sharing among a PU and multiple SUs, formulating this problem as an oligopoly market competition and using a non-cooperative game to execute the spectrum allocation for SUs. Zhang et al.²⁷ introduced novel routing metrics that estimate both the future spectrum availability and the average transmission time. Then, they proposed two routing algorithms for multi-hop CR networks that attempt to reduce the probability of spectrum hand-off and rerouting upon PU’s arrival. They estimated the spectrum availability and spectrum quality in Zhang et al.²⁸ from the view of both the global statistical spectrum usage and the local instant spectrum status and then introduced novel routing metrics to consider the estimation. Zheng et al.²⁹ presented a new network model aiming at improving users’ experience that pushes the scheduling problem to the task layer. They first introduced a quality-of-experience (QoE) requirement that can generalize the quality-of-service (QoS) requirement in link scheduling. Subsequently, a novel scheduling policy was proposed which can capture this requirement for each task and then perform an application-aware scheduling. Following this design, a corresponding scheduling policy in Zheng et al.³⁰ was proposed to capture it for each task and then reach an application-aware transmission allocation. They theoretically analyzed the performance of the scheduling policy and discussed the design of an optimal solution and the impact of the QoE requirements.

We consider the characteristics of small cells, such as automatic mechanisms of plug-and-play provisioning to support flexible configuration and lower cost for operation and maintenance. Therefore, we need an efficient and stable spectrum allocation method that allows small cells get spectrum resources quickly. In this article, we propose a real-time spectrum auction model that macro-cells as the seller are licensed users. They may not take up the owned spectrum all the time, so they have many licensed vacant spectrum resources. Small cells as the buyer are unlicensed users, equipped with the technology of CRs which can detect the vacant spectrum in the surrounding environment anytime and opportunistically access vacant licensed spectrum without imposing significant impacts on services of macro-cells. In this real-time spectrum auction framework, we aim at designing a multi-greedy algorithm that controls trade-offs between the spectrum utilization and revenues for future small cell networks.

Compared with previous works, the main contributions of this article are summarized as follows:

We propose a real-time spectrum auction model that assigns the scarce spectrum resources to small cells, solving the problem of dramatically increasing demand for spectrum and under-utilization of spectrum.

While the revenue-maximizing auction problem is NP-hard, we propose a low-complexity multi-greedy algorithm to derive prices and spectrum allocations.

Our approach achieves conflict-free spectrum allocation that maximizes auction revenue and spectrum utilization.

By comparing with the Vickrey–Clarke–Groves (VCG) algorithm, the simulation results verify the efficiency and feasibility of the proposed multi-greedy algorithm.

The rest of this article is organized as follows. Section “System model” introduces the system model considered in this article. The basic auction design which describes the multi-greedy algorithm to obtain the optimal solution to the spectrum auction problem is presented in section “Spectrum allocation algorithms.” Simulation results are presented in section “Simulation results,” followed by conclusions in section “Conclusion.”

System model

In this section, we present the network model and auction model of our work; through the presentation of the proposed spectrum auction framework and the formulation of the auction algorithm under the framework, we consider how to efficiently auction spectrum resources to satisfy user’s demands while maximizing allocation revenue. First, we assume that each small cell bids spectrum with specific but fixed power requirements, and hence focuses solely on channel allocation. So the signal fading and noise in the channels are ignored in our spectrum auction model. Then the macro-cell base station divides its spectrum into a large number of homogeneous channels with equal power and channel bandwidth. When using the channel access, we assume that the small cells adopt constant transmission power and experience no interference.

Cognitive small cell network

Conventional cellular systems use a macro-cell base station homogeneous network architecture, where a network of macro-cell base stations provides coverage to user equipment in each cell. However, such a deployment especially degrades the coverage of the cell-edge users and the overall spectrum utilization. Heterogeneous networks using a mixture of macro- and small cells are foreseen as one of the solutions to meet the ever increasing mobile traffic demand. In this article, we consider a network model of two-tier cellular heterogeneous network, which comprises conventional macro-cell base stations in the first tier which is overlaid with low-power, low-complexity small cell in the second tier, distributed according to a homogeneous Poisson point process. The macro-cell tier guarantees the coverage, while the second tier is a means to offload the data traffic from the macro-cells and to satisfy the local capacity demand. In our network model, small cells can extend the network coverage, and the reduced cell size leads to higher spatial frequency reuse and increased spectrum utilization.

Figure 1 shows a heterogeneous network model where a macro-cell base station is overlaid with several small cells. In this article, we ignore the users of macro-cell tier and mainly discuss the second tier. In hot-spot indoor/outdoor locations, a single or a few small cells are sparsely deployed, for example, to cover the traffic hot-spot. In dense urban or large shopping malls, a large number of small cells are densely deployed to support a huge amount of traffic over a relatively wide area. At the same time, small cells can be deployed by either operators or independent users such as an organization in an office building. Automatic mechanisms such as plug-and-play provisioning to support flexible configuration and lower cost for operation and maintenance could be considered. The mobile users are scattered over second tier distributed according to a homogeneous Poisson point process. In this network, each mobile user device usually communicates on a specific sub-channel corresponding to the base station from which it receives the strongest signal strength. Next, we investigate how to use the spectrum auctions to offload the traffic from the macro-cells by small cells and exploit their capabilities to enhance the spectral efficiency.

Figure 1.

A cognitive small cell network.

Auction model

From LTE Release 10, using small cells has been an important evolution direction in 3GPP to provide the necessary means to accommodate the anticipated huge traffic growth, especially for hot-spot areas.¹ In this article, we consider that macro-cells are the licensed users. They may not take up the owned spectrum all the time, so they have many licensed vacant spectrum resources. Small cells are the unlicensed users needed to obtain vacant licensed spectrum resources’ service to mobile users. The licensed vacant spectrum resources in the macro-cell base stations are divided into multiple vacant spectra that are non-overlapping and indivisible and the nature of these (bandwidth, modulation, etc.) is exactly the same. Each vacant spectrum can be shared among several users by time division multiplexing. In the real-time spectrum auction model we are designing, the supplier (macro-cell base stations) brings the free spectrum for public sale, while the purchaser (small cells) bids at a certain payoff. There is a third-party device called the central spectrum auction processor as the auctioneer which collects spectrum price, geographical location, network node, and other information to the spectrum auction. Therefore, small cells compete the access opportunities while macro-cell base stations snatch the revenue by leasing the vacant spectrum to the lessees, the central spectrum auction processor determines the winner of auctions according to the principle of maximizing the benefits to reach a state of win-win business. It effectively allocates these vacant licensed spectrum resources to small cells, which solves the problem of extremely limiting spectrum resources of small cells and takes advantages of small cells’ optimization network coverage, thus improves the spectrum utilization.

Macro-cell base stations divide its spectrum into a large number of homogeneous bands with equal power and channel bandwidth. So we use $n = {1, 2, \dots, N}$ and $m = {1, 2, \dots, M}$ to denote the vacant spectrum set and the small cells’ set, respectively. To provide conflict-free spectrum usage, spectrum auction is constrained by radio interference. Small cells in close proximity interfere with each other and cannot use the same spectrum, while well-separated buyers can reuse the same spectrum. So we set up an $M \times M$ matrix to determine whether there is an interference between small cells or not

B = {b_{ij}}_{M \times M}, b_{ij} \in {0, 1}, i \in m, j \in m

(1)

The expression B is the interfering matrix, and $b_{ij}$ indicates whether the ith small cell and the jth small cell are interfering. When $b_{ij} = 1$ , the ith small cell and the jth small cell are interference between each other, and they cannot use the same spectrum. Through the technology of dynamic spectrum access, the small cell makes an estimated price matrix Q for the vacant spectrum

Q = {q_{i}^{k}}_{M \times N}, k \in n, i \in m

(2)

Here, $q_{i}^{k}$ is the estimated price of the kth vacant spectrum for the ith small cell.

Then, the small cell makes a quoted price matrix V to the central spectrum auction processor

V = {v_{i}^{k}}_{M \times N}, v_{i}^{k} \leq q_{i}^{k}, k \in n, i \in m

(3)

The macro-cell base stations show the cost price of a single vacant spectrum to central spectrum auction processor, denoted by P_C, and $v_{i}^{k} \geq P_{C}$ .

We assume centralized auctions after collecting all asks/bids’ information from macro-cell base stations and small cells. The central spectrum auction processor determines resource allocation, payment to the macro-cell base stations, and charges to winning small cells. The auction is sealed-bid, private, and collusion-free. All participants submit sealed asks/bids over some control channels or frames reserved for the auction, such that no one knows others’ asks/bids, and they do not collude with each other to improve the utility of the auction system. Moreover, all asks and bids from participants are static and will not change during the auction. In this case, we should search for the revenue-maximizing allocation matrix D

D = {d_{i}^{k}}_{M \times N}, k \in n, i \in m

(4)

The expression D indicates whether the kth vacant spectrum of the ith small cell is successful or not.

According to the allocation matrix and the valuation matrix, we can get the utility of the auction system

U_{v} (D) = \sum_{i = 1}^{m} \sum_{k = 1}^{n} d_{i}^{k} v_{i}^{k}, i \in m, k \in n

(5)

The expression $U_{v} (D)$ is the system utility value, $d_{i}^{k}$ is the allocation of the kth vacant spectrum for the ith small cell, and $v_{i}^{k}$ is the valuation of the kth vacant spectrum for the ith small cell. The utility of the auction system is defined as the total revenue obtained from the entire auction model in an auction cycle. Our spectrum auction is formulated as the following optimization problem

max_{D} \sum_{i = 1}^{m} \sum_{k = 1}^{n} d_{i}^{k} v_{i}^{k}

s.t.

d_{i}^{k} \in {0, 1}, i \in m, k \in n

(6)

v_{i}^{k} \geq p_{C}

(7)

d_{i}^{k} + d_{j}^{k} \leq 1, i \in m, j \in m, if b_{ij} = 1

(8)

\sum_{i = 1}^{m} d_{i}^{k} \leq 1

(9)

Constraint (6) indicates vacant spectrum allocation to ensure the rationality of the auction; constraint (7) ensures incentive compatibility, that is, “truthfulness”; constraint (8) indicates that each small cell is allocated at most one spectrum band and that two conflicting small cells cannot get the same spectrum band; constraint (9) indicates that each small cell can only access one spectrum band at a time.

Spectrum allocation algorithms

We need to make $Q = V$ , but the spectrum auction of small cells is selfish and rational, that is, each small cell tries to maximize its own interest. They will choose to lie to estimate the price if they can get higher benefits. A well-known auction is the VCG, which has a dominant strategy to encourage compatibility characteristics. The maximum incentive buyer submits their true valuation and effectively ensures the fairness of the entire auction system. In the VCG mechanism, if the allocation matrix is D, then the system utility value is $U_{v} (D)$ . We assume that the ith small cell gets the spectrum successfully, then $v_{i *} = [v_{1}, v_{2}, \dots, v_{i - 1}, v_{i + 1}, \dots, v_{N}]$ . The actual price of the ith small cell is

p_{i} = v_{i} + U_{i *} (D) - U_{i} (D)

(10)

In view of the auction framework proposed in this article, the use of VCG leads to a relatively low system utility, resulting in a serious resistant mechanism.³¹ We compared the multi-greedy algorithm with the VCG mechanism, which embodies the superiority of the multi-greedy algorithm. The small cells of vacant spectrum y obtained above are considered as Y set in multi-greedy, $V_{Y} = \sum_{i \in Y} v_{i}$ . The actual price of the Y small cells is

p_{Y} = v_{Y} + U_{V - V_{Y}} (D) - U_{V} (D)

(11)

According to the proportional fairness, the actual price of the ith small cell is

p_{i} = v_{i} - \frac{v_{i} (v_{Y} - p_{Y})}{v_{Y}}

(12)

Primitive greedy algorithm

To support the proposed spectrum allocation framework, we need an efficient allocation algorithm to allocate spectrum resources in real time. However, the existing solutions for spectrum auctions such as the enumeration method require complex calculating time that grows exponentially with the number of frequency bands and apply complex allocation and pricing process. In this article, we consider that small cells can be deployed by either operators or independent users such as automatic mechanisms of plug-and-play provisioning to support flexible configuration and lower cost for operation and maintenance. So high-complexity algorithms such as enumeration method are not suitable for this auction framework. In conclusion, we design a greedy allocation algorithm to decrease the computational overhead. In the greedy algorithm, the central spectrum auction processor collects all ask/bid information from macro-cell base stations and small cells, and then according to the principle of maximizing the benefits chooses proper spectrum from the highest price to the lowest price to determine the winner. The advantages of greed algorithm are fast speed and low computational complexity.

Our algorithms are supported by strong theoretical bounds on performance and complexity and possess the following economic properties: individual rationality, incentive compatibility, and self-collusion resistance.

Algorithm 1. Primitive greedy algorithm.
Information collection: The central spectrum auction processor collects the information of n vacant spectrum bands’ set (geographical location, bandwidth, etc.) provided by the macro-cell base stations.Price announcing: The central spectrum auction processor announces the information of vacant spectrum bands’ set to m small cells’ set and single vacant spectrum band’s cost price $P_{C}$ .Bidding: Based on $P_{C}$ , each small cell submits a bid $v_{i}^{k}$ , where $i \in m, k \in n$ and $v_{i}^{k} \geq P_{C}$ .Interference matrix: After collecting information from macro-cell base stations and small cells, the central spectrum auction processor sets interference matrix B. Each small cell has its own available band set $F_{i}$ and the interference user set $A_{i}$ , if $v_{i}^{k} \leq P_{C}, A_{i} \in \emptyset$ , $i \in m, F_{i} \in n, A_{i} \in m$ .Spectrum allocation: The central spectrum auction processor selects a winner $t (t \in m)$ from m according to the formula $t = max \frac{v_{t}}{\sum_{i \in m} V_{i}}$ Assign the highest priority bands $F_{t 1}$ in $F_{t}$ to t. If $F_{t} = \emptyset$ , discard the small cell t. Update small cells’ set: $m = m - t$ .if $m = \emptyset$ ,we can get allocation matrix D.

Algorithm 1. Primitive greedy algorithm.

Information collection: The central spectrum auction processor collects the information of n vacant spectrum bands’ set (geographical location, bandwidth, etc.) provided by the macro-cell base stations.Price announcing: The central spectrum auction processor announces the information of vacant spectrum bands’ set to m small cells’ set and single vacant spectrum band’s cost price

P_{C}

.Bidding: Based on

P_{C}

, each small cell submits a bid

v_{i}^{k}

, where

i \in m, k \in n

and

v_{i}^{k} \geq P_{C}

.Interference matrix: After collecting information from macro-cell base stations and small cells, the central spectrum auction processor sets interference matrix B. Each small cell has its own available band set

F_{i}

and the interference user set

A_{i}

, if

v_{i}^{k} \leq P_{C}, A_{i} \in \emptyset

i \in m, F_{i} \in n, A_{i} \in m

.Spectrum allocation: The central spectrum auction processor selects a winner

t (t \in m)

from m according to the formula

t = max \frac{v_{t}}{\sum_{i \in m} V_{i}}

Assign the highest priority bands

F_{t 1}

F_{t}

to t. If

F_{t} = \emptyset

, discard the small cell t. Update small cells’ set:

m = m - t

.if

m = \emptyset

,we can get allocation matrix D.

Multi-greedy algorithm

The greedy algorithm is an approximate algorithm for solving the NP-hard problem. The advantages of greedy algorithm are fast speed and low computational complexity, but the superiority of the result is not ideal. In this article, we take the greedy criterion and interference constraints into account and then add the multi-greedy strategy to the primitive greedy algorithm. Multi-greedy algorithm increases the solutions of the search space, which makes up for the shortage of primitive greedy algorithm and improves the superiority of the results. The time complexity of multiple greedy algorithm is only slightly higher than primitive greedy algorithm, but it is obviously lower than the enumeration method. When m and n sets are extremely large, the multi-greedy algorithm can save a lot of auction times, and this sub-optimal solution can never be too far off from the optimal one.

Algorithm 2. Multi-greedy algorithm.
Rebuilding buyers: The central spectrum auction processor extracts 40% of the small cells from the allocation matrix D which removes the vacant spectrum they have obtained, plus the discarded small cells in the primitive greedy algorithm, reconstructing the new small cell set. Spectrum allocation: The allocation matrix E is obtained using the greedy algorithm to allocate spectrum to the new small cells’ set.Compare the utility of the allocation matrices D and E. If $U_{v} (D) \geq U_{v} (E)$ , throws away E, Else, E takes the place of D.The remaining procedure is repeated the spectrum allocation for Y times to find the final allocation matrix H.

Algorithm 2. Multi-greedy algorithm.

Rebuilding buyers: The central spectrum auction processor extracts 40% of the small cells from the allocation matrix D which removes the vacant spectrum they have obtained, plus the discarded small cells in the primitive greedy algorithm, reconstructing the new small cell set. Spectrum allocation: The allocation matrix E is obtained using the greedy algorithm to allocate spectrum to the new small cells’ set.Compare the utility of the allocation matrices D and E. If

U_{v} (D) \geq U_{v} (E)

, throws away E, Else, E takes the place of D.The remaining procedure is repeated the spectrum allocation for Y times to find the final allocation matrix H.

Simulation results

In this section, we conduct simulations to evaluate the performance of the proposed auction framework and demonstrate some intrinsic properties of the proposed auction framework, especially the fairness and efficiency, which are not explicitly addressed in the analysis part of the article.

In our simulations, we consider a network model of $100 \times 100$ rectangular area. There are 50 small cells randomly distributed in the auction models. The central spectrum auction processor has 10 vacant spectra from the macro-cell base stations waiting for the auction. The cost of each vacant spectrum price is 5. The coverage radius of each small cell is 25 m, and if the distance between the two small cells is less than 50 m, they are considered to interfere with each other. The quote prices for vacant spectrum by small cells are evenly randomly distributed between [3, 10]. The number of small cells gradually increases from 50 to 100, and 100 rounds of run times in auction system are performed. In addition, we could define the vacant spectrum allocation efficiency as the number of winning small cells divided by the number of vacant spectrum that they have been sold. All the simulations are run in Matlab on a 3.0-GHz processor with 2 GB of computer (Table 1).

Table 1.

Simulation parameters.

Parameters	Value
System model area	$100 \times 100 m^{2}$
Number of small cells	Increasing from 50 to 100
Number of vacant spectrum	10
$P_{C}$	5 W
The quote prices for vacant spectrum by small cells	Randomly distributed between [3, 10]
Coverage radius of small cells	25 m
Interference radius between two small cells	50 m
Percentage of small cells resetting	40%
Times of greedy algorithm	3
Run times	100

Figure 2 compares the system utility of the three algorithms when the number of small cells is 50. Through 100 simulations, many small cells are discarded because they do not have available channel, so there will be few winners in primitive greedy algorithm and the system utility is lower than the other two algorithms.

Figure 2.

Comparison of the system utility versus run times.

The system utility of the optimized multi-greedy algorithm is higher than the VCG. It is steady and the system utility is generally 5%–10% higher than VCG mechanism. The simulation results show that the optimized multi-greedy algorithm is more suitable in this auction framework.

Figure 3 shows the system utility versus different numbers of small cells. We can see that as the number of small cells increases from 50 to 100, the system utility of the three algorithms is on the rise. However, the trend of the primitive greedy algorithm and VCG algorithm is relatively gentle than multi-greedy algorithm. We can conclude that as the number of small cells increases, the gap in the system utility of the three algorithms would increase gradually.

Figure 3.

Comparison of system utility versus number of small cells.

Figure 4 describes the spectrum allocation efficiency versus the number of small cells for the multi-greedy algorithm and VCG algorithm. We define the vacant spectrum allocation efficiency as the number of winning small cells divided by the number of vacant spectrum that have been sold. The multi-greedy algorithm is an algorithmic paradigm that follows the problem solving of making the locally optimal choice at each stage with the hope of finding a global optimum. In these cases, the multi-greedy algorithm does not in general produce an optimal solution, but nonetheless a greedy execution may yield locally optimal solutions that approximate a globally optimal solution in a reasonable time. Therefore, the multi-greedy algorithm has a high spectrum allocation efficiency and stability, at about 87%–90%. The VCG allocation is at about 75%–77%.

Figure 4.

Spectrum allocation efficiency versus number of small cells.

Figure 5 compares the spectrum allocation efficiency for different number of small cells and algorithms. We can see that as the number of small cells increases from 50 to 100, the multi-greedy algorithm achieves a more efficient spectral allocation than other algorithms, which is no less than 80%. Spectrum allocation efficiency for VCG is between 75% and 85%. Due to the limitations of the primitive greedy algorithm, the spectrum allocation efficiency of primitive greedy algorithm is relatively low, which is about 5%–10%.

Figure 5.

Comparison of spectrum allocation efficiency versus number of small cells.

Conclusion

In this article, we propose a spectrum auction which includes macro-cells as the supplier users and small cells as the purchaser users. There is a third-party device called the central spectrum auction processor as the auctioneer. Our goal is to assign the scarce spectrum resources to small cells and then construct the co-win situation and control trade-offs between the spectrum utilization and revenues. Our approach achieves conflict-free spectrum allocations that maximize auction revenue and spectrum utilization. The revenue-maximizing problem is NP-hard, thus we propose a low-complexity multi-greedy algorithm to derive prices and spectrum allocations. In the simulation, we compare it with the VCG algorithm to verify the efficiency and feasibility of our proposed multi-greedy algorithm.

Footnotes

Academic Editor: Zhipeng Cai

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the National Natural Science Foundation of China (61471135, 61671165); the Guangxi Natural Science Foundation (2013GXNSFGA019004, 2015GXNSFBB139007); the Fund of Key Laboratory of Cognitive Radio and Information Processing (Guilin University of Electronic Technology), Ministry of Education, China; the Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (CRKL150104, CRKL160105); and the Innovation Project of GUET Graduate Education (2016YJCX87).

References

Nakamura

Nagate

Benjebbour

. Trends in small cell enhancements in LTE advanced. IEEE Commun Mag 2013; 51(2): 98–105.

Andrews

Claussen

Dohler

. Femtocells: past, present, and future. IEEE J Sel Area Comm 2012; 30(3): 497–508.

Chandrasekhar

Andrews

Gatherer

. Femtocell networks: a survey. IEEE Commun Mag 2008; 46(9): 59–67.

Hasan

Boostanimehr

Bhargava

. Green cellular networks: a survey, some research issues and challenges. IEEE Commun Surv Tut 2011; 13(4): 524–540.

Hoadley

Maveddat

. Enabling small cell deployment with HetNet. IEEE Wirel Commun 2012; 19(2): 4–5.

Xie

. Energy-efficient resource allocation for heterogeneous cognitive radio networks with femtocells. IEEE T Wirel Commun 2012; 11(11): 3910–3920.

Cheung

Quek

TQS

Kountouris

. Throughput optimization, spectrum allocation, and access control in two-tier femto-cell networks. IEEE J Sel Area Comm 2012; 30(3): 561–574.

Tsai

Wang

Huang

. High-capacity OFDMA femtocells by directional antennas and location awareness. IEEE Syst J 2012; 6(2): 329–340.

Chen

Baccelli

Roullet

. Joint optimization of radio resources in small and macro cell networks. In: IEEE 73rd vehicular technology conference (VTC Spring), Yokohama, Japan, 15–18 May 2011, pp.1–5. New York: IEEE.

10.

Wildemeersch

Quek

TQS

Slump

. Cognitive small cell networks: energy efficiency and trade-offs. IEEE T Commun 2013; 61(9): 4016–4029.

11.

Liu

Zhao

. Dynamic small cell on/off control for green ultra-dense networks. In: 2016 8th international conference on wireless communications & signal processing (WCSP), Yangzhou, China, 13–15 October 2016, pp.1–5. New York: IEEE.

12.

Hasan

Bansal

Hossain

. Energy-efficient power allocation in OFDM-based cognitive radio systems: a risk-return model. IEEE T Wirel Commun 2009; 8(12): 6078–6088.

13.

Gan

Wang

Feng

. Energy efficient switch policy for small cells. IEEE Commun Mag 2015; 12(1): 78–88.

14.

Federal Communications Commission (FCC). First report and order. FCC 02-48, 2002. Washington, DC: Federal Communications Commission Std.

15.

Mitola

. Software radio architecture: a mathematical perspective. IEEE J Sel Area Comm 1999; 17(4): 514–538.

16.

Gao

Wang

. Spectrum trading in cognitive radio networks: a contract-theoretic modeling approachIEEE J Sel Area Comm 2012; 29(4): 843–855.

17.

Zhang

Lee

Niyato

. Auction approaches for resource allocation in wireless systems: a survey. IEEE Commun Surv Tut 2013; 15(3): 1020–1041.

18.

Pan

Zhang

. Spectrum harvesting and sharing in multi-hop CRNs under uncertain spectrum supply. IEEE J Sel Area Comm 2012; 30(2): 369–378.

19.

Zhu

. Core-selecting secondary spectrum auctions. IEEE J Sel Area Comm 2014; 32(11): 2268–2279.

20.

Ding

Pan

. Users first: service-oriented spectrum auction with a two-tier framework support. IEEE J Sel Area Comm 2016; 34(11): 2999–3013.

21.

Huang

Berry

Honig

. Spectrum sharing with distributed interference compensation. In: First IEEE international symposium on new frontiers in dynamic spectrum access networks (DySPAN 2005), Baltimore, MD, 8–11 November 2005, pp.88–93. New York: IEEE.

22.

Wang

Liu

KJR

. Collusion-resistant multi-winner spectrum auction for cognitive radio networks. In: IEEE global telecommunications conference (IEEE GLOBECOM 2008), New Orleans, LO, 30 November–4 December 2008, pp.1–5. New York: IEEE.

23.

Chen

Iellamo

Coupechoux

. An auction framework for spectrum allocation with interference constraint in cognitive radio networks. In: Proceedings of IEEE INFOCOM, San Diego, CA, 14–19 March 2010, pp.1–9. New York: IEEE.

24.

Teng

Zhang

Niu

. Reinforcement learning based auction algorithm for dynamic spectrum access in cognitive radio networks. In: IEEE 72nd vehicular technology conference fall (VTC 2010-Fall), Ottawa, ON, Canada, 6–9 September 2010, pp.1–5. New York: IEEE.

25.

Pal

Kundu

Chatterjee

. Combinatorial reverse auction based scheduling in multi-rate wireless systems. IEEE T Comput 2007; 56(10): 1329–1341.

26.

Niyato

Hossain

. Competitive spectrum sharing in cognitive radio networks: a dynamic game approach. IEEE T Wirel Commun 2008; 7(7): 2651–2660.

27.

Zhang

Cai

. Exploiting spectrum availability and quality in routing for multi-hop cognitive radio networks. In: Proceedings of wireless algorithms, systems, and applications (WASA 2016), Bozeman, MT, 8–10 August 2016, pp.283–294.

28.

Zhang

Cai

. Spectrum-availability based routing for cognitive sensor networks. IEEE Access 2017; 5: 4448–4457.

29.

Zheng

Cai

. An application-aware scheduling policy for real-time traffic. In: 2015 IEEE 35th international conference on distributed computing systems (ICDCS), Columbus, OH, 29 June–2 July 2015, pp.421–430. New York: IEEE.

30.

Zheng

Cai

. A study on application-aware scheduling in wireless networks. IEEE T Commun 2016; 16: 1787–1801.

31.

Wang

Liu

KJR

. A multi-winner cognitive spectrum auction framework with collusion-resistant mechanisms. In: 3rd IEEE symposium on new frontiers in dynamic spectrum access networks (DySPAN 2008), Chicago, IL, 14–17 October 2008, pp.1–9. New York: IEEE.

A multi-greedy spectrum auction algorithm for cognitive small cell networks

Abstract

Keywords

Introduction

System model

Cognitive small cell network

Auction model

Spectrum allocation algorithms

Primitive greedy algorithm

Multi-greedy algorithm

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References