Nearly collision-free channel access system and method

• US 7,729,321 B2
• Filed: 02/21/2007
• Issued: 06/01/2010
• Est. Priority Date: 02/21/2007
• Status: Expired due to Fees

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: ITT Manufacturing Enterprises, Inc. (ITT, Inc.)
• Inventors: Liu, Yu-Jih
• Primary Examiner(s): Juntima, Nittaya
• Assistant Examiner(s): WONG, XAVIER S
• Application Number:
  US11/677,313
• Publication Number:
  US 20080198815A1
• Time in Patent Office: 1,196 Days
• Field of Search: 370/321, 370/329, 370/336, 370/337, 370/343, 370/347, 370/431, 370/442, 370/445, 370/458, 370/461, 370/462
• US Class Current: 370/337
• CPC Class Codes: H04W 74/0816 with collision avoidance
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Techniques for controlling access to a communication channel for each of a plurality of nodes in a wireless ad hoc communication network. According to one embodiment, each node uses a predetermined rule, such as a hash function, to compute which of a plurality of time slots during a contention window it is to attempt transmissions. Each node in the network follows the same rule to access the channel and as a result no additional overhead transmissions are required between the nodes. In addition, contention among different nodes is reduced when a node needs to repeat an attempt to make a transmission. When a node has data to transmit on the channel, it determines a time slot in the contention window period during which to attempt the transmission using a computation that is based on a number identifier assigned to the node, the number of time slots in the contention window period and a transmission count value that represents the number of attempts the node has made to make the transmission. According to another embodiment, nodes are assigned to slot groups based on the time slot computation and the groups are assigned to particular slots during successive blocks in a round robin fashion so as to ensure fair access to the communication channel.

Claims

1. A method for controlling access of each of a plurality of nodes to a communication channel based on time slots such that the plurality of nodes contend for access during a contention window period comprised of K plurality of time slots, comprising:

each node determining which one of the K plurality of time slots the node is assigned using a computation that is based on a number identifier N assigned to the node among the plurality of nodes, the number K of time slots, and a transmission count value R representing a number of attempts the node has made to transmit the data, wherein each node determines which of the K plurality of time slots it is assigned to by computing a value of a hash function

2. The method of claim 1, wherein said determining is performed at a beginning of a sequence of K time slots, and after determining whether the communication channel is free.

3. The method of claim 1, and further comprising transmitting data during said one of the plurality of time slots, determining whether the transmission is successful and incrementing the transmission count value R when it is determined that the transmission was not successful and repeating said determining at a next sequence of K time slots.

4. The method of claim 1, and further comprising determining during which of the K time slots the node has access to the channel during each contention time period in a sequence of contention time periods during a block of time slots, each block comprising M*K time slots, where M is an integer, according to a group assignment sequence that changes from one block of time slots to the next block of time slots, wherein a plurality of slot groups are defined such that each slot group comprises those nodes which are assigned to the same time slot according to said computation.

5. A method for controlling access of each of a plurality of nodes to a communication channel based on time slots such that the plurality of nodes contend for access during a contention window period comprised of K plurality of time slots, comprising:

each node determining which one of the K plurality of time slots the node is assigned to using a computation that is based on a number identifier N assigned to the node among the plurality of nodes, the number K of time slots, and a transmission count value R representing a number of attempts the node has made to transmit the data;

determining during which of the K time slots the node has access to the channel during each contention time period in a sequence of contention time periods during a block of time slots, each block comprising M*K time slots, where M is an integer, according to a group assignment sequence that changes from one block of time slots to the next block of time slots, wherein a plurality of slot groups are defined such that each slot group comprises those nodes which are assigned to the same time slot according to said computation, wherein the group assignment sequence rotates one slot group from one block of time slots to the next block of time slots and repeats after K blocks of time slots such that within every block of (M*K) slots, all nodes follow the same rule to determine the slot for access the channel, but group assignments rotate from one block of (M*K) slots to the next block of (M*K) slots.

6. The method of claim 5, wherein determining comprises determining during which of the K time slots the node may access the channel according to the group assignment sequence in which:

i. during a first block of time slots;

nodes in a first slot group are assigned to a first time slot during the contention window periods, nodes in a second slot group are assigned to a second time slot during the contention window periods, and so on, and such that the nodes in the Kth slot group are assigned to the Kth slot during the contention window periods;

ii. during a second block of time slots;

nodes in the second slot group are assigned to the first time slot during the contention window periods, nodes in a third slot group are assigned to the second time slot during the contention window periods, and so on, and such that nodes in the last slot group are assigned to a next to last time slot during the contention window periods and nodes in the first slot group are assigned to the last time slot during the contention window periods;

