实用网络编码系统的可靠传输策略

王 伟，金明录，曲 强②

0 引言

2000年香港中文大学的R. Ahlswede等人提出了网络编码这一概念。该理论以最大流最小割定理为基础，通过分析证明，网络中存在理论上的最大流。为了充分挖掘网络潜在的能力，达到理论最大流，网络编码应运而生[1]。Philip A.Chou,Yunnan Wu等人在前人工作的基础上，提出了一种适用于真实网络环境的实用网络编码系统。该系统成功的解决了真实网络中传输延迟以及网络拓扑复杂等问题，大大的推动了网络编码理论与实践的发展[2]。

1 实用网络编码简介

由于大部分确定性的网络编码算法只适用于单信源的无环无时延的多播网络，对于更普遍的多信源有环和时延的多播网络并不适用，文献[3]提出了完全随机选取线性编码系数的分布式的网络编码方式[4]。对于随机网络编码，每个接收节点只需要知道全局编码向量，就可以完成网络编码的解码过程了。在此基础上，文献[5-6]提出实用网络编码的概念。实用网络编码系统采用的编码算法是随机网络编码，在编码形成的数据包的前面加入该节点的编码向量的信息以及在节点中引入缓存池，这样便解决了实际网络中传输延迟大，网络拓扑结构复杂的问题。

以 4个信源节点 Sk，k=1,2,3,4,两个中继节点 rl，l=1,2以及若干个信宿Dn，n=1,2,…,N为例,如下页图1所示。

如果对于所有信宿都要接收来自于 4个发送节点的信息，对于某信宿Dn可与之通信的节点为S1，S2，r1，r2，则选择的接收路径是：S1Dn，S2Dn，r1Dn，r2Dn，对于 Di(i≠n)，与之通信的节点为S3，S4，r1，r2，选择的接收路径为：S3Di，S4Di，r1Di，r2Di。这样对于中继节点r1，r2则成为关键节点。Dn需要从r1，r2获得信息m3，m4。而Di需要从r1与r2获得信息m1，m2。这样在r1，r2引入网络编码技术可以增加网络的吞吐量。在r1与r2分别进行网络编码操作得到：

图1 网络举例

其中 gr1， gr2分别为 r1与 r2的编码向量。引入实际网络编码的思想，在r1与r2编码好的数据帧前面加入该节点的编码向量组成新的数据帧，即[ gr1Mr1]和 gr1Mr1]发送出去。将信源 S1-S4发送出去的数据也视为进行了网络编码操作的数据,只是在其原始数据前面加入少量编码向量信息 gr1=[1 0 0 0], gr2=[0 1 0 0]， gr3=[0 0 1 0]， gr4=[0 0 0 1]。这样，对于接收节点 Dn无论接收到了哪个节点发送过来的信息，当收到足够多的数据包后都先提取编码向量，再进行网络编码的解码操作即可[7]。

2 实用网络编码系统传输质量稳定性的研究

2.1 通信质量不稳定的原因

因为实用网络编码的系统中，整个的网络拓扑结构未知，因此在编码节点要将其编码向量放到分组交换的数据包的前面，便于接收节点解码。若在无线信道中，数据在传输过程中会受到噪声很大的干扰，而且对于一些能量有限的节点，如无线传感器网络节点，不能依靠提高发射功率的方法来提高信噪比，因此数据在传输过程中经常出现错误。尤其是对于网络编码系统的数据分组，当编码向量出现错误，会导致接收端收到的信息解码产生严重错误。如式（3）所示：

其中：

利用高斯消去法解该方程也即网络编码系统的解码过程。其中系数矩阵为每个输入链路上的编码向量信息，xj为原始信，yj为编码好的信息，n为编码向量的维数，也即同时进行编码的数据分组的个数。因为方程右边的取值为矩阵：

