Multiple-seller and multiple-buyer spectrum sharing model in cognitive radio-based wireless sensor network

Abstract

As the use and scale of wireless sensor networks has grown, the lack of transmission spectrum has become a key factor affecting wireless sensor network quality of service. An effective solution is to collect unused spectrum from primary users (i.e. licensed users) and use that spectrum for wireless sensor networks. In this article, for a cognitive radio-based wireless sensor network, a spectrum sharing strategy between primary users and clusters is proposed. First, as a secondary user (i.e. an unlicensed user), the base station plays a Bertrand game with the monopolists (the primary users) to gain spectrum access on behalf of the clusters. Then, the base station allocates the spectrum band to the cluster heads using the ant colony optimization–based multiple knapsack problem. After obtaining the spectrum, each cluster head programs its nodes’ spectrum according to a timing sequence. Simulation results show that the Bertrand game model is a good choice for determining spectrum pricing and that the ant colony optimization–based multiple knapsack problem algorithm is an efficient way to allocate spectrum dynamically.

Introduction

As wireless communication technology develops, wireless sensor network (WSN) applications are becoming increasingly widespread and application environments have become increasingly complicated; consequently, the existing spectrum sharing scheme fails to meet WSN spectrum demand in many cases. Using cognitive radio technology,^1–4 taking advantage of the idle spectrum owned by primary users under the constraint that such use not affects primary users’ normal communications, secondary users can improve spectral efficiency. However, in WSNs, the spectrum sharing problem that determines how to allocate different spectra to many different nodes is a multiple-seller/multiple-buyer spectrum sharing model.

Assuming that all WSNs can be clustered, meeting WSN spectrum demand is equivalent to solving the spectrum demand in a clustered WSN. In this article, we take a centralized WSN as an example, where the base station acts as a middleman between the primary users and the clusters. In distributed WSNs, we can create a center that knows all the WSN information to act as the middleman. Representing all cluster heads, the base station plays the game with the primary users. Simultaneously, the primary users, who possess different channel qualities, compete on spectrum price. Although the Cournot Game, ⁵ Bertrand Game,^6,7 Stackelberg Game, ⁸ Evolutionary Game, ⁹ and Auction ¹⁰ are available, in this study, the Bertrand Game was chosen because it is popularly applied to model price competition behavior in the oligopoly market and obtain the equilibrium price of each primary user. Thus, the base station buys bandwidth from each primary user depending on the price and the channel quality. Using the multiple knapsack problem (MKP), the base station allocates the purchased spectrum (with different channel qualities) to the clusters based on the size and urgency of each cluster’s requirements. Finally, the cluster head assigns bandwidth to nodes while considering the timing sequence. In this manner, we can achieve a spectrum pricing and dynamic allocation model. The major contributions of this article are as follows:

• Most existing studies focus on multiple sellers selling spectrum to one buyer or one seller selling spectrum to multiple buyers.^11,12 This article solves the problem of multiple sellers selling spectrum to multiple buyers in WSN using game theory and the MKP algorithm.

• It improves the practicality of the spectrum sharing model by considering the importance and urgency of a node’s information and imposing a maximum waiting period for a node.

The remainder of this article is organized as follows. Section “Related work” reviews related works and analyzes the existing problems. The system model and some assumptions made in this article, including the spectrum pricing and dynamic allocation model, are described in section “System model and assumptions.” In section “Spectrum pricing game,” based on the game, the existence of a Nash equilibrium (NE) is proved and the NE is found. After purchasing spectrum, to address the algorithm that describes spectrum allocation, section “Spectrum allocation model” discusses its implementation process. Section “Performance evaluation” presents a quantitative performance analysis, and section “Conclusion and future work” summarizes the work and proposes future work.

Related work

Cognitive radio technology is an effective method for solving spectrum management problems in WSNs. Xing et al. ¹³ and Martin et al. ¹⁴ provided an overview of different spectrum access/sharing models, including the open sharing model, hierarchical access model and the dynamic exclusive use model. These studies also addressed detecting the unused spectrum of primary users.

Game theory, which can maximize the benefits accrued by both primary and secondary users, has been proved to be feasible for a cognitive radio network (CRN). ¹⁵ Based on whether the game participants choose to cooperate, games can be broadly divided into two types: cooperative and non-cooperative games. Non-cooperative games do not achieve overall optimal results for their participants; its players determine their strategies based on local rather than global information.^16,17 Therefore, this study proposes using a cooperative game to achieve spectrum management, because cooperative games outperform non-cooperative games in terms of fairness and efficiency.^18–20 Cooperative and non-cooperative games were compared in detail in Niyato and Hossain^21,22 and Raoof and Al-Raweshidy ²³ in terms of their application environments, network structure, advantages and disadvantages, and so forth.

