# Crowdsensing Task Assignment Based on Particle Swarm Optimization in Cognitive Radio Networks

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

---

## Abstract

Cognitive radio technology allows unlicensed users to utilize licensed wireless spectrum if the wireless spectrum is unused by licensed users. Therefore, spectrum sensing should be carried out before unlicensed users access the wireless spectrum. Since mobile terminals such as smartphones are more and more intelligent, they can sense the wireless spectrum. The method that spectrum sensing task is assigned to mobile intelligent terminals is called crowdsourcing. For a large-scale region, we propose the crowdsourcing paradigm to assign mobile users the spectrum sensing task. The sensing task assignment is influenced by some factors including remaining energy, locations, and costs of mobile terminals. Considering these constraints, we design a precise sensing effect function with a local constraint and aim to maximize this sensing effect to address crowdsensing task assignment. The problem of crowdsensing task assignment is difficult to solve since we prove that it is NP-hard. We design an optimal algorithm based on particle swarm optimization to solve this problem. Simulation results show our algorithm achieves higher performance than the other algorithms.


---

## Body

## 1. Introduction

In recent years, the wireless traffic has grown heavily and this case leads to crowd wireless spectrum. According to the current policy that wireless spectrum assignment is fixed, only licensed users can utilize the licensed wireless spectrum. Even though the wireless spectrum is idle, unlicensed users cannot use the idle spectrum. Therefore, the current policy of spectrum assignment leads to low ratio of wireless spectrum utilization. To solve this problem, cognitive radio has recently emerged to improve wireless spectrum utilization [1]. When the licensed wireless spectrum is idle, cognitive radio makes unlicensed users utilize the wireless spectrum. Therefore, unlicensed users should carry out spectrum sensing before they use the wireless spectrum.With the development of mobile terminals such as smartphones and pads, a new paradigm called mobile crowd sensing and computing (MCSC) appears [2]. The formal definition of MCSC is described as follows: a new sensing paradigm that empowers ordinary citizens to contribute data sensed or generated from their mobile devices and aggregates and fuses the data in the cloud for crowd intelligence extraction and human-centric service delivery.Inspired by MCSC, mobile terminals configured with sensors are leveraged to accomplish spectrum sensing task. In the same spirit, with the recent Federal Communications Commission (FCC) ruling that a geolocation database could be used by Secondary TV spectrum users to obtain the spectrum availability, it is assumed that there is a crowdsourcing-based fusion center (FC). FC assigns sensing task to mobile users and receives the sensing data from them. To incentivize mobile users to carry out sensing tasks, FC needs to provide monetary benefits. This way is called crowdsourcing.In this paper, we propose the crowdsourcing paradigm to assign the spectrum sensing task to many mobile users. It is assumed that there is a crowdsourcing-based fusion center (FC). FC assigns the sensing task to mobile users. During the assignment process, we have considered some factors. At first, the remaining energy is very important to mobile users. Only when a mobile user has enough energy can the wireless spectrum be sensed. Then mobile users should be given incentives to carry out spectrum sensing. With a limited budget, FC may choose a subset of whole mobile users to carry out spectrum sensing. At last, the positions of mobile users also influence the sensing results. Considering these factors, we propose precise sensing effect function for the crowdsourcing-based sensing task assignment. And the objective function considers a local constraint. Then we prove that the sensing task assignment is NP-hard. Therefore, we design an optimal algorithm based on particle swarm optimization (PSO) to solve the problem. Simulation results show our proposed algorithm achieves higher performance than other algorithms.In this paper, we study the problem of sensing task assignment. The main contributions of this paper are summarized below.(i)
Considering the remaining energy of mobile users, budget constraint, and mobile users’ positions, we propose precise objective function with a local constraint. We define the local constraint which means the sensing effect of a channel in a location is not less than a threshold. Compared to other literatures, we aim to not only maximize global sensing effect but also satisfy the local sensing constraint. And we prove the sensing task assignment is NP-hard.(ii)
Since the sensing task assignment is NP-hard, we design an optimal algorithm based on particle swarm optimization (PSO) to solve the problem. To the best of our knowledge, there is no related work designing the PSO-based algorithm to solve sensing task assignment in cognitive radio networks.(iii)
Simulation results show our proposed algorithm achieves higher performance than other algorithms.The rest of the paper is organized as follows. In Section2, related literatures are introduced. In Section 3, the system model of sensing task assignment is described. In Section 4, we design a PSO-based algorithm to solve the sensing task assignment. In Section 5, the proposed algorithm is evaluated with simulation results. Finally, conclusions are shown in Section 6.


## 2. Related Work

