Method of addressing messages, method of establishing wireless communications, and communications system

• US 20010043569A1
• Filed: 01/31/2001
• Published: 11/22/2001
• Est. Priority Date: 02/19/1998
• Status: Active Grant

• Current Assignee: Round Rock Research LLC
• Original Assignee: Clifton W. Wood Jr
• Inventors: Wood, Clifton W. Jr.
• Granted Patent: US 6,307,848 B1
• Time in Patent Office: Days
• US Class Current: 370/256
• 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/10049 binary tree
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• 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 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 representing subgroups of the multiple wireless identification devices, the number of devices in a subgroup in one level being half of the number of devices in the next higher level, the tree search method employing level skipping wherein at least one level of the tree is skipped. 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 levels of the tree are occasionally skipped.

Claims

1. A method of 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 representing subgroups of the multiple wireless identification devices, the number of devices in a subgroup in one level being half of the number of devices in the next higher level, the tree search method employing level skipping wherein at least one level of the tree is skipped.

2. 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.

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

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 that is one quarter of the first mentioned specified group.

4. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with

claim 3

wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply.

5. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with

claim 3

wherein sending a reply to the interrogator comprises transmitting the random value of the device sending the reply.

6. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with

claim 3

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.

7. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with

claim 3

wherein, after receiving a reply without collision from a device, the interrogator sends a command individually addressed to that device.

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

the interrogator transmitting 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 or equal to the entire set of random values, the plurality of possible groups being organized in a binary tree having a plurality of levels, wherein groups of random values decrease in size by half with each level descended;

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 at least two levels in the tree.

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 8

wherein establishing unique identification numbers for respective devices comprises establishing a predetermined number of bits to be used for the unique identification numbers.

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 9

and further including establishing a predetermined number of bits to be used for the random values.

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 10

wherein the predetermined number of bits to be used for the random values comprises sixteen bits.

12. A method of addressing messages from an interrogator to a selected one or more of a number of communications devices in accordance with

claim 10

wherein devices sending a reply to the interrogator do so within a randomly selected time slot of a number of slots.

13. 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, the first predetermined number being a multiple of sixteen;

establishing a second predetermined number of bits to be used for random values, the second 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 from the interrogator 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 or equal to the entire set of random values, the plurality of possible groups being organized in a binary tree having a plurality of levels, wherein groups of random values decrease in size by half with each level;

receiving the command at multiple of the devices, the 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;

determining using the interrogator 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, wherein at least one level of the tree is skipped, 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.

14. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with

claim 13

wherein exactly one level is skipped.

15. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with

claim 13

wherein the first predetermined number of bits is sixteen.

16. A method of addressing messages from an interrogator to a selected one or more of a number of RFID devices in accordance with

claim 13

wherein the first predetermined number of bits is sixteen and the second predetermined number of bits is sixteen.

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 13

and further comprising, after the interrogator transmits a command requesting devices having random values within the new specified group of random values to respond:

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.

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 17

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.

19. 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 levels of the tree are skipped in some instances.

20. A communications system in accordance with

claim 19

wherein the tree search technique is a binary tree search technique.

21. A communications system in accordance with

claim 19

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

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 that is one quarter of the first mentioned specified group.

23. A system in accordance with

claim 22

wherein sending a reply to the interrogator comprises transmitting the unique identification number of the device sending the reply.

24. A system in accordance with

claim 22

wherein sending a reply to the interrogator comprises transmitting the random value of the device sending the reply.

25. A system in accordance with

claim 22

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.

26. A system in accordance with

claim 22

wherein the interrogator further includes means for, after receiving a reply without collision from a device, sending a command individually addressed to that device.

27. 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 a plurality of possible groups of random values to respond, 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 having a plurality of levels, wherein groups of random values decrease in size by half with each level descended;

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 at least two levels in the tree.

28. A system in accordance with

claim 27

wherein the random values have a predetermined number of bits.

29. A system in accordance with

claim 27

wherein respective devices are configured to store unique identification numbers of a predetermined number of bits.

30. A system in accordance with

claim 27

wherein respective devices are configured to store unique identification numbers of sixteen bits.

31. 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, the first predetermined number being an integer multiple of sixteen, respective devices being further configured to store a second predetermined number of bits to be used for random values, the second predetermined number being an integer multiple of sixteen, 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 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, 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, wherein at least one level of the tree is skipped, 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.

32. A system in accordance with

claim 31

wherein the interrogator is configured to skip exactly one level when creating the new, smaller, specified group.

33. A system in accordance with

claim 31

wherein the number of possible time slots is four, wherein the first predetermined number of bits is sixteen.

34. A system in accordance with

claim 31

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.

35. A system in accordance with

claim 31

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.

36. A system in accordance with

claim 35

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.