# Modeling and Optimization of RFID Networks Planning Problem

Authors: Hongshan Kong; Bin Yu
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Aimed at solving the RFID networks planning problem, a mathematical model considering tag coverage and reader interference is presented. The DEEPSO algorithm that adds differential evolution and evolutionary strategies to the standard PSO is introduced to the optimization of RFID Networks Planning, which can improve the global convergence ability and particle diversity and can avoid falling into local convergence. According to the simulation results, compared with RFID networks planning by standard PSO, RFID networks planning by DEEPSO is superior.


---

## Body

## 1. Introduction

Radio frequency identification (RFID) technology has been widely applied to asset tracking, smart grid, car manufacturing, and supply chain management. The basic components of RFID system are tags and readers. Readers gain access to the information stored on the tags within a distance of several meters [1]. Then, readers and tags need to be deployed in the working area, which must consider several practical problems, such as the tag coverage, the cost efficiency, and the quality of service (QoS) [2]. The RFID network planning (RNP) problem aims to optimize a set of objectives by adjusting the control variables of the system and RNP is a difficult NP problem [3]. Because RNP is a large-scale, high-dimensional nonlinear optimization problem with large number of uncertain parameters, it cannot be tackled by the traditional techniques [4].Metaheuristic is an efficient approach for hard optimization problems. For solving the RNP problem, evolutionary computation and swarm intelligence techniques have been applied, such as genetic algorithms [5], evolutionary strategy [6], particle swarm optimization (PSO) algorithms [7, 8], firefly algorithms [9], artificial bee colony algorithms [2], and bacterial foraging algorithms [10]. However, with the increasing number of the deployed readers and tags in the large-scale RFID deployment environment, the degree of complexity for solving the RNP optimization increases exponentially. The previous methods to solve the RNP optimization are incompetent for being prone to premature convergence.For avoiding premature convergence, the idea of heuristic algorithm has been developed into an important and effective way to improve the optimization performance, which can combine the advantages of various algorithms. In [11], a hybrid algorithm combining genetic algorithm and particle swarm optimization is proposed and applied RNP optimization. In [12], a hybrid algorithm combining genetic algorithm and artificial bee colony algorithm is proposed and applied RNP optimization. DEEPSO [13] is a hybrid algorithm based on PSO combining differential evolution and evolutionary computation, which was the winner in 2014 of the competition on the application of modern heuristic optimization algorithms for solving optimal power flow problems [14]. For increasing the optimization performance of RFID Networks Planning, the DEEPSO algorithm is introduced and applied.The rest of the paper is organized as follows. In Section2, RFID network planning problem and Mathematical model are presented. Section 3 first gives a review of the DEEPSO algorithm and then proposes the realization method of RFID network planning problem using DEEPSO. In Section 4, the simulation experiments and results analysis of RFID network planning problem using DEEPSO are presented. Finally, Section 5 outlines the conclusions.


## 2. RFID Network Planning Problem and Modeling

### 2.1. Problem Description

The key components of an RFID system are the tags and readers. The RFID tag, which is attached to the item to be tracked, stores the unique identification number of the item using a small integrated circuit. The RFID readers communicate with the tags by reading the information stored on them. The reader has a limit on its interrogation range, within which the tags can be read. Thus, the RFID network planning problem is a difficult problem that needs to be solved in order to deploy and operate the large-scale network of RFID readers in an optimal fashion. Consider the following:(1)
The monitoring area is a two-dimensional plane(2)
An appropriate amount of tags are randomly placed in the area(3)
The coverage of the reader is a circular area centered(4)
The readers are isomorphic with the same perceived radius(5)
The reader can be moved and the energy is sufficient to ensure that the final positional movement is completed


### 2.2. Mathematical Model

