# Patent

## Title
Bandwidth allocation base station and method for allocating uplink bandwidth using SDMA

## Abstract

Embodiments of a base station and methods for allocating uplink bandwidth using SDMA are generally described herein. In some embodiments, uplink bandwidth request messages are received on a bandwidth request contention channel from one or more subscriber stations. The uplink bandwidth request messages are generated by the subscriber stations by modulating pilot subcarriers of a randomly selected disjoint pilot pattern with a randomly selected orthogonal sequence. The base station allocates uplink bandwidth to the subscriber stations when the uplink bandwidth request messages are successfully detected and decoded. The base station uses an SDMA technique to determine channel responses based on the orthogonal sequences to detect and decode the uplink bandwidth request messages.

## Background
TECHNICAL FIELD
Some embodiments pertain to bandwidth allocation in wireless access networks. Some embodiments pertain to uplink bandwidth requests and uplink bandwidth request ranging in broadband wireless access networks, such as WiMax networks.
BACKGROUND
In many conventional wireless access networks, bandwidth requests by subscriber stations consume a large amount of overhead and collisions of simultaneously submitted requests cause an increase in latency. Thus, what is needed are apparatus and methods that reduce the amount of overhead for bandwidth requests, and apparatus and methods that reduce the latency caused by collisions of simultaneously submitted bandwidth requests.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates a space-division multiple access (SDMA) wireless access network in accordance with some embodiments;
FIG. 2 illustrates uplink and downlink subframes of an uplink bandwidth request process in accordance with some embodiments;
FIG. 3 illustrates tiles of a bandwidth request contention channel in accordance with some embodiments;
FIG. 4 illustrates disjoint pilot patterns in accordance with some embodiments; and
FIG. 5 illustrates uplink and downlink subframes of an uplink bandwidth request process in accordance with some alternate embodiments.



