# Distributed Schemes for Crowdsourcing-Based Sensing Task Assignment in Cognitive Radio Networks

Authors: Linbo Zhai; Hua Wang; Chengcheng Liu
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

Spectrum sensing is an important issue in cognitive radio networks. The unlicensed users can access the licensed wireless spectrum only when the licensed wireless spectrum is sensed to be idle. Since mobile terminals such as smartphones and tablets are popular among people, spectrum sensing can be assigned to these mobile intelligent terminals, which is called crowdsourcing method. Based on the crowdsourcing method, this paper studies the distributed scheme to assign spectrum sensing task to mobile terminals such as smartphones and tablets. Considering the fact that mobile terminals’ positions may influence the sensing results, a precise sensing effect function is designed for the crowdsourcing-based sensing task assignment. We aim to maximize the sensing effect function and cast this optimization problem to address crowdsensing task assignment in cognitive radio networks. This problem is difficult to be solved because the complexity of this problem increases exponentially with the growth in mobile terminals. To assign crowdsensing task, we propose four distributed algorithms with different transition probabilities and use a Markov chain to analyze the approximation gap of our proposed schemes. Simulation results evaluate the average performance of our proposed algorithms and validate the algorithm’s convergence.


---

## Body

## 1. Introduction

According to Cisco’s report, the wireless traffic has increased sharply in the past few years and the global mobile data traffic grew by 63% in 2016 [1]. The high growth rate of wireless traffic leads to crowd wireless spectrum. This upward trend of mobile traffic, which is attributed to the rapid proliferation of mobile devices (e.g., smartphones and tablets), will lead to a looming shortage of wireless spectrum [2]. Nevertheless, a recent study reveals that much of the licensed spectrum, under current policy in the fixed spectrum assignment, is in fact poorly utilized [3]. To improve wireless spectrum utilization, cognitive radio has recently emerged as a solution [4]. When the licensed wireless spectrum is sensed to be idle, cognitive radio allows unlicensed users to access the idle licensed wireless spectrum opportunistically. Therefore, wireless spectrum sensing is the premise for unlicensed users to use the wireless spectrum.Nowadays, mobile terminals, including smartphones and tablets, are very popular. These mobile terminals are intelligent and they can sense the wireless spectrum. Therefore, spectrum sensing tasks can be assigned to mobile terminals, which is called crowdsourcing, a new sensing method empowering ordinary users to carry out sensing with their mobile devices and aggregating the sensing data [5].In this paper, based on the crowdsourcing method, we propose distributed algorithms to assign mobile terminals the spectrum sensing task. Mobile terminals in different positions may have different sensing results about the same channel since shadowing, multipath fading, and other issues may influence the sensing results. Considering the impact of mobile terminals’ positions, we propose a precise sensing effect function of the crowdsourcing-based sensing task assignment. We aim to maximize the sensing effect function and cast this optimization problem to address crowdsensing task assignment in cognitive radio networks. Because the complexity of this problem increases exponentially with the growth in mobile terminals, this problem is difficult to be solved. To assign crowdsensing task, we propose four distributed algorithms with different transition probabilities and use a Markov chain to analyze the approximation gap of our proposed schemes. As the proposed algorithms are distributed, it is convenient for each mobile terminal to carry out algorithms independently. Based on the details of our proposed algorithms, the complexity is low. Therefore, it is comfortable for mobile terminals to implement the distributed algorithms.In this paper, we study crowdsourcing-based sensing task assignment. The main contributions of the paper are summarized as follows:(i)
Considering the impact of mobile terminals’ positions, we propose a precise objective function for the crowdsensing task assignment.(ii)
It is difficult to assign crowdsensing task for the reason that the complexity of this problem increases exponentially with the growth in mobile terminals. Therefore, we design four distributed algorithms with different transition probabilities to solve this problem in cognitive radio networks.(iii)
Using a Markov chain, we analyze the approximation gap of our proposed schemes.(iv)
Simulation results validate the algorithm’s convergence and show that our proposed algorithms achieve the optimal sensing effect.The rest of the paper is organized as follows. In Section2, related literatures are introduced. In Section 3, we formulate the system model of crowdsensing task assignment. In Section 4, we propose four distributed algorithms to solve the sensing task assignment and use a Markov chain to analyze the approximation gap of our schemes. In Section 5, the proposed algorithm is evaluated with simulation results. Finally, conclusions are shown in Section 6.