The symbols and declarations of the mathematical model are shown in Table1.Table 1
The symbols and declarations.
Symbol
Declaration
N
t
The number of tags
t
i
The coordinates ofith tag, ti=xti,yti
N
r
The number of readers
r
k
The coordinates ofkth reader, rk=xrk,yrk
R
The sensing radius of reader
d
t
i
,
r
k
The distance between theith tag and the kth readerThe first objective functionfc represents the tag coverage, which is the most important in an RFID system. If the distance between the ith tag and the kth reader is smaller than the sensing radius of reader, the communication between the ith tag and the kth reader can be established. Then the function is formulated as(1)maxfc=1Nt⋅∑i=1Nt∑k=1Nrp1ti,rk,where(2)p1ti,rk=1,ifdti,rk≤R,0,else.The second objective functionfi represents the reader interference. Reader collision mainly occurs in a dense reader environment, where several readers try to interrogate tags at the same time, which results in an unacceptable level of misreads. The objective function is formulated as(3)minfi=1Nt⋅∑i=1Ntp2ti,where(4)p2ti=1,if∑k=1Ntp1ti,rk≥2,0,else.In order to align with the first objective optimization direction, modify (3) into the following formula:(5)maxfi′=1∑i=1Ntp2ti+1⋅Then, the RNP problem concerns the tag coverage and the reader interference that are formulated as follows:(6)maxf=wcfc+wifi′,wc+wi=1.


## 2.1. Problem Description

The key components of an RFID system are the tags and readers. The RFID tag, which is attached to the item to be tracked, stores the unique identification number of the item using a small integrated circuit. The RFID readers communicate with the tags by reading the information stored on them. The reader has a limit on its interrogation range, within which the tags can be read. Thus, the RFID network planning problem is a difficult problem that needs to be solved in order to deploy and operate the large-scale network of RFID readers in an optimal fashion. Consider the following:(1)
The monitoring area is a two-dimensional plane(2)
An appropriate amount of tags are randomly placed in the area(3)
The coverage of the reader is a circular area centered(4)
The readers are isomorphic with the same perceived radius(5)
The reader can be moved and the energy is sufficient to ensure that the final positional movement is completed


## 2.2. Mathematical Model

The symbols and declarations of the mathematical model are shown in Table1.Table 1
The symbols and declarations.
Symbol
Declaration
N
t
The number of tags
t
i
The coordinates ofith tag, ti=xti,yti
N
r
The number of readers
r
k
The coordinates ofkth reader, rk=xrk,yrk
R
The sensing radius of reader
d
t
i
,
r
k
The distance between theith tag and the kth readerThe first objective functionfc represents the tag coverage, which is the most important in an RFID system. If the distance between the ith tag and the kth reader is smaller than the sensing radius of reader, the communication between the ith tag and the kth reader can be established. Then the function is formulated as(1)maxfc=1Nt⋅∑i=1Nt∑k=1Nrp1ti,rk,where(2)p1ti,rk=1,ifdti,rk≤R,0,else.The second objective functionfi represents the reader interference. Reader collision mainly occurs in a dense reader environment, where several readers try to interrogate tags at the same time, which results in an unacceptable level of misreads. The objective function is formulated as(3)minfi=1Nt⋅∑i=1Ntp2ti,where(4)p2ti=1,if∑k=1Ntp1ti,rk≥2,0,else.In order to align with the first objective optimization direction, modify (3) into the following formula:(5)maxfi′=1∑i=1Ntp2ti+1⋅Then, the RNP problem concerns the tag coverage and the reader interference that are formulated as follows:(6)maxf=wcfc+wifi′,wc+wi=1.


## 3. RFID Network Planning Optimization Based on DEEPSO

### 3.1. DEEPSO

