信息论与编码在处理网络问题中的应用

信息论与编码在处理网络问题中的应用摘要随着计算机技术、通信技术和网络技术等信息技术的快速发展，信息技术已经成为当今社会应用范围最广的高新技术之一。信息论是信息技术的主要理论技术基础之一，它的一些基本理论在通信、计算机、网络等工程领域中得到了广泛的应用。其中信息论与编码与网络结合的更为紧密，在网络方面得到了广泛的应用。本文主要从这个方面作为切入点，介绍了信息论与编码在网络编码、基于网络编码的路由选择、在网络安全方面的放窃听的网络编码，还有就是在网络数据挖掘这方面的应用。1.引言人类社会的生存和发展无时不刻都离不开信息的获取、传递、再生、控制和利用。信息论正式一门把信息作为研究对象的科学，以揭示信息的本质特性和规律为基础，应用概率论。随机过程和树立统计等方法来研究信息的存储、传输、处理、控制和利用。它主要研究如何提高信息系统的可靠性、有效性、保密性和认证性，以使信息系统最优化。许多科学技术问题（如无线电通讯、电视、遥测、图像和声音识别等）都必须以信息论为理论指导才能很好地解决。信息论的研究对象又可以是广义的信息传输和信息处理系统。从最普通的电报、电话、传真、电视、雷达、声纳,一直到各类生物神经的感知系统,以及大到人类社会系统,可以用同一的信息论观点加以阐述,?都可以概括成某种随机过程或统计学的数学模型加以深入研究。2.概述2.1信息与信息论1948年6月和10月香农在贝尔实验室出版的著名的《贝尔系统技术》杂志上发表了两篇有关《通信的数学理论》的文章。在这两篇文章中，他用概率测度和数理统计的方法系统的讨论了通信得基本问题，首先严格定义了信息的度量——熵的概念，又定义了信道容量的概念，得出了几个重要而带有普遍意义的结论，并由此奠定了现代信息论的基础。Shannon理论的核心是：揭示了在通信系统中采用适当的编码后能够实现高效率和高可靠地传输信息，并得出了信源编码定理和信道编码定理。从数学观点看，这些定理是最优编码的存在定理。但从工程观点看，这些定理不是结构性的，不能从定理的结果直接得出实现最优编码的具体途径。然而，它们给出了编码的性能极限，在理论上阐明了通信系统中各种因素的相互关系，为人们寻找出最佳通信系统提供了重要的理论依据。而其理论到目前主要经历了以下几个方面的发展：Shannon信息理论的数学严格化、无失真信源编码定力和技术的发展、信道纠错编码的发展、限失真信源编码的提出和发展、多用户、网络信息论的发展、信息保密与安全理论的提出与发展，从此以后，纠错码和密码学相结合的研究迅速发展起来。2.2网络与信息论网络信息论的发展前期是多用户信息论，在20世纪70、80年代有很大的发展，当时的多用户信息论已具有网络结构的特征，其中的信源与信道模型已具有多数人多输出的结构，对信道还有并联与串联的结构等模型，多用户信息论就是解决这些模型的编码问题，一时成为信息论研究的热点问题。到20世纪90年代，由于网络通信的兴起，网络模型远比多用户模型复杂，网络中的通信、数据压缩、资源共享与安全管理将是信息论发展的重要领域。2.3网络编码2000年Ahlswede等人首次提出了网络编码理论,通过网络编码可以实现网络流量的最大化.2003年,Li,Yeung和Cai证明了线性网络编码就可以实现网络的最大流.随后T.Ho等人提出了随机网络编码理论,其思想是在网络中参与传输的节点,其输出信道上传输的数据是该点多条输入信道上传输的数据的随机线性组合,他们并且证明了接收节点能以很大的概率正确恢复出信源所发送的信息.传统的通信网络传送数据的方式是存储转发，即除了数据的发送节点和接收节点以外的节点只负责路由，而不对数据内容做任何处理，中间节点扮演着转发器的角色。长期以来，人们普遍认为在中间节点上对传输的数据进行加工不会产生任何收益，然而RAhlswede等人于2000年提出的网络编码理论彻底推翻了这种传统观点。网络编码是一种融合了路由和编码的信息交换技术，它的核心思想是在网络中的各个节点上对各条信道上收到的信息进行线性或者非线性的处理，然后转发给下游节点，中间节点扮演着编码器或信号处理器的角色。根据图论中的最大流-最小割定理，数据的发送方和接收方通信的最大速率不能超过双方之间的最大流值(或最小割值)，如果采用传统多播路由的方法，一般不能达到该上界。RAhlswede等人以蝴蝶网络的研究为例，指出通过网络编码，可以达到多播路由传输的最大流界，提高了信息的传输效率，从而奠定了网络编码在现代网络通信研究领域的重要地位。3.信息论与编码在处理网络问题中的应用3.1在防止网络窃听方面的应用前面介绍的网络编码提高了网络的吞吐量和可靠性，但同时时也带来了不可忽视的安全问题,主要包括污染和窃听两类问题。针对窃听问题，文献[1]提出一种防窃听的网络编码算法.应用该算法,窃听者得不到关于信源的任何有意义的信息,称之为弱安全.该算法通过舍弃少量带宽使得随机网络编码能以很高的概率达到弱安全性的要求.另外,当信源和信宿共享有秘密信道时,秘密信道编码算法达到弱安全性要求的概率为1,且能达到网络的最大流.该编码算法仅是在原随机编码体制的基础上对信源和信宿进行了改变,中间节点编码保持不变.弱安全就是在实际应用中对安全性的要求并不一定要像信息论安全这样高.例如,如果窃听者得到了关于信源的两个比特的异或b1b2,他虽然得到了关于信源的一个比特的信息,但他却无法得到关于信源的任何“有意义”的信息,即他无法得到b1或b2.在实际应用中这样的安全性就足够了.这样的安全性是弱于信息论安全的,称之为“弱安全”。文献[2]中提出了一种基于信息论安全的网络编码方案。利用大素数及其本原根产生不同的噪声符号，并将噪声符号与原始信息进行混合，达到隐藏信息的目的。分析结果表明，该方案通过舍弃少量带宽，使网络编码以很高的概率达到信息论安全的要求，当信源与信宿之间有一条专用的安全信道时，可在不增加通信开销的前提下使网络的信息论安全概率为1。这两种方法都能在一定程度上提高网络编码的安全性，只是所采用的方法不同，文献[1]通过舍弃少量带宽，而文献[2]则通过增加噪声符号和原始信息混合，进而达到对窃听者进行干扰的作用。文献[3]介绍了现在一些网络编码方式和存在的一些问题，并介绍网络编码以后的发展方向。3.2在防止网络污染方面的应用前面介绍的网络编码除了会造成窃听问题外还会带来污染攻击。污染攻击是指攻击者利用网络中间节点生成虚假的编码消息，大量的转发至其他节点，占用传输信道，降低网络吞吐量，甚至导致目的节点出现译码异常的现象。对于网络编码中的污染问题，传统的数字签名方法都不适用。于是，人们提出一些新的签名算法来满足网络编码的需求：一类是同态数字签名技术；另一类是基于同态哈希函数的签名技术，前者需要安全信道传输哈希值，后者大多基于双线性运算。然而，以上适用于单源网络编码的签名算法无法应用于多源网络编码中，其主要原因在于：现有的单源网络编码签名算法只需用一个私钥对消息进行签名，而在多源网络编码中，不同的信源节点用不同的私钥进行签名。针对这一现象文献[4]提出一种可抵御污染攻击的多源线性网络编码签名算法，其中，每个源节点用自己的私钥对文件签名，中间或信宿节点仅用公钥即可验证收到的签名，利用随机预言模型证明该算法能够抵抗信源节点和中间节点的攻击。该算法仅假设每个源节点只发送一个消息，若考虑发送多个消息，针对多信源、多消息的向量合并算法解决，其能够线性组合来自不同信源的多个消息，组合后的向量数据为元线性组合，而增量元保持不变。文献[5]则在在已有的同态HASH签名基础上，为了解决网络编码传输过程中容易遭受污染攻击的问题，提出了一种新型的应用同态HASH函数的抗污染攻击系统，网络中的各个节点通过同步同态HASH函数的参数和原始消息分组的HASH值来对所收到的每个分组进行验证，只有通过验证的分组才会转发给下一个节点。该方案结合了针对源节点与目标节点端对端在线验证的安全ACK验证方案，从而能有效抵抗网络编码中的污染攻击。同时，为了有效降低网络编码中各节点的运算时间，文章提出了硬件加速的方法，利用FPGA开发板进行数据分组的验证以及编码操作，以提高系统的运行效率。该系统能够提高整体网络吞吐量，并确保被篡改的数据不会因为编码在整个网络中扩散，对于网络编码环境下的网络传输安全具有重要的作用。基于网络编码的同态HASH抗污染攻击系统在效率和安全性上取得了一定的平衡。从测试结果来看，安全性问题得到了很好地解决，一般强度的污染攻击已经能很好地识别并抵抗。从计算代价来看，传输延迟完全在一个用户可以接受的范围内。3.3在无线网络路由方面的应用无线网络具有不可靠的传输链路、动态的拓扑结构、受限的信道带宽和节点电量等显著特征.近年来,多路径路由在无线网络中得到了广泛的应用.多路径路由可以有效地提高数据传输的可靠性,在节点间平衡网络流量负载和电量消耗,降低端到端时延和路由发现频率,应对频繁的拓扑结构变化及其带来的不可靠的通信服务,以及改进网络的安全性等.但是,多路径路由又会导致多条路径上同时发送数据包所带来的网络拥塞问题,特别是当选择多条不相交的路径传输数据包时,拥塞会变得更加严重.针对这个问题文献[6]提出了一种基于网络编码的多路径路由机制CAMP(networkcoding-awaremulti-pathrouting).该机制能够根据路径的可靠性和编码机会,动态地在多条路径上进行数据包的传输.CAMP的路由发现机制能够向源节点返回多条可能的路径以及各条路径的每条边上的ETX(expectedtransmissioncount).与以往的多路径路由机制不同,CAMP可以通过转换它的传输路径来动态地创造而非仅仅等待编码机会.利用这一独特的路由制,CAMP可以让多条路径分摊网络流量负载,并且最大化路径转换收益,从而改进网络的吞吐量.实验结果表明,在无线网络的数据传输过程中,CAMP能够取得比其他路由机制高得多的网络吞吐量.CAMP由两个阶段组成:路由发现阶段和数据包发送阶段.CAMP的路由发现机制能够向源节点返回多条可能的路径以及各条路径上所有链路的ETX.每条路径上的中间节点会为以后的路径交换决策保存其他候选路径信息.与现有的多路径路由机制不同的是,CAMP可以从当前默认路径转换到具有最大路径转换收益的路径,从而动态地创造编码机会,而不仅是等待编码机会.实验结果表明,在无线网络的数据传输中,与其他基于网络编码的传统最佳路径路由、多路径路由和单路径路由机制相比,CAMP能够大幅度提高网络吞吐量.文献[7]提出了出一种无需重传与确认的路由算法,这种算法以最小化单位比特有效数据的能耗为目标,给出最优化数学模型,并用遗传算法进行求解.所提出的免重传路由算法可以降低能耗,减轻节点之间的无线电干扰,节省了节点用于重传数据包所需配置的缓存.文献中基于网络编码思想并结合多路径数据传递方法,提出一种称为“免重传网络编码路由”的节能算法(以下简称“免重传路由”).在这种路由算法支持下,信源将要发送的数据分成多个数据片,然后选取一组线性独立的系数,利用线性网络编码形成新的数据分组(下称“编码数据分组”),将编码数据分组分别通过不同的路径发送,确保信宿收到一定数量的编码数据包进而获得信源所发送的数据.这种路由算法的主要特点在于:不需要重传机制,也就是说接收节点不需要发送ACK包,同时发送节点也不需要重发数据包.本文的主要贡献在于:利用无线网络编码技术,在多条路径中选择最佳路径进行数据传递,避免了数据包重传与确认,同时降低能耗及减轻无线电干扰,节省所有节点为重发数据包所必须配置的用于存储尚未得到接收节点确认的数据包的内存空间.3.4在网络数据挖掘中的应用互联网的出现，不仅改变了人们获得信息的生活方式，也造就了很多以前从来没有过的专业或行业。网络上的数据每天都在爆炸式地增长，其中肯定有不少有价值的信息，只不过被掩埋在数量上占压倒多数的八卦和”垃圾“里面而已。文献[8]针对时序数据库提出一种基于信号处理和信息论网络的方法，并使用模糊和集成的概念来简化规则库，通过这些方法来进行数据库挖掘。时