## 2. Related Work

Whether licensed users utilize the wireless spectrum or not decides the spectrum state. Therefore, to search for the idle spectrum, it is necessary to model licensed users’ activity [6]. Then, spectrum sensing is carried out. A single user, experiencing shadowing, multipath fading, and other issues, may acquire a wrong sensing result. To improve the sensing accuracy, cooperative spectrum sensing has been proposed by multiple users [7].There are some related works about cooperative spectrum sensing. In wideband cooperative sensing, users, by exchanging their compressed sensing results, estimate the spectrum states cooperatively [8, 9]. In [10], the cooperative spectrum sensing that is assigned to multiple users, namely, crowdsourcing-based method, is proposed to address the security issue of false data launched by malicious mobile users. The studies only relate to single-channel system, while in multichannel networks, the assignment of channel sensing is studied to maximize the quality of monitoring [11–14]. These literatures propose a simplistic objective function which is a weighted sum of some binary variables. And there is no budget constraint in these literatures. In [15], the authors, considering a limited budget, propose the sensing task assignment by selecting a subset of mobile users and solve the problem by greedy algorithm and Linear Program rounding algorithm.In all aforementioned literatures, centralized algorithms are implemented to assign spectrum sensing. However, the system employing a centralized algorithm is not robust when the central node goes down. Moreover, the centralized system is not flexible in users joining or leaving the system [16]. To tackle the faults of centralized algorithms, the problem of spatial spectrum sensing is studied in a distributed way to make full use of spatial spectrum opportunities [17]. Using stochastic geometry, the performance of spatial spectrum sensing is analyzed. In [18], the authors propose a game-theoretic distributed power control mechanism based on channel sensing results of users in cognitive wireless sensor network. Tiny operating system (TinyOS), widely used in sensing system, is considered to be the most robust and energy-efficient system. In [19], the authors provide a review of TinyOS at its design paradigm, scheduling algorithms, programming model, and other features. Sensing nodes with TinyOS are more flexible in different sensing applications.Compared to the spectrum sensing in recent studies, the paper solves sensing task assignment in distributed ways with the two major differences: (i) an objective function, considering different sensing outcomes in various subregions, is introduced to represent sensing effect; (ii) aiming to achieve higher sensing effect, four distributed algorithms, with different transition probabilities, are designed to tackle the problem of sensing task assignment.


## 3. System Model of Crowdsensing Task Assignment

