Wireless network resource allocation

This non-provisional application claims the benefit of U.S. provisional application Ser. No. 60/141,964 entitled “Network Assisted Dynamic Packet Assignment For Wireless Data Networks” filed on Jul. 1, 1999. The Applicants of the provisional application are Kapil K. Chawla, Justin Che-I Chuang, Xiaoxin Qiu, Nelson Ray Sollenberger (Attorney Docket No. 113685). The above provisional application is hereby incorporated by reference including all references cited therein.

1. Field of Invention

The invention relates to wireless network resource allocation.

2. Description of Related Art

Allocation of wireless network resources is becoming critical due to increased volume of wireless communication devices. Conventional resource allocation techniques consider only communication conditions between a terminal and a serving base station to determine whether to allocate or change allocation of wireless network resources. However, such resource allocation techniques may be inefficient with respect to spectrum usage, for example. Other methods have been proposed to more efficiently use wireless network resources to accommodate a greater number of terminals. Unfortunately, these methods require large amounts of processing power. Thus, new technology is needed to increase resource usage efficiency and reduce computational power required to allocate wireless network resources.

This invention provides an efficient wireless resource allocation technique where a communication link is allocated wireless network resources based on an optimum system gain based on link neighborhoods. System gain may be the difference between a maximum performance (e.g., throughput rate) for a selected link and the performance loss of non-selected links that may be affected by the selected link if the selected link is allocated resources. A non-selected link is affected if the selected link is within its link neighborhood. The selected link is allocated wireless network resources only if a largest system gain across all links is greater than a gain threshold, and if so, the selected link is allocated resources consistent with the largest system gain.

The performance loss experienced by any non-selected link is called damage to that link. Damage is determined in a pair-wise fashion based on a nominal performance. The nominal performance may be defined by a number of techniques. For example, the nominal performance may be the performance of a link if interference is experienced only from other links which are outside a link neighborhood of the link. This definition of link neighborhood may be dynamically adjusted to include all other links that may cause interference above a link threshold. For example, such a link neighborhood may be geographically defined, because the greater geographical separation, the less likely interference will occur. The nominal performance for a link may be a system specified parameter or defined as a maximum performance for that link if the only interference is experienced from a largest interfering source that is outside its link neighborhood.

The damage for a link i, caused by a link j, is the difference between the nominal performance of link i and the performance of the link i if interference is experienced from the link j. The above definition for damage is computationally efficient because computation for damage to the link i only requires consideration of the nominal performance of the link i, and the performance of the link i when receiving interference from the link j. In addition, the concept of link neighborhoods limits inter-base station communications and thus reduces base station interconnect costs required to support wireless communication resource allocation.

The invention is described in detail with reference to the following figures wherein like numerals reference like elements, and wherein:

FIG. 1 shows an exemplary diagram of a wireless communication system;

FIG. 2 shows channels of a time domain multiplexing scheme;

FIG. 3 shows an exemplary block diagram of a base station;

FIG. 4 shows a flowchart of an exemplary base station process for updating path gain information and link resource allocations; and

FIG. 5 shows a flowchart of an exemplary process for allocating wireless network resources in response to a request;

FIG. 6 shows a flowchart of an exemplary process for selecting a channel that corresponds to a maximum system gain; and

FIG. 7 shows a flowchart of an exemplary process for determining the maximum system gain.

FIG. 1 shows a wireless communication system that includes a network 102 and base stations 110 , 112 and 114 . The base stations 110 - 114 are coupled to the network 102 which provides inter-base station communication for allocating wireless network resources.

FIG. 1 shows terminals 134 - 136 communicating with the base stations 110 - 114 using links 104 - 108 , respectively. Associated with each of the links 104 - 108 is a link neighborhood 116 - 120 . FIG. 1 shows the link neighborhoods 116 - 120 as contours which may be defined based on parameters such as geographic areas, interference and/or noise thresholds, N largest interference/noise sources, etc. For example, FIG. 1 shows the link neighborhood 118 of link 106 including link 104 while excluding link 108 .

The terminal 134 may select one of the base stations 110 - 114 based on a path gain measurement. The terminal 134 may detect signal strength from control signals being transmitted by each of the base stations 110 - 114 and transmits the detect information or information derived from the detected information to the selected base station 110 - 114 . For example, the base station 112 may transmit a control signal that may include the base station identification, an identification of a channel on which the terminal 134 may transmit a request, etc. as is well known in the art.

When a request for a link 106 for the terminal 134 is received, the base station 112 may determine whether to allocate wireless communication resources to the link 106 by assessing a magnitude of a maximum system gain G of available system parameters such as channels, for example. The maximum system gain G is generated based on a difference between a performance (e.g., transmission throughput) T that is possible for the requested link 106 under conditions at the time of the request and a total performance loss B (damage) that will be sustained by all other links 104 , 108 that may be actively communicating at that time. Performance of a link 104 - 108 may be defined based on any communication parameters. For example, throughput, bandwidth, predetermined bit rate, error rate, etc. For purposes of illustration and discussion, throughput rate is used as an example in the following description.

A performance loss may be incurred because the link 106 if allocated resources may introduce more interfering noise affecting other links 104 , 108 . If the maximum gain G is greater than a gain threshold Gth, then the request for the link 106 may be granted and resources are allocated for the link 106 . The base station 112 may return a busy signal if the request is denied for a telephone call, or delayed if the request is for data transmission, for example. The gain threshold may be set based on desired system performance. For example, the gain threshold may be set to 0 so that the requested link 104 is not allocated resources unless there is a positive system gain. In this way, the decision whether to allocate wireless network resources to the requested link may be based on a system impact assessment instead of only the noise environment associated with the requested link 106 , for example. Consideration of the system impact permits more efficient allocation of wireless network resources so that a greater number of links 104 - 108 may be supported over a same quantity of system resources such as a same number of channels, for example.

In other words, the base station 112 estimates the system performance of a current system state, estimates possible system performances for possible system states different from the current system state by permuting selected system parameters such as channels through values other than the current value, and selects a system state that optimizes system performance. For example, if channel is selected as the permuting system parameter, then the channel assignment for the requesting user is permuted or assigned different ones of available channels and the system performance is estimated for each permutation. The channel that corresponds to the permutation that optimizes the system performance is selected.

In the following, channels are used as an example of a system parameter that is selected to optimize system performance. Other system parameters may also be used such as transmission power, a maximum resource holding time for data communication, a maximum permitted data transfer amount, etc.

A channel is a medium that carries communication signals between a terminal 134 - 136 such as a cellphone or other wireless devices and a base station 110 - 114 . For example, in time division multiplexing (TDM), a channel may be a time slot of a frequency carrier or in code division multiplexing (CDM), a channel may be a specific spread spectrum code.

Co-channel users are those users that are communicating via links that have been assigned the same channel. Thus, co-channel users interfere with each other. For example, FIG. 2 shows that under a TDM scheme, each carrier frequency supports multiple channels which may be grouped into fixed frames. A requested link may be assigned one of the channels for communication. Co-channel users are those users that are assigned the same slot of the same frequency carrier. Users assigned different channels may also interfere with each other. Thus, channels may have channel neighborhoods which include those channels that may cause interference. Such interference may be defined based on parameters characterizing an energy level of the interference, geographical separation of interfering sources or channel separation, for example. For simplicity in the following discussion, only co-channel users are considered, by way of example.

The system gain G for a channel s of a link j is defined by equation 1 as follows:

G j (s)=T j (s) - B j (s),   (1)

