Lijing Jiang, Rongfang Song

Nanjing University of Posts and Telecommunications, Nanjing 210003, China

I. INTRODUCTION

1.1 Backgrounds and motivation

With surging demands of multimedia services,such as mobile television and web browsing,it is worth noting that multicast transmission[1], [2] is gaining importance in orthogonal frequency division multiple access (OFDMA)systems. While abundant accomplishment is achieved on dynamic resource allocation(DRA) in unicast systems as surveyed in [3],[4], research on multicast systems is rising.As known in previous works [5], [6], DRA in multicast systems is a challenging problem for its complicated channel conditions, proportional fairness requirements and energy-efficient power constraints.

Considering complicated channel conditions and proportional fairness requirement which intends to prevent resource starvation and provide fair quality of service (QoS) to all groups, the major challenge is to solve the non-convex problem of allocating sub-channels to proper users grouped together. There are three simple rate rules adopted extensively to address the complicated multicast channel conditions: a pre-dened default rate [7],adaptive transmission at worst user’s rate [8]and dynamic transmission with group average throughput [9]. To maintain proportional fairness, allocating a fixed number of sub-channels among different groups is proved to be inefcient because of the diverse sub-channels conditions in [10]. So we solve this problem from another perspective by restricting group data rate directly. In our concerned situation,adaptive transmission at worst user’s rate is appropriate.

In retrospect, in order to solve a non-convex problem, the traditional evolutionary algorithms (EA) [11], [12], such as genetic algorithm (GA) and particle swarm optimization (PSO) [13], have been widely employed.These algorithms are sensitive to parameters selection. Improper parameters selection will cause slow or premature convergence. So this paper proposes a constrained team progress algorithm (CTPA) which is modified based on[14] as the optimization tool over GA and PSO for its superiority in both parameter tuning complexity and computational cost.

Power assignment is designed to guarantee proportional fairness in [15]. It is under the presumption that the ratio of allocated number of sub-channels to each group is almost equal to the required group data rates ratio(the presumption is true when the sub-channels number is enormously big and much bigger than the group number). However, this presumption carries limitation in application.Besides, the formula derivation of the power for each group according to the fairness ratio can roughly maintain proportional fairness.Power assignment within each group utilizing water-lling algorithm at last will directly in-uence group data rate. Thus, the group data rates ratio will no longer be ensured at last.

1.2 Challenges

– Optimizing sub-channels allocation is non-convex because of its combinatorial nature and the objective functions with proportional fairness constraint. We focus on designing a near optimal approach to maximize the capacity under the constraint of fairness.

– In addition to sub-channels allocation, how to utilize the total power budget efciently is another concern. The power assignment should also take proportional fairness into consideration, which makes the searching more complicated.

1.3 Contributions

– The proposed approach utilizes frequency diversity and meets the proportional fairness demand properly. So the multicast diverse data rates can be tunable.

– CTPA can address non-convex problem which aims at maximizing throughput while satises the proportional fairness constraint with a low complexity.

– MPA, utilizing the mapping relation between power and throughput, can be as good as exhaustive search (ES) while sacri-ce storage space based on the accuracy of system demands. Although the discretization method may lead the solution slightly off the feasible set dened by the nonlinear constraints. There is always a tradeoff between satisfaction of the constraints and improvement of the objective.

1.4 Paper organization

The remainder of this paper is organized into following parts: in Section II, the multicast system is formulated and the optimization model is presented. Section III introduces the optimization algorithm CTPA subject to certain constraints. Section IV makes a presentation of proposed solution including sub-channels allocation CTPA and power assignment scheme MPA, and compares it with related research work. In Section V, the simulation results are analyzed in different scenarios. At last, Section VI makes a conclusion.

II. SYSTEM MODEL