In cognitive radio networks, licensed users activity will decide whether the spectrum is idle or not [3]. As some factors such as shadowing and multipath fading may make a user mistake the sensing result, cooperative spectrum sensing is proposed to improve the sensing accuracy [4].There have been some related literatures about cooperative spectrum sensing. In wideband wireless system, users exchange their compressed sensing results. According to the sensing results, they estimate the spectrum states cooperatively [5]. In [6], authors propose a two-level defense scheme to solve the attackers in cooperative spectrum sensing. In [7], cooperative spectrum sensing based on crowdsourcing is studied to address the security issue brought by malicious mobile users. In [8], authors consider the simultaneous sensing and transmitting of users and propose a novel detection model for cooperative spectrum sensing. In multichannel networks, the sensing task assignment is considered in parallel, and several sensing strategies are proposed to schedule users based on network parameters [9]. In [10], authors propose a game-theoretic distributed power control mechanism based on channel sensing results of users in cognitive wireless sensor network. To maximize the sensing quality, authors study the problem of multichannel sensing assignment in the multichannel system [11–13]. These literatures use a simplistic objective function and there is no budget constraint. If the system has a limited budget, there may be only a subset of mobile users chosen to carry out spectrum sensing. In [14], considering budget constraint, the authors study the problem of sensing task and channel allocation. However, the energy of mobile users is not considered. In [15], considering the character of sensing tasks and the sensor availability, authors study the multitask allocation problem to maximize overall system utility. It is the first to study different data quality metrics and formulate the multitask allocation optimization problem when diverse sensing capability constraints of each participant are taken into account. To achieve the near-optimal objective, the method using a two-phase offline multitask allocation framework needs historical call data from the telecom operator.The aforementioned literatures use centralized algorithms. There are some distributed methods about spectrum sensing. In [16], with a distributed way, spatial spectrum sensing is studied to make use of spatial spectrum opportunities. To analyze the performance of spatial spectrum sensing, stochastic geometry is utilized. In [10], based on channel sensing results of users, a game-theoretic distributed power control mechanism is proposed. Besides, there are other studies about spectrum sensing [17–20].


## 3. System Model

It is assumed that there is a crowdsourcing-based fusion center (FC). FC assigns the sensing task to mobile users. Remaining energy and positions of mobile users, as well as limited budget, may influence the assignment process. Considering these constraints, we propose precise sensing effect function with a local constraint. Then we prove the sensing task assignment is NP-hard.


### 3.1. Problem Formulation

We assume that there are many locations needed to be sensed. In each location, there are many channels that needed sensing. By crowdsensing task assignment, we aim to maximize the sensing effect with a local constraint.LetM denote the number of locations needed to be sensed and N(j) denote the number of channels that should be sensed in a location j. In the location j, shadowing, multipath fading, and other issues may influence the sensing results of mobile users in different positions of this location. In other words, mobile users may obtain different sensing results in the same location since they are at different positions. Therefore, location j may be divided into several sublocations. The spatial diversity can be captured by the sensing outcomes of mobile users in different sublocations. In a sublocation h of location j, zihj=1 denotes that there is at least one mobile user sensing channel i, and zihj=0 denotes that there are no mobile users sensing channel i. In location j, let yij denote the number of sublocations where channel i is sensed by at least one mobile user. We can derive yij=∑h=1m(j)zhji, where m(j) denotes the number of sublocations in location j. Obviously, the higher yij is, the more effective the sensing result is. When yij equals zero, there is no sensing effect. When yij equals m(j), the maximized sensing effect is reached. We can imagine that sensing effect increases fast as yij increases when yij is small, while sensing effect increases slowly as yij increases when yij is large. Let fi,j=yij/mj denote the sensing effect of channel i in location j. Then we can design the sensing effect function for the crowdsensing task assignment as follows: (1)∑j=1M∑i=1Njwijfi,j,where wij denotes the nonnegative weight with ∑j=1M∑i=1N(j)wij=1, and wij could distinguish the important degrees of sensing channels in each location. According to formula (1), the sensing effect function increases as yij varies from zero to m(j). And the smaller yij is, the faster sensing effect function increases with the yij growth. The larger yij is, the more slowly sensing effect function increases with the yij growth.To obtain optimized sensing effect, we aim to maximize the sensing effect function in (1) with a local constraint which means the sensing effect of channel i in location j is no less than a threshold H. The local constraint can be described as(2)fi,j≥Hi∈1,Nj,j∈1,M.There are some factors which should be considered as follows.For the mobile users, the remaining energy should be considered at first. Only when one mobile user’s remaining energy is higher than the threshold could the mobile user carry out the task of spectrum sensing. LetTh be the normalized threshold of the remaining energy,K denote the set of all mobile users, and ek be the remaining energy for a mobile user k. Then the energy constraint can be expressed as(3)ek≥Thk∈K.LetM denote the number of locations needed to be sensed. For a location j, only the mobile users in that location can sense the channels within that location. We assume a mobile user can only sense one channel. In location j, let K(j) denote the set of mobile users, n(j) denote the number of mobile users, and N(j) denote the number of channels that should be sensed. For the mobile user k∈K(j), xki=1 denotes that the channel i is sensed by mobile user k and xki=0 denotes that the channel i is not sensed by mobile user k. Then considering a mobile user can only sense one channel, another constraint can be expressed as (4)∑k∈Kj∑i=1Njxki≤nj.Additionally, the incentive scheme allows FC to pay for the mobile users that try to sense channels. However, the cost of crowdsensing must be in the acceptable range. LetC be the maximum cost that can be paid for the sensing users and ck be the cost for the mobile user k∈K(j). The constraint can be expressed as (5)∑j=1M∑k∈Kjck∑i=1Njxki≤C.The optimal object of crowdsensing task assignment can be described as(6)max∑j=1M∑i=1Njwijfi,jsubject tofi,j≥H,i∈1,Nj,j∈1,Mek≥Th,k∈K∑k∈Kj∑i=1Njxki≤nj∑j=1M∑k∈Kjck∑i=1Njxki≤C∑j=1M∑i=1Njwij=1.Figure1 depicts an example of crowdsensing task assignment. There are two locations and three channels in the system. Each location is divided into three sublocations. Mobile users in different sublocations may obtain different sensing results about the same channel. Since the local constraint is not satisfied or the remaining energy is not enough or the cost is too high, some mobile users are not assigned sensing task. Other users are assigned channels to sense according to formula (6).Figure 1
An example of crowdsensing task assignment.


