Sage Journals: Discover world-class research

Abstract

To realize higher coverage rate, lower reading interference, and cost efficiency of radio-frequency identification network in logistics under uncertainties, a novel robust radio-frequency identification network planning model is built and a robust particle swarm optimization is proposed. In radio-frequency identification network planning model, coverage is established by referring the probabilistic sensing model of sensor with uncertain sensing range; reading interference is calculated by concentric map–based Monte Carlo method; cost efficiency is described with the quantity of readers. In robust particle swarm optimization, a sampling method, the sampling size of which varies with iterations, is put forward to improve the robustness of robust particle swarm optimization within limited sampling size. In particular, the exploitation speed in the prophase of robust particle swarm optimization is quickened by smaller expected sampling size; the exploitation precision in the anaphase of robust particle swarm optimization is ensured by larger expected sampling size. Simulation results show that, compared with the other three methods, the planning solution obtained by this work is more conducive to enhance the coverage rate and reduce interference and cost.

Keywords

Radio-frequency identification network planning uncertain environment robust particle swarm optimization logistics

Introduction

With the development of information technology, there is an increasing usage of radio-frequency identification (RFID) network in logistics.^1,2 How to deploy the minimum number of readers for covering all tags in the entire space is known as the radio-frequency identification network planning (RNP) problem,³ which is one of the fundamental problems in large-scale RFID networks.⁴ Coverage, inference, and cost, which are key elements of the RNP problem, are largely influenced by the number and positions of the RFID devices.^5,6 However, uncertainties, such as radio channel, antenna read range and the influence on readers’ identification ability by different materials and objects around tags, may exist in the actual RFID network system. These uncertainties bring great influence to coverage, interference, and cost of the RFID network. Therefore, how to adopt the intensive way of deploying the readers to obtain higher coverage rate and less interference within low budget becomes a key issue for the popularization and application of RFID networks in logistics.

In the past decades, extensive efforts have been made to model and plan RFID network under certain environment,^5–10 and coverage problem is one of the fundamental issues in RNP. Gong et al.⁵ formulated a model of RNP, in which tag coverage, number of readers, interference, and the sum of transmitted power were considered. Liu and Ji⁶ proposed an optimization model of RFID network system to solve the problem of how to place readers, taking the coverage rate and load balance into consideration. Di Giampaolo et al.⁸ developed a simple and effective model, in which the performance indicators consisted of coverage efficiency, overall overlapping, total power, and cost of the network. Tao et al.¹⁰ conducted the reader deployment in large-scale RFID systems as a problem of multi-objective combination optimization by taking the coverage, signal interference, and load balance as the optimization objectives and deducing the objective ranges.

The RFID network planning problem has been proved to be NP-hard for its nonlinearity and complexity. In recent years, evolutionary computation (EC) and swarm intelligence (SI) have become an effective tool for solving the planning of RFID network problem under certain environment, such as genetic algorithm (GA),^3,7 plant growth simulation algorithm (PGSA),⁴ particle swarm optimization (PSO),^8–10 and artificial colony algorithm.¹¹ Yang et al.⁷ proposed a GA-based RNP method, which included mapping the RFID network, presenting the problem states using gene and chromosome, and implementing the mechanisms of individual selection and genetic operation. Simple and effective models of electromagnetic elements involved in RNP are developed and included in the frame of PSO algorithm.⁸ An improved PSO algorithm based on genetic algorithm (GA-PSO) was proposed to solve the problem of how to place readers so that the readers can effectively get the information of multiple tags.⁹ Tao et al.¹⁰ proposed an improved particle swarm algorithm, which can restrict the position change of original and new particles in the iteration process and accelerate the convergence speed of the algorithm, to solve the reader deployment in large-scale RFID systems. A k-coverage model, which is formulated as a multi-dimensional optimization problem with constraint conditions is developed to evaluate the network performance. And the PGSA is used to optimize the RFID networks by determining the optimal adjustable parameters in the model.⁴ Ma et al.¹¹ proposed a cooperative multi-objective artificial colony algorithm to find all the pareto optimal solutions and to achieve the optimal planning solutions by simultaneously optimizing four conflicting objectives (tag coverage, reader interference, economic efficiency and load balance) in multi-objective RNP. Lin and Tsai³ proposed a micro-genetic algorithm (mGA) with novel spatial crossover and correction schemes to cope with this constrained three-dimensional reader network planning problem. The mGA was computationally efficient, which allowed a frequent replacement of RFID readers in the network to account for the short turnaround time of cargo storage and guaranteed 100% tag coverage rate to avoid missing the cargo records.

Although the modeling and planning of RFID network has drawn extensive attention, few studies have considered several objectives under uncertainties about decision-making for the RNP problem. Meanwhile, there have been some studies on the sensor deployment of wireless sensor networks (WSNs) under uncertainties. Li et al.¹² and Ozturk et al.¹³ proposed a probability sensing model when the detection region of sensor was uncertain. Vu and Zheng¹⁴ presented a systematic study of the impact of location uncertainty on the coverage properties of WSNs and devised an efficient polynomial algorithm. Vu and Zheng¹⁵ carried out a rigorous study of the impacts of location uncertainty on the accuracy of target localization and tracking, and proposed an effective algorithm based on order-k max and min Voronoi diagrams. However, different properties of WSNs and RFID network make these approaches useful in WSNs inapplicable to RFID networks.⁴

