Method of addressing messages and communications system

• US 20050207364A1
• Filed: 06/01/2005
• Published: 09/22/2005
• Est. Priority Date: 02/19/1998
• Status: Active Grant

• Current Assignee: Round Rock Research LLC
• Original Assignee: Round Rock Research LLC
• Inventors: Wood, Clifton W. Jr.
• Granted Patent: US 7,760,677 B2
• Time in Patent Office: Days
• US Class Current: 370/310
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10019 resolving collision on the communication channels between simultaneously or concurrently interrogated record carriers. collision between the communication channels used by wireless communication devices, where the solution is not particularly adapted for RFIDs or the like, H04W74/08
• CPC Class Codes: G06Q 20/24 Credit schemes, i.e. "pay after"
• CPC Class Codes: G06Q 20/26 Debit schemes, e.g. "pay now"
• CPC Class Codes: G06Q 20/3223 Realising banking transactions through M-devices
• CPC Class Codes: G07B 15/00 Arrangements or apparatus for collecting fares, tolls or entrance fees at one or more control points handling coins or valuable papers, e.g. banknotes, G07D; apparatus for vending or hiring articles or services activated by coins, credit cards, paper currency or the like G07F7/00, G07F17/00
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 74/06 using polling
• CPC Class Codes: H04W 74/08 Non-scheduled access, e.g. ALOHA hybrid access H04W74/02
• CPC Class Codes: H04W 76/11 Allocation or use of connection identifiers
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support

Abstract

A method of establishing wireless communications between an interrogator and individual ones of multiple wireless identification devices, the method comprising combining tree search and Aloha methods to establish communications between the interrogator and individual ones of the multiple wireless identification devices without collision. A 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 tree search and Aloha techniques 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.

Claims

1-40. -40. (canceled)

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

establishing a first predetermined number of bits to be used as unique identification numbers, and establishing for respective devices unique identification numbers respectively having the 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;

transmitting a command from the interrogator requesting devices having random values within a specified group of random values to respond, the specified group being less than or equal to the entire set of random values;

receiving the command at multiple devices, the devices receiving the command respectively determining if the random value chosen by the command falls within the specified group and, if so, sending a reply to the interrogator within a randomly selected time slot of a number of slots; and

, if not, not sending a reply; and

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

42. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 41 wherein the sending of a reply to the interrogator within a randomly selected time slot is in accordance with an Aloha technique.

43. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 41 wherein the sending of a reply to the interrogator within a randomly selected time slot is in accordance with slotted Aloha.

44. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 41 wherein the method is an adaptive method.

45. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 41 wherein the number of slots is four.

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

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

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

49. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 41 wherein the time slot randomly selected by a device is selected using a random number different from the random value of that device.

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

establishing unique identification numbers for respective devices;

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

transmitting from the interrogator a command requesting devices having random values within a specified group of random values to respond, the specified group being less than or equal to the entire set of random values;

receiving the command at multiple devices, the 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 within a randomly selected time slot of a number of slots; 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.

51. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with claim 50 wherein establishing unique identification numbers for respective devices comprises establishing a predetermined number of bits to be used for the unique identification numbers.

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

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

54. 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 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;

transmitting from the interrogator a command requesting devices having random values within a specified group of random values to respond, the specified group being less than or equal to the entire set of random values;

receiving the command at multiple devices, the devices receiving the command respectively determining if the random values chosen by the device falls within the specified group and, if so, sending a reply to the interrogator within a randomly selected time slot of a number of possible time slots, in accordance with an Aloha technique; and

, if not, not sending a reply, 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, and wherein the time slot randomly selected by a device is selected using a random number different from the random value of that device;

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

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

55. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 54 wherein the number of possible time slots is four.

56. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 54 wherein the number of possible time slots is four, wherein the first predetermined number of bits is sixteen, and wherein the second predetermined number of bits is sixteen.

57. 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 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;

transmitting from the interrogator a command requesting devices having random values within a specified group of random values to respond, the specified group being less than or equal to the entire set of random values;

receiving the command at multiple devices, the devices receiving the command respectively determining if the random values chosen by the device falls within the specified group and, if so, sending a reply to the interrogator within a randomly selected time slot of a number of possible time slots, in accordance with an Aloha technique; and

, if not, not sending a reply, 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, and wherein the time slot randomly selected by a device is selected using a random number different from the random value of that device;

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

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

wherein the number of possible slots varies from one specified group to another.

58. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 57 and further comprising, after creating a new, smaller, specified group;

the interrogator transmitting a command requesting devices having random values within a specified group of random values to respond, the specified group being less than or equal to the entire set of random values; and

