基于压缩感知解码的网络编码技术

高 超， 李生红， 唐俊华

（上海交通大学 电子信息与电气工程学院，上海，200240）

0 引言

在 R. Alshwed等人提出了网络编码[1]的概念之后，网络编码吸引了众多研究者的兴趣。在文献[1]中，作者证明了网络编码可以使网络容量达到最大流-最小割定理的理论上界。在此之后，网络编码的容量和组网方法又成为了研究的焦点。文献[2]中描述的无差错网络的线性编码代数模型证明了多播网络编码的存在。随机网络编码作为一种可行的分布式编码方案，在文献[3]中进行了详细讨论，证明了当所有的编码系数是从一个有限域中按照均匀分布的概率随机抽取时，可以以很高的概率得到一个可解码的网络编码。当网络编码不可解码时，其传输矩阵可视为一个欠定方程组的系数矩阵。借助压缩感知的思想，网络可解码的概率可以进一步增加。

压缩感知[4]是一种新的对稀疏信号的采样重建方法。Candes和Donoho等人证明了对于稀疏信号，可以采样部分信号，并利用采样通过一定的方法重建[5-6]。压缩感知的核心在于感知矩阵，也称为测量矩阵。Candes和Tao等人证明了满足有限等距性(RIP,Restricted Isometric Property)的矩阵可以用作感知矩阵。在随机网络编码中，传输矩阵的子矩阵具有RIP性质。仿真结果表明，压缩感知可以用于随机网络编码的解码。

1 系统模型

考虑单源单信宿的无误差无环网络。用一个有向图G=(V, E)表示此网络，V为顶点集，E为边集。每条边的容量为单位容量。如果两个节点之间实际容量大于 1，则用多条边表示。……