Global packet dynamic resource allocation for wireless networks

• US 6,295,285 B1
• Filed: 04/17/1997
• Issued: 09/25/2001
• Est. Priority Date: 04/17/1997
• Status: Expired due to Term

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Whitehead, James F.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Previl, Daniel
• Application Number:
  US08/842,755
• Time in Patent Office: 1,622 Days
• Field of Search: 370/329, 370/330, 370/331, 370/332, 370/333, 370/216, 370/218, 370/241, 370/242, 370/245, 370/349
• US Class Current: 370/329
• CPC Class Codes: H04W 16/02 Resource partitioning among network components, e.g. reuse partitioning
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 28/24 Negotiating SLA [Service Level Agreement]; Negotiating QoS [Quality of Service]
• CPC Class Codes: H04W 52/46 in multi hop networks, e.g. wireless relay networks
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02

Abstract

A reuse management method for a packet-switched wireless network having a plurality of links between a plurality of terminal devices and at least one base station. Each link is a wireless connection in a medium between a terminal device of the plurality of terminal devices and the one base station. A request for a link in the medium for transmitting a data packet is received. Permission to transmit the data packet over the requested link is granted based on compatibility of the requested link with other links in the medium. Granting permission to transmit the data packet includes assigning a slot for transmitting the data packet over the requested link. The packet-switched wireless network is also coupled to a plurality of connections. Each connection has an associated quality of service and the packet-switched wireless network has a virtual service rate. A data packet is received from a connection of the plurality of connections, and is placed in a quality-of-service (QoS) queue based on the quality of service associated with the connection and based on the virtual service rate of the packet-switched wireless network.

Claims

1. A method of reuse management for a medium comprising a plurality of wireless links in a packet switched wireless network, each wireless link comprising a connection between one of plural terminal devices and one of plural base stations, the method comprising the steps of:

receiving at least one request for a link in the medium for transmitting a data packet, including at least one request, which if granted, would result in medium reuse; and

granting the at least one request for transmission of a data packet over the requested link based on compatibility of the requested link with other links in the medium.

2. The method according to claim 1, wherein the step of granting permission to transmit the data packet includes the step of assigning a slot for transmitting the data packet over the requested link.

3. The method according to claim 2, further comprising the steps of:

transmitting the request at the terminal device;

receiving the request at the base station; and

assigning the slot for transmitting the data packet over the requested link based on a signal-to-interference ratio for successful transmission of the data packet over the requested link.

4. The method according to claim 3, further comprising the steps of:

sending the request received at the base station to a controller; and

assigning the slot for transmitting the data packet over the requested link at the controller.

5. The method according to claim 4, wherein transmitting the data packet includes the step of transmitting another request with the transmitted data packet, the request for transmitting another data packet over the link in the medium.

6. The method according to claim 4, wherein the slot is one of a time slot in a time-division duplex system and a frequency slot in a frequency-division duplex system.

7. The method according to claim 4, further comprising the steps of:

sending the slot assignment from the controller to the base station;

transmitting the slot assignment from the base station to the terminal device; and

transmitting the data packet from the terminal device to the base station in the assigned slot over the requested link.

8. The method according to claim 7, wherein the step of receiving the request for the link includes the step of receiving a plurality of requests, each request being for a link in the medium for transmitting a data packet, each requested link being a wireless connection between a terminal device of the plurality of terminal devices and a base station of the plurality of base stations, and

wherein the step of assigning a slot for transmitting the data packet includes the steps of:

determining, in order of receipt of the requests, whether a requested link is compatible with links previously assigned the slot;

assigning the slot to a requested link when the requested link is compatible with other links previously assigned the slot;

terminating determination of whether a requested link is compatible with links previously assigned the slot when a link is determined to be incompatible with links previously assigned the slot; and

sending the slot assignment for the requested links to the respective base stations.

9. The method according to claim 8, further comprising the steps of:

determining from all received requests whether a transmit power level associated with a respective requested link makes the respective requested link compatible with other requested links;

assigning the slot to a requested link when the link has a transmit power level making the requested link compatible with other requested links; and