In this section, we describe the system model of crowdsensing task assignment. Since shadowing, multipath fading, and other issues may influence the sensing results, mobile terminals in different positions may have different sensing results about the same channel. Considering the impact of mobile terminals’ positions, we propose a precise sensing effect function of the crowdsourcing-based sensing task assignment.LetN denote the number of channels and let M denote the number of mobile terminals in the system. We assume that a mobile terminal can only choose one channel to sense from all N channels. A channel-assignment configuration f is a vector indicating the channel choice of each mobile terminal; that is, f={f1,f2,…,fM}, where fi∈{1,2,…,N} denotes the chosen channel of mobile terminal i. We define F as the set of all feasible f’s. Given a channel-assignment configuration f, we design the sensing effect as follows.Some issues may influence the sensing results of mobile terminals. In a region, mobile terminals may experience different shadowing and multipath fading in the sensing process when they are at different positions of this region. Therefore, the sensing results of these terminals are different even if they sense the same channel. Considering the impact of positions, we can divide a region into several subregions. Mobile terminals in these subregions obtain different sensing results which capture the spatial diversity. It is assumed that there arem subregions. For the mobile terminals in a subregion h, each terminal chooses a channel to sense. If a channel i is sensed by at least a mobile terminal, we use zih=1 to denote this case. If no mobile terminals sense the channel i, we use zih=0 to denote this case. As the channel i may be sensed in multiple subregions, we use yi to denote the number of sensing subregions. Then we can obtain yi=∑h=1mzhi. The sensing effect can be represented by yi. When yi equals a larger value, the sensing result is more effective. Therefore, if yi equals m, the maximized sensing effect is reached. If yi equals zero, the sensing effect is also zero. When yi is small, we can imagine that the growth rate of sensing effect is higher as yi increases. On the contrary, when yi is large, the growth rate of sensing effect is slower as yi increases.Therefore, given a channel-assignment configurationf, we design the sensing effect function of channel i as follows: (1)Ufi=yim1/m,i=1,2,…,N.According to (1), we can see that the sensing effect function increases as yi increases from zero to m. When yi is small, the sensing effect function increases faster with the growth of yi. When yi is large, the sensing effect function increases more slowly with the growth of yi.Figure1 depicts an instance of crowdsensing task assignment with any one channel-assignment configuration f∈F. It is assumed that there are three channels in the system. In the sensing region, we assume that there are four terrain types. Mobile terminals in different terrain types may have different sensing results about the same channel. Therefore, the sensing region can be divided into four subregions. Obviously, the sensing region may be divided into more subregions when there are more terrain types. Due to the influence of terrain types, mobile terminals in different subregions may obtain different sensing results when they sense the same channel. According to the channel-assignment configuration f, each mobile terminal is assigned a channel to sense.Figure 1
An instance of crowdsensing task assignment.LetVf=∑i=1NUf(i) denote the sensing effect function of all channels with channel-assignment configuration f. To obtain optimized sensing effect of the system, we aim to maximize the sensing effect function of all channels by choosing the optimal channel-assignment configuration f from F. Therefore, the objective function can be expressed as(2)maxf∈FVf.


## 4. Distributed Algorithms

In the system, the size of feasible setF is very large even for a fewer mobile terminals, since |F|=NM, where N denotes the number of channels and M denotes the number of mobile terminals. Therefore, the maximization problem in (2) is hard to be solved. In this section, we design four distributed algorithms to address crowdsensing task assignment. Then we use a Markov chain to analyze the approximation gap of our distributed algorithms. Each mobile terminal broadcasts its sensing result representing the channel status to other terminals with one bit result (0 denoting the idle state and 1 denoting the busy state). Therefore, the signaling overhead is small and can be overlooked.


### 4.1. Distributed Algorithms

