In this paper, we consider a network-coded cooperative wireless network, where users mutually pair among themselves to realize network coding. We assume a multi-user environment, where users transmit to a common destination in the absence of dedicated relaying nodes. We address the important problem of the mutual pairing of users, which directly governs the overall network performance. An optimal user pairing algorithm is proposed and tailored to maximize the network capacity. Next, we develop heuristic user pairing schemes, which demonstrate near-optimal performance at significantly reduced computational complexity. In particular, we propose max-max pairing to maximize the network capacity and max-min pairing to minimize the outage probability. We then consider power minimization for energy-constrained networks. A joint optimization problem is formulated and solved to find the pairing which maximizes the network capacity and minimizes the transmission power, while meeting certain network performance constraint, such as in terms of the minimum average capacity per user or maximum average outage probability per user.
The online version of this article (doi:10.1186/1687-1499-2013-173) contains supplementary material, which is available to authorized users.
Competing interests
The authors declare that they have no competing interests.
1 Introduction
In contemporary wireless networks, diversity represents an efficient and established means to combat multipath fading. Moreover, user cooperation has recently emerged as an elegant technique to achieve spatial diversity over wireless channels by exploiting the broadcast nature of the medium [1]. Cooperative diversity retains many benefits innate to multiple-input multiple-output systems, without incurring the additional hardware costs, and has been widely shown to achieve remarkable performance gains for wireless networks [2‐4].
Moreover, in recent years, the application of network coding [5] in cooperative wireless networks has gained increasing interest with its potential to further boost the network performance, e.g., in terms of the achievable throughput. With network coding, the intermediate nodes are allowed to linearly combine packets from multiple sources and then forward the linearly combined packets for better throughput and resource utilization. The application of network coding in wireless networks has been studied in a variety of settings, including the cases of two sources transmitting to a common destination [6‐13], multi-cast networks [14, 15], ad-hoc networks [16], and two-way relay channels [17‐20].
Anzeige
The performance of network-coded cooperative networks is heavily determined by the relay selection scheme. Owing to its importance, this problem has received significant interest from the wireless communication research community [21]. The problem of relay selection for transmission to a common destination, such as a base station (BS) in a cellular environment, is considered for instance in [6, 7]. However, the relays are assumed to be dedicated; the relaying nodes participate in cooperation but transmit nothing for themselves when relaying. Moreover, multi-user environments are not considered. Relay selection schemes with network coding over two-way relay channels have been considered for instance in [17‐20]. Various optimal and heuristic selection methods have been proposed for choosing the relay (or set of relays) which forwards the network-coded packet. However, the relaying nodes are assumed to be dedicated.
In [12, 13], user pairing has been considered for network-coded cooperative wireless networks; however, the optimality of the proposed user pairing algorithms has not been proven. Furthermore, in [22] the authors consider the problem of optimal user selection for cooperative wireless networks, which do not feature network coding, with the objective of energy minimization.
This motivates us to address the problem of optimal mutual user pairing (i.e., partner selection) in a multi-user environment, where users employ network coding to transmit to a common destination (e.g., a BS in a cellular environment). In the absence of dedicated relay nodes, as shown in Figure 1, users mutually pair among themselves to realize network coding. This is an important communication scenario, and to the best of our knowledge, the problem of optimal mutual user pairing in such multi-user environments has not been addressed previously.
Figure 1
The system model. Dotted and solid lines represent source- and network-coded-packet transmissions, respectively.
×
The user pairing can be performed to optimize certain system performance metrics, such as network capacity, outage probability, power consumption, and/or user fairness. Two nodes constituting a pair periodically swap the roles of source and relay for the mutual benefit of achieving diversity gain. In this paper, we first formulate and solve an optimization problem to determine the user pairing which maximizes the total network capacity. We then propose implementation-oriented heuristic pairing algorithms which demonstrate near-optimal performance at significantly alleviated computational complexity. We subsequently consider power minimization for energy-constrained wireless networks, such as sensor and cellular networks, where the design of energy-efficient protocols is imperative. The performance gains from network coding in terms of better throughput or outage performance can be traded off for improved energy efficiency. In particular, we solve a joint constrained optimization problem to find the user pairing which maximizes the network capacity and minimizes the transmission power, such that certain network performance constraints in terms of the average capacity per user or the average outage probability per user are satisfied.
Anzeige
The rest of the paper is organized as follows. In Section 2, the system model of the multi-user cell-based network-coded cooperation is established. The capacity and outage analysis of this cooperation scenario is presented in Section 3. User pairing algorithms (including the optimal and heuristic ones) are proposed in Section 4. The joint constrained optimization problem for power minimization and capacity maximization is formulated and solved in Section 5. Simulation results are presented in Section 6. In Section 7, we draw conclusions and present directions for future work.
2 System model
The system model is shown in Figure 1. We consider a circular cell, where the nodes are uniformly and randomly distributed. Users strategically pair and take turns to relay the network-coded packets for their partners. We consider full buffer traffic and assume the inter-source channels to be non-ideal (noisy with Rayleigh fading). Thus, nodes may not always detect the packets of their partner and therefore do not always forward the network-coded packets to help their partner.
The communication with the common destination (BS) is performed over two phases, and each phase consists of two time slots. This is depicted in Figure 2, where it is assumed that nodes i and j constitute a pair, where i, j ∈ {1,…, N}, and i ≠ j. Node i transmits its packet to the destination in the first time slot during the first (direct transmission) phase, while node j listens. Subsequently, j transmits its packet in the second time slot while i listens. This is followed by the second (network coding) phase of transmission. Now, if i decoded the packet of j in the previous phase, it combines this packet with its own packet and sends the network-coded packet to the destination in the first time slot. Otherwise, it sends an additional packet for itself. Meanwhile, j does the same in the second time slot of the second phase. This two-source packet transmission model is inspired by the incremental network coding scheme proposed in [9]. Both nodes employ channel coding for error detection and correction, as practiced in modern wireless communication networks.
Figure 2
Packets transmitted by the paired nodesiandjin the two phases. In case of inter-user transmission failure, an individual packet is transmitted by the relaying node in the network coding phase.
×
At the destination, the two independently faded network-coded packets are combined using maximum ratio combining (MRC) to form a single packet, which provides diversity. This packet is subsequently jointly decoded with the packets received in the first phase to recover the information bits. In case of successful inter-source transmissions, each user achieves a diversity order of 2. This concludes the two phases of transmission to the destination.
Time and energy resources are split equally between the two phases and also within the two time slots constituting each phase. Moreover, the success of decoding at the partner nodes is assumed to be determined by cyclic redundancy checks, whereas incorporating an additional flag bit in the packets transmitted in the second phase helps the BS determine the success of inter-source transmissions and, hence, the nature of the packets received in the second phase. All users have data to send and transmit over orthogonal channels; hence, there is no same-cell interference. All channels, i.e., inter-source and source-destination, are assumed to be spatially independent, frequency-flat Rayleigh fading, with additive white Gaussian noise (AWGN). We assume block fading such that all channels remain constant during the two phases and change independently afterwards; this accommodates for relatively low-medium mobility. In addition, the inter-source channels are assumed to be symmetric but non-reciprocal, i.e., having equal average signal-to-noise ratio (SNR) in both directions, but not necessarily the same instantaneous SNR.
During the first (direct transmission) phase, node i (assuming the role of source) transmits L/2 symbols in the first time slot, and therefore the time index m = 1,…, L/2. For the direct source-to-destination transmission, the received symbol at time index m is given by
(1)
where si[m] is the transmitted source information symbol, nD[m] is the AWGN noise at the destination, and the channel coefficient hi,D[m] captures the effect of pathloss and Rayleigh fading. We assume perfect channel state information (CSI) at all receivers. The channel coefficient is assumed to be fixed over the two phases (i.e., for 2L symbols), and the time index of h is henceforth dropped. Meanwhile, the received symbol at node j is
(2)
where nj[m] is the AWGN noise at node j, and hi,j is the coefficient of the channel from node i to j. Similarly, during the second time slot, i.e., for m = L/2 + 1,…, L, node j (now assuming the role of source) sends its packet to the BS, which is received by i. The received symbols at destination D and node i are given respectively as
(3)
(4)
where sj[m − L/2] is the symbol transmitted by node j, ni[m] is the AWGN noise at node i, and hj,D and hj,i are the coefficients of the channels between j and D, and j and i, respectively. In the second (network coding) phase of transmission, nodes i and j transmit with time indices m = L + 1,…, 3L/2 and m = 3L/2 + 1,…, 2L, respectively. The symbols received at the destination D from nodes i and j are given respectively as
(5)
(6)
where ⊕ denotes the bit-wise XOR operator. In case either node i or node j fails to decode the packet of their partner, an additional individual packet is sent by that node in the network coding phase.
3 Capacity and outage performance analysis
The inter-source and source-destination channel capacities for nodes i and j are functions of the corresponding channel coefficients, and therefore, they are random variables [2]. Moreover, an outage over a link is defined as the event of the throughput falling below a target information rate. We use the outage probability at a certain rate as a metric of the packet error rate for the block-based transmissions under consideration [23]. The inter-source channels are modeled as non-ideal (due to noise and fading), and successful decoding at the (acting) relay is not guaranteed. This translates to the fact that the relay helps its partner by forwarding a network-coded packet in the second phase only if it decodes correctly the packet of its partner in the first phase. Otherwise, it transmits its own packet only. Thus, the average throughput for the pair depends on the success of the inter-source transmissions, which must first be determined. The nodes use channel coding for error control.
3.1 Direct transmission phase
In the direct transmission phase, nodes i and j sequentially broadcast their respective packets to the destination and also listen to each other's transmissions. The inter-source information theoretic channel capacity for node i is Ci,j = log2(1 + γi,j), where γi,j = |hi,j|2P/N0 is the instantaneous SNR of the inter-source link, with P as the transmit power and N0 as the noise power spectral density. An outage occurs when Ci,j < 2R[9], where R is the packet information rate in the case of point-to-point transmission. For Rayleigh fading, the inter-source link outage probability for i is given as [8]
(7)
where Γi,j is the average SNR of the inter-source link. The inter-source outage probability for node j can be calculated by replacing Γi,j with Γj,i in (7). In case of symmetric inter-source channels, the inter-source link outage probability for both nodes is equal.
3.2 Network coding phase
Depending on the success of inter-source packet transmissions, there can be four different cases: (a) when both nodes i and j in the pair decode each other's packets, (b) when none of them decodes the partner's packet, (c) when only node j decodes node i's packet, and (d) when only node i decodes node j's packet [9]. In this subsection, we present the capacity and outage analysis for node i; the same approach holds for node j.
For node i, the source-destination channel capacities Ci,D, as well as the corresponding outage events for the four possible cases (a) to (d) are provided in (8) [9]. For the channel capacity, the first and the second terms on the right-hand side of (8), cases (a) to (d), represent contributions from the direct transmission and the network coding phases, respectively. The threshold for outage is the code rate of the packet formed at the destination in each case for decoding the information symbols of node i. Moreover, the effect of the MRC on capacity is reflected by the addition of the SNRs (e.g., the second term in (8), case (a), where the same network-coded packet si ⊕ sj is received twice over uncorrelated channels).
(8)
4 User pairing and capacity maximization
In this section, we address the problem of user pairing, which directly governs the overall network performance. The pairing decisions are made at the BS, which is assumed to have complete knowledge of the inter-source and source-destination CSI. We first solve the problem of determining the optimal user pairing P* and tailor it to maximize the total network capacity. To facilitate user pairing, we then develop computationally simpler heuristic algorithms which are designed to address the throughput and outage performance.
4.1 Optimal user pairing P*
Let Π be the set of all possible pairing sets such that every set P ∈ Π is the pairing containing ⌊N/2⌋ disjoint user pairs, where ⌊ ⌋ is the floor functiona. Each pairing P is a symmetric mapping of elements from the set to the set , with the restriction that an element from cannot be mapped to the same element in . The goal is to find the optimal pairing P* that maximizes the total network capacity C = ∑ iCi. Therefore,
(9)
At first glance, this can be formulated as the problem of maximum weighted matching (i.e., pairing) in bipartite graphs, and any of the assignment algorithms, such as the well-known Hungarian algorithm [24], seem to be a candidate solution. However, as it was observed, a weight matrix W with zeros on the main diagonal and symmetric entries, [W]i,j = [W]j,i = Ci,D + Cj,D (depending on the applicable case, from (8)), describing the weight of the assignment of node i to j, and node j to i (where i and j constitute a potential pair), did not always lead to a symmetric assignment. To find the optimal solution, we therefore model this problem as maximum weighted matching in general graphs.
We construct a weighted undirected graph G = (V, E),, where the vertices V are the users to be paired, connected by the set of edges E. Furthermore, |V| = N and |E| = N(N − 1)/2for the fully connected graph, where |.| denotes the cardinality of a set. Each edge (i, j) has an associated weight [W]i,j = Ci,D + Cj,D. The goal is to find the matching (i.e., pairing) with the maximum total weight. This maximum weighted matching covers all the vertices in the graph, and each vertex is connected only to a single edge. Moreover, each edge in the matching connects two distinct vertices. One such potential matching for a weighted graph with four nodes is shown in Figure 3. It is noteworthy that the edge with the maximum weight may not be a part of the maximum weighted matching. When the number of users to be paired is large, the problem of finding the optimal pairing (i.e., the matching with the maximum total weight) is clearly far from trivial, whereas an exhaustive search is prohibitively expensive. To solve this pairing problem, we utilize Jack Edmond's maximum weighted matching algorithm for general graphs [25].
Figure 3
A potential matching in the weighted, undirected graph. The edges drawn with thick lines are part of the matching.
×
The notion is to start with an empty pairing and then, during each stage, to find an augmenting path in the graph which yields the maximum increase in weight. The blossom method is used for finding the augmenting paths, and the primal-dual method is employed for finding the pairing with maximum weight. The problem is defined as a linear program. Considering the dual problem, we use complementary slackness to convert the optimization problem to that of solving a set of inequalities or constraints. A pair of feasible solutions for the primal and dual problems is optimal if, for every positive variable in one of these problems, the corresponding inequality in the other one is satisfied as an equality.
Defining this matching problem as a linear program is immediate. We then describe it as an integer program and replace the integrality constraints xi,j ∈ {0, 1} (which indicate that the edge (i, j) may not or may belong to the final pairing, respectively) by xi,j ≥ 0. Moreover, additional constraints, i.e., , are added for all odd subsets of vertices Vo. We have a primal solution, a pairing P, and a dual solution which is the assignment of the dual variables which are denoted by ui (for all vertices) and zk for all odd subset of vertices, . The slack variables are defined as . Moreover πi,j ≥ 0 are the constraints of the dual problem. By duality, we find the optimal pairing P* when all of the following conditions hold true (for the complete proof the optimality of this algorithm, the reader is referred to [25]) the following:
(a). For all i, j, and k, ui, πi,j, zk ≥ 0.
(b). The edge (i, j) is matched ⇒ πi,j = 0.
(c). zk > 0 ⇒ subset of vertices ,
is full.
The algorithm solves the pairing problem in O(N3) time, whereas an exhaustive search would require (N − 1) ! ! calculations, where !! denotes double factorial.
4.2 Heuristic pairing algorithms
The following are the heuristic pairing algorithms:
1
Max-max pairing. This algorithm pairs users with the objective of approaching the optimal capacity at a significantly reduced computational complexity. A weight matrix W with zeros on main diagonal and symmetric entries [W]i,j = [W]j,i = Ci,D + Cj,D is established, where i and j are potential pairs. The algorithm is formally presented as follows:
1.a Initialize an empty pairing P.
1.a Select the largest element from W, for instance [W]i,j, and form the pair by augmenting P with i and j.
1.a Update W by removing the rows and columns corresponding to the pair formed in 1.b.
1.a Continue from 1.b until P is complete and all nodes have been paired.
This algorithm has O(N3) time complexity and therefore responds similarly to the change in the number of inputs (i.e., users to be paired) as the optimal algorithm. However, max-max pairing is significantly computationally less expensive than optimal pairing as it is uses simpler comparison operations to search for the maximum weight in a single iteration. This is also reflected by the simulation times which are referred to in Section 6.1.
2
Max-min pairing. This heuristic algorithm is designed to address the system outage probability. We start with the weakest user (in terms of the SNR to the destination) in the cell and pair it with the user having the strongest of the weaker of the source-relay and relay-destination links, since the outage performance is always determined by the weaker of the two links [24], and continue so on for other users. The algorithm has a time complexity of O(N2) and is formally presented as follows:
2.a Initialize an empty pairing P.
2.a Select a node i with the lowest γi,D and pair it with node j with max[min(γi,j, γj,D)].
2.a Augment the pairing P with the pair formed in 2.b and update the set of eligible nodes.
2.a Continue from 2.b until P is complete and all nodes have been paired.
Max-min pairing is computationally efficient as it is based on simple comparison operations; this is also reflected in the average simulation times, as stated in Section 6.1.
3
Random user pairing. Pairing users randomly is the most straightforward strategy and is the simplest to implement in practice. From the set of eligible users, two randomly chosen nodes are paired. P is augmented, the set of eligible users is updated, and the algorithm repeats until all users have been paired. Although random selection is not an effective way of pairing, we include it here for comparison purposes.
5 Power minimization: joint constrained optimization of power and capacity
Power minimization is considered for energy-constrained wireless networks. Besides improving battery lives for energy-constrained devices and being more environment-friendly, the optimization (i.e., minimization) of transmission power while meeting certain network performance constraints also improves inter- and intra-cell interferences. Relaxing the assumption of fixed power allocation to users, we address power minimization with equal power allocationb. In particular, we consider joint optimization of power and capacity; the user pairing is performed to maximize the total network capacity and minimize the transmission power per user, such that a certain network performance constraint in terms of the average outage probability per user or the average capacity per user is satisfied. We use the optimal pairing algorithm as described in Section 4 to find Pc*. Subsequently, we use the bisection optimization [26] to solve for the minimum transmission power, such that the given constraint on the average capacity per user or on the average outage probability per user is satisfied.
5.1 Power minimization and capacity maximization with constraint on average outage probability per user
The performance constraint is in terms of the average outage probability per user, i.e.,
(10)
where Φo(P) is the average outage probability per user, which is a monotonically decreasing function of the transmission power per user, P, and Φo,th is the maximum acceptable average outage probability per user. This is important for communication networks where the reliability of the communication link and hence the outage probability is of greater concern. The optimal transmission power per user, Pmin*, i.e., the minimum power which meets this constraint on outage probability, satisfies the equation
(11)
We use the bisection method to solve this constrained optimization problem. To find Pm*, we locate the root of the function
(12)
An upper and lower bound on the transmission power defines the initial search interval [Pl, Pu], such that it contains the root of F(P), i.e., Pm*. The bisection method converges to the actual root with a predefined tolerance, ϵ. The algorithm for outage probability-constrained power minimization is formally expressed as follows:
A.a) Choose the initial values for Pl and Pu.
A.b) Set the transmission power, P = Pl + (Pu − Pl)/2.
A.c) Obtain the new Pcap* for transmission power P.
A.d) If F(P) = 0, exit
Else if (Pu − Pl) < ϵ, and F(P) > 0, exit
Else if F(Pl) ⋅ F(P) > 0, then Pl = P
Else Pu = P
go to step A.b).
5.2 Power minimization and capacity maximization with constraint on average capacity per user
The performance constraint is in terms of the average capacity per user, i.e.,
(13)
where Φc(P) is the average capacity per user, which is a monotonically increasing function of P, and Φc,th is the minimum acceptable average capacity per user. This scenario is important for communication networks where the bandwidth is of greater concern, such as for video transmission. The optimal transmission power, Pm*, i.e., the minimum power per user which meets this constraint on average capacity per user, satisfies the equation
(14)
Similar to the previous case, to find Pmin*, we locate the root of the function
(15)
The algorithm for capacity-constrained power minimization is formally expressed as follows:
B.a) Choose the initial values forPl and Pu.
B.b) Set the transmission power, P = Pl + (Pu − Pl)/2,
B.c) Obtain the new Pc* for transmission power P,
B.d) If F(P) = 0, exit
Else if (Pu − Pl) < ϵ, and F(P) > 0, exit
Else if F(Pl) ⋅ F(P) > 0, then Pl = P
Else Pu = P
go to step B.b).
6 Simulation results
We herein present the simulation results for the network-coded cooperation framework considered in this paper. We first present the results for the problem of user pairing to maximize the network capacity, given a fixed transmission power. The proposed algorithms are evaluated and compared in terms of the average capacity per user, average outage probability per user, and per-user throughput fairness. The performance achieved for the joint and constrained optimization of power and capacity is subsequently investigated in terms of the average transmission power per user with constraints on average outage probability, average capacity per user with constraints on target outage probability, and average transmission power per user with a constraint on average capacity. In all these results, we compare the performance of the network-coded framework with that of the traditional direct transmission.
For simulations, we use the exponential pathloss model with a break-point distance of 1 m, and a pathloss exponent of 3.5 [27]. The inter-source and uplink channel bandwidth is 10 MHz. The antennas at the nodes and the BS are modeled as having absolute gains of 6 and 20 dBi, respectively. The information rate R = 0.25 bps/Hz, and the users are uniformly and randomly distributed over a cell of radius 1 km. Equal power allocation is assumed for all users.
6.1 User pairing for capacity maximization: fixed power allocation
We herein present the simulation results ensembled in Matlab for the optimal and heuristic user pairing algorithms to maximize the network capacity. All users employ a fixed transmission power of 1 W, and the results are averaged over 103 location sets and 103 channel samples per location. This is the simplest scenario, which is used to analyze and gauge the performance of the optimal and heuristic algorithms, without additional network performance constraints.
In Figure 4, the average capacity per user is shown versus the number of users for the four pairing schemes, as well as for direct transmission. As expected, the optimal pairing yields the maximum throughput per user for all values of N and is therefore used as the benchmark for the heuristic schemes. The average capacity increases slightly with the increasing number of users as the pairing opportunities improve. We should note that the optimality of the algorithm was also verified through extensive comparisons with the exhaustive search pairing. From the proposed heuristic algorithms, max-max pairing achieves the closest capacity to the optimal pairing. For N = 30 and 40 for instance, max-max pairing is shy of the optimal pairing by 6.03% and 6.12%, respectively. This performance is achieved approximately four times faster when compared with the optimal pairing in terms of the average simulation times. Comparing the performance degradation against the relative complexities of the two algorithms, max-max pairing emerges as a very good choice for practical implementation. On the other hand, the max-min pairing algorithm, which is designed to minimize the outage probability, is significantly inferior to max-max pairing. This is anticipated, as the max-min algorithm pairs the weakest user in the cell (in terms of the source-destination SNR) with the strongest one, and the second weakest with the second strongest one, etc., which leads to a lower value of average capacity per user. For max-min and random pairing, the effect of improving pairing opportunities is countered by a decreasing average source-destination SNR as the number of users increases (and the average source-destination distance increases), which results in a relatively steady average capacity per user. Direct transmission has a considerable lower capacity per user (less than 50% of the capacity of the network coding with optimal pairing for all N). This is expected since direct transmission does not take advantage of relaying and signal combining.
Figure 4
Average capacity per user versus number of paired users in cell for proposed pairing algorithms.
×
Although the optimal pairing scheme is designed to maximize the network throughput, it also achieves the best outage performance. Moreover, the outage performance-oriented max-min algorithm matches the optimal algorithm in terms of the average outage probability per user, as they both demonstrate zero outage for all values of N. When compared with the optimal pairing, the max-min pairing achieves this performance approximately 40 times faster, as reflected by the average simulation times. Results for the average outage probability per user for the max-max pairing, random pairing, and direct transmission are depicted in Figure 5. As expected, direct transmission has the highest outage probability (>0.032 for all N). Among the two network coding schemes, max-max pairing is observed to perform worse than random pairing for all N. This is owing to the aggressive nature of the max-max pairing, which leads to a greater variance and spread within pairs (in terms of throughput), and therefore results in a relatively high average outage probability per user, which is consistent as the number of pairing users increase.
Figure 5
Average outage probability per user versus number of paired users in cell for proposed pairing algorithms.
×
Furthermore, the long-term fairness performance of the proposed pairing algorithms was evaluated by averaging Jain's fairness indexc over all location sets. The optimal pairing demonstrates the best fairness performance and achieves the maximum Jain's fairness index, which is around 0.98. The performance of the heuristic schemes is only slightly inferior, as Jain's fairness index lies in the range [0.93, 0.96].
6.2 Power minimization: joint optimization of power and capacity
We herein present the results for joint optimization of power and capacity, given a certain network performance constraint in terms of the average outage probability per user and average capacity per user, respectively. The results are averaged over 102 location sets and 103 channel samples per location; furthermore, we used an epsilon, ϵ = 10−2 or 10% of the final value (whatever less).
6.2.1 Power minimization and capacity maximization, with a constraint on average outage probability per user
In Figure 6, the results for optimal power allocation per user (i.e., power minimization) are presented to meet the network performance constraint on the average outage probability per user of 0.1 and 0.2, with the latter requiring lower power owing to the inverse relationship of transmit power and outage probability. As it is observed, the optimal power decreases monotonically with the number of pairing users. As the number of users increase, the pairing opportunities improve, which allows the threshold outage probability to be achieved with lower power. Direct transmission has less power per user (to achieve the same outage probability). This is because direct transmission has lower SNR. However, this low SNR leads to lower capacity as indicated below.
Figure 6
Optimal (minimum) power allocation per user versus the number of paired users in the cell. This is to meet the constraint on the maximum average outage probability per user.
×
Figure 7 shows the results for the average capacity per user versus the number of users. A lower value of outage constraint leads to a higher average capacity, and vice versa, because of the inverse relationship between outage probability and capacity. It is noteworthy that the capacity for one particular value of outage constraint is steady, as anticipated (since the target outage probability is fixed). However, with a fixed transmission power (i.e., without power minimization), the capacity increases monotonically with the number of users as the pairing opportunities improve (e.g., see the optimal capacity pairing curve in Figure 4). Also, it is evident that direct transmission has lower capacity (<65% of that of network coding) due to the poorer links and the unavailability of diversity compared with network coding framework.
Figure 7
Average capacity per user versus the number of paired users in the cell. This is to meet the constraint in terms of the maximum average outage probability per user.
×
6.2.2 Power minimization and capacity maximization, with a constraint on average capacity per user
Figure 8 shows the results for optimal power allocation (i.e., power minimization) against the number of users to achieve the threshold average capacity. The value of the threshold capacity is chosen as 9.36 bps/Hz, which is the value achieved with the optimal capacity pairing for a fixed transmission power of 1 W and N = 20 (please refer to Figure 4). As expected, the optimal power decreases monotonically with increasing number of users, or in other words, with improvement of the pairing opportunities. An interesting point on the curve is for N = 20 where the optimal power is approximately 1.05 W, which is consistent with the results in Figure 4. The subtle discrepancy is due to the tolerance of the bisection optimization. The optimal (minimum) power per user of direct transmission is significantly higher than that of network coding (4 to 5 times) for the same average capacity per user (9.36 bps/Hz). This is because direct transmission needs to use much higher power to compensate for its poorer link.
Figure 8
Minimum average transmission power per user versus the number of pairing users. With a target capacity per user of 9.36 bps/Hz.
×
7 Conclusions
The important problem of the mutual pairing of users in cooperative wireless network coding is addressed in this paper. The performance gains achievable with network coding over traditional direct transmission are highlighted. To realize network coding, the proposed optimal pairing algorithm exhibits the maximum achievable network throughput, lowest outage probability, and highest fairness among all the proposed schemes. For networks with a smaller number of users and where pairing complexity is not the foremost concern, the optimal pairing is most favorable. Of the proposed heuristic algorithms, it was shown that max-max pairing exhibits a good capacity and fairness performance, whereas the max-min pairing matches the optimal pairing in terms of the average outage probability per user. Max-max pairing is therefore an excellent choice when high throughput and fairness are desirable, whereas max-min is preferable where the average outage probability is of vital concern. For energy-constrained wireless networks, we performed constrained power optimization to minimize the transmission power while meeting a certain network performance constraint, such as in terms of the average outage probability for reliability-hinged networks or average capacity per user for bandwidth-hinged networks.
Considering non-equal power allocation between the direct and network coding phases for a single user as well as non-equal power allocation to users in the cell is a problem for future investigation. Other interesting off-shooting directions are the consideration of the impact of imperfect channel state information on user pairing, as well as the inter-cell interference in multi-cell environments. For illustration, in this work, we considered an even number of users in the cell; addressing the unpaired user in case of an odd number of users is an additional aspect for future investigation.
Endnotes
aIn case if N is odd, one node will be excluded from pairing by the proposed optimal pairing algorithm. Devising optimal and heuristics schemes, which potentially revolve around the notion of iteratively excluding one node and pairing the remaining to search for optimal pairing, or excluding the node with the best source-destination link SNR for heuristic pairing is an interesting area for future investigation.
bConsidering unequal power allocation is an intriguing area for future investigation.
This work is supported in part by the Natural Sciences and Engineering Research Council (NSERC) of Canada through the NSERC Discovery program. We would like to thank the anonymous reviewers and the Editor, Professor H. Steendam, for their feedback, which helped us improve this paper.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Competing interests
The authors declare that they have no competing interests.