The robust optimization method is very important in complicated RFID network planning under uncertainties. To deal with complex uncertainty problem, it is simple and effective to combine intelligent optimization algorithms and robust optimization.^16–19 However, robust optimization is generally based on Monte Carlo integral, while cyclic iteration is usually used in intelligent optimization algorithms. This straightforward method needs more number of fitness evaluations, which brings about a large calculation. Therefore, how to keep the search performance while reducing the computational complexity, in other words, how to improve the search performance in the case of limited sampling size, is a problem deserving study.

Uncertainties, such as radio channel, antenna read range, and the influence on readers’ identification ability by different materials and objects around tags, can be converted to uncertain positions of tags with respect to readers’ identification. Therefore, to enhance the reliability and stability in logistics, this work focuses on tags’ uncertain positions and studies robust modeling and planning of RFID networks under uncertainties. First, a robust planning model of an RFID network in logistics is built, in which the coverage rate is analyzed on the basis of the probability sensing model of WSN under uncertainty. Second, the concentric map–based Monte Carlo method is applied to calculate the interference. Third, to enhance the searching capability, robust particle swarm optimization (RPSO), which can trade off the exploitation speed and precision, is put forward to solve the RFID planning problem under uncertainties. Finally, the simulation results indicate that the proposed method possesses a better robust optimization capability.

RFID network planning problem under uncertainties

The key to the RFID network planning problem is the deployment of readers to satisfy multi-objective requirements due to the limited range of reader–tag communication. First, it is hoped that the tags can be identified as much as possible. Second, reading interference is closely related to the reader collision problem,²⁰ which may occur when the tags are located in the overlapping area of any two readers’ interrogation zones, and both readers read tags simultaneously.³ Consequently, the number of tags located in the overlapping area of interrogation zones should be as small as possible. Third, the smaller the number of placed readers is, the lower the cost is. Therefore, the proposed planning model of RFID network aims to optimize a set of objectives (such as tag coverage, reading interference, and economic efficiency) simultaneously by adjusting the control variables (the coordinates of readers, the number of readers, etc.) of the system. In view of uncertainties which can be converted to uncertain positions of tags with respect to readers’ identification, a novel study related to the coverage and interference analysis is considered in this work.

The deployment region of the RFID network system is supposed as a two-dimensional (2D) square domain which consists of several tags. Assume that uncertainties are arbitrary and then the uncertain area of tags’ positions to readers’ identification is circles with radius R_T. A conceptual view of tags’ uncertainty positions is shown in Figure 1, where coarse dots indicate tags and small circles are the ranges of tags’ uncertainty positions.

Figure 1.

Tags and their uncertainty positions.

Coverage rate

Coverage is the main task of an RFID network. By referring the probability sensing model for WSNs,^12,15 $reade r_{ij}$ , which denotes the capability of the ith reader to identify the jth tag, is described using equation (1)

