一种提高网络编码在P2P应用中效率算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种提高网络编码在P2P应用中效率算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘要】 传统P2P网络中，每个中间节点都只是存储转发，不会对接收到的文件块做任何处理。在P2P中引入网络编号后[3-4]，在入度大于等于二的节点上进行网络编码，可以提高文件的传输效率，而且还能提高网络的鲁棒性。改进后的网络编码，不是对每个入度大于等于二的中间节点都进行网络编码，而是只对关键路径的入度大于等于二的节点进行编码，这样就会节省了网络编码和解码消耗的时间，提高了传输效率。
【关键词】 网络编码 p2p网络 BT系统
一、传统的P2P方式
在P2P网络中，每个节点都是对等了，既充当服务器，又充当客户端。与C/S模式不同。P2P中最流行的是BT系统，它可以把每一个加入进来下载资源的主机变成服务器。BT系统中有跟踪服务器，种子节点和下载节点。跟踪服务器记录了每个加入进来的主机的状态。假如主机A上有个文件file，主机B、C、D、E分别想下载主机A上的file文件。主机B第一个加入进来下载主机A上的文件，主机B向主机A上的跟踪服务器注册，得到file在主机A上的信息块，取得主机A的节点信息，此时主机B与主机A的节点信息建立了连接，告诉主机A上的跟踪服务器要下载的文件信息，然后从种子节点开始下载，此时如果没有其他的主机加入进来，这就是典型的C/S模式。当主机C加入进来时，主机C向A上的跟踪服务器注册，由于主机A此时还和主机B连着，这时主机A的跟踪服务器会帮助主机B和主机C建立连接，主机C可以从主机A，B上获取资源，同时也把自己已有的资源向主机B提供。这时主机B和主机C分别既当下载资源的客户机，也当提供资源给别的主机下载的服务器。随着主机D，E的加入进来，这样就构成的对等的局域网络。假如主机A的file分成了4个文件块，主机B，C，D，E分别只得到了文件块file1，file2，file3，file4，此时主机A由于网络故障退出了这个网络，要是在C/S模式下，这样主机B，C，D，E都不能得到原来的文件file。但是在P2P模式下，他们分别可以为其他主机提供自己已有的资源，这样即使没有主机A，他们也能从其他主机上得到其余文件块，最终复原想要下载的file文件。所以P2P还有很好的鲁棒性。
二、引入网络编码后的P2P方式
在传统的P2P模式下，每个节点都只是存储转发，不会对文件进行任何操作，人们都认为在中间节点上对文件进行操作完全没有必要，起不到任何有益作用，然而在2000年，R Ahlswede等人提出了网络编码这一个概念[1]。在网络通信中，网络中的中间节点会对要存储转发的信息进行一定的线性或者非线性的编码操作[5]，然后转发给下一个节点，这样会使网络中的通信容量达到最大。
如图1（a）A为信源节点，E，F为信宿节点，假设每条链路的容量为1比特/单位时间。A分别向中间节点B，C发送两个比特的信息a，b。在一个单位时间内，B接收到一个信息比特a，C接收到一个信息比特b。在下一个单位时间内，E，F分别可以得到a，b信息中一个，D点可以同时接收到a，b信息。如果不引入网络编码，而是传统的存储转发，由于每条链路容量为1比特/单位时间，G点要接收到信息a，b需要两个单位时间。但是如果在D点引入网络编码，如图1（b），信息a，b会通过网络编码，组合成一个信息a+b。这样，只需一个单位时间就可以把D点的信息传到G节点上。这点在现实生活中很重要。S.Y.R. Li进一步证明了在单信源多信宿情况下，应用线性网络编码理论[6]，一定能够达到该上界[2]。G点得到信息a+b。在下一个单位时间，G点把信息分别传到信宿节点E，F上。E，F通过解码，在E上得到信息b，在F上得到信息a。这样在信宿节点E，F就分别都获取到a，b两比特信息。
数学模型，服务器有一个文件D，分成n份，每个数据包为M1，M2，M3，…，Mn，则原数据可以表示为D=（gi） （Mi）（其中gi为Mi数据片段随机产生的编码系数），在网络中传输的为数据D和编码系数gi。数据从发送端到接收端经过的每个节点通过迭代进行编码。假设一个节点收到的数据包为（g1，D1），（g2，D2），…，（gj，Dj），（gm，Dm），（gj，Dj）表示第j个数据包编码系数向量和信息向量，这个节点的随机产生的编码系数为V1，V2，…， Vm得到的信息向量D’=（Vi） （Di），从而得到新的数据包（g’，Di）， gi’=Vjgij。每经过一个节点进行一次编码迭代，最后在接收端进行译码，通过接收到的系数向量恢复出原来的信息，接收端的数据包至少等于发送端的数据包。
三、改进网络编码后的P2P方式
在网络中，并不是对每个节点都需要进行网络编码的。只需对入度大于等于2的节点需要进行网络编码。如图2（a）是传统的网络编码，在节点A，B，C的入度均为1，无需进行网络编码，节点D，E的入度为2，需要进行网络编码。但是进行网络编码和解码时，也会消耗一定的时间。
如图2（b）是经过改进后的网络编码，在D节点无需进行网络编码，这样就节省了在D节点的编码时间和在F节点的解码时间。
作者简介：
刊物邮寄地址：北京市丰台区莲花池东路106号汇融大厦建行开发中心 张雷 15590264889
参 考 文 献
[1] R. Ahlswede， N. Cai， S.-Y. R. Li and R. W. Yeung， "Network information flow"， IEEE Transactions on Information Theory，vol.IT-46，NO.4， pp. 1204-1216， July.2000.
[2] S.Y.R. Li， R. W. Yueng， and N. Cai， "Linear network coding"， IEEE-IT， vol.IT-49， no.2，pp.371-381， Feb.2003.
[3] Han Liu，Xiaodong Tu，Jun Xie， "Network Coding For P2P Live Media Streaming". IFIP International Conference Network and Parallel ComPuting.2008.
[4] 陶少国，黄佳庆，杨宗凯， “网络编码研究综述”.通信技术.2010.
[5] 张璇，张博，慕建军， “线性网络编码及其在P2P文件共享系统中的应用”， 2008年西安电子科技大学研究生学术年会.
[6] 周伟伟，线性网络编码研究.通信技术.2008.