Down-link transmission inter-cell scheduling in CDMA data networks

[0002] This application is related to U.S. patent application filed Dec. 3, 1999 the teachings of which are incorporated herein by reference.

[0003] 1. Field of the Invention

[0004] The present invention relates to code division, multiple access (CDMA) telecommunication systems, and, more particularly, to scheduling downlink data transmission from a base station to users.

[0005] 2. Description of the Related Art

[0006] Mobile cellular or wireless systems of the prior art generally have limited capabilities for transmission of data signals (data transmission) between a base station and remote users in comparison with transmission of voice or voiceband data signals. For some code division, multiple-access (CDMA) communication systems, such as those systems presently operating in accordance with the IS-95 standard, transmission of data traffic to and from users may only have a data rate of approximately 10 kbits/s. This data rate may typically be too low to satisfy delay requirements of many data applications, including connections between a remote user and the Internet or for file transfer to/from the remote user. When a large number of voice users are supported, user connections of the cellular or wireless network may be relatively easy to manage using statistical averaging. However, statistical averaging techniques may no longer be valid when a few users having high data rate traffic are admitted into the network.

[0007] Modifying resource management of existing CDMA telecommunication systems may allow a network to admit users having high data rate traffic. Resource management primarily includes schedule time, transmit power, and data rate. One approach to resource management in such CDMA networks schedules the transmission of data traffic from users to the base station (i.e., transmissions in the up-link channel) in a manner to avoid interference between user signals. Increasing the transmission rate while avoiding interference from other users compensates for a reduction in available transmission time.

[0008] FIG. 1 shows CDMA telecommunication system cell 100 comprising a base station 101 and voice and data users. Cell 100 operates in accordance with prior art methods of resource management. Base station 101 is in communication with transceivers of voice users x_V1and x_V2and data users X_D1through x_D3. Base station 101 has maximum transmission power P_maxavailable for transmission from the base station 101 to users in a down-link channel. To maintain a rate and minimum bit error rate (BER), the base station 101 communicates with data users x_D1through x_D3during a time period with a certain data rate and transmit power level.

[0009] For the up-link channel, methods of the prior art may use common CDMA techniques, such as overlapping techniques (simultaneous transmission of spread signals within the same frequency band during the same time) that allow users to transmit signals to the base station 101. For both up-link and down-link channels, a BS 101 of the prior art may employ overlapping techniques for transmission of data as shown in FIG. 2. During time span Δt, the base station 101 apportions fractions φ_D1through φ_D3of the total transmit power P_Dto user transceivers x_D1through x_D3. Consequently, each user receives interference noise from other users with transmissions occupying the same frequency band during the time span Δt. While providing continuous transmission of data, the overall throughput of a cell may be reduced because of the lower signal to interference noise level.

[0010] Also, methods may schedule each voice and data signal transmission between users and a base station to reduce interference noise, and these methods may employ non-overlapping scheduling techniques (i.e., spread user signals within a frequency band are transmitted either one-at-a-time, or in small, simultaneous groups). This method is used by a base station to coordinate many signals transmitted between the base station and users, which signals may experience varying forms of delay during transmission. Methods of scheduling signal transmission generally apply one or more criteria to determine which particular user signal should be transmitted. However, voice/voiceband data signals are delay non-tolerant, as opposed to data signals which are generally delay-tolerant, and as such voice signals may be adversely affected by delay caused by scheduling methods. Consequently, scheduling methods may divide user signal transmission into one or more classes depending on whether the spread signals are delay tolerant or delay intolerant.

[0011] A method of intra-cell scheduling of the prior art is described in J. M. Holtzman and S. Ramakrishna, A Scheme for Throughput Maximization in a Dual-Class CDMA System, I.E.E.E. Journal on Selected Areas of Communications, 40(2):830-841, 1998. For this method, the base station schedules user transmissions in the up-link since the overlapping, asynchronous transmissions contribute significant noise to one another since the spreading codes are not aligned. Such scheduling may be employed to improve gain (SNR) in the up-link by reducing high interference noise power from non-zero partial cross-correlation of the transmitted signals. Another prior art intra-cell scheduling method may allocate transmission slots in the down-link for signal transmission from the base station to users using signal-to-noise (SNR) measurements and/or fading predictions. A user measures the SNR value of the signal received at the user transceiver and transmits the SNR value back to the base station. The base station then allocates the transmission slot based onmaximizing the SNR while providing the minimum transmission delay for all users. Such scheduling methods base such allocation on various throughput criteria of the cell, and these systems may be characterized by low user speed and are generally designed for data-only (delay-tolerant user) transmission.

[0012] The present invention relates to allocating a transmission time interval to a corresponding user, for transmission of a spread data signal to the user by a given base station of a given cell in a network of cells. A set of interference patterns is defined for the given cell related to signal transmission characteristics between the corresponding user and one or more base stations of thenetwork of cells, each cell of the network of cells having users and a base station capable of transmitting one or more spread data signals to such users. In accordance with an optimizing criterion, a linear programming problem defined by (i) the set of interference patterns and (ii) a set of constraints for allocated time intervals based on the set of interference patterns is solved to determine the time interval to be allocated. Responsive to the solution of the linear programming problem, a recurrent time interval is allocated to each user for the given base station to transmit therewithin spread data signals to the corresponding user, such that the recurrent time interval overlaps no time interval allocated to any other individual user belonging to the given cell.

