RFID network planning using a new hybrid ANNs-based approach

Abstract

Radio frequency identification (RFID) is a wireless technology that uses radio waves to automatically identify and track objects within a certain range. Due to the benefits of the technology, RFID technology has been adopted as a reliable and efficient solution and is an important technology used in various IoT applications. The deployment of the RFID system has caused an RFID network planning (RNP) problem. However, the RNP problem can be defined as an NP-hard combinatorial optimisation problem that requires the examination of a large number of combinations to obtain the best solution. The goal of this research is to introduce and describe a new hybrid approach to solve the problem of RNP optimisation that is based on artificial intelligence algorithms that require a minimum number of initial parameters. Based on widely used benchmarks, our approach is compared against a hybrid approach based on the genetic algorithm, and the results are efficient, cost-effective and assure a good deployment of the RFID system.

Keywords:

• Meta-heuristics
• redundant antenna elimination
• optimisation
• artificial neural networks
• RFID network planning

1. Introduction

In the face of current technological advancements and modern production processes, ‘barcode’ technology has proven useless for identifying and tracking things, particularly in IoT applications (Elbasani et al., 2020; Figueiredo e Silva et al., 2018; J. Zhang & Tai, 2022). As a result, radio frequency identification (RFID) is being welcomed as a reliable and effective solution to many of the difficulties brought by recent technological developments, modern manufacturing, and service automation (Altaf et al., 2018; Xiao et al., 2021). The implementation of an RFID system requires four basic elements: readers, antennas, tags and middleware.

In needed to conduct a large-scale RFID network efficiently, a problem known as RFID network planning (RNP) must be solved, the RNP problem is generated by deploying an RFID system that relies on the distance between antennas and tags.

In more general terms, the RNP problem aims to optimise a number of objectives in an RFID network, including coverage, interference, and redundancy, for this purpose Gong et al. (2012) have proposed a more recent mathematical model to model these objectives. Taking into account control variables such as antenna coordinates, number of antennas , etc., the RNP problem can be defined as a high-dimensional non-linear combinatorial optimisation problem with a large number of variables and uncertain parameters, specifically, it is an NP-hard optimisation problem (Azizi, 2019; Ke et al., 2007; Maimouni et al., 2022), whose solution requires the examination of a very large number of combinations to obtain a cost-effective solution, which shows that artificial intelligence (AI) and meta-heuristics methods appear to be well suited to solving the RNP problem and that these methods have been successfully applied to a variety of NP-hard problems (Ma et al., 2020; Osei-kwakye et al., 2022), most of them use random and iterative processes as a tool for assembling information, exploiting and exploring the research space.

The aim of this paper is to introduce, present, and evaluate RAE-NNA, a new hybrid approach to optimise the RNP problem that merges a new metaheuristic based on artificial neural networks, named neural network algorithm (NNA), and a redundant antenna elimination algorithm (RAE) that focuses on optimising the RNP problem by eliminating the redundant antennas. And we considered a hybrid approach, named RAE-GA, based on the genetic algorithm to compare our approach in terms of convergence and quality of the solutions found.

The ultimate goal of this work is to introduce an efficient and reliable optimisation approach to solve RNP problems and designing a cost-effective network by minimising the number of antennas and collisions between antennas and maximising the coverage area.

The explanation of the abbreviations used is shown in Table 1, and the main contributions of this paper are listed below:

• Since we have three objectives to optimise, we propose to design a mono-objective RNP problem whose fitness function represents a trade-off between each objective. The advantage is to give a clearer and simpler understanding of the RNP problem using proportions of the relative importance of each objective.

• Our proposed RAE-NNA approach is generally composed of two hybrid phases, the reduction phase consists in reducing the dimensionality by eliminating redundant antennas, through RAE algorithm, by earning flexibility in terms of RNP criteria and minimising the execution time. The optimisation phase serves to find suitable antenna positions by taking advantage of the intelligent strategies inspired by ANNs to produce better results.

• The new hybrid RAE-NNA approach is proposed with a minimum number of parameters required for the implementation to address the RNP problem, only three parameters are needed to have the perfect planning of an RFID system, which are number of available antennas, population size and maximum iterations.

Table 1. List of abbreviations.

Notations	Explication
RFID	Radio Frequency IDentification
RNP	RFID Network Planning
RAE	Redundant Antenna Elimination
GA	Genetic Algorithm
NNA	Neural Network Algorithm
ANNs	Artificial Neural Networks
dB	Decibel
dBm	Decibels Milliwatt
dBi	Decibel Isotropic
Mpop	Population Matrix of candidate solutions (S)
Si	The ith Solution Vector that contains the coordinates of antennas
CV($S_i$)	Coverage of an RFID system that contains antennas expressed in $S_i$
IT($S_i$)	Interference of an RFID system that contains antennas expressed in $S_i$

