LI Yu,WU Honglan,and SUN Youchao

Civil Aviation College,Nanjing University of Aeronautics and Astronautics,Nanjing 211100,China

Abstract: The existing active tag-based radio frequency identification (RFID) localization techniques show low accuracy in practical applications.To address such problems,we propose a chaotic adaptive genetic algorithm to align the passive tag arrays.We use chaotic sequences to generate the intersection points,the weakest single point intersection is used to ensure the convergence accuracy of the algorithm while avoiding the optimization jitter problem.Meanwhile,to avoid the problem of slow convergence and immature convergence of the algorithm caused by the weakening of individual competition at a later stage,we use adaptive rate of change to improve the optimization efficiency.In addition,to remove signal noise and outliers,we preprocess the data using Gaussian filtering.Experimental results demonstrate that the proposed algorithm achieves higher localization accuracy and improves the convergence speed.

Keywords:radio frequency identification (RFID) positioning,improved genetic algorithm,Gaussian filter,passive tags.

1.Introduction

Recently,the indoor location services have been increasingly demanded [1,2].With the advantage of high immunity to interference and strong penetration,and being less affected by indoor environmental factors,the radio frequency identification (RFID) localization technology [3?7]has become a hot research topic in indoor positioning technology.

Bian et al.[8]proposed an algorithm that combines the backward propagation neural network and the particle swarm,which could not identify a suitable neural network.Eberhardt et al.[9]proposed the SpotON system,which uses tags and readers to model signal transmission and combines clustering algorithms to improve localization accuracy.However,the cost of this method is high and it cannot be used in practice.Intel [10]achieved indoor localization of targets by passive tagging and adding the Monte Carlo algorithm,but as the method is based on Bayesian filtering,it leads to a large system computation and poor real-time performance.Xu et al.[11]proposed the indoor localization algorithm based on K-means and support vector machine (SVM),the system achieves an accuracy of less than 1.5 m.Lan et al.[12]combined the features of the network clustering algorithm and the density peak clustering algorithm and applied them to the localization of target tags,which enables the localization effect to meet the practical needs.But it requires secondary clustering and large computation,and the average value of error is about 0.128 m.

The above research mainly focused on arranging active tags with multiple readers,with disadvantages such as hard maintenance,high cost,and low accuracy.We propose a chaotic adaptive genetic algorithm to solve the postioning problem.We arrange the passive tag arrays,which could effectively speed up the algorithm convergence while improving the positioning accuracy.

2.RFID localization principal

The working principle of RFID is that after the tag receives the RF signal sent by the reader,the information stored in the chip is sent out by the energy obtained from the induction current [13].The positioning technology mainly includes ranging-based and non-ranging-based methods [14?18],among which the positioning method based on received signal strength indication (RSSI) is simple and low-cost,and it has become the mainstream research direction of positioning technology [19].Considering the advantages of RFID with high volume data reading,passive tag arrays are arranged,as shown in Fig.1.

Fig.1 Passive tag array

We divide the area into several cells.The vertex of each cell is a known node with a unique ID,and the coordinates are indicated by position,e.g.(0,0).The reader is the unknown node,and the distance relationship is converted by reading the RSSI signal value in the cell and using the relevant algorithm to solve the location information.

Distance computation model:the distance between nodes is calculated by the Shadowing model [20].

where RSSI is the signal strength value,dis the distance from the unknown point to the signal source,d0is usually set to 1 m,RSSI(d0)is the loss when 1 m,nis the path loss factor which is determined by the environment,Xσis a Gaussian noise variable with a mean value of 0 and a standard deviation of σ,in dBm.

In practical applications,we ignore the influence ofXσon the calculation results.To make the parameters best fit the propagation characteristics of the current environment,we suppose a set of measurement data (RSSIi,di),among themi=1,2,3,···,k,RSSIicorresponds to the value of RSSI measured when the distance isdi.Let ρi=?10lgdi,we have the following estimates:

3.Genetic algorithm

Genetic algorithm has a good global search ability and can get rid of the situation of local optimal solution without prior knowledge.When calculating the accuracy requirements,it only takes a short time to compute while maintaining the robustness [21?24].

