Method for predicting tag arrival rate of mobile RFID system

Abstract

The present invention discloses a method for predicting a tag arrival rate of a mobile Radio Frequency Identification (RFID) system. The method includes: first, establishing a dynamic tag arrival model for a mobile RFID system based on modeling data and a grey model GM(1, 1); improving a weight of an initial value of a differential equation of the grey model through weighting; and predicating a tag arrival rate based on a sliding window mechanism. A weighted grey model predication algorithm based on the sliding window mechanism can be obtained, to predicate a tag arrival rate of a mobile RFID system. The method for predicting the tag arrival rate of the mobile RFID system of the present invention can reduce a prediction error rate of the system, maintain a modeling length of 4 for the system through the sliding window mechanism, and update modeling data online.

Claims

1. A method for predicting a tag arrival rate of a mobile Radio Frequency Identification (RFID) system, comprising the following steps: S1: establishing a dynamic tag arrival model for a mobile RFID system based on original modeling data and a grey model, which comprises: S11: establishing the tag arrival model for the mobile RFID system based on the original modeling data; S12: denoting an original non-negative time series X.sup.0 of a modeling length m as X.sup.0={x.sup.0(1), x.sup.0(2), . . . , x.sup.0(i), . . . , x.sup.0(m)}, wherein x.sup.0(i) is an arrival rate of a frame Fi, and m is the modeling length, namely, a number of pieces of the original data used for prediction; S13: accumulating the original series once to obtain a first-order accumulated series X.sup.1 X.sup.1={x.sup.1(1), x.sup.1(2), . . . , x.sup.i(j), . . . , x.sup.1(m)} wherein x.sup.1(j)=Σ.sub.k=1.sup.jx.sup.0(k), and a corresponding continuous time function is denoted as x.sup.1(t); S14: fitting, based on the grey model, $x^1\left(t\right)\mathrm{to}\frac{{\mathrm{dx}}^1\left(t\right)}{\mathrm{dt}}+{\mathrm{ax}}^1\left(t\right)=b$  using a first-order differential equation, wherein parameters a and b are undetermined parameters of the equation, a is referred to as a development coefficient, and b is referred to as a grey action quantity; S15: discretizing the first-order differential equation in step S14 into x.sup.0(k)+ay.sup.1(k)=b when t increments by 1, that is, $x^1\left(t\right)-x^1\left(t-1\right)=\frac{\Delta x^1\left(t\right)}{\Delta t}=x^0\left(t\right),$  wherein $y^1\left(k\right)=\frac{x^1\left(k\right)+x^1\left(k-1\right)}{2},$  k=2, 3, 4, . . . , m, and Y.sup.1={y.sup.1(2), y.sup.1(3), . . . y.sup.1(t) . . . y.sup.1(m)} is referred to as a background value sequence; S16: solving the discretized first-order differential equation in step S15 to obtain ${\tilde{x}}^1\left(k+1\right)=\left(x^1\left(1\right)-\frac{b}{a}\right)e^{-\mathrm{ak}}+\frac{b}{a},$  wherein {tilde over (x)}.sup.1(k+1) is a predicted value of a tag arrival rate corresponding to the first-order accumulated series at t=k+1, a and b are obtained by using the following least square method: (a, b).sup.T=(P.sup.T P).sup.−1 P.sup.TQ, wherein P and Q are both matrices, $P=\left(\begin{array}{cc}-y^1\left(2\right)& 1\\ -y^1\left(3\right)& 1\\ .Math.& .Math.\\ -y^1\left(m\right)& 1\end{array}\right),Q=\left(\begin{array}{c}{x}^0\left(2\right)\\ x^0\left(3\right)\\ .Math.\\ x^0\left(m\right)\end{array}\right),$  and T is a matrix transpose operation; S17: obtaining, based on a solution of the first-order differential equation and values of a and b, a predicted value ${\tilde{x}}^0\left(k+1\right)={\tilde{x}}^1\left(k+1\right)-{\tilde{x}}^1\left(k\right)=\left(x^1\left(1\right)-\frac{b}{a}\right)*e^{-\mathrm{ak}}*\left(1-e^a\right)$  of the original series through first-order decumulation, wherein {tilde over (x)}.sup.0(k+1) is the predicted value of the tag arrival rate when t=k+1 and k>=1; S2: improving initial values of the original modeling data through weighting; S3: updating the data of the model based on a sliding window mechanism; and S4: obtaining a tag arrival rate of the mobile RFID system based on updated data of the model.