DETAILED DESCRIPTION
The following description and the drawings sufficiently illustrate specific embodiments to enable those skilled in the art to practice them. Other embodiments may incorporate structural, logical, electrical, process, and other changes. Examples merely typify possible variations. Individual components and functions are optional unless explicitly required, and the sequence of operations may vary. Portions and features of some embodiments may be included in, or substituted for those of other embodiments. Embodiments set forth in the claims encompass all available equivalents of those claims.
FIG. 1 illustrates a SDMA wireless access network in accordance with some embodiments. Network 100 includes base station 102 and one or more subscriber stations (SS) 104. In multiple-access embodiments, base station 102 communicates with subscriber stations 104 by transmitting within downlink (DL) subframes 107 and subscriber stations 104 communicate with base station 102 by transmitting within uplink (UL) subframes 109. Base station 102 may include one or more maps in downlink subframes 107 to indicate the particular time and frequency resource that each subscriber station 104 may receive information within the current downlink subframe and the particular time and frequency resource that each subscriber station 104 may transmit information within a next uplink subframe.
Base station 102 may include, among other things, physical (PHY) layer circuitry 112 to communicate signals with subscriber stations 104, and signal processing circuitry (SPC) 114 to processes the signals received from subscriber stations 104 and to process signals for transmission to subscriber stations 104. In some embodiments, physical layer circuitry 112 may be configured to receive orthogonal sequences over a bandwidth request contention channel from subscriber stations 104. Signal processing circuitry 114 may detect and/or decode the received signals, as described in more detail below, to allocate uplink bandwidth to subscriber stations 104.
In some embodiments, base station 102 may receive, among other things, the orthogonal sequences from subscriber stations 104 through a plurality of antennas 103 and may use one or more SDMA techniques to help differentiate two or more of the orthogonal sequences that have collided. Accordingly, transmissions of colliding subscriber stations may be detected for allocation of uplink bandwidth. These embodiments are described in more detail below.
In some embodiments, base station 102 and subscriber stations 104 may communicate using a multicarrier communication technique that uses orthogonal frequency division multiplexed (OFDM) communication signals. The OFDM signals may comprise a plurality of orthogonal subcarriers. In some of these multicarrier embodiments, base station 102 may be part of a broadband wireless access (BWA) network communication station, such as a Worldwide Interoperability for Microwave Access (WiMax) communication station, although the scope of the invention is not limited in this respect. Subscriber stations 104 may be BWA network communication stations, such as WiMax subscriber stations, although the scope of the invention is not limited in this respect. In some embodiments, base station 102 and subscriber stations 104 may communicate using a multiple access technique, such as orthogonal frequency division multiple access (OFDMA). Subscriber stations may be almost any portable wireless communication device, such as a personal digital assistant (PDA), a laptop or portable computer with wireless communication capability, a web tablet, a wireless telephone, a wireless headset, a pager, an instant messaging device, a digital camera, an access point, a television, a medical device (e.g., a heart rate monitor, a blood pressure monitor, etc.), or other device that may receive and/or transmit information wirelessly.
In some embodiments, base station 102 and subscriber stations 104 may communicate in accordance with specific communication standards, such as the Institute of Electrical and Electronics Engineers (IEEE) standards including the IEEE 802.16-2004 and the IEEE 802.16(e) standards for wireless metropolitan area networks (WMANs) including variations and evolutions thereof, although the scope of the invention is not limited in this respect as they may also be suitable to operate in accordance with other techniques and standards. In some embodiments, base station 102 and subscriber stations 104 may operate in accordance with the provisions of the IEEE 802.16(m) task group. For more information with respect to the IEEE 802.16 standards and task groups, please refer to “IEEE Standards for Information Technology—Telecommunications and Information Exchange between Systems”—Local and Metropolitan Area Networks—Specific Requirements—Part 16: “Air Interface for Fixed Broadband Wireless Access Systems,” May 2005 and related amendments/versions. In some embodiments, base station 102 and subscriber stations 104 may communicate in accordance with the 3GPP LTE standards.
Antennas 103 and 105 may comprise one or more directional or omnidirectional antennas, including, for example, dipole antennas, monopole antennas, patch antennas, loop antennas, microstrip antennas or other types of antennas suitable for transmission of RF signals. In some embodiments, instead of two or more antennas, a single antenna with multiple apertures may be used. In these embodiments, each aperture may be considered a separate antenna. In some SDMA and multi-user multiple-input, multiple-output (MIMO) embodiments, antennas 103 may be effectively separated to take advantage of spatial diversity and the different channel characteristics that may result between each of antennas 103 and each antenna 105. Although subscriber stations 104 are illustrated with only a single antenna 105, subscriber stations 104 may include more than one antenna.
FIG. 2 illustrates uplink and downlink subframes of an uplink bandwidth request process in accordance with some embodiments. Uplink (UL) subframes 202, 206 and 210 may correspond to uplink subframes 109 (FIG. 1), and downlink (DL) subframes 204 and 208 may correspond to downlink subframes 107 (FIG. 1).
In these embodiments, base station 102 (FIG. 1) may receive orthogonal codes from subscriber stations 104 (FIG. 1) in uplink subframe 202 and may broadcast the detected orthogonal codes in downlink subframe 204 to indicate when a detected subscriber station may transmit a request for uplink bandwidth in uplink subframe 206. Base station 102 (FIG. 1) may provide bandwidth allocations to subscriber stations in downlink subframe 208, and subscriber stations 104 (FIG. 1) may transmit uplink data during a portion of uplink subframe 210 as indicated by base station 102 (FIG. 1) in downlink subframe 208. As described in more detail below, base station 102 (FIG. 1) uses SDMA techniques to detect signals received by colliding subscriber stations in uplink subframe 202. Base station 102 (FIG. 1) may also use SDMA techniques to decode uplink bandwidth request messages concurrently received in uplink subframe 206.
FIG. 3 illustrates tiles of a bandwidth request contention channel in accordance with some embodiments. In these embodiments, subscriber stations 104 (FIG. 1) may transmit orthogonal sequences in two or more tiles 302 during uplink subframe 202 (FIG. 2). Each of tiles 302 may comprise a time-frequency block of the bandwidth request contention channel. The two or more tiles utilized by a particular subscriber station may comprise different sets of frequency subcarriers as shown. Base station 102 (FIG. 1) may detect one or more of subscriber stations 104 (FIG. 1) by applying each of a plurality of the orthogonal sequences to the received orthogonal sequences. In these embodiments, base station 102 (FIG. 1) receives the orthogonal sequences from subscriber stations 104 (FIG. 1) through antennas 103 (FIG. 1) and uses an SDMA technique to help differentiate two or more of the orthogonal sequences that may have collided. In these embodiments, subscriber stations 104 (FIG. 1) may transmit their orthogonal sequences in two or more frequency orthogonal tiles 302 over bandwidth request contention channel during uplink subframe 202 (FIG. 2).
As illustrated in FIG. 3, the orthogonal sequence transmitted in each of orthogonal tiles 302 is transmitted by a subscriber station on different frequency subcarriers. In the example of FIG. 3, the first three bits of the orthogonal sequence may be transmitted on one subcarrier, the next three bits may be transmitted on another subcarrier, etc. Although tiles 302 are illustrated for transmission of only twelve bits, the orthogonal sequences generally include many more bits.
FIG. 4 illustrates disjoint pilot patterns in accordance with some embodiments. In some embodiments, base station 102 (FIG. 1) may broadcast a schedule in downlink subframe 204 (FIG. 2) which includes the detected orthogonal codes and an assignment of one of a plurality disjoint pilot patterns 400 to each detected subscriber station 104 (FIG. 1). Each disjoint pilot pattern 400 may be used for subsequent transmission by a detected subscriber station 104 (FIG. 1) of an uplink bandwidth request message in uplink subframe 206 (FIG. 2). Disjoint pilot patterns 400 may comprise orthogonal (i.e., non-overlapping) pilot subcarriers 402 and non-orthogonal (i.e., overlapping) data subcarriers 404. Thus, each pilot subcarrier 402 of disjoint pilot pattern 400A may have a null subcarrier 406 in a corresponding location of disjoint pilot pattern 400B, and each pilot subcarrier 402 of disjoint pilot pattern 400B may have a null subcarrier 406 in a corresponding location of disjoint pilot pattern 400A. Accordingly, orthogonal sequences transmitted on pilot subcarriers 402 of one of disjoint pilot patterns 400 may be used to help determine the channel response for the transmitting subscriber station as well as to help identify the subscriber station. Accordingly, the use of SDMA processing techniques by base station 102 (FIG. 1) allows subscriber stations 104 (FIG. 1) to submit requests for uplink bandwidth simultaneously using the same frequency data subcarriers.
In some embodiments, at least some of subscriber stations 104 (FIG. 1) use non-orthogonal data subcarriers 404 for transmission of the uplink bandwidth request messages in next uplink subframe 206 (FIG. 2). Base station 102 (FIG. 1) may receive the uplink bandwidth request messages in next uplink subframe 206 (FIG. 2) from two or more of the subscriber stations may use SDMA techniques to separate the uplink bandwidth request messages sent by the two or more subscriber stations 104 (FIG. 1) on the same data subcarriers 404. In these embodiments, uplink bandwidth request messages may be sent using different of disjoint pilot patterns 400. Although FIG. 4 illustrates only two disjoint pilot patterns 400, embodiments may use more than the two disjoint pilot patterns that are illustrated.
In some embodiments, each subscriber station 104 (FIG. 1) may transmit an orthogonal sequence in uplink subframe 202 (FIG. 2) and may transmit an uplink bandwidth request message in uplink subframe 206 (FIG. 2) using one antenna 105 (FIG. 1), although this is not a requirement. Base station 102 (FIG. 1), on the other hand, receives the uplink bandwidth request messages with two or more of antennas 103 (FIG. 1) so that SDMA techniques may be utilized.
Referring to FIGS. 1-4, in some embodiments, the orthogonal sequences may be randomly selected by subscriber stations 104 prior to their transmission in uplink subframe 202. In these embodiments, subscriber stations 104 transmit the randomly selected orthogonal sequences in two or more tiles 302 during uplink subframe 202 to initiate a request for uplink bandwidth. In these embodiments, subscriber stations 104 may refrain from transmitting non-orthogonal codes or partially orthogonal codes, such as code-division multiple access (CDMA) codes, to base station 102 over the bandwidth request contention channel to initiate a request for uplink bandwidth. In a conventional WiMax network, bandwidth requests by subscriber stations include non-orthogonal codes or partially orthogonal codes, such as CDMA codes, modulated on a significant portion of subcarriers of one OFDM symbol.
In these embodiments, each subscriber station 104 may select two or more non-overlapping tiles 302 for transmission of an orthogonal sequence on the bandwidth request contention channel. The tiles may be randomly selected and a subscriber station 104 may end up selecting tiles that partially or fully overlap with the tiles selected by other subscriber stations. The use of SDMA techniques by base station 102 helps the different orthogonal codes to be detected.
Since the use of SDMA augments the channel bandwidth for the requests, the collision rate and delay are reduced. The use of SDMA also magnifies network throughput using augmented spatial channels, which are formed by antennas 105 of subscriber stations 104 and antennas 103 of base station 102. In accordance with embodiments, SDMA, when is utilized for bandwidth requests, allows two or more subscriber stations 104 to transmit simultaneously. In contrast, when a collision occurs in conventional bandwidth request schemes, neither of the subscriber stations are detected.
In a conventional bandwidth request scheme, CDMA codes are used to help differentiate subscriber stations. In accordance with some embodiments, these CDMA codes are replaced by a set of orthogonal sequences bi for i=1, . . . , M, where




  
    
      b
      j
      H
    
    ⁢
    
      b
      i
    
  
  =
  
    {
    
      
        
          
            M
            ,
          
        
        
          
            
              for
              ⁢
              
                
              
              ⁢
              i
            
            =
            j
          
        
      
      
        
          
            0
            ,
          
        
        
          
            
              for
              ⁢
              
                
              
              ⁢
              i
            
            ≠
            
              j
              .
            
          
        
      
    
  




Any frequency offset may be corrected using downlink common pilot or preamble and the time offset is bounded by periodical ranging. Furthermore, the orthogonal sequence may be sent in multiple tiles 302. Each tile 302 is a time-frequency resource block and may comprise subcarriers adjacent in time and frequency. The orthogonal sequence transmitted in each of the tiles 302 may be the same, although different sequences may be used. The channel response over an entire tile 302 varies little and is treated as constant over that tile.

In some embodiments, each subscriber station 104 randomly selects one out of the M sequences and transmits the selected sequence on the bandwidth request contention channel that are formed by tiles 302. In some example embodiments, base station 102 may use four receive antennas 103 to receive sequences from two subscriber stations 104 that each use one transmit antenna 105. The received signal in tile ‘t’ can be modeled as




  
    
      
        
          
            [
            
              
                
                  
                    
                      y
                      
                        1
                        ,
                        1
                      
                    
                    ⁡
                    
                      (
                      t
                      )
                    
                  
                
                
                  ...
                
                
                  
                    
                      y
                      
                        1
                        ,
                        M
                      
                    
                    ⁡
                    
                      (
                      t
                      )
                    
                  
                
              
              
                
                  ⋮
                
                
                  
                    
                  
                
                
                  ⋮
                
              
              
                
                  
                    
                      y
                      
                        4
                        ,
                        1
                      
                    
                    ⁡
                    
                      (
                      t
                      )
                    
                  
                
                
                  ...
                
                
                  
                    
                      y
                      
                        4
                        ,
                        M
                      
                    
                    ⁡
                    
                      (
                      t
                      )
                    
                  
                
              
            
            ]
          
          
            }
            
              Y
              ⁡
              
                (
                t
                )
              
            
          
        
        =
        
          
            
              
                [
                
                  
                    
                      
                        
                          h
                          
                            1
                            ,
                            1
                          
                        
                        ⁡
                        
                          (
                          t
                          )
                        
                      
                    
                    
                      
                        
                          h
                          
                            1
                            ,
                            2
                          
                        
                        ⁡
                        
                          (
                          t
                          )
                        
                      
                    
                  
                  
                    
                      ⋮
                    
                    
                      ⋮
                    
                  
                  
                    
                      
                        
                          h
                          
                            4
                            ,
                            1
                          
                        
                        ⁡
                        
                          (
                          t
                          )
                        
                      
                    
                    
                      
                        
                          h
                          
                            4
                            ,
                            1
                          
                        
                        ⁡
                        
                          (
                          t
                          )
                        
                      
                    
                  
                
                ]
              
              
                }
                
                  H
                  ⁡
                  
                    (
                    t
                    )
                  
                
              
            
            ⁢
            
              
                [
                
                  
                    
                      
                        b
                        
                          1
                          ,
                          1
                        
                      
                    
                    
                      ...
                    
                    
                      
                        b
                        
                          1
                          ,
                          M
                        
                      
                    
                  
                  
                    
                      
                        b
                        
                          2
                          ,
                          1
                        
                      
                    
                    
                      ...
                    
                    
                      
                        b
                        
                          2
                          ,
                          M
                        
                      
                    
                  
                
                ]
              
              
                }
                B
              
            
          
          +
          
            
              [
              
                
                  
                    
                      
                        n
                        
                          1
                          ,
                          1
                        
                      
                      ⁡
                      
                        (
                        t
                        )
                      
                    
                  
                  
                    ...
                  
                  
                    
                      
                        n
                        
                          1
                          ,
                          M
                        
                      
                      ⁡
                      
                        (
                        t
                        )
                      
                    
                  
                
                
                  
                    ⋮
                  
                  
                    
                      
                    
                  
                  
                    ⋮
                  
                
                
                  
                    
                      
                        n
                        
                          4
                          ,
                          1
                        
                      
                      ⁡
                      
                        (
                        t
                        )
                      
                    
                  
                  
                    ...
                  
                  
                    
                      
                        n
                        
                          4
                          ,
                          M
                        
                      
                      ⁡
                      
                        (
                        t
                        )
                      
                    
                  
                
              
              ]
            
            
              }
              
                N
                ⁡
                
                  (
                  t
                  )
                
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




