Sage Journals: Discover world-class research

Abstract

With the explosive demand for wireless communications, users are always experiencing poor quality-of-services. Spectrum auction is a promising approach to allocate spectrum resources in wireless networks. Most of the previous works ignored social characteristics of users in wireless networks which influence the allocation of spectrum resources. In this article, we study the spectrum auction problem in a femtocell network and jointly exploit the social reciprocity of users for optimizing the allocation of spectrum resources. We propose an auction incentive framework combined with social reciprocity in the femtocell network. Such a matter is formulated as an integer programming optimization problem, and a modified quantum genetic algorithm is developed to solve the optimization problem. Besides we propose a payment rule satisfying truthfulness and individual rationality properties. Simulation results show that our algorithm can achieve the optimal solution to the optimization problem.

Keywords

Femtocell network spectrum auction social reciprocity modified quantum genetic

Introduction

The increasing demand for wireless services has posed challenges to the existing wireless communication networks. Also, most of these growing data streams have occurred indoors, and weak signal area and even fade area often happened due to signal transmission fading. Therefore, it is important to improve the quality of services (QoSs) of users through efficient resource allocation. One question arises, that is, can we leverage user’s social features appeared in social networks to improve the efficiency of resource allocation? So, how to efficiently and flexibly utilize radio spectrum resources becomes a key design challenge of the next-generation wireless network.

Femtocell is a newly emerging technology to address the problem of poor indoor coverage and wireless capacity limitation.¹ In the two-tier macro-femtocell network, femtocell access point (FAP) owners can autonomously deploy it in room to increase hot-spot service,² so femtocell is enabled by a short-range low-cost home base station (BS) installed by end consumers to provide high-speed data access. FAP can help users to access the core network via themselves as a relays with less power.³ Femtocell connects with the core network through broadband Internet Protocol (IP), such as digital subscriber line (DSL) or cable modems. In addition, it is important to choose the proper access control mechanism. According to De la Roche et al.,⁴ there are three mainstream access control mechanisms: (1) closed access, only femtocell users can access the femtocell; (2) open access, any user can access the femtocell; (3) hybrid access, femtocell users can access the femtocell and other users can access the femtocell with certain restriction. Furthermore, Zheng et al.^5,6 have proposed a new network model to improve user experience by pushing the scheduling problem to the task layer, which improves quality of experience (QoE) through link scheduling.

As we know, dynamic spectrum sharing has been considered as an effective method to better utilize the limited spectrum resources.⁷ In order to use the spectrum effectively, Zhang et al.^8,9 proposed novel routing metrics that estimate both the future spectrum availability and the average transmission time. And many research works have dedicated to optimize the spectrum resource management,^10,11 which can achieve the Pareto optimal payoff vectors. As we know, auction theory is a special game. It is the most well-known market-based mechanism to redistribute resources.¹² Auction has been widely applied to wireless communications, especially in spectrum auction.^13–15 By dynamically distributing the idle channels of primary users (PUs) to secondary users (SUs), the spectrum utilization can be greatly improved. Wang et al.¹⁶ proposed a truthfulness auction between PUs and SUs to avoid market manipulation and considered both QoS demands and spectrum spatial reuse. Zheng et al.¹⁷ studied the problem of dynamic channel redistribution by jointly considering the five design challenges, including strategy-proof, spatial reusability, channel heterogeneity, bid diversity, and system utility maximization. Also, an extensible and flexible truthful auction framework has been designed, which has proposed attribute-aware auctions that take the channel diversity into consideration, using a novel procedure to prevent bidder self-collusion resulted from the bid diversity.¹⁸ Chen et al.¹⁹ have addressed the incentive issue of access femtocell, and the utility of both wireless service provider and femtocell owner was significantly improved. Hua et al.²⁰ proposed a truthful Vickrey–Clarke–Groves (VCG) auction-based incentive framework for open access femtocells, but they only considered the selfish of femtocell owners. Zhan et al.²¹ have considered a coexistence network that involves one spectrum provider sharing unused spectrum resources to multiple heterogeneous secondary networks, designing a unilateral VCG-based auction for multiple heterogeneous secondary networks. However, they did not consider the demand of users. Some papers have proposed the reverse auction for spectrum auction; Chen et al.¹ proposed a reverse auction framework for fair and efficient access permission transaction, which allows range outcome. Zhang et al.²² studied resource allocation among multiple network service providers and designed a reverse combinatorial auction game for optimal total system throughput with personal QoS requirement. Finally, they get the suboptimal solution.

