A Physical Layer Network Coding Based Tag Anti-Collision Algorithm for RFID System

Cuixiang Wang,Xing Shao,2,3,＊,Yifan Meng and Jun Gao

1School of Information Engineering,Yancheng Institute of Technology,Yancheng,224000,China

2School of Computer,Nanjing University of Posts and Telecommunication,Nanjing,210003,China

3Modern Agricultural Resources Intelligent Management and Application Laboratory,Huzhou Normal University,Huzhou,313000,China

4School of Science and Technology,Troy University,Troy,36082,USA

Abstract:In RFID(Radio Frequency IDentification)system,when multiple tags are in the operating range of one reader and send their information to the reader simultaneously,the signals of these tags are superimposed in the air,which results in a collision and leads to the degrading of tags identifying efficiency.To improve the multiple tags’identifying efficiency due to collision,a physical layer network coding based binary search tree algorithm(PNBA)is proposed in this paper.PNBA pushes the conflicting signal information of multiple tags into a stack,which is discarded by the traditional anti-collision algorithm.In addition,physical layer network coding is exploited by PNBA to obtain unread tag information through the decoding operation of physical layer network coding using the conflicting information in the stack.Therefore,PNBA reduces the number of interactions between reader and tags,and improves the tags identification efficiency.Theoretical analysis and simulation results using MATLAB demonstrate that PNBA reduces the number of readings,and improve RFID identification efficiency.Especially,when the number of tags to be identified is 100,the average needed reading number of PNBA is 83% lower than the basic binary search tree algorithm,43% lower than reverse binary search tree algorithm,and its reading efficiency reaches 0.93.

Keywords:Radio frequency identification(RFID);tag anti-collision algorithm;physical layer network coding;binary search tree algorithm

1 Introduction

As a kind of automatic identification technology,radio frequency identification(RFID)[1]system can identify object even when the object is not in its visual range.Compared with other automatic identification technologies,RFID has the advantages of high accuracy,long reading distance,large amount of data storage,strong robustness and so on.In addition,as one of the key technologies of Internet of Things(IoT),RFID technology is widely used in warehousing logistics,goods tracking,identity recognition,access control and many other fields.

A typical RFID system[2]consists of a reader and a number of tags.Information about an object is stored in the tag,while the reader is used to read and write the information in the tag.When a plurality of tags is in the working range of a reader,and these tags use the same communication frequency to send information to the reader,the transmission signals of these tags interfere with each other.Once the signal interference is detected by a reader,the reader will not be able to read the information in the tags correctly,which is called the tag collision problem of RFID system[3–6].Actually,the tag collision problem seriously restricts the reading and writing efficiency of RFID system.Therefore,the research on tag collision problem is one hot topic of RFID research and of great significance to the application of RFID systems.

2 Related Works and Motivation

Actually,in order to solve the tag collision problem of RFID system,some tag anti-collision algorithms have been proposed.These algorithms can be divided into two categories:ALOHA based indeterminate algorithm[5]and tree based deterministic algorithm[6].

ALOHA based algorithm controls tags access the channel to reduce the tag collision possibility.Typical ALOHA based algorithms includes slotted ALOHA algorithm[7],frame slotted algorithm[8–10],and bit slot algorithm[11],etc.In addition,the tags’ number estimation algorithm[12]is also an important improvement of ALOHA based algorithms.As a kind of random algorithm,ALOHA based algorithm cannot ensure that a tag is read in a certain period of time and some tags may not be read for a long time,which is called the problem of “tag starvation”.

In tree based algorithm,tags are divided into groups continuously when a collision occurs.When there is only one tag in a group,the tag will be read correctly without collision.And all tags using tree based algorithm will be read in this way.In the binary search tree based algorithms,once tag collision is detected,tags will be divided into 2 groups and finally,the reader will read all tags’information without collision.

