1 Introduction
The Third Generation Partnership Project Long Term Evolution (3GPP-LTE) uses SC-FDMA (Single Carrier Frequency Division Multiple Access) as uplink access scheme in LTE systems, because it has a low peak-to-average power ratio (PAPR) in view of power limitations of the user terminals [1]. In wireless communication, the instantaneous channel conditions of all users always differ from each other, both in time and frequency domains. Therefore, dynamic radio resource allocation at each transmission time interval (TTI) plays a crucial role in improving system performance [2]-[3].
Many schemes of resource allocation in both uplink and downlink have been proposed. They focus on power allocation and subcarrier allocation, where power and subcarrier are dynamically allocated to all users to achieve a desired quality of service (QoS). At each TTI, the resource allocation can be formulated as an optimization problem to maximize or minimize the quality of service with a number of constraints.
Algorithm development in uplink is more challenging than in downlink because of the power constraints and subcarrier contiguity problem. In downlink there is only one power constraint (caused by limited power availability at the base station), while in uplink there are many power constraints (based on the transmit power of each user). Futhermore, subcarriers should be allocated to the user in a contiguous manner in order to maintain a low PAPR. Both issues make uplink resource allocation problems more challenging than those in downlink.
In this paper, improved mean greedy algorithms are proposed to solve the chunk allocation problem in SC-FDMA uplink systems. Improvement is achieved by performing a chunk-based allocation simultaneously with the existing mean enhanced greedy allocations, which employ user-based allocation. Additionally, selection criteria based on spectral efficiency and fairness are proposed to choose the best of both allocations.
The organization of this paper is as follows. In Section 2, we discuss related works. In Section 3 and 4, the system model and problem formulation are presented. In Section 5, the improved algorithms and their time complexities are investigated. Finally, the simulation results and conclusion are discussed in Section 6 and 7 respectively.
2 Related Works
Concerning downlink, several recent studies of allocation schemes have been carried out, as presented in [3]-[7]. In these schemes one power constraint is used to limit the transmit power, which depends on the available power at the base station. Subcarrier allocation is performed in terms of chunk unit. The chunk can contain an uncontiguous subcarrier, because of which a higher PAPR may occur. This can be accommodated by the base station because of higher power availability than at the mobile station [8]-[11].
The most recent schemes of uplink allocation are presented in [12]-[21]. The schemes presented in [12]-[15] are each divided into two steps, namely power allocation and subcarrier allocation. The optimization problem of the allocations was to maximize the spectral efficiency [12],[15], the data rate fairness [13], and system utility [14]. A waterfilling-based power allocation process is performed on each subcarrier for all users, where the power allocated to each subcarrier is based on each subcarrier's channel gain. Subsequently, subcarrier allocation is performed using a greedy-based algorithm. Using a waterfilling scheme can improve performance, but also increases the time complexity.
In order to reduce the time complexity, the power allocations proposed in [2],[8]-[9],[16]-[19] were simplified using equal power allocation by equally
dividing the amount of available power among the subcarriers without considering their channel gain. Using equal power allocation, the problem of resource allocation becomes a problem of subcarrier allocation. The subcarrier allocations described in [16] and [18] are performed on a subcarrier-bysubcarrier basis and in [2],[8]-[9],[17],[19] on a chunk-by-chunk basis so that the time complexity is reduced. In [20-21], chunk-by-chunk allocation algorithms using power allocation based on waterfilling are investigated. The algorithm presented in [21] introduces fractional power control to limit the transmit power of each user. The method described in [20]-[21] can achieve optimal spectral efficiency and fairness performance. However, this method increases the complexity.
In [2],[8]-[9],[17],[19] chunk-by-chunk allocation was performed using a searching process based on a greedy algorithm. The optimization problem of these allocation schemes was to maximize spectral efficiency [9],[17], or to maximize data rate fairness among users [2],[8],[19]. The advantage of chunkbased subcarrier allocation is that it can maintain a low PAPR due to subcarrier contiguity within a chunk and reduce the complexity. The algorithms described in [2],[17],[19] consider the data rate fairness among users as one of the constraints for their optimization problem. The algorithm in [17] maximizes the spectral efficiency while maintaining the fairness among users.
In [2], two mean greedy algorithms, namely the Mean Enhanced Greedy (MEG) algorithm and Single Mean Enhanced Greedy (SMEG) algorithm, are investigated. Both algorithms maintain the data rate fairness among users instead of spectral efficiency, by allocating one chunk to one user. Its allocations are performed according to the average of the chunk's channel quality experienced by the user. In [19], the Multicriteria Greedy-based algorithm is investigated. In this scheme, the users who obtain chunks are sorted according to multiple criteria of utility, such as mean, standard deviation and minimum utility threshold.
3 System Model
The resource allocation model for the SC-FDMA uplink system is presented in Figure 1. There are K users and N available subcarriers. The focus of this work is on the resource allocation scheme that allocates resources to all users using a certain algorithm. In the initialization process, each user sends channel state information (CSI) consisting of the channel gain of N subcarriers to the base station via the control signal. On the basis of this CSI, the algorithm assigns power to all subcarriers and allocates C chunks to K users. The output of the resource allocation is resource assignment decisions for all users, which are sent to all users via the control signals. These are used by all users for transmitting traffic signals in the uplink direction.
Figure 1 Resource allocation in SC-FDMA uplink systems.
Figure 2 The optimization problem of chunk allocation.
The available subcarriers are converted into several chunks, based on the L-FDMA (Localized Frequency Division Multiple Access) method used in [21]-[22]. The number of consecutive subcarriers per chunk is \(n_c = N/K\). One chunk is equal to the fraction of the total transmission bandwidth that is allocated to one user. In order to maintain fairness among users, only one chunk is allocated to one user and can not be shared by other users [2],[17]. This means that the number of available chunks is equal to the number of users (C = K). Equal
power allocation is used in our improved algorithms, so that the problem of resource allocation becomes a problem of chunk allocation. The problem of chunk allocation with C chunks and K users is to determine the elements of matrix S specifying the chunk assignment index. This indicates which chunk should be assigned to which user such that the sum of spectral efficiency or data rate fairness among users is maximized. A model of the uplink resource allocation problem is shown in Figure 2.
4 Problem Formulation
The channel gain on subcarrier n of user k at a certain TTI is defined as \(H_{n,k}\). In this work, the CSI of all users is perfectly known by the base station and is modeled as follows [8],[9],[23],[24]:
\[H_{n,k} = \frac{R_{n,k}}{L_p \ x \ (d_k)^{\delta} \ x \ \varepsilon_{n,k}} \tag{1}\]
Where \(L_p\) is the propagation loss; \(d_k\) is distance of user k from the base station in kilometers; \(\delta\) is path loss exponent; \(\varepsilon_{n,k}\) is lognormal shadowing; and \(R_{n,k}\) is the rayleigh fading with rayleigh parameter \(\tau\) such that \(E[\tau^2]=1\). This can be expressed as channel gain-to-noise ratio of subcarrier n of user k as follows:
\[CNR_{n,k} = \frac{H_{n,k}}{\sigma_n^2} \tag{2}\]
\(\sigma_n^2\) is the noise power of subcarrier n. In the case of power allocation, power is allocated to each subcarrier within a chunk using equal power allocation as follows:
\[p_{n,k} = \frac{P_k}{n_c} \tag{3}\] where \(p_{n,k}\) is the power allocated to subcarrier n of user k and its allocations are performed for n = 1,...,N and k = 1,...,K. \(P_k\) is the transmit power of user k. At every TTI, the transmit power of all users is constant and equal to the maximum power (\(P_k = P_{max}\)). After power is allocated to all subcarriers, chunk allocation is performed. The base station establishes a unit of allocation by collecting \(n_c\) consecutive subcarriers into a group, which is called a chunk. One chunk containing 12 consecutive subcarriers is denoted as \(n_c = 12\). In the chunk allocation algorithm, the pairs of user-chunks are searched by the base station such that the objective of the allocation is achieved. To be able to search user-chunk pairs, the quality of all possibilities of user-chunk pairs should be known by the base station, which depends on the users' CSI. The quality of a userchunk pair using MMSE (Minimum Mean Square Equalizer) equalization can be determined by [8],[9]:
\[\gamma_{c,k} = \left(\frac{1}{\frac{1}{n_c} \sum_{n=i,n_c+1}^{i,n_c+n_c} \frac{\gamma_{n,k}}{\gamma_{n,k}+1}} - 1\right)^{-1}\] (4)
\(\gamma_{c,k}\) is signal-to-noise ratio (SNR) if chunk c is allocated to user k and i = 0,1,2,...,C-1. This quality is determined for k = 1,2,...,K and \(\gamma_{c,k} = p_{n,k}H_{n,k}/\sigma_n^2\). \(\gamma_{n,k}\) is SNR if subcarrier n is allocated to user k. The achievable data rate of chunk c if it is allocated to user k has the following upper bound [8],[9]:
\[R_{c,k} = b \log_2 \left[ 1 + \gamma_{c,k} \right] \tag{5}\] where b is bandwidth per chunk, which is defined as b = B/C, where B is the bandwidth of the system. In our optimization problem, in order to maintain the fairness among users one chunk is allocated to one user only. Then, the calculation of the achievable data rate of user k after chunk allocation is performed, which has the following upper bound:
\[R_{k} = \sum_{c=1}^{C} S_{c,k} R_{c,k} = b \sum_{c=1}^{C} S_{c,k} (1 + \gamma_{c,k})\] subject to: \[\sum_{c=1}^{C} S_{c,k}, \forall k \in K\] \[S_{c,k} = \{0,1\}\] (6)
where \(S_{c,k}\) is the chunk assignment index, which indicates whether user k occupies chunk c or not. In practical modulation schemes, the power and the signal-to-noise ratio have to be adjusted according to the required bit error rate (BER). The approximate expression is used for BER. In [25], the BER of a square M-QAM with Gray bit mapping as a function of received SNR \(\gamma\) and number of bits per symbol r has been approximated for \(r \ge 2\) and BER \(\le 10^{-3}\), as follows [25]:
\[BER_{M-QAM}(\gamma) \approx 0.2 \exp\left[\frac{-1.5\gamma}{2^r - 1}\right]\] (7)
By solving equation (7) we have:
\[r = \log_2 \left[ 1 + \frac{\gamma}{\Gamma} \right] \tag{8}\] where
\[\Gamma = \frac{-\ln(5BER)}{1.5} \tag{9}\]
\(\Gamma\) is called the SNR gap, which is the difference between the SNR needed to achieve a certain transmission data rate for a practical system and the theoretical limit. \(\gamma\) /\(\Gamma\) is the effective SNR, which has been adjusted according to the desired BER and the modulation scheme. Since equal power is allocated to each subcarrier within a chunk, the modulation scheme and bit per symbol used in each subcarrier within a chunk are also the same. In case of chunk allocation problems, the number of bits per symbol per chunk \(r_{c,k}\) in a practical modulation scheme can be approximated as follows:
\[r_{c,k} = \log_2 \left[ 1 + \frac{\gamma_{c,k}}{\Gamma} \right] \tag{10}\] where \(\gamma_{c,k}\) is the SNR of chunk c, which is allocated to user k based on equation (4). By considering the SNR gap, the achievable data rate of user k can be expressed as follows:
\[R_{k} = b \sum_{c=1}^{C} S_{c,k} \left( 1 + \frac{\gamma_{c,k}}{\Gamma} \right)\] \[\tag{11}\]
To obtain the data rate fairness among users, Jain's fairness index is used to express it as [26]:
\[F_{i} = \frac{\left(\sum_{k=1}^{K} R_{k}\right)^{2}}{Kx \sum_{k \in K} R_{k}^{2}}\] \[\tag{12}\] where \(R_k\) is the data rate of user k. By substituting (11) into (12) we obtain:
\[F_{i} = \frac{\left(b\sum_{k=1}^{K}\sum_{c=1}^{C}S_{c,k}\left(1 + \frac{\gamma_{c,k}}{\Gamma}\right)\right)^{2}}{K\sum_{k=1}^{K}\left(b\sum_{c=1}^{C}S_{c,k}\left(1 + \frac{\gamma_{c,k}}{\Gamma}\right)\right)^{2}}\] (13)
In our optimization problem, a new chunk allocation formulation is proposed that uses selection criteria based on spectral efficiency or on fairness. The objective of these criteria is to maximize the sum of the data rate or to maximize the data rate fairness among users respectively. The optimization problem is formulated as:
Objective:
\[Max : R_{T} = b \sum_{k=1}^{K} \sum_{c=1}^{C} S_{c,k} \left( 1 + \frac{\gamma_{c,k}}{\Gamma} \right)\] \[or\] \[F_{i} = \frac{\left( b \sum_{k=1}^{K} \sum_{c=1}^{C} S_{c,k} \left( 1 + \frac{\gamma_{c,k}}{\Gamma} \right) \right)^{2}}{K \sum_{k=1}^{K} \left( b \sum_{c=1}^{C} S_{c,k} \left( 1 + \frac{\gamma_{c,k}}{\Gamma} \right) \right)^{2}}\]
Subject to:
\[C1: \sum_{c=1}^{C} S_{c,k}, \forall k \in K\] \[C2: \sum_{k=1}^{K} S_{c,k}, \forall c \in C\] \[C3: S_{c,k} = \{0,1\}\] \[(14)\]
Constraints (C1) to (C3) are used to guarantee the data rate fairness among users by allowing each user to use only one chunk that can not be shared by other users. The optimization problem in (14) is a combinatorial optimization problem which involves binary variable \(S_{c,k}\) for chunk assignment. The optimum solution can be achieved by linear integer programming [27] with a high complexity, which is difficult to implement. Ideally, chunk and power allocation should be carried out jointly, which also requires a high complexity. Low-complexity algorithms using a simplified power allocation with accepted performance are more preferable over complex optimal algorithms. In this paper, several algorithms to solve the optimization problems are proposed.
5 Improved Mean Greedy Algorithm
In user-based allocations, i.e. the MEG and SMEG algorithms [2], the user order that will determine the chunk on each allocation is established. The user order is arranged depending on the average of each chunk's channel quality sorted in ascending order. The user who obtains a chunk on each allocation is assigned according to the sorted user order. Futhermore, the chunk allocated to a user is obtained by selecting the chunk that has the highest channel quality for that user. In the MEG algorithm, the calculation of the average of the chunk's channel quality of all users is done for every allocation at a TTI, but in the SMEG algorithm the calculation of this average is performed only once at a TTI. Both algorithms have a lower complexity than the conventional greedybased scheme, because the searching process is not performed on all possibilities of allocation, which would be time-consuming.
In our improved algorithms, chunk-based allocation is performed simultaneously with the existing user-based allocation. It determines the chunk order which be allocated to user on each allocation. The chunk order is arranged depending on the average of the user's channel quality, sorted in ascending order. One chunk allocated on each allocation is assigned according to the sorted chunk order. Then, the user who obtains that chunk is determined by choosing the user who has the highest channel quality on that chunk. The chunk-based allocation is performed simultaneously with the MEG and SMEG algorithms, which are called Chunk-Based MEG (CB-MEG) algorithm and Chunk-Based SMEG (CB-SMEG) algorithm respectively.
The improved algorithms consist of user-based allocation combined with chunk-based allocation. After both allocations are performed, the spectral efficiency index and fairness index achieved by both allocations are obtained. A selection criteria procedure is proposed to choose one of both allocations as the final allocation at each TTI. These combined schemes are called Improved Mean Enhanced Greedy (IMEG) algorithm and Improved Single Mean Enhanced Greedy (ISMEG) algorithm respectively. Each of them can use one of two criteria selections, so we divide them into four algorithms, namely IMEG-SE (IMEG based on spectral efficiency) algorithm, IMEG-FAIR (IMEG based on fairness) algorithm and ISMEG-FAIR (ISMEG based on fairness) algorithm respectively. A flowchart of the improved algorithms can be seen in Figure 3. The procedures of the CB-MEG and CB-SMEG algorithms can be described as follows:
CB-MEG Algorithm:
1. For all chunks (c = 1,2,...C), calculate the average users's channel quality (k=1,2,...K) using:
\[X_{c} = (1/K) \sum_{k=1}^{K} \gamma_{ck}\] (15)
- 2. Sort \(X_c\) in ascending order.
- 3. Select a chunk to be allocated by choosing the chunk which has the lowest average user's channel quality using:
\[\tilde{c} = \arg\min X_c \tag{16}\] 4. The user who obtains chunk c is selected by searching the highest channel quality on chunk \(\overset{\circ}{c}\):
\[\tilde{k} = \arg\max \quad \gamma_{ck} \tag{17}\]
- 5. A chunk c is allocated to user k and both are removed from the process.
- 6. Repeat step 1 to 5 until all chunks have been allocated.
CB-SMEG Algorithm:
1. For all users (c = 1,2,....C) calculate the average user's channel gain quality (k = 1,2,....K):
\[X_{c} = (1/K) \sum_{k=1}^{K} \gamma_{ck}\] (18)
- 2. Sort \(X_c\) in ascending order.
- 3. Select a chunk to be allocated depending on its place in the ascending-order sequence. The chunk with the lowest \(X_c\) is selected using:
\[\tilde{c} = \arg\min \ X_c\] (19)
4. The user who obtains chunk c is selected by searching the highest channel quality on chunk \(\overset{\sim}{c}\) using:
\[\tilde{k} = \arg\max_{\tilde{c}k} \quad \gamma_{\tilde{c}k}\] (20)
- 5. The chunk c is allocated to user k.
- 6. Remove c from the ascending-order index and remove k from the allocation process.
- 7. Repeat step 3 to 6 until all chunks have been allocated.
In order to determine the time complexity of the improved algorithms, the asymptotic time complexity due to the time constraint within a TTI is used. In the MEG algorithm, the calculation of the average of the chunk's channel quality for all users requires O(KC) operations. The sorting of the average of the user's channel quality and selecting of the user who obtains the chunk requires O(K) operations. To select the chunk that has the highest channel quality for that user requires O(C) operations. All these steps are repeated for all users until all users have been allocated chunks. The total time complexity of the MEG algorithm is \(O(K(KC)+K(K)+K(C))=O(K^2C)\), where the polynomial degree of O(.) is 3.
The SMEG algorithm has a lower complexity than the MEG algorithm because of the single average calculation at each TTI. The calculation of the average of the chunk's channel quality for all users requires O(KC) operations. The sorting of the average of the chunk's channel quality in ascending order and selection of the user who will get the chunk requires O(K) operations. To find the chunk that will be allocated to the user requires O(C) operations. The last two steps are repeated until all users have been allocated chunks. The total time complexity is \(O(KC+K(K)+K(C))=O(KC)+O(K^2)\). It can be seen that the polynomial degree of O(.) is 2, which is lower than that of the MEG algorithm.
In the CB-MEG algorithm, the calculation of the average of the user's channel quality for all chunks requires O(KC) operations. The sorting of the average of the chunk's channel quality and selection of the chunk that will be allocated to the user requires O(C) operations. To select the user who has the highest channel quality on that chunk requires O(K) operations. All these steps are repeated for all chunks until all chunks have been allocated. The total time complexity of the CB-MEG algorithm is \(O(C(KC)+C(C)+C(K))=O(KC^2)\). Futhermore, the selection criteria require O(1) operations. The total time complexity of the IMEG algorithms is a combination of the time complexity of the MEG algorithm and that of the CB-MEG algorithm. Thus, the complexity of the IMEG algorithms is \(O(K^2C)+O(KC^2)+O(1)=O(K^2C+KC^2)\) where the polynomial degree of O(.) is 3. Therefore, it has the same time complexity as the MEG algorithm.
In the CB-SMEG algorithm, the calculation of the average of the user's channel quality for all chunks requires O(KC) operations. The sorting of the averages of the user's channel quality in ascending order and selection of the chunk to be allocated requires O(C) operations. To find the user who will obtain that chunk requires O(K) operations. The last two steps are repeated until all chunks have been allocated. The total time complexity of the CB-SMEG algorithm is then \(O(KC+C(C)+C(K))=O(KC)+O(C^2)\). Futhermore, the selection criteria need O(1) operations. The total time complexity of the ISMEG algorithms is a combination of the time complexity of the SMEG algorithm and that of the CB-SMEG algorithm. Thus, the complexity of the ISMEG algorithms is \(O(KC)+O(K^2)+O(KC)+O(C^2)+O(1)=O(KC)+O(K^2)+O(C^2)\). It can be seen that the polynomial degree of O(.) of ISMEG is 2, which is lower than that of the IMEG algorithm. This means that the ISMEG algorithms have less time complexity than the IMEG algorithms and they have the same time complexity as the SMEG algorithm.
In order to maintain fairness among users by taking into account K = C, the total time complexity of the IMEG algorithms becomes \(O(KC^2)\) and that of the ISMEG algorithms becomes O(KC). A comparison between the time
complexity of the improved algorithms and that of the mean greedy algorithms is presented in Table 1. It can be seen that the IMEG algorithms have the same complexity as the MEG algorithm. The ISMEG algorithms have the same complexity as the SMEG algorithm and less complexity than the IMEG algorithms.
Figure 3 Flowchart of the improved algorithms.
Table 1 Summary of time complexity with K = C.
| Algorithm | Time complexity |
|---|---|
| Mean Enhanced Greedy(MEG) | O(KC2 ) |
| Single Mean Enhanced Greedy(SMEG) | O(KC) |
| Improved MEG(IMEG) | O(KC2 ) |
| Improved SMEG(ISMEG) | O(KC) |
6 Simulation Results and Discussion
The improved algorithms were evaluated based on a montecarlo simulation using MATLAB. The sum average of the spectral efficiency and the average of the fairness index of the proposed algorithms were compared to those of the
MEG and the SMEG algorithms. All simulations were evaluated with 5000 trials, except when observing the effect of the user's velocity, for which 50000 trials were used. The desired BER for each user in all simulations was 10-4. A frequency of 2 Ghz was assumed and the channel gain of the CSI was perfectly known by the base station. The channel gain of each subcarrier per user at every TTI was determined on the basis of the macrocell model for urban and suburban areas based on (1). Substituting Hn,k on (1) into CNR on (2) with σn 2=No.B, CNR per subcarrier of each user in decibel can be expressed as:
\[CNR_{n,k}[dB] = 10\log R_{n,k} - L_p - 10\delta \log d_k - \varepsilon_{n,k} - N_o.B\] (21)
where Lp is propagation loss, chosen to be 128.1 dB; dk is the distance of user k from the base station in kilometers; δ is pathloss exponent, set to 3.76; εn,k is the lognormal shadowing deviation, set to 7 dB; Rn,k is the rayleigh fading, with rayleigh parameter τ such that E[τ 2]=1; No is the noise spectral density per subcarrier, chosen to be –174 dBm/hz; and B is the bandwidth per subcarrier, set to 15 Khz. Each chunk consists of 12 consecutive subcarriers.
In order to know the general behaviour of each of the proposed algorithms in terms of spectral efficiency and fairness, its performance was evaluated in four scenarios by varying four parameters: number of users, distance of all users, cell radius, and velocity of all users. The average improvement of both performances was denoted in percentage values by averaging the performance difference between each proposed scheme with the previous schemes over all values on the horizontal axis.
6.1 Effect of Number of Users
Figures 4 and 5 show the effect of the number of users on spectral efficiency and fairness respectively, by varying the number of users from 5 to 50. The radius of cell was 2 kilometers. The users' locations were randomly generated and uniformly distributed over the cell. The sum average of spectral efficiency of all schemes increased due to the increase in number of users, as can be seen in Figure 4, since the spectral efficiencies achieved by all users are added up. The ISMEG-SE algorithm provided a spectral efficiency improvement for all numbers of users. It gave an average spectral efficiency improvement of 2.6% and 11.6% compared to the SMEG and MEG schemes respectively. While the IMEG-SE algorithm gave an average spectral efficiency improvement of 2.1% compared to the MEG schemes, it achieved an average spectral efficiency reduction of 6% compared to the SMEG scheme. The ISMEG-FAIR algorithm achieved an average spectral efficiency improvement of 1.9% compared to the MEG algorithm, while it gave an average spectral efficiency reduction of 6.3% compared to the SMEG scheme. The IMEG-FAIR algorithm achieved an average spectral efficiency reduction of 13.1% and 5.5% compared to the SMEG and MEG schemes respectively.
In Figure 5, it can be seen that by increasing the number of users, the IMEG-FAIR, IMEG-SE and MEG algorithms maintained a constant fairness, while the ISMEG-FAIR, ISMEG-SE and SMEG algorithms experienced a decrease in fairness. The IMEG-FAIR scheme had the highest fairness and provided a fairness improvement for all numbers of users. It gave an average fairness improvement of 16.1% and 4% compared to the SMEG and MEG schemes respectively. While the ISMEG-FAIR scheme achieved an average fairness improvement of 9.1% compared to the SMEG scheme, it gave an average fairness reduction of 2.2% compared to the MEG scheme. The ISMEG-SE algorithm achieved an average reduction of fairness of 1.6% and 11.6% compared to the SMEG and MEG schemes respectively. The IMEG-SE algorithm gave an average fairness improvement of 10.9% compared to the SMEG algorithm and an average fairness reduction of 0.8% compared to the MEG scheme.
Figure 4 Effect of number of users on spectral efficiency.
Considering the results presented in Figure 4 and 5, it can be concluded that there is a trade-off between spectral efficiency and fairness. The ISMEG-SE and IMEG-SE schemes improved the spectral efficiency when they used the spectral efficiency selection criterium to choose the final allocation, as shown in Figure 4. Consequently, there was a fairness reduction in the ISMEG-SE and IMEG-SE schemes, as shown in Figure 5. On the other hand, IMEG-FAIR and ISMEG-FAIR improved the fairness when they used the fairness selection criterium to choose the final allocation, as shown in Figure 5. Consequently, there was a spectral efficiency reduction in the IMEG-FAIR and ISMEG-FAIR schemes, as shown in Figure 4.
Figure 5 Effect of number of users on fairness.
6.2 Effects of Distance of Users
Figures 6 and 7 present the effects of distance of all users on spectral efficiency and fairness respectively. These were evaluated by placing all users at the same distance from the base station and varying this distance from 0.5 to 5 kilometers. The number of users within 1 cell was 30. When increasing the distance of all users, all schemes had the same tendency, i.e. to experience a spectral efficiency decrease and a fairness increase. This occured because both the average and the variance of the users' channel gain-to-noise ratio (CNR) decreased with the increasing distance of all users.
In Figure 6, it can be seen that the ISMEG-SE scheme gave a small improvement. It gave an average spectral efficiency improvement of 0.9% and 1.5% compared to the SMEG and MEG schemes respectively. The IMEG-SE scheme gave an average spectral efficiency improvement of 0.5% and 1.1% compared to the SMEG and MEG schemes respectively. The ISMEG-FAIR scheme achieved an average improvement of 0.2% and 0.8% compared to the SMEG and MEG schemes respectively. The IMEG-FAIR scheme gave an average reduction of 0.6% and 0.03% compared to the SMEG and MEG schemes respectively.
Figure 6 Effect of distance of all users on spectral effiency.
Figure 7 Effect of distance of all users on fairness.
In Figure 7 it can be seen that the IMEG-FAIR scheme also provided a small fairness improvement. It gave an average fairness improvement of 0.9% and 0.2% compared to the SMEG and MEG schemes respectively. The ISMEG-FAIR scheme achieved an average improvement of 0.3% and an average reduction of 0.3% compared to the SMEG and MEG schemes respectively. The ISMEG-SE scheme achieved an average improvement of 0.05% and an average reduction of 0.6% compared to the SMEG and MEG schemes respectively. The
IMEG-SE scheme gave an average improvement of 0.6% and 0.002% compared to the SMEG and MEG schemes respectively.
By varying the users' distance, the ISMEG-SE and IMEG-SE algorithms provided a small spectral efficiency improvement, whereas the ISMEG-FAIR and IMEG-FAIR schemes achieved a small spectral efficiency reduction compared to the SMEG and MEG schemes respectively. On the other hand, the ISMEG-FAIR and IMEG-FAIR schemes provided a small fairness improvement, while the ISMEG-SE and IMEG-SE schemes provided a small fairness reduction compared to the SMEG and MEG schemes. It can be concluded that the proposed algorithms achieved no significant improvements in both spectral efficiency and fairness compared to the SMEG and MEG schemes.
6.3 Effect of Cell Radius
Figures 8 and 9 show the influence of cell radius on spectral efficiency and fairness respectively. These were varied between 1 and 5 kilometers. The number of users within 1 cell was 30 and their locations were randomly generated with uniform distribution over the cell. The results show that the sum of spectral efficiency and fairness of all schemes decreased due to a cell-radius increase. This was caused by the lower average and the higher variance of the users' CNR when the cell radius increased.
Figure 8 Effect of radius of cell on spectral efficiency.
Figure 9 Effect of radius of cell on fairness.
In Figure 8, it can be seen that the ISMEG-SE scheme gave a small spectral efficiency improvement for all cell radii. It achieved an average spectral efficiency improvement of 0.1% and 1.5% compared to the SMEG and MEG schemes respectively. The IMEG-SE scheme gave an average spectral efficiency reduction of 1.3% compared to the SMEG scheme and an average spectral efficiency improvement of 1.1% compared to the MEG scheme. The ISMEG-FAIR scheme gave an average spectral efficiency reduction of 3.1% and 1.8% compared to the SMEG and MEG schemes respectively. The IMEG-FAIR scheme gave an average spectral efficiency reduction of 4.6% and 3.2% compared to the SMEG and MEG schemes respectively.
Figure 9 shows that the IMEG-FAIR algorithm provided a small improvement for all cell radii. It achieved an average fairness improvement of 2.1% and 0.5% compared to the SMEG and MEG schemes respectively. The ISMEG-FAIR algorithm gave an average spectral fairness improvement of 0.6% and an average fairness reduction of 1% compared to the SMEG and MEG schemes respectively. The ISMEG-SE algorithm gave an average fairness reduction of 0.1% and 1.7% compared to the SMEG and MEG schemes respectively. The IMEG-SE algorithm gave an average fairness improvement of 1.6% and an average fairness reduction of 0.04% compared to the SMEG and MEG schemes respectively.
By varying the cell radius, the improved schemes also gave a small improvement in both spectral efficiency and fairness. It can be concluded that there were no significant improvements in this scenario.
6.4 Effect of Velocity of Users
Figures 10 and 11 show the effects of user's velocities on spectral efficiency and fairness respectively. The number of users within 1 cell was 10 and they moved away radially from the base station with the same velocitiy. The velocity was varied between 0 and 240 km/h. The channel state information of all users was perfectly known by the base station and the coherence time of channel when a user moved at a speed of 240 km/h was 2.16 ms, based on (18) of [28]. This means that a user moved a distance of 0.035 meters per TTI. When increasing the velocity of all users, all schemes had the same tendency of decreasing spectral efficiency and increasing fairness. This occured because both the average and the variance of the users' CNR decreased with an increasing distance of all users.
Figure 10 shows that the ISMEG-SE algorithm achieved the highest spectral efficiency. It achieved an average spectral efficiency improvement of 6.5% and 12.5% compared to the SMEG and MEG schemes respectively. The IMEG-SE algorithm gave an average spectral efficiency improvement of 4.1% and 10% compared to the SMEG and MEG schemes respectively. The ISMEG-FAIR algorithm gave an average spectral efficiency reduction of 2.8% and an average improvement of 2.8% compared to the SMEG and MEG schemes respectively. The IMEG-FAIR algorithm achieved an average spectral efficiency reduction of 8% and 2.7% compared to the SMEG and MEG schemes respectively.
Figure 11 shows that the IMEG-FAIR algorithm had the highest fairness. It achieved an average fairness improvement of 6% and 2.3% compared to the SMEG and MEG schemes respectively. The ISMEG-FAIR algorithm gave an average fairness improvement of 3.4% compared to the SMEG scheme and an average fairness reduction of 0.2% compared to the MEG scheme. The ISMEG-SE algorithm gave an average fairness reduction of 1.7% and 5.1% compared to the SMEG and MEG schemes respectively. The IMEG-SE algorithm achieved an average fairness improvement of 0.34% compared to the SMEG scheme and an average fairness reduction of 3.1% compared to the MEG scheme.
Varying the velocity of all users there was, again, a tradeoff between spectral efficiency and fairness. These results are consistent with the results in Section 6.1, where the ISMEG-SE and IMEG-SE schemes improved the spectral efficiency as presented in Figure 10, while there was a fairness reduction as shown in Figure 11. Moreover, the IMEG-FAIR and ISMEG-FAIR schemes improved the fairness, as can be seen in Figure 11, although there was a spectral efficiency reduction, as can be seen in Figure 10. Thus, it can be concluded that using the selection criteria based on spectral efficiency caused a sacrifice of the fairness in the system, and vice versa.
Figure 10 Effect of velocity of all users on spectral efficiency.
Figure 11 Effect of velocity of all users on fairness.
7 Conclusions
In this paper, improved mean greedy algorithms to solve the chunk allocation problem in SC-FDMA uplink have been proposed. The proposed algorithms are: IMEG-SE, IMEG-FAIR, ISMEG-SE and ISMEG-FAIR. They are performed by employing chunk-based allocation simultaneously to existing MEG and SMEG algorithms respectively. Selection criteria based on both
spectral efficiency and fairness have been proposed to choose either user-based or chunk-based allocation for the final allocation at each transmission time interval.
The simulations results show that by varying the number of users and the velocity of the users, the ISMEG-SE and IMEG-SE schemes both achieved spectral efficiency improvements compared to the SMEG and MEG schemes. On the other hand, there was a fairness reduction due to the use of spectral efficiency as the selection criterium. The IMEG-FAIR and ISMEG-FAIR schemes gave fairness improvements compared to the SMEG and MEG schemes because they use fairness as the selection criterium. Consequently, there was a fairness reduction with the ISMEG-SE and IMEG-SE schemes, as well as a spectral-efficiency reduction with the ISMEG-FAIR and IMEG-FAIR schemes compared to the SMEG and MEG schemes. Thus, it can be concluded that there is a tradeoff between spectral efficiency and fairness that depends on the objective of the allocation.
Using both allocations at the same time within a TTI does not increase the time complexity due to the asypmtotic approximation. The ISMEG-SE and ISMEG-FAIR algorithms have the same complexity as the SMEG scheme. Meanwhile, the IMEG-SE and IMEG-FAIR algorithms have the same complexity as the MEG scheme. Both ISMEG schemes have less time complexity than both IMEG schemes because the average calculation in the ISMEG schemes is done only once at each TTI. The ISMEG-SE algorithm has the highest spectral efficiency with a low time complexity, which can be applied in multimedia services that consider throughput and time constraints. The IMEG-FAIR algorithm has the highest fairness, while its time complexity can still be compared with the other schemes.
Acknowledgements
The first author is a lecturer at the Telkom Institut of Technology (IT TELKOM), Bandung. This work was supported by a Yayasan Pendidikan Telkom (YPT) Scholarship, grant number 160/SDM-06/YPT/2009.