# Finder-MCTS: A Cognitive Spectrum Allocation Based on Traveling State Priority and Scenario Simulation in IoV

Authors: Zhong Li; Hao Shao
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

With the increasing number of intelligent connected vehicles, the problem of scarcity of communication resources has become increasingly obvious. It is a practical issue with important significance to explore a real-time and reliable dynamic spectrum allocation scheme for the vehicle users, while improving the utilization of the available spectrum. However, previous studies have problems such as local optimum, complex parameter setting, learning speed, and poor convergence. Thus, in this paper, we propose a cognitive spectrum allocation method based on traveling state priority and scenario simulation in IoV, named Finder-MCTS. The proposed method integrates offline learning with online search. This method mainly consists of two stages. Initially, Finder-MCTS gives the allocation priority of different vehicle users based on the vehicle’s local driving status and global communication status. Furthermore, Finder-MCTS can search for the approximate optimal allocation solutions quickly online according to the priority and the scenario simulation, while with the offline deep neural network-based environmental state predictor. In the experiment, we use SUMO to simulate the real traffic flows. Numerical results show that our proposed Finder-MCTS has 36.47%, 18.24%, and 9.00% improvement on average than other popular methods in convergence time, link capacity, and channel utilization, respectively. In addition, we verified the effectiveness and advantages of Finder-MCTS compared with two MCTS algorithms’ variations.


---

## Body

## 1. Introduction

Recently, as a promising technology to serve the smart city, the internet of vehicle (IoV) has attracted the attention of governments and enterprises around the world. The moving vehicles can be regarded as mobile terminals equipped with advanced network components, such as wireless network interfaces and onboard sensors, which provide many personalized services by accessing the internet. These vehicle services (e.g., road condition broadcasts and dangerous event predictions) have high requirements for data transmission and communication quality. Although 5G technology is becoming popular and growing rapidly, the available spectrum resources have not increased simultaneously. So far, the spectrum resources of 6 GHz and below 6 GHz have almost been exhausted [1]. Moreover, the spectrum resources charged by the base stations are usually allocated to the calls and traffic services of mobile users firstly. Some up-to-date spectrum measurements [2] have demonstrated the reality that the spectrum is vastly underutilized, while most licensed spectra have been allocated. Thus, the scarcity of spectrum resources and the low utilization of frequency bands are critical issues hindering the development of IoV.Currently, as an effective solution to the underutilized problem of spectrum resources, cognitive radio (CR) can reuse idle spectrum resources through dynamic spectrum access technology. In CR networks, network users are divided into two types: primary users (PUs) and secondary users (SUs). PUs have a high priority to use the spectrum in the authorized frequency bands. SUs can dynamically access spectrum holes opportunistically and use available spectrum resources, which can enhance spectrum utilization. Therefore, in order to meet the spectrum demand of vehicles, we present a system model of cognitive radio-based internet of vehicle (CR-IoV) by introducing the cognitive radio function into smart vehicles.In CR-IoV, the system includes PUs (composed of mobile phone users) and SUs (composed of vehicles equipped with CR functions). However, in reality, vehicle users with high mobility will cause frequent changes in the network topology. The availability of spectra will also change with the activation time and channel occupancy of PUs. Hence, how to meet the real-time and reliable requirements when solving the dynamic spectrum allocation problem under a time-varying environment is a significant challenge.There are many previous studies about dynamic spectrum allocation in mobile wireless networks. The most popular studies can be mainly classified into four categories: (1) traditional optimization theory-based allocation methods [3, 4], (2) game theory-based allocation methods [5–7], (3) swarm intelligence optimization-based allocation methods [8–12], and (4) machine learning-based allocation methods [13–18]. Although the above methods can solve the spectrum allocation problem, there exist many disadvantages. First, when the constraints are complex, traditional optimization theory and game theory are not suitable for quickly solving large-scale dynamic planning problems. Second, swarm intelligence optimization is easy to fall into the local optimum [19]. Besides, the effective parameter settings and selection in the swarm intelligence optimization are also complex. Recently, deep reinforcement learning (DRL) algorithms have been proved to solve complex dynamic decision-making problems with high-dimensional state and action space. It can learn the potential regularities in the environment with the help of the idea of trial and error, thereby assisting intelligent decision-making. However, this type of machine learning-based method also exists some limitations, such as slow learning speed, poor convergence, and bad self-adaption ability. Thus, in this paper, we propose a new cognitive spectrum allocation method based on traveling state priority and different scenarios specially for IoV in this paper.First, especially in IoV, we should consider the traveling/moving state of a vehicle. A vehicle that is about to leave the coverage area of a base station should have a relatively low spectrum allocation priority. Vehicle users with different traveling states, such as location, speed, acceleration, and communication capabilities, should have different opportunities to obtain spectrum resources. Thus, we consider the priority assignment based on vehicle state in spectrum allocation.In addition, in this proposed new method, we choose the Monte-Carlo tree search algorithm (MCTS) to model our problem. Traditional model-free-based deep reinforcement learning algorithms (e.g., deepQ network and soft actor-critic) often require a large number of samplings and learn strategies from past experiences with the help of neural networks. However, model-based deep MCTS can not only use deep neural networks to fit the environment model from experience data but also simulate a variety of possible future trajectories for evaluation through the expansion of the tree structure, so as to choose more promising directions to explore the best policy. In this paper, through designing to simulate different scenarios, we improve the learning efficiency and reduce the searching space compared with traditional MCTS methods.Our main contributions can be summarized as follows:(i)
We design a priority assignment rule based on vehicle traveling states for spectrum allocation. Through defining a vehicle traveling evaluation score and a network utility score, we obtain a comprehensive priority evaluation score for each vehicle. According to the priority score, we allocate available spectrum resources from the highest priority to the lowest vehicle user, which can improve the allocation performance when doing dynamic spectrum allocation in IoV(ii)
Combining with the above priority score, we propose a cognitive spectrum allocation method based on traveling state priority and different scenarios specially for IoV, named Finder-MCTS. We model the problem of spectrum allocation as a binary integer linear programming problem (BILP) with constraints. Meanwhile, through designing a constraint-oriented tree expansion and scenario simulation mechanism, Finder-MCTS can give an approximate optimal solution quickly and improve the link capacity of V2I (vehicle to infrastructure) communication in the network(iii)
We conduct experiments to evaluate the performance of Finder-MCTS by using SUMO. Results show that our proposed method has 36.47%, 18.24%, and 9.00% improvements on average than other popular comparison methods in convergence time, link capacity, and channel utilization, respectively. In addition, Finder-MCTS also shows good improvements with the aid of priority evaluation and different scenarios’ simulation of PUs’ service durations, compared with two variations of MCTSThe remainder of this paper is organized as follows. In Section2, a review of related work is provided. In Section 3, the system scenario and problem formalization are presented in detail. In Section 4, the priority assignment based on vehicle traveling state is described. In Section 5, the Finder-MCTS method for cognitive IoV spectrum allocation is proposed. In Section 6, simulations are carried out to demonstrate the effectiveness of the proposed Finder-MCTS method. In Section 7, conclusion and future work are given.


## 2. Related Work

Nowadays, there are many excellent studies on dynamic spectrum allocation in cognitive radio networks. In this section, we classify and compare them from the perspective of theoretical methods.


### 2.1. Spectrum Resource Allocation Based on Traditional Optimization Theory and Game Theory

In order to solve the problem of dynamic allocation of spectrum resources in wireless communications, the traditional methods mainly include the methods based on mathematical optimization [3, 4] and the methods based on game theory [5–7]. For example, Martinovic et al. propose a cognitive radio spectrum allocation method based on integer linear programming in the work of [4], which solves the spectrum allocation problem with interference by using many complex assumptions and constraints. It is difficult or even impossible to find an optimal solution in the real cognitive radio network with the complex environment and dynamic network topology. Although the methods based on mathematical optimization have high solution accuracy, the generalization capability is insufficient.Besides, with the goal of maximizing spectrum utilization, Yi and Cai introduce a spectrum resource allocation method based on auction in the work of [6]. Liu et al. design a dynamic spectrum access method using game theory in the work of [7]. However, these methods are not fit for IoV. The high mobility of vehicles puts forward a strict requirement for the convergence of Nash equilibrium in the game theory. It is hard to reach this equilibrium point.


### 2.2. Spectrum Resource Allocation Based on Swarm Intelligence Optimization

There are many related studies [8–12] based on swarm intelligence optimization in the domain of spectrum allocation. For example, Liu et al. use PSO to solve the allocation of spectrum resources in a centralized way in the work of [12]. However, the iteration of swarm intelligence optimization usually gets stuck in local optimal solutions, which can be far from the global optimal solution [19]. In addition, many swarm intelligence optimization algorithms have a large number of calculations in debugging due to complex parameters.


### 2.3. Spectrum Resource Allocation Based on Machine Learning

In recent years, with the development of statistical learning methods, many studies use machine learning to realize the dynamic spectrum allocation [13]. Among them, reinforcement learning can guide a system agent to learn the unknown environment by trial and error [20]. It can be applied to the spectrum allocation decision.First, the multiarm gambling machine (MAB) not only is an important random decision-making theory in the field of operational research but also belongs to a type of online learning algorithm in reinforcement learning. The task of the agent is to select one arm to pull in each round based on the historical rewards it collected, and the goal is to collect cumulative rewards over multiple rounds as much as possible. In essence, MAB is a way to optimize the reward by balancing exploration and exploitation. Li et al. give a survey of spectrum resource allocation by using MAB in the cognitive radio network in the work of [14]. Zhang et al. formulate and study a multiuser MAB problem that exploits the idea of temporal-spatial spectrum reuse in the cognitive radio network [15]. However, the MAB modeling does not consider the cost of pulling arms in the existing allocation schemes. When MAB is utilized to solve the allocation problem in a centralized way, the scale of the arm increases exponentially with the number of users to be assigned. Therefore, the convergence of the spectrum resource scheduling algorithm based on MAB cannot be guaranteed.In addition, model-free-based deep reinforcement learning is also applied to the research of spectrum allocation. Naparstek and Cohen propose a spectrum allocation scheme based on a deep learning framework under the wireless environment in the work of [16]. However, model-free-based deep reinforcement learning has problems of slow online learning speed and bad self-adaption ability.Recently, another kind of model-based reinforcement learning, Monte-Carlo tree search algorithm (MCTS), is applied in the field of resource allocation [17, 18]. The MCTS-based allocation algorithm builds a decision tree to explore the possible solutions by expanding and pruning. Due to the expansion of the tree, the search space becomes tremendous gradually and the calculation scale is unacceptable. If this type of method is applied in IoV directly, the dynamic environment will further cause a large search tree. In addition, due to the neglect of environmental uncertainties, the random strategy adopted by Basic-MCTS in the simulation stage will produce a high variance, which reduces the search efficiency [21].


## 2.1. Spectrum Resource Allocation Based on Traditional Optimization Theory and Game Theory

In order to solve the problem of dynamic allocation of spectrum resources in wireless communications, the traditional methods mainly include the methods based on mathematical optimization [3, 4] and the methods based on game theory [5–7]. For example, Martinovic et al. propose a cognitive radio spectrum allocation method based on integer linear programming in the work of [4], which solves the spectrum allocation problem with interference by using many complex assumptions and constraints. It is difficult or even impossible to find an optimal solution in the real cognitive radio network with the complex environment and dynamic network topology. Although the methods based on mathematical optimization have high solution accuracy, the generalization capability is insufficient.Besides, with the goal of maximizing spectrum utilization, Yi and Cai introduce a spectrum resource allocation method based on auction in the work of [6]. Liu et al. design a dynamic spectrum access method using game theory in the work of [7]. However, these methods are not fit for IoV. The high mobility of vehicles puts forward a strict requirement for the convergence of Nash equilibrium in the game theory. It is hard to reach this equilibrium point.


## 2.2. Spectrum Resource Allocation Based on Swarm Intelligence Optimization

There are many related studies [8–12] based on swarm intelligence optimization in the domain of spectrum allocation. For example, Liu et al. use PSO to solve the allocation of spectrum resources in a centralized way in the work of [12]. However, the iteration of swarm intelligence optimization usually gets stuck in local optimal solutions, which can be far from the global optimal solution [19]. In addition, many swarm intelligence optimization algorithms have a large number of calculations in debugging due to complex parameters.


## 2.3. Spectrum Resource Allocation Based on Machine Learning