Assumed in the spaceD, randomly initialize a population of particles P=p1,p2,…,pN with number of particles N. The position and velocity of the i particle are xi=xi1,xi2,…,xiDTand vi=vi1,vi2,…,viDT. The individual extremum of the population is expressed as besti=besti1,besti2,…,bestiDT, the global extremum is expressed as gbest=gbest1,gbest2,…,gbestDT, particles update speed, and position according to the following formula:(7)vk+1=wvik+c1⋅rand⋅bestik−xik+c2⋅rand⋅gbest−xik,(8)xik+1=xik+vik,in which k denotes the current generation, rand is a random number between (0, 1), c1 and c2 are acceleration constants, which represent the weight of particles moving toward individual extremum and global extremum, and w is the inertia coefficient, when w is larger, representations have stronger global search capabilities, when w is smaller, representations have stronger local search capabilities.The improvement of DEEPSO over PSO consists of using a recombination mechanism with Differential Evolution (DE) and using a self-adaptive recombination operator with Evolutionary Strategies (ES). On one hand, DEEPSO relies on the past information of optimization process to create new promising solutions and proposes the replacement of the individual memory by a collective memory to enable an improved sensitivity of the optimization landscape. On the other hand, DEEPSO has self-adaptive properties by a self-adaptive recombination operator. The DEEPSO movement rule based on classical PSO by replacing the memory term by the perception term as(9)vk+1=w1⋅vk+w2⋅bestrk−xk+w3⋅C⋅gbest∗−xk,in which w1, w2, and w3 represent inertia, memory, and cooperation weights, respectively, C is an N×N diagonal matrix of random variables that follow a Bernoulli distribution with success probability P, bestrk represents an individual from memory B that is computed every iteration according to one strategy of sampling in the same generation and sampling from the past bests, the superscript gbest∗ indicates that the parameter undergoes evolution under a mutation process:(10)gbest∗=gbest+τ⋅N0,1,where τ is the mutation rate and N0,1 is a number sampled from the standard Gaussian distribution.


### 3.2. RFID Network Planning Optimization Based on DEEPSO

When applying the DEEPSO algorithm to RFID network planning optimization, two problems must be solved: parameter coding and fitness function. Randomly deployingm nodes to the monitoring area can be seen as a continuous optimization problem. Each deployment scenario includes 2m elements, which represent the x coordinates and the y coordinates of m nodes. Define the fitness function of particles in the RFID network planning optimization algorithm as equation (6). Suppose the number of particles is N, each deployment scenario can be thought of as a particle. The goal of RFID network planning optimization is to find the particle that maximizes the fitness function value.To using DEEPSO to solve the RNP problem, the following steps should be taken and repeated.Step 1.
Initialization: There are RFID deployment parameters and simulation parameters. The deployment parameters consist of the shape, size, and dimension of the working area, the number of tagsNt, the coordinates of tags ti, the number of readers Nr, and the sensing radius of reader R. Simulation parameters consist of the positions xkii=1Nand the velocities vkii=1Nof particles, the inertia weight w1, the memory weight w2, and the cooperation weight w3, the success probability P, the mutation rate τ, and the simulation generation Gen.Step 2.
Evaluate: Calculate the fitness function values of all particles using equation (6), get the best individual gbest and memory B.Step 3.
Loop: Determine whether the generation number is smaller than the simulation generationGen. If so, firstly, compute the perception term bestrk for the current individual according to the perception strategy; secondly, copy the current individual; thirdly, mutate the strategic parameters gbest∗ of the copied individual according to (10); fourthly, move the current individual and its copy according to 8) and (9); lastly, evaluate the current individual and its copy, and update the best individual gbest and memory B. If not, stop the procedure.Step 4.
Termination: The results containing the coordinates of readers and the fitness values are given.


## 3.1. DEEPSO

Assumed in the spaceD, randomly initialize a population of particles P=p1,p2,…,pN with number of particles N. The position and velocity of the i particle are xi=xi1,xi2,…,xiDTand vi=vi1,vi2,…,viDT. The individual extremum of the population is expressed as besti=besti1,besti2,…,bestiDT, the global extremum is expressed as gbest=gbest1,gbest2,…,gbestDT, particles update speed, and position according to the following formula:(7)vk+1=wvik+c1⋅rand⋅bestik−xik+c2⋅rand⋅gbest−xik,(8)xik+1=xik+vik,in which k denotes the current generation, rand is a random number between (0, 1), c1 and c2 are acceleration constants, which represent the weight of particles moving toward individual extremum and global extremum, and w is the inertia coefficient, when w is larger, representations have stronger global search capabilities, when w is smaller, representations have stronger local search capabilities.The improvement of DEEPSO over PSO consists of using a recombination mechanism with Differential Evolution (DE) and using a self-adaptive recombination operator with Evolutionary Strategies (ES). On one hand, DEEPSO relies on the past information of optimization process to create new promising solutions and proposes the replacement of the individual memory by a collective memory to enable an improved sensitivity of the optimization landscape. On the other hand, DEEPSO has self-adaptive properties by a self-adaptive recombination operator. The DEEPSO movement rule based on classical PSO by replacing the memory term by the perception term as(9)vk+1=w1⋅vk+w2⋅bestrk−xk+w3⋅C⋅gbest∗−xk,in which w1, w2, and w3 represent inertia, memory, and cooperation weights, respectively, C is an N×N diagonal matrix of random variables that follow a Bernoulli distribution with success probability P, bestrk represents an individual from memory B that is computed every iteration according to one strategy of sampling in the same generation and sampling from the past bests, the superscript gbest∗ indicates that the parameter undergoes evolution under a mutation process:(10)gbest∗=gbest+τ⋅N0,1,where τ is the mutation rate and N0,1 is a number sampled from the standard Gaussian distribution.