[0013] For some embodiments of the present invention, a recurrent time interval for base station transmissions is allocated to each of a group of two or more users belonging to the given cell. At least one spread data signal is transmitted, at a transmit power, from the given base station to each user of said group, such that the given base station transmits to only one member of the group at a time. Some embodiments of the present invention may determine the time intervals and transmit powers allocated to spread data signals based on either minimum average rates, an optimization criterion such as relative maximum throughput, or signal-to-interference noise measurements by users. According to other embodiments of the present invention, users having delay-intolerant spread signals may be allocated corresponding time intervals that may overlap time intervals of transmitted spread data signals. For other embodiments of the present invention may allocate a common time interval to a set of users during which the spread signals are transmitted in time intervals that may overlap one-another, and the spread data signals of another set of users are transmitted in corresponding time intervals that are disjoint.

[0014] Other aspects, features, and advantages of the present invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which:

[0015] FIG. 1 shows a base station, voice users, and data users of a CDMA telecommunication system cell employing methods of resource management of the prior art;

[0016] FIG. 2 shows base station transmit power to users versus frequency with a scheduling method of the prior art that uses stacked interference of user power;

[0017] FIG. 3 shows a base station and voice and data users of a CDMA telecommunication system cell employing scheduling in accordance with embodiments of the present invention;

[0018] FIG. 4 shows base station transmit power to a user during a time window for the network of FIG. 3 employing an exemplary embodiment of the present invention;

[0019] FIG. 5 shows base station transmit power to users versus time with the scheduling method of the present invention of FIG. 4 transmitting signals in the down-linkchannel one-at-a-time;

[0020] FIG. 6A shows a linear network of adjacent base stations operating in L-time;

[0021] FIG. 6B shows a linear network of adjacent base stations operating in R-time;

[0022] FIG. 6C shows a linear network of adjacent base stations operating in 0-time;

[0023] FIG. 6D shows a linear network of adjacent base stations operating in 2-time;

[0024] FIG. 7 is a flow chart of the method of determining scheduling using a linear programming model; and

[0025] FIG. 8 is a graph of throughput versus fraction of users transmitting of simulations for a telecommunication system employing a hybrid CDMA/time-sharing method of scheduling.

[0026] In accordance with the present invention, a code division, multiple access (CDMA) telecommunications system employs scheduling of data transmission to user transceivers in down-link channels of a data network. Scheduling data transmission in the down-link to users may follow the constraints that 1) each base station transmits to data (or delay tolerant) user transceivers one at a time (for voice and data networks), and 2) the base station uses full available power when transmitting (for data networks only). A linear programming problem may be formed given i) a set of users of a data network; ii) transmission of spread data signalsto users in a cell one-at-a-time and with full power; iii) the network configuration for interference to one cell by other cells; and iv) the user data rates. The linear programming problem may be solved to find scheduling that is optimized in the sense that it maximizes or minimizes objective functions sensitive to predefined criteria such as maximum throughput. In addition, the present method may be employed in a hybrid CDMA/time-share system to reduce power of data channels in communication with user transceivers that are near the base station. Such hybrid CDMA/time-share systems may employ scheduling for transmission of spread data signals during corresponding disjoint time intervals for users nearer the outside of the cell, and overlapping transmission of spread data signals (i.e., overlapping noise power) for users near the base station of the cell.

[0027] For the following exemplary embodiments, networks with data signals are described. However, as would be apparent to one skilled in the art, the exemplary embodiments described herein may be extended to networks having both delay-intolerant signals (e.g., voice and voiceband data users) and delay-tolerant signals (data signals). Each data user may have a minimum data rate requirement that is desirably satisfied. A continuum of data rates may be achieved, although, as would be apparent to those skilled in the art, the present exemplary embodiments may be extended to systems supporting discrete data rates. Data rates may be determined by employing a Gaussian interference model for the signal to interference ratio (S/I), and the desired maximum bit-error rate value for a user is satisfied provided his S/I is greater than a corresponding threshold. Systems operating in accordance with the present invention may employ relatively long term SNR measurements by the base station and/or user transceiver, may be characterized by relatively high data speed, and may integrate both delay tolerant (e.g., data) and delay-intolerant (e.g., voice) transmission when power limits are employed for data users.

[0028] FIG. 3 shows a base station (BS) 401 and data users x_D1through x_DNof a CDMA telecommunication system cell 400 employing scheduling in accordance with embodiments of the present invention. CDMA telecommunication system cell 400 may be the k^thcell, denoted E_k, of a network having many cells and where k is an integer greater than 0. In the k^thcell E_kare N^kdata users, N an integer, and base station 401 is in communication over a down-link channel with N^kdata user transceivers x_D1through x_DN. Base station 401 has maximum transmission power P_maxavailable, and communicates with data users x_D1through x_D3during a series of discrete time intervals Δt.

[0029] The value W is defined as the bandwidth available for transmission of data by the i^thdata user (i.e., x_Di) and the value R is the data rate available to the i^thdata user x_Di. Defining P as the power received by the transceiver of the i^thdata user from the BS 401 and defining I as the interference noise power, the energy-per-bit to noise-density ratio (E_b/N_o) may be as defined in equation (1): $\begin{array}{cc}\frac{E_b}{N_o}=\frac{\mathrm{WP}}{\mathrm{RI}}.& \left(1\right)\end{array}$