Typical tree based algorithms include tree splitting algorithm(TS)[13],query tree algorithm(QT)[14,15],binary search tree algorithm(BST)[6],dynamic binary search tree(DBST)[16],regressive binary search tree algorithm(RBST)[17,18].As a deterministic algorithm,tree based algorithm is able to avoid the problem of “tag starvation”.Therefore,more and more attention has been paid to the research on tree based anti-collision algorithm for RFID system.

In existing tree based algorithms,the collision signal will be discarded directly when a collision is detected.However,the conflicting signal is usually the superposition of multiple tags’ information.If the collision signal in tree based algorithm could be exploited to obtain the original tag information,the performance of tree based algorithm will be further improved significantly.

In recent years,the emergence of network coding technology[19,20]provides an opportunity to exploit collision information of multiple tags to improve the efficiency of the tree based algorithm.

Network coding[19]allows the intermediate nodes in the network to encode the received data.Using network coding,the multicast transmission rate can reach the theoretical upper limit value according to the maximum flow minimum cut theory.

Network coding can be applied to physical layer,which is called physical network coding[21]and exploits the additive nature of simultaneously arriving electromagnetic waves for equivalent coding operation.Exactly,the conflicting signal of multiple tags in RFID system is the superposition signal of multiple tags.Therefore,the conflicting signal can be treated as a kind of physical network coding,and the original information of each tag can be obtained through decoding operation at the reader.

Fig.1 shows an example of physical layer network coding.There are three nodes in Fig.1,node 1,node 2 and node 3.And node 1 intends to send packetP1to node 3 through node 2,while node 3 wants to send packetP2to node 1 through node 2.If these nodes work in the traditional store-forward mode,4 time slots are needed to complete the transmission ofP1andP2as shown in Fig.1(A).

Figure 1:Illustration of physical layer network coding.(A)Store-forward manner,(B)network layer network coding manner,(C)physical layer network coding manner

Nevertheless,if network layer network coding is exploited,3 time slots are required as shown in Fig.1(B).Node 1 sendsP1and node 3 sendsP2both to node 2 consuming 1 time slot respectively.Then node 2 codesP1andP2(XOR operation)and sends outP1 ⊕P2.Due to the broadcast nature of the wireless channel,node 1 will receiveP1 ⊕P2 and obtainP2through decoding operation(P1 ⊕P2)⊕P1.Similarly,node 3 will obtainP1.

However,if physical layer network coding is exploited,the total number of time slots can be further reduced to 2.Inslot 1,node 1 sendsP1and node 3 sendsP2simultaneously.The magnetic wave ofP1andP2overlays in the space and forms the superimposed signalP1+P2.The overlaying can be considered as physical layer network coding operation.Then node 2 sends outP1+P2.Node 1 will getP2through decoding operation(P1+P2)-P1.Similarly,node 2 will obtainsP1as shown in Fig.1(C).

It is evident from Fig.1 that using physical network coding,the number of time slots is reduced by 50% compared with the store-forward mode,and reduced by 33% compared with the network layer network coding.Physical layer network coding can reduce data transmission time and improve transmission efficiency.

In RFID system,when tag collision occurs,the conflicting signal is the superposition of multiple tags’signals,which can exactly be treated as physical layer network coding operation.However,traditional RFID tag anti-collision algorithms discard conflicting signals,which can be used for decoding to obtain original tag information.Therefore,the characteristics of physical layer network coding make it suitable for dealing with the tag collision problem of RFID system.

In this paper,a physical layer network coding based binary algorithm(PNBA)is proposed to solve multiple tags collision problem in RFID.Compared with existing mechanisms,PNBA exploits physical layer network coding to obtain information from the conflicting signal,which is discarded by the traditional method.Therefore,PNBA improves the tags identifying speed and reduce interaction costs between reader and tags.Simulation results demonstrate that,when the number of tags is 100,the average needed reading number of PNBA algorithm is 83% lower than that of BST,and 43% lower than that of RBST,and its reading efficiency is 0.93.

3 Details of PNBA

3.1 Conflicting Bit Recognition

