曹张华，吉晓东，刘 敏

(南通大学电子信息学院，南通 226019)

0 引言

网络编码这一思想由Yeung等在文献［1］中首先应用于对卫星通信系统的研究，随后Ahlshede等在文献［2］中明确提出了网络编码这一概念，并证明了使用网络编码可以有效提高网络容量利用率。文献［3－4］给出了构造适用于组播网络的线性网络编码，接着Ho等在文献［5］中研究了随机线性网络编码这一实用的数据传输技术。文献［1－5］讨论了网络编码和线性网络编码，但他们研究网络编码时均假定网络的信息率固定，然而在实际应用中，信源在不同的时刻需要给不同的节点发送不同数量的消息分组，这就是变信息率网络通信问题，该问题可视为文献［6］中变信息率信道问题的网络化。

Jaggi等在文献［7］中提出的解决变信息率网络通信问题的方法是为每一个信息率建立一线性网络编码，然后将相应的局部网络编码核存储起来，显然，这会耗费网络中继节点的大量存储资源。Fong和Yeung在文献［8－9］中用降维法构造的线性网络编码能实现变信息率网络的有效通信，但对每一信息率，都需要根据最高维线性网络编码进行迭代计算，才能获得一合适的低维线性网络编码。Goseling等在文献［10］中研究了变信息率网络的网络编码构造和网络费用之间的平衡问题。文献［11］从跨层设计的角度研究了变信息率网络编码的实现问题。文献［12－13］研究了无线变信息率网络中的网络编码，通过在网络中继节点寻找更多的网络编码机会，自适应地调整网络编码策略，来实现高效的变信息率通信。Mar等在文献［14］中将中继协作和网络编码相结合，提高了变信息率网络的通信效率。但文献［11－14］只使用仿真结果验证了所提出方法的有效性，没有给出显式解。文献［15］对网络编码在数据传输中的积极作用进行了综述。针对已有的变信息率网络编码方法的缺点，该文构造了一种新的、能在变信息率网络中实现有效通信的线性网络编码。该方法无需为适应不同的信息率而频繁地重新计算出新网络编码。

1 基本概念

通信网络用有向、无圈图G=(V，E)表示。其中，V是节点集，E是信道集，显然E⊆V×V。网络G=(V，E)中的信道用有向边 e=(u，v)表示，且设每一信道的容量均为单位容量。对有向边e=(u，v)，节点u称为e的尾节点，v称为e的头节点，分别记为u=t(e)和v=h(e)。对任意节点v∈V，其入边集和出边集分别记为

通信网络G=(V，E)中的信源节点s到任一非源节点v的最大流记为maxflow(s，v)，信源s发送的消息用有限域Fq上的等长的数据组表示，设信源s发送的消息数据组为(Fq)N中的向量x1，x2，…，xn。在通信网络G=(V，E)中使用线性网络编码这一数据传输技术时，网络中任一节点v∈V的任一输出边所传输的数据组是输入边所传输的数据组的线性组合。即对任意的信道e∈E，记其传输的数据组为向量fe称为e的全局网络编码核，e∈ΓI(s)时，称fe为虚拟全局网络编码核。

定义1 有向无圈图G=(V，E)表示一单信源通信网络，Fq为一有限域，设信源s发出的消息数据组为 x1，x2，…，xn∈，使用线性网络编码进行数据传输时，对任意的 el∈ΓO(s)，有对非源节点v∈V及任意的边ej∈ΓO(v)，有

(4)式和(5)式中，αi，el，βei，ej称为局部网络编码核。

对任意的非源节点v，其局部网络编码核构成|ΓI(v)|× |ΓO(v)|的矩阵 Kv;对源节点 s，其局部网络编码核构成n×|ΓO(s)|的矩阵Ks。显然全局网络编码核由局部网络编码核决定。此处的定义综合了文献［3－4］中的基本概念。

2 变信息率网线性络编码的构造

有向无圈图G=(V，E)表示单信源通信网络，且信源s在不同时刻发送的消息数不一样。记信源s的M个不同的信息率为正整数r1＞r2＞…＞rM，为讨论的方便起见，设

对信息率 ri和非信源节点 v，若有 ri≤maxflow(s，v)，则要求非源节点v能够恢复出ri个信源消息，这样的网络称为变信息率线性广播网络。若有线性网络编码在变信息率线性广播网络中实现上述目标，则称该网络编码能实现变信息率线性广播网络的有效通信。

2.1 基本思想

实现单信源、多信息率网络G=(V，E)有效通信的基本思路如下。首先建立变信息率通信网络G=(V，E)中Fq上的r1维线性网络编码，该线性网络编码能使得满足条件maxflow(s，u)≥r1的节点u恢复出信源发送的消息。对其他的非源节点v，当信息率 r≤maxflow(s，v)，且 r＜r1时，记信源发送的消息分组为 x1，…，xr∈(Fq)N，而 xr+1，…，xr1为(Fq)N中的零向量。这样，对于信息率r，仍设信源s发送的消息数据组构成的消息向量为x=(x1，…，xr，xr+1，…，xr1)，只是其中的 xr+1，…，xr1为零向量。仍使用上面给出线性网络编码，不改变通信网络中的各节点的局部网络编码核，只是要求ΓI(v)中存在r条信道ei1，…，eir，这r条信道所对应的全局网络编码核fei1，…，feir的前r个分量构成的短向量组f'ei1，…，f'eir是线性无关的。下面举一个例子来说明上述想法。

例1 单信源通信网络G=(V，E)如图1所示，信道的容量为单位容量，信源到非源节点的信息率分别为1，2，3。当信息率为3时，充当字母表的有限域为F5，设信源发送的消息为(F5)N中的向量x1，x2，x3，记信源消息分组构成的向量为 x=(x1，x2，x3)。

图1 信息率为1，2，3的网络Fig.1 Network G=(V，E)with rates 1，2 and 3

由定义1，通信网络中各信道传输的数据组为

系数 αi，el和 βei，ej为通信网络的局部网络编码核。对图1中的通信网络进行如下的网络编码，局部网络编码核为

对于如图1所示的通信网络，信源s的信息率为1时，令x2=x3= 0;信源信息率为2时，令x3=0。使用如上的线性网络编码，对任一信息率，无需改变通信网络中的局部网络编码核，只需在解码过程中，将非源节点输入边的全局网络编码核中与零消息分组相对应的分量去除。显然，使用如上的方法可实现如图1所示的变信息率网络的有效通信。

2.2 传输矩阵

记单信源，变信息率通信网络为G=(V，E)，对网络中的信道进行编号时，要求任一中继节点v的入边集ΓI(v)中的信道编号小于ΓO(v)中的信道编号。

对于如图1所示的变信息率通信网络G=(V，E)，记信道集E所传输的数据组为

显然，K(I－F)－1是3×10矩阵，对于网络中的任一非源节点v。此时ΓI(v)中的边所对应的全局网络编码核与矩阵K(I－F)－1中的部分列向量相对应，将相应的列选出，构成一局部传输矩阵。当信源的信息率r≤maxflow(s，v)，只需局部传输矩阵前r行构成的子矩阵的秩为r。

对一般的单信源，变信息率通信网络G=(V，E)，如前面所述，信源s的最大信息率为r1，其发送的信源消息分组记为 x1，x2，…，xr1∈FNq，则矩阵 K中的单项Kil定义为

(24)式中，Kil的下标i对应信源消息xi，这样得到的矩阵K是r1×|E|的。

而矩阵F中的单项Fij定义为由此得到|E|×|E|矩阵F。对有向无圈通信网络G=(V，E)中的信道编号，任一节点v的输出边的编号大于输入边的编号。因此，矩阵F是一主对角线元素全为0的上三角矩阵，从而可得det(I－F)=1，即矩阵I－F是|E|×|E|的可逆矩阵。

与例1相似，任一单信源通信网络G=(V，E)都对应了一矩阵K(I－F)－1，该矩阵定义了信源输入消息与网络中各信道所传输的数据组之间的关系，称这样的矩阵为全局传输矩阵。事实上，对任一单信源，变信息率的通信网络G=(V，E)，结合定义1，有如下的结论成立。

2.3 变信息率线性网络编码的构造

对任一单信源，变信息率通信网络G=(V，E)，设其信息率为r1＞r2＞…＞rM，通信网络G=(V，E)的传输矩阵记为T=K(I－F)－1。对网络中的任意的节点v，其入边集ΓI(v)中的边所对应的全局网络编码核与全局传输矩阵T=K(I－F)－1中的部分列向量相对应。可得节点v∈V的局部传输矩阵为

易知，如图1所示的变信息率通信网络中的非源节点v1，...，v5，u的局部传输矩阵分别为

显然，使用(28)式所示的局部传输矩阵，信源发送一个消息数据组x1时，网络中所有非源节点均可获得x1;当信源发送2个消息分组x1，x2时，节点v2，v4，u 能获得 x1，x2;信源发送分组为 x1，x2，x3时，节点u能获得x1，x2，x3。由此，可得关于变信息率线性网络编码构造的一般性结论。

定理2 对于一个有向、单信源无圈变信息率网络G=(V，E)，可能的信息率为r1＞r2＞…＞rM。如上，任一非源节点v∈V{s}的局部传输矩阵为T(v)，信源s到节点 v的最大流为 maxflow(s，v)，记T(v)的前maxflow(s，v)行构成的矩阵为(v)。若对任意的非源节点v∈V{s}，有r1维线性网络编码使得

成立，则此网络编码能实现变信息率网络的有效通信。

每周二下午的社团课，岳舒恺老师都会带领社团的小“刀客”们走进篆刻的世界。从简单、有趣的肖形印（肖像某种物体形状的印章，只有图像，没有文字）开始，锻炼孩子们手上的刀功，刻出平稳均匀的直线；有趣的卡通形象和深厚的传统文化碰撞在一起，让孩子们产生了浓厚的兴趣。

定理2从局部传输矩阵出发，给出了实现变信息率网络有效通信的线性网络编码应满足的条件，而没有说明此线性网络编码是否存在，下面给出此类线性网络编码存在的条件。

定理3 对于一个有向、单信源无圈变信息率网络G=(V，E)，可能的信息率为r1＞r2＞…＞rM。充当字母表的有限域Fq满足条件|Fq|＞r1(|V|－1)时，则变信息率网络中一定存在满足定理2中式(29)的变信息率线性网络编码。

定理2和定理3给出了在变信息率网络中构造实现有效通信的线性网络编码的条件和方法。根据所得到的结论，下面给出一个寻找变信息率线性网络编码的简单算法。

3 链路故障网络中变信息率网络编码的构造

上文讨论了怎样在拓扑结构确定的变信息率广播网络中实现有效通信。但是，在现实的生活中，网络中的数据传输会发生拥塞，链路也会发生故障，从而导致链路无法正常工作。由此可知，网络中的链路状态是随时间而改变的。链路故障对网络通信的危害极大，既可导致网络无法通信，也可使得数据大量的丢失。因此，怎样在有链路故障的变信息率网络中实现有效通信是一个更加现实的问题。

对于链路会发生故障的变信息率线性广播网络G=(V，E)，定义信道集 E到{0，1}的映射 ε。对任意的信道e∈E，ε(e)=1表示信道e可以正常使用，而ε(e)=0表示信道e发生了故障。这样，映射ε对应了网络G=(V，E)的一个新的构造，记新得到的网络为Gε。相应的，对于任意的信道e，全局网络编码核记为。网络Gε中的信源s到各非源节点v的最大流记为 maxflowε(s，v)。

和上文中一样，在单信源无圈变信息率通信网络G=(V，E)中，信源s的M个互不相同的信息率记为r1＞r2＞…＞rM，且存在一非源节点v∈V{s}，使得maxflow(s，v)≥r1。下面，考虑怎样在有链路故障的网络中实现有效的通信。即要构造合适的线性网络编码，对于可能的构造ε和任意的非源节点v，若信源的信息率 ri≤maxflowε(s，v)，则要求节点 v能恢复信源发送的消息分组x1，…，xri。使用和上文相似的方法，可以构造有效的线性网络编码来实现有链路故障的变信息率网络的有效通信。此类线性网络编码应满足的条件如下。

注意到定理4和定理2的证明类似，实际上，定理2只是对任意的e∈E，有ε(e)=1的情形进行了证明。

与定理3类似，只要充当网络编码字母表的有限域Fq足够的大，此类线性网络编码存在，具体如下。

定理5 在有向单信源，有链路故障变信息率网络G=(V，E)中，可能的信息率为r1＞r2＞… ＞rM。网络的构造共有ω种，则充当网络编码字母表的有限域Fq的基数|Fq|＞ωr1(|V|－1)时，有链路故障的变信息率网络中一定存在满足式(31)的r1维线性网络编码。

在链路会发生故障的通信网络中，同样可以使用算法1获得变信息率线性网络编码，只是要求有限域Fq更大。同时，由定理4和定理5可知，使用此处给出的方法所构造出的变信息率线性网络编码可以有效应对网络中的链路故障，使得网络拥有良好的稳健性。

4 结束语

长久以来，变信息率网络的有效通信问题一直受到人们的关注，该文从全局角度研究了变信息率网络中的数据传输，构造了变信息率线性网络编码，并得到了全局传输矩阵和局部传输矩阵。然后使用代数学方法对全局传输矩阵和局部传输矩阵进行了分析，由此获得了实现变信息率网络有效通信的局部网络编码核和全局网络编码核应满足的条件。而且，该方法还适用于链路会发生故障的变信息率网络，结论表明，使用此方法构造出的线性网络编码能适应网络拓扑结构变化的变信息率网络，从而提高网络的稳健性。与已有的方法相比，该文提出的方法不要求网络节点存储多个信息率对应的局部网络编码核，也无需对不同信息率进行迭代计算来获得相应的网络编码。

［1］YEUNG RW，ZHANG Z.Distributed Source Coding for Satellite Communication［J］.IEEE Transaction on Infor mation Theory，1999，45(4):1111－1120.

［2］AHLSWEDE R，CAIN，LISY R.Network Information flow［J］.IEEE Transaction on Information Theory，2000，46(4):1204－1216.

［3］LISY R，CAIN.Linear Network Coding［J］.IEEE Transaction on Information Theory，2003，49(2):371－381.

［4］KOETTER R，MEDARD M.An Algebraic Approach to Network Coding［J］.IEEE/ACM Transaction on Networking，2003，11(5):782－795.

［5］HO T，MEDARD M，KOETTER R，et al.A Random Linear Network Coding Approach to Multicast［J］.IEEE Transaction on Information Theory，2006，52(10):4413－4430.

［6］HARSINI J，MICHELE Z.Effictive Capacity for Multi－Rate Relay Channels with delay Constraint Exploiting A－daptive Cooperativer Diversity［J］.IEEE Transaction on Wireless Communication，2012，11(9):3136－3147.

［7］JAGGIS，SANDERS P，CHOU P A.Polynomial Time Algorithms for Multicast Network Code Construction［J］.IEEE Transaction on Information Theory，2005，51(6):1973－1982.

［8］FONG S L，YEUNG RW.Variable－rate Linear Network Coding［C］//IEEE Information Theory workshop(IEEE ITW).USA:Conference Publications，2006:409－412.

［9］FONG S L，YEUNG RW.Variable－rate Linear Network Coding［J］.IEEE Transaction on Information Theory，2010，56(6):2618－2625.

［10］GOSELING J，WEBER J H.Multi－rate network coding for minimum－cost multicasting［C］//IEEE International Sy－mposium on Information Theory(ISIT).USA:Conference Publications，2008:36－40.

［11］LAKSHMINARAYANA S，ERYILMAZA.Multirate Multicasting with Intralayer Network Coding［J］.IEEE/ACM Transaction on Networking，2013，21(4)1256－1269.

［12］HUANG Meng，FENG Gang，ZHANG Yide.Network Coding with Relay Assistance in Multi－rate Wireless Networks［C］//IEEE 6th International ICST Conference on Cmmunications and Networking in China(CHINACOM).USA:Conference Publications，2011:1120－1125.

［13］WANG Fanzhao，WANG Shiqiang，SONG Qingyang.A－daptive Relaying Method Selection for Multi－Rate Wireless Networks with Network Coding［J］.IEEE Communications Letters，2012，16(12):2004－2007.

［14］MAR C H，KONG P Y.Cooperative MAC Relaying with Multi－Rate Transmissions and Network Coding［C］//IEEE Wireless Communication and Networking Conference(WCNC).USA:Conference Publications，2012:1602－1607.

［15］王练，雷芳.基于网络编码的无线重传方案综述［J］.重庆邮电大学学报:自然科学版，2012，24(5):664－668.

WANG Lian，LEI Fang.Survey of Network Code Retransmission in Wireless Network［J］. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2012，24(5):664－668.

(编辑:田海江)