However, the number of network users has increased dramatically, whether user can generate more system benefits with a band or reduce the own costs for the same utility. As we know, user devices are carried by human beings who have social relationship with each other. Can we use the user’s behaviors appeared in social network to improve the efficiency of the whole system? Certainly, with the explosive growth of online social networks and diverse network access methods, more and more people are actively involved in social interactions; hence, the connections of social ties among human beings are strengthened and stabilized.²³ Research on mobile social network has exhibited stable social structure, for instance centrality, bridge, and social community.²⁴ Gong et al.²⁵ designed an incentive mechanism to provoke users to help each other using a synergistic marriage of social trust and social reciprocity. Besides, users with social ties in the social network may stay far away from each other, others with shouter physical are more convenient to share resources, and social ties play an unprecedented role in user’s interaction with others. For example, individuals with close friendship may have similar interests, which means they tend to have similar preference for the same data content.²⁶ They can get information from each other. Therefore, we construct the social reciprocity mutual considering both physical and social factors. Users with similar interests are likely to have similar behavior, such as downloading the same popular contents, and users can select an appropriate partner who has the target content. Then, a user can obtain his or her needs from his or her partner, also the users who have the desired contents would like to share their data with partner, so the entire system performances can be improved.²⁷ In this article, we leverage the social property appearing in the human social network to improve the performance of resource allocation. During the spectrum auction, A and B compete for the same frequency band and they submit the same bid. If A can share data with others and produce a better system utility than B, then A gets the band, even A’s bid is lower than B.

This article aims to maximize the system utility of the spectrum resources. In addition to maximizing the system utility, we also consider the frequency spatial reuse. As far as we know, this is the first work to consider spectrum auction mechanism with spatial frequency reuse and social reciprocity in femtocell networks. In order to solve the optimization problem finally formed, we have developed a modified quantum genetic algorithm (MQGA) based on the auction mechanism. The major contributions of this article are summarized as follows:

We combine the user’s social characteristics with spectrum allocation in femtocell network and propose a spectrum auction mechanism in femtocell networks.

We develop the MQGA to obtain the solution to the final formation of the problem.

We propose a new payment rule and demonstrate that can ensure both truthfulness and individual rationality.

The rest of this article is organized as follows. In section “System model,” system model and spectrum auction model have been described. In section “Problem formulation,” we introduced the problem formed in detail. Section “Solution algorithm” describes the quantum genetic algorithm based on the auction mechanism to obtain the solution to the spectrum auction. In section “Payment rules,” we introduce the payment rule in detail and prove its properties. Next, simulation results are presented to evaluate the proposed algorithm in section “Simulation results.” Finally, section “Conclusion” draws the conclusions of this article.

System model

In this section, we describe our spectrum auction model combined with social reciprocity in detail. We first describe the femtocell network and then introduce users’ relationship of mutual benefit embodying in social network. Next, the spectrum auction model is explained.

Femtocell network

We consider a two-tier macro-femtocell network with some FAPs and femtocell user equipments (FUEs), as shown in Figure 1. Macrocell base station (MBS) is located at the center, and FAPs are distributed within the coverage of MBS. MBS can collect the channel state information and request from buyers. The macrocell user equipments (MUEs) are regarded as PUs who have licensed spectrum band and FUEs are regarded as SUs who need to get frequency band to access network, and SUs can access the cellular network if they are under the cover of the FAP. All the SUs are randomly distributed under the coverage of the femtocell. Specially, it is closer to practical application than FAPs sparsely deployed scenario and each FAP only serves one user in time slots. For analytical tractability, we assume the number of users served by femtocells is not beyond the capacity of the FAPs and all SUs are equipped with a single antenna. The SUs share spectrum with PUs when the PUs have vacant bands. All femtocells are connected to the core network through fibers and then to MBS. SUs want to get spectrum bands from PUs to transmit their data. Meanwhile, PUs would like to lease bands to SUs for monetary gains. In our model, a trusted third-party serves as auctioneer who helps to coordinate the whole auction. Due to the fact that femtocells can shorter the communication distance between users, it reduces the transmission power of both femtocell and SUs. When SUs communicate via different femtocells, they can share the licensed spectrum band synchronously if there is no interference between them.

Figure 1.

Femtocell system model with social reciprocity.

Social reciprocity extraction

With the introduction of femtocells, the number of users can form a mobile social network. There are two domains in the proposed framework: social domain and physical domain. Each user in the physical domain corresponds to a human being in the social domain. Different users may have the same characteristics in networks, such as interest similarity, social trust, and social reciprocity. In fact, users with similar interests are more likely to become friends, and individuals with strong social strength have similar interest in the same content. They are willing to cooperate to help get data for each other and share information. They may both benefit from this situation. Such social feature information can be easily obtained from online social networks. We think all users have their own interest list, and there are $L$ resource types in the femtocell network. According to the user’s request, we can get the interest list of users, marked as $T_{il} \in {0, 1}$ , where 1 suggests user $i$ has requested $l$ class resource and 0 suggests he has not requested. In our scheme, we use the Jaccard similarity²⁸ and the user’s physical distance to define the social mutual factor between SUs marked as $t_{ij}$ . Formally, we describe $t_{ij}$ as

t_{ij} = \frac{1}{l_{ij}} J_{ij}

(1)

where $l_{ij}$ is the distance between users $i$ and $j$ , and $J_{ij}$ is the Jaccard coefficient of users $i$ and $j$ . Its common expression is denoted as

J_{ij} = \frac{| T_{i} \cap T_{j} |}{| T_{i} \cup T_{j} |}

(2)

where $T_{i}$ denotes interest list of user $i$ .