### 3.2. NP-Hardness

The problem of crowdsensing task assignment is difficult to solve since we prove this problem is NP-hard. The reason is that the problem of crowdsensing task assignment is as hard as maximum coverage problem which is NP-hard [21].The maximum coverage problem is described as follows: given a numberd and a collection of l sets S={S1,S2,…,Sl}, the maximum coverage problem is to select at most d of these sets to form S′ such that the maximum number of elements is covered:(7)maxS′USi∈S′Si,s.t.S′⊆S,S′≤d.Theorem 1.
The problem of crowdsensing task assignment is NP-hard.Proof.
By showing a special case of crowdsensing task assignment is as hard as maximum coverage problem, we prove that the problem of crowdsensing task assignment is NP-hard.
The special case is described as follows: each mobile user has enough energy to carry out spectrum sensing, the local thresholdH is set to zero that means the local constraint is satisfied, and the cost of crowdsensing is in the acceptable range. There are K mobile users and M locations in the system. And, in each location, there are N channels that should be sensed. Each mobile user is denoted by i∈{1,2,…,K}. Then K mobile users can form 2K sets such as {1}, {1,2}, and {1,2,3}. Let the nonnegative weight wij be a constant. Then (6) can be rewritten as (8)max⁡∑j=1M∑i=1Nfi,j.
Letl equal 2K and d equal MN. Equation (8) means selecting d sets from l sets to maximize the sum of f(i,j). Compared to (7), it is at least as hard as the maximum coverage problem which is NP-hard. In other words, the special case of crowdsensing task assignment is NP-hard.
The problem of crowdsensing task assignment is no easier than the special case. Therefore, the problem of crowdsensing task assignment is NP-hard.


## 3.1. Problem Formulation

We assume that there are many locations needed to be sensed. In each location, there are many channels that needed sensing. By crowdsensing task assignment, we aim to maximize the sensing effect with a local constraint.LetM denote the number of locations needed to be sensed and N(j) denote the number of channels that should be sensed in a location j. In the location j, shadowing, multipath fading, and other issues may influence the sensing results of mobile users in different positions of this location. In other words, mobile users may obtain different sensing results in the same location since they are at different positions. Therefore, location j may be divided into several sublocations. The spatial diversity can be captured by the sensing outcomes of mobile users in different sublocations. In a sublocation h of location j, zihj=1 denotes that there is at least one mobile user sensing channel i, and zihj=0 denotes that there are no mobile users sensing channel i. In location j, let yij denote the number of sublocations where channel i is sensed by at least one mobile user. We can derive yij=∑h=1m(j)zhji, where m(j) denotes the number of sublocations in location j. Obviously, the higher yij is, the more effective the sensing result is. When yij equals zero, there is no sensing effect. When yij equals m(j), the maximized sensing effect is reached. We can imagine that sensing effect increases fast as yij increases when yij is small, while sensing effect increases slowly as yij increases when yij is large. Let fi,j=yij/mj denote the sensing effect of channel i in location j. Then we can design the sensing effect function for the crowdsensing task assignment as follows: (1)∑j=1M∑i=1Njwijfi,j,where wij denotes the nonnegative weight with ∑j=1M∑i=1N(j)wij=1, and wij could distinguish the important degrees of sensing channels in each location. According to formula (1), the sensing effect function increases as yij varies from zero to m(j). And the smaller yij is, the faster sensing effect function increases with the yij growth. The larger yij is, the more slowly sensing effect function increases with the yij growth.To obtain optimized sensing effect, we aim to maximize the sensing effect function in (1) with a local constraint which means the sensing effect of channel i in location j is no less than a threshold H. The local constraint can be described as(2)fi,j≥Hi∈1,Nj,j∈1,M.There are some factors which should be considered as follows.For the mobile users, the remaining energy should be considered at first. Only when one mobile user’s remaining energy is higher than the threshold could the mobile user carry out the task of spectrum sensing. LetTh be the normalized threshold of the remaining energy,K denote the set of all mobile users, and ek be the remaining energy for a mobile user k. Then the energy constraint can be expressed as(3)ek≥Thk∈K.LetM denote the number of locations needed to be sensed. For a location j, only the mobile users in that location can sense the channels within that location. We assume a mobile user can only sense one channel. In location j, let K(j) denote the set of mobile users, n(j) denote the number of mobile users, and N(j) denote the number of channels that should be sensed. For the mobile user k∈K(j), xki=1 denotes that the channel i is sensed by mobile user k and xki=0 denotes that the channel i is not sensed by mobile user k. Then considering a mobile user can only sense one channel, another constraint can be expressed as (4)∑k∈Kj∑i=1Njxki≤nj.Additionally, the incentive scheme allows FC to pay for the mobile users that try to sense channels. However, the cost of crowdsensing must be in the acceptable range. LetC be the maximum cost that can be paid for the sensing users and ck be the cost for the mobile user k∈K(j). The constraint can be expressed as (5)∑j=1M∑k∈Kjck∑i=1Njxki≤C.The optimal object of crowdsensing task assignment can be described as(6)max∑j=1M∑i=1Njwijfi,jsubject tofi,j≥H,i∈1,Nj,j∈1,Mek≥Th,k∈K∑k∈Kj∑i=1Njxki≤nj∑j=1M∑k∈Kjck∑i=1Njxki≤C∑j=1M∑i=1Njwij=1.Figure1 depicts an example of crowdsensing task assignment. There are two locations and three channels in the system. Each location is divided into three sublocations. Mobile users in different sublocations may obtain different sensing results about the same channel. Since the local constraint is not satisfied or the remaining energy is not enough or the cost is too high, some mobile users are not assigned sensing task. Other users are assigned channels to sense according to formula (6).Figure 1
An example of crowdsensing task assignment.


