Granted Patent B2

US 8,358,636 · App. 11/729,791 · Granted Jan 22, 2013

Inventors: Yigal Bejerano (Springfiled, NJ); Yihao Lisa Zhang (New Providence, NJ)

Assignee: Alcatel Lucent

Abstract

Claims (166)

1. A method for scheduling the transmission of a multicast data packet in a wireless, local area network (WLAN) comprising:

scheduling using a unit-disk, interference graph, which defines predetermined dimensions of WLAN partitioned square subregions coinciding with an interference range of the graph, to provide constant approximations of an optimal time period for the transmission of a multicast data packet by,

minimizing the time needed to send the multicast data packet from an access point (AP) in the WLAN to each user over allocated time slots without interference and over a frequency used by another AP,

wherein the use of the unit-disk, interference graph provides an approximation guarantee of obtaining an approximation ratio of one of 12, 10, and 5 which indicates that, a total time period of a CFP (Contention Free Period) associated with all allocated time slots is no more than a factor of one of 12, 10, and 5, respectively, of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference over a frequency used by another AP;

and wherein the partitioned square subregions contain one or more labeled access points (APs).

2. The method as in claim 1 further comprising:

(a) partitioning the WLAN into square subregions, each subregion having a pre-determined dimension defined by a unit-disk, interference graph and containing one or more APs;

(b) for a first subregion, arbitrarily assigning each AP in the first subregion a position within an order and then sequentially allocating one or more time slots to each AP in the first subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the first subregion,

(c) for a next subregion, arbitrarily assigning each AP in the next subregion a position within an order and then sequentially allocating one or more time slots to each AP in the next subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the next subregion,

wherein the first time slot allocated to an AP in the next subregion occurs after the last time slot allocated in a preceding region, and

(d) repeating step (c) for each, next subregion,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 12 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

3. The method as in claim 2 further comprising:

(a) for each AP,

(i) computing a time period needed to transmit the multicast data packet to each user associated with the AP;

(ii) computing a number of needed time slots associated with the computed time period; and

(iii) rounding up the number of computed time slots to the nearest 2 J time slots; and

(b) taking all of the APs together,

(i) ordering the APs in decreasing order from an AP that needs the largest number of 2 J time slots to an AP that needs the lowest number of 2 J time slots; and

(ii) allocating available time slots to each AP in accordance with the order, wherein an available time slot is one that does not cause interference between the AP and its neighboring APs,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 10 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

4. The method as in claim 1 further comprising:

(a) for each AP, identifying a time slot that is associated with the lowest indexed position within a Contention Free Period (CFP) time frame that the AP may transmit during without interference from neighboring APs;

(b) taking all of the APs together,

(i) identifying an AP whose identified time slot is also associated with a lowest indexed position from among all of the so-identified time slots,

(ii) allocating a number of time slots to the so-identified AP sufficient to enable the AP to transmit the multicast data packet to each user associated with the AP; and

(c) repeating steps (a) and (b) until each AP has been allocated time slots,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

5. A method for scheduling the transmission of a multicast data packet in a wireless, local area network (WLAN) to minimize the time needed to send the multicast data packet from an access point (AP) in the WLAN to each user within transmission range of the AP without interference comprising:

scheduling using a unit-disk, interference graph, which defines predetermined dimensions of WLAN partitioned square subregions coinciding with an interference range of the graph, to provide constant approximations of an optimal time period for the transmission of a multicast data packet by,

(1) during each scheduling iteration, associating each user to an AP by,

(i) determining an AP that can serve the most users within a specified time period and over a frequency used by another AP;

(ii) associating the determined AP with the users the AP can serve within the time period;

(2) repeating steps (1)(i) and (ii) until each user is associated with an AP; and

(3) allocating one or more time slots to each determined AP using an association process;

wherein the use of the unit-disk, interference graph provides an approximation guarantee of obtaining an approximation ratio of one of 12, 10, and 15 which indicates that, a total time period of a CFP (Contention Free Period) associated with all allocated time slots is no more than a factor of one of 12, 10, and 5, respectively, of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference over a frequency used by another AP;

and wherein the partitioned square subregions contain one or more labeled access points (APs).

6. The method as in claim 5 wherein the association process comprises:

(a) partitioning the WLAN into square subregions, each subregion having a pre-determined dimension defined by a unit-disk, interference graph and containing one or more APs;