2. Related work

In the context of solving RNP problems, several researches have been carried out using meta-heuristics. In 2012, Gong et al. proposed a hybrid approach based on particle swarm optimisation (PSO) with a tentative reader elimination to address the RNP problem (Gong et al., 2012).

The majority of prior research has applied genetic algorithm (GA) in the RNP problem, Yang et al. (2009) present a method combining binary-coded gene presentation to descript the antenna's location and the coverage, and real-coded to descript antenna's types, power, direction. Authors in Z. Zhang et al. (2019) have implemented the genetic algorithm to resolve the RNP problem with two types of antennas: omnidirectional and directional.

Other meta-heuristics have been applied to deal with the RNP problem, in Raghib et al. (2018); Raghib and Majd (2019) the authors offer the possibility to change the multi-objective deployment problem to a bi-objective problem and find the best deployment without limiting the number of available readers using Non-dominated Sorting Genetic Algorithm (NSGA-II) and speed constrained multi-objective particle swarm optimisation (SMPSO) algorithm. In Raghib et al. (2016), authors applied the NSGA-II algorithm to obtain an RFID deployment taking into account the variations of the reader's range.

In Ma et al. (2017), a hybrid multi-objective artificial bee colony optimiser based on reinforcement learning and orthogonal Latin squares is used to solve real-world RNP problems using a hierarchical decoupling method. In Ma et al. (2014), the writers have proposed a cooperative artificial bee colony algorithm to reach an optimal deployment by simultaneously optimising four conflicting objectives: coverage, load balance, economic efficiency and interference. Artificial intelligence methods are also applied to RNP problems, Azizi (2019) presented a new RNP optimiser that uses a probabilistic ring logic neural network.

Although studies have been conducted by many authors, this problem is still insufficiently explored (Table 2), most of them require a large number of parameters to be defined, for this, we propose a hybrid approach based on artificial neural network strategies by defining only the number of available antennas, population size and the maximum number of iterations.

Table 2. Comparison of several RFID network planning approaches.

Approach	Technique used	Advantages	Limitations
Z. Zhang et al. (2019)	GA	Ability to solve the RNP problem with different types of antennas	Should be applied on commonly known benchmarks
Raghib and Majd (2019)	ML-SMPSO	Offer the possibility of solving the RNP problem without having to fix the number of available antennas	Recent modelling of the RNP problem should be considered
Raghib et al. (2016)	NSGA-II	Variations in the reader interrogation range have been taken into account	Recent modelling of the RNP problem should be considered
Ma et al. (2017)	ABC	Ability to decompose an RNP instance into continuous and discrete instances in order to solve complex RNP problems	Should be applied on commonly known benchmarks
Azizi (2019)	RPLNN	Using Ring Probabilistic Logic Neural Network, a novel artificial intelligence-based RNP optimiser has been used	Application to large-scale RNP benchmarks with high tag numbers should be considered

The structure of the rest of this paper is as follows: in Section 3 we present the problem formulation and we give the mathematical modelling of RNP, Section 4 is reserved to introduce and present our approach RAE-NNA, in Section 5 we evaluate RAE-NNA approach and the obtained results are discussed, finally Section 6 presents a general conclusion and some perspectives.

3. Problem formulation

The RFID technology refers to wireless technology that uses radio waves to automatically identify and track items within certain proximity (Maimouni & Abou El Majd, 2021), and an RFID system is built up of two principal parts (Figure 1): hardware part: includes tags, readers and antennas, software part: includes a middleware that can be defined as a computer unit (Azizi et al., 2016; Haibi et al., 2022).

Figure 1. Interconnections between RFID system components.

In this section, firstly we will introduce the mathematical formalisation of the RNP problem based on the Friis transmission equation (Franek, 2017; Gong et al., 2012), after setting the working area, the number of tags that must be scanned by the antennas, and the number of available antennas, we will determine the most important criteria such as coverage network, interference, and redundancy of an RFID system.

Secondly, we are going to propose our RAE-NNA approach which firstly requires defining the RAE algorithm, which serves to detect redundant antennas in the RFID network, and then we take advantage of the intelligent strategies of the weighted neural networks to construct an artificial intelligence computational algorithm for the optimisation of the RNP problem.

3.1. Mathematical model of RNP

The definition of an RNP is formed by defining the deployment space and determining the number of tags $N_t$ that should be read and finally giving the number of available antennas, after these steps the following RNP criteria should be calculated.

3.2. Coverage