sending the slot assignment for the requested links and the respective transmit power levels for each requested link to the respective base stations.

10. The method according to claim 7, wherein the step of receiving the request for the link includes the step of receiving a plurality of requests, each request being for a link in the medium for transmitting a data packet, each requested link being a wireless connection between a terminal device of the plurality of terminal devices and a base station of the plurality of base stations, and

wherein the step of assigning a slot for transmitting the data packet includes the steps of:

determining, in order of receipt of all requests, whether a requested link is compatible with other requested links previously assigned the slot;

assigning the slot to a requested link when the requested link is compatible with other links previously assigned the slot;

terminating determination of whether a requested link is compatible with other requested links when compatibility for all requested links has been determined; and

sending the slot assignment for the requested links to the respective base stations.

11. The method according to claim 10, further comprising the steps of:

determining from all received requests whether a transmit power level associated with a respective requested link makes the respective requested link compatible with other requested links;

assigning the slot to a requested link when the link has a transmit power level making the requested link compatible with other requested links; and

sending the slot assignment for the requested links and the respective transmit power levels for each requested link to the respective base stations.

12. The method according to claim 7, wherein the step of receiving the request for the link includes the step of receiving a plurality of requests, each request being for a link in the medium for transmitting a data packet, each requested link being a wireless connection between a terminal device of the plurality of terminal devices and a base station of the plurality of base stations, and

wherein the step of assigning a slot for transmitting the data packet includes the steps of,

determining from all received requests whether a respective requested link is compatible with other requested links;

assigning the slot to a maximum independent set of requested links that are mutually compatible; and

sending the slot assignment for the requested links to the respective base stations.

13. The method according to claim 12, further comprising the steps of:

determining from all received requests whether a transmit power level associated with a respective requested link makes the respective requested link compatible with other requested links;

assigning the slot to a requested link when the link has a transmit power level making the requested link compatible with other requested links; and

sending the slot assignment for the requested links and the respective transmit power levels for each requested link to the respective base stations.

14. The method according to claim 7, wherein the step of receiving the request for the link includes the step of receiving a plurality of requests, each request being for a link in the medium for transmitting a data packet, each requested link is a wireless connection between a terminal device of the plurality of terminal devices and a base station of the plurality of base stations, and

wherein the step of assigning a slot for transmitting the data packet includes the steps of:

determining, from all requests received during a time window, whether a requested link received during the time window is compatible with other requested links received during the time window;

assigning the slot to a requested link when the requested link is compatible with other links previously assigned the slot;

terminating determination of compatibility of the links when compatibility of all link requests received during the time window has been determined; and

sending the slot assignment for the requested links to the respective base stations.

15. The method according to claim 14, further comprising the steps of:

determining from all received requests whether a transmit power level associated with a respective requested link makes the respective requested link compatible with other requested links;

assigning the slot to a requested link when the link has a transmit power level making the requested link compatible with other requested links; and

sending the slot assignment for the requested links and the respective transmit power levels for each requested link to the respective base stations.

16. The method according to claim 7, wherein the step of receiving the request for the link includes the step of receiving a plurality of requests, each request for a link in the medium for transmitting a data packet, each requested link being a wireless connection between a terminal device of the plurality of terminal devices and a base station of the plurality of base stations, and

wherein the step of assigning a slot for transmitting the data packet includes the step of:

determining from all received requests whether a transmit power level associated with a respective requested link makes the respective requested link compatible with other requested links;

assigning the slot to a requested link when the link has a transmit power level making the requested link compatible with other requested links; and

sending the slot assignment for the requested links and the respective transmit power levels for each requested link to the respective base stations.

17. The method according to claim 4, further comprising the steps of:

measuring a received signal-level at the one base station;

determining a propagation path gain of the requested link between the terminal device and the one base station using the received signal-level measured at the base station; and

determining the compatibility of the requested link with other links in the medium based on the determined propagation path gain of the requested link.

18. The method according to claim 17, further comprising the step of measuring a received signal-level at the terminal device, and

wherein the step of determining a propagation path gain of the requested link is further based on the received signal-level measured at the terminal device.

19. The method according to claim 17, further comprising the steps of:

determining a transmit power level for the signal-to-interference ratio for successful transmission of the data packet over the requested link; and

sending a transmit power level message to the terminal device, the transmit power level message based on the determined transmit power level for successful transmission of the data packet over the requested link.

20. The method according to claim 17, wherein the step of measuring a received signal-level at the one base station includes the steps of:

sending a test permit message to the terminal device;

transmitting a test message from the terminal device; and

measuring a received signal-level of the transmitted test message at the one base station.

21. The method according to claim 17, further comprising the steps of:

forming a matrix having a plurality of first and second type elements, the first type element corresponding to a path gain G_ii of a link between a base station BS_i and a terminal device T_i, and the second type element corresponding to a path gain G_ij of a link between a base station BS_i and a terminal device T_j and to a path gain G_ji of a link between a base station BS_j and a terminal device T_i, where i≠

j;

setting a value of the first type elements to equal zero;

setting a value of the second type elements to be large; and

updating each respective element of the matrix based on the measured received signal-level at the one base station.

22. The method according to claim 2, wherein the step of granting permission is based on a path-gain matrix for the requested link.

23. The method according to claim 2, wherein the packet-switched wireless network is coupled to a plurality of stations, each station comprising part of a connection having an associated quality of service and the packet-switched wireless network having a virtual service rate, the method further comprising the steps of:

creating a data packet token to represent a data packet received at a station of the plurality of stations; and

placing the data packet token in a global wireless network queue based on the quality of service associated with the connection and based on the virtual service rate of the packet-switched wireless network.

24. The method according to claim 23, further comprising the steps of:

using the data packet token from the global wireless network queue to create a slot assignment for the switched wireless network at the virtual service rate of the packet-switched wireless network; and

controlling a time and a manner of transmission of the data packet in accordance with the slot assignment.

25. The method according to claim 24, further comprising the steps of:

determining a status of the global wireless network queue; and

placing the data packet token in the global wireless network queue further based on the status of the global wireless network queue.

26. The method according to claim 25, wherein the status of the global wireless network queue includes, an empty status, a not-full status and a full status, and wherein the data packet token is placed in the queue when the global wireless network queue status is one of the empty status and the not-full status.

27. The method according to claim 26, wherein each connection has a related input queue, and wherein the step of creating the data packet token includes the step of:

creating a plurality of data packet tokens for the respective input queues of the plurality of connections, and

placing the plurality of data packet tokens in the global wireless network queue based on the respective quality of services associated with the stations at which the data packets are received and based on the virtual service rate of the packet-switched wireless network when the global wireless network queue has the not-full status and when the quality of service for each connection is not achieved.

28. A method of providing access for a plurality of stations to a packet-switched wireless network, each station forming a component of a connection having an associated quality of service and the packet-switched wireless network having a virtual service rate, the method comprising the steps of:

creating a data packet token to represent a data packet received at a station of the plurality of stations; and

placing the data packet token in a global wireless network queue based on the quality of service associated with the connection and based on the virtual service rate of the packet-switched wireless network.

29. The method according to claim 28, further comprising the steps of:

using the data packet token from the global wireless network queue to create a slot assignment for the switched wireless network at the virtual service rate of the packet-switched wireless network; and

controlling a time and a manner of transmission of the data packet in accordance with the slot assignment.

30. The method according to claim 29, further comprising the steps of:

determining a status of the global wireless network queue; and

placing the data packet token in the global wireless network queue further based on the determined status of the global wireless network queue.

31. The method according to claim 30, wherein the status of the global wireless network queue includes, an empty status, a not-full status and a full status;

and

wherein the data packet token is placed in the queue when the global wireless network queue status is one of the empty status and the not-full status.

32. The method according to claim 31, wherein each station includes an input queue;

and

wherein the step of creating the data packet token includes the step of creating a plurality of data packet tokens for the respective input queues of the plurality of stations; and

placing the plurality of data packet tokens in the global wireless network queue based on the respective quality of service associated with the stations at which the data packets are received and based on the virtual service rate of the packet-switched wireless network when the global wireless network queue has the not-full status and when the quality of service for each connection is not achieved.