Most of the studies mentioned above solved spectrum sharing problems in which multiple sellers sell spectrum to one buyer or one seller sells spectrum to multiple buyers. Niyato et al. ⁹ modeled the dynamics of competitive spectrum sharing/pricing among multiple primary users and multiple secondary users in a CRN and proposed a dynamic evolutionary game to analyze the evolutionary and dynamic behavior of secondary users, while a non-cooperative game was formulated to model the competition among primary users in terms of the size of the offered bandwidth and the spectrum price. However, it is this model used the same parameter settings for primary users, which is unrealistic, and secondary users’ spectrum requirements were all considered to be the same. A feedback learning scheme based on the multi-leader multi-follower Stackelberg game model in CRN ²⁴ outperformed many existing schemes in terms of spectrum efficiency, system fairness, throughput, network revenue, and so on. This scheme applied to widely diverse network environment, but obtained only an individual optimal solution. Considering the heterogeneity in terms of primary users’ channel bandwidths and secondary users’ demands, a new combinatorial spectrum auction framework in CRN was proposed for the scenarios in which each primary user had multiple channels to sell and each secondary user demanded multiple channels. ¹⁰ In the proposed auction framework, the winner determination problem was formulated as multiple multidimensional knapsack problem (MMKP) and was solved by a polynomial-time approximation algorithm. Although the proposed auction algorithm can be applied to WSNs, whose total spectrum demand and number of secondary users are larger than the total bandwidth and the number of primary users, it lacks fairness for secondary users who are only weakly competitive and faces the dilemma that the bids of some secondary users always succeed, but the most of the other secondary users will be unable to communicate during any period.

System model and assumptions

We consider a system with M primary users, a base station and N clusters (Figure 1). The M primary users own different spectra (denoted by $F_i$ ) with different bandwidth sizes. As sellers, under the premise that their normal communications remain assured, primary users can benefit from offering unused frequency bands to form pooled spectrum, which can then be leased by secondary users. In the WSN, the N cluster heads function as the secondary users. Then, on behalf of the spectrum demand from all the nodes, they buy a certain bandwidth size from the primary users. However, because it is difficult to achieve having the N cluster heads bargain directly with the M main users, the overall benefit for the WSN cannot be maximized. Therefore, in this article, the base station acts as a middleman and plays a game with the primary users. In the end, both sides come to an agreement on price and bandwidth to achieve maximum profit and benefit.

Figure 1.

System model for spectrum sharing.

Pricing model (Bertrand game)

The M primary users, without cooperating with each other, compete to rent their own spectrum to the base station by controlling their own band prices to maximize their own interests. In economics, this is called an oligopoly market. Each monopolist’s decision will change dynamically in response to the strategies of other monopolists. As a type of oligopoly market game, the Bertrand game is used to analyze the price competition behavior and equilibrium pricing strategy of each primary user. The game’s participants are the M primary users. The strategy of each player is to maximize the unit spectrum price (which is non-negative). The final benefit to the primary user is the accrued income from selling spectrum minus any loss caused by a decrease in the QoS. The spectrum demands of secondary users depend on the available channel quality of the $F_i$ and the price charged by the primary users. Obviously, a secondary user prefers an $F_i$ that has a higher quality and a lower price.

Spectrum allocation model (ant colony optimization–based multiple knapsack problem)

After the base station purchases spectrum, it must allocate the spectrum, which consists of different qualities and quantities, to the N cluster heads to meet spectrum demand. This is a MKP. N items are selectively placed in the M knapsacks in a manner that maximizes the value of the items in the knapsacks. Obviously, each knapsack contains a subset of the N items. This allocation is also an non-deterministic polynomial-time (NP)-hard problem. If the traversal algorithm is used to attempt all possible cases, the calculation complexity becomes an exponential function of M and N; thus, when M or N are relatively large, finding the optimal solution takes too long. The ACO algorithm, as a population-based stochastic meta-heuristic, is amenable to parallel implementation. Therefore, the ACO algorithm can more quickly find an approximately optimal solution of the MKP.^25,26

Assumptions

• The spectrum allocated to the cluster head is used only for communication between the cluster head and its nodes; inter-cluster communication uses a fixed spectrum. Therefore, the spectrum demand of each cluster is related only to the urgency coefficient and the number of nodes in the cluster and does not involve inter-cluster relationships. We assume that there are no spatial differences between the clusters.