To determine if a tag (t) is covered or not, two important powers must first be calculated (Figure 2). A tag (t) receives a signal through an antenna ( a) with a received power $P{T}_{a,t}$: (1) $\begin{array}{rl}P{T}_{a,t}\left[\mathrm{d}\mathrm{B}m\right]& =P_a\left[\mathrm{d}\mathrm{B}m\right]+G_a\left[\mathrm{d}\mathrm{B}i\right]+G_t\left[\mathrm{d}\mathrm{B}i\right]\\ & -L_s\left[\mathrm{d}\mathrm{B}\right].\end{array}$(1) With $L_s$ represents the loss: $L_s\left[\mathrm{d}\mathrm{B}\right]=10\log \left[{\left(\frac{4\pi }{\lambda }\right)}^2{d}^n\right]+\delta \left[\mathrm{d}\mathrm{B}\right],$where $G_t$ and $G_a$ are the tag gain and antenna gain, respectively, $P_a$ is the transmitted power of the antenna, n depends on the environment which varies from 1.5 to 4, δ represents other losses, λ is the wavelength and the distance between the tag and the antenna is denoted by d.

Figure 2. Transmission process.

When the received signal enables the tag (t), this tag sends RF signal to the antenna ( a) with transmitted power $P{A}_{t,a}$: (2) $\begin{array}{rl}P{A}_{t,a}\left[\mathrm{d}\mathrm{B}m\right]& =P_b\left[\mathrm{d}\mathrm{B}m\right]+G_t\left[\mathrm{d}\mathrm{B}i\right]+G_a\left[\mathrm{d}\mathrm{B}i\right]\\ & -20\log \left(\frac{4\pi d}{\lambda }\right),\end{array}$(2) where $P_b$ denotes the tag's backscatter power, which is calculated by multiplying the received power by a reflection coefficient called ${\mathrm{\Gamma }}_{tag}$: (3) $P_b={\left({\mathrm{\Gamma }}_{tag}\right)}^2\times P{T}_{a,t}.$(3)

The tag (t) is covered if there exist two antennas $a_1,a_2$ in the antennas set (AS) such that the received power $P{T}_{a_1,t}$ and the transmitted power $P{A}_{t,a_2}$ are greater than threshold power values $T_t$ and $T_a$, respectively. A tag's coverage is calculated mathematically using the equation below (Gong et al., 2012): (4) $C_v\left(t\right)=\{\begin{array}{ll}1& \mathrm{i}\mathrm{f}\mathrm{\exists }{a}_1,a_2\in AS,P{T}_{a_1,t}\ge T_t\wedge P{A}_{t,a_2}\ge T_a,\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}$(4) The percentage of covered tags for a set of tags (TS) refers to the total network coverage: (5) $CV=\sum _{t\in TS}\frac{C_v\left(t\right)}{N_t}\times 100\mathrm{\%}.$(5)

3.3. Interference

The accumulation of collisions by each tag causes interference, when a tag (t) is covered by many antennas, a collision $\gamma \left(t\right)$ is accumulated given by the equation below (Maimouni & Abou El Majd, 2021): (6) $\gamma \left(t\right)=\sum _{a\in AS}[P{T}_{a,t}-max\left\{P{T}_{a,t}\right\}],a\in AS\wedge P{T}_{a,t}\ge T_t.$(6) Therefore, the sum of the accumulated collisions of all tags defines the total interference of the RFID network: (7) $IT=\sum _{t\in TS}\gamma \left(t\right).$(7)

3.4. Redundancy

There could be antennas deployed in the RFID network their existence/absence does not affect the total coverage of the network, these antennas are redundant antennas that must be removed in efforts to realise an RFID network with just usable antennas, this redundancy criterion can be easily described using the equation below (Azizi, 2017): (8) $N_u=N_A-N_{red},$(8) where $N_u,N_A$ and $N_{red}$ are number of usable antennas, available antennas and redundant antennas, respectively.

4. The proposed hybrid approach RAE-NNA

4.1. Redundant antenna elimination (RAE)

The reduction task is done by deleting the deployed antennas one by one, and at each elimination, the total coverage of the new network is calculated (Figure 3).

Figure 3. RAE procedure.

If the total coverage calculated without the deleted antenna stays the same in the existence of this antenna, so this antenna seems to be redundant and should be eliminated; alternatively, if the new calculated coverage is lower than the previously calculated coverage, then this antenna is useful and should be restored (Azizi et al., 2016).

RAE plays an auxiliary role in the second phase of optimisation, on the one side regarding to the flexibility of RNP in terms of the number of antennas, and the other side in terms of searching for new positions while keeping the same coverage.

4.2. Proposed approach RAE-NNA

The optimisation phase is addressed using an unsupervised method based on artificial neural networks (ANNs). Taking into consideration that ANNs are used for forecasting by minimising the difference between the target and the predicted outputs, the primary idea of NNA is that the target solution $\left(S^{Target}\right)$ is the best solution acquired at each iteration, and the aim is to minimise the difference between the target solution and the forecasted solutions, which are solutions created at each iteration using strategies and mathematical formulae influenced by ANNs (Maimouni & Abou El Majd, 2021; Sadollah et al., 2018).