Initially, each mobile terminal chooses a channel to sense randomly. Using an additional report, each mobile terminal broadcasts the chosen channel and its position to other mobile terminals. When all mobile terminals have received other terminals’ chosen channels and positions, each terminal can obtain the current channel-assignment configurationf and calculate Vf independently. Then each mobile terminal generates a random number following exponential distribution [20], and its mean equals E which is predefined.After mobile terminals generate their random numbers independently, they count down their random numbers one by one. When the countdown of a mobile terminal expires, this mobile terminal (named mobile terminalj) chooses one of its not-in-sensing channels randomly. Then mobile terminal j may switch to the chosen channel with the probability pfg or stay at the current channel with the probability 1-pfg, where g denotes a new channel configuration if mobile terminal j switches to the chosen channel to sense.If mobile terminalj stays at its current channel, there is still the channel-assignment configuration f. On the contrary, if mobile terminal j switches to the chosen channel to sense, a new channel-assignment configuration g appears. When mobile terminal j switches to the chosen channel to sense, it generates a random number following exponential distribution and broadcasts the new channel-assignment configuration g to other mobile terminals. After other terminals receive the channel-assignment configuration g, they can calculate the new sensing effect function Vg and continue their current countdown processes. When the countdown process of a mobile terminal ends, the terminal can calculate the transition probability based on new Vg.In this implementation, the transition probabilitypfg is so important that it will influence the sensing effect of the system. We design pfg by four different algorithms as follows.Algorithm 1.
In this algorithm, the transition probabilitypfg is designed as(3)pfg=1expβVf,where β is a positive constant which is predefined. This algorithm is easy to achieve as pfg only depends on the sensing effect function Vf under current channel-assignment configuration f. And pfg is independent of sensing effect under the targeting channel-assignment configuration g. Therefore, mobile terminal j switches to the chosen channel with the transition probability determined by the current channel-assignment configuration f.Algorithm 2.
In this algorithm, the transition probabilitypfg is designed as(4)pfg=min⁡exp⁡βVf,exp⁡βVgexp⁡βVf.
When the sensing effect functionVg under targeting channel-assignment configuration g is larger than Vf under current channel-assignment configuration f, the transition probability equals 1. This means that the mobile terminal must switch to the chosen channel. When Vg is smaller than Vf, the transition probability can be obtained based on (4).Algorithm 3.
In this algorithm, the transition probabilitypfg is designed as(5)pfg=exp⁡βVgexp⁡βVf+exp⁡βVg.
WhenVg is larger than Vf, the transition probability is more than 50%. This means that the mobile terminal is more likely to switch to the chosen channel. When Vg is smaller than Vf, the transition probability is less than 50%. This means that the mobile terminal is more likely to stay at the current channel.Algorithm 4.
In this algorithm, the transition probabilitypfg is designed as(6)pff′=exp⁡βVgmax⁡exp⁡βVf,exp⁡βVg.
WhenVg is larger than Vf, the transition probability equals 1. This means that the mobile terminal must switch to the chosen channel. When Vg is smaller than Vf, the transition probability is calculated based on (6).In Algorithms2–4, the transition probability pfg depends on both the current channel-configuration f and the targeting channel-assignment configuration g. Therefore, the algorithms employing Algorithms 2–4 are more complicated than that employing Algorithm 1.We name this implementation with four different transition probabilities as Wait-and-Selection (WS) algorithms.Each mobile terminal carries out the Wait-and-Selection (WS) algorithms independently. The distributed algorithms are described as in Algorithm1.Algorithm 1:Wait-and-Selection algorithms for terminal j.
InputE,β
(1) Each mobile terminal chooses a channel to sense randomly.
(2) Mobile terminal j broadcasts its chosen channel and position to other mobile
terminals.
(3) When terminal j receives all other terminals’ choice and positions, it calculate
V
f independently.
(4) Terminal j generates a timer following exponential distribution with mean
equalingE.
(5) Terminal j begins to count down.
(6) When the timer expires, terminal j chooses one of its not-in-sensing channels
randomly. Terminalj switches to this channel with pfg or stay at the current channel
with1-pfg.
(7) If terminal j switches, it broadcasts g to other mobile terminals.
(8) Other terminals calculate Vg under the new channel-configuration g.
(9) Then the terminal j repeats step (4)–(9).


### 4.2. Analysis of Approximation Gap

