RADIO RESOURCE MANAGEMENT IN WIRELESS CELLULAR NETWORKS HAVING

MULTI-HOP RELAY STATIONS

PRIORITY CLAIM AND RELATED APPLICATION This application claims benefit of U.S. Provisional Application No. 60/894,186 entitled

"Radio resource management in wireless cellular networks having multihop relay stations" and filed on March 9, 2007, which is incorporated by reference as part of the specification of this application.

BACKGROUND This application relates to wireless communications, including communication systems, apparatus and techniques associated with wireless cellular networks that employ relay stations in addition to base stations.

Wireless cellular networks include stationary or fixed base stations that are spatially distributed over a network's service area to support communiations for network subscriber stations (e.g. mobile phones, PDAs, laptop PCs, etc.). Allocated network channel frequencies are value resources and it is desirable to utlilzie such resources efficiently. Reusing allocated network channel frequencies to increase network capacity is one example for of various techniques for efficiently using the frequency resources. The resue can be implemented, as one example, by partitioning a geographical area into a number of local radio communication service areas or cells and providing frequency reuse allocation that permits a chaanel frequency to be reused in certain non-adjacent cells. At the center of each cell is a fixed base station used for controlling the transmission and reception of protocol data units (PDUs) to and from subscriber stations distributed and roaming within its cell. In many wireless networks, base stations can transmit PDUs directly to subscriber stations via base station downlink (DL) radio signals; subscriber stations transmit PDUs directly to a base station via subscriber station uplink (UL) radio signals. DL and UL radio signals can be optimized based on dynamic channel and network conditions. Cell base stations communicate with each other either by point-to-point radio links, or by high capacity wireline based connections such as optical fibers.

SUMMARY This application includes systems, apparatus and techniques for radio resource management for wireless cellular networks equipped with relay stations for multi-hop packet or protocol data unit (PDU) relaying.

In one aspect, a wireless cellular network with relay stations is described to include a plurality of base stations forming a base station network to provide wireless radio access for subscriber stations for wireless communications and a plurality of relay stations, each relay station being in wireless communication with at least one of the base stations and another relay station to

extend a wireless coverage of the base station network. Each relay station establishes a link connection to a superordinate station, which is either a different relay station or a base station, to be connected to the base station network. This network includes a radio resource management mechansim that operates each base station to provide a base station link-quality matrix to indicate quality of a link between the base station to at least one or more relay stations suborindate to the base station, and one or more subscriber stations. Each element in the link-quality matrix corresponds to a network link and quantifies a quality of a link connecting to at least one or more relay stations suborindate to the base station, and one or more subscriber stations. The radio resource management mechansim opeerats to the base station to allocate frame elements in signal transmission based on the quality of a link between the base station to the at least one or more relay stations suborindate to the base station and the one or more subscriber stations.

In another aspect, a method for managing radio resource in a wireless cellular network with relay stations includes operating a base station to provide a base station link-quality matrix to indicate quality of a link between the base station to at least one or more relay stations suborindate to the base station, and one or more subscriber stations. Each element in the link-quality matrix corresponds to a network link and quantifies a quality of a link connecting to at least one or more relay stations suborindate to the base station, and one or more subscriber stations. This method includes operating the base station to allocate frame elements in signal transmission based on the quality of a link between the base station to the at least one or more relay stations suborindate to the base station and the one or more subscriber stations.

These and other apsects of described systems, apparatus and techniques are described in detail in the drawings, the description and the claims.

BRIEF DESCRIPTION OF DRAWINGS FIG. 1 shows an example of a wireless cellular network with relay stations.

FIG. 2 shows an exemplary cell cluster pair that illustrates basic concept of radio resource reuse.

FIG. 3 is the graphical representation of the wireless cellular network of FIG. 1.

FIG. 4A shows the link rank matrix for the wireless cellular network of FIG. 1. FIG. 4B shows the one-hop connectivity matrix for the wireless cellular network of FIG. 1.

FIG. 4C shows the 5-hop connectivity matrix for the wireless cellular network of FIG. 1.

FIG. 5A illustrates an exemplary fully-used OFDMA TDD Frame.

FIG. 5B illustrates an exemplary partially-used OFDMA TDD Frame.

FIG. 5C illustrates an exemplary burst allocation via DL and UL MAPs according to an embodiment.

FIG. 6A illustrates an exemplary TDD DL-OFDMA subframe for a single-frame relaying method without frame element reuse.

FIG. 6B illustrates an exemplary TDD UL-OFDMA subframe for a single-frame relaying method without frame element reuse. FIG. 6C illustrates an exemplary OFDMA frame without frame element reuse.

FIG. 7A illustrates an exemplary OFDMA frame for a single-frame relaying method with frame element reuse.

FIG. 7B illustrates exemplary OFDMA frame element reuse within single-frame relaying method. FIG. 8 illustrates an example of a flowchart for OFDMA frame element allocation, transmission and reuse within a single-frame relaying method.

FIG. 9 illustrates a flowchart for computing an m-hop link connectivity matrix. FIG. 1OA illustrates an exemplary Mth OFDMA frame for a multi-frame relaying method. FIG. 1OB illustrates an exemplary (M+l)th OFDMA frame for a multi-frame relaying method.

FIG. 1OC illustrates exemplary OFDMA frame element reuse within a multi-frame relaying method.

FIG. 11 illustrates an example of a flowchart for OFDMA frame element allocation, transmission and reuse within a multi-frame relaying method.

DETAILED DESCRIPTION

The performance of wireless cellular networks may be affected by various factors. For example, the capacity and data throughput of a wirless cellular network can be degraded under network conditions such as unavailable or congested network spectrum and poor signal quality. The allocated spectral bands are becoming more and more congested with desired and undesired signals due to the proliferation of both intentional and unintentional electromagnetic emissions.

Congested spectrum results in a combination of low and high power signals being simultaneously observed by a receiver's antenna or antenna array. Consequently, desired signals may be obscured and undetectable since they can be buried beneath much stronger clusters of interfering signals. The signal quality tends to be poor at cell edges due to neighboring cell interference and low DL and UL signal powers. Low power DL and UL signals result in a decrease in throughput since the base and subscriber stations adapt their signals (modulation and coding) to channel and network conditions. Other factos can also degrate the network performance, such as service coverage holes due to shadowing from various buildings, structures and trees, subscriber stations out of the radio signal range of any fixed base station, and non-uniform distribution of subscriber stations and

traffic load due to urban hot spots and rural locations.

One approach to mitigating these and other adverse network conditions is to increase the number of base stations and thereby reduce base station cell size. Base stations are complex radio tranxceivers and include transmitting and receiving circuitry, control circuitry, digital signal processors and a single antenna or an antenna array. Designs and deployment of base stations can be configured to achieve optimal performance based on various factors such as the signal transmit power, antenna height and antenna spatial coverage or beamwidth. One concern for this approach are the high cost of base station installation and limited access to locations that support their installation. Indeed, the cost for deploying a cellular network is normally dominated by base station sites (e.g. real estate costs, planning, maintenance, distribution network, energy, etc.).

Another approach to mitigating these and other adverse network conditions is to use wireless relay stations that work with base stations. One or more relay stations (RSs) can be deployed among certain fixed base stations to relay communication signals between a subscriber station and a base station, thus extending the coverage and improving the communication capacity and quality of the base station. A relay station may be a fixed transceiver or a mobile transceiver station depending on the specific conditions for deploying such as relay station. A subscriber station signals may hop through one or more RSs before reaching a serving base station. The proposed IEEE 802.16j provides Multi-hop Relay (MR) modes to use relay stations for enhanced coverage and service to subscribers. A multi-hop relay wireless network under IEEE 802.16j can include MR base stations (MR-BSs) with the support of the Multi-hop Relay modes.

