基于多播的线性网络编码

网络编码初步陆巍220080551摘要：网络编码是通信网络中信息处理和信息传输理论研究上的重大突玻，其核心思想是允许网络节点对传输信息进行编码处理。

运用网络编码能够提升网络吞吐量、均衡网络负载和提高网络带宽利用率等。

本文简单介绍网络编码的基本原理以及主要优缺点，归纳网络编码的主要实现算法和机制，并重点分析网络编码的在P2P网络中应用。

关键词：网络编码随机网络编码信息流多播1引言传统的多播传输很难使多播传输达到“最大流最小割”定理确定的最大理论传输容量。

这主要是因为现有通信网络中使用的路由机制认为网络中传输的信息是不能叠加的，只能进行存储和转发。

然而，香港中文大学R. Alshwede等在2000年的IEEE信息论会刊上发表的一篇论文，彻底推翻了这一结论。

该文首次提出了网络编码的概念并从理论上证明：如果允许网络信息按照合适的方式进行编码处理，则基于该方式的网络多播总能够实现理论上的最大传输容量。

网络节点对传输信息进行操作和处理的过程，就称为网络编码。

2网络编码的基本概念和优缺点2.1基本概念R. Alshwede等[1]以著名的“蝴蝶网络”（Butterfly Network）模型为例，阐述了网络编码的基本原理。

如图1所示的“单信源二信宿”蝴蝶网络，设各链路容量为1，S是信源节点，Y和Z是信宿节点，其余为中间节点，根据“最大流最小割”定理，该多播的最大理论传输容量为2，即理论上信宿Y和Z能够同时收到信源S发出的2个单位的信息，也就是说能同时收到b1和b2。

图1（a）表示的是传统的路由传输方式，节点W执行存储和转发操作，假定W转发信息b1，则链路WX、XY和XZ上传输的信息均为b1，虽然信宿Z收到b1和b2，但信宿Y却只能收到b1(同时收到一个多余的b1)，因此信宿Y和Z无法同时收到b1和b2，该多播不能实现最大传输容量。

图1(b)表示的是网络编码方法，节点W对输入的信息进行模二加操作，然后将操作结果b1+b2发送至输出链路WX，然后又通过链路XY和XZ，最终达到信宿Y和Z。

网络编码原理
网络编码是一种数据传输方式，通过在发送端对数据进行编码处理，再在接收端进行解码，从而达到提高数据传输效率和可靠性的目的。

网络编码的原理主要包括源编码和恢复编码。

源编码是指将数据进行编码处理的过程。

在源编码过程中，发送端将数据划分为一定大小的数据包，并对这些数据包进行编码。

常用的源编码方式包括重传编码和线性编码。

重传编码是将原始数据包进行冗余编码，即在发送端对每个数据包进行冗余复制，接收端在接收到一定数量的数据包后，可以通过解码这些数据包来恢复原始数据。

线性编码则是通过对一组数据包进行线性组合，生成新的编码包发送出去。

接收端在接收到一定数量的编码包后，可以通过解码这些编码包来恢复原始数据。

恢复编码是指在接收端对接收到的编码包进行解码恢复的过程。

在恢复编码过程中，接收端通过解码接收到的编码包，获得一组数据包。

常用的恢复编码方式包括高斯消元法和LDPC码。

高斯消元法是通过将解码问题转化为一个线性方程组求解问题，从而得到原始数据包。

LDPC码则是通过矩阵解码的方法，从
一组接收到的编码包中恢复原始数据。

网络编码的优势在于提高了数据传输的可靠性和效率。

通过编码冗余，网络编码可以抵抗数据包损坏和丢失的影响，从而提高了数据传输的可靠性。

同时，通过对数据包进行编码组合，网络编码可以将多个数据包一起传输，从而有效利用了网络带宽，提高了数据传输的效率。

总的来说，网络编码通过源编码和恢复编码的方式，对数据包进行编码处理，提高了数据传输的可靠性和效率。

在实际应用中，网络编码被广泛应用于各种数据传输场景，如无线传感器网络、多播通信等。

多级网络编码方案宋雪;周异辉;师军;吴振强【摘要】目前安全网络编码的研究有信息论安全和密码学安全两种方法。

信息论安全的编码方案中，中继节点编码主要是使用随机线性网络编码（RLNC）生成编码矩阵，但是此方法并不能保证生成的矩阵一定满秩，从而影响方案的解码率。

提出了一个多级网络编码（MLNC）方案，该方案通过在源端使用对角矩阵对消息进行编码，以降低编码复杂度；在中继节点，让入度大于等于2的节点作为编码节点，使用多级的网络编码使混淆效果更好，编码节点随机生成满秩的下三角矩阵和上三角矩阵，用它们的乘积作为编码矩阵，这样能保证编码矩阵满秩，接收节点可以成功解码。

Matlab仿真结果表明，MLNC编码矩阵达到k-安全概率优于RLNC 编码矩阵，并证明MLNC方案满足信息论安全。