We define the approximation gap as the difference between the maximum sensing effect in our algorithms and that in theory. A Markov chain is used to describe the transition among channel-assignment configurations in the system. Based on the balance equation, the probability of each state in the Markov chain can be obtained. Then we can use the state probabilities to calculate the approximation gap. The details are described as follows.According to the “Wait-and-Selection” algorithms, each channel-assignment configurationf corresponds to one state. Thus, there are finite states of the designed Markov chain. The number of states equals F, with F representing the set of all feasible f’s. Each channel-assignment configuration can be reachable from any adjacent state based on one-step transition.LetN denote the number of channels and let M denote the number of mobile terminals in the system. According to the WS algorithms, each mobile terminal counts down following exponential distribution which is memoryless. Since each mobile terminal counts down with the rate 1/E under the current state f, the rate by which the process has the opportunity to leave state f is M/E.After count-down expiration, a mobile terminal chooses one of its not-in-sensing channels randomly with the probability1/(N-1). Then the mobile terminal may switch to the chosen channel with transition probability pfg designed by four algorithms in (3)–(6). Therefore, the transition probability from state f to state g after count-down expiration is pfg/(N-1).Then, we can obtain the transition rateqfg from state f to state g as follows:(7)qfg=MpfgEN-1.Letpf∗ be the stationary distribution of state f. Since the detailed balance equation must be satisfied, we obtain(8)pf∗qfg=pg∗qgf∑f∈Fpf∗=1.From (8), we can obtain the stationary distribution pf∗ of state f. For each transition probability of four algorithms, the stationary distribution pf∗ of state f is the same as others.(9)pf∗=exp⁡βVf∑g∈Fexp⁡βVg,f∈F.The stationary distributionpf∗ also denotes the percentage of the duration that the system is under the channel-assignment configuration f. Obviously, it represents the optimal solution of the problem which is expressed as follows:(10)maxpf≥0∑f∈FpfVf-1β∑f∈Fpflog⁡pf,s.t.∑f∈Fpf=1,where β is a constant.With the stationary distributionpf∗ obtained in (9), the optimal value in (10) is(11)γ=1βlog⁡∑f∈Fexp⁡βVf.The aforementioned analysis illustrates that our distributed algorithm realizes the optimal value of the problem in (10). From (11), we can obtain(12)γ=1βlog⁡exp⁡βmaxf∈FVf∑f∈Fexp⁡βVf-maxf∈FVf≤1βlog⁡exp⁡βmaxf∈FVfF=maxf∈FVf+1βlog⁡F,where F describes the size of channel-assignment set F.From (12), we can obtain the approximation gap of our proposed algorithms as follows:(13)γ-maxf∈FVf≤1βlog⁡F.Therefore, the upper bound of approximation gap is(14)1βlog⁡F.Based on formulation (14), the approximation gap is close to zero when β approaches to infinity. This illustrates that our distributed algorithms approach the optimal value of the maximization problem in (2) with a large value of β. On the other hand, the approximation gap ratio is 1/βlog|F|/maxf∈FVf. When maxf∈FVf is much larger than 1/βlog⁡|F|, β has less impact on the results of our distributed algorithms. Under this condition, our distributed algorithms are not sensitive to β and approach the optimal value of the maximization problem in (2) even if β is not large.


## 4.1. Distributed Algorithms