Relay stations are typically smaller in size and simpler in complexity than regular base stations. Hence, the use of relay stations can be less costly than expanding the radio coverage with the regulra base stations and provide improvements in network capacity, data throughput and service area coverage. Conceptually a relay station can serve as a base station for a subscriber station and as a subscriber station for a base station. Relay stations can be managed by a base station, but they may also have some local control of relay functions within their cell of a cellular network. One or more relay stations can be deployed to relay or forward signals between subscriber stations and base stations. Subscriber station and base station PDUs may hop through one or more relay stations before reaching their desired destination. FIG. 1 illustrates a portion of an exemplary wireless multi-hop relay communication system.

This system includes multi-hop relay base stations (MR-BSs) and relay stations (e.g., RSl, RS2, and RS3) to provide radio coverage for serving one or more subscriber stations (e.g., SSl to SS8). The base stations form a base station network to provide wireless radio access for wireless communications. Each relay station is in wireless communication with at least one of the base stations and another relay station to extend a wireless coverage of the base station network. Each

relay station establishes a wireless link connection to a superordinate station, which is either a different relay station or a base station, to be connected to the base station network.

For example, the BS in FIG. 1 is shown to have three relay stations, RSl, RS2 and RS3 that expand the service coverage of the BS. The relay stations RSl, RS2 and RS3 are subordinate to the BS because the BS is connected to the network and is the gateway for the relations RSl, RS2 and RS3 to the rest of the network. Accordingly, the BS is the superordinate to the relay stations RSl, RS2 and RS3. hi addition, it is possible for relay stations RSl, RS2 and RS3 under the control of the superordinate BS to have superordinate and subordinate relationships with one another. For example, the relay station RS3 is subordinate to the relay station RS2 because RS3 communicates to BS through RS2. Therefore, the relay station RS2 is the superordinate to the relay station RS3. In this context, BSs and relation stations in the system in FIG. 1 can be classified into superordinate base stations and subordinate base stations based on their relative relationships. Accordingly, the BS in FIG. 1 is the superordinate base station to all relay stations and the relay station RS2 is a subordinate base station to the BS but a superordinate base station to the relay station RS3. In FIG. 1, two subscriber stations SS3 and SS4 are shown to be in a coverage area of the RSl. Two subscriber stations SS5 and SS6 and one relay station RS3 are shown to be in a coverage area of RS2. The subscriber station s SS7 and SS8 are served by RS3. A relay station (RS) is introduced between a MR base station (MR-BS) and one or more subscriber stations (SSs) (e.g., a mobile subscriber station) or one or more additional subordinate relay stations.

The relay station deployment shown in FIG. 1 can be used to achieve certain advantages in varous system implementations. For example, the throughput can be enhanced via the replacement of low rate, unreliable links with multiple high rate, reliable links; the radio coverage area can be extended to isolated network service areas; the power consumption can be reduced to increasethe battery life for mobile subscriber stations; and efficient radio resource use and reuse cam be implemented due to the spatial distribution of network stations. Additional advantages include increased network capacity and improved network load sharing, flexible placement of base station or cell sites due to fewer access limitations, and better network fault tolerance and spatial diversity via multi-path redundancy. Relay stations may be classified as fixed, nomadic or mobile. A fixed relay station is permanently installed at a location; a nomadic relay station may be moved but is fixed when operating. A mobile relay station may be placed on vehicle such as a bus, train or boat and is intended to operate while the vehicle is fixed or in motion. Relay stations can be classified according to their forwarding strategy. Examples of relay station forwarding strategies include Amplify- and-forward in which an amplify-and-forward relay station acts as an analog repeater and

an amplify-and-forward relay station may increaset the signal noise; Decode-and-Forward in which a decode-and-forward relay station decodes received PDUs, re-encodes and retransmits the received PDUs; and Decode-and-Reencode in which a decode-and-reencode relay station decodes a received PDU and constructs a codeword differing from the source codeword. Decode-and-reencode relay stations allow smart forwarding, can take advantage of adaptive transmission with different modulation and coding schemes on different network hops, and can participate in interference avoidance and mitigation schemes. The latter two relay station forwarding strategies may experience propagation of the decoding errors through a network path which may lead to a wrong decision at a destination. Various relay station usage methods can be implemented. In one implementation, relay stations are configured and operated as signal forwarders that operate in a network path within the cellular network and each relay station in a network path relies solely on PDUs sent to it by its immediate path predecessor. Such relaying methods can be used to reduce the end-to-end network path loss between a PDU source and its destination, hi another implemneation, spatially distributed relay stations are configured and operated to cooperate with one another to provide spatial diversity. More specifically, relay station transmissions received at a destination may be combined to achieve spatial diversity. This spatial diversity via cooperaton among the spatially distributed relaying stations is different from spatial diversity achieved via antenna arrays without having the integration of multiple antenna elements at a base , subcriber or relay station and without requiring signals received by antenna array elements to be uncorrelated for optimal performance. In scenarios where these conditions for the antenna array-based spatial diversity cannot be met, spatial diversity via cooperaton among the spatially distributed relaying stations provides an alternative by distributing the antenna array elements among base, subcriber and relay stations to form a "virtual" antenna array. Deployment of relay stations within current and future cellular networks poses many technical challenges in connection with various features in the networks such as PDU routing, radio resource management, use of advanced antenna technologies, network management, network security, and spatial deviersity. To facilitate the deployment of relay stations new network subsystems and methods may be required. Further, it may be desirable that features for relaying methods be added to some cellular networks with minimal changes to the existing designs of subscriber and base stations.

Various features for radio resource management in a wireless multi-hop relay communication system are described in this application. One example is radio resource management (RRM) which concerns cellular network capacity issues rather than point-to-point channel capacity. RRM involves designing procedures, algorithms and data structures that direct, control and facilitate the

optimal utilization of a network's radio-based communication links. Efficient dynamic RRM methods may be used to increase network capacity by an order of magnitude. RRM can be used in cellular systems that are limited by co-channel interference.

Examples of applications for the present RRM procedures, algorithms and data structures include, among others, mitigation of signal fading and signal degradations due to co-channel interference, noise, signal propagation distances, shadowing, multipath, and Doppler frequency shifts; radio or network connection admission control; scheduling and allocation of frame elements for PDU transmissions; cell design, cell sectoring, and cell-to-cell handoff; power control and allocation; adaptive modulation and error control coding; fixed and dynamic channel frequency selection and allocation; and bandwith reservation and quality of service guarantee. Techniques for radio resource reuse are also described in this application.

FIG. 2 shows an example of frequency resue in two groups of seven hexagonal cells arranged as two cell clusters. Each cell in a cluster contains a base or relay station that is denoted by CeIl ₁ , where the subscript / = 0, ... ,6 . Each base statoin or relay station in a cluster is allowed to use one of seven independent subsets of allocated radio resources (e.g. frequencies, time slots, etc.). Base and relay stations with the same index i use the same set of radio resources. Radio resources may be reused in another cell that is separated from the first by at least the reuse distance which is a distance such that interference between cells will not corrupt reception to a point where desired signals cannot be extracted from a received composite signal. The radio resource reuse concept allows base and relay stations in different cell clusters to simultaneously use and share a set of radio resources, thereby increasing network capacity.

