基于网络编码的无线网络吞吐量分析与优化

《基于网络编码的无线网络吞吐量分析与优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、巾l词科学技术大学硕十论文第2章网络编码概述§2．1引言在前一章中，本文定义了max．flow界。在以下的论文，我们将用一个章节的内容，讲解线性网络编码如何取得max．flow界。这一部分的内容散秩于诸多文献，例如，文献[4】把网络编码看作是经典信息论的～。种扩展，本章的主要内容基于文献14】。在继续讨论之前，这里对“有限域”这·在编码理论领域常用的概念进行简单的同顾，有助于理解网络编码的编码／解码过程。有限域是指这样的⋯个符号集合，在该符号集合上，定义了类似于实数域上的四种算术运算：加，减，乘，除。这类似于对于所有的实数，以及在任意的两个实数之间定义的加减乘除四则

2、运算，构成了实数域。然而，与实数域具有无限的、不可数的元素个数这些特性不同，有限域，顾名思义，具有有限数目的元素。【5】的附录C给出了‘一个很好的、简略的、有关有限域以及编码理论的数学理论基础。在一个线性网络编码中，所有的信息符号都被看作是有限域，上的元素；这里，F被称为基域。这里的信息符号，既包括源信息符号，也包括在每条信道上传输的符号。例如，当F是■进制的GF(2)域，也就是0一l比特，源发送的一个符号，以及在每条信道上传输的一个符号，就是比特；F=GF(2)上的加法和减法运算，就是二进制异或运算；F=GF(2)上的乘法和除法运算就是二进制与运算(注意：除数不能

3、为O)。更复杂地，如果F=GF(2”1，那么源每发送的符号以及在每条信道上传输的每个符号，就是m个比特。更进。步地，由于编码和解码是对基域F中多个符号进行在基域尸上的线性代数操作(e．g．，数乘和相加)，因此，可以得到高速可编羁!器件1来构建码字和编／解码。在这一章中，本文考察在无环网络上，由有限长的符号块所组成的分组网络。这里，“有环网络”和“无环网络”的概念，来源于对网络拓扑的有向图G(V，E)建模：y表示网络拓扑的节点，而E表示网络拓扑的有向边，边的方向指向分组的传送方向。如果G(V，E)存在环路，就称该网络为有环网络；不然，就称该网络为无环网络。其次，本文作

4、如F的理想假设：网络上的分组传输延迟(包括节点处理数据带来的延迟，以及分组在信道传输的延迟)为零。虽然，在实际网络中，网络上的分组传播延迟有限但非零、不可忽略的；而且，这些传输延迟的累加，决定了网络上从源点到宿点的传输时延，这个传输时延可以作为网络性能和代价的+种衡最。但是，在无环网络上，串行流动的分组从源点流向宿点，不存在分组的环路，因此，传输延迟不会影响多个分组的线性操作：这时候，分组传播延迟为零的假设是合理的。然而，当网络存在环路，网络上的节点就需要处理反馈的分组，而且反馈的时间与分组在反馈环路上分组传输时延有关。在这种情况F，网络的传输延迟就得考虑。§2．2

5、。无环网络记网络拓扑表示为G=(矿，E)，这里矿和E分别表示网络节点集合和网络上的边集合。记号tn(t)表示进入节点，的输入边，绝对值Izn(t)I表示节点t的入度；记号Out(t)表示离开节点t的输出边，lOut(t)I表示节点t的出度。如果这一对边(d，P)满足：存在一个节点t∈V。使得d∈Zn(t)，而e∈out(t)，那么称某一对边(d，P)∈ExE是一对相邻的边。定义：(有向路径，无环网络)G中的有向路径，是指一‘组边序列：(el，e2，．．．，em)。其中，(el，ej+．)是。对相邻的边(1≤f

6、，序列(el，e2，．．．，气)就是从t剑t’的‘条有向路径。如果t=f’，那么，(岛，P’，．．．，气)有向路径构成‘个有向环路。G如果含有向环路，就称G为有环网络；否则，就称G为无环网络。无环网络的‘个特点是，网络上的节点可以Hj某种次序被排列。1文献f6】给⋯‘种基于基域F的乘法和幂运算的非线性的网络编码。本质}：，这种非线件网络编码对应于基域F的对数域的一种线性运算，但是它可以利用现有的FPGA硬件电路，快速实现基域F．1：的乘法和幂运算。第5页≯∈53贞巾Ⅲ科学技术人学硕十论文定理：如果G是一个有限的无环图，那么可以把G中的节点以满足以下的次序方式排列，使

7、得：如果有一条边从节点i到达节点，，那么在该排列方式中，i总是排列在，的前面‘。证明：该定理相当于图论中有向无环图的拓扑排序问题，【4]给出了详细的证明，[7】给出了寻找拓扑排序的图深度搜索算法。§2．3线性网络编码这。节归纳无环网络G上定义的线性网络编码。为了简化描述，这里假设：所有的边都具有单位的容最：换句话说：在每条边上只能在单位时间内发送和接收基域F中的‘个符号。实际上，如果某条边具有咒(>1)个单位的容黄，那么，该边可以等价为：在每‘对节点之间存在着胛(>1)条并行的、具有单位容帚的边。G具有唯一的源点’s，在源点S上。呜；消息由w个符号构成，每个符号