与经典信道相关的网络编码

基金项目：国家自然科学基金项目资助(60832001)；国家重点基础研究发展规划项目(2007CB310900)

    传统的通信网络传送数据的方式是存储转发，即除了数据的发送节点和接收节点以外的节点只负责路由，而不对数据内容做任何处理，中间节点扮演着转发器的角色。长期以来，人们普遍认为在中间节点上对传输的数据进行加工不会有任何收益，然而R Ahlswede等人[1]于2000年提出的网络编码理论彻底推翻了这种传统观点。

    网络编码是一种融合了路由和编码的信息交换技术，它的核心思想是在网络中的各个节点上对各条信道上收到的信息进行线性或者非线性的处理，然后转发给下游节点，中间节点扮演着编码器或信号处理器的角色。根据图论中的最大流-最小割定理[2]，数据的发送方和接收方通信的最大速率不能超过双方之间的最大流值(或最小割值)，如果采用传统多播路由的方法，一般不能达到该上界。R Ahlswede等人以蝴蝶网络的研究为例，指出通过网络编码，可以达到多播路由传输的最大流界，提高了信息的传输效率，从而奠定了网络编码在现代网络通信研究领域的重要地位。

    在网络编码研究中，如何保证信息在通信网络中可靠、安全地传输是一项重要课题。

    首先，信息的可靠传输是网络编码研究的主要目标，即接收方能够准确收到发送方传输的消息。但是，信息在网络信道上的传输一般会受到信道噪声的干扰。因此，如何将经典的信道编码理论扩展到网络环境中，并极大限度地控制接收方的译码差错概率就显得尤为重要。

    同时还需要考虑中间节点的编码效率，即如何合理设计网络-信道编码方案以提高传输效率。

    其次，信息传输的过程中可能遭到窃听，导致通信双方的隐私泄露。所以，在保障可靠传输的基础上，还需要考虑如何利用网络编码来保护消息传输的安全。

1 网络编码的基本原理和研究现状
    网络编码和传统的路由传输方式相比，在网络吞吐量、普适性、鲁棒性、可靠性和安全性等方面都有明显的优势。

1.1 网络编码的基本原理
    R Ahlswede等人利用单信源双信宿的蝴蝶网络为例，阐述了网络编码的基本原理，并说明通过网络编码在某些网络拓扑中能够获得比路由方式更高的传输效率。

    如图1所示，S 表示信源节点，Y和Z表示信宿节点，并且信源S同时发送两个二进制数据位b 1和b 2到信宿Y 和Z。
假设每条边(信道)的容量(这里的容量是从图论的角度定义的，而不是指信息论角度的信道容量)都为1，表示每单位时间只允许传输一个数据位，并且所有信道都是无噪声的。另外，允许两个节点之间有多条信道，表示两节点间在单位时间内可以传送多个数据位。

    对于图1(a)的情况，采用传统的路由方式就可以将b 1和b 2一次发送到Y和Z，因为中间节点W和X之间有两条独立的信道。
对于图1(b)的情况，虽然S到Y和Z的最大流值也分别为2，但是无法采用路由方式来达到该最大速率，因为W和X之间唯一的一条信道成为了传输瓶颈。

    图1(c)中采用了网络编码方案，在节点W 处对输入信息进行模2加操作，并输出b 1?茌b 2。当Y收到b 1和b 1?茌b 2后，通过计算b1(b1?茌b 2)就得到了b 2，同理Z也可以通过这种方式得到b 1。

    网络编码操作过程大致可概括如下：信源将消息通过输出信道发送，每个中间节点根据各条输入信道的信息进行编码，并将编码后的结果分别输出到各条输出信道上。最后信宿接收输入信息，进行译码，得到信源所发送的消息。网络编码是在有限域GF(q)上的操作，文献[3]指出：如果有限域GF(q)选取充分大，则通过网络编码可以达到的最大传输速率(熵率)为信源到各个信宿的相应最大流值中的最小值h =min{maxflow(t ): tT }，其中T 为信宿集合。

    网络编码在网络传输效率、普适性、鲁棒性、可靠性和安全性等方面都具有优势：