%The current secure network coding has two methods.They are information-theoretic security and cryptography security. Among the encoding methods of information-theoretic security, the encoding scheme of the relay node uses the Random Linear Network Coding(RLNC)to generate the encoding matrix. But this method does not guarantee that the resulting matrix must be full rank and affects the decoding rate. This paper proposes a Multi-Level Network Coding(MLNC) scheme. The scheme uses the triangle matrix to encode source message. On the relay node, the node whose degree is greater than or equal to 2 is used as coding node, using multi-level network coding can make the message encode mix better. The encoding nodes generate the full rank lower triangular matrix and the full rank upper triangular matrix randomly. It uses their product as an encoding matrix.This scheme will ensure encoding matrix must be full rank. The receiving node can successfully decode the data. The result of the Matlab simulation shows that the probability of the coding matrix of MLNC satisfying k-secure can be better than RLNC. And the scheme of MLNC satisfies the theoretic security.【期刊名称】《计算机工程与应用》【年(卷),期】2015(000)018【总页数】5页(P94-98)【关键词】网络编码;对角矩阵;多级网络编码;k-安全【作者】宋雪;周异辉;师军;吴振强【作者单位】陕西师范大学计算机科学学院，西安 710062;陕西师范大学计算机科学学院，西安 710062;陕西师范大学计算机科学学院，西安 710062;陕西师范大学计算机科学学院，西安 710062【正文语种】中文【中图分类】TP3931 概述网络编码理论是2000 年由香港中文大学Rudolf Ahlswede[1]等基于网络信息流的概念首次提出的。

随机线性网络编码问题及其应用研究随机线性网络编码问题及其应用研究随机线性网络编码是一种用于网络通信中的编码技术，通过在发送端对数据进行编码，可以在接收端实现数据的高效恢复。

随机线性网络编码以其简单性和高效性在研究领域中引起了广泛的关注。

本文将从随机线性网络编码的定义、特点和优势，以及其在不同应用领域中的研究进展进行探讨。

一、随机线性网络编码的定义与特点随机线性网络编码是一种利用线性运算对数据进行编码的方法。

在发送端，将待传输的数据分成若干个数据包，然后将每个数据包进行线性组合，形成一个编码后的数据包。

在接收端，通过解码技术将这些编码后的数据包恢复为原始的数据包。

随机线性网络编码具有以下特点：1. 简单易实现：相比于传统的网络编码方法，随机线性网络编码的实现更加简单。

它不需要复杂的计算，只需要进行简单的线性运算即可，因此降低了实现的复杂度。

2. 高效可靠：随机线性网络编码能够实现数据包的高效传输和可靠恢复。

通过编码后的数据包，接收端可以利用线性方程进行解码，准确恢复原始数据包，从而提高传输效率和可靠性。

3. 抗干扰能力强：随机线性网络编码具有一定的抗干扰能力。

在网络传输过程中，数据包可能会遭受信道误差、丢包等干扰，而随机线性网络编码可以通过冗余信息提高数据包的抗干扰能力，减小传输错误的影响。

二、随机线性网络编码的优势随机线性网络编码相较于传统的网络编码方法具有以下优势：1. 高效性：随机线性网络编码能够利用冗余信息提高数据传输速率和网络吞吐量。

通过在发送端对数据进行编码，可以将多个数据包合并为一个编码后的数据包进行传输，从而减少了传输的时间。

2. 可扩展性：随机线性网络编码具有良好的可扩展性。

在网络中，随机线性网络编码可以应用于多个发送节点和接收节点之间的通信，可以实现多节点之间的数据传输。

3. 适应性：随机线性网络编码能够适应不同的网络环境和传输条件。

它可以灵活地根据网络的实际情况自动调整编码参数，提高编码适应性。

xx 大学本科毕业设计（论文）文献综述课题名称：基于网络编码的无线广播重传方案的研究学院（系）：学生姓名：指导教师：完成日期：一、课题国内外现状无线传输中的广播信道特性，使得网络编码在减少无线传输次数方面有很好的应用，近年来出现了很多相关的研究。

Wu等人提出了利用网络编码减少信息包互换传输次数的方法，Bin等人提出了网络编码寻找无线Mesh网最少传输次数路径的思想。

Katti等人构造了无线Mesh网络使用网络编码的体系结构COPE，并利用29个节点的实验平台证实能显著减少平均传输次数。

Chachulski等人则提出无线路由协议MORE，并证实该协议能有效减少信息包的平均发送次数。

同时，与传统的有线网络相比，无线网络拥有较高的比特出错率，重传效率问题显得更加重要。

目前的研究现状来看，国外在无线传输技术中引入网络编码的研究起步较早。

国外多所著名大学如麻省理工学院、普林斯顿大学、多伦多大学、瑞士EPFL学院等和多家IT公司的研究中心，包括微软研究酣、贝尔实验室、AT&T 的香农信息实验室等都在积极开展相关的研究。

目前国外在无线传输技术中引入网络编码的研究主要侧重在二个方面：改善无线传输吞吐量和能量利用效率、保证无线链路的可靠传输和安全性。

在无线传输吞吐量研究上，Ahlswede等人指出网络编码可以达到组播传输理论最大流速；Li等人Kotter等人先后证明线性网络编码、随机网络编码同样可以达到组播传输理论最大流速、并对网络编码的数学框架进行了阐述，为网络编码在无线组播传输吞吐量方面的研究提供了必要的理论条件。

在能量利用效率方面，Wu等人证明在无线网络组播时应用网络编码，可以将最小化每位数据能量消耗问题归结为线性问题。

KaRi等人证实了局部混合网络编码的传输，在TCP和UDP传输流的环境下均可以显著提高传输吞量；Wu等人接下来研究了基于局部混合网络编码互换传输的性能，证明了互换传输可以优化传输性能，这些研究均为局部混合网络编码传输提供了理论基础和条件。