To solve the tags collision problem,it is essential for the PNBA algorithm to judge whether there exits collision in the received signal,and further detects which bit occurs collision.As other binary algorithms,the PNBA algorithm exploits the Manchester code.Fig.2 illustrates an example of the conflicting bits identification when signals of three tags are superimposed.

It can be found from Fig.2 that PNBA algorithm needs to check the first half and latter half of each bit in the superimposed signal to identify the conflicting bits.In Manchester code,‘01’ represents the original information ‘0’,and ‘10’ represents the original information ‘1’.Using the Manchester code,the overlaying of multiple ‘01’ or multiple ‘10’ still ensure a half bit is 0.Therefore,if the first half or the latter half is zero,then there is no conflicting in this bit.Otherwise,conflict occurs in this bit,which is marked with “X”.

3.2 Relevant Agreement

Before delving into the introduction of the detailed process of the PNBA algorithm,related concepts and commands used in the PNBA algorithm are presented.

Request Command:REQ(RSN)

Request command which contains reference sequence number(RSN),is sent by reader to tags.The tag whose sequence number is larger thanRSNdoes not respond the command,while the tag whose sequence number is less than or equal toRSNwill respond.In this way,the number of conflicting tags will be reduced.

Select Command:SEL(RSN)

Select command is sent by the reader.The tag whose sequence number is equal toRSNwill be selected by the reader to prepare for subsequent reading and writing operations.

Read Command:RD-DATA

Read command means that the reader reads the sequence number returned by the selected tag.

Sleep Command:UNSEL(RSN)

The status of the tag whose sequence number is equal to theRSN,is set SLEEP,which means the tag will no longer respond to the reader’s any command.

Conflicting Stack:

In the PNBA algorithm,the reader maintains a conflicting information stack,which is used to store the overlapping conflict signal information of multiple tags.

Figure 2:Illustration of conflicting bit identification using Manchester Code

3.3 Process of PNBA in Detail

PNBA algorithm introduces physical layer network coding into the RFID tag anti-collision algorithm.PNBA analyses and uses the conflict signal information discarded by the traditional tag anti-collision algorithm,which improves the efficiency of tag identification.The detailed process of PNBA is as follows.

Step 1.InitializeRSNand each bit ofRSNis set to 1.For example,if the sequence number of a tag is 8 bits,the RSN is initialized as11111111.Then initialize the backward variablei,which is set 0.

Step 2.The reader sends Request Command,REQ(RSN).The tag whose sequence number is less than or equal toRSNwill respond and return its sequence number.

Step 3.Receiving magnetic waves,the reader will demodulate the received signal and detect whether conflict occurs in the received signal according to the Manchester Code principle.If the first half and the second half of a bit in the received signal are not zero,conflicting occurs in this bit.And it also means that the received signal contains conflicting.The conflicting signal is pushed into the Conflicting Stack.Find the highest conflicting bit in the conflicting signal and set it as 0.In addition,the bits lower than these bits are all set to 1,and the bits higher than these bits remain unchanged.Then the new modified conflicting signal is used as theRSNparameter of the next Request Command and Step 2 is executed.If the first half and the second half of each bit,one is high level,another is zero,there is no conflict in the received signal.

Step 4.The reader sends Select CommandSEL(RSN).The tag whoseIDequals toRSN,responds and returns itsIDto the reader.

Step 5.The Read Command RD-DATA is executed by the reader to read and save the tag’sID.Then the reader sends Sleep CommandUNSEL(RSN),and the tag whoseIDhas just been read will be set SLEEP.

Step 6.Detect whether the Conflicting Stack is empty.If the stack is empty,it indicates that all the tags’information has been read,and PNBA algorithm ends.Otherwise,the reader pops the element at the top of the Conflicting Stack and uses it minus the tag information the reader just read(decoding operation of physical layer network coding).Besides,i=i+1.