Initially, each mobile terminal chooses a channel to sense randomly. Using an additional report, each mobile terminal broadcasts the chosen channel and its position to other mobile terminals. When all mobile terminals have received other terminals’ chosen channels and positions, each terminal can obtain the current channel-assignment configurationf and calculate Vf independently. Then each mobile terminal generates a random number following exponential distribution [20], and its mean equals E which is predefined.After mobile terminals generate their random numbers independently, they count down their random numbers one by one. When the countdown of a mobile terminal expires, this mobile terminal (named mobile terminalj) chooses one of its not-in-sensing channels randomly. Then mobile terminal j may switch to the chosen channel with the probability pfg or stay at the current channel with the probability 1-pfg, where g denotes a new channel configuration if mobile terminal j switches to the chosen channel to sense.If mobile terminalj stays at its current channel, there is still the channel-assignment configuration f. On the contrary, if mobile terminal j switches to the chosen channel to sense, a new channel-assignment configuration g appears. When mobile terminal j switches to the chosen channel to sense, it generates a random number following exponential distribution and broadcasts the new channel-assignment configuration g to other mobile terminals. After other terminals receive the channel-assignment configuration g, they can calculate the new sensing effect function Vg and continue their current countdown processes. When the countdown process of a mobile terminal ends, the terminal can calculate the transition probability based on new Vg.In this implementation, the transition probabilitypfg is so important that it will influence the sensing effect of the system. We design pfg by four different algorithms as follows.Algorithm 1.
In this algorithm, the transition probabilitypfg is designed as(3)pfg=1expβVf,where β is a positive constant which is predefined. This algorithm is easy to achieve as pfg only depends on the sensing effect function Vf under current channel-assignment configuration f. And pfg is independent of sensing effect under the targeting channel-assignment configuration g. Therefore, mobile terminal j switches to the chosen channel with the transition probability determined by the current channel-assignment configuration f.Algorithm 2.
In this algorithm, the transition probabilitypfg is designed as(4)pfg=min⁡exp⁡βVf,exp⁡βVgexp⁡βVf.
When the sensing effect functionVg under targeting channel-assignment configuration g is larger than Vf under current channel-assignment configuration f, the transition probability equals 1. This means that the mobile terminal must switch to the chosen channel. When Vg is smaller than Vf, the transition probability can be obtained based on (4).Algorithm 3.
In this algorithm, the transition probabilitypfg is designed as(5)pfg=exp⁡βVgexp⁡βVf+exp⁡βVg.
WhenVg is larger than Vf, the transition probability is more than 50%. This means that the mobile terminal is more likely to switch to the chosen channel. When Vg is smaller than Vf, the transition probability is less than 50%. This means that the mobile terminal is more likely to stay at the current channel.Algorithm 4.
In this algorithm, the transition probabilitypfg is designed as(6)pff′=exp⁡βVgmax⁡exp⁡βVf,exp⁡βVg.
WhenVg is larger than Vf, the transition probability equals 1. This means that the mobile terminal must switch to the chosen channel. When Vg is smaller than Vf, the transition probability is calculated based on (6).In Algorithms2–4, the transition probability pfg depends on both the current channel-configuration f and the targeting channel-assignment configuration g. Therefore, the algorithms employing Algorithms 2–4 are more complicated than that employing Algorithm 1.We name this implementation with four different transition probabilities as Wait-and-Selection (WS) algorithms.Each mobile terminal carries out the Wait-and-Selection (WS) algorithms independently. The distributed algorithms are described as in Algorithm1.Algorithm 1:Wait-and-Selection algorithms for terminal j.
InputE,β
(1) Each mobile terminal chooses a channel to sense randomly.
(2) Mobile terminal j broadcasts its chosen channel and position to other mobile
terminals.
(3) When terminal j receives all other terminals’ choice and positions, it calculate
V
f independently.
(4) Terminal j generates a timer following exponential distribution with mean
equalingE.
(5) Terminal j begins to count down.
(6) When the timer expires, terminal j chooses one of its not-in-sensing channels
randomly. Terminalj switches to this channel with pfg or stay at the current channel
with1-pfg.
(7) If terminal j switches, it broadcasts g to other mobile terminals.
(8) Other terminals calculate Vg under the new channel-configuration g.
(9) Then the terminal j repeats step (4)–(9).


## 4.2. Analysis of Approximation Gap

We define the approximation gap as the difference between the maximum sensing effect in our algorithms and that in theory. A Markov chain is used to describe the transition among channel-assignment configurations in the system. Based on the balance equation, the probability of each state in the Markov chain can be obtained. Then we can use the state probabilities to calculate the approximation gap. The details are described as follows.According to the “Wait-and-Selection” algorithms, each channel-assignment configurationf corresponds to one state. Thus, there are finite states of the designed Markov chain. The number of states equals F, with F representing the set of all feasible f’s. Each channel-assignment configuration can be reachable from any adjacent state based on one-step transition.LetN denote the number of channels and let M denote the number of mobile terminals in the system. According to the WS algorithms, each mobile terminal counts down following exponential distribution which is memoryless. Since each mobile terminal counts down with the rate 1/E under the current state f, the rate by which the process has the opportunity to leave state f is M/E.After count-down expiration, a mobile terminal chooses one of its not-in-sensing channels randomly with the probability1/(N-1). Then the mobile terminal may switch to the chosen channel with transition probability pfg designed by four algorithms in (3)–(6). Therefore, the transition probability from state f to state g after count-down expiration is pfg/(N-1).Then, we can obtain the transition rateqfg from state f to state g as follows:(7)qfg=MpfgEN-1.Letpf∗ be the stationary distribution of state f. Since the detailed balance equation must be satisfied, we obtain(8)pf∗qfg=pg∗qgf∑f∈Fpf∗=1.From (8), we can obtain the stationary distribution pf∗ of state f. For each transition probability of four algorithms, the stationary distribution pf∗ of state f is the same as others.(9)pf∗=exp⁡βVf∑g∈Fexp⁡βVg,f∈F.The stationary distributionpf∗ also denotes the percentage of the duration that the system is under the channel-assignment configuration f. Obviously, it represents the optimal solution of the problem which is expressed as follows:(10)maxpf≥0∑f∈FpfVf-1β∑f∈Fpflog⁡pf,s.t.∑f∈Fpf=1,where β is a constant.With the stationary distributionpf∗ obtained in (9), the optimal value in (10) is(11)γ=1βlog⁡∑f∈Fexp⁡βVf.The aforementioned analysis illustrates that our distributed algorithm realizes the optimal value of the problem in (10). From (11), we can obtain(12)γ=1βlog⁡exp⁡βmaxf∈FVf∑f∈Fexp⁡βVf-maxf∈FVf≤1βlog⁡exp⁡βmaxf∈FVfF=maxf∈FVf+1βlog⁡F,where F describes the size of channel-assignment set F.From (12), we can obtain the approximation gap of our proposed algorithms as follows:(13)γ-maxf∈FVf≤1βlog⁡F.Therefore, the upper bound of approximation gap is(14)1βlog⁡F.Based on formulation (14), the approximation gap is close to zero when β approaches to infinity. This illustrates that our distributed algorithms approach the optimal value of the maximization problem in (2) with a large value of β. On the other hand, the approximation gap ratio is 1/βlog|F|/maxf∈FVf. When maxf∈FVf is much larger than 1/βlog⁡|F|, β has less impact on the results of our distributed algorithms. Under this condition, our distributed algorithms are not sensitive to β and approach the optimal value of the maximization problem in (2) even if β is not large.