In recent years, with the development of statistical learning methods, many studies use machine learning to realize the dynamic spectrum allocation [13]. Among them, reinforcement learning can guide a system agent to learn the unknown environment by trial and error [20]. It can be applied to the spectrum allocation decision.First, the multiarm gambling machine (MAB) not only is an important random decision-making theory in the field of operational research but also belongs to a type of online learning algorithm in reinforcement learning. The task of the agent is to select one arm to pull in each round based on the historical rewards it collected, and the goal is to collect cumulative rewards over multiple rounds as much as possible. In essence, MAB is a way to optimize the reward by balancing exploration and exploitation. Li et al. give a survey of spectrum resource allocation by using MAB in the cognitive radio network in the work of [14]. Zhang et al. formulate and study a multiuser MAB problem that exploits the idea of temporal-spatial spectrum reuse in the cognitive radio network [15]. However, the MAB modeling does not consider the cost of pulling arms in the existing allocation schemes. When MAB is utilized to solve the allocation problem in a centralized way, the scale of the arm increases exponentially with the number of users to be assigned. Therefore, the convergence of the spectrum resource scheduling algorithm based on MAB cannot be guaranteed.In addition, model-free-based deep reinforcement learning is also applied to the research of spectrum allocation. Naparstek and Cohen propose a spectrum allocation scheme based on a deep learning framework under the wireless environment in the work of [16]. However, model-free-based deep reinforcement learning has problems of slow online learning speed and bad self-adaption ability.Recently, another kind of model-based reinforcement learning, Monte-Carlo tree search algorithm (MCTS), is applied in the field of resource allocation [17, 18]. The MCTS-based allocation algorithm builds a decision tree to explore the possible solutions by expanding and pruning. Due to the expansion of the tree, the search space becomes tremendous gradually and the calculation scale is unacceptable. If this type of method is applied in IoV directly, the dynamic environment will further cause a large search tree. In addition, due to the neglect of environmental uncertainties, the random strategy adopted by Basic-MCTS in the simulation stage will produce a high variance, which reduces the search efficiency [21].


## 3. System Scenario and Problem Formalization

In this section, we introduce the system scenario of spectrum allocation in CR-IoV in Section3.1 and give the mathematical formalization of our optimization problem in Section 3.2.


### 3.1. System Scenario

Figure1 shows the system scenario of spectrum allocation in CR-IoV. PUs are the authorized mobile phone users in the current network, and SUs are vehicles equipped with CR modules. When a PU occupies a channel, there is a protection area around the PU (i.e., the red area in Figure 1). Similarly, an interference radius is also generated when the SU occupies a channel (i.e., the green area in Figure 1). Any radiation from SUs falling into the protection area would interfere with the PU.Figure 1
System scenario of spectrum allocation in CR-IoV.In this scenario, our designed allocation algorithm is deployed on the base station. Vehicle nodes equipped with CR modules can sense whether there exist available idle spectrum resources. A vehicle can use the common control channel (CCC) to send a request to the base station to access the channel. The base station collects requests from vehicles centrally and learns a near-optimal policy to allocate available channel resources to cognitive vehicles within the coverage area (i.e., the black solid circle in Figure1). Finally, the base station broadcasts the access confirmation message (i.e., the learned allocation policy) to the vehicles. The vehicle that received the access confirmation message can access the CR-IoV. Instead, the vehicle which has not received the message can continue to propose a new request to enter the next round of allocation.Note that, because IoV is a dynamic network, our designed spectrum resource allocation algorithm must be executed within a defined allocation time window. We assume that the allocation time window for channel allocation isT. After the time window slides, we will refresh and observe the current vehicles which require to access the base station. A large time window cannot meet the real-time requirement of IoV, but a time window that is too small cannot support our algorithm for well operating. In the experiment, we set the size of a time window T to 10 s to handle the dynamic network.


### 3.2. Definitions and Problem Formalization

#### 3.2.1. Definitions

In this paper, we consider spectrum resource allocation in the underlay mode, i.e., each channel can support the parallel transmissions of several access users. Assume that within a base station’s communication coverage, there areN SUs competing for spectrum resources of M channels at time t, and the channels are orthogonal and nonoverlapping. Meanwhile, we assume that there are K PUs as a prerequisite for spectrum allocation in the coverage area, and each PU occupies only one channel for information transmission in the current network. The spectrum resource allocation model consists of a channel availability matrix L, a SU-SU interference constraint matrix C, a channel reward matrix R, and a conflict-free channel assignment matrix A.We define that a PUk1≤k≤K occupying a certain authorized channel m1≤m≤M in CR-IoV has a protection radius R~k,m. Meanwhile, each SU n1≤n≤N has an interference radius R¯n,m on channel m due to its transmit power. We obtain a Euclidean distance DR~k,m,R¯n,m between a PU k and a SU n. When the inequality DR~k,m,R¯n,m−R~k,m≤R¯n,m holds, it means that there exists communication interference between the PU k and SU n.Similarly, we also can obtain a Euclidean distanceDR¯n,m,R¯n′,m between two different SUs n and n′, where R¯n,m and R¯n′,m are the interference radius values of the two SUs n and n′. When DR¯n,m,R¯n′,m−R¯n,m≤R¯n′,m holds, it means that there exists communication interference between the two SUs n and n′. Note that, when there is no communication interference between two users, they can use the same channel for transmissions at the same time; otherwise, they cannot access the same channel at the same time.Next, according to the above descriptions of communication interference between different users, we give the following definitions about our problem.(1) Channel Availability MatrixL. L=ln,m∣ln,m∈0,1N×M is an N×M-dimensional matrix used to describe the channel availability. When ln,m=1, it means channel m is available for SU n, and vice versa. It needs to meet the following two conditions to determine whether channel m is available for SU n. First, SU n cannot use channel m occupied by PU k under the condition DR~k,m,R¯n,m−R~k,m≤R¯n,m. Second, SUs need to compare the interference power they received with the maximum allowable interference level γm on channel m. Channel m is considered to be available to SU n if the following inequality is satisfied:
(1)∑k=1KPm,n,k+Nm≤γm,where Pm,n,k denotes the received power at SU n of a signal transmitted from PU k on channel m and Nm denotes the level of background noise on channel m.(2) SU-SU Interference MatrixC. C=cn,n′,m∣cn,n′,m∈0,1N×N×M is an N×N×M-dimensional matrix used to describe the interference constraint between two different SUs n and n′ on channel m, where cn,n′,m=1 indicates that there exists interference when SUs n and n′ share the channel m for information transmission. Conversely, cn,n′,m=0 indicates that SUs n and n′ can use channel m simultaneously. When n=n′, cn,n′,m=1−ln,m. Meanwhile, the matrix element needs to satisfy the condition cn,n′,m≤ln,m·ln′,m, i.e., the premise for the possibility of interference is that channel m is available to both SUs n and n′.(3) Channel Allocation MatrixA. A=an,man,m∈0,1N×M is an N×M-dimensional matrix used to describe the conflict-free channel allocation for SUs. When an,m=1 holds, it means that channel m is allocated to the SU n, and vice versa. Meanwhile, matrix A must satisfy the interference constraint given by matrix C. That is to say, for two different SUs n and n′, when cn,n′,m=1, the equation an,m·an′,m=0 holds. In addition, we assume that each SU in the allocation can only occupy one channel for information transmission. Therefore, for any two different channels m and m′, the inequality an,m+an,m′≤1 should be satisfied.(4) Channel Reward MatrixR. R=rn,m∣rn,m≥0N×M is an N×M-dimensional matrix used to describe the link rewards for different SUs. Notation rn,m denote the reward obtained by SU n when it occupies channel m of a base station. rn,m is measured by the link capacity. Link capacity is defined as follows:
(2)rn,m=Wm·log21+SINRn,m,where Wm is the bandwidth of channel m and SINRn,m is the signal-to-interference-plus-noise ratio when SU n accesses channel m. The calculation of SINRn,m is shown in
(3)SINRn,m=Pm,nNm+∑q=1,q≠nCountAmPm,q,where we regard the SU and the base station as the transmitting-end and the receiving-end, respectively. Here, Am represents the mth column vectors of matrices A and CountAm denotes the total number of allocated SUs on channel m; Pm,n is the power received by the receiver (base station) from the transmitter n on channel m.


#### 3.2.2. Problem Formalization

From the above definitions, it can be seen that there are more than one channel allocation matrix satisfying the allocation constraints. Therefore, letΛL,C=Agg∈ℕ+ denote the set of all conflict-free channel allocation schemes derived from the current network conditions L and C. Because there are many possible spectrum allocation schemes, choosing different spectrum allocation schemes will generate different total system rewards. The object of spectrum allocation in this paper is to maximize the total network capacity UA,R of the network system. We give the definition of total network capacity as follows:
(4)UA,R=SUM∑m=1MAm∘Rm,where Rm represents the mth column vector of matrix R. Notation ∘ represents the Hadamard product, i.e., multiplication of the elements at the corresponding positions of the two vectors. Am is a 0/1 decision vector of N×1 size, and Rm is an N×1-dimensional reward vector with real numbers. ∑m=1MAm∘Rm is also an N×1-dimensional vector. Notation SUM is the operator that returns the summation of all entries of a matrix.In the IoV, our paper is aimed at obtaining an optimal channel allocation matrixA∗ (i.e., with the equation A∗=argmaxA∈ΛL,CUA,R), which satisfies the above noninterference constraints and solves the problem of low utilization of spectrum resources at the base station side. The combinatorial optimization problem can be formulated as a binary integer linear programming problem (BILP) as follows:
(5)∗maxA,RUA,R=∗maxA,RSUM∑m=1MAm∘Rm(5a)s.t.an,m∈0,1,rn,m≥0,1≤n≤N,1≤m≤M(5b)an,m≤ln,m(5c)an,m·an′,m=0ifcn,n′,m=1(5d)an,m+an,m′≤1(5e)P¯m,nmin≤P¯m,n≤P¯m,nmaxifP¯m,n≠0(5f)∑i=1nPm,k.n≤δm,k,1≤k≤K(5g)Am×RmT≤ϕm.Among these, constraint (5a) gives the value range of the matrix vectors Am and Rm. Constraint (5b) ensures that an allocated channel must be an available channel for SU n. Besides, to protect the communication of each SU from interference by other SUs on channel m, the conflict-free channel allocation matrix should satisfy constraint (5c). Constraint (5d) indicates that each SU can only occupy one channel for information transmission. In constraint (5e), P¯m,n represents the transmission power of SU n on channel m; P¯m,nmin and P¯m,nmax represent the maximum and minimum allowable transmission power of SU n on channel m, respectively. This constraint defines the upper and lower bounds for the transmitted power of the SU. In other words, the transmission power of the SU should meet two constraints: on the one hand, it should not interfere with the normal use of the PU; on the other hand, it should meet the minimum allowable SINR required for transmissions. In the constraint (5f), Pm,k,n represents the interference power of SU n received by PU k on channel m, and δm,k represents the maximum allowable interference power of PU k on channel m. For any PU k, the total received interference power on the channel m must be kept below the maximum allowable interference threshold, i.e., the PU is not interfered by SUs on the channel. In the constraint (5g), ϕm represents the available bandwidth of channel m, and RmT represents the transposed vector of Rm. This constraint ensures that the total network capacity of channel m should be less than or equal to its available bandwidth.


## 3.1. System Scenario

Figure1 shows the system scenario of spectrum allocation in CR-IoV. PUs are the authorized mobile phone users in the current network, and SUs are vehicles equipped with CR modules. When a PU occupies a channel, there is a protection area around the PU (i.e., the red area in Figure 1). Similarly, an interference radius is also generated when the SU occupies a channel (i.e., the green area in Figure 1). Any radiation from SUs falling into the protection area would interfere with the PU.Figure 1
System scenario of spectrum allocation in CR-IoV.In this scenario, our designed allocation algorithm is deployed on the base station. Vehicle nodes equipped with CR modules can sense whether there exist available idle spectrum resources. A vehicle can use the common control channel (CCC) to send a request to the base station to access the channel. The base station collects requests from vehicles centrally and learns a near-optimal policy to allocate available channel resources to cognitive vehicles within the coverage area (i.e., the black solid circle in Figure1). Finally, the base station broadcasts the access confirmation message (i.e., the learned allocation policy) to the vehicles. The vehicle that received the access confirmation message can access the CR-IoV. Instead, the vehicle which has not received the message can continue to propose a new request to enter the next round of allocation.Note that, because IoV is a dynamic network, our designed spectrum resource allocation algorithm must be executed within a defined allocation time window. We assume that the allocation time window for channel allocation isT. After the time window slides, we will refresh and observe the current vehicles which require to access the base station. A large time window cannot meet the real-time requirement of IoV, but a time window that is too small cannot support our algorithm for well operating. In the experiment, we set the size of a time window T to 10 s to handle the dynamic network.


## 3.2. Definitions and Problem Formalization

### 3.2.1. Definitions