• The sensor nodes have the same hardware and adaptive modulation. Therefore, it can be assumed that each node has the same signal-to-noise ratio (SNR) and the same channel quality for the same primary user.

• The required channel quality of each node is 9 dB by default. The channel quality of the primary users ranges from 9 to 22 dB.

• This article considers only the situation in which the purchased bandwidth is less than the node spectrum demand (otherwise, spectrum allocation would not be required because the requirements of all the nodes could be satisfied.).

Spectrum pricing game

In this section, to find the solution of the spectrum pricing game, that is, the NE, we quantify the utility of the primary user and the base station according to the utility function used in Singh and Vives. ²⁷

Utility of secondary user

In Singh and Vives, ²⁷ the utility function of the secondary user, which consists of three parts (the revenue gained from using purchased spectrum to communicate, the cost caused by secondary users’ switch among the frequency spectra, and the payment for radio resource usage), is related to the owned bandwidth, channel quality, spectrum price, and spectrum substitutability

$$U(b)=\sum _{i=1}^M{\omega }_i{b}_i{k}_i^{\left(s\right)}-\frac{1}{2}(\sum _{i=1}^M{b}_i^2+2\nu \sum _{i\ne j}{b}_i{b}_j)-\sum _{i=1}^M{P}_i{b}_i$$ (1)

where $b$ is the set of the sizes of purchased spectrum from all the primary users, that is, $b=\{b_1,\dots ,b_i,\dots ,b_M\}$ , and ${\omega }_i$ is the income from the per-transmission rate of the secondary user. $P_i$ is the spectrum price of primary user $i$ , and $\nu$ is the spectrum substitutability (i.e. $\nu \in [0,1]$ ). When $\nu =0$ , the secondary user prefers a specific spectrum and cannot switch among spectra, while when $\nu =1$ , the secondary user can switch freely. Note that $k_i^{\left(s\right)}$ denotes the spectral efficiency of wireless communication by a secondary user using the spectrum $F_i$ owned by primary user $i$ , and it can be formulated as follows

$$k_i^{\left(s\right)}={\log }_2(1+K\gamma ),\mathrm{where}K=\frac{1.5}{\ln (0.2/\mathrm{BE}{R}^{\mathrm{tar}})}$$ (2)

where $\gamma$ is the SNR and $\mathrm{BE}{R}^{\mathrm{tar}}$ is the target bit-error rate.

In equation (1), the utility function of the base station is not related to the spectrum demand of the WSN. For different networks, we would certainly hope that the purchased bandwidth changes based on network demands. Therefore, the utility function should consider the negative utility caused by the difference between spectrum supply and demand as follows

$$\begin{array}{l}U(b)={\displaystyle \sum _{i=1}^M{\omega }_i{b}_i{k}_i^{\left(s\right)}}-\frac{1}{2}\left({\displaystyle \sum _{i=1}^M{b}_i^2}+2\nu {\displaystyle \sum _{i\ne j}{b}_i{b}_j}\right)\\ -{\displaystyle \sum _{i=1}^M{P}_i}{b}_i-\theta {\left({\displaystyle \sum _{i=1}^M{b}_i}-D\right)}^2\end{array}$$ (3)

where $\theta$ denotes a coefficient of negative utility when the purchased spectrum does not properly meet the demand of the network, and $D$ is the overall spectrum demand of the WSN. This approach works because the utility function in equation (3) satisfies the conditions in Niyato and Hossain. ²¹ When $d_j$ is the spectrum demand of cluster $j$ , it can be presented as follows

$$d_j={\mathrm{\Lambda }}_j\times \mathrm{\Theta }\times e^{{\lambda }_j/2}$$ (4)

where ${\mathrm{\Lambda }}_j$ is the number of nodes in cluster $j$ , $\mathrm{\Theta }$ is the spectrum demand of one node, and ${\lambda }_j$ is the urgency coefficient of cluster $j$ . Hence, the value of $D$ can be obtained as shown below

$$D=\sum _{j=1}^N{d}_j$$ (5)

The purchased spectrum size at which the base station obtains the maximal profit can be calculated using $\partial U(b)/\partial b_i=0$ as follows

$$b_i=\frac{\left({\omega }_i{k}_i^{\left(s\right)}-P_i\right)\left(\nu \left(M-2\right)+1\right)-\nu {\displaystyle \sum _{j\ne i}\left({\omega }_j{k}_j^{\left(s\right)}-P_j\right)}+2\theta \left(1-\nu \right)D}{\left(1-\nu +\nu M+2\theta M\right)\left(1-\nu \right)}$$ (6)