2. The method for predicting the tag arrival rate of the mobile RFID system according to claim 1, wherein step S2 specifically comprises: changing x.sup.1(1) in step S13 to {tilde over (x)}.sup.1(1)=γ.sub.1x.sup.0(1)+γ.sub.2x.sup.0(2)+ . . . γ.sub.mx.sup.0(m) through weighting, wherein γ.sub.k=k/Σ.sub.j=1.sup.m a weighting coefficient, and Σ.sub.k=1.sup.mγ.sub.k=1.

3. The method for predicting the tag arrival rate of the mobile RFID system according to claim 2, wherein the original series in step S17 is restored to obtain ${\tilde{x}}^0\left(k+1\right)=\left({\gamma }_1{x}^0\left(1\right)+{\gamma }_2{x}^0\left(2\right)+.Math.{\gamma }_m{x}^0\left(m\right)-\frac{b}{a}\right)*e^{-a_k}*\left(1-e^a\right).$

4. The method for predicting the tag arrival rate of the mobile RFID system according to claim 3, wherein step S3 specifically comprises: appending a tag arrival rate obtained after a reader finishes reading in a frame as a latest tag arrival rate to a latest piece of the modeling data, and deleting an oldest piece of the modeling data.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a tag arrival rate model for a mobile RFID system according to the present invention;

(2) FIG. 2 is a schematic diagram of a sliding window mechanism according to the present invention;

(3) FIG. 3 is a flowchart of a method for predicting a tag arrival rate of a mobile RFID system according to the present invention;

(4) FIG. 4 is a schematic diagram of a reader-tag interaction process of a method for predicting a tag arrival rate of a mobile RFID system according to the present invention;

(5) FIG. 5 is a screenshot of simulation pseudo code of a method for predicting a tag arrival rate of a mobile RFID system according to the present invention;

(6) FIG. 6a is a graph of a simulation result for a normal distribution with a mean value of 50 and a variance of 15 in a traditional GM (1, 1) method according to Example 1 of the present invention;

(7) FIG. 6b is a graph of a simulation result for a normal distribution with a mean value of 50 and a variance of 15 in a WGMSW (1, 1) method according to Example 1 of the present invention;

(8) FIG. 6c is a graph of a simulation result for a normal distribution with a mean value of 50 and a variance of 25 in a traditional GM (1, 1) method according to Example 1 of the present invention; and

(9) FIG. 6d is a graph of a simulation result for a normal distribution with a mean value of 50 and a variance of 25 in a WGMSW (1, 1) method according to Example 1 of the present invention.

DETAILED DESCRIPTION

(10) To enable a better understanding of the technical solutions of the present invention by those of ordinary skill in the prior art, the technical solutions of the present invention are further described below with reference to the accompanying drawings and embodiments.

(11) In a static RFID system, a round R, a period that starts from a moment when a reader issues the first read command and ends after all tags in an identification zone are identified, consists of multiple frames Fi (i>=1), that is R={Fi|i.Math.N}, where N is a natural number. Each frame Fi includes multiple slots tij, that is, Fi={ttj|j=1, 2, . . . Li}, where Li is a number of slots of a frame i, also referred to as a frame length of the frame i. A tag in the identification zone randomly selects a slot to wait for identification. After a frame elapses, the reader collects statistics on numbers of three types of slots: first, a successful slot in which a tag is successfully identified, second, a collision slot in which no tag is successfully identified because of tag collision, and an idle slot that is not selected by any tags. The reader sets a new identification frame length based on the numbers of the three types of slots and starts identification in a next frame. In the static RFID system, tags do not move, and no new tag enters the identification zone during identification. Therefore, the concept of round R in the static RFID system does not apply to a dynamic RFID system. In the dynamic RFID system, the concept of frame Fi is the same as the static RFID system, but during the identification process in the frame Fi, a new tag enters the identification zone. The following assumption is used: A tag arriving within the Fi frame can only be read in a next frame rather than this frame. A tag arrival rate of a frame i is unknown, and therefore a number of tags arriving in the frame cannot be foreseen. Consequently, a number of tags to be identified in a next frame are unknown, and a frame length of the next frame cannot be accurately set.