Specially, as shown in Figure 1, the user in same color has the characteristics of social reciprocity properties. They can assist each other, as SU1 and SU2. They are interested in same network resource. With the human social properties, they will help cache the data for each other. They can use the frequency band for information communication, and to a certain extent, they can share their resources.

Auction model

The auction mechanism consists of three entities: the spectrum owners, the secondary wireless service providers, and a third-party auctioneer who manages the auction. We assume that each buyer (seller) demands (supplies) only one channel and each channel is allowed to be sold to the buyers who do not interfere with each other. Thus, the channel allocation can be modeled as double auction, which is controlled by an auctioneer, and time is slotted. We consider the number of PUs and SUs are $M$ and $N$ . Our study focus on one time period that comprises enough slots for the proposed scheme to converge to the optimal solution. The seller is PU in the spectrum auction, contains $M$ free spectrum bands denoted as $M = {f_{1}, f_{2}, \dots, f_{M}}$ . Each seller submits his or her ask to the auctioneer, denoted as $a = {a_{1}, a_{2}, \dots, a_{M}}$ , which indicates the cost of the seller for supplying its channel, where $a_{j}, 1 \leq j \leq M$ asks price of seller $j$ . Each buyer has a valuation for all spectra, denoted as $u = {u_{1,} u_{2}, \dots, u_{N}}$ , within $u_{i} = {u_{i 1}, u_{i 2}, \dots, u_{iM}}, 1 \leq i \leq N$ , which indicates the benefits that the buyer can obtain from winning a channel. Based on buyer’s valuation, buyers submit their bids $b_{i} = {b_{i 1}, b_{i 2}, \dots, b_{iM}}, 1 \leq i \leq N$ , which represent the bid price vector of buyer $i$ for the $M$ channels. These asks are private and independent, also, the bid is private and independent from each other. After the auction, we can calculate payment for winners. We think that only if the bid is greater than the corresponding ask, the buyer is likely to win the spectrum band. So, based on the information the auctioneer has collected, the auctioneer decides the allocation vector $X = {x_{ij}}_{N \times M}$ , with $x_{ij} = 1$ means SU $i$ wins spectrum $j$ , otherwise failure in the auction. Accordingly, during the auction, seller $i$ sold a band. Let $p_{i}^{s}$ be the payment from the auctioneer, so the utility can be defined as $u_{i}^{s} = p_{i}^{s} - a_{i}$ ; otherwise $u_{i}^{s} = 0$ , and each buyer offers price to purchase band, if buyer $i$ wins. Let $p_{i}^{b}$ denote the price needed to be paid to auctioneer, so the utility of $i$ can be defined as $u_{i}^{b} = u_{i} - p_{i}^{b}$ ; otherwise $u_{i}^{b} = 0$ . Generally, $p_{i}^{s}$ and $p_{i}^{b}$ are different, and the auctioneer profit is $p_{i}^{b} - p_{i}^{s}$ , that is, the auctioneer collecting all ask/bid information from sellers and buyers. Then, the auctioneer decides the allocation solution and payment for both win sellers and buyers.

For each buyer, according to the difference of spectrum, such as channel quality and degree of buyers demand, we define the evaluation function of buyers. Without loss of generality, we deem that all SUs use same valuation function. Even though the function is shared, the values of the parameters of the function are private.²⁹ We use $u_{ij}$ to characterize user $i$ valuation for spectrum $j$ . The private value is defined as

u_{ij} = d_{i} B_{j} \log_{2} (1 + SIN R_{ij})

(3)

where $d_{i}$ denotes the utility gain ratio of user $i$ , reflecting how much SU $i$ values the band $j$ ; $B_{j}$ represents the size of spectrum $j$ ; $SIN R_{ij} = P {| h_{ik} |}^{2} / (n_{0} + I_{j})$ is the received signal to interference plus noise ratio (SINR) of user $i$ when using band $j$ , where $P_{i}$ is the transmission power of FAP and $h_{ik}$ is the average channel gain of link between FAP $k$ and SU $i$ on channel $j$ and combines the impact of path loss and large-scale fading. Specifically, we have $h_{ik} = g_{ik} d_{ik}^{- γ}$ , where $g_{ik}$ is the fading gain between FAP $k$ and SU $i$ on channel $j$ , $d_{ik}$ is the distance between FAP $k$ and SU $i$ , $γ$ is the path loss exponent,⁷ $n_{0}$ is the background noise power, and $I_{j}$ is the aggregate interference power which comes from MBS.

As there are a lot of SUs competing for the limited spectrum resources, this can lead to a phenomenon that some SUs obtain multiple bands, while others are starved.³⁰ Spectrum can be reused among SUs subjecting to the spatial interference limits: buyers in close proximity cannot use the same spectrum band simultaneously but well-separated buyers can.³¹ In our system, SUs are served by multiple FAPs. The interference between two SUs is the interference between the two serving FAPs. If there are two SUs interfering with each other, the distance between their serving FAPs is shorter than the interference distance threshold $d_{m}$ . We assume each SU can win at most one band as the communication distance is shorted. We consider the influence of social properties appearing in the social network on the allocation of resources. Using the inherent interplay between social network and wireless communication, individuals with social ties and similar interests tend to have similar preference for same data content. They can establish a cooperative relationship, help to get data for each other, and share information. In order to improve system utility, spectrum will be assigned to one who produces higher benefit, if their bids are same.

