多级网络编码方案

多级网络编码方案宋雪;周异辉;师军;吴振强【摘要】目前安全网络编码的研究有信息论安全和密码学安全两种方法。信息论安全的编码方案中，中继节点编码主要是使用随机线性网络编码(RLNC)生成编码矩阵，但是此方法并不能保证生成的矩阵一定满秩，从而影响方案的解码率。提出了一个多级网络编码(MLNC)方案，该方案通过在源端使用对角矩阵对消息进行编码，以降低编码复杂度；在中继节点，让入度大于等于2的节点作为编码节点，使用多级的网络编码使混淆效果更好，编码节点随机生成满秩的下三角矩阵和上三角矩阵，用它们的乘积作为编码矩阵，这样能保证编码矩阵满秩，接收节点可以成功解码。Matlab仿真结果表明，MLNC编码矩阵达到k-安全概率优于RLNC编码矩阵，并证明MLNC方案满足信息论安全。%Thecurrentsecurenetworkcodinghastwomethods.Theyareinformation-theoreticsecurityandcryptographysecurity.Amongtheencodingmethodsofinformation-theoreticsecurity,theencodingschemeoftherelaynodeusestheRandomLinearNetworkCoding(RLNC)togeneratetheencodingmatrix.Butthismethoddoesnotguaranteethattheresultingmatrixmustbefullrankandaffectsthedecodingrate.ThispaperproposesaMulti-LevelNetworkCoding(MLNC)scheme.Theschemeusesthetrianglematrixtoencodesourcemessage.Ontherelaynode,thenodewhosedegreeisgreaterthanorequalto2isusedascodingnode,usingmulti-levelnetworkcodingcanmakethemessageencodemixbetter.Theencodingnodesgeneratethefullranklowertriangularmatrixandthefullrankuppertriangularmatrixrandomly.Itusestheirproductasanencodingmatrix.Thisschemewillensureencodingmatrixmustbefullrank.Thereceivingnodecansuccessfullydecodethedata.TheresultoftheMatlabsimulationshowsthattheprobabilityofthecodingmatrixofMLNCsatisfyingk-securecanbebetterthanRLNC.AndtheschemeofMLNCsatisfiesthetheoreticsecurity.【期刊名称】《计算机工程与应用》【年(卷)，期】2015(000)018【总页数】5页(P94-98)【关键词】网络编码;对角矩阵;多级网络编码;k-安全【作者】宋雪;周异辉;师军;吴振强【作者单位】陕西师范大学计算机科学学院，西安710062;陕西师范大学计算机科学学院，西安710062;陕西师范大学计算机科学学院，西安710062;陕西师范大学计算机科学学院，西安710062【正文语种】中文【中图分类】TP3931概述网络编码理论是2000年由香港中文大学RudolfAhlswede[1]等基于网络信息流的概念首次提出的。通过允许网络节点进行编码，指出网络信息流可以被处理/压缩，从而可进一步提升网络吞吐量，实现网络流量的最大化，即网络资源利用的理论上限，而通过传统的路由和复制并不能够获得该最大流限。2003年香港中文大学的李硕彦教授、杨伟豪教授、蔡宁教授等人在文献［2］中指出线性网络编码可以达到多播方式下的网络容量。近几年，研究者们发现网络编码也可以实现网络中信息的安全传输，文献［3］论述了网络编码在安全方面的应用，为网络编码增加了新的应用领域，给出搭线窃听的网络通信模型。文献［4］提出安全网络编码满足以下两个条件：(1)可解码条件：伽为编码函数，p,p'为随机密钥，对于所有用户ueU和所有消息x,x,eX,x/x,,^u(x,p)/^u(x,/p,);(2)安全条件：对于窃听子集weW,Yw为窃听信道获得的信息，X为源消息，H(X|Yw)=H(X)。文献［5］给出了存在信道噪声时网络纠错编码的具体编译码算法。文献［6］给出了具体的信息论安全的网络编码方法。网络编码具有一定的优势，可以提升网络有效性、可靠性、安全性和降低复杂度，但是需要中间节点进行编码，相对于路由的存储转发，增加了因编译码带来的计算和存储方面的复杂度，与此同时，允许中间节点参与编译码，因而凸显了安全问题。文献［7］通过简单网络法降低编码复杂度，将网络转变为节点入度和出度之和不超过3的简单网络，但简单网络的节点数比原网络扩大了很多，即网络编码的节点数的代价被放大，简单网络法的最小代价不等于原网络的最小代价。文献［8］提出了一种基于稀疏矩阵理论的随机线性网络编码的对等内容分发技术，其性能较传统线性随机编码有所改善，但只降低了编码的复杂度，没有降低解码的复杂度。文献［9］提出一种基于稀疏矩阵的低复杂度安全网络编码算法，在源端对信息进行稀疏矩阵(对角矩阵)变换，然后在中继节点进行随机线性网络编码，但是不能保证汇点一定能解码。通过对以上文献的优缺点的比较，本文提出一种多级网络编码方案(MLNC),MLNC方案既可以降低编码复杂度，又可以保证中继节点生成的矩阵满秩，并采用多级网络编码，在源端使用对角矩阵对源消息进行变换；中继编码节点随机生成下三角矩阵和上三角矩阵，并用它们的乘积作为编码矩阵对数据进行编码，确保本方案在汇点能够成功解码，分析表明MLNC的编码矩阵达到k-安全的概率高于RLNC编码矩阵，并证明MLNC方案满足信息论安全。2安全网络编码方案本文基于多播图进行研究，该网络拓扑图如图1所示。图1拓扑图通信网络中用一有向无环图G=(V，E)表示，其中V是节点的集合，E是边的集合，令Fq为q阶有限域，q为一个素数。对于任意节点vGV,uuV,若存在从v到u的有向信道，则用有向边e=(v,u)表示此信道，u称为e的头节点，v称为e的尾节点，即tail(e)。拓扑图1中S为源节点，A、B、W为中继编码节点，Z1和Z2为接收节点。下面以图1为例详细介绍MLNC方案的实施过程。首先，在源端S点进行编码，使用对角矩阵对源端消息进行变换。其次，将入度大于等于2的中继节点A、B、W作为编码节点，中继编码节点随机生成满秩的下三角矩阵和上三角矩阵，并用它们的乘积作为编码矩阵对数据进行编码。最后，通过全局编码矩阵的逆和对角矩阵的逆对消息进行解码，还原出源消息。算法1源端节点编码算法在源节点S处进行如下的操作：输入编码数据信息输出进行对角矩阵变换后的消息选取有限域中的一个随机数t作为种子，通过随机数生成器生成11,12，…，In，并排列成对角矩阵L;使用加密函数对种子t进行加密并放在数据包的头部。(2)令X，=(X1,X2，…，Xn)L=(X1',X2',...,Xn')。(3)S=GX'为信源节点S最后要传输到网络中的信息，G为全局编码矩阵。算法2中继节点编码算法在中继编码节点进行如下操作：首先随机生成一个满秩的下三角矩阵C，和一个上三角矩阵D，矩阵C和D的乘积为M，作为系数矩阵，这样生成的系数矩阵一定满秩；对源消息进行编码得S'=MS=G'X'。算法3信宿解码算法在汇点Z1和Z2处进行解码：(1)S'为信宿接收到的信息，信宿获得全局编码向量G',通过全局编码矩阵的逆可求出信息X'=S'G'-1。(2)通过解密密钥得t,以t为种子，通过随机数生成器得到序列11,12，…，In,即可得L。(3)解码出源信息X=X'L-1。算法4随机数生成器算法3实例分析以图1为例，假设源端发送两个数据包X1和X2,令Y代表各个链路传输的数据包，S‘代表汇点接收的数据包，8代表编码向量，具体的编码过程如下：对于接收节点Z1,接收的矩阵为：假设数据包X1=[01],X2=[10],则源端消息X=[0110],所有的操作都是在有限域GF(23)上进行的，随机选取种子3，在随机数生成器上生成随机数(1653),并构造对角矩阵：然后用对角矩阵对源消息进行操作得X'=XxL=[0650],分别构造矩阵：在中继节点根据编码算法生成矩阵：可得矩阵：从而得，因为：解码可得，用解密密钥获得种子为3，然后根据随机数生成器算法生成随机数(1653),并形成对角矩阵。从而得：即可得源消息X=X'xL-1=[0110]。同理对于接收节点Z2接收信息也是如此，窃听者所能窃听到的消息都是变换了(编码后)的消息，并且随机数种子t是保密的，即使获得中间节点编码的消息，也无法获得矩阵L,所以能保证消息的安全性。4仿真实验与分析4.1复杂度分析本文所提出的安全网络编码方案是对信源进行了对角矩阵变换操作，在中间节点使用随机生成下三角矩阵和上三角矩阵，并用它们的乘积作为编码矩阵对数据进行编码。所以从整个编码过程来说，信源编码的复杂度只是与矩阵的维数相关，矩阵的维数越高，复杂度就越高，因此算法的时间复杂度为O(n2)。4.2安全性分析根据预备知识定义的两个条件进行以下证明。可解码条件证明前提假设经过推导变换后得到的cr+1，cr+2，…，cn这n-r个数有不为0的数。对于源端消息x=[x1,x2,_/xn]和x'=[x1',x2',...,xn'],x玫，则k=xxL=[k1,k2，…，kn]和，假设对应的编码矩阵分别为：对源消息分别进行编码得：如果两个消息编码之后一样则A=A‘，即A和A'中元素对应相等，可得方程组如下：此方程组为不定方程组，如果方程有解则证明编码后的消息相等。根据文献[10]转换得：因为cr+1,cr+2，…，cn这n-r个数有不为0的数，所以方程组无解，因此本方案满足可解码条件。安全条件证明对于文中编码方案，如果窃听者能获得链路所有的消息，它就能够还原出源端发送的消息，但是源端编码过程中p是保密的，所以窃听者无法获得源消息，即Yw和X是相互独立的，满足安全条件。通过证明可知，本文编码方案满足安全网络编码的两个条件，因此本方案是安全的网络编码。4.3仿真分析在有限域Fq中，n阶矩阵共有个，其中n阶可逆矩阵共有个，所以在有限域Fq上任意取一n阶矩阵，可逆的概率为。在有限域F（23）上，以3阶矩阵为例，对于3阶编码矩阵和源消息［x1x2x3］，信宿接收到的消息为（z1，z2，z3），可得，求其满足2-安全的概率p，即获得任何两条链路都获得不到消息的概率。（1）MLNC编码矩阵（满秩）编码矩阵中元素为非0元素，从有限域中1~7个数中选取，窃听到两条链路即可得两个方程，能获得消息（即有解）的概率为：MLNC方案是采用多级网络编码，如图1所示，采用二级网络编码，使用一级网络编码时有解的概率为33.8%，则使用二级网络编码有解的概率p2=p1xp1必11.4%。则获得不到任何消息的概率为：pMLNC=1-p2必88.6%（2）RLNC编码矩阵在RLNC编码矩阵，矩阵中元素是随机选取的，不是完全可逆的，要使接收方能获得源消息，编码矩阵必须可逆。编码矩阵中元素为非0元素，从有限域中1~7个数中取，窃听到两条链路即可得两个方程，不能获得任何消息（即无解）的概率为：在Matlab中取1000组矩阵进行仿真，仿真编码矩阵达到2-安全的个数。RLNC方案达到2-安全的概率为56.9%，则1000组矩阵达到2-安全的矩阵有569个；MLNC方案达到2-安全的概率为66.2%，则1000组矩阵达到2-安全的矩阵有662个。结果表明系数矩阵越安全，消息在网络中传输就越安全。本文对MLNC方案和RLNC方案达到k-安全的编码矩阵的个数进行比较，分析结果如表1所示。表1MLNC与RLNC方案比较2-安全232425262728MLNC886915948969980990RLNC761840896937960985图23阶矩阵图2对安全网络编码方案进行分析，横坐标是有限域的大小，纵坐标是满足m-1(m阶方阵中最高安全级别)安全的概率，可知使用的MLNC方案是更安全的，以有限域GF(23)为例，在图2的3阶矩阵中，MLNC达到2-安全的概率为88.6%，RLNC达到2-安全的概率为76.1%，MLNC高于RLNC12.5%。5结束语本文研究了网络编码的安全问题，在源端利用对角矩阵对消息进行变换、降低复杂度的同时，中继节点使用多级的网络编码对消息进行编码。理论分析和实验结果表明，MLNC的编码矩阵达到k-安全的概率高于RLNC编码矩阵达到k-安全的概率，MLNC方案可以更好地提供数据保密，并满足信息论安全。【相关文献】AhlswedeR，CaiN，LiSYR,etal.Networkinformationflow[J].IEEETransactionsonInformationTheory,2000,46(4):1204-1216.LiSYR,YeungRW,CaiN.Linearnetworkcoding[J].IEEETransactionsonInformationTheory,2003,49(2):371-381.CaiN,YeungRW.Securenetworkcoding[C]//2002IEEEInternationalSymposiumonInformationTheory，