# A Hybrid Spectrum Combinational Auction Mechanism Based on a Weighted Bipartite Graph for Energy Internet in Smart Cities

Authors: Huibin Feng; Zhaocai Yu; Jian Guan; Geng Lin
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Energy Internet (EI) is aimed at sustainable computing by integrating various energy forms into a highly flexible grid similar to the Internet. The network subsystems of EI connect different components to enable real-time monitoring, controlling, and management. In this paper, the spectrum allocation problem of the cognitive radio network for EI in a smart city is investigated. The network spectrum allocation with both heterogeneous primary operators and secondary users is formulated as the combinatorial auction problem and then is converted to a subset selection problem on a weighted bipartite graph. We propose a hybrid algorithm to solve the problem. Firstly, the proposed algorithm uses a constructive procedure based on the Kuhn-Munkres algorithm to obtain an initial solution. Then, a local search is used to improve the solution quality. In addition, the truthfulness of the auction is guaranteed by adopting a “Vickrey-like” mechanism. Simulation results show that the performance of the proposed algorithm is better than existing greedy algorithms in terms of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio.


---

## Body

## 1. Introduction

The smart city is an innovation of the physical city with high integration of advanced monitoring, sensing, communication, and control technologies aimed at providing real-time, interactive, and intelligent urbanization services to end users [1]. To realize the smart city, Energy Internet is one of the key technologies. Energy Internet (EI) is aimed at sustainable computing by integrating various energy forms into a highly flexible grid similar to the Internet in the smart city [2]. A typical EI system for a smart city consists of three subsystems: energy subsystem, information subsystem, and network subsystem [3]. The network subsystems connect different devices of EI to enable real-time monitoring, controlling, and management [4, 5]. The devices in the network subsystem use wired or wireless technologies to establish direct transmission links between devices, such as D2D communication, WiMAX, cognitive radio (CR) network, and cellular network [6, 7]. These communication technologies are combined in EI to implement real-time monitoring of devices in a smart city [8, 9]. To improve the reliability and efficiency of device information communications in a smart city, the cognitive radio network spectrum allocation technology is required. Cognitive radio [10] technology has been introduced to increase transmission availability and efficiency. In a cognitive radio network, the secondary user can dynamically access the spectrum bands when the licensed primary users are not occupied according to the dynamic spectrum access technology. The dynamic spectrum access technology makes the primary wireless service providers not only satisfy their own spectrum requirement but also obtain additional profit by offering a free spectrum to the other secondary users. So it is vital to design a mechanism to encourage the primary spectrum operators to permit the secondary users to access the idle primary operators’ spectrum band and to enhance the spectrum availability and efficiency. While dynamic spectrum access is attractive, how to allocate the spectrum across multiple primary operators and secondary users is still an important open issue. The fact of the matter is to construct a mechanism that can effectively allocate the spectrum. There are many works that had been done about the dynamic spectrum allocation for the cognitive radio network with many tools such as game theory [11, 12] and contract theory [13]. Different from [12, 13], the dynamic spectrum access on auction is more suitable because of its economic incentive and joint consideration about the quality of service and statistical reference in the network. To achieve the economic incentive for the spectrum auction, the truthfulness, revenue, and utilization must be guaranteed. The truthfulness can make the bidders in the auction not benefit from their untrue valuation for the spectrum opportunity, the revenue can make the total amount of payment from all winning buyers in the auction maximized, and the utilization can make as many buyers as possible to reuse the spectrum. So the auction has been widely applied to the spectrum market.In general, the spectrum auction mechanism includes online auction and periodical auction. The online auction is developed based on short intervals in the time domain and small areas in the space domain, while in the periodical auction, the spectrum is sold periodically by the primary operator and the intervals are relatively long. For the periodical auction, in [14], Gandhi et al. proposed a general centralized periodical auction framework for spectrum allocation in the cognitive radio network. In [15], the spectrum opportunity in a time-frequency division manner and the spectrum allocation mechanism on combinatorial auction are proposed. As for the online auction, Tehrani and Uysal proposed an auction-based spectrum trading method to maximize the total satisfaction of the secondary users and revenue of the wireless service provider in [16]. In [17], Yi et al. proposed an online spectrum auction framework for the cognitive radio network which considered the uncertain activities of primary users. To further improve the spatial reusability of the spectrum, Wang et al. proposed an online auction framework using a mixed graph for licensed shared access systems in [18]. Different from [18], group buying strategy is used to design the spectrum auctions to increase the buying power of small network providers in [19]. Considering the channels are heterogeneous, Khairulla and Chatterjee proposed an auction-based allocation algorithm in a distributed multichannel cognitive radio network in [20]. To satisfy the quality of service of user equipment in the specific network, Shen et al. proposed a spectrum sharing framework for the hybrid access in the two-tier macro-femtocell networks in [21]. Secondary spectrum auction taking communication constraints into account is studied in [22]. Yi and Cai introduced another spectrum auction framework among heterogeneous secondary users with various quality of service requirements for recall-based cognitive radio networks in [23].To improve the fairness and efficiency of the online auction, another research topic for spectrum sharing is the double auction. Compared with the single auction on spectrum allocation, the double auction is more fair and effective because both buyers and sellers can submit bids to the central auctioneer. In [24], a truthful multichannel spectrum double auction framework is proposed. Considering the shared spectrum consists of a wide range of frequencies, a truthful double auction framework for a heterogeneous spectrum named TAMES is proposed in [25]. Assuming without the valuation distribution knowledge, a framework for spectrum double auction which jointly considers spectrum reusability, truthfulness, and profit maximization is designed in [26]. To ensure strategy-proof auction, Sun et al. proposed a multiunit double auction approach that guarantees the competitive fairness among buyers while remaining strategy-proof for spectrum allocation in [27]. Another spectrum allocation on double auction for explicitly decoupling the buyer-side and seller-side auction while achieving truthfulness, individual rationality, and budget balance is investigated in [28].For both online auctions mentioned above, none of them takes both multiple multichannel primary operators and secondary users existing in the cognitive radio network into account. In [29], Zhou et al. firstly proposed a spectrum allocation framework on combinatorial auction and an approximation algorithm is presented. Another spectrum combinatorial auction framework for the scenario that each primary user has multiple channels to sell and each secondary user demands multiple channels is proposed in [30]. Assuming primary users possess heterogeneity and secondary users may request different types of spectrum bands, a spectrum combinatorial double auction and corresponding greedy allocation algorithm are proposed in [31].Spectrum allocation for the cognitive radio network on both multiple multichannel primary users and secondary users is mostly based on combinatorial auction, because the combinatorial auction problem is NP-hard; most studies in the literature model the combinatorial auction as a multiple multidimensional knapsack problem or integer program problem, then use greedy algorithms to solve the problem and derive an approximate solution, but the quality of the solution is not good enough. In this paper, we focus on the spectrum auction problem with multiple heterogeneous primary operators and multiple secondary users in a smart city. Each primary operator in a smart city has multiple channels, and the channels have different widths (e.g., the channel width for a TV broadcast network is 6 MHz, and the channel width of a global system for mobile communications is 200 kHz). The secondary user in a smart city can dynamically access the different primary operators according to cognitive radio technology [32]. We also assume that each secondary user in a smart city has a different spectrum requirement, and it must request different channel numbers from multiple primary operators. So the spectrum allocation in a smart city can be formulated as a combinatorial auction problem because the secondary user bids a bundle of channels. To make the auction mechanism work efficiently, we firstly model the spectrum combinational auction problem in a smart city as a subset selection problem on the weighted bipartite graph; then, we design a hybrid algorithm which can run in a hybrid manner with high efficiency. Simulation results and comparison show that the efficiency of the proposed auction mechanism can be enhanced.The key contributions of this paper can be summarized as follows:(i)
We consider the spectrum allocation problem of the cognitive radio network for EI in a smart city. The spectrum combinational auction problem of the cognitive radio network with multiple heterogeneous primary operators and multiple secondary users is converted to a subset selection problem on a weighted bipartite graph(ii)
We design a constructive procedure, which iteratively uses the Kuhn-Munkres (KM) algorithm [33, 34], to generate an initial solution. Then, a swap procedure and an interchange procedure are applied to improve the solution quality(iii)
We design extensive experiments to verify the performance of the proposed auction mechanism. Social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio have been carefully investigated. Simulation results show that the proposed algorithm can obtain higher allocation performance and efficiency for the cognitive radio network of EI in a smart cityThe remainder of this paper is organized as follows. Section2 formulates the spectrum allocation model and describes the framework with multiple heterogeneous primary operators and multiple secondary users in a smart city. Section 3 presents a hybrid spectrum allocation algorithm on a weighted bipartite graph model to obtain a good-quality allocation scheme. Section 4 gives the simulation results and comparisons. The concluding remarks are made in Section 5.