Step 7.Detect whether the result of the subtraction operation contains conflicting according to the Manchester Code.If the subtraction result contains conflicting,Step 8 is executed.If there is no conflicting in the subtraction result,it indicates that the subtraction result is one tag’s ID.The reader obtains the tag’s ID through physical network coding and will send SLEEP Command and let the tag enter the SLEEP state.Pop-up the element at the top of the Conflicting Stack,and Step 6 is executed.If each bit of the subtraction result is zero,it indicates that all the conflicting tags of the conflicting signal have been correctly read.Pop-up the top element of the Conflicting Stack,and Step 6 is executed.

Step 8 TheRSNused in lastith interaction between reader and tag is taken as the parameter of the next Request CommandREQ(RSN).iis reset to 0.Return to Step 2 until all tags are correctly read.

The flow chart of the PNBA algorithm is shown in Fig.3.

3.4 An Application Example of PNBA

In order to clearly illustrate the principles of PNBA,an example scenario is given to analyse the working process of the PNBA.In this scenario,there is a reader and 4 tags in its working range:Tag1,Tag2,Tag3 and Tag4.The ID of each tag is formulated asD7D6D5D4D3D2D1D0with 8 bits and is as follows:Tag1 with ID=10110010,Tag2 with ID=10100011,Tag3 with ID=10110011and Tag4 with ID=11100011.Then PNBA is executed:

Figure 3:Flow chart of PNBA

1.InitialRSNis set11111111.The reader sendsREQ(11111111)and all 4 tags return their IDs.According to Manchester Coding,the reader receives 1X1X001X(X means conflicting bit.),which means there occurs collision and the conflicting demodulation signal(Tag1+Tag2+Tag3+Tag4)is pushed into the Conflicting Stack.AndD6is the highest collision bit.Therefore,D6is set 0 and all bits lower thanD6are set 1 and the nextRSNis10111111.

2.The reader sendsREQ(10111111).Tag1,Tag2 and Tag3,whose ID is less than10111111respond and return their IDs.The reader receives 101X001X.Since collision still occurs,the conflicting demodulation signal(Tag1+Tag2+Tag3)is pushed into the Conflicting Stack.D4is the highest bit with collision.Therefore,D4is set 0 and all bits lower thanD4are set 1 and the next RSN is10101111.

3.The reader sendsREQ(10101111),and only Tag2 returns its ID.The reader demodulates and decodes the received signal and gets10100011which contains no collision.The reader identifies Tag2 correctly and sendSLEEP(10101111)to let Tag2 enter the state ofSLEEP.

4.The reader sendsREQ(10111111).Tag1 and Tag3 return their IDs.The reader demodulates and decodes the received signal and gets1011001X.Since collision occurs atD0,the conflicting demodulation signal(Tag1+Tag3)is pushed into the Conflicting Stack.D0is set 0 and10110010is the parameter of the nextREQ(RSN).

5.The reader sendsREQ(10110010)and only Tag1 returns its ID.The reader demodulates and decodes the received signal and gets10110010which contains no collision.The reader identifies the Tag1 correctly and sendsSLEEP(10110010)to let the Tag1 enter into the state ofSLEEP.The reader pops up the top element(Tag1+Tag3)of the Conflicting Stack.The top element minus the10110010(Tag1)and get10110011with no collision.The10110011is the ID of Tag3 obtained through physical layer network coding.The reader sendsSLEEP(10110011)to let Tag3 enter into the state ofSLEEP.The reader pops up top element(Tag1+Tag2+Tag3)of the Conflicting Stack.Subtract the information of Tag1,Tag2 and Tag3 from the top element.And then the result is 00000000.The reader pops up top element(Tag1+Tag2+Tag3+Tag4)of the Conflicting Stack.Subtract the information of Tag1,Tag2 and Tag3 from the top element.And then the result is11100011.The11100011is just the ID of Tag4 obtained through physical layer network coding.So far,all the tags have been correctly obtained.It is obvious that only Tag2 and Tag1 are read by the reader,while the IDs of Tag3 and Tag4 are obtained by physical layer network coding,which reduces the number of reading times between reader and tags and improves reading efficiency.