[0030] The i^thdata user decodes data of the down-link transmission from the BS 401 with a threshold error probability value ε. If the BS 401 decodes (demodulates) with threshold error probability value ε, then E_b/N_o≧γ, where γ is some threshold determined from ε (i.e., γ=f(ε)), and is employed below to denote the E_b/N_ovalue. Although the following uses a E_b/N_ovalue common to all users, the present invention is not so limited and one skilled in the art may adapt the teachings herein to include varying E_b/N_ovalues for the different types of user data signals. For a given received power P, the maximum data rate {overscore (R)} that may be achieved by the i^thdata user is given in equation (2): $\begin{array}{cc}\stackrel{\_}{R}=\frac{\mathrm{WP}}{\gamma I}& \left(2\right)\end{array}$

[0031] The maximum available transmit power for the BS 401 in cell E_kis defined as P_T^k. At a given time t, P^kis defined as the power at which BS 401 in cell E_kis transmitting. The value φ_iis defined as the fraction of power P^kthat the BS 401 is transmitting to the i^thdata user in cell E_k, and that the sum of the fractions of power is 1 $\left(i.e.,\sum _{i=1}^{N^k}{\phi }_i=1\right).$

[0032] For cell E_k, the set B(k) is defined as the set of cells with corresponding base stations that provide noise interference to the cell E_k. Typically, the set B(k) includes those cells that are adjacent to cell E_k. Defining G_i^mas the path loss of an interference transmission from the base station in E_mto the i^thdata user in cell E_k, the interference noise provided to the i^thdata user in cell E_kby the base station transmissions of cell E_kto other users in the cell is defined as (1−φ_i)P^kG_i^kf_i. The value f_iis an orthogonality factor representing a fraction of power transmitted to other users in the cell that appears as interference to the i^thdata user in cell E_k.

[0033] If BS 401 employs a set of orthogonal codes during the spreading operation to distinguish signals transmitted to distinct users, then intra-cell interference may be relatively small, such as when the channel is a Gaussian channel (i.e., f_i=0). However, when the transmission channel includes effects of multi-path intersymbol interference such that f_i>0, The total external interference power I_iexperienced by the i^thuser in cell E_kby transmissions provided by base stations in other cells is given by equation (3): $\begin{array}{cc}{I}_i=\sum _{n\epsilon B\left(k\right)}{G}_i^m{P}^m& \left(3\right)\end{array}$

[0034] Using equations (1) through (3), the data rate {overscore (R)} that the i^thuser in cell E_kreceives at time t is given by equation (4): $\begin{array}{cc}\stackrel{\_}{R}=\left(\frac{W}{\gamma }\right)\frac{{\phi }_i{P}^k{G}_i^k}{I_i+\left(1-{\phi }_i\right)P^k{G}_i^k{f}_i+\eta }& \left(4\right)\end{array}$

[0035] where the value η is the background noise power.

[0036] Described first is an intra-cell scheduling method is employed by the BS 401. When BS 401 transmits data in the down-link channel with total available power P_maxto the i^thdata user, the base station 401 may only transmit to each user for a time interval equivalent to a fraction of a duty cycle. Consequently, the ith user is allocated a time interval a_iΔt in which the base, station enables transmission of the corresponding spread data signal to the user during the allocated time interval. The duty cycle Δt is the maximum duration of time between successive time intervals of a user for two enabled transmissions of the corresponding spread data signal by the base station.

[0037] As described herein, the fraction a_imay be equivalent to the fraction of total power that the base station would apportion to transmit to a data user under the scheme as shown in FIG. 2. FIG. 4 shows transmit power P_Dof a single spread data signal to a user during one duty cycle for the network of FIG. 3 employing an exemplary embodiment of the present invention. FIG. 5 shows base station transmit power to multiple users in scheduled time intervals during the duty cycle with the scheduling method of FIG. 4. The base station 401 selects each user time interval for transmission of the corresponding data signal and transmits signals with power P_Dto transceivers of data users x_D1through x_DN. The advantage of intra-cell scheduling in accordance with the present invention may be shown with the ratio of the average throughputs of the intra-cell scheduling and overlapping being greater than 1.

[0038] For the CDMA systems of the prior art, such as those conforming to the IS-95 standard, spread data signals that overlap in time may typically be employed for transmission to data users over the down-link channel. For such systems, a fraction a_iof the current total transmit power P_maxis allocated to the i^thdata user. Then the maximum data rate for prior art resource allocation of CDMA systems ({overscore (R)}_i^CMDA) the i^thdata user may receive is similar to equation (4) with φ_ireplaced by a_iand is given in equation (4′) $\begin{array}{cc}{\stackrel{\_}{R}}_i^{\left(\mathrm{CDMA}\right)}=\left(\frac{W}{\gamma }\right)\frac{{\alpha }_i{P}^k{G}_i^k}{I_i+\left(1-a_i\right)P^k{G}_i^k{f}_i+\eta }& \left(4^{\prime }\right)\end{array}$