(b) for a first subregion, arbitrarily assigning each AP in the first subregion a position within an order and then sequentially allocating one or more time slots to each AP in the first subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the first subregion,

(c) for a next subregion, arbitrarily assigning each AP in the next subregion a position within an order and then sequentially allocating one or more time slots to each AP in the next subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the next subregion,

wherein the first time slot allocated to an AP in the next subregion occurs after the last time slot allocated in a preceding region, and

(d) repeating step (c) for each, next subregion, wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 12 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

7. The method as in claim 5 wherein the association process comprises:

(a) for each AP,

(i) computing a time period needed to transmit the multicast data packet to each user associated with the AP;

(ii) computing a number of needed time slots associated with the computed time period; and

(iii) rounding up the number of computed time slots to the nearest 2 J time slots; and

(b) taking all of the APs together,

(i) ordering the APs in decreasing order from an AP that needs the largest number of 2 J time slots to an AP that needs the lowest number of 2 J time slots; and

(ii) allocating available time slots to each AP in accordance with the order, wherein an available time slot is one that does not cause interference between the AP and its neighboring APs,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 10 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

8. The method as in claim 5 wherein the association process comprises:

(a) for each AP, identifying a time slot that is associated with the lowest indexed position within a Contention Free Period (CFP) time frame that the AP may transmit during without interference from neighboring APs;

(b) taking all of the APs together,

(i) identifying an AP whose identified time slot is also associated with a lowest indexed position from among all of the so-identified time slots,

(ii) allocating a number of time slots to the so-identified AP sufficient to enable the AP to transmit the multicast data packet to each user associated with the AP; and

(c) repeating steps (a) and (b) until each AP has been allocated time slots,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

9. A method for scheduling the transmission of a multicast data packet in a wireless, local area network (WLAN) to minimize the time needed to send the multicast data packet from an access point (AP) in the WLAN to each user within transmission range of the AP without interference comprising:

scheduling using a unit-disk, interference graph, which defines predetermined dimensions of WLAN partitioned square subregions coinciding with an interference range of the graph, to provide constant approximations of an optimal time period for the transmission of the multicast data packet by,

(1) selecting a time period;

(2) selecting an independent set of non-interfering APs;

(3) associating each AP within the selected set to those users each can serve within the selected time period and over a frequency used by other APs;

(4) selecting the next set of non-interfering APs and repeating steps (1) through (3);

(5) repeat step (4) until every user in the WLAN has been associated with at least one AP; and

(6) allocating one or more time slots to each AP using an association process;

wherein the use of the unit-disk, interference graph provides an approximation guarantee of obtaining an approximation ratio of one of 12, 10, and 5 which indicates that, a total time period of a CFP (Contention Free Period) associated with all allocated time slots is no more than a factor of one of 12, 10, and 5, respectively, of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference over a frequency used by another AP;

and wherein the partitioned square subregions contain one or more labeled access points (APs).

10. The method as in claim 9 wherein the selection of the independent set of APs comprises:

for a fixed time period,

(a) selecting an AP that can serve the most users within the fixed time period; and

(b) eliminating those neighboring APs of the selected AP that may interfere with the selected AP.

11. The method as in claim 9 wherein the selection of the next set of non-interfering APs comprises:

(a) selecting the next AP that can serve the next most users within the fixed time period;

(b) eliminate those neighboring APs of the selected next AP that may interfere with the selected AP.

12. The method of claim 10 wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5 of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

13. The method of claim 10 wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5Hn=O(log n) of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

14. The method as in claim 9 wherein the selection of the independent set comprises:

(a) partitioning the WLAN into square subregions, each subregion having a pre-determined dimension defined by a unit-disk, interference graph and containing one or more APs;

(b) identifying the subregion that serves the most users within a specified time period.

15. The method as in claim 9 wherein the selection of the next set of non-interfering APs further comprises identifying the next subregion that serves the next most users within the specified time period.

16. The method as in claim 14 wherein a total time period of a contention free period (CFP) associated with all allocated time slots was within a factor of 4 of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

17. The method as in claim 14 wherein a total time period of a contention free period (CFP) associated with all allocated time slots was within a factor of 4Hn=O(log n) of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

18. A device for scheduling the transmission of a multicast data packet in a wireless, local area network (WLAN), the device operable to:

