System and method for hybrid contention/polling protocol collision resolution using a depth first search technique
First Claim
1. 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.
7 Assignments
0 Petitions
Accused Products
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.
66 Citations
10 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5)
-
-
6. 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. - View Dependent Claims (7, 8, 9, 10)
-
Specification