网络编码技术在分布式内容分发中的应用

维普资讯 http://www.cqvip.com 第１３卷第４期　上海大学学报（自然科学版）　Ｖ０Ｉ．１３　Ｎｏ．４　２００７年８月　ＪＯＵＲＮＡＬ　ＯＦ　ＳＨＡＮＧＨＡＩ　ＵＮＩＶＥＲＳＩＴＹ（ＮＡＴＵＲＡＬ　ＳＣＩＥＮＣＥ）　Ａｕｇ．２００７　文章编号：１００７—２８６１（２００７）０４—０４６５—０６　网络编码技术在分布式内容分发中的应用　邹君妮，　李乐扬，　谭　冲　（上海大学通信与信息工程学院，上海２０００７２）　摘要：结合图论及有限域运算的相关知识，详细阐述了网络编码技术的编解码原理、优点及其应用领域．针对分布　式内容分发系统，讨论比较了分别采用不编码、纠删码和网络编码三种方式对数据进行处理的优缺点，并且从理论　分析和仿真实验两方面验证了网络编码在内容分发领域的优越性能．最后，指明了未来网络编码在实际应用中的　发展方向．　关键词：网络编码；对等网络；内容分发；组播　中图分类号：ＴＰ　３９３　文献标识码：Ａ　Ｎｅｔｗｏｒｋ　Ｃｏｄｉｎｇ　ｉｎ　Ｄｅｃｅｎｔｒａｌｉｚｅｄ　Ｃｏｎｔｅｎｔ　Ｄｉｓｔｒｉｂｕｔｉｏｎ　ＺＯＵ　Ｊｕｎ—ｎｉ，　ＬＩ　Ｌｅ—ｙａｎｇ．ＴＡＮ　Ｃｈｏｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａｎｇｈａｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０００７２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｇｒａｐｈ　ｔｈｅｏｒｙ　ａｎｄ　ｆｉｎｉｔｅ　ｆｉｅｌｄ　ｏｐｅｒａｔｉｏｎ，ｔｈｉｓ　ｐａｐｅｒ　ｉｎｔｒｏｄｕｃｅｓ　ｔｈｅ　ｐｒｉｎｃｉｐｌｅ　ｏｆ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎｓ．Ｆｏｒ　ａ　ｄｅｃｅｎｔｒａｌｉｚｅｄ　ｃｏｎｔｅｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｎｅｔｗｏｒｋ，ｔｈｒｅｅ　ｃｏｄｉｎｇ　ｍｅｃｈａｎｉｓｍｓ　ｉｎｃｌｕｄｉｎｇ　ｕｎｃｏｄｅｄ　ｄｉｓｔｉｒｂｕｔｉｏｎ，ｅｒａｓｕｒｅ　ｃｏｄｉｎｇ　ｂａｓｅｄ　ｄｉｓｔｉｒｂｕｔｉｏｎ　ａｎｄ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　ｂａｓｅｄ　ｄｉｓｔｉｒｂｕｔｉｏｎ　ａｒｅ　ｄｉｓｃｕｓｓｅｄ．Ｔｈｅ　ｅｘｃｅｌｌｅｎｔ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　ｂａｓｅｄ　ｃｏｎｔｅｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｉｓ　ｄｅｍｏｎｓｔｒａｔｅｄ　ｗｉｔｈ　ｂｏｔｈ　ｔｈｅｏｒｅｔｉｃ　ａｎａｌｙｓｉｓ　ａｎｄ　ｃｏｍｐｕｔｅｒ　ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔｓ．Ｋｅｙ　ｉｓｓｕｅｓ　ｉｎ　ｐｒａｃｔｉｃａｌ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　ａｒｅ　ｐｒｅｓｅｎｔｅｄ．　Ｋｅｙ　ｗｏｒｄｓ：ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ；Ｐ２Ｐ；ｃｏｎｔｅｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ；ｍｕｌｔｉｃａｓｔ　在目前的计算机网络通信中，中间节点（交换机　分析网络编码技术及其应用之前，首先介绍图　或路由器）都是采用传统的存储转发的信息处理方　论的相关背景知识．对于包含一个源节点ｓ和Ｌ个　式．输入的信息流被直接转发给下一个节点（单播通　汇节点　。，　，…，　的有向图　：（　，Ｅ），Ｖ代表顶　信），或者被复制之后转发给多个节点（组播通信）．　点（Ｖｅｒｔｉｃｅ）集合，Ｅ代表有向边（Ｅｄｇｅ）集合，用Ｒ　表　然而，网络中被传递的信息本质上就是连续的比特　示边（ｉ，＿『）∈Ｅ的容量，Ｆ　表示流经边（　，　）的流量，　流，是一系列抽象的代数符号，因此信息除了可以被　显然对所有（　，　）∈Ｅ，有０≤　Ｒ　而且，对Ｇ上　转发和复制之外，应该还可以进行代数运算．２０００　年，Ｒ．Ａｈｌｓｗｅｄｅ首次提出了对信息进行网络编码的　任意节点　（　∈　，　岳｛　，ｔ　｝），有　：　，　＝　。，：（　∈Ｅ　思想…．所谓网络编码，就是指节点对输入的多路信　：（舒一∈Ｅ＞：　　，即流人中间节点ｉ的数据总量等于流出　息流进行代数组合运算，生成一路或多路新的输出　节点　的数据总量．用Ｆ（ｚ）：［　，（ｉ，．，）∈Ｅ］表示　信息流．　Ｇ上从源点ｓ到汇点ｔ　的流，则Ｆ（２）的大小为　收稿日期：２００７—０２—０７基金项目：国家高技术研究发展计划（８６３计划）资助项目（２００６ＡＡ０１Ｚ３２２）　通信作者：邹君妮（１９７６一），女，讲师，博士，研究方向为多媒体通信、分布式系统和网络信息论．Ｅ－ｍａｉｌ：ｚｏｕｊｎ＠ｓｈｕ．ｅｄｕ．ｃａ　维普资讯 http://www.cqvip.com 上海大学学报（自然科学版）　第１３卷　Ｆ（　）＝∑　一∑　：　：【　－，）∈Ｅ　ｌ：【　，５）∈Ｅ　网络编码可以重复进行，换言之，节点可以对收　到的已编码的信息向量进行再次编码．假定节点收　ｉ：【ｉ－‘　）∈　∑ＦＩｆｊ一∑Ｆ　，：【ｆ』，，）∈Ｅ　（１）　到了ｍ个信息向量（ｇ　，Ｘ　），…，（ｇ　，　），它对ｍ　用ｍａｘ｛Ｆ（　）｝表示从源点ｓ到汇点ｔ　的最大流值，　根据最大流最小割定理，有ｍａｘ｛Ｆ（Ｚ）｝＝ｍｉｎ　个信息向量再次编码，生成新的信息向量（ｇ　，Ｘ　）．　这里ｇ　＝（ｇ　，…，ｇ：）代表与　相对应的编码向　量，二者满足　｛ｃ（　）｝，这里ｍｉｎ｛Ｃ（　）｝代表ｓ和￡　之间最小割的　容量．　如果将组播通信网络映射为有向图，用ｓ和ｔ．，　ｔ　，…，￡　分别代表组播源和组播成员，那么从ｓ同　时流向ｔ　，ｔ　，…，ｔ　的最大流值（即组播最大容量）　满足　Ｆ　＝ｍｉｎ｛ｍａｘ（Ｆ（　））｝＝　ｆｔ【１，…，Ｌ，　ｍｉｎ｛ｍｉｎ（Ｃ（　））｝，　（２）　ｆ∈（１．…，Ｌ）　即组播最大容量等于组播源与组播不同成员之间最　大流的最小值．　１　网络编码原理　我们以目前普遍采用的随机线性网络编码　习　为例，来说明网络编码的原理．假定流入节点的每个　数据包的包长度均为　ｂｉｔ（位数不够末尾添零），如　果把这　ｂｉｔ中每连续的ｓ　ｂｉｔ映射为有限域　中　的一个元素，那么就可以把这个数据包看成一个包　含　／ｓ个元素的向量．这样，从代数学的角度来看，　数据包之间的编码运算就等同于一系列向量的线性　组合，并且线性组合所用到的加法和乘法，必须遵循　有限域的运算法则．选择有限域是缘于它的两条性　质：（１）有限域中的元素个数是有限个；（２）有限域　中的元素对于该有限域所定义的两种运算（加法和　乘法）是封闭的．这不仅极大增强了线性组合的灵活　性，同时保证了运算所得的结果不会占据额外的存　储空间　．　１．１编码过程　假设原始信源由ｎ个数据包　，…，Ｍ　组成，　节点对流入的这ｎ个数据包进行网络编码，生成１　个新的数据包Ｘ＝∑ｇｉＭ‘．其中，ｇｉ就是有限域　中的元素，它由节点随机产生．由于编码运算在有限　域中进行，所以　所占据的存储空间与Ｍ‘完全相　同．组合运算的系数ｇ＝（ｇ　一，ｇ　）称为编码向量，　称为信息向量．编码完成后，节点将编码向量和　信息向量（ｇ，　）同时转发出去，用于目的节点对信　息向量进行解码，恢复原始信源．　＝∑　＝∑　（∑　Ｍ‘）＝　，：ｌ　，＝ｌ　ｉ＝ｌ　∑（∑　）Ｍ　＝∑　．　（３）　：ｌ　Ｊ＝ｌ　ｉ＝ｌ　１．２解码过程　当一个节点收到ｍ个编码后的数据包（ｇ　，　），…，（ｇ　，Ｘ　）后，为了恢复出ｎ个原始数据包　Ｍ　，…，Ｍ　，只需求解以下方程组：　Ｘ　＝ｇ：Ｍ　＋ｇ　Ｍ　＋…＋ｇ＇ｏＭ　，　＝ｇ２ｌ　Ｍ　＋ｇ２２　Ｍ　＋…＋ｇ２ｎ　，　（４）　Ｘ爪＝ｇｍ１　Ｍ　＋ｇｍ２　Ｍ　＋…＋ｇ：　．　这是一个含有ｎ个未知数和ｍ个方程的线性方程　组．我们知道，只有当方程个数大于或等于未知数个　数（即ｍ≥ｎ）时线性方程组才有唯一解．虽然ｍ≥ｎ　并不是充分条件，因为方程之间有可能出现线性相　关的现象，即编码向量之间线性相关．虽然编码向量　之间的线性相关程度取决于所选取的有限域的大　小，但实验证明即使选择比较小的有限域，比如ｓ＝　８的有限域，编码向量之间出现线性相关的概率也　是非常小的　．因此，节点的解码过程是非常简单　的，节点不需要接收指定内容的数据包，只要接收到　足够数量的线性无关的编码数据包，就可以成功恢　复原始数据．　２网络编码技术的优点　在组播通信中，由于从信源ｓ到不同信宿ｔ　之　间的最大流经过的路径可能在Ｇ的某些链路上形　成交叉共享链路，进而影响共享链路之间节点的数　据传输率，因此采用传统的存储转发模式一般是不　可能达到式（２）规定的组播信息容量上限的．２００３　年，Ｒ．“证明了在单信源多信宿情况下应用线性网　络编码理论，一定能够达到该上限　Ｊ．　概括来讲，对于单信源多信宿的组播系统，除了　存储转发操作之外，在系统的中间节点对信息进行　网络编码操作，可以为系统带来以下几方面的　益处　．　维普资讯 http://www.cqvip.com 第４期　邹君妮，等：网络编码技术在分布式内容分发中的应用　４６７　２．１提高组播速率，实现组播最大容量　能容忍节点２或３中一个失效或离开，否则系统中　的其他节点就不能从剩余节点中完整地获取数据　口、ｂ、ｃ、ｄ；而图２（ｂ）中允许任一节点失效或离开，　我们通过图１的示例来说明这一点，图１（ａ）给　出了网络拓扑结构及不同链路的容量，其中．ｓ是信　源，Ｒ　、Ｒ：和Ｒ　是３个不同的信宿．显然，从．ｓ到　尼（ｉ＝１，２，３）的最大流均为４，所以将信息从．ｓ同时　其他节点都能够自适应地做出调整，重新路由，从剩　余的３个节点完整地获取数据口、ｂ、ｃ、ｄ．　发送给Ｒ　、Ｒ　和Ｒ　时的最大组播容量也是４．然而　从图１（ｂ）可以看出，存储转发模式下的单组播最大　速率仅为２，图１（Ｃ）显示在部分节点上进行网络编　码能够提高组播速率至４，实现组播最大容量．　图１存储转发方式与网络编码方式的比较　Ｆｉｇ．１　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｓｔｏｒｉｎｇ　ａｎｄ　ｆｏｒｗａｒｄｉｎｇ　ｗｉｔｈ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　２．２节约系统带宽，有利于负载平衡　采用图１（ｂ）的存储转发方式，同时传输２　ｂｉｔ信　息占有的链路带宽总量为１０；而采用图１（ｄ）的网络　编码方式，同时传输２　ｂｉｔ信息所占有的链路带宽总　量为９．相比之下，后者可以节约１０％的系统带宽．　前者集中使用了系统中的５条链路，闲置了另外４　条链路，导致节点上的带宽资源占用情况非常不平　衡；而后者均衡地利用了系统中的全部９条链路，很　好地平衡了网络负载．　２．３提高系统的鲁棒性和自适应性　如图２所示，图中每个节点都存储了一组固定　长度的数据．图２（ａ）中的每个节点均以原始格式对　数据进行存储，图２（ｂ）中的每个节点均以网络编码　后的格式对数据进行存储．可以看出，图２（ａ）中只　（ｂ）　图２节点失效或离开的影响示例　Ｆｉｇ．２　Ｉｍｐａｃｔ　ｏｆ　ｔｈｅ　ｎｏｄｅ’ｓ　ｉｎｖａｌｉｄｉｎｇ　ｏｒ　ｌｅａｖｉｎｇ　３网络编码的应用　网络编码将原先分立于物理层和网络层的两个　核心概念——编码和路由有机地融为一体，彻底改　变了路由器只能对信息进行存储转发的传统模式，　建立起一种全新的网络体系结构及信息编码和传输　模式．网络编码代表了一种协同工作的理念，这使得　它的应用不仅局限于改进组播增加网络容量，与其　他技术相结合已经应用于分布式内容存储与分　发［６］、应用层组播　］、无线传感器网络数据采集‘８］、　网络管理　、信息安全Ｈ。。等众多领域．　３．１分布式内容存储与分发　传统的分布式内容分发或Ｐ２Ｐ对等通信时，　Ｐｅｅｒ之间传送的是未编码的原始数据块（ｂｌｏｃｋ），诸　如Ｐｅｅｒ节点的搜索定位方法、资源分发与调度算法　优化、网络负载平衡以及数据分发路由设计等问题　都是目前Ｐ２Ｐ内容分发所面临的难题．而在Ｐｅｅｒ之　间传输经过网络编码的数据块能够有效解决甚至避　免这些问题．　３．２应用层组播　Ｐ２Ｐ技术与覆盖网络（ｏｖｅｒｌａｙ　ｎｅｔｗｏｒｋ）的发展，　将组播功能从ＩＰ层扩展到了应用层，在Ｐ２Ｐ应用层　维普资讯 http://www.cqvip.com ４６８　上海大学学报（自然科学版）　第１３卷　组播系统中，Ｐｅｅｒ节点对流经的数据除了进行存储　转发外，如果还可以进行额外的网络编码处理，将可　以在很大程度上改善应用层组播性能，提高覆盖网　络数据吞吐能力．　３．３无线传感器网络数据获取　在无线传感器网络中，传感器节点的数据存储　能力十分有限，如何将这些节点采集的信息在最小　代价、最小耗能、最大容量等约束下发送给存储节点　是当前网络编码在无线通信领域的一个新课题．　３．４网络管理　对于链路被截断等物理故障，传统的解决办法　是启用备份链路进行重新路由，而对于采用网络编　码的节点，改变编码规则就可以改变其传递给其他　节点的信息内容，这同样起到了重新路由的作用，而　且这种网络管理方式的开销非常小．　３．５信息安全　攻击者恶意篡改网络上传输的数据内容将直接　影响接收端的信息接收，这是目前计算机通信网的　一个潜在隐患．采用随机网络编码技术，攻击者对接　收端收到的其他编码数据无法进行预知和控制，数　据篡改的影响可以降至最低．　４分布式内容分发中的应用　下面我们以分布式内容分发为例，来详细分析　网络编码的性能．　简单说来，内容分发就是指服务器将一组相同　的数据分发到网络的多个客户机（Ｃｌｉｅｎｔ）．互联网上　传统的内容分发系统是基于Ｃ／Ｓ（客户机／服务器）的　网络模式，中央服务器负责将整个文件发送给所有　客户机，客户机之间彼此不允许通信，都只能与服务　器通信．随着客户机的增加，服务器的负载越来越　重，形成了系统的瓶颈，一旦服务器崩溃，整个网络　将跟着瘫痪．　随之出现了ＣＤＮ（内容分发网络）技术，ＣＤＮ的　基本思想是将待分发文件部分或全部缓存到位于互　联网“边缘”的代理服务器上，客户机根据地理位置　从位于本地的代理服务器上获取文件，从而减轻中　央服务器的负荷，同时也增加了系统容量．然而　ＣＤＮ的部署成本十分昂贵，而且也并没有脱离Ｃ／Ｓ　的本质．　内容分发系统的另外一种典型网络模型就是　Ｐ２Ｐ网络（对等网络），它是一种新兴的网络模型．与　Ｃ／Ｓ模式完全不同，在Ｐ２Ｐ网络中，所有的节点都是　对等的，各节点可以不通过服务器直接互连而共享　网络资源，协同完成任务．与服务器集中控制的Ｃ／Ｓ　模式相比，Ｐ２Ｐ模型采用的是一种分散控制方式，这　在很大程度上降低了系统对服务器的依赖程度，而　且节点越多，网络规模越大，网络的性能就越好．　考虑一个Ｐ２Ｐ的内容分发网络，假定网络上共　有　个节点，其中　个为存储节点，其余　一　个为　下载节点．文件被分割为ｎ个数据块（ｂｌｏｃｋ），每个　存储节点最多能够存储后（后＜ｎ）个数据块，每个下　载节点最多可以与ｒ（ｒ＜　）个存储节点通信．一旦　下载节点从其他节点处成功下载到ｎ个ｂｌｏｃｋ，它就　可以重建原始文件，结束下载任务．对ｂｌｏｃｋ的数据　处理我们采用３种编码方式：不编码、纠删码和网络　编码．　（１）不编码　不编码指的是ｎ个ｂｌｏｃｋ不进行任何编码处　理，以原始数据格式直接存储在下载节点中，而且网　络上节点之间交互的ｂｌｏｃｋ也是未经过编码的原始　数据．目前，互联网上的Ｐ２Ｐ内容分发系统，诸如　ＢｉｔＴｏｒｒｅｎｔ（ＷＷＷ．ｂｉｔｔｏｒｒｅｎｔ．ｃｏｒｎ）等，普遍采用的是不　编码方式．　关于不编码方式进行内容分发的统计性能，我　们给出以下结论，详细证明方法可见文献［１１］．　①为完成　％的下载任务，下载节点平均需要　连接的存储节点个数为ｎｌｎ【　）；　②连接ｒ个存储节点，下载节点平均完成的下　，　１、ｈ　载任务率为１一Ｉ、　　１一　ｌ；ｎ／　　③为完成整个下载任务，下载节点平均需要连　接的存储节点个数为ｎｌｎ（ｎ）／ｋ．　（２）纠删码　纠删码（Ｅｒａｓｕｒｅ　Ｃｏｄｅ）方式指的是文件的ｎ个　ｂｌｏｃｋ不直接存储在存储节点中，而是先对它们进行　纠删码编码，生成ｎ（１＋ｂ）个编码后的ｂｌｏｃｋ，然后　采用与不编码方式相同的存储方式来存储这些　ｂｌｏｃｋ，下载节点只要下载到ｎ（１＋ｂ）个编码ｂｌｏｃｋ中　的任意ｎｙ个，就可以进行解码操作，重建原文件．　这里，１／（１＋ｂ）称为编码码率，ｂ和ｙ的取值由纠删　码的具体编码类型所决定．Ｒｓ（Ｒｅｅｄ　Ｓｏｌｏｍｏｎ）码和　Ｔｏｒｎａｄｏ码都是比较常用的纠删码，其中Ｒｓ码的ｙ　为１．　关于纠删码的统计性能，我们有以下结论：当　维普资讯 http://www.cqvip.com 第４期　邹君妮，等：网络编码技术在分布式内容分发中的应用　＝１，而且ｂ足够大时，下载节点只要连接芋个存　ｆ　Ｉ），＝１．可以看出，不编码方式因为节点之间存储的　重复数据块很多，所以完整下载到１００个ｂｌｏｃｋ需要　连接的存储节点次数最大，纠删码（ｂ＝２，４）的连接　次数次之，网络编码连接的次数最少，几乎连接任意　２０个存储点就可以完成下载．而且，有限域的大小　（ｑ＝２，３，７）对下载性能的影响也非常小．　储点就能完成文件下载任务　．芋是下载节点完成　下载任务必须连接的存储节点的最少个数，连接的　存储点数量越少，下载速度越快，下载延时越短，对　于下载节点而言，这是最理想的情况．然而，ｂ越大，　占用的服务器存储空问越大，解码算法也越复杂，下　载耗时也越长，这又是最不希望出现的情况．因此，　采用纠删码方式进行内容分发时，必须在ｂ的取值　和存储节点连接数量之间作出权衡．　与不编码方式相比，纠删码方式最大的优势在　于出现链路丢包或错误时，下载点不需要采用自动　重传机制（如ＡＲＱ）就可以完成下载任务．不过它也　存在２个问题：（１）同一个文件，纠删码方式在服务　器端存储的是ｎ（１＋ｂ）个ｂｌｏｃｋ，它所占用的存储空　间比不编码方式大６％；（２）编码操作只能在服务　器端进行，存储节点等中间节点不能进行编码，这是　一种端到端的集中式编码方式，可扩展性不强．　（３）网络编码　如前所述，网络编码是一种完全的分布式编码，　编码操作可以在服务器端和中间节点同时进行，中　央服务器对ｎ个ｂｌｏｃｋ进行随机线性网络编码，生　成ｎ个编码ｂｌｏｃｋ，不需要占用额外的存储空间．存　储节点对所存储的ｋ个编码ｂｌｏｃｋ进行再编码，生　成新的ｂｌｏｃｋ传送给下载节点．一般情况下，下载节　点只要获得ｎ个ｂｌｏｃｋ，就可以解码出原始文件．　节点完成网络编码之后，必须将信息向量　和　编码向量ｇ（ｇ　，ｇ：，…，ｇ　）同时发送给下一个节点，　因此需要占用额外带宽来转发编码向量ｇ．考虑分　发一个１００　ＭＢ的文件，ｎ＝５００，则每个ｂｌｏｃｋ的大小　为０．５　ＭＢ，选取ｓ＝８的有限域，那么每传输一个　０．５　ＭＢ的编码ｂｌｏｃｋ，需要的额外开销为５００×８　ｂｉｔ／　０．５　ＭＢ＝０．１％．可见，网络编码的开销是非常小的，　几乎可以忽略不计．　５　仿真分析　为确保编码算法的可移植性，我们采用ｃ＋＋语　言对采用上述３种编码方式的分布式内容分发算法　进行了仿真实现．图３显示了下载节点与存储节点　的平均连接次数与下载进度之间的关系．其参数设　置如下：文件分块数ｎ＝１００，存储节点个数ｒ＝４０，　每个存储节点存储的数据块个数ｋ＝５，纠删码的　图３连接次数与下载进度的关系　Ｆｉｇ．３　Ｄｏｗｎｌｏａｄ　ｐｒｏｇｒｅｓｓ　ｗｉｔｈ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｃｏｎｎｅｃｔｉｏｎｓ　进行网络编码时，每个编码ｂｌｏｃｋ中所包含的原　始ｂｌｏｃｋ的个数Ｌ（编码维数）对下载性能的影响是　非常大的．图４显示了ｎ＝１０、ｒ＝１０、ｋ＝１时，网络　编码的编码维数与节点下载性能之问的关系．显然，　三越大，每个编码ｂｌｏｃｋ中包含的原始文件信息越　多，节点从每个编码ｂｌｏｃｋ获取的信息量也越大，为　了完成下载任务，需要连接的存储节点数也越少．当　Ｌ＝１０时，即所有原始ｂｌｏｃｋ参与每次编码过程，节　点连接次数最少．　太小（Ｌ≤５），所有编码ｂｌｏｃｋ都　不能提供原始文件的完整信息，因而节点始终无法　恢复出原始文件．　１０Ｏ　９０　８０　芝７０　６０　５０　４０　３０　２０　ｌ０　０　图４编码维数对下载进度的影响　Ｆｉｇ．４　Ｄｏｗｎｌｏａｄ　ｐｒｏｇｒｅｓｓ　ｗｉｔｈ　ｔｈｅ　ｃｏｄｉｎｇ“ｄｅｎｓｉｔｙ’’　６　结　论　作为一个新兴的研究领域，近年来对网络编码　的研究主要集中在编码的方法、复杂性等理论问题，　维普资讯 http://www.cqvip.com ４７０　上海大学学报（自然科学版）　第１３卷　２００５年微软剑桥实验室成功开发出第一个基于网　络编码的文件分发系统Ａｖａｌａｎｃｈｅ，使得网络编码技　术开始从理论研究转向实际应用．不过，有研究指　［Ｒ／ＯＬ］．［２００７一Ｏ１—０５］．ｈｔｔｐ：／／ｗｗｗ．却．ｕｉｕｃ　ｅｄｕ／ｋｏｅｔｔｅｄ　ＮＷＣ／ｉｎｄｅｘ．ｈｔｍ１．　［５］　ＮＯＧＵＣＨＩ　Ｔ，ＭＡＴＳＵＤＡ　Ｔ，ＹＡＭＡＭＯＴＯ　Ｍ．Ｐｅｒｆｏｒｍａｎｃｅ　ｅｖａｌｕａｔｉｏｎ　ｏｆ　ｎｅｗ　ｍｕｈｉｃａｓｔ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｗｉｔｈ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　出，大规模的矩阵运算造成网络编码的编码和解码　时间过长，使得Ａｖａｌａｎｃｈｅ相比于ＢｉｔＴｏｒｒｅｎｔ，在总体　性能方面并没有明显优势；而且，Ｐ２Ｐ网络中网络编　［Ｊ］．ＩＥＩＣＥ　Ｔｒｎｓａ　Ｃｏｍｍｕｎ，２００３，Ｅ８６一Ｂ：１７８８—１７９５．　［６］　ＧＫＡＮＴＳＩＤＩＳ　Ｃ．Ｒ０ＤｍＧＵＥＺ　Ｐ．Ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　ｆｏｒ　ｌａｒｇｅ　ｓｃａｌｅ　ｃｏｎｔｅｎｔ　ｄｉｓｔｒｉｂｕｔｉｏｎ【Ｃ】／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　ＩＮＦＯＣＯＭ　码应用层组播尚未有明确的解决方案．因此，未来几　年，实用化的网络编码技术还必须解决编解码算法　简化与优化、应用层组播路由实现以及编码过程缓　冲与同步等现实问题．　参考文献：　ＡＨＬＳＷＥＤＥ　Ｒ，　ＣＡＩ　Ｎ，　ＬＩ　Ｓ　Ｒ，　ｅｔ　ａ１．　Ｎｅｔｗｏｒｋ　ｉｎｆｏｒｍａｔｉｏｎ　ｆｌｏｗ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｆｎｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ。２０００，４６（４）：１２０４—１２１６．　［２］　Ｈ０　Ｔ，Ｋ０ＥＴＴＥＲ　Ｒ，ＭＥＤＡＲＤＭ，ｅｔ　ａ１．Ｔｈｅ　ｂｅｎｅｆｉｔｓ　ｏｆ　ｃｏｄｉｎｇ　ｏｖｅｒ　ｍｕｔｉｎｇ　ｉｎ　ａ　ｒａｎｄｏｍｉｚｅｄ　ｓｅｔｔｉｎｇ［ｃ］／／２０ｏ３　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ　（ＩＳＩＴ）．Ｊａｐａｎ：ＩＥＥＥ　Ｐｒｅｓｓ，２００３：４４２—４４５．　［３］　ＬＩ　Ｓ　Ｙ　Ｒ．ＹＥＵＮＧ　Ｒ　Ｗ．ＣＡＩ　Ｎ．Ｌｉｎｅａｒ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｆｎｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，２００３，４９　（２）：３７１．３８１．　［４］　ＦＲＡＧＯＵＬＩ　Ｃ，ＢＯＵＤＥＣ　Ｊ　Ｌ，ＷＩＤＭＥＲ　Ｊ．Ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ：ａｎ　ｉｎｓｔａｎｔ　ｐｒｉｍｅｒ，ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　ｔｅｃｈｎｉｃａｌ　ｒｅｐｏｒｔ　２０ｏ５．Ｍｉａｍｉ：ＩＥＥＥ　Ｐｒｅｓｓ。２０ｏ５：２２３５．２２４５．　［７］　ＺＨＵ　Ｙ，ＬＩ　Ｂ，ＧＵＯ　Ｊ．Ｍｕｈｉｃａｓｔ　ｗｉｔｈ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ　ｉｎ　ａｐｐｌｉｃａｔｉｏｎ—ｌａｙｅｒ　ｏｖｅｒｌａｙ　ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ　Ｊ　Ｓｅｌｅｃｔ　Ａｒｅａｓ　Ｃｏｍｍｕｎ，２ｏｏ４，２２（１）：１－１３．　［８］　ＢＥＮＮＥＴｒ　ｊ　Ｃ　Ｒ。ＺＨＡＮＧ　Ｈ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｐａｃｋｅｔ　ｆａｉｒ　ｑｕｅｕｉｎｇ　ｌａｇｏｒｉｔｈｍｓ［Ｊ］．ＡＣＭ／ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｎｅｔｗｏｒｋｉｎｇ，　１９９７，５（５）：６７５．６８９．　［９］　Ｋ０ＥＴｒＥＲ　Ｒ，ＭＩ￣ＤＡＲＤ　Ｍ．Ｂｅｙｏｎｄ　ｍｕｔｉｎｇ：ａｎ　ａｌｇｅｂｒａｉｃ　ａｐｐｒｏａｃｈ　ｔｏ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　ＩＮＦＯＣＯＭ　２０ｏ２．Ｎｅｗ　Ｙｏｒｋ：ＩＥＥＥ　Ｐｒｅｓｓ，２００２：１２２—１３０．　［１Ｏ］　ＨＯ　Ｔ，Ｕ　０ＮＧ　Ｂ，　ＫＯＥＴｒＥＲ　Ｒ，ｅｔ　ａ１．　Ｂｙｚａｎｔｉｎｅ　ｍｏｄｉｉｆｃａｔｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｍｕｈｉｃａｓｔ　ｎｅｔｗｏｒｋｓ　ｕｓｉｎｇ　ｒａｎｄｏｍｉｚｅｄ　ｎｅｔｗｏｒｋ　ｃｄｏｉｎｇ　ｌ　Ｃ］／／２００４　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ（ＩＳＩＴ）．２００４：１４３—１４７．　ＡＣＥＤＡＮＳＫＩ　Ｓ，ＤＥＢ　Ｓ，ＭＥＤＡＲＤ　Ｍ，ｅｔ　ａ１．Ｈｏｗ　ｇｏｏｄ　ｉｓ　ｒａｎｄｏｍ　ｌｉｎｅａｒ　ｃｏｄｉｎｇ　ｂａｓｅｄ　ｄｉｓｔｒｉｂｕｔｅｄ　ｎｅｔｗｏｒｋｅｄ　ｓｔｏｒａｇｅ？　［Ｃ］／／ＮｅｔＣｏｄ　２００５，Ｉｔｌａｙ．２０ｏ５：１—６．　（编辑：刘志强）