其中N为数据包的长度（除编码向量之外），每次解码只取出一列来参与解码操作。因此，若某一个 ykj，k=1,2,…,n。在传输过程中出现错误，甚至是某一列有错误，其影响的最终解码结果也只有对应的一列数据。但是如果系数矩阵G某一位出现错误，每组数据的解码都要用到该系数矩阵G，所以这样便会导致解码出现严重的错误使得通信质量不稳定，如下页图 3所示。表1中是对应的不同信噪比下，仿真循环50次时，编码向量错误的次数。由图3和表1可见在信噪比为2.5 dB的时候，误符号率之所以有一个突变的上升是因为编码向量在 50次循环中出现了两次错误。有时在信噪比较高的情况下，由于G出现错误误码率甚至会高于信噪比较低的信道，导致通信质量不稳定。另外，在当G因为噪声的干扰导致其不是满秩矩阵时，会导致解码失败。

图2 不对编码向量进行特殊保护的情况

表1 不同信噪比下编码向量出错的次数

2.2 实用网络编码系统提高传输稳定性的策略

针对上面提到的实用网络编码系统中，由于编码向量在传输过程中产生了错误而导致的通信质量不稳定甚至解码失败的问题。在不提高发送功率的同时降低误码率，只能采取各种信道编码的手段，以期通过增加冗余牺牲传输的有效性来提高可靠性。本文提出了三种对于编码向量保护的策略，这三种策略都是基于信道编码的算法来对编码向量进行保护的。一种是在发送节点对编码向量加入CRC循环冗余校验码来对编码向量进行保护；另外一种是利用协作编码的思想，针对网络编码系统类似于一个 MIMO系统的特点，对所选定编码节点的编码向量进行空时分组码的编码；第三种是在上述两种保护策略之间做一个折中的选择。三种保护方案的仿真均考虑在一个信宿节点所收到数据的误码率问题。

2.2.1 循环冗余校验的策略

循环冗余校验的策略，是在编码端对所有数据进行卷积码保护之前，先单独对编码向量加入CRC校验位，采用美国16-CRC标准，生成多项式为 x16+x12+x5+1。在解码端先进行卷积码解码，然后对编码向量的冗余位进行判断。如果出现编码向量的错误提示，则接收节点对于发送该数据分组的上游节点发出重传该分组数据请求。在上游节点存有发送数据的备份，若得到接收节点发送的重传请求，则重新发送该数据分组，直至在规定时间内不再收到重传的反馈信息为止。

2.2.2 空时编码保护策略

我们知道,使用多根发射天线和多根接受天线可以使无线通信系统的信息容量得到显著提高。空时编码是一种用于多发射天线的编码技术。该编码在多根发射天线和各个时间周期的发射信号之间能够产生空域和时域的相关性。这种空时相关性可以使接收机克服MIMO信道衰落和减少发射误码。对于空间未编码系统，空时编码可以在不牺牲带宽的情况下起到了发射分集和功率增益作用。

空时编码在编码结构上有多种方法，包括空时分组码(STBC),空时网格码(STTC),空时 turbo网格码和分层空时码(LSTC)。所有这些编码方案的核心思想是使用多径能力来获得较高的频谱利用率和性能增益的目的。虽然在无线网络中，每一个移动终端要存在多条输出天线是很难实现的,但是通过多个终端之间的相互通信，可以以协作编码(Cooperative Coding)的思想来传送数据。即终端A可以与终端B进行协作式的空时编码，互相利用彼此的天线来传送数据,构成了MIMO系统。本文正是利用上游节点之间的协作编码的思想，来组成一个MIMO系统，从而实现了空时编码技术在实用网络编码系统中的应用。本文所采用的是Alamouti空时分组码方案来对网络编码中的编码向量进行保护。

对于图2所示的网络，我们只考虑接收节点Dn，该节点需要接收 S1，S2，r1，r2发送的实用网络编码系统的数据分组。若 Dn的这四个上游节点之间实现通信，成为一个协作通信机制。对于这样的一个系统，实质是一个 4发送，1接收的MIMO系统。因此S1，S2，r1，r2就可以使用上面提到的 Alamouti空时分组码方案对数据分组中的编码向量进行STBC的编码方式保护，从而提高通信的质量。

2.2.3 模式切换保护策略