## 2. System Model

### 2.1. System Model

In this section, the spectrum allocation model and framework for the cognitive radio network for EI in a smart city are described in Figure1. We consider a cognitive radio network of EI in a smart city [35] with n secondary users (such as the neighborhood area network gateway) and m primary operators. We also assume that the primary operators have a different number of channels, and the channel width of the primary operators is different. To share the spectrum between the primary operators and the secondary users, we assume that there exists a centralized control center that acts as the spectrum auctioneer which manages the spectrum allocation. In the auction, the primary operators act as the seller and the secondary users act as buyers; we also assume that the auctioneer is a nonprofit body which runs the auction, determines the winners, and allocates the spectrum to the secondary user.Figure 1
Cognitive radio network of EI in a smart city.Each primary operator owns a spectrum which serves its licensed users. When the spectrum is idle at a time, the primary operator would like to allow the secondary user to access the idle spectrum to earn extra profits. We assume that the auction is an online auction-based short interval in the time domain. Because the auctioned spectrum bandwidth of the primary operator is different, without loss of generality, we further assume that each primary operator’s ideal spectrum band is divided into a series of channels with identical channel bandwidth; thus, the number of channels may be different for each primary operator in terms of the different channel bandwidths, for example, 6 MHz for a TV band and 200 kHz for a global system band for mobile communication.Assume that the secondary users in the system can request and obtain multiple channels from different primary users to satisfy their own bandwidth demand, but it is difficult for the secondary users to use multiple discontinuous spectrum bands from different primary operators; we assume that each secondary user can only access the spectrum band for the same primary operator. All secondary users in the system are not interfere-free because within the same communication range, one channel can only be accessed by secondary users at some specific time.In order to describe the formulation and our spectrum combinational auction mechanism clearly, some notations are introduced. LetM=1,2,⋯,m be the set of the primary operators and ci∈ℤ+ denote the number of channels owned by the ith primary operator, where i=1,2,⋯,m. Then, the set of primary operators in the auction channel in terms of quantity can be denoted asC=c1,c2,⋯,ci,⋯,cm. Let bi∈ℤ+ be the channel’s bandwidth of the ith primary operator. The vector B=b1,b2,⋯,bi,⋯,bm represents the set of primary operators of the channel bandwidth.LetN=1,2,⋯,n be the set of secondary users; each secondary user has a spectrum bandwidth demand to satisfy its own quality of service. Let dj>0 be the specific spectrum demand of the jth secondary user. The secondary user’s valuation of its own spectrum demand is denoted as vj; we also denote the vj=dj×log1+γj, where the γj denotes the signal-to-noise ratio of the jth secondary user, and we also assume that it is a constant during the auction interval. Letpj>0be the bid price the secondary user is willing to pay for using the spectrum demanddj; thus, the bid price vector of the secondary user can be denoted as P=p1,p2,⋯,pj,⋯,pn. We assume that the auction is the truthful auction; then, the bidding price is equal to the valuation price of the secondary user, i.e., pj=vj.For the reason that each secondary user can bid a bundle of channels for different primary operators, we can formulate the spectrum allocation as a combinational auction model. For each round of the auction, the auctioneer collects each primary operator channel number and channel bandwidth; it also collects each secondary user’s private spectrum bandwidth demand and bid price. Then, the auctioneer determines the optimal spectrum allocation according to these sealed bid information.


### 2.2. Problem Formulation

We assume that the primary operators and secondary users in the network subsystem can exchange the information with the auctioneer. After receiving the primary operator-submitted information, the auctioneer generates the channel bandwidth vectorB, the channel quantity C of the primary operators, the specific spectrum demand vector D=d1,⋯,dm, and the bid price vector P.Basing on the above bid information, the auctioneer executes the winner determination algorithm to maximize the utility of the seller, and thus, the allocation matrix can be achieved. The allocation matrix can be denoted byXnm.The element in the allocation matrix can be denoted byxij and can be defined as follows:
(1)xij=1,ifprimaryoperatoriallocatesthespectrumchunktosecondaryuserj,0,otherwise.Since each secondary user can only acquire the specific spectrum demand from no more than one primary operator, the spectrum allocation constrained equation of thejth secondary user can be written as follows:
(2)∑i=1mxij≤1.Similarly, the primary operator spectrum is limited; thus, the requested spectrum chunk of all the secondary users cannot exceed the bandwidth the primary operator owns. So the spectrum bandwidth constraint of theith primary operator can be written as follows:
(3)∑j=1nxijdj≤cibi.The objective of the spectrum combinational auction is to determine an optimal allocation matrix so that the social welfare is maximized. We can model the above problem as an optimization problem as follows:(4)maxz=∑i=1m∑j=1nxijpj.The optimization problem with spectrum constrain condition must satisfy equations (1)–(3), and the optimization problem is known to be NP-hard [36].


### 2.3. Spectrum Auction Model on a Weighted Bipartite Graph

Due to the high complexity of solving the optimization problem, we propose a heuristic method to find good-quality allocation schemes. Existing greedy algorithms used the individual information to allocate the spectrum. In order to consider all information simultaneously, we use the weighted bipartite graph to model the considered spectrum combinational auction problem in a smart city.LetG=V,E be an undirected weighted bipartite graph, where V is the vertex set and E is the edge set. The vertex set consists of two disjoint subsets N and M. Each vertex in the set N represents a secondary user, and each vertex in the set M represents a primary operator. Each edge in the edge set is denoted by eij, where i∈N and j∈M; the edge eij exists only if the vertex i∈N and the vertex j∈M satisfy the following equation:
(5)dj≤cibi.If there exists an edgeeij between the primary operator i and the secondary user j, the weight of eij is set as the secondary user’s bid price pj. So we have
(6)wij=pj,ifprimaryoperatoriconnectstosecondaryuserjwithoneedge,0,otherwise.Based on the above definition, we convert the spectrum combinatorial auction model to a weighted bipartite graph. The vertices of the graph are the primary operator and secondary user in the network. The edges between the primary operators and the secondary users exist only if the primary operators, which can satisfy the corresponding secondary user’s spectrum requirement, and the edges are constructed according to equation (5). The weights of the edges are set according to equation (6).In fact, an edge subsetT∈E represents a spectrum allocation scheme. If an edge eij is selected in T, it means that primary operator i allocates the spectrum chunk to secondary user j. Otherwise, primary operator i does not allocate the spectrum chunk to secondary user j. An edge set T is called feasible if its corresponding spectrum allocation scheme satisfies equations (2) and (3).The objective of the spectrum allocation is to maximize the social welfare for allocating the spectrum to the secondary user. Maximizing the social welfare of the auction can be converted to finding a feasible edge set, such that the sum of the weights of the selected edges is maximized.


## 2.1. System Model