3.1 Fitness function setting

Assuming the position of the unknown point is (x,y),we take the three tags with the strongest signal in the cell:(x1,y1),(x2,y2),(x3,y3).The distance isd1,d2,d3.Then,we construct the fitness function

3.2 Feasibility area

Based on the trilateral ranging algorithm [25],we denote the three reference nodes asa,b,c,and the distance from the unknown nodepto the reference node as (d1,d2,d3).

Taking the three pointsa,b,cas the center of the circle,we can find the intersection point between the three circles using the following formula and the intersection point is the coordinate of the unknown node:

However,due to the influence of factors such as multipath effects in practical applications,there can be errors in the distance obtained by the RSSI ranging model,resulting in that the three circles can not intersect at a point.There are four possible situations,which are shown in the Fig.2.

Fig.2 Feasible solution area

To select the feasible region of unknown nodes,we first combine the three equations of (5) in pairs,and then we derive the effective pointsI,J,Kby comparing the distance with the third circle center coordinate according to the solution of the equation,and then,we determine the feasible area by the range of the three effective points

3.3 Crossover operator

We use the crossover operation and generate a single point crossover based on the chaotic sequence [26,27],which can improve the accuracy of the algorithm while avoiding the problem of optimal chattering.The specific design is as follows:first,after initializing the population,we sort the parents according to the size of the fitness function value,and then pair them based on the principle of “matching each other”.For example,when the parents(W1,W2) are paired,the number of genes in each parent’s chromosome ism,then

The logistic chaotic sequence formula is as follows:

We take a random number between (0,1) and iteratively generate a chaotic value ε1between (0,1) through the chaotic sequence formula.Then,we save this value as the initial value of the next generation iteration,and use ε1to compute the value of (1,m) rounding between,=ε1×(m?1)+1,andis the intersection position betweenW1andW2.

3.4 Mutation operator

The traditional genetic algorithm uses a fixed mutation probability (Pm) [23,28].A higher probability leads to a faster searching speed,which may cause early convergence,while a lower probability causes the algorithm to converge slowly.To avoid such problems,we adopt an adaptivePmbased on fitness value to make the algorithm maintain the diversity of the population while ensuring the convergence of the algorithm.The adjustment formula of mutation probability is as follows:

wherePmis the mutation probability of the current individual,Pm1is the maximum mutation probability,fmaxis the maximum fitness in the group,fis the fitness of the current individual,andfmeanis the average fitness in the group.

3.5 Algorithm

There are five steps in the proposed algorithm.The specific process is shown in Fig.3.

Fig.3 Algorithm work flow

(i) The feasible domain is determined based on the trilateral localization model according to (5) and (6),the initial population sizeMand the number of genetic generationsNin the region.The upper and lower boundsPm1andPm2are defined for the variation operator.

(ii) The fitness of each individual in the population is calculated in line using (4),sorted by size,and then paired according to the principle of “family matching” to obtain the parent individuals.

(iii) Crossover operation.For each pair of parents,a random number within (0,1) is generated.Then,the gene position for the crossover operation is calculated in accordance with the logistic (7).

(iv) Adaptive mutation operation.The fitness of an individual in the population is brought into (8) to obtain the probability of variationPmfor that individual.After operating on all individuals,a new population individual is obtained as the parent of the next generation.

(v) If the number of evolutions reaches the upper limitN,the algorithms ends and the optimal individual and the corresponding fitness are output,otherwise go back to (ii).

4.Experimental results

4.1 Data collection

The experimental workspace is arranged as a square field of 10 m ×10 m.Fig.4 shows an experimental setup.The cell size is 1 m ×1 m,and the unique ID and coordinate information are written in each tag.We use HZ9300-8C reader to read passive tags,the reading distance is 0–5 m.The hardware specifications are shown in Table 1.The test cell is shown in Fig.5.

Fig.4 Part of the experimental setup

Fig.5 Test cell

Table 1 Hardware specifications

In order to verify the effectiveness of the algorithm,we randomly selected 10 unknown points and use the algorithm based on trilateral positioning for positioning calculation using Matlab,as shown in Fig.6.

