---
abstract: 'A key problem in network coding (NC) lies in the complexity and energy consumption associated with the packet decoding processes, which hinder its application in mobile environments. Controlling and hence limiting such factors has always been an important but elusive research goal, since the packet degree distribution, which is the main factor driving the complexity, is altered in a non-deterministic way by the random recombinations at the network nodes. In this paper we tackle this problem with a new approach and propose Band Codes (BC), a novel class of network codes specifically designed to preserve the packet degree distribution during packet encoding, recombination and decoding. BC are random codes over GF(2) that exhibit low decoding complexity, feature limited and controlled degree distribution by construction, and hence allow to effectively apply NC even in energy-constrained scenarios. In particular, in this paper we motivate and describe our new design and provide a thorough analysis of its performance.We provide numerical simulations of the BC performance in order to validate the analysis and assess the overhead of BC with respect to a conventional random NC scheme. Moreover, experiment in a real-world application, namely peer-to-peer mobile media streaming using a random-push protocol, show that BC reduce the decoding complexity by a factor of two with negligible increase of the encoding overhead, paving the way for the application of NC to power-constrained devices.'
author:
- 'Attilio Fiandrotti,  Valerio Bioglio,  Marco Grangetto,  Rossano Gaeta, and Enrico Magli,  [^1]'
bibliography:
- 'main.bib'
title: 'Band Codes for Energy-Efficient Network Coding with Application to P2P Mobile Streaming'
---

Network Coding, Rateless codes, P2P, Mobile Streaming, Energy-Efficiency.

Conclusions and Future Work {#sec:conclusions}
===========================

In this paper we presented Band Codes (BC), a family of codes that preserve the packet degree distribution enabling controlled-complexity NC independently from the network topology. Our experiments show that BC reduce the decoding complexity by a factor of two with almost no losses in encoding efficiency with respect to random NC. Furthermore, a reduction of up to four times is achieved while maintaining the encoding overhead below 5%. Experiments with a mobile phone showed that the reduced computational complexity reduces its energy consumption extending the operational lifetime. Streaming experiments show that our P2P protocol designed around BC is capable to deliver high quality video on the global scale testbed, showing the benefits of BC in a realistic setting. Although in this work we have focused on P2P video streaming, BC are well suited in any scenario where energy consumption is a critical issue, such as sensor networks. Finally, while we have considered NC over $GF(2)$ thanks to its low complexity, the main concepts behind BC can be extended to Galois fields of larger size.

\[sec:appendix\] We indicate with $\Omega^j$ the packet degree distribution in the network after $j$ recombinations, i.e. the probability that a randomly selected packet in the network has degree $i$ after $j$ recombinations is $\Omega^j_i$. The source node encodes packets of degree $d$ with probability $\Omega_d^0$. Let $P^1$ and $P^2$ be two packets in the network with degree $d^1$ and $d^2$. We define as $s_N(d^1, d^2, d^r)$ the probability that the recombination of $P^1$ and $P^2$ produces a packet $P^r$ with degree $d^r = d^1 + d^2 - 2\chi$, where $\chi$ is the random variables that counts the number of times that $g_i^1 = g_i^2 = 1$ for $i \in [0, N-1]$.

$$s_N (d^1, d^2, d^r) = s_N (d^1, d^2, d^1 + d^2 - 2\chi) = \mathbb{P}(2\chi = d^1 + d^2 - d^r) = \mathbb{P}(\chi = \frac{ d^1 + d^2 - d^r }{2}).$$ $$\begin{array}{r c l}
    s_N (d^1, d^2, d^r)& = & s_N (d^1, d^2, d^1 + d^2 - 2\chi)\\
    & = & \mathbb{P}(2\chi = d^1 + d^2 - d^r)\\
    & = & \mathbb{P}(\chi = \frac{ d^1 + d^2 - d^r }{2})\\
    \end{array}$$ As $\chi$ follows the Hypergeometric Distribution $\mathcal{H}(N, d^1, d^2)$, we rewrite the above equation as

$$\begin{array}{r c l}
s_N (d^1, d^2, d^r)& = & \frac{\binom{d^1}{\frac{ d^1 + d^2 - d^r }{2}}\binom{N-d^1}{d^2-\frac{ d^1 + d^2 - d^r }{2}}}{\binom{N}{d^2}}.
\end{array}$$ For the law of total probability, we have that\
$$\label{eqn:omega_recursive}
\Omega^j_i = \sum_{d^1=0}^{N} \sum_{d^2=0}^{N} s_N(d^1,d^2,i) \Omega_{d^1}^{j-1} \Omega_{d^2}^{j-1}.$$ We indicate as $\Omega^\infty$ the distribution of the degree of the packets in the network after a number of recombinations that tends to infinite. If $\Omega^0$ is not degenerate, we have from Equation \[eqn:omega\_recursive\] that $$\Omega^{ \infty }_i  =\frac{\binom{N}{i}}{2^{N}}.$$ Therefore, the distribution of the degree of the packets in the network follows the Binomial Distribution $\mathcal{B}(N, \frac{1}{2})$ and the average degree of the packets in the network tends to $\frac{N}{2}$.

[^1]: Copyright (c) 2013 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org.

    This publication is based partly on work performed within Project COAST-ICT-248036 which is funded by the European Union, partly on work performed within project AMALFI which is funded by Università di Torino and Compagnia di San Paolo, partly on work performed within project ARACNE, a PRIN funded by the Italian Ministry of Education and Research.

    A.Fiandrotti, V.Bioglio, and E. Magli are with the Department of Electronics and Telecommunications, Politecnico di Torino, 10129, Torino, Italy (e-mail: attilio.fiandrotti@polito.it; valerio.bioglio@polito.it; enrico.magli@polito.it).

    M.Grangetto and R.Gaeta are with the Department of Computer Science, Università di Torino, 10149 Torino, Italy (e-mail: marco.grangetto@di.unito.it; rossano.gaeta@di.unito.it).