In this section, the spectrum allocation model and framework for the cognitive radio network for EI in a smart city are described in Figure1. We consider a cognitive radio network of EI in a smart city [35] with n secondary users (such as the neighborhood area network gateway) and m primary operators. We also assume that the primary operators have a different number of channels, and the channel width of the primary operators is different. To share the spectrum between the primary operators and the secondary users, we assume that there exists a centralized control center that acts as the spectrum auctioneer which manages the spectrum allocation. In the auction, the primary operators act as the seller and the secondary users act as buyers; we also assume that the auctioneer is a nonprofit body which runs the auction, determines the winners, and allocates the spectrum to the secondary user.Figure 1
Cognitive radio network of EI in a smart city.Each primary operator owns a spectrum which serves its licensed users. When the spectrum is idle at a time, the primary operator would like to allow the secondary user to access the idle spectrum to earn extra profits. We assume that the auction is an online auction-based short interval in the time domain. Because the auctioned spectrum bandwidth of the primary operator is different, without loss of generality, we further assume that each primary operator’s ideal spectrum band is divided into a series of channels with identical channel bandwidth; thus, the number of channels may be different for each primary operator in terms of the different channel bandwidths, for example, 6 MHz for a TV band and 200 kHz for a global system band for mobile communication.Assume that the secondary users in the system can request and obtain multiple channels from different primary users to satisfy their own bandwidth demand, but it is difficult for the secondary users to use multiple discontinuous spectrum bands from different primary operators; we assume that each secondary user can only access the spectrum band for the same primary operator. All secondary users in the system are not interfere-free because within the same communication range, one channel can only be accessed by secondary users at some specific time.In order to describe the formulation and our spectrum combinational auction mechanism clearly, some notations are introduced. LetM=1,2,⋯,m be the set of the primary operators and ci∈ℤ+ denote the number of channels owned by the ith primary operator, where i=1,2,⋯,m. Then, the set of primary operators in the auction channel in terms of quantity can be denoted asC=c1,c2,⋯,ci,⋯,cm. Let bi∈ℤ+ be the channel’s bandwidth of the ith primary operator. The vector B=b1,b2,⋯,bi,⋯,bm represents the set of primary operators of the channel bandwidth.LetN=1,2,⋯,n be the set of secondary users; each secondary user has a spectrum bandwidth demand to satisfy its own quality of service. Let dj>0 be the specific spectrum demand of the jth secondary user. The secondary user’s valuation of its own spectrum demand is denoted as vj; we also denote the vj=dj×log1+γj, where the γj denotes the signal-to-noise ratio of the jth secondary user, and we also assume that it is a constant during the auction interval. Letpj>0be the bid price the secondary user is willing to pay for using the spectrum demanddj; thus, the bid price vector of the secondary user can be denoted as P=p1,p2,⋯,pj,⋯,pn. We assume that the auction is the truthful auction; then, the bidding price is equal to the valuation price of the secondary user, i.e., pj=vj.For the reason that each secondary user can bid a bundle of channels for different primary operators, we can formulate the spectrum allocation as a combinational auction model. For each round of the auction, the auctioneer collects each primary operator channel number and channel bandwidth; it also collects each secondary user’s private spectrum bandwidth demand and bid price. Then, the auctioneer determines the optimal spectrum allocation according to these sealed bid information.


## 2.2. Problem Formulation

We assume that the primary operators and secondary users in the network subsystem can exchange the information with the auctioneer. After receiving the primary operator-submitted information, the auctioneer generates the channel bandwidth vectorB, the channel quantity C of the primary operators, the specific spectrum demand vector D=d1,⋯,dm, and the bid price vector P.Basing on the above bid information, the auctioneer executes the winner determination algorithm to maximize the utility of the seller, and thus, the allocation matrix can be achieved. The allocation matrix can be denoted byXnm.The element in the allocation matrix can be denoted byxij and can be defined as follows:
(1)xij=1,ifprimaryoperatoriallocatesthespectrumchunktosecondaryuserj,0,otherwise.Since each secondary user can only acquire the specific spectrum demand from no more than one primary operator, the spectrum allocation constrained equation of thejth secondary user can be written as follows:
(2)∑i=1mxij≤1.Similarly, the primary operator spectrum is limited; thus, the requested spectrum chunk of all the secondary users cannot exceed the bandwidth the primary operator owns. So the spectrum bandwidth constraint of theith primary operator can be written as follows:
(3)∑j=1nxijdj≤cibi.The objective of the spectrum combinational auction is to determine an optimal allocation matrix so that the social welfare is maximized. We can model the above problem as an optimization problem as follows:(4)maxz=∑i=1m∑j=1nxijpj.The optimization problem with spectrum constrain condition must satisfy equations (1)–(3), and the optimization problem is known to be NP-hard [36].


## 2.3. Spectrum Auction Model on a Weighted Bipartite Graph

Due to the high complexity of solving the optimization problem, we propose a heuristic method to find good-quality allocation schemes. Existing greedy algorithms used the individual information to allocate the spectrum. In order to consider all information simultaneously, we use the weighted bipartite graph to model the considered spectrum combinational auction problem in a smart city.LetG=V,E be an undirected weighted bipartite graph, where V is the vertex set and E is the edge set. The vertex set consists of two disjoint subsets N and M. Each vertex in the set N represents a secondary user, and each vertex in the set M represents a primary operator. Each edge in the edge set is denoted by eij, where i∈N and j∈M; the edge eij exists only if the vertex i∈N and the vertex j∈M satisfy the following equation:
(5)dj≤cibi.If there exists an edgeeij between the primary operator i and the secondary user j, the weight of eij is set as the secondary user’s bid price pj. So we have
(6)wij=pj,ifprimaryoperatoriconnectstosecondaryuserjwithoneedge,0,otherwise.Based on the above definition, we convert the spectrum combinatorial auction model to a weighted bipartite graph. The vertices of the graph are the primary operator and secondary user in the network. The edges between the primary operators and the secondary users exist only if the primary operators, which can satisfy the corresponding secondary user’s spectrum requirement, and the edges are constructed according to equation (5). The weights of the edges are set according to equation (6).In fact, an edge subsetT∈E represents a spectrum allocation scheme. If an edge eij is selected in T, it means that primary operator i allocates the spectrum chunk to secondary user j. Otherwise, primary operator i does not allocate the spectrum chunk to secondary user j. An edge set T is called feasible if its corresponding spectrum allocation scheme satisfies equations (2) and (3).The objective of the spectrum allocation is to maximize the social welfare for allocating the spectrum to the secondary user. Maximizing the social welfare of the auction can be converted to finding a feasible edge set, such that the sum of the weights of the selected edges is maximized.


## 3. Spectrum Allocation Mechanism on a Weighted Bipartite Graph

In this section, we propose a hybrid spectrum auction mechanism by finding a feasible edge set of the weighted bipartite graph. The hybrid spectrum auction mechanism consists of two phases. In the first phase, a constructive procedure based on the well-known Kuhn-Munkres (KM) algorithm [33, 34] is used to generate a feasible edge set (i.e., an initial spectrum allocation scheme). Then, the initial spectrum allocation scheme is further improved by the local search procedure in the second phase. In the following subsection, we will give the detailed descriptions of the constructive procedure based on KM and the local search procedure and analyze the computational complexity and the auction properties of the mechanism.


### 3.1. The Constructive Procedure Based on KM