(12) A method for predicting a tag arrival rate of a mobile RFID system provided in the present invention specifically includes the following steps.

(13) S1: Establish a dynamic tag arrival model for a mobile RFID system based on original modeling data and a grey model.

(14) Specifically, the method included the following steps.

(15) S11: Establish a tag arrival model for the mobile RFID system based on the original modeling data; as shown in FIG. 1.

(16) In FIG. 1, Fi represents a frame i in an identification process, and Xi represents a tag arrival rate of the frame i. Ui is a number of to-be-identified tags transferred from the frame i to a frame i+1. W is a total number of frames that can be accommodated in an identification zone. F.sub.0 is a preliminary frame in which a reader does not identify any tags. All tags that arrive in the frame F.sub.0 are transferred to a frame F.sub.1 for identification. Therefore, U.sub.0=x.sub.0*L.sub.0, where L.sub.0 represents a frame length of the frame F.sub.0. After the preliminary frame, each Ui (i>=1) includes two parts: one is a number Ci of tags that are not identified in the frame i due to collision, and the other is a number Xi*Li of tags arrived in the frame i, that is, U.sub.i=C.sub.i+x.sub.i*L.sub.i.

(17) S12: Denote an original non-negative time series X.sup.0 of a modeling length m as X.sup.0={x.sup.0(1), x.sup.0(2), . . . x.sup.0(i), . . . , x.sup.0(m)}, where x.sup.0(i) is an arrival rate of a frame Fi, and m is the modeling length, namely, a number of pieces of the original data used for prediction.

(18) S13: Accumulate the original series once to obtain a first-order accumulated series X.sup.1 so as to smooth randomness of a random sequence, X.sup.1={x.sup.1(1), x.sup.1(2), . . . x.sup.1(j), . . . , x.sup.1(m)}, where x.sup.1(j)=Σ.sub.k=1.sup.j x.sup.0(k), and a corresponding continuous time function is denoted as x.sup.1(t).

(19) S14: Fit, based on the grey model,

(20) $x^1\left(t\right)\mathrm{to}\frac{{\mathrm{dx}}^1\left(t\right)}{\mathrm{dt}}+{\mathrm{ax}}^1\left(t\right)=b$
using a first-order differential equation, where parameters a and b are undetermined parameters of the equation, a is referred to as a development coefficient, and b is referred to as a grey action quantity.

(21) S15: Discretize the first-order differential equation in step S14 into x.sup.0(k)+ay.sup.1(k)=b when t increments by 1, that is,

(22) $x^1\left(t\right)-x^1\left(t-1\right)=\frac{\Delta x^1\left(t\right)}{\Delta t}=x^0\left(t\right),$
where

(23) 0$y^1\left(k\right)=\frac{x^1\left(k\right)+x^1\left(k-1\right)}{2},$
k=2, 3, 4, . . . m, and Y.sup.1={y.sup.1(2), y.sup.1(3), . . . y.sup.1(t), . . . , y.sup.1(m)} is a background value sequence. A common background value sequence is a median sequence.

(24) S16: Solve the discretized first-order differential equation in step S15 to obtain

(25) ${\tilde{x}}^1\left(k+1\right)=\left(x^1\left(1\right)-\frac{b}{a}\right)e^{-\mathrm{ak}}+\frac{b}{a},$
where x.sup.1(k+1) is a predicted value of a tag arrival rate corresponding to the first-order accumulated series at t=k+1, a and b are obtained by using the following least square method, (a, b).sup.T=(P.sup.T P).sup.−1P.sup.TQ, P and Q are both matrices,

(26) $P=\left(\begin{array}{cc}-y^1\left(2\right)& 1\\ -y^1\left(3\right)& 1\\ .Math.& .Math.\\ -y^1\left(m\right)& 1\end{array}\right),Q=\left(\begin{array}{c}{x}^0\left(2\right)\\ x^0\left(3\right)\\ .Math.\\ x^0\left(m\right)\end{array}\right),$
and T is a matrix transpose operation.

(27) S17: Obtain, based on a solution of the first-order differential equation and values of a and b, a predicted value

