HK1092312B - Grant channel assignment - Google Patents

Description

Granting channel allocation

Claim priority under U.S. 35 clause 119

This patent application claims priority from provisional application No. 60/463,414 entitled "grant channel assignment" filed on 15/4/2003 and assigned to the assignee of the present application and is hereby incorporated by reference.

Technical Field

The disclosed embodiments of the present invention relate generally to telecommunications networks and, more particularly, to assigning grant channels to mobile stations in such networks.

Background

A High Data Rate (HDR) subscriber station or Mobile Station (MS), referred to herein as an access terminal, may be mobile or stationary and may communicate with one or more HDR Base Stations (BS), referred to herein as modem pool transceivers. An access terminal sends and receives data packets through one or more modem pool transceivers to and from an HDR base station controller, referred to herein as a modem pool controller. The modem pool transceivers and modem pool controllers are part of a network called an access network. An access network transports data packets between multiple access terminals. The access network may also be connected to other networks outside the access network, such as corporate intranets and the internet, and may transport data packets between each access terminal and such outside networks. An access terminal that has established an active traffic channel connection with one or more modem pool transceivers is called an active access terminal and is said to be in a traffic state. An access terminal that is in the process of establishing an active traffic channel connection with one or more modem pool transceivers is said to be in a connection setup state. An access terminal may be any data device that communicates through a wireless channel or through a wired channel, for example using fiber optic or coaxial cables. An access terminal may further be any of a number of types of devices including but not limited to PC card, compact flash, external or internal modem, or wireless or wireline phone. The communication link through which the access terminal sends signals to the modem pool transceiver is called a reverse link. The communication link through which a modem pool transceiver sends signals to an access terminal is called a forward link.

In different system configurations of HDR access networks, a Base Station (BS) may issue a Mobile Station (MS) -specific grant, such as a reverse enhanced supplemental channel (R-ESCH) grant, using a dedicated Grant Channel (GCH). According to these system configurations, the dedicated GCH may convey information of only a single MS. Thus, if more than one MS needs to be scheduled simultaneously in a particular time slot, more than one GCH must be used. The number of grant channels used is determined by the number of mobile stations that can be scheduled simultaneously in the same time slot, as well as by the presence of a common grant channel.

Thus, to ensure that the mobile stations are informed about the grant, each mobile station may monitor each dedicated channel in the grant channel. In that case, each scheduled mobile station can be informed about the grant as long as the number of scheduled mobile stations in a time slot does not exceed the number of grant channels. However, such monitoring of each dedicated grant channel requires each mobile station to monitor a significant number of parallel code channels and increases the complexity of the mobile station processing. To reduce the processing required in the mobile stations, a subset of the grant channels may be allocated to each mobile station for monitoring. However, requiring the mobile stations to monitor only a subset of the grant channels means that there may be times when not every scheduled mobile station can be notified about the grant. This expected loss of performance, including the failure of GCH notifications, is referred to herein as "GCH outage" (outage) and is due to inconsistencies between the subsets that are allocated.

From the above discussion, it should be apparent that a need exists for effectively informing each mobile station of a grant channel so that each mobile station monitors less than all available dedicated grant channels. The present invention satisfies this need.

Disclosure of Invention

Embodiments disclosed herein efficiently allocate grant channels to mobile stations such that each mobile station monitors less than all available dedicated grant channels. Assigning grant channels to mobile stations includes selection of grant channels to convey notifications to each scheduled mobile station.

In one aspect, a grant channel is scheduled to transmit a grant message to a plurality of scheduled mobile stations. In particular, scheduling grant channels includes dynamically allocating previously unassigned grant channels in a grant channel list monitored by a current mobile station to a current mobile station of the plurality of scheduled mobile stations. After the current mobile station is scheduled, if there are additional mobile stations to be processed among the plurality of scheduled mobile stations, the scheduling moves to a next mobile station among the plurality of scheduled mobile stations, and the allocation process is repeated. Further, if not every grant channel has been assigned to a mobile station, the order of a plurality of scheduled mobile stations is rearranged and the assignment and movement processes are repeated.

In another aspect, scheduling grant channels to mobile stations further includes statically assigning at least one grant channel to each mobile station for monitoring. In one embodiment, the static allocation includes sequentially allocating each of a first plurality of mobile stations to one of the grant channels until all available grant channels have been allocated, wherein the first plurality of mobile stations is a subset of a set that includes all mobile stations operating within the area of the CDMA communication network. The static allocation also includes sequentially allocating the remaining mobile stations to the first set of the same number of grant channels. In another embodiment, the static allocation includes randomly choosing a set of grant channels from among the monitored grant channels to allocate to each mobile station for monitoring.

In another aspect, a CDMA communication network having a base station and a plurality of mobile stations includes a base station configured with a controller configured to schedule a grant channel for transmission of grant information to a plurality of scheduled mobile stations. The controller includes a grant channel assignment module operative to assign a previously unassigned grant channel from a list of grant channels monitored by a current mobile station to a current mobile station of the plurality of scheduled mobile stations. The base station also includes a modulator configured to process and spread the grant message. The base station also includes a transmitter unit configured to condition the processed grant message, generate a forward link signal, and transmit the forward link signal over a grant channel.

Other features and advantages of the present invention will be apparent from the following description of exemplary embodiments, which illustrate, by way of example, the principles of the invention.

Drawings

Fig. 1 illustrates an exemplary configuration for assigning grant channels to mobile stations;

fig. 2A, 2B and 2C illustrate an exemplary "dynamic" process of selecting or allocating a grant channel for transmitting a grant message to a scheduled mobile station;

FIG. 3 outlines a greedy technique applied in the exemplary dynamic selection process described in FIGS. 2A, 2B, and 2C;