The existing greedy algorithm [30] used the individual information to generate a spectrum allocation scheme. In each iteration, only one secondary user obtained the spectrum. In this work, our proposed constructive procedure applies the KM to achieve global optimization efficiently and generate an initial spectrum auction scheme. Different from existing greedy algorithms, in each iteration of our constructive procedure, several secondary users are simultaneously allocated by global consideration. It enhances the efficiency of the allocation.The pseudocode of the constructive procedure is given in Algorithm1. After receiving all channel information and bid information, the constructive procedure firstly constructs the weighted bipartite graph G=V,E, where V=M∪N. Note that the number of primary operators is usually smaller than the number of secondary users (i.e., m<n). In order to apply the KM, we add n−m virtual vertices to M for ensuring n=m. Meanwhile, we add edges between each virtual vertex and each vertex in N, and the weights of these adding edges are set to zero. The obtained graph is also denoted by G. Let T and SumW be the selected edge set and the weight sum of the selected edges in T, respectively.Then, the proposed constructive procedure employs the KM to find a maximum perfect matchingMT of G. The obtained maximum perfect matching MT is an edge set which indicates a spectrum auction scheme. Add the obtained maximum perfect matching MT into T. After adding the obtained maximum perfect matching, for each eij∈MT, the primary operator i allocates the spectrum to the secondary users j, and its surplus spectrum is calculated by ci=ci−dj/bi. There may exist primary operators whose surplus spectrum exceeds the requested spectrum chunk of unallocated secondary users. In other words, after the above auction allocation, some primary operators may still have enough spectrum to provide to secondary users. A primary operator is called active if it can allocate the surplus spectrum chunk to at least one unallocated secondary user in the system. We update the graph G as follows. First, we delete all edges with wij≠0. Second, for each i∈M and j∈N, if equation (5) is satisfied, we add an edge eij into E, and the weight of eij is set to pj. Finally, we remove all edges between the allocated secondary user and primary operator, which indicates that the allocated secondary user is not allowed to receive the spectrum again. Let activepn be the number of active primary users. If activepn≠0, the constructive procedure executes the above process. Otherwise, if there is no active primary operator in the system, we stop the algorithm and return the selected edge setT, which indicates an initial spectrum allocation scheme and its social welfareSumW.Algorithm 1: Constructive procedure
Require: input n, m, b, c, d, p.Ensure: T, and SumW.1: Construct the initial weighted bipartite graphG=V,E, where V=M∪N.2: Add virtual vertices and edges.3: InitializeT=∅, SumW=0.4:repeat5:  Find the maximum perfect matchingMT by using the KM.6:  LetT=T∪MT, SumW=SumW+∑eij∈MTwij, and for each eij∈MT, update ci=ci−dj/bi.7:  Update graphG.8:untilactivepn=09: RETURNT, and SumWFigure2 shows an example of the constructive procedure based on KM with n=10 and m=6. The spectrum demand and the signal-to-noise ratio of secondary users (cognitive users) N are set to 181,51,126,140,65,185,178,157,152,63 and 112,117,117,200,139,108,185,117,186,144, respectively. The number of channels and the channel’s bandwidth of primary operators M are set to 16,10,20,15,7,15 and 16,11,18,12,19,16, respectively. The weighted bipartite graph G is constructed by adding four virtual vertices in M. The weights of the edges between the primary operator and the secondary user are set as dj×log1+γj. The weights of the edges between the virtual vertices and the secondary user are set to zero.Figure 2
An example withn=10 and m=6.There are six active primary operators in the weighted bipartite graph, i.e.,activepn=6; the KM algorithm is applied to find the maximum perfect matching. The secondary users with spectrum demand D=181,126,65,185,178 are allocated with a spectrum by primary operators with the channel’s bandwidth B=16,10,20,15,7,15. After the first match, the primary operator with the channel’s bandwidth of sixteen has four channels remaining, and the primary operator with the channel’s bandwidth of twenty has eight channels remaining also. Therefore, the new weighted bipartite graph can be constructed. The number of active primary operators is activepn=2, the KM algorithm is applied to find the maximum perfect matching, and finally the secondary users with spectrum demand D=157,63 are allocated with a spectrum by primary operators with the channel’s bandwidth B=20,16. After the second match, the secondary users with spectrum demand D=51,140 are still not allocated. Because all the primary operators are not active, the constructive procedure on KM stops and we get the initial spectrum allocation.


### 3.2. Local Search Procedure

According to the execution of Algorithm1, an initial spectrum allocation scheme is obtained. Although there are no primary operators that can directly allocate the spectrum to any secondary users in the system, the allocation is not the optimal allocation for the system because some of the primary operators also have some idle spectrum chunk. We propose a local search procedure, which integrates a swap procedure and an interchange procedure, to improve the solution quality.The basic idea of the swap procedure is to swap the allocated spectrum chunk between the primary operators and make some primary operators get a bigger idle spectrum chunk. So it is possible for the primary operators with a bigger idle spectrum chunk to assign spectrum chunk to some unallocated secondary users.LetAsnumi be the number of secondary users which the primary operator i has been allocated to and sik be the quantity of the spectrum chunk of the kth secondary user in the array the primary user i has been assigned to. To swap the allocated spectrum chunk, we also define the value of the swap flag as Fswap, where Fswap=true denotes that there exist primary operators swapping allocated secondary users. Variable Sfj records the status of the secondary user j, where Sfj can be defined as follows:
(7)Sfj=i,ifprimaryoperatoriallocatesthespectrumtosecondaryuserj,0,otherwise.At the beginning of the swap procedure, we first sort all the primary operators according to the surplus spectrum chunk quantity valueci in descending order; then, we swap the idle spectrum chunk between the sorted primary operators to make one of the primary operator idle spectrum chunk bigger. During the swap procedure, if the primary operator with a bigger idle spectrum chunk can be allocated to an unallocated secondary user, the primary operator allocates the spectrum to this unallocated secondary user to improve the social welfare. We iteratively implement the swap process until all primary operators have been checked. The swap procedure is presented in Algorithm 2.Algorithm 2: Swap procedure
1: Generate primary operator array according to the assigned secondary user.2: Sort primary operator array on the surplus spectrum chunk in descending order.3: setFswap=false; q=0.4:fori=m−1;i>0;i−−do5:forj=i+1;j<=m;j++do6:fork=0;k<Asnumi;k++do7:ifsik/bjbj≤bjc′jthen8:     Move secondary userk in primary operator i to the idle surplus spectrum of primary operator j; k−−.9:else10:forl=Asnumj−1;l>=0;l−−do11:ifsjl>=sikthen12:      break.13:else14:ifc′jbj+sjl/bjbj>=sikthen15:       Swap allocated spectrum betweenk secondary user in primary operator i and l secondary user in primary operator j.16:end if17:end if18:end for19:end if20:end for21:  Finding an unassigned secondary userq with maximal bid price.22:ifq≠0then23:Sfq=i, Asnumi=Asnum+1, c′i=c′i−dq/bi.24:end if25:  Sort the primary operatori on the assigned spectrum chunk in descending order.26:end for27: ifFswap==true28:i++.29:end forAfter the swap procedure, we use an interchange procedure to further improve the social welfare. The proposed interchange procedure uses the interchange of the allocated secondary user by some unallocated users set with higher bid price, so as to promote the total social welfare of the auction.In order to describe the interchange procedure clearly, we introduce some notations. LetSump be the total value of some given secondary user set bid price, TS be the value of the temporary secondary user set, and counter be the number of the vector TS, respectively. cp represents the value of the spectrum quantity. The step of the interchange algorithm on local search can be presented as Algorithm 3.Algorithm 3: Interchange procedure
1: Inherit the parameter value obtained from Algorithm1 and Algorithm 2.2:fori=1;i<n;i++do3:ifSfi>0then4:  Setk=Sfi; cp=sik+ck.5:  SetSump=0; counter=0.6:  SetTS=∅.7:forj=1;j<n;j++do8:ifSfj==0andcp>=sikthen9:counter=counter+1; Tcounter=j.10:cp=cp−sjk; l=Sfj.11:Sump=Sump+pl.12:end if13:end for14:ifSump>pkthen15:fory=0;y<counter;y++do16:Sfy=k.17:end for18:ck=cp; Sfi=0.19:SumW=SumW+Sump−pk.20:end if21:end if22:end for23: ReturnSumW.


### 3.3. The Computational Complexity