## 5. Simulations

In this section, our proposed algorithms are evaluated by simulations. The average solution is derived by running the algorithm 1000 times. The simulation parameters are described as follows. The sensing region is a circular region with a 100-meter radius. And the sensing region is equally divided into four subregions. Mobile terminals are located in the subregions randomly.LetN denote the number of channels and let M denote the number of mobile terminals. There are three channels in the system. Then N=3. E is set to be 3. In Tables 1 and 2, we set β=10 and 20, respectively. It is easy to see that the optimal channel-assignment configuration can be realized when each channel is sensed in all four subregions. According to formulation (1), the optimal sensing effect of a channel is 1. Therefore, we can obtain that the optimal sensing effect of the system is 3 when there are three channels in the system. As M varies from 20 to 28 and β changes, Tables 1 and 2 show the approximation gap of the sensing effect following our Wait-and-Selection algorithms. As shown in Tables 1 and 2, we can see that the approximation gap of our proposed algorithms employing four transition probabilities decreases as the number of mobile terminals increases. As there are more mobile terminals, more subregions will be sensed. Therefore, the approximation gap decreases as M increases, and its magnitude is less than the gap’s upper bound 1/βlog|F|, where |F| equals NM. We also see that the approximation gap is smaller when β is larger. This means that our distributed algorithms approach the optimal sensing effect with a large value of β. In addition, the approximation gap of Algorithm 1 is more than the other three algorithms. This implies that the algorithms employing Algorithms 2–4 approach the optimal sensing effect at the cost of increased complexity.Table 1
The approximation gap of sensing effect withβ=10.
Algorithm
M
20
22
24
26
28
Algorithm1
0.17
0.14
0.093
0.068
0.065
Algorithm2
0.1
0.089
0.066
0.05
0.044
Algorithm3
0.099
0.087
0.068
0.048
0.045
Algorithm4
0.1
0.087
0.067
0.049
0.056Table 2
The approximation gap of sensing effect withβ=20.
Algorithm
M
20
22
24
26
28
Algorithm1
0.15
0.114
0.092
0.069
0.067
Algorithm2
0.073
0.073
0.035
0.037
0.032
Algorithm3
0.074
0.072
0.035
0.035
0.031
Algorithm4
0.074
0.071
0.035
0.038
0.031Figures2 and 3 depict the impact of β on the real gap ratio of our four algorithms when E=3. In Figure 2, the number of mobile terminals equals 12, and the number of channels equals 3. In Figure 3, the number of mobile terminals equals 30, and the number of channels equals 5. As shown in Figures 2 and 3, the gap ratio of Algorithms 2–4 decreases as β increases, while the gap ratio of Algorithm 1 does not change as β increases. For Algorithm 1, the transition rate qfg is so little that mobile terminals almost do not switch to other channels. Therefore, the sensing effect will not change and the gap ratio is stable. For Algorithms 2–4, this means that the larger β is, the more accurate our distributed algorithms are. Moreover, we can see that the gap ratio of Figure 3 is lower than that of Figure 2. That means β has less impact on our distributed algorithms when there are more channels.Figure 2
The approximation gap ratio varies withβ (N=3; M=12).Figure 3
The approximation gap ratio varies withβ (N=5; M=30).When there are three channels in the system (β=20), Figure 4 depicts the gap of our algorithms and other centralized algorithms such as the greedy algorithm in [15] and the particle swarm optimization (PSO) algorithm which is good at optimization problem [21]. As shown in Figure 4, the approximation gap of our algorithms is lower than centralized algorithms. And our algorithms’ gap decreases as the number of mobile terminals increases. That means our distributed algorithms have better performance than centralized algorithms. The distributed algorithms employing Algorithms 2–4 have similar performance which is better than the algorithm employing Algorithm 1. This implies that Algorithms 2–4 make mobile terminals switch to channels to obtain higher sensing effect.Figure 4
Our algorithm compared with centralized algorithms.Figure5 depicts the impact of β on the sensing effect of the system and the convergence time for the distributed algorithm employing Algorithm 2. There are five channels and 30 mobile terminals in the system. Therefore, the optimal sensing effect is five. As shown in Figure 5, the sensing effect is close to the optimal value and the convergence time is long when β=30. On the other hand, the sensing effect is far from the optimal value and the convergence time is short when β=1. Therefore, the proposed algorithm employing Algorithm 2 approaches the optimal value and the convergence time increases as β increases.Figure 5
The impact ofβ for Algorithm 2.Figures6 and 7 depict the impact of β for Algorithms 3 and 4, respectively. There are also five channels and 30 mobile terminals in the system. Therefore, the optimal sensing effect is five. As shown in Figures 6 and 7, the sensing effects of Algorithms 3 and 4 increase as β increases. The larger β is, the higher the sensing effect is. And we also observe that convergence time is longer when β is larger.Figure 6
The impact ofβ for Algorithm 3.Figure 7
The impact ofβ for Algorithm 4.Through contrasting Figures5, 6, and 7, we can observe that the sensing effect of Algorithm 2 is similar to that of Algorithm 4. And the sensing effect of Algorithm 3 is less than those of Algorithms 2 and 4. The reason is that Algorithms 2 and 4 make the channel-assignment configuration f move to g with a higher probability if the new configuration g corresponds to higher sensing effect.


## 6. Conclusion

Spectrum sensing can be assigned to mobile intelligent terminals, which is called crowdsourcing method. This paper studies crowdsensing task assignment to maximize sensing effect. Considering the fact that mobile terminals’ positions may influence the sensing results, we design a precise sensing effect function for the crowdsourcing-based sensing task assignment and aim to maximize sensing effect and cast this optimization problem to address crowdsensing task assignment in cognitive radio networks. To tackle the impact of interference and multipath, we design the objective function considering the sensing results influenced by different locations. When users locate at various areas, the sensing process may be affected differently. Thus, the sensing outcomes may be different. To decrease the impact of different locations, the objective function of this paper, representing the sensing effect, is designed based on the number of locations sensed by users. The larger the number is, the higher the sensing effect is. Therefore, maximizing the objective function means considering the impact of interference and multipath. Compared to aforementioned literatures implementing centralized algorithms, distributed algorithms are proposed with different transition probabilities to obtain bounded close-to-optimal solutions. Simulation results show that our distributed algorithms approach the optimal sensing effect and validate the algorithm’s convergence. In the future, some related issues such as multipath should be studied in the cooperative spectrum sensing.



---

*Source: 5017653-2017-12-14.xml*