Problem formulation

According to the principles discussed above, our target is to improve the spectrum efficiency in femtocell networks, so the auction mechanism is designed to maximize system utility, equal to the sum of all winner valuation, which will reflect the win users’ efficiency of frequency band. Then, we can get an optimization problem and propose an algorithm to solve this problem and get a suboptimal allocation.

Overall, we define the utility of SU $i$ as

v_{ik} = u_{ik} + \sum_{t \neq i}^{N} t_{it} v_{t}

(4)

where $v_{ik}$ denotes the gain of SU $i$ when using spectrum $k$ and $v_{t}$ denotes the utility of other user who has social relationship of mutual benefit with SU $i$ . Then, our system maximization utility can be expressed as

U = \sum_{i}^{N} \sum_{k}^{M} x_{ik} v_{ik}

(5)

In order to solve the assignment problem, the goal of allocating spectrum bands to the SUs who value them most, that is, to maximum system utility, can be formulated as the following optimization problem

\begin{matrix} max U = \sum_{i}^{N} \sum_{k}^{M} x_{ik} v_{ik} \\ s . t . {\begin{matrix} x_{ik} \in {0, 1}, \forall i \in N, \forall k \in M \\ x_{ik} + x_{lk} \leq 1, k \in M, if C_{il} = 1 \\ \sum_{k}^{M} x_{ik} \leq 1, \forall i \in N \end{matrix} \end{matrix}

(6)

The first constraint in equation (6) indicates that if one wins a spectrum band, $x_{ij} = 1$ , otherwise $x_{ij} = 0$ ; the second constraint is the interference matrix of SUs, if $C_{il} = 1$ , means that SU $i$ and SU $l$ exist in the co-channel interference, so the two SUs cannot be assigned the same frequency band; the third constraint represents that one SU can only win a spectrum band.

Obviously, our problem can be converted into a 0–1 programming problem. As we know, the optimization problem is NP-hard (non-deterministic polynomial-time hard). There is no polynomial-time algorithm to solve it. It is a challenge to obtain the optimal solution. In theory, it can get the optimal solution by enumeration methods. But considering the fact that the computational complexity of exhaustive searching methods is exponential, when the number of users is large, it becomes an infeasible solution. So, we develop a quantum genetic algorithm to solve this problem and have resulted in a good solution.

Solution algorithm

As the spectrum auction problem can be inherently seen as an optimization problem, we have developed an MQGA to solve it. It has three sections: chromosome code, measures, and update. It is a new optimum method that combines quantum computation with genetic algorithm and has significant value in research and application. MQGA is established on the basis of the quantum state vector expression, applying the probability of quantum bits in the chromosome code, which makes a chromosome to be expressed as the stack of multiple states, and uses quantum rotating gates to realize the chromosome update operations, and are mutated by quantum non-gate.

Getting feasible matrix

According to the seller’s ask and buyer’s bid and the matrix interference among SUs, through the auction mechanism, we can get a feasible matrix $W$ which means the space of band users can be obtained through auction. As mentioned before, $N$ SU indices from 1 to $N$ are competing for $M$ spectrum channels index from 1 to $M$ which are orthogonal. The feasible matrix $W = {w_{nm}}_{N \times M}$ , where $w_{nm} = 1$ means channel $m$ is available to user $n$ , and if $w_{nm} = 0$ , otherwise.

Overview of the algorithm

We use binary encoding in our algorithm. After obtaining the feasible matrix $W$ , we can get down to chromosome encoding. The string called chromosome consists of lots of genes which store a set of values for optimization variables.³² In order to simplify the operation, we propose to only encode those elements which take value 1 in $W$ . As a consequence, the length of the binary string is equal to the number of elements equal to 1 in $W$ . In this way, the search space is greatly reduced. Figure 2 expresses the process of chromosomes being formed. In this case, $N = 5$ and $M = 3$ . We note that encoding all the elements needs 15 bits, but only encoding the elements with value 1 needs 9 bits, and we have to map the chromosome to the channel assignment to figure up the fitness of the chromosome.

Figure 2.

Example of chromosome structure and its matching.

The initial value of every bit in chromosome is measured by quantum rotating gates. The qubits in chromosome are expressed as

Q_{i}^{g} = [\begin{matrix} \partial_{i 1}^{g} \partial_{i 2}^{g} \dots \partial_{iz}^{g} \\ ρ_{i 1}^{g} ρ_{i 2}^{g} \dots ρ_{iz}^{g} \end{matrix}]

(7)

where $Q_{i}^{g}$ denotes the $i$ chromosome, the maximum value of $i$ is the population size set to $h$ , $g$ represents the generation of population, $z$ is the size of chromosome, in addition, $\partial_{ij}^{g}$ and $ρ_{ij}^{g}$ must satisfy $| \partial_{ij}^{g} |^{2} + | ρ_{ij}^{g} |^{2} = 1$ , and the initial values of $\partial_{ij}^{0}$ and $ρ_{ij}^{0}$ are set to $1 / \sqrt{2}$ on the original population. The population of MQGA can be denoted as $Q^{g} = {Q_{1}^{g} Q_{2}^{g} \dots Q_{h}^{g}}$ . The value of j variable in $Q_{i}^{g}$ measure by the probability of the jth qubit $| \partial_{ij}^{g} |^{2}$ . After initialization, the chromosome we get from the above step is probably infeasible for the allocation because it may violate the auction rules we set, so we need to determine the feasibility of the initial solution and then adjust it to make it meet our requirement. The detailed steps are as follows:

Step 1. Based on the initial chromosomes $Q^{0}$ , get the initial distribution matrix $X$ .

Step 2. Inspect the initial distribution matrix $X$ , if $\sum_{i = 1}^{N} x_{ij} > 1, j = (1, 2, \dots, M)$ .

Step 3. If there are no interference among SUs who competed for the same frequency band, SUs who have no mutual interference can gain the band. If there are mutual interference among SUs is 1, we should according their bids to select the SU who has maximum price, and the allocation value remains 1, other set 0.

Step 4. Then, check whether a band is not occupied in the distribution matrix; if exist, choose the band which has the highest valuation among SUs who have no occupied band.

Then, we use MQGA to optimize the result of Step 4. We directly use the objective function as the fitness function. MQGA uses quantum rotate gate to realize population evolution; once the quantum rotate gate and the population are updated, the update operation of the quantum rotate gate is expressed as

(\begin{matrix} \partial_{ij}^{g + 1} \\ ρ_{ij}^{g + 1} \end{matrix}) = (\begin{matrix} \cos θ_{i} \\ \sin θ_{i} \end{matrix} \begin{matrix} - \sin θ_{i} \\ \cos θ_{i} \end{matrix}) (\begin{matrix} \partial_{ij}^{g} \\ ρ_{ij}^{g} \end{matrix})

(8)

where $θ_{i} = γ \cdot Δ θ, (γ = \pm 1)$ , $Δ θ$ is the rotation angle resize, set an appropriate value at the time of simulation, and $γ$ is the direction of the rotation angle, this variable ensures the convergence of the algorithm. $f (x)$ denotes the present fitness of the chromosome, $f (o)$ denotes the fitness of the optimal chromosome at present, for example, when the chromosome code bit $x_{i} = 0, o_{i} = 1$ , and $f (x) > f (o)$ , we should increase the probability of the current solution to take state 0, this helps the current solution converge to a higher fitness of chromosome. The whole algorithm is elaborated in Algorithm 1.

Algorithm 1. QGA-based spectrum auction algorithm.
Input: $a$ , $b$ , $θ$ , $C$ and $t$ . Output: the optimal solution $X$ to the spectrum auction problem. 1. Initialize, set $g = 0$ and population size $h$ , set the number of qubits in the chromosome as $\sum_{n = 1}^{N} \sum_{m = 1}^{M} x_{nm}$ ; 2. Set the initial quantum rotate gate, and map all the bit of $Q_{i}^{0}$ to $X$ for every chromosomes; 3. Get feasible solution through four steps; 4. Compute the fitness values of $Q^{g}$ , store the current best solution; 5. Determine whether reach the maximum generation, if so, terminate the algorithm, else, go to step 6; 6. Set g = g+1, update the quantum gate then get the next population; 7. Then, go to 3 step operation, until the end of algorithm. 8. Return $X$ .

Algorithm 1. QGA-based spectrum auction algorithm.

Input:

a

b

θ

C

and

t

.
Output: the optimal solution

X

to the spectrum auction problem.
1. Initialize, set

g = 0

and population size

h

, set the number of qubits in the chromosome as

\sum_{n = 1}^{N} \sum_{m = 1}^{M} x_{nm}

;
2. Set the initial quantum rotate gate, and map all the bit of

Q_{i}^{0}

X

for every chromosomes;
3. Get feasible solution through four steps;
4. Compute the fitness values of

Q^{g}

, store the current best solution;
5. Determine whether reach the maximum generation, if so, terminate the algorithm, else, go to step 6;
6. Set g = g+1, update the quantum gate then get the next population;
7. Then, go to 3 step operation, until the end of algorithm.
8. Return

X

The result of spectrum auction is a suboptimal solution. In order to check up the accuracy of the algorithm, we get the optimal solution by applying the exhaustive search method. Moreover, we compare with greedy algorithm to verify the performance of our algorithm.

Computational complexity analysis

We compare the computational complexity of our algorithm with exhaustive search and greedy algorithm. The optimization problem is a classic NP-hard. There is no exact algorithm to solve this kind of problem. Exhaustive search needs to traverse whole solution space and then get the optimal solution. It can be easily proved that the computational complexity of exhaustive search is $O (2^{NM})$ . When $N$ and $M$ are large enough, it is not suitable to solve this problem since the complexity is exponential. The greedy algorithm, which aims at maximizing the utility in each loop, repeats $M$ times, and in each loop less than $N$ SUs are considered, so the computational complexity is $O (MN)$ .

For the proposed algorithm, which aims to get the optimal solution in each iteration, the population size is set to $h$ and is repeated $g$ times. From Figure 3, the proposed algorithm can obtain the optimal solution within 10 iterations. Moreover, it performed four steps to get feasible solution, and repeats $M$ times at most, and each loop is not more than $N$ . So, the computational complexity of our proposed algorithm is $O (hgMN)$ . Obviously, the complexity of exhaustive search is bigger, and from the simulation results, it is known that MQGA has better performance than greedy algorithm.

Figure 3.

Sum utility comparison between MQGA and exhaustive search.

Payment rules

After getting the solution, the third-party computes the price each buyer should pay according to plan of resource allocation.²⁰ we define it as follows

p_{ij} = b_{i} + U (x_{i}^{*}) - U_{i} (x)

(9)

where $x^{*}$ is the optimal feasible solution to the objective function, $U (x_{i}^{*})$ is the optimal solution of objective function except $i$ , and $x$ denotes the solution to the same problem without considering the vector $b_{i}$ . And $U_{i} (x)$ is the optimal solution of the same problem without considering the vector $b_{i}$ . And the utility achieved by it is $s_{i} = p_{ij} - u_{i}$ . Based on the above price rule, we then have proved some important properties of our auction.

Truthfulness

The payment rule satisfies the truthfulness property, and its bid is equal to its private valuation, a weakly dominant strategy.

Proof

Similarly, we let $x^{*}$ and $x$ represent the solution to the problem, as stated above. To prove the theory, we have to show that $s (u_{i}) \geq s (b_{i}), \forall u_{i} \neq b_{i}$ .

The utility of the bid submitted by bidder $i$ , when declaring $u_{i}$ , is equal to

s (u_{i}) = p_{ij} (x^{*}) - u_{i} = u_{i} + U (x_{i}^{*}) - U_{i} (x) - u_{i}

(10)

In the other, when bidding a false valuation $b_{i}$ , $u_{i} \neq b_{i}$ , aiming to improve its utility by cheating. As a result, the utility can be written as

s' (b_{i}) = p_{ij} (x^{*}') - u_{i} = b_{i} + U (x_{i}^{*}') - U_{i} (x') - u_{i}