In this paper, we consider spectrum resource allocation in the underlay mode, i.e., each channel can support the parallel transmissions of several access users. Assume that within a base station’s communication coverage, there areN SUs competing for spectrum resources of M channels at time t, and the channels are orthogonal and nonoverlapping. Meanwhile, we assume that there are K PUs as a prerequisite for spectrum allocation in the coverage area, and each PU occupies only one channel for information transmission in the current network. The spectrum resource allocation model consists of a channel availability matrix L, a SU-SU interference constraint matrix C, a channel reward matrix R, and a conflict-free channel assignment matrix A.We define that a PUk1≤k≤K occupying a certain authorized channel m1≤m≤M in CR-IoV has a protection radius R~k,m. Meanwhile, each SU n1≤n≤N has an interference radius R¯n,m on channel m due to its transmit power. We obtain a Euclidean distance DR~k,m,R¯n,m between a PU k and a SU n. When the inequality DR~k,m,R¯n,m−R~k,m≤R¯n,m holds, it means that there exists communication interference between the PU k and SU n.Similarly, we also can obtain a Euclidean distanceDR¯n,m,R¯n′,m between two different SUs n and n′, where R¯n,m and R¯n′,m are the interference radius values of the two SUs n and n′. When DR¯n,m,R¯n′,m−R¯n,m≤R¯n′,m holds, it means that there exists communication interference between the two SUs n and n′. Note that, when there is no communication interference between two users, they can use the same channel for transmissions at the same time; otherwise, they cannot access the same channel at the same time.Next, according to the above descriptions of communication interference between different users, we give the following definitions about our problem.(1) Channel Availability MatrixL. L=ln,m∣ln,m∈0,1N×M is an N×M-dimensional matrix used to describe the channel availability. When ln,m=1, it means channel m is available for SU n, and vice versa. It needs to meet the following two conditions to determine whether channel m is available for SU n. First, SU n cannot use channel m occupied by PU k under the condition DR~k,m,R¯n,m−R~k,m≤R¯n,m. Second, SUs need to compare the interference power they received with the maximum allowable interference level γm on channel m. Channel m is considered to be available to SU n if the following inequality is satisfied:
(1)∑k=1KPm,n,k+Nm≤γm,where Pm,n,k denotes the received power at SU n of a signal transmitted from PU k on channel m and Nm denotes the level of background noise on channel m.(2) SU-SU Interference MatrixC. C=cn,n′,m∣cn,n′,m∈0,1N×N×M is an N×N×M-dimensional matrix used to describe the interference constraint between two different SUs n and n′ on channel m, where cn,n′,m=1 indicates that there exists interference when SUs n and n′ share the channel m for information transmission. Conversely, cn,n′,m=0 indicates that SUs n and n′ can use channel m simultaneously. When n=n′, cn,n′,m=1−ln,m. Meanwhile, the matrix element needs to satisfy the condition cn,n′,m≤ln,m·ln′,m, i.e., the premise for the possibility of interference is that channel m is available to both SUs n and n′.(3) Channel Allocation MatrixA. A=an,man,m∈0,1N×M is an N×M-dimensional matrix used to describe the conflict-free channel allocation for SUs. When an,m=1 holds, it means that channel m is allocated to the SU n, and vice versa. Meanwhile, matrix A must satisfy the interference constraint given by matrix C. That is to say, for two different SUs n and n′, when cn,n′,m=1, the equation an,m·an′,m=0 holds. In addition, we assume that each SU in the allocation can only occupy one channel for information transmission. Therefore, for any two different channels m and m′, the inequality an,m+an,m′≤1 should be satisfied.(4) Channel Reward MatrixR. R=rn,m∣rn,m≥0N×M is an N×M-dimensional matrix used to describe the link rewards for different SUs. Notation rn,m denote the reward obtained by SU n when it occupies channel m of a base station. rn,m is measured by the link capacity. Link capacity is defined as follows:
(2)rn,m=Wm·log21+SINRn,m,where Wm is the bandwidth of channel m and SINRn,m is the signal-to-interference-plus-noise ratio when SU n accesses channel m. The calculation of SINRn,m is shown in
(3)SINRn,m=Pm,nNm+∑q=1,q≠nCountAmPm,q,where we regard the SU and the base station as the transmitting-end and the receiving-end, respectively. Here, Am represents the mth column vectors of matrices A and CountAm denotes the total number of allocated SUs on channel m; Pm,n is the power received by the receiver (base station) from the transmitter n on channel m.


### 3.2.2. Problem Formalization

From the above definitions, it can be seen that there are more than one channel allocation matrix satisfying the allocation constraints. Therefore, letΛL,C=Agg∈ℕ+ denote the set of all conflict-free channel allocation schemes derived from the current network conditions L and C. Because there are many possible spectrum allocation schemes, choosing different spectrum allocation schemes will generate different total system rewards. The object of spectrum allocation in this paper is to maximize the total network capacity UA,R of the network system. We give the definition of total network capacity as follows:
(4)UA,R=SUM∑m=1MAm∘Rm,where Rm represents the mth column vector of matrix R. Notation ∘ represents the Hadamard product, i.e., multiplication of the elements at the corresponding positions of the two vectors. Am is a 0/1 decision vector of N×1 size, and Rm is an N×1-dimensional reward vector with real numbers. ∑m=1MAm∘Rm is also an N×1-dimensional vector. Notation SUM is the operator that returns the summation of all entries of a matrix.In the IoV, our paper is aimed at obtaining an optimal channel allocation matrixA∗ (i.e., with the equation A∗=argmaxA∈ΛL,CUA,R), which satisfies the above noninterference constraints and solves the problem of low utilization of spectrum resources at the base station side. The combinatorial optimization problem can be formulated as a binary integer linear programming problem (BILP) as follows:
(5)∗maxA,RUA,R=∗maxA,RSUM∑m=1MAm∘Rm(5a)s.t.an,m∈0,1,rn,m≥0,1≤n≤N,1≤m≤M(5b)an,m≤ln,m(5c)an,m·an′,m=0ifcn,n′,m=1(5d)an,m+an,m′≤1(5e)P¯m,nmin≤P¯m,n≤P¯m,nmaxifP¯m,n≠0(5f)∑i=1nPm,k.n≤δm,k,1≤k≤K(5g)Am×RmT≤ϕm.Among these, constraint (5a) gives the value range of the matrix vectors Am and Rm. Constraint (5b) ensures that an allocated channel must be an available channel for SU n. Besides, to protect the communication of each SU from interference by other SUs on channel m, the conflict-free channel allocation matrix should satisfy constraint (5c). Constraint (5d) indicates that each SU can only occupy one channel for information transmission. In constraint (5e), P¯m,n represents the transmission power of SU n on channel m; P¯m,nmin and P¯m,nmax represent the maximum and minimum allowable transmission power of SU n on channel m, respectively. This constraint defines the upper and lower bounds for the transmitted power of the SU. In other words, the transmission power of the SU should meet two constraints: on the one hand, it should not interfere with the normal use of the PU; on the other hand, it should meet the minimum allowable SINR required for transmissions. In the constraint (5f), Pm,k,n represents the interference power of SU n received by PU k on channel m, and δm,k represents the maximum allowable interference power of PU k on channel m. For any PU k, the total received interference power on the channel m must be kept below the maximum allowable interference threshold, i.e., the PU is not interfered by SUs on the channel. In the constraint (5g), ϕm represents the available bandwidth of channel m, and RmT represents the transposed vector of Rm. This constraint ensures that the total network capacity of channel m should be less than or equal to its available bandwidth.


## 3.2.1. Definitions

In this paper, we consider spectrum resource allocation in the underlay mode, i.e., each channel can support the parallel transmissions of several access users. Assume that within a base station’s communication coverage, there areN SUs competing for spectrum resources of M channels at time t, and the channels are orthogonal and nonoverlapping. Meanwhile, we assume that there are K PUs as a prerequisite for spectrum allocation in the coverage area, and each PU occupies only one channel for information transmission in the current network. The spectrum resource allocation model consists of a channel availability matrix L, a SU-SU interference constraint matrix C, a channel reward matrix R, and a conflict-free channel assignment matrix A.We define that a PUk1≤k≤K occupying a certain authorized channel m1≤m≤M in CR-IoV has a protection radius R~k,m. Meanwhile, each SU n1≤n≤N has an interference radius R¯n,m on channel m due to its transmit power. We obtain a Euclidean distance DR~k,m,R¯n,m between a PU k and a SU n. When the inequality DR~k,m,R¯n,m−R~k,m≤R¯n,m holds, it means that there exists communication interference between the PU k and SU n.Similarly, we also can obtain a Euclidean distanceDR¯n,m,R¯n′,m between two different SUs n and n′, where R¯n,m and R¯n′,m are the interference radius values of the two SUs n and n′. When DR¯n,m,R¯n′,m−R¯n,m≤R¯n′,m holds, it means that there exists communication interference between the two SUs n and n′. Note that, when there is no communication interference between two users, they can use the same channel for transmissions at the same time; otherwise, they cannot access the same channel at the same time.Next, according to the above descriptions of communication interference between different users, we give the following definitions about our problem.(1) Channel Availability MatrixL. L=ln,m∣ln,m∈0,1N×M is an N×M-dimensional matrix used to describe the channel availability. When ln,m=1, it means channel m is available for SU n, and vice versa. It needs to meet the following two conditions to determine whether channel m is available for SU n. First, SU n cannot use channel m occupied by PU k under the condition DR~k,m,R¯n,m−R~k,m≤R¯n,m. Second, SUs need to compare the interference power they received with the maximum allowable interference level γm on channel m. Channel m is considered to be available to SU n if the following inequality is satisfied:
(1)∑k=1KPm,n,k+Nm≤γm,where Pm,n,k denotes the received power at SU n of a signal transmitted from PU k on channel m and Nm denotes the level of background noise on channel m.(2) SU-SU Interference MatrixC. C=cn,n′,m∣cn,n′,m∈0,1N×N×M is an N×N×M-dimensional matrix used to describe the interference constraint between two different SUs n and n′ on channel m, where cn,n′,m=1 indicates that there exists interference when SUs n and n′ share the channel m for information transmission. Conversely, cn,n′,m=0 indicates that SUs n and n′ can use channel m simultaneously. When n=n′, cn,n′,m=1−ln,m. Meanwhile, the matrix element needs to satisfy the condition cn,n′,m≤ln,m·ln′,m, i.e., the premise for the possibility of interference is that channel m is available to both SUs n and n′.(3) Channel Allocation MatrixA. A=an,man,m∈0,1N×M is an N×M-dimensional matrix used to describe the conflict-free channel allocation for SUs. When an,m=1 holds, it means that channel m is allocated to the SU n, and vice versa. Meanwhile, matrix A must satisfy the interference constraint given by matrix C. That is to say, for two different SUs n and n′, when cn,n′,m=1, the equation an,m·an′,m=0 holds. In addition, we assume that each SU in the allocation can only occupy one channel for information transmission. Therefore, for any two different channels m and m′, the inequality an,m+an,m′≤1 should be satisfied.(4) Channel Reward MatrixR. R=rn,m∣rn,m≥0N×M is an N×M-dimensional matrix used to describe the link rewards for different SUs. Notation rn,m denote the reward obtained by SU n when it occupies channel m of a base station. rn,m is measured by the link capacity. Link capacity is defined as follows:
(2)rn,m=Wm·log21+SINRn,m,where Wm is the bandwidth of channel m and SINRn,m is the signal-to-interference-plus-noise ratio when SU n accesses channel m. The calculation of SINRn,m is shown in
(3)SINRn,m=Pm,nNm+∑q=1,q≠nCountAmPm,q,where we regard the SU and the base station as the transmitting-end and the receiving-end, respectively. Here, Am represents the mth column vectors of matrices A and CountAm denotes the total number of allocated SUs on channel m; Pm,n is the power received by the receiver (base station) from the transmitter n on channel m.


## 3.2.2. Problem Formalization

From the above definitions, it can be seen that there are more than one channel allocation matrix satisfying the allocation constraints. Therefore, letΛL,C=Agg∈ℕ+ denote the set of all conflict-free channel allocation schemes derived from the current network conditions L and C. Because there are many possible spectrum allocation schemes, choosing different spectrum allocation schemes will generate different total system rewards. The object of spectrum allocation in this paper is to maximize the total network capacity UA,R of the network system. We give the definition of total network capacity as follows:
(4)UA,R=SUM∑m=1MAm∘Rm,where Rm represents the mth column vector of matrix R. Notation ∘ represents the Hadamard product, i.e., multiplication of the elements at the corresponding positions of the two vectors. Am is a 0/1 decision vector of N×1 size, and Rm is an N×1-dimensional reward vector with real numbers. ∑m=1MAm∘Rm is also an N×1-dimensional vector. Notation SUM is the operator that returns the summation of all entries of a matrix.In the IoV, our paper is aimed at obtaining an optimal channel allocation matrixA∗ (i.e., with the equation A∗=argmaxA∈ΛL,CUA,R), which satisfies the above noninterference constraints and solves the problem of low utilization of spectrum resources at the base station side. The combinatorial optimization problem can be formulated as a binary integer linear programming problem (BILP) as follows:
(5)∗maxA,RUA,R=∗maxA,RSUM∑m=1MAm∘Rm(5a)s.t.an,m∈0,1,rn,m≥0,1≤n≤N,1≤m≤M(5b)an,m≤ln,m(5c)an,m·an′,m=0ifcn,n′,m=1(5d)an,m+an,m′≤1(5e)P¯m,nmin≤P¯m,n≤P¯m,nmaxifP¯m,n≠0(5f)∑i=1nPm,k.n≤δm,k,1≤k≤K(5g)Am×RmT≤ϕm.Among these, constraint (5a) gives the value range of the matrix vectors Am and Rm. Constraint (5b) ensures that an allocated channel must be an available channel for SU n. Besides, to protect the communication of each SU from interference by other SUs on channel m, the conflict-free channel allocation matrix should satisfy constraint (5c). Constraint (5d) indicates that each SU can only occupy one channel for information transmission. In constraint (5e), P¯m,n represents the transmission power of SU n on channel m; P¯m,nmin and P¯m,nmax represent the maximum and minimum allowable transmission power of SU n on channel m, respectively. This constraint defines the upper and lower bounds for the transmitted power of the SU. In other words, the transmission power of the SU should meet two constraints: on the one hand, it should not interfere with the normal use of the PU; on the other hand, it should meet the minimum allowable SINR required for transmissions. In the constraint (5f), Pm,k,n represents the interference power of SU n received by PU k on channel m, and δm,k represents the maximum allowable interference power of PU k on channel m. For any PU k, the total received interference power on the channel m must be kept below the maximum allowable interference threshold, i.e., the PU is not interfered by SUs on the channel. In the constraint (5g), ϕm represents the available bandwidth of channel m, and RmT represents the transposed vector of Rm. This constraint ensures that the total network capacity of channel m should be less than or equal to its available bandwidth.


