Joint Optimization of Subcarrier-Pairing Based Channel Assignment and Relay Selection for MIMO Systems

DOI : 10.17577/IJERTV2IS4955

Download Full-Text PDF Cite this Publication

Text Only Version

Joint Optimization of Subcarrier-Pairing Based Channel Assignment and Relay Selection for MIMO Systems

V. SriRathiPriya, M. Methini

Sri Sai Ram Engineering College, Chennai


Usage of radio resources effectively in wireless networks is essential. This project studies where multiple user communicate via multiple relays based on orthogonal frequency division multiplexing (OFDM) in a wireless relay network transmission. The relay selection and relay assignment as well as subcarrier pairing and subcarrier allocation for total throughput enhancement is formulated as a combinatorial optimization problem. Simulations analyses are carried out to evaluate the network total throughput versus transmit power per node and the number of relay nodes by transforming it into a maximum weighted bipartite matching (MWBM) problem by utilizing a graph theoretical approach.

  1. Introduction

    Orthogonal frequency-division multiplexing (OFDM) based transmission is a method to allow high data rates over broadband wireless networks with relay architecture. In wireless networks relay based communication can improve the system performance such as extending the area coverage, power saving, improving the spectral efficiency, prolonging the network lifetime and increase the system throughput. It is very difficult to design resource allocation effectively includes selection of relay node, set of subcarriers to operate on and how much power to transmit the signals in OFDM- based relay networks in [1]. Multiple relays help multiple pairs of source nodes to conduct bidirectional communications is considered. The aim of the project lies to enhance the system overall throughput by optimally coordinating the relay and subcarrier assignment among the multiple pairs of two-way users.

    The joint optimization problem of subcarrier pairing based subcarrier assignment and relay selection for multiple user pair is considered as a

    combinatorial optimization problem in [2] and used a dual approach to solve the problem. In this paper a graph based approach is implemented to establish the equivalence between the proposed problem and a maximum weighted bipartite matching (MWBM) problem. Then the problem is solved by the corresponding graph based algorithm optimally in polynomial time. In relay assisted network with the frequency fading environment, the choices of relay node, relay strategy and the allocation of power and bandwidth for each users are important. In a cooperative network when a relay is located closer to the source than to destination a choice of Decode and Forward (DF) relay strategy consider where the received signal decoded prior to transmits. When a relay is located closer to the destination, its received signal-to-noise ratio(SNR) may not be high enough to allow decoding in which case Amplify and Forward(AF) strategy can be used. In AF the relays only amplify and may process the signal linearly before they transmit. Thus AF leads to low complexity relay transceivers and lower consumption since there is no need to signal processing for decoding procedures, but suffer from the noise amplification induced by the relay.

    Optimal resource allocation in relay-assisted orthogonal frequency division multiplexing (OFDM) communication system involves even more technical challenges. Compared with traditional single-hop OFDM or OFDMA systems, we need to carefully co-ordinate the power and subcarrier allocation across different hops resulting from multiple relays. Subcarrier-to-relay usually assumes that signals receive over one subcarrier, say n is amplified(or decode) and forwarded by the relay also over subcarrier n in the next hop. However, this is not optimal in terms of system performance. A better performance can be achieved if subcarriers in first and second hops are paired accordingly to their channel condition. The concept of subcarrier pairing was originally proposed in [3] independently for two-hop single relay OFDM-systems in particular, it is proved that the ordered subcarrier pairing is optimal for AF protocol. The AF relays are transparent to adaptive modulation techniques which may be employed by

    the source. The optimal gain matrix for an AF- MIMO relay which optimizes the instantaneous rate for a given uniform Power Allocation at the source is presented. Gain allocations with a MIMO first hop and second hop which considers Orthogonal channels to a single antenna destination.

    1. Jointly optimizing sub carrier-pairing

      A point-to-point Orthogonal Frequency Division Multiplexing (OFDM) system with Amplify and Forward (AF) relay is considered. The transmission consists of two hops. The source transmits in the first hop, and the relay transmits in the second hop. Each hop occupies one time slot. The relay is in half-duplex, and capable of decoding the message on a particular subcarrier in one time slot, and re-encoding and forwarding it on a different subcarrier in the next time slot. Thus each message is transmitted on a pair of subcarriers in two hops. It is assumed that the destination is capable of combining the signals from the source and the relay pertaining to the same message. The goal is to maximize the weighted sum rate of the system by jointly optimizing subcarrier pairing and power allocation on each subcarrier in each hop studied [4]. The weighting of the rates is to take into account the fact that different subcarriers may carry signals for different services. Both total and individual power constraints for the source and the relay are investigated. For the situations where the relay does not transmit on some subcarriers because doing so does not improve the weighted sum rate, we further allow the source to transmit new messages on these idle subcarriers. The problem is first formulated as a mixed integer programming problem. It is then transformed to a convex optimization problem by continuous relaxation, and solved in the dual domain. Based on the optimization results, algorithms to achieve feasible solutions are also proposed. Simulation results show that the proposed algorithms almost achieve the optimal weighted sum rate, and outperform the existing methods in various channel conditions.

  2. System Model

    In this work we consider K pairs of users and M relays as shown in Figure 1. where each user pair exchanges information via the relays. Each node operates in a half-duplex mode and for simplicity, the Amplify and- forward (AF) two-way

    relay strategy is adopted in [5]-[6]. The wireless fading environment by large-scale path loss and shadowing, along with small-scale frequency- selective fading is considered. Assume, (i) the channel between different links experience independent fading and the network operates in slow fading environment, so that channel estimation is perfect. (ii) A central controller is available in the network so that the centralized processing is possible. (iii) The additive white noises at all nodes are assumed to be independent circular symmetric complex Gaussian random variables and the direct communication link between the two users in each pair is neglected due to, for instance, the shadowing effects.

    Figure 1. OFDM-based wireless network with K pairs of users and M relays

    The two way communication takes place in two phases. The first phase is multiple-access (MAC) phase where all the pairs of users concurrently transmit signals to the relay nodes. In order to avoid inter-pair interference, each user pair occupies non-overlapping subcarriers. The intra- pair interference will be treated as back-propagated self interference and canceled perfectly fter two- way relaying. In the second phase, known as broadcast (BC) phase, the relay nodes amplify the received signal and then forwards to the 2 destinations. Again, each relay is operating on non overlapping subcarriers to avoid inter-relay interference.

  3. Problem Formulation

    The subcarriers are n and n in the first and second phase respectively. If the user pair is assigned with subcarrier and sends signals to relay in the first phase, the relay then broadcasts the amplified received signals on subcarrier in the second phase.

    The achievable sum rate is given by,

    This equation shows that the simplified P2 is equivalent to a maximum weighted bipartite

    n,n' 1 C








    r ,k 2

    matching (MWBM) problem.

    Rk ,r

    2 1 n'


  4. Bipartite Graph

    1 C




    k 2,r

    r ,k 2


    r ,k1


    k 2,r

    A bipartite graph is a graph whose vertices are



    r ,k1

    n k1,r

    k 2,r

    separated into two disjoint sets so that every edge connects a vertex in one set to one in another. If the

    two sets of vertices have the same cardinality, then

    C(x)=log (1+x) and n

    i, j

    denotes the instantaneous

    the bipartite graph is a balanced bipartite graph in [7]. A matching is a set of mutually disjoint edges,

    Signal-noise ratio (SNR) from node i to node j over

    subcarrier n, assuming that all the nodes have the unit noise variance. The main objective is to enhance the system total throughput by optimally pairing subcarriers in to two phases and selecting the best relays and the best paired subcarriers for each user pair. Mathematically, this can be formulated as (P1)

    i.e., any two edges do not share a common vertex. An example is shown in Figure 2(a). A perfect matching is a matching that every vertex in the graph is matched, an example of which is shown in Figure. 2(b). Note that perfect matching is the special case of matching. A balanced bipartite graph = (MAC× BC, ,), where the two set of vertices, MAC and BC, are the set of

    subcarriers in the MAC phase and the BC phase,


    max Rn,n' n,n'


    respectively, is constructed as shown in Figure.

    k K r M n N n' N

    k ,r

    k ,r

    2(c). is the set of edges that connect all possible


    n.n ' 1

    k ,r

    means that subcarrier n in the

    pairs of vertices in the two set of vertices. Note that

    is shared in each phase, thus |MAC| = BC =

    first phase is paired with subcarrier n in the second phase assisted by relay r for user pair k, else

    = and = 2, where is cardinality of a set. is the weighting function such that :

    n.n' 0

    k ,r

    otherwise. Problem P1 is a

    +. More specifically, each edge is assigned a

    weight, representing the maximum achievable rate

    combinatorial optimization problem and the optimal solution can be obtained by thorough search. The difficulty is exponential and thus excessive when K, M, and N are large. In this

    section, a graph based approach was proposed to

    over the matched two vertices. Namely,

    W(n,n') R(n,n')


    resolve the problem optimally in polynomial time. Based on the observation, we define

    where R(, ) is defined in (3). The weighting process is done across all edges. Hence its total complexity is O(KMN2), which is polynomial.




    n,n' k,r




    for each possible subcarrier pair (n, n). The original problem P1 is transformed into P2 without the loss of optimality,

    P2: max

    R(n,n') n,n'


    nN n'N




    n,n' k*,r*

    n N

    Figure 2. Bipartite Graphs (a) An Example of a matching (b) An Example of a perfect matching (c) The proposed Bipartite graph.


    n,n' k*,r*




    n' N

    According to our construction method of graph in above, the following equivalences were found:

    (i) a pair of matched vertices is just a subcarrier pair in the MAC and BC phases, (ii) a matching implies no violating the exclusive subcarrier assignment in each phase, and (iii) the weighting process done for each edge in is equivalent to finding the optimal user pair and relay for each possible subcarrier pair. Consequently, the joint optimization problem of subcarrier-pairing based subcarrier assignment and relay selection in multi- relay multi-pair relaying networks studied in [8] for the total throughput maximization is equivalent to finding a perfect matching in so that the sum weights of is maximum1 in [9].This is the so-called MWBM problem.

    The number of subcarriers is = 32. All sources have the same maximum power constraints, so do all relays and they satisfy =

    1 + 3dB = 2 + 3dB (per-subcarrier) for all

    and k.

    We consider the number of subcarrier pairing for both N=16 as well as N=32 with adaptive subcarrier pairing. The system throughput increased by consider the number of subcarrier pairing where N=16 with effect of number of relay nodes shown in Figure.3. The Performance comparison of the proposed algorithm and the benchmark is evaluated using the greedy algorithm and proves that complexity of the proposed system




    , (6)

    is higher than the benchmark. This shows the total

    throughput increase when there are K=5 user pairs

    F* (n,n')F *

    this is NP-complete and equivalent to P2.

    The key of the proposed algorithm is the mapping from the original problem P1 to the simplified problem P2 and then to the MWBM problem P3, without loss of optimality. Once the mapping is done, the classic Hungarian algorithm can be adopted to solve P3 optimally with the computational complexity O(N3).By combining the aforementioned complexity of the weighting process, the total complexity of our proposed algorithm is O(KMN2 + N3), which is polynomial in time.

    and M=4 relays in the network. And also this shows the throughput performance versus the number of relays. Through this simulated results, the total throughput when there are K = 5 user pairs and M = 4 relays in the network and also the performance of throughput versus the number of relays when K = 5 and 1 = 10 dB was analyzed.

    Effect of number of relays




    sumrate (bits/s/Hz)

    sumrate (bits/s/Hz)




  5. Simulation Output

    In this work a two-dimensional plane of node locations is considered, where the source nodes and relay nodes are randomly but uniformly distributed





    N = 32,Adaptive subcarrier pairing N = 32,fixed subcarrier pairing

    N = 16,Adaptive subcarrier pairing

    0 5 10 15 20 25

    number of relays

    in the corresponding square regions. The path loss model was adopted in [8], where the path loss exponent is set to 4 and the standard deviation of log-normal shadowing is set to 5.8 dB. The small- scale fading is modelled by multi-path Rayleigh fading process, where the power delay profile is exponentially decaying with maximum delay spread of 5 and maximum Doppler spread of 5 Hz. A total of 2000 independent channel realizations were generated, each associated with a different node loctions.

    1Note that the MWBM must be perfect matching.

    Figure 3. Effects of number of relays, where N=16,

    K = 5 and 1 = 10 dB

    Figure 4. illustrates the total throughput when there are K= 5 user pairs and M = 4 relays in the network. The proposed optimal channel and relay assignment with adaptive subcarrier pairing achieves 8 10% improvement in total throughput over the scheme with fixed subcarrier pairing is observed in [9]. In this work with adaptive subcarrier pairing the system total throughput increased by ~10 to 13% at start point and ~20 to 22 % at the end point as the number of relay get increased.

    comparision with fixed subcarrier pairing and adaptive subcarrier pairing


    adaptive subcarrier pairing fixed subcarrier pairing


    sumrate (bits/s/Hz)

    sumrate (bits/s/Hz)







    -5 0 5 10 15

    source power per sub carrier,dB

    Areas Commun., vol. 25, no. 2, pp. 328339, Feb.


    1. D. West, Introduction to Graph Theory. Prentice Hall, 2001.

    2. V. Erceg, L. Greenstein, S. Tjandra, S. Parkoff,

      1. Gupta, B. Kulic, A. Julius, and R. Jastrzab, An empirically based path loss model for wireless channels in suburban environments, IEEE J. Sel. Areas Commun., vol. 17, no. 7, pp. 12051211, July 1999.

    3. Yuan Liu and Meixia Tao, Senior Member, IEEE, optimal channel and relay assignment in ofdm- based multi-relay multi-pair two-way communication networks, vol. 60, no. 2, February 2012.

    Figure 4. Performance comparison of the proposed subcarrier pairing and the fixed subcarrier pairing

  6. Conclusion

    In relay-based networks the joint optimization of subcarrier-pairing, subcarrier assignment and the relay selection for multi-pair multi-relay in a two- way communication has been studied and considered as a combinatorial optimization problem. Then the network total throughput versus transmit power per node by transforming it into a maximum weighted bipartite matching (MWBM) problem. To resolve the problem a graph based approach is proposed optimally in polynomial time.

  1. G. Li and H. Liu, Resource allocation for OFDMA relay networks with fairness constraints, IEEE J. Sel. Areas Commun., vol. 24, no. 11, pp.20612069, Nov. 2006.

  2. W. Dang, M. Tao, H. Mu, and J. Huang, Subcarrier-pair based resource allocation for cooperative multi-relay OFDM systems, IEEE Trans. Wireless Commun., vol. 9, no. 5, pp. 16401649, May 2010.

  3. I. Hammerstrom and A. Wittneben, Power allocation schemes for amplify-and-forward MIMO-OFDM relay links, IEEE Trans. Wireless Commun., vol. 6, no. 8, pp. 27982802, Aug. 2007.

  4. Y. Li, W. Wang, J. Kong, and M. Peng, Subcarrier pairing for amplify-and-forward and decode-and-forward OFDM relay links, IEEE Commun. Lett., vol. 13, no. 1, pp. 209211, Apr. 2009.

  5. X. J. Zhang and Y. Gong, Adaptive power allocation in two-way amplify-and-forward relay networks, in Proc. 2009 IEEE ICC.

  6. T. C.-Y. Ng and W. Yu, Joint optimization of relay strategies and resource allocations in cooperative cellular networks, IEEE J. Sel.

Leave a Reply