In various practical system deployment, predominant interference within a cellular network can be classified as co-channel interference (CCI) and adjacent channel interference (ACI). CCI is typically observed by a receiver when a transmitter within an adjacent cell cluster is transmitting simultaneously on the receiver's frequency and the transmitter is within the receive range of the receiver. CCI can be controlled by restricting the separation of the transmitter to be greater than the reuse distance or by using some means of dividing the transmission and reception times between radios so that only one is transmitter operational at any one time. If two transmitters are operating within adjacent frequency bands, ACI may be result. ACI results when spectral components from signals which are adjacent in frequency are not fully isolated. For example, ACI would result due to nonideal modem filter characteristics. This can be minimized by judicious design of modulation scheme and filter design.

Sytems, apparatus and methods described in this application may be implemented to achieve one or more advnatages or benefits. For example, deployment of relay stations may result in a decrease in network capacity in some systems because PDUs may be relayed several times and

therefore occupy multiple frame elements. Capacity for networks with relays can be substantially improved by reusing frame elements for different independent network links. The RRM aspect relates to the allocation, transmission and reuse of frame elements within multi-hop cellular networks equipped with relay stations. Sytems, apparatus and methods described in this application can be implemented to provide a method for frame element allocation, transmission and reuse within multi-hop cellular networks. In some implemnetaitons, frame elements can be used to better support relayed PDU transmissions that occur between base, relay and subcriber stations, where relay and subcriber stations may be fixed, nomadic and/or mobile. Sytems, apparatus and methods described in this application can also be implemented to provide increased network capacity and improve the spectral effciency of individual relay station transmissions. For exmaple, one disclosed method for frame element allocation, transmission and reuse can be used, in some implementations, to minimize interference so that no base, subscriber or relay station within the same network cell can transmit and receive simultanously using the same frame elements. The frame elements can be spatially reused by base, subscriber and relay stations. In addition, the total number of frame elements can be kept at a minimum as available bandwidth and allowed delay are limited.

Various features described can be implemented within wireless cellular networks such as the exemplary network illustrated in FIG. 1 showing a portion of an exemplary wireless cellular network C with relay stations added to support multi-hop PDU relaying. This exemplary network includes one base station (BS) and three relay stations (RSl, RS2, and RS3). Working together the base station and relay stations provide radio coverage to subscriber stations (SSl to SS8). The circles enclose the coverage areas of the BS and RSs. For example, subscriber stations SS3 and SS4 are shown to be within the coverage area or cells of the RSl and the outer edge of the BS cell. In FIG. 1, subscriber stations SSl and SS2 are directly served by the base station without hopping through any relay stations. The base station communicates with SS5 and SS6 via RS2 so downlink PDUs from the base station is first transmitted to RS2, RS2 then transmits the PDUs to SS5 and SS6. Base station downlink PDUs for SS7 and SS8 go through two hops via RS2 and RS3. The base station communicates with SS3 and SS4 via RSl, therefore the DL PDUs are first sent from the BS to RS 1 , RS 1 then sends the PDUs to SS3 and SS4.

FIG. 3 shows a graph structure of the exemplary network of FIG. 1. The network graph of FIG. 3 is defined by the triple C = (N, L, R) where N, L and R are definede below. Set N is the network's M -element node set comprised of base stations, subscriber stations and relay stations:

N = {ra ₁ , n ₂ , n ₃ , n ₄ , n ₅ ,« ₆ ,..., n ₁₂ }

= {BS, RSl, RS2,RS3, SS1, SS2,..., SSS]

Set L is a network link set comprised of node pairs; each pair denotes a link connection within the network, that is,

L = {{BS, SSI), {BS, SS2), {BS, RS1), . .. , {RS3, SS7), {RSX SS&)}

Matrix R contains link ranks or weights; each element in R corresponds to a link L .

FIG. 4A shows the link rank matrix R for the wireless cellular network of FIG. 1. For the network of FIG. 3, values of zero within the rank matrix R indicate that no link exists between a network node pair. The non-zero link ranks may be any radio resource measurement value or combination that indicates the quality of network link. For example, the value BS-RSl (row 1, column 2 in R ) may contain a four bit link-quality value such as

0 ifO < 5/N7?(BS - RS I) -^ ₁

1 if CC, < SINR (BS - RS 1) < CC ₂ BS - RSl = ^{1 2}

2 if CC ₁ < SINR(BS - RS 1) < CC ₃

3 if Gr ₃ < SINR(BS -RSl)

SINR (BS-RSl) denotes an estimate of the ratio of signal power to interference-plus-noise for the network link BS-RSl and CC ₁ , i = 1,2,3 , specified SIνR decision region bounds.

A network path of hop -length P from a source node to a sink node is a sequence of P links. Network paths within C are elementary meaning all nodes in a path are traversed only once. Network paths within C contain no cycles meaning the initial and final nodes in a path are distinct. The rank of a network path is defined as a the summation of its link ranks.

Let N _subna be a subset of N . A subnetwork C _subnet of C is derived from the set difference

N - N _mbnet . Specifically, C _subnet is derived from N by removing all nodes and links associated with N _subnet . For example, FIG. 3 illustrates a subnetwork derived from the set difference

N -N _subnet =

= N -{BS,RS1,RS2,SSI, SS2, SS3, SS4, SS5, SS6}

Exemplary Method for Multi-hop Connectivity Identification

FIG. 4B shows the one-hop connectivity matrix for the wireless cellular network of FIG. 1.

FIG. 4C shows the 5-hop connectivity matrix for the wireless cellular network of FIG. 1.

The 1 -hop network connectivity matrix C ⁽¹⁾ for an arbitray M -node network C = (N, L, R) is defined as the M -by- M matrix C ⁽¹⁾ = {c™ }* _J=l where

11 If a link from node re, to w _; exists c , _y (D = _ < ^ 0 If a link from node re, to re _; does not exist

[0 Jf i = j

C ⁽¹⁾ can be obtained from the ranking matrix R of FIG. 4A by the applying specified 1 -bit quantization map to the elements of R . FIG. 4B shows the one-hop network connectivity matrix C ⁽¹⁾ for the exemplary network of FIG. 1.

More generally the m -hop connectivity matrix for network C is defined by the M -by- M matrix C ^(m) = {c< ^m) }" ₌₁ where

m Node re, is connected to re by a path of P = m links or hops

0 otherwise

The element c^ ^m) is computed using the iterative equation

c^ ⁽ = c^- ^V) +ψ^, m ≥ 2 where

FIG. 4C shows the 5-hop network connectivity matrix C ⁽⁵⁾ for the exemplary network of FIG. 1 and 2. FIG. 10 shows a flowchart of one exemplary method for computing the 5-hop network connectivity matrix C ^(m) .

Exemplary Cellular Network Physical Layer

Various described features can be applied to Orthogonal Frequency Division Multiplexing (OFDM), Orthogonal Frequency Division Multiple Access (OFDMA), and Time Division

Duplexing (TDD). Examples of physical layers for these technologies are described below.

OFDM is a technique for multicarrier data transmission that has been standardized for several wireless network physical layers. In OFDM, an allocated channel is divided into a number of orthogonal subchannels. Each subchannel has an equal bandwidth and is centered on the unique frequency of a subcarrier signal. The subcarrier signals are orthogonal in that the inner product of any two of the subcarriers equals zero. The frequencies of the orthogonal subcarrier signals are equally and minimally spaced so data modulation of the subcarrier signals facilitates optimal bandwidth efficiency. In comparison, frequency division multiplexing for multicarrier data transmission utilizes non-orthogonal subcarrier signals and therefore wastes large segments of allocated channel bandwidth in order to isolate subcarrier signal frequency spectra.