• 传输效率：从图1的蝴蝶网络的例子可以看出，网络编码可以提高网络吞吐量；
• 普适性：信源传输信息的最大速率只和信源到信宿的最大流值有关，在构造网络编码时不需要考虑信宿的具体位置。
• 鲁棒性：只要位于信宿的用户能够接收到足够的信息进行译码，即使网络中的某些节点或信道失效，仍然可以正常通信。
• 可靠性：即使网络中的数个信道发生错误，通过编码仍然可以纠正错误。
• 安全性：即使网络中的部分信道被窃听，通过适当的网络编码仍然可以保护数据安全。
• 应用于无线网络的优点：可以提高无线网络的带宽利用率，降低传输延迟，减少能量消耗。

1.2 从网络编码到网络-信道编码
    2000年，R Ahlswede、蔡宁、李硕彦和杨伟豪等人在IEEE Transactions on Information Theory上发表了论文Network Information Flow，证明了在单信源组播网络中，使用网络编码可以达到信息传输的最大流界，并通过蝴蝶网络的例子说明传统路由无法实现最高的传输效率。这篇文章是网络编码理论发展的开端。

    2003年，李硕彦、杨伟豪和蔡宁提出了线性网络编码理论，并证明了使用线性网络编码在单信源网络中可达最大流界。他们还提出了一种通过线性网络编码达到最大流界的线性算法，降低了中间节点编码的复杂度，为网络编码的实用创造了条件。
此后，R Koetter和M Medard将有限域上的多项式应用于网络编码的研究中[4]，并提出使用静态线性编码保证如何在部分网络失效的情况下仍能正常通信。目前，网络编码的研究热点主要分布在网络信息论和多信源网络编码、网络随机编码、网络卷积编码、网络纠错编码和网络安全编码等领域。

    网络编码和网络上的经典信道编码在什么条件下可以分离是简化编码设计复杂度的重要课题。2006年，文献[5]通过研究单信源多信宿网络，在假设所有信道都是统计独立的离散无记忆信道(DMC)的基础上，得到了网络编码和信道编码可以分离的结论。此后，文献[6]证明了当网络中的信道是确定型广播信道时，网络-信道分离定理不成立。

    除了网络传输效率之外，研究者也开始考虑如何利用网络编码实现安全通信。2002年，文献[7]提出了单信源窃听网络中网络安全编码的概念，并在2007年将工作推广到了多信源的情况[8]。

    目前，网络编码的研究领域已经触及到了网络信息论、多信源网络编码、网络随机编码、网络卷积编码、网络纠错编码以及网络安全编码等领域，其研究潜力十分巨大。