reade r_{ij} = {\begin{matrix} 0, & R_{R} + R_{b} \leq d (s_{i}, o_{j}) \\ e^{(- λ_{1} {α_{1}}^{β_{1}} {α_{2}}^{β_{2}} + λ_{2})} & R_{R} - R_{b} < d (s_{i}, o_{j}) \leq R_{R} + R_{b} \\ 1 & d (s_{i}, o_{j}) \leq R_{R} - R_{b} \end{matrix}

(1)

where R_R is the sensing radius of each reader; R_b is the radius of each tag’s uncertainty position; $α_{1} = R_{b} - R_{R} + d (s_{i}, o_{j})$ ; $α_{2} = R_{b} + R_{R} - d (s_{i}, o_{j})$ ; $λ_{2}$ is the disturbing effect; $β_{1}, β_{2}$ , and $λ_{1}$ are the measuring parameters of detection probability; $d (s_{i}, o_{j}) = \sqrt{{(x_{S}^{i} - x_{O}^{j})}^{2} + {(y_{S}^{i} - y_{O}^{j})}^{2}}$ ; $(x_{S}^{i}, y_{S}^{i})$ and $(x_{O}^{j}, y_{O}^{j})$ are the coordinates of the ith reader and the jth tag, respectively. Then, $c_{O}^{j}$ , which denotes the coverage of the tag overlapped by readers, is described using equation (2). In equation (2), N_R denotes the number of deployed readers

c_{O}^{j} = 1 - Π_{i = 1}^{N_{R}} (1 - reade r_{ij})

(2)

In order to make the coverage rate comparable in different numbers of tags, $f_{1}$ denotes the coverage rate of the RFID network, which can be obtained using equation (3) by referring to Gong et al.,⁵ Liu and Ji,⁶ and Di Giampaolo et al.⁸ In equation (3), N_b denotes the number of tags

f_{1} = \frac{100}{N_{b}} \sum_{j = 1}^{N_{b}} c_{o}^{j}

(3)

Interference

Interference mainly occurs in an environment with dense readers, where several readers try to interrogate tags simultaneously. Interference will result in unacceptable misreading²¹ and failure of information collection.¹⁰ Due to uncertainty of tags’ positions, it is complicated to use geometric analysis method to deal with the interference problem. And it is hard to build an approximate mathematical coverage model. Here the Monte Carlo sampling method is employed.

If the ith reader can identify the sampling site $o_{k}^{j}$ , then ${reader}_{ik}^{j} = 1$ ; otherwise, ${reader}_{ik}^{j} = 0$ , where $k = 1, 2, \dots, K$ , K is the number of sampling sites, $o_{k}^{j}$ , the coordinate of which is $(x'_{k}^{j}, y'_{k}^{j})$ , denotes the kth sampling site within the uncertainty range of the jth tag, ${reader}_{ik}^{j}$ is the capability of the ith reader to identify the sampling site $o_{k}^{j}$ . When $R_{R} + R_{b} < d (s_{i}, o_{j})$ or $R_{R} - R_{b} \geq d (s_{i}, o_{j})$ , ${reader}_{ik}^{j}$ is attained straightly by equation (4)

{reader}_{ik}^{j} = {\begin{matrix} 0, & R_{R} + R_{b} < d (s_{i}, o_{j}) \\ 1, & R_{R} - R_{b} \geq d (s_{i}, o_{j}) \end{matrix}

(4)

When $R_{R} - R_{b} < d (s_{i}, o_{j}) \leq R_{R} + R_{b}$ , the concentric map method²² is applied. For a unit circle, the center of which is in the origin of the coordinate, the polar coordinates of the sampling sites are

r = ε_{1}, θ = \frac{π}{4} \cdot \frac{ε_{2}}{ε_{1}}, if ε_{1} > | ε_{2} |

(5)

r = ε_{2}, θ = \frac{π}{4} \cdot (2 - \frac{ε_{1}}{ε_{2}}), if - ε_{2} < ε_{1} \leq ε_{2}

(6)

r = - ε_{1}, θ = \frac{π}{4} \cdot (4 + \frac{ε_{2}}{ε_{1}}), if \begin{matrix} ε_{1} \leq - ε_{2}, ε_{1} < ε_{2} \end{matrix}

(7)

r = - ε_{2}, θ = \frac{π}{4} (6 - \frac{ε_{1}}{ε_{2}}), if \begin{matrix} ε_{2} \leq ε_{1} \leq - ε_{2}, ε_{2} \neq 0 \end{matrix}

(8)

r = 0, θ = 0, if ε_{1} = ε_{2} = 0

(9)

where $ε_{1}$ and $ε_{2}$ are the random real numbers in the interval [−1,1]. The Cartesian coordinate of a sampling site is $(x, y) = (r \cos θ, r \sin θ)$ . In this work, the Cartesian coordinate of the jth tag is $(x, y) = (x_{O}^{j} + R_{b} r \cos θ, y_{O}^{j} + R_{b} r \sin θ)$ , because the jth tag is located in $(x_{O}^{j}, y_{O}^{j})$ and the uncertainty area of a tag’s position is a circle with radius R_b.

Precision of random sampling is low, because $ε_{1}, ε_{2}$ are random real numbers in the interval [−1,1]. A low-discrepancy sampling, Korobov Lattice,²³ is adopted to enhance coverage calculation precision. Korobov Lattice is defined as $P_{K} = {(m / K) (1, a mod K, \dots, a^{s - 1} mod K) mod 1 : m = 0, \dots, K - 1}$ , where $a = ⌈ \sqrt{K} ⌉$ .

If $\sqrt{{(x_{S}^{i} - x'_{k}^{j})}^{2} + {(y_{S}^{i} - y'_{k}^{j})}^{2}} \leq R$ , $r e a d e r_{i k}^{j} = 1$ ; otherwise, ${reader}_{ik}^{j} = 0$ . ${Over}_{k}^{j}$ , which denotes the reading overlap of the kth sampling site within the uncertainty area of the jth tag, is described using equation (10). Referring to Di Giampaolo et al.,⁸ $f_{2}$ , which denotes the average interference, is described using equation (11)

{Over}_{k}^{j} = {\begin{matrix} 0, & \sum_{i = 1}^{N_{R}} {reader}_{ik}^{j} \leq 1 \\ - 1 + \sum_{i = 1}^{N_{R}} {reader}_{ik}^{j}, & \sum_{i = 1}^{N_{R}} {reader}_{ik}^{j} \geq 2 \end{matrix}

(10)

f_{2} = Π_{j = 1}^{N_{b}} \frac{1}{1 + \frac{1}{K} \sum_{k = 1}^{K} {Over}_{k}^{j}}

(11)

Cost

The quantity of readers is a key impact factor of the RFID network cost. $f_{3}$ in equation (12) denotes the RFID network cost. In equation (12), N_max is the maximum number of readers that can be deployed

f_{3} = \frac{N_{max} - N_{R}}{N_{max}}

(12)

RFID network planning model under uncertainties

The robust planning model of RFID network is built, in which the coverage rate, interference, and cost are considered. Equation (13) is taken as the objective function, where $γ_{1}, γ_{2}$ , and $γ_{3}$ are the weight coefficients and $γ_{1} + γ_{2} + γ_{3} = 1$

max f = γ_{1} f_{1} + γ_{2} f_{2} + γ_{3} f_{3}

(13)

Any deployed reader must be in the region of the RFID network. Let A be the region of the RFID network. Then the feasible region is shown in equation (14)

(x_{S}^{i}, y_{S}^{i}) \in A, \forall i \in {1, 2, \dots, N_{R}}

(14)

Constraints of the RFID network planning model are equations (1)–(3), (10)–(12), and (14).

Robust particle swarm optimization algorithm

From section “RFID network planning model under uncertainties,” it can be known that the RFID network planning problem under uncertainties is mainly a continuous problem. In this work, PSO is applied to the RFID network planning problem, because PSO possesses ease of implementation, high quality of solutions, computational efficiency, and speed of convergence⁶ and also exhibits good ability to solve continuous optimization problem.⁵

From section “Interference,” it can be shown that there is a trade-off between accuracy and speed in interference calculation. Larger number of sampling sites can improve the calculation accuracy and lead to lower speed, or vice versa. In order to balance the calculation of accuracy and speed, a novel robust particle swarm optimization algorithm is proposed.

Particle swarm optimization (PSO) algorithm

PSO is a population-based heuristic search technique, in which a group of particles search the best solution by iterations. The iteration formulations²⁴ are as follows

V_{ld}^{t + 1} = ω V_{ld}^{t} + c_{1} R_{1} (X_{ld}^{pb} - X_{ld}^{t}) + c_{2} R_{2} (X_{d}^{gb} - X_{ld}^{t})

(15)

X_{ld}^{t + 1} = X_{ld}^{t} + V_{ld}^{t + 1}

(16)

where $d = 1, 2, \dots, D$ with D being the number of particles’ dimensions; $t$ is the iteration number, $t = 1, 2, \dots, T$ , with $T$ being the maximum iteration; $ω$ is the inertia weight; $c_{1}$ and $c_{2}$ are the acceleration constants; $R_{1}$ and $R_{2}$ are random numbers between 0 and 1; $X_{l}^{pb}$ is the best solution of the lth particle; $X^{gb}$ is the best solution of the swarm; and $X_{ld}^{pb}$ and $X_{d}^{gb}$ are the dth dimensions of $X_{l}^{pb}$ and $X^{gb}$ , respectively.

Besides, the velocity V_ld is limited by the maximum velocity V_max,d.

Basic idea of RPSO

In the prophase of iterations, PSO algorithm should explore the search space to find the optimum region with faster speed. In the anaphase of iterations, PSO is supposed to develop the optimum region to search the optimal solution with higher precision. The sampling size is closely related to the exploring speed and exploitation precision. The smaller the sampling size is, the faster the exploring velocity is. The larger the sampling size is, the higher the exploitation precision is.

According to this line of thinking, a robust particle swarm optimization is proposed. To be specific, some sampling sizes formed a set $S_{N} = {n_{1}, n_{2}, \dots, n_{N}}$ . In $S_{N}$ , some larger sampling sizes formed a subset $S_{N}^{s}$ , while the other smaller sampling sizes formed a subset $S_{N}^{l}$ . In the prophase of iterations, the selection probabilities of sampling sizes in $S_{N}^{s}$ are larger than those in $S_{N}^{l}$ , or vice versa in the anaphase of iterations. Then the exploring speed in the prophase of iterations and the exploitation precision in the anaphase of iterations can be ensured. In the prophase of iterations, sampling sizes in $S_{N}^{l}$ are given low selection probabilities to get some high-reliability solutions, which can reduce blind exploration, while in the anaphase of iterations sampling sizes in $S_{N}^{s}$ are given low selection probabilities to get some unreliability solutions, which can help RPSO to escape local extrema.

In this work, the sampling sizes in $S_{N}$ are symmetrical about $n_{av} = (n_{1} + n_{N}) / 2$ .

Method of sampling size selection

Here, an asymmetric 2D sigmoid function is designed to set the selection probability of each sampling size in $S_{N}$ . $φ (n, t)$ , which is described in equation (17), denotes the probability of the sampling size n in the tth iteration. $φ_{1} (n)$ and $φ_{2} (t)$ in equation (17) are given by equations (18) and (19)

φ (n, t) = \frac{B [φ_{1} (n) φ_{2} (t) + 1]}{2}

(17)

φ_{1} (n) = \frac{2}{1 + \exp [- A_{1} (n - n_{av})]} - 1

(18)

φ_{2} (t) = \frac{2}{1 + \exp [- A_{2} (t - t_{a})]} - 1

(19)

where $B \in (0, 1)$ , $A_{1}, A_{2} \in (0, + \infty)$ , $t_{a}$ is an integer, $t_{a} \in ((1 + T) / 2, T)$ , and T is the maximum iteration of the RPSO algorithm. It can be seen that $φ_{1} (n)$ and $φ_{2} (t)$ are both changed from the sigmoid function. Here $φ_{1} (n) \in (- 1, 1)$ , $φ_{2} (t) \in (- 1, 1)$ , and $φ (n, t) \in (0, 1)$ . $φ_{1} (n)$ and $φ_{2} (t)$ are symmetrical about $(n_{av}, 0)$ and $(t_{a}, 0)$ , respectively.

The changes of $φ (n, t)$ with n and t are modified by updating the parameters $A_{1}$ and $A_{2}$ . Besides, the sum of selection probabilities of sampling sizes in $S_{N}$ should be 1, then $\sum_{i = 1}^{N} B [φ_{1} (n_{i}) φ_{2} (t) + 1] / 2 = 1$ and $φ_{2} (t) \sum_{i = 1}^{N} φ_{1} (n_{i}) + N = 2 / B$ .

It can be known that if $\sum_{i = 1}^{N} φ_{1} (n_{i}) = 0$ , then $B = 2 / N$ . So equation (20) holds

φ (n, t) = \frac{[φ_{1} (n) φ_{2} (t) + 1]}{N}

(20)

Expected sampling size

The expected sampling size, $E (t)$ , which is relevant to the computational complexity of RPSO, is analyzed here.

Calculation of expected sampling size

$E (t)$ can be derived as follows

\begin{matrix} E (t) = \sum_{i = 1}^{N} n_{i} φ (n_{i}, t) = \frac{1}{N} \sum_{n = 1}^{N} n_{i} [φ_{1} (n_{i}) φ_{2} (t) + 1] \\ = \frac{1}{N} {φ_{2} (t) \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i}) + \sum_{n = 1}^{N} n_{i}} \end{matrix}

The sampling sizes in $S_{N}$ are symmetrical about $n_{av}$ . Therefore, equation (21) holds

E (t) = n_{av} + \frac{1}{N} φ_{2} (t) \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i})

