Method and apparatus for communication system access

Description of equivalent WO 9719525 A1

METHOD AND APPARATUS FOR COMMUNICATION SYSTEM ACCESS

Related Applications

The present application is a continuation-in-part of co- pending U.S. application serial nos. 08/495,385 filed June 28, 1995, and 08/522,649 filed September 1 , 1995, both commonly assigned together with this application to Motorola, Inc.

Field of the Invention

The present invention relates to communications and more particularly an imp and Terri ommunicating data in a wireless communications system.

Background

The last 10 years have seen a tremendous increase in the demand for wireless networks capable of handling data communications. Unlike voice services, such as the GSM (Global System for Mobiles) cellular service, in which circuit- switched communications are used because of the sensitivity of users to the timing of oral dialogue, greater efficiencies can be achieved in data communications through the use of packet-switched and hybrid communications. Thus, it is anticipated that a significantly increased throughput can be achieved for shorter traffic by using proposed services such as the GPRS (GSM Packet Radio Service) over traditional circuit-switched wireless technology.

However, with the increased demand for wireless services has also come a demand for faster throughput rates of data traffic, at least for some users. One proposed solution to this need is the use of "quality of service" (QoS) grades for data traffic. By designating a particular data message with a high QoS grade or priority, users who have the need for rapid end-to-end delivery of their data will have their data delivered ahead of Iower QoS data. On the other hand, users who do not want to pay the higher QoS rates and can tolerate longer end-to-end delays can designate their data traffic with a Iower QoS grade.

A key problem in implementing this type of service for wireless data communications is the delay in obtaining access to a wireless channel. This problem arises because there are only a limited number of channels (or in the case of TDMA (time division multiple access) systems like GSM, subchannels/time slot sets) available for any given base station service area. Any delay in access will mean a decrease in the time the subchannels are available for actual data transmissions. Further, as the system approaches peak loading, there may well be many more mobile stations (MSs, or more generally subscriber units) attempting to gain access than can be accommodated by the system.

In order to reduce access delay in other wireless systems a number of medium access control (MAC) protocols have been proposed, including both non-contention systems, and well-known contention systems like ALOHA, Slotted- ALOHA, reservation ALOHA, CSMA (Carrier-Sense Multiple Access), DSMA (Digital-Sense Multiple Access), PRMA (Packet Reservation Multiple Access) and QCRA (Queued Contiguous Reservation Aloha). Enhancements to such systems have also been proposed using control algorithms to modify access probabilities. Thus, e.g., pseudo-Bayesian control techniques have been suggested to modify slotted-ALOHA systems based on the number of access attempts per given time period. Using such a technique, a base station might broadcast a value p = β/v periodically, where β is a constant and v is an estimate of the current number of ready communication units (e.g., meaning those communication units with data to transmit at that time (e.g., a burst period)). A ready user transmits an access request with probability p during any available access burst period.

A problem with the standard prior art approaches is that any given access scheme is applied to all units equally. Even where some QoS scheme was used in assigning traffic channels, accessing the system may take significantly longer during higher loading, making for undesirable delays for the high priority traffic.

There remains therefore a need for an improved means for data communications in wireless systems that solves these and related problems.

Brief Description of the Drawings

FIG. 1 is a block diagram of a wireless communications system according to first and second embodiments of the invention;

FIG. 2 is a diagram illustrating messaging between different functional entities of the wireless communications system of FIG. 1 ;

FIG. 3 is a state diagram illustrating transition states for access of the subscriber unit in the wireless communications system of FIG. 1 ;

FIG. 4 is a table illustrating access control parameters for use according to the first embodiment of the invention;

FIG. 5 is a diagram illustrating an uplink multiframe communication channel structure for use according to the first embodiment of the invention;

FIG. 6 is a a diagram illustrating an GPRS access channel structure for use according to a second embodiment of the invention. Detailed Description of the Drawings