## 4. Priority Assignment Based on Vehicle Traveling State

In Section4.1, we describe the problem of priority assignment. In Section 4.2, we give detailed definition of priority.


### 4.1. Problem Description

In CR-IoV, when the system carries out the spectrum allocation, the current state of vehicle traveling should be considered. For example, if a vehicle is about to leave the communication range of the current base station, it should be assigned to a low priority for spectrum allocation.The traveling state of a vehicle at the current moment mainly includes direction, speed, acceleration, and GPS coordinates. Besides, the traveling state also should consider the degree of geographical dispersion among vehicles and the communication capability of a vehicle.The current state information of each vehicle is collected by the current communicating base station. Then, we carry out priority evaluation for different cognitive vehicle users to distinguish the priority weights for spectrum allocation.For a SUn who initiates a service request, from the perspectives of the global state and local state, a comprehensive priority evaluation score Priorityscoren is constructed by defining a vehicle traveling evaluation score Travelingscoren and a network utility score Utilityn for the SU.


### 4.2. Priority Definition Based on Vehicle Traveling State

Definition 1 (vehicle traveling evaluation score).
According to the GPS coordinates, speed, and acceleration, we define a vehicle traveling evaluation scoreTravelingscoren for a cognitive vehicle n as
(6)Travelingscoren=1+cosθn4·vmax−vnvmax−vmin+11+ean,where θn denotes the angle between the current driving direction and the link connecting the vehicle’s position with the base station’s position. Notation an denotes the acceleration of the vehicle n. Notation vn denotes the speed of the vehicle n. Notations vmax and vmin represent the maximum and minimum values of the driving speed. We assume that the vehicle speed is within the value interval vmin,vmax.Obviously, a relatively large angleθn indicates that vehicle n will travel out of the coverage range of the base station in the future. Therefore, vehicle n with large θn should be given a relatively low spectrum allocation priority. We use formula 1+cosθn/2 to normalize the different weights of the angle θn to the value interval 0,1. In addition, a vehicle with high driving speed will quickly travel out of the coverage range of the base station in the future. Therefore, it should be given a relatively low spectrum allocation priority. The normalized formula vmax−vn/vmax−vmin is used to describe the influence of vehicle driving speed on the priority. Similarly, a vehicle with high acceleration should be given a relatively low spectrum allocation priority. To normalize the value interval to 0,1, formula 1/1+ean is used to describe the influence of vehicle driving acceleration on the priority. Finally, to constrain the value of Travelingscoren within the value interval 0,1, we use constant coefficient 1/2 to obtain the right side of Equation (6).Definition 2 (network utility score).
We define a network utility score to evaluate the communication capability of cognitive vehicles. For cognitive vehiclen, its network utility score is defined as follows:
(7)Utilityn=log21+SNRn·∑1≤n,n′≤N,n′≠nDispersionn,n′N−1,where SNRn denotes the signal-to-noise ratio of the user n to receive the signal from the base station. Formula ∑1≤n,n′≤N,n′≠nDispersionn,n′ represents the global dispersion of user n within the coverage area of the base station.For the numerator of Equation (7), we give the following detailed definition. Dispersionn,n′ between two SUs n and n′ is defined as follows:
(8)Dispersionn,n′=1,Dn,n′>εn,0,others,where εn is a dispersion threshold and notation Dn,n′ represents the average dispersion time between two SUs n and n′. First, the threshold εn is obtained by taking the median value of Dn,n′∣1≤n′≤N,n′≠n. Second, the average dispersion time Dn,n′ is defined as
(9)Dn,n′=∫0Tβn,n′tdtτn,n′.In Equation (9), the communication dispersion state between two vehicles n and n′ is defined as βn,n′t. When there exists communication interference between vehicle n and n′, we let βn,n′t=0. It means that the two are in an “encounter” state. On the contrary, when βn,n′t=1, it means that the two are in a “scattered” state. Thus, in a time window T, the numerator of Equation (9) represents the total dispersion time between user n and user n′. Besides, τn,n′ in the denominator denotes the total number of times that user n and user n′ are in the “scattered” state in time window T. Obviously, the higher the value of Dn,n′, the longer the time that the two users n and n′ are in the “scattered” state. Thus, we conclude that the higher the global dispersion ∑1≤n,n′≤N,n′≠nDispersionn,n′, the greater the probability that vehicle n has the chance to reuse the channel, which further leads to a high network utility.To sum up, a vehicle with a large network utility score in Equation (7) means that its global communication capability is strong, so the vehicle should be given a high spectrum allocation priority.Definition 3 (comprehensive priority evaluation score).
According to the vehicle traveling evaluation scoreTravelingscoren and network utility score Utilityn, we construct a comprehensive priority evaluation score Priorityscoren for the cognitive vehicle n below:
(10)Priorityscoren=Travelingscoren·Utilityn.
For a cognitive vehicle who requests to access the base station, the base station calculates the priority score by collecting the vehicle’s information. We rank all the scores from the largest to the smallest. Therefore, we can obtain a priority order listPriorityscore_list for all the cognitive vehicles in the current allocation task, which will be used in Section 5.


## 4.1. Problem Description

In CR-IoV, when the system carries out the spectrum allocation, the current state of vehicle traveling should be considered. For example, if a vehicle is about to leave the communication range of the current base station, it should be assigned to a low priority for spectrum allocation.The traveling state of a vehicle at the current moment mainly includes direction, speed, acceleration, and GPS coordinates. Besides, the traveling state also should consider the degree of geographical dispersion among vehicles and the communication capability of a vehicle.The current state information of each vehicle is collected by the current communicating base station. Then, we carry out priority evaluation for different cognitive vehicle users to distinguish the priority weights for spectrum allocation.For a SUn who initiates a service request, from the perspectives of the global state and local state, a comprehensive priority evaluation score Priorityscoren is constructed by defining a vehicle traveling evaluation score Travelingscoren and a network utility score Utilityn for the SU.


## 4.2. Priority Definition Based on Vehicle Traveling State

Definition 1 (vehicle traveling evaluation score).
According to the GPS coordinates, speed, and acceleration, we define a vehicle traveling evaluation scoreTravelingscoren for a cognitive vehicle n as
(6)Travelingscoren=1+cosθn4·vmax−vnvmax−vmin+11+ean,where θn denotes the angle between the current driving direction and the link connecting the vehicle’s position with the base station’s position. Notation an denotes the acceleration of the vehicle n. Notation vn denotes the speed of the vehicle n. Notations vmax and vmin represent the maximum and minimum values of the driving speed. We assume that the vehicle speed is within the value interval vmin,vmax.Obviously, a relatively large angleθn indicates that vehicle n will travel out of the coverage range of the base station in the future. Therefore, vehicle n with large θn should be given a relatively low spectrum allocation priority. We use formula 1+cosθn/2 to normalize the different weights of the angle θn to the value interval 0,1. In addition, a vehicle with high driving speed will quickly travel out of the coverage range of the base station in the future. Therefore, it should be given a relatively low spectrum allocation priority. The normalized formula vmax−vn/vmax−vmin is used to describe the influence of vehicle driving speed on the priority. Similarly, a vehicle with high acceleration should be given a relatively low spectrum allocation priority. To normalize the value interval to 0,1, formula 1/1+ean is used to describe the influence of vehicle driving acceleration on the priority. Finally, to constrain the value of Travelingscoren within the value interval 0,1, we use constant coefficient 1/2 to obtain the right side of Equation (6).Definition 2 (network utility score).
We define a network utility score to evaluate the communication capability of cognitive vehicles. For cognitive vehiclen, its network utility score is defined as follows:
(7)Utilityn=log21+SNRn·∑1≤n,n′≤N,n′≠nDispersionn,n′N−1,where SNRn denotes the signal-to-noise ratio of the user n to receive the signal from the base station. Formula ∑1≤n,n′≤N,n′≠nDispersionn,n′ represents the global dispersion of user n within the coverage area of the base station.For the numerator of Equation (7), we give the following detailed definition. Dispersionn,n′ between two SUs n and n′ is defined as follows:
(8)Dispersionn,n′=1,Dn,n′>εn,0,others,where εn is a dispersion threshold and notation Dn,n′ represents the average dispersion time between two SUs n and n′. First, the threshold εn is obtained by taking the median value of Dn,n′∣1≤n′≤N,n′≠n. Second, the average dispersion time Dn,n′ is defined as
(9)Dn,n′=∫0Tβn,n′tdtτn,n′.In Equation (9), the communication dispersion state between two vehicles n and n′ is defined as βn,n′t. When there exists communication interference between vehicle n and n′, we let βn,n′t=0. It means that the two are in an “encounter” state. On the contrary, when βn,n′t=1, it means that the two are in a “scattered” state. Thus, in a time window T, the numerator of Equation (9) represents the total dispersion time between user n and user n′. Besides, τn,n′ in the denominator denotes the total number of times that user n and user n′ are in the “scattered” state in time window T. Obviously, the higher the value of Dn,n′, the longer the time that the two users n and n′ are in the “scattered” state. Thus, we conclude that the higher the global dispersion ∑1≤n,n′≤N,n′≠nDispersionn,n′, the greater the probability that vehicle n has the chance to reuse the channel, which further leads to a high network utility.To sum up, a vehicle with a large network utility score in Equation (7) means that its global communication capability is strong, so the vehicle should be given a high spectrum allocation priority.Definition 3 (comprehensive priority evaluation score).
According to the vehicle traveling evaluation scoreTravelingscoren and network utility score Utilityn, we construct a comprehensive priority evaluation score Priorityscoren for the cognitive vehicle n below:
(10)Priorityscoren=Travelingscoren·Utilityn.
For a cognitive vehicle who requests to access the base station, the base station calculates the priority score by collecting the vehicle’s information. We rank all the scores from the largest to the smallest. Therefore, we can obtain a priority order listPriorityscore_list for all the cognitive vehicles in the current allocation task, which will be used in Section 5.


## 5. Finder-MCTS Algorithm for Cognitive IoV Spectrum Allocation

In Introduction, we mentioned that our paper will use MCTS to solve the problem of efficient spectrum allocation for CR-IoV. MCTS is a classic reinforcement learning algorithm based on tree search. To distinguish it from the method proposed in our paper, we call the classic MCTS as Basic-MCTS. The Basic-MCTS offers a concise computation framework by recursively using a tree policy to expand the search tree towards high-reward nodes and a default policy to perform the simulations for updating the estimated rewards and other statistics [22]. However, due to the continuous expansion of search actions, the search scale of Basic-MCTS is often very large, which greatly affects its search speed. In addition, due to the neglect of environmental uncertainties, the random strategy adopted by Basic-MCTS in the simulation stage will produce a high variance, which reduces the search effect of Basic-MCTS.To improve the search speed and obtain a near-optimal solution, we propose an algorithm named Finder-MCTS in this section. First, we construct a search tree vertically according to the comprehensive priority evaluation score defined in Definition3. Meanwhile, the constraints defined in Section 3.2 are also considered to reduce the search scale of the tree horizontally. Second, the uncertainty of the SUs’ spectrum occupation activities is included in the simulation strategy. We give the bias estimation of reward in different scenarios in the simulation stage so as to approximate the real environment and accelerate the convergence of tree search.Thus, in Finder-MCTS, the first step is to use the Markov decision process (MDP) to construct the Monte-Carlo tree computation framework (Section5.1). Then, with respect to the state prediction, we give a DNN-based environment state predictor (ESP) (Section 5.2). Finally, we describe the detailed steps of the Finder-MCTS algorithm (Section 5.3).


### 5.1. Finder-MCTS’ Computation Framework

The problems solved by the MCTS are commonly formalized by the Markov decision process (MDP), in which we take the base station as the spectrum scheduling agent and use the link capacity formulated in Equation (2) as the value of the reward Q when a SU occupies a channel. Let S and A denote the MDP state space and action space, respectively. F:S×A⟶S denotes the MDP transition function from a state-action pair to the next state. The state transition function fESP is given by a deep neural network (DNN) simulator in Section 5.2. The definitions of the MDP state space and action space are described as follows:
(11)S=svsv,φv,ξv,(12)A=am∣1≤m≤M.In Equation (11), the MDP state is composed of two parts: λv denotes a vector of remaining bandwidth of M channels under the base station, with sv=λv=λ¯1,⋯,λ¯m,⋯,λ¯Mv; λ¯m denotes the remaining bandwidth of mth channel. φv denotes the number of service requests to be allocated. ξv describes the total bandwidth requests of all φv cognitive vehicles. In addition, in Equation (12), the action space is a set composed of whether the number of M channels are allocated, in which the action am denotes that the agent allocates the channel m to a vehicle that enters into the priority-based allocation sequence and is ready to be scheduled by the base station currently.A Monte-Carlo search tree consists of nodes and edges. A nodev is a tree node that corresponds to the MDP statesv, and the edge connecting a parent node and a child node in the tree represents an action that causes the state transition. Each node v in the tree holds a node state, which contains three types of statistics: visit count (N¯v), MDP state sv, and cumulative reward (Qv) received by node v.The specific search steps are shown in Figure2.
(1)
Create a root node of the search tree and initialize the node state. Assume that the root node is denoted byv and the node state is N¯v,sv,Qv(2)
Allocate the spectrum resources for vehicles according to the priority order listPriorityscore_list defined in Definition 3, and extend the child node while updating the node state. Each layer’s tree expansion represents the spectrum allocation for a vehicle, and each allocation process involves many iterations. Take the root node v in Figure 2 as an example. When the channel assignment action of vehicle ID3 is a1, the search tree extends down to the child node v′ and update the node state through iterative calculation (i.e., sv′=fESPsv,a1)(3)
When the tree expansion reaches the termination condition of iteration (i.e., the second users or the available spectrum resources are all allocated), an optimal channel allocation matrixA∗ in the current allocation period is returned. For example, assume that when reaching the node v′′′ in Figure 2, the iteration ends. The black arrow lines direct an allocation path v⟶v′⟶v′′⟶v′′′. Then, the corresponding actions constitute a feasible allocation policy set a1,a5,a1, which can be converted to a channel allocation matrix AN×M as an outputFigure 2
An example of search steps in Finder-MCTS.