2 信道编码理论
    文献[9]开创性地提出了DMC信道和高斯信道的信道编码定理，其正定理部分说明如果码率不大于信道容量，则存在一种渐进达到该码率的编码方案(或称编译码方案)使得信息在信道中传输，并且最大译码差错概率可以任意小，见式(1)；其逆定理部分说明如果码率超过信道容量，则无论采用何种渐进达到该码率的编码方案，其最大译码差错概率总大于一个正常数。

    对于单用户信道情况，编码定理的一般形式为：如果信道的容量为C，则码率R是渐进可达的，当且仅当R≤C。所谓码率R 渐进可达是指对于任意的ε>0，存在充分大的n及一种(n, M )编码方案使得(1)式成立：

    其中λmax是信宿端最大差错译码概率，n是码字长度，M是码字个数。对于很多单用户信道容量的研究已较为透彻，这里不再赘述。

    对于多用户信道，其信道容量由一个区域来刻画，称为容量区域。假设用户的个数为m，第i 个用户(1≤i≤m )的码率用Ri表示，则只要(R1,R2……Rm )在区域边界的内部，则存在一种多用户信道编码方案可以渐进达到码率(R1,R2……Rm )，同时使得接收端最大译码差错概率任意小；反之，如果(R1,R2……Rm )在区域边界的外部，则无论采用何种编码方案，接收端最大译码差错概率都不能够任意小。

    目前，许多多用户信道的容量区域只能给出外界或者内界，结论还很不完善。多用户信道可以分为以下几种简单情况[10]：多元接入信道、广播信道、中继信道、干扰信道和多用户网络。

    多元接入信道是目前了解最多的信道，经典多元接入信道的容量区域已经被文献[11]和文献[12]分别确定。典型的离散无记忆二元接入信道如图2所示，两个独立信源分别向同一个信宿发送消息W1和W2，编码后分别得到长度为n 的码字X1和X2，信道的转移概率矩阵为p(y |x1,x2)，信道的输出为Y，译码后的输出为(W1,W2)。二元接入信道的容量区域为，对每个乘积分布p(x1,x2) = p(x1)p(x2)，满足式(2)的所有(R1,R2)的凸闭包：

    其中R1和R2分别可以被两个用户的码率达到。此后，文献[13]将多元接入信道的容量区域推广到了带有公共信息的多元接入信道的情况；文献[14]第一次证明了反馈可以增加离散无记忆多接入信道的容量；文献[15]确定了带反馈的两元高斯接入信道的容量区域；文献[16]发现了一类特殊的多元接入信道，该信道采用平均译码差错概率和最大译码差错概率得到的容量区域不同。

    除多元接入信道之外，广播信道也是研究最广泛的多用户信道之一。广播信道的概念最早是由T M Cover在1972年提出的。一般广播信道的容量区域仍然没有得到，但是降阶的广播信道容量区域已经被文献[17]和文献[18]确定。确定型广播信道的容量是由S I Gelfand和M S Pinsker[19-21]以及K Marton[22]发现的。
中继信道最早是由V Meulen提出的[23]，T M Cover等人研究了退化中继信道的容量区域[24]。对于干扰信道，A B Carleial在文献[25]中介绍了具有功率约束的高斯干扰信道并指出了非常强的干扰和总体无干扰的研究手法是类似的。Han等给出了目前一般干扰信道最好的可达速率区域[26]。目前为止，关于多用户信道的研究还没有统一的理论。

    另外，蔡宁和K Y Lam在2000年提出了广播信道的保密隐私编码[27]，使得合法用户可以正确译码，并且非法用户得不到有关信源的任何信息。

3 网络编码与信道编码的分离问题
    经典的分离问题是指信源-信道编码分离问题，其核心在于信源-信道编码联合设计是否能提高分离设计中的可靠传输效率。如果采用信源-信道联合编码不能提高传输效率，则可以采用独立的信源编码器和信道编码器。这种方法的优势在于可以简化编码系统设计的复杂度，具有很强的实用价值。但是，分离定理并不总是成立的。文献[10]中指出在某些多用户信道中，采用联合编码比采用分离编码能够获得更高的可靠传输效率。类似地，在网络编码的概念提出后，一些研究者也开始考虑在有噪声的网络环境下，网络编码和信道编码是否可以分离的问题。

    李硕彦、杨伟豪和蔡宁证明了当单源多汇有向网络中的所有信道是DMC的并且信道噪声都统计独立时，网络-信道编码分离定理是成立的，而且成立条件不依赖于网络是否有环，并且信源允许有输入边，信宿也可以有输出边。

3.1 网络编码顺序问题
    在网络编码中，节点之间(或边上)的编码顺序是非常重要的。在编码过程中，需要保证在进行编码之前收到了所有输入边的信息，否则就会失败。对于有向无环图，根据图论中拓扑排序的方法就能确定节点之间(或边上)的编码顺序，保证序号小的节点总是比序号大的节点先完成输出边上的编码。但是对于有向有环图，问题就有些复杂。这时必须考虑边上的延迟，以区分不同时刻的消息。文献[5]中指出，如果有向图中有环，则只要在环路的任意边上，加上一个单位时间的延迟就可以解决不同时刻消息的区分问题。文献[5]提出了网络流图的概念，通过将有向有环图按照传输时刻分层的方法，准确刻画了网络信息流的传输过程。

