最大可解线性网络编码的计算复杂性与构造方法

摘要

网络编码是一个的新研究领域,主要是为了充分利用网络容量来改善传输速率。传统的网络传输方式只允许中间节点(如路由器)转发收到的消息,而网络编码则允许中间节点对收到的信息编码后再发送,接受节点收到足够的信息后,解码出源点发出的初始信息。这样,路由方式即可以看作是网络编码传输方式的一种特例。
　　在一个通信网络中,对于任意非源节点,其接收信息的最大速率不能超过其最大流,这是一个理论上界。对于单源多播网络,所有收点的最大流的最小值即是这些接收节点同时可以收到的信息的最大速率,并且线性网络编码对于达到这个网络极限速率是充分的。
　　然而,一般构造的线性多播网络编码,由于源节点只能以所有接收节点的最大流的最小值作为发送速率,对于有较大的最大流的网络接收节点则没有充分利用它们的容量。本文就是在一般的线性多播网络编码基础上,定义了一种新的网络编码,此网络编码保证各接收节点接收信息的速率等于其各自的最大流,并可以解析出原始信息,此即最大可解线性网络编码。
　　本文主要研究了最大可解线性网络编码的计算复杂性与构造方法。对信息流问题进行了复杂性分类,同时从编码的代数表示上论证了对于一个特定的网络,判定是否存在一个最大可解线性多播网络编码是个NP难问题。并且,在线性多播网络编码的多项式构造算法基础上,给出了基于边的重要性排序的启发式近似构造算法。