where yia,it(t) represents the received signal at a base station antenna ia at time it; hia,ja(t) represents the channel response from subscriber ja's transmit antenna to the base station antenna ia and is assumed to be constant over the tile; bi=└bi,1 . . . bi,M┘ represents the orthogonal sequence sent by subscriber i; and nia,it(t) represents the additive white Gaussian noise (AWGN) noise at the base station antenna ia at time it. The two transmitted sequences may be detected in accordance with:




  
    
      
        
          
            [
            
              
                
                  b
                  ^
                
                1
              
              ,
              
                
                  b
                  ^
                
                2
              
            
            ]
          
          =
          
            
              argmax
              
                
                  B
                  ~
                
                ,
                
                  
                    b
                    ~
                  
                  1
                
                ,
                
                  
                    
                      b
                      ~
                    
                    2
                  
                  ∈
                  
                    {
                    
                      
                        b
                        i
                      
                      ,
                      
                        i
                        =
                        1
                      
                      ,
                      ...
                      ⁢
                      
                        
                      
                      ,
                      M
                    
                    }
                  
                
              
            
            ⁢
            
              
                ∑
                t
              
              ⁢
              
                
                  
                  
                    
                      Y
                      ⁡
                      
                        (
                        t
                        )
                      
                    
                    ⁢
                    
                      
                        B
                        ~
                      
                      H
                    
                  
                  
                
                1
              
            
          
        
        ,
      
    
    
      
        (
        2
        )
      
    
  




