Xiang Chen, Fei He, Limin Xiao, Shidong Zhou

1 School of Electronics and Information Technology, SYSU-CMU Shunde International Joint Research Institute, Sun Yat-sen Univ.,Guangzhou, 510006, China

2 Key Lab of EDA, Research Institute of Tsinghua University in Shenzhen, Shenzhen, 518057, China

3 China Academy of Electronics and Information Technology, Beijing, 100041, China

4 EE Department, Research Institute of Information Technology, TNList, Tsinghua University, Beijing, 100084, China

* The corresponding author, email:chenxiang@mail.sysu.edu.cn

I. INTRODUCTION

Orthogonal frequency division multiplexing(OFDM) two-way relaying is a cost-efficient technique to realize coverage extension and throughput enhancement in fifth generation(5G) wireless networks, which has been firstly advocated in many 4G standards, including IEEE 802.16m and 3GPP advanced long term evolution (LTE-Advanced) [1,2]. When multiple users are served simultaneously by the single OFDM based two-way relay, different users will go through different fading, which results in multi-user diversity beneficial to improve system performance.

There are many previous works investigating the multiuser access, signal processing and resource allocation optimization problem in the above multiuser OFDM based two-way relay system [3-14]. In [3], a Code Division Multiple Access(CDMA) based scheme is considered for single relay aided two-way multiuser communications, however the system capacity is limited by multiuser interference in CDMA. [4] then takes F/TDMA instead of CDMA to maximize the weighted system sum rates by proper power allocation for different relaying strategies. [5,6] investigate the joint power, subcarrier allocation optimization problem in Amplify-and-Forward(AF) relay networks, in which [6] further considered a multiple-relay aided case involving relay selection in the optimization procedure. In the contrary, the multiple Decode-and-Forward(DF)-relay based resource allocation problem is considered in [7], and proportional fairness user scheduling is performed to improve system performance. [8] then systematively solves the resource allocation problem for AF/DF relay networks, when the direct link between the base-station and terminals, and the one-way/two-way relay nodes coexist in the system. Regarding the combinatorial optimization problem raised in [8-10], an alternative graph theory based method is proposed, in which Hungarian method is adopted to solve the subcarrier pairing for OFDM based relays.Literatures [11-14] investigate the two-way MIMO relays systems to optimize system throughput from the aspects of signal processing, while cannot be directly applied to OFDM systems.

This paper studied joint subcarrier and power allocation for DF-based multiuser two-way relay network. A generalized subcarrier pairing strategy was proposed and solved by a low complexity Lagrange duality decomposition-based method.

It should be noted that, all the above literatures only consider the independent coding for each subcarrier in OFDM based relay networks. However, it has been proved, by joint coding across multiple subcarriers for OFDM relay systems will obviously help to improve system spectrum efficiency [10]. Therefore,we will firstly take multi-subcarrier DF relay strategy [10] into the multiuser case, then try to solve the resource allocation problem by low complexity algorithms. The main contributions of this paper are summarized as follows:

(1) For an OFDM based single two-way relay aided network, we firstly propose a generalized subcarrier pairing (GSP) strategy,permitting each user-pair to occupy different subcarriers during the multiple access (MA)and broadcast (BC) phases. Each user-pair can perform joint coding cross the allocated subcarriers to avoid the one-to-one mapping in traditional subcarrier pairing [7,8,9], reducing the complexity of multiuser scheduling.

(2) The non-convex resource allocation problem for multiuser OFDM based twoway relay networks by the GSP is formulated,which is then solved by low complexity Lagrange duality decomposition based method.By Lagrange duality decomposition, the power and subcarrier allocation for two phases can be optimized independently, reducing the complexity of resource allocation, simultaneously obtain additional multiuser diversity.

The rest of this paper is organized as follows. Section II presents the system model.Section III describes the novel GSP strategy,and formulates the joint resource allocation problem to characterize the corresponding achievable rate region. The duality-based resource allocation algorithm is developed in Section IV. Some numerical results are presented in Section V. Finally, Section VI draws some conclusions.