## 3.2. NP-Hardness

The problem of crowdsensing task assignment is difficult to solve since we prove this problem is NP-hard. The reason is that the problem of crowdsensing task assignment is as hard as maximum coverage problem which is NP-hard [21].The maximum coverage problem is described as follows: given a numberd and a collection of l sets S={S1,S2,…,Sl}, the maximum coverage problem is to select at most d of these sets to form S′ such that the maximum number of elements is covered:(7)maxS′USi∈S′Si,s.t.S′⊆S,S′≤d.Theorem 1.
The problem of crowdsensing task assignment is NP-hard.Proof.
By showing a special case of crowdsensing task assignment is as hard as maximum coverage problem, we prove that the problem of crowdsensing task assignment is NP-hard.
The special case is described as follows: each mobile user has enough energy to carry out spectrum sensing, the local thresholdH is set to zero that means the local constraint is satisfied, and the cost of crowdsensing is in the acceptable range. There are K mobile users and M locations in the system. And, in each location, there are N channels that should be sensed. Each mobile user is denoted by i∈{1,2,…,K}. Then K mobile users can form 2K sets such as {1}, {1,2}, and {1,2,3}. Let the nonnegative weight wij be a constant. Then (6) can be rewritten as (8)max⁡∑j=1M∑i=1Nfi,j.
Letl equal 2K and d equal MN. Equation (8) means selecting d sets from l sets to maximize the sum of f(i,j). Compared to (7), it is at least as hard as the maximum coverage problem which is NP-hard. In other words, the special case of crowdsensing task assignment is NP-hard.
The problem of crowdsensing task assignment is no easier than the special case. Therefore, the problem of crowdsensing task assignment is NP-hard.


## 4. The Optimal Algorithm Based on PSO

Since the crowdsensing task assignment problem is NP-hard, we design the optimal algorithm based on particle swarm optimization (PSO) to solve this problem in this section. The PSO algorithm is good at NP-hard problem optimization [22]. The PSO algorithm is described at first. Then the optimal algorithm based on PSO is proposed. And time complexity is analyzed.


### 4.1. PSO Algorithm

In the PSO algorithm [23], each particle flies in the search space with certain speed. During the flight, a particle changes its flight experience with its companions. Therefore, each particle can fly to a better solution region based on this mechanism. Let Vid denote the particle speed and Xid denote the particle’s position. The movement of the particle is described as follows:(9)Vidt+1=wVidt+c1r1Pid-Xidt+c2r2Pgd-Xidt(10)Xidt+1=Vidt+1+Xidt,where w denotes the inertia weight, Pid denotes this particle’s historical best position, and Pgd denotes the global best position. Both r1 and r2 are independent in the range [0,1], and both c1 and c2 are study factors. The inertia weight w makes the algorithm improve its performance according to a series of applications. Formulas (9) and (10) calculate the current particle’s velocity and position, respectively.


### 4.2. Crowdsensing Task Assignment Algorithm Based on PSO