where T j b 55 is a performance of link j and B j is a cumulative performance damage. B j and T j will be discussed in turn below. The channel allocated for the requested link j (e.g., link 106 is: s * = { argmax s  ( G j  ( s ) ) if     max     ( G j  ( s ) ) > G  th     for     all     channels 0 otherwise

Thus the request for the link 106 is denied (e.g., busy tone for voice call) or delayed (in data communication, for example) if s*=0 and granted if s*>0.

The throughput T j may be determined by equation 2 below,

T j =R m j (1-BLER m j (SINR j ))   (2)

where R m j is a radio interface rate for the link j when assigned mode m j ; BLER j j is the block error rate of the link j when transmitting using the mode m j ; and SINR j is the signal-to-interference-plus-noise-ratio for the link j. The BLER is a link quality parameter which may be obtained directly from a decoding process or based on a bit error rate measure or the SINR. In addition, other link quality parameters such as frame error rate (FER) may be used.

Intuitively, the throughput for link j is the maximum performance, that is possible for the link j, reduced by an amount of transmission failures such as errors that may occur for link quality parameters such as the signal-to-interference-plus-noise ratio (SINR) that is/will be experienced. The maximum performance takes account of possible communication modes m j for the link j. For example, different transmission modes, such as QAM (Quadrature Amplitude Modulation), nPSK (n order phase shift keying), etc. combined with various error correction coding schemes or transmission power schemes, have different transmission performance advantages based on the transmission environment.

B j (s) is a cumulative performance damage that would be caused by a selected link j. Thus, B j (s) represents the decrease in performance (e.g., transmission throughput) of all non-selected links that would result if the selected link j is allocated channel s.

The cumulative performance damage B j (s) may be determined by adding together all the throughput decreases (damage), for example, that would result for each of the non-selected links 104 , 108 (e.g., currently active links if link j is a newly requested link) due to additional noise or interference that may be generated by a requested link j. The affected non-selected links 104 may be identified based on link neighborhoods 116 - 120 . For example, a non-selected link 104 is affected if link j is in the link neighborhood 116 of link 104 . As mentioned above, the link neighborhoods 116 - 120 may be defined based on parameters such as geographical areas, interference and/or noise thresholds, N largest interference/noise sources (e.g., other links), etc.

Thus, as shown in FIG. 1, the requested link 106 is in the link neighborhood of link 104 . Thus, the damage to the performance of the link 104 is included in B j (s). The link neighborhood 120 of the link 108 does not include the requested link 106 . Thus, the damage to the performance of the link 108 is not included in B j (s).

B j (s) is defined by equation 3 as follows:

B j (s)=ΣU i (j)I i (s)

i≠j   (3)

where U i (j) is the performance damage to the ith link, and I i (s) is a function that includes U i (j) for only non-selected links 104 , 108 whose link neighborhoods include link j. The summation is taken over all possible links 104 , 108 other than the requested link j.

As mentioned above, the size of the link neighborhoods 116 - 120 may be adjusted depending on the particular cost/performance levels desired. The link neighborhoods 116 - 120 may be selected based on a trade off between optimizing performance of the wireless communication system 100 and resources of the network 102 (i.e., costs) that are required to support that performance. In the ideal case, the link neighborhoods 116 - 120 may be defined to include all links 104 - 108 of the wireless communication system 100 . If such a definition is assumed, then path gain and other information from all the base stations 110 - 114 of the communication system 100 must be included to determine whether to allocate resources such as assign a channel to a requested link. For this case, all the base stations 110 - 114 are required to constantly communicate with every other base station in the wireless communication system 100 to achieve optimum system performance. The cost to support such a communication may be very high.

The cost may be reduced while controlling the impact on system performance by limiting the size of the link neighborhoods 116 - 120 based on magnitudes of interference that are expected to be received, for example. The link neighborhood of link r may be defined as follows:

1) sort all links of a wireless communication system in a descending order based on a magnitude of interference that may be expected from a link q on link r; then

2) select the first K r links q in the sorted order to be the link neighborhood for link r.

In this way, the size of a link neighborhood K r may be balanced against an efficiency of wireless network resource allocation by accounting for damage that may be sustained by non-selected links 104 - 108 within the link neighborhood of a limited size. Thus, cost and performance are optimized by balancing the magnitude of K r against the cost required to provide inter-base station communications over the network 102 .

Interference noise conditions experienced by each of the non-selected links 104 - 108 as well as other communication parameters such as channel assignments and transmission power within the link neighborhoods 116 - 120 may be collected by the base stations 110 - 114 and communicated among the base stations 110 - 114 on an ongoing basis. This inter-base communication may be performed via the network 102 . In this way, when requests are received, each of the base stations 110 - 114 may make timely independent assessment of the cumulative performance damage B j when a request is received at a base station 110 - 114 .