Notation: Throughout this paper, we use bold lowercase letters to denote column vectors, and we also denote ann×1 column vector bymeans that each component of column vectorpis nonnegative.denotes the statistical expectation of the argument.

II. SYSTEM MODEL

Fig. 1 System model of OFDM based DF two-way relay network, including generalized subcarrier pairing strategy

We consider a multiuser two-way OFDM relay network withNsubcarriers, whereKpairs of terminal nodesandexchange messages by virtue of an intermediate relay node.Each time frame of a two-way DF relay strategy consists of two phases: a multiple-access phase and a broadcast phase, as illustrated in Fig.1.

In the multiple-access phase, the terminal nodesandsimultaneously transmit their messages to the relay nodethen the relay nodedecodes its received messages,re-encodes them into a new codeword, and broadcasts it to the terminal nodesandin the broadcast phase. The time proportion of the multiple-access phase is denoted as μ for 0＜μ＜1, and so the time proportion of the broadcast phase is 1-μ. We further defineas the binary variables for the subcarrier allocation in the MA and BC phases, respectively, such thatif themth subcarrier is allocated to thekth terminal pair in the multiple-access phase, whileotherwise; andif thenth subcarrier is allocated to thekth terminal pair in the broadcast phase, whileotherwise.Since during each relay phase each subcarrier can only be allocated to one user-pair, the subcarrier allocation policy also should satisfy the following constraint:

In the traditional subcarrier pairing strategy in OFDM two-way relay networks[8,9],during the MA and BC phases, the allocated subcarrier group for each user-pair will always be the same, i.e.,for alandIn the same time, each user-pair only consider independent coding over each subcarrier, without considering joint coding cross multiple subcarriers[10]. Obviously, by the above fixed subcarrier allocation strategy for different relay phases for each user-pair, the multiuser diversity cannot be fully obtained, resulting in sum rate loss. The complexity of subcarrier allocation for each user-pair is also a NP-hard problem. Therefore,in the next section, we will firstly propose a novel GSP strategy to reduce the subcarrier allocation complexity, simultaneously guaranteeing multiuser diversity.

III. GENERALIZED SUBCARRIER PAIRING AND RESOURCE ALLOCATION PROBLEM FORMULATION

3.1 Generalized subcarrier pairing strategy

In Fig.1, the numbers over the arrow lines mean the allocated subcarrier indices for the related user-pair. For example, for the 1st user-pair, during the MA phase,subcarriers are allocated for joint coding transmission, whilesubcarriers are allocated for BC phase. Similarly, forKth user-pair,during the MA phase,subcarriers are allocated for joint coding transmission, whilesubcarriers are allocated for BC phase.Obviously, the GSP is different from the traditional subcarrier pairing by allocating the same indicesandfor MA and BC phases.In fact, in traditional subcarrier pairing strategy[8,9], the same subcarrier allocation during the two phases limits the degree of freedom for channel matching, resulting in sum rate loss. In virtue of joint coding DF scheme[10],the one-to-one mapping of traditional subcarrier pairing is no longer necessary, so the adaptive rate allocation among multiple subcarriers is also no longer needed.

In our GSP strategy with joint coding DF transmission scheme, only one channel coder/decoder pair is needed for each user node,while at the relay node one channel coder/decoder pair is equipped for each user-pair.So the total number of channel coder/decoder pairs in such scheme needs to be 6K. For traditional independently coding DF transmission for each subcarrier [10], the total number of channel coder/decoder pairs should be 6N. In general, the number of subcarrierNis much larger than the number of user-pairK, so by our proposed GSP algorithm, the number of channel coder/decoder pairs involved in the system can be reduced obviously due to the joint subcarriers channel coding scheme, simultaneously resulting in the following low complexity resource allocation schemes in Section IV.

3.2 Resource allocation problem formulation

In this subsection, we will formulate the joint power and subcarrier allocation problem.

As Fig.1 shows, in the multiple-access phase, the received signalYRmof the relay nodeover subcarriermis expressed as