where




  
    
      
      A
      
    
    1
  
  =
  
    
      ∑
      
        i
        ,
        j
      
    
    ⁢
    
      
        
        
          a
          
            i
            ,
            j
          
        
        
      
      .
    
  




The original channel H(t) may be treated as the transmitted data and the original data B as the channel carrying the virtual data H(t). All possible sequences {tilde over (B)}s may be tried to match against the received signals Y(t). The sequence with the best fit may be selected. The noise term N(t) is not amplified in Equation (2) because {tilde over (B)} consists of unit vectors. Furthermore, Equation (2) may be used to detect subscriber stations 104 even when two subscriber stations 104 transmit the same sequences because the use of SDMA can differentiate the two subscriber stations 104 based on the difference of their spatial channels.

After subscriber stations 104 are detected, base station 102 may schedule the actual submission of the bandwidth request and broadcast the schedule in downlink subframe 204. The bandwidth request submitted by subscriber stations 104 in uplink subframe 206 may be submitted using SDMA. In these embodiments, the SDMA processing techniques are extended for bandwidth requests and base station 102 may allocate time-frequency subchannels for two or more detected subscriber stations 104 to transmit on the same subchannels and may assign two disjoint pilot patterns 400A and 400B to the two detected subscriber stations 104 so that base station 102 may estimate the channel responses from each of the two subscriber stations 104. In these embodiments, base station 102 may assign a different one of disjoint pilot patterns 400 to the two detected subscriber stations 104. The two detected subscriber stations 104 may submit their bandwidth requests over the same subchannels in uplink subframe 206.
FIG. 5 illustrates uplink and downlink subframes of an uplink bandwidth request process in accordance with some alternate embodiments. Uplink (UL) subframes 506 and 510 may correspond to uplink subframes 109 (FIG. 1), and downlink (DL) subframe 508 may correspond to one of downlink subframes 107 (FIG. 1).
In these embodiments, uplink bandwidth request messages may be received on the bandwidth request contention channel from one or more subscriber stations 104 (FIG. 1) in uplink subframe 506. The uplink bandwidth request messages may be generated by subscriber stations 104 (FIG. 1) by modulating pilot subcarriers of a randomly selected disjoint pilot pattern 400 (FIG. 4) with a randomly selected orthogonal sequence. Allocations of uplink bandwidth may be provided to subscriber stations 104 (FIG. 1) in downlink subframe 508 when the uplink bandwidth request messages are successfully detected and decoded. In these embodiments, the first three steps of the uplink bandwidth request process of FIG. 2 are combined and thus, bandwidth can be allocated quicker, with less bandwidth consumption, and with reduced latency.
In these embodiments, base station 102 (FIG. 1) may receive the uplink bandwidth request messages through two or more antennas 103 (FIG. 1) and may apply SDMA techniques to determine channel responses based on the orthogonal sequences to detect and decode the uplink bandwidth request messages. In these embodiments, the uplink bandwidth request messages may be received on the bandwidth request contention channel in uplink subframe 506.
In these embodiments, subscriber stations 104 (FIG. 1) may randomly select one of a plurality of disjoint pilot patterns, such as one of disjoint pilot patterns 400 (FIG. 4), and one of a plurality of orthogonal sequences prior to transmitting the uplink bandwidth request messages. Data subcarriers 404 (FIG. 4) may be modulated by subscriber stations 104 (FIG. 1) with an uplink bandwidth request data element. In these embodiments, base station 102 (FIG. 1) may determine a channel response for each subscriber station 104 (FIG. 1) by applying each of the orthogonal sequences of the plurality to signals received on the pilot subcarriers of disjoint pilot patterns 400 (FIG. 4).
Referring to FIGS. 1 and 3-5, in some embodiments, when a single uplink bandwidth request is received from one subscriber station 104 in uplink subframe 506, base station 102 may detect the uplink bandwidth request using maximum ratio combining (MRC) and may allocate uplink bandwidth for an uplink data transmission in next downlink subframe 508 to the one detected subscriber station.
When two colliding uplink bandwidth requests are received from two subscriber stations 104 over the bandwidth request contention channel and when the two subscriber stations have randomly selected different disjoint pilot patterns and different orthogonal sequences, base station 102 may detect and decode the uplink bandwidth requests using a spatial demultiplexing technique. Base station 102 may indicate an allocation of uplink bandwidth for an uplink data transmission to each of the detected subscriber stations 104 in next downlink subframe 508. Thus, in these embodiments, uplink bandwidth can be allocated in a two-step process, unlike convention processes using CDMA codes that require four or more steps. In these embodiments, the spatial demultiplexing technique may include either a minimum mean square error (MMSE) estimation technique or a zero-forcing technique, although the scope of the embodiments is not limited in this respect.
In some embodiments, when two colliding uplink bandwidth requests are received from two subscriber stations over the bandwidth request contention channel and when the two subscriber stations have randomly selected the same disjoint pilot pattern and different orthogonal sequences, base station 102 may attempt to detect and decode at least one of the uplink bandwidth requests (e.g., with a higher error rate) using a spatial demultiplexing technique (e.g., MMSE or zero forcing). Base station 102 may also allocate uplink bandwidth for an uplink data transmission to at least one of the subscriber stations when at least one subscriber station was successfully detected. In these embodiments, the colliding uplink bandwidth request messages may be received on the bandwidth request contention channel in uplink subframe 506.
In some embodiments, when two colliding uplink bandwidth requests are received from two subscriber stations 104 over the bandwidth request contention channel and when the two subscriber stations 104 have selected the same disjoint pilot pattern and the same orthogonal sequences, base station 102 may refrain from allocating bandwidth for an uplink data transmission to either of the two subscriber stations 104 when the uplink bandwidth requests are unable to be detected and/or decoded. In these embodiments, the base station 102 may be unable to detect either of the uplink bandwidth requests received on the bandwidth request contention channel in uplink subframe 506 since the two subscriber stations 104 have selected the same disjoint pilot pattern and the same orthogonal sequences. Accordingly, base station 102 is unable to provide a bandwidth allocation in next downlink subframe 508. Furthermore, since neither subscriber station 104 has been detected, the base station 102 is unable to broadcast a detected sequence to allocate a transmission resource to a subscriber station 104 for submission of a contention-free uplink bandwidth request, as in the uplink bandwidth request process of FIG. 2.
In some embodiments, subscriber stations 104 may randomly select one of two disjoint pilot patterns 400 and one of two orthogonal sequences for transmission of uplink bandwidth request messages. When more than two colliding uplink bandwidth requests are received from more than two subscriber stations 104 over the bandwidth request contention channel, base station 102 may attempt to detect one or more of the orthogonal sequences and the pilot patterns to detect one or more subscriber stations 104. Base station 102 may also broadcast in a downlink subframe, such as downlink subframe 204 (FIG. 2), the one or more detected orthogonal sequences and pilot patterns to allocate a transmission resource for each detected subscriber station 104. The transmission resource is to be used by the detected subscriber stations 104 to retransmit a contention-free bandwidth request message. In these embodiments, base station 102 may only be able to detect one or more subscriber stations 104, but is likely to be unable to decode the uplink bandwidth request messages. Thus, the detected subscriber stations 104 may be allocated a transmission resource to retransmit an uplink bandwidth request message in a next uplink subframe.
In some embodiments, each subscriber station 104 may include PHY layer circuitry and signal processing circuitry to perform the operations described herein. In these embodiments, the signal processing circuitry may randomly select one of disjoint pilot patterns 400 and one the orthogonal sequences. The PHY layer circuitry may be configured to transmit an uplink bandwidth request message on the bandwidth request contention channel. The PHY layer circuitry may generate the uplink bandwidth request messages by modulating pilot subcarriers of the randomly selected disjoint pilot pattern 400 with the randomly selected orthogonal sequence.
Although base station 102 is illustrated as having several separate functional elements, one or more of the functional elements may be combined and may be implemented by combinations of software-configured elements, such as processing elements including digital signal processors (DSPs), and/or other hardware elements. For example, some elements may comprise one or more microprocessors, DSPs, application specific integrated circuits (ASICs), radio-frequency integrated circuits (RFICs) and combinations of various hardware and logic circuitry for performing at least the functions described herein. In some embodiments, the functional elements of base station 102 may refer to one or more processes operating on one or more processing elements.
Unless specifically stated otherwise, terms such as processing, computing, calculating, determining, displaying, or the like, may refer to an action and/or process of one or more processing or computing systems or similar devices that may manipulate and transform data represented as physical (e.g., electronic) quantities within a processing system's registers and memory into other data similarly represented as physical quantities within the processing system's registers or memories, or other such information storage, transmission or display devices. Furthermore, as used herein, a computing device includes one or more processing elements coupled with computer-readable memory that may be volatile or non-volatile memory or a combination thereof.
Embodiments may be implemented in one or a combination of hardware, firmware and software. Embodiments may also be implemented as instructions stored on a computer-readable medium, which may be read and executed by at least one processor to perform the operations described herein. A computer-readable medium may include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a computer-readable medium may include read-only memory (ROM), random-access memory (RAM), magnetic disk storage media, optical storage media, flash-memory devices, and others.
The Abstract is provided to comply with 37 C.F.R. Section 1.72(b) requiring an abstract that will allow the reader to ascertain the nature and gist of the technical disclosure. It is submitted with the understanding that it will not be used to limit or interpret the scope or meaning of the claims. The following claims are hereby incorporated into the detailed description, with each claim standing on its own as a separate embodiment.