We design an optimal algorithm based on PSO to solve crowdsensing task assignment. According to PSO algorithm, each particle’s position represents a solution to the crowdsensing task assignment problem. It can be denoted by a matrix as follows.When there areN(j) channels in location j∈[1,M], the total number of sensing channels is ∑j=1MN(j) in all locations. Let K denote the number of mobile users. Then each particle is defined as a K×∑j=1MN(j) matrix X, where X[a][b]=1 denotes that the mobile user a chooses channel b to sense, and X[a][b]=0 denotes that the mobile user a does not choose channel b to sense.We optimize the crowdsensing task assignment based on PSO algorithm (PSO-CTA). The optimized algorithm is described as follows. Initializeq particles randomly, and each particle denotes a solution of crowdsensing task assignment of all K mobile users. Then we set the particle with the highest objective function based on formulas (6) to be the current best solution. According to the PSO algorithm, we use the PSO formulas (9) to merge the crowdsensing task assignment and determine the new particle position until it converges or this swarm obtains its longest lifetime. If PSO-CTA converges, the best solution can be obtained. The proposed algorithm is described as follows.Initialization. The first important problem to be solved is how the algorithm initially produces the particles. We produce a random particle as follows.For a mobile user, its remaining energy should be considered at first. If its remaining energy is higher than the threshold, the mobile user could carry out the task of spectrum sensing. Then it chooses a channel to sense randomly in its corresponding locations. All mobile users with enough energy choose channels like this. If the local constraint of sensing effect in (2) is satisfied in each location, the cost should be considered next. Otherwise, this particle should be generated again. If the cost for the mobile users which carry out spectrum sensing is lower than the maximum cost C, the process of initialization is completed. If the cost for the mobile users which carry out spectrum sensing is higher than the maximum cost C, FC will not assign sensing task to some mobile users to satisfy the cost constraint. At first, when there are multiple users sensing a channel in the same sublocation, FC will only choose a user with lower cost to assign sensing task, and other users are given up. According to our model, the sensing effect will not change. If the cost constraint is satisfied, the initialization is completed. Otherwise, FC should continue to give up users in the sublocations with less weight until the cost constraint is satisfied. Then a K×∑j=1MN(j) matrix X is generated corresponding to this particle.Initializeq particles randomly, and each particle denotes a solution of crowdsensing task assignment of all K mobile users.Optimizing Process. After each spectrum sensing instance of a mobile user, its energy will decrease. A mobile user should determine that its remaining energy meets the energy constraint. If its remaining energy is higher than the threshold, the mobile user is able to carry out spectrum sensing again. If its remaining energy is lower than the threshold, the mobile user could not carry out spectrum sensing from now on. For each particle, if a mobile user’s energy is not enough to carry out spectrum sensing, the user’s row vector is set to zero in the corresponding matrix. Then the matrix of a particle will change.Based on the current matrix, the crowdsensing effect function of the particle is obtained following (1). After calculating all particles’ effect function, we can derive a particle’s historical best position Pid and the global best position Pgd. The best position corresponds to the maximized crowdsensing effect function.According to a particle’s historical best positionPid and the global best position Pgd, we merge the matrixes to optimize the sensing task assignment. LetT1 denote the current matrix of a particle andT2 andT3 denote historical best solution of the particle and the global best solution, respectively. The merging matrix can be described as the combination ofT1,T2, andT3. Then we optimized the merging matrix as follows.In the merging matrix, if a channel in a sublocation is sensed by multiple users, only one user with higher energy is reserved and other users are given up. That means only an element is set to one in the column vector of the merging matrix after optimization. If a user chooses different channels to sense inT1,T2, andT3, there are more than elements set to one in the row vector of the merging matrix. Considering the global property of PSO, we optimize the row vectors of the merging matrix with specific probability decided by the parameters in (9) to guarantee the search space. If a mobile user chooses different channels in these three matrixes, the user will select the channel inT1 based on the probability w/(w+c1+c2), select the channel inT2 based on the probability c1/(w+c1+c2), and select the channel inT3 based on the probability c2/(w+c1+c2). That means only an element is set to one in the row vector of the merging matrix after optimization. The search space and converging speed of this algorithm can be adjusted by adjusting the values of w, c1, and c2.The proposed algorithm for crowdsensing task assignment problem is described in Algorithms1, 2, and 3.Algorithm 1:Overall procedure of proposed PSO-CTA.
Input:
Objective function according to formula (6);
A local constraintH;
The number of mobile usersK;
The number of locationsM;
The number of channelsN(j) in location j;
The number of sub-locationsm(j) in location j;
The maximum costC;
The maximal generationT;
Output: The maximum sensing effect function and sensing task assignment
Initialization:
Randomly generate each particle;
Optimization:
(1) repeat
(2) foreach particle
(3)  Optimizing the crowdsensing task assignment of the particle;
(4)  Update the Pid;
(5)  Update the Pgd;
(6) end for
(7) untilstopping criterion is satisfiedAlgorithm 2:Random generation of each particle (initialization).
(
1
) foreach mobile user
(
2
)  ifits remaining energy satisfies formula (3)
(
3
)   It chooses a random channel;
(
4
)   elseit will not sense;
(
5
)  end if
(
6
) end for
(
7
) ifthe cost constraint is satisfied
(
8
)  The initialization is completed;
(
9
)  elsereserve a user sensing a same channel in a sub-location;
(
10
)
end if
(
11
)
ifthe cost constraint is satisfied
(
12
)   The initialization is completed;
(
13
)   elsegive up users less weight until the cost is satisfied;
(
14
)
end ifAlgorithm 3:Procedure of optimizing the sensing task assignment of the particle.
(
1
)  foreach particle
(
2
)   foreach mobile user
(
3
)    ifits remaining energy satisfies formula (3)
(
4
)     Maintain the matrix;
(
5
)     elseset the corresponding row vector to zero;
(
6
)    end if
(
7
)   end for
(
8
)   Then the current matrix T1 is derived;
(
9
)    Evaluate the crowdsensing effect function of this particle;
(
10
)   Obtainthis particle’s Pid (matrix T2) based on crowdsensing effect function;
(
11
)   Obtain Pgd (matrix T3) with the optimal Pid;
(
12
)   Merge matrix T1, T2, T3;
(
13
)   Optimize the column vectors of the merging matrix;
(
14
)   Optimize row vectors of the merging matrix with specific probability using (9);
(
15
)   Evaluate the crowdsensing effect function of merging matrix according to (6);
(
16
)
end for