iii. and so on, such that during a last block of time slots;

nodes in the last slot group are assigned to the first time slot during contention window periods, nodes in the first slot group are assigned to the second time slot during contention window periods, and so on, and such that nodes in a next to last slot group are assigned to the last time slot during contention window periods.

7. A method for controlling access of each of a plurality of nodes to a communication channel over a period of time that is divided into a sequence of successive blocks of time slots, each block comprising a sequence of contention time periods comprising K time slots, where K is an integer, the method comprising:

each node determining which one of K slot groups the node is assigned to using a computation based directly on (a) a number identifier N assigned to the node among the plurality of nodes, (b) the number K, and (c) a transmission count value R that represents how many attempts the node has made to transmit the data, wherein each node determining which of the K plurality of time slots comprises computing a value of a hash function

8. The method of claim 7, wherein determining during which of the K time slots the node is to access the channel comprises computing the time slot S_t=[(K−

R+1)−

b+s] modulo(K−

R+1), wherein b is a number for the particular block of time slots during which the node is seeking access to the channel, s is the slot group from 0 to K−

1 for the node.

9. The method of claim 7, and further comprising at the time slot for which a node is determined to access the channel, determining whether the channel is busy and if so waiting until the next contention window period.

10. The method of claim 7, and further comprising transmitting data during the time slot for which a node is determined to access the channel, determining whether the transmission is successful, and incrementing the transmission count value R by 1 and repeating said determining which one of K slot groups a node is assigned and said determining during which of the K time slots the node is to access the channel.

11. A method for controlling access of each of a plurality of nodes to a communication channel over a period of time that is divided into a sequence of successive blocks of time slots, each block comprising a sequence of contention time periods comprising K time slots, where K is an integer, the method comprising:

each node determining which one of K slot groups the node is assigned to using a computation based directly on (a) a number identifier N assigned to the node among the plurality of nodes, (b) the number K, and (c) a transmission count value R that represents how many attempts the node has made to transmit the data, such that nodes in each slot group access the channel at a corresponding one of the K time slots; and

determining during which of the K time slots the node is to access the channel during each contention time period in the sequence of contention time periods during a block of time slots, each block comprising M*K time slots, where M is an integer, according to a group assignment sequence that changes from one block of time slots to the next block of time slots, wherein a plurality of slot groups are defined such that each slot group comprises those nodes which are assigned to the same time slot, wherein the group assignment sequence rotates one slot group from one block of time slots to the next block of time slots and repeats after K blocks of time slots such that within every block of (M*K) slots, all nodes follow the same rule to determine the slot for access the channel, but group assignments rotate from one block of (M*K) slots to the next block of (M*K) slots.

12. The method of claim 11, wherein determining comprises determining during which of the K time slots the node is to access the channel according to the group assignment sequence such that:

i. during a first block of time slots nodes in a first slot group are assigned to a first time slot during the contention window periods, nodes in a second slot group are assigned to a second time slot during the contention window periods, and so on, and such that the nodes in the Kth slot group are assigned to the Kth slot during the contention window periods;

ii. during a second block of time slots;

nodes in the second slot group are assigned to the first time slot during the contention window periods, nodes in a third slot group are assigned to the second time slot during the contention window periods, and so on, and such that nodes in the last slot group are assigned to a next to last time slot during the contention window periods and nodes in the first slot group are assigned to the last time slot during the contention window periods;

iii. and so on, such that during a last block of time slots;

nodes in the last slot group are assigned to the first time slot during contention window periods, nodes in the first slot group are assigned to the second time slot during contention window periods, and so on, and such that nodes in a next to last slot group are assigned to the last time slot during contention window periods.

13. A wireless communication device for operation in a wireless ad hoc data network, comprising:

a radio transceiver;

a modem; and

a controller connected to the modem and radio transceiver, wherein the controller is configured to control access of the wireless communication device to a communication channel during a contention window period comprised of K plurality of time slots by determining which of the K plurality of time slots the wireless communication device is assigned based on a number identifier N assigned to the wireless communication device among a plurality of other wireless communication devices operating in the network, the number K of time slots, and a transmission count value R representing a number of attempts the wireless communication device has made to transmit the data, by computing a value of a hash function

14. The wireless communication device of claim 13, wherein the controller is configured to determine whether the transmission from the wireless communication device is successful, and to increment the transmission count value R when the transmission is determined not to be successful.

15. The wireless communication device of claim 13, wherein the controller is configured to determine the time slot for the wireless communication device using the same mathematical computation that is used by each of a plurality of other wireless communication devices operating in the network.