schedule using a unit-disk, interference graph, which defines predetermined dimensions of WLAN partitioned square subregions coinciding with an interference range of the graph, to provide constant approximations of an optimal time period for a transmission of a multicast data packet by minimizing a time needed to send the multicast data packet from an access point (AP) in the WLAN to each user over allocated time slots without interference and over a frequency used by another AP,

wherein the use of the unit-disk, interference graph provides an approximation guarantee of obtaining an approximation ratio of one of 12, 10, and 5 which indicates that a total time period of a CFP (Contention Free Period) associated with all allocated time slots is no more than a factor of one of 12, 10, and 5, respectively, of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference;

and wherein the partitioned square subregions contain one or more labeled access points (APs).

19. The device as in claim 18 further operable to schedule the transmission of the multicast data packet by:

(a) partitioning the WLAN into square subregions, each subregion having a pre-determined dimension defined by a unit-disk, interference graph and containing one or more APs;

(b) for a first subregion, arbitrarily assigning each AP in the first subregion a position within an order and then sequentially allocating one or more time slots to each AP in the first subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the first subregion,

(c) for a next subregion, arbitrarily assigning each AP in the next subregion a position within an order and then sequentially allocating one or more time slots to each AP in the next subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the next subregion,

wherein the first time slot allocated to an AP in the next subregion occurs after the last time slot allocated in a preceding region, and

(d) repeating step (c) for each, next subregion,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 12 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

20. The device as in claim 18 further operable to schedule the transmission of the multicast data packet by:

(a) for each AP,

(i) computing a time period needed to transmit the multicast data packet to each user associated with the AP;

(ii) computing a number of needed time slots associated with the computed time period; and

(iii) rounding up the number of computed time slots to the nearest 2 J time slots; and

(b) taking all of the APs together,

(i) ordering the APs in decreasing order from an AP that needs the largest number of 2 J time slots to an AP that needs the lowest number of 2 J time slots; and

(ii) allocating available time slots to each AP in accordance with the order, wherein an available time slot is one that does not cause interference between the AP and its neighboring APs,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 10 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

21. The device as in claim 18 further operable to schedule the transmission of the multicast data packet by:

(a) for each AP, identifying a time slot that is associated with the lowest indexed position within a Contention Free Period (CFP) time frame that the AP may transmit during without interference from neighboring APs;

(b) taking all of the APs together,

(i) identifying an AP whose identified time slot is also associated with a lowest indexed position from among all of the so-identified time slots,

(ii) allocating a number of time slots to the so-identified AP sufficient to enable the AP to transmit the multicast data packet to each user associated with the AP; and

(c) repeating steps (a) and (b) until each AP has been allocated time slots,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

22. A device for scheduling the transmission of a multicast data packet in a wireless, local area network (WLAN) to minimize the time needed to send the multicast data packet from an access point (AP) in the WLAN to each user within transmission range of an AP without interference, the device operable to:

Schedule using a unit-disk, interference graph, which defines predetermined dimensions of WLAN partitioned square subregions coinciding with an interference range of the graph, to provide constant approximations of an optimal time period for a transmission of a multicast data packet by,

(1) during each scheduling iteration, associate each user to an AP by,

(i) determining an AP that can serve the most users within a specified time period and over a frequency used by another AP;

(ii) associating the determined AP with the users the AP can serve within the time period;

(2) repeating steps (1)(i) and (ii) until each user is associated with an AP; and

(3) allocating one or more time slots to each determined AP using an association process;

wherein the use of the unit-disk, interference graph provides an approximation guarantee of obtaining an approximation ratio of one of 12, 10, and 5 which indicates that, a total time period of a CFP (Contention Free Period) associated with all allocated time slots is no more than a factor of one of 12, 10, and 5, respectively, of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference over a frequency used by another AP;

and wherein the partitioned square subregions contain one or more labeled access points (APs).

23. The device as in claim 22 further operable to schedule the transmission of the multicast data packet by:

(a) partitioning the WLAN into square subregions each subregion having a pre-determined dimension defined by a unit-disk, interference graph and containing one or more APs;

(b) for a first subregion, arbitrarily assigning each AP in the first subregion a position within an order and then sequentially allocating one or more time slots to each AP in the first subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the first subregion,

(c) for a next subregion, arbitrarily assigning each AP in the next subregion a position within an order and then sequentially allocating one or more time slots to each AP in the next subregion in accordance with the order, the number of time slots allocated to each AP being sufficient to transmit the multicast data packet to every associated user of each AP within the next subregion,