The performance damage U i (j) for link i that may be affected by a link j is given by equation 4 below: U i  ( j ) = { T i 0 - T i j if     the     requested     link     j     is     in     link     i '  s   neighborhood 0 otherwise ( 4 )

The performance damage is equal to 0 if the requested link j is outside the link neighborhood of the link i, and is equal to a difference between a nominal performance TP i o and estimated performance T i j if link j is in the link neighborhood of link i. T i j is the estimated performance of link i if the requested link j is allocated resources. The nominal performance T i o is the performance of link i (bits per second, for example) if the only interference is coming from a link 104 - 108 that is outside the link neighborhood of link i. The nominal performance T i o may also be specified as a system parameter. For example, the nominal performance for audio or video communication may be determined by the respective codec rates. The concept of a nominal performance provides a simple but effective objective standard to measure damage.

The throughput T i j may be determined by equation 5 below, assuming that the requested link is link j,

T i j =R m i j (1-BLER m j j (SINR i j )).   (5)

where R m i j , is the radio interface rate for the link i when assigned mode m i j (for a requested link j); and BLER m i j is the block error rate of link i when assigned mode m i j ; and SINRJ i j is the signal-to-interference-plus-noise-ratio for link i assuming link j is the only interfering source and is allocated resources.

Intuitively, the throughput rate T i j is the maximum performance for link i, if the requested link j is allocated resources, reduced by the amount of transmission failures such as errors that may occur for the link quality parameters such as the signal-to-interference-plus-noise ratio (SINR) that will be experienced. Thus, the damage U i (j) is the estimated reduction in performance to link i when the requested link j is allocated resources.

The above definition of damage is a pair-wise approximation of the actual damage that may be experienced by the link i because the damage U i (j) only accounts for the interference caused by the requested link j. While other links 104 - 108 may also be co-channel users of channel s and interfering with link i, the above damage definition only accounts for the damage caused by the requested link j. Thus, equation (3) reduces the information that would have been required if a total damage picture is required. In this way, a trade off is made between performance and the amount of damage information that is required which implicitly includes the network cost in the system performance optimization.

The signal-to-interference-plus-noise ratio SINR for a link 104 - 108 may be generated based on path gain values and channel assignment information obtained by the base stations 110 - 114 from the terminals 134 - 136 . For example, when the terminals 134 - 136 are either in standby mode or actively communicating, the terminals 134 - 136 measure path gain by determining a signal strength of control channels received from various base stations 110 - 114 . The terminals 134 - 136 return wirelessly (via a radio link, for example) to the base stations 110 - 114 the measured signal strengths and/or other parameters (measured or processed) so that the base stations 110 - 114 may collect respective path gains and other useful information such as channel assignment information. If G j is the path gain of link j, then the signal-to-interference-plus-noise ratio for link j (SINR j ) is provided by the equation (6) below: SINR j = P j  G j ∑ i ≠ j  P i  G ij + N j ( 6 )

where P j is the transmission power for link j, and N j is the thermal noise of link j, P i is transmission power for link i and G ij is a cross path gain of link ij which is an interference link between a transmitter of link i and a receiver of link j. Thus, each of the base stations 110 - 114 may collect path gain information measured by any of the terminals 134 - 136 and may determine the corresponding SINR for the respective links. This collected information together with other information such as channel assignments are shared among all the base stations 110 - 114 via the network 102 . In this way, wireless communication may be limited to communication of path gain. The network 102 may be a “wired” network (e.g., optic fiber, coax, twisted pair, etc.), thus, wireless system performance may be further improved.

While the base stations 110 - 114 may exchange measured information received from terminals 134 - 136 , a volume of such exchanged data may be reduced by performing appropriate processing in each of the base stations 110 - 114 . For example, if transmission power of the base stations 110 ∝ 114 are fixed and the path gains both G j and G ij are known, then the base stations 110 - 114 may generate performance damage U i (j) for as many of the terminals 134 - 136 as possible. When required, the performance damage value for a part or all active links for a base station 110 - 114 may be exchanged instead of the path gain information for example. In this way, the amount of data exchanged may be reduced and resource allocation efficiency may be increased.

When a request for allocation of wireless network resources for the link j (e.g., link 106 ) is received, the associated base station such as base station 112 , may request information such as path gains, SINRs, or performance damage from the terminal 134 and/or other base stations 110 - 114 that service the links i where link j is in the link i's neighborhood. The cumulative performance damage B j (s) is determined by calculating the damage for each of the links i if the requested link j is allocated wireless network resources for communication. Then the base station 112 determines system gains for each of the available channels via equation 1. If a maximum system gain G across all the channels is greater than a gain threshold, the base station 112 allocates resources to the requested link j, assigning channel s that corresponds to the maximum system gain G.

The above resource allocation technique may also be applied to verifying that the resource already allocated results in optimum system performance. The system 100 may re-assess the current resource allocations either on a continuing basis or at regular intervals. When performing verification, each of the currently active links are selected in turn. The selected link is permuted through system parameters such as the channel assignment and the system performance is evaluated as above by generating a performance for the selected link and a performance for all the non-selected links that accounts for damage caused by the new channel assignment to the selected link, for example. In this way, a system gain is generated for each of the available channels (which may be all possible channels or a selected portion of all the possible channels). A maximum system gain is compared with the current system gain. If the maximum system gain exceeds the current system gain by a gain threshold, then the selected link is assigned the channel that corresponds to the maximum system gain.

The above discussion assumes that the base stations 110 - 114 are immobile facilities and the terminals 134 - 136 are portable devices such as cell phones or PDAs. However, there is no requirement for such distinctions. Any device may perform the resource allocation functions performed by the base stations 110 - 114 above. For example, a terminal 134 - 136 may include sufficient processing power and connectivity to perform the resource allocation functions. Such a terminal 134 - 136 may be connected to the network 102 via a wired connection or a wireless connection.

FIG. 3 shows an exemplary block diagram of the base station 112 . The base station 112 includes a controller 202 , a memory 204 , a wireless interface 206 and a network interface 208 . The above components are coupled together via a signal bus 210 . While FIG. 3 shows the base station 112 organized in a bus architecture, other architectures are possible as is well known to one of ordinary skill in the art.

The base station 112 may, as a background process, receive path gain information from currently communicating terminals 134 - 136 . Path gain information may be received via the wireless interface 206 from the terminals 134 - 136 and/or from the other base stations 110 , 114 via the network interface 208 and forwarded to the controller 202 . The controller 202 may determine communication parameters such as transmission mode, the SINR, performance damage, throughput, etc. based on the equations discussed above.

If the link quality parameters such as SINR for a particular link 104 - 108 falls below a threshold such as SINR th for the SINR link quality parameter, for example, then the controller 202 servicing the link 104 - 108 sets the mode of that link 104 - 108 to a mode 0 , for example, which may indicate that transmission is to be stopped until the SINR for the link 104 - 108 exceeds the SINR th . If the SINR exceeds the SINR th, the controller 202 servicing the link 104 - 108 may readjust the transmission characteristics of the link 104 - 108 such as changing the transmission mode to further optimize the complete communication system 100 . For example, the transmission rate may be changed if the SINR has increased for the assigned channel, assigning a different channel or a different modulation scheme such as QAM, QPSK, etc. may improve transmission characteristics for the link 104 - 108 . Thus, the base stations 110 - 114 review the communication environment with each of the currently active links 104 - 108 to ensure that the most efficient transmission mode is applied.

FIG. 4 shows a flowchart of an exemplary background process of the base stations 110 - 114 (e.g., base station 112 ) for verifying that channel resource allocations for the currently active links 104 - 108 (e.g., link 106 ) corresponds to optimum system performance. In step 2000 , the controller 202 receives the path gain information from the terminal 134 being served by the base station 112 and/or from other base stations 110 , 114 . Then the controller 202 goes to step 2002 . In step 2002 , the controller 202 selects a next link for verification of optimum system performance and goes to step 2004 .

In step 2004 , the controller 202 processes system performance parameters to select a channel that corresponds to a maximum system gain and goes to step 2006 . In step 2006 , the controller 202 determines whether the maximum system gain that corresponds to the selected channel exceeds the gain threshold. If exceeded, the controller 202 goes to step 2012 ; otherwise the controller 202 goes to step 2008 .

In step 2008 , the controller 202 determines whether the selected link i protected. For example, if a link is used for a telephone call or has a guaranteed connection service, then the link is protected and the cannot be assigned a transmission mode 0 (stop transmission). If not protected, the controller 202 goes to step 2010 ; otherwise, the controller 202 goes to step 2014 . In step 2010 , the controller 202 assigns the transmission mode 0 to the selected link and goes to step 2014 . In step 2012 , the controller 202 assigns the selected channel to the link and goes to step 2014 .

In step 2014 , the controller 202 waits for a preset amount of time and goes to step 2016 . in step 2016 , the controller 202 determines whether the system 100 has been switched off. If switched off, the controller 202 goes to step 2018 and ends; otherwise, the controller 202 returns to step 2000 to repeat the process again.

The communication parameter data collected during the background process described above may be used to determine whether a request for a link 106 for a terminal 134 could be allocated resources. When a request is received, the controller 202 searches for communication parameters corresponding to the requested link 106 in the memory 204 . For example, the communication parameters may have already been collected or generated and stored in the memory 204 . If the communication parameters corresponding to the requested link are not found in the memory 204 , the controller 202 may send a query to the requesting terminal 134 or to other base stations 110 , 114 via the wireless interface 206 for the terminal 134 to report the path gain or other parameters so that the needed communication parameters may be determined for the requested link.

Once the communication parameters are obtained, the controller 202 processes system performance parameters to select a channel that corresponds to a maximum system gain. If the a maximum system gain exceeds the gain threshold, then the controller 202 allocates the selected channel to the requested link. Otherwise, the controller 202 either denies allocation of resources to the requested link or delays allocation until a more favorable condition is found.

FIG. 5 shows a flowchart of an exemplary process for responding to a request. In step 3000 , the controller 202 receives a request for a requested link and goes to step 3002 . In step 3002 , the controller 202 processes system performance parameters to select a channel that corresponds to a maximum system gain and goes to step 3004 . In step 3004 , the controller 202 determines whether the maximum system gain corresponding to the selected channel exceeds the gain threshold. If exceeded, the controller 202 goes to step 3008 ; otherwise the controller 202 goes to step 3006 . In step 3006 , the controller 202 denies or delays resource allocation to the requested link and goes to step 3010 and ends the process. In step 3008 , the controller 202 allocates resources for the selected channel to the requested link and goes to step 3010 to end the process.

FIG. 6 shows a flowchart for steps 2004 and 3002 in greater detail using SINR as a link quality parameter. In step 5000 , the controller 202 selects a next channel and goes to step 5002 . In step 5002 , the controller 202 determines the SINR for the selected channel based on path gain information either obtained from the terminal 134 - 136 associated with the selected link or from other base stations 110 - 114 . Then the controller 202 goes to step 5004 .

In step 5004 , the controller 202 determines whether the SINR is greater than or equal to the SIN th. If greater than or equal to the SINR th , the controller 202 goes to step 5006 ; otherwise, the controller 202 goes to step 5006 . In step 5006 , the controller 202 determines the maximum system gain and goes to step 5008 . In step 5008 , the controller 202 determines if there are more channels remain that may be selected. If more channels remain, the controller 202 returns to step 5000 ; otherwise the controller 202 goes to step 5010 and ends.

FIG. 7 shows a flow chart for step 5006 in greater detail. In step 4000 , the controller 202 sets the maximum system gain to an initial value such as 0 and goes to step 4004 . In step 4004 , the controller 202 determines the damage U i (j) for all currently active links 104 - 108 , the link neighborhoods which include the requested link for the selected channel, via equation 2-4 and goes to step 4006 . In step 4006 , the controller 202 determines the performance of the selected link and goes to step 4008 . In step 4008 , the controller 202 generates a system gain for the selected channel as a next system gain and goes to step 4010 .

In step 4010 , the controller 202 determines whether the next system gain is greater than the maximum system gain. If greater than maximum system gain, the controller 202 goes to step 4012 ; otherwise the controller 202 goes to step 4014 and returns to the calling step. In step 4012 , the controller 202 sets the next system gain as the maximum system gain and goes to step 4014 to return to the calling step.

While this invention has been described in conjunction with specific embodiments thereof, it is evident that many alternatives, modifications, and variations will be apparent to those skilled in the art. For example, while the allocation technique disclosed above determines a channel that corresponds a maximum system gain, a first channel that corresponds to a system gain that exceeds a system threshold may also be used. In this way, all possible permutations of the selected through possible channels would not be required, processing speed may be increased and processing power requirements reduced. Accordingly, preferred embodiments of the invention as set forth herein are intended to be illustrative not limiting. Various changes may be made without departing from the spirit and scope of the invention.