4.2.1. Population

An individual must contain the coordinates of each antenna deployed in the network, so an individual defines a solution as an S vector with size ($1\times 2N_u$): (9) $S=[x_1,x_2,\dots ,x_i,\dots ,x_{N_u},y_1,y_2,\dots ,y_i,\dots ,y_{N_u}],$(9) where the $x_i$ and $y_i$ represent the coordinates of the ith antenna.

The population of solutions $M_{pop}$ is defined by $N_{pop}$ solutions, so it is of size ($N_{pop}\times 2N_u$): $\begin{array}{rl}{M}_{pop}& ={[S_1,S_2,S_3,\dots ,S_i,\dots ,S_{pop}]}^{\mathrm{T}}\\ & =\left[\begin{array}{cccccc}{x}_1^1& \dots & x_{Nu}^1& y_1^1& \dots & y_{Nu}^1\\ x_1^2& \dots & x_{Nu}^2& y_1^2& \dots & y_{Nu}^2\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ x_1^i& \dots & x_{Nu}^i& y_1^i& \dots & y_{Nu}^i\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ x_1^{N_{pop}}& \dots & x_{Nu}^{N_{pop}}& y_1^{N_{pop}}& \dots & y_{Nu}^{N_{pop}}\end{array}\right].\end{array}$With $x_j^i$ and $y_j^i$ represents the coordinates of the jth antenna in the solution $S_i$.

4.2.2. Objective function

Each solution must be evaluated using an objective function that can be interpreted as a combination of the RNP objectives that need to be maximised or minimised. The following objective function that must be minimised is proposed: (10) $\varphi \left(S_i\right)=1-\phi \left(S_i\right),$(10) where $\phi \left(S_i\right)=\frac{110}{1+(100-CV(S_i){)}^2}+\frac{100}{1+{IT}^2\left(S_i\right)}+\frac{5}{1+(\mathrm{N}\mathrm{b}\mathrm{o}\mathrm{f}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{n}\mathrm{a}\mathrm{s}{)}^2}.$With $CV\left(S_i\right)$ and $IT\left(S_i\right)$ denote the total coverage and interference, respectively, of an RFID system that contains antennas whose coordinates are expressed in the vector $S_i$. By increasing the coverage of the network and decreasing the interference and the number of antennas deployed in the RFID network, the proposed function will be decreased.

4.2.3. Weight matrix

A weight vector $W_i$, including $N_{pop}$ random values associated with all solutions, is utilised to generate new candidate solutions for each solution $S_i$. The $N_{pop}$ weight vector in the weight matrix indicates that is square with the size ($N_{pop}\times N_{pop}$): (11) $\begin{array}{rl}W& =[W_1,W_2,\dots ,W_{N_{pop}}]\\ & =\left[\begin{array}{ccccc}{w}_{11}& \cdots & w_{i1}& \cdots & w_{N_{pop}1}\\ w_{12}& \cdots & w_{i2}& \cdots & w_{N_{pop}2}\\ & ⋮& & ⋮& ⋮\\ w_{1N_{pop}}& \cdots & w_{i{N}_{pop}}& \cdots & w_{N_{pop}{N}_{pop}}\end{array}\right],\end{array}$(11) where (12) $w_{ij}\in U(0,1)\mathrm{a}\mathrm{n}\mathrm{d}\sum _{j=1}^{N_{pop}}{w}_{i,j}=1\mathrm{f}\mathrm{o}\mathrm{r}i,j=1,2,\dots ,N_{pop}.$(12) Equation (12(12) $w_{ij}\in U(0,1)\mathrm{a}\mathrm{n}\mathrm{d}\sum _{j=1}^{N_{pop}}{w}_{i,j}=1\mathrm{f}\mathrm{o}\mathrm{r}i,j=1,2,\dots ,N_{pop}.$(12) ) shows that the sum of the elements of a weight vector for a solution must be one, in order to avoid undesirable changes in the creation of new candidate solutions.

4.2.4. Update of solutions and weights