Each node is subject to an individual power constraint, i.e.,

IV. LOW-COMPLEXITY RESOURCE ALLOCATION ALGORITHM

It is easily known that (5) is a mixed integer non-linear programming problem, and thus an exhaustive search overis required to find the optimal solution. Thanks to [19], we know that the duality gap between the primal problem and the dual problem in a multi-carrier system approaches to zero for a sufficiently large number of subcarriers. Thus we can bottom at this page, wherefor allandare nonnegative dual variables solve the dual problem instead of the original problem.

Let us define the partial Lagrange dual function of problem (5) as (6) shown in the associated with five rate inequality constraints and two power inequality constraints for thekth terminal pair, respectively, andis the nonnegative dual variable associated with power inequality constraint for relay terminal. Then, the corresponding dual problem is defined as [16]

4.1 Lagrange dual decomposition for dual function

For any given dual variablesthe dual function can be re-expressed as (8) shown in the bottom at this page.

4.2 Power allocation

We solve (9) for allk, m, thus there are totalKNsub-problems. Fortunately, we can derive closed-form solutions to problem (9) by the following Karush-Kuhn-Tucker (KKT) conditions

1)Case 1In this case,theKKTconditions (11a) and (11b) both hold with equality. Therefore, we need to solve a system ofquadraticequations with two variables. To simplify this problem, we define an auxiliary variable

Then, by (11a) and (11b) and through some derivations, we obtain

By substituting (13a) and (13b) into (12),we end up with the followingcubicequation ofx:

and its closed-form solutions are given by Cardano’s formula [17]. After obtaining the positive real root x of (14), we can easily obtain the optimalby substituting x into (13).

2)Case 2:. Then the solutions to (11a) and (11b) are given by

3) Case 3:Then the solutions to (11a) and (11b) are given by

4) Case 4:This is the default case when the above 3 cases do not happen.

Similarly, we solve (10) for allk; n, thus there are alsoKNsub-problems. According to theKKTcondition

If (18) has no positive root, then

4.3 Subcarrier allocation

Substituting optimal power values, andinto (8), we obtain (19) shown in the bottom at this page, whereis obtained by substitutinginto the objective function of (9), andis obtained by substitutinginto the objective function of (10).

From (19), the optimal subcarrier allocation is given by

Each maximization operation in (20) has the complexity ofO(K) and the total complexity of subcarrier allocation thus isO(KN),where the complexity is defined as that in[9,19].

4.4 Dual update with subgradient method

Next we solve the dual problem (7) to find the optimal values of dual variables. By the subgradient method [18], we set initial dual variablesandto find the optimal power allocation in (9) and (10) and the optimal subcarrier allocation in (20). Then, with the obtainedunderandafterlth iteration, the dual variables at (l+1)th iteration should be updated as (21) shown in the bottom at this page.

for allk, where,andis an appropriate step size of thelth iteration to guarantee the convergence of the sub-gradient method [18], and (21d) and (21e) are due to the fact that the partial derivations of (6) with respect toare both equal to zero.The iteration will be stopped once certain criterion is fulfilled. Finally, we normalize the convergedandso that the power constraint at each terminal node is satisfied.

V. NUMERICAL RESULTS

In this section, numerical results are provided to illustrate the achievable rate performance of the proposed GSP strategy fulfilled by the proposed optimal power allocation. The wireless channels are generated by usingMindependently Rayleigh distributed time-domain taps with unit variance. We assume thatfor alli, k, n, i.e., the wireless channels betweenandTRare reciprocal, and thus. The time proportion of the multiple-access phase used isμ=0.5 and the maximum total transmission power for all the nodes are the same, i.e.,. Thus, the average signal-to-noiseratios (SNR) of the wireless links are given byAll simulations in this section are performed under the symmetric channel scenario, i.e.We also set

