Source: http://www.google.com/patents/US8238367?dq=6106459
Timestamp: 2014-08-30 12:52:36
Document Index: 581962994

Matched Legal Cases: ['Application No. 61', 'art 1', 'art 16', 'art 16', 'art 16', 'art 16']

Patent US8238367 - Slot allocation, user grouping, and frame partition method for H-FDD systems - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsCommunication between a base station and remote stations is partitioned into frames, each including subframes having a number of slots that are allocated based on data rates for each remote station. For communication in a half-duplex mode, multiple subframes are used, each separated by a frame partition,...http://www.google.com/patents/US8238367?utm_source=gb-gplus-sharePatent US8238367 - Slot allocation, user grouping, and frame partition method for H-FDD systemsAdvanced Patent SearchPublication numberUS8238367 B1Publication typeGrantApplication numberUS 12/388,302Publication dateAug 7, 2012Filing dateFeb 18, 2009Priority dateMar 27, 2008Also published asUS8730851Publication number12388302, 388302, US 8238367 B1, US 8238367B1, US-B1-8238367, US8238367 B1, US8238367B1InventorsJihwan P. Choi, Jungwon LeeOriginal AssigneeMarvell International Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (20), Non-Patent Citations (8), Referenced by (1), Classifications (11), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetSlot allocation, user grouping, and frame partition method for H-FDD systemsUS 8238367 B1Abstract Communication between a base station and remote stations is partitioned into frames, each including subframes having a number of slots that are allocated based on data rates for each remote station. For communication in a half-duplex mode, multiple subframes are used, each separated by a frame partition, such that a first user group of remote stations can receive down-link data in a first subframe while another user group of remote stations can transmit up-link data during that same subframe. For the next subframe, the converse happens. Slot allocation is achieved in such a half-duplex system based on weighted down-link and up-link data rates and without first or simultaneously determining user group allocation or frame partition, which are instead determined in response to the determined slot allocations for each remote station, e.g., using a linear programming technique.
n i ⁢ R i w i , where ni is the number of slots assigned to the remote station i for down-link communication in each frame, Ri is the down-link data rate per slot assigned to the remote station i for down-link communication in each frame, and wi is a down-link weighting factor assigned to the remote station i.
m i ⁢ Q i v i , where mi is the number of slots assigned to the remote station i for up-link communication in each frame, Qi is the up-link data rate per slot assigned to the remote station i for up-link communication in each frame, and vi is a up-link weighting factor assigned to the remote station i.
x = x D + x U 2 . 8. The method of claim 6, further comprising re-allocating, using the base station, the down-link slot allocation and the up-link slot allocation to each remote station in response to the determination of the frame partition and after the assignment of each remote station to one of the first user group or the second user group.
n i ⁢ R i w i , where ni is the number of slots assigned to the remote station i for down-link communications in each frame, Ri is the down-link data rate per slot assigned to the remote station i for down-link communications in each frame, and wi is the respective down-link weighting factor assigned to the remote station i.
m i ⁢ Q i v i , where mi is the number of slots assigned to the remote station i for up-link communications in each frame, Qi is the up-link data rate per slot assigned to the remote station i for up-link communications in each frame, and vi is the respective up-link weighting factor assigned to the remote station i.
x = x D + x U 2 . 24. The method of claim 14, further comprising re-assigning, using the base station, the down-link slot allocation and the up-link slot allocation to each remote station in response to the determination of the frame partition and user groupings prior to the base station communicating slot allocation data to the plurality of remote stations. Description
CROSS-REFERENCE TO RELATED APPLICATION The present application claims the benefit of U.S. Provisional Application No. 61/039,919, entitled �Joint Slot Allocation, User Grouping and Frame Partitioning for OFDMA H-FDD,� filed on Mar. 27, 2008, which is hereby incorporated by reference herein in its entirety.
FIELD OF TECHNOLOGY The present disclosure relates generally to slot-based communication schemes and devices that use them, and more particularly, to techniques for assigning users to one of a number of groups in a half-duplex, slot-based communication scheme, allocating slots in each grouping, and partitioning a frame ratio for the groupings.
DESCRIPTION OF THE RELATED ART Slot-based communication systems, such as WiMAX systems and other systems employing the IEEE 802.16 family of communication standards, typically include one or more base stations and two or more remote stations that communicate with the one or more base stations by transmitting data in a plurality of time and frequency slots. These systems use different communication schemes for up-linking data (i.e., sending from the remote stations to the base stations) and for down-linking data (i.e., sending from the base stations to the remote stations). Time division duplexing (TDD) schemes, for example, assign the same frequency slot for both up-linking And down-linking, but assign different remote stations to transmit at different time slots. Full-frequency division duplexing (F-FDD) schemes assign different frequency slots for up-linking and down-linking data and allow remote stations to communicate on both links simultaneously, i.e., on a common time slot. A hybrid-type scheme now being explored is half-frequency division duplexing (H-FDD) in which different frequency slots are assigned for down-linking and up-linking, like F-FDD, but where time slots are not shared, meaning that a remote station can only communicate on one of these two links at a given time. While some communication standards such as WiMAX Revision 1.0 only require the more traditional TDD, the desire for F-FDD/H-FDD compliant systems is increasing as a way of promoting performance flexibility and better meeting the regulatory demands of various countries where networks may be installed.
SUMMARY OF THE DISCLOSURE Embodiments described herein may be adapted for use in WiMAX systems and other slot-based communication system having at least one base station and a plurality of remote stations, wherein time and frequency resource available for communication among the at least one base station and the plurality of remote stations is partitioned into a series of frames, each frame including at least two user groups (down-link and up-link) and a total number of slots per group, where the slots may be allocated in a way that seeks to maximize system capacity, attain acceptable QoS for system users, provide fairness to users, etc.
n i ⁢ R i w i , where ni is the number of slots assigned to the remote station i for down-link communications in each frame, Ri is the down-link data rate per slot assigned to the remote station i for down-link communications in each frame, and wi is a down-link weighting factor assigned to the remote station i. The weighted up-link data rate of each remote station i is given by
m i ⁢ Q i v i , where mi is the number of slots assigned to the remote station i for up-link communications in each frame, Qi is the up-link data rate per slot assigned to the remote station i for up-link communications in each frame, and vi is a up-link weighting factor assigned to the remote station i.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 depicts a cellular communication system for duplex communication between remote stations at least one base station;
DETAILED DESCRIPTION FIG. 1 depicts an example communication system 10 in connection with which slot-allocation methods and apparatus described herein may be used. More particularly, the slot-allocation techniques may be used in cellular and other communication systems and may employ the IEEE 802.16 family of communication standards or any other slot-based communication techniques to provide for communication among one or more base stations and a plurality of remote stations, which may be either fixed (i.e., stationary) or mobile stations. The example communication system 10 illustrated in FIG. 1 includes three base stations 12, 14, 16 and three remote stations 18, 20, 22.
min i ⁢ [ min DL , UL ⁢ { n i ⁢ R i w i , m i ⁢ Q i v i } ] ( Expression ⁢ ⁢ 1 ) subject to the following constraints:
∑ i = 1 I ⁢ ⁢ n i = N ( Constraint ⁢ ⁢ 1 ) ∑ i = 1 I ⁢ ⁢ m i = M ( Constraint ⁢ ⁢ 2 ) ∑ i = 1 I ⁢ ⁢ a i ⁢ n i = xN ( Constraint ⁢ ⁢ 3 ) ∑ i = 1 I ⁢ ⁢ a i ⁢ m i = ( 1 - x ) ⁢ M ( Constraint ⁢ ⁢ 4 ) n i≧0,integer for every i (Constraint 5) m i≧0,integer for every i (Constraint 6) a i=0 or 1, for every i (Constraint 7)0≦x≦1 (Constraint 8) wi(≧0):DL weight for user i (Constraint 9) vi(≧0):UL weight for user i (Constraint 10)
n i ⁢ R i w i = ∞ . Consequently, the weighted data rate of that user cannot be a minimum of the weighted data rates among all users and thus will not bear on the maximization of that minimum.
Three types of users may be considered, by way of example. One, some users may be satisfied if all of their data is communicated at whatever minimum data rate is determined for the overall communication system 10. For these users, their corresponding communication weights may be set to zero (wi=0, vi=0). As explained above, the weighted data rate of these users will have no bearing on the maximization of the minimum weighted per-user data rate. Two, other users may require a particular minimum data rate because of QoS or other requirements. These users will have a non-zero wi and Rmin,i and a non-zero vi and Qmin,i, where the required minimum data rate Rmin,i and Qmin,i satisfy niRi>Rmin,i and miQi>Qmin,i, respectively for down-link and up-link. Three, still other users may be satisfied if all of their data is communicated on a when-possible or �best efforts� basis. For these users Rmin,i=0 and Qmin,i=0.
It should be noted that inasmuch as each remote station has weighted data rates as described above, there will be a �minimum� weighted data rate associated with each group of remote stations for down-link communications and each group of remote stations for up-link communications. These minimums are what are maximized. One or more remote stations in the group may have the minimum weighted data rate.
In Expression 1, ni and mi (the respective down-link slot allocation to each user i and the respective up-link slot allocation to each user i during a frame, respectively) are control variables. Values for ni and mi may be determined in order to maximize the minimum of the weighted data rates for the remote stations, in this example the weighted data rates for down-link and up-link communications. In other words, the slots of a group are allocated among the plurality of remote stations communicating with a base station at a given time in such a way that the weighted data rate of whichever remote station has the lowest weighted data rate among all of the remote stations (i.e., the �minimum weighted data rate�) is maximized. Thus, this solution advantageously takes account of the differing quality-of-service (QoS) requirements of all I users. These requirements may be satisfied by �best-efforts� service, where the base station provides communication to the user or remote station when it is possible to do so in light of other higher-priority communication traffic. Or, the requirements may be satisfied by having a minimum data rate requirement based on the particular type of communication being handled for that remote station. For example, video data may require a relatively high minimum data rate for acceptable quality, whereas acceptable internet browsing and other less data-intensive communication may be provided with a �best efforts� data rate.
R = min i = 1 , � ⁢ ⁢ l ⁢ n i ⁢ R i w i ( Expression ⁢ ⁢ 2 ) subject to:
n 1 *R 1 ≧w 1 *R (Constraint 11) n 2 *R 2 ≧w 2 *R (Constraint 12) n 1 *R 1 ≧R min1 (Constraint 13) n 2 *R 2 ≧R min2 (Constraint 14) n 1 +n 2 =N (Constraint 15) n 1≧0 (Constraint 16) n 2≧0 (Constraint 17)
Constraints 16 and 17 restrict the slot allocation of each user to non-negative numbers, such that the solution must be in the upper-right quadrant, as shown. Constraint 15 requires that all slots in the subframe be used (i.e., every slot must be allocated to one of the two remote stations). Constraints 11 and 12 implement the �best efforts� requirement of each of the two remote stations, with an optimal solution produced when equality holds for each of those two constraints (i.e., when n1*R1=w1*R and n2*R2=w2*R) such that the two constraints can be combined to produce a linear equation in n1 and n2, namely:
n 1 ⁢ R 1 w 1 = n 2 ⁢ R 2 w 2 ( Expression ⁢ ⁢ 3 ) This line is also shown graphically in FIG. 5 and the point of intersection is labeled.
n j = w i R j ∑ i = 1 I ⁢ ⁢ w i R i ⁢ N 1 , ⁢ j = 1 , � ⁢ , I ( Expression ⁢ ⁢ 4 ) The foregoing description provides one embodiment of a method of calculating slot allocations in a duplex communication system, such as a WiMAX H-FDD system. For simplicity of description, the numbers of slots were not constrained to be integers. However, as will be apparent to those skilled in the art, the numbers of slots ni should have integer values for all i=1, . . . , I (i.e., for all users). Therefore, after a slot allocation solution is found as described herein, any suitable post-processing algorithm may be applied to obtain an integer slot allocation solution close to the calculated optimal solution. For example, conventional integer programming, round-off, or other optimization techniques may be used.
Q = min i = 1 , � ⁢ ⁢ I ⁢ m i ⁢ Q i v i ( Expression ⁢ ⁢ 5 ) A corresponding solution to the linear programming problem for the up-link communication may be performed in the same way as for the down-link solution; and thus we only provide an example of the final solution in FIG. 6. Optimal point 256 is shown as determined for the respective up-link slot allocations, m1 and m2, for remote stations 1 and 2, respectively.
∑ i = 1 I ⁢ ⁢ a i ⁢ n i = x D ⁢ N ( Constraint ⁢ ⁢ 18 ) ∑ i = 1 I ⁢ ⁢ a i ⁢ m i = ( 1 - x U ) ⁢ M ( Constraint ⁢ ⁢ 19 ) ∑ i = 1 I ⁢ ( 1 - a i ) ⁢ n i = ( 1 - x D ) ⁢ N ( Constraint ⁢ ⁢ 20 ) ∑ i = 1 I ⁢ ( 1 - a i ) ⁢ m i = x U ⁢ M ( Constraint ⁢ ⁢ 21 ) a i=0 or 1 for every i (Constraint 22)0≦x D≦1 (Constraint 23)0≦x U≦1 (Constraint 24)
Z≦x D −x U (Constraint 22) Z≦x U −x D (Constraint 23) Z≦0 (Constraint 24)
∑ i = 1 I ⁢ ⁢ a i ⁢ n i = x D ⁢ N ( Constraint ⁢ ⁢ 25 ) ∑ i = 1 I ⁢ ⁢ a i ⁢ m i = ( 1 - x U ) ⁢ M ( Constraint ⁢ ⁢ 26 ) ∑ i = 1 I ⁢ ( 1 - a i ) ⁢ n i = ( 1 - x D ) ⁢ N ( Constraint ⁢ ⁢ 27 ) ∑ i = 1 I ⁢ ( 1 - a i ) ⁢ m i = x U ⁢ M ( Constraint ⁢ ⁢ 28 ) a i=0 or 1 for every i (Constraint 29)0≦x D≦1 (Constraint 30)0≦x U≦1 (Constraint 31)
x = x D + x U 2 ( Expression ⁢ ⁢ 8 ) With x and ai determined, the slot allocation problem of Expression 1 may be re-solved (e.g., through integer programming at block 206 of FIG. 4) for each group to obtain new sets of ni′ and mi′. Specifically for remote stations assigned to Group 1, maximization the following expression is used:
min i ∈ Group ⁢ ⁢ 1 ⁢ [ min DL , UL ⁢ { n i ′ ⁢ R i w i , m i ′ ⁢ Q i v i } ] ( Expression ⁢ ⁢ 9 ) subject to:
∑ i ∈ Group ⁢ ⁢ 1 ⁢ ⁢ n i ′ = xN ∑ i ∈ Group ⁢ ⁢ 1 ⁢ ⁢ m i ′ = ( 1 - x ) ⁢ M ni′≧0
min i ∈ Group ⁢ ⁢ 2 ⁢ [ min DL , UL ⁢ { n i ′ ⁢ R i w i , m i ′ ⁢ Q i v i } ] ( Expression ⁢ ⁢ 10 ) subject to:
∑ i ∈ Group ⁢ ⁢ 2 ⁢ ⁢ n i ′ = ( 1 - x ) ⁢ N ∑ i ∈ Group ⁢ ⁢ 2 ⁢ ⁢ m i ′ = xM ni′≧0
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5822318 *Jul 29, 1994Oct 13, 1998Qualcomm IncorporatedMethod and apparatus for controlling power in a variable rate communication systemUS7215653 *Feb 11, 2002May 8, 2007Lg Electronics Inc.Controlling data transmission rate on the reverse link for each mobile station in a dedicated mannerUS7218644 *May 29, 2002May 15, 2007Nokia CorporationDynamic bandwidth allocation for bluetooth access point connectionsUS7392054May 31, 2005Jun 24, 2008Samsung Electronics Co., Ltd.Resource allocation scheduling method for a cellular communication systemUS7423997 *Oct 4, 2005Sep 9, 2008Motorola, Inc.Group scheduling in wireless communication systemsUS7801490 *Mar 17, 2004Sep 21, 2010Hewlett-Packard CompanyInterference based scheduling using cognitive radiosUS20040097238Nov 7, 2003May 20, 2004Samsung Electronics Co., Ltd.Frequency reuse method in an orthogonal frequency division multiplex mobile communication systemUS20050053123 *Sep 2, 2004Mar 10, 2005Ntt Docomo, IncWireless communications apparatus and method using array antennaUS20050053164Jul 7, 2004Mar 10, 2005Severine CatreuxSystem and method for RF signal combining and adaptive bit loading for data rate maximization in multi-antenna communication systemsUS20050111488 *Nov 8, 2004May 26, 2005Subramanian Vijay G.Method and apparatus for resource allocation and schedulingUS20060203765 *Sep 19, 2005Sep 14, 2006Rajiv LaroiaData rate methods and apparatusUS20070248048Apr 20, 2007Oct 25, 2007Fujitsu LimitedProportional fair scheduler for OFDMA wireless systems with QOS constraintsUS20080075032Sep 22, 2006Mar 27, 2008Krishna BalachandranMethod of resource allocation in a wireless communication systemUS20080123569 *Nov 28, 2006May 29, 2008Motorola, Inc.Intelligent scheduling in a time division duplexing system to mitigate near/far interference scenariosUS20080159417Dec 27, 2006Jul 3, 2008Hujun YinBase station and method for mitigating interference in a sectorized communication networkUS20080232341Mar 19, 2007Sep 25, 2008Lucent Technologies Inc.Scheduling for multi-carrier wireless data systemsUS20080299981 *May 31, 2007Dec 4, 2008Foschini Gerard JMethod of coordinated wireless downlink transmissionUS20090046606 *Jul 1, 2005Feb 19, 2009Lei WanAdaptive Frame Structure for TDD Point-to-Point Wireless TransmissionUS20090092067 *Oct 7, 2007Apr 9, 2009Motorola IncFlexible frame structure in wireless communication systemEP1718002A1 *Apr 29, 2005Nov 2, 2006Siemens S.p.A.User selection method and device for data packet services in wireless communication systems* Cited by examinerNon-Patent CitationsReference1"Mobile WiMAX-Part 1: A Technical Overview and Performance Evaluation," WiMax Form, Aug. 2006.2IEEE P802.16Rev2/D5 (Jun. 2008) (Revision of IEEE Std 802.16-2004 and consolidates material from IEEE Std 802.16e-2005, IEEE Std 802.16-2004/Cor1-2005, IEEE Std 802.16f-2005 and IEEE Std 802.16g-2007) "Draft Standard for Local and metropolitan area networks: Part 16: Air Interface for Broadband Wireless Access Systems," The Institute of Electrical and Electronics Engineers, Inc., Jun. 2008.3IEEE Std 802.16-2004 (Revision of IEEE Std 802.16/2001), "IEEE Standard for Local and metropolitan area networks; Part 16: Air Interface for Fixed Broadband Wireless Access Systems," The Institute of Electrical and Electronics Engineers, Inc., Oct. 1, 2004; 893 pages.4IEEE Std 802.16a-2003 (Amendment to IEEE Std 802.16-2001) "IEEE Standard for Local and metropolitan area networks: Part 16: Air Interface for Fixed Broadband Wireless Access Systems-Amendment 2: Medium Access Control Modifications and Additional Physical Layer Specifications for 2-11 GHZ," The Institute of Electrical and Electronics Engineers, Inc., Apr. 1, 2003.5IEEE Std 802.16e-2005 and IEEE Std 802.16-2004/Cor1-2005 (Amendment and Corrigendum to IEEE Std 802.16-2004), IEEE Standard for Local and metropolitan area networks: Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems: Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1, The Institute of Electrical and Electronics Engineers, Inc., Feb. 28, 2006.6Non-Final Office Action for U.S. Appl. No. 12/118,525, dated Apr. 4, 2011.7U.S. Appl. No. 12/118,525, filed May 9, 2008, entitled "Slot Allocation Method and Apparatus for Slot-Based Communication" (unpublished).8Wong, C.Y. "Multiuser OFMD with Adaptive Subcarrier, Bit, and Power Allocation," IEEE Journal on Selected Areas in Communications, vol. 17, No. 10 pp. 1747-1758 (Oct. 1999).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS20100309788 *Jun 7, 2010Dec 9, 2010Qualcomm IncorporatedSystems and methods to provide flow control for mobile devices* Cited by examinerClassifications U.S. Classification370/468, 370/235International ClassificationH04J3/16Cooperative ClassificationH04L5/16, H04L5/0037, H04L5/0007, H04L5/0064European ClassificationH04L5/00A2A1, H04L5/16, H04L5/00C2, H04L5/00C7CLegal EventsDateCodeEventDescriptionFeb 18, 2009ASAssignmentEffective date: 20090218Owner name: MARVELL INTERNATIONAL LTD., BERMUDAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MARVELL SEMICONDUCTOR, INC.;REEL/FRAME:022278/0012Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CHOI, JIHWAN P.;LEE, JUNGWON;REEL/FRAME:022276/0949Effective date: 20090217Owner name: MARVELL SEMICONDUCTOR, INC., CALIFORNIARotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google