### 4.3. Analysis of Time Complexity

The complexity of proposed PSO-CTA algorithm is computed as follows. The computation complexity isO(n×N×q) in the initialization stage, where n denotes the number of mobile users, N denotes the number of channels, and q denotes the number of particles.In Line(3) of Algorithm 1, optimizing the sensing task assignment which is described in Algorithm 3 dominates the complexity of our algorithm. Then we focus on the computation complexity of optimizing the sensing task assignment. In a particle, the mobile users satisfying formulas (2), (3), (4), and (5) should be chosen, and the chosen mobile users are combined to obtain the maximized sensing effect function. Therefore, the complexity of a particle is O(n2×N). The complexity of all particles is O(n2×N×q) at the stage of evaluating sensing effect function.When particles update their velocities and positions, the computation complexity isO(n×q) in Lines (4)–(7) of Algorithm 1. Therefore, the computation complexity of the whole algorithm is O(n2×N×q).


## 4.1. PSO Algorithm

In the PSO algorithm [23], each particle flies in the search space with certain speed. During the flight, a particle changes its flight experience with its companions. Therefore, each particle can fly to a better solution region based on this mechanism. Let Vid denote the particle speed and Xid denote the particle’s position. The movement of the particle is described as follows:(9)Vidt+1=wVidt+c1r1Pid-Xidt+c2r2Pgd-Xidt(10)Xidt+1=Vidt+1+Xidt,where w denotes the inertia weight, Pid denotes this particle’s historical best position, and Pgd denotes the global best position. Both r1 and r2 are independent in the range [0,1], and both c1 and c2 are study factors. The inertia weight w makes the algorithm improve its performance according to a series of applications. Formulas (9) and (10) calculate the current particle’s velocity and position, respectively.


## 4.2. Crowdsensing Task Assignment Algorithm Based on PSO

