Method of addressing messages and communications system

• US RE40,686 E1
• Filed: 08/28/2003
• Issued: 03/31/2009
• Est. Priority Date: 02/19/1998
• Status: Expired due to Term

• Current Assignee: Round Rock Research LLC
• Original Assignee: Keystone Technology Solutions, LLC
• Inventors: Wood, Clifton W. Jr.
• Primary Examiner(s): Patel; Ajit
• Application Number:
  US10/652,573
• Time in Patent Office: 2,042 Days
• Field of Search: 370/346, 370/348, 370/347, 370/449, 370/461, 370/462
• US Class Current: 370/346
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04W 4/00 Services specially adapted for wireless communication networks; Facilities therefor

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 attempt to identify individual ones of the multiple wireless identification devices so as to be able to perform 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 nodes respectively representing subgroups of the multiple wireless identification devices, wherein the interrogator transmits a command at a node, requesting that devices within the subgroup represented by the node respond, wherein the interrogator determines if a collision occurs in response to the command and, if not, repeats the command at the same node. An interrogator configured to transmit a command at a node, requesting the devices within the subgroup represented by the node respond, the interrogator further being configured to determine if a collision occurs in response to the command and, if not, to repeat the command at the same node.

Claims

1. A method of establishing wireless communications between an interrogator and wireless identification devices, the method comprising utilizing a tree search technique to establish communications, without collision, between the interrogator and individual ones of the multiple wireless identification devices, the method including using a search tree having multiple nodes respectively representing subgroups of the multiple wireless identification devices, the method further comprising, for a node, transmitting a command, using the interrogator, requesting that devices within the subgroup represented by the node respond, determining with the interrogator if a collision occurred in response to the command and, if not, repeating the command at the same node.

2. A method in accordance with claim 1 and further comprising, if a collision occurred in response to the first mentioned command, sending a command at a different node, using the interrogator.

3. A method in accordance with claim 1 wherein when a subgroup contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, the device that is not within communications range of the interrogator does not response to the command.

4. A method in accordance with claim 1 wherein when a subgroup contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, the device that is within communications range of the interrogator responds to the command.

5. A method in accordance with claim 1 wherein a device in a subgroup changes between being within communications range of the interrogator and not being within communications range, over time.

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;

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

transmitting a communication, from the interrogator, requesting devices having random values within a first specified group of random values to respond;

receiving the communication at multiple devices, devices receiving the communication respectively determining if the random value chosen by the device falls within the first 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 second specified group smaller than the first specified group; and

, if not, again transmitting a communication requesting devices having random values within the first specified group of random values to respond.

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 in accordance with claim 7 wherein one of the first and second specified groups contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, and wherein the device that is not within communications range of the interrogator does not respond to the interrogator.

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, after receiving a reply without collision from a device, the interrogator sends a communication individually addressed to that device.

11. A method of addressing messages from a transponder to a selected one or more of a number of communications device, 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 a communication from the transponder requesting devices having random values within a specified group of a plurality of possible groups of random values to respond, the plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, the specified group being defined as being at one of the nodes;

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

and, if not, not sending a reply; and

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

, if not, transmitting a communication at the same node.

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

13. A method of addressing messages from a transponder 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 RFID devices, the method comprising:

establishing for respective devices unique identification numbers;

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

receiving the command at multiple RFID devices, RFID devices receiving the command respectively determining if their chosen random values fall within the specified group and, only if so, sending a reply to the interrogator, wherein sending a reply to the interrogator comprises transmitting 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 different level of the tree, the interrogator transmitting a command requesting devices having random values within the new specified group of random values to respond; and

, if not, the interrogator re-transmitting a command requesting devices having random values within the first mentioned 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.

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 14 wherein the first mentioned specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, and wherein the device that is not within communications range of the interrogator does not respond to the transmitting of the command or the re-transmitting of the command.

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 14 wherein the first mentioned specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, and wherein the device that is within communications range of the interrogator responds to the transmitting of the command and the re-transmitting of the command.

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 14 wherein a device in the first mentioned specified group is capable of changing between being within communications range of the interrogator and not being within communications range of the interrogator over time.

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 14 wherein the devices respectively comprise an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator.

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

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 19 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 capable of communicating with the interrogator are identified.

21. A communications system comprising an interrogator, and a plurality of wireless identification devices configured to communicate with the interrogator using RF, the interrogator being configured to employ tree searching to attempt to identify individual ones of the multiple wireless identification devices, so as to be able to perform communications without collision between the interrogator and individual ones of the multiple wireless identification devices, the interrogator being configured to follow a search tree, the tree having multiple nodes respectively representing subgroups of the multiple wireless identification devices, the interrogator being configured to transmit a command at a node, requesting that devices within the subgroup represented by the node respond, the interrogator further being configured to determine if a collision occurs in response to the command and, if not, to repeat the command at the same node.

22. A communications system in accordance with claim 21 wherein the interrogator is configured to send a command at a different node if a collision occurs in response to the first mentioned command.

23. A communications system in accordance with claim 21 wherein a subgroup contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator.

24. A communications system in accordance with claim 21 wherein a subgroup contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator, and wherein the device that is within communications range of the interrogator responds to the command.

25. A communications system in accordance with claim 21 wherein a device in a subgroup is movable relative to the interrogator so as to be capable of changing between being within communications range of the interrogator and not being within communications range.

26. A communications system in accordance with claim 21 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 for respective devices unique identification numbers respectively having the first predetermined number of bits;

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, to 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, to create a new, smaller, specified group; and

, if not, transmit a command requesting devices having random values within the same specified group of random values to respond.

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