wherein the first time slot allocated to an AP in the next subregion occurs after the last time slot allocated in a preceding region, and

(d) repeating step (c) for each, next subregion,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 12 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

24. The device as in claim 22 further operable to schedule the transmission of the multicast data packet by:

(a) for each AP,

(i) computing a time period needed to transmit the multicast data packet to each user associated with the AP;

(ii) computing a number of needed time slots associated with the computed time period; and

(iii) rounding up the number of computed time slots to the nearest 2 J time slots; and

(b) taking all of the APs together,

(i) ordering the APs in decreasing order from an AP that needs the largest number of 2 J time slots to an AP that needs the lowest number of 2 J time slots; and

(ii) allocating available time slots to each AP in accordance with the order, wherein an available time slot is one that does not cause interference between the AP and its neighboring APs,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 10 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

25. The device as in claim 22 further operable to schedule the transmission of the multicast data packet by:

(a) for each AP, identifying a time slot that is associated with the lowest indexed position within a Contention Free Period (CFP) time frame that the AP may transmit during without interference from neighboring APs;

(b) taking all of the APs together,

(i) identifying an AP whose identified time slot is also associated with a lowest indexed position from among all of the so-identified time slots,

(ii) allocating a number of time slots to the so-identified AP sufficient to enable the AP to transmit the multicast data packet to each user associated with the AP; and

(c) repeating steps (a) and (b) until each AP has been allocated time slots,

wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5 of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference.

26. A device for scheduling the transmission of a multicast data packet in a wireless, local area network (WLAN) to minimize the time needed to send the multicast data packet from an access point (AP) in the WLAN to each user within transmission range of an AP without interference, the device operable to:

schedule using a unit-disk, interference graph, which defines predetermined dimensions of WLAN partitioned square subregions coinciding with an interference range of the graph, to provide constant approximations of an optimal time period for a transmission of a multicast data packet by, selecting a time period;

(1) selecting an independent set of non-interfering APs;

(2) associating each AP within the selected set to those users each can serve within the selected time period and over a frequency used by other APs;

(3) selecting the next set of non-interfering APs and repeat steps (1) through (3);

(4) repeating step (4) until every user in the WLAN has been associated with at least one AP; and (5) allocating one or more time slots to each AP using an association process;

wherein the use of the unit-disk, interference graph provides an approximation guarantee of obtaining an approximation ratio of one of 12, 10, and 5 which indicates that, a total time period of a CFP (Contention Free Period) associated with all allocated time slots is no more than a factor of one of 12, 10, and 5, respectively, of an ideal, minimum time period required to transmit the multicast data packet to every user within the WLAN without interference over a frequency used by another AP;

and wherein the partitioned square subregions contain one or more labeled access points (APs).

27. The device as in claim 26 further operable to schedule the transmission of the multicast data packet by:

for a fixed time period,

(c) selecting an AP that can serve the most users within the fixed time period; and

(d) eliminating those neighboring APs of the selected AP that may interfere with the selected AP.

28. The device as in claim 26 further operable to schedule the transmission of the multicast data packet by:

(a) selecting the next AP that can serve the next most users within the fixed time period;

(b) eliminating those neighboring APs of the selected next AP that may interfere with the selected AP.

29. The device as in claim 27 wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5 of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

30. The device as in claim 27 wherein a total time period of a contention free period (CFP) associated with all allocated time slots is within a factor of 5Hn=O(log n) of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

31. The device as in claim 26 further operable to schedule the transmission of the multicast data packet by:

(c) partitioning the WLAN into square subregions, each subregion having a pre-determined dimension defined by a unit-disk, interference graph and containing one or more APs;

(d) identifying the subregion that serves the most users within a specified time period.

32. The device as in claim 26 further operable to schedule the transmission of the multicast data packet by identifying the next subregion that serves the next most users within the specified time period.

33. The device as in claim 31 wherein a total time period of a contention free period (CFP) associated with all allocated time slots was within a factor of 4 of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

34. The device as in claim 31 wherein a total time period of a contention free period (CFP) associated with all allocated time slots was within a factor of 4Hn=O(log n) of an ideal, minimum time period required to transmit the multicast data packet to every user within a WLAN without interference.

Assignments (16)

Continuity (1)