(28) ${\tilde{x}}^0\left(k+1\right)={\tilde{x}}^1\left(k+1\right)-{\tilde{x}}^1\left(k\right)=\left(x^1\left(1\right)-\frac{b}{a}\right)*e^{-\mathrm{ak}}*\left(1-e^a\right)$
of the original series through first-order decumulation, where {tilde over (x)}.sup.0(k+1) is the predicted value of the tag arrival rate when t=k+1, and k>=1.

(29) S2: Improve initial values of the original modeling data through weighting.

(30) Specifically, x.sup.1(1) in step S13 is changed to {tilde over (x)}.sup.1=γ.sub.1x.sup.0(1)+γ.sub.2x.sup.0(2)+ . . . γ.sub.mx.sup.0(m), through weighting, where γ.sub.k=k/Σ.sub.j=1.sup.m m is a weighting coefficient, and Σ.sub.k=1.sup.m γ.sub.k=1. The original series is restored in step S17 to obtain

(31) ${\tilde{x}}^0\left(k+1\right)=\left({\gamma }_1{x}^0\left(1\right)+{\gamma }_2{x}^0\left(2\right)+.Math.{\gamma }_m{x}^0\left(m\right)-\frac{b}{a}\right)*e^{-\mathrm{ak}}*\left(1-e^a\right),$
where {tilde over (x)}.sup.0(k+1) is a final predicted value of the tag arrival rate.

(32) The main reason for doing so is that the predicted value is generated based on x.sup.0(m), and therefore the predicated value is greatly affected by x.sup.0(m) but minimally affected by oldest data x.sup.0(1). As a result, in weight allocation, greater impact indicates a larger weight.

(33) Step S3: After the tag arrival rate is predicated using the grey model, the RFID reader uses this predicted value to set a frame length and performs a next reading cycle. After tags are read in one frame, the reader can re-estimate the tag arrival rate based on an obtained slot status and corresponding value. Therefore, this predicted value should be appended as a latest tag arrival rate to a latest piece of the modeling data, and an oldest piece of the modeling data should be deleted.

(34) This process is like a window sliding with an identification process, and a size of the window is the modeling length. After the reader completes reading in one frame, the window moves forward, as shown in FIG. 2.

(35) Specifically, when modeling data of a prediction series is x.sup.0(i), x.sup.0(i+1), . . . x.sup.0(i+m−1), {tilde over (x)}.sup.0 (i+m) is obtained through one prediction, and a data set used for next prediction is {x.sup.0(i+1), . . . x.sup.0(i+m)}.

(36) Step S4: Obtain a value {tilde over (x)}.sup.0(k+1), namely, the tag arrival rate of the mobile RFID system tag, of the restored original series based on updated model data.

(37) The above is the method WMGSW (1, 1) for predicting the tag arrival rate of the mobile RFID system of the present invention. In this method, the following mechanisms are used: the weighted grey model with a modeling length of four and the sliding window mechanism. This prediction method is implemented as shown in FIG. 3.

(38) It can be seen from FIG. 3 that the method for predicting the tag arrival rate of the mobile RFID system of the present invention including the following steps: inputting an original data series X.sup.0={x.sup.0(k)}, where k=1, 2, 3, 4;

(39) obtaining a first-order accumulated series X.sup.1={x.sup.1(k)} through a cumulative generation algorithm, where k=1, 2, 3, 4, and x.sup.1(k)=x.sup.0(1)+x.sup.0(2)+ . . . +x.sup.0(k);

(40) performing discretization and obtaining a and b, where (a, b).sup.T=(P.sup.T P).sup.−1P.sup.TQ;

(41) weighting an initial value of a to-be-solved equation x.sup.1(1) to obtain {tilde over (x)}.sup.1(1)=γ.sub.1x.sup.0(1)+γ.sub.2x.sup.0(2)+γ.sub.3x.sup.0(3)+γ.sub.4x.sup.0(4);

(42) obtaining, by using the weighted x.sup.1(1), a solution

(43) ${\tilde{x}}^1\left(k\right)=\left(x^1\left(1\right)-\frac{b}{a}\right)*e^{-a\left(k-1\right)}+\frac{b}{a}$
of a first-order grey differential equation with a single variable, where k=2, 3, 4, 5;