Fig.2 presents the averaged system sum rates vs. SNR, by our proposed GSP and traditional subcarrier pairing scheme, respectively.For each SNR, the results are obtained averagely over 500 independent channel realizations. For simplicity, the user-pair number is set asThe traditional subcarrier pairing scheme is deduced from [5]1The resource allocation scheme in [5] is originally designed for AF relay systems. Due to no more DF-based comparative objectives in current literatures, we have to modify the subcarrier pairing scheme of [5]combined with our power allocation solution by(11) to perform traditional resource allocation (i.e.,called “traditional subcarrier pairing scheme”in this paper) for DF relay networks. The corresponding upper bound proposed by AF scheme in [5] is also changed as Fig.2 shows.combined with power allocation closed-form solution for DF relay networks in Subsection IV.B. From Fig.2 it can be seen that, the achieved system spectrum efficiency by the GSP is obviously higher than that by the traditional method. If we regard the optimal solution of the dual problem(7) as the performance upper bound (drawn by solid line), the performance obtained by the GSP approaches to the bound with a negligible gap, verifying the asymptotic optimal solution by the Lagrange dual decomposition in Section IV.

Fig. 2 Averaged sum rates vs. SNR by the GSP (marked by square) and traditional subcarrier pairing (Traditional SP, marked by triangle), K=2

Fig. 3 Averaged sum rates vs. SNR by different subcarrier allocation and power allocation schemes

In Fig.3, we further compare the averaged sum rates by different subcarrier allocation(-SA) schemes under different number of user groups. The used SA schemes include: (I) the optimal solution SA by (20); (II) the fixed block subcarrier allocation (i.e., Block SA).Here, we only user Block SA as the basic comparison to discuss the tradeoff between system control complexity and the system performance, while the approximate optimality of the GSP has been proved in Fig.2. For the Block SA, we assign the subcarriers with indicesto thekth user-pair (for simplicity, assumeto be an integer), and the SA keeps the same during the two phases, i.e., MA and BS phases. We use the power allocation scheme by Subsection IV.B for the Block SA scheme. It can be seen that, for fixed, the optimal SA outperforms the Block SA in terms of averaged sum rates.We also compare the performance under different user-pair numbers,Whenall the subcarriers are allocated to only one user-pair, so the performance is the same as that of [10]. From Fig.3, along with the increase of number of user-pair, the averaged sum rates are improved, adequately showing the multiuser diversity gain.

VI. CONCLUSIONS

In this paper, we investigate the resource allocation problem in the OFDM based multiuser two-way relay networks, including power and subcarrier allocation. The joint coding DF scheme [10] is firstly incorporated to enlarge the achievable rate region compared with the existing per-subcarrier DF relay strategies for the multiuser DF relay case. Then the GSP is proposed to reduce the complexity of resource allocation and user scheduling in multiuser scenarios. In order to solve the non-convex resource allocation problem under the above scheme, a low complexity Lagrange dual decomposition based method is proposed to maximize the system sum rates. Numerical simulations show that, by the proposed GSP,the system spectrum efficiency will be evidently improved, with the multiuser diversity guaranteed.

ACKNOWLEDGEMENTS

The authors would like to thank the reviewers for their detailed reviews and constructive comments, which have helped improve the quality of this paper. The work is supported by the National Natural Science Foundation of China (NSFC) (No. 61501527), State’s Key Project of Research and Development Plan (No. 2016YFE0122900-3), the Fundamental Research Funds for the Central Universities, Basic Research Foundation of Science Technology and Innovation Commission of Shenzhen Municipality (No.JCYJ20150630153033410) SYSU-CMU Shunde International Joint Research Institute and 2016 Major Project of Collaborative Innovation in Guangzhou (Research and Application of Ground Satellite Communicaiton Systems for Space Broadband Information Networks).

[1] M. Salem, A. Adinoyi, M. Rahman, H. Yanikomeroglu, D. Falconer, Y.-D. Kim,E. Kim, and Y.-C. Cheong. An overview of radio resource management in relay-enhanced OFDMA-based networks[J], IEEE Commun. Surv. Tutorials, 2010,12(3): 422–438.