OFDMA is a multi-user version of OFDM. Multiple access is achieved in OFDMA by assigning subsets of orthogonal subcarriers to individual subscriber stations. OFDMA can be described as a combination of frequency domain and time domain multiple access where radio resources are partitioned in a time-frequency space, and network user data bursts are assigned along the OFDM symbol index as well as OFDM sub-carrier index. The addition of relay stations within a cellular network allows for OFDMA with time, frequency and spatial domain multiple access. Simultaneous data transmissions between several subscriber stations, base station or relay stations may occur if they are spatially distributed and their interference to each other is below a specified threshold. OFDMA physical layers can be configured to use Time Division Duplexing (TDD). To counter interference issues, TDD uses system-wide synchronization. TDD has certain advantages when compared to Frequency Division Duplexing (FDD). For example, TDD efficiently supports asymmetric bandwidth for downlink (DL) and uplink (UL) signals; TDD enables channel reciprocity for better support of link adaptation, MIMO and other signal processsing methods; TDD only uses a single channel for DL and UL signals thereby providing flexibility for various spectrum usage requirements; and transceiver designs for TDD systems are less complex than FDD.

Exemplary Frame Structure and Elements

Applicatoins based on the exemplary OFDMA frame structure are described within this subsection.

An OFDMA frame includes DL and UL transmissions. FIG. 5A illustrates exemplary OFDMA frame structure for a physical layer based on TDD. Each frame is divided into DL and UL subframes that are respectively separated by a Transmit Transition Gap (TTG) and a Receive Transition Gap (RTG). These two gaps prevent DL and UL transmission collisions. Each subframe is comprised of a number of frame elements. These frame elements are the radio resources that may

be allocated, transmitted and reused. FIG. 5B illustrates an exemplary partially-used OFDMA TDD Frame.

FIG. 5A and FIG. 5B illustrate exemplary OFDMA frame elements for Zone, Burst, Slot, Subchannel, Suchannel Group, Symbol, and Segment. Zone:

A OFDMA frame includes one or more zones. A zone is one complete logical part or partition of an OFDMA frame. There are different types of DL and UL zones. Zones may use all of the OFDM signal subchannels or only a subset of the subchannels. Zones that use all of the OFDM signal subchannels are called Fully Used Subchannel (FUSC) zones; those that use a subset of the subchannels are called Partially Used Subchannel (PUSC) zones. See FIG. 5B for an exemplary PUSC zone within a DL subframe.

Burst:

A zone includes DL or UL bursts. A burst is an area within a zone that uses a specified number of subchannels (frequencies) and a specified number of OFDM symbols (time slots). See FIG. 5A and FIG. 5B for examples.

Slot:

A burst includes slots. A slot is the minimum possible data allocation unit within a OFDMA-based system and is defined in time and frequency. A slot has one subchannel and can contain a number of OFDM symbols (depending on the zone type). See FIG. 5A for an example. Subchannel:

A subchannel is the smallest logical allocation unit within the frequency domain and has one or more subcarriers that are normally non-adjacent carriers and whose order may change within a burst from OFDM symbol to symbol. FIG. 5A and 5B show N subchannels for the frames.

Subchannel Group: A subchannel group is comprised of one or more subchannels. See FIG. 5B for an example.

Symbol:

A symbol is the smallest allocation unit in the time domain. FIG. 5A shows DL and UL subframes comprised of L and M symbols.

Segment: A segment is a set of OFDMA subchannel groups. FIG. 5B shows three segments within a

DL subframe.

An OFDMA frame may have various control fields to manage the usage of the frame elements. Exemplary control fields are shown within FIG. 5C.

Preamble: The preamble is used for DL synchronization (frame timing acquisition, frequency offset

estimation, symbol timing estimation) and channel estimation and is the first OFDM symbol of an OFDMA frame. As an example, the preamble can be a binary phase shift keying (BPSK) modulated preamble or in other modulatoin formats. The preamble is a reference field known by all network receivers. Frame Control Header (FCH):

The FCH follows the preamble field and is transmitted using quadrature phase shift keying (QPSK) rate 1/2 channel coding and four-fold repetition encoding (four subchannels with successive logical subchannel numbers). The FCH provides frame configuration information such as the following: Subchannel groups used on the first DL-PUSC zone and DL-MAP (Medium Access Protocol) info. The DL-MAP includes subchannels used, subchannel repetition coding used in DL-MAP, channel coding used in DL-MAP, and DL-MAP length.

DL-MAP and UL-MAP:

The DL-MAP and UL-MAP provide frame element allocation and other control information for the DL and UL sub-frames, respectively. The DL/UL map begins with header information followed by one or more DL-MAP/UL-MAP information elements (DL-MAP/UL-MAP IEs).

UL Ranging:

The UL ranging subchannel is allocated for subscriber or relay stations to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests. Four types of ranging are defined: initial ranging for when a SS enters the network; periodic ranging after a connection is set up, hand-over ranging, and bandwidth request.

UL channel quality indicator channel (CQICH):

The UL CQICH is used by subscriber or relay stations to feedback channel-state information.

UL ACK:

The UL ACK is used by subscriber or relay stations to feedback DL Hybrid- ARQ acknowledgements.

Frame Element Allocation hi some implementatons, the base station can be used to allocate frame elements (slots, bursts, zones, subchannels, subchannel groups, etc.) for all PDU transmissions between the base station, relay stations and subcriber stations. The frame element allocation by the base station may be based on one or more factors: (1) link quality as indicated by elements of the link rank matrix R (FIG. 4A) and/or the link connectivity matrices (FIG. 4B and 4C), (2) the size of a PDU to be transmitted, and (3) the type of PDUs (described by frame control fields) that an RS can support and forward to other base, subscriber and relay stations within its coverage area. The base station can allocate frame elements based on the location and spatial distribution of

the base station and relay and subscriber stations. The base station can concurrently use or reuse frame elements whenever the spatial distribution of communicating network stations is such that their co-channel interference to each other is below certain reasonable levels. For example the cell coverage areas of RSl and RS3 in FIG. 1 do not overlap. Hence, frame elements for RSl and RS3 can be concurrently used to further enhance network capacity and throughput.

A base station may be pre-configured with network link connection information or may be operatd to acquire network link connection information. Such network link connection information indicates the coverage areas of its subordinate relay stations. Using network link connection information, a base station can optimally allocate DL subframe elements to its subordinate relay stations. For example, assume that there are two or more relay stations with no overlapped downlink coverage (e.g. RS l and RS3 of FIG. 1 or 2), or in other words, their co-channel interference to each other is below certain reasonable levels. Using link connection information as in the link rank matrix R and/or the connectivity matrices (see FIG. 4A, FIG. 4B and FIG. 4C) the base station can command relay stations RSl and RS3 to concurrently use or reuse the same frame elements for their downlink PDU transmissions to the subscriber stations within their coverage areas.

A base station may be pre-configured with network link connection information or may be operated to acquire network link connection information. Such network link connection information indicates the coverage areas of its subordinate relay stations. Using network link connection information a base station can optimally allocate UL subframe elements to its subordinate relay stations. For example, assume that there are two or more relay stations with no overlapped downlink coverage (e.g. RS l and RS3 of FIG. 1 or 2), or in other words, their co-channel interference to each other is below certain reasonable levels. Using link connection information as in the link rank matrix R and/or the connectivity matrices (see FIG. 4A, FIG. 4B and FIG. 4C) the base station can command relay stations RSl and RS3 to concurrently use or reuse the same frame elements for their uplink PDU transmissions to the BS and RS2 within their respective coverage areas.

Frame Element Transmission for Single-frame Relaying A base station can be configured to have the option of selecting a single-frame relaying (SFR) method. In a single-frame relaying (SFR) method DL and UL transmissions between a BS and its subordinate relay and subscriber stations can occur using a single OFDMA frame. Relay stations in a source-to-sink network path need to synchronize with each other so PDUs are quickly hopped from station to station within the network path. FIG. 6A shows an exemplary DL subframe structure for an SFR method. FIG. 6B displays an