## 3.2. RFID Network Planning Optimization Based on DEEPSO

When applying the DEEPSO algorithm to RFID network planning optimization, two problems must be solved: parameter coding and fitness function. Randomly deployingm nodes to the monitoring area can be seen as a continuous optimization problem. Each deployment scenario includes 2m elements, which represent the x coordinates and the y coordinates of m nodes. Define the fitness function of particles in the RFID network planning optimization algorithm as equation (6). Suppose the number of particles is N, each deployment scenario can be thought of as a particle. The goal of RFID network planning optimization is to find the particle that maximizes the fitness function value.To using DEEPSO to solve the RNP problem, the following steps should be taken and repeated.Step 1.
Initialization: There are RFID deployment parameters and simulation parameters. The deployment parameters consist of the shape, size, and dimension of the working area, the number of tagsNt, the coordinates of tags ti, the number of readers Nr, and the sensing radius of reader R. Simulation parameters consist of the positions xkii=1Nand the velocities vkii=1Nof particles, the inertia weight w1, the memory weight w2, and the cooperation weight w3, the success probability P, the mutation rate τ, and the simulation generation Gen.Step 2.
Evaluate: Calculate the fitness function values of all particles using equation (6), get the best individual gbest and memory B.Step 3.
Loop: Determine whether the generation number is smaller than the simulation generationGen. If so, firstly, compute the perception term bestrk for the current individual according to the perception strategy; secondly, copy the current individual; thirdly, mutate the strategic parameters gbest∗ of the copied individual according to (10); fourthly, move the current individual and its copy according to 8) and (9); lastly, evaluate the current individual and its copy, and update the best individual gbest and memory B. If not, stop the procedure.Step 4.
Termination: The results containing the coordinates of readers and the fitness values are given.


## 4. Simulation Experiment and Analysis

In order to measure the optimization performance of the proposed method, the MATLAB software was used to implement numerical simulation.


### 4.1. Simulation Experiment Environment and Parameter Settings

All the algorithms are evaluated against an ideal square working area (a 30 m∗ 30 m working space with 100 tags that distributed randomly), which is shown in Figure 1.Figure 1
The initial placement of square working area.The RFID reader has a working radius of 3 m and uses 10 RFID readers to collect data from the tags in the work area. The experiment uses PSO and DEEPSO to optimize the planning of the RFID reader network. The parameters are shown in Table2.Table 2
Simulation parameter setting.
Parameters
Setting values
Algorithms
N
50
PSO and DEEPSO
Gen
150
PSO and DEEPSO
c
1
1.467
PSO
c
2
1.467
PSO
w
0.729844
PSO
w
1
rand
DEEPSO
w
2
rand
DEEPSO
w
3
rand
DEEPSO
P
0.8
DEEPSO
τ
0.4
DEEPSO
ω
c
0.8
DEEPSO
ω
i
0.2
DEEPSOIn the work area, 50 deployment locations are randomly generated for 10 readers, respectively, and are the initial position values of the particles in the particle swarm algorithm, which corresponds to 50 deployment scenarios. The initial position values of the 50 particles are shown in Figure2.Figure 2
The initial position values of the 50 particles. (a) Reader 1. (b) Reader 2. (c) Reader 3. (d) Reader 4. (e) Reader 5. (f) Reader 6. (g) Reader 7. (h) Reader 8. (i) Reader 9. (j) Reader 10.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)In the 50 deployment scenarios, the best scenario is the 1st through calculating the fitness value, which is shown in Figure 3. The coordinates of the 10 readers are, respectively, (−4.28, 9.73), (−1.36, 1.48), (0.54, −6.05), (−6.69, −0.02), (9.80, −2.12), (4.28, −6.48), (−8.59, −6.85), (−6.77, −4.33), (0.73, 5.46), and (7.61, 2.75), and the function value is 51.6%.Figure 3
The best scenario of 50 deployment scenarios.A random number between two [−7, 7] is randomly generated as theX-axis velocity and the Y-axis velocity of each deployment position, the initial velocity value of the particles in the particle swarm algorithm, and the initial velocity of the readers 1 to 6 is shown in Figure 4.Figure 4
The initial velocity of the 50 particles in the readers 1 to 6. (a) Reader 1. (b) Reader 2. (c) Reader 3. (d) Reader 4. (e) Reader 5. (f) Reader 6.
(a)
(b)
(c)
(d)
(e)
(f)