fig. 4 illustrates simulation results of exemplary grant channel allocation performance expressed in terms of relative reverse link efficiency, where the number of mobile stations scheduled per time slot is evenly distributed over {1, 2, … …, k };

fig. 5 illustrates simulation results representing exemplary grant channel allocation performance by relative reverse link efficiency, where the number of mobile stations allocated per time slot obeys the following probability distribution: p (0), P (1), … …, P (8) {0.00860689, 0.0458367, 0.172538, 0.303443, 0.269816, 0.138511, 0.0490392, 0.0104083, 0.00180144 };

FIG. 6 illustrates a simplified block diagram of a CDMA communication system, such as an HDR access network;

fig. 7 illustrates a simplified block diagram of a CDMA communication system, such as a 1xEV-DV access network.

Detailed Description

The detailed description set forth below in connection with the appended drawings is intended as a description of exemplary embodiments of the present invention and is not intended to represent the only embodiments in which the present invention may be practiced. The term "exemplary" used throughout this description means "serving as an example, instance, or illustration," and should not be construed as preferred or advantageous over other embodiments. The detailed description includes specific details for a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In some instances, well-known structures and devices are shown in block diagram form in order to avoid obscuring the concepts of the present invention. In these figures, like reference numerals refer to like structures.

As described above, when only a subset of grant channels are allocated to each mobile station for monitoring, there may be times when not every scheduled mobile station can be notified of a grant. This expected loss of performance due to inconsistencies between the subsets being allocated (i.e., "GCH line breaks") is undesirable. As described herein, it can be shown that the expected performance penalty due to "GCH outage" will not be significant if each mobile station is able to monitor two or more grant channels. Furthermore, the expected performance loss can be further reduced by effectively allocating grant channels to each mobile station for monitoring, and by effectively selecting grant channels (from the allocated grant channels) to transmit notifications to each scheduled mobile station.

In the following description, the allocation of grant channels to each mobile station to monitor for allocations is referred to as "static" allocation, since such allocations are typically only performed once during initialization or similar initialization of the mobile station. Selecting a grant channel from among statically allocated grant channels is referred to as "dynamic" allocation, as this selection may be repeated in each time slot, and a different grant channel may be selected.

Fig. 1 illustrates an exemplary configuration for assigning grant channels to mobile stations in a CDMA system. The exemplary configuration includes four dedicated grant channels GCH1, GCH2, GCH3, GCH 4; and seven mobile stations MS1, MS2, MS3, MS4, MS5, MS6, and MS 7. Each mobile station monitors exactly two grant channels to receive grant notifications. The grant notifications for GCH1 through GCH4 all come from the base station. In the illustrated configuration, the first mobile station MS1 monitors grant channels GCH2 and GCH 4; the mobile station MS2 monitors grant channels GCH3 and GCH 4; the mobile station MS3 monitors grant channels GCH3 and GCH 4; the mobile station MS4 monitors grant channels GCH1 and GCH 2; the mobile station MS5 monitors grant channels GCH2 and GCH 4; the mobile station MS6 monitors grant channels GCH1 and GCH 4; while the mobile station MS7 monitors the grant channels GCH1 and GCH 3. In fig. 1, the grant channels monitored by each mobile station are represented by a line from the mobile station to the monitored grant channel originating from the base station.

In the exemplary configuration of fig. 1, the base station is able to schedule mobile stations MS1, MS2, and MS5 within a particular time slot by sending a grant for mobile station MS1 on grant channel GCH4, a grant for mobile station MS2 on grant channel GCH3, and a grant for mobile station MS5 on grant channel GCH 2. The connecting lines corresponding to such a scheduling map are shown as dashed lines in fig. 1. Since the base station can allocate a grant channel to each of the three mobile stations, there is no GCH outage in this scheduling map. However, if the base station is also to schedule mobile station MS3 within the same time slot, then a GCH outage will occur because there is no mapping for the exemplary configuration that can allocate a grant channel for each of the four scheduling mobile stations MS1, MS2, MS3, and MS5 in this case. That is, in the configuration of fig. 1, only three grant channels GCH2, GCH3 and GCH4 are monitored among four mobile stations MS1, MS2, MS3 and MS 5. Thus, in the proposed scheduling mapping, GCH outage can occur because there is less than efficient allocation of grant channels to mobile stations.

Recognizing the above-described need for efficiently allocating grant channels to each mobile station for monitoring, and selecting grant channels to transmit notifications to each scheduling mobile station, this disclosure describes exemplary embodiments of such allocation and/or selection. In particular, the techniques for "dynamic" and "static" allocation are described in detail below. However, it should be understood that even "valid" assignments to grant channels can sometimes result in "GCH" outages due to system resource limitations.

Fig. 2A, 2B and 2C illustrate an exemplary "dynamic" process in which a grant channel is selected or allocated to convey a grant message to a scheduled mobile station. In the exemplary "dynamic" selection process, it is assumed that less than the total number of dedicated grant channels have been allocated to each mobile station for monitoring in the "static" allocation process. The assumptions made for the static allocation process are described in further detail below.

Let k be the total number of dedicated grant channels. This number k is also the maximum number of mobile stations that can be scheduled simultaneously. Typically, k is between 2 and 8. Also, assume 1 is the number of grant channels allocated to each mobile station to monitor.

