网络编码及其应用优势分析

曹骞 程军

（巢湖学院计算机与信息工程学院，安徽 巢湖 238000）

为了提高组播中传输效率，香港中文大学的R.Alshwede等人[1]提出并证明如果网络节点不只是简单的对传输的信息进行存储和转发，而且可以利用线性编码方式对信息进行处理，可以让网络组播实现理论上的最大传输流量，我们将这种方法称为网络编码。网络编码方法可以按照网络中节点对消息的处理方式分为线性和非线性两种，也可以按照网络编码系数的生成方式划分为随机网络编码和确定型网络编码。目前网络中有三种通讯模式：单播、广播和组播，其中组播同时具有单播和广播的优点，组播是通过在发送者和每一接收者之间实现点对多点的网络链接，加入到同一个组的主机可以接收到此组内的所有数据，发送者同时给多个接受者传输的数据相同，只复制一份相同的数据包组播的数据传送效率较高，能够有效地减少网络拥塞的出现。传统的组播通过构造多播树实现，其构造过程一般是NP完全问题。而且传统网络中的中继节点只能对数据进行存储和转发，不能够对数据进行编码处理，在传输过程中不能通过编码技术对信息进行叠加，因此大多数算法都不能达到”最大流、最小割”定理确定的理论流量值[2]。下面我们通过一些例子简单说明网络编码的原理极其特点：

1 网络编码原理

在组播树中我们可以利用Ford and Fulkerson标号法，通过寻找源节点和信宿节点之间的增广链并进行调整，可以寻找到最大流。对于单信源多接收的网络，第一个查找的信宿节点可以通过这种标记方法查找到与信源节点之间的最大流，但是从第二个信宿节点开始，在查找开始前需要把第一个信宿节点与信源节点之间用掉的容量从网络中去除，因为传统网络中的节点只能够对信息进行简单的存储和转发，并不能够对信息进行叠加处理和传输，所以用组播树的方式构建的最大流方法，只有第一个信宿节与信源节点之间能够以最大流进行传输，其他的信宿节点都不能够达到最大流，最终实际的组播传输容量达不到理论上的最大流最小割定理确定的理论容量上限，所以我们希望网络中的节点不仅仅能够对信息进行存储和转发，如果中继节点能够对需要传播的多条信息进行处理，将信息进行叠加之后进行传输，在不增加网络流量的情况下扩充网络传输的能力。图1（a）是一个经典的“单信源二信宿”蝴蝶网络，其中s是信源，t1,t2是信宿，w,u,v1,v2是中继节点,a和b是信源s发出的信息，此图中的最小割为2即组播的最大理论容量为2，信宿t1,t2能够同时接收到信源s发出的2个单位的信息，但是传统的路由传输方式中，图中的w节点只能对收到的信息进行存储和转发，并不能对信息进行处理或者编码，在一个时间段节点w只能转发一种信息，所以与w相邻的节点只能接收到一种信息，假定w转发信息a，则链路（w，u），（u，t1）和（u，t2）中传输的信息都是 a，此时信宿t2接收到信息a，并且通过链路（v2，t2）接收到b，但是信宿t1只能接收到信息a，无法接收到信息b，在此图中组播不能达到追到理论传输容量。图1（b）中采用网络编码方式，对输入的信息进行模二加运算，将结果a+b发送至节点w，此时链路（w，u），（u，t1）和（u，t2）中传输的信息都是a+b，信宿t1,t2都能够接收到a+b，而且信宿t1通过链路（v1，t1）接收到信息 a，通过信息 a和信息a+b,能够解出信息b，同理信宿t2也能够收到信息a和b，采用网络编码的方式，提高了网络组播信息的传输效率，当网络编码的域无限大，则运用网络编码的组播传输能够达到理论上最大传输容量。

图1 蝴蝶网络

2 网络编码的优缺点

2.1 均衡网络负载，提高带宽利用率

传统的组播中，信息有可能过度集中在某些节点，或者造成某一链路的流量过大，使得网络链路的负载不均衡，利用网络编码技术，能够提高网络的负载均衡，平均的使用网络链路的容量，避免网络拥塞，在节点平均读书较大时，效果更加明显。图2（a）是一个单源三接收网络，每条链路的容量为2，图2（b）中表示的是利用基于多播树的路由多播，图中用到了5条链路，每条链路上的可行流为2，消耗总带宽为5*2=10，在图2（c）中采用网络编码进行多播，为了平均链路流量的使用，尽量使用了网络中的可能链路，本例中一共9条传输链路，相比传统多播技术多使用了4条链路，每条链路的可行流为1，消耗的总带宽为9*1=9，相比于传统的多播方法，节省了10%的带宽消耗，每条链路的平均流量下降到1，链路的使用更加合理，均衡了网络负载，提高了带宽利用率。

图2 单源三接收网络

2.2 增强网络安全