Suppose that in a certain iteration (t), the updating of the solutions for the next iteration (t + 1) is done using the following equations, which were influenced by ANNs: (13) $\begin{array}{rl}{\overrightarrow{S}}_j^{New}(t+1)& =\sum _{i=1}^{Npop}{w}_{ij}\left(t\right)\times {\overrightarrow{S}}_i\left(t\right),j=1,2,3,\dots ,N_{pop},\end{array}$(13) (14) $\begin{array}{rl}{\overrightarrow{S}}_i(t+1)& ={\overrightarrow{S}}_i\left(t\right)+{\overrightarrow{S}}_i^{New}(t+1),i=1,2,3,\dots ,N_{pop}.\end{array}$(14) It should be noted that any target solution obtained ($S^{Target}$) has its corresponding target weight $W^{Target}$. As a result, the weights are updated based on $W^{Target}$, always respecting the constraint (12(12) $w_{ij}\in U(0,1)\mathrm{a}\mathrm{n}\mathrm{d}\sum _{j=1}^{N_{pop}}{w}_{i,j}=1\mathrm{f}\mathrm{o}\mathrm{r}i,j=1,2,\dots ,N_{pop}.$(12) ), using the following equation, for $i=1,2,3,\dots ,N_{pop}$: (15) ${\overrightarrow{W}}_i^{Updated}(t+1)={\overrightarrow{W}}_i\left(t\right)+2\times \mathrm{r}\times \left({\overrightarrow{W}}^{Target}\right(t)-{\overrightarrow{W}}_i(t\left)\right),$(15) where $\mathrm{r}$ denotes a random variable taking values in the range of 0 to 1.

4.2.5. Bias and transfer operator

After the solutions and weights have been updated, one of the two Bias/Transfer operators is applied to each $S_i$ solution. The Bias operator acts as a noise source to exploit the search space and look for other solutions in the search space, and for producing higher-quality solutions, the Transfer operator moves the solutions to the target solution.

The application of the Bias/Transfer operators depends on a modifying factor α decreases as the number of iterations increases, at each iteration this factor will be compared with a generated random value, in fact, the Bias operator is applied if this factor is higher than the generated value, in order to examine a variety of solutions, if not the Transfer operator is applied in the latest iterations in order to attain maximum results high-quality solutions.

The Bias operator consists of changing a proportion α of the current solution $S_i(t+1)$ and the actualised weight matrix $W^{Updated}$, however, the Transfer operator moves the solutions to better novel solutions to the target solution respecting the following equation, for $i=1,2,\dots ,N_{pop}$: (16) ${\overrightarrow{S}}_i^{Transfer}(t+1)={\overrightarrow{S}}_i(t+1)+2\times \mathrm{r}\times \left[{\overrightarrow{S}}^{Target}\right(t)-{\overrightarrow{S}}_i(t+1\left)\right],$(16) where $\mathrm{r}$ denotes a random variable taking values in the range of 0 to 1.

4.2.6. Approach

The functionalities of NNA are illustrated in Figure 4. Inspired by the artificial neural network, the local feedback and global feedback connections types are represented by the dotted blues and slim black lines respectively, this shows that NNA uses these types of connections as a way to collect information locally and globally from the population matrix, in order to generate optimal solutions by the feed-forward connections presented in bold black lines, for this reason NNA, is seen as a parallel sequential-batch learning method using global and local feedbacks (Sadollah et al., 2018).

Figure 4. Performance of NNA.

As presented in Algorithm 1, The RAE-NNA approach firstly starts by defining the number of available antennas and generating two matrices, population matrix ${\mathcal{M}}_{pop}$ and weight matrix W, and with the evaluation of the objective function of each solution, the target solution $S^{Target}$ and the target weight $W^{Target}$ are given. The target solution $S^{Target}$ contains the best positions of the deployed antennas in the network, and with these positions, the RAE algorithm optimises the RNP by determining the redundant and non-redundant antennas having the number $N_r$ and $N_u$ respectively.

And to proceed to the NNA phase, if the $S^{Target}$ solution has full coverage ($CV=100\mathrm{\%}$) it is necessary to eliminate redundant antenna positions for each solution in the population, if they exist $N_r!=0$, after this reduction process a population matrix of size ($N_{pop}\times 2N_u$) will be generated, then new positions will be generated by applying one of the two operator strategies of Bias or Transfer, by taking into consideration the condition of the modifying factor for any solution in the population matrix, and by evaluating the objective function on each new solution obtained, the optimal $S_{Opt}$ solution and its corresponding optimal $W_{Opt}$ weight are determined ($S_{Opt}$ best solution among the new solutions generated).

If the optimal solution $S_{Opt}$ is better than the target solution $S^{Target}$, then this optimal solution will be the new target solution ($S^{Target}=S_{Opt}$) and its corresponding weight will be the new target weight ($W^{Target}=W_{Opt}$), the RAE algorithm will be applied again to the new target solution which contains the new best antenna positions in order to determine a new number of redundant antennas $N_r^{new}$, in case the coverage is full the reduction process prepares the new population matrix of size ($N_{pop}\times 2N_a^{new}$) with $N_u^{new}=N_u-N_r^{new}$.