29. A system in accordance with claim 27 wherein a specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator.

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

31. A system comprising:

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

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 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, the specified group being defined as being at one of the nodes;

devices receiving the command being configured to respectively 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 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 different level of the tree, the interrogator being configured to transmit a command requesting devices having random values within the new specified group of random values to respond; and

, if not, the interrogator being configured to re-transmit a command requesting devices having random values within the first mentioned specified group of random values to respond.

32. A system in accordance with claim 31 wherein the first mentioned specified group contains both a device that is within communications range of the interrogator, and a device that is not within communications range of the interrogator.

33. A system in accordance with claim 31 wherein a device in the first mentioned specified group is capable of changing between being within communications range of the interrogator and not being within communications range of the interrogator over time.

34. A system in accordance with claim 31 wherein the respective devices comprise an integrated circuit including a receiver, a modulator, and a microprocessor in communication with the receiver and modulator.

35. 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 a unique identification number, respective devices being further configured to store a random value;

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 plurality of possible groups being organized in a binary tree defined by a plurality of nodes at respective levels, the specified group being defined as being at one of the nodes;

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; 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, to create a new, smaller, specified group by descending in the tree; and

, if not, to transmit a command at the same node.

36. A system in accordance with claim 35 wherein the unique identification numbers for respective devices are stored in digital form and respectively comprise a predetermined number of bits.

37. A system in accordance with claim 35 wherein the random values for respective devices are stored in digital form and respectively comprise a predetermined number of bits.

38. 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, to create further new specified groups and repeat 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 responding devices capable of responding are identified.

39. A method of establishing wireless communications between an interrogator and wireless identification devices, the method comprising:

transmitting a first interrogation command, using the interrogator, to a first plurality of wireless identification devices, said command requesting that devices receiving the command respond to the interrogator;

detecting with the interrogator if a collision occurred in response to the interrogation command;

sending an interrogation command to at least a portion of said first plurality of wireless identification devices until no collision is detected; and

once no collision is detected, sending another interrogation command to at least a portion of said first plurality of wireless identification devices.

40. The method of claim 39, further comprising, after sending said first interrogation command and detecting a collision, sending a signal to at least one wireless identification device configured to avoid a subsequent collision.

41. The method of claim 39, wherein the interrogation command sent to at least a portion of said wireless identification devices after a collision is detected is sent to the entire first plurality of wireless identification devices.

42. The method of claim 39, wherein said interrogation command sent to said first plurality of wireless identification devices is the same interrogation command as is subsequently sent to at least a portion of said wireless identification devices.

43. The method of claim 39, further comprising, after said step of sending an interrogation command after no collision is detected, sending a communication to a selected wireless identification device through use of an identification individually addressed to that device.

44. A method of establishing wireless communications between an interrogator and wireless identification devices, the method comprising:

transmitting a first interrogation command, using the interrogator, to a first plurality of wireless identification devices, said command requesting that devices receiving the command respond to the interrogator;

detecting if a collision occurred in response to the interrogation command;

in the event of detection of a collision, sending a signal to at least one wireless identification device to avoid a subsequent collision;

sending an interrogation command to at least a portion of said first plurality of wireless identification devices until no collision is detected; and

once no collision is detected, sending another interrogation command to said first plurality of wireless identification devices.

45. A method comprising:

performing arbitration including sending a first command from an interrogator to a plurality of wireless identification devices;

receiving a good reply from a first wireless identification device of the plurality of wireless identification devices in response to the first command;

sending a second command from the interrogator to silence the first wireless identification device; and

resending the first command from the interrogator to the plurality of wireless identification devices.

46. The method of claim 45 wherein performing the arbitration is done using a search tree.

47. The method of claim 46 wherein the first command requests a response from wireless identification devices associated with a first node of the search tree.

48. The method of claim 45 wherein the second command individually addresses the first wireless identification device.

49. The method of claim 45 wherein the good reply comprises unique ID received by the interrogator without a collision detected.

50. An arbitration method comprising:

sending a first command from an interrogator to a plurality of wireless identification devices;

receiving a reply from a first wireless identification device of the plurality of wireless identification devices, and detecting no collisions, in response to the first command; and

resending the first command from the interrogator to the plurality of wireless identification devices in response to receiving the reply and detecting no collisions.

51. The method of claim 50, further comprising sending a second command from the interrogator to silence the first wireless identification device, in response to receiving the reply, before resending the first command.

52. The method of claim 51, wherein sending the second command comprises sending a number associated with the first wireless identification device to address the first wireless identification device.

53. The method of claim 50, further comprising:

sending a third command from the interrogator to the plurality of wireless identification devices;

receiving a reply from a second wireless identification device of the plurality of wireless identification devices, and detecting no collisions, in response to the third command; and

resending the third command from the interrogator to the plurality of wireless identification devices in response to receiving the reply from the second wireless identification device and detecting no collisions.

54. The method of claim 50, wherein sending the first command comprises sending a request for identification, the request including at least a portion of a number that identifies the first wireless identification.

55. The method of claim 54, wherein the portion of the number is associated with a node of a search tree.

56. The method of claim 50, wherein receiving the reply includes receiving the reply at a randomly selected time.

57. The method of claim 56, wherein receiving the reply at a randomly selected time is in accordance with an Aloha method.

58. The method of claim 57, wherein the Aloha method is a slotted Aloha method.

59. The method of claim 50, wherein sending the first command comprises sending a request for identification, the request including a number associated with a node of a search tree, and wherein receiving the reply is in accordance with an Aloha method.

60. The method of claim 50, wherein receiving the reply comprises receiving at least a portion of a number that identifies the first wireless identification device.