We design an optimal algorithm based on PSO to solve crowdsensing task assignment. According to PSO algorithm, each particle’s position represents a solution to the crowdsensing task assignment problem. It can be denoted by a matrix as follows.When there areN(j) channels in location j∈[1,M], the total number of sensing channels is ∑j=1MN(j) in all locations. Let K denote the number of mobile users. Then each particle is defined as a K×∑j=1MN(j) matrix X, where X[a][b]=1 denotes that the mobile user a chooses channel b to sense, and X[a][b]=0 denotes that the mobile user a does not choose channel b to sense.We optimize the crowdsensing task assignment based on PSO algorithm (PSO-CTA). The optimized algorithm is described as follows. Initializeq particles randomly, and each particle denotes a solution of crowdsensing task assignment of all K mobile users. Then we set the particle with the highest objective function based on formulas (6) to be the current best solution. According to the PSO algorithm, we use the PSO formulas (9) to merge the crowdsensing task assignment and determine the new particle position until it converges or this swarm obtains its longest lifetime. If PSO-CTA converges, the best solution can be obtained. The proposed algorithm is described as follows.Initialization. The first important problem to be solved is how the algorithm initially produces the particles. We produce a random particle as follows.For a mobile user, its remaining energy should be considered at first. If its remaining energy is higher than the threshold, the mobile user could carry out the task of spectrum sensing. Then it chooses a channel to sense randomly in its corresponding locations. All mobile users with enough energy choose channels like this. If the local constraint of sensing effect in (2) is satisfied in each location, the cost should be considered next. Otherwise, this particle should be generated again. If the cost for the mobile users which carry out spectrum sensing is lower than the maximum cost C, the process of initialization is completed. If the cost for the mobile users which carry out spectrum sensing is higher than the maximum cost C, FC will not assign sensing task to some mobile users to satisfy the cost constraint. At first, when there are multiple users sensing a channel in the same sublocation, FC will only choose a user with lower cost to assign sensing task, and other users are given up. According to our model, the sensing effect will not change. If the cost constraint is satisfied, the initialization is completed. Otherwise, FC should continue to give up users in the sublocations with less weight until the cost constraint is satisfied. Then a K×∑j=1MN(j) matrix X is generated corresponding to this particle.Initializeq particles randomly, and each particle denotes a solution of crowdsensing task assignment of all K mobile users.Optimizing Process. After each spectrum sensing instance of a mobile user, its energy will decrease. A mobile user should determine that its remaining energy meets the energy constraint. If its remaining energy is higher than the threshold, the mobile user is able to carry out spectrum sensing again. If its remaining energy is lower than the threshold, the mobile user could not carry out spectrum sensing from now on. For each particle, if a mobile user’s energy is not enough to carry out spectrum sensing, the user’s row vector is set to zero in the corresponding matrix. Then the matrix of a particle will change.Based on the current matrix, the crowdsensing effect function of the particle is obtained following (1). After calculating all particles’ effect function, we can derive a particle’s historical best position Pid and the global best position Pgd. The best position corresponds to the maximized crowdsensing effect function.According to a particle’s historical best positionPid and the global best position Pgd, we merge the matrixes to optimize the sensing task assignment. LetT1 denote the current matrix of a particle andT2 andT3 denote historical best solution of the particle and the global best solution, respectively. The merging matrix can be described as the combination ofT1,T2, andT3. Then we optimized the merging matrix as follows.In the merging matrix, if a channel in a sublocation is sensed by multiple users, only one user with higher energy is reserved and other users are given up. That means only an element is set to one in the column vector of the merging matrix after optimization. If a user chooses different channels to sense inT1,T2, andT3, there are more than elements set to one in the row vector of the merging matrix. Considering the global property of PSO, we optimize the row vectors of the merging matrix with specific probability decided by the parameters in (9) to guarantee the search space. If a mobile user chooses different channels in these three matrixes, the user will select the channel inT1 based on the probability w/(w+c1+c2), select the channel inT2 based on the probability c1/(w+c1+c2), and select the channel inT3 based on the probability c2/(w+c1+c2). That means only an element is set to one in the row vector of the merging matrix after optimization. The search space and converging speed of this algorithm can be adjusted by adjusting the values of w, c1, and c2.The proposed algorithm for crowdsensing task assignment problem is described in Algorithms1, 2, and 3.Algorithm 1:Overall procedure of proposed PSO-CTA.
Input:
Objective function according to formula (6);
A local constraintH;
The number of mobile usersK;
The number of locationsM;
The number of channelsN(j) in location j;
The number of sub-locationsm(j) in location j;
The maximum costC;
The maximal generationT;
Output: The maximum sensing effect function and sensing task assignment
Initialization:
Randomly generate each particle;
Optimization:
(1) repeat
(2) foreach particle
(3)  Optimizing the crowdsensing task assignment of the particle;
(4)  Update the Pid;
(5)  Update the Pgd;
(6) end for
(7) untilstopping criterion is satisfiedAlgorithm 2:Random generation of each particle (initialization).
(
1
) foreach mobile user
(
2
)  ifits remaining energy satisfies formula (3)
(
3
)   It chooses a random channel;
(
4
)   elseit will not sense;
(
5
)  end if
(
6
) end for
(
7
) ifthe cost constraint is satisfied
(
8
)  The initialization is completed;
(
9
)  elsereserve a user sensing a same channel in a sub-location;
(
10
)
end if
(
11
)
ifthe cost constraint is satisfied
(
12
)   The initialization is completed;
(
13
)   elsegive up users less weight until the cost is satisfied;
(
14
)
end ifAlgorithm 3:Procedure of optimizing the sensing task assignment of the particle.
(
1
)  foreach particle
(
2
)   foreach mobile user
(
3
)    ifits remaining energy satisfies formula (3)
(
4
)     Maintain the matrix;
(
5
)     elseset the corresponding row vector to zero;
(
6
)    end if
(
7
)   end for
(
8
)   Then the current matrix T1 is derived;
(
9
)    Evaluate the crowdsensing effect function of this particle;
(
10
)   Obtainthis particle’s Pid (matrix T2) based on crowdsensing effect function;
(
11
)   Obtain Pgd (matrix T3) with the optimal Pid;
(
12
)   Merge matrix T1, T2, T3;
(
13
)   Optimize the column vectors of the merging matrix;
(
14
)   Optimize row vectors of the merging matrix with specific probability using (9);
(
15
)   Evaluate the crowdsensing effect function of merging matrix according to (6);
(
16
)
end for


## 4.3. Analysis of Time Complexity

The complexity of proposed PSO-CTA algorithm is computed as follows. The computation complexity isO(n×N×q) in the initialization stage, where n denotes the number of mobile users, N denotes the number of channels, and q denotes the number of particles.In Line(3) of Algorithm 1, optimizing the sensing task assignment which is described in Algorithm 3 dominates the complexity of our algorithm. Then we focus on the computation complexity of optimizing the sensing task assignment. In a particle, the mobile users satisfying formulas (2), (3), (4), and (5) should be chosen, and the chosen mobile users are combined to obtain the maximized sensing effect function. Therefore, the complexity of a particle is O(n2×N). The complexity of all particles is O(n2×N×q) at the stage of evaluating sensing effect function.When particles update their velocities and positions, the computation complexity isO(n×q) in Lines (4)–(7) of Algorithm 1. Therefore, the computation complexity of the whole algorithm is O(n2×N×q).


