Capacity Region of Wireless Network Coding

Jun Zhang, Shu-Tao Xia

► To cite this version:

Jun Zhang, Shu-Tao Xia. Capacity Region of Wireless Network Coding. 11th IFIP International Conference on Network and Parallel Computing (NPC), Sep 2014, Ilan, Taiwan. pp.534-537, 10.1007/978-3-662-44917-2_46. hal-01403133

HAL Id: hal-01403133

https://inria.hal.science/hal-01403133

Submitted on 25 Nov 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Capacity Region of Wireless Network Coding

Jun Zhang¹, Shu-Tao Xia¹

¹ Graduate School at Shenzhen, Tsinghua University, Shenzhen, China
zhangjun.zero@gmail.com, xiast@sz.tsinghua.edu.cn

**Abstract.** Network coding is a highly regarded technology for improving the capacity of wireless networks. COPE-sys network coding is an easily implemented and widely studied coding system. This paper studies the maximum throughput that can be supported by COPE-sys network coding over a practical CSMA/CA medium access control (MAC) protocol. Traditional method of analyzing capacity is multi-commodity flow (MCF) formulation, which assumes impractical centralized scheduling. We enhanced MCF formulation by taking into account the collision overhead in the distributed CSMA/CA protocol, to compute the maximum throughput. To the best of our knowledge, this paper is the first rigorous theoretical study of the achievable capacity over a multi-hop CSMA/CA based wireless network coding system.

## 1 Introduction

We develop a method to integrate CSMA/CA MAC analysis with the MCF formulation. We enhance traditional MCF clique constraints by utilizing the maximum normalized throughput. Our method can give a tighter upper bound of the network coding throughput over the CSMA/CA MAC. We also give an achievable lower bound of the network throughput by analyzing conflict within cliques and inter-cliques.

## 2 Capacity Region over CSMA/CA MAC

### 2.1 Throughput Analysis

The wireless network discussed in this paper is assumed to be a static, multihop wireless network where all nodes are single-channel single-radio and all antennas are omnidirectional. Let $p_t$ denote the transmission probability for each node in any time slot. A time slot at the MAC layer could be an empty backoff time slot, a period associated with successful transmission, or a period associated with collision [1]. The length of a time slot equals to one physical time slot $T_{idle}$ if the channel is idle, or the packet transmission time $T_s$ if the channel is experiencing a successful transmission, or the packet collision time $T_c$ if a collision happens. Let $p_{idle}$, $p_s$, and $p_c$ denote the probabilities of seeing an idle slot, a successful transmission slot, and a collision
slot, respectively. Let $\epsilon_i$ denote the number of native packets in an encoded transmission. Let $L_p$ denote the payload size of a native packet and C the spectrum bandwidth. The normalized throughput $S$ are expressed as

$$S = \frac{\sum_{i=1}^{N} [p_t (1 - p_t)^{N-1} \times \epsilon_i] \times L_p}{C \times (p_{idle} \times T_{idle} + p_s \times T_s + p_c \times T_c)} \quad (1)$$

We use a Markov chain to compute $\epsilon_i$. To obtain the maximum channel utilization and normalized throughput, we can determine $p_t$ according to $\frac{d}{dp_t} R_S|_{p_t=p_t^*} = 0$. The maximum normalized throughput can be computed as

$$S^* = \frac{\sum_{i=1}^{N} [p_t^* (1 - p_t^*)^{N-1} \times \frac{n_i M}{M+1}] \times L_p}{C \times (p_{idle}^* \times T_{idle} + p_s^* \times T_s + p_c^* \times T_c)} \quad (2)$$

## 2.2 Upper Bound

Suppose that there are k given commodities with pairs $\{s_x, t_x\}$, where $s_x, t_x \in V$ are source and destination for commodity x respectively. Let $\mathcal{F}_x$ denote the set of $s_x$-t_x flows. A k-flow is a sequence of flows $<f_1, f_2, ..., f_k>$ with $f_x \in \mathcal{F}_x$, $x=1, 2, ..., k$. The classic MCF formulation without considering the wireless interference is expressed as [2]

$$\max \sum_{i=1}^{k} val(f_x) \quad (3)$$

$$\text{s.t.} \quad f_x \in \mathcal{F}_x, x = 1, 2, ..., k, \quad (4)$$

$$(\sum_{x=1}^{k} f_x) \not\in \mathcal{B} \in \mathcal{P}, \quad (5)$$

A clique in NC network in the conflict graph is a set of vertices that mutually conflict with each other. Note that a vertex in conflict graph in NC network may represent a hyperarc. In a clique at most one hyperarc can transmit at a time. Suppose that there are R maximal cliques in the conflict graph $G$, denoted as $C_1, C_2, ..., C_R$, respectively. If a hyperarc (i, J) within a maximal clique is allocated the transmission time of $t_{ij}$ during the whole clique transmission interval T, the upper bound of the maximum network throughput can be solved by augmenting the basic MCF formulation with the clique constraint (6)

$$\sum_{(i,j) \in C_u} \sum_{(i,j) \in (i,j)} \frac{1}{B_{ij}} \sum_{1 \le x \le k} f_{xij} \le |J| \quad u = 1, 2, ..., R \quad (6)$$

Let $\hat{F}$ denote the upper bound of the MCF throughput based on the clique constraint. We have the following theorem about a tighter upper bound of the network throughput over the CSMA/CA MAC.
**Theorem 1:** A tighter upper bound of the optimal throughput of a wireless NC network based on a CSMA/CA MAC protocol is $\hat{X} = (S^*\hat{F})/|J|$.