From equation (6), the conclusion can be drawn that $b_i$ has a linear positive relationship with $D$ . If the $b_i$ in equation (6) is rewritten as $b_i=Q_1(P_{-i})-Q_2{P}_i$ , where $Q_1(P_{-i})$ and $Q_2$ are constants when all $P_j$ are given for $j\ne i$ , $Q_1(P_{-i})$ and $Q_2$ can be expressed as follows

$$Q_1\left(P_{-i}\right)=\frac{{\omega }_i{k}_i^{\left(s\right)}(\nu (M-2)+1)-\nu \sum _{j\ne i}({\omega }_j{k}_j^{\left(s\right)}-P_j)+2\theta (1-\nu )D}{(1-\nu +\nu M+2\theta M)(1-\nu )}$$ (7)

$$Q_2=\frac{(\nu (M-2)+1)}{(1-\nu +\nu M+2\theta M)(1-\nu )}$$ (8)

Profit function of primary users

The profit acquired by primary user $i$ consists of three parts: the revenue from leasing spectrum to the secondary users, the revenue from $F_i$ gained from providing service to the ongoing primary connections, and the cost related to the QoS degradation of the primary users. Thus, the profit function of primary user $i$ is

$${\mathrm{\Pi }}_i\left(P\right)=P_i{b}_i+c_1{M}_i-c_2{M}_i{(B_i^{\mathrm{req}}-k_i^{\left(p\right)}\frac{W_i-b_i}{M_i})}^2$$ (9)

where $P$ is a set composed of the spectrum prices of all the primary users (i.e. $P=\{P_1,...P_i,...P_M\}$ ); $M_i$ is the number of ongoing primary connections; $c_1$ and $c_2$ are constants denoting the weights for revenue and the cost function, respectively; $B_i^{\mathrm{req}}$ is the spectrum demand of an ongoing primary connection; $W_i$ is the bandwidth of primary user $i$ ; and $k_i^{\left(p\right)}$ is the spectral efficiency of wireless communication for primary user $i$ , which can be expressed by

$$k_i^{\left(p\right)}=\frac{B_i^{\mathrm{req}}}{W_i/M_i}$$ (10)

If $b_i$ is replaced by $b_i=Q_1(P_{-i})-Q_2{P}_i$ , equation (9) can be rewritten as

$$\begin{array}{l}{\mathrm{\Pi }}_i\left(P\right)=P_i\left(Q_1\left(P_{-i}\right)-Q_2{P}_i\right)+c_1{M}_i-c_2{M}_i\\ {\left(B_i^{req}-k_i^{\left(p\right)}\frac{W_i-\left(Q_1\left(P_{-i}\right)-Q_2{P}_i\right)}{M_i}\right)}^2\end{array}$$ (11)

Bertrand game mode

The Bertrand game is used to model the process of spectrum pricing; an analysis is given below:

• Players: M primary users;

• Strategy: variable $P_i$ , $i\in \{1,2,\dots ,M\}$ ;

• Payoff: $\mathrm{\Pi }(P)$ , $i\in \{1,2,\dots ,M\}$ .

In Namvar and Afghah, ¹⁷ the existence of a single game solution (i.e. the NE) has been proved; therefore, there is no need to restate it here. To find NE, the best response (BR) of primary user $i$ is calculated as follows

$$\mathrm{BR}\left(P_{-i}\right)=\arg \underset{P_i}{max}\left({\mathrm{\Pi }}_i\left(P\right)\right)=\arg \underset{P_i}{max}\left({\mathrm{\Pi }}_i(P_i\cup P_{-i})\right)$$ (12)

where $P_{-i}$ is the subset of $P$ that does not include $P_i$ . Under the premise that $P_{-i}^{*}$ denotes the BR set for all primary users except primary user $i$ if and only if ${P_i}^{*}=\mathrm{BR}({P_{-i}}^{*})$ , then NE is $P^{*}=\{P_1^{*},\dots ,P_i^{*},\dots ,P_M^{*}\}$ . Using $\partial {\mathrm{\Pi }}_i(P)/\partial P_i=0$ , we obtain the following equation

$$\begin{array}{l}2c_2{k}_i^{\left(p\right)}{Q}_2\left(B_i^{req}-k_i^{\left(p\right)}\frac{W_i-\left(Q_1\left(P_{-i}\right)-Q_2{P}_i\right)}{M_i}\right)\\ +Q_1\left(P_{-i}\right)-2Q_2{P}_i=0\end{array}$$ (13)

