Method of addressing messages and communications systems

• US RE43,382 E1
• Filed: 02/07/2010
• Issued: 05/15/2012
• Est. Priority Date: 02/19/1998
• Status: Expired due to Term

• Current Assignee: Round Rock Research LLC
• Original Assignee: Round Rock Research LLC
• Inventors: Wood, Clifton W. Jr.
• Primary Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US12/701,563
• Time in Patent Office: 828 Days
• Field of Search: 370/329, 370/346, 370/347, 370/460, 370/408, 370/230, 370/437, 370/441, 370/442, 370/449, 370/458, 370/463, 370/342, 370/447, 370/445, 370/448, 370/432, 370/461, 370/475, 370/345, 370/348
• US Class Current: 370/329
• CPC Class Codes: H04W 4/00 Services specially adapted for wireless communication networks; Facilities therefor

Abstract

A method of and apparatus for establishing wireless communications between an interrogator and individual ones of multiple wireless identification devices, the method comprising utilizing a tree search method to establish communications without collision between the interrogator and individual ones of the multiple wireless identification devices, a search tree being defined for the tree search method, the tree having multiple levels respectively representing subgroups of the multiple wireless identification devices, the method further comprising starting the tree search at a selectable level of the search tree. A communications system comprising an interrogator, and a plurality of wireless identification devices configured to communicate with the interrogator in a wireless fashion, the respective wireless identification devices having a unique identification number, the interrogator being configured to employ a tree search technique to determine the unique identification numbers of the different wireless identification devices so as to be able to establish communications between the interrogator and individual ones of the multiple wireless identification devices without collision by multiple wireless identification devices attempting to respond to the interrogator at the same time, wherein the interrogator is configured to start the tree search at a selectable level of the search tree. In one embodiment, the interrogator transmits a first request indicating a subgroup of random numbers out of a total number of possible random numbers. The wireless identification devices each determine if the random number generated by each wireless identification device falls within the subgroup, and if so, the wireless identification device responds to the interrogator. If a collision between wireless identification device responses is detected by the interrogator, the interrogator transmits a second request indicating a subgroup of random numbers.

Claims

1. A method of establishing wireless communications between an interrogator and individual ones of multiple wireless identification devices, the wireless identification devices having respective identification numbers and being addressable by specifying identification numbers with any one of multiple possible degrees of precision, the method comprising utilizing a tree search in an arbitration scheme to determine a degree of precision necessary to establish one-on-one communications between the interrogator and individual ones of the multiple wireless identification devices, a search tree being defined for the tree search method, the tree having multiple selectable levels respectively representing subgroups of the multiple wireless identification devices, the level at which a tree search starts being variable the method further comprising starting the tree search at any selectable level of the search tree.

2. A method in accordance with claim 1 and further comprising determining the maximum possible number of wireless identification devices that could communicate with the interrogator, and selecting a level of the search tree based on the determined maximum possible number of wireless identification devices that could communicate with the interrogator.

3. A method in accordance with claim 2 and further comprising starting the tree search at a level determined by taking the base two logarithm of the determined maximum possible number, wherein the level of the tree containing all subgroups is considered level zero, and lower levels are numbered consecutively.

4. A method in accordance with claim 2 and further comprising starting the tree search at a level determined by taking the base two logarithm of the determined maximum possible number, wherein the level of the tree containing all subgroups is considered level zero, and lower levels are numbered consecutively, and wherein the maximum number of devices in a subgroup in one level is half of the maximum number of devices in the next higher level.

5. A method in accordance with claim 2 and further comprising starting the tree search at a level determined by taking the base two logarithm of the power of two nearest the determined maximum possible number, wherein the level of the tree containing all subgroups is considered level zero, and lower levels are numbered consecutively, and wherein the maximum number of devices in a subgroup in one level is half of the maximum number of devices in the next higher level.

6. A method in accordance with claim 1 wherein the wireless identification device comprises an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator.

7. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices, the method comprising:

establishing for respective devices unique identification numbers respectively having a first predetermined number of bits;

establishing a second predetermined number of bits to be used for random values;

causing the devices to select random values, wherein respective devices choose random values independently of random values selected by the other devices;

determining the maximum number of devices potentially capable of responding to the interrogator;

transmitting a command from the interrogator requesting devices having random values within a specified group of random values to respond, by using a subset of the second predetermined number of bits, the specified group being chosen in response to the determined maximum number;

receiving the command at multiple devices, devices receiving the command respectively determining if the random value chosen by the device falls within the specified group and, if so, sending a reply to the interrogator; and

determining using the interrogator if a collision occurred between devices that sent a reply and, if so, creating a new, smaller, specified group.

8. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 7 wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply.

9. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 7 wherein sending a reply to the interrogator comprises transmitting the random value of the device sending the reply.

10. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 7 wherein sending a reply to the interrogator comprises transmitting both the random value of the device sending the reply and the unique identification number of the device sending the reply.

11. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 7 wherein, after receiving a reply without collision from a device, the interrogator sends a command individually addressed to that device.

12. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices, the method comprising:

causing the devices to select random values for use as arbitration numbers, wherein respective devices choose random values independently of random values selected by the other devices, the devices being addressable by specifying arbitration numbers with any one of multiple possible degrees of precision;

transmitting a command from the interrogator requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the specified group being less than the entire set of random values, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, wherein the size of groups of random values decrease in size by half with each node descended, wherein the specified group is below a node on the tree selected based on the maximum number of devices capable of communicating with the interrogator;

receiving the command at multiple devices, devices receiving the command respectively determining if the random value chosen by the device falls within the specified group and, if so, sending a reply to the interrogator; and

, if not, not sending a reply; and

determining using the interrogator if a collision occurred between devices that sent a reply and, if so, creating a new, smaller, specified group by descending in the tree.

13. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 12 and further including establishing a predetermined number of bits to be used for the random values.

14. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 13 wherein the predetermined number of bits to be used for the random values comprises an integer multiple of eight.

15. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 13 wherein devices sending a reply to the interrogator do so within a randomly selected time slot of a number of slots.

16. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices, the method comprising:

establishing for respective devices a predetermined number of bits to be used for random values, the predetermined number being a multiple of sixteen;

causing the devices to select random values, wherein respective devices choose random values independently of random values selected by the other devices;

transmitting a command from the interrogator requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the specified group being equal to or less than the entire set of random values, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, wherein the maximum size of groups of random values decrease in size by half with each node descended, wherein the specified group is below a node on a level of the tree selected based on the maximum number of devices known to be capable of communicating with the interrogator;

receiving the command at multiple devices, devices receiving the command respectively determining if the random value chosen by the device falls within the specified group and, only if so, sending a reply to the interrogator, wherein sending a reply to the interrogator comprises transmitting both the random value of the device sending the reply and the unique identification number of the device sending the reply;

using the interrogator to determine if a collision occurred between devices that sent a reply and, if so, creating a new, smaller, specified group using a level of the tree different from the level used in the interrogator transmitting, the interrogator transmitting a command requesting devices having random values within the new specified group of random values to respond; and

if a reply without collision is received from a device, the interrogator subsequently sending a command individually addressed to that device.

17. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 16 and further comprising determining the maximum possible number of wireless identification devices that could communicate with the interrogator.

18. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 16 wherein selecting the level of the tree comprises taking the base two logarithm of the determined maximum possible number, wherein a level of the tree containing all subgroups is considered level zero, and lower levels are numbered consecutively.

19. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 16 wherein selecting the level of the tree comprises taking the base two logarithm of the determined maximum possible number, wherein a level of the tree containing all subgroups is considered level zero, and lower levels are numbered consecutively, and wherein the maximum number of devices in a subgroup in one level is half of the maximum number of devices in the next higher level.

20. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 16 wherein selecting the level of the tree comprises taking the base two logarithm of the power of two nearest the determined maximum possible number, wherein the level of the tree containing all subgroups is considered level zero, and lower levels are numbered consecutively, and wherein the maximum number of devices in a subgroup in one level is half of the maximum number of devices in the next higher level.

21. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 16 wherein the wireless identification device comprises an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator.

22. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 16 and further comprising, after the interrogator transmits a command requesting devices having random values within the new specified group of random values to respond, determining, using devices receiving the command, if their chosen random values fall within the new smaller specified group and, if so, sending a reply to the interrogator.

23. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 22 and further comprising, after the interrogator transmits a command requesting devices having random values within the new specified group of random values to respond, determining if a collision occurred between devices that sent a reply and, if so, creating a new specified group and repeating the transmitting of the command requesting devices having random values within a specified group of random values to respond using different specified groups until all of the devices within communications range are identified.

24. A communications system comprising an interrogator, and a plurality of wireless identification devices configured to communicate with the interrogator in a wireless fashion, the wireless identification devices having respective identification numbers, the interrogator being configured to employ a tree search in a search tree having multiple selectable levels, to determine the identification numbers of the different wireless identification devices with sufficient precision so as to be able to establish one-on-one communications between the interrogator and individual ones of the multiple wireless identification devices, wherein the interrogator is configured to start the tree search at any selectable level of the search tree.

25. A communications system in accordance with claim 24 wherein the tree search is a binary tree search.

26. A communications system in accordance with claim 24 wherein the wireless identification device comprises an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator.

27. A system comprising:

an interrogator;

a number of communications devices capable of wireless communications with the interrogator;

means for establishing a predetermined number of bits to be used as random numbers, and for causing respective devices to select random numbers respectively having the predetermined number of bits;

means for inputting a predetermined number indicative of the maximum number of devices possibly capable of communicating with the receiver;

means for causing the interrogator to transmit a command requesting devices having random values within a specified group of random values to respond, the specified group being chosen in response to the inputted predetermined number;

means for causing devices receiving the command to determine if their chosen random values fall within the specified group and, if so, send a reply to the interrogator; and

means for causing the interrogator to determine if a collision occurred between devices that sent a reply and, if so, create a new, smaller, specified group.

28. A system in accordance with claim 27 wherein sending a reply to the interrogator comprises transmitting the random value of the device sending the reply.

29. A system in accordance with claim 27 wherein the interrogator further includes means for, after receiving a reply without collision from a device, sending a command individually addressed to that device.

30. A system comprising:

an interrogator configured to communicate to a selected one or more of a number of communications devices;

a plurality of communications devices;

the devices being configured to select random values, wherein respective devices choose random values independently of random values selected by the other devices, different sized groups of devices being addressable by specifying random values with differing levels of precision;

the interrogator being configured to transmit a command requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the specified group being less than the entire set of random values, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, wherein the size of groups of random values decrease in size by half with each node descended, wherein the specified group is below a node on the tree selected based on a predetermined maximum number of devices capable of communicating with the interrogator;

devices receiving the command being configured to respectively determine if their chosen random values fall within the specified group and, if so, send a reply to the interrogator; and

, if not, not send a reply; and

the interrogator being configured to determine if a collision occurred between devices that sent a reply and, if so, create a new, smaller, specified group by descending in the tree.

31. A system in accordance with claim 30 wherein the random values respectively have a predetermined number of bits.

32. A system in accordance with claim 30 wherein respective devices are configured to store unique identification numbers of a predetermined number of bits.

33. A system in accordance with claim 30 wherein respective devices are configured to store unique identification numbers of sixteen bits.

34. A system comprising:

an interrogator configured to communicate to a selected one or more of a number of RFID devices;

a plurality of RFID devices, respective devices being configured to store unique identification numbers respectively having a first predetermined number of bits, respective devices being further configured to store a second predetermined number of bits to be used for random values, respective devices being configured to select random values independently of random values selected by the other devices;

the interrogator being configured to transmit an identify command requesting a response from devices having random values within a specified group of a plurality of possible groups or random values, the specified group being less than or equal to the entire set of random values, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, wherein the maximum size of groups of random values decrease in size by half with each node descended, wherein the specified group is below a node on a level of the tree selected based on the maximum number of devices known to be capable of communicating with the interrogator;

devices receiving the command respectively being configured to determine if their chosen random values fall within the specified group and, only if so, send a reply to the interrogator, wherein sending a reply to the interrogator comprises transmitting both the random value of the device sending the reply and the unique identification number of the device sending the reply;

the interrogator being configured to determine if a collision occurred between devices that sent a reply and, if so, create a new, smaller, specified group using a level of the tree different from the level used in previously transmitting an identify command, the interrogator transmitting an identify command requesting devices having random values within the new specified group of random values to respond; and

the interrogator being configured to send a command individually addressed to a device after communicating with a device without a collision.

35. A system in accordance with claim 34 wherein the interrogator is configured to input and store the predetermined number.

36. A system in accordance with claim 34 wherein the devices are configured to respectively determine if their chosen random values fall within a specified group and, if so, send a reply, upon receiving respective identify commands.

37. A system in accordance with claim 36 wherein the interrogator is configured to determine if a collision occurred between devices that sent a reply in response to respective identify commands and, if so, create further new specified groups and repeat the transmitting of the identify command requesting devices having random values within a specified group of random values to respond using different specified groups until all responding devices are identified.

38. A method, comprising:

transmitting, from a reader, an initial wireless command to start identification of a plurality of radio frequency identification (RFID) tags, the initial wireless command specifying at least two bits and requesting first RFID tags having the at least two bits to reply with at least random numbers generated on the first RFID tags as identifiers to be used by the reader in subsequent communications to individually address the first RFID tags;

determining whether there is a collision in response to the initial wireless command;

identifying, from a response to the initial command, a random number generated at an RFID tag, if there is no collision in response to the initial wireless command; and

transmitting, from the reader, a subsequent wireless command to identify RFID tags, the subsequent command specifying at least the two bits to request replies.

39. The method of claim 38, wherein the first RFID tags are to select time slots, based on random numbers generated on the first RFID tags, to reply to the initial wireless command.

40. The method of claim 39, further comprising:

transmitting, from the reader, at least one command to indicate the time slots to the first RFID tags.

41. The method of claim 38, wherein the random number is a sixteen-bit random number.

42. The method of claim 38, wherein the subsequent wireless command includes one bit more than the at least two bits specified in the initial wireless command.

43. The method of claim 38, further comprising:

transmitting, from the reader, an acknowledge command in response to the random number being identified from the response.

44. The method of claim 38, wherein the RFID tag is to further communicate to the reader at least a portion of an identification code of the RFID tag.

45. A radio frequency identification (RFID) interrogator, comprising:

one or more antennas;

a controller;

a transmitter coupled to the controller and the one or more antennas to send a first wireless radio frequency (RF) signal to start identification of individual tags of a population of RFID tags, the first RF signal requesting RFID tags having first bits specified in the first RF signal to reply, the first bits having at least two bits; and

a receiver coupled to the controller and the one or more antennas to detect a collision in response to the first RF signal and, when there is no collision in response to the first RF signal, to determine an identifier of a first RFID tag from a reply to the first RF signal;

wherein the transmitter is to subsequently use the identifier, determined from the reply to the first RF signal, to address the first RFID tag, among the population of RFID tags, for a response from the first RFID tag.

46. The interrogator of claim 45, wherein the transmitter is to further send a second wireless RF signal to specify at least the first bits and to request RFID tags having bits specified in the second RF signal to reply.

47. The interrogator of claim 45, wherein the first RF signal requests the RFID tags having the first bits specified in the first RF signal to reply with at least random numbers generated on respective RFID tags;

and the first RFID tag is identified via a random number provided by the first RFID tag in the reply to the first RF signal.

48. The interrogator of claim 45, wherein a random number provided by the first RFID tag in the reply to the first RF signal has sixteen bits.

49. The interrogator of claim 45, wherein the transmitter is to further send an acknowledge signal to the first RFID tag, in response to a random number being identified from the reply.

50. A radio frequency identification (RFID) system, comprising:

a plurality of RFID tags; and

an interrogator having a range for wireless communications, the plurality of RFID tags disposed within the range for communications with the interrogator, the interrogator comprising;

at least one antenna,

a transmitter coupled to the at least one antenna to transmit a first wireless radio frequency (RF) signal to initiate a search to identify the RFID tags, the first RF signal specifying at least two bits, wherein RFID tags having the at least two bits reply to the first RF signal with at least random numbers generated on respective RFID tags, and

a receiver coupled to the at least one antenna to identify, from at least one reply to the first RF signal, a random number generated by a first RFID tag, if there is no response collision in replying to the first RF signal;

wherein the transmitter is to subsequently use the random number, identified from the reply to the first RF signal, to request a response from the first RFID tag.

51. The RFID system of claim 50, wherein each of the RFID tags having the at least two bits generates a random value to determine a time slot to reply.

52. The RFID system of claim 51, wherein the transmitter is to further transmit a plurality of second signals to indicate a plurality of time slots to reply.

53. The RFID system of claim 50, wherein the transmitter is to transmit a second signal to cause the first RFID tag to generate the random number as an identifier.

54. The RFID system of claim 53, wherein the second signal is different from the first signal.

55. The RFID system of claim 50, wherein the random number is a sixteen-bit number.

56. The RFID system of claim 50, wherein the at least two bits are a portion of the random number.

57. A radio frequency identification (RFID) system, comprising:

an interrogator to transmit an initial wireless radio frequency (RF) signal to start a search to identify RFID tags, the initial wireless RF signal specifying at least two first bits and requesting replies; and

a set of RFID tags, each tag of the set having;

an antenna,

a memory storing a plurality of bits; and

a circuit coupled to the antenna to receive the initial RF signal, to compare the at least two first bits with corresponding bits stored in the memory, to independently generate a random number as an identifier, to generate a random value to select a time slot to reply, and to reply with the random number in accordance with the time slot, if there is a match between the at least two first bits specified in the initial RF signal and the corresponding bits stored in the memory;

wherein the interrogator is to individually address a first RFID tag among the set of RFID tags, using the random number of the first RFID tag identified from a reply to the first wireless RF signal, to request a response from the first RFID tag.