exemplary UL subframe structure for an SFR method.

FIG. 7A shows an exemplary subframe for an SFR Method that may be used to facilitate frame element reuse. FIG. 7B clarifies how frame slots may be reused by RS 1 and RS3 due to the spatial distribution of RSl and RS3. Using an SFR method source-to-sink PDU transmission time is less compared to a multi-frame relaying method (described below) but may require more complex hardware so relay stations with a path can process received PDUs within a specified time interval.

DL Subframe Transmission for Single-frame Relaying

Referring to FIG. 7A, FIG. 7B and to the flowcharts in FIG. 8 and FIG. 9, the steps for the allocation and transmission of DL subframe elements for a single-frame relaying method are described below.

In step 92 the base station initializes a network graph defined by the triple C = (N, L, R) . Set N is the network's M -element node set comprised of base stations, subscriber stations and relay stations, set L is a network link set comprised of node pairs; each pair denotes a link connection within the network, matrix R contains link ranks or weights; each element in R corresponds to a link L within C . Network C includes all network nodes for which the base station allocates frame elements to carry PDU transmissions. hi step 94 the base station obtains one or more PDUs that are to be transmitted to nodes within its service network C defined above. hi step 96 the base station the groups the PDUs according to their desitination nodes within the node N of the service network C .

The ranks or weights of all links within the link set L are contained within the link rank matrix R . In step 98 the base station first updates the link rank matrix R (see FIG. 4A). The link rank matrix R can be easily updated from link quality estimates returned to the base station by relay and subscriber stations via their UL channel quality indicator channels. This is described below and shown in FIG. 9 by the horizontal arrow to block 94. Using the updated R the base station then updates the m -hop connectivity matrix C ^(m) (FIG. 4C). The flowchart for the method of updating C ^(m) based on updates of R is shown in FIG. 9. This process can be implemented as an application of an algorithm published by L. E. Miller, " Multihop Connectivity of Arbitrary Networks," Wireless Communication Technologies Group, NIST, Tech Report (March 2001). In one embodiment, network C can contain mobile and/or nomadic relay and subscriber stations so node set N and link set L can change. Hence, C ^(ra) is acquired and updated at different time intervals using the method of FIG. 9. In another emobodiment, the base station can be pre-configured with C ^(m) . For example, if all network relay and susbscriber stations are fixed in

location the base station could be pre-configured with a fixed C ^(m) and only R would need to be updated.

Using the updated link ranks within R , the updated link connectivity matrix C ^(ra) , and an appropriate ranking algorithm the base station then ranks and selects the optimal paths for transmitting PDUs to their destinations. More specifically, a number of candidate paths may exist between the base station and a desired PDU destination node. Using R and C ^(m) the base station can rank all candidate paths and select the optimal path. For example, FIG. 3 shows two possible paths from the base station to subscriber station SS6, both a one-hop and two-hop path exist. The base station may rank the two paths using the link rank BS-SS6 for the one-hop path and a simple summation of the link ranks BS-RS2 and RS2-SS6 for the two-hop path.

Using the outputs of the ranking algorithm the base station then optimally allocates or apportions frame elements (slots, bursts, zones, subchannels, subchannel groups, and segments) that are to be used by the relay and subscriber stations within its service network C . The base station then constructs DL and UL MAPs based on the optimal frame element allocation. In another emobodiment, path diversity may be implemented by receiving relay and subscriber stations. For example, referring to FIG. 7A it is seen that frame bursts are allocated for both of the two paths to SS6 as described above. One is marked " Direct BS to SS6 path" the other is marked " Relayed BS to SS6 path." For clarity only the RS2 DL burst is marked in FIG. 7A. The BS DL burst would be the BS-RS2 burst of the BS-DL Zone. The UL bursts for two-hop path is also marked in a similar manner within FIG. 7A. The base station may use both paths or one of the two paths. Signal processing methods that exploit the path diversity can therefore be implemented in subscriber station SS6.

In step 100 the base station constructs and transmits the BS Preamble of the DL subframe. The BS Preamble is a reference signal known by all receivers within the exemplary network C of FIG. 3. It is used by the base station's one-hop relay stations (RSl, RS2) and its one-hop subscriber stations (SSl, SS2, SS3, SS6) for DL synchronization (frame timing acquisition, frequency offset estimation, symbol timing estimation) and link or channel quality estimation. RSl, RS2, SS l, SS2, SS3 and SS6 use the BS Preamble to obtain link quality estimates BS-RS l, BS-RS2, BS-SSl, BS-SS2, BS-SS3 and BS-SS6 as defined in the first row of the link rank matrix of FIG. 4A. These link quality estimates can be returned to the base station in the UL frame so the base station can update R . hi steps 102 and 104 the base station constructs and transmits the BS DL Zone of the DL subframe. As shown in FIG. 7A, the BS DL Zone is comprised of an FCH, DL-MAP, UL-MAP and DL bursts that are to be transmitted by the base station to its one-hop relay stations (RS 1 , RS2) and its one-hop subscriber stations (SS 1, SS2, SS3, SS6). The DL and UL burst allocations for the

Base Station DL and UL Zones are specified by the BS using information elements (IEs) that are within the BS Downlink Map (DL-MAP) and BS Uplink Map (UL-MAP). FIG. 5C shows an exemplary group of DL-MAP and UL-MAP IEs and their usage in allocating bursts. The base station's one-hop neighbors (RSl, RS2, SS l, SS2, SS3, SS6) receive the BS DL Zone and prepare to receive DL data and transmit UL data based on frame element usage commands within their sections of the DL-MAP and UL-MAP. These MAPs were derived by the BS according to step 98. hi step 106 relay station RS2 constructs and transmits the RS2 Preamble of the DL subframe. The RS2 Preamble is a reference signal known by all receivers within the exemplary network C of FIG 2. It is used by relay station RS2's one-hop relay station (RS3) and its one-hop subscriber stations (SS5, SS6, SS8) for DL synchronization (frame timing acquisition, frequency offset estimation, symbol timing estimation) and link or channel quality estimation. RS3, SS5, SS6, and SS8 use the RS2 Preamble to obtain link quality estimates RS2-RS3, RS2-SS5, RS2-SS6 and RS2-SS8 as defined in row three of the link rank matrix of FIG. 4A. These link quality estimates can be returned to the base station in the UL frame so the base station can update R . hi steps 108 and 110 relay station RS2 constructs and transmits the RS2 DL Zone of the DL subframe. As shown in FIG. 7A, the RS2 DL Zone is comprised of an FCH, DL-MAP, UL-MAP and DL bursts that are to be transmitted by RS2 to its one-hop relay station RS3 and its one-hop subscriber stations (SS5, SS6, SS8). The DL and UL burst allocations for the RS2 DL and UL Zones are specified by RS2 using information elements (IEs) that are within the RS2 Downlink Map (DL-MAP) and RS2 Uplink Map (UL-MAP). RS2's one-hop neighbors (RS3, SS5, SS6, SS8) receive the RS2 DL Zone and prepare to receive DL data and transmit UL data based on frame element usage commands within their sections of the DL-MAP and UL-MAP. These MAPs were originally derived by the BS according to step 98 so RS2 serves as a MAP forwarding node for the BS. hi step 112 relay stations RS 1 and RS 3 concurrently construct and transmit the RS 1 Preamble and the RS3 Preamble of the DL subframe. The RS 1 Preamble is a reference signal known by all network receivers. It is used by SS3 and SS4 for DL synchronization (frame timing acquisition, frequency offset estimation, symbol timing estimation) and channel estimation. SS3 and SS4 can use the RS l Preamble to obtain link quality estimates RSl -S S 3 and RS1-SS4 as defined in row two of the link rank matrix of FIG. 4A. The RS3 Preamble is a reference signal known by all network receivers. It is used by SS7 and SS8 for DL synchronization (frame timing acquisition, frequency offset estimation, symbol timing estimation) and channel estimation. SS7 and SS8 can use the RS 3 Preamble to obtain link quality estimates RS3-SS7 and RS3-SS8 as defined in row four of the link rank matrix of FIG. 4A. These link quality estimates can be returned to the base station in the UL frame so the base station can update R .