[0039] Equation (5) gives the maximum data rate, which may also be defined as the throughput per unit time of the i^thdata user using CDMA systems such as that conforming to the IS-95 standard, since the data rate {overscore (R)}_i^(CDMA)remains relatively constant.

[0040] For the exemplary embodiments of the present invention, no signal is transmitted to other data users in the cell during the time interval a_iΔt that the BS 401 transmits to the i^thdata user. Therefore, the i^thdata user receives no interference noise power from other users in the cell. Since BS 401 still uses the same total power P_maxfor the users at any instant, the users in neighboring cells do not notice any change in their interference power. Given the intra-cell scheduling method, the rate received by the i^thdata user with intra-cell scheduling is given in equation (5) (derived from equation (4) with a_i=φ_i=1): $\begin{array}{cc}{\stackrel{\_}{R}}_i^{\left(\mathrm{Intra}\right)}=\left(\frac{W}{\gamma }\right)\frac{P^k{G}_i^k}{I_{\mathrm{ik}}+\eta }& \left(5\right)\end{array}$

[0041] Hence the total throughput received by the i^thdata user in unit time is a _i{overscore (R)}_i(Intra). The ratio T_Intra/T_CDMAof the average throughputs received by the i^thdata user in the intra-cell method (equation (5)) to throughput of the CDMA system of the prior art (equation (4′)) is given in equation (6): $\begin{array}{cc}{T}_{\mathrm{Intra}}/T_{\mathrm{CDMA}}=1+\frac{\left(1-a_i\right)P^k{G}_i^k{f}_i}{I_{\mathrm{ik}}+\eta }& \left(6\right)\end{array}$

[0042] Equation (6) shows that for delay-tolerant users and for CDMA telecommunication systems having non-zero orthogonality factors f_i, a base station transmitting to one data user at a time yields an improvement in average data rate and throughput over transmitting to users using the method of overlapping spread signals. If f_iis 0, then the average throughput of the CDMA systems may be equivalent to the average throughput of intra-cell scheduling in accordance with the present invention.

[0043] As shown in FIG. 4, for the intra-cell scheduling method in accordance with the present invention with systems having receivers that generate relatively minimum self-noise, the BS 401 desirably transmits to the i^thdata user with relatively maximum available power P_max(=P_T^k). By “relatively maximum” available power is meant more than half the total power available for downlink transmission, and preferably more than 90% thereof. This value P_T^kfor the level of power of the BS 401 may optimize the data rate and throughput per unit time for users of the cell, and this property is now shown. BS 401 of cell E_ktransmits at some intermediate power P^k, 0<P^k<P_T^kfor a period of time and the power transmitted by every BS to each of its users is constant over the time period. Using equation (5), the average data rate over the time period with a_ik=φ_ik=1 is given in equation (7): $\begin{array}{cc}{\stackrel{\_}{R}}_{\mathrm{ik}}=\left(\frac{W}{\gamma }\right)\frac{P^k{G}_{\mathrm{ik}}^k}{I_{\mathrm{ik}}+\eta },\mathrm{and}{I}_{\mathrm{ik}}=\sum _{m\epsilon B\left(k\right)}{P}^m{G}_{\mathrm{ik}}^m& \left(7\right)\end{array}$

[0044] where I_ikis the external interference noise power of other cells provided to cell E_k.

[0045] If the intra-cell scheduling method is employed, full power P_T^kis allocated to a user i (the i^thdata user) instead of using transmit power P^k. BS 401 of cell E_ktransmits to one user i_kfor a proportion (P^k/P_T^k) of the time and at minimal power otherwise. Consequently, the average power for a cell remains constant. Then user i_kmaintains the same average rate over that period because the average power and interference power received does not change, whereas all other users receive the same interference power and may now increase their average rates to R_ik. The average rates R_ikincrease to a value greater than the rate {overscore (R)}_ikof equation (7) because of the convexity of the interference of equation (7) for each P^m, m εB(k).

[0046] Given the exemplary intra-cell scheduling method described with respect to FIGS. 4 and 5, scheduling in accordance with the present invention for multiple cells (inter-cell scheduling) is now described. For exemplary implementations and networks in accordance with the present invention, a base station schedules data transmission to data users of a data network with multiple cells. Base stations that schedule transmission are preferably synchronized with each other or with a centralized time base. Scheduling may be related to two parameters for given user data requirements (e.g., BER) and time period. The first parameter is the rate. The rate is the instant number of bits or symbols per unit time transmitted through the channel for a user; and this value of rate may change based on power and location, where the latter determines the signal to noise ratio. The “noise” in the signal to noise ratio is typically the sum of external noise and base-station interference. The second parameter is the throughput. The throughput is the average rate times the duty cycle. The duty cycle is the duty cycle of each cell, assuming intra-cell scheduling in accordance with the present invention is used (i.e., the signal “on” and “off” time intervals of a duty cycle are set, such as shown in FIGS. 4 and 5).