### 5.2. DNN-Based Environmental State Predictor (ESP)

Due to the uncertainty of the PUs’ spectrum occupancy activities, when the tree is expanded from one node to the next in Section5.1, the expansion will be not stable, i.e., given a state and an action, the next state is uncertain. This uncertainty is caused by the unknown environment of IoV. Therefore, to limit the expansion scale of the MCTS tree horizontally and speed up the search, it is necessary to gradually learn to approach the real environment of IoV when doing spectrum allocation. This section presents an offline environment state predictor (named ESP) based on a deep neural network (DNN).Note that, to obtain the ESP, enough training data are needed. Thus, first during the cold start phase of Finder-MCTS (i.e., the algorithm just starts running), we do not rely on ESP. This does not affect the channel allocation solution of Finder-MCTS. After a period of time in the cold start phase, our base station can obtain and cumulate large numbers of “state-action transition pairs.” Subsequently, we input these “state-action transition pairs” into ESP continuously as the training data to obtain a state transition functionfESP, which is an offline training process. Once we have fESP, the Finder-MCTS could converge fast due to the reduction in branching. The above training is done by DNN.The network structure of DNN consists of one input layer, three hidden layers, and one output layer. In this paper, we set the learning rate of DNN to 0.05 and the activation function of DNN is the rectified linear unit function (ReLU). To optimize the neural network parameters, we use the minibatch gradient descent method [23]. In the DNN, the training label is the state sv′, which is the state of the corresponding expansion child node v′ of node v. ESP is used to obtain the prediction state s^v′. The loss function of ESP is
(13)lossESP=1B∑B∥sv′−s^v′∥2,where B represents the batch size of minibatch gradient descent. In the experiment, we set B=64, indicating that 64 samples are selected in each iteration. Notation ·2 represents the L2 norm. When lossESP converges, we let the DNN network parameter wESP update.After we obtain the ESP function, based on the selected actionam and MDP state sv, ESP can give the MDP state of its expanded node s^v′,
(14)s^v′=fESPsv,am∣wESP.


### 5.3. Finder-MCTS Algorithm Based on Action Space Pruning and Scenario Simulation

Finder-MCTS requires to execute the following four steps: selection, expansion, simulation, and backpropagation iteratively to complete a computation process, which is shown in Figure3. In Figure 3, the black circles indicate the nodes involved in each step and the red arrow lines indicate the actions corresponding to each step. In subfigure (c), the policy usually refers to the random selection action extended at each step of the simulation process. We usually call step (a) selection and step (b) expansion together as the tree policy. Specifically, the detailed procedures and descriptions are given in the following steps (a)–(d) and in Figure 4.
(a)
Selection. Each iteration starts from the root node. When the algorithm has to choose to which child node it will descend, it tries to find a good balance between exploitation and exploration. We use the upper confidence bound for tree (UCT) [24] to recursively select child nodes. The selection criterion of the optimal child node is
(15)argmaxv′∈childvQv′N¯v′+c·lnN¯vN¯v′,where c≥0 is a weight coefficient used to adjust the exploitation and exploration. We set c=0.8 in the experiment through many tests. Notation childv represents the set of child nodes with v as the parent in the tree. N¯v′ and N¯v represent the total number of times that the child node v′ and its parent node v have been visited iteratively. Qv′ represents the cumulative reward obtained by node v′. Note that the selected child node should be expandable (i.e., have unvisited child node) and represent a nonterminal state. Next, the algorithm treats the child node with the largest value of UCT as the current node for the next expansion.(b)
Constraint-Oriented Expansion. Finder-MCTS judges whether the number of visits of the current node is 0. If visit count N¯=0, the algorithm goes to step (c) directly. If the visit count N¯≠0, the algorithm enumerates the available actions. However, if it is just a simple enumeration, the number of available actions in the next layer is M. As the tree expands, a huge search tree will be built. The computational complexity grows geometrically with the number of SUs to be allocated. Thus, here, we give the constraint-oriented expansion.Figure 3
An iterative computation process of Finder-MCTS.Figure 4
The flow chart of Finder-MCTS.In the constraint-oriented expansion, we prune the action space according to the constraint conditions defined in Section3.2 so as to obtain all available actions from the current node. And then, add new nodes to expand the tree and let the current node be a new child node which is randomly selected after expansion.Specifically, we useAn,v to represent the set of available actions starting from the node v, which is used for the next round of channel allocation for the nth SU. That is to say, An,v is an interference-free action space of a SU. The detailed implementation steps of the constraint-oriented expansion are described in Algorithm 1.In Algorithm1, we use three main steps to perform action pruning. First, considering the channel availability, we introduce the channel availability matrix L to prune the set of actions. We map the elements of ln,m=1 in the channel availability matrix for vehicle n to the available action set (Lines 2-6 in Algorithm 1). Second, considering that the vehicle IDn currently to be allocated should not share the same channel with a vehicle having communication interference, we introduce the SU-SU interference matrix C for the tree pruning. The algorithm traverses the elements in the channel allocation matrix A and makes a judgement on whether an′,m=1 and cn,n′,m=1 hold at the same time. If they hold at the same time, am is removed from the action set (Lines 7-15 in Algorithm 1). Next, in each iteration, the algorithm needs to make a judgement on whether constraint (1) and constraints (5a)–(5g) hold. If the available channel m for the vehicle currently to be allocated does not satisfy these constraints, action am needs to be removed from the set of actions (Lines 16-20 in Algorithm 1). Finally, if An,v=∅, the algorithm will skip the current allocation and wait for the next round of allocation (Lines 21-23 in Algorithm 1).
(c)
Simulation Based on Different Scenarios. From the above step (b), we know that if the visit count of the current node is zero, we will perform a simulation from the current node (i.e., the newly expanded node, denoted by v~) to the terminal node (denoted by v~Δ). Here, the terminal node refers to the node that the descending arrives at when the SUs or the available channel resources have been all allocated. Usually, the simulation uses a random search strategy to generate a reward Qv~Δ at the final leaf node v~Δ. However, the time-varying property of PUs’ spectrum occupancy activities makes the actual available spectrum resources uncertain. This uncertainty will have potential impacts on the reward evaluation for the SU to be allocated in IoV.Algorithm 1: Constraint-oriented expansion for vehicle IDn.
Input:L - channel availability matrixC - SU-SU interference constraint matrixA - channel allocation matrixγm - the maximum allowable interference level of channel mϕm - the available bandwidth of channel mδm,k - the maximum allowable interference power of PU k on channel mOutput:An,v - the action space/set of vehicle IDn under the current node vFunction Actionn,v1:An,v⟵∅2:for each ln,m in the n-th row of matrix Ldo3:ifln,m=1then4:An,v⟵am5:end if6:end for7:for each cn,n′,m in 1 ~n columns of the n-th row of matrix Cdo8:for each an′,m in Ado9:ifcn,n′,m=1 and an′,m=1then10:ifam∈An,vthen11:     removeam from An,v12:end if13:end if14:end for15:end for16:for each am in An,vdo17:if the available channel m for the vehicle IDn does not satisfy the constraint (1) and constraints (5a)–(5g) then18:   removeam from An,v19:end if20:end for21:ifAn,v=∅then22:  the algorithm does not perform the allocation for vehicleIDn and waits for the allocation of the next user according to the Priorityscore_list23:end ifTherefore, in this paper, the duration of network service for a PU (denoted byτ) is included in the simulation when doing reward evaluation. Reference [25] pointed out that the duration of network service for PU in each channel obeys a log-normal distribution. The probability density function (PDF) is
(16)fτ;μ,σ=1τσ2πe−lnτ−μ2/2σ2τ>0.The parametersμ,σ are in milliseconds (ms), and the values used in this paper are 2.47,1.88 [25]. Note that the PDF model of PUs does not differentiate the location distribution of PUs (e.g., PUs on the vehicles or PUs on the pedestrians).Through random sampling from the above distribution, we can obtain different scenarios of the service durations for the PUs at each layer in the simulation stage. Each sampling corresponds to a scenario. Since there are infinite scenarios when sampling, here, we sample the number ofχ times at each layer of simulation to control the computation scale. Thus, a scenario set is formed, denoted by π^=π1,π2,⋯,πi,⋯,πχ. In the experiment, we set χ=9. Next, we define a stochastic bonus to adjust the reward evaluation according to different service durations, the resource supply and demand situation, and the utilities of SUs.Definition 5 (stochastic bonus).
Assume that the channelm matches the vehicle IDn and the tree expands from node v~ to node v~′ in the simulation stage. Then, we define a stochastic bonus for node v~ as Ei∈π^Hn,mv~i, in which E represents the expectation of stochastic bonus obtained by vehicle IDn in χ scenarios. We have
(17)Hn,mv~i=tanhUtilityn·τi−1·λ¯mCountLm−CountAm,where τi1≤i≤χ denotes one of the samplings based on distribution fτ;μ,σ. The larger the value of τi, the longer the channel occupied by the PUs in this sampling. It indicates that the bonus of vehicle IDn when doing allocation will be low. Notation Utilityn>0 represents the network utility score of vehicle IDn (Definition 2), which reflects the communication capability of vehicle IDn and is used as a weight coefficient here. We utilize the hyperbolic tangent function tanh· to normalize the value of Utilityn to the interval 0,1. When the Utilityn is large, the weight coefficient is closer to 1, which indicates that the vehicle IDn with strong communication ability tends to have a high bonus. Besides, λ¯m/CountLm−CountAm measures the remaining minimum average bandwidth available to vehicle IDn currently. CountLm records the number of elements in the mth column with value of 1 in matrix L. Thus, CountLm−CountAm describes the maximum number of allowable access vehicles on channel m without considering the interference matrix C and the available bandwidth ϕm.In summary, if a vehicle has strong communication capability, the PUs have low service durations, and the remaining resources are enough, the stochastic bonus will be high.Based on Equation (17), we have an adjusted reward Qv~ for node v~ in the simulation stage:
(18)Qv~=rn,m+Ei∈π^Hn,mv~i,where rn,m refers to the immediate reward that channel m is allocated to vehicle IDn (defined in Equation (2)). For simplicity, we use notation Qv~ omitting the label of n and m.When the simulation reaches the terminal nodev~Δ, we can get the simulation cumulative reward Qv~Δ of all nodes on the simulation path from v~ to v~Δ. We have
(19)Qv~Δ=∑v~v~Δrn,m+Ei∈π^Hn,mv~i.(d)
Backpropagation. The aim of backpropagation is to update the empirical information of the prior exploration before the next iteration, which is shown in Figure 5. When an iteration reaches the terminal node v~Δ, according to Equation (19), we get the simulation cumulative reward Qv~Δ for backpropagation.Figure 5
Backpropagation of Finder-MCTS.In this way, the reward of backpropagation can include the reward evaluation of all expanded nodes on the simulation path, reflecting the overall spectrum allocation performance of simulation in the current iteration. Meanwhile, the algorithm updates the node state on the path from the root to the expanded node according to the following rules:(20)N¯v⟵N¯v+1,Qv⟵Qv+Qv~Δ.To sum up, we provide the pseudocode of Finder-MCTS in Algorithm2. The Finder-MCTS algorithm iteratively executes functions such as Treepolicy, Simulation, and Backpropagation to explore different spectrum allocation schemes (i.e., Am in ΛL,C). It finally finds the optimal spectrum allocation scheme A∗ in the current network.Algorithm 2: Finder-MCTS.
Input:Priorityscore_listOutput:optimal channel allocation matrixA∗Function Finder-MCTSv,Priorityscore_list1: load networkfESP2: create root nodev with state sv3: create channel allocation bufferΛL,C4:while node v is a terminal node do5:  initialize a matrixAN×M with all elements equaling to 06:v~⟵Treepolicyv7:Qv~Δ⟵Simulationsv~,v~8:ifam=1 for vehicle IDnthen9:an,m=110:else11:an,m=012:end if13:  update and putAN×M in ΛL,C14:Backpropagationv,Qv~Δ15:end while16:returnA∗=argmaxAN×M∈ΛL,CUAN×M,RFunctionTreepolicyv17:whilev is nonterminal do18:ifv is not a leaf node then19:v′⟵Bestchildv20:Treepolicyv′21:else22:ifN¯v=0then23:v~⟵v24:else25:Expandv26:end if27:end if28:end whileFunctionBestchildv29:returnargmaxv′∈childvQv′/N¯v′+c·lnN¯v/N¯v′FunctionExpandv30: executeActionn,v31: chooseam∈An,v randomly32: generate a new childv′ of node v33: initializeQv′=034:sv′=fESPsv,am35:Treepolicyv′FunctionSimulationv~36: initializei=0,Qv~=037:whilev~ is not a terminal node v~Δdo38:  chooseam∈An,v~ randomly39:sv~′⟵fsv~,am,v~′⟵v~40:  calculatern,m according to Eq. (2)41:Qv~′⟵Qv~+rn,m+Bonus (Bonus is calculated based on Eq. (17), (18), (19))42:i⟵i+143:end while44:returnQv~Δ when node v~ reaching to the terminal node v~ΔFunctionBackpropagationv,Qv~Δ45:while node v is not null do46:N¯v⟵N¯v+1,Qv⟵Qv+Qv~Δ47:v⟵parentofv48:end while