## Claims

1. A bandwidth allocation method performed by a base station, the method comprising:
receiving, over a bandwidth request contention channel, orthogonal sequences sent in two or more tiles during an uplink subframe from subscriber stations, the orthogonal sequences being selected by the subscriber stations from a set of orthogonal sequences, each of the two or more tiles comprising a time-frequency block; and
detecting one or more of the subscriber stations by applying each of the orthogonal sequences of the set to the received orthogonal sequences;
broadcasting in a downlink subframe, the orthogonal sequences corresponding to the detected subscriber stations and an assignment of one of a plurality disjoint pilot patterns to each detected subscriber station; and
receiving uplink bandwidth request messages in the next uplink subframe from the detected subscriber stations in accordance with the disjoint pilot patterns assigned to the detected subscriber stations,
wherein the base station receives the orthogonal sequences from the subscriber stations through a plurality of antennas and uses a space-division multiple access (SDMA) technique to help differentiate two or more of the orthogonal sequences that have collided.

2. The method of claim 1 wherein the disjoint pilot patterns comprise orthogonal pilot subcarriers and non-orthogonal data subcarriers.

3. The method of claim 2 wherein at least some of the subscriber stations use the non-orthogonal data subcarriers for transmission of the uplink bandwidth request messages in the next uplink subframe.

