US5651009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for hybrid contention/polling protocol collision resolution using a depth first search technique
Assignee: Motorola Mobility LLC
•
Filing: 1995-05-02
•
Granted: 1997-07-22
•
Expires: 2015-05-02
Abstract
Abstract A method and system provide efficient resolution of transmission collisions in a simultaneous channel access communication environment. At least a first Master device and a plurality of Slave devices utilize the steps of: (1) transmitting, by the plurality of Slave devices upon receiving a contention poll from the first Master device, information to the Master device, wherein transmissions of the Slave devices provide a collision; (2) selecting a subset of Slaves allowed to retransmit following the collision, by the first Master device using a collision resolution poll in accordance with a predetermined depth first tree search technique; and (3) retransmitting, by the subset of Slave devices, the information to the Master device, and, where another collision is obtained, recycling to step 2 and repeating steps 2 and 3 until all collisions are resolved.
Inventors
- 👤 John A. Perreault
- 👤 Abhay Joshi
- 👤 Mete Kabatepe
- 👤 Lawrence W. Lloyd
- 👤 Stephen Schroeder
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 08:35
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/28; H04L12/40; H04L12/407; H04L12/413; H04L12/403
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
231 words
A method of providing efficient collision resolution for transmissions that collide in a simultaneous channel access communication system having at least a first Master device and a plurality of Slave devices, the method comprising the steps of: 14A) sending, by the Master device to the Slave devices, a contention poll authorizing at least two of the Slave devices to transmit on the simultaneous channel access communication system, wherein the contention poll represents an initial search depth; 14B) sending, by at least two of the Slave devices, transmissions on the simultaneous channel access communication system; 14C) detecting, by the Master device, that a collision occurred between the transmissions of a group of at least two of the Slave devices; and 14D) resolving the collision between said group of colliding Slave devices using a hybrid contention/polling protocol comprising the steps of: 14D1) incrementing the search depth; 14D2) dividing the group of colliding Slave devices into a predetermined number of subgroups, where each subgroup includes zero or more Slave devices, and wherein each subgroup is identified by a branch number; 14D3) recursively, for each subgroup, providing the Slave devices in the subgroup an opportunity to retransmit; 14D4) when a collision occurs for the subgroup, recursively cycling to step 14C1 and performing collision resolution using the subgroup as the group; and 14D5) when the subgroup is free from collisions, terminating collision resolution for the subgroup.
Claim 2
Independent Claim
231 words
A method of providing efficient collision resolution for transmissions that collide in a simultaneous channel access communication system having at least a first Master device and a plurality of Slave devices, the method comprising the steps of: 14A) sending, by the Master device to the Slave devices, a contention poll authorizing at least two of the Slave devices to transmit on the simultaneous channel access communication system, wherein the contention poll represents an initial search depth; 14B) sending, by at least two of the Slave devices, transmissions on the simultaneous channel access communication system; 14C) detecting, by the Master device, that a collision occurred between the transmissions of a group of at least two of the Slave devices; and 14D) resolving the collision between said group of colliding Slave devices using a hybrid contention/polling protocol comprising the steps of: 14D1) incrementing the search depth; 14D2) dividing the group of colliding Slave devices into a predetermined number of subgroups, where each subgroup includes zero or more Slave devices, and wherein each subgroup is identified by a branch number; 14D3) recursively, for each subgroup, providing the Slave devices in the subgroup an opportunity to retransmit; 14D4) when a collision occurs for the subgroup, recursively cycling to step 14C1 and performing collision resolution using the subgroup as the group; and 14D5) when the subgroup is free from collisions, terminating collision resolution for the subgroup.
Claim 3
Dependent Claim
41 words
The method of claim 1 wherein dividing each group of colliding Slave devices comprises: selecting, by each Slave device, a branch number in the range one to the predetermined number, where the branch number indicates one of the number of subgroups.
Claim 4
Dependent Claim
42 words
The method of claim 2 wherein providing the Slave devices in the subgroup an opportunity to transmit comprises: sending, by the Master device to the Slave devices, a collision resolution poll indicating the search depth and the branch number for the subgroup.
Claim 5
Dependent Claim
55 words
The method of claim 3 wherein, upon receipt of the collision resolution poll by the Slave devices, each Slave device having its branch number equal to the branch number specified in the collision resolution poll and having transmitted, at a search depth one less than the search depth specified in the collision resolution poll retransmits.
Claim 6
Dependent Claim
28 words
The method of claim 1 further comprising the step of, following incrementing the search depth, terminating collision resolution where the search depth exceeds a predetermined maximum search depth.
Claim 7
Dependent Claim
230 words
A hybrid contention/polling protocol system comprising: at least one Master device; and a plurality of Slave devices responsive to poll messages sent by the Master device on a downstream channel for transmitting messages to the Master device on an upstream channel shared by the plurality of Slave devices, wherein: the Master device sends a contention poll to the Slave devices authorizing at least two of the Slave devices to transmit on the shared channel, wherein the contention poll represents an initial search depth; at least two of the Slave devices send transmissions on the shared channel; the Master device detects that a collision occurred between the transmissions of a group of at least two of the Slave devices; and the collision between the group of colliding Slave devices is using a hybrid contention/polling protocol comprising the steps of: 19D1) incrementing the search depth; 19D2) dividing the group of colliding Slave devices into a predetermined number of subgroups, where each subgroup includes zero or more Slave devices, and wherein each subgroup is identified by a branch number; 19D3) recursively, for each subgroup, providing the Slave devices in the subgroup an opportunity to retransmit; 19D4) when a collision occurs for the subgroup, recursively cycling to step 6C1 and performing collision resolution using the subgroup as the group; and 19D5) when the subgroup is free from collisions, terminating collision resolution for the subgroup.
Claim 8
Dependent Claim
230 words
A hybrid contention/polling protocol system comprising: at least one Master device; and a plurality of Slave devices responsive to poll messages sent by the Master device on a downstream channel for transmitting messages to the Master device on an upstream channel shared by the plurality of Slave devices, wherein: the Master device sends a contention poll to the Slave devices authorizing at least two of the Slave devices to transmit on the shared channel, wherein the contention poll represents an initial search depth; at least two of the Slave devices send transmissions on the shared channel; the Master device detects that a collision occurred between the transmissions of a group of at least two of the Slave devices; and the collision between the group of colliding Slave devices is using a hybrid contention/polling protocol comprising the steps of: 19D1) incrementing the search depth; 19D2) dividing the group of colliding Slave devices into a predetermined number of subgroups, where each subgroup includes zero or more Slave devices, and wherein each subgroup is identified by a branch number; 19D3) recursively, for each subgroup, providing the Slave devices in the subgroup an opportunity to retransmit; 19D4) when a collision occurs for the subgroup, recursively cycling to step 6C1 and performing collision resolution using the subgroup as the group; and 19D5) when the subgroup is free from collisions, terminating collision resolution for the subgroup.
Claim 9
Dependent Claim
41 words
The method of claim 6 wherein dividing each group of colliding Slave devices comprises: selecting, by each Slave device, a branch number in the range one to the predetermined number, where the branch number indicates one of the number of subgroups.
Claim 10
Dependent Claim
42 words
The method of claim 7 wherein providing the Slave devices in the subgroup an opportunity to transmit comprises: sending, by the Master device to the Slave devices, a collision resolution poll indicating the search depth and the branch number for the subgroup.
Claim 11
Dependent Claim
55 words
The method of claim 8 wherein, upon receipt of the collision resolution poll by the Slave devices, each Slave device having its branch number equal to the branch number specified in the collision resolution poll and having transmitted at a search depth one less than the search depth specified in the collision resolution poll retransmits.
Claim 12
Dependent Claim
28 words
The method of claim 6 further comprising the step of, following incrementing the search depth, terminating collision resolution where the search depth exceeds a predetermined maximum search depth.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-21 | 2001-01-20 | 2001-07-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-21 | 2005-01-20 | 2005-07-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-21 | 2009-01-20 | 2009-07-22 | $7700.00 | Window Closed / Lapsed |