### 4.2. Simulation Results and Analysis

The result of the RFID network planning simulation run once using standard PSO and DEEPSO is shown in Figures5 and 6.Figure 5
The simulation result of RFID network planning by the standard PSO.
(a)
(b)Figure 6
The simulation result of RFID network planning by DEEPSO.
(a)
(b)It can be seen from Figures5 and 6 that the distribution of readers after optimization is more reasonable. The coordinates of the 10 readers by the standard PSO are, respectively, (−4.96, 9.52), (0.09, 0.16), (−1.55, −5.49), (−5.21, −1.99), (9.93, −1.77), (5.02, −5.96), (−7.00, −9.30), (−5.13, −3.87), (−1.55, 5.16), and (8.27, 5.71), the optimization function value is 79.2% when the generation value is 35. The coordinates of the 10 readers by the DEEPSO are, respectively, (2.40, 4.45), (1.97, −1.2), (8.86, −3.15), (5.28, −0.48), (0.32, 8.20), (−0.59, −4.04), (−4.95, -7.87), (5.17, −7.47), (−5.26, 5.24), and (7.30, 4.73), the optimization function value is 81.6% when the generation value is 119. Compared with RFID networks planning using PSO, RFID networks planning using DEEPSO shows the better optimization performance, which makes the function value increase by 2.4%.In order to further verify the optimization performance of the proposed method, the simulation experiment environment and parameters remain unchanged, 50 independent optimization experiments are performed respectively. The performance comparison of the two methods is shown in Figure7.Figure 7
Comparison of two methods running 50 times.It can be seen from Figure7 that the min fitness value is 58.4%, the max fitness value is 84%, the mean fitness value is 77.36% in RNP by PSO, and the min fitness value is 72%, the max fitness value is 88%, the mean fitness value is 80.75% in RNP by DEEPSO. Comparing with RNP by PSO, the mean fitness value of RNP by DEEPSO can be improved by 3.39%. The simulation results show that the method of RNP by DEEPSO has the better optimization performance. This is because DEEPSO, which adds Differential Evolution (DE) and Evolutionary Strategies (ES) to the standard PSO, has continuous optimization ability, especially the later of the optimization process.


## 4.1. Simulation Experiment Environment and Parameter Settings

