Improving RFID reader throughput!

Folks,

         I'm doing performance measurements on our MCU based RFID
reader. The very problem I'm facing is redundancy of tag ID (say 12
bytes) transmission, every time my MCU receives a tag ID; will just
push that ID to UART without any prior knowledge of that it is sending
the same ID again and again. (Due to poor designs of RFID tag protocols
single tag can response its ID repeatedly unless some other tag steps
in). Is it possible to implement some AI or data structure technique to
avoid that? And to decide that this tag id was pushed before so no use
to resend go-on to process another incoming IDs.

I just can't ignore the incoming tags while executing some complex
comparison or say search algorithm even assuming that I have 2K free
memory.


Thanks for your time
ali

Ali wrote:

> Folks,
> 
>          I'm doing performance measurements on our MCU based RFID
> reader. The very problem I'm facing is redundancy of tag ID (say 12
> bytes) transmission, every time my MCU receives a tag ID; will just
> push that ID to UART without any prior knowledge of that it is sending
> the same ID again and again. (Due to poor designs of RFID tag protocols
> single tag can response its ID repeatedly unless some other tag steps

So the RFID tag should have enough code and memory to keep track of 
other tags in its immediate area ??

The kind of looses the idea of being cheap.


> in). Is it possible to implement some AI or data structure technique to
> avoid that? And to decide that this tag id was pushed before so no use
> to resend go-on to process another incoming IDs.
> 
> I just can't ignore the incoming tags while executing some complex
> comparison or say search algorithm even assuming that I have 2K free
> memory.
> 
> Thanks for your time
> ali
> 


Good Luck

Ali wrote:
> Folks,
>
>          I'm doing performance measurements on our MCU based RFID
> reader. The very problem I'm facing is redundancy of tag ID (say 12
> bytes) transmission, every time my MCU receives a tag ID; will just
> push that ID to UART without any prior knowledge of that it is sending
> the same ID again and again. (Due to poor designs of RFID tag protocols
> single tag can response its ID repeatedly unless some other tag steps
> in). Is it possible to implement some AI or data structure technique to
> avoid that? And to decide that this tag id was pushed before so no use
> to resend go-on to process another incoming IDs.
>
> I just can't ignore the incoming tags while executing some complex
> comparison or say search algorithm even assuming that I have 2K free
> memory.


Are you just looking for a fast way to filter tags, IOW, something
like: don't retransmit a tag already sent in the last N seconds?

Perhaps a hash to divide your search space into N buckets of M tags
(perhaps 64 buckets of four tags), then just search the M tags, and
manage those on a pseudo-LRU basis?  Obviously all that depends on
exactly how much filtering you want to do, and how much CPU time and
memory you actually have available to do it.

robertwessel2@yahoo.com wrote:
> Ali wrote:
> > Folks,
> >
> >          I'm doing performance measurements on our MCU based RFID
> > reader. The very problem I'm facing is redundancy of tag ID (say 12
> > bytes) transmission, every time my MCU receives a tag ID; will just
> > push that ID to UART without any prior knowledge of that it is sending
> > the same ID again and again. (Due to poor designs of RFID tag protocols
> > single tag can response its ID repeatedly unless some other tag steps
> > in). Is it possible to implement some AI or data structure technique to
> > avoid that? And to decide that this tag id was pushed before so no use
> > to resend go-on to process another incoming IDs.
> >
> > I just can't ignore the incoming tags while executing some complex
> > comparison or say search algorithm even assuming that I have 2K free
> > memory.
>
>
> Are you just looking for a fast way to filter tags, IOW, something
> like: don't retransmit a tag already sent in the last N seconds?
>
> Perhaps a hash to divide your search space into N buckets of M tags
> (perhaps 64 buckets of four tags), then just search the M tags, and
> manage those on a pseudo-LRU basis?  Obviously all that depends on
> exactly how much filtering you want to do, and how much CPU time and
> memory you actually have available to do it.

Donald Wrote:

>So the RFID tag should have enough code and memory to keep track of other tags in >its immediate area ??

Yes you are right the right place to handle this problem is tag side.
Well friend as I mentioned in my post that we are developing reader so
it is suppose to operate with third party products ( tags falling in
reader supported protocols i.e. ISO , EM , EPC Gen 1 or Gen 2 . )
All rfid tags use binary or aloha algorithm to backscatter their
response (ID), these algorithms assure to minimize the tags response in
anit-collision situation but neither of these algorithm consider that
tag should not be responding repeatedly. The bottom line is that I need
to provide logic on reader to avoid retransmitting the ID!

I was just thinking if following can work:

Assumptions :
RS = An double index array for holding the 15 tags ID.
RS_Counter = This counter will help to make that straight array look
like circular list.

Pseudo-code:
If(RS[RS_Counter] == Recently_Processed_ID)
//Do nothing and process new incoming ID because RS_Counter will always
point to last transmitted ID.


for(i=RS_Counter ; i == 0; i--)
if(RS[i] == Recently_Pocessed_ID)
//got it in list so no use to transmit skip to process more incoming
IDs

If(RS_Counter == 15)
//Ok here I'm! could not find any ID in my stored array so time to
put in array and transmit it.
RS_Counter = 0;
RS[RS_Counter++] = Recently_Processed_ID
//Send it to UART while storing it in array but before make sure that
that array is not full. If array is filled then overwrite the oldest ID
in array, whihc is allways at the starting index.

Not sure if it is worthy ,of course it simply can't be the solution
if I'm using more processing as compare to retransmission. 



ali

On 29 Aug 2006 07:53:20 -0700, "Ali" <abdulrazaq@gmail.com> wrote:

>
>Folks,
>
>         I'm doing performance measurements on our MCU based RFID
>reader. The very problem I'm facing is redundancy of tag ID (say 12
>bytes) transmission, every time my MCU receives a tag ID; will just
>push that ID to UART without any prior knowledge of that it is sending
>the same ID again and again. (Due to poor designs of RFID tag protocols
>single tag can response its ID repeatedly unless some other tag steps
>in). Is it possible to implement some AI or data structure technique to
>avoid that? And to decide that this tag id was pushed before so no use
>to resend go-on to process another incoming IDs.
>
>I just can't ignore the incoming tags while executing some complex
>comparison or say search algorithm even assuming that I have 2K free
>memory.
>
>
>Thanks for your time
>ali

Ali
  What tag formats are you trying to read?  If it is one or more of
the EPC Global formats, all of them (Class 0, Class 1, and Class 1 Gen
2) have a means within the protocol to silence a tag once it has
reported its ID.  If it is some other tag protocol, I'm afraid I
cannot help you.

Reards
-Bill Knight
R O SoftWare

Bill Knight wrote:
> On 29 Aug 2006 07:53:20 -0700, "Ali" <abdulrazaq@gmail.com> wrote:
>
> >
> >Folks,
> >
> >         I'm doing performance measurements on our MCU based RFID
> >reader. The very problem I'm facing is redundancy of tag ID (say 12
> >bytes) transmission, every time my MCU receives a tag ID; will just
> >push that ID to UART without any prior knowledge of that it is sending
> >the same ID again and again. (Due to poor designs of RFID tag protocols
> >single tag can response its ID repeatedly unless some other tag steps
> >in). Is it possible to implement some AI or data structure technique to
> >avoid that? And to decide that this tag id was pushed before so no use
> >to resend go-on to process another incoming IDs.
> >
> >I just can't ignore the incoming tags while executing some complex
> >comparison or say search algorithm even assuming that I have 2K free
> >memory.
> >
> >
> >Thanks for your time
> >ali
>
> Ali
>   What tag formats are you trying to read?  If it is one or more of
> the EPC Global formats, all of them (Class 0, Class 1, and Class 1 Gen
> 2) have a means within the protocol to silence a tag once it has
> reported its ID.  If it is some other tag protocol, I'm afraid I
> cannot help you.
>
> Reards
> -Bill Knight
> R O SoftWare


Hello Bill,
         Our reader is supporting ISO 18000 Type B and C, where as we
are supporting Class 1 from Gen2. Well as a original developer of these
protocols I don't know if there is a way to make these tags silence!
But I remember there was a sleep command in Gen1.
Lets take an example of ISO Type B, do you think there is a way to make
these tags silence? Well if you say that using GROUP_SELECT_X commands
(where X is EQUAL , LESS or GREATER etc..) can solve the problem then
question is; what to do with tags that are exposed very first time to
reader?