(44) restoring the original series through a first-order decumulative algorithm to obtain

(45) ${\tilde{x}}^0\left(k\right)=\left(x^1\left(1\right)-\frac{b}{a}\right)*e^{-a\left(k-1\right)}*\left(1-e^a\right),$
namely, a prediction result of a tag arrival rate of a mobile RFID system, where k=2, 3, 4, 5;

(46) removing x.sup.0(1) from the original data series, and using the predicted value x.sup.0(5) as a last value of the data series, to reconstruct the model series X.sup.0={x.sup.0(k)}, where k=2, 3, 4, 5; and

(47) repeating the above calculation steps to obtain a predicted value of a next tag arrival rate.

(48) Further, in the method for predicting the tag arrival rate of the mobile RFID system of the present invention, a reader performs prediction calculation, and a tag receives only a signal from the reader and responds to the reader in a specific slot. FIG. 4 shows a specific reader-tag interaction process.

(49) It can be seen from FIG. 4 that the specific reader-tag interaction process in the present invention is as follows: First, the reader broadcasts a reading parameter, and initiates a reading round. After receiving the broadcast parameter from the reader, the tag randomly selects a slot for data transmission. After completing a round of identification, the reader counts numbers of successful slots, idle slots, and collision slots, and calculates a number of collision tags based on the statistic result. The reader uses the prediction method in the present invention to predict a tag arrival rate and calculate a total number of tags participating in a next reading round. The reader sets a parameter based on the total number of tags, and broadcasts the parameter to start a new round of reading. This process repeats.

(50) Further, to verify feasibility of the method for predicting the tag arrival rate of the mobile RFID system of the present invention, the following examples are carried out.

Example 1

(51) A single-peak Gaussian distribution is used to simulate the method for predicting the tag arrival rate of the mobile RFID system of the present invention, that is, a normal distribution function denotes the tag arrival rate, namely, x(t)˜N(μ, σ), where μ represents a mean value and σ represents a variance.

(52) A class ratio of data is calculated before prediction, to ensure that the data can be used in WGMSW (1, 1) for predication. The class ratio of the data is defined as

(53) ${\rho }_i=\frac{x\left(i\right)}{x\left(i+1\right)}.$

(54) According to application criteria of GM (1, 1), ρ.sub.i should fall within

(55) $\left[e^{\frac{-2}{m+1}},e^{\frac{2}{m+1}}\right],$
where m is a modeling length. If the system sets the modeling length to 4, ρ.sub.t should fall within

(56) $\left[e^{\frac{-2}{5}},e^{\frac{2}{5}}\right].$
If the criteria cannot be met, pre-processing needs to be performed before prediction, to make the class ratio fall within the required interval.

(57) Pseudo code of WGMSW (1, 1) is shown in FIG. 5.

(58) In the pseudo code of FIG. 5, wgmsw(parameters) is a custom function constructed using the algorithm in FIG. 3. In the function, the tag arrival rate is predicated by using a sliding window, and weighting and updating an initial value.

(59) In a mobile RFID system, a reader can predicate, based on the obtained tag arrival rate, a next tag arrival rate by using the above pseudo code. This predicted value can be used to set a frame length of a next reading round.

(60) A simulation hardware platform is as follows:

(61) CPU: Intel® Core™ i5-4590 CPU @ 3.3 GHz

(62) RAM: 8 GB

(63) A simulation software platform is as follows:

(64) Operating system: Windows 7

(65) Application software: Matlab 2015b

(66) To measure performance of WGMSW (1, 1), a normal distribution with a same mean value μ but different variances σ is used in the present invention, and 100 pieces of data are sampled for simulation. With the sliding window mechanism, the algorithm can be run for 96 times to predict a tag arrival rate of a frame 5 to a frame 100. FIG. 6a to FIG. 6d show obtained simulation results of the normal distribution with the mean value of 50 and the variances of 15 and 25, respectively

(67) The blue line in the figure represents an actual tag arrival rate, and the red line represents a predicted tag arrival rate. FIG. 6a and FIG. 6c show a simulation analysis result of the traditional GM (1,1) method, and FIG. 6b and FIG. 6d show a simulation result of WMGSW (1,1).