All the algorithms are evaluated against an ideal square working area (a 30 m∗ 30 m working space with 100 tags that distributed randomly), which is shown in Figure 1.Figure 1
The initial placement of square working area.The RFID reader has a working radius of 3 m and uses 10 RFID readers to collect data from the tags in the work area. The experiment uses PSO and DEEPSO to optimize the planning of the RFID reader network. The parameters are shown in Table2.Table 2
Simulation parameter setting.
Parameters
Setting values
Algorithms
N
50
PSO and DEEPSO
Gen
150
PSO and DEEPSO
c
1
1.467
PSO
c
2
1.467
PSO
w
0.729844
PSO
w
1
rand
DEEPSO
w
2
rand
DEEPSO
w
3
rand
DEEPSO
P
0.8
DEEPSO
τ
0.4
DEEPSO
ω
c
0.8
DEEPSO
ω
i
0.2
DEEPSOIn the work area, 50 deployment locations are randomly generated for 10 readers, respectively, and are the initial position values of the particles in the particle swarm algorithm, which corresponds to 50 deployment scenarios. The initial position values of the 50 particles are shown in Figure2.Figure 2
The initial position values of the 50 particles. (a) Reader 1. (b) Reader 2. (c) Reader 3. (d) Reader 4. (e) Reader 5. (f) Reader 6. (g) Reader 7. (h) Reader 8. (i) Reader 9. (j) Reader 10.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)In the 50 deployment scenarios, the best scenario is the 1st through calculating the fitness value, which is shown in Figure 3. The coordinates of the 10 readers are, respectively, (−4.28, 9.73), (−1.36, 1.48), (0.54, −6.05), (−6.69, −0.02), (9.80, −2.12), (4.28, −6.48), (−8.59, −6.85), (−6.77, −4.33), (0.73, 5.46), and (7.61, 2.75), and the function value is 51.6%.Figure 3
The best scenario of 50 deployment scenarios.A random number between two [−7, 7] is randomly generated as theX-axis velocity and the Y-axis velocity of each deployment position, the initial velocity value of the particles in the particle swarm algorithm, and the initial velocity of the readers 1 to 6 is shown in Figure 4.Figure 4
The initial velocity of the 50 particles in the readers 1 to 6. (a) Reader 1. (b) Reader 2. (c) Reader 3. (d) Reader 4. (e) Reader 5. (f) Reader 6.
(a)
(b)
(c)
(d)
(e)
(f)


## 4.2. Simulation Results and Analysis

The result of the RFID network planning simulation run once using standard PSO and DEEPSO is shown in Figures5 and 6.Figure 5
The simulation result of RFID network planning by the standard PSO.
(a)
(b)Figure 6
The simulation result of RFID network planning by DEEPSO.
(a)
(b)It can be seen from Figures5 and 6 that the distribution of readers after optimization is more reasonable. The coordinates of the 10 readers by the standard PSO are, respectively, (−4.96, 9.52), (0.09, 0.16), (−1.55, −5.49), (−5.21, −1.99), (9.93, −1.77), (5.02, −5.96), (−7.00, −9.30), (−5.13, −3.87), (−1.55, 5.16), and (8.27, 5.71), the optimization function value is 79.2% when the generation value is 35. The coordinates of the 10 readers by the DEEPSO are, respectively, (2.40, 4.45), (1.97, −1.2), (8.86, −3.15), (5.28, −0.48), (0.32, 8.20), (−0.59, −4.04), (−4.95, -7.87), (5.17, −7.47), (−5.26, 5.24), and (7.30, 4.73), the optimization function value is 81.6% when the generation value is 119. Compared with RFID networks planning using PSO, RFID networks planning using DEEPSO shows the better optimization performance, which makes the function value increase by 2.4%.In order to further verify the optimization performance of the proposed method, the simulation experiment environment and parameters remain unchanged, 50 independent optimization experiments are performed respectively. The performance comparison of the two methods is shown in Figure7.Figure 7
Comparison of two methods running 50 times.It can be seen from Figure7 that the min fitness value is 58.4%, the max fitness value is 84%, the mean fitness value is 77.36% in RNP by PSO, and the min fitness value is 72%, the max fitness value is 88%, the mean fitness value is 80.75% in RNP by DEEPSO. Comparing with RNP by PSO, the mean fitness value of RNP by DEEPSO can be improved by 3.39%. The simulation results show that the method of RNP by DEEPSO has the better optimization performance. This is because DEEPSO, which adds Differential Evolution (DE) and Evolutionary Strategies (ES) to the standard PSO, has continuous optimization ability, especially the later of the optimization process.


## 5. Conclusions

In this paper, aimed at solving the RFID networks planning problem, we present a mathematical model considering the tag coverage and the reader interference. In order to align with the same objective optimization direction, we present a transformed formula of the mathematical model as the fitness function. The DEEPSO algorithm that adds Differential Evolution (DE) and Evolutionary Strategies (ES) to the standard PSO is introduced to the optimization of RFID Networks Planning, which can improve the global convergence ability and particle diversity and can avoid falling into local convergence. According to the simulation results, compared with RFID networks planning by standard PSO, RFID networks planning by DEEPSO shows better optimization performance superior. Further research efforts should focus on the modeling and optimization of RFID network planning problem considering the adjustable radiated power of RFID reader.



---

*Source: 2745160-2019-12-07.xml*