Fig.4 shows the entire recognition process of the example and the change of the demodulated signal stack.

4 Theoretical Analysis of PNBA

4.1 Theoretical Analysis of Reading Times

For binary search tree algorithm(BST),when there areNtags to be identified,the needed reading times for the first tag to be identified is log2N+1.Therefore,the number of the total needed reading times of BST(abbreviated as RT-BST)to identify allNtags is as Eq.(1).

Since the key process of the dynamic binary search tree algorithm(DBST)is similar to BST,the total number of reading times of DBST(abbreviated as RT-DBST)is the same as that of BST,and is shown in Eq.(2).

The process of regressive-style binary search tree algorithm(RBST)to identifyNtags is equivalent to the complete search of binary tree withNnode.Therefore,the required reading number of RBST is 2×N.

For the PNBA algorithm,the required reading number to identify the first tag is log2N+1.Since the PNBA algorithm exploits physical layer network coding,the conflicting signals can be decoded layer by layer.For the rest(N-1)tags,each tag only needs one time reading.Therefore,the total required reading time by the PNBA(abbreviated as RT-PNBA)is as Eq.(3).

Figure 4:Application example of PNBA

The comparison of the required reading number to identifyNtags for the algorithms mentioned above is shown in Tab.1.

The reading efficiency is defined asNdivided by the reading times.The reading efficiency comparison of the algorithms is shown in Tab.2.

4.2 Theoretical Analysis of Transmission Bits Number

The transmission bit number is the bit number of each transmission multiplied by the transmission number.AssumeNis the number of tags to be identified andKis the bit number of each tag.For DBST,the bit number of each transmission depends on the position of the conflicting bit.Assume the conflicting bit is random and the probability of collision at each bit is the same as 1/K.Then,the expectation of each transmission bit number for DBST(abbreviated as TB-DBST)is as Eq.(4).

The transmission bits number comparison of the 4 algorithms is shown in Tab.3.

The transmission efficiency is defined asK×Ndivided by the expectation of transmission bit number.The transmission efficiency comparison of the 4 algorithms is shown in Tab.4.

Table 1:Comparison of reading times

Table 2:Comparison of reading efficiency

Table 3:Comparison of transmission bits number

Table 4:Comparison of transmission efficiency

5 Simulation Analysis of PNBA

In order to analyze the performance of the PNBA algorithm,the BST,DBST,RBST and PNBA are simulated using MATLAB.

Fig.5 shows the required reading times for the four algorithms when the number of tags to be identified is between 5 and 100.It is clear that BST and DBST are always the same.Compared with BST and DBST,RBST is significantly lower,and the advantage is more obvious with the increasing of the tags’ number.When the number of tags to be identified is less than 25,PNBA is close to RBST.When the number of tags to be identified is greater than 25,the required reading number of PNBA is significantly lower than that of RBST,and the advantage is more obvious with the growth of the tags’ number.When the number of tags is 100,the PNBA is 45%lower than RBST.

Figure 5:Comparison of required reading times under different number of tags to be identified for 4 algorithms

Fig.6 illustrates the comparison of reading efficiency when the tags number to be identified is between 5 and 100 for the 4 algorithms.The so-called read efficiency is calculated as the number of tags divided by the number of required reading times.It is evident from Fig.6 that the PNBA algorithm is more efficient than the other 3 algorithms.BST and DBST are always the same.When the number of tags is between 5–40,BST and DBST gradually reduce to 0.2,and RBST is always maintained at 0.5.However,the PNBA algorithm gradually increases to 0.8.When the number of tags is larger than 40,the reading efficiency of the 4 algorithms changes slowly.BST and DBST are between 0.16–0.19,PNBA is between 0.89–0.93,and RBST is at 0.5.

Figs.7–10 illustrates the number comparison of needed transmission bits number when the tags’number to be identified is between 5 and 100 for the 4 algorithms underK=8,K=16,K=24 andK=32 respectively.