(21)

From equation (21), it can be seen that the change of $E (t)$ with the iteration t depends entirely on $φ_{2} (t)$ . It means that $E (t)$ is a monotonically increasing function of t, just like $φ_{2} (t)$ .

Change of expected sampling size

$n_{av}^{s}$ and $n_{av}^{l}$ denote the average sampling sizes in $S_{N}^{s}$ and $S_{N}^{l}$ , respectively, and $n_{m}^{s}$ denotes the maximum sampling size in $S_{N}^{s}$ . If $A_{2} >> \ln 2 / (T - t_{a})$ , $\exp [- A_{2} (T - t_{a})] >> 2$ , then $φ_{2} (t) \approx 1$ and equation (22) holds

E (T) \approx n_{av} + \frac{1}{N} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i})

(22)

because

t_{a} \in ((\frac{1 + T}{2}), T)

Therefore, when $t \in [1, 2 t_{a} - T]$ , $φ_{2} (t) \approx - 1$ , and equation (23) holds

E (t) \approx n_{av} - \frac{1}{N} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i}), t \in [1, 2 t_{a} - T]

(23)

Therefore, $E (t)$ is a monotonically increasing function approximately from $n_{av} - \frac{1}{N} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i})$ to $n_{av} + \frac{1}{N} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i})$ if $A_{2} >> \ln 2 / (T - t_{a})$ . And $E (t)$ is almost unchanged when $t \in [1, 2 t_{a} - T]$ .