The next iteration is performed even if the previous condition is not verified, which generally shows that the RAE algorithm is applied just when the new best positions are available, and the reduction process is applied when there exist redundant antennas with full coverage.

These processes continue until the optimisation process completes the maximum number of predefined iterations, and the last step is to show the number of effective antennas and their best positions that will be deployed in the RFID network. The diagram in Figure 5 shows the general functioning of our RAE-NNA approach.

Figure 5. Diagram of RAE-NNA.

4.3. Genetic algorithm based approach RAE-GA

In order to carry out a comparative study, we chose to test our approach against a hybrid approach based on the genetic algorithm with RAE. Genetic algorithm is a stochastic optimisation algorithm based on natural selection mechanisms and genetics, moreover, several studies show the efficiency and reliability of the application of genetic algorithm in the face of the NP-hard optimisation problem on several domains (Mei et al., 2020; Shang et al., 2019; Too & Rahim Abdullah, 2020).

From an initial population, a new population of potential solutions is created based on the evaluated performance of each solution, this is done by applying the simple evolutionary operators: selection, crossover, and mutation.

4.3.1. Roulette wheel selection

Based on the lottery wheel, each solution $S_i$ is represented by a sector proportional to its fitness (value of the objective function), with an associated probability $P\left(S_i\right)$ defining the chance of selection. We spin the wheel and we select a solution, the best-evaluated solutions are statistically more likely to be selected (Figure 6), where (17) $P\left(S_i\right)=\frac{\varphi \left(S_i\right)}{\sum _{i=1}^{Npop}\varphi \left(S_i\right)}.$(17)

Figure 6. Roulette wheel selection.

4.3.2. Uniform crossover

The uniform crossover is made with two selected solutions ($S_1^{Selected},S_2^{Selected}$) and generates two new solutions ($S_1^{New},S_2^{New}$), it switches each element of the two solutions with a fixed probability $P_{\gamma }=[P_1,P_2,\dots ,P_{2Nu}]$ where $P_i\sim U(0,\gamma )$ (18) $\begin{array}{rl}{S}_1^{New}& =P_{\gamma }\odot S_1^{Selected}+(\text{1}-P_{\gamma })\odot S_2^{Selected},\end{array}$(18) (19) $\begin{array}{rl}{S}_2^{New}& =P_{\gamma }\odot S_2^{Selected}+(\text{1}-P_{\gamma })\odot S_1^{Selected}.\end{array}$(19)

4.3.3. Mutation

Like NNA, for introducing diversity the mutation operator applies a change to each new solution with a probability $P_{\mu }$, this change is applied on a percentage $P_{\mu }$ of the elements of the new solutions which disturbs these elements by adding a random variable X such that $X\sim N(0,{\sigma }^2)$.

4.3.4. RAE-GA approach

The functioning of the RAE-GA approach is extremely simple, the RAE algorithm is applied only after the evaluation phase of a given population. Like RAE-NNA the reduction of the population matrix is done if and only if full coverage is available with the existence of redundant antennas for the best solution obtained (Figure 7).

Figure 7. Diagram of RAE-GA.

5. Results and discussion

5.1. Benchmarks used

Four benchmarks have been chosen to evaluate the performance of our approach RAE-NNA to solve the RNP problem, these instances are public on the website http://www.ai.sysu.edu.cn/GYJ/RFID/TII/, and are used in many works concerning the optimisation of the RNP problem, these four benchmarks are illustrated in Figure 8, and these characteristics are summarised in Table 3.

Figure 8. Benchmarks C and R.

Table 3. Benchmarks characteristics.

	C		R
Name	C30	C50	R30	R50
Number of Tags	30	50	30	50
Nature	Clustered		Random
Work space size	$50\text{m}\times 50\text{m}$		$50\text{m}\times 50\text{m}$

On a workspace of $50\text{m}\times 50\text{m}$, Benchmarks C30 and R30 contain 30 tags, and C50 and R50 contain 50 tags, C30 and C50 benchmarks are easier to solve because the tags are clustered, but R30 and R50 instances are difficult to solve because the tags are randomly distributed.

5.2. Parameters used

The parameters of the experiment are divided into two: RNP parameters and RAE-NNA parameters. The RNP parameters are particular parameters for RFID network modelling, whereas the RAE-NNA parameters are technical parameters for the RAE-NNA algorithm's execution.

RNP parameters shown in Table 4 are specific to: Antennas, Tags and Transmission:

Table 4. Parameters RNP.

Antennas		Tags		Transmission
$P_a$	30 dbm	${\mathrm{\Gamma }}_{tag}$	0.3	λ	0.328 m
$T_a$	−80 dBm	$T_t$	−14 dBm	n	2
$G_a$	6.7 dBi	$G_t$	3.7 dBi	δ	0