We now analyze the computational complexity of the proposed spectrum auction mechanism. The proposed mechanism contains three main procedures: the constructive procedure, the swap procedure, and the interchange procedure. The computational complexity of the constructive procedure (Algorithm1) is decided by the application of the KM. The computational complexity of the KM is On3. Since the KM is executed at most m iterations in the constructive procedure, the computational complexity of the constructive procedure is bounded by Omn3. To find a bigger spectrum chunk for secondary users, the swap procedure (Algorithm 2) searches the idle spectrum chunk between all the primary operators. This operator takes Om2 time. If a bigger idle spectrum chunk is found, the swap procedure needs On to find a secondary user for allocation. Hence, the swap procedure is bounded by Onm2. The interchange procedure (Algorithm 3) takes On2 to further improve the social welfare. Therefore, the computational complexity of the proposed spectrum auction mechanism is bounded by Omn3+nm2+n2.


### 3.4. The Payment Rule and Economic Properties

We propose the payment rule and the economic properties for the auction model. After executing the proposed algorithm, we adopt the payment of each winning secondary user; if secondary userj was denied in the auction or Bj−=∅, then its payment is zero. Otherwise, secondary user j wins, and its payment is dj×pk/dk, where k∈Bj−, Bj− represents the bid set of the secondary user j that was denied in the auction, and Bj denotes the bid bundle of the secondary user j that won in the auction, and theBj−andBjcan be calculated according to the following: bidBjblocksBj−or not. We say the bid Bj blocks Bj− if removing secondary user j from the bidders’ set, all bids in Bj− can be granted.[30] analyzed the economic properties of their auction model. Although our proposed spectrum auction mechanism is different from the mechanism in [30], we use the same payment rule. The results in [30] indicate that our auction model has incentive compatibility and individual rationality. Therefore, it guarantees that no secondary user can get a higher utility by bidding untruthfully and all true bidding for the secondary user can get nonnegative utilities in the proposed auction model.


## 3.1. The Constructive Procedure Based on KM

The existing greedy algorithm [30] used the individual information to generate a spectrum allocation scheme. In each iteration, only one secondary user obtained the spectrum. In this work, our proposed constructive procedure applies the KM to achieve global optimization efficiently and generate an initial spectrum auction scheme. Different from existing greedy algorithms, in each iteration of our constructive procedure, several secondary users are simultaneously allocated by global consideration. It enhances the efficiency of the allocation.The pseudocode of the constructive procedure is given in Algorithm1. After receiving all channel information and bid information, the constructive procedure firstly constructs the weighted bipartite graph G=V,E, where V=M∪N. Note that the number of primary operators is usually smaller than the number of secondary users (i.e., m<n). In order to apply the KM, we add n−m virtual vertices to M for ensuring n=m. Meanwhile, we add edges between each virtual vertex and each vertex in N, and the weights of these adding edges are set to zero. The obtained graph is also denoted by G. Let T and SumW be the selected edge set and the weight sum of the selected edges in T, respectively.Then, the proposed constructive procedure employs the KM to find a maximum perfect matchingMT of G. The obtained maximum perfect matching MT is an edge set which indicates a spectrum auction scheme. Add the obtained maximum perfect matching MT into T. After adding the obtained maximum perfect matching, for each eij∈MT, the primary operator i allocates the spectrum to the secondary users j, and its surplus spectrum is calculated by ci=ci−dj/bi. There may exist primary operators whose surplus spectrum exceeds the requested spectrum chunk of unallocated secondary users. In other words, after the above auction allocation, some primary operators may still have enough spectrum to provide to secondary users. A primary operator is called active if it can allocate the surplus spectrum chunk to at least one unallocated secondary user in the system. We update the graph G as follows. First, we delete all edges with wij≠0. Second, for each i∈M and j∈N, if equation (5) is satisfied, we add an edge eij into E, and the weight of eij is set to pj. Finally, we remove all edges between the allocated secondary user and primary operator, which indicates that the allocated secondary user is not allowed to receive the spectrum again. Let activepn be the number of active primary users. If activepn≠0, the constructive procedure executes the above process. Otherwise, if there is no active primary operator in the system, we stop the algorithm and return the selected edge setT, which indicates an initial spectrum allocation scheme and its social welfareSumW.Algorithm 1: Constructive procedure
Require: input n, m, b, c, d, p.Ensure: T, and SumW.1: Construct the initial weighted bipartite graphG=V,E, where V=M∪N.2: Add virtual vertices and edges.3: InitializeT=∅, SumW=0.4:repeat5:  Find the maximum perfect matchingMT by using the KM.6:  LetT=T∪MT, SumW=SumW+∑eij∈MTwij, and for each eij∈MT, update ci=ci−dj/bi.7:  Update graphG.8:untilactivepn=09: RETURNT, and SumWFigure2 shows an example of the constructive procedure based on KM with n=10 and m=6. The spectrum demand and the signal-to-noise ratio of secondary users (cognitive users) N are set to 181,51,126,140,65,185,178,157,152,63 and 112,117,117,200,139,108,185,117,186,144, respectively. The number of channels and the channel’s bandwidth of primary operators M are set to 16,10,20,15,7,15 and 16,11,18,12,19,16, respectively. The weighted bipartite graph G is constructed by adding four virtual vertices in M. The weights of the edges between the primary operator and the secondary user are set as dj×log1+γj. The weights of the edges between the virtual vertices and the secondary user are set to zero.Figure 2
An example withn=10 and m=6.There are six active primary operators in the weighted bipartite graph, i.e.,activepn=6; the KM algorithm is applied to find the maximum perfect matching. The secondary users with spectrum demand D=181,126,65,185,178 are allocated with a spectrum by primary operators with the channel’s bandwidth B=16,10,20,15,7,15. After the first match, the primary operator with the channel’s bandwidth of sixteen has four channels remaining, and the primary operator with the channel’s bandwidth of twenty has eight channels remaining also. Therefore, the new weighted bipartite graph can be constructed. The number of active primary operators is activepn=2, the KM algorithm is applied to find the maximum perfect matching, and finally the secondary users with spectrum demand D=157,63 are allocated with a spectrum by primary operators with the channel’s bandwidth B=20,16. After the second match, the secondary users with spectrum demand D=51,140 are still not allocated. Because all the primary operators are not active, the constructive procedure on KM stops and we get the initial spectrum allocation.


## 3.2. Local Search Procedure