16. The wireless communication device of claim 13, wherein the controller is configured to determine during which of the K time slots the wireless communication device may access the channel during each contention time period in a sequence of contention time periods during a block of time slots, each block comprising M*K time slots, where M is an integer, according to a group assignment sequence that changes from one block of time slots to the next block of time slots, wherein a plurality of slot groups are defined such that each slot group comprises those wireless communication devices in the network which are assigned to the same time slot.

17. The wireless communication device of claim 16, wherein the controller is configured to determine during which of the K time slots the wireless communication device has access to access the channel based on the group assignment sequence that rotates one slot group from one block of time slots to the next block of time slots and repeats after K blocks of time slots such that within every block of (M*K) slots, the wireless communication device follows the same rule as other wireless communication devices seeking access to the channel in the network to determine the slot for access the channel, but group assignments rotate from one block of (M*K) slots to the next block of (M*K) slots.

18. The wireless communication device of claim 16, wherein the controller is configured to determine which of the K time slots the node may access the channel according to the group assignment sequence such that:

i. during a first block of time slots;

wireless communication devices in a first slot group are assigned to a first time slot during the contention window periods, wireless communication devices in a second slot group are assigned to a second time slot during the contention window periods, and so on, and such that the wireless communication devices in the Kth slot group are assigned to the Kth slot during the contention window periods;

ii. during a second block of time slots;

wireless communication devices in the second slot group are assigned to the first time slot during the contention window periods, wireless communication devices in a third slot group are assigned to the second time slot during the contention window periods, and so on, and such that wireless communication devices in the last slot group are assigned to a next to last time slot during the contention window periods and nodes in the first slot group are assigned to the last time slot during the contention window periods;

iii. and so on, such that during a last block of time slots;

wireless communication devices in the last slot group are assigned to the first time slot during contention window periods, wireless communication devices in the first slot group are assigned to the second time slot during contention window periods, and so on, and such that wireless communication devices in a next to last slot group are assigned to the last time slot during contention window periods.

19. A wireless communication device for operation in a wireless ad hoc data network, comprising:

a radio transceiver;

a modem; and

a controller connected to the modem and radio transceiver, wherein the controller is configured to control access of the wireless communication device to a communication channel over a period of time that is divided into a sequence of successive blocks of time slots, each block comprising a sequence of contention time periods comprising of K time slots, where K is an integer, the controller being configured to determine which one of K slot groups a wireless communication device is assigned to based on a number identifier N assigned to the wireless communication device among the plurality of wireless communication devices operating in the wireless ad hoc data network, the number K, and a transmission count value R that indicates how many attempts the wireless communication device has made to transmit the data, such that wireless communication devices in each slot group access the channel at a corresponding one of the K time slots, and configured to determine during which of the K time slots the wireless communication device is to access the channel during each contention time period in the sequence of contention time periods during a block of time slots, each block comprising M*K time slots, where M is an integer, according to group assignment sequence that changes from one block of time slots to the next block of time slots, wherein the controller is configured to determined which of the K time slots the wireless communication device may access the channel based on the group assignment sequence that rotates one slot group from one block of time slots to the next block of time slots and repeats after K blocks of time slots, where K is an integer, such that within every block of (M*K) slots, the wireless communication device follows the same rule as all other wireless communication devices seeking access to the channel in the network to determine the slot for access the channel, but group assignments rotate from one block of (M*K) slots to the next block of (M*K) slots.

20. The wireless communication device of claim 19, wherein the controller is configured to determine-which of the K time slots the wireless communication device is to access the channel according to the group assignment sequence in which during a first block of time slots such that:

wireless communication devices in a first slot group are assigned to a first time slot during the contention window periods, wireless communication devices in a second slot group are assigned to a second time slot during the contention window periods, and so on, and such that the wireless communication devices in the Kth slot group are assigned to the Kth slot during the contention window periods;

during a second block of time slots;

wireless communication devices in the second slot group are assigned to the first time slot during the contention window periods, wireless communication devices in a third slot group are assigned to the second time slot during the contention window periods, and so on, and such that wireless communication devices in the last slot group are assigned to a next to last time slot during the contention window periods and wireless communication devices in the first slot group are assigned to the last time slot during the contention window periods; and

so on, such that during a last block of time slots;

wireless communication devices in the last slot group are assigned to the first time slot during contention window periods, wireless communication devices in the first slot group are assigned to the second time slot during contention window periods, and so on, and such that wireless communication devices in a next to last slot group are assigned to the last time slot during contention window periods.