In steps 114 and 116 relay stations RSl and RS3 construct the RS l DL Zone and the RS3 DL Zone of the DL subframe. Because of the spatial distribution of RS 1 and RS3 downlink zones for RSl and RS3 are transmitted concurrently using the same frame elements (see FIG. 7B for clarification). The RS 1 DL Zone is comprised of an FCH, DL-MAP, UL-MAP and DL bursts that are to be transmitted by RSl to its one-hop subscriber stations (SS3, SS4). The RS3 DL Zone is comprised of an FCH, DL-MAP, UL-MAP and DL bursts that are to be transmitted by RS 3 to its one-hop subscriber stations (SS7, SS8). For clarity these fields are not shown within FIG. 7A. If shown they would have a similar structure to that shown for the RS2 DL Zone. The DL and UL burst allocations for the RS 1 DL and UL Zones are specified by RS 1 using information elements (IEs) that are within the RS 1 Downlink Map (DL-MAP) and RS 1 Uplink Map (UL-MAP). The DL and UL burst allocations for the RS 3 DL and UL Zones are specified by RS 3 using information elements (IEs) that are within the RS3 Downlink Map (DL-MAP) and RS3 Uplink Map (UL-MAP). RSI's one-hop neighbors (SS3, SS4) receive the RSl DL Zone and prepare to receive DL data and transmit UL data based on frame element usage commands within their sections of the DL-MAP and UL-MAP. RS3's one-hop neighbors (SS7, SS8) receive the RS3 DL Zone and prepare to receive DL data and transmit UL data based on frame element usage commands within their sections of the DL-MAP and UL-MAP. The RSl and RS3 MAPs were originally derived by the BS according to step 98 so RS l and RS 3 serve as a MAP forwarding nodes for the BS.

UL Subframe Transmission for Single-frame Relaying

Referring to FIG. 7A, FIG. 7B and to the flowcharts in FIG. 8 and FIG. 9, the steps for the allocation and transmission of UL subframe elements for a single-frame relaying method are described below. hi steps 118 and 120 the one-hop subscriber stations (SS3, SS4) of relay station RSl and the one-hop subscriber stations (SS7, SS8) of RS3 concurrently construct the RSl UL Zone and the RS3 UL Zone of the UL subframe. The RS 1 UL Zone is comprised of data bursts that are to be transmitted from one-hop subscriber stations (SS3, SS4) to RS l. The RS3 UL Zone is comprised of data bursts that are to be transmitted from one-hop subscriber stations (SS7, SS8) to RS3. Because of the spatial distribution of RS 1 and RS 3 uplink zones for RS 1 and RS 3 are transmitted concurrently using the same frame elements (see FIG. 7B for clarification). Burst allocations for the RS 1 and RS 3 UL Zones are specified using information elements within the RS 1 Uplink Map (UL-MAP) and the RS3 Uplink Map (UL-MAP) received in step 114. Information for RSI's UL-MAP are obtained from the base station via a one-hop DL burst from the BS to RSl. Information for RS3's UL-MAP are obtained from the base station via a two-hop DL burst from the BS to RS2 to RS3.

The Uplink zones for RS 1 and RS3 also include an RS 1 UL Ranging Subchannel, an RS3 UL Ranging Subchannel, an RSl UL CQICH (channel quality indicator channel), an RS3 UL CQICH, an RSl UL ACK subchannel, and an RS3 UL ACK subchannel. For clarity these fields are not shown within FIG. 7A. If shown they would have a similar structure to that shown in the RS2 UL Zone.

The RSl UL ranging subchannel is used by RSI's one-hop subscriber stations (SS3, SS4) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests. The RS3 UL ranging subchannel is used by RS3's one-hop subscriber stations (SS7, SS8) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests. The RS 1 UL CQICH (channel quality indicator channel) is used by RS l's one-hop subscriber stations (SS3, SS4) to feedback channel-state information to RSl. Specifcally the link quality estimates RS1-SS3 and RS1-SS4 as defined in row two of the link rank matrix of FIG. 4A. The base station can use these estimates to update the link rank matrix R shown in FIG. 4A.

The RS3 UL CQICH (channel quality indicator channel) is used by RS3's one-hop subscriber stations (SS7, SS8) to feedback channel-state information to RS3. Specifically the link quality estimates RS3-SS7 and RS3-SS8 as defined in row four of the link rank matrix of FIG. 4A. The base station can use these estimates to update the link rank matrix R shown in FIG. 4A.

The RSl UL ACK is used by RS I's one-hop subscriber stations (SS3, SS4) to feedback DL Hybrid- ARQ acknowledgements to RSl. The RS3 UL ACK is used by RS3's one-hop subscriber stations (SS7, SS8) to feedback DL Hybrid-ARQ acknowledgements to RS3.

In steps 122 and 124 the one-hop relay station (RS3) and the one-hop subscriber stations (SS5, SS6, SS8) of relay station RS2 construct and transmit the RS2 UL Zone of the UL subframe. The RS2 UL Zone is comprised of data bursts that are to be transmitted to RS2 from its one-hop relay station RS3 and its one-hop subscriber stations (SS5, SS6, SS8). Burst allocations for the RS2 UL zone are specified using information elements within the RS2 Uplink Map (UL-MAP) field.

The RS2 UL ranging subchannel is used by RS2's one-hop relay station (RS3) and its one-hop subscriber stations (SS5, SS6, SS8) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests.

The RS2 UL CQICH (channel quality indicator channel) is used by RS2's one-hop relay station (RS3) and its one-hop subscriber stations (SS5, SS6, SS8) to feedback channel-state information to RSl. Specifcally the link quality estimates RS2-RS3, RS2-SS5, RS2-SS6 and RS2-SS8 as defined in row three of the link rank matrix of FIG. 4A. The base station uses these estimates to update the link rank matrix R shown in FIG. 4A.

The RS2 UL ACK is used by RS2's one-hop relay station (RS3) and its one-hop subscriber stations (SS5, SS6, SS8) to feedback DL Hybrid-ARQ acknowledgements to RS2.

In steps 126 and 128 the one-hop relay stations (RSl, RS2) and the one-hop subscriber stations (SSl, SS2, SS3, SS6) of the base station BS construct and transmit the BS UL Zone of the UL subframe. The BS UL Zone is comprised of data bursts that are to be transmitted to the BS from its one-hop relay stations (RS l, RS2) and its one-hop subscriber stations (SS l, SS2, SS3, SS6). Burst allocations for the BS UL Zone can be specified using information elements within the BS Uplink Map (UL-MAP).

The BS UL ranging subchannel is used by the base station's one-hop relay stations (RS l, RS2) and its one-hop subscriber stations (SS l, SS2, SS3, SS6) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests. The BS UL CQICH (channel quality indicator channel) is used by the base station's one-hop relay stations (RS l, RS2) and its one-hop subscriber stations (SSl, SS2, SS3, SS6) to feedback channel-state information to the BS. Specifcally the link quality estimates BS-RS l, BS-RS2, BS-SS 1, BS-SS2, BS-SS3, and BS-SS6 as defined in row one of the link rank matrix of FIG. 4A. The base station uses these estimates to update the link rank matrix R shown in FIG. 4A. The BS UL ACK is used by the base station's one-hop relay stations (RS 1, RS2) and its one-hop subscriber stations (SS l, SS2, SS3, SS6) to feedback DL Hybrid- ARQ acknowledgements to the BS.