Due to the diversity of the benchmarks in terms of the difficulty and number of tags, each benchmark has its own parameters, the RAE-NNA parameters are illustrated in Table 5.

Table 5. RAE-NNA parameters.

	C30	C50	R30	R50
Available antennas	6	8	10	12
Population size	25	30	30	50
Max_It	300	300	1500	2000

5.3. Experimental results

5.3.1. Analysis

For each benchmark, fifty independent runs were performed, taking into account the non-deterministic nature of the proposed approach (random initial antenna positions), and the results are analysed via four aspects: Coverage network, Number of deployed Antennas, Interference of the network and Evolution of the objective function.

Tables 6 and 7 show the average of the results obtained and the best solution obtained for each R and C benchmark:

Table 6. RAE-NNA obtained results for C benchmarks after 50 independent runs.

		Nb of antennas	Coverage	Interference
C30	Avg	3	100%	0
	Best	3	100%	0
C50	Avg	4.9800	100%	0
	Best	4	100%	0

Table 7. RAE-NNA obtained results for R benchmarks after 50 independent runs.

		Nb of antennas	Coverage	Interference
R30	Avg	6.3800	100%	−2.1509e−06
	Best	6	100%	0
R50	Avg	7.0200	100%	−0.1838
	Best	6	100%	0

Note: Avg denotes the average of the results obtained during 50 runs, and Best denotes the best solution obtained in 50 runs.

Preliminary observations of the obtained results show that during 50 independent experiments, the proposed RAE-NNA approach was effective in reducing the number of antennas deployed. by keeping a full coverage for all C and R instances.

For C30, RAE-NNA still tends to use three antennas to cover 30 clustered tags deployed with full coverage and null interference, which is well shown in the evolution of the objective function (Figure 10), the deployment of the best-obtained solution is illustrated in Figure 9.

Figure 9. Best deployment of antennas for the C30 benchmark.

Figure 10. Evolution of the objective function for benchmark C30.

The best solution obtained for the C50 instance deploys only four antennas among eight, with full coverage and null interference for 50 tags clustered in five groups as shown in Figure 11, and on average RAE-NNA always succeeds in obtaining null interference and full coverage with only four or five antennas, and the evolution of the objective function (Figure 12) shows that RAE-NNA always achieves better solutions during 50 experiments.

Figure 11. Best deployment of antennas for the C50 benchmark.

Figure 12. Evolution of the objective function for benchmark C50.

The R30 benchmark contains 30 randomly distributed tags, the best solution obtained shows that they are all covered by 6 among 12 available antennas with null interference, the deployment of the best solution is shown in Figure 13. RAE-NNA was able to attain average interference of $-2.1509e-06$ and an average number of antennas of 6.38 with always full coverage, this is clearly shown in the average evolution of the objective function, moreover by observing the evolution of the objective function in Figure 14, our approach always ensures that the best quality solutions are always obtained.

Figure 13. Best deployment of antennas for the R30 benchmark.

Figure 14. Evolution of the objective function for benchmark R30.

R50 is the most difficult benchmark to solve among the others, which contains 50 randomly distributed tags, the best solution obtained shows that with only six antennas we have full coverage and an interference equal to zero as shown in Figure 15.

Figure 15. Best deployment of antennas for the R50 benchmark.

Due to the increase in the number of tags and their random distribution, there is a small deviation between the average and best evolution of the objective function over the last iterations (Figure 16), this can be interpreted by the effect of interferences that do not reduce to zero on average, which shows that RAE-NNA guarantees full coverage and a minimum number of antennas but sometimes with small interferences. It should be noted that all the best solutions obtained by RAE-NNA give ideal deployments with full coverage, interferences equal to zero, and a minimal number of antennas.

Figure 16. Evolution of the objective function for benchmark R50.

5.3.2. Comparison

Fifty runs are done by RAE-GA, respecting the same parameters used for the RAE-NNA approach ($Max\mathrm{\_}It,N_{pop},N_a$), in order to make a comparison of the performances of the two approaches, and the comparison is made by illustrating the results obtained from RAE-NNA and RAE-GA and comparing the average evolution of the objective function of the 50 runs during the iterations for each benchmark. And to conduct a comparison with other similar existing approaches, respecting the equivalence of RNP parameters, we have chosen to compare our approach with a Hierarchical multi-objective approach using a multi-level optimisation based on the SMPSO algorithm, established by Raghib and Majd (2019) called ML-SMPSO.

For the C30 benchmark, RAE-NNA and RAE-GA obtain the same best solution during 50 independent runs, but on average RAE-NNA always obtains the perfect solution which always deploys three antennas for full coverage and null interference (Table 8), this is seen in the average evolution of the objective function illustrated in Figure 17. Hence, ML-SMPSO achieved the same results (Table 8).

