Method and system for data transmission in a wireless network

• US 8,149,737 B2
• Filed: 08/09/2005
• Issued: 04/03/2012
• Est. Priority Date: 08/09/2005
• Status: Active Grant

• Current Assignee: ARRIS Enterprises LLC (CommScope Holding Company, Inc.)
• Original Assignee: Motorola Solutions, Inc.
• Inventors: Ware, Christopher G., Phillips, Joseph E., Pandey, Aparna, Metke, Anthony R.
• Primary Examiner(s): Moe, Aung S
• Assistant Examiner(s): Alia, Curtis A
• Application Number:
  US11/199,783
• Publication Number:
  US 20070036089A1
• Time in Patent Office: 2,429 Days
• Field of Search: 370254-256, 370276-278, 370/280, 370/294, 370/310, 370/314, 370/326, 370/329, 370/336, 370/345, 370347-348, 370/431, 370/439, 370/442, 370/443, 370/445, 370/446, 370/458, 709/208, 709/223, 709/226, 709/230, 709/238, 709/240, 709/241, 709/242, 709/244, 709/252
• US Class Current: 370/256
• CPC Class Codes: H04W 72/541 using the level of interference
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: H04W 84/04 Large scale networks; Deep hierarchical networks

Abstract

A method and system for data transmission by computational devices in a wireless network (100) are disclosed. A computational device (102) organizes the wireless network in a hierarchical topology having at least one root node and updates a list of interferers and a list of descendents. Then, the computational device allocates a Contention Free Period (CFP) slot to each computational device in the wireless network based on at least one of the list of interferers and the list of descendents and transmits data during the allocated CFP slot.

Claims

1. A method for transmitting data in a wireless network, the wireless network comprising a plurality of computational devices, the method comprising:

organizing the plurality of computational devices in a hierarchical topology, the hierarchical topology having at least one root node;

updating, for each particular computational device in the plurality, (i) a list of interferers comprising other computational devices that are within a wireless communication range of the particular computational device but are not a parent computational device or a descendant computational device of the particular computational device in the hierarchical topology, and (ii) a list of descendent computational devices;

each particular computational device in the plurality allocating a Contention Free Period (CFP) slot to each computational device in the plurality that is a direct descendent of the particular computational device to support communications between the respective particular computational device and the computational device that is the direct descendant of the particular computational device based on the list of interferers and the list of descendents of the particular computational device; and

transmitting data from at least one of the particular computational devices in the plurality to one of the computational devices that is a direct descendant of the particular computational device during a corresponding allocated CFP slot.

2. The method according to claim 1, wherein, for each of the computational devices, updating the list of interferers Comprises removing descendents and ancestors from the list of interferers based on the list of descendents.

3. The method according to claim 1, wherein, for each of the computational devices, allocating the CFP slot comprises determining a CFP slot duration for each direct descendent of the computational device based on a local queue size of the direct descendent of the computational device and the list of interferers of the direct descendent of the computational device.

4. The method of claim 3, wherein determining a CFP slot duration comprises, for each descendent of the computational device, reporting to an immediate ancestor of the computational device the local queue sizes and the list of interferers of the descendent of the computational device.

5. The method of claim 1, wherein, for each of the computational devices, allocating the CFP slot comprises allocating time for each descendent to communicate with the descendant'"'"'s parent and allocating time for each descendent to communicate with each descendant'"'"'s descendent.

6. The method according to claim 1, wherein, for each of the Computational devices, allocating the CFP slot comprises allocating a dependent CFP slot to each direct descendent of the computational device based on an aggregate descendent queue size of the direct descendent of the computational device and the list of interferers of the direct descendent of the computational device, the dependent CFP slot being used for data transmission by descendents of the direct descendent to which the dependent CFP slot is allocated.

7. The method according to claim 1, wherein each of the computational devices allocating the CFP slot comprises prorating a duration of the CFP slot based upon an aggregate dependent queue size of each of the direct descendents of the computational device.

8. The method according to claim 1, further comprising each of the plurality of computational devices transmitting a CFP slot request to a parent node of the computational device from which the CFP slot request is transmitted.

9. The method according to claim 8, wherein the CFP slot request comprises at least one of:

a local queue size, an aggregate descendent queue size and an External Interferers List (EIL) for each of the plurality of computational devices.

10. The method according to claim 1, wherein each computational device that is a descendent of the root node updates a list of interferers of itself and any computational device that is a descendent of itself and a list of descendents of itself and any computational device that is a descendent of itself by each of the plurality of computational devices transmitting the list of interferers periodically to a parent node of the computational device from which the list of interferers is transmitted.

11. The method according to claim 1, further comprising each of the plurality of computational devices allocating an independent CFP slot to at least two independent computational devices for simultaneous transmission of data, the at least two independent computational devices having descendents, none of which interfere with each other.

12. The method according to claim 1, further comprising coordinating a beacon propagation from the at least one root node across the hierarchical topology for synchronizing allocation of the CFP slot to each of the plurality of computational devices.

13. The method of claim 1, wherein:

a particular communication device updates a descendent list of all descendents, including direct descendents, for each descendent of the particular communication device,

the particular communication device receives from each descendent of the particular communication device an interferer list of all interferers of the descendent of the particular communication device,

the interferer list and the descendent list are different, the descendent list is used to remove descendents of the particular communication device present in the interferes list, and