These problems and others are solved by the improved method and apparatus according to the invention. A presently preferred embodiment of the invention is a system for controlling access through the use of varying access probabilities for subscribers of varying priority. This would typically start with a serving base station determining access probabilities (e.g., p^i and pι₀ where there are two classes of subscribers) in response to known system parameters like the current rate of access attempts for each QoS class. Values representative of these access probabilities are then transmitted to the subscriber unit(s), for example by use of a system broadcast channel or control channels. These values are then used by each subscriber communication unit in determining when to access a communication resource, e.g., an uplink channel. In calculating these values, one may use, e.g., a temporal or a proportional priority distribution as more fully described below. As a result of this contention-based prioritization scheme, an expedited access is achieved by higher priority units, thus increasing the overall throughput.

Turning now to FIG. 1 , there is generally depicted a wireless communications system 100 having one or more subscriber units (i.e., mobile station (MS) 105) communicating via base station transceiver 11 1 of base station (BS) 110 and base station controller (BSC) 1 15. The subscriber unit may be of such diverse types as dedicated data units (e.g., personal digital assistants (PDAs)), radiotelephones (including those adapted for coupling with data terminals like portable computers), or wireless adapter devices (e.g., wireless modems adapted for coupling with computers, message pads, etc.), and the like. In any event, the subscriber unit includes a transceiver 107 and processor 106 appropriately programmed for wireless data communications according to a serving systems protocols. In the illustrated case a combined GPRS- GSM system is shown, although it will be recognized that the embodiments discussed herein are equally applicable to any other wireless communications system, including CDPD (cellular digital packet data), CDMA (code division multiple access), data systems like ARDIS or RAM, etc. Thus, the portion of the GSM system servicing voice/short messaging subscribers includes an MSC (mobile switching center) 125 connected to an HLR/AuC (home location register/authentication center) 130 and PSTN (public switched telephone network) 150. The GPRS portion includes a GSN (GPRS service node) 120 connected to a packet switched PDN (public data network). GSN 120 includes all information necessary for appropriate routing of data messages; it may alternatively be coupled to MSC 125 to allow access to higher layer user information stored at a common platform such as HLR 130. BSC 1 15 includes a channel controller 1 16 and scheduler 1 17, along with typical BSC circuitry. Alternatively, the controller can be co-located with the base station 1 10, or distributed elsewhere to a further infrastructure entity, depending on the system design employed. Further, the base station 1 10 should be understood as illustrative of, and thus meaning, any communication unit operable for serving plural other communication units, not just a central communication unit of a wireless service area or cell.

The operation of this system can be further understood by additional reference now to FIGS. 2 and 3. In FIG. 2, the control/traffic communications flow among the MS 210, BS subsystem 220 and GSN 230 is generally depicted. Both MS 210 and BS/BSC 220 include access controllers (212 and 222 respectively) and data transmission controllers (214 and 224 respectively), which GSN 230 includes an access manager 232. Current configuration parameters, including loading and service priority information derived from usage and access channel statistics, is communicated between the GSN 230 and BS/BSC access controller 222. Based on this information access control parameters are determined and broadcast in an access control message via the BS to MSs in the BS service area. These access parameters are preferably the current service priority level and access probability parameters. When the MS data transmission controller 214 receives a data transfer request, a transmission request message is transferred to the access controller 212 (i.e., moving from state 310 to monitor state 320 of FIG. 3). Based on the access control parameters and its data message priority, MS access controller 212 determines whether to send an access message/request (state 330) or backoff (state 325), and BS/BSC access controller 222 determines whether to allocate communications resource(s) in response to such a request. After a time-out period and no response, MS 210 again retries access (state 335). Upon allocation, access controller 222 notifies both MS 210 and data receiver controller 224 of the subchannel allocation, and the data transmitter controller 214 and data receiver controller 224 commence transfer of the data (state 340).

In order to facilitate transfer of higher priority data, a contention-based procedures is employed to limit MS access requests. A preferred contention-based procedure, illustrated with reference to FIGS. 4 through 6, uses two or more access probabilities (e.g., p_nj and pι₀, or p-j , p2, .. Pn if more than two probability levels) to control the access attempts by different priority classes of subscribers. Two particularly useful approaches for determining the access values are the following proportional and temporal priority distribution approaches. In a preferred proportional priority distribution, one starts with a pseudo-Bayesian algorithm modified to consider a three state feedback: idle, success or collision. While the best approach would be to establish the priority based access probability p for one of all current ready users n (such that p = 1/n), the value of n is often unknown. This can be approximated by, e.g., a known pseudo-Bayesian algorithm, derived by approximating the value of n using a Poisson distribution of backlogged users having mean of n. Since this only takes into account collision vs. no collision states, this can be further modified to take into account the effects of capture by taking into consideration the value (e.g., the constant β) at which the maximum channel throughput occurs, such that p = β/v. For slotted-ALOHA (S-ALOHA) in GPRS, this has been approximated as about 1.39; one skilled in the art will know how to determine this parameter for other protocols and system conditions.