(68) For a tag arrival rate of a frame 52 in FIG. 6a (refer to FIG. 6a in substantial references), an actual value is 0.4535, but a predicted value is 0.5. This error is much larger than prediction errors of other data. The same phenomenon also occurs in FIG. 6c (refer to FIG. 6c in substantial references). In FIG. 6b (refer to FIG. 6b in substantial references) and FIG. 6d (refer to FIG. 6d in substantial references), there is no error mutation. Therefore, WGMSW(1,1) has better stability than the traditional GM(1,1) algorithm.

(69) Further, a relative error method is used to measure a difference between a prediction series {tilde over (X)}.sup.0 and an original series X.sup.0. A residual thereof is denoted as E=X.sup.0−{acute over (X)}.sup.0=[e(1), e(2), . . . , e(n)], a relative error is

(70) 0$\mathrm{relerror}=\frac{e\left(k\right)}{x^0\left(k\right)}*100\%,$
and an average relative error is

(71) $\mathrm{meanerror}=\frac{1}{n}\underset{i=1}{\overset{n}{.Math.}}.Math.\mathrm{relerror}\left(i\right).Math..$

(72) Table 1 lists average prediction error rates of GM (1, 1) and WGMSW (1, 1).

(73) TABLE-US-00001 TABLE 1 Average predication error table Average estimation Algorithm error rate ε GM(1, 1) with 0.0071 μ = 50, σ = 15 WGMSW (1, 1) 0.0055 with μ = 50, σ = 15 GM(1, 1) with 0.0036 μ = 50, σ = 25 WGMSW (1, 1) 0.0019 with μ = 50, σ = 25

(74) It can be seen from Table 1 that the prediction error rate of WGMSW(1,1) is lower than that of GM(1,1). Compared with a smaller σ, a larger σ means a slower change in the tag arrival rate and better tracking performance of predication.

Example 2

(75) To compare with research results of other researchers, we choose the DSA-RMGM prediction method mentioned in the comparison document Dynamic Self-adaptive Gray Prediction Algorithm for RFID Tag Arrival Rate, and the data thereof. Table 2 lists the comparison results.

(76) TABLE-US-00002 TABLE 2 Data comparison between WGMSW (1, 1) and DSA-RMGM prediction methods Predicated Predication Predicated Predication Predication value with error rate value with error rate Predicated error rate DSA- with DSA- DSA- with DSA- value with with Frame Measurement RMGM RMGM RMGM RMGM WGMSW WGMSW number value when L = 4 when L = 4 when L = 12 when L = 12 (1, 1) (1, 1) 40 0.46 0.6371 0.385 0.3879 41 0.47 0.5899 0.2551 0.478 0.0170 0.4505 0.0415 42 0.42 0.5089 0.2117 0.622 0.4810 0.405 0.0357 43 0.38 0.4122 0.0847 0.6248 0.6442 0.364 0.0421 44 0.37 0.3405 0.0797 0.5802 0.5681 0.3272 0.1157 45 0.2 0.3419 0.7095 0.5267 1.6335 0.3482 0.7410 46 0.26 0.1839 0.2927 0.4079 0.5688 0.1678 0.3546 47 0.19 0.3545 0.8658 0.1711 0.0995 0.1633 0.1405 Average predication 0.3570 0.5732 0.2102 error rate

(77) It can be seen from Table 2 that an average prediction error rate is obtained by averaging prediction errors of a frame 41 to a frame 47. This value is slightly different from the data in Document [20], but this does not affect our conclusion. It can be learned from the results that the proposed WGMSW (1, 1) has a lower prediction error rate than the method mentioned in Dynamic Self-adaptive Gray Prediction Algorithm for RFID Tag Arrival Rate. Moreover, the modeling length of WGMSW (1, 1) is a fixed value of 4, and therefore the system has better stability.

(78) The basic principles, main features, and advantages of the present invention are shown and described above. It should be understood by those skilled in the art that, the present invention is not limited by the aforementioned examples. The aforementioned examples and the description only illustrate the principle of the present invention. Various changes and modifications may be made to the present invention without departing from the spirit and scope of the present invention. Such changes and modifications all fall within the claimed scope of the present invention. The protection scope of the present invention is defined by the appended claims and their equivalents.