线性网络编码导出扩展软件学报

-不同组播率下线性网络编码的导出与扩展*Supported by the National Natural Science Foundation of China under Grant Nos. 60673164, 60873265 (国家自然科学基金), Provincial Natural Science Foundation of Hunan under Grant No. 06JJ20031(*省自然科学基金). 作者简介：蒲保兴(1965-),男,*人,博士研究生,副教授,主要研究领域为网络编码,进化计算;杨路明(1947-),男,*人,博士生导师,教授,主要研究领域为数据库信息系统;王伟平(1969-),女, *人,博士,教授,研究方向为网络信息平安,网络编码.蒲保兴1,2+,路明1,王伟平11(中南大学 信息科学与工程学院,410083)2(学院 信息工程系, ,422001)Generation and E*tension of Linear Network Coding at Different Multicast RatePU Bao-*ing1,2+,YANG Lu-Ming1,WANG Wei-Ping11 (School of Information Science and Engineering, Central South University, Changsha 410083, China)2(Department of Information Engineering, Shaoyang College, Shaoyang 422001,Hunan, China+ Corresponding author: Phn: +86-0739-5432505, :pubook.Received 2021-10-11; Accepted 2021-00-00Abstract:Aiming at single-source multicast network,by studying the intrinsic mechanism of linear network coding, this paper proposes a concept of generation and e*tension between two coding schemes at different multicast rates. We find out that a coding scheme at lower multicast rate is a generation of one at higher multicast rate, and a coding scheme at higher multicast rate is an e*tension of one at lower multicast rate. Furthermore, we find out a determinate relationship between channels global encoding vectors under two generation-e*tension coding schemes. Besides, by bining with random linear network coding, several important properties are derived, which are helpful to implement linear network coding for single-source multicast network. Several related applications are enumerated, and simulation results validate the conclusions derived by theoretical analysis. Key words:single-source multicast network, random linear network coding, generation and e*tension of coding schemes at different multicast rate.摘要:针对单源组播网络,通过对线性网络编码方案(编码系数的组合)的在机理进展分析,提出了不同组播率下编码方案的导出与扩展的概念:低组播的编码方案可以由高组播率的编码方案导出,高组播率的编码方案可以由低组播率的编码方案扩展而成.研究了具有导出与扩展关系的两个编码方案下全局编码向量间的相互联系,结合随机线性网络编码,导出了几个重要的性质,这些性质有助于有效地运用线性网络编码技术实现单组播连接,具有一定的应用价值.列出了几个方面的应用,基于相关的应用给出了仿真实验,仿真结果验证了理论分析的结论.关键字:单源组播;随机线性网络编码;不同组播率下编码方案的导出与扩展中图法:TP911文献标识码: A网络编码1-4是一种新型的数据传输技术,能提高网络的吞吐率、鲁棒性和平安性.Ahlswede 等人1首次提出了网络编码的概念,并指出:通过网络中间节点的编码可以实现单源组播网络的最大流界,而传统的路由技术一般情况下不能到达这个极限.硕彦等人2提出了线性网络编码技术,并证明了线性网络编码技术可以充分实现这一功能.Koetter等人3给出了线性网络编码的代数框架.因线性网络编码具有简单的特点,从而得到了深入广泛地研究4,5,6,7,8.运用线性网络编码进展数据传输必须构造编码方案:确定源点的数据传输速率(组播率)和各信道的编码系数.已有文献主要针对同一组播率下的编码方案进展研究,而对不同的组播率下的编码方案之间的关系研究较少.在实际应用中,运用线性网络编码技术面临以下问题:1)有时需要以不同的组播率进展数据传输,如采用已有的方法,则针对不同的组播率要设计不同的编码方案,且编码节点需保存不同组播率下的编码系数,占用了大量的存贮空间;2)尽管有文献9,10,11基于网络编码提出了分布式构造编码方案或减少编码代价的方法,但均是针对*一可行的组播率(不超过组播容量)进展研究,且假定组播容量是的或者能运用网络的全局拓扑知识采用最大流算法求出组播容量,而在实际应用中,假设源点缺乏全局网络拓扑知识,获知网络的组播容量是一件困难的事情,从而选定一个可行的组播率也是困难的;3)文献12,13研究了动态网络拓扑环境下的线性网络编码问题,均假定组播容量是且不变的,事实上在数据传输过程中,因接收点的随机参加或离开,节点或链路的失效会造成网络拓扑随时间动态变化,从而导致了组播容量的变化,因此数据传输过程中需要动态地测试组播容量,以便动态地更改组播率.针对单源组播网络,通过对线性网络编码的在机理进展分析,提出了不同组播率下编码方案的导出与扩展的概念:一个组播率为h的编码方案能导出一个组播率为k(kh)的编码方案,而后者仅在源点输出信道的编码系数略有不同,而一个组播为k的编码方案通过扩展源点输出信道的编码系数便可以得到一个组播率为h的编码方案.运用线性代数的相关理论对互为导出与扩展的两个编码方案进展研究,我们发现信道的全局编码向量具有确定的关系.运用这一关系,结合随机线性网络编码方法,推导出了几个重要的性质,这些性质对于运用线性网络编码技术具有一定的实用价值,能够有效地解决上述问题:不同组播率下的编码方案可共享编码系数,而不需重新构造编码方案;可以在线测试组播容量,且能把测试组播容量嵌入到数据传输过程中,而不会中断数据传输;能在线构造确定的编码方案.对相关的应用进展了仿真实验,仿真结果验证了理论分析的结论.1.相关知识以下根据文献5来表达线性网络编码的相关定义.一个单源组播网络用有向无环多重图G=(V,E)表示,其中V为节点集,E为有向边集,TV代表宿点集,sV是源点,为讨论方便,限定链路的容量为整数,假设网络节点之间存在容量大于1的有向链路,把它分成多条有向边,有向边e=(u,v)E代表节点u至节点v的单位容量的有向信道,其中u称为e的始点,记为u=tail(e),v称为e的终点,记为v=head(e).记In(v)=dE:head(d)=v为v的输入信道集合, 记Out(u)=eE:tail(e)=u为u的输出信道集合.定义1:组播率和组播容量.单源组播网络的组播率是指源点的数据传输速率,记为h;组播容量记为C,等于源点与所有宿点之间的最小割值1.线性网络编码操作在有限域上(本文采用伽罗华域GF(2m)14,信息的编码操作对应于有限域上的字符运算,在单位时间,假设源点播出的信息字符为*1,*2,*h,每一字符均为m比特,属于GF(2m)上的字符.信道eE传输的信息记为y(e),也属于GF(2m)上的字符.定义2:局部编码向量.采用线性网络编码,每一节点的输出信道e传输的信息是该节点所有输入信道传输信息的线性组合,这个线性组合的系数构成该信道的局部编码向量,记为m(e),则有m(e)=md,e GF(2m):dIn(tail(e) (1)(2)定义3:全局编码向量和全局编码矩阵.假设采用线性网络编码以组播率h传输数据,每一信道e传输的信息均可以表示为源点播出信息*1,*2,*h的线性组合,这个线性组合的系数构成一个向量,记为g(e)=(ge,1,ge,2,ge,h),则有 (3) (4)对于任意节点vV,该节点所有输入信道的全局编码向量构成了一个|In(v)|行,h列的矩阵,称为该节点的全局编码矩阵,每一信道的全局编码向量构成矩阵的一个行向量(注:|.|为集合的元素个数或向量的分量个数,以下同).由式(3),宿点可以通过其全局编码矩阵和接收到的信息字符形成一个线性方程组,只有当该线性方程组的系数矩阵的秩等于h,宿点才能恢复出源点的信息.定义4:编码方案.单源组播网络以组播率h采用线性网络编码进展数据传输,各信道的局部编码向量的集合称为一个组播率为h的编码方案,在该编码方案下,假设所有宿点的全局编码矩阵的秩均为h,则称为一个可行编码方案.一个编码方案不一定是可行的,其最大组播率为H=|Out(s)|;假设编码方案是可行的,由文献2,其组播率不能超过组播容量C.文献8提出了随机线性网络编码方法,与集中式网络编码构造方法6相比,该方法不需要获知全局网络拓扑知识,它在数据传输过程中随机地产生编码系数,即所有编码节点为其输出信道随机生成局部编码向量,为了使宿点实现解码,每一编码节点不仅需要进展信息编码运算,同时需要计算输出信道的全局编码向量,且把全局编码向量与传输的信息以数据包形式沿输出信道传输至下游节点.根据文献5,假设组播率为h,则信道上传输的数据包的格式如图1所示.Fig.1 The structure of a data packet with random linear network coding图1 随机线性网络编码的数据包格式L称为数据块的长度,一般来说,所传输的信息量远远超过L,因而需要进展假设干批数据传输才能完成整个数据传输任务.2.线性网络编码方案的导出与扩展以下定义了不同组播率下线性网络编码的导出与扩展的概念.记一个组播率为h的编码方案为xh (编码方案是一个集合,集合的元素是各信道的局部编码向量;也可以把编码方案看成是由编码系数构成的集合,xh是一个集合变量).在编码方案xh下,对于信道eE,其局部编码向量记为m(e,xh),全局编码向量记为g(e, xh);节点v的全局编码矩阵记为M(v, xh).由定义(2)和定义(3),信道e的局部编码向量的维数为|In(tail(e)|,全局编码向量的维数为h.因组播率为h,源点相当于具有h条虚拟输入信道,它们把要传输的h个字符以及h维向量空间的h个单位向量分别注入至源点.则对于源点的输出信道,其局部编码向量的维数是h,且全局编码向量与局部编码向量相等.而其余信道的局部编码向量的维数与组播率h无关,即: (5)从式(5)可以看出,一个编码方案xh包含了组播率为k(1kh)的编码方案(在同一有限域下,以下同).定义5:编码方案的导出与扩展.对于一个组播率为 h的编码方案xh,称由式(6)确定的一个组播率为k(1kh)的编码方案zk是由xh导出的,并称xh是由zk扩展而成.zk=m(e, zk):eE且m(e, zk)满足式(7) (6) (7)式(7)的含义为:当e为源点s的输出信道时,在zk下局部编码向量由xh下的局部编码向量的前k个元素构成;对于其它信道,在zk下的局部编码向量与xh下的局部编码向量一样.例如,图2中的z2是由x3导出的.从定义5可知,对于一个组播率为k的编码方案,只要对源点输出信道的局部编码向量进展扩展,每一个局部编码向量添加h-k个元素,构成维数为h的向量,而对于其它信道,保持其局部编码向量不变,则形成了一个组播率为h的编码方案.因此,对于一个组播率为k(1kh)的编码方案,可以由*一个组播率为h的编码方案导出,反之,一个组播率为h的编码方案可以由*一个组播率为k的编码方案扩展而成.3.几个重要性质定理1:设两个组播率k和h,xh是组播率为h的*一个编码方案,zk是组播率为k且由xh导出的编码方案,则在两个编码方案下,对于任意信道eE,它的全局编码向量具有以下性质:g(e, zk)的k个分量与g(e, xh)的前k个分量对应一样,即假设g(e,xh )= (g1,g2,gk,gk+1,gh), 则g(e, zk)=(g1,g2,gk).证明:采用归纳法证明.1) 当eout(s)时,由上所述,有g(e, zk)=m(e, zk) ,g(e, xh)=m(e, xh)成立.根据定义5,结论成立.2)假设对于编码节点v(vs),假设dIn(v)时结论成立,即:g(d, xh)=(g(d, zk) g),其中g是一个含有h-k个分量的向量*这里把向量写成了矩阵形式,并利用了矩阵分块的概念,把一个h维的向量看成是一个1行h列的矩阵.例如:(1,2,3,4)=(1 2 3 4)=(1 2) (3 4).不妨记节点v的输入信道分别为d1,d2,d|In(v)|,并注意到定义3,节点的全局编码矩阵是由其输入信道的全局编码向量组成,则 (8)其中M是一个|In(v)|行,h-k列的矩阵.对于eOut(v),根据定义5,有m(e, zk)=m(e, xh).假定m(e, zk)=(m1,m2,m|In(v)|),再根据式(4),则 (9)(10)结合式(8),(9),(10),根据分块矩阵相乘的性质,得出:g(e,xh)=m(e,zk)(M(v,zk) M)=(g(e, zk) m(e,zk)M).从而对于节点v的输出信道,结论也成立.因单源组播网络是一个有向无环图,所有的节点存在一个偏序,按照这个偏序反复使用公式(4),可以把所有信道的全局编码向量求出.由归纳法原理,结论成立.图2给出了定理1的一个例如.在图2中,各链路的容量均为1,s为源点,r1和r2为宿点.x3是一个编码方案,而z2是由x3导出的编码方案.采用的有限域为GF(22),其极小多项式为*2+*+1.分别在两个编码方案下,采用式(4)计算信道的全局编码向量,所得结果如图2所示,显然满足定理1的结论.Fig. 2 An illustration for generation and e*tension of coding schemes图2 编码方案的导出与扩展示意图在编码方案xh下,对于节点vV,令N(v,xh,k)是由其全局编码矩阵M(v,xh)的前k列构成的一个矩阵,这里1kh.推论1:假设xh是组播率为h的一个编码方案,而zk是由xh导出且组播率为k的编码方案,则对于任一节点vT,在编码方案zk下的全局编码矩阵是由在编码方案xh下的全局编码矩阵的前k列组成,即:M(v, zk)= N(v, xh ,k)证明:由定理1和定义3,结论显然成立.推论2:假设xh是组播率为h的一个编码方案,而zk是由xh导出且组播率为k的编码方案,则zk是可行编码方案的充分必要条件是对于每一个宿点rT,有rank(N(r, xh, k) )=k,其中rank(.)表示矩阵的秩.证明:根据推论1,对于每一宿点rT,它在编码方案zk下的全局编码矩阵为N(r, xh ,k),再根据定义4,结论成立.性质1:假设xh是组播率为h的一个可行的编码方案,假设1kh,则由xh导出且组播率为k的编码方案zk一定是可行的.证明:因xh是可行的,从而任一宿点rT在xh下的全局编码矩阵的秩为h,注意到这个矩阵只有h列,且矩阵的行数不小于h,这个矩阵的h个列向量线性无关,则前k个列向量必定线性无关,从而由这个矩阵的前k列构成的矩阵其秩必为k,再由推论1,则任一宿点在编码方案zk下的全局编码矩阵的秩必为k,由推论2,结论成立.源点s能获知其输出信道数H=|Out(s)|,H为源点的最大发送速率,记Vs=s,则是别离源点s与所有宿点的一个割集,其割值为H,因C为组播容量,由定义1,以下式子成立.CH (11)在单源组播网络中,让ma*flow(s,r)为别离源点s与宿点r的最小割值.假设以组播率H采用线性网络编码方法组播数据至所有宿点,相当于随机产生了一个编码方案,不妨记其编码方案为xH.引理1:在编码方案xH下,则每一宿点rT的全局编码矩阵的秩不会超过ma*flow(s,r),即rank(M(r, xH)ma*flow(s,r) rT (12)证明:由最大流-最小割定理,对于宿点rT,存在一个别离源点s与宿点r的最小割,该割中有且只有ma*flow(s,r)条信道,这ma*flow(s,r)条信道携带的全局编码向量成了H维向量空间的一个子空间,该子空间的秩不超过ma*flow(s,r),由线性网络编码的特点2,宿点r的每一输入信道的全局编码向量一定可以表示成这个最小割中的信道所携带的全局编码向量的线性组合,由代数知识,宿点r的全局编码矩阵的秩不能超过ma*flow(s,r),从而不等式(12)成立. 对不等式(12)两边取最小值,再由定义1,则 (13)文献5,8指出:在单源组播网络中以组播率C采用随机线性网络编码方法组播数据,且采用的有限域的阶为q(q|T|,|T|为宿点个数),则所有宿点全局编码矩阵的秩均为C的概率大于0,当有限域的阶足够大时,这个概率接近于1,不妨记这个概率为Pq.注意到当所有宿点的全局编码矩阵的秩为C时,则对应一个组播率为C的可行编码方案,由于随机线性网络编码产生编码系数的均匀性和随机性,从而随机从组播率为C的编码方案中选择一个编码方案,其编码方案是可行的概率为Pq.定理2: 在单源组播网络中以组播率H采用随机线性网络编码方法组播数据,且采用的有限域的阶为q(q|T|),记其编码方案为xH,宿点rT的全局编码矩阵的前C列构成的矩阵记为N(r,xH,C),则对于所有宿点,N(r,xH,C)的秩等于C的概率为Pq,即 (14)证明:在其阶为q的有限域下,不妨设有a个组播率为C的编码方案,其中有b个是可行的,则Pq=b/a.注意到 CH,由定义5,所有组播率为H的编码方案均由组播率为C的编码方案扩展而成.对组播率为C的编码方案,只需对源点输出信道的局部编码向量进展扩展,每一向量扩展H-C个分量,便构成了组播率为H的编码方案,则组播率为H的编码方案比组播率为C的编码方案多了 (H-C) |Out(s)|个分量,由随机线性网络编码方法在q阶有限域上取各分量值的均匀和随机性,再根据乘法原理,则组播率为H的编码方案数为aq|out(s)|(H-C),其中有bq|out(s)|(H-C)个编码方案是由组播率为C的可行编码方案扩展而成的,因而随机构造一个组播率为H的编码方案,它是由组播率为C的可行编码方案扩展而成的概率为Pq,由推论2,结论成立.性质2:对于单源组播网络,以组播率H采用随机线性网络编码方法传输数据,不妨记其编码方案为xH,则宿点rT接收到所有的数据包后,析出全局编码矩阵,并按式(15)计算h(r,xH),源点按式(16)计算f(xH),当采用的有限域足够大时,f(xH)不超过C且f(xH)=C的概率接近于1.(15) (16)证明:由矩阵的性质,当kH时,有rank(N(r, xH, k) rank(M(r, xH),再根据式(13),(15),(16),必定有f(xH) C.根据定理2,则f(xH) C的概率为Pq,从而当有限域较大时,f(xH) =C的概率接近于1.式(15)的含义是:对于任一宿点r,寻找一个最大的h,且满足全局编码矩阵M(v,xH)的前h列构成的矩阵其秩为h.可以通过对矩阵M(v, xH)作行初等变换,把矩阵化为上三角形式来计算式(15),限于篇幅,不作详细讨论.4. 应用以上描述的定理、推论与性质有助于有效地运用线性网络编码技术,具有一定的实用价值.4.1 不同组播率下编码系数的共享由性质1,假设单源组播网络具有一个组播率为h的可行编码方案,则可以任意选择组播率k(kh)进展数据传输,而不用重新构造编码方案.记原有可行编码方案为xh,假设采用组播率k进展数据传输,则可以采用xh的导出编码方案.由性质1,xh的导出编码方案必定是可行的.在组播率为k的导出编码方案下,源点输出信道的局部编码向量取其在xh编码方案下的局部编码向量的前k个分量,而其余信道的局部编码向量不变,从而各节点只要保存组播率为h的可行编码方案的编码系数,便可以采用组播率k(kh)进展数据传输.4.2 测试组播容量及构造编码方案性质2提供了一个测试组播容量的方法,因源点能获知其输出信道数H,则能以组播率H采用随机线性网络编码方法组播试验包至所有宿点,由于仅关心宿点的全局编码矩阵,则数据块可以为空,从而试验包的格式如图3所示.Fig.3 The structure of a trial packet图3 试验包的构造假设以组播率为H采用随机线性网络编码方法组播数据至网络,相当于随机产生了一个编码方案,不妨记为xH.所有宿点只需按式(15)计算h(r,xH),源点按式(16)计算f(xH).由性质2, 当有限域较大时,f(xH)=C的概率接近于1.我们把一次试验包的传输称为一次测试,当采用的有限域的阶不够大时,为确保找到组播容量,可以采用蒙托卡罗法进展屡次测试.每次测试时,源点记录最好的结果.这一策略还可以用于构造编码方案,只需在测试过程中各节点保存编码系数,则在测试出组播容量C的同时,构造出了组播率为C的可行编码方案.与文献6提出的LIF法相比,该方法具有操作简单的特点.假设各宿点能反应信息至源点,即宿点能把h(r,xH)的值传输至源点,则可以采用分布式方式在线测试组播容量.对于静态网络(网络拓扑在完成整个数据传输任务的过程中不会发生变化),假设所有宿点能反应信息至源点,则可以在线构造确定的网络编码方案,且各编码系数保存在相应的节点中,从而可以采用确定的网络编码数据传输策略传输数据.4.3 动态环境下网络编码数据传输策略假设宿点能反应信息至源点,则根据上述理论可以构造出网络拓扑动态变化环境下的网络编码数据传输策略.采用网络编码进展数据传输的最优策略是使组播率不超过且贴近组播容量,以便使网络的吞吐率尽可能大.如前所述,一个传输任务通过多批数据传输来完成,因网络拓扑的变化会造成组播容量的变化,则在各批数据传输时需要更改组播率以适应组播容量的变化.因此,一方面需进展数据传输,另一方面要测试组播容量,如把测试组播容量嵌入到每批数据传输过程中,则不会中断网络的数据传输.设当前的组播率为k, 假设采用随机线性网络编码方法组播数据,则对应一个组播率为k的编码方案,不妨记为zk;为测试组播容量,由上所述,需要以组播率为H采用随机线性网络编码方法组播试验包至网络,其编码方案记为xH.由于两者均具有随机性,可以把zk当成是xH的导出编码方案,由定义5和推论1,可以让这两个编码方案的编码系数共享.实施方法如下:源点相当于具有H条虚拟输入信道,它们分别注入H维向量空间的单位向量至源点s,记为p1,p2,pH,前k条虚拟输入信道分别把要发送的字符注入至源点s,记为y1,y2,yk,如图4所示.Fig.4 Testing multicast capacity in data transmission图4 数据传输过程中测试组播容量对于源点s的输出信道eOut(s), 其局部编码向量m(e)是一个H维的向量,设m(e)=(me,1,me,H),各分量由源点随机产生,则信道e传输的全局编码向量与字符分别按式(17)和式(18)计算.(17) (18)假设eOut(v)(vs), 其局部编码向量如式(1)所示,各分量由节点v随机产生,信道e传输的全局编码向量和字符分别按式(4)和式(2)计算.宿点rT接收到所有的数据包后,从中析出全局编码矩阵M(r, xH),把前k列构成的矩阵N(r, xH,k)作为方程组的系数矩阵,解出源信息字符;再按式(15)求出h(r, xH)并传输至源点s,源点s收到所有宿点的反应信息后,按式(16)便可以计算出组播容量(当有限域较大时),从而在下一批数据传输时,可以根据测试出的组播容量调整组播率,以便适应网络拓扑的变化.由性质2,因f(xH) C,即使f(xH)达不到C,则源点选取不超过f(xH)的组播率必定为可行的组播率.尽管采用这种策略测试出的组播容量是传输前一批数据时的组播容量,但当组播容量的变化具有一定的平稳性时,并结合重传技术(当有宿点不能解码时,要求源点重传信息),则仍不失为一种较好的策略,它能跟踪网络拓扑的变化,使组播率尽可能地适应组播容量的变化,且把测试组播容量嵌入至数据传输过程中,不会中断网络的数据传输,与随机网络编码方法相比,信道传输的数据包仅增加了全局编码向量的维数.5. 仿真测试采用5个测试用例,其中测试用例1如图4所示,其它4测试用例采用文献15的方法随机产生.测试用例1:|V|=26,|E|=85,|T|=5,H=13,C=6;测试用例2:|V|=40,|E|=174,|T|=10,H=11,C=10;测试用例3:|V|=45,|E|=202,|T|=10,H=12,C=9;测试用例4: |V|=50,|E|=237,|T|=10,H=13,C=12;测试用例5:|V|=55,|E|=259,|T|=10,H=14,C=11.测试方法如下,对不同的测试用例,在不同的伽罗华域GF(2m)下,以组播率H采用随机线性网络编码的方法组播试验包至网络,测试次数为500次,统计出所有宿点全局编码矩阵的前k(k=k1,C,其中k1C时,第三个编码方案必定是不可行的,前两个编码方案是第三个编码方案的导出编码方案,第一个编码方案也是第二个编码方案的导出编码方案,在测试过程中,我们还验证当第二个编码方案是可行时,第一个编码方案的可行性.Table 1 Simulation results表1 仿真结果m测试用例1测试用例2测试用例3测试用例4测试用例5k=5k=6k=9k=10k=8k=9k=10k=12k=10k=1140.8940.2720.8460.2740.980 0.7020.9940.3280.9980.91850.9800.5660.964 0.6120.996 0.8380.998 0.62810.95460.9960.7480.9960.8320.9980.91810.78210.99070.9980.8620.998 0.8961 0.9621 0.9001 0.992810.93010.95210.98610.95211910.97010.97210.99010.978111010.98810.98010.99210.986111110.98610.99410.9981111121111111111我们的试验结果说明,每当第二个编码方案是可行的,第一个编码方案必定是可行的,从而验证了性质1的正确性.从表1中可以看出,当有限域较大时(m10),对于给定的测试用例,在线测试出组播容量是一个大概率事件,从而验证了性质2的正确性;即使当有限域较小时(4m10),采用蒙托卡罗法,能测试出组播容量也是一个大概率事件.注意以下事实:采用式(16)求f(xH),则f(xH)k(kC)的充要条件是对于所有的rT,有rank(N(r, xH, k) =k成立.因而当有限域较大时,本文给出的动态环境下的数据传输策略是有效的,从表1中可以看出:对于单次测试,能测试出组播容量是一个大概率事件,即使式(16)中的f(xH)达不到C,必定与C接近.例如对于测试用例3,5,当m6时，每一次测试均使f(xH)的值不低于C-1.6. 完毕语针对单源组播网络,通过对线性网络编码的在机理进展分析,提出了不同组播率下编码方案的导出与扩展的概念,对具有导出与扩展的两个编码方案进展研究,导出了信道全局编码向量之间确实切关系,利用这个关系,结合随机线性网络编码方法,得出了几个重要的性质,这些性质有助于有效地运用线性网络编码技术,具有一定的应用价值.仿真结果验证了理论分析的结论.下一步的工作是在多源组播情况下,如何对这些理论和应用进展推广.References:1 Ahlswede R,Cai N,Li S R,et al.Network information flow .IEEE Transaction on Information Theory,2000,46(4):1204-1216.2 Li S-Y R,Yeung R W,Cai N.Linear network coding.IEEE Transaction Information Theory,2003,49(2):371-381.3 Koetter R,Medard M.An algebraoc approach to network coding.IEEE/ACM Transaction on Networking, 2003,11(5):782-795.4 Yang Lin, Zheng Gang, Hu *iao-hui. Research on network coding:A Survey.Journal of puter Research and Development,2021,45(3):400-407.5 ChouP A,Wu Y, Jain K. Practical network coding.Allerton Conference on munication, Control and puting, Monticello, 2003:473-482.6 Jaggi s,Sanders p,Chou A et al.Polynomial time algorithms for multicast network code construction.IEEE Transaction on Information Theroy,2005:51(6):1973-1982.7 Fragouli C,Soljanin E.Information flow deposition for network coding.IEEE Transaction on Information Theory ,2006,51(4):1295-1312.8 Ho T,Medard M,Koetter R,et al. A random linear network coding approach to multicast.IEEETransaction Information Theory,2006,52(10):4413-4430.9 Jabbarihagh M,Lahouti F. A decentralized approach to network coding based on learning.Information Theory for Wireless Networks, 2007 IEEE Information Theory Workshop on.10 Kim M, Medard M, Aggarwal,V et al.A doubly distributed genetic algorithm for network coding.2007 ACM Genetic and Evolutionary putation Conference (GECCO 2007), July 2007, London, UK.11 LunDS,RatnakarN,MedardMet al. Minimum-cost multicast over coded packet networks.IEEE Transactions on Information Theory,2006,52(6):2608-2623.12 Tracey H, Ben L, Muriel M et al.On the utility of network coding in dynamic Environments. Informational WorkshoponWireless Ad-hoc Networks (IWWAN) 2004.13 Zhao F, Medard M. Online network coding for the dynamic multicast problem. ISIT 2006, Seattle, USA.14 Wang Beng-shan. Discretemathematics.Changsha: National University of Defence Technology Press, 2004:263-281.15 Melancon G,Philippe F. Generating connected acyclic digraphs uniformly at random.Information Processing Letters,2004,90(4):209-213.附中文参考文献:4 林,刚,胡晓惠.网络编码研究进展.计算机研究与开展,2021,45(3):400-407.14 王兵山.离散数学.:国防科技大学,2004:263-281.附 录为专家审稿方便,特提供这个附录,如本文能发表,则附录局部不必登载.1 GF(22)运算表(极小多项式为)图2中的数据按以下表计算.四进制形式加法运算表+012300123110322230133210四进制形式乘法运算表*012300000101232023130312二进制形式加法运算表+000110110000011011010100111010101100011111100100二进制形式乘法运算表*0001101100000000000100011011100010110111001101102 求式(15)中h(r,xH)的算法找一个最大的列数h,使矩阵的前h列构成的矩阵的秩为h.设矩阵为,其中m为行数,n为列数.第1步:置i=1,mark=1;第2步:while mark=1 and im+1 and in+1 do第3步:检查第i列中自第i行至第m行的元素(ai,i,ai+1,i,am,i),假设所有元素全为零,置mark=0; 否则找出其不为零的元素所在的行号(记为k);第4步:假设mark=1,则进展下述工作 4.1 把第i行与第k行交换;4.2 把第j(iji;第5步: end while第6步:输出结果为i-1;第7步:完毕.该算法的时间复杂度为O(h2),其中h是满足条件的最大者.3 仿真测试中伽罗华域的代数运算方法因信息编码与数据通信均以比特流为根底,尽管文献1-3中指出网络编码技术是在有限域上进展信息编码,但在实际应用中宜采用伽罗华域伽罗华域是有限域的特例.这是因为同一伽罗华域上的字符均为位数一样的二进串,而一般的有限域不具备这个性质.定义114:一个F(2)上的不可约多项式叫做一个极小多项式,一个极小多项式可以唯一确定一个伽罗华域.一个极小多项式决定了其对应的伽罗华域的各个元素字符,同时也确定了该伽罗华域上的运算.在组播网络中采用网络编码技术进展数据传输时,要使各宿点能正确地解出源点播出的信息字符,各节点必须在一样的伽罗华域上进展编码,即各节点选定的极小多项式是一样的.设一个次数为m的极小多项式,如式(a)所示,其相应的伽罗华域记为GF(2m),其中q=2m称为伽罗华域的阶,m称为伽罗华域的次. (a)式(a)中的,即取1或0.由伽罗华域的性质,GF(2m)中的每一元素(字符)都是其极小多项式的根,即任意,有 (b)在已有的文献中,针对伽罗华域的乘除运算一般采用硬件电路实现,或者通过查找乘法表实现.由于不同的伽罗华域的乘法运算与不同的硬件电路对应,也与不同的乘法表对应,尽管这些方法运算简便,但对于网络编码技术是不适合的,主要原因是难以设计节点的编码器/解码器.网络中的节点可能会参与不同的组播连接,而每一组播连接所采用的伽罗华域的阶不一定一样,即节点必须具有不同阶伽罗华域的计算能力.假设采用硬件电路实现乘除法运算,编码器/解码器上必须具有不同阶伽罗华域的乘除法运算电路;假设采用查表法实现,则每一节点需要保存不同阶伽罗华域的乘法表,存开销将会相当地大.从而对网络编码来说,只能从伽罗华域的代数构造出发来构造代数运算方法,这样,节点的编码器/解码器只需要保存不同阶的伽罗华域的极小多项式和代数运算的算法,从而设计编码器/解码器成为可能.设GF(2m)上参与运算的三个字符分别记为:, (c)由文献14,伽罗华域的乘除法运算归结为其相应的多项式的运算,则它们对应的多项式分别记为:, (d)接下来表达伽罗华域的代数运算方法,其中除法运算方法是我们首次提出的.加法(减法)运算:加法运算就是两个字符对应位的异或运算,假设,则有,在伽罗华域上,减法与加法是同一运算乘法运算:两个字符的乘法运算转化它们相应的多项式运算,假设c=ab,则C(*)满足以下关系式14: (e)由式(e)可以确定乘法运算的方法:先进展两个多项式的相乘,在相乘过程中合并同类项时系数按模2加即异或运算,得到一个不高于2m-2次的多项式;然后对于次数大于或等于m的项,用式(b)代入进展降次,最后得到一个次数低于m的多项式,其系数便是字符c的相应位.除法运算:我们提出了一种适合网络编码的伽罗华域上的除法运算方法,该方法类似于欧几里德除法,描述如下:求c=a/b,则它们对应的多项式必须满足: (f)由于a,b是的,则它们对应的多项式A(*)和B(*)的系数是的,而C(*)是系数是未知的,分别用未知数c0,c1,cm-1表示,计算方程f的右边局部就是两个字符的乘法运算,则通过逐位相乘并合并同类项后得到一个次数不超过2m-2的多项式,它们的系数中含有未知数,与上所述,再用式(b)进展降次,便得到了一个次数不超过m且系数含有求知数的多项式,由式(f),利用与A(*)相等的关系,则其系数对应一样,可以得到一个m阶的线性方程组,采用高斯消元法求解这个线性方程组便提出了C(*)的系数,从而求出了商c.例:取m=3,极小多项式方程为,求伽罗华域GF(23)的两个字符(101)2与(110)2的商.解:置,则,用代入后,得,再用代入得再根据则得到以下线性方程组:采用高斯消元法求解得到商c=(100)2. z