## 5. Simulation Results

The proposed PSO-CTA algorithm is evaluated by simulations. The average solution is obtained by running the algorithm 100 times. We compare our PSO-CTA algorithm with the algorithm in [14]. The simulation parameters are described as follows. There are some locations needed to be sensed, with the same radius. Each location is equally divided into 3 sublocations. The whole number of channels is N=5. The local threshold H is set to 0.57. The nonnegative weight of wij is identical for each channel and each location. Mobile users are deployed randomly in the locations.Figure2 shows the crowdsensing effect outcomes as the number of locations varies from 15 to 40 when there are 50 mobile users. The cost values of ck are chosen from {1;2;3;…;49;50}. The maximum cost is C=a∑k=150ck, where a equals 0.6 and 0.8, respectively. The normalized energy threshold of Th is set to 0.2 and 0.5, respectively. The crowdsensing effect function could be obtained based on (1). This function reflects the sensing effect and its value is between 0 and 1. The closer the value is to 1, the better the sensing effect is. Compared to the DRA algorithm in [13] and the budget algorithm in [14], our proposed PSO-CTA algorithm achieves higher crowdsensing effect function. As the number of locations increases, the crowdsensing effect function decreases. The reason is that more locations lead to more sublocations and fixed number of mobile users cannot sense all sublocations. When Th equals 0.2 and a equals 0.8, the crowdsensing effect function obtained is higher than those obtained when Th and a equal other values, since there are more mobile users assigned to sense channels with Th=0.2 and a=0.8.Figure 2
Crowdsensing effect function with 50 mobile users.Figure3 shows the crowdsensing effect results as the number of mobile users varies from 20 to 70 when there are 20 locations. The cost values of ck are chosen from {1;2;3;…;L}, where L denotes the number of mobile users. The maximum cost is C=a∑k=1Lck, where a equals 0.6 and 0.8, respectively. The normalized energy threshold of Th is set to 0.2 and 0.5, respectively. Compared to the DRA algorithm in [13] and the budget algorithm in [14], our proposed PSO-CTA algorithm achieves higher crowdsensing effect function. As the number of mobile users increases, the crowdsensing effect function increases. The reason is that more sublocations could be sensed by more mobile users. When Th equals 0.2 and a equals 0.8, the crowdsensing effect function obtained is higher than those obtained when Th and a equal other values, since there are more mobile users assigned to sense channels with Th=0.2 and a=0.8.Figure 3
Crowdsensing effect function with 20 locations.Figure4 shows the average remaining energy of mobile users as the number of spectrum sensing instances increases when there are 50 mobile users deployed randomly in 15 locations. It is assumed that the initial average energy of each user is 0.6. And after each spectrum sensing instance, a mobile user’s energy falls 0.5%. The normalized energy threshold Th is set to 0.5 and 0.3, respectively. As shown in Figure 4, our proposed PSO-CTA algorithm achieves higher remaining energy of mobile users than the other algorithms. And we can see that the remaining energy will be higher when the threshold of Th is set to a higher value.Figure 4
Average remaining energy with the number of spectrum sensing instances.It is assumed that there are four channels and three locations which can be divided into three sublocations. The nonnegative weight is not identical for each channel. We set the weights equal to 0.3, 0.3, 0.3, and 0.1 for these four channels. Under the aforementioned conditions, the local sensing effect for the fourth channel (weight equaling 0.1) is shown in Figure5. When there are not so many users in the system, the fourth channel is not sensed for the budget algorithm and DRA algorithm as the weight is too small to increase the global sensing effect. In the proposed PSO-CTA algorithm, the fourth channel should be sensed because a local constraint is set. Any channel, no matter what its weight equals, should be sensed. Therefore, no channel will be omitted with the PSO-CTA algorithm.Figure 5
Local sensing effect with weight equaling 0.1 for three locations.When there are 40 users, Figure6 shows the local sensing effect for the fourth channel as the number of locations increases. There will not be enough users to sense each channel if the number of locations increases. Thus, the budget algorithm and DRA algorithm may choose the channels with higher weights to improve the global sensing effect. Therefore, the local sensing effect for the fourth channel will decrease. However, the proposed PSO-CTA algorithm will not ignore the fourth channel due to the local constraint.Figure 6
Local sensing effect with weight equaling 0.1 for 40 users.


## 6. Conclusion

For a large-scale region, this paper proposes the crowdsourcing method to assign the spectrum sensing task to many mobile users such as smartphones and pads. Considering some constraints such as remaining energy, locations, and costs of mobile users, we propose a sensing effect function with a local constraint and aim to maximize the sensing effect function. Since the problem of sensing task assignment is proved to be NP-hard, we design an optimal algorithm based on PSO to solve this problem. Simulation results show our algorithm achieves higher performance than the other algorithms.



---

*Source: 4687974-2017-09-11.xml*