Fig.6 Positioned points

4.2 Calculation of ranging model parameters

In a cell of 1 m ×1 m,we find the ranging model from RSSI value to distance.The specific steps are as follows:

(i) Measuring 50 sets of RSSI values at different distances between 0.1 m and 1 m.

(ii) Using Gaussian filtering [29?31] to preprocess the rea d signal strength values.RSSI obeys a (0,σ2) Gaussian distribution,and its probability density function is

According to the characteristics of Gaussian distribution,(μ?σ ≤RSSIk≤μ+σ) is the high probability occurrence area.

whereMis the number of (μ?σ,μ+σ ) in RSSIk.

(iii) Using linear regression to find the values of RSSI(d0)andn: RSSI(d0)=?70.18n=2.375.The fitted curve is shown in Fig.7.

Fig.7 Fitted curve

4.3 Analysis of positioning results

In order to verify and improve the performance of the genetic algorithm,multiple positioning calculations are performed on the same unknown point with traditional genetic algorithm,and finally the optimal value curve of each generation is obtained as shown in Fig.8.

Fig.8 Iteration process

By comparing Fig.8(a) and Fig.8(b),we find that the algorithm proposed in this paper has reached the optimal solution after evolving about 20 generations,while the traditional genetic algorithm reaches the optimal solution after 25 generations.While improving the convergence speed,it weakens and avoids the optimal chattering problem in the solution process.In order to verify the positioning effect of the proposed algorithm,we define the point position errorE,the abscissa errorE1,and the ordinate errorE2as follows:

where (x0,y0) is the actual coordinate of the unknown point,(x′,y′) is the estimated coordinate calculated by the positioning algorithm.

The positioning calculation results of the chaotic adaptive genetic algorithm and the trilateral centroid algorithm based on ranging are shown in Table 2.

Table 2 Positioning results

As indicated by Table 2,the average error of point position of the improved positioning algorithm is 5.4 cm with a standard deviation of 3 cm;the average error of horizontal coordinate is 3.39 cm;the error fluctuation is 4.68 cm;the average error of the vertical coordinate is 3.91 cm;the error fluctuation is 4.13 cm.The average error of point position of the trilateral center of mass algorithm is 8.65 cm,the error fluctuation range is 8.89 cm;the average error of horizontal coordinate is 6.24 cm with a standard deviation of 8.39 cm;the average error of vertical coordinate is 5.58 cm with a standard deviation of 4.68 cm.

For ease of intuitive understanding,we show a plot of the localization error curve is Fig.9.The algorithm proposed in this paper shows a significant enhancement in positioning accuracy over the three-sided center-of-mass positioning algorithm,with a 37% reduction in positioning error,smaller fluctuations and more stable positioning performance.

Fig.9 Point error

To further verify the effectiveness of the algorithm,the reader is made to communicate with the smart mobile terminal for connection,and the RSSI value is sent to the host computer via Bluetooth to reproduce the positioning of the trajectory.As given in Fig.10,the algorithm in this paper can reproduce the trajectory as well as accurate positioning.

Fig.10 Trajectory positioning

5.Conclusions

In this paper,a chaotic adaptive genetic algorithm is proposed to solve the RFID localization problem by arranging a dense passive tag array and dividing the area into cells.It is also combined with the trilateral ranging and positioning algorithm to find the feasible domain and further progress the convergence speed of the algorithm.In order to suppress the influence of noise and abnormal data,a Gaussian filter is used to process the received RSSI values.Along with the experimental data,it is calculated that the average error of point position is 5.4 cm,the error fluctuation range is 3 cm;the average error of horizontal coordinates is 3.39 cm,the error fluctuation is 4.68 cm;the average error of vertical coordinates is 3.91 cm,the error fluctuation is 4.13 cm.By comparing with the other state-of-the-art algorithms,the proposed algorithm achieves reliable stability while progressing the accuracy of RSSI-based positioning.Finally,the fine positioning performance of algorithm is further verified by reproducing the positioning of the driving trajectory.