Frame Element Transmission for Multi-frame Relaying hi some implementations, a base station can be configured to have the option of selecting a multi-frame relaying (MFR) method. In a multi-frame relaying (MFR) method DL and UL transmissions between a BS and its subordinate relay and subscriber stations can occur using two or more frames. Relay stations in a network path can receive PDUs from their parent BS or RS and forward the PDU to their child RSs or subscriber stations using a subsequent frame or sequence of frames. FIG. 1OA and 1OB display exemplary frame structures for an MFR method. FIG. 1OC shows the resuse of time slots within an MFR method due to the spatial distribution of RS 1 and RS3.

Using an MFR method source-to-sink PDU transmission time is more compared to a single-frame relay (SFR) method but typically requires less complex hardware. A key benefit of a MFR method is that relay stations have more time to process PDUs that they receive. Signal processing can therefore be implemented in less-costly software rather than hardware. A reduction in relay station size, weight and power is more easily attainable if signal processing is implemented in software rather than dedicated hardware. Due to the added time for PDU processing, an MFR method also facilitates the implementation of more complex Decode-and-Reencode relay stations as defined above.

Mth Frame Transmission

FIG. 11 shows a flowchart of the method for dynamic frame element allocation and reuse.

FIG. 1OA and 1OB display exemplary frame structures for an MFR method. FIG. 1OC shows the reuse of time slots within an MFR method due to the spatial distribution of RS 1 and RS 3. Referring to FIG. 1OA, FIG. 1OC and to the flowchart in FIG. 11, the steps for allocation of m th frame elements for an MFR method are described below, hi this example, the steps 192, 194, 196, 198,

200, 202, 204, 206, 208, and 210 are configured to perform the same operations in steps 92, 94, 96,

98, 100, 102, 104, 106, 108 and 110 in FIG. 8, respectively. In steps 212 and 214 the one-hop subscriber stations (SSl, SS2, SS3, SS6) of the base station

BS construct and transmit the BS UL Zone of the UL subframe. The BS UL Zone is comprised of data bursts that are to be transmitted to the BS from its one-hop subscriber stations (SSl, SS2, SS3,

SS6). Burst allocations for the BS UL Zone can be specified using information elements within the

BS Uplink Map (UL-MAP). The BS UL ranging subchannel is used by the base station's one -hop subscriber stations (SS 1,

SS2, SS3, SS6) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests.

The BS UL CQICH (channel quality indicator channel) is used by the base station's one-hop subscriber stations (SS l, SS2, SS3, SS6) to feedback channel-state information to the BS. Specifcally the link quality estimates BS-SSl, BS-SS2, BS-SS3, and BS-SS6 as defined in row one of the link rank matrix of FIG. 4A. The base station uses these estimates to update the link rank matrix R shown in FIG. 4A.

The BS UL ACK is used by the base station's one-hop subscriber stations (SS l, SS2, SS3,

SS6) to feedback DL Hybrid- ARQ acknowledgements to the BS.

(M+l)th Frame Transmission

Referring to FIG. 1OB, FIG. 1OC and to the flowchart in FIG. 11, the steps for allocation of

(m+l)th frame elements for an MFR method are described below. hi steps 216 relay stations RS l and RS3 concurrently construct and transmit the RS l Preamble and the RS3 Preamble of the DL subframe. The RS 1 Preamble is a reference signal known by all network receivers. It is used by SS3 and SS4 for DL synchronization (frame timing acquisition, frequency offset estimation, symbol timing estimation) and channel estimation. SS3 and SS4 can use the RS l Preamble to obtain link quality estimates RS1-SS3 and RS1-SS4 as defined in row two of the link rank matrix of FIG. 4A. The RS3 Preamble is a reference signal known by all network receivers. It is used by SS7 and SS8 for DL synchronization (frame timing

acquisition, frequency offset estimation, symbol timing estimation) and channel estimation. SS7 and SS8 can use the RS3 Preamble to obtain link quality estimates RS3-SS7 and RS3-SS8 as defined in row four of the link rank matrix of FIG. 4A. These link quality estimates can be returned to the base station in the UL frame so the base station can update R . In steps 218 and 220 relay stations RS 1 and RS3 construct the RS 1 DL Zone and the RS3 DL

Zone of the DL subframe. Because of the spatial distribution of RS 1 and RS3 downlink zones for RSl and RS3 are transmitted concurrently using the same frame elements (see FIG. 1OC for clarification). The RS 1 DL Zone is comprised of an FCH, DL-MAP, UL-MAP and DL bursts that are to be transmitted by RSl to its one-hop subscriber stations (SS3, SS4). The RS3 DL Zone is comprised of an FCH, DL-MAP, UL-MAP and DL bursts that are to be transmitted by RS3 to its one-hop subscriber stations (SS7, SS8). For clarity these fields are not shown within FIG. 1OB. If shown they would have a similar structure to that shown for the RS2 DL Zone of FIG. 1OA. The DL and UL burst allocations for the RS 1 DL and UL Zones are specified by RS 1 using information elements (IEs) that are within the RSl Downlink Map (DL-MAP) and RSl Uplink Map (UL-MAP). The DL and UL burst allocations for the RS3 DL and UL Zones are specified by RS3 using information elements (IEs) that are within the RS3 Downlink Map (DL-MAP) and RS3 Uplink Map (UL-MAP). RS l's one-hop neighbors (SS3, SS4) receive the RS 1 DL Zone and prepare to receive DL data and transmit UL data based on frame element usage commands within their sections of the DL-MAP and UL-MAP. RS3's one-hop neighbors (SS7, SS8) receive the RS3 DL Zone and prepare to receive DL data and transmit UL data based on frame element usage commands within their sections of the DL-MAP and UL-MAP. The RSl and RS3 MAPs were originally derived by the BS according to step 198 so RS 1 and RS3 serve as a MAP forwarding nodes for the BS. hi steps 222 and 224 the one-hop subscriber stations (SS3, SS4) of relay station RSl and the one-hop subscriber stations (SS7, SS8) of RS3 concurrently construct the RSl UL Zone and the RS3 UL Zone of the UL subframe. The RS 1 UL Zone is comprised of data bursts that are to be transmitted from one-hop subscriber stations (SS3, SS4) to RS l. The RS3 UL Zone is comprised of data bursts that are to be transmitted from one-hop subscriber stations (SS7, SS8) to RS3. Because of the spatial distribution of RS 1 and RS 3 uplink zones for RS 1 and RS 3 are transmitted concurrently using the same frame elements (see FIG. 1OC for clarification). Burst allocations for the RS 1 and RS 3 UL Zones are specified using information elements within the RS 1 Uplink Map (UL-MAP) and the RS3 Uplink Map (UL-MAP) received in step 218. Information for RSI's UL-MAP are obtained from the base station via a one-hop DL burst from the BS to RSl. Information for RS3's UL-MAP are obtained from the base station via a two-hop DL burst from the BS to RS2 to RS3. The Uplink zones for RS 1 and RS3 also include an RS 1 UL Ranging Subchannel, an RS3 UL