(11)

where $U_{i} (x^{'}) and U (x_{i}^{*'})$ are corresponding optimal solutions of the bid vector set ${u_{1}, u_{2}, \dots, b_{i}, \dots, u_{n}}$ . So, the loss of the utility can be computed as

\begin{matrix} Δ s_{i} = U (x_{i}^{*}) - U_{i} (x) + U (x') - U (x_{i}^{*}') - b_{i} + u_{i} \\ = U (x_{i}^{*}) - U (x_{i}^{*}') - U_{i} (x) + U (x') + u_{i} - b_{i} \end{matrix}

(12)

Since $U_{i} (x) = U_{i} (x')$ , then

Δ s_{i} = U (x_{i}^{*}) + u_{i} - [U (x_{i}^{*}') + b_{i}]

(13)

As the unreal bid $b_{i}$ satisfies the constraints of our spectrum auction mechanism, $x^{*}$ is the solution that maximizes the original problem shown in equation (6). Hence, we have $U (x_{i}^{*}) + u_{i} \geq [U (x_{i}^{*'}) + b_{i}]$ , thus $Δ s_{i} \geq 0$ . It indicates that one cannot unilaterally increase its utility by submitting a bid vector different from its private value, and we complete our proof.

Individual rationality

The utility gained for each winner seller is not negative value.

Proof

According to the above, as we have proved that our scheme is truthful, $b_{i} = u_{i}$ , and the utility of a winning seller is $s_{i} = U (x_{i}^{*}) - U_{i} (x)$ , noting that $U_{i} (x)$ can be regard as the optimal solution when $b_{i} = 0$ , and the bid vectors from others remain unchanged. So, the result solution set with $b_{i} = 0$ is just a subset of the solution space to the formed problem. Therefore, the value of $U_{i} (x)$ is always more than $U (x_{i}^{*})$ , and $s_{i} \geq 0$ , and we complete our proof.

Simulation results

The main purpose of our simulation is to show the advantage of social network feature to resource allocation and compare the performance of our proposed algorithm to exhaustive search method. We use MATLAB to verify the proposed algorithm.

For simplicity, we consider a BS standing in the center of a cell. We assume that FAPs are randomly distributed in the range of [500, 500]. The coverage range of each FAP is fixed as 15 m, and SUs are distributed under the scope of femtocell. Besides, the interference distance threshold is set to $d_{m} = 300 m$ . We consider a scenario where there are four PUs and seven SUs in our spectrum auction system. We can use channel model in the work by Ma et al.,¹¹ in which the path loss exponent is set to 3, the FAP transmission power is 20 dBm, and the noise interference is set to 1. We set the auction of spectrum bandwidth as 1 MHz. The seller’s reserve price is uniformly distributed over [0, 1].¹⁶ For social reciprocity mechanism, we can reference the data set released by Stanford University,³³ which was generated by surveying a number of volunteer social network users, known as ego nodes. The data set in the work by Pietilainen and Diot³⁴ contained the user’s social profiles, friends, proximity, and interests. Similar to Gong et al.,²⁵ we can get social reciprocity factor that we use. Then, we choose the parameters of the MQGA. We refer to Zhao et al.,³⁵ which can be expressed as: the population size is 20, and the increment of rotation angle of quantum gates decreased linearly from $0.1 π$ at the first generation to $0.005 π$ at the last generation.

Our work is dedicated to maximum system utility, which is the total valuation of winning buyers in the auction. As shown in Figure 3, the suboptimal solution is almost as good as the optimal solution in terms of sum utility. With the update of the population, we can find the sum utility gradually increases, ultimately achieves the optimal value. Our designed mechanism can reach convergence only after six iterations. Considering the high computational complexity of exhaustive search when a large number of users participate in the spectrum auction, our developed algorithm is more applicable.

Next, we examine the impact of social reciprocity factor on the utility of the femtocell network. As shown in Figure 4, we consider the influence of social reciprocity among SUs. We can get a higher sum utility than that without social reciprocity. Besides, through comparison, when considering the social reciprocity factor, the spectral efficiency has been improved after an SU obtains a frequency band. Also, it can improve the satisfaction of users under the coverage of the femtocell. This also motivates SUs to have higher valuation for the frequency bands.

Figure 4.

Sum utility comparison with and without social reciprocity.

In Figure 5, the number of frequency bands provided by PUs is changed from 1 to 10 in order to compare the utility obtained by two different cases. From Figure 3, we clearly know that our proposed algorithm can approach the optimal solution. From Figure 5, we can see that all of them possess a rising trend. Obviously, our proposed spectrum auction mechanism can significantly improve the femtocell network utility than the one without considering the effect of social reciprocity.

Figure 5.

Comparison of the utility versus number of frequency bands.

Figure 6 shows the variation trend of the sum utility when the number of frequency bands increases. We can see that the sum utility increases with the number of frequency bands for both greedy algorithm and MQGA. Furthermore, our proposed algorithm has a better performance than the greedy algorithm.

Figure 6.

Sum utility comparison versus number of frequency bands.

Conclusion

In this article, we combined the social reciprocity to formulate a spectrum auction mechanism. The SUs in femtocells can obtain the available unused bands from multiple licensed users. An auction incentive framework was proposed, and an optimization problem was formulated which was NP-hard. Then, we proposed an MQGA to solve the optimization problem for spectrum allocation. Besides, a payment rule was proposed to guarantee the truthfulness and individual rationality properties. Simulation results showed that our proposed scheme could achieve the optimal solution to the optimization problem.

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 and 61671165), the Guangxi Natural Science Foundation (2015GXNSFBB 139007 and 2016GXNSFGA380009), the Fund of Key Laboratory of Cognitive Radio and Information Processing (Guilin University of Electronic Technology), Ministry of Education, China and the Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (CRKL150104 and CRKL160105), and the Innovation Project of GUET Graduate Education (2016YJCX87, 2017YJCX39).

References

Chen

Zhang

. A reverse auction framework for access permission transaction to promote hybrid access in femtocell network. In: Proceedings of the IEEE INFOCOM, Orlando, FL, 25–30 March 2012, pp.2761–2765. New York: IEEE.

Chandrasekhar

Andrews

Gatherer

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

Cheung

Quek

TQS

Kountouris

. Spectrum allocation and optimization in femtocell networks. In: Proceedings of the IEEE international conference on communications (ICC), Ottawa, ON, Canada, 10–15 June 2012, pp.2473–2478. New York: IEEE.

Roche

Valcarce

Lopez-Perez

. Access control mechanisms for femtocells. IEEE Commun Mag 2010; 48(1): 33–39.

Zheng

Cai

. A study on application-aware scheduling in wireless networks. IEEE T Mobile Comput. Epub ahead of print 26 September 2016. DOI: 10.1109/TMC.2016.2613529.

Zheng

Cai

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

Zhao

Sadler

BM.

A survey of dynamic spectrum access. IEEE Signal Proc Mag 2007; 24(3): 79–89.

Zhang

Cai

. Exploiting spectrum availability and quality in routing for multi-hop cognitive radio networks. In: Proceedings of the 11th international conference on wireless algorithms, systems, and applications (WASA), Bozeman, MT, 10 August 2016, pp.283–294. New York: IEEE.

Zhang

Cai

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

10.

Gharehshiran

Attar

Krishnamurthy

Collaborative sub-channel allocation in cognitive LTE femto-cells: a cooperative game-theoretic approach. IEEE T Commun 2013; 61(1): 325–334.

11.

Cheung

Wong

VWS

. Hybrid overlay/underlay cognitive femtocell networks: a game theoretic approach. IEEE T Wirel Commun 2015; 14(6): 3259–3270.

12.

Koutsopoulos

Iosifidis

. Auction mechanisms for network resource allocation. In: Proceedings of the 8th international symposium on modeling and optimization in mobile, ad hoc, and wireless networks, Avignon, 31 May–4 June 2010, pp.554–563. New York: IEEE.

13.

Wang

. Spectrum sharing in cognitive radio networks—an auction-based approach. IEEE T Syst Man Cy B 2010; 40(3): 587–596.

14.

Chen

Iellamo

Coupechoux

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

15.

Zhou

Zheng

. TRUST: a general framework for truthful double spectrum auctions. In: Proceedings of the IEEE INFOCOM, Rio de Janeiro, 19–25 April 2009, pp.999–1007. New York: IEEE.

16.

Wang

. A truthful QoS-aware spectrum auction with spatial reuse for large-scale networks. IEEE T Parall Distr 2014; 25(10): 2499–2508.

17.

Zheng

Chen

A strategy-proof combinatorial heterogeneous channel auction framework in noncooperative wireless networks. IEEE T Mobile Comput 2015; 14(6): 1123–1137.

18.

Cheng

. An extensible and flexible truthful auction framework for heterogeneous spectrum markets. IEEE Trans Cognit Commun Netw 2016; 2(4): 427–441.

19.

Chen

Zhang

Utility-aware refunding framework for hybrid access femtocell network. IEEE T Wirel Commun 2012; 11(5): 1688–1697.

20.

Hua

Zhuo

Panwar

. A truthful auction based incentive framework for femtocell access. In: Proceedings of the IEEE wireless communications and networking conference (WCNC), Shanghai, China, 7–10 April 2013, pp.2271–2276. New York: IEEE.

21.

Zhan

Chou

Chang

. Auction-based spectrum sharing among heterogeneous secondary networks. In: Proceedings of the IEEE international conference on communications (ICC), London, 8–12 June 2015, pp.2160–2165. New York: IEEE.

22.

Zhang

Chang

Hamalainen

. Reverse combinatorial auction based resource allocation in heterogeneous software defined network with infrastructure sharing. In: Proceedings of the IEEE 83rd vehicular technology conference (VTC Spring), Nanjing, China, 15–18 May 2016, pp.1–6. New York: IEEE.

23.

Wang

. Social-community-aware resource allocation for D2D communications underlaying cellular networks. IEEE T Veh Technol 2016; 65(5): 3628–3640.

24.

Hui

Crowcroft

Yoneki

. BUBBLE Rap: social-based forwarding in delay-tolerant networks. IEEE T Mobile Comput 20111; 10(11): 1576–1589.

25.

Gong

Chen

Zhang

. Exploiting social trust assisted reciprocity (STAR) toward utility-optimal socially-aware crowdsensing. IEEE Trans Sig Inf Process Netw 2015; 1(3): 195–208.

26.

Zhu

Zhi

Zhang

. Social-aware incentivized caching for D2D communications. IEEE Access 2016; 4: 7585–7593.

27.

Wang

. Socially enabled wireless networks: resource allocation via bipartite graph matching. IEEE Commun Mag 2015; 53(10): 128–135.

28.

Huang

Tian

Fan

. Social-aware resource allocation for content dissemination networks: an evolutionary game approach. IEEE Access. Epub ahead of print 22 December 2016. DOI: 10.1109/ACCESS.2016 .2643158.

29.

Khaledi

Abouzeid

. ADAPTIVE: a dynamic index auction for spectrum sharing with time-evolving values. In: Proceedings of the 12th international symposium on modeling and optimization in mobile, ad hoc and wireless networks (WiOpt), Hammamet, Tunisia, 12–16 May 2014, pp.513–520. New York: IEEE.

30.

Wang

Ray Liu

. A scalable collusion-resistant multi-winner cognitive spectrum auction game. IEEE T Commun 2009; 57(12): 3805–3816.

31.

Chen

Huang

Sun

. True-MCSA: a framework for truthful double multi-channel spectrum auctions. IEEE T Wirel Commun 2013; 12(8): 3838–3850.

32.

Fei

Min

. Simultaneous feature with support vector selection and parameters optimization using GA-based SVM solve the binary classification. In: Proceedings of the first IEEE international conference on computer communication and the internet (ICCCI), Wuhan, China, 13–15 October 2016, pp.426–433. New York: IEEE.

33.

Leskovec

Stanford large network dataset collection, 2014, https://snap.stanford.edu/data/

34.

Pietilainen

Diot

CRAWDAD dataset thlab/sigcomm (v 2012-07-15), 2009, http://crawdad.org/thlab/sigcomm2009/20120715/

35.

Zhao

Peng

Zheng

. Cognitive radio spectrum allocation using evolutionary algorithms. IEEE T Wirel Commun 2009; 8(9): 4421–4425.

Exploiting social reciprocity for auction-based spectrum allocation in femtocell networks

Abstract

Keywords

Introduction

System model

Femtocell network

Social reciprocity extraction

Auction model

Problem formulation

Solution algorithm

Getting feasible matrix

Overview of the algorithm

Computational complexity analysis

Payment rules

Truthfulness

Proof

Individual rationality

Proof

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References