According to the execution of Algorithm1, an initial spectrum allocation scheme is obtained. Although there are no primary operators that can directly allocate the spectrum to any secondary users in the system, the allocation is not the optimal allocation for the system because some of the primary operators also have some idle spectrum chunk. We propose a local search procedure, which integrates a swap procedure and an interchange procedure, to improve the solution quality.The basic idea of the swap procedure is to swap the allocated spectrum chunk between the primary operators and make some primary operators get a bigger idle spectrum chunk. So it is possible for the primary operators with a bigger idle spectrum chunk to assign spectrum chunk to some unallocated secondary users.LetAsnumi be the number of secondary users which the primary operator i has been allocated to and sik be the quantity of the spectrum chunk of the kth secondary user in the array the primary user i has been assigned to. To swap the allocated spectrum chunk, we also define the value of the swap flag as Fswap, where Fswap=true denotes that there exist primary operators swapping allocated secondary users. Variable Sfj records the status of the secondary user j, where Sfj can be defined as follows:
(7)Sfj=i,ifprimaryoperatoriallocatesthespectrumtosecondaryuserj,0,otherwise.At the beginning of the swap procedure, we first sort all the primary operators according to the surplus spectrum chunk quantity valueci in descending order; then, we swap the idle spectrum chunk between the sorted primary operators to make one of the primary operator idle spectrum chunk bigger. During the swap procedure, if the primary operator with a bigger idle spectrum chunk can be allocated to an unallocated secondary user, the primary operator allocates the spectrum to this unallocated secondary user to improve the social welfare. We iteratively implement the swap process until all primary operators have been checked. The swap procedure is presented in Algorithm 2.Algorithm 2: Swap procedure
1: Generate primary operator array according to the assigned secondary user.2: Sort primary operator array on the surplus spectrum chunk in descending order.3: setFswap=false; q=0.4:fori=m−1;i>0;i−−do5:forj=i+1;j<=m;j++do6:fork=0;k<Asnumi;k++do7:ifsik/bjbj≤bjc′jthen8:     Move secondary userk in primary operator i to the idle surplus spectrum of primary operator j; k−−.9:else10:forl=Asnumj−1;l>=0;l−−do11:ifsjl>=sikthen12:      break.13:else14:ifc′jbj+sjl/bjbj>=sikthen15:       Swap allocated spectrum betweenk secondary user in primary operator i and l secondary user in primary operator j.16:end if17:end if18:end for19:end if20:end for21:  Finding an unassigned secondary userq with maximal bid price.22:ifq≠0then23:Sfq=i, Asnumi=Asnum+1, c′i=c′i−dq/bi.24:end if25:  Sort the primary operatori on the assigned spectrum chunk in descending order.26:end for27: ifFswap==true28:i++.29:end forAfter the swap procedure, we use an interchange procedure to further improve the social welfare. The proposed interchange procedure uses the interchange of the allocated secondary user by some unallocated users set with higher bid price, so as to promote the total social welfare of the auction.In order to describe the interchange procedure clearly, we introduce some notations. LetSump be the total value of some given secondary user set bid price, TS be the value of the temporary secondary user set, and counter be the number of the vector TS, respectively. cp represents the value of the spectrum quantity. The step of the interchange algorithm on local search can be presented as Algorithm 3.Algorithm 3: Interchange procedure
1: Inherit the parameter value obtained from Algorithm1 and Algorithm 2.2:fori=1;i<n;i++do3:ifSfi>0then4:  Setk=Sfi; cp=sik+ck.5:  SetSump=0; counter=0.6:  SetTS=∅.7:forj=1;j<n;j++do8:ifSfj==0andcp>=sikthen9:counter=counter+1; Tcounter=j.10:cp=cp−sjk; l=Sfj.11:Sump=Sump+pl.12:end if13:end for14:ifSump>pkthen15:fory=0;y<counter;y++do16:Sfy=k.17:end for18:ck=cp; Sfi=0.19:SumW=SumW+Sump−pk.20:end if21:end if22:end for23: ReturnSumW.


## 3.3. The Computational Complexity

We now analyze the computational complexity of the proposed spectrum auction mechanism. The proposed mechanism contains three main procedures: the constructive procedure, the swap procedure, and the interchange procedure. The computational complexity of the constructive procedure (Algorithm1) is decided by the application of the KM. The computational complexity of the KM is On3. Since the KM is executed at most m iterations in the constructive procedure, the computational complexity of the constructive procedure is bounded by Omn3. To find a bigger spectrum chunk for secondary users, the swap procedure (Algorithm 2) searches the idle spectrum chunk between all the primary operators. This operator takes Om2 time. If a bigger idle spectrum chunk is found, the swap procedure needs On to find a secondary user for allocation. Hence, the swap procedure is bounded by Onm2. The interchange procedure (Algorithm 3) takes On2 to further improve the social welfare. Therefore, the computational complexity of the proposed spectrum auction mechanism is bounded by Omn3+nm2+n2.


## 3.4. The Payment Rule and Economic Properties

We propose the payment rule and the economic properties for the auction model. After executing the proposed algorithm, we adopt the payment of each winning secondary user; if secondary userj was denied in the auction or Bj−=∅, then its payment is zero. Otherwise, secondary user j wins, and its payment is dj×pk/dk, where k∈Bj−, Bj− represents the bid set of the secondary user j that was denied in the auction, and Bj denotes the bid bundle of the secondary user j that won in the auction, and theBj−andBjcan be calculated according to the following: bidBjblocksBj−or not. We say the bid Bj blocks Bj− if removing secondary user j from the bidders’ set, all bids in Bj− can be granted.[30] analyzed the economic properties of their auction model. Although our proposed spectrum auction mechanism is different from the mechanism in [30], we use the same payment rule. The results in [30] indicate that our auction model has incentive compatibility and individual rationality. Therefore, it guarantees that no secondary user can get a higher utility by bidding untruthfully and all true bidding for the secondary user can get nonnegative utilities in the proposed auction model.


## 4. Experiment

In this section, we evaluate the performance of the proposed spectrum auction mechanism of the cognitive radio network for EI in a smart city. We run the implementation in a Windows 7 system with Intel Core i5-3210M 2.5GHZ and 4GB memory. The program was written in C language and run in software C-Free 5. We also generate the scenario with heterogeneous primary operators (the channel bandwidth and the number of channels are different) and multiple secondary users with different spectrum demands in the cognitive radio network of EI in a smart city. For comparison purposes, the specific simulation parameters in this paper are similar to those in [30]. We also coded the spectrum allocation algorithm in [30] in C language and made comparisons between this spectrum allocation algorithm [30] and our proposed algorithm.


### 4.1. Experimental Setup

We assume that there are 100 secondary users randomly distributed in the network. All the primary operators are independent, and the number of channels of each primary operator is randomly selected in10,20; the channel bandwidth of each primary operator is also randomly selected in 5,20 MHz. In the same way, we also assume that the spectrum demand of each secondary user in the network is randomly chosen in 50,20 MHz, and the corresponding secondary users’ SNR γj for secondary user j is randomly selected in 100,200; the bid price of the secondary user is defined as dj×log1+γj, where dj is the spectrum demand of secondary users j. We use the following performance metrics to evaluate the proposed auction model:
(i)
Social Welfare. The sum bid price of the secondary user in the auction.(ii)
Seller Revenue. The sum of charged payments of all the winning secondary users in the auction.(iii)
Buyer Satisfaction Ratio. The percentage of winning secondary user bids to the total demands.(iv)
Winning Buyer Ratio. The percentage of the number of winning secondary users to the total number of secondary users.


### 4.2. Experimental Results

#### 4.2.1. Fixed Network Size

