（信号与信息处理专业论文）无线mesh网络中网络编码感知机会路由技术研究.pdf

network coding aware opportunistic routing technology research in wireless mesh network thesis submitted to nanjing university of posts and telecommunications for the degree of master of engineering by shaoyuan wang supervisor: prof. wu meng april 2013 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。 南京邮电大学学位论文使用授权声明 本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索； 可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质 论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院办理。 涉密学位论文在解密后适用本授权书。 研究生签名：_ 日期：_ 研究生签名：_ 导师签名：_ 日期：_ i 摘要摘要 与有线网络相比， 无线网络， 尤其是无线 mesh 网络， 具有其独特的广播特性和时变特性， 这些特性为编码技术和机会路由技术的使用提供了平台，提高了网络的性能。越来越多的研 究集中在两种技术的结合使用方面，近年来，无线 mesh 网络中的网络编码感知机会路由技术 成为一个研究热点，但是现存的网络编码感知机会路由技术存在两方面的问题：一方面多数 研究集中在尽可能选取编码机会多的节点进行机会转发，当数据流量较大时有可能造成网络 拥塞等问题。另一方面对参与编码的数据包和机会转发节点要求越多越好，而在实际环境中 节点的处理能力有限，节点个数和参与编码的数据包越多越会增大节点的传输负担。 针对上述问题， 本文对 cope 方案进行优化， 实现无线网络中网络编码感知机会路由技术， 主要做了以下三个方面的研究工作：第一、提出基于路由优化的网络编码感知机会算法，该 算法中给出新的路由度量标准又称链路质量度量标准 lqm(link quality metric)，此标准在 编码机会，链路质量和链路的拥塞情况三种因素之间权衡，选取出具有高质量的节点作为转 发节点，从而提高网络性能。仿真结果显示，与 cope 算法相比，此改进算法在一定程度上提 高了网络性能；第二、提出基于编码优化的编码感知机会路由算法，该算法给出编码增益度 量来动态确定节点是否具有编码机会，并且通过计算数据包的编码机会值的大小选取最佳数 据包参与编码，实现对参与编码的数据包个数和转发节点的个数进行限制，对网络编码的实 现方式进行优化，从而降低编码实现的复杂度和编码造成的延时。仿真结果证明此改进算法 提高了网络的吞吐量和数据包投递率。第三、提出基于 cope 协议网络拓扑结构的编码机会探 测实现方法，此方法考虑了实际网络的特性，寻找到能够容纳最大流量的编码配置，仿真结 果证明此方法能够增加实际网络中的编码机会，提高编码增益。 关键词关键词: 无线无线 mesh网络，网络编码，机会路由，编码感知机会路由网络，网络编码，机会路由，编码感知机会路由 ii abstract compared to wired networks, wireless network, especially wireless mesh network, has its two characteristics including broadcasting and time-varying.and these features provide platform for the use of network coding and opportunistic routing. in recent years, network coding aware opportunistic routing technology in the wireless mesh network has become a hot research topic, but there are two issues about existing network coding aware opportunistic routing technology: the first one, most studies have focused on selecting nodes to take participate in the encoding as much as possible opportunities;the second one, they mainly require more data packet and opportunities forwarding node without regard of the limited capacity of nodes in a real environment in response to these problems, this article mainly did the research work of the following three aspects: firstly, it proposed the algorithm that is aim at optimizing routing and gived a new routing metrics,known as link quality metrics lqm (link quality metric), which considered coding opportunities, link quality and the congestion of the link into selecting a high quality nodes as a forwarding node.simulation results show that this improved algorithm can improve the network performances; second, it proposed a new algorithm based on code optimization by giving coding gain metric to dynamically determine whether a node having the encoding opportunities as well as by the value of coding opportunities of a data packet.these programes can limit the number of packets and forwarding the number of nodes so that reducing the complexity of coding . the simulation results show that this improved algorithm can improve network throughput and packet delivery ratio. third, it proposed a detection method by using the cope protocol, this method takes into account the actual characteristics of the network and finds the maximum flow rate of the encoding configuration, simulation results show that this method can increase the actual network coding opportunities and coding gain. key words: wireless mesh networks, network coding, opportunistic routing, coding aware opportunistic routing iii 目录目录 摘要. i abstract . ii 第一章 绪论 .1 1.1 研究背景 .1 1.2 研究现状及其意义 .2 1.3 论文的内容及安排 .6 第二章 无线 mesh 网络中的网络编码和机会路由技术.8 2.1 无线 mesh 网络 .8 2.1.1 无线 mesh 网络的组成 .8 2.1.2 无线 mesh 网络的抽象模型 .8 2.1.3 无线 mesh 网络的协议体系 . 10 2.2 网络编码在 mesh 网络中的实现技术 . 10 2.2.1 网络编码的编码实现 . 11 2.2.2 网络编码的解码实现 . 13 2.2.3 随机网络编码在实际网络中的实现 . 14 2.3 编码感知机会路由关键技术 . 15 2.3.1 备选转发节点集的选取 . 16 2.3.2 最佳转发节点的选取 . 16 2.3.3 备选转发节点之间的转发调度 . 17 2.4 网络编码感知机会路由在无线 mesh 网络中的实现机制 . 17 2.5 本章小结 . 19 第三章 基于路由优化的网络编码感知机会路由算法 . 20 3.1 引言 . 20 3.2 研究背景与现状 . 21 3.2.1 cope 协议方案的优势和不足 . 21 3.2.2 现有的路由标准 . 22 3.3 基于 cope 协议的网络编码感知机会路由改进算法 . 24 3.3.1 备选转发节点集的选取 . 24 3.3.2 节点编码机会的判断 . 25 3.3.3 确定转发节点的优先级 . 26 3.3.4 数据包编码的实现 . 29 3.4 仿真性能分析 . 29 3.5 本章小结 . 32 第四章 基于编码优化的编码感知机会路由算法 . 33 4.1 引言 . 33 4.2 网络编码优化的发展及现状 . 34 4.3 基于网络编码优化的改进算法 . 37 4.4 仿真实验分析 . 42 4.5 本章小结 . 44 第五章 基于 cope 通信模型的网络编码实现方案 . 45 5.1 引言 . 45 5.2 网络编码机会的定义 . 45 5.3 ocp-cope 算法的关键技术及实现机制. 46 5.4 仿真实验分析 . 50 iv 5.5 本章小结 . 52 第六章 总结与展望 . 53 6.1 本文的主要工作 . 53 6.2 研究展望 . 54 参考文献. 56 附录 1 攻读硕士学位期间撰写的论文. 59 附录 2 攻读硕士学位期间参加的科研项目. 60 致谢. 61 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 1.1 研究背景研究背景 当今社会，信息化日益发展，网络用户数量不断增多，对信息传输质量的要求也愈来 愈高，用户也迫切需要能够快速、准确地获取各种网络信息，如何在有限的无线带宽范围 内改善无线网络的传输性能，此问题已成为当今无线网络研究领域的重要课题之一。在此 背景下，各种信息技术、网络技术、通信技术、及多媒体技术的快速发展，为用户的生活 带来了极大的方便，无线网络领域已成为近年来通信与计算机领域迅猛发展的领域之一， 其快速发展为用户较高的网络业务需求提供灵活高效的网络支持1。本文研究的网络背景 是无线 mesh网络，我们首先介绍下无线 mesh网络的基本特征。 作为一种新兴的宽带接入技术，无线 mesh 网络(无线网状网)2既克服了 wlan 技术 的热点接入问题， 又拥有 adhoc 自组织网络3中移动节点的独立路由和主机功能,不采用基 站式的网络中心控制点而是采用分布式控制方式进行控制。网络中的每个无线节点可以既 是接入点又是路由器，且每个节点都能够发送信号也能够接收信号，并与一个或者多个对 等节点直接通信，与传统网络相比，无线 mesh 网络通常具有较短的无线链路长度，这样 不仅能够降低天线成本还能够降低信号的发射功率，进而降低不同系统之间信号的干扰和 系统自身信号的干扰，优化了无线链路设计，减轻了链路之间的干扰4。本文如无特殊说 明，则研究的网络背景均是无线 mesh网络，以下简称无线网络。 无线网络的设计一直都是以有线网络作为蓝本，在设计过程中，把有线网络抽象成点 对点的通信链路模型，并在此基础上将适用于有线网络的各种协议运用到无线网络环境之 中，例如，传统的无线网络路由协议借鉴有线网络中基于最短路径的路由协议，在节点选 取最佳路由后，对接收到的数据包不对节点存储的数据信息内容进行任何处理，仅进行存 储和转发操作，这种路由选取方式在有线网络中效果很好，但是对于无线媒质来说并不能 取得很好的效果5。这是因为无线网络中的传输媒质不同于有线传输介质，有线网络的链 路具有可靠性和可预测性，而无线网络的链路却有较高的误码率和时变性；更重要的是， 有线链路是单播链路，因此有线网络中不同链路的数据传输不会互相干扰，而大部分的无 线链路是广播链路，所以链路之间的干扰却是无线网络的固有问题；另外，有线网络中的 节点是静态的，而无线网络中的节点支持流动性和机会性6；传统的无线网络设计并没有 考虑自身的特性，因此其存在吞吐量较低，死角和不能够充分支持节点的移动性能7。最 南京邮电大学硕士研究生学位论文 第一章 绪论 2 初，无线通信网络的特性被认为是不利于网络中信息传输，许多学者提出的网络技术着重 于降低无线网络中广播特性的影响，这样使得无线网络的广播特性不仅没有被充分利用， 反而会造成传输路径上出现多条不可靠的链路， 影响链路的传输性能， 从而难以提供高速、 可靠的传输服务。无线网络的节点像有线网络节点一样仅对接收到的信息进行存储和转 发，这在实现网络传输的最大吞吐量和带宽的有效利用方面得不到很大的提高8。 一方面，无线网络的广播特性一个节点发送的数据包可能会被传输范围内的多个节点 同时监听，这多个节点组成转发节点集，成为潜在的下一跳转发节点，这被称为空间分集 技术，而在目前的网络设计中，大多数是发送数据包之前选择一条固定的路由9; 10。另一 方面，无线网络的广播特性造成各节点之间数据容易出现重叠，出现数据冗余问题。近年 来，如何充分利用无线网络的空间分集和数据冗余特性来提高网络的吞吐量成为一个研究 热点11-13。 1.2 研究现状及其意义研究现状及其意义 ahlswede 等人在 2000 年首次提出网络编码的概念14，网络编码主要利用无线通信网 络的广播特性和时变特性，在传统无线网络中中间节点拥有“存储转发”性能的基础上增 加了编码的功能。网络编码技术的核心思想是对中间节点接收到的多个信息进行编码融合 后发送传输，接收节点根据解码信息对编码数据进行解码，从而获取自己所需的信息，这 样就实现一次传输携带多条信息。无线网络的链路具有不可靠性和物理层广播特性，这些 特性为网络编码的使用提供了网络平台，在无线网络中应用网络编码技术迅速成为通信网 络技术领域的一个重要课题15。表 1.1 显示了网络编码技术的发展。 a rb x1x2 x2x2 x1x1 (a) arbx2 x2 x1x2 x1 x1x2 x1 (b) 图1.1 网络编码的基本思想 接下来我们用图 1.1 来阐述网络编码的主要思想， 图中节点 a 需要传送数据包 x1 到节 点 b，节点 b 需要传送数据包 x2 到节点 a，由于无线网络中传输范围的限制，两个数据包 在传输的过程都必须要经过中间节点 r，如果按照传统的路由协议，两个数据包的传输过 程如图 1.1（a） ，需要 4 次传输，节点 a 发送数据包 x1 到中间节点 r，r 再把 x1 发送到目 的节点 b，节点 b 发送数据包 x2 到 r，r 再把 x2 发送到其目的节点 a；相比较之下，利用 具有网络编码则只需要 3 次传输，具体过程如图 1.1（b） ，节点 a 发送数据包 x1 到 r，节 南京邮电大学硕士研究生学位论文 第一章 绪论 3 点 b 发送数据包 x2 到 r，r 对 x1 和 x2 进行异或编码，得到编码数据包 x1x2 后节点 r 将编码包广播发送到节点 a 和 b，a 和 b 获取编码包后利用自身缓存数据包对编码包进行 异或解码，从而获得各自所需数据包。与传统路由技术相比，网络编码使传输次数减少到 了 3 次，提高了网络容量。 网络编码技术有其独特的优越性，网络编码技术也已经被证明是可以逼近网络容量理 论传输极限的有效方法，可以显著提高改善负载均衡、节省节点能耗、增强网络鲁棒性、 减小传输延迟、提高网络吞吐量等性能。但是网络编码的这些优越性是以节点的复杂计算 和利用存储资源换取链路带宽利用率的提高为代价的，实际的无线网络中，网络节点的处 理能力有限，如何能够使网络编码技术与现有网络协议及机制完美结合和如何实现网络编 码优化成为一个新的研究趋势16-20。 无线网络中路由的设计是其关键性问题之一，传统的无线网络路由协议大都采用确定 性路由方式，其基本思想是：源节点在发送数据前首先确定一个固定的下一跳节点，然后 进行数据传输， 并且在整个传输过程中， 数据始终沿着此固定路由传输数据直至传送完毕。 如果传输过程中发生分组丢失或差错,则启动链路层重传。 传统的路由选择方式在有线链路 中能够保证数据传输的可靠性，但是在链路质量和稳定性较差的无线环境下,一方面，无线 链路的广播特性使得接收节点的多个邻近节点能够接收到相同的数据包,这在传统路由协 议中被认为是信号干扰，而忽视这些节点的机会性接收将会导致网络资源的浪费。另一方 面，动态变化的无线网络容易造成路由的中断和重新修复，有可能频繁地进行链路层的数 据重传，消耗大量的带宽资源，造成网络资源的浪费和节点能量的消耗，不适用于大规模 动态的网络环境。 为了充分利用无线信道的广播特性21和无线网络的空间分集特性，2004 年，麻省理工 学院(mit)的 biswas 等人首次提出了机会路由的概念22，与传统路由方式不同的是，它 是后选择路由方式。其基本思想是转发节点在发送数据前根据路由协议首先确定备选转发 节点集（下一跳集） ，不同的数据包从转发节点集中选择不同的节点作为下一跳来转发， 多条路径可以同时传输而不相互干扰，选择靠近目的节点的邻居节点进行每一次转发直至 达到目的节点，降低网络中的数据冗余，增强链路的鲁棒性。机会路由技术有两个特点： 1. 利用无线信道的广播特性和数据冗余，降低数据包的重传次数。 图 1.2 描述了这个特点，源节点 a 要发送数据包 x1 到目的节点 b，由于链路的衰落 特性，链路上有两个中间节点 r1 和 r2。各传输链路的丢包率如图所示。源节点 a 发送数 据包时，节点 r1 接收到数据包，节点 r2 和 r3 同时也监听到了数据包，如果依据传统路 由协议， 源节点 a 选择最短路径 r1 作为下一跳， 如果 r1 没有接收到数据包， 不发送 ack 南京邮电大学硕士研究生学位论文 第一章 绪论 4 确认包反馈给 a，则链路就要启动重传模式，要求源节点重新发送数据包，直到节点 r1 接收到数据包并成功发送 ack 确认包到源节点 a 为止。但是如果按照机会路由协议，选 择中间节点 r1，r2 和 r3 作为备选转发节点，并依据各节点到目的节点的距离分配优先 级，节点 r3 接收到数据包后，直接发送数据包到目的节点，节点 r2 和 r1 监听到 r3 已 经发送数据包则停止发送 x1，从而降低数据包重传次数，节省能量消耗。 ar1r2x1r3 0.80.8 0.8 0.5 0.5 0.3 b 图1.2 机会路由降低重传次数的思想 2. 利用无线信道的空间分集特性和广播特性，提高链路传输数据的可靠性 图 1.3 描述了机会路由如何提高传输链路质量的过程，源节点 a 发送数据包 x1 到目 的节点 b，节点 a 到中间节点的链路质量(发送成功率)为 20%，中间节点到目的节点 r1 b r2 r3 r4 r5 a 20% 20% 20% 20% 20% 100% 100% 100% 100% 100% x1 图1.3 机会路由的提高链路质量的特点 的链路质量为 100%，当源节点 a 发送 x1 后，如果按照传统路由方式，则数据包 x1 选择 其中一个中间节点进行转发，则中间节点接收数据包成功的概率仅为 20%，但是按照机会 路由方式，五个中继节点的任何一个接收到数据包都可以进行转发，则中间节点接收数据 包成功的概率变为(1-0.85)*10067.2%，提高了网络传输的可靠性，从而提高网络的吞吐 量。 机会路由的这个两个特点在无线网络中发挥了极大的优势，提高网络链路的鲁棒性 23。网络编码技术和机会路由技术是两个最新的通信技术，它们是两种不相关的技术，分 别在不同的网络条件下实现，网络编码是在高质量链路上体现极大的优势，而机会路由则 南京邮电大学硕士研究生学位论文 第一章 绪论 5 更适用于链路质量低，误码率较高和衰落大的低质量链路。但是两者有共同的目标就是通 过利用无线网络的广播特性降低数据信息的传输次数，提高网络性能。近年来，如何将两 种技术进行结合从而更大限度的提高网络吞吐量问题成为国内外学者研究的热点之一。 文献24提出了通信模型已知的情况下，考虑链路中网络编码机会来选择最佳路由的衡 量方式。这种方式一定程度上增加了链路上的编码次数，降低了传输次数，但是，这些方 案仅利用网络编码来选择固定最佳路由并没有考虑机会路由技术的实现。为了提高所选路 径中的编码机会，研究者提出的网络编码感知路由算法日益增多23; 25，在目前的网络编码 研究中，只有小部分研究提出优秀的方案实现了通过考虑链路中编码机会的次数来选择机 会路由转发备选节点实现两种技术的结合，并给出了理论分析和仿真实验结果给予说明 26-28。 自 katti 等人首次提出基于机会的网络编码在无线环境中的协议层面上具体实现的问 题的 cope 协议29后，无线网络中网络编码技术与机会路由技术的结合已经为越来越多的 研究学者所研究，并且取得了一些突破性的成果。无线网络物理层的广播特性、无线链路 的不可靠性、无线节点的发射功率特性等，使得两种技术更适合于无线网络，在此基础上 很多优秀的网络编码感知机会路由协议相继提出30-32。 cope 协议是一种提高无线网络单播 通信吞吐量的网络编码技术， 在一定程度上增加了网络中的编码机会， 提高了网络吞吐量， 但是此方案只是被动的等待编码机会的出现，且选择传统的固定路由方式进行数据的传 输，这种策略很大程度上限制了网络编码提高网络吞吐量的能力。more33协议首次实现了 将流内随机网络编码和机会路由进行结合，利用了标准 802.11mac 层的基本特性，实现在 路由层和 mac 层透明的情况下进行机会路由，独立于 mac 层，而且路由层和 mac 层的透 明使得 more 协议更易于向组播传输。 但是此协议在选择转发节点时并没有考虑编码机会， 只是将数据包进行线性编码后广播出去，在此基础上， core 协议34提出一个基于网络编码 感知的机会路由机制，弥补了之前协议中被动地利用各节点现有的编码机会的不足，此机 制结合了机会路由技术和局部流内网络编码技术，选择具有较大编码机会的节点作为下一 跳，从而使得分组总是尽量转发到编码机会多的节点上去，创造更多的编码机会，提高了 无线 mesh 网络的吞吐量。此机制的不足之处在于需要节点保持两跳邻居缓存队列内的分 组信息，增加了数据的复杂度，且在选择转发节点时没有考虑链路质量和拥塞程度，使得 所选转发节点因为编码机会多，传输更多的数据包而造成链路拥塞，如何在编码机会和所 选链路之间进行折衷也越来越多的被业界关注和研究35。 南京邮电大学硕士研究生学位论文 第一章 绪论 6 1.3 论文的内容及安排论文的内容及安排 目前为止，网络编码感知机会路由方面的研究及其应用仍然处于初级理论探索阶段， 大多数协议或者算法在网络理想状况下简化传输模型，对网络吞吐量、能量消耗、算法复 杂度等方面进行理论研究，且在编码感知机会路由策略中大多通过考虑节点的编码机会来 选择路由，而对实际的网络应用环境中存在的节点处理能力，能量消耗和链路质量考虑却 不足，针对这些问题，本课题对经典编码协议 cope 协议进行分析，进一步研究无线网络 中的网络编码感知机会路由技术实现，深入分析 cope 编码策略和路由策略，研究其技术 实现的关键因素，根据现存不足提出编码感知机会路由实现方案中的机会路由和网络编码 的优化方案以及在实际应用过程中的实用算法。本文主要网络环境是无线 mesh 网络即无 线网状网。本文内容安排如下： 第一章绪论部分，首先介绍了无线网络中网络编码和机会路由两种技术的研究背景和 意义，给出编码技术和机会路由技术结合的必要性，然后概述了有关两种技术结合的发展 现状及意义，最后给出本文研究的主要内容及其章节安排。 第二章首先具体描述了无线 mesh 网络中网络编码和机会路由技术实现的基本原理和 相关技术背景，其次介绍了网络编码感知机会路由在 mesh 网络实现过程中的关键技术， 为课题的研究实现提供了理论平台和拓展思路。 第三章提出基于路由优化的改进编码感知机会路由算法 or-cope(optimized routing-cope)，此算法以 cope 方案为基础，针对其被动的等待编码机会和当前研究主 要集中在选取编码机会多的节点作为转发节点这一不足，该改进算法中引入机会路由并进 一步分析给出一个新的备选转发节点选取路由标准 lqm(link quality metric)，该标准在节 点的编码机会，链路丢包率和发送队列的长度几个因素之间做出权衡，选择出性能较佳的 节点作为备选转发节点，文章给出改进算法的实现思路，最后仿真结果分析证明该改进算 法能够提高网络的性能。 第四章提出基于编码优化的编码感知机会路由的改进算法 oc-cope(optimized coding-cope)，此算法在 cope 协议随机网络编码策略的基础上，通过对数据包编码机会 的多少进行计算，选取具有最优性能的数据包参与编码，同时利用网络编码增益判定标准 动态判定节点的转发性能和链路质量，增加网络中的编码机会和转发效能，从而提高网络 性能，并通过仿真实验进行了分析验证。 第五章在网络编码感知机会路由的实用性方面进行创新，本章在网络编码技术的实用 性方面进行优化， 给出优化方案 ocp-cope(optimized communication patter-cope),此方案 南京邮电大学硕士研究生学位论文 第一章 绪论 7 利用 cope 协议实现通信模型，对实际网络进行通信模型的配置，主动寻找具有网络编码 机会的拓扑结构和通信模型， 使得网络编码技术适用于实际网络， 文章给出理论结果分析， 通过仿真进行验证。 第六章对本文内容进行总结概括，并对网络编码感知机会路由技术目前存在的问题和 前景提出一些自己的看法。 南京邮电大学硕士研究生学位论文 第二章 无线 mesh 网络中的网络编码和机会路由技术 8 第二章第二章 无线无线 mesh 网络中的网络编码和机会路由技术网络中的网络编码和机会路由技术 2.1 无线无线 mesh 网络网络 2.1.1 无线 mesh 网络的组成 无线 mesh 网络兼有无线局域网 wlan 和无线自组织网 ad hoc 网络的优点，由一些固 定的路由器和客户端构成的网状结构网络， 各用户节点通其相邻的其他已经接入的用户节点， 以多跳方式实现到骨干网的连接，路由器和客户端之间通过无线链路进行信号传输。新节点 可以也通过它周围的其他已入网节点方便地接入到网络，不需要中心节点的连接便可以实现 网络扩展，mesh网络的这个特性可以极大地减少网络建设成本。 无线 mesh网络通过多跳的方式实现与有线网络的连接， 减少了网络中热点的数量， 组网 方便灵活，便于维护，且增大了无线网络的覆盖范围和系统容量，因此在数据传输过程中具 有一定的冗余，独特的路由选择特性降低了局部链路对整体网络的影响，比如链路中断和局 部容量增加或者扩充对整体网络性能的影响有明显的降低，提高了网络的可靠性。 2.1.2 无线 mesh 网络的抽象模型 无论是网络编码技术还是机会路由技术都与所在的网络拓扑环境密切相关, 但是无线 mesh网络作为一个自组织网络，在实际环境中更为复杂，链路具有不稳定性和不可靠性，造 成在进行数据传输时信号衰落、不同信号之间会互相干扰等问题，使得网络技术在实际应用 的过程中遇到了困难，所以在对相关算进行仿真或者考虑时，会将实际无线网络进行抽象成 网络模型来分析算法的性能，以便更好的分析网络性能。接下来我们给出无线网络的定义及 抽象出来的模型结构。 网络模型定义：有向图 g = (v(g) , e(g)表示无线网络，其中 v(g)表示网络中所有的节 点，即网络节点集，包括源节点，中间节点和目的节点。e(g)表示网络中所有的链路，即网 络边集。在一个网络中，如果含有多个源节点和目的节点，则此网络是多源多播网络，如果 只有一个源节点和目的节点， 则此网络被称为单源多播网络。 网络中， e(g)中链路表示为 l(i , j )e(g)，即链路的方向是从始节点 i到终节点 j。l(i , j )的链路容量表示为非负数 c(i,j) ， 我们也可以使用网络流图来定义无线网络，图 2.1 是一个网络流图的例子， 南京邮电大学硕士研