[0047] An exemplary implementation of a data network includes a linear array of cells with an arbitrary distribution of users in each cell. Such a data network is shown in FIGS. 6A through 6D. Each base station E_kinterferes with user signals of its two neighboring cells E_k−1 and E_k+1. Using inter-cell scheduling in accordance with the present invention, each base station has on and off periods during which the total transmit power is P_T^kand 0, respectively. When the base station of cell E_kis transmitting to the i^thdata user, the average rate received by the i^thdata user is given in equation (8): $\begin{array}{cc}{\stackrel{\_}{R}}_{\mathrm{ik}}=\left(\frac{W}{\gamma }\right)\frac{P_T^k{G}_i^k}{{\delta }_{k-1}{P}_T^{k-1}{G}_i^{k-1}+{\delta }_{k+1}{P}_T^{k+1}{G}_i^{k+1}+\eta }& \left(8\right)\end{array}$

[0048] where δ_j(j=k,k−1,k+1) is 1 if the base station of cell E_jis on (transmitting) and 0 otherwise. The scheduling time interval may be common to all base stations and may be of unit length. The fraction that the base station of cell E_kis on (transmitting) in the scheduling time interval may be referred to as the duty cycle of the cell.

[0049] FIG. 6A shows a linear network of adjacent base stations operating in L-time. The L-time of a cell is defined as the time during which only its left neighboring base station is on. FIG. 6B shows a linear network of adjacent base stations operating in R-time in which only the right neighboring base station transmits over the down-link to a user. Similarly defined are the cell E_k's 0-time and 2-time (i.e, the periods in which the neighboring base stations either don't transmit at all or both neighboring base stations are transmitting to their corresponding users, respectively) as illustrated in FIGS. 6C and 6D.

[0050] If the BS in E₀transmits to the ith data user, the power received by that user from its own BS is P_i, is P_T⁰G_i⁰. In addition, the left interference power (P_li) received by the i^thdata user in cell E₀from the base station of E₋₁whenever the BS of E₋₁is transmitting is P_T⁽⁻¹⁾G_i⁽⁻¹⁾. In a similar manner the right interference power (P_ri) whenever the BS of E₁is transmitting is P_T¹G_i¹. The fractions of the total time that the i^thdata user in cell E₀receives transmission from its own BS in L-time and R-time are defined as τ_liand τ_ri, respectively. Similarly, the fraction of the total time that the i^thdata user in cell E₀receives transmission from its own BS as well as transmissions from both the BSs of E₋₁and E₁is defined as τ_2i. The fraction of the total time that the i^thdata user in cell E₀receives transmission from its own BS and neither of the BSs of E₋₁and E₁is defined as τ_oi. The value τ₁²is the total of all fractions in L-time of the cell E_kand is defined as Σ_iεEτ_li. The values τ_r^k, τ_o^kand τ₂²for the total of all fractions in R-time, 0-time, and 2-time may be similarly defined.

[0051] During 2-time, the power of signals transmitted from BSs in both cells E₋₁and E₁interfere with the signal transmitted to the i^thdata user in cell E₀. Given the previous definitions and equation (7), the normalized rate R_2ithe i^thdata user in cell E₀receives during 2-time may be as given by equation (9): $\begin{array}{cc}{R}_{2i}=\frac{\gamma {\stackrel{\_}{R}}_{2i}}{W}=\frac{P_i}{P_{\mathrm{li}}+P_{\mathrm{ri}}+\eta }=\frac{P_i}{\eta \left(1+{\beta }_{\mathrm{li}}+{\beta }_{\mathrm{ri}}\right)},& \left(9\right)\end{array}$

[0052] with the normalization β_li=P_li/η, β_ri=P_ri/η.

[0053] Similar equations may be derived for normalized rates that may be available to the i^thdata user in cell E₀during R-time, L-time, and 0-time. The normalized throughput T_iper unit time obtained by the i^thdata user in cell E₀may be as given in equation (10): $\begin{array}{cc}{T}_i=\frac{{\tau }_{0i}{P}_i}{\eta }+\frac{{\tau }_{\mathrm{li}}{P}_i}{\eta \left(1+{\beta }_{\mathrm{li}}\right)}+\frac{{\tau }_{\mathrm{ri}}{P}_i}{\eta \left(1+{\beta }_{\mathrm{ri}}\right)}+\frac{{\tau }_{2i}{P}_i}{\eta \left(1+{\beta }_{\mathrm{li}}+{\beta }_{\mathrm{ri}}\right)}& \left(10\right)\end{array}$

[0054] As shown in equation (10), the schedule of transmissions for each user in the network may be expressed using values for portions (τ_li, τ_ri, τ_0i, τ_2i) of the total time period allocation τ, where τ={(τ_li, τ_ri, τ_0i, τ_2i)iεE_k,kεZ}, where Z is the set of cells in the network. Solutions for the schedule may be found by forming a linear programming problem for the network, and then solving the linear programming problem.

[0055] For example, a linear cluster of cells is defined as the set S and is formed from the set Z of all cells in the linear network (i.e., S⊂Z). The space F_Sis defined as the feasible space of time allocations for users in the subset S, and the value A_iis defined as the minimum throughput value for the i^thdata user. The following values are defined: The total transmit time period allocation τ₁^k,onis defined as the time period that the base station E_kis on (transmitting to the users) in L-time, and τ_r^k,on, τ₀^k,on, and τ₂^k,onare similarly defined for R-time, 0-time, and 2-time, respectively. The total transmit time period allocation τ_l^k,off, is defined as the time period that the base station E_kis off (not transmitting) in L-time, and τ_r^k,off, τ₀^k,off, and τ₂^k,offare similarly defined for R-time, 0-time, and 2-time, respectively.