Firstly, we evaluate the proposed algorithm performance with the number of primary operators is fixed to 50. The other network parameter is randomly generated as described in Section4.1. The result generated under the greedy algorithm and the enhanced greedy algorithm in [30] is, respectively, denoted as the Greedy algorithm and Enhanced Greedy algorithm; the results of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio for the different algorithms are compared on the value over 100 runs.Figure3 shows the computational results with respect to the social welfare when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 11.48% times) than the Greedy algorithm on the social welfare with different algorithm run indexes. The proposed algorithm is also higher (average of 1.23% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the social welfare.Figure 3
Comparison of the social welfare under different algorithms with a fixed secondary user.Figure4 shows the computational results with respect to the auction revenue when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 13.7% times) than the Greedy algorithm on the auction revenue with different algorithm run indexes. The proposed algorithm is also higher (average of 5.19% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the auction revenue.Figure 4
Comparison of the auction revenue under different algorithms with a fixed network size.Figure5 shows the computational results with respect to the buyer satisfaction ratio when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 11.3% times) than the Greedy algorithm on the buyer satisfaction ratio with different algorithm run indexes. The proposed algorithm is also higher (average of 1.9% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the buyer satisfaction ratio.Figure 5
Comparison of the buyer satisfaction ratio under different algorithms with a fixed network size.Figure6 shows the computational results with respect to the winning buyer ratio when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 15.99% times) than the Greedy algorithm on the winning buyer ratio with different algorithm run indexes. The proposed algorithm is also higher (average of 8.47% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the winning buyer ratio.Figure 6
Comparison of the winning buyer ratio under different algorithms with a fixed network size.


#### 4.2.2. Varied Network Size

Secondly, we varied the number of primary operators from 5 to 50 to evaluate the proposed algorithm performance with different network sizes. The result also generated under the greedy algorithm and the enhanced greedy algorithm in [30] is, respectively, denoted as Greedy algorithm and Enhanced Greedy algorithm; the results of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio for the different algorithms are compared on the average value over 1000 runs.In Figure7, the social welfare of different algorithms increases when the number of primary operators varies from 5 to 50. That is because more primary operators in the network can allocate more spectrum requirements for higher bid secondary users. When the number of primary operators varies from 5 to 50, the gap between the proposed algorithm and the Greedy algorithm increases, and the social welfare is varied from 2.96% to 11.03% times higher than the Greedy algorithm. Compared with the Enhanced Greedy algorithm, the proposed algorithm can achieve larger social welfare. Moreover, the social welfare of the proposed algorithm is about averagely 0.42% times higher than that of the Enhanced Greedy algorithm. From the simulation result, we can see that when the network size is small, the social welfare of the proposed algorithm is slightly larger than that of the two benchmark algorithms. When the number of the primary operator and secondary users is large, the social welfare of the proposed algorithm is more efficient than that of the benchmark algorithms.Figure 7
Comparison of the social welfare under different algorithms.Figure8 shows the computational results with respect to the auction revenue. We can see clearly from Figure 8 that the auction revenue increases when the number of primary operators varies from 5 to 50. That is because the more primary operators in the network, the more spectrum requirements of secondary users can be satisfied. The proposed algorithm is 13.75% to 38.6% times higher than the Greedy algorithm on the auction revenue (average of 24.67%). The proposed algorithm is 4.89% to 25.31% times higher than the Enhanced Greedy algorithm (average of 13.08%). The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the auction revenue.Figure 8
Comparison of the auction revenue under different algorithms.Figure9 lists the buyer satisfaction ratio obtained by three algorithms. In Figure 9, we can see that with the increase of primary operators, the buyer satisfaction ratio goes up. The buyer satisfaction ratio of the proposed algorithm is averagely 8.3% and 0.12% times higher than that of the Greedy algorithm and the Enhanced Greedy algorithm, respectively.Figure 9
Comparison of the buyer satisfaction ratio under different algorithms.In Figure10, we compare the winning buyer ratio achieved by our proposed algorithm with the two benchmark algorithms. We can see that with the increase of primary operators, the winning buyer ratio increases because more secondary users’ spectrum demands are satisfied. The proposed algorithm is averagely 47.79% times and 23.78% times higher than the Greedy algorithm and Enhanced Greedy algorithm on the winning buyer ratio, respectively. The proposed algorithm can allocate more secondary users because the demand and the bid price are globally considered.Figure 10
Comparison of the winning buyer ratio under different algorithms.Figure11 shows the time of each run (the average value over 1000 runs) achieved by our proposed algorithm with the two benchmark algorithms. We can see the running time increases with primary operators increasing. That is because more primary operators in the network increase the computational complexity. Though the running time of the proposed algorithm is a few milliseconds than the two benchmark algorithms, the proposed algorithm achieves obviously higher social welfare, auction revenue, buyer satisfaction ratio, and winning buyer ratio than the two benchmark algorithms. The proposed algorithm can obtain higher allocation performance and efficiency for the cognitive radio network of EI in a smart city.Figure 11
Comparison of the time of each run under different algorithms.From the above observations, we can conclude that our proposed algorithm outperforms the two greedy algorithms in terms of the above four performance metrics. The proposed algorithm provides an efficient method to allocate the allocation spectrum resource in the cognitive radio system of EI for a smart city.


## 4.1. Experimental Setup

We assume that there are 100 secondary users randomly distributed in the network. All the primary operators are independent, and the number of channels of each primary operator is randomly selected in10,20; the channel bandwidth of each primary operator is also randomly selected in 5,20 MHz. In the same way, we also assume that the spectrum demand of each secondary user in the network is randomly chosen in 50,20 MHz, and the corresponding secondary users’ SNR γj for secondary user j is randomly selected in 100,200; the bid price of the secondary user is defined as dj×log1+γj, where dj is the spectrum demand of secondary users j. We use the following performance metrics to evaluate the proposed auction model:
(i)
Social Welfare. The sum bid price of the secondary user in the auction.(ii)
Seller Revenue. The sum of charged payments of all the winning secondary users in the auction.(iii)
Buyer Satisfaction Ratio. The percentage of winning secondary user bids to the total demands.(iv)
Winning Buyer Ratio. The percentage of the number of winning secondary users to the total number of secondary users.


## 4.2. Experimental Results

### 4.2.1. Fixed Network Size

Firstly, we evaluate the proposed algorithm performance with the number of primary operators is fixed to 50. The other network parameter is randomly generated as described in Section4.1. The result generated under the greedy algorithm and the enhanced greedy algorithm in [30] is, respectively, denoted as the Greedy algorithm and Enhanced Greedy algorithm; the results of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio for the different algorithms are compared on the value over 100 runs.Figure3 shows the computational results with respect to the social welfare when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 11.48% times) than the Greedy algorithm on the social welfare with different algorithm run indexes. The proposed algorithm is also higher (average of 1.23% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the social welfare.Figure 3
Comparison of the social welfare under different algorithms with a fixed secondary user.Figure4 shows the computational results with respect to the auction revenue when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 13.7% times) than the Greedy algorithm on the auction revenue with different algorithm run indexes. The proposed algorithm is also higher (average of 5.19% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the auction revenue.Figure 4
Comparison of the auction revenue under different algorithms with a fixed network size.Figure5 shows the computational results with respect to the buyer satisfaction ratio when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 11.3% times) than the Greedy algorithm on the buyer satisfaction ratio with different algorithm run indexes. The proposed algorithm is also higher (average of 1.9% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the buyer satisfaction ratio.Figure 5
Comparison of the buyer satisfaction ratio under different algorithms with a fixed network size.Figure6 shows the computational results with respect to the winning buyer ratio when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 15.99% times) than the Greedy algorithm on the winning buyer ratio with different algorithm run indexes. The proposed algorithm is also higher (average of 8.47% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the winning buyer ratio.Figure 6
Comparison of the winning buyer ratio under different algorithms with a fixed network size.


### 4.2.2. Varied Network Size

Secondly, we varied the number of primary operators from 5 to 50 to evaluate the proposed algorithm performance with different network sizes. The result also generated under the greedy algorithm and the enhanced greedy algorithm in [30] is, respectively, denoted as Greedy algorithm and Enhanced Greedy algorithm; the results of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio for the different algorithms are compared on the average value over 1000 runs.In Figure7, the social welfare of different algorithms increases when the number of primary operators varies from 5 to 50. That is because more primary operators in the network can allocate more spectrum requirements for higher bid secondary users. When the number of primary operators varies from 5 to 50, the gap between the proposed algorithm and the Greedy algorithm increases, and the social welfare is varied from 2.96% to 11.03% times higher than the Greedy algorithm. Compared with the Enhanced Greedy algorithm, the proposed algorithm can achieve larger social welfare. Moreover, the social welfare of the proposed algorithm is about averagely 0.42% times higher than that of the Enhanced Greedy algorithm. From the simulation result, we can see that when the network size is small, the social welfare of the proposed algorithm is slightly larger than that of the two benchmark algorithms. When the number of the primary operator and secondary users is large, the social welfare of the proposed algorithm is more efficient than that of the benchmark algorithms.Figure 7
Comparison of the social welfare under different algorithms.Figure8 shows the computational results with respect to the auction revenue. We can see clearly from Figure 8 that the auction revenue increases when the number of primary operators varies from 5 to 50. That is because the more primary operators in the network, the more spectrum requirements of secondary users can be satisfied. The proposed algorithm is 13.75% to 38.6% times higher than the Greedy algorithm on the auction revenue (average of 24.67%). The proposed algorithm is 4.89% to 25.31% times higher than the Enhanced Greedy algorithm (average of 13.08%). The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the auction revenue.Figure 8
Comparison of the auction revenue under different algorithms.Figure9 lists the buyer satisfaction ratio obtained by three algorithms. In Figure 9, we can see that with the increase of primary operators, the buyer satisfaction ratio goes up. The buyer satisfaction ratio of the proposed algorithm is averagely 8.3% and 0.12% times higher than that of the Greedy algorithm and the Enhanced Greedy algorithm, respectively.Figure 9
Comparison of the buyer satisfaction ratio under different algorithms.In Figure10, we compare the winning buyer ratio achieved by our proposed algorithm with the two benchmark algorithms. We can see that with the increase of primary operators, the winning buyer ratio increases because more secondary users’ spectrum demands are satisfied. The proposed algorithm is averagely 47.79% times and 23.78% times higher than the Greedy algorithm and Enhanced Greedy algorithm on the winning buyer ratio, respectively. The proposed algorithm can allocate more secondary users because the demand and the bid price are globally considered.Figure 10
Comparison of the winning buyer ratio under different algorithms.Figure11 shows the time of each run (the average value over 1000 runs) achieved by our proposed algorithm with the two benchmark algorithms. We can see the running time increases with primary operators increasing. That is because more primary operators in the network increase the computational complexity. Though the running time of the proposed algorithm is a few milliseconds than the two benchmark algorithms, the proposed algorithm achieves obviously higher social welfare, auction revenue, buyer satisfaction ratio, and winning buyer ratio than the two benchmark algorithms. The proposed algorithm can obtain higher allocation performance and efficiency for the cognitive radio network of EI in a smart city.Figure 11
Comparison of the time of each run under different algorithms.From the above observations, we can conclude that our proposed algorithm outperforms the two greedy algorithms in terms of the above four performance metrics. The proposed algorithm provides an efficient method to allocate the allocation spectrum resource in the cognitive radio system of EI for a smart city.


## 4.2.1. Fixed Network Size

Firstly, we evaluate the proposed algorithm performance with the number of primary operators is fixed to 50. The other network parameter is randomly generated as described in Section4.1. The result generated under the greedy algorithm and the enhanced greedy algorithm in [30] is, respectively, denoted as the Greedy algorithm and Enhanced Greedy algorithm; the results of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio for the different algorithms are compared on the value over 100 runs.Figure3 shows the computational results with respect to the social welfare when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 11.48% times) than the Greedy algorithm on the social welfare with different algorithm run indexes. The proposed algorithm is also higher (average of 1.23% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the social welfare.Figure 3
Comparison of the social welfare under different algorithms with a fixed secondary user.Figure4 shows the computational results with respect to the auction revenue when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 13.7% times) than the Greedy algorithm on the auction revenue with different algorithm run indexes. The proposed algorithm is also higher (average of 5.19% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the auction revenue.Figure 4
Comparison of the auction revenue under different algorithms with a fixed network size.Figure5 shows the computational results with respect to the buyer satisfaction ratio when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 11.3% times) than the Greedy algorithm on the buyer satisfaction ratio with different algorithm run indexes. The proposed algorithm is also higher (average of 1.9% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the buyer satisfaction ratio.Figure 5
Comparison of the buyer satisfaction ratio under different algorithms with a fixed network size.Figure6 shows the computational results with respect to the winning buyer ratio when the number of different algorithm run indexes varies from 1 to 100. It can be clearly seen that the proposed algorithm is higher (average of 15.99% times) than the Greedy algorithm on the winning buyer ratio with different algorithm run indexes. The proposed algorithm is also higher (average of 8.47% times) than the Enhanced Greedy algorithm. The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the winning buyer ratio.Figure 6
Comparison of the winning buyer ratio under different algorithms with a fixed network size.


## 4.2.2. Varied Network Size

Secondly, we varied the number of primary operators from 5 to 50 to evaluate the proposed algorithm performance with different network sizes. The result also generated under the greedy algorithm and the enhanced greedy algorithm in [30] is, respectively, denoted as Greedy algorithm and Enhanced Greedy algorithm; the results of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio for the different algorithms are compared on the average value over 1000 runs.In Figure7, the social welfare of different algorithms increases when the number of primary operators varies from 5 to 50. That is because more primary operators in the network can allocate more spectrum requirements for higher bid secondary users. When the number of primary operators varies from 5 to 50, the gap between the proposed algorithm and the Greedy algorithm increases, and the social welfare is varied from 2.96% to 11.03% times higher than the Greedy algorithm. Compared with the Enhanced Greedy algorithm, the proposed algorithm can achieve larger social welfare. Moreover, the social welfare of the proposed algorithm is about averagely 0.42% times higher than that of the Enhanced Greedy algorithm. From the simulation result, we can see that when the network size is small, the social welfare of the proposed algorithm is slightly larger than that of the two benchmark algorithms. When the number of the primary operator and secondary users is large, the social welfare of the proposed algorithm is more efficient than that of the benchmark algorithms.Figure 7
Comparison of the social welfare under different algorithms.Figure8 shows the computational results with respect to the auction revenue. We can see clearly from Figure 8 that the auction revenue increases when the number of primary operators varies from 5 to 50. That is because the more primary operators in the network, the more spectrum requirements of secondary users can be satisfied. The proposed algorithm is 13.75% to 38.6% times higher than the Greedy algorithm on the auction revenue (average of 24.67%). The proposed algorithm is 4.89% to 25.31% times higher than the Enhanced Greedy algorithm (average of 13.08%). The simulation result shows that the proposed algorithm is more efficient than the benchmark algorithms in terms of the auction revenue.Figure 8
Comparison of the auction revenue under different algorithms.Figure9 lists the buyer satisfaction ratio obtained by three algorithms. In Figure 9, we can see that with the increase of primary operators, the buyer satisfaction ratio goes up. The buyer satisfaction ratio of the proposed algorithm is averagely 8.3% and 0.12% times higher than that of the Greedy algorithm and the Enhanced Greedy algorithm, respectively.Figure 9
Comparison of the buyer satisfaction ratio under different algorithms.In Figure10, we compare the winning buyer ratio achieved by our proposed algorithm with the two benchmark algorithms. We can see that with the increase of primary operators, the winning buyer ratio increases because more secondary users’ spectrum demands are satisfied. The proposed algorithm is averagely 47.79% times and 23.78% times higher than the Greedy algorithm and Enhanced Greedy algorithm on the winning buyer ratio, respectively. The proposed algorithm can allocate more secondary users because the demand and the bid price are globally considered.Figure 10
Comparison of the winning buyer ratio under different algorithms.Figure11 shows the time of each run (the average value over 1000 runs) achieved by our proposed algorithm with the two benchmark algorithms. We can see the running time increases with primary operators increasing. That is because more primary operators in the network increase the computational complexity. Though the running time of the proposed algorithm is a few milliseconds than the two benchmark algorithms, the proposed algorithm achieves obviously higher social welfare, auction revenue, buyer satisfaction ratio, and winning buyer ratio than the two benchmark algorithms. The proposed algorithm can obtain higher allocation performance and efficiency for the cognitive radio network of EI in a smart city.Figure 11
Comparison of the time of each run under different algorithms.From the above observations, we can conclude that our proposed algorithm outperforms the two greedy algorithms in terms of the above four performance metrics. The proposed algorithm provides an efficient method to allocate the allocation spectrum resource in the cognitive radio system of EI for a smart city.


## 5. Conclusions

In this paper, we have proposed a novel spectrum combinatorial auction mechanism for the cognitive radio network of EI in a smart city with multiple heterogeneous primary spectrum operators and multiple secondary users. The proposed mechanism iteratively used the well-known KM to generate an initial allocation scheme. Then, a swap procedure and an interchange procedure were applied to further promote the spectrum allocation efficiency. The truthfulness was guaranteed by adopting a “Vickrey-like” mechanism. Simulation results show that the proposed auction mechanism can enhance the spectrum allocation efficiency of the cognitive radio network in a smart city in terms of the social welfare, seller revenue, buyer satisfaction ratio, and winning buyer ratio by comparing with the existing mechanism. As a future work, our hybrid spectrum auction mechanism can be extended to resource allocation problems in other networks of EI in a smart city.



---

*Source: 8829602-2020-11-05.xml*