Proof: Since simultaneous transmissions will not be successful under the CSMA/CA protocol within a clique, the maximum normalized throughput over a maximal clique is upper-bounded by $S^*$. Then the clique constraint under CSMA/CA MAC is now expressed as

$$ \sum_{(i,j) \in C_u} \sum_{(i,j) \in (i,j)} \frac{1}{B_{ij}} \sum_{1 \le x \le k} x_{xij} \le S^* \quad u = 1, 2, \dots, R \quad (7) $$

If we define $f_{xij} = \binom{x_{xij}}{S^*} |J|$, the new MCF formulation with the constraint of (7) is then transformed back to the original clique-based MCF formulation assuming a centralized scheduling (6). Therefore, the optimal throughput is $\hat{X} = (S^*\hat{F})/|J|$.

## 2.3 CSMA/CA Area and CSMA/CA Clique

A circle with a diameter of $\mathcal{X}'$ is termed as a CSMA/CA area, where $\mathcal{X}'$ denote interference range. Considering that we adopt the protocol interference model, we define a CSMA/CA clique as follows: let $\mathcal{A}_C$ denote the CSMA/CA area and $i \in \mathcal{A}_C$ denote that node i is within the CSMA/CA area $\mathcal{A}_C$. The clique C consists of hyperarcs satisfying that source node of the hyperarc is within $\mathcal{A}_C$ or all the destination nodes of the hyperarc are within $\mathcal{A}_C$. We have the following lemma regarding the maximum normalized throughput over a CSMA/CA area and the associated CSMA/CA clique (the proof is ignored due to the limit of space).

**Lemma 1:** The total normalized throughput over a CSMA/CA clique can be transformed to that over the CSMA/CA area defining the clique, and vice versa. Thus, the maximum normalized throughput over a CSMA/CA clique is $S^*$.

## 2.4 Lower Bound

The fundamental reason that the clique-based MCF formulation gives an upper bound, which may not be achievable, is that the interference among the cliques in the multihop context can not be described by the clique constraint. Considering inter-clique interference over each clique, we have the following theorem about a lower bound of the network throughput.

**Theorem 2:** For a uniform network, a lower bound of the optimal throughput over the CSMA/CA MAC is $\hat{X} = \frac{\pi^*(x')^2}{(\max\{U\{D_w\}\})^*4} \hat{X}$, $w \in Nei\{i\}$, where $\mathcal{X}'$ denotes the interference range, $D_i$ denotes the area of the circle center at node i, i can be any node in the network, and $\hat{X}$ is the upper bound given in Theorem 1. Thus, the lower bound is at least $\frac{\pi^*(x')^2}{(\max\{U\{D_w\}\})^*4}$ of the maximum capacity $X^*$.
Proof: From lemma 1, we can transform the total throughput over a CSMA/CA clique C to the associated CSMA/CA area $\mathcal{A}_C$. Let $D(\mathcal{A}_C)$ denotes the area of $\mathcal{A}_C$. If nodes are uniformly distributed with a density of $\rho$, the number of nodes contained in $\mathcal{A}_C$ is $\rho D(\mathcal{A}_C)$, each node $i \in \mathcal{A}_C$ can achieve the throughput of $S^*/\rho D(\mathcal{A}_C)$.

Suppose node A transmits to its neighbors. To ensure all destination nodes are free of conflict, all the circles centered at these destination nodes with radius of $\chi'$ should be consider as one CSMA/CA area, as shown in Fig. 1. Then the number of nodes contained in this CSMS/CA area is $\rho * (D_B \cup D_C \cup D_D \cup D_E) = \rho * \cup \{D_w\}, w \in \text{Nei}\{A\}$. Then a lower bound of the achievable throughput of the tagged node A is $S^*/\rho * \cup \{D_w\}$. Considering all the nodes contained in $\mathcal{A}_C$, a lower bound of the achievable throughput of any node in $\mathcal{A}_C$ is $S^*/\rho * \max\{\cup \{D_w\}\}$.

<figure><img src="image_2.png" /><figcaption>Fig. 1 Possible interference on a clique</figcaption></figure>

In a uniform network, all nodes have the same stochastic behavior, therefore the same achievable throughput. Thus, the lower bound of the total achievable throughput over a CSMA/CA area, with inter-clique interference taken into account, is

$$ \tilde{S} = \rho D(\mathcal{A}_C) \times \frac{S^*}{\rho * \max\{\cup \{D_w\}\}} = S^* \frac{\pi(\frac{\chi'}{2})^2}{\rho * \max\{\cup \{D_w\}\}} \quad (8) \\ = \frac{\pi * (x')^2}{(\max\{\cup \{D_w\}\}) * 4} S^* $$

Therefore, the total throughput $S$ over a CSMA/CA clique C is achievable if $S \le \frac{\pi*(x')^2}{(\max\{\cup\{D_w\}\}) * 4} S^*, w \in \text{Nei}\{i\}, i \in C$. Regarding the total throughput over the whole network, we have theorem 2.

## References

1. G. Bianchi, Performance analysis of the IEEE 802.11 distributed coordination function, IEEE J. Sel. Areas Commun., vol. 18, no. 3, pp. 535–547, Mar. 2000

2. JY. Zhou, ST. Xia, Y. Jiang, HT. Zheng and LZ. Cui, Maximum Multiflow in Wireless Network Coding, IEICE Trans. Fundamental Theories for Communications, vol. E96-B, no.7, pp.1780-1790, 2013