## 5.1. Finder-MCTS’ Computation Framework

The problems solved by the MCTS are commonly formalized by the Markov decision process (MDP), in which we take the base station as the spectrum scheduling agent and use the link capacity formulated in Equation (2) as the value of the reward Q when a SU occupies a channel. Let S and A denote the MDP state space and action space, respectively. F:S×A⟶S denotes the MDP transition function from a state-action pair to the next state. The state transition function fESP is given by a deep neural network (DNN) simulator in Section 5.2. The definitions of the MDP state space and action space are described as follows:
(11)S=svsv,φv,ξv,(12)A=am∣1≤m≤M.In Equation (11), the MDP state is composed of two parts: λv denotes a vector of remaining bandwidth of M channels under the base station, with sv=λv=λ¯1,⋯,λ¯m,⋯,λ¯Mv; λ¯m denotes the remaining bandwidth of mth channel. φv denotes the number of service requests to be allocated. ξv describes the total bandwidth requests of all φv cognitive vehicles. In addition, in Equation (12), the action space is a set composed of whether the number of M channels are allocated, in which the action am denotes that the agent allocates the channel m to a vehicle that enters into the priority-based allocation sequence and is ready to be scheduled by the base station currently.A Monte-Carlo search tree consists of nodes and edges. A nodev is a tree node that corresponds to the MDP statesv, and the edge connecting a parent node and a child node in the tree represents an action that causes the state transition. Each node v in the tree holds a node state, which contains three types of statistics: visit count (N¯v), MDP state sv, and cumulative reward (Qv) received by node v.The specific search steps are shown in Figure2.
(1)
Create a root node of the search tree and initialize the node state. Assume that the root node is denoted byv and the node state is N¯v,sv,Qv(2)
Allocate the spectrum resources for vehicles according to the priority order listPriorityscore_list defined in Definition 3, and extend the child node while updating the node state. Each layer’s tree expansion represents the spectrum allocation for a vehicle, and each allocation process involves many iterations. Take the root node v in Figure 2 as an example. When the channel assignment action of vehicle ID3 is a1, the search tree extends down to the child node v′ and update the node state through iterative calculation (i.e., sv′=fESPsv,a1)(3)
When the tree expansion reaches the termination condition of iteration (i.e., the second users or the available spectrum resources are all allocated), an optimal channel allocation matrixA∗ in the current allocation period is returned. For example, assume that when reaching the node v′′′ in Figure 2, the iteration ends. The black arrow lines direct an allocation path v⟶v′⟶v′′⟶v′′′. Then, the corresponding actions constitute a feasible allocation policy set a1,a5,a1, which can be converted to a channel allocation matrix AN×M as an outputFigure 2
An example of search steps in Finder-MCTS.


## 5.2. DNN-Based Environmental State Predictor (ESP)

Due to the uncertainty of the PUs’ spectrum occupancy activities, when the tree is expanded from one node to the next in Section5.1, the expansion will be not stable, i.e., given a state and an action, the next state is uncertain. This uncertainty is caused by the unknown environment of IoV. Therefore, to limit the expansion scale of the MCTS tree horizontally and speed up the search, it is necessary to gradually learn to approach the real environment of IoV when doing spectrum allocation. This section presents an offline environment state predictor (named ESP) based on a deep neural network (DNN).Note that, to obtain the ESP, enough training data are needed. Thus, first during the cold start phase of Finder-MCTS (i.e., the algorithm just starts running), we do not rely on ESP. This does not affect the channel allocation solution of Finder-MCTS. After a period of time in the cold start phase, our base station can obtain and cumulate large numbers of “state-action transition pairs.” Subsequently, we input these “state-action transition pairs” into ESP continuously as the training data to obtain a state transition functionfESP, which is an offline training process. Once we have fESP, the Finder-MCTS could converge fast due to the reduction in branching. The above training is done by DNN.The network structure of DNN consists of one input layer, three hidden layers, and one output layer. In this paper, we set the learning rate of DNN to 0.05 and the activation function of DNN is the rectified linear unit function (ReLU). To optimize the neural network parameters, we use the minibatch gradient descent method [23]. In the DNN, the training label is the state sv′, which is the state of the corresponding expansion child node v′ of node v. ESP is used to obtain the prediction state s^v′. The loss function of ESP is
(13)lossESP=1B∑B∥sv′−s^v′∥2,where B represents the batch size of minibatch gradient descent. In the experiment, we set B=64, indicating that 64 samples are selected in each iteration. Notation ·2 represents the L2 norm. When lossESP converges, we let the DNN network parameter wESP update.After we obtain the ESP function, based on the selected actionam and MDP state sv, ESP can give the MDP state of its expanded node s^v′,
(14)s^v′=fESPsv,am∣wESP.


## 5.3. Finder-MCTS Algorithm Based on Action Space Pruning and Scenario Simulation

Finder-MCTS requires to execute the following four steps: selection, expansion, simulation, and backpropagation iteratively to complete a computation process, which is shown in Figure3. In Figure 3, the black circles indicate the nodes involved in each step and the red arrow lines indicate the actions corresponding to each step. In subfigure (c), the policy usually refers to the random selection action extended at each step of the simulation process. We usually call step (a) selection and step (b) expansion together as the tree policy. Specifically, the detailed procedures and descriptions are given in the following steps (a)–(d) and in Figure 4.
(a)
Selection. Each iteration starts from the root node. When the algorithm has to choose to which child node it will descend, it tries to find a good balance between exploitation and exploration. We use the upper confidence bound for tree (UCT) [24] to recursively select child nodes. The selection criterion of the optimal child node is
(15)argmaxv′∈childvQv′N¯v′+c·lnN¯vN¯v′,where c≥0 is a weight coefficient used to adjust the exploitation and exploration. We set c=0.8 in the experiment through many tests. Notation childv represents the set of child nodes with v as the parent in the tree. N¯v′ and N¯v represent the total number of times that the child node v′ and its parent node v have been visited iteratively. Qv′ represents the cumulative reward obtained by node v′. Note that the selected child node should be expandable (i.e., have unvisited child node) and represent a nonterminal state. Next, the algorithm treats the child node with the largest value of UCT as the current node for the next expansion.(b)
Constraint-Oriented Expansion. Finder-MCTS judges whether the number of visits of the current node is 0. If visit count N¯=0, the algorithm goes to step (c) directly. If the visit count N¯≠0, the algorithm enumerates the available actions. However, if it is just a simple enumeration, the number of available actions in the next layer is M. As the tree expands, a huge search tree will be built. The computational complexity grows geometrically with the number of SUs to be allocated. Thus, here, we give the constraint-oriented expansion.Figure 3
An iterative computation process of Finder-MCTS.Figure 4
The flow chart of Finder-MCTS.In the constraint-oriented expansion, we prune the action space according to the constraint conditions defined in Section3.2 so as to obtain all available actions from the current node. And then, add new nodes to expand the tree and let the current node be a new child node which is randomly selected after expansion.Specifically, we useAn,v to represent the set of available actions starting from the node v, which is used for the next round of channel allocation for the nth SU. That is to say, An,v is an interference-free action space of a SU. The detailed implementation steps of the constraint-oriented expansion are described in Algorithm 1.In Algorithm1, we use three main steps to perform action pruning. First, considering the channel availability, we introduce the channel availability matrix L to prune the set of actions. We map the elements of ln,m=1 in the channel availability matrix for vehicle n to the available action set (Lines 2-6 in Algorithm 1). Second, considering that the vehicle IDn currently to be allocated should not share the same channel with a vehicle having communication interference, we introduce the SU-SU interference matrix C for the tree pruning. The algorithm traverses the elements in the channel allocation matrix A and makes a judgement on whether an′,m=1 and cn,n′,m=1 hold at the same time. If they hold at the same time, am is removed from the action set (Lines 7-15 in Algorithm 1). Next, in each iteration, the algorithm needs to make a judgement on whether constraint (1) and constraints (5a)–(5g) hold. If the available channel m for the vehicle currently to be allocated does not satisfy these constraints, action am needs to be removed from the set of actions (Lines 16-20 in Algorithm 1). Finally, if An,v=∅, the algorithm will skip the current allocation and wait for the next round of allocation (Lines 21-23 in Algorithm 1).
(c)
Simulation Based on Different Scenarios. From the above step (b), we know that if the visit count of the current node is zero, we will perform a simulation from the current node (i.e., the newly expanded node, denoted by v~) to the terminal node (denoted by v~Δ). Here, the terminal node refers to the node that the descending arrives at when the SUs or the available channel resources have been all allocated. Usually, the simulation uses a random search strategy to generate a reward Qv~Δ at the final leaf node v~Δ. However, the time-varying property of PUs’ spectrum occupancy activities makes the actual available spectrum resources uncertain. This uncertainty will have potential impacts on the reward evaluation for the SU to be allocated in IoV.Algorithm 1: Constraint-oriented expansion for vehicle IDn.
Input:L - channel availability matrixC - SU-SU interference constraint matrixA - channel allocation matrixγm - the maximum allowable interference level of channel mϕm - the available bandwidth of channel mδm,k - the maximum allowable interference power of PU k on channel mOutput:An,v - the action space/set of vehicle IDn under the current node vFunction Actionn,v1:An,v⟵∅2:for each ln,m in the n-th row of matrix Ldo3:ifln,m=1then4:An,v⟵am5:end if6:end for7:for each cn,n′,m in 1 ~n columns of the n-th row of matrix Cdo8:for each an′,m in Ado9:ifcn,n′,m=1 and an′,m=1then10:ifam∈An,vthen11:     removeam from An,v12:end if13:end if14:end for15:end for16:for each am in An,vdo17:if the available channel m for the vehicle IDn does not satisfy the constraint (1) and constraints (5a)–(5g) then18:   removeam from An,v19:end if20:end for21:ifAn,v=∅then22:  the algorithm does not perform the allocation for vehicleIDn and waits for the allocation of the next user according to the Priorityscore_list23:end ifTherefore, in this paper, the duration of network service for a PU (denoted byτ) is included in the simulation when doing reward evaluation. Reference [25] pointed out that the duration of network service for PU in each channel obeys a log-normal distribution. The probability density function (PDF) is
(16)fτ;μ,σ=1τσ2πe−lnτ−μ2/2σ2τ>0.The parametersμ,σ are in milliseconds (ms), and the values used in this paper are 2.47,1.88 [25]. Note that the PDF model of PUs does not differentiate the location distribution of PUs (e.g., PUs on the vehicles or PUs on the pedestrians).Through random sampling from the above distribution, we can obtain different scenarios of the service durations for the PUs at each layer in the simulation stage. Each sampling corresponds to a scenario. Since there are infinite scenarios when sampling, here, we sample the number ofχ times at each layer of simulation to control the computation scale. Thus, a scenario set is formed, denoted by π^=π1,π2,⋯,πi,⋯,πχ. In the experiment, we set χ=9. Next, we define a stochastic bonus to adjust the reward evaluation according to different service durations, the resource supply and demand situation, and the utilities of SUs.Definition 5 (stochastic bonus).
Assume that the channelm matches the vehicle IDn and the tree expands from node v~ to node v~′ in the simulation stage. Then, we define a stochastic bonus for node v~ as Ei∈π^Hn,mv~i, in which E represents the expectation of stochastic bonus obtained by vehicle IDn in χ scenarios. We have
(17)Hn,mv~i=tanhUtilityn·τi−1·λ¯mCountLm−CountAm,where τi1≤i≤χ denotes one of the samplings based on distribution fτ;μ,σ. The larger the value of τi, the longer the channel occupied by the PUs in this sampling. It indicates that the bonus of vehicle IDn when doing allocation will be low. Notation Utilityn>0 represents the network utility score of vehicle IDn (Definition 2), which reflects the communication capability of vehicle IDn and is used as a weight coefficient here. We utilize the hyperbolic tangent function tanh· to normalize the value of Utilityn to the interval 0,1. When the Utilityn is large, the weight coefficient is closer to 1, which indicates that the vehicle IDn with strong communication ability tends to have a high bonus. Besides, λ¯m/CountLm−CountAm measures the remaining minimum average bandwidth available to vehicle IDn currently. CountLm records the number of elements in the mth column with value of 1 in matrix L. Thus, CountLm−CountAm describes the maximum number of allowable access vehicles on channel m without considering the interference matrix C and the available bandwidth ϕm.In summary, if a vehicle has strong communication capability, the PUs have low service durations, and the remaining resources are enough, the stochastic bonus will be high.Based on Equation (17), we have an adjusted reward Qv~ for node v~ in the simulation stage:
(18)Qv~=rn,m+Ei∈π^Hn,mv~i,where rn,m refers to the immediate reward that channel m is allocated to vehicle IDn (defined in Equation (2)). For simplicity, we use notation Qv~ omitting the label of n and m.When the simulation reaches the terminal nodev~Δ, we can get the simulation cumulative reward Qv~Δ of all nodes on the simulation path from v~ to v~Δ. We have
(19)Qv~Δ=∑v~v~Δrn,m+Ei∈π^Hn,mv~i.(d)
Backpropagation. The aim of backpropagation is to update the empirical information of the prior exploration before the next iteration, which is shown in Figure 5. When an iteration reaches the terminal node v~Δ, according to Equation (19), we get the simulation cumulative reward Qv~Δ for backpropagation.Figure 5
Backpropagation of Finder-MCTS.In this way, the reward of backpropagation can include the reward evaluation of all expanded nodes on the simulation path, reflecting the overall spectrum allocation performance of simulation in the current iteration. Meanwhile, the algorithm updates the node state on the path from the root to the expanded node according to the following rules:(20)N¯v⟵N¯v+1,Qv⟵Qv+Qv~Δ.To sum up, we provide the pseudocode of Finder-MCTS in Algorithm2. The Finder-MCTS algorithm iteratively executes functions such as Treepolicy, Simulation, and Backpropagation to explore different spectrum allocation schemes (i.e., Am in ΛL,C). It finally finds the optimal spectrum allocation scheme A∗ in the current network.Algorithm 2: Finder-MCTS.
Input:Priorityscore_listOutput:optimal channel allocation matrixA∗Function Finder-MCTSv,Priorityscore_list1: load networkfESP2: create root nodev with state sv3: create channel allocation bufferΛL,C4:while node v is a terminal node do5:  initialize a matrixAN×M with all elements equaling to 06:v~⟵Treepolicyv7:Qv~Δ⟵Simulationsv~,v~8:ifam=1 for vehicle IDnthen9:an,m=110:else11:an,m=012:end if13:  update and putAN×M in ΛL,C14:Backpropagationv,Qv~Δ15:end while16:returnA∗=argmaxAN×M∈ΛL,CUAN×M,RFunctionTreepolicyv17:whilev is nonterminal do18:ifv is not a leaf node then19:v′⟵Bestchildv20:Treepolicyv′21:else22:ifN¯v=0then23:v~⟵v24:else25:Expandv26:end if27:end if28:end whileFunctionBestchildv29:returnargmaxv′∈childvQv′/N¯v′+c·lnN¯v/N¯v′FunctionExpandv30: executeActionn,v31: chooseam∈An,v randomly32: generate a new childv′ of node v33: initializeQv′=034:sv′=fESPsv,am35:Treepolicyv′FunctionSimulationv~36: initializei=0,Qv~=037:whilev~ is not a terminal node v~Δdo38:  chooseam∈An,v~ randomly39:sv~′⟵fsv~,am,v~′⟵v~40:  calculatern,m according to Eq. (2)41:Qv~′⟵Qv~+rn,m+Bonus (Bonus is calculated based on Eq. (17), (18), (19))42:i⟵i+143:end while44:returnQv~Δ when node v~ reaching to the terminal node v~ΔFunctionBackpropagationv,Qv~Δ45:while node v is not null do46:N¯v⟵N¯v+1,Qv⟵Qv+Qv~Δ47:v⟵parentofv48:end while