the CFP slots of each descendent of the particular communication device are all allocated within the CFP slot of an immediate ancestor of the descendent.

14. A system suitable for data transmission in an ad-hoc wireless network, the ad-hoc wireless network comprising a plurality of computational devices, each of the plurality of computational devices comprising:

an organization device configured to organize the plurality of computational devices in a hierarchical topology, the hierarchical topology having at least one root node;

an interference detect device configured to update a list of interferers for each of the plurality of computational devices, the list of interferes comprising other computational devices that are within a wireless communication range but are not a parent computational device or a descendant computational device in the hierarchical topology;

a CFP allocation device configured to allocate a Contention Free Period (CFP) slot to each of the plurality of computational devices that is a direct descendent of the computational device to support communications between the computational device and each computational device that is the direct descendant of the computational device based on the list of interferers and a list of descendents of the computational device; and

a transmission device configured to transmit data to one of the computational devices that is a direct descendant of the computational device during a corresponding allocated CFP slot.

15. The system according to claim 14, wherein each of the computational devices is further configured to periodically transmit the list of interferers for each of the plurality of computational devices to a parent node of each of the plurality of computational devices according to a set of predefined rules, each of the plurality of computational devices further configured to periodically update the list of descendents of the computational device in which the network maintenance module is located.

16. The system according to claim 14, wherein each of the computational devices is further configured to periodically transmit the list of interferers for each of the plurality of computational devices to a parent node of each of the plurality of computational devices according to a set of predefined rules, each of the plurality of computational devices further configured to transmit a CFP slot request to a parent node of the computational device in which the CFP request module is located.

17. The system according to claim 14, wherein each of the computational devices is further configured to periodically transmit the list of interferers for each of the plurality of computational devices to a parent node of each of the plurality of computational devices according to a set of predefined rules, each of the plurality of computational devices further configured to determine a CFP slot duration and a dependent CFP slot duration for the computational device in which the CFP determination module is located.

18. The system according to claim 14, wherein each of the computational devices is further configured to periodically transmit the list of interferers for each of the plurality of computational devices to a parent node of each of the plurality of computational devices according to a set of predefined rules, each of the plurality of computational devices further configured to prorate a duration of the CFP slot based upon an aggregate queue size for each of the descendents of the computational device in which the scheduler module is located.

19. The system according to claim 14, wherein each of the computational devices is further configured to periodically transmit the list of interferers for each of the plurality of computational devices to a parent node of each of the plurality of computational devices according to a set of predefined rules, each of the plurality of computational devices further configured to coordinate a beacon propagation from the root node down the hierarchical topology for synchronizing allocation of the CFP slot allocation to each of the plurality of computational devices, the beacon propagation being based on a predefined timing rule.

20. In an ad-hoc wireless network comprising a hierarchy of computational devices that includes a root computational device having all remaining computational devices in the hierarchy as its descendents, a particular remaining computational device of the remaining computational devices configured to:

maintain a list of descendents of the particular remaining computational device;

maintain a periodically-updated list of interferers for the particular remaining computational device, interferers being computational devices in the ad-hoc network which are able to communicate with a particular computational device in the ad-hoc network and are not an ancestor or descendent of the particular computational device, the list of interferers of the particular remaining computational device containing the interferers of the particular remaining computational device as well as the interferers of all computational devices that are descendents of the particular remaining computational device;

allocate a Contention Free Period (CFP) slot between each parent/child computational device set forth in the hierarchy for future communications between the respective parent/child computational devices based upon the list of interferers and the list of descendents of the particular remaining computational device;

a calculate an Aggregate Descendent Queue Size (ADQS) for the particular remaining computational device, the ADQS being an aggregate of an independent CFP slot, dependent CFP slots and a sum of local queue sizes for the descendents of the particular remaining computational device; and

provide a CFP request of the particular remaining computational device to a direct ancestor of the particular remaining computational device and a CFP slot allocation message containing information about each duration and timing offset of the CFP slot for each direct descendent to all direct descendents, the scheduler module and prorate the CFP slots if a duration of the CFP slot granted to the particular remaining computational device is shorter than the ADQS for the particular remaining computational device.

21. In an ad-hoc wireless network comprising a hierarchy of computational devices that includes a root computational device having all remaining computational devices in the hierarchy as its descendents, the root computational device configured to:

maintain a list of descendents of the root computational device;

an interference detect module that, if executed on the processor, maintains a periodically-updated list of interferers for the root computational device, interferers being computational devices in the ad-hoc network which are able to communicate with a particular computational device in the ad-hoc network and are not an ancestor or descendent of the particular computational device, the list of interferers of the root computational device also containing the interferers of the descendents of the root computational device;

allocate a Contention Free Period (CFP) slot between each parent/child computational device set forth in the hierarchy for future communications between the respective parent/child computational devices based upon the list of interferers and the list of descendents of the root computational device;

calculates an Aggregate Descendent Queue Size (ADQS) for the root computational device and schedules different branches of the hierarchy of computational devices whose computational devices do not interfere with each other to communicate at the same time such that no interferers communicate at the same time, the ADQS being an aggregate of an independent CFP Slot, dependent CFP slots and a sum of local queue sizes for the descendents of the root computational device; and

provide a CFP slot allocation message containing information about each duration and timing offset of the CFP slot for each direct descendent to all direct descendents of the root computational device, and prorate the CFP slots if a duration of all available time to grant to all CFP slots is shorter than the ADQS for the root computational device.