网络编码作为一种新的技术在宽带无线自组织网络中有很好的应用，通过网络编码，中间节点可以将接收信息进行编码并发送出去，提高了网络吞吐量和健壮性。为不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在高层实现网络编码。无线传感器网络、无线格状网(Mesh)等无线自组织网络都可以使用网络编码技术显著提高多跳链路的传输性能。目前网络编码的研究热点集中在网络编码节点选取方案、网络编码算法的设计、网络编码复杂度分析、网络编码的性能分析、网络编码与系统安全性分析、网络编码在无线分布式网络中的应用等方面。
宽带无线多跳通信系统的设计目标是在充分利用有限的无线网络资源的前提下，使各接收节点能快速收到完整信息。如何提高多跳自组织无线网络的性能，一直是业界研究和关注的重点[1]。
|
1 网络编码技术原理
网络编码(Network coding)从广义上来讲，是网络中的节点将接收到的信息进行编码后再转发出去的多点传送(Multicast)技术。多点传送(也称组播)是网络中的一种重要的通信方式。当一个或几个节点同时向若干个其他节点发送数据时，往往要借助其他节点的传递。
在传统的网络中，作为中继的节点只能对接收到的信号进行复制、放大和转发，这对于网络资源有时候是一种浪费。网络编码技术打破了这种限制，它允许中继节点对接收到的信息进行编码，并将接收到的多个数据包按照某种特定算法重新组合再发送出去。
图1所示为一无线通信领域3节点拓扑的实例：节点A、节点B相互传递信息a、b。图1中的箭头代表有向链路，假设每条链路的容量为“1”。图1(a)采用传统的通信方式，A首先向S发送信息a，然后B向S发送信息b，S然后依次把信息a和b分别广播给节点A和节点B。这样经过4条链路的传输节点B可以获得信息a，而节点A可以获得信息b 。但是当信息a和b准备通过节点S进行转发时，如果应用网络编码技术，将a和b作模2和运算后直接转发出去，则在节点B处，根据接收到的信息可恢复出a来；同理，在节点A处也可以恢复出信息b来，从而可以译码得到信息b。采用了网络编码技术后(见图1(b))，只需要使用3条链路就可以实现传统方式的所有通信要求。
从实例可以看出，网络编码技术可以显著地提高多点传送的数据率。在一个网络中传递的信息，可以形象的称之为“流”。网络的最大流量即为从源点到收点的最大传输数据率。而广播的最大流量是指源点同时向所有收点发送同样数据时，每个收点能接收到的最大数据传输速率。理论上讲，最大流取决于网络的拓扑结构，即各节点的连接关系和带宽。利用图论中著名的最大流最小割定理可以得到给定网络中某个源点到收点的最大流[2]。
最大流最小割定理：任何带发点和收点的网络中都存在最大流和最小割，并且最大流的流值等于最小割的容量。
从图1还可以看出，一个容许的网络编码方案，必须使得收点能够从接收到的数据中恢复出原始信息，也就是说，根据接收到的数据，和已知的编码方案，可以唯一地解出原始的数据。如果把整个网络看作一个系统，源点发送的数据可以视为系统的输入，收点接收到的数据作为输出，中间每个编码节点的操作作为系统函数，则要求从源点到每个收点之间的信息传输矩阵满秩，才能够满足广播的要求。
数据在经过中间网络时，可能经过多次编码。一个节点如果自身不是源点，那么它发出的信息只能来源于收到的信息。因此无论怎样编码，它发出的信息量必然小于等于收到的信息量。从信息论的角度讲，数据在传输过程中每经过一个节点，其信息熵都是非增的。所以，为了保证最后传到收点处的信息熵不降低，就要求每一个中间节点在编码时，系统的传输矩阵不降秩，即无损编码。而该节点为了判断当前的编码方案是否会造成系统传输矩阵降秩，还要知道其他节点处的编码情况。这就需要整个网络的通力协作，这是迥异于传统网络的新概念。在传统的网络通信中，每个节点只知道自己和临近节点的状态，并致力于满足自身的最优化目标。但网络编码技术要求各个节点之间的合作，以保证整个通信系统的最优化。如何让各节点协同工作，并不降低编码效率和网络其他方面的性能，是网络编码算法设计的重大挑战之一。