For all $i\in \{1,2,...,M\}$ , we can obtain M equations similar to equation (13). When all the parameters in equation (13) are available for each $i$ , we can obtain $P^{*}$ (i.e. NE). Furthermore, given $P^{*}$ , $b$ can be easily solved.

However, the $P^{*}$ obtained by the above means is only an individual optimal solution, not the global optimal solution. Pareto optimization, which is significant in game theory, is a good way to find the global optimal solution. Here, we recalculate BR as follows

$$BR\left(P_{-i}\right)=\arg \underset{P_i}{\max }\left({\displaystyle \sum _{i=1}^M{\mathrm{\Pi }}_i\left(P\right)}\right)=\arg \underset{P_i}{\max }\left({\displaystyle \sum _{i=1}^M{\mathrm{\Pi }}_i\left(P_i\cup P_{-i}\right)}\right)$$ (14)

Similarly, using $\partial \sum _{i=1}^M{\mathrm{\Pi }}_i\left(P\right)/\partial P_i=0$ , ${P_{\mathrm{opt}}}^{*}$ , which represents the global optimum for all primary users, is obtained.

Spectrum allocation model

M spectra with varied channel qualities and different widths are assigned to N clusters while ensuring that the cluster with the highest urgency is preferentially satisfied. First, the differences in channel quality are presented in the form of bandwidth; the equivalent bandwidth of each spectrum is calculated as follows

$$c_i=b_i{k}_i^{\left(s\right)}/k_{\mathrm{tar}}^{\left(s\right)}$$ (15)

where $k_{\mathrm{tar}}^{\left(s\right)}$ is the spectral efficiency corresponding to $\gamma =9\mathrm{dB}$ . Each cluster will have a value related to the number of nodes and the urgency coefficient of that cluster. In this article, the value of cluster $j$ is notated as

$$V_j={\mathrm{\Lambda }}_j\times \mathrm{\Theta }\times e^{{\sigma }_j/4}+max\left(\mathrm{\Lambda }\right)\times {\lambda }_j$$ (16)

where $max(\mathrm{\Lambda })$ is the maximum of all $\mathrm{\Lambda }$ , ${\sigma }_j$ is the number of periods waiting for communication, and ${\sigma }_j$ is determined by

