OFDM-Based Multi-Relay Multi-Pair Two-Way Communication Networks with Optimal Channel and Relay Assignment

OFDM-Based Multi-Relay Multi-Pair Two-Way Communication Networks with Optimal Channel and Relay Assignment

Madhava Rao Alla1 Dr. B. Ananda Krishna2

1Student, M. Tech-DECS, Dept. of ECE, Gudlavalleru Engineering College, AP, India.

2Professor, Dept. of ECE, Gudlavalleru Engineering College, AP, India.

Abstract- To fully exploit the potential of OFDM-based relay networks, it is crucial to design efficient resource allocation schemes, including determining which relay node to cooperative with, which set of subcarriers to operate on, and with how much power to transmit the signals. Resource allocation has extensive attention recently in a variety of OFDM-based relay networks like node cooperation, operation of sub-carriers, power to transmit the signal. Efficient utilization of radio resources in wireless networks is crucial and has been investigated extensively. This paper considers a wireless relay network where multiple user pairs conduct bidirectional communications via multiple relays based on orthogonal frequency-division multiplexing (OFDM) transmission. The joint optimization of channel and relay assignment, including subcarrier pairing, subcarrier allocation as well as relay selection, for total throughput maximization is formulated as a combinatorial optimization problem. Using a graph theoretical approach, the problem is solved optimally in polynomial time by transforming it into a maximum weighted bipartite matching (MWBM). Simulation studies are carried out to evaluate the network total throughput versus transmit power per node and the number of relay nodes.

Keywords: Two-way relaying, Orthogonal Frequency Division Multiplexing (OFDM), subcarrier pairing, graph theory, Maximum Weighted Bipartite Matching (MWBM).

1. INTRODUCTION

   In cooperative relaying multiple frequency channels, the relay can exploit the additional frequency dimension to process incoming signals adaptively based on the diversity in channel strength. For example, subcarrier pairing, which devises a matching of incoming and outgoing subcarriers in OFDM relaying, was first proposed independently in [1] and [2] for single-user relaying. Furthermore, in a multiuser communication environment, both incoming and outgoing channels at the relay are shared among all the users. Since the channel condition can vary drastically for different users, judicious channel-user assignment, which allocates channels to users, can potentially lead to significant improvement in spectral efficiency.

   There is strong correlation between channel pairing, channel-user assignment, and power allocation.

   Therefore, optimal system performance requires joint consideration of these three problems. However, the combinatorial nature of channel pairing and assignment entails a mixed integer programming problem, whose

   solution often bears prohibitive computational complexity. Previous attempts to optimize the performance of dual-hop multi-channel multi-user relaying often either consider only a subset of the three problems or adopt a suboptimal approach [4].

   For a single-user amplify-and-forward (AF) OFDM relaying system, [3] showed that the sorted subcarrier pairing scheme, which matches the incoming and outgoing subcarriers according to the sorted order of their SNRs for given power allocation, is sum-rate optimal when the direct source destination link is unavailable. The authors of [4] and [5], for AF and decode-and-forward (DF) respectively, showed that joint power allocation and subcarrier pairing are separable for sum-rate optimization in single-user OFDM relaying, without the direct source-destination link. This separation was also found for the multi-hop case. The authors of [6] and [7], for AF and DF respectively, considered joint power allocation and subcarrier pairing in a single-user OFDM system with the direct source-destination link available. The joint optimization problems were formulated as mixed integer programs and solved in the Lagrangian dual domain. Although strict optimality was not established, the proposed solutions are optimal in the limiting case as the number of subcarriers approaches infinity based on the time-sharing argument. For given power allocation, [8] and [9] sought an optimal subcarrier- user assignment to maximize the end-to-end rate. Using continuous relaxation and allowing partial subcarrier assignment, provided an asymptotically optimal solution to the problem of joint power and subcarrier-user assignment for DF relaying. The authors of [10] considered all three problems in DF relaying with a total power constraint and without the direct source-destination link. They showed that it is optimal to separately apply subcarrier-user assignment by channel gain, sorted subcarrier pairing, and water-filling power allocation.

   Problem Statement:

   This work considers an OFDM-based network where multiple relays help multiple pairs of source nodes to conduct Bidirectional communications. The aim of the project lies in maximizing the system total 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 two-way users is considered as a combinatorial optimization problem. Hence graph based approach is implemented to establish the equivalence between the proposed method and a Maximum Weighted Bipartite Matching (MWBM) problem. Then the problem is solved by the corresponding graph based algorithm optimally in polynomial time.