This paper considers an OFDMA multicast system with one cell as shown ingure 1: one base station (BS) transmits data streams to G multicast groups on Ssub-channels. The total bandwidth is B Hz, thus the bandwidth of each sub-channel isEach user can be assorted to one group exclusively.All sub-channel is assumed to be slowly-varying. The total Q users are grouped into G user groups. Denoteas the users assorted to group g,being the cardinality of this combination. We specifically discuss the situation ofwhich is de-ned as multicast transmission. Denote hq,sas the channel gain of user q over sub-channel s, ρg,sas the indication of whether group g is available on sub-channel s, psas the power assigned over sub-channel s, N0as power spectral density of additive white Gaussian noise (AWGN).

DRA is realized in a centralized way in this system which indicates that BS determines the corresponding sub-channels and the maximum power budget for different groups to make sure each user in the group can reliably receive the data stream. In this paper, BS transmits data at worst user’s rate so that even the worst user (user with worst channel conditions) is able to reliably decode any of the received data. Based on the assumption in [15], the total data rate of one specic group g is dened as Eq.1:

The binary variable ρg,sin Eq. 3 represents the allocation of subcarrier s to group g. In Eq. 4,is data rate ratio among all groups. Because of Eq. 3 and Eq. 4, this problem is obviously a non-convex one. The optimal sub-channels and power allocation should be jointly optimized with ES which can be proved extremely difficult to realize and not suitable for the dynamic nature of wireless channels. So this paper brings up a suboptimal algorithm preferable for cost-effective and delay-sensitive implementations.

III. CONSTRAINED TEAM PROGRESS ALGORITHM (CTPA)

Sub-channels allocation is a multi-modal matrix-based optimization problem with constraints. However, the traditional EAs are unconstrained optimization tools which manipulate trial solutions with selection or updating procedure based on evaluations. Therefore, a penalty mechanism to penalize any individual who violates constraints would easily come to mind. Besides, for any of these traditional algorithms, parameter tuning and penalty weights selection are the challenging part in realization.

Fig. 1. Multicast OFDM-based system model.

Team progress algorithm (TPA) [14], which can be described as human progress ideas of exploration and learning, cannd the optimal solutions efficiently without complicated pa-rameter tuning. In the progress process, there are two groups: plain one and elite one, new member candidates should go through inheritance, learning and/or exploration procedure to enter one group and the new groups should go through replacement or elimination to refresh themselves. Replacement and elimination are designed for behavior division and keeping two groups from assimilation.

Subject to certain constraints, we design an auxiliary objection function which converts the original problem into bi-objective one based on whether the individual is within the feasible region or not.

This identification describes the deviation from the assigned data rate ratio to measure how well the fairness is maintained. For Eq. 5,when ?=0, it means that the rates of every group strictly follow the pre-determined data rate ratio, when ?≠0, this identification is taken as the other objective function instead of maximization of system capacity. The optimization means the rates ratio gets closer to the pre-assigned ratio value.

Fig. 2. Channel conditions in multicast system.

IV. PROBLEM FORMULATION AND SOLUTION

This approach allocates sub-channels assuming equal power on all sub-channels based on CTPA, followed by power adjustment employing MPA.

4.1 Sub-channels assignment based on CTPA

We consider a multicast OFDMA system with totalQusers overSsub-channels in which the BS transmits toGmulticast groups, each having equalusers. In one group:hi,jrepresents the channel condition of userion sub-channelj. Take a system withG=4,Q=16,S=16 for example:For each group: there are 4 users which have channel conditions as ingure 2.

Thus there are 4 arrays to represent channel condition of the 4 groups to form a new matrixin whichhg,srepresents the channel condition of thegth group on thesth sub-channel. The channel availability matrixis aGbySbinary matrix representing the channel availability, wherelg,s=1 if and only if the channelsis available to user in the groupg, and otherwise.

The different group selection pattern over all sub-channels can be formulated asrepresents one particular group was selected to transmit data on sub-channeli. This pattern contains the information of selected sub-channels condition which is the matrix of H×L because of the mapping relation between group selection pattern and selected channel condition.

With the assumption of equal power over all sub-channels and selected channel conditions, the fitness (data rate or violations)value of each member can be calculated like the aforementioned part: When the constraints are satised, the objective is to maximize the system capacity. On the contrary, the goal is to optimize the group selection to attain proportional fairness when the constraints are not satised.