4. The method of claim 3 wherein the detected subscriber stations transmit their uplink bandwidth request messages using one or more antennas, and
wherein the base station receives the uplink bandwidth request messages with two or more antennas.

5. The method of claim 1 wherein the orthogonal sequences are randomly selected by the subscriber stations,
wherein the subscriber stations transmit the randomly selected orthogonal sequences in the two or more tiles during an uplink subframe to request uplink bandwidth, and
wherein each tile comprises a time-frequency block of the bandwidth request contention channel.

6. The method of claim 1 wherein the subscriber stations refrain from transmitting code-division multiple access (CDMA) codes to the base station over the bandwidth request contention channel to request uplink bandwidth.

7. A base station to allocate bandwidth to subscriber stations, the base station comprising:
physical-layer circuitry to receive through two or more antennas over a bandwidth request contention channel, orthogonal sequences sent in two or more tiles during an uplink subframe from subscriber stations, the orthogonal sequences being selected by the subscriber stations from a set of orthogonal sequences, each of the two or more tiles comprising a time-frequency block; and
signal processing circuitry to detect one or more of the subscriber stations by applying each of the orthogonal sequences of the set to the received orthogonal sequences,
wherein the physical-layer circuitry is configured to:
broadcast in a downlink subframe, the orthogonal sequences corresponding to the detected subscriber stations and an assignment of one of a plurality disjoint pilot patterns to each detected subscriber station; and
receive uplink bandwidth request messages in the next uplink subframe from the detected subscriber stations in accordance with the disjoint pilot patterns assigned to the detected subscriber stations, and
wherein the signal processing circuitry uses a space-division multiple access (SDMA) technique to help differentiate two or more of the orthogonal sequences that have collided.