3.2 关于可达的描述
    网络流图解决了有向图G中的网络编码次序问题后，文献[5]为每条边确定了网络编码函数，对信宿确定了网络译码函数，并且定义了译码差错概率Pe(n )为：

    其中Wt表示信宿t译码后的消息，W表示信源发送的消息，T 表示网络中所有信宿的集合，n是码字长度。在网络流图中考虑的网络编码方案都是不变延迟时间的。

    在此基础上，文献[5]进一步定义了可达的概念：设(G,C )是一个由单信源s和信宿集合T构成的网络，其中G为有向图，C为以G中每条边上经典信道容量为分量的向量。设ω为信源s的熵率，则是可达的定义为：存在一种不变延迟时间的n长分组网络—信道联合编码方案，使得各边达到经典信道容量，同时信源s可以向信宿集合T 以熵率ω传输消息，并且当n充分大时Pe(n )→0。

3.3 网络编码与信道编码的分离定理
    在上述模型中，文献[5]中对单信源单信宿的情况指出：(G,C,ω)是可达的当且仅当信源熵率ω不超过信源和信宿之间的最大流值。这个最大流值就是信源到信宿之间最小割中所有边的信道容量之和。具体来说，对G ?劬(V,E )的任意一个割(V1,V2)?劬{(i,j )∈E :i∈V1且j∈V2}，均有

    其中K =|(V1,V2)|，Ci表示割(V1,V2)中的第i 条边的信道容量。最后，文献[5]的结论从单信源单信宿的情况推广到单信源多信宿的情况，并且说明上述结论与无噪情形下的结论是相同的，这就暗示了网络-信道编码分离定理。

    值得注意的是，该分离定理是建立在网络中各信道噪声是统计独立的基础之上的。一般情况下，网络-信道编码分离定理不一定成立。例如，N Ratakar和G Kramer证明了当网络中的信道是确定型广播信道时，分离定理不成立[6]。至今，分离定理何时成立的条件尚无定论，有待进一步的研究发现。

4 信道安全编码与网络安全编码
    网络中的通信安全也是网络编码研究的重要课题之一，分为经典信道(以广播信道为例)安全问题与网络编码安全问题两部分论述，希望进一步的研究能够将两者结合考虑。

    对广播信道的研究延伸到安全领域是在1975年A D Wyner提出的窃听信道中，窃听信道也是一种降阶的广播信道。A D Wyner在文献[28]中确定了含疑惑度的窃听信道的容量区域。这一研究又被I Csiszar等人加以推广研究[29]。

    除了窃听信道之外，广播信道的另一种应用场景是不同的用户只能接收信源发给他们各自的消息，而不能知道发给别人的消息。例如，银行用户只能知道其个人帐户的信息，而不能获悉别人帐户上的余额。N Cai和K Y Lam首先提出了广播信道的保密隐私编码，并且得到了确定型广播信道的容量区域[27][0]。这种广播信道的扩展模型由蔡宁和K Y Lam在2000年提出，如图3所示。信源分别发送消息M1和M2，经过编码后得到码字X，再经过不同的噪声信道达到两个用户，两用户分别将收到的消息译码为M1和M2，并且满足(5)式的条件：

    其中n是码字X 的长度。这种通信模型的信道容量区域称为广播信道的保密隐私容量区域。虽然确定型广播信道的保密隐私编码容量区域已经在文献[27]中确定，但是对于一般广播信道甚至其他多用户信道的情况尚无定论。关于保密隐私编码未来的研究方向包括：

• 确定一般广播信道的保密隐私容量区域或内外界；
• 找到其他多用户信道的保密隐私编码容量区域或内外界。
  

    另外，蔡宁和杨伟豪研究了反窃听网络安全编码的概念，提出了窃听网络上的通信系统模型，并且为单信源网络构造了安全的网络编码方案。在这种通信模型中，每个攻击者可任意选取固定数量的信道作为窃听目标，并得到这些信道上传输的全部数据，但系统不能让他得到有关信源消息的任何信息。值得一提的是，该模型包含了Shannon密码系统和秘密共享体制两个著名的安全系统。其后，蔡宁和杨伟豪又将该工作推广到多信源网络，发现了一般窃听网络上通信系统安全编码的充要条件，为这类网络编码从理论走向应用奠定了基础。S Y E Rouayheb和E Soljanin将第二类窃听信道编码应用到了网络编码中，得到了一种新的网络安全编码方案，并利用文献[30]发现的关系证明了该方法等价于文献[7]的安全网络编码。

5 结束语
    网络编码较传统的路由通信技术有较大的优势，近年来已经成为信息论方向研究的热点。网络-信道编码能够保证通信双方在网络噪声信道中高效可靠收发消息，也是网络编码领域的主要研究方向之一。目前，网络-信道编码的研究方向主要包括多用户信道理论和网络-信道编码定理，其中许多问题尚未得到解决。

    感谢在本文成文过程中西安电子科技大学蔡宁教授提供宝贵的参考资料。

6 参考文献
[1] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.
[2] CHARTRAND G, ZHANG P. 图论导引[M]. 范益政，汪毅，龚世才，等译. 北京：人民邮电出版社, 2006.
[3] LI S Y R, YEUNG R W, CAI N. Linear network coding [J]. IEEE Transactions on Information Theory, 2003, 49(2): 371-381.
[4] KOETTER R, MEDARD M. An algebraic approach to network coding [J]. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795.
[5] SONG L, YEUNG R W, CAI N. A separation theorem for single-source network coding [J].IEEE Transactions on Information Theory, 2006, 52 (5): 1861-1871.
[6] RATNAKAR N, KRAMER G. The multicast capacity of deterministic relay networks with no interference [J]. IEEE/ACM Transactions on Networking, 2006, 52(6): 2425-2432.
[7] CAI N, YEUNG R W. Secure network coding [C]//Proceedings of 2002 IEEE International Symposium on Information Theory (ISIT 2002), Jun 30-Jul 5, 2002, Lausanne, Switzerland. Los Alamitis, CA, USA: IEEE Computer Society, 2002: 323.
[8] CAI N, YEUNG R W. A security condition for multi-source linear network coding [C] //Proceedings of 2007 IEEE International Symposium on Information Theory (ISIT 2007), Jul 24-29, 2007, Nice, France. Los Alamitis, CA, USA: IEEE Computer Society, 2007: 561-565.
[9] SHANNON C E. A Mathematical theory of communication: Part 1 [J]. Bell Systems Technical Journal, 1948, 27(4): 623-656.      
[10] SLEPIAN D, WOLF J K. A coding theorem for multiple access channels with correlated sources[J]. Bell Systems Technical Journal, 1973, 52 (7): 1037-1076.
[11] AHLSWEDE R. Multi-way communication channels[C] //Proceedings of 2nd International Symposium on Information Theory (ISIT'71), Sep, 1971, Thakadsor, Armenian SSR. Budapest, Hungary: Hungarian Academy of Sciences, 1971: 23-52.
[12] LIAO H. Multiple access channels [D]. Honolulu, HI, USA: Department of Electrical Engineering, University of Hawaii, 1972.
[13] COVER T W, THOMAS J A. Element of information theory[M].2nd ed. New York, NY, USA: Wiley, 2006.
[14] GAARDER T, WOLF J K. The capacity region of a multiple-access discrete memoryless channel can increase with feedback [J]. IEEE Transactions on Information Theory, 1975, 21(1): 100-102.
[15] OZAROW L H. The capacity of the white Gaussian multiple access channel with feedback [J]. IEEE Transactions on Information Theory, 1984, 30(4):623-629.
[16] DUECK G. Maximal error capacity regions are smaller than average error capacity regions for multi-user channels[J]. Problems of Control and Information, 1978, 7(1): 11-19.
[17] BERGMANS P. Random coding theorem for broadcast channels with degraded components [J].IEEE Transactions on Information Theory, 1973, 19(2):197-207.
[18] GALLAGER G R. Capacity and coding for degraded broadcast channels [J]. Problemy Peredaci Informaccii (USSR), 1974, 10(3):3-14.
[19] WYNER A D. The wiretap channels [J]. Bell Systems Technical Journal, 1975, 54 (8): 1355-1387.
[20] GELFAND S I, PINSKER M S. Capacity of a
broadcast channel with one deterministic component [J]. Problemy Peredaci Informaccii (USSR), 1980, 6(1):24-34.
[21] PINSKER M S. The capacity region of noiseless broadcast channels [J]. Problems of Information Transmission (USSR), 1978, 14 (2):97-102.
[22] MARTON K. A coding theorem for the discrete memoryless broadcast channel [J]. IEEE Transactions on Information Theory, 1979, 25 (3):306-311.
[23] VAN DER MEULEN E C. A survey of multi-way channels in information theory [J]. IEEE Transactions on Information Theory, 1977, 23 (1):1-37.
[24] COVER T M, EL GAMAL A. Capacity theorems for the relay channel [J]. IEEE Transactions on Information Theory, 1979, 25(5):572-584.
[25] CARLEIAL A B. A case where interference does not reduce capacity [J]. IEEE Transactions on Information Theory, 1975, 21(5):569-570.
[26] HAN T S, KOBAYASHI K. A new achievable rate region for the interference channel [J]. IEEE Transactions on Information Theory, 1981, 27(1):49-60.
[27] CAI N, LAM K Y. How to broadcast privacy: Secret coding for deterministic broadcast channels[C] // ALTHOFER I, CAI N, DUECK G, et al. Numbers, Information and Complexity (Festschrift for Rudolf Ahlswede). Kluwer Netherland: Academic Publishers, 2000: 353-368.
[28] GELFAND S I. Capacity of one broadcast channel [J]. Problemy Peredaci Informaccii (USSR), 1977, 13(3):106-108.
[29] CSISZAR I, KORNER J. Broadcast channels with confidential messages [J]. IEEE Transactions on Information Theory, 1978, 24(3):339-348.
[30] FELDMAN J, MALKIN T, STEIN C, et al. On the capacity of secure network coding [C]// Proceedings of 42nd Annual Allerton Conference on Communication, Control, and Computing, Sep 29-Oct 1, 2004, Monticello, IL, USA.

收稿日期：2008-11-07

[摘要] 传统的网络信息流传输方式是存储转发，但通常无法达到通信的最大流界。为了实现更高的传输效率，Ahlswede等人提出采用网络编码的方法，不但可以提高网络吞吐量，而且在普适性、鲁棒性、可靠性和安全性等方面都具有优势。网络中的信道通常是有噪声的，目前网络编码理论的研究重点包括经典多用户信道、网络-信道编码分离和网络安全编码等问题。

[关键词] 网络编码；多用户信道；分离定理；保密隐私编码容量

[Abstract] The traditional networks transmit information in a store-and-forward manner. Unfortunately, the coding rate cannot achieve the max-flow bound. In order to improve the reliable transmission efficiency, Ahlswede et al. introduced the network coding theory. Network coding can not only increase network throughput, but also advance in data universalness, robustness, reliability and security. Generally, the channels in a network are interfered by noises. Therefore, the most important research areas in the network coding theory include multiple user channel, separation theorem for network coding and privacy capacity region.

[Keywords] network coding; multiple user channel; separation theorem; private capacity region