Following calculation of p, the base station determines a separate probability for the different priority groups. A presently preferred approach is to have a smaller number of priority groups for access purposes than the number of defined QoS classes. This approach reduces the overhead in the repeatedly broadcast p vectors, when separate access values may not be necessary for efficient access. For example, in GPRS proposal has been made for five QoS classes, based on the delay time for end to end throughput. These classes are illustrated in the following table:

128 octet packets 1024 octet p ackets

QoS Class mean delay 95% delay mean delay 95% delay

Class 1 0.5 sec 0.7 sec 1.2 sec 1.4 sec

Class 2 0.5 sec 2.5 sec 3 sec 1.5 sec

Class 3 5 sec 25 sec 15 sec 75 sec

Class 4 50 sec 250 sec 75 sec 375 sec

Class 5 best effort best effort best effort best effort Because there is a significantly longer delay tolerance for classes 3-5 than for classes 1-2, one can advantageously use two access probabilities--a regular access probability for the group of communication units from classes 3 through 5, and an expedited access probability for the group of communication units from classes 1 and 2, having a higher priority than the other group.

A base station (or BSC, GSN or other controller, depending on the implementational assignment of control features) preferably determines an access probability vector (e.g., one or more words representative of the plural access probabilities or p-persistence values) using the calculated p and additional access parameters. In the preferred embodiment for proportional priority distribution the BS also maintains a running count of the proportion of expedited versus regular access messages received over a predetermined time period. The proportion of regular access requests to the total number of access requests (i.e., regular plus expedited) may be termed α, where 0 < α < 1. The proportion of expedited access requests is then 1 - α. Alternatively, depending on the implementation one may find it advantageous to keep the value of α within some defined min-max boundaries, for example α_mjn < α < αmax. where α_min = 0.1 and αmax = 0-9-

The base station then preferably calculates the group probability values as

Phi = (1 + α) x p, and Eq. 1

Plo = α x p. Eq. 2

This algorithm does not alter the overall probability that an access request will be transmitted during a given burst period, and therefore does not alter the effectiveness of the optimized pseudo-Bayesian technique. That such is the case can be shown by considering the following relationships, starting with the probability p = β/v that each ready user will transmit within an individual burst period, where the number of ready users is estimated by v and the optimal throughput is achieved when pv=β. When all ready users are categorized in two priority groups, high and low, such that v = v_ni + vι_0j then the proportion of lo priority ready users is α = vι₀/v. Eq. 3

The two probability values p^i and pι₀ are then determined as

Phi = (1 + α) x p = (1 + α) β/v and Eq. 4

Plo = α x p = αβ/v, Eq. 5

where p_ni represents the probability that each of the v_ni ready users transmits within an individual burst period, and pι₀ represents the probability that each of the vι₀ ready users transmits within an individual burst period. From the above it can be seen that the sum of all transmit probabilities remains constant β no matter what the proportional distribution of high and low priority ready users is; i.e., β = pv = (phi x v_hi) + (Pio x io). Eq. 6

Substituting the values for Phj and pι₀ above yields

β = pv = ((1 + α)pv_hi) + (αpvjo), Eq. 7

which reduces to v = (1 + α)v_hi + αv_lo,

= Vhi + (vio hi v) + (vι₀v_lo/v) . Eq. 8

This further reduces from:

vio = v " ^vhi = (vioVhi/ ) + ( joVio/ ), to V X V_l0 = Vι₀(V_hi + V_l0), tO