8. The base station of claim 7 wherein the disjoint pilot patterns comprise orthogonal pilot subcarriers and non-orthogonal data subcarriers.

9. A bandwidth allocation request method performed by a subscriber station, the method comprising:
selecting an orthogonal sequence from a set of orthogonal sequences;
transmitting, over a bandwidth request contention channel, the selected orthogonal sequence during an uplink subframe to a base station;
receiving the selected orthogonal sequence broadcasted in a downlink subframe that includes a plurality of orthogonal sequences corresponding to detected subscriber stations;
receiving an assignment of one of a plurality disjoint pilot patterns along with the selected orthogonal sequence in the downlink subframe; and
transmitting an uplink bandwidth request message in the next uplink subframe in accordance with the disjoint pilot pattern assigned to the subscriber station to request uplink bandwidth.

10. The method of claim 9 wherein the disjoint pilot patterns comprise orthogonal pilot subcarriers and non-orthogonal data subcarriers.

11. The method of claim 10 wherein the orthogonal sequences are randomly selected by the subscriber stations,
wherein the subscriber stations transmit the randomly selected orthogonal sequences in the two or more tiles during the uplink subframe, and
wherein each tile comprises a time-frequency block of the bandwidth request contention channel.

12. The method of claim 11 wherein the base station receives orthogonal sequences sent in two or more tiles during the uplink subframe from subscriber stations and prior to broadcasting the orthogonal sequence in the downlink subframe, the base station is to detect one or more of the subscriber stations by applying each of the orthogonal sequences of the set to orthogonal sequences received in the uplink subframe over the bandwidth request contention channel, and
wherein the base station receives the orthogonal sequences from the subscriber stations through a plurality of antennas and uses a space-division multiple access (SDMA) technique to help differentiate two or more of the orthogonal sequences that have collided.