2. SYSTEM MODELING

   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.

   The subcarriers are n and 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,

   An OFDM-based wireless network with pairs of users and

   relays is shown in Fig.1. Here each user pair exchanges

   ,

   ,

   1

   = 1, 2

   2 1 + + +

   information via the relays. Each node operates in a half- duplex mode. For simplicity, the amplify and- forward (AF)

   2

   +

   1

   1

   2

   two-way relay strategy is adopted. The wireless fading environment by large-scale path loss and shadowing, along with small-scale frequency-selective fading is considered.

   Figure 1 OFDM-BASED Wireless Network with K Pairs of Users and M Relays

   The following assumptions are considered for the proposed wireless network:

   The channels between different links experience independent fading and the network operates in slow fading environment, so that channel estimation is perfect.

   A central controller is available in the network so that the centralized processing is possible.

   The additive white noise at all nodes is 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.

   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-overlappng subcarriers. The intra-pair interference will be treated as back-propagated self interference and canceled perfectly after two-way relaying. In the second phase, known as BroadCast (BC) phase, the

   2 2

   2 1 + + +

   1 1 2

   Where (x)=log (1+x) and _ij^n denotes the instantaneous signal-noise ratio (SNR) from node i to node j over subcarrier n, assuming that all the nodes have the unit noise variance.

   Let us consider the set of binary variables _(k,r)^(n,n')={0,1} for all k, r, n, n Where _(k,r)^(n,n')=1 means that subcarrier n in the first phase is paired with subcarrier n in the second phase assisted by relay r for user pair k, else _(k,r)^(n,n')=0 otherwise. As assumed above, each subcarrier can be assigned to one user pair and one relay, in the first and second phases, respectively to avoid interference. Therefore, _(k,r)^(n,n') must satisfy the following constraints:

   The main objective is to maximize the system total throughput by optimally pairing subcarriers in the two phases and selecting the best relays and the best paired subcarriers for each user pair. Mathematically, this can be formulated as P1:

   Note that it can be easily modify the objective function in P1 to weighted sum of all user rates without affecting the algorithm design if fairness is considered.

   Problem P1 is a combinatorial optimization problem and the optimal solution can be obtained by exhaustive search. The complexity is exponential and thus prohibitive when , , and are large. In this section, a graph based approach was proposed to solve the problem optimally in polynomial time.

   By observing the summation in the objective function of P1, it is easy to find that there is at most one non-zero element for a given subcarrier pair (, ) due

   to the constraints. Based on the observation, it is defined as,

   n,n'

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

   where (, ) is defined in a previous equation. The

   R(n,n')

   max

   kK,rM

   Rk,r

   weighting process is done across all the edges. Hence its total complexity is (2), which is polynomial.

   for each possible subcarrier pair (, ).

   The associated user pair and relay node that take the maximum for each subcarrier pair (, ) are denoted as

   * and *, respectively. Consequently, we can transform the original problem P1 to the following simplified problem (P2) without loss of optimality.

   P2: max R(n,n') n,n'

   According to the construction method of graph in above, the following equivalences are to be consider: (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 defined in (2) and (3), and (iii) the weighting process done for each edge in is equivalent to finding the optimal user pair and relay

   nN n'N

   k*,r*

   for each possible subcarrier pair. Consequently, the joint

   optimization problem of subcarrier-pairing based subcarrier assignment and relay selection in multi-relay multi-pair

   n'N

   n,n'

   k*,r*

   1,

   n N

   two-way relaying networks for the total throughput maximization is equivalent to finding a perfect matching

   in so that the sum weights of is maximum. This is

   nN

   n,n' k*,r*

   1,

   n' N

   the so-called MWBM problem (P3):

   P3:

   max

   W(n,n') ,

   It is shown that the simplified P2 is equivalent to a maximum weighted bipartite matching (MWBM) problem.

   F *

   (n,n')F *

3. BIPARTITE GRAPH

   A bipartite graph is a graph whose vertices are divided 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 the bipartite graph is balanced bipartite graph. A matching is a set of mutually disjoint edges, i.e., any two edges do not share a common vertex, is shown in Fig. 2(a). A perfect matching is a matching that every vertex in the graph is matched, shown in Fig. 2(b). Note that perfect matching is the special case of matching.

   Figure 2: Bipartite graphs (a) An example of a matching. (b) An example of a perfect matching. (c) The proposed bipartite graph.

   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, respectively, is constructed as shown in Fig. 2(c). is the set of edges that connect all possible pairs of vertices in the two set of vertices. Note that is shared in each phase, thus

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

   : +. More specifically, each edge is assigned a weight, representing the maximum achievable rate over the matched two vertices.

   which 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, both without loss of optimality. Once the mapping is done, the classic Hungarian algorithm can be adopted to solve P3 optimally with the computational complexity (3). By combining the aforementioned complexity of the weighting process, the total complexity of our proposed algorithm is (2+3), which is polynomial.

4. SIMULATION RESULTS

   The Proposed method is simulated using Matlab. A two- dimensional plane of node locations shown in Fig. 3, where the source nodes and relay nodes are randomly but uniformly distributed in the corresponding square regions. The path loss model, where the path loss exponent is set to 4 and the standard deviation of Log-normal shadowing is set to 5.8 dB is adopted. The small-scale fading is modeled 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 locations.

   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.

   Two dimensional plane of nodes location

   3

   sources

   boundary

   2.5 relays

   2

   1.5

   1

   0.5

   0

   Effect of number of relays

   proposed

   fixed subcarrier pairing

   2.2

   3

   2.5

   2

   1 1.5

   kms

   0.5

   0

   kms

   sumrate (bits/s/Hz)

   Figure 3: Two-dimensional plane of nodes location

   N = 32,proposed

   N = 32,fixed subcarrier pairing N = 16,proposed

   N = 16,fixed subcarrier pairing

   As a performance benchmark, the fixed subcarrier pairing scheme is considered. Let signals transmitted by the user pair on one subcarrier in the MAC phase is forwarded on the same subcarrier by a relay in the BC phase, i.e., () = , rather than seeking the optimal subcarrier pairing. Then the problem reduces to selecting the optimal user pair and relay for each subcarrier for throughput maximization, which can be optimally solved by the greedy algorithm. Namely, each subcarrier shall be assigned to the user pair and the relay that satisfy .

   0

   5

   10

   number of relays

   15

   20

   2.1

   2

   1.9

   1.8

   1.7

   1.6

   Figure 5: Effects of the number of relays, where = 32, = 5, and 1 = 10 dB.

   Effect of number of relays

   0

   k*,r* arg max k ,rM

   Rn,n' k,r

   2.5

   2.4

   2.3

   2.2

   2.1

   2

   1.9

   1.8

   1.7

   sumrate (bits/s/Hz)

   The overall complexity of the fixed subcarrier paring scheme is (). Recall thatthe complexity of the proposed graph-based scheme is (2 + 3), which is higher than the benchmark scheme.

   Fig. 5 illustrates the total throughput when there are = 5 user pairs and = 4 relays in the network. It is observed that 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.

   sumrate (bits/s/Hz)

   With the change in number of subcarriers, we get the relation between the number of relays used to that of throughput.

   comparision with proposed and benchmark

   3.5

   3

   2.5

   2

   1.5

   1

   0.5

   0

   -5

   proposed

   fixed subcarrier pairing

   15

   10

   5

   source power per sub carrier

   0

   Figure 4: Performance comparison of the proposed algorithm vs the benchmark

   1.6

   5 10

   15

   20

   25

   number of relays

   Figure 6 : Performance Comparison of proposed system and the benchmark

5. CONCLUSION

This work proves our investigations on the joint optimization of subcarrier-pairing based subcarrier assignment and relay selection for multi-relay multi-pair two-way relay OFDM networks. The problem was formulated as a combinatorial optimization problem. The proposed bipartite matching approach solves the problem optimally in polynomial time. The work assumed the amplify-and-forward based non regenerative relay strategy. The similar problem based on more advanced regenerative two-way relay strategies can be considered in the future work. The results are shown for the use of different number of subcarriers. The difference between proposed and fixed scheme are shown using graphs.

The advantages of the proposed system are listed below:

• The channel estimation is perfect as the channel between different links experience independent fading.

• OFDM is very easy and efficient in dealing with multi-path and Robust again narrow-band interference.

• As OFDM-based network supports multi relay- multi pairs of source node to conduct bidirectional communications, it maximizes the throughput optimally.

REFERENCES:

1. A. Hottinen and T. Heikkinen, Subchannel assignment in OFDM relay nodes, in Proc. of Annual Conf. on Information Sciences and Systems, Princeton, NJ, Mar. 2006.

2. M. Herdin, A chunk based OFDM amplify-and-forward relaying scheme for 4G mobile radio systems, in Proc. IEEE Int. Conf. Communications (ICC), Jun. 2006.

3. A. Hottinen and T. Heikkinen, Optimal subchannel assignment in a two-hop OFDM relay, in Proc. IEEE Workshop on Signal Processing advances in Wireless Commun (SPAWC), Jun. 2007.

4. W. Wang, S. Yan, and S. Yang, Optimally joint subcarrier matching and power allocation in OFDM multihop system, EURASIP J. Appl. Signal Process. (USA), Mar. 2008.

5. W. Wang and R. Wu, Capacity maximization for OFDM two-hop relay system with separate power constraints, IEEE Trans. Veh. Technol., vol. 58, no. 9, pp. 49434954, Nov. 2009.

6. 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.

7. T. C.-Y. Ng and W. Yu, Joint optimization of relay strategies and resource allocations in cooperative cellular networks, IEEE J. Sel. Areas Commun., vol. 25, no. 2, pp. 328339, Feb. 2007.

8. 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.

9. 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. 209 211, Apr. 2009.

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