利用网络编码进行数据传输在一定程度上可以提高数据的安全性，在传统的网络传输中，数据有可能被窃听，受到被动攻击，例如在图3（a）表示的结构中，窃听者可以窃听网络中的任意一条信道，获取传输内容。图3（b）中我们利用网络编码方式进行组播，信源不再直接发送a和b而是发送a+b和a+2b对消息进行混合，在单独的每一条路径上都不会出现原始的信源消息a或者b，此时窃听者在窃听网络中的任一信道（假设窃听者只能窃听一个信道）获得的传输数据是难以破一出信源消息a和b的，信宿只有在接收到足够多的消息后，从中译出信源消息。而且在网络编码技术中可以引入数据加密技术，对部分消息数据进行加密，并且将加密后的消息数据和未加密的消息数据充分混合，此时只要窃听者窃听的信道数量小于信源消息的总数，窃听者就很难破译出信源消息，信宿接收到足够的消息数据时，同时得到加密的消息数据和未加密的消息数据，可以直接译出未加密的信源消息，并且可以译出加密的信源消息，利用解密算法对其解密，得到信源要传递的全部消息。通过数据编码的方法在没有增加网络容量的情况下提高了数据传输的安全性。图3（c）中采用这种技术，将信源要传递的消息b经过数据加密技术转换层密文k，此时窃听者在单一信道上不能窃听到信源消息a，只能窃听到消息k，但是无法破解密文k，在信宿节点通过足够多的消息可以译出消息a和k，再采用解密技术将k解密成明文b，这种方法提高了网络的安全性，而且没有网络链路的开销，但是这种技术增加了加密和解密的计算量，在实际的使用过程，对消息全部加密成本太高，所以可以选择对发送的消息进行部分加密，附加在发送的消息后面，减少加密和解密运算的成本。

图3 线性网络编码

2.3 减少无线网络的能量消耗，提高数据安全

在无线网络中通过对传输的信息进行编码，将信息叠加之后进行传输，这样传输单位信息所需要的发射功率就会减少，无线网络的能量消耗会下降。无线网络很多节点都是依靠电池供电，功率的降低能够延长无线设备的续航时间。无线网络中还可以采用网络编码的方法增强网络的安全性，在无线网络中数据的传输容易被窃听和攻击，在安全级别要求较高时我们可以结合密码学对数据进行加密处理再进行传输。数据加密技术计算复杂度较大，带来的数据冗余也较多，从而影响数据的传输效率，并且数据在解码的时候对接收节点的计算能力和存储能力也有较高的要求，整个的传输成本比较高，不适合普通信息和数据的传输中使用。

网络编码能够在一定程度上提高无线网络传输的安全性能。相比于传统传输方法，在引入了数据编码技术之后，无线网络中传输的是叠加之后的数据而不是原始数据，数据的防窃听能力加强了。即使有人试图从采用了网络编码技术的网络中窃听数据，只要监听者没有窃听到足够多的数据或者没有足够强大的运算能力，就不能译出信源传输的原始信息，虽然安全的级别不能够达到利用数据加密或者哈希函数的方法运算的等级，但是低安全级别的数据传输中还是有很广的应用前景。

3 目前存在的问题

进行网络编码需要网络中的节点，需要具有运算和编码的能力，传统的节点设备可能不具备这些功能，而且网络编码涉及到大量的编码运算，而且运算复杂度和编码规则相关，在增加通信能力的同时也增加了网络中节点计算的复杂性，在某些情况下还需要在编码前进行信号的转换，这些都可能造成网络编码对网络带来更高的计算成本，也提高网络节点的制造成本，而且目前主要针对单信源多信宿的网络情况进行网络编码研究，对于实际的网络组播情况中多信源的多源网络进行网络编码还是具有相当的难度。如果传输的信息进行了编码，信宿节点接收到的某些信息并不能直接解码，只有在接收到足够的信源发出的信息后，才能够解码得到源信息，对网络传输的同步提出了更高的要求。而且在有些网络中并不是所有具有多输入链路的节点都需要网络编码，如果对所有具有多条链路的节点都进行网络编码，同样会产生冗余，因为网络编码的主题是输出链路而不是节点。例如在图4中，由于节点v3的存在使得在不用给节点w进行网络编码的情况下也可以让信宿节点同时收到信源节点发送的信息a和b，所以在一些网络拓扑结构上保证组播速率达到最大理论值的前提下，只在必须的网络链路上使用网络编码技术，优化网络编码减少网络中的开销。

图4 不需要编码的网络

网络编码是网络通信研究中的重大突破，是下一代网络的关键技术，有着很好的应用前景。目前对于网络编码的研究和验证都基于理想化的模型，很多的网络编码技术需要在实际的网络环境中进行检验。而且随着网络拓扑结构的增大，网络编码的速度就会变慢，对于资源的消耗变大，一些研究中已经引入遗传算法对网络编码进行优化。网络编码和纠错码、数字签名技术之间的联系，非线性网络编码与安全网络构建之间的联系，这些都是以后网络编码研究新的方向。综上所述，网络编码技术在未来网络技术的发展中有着很重要的地位，网络编码技术会有更好的应用前景，对网络的组播传输效率、网络安全、数据纠错都会带来新的发展。

[1]AHLSWEDER,CAIN,LISY-R.etal Network information flow[J].IEEE Transactions on Information Theory,2000，（4）：1204-1206.

[2]黄佳庆.网络编码原理[M].北京：国防工业出版社，2012.