It can be found that in the cases with different values ofK,the relative relationship and changing trend of the 4 algorithms in the transmission bit number is consistent.

With the increase of the tags number to be identified,the needed transmission bits number for the 4 algorithms increases gradually.And the gap between the 4 algorithms is widened gradually.Besides,with the growing ofKvalue,the gap between the 4 algorithms increases gradually as well.

Figure 6:Comparison of reading efficiency under different number of tags to be identified for 4 algorithms

Figure 7:Comparison of number of bits transmitted of 4 algorithms with K =8 for DBST

Figure 8:Comparison of number of bits transmitted of 4 algorithms with K= 16 for DBST

Figure 9:Comparison of number of bits transmitted of 4 algorithms with K= 24 for DBST

Figure 10:Comparison of number of bits transmitted of 4 algorithms with K =32 for DBST

It is clear from Figs.7–10 that BST needs the greatest transmission bits number,DBST takes the second place.Since RBST can reduce the transmitted bits number of each identifying procedure,it is lower than DBST,but higher than PNBA.The reason is that PNBA needs lower identifying number than RBST,and PNBA can exploit the conflicting information in the stack to avoid the transmission of a large number of duplicate data.PNBA is always the lowest under the differentKvalues.

Fig.11 depicts the comparison of the transmission efficiency of the 4 algorithms when the number of tags to be identified is between 5 and 100.According to Tab.4,the transmission efficiency of DBST is only related to the value ofK.Therefore,the simulations of DBST underK= 8,16,24,32 are carried out respectively.The so-called transmission efficiency is calculated asK × Ndivided by the total number of transmission bits.It is obvious from Fig.11 that the relationship of BST,RBST and PNBA in transmission efficiency is consistent with that in reading efficiency from Fig.6,and PNBA is greater than BST and RBST significantly.When the tag number is 5,DBST is higher than PNBA,DBST withK=8 is 9% greater than PNBA,DBST withK=32 is 19%greater than PNBA.

Figure 11:Comparison of the transmission efficiency of the 4 algorithms

However,with the increase of tags number,DBST declines dramatically.When the tags number is 15,DBST is lower than PNBA and close to RBST.The reason is the sharp increase in the number of transmissions required by the DBST with the increase of the tags number.When the tags number is greater than 15,the DBST is less than RBST.And for DBST with differentKvalues,the greater the value ofK,the higher the transmission efficiency is.However,the greater theKvalue,the smaller the improvement of the transmission efficiency.As shown in Fig.11,DBST withK= 8 is significantly lower than that of the DBST withK=16,while the transmission efficiency is close for the DBST withK=16,24,32.

6 Conclusion

Aiming the multiple tags collision problem in the RFID system,this paper exploits physical layer network coding and presents physical layer network coding based binary search tree algorithm(PNBA).In PNBA,the multiple tags collision signal is exploited to reduce the times of identifying and improve reading efficiency.In addition,the physical layer network coding usually needs strict synchronization.The decoding of multiple tags conflicting information with non-strict synchronization will be the future work.

Acknowledgement:The authors wish to thank anonymous reviewers for their valuable comments and suggestions for the improvement of this paper.

Funding Statement:This work was supported by the National Natural Science Foundation of China under Grant 61502411;Natural Science Foundation of Jiangsu Province under Grant BK20150432 and BK20151299;Natural Science Research Project for Universities of Jiangsu Province under Grant 15KJB520034;China Postdoctoral Science Foundation under Grant 2015M581843;Jiangsu Provincial Qinglan Project;Teachers Overseas Study Program of Yancheng Institute of Technology;Jiangsu Provincial Government Scholarship for Overseas Studies;Talents Project of Yancheng Institute of Technology under Grant KJC2014038;“2311” Talent Project of Yancheng Institute of Technology;Open Fund of Modern Agricultural Resources Intelligent Management and Application Laboratory of Huzhou Normal University.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.