[0056] Given these defined values, the time period allocations may satisfy the constraints given in equations (11a) through (11f). First, a total time allocation $\begin{array}{cc}{\tau }_l^{k,on}=\sum _{i=1}^{N_k}{\tau }_{\mathrm{li}}^{k,\mathrm{on}}& \text{(11a)}\end{array}$

[0057] where N_kis the number of user in cell E_k. Similar identity relations hold for τ_r^k,on, τ₀^k,on, and τ₂^k,on. Equation (11b) yields the identity for the conservation of time for the duty cycle:

[0058] τ_l^k,on+τ_r^k,on+τ₀^k,on+τ₂^k,on+τ_r^k,off+τ₀^k,off+τ₂^k,off=1,  (11b)

[0059] given that the total normalized time period for a duty cycle is 1.

[0060] The base station of cell E_kis off with 0- or L-time, and the base station of cell E_k+1is off with 0- or R-time, when the base stations of both cells E_kand E_k+1are off, which yields the identity given in equation (11c):

[0061] τ₀^k,off+τ_l^k,off=τ₀^k+1,off+τ_r^k+1,off  (11c)

[0062] The base station of cell E_kis off with R- or 2-time, and the base station of cell E_k+1is on with 0- or R-time, when the base station of cell E_kis off and the base station of cell E_k+1is on, yielding the identity of equation (11d):

[0063] τ_r^k,off+τ₀^k,off=τ₀^k+1,on+τ_r^k+1,on  (11d)

[0064] The base station of cell E_kis on with 0- or L-time, and the base station of cell E_k+1is off with L- or 2-time, when the base station of cell E_kis on and the base station of cell E_k+1is off, yielding the identity given in equation (11e):

[0065] τ₀^k,on+τ_l^k,on=τ_l^k+1,off+τ₂^k+1,on  (11e)

[0066] The base station of cell E_kis on with R- or 2-time, and the base station of cell E_k+1is on with L-or 2-time, when both the base stations of cells E_kand E_k+1are on, yielding the identity given in equation (11f):

[0067] τ_r^k,on+τ₂^k,on=τ_l^k+1,on+τ₂^k+1,on  (11f)

[0068] Satisfying time period allocations for the duty cycle as given by equations (11a) through (11f) provides for feasible time period allocations for transmitting signals to the data users of cell E_kin a linear network. If equations (11a) through (11f) hold, the schedule is feasible. Otherwise, it is not feasible. Appendix A shows that if these equations hold, a schedule can be constructed.

[0069] Given these definitions, the scheduling of user transmissions may have objective functions such as a maximizeable total throughput, thus leading to a feasible time-period allocation. Consequently, an exemplary linear programming problem may be formed from equation (10), with appropriate constraints and objective functions optimizeable for a relative maximum total throughput of equation (12). Equations (11a) through (11f) define a set of constraints appropriate when the network is a linear network. Thus, an illustrative linear programming problem is expressed by: $\begin{array}{cc}\max \sum _{j\in S}\sum _{i\in E_j}{T}_i,\mathrm{with}{T}_i\ge A_i,i\in \bigcup _{j\in S}{E}_j& \left(12\right)\end{array}$

[0070] where the term “max” indicates the mathematical maximum. As would be apparent to one skilled in the art, forms of optimization criteria other than that shown in equation (12) may be employed.

[0071] For an exemplary symmetric network, the time period allocations for all users may be equivalent within each cell. Consequently, the time period allocation values may be simplified to τ_li^k=τ_li;=τ_ri; τ_2i^k=τ_2i; and τ_0i^k=r for all k. In addition, the “on” and “off” periods may be simplified to τ_l^k,on=τ_l^on; τ_r^k,on=τ_r^on; τ₂^2k,on=τ₂^on; and τ₀^k,on=τ₀^on. In such symmetric network and given simplifications to the time period allocation values, the constraints of equations (11a) through (11f) may be reduced to the constraints given in equations (13) and (14) (where the superscript “on” dropped for clarity):

[0072] $\begin{array}{cc}{\tau }_0=\sum _{i=1}^{N_k}{\tau }_{0i};{\tau }_l=\sum _{i=1}^{N_k}{\tau }_{\mathrm{li}};{\tau }_r=\sum _{i=1}^{N_k}{\tau }_{\mathrm{ri}};{\tau }_2=\sum _{i=1}^{N_k}{\tau }_{2i}& \left(13\right)\end{array}$  2τ₀+3τ₁+τ₂=1  (14)

[0073] from which the optimality constraint of equation (15) may be derived:

[0074] If β_li+β_ri<1, then τ_0i=0; and if β_li+β_ri>1, then τ_2i=0  (15)

[0075] FIG. 7 is a flow chart of the method of determining scheduling of signals to users in a cell E₀using a linear programming problem. First, at step 701 the expressions for normalized rates are determined for each of the combinations of cell interference of the network. For example, expressions for normalized rates such as given in equation (9) may be determined in the linear network of FIGS. 6A-6D for 0-, 2-, L-, and R-time.

