Data communication method using identification protocol

• US 5,500,650 A
• Filed: 12/15/1992
• Issued: 03/19/1996
• Est. Priority Date: 12/15/1992
• Status: Expired due to Term

• Current Assignee: Round Rock Research LLC
• Original Assignee: Micron Technology, Inc.
• Inventors: Tuttle, John R., Rotzoll, Robert R., Allen, David H., Snodgrass, Charles K., Pax, George E.
• Primary Examiner(s): Sotomayor, John B.
• Application Number:
  US07/990,915
• Time in Patent Office: 1,190 Days
• Field of Search: 342/42, 342/44, 342/45, 342/50, 342/51
• US Class Current: 342/42
• CPC Class Codes: G01S 13/758 using a signal generator powered by the interrogation signal
• CPC Class Codes: G01S 13/765 with exchange of information between interrogator and responder
• CPC Class Codes: G01S 13/78 discriminating between different kinds of targets, e.g. IFF-radar, i.e. identification of friend or foe G01S13/75, G01S13/79 take precedence
• CPC Class Codes: G06K 19/0723 the record carrier comprising an arrangement for non-contact communication, e.g. wireless communication circuits on transponder cards, non-contact smart cards or RFIDs
• CPC Class Codes: G06K 19/073 Special arrangements for circuits, e.g. for protecting identification code in memory protection against unauthorised use of computer memory G06F12/14
• 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: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]
• CPC Class Codes: H04L 61/5046 Resolving address allocation conflicts; Testing of addresses testing when self-assigning an address H04L61/5092
• CPC Class Codes: H04L 61/5069 for group communication, multicast communication or broadcast communication
• CPC Class Codes: H04L 61/5084 Providing for device mobility network addressing or numbering for mobility support in wireless networks H04W8/26; mobile IP H04W80/04
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use

Abstract

A protocol is used to coordinate the use of a common communication medium by one or more interrogating commander stations and an unknown plurality of responding responder stations. Each commander station and each responder station is equipped to broadcast messages and to check for error in received messages. When more than one station attempts to broadcast simultaneously, an erroneous message is received and communication is interrupted. To establish uninterrupted communication, a commander station broadcasts a command causing each responder station of a potentially large first number of responder stations to each select a random number from a known range and retain it as its arbitration number. After receipt of such a command, each addressed responder station transmits a response message containing its arbitration number. Zero, one, or several responses may occur simultaneously. By broadcasting requests for identification to various subsets of the full range of arbitration numbers and checking for an immediate error-free response, a commander station can determine the arbitration number of every responder station capable of communicating at the time. Consequently, a commander station can conduct subsequent uninterrupted communication with each responder station, for example by addressing only one responder station. Responder stations of this invention require minimal logic and circuitry to respond to multiple commander stations.

Claims

1. For communication between a commander communication transceiver and a plurality of responder communication transceivers, a method for each responder transceiver to establish an address number so that it can be individually addressed by the commander transceiver, comprising the steps of:

a) establishing a set of possible addresses for responder transceivers;

b) the commander transceiver transmitting a generate message requesting responder transceivers who receive the message to select a new address; and

c) upon receipt of the generate message, each responder transceiver choosing a random address from the set of possible addresses, wherein each responder transceiver chooses its address independently of addresses chosen by all other responder transceivers;

d) whereby the addresses chosen by the responder transceivers are randomly distributed within the set of possible addresses, and whereby the commander transceiver controls when the responder transceivers choose new addresses.

2. A method according to claim 1, further comprising the subsequent steps of:

each responder transceiver transmitting an identification message containing its chosen address;

upon receipt of identification messages from different responder transceivers containing the same chosen address, the commander transceiver transmitting an address reset message; and

upon receipt of the address reset message, each responder transceiver choosing a new address.

3. A method according to claim 1, further comprising the subsequent steps of:

the commander transceiver transmitting an identification request message requesting responder transceivers having addresses within a specified first subset of addresses to identify themselves without selecting a new address, the first subset being less than the entire set of possible addresses; and

upon receipt of the identification request message, each responder transceiver

i) determining whether its previously chosen address is within the first subset, and if it is, then

ii) transmitting an identification message containing its chosen address.

4. A method according to claim 3, further comprising the subsequent steps of:

upon receipt of identification messages from different responder transceivers containing the same chosen address, the commander transceiver transmitting an address reset message addressed to a specified second subset of addresses, wherein the second subset includes the first subset, the second subset being less than or equal to the entire set; and

upon receipt of the address reset message, each responder transceiver

i) determining whether its most recently chosen address is within the second subset, and if so, then

ii) choosing a new address.

5. A method according to claim 1, wherein:

the generate message specifies for response a first subset of addresses within the set of possible addresses, said first subset being less than or equal to the entire set of possible addresses; and

after the step of choosing a random address, each responder transceiver

i) determining whether its chosen address is within the first subset specified in the received first message, and if so, then

ii) transmitting an identification message containing its chosen address.

6. A method according to claim 5, further comprising the subsequent steps of:

the commander transceiver transmitting an identification request message requesting responder transceivers having addresses within a specified second subset of addresses to identify themselves without selecting a new address, the second subset being less than the entire set; and

upon receipt of the an identification request message, each responder transceiver

i) determining whether its previously chosen address is within the second subset, and if it is, then

ii) transmitting an identification message containing its chosen address.

7. A method according to claim 5, further comprising the subsequent steps of:

upon receipt of identification messages from different responder transceivers containing the same chosen address, the commander transceiver transmitting an address reset message; and

upon receipt of the address reset message, each responder transceiver choosing a new address.

8. A method according to claim 5, further comprising the subsequent steps of:

upon receipt of identification messages from different responder transceivers containing the same chosen address, the commander transceiver transmitting an address reset message addressed to a specified third subset of addresses, wherein the third subset includes the first subset, the third subset being less than or equal to the entire set; and

upon receipt of the address reset message, each responder transceiver

i) determining whether its previously chosen address is within the third subset, and if it is, then

ii) choosing a new address.

9. A method of addressing messages from a commander station communication transceiver to a selected one or more of a plurality of responder station communication transceivers, comprising the steps of:

a) establishing a first predetermined number of bits to be used for unique identification numbers, and establishing for each responder transceiver a unique identification number having said predetermined number of bits;

b) establishing a second predetermined number of bits to be used for arbitration addresses, the second number being less than the first number, and establishing a set of possible arbitration addresses having said second number of bits;

c) the commander transceiver transmitting a generate message requesting responder transceivers who receive the generate message to select a new arbitration address;

d) the commander transceiver transmitting an identification request message requesting responder transceivers to respond identifying themselves, wherein the message specifies for response a first subset of arbitration addresses within the set of possible arbitration addresses, said first subset being less than the entire set; and

e) after receiving the generate message, each responder transceiver choosing an arbitration address having the second number of bits, wherein each responder transceiver chooses its arbitration address independently of arbitration addresses chosen by all other responder transceivers; and

f) after receiving the identification request message, each responder transceiver

i) determining whether its chosen arbitration address is within the first subset specified in the identification request message, and if it is, then

ii) transmitting an arbitration identification message containing its chosen arbitration address and a unique identification message containing its unique identification number.

10. A method according to claim 9, wherein

after receiving an arbitration identification message containing the arbitration address of a responder transceiver, the commander transceiver transmitting a command message containing that arbitration address;

and

the step of each responder transceiver transmitting the unique identification message is delayed until the responder transceiver receives said command message from the commander transceiver.

11. A method according to claim 9, wherein the unique identification message transmitted by each responder transceiver includes both that transceiver'"'"'s arbitration address and its unique identification number.

12. A method according to claim 9, further comprising the subsequent steps of:

upon receipt of arbitration identification messages from different responder transceivers containing the same arbitration address, the commander transceiver transmitting an address reset message; and

upon receipt of the address reset message, each responder transceiver choosing a new arbitration address.

13. A method according to claim 9, further comprising the subsequent steps of:

upon receipt of identification messages from different responder transceivers containing the same chosen address, the commander transceiver transmitting an address reset message addressed to a specified second subset of addresses, wherein the second subset includes the first subset, the second subset being less than or equal to the entire set; and

upon receipt of the address reset message, each responder transceiver

i) determining whether its most recently chosen address is within the second subset, and if so, then

ii) choosing a new address.

14. A method of establishing an address number in a responder station communication transceiver so that it can be individually addressed by a commander station communication transceiver, comprising the steps of:

a) establishing a set of possible responder transceiver addresses;

b) the commander transceiver transmitting a first command message;

c) after receipt of the first command message, each responder transceiver

i) choosing an address independently of addresses chosen by all other responder transceivers, and then

ii) transmitting an identification message containing its chosen address;

d) the commander transceiver

i) detecting whether it receives identification messages from different responder transceivers containing the same address, and if so, then

ii) transmitting a second command message; and

e) after receipt of the second command message, each responder transceiver choosing a new address;

f) whereby the commander transceiver can individually address a message to any of said responder transceivers by using the responder transceiver'"'"'s chosen address.

15. A method according to claim 14, wherein each step of choosing an address comprises choosing a random address within the set of all possible addresses.

16. A method of establishing an address number in a responder station communication transceiver so that it can be individually addressed by a commander station communication transceiver, comprising the steps of:

a) establishing a set of possible responder transceiver addresses;

b) the commander transceiver transmitting a first command message requesting responder transceivers who receive the message to select a new address and to respond identifying themselves, wherein the message specifies for response a subset of addresses within the set of possible addresses, the subset being less than or equal to the entire set;

c) after receipt of the first command message, each responder transceiver

i) choosing an address independently of addresses chosen by all other responder transceivers, and then

ii) if the chosen address is within the subset specified in the first command message, transmitting an identification message containing the chosen address;

d) the commander transceiver

i) detecting whether it receives identification messages from different responder transceivers containing the same address, and if so, then

ii) transmitting a second command message addressed to a second subset of addresses, wherein the second subset includes the first subset, the second subset being less than or equal to the entire set of possible addresses; and

e) after receipt of the second command message, each responder transceiver

i) determining whether its previously chosen address is within the second subset, and if it is, then

ii) choosing a new address

f) whereby the commander transceiver can individually address a message to any of said responder transceivers by using the responder transceiver'"'"'s chosen address.

17. A method according to claim 16, wherein each step of choosing an address comprises choosing a random address within the set of all possible addresses.

18. A method for a commander communication transceiver to poll a plurality of responder communication transceivers to determine their addresses, comprising the steps of:

(A) establishing a set of possible addresses for the responder transceivers;

(B) the commander transceiver transmitting a Clear Polling Lock message;

(C) upon receipt of the Clear Polling Lock message, each responder transceiver clearing a Polling Lock flag in a memory device within that responder transceiver;

(D) the commander transceiver transmitting a first polling message requesting responder transceivers having addresses within a specified first subset of addresses to identify themselves, the first subset being less than or equal to the entire set of possible addresses;

(E) upon receipt of the first polling message, each responder transceiver

1) determining whether its address is within the first subset, and if it is, then

2) transmitting an identification message containing its address;

(F) the commander transceiver determining whether it receives an identification message from a responder transceiver which is not corrupted by a collision with another message, and if so, then

1) transmitting a Set Polling Lock message addressed to the responder transceiver from whom the commander transceiver received the uncorrupted identification message, and

2) subsequently transmitting a second polling message requesting responder transceivers having addresses within a specified second subset of addresses to identify themselves, wherein the second subset includes the first subset, the second subset being less than or equal to the entire set of possible addresses;

(G) each responder transceiver, upon receipt of a Set Polling Lock message addressed to that responder transceiver, setting the Polling Lock flag within that responder transceiver;

(H) upon receipt of the second polling message, each responder transceiver

1) determining whether its address is within the second subset and whether its Polling Lock flag is clear, and if both conditions are true, then

2) transmitting an identification message containing its address; and

(I) the commander transceiver

1) determining whether it receives, in response to the second polling message, a plurality of identification messages which collide with each other so as to be unintelligible to the commander transceiver, and if so, then

2) repeating steps (F) through (I), using in each repetition a progressively smaller second subset, until the commander transceiver does not receive unintelligible, colliding identification messages in response to the second polling message.

19. A method according to claim 18, further including the steps of

the commander transceiver determining whether any of the identification messages transmitted by the responder transceivers contain duplicate addresses, and if so, then

i) the commander transceiver transmitting a Clear Polling Lock message, and

ii) the commander transceiver transmitting a message requesting the responder transceivers to choose new addresses.