Average expected sampling size

When $t \in [2 t_{a} - T, T]$

\begin{matrix} \bar{E} (t) = \frac{1}{2 T - 2 t_{a} + 1} \sum_{t = 2 t_{a} - T}^{T} E (t) \\ = \frac{1}{2 T - 2 t_{a} + 1} \sum_{t = 2 t_{a} - T}^{T} [n_{av} + \frac{1}{N} φ_{2} (t) \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i})] \\ = n_{av} + \frac{1}{N (2 T - 2 t_{a} + 1)} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i}) \sum_{t = 2 t_{a} - T}^{T} φ_{2} (t) \end{matrix}

Because $φ_{2} (t)$ is symmetrical about $(t_{a}, 0)$ , $\sum_{t = 2 t_{a} - T}^{T} φ_{2} (t) = 0$ and equation (24) holds

\bar{E} (t) = n_{av}, t \in [2 t_{a} - T, T]

(24)

From equation (23), it can be known that equation (25) is true if $A_{2} >> \ln 2 / (T - t_{a})$

\bar{E} (t) \approx n_{av} - \frac{1}{N} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i}), t \in [1, 2 t_{a} - T - 1]

(25)

Therefore, if $A_{2} >> \ln 2 / (T - t_{a})$ , then equation (26) is obtained using equations (24) and (25), and equation (27) is true

\begin{array}{l} \bar{E} (t) \approx \frac{1}{T} {(2 t_{a} - T - 1) [n_{a v} - \frac{1}{N} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i})] + (2 T - 2 t_{a} + 1) n_{a v}}, \\ t \in [1, T] \end{array}

(26)

\bar{E} (t) \approx \frac{T + 1 - 2 t_{a}}{NT} \sum_{n = 1}^{N} n_{i} φ_{1} (n_{i}) + n_{av}

(27)

Case of parameter setting

Here, a case of parameter setting is illustrated to visualize the changes of $φ (n, t)$ and $E (t)$ . S_N = {4, 8, 10, 30, 32, 36}, T = 100, A₁ = 0.1, A₂ = 0.25, and t_a = 70. It can be obtained that $\ln 2 / (T - t_{a}) \approx 0.02$ , so $A_{2} >> \ln 2 / (T - t_{a})$ . The changes of $φ (n, t)$ and $E (t)$ with t are shown in Figures 2 and 3, respectively.

Figure 2.

Change of $φ (n, t)$ with t.

Figure 3.

Change of $E (t)$ with t.

From Figure 2, it can be known that $φ (2, t)$ , $φ (4, t)$ , and $φ (5, t)$ are larger in the prophase of iterations and smaller in the anaphase of iterations; $φ (15, t)$ , $φ (16, t)$ , and $φ (18, t)$ are smaller in the prophase of iterations and larger in the anaphase of iterations. They all change slightly when $t \in [1, 40]$ . All these characteristics are consistent with section “Basic idea of RPSO.”

From Figure 3, it is seen that $E (t)$ is almost unchanged in the prophase of iterations. From the simulation results, $E (t) \approx 9.211 (t \in [1, 40])$ , $E (T) \approx 30.789$ , and $\bar{E} (t) \approx 15.792$ . At the same time, it can be obtained that $E (t) \approx 9.211$ $(t \in [1, 40])$ , $E (T) \approx 30.789$ , and $\bar{E} (t) \approx 15.792$ according to equations (23), (22), and (27), respectively. Therefore, the conclusion of the analysis is consistent with section “Expected sampling size.”

RPSO for the RFID network planning problem

Here, the proposed RPSO is applied for the RFID network planning problem. The objective function, equation (13), acts directly as the fitness function of RPSO. In the objective function, the coverage of RFID network is calculated by referring to section “Coverage rate”; interference is determined by Monte Carlo sampling method introduced in section “Interference”; cost is counted by equation (12) in section “Cost.” The pseudo-code of RPSO is as follows

Initialize population
For t = 1: T
For i = 1: population size
Evaluate coverage rate according to section “Coverage rate”;
Evaluate interference according to section “Interference,” in which the sampling size is selected based on section “Method of sampling size selection”;
Evaluate cost according to section “Cost”;
Evaluate fitness according to section “RFID network planning model under uncertainties”;
If

f (X_{l}^{t}) > f (X_{l}^{pb})

then

X_{l}^{pb} = X_{l}^{t}

;

X^{gb} = max {X_{l}^{pb} | l = 1, 2, \dots}

;
for d = 1: D
update

V_{ld}^{t + 1}

and

X_{ld}^{t + 1}

according to section “PSO algorithm”;
end
end
end

Simulations

In an ultra-high-frequency (UHF) RFID network area of 30 m × 30 m, 100 RFID tags (JY-T9662) are randomly distributed. Tag (JY-T9662), which is made of copperplate paper, is an UHF passive tag characterized by 860–960 MHz. Parameters are set according to Table 1, where R_R is set in accordance with Gong et al.;⁵λ₁, λ₂, β₁, and β₂ are set in accordance with Ozturk et al.;¹³M and T are the population size and the number of iterations of optimization algorithms detailed in the following paragraphs, respectively.

Table 1.

Parameter setting.

Parameter	R_R	R_b	λ ₁	λ ₂	β ₁	β ₂	N _max	γ ₁	γ ₂	γ ₃	M	T
Value	5 m	1 m	1	0	1	0.5	20	0.08	0.91	0.01	20	100

To verify the performance of the proposed method, four algorithms are implemented and compared, among which RGA_MC is real-coded GA based on traditional Monte Carlo method, RPSO_MC is PSO based on traditional Monte Carlo method, RGA_SC is real-coded GA based on the sampling method introduced in this work, and RPSO_SC is RPSO described in section “Robust particle swarm optimization algorithm.” In all these four algorithms, coverage of the RFID network is calculated by referring to section “Coverage rate”; cost is calculated using equation (12); interference in RGA_MC and RPSO_MC is determined by traditional Monte Carlo method, while interference in RGA_SC and RPSO_SC is calculated by Monte Carlo method based on the sampling method presented in this work. M and T of all algorithms are set according to Table 1. In RGA_MC and RGA_SC, the uniform crossover and uniform mutation are implemented, where the crossover and mutation rates are 0.7 and 0.01, respectively. $ω = 0.729$ and $c_{1} = c_{2} = 1.49445$ in RPSO_MC and RPSO_SC. Every chromosome or particle is coded as a $3 \times N_{max}$ matrix. Each reader has three codes: abscissa, ordinate, and whether to be deployed. The third code is a real number in the interval (0, 1). If the third code is greater than 0.5, the reader is deployed, or vice versa. Parameters on sampling size selection in RGA_SC and RPSO_SC are set according to section “Case of parameter setting.”

To compare these four algorithms, let the calculation quantity of the sampling method introduced in this work be the same as that in the traditional Monte Carlo method. In view of additional selection probability calculation for sampling size in RGA_SC and RPSO_SC, the sampling sizes of RGA_MC and RPSO_MC are both set at 18, which is slightly higher than $\bar{E} (N, t)$ in RGA_SC and RPSO_SC.

These four algorithms are continuously executed for 50 times. The best and average results are shown in Tables 2 and 3, respectively, where $f^{\exp}$ is obtained by traditional Monte Carlo method in which the sampling size is 1000. Table 4 shows $Error (f^{\exp})$ of interference and fitness ( $Error (f^{\exp}) = | f^{\exp} - {\hat{f}}^{\exp} |$ , where ${\hat{f}}^{\exp}$ is obtained by RGA_MC, RPSO_MC, RGA_SC, and RPSO_SC). The average CPU times spent by these four methods are shown in the last row of Table 3. The unit of CPU time is seconds.

Table 2.

The best results’ $f^{\exp}$ of four methods.

Performance index	RGA_MC	RPSO_MC	RGA_SC	RPSO_SC
Coverage	92.945	90.424	91.764	90.301
Interference	0.002	0.318	0.474	0.8
Network cost	0.4	0.55	0.3	0.4
Fitness	7.441	7.529	7.775	7.956

Table 3.

The average results’ $f^{\exp}$ and CPU times of four methods.

Performance index	RGA_MC	RPSO_MC	RGA_SC	RPSO_SC
Coverage	80.943	82.226	84.076	85.787
Interference	0.015	0.033	0.035	0.364
Network cost	0.200	0.200	0.260	0.320
Fitness	6.491	6.610	6.761	7.197
CPU time	3.16	1.74	3.05	1.70

Table 4.

Average $Error (f^{\exp})$ of interference degree and fitness.

	Performance index	RGA_MC	RPSO_MC	RGA_SC	RPSO_SC
Best results	Interference (×10⁻³)	5.765	3.405	2.127	1.569
	Fitness (×10⁻³)	5.246	3.099	1.936	1.428
Average results	Interference (×10⁻³)	4.049	2.433	1.956	1.303
	Fitness (×10⁻³)	3.685	2.214	1.780	1.186

The average fitness value comparisons among these four methods are shown in Figure 4(a). The average fitness error comparisons among these four methods are shown in Figure 4(b). The best results acquired by RPSO_AS are shown in Figure 5, where * represents the reader, coarse dots indicate the tags, large circles represent the identification ranges of readers, and small circles are uncertain positions of tags.

Figure 4.

Average fitness value (a) and average fitness error $Error (f^{\exp})$ (b) with iterations.

Figure 5.

Diagram of the best RFID network obtained by RPSO_SC.

From Tables 2 and 3, the best and average results displayed by RGA_SC and RPSO_SC are better than those by RGA_MC and RPSO_MC. RPSO_SC shows more excellent interference and fitness than RGA_SC. CPU time spent by RPSO_SC is obviously less than those spent by the other three methods.

From Table 4, individual evaluation errors in the best and average results obtained by RGA_SC and RPSO_SC are significantly smaller than those obtained by RGA_MC and RPSO_MC. It can be reflected from the expected sampling sizes in the last few iterations. For example, in the 77th–100th iterations, the expected sampling size of RGA_SC and RPSO_SC is between 30 and 31, which are drastically larger than those of RGA_MC and RPSO_MC, which is 18. In addition, it can be seen that the average fitness error obtained by RPSO_SC is smaller than that obtained by RGA_SC.

From Figure 4(a), the convergence rate of RPSO_SC is faster than those of the other three methods. From Figure 4(b), the fitness errors are clearly influenced by the sampling size. The average fitness error of RPSO_SC is obviously larger than those of RGA_MC and RPSO_MC in the 1st–65th iterations, but it is gradually smaller than those of the other three methods after the 70th iteration. From Figure 5, most tags have been identified by readers and lower reading interferences occur among readers.

To verify the model and method proposed in this work comprehensively, RFID network planning is done using different numbers of tags. In areas of 50 m×50 m, 50 m × 100 m, and 100 m × 100 m, the values of $N_{max}$ are 40, 75, and 140, respectively; and there are 250, 500, and 1000 tags, respectively, which are randomly distributed; the population sizes are 20, 40, and 50, respectively; the numbers of iterations are 300, 500, and 1000, respectively; the t_a values are 210, 350, and 700, respectively; the other parameters of sampling size selection in RGA_SC and RPSO_SC are set according to section “Case of parameter setting.”Table 5 shows the average optimization results and average CPU times of these three examples for the four algorithms. Figures 6(a), 7(a), and 8(a) show the average fitness value comparisons among these four methods, while Figs. 6(b), 7(b), and 8(b) show the average fitness error comparisons among these four methods.

Table 5.

Average planning results of the three examples.

Size of area network scale	Performance index	RGA_MC	RPSO_MC	RGA_SC	RPSO_SC
50 m × 50 m250 tags	Interference	0.012	0.041	0.081	0.318
	Fitness	6.147	6.111	6.480	6.541
	CPU time	9.59	5.43	9.01	5.34
50 m × 100 m500 tags	Interference	0.011	0.037	0.062	0.232
	Fitness	5.933	6.034	6.162	6.267
	CPU time	15.33	9.78	15.06	9.58
100 m × 100 m1000 tags	Interference	0.011	0.026	0.053	0.161
	Fitness	5.906	6.176	6.211	6.328
	CPU time	35.44	22.15	34.38	21.35

Figure 6.

Average fitness value (a) and average fitness error $Error (f^{\exp})$ (b) with iterations when the number of tags is 250.

Figure 7.

Average fitness value (a) and average fitness error $Error (f^{\exp})$ (b) with iterations when the number of tags is 500.

Figure 8.

Average fitness value and average fitness error $Error (f^{\exp})$ with iterations when the number of tags is 1000.

From Table 5, it can be seen that in different tag quantities RPSO_SC which spent the shortest CPU time is the best among the four algorithms referring to the interference and fitness. From Figures 6 –8, in robust planning of the RFID network with different numbers of tags, the convergence rate of RPSO_SC is faster than those of the other three methods and the average fitness error of RPSO_SC is gradually smaller than those of the other three methods. The average fitness value obtained by RPSO_SC is obviously larger than those obtained by the other three methods from the 44th, 25th, and 119th iterations in Figures 6(a), 7(a), and 8(a), respectively. The average fitness error in fitness values obtained by RPSO_SC is obviously larger than those obtained by RGA_MC and RPSO_MC in the 1st–150th iterations, 1st–300th iterations, and 1st–600th iterations shown in Figures 6(b), 7(b), and 8(b), respectively. However, it is gradually smaller than those obtained by the other three methods from the 206th, 351st, and 690th iterations shown in Figures 6(b), 7(b), and 8(b), respectively.

These results suggest that RPSO_SC possesses better optimization performance in solving the RFID network planning problem under uncertainties.

Conclusion

To sum up, this work builds a RFID network planning model in logistics under uncertainties which can be converted to uncertain positions of tags with respect to readers’ identification. The probability sensing model is employed to analyze the coverage rate, and the Monte Carlo method is applied to calculate the interference among readers. To enhance the planning efficiency of an RFID network under uncertainties, a robust particle swarm optimization algorithm is proposed. To reduce the computational complexity and improve the search performance simultaneously, the sample sizes are smaller and larger in the prophase and anaphase of iterations, respectively. The expected sampling size is analyzed for the convenience of performance comparisons between RPSO_SC and the other algorithms based on traditional sampling method. Several simulations are executed in different network scales. With respect to coverage, interference, network cost, fitness, CPU time, convergence rate, and fitness error, the proposed approach can provide a better planning scheme for an RFID network system in logistics under uncertainties.

Footnotes

Handling Editor: Luca Catarinucci

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (No. 51579143), The Ministry of education of Humanities and Social Science project (Nos 15YJC630145 and 15YJC630059), and the Natural Science Foundation supported by Shanghai Science and Technology Committee (No. 15ZR1420200), which is gratefully acknowledged.

References

Ngai

EWT

Cheng

TCE

et al . Mobile commerce integrated with RFID technology in a container depot. Decis Support Syst 2007; 43: 62–76.

Kuo

Chen

Warren Liao

et al . Hybrid of artificial immune system and particle swarm optimization-based support vector machine for Radio Frequency Identification-based positioning system. Comput Ind Eng 2013; 64: 333–341.

Lin

Tsai

. Micro genetic algorithm with spatial crossover and correction schemes for constrained three-dimensional reader network planning. Expert Syst Appl 2016; 44: 344–353.

. A fuzzy k-coverage approach for RFID network planning using plant growth simulation algorithm. J Netw Comput Appl 2014; 39: 280–291.

Gong

Shen

Zhang

et al . Optimizing RFID network planning by using a particle swarm optimization algorithm with redundant reader elimination. IEEE T Ind Inform 2012; 8(4): 900–912.

Liu

. RFID network deployment based on hybrid particle swarm optimization. Appl Res Comput 2012; 29(4): 1326–1328.

Yang

Xia

et al . A RFID network planning method based on genetic algorithm. In: Proceedings of the international conference on networks security, wireless communications and trusted computing, Wuhan, China, 25–26 April 2009. New York: IEEE.

Di Giampaolo

Forni

Marrocco

. RFID-network planning by particle swarm optimization. In: Proceedings of the 4th European conference on antennas and propagation, Barcelona, 12–16 April 2010. New York: IEEE.

Liu

Shen

. RFID network optimization based on improved particle swarm optimization algorithm. J Cent South Univ: Sci Technol 2011; 42(s1): 900–904.

10.

Tao

Huang

et al . SA-PSO based optimizing reader deployment in large-scale RFID systems. J Netw Comput Appl 2015; 52: 90–100.

11.

Zhu

et al . Cooperative artificial bee colony algorithm for multi-objective RFID network planning. J Netw Comput Appl 2014; 42: 143–162.

12.

Pan

et al . Sensor deployment optimization for detecting maneuvering targets. In: Proceedings of the 7th international conference on information fusion, Philadelphia, PA, 25–28 July 2005. New York: IEEE.

13.

Ozturk

Karaboga

Gorkemli

. Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm. Sensors 2011; 11(6): 6056–6065.

14.

Zheng

. Robust coverage under uncertainty in wireless sensor networks. In: Proceedings of the international conference on computer communications, Shanghai, China, 10–15 April 2011. New York: IEEE.

15.

Zheng

. Geometric algorithms for target localization and tracking under location uncertainties in wireless sensor networks. In: Proceedings of the international conference on computer communications, Orlando, FL, 25–30 March 2012. New York: IEEE.

16.

Jin

Branke

. Evolutionary optimization in uncertain environments—a survey. IEEE T Evolut Comput 2005; 9(3): 303–317.

17.

Jin

Tang

et al . Robust optimization over time—a new perspective on dynamic optimization problems. In: Proceedings of the IEEE congress on evolutionary computation, Barcelona, 18–23 July 2010. New York: IEEE.

18.

Zhu

Luo

Zheng

et al . Research on increasing the performance of evolutionary algorithm in searching robust optimal solutions based on quasi-Monte Carlo method. Pattern Recogn Artif Intell 2011; 24(2): 201–209.

19.

Jin

Tang

et al . A framework for finding robust optimal solutions over time. Memet Comput 2013; 5(1): 3–18.

20.

. Artificial immune network-based anti-collision algorithm for dense RFID readers. Expert Syst Appl 2014; 41(5): 4798–4810.

21.

Chen

Zhu

et al . RFID network planning using a multi-swarm optimizer. J Netw Comput Appl 2011; 34: 888–901.

22.

Shirley

Chiu

. A low distortion map between disk and square. J Graph Tool 1997; 2(3): 45–52.

23.

Gill

Lemieux

. Searching for extensible Korobov rules. J Complexity 2007; 23(4–6): 603–613.

24.

Shi

Eberhart

. A modified particle swarm optimizer. In: Proceedings of the IEEE international conference on evolutionary computation, Anchorage, AK, 4–9 May 1998. New York: IEEE.

Robust modeling and planning of radio-frequency identification network in logistics under uncertainties

Abstract

Keywords

Introduction

RFID network planning problem under uncertainties

Coverage rate

Interference

Cost

RFID network planning model under uncertainties

Robust particle swarm optimization algorithm

Particle swarm optimization (PSO) algorithm

Basic idea of RPSO

Method of sampling size selection

Expected sampling size

Calculation of expected sampling size

Change of expected sampling size

Average expected sampling size

Case of parameter setting

RPSO for the RFID network planning problem

Simulations

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References