01.12.2013 | Research | Ausgabe 1/2013 Open Access

# User pairing in cooperative wireless network coding with network performance optimization

## Electronic supplementary material

## Competing interests

## 1 Introduction

## 2 System model

_{ i }[m] is the transmitted source information symbol, n

_{ D }[m] is the AWGN noise at the destination, and the channel coefficient h

_{i,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

_{ j }[m] is the AWGN noise at node j, and h

_{i,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

_{ j }[m − L/2] is the symbol transmitted by node j, n

_{ i }[m] is the AWGN noise at node i, and h

_{j,D}and h

_{j,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

## 3 Capacity and outage performance analysis

### 3.1 Direct transmission phase

_{i,j}= log

_{2}(1 + γ

_{i,j}), where γ

_{i,j}= |h

_{i,j}|

^{2}P/N

_{0}is the instantaneous SNR of the inter-source link, with P as the transmit power and N

_{0}as the noise power spectral density. An outage occurs when C

_{i,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]

_{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

_{i,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 s

_{ i }⊕ s

_{ j }is received twice over uncorrelated channels).

## 4 User pairing and capacity maximization

^{*}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^{*}

^{a}. Each pairing P is a symmetric mapping of elements from the set $\mathbb{X}\in \left\{1,2,\dots ,N\right\}$ to the set $\mathbb{Y}\in \left\{1,2,\dots ,N\right\}$, with the restriction that an element from $\mathbb{X}$ cannot be mapped to the same element in $\mathbb{Y}$. The goal is to find the optimal pairing P

^{*}that maximizes the total network capacity C = ∑

_{ i }C

_{ i }. Therefore,

_{i,j}= [W]

_{j,i}= C

_{i,D}+ C

_{j,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.

_{i,j}= C

_{i,D}+ C

_{j,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].

_{i,j}∈ {0, 1} (which indicate that the edge (i, j) may not or may belong to the final pairing, respectively) by x

_{i,j}≥ 0. Moreover, additional constraints, i.e., ${\sum}_{i,j\in {V}_{o}}{x}_{i,j}\le \u230a\left|{V}_{o}\right|/2\u230b$, are added for all odd subsets of vertices V

_{ o }. We have a primal solution, a pairing P, and a dual solution which is the assignment of the dual variables which are denoted by u

_{ i }(for all vertices) and z

_{ k }for all odd subset of vertices, ${V}_{{o}_{k}}$. The slack variables are defined as ${\pi}_{i,j}={u}_{i}+{u}_{j}-{w}_{i,j}+{\displaystyle {\sum}_{i,j\in {V}_{{o}_{k}}}{z}_{k}}$. 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:

_{ i }, π

_{i,j}, z

_{ k }≥ 0.

_{i,j}= 0.

_{ k }> 0 ⇒ subset of vertices ,

^{3}) time, whereas an exhaustive search would require (N − 1) ! ! calculations, where !! denotes double factorial.

### 4.2 Heuristic pairing algorithms

_{i,j}= [W]

_{j,i}= C

_{i,D}+ C

_{j,D}is established, where i and j are potential pairs. The algorithm is formally presented as follows:

_{i,j}, and form the pair by augmenting P with i and j.

^{3}) 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}) and is formally presented as follows:

_{i,D}and pair it with node j with max[min(γ

_{i,j}, γ

_{j,D})].

## 5 Power minimization: joint constrained optimization of power and capacity

^{b}. 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 P

_{ c }

^{*}. 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

_{ 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, P

_{min}

^{*}, i.e., the minimum power which meets this constraint on outage probability, satisfies the equation

_{m}*, we locate the root of the function

_{ l }, P

_{ u }], such that it contains the root of F(P), i.e., P

_{m}*. 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:

_{ l }and P

_{ u }.

_{ l }+ (P

_{ u }− P

_{ l })/2.

_{ cap }* for transmission power P.

_{ u }− P

_{ l }) < ϵ, and F(P) > 0, exit

_{ l }) ⋅ F(P) > 0, then P

_{ l }= P

_{ u }= P

### 5.2 Power minimization and capacity maximization with constraint on average capacity per user

_{ 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, P

_{m}*, i.e., the minimum power per user which meets this constraint on average capacity per user, satisfies the equation

_{min}

^{*}, we locate the root of the function

_{ l }and P

_{ u }.

_{ l }+ (P

_{ u }− P

_{ l })/2,

_{ c }* for transmission power P,

_{ u }− P

_{ l }) < ϵ, and F(P) > 0, exit

_{ l }) ⋅ F(P) > 0, then P

_{ l }= P

_{ u }= P

## 6 Simulation results

### 6.1 User pairing for capacity maximization: fixed power allocation

^{3}location sets and 10

^{3}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.

^{c}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

^{2}location sets and 10

^{3}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

#### 6.2.2 Power minimization and capacity maximization, with a constraint on average capacity per user

## 7 Conclusions

## Endnotes

^{a}In 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.

^{b}Considering unequal power allocation is an intriguing area for future investigation.

^{c}Defined as $J={\left({\displaystyle {\sum}_{i=1}^{N}{C}_{i}}\right)}^{2}/\left(N{\displaystyle {\sum}_{i=1}^{N}{C}_{i}2}\right)$[28].