Ranging Subchannel, an RSl UL CQICH (channel quality indicator channel), an RS3 UL CQICH, an RSl UL ACK subchannel, and an RS3 UL ACK subchannel. For clarity these fields are not shown within FIG. 1OB. If shown they would have a similar structure to that shown in the RS2 UL Zone. The RSl UL ranging subchannel is used by RSI's one-hop subscriber stations (SS3, SS4) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests. The RS3 UL ranging subchannel is used by RS3's one-hop subscriber stations (SS7, SS8) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests.

The RSl UL CQICH (channel quality indicator channel) is used by RS I's one-hop subscriber stations (SS3, SS4) to feedback channel-state information to RSl. Specifcally the link quality estimates RS1-SS3 and RS1-SS4 as defined in row two of the link rank matrix of FIG. 4A. The base station can use these estimates to update the link rank matrix R shown in FIG. 4A.

The RS3 UL CQICH (channel quality indicator channel) is used by RS3's one-hop subscriber stations (SS7, SS8) to feedback channel-state information to RS3. Specifically the link quality estimates RS3-SS7 and RS3-SS8 as defined in row four of the link rank matrix of FIG. 4A. The base station can use these estimates to update the link rank matrix R shown in FIG. 4A.

The RSl UL ACK is used by RS I's one-hop subscriber stations (SS3, SS4) to feedback DL Hybrid- ARQ acknowledgements to RSl. The RS3 UL ACK is used by RS3's one-hop subscriber stations (SS7, SS8) to feedback DL Hybrid-ARQ acknowledgements to RS3. hi steps 226 and 228 the one-hop relay station (RS3) and the one-hop subscriber stations (SS5,

SS6, SS8) of relay station RS2 construct and transmit the RS2 UL Zone of the UL subframe. The RS2 UL Zone is comprised of data bursts that are to be transmitted to RS2 from its one-hop relay station RS3 and its one-hop subscriber stations (SS5, SS6, SS8). Burst allocations for the RS2 UL zone are specified using information elements within the RS2 Uplink Map (UL-MAP) field. The RS2 UL ranging subchannel is used by RS2's one-hop relay station (RS3) and its one-hop subscriber stations (SS5, SS6, SS8) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests.

The RS2 UL CQICH (channel quality indicator channel) is used by RS2's one-hop relay station (RS3) and its one-hop subscriber stations (SS5, SS6, SS8) to feedback channel-state information to RS 1. Specifcally the link quality estimates RS2-RS3, RS2-SS5, RS2-SS6 and

RS2-SS8 as defined in row three of the link rank matrix of FIG. 4A. The base station uses these estimates to update the link rank matrix R shown in FIG. 4A.

The RS2 UL ACK is used by RS2's one-hop relay station (RS3) and its one-hop subscriber stations (SS5, SS6, SS8) to feedback DL Hybrid-ARQ acknowledgements to RS2. In steps 230 and 232 the one-hop relay stations (RSl, RS2) of the base station BS construct

and transmit the BS UL Zone of the UL subframe. The BS UL Zone is comprised of data bursts that are to be transmitted to the BS from its one-hop relay stations (RSl, RS2). Burst allocations for the BS UL Zone can be specified using information elements within the BS Uplink Map (UL-MAP).

The BS UL ranging subchannel is used by the base station's one-hop relay stations (RS l, RS2) to perform closed-loop time, frequency, and power adjustment as well as bandwidth requests.

The BS UL CQICH (channel quality indicator channel) is used by the base station's one-hop relay stations (RS l, RS2) to feedback channel-state information to the BS. Specifcally the link quality estimates BS-RS 1 and BS-RS2 as defined in row one of the link rank matrix of FIG. 4A. The base station uses these estimates to update the link rank matrix R shown in FIG. 4A. The BS UL ACK is used by the base station's one-hop relay stations (RS 1, RS2) to feedback

DL Hybrid- ARQ acknowledgements to the BS.

Hence, one method for frame element allocation and reuse within a wireless cellular network equipped with base stations, subscriber stations and relay stations for multi-hop protocol data unit (PDU) relaying can include the following. A base station (BS) is operated to obtain PDUs that are to be transmitted to subscriber stations (SSs) within its service network and to group the PDUs based on their destination SSs; the BS ranking network links in terms of a link quality metric. The BS is also opeated to rank all candidate BS-to-SS network paths based on the link quality metrics. The BS is opeated to select the optimal BS-to-SS network paths from the candidates. The BS is also operted to optimally allocate or apportion frame elements (slots, bursts, zones, subchannels, subchannel groups, and segments) that are to be used by the relay and subscriber stations within the selected BS-to-SS network paths. In this mehtod, the base station is operated to construct and transmit DL and UL MAPs specifying the frame element allocation to be used by stations within selected BS-to-SS network paths.

Based on the above described features and examples, one or more of the following implemenations may be used in various applications. In one implemneation, a base station link-quality matrix can be provided where each element in the link-quality matrix corresponds to a network link and quantifies the quality of a link connecting two BS, RS or SS network nodes. Values of zero within the link rank matrix indicate that no link exists between a network node pair; non-zero link ranks may be any radio resource measurement value or combination that indicates the quality of a network link.

In another implementation, matrix lements of the link rank matrix are updated from local link quality values or estimates performed by RSs and SSs and returned to the base station by single or multi-hop UL paths (channel quality indicator channels) to the BS.

In another implemnetation, DL Preambles or reference signals known by all receivers within the exemplary network are used by relay stations and subscriber stations for DL synchronization

(frame timing acquisition, frequency offset estimation, symbol timing estimation) and link or channel quality estimation.

In another implemenation, an appropriate link and path ranking algorithm based on values within the link rank matrix can be used in the described techniques. In yet another implementation, an m-hop link connectivity matrix can be used for the base station's service network. Elements within the link connectivity matrix quantify the number of hops of m or less for all service network nodes.

In yet another implementation, matrix elements of the link rank matrix can be used to compute the m-hop link connectivity matrix without relying on other values. In yet another implementation, a base station can be pre-configured with the m-hop link connectivity matrix. For example, if all network relay and susbscriber stations are fixed in location the base station could be pre-configured with a fixed m-hop link connectivity matrix.

In yet another implementation, a base station can be operated to acquire and update the m-hop link connectivity matrix. For example, if the network contains mobile and/or nomadic relay and subscriber stations, nodes and link connectivity can change.

In yet another implementation, a described techniques can selec single- or multi-frame allocation of frame elements, hi a single-frame allocation DL and UL transmissions between a BS and its subordinate relay and subscriber stations can occur using a single frame. In a multi-frame allocation DL and UL transmissions between a BS and its subordinate relay and subscriber stations can occur using two or more frames.

In yet another implementation, the base station frame element allocation can be made based on one or more factors: (1) link quality as indicated by elements of the link rank matrix, (2) the size of a PDU to be transmitted, and (3) the type of PDUs that an RS can support and forward to other base, subscriber and relay stations within its coverage area. In yet another implementation, a base station can be operated to optimally allocate frame elements based on the location and spatial distribution of the base station and relay and subscriber stations.

In yet another implementation, a base station can be operated to concurrently use or reuse frame elements whenever the spatial distribution of communicating network stations is such that their co-channel interference to each other is below certain reasonable levels.

In yet another implemenation, a network can be configured to include mobile and/or nomadic relay and subscriber stations and the m-hop connectivity matrix is acquired and updated at different time intervals. hi yet another implementation, the path diversity may be implemented by receiving relay and subscriber stations when duplicated frame elements are allocated for independent paths to an SS or

RS.

While this specification contains many specifics, these should not be construed as limitations on the scope of an invention or of what may be claimed, but rather as descriptions of features specific to particular embodiments of the invention. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or a variation of a subcombination.

Only a few implementations are disclosed. However, it is understood that variations and enhancements may be made.