Figure 17. The average evolution RAE-NNA and RAE-GA of the objective function for C30.

Table 8. Comparison of the results obtained by RAE-NNA, RAE-GA and ML-SMPSO for the C benchmarks.

		C30			C50
				ML-SMPSO			ML-SMPSO
		RAE-NNA	RAE-GA	(Raghib & Majd, 2019)	RAE-NNA	RAE-GA	(Raghib & Majd, 2019)
Nb of antennas	Avg	3	3.0600	3	4.9800	5.0400	5
	Best	3	3	3	4	5	5
Coverage	Avg	100%	100%	100%	100%	100%	100%
	Best	100%	100%	100%	100%	100%	100%
Interference	Avg	0	−0.0846	0	0	−1.6662e−06	0
	Best	0	0	0	0	0	0

The best solutions obtained for C50 show that the RAE-NNA approach deploys only four antennas against five antennas found by RAE-GA and ML-SMPSO with zero interference and full coverage (Table 8), and on average RAE-NNA still reaches perfect solutions than RAE-GA and ML-SMPSO, the average evolution of the objective function suggests that RAE-NNA and RAE-GA achieve high-quality solutions but those obtained by RAE-NNA are more accurate in terms of average antenna number and average interference (Figure 18).

Figure 18. The average evolution RAE-NNA and RAE-GA of the objective function for C50.

For the C benchmarks, all approaches achieve full coverage and null interference, but the optimal results of RAE-NNA outperformed those of the RAE-GA and ML-SMPSO algorithms in terms of minimising the number of antennas.

For the R benchmarks, the results shown in Table 9 have concluded that RAE-NNA and RAE-GA achieve better performance than ML-SMPSO in terms of reducing the number of antennas, by only deploying six antennas against seven for ML-SMPSO to ensure full coverage and null interference in the best-found solution. On average, RAE-NNA outperforms the other approaches in terms of the average number of deployed antennas, which favours the solutions found by RAE-NNA, as well as the average results obtained, show that our approach achieves more efficient and reliable solutions than RAE-GA in terms of all the objectives as shown in Figures 19 and  20.

Figure 19. The average evolution RAE-NNA and RAE-GA of the objective function for R30.

Figure 20. The average evolution RAE-NNA and RAE-GA of the objective function for R50.

Table 9. Comparison of the results obtained by RAE-NNA, RAE-GA and ML-SMPSO for the R benchmarks.

		R30			R50
				ML-SMPSO			ML-SMPSO
		RAE-NNA	RAE-GA	(Raghib & Majd, 2019)	RAE-NNA	RAE-GA	(Raghib & Majd, 2019)
Nb of antennas	Avg	6.3800	6.7800	6.8	7.0200	7.3400	7.6
	Best	6	6	6	6	6	7
Coverage	Avg	100%	100%	100%	100%	99.84%	100%
	Best	100%	100%	100%	100%	100%	100%
Interference	Avg	−2.1509e−06	−0.5391	0	−0.1838	−1.9613	0
	Best	0	0	0	0	0	0

Moreover, Figures 17– 20 show that RAE-NNA converges slowly than RAE-GA towards optimal solutions, but RAE-NNA still succeeds in reaching more best solutions than RAE-GA, especially for the difficult benchmarks R30 and R50, this is seen in the gap existing between the average evolution of the two approaches (Figures 19 and 20), so neither the non-deterministic nature of the initial population choice nor the random distribution of the Tags influences the efficiency and reliability of RAE-NNA.

6. Conclusion

In this paper, we introduced and presented a novel approach, called RAE-NNA, which aims at optimising the RNP problem by combining two algorithms: Redundant Antennas Elimination and Neural Network Algorithm.

RAE is used to eliminate the redundancy of the RFID network while NNA searches for better positions by intelligent strategies inspired by artificial neural networks, this is done to deal with the RNP problem which is based on the satisfaction of four objectives: Maximising coverage, Minimising interference, Minimising redundancy and Minimising the number of antennas.

The evaluation of the RAE-NNA approach is made by performing 50 independent experiments, the results provided by our proposed hybrid approach are more precise and cost-efficient and easily meet the most important criteria of RNP.

The results obtained show very clearly the efficiency and reliability of RAE-NNA, moreover the deployment of the best solutions found resume that the approach guarantees a better deployment of useful antennas which shows that RAE-NNA can be defined as an automated technique for RFID network planning.

Future work will focus on the treatment of real and more complex benchmarks with dynamic spaces. In this context, we will develop a robust multi-objective optimisation algorithm to deal with uncertainty based on Bayesian decision models, Bayesian game theory, and machine learning algorithms.

Acknowledgement

Our thanks go to MESRSFC and CNRST for financial support.

Disclosure statement

No potential conflict of interest was reported by the authors.