13. A subscriber station comprising:
processing circuitry to select an orthogonal sequence from a set of orthogonal sequences; and
physical layer circuitry to:
transmit, over a bandwidth request contention channel, the selected orthogonal sequence during an uplink subframe to a base station;
receive the selected orthogonal sequence broadcasted in a downlink subframe that includes a plurality of orthogonal sequences corresponding to detected subscriber stations;
receive an assignment of one of a plurality disjoint pilot patterns along with the selected orthogonal sequence in the downlink subframe; and
transmit an uplink bandwidth request message in the next uplink subframe in accordance with the disjoint pilot pattern assigned to the subscriber station to request uplink bandwidth.

14. The subscriber station of claim 13 wherein the disjoint pilot patterns comprise orthogonal pilot subcarriers and non-orthogonal data subcarriers.

15. The subscriber station of claim 14 wherein the orthogonal sequences are randomly selected by the subscriber stations,
wherein the subscriber stations transmit the randomly selected orthogonal sequences in the two or more tiles during the uplink subframe, and
wherein each tile comprises a time-frequency block of the bandwidth request contention channel.

16. The subscriber station of claim 15 wherein the base station receives orthogonal sequences sent in two or more tiles during the uplink subframe from subscriber stations and prior to broadcasting the selected orthogonal sequence in the downlink subframe, the base station is to detect one or more of the subscriber stations by applying each of the orthogonal sequences of the set to orthogonal sequences received in the uplink subframe over the bandwidth request contention channel, and
wherein the base station receives the orthogonal sequences from the subscriber stations through a plurality of antennas and uses a space-division multiple access (SDMA) technique to help differentiate two or more of the orthogonal sequences that have collided.