58. The system of claim 57, wherein the interrogator is to further transmit at least one signal to indicate subsequent time slots for RFID tags having the at least two first bits to reply.

59. The system of claim 57, wherein the interrogator is to transmit a separate signal to cause each tag of the set to generate the random number.

60. The system of claim 59, wherein the random number is a sixteen-bits number.

61. The system of claim 59, wherein the interrogator is to further transmit an acknowledge signal if a first RFID tag is identified from a response to the initial RF signal.

62. The system of claim 57, wherein each tag of the set is to transmit the random number via backscattering.

63. A radio frequency identification (RFID) method, comprising:

transmitting, from a reader, a first wireless command to initiate identification of a population of RFID tags and a plurality of subsequent wireless commands to continue the identification of a population of RFID tags, the first command including first bits, the first command to request a set of RFID tags having the first bits to reply with identifiers of the set of RFID tags, the identifiers including random numbers individually generated by the set of RFID tags, the first bits including at least two bits;

generating, by the set of RFID tags, the random numbers independent from each other;

generating, by the set of RFID tags, random values;

replying, by the set of RFID tags, to the first command and the subsequent command with at least the random numbers of the set of RFID tags, in an order in accordance with the random values;

receiving, at the reader, a reply to the first command from a first RFID tag;

determining whether there is a collision in replying to the first command;

if there is no collision in replying to the first command, identifying from the reply a random number generated by the first RFID tag; and

transmitting a second wireless command to address the first RFID tag using the random number, the second wireless command to request a response from the first RFID tag addressed by the random number.

64. The method of claim 63, further comprising:

transmitting a third wireless command from the reader to continue identification of a population of RFID tags, the third command including at least the first bits included in the first command.

65. The method of claim 64, wherein the third command includes one more bit than the first bits to address RFID tags.

66. The method of claim 63, wherein the random number is a sixteen-bit random number.

67. The method of claim 63, wherein the first bits is a portion of the random number.

68. The method of claim 63, wherein the subsequent commands comprise coordination pulses to indicate time slots.

69. The method of claim 63, wherein the first RFID tag further transmits at least a portion of an identification code to the reader.

70. The method of claim 63, wherein each of the subsequent wireless commands continues the request of the first wireless command.

71. The method of claim 63, wherein each of the subsequent wireless commands indicates a time slot for replying in accordance with the request of the first wireless command.

72. The method of claim 63, further comprising:

transmitting, from the reader, an acknowledge command in response to the random number being identified from the reply.

73. A radio frequency communications-based method of conducting a financial transaction, comprising:

sending a first wireless radio frequency (RF) signal to start identification of one or more radio frequency devices of a population of radio frequency devices, the first RF signal requesting one or more radio frequency devices having at least two first bits specified in the first RF signal to reply;

receiving a response via a receiver coupled to a controller and one or more antennas, said receiver, said controller and said one or more antennas configured to detect a collision in response to the first RF signal and, when there is no collision in response to the first RF signal, to determine an identifier of a first radio frequency device from a reply to the first RF signal;

addressing the first radio frequency device using the identifier determined from the reply to the first RF signal so as to elicit a subsequent response from the first radio frequency device; and

initiating a financial transaction based at least in part on said acts of sending, receiving and addressing, thereby resulting in the debiting of an account associated with said first radio frequency device.

74. The method of claim 73, wherein the financial transaction is associated with the payment of a toll.

75. The method of claim 74, wherein said receiver and said one or more antennas is disposed within a toll booth, and said method further comprises operating said receiver disposed within said toll booth at least when said first radio frequency device issuing said response to said first wireless RF signal is in proximity thereto.

76. The method of claim 74, wherein the financial transaction comprises receiving a credit card number against which the toll can be charged.

77. The method of claim 73, wherein the debiting of the account comprises charging a credit card number associated with an owner of the account.

78. The method of claim 73, wherein the financial transaction is for payment for goods or services.

79. The method of claim 78, further comprising:

transmitting a subsequent wireless command requesting one or more responses to continue the identification of one or more radio frequency devices within the population of radio frequency devices, the subsequent wireless command to identify a subset of the population of radio frequency devices and request the subset to reply with identification numbers.

80. The method of claim 73, wherein the response comprises further information about the first radio frequency communications device.

81. The method of claim 73, wherein the identifier comprises a unique identification code that uniquely identifies the first radio frequency device among the population of radio frequency devices.

82. The method of claim 73, wherein the identifier comprises a random number generated by the first radio frequency device.

83. The method of claim 73, wherein the first radio frequency device is configured to select a random value that determines a time slot in which the first radio frequency device provides the response.