And how about Gen2 say we are in inventory process how to do that? How
one can command the tags not to retransmit their IDs? my anti-collision
design is using Query(x)[Where x is less than equal to 15 and greater
than equal to 0] , QueryAdjust(x) [Where x is Q+1 , Q and Q-1] in a
loop


Thanks for your time and I'm glad that I got company here;-) can you
point some rfid related useNet places?

ali

Bill Knight wrote:
> On 29 Aug 2006 07:53:20 -0700, "Ali" <abdulrazaq@gmail.com> wrote:
>
> >
> >Folks,
> >
> >         I'm doing performance measurements on our MCU based RFID
> >reader. The very problem I'm facing is redundancy of tag ID (say 12
> >bytes) transmission, every time my MCU receives a tag ID; will just
> >push that ID to UART without any prior knowledge of that it is sending
> >the same ID again and again. (Due to poor designs of RFID tag protocols
> >single tag can response its ID repeatedly unless some other tag steps
> >in). Is it possible to implement some AI or data structure technique to
> >avoid that? And to decide that this tag id was pushed before so no use
> >to resend go-on to process another incoming IDs.
> >
> >I just can't ignore the incoming tags while executing some complex
> >comparison or say search algorithm even assuming that I have 2K free
> >memory.
> >
> >
> >Thanks for your time
> >ali
>
> Ali
>   What tag formats are you trying to read?  If it is one or more of
> the EPC Global formats, all of them (Class 0, Class 1, and Class 1 Gen
> 2) have a means within the protocol to silence a tag once it has
> reported its ID.  If it is some other tag protocol, I'm afraid I
> cannot help you.
>
> Reards
> -Bill Knight
> R O SoftWare


Hello Bill,
         Our reader is supporting ISO 18000 Type B and C, where as we
are supporting Class 1 from Gen2. Well as a original developer of these
protocols I don't know if there is a way to make these tags silence!
But I remember there was a sleep command in Gen1.
Lets take an example of ISO Type B, do you think there is a way to make
these tags silence? Well if you say that using GROUP_SELECT_X commands
(where X is EQUAL , LESS or GREATER etc..) can solve the problem then
question is; what to do with tags that are exposed very first time to
reader?

And how about Gen2 say we are in inventory process how to do that? How
one can command the tags not to retransmit their IDs? my anti-collision
design is using Query(x)[Where x is less than equal to 15 and greater
than equal to 0] , QueryAdjust(x) [Where x is Q+1 , Q and Q-1] in a
loop


Thanks for your time and I'm glad that I got company here;-) can you
point some rfid related useNet places?

ali

In article <1156915907.497673.230230@h48g2000cwc.googlegroups.com>, 
abdulrazaq@gmail.com says...
> 
> >So the RFID tag should have enough code and memory to keep track of other tags in >its immediate area ??
> 
> Yes you are right the right place to handle this problem is tag side.
> 
He was joking.
Why should the tag need to handle that.
The tag is the dumb side the receiver is suppose to have enough 
resources to track tags that won't/can't shut up. 