## 6. Experimental Results and Analysis

In this section, first, we give the detailed simulation settings, including the vehicular dataset generation and some parameters in our proposed method. Second, we compare Finder-MCTS with other types of methods in terms of channel utilization ratio (CUR), average link capacity (ALC), and convergence time. Finally, we test the performance of Finder-MCTS compared with other MCTS algorithms’ variations.


### 6.1. Simulation Settings

Our experiments are done by using the simulation of urban mobility (SUMO) simulator. All the simulations are conducted on a PC with Intel Core CPU i9-9820X 3.50 GHz processor, 64 GB RAM. We export a map of the area near Pudong Airport in Shanghai from OpenSteetMap, which is shown in Figure6. The latitude of the experimental area is between [31.19177, 31.19742]. The longitude is between [121.31134, 121.31853]. In this area, we randomly select four base stations (depicted by red star marks). The locations of these base stations and different communication radii are listed in Table 1. Each base station can observe the traffic flows and obtain the passing vehicles’ information, including the vehicle ID, location, speed, timestamp, and acceleration.Figure 6
The experimental area imported from OpenStreetMap.Table 1
Information of the four base stations.
NameLatitudeLongitudeCommunication radiusBS131.19554121.31274500 mBS231.19604121.31619500 mBS331.19327121.31462500 mBS431.19363121.31713500 mAssume that each base station hasM=10 available spectrum channels. The bandwidth of each channel is set to 20 MHz. We import 100 cognitive vehicles into the simulation scene. Each vehicle randomly proposes a service request to the base station with probability of 50% at each allocation time window. Suppose that the duration of network service for each vehicle is equal to the allocation time window. In SUMO, we set the parameters for the different types of vehicles in Table 2. Compared with the moving vehicle, a PU can be regarded as a static point in the experiment. We set a total of K=30 fixed points as PUs under the four base stations. Each PU randomly occupies a part of the communication bandwidth (MHz), which is subject to U1,10 uniform distribution. At each allocation time window, we randomly let 70% PUs occupy the nearest base station’s available channels. The duration of network service for a PU is chosen according to Equation (16). The spectrum demand of each SU n is randomly selected in [1, 3] MHz. The maximum allowable interference level on channel mγm is −114dBm. The level of background noise on channel mNm is 1 dB. The minimum transmission power and maximum transmission power are P¯m,nmin=20dBm and P¯m,nmax=25dBm, respectively. The maximum allowable interference power of PU k on channel mδm,k is 5 dB.Table 2
Parameters used in SUMO.
ParametersCarBusTruckThe maximum speed15 (m/s)13 (m/s)10 (m/s)The minimum speed1 (m/s)1 (m/s)1 (m/s)The minimum gap between vehicles2.5 (m)2.5 (m)2.5 (m)The maximum acceleration3 (m/s2)1.5 (m/s2)1.5 (m/s2)The maximum deceleration7.5 (m/s2)4 (m/s2)4 (m/s2)The maximum deceleration for emergency breaking9 (m/s)7 (m/s)7 (m/s)In the experiment, the protection radius of a PU (R~k,m) is set to 100 m. We let the transmit power level of SUs be generated from the set 20dBm,21dBm,22dBm,23dBm,24dBm,25dBm. Thus, the interference radius of a SU (R¯n,m) corresponding to the above power levels is 100 m, 150 m, 200 m, 250 m, 300 m, and 350 m. The transmit power of a base station is set to 46 dBm. For simplicity, assume that the transmit power is equal to the transmission power and let the channel gain in the wireless space be constituted by the path loss. We define the path loss between SU n and base station j as PLn,j=34+40lgdnj, where dnj denotes the Euclidean distance between SU n and base station j. Besides, we define the path loss between SU n and PU k as PLn,k=40+24.4lgdnk [26], where dnk denotes the Euclidean distance between SU n and PU k. The received signal power level is given by the product of the transmit power and the channel gain. Thus, the parameters Pm,n,k, Pm,k,n, and Pm,n can be obtained through the above calculations.


### 6.2. Comparison with Other Types of Methods

Under the same simulation settings, we compare our Finder-MCTS with three other algorithms, i.e., the game theory-based method [7], particle swarm optimization-based (PSO-based) method [12], and DQN-based method [27], in terms of channel utilization ratio, convergence time, and average link capacity of SUs.The channel utilization ratio (CUR) refers to the occupancy ratio of the available spectrum resources in the current base station. Besides, the average link capacity (ALC) is defined as follows:(21)ALC=1N·∑n=1N∑m=1Man,m·rn,m.If a method has high CUR, high ALC, and low convergence time, it means that the method can not only make full use of the spectrum resources but also enable SUs to obtain better communication service quality quickly.First, after the simulations are all done in the four base stations, we compare the average CUR, ALC, and convergence time of the proposed Finder-MCTS with three other methods, shown in Figure7. From the average CUR performance in Figure 7(a), we can see that Finder-MCTS performs the best, the second-best is the DQN-based method, and the worst is the PSO-based method. From the average ALC performance in Figure 7(b), we can see that Finder-MCTS performs the best, the second-best is the DQN-based method, and the worst is the game theory-based method. From the average convergence time performance in Figure 7(c), we can see that Finder-MCTS performs the best, the second-best is the DQN-based method, and the worst is the game theory-based method.Figure 7
Comparison with three other methods in terms of average CUR, ALC, and convergence time.
(a)
Performance of CUR(b)
Performance of ALC(c)
Performance of convergence timeBased on the above results, we give the following analysis. Because the convergence of the Nash equilibrium solution is negatively related to the size of the problem, the game theory-based method’s convergence performance is poor. When the game theory-based method reaches convergence, the CUR performance of the system can be approximately optimal; however, the equilibrium of the multiuser game makes the ALC value relatively low. Besides, the PSO-based method is easy to fall into the local optimal solution; its average CUR and average ALC perform relatively poorly. Since the complicated parameters’ setting of PSO, its average convergence time becomes longer as the scale of the problem becomes larger. Moreover, after the exploration of actions through reinforcement learning, the DQN-based method can obtain a higher quality spectrum allocation solution, and the performance of average CUR and ALC is second only to Finder-MCTS. However, the convergence time of the DQN-based method is higher than that of Finder-MCTS due to the long-term exploration and value updating, although enough experience information learned through online learning can speed up the convergence time of DQN to some extent. By contrast, Finder-MCTS based on offline training and online learning has an average 36.47% improvement in convergence time than other methods. In terms of ALC, Finder-MCTS has an average advantage of 18.24% over other methods. At the same time, the channel utilization of Finder-MCTS is 9.00% higher than that of other methods on average.Second, since the number of SUs in the coverage area of each base station is time-varying, it is necessary to observe the performance changes under different SUs’ scales. The results are shown in Figure8. Here, notice that in Figure 8, each depicted point in the curve is an averaged value statistically. For example, as to the results that distribute in the scale interval p1,p2 of the x-axis, we average these results and depict the averaged value corresponding to point p2.Figure 8
Performance comparison with varying numbers of SUs.
(a)
Performance of CUR(b)
Performance of ALC(c)
Performance of convergence timeFigure8(a) shows the relationship between the number of SUs and CUR. In general, as the number of SUs increases, the CUR curve increases until it gradually converges. In addition, we find that when the number of SUs is small, the game theory can give a solution with high CUR. However, with the increase of SUs, the Finder-MCTS and DQN-based methods show obvious advantages in resource utilization. The reason behind that is when the scale of SU becomes large, the combination of historical experiences and online exploration can greatly improve the quality of the solution. In contrast, the game theory-based equilibrium quality for large-scale SU problems has declined. Also, the PSO-based method often converges to a local optimal solution and its CUR performance cannot be guaranteed.Figure8(b) depicts the relationship between the number of SUs and ALC. It is obvious that as the number of SUs increases, the ALC value decreases since the available spectrum resources of the base station side are limited. Besides, we find that when the number of SUs is small, the game-based method shows a good performance in ALC. However, as the number of SUs increases, Finder-MCTS shows an obvious advantage. This is because when the scale of SUs becomes large, finding an optimal solution is hard for the game-based method. Moreover, since the PSO-based method is hard to reach the global convergence, the ALC performance is relatively low with the number of SUs increasing.Figure8(c) shows the simulation results of the relationship between the number of SUs and the convergence time. First, we can see that the convergence time of game theory-based and PSO-based methods shows an obvious growth trend as the number of SUs increases, while the convergence time based on DQN and Finder-MCTS rises moderately. The main reason is that the Finder-MCTS and DQN-based methods gradually fit the channel state model after continuous learning, thereby greatly improving the search efficiency. The convergence time of Finder-MCTS is reduced by 65.23% and 18.85% compared with the game theory-based method and the PSO-based method. In the long run, Finder-MCTS shows a short and gentle convergence time performance in the dynamic environment.All the above phenomena verify the advantage of Finder-MCTS in solving spectrum allocation in IoV. Finder-MCTS can effectively complete the rapid learning of the approximate optimal allocation solution in a time-varying environment, which greatly improves the available spectrum utilization ratio of the current base station system.


### 6.3. Comparison with Other MCTS Algorithms’ Variations