保护模式的切换方案，是指在上述两种模式之间的一个折中策略。考虑到循环冗余校验的模式需要大量的重传次数而空时分组码虽然对编码向量加以保护，但是仍然无法完全消除编码向量出现错误。因此提出了该方案，即在信噪比较低的情况下，采用空时分组码的形式来代替循环冗余校验；在信噪比较高时，采用循环冗余校验的方案。本文所仿真的模式是在信噪比不大于 2 dB的时候采用空时分组码的方式对编码向量加以保护，在信噪比大于 2 dB的时候改为循环冗余校验的模式。采用 2 dB作为模式切换的临界点是根据蒙特卡罗多次仿真得出的结论。

3 仿真结果与分析

仿真采用本文第二部分提出的网络模型，采用实用网络编码的分组格式，即该链路的编码向量信息放入到网络编码完成的数据帧前面，然后对所有数据加入码率为1/2的卷积码保护，再进行16QAM调制后发送数据。经过高斯加性白噪声的信道后，对于一个接收节点讨论其误码率的情况。

3.1 三种方案传输质量的比较

讨论4组发送节点的信息，原始信息位的符号为GF(23)域，在上面提到的模块基础上，将分别采用CRC模式，STBC模式对编码向量进行保护的情况与只进行卷积码保护的模式进行误符号率的比较，如图3所示。

图3 三种保护模式的比较1

可见通信质量最好的还是CRC模式，而用STBC模式保护编码向量相对于只进行卷积码保护的模式误符号率也有大幅的降低。但是STBC模式在信噪比较高的情况下由于仍然无法避免编码向量错误所带来影响，会产生通信质量不稳定的问题。但是在信噪比较低时，误符号率与 CRC模式很接近，并且其避免了重传所带来的费用。因此又提出了保护模式切换的方案。

从下页图4可见，采用保护模式切换的实行在低信噪比（2 dB以下）的时候误码率可以与CRC模式相接近，在较高信噪比（2 dB以上）的情况下，又有效避免了编码向量错误所产生的误码率突然升高的情况，保证了通信质量随着信噪比升高而提高。

3.2 CRC模式与切换模式的重传次数比较

在运行 50次蒙特卡洛仿真时，两种传输模式在不同信噪比下总的重传次数如下页表2所示。由表2可知，CRC模式在信噪比较低的时候，重传的次数很多，虽然通信的质量得以保证，但是效率很低。而采用保护模式切换的方案之后，因为在信噪比较低时采用的是 STBC的信道编码模式，因此没有重传的代价，而在信噪比较高时，重传次数也很少

图4 三种保护模式的比较2

表2 两种保护策略的重传次数统计

4 结语

本文提出了在实际网络编码系统中，对于编码向量进行保护的三种不同的保护策略。仿真结果表明这三种保护策略有各自的优势与缺点。对于CRC模式，通信的质量较高，但是需要大量的重传，效率较低；利用协作通信机制，在发送节点采用空时编码对编码向量进行保护，可以避免重传所带来的低效问题，但是同样会产生由于编码向量错误而带来的通信质量不稳定的问题；第三种折中的方案，在信噪比较低的时候误码率只比CRC模式略高，而在信噪比较高时在较少的重传次数的基础上又避免了通信质量不稳定的问题。

[1] Ahlswede R, Cai N, Li S Y R,et al. Network information flow[J].Information Theory,2000,46(04)： 1204-1216.

[2] Chou P A, Wu Yunnan. Network Coding for the Internet and Wireless Networks[J]. IEEE Signal Processing Magazine, 2007,23(05)：77-85.

[3] Tracey Ho, Muriel Medard, Jun Shi. On Randomized Network Coding[C].USA：[s.n.],2003：65-70.

[4] Jaggi S, Sanders P, Chow P A. Polynomial Time Algorithms for Multicast Network Code Construction[J]. IEEE, 2005(51)：1973-1982.

[5] Chou P A, Wu Yunnan, Jain K. Practical Network Coding[C].US：[s.n.],2003：781-790.

[6] 王晓海，黄开枝.空时网络编码[M].北京：机械工业出版社，2004.

[7] Koetter R,Medard M.A Nalgebraic Approach to Network Coding[J].IEEE/ACMTrans. Networking,2003(11)：182-795.