Ali wrote:
> robertwessel2@yahoo.com wrote:
> > Ali wrote:
> > > Folks,
> > >
> > >          I'm doing performance measurements on our MCU based RFID
> > > reader. The very problem I'm facing is redundancy of tag ID (say 12
> > > bytes) transmission, every time my MCU receives a tag ID; will just
> > > push that ID to UART without any prior knowledge of that it is sending
> > > the same ID again and again. (Due to poor designs of RFID tag protoco=
ls
> > > single tag can response its ID repeatedly unless some other tag steps
> > > in). Is it possible to implement some AI or data structure technique =
to
> > > avoid that? And to decide that this tag id was pushed before so no use
> > > to resend go-on to process another incoming IDs.
> > >
> > > I just can't ignore the incoming tags while executing some complex
> > > comparison or say search algorithm even assuming that I have 2K free
> > > memory.
> >
> >
> > Are you just looking for a fast way to filter tags, IOW, something
> > like: don't retransmit a tag already sent in the last N seconds?
> >
> > Perhaps a hash to divide your search space into N buckets of M tags
> > (perhaps 64 buckets of four tags), then just search the M tags, and
> > manage those on a pseudo-LRU basis?  Obviously all that depends on
> > exactly how much filtering you want to do, and how much CPU time and
> > memory you actually have available to do it.
>
> Donald Wrote:
>
> >So the RFID tag should have enough code and memory to keep track of othe=
r tags in >its immediate area ??
>
> Yes you are right the right place to handle this problem is tag side.
> Well friend as I mentioned in my post that we are developing reader so
> it is suppose to operate with third party products ( tags falling in
> reader supported protocols i.e. ISO , EM , EPC Gen 1 or Gen 2 . )
> All rfid tags use binary or aloha algorithm to backscatter their
> response (ID), these algorithms assure to minimize the tags response in
> anit-collision situation but neither of these algorithm consider that
> tag should not be responding repeatedly. The bottom line is that I need
> to provide logic on reader to avoid retransmitting the ID!
>
> I was just thinking if following can work:
>
> Assumptions :
> RS =3D An double index array for holding the 15 tags ID.
> RS_Counter =3D This counter will help to make that straight array look
> like circular list.
>
> Pseudo-code:
> If(RS[RS_Counter] =3D=3D Recently_Processed_ID)
> //Do nothing and process new incoming ID because RS_Counter will always
> point to last transmitted ID.
>
>
> for(i=3DRS_Counter ; i =3D=3D 0; i--)
> if(RS[i] =3D=3D Recently_Pocessed_ID)
> //got it in list so no use to transmit skip to process more incoming
> IDs
>
> If(RS_Counter =3D=3D 15)
> //Ok here I'm! could not find any ID in my stored array so time to
> put in array and transmit it.
> RS_Counter =3D 0;
> RS[RS_Counter++] =3D Recently_Processed_ID
> //Send it to UART while storing it in array but before make sure that
> that array is not full. If array is filled then overwrite the oldest ID
> in array, whihc is allways at the starting index.
>
> Not sure if it is worthy ,of course it simply can't be the solution
> if I'm using more processing as compare to retransmission.
>
>
>
> ali



Pseudo-code

Definitions:
row =3D represent the total number of tags that array can store.
ID_SIZE =3D Represents the tag ID size.
Search  =3D Array will be treated as FIFO data structure while performing
the search; that is, start search from latest ID to oldest
Storing  =3D Array will be treated as LIFO data structure while
performing the search; that is, replace the oldest ID first.

Pre-process

1)	Set the tag ID_SIZE according to selected protocol tag ID size.
2)	Flush the array.
3)	Row points to 'zero' index at the start.

Algorithm

The below code is used once the incoming ID has passed the CRC check.

Because we increment after saving the ID start from current row to 0
	for(k=3Drow; k >=3D0 ; k--)
Start searching from CRC as it is 16 bit so there are ample chances
that these tow bytes are unique(but not for sure) and start with next
tag ID if there is even a single mismatch.
            for(j=3D0 , i=3DID_SIZE; i >=3D0 ; i--)
	{
		if(RS[k][i] =3D=3D rawid[i])
			j++;
		else
			break; leave this tag ID and iterate for another
			if(j=3D=3DID_SIZE)
Ok ID is in the list so exit and indicate host if required
				goto exit;


		}
We could not find the ID in straight search, now start searching the
rest of the old IDs.
Start max size to row+1, as we always increment row after storing at
current location so it is already current row + 1.
for(k=3D14; k >=3D row ; k--)
Again start searching from CRC bytes first.
	for(j=3D0 , i=3DID_SIZE; i >=3D0 ; i--)
		{
		if(RS[k][i] =3D=3D rawid[i])
			j++;
		else
			break; leave this tag ID and iterate for another

Ok ID is in the list so exit. Indicate host if required
				if(j=3D=3DID_SIZE)
				goto exit;
		}

Could not find it , so store it for further reference and push it to
UART
		for(i=3D0; i <=3D ID_SIZE; i++)
		sendbyte((RS[row][i] =3D rawid[i]));
Increment row.
		row++;
Ok array is full start treating it as a LIFO for saving new incoming
IDs.
	if(row =3D=3D 0x0e) // this is size - 1 of rows
                 row=3D0;


The worse case of this algorithm is the overhead of searching, storing
and transmitting which requires extra  time which counts to 25=B1
overhead. However, the ideal case is quite promising, as it just
requires =BD millisecond to search and notify the reader that tag is
already in the list. This can save next  5 to 8 milliseconds(Depending
on the communication datarate) for transmitting the same ID, that is
tow more tags can be processed in the same time.


ali