devices receiving the command respectively determining if their chosen random values fall within the new smaller specified group and, if so, sending a reply to the interrogator within a randomly selected time slot of a number of possible time slots, in accordance with an Aloha technique.

59. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with claim 58 and further comprising the subsequent steps of the interrogator 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 devices are identified, for every command the devices receiving the command determining if their chosen random values fall within the specified group and, if so, sending a reply to the interrogator within a randomly selected time slot of a number of possible time slots, in accordance with an Aloha technique.

60. 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 tree search and Aloha techniques 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.

61. A communications system in accordance with claim 60 wherein the Aloha technique is a slotted Aloha technique.

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

63. A system comprising:

an interrogator;

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

means for establishing a first predetermined number of bits to be used as unique identification numbers, and for establishing for respective devices unique identification numbers respectively having the first predetermined number of bits;

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

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

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 less than or equal to the entire set of random values;

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 within a randomly selected time slot of a number of slots; and

, if not, not send a reply; 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.

64. A system in accordance with claim 63 wherein the sending of a reply to the interrogator within a randomly selected time slot is in accordance with an Aloha technique.

65. A system in accordance with claim 63 wherein the sending of a reply to the interrogator within a randomly selected time slot is in accordance with a slotted Aloha technique.

66. A system in accordance with claim 63 wherein the number of slots is four.

67. A system in accordance with claim 63 wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply.

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

69. A system in accordance with claim 63 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.

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

71. A system in accordance with claim 63 wherein the time slot randomly selected by a device is selected using a random number different from the random value of that device.

72. 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;

the interrogator being configured to transmit a command requesting devices having random values within a specified group of random values to respond, the specified group being less than or equal to the entire set of random values;

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 within a randomly selected time slot of a number of slots; 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.

73. A system in accordance with claim 72 wherein the predetermined number of bits to be used for the random values comprises sixteen bits.

74. 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, 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 a command requesting devices having random values within a specified group of random values to respond, the specified group being less than or equal to the entire set of random values;

devices receiving the command respectively being configured to determine if their chosen random values fall within the specified group and, if so, send a reply to the interrogator within a randomly selected time slot of a number of possible time slots, in accordance with an Aloha technique; and

, if not, not send a reply, 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, and wherein the time slot randomly selected by a device is selected using a random number different from the random value of that device;

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; and

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

wherein the number of possible slots varies from one specified group to another.

75. A system in accordance with claim 74 wherein the number of possible time slots is four.

76. A system in accordance with claim 74 wherein the number of possible time slots is four, wherein the first predetermined number of bits is sixteen, and wherein the second predetermined number of bits is sixteen.

77. 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, respective devices being configured to store unique identification numbers respectively having a first predetermined number of bits, respective devices being further configured to respectively store a second predetermined number of bits to be used for respective random values, respective devices being configured to select random values independently of random values selected by the other devices;

the interrogator being configured to define a group of random values, the group being a subset of all possible values the devices could select, and to transmit a command requesting devices having random values corresponding to any of the random values in the defined group to respond;

devices respectively being configured to, in response to receiving the command, determine if their chosen random values fall within the defined group and, if so, send a reply to the interrogator within a randomly selected time slot of a number of possible time slots, in accordance with Aloha; and

, if not, not send a reply, 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, wherein the time slot randomly selected by a device is selected using a random number different from the random value of that device, and wherein the number of possible slots varies from one specified group to another; and

the interrogator being configured to determine if a collision occurred between devices that sent a reply and, if so, to define a new, smaller, specified group.

78. A system in accordance with claim 77 wherein the number of possible time slots is four.

79. A system in accordance with claim 77 wherein the number of possible time slots is four, wherein the first predetermined number of bits is sixteen, and wherein the second predetermined number of bits is sixteen.

80. 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, respective devices being configured to store unique identification numbers, respective devices being further configured to respectively store respective random values, respective devices being configured to select random values independently of random values selected by the other devices;

the interrogator being configured to define a group of random values, the group being a subset of all possible values the devices could select, and to transmit a command requesting devices having random values corresponding to any of the random values in the defined group to respond;

devices respectively being configured to, in response to receiving the command, determine if their chosen random values fall within the defined group and, if so, send a reply to the interrogator within a randomly selected time slot of a number of possible time slots, in accordance with Aloha; and

, if not, not send a reply, wherein the number of possible time slots varies from one specified group to another; and

the interrogator being configured to determine if a collision occurred between devices that sent a reply and, if so, to define a new, smaller, specified group.