v = hj + v|₀. Eq. 9 Thus, it is shown that this algorithm does not alter the overall probability that an access request will be transmitted during a given burst period, and does not alter the effectiveness of the optimized pseudo-Bayesian technique. It therefore better insures that expedited access requests will be transmitted with a higher probability than regular access requests, and meets such preferred system design criterion as (1 ) increasing loads from low priority users without degrading performance of high priority users; (2) permitting equal priority messages to contend fairly (e.g., by a FIFO (first in first out) rule); and (3) keeping overhead and volume of control information to a minimum.

Again, while the above embodiment has been described in connection with a two group priority scheme, any number n of groups can be used depending on the design criterion for a given system. FIGS. 4 and 5 illustrate the use of n = 4 groups/ levels of access probability. The probability values pi , p2, ... Pn for each group are again determined by the appropriate infrastructure entity (e.g., the BS or BSC) in response to known system parameters like the current rate of access attempts for each group. Values representative of these access probabilities are then transmitted to the subscriber unit(s), for example by use of a system broadcast channel or control channels. These values could simply be the probability values, or could be a more convenient format for efficient communication such as the closest integer wn (an access window period) to the inverse of the pn value, with the access values appropriately formatted, e.g., as one or plural control words (i.e., an access control vector).

Each MS then determines whether to transmit during a current access period based on the received access control vector. Where the vector includes access window values such as in FIG. 4, the values are preferably applied by first selecting the value applicable to priority class of the subscriber or, if appropriate to the system, a queued packet or message. A random number or the like is then preferably generated and applied to the selected value to generate a delay value. The subscriber then counts this delay value number of allowed burst periods (i.e., data time slots available for access) before transmitting its access/reservation request; counting is suspended during periods when the MS is not allowed access. Thus, as illustrated in FIG. 5, a priority level 1 packet will have a maximum wait period ti (501 ) substantially shorter than periods t2 through t4 (502-504) for priority levels 2 through 4. However, the actual burst period 505 at which an access request is sent could be the same for data traffic of all priority levels (at least those greater than the minimum priority level), although with differing probabilities of occurrence. The use of a random/pseudorandom number or similar user differentiating value permits different outcomes for plural subscribers, so all do not attempt access at the same time. This reduces the collision potential, particularly when service is denied to a whole group for a given period (such as happens in the temporal priority approach below) and then made available again. Alternative uses of a differentiating user-generated value such as a random number will be apparent to a skilled artisan; e.g., instead of determining a window period, between 0 and 1 could be generated each allowed burst period, with an access attempt being permitted if the number is greater than the applicable probability value and otherwise inhibited.

A second embodiment may alternatively be used, in which a temporal priority distribution is employed. In one form, as illustrated by FIG. 6, separate expedited and regular periods are provided on, e.g., a random access channel in which to make access attempts. Assuming for illustration that there are two priority access groups, the BSC (or other appropriate infrastructure entity like a GSN) determines two estimates of the number of ready users, V i being the estimate of ready high priority users and vι₀ being the estimate of ready low priority users. Using a pseudo-Bayesian calculation, the access probabilities are Phi = β/v_ni and pι₀ = β/vj₀. Each access channel, such as channel 600, is then preferably apportioned into plural (two in this case) access periods, one group of bursts being for expedited access requests and the other being for both regular and expedited access requests. The expedited access period 601 is variable in length and high priority users (e.g., QoS class 1 and 2 subscribers or packets) contend equally using transmit probability p_nj. The regular access period 602 has a fixed length of Nr frames and regular priority users contend equally using transmit probability pι₀. The base station preferably keeps track of the current estimate of high priority ready users Vhi and regular ready users vι₀ using the pseudo-Bayesian algorithm described above. During the expedited access period 601 the base station broadcasts the value of pι₀ = 0 (indicating that no regular access requests should be transmitted) and p_nj = βΛ/ i- During the regular access period 602, the base station broadcasts the value of p_ni = pio = β/v. In other words, both expedited and regular access requests may be transmitted during this period 602 using the same transmit probability.

The transition from expedited to regular access periods preferably occurs as follows: when the base station determines that P i = 1 and the channel status is idle for at least one access burst period, then the regular contention period may begin and continue for some fixed duration (Nr frames). The base station knows to begin the regular access period when p_nj = ^βΛ/ i = 1 , because if any ready users remain with an expedited request the burst period status would not be idle (i.e. it would be a success or collision status). Therefore this algorithm provides a level of guarantee that there are no remaining expedited requests to be transmitted when the regular contention period begins, and that an expedited request should not wait longer than Nr frames for an expedited channel access period. The base station may, of course, alter the 1 3

