一种改进的多源组播网络的线性网络编码构造方案

卢花，高海波，张诚，冯新

（湖南涉外经济学院信息与机电工程学院，长沙410205）

0 引言

网络编码[1-2]技术通过向网络多播中的一些节点附加编码操作来最大化源点和每个宿点之间的多播容量。网络编码可以提高网络性能，甚至改变网络结构。其中,线性网络编码是重点研究方向。在文献[3]中，为了实现网络的最大吞吐量，子图问题通过组合优化解决。在考虑分源点优先级的情况下，提出了基于单目标优化的子图划分方法。文献[4]研究了多播节点执行网络编码的时间。实验数据表明，在极端情况下，节点编码操作的成本将产生很大的影响。文献[5]提出了多种方法降低网络编码成本。因要考虑多源组播网络中节点编码和解码的时间要求[6]，需要优化网络编码算法。利用粒子群优化算法进行子图划分[7-8]，可以优化子图的线性网络编码方案。

1 线性网络编码

网络编码允许中间节点复制和转发信息，中间节点对输入的信息还可以进行编码，再将编码后的信息转发给下游节点，后者起到编码器的作用。网络编码节点可以对从输入信息进行编码，并相应地将编码信息输出到相应链路。在接收节点处，解码器对接收的多播信息进行解码。如果节点对输入信息进行线性编码，则称为线性网络编码。

图1 和图2 中所示的蝶形网络说明了网络编码和路由的不同性质以及网络编码的优点。它也是可以实现最大多播容量的网络编码的示例。在网络编码示例中，每个信道仅使用一次，这不仅减少了传输次数，使网络负载更加平衡，同时减少了网络延迟并增加了网络吞吐量。

图1 传统路由示例

图2 网络编码示例

文献[9-10]中单源组播网络采用网络编码技术能获得最大组播能力，而利用传统的路由传输技术很难实现这种最大流量边界。

2 线性网络编码的构造

线性网络编码针对单位容量的信道进行编码，容量大于1 的信道被划分为多条单位容量的信道。

源点播出的字符和信道的全局编码向量构成一个线性方程。在接收点r(r ∈R)，可获得相应的解码方程组。只有当该方程组的系数矩阵的秩为h 时，才能求得源点广播的信息。

从图3 可以看出，信宿r 从第一输入信道接收的信息是y1=4*x1+2*x2，信宿r 从第二输入信道接收的信息是y2=7*x1+3*x2，信宿r 从第三输入信道接收的信息是y3=2*x1+7*x2。其中，x1、x2 和x3 是由源点广播的信息。

图3 线性网络编码示例

在宿点r 处，解码的线性方程组如下：

此系数矩阵的秩为3，解线性方程组可恢复出s 播出的信息x1、x2 和x3。

3 改进的线性网络编码的构造

改进的线性网络编码的思想是：采用传统路由方式与线性网络编码相结合的方式进行传输。对于每一个节点，先计算该节点的入度，以及该节点与相连的每个后续节点之间的吞吐量，若入度小于等于每一个相连节点之间的吞吐量，则这样的节点采用路由方式对信息进行存储和转发，而无需进行网络编码。若入度大于任意一个与之相连的后续节点之间的吞吐量，则此节点无法通过传统路由方式保证吞吐量，这样的节点需要进行线性网络编码，输出信息是该点所有输入字符的线性组合。

对于节点v∈V，记节点v 的入度为Indegree(v)=W(E1,v)+W(E2,v)+…+W(Ein,v)，E1,v表示以节点1 为弧尾，v 节点为弧头的弧线，in 表示以v 节点为弧头，与该节点相连的所有节点数目，W(E1,v)表示以节点1 为弧尾，v 节点为弧头的所有弧线数量，即有向边的权值。记节点v的出度为Outdegree(v)=W(Ev,1)+W(Ev,2)+…+W(Ev,out)，Ev,1表示以节点v 为弧尾，1 节点为弧头的弧线，out 表示以v 节点为弧尾，与该节点相连的节点数目，W(Ev,1)表示以节点v 为弧尾，1 节点为弧头的所有弧线数量，即有向边的容量，则节点v 与相连的后续节点之间的容量为{W(Ev,1),W(Ev,2),…,W(Ev,out)}，若∀(W(Ev,i))≥Indegree(v)(i=1,…,out)，节点v 采用路由方式对信息进行存储和转发，不进行网络编码。若∃(W(Ev,i))≤Indegree(v)(i=1,…,out)，则节点v 进行随机线性网络编码。同理，计算出全局编码矩阵的逆矩阵，可恢复出源点的信息。

如图4 所示，节点A、B、D 的入度均为1，后续每一个相连节点之间的容量均为1，入度小于等于相连的后续节点之间的容量，则节点A、B、D 采用路由方式对信息进行存储和转发，而无需进行网络编码，图中用虚线表示。节点C 的入度为2，出度为1，入度大于等于任意一个与之相连的后续节点之间的容量，节点C 无法通过一次传统路由方式传输信息x1 和x2，节点C 进行线性网络编码，输出信息是x1 和x2 的线性组合。

图4 改进的线性网络编码

4 仿真实验与结果分析

图5 有向无环网络G1

s1 对应宿点{r1,r2,r3}，s2 对应宿点{r4,r5,r6}，s3 对应宿点{r6,r7,r8}，{t1,t2,t3}为虚拟宿点集。对G1 划分子图，选取pareto 解集为{4,4,3}，得到3 个子图。假定优先考虑s2 的吞吐率，图6 子图2 中显示的信道可使s2获得最大组播容量，得到了从源点到各宿点的边互不重叠的传输路径，得到了一个可行的编码方案。

图7 显示了改进编码方案后时s2组播信息所经由的信道，可获得最大组播容量，与图6 的编码信道相比较，虚线部分的有向链路2-7、8-13、8-14、12-18、12-19、14-21、21-r6 均为存储转发方式，并未参与网络编码。在一定程度上节省了时间和存储资源。

图6 子图2 的编码信道

图7 改进后的子图2 的编码信道

表1 各编码节点的局部编码向量

表1 是各编码节点随机生成的局部编码向量，表2是各宿点对应各信道的全局编码向量，以宿点r4 为例，根据线性网络编码构造方案求解源点发出的字符。

表2 各宿点输入信道的全局编码向量

5 结语

网络编码技术可以提高组播吞吐量。如果网络中的某些节点或信道发生故障，接收器仍然可以解码。网络编码可以增强网络的容错能力，改善了网络链路的负载均衡，实现了多目标优化，无需其他加密算法，可以改善网络安全性。在后续工作中，需要考虑多源组播的安全性，并进一步完善本文的解决方案。