[0076] At step 702, the constraints are set for time allocation, such as the constraints given for the linear network of equation (11). At step 703, the normalized rates are employed to determine the expression for normalized throughput of a cell, such as the expression given in equation (10). At step 704 the constraints are set so as to ensure feasibility of the time allocations, and an optimization criterion, such as the maximized throughput is selected (such as given in equation (12)).

[0077] At step 705, a linear programming problem is formed using the expressions determined in steps 701 and 702, and the constraints as set in steps 703 and 704. At step 706 the solution to the linear programming problem of step 705 is generated. As would be apparent to one skilled in the art, network configuration, additional constraints, or other factors may be added in steps 705 and 706 to convert the linear programming problem into an integer programming problem. For either linear or integer programming problems, techniques for solving such problems are well known in the art. The solution generated in step 706 is applied at step 707. The solution, i.e., the output of the linear program, includes a complete transmission schedule for all the base stations in the network. Thus, the rate and duration are determined for each transmission to a given user, and also the specific time of that transmission. It should be noted in this regard that in alternative embodiments of the invention, part of the network may be scheduled according to inter-cell scheduling, which requires transmissions to be coordinated between base stations, while the rest of the network has intra-cell scheduling, which does not require such coordination.

[0078] As an example of a particular implementation, the general, exemplary linear programming problem defined in equation (10) through equation (12) may, for example, simply include a particular cell E₀in the network and cell E₀'s two neighboring cells E₋₁and E₁such as shown in FIGS. 6A-6D. For this case, the network is assumed to be a symmetric network. The users in cell E₀may be indexed as data users 1 through M (user 1 through user M), starting with the left most user and proceeding towards the right. The normalized values for β_liand β_risatisfy the monotonicity properties: a) if i>j then β_ri>β_rjand β_li>β_lj; and b) if the i^thdata user is closer to the base station of cell E₀than user j, then β_li+β_ri<β_lj+β_rj.

[0079] The quantity r* is defined as the network-wide allocation of transmission intervals to the data users 1 through M, and the transmission times allocated to the i^thdata user (i.e., user i) in cell E₀during an interval are τli, τri, τoi, τ2i. The exemplary solution for the linear programming problem may satisfy the following conditions: i) if i>j, then τ_ri*>0 implies τ_li*=τ_oj*=τ_2j*=0, and τ_lj*>0 implies τ_ri*=τ_0i*=τ_2i*=0; and ii) if user j is closer to the base station of cell E₀than user i, then τ_2i*>0 implies τ0j* =0, and τ_0j*>0 implies τ_2i*=0.

[0080] Condition (i) relates to the outer set of users in the left part of cell E₀receiving data only when the right interferer E₁is on, and a similar outer set of users in the right part of cell E₀receiving data only when the left interferer E₋₁is on. Condition (ii) implies that if cell E₀needs to transmit when both interferers are on, then it would prefer to do so to users which are closer to the base station. The optimal solution may be characterized by specifying the leftmost user that has non-zero R-time, the rightmost user that has non-zero L-time, and the innermost users (possibly one or either side of the base station) that have non-zero 0-time.

[0081] The above conditions may hold in other exemplary implementations even when the duty cycles and relative shifts between the transmission intervals of cells E−1, E₀, and E₁are fixed and only the allocations of transmission intervals to the data users 1 through M within each cell may be adjusted.

[0082] The inter-cell scheduling method of the present invention is applicable not only to linear networks, but also to two-dimensional networks. When defining the linear programming problem in the context of a two-dimensional network, it will be advantageous to specify, in advance, a structure for the schedule of downlink transmissions. The linear program is then solved for the corresponding durations. An exemplary such structure is a stipulation that each base station shall transmit in contiguous fashion within an assigned interval occupying a definite position relative to a cyclic start time.

