Abstract
We present matrix network coding methods that are
naturally amenable to a distributed implementation method, i.e.,
do not require the knowledge of network topology, and that are
suitable for network error correction. First, the Singleton bound
can be K-fold increased by employing a K×K matrix coefficient.
Moreover, we prove that matrix network coding outperforms
linear network coding, since it corrects more errors than linear
network coding, while the amount of header overhead per packet
can be kept the same by reducing the finite field size. This comes
from the fact that the finite field size of matrix network coding
required to guarantee the sufficient decoding probability is much
smaller than linear network coding. Secondly, matrix network
coding is refinable in the sense that, by receiving a larger number
of network coded packets, larger error correction capabilities are
achieved. Simulation results show that matrix network coding can
provide 0.7 − 2[dB] more coding gain than the linear network
coding schemes.
I. INTRODUCTION
Recently, wireless ad-hoc networks have received much
attention, because of their applications to sensor networks
and wireless local-area network (LAN) meshes. Such adhoc
networks can improve the coverage of LANs and enable
networking among wireless sensors and handheld devices.
For such consumer applications, a wireless ad-hoc network
needs to accommodate multiple data-flows that have different
source/destination pairs. Each data-flow takes multiple hops
over the air from a source node to a destination node, thus
requiring intermediate nodes for relaying. Usually, such relaying
protocol has been implemented using ad-hoc routing
protocols, for example, ad-hoc on demand vector routing
(AODV) in WLAN mesh using IEEE 802.11s standards [14].
Unfortunately, such ad-hoc routing schemes may not provide
enough performance and robustness to support consumergrade
handheld devices. This is because multiple data-flows
would intersect at a certain relay node, the ad-hoc routing
protocols may suffer from the bottleneck effect at the relay
node. In addition, since handheld devices would frequently
move in and out of the network, ad-hoc routing protocols may
not support sufficient robustness to such topology changes and
may increase error rates. One of the candidates for improving
ad-hoc routing protocols is network coding [4].
The concept of network coding was first invented by
Ahlswede et al. who proved that it is suboptimal to restrict
the network nodes to perform only routing [1]. Li et al. [8],
and Koetter and M´edard [7] showed that the multicast capacity
can be achieved by only allowing linear operations in the
intermediate nodes. Later, Ho et al. [6] showed that the linear
network coding coefficients can be randomly selected, while
the decoding probability approaches to 1 exponentially as the
field size increases. On the other hand, a simple XOR network
coding scheme was used in an IEEE 802.11 mesh network in
[10]. It has been shown that this network coding significantly
improves the throughput of both multicast and unicast traffic.
In this paper, we explore the other benefit of network coding:
the robustness to channel errors.
In network coding, intermediate nodes between various
source/destination pairs typically transmit a linear combination
(computed over finite field F2m) of their various received
data streams. If N packets P1, P2 · · · , PN defined over finite
field F2m are network coded, then N linear combinations of
these packets are usually sufficient to decode P1, · · · , PN at
the receiver. When a destination node receives more than N
linear combinations of P1, · · · , PN, this additional information
can be used for error correction to improve the robustness
to channel errors. Yeung and Cai [12] considered this issue
and then further explored in [13]. These papers establish
upper and lower bounds on the error correction capability
of network codes analogous to the singleton and Gilbert-
Varshamov bounds. In their work it is assumed that the
network topology is known, nonetheless they do not provide
concrete constructions that can be used in practice (over
arbitrary network topologies). This motivates our approach in
this paper, where we introduce matrix network coding schemes
to enable network error corrections. We will remove the
restriction on the knowledge of network topology in designing
our network coding methods by using random matrix coding
coefficients, similarly as random linear network coding in [6].
The outline of this paper is the following: In Section
II, we review random linear network coding and discuss
its limitations in network error correction. We then present
the mathematical model of our system and introduce matrix
network coding in Section III. In Section IV, we explain
the encoding and decoding algorithms for the matrix network
coding. We then compare the random linear network coding
scheme and the proposed matrix network coding scheme in
Section V.

Download full report
http://googleurl?sa=t&source=web&cd=1&ve...r_2318.pdf&ei=kHMyToGZF43IrQfwgN3NCw&usg=AFQjCNEU2PGCaPsVy5FB2zIHy9xVH4HIjQ&sig2=coOQFR9FbynRM8Z6L1nPxw