In this part, we compare Finder-MCTS with other MCTS algorithms’ variations. We show why we consider the priority mechanism and simulation under different scenarios.We set two basic types of MCTS-based spectrum allocation modes: random-order-based allocation mode and priority-based allocation mode, which are called as R-MCTS and P-MCTS, respectively. In R-MCTS, compared with Finder-MCTS, both priority and the uncertainty of PUs’ service durations are not taken into consideration. In P-MCTS, compared with Finder-MCTS, only the uncertainty of PUs’ service durations is not taken into consideration. The simulation results are shown in Figure9. We can see that Finder-MCTS performs the best, the second-best is P-MCTS, and the worst is R-MCTS. According to the above results, we give the following analysis.Figure 9
Comparison with two types of MCTS algorithms’ variations in terms of average CUR, ALC, and convergence time.
(a)
Performance of CUR(b)
Performance of ALC(c)
Performance of convergence timeFrom Figure9(a), we can see that the CUR performance of P-MCTS is superior than R-MCTS. This gap illustrates that the introduction of priority evaluation will improve the ratio of the spectrum utilization (about 9.12% increase). Meanwhile, Finder-MCTS has the best CUR performance. In the long run, the service duration τ of PU on each channel will give each allocated SU differentiated stochastic bonus. Hence, based on the uncertainty of the channel state occupied by the PUs, we introduce the factor τ that affects the supply-demand ratio of spectrum resources into the reward evaluation during each expansion step of the simulation process. We learn that Finder-MCTS is better (about 4.08% increase) than P-MCTS on ALC. Hence, we can conclude that the optimization of the stochastic simulation process contributes to improved spectrum usage efficiency of CR-IoV from a global perspective.Figure9(b) depicts the different performances of the three methods in ALC performance. With the help of priority evaluation, P-MCTS has increased by 6.73% compared with R-MCTS. The ALC performance of Finder-MCTS has increased by 10.19% compared with P-MCTS by evaluating the uncertainty of PUs’ service durations.Figure9(c) shows the average convergence time of the three methods. Owing to the priority evaluation, P-MCTS has a 22.89% advantage over R-MCTS. This characterizes the positive impact of the differentiation priority evaluation on the algorithm convergence time. Secondly, under the same setting, with the help of reduction of action space in each descending layer, Finder-MCTS achieves a faster convergence speed (about 46.69% increase and 30.86% increase) than R-MCTS and P-MCTS.


## 6.1. Simulation Settings

Our experiments are done by using the simulation of urban mobility (SUMO) simulator. All the simulations are conducted on a PC with Intel Core CPU i9-9820X 3.50 GHz processor, 64 GB RAM. We export a map of the area near Pudong Airport in Shanghai from OpenSteetMap, which is shown in Figure6. The latitude of the experimental area is between [31.19177, 31.19742]. The longitude is between [121.31134, 121.31853]. In this area, we randomly select four base stations (depicted by red star marks). The locations of these base stations and different communication radii are listed in Table 1. Each base station can observe the traffic flows and obtain the passing vehicles’ information, including the vehicle ID, location, speed, timestamp, and acceleration.Figure 6
The experimental area imported from OpenStreetMap.Table 1
Information of the four base stations.
NameLatitudeLongitudeCommunication radiusBS131.19554121.31274500 mBS231.19604121.31619500 mBS331.19327121.31462500 mBS431.19363121.31713500 mAssume that each base station hasM=10 available spectrum channels. The bandwidth of each channel is set to 20 MHz. We import 100 cognitive vehicles into the simulation scene. Each vehicle randomly proposes a service request to the base station with probability of 50% at each allocation time window. Suppose that the duration of network service for each vehicle is equal to the allocation time window. In SUMO, we set the parameters for the different types of vehicles in Table 2. Compared with the moving vehicle, a PU can be regarded as a static point in the experiment. We set a total of K=30 fixed points as PUs under the four base stations. Each PU randomly occupies a part of the communication bandwidth (MHz), which is subject to U1,10 uniform distribution. At each allocation time window, we randomly let 70% PUs occupy the nearest base station’s available channels. The duration of network service for a PU is chosen according to Equation (16). The spectrum demand of each SU n is randomly selected in [1, 3] MHz. The maximum allowable interference level on channel mγm is −114dBm. The level of background noise on channel mNm is 1 dB. The minimum transmission power and maximum transmission power are P¯m,nmin=20dBm and P¯m,nmax=25dBm, respectively. The maximum allowable interference power of PU k on channel mδm,k is 5 dB.Table 2
Parameters used in SUMO.
ParametersCarBusTruckThe maximum speed15 (m/s)13 (m/s)10 (m/s)The minimum speed1 (m/s)1 (m/s)1 (m/s)The minimum gap between vehicles2.5 (m)2.5 (m)2.5 (m)The maximum acceleration3 (m/s2)1.5 (m/s2)1.5 (m/s2)The maximum deceleration7.5 (m/s2)4 (m/s2)4 (m/s2)The maximum deceleration for emergency breaking9 (m/s)7 (m/s)7 (m/s)In the experiment, the protection radius of a PU (R~k,m) is set to 100 m. We let the transmit power level of SUs be generated from the set 20dBm,21dBm,22dBm,23dBm,24dBm,25dBm. Thus, the interference radius of a SU (R¯n,m) corresponding to the above power levels is 100 m, 150 m, 200 m, 250 m, 300 m, and 350 m. The transmit power of a base station is set to 46 dBm. For simplicity, assume that the transmit power is equal to the transmission power and let the channel gain in the wireless space be constituted by the path loss. We define the path loss between SU n and base station j as PLn,j=34+40lgdnj, where dnj denotes the Euclidean distance between SU n and base station j. Besides, we define the path loss between SU n and PU k as PLn,k=40+24.4lgdnk [26], where dnk denotes the Euclidean distance between SU n and PU k. The received signal power level is given by the product of the transmit power and the channel gain. Thus, the parameters Pm,n,k, Pm,k,n, and Pm,n can be obtained through the above calculations.


## 6.2. Comparison with Other Types of Methods

Under the same simulation settings, we compare our Finder-MCTS with three other algorithms, i.e., the game theory-based method [7], particle swarm optimization-based (PSO-based) method [12], and DQN-based method [27], in terms of channel utilization ratio, convergence time, and average link capacity of SUs.The channel utilization ratio (CUR) refers to the occupancy ratio of the available spectrum resources in the current base station. Besides, the average link capacity (ALC) is defined as follows:(21)ALC=1N·∑n=1N∑m=1Man,m·rn,m.If a method has high CUR, high ALC, and low convergence time, it means that the method can not only make full use of the spectrum resources but also enable SUs to obtain better communication service quality quickly.First, after the simulations are all done in the four base stations, we compare the average CUR, ALC, and convergence time of the proposed Finder-MCTS with three other methods, shown in Figure7. From the average CUR performance in Figure 7(a), we can see that Finder-MCTS performs the best, the second-best is the DQN-based method, and the worst is the PSO-based method. From the average ALC performance in Figure 7(b), we can see that Finder-MCTS performs the best, the second-best is the DQN-based method, and the worst is the game theory-based method. From the average convergence time performance in Figure 7(c), we can see that Finder-MCTS performs the best, the second-best is the DQN-based method, and the worst is the game theory-based method.Figure 7
Comparison with three other methods in terms of average CUR, ALC, and convergence time.
(a)
Performance of CUR(b)
Performance of ALC(c)
Performance of convergence timeBased on the above results, we give the following analysis. Because the convergence of the Nash equilibrium solution is negatively related to the size of the problem, the game theory-based method’s convergence performance is poor. When the game theory-based method reaches convergence, the CUR performance of the system can be approximately optimal; however, the equilibrium of the multiuser game makes the ALC value relatively low. Besides, the PSO-based method is easy to fall into the local optimal solution; its average CUR and average ALC perform relatively poorly. Since the complicated parameters’ setting of PSO, its average convergence time becomes longer as the scale of the problem becomes larger. Moreover, after the exploration of actions through reinforcement learning, the DQN-based method can obtain a higher quality spectrum allocation solution, and the performance of average CUR and ALC is second only to Finder-MCTS. However, the convergence time of the DQN-based method is higher than that of Finder-MCTS due to the long-term exploration and value updating, although enough experience information learned through online learning can speed up the convergence time of DQN to some extent. By contrast, Finder-MCTS based on offline training and online learning has an average 36.47% improvement in convergence time than other methods. In terms of ALC, Finder-MCTS has an average advantage of 18.24% over other methods. At the same time, the channel utilization of Finder-MCTS is 9.00% higher than that of other methods on average.Second, since the number of SUs in the coverage area of each base station is time-varying, it is necessary to observe the performance changes under different SUs’ scales. The results are shown in Figure8. Here, notice that in Figure 8, each depicted point in the curve is an averaged value statistically. For example, as to the results that distribute in the scale interval p1,p2 of the x-axis, we average these results and depict the averaged value corresponding to point p2.Figure 8
Performance comparison with varying numbers of SUs.
(a)
Performance of CUR(b)
Performance of ALC(c)
Performance of convergence timeFigure8(a) shows the relationship between the number of SUs and CUR. In general, as the number of SUs increases, the CUR curve increases until it gradually converges. In addition, we find that when the number of SUs is small, the game theory can give a solution with high CUR. However, with the increase of SUs, the Finder-MCTS and DQN-based methods show obvious advantages in resource utilization. The reason behind that is when the scale of SU becomes large, the combination of historical experiences and online exploration can greatly improve the quality of the solution. In contrast, the game theory-based equilibrium quality for large-scale SU problems has declined. Also, the PSO-based method often converges to a local optimal solution and its CUR performance cannot be guaranteed.Figure8(b) depicts the relationship between the number of SUs and ALC. It is obvious that as the number of SUs increases, the ALC value decreases since the available spectrum resources of the base station side are limited. Besides, we find that when the number of SUs is small, the game-based method shows a good performance in ALC. However, as the number of SUs increases, Finder-MCTS shows an obvious advantage. This is because when the scale of SUs becomes large, finding an optimal solution is hard for the game-based method. Moreover, since the PSO-based method is hard to reach the global convergence, the ALC performance is relatively low with the number of SUs increasing.Figure8(c) shows the simulation results of the relationship between the number of SUs and the convergence time. First, we can see that the convergence time of game theory-based and PSO-based methods shows an obvious growth trend as the number of SUs increases, while the convergence time based on DQN and Finder-MCTS rises moderately. The main reason is that the Finder-MCTS and DQN-based methods gradually fit the channel state model after continuous learning, thereby greatly improving the search efficiency. The convergence time of Finder-MCTS is reduced by 65.23% and 18.85% compared with the game theory-based method and the PSO-based method. In the long run, Finder-MCTS shows a short and gentle convergence time performance in the dynamic environment.All the above phenomena verify the advantage of Finder-MCTS in solving spectrum allocation in IoV. Finder-MCTS can effectively complete the rapid learning of the approximate optimal allocation solution in a time-varying environment, which greatly improves the available spectrum utilization ratio of the current base station system.


## 6.3. Comparison with Other MCTS Algorithms’ Variations

In this part, we compare Finder-MCTS with other MCTS algorithms’ variations. We show why we consider the priority mechanism and simulation under different scenarios.We set two basic types of MCTS-based spectrum allocation modes: random-order-based allocation mode and priority-based allocation mode, which are called as R-MCTS and P-MCTS, respectively. In R-MCTS, compared with Finder-MCTS, both priority and the uncertainty of PUs’ service durations are not taken into consideration. In P-MCTS, compared with Finder-MCTS, only the uncertainty of PUs’ service durations is not taken into consideration. The simulation results are shown in Figure9. We can see that Finder-MCTS performs the best, the second-best is P-MCTS, and the worst is R-MCTS. According to the above results, we give the following analysis.Figure 9
Comparison with two types of MCTS algorithms’ variations in terms of average CUR, ALC, and convergence time.
(a)
Performance of CUR(b)
Performance of ALC(c)
Performance of convergence timeFrom Figure9(a), we can see that the CUR performance of P-MCTS is superior than R-MCTS. This gap illustrates that the introduction of priority evaluation will improve the ratio of the spectrum utilization (about 9.12% increase). Meanwhile, Finder-MCTS has the best CUR performance. In the long run, the service duration τ of PU on each channel will give each allocated SU differentiated stochastic bonus. Hence, based on the uncertainty of the channel state occupied by the PUs, we introduce the factor τ that affects the supply-demand ratio of spectrum resources into the reward evaluation during each expansion step of the simulation process. We learn that Finder-MCTS is better (about 4.08% increase) than P-MCTS on ALC. Hence, we can conclude that the optimization of the stochastic simulation process contributes to improved spectrum usage efficiency of CR-IoV from a global perspective.Figure9(b) depicts the different performances of the three methods in ALC performance. With the help of priority evaluation, P-MCTS has increased by 6.73% compared with R-MCTS. The ALC performance of Finder-MCTS has increased by 10.19% compared with P-MCTS by evaluating the uncertainty of PUs’ service durations.Figure9(c) shows the average convergence time of the three methods. Owing to the priority evaluation, P-MCTS has a 22.89% advantage over R-MCTS. This characterizes the positive impact of the differentiation priority evaluation on the algorithm convergence time. Secondly, under the same setting, with the help of reduction of action space in each descending layer, Finder-MCTS achieves a faster convergence speed (about 46.69% increase and 30.86% increase) than R-MCTS and P-MCTS.


## 7. Conclusion

In this paper, we investigate the spectrum allocation in CR-IoV by modeling an optimization problem to maximize the link capacity of vehicle users. What is more, we propose a method named Finder-MCTS to solve the optimization problem. We show that Finder-MCTS can learn to adapt and update allocation strategy for transmission under a dynamic network environment. The experimental results show that Finder-MCTS is more efficient in convergence speed, and it achieves good performance gain in spectrum utilization and link capacity compared with other popular strategies, especially when the number of vehicle users becomes more. Besides, we have also confirmed the effectiveness of priority evaluation and uncertainty evaluation of the PUs’ service durations by comparing with two variations of MCTS. In future work, how to achieve adaptive equilibrium between the number of sampling scenarios and the running time of uncertainty evaluation in simulation is a worthy direction to improve the convergence time of Finder-MCTS. Besides, we will further study the cooperative spectrum allocation problem of IoV under a complex scenario with space/air/ground communications and networking.



---

*Source: 2270505-2021-11-08.xml*