[0083] In a case where the user's signals are at maximum rate (minimum spreading) and do not require full transmit power for reception by a user with minimum required SNR, the power of the signal may then be set to a level consistent with reception at or near the minimum required SNR at the user's transceiver. For the set of spreading constraints defining this case, users may be partitioned into two groups. For example, users in the group that are physically closer to a transmitting antenna of a base station (i.e., at the center of the cell) may generally receive a signal in the down-link that has a much higher signal-to-noise ratio than that of the signal received in the down-link by a user at the edge of the cell. In accordance with the present invention, a combination of both prior art CDMA transmission for one group (i.e., “CDMA mode” such as overlapping in frequency of the users'spread signal power such as shown in FIG. 2) and scheduling (time-sharing) of user transmissions in accordance with the present invention for the second group may be employed for reducing overall transmitted power by a base station.

[0084] For example, a simulation may be generated of symmetrical networks having different corresponding values of the orthogonality factor f; Results of simulations may be compared with the results computed for intra-cell scheduling only as the solution for the optimized linear programming problem of equations (10) through (12) (with the time period, or duty cycle, of all base stations set to 1).

[0085] For the network employed for the simulation of hybrid CDMA/Time-sharing, each base station transmits to an inner set of users with overlapping for part of the time, and transmits to the outer set of the users with scheduling in accordance with an implementation of the present invention for the remaining time. Referring to FIG. 3, the inner set of users may be located in the cell between -d₁and d₁, while the outer set of users may be located in the cell between -d₂and -d₁and between d₁and d₂. As defined herein, a user's “location” may not necessarily be a physical location, but may rather be a position within a range of signal-to-noise ratios or family of gains. If the inner set of users is large, for example, the spreading rate constraint R_max=0.1 W may be met; consequently, the portion of the time allocated to the inner set of users then depends on their minimum rate requirement. The orthogonality factor determines the interference between users in CDMA mode, and the minimum size of the inner set of users in CDMA mode is related to this orthogonality factor.

[0086] For the simulation, 32 users are uniformly spaced throughout the cell, and all users have a common minimum throughput requirement. The inner set comprises the N innermost users, and the variable ρ is defined as the fraction N/32. When ρ is “1”, all down-link signals to users in the cell are sent during CDMA mode, and when ρ is 0 all down-link signals to users in the cell are sent during intra-cell scheduling.

[0087] FIG. 8 is a theoretical graph of throughput versus fraction of users transmitting for a telecommunication system employing a hybrid CDMA/time-sharing method of scheduling. As shown in FIG. 8, the simulation of maximum common minimum throughput is plotted against the fraction ρ of the inner set of users in the CDMA set. The left-most point of each plotted curve corresponds to the minimum size of the inner set for the corresponding value of orthogonality factor to meet the R_maxconstraint. When the inner set is selected for the minimum size, the hybrid CDMA/Time-sharing method of scheduling approaches within 15% of the calculated bound of the intra-cell scheduling method. Since at least a fraction of the users within a cell may receive signal in the down-link with lower transmit power of the base station, base station power, and hence interference power to other cells, may be reduced.

[0088] The present invention can be embodied in the form of methods and apparatuses for practicing those methods. The present invention can also be embodied in the form of program code embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. The present invention can also be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a general-purpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits.

[0089] It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the principle and scope of the invention as expressed in the following claims.

[0090] It is shown below that Equations (11a) through (11f) state conditions sufficient for the time allocations to be feasible.

[0091] Define τ_k^ε,ε,εas the fraction of time that the on/off state of base stations (k−1, k, k+1) is (ε_k−1, ε_k, ε_k+1). These time fractions are uniquely determined by the time allocations, $\begin{array}{cc}\begin{array}{cccc}{\tau }_k^{0,0,0}={\tau }_k^{0,\mathrm{off}}& {\tau }_k^{0,0,1}={\tau }_k^{R,\mathrm{off}}& {\tau }_k^{0,1,0}={\tau }_k^{0,\mathrm{on}}& {\tau }_k^{1,0,0}={\tau }_k^{L,\mathrm{off}}\\ {\tau }_k^{0,1,1}={\tau }_k^{R,\mathrm{on}}& {\tau }_k^{1,0,1}={\tau }_k^{2,\mathrm{off}}& {\tau }_k^{1,1,0}={\tau }_k^{L,\mathrm{on}}& {\tau }_k^{1,1,1}={\tau }_k^{2,\mathrm{on}}\end{array}& \text{(A-1)}\end{array}$

[0092] The on-off configuration of the entire network may be represented by a vector δε{0,1}^{{0, . . . , K+1}}, wherein δ_kindicates the on/off state of base station k. For any δε{0,1}^{{0, . . . , K+1}}, let a_δ be the fraction of time that the on/off configuration of the network is δ. Then it remains to be shown that there are non-negative a_δ, with $\begin{array}{cc}\sum _{\delta \in {\left\{0,1\right\}}^{\left\{0,\dots ,K+1\right\}}}{\alpha }_{\delta }=1,& \text{(A-2)}\end{array}$

[0093] such that $\begin{array}{cc}\sum _{\delta \in {\left\{0,1\right\}}^{\left\{0,\dots ,K+1\right\}}\left({\delta }_{m-1},{\delta }_m,{\delta }_{m+1}\right)=\left({ϵ}_{m-1},{ϵ}_m,{ϵ}_{m+1}\right)}{\alpha }_{\delta }={\tau }_m^{{ϵ}_{m-1},{ϵ}_m,{ϵ}_{m+1}},& \text{(A-3)}\end{array}$

[0094] for all m=1, . . . , K.

[0095] Define τ_k,k+1^ε,εas the fraction of time that the on/off state of base stations (k, k+1) is (ε_k, ε_k+1) In view of Equations (11a) through (11f), we have $\begin{array}{cc}{\tau }_{k,k+1}^{{ϵ}_k,{ϵ}_{k+1}}=\sum _{{ϵ}_{k-1}=0}^1{\tau }_k^{{ϵ}_{k-1},{ϵ}_k,{ϵ}_{k+1}}=\sum _{{ϵ}_{k+2}=0}^1{\tau }_k^{{ϵ}_k,{ϵ}_{k+1},{ϵ}_{k+2}}.& \text{(A-4)}\end{array}$

[0096] Now let the time fractions a_δ be set as follows: $\begin{array}{cc}{\alpha }_{\delta }=\frac{\prod _{k=1}^K{\tau }_k^{{\delta }_{k-1},{\delta }_k,{\delta }_{k+1}}}{\prod _{k=1}^{K-1}{\tau }_{k,k+1}^{{\delta }_k,{\delta }_{k+1}}}.& \text{(A-5)}\end{array}$

[0097] It is readily shown that for a_δ defined as in Equation (A-5), the conditions stated in Equations (A-2) and (A-3) are satisfied.