In one embodiment, a group of r mobile stations is scheduled in each time slot (e.g., 5 millisecond period), where r may be different from one time slot to another. The size of the set of mobile stations, r, can be assumed to be evenly distributed over {1, 2, …, k }, i.e., p (r) ═ 1/k, r ═ 1, …, k, or obey the following probability distribution: p (r ═ 0), P (r ═ 1), …, P (r ═ 8) ═ 0.00860689, 0.0458367, 0.172538, 0.303443, 0.269816, 0.138511, 0.0490392, 0.0104083, 0.00180144 }. The latter probability distribution is based on a single reverse link system level simulation result obtained by assuming that there are ten fully buffered FTP users in the sector. In addition, a randomly selected set of grant channels { GCH₁，GCH₂，…，GCH₁Is assigned to each mobile station to monitor.

In various embodiments and system configurations, the allocation of grant channels to be monitored by the mobile station may be either actively controlled by the base station or may be hashed (hash), where the grant channels are allocated pseudo-randomly based on a predetermined technique.

As described above, when each mobile station monitors less than the total number of dedicated grant channels (i.e., 1< k), it is desirable for the base station to efficiently allocate grant channels to particular mobile stations per time slot. This "dynamic" assignment task may be performed by a search solution where the number of scheduled mobile stations (designated r') that can be successfully assigned to the grant channel is maximized.

In various embodiments, "dynamic" scoringThe configuration can adopt the check 1^rAn exhaustive search of possible allocations. The search may terminate early whenever an allocation is found that enables r' ═ r. For example, when 1-3 and k-r-8, the worst-case exhaustive search length is 3⁸＝6561。

Another way to perform an exhaustive search is to use a recursive approach. In this approach, the search is performed in a trial-and-error manner. In each attempt, the first available grant channel from the 1 monitored grant channel list is assigned to each mobile station. The assignment is performed sequentially to the r mobile stations in a list or ordering of mobile stations. When a mobile station cannot be assigned a grant channel because all its monitored grant channels have been previously assigned to other mobile stations by the technique, then the technique tracks back (i.e., backtracks the ordering of the mobile stations in reverse order) until a mobile station is found that has at least one monitored grant channel that has not yet been assigned. The assignment to that mobile station is switched to the next available monitored grant channel. The assignment process is then retried for the remaining mobile stations (i.e., the technique tracks the ordering of the mobile stations in the order of the original direction). This forward-backward search is continued until an allocation is found that enables r' to r, or until all possibilities are exhausted. Such recursive algorithms will typically be less than 1^rThe sub-operations are completed, but that number may still be considered too long for some practical implementations.

In other embodiments, "dynamic" allocation may take the form of a relatively short search (sometimes referred to as a "greedy" technique). In this short search, the first available grant channel from the list of 1 monitored grant channels is assigned to each mobile station. The assignment is performed sequentially to the r mobile stations in a list or ordering of mobile stations. Thus, the assignment will attempt to assign grant channels to the mobile stations 1x r times, in such a way that the list of mobile stations and/or the list of monitored grant channels for each mobile station is rotated (rotate), or rearranged, between the attempts. For the example of 1-3 and k-r-8, in the worst case there will be only 3 a8-24 allocations, which is 3 of the more worst case exhaustive search⁸6561 a much smaller number of times.

In the exemplary dynamic selection process illustrated in fig. 2A, 2B, and 2C, there are eight grant channels (k 8), GCH1 through GCH8, and each mobile station monitors three grant channels (1-3). Further, the base station schedules eight mobile stations (r ═ 8) in a specific time slot. There are ten mobile stations, MS1 through MS10, operating within the operating boundaries of the base stations.

Fig. 2A shows a "static" allocation of grant channels to be monitored by each mobile station. For example, mobile station MS1 is assigned to monitor grant channels GCH1, GCH2, and GCH3, while mobile station MS2 is assigned to monitor grant channels GCH4, GCH5, and GCH 6. The assignments for grant channels to monitor are also arranged in a table form for other mobile stations MS3 to MS 10.

Figure 2B shows a plurality of sequences of possible assignments to mobile stations that are scheduled in a particular time slot to be informed of a grant. For example, R0 is the first sequence, R1 is the second sequence, and so on. Thus, in the first possible sequence or iteration (iteration) for the exemplary time slot of fig. 2B, mobile stations MS2, MS3, MS4, MS6, MS7, MS8, MS9, and MS10 are initially scheduled, as shown in row R0 of fig. 2B. It should be noted that the initial assigned ranks of MS2, MS3, …, and MS10 are random default ranks selected for purposes of this example. Other initial allocation orderings may be used depending on system requirements or design performance. In this example, mobile stations MS1 and MS5 are not scheduled. The second possible allocation sequence for the mobile station and grant channel is shown in row R1 of fig. 2B, which includes the sequences MS3, MS4, MS6, MS7, MS8, MS9, MS10, and MS 2. Likewise, MS1 and MS5 are not scheduled.

FIG. 2C illustrates a "dynamic" allocation process using the greedy "technique described above. For example, the base station tries to assign a mobile station to each of the grant channels GCH1 through GCH8 by using the assignment of grant channels to mobile stations listed in fig. 2A and the list of mobile stations (R0) scheduled in a time slot shown in fig. 2B. The first allocation attempt using the list R0 of FIG. 2B is shown in the column labeled R0 of FIG. 2C.

According to the "greedy" technique, the first mobile station to be scheduled, MS2 (see fig. 2B, row R0), is assigned to the first grant channel that MS2 is monitoring. Since fig. 2A shows that MS2 is monitoring grant channels GCH4, GCH5, and GCH6, mobile station MS2 is assigned the first of these channels, grant channel GCH 4. The second mobile station MS3 to be scheduled monitors grant channels GCH1, GCH7, and GCH 8. Thus, the mobile station MS3 is assigned the grant channel GCH1 because GCH1 was not previously assigned. The third mobile station MS4 to be scheduled, monitors grant channels GCH2, GCH3, and GCH 4. Thus, the mobile station MS4 is allocated to the grant channel GCH 2. By allocating other mobile stations in a similar process, the allocation of a mobile station to a grant channel can produce the results shown in the column labeled R0 of fig. 2C. This represents the allocation of the mobile station to the grant channel by using the first sequence of mobile stations R0. Thus, the figure 2C result shows that mobile station MS3 is assigned grant channel GCH1, mobile station MS4 is assigned grant channel GCH2, mobile station MS7 is assigned grant channel GCH3, mobile station MS2 is assigned grant channel GCH4, mobile station MS10 is assigned grant channel GCH5, mobile station MS8 is assigned grant channel GCH6, and mobile station MS6 is assigned grant channel GCH 8. However, the result also indicates that the mobile station MS9 cannot be scheduled in this time slot because all available grant channels have been allocated, which can result in a "GCH outage".

Referring again to fig. 2B, the mobile stations scheduled in the R0 sequence are rotated one by one to generate the next allocation sequence R1. Row R1 of fig. 2B shows scheduled mobile station sequences such as MS3, MS4, MS6, MS7, MS8, MS9, MS10, and MS 2. Applying a "greedy" technique to this sequence, the first mobile station MS3 to be scheduled in R1 is assigned the first grant channel GCH1 that MS3 is monitoring (see fig. 2A). The assignment of the mobile station to the grant channel can result in the results shown in column R1 of fig. 2C by assigning other mobile stations through a similar process. Thus, the result shows that the mobile station MS3 is assigned grant channel GCH1, the mobile station MS4 is assigned grant channel GCH2, the mobile station MS7 is assigned grant channel GCH3, the mobile station MS10 is assigned grant channel GCH4, the mobile station MS2 is assigned grant channel GCH5, the mobile station MS8 is assigned grant channel GCH6, and the mobile station MS6 is assigned grant channel GCH 8. However, the result also indicates again that the mobile station MS9 cannot be scheduled in this time slot, which again would result in a "GCH outage".

The above sequence of rotations of scheduled mobile stations may be repeated until the number of scheduled mobile stations that can be successfully allocated to the grant channel (r ') is at a maximum, or until r ' equals the total number of scheduled mobile stations (r ' ═ r). When r' is r, there will be no more "GCH open".

The loss of reverse link efficiency due to GCH outage can be estimated as follows. Let r be the total number of mobile stations scheduled in a time slot. It is assumed that out of r mobile stations, only r' can be notified by using the grant channel. Then the remaining r-r' mobile stations are in a GCH outage state. The efficiency in that time slot can be calculated asThis efficiency value is conservative, as losses due to GCH disconnection can be mitigated by any or all of the following methods. For example, if there are mobile stations that cannot be notified due to a GCH outage, then other mobile stations with outstanding demand can still be scheduled in the same time slot. The r-r' mobile stations that cannot be notified due to GCH outage can be selected from low priority users (among scheduled users). R-r' mobile stations that cannot be notified due to GCH outage can still be scheduled through the common grant channel.

Referring again to fig. 2B, next consider a sequence of scheduled mobile stations that are rotated to generate the sequence shown in row R4. Row R4 of fig. 2B shows the sequence of scheduled mobile stations such as MS7, MS8, MS9, MS10, MS2, MS3, MS4, and MS 6. A "greedy" technique is applied to the sequence in which the first mobile station MS7 to be scheduled is assigned to the first grant channel GCH3 being monitored by MS 7. Assigning the mobile station to the grant channel may result as shown in the column labeled R4 in fig. 2C by assigning other mobile stations in a similar process. Thus, the results indicate that mobile station MS9 was assigned grant channel GCH1, mobile station MS4 was assigned grant channel GCH2, mobile station MS7 was assigned grant channel GCH3, mobile station MS10 was assigned grant channel GCH4, mobile station MS2 was assigned grant channel GCH5, mobile station MS8 was assigned grant channel GCH6, mobile station MS3 was assigned grant channel GCH7, and mobile station MS6 was assigned grant channel GCH 8. Thus, each of the eight scheduled mobile stations has been assigned to a grant channel, resulting in no "GCH outage," as shown in fig. 2C.

The greedy technique described in fig. 2A, 2B, and 2C as applied in an exemplary dynamic selection process is outlined in fig. 3. The technique involves ordering by multiple sequences of scheduled mobile stations within a time slot. In an embodiment, the first available (unassigned) grant channel in the list of grant channels monitored by the current mobile station is assigned to the current mobile station (see box 300). In another embodiment, any unallocated grant channels in the grant channel list are allocated to the current mobile station.

If it is determined that there are additional mobile stations in the sequence of scheduled mobile stations to process (i.e., "yes" output by logic block 302), then the process moves to the next mobile station in the sequence of scheduled mobile stations at logic block 304 and the process shown in logic block 300 is repeated. Once a grant channel is assigned, that grant channel is removed from the list of all available grant channels. Otherwise, if it is determined that there are no more mobile stations in the sequence of scheduled mobile stations to process ("no" output to logic block 302), then a determination is made at logic block 306 as to whether each grant channel has been assigned to a mobile station. A yes result of this determination would indicate that there is no GCH outage in the scheduling grant channel, and a no result would indicate that there is a GCH outage and a new assignment should be attempted. Thus, if a GCH outage is detected at logic block 306, the sequence of scheduled mobile stations and/or the list of monitored grant channels for each mobile station will be reordered at logic block 308. In one embodiment, the sequence of scheduled mobile stations and/or monitored grant channels is reordered in such a way that the mobile station order is rotated as shown in figure 2B. For example, in FIG. 2B, the sequence R1 is a rotational variation of the sequence R0. In another embodiment, the sequence of scheduled mobile stations and/or monitored grant channels is reordered in an arbitrary manner such that the new sequence is different from the previous sequence.

If a GCH outage is detected at logic block 306, the process described in logic blocks 300 and 304 is repeated after rearranging the sequence of the list of scheduled mobile stations and/or monitored grant channels. If the GCH outage continues until the sequence rearrangement has been exhausted and there are no more previously unassigned sequences, then the mobile station cannot be notified of a grant in this time slot. In this case, the base station may wait until the next slot to try again to schedule the mobile station affected by the GCH outage.

Fig. 4 and 5 illustrate simulation results of exemplary grant channel allocation performance, expressed in terms of relative reverse link efficiency for different numbers of grant channels (1) monitored by each mobile station. If a GCH outage never occurs, a relative reverse link efficiency of 1.0 can be achieved. Each figure comprises seven curves representing different total numbers of available grant channels (k). Fig. 4 illustrates the reverse link rate when it is assumed that the number of mobile stations scheduled per slot is uniformly distributed over {1, 2, … …, k }, i.e., p (r) ═ 1/k, r ═ 1, … …, k. Fig. 5 illustrates the following probability distribution assuming that the number of mobile stations scheduled per time slot obeys: reverse link efficiency for P (r ═ 0), P (r ═ 1), …, P (r ═ 8) {0.00860689, 0.0458367, 0.172538, 0.303443, 0.269816, 0.138511, 0.0490392, 0.0104083, 0.00180144 }.

Since the relative efficiency values shown in figures 4 and 5 are normalized for each curve, no efficiency value comparison should be made between the curves. That is, these curves do not provide insight into the performance differences between cases corresponding to different values of k. However, this curve does give insight into the performance difference between the cases of different 1 values for any given k. It should be appreciated that conservative assumptions are used in calculating the reverse link efficiency losses illustrated in fig. 4 and 5. Therefore, the results shown here should be interpreted as lower limits in terms of performance.

The simulations shown in fig. 4 and 5 indicate that the loss of efficiency is only around 3% to 5% (i.e., relative efficiency around 95% to 97%) in the case where each mobile station monitors two grant channels (i.e., 1-2). The efficiency loss is shown to be significant when each mobile station monitors at least three grant channels (i.e., 1 ≧ 3). Thus, the results show that by having each mobile station monitor two or three dedicated grant channels, reverse link performance can be expected to achieve the performance achieved when each mobile station monitors all grant channels. It should be noted that for randomly chosen assignments, a more suitable performance measure, in some cases, is the probability that the assignment will disconnect the GCH less than or equal to a given level, greater than some threshold.

Based on the results of the above grant channel assignments, the following assumptions will guarantee sufficient performance for the cdma2000 reverse link. It is assumed that the mobile station has the capability to monitor at least two dedicated grant channels simultaneously. It is also assumed that the base station has the capability to signal the GCH allocation parameters to the mobile station in a three-layer (L3) message such as an Enhanced Channel Assignment Message (ECAM) and a Universal Handoff Direction Message (UHDM). In a recommendation document by the standards set Association of 3GPP2, entitled "cdma 2000 reverse Link recommendation Rev.D", at 17.2.2003, a cdma2000 reverse link is described in the document C30-20030217-.

Simulation results illustrating the expected performance loss due to GCH disconnection are discussed above. However, these results are obtained by assuming that each mobile station has a randomly selected set of grant channels assigned to it (i.e., random "static" assignments). Various embodiments are described below that use a non-random set of grant channels. It can be shown that using a set of explicitly assigned grant channels for each mobile station provides better performance than using a random set. Furthermore, for a uniform probability distribution of the size of the set of scheduled mobile stations in each time slot (i.e., a uniform distribution over {1, 2, …, k }), it can be shown that the reverse link efficiency using the non-random set of grant channels is actually the best. That is, the techniques described below for non-randomly assigning sets of grant channels to mobile stations provide maximum reverse link efficiency.

Assuming that the total number (n) of mobile stations is 10 (i.e., n-10), the number (1) of grant channels allocated to each mobile station to monitor is 1 (i.e., 1-1), and the number of grant channels that can be simultaneously scheduled is 8 (i.e., k-8). The mobile station is designated from MS1 to MS10, while the grant channel is designated from GCH1 to GCH 8. Further, it is assumed that the size of the set of scheduled mobile stations in each time slot is subject to a uniform distribution. Then, for a practical optimal allocation that provides the maximum efficiency, the efficiency is not less than

Wherein

If x<0，If x is 0, and

p (r) is the probability distribution of the set size of mobile stations scheduled in one time slot.

In one exemplary embodiment of a non-random "static" distribution, a number of assumptions are made as described above, including the assumption that the size of the set of mobile stations scheduled in each time slot obeys a uniform distribution of p (r) 1/k, r1, …, k. In this exemplary embodiment, maximum reverse link efficiency can be achieved by allocating grant channels GCH1, GCH2, GCH3, GCH4, GCH5, GCH6, GCH7, GCH8, GCH1, and GCH2 to scheduled mobile stations MS1, MS2, MS3, MS4, MS5, MS6, MS7, MS8, MS9, and MS10, respectively.

To verify and prove that the maximum reverse link efficiency can be achieved by assigning grant channels to mobile stations as defined above, consider the following. For n 10 mobile stations, k 8 scheduled grant channels, and 1 assigned to the grant channel monitored by each mobile station, the 1 st grant channel (referred to as number 1) is assigned to mobile stations MS1 and MS9, and number 2 is assigned to mobile stations MS2 and MS 10. In addition, a grant channel number i, where i is 3,4, 5, 6, 7, 8 is assigned to the mobile station MSi.

The combination of r different mobile stations, by definition, would result in a GCH outage if it contained mobile stations with the same number. From a combination point of view, unordered combinations are considered here. And if the number of different numbers in the combination is k-m, the broken line of the combination is repeated m times, wherein m is less than or equal to k-1. The combination of r mobile stations is the set of mobile stations scheduled in one time slot.

The number of combinations, U, that result in a GCH disconnection is calculated below. This wire break occurs in three cases, where if x < 0,and if x is equal to 0, and,

in the first case, the mobile station MS1 and MS9 are in combination and the mobile station MS10 is not. The number of such different combinations isIn this case, 2 of r-2 is the number of mobile stations (i.e., MS1 and MS9) that must join all such combinations. The other r-2 mobile stations in this combination are extracted from n-3 mobile stations MS2, MS3, MS4, MS5, MS6, MS7, and MS 8.

In the second case, the mobile stations MS2 and MS10 do not have any additional restrictions in the combination. The number of such different combinations isIn this case 2 in r-2 refers to the mobile stations MS2 and MS10 that must be added to all such combinations. The other r-2 mobile stations in this combination are extracted from n-2 mobile stations MS1, MS3, MS4, MS5, MS6, MS7, MS8, and MS 9.

In the third case, the mobile stations MS1, MS9, and MS10 are in combination and MS2 is not. The number of such different combinations isIn this case, 3 of r-3 refers to the mobile stations MS1, MS9, and MS10 that must be added to all such combinations. The other r-3 mobile stations in this combination are extracted from n-4 mobile stations MS3, MS4, MS5, MS6, MS7, and MS 8.

The combination of the three cases considered above is different, so that,

then, the number of combinations U of the broken line repeated twice₂Calculated as follows:

thus, the formula of equation (4) indicates that each combination of twice repeated disconnections should contain mobile stations MS1, MS2, MS9, and MS10 and the other r-4 mobile stations in such combination are extracted from n-4 mobile stations MS3, MS4, MS5, MS6, MS7, and MS 8.

For the assignments considered above, the disconnection repeats more than two times the combination and is absent. Thus, expressions U and U₂Equations (3) and (4) of (1) provide the following pairs of U₁General expression of (1), wherein U₁Is the number of combinations that repeat the broken line once:

each time r are extracted from the total number of n mobile station combinations and are given as. If the combination is not broken, all r mobile stations in the channel combination can be notified by using the grant. If the combining repeats the disconnection once, then one mobile station in the combination cannot use the grant channel. If the combining repeats the disconnection twice, then two mobile stations in the combination cannot use the grant channel.

If all ofThe combinations have the same probability of occurrence, then are communicatedKnowing the average number of mobile stations as

WhereinIs the number of combinations without broken lines and b (0) ═ 0. Let r be a random variable subject to the distribution p (r).

The average number of mobile stations notified normalized with respect to r is:

a(0)＝0 a(1)＝1 (7)

and the efficiency c (n, k) is defined as

By using equations (4) to (7), equation (1) is obtained for allocating grant channels GCH1, GCH2, GCH3, GCH4, GCH5, GCH6, GCH7, GCH8, GCH1, GCH2 to mobile stations MS1, MS2, MS3, MS4, MS5, MS6, MS7, MS8, MS9, MS10, respectively.

For a uniform distribution p (r) 1/k, r1, … …, k, the above listed allocation of grant channels to mobile stations is shown to be substantially optimal, as for any such distribution of 8 out of ten numbers with different numbers, and 2 with additional different numbers drawn from those 8 numbers, c (n, k) is the same. For any allocation with less than 8 different numbers or with 8 different numbers but with the same two additional numbers, c (n, k) is smaller than c (n, k) calculated according to equation (8).

In one example, consider the case where n is 10, k is 8, and p (r) is 1/k, r is 1, … …, k. Then, according to equation (8), when the grant channels GCH1, GCH2, GCH3, GCH4, GCH5, GCH6, GCH7, GCH8, GCH1, GCH2 are optimally allocated to the mobile stations MS1, MS2, MS3, MS4, MS5, MS6, MS7, MS8, MS9, MS10, respectively, c (n, k) is 0.922. However, for the same case but with the allocation being a random selection, the efficiency is shown to be around 0.82 (see fig. 4).

In another example, consider the case where n is 10, k is 8, and the probability distribution is as follows: p (0) ═ 0.00860689, P (1) ═ 0.0458367, P (2) ═ 0.172538, P (3) ═ 0.303443, P (4) ═ 0.269816, P (5) ═ 0.138511, P (6) ═ 0.0490392, P (7) ═ 0.0104083, and P (8) ═ 0.00180144. Then when grant channels GCH1, GCH2, GCH3, GCH4, GCH5, GCH6, GCH7, GCH8, GCH1, GCH2 are optimally allocated to mobile stations MS1, MS2, MS3, MS4, MS5, MS6, MS7, MS8, MS9, MS10, respectively, c (n, k) is 0.937 according to equation (8). However, for the same case but with the assignment as a random selection, the efficiency is shown to be around 0.86 (see fig. 5).

Thus, it can be seen that the non-random assignment of grant channels to mobile stations provides higher reverse link efficiency than the random assignment.

In another exemplary embodiment of a non-random "static" allocation, some assumptions are made as follows. Assuming that the total number (n) of mobile stations is an even number of numbers, the number of grant channels (1) allocated to each mobile station to monitor is 1 (i.e., 1 is 1), and the number of grant channels (k) that can be simultaneously scheduled is k is n/2. The mobile stations are designated from MS1 to MSn, while the grant channel is designated from GCH1 to GCHk. Furthermore, it is assumed that the size of the set of scheduled mobile stations in each time slot is subject to a uniform distribution. Then, for a substantially optimal allocation that gives maximum efficiency, the efficiency is not less than

Wherein

If x<0，If x is 0

P (r) is the probability distribution of the set size of the set of mobile stations scheduled in one time slot.

In this exemplary embodiment, maximum reverse link efficiency can be achieved by allocating grant channels GCH1, GCH2, … …, GCH (n/2), GCH1, GCH2, … …, and GCH (n/2) to scheduled mobile stations MS1, MS2, … …, and MSn, respectively.

To verify and prove that maximum reverse link efficiency can be achieved by assigning grant channels to scheduled mobile stations as defined above, consider the following. For a given total number of even mobile stations n and a given number of grant channels k that can be scheduled simultaneously n/2, assume that U (n, k, r, m) represents the number of combinations with r different mobile stations and that GCH disconnection is repeated m times. Let S (n, k, r, m) denote the set of these U (n, k, r, m) combinations. In this proof, the definitions of combination, numbering, line breakage, and line breakage repeated m times remain the same as in the first embodiment described above.

For r <2m > 0 ≦ r,

U(n，k，r，m)＝0 (10)

for 2m ≦ r ≦ k

Equation (11) can be verified as follows. Each combination of S (n, k, r, m) has exactly m pairs of mobile stations, with the mobile stations in each pair having the same number. The number of such different m pairs is equal to. The m pairs are sometimes referred to as twin pairs (twins pairs). For each combination in S (n, k, r, m), there is a set of remaining pairs (i.e., pairs that are not among the m twin pairs). The number of remaining pairs is equal to (n/2) -m.

One of the remaining pairs is able to provide no more than one of its mobile stations to the combination. The combination can obtain exactly r-2m such mobile stations from the remaining pairs, which means that for a given twin pair and r-2m pairs in a given remaining pair, the remaining pair can provide 2^r-2mA different combination of mobile stations. For a given twin pair, the total number of different sets of r-2m remaining pairs isWhich is given in equation (11).

Each time taking r writes from the total number of combinations of n mobile stations. Thus, if allThe combinations have the same probability of occurrence, then the average number of mobile stations notified is

Equation (9) can be obtained after normalizing b (n, k, r) with respect to r and averaging r.

In one example, consider the case where n is 10, k is 5, and p (r) is 1/k, r is 1, … …, k. Then, when the grant channels GCH1, GCH2, … …, GCH (n/2), GCH1, GCH2, … …, and GCH (n/2) are optimally allocated to the scheduled mobile stations MS1, MS2, … …, and MSn, respectively, c (n, k) is 0.889 according to equation (9). However, for the same case but with the allocation being a random selection, the efficiency is shown to be around 0.83 (see fig. 4).

In another example with a uniform probability distribution (i.e., p (r) ═ 1/k, r ═ 1, … …, k), consider the case where [ n ═ 16, k ═ 8], [ n ═ 14, k ═ 7], [ n ═ 12, k ═ 6 ]. Again, according to equation (9), when the grant channels GCH1, GCH2, … …, GCH (n/2), GCH1, GCH2, … …, and GCH (n/2) are optimally allocated to the scheduled mobile stations MS1, MS2, … …, and MSn, respectively, c (n, k) is 0.883, c (n, k) is 0.885, and c (n, k) is 0.886. No efficiency figures are given for the same case but for randomly chosen allocations. However, the efficiency figures are expected to be less than the efficiencies given by the non-random case shown here.

Fig. 6 is a flow chart illustrating the non-random "static" assignment of sets of grant channels to mobile station monitoring described above. The allocation process outlined in fig. 6 assumes that n represents the total number of mobile stations and k represents the total number of grant channels that can be scheduled simultaneously. Thus, k must be at least as large as r, where r is equal to the number of mobile stations scheduled in one time slot.

The non-random "static" assignment process successively assigns a first set of k mobile stations of the entire n mobile stations to k grant channels, respectively, at box 600. The next (n-k) mobile stations are assigned to a first set of (n-k) grant channels, box 602. Thus, the first set of (n-k) grant channels will have at least two mobile stations assigned to them.

Fig. 7 is a simplified block diagram of a CDMA communication system 700, such as a 1xEV-DV access network. System 700 includes at least one base station 750 and one mobile station 710 capable of implementing various aspects of the invention. For particular communications, voice data, packet data, and/or messages may be exchanged between base station 750 and mobile station 710. Different types of messages may be transmitted, such as messages used to establish a communication session between a base station and a mobile station, and messages used to control data transmission (e.g., power control, data rate messages, acknowledgements, etc.).

With respect to the forward link aspect, at base station 750, voice and/or packet data (e.g., from a data source 776) and messages (e.g., from controller 764) are processed (e.g., formatted and encoded) by a Transmit (TX) data processor 774, further processed (e.g., masked (cover) and spread) by a Modulator (MOD)772, and conditioned (e.g., converted to analog signals, amplified, filtered, and quadrature modulated) by a transmitter unit (TMTR)770 to generate a forward link signal.

The messages processed by base station controller 764 may include grant messages carrying grants specific to the mobile station, such as R-ESCH grants. These messages may use a dedicated grant channel that is optimally allocated according to the techniques described above. The controller 764 schedules the mobile stations within a particular time slot by processing and assigning grant channels to each scheduled mobile station. The controller includes a memory in which one (memory) maintains a list and ordering, such as allocation and scheduling, of the mobile stations, grant channels, and slot configurations, as illustrated in fig. 2A, 2B, 2C. In one embodiment, the controller 764 includes a grant channel assignment module 780 that assigns a previously unassigned grant channel in the list of grant channels monitored by the current mobile station to the current mobile station of the plurality of scheduled mobile stations. The controller 764 also includes a reordering module 782 that is configured to reorder the order of the plurality of scheduled mobile stations and repeat the assignment process performed by the grant channel assignment module if not every grant channel has been assigned to a mobile station. The forward link signal then passes through duplexer 754 and is transmitted via antenna 752 to mobile station 710.

At mobile station 710, the forward link signal is received by antenna 732, through duplexer 730, and provided to a receiver unit 728. The receiver unit 728 conditions (e.g., down converts, filters, amplifies, quadrature demodulates, and digitizes) the received signal and provides samples. The samples are processed (e.g., despreaded, decovered, and pilot demodulated) by a demodulator 726 to provide symbols, and the symbols are further processed (e.g., decoded and checked) by a receive data processor 724 to recover the data and messages transmitted over the forward link. The recovered data is provided to a data sink and the recovered message is provided to controller 720.

In regard to the reverse link, at mobile station 710, voice and/or packet data (e.g., from a data source 712) and messages (e.g., from a controller 720) are provided to a Transmit (TX) data processor 714, which formats and codes the data and messages with one or more coding schemes to generate coded data. Each coding scheme includes any combination of Cyclic Redundancy Check (CRC), convolutional, Turbo, block, and other coding, or no coding at all. Typically, voice data, packet data, and messages are encoded using different schemes, and different types of messages may be encoded differently.

The encoded data is then provided to a Modulator (MOD)716 and further processed (e.g., masked, spread with short PN sequences, and scrambled with a long PN sequence assigned to the user terminal). The modulated data is then provided to a transmitter unit (TMTR)718 and conditioned (e.g., converted to one or more analog signals, amplified, filtered, and quadrature modulated) to generate a reverse link signal. The reverse link signal passes through duplexer (D)730 and is transmitted via antenna 732 to base station 750.

At base station 750, the reverse link signal is received by an antenna 752, through a duplexer 754, and provided to a receiver unit (RCVR) 756. The receiver unit 756 conditions (e.g., filters, amplifies, downconverts, and digitizes) the received signal and provides samples. A demodulator (DEMOD)758 receives and processes (e.g., despreads, demasks, and pilot demodulates) the samples to provide recovered symbols. Demodulator 758 may implement a RAKE receiver that processes multiple samples of the received signal and generates combined symbols. A Receive (RX) data processor 760 then decodes the symbols to recover the data and messages transmitted over the reverse link. The recovered voice/packet data is provided to a data sink 762 and the recovered message may be provided to a controller 764. The processing by demodulator 758 and RX data processor 760 is complementary to that performed by mobile station 710.

Those of skill in the art would understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by power, current, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

Those of skill would further appreciate that the logical functional blocks, modules, circuits, and techniques described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.

The various illustrative logical blocks, modules, and circuits described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor may be a microprocessor, but, in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a technique or method described in connection with the embodiments disclosed may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal.

The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein

Claims (14)

1. A base station in a CDMA communications network, the base station comprising:

a controller configured to schedule a grant channel to transmit a grant message to a plurality of scheduled mobile stations in an area of the CDMA communication network, the controller comprising a grant channel assignment module to:

allocating a previously unassigned grant channel from a list of grant channels monitored by a current mobile station to the current mobile station in the ordering of the plurality of scheduled mobile stations; and

repeating said allocating for a next mobile station in the sequence of scheduled mobile stations if there are additional mobile stations in the sequence of scheduled mobile stations to process;

a modulator configured to process the grant message, the processing including spreading; and

a transmitter unit configured to modulate the processed grant message, generate a forward link signal, and transmit the forward link signal over a grant channel.

2. The base station of claim 1, wherein each of the grant messages comprises a message specific to a mobile station.

3. The base station of claim 1, wherein the grant message comprises a reverse enhanced supplemental channel, R-ESCH, grant.

4. The base station of claim 1, wherein the controller comprises:

a reordering module configured to reorder the order of the plurality of scheduled mobile stations if not every grant channel has been assigned to a mobile station, and to repeat the assignment process performed by the grant channel assignment module if not every grant channel has been assigned to a mobile station.

5. The base station of claim 4, wherein the rearrangement module rearranges an order of the list of grant channels monitored by the current mobile station.

6. The base station of claim 5, wherein the reordering module reorders the list in such a way that mobile station order is rotated.

7. The base station of claim 1, wherein the previously unassigned grant channel includes a first available grant channel in a list of grant channels monitored by the current mobile station.

8. The base station of claim 1, wherein the plurality of scheduled mobile stations is a subset of a set that includes all mobile stations operating within the area.

9. A CDMA communications network, comprising:

a first plurality of mobile stations operating within said CDMA communications network; and

a base station, comprising:

a controller configured to schedule grant channels to transmit grant messages to a plurality of scheduled mobile stations within an area of the CDMA communication network, the controller including a grant channel assignment module to assign a previously unassigned channel in a grant channel list monitored by the current mobile station to the current mobile station in the ordering of the plurality of scheduled mobile stations; and if there are additional mobile stations in the sequence of scheduled mobile stations to process, repeating the allocating for a next mobile station in the sequence of scheduled mobile stations;

a modulator configured to process the grant message, the processing including spreading; and

a transmitter unit configured to modulate the processed grant message, generate a forward link signal, and transmit the forward link signal over a grant channel.

10. The communication network of claim 9, wherein the controller in the base station further comprises:

a reordering module configured to reorder the order of the plurality of scheduled mobile stations if not every grant channel has been assigned to a mobile station, and to repeat the assignment process performed by the grant channel assignment module if not every grant channel has been assigned to a mobile station.

11. The communication network of claim 10, wherein the rearrangement module rearranges an order of the list of grant channels monitored by the current mobile station.

12. The communication network of claim 11, wherein the reordering module reorders the list in such a way that mobile station order is rotated.

13. The communication network of claim 9, wherein the previously unassigned grant channel includes a first available grant channel in a list of grant channels monitored by the current mobile station.

14. The communication network of claim 9, wherein the plurality of scheduled mobile stations is a subset of a set that includes all mobile stations operating within the area.