Therefore, a suitable group selection pattern over all sub-channels which can achieve the optimal system capacity while maintaining the proportional fairness constraint can be obtained through Algorithm 1.

Because it is infeasible to be verified in a more complicated system with large number of sub-channels and groups, we take a simple scenario with 2 groups over 8 sub-channels for example just to explain it. The proportional fairness index is dened asγ1:γ2=1:1. With equally distributed power, as we can see in figure 3, the proposed algorithm can achieve 98% of the optimal ES.

4.2. Power allocation: mappingpower algorithm

It is convenient to construct group power -capacity matrix as in Table.1 accordingly employing water-lling algorithm. The matrices are determined by two elements: the power allocated to this specific group, the worst channel condition in this group. MPA can fully exploit the mapping relation between power and capacity as Algorithm.2.

The computation complexity is reduced by increasing the physical storage cost. The results can be as good as ES with a low computational cost. The accuracy of power is dened aswhich means total power is divided intounits as in Table.1.

Algorithm 1: Constrained team progress algorithm (CTPA)

Input:

system parameters: group numberG, user number per groupq, sub-channels numberS, power budget at BSPtot;

the CTPA algorithm parameters: team members:N+M, learning probabilityl, contraction exponentsαeandαp, the search accuracy for the function optimizationδ, the maximal iterations to terminate the searchK;

Output:

The sub-channels allocation assignment

1. Calculate the auxiliary objective function as Equ.5 to select appropriate operation.

If ?=0, optimize the sum capacity, otherwise, optimize Equ.5 as objective function.

2. for k=1 to K do

3. Among all the team members, calculate theirtness values, determine theNelite group members and theMplain group members, find the best member xopt, the last elitist xewstand the last member xwst;

5.k=k+1, ifk＞Kstop the search and export xopt. Otherwise, go to next step.6. Generate a random binary integers. Ifs=0, select the elite group; otherwise select the plain group, to generate the new individual xr.

7. Generate a random real numberr∈(0,1). Ifr＜l, perform learning. Otherwise,take exploration.

8. Obtain xcand evaluate the candidate byf(xc) . Go to step 10).

9. Ifs=0, calculate xcwithαe. Otherwise, obtain xcusingαp. Evaluate the candidate byGo to the next step.

12. return: The sub-channels allocation assignment

4.3 Scheme analysis

For this NP-hard problem, there areGSsolutions of sub-channels allocation and each allocation needsSiterations of power allocation.Therefore it has a complexity of(SGS).

Table I. Matrix mapping relation.

The complexity analysis of related algorithms is described in Table 2.

In terms of sub-channels allocation, bandwidth control-separate optimization (BC-SO),reduced-complexity bandwidth control separate optimization (RCBC-SO) and bandwidth control genetic algorithm (BC-GA) [10] try to maintain proportional fairness by allocating axed number of sub-channels regardless of different channel conditions. The proposed CTPA outperforms GA for two reasons. One is the parameters selection of CTPA is easier than parameters tuning of GA according to[14] and [15]. The other one is computational complexity. The complexity of any GA based scheme isdepending on the maximum number of generationsVmaxand the population sizeNp. Considering GA with constraint, the only difference lies in thetness value calculation. Obviously, no extra calculation step is required. However,Vmaxmay increase slightly to attain the optimal solution because the optimization process is iteratively optimizing the bi-objective function.Therefore the constrained GA (CGA) has the same complexity ofas BC-GA [10]. CTPA has a lower complexity((N+M)×S) compared with GA. We assume the same constraint penalty method is utilized by BC-SO, RCBC-SO and BC-GA[10].

In terms of power assignment, although in [15] it has a complexity of(G), but it breaks the proportional fairness for employing water-lling algorithm within each group.Thus the proposed MPA is obviously better for strictly following proportional fairness ratio by considering water-lling procedure atrst.The complexity of MPA is(A×G) which is acceptable directly related to the accuracyAof power.

Fig. 3. The ef ciency of CTPA.

Algorithm 2: Matrix-Mapping Algorithm

Input:Output:

system parameters: group numberG, user number per groupq, sub-channels numberS, power budget at BSPtot, the channel conditions;

the selected sub-channel pattern

The power assignment for each group

1. Initialization: Leti=1,

2. FindCgroup_1in table for group_1 accordingly. Calculateaccordingly;

3. fork=1 toKdo

4. Subject toCgroup_2,Cgroup_3,...Cgroup_G,ndPgroup_2,Pgroup_3,...Pgroup_Gthrough the corresponding tables;

8. return: The power assignment for each group

V. SIMULATION

In this multicast system, BS transmits data toG=4 groups overS=16 sub-channels. Each group has userstell the differences between each multicast group, group 1 is set to have a path loss advantage of 1.5 dB over group 2, and of 3 dB over group 3 and group 4. The multiple sets of independent channel gainshq,mwere generated randomly with Rayleigh distribution to describe the channel condition of userqover sub-channelm. To prole the situation, average channel gain of group 1, the sub-channel bandwidthB0and the noise powerN0are normalized to 1. The parameters are selected according to system scale.

The sub-channels allocation scheme advantage is analyzed by comparing to BC-SO,RCBC-SO and BC-GA [10]. The power assignment superiority is proved by comparisons among equal power algorithm (EPA) and optimal power algorithm (OP) proposed in [15].

5.1 Proportional fairness constraint indices are set as: γ1 :γ 2 :γ 3 :γ 4=0

It can be interpreted as a free competition among groups to attain as much resources as they can because the groups with better channel conditions will secure more resources. Figure 4 displays the variation tendency of total system capacityCtotwith transmit power budgetPtot. CTPA-MPA and CTPA-OP provide slightly better sum capacity as compared to all other schemes. With no proportional fairness constraint, they all utilize the water-filling procedure over all sub-channels, while CTPA-EPA performs equal power allocation.

Table II. Complexity analysis.

Figure 5 and figure 6 show the bandwidth allocation and the data rates among all groups which verify that more available resources are assigned to groups with better conditions to achieve a better performance. The advantage becomes smaller in the higher total power region which is understandable. Refer to the multicast system model we set (group 1 has an advantage over group 2 , 3 and 4), this set of figures shows that all algorithms assign more resource (data rates/sub-channels) to the group with better channel gains as analyzed before.

5.2 Proportional fairness constraint indices are set as:γ1 :γ2 :γ3 :γ4=4:2:1:1

Considering the channel condition differences assumed, we set a matching data rata ratio just to explain the case. This ratio can be set as any rational value as well. The sum rates attained follow similar trend ingure 7 as in the first case.

Fig. 4. Sum capacity (γ1 :γ 2 :γ 3 :γ 4=0).

Fig. 5. Sub-channel allocation (γ1 :γ 2 :γ 3 :γ 4=0).

More importantly, referring to figure 7 and figure 9, CTPA-MPA strictly sticks to the normalized data rate ratio among all groups with a better system capacity performance comparing with other algorithms. The imbalance coefcient of normalized group capacity of CTPA-MPA ? is 0 in all power region which means that the capacity of every group strictly follow the pre-determined ratio. As for CTPA-OP, take total transmit power is 0 dB for example, the imbalance coefficient of normalized group capacity is?==2.95e?04.The deviations from the assigned indicesof other algorithms are even worse which is obvious in figure 9.As shown ingure 8, instead of axed number of sub-channels allocated to each group like BC-SO, RCBC-SO and BC-GA, the total bandwidth in terms of sub-channels was distributed more flexibly with CTPA. It can be concluded fromgure 8 andgure 9 that proportional sub-channel allocation may not provide proportional fairness of data rates to each groups in multicast system for the fact that different channels have different gains for different groups. Furthermore, comparing the results of CTPA-MPA, CTPA-OP and CTPA-EPA, it can be verified that MPA further guarantees the fairness of data rates as compared to the optimal power scheme utilized in CTPA-OP and equal power allocation employing by CTPA -EPA. This advantage will become more obvious when the number of sub-channels, users and groups are larger which can be proved later in this section.

Fig. 6. Group capacity (γ1 :γ 2 :γ 3 :γ 4=0).

Fig. 7. Sum capacity (γ :γ :γ :γ =4:2:1:1).1 2 3 4

Fig. 8. Sub-channel allocation(γ1 :γ 2 :γ 3 :γ 4=4:2:1:1).

5.3 Proportional fairness constraint indices are set as:γ1 :γ 2 :γ 3 :γ 4=1:1:1:1

The aim of this set is to keep all groups transmit data with same rate. It can be observed that the sum capacity of each algorithm keeps the same linear tendency in figure 10. The system capacity is increased by 19% in lower power region compared with CTPA-OP. The total bandwidth is divided more evenly among all groups as shown ingure 11.

Fig. 9. Group capacity (γ1 :γ 2 :γ 3 :γ 4=4:2:1:1).

Fig. 10. Sum capacity (γ1 :γ 2 :γ 3 :γ 4=1:1:1:1).

Fig. 11. Sub-channel allocation(γ1 :γ 2 :γ 3 :γ 4=1:1:1:1).

Still, same as the case of proportional fairness constraint indices setit can be veried again fromgure 12 that the CTPA-MPA algorithm sticks strictly to the normalized fairness variableγcomparing to the data rates obtained by all other schemes. Take bothgure 11 and figure 12 into consideration, the fact that allocating axed number of sub-channels to maintain fairness as BC-SO, RCBC-SO and BC-GA may not provide fairness of data rates to different groups with different channel conditions. So with a flexible sub-channels allocation scheme, CTPA-OP sticks more closely to the normalized fairness variableγcomparing to BC-SO, RCBC-SO and BC-GA.But through a MPA, CTPA-MPA outperforms CTPA-OP by further guaranteeing the fairness of data rates in the power assignment procedure.

The imbalance coefficient of normalized group capacity of CTPA-MPA ? is still 0 in all power region which means that the capacity of every group strictly follow the ra-As for CTPA-OP,take total transmit power is 1 for example, the imbalance coefcient of normalized group capacity is?=6.16e?04. The deviations from the assigned proportional fairness indices of other algorithms are even worse which is obvious ingure 12.

5.4 System with larger number of sub-channels, groups and users

The sub-channels number and groups number are set asS=128 andG=16, each group hasqg=8 users. The groups of 1-4 have an advantage of 3 dB over the groups of 5-8 and the groups of 9-16 have advantage of 1.5 dB over the groups of 5-8. The proportional fairness constraint indices are set to 1.

In figure 13, all algorithms follow the same tendency as in simple scenario. The CTPA-MPA provides slightly higher sum capacity comparing to BC-SO, RCBC-SO and BC-GA as expectation. Furthermore, figure 14 shows that BC-SO, RCBC-SO and BCGA allocate same number of sub-channels to all the groups. CTPA-MPA, CTPA-OP and CTPA-EPA perform a flexible sub-channels allocation according to different channel conditions. Figure 15 shows that CGA-MPA outperforms all other algorithms in terms of keeping the proportional fairness. The imbalance coefficient of normalized group capacity of CTPA-MPA is 0 which means that the capacity of every group strictly follow the pre-determined indices. As for CTPA-OP, take total transmit power is 5 dB for example, the imbalance coefficient of normalized group capacity is ?==5.58e?05. The deviations from the assigned indices of other algorithms are even worse which is obvious ingure 15.

Fig. 12. Group capacity (γ1 :γ 2 :γ 3 :γ 4=1:1:1:1).

Fig. 13. Sum capacity (γ all set to 1).

Fig. 14. Sub-channel allocation(γ all set to 1).

VI. CONCLUSION

This paper proposes a suboptimal solution with a low complexity which optimizes the sub-channels allocation and power assignment sequentially.

CTPA optimizes non-convex problem of sub-channels allocation with proportional fairness constraint which aims at maximizing throughput while satisfies the proportional fairness constraint. The challenge of power assignment which intends to utilize power efficiently with the strict proportional fairness constraint can be realized by the proposed MPA conveniently. The proposed DRA scheme based on CTPA-MPA improves the performance in a typical scenario with 4 groups over 16 sub-channels, while reducing the complexity from exponential to linear. It is also efcient in a more complicated system with 16 groups over 128 sub-channels.

Fig. 15. Group capacity (γ all set to 1).

[1] Hartung F, Horn U, Huschke J, et al. “Delivery of broadcast services in 3G networks,”IEEE Transactions on Broadcasting, vol. 53, no. 1, 2007, pp.188-199.

[2] Correia A M C, Silva J C M, Souto N M B, et al.“Multi-Resolution Broadcast/Multicast Systems for MBMS,”IEEE Transactions on Broadcasting,vol. 53, no. 1, 2007, pp. 224-234.

[3] Shariat M, Quddus A U, Ghorashi S A, et al.“Scheduling as an important cross-layer operation for emerging broadband wireless systems,”IEEE Communications Surveys & Tutorials,vol.11, no. 2, 2009, pp. 74-86.

[4] Sadr S, Anpalagan A, Raahemifar K. “Radio Resource Allocation Algorithms for the Downlink of Multiuser OFDM Communication Systems,”IEEE Communications Surveys & Tutorials,vol.11, no. 3, 2009, pp. 92-106.

[5] Afolabi R O, Dadlani A, Kim K. “Multicast Scheduling and Resource Allocation Algorithms for OFDMA-Based Systems: A Survey,”IEEE Communications Surveys & Tutorials,vol. 15, no. 1,2013, pp. 240-254.

[6] Xu J, Lee S J, Kang W S, et al. “Adaptive Resource Allocation for MIMO-OFDM Based Wireless Multicast Systems,”IEEE Transactions on Broadcasting,vol. 56, no. 1, 2010, pp. 98-102.

[7] Ngo D T, Tellambura C, Nguyen H H. “Eff cient Resource Allocation for OFDMA Multicast Systems With Spectrum-Sharing Control,”IEEE Transactions on Vehicular Technology,vol. 58,no. 9, 2009, pp. 4878-4889.

[8] Agashe P, Rezaiifar R, Bender P. “QUALCOMM.cdma2000 high rate broadcast packet data air interface design,”Communications Magazine IEEE,vol. 42, no. 2, 2004, pp. 83-89.

[9] Liu J, Chen W, Cao Z, et al. “Dynamic Power and Sub-Carrier Allocation for OFDMA-Based Wireless Multicast Systems,”P(pán)roc. IEEE International Conference on Communications, 2008, pp.2607-2611.

[10] Koh C H, Kim Y Y. “A Proportional Fair Scheduling for Multicast Services in Wireless Cellular Networks,”P(pán)roc. Vehicular Technology Conference,2006, pp. 1-5.

[11] Galletly J. “Evolutionary Algorithms in Theory and Practice,” Oxford Univ. Pr, 1998.

[12] Back T, Hammel U, Schwefel H P. “Evolutionary computation: comments on the history and current state,”IEEE Transactions on Evolutionary Computation,vol. 1, no. 1, 1997, pp. 3-17.

[13] Eberhart R, Kennedy J, ‘’A new optimizer using particle swarm theory,’Proc. IEEE International Symposium on MICRO Machine and Human Science,1995, pp. 39-43.

[14] Bo Y, Liu B. “An epitome-based evolutionary algorithm with behavior division for multimodal optimizations,”P(pán)roc. International Conference on Neural Networks and Signal Processing,2008, pp. 406-411.

[15] Sharma N, Madhukumar A S, “Genetic Algorithm Aided Proportional Fair Resource Allocation in Multicast OFDM Systems,”IEEE Transactions on Broadcasting,vol. 61, no. 1, 2015, pp.16-29.