[2] H. Zhang, Y. Liu, and M. Tao. Resource allocation with subcarrier pairing in OFDMA two-way relay networks[J]. IEEE Wireless Commun. Lett., 2012,1(4): 61–64.

[3] Chen M, Yener A. Multiuser two-way relaying:Detection and interference management strategies[J]. IEEE Trans. Wireless Commun., 2009,8(8):4296–4305.

[4] Chen M, Yener A. Power Allocation for F/TDMA Multiuser Two-way Relay Networks[J]. IEEE Trans. Wireless Commun., 2010, 9(2):546–551.

[5] Sidhu G A S, Gao F, Chen W, et al. A Joint Resource Allocation Scheme for Multiuser Two-Way Relay Networks[J]. IEEE Trans. Commun.,2011, 59(11):2970–2975.

[6] Zhang H, Liu Y, Tao M. Resource Allocation with Subcarrier Pairing in OFDMA Two-Way Relay Networks[J]. IEEE Wireless Commun. Lett., 2012,1(2):61–64.

[7] Shin H, Lee J H. Joint Resource Allocation for Multiuser Two-Way OFDMA Relay Networks with Proportional Fairness[C]. Proceedings of IEEE VTC’11 Fall, 2011.

[8] Jitvanichphaibool K, Zhang R, Liang Y C. Optimal Resource Allocation for Two-Way Relay-Assisted OFDMA[J]. IEEE Trans. Veh. Technol.,2009, 58(7):3311–3321.

[9] Liu Y, Tao M, Li B, et al. Optimization Framework and Graph-Based Approach for Relay-Assisted Bidirectional OFDMA Cellular Networks[J]. IEEE Trans. Wireless Commun., 2010, 9(11):3490–3500.

[10] Fei He, Yin Sun, Limin Xiao, Xiang Chen, Chong-Yung Chi, Shidong Zhou. Capacity Region Bounds and Resource Allocation for Two-Way OFDM Relay Channels[J]. IEEE Transactions on Wireless Communications, 2013, 12(6): 2904-2917.

[11] Chengwen Xing, Ying Ma, Yiqing Zhou and Feifei Gao. Transceiver Optimization for Multi-Hop Communications with Per-Antenna Power Constraints[J]. IEEE Transactions on Signal Processing, 2016, 64(6): 1519-1534.

[12] Chengwen Xing, Feifei Gao, and Yiqing Zhou.A Framework for Transceiver Designs for Multi-Hop Communications with Covariance Shaping Constraints[J]. IEEE Transactions on Signal Processing, 2015, 63(15): 3930-3945.

[13] Chengwen Xing, Shaodan Ma, and Yiqing Zhou.Matrix-Monotonic Optimization for MIMO Systems[J]. IEEE Transactions on Signal Processing,2015, 63(2): 334-348.

[14] Chengwen Xing, Shaodan Ma and Yik-Chung Wu. Robust Joint Design of Linear Relay Precoder and Destination Equalizer for Dual-Hop Amplify-and-Forward MIMO Relay Systems[J].IEEE Transactions on Signal Processing, 2010,58(4): 2273-2283.

[15] W. Yu and R. Lui. Dual methods for nonconvex spectrum optimization of multicarrier systems[J]. IEEE Trans. Commun., 2006, 54(7):1310–1322.

[16] S. Boyd and L. Vandenberghe. Convex Optimization[M]. Cambridge, U.K.: Cambridge Univ.Press, 2004.

[17] W. Dunham. Cardano and the solution of the cubic. Journey through Genius: The Great Theorems of Mathematics[M]. New York: John Wiley& Sons, Inc., 1990: 133–154.

[18] S. Boyd and A. Mutapcic. Notes for EE364b:Subgradient methods[EB/OL]. Jan. 2007, Stanford University. Available:http://www.stanford.edu/class/ee364b/notes/subgradients notes.pdf

[19] G. A. S. Sidhu, F. Gao, W. Chen, and A. Nallanathan. A joint resource allocation scheme for multiuser two-way relay networks[J]. IEEE Trans.Commun., 2011, 59(11): 2970–2975.