$${\sigma }_j=\{\begin{array}{cc}{\sigma }_j+1\hfill & \mathrm{if}\mathrm{cluster}j\mathrm{get}\mathrm{spectrum}\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$ (17)

The MKP is formulated as follows

$$\begin{array}{c}max\sum _{i=1}^M\sum _{j=1}^N{V}_j{x}_{\mathrm{ij}}\hfill \\ \mathrm{subject}\mathrm{to}\sum _{j=1}^N{d}_j{x}_{\mathrm{ij}}\le c_i,i=1,\dots ,M\hfill \\ \sum _{i=1}^M{x}_{\mathrm{ij}}\le 1,j=1,\dots ,N\hfill \\ x_{\mathrm{ij}}\in \{0,1\},i=1,\dots ,M;j=1,\dots ,N\hfill \end{array}$$ (18)

Then, $x_{\mathrm{ij}}=1$ if cluster $j$ is allocated the spectrum from $F_i$ ; otherwise, $x_{\mathrm{ij}}=0$ . To avoid extreme cases, we assume that for $\forall j$ , $\exists i$ , let $d_j\le c_i$ , and for $\forall i$ , $\exists j$ , let $d_j\le c_i\le \sum _{j=1}^N{d}_j$ .

However, MKP is a typical NP-hard problem. When either the number of knapsacks or the number of items is relatively large, it is difficult to find the optimal MKP solution. Nevertheless, using an optimization algorithm, an approximately optimal solution is easy to obtain. In this article, we adopt the ACO algorithm, which has been shown to be efficient. Ants consider each cluster as an intersection that have (M + 1) directions; therefore, there are N intersections. Whenever ants pass through an intersection, they choose a path from among the M primary users and user 0 (where path 0 does not choose any primary user) based on a probability that is in a direct ratio to $V$ .When an ant completes an entire journey, it saves the path and the value $v\_\mathrm{ant}$ of this path. At the same time, it locally updates the amount of pheromone $\tau$ for that path according to the following rule

$${\tau }_{\mathrm{ij}}(t+1)=(1-\rho )·{\tau }_{\mathrm{ij}}\left(t\right)+\rho ·v\_\mathrm{ant}/\sum _{j=1}^N{V}_j$$ (19)

When all ants have completed their journeys, the $\tau$ values on the paths whose $v\_\mathrm{ant}$ values are among the five largest are updated as follows

$${\tau }_{\mathrm{ij}}(t+n)=(1-\rho )·{\tau }_{\mathrm{ij}}\left(t\right)+\rho ·v\_\mathrm{ant}/max(v\_\mathrm{ant})$$ (20)

where $\rho \in (0,1]$ is a parameter governing pheromone decay and $(1-\rho )$ can be interpreted as pheromone evaporation from a trail. Each iteration can output an optimal path and the global optimal path for all iterations. A schematic of ACO is shown in Figure 2.

Figure 2.

ACO-MKP algorithm model.

Here, $\tau$ is defined as a matrix, ${\tau }_{(M+1)\times N}$ , while $\tau (M+1,:)$ denotes the $\tau$ on path 0. The initial value of $\tau$ is $\tau =\left[\begin{array}{ccc}\frac{1}{M}\hfill & \cdots \hfill & \frac{1}{M}\hfill \\ \multicolumn{1}{c}{⋮}& \ddots \hfill & ⋮\hfill \\ \multicolumn{1}{c}{\frac{1}{M}}& \cdots \hfill & \frac{1}{M}\hfill \\ \multicolumn{1}{c}{1}& 1-\frac{j}{M}\hfill & \frac{1}{M}\hfill \end{array}\right]$ , which ensures that the initial clusters select path 0 with higher probability, and later clusters select path 0 with lower probability when they choose a path. The iteration process causes the probability of choosing path 0 to converge to a reasonable value if the precious choices of ants run out of bandwidth, forcing later ants to choose path 0. The lowercase $p$ (which differs from the price, $P$ ) denotes the probability of choosing one path, which is a 1×(M + 1) matrix that can be obtained as follows

$$p\left(i\right)={\tau }_{\mathrm{ij}}/\sum _{i=1}^{M+1}{\tau }_{\mathrm{ij}}$$ (21)

Here, $\mathrm{vd}$ denotes the value density of a cluster, which can be obtained by $v{d}_j=V_j/d_j$ , and $\mathrm{con}$ denotes the convergence of the ACO algorithm, which is 1 when the optimization is convergent; otherwise, it is 0. The pseudocode of the ant colony optimization–based multiple knapsack problem (ACO-MKP) algorithm is shown below.

ACO-MKP algorithm
1:	Input: vd , c , d , τ , loop, ant_num
2:	Function: ACO-MKP
3:	For i1 = 1 to loop
4:	For i2 = 1 to ant_num
5:	Sort the cluster by vd in descending order
6:	For i3 = 1 to N
7:	If( c (i)<  d (j))Then
8:	p(i)←0
9:	Else, compute the probability p according to equation (21)
10:	Ants choose the path l according to the p
11:	Compute the remaining c according to the l
12:	End For
13:	Compute the value v_ant of the path
14:	End For
15:	Update the τ on the path of each ant according to equation (19)
16:	Update the τ on the path whose v_ant is among the five largest according to equation (20)
17:	If(value< max(v_ant)) Then
18:	value←max(v_ant), temp←0list← l (corresponding to max(v_ant))
19:	Else if(value = max(v_ant)) Then
20:	temp←temp + 1
21:	Else, temp←0
22:	If(temp >10) Then
23	con←1, break
24:	Else, con←0
25:	End For Output: value, list
26:	End ACO-MKP

After the spectrum has been allocated through the ACO-MKP algorithm, the clusters can use the spectrum for their own nodes based on the timing sequence. For the other nodes waiting to transmit, their probabilities of obtaining bandwidth during the next period are increased by controlling the $\sigma$ until their spectrum demand is satisfied. Even though the total bandwidth is insufficient, using this approach, each cluster has a discrete opportunity to communicate. The cluster with the greatest urgency is given greater priority, while clusters with lower urgency and importance can also communicate within the time limit.

Performance evaluation

Parameter setting

We consider a network model with three primary users providing service for a WSN containing 15 clusters as secondary users (Figure 1). The total bandwidth available to each primary user is 30 MHz (i.e. $W_i=30$ ). The number of ongoing primary connections is set to $M_1=M_2=M_3$ . The bandwidth requirement of each primary user is 2 Mbps (i.e. $B_i^{\mathrm{req}}=2$ ), $c_1=2$ , and $c_2=2$ . The number of nodes in the fifteen clusters is $\mathrm{\Lambda }=\left[\begin{array}{ccccccccccccccc}18\hfill & 8\hfill & 9\hfill & 12\hfill & 14\hfill & 10\hfill & 17\hfill & 20\hfill & 16\hfill & 12\hfill & 14\hfill & 18\hfill & 22\hfill & 15\hfill & 8\hfill \end{array}\right]$ , and their corresponding urgency coefficients are $\lambda =\left[\begin{array}{ccccccccccccccc}0.3& 0.4& 0.2& 1& 0.6& 0.5& 0.3& 0.2& 0& 0.4& 0.1& 1& 0.6& 0.4& 0.3\end{array}\right]$ . The income from the per-transmission rate of secondary users is 8 (i.e. ${\omega }_i=8$ ), and the spectrum demand of one node is $\mathrm{\Theta }=0.1$ . The spectrum substitutability is $\nu =0.6$ , and the coefficient of negative utility is 0.1 (i.e. $\theta =0.1$ ). The target $\mathrm{BER}$ for the secondary users is $\mathrm{BE}{R}^{\mathrm{tar}}={10}^{-4}$ . The channel quality (i.e. $\mathrm{SNR}$ ) for the secondary users ranges from 9 to 22 dB; in this article, they are 18, 15, and 10 dB.

Numerical results

BR, NE, and the optimization process

For the Bertrand game with three primary users, the proof of its principle is similar to that of the game with two primary users. As shown in Figure 3, the BR of each primary user corresponding to other primary users is a complex three-dimensional (3D) surface rather than the simple two-dimensional (2D) curve resulting from the game model with two primary users. The three curved surfaces intersect at point (6.7, 5.7, 3.5); this is the NE and proves that the NE is unique.

Figure 3.

Best response function and NE.

At the NE, the spectrum prices demanded by the primary users are P = {6.7, 5.7, 3.5} and the sold bandwidth amounts are b = {7.0, 5.9, 3.6}. Furthermore, the utility value of the WSN is U(b) = 57.0, and the utility values of the primary users are π(P) = {70.3, 58.7, 40.9}. Using global optimization, the spectrum price at NE changes to P* = {9.2, 7.8, 5.2}, while the sold bandwidth becomes b* = {5.4, 5.1, 3.6}. The utility values of the WSN and the primary users are U*(b) = 23.2 and π*(P) = {76.2, 66.3, 47.3}, respectively. Through cooperation, the primary users’ utility values have been significantly increased at the expense of the network’s utility value. In economics, three primary users form a market monopoly, controlling the market supply of spectrum and the spectrum price. Therefore, the network should pay more for the same bandwidth, leading the utility value U(b) to decrease from 57.0 to 23.2.

Total profit

As shown in Figure 4, When P₂ and P₃ are kept constant in P and P* while P₁ gradually increases, the total profits corresponding to P and P* both increase as P₁ increases; however, after the total profit reaches a certain peak value, the total profit will be reduced for a reduced spectrum demand leading the secondary users to choose a less-expensive primary user. In addition, when P₁ reaches the NE, the total profit is the maximal value. The fact that the total profit obtained by P* is higher than that of P proves that optimizing the game does improve the total profit of the primary users.

Figure 4.

Total profit when $P_1$ in P and $P^{*}$ is changed.

ACO-MKP algorithm and genetic algorithm–based MKP algorithm during one period

When the purchased bandwidth of WSN is b = {5.4, 5.1, 3.6}, the ACO-MKP algorithm uses ant colony optimization (ACO) to heuristically find the optimal allocation scheme. By influencing the pheromone, the ACO-MKP algorithm can converge to an optimal scheme after repeated iterations. As a comparison, the genetic algorithm–based MKP (GA-MKP) in Unal ²⁸ is taken into consideration.

Figure 5 shows that after 23 iterations, the ACO-MKP algorithm whose time and space complexity are O(N) and O(150 × N) has converged to the clustering scheme (list = [1, 1, 1, 3, 3, 2, 1, 0, 0, 2, 0, 2, 0, 1, 2]), whose value is 26. In other words, b₁ supplies spectrum to clusters 1, 2, 3, 7 and 14 and b₂ meets the spectrum demand of clusters 6, 10, 12, and 15, b₃ is allocated to clusters 4 and 5, and the remaining clusters (8, 9, 11, and 13) must wait to communicate until additional spectrum is purchased and allocated. The remaining bandwidth is b_remain = {0.1, 0.2, 0}. However, to converge to an approximate iteration, the time and space complexity of GA-MKP algorithm are O(2 N) and O(500 × 2 N) (the length of each chromosome is 2N). It obtains list = [2, 1, 0, 3, 3, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2], whose value is only 24.6, and the remaining bandwidth is b_remain = {0.4984, 0.1793, 0.0209}. Compared to the GA-MKP algorithm, the ACO-MKP algorithm uses less time and increases the value to 1.4, which is equivalent to providing bandwidth for an additional 14 nodes. The ACO-MKP algorithm, which outperforms GA-MKP, can improve the utilization rate of the purchased bandwidth.

Figure 5.

ACO-MKP and GA-MKP algorithm during one period.

ACO-MKP algorithm and GA-MKP algorithm over 30 periods

We executed both algorithms for 30 periods under the premise of b = {5.4, 5.1, 3.6}; Figure 6 describes each cluster’s degree of spectrum demand satisfaction. When all clusters are sorted by vd in descending order, the satisfaction degree of the two algorithms shows a decreasing trend. This trend occurs because the clusters with higher vd values generally have greater urgency or are more valuable; clusters with lower vd values often do not have sufficient urgency to require immediate communications. Therefore, two algorithms, which both allocate spectrum dynamically, cause low-urgency clusters to fail to communicate over more periods.

Figure 6.

ACO-MKP and GA-MKP algorithm over 30 periods.

For those clusters with high vd, the satisfaction degrees of the ACO-MKP algorithm are obviously higher than the GA-MKP algorithm, while for those cluster with low vd, the contrary happens. This is caused by the characteristic of each algorithm. The ACO finds the best solution by affect the pheromone, which not only iteratively screens out those optimal solutions, but focuses on those clusters with high vd. The GA iteratively optimizes the population and selects those better chromosomes to obtain the optimal solution, which cannot take the difference of each gene into consideration. It is worth mentioning that because the urgency coefficients of clusters 4 and 12 are 1, the satisfaction degrees of ACO-MKP algorithms is 1. However, the urgency coefficient cluster 9 and 11 is the lowest; therefore, the satisfaction degrees of the two algorithms are both relatively low.

Through the ACO-MKP algorithm, the σ values of the majority clusters are 1 or 2 (GA-MKP are 3), and when the urgency coefficient is 1, the σ of that cluster is 0 (that is, that cluster is guaranteed to be allowed to communicate in all periods). The maximal σ of all clusters is 3, which fulfills the application requirement. About GA-MKP algorithm, Figure 6 shows that it cannot guarantee the transmission to the cluster, whose urgency coefficient is 1. And its maximal σ of all clusters is higher (5 or higher, that depends). Therefore, ACO-MKP is a better way to solve the spectrum allocation in the WSN.

The remaining b

Figure 7 shows that the remaining b₁, b₂, and b₃ in the ACO-MKP algorithm are generally lower than 0.2, which can be ignored, while in the GA-MKP algorithm, the remaining b₃ is generally higher than 0.4, and in some cases, the maximum value reaches 1.3. It is inefficient when the remaining b of the GA-MKP algorithm is high enough to meet substantial node demand. Finally, the ACO-MKP algorithm allows the utilization rate of b to reach 0.9576, while for the GA-MKP algorithm, it reaches only 0.9012. This result also indicates that the ACO-MKP algorithm performs better in many aspects than does the GA-MKP algorithm. The proposed ACO-MKP algorithm can outperform GA-MKP algorithm in terms of the spectrum utilization rate.

Figure 7.

The remaining b of the ACO-MKP and GA-MKP algorithm.

Conclusion and future work

Employing game theory and cognitive radio technology in a spectrum sharing model for WSNs finds a solution that simultaneously achieves the maximum utility for both primary and secondary users. Figure 3 confirms that this unique point of equilibrium indeed exists. Through global optimization, Figure 4 shows that the optimized NE is selected even as the spectrum price rises and the total utility of primary users increases, while Figures 6 and 7 show that—compared to the GA-MKP algorithm—the ACO-MKP algorithm increases the bandwidth utilization rate by 5.9%. Overall, this article achieves the multi-seller and multi-buyer spectrum sharing model in WSN by combining the Bertrand game with the ACO-MKP algorithm.

Even though this study realized the spectrum sharing model in WSN, the Bertrand game was simulated in a simplistic fashion. In addition, approaching the problem from the standpoint that the difference in channel quality is equivalent to bandwidth is controversial. Moreover, in this article, the urgency coefficient refers specifically to a static urgency coefficient, while in real-world situations, a dynamic urgency coefficient would be more applicable and will be considered in future work.