frequency of the expedited access periods (i.e. the value of Nr), since it controls the broadcast values Phi and pι₀. An expedited access period occurs whenever pj₀ = 0, and a regular access period occurs whenever pι₀ > 0.

Alternately, a hybrid of both the temporal and proportional priority distribution approaches may be employed where there are more than two priority groups. Thus, in the case illustrated by FIGS. 4 and 5, a temporal distribution can be effected by setting the broadcast access probability of one or more of the Iower priority classes to 0. The remaining priority groups would apply the applicable access value to determine w.hen to attempt access. Alternately, rather than setting some values to 0 an inhibit message can be sent as part of the access control parameters message. These approaches are particularly advantageous in taking advantage of changing loading conditions, without forcing all classes of the lowest group to contend for a significantly shortened access resource. For example, as loading increases a best efforts service (BES, class 5 in GPRS) could be readily set to probability 0 without affecting the QoS delays for classes 1 - 4. As loading continues to increase, classes 4 to 2 could be progressively shed by setting their probability to 0 as needed to maintain access for the higher priority classes. Of the classes still being served at any time, these users would continue determining when to send an access burst using the proportional priority approach above. But, unlike the temporal priority approach above, when loading is only moderate so as to permit class 1 -4 but not class 5 service, there is no requirement for inhibiting all the low group users, i.e., those units that are a member of class 3 or 4, along with class 5 users. If desired, periodic higher priority access periods could be permitted even during moderate loading, set, e.g., to allow an access attempt for users of a given class within some predetermined period related to their QoS delay time. For example, even where there continue to be sufficient class 3 and higher users to otherwise result in class 4 users having a 0 access probability, every 50 seconds (i.e., the guaranteed mean delay period, and 1/5 of the 95% delay period for class 4 users) a period for class 4 access attempts is provided. Further refinements are also possible, such as by allowing the infrastructure entity to vary the access probabilities and inhibits for different channel/subchannel resources as opposed to all resources served, e.g., by a given BS. Likewise, a subscriber's class membership need not remain static, so the group for which a unit is currently a member can be determined by any convenient means such as a unit class, a user class, or even a user-selected priority class for a currently pending/queued data message. Thus, if the subscriber wants to send traffic and a comparison of the access value/priority service level for other subchannels shows that no subchannel is available at the specified priority grade of service/group, the subscriber may optionally chose to either automatically or via user input alter the data priority (and billing) level to a level high enough to permit access requests. Additionally, if other packets of higher priority are queued in the MS, the MS may chose to transmit the higher priority data packets ahead of a currently queued Iower priority packet.

One skilled in the art will appreciate that any one of numerous well-known access channel structures and post- contention prioritization schemes may be employed with the invention, each with varying merit depending on the specific design parameters of a given communication system. Thus none are presently preferred, even in the context of GPRS given the presently undecided nature of its standard, but a skilled artisan will be able to readily determine which to apply.

While the invention has been described in conjunction with specific embodiments thereof, it is evident that many alterations, modifications, and variations will be apparent to those skilled in the art in light of the foregoing description. For example, while processor 106, channel controller 1 16 and scheduler 1 17, and other circuits, are described in terms of specific logical/functional circuitry relationships, one skilled in the art will appreciate that such may be implemented in a variety of ways, such as appropriately configured and programmed processors, ASICs (application specific integrated circuits), and DSPs (digital signal processors). Further, the invention is not limited to the illustrated cellular systems, but has applicability to any communication system having an access protocol for communication resources (including wireline or fiber optic channels) and differentiated service. It should further be understood that for purposes of this application, a first device or component is responsive to or in communication with a second unit or component regardless of whether the first and second units are directly coupled or indirectly coupled, such as via intermediate units, including switches that operatively couple the units for only a segment of time, as long as a signal path can be found that directly or indirectly establishes a relationship between the first and second units. Thus, it should be understood that the invention is not limited by the foregoing description of preferred embodiments, but embraces all such alterations, modifications, and variations in accordance with the spirit and scope of the appended claims.

We claim: