《（毕业论文）-基于网络编码的机会网络数据分发研究与仿真》由会员分享，可在线阅读，更多相关《（毕业论文）-基于网络编码的机会网络数据分发研究与仿真（57页珍藏版）》请在金锄头文库上搜索。
1、中北大学 2013 届毕业设计说明书 第 1 页 共 57 页 1 1 引言引言 1.11.1 研究问题现状研究问题现状 近年来，无线通信技术得到了飞速的发展，新技术不断出现，其中移动通信 系统的 3G 技术已经进入应用普及阶段，并朝第四代通信系统方向演进。 国家中 长期科学和技术发展规划纲要(2006 一 2020)中已经明确提出了未来通信领域的 竞争将集中反映在特殊环境和新兴应用领域中的通信网络能力及通信技术的竞争 上1。其中新兴应用领域涉及到的移动网络技术更是被作为前沿技术中的重点。 目前,移动通信的快速发展使得移动网络带宽逐渐增大，移动应用不断丰富，移动 终端的处理能力越来越强。为了适
2、应不同的应用需求,各具特色的网络结构和无线 网络技术不断涌现,包括无线个域网(如 IEEE802.15)、无线局域网(如 IEEE802.lla/b/g/i/n)、无线城域网(如 802.16、802.20)、无线移动广域网(如 2G、3G)、卫星网络，以及无线自组织(Ad Hoc)网络、无线传感器网络(Wireless Sensor Network,WSN)等等。而 WIFi、WIMax、UWB 等无线接入网络和 GPRS、B3G、UMTS 等蜂窝移动网络等基础设施与技术的完善为移动应用提供了在 任何时间、任何地点访问所有网络服务的可能性。 在上述的各种网络发展后，一种节点移动范围更大，网络
3、大多数都是不连通 的新型网络出现了，这种类型的网络被称为机会网络，机会网络是一种不需要源 节点和目的节点之间存在完整路径，利用节点移动带来的相遇机会实现网络通信 的自组织网络。 经过近几年的发展，机会网络技术研究与应用已经取得了一定的进展，但是， 总体而言目前相关研究还处于一个刚起步的初级阶段。随着移动应用业务的增加 以及机会网络商业化，机会网络技术的全面应用与深入仍然要解决很多极具挑战 性的问题，如复杂环境下的路由、数据时延与网络开销均衡问题、移动状态下网 络可靠性以及安全问题等等。同时在一些领域，机会网络的相关技术标准尚未形 成，尤其在国内对于这类高延迟的特殊通信网络的研究才刚刚起步。规划
4、信息化 发展战略中不仅强调了信息产业以及信息技术的发展，同时也提出了将宽带无线 移动通信、新兴及特殊应用领域的网络通信等核心关键技术研究作为我国信息技 术的主要发展方向之一。因此，对机会网络数据分发展开研究将为正确理解机会 中北大学 2013 届毕业设计说明书 第 2 页 共 57 页 网络拓扑与数据传输特点提供可行性依据，有助于推进现有关键技术的可扩展性， 并对提高机会网络数据传输可靠性，探索节点移动模型对机会网络服务性能保障 的影响，推动相关技术的深入研究有重要现实的意义。 2000 年,R.Ahlswede 等人基于网络信息流的概念提出了网络编码的思想，通 过允许中间节点既实现路由功能又
5、实现编码功能，达到组播的最大流量2。为使 得网络编码具有实际可用性，Li 等人提出了线性网络编码的概念，证实节点进行 线性网络编码运算，具有可行性，能够达到最大流传输理论极限3。Ho 等人推广 了这一概念，提出了有限域下随机线性网络编码的思想，并证实其有效性4。之 后，随机线性网络编码被应用于各个方面的研究，用于提高网络吞吐量、能量利 用效率。 网络编码彻底改变了通信网络中信息处理和信息传输的方式，被认为是进入 21 世纪后信息处理和信息传输研究领域上最重要的理论成果之一。网络编码的核 心思想是允许通信网络中的节点对传输的信息进行操作和处理（如有限域中的运 算等） ，而不再局限于存储与转发。与
6、传统的基于存储和转发的路由传输机制相比， 网络编码能显著改善数据分发系统性能，如提升网络吞吐量，节约传输带宽和均 衡网络负载等。网络编码具有重要的理论价值和广泛的应用前景，其研究已经引 起了学术界和产业界的广泛关注和高度重视。国际知名大学、科研机构和公司， 如普林斯顿大学、麻省理工学院（MIT） 、贝尔实验室（Bell Lab） 、AT；2)节点异构性:某些节点能够到达所有位置，遇到 所有其他节点；3)行为时变性:节点移动随着时间变化。Musolesi等人17结合社 会网络理论提出了一种基于社区的移动模型。该模型根据节点之间联系的紧密程 中北大学 2013 届毕业设计说明书 第 9 页 共 5
7、7 页 度，将节点分布在多个在不同区域的社区，然后计算不同社区对每个节点的吸引 力，并以此确定节点是否移动以及朝哪个目标区域移动。Spyropoulos 等人18,19 提出了时变的社区移动模型，每个节点的工作周期由正常移动周期和集中移动周 期组成，每个周期内，节点随机选择一个社区作为它的本地社区。节点在每个周 期都有两种移动状态，Local epoch和Roaming epoch。前者是选择在本地社区内 移动，后者是在其他地方漫游。节点在两个状态之间以一定的概率来切换，形成 一个马尔可夫链，概率大小由所处的移动周期来确定。例如，在集中移动周期内， 节点访问本地社区的概率较高。 2.52.5
8、网络编码的概念思想网络编码的概念思想 在传统网络中，结点仅对接收的数据进行存储和转发，难以达到网络传输的 最大吞吐量和带宽利用率，若数据传输路径出现瓶颈链路，则网络数据传输性能 将受限于瓶颈链路。对此，在网络中引入网络编码技术，增加结点对数据的编码 运算功能，节约网络链路的带宽资源，减小网络数据传输中瓶颈链路的影响。 网络编码(network coding)是一种融合编码和路由的信息交换技术，在传统 存储转发的路由方法基础上，通过允许对接收的多个数据包进行编码信息融合， 增加单次传输的信息量，提高网络整体性能。Ahlswede等人于2000年提出了网络 编码概念，指出对组播网络中的某些节点附加
9、额外的编码操作能使源与组播成员 间达到最大流最小割心的组播速率。网络编码一经提出便引起了国际学术界的广 泛关注，其理论和应用已成为通信领域研究的新热点网络编码在提高网络吞吐 量、改善负载均衡、减小传输延迟、节省节点能耗、增强网络鲁棒性等方面均显 示出其优越性，可广泛应用于Ad Hoe网络，传感器网络、P2P内容分发、分布式文 件存储和网络安全等领域。经过几年的发展，网络编码的理论研究已取得重要进 展，在应用基础和工程实践方面的研究正在全方位展开。网络编码已成为一项融 合信息论、代数学、图论、网络流理论和优化理论等多学科的交叉技术，且日益 引起更多研究者的关注，其对现有的网络体系结构、协议设计方
10、法、信息交换方 式和网络管理模式带来了革命性的变化。 网络编码的基本思想是使网络中的节点不仅具有存储转发的功能，他们还能 够打若干个待转发的数据包进行编码压缩成一个数据包，然后转发给相应的接收 节点，并且以足够大的概率保证它的接收节点能够顺利地解码恢复出原始的数据 中北大学 2013 届毕业设计说明书 第 10 页 共 57 页 包，从而减少传输次数，提高网络吞吐量，降低网络延迟。 以一个简单的具代表性的蝴蝶网络来描述网络编码的思想，一下均假设每条 链路单位时间只能传输单位bit的数据数据信息量。 图2.3和图2.4中分别是利用网络编码前后的网络传输状态，该网络有一个源 节点S，两个端节点Y，
11、Z以及其余4个T,W,U,X是四个中转节点。在图2.2中，b1和 b2都是源s向端节点y和x发出的两个单位bit的信息，当b1和b2到达w节点时，由于 一次只能处理一个单位的信息，所以W只能选择发送其中之一，而另一个则必须送 入等待队列，因此，要使Y和Z这两个目的节点都要收到这两个信息，则W必须至少 传送两次；图2.3表示的是网络编码方法，节点W对输入的信息进行网络编码操作 （“+”表示模二加） ，然后将操作结果 b1 + b2（称为编码信息）发送至输出链 路(W,X)，然后又通过链路(X,Y)和(X,Z)，最终传送给信宿 Y 和 Z。当信宿 Y 收 到 b1 和 b1 + b2后，通过逆过程
12、的译码操作 b1 + (b 1 + b 2)就能恢复出信源 S 发出的 b2，这样使得信宿 Y 同时收到了 b1 和 b2。按照同样的方式，信宿 Z 也可恢复出信源发出的 b1（通过译码操作b 2 + (b 1 + b2)）而同时收到 b1 和 b2。也就是说，基于网络编码的数据分发模式实现了该组播的理论传输容量。可 见，与传统的路由传输方式相比，网络编码提升了网络的吞吐量。 图2.2 网络结构 图2.3 普通的存储转发 图2.4 运用网络编码 从上述实例可以看出，基于网络编码的数据分发的具体实施过程是：具备编 码条件的中间节点（比如该节点的入度至少为 2，如图2.4中的节点 W 就具备编 码
13、条件，节点 T，U 和 X 等则不具备编码条件，只能执行存储和转发操作）对接 收到的数据信息按照一定方式的处理（编码） ，然后传输给下一级的网络节点，收 到信息的下一级节点如果具备编码条件，又对其接收的信息按照同样的方式进行 中北大学 2013 届毕业设计说明书 第 11 页 共 57 页 处理和传输，如此反复，直到所有经过处理后的信息都汇聚到信宿节点为止。最 后，在信宿节点，通过逆过程的操作（译码） ，即可译出信源发出的原始信息。 节点对传输的信息进行如何处理和操作，属于网络编码的码构造问题。如果 节点对传输的信息进行线性操作，则称为线性网络编码；否则称为非线性网络编 码（Non-linea
14、r Network Coding） 。如果网络节点对信息进行操作的系数是随机 选取的，则称为随机网络编码；如果是通过算法确定出来的，则称为确定性网络 编码。因此，线性网络编码是一种有效的网络编码码构造方式，当前具体的基于 网络编码的数据分发系统中均采用线性网络编码作为其码构造方式。图2.4 所示 的节点W对输入的信息 b1 和 b2 进行的模二加操作，就是一种最简单的线性网络 编码操作方式。 2.62.6 网络编码的应用网络编码的应用 虽然网络编码提出的初衷是为改善组播传输网络中数据分发系统的传输性能， 但随着研究的不断深入，网络编码表现出了越来越广泛的应用前景。目前，网络 编码与覆盖网络（O
15、verlay Network）和无线网络（Wireless Network）等相结合 的研究取得了重要的进展，被认为是网络编码最有可能被首先应用的领域。 1、数据分发 网络编码最直接的应用就是数据分发，尤其是大范围的数据分发。前面讨论 的基于组播网络的数据分发，均是网络编码最典型的应用。Chou 等最早将随机网 络编码付诸实施，构建了一个可实用化的网络编码数据分发系统，并在 Washington 大学的 Rocketfuel 项目所获得的几个 ISP 骨干网络拓扑上进行了 仿真，取得了较好的传输性能。CodedStream 也是在网络中较早进行了基于网络 编码的数据分发的尝试71，CodedS
16、tream 是一个基于 P2P 模式的，面向高带宽 流媒体的数据分发系统。它按照编码网络分发数据的特性，在覆盖网络上构建一 个 K-redundant 路径图作为网络拓扑，网络编码被用于图中“瓶颈”处的数据分 发。最初的 CodedStream 在自己的仿真平台上进行了测试，其后续研究将整个思 想进一步扩展，并利用 PlanetLab 平台进行了更广泛的测试。 网络编码与应用层组播（Application Layer Multicast，ALM）相结合也取 得一定进展。应用层组播中的数据分发由客户端主机实现的，端主机具有一定的 计算能力，这为网络编码提供了良好的应用环境。而且，应用层组播利用的覆盖 中北大学 2013 届毕业设计说明书 第 12 页 共 57 页 网络拓扑可以按需变化，这也恰好可以利用网络编码对动态网络适应性强的优势。 Y. Zhu 给出了一个基于网络编码的应用层组播的完整实现。通过对比测试，证明 了基于网络编码的应用层组播在网络吞吐量、资源利用率等方面的性能要优于网 络层组播和普通的应用层组播。但是在传输迟延和信息冗余等方
