无线网状网络.ppt

《无线网状网络.ppt》由会员分享，可在线阅读，更多相关《无线网状网络.ppt（79页珍藏版）》请在三一文库上搜索。

1、无线网状网络,Wireless Mesh Network（WMN）,无线用户接入因特网的途径,蜂窝移动通信网络 通过2G的GPSR技术或3G网络 覆盖范围广 建立基站的代价高，用户上网费用高，带宽低 无线局域网（802.11） 带宽高，组网成本低 覆盖范围小,无线用户接入因特网的途径（续）,宽带无线网络WiMax,无线用户接入因特网的途径（续）,无线网状网在自组网基础上发展起来，希望结合移动通信网和无线局域网的优点。 无线网状网利用无线mesh路由器建立大范围无线骨干，为各种有线与无线用户提供多跳无线接入，被认为是下一代无线网络的关键技术。 WMN可能的应用包括无线宽带服务、社区网络、实时监视

2、系统、高速城域网等。,1. 无线网状网的组成,Mesh路由器： 具备mesh组网能力，相互之间通过无线链路形成多跳网状网络，构成mesh骨干。 具备作为网关/网桥的路由能力，允许其它网络接入。 Mesh客户： 可直接接入mesh路由器，mesh客户之间也可通过无线链路形成多跳网状网络。 硬件平台和软件比mesh路由器简单得多。,2. 无线网状网络的结构类型1,架构/骨干式（Infrastructure/backbone WMN）,无线mesh网络的结构类型（续）,对等式WMN,无线mesh网络的结构类型（续）,混合式WMN,WMN的特性（混合式）,虽说是一种多跳无线网络，但有一个无线骨干，通过

3、无线骨干很容易支持终端节点的移动。 Mesh路由器较少移动且专门执行路由与配置功能，大大减轻了mesh客户与其它终端节点的负担。 可集成包括有线网络和无线网络在内的异构网络，支持多种类型网络接入。 mesh路由器通常不移动且有持久的电源供应，mesh客户则一般是移动的且由电池供电。 WMN并不是独立运行的，需要与其它无线网络相兼容和互操作。,3. 一个架构式mesh网络的实例 MeshCluster2,中继节点： 中继接口：构造mesh主干； 接入接口：允许mesh客户接入； 网关节点： 中继接口：构造mesh主干； 因特网回程接口：接入因特网。,AODV-ST路由协议,AODV-spanni

4、ng tree是一种混合路由协议： 采用主动策略维护中继节点到每个网关节点的最佳路由，减小中继节点和网关节点之间的路由发现延迟； 采用按需路由发现策略建立中继节点之间的路由。,4. WMN的关键设计要素1,无线技术 有向和智能天线、MIMO系统、多射频/多信道系统、可重配置无线电、认知无线电、软件无线电等。 高层协议需要进行革命性的设计，尤其是MAC层和路由协议。 可扩放性 从MAC层到应用层的所有协议都必须是可扩放的。 网状连接 拓扑认知的MAC和路由协议可极大提高网络性能。,WMN的关键设计要素（续）,宽带和QoS 必须考虑延迟抖动、集合吞吐量、每节点吞吐量、丢包率等更多性能参数。 安全

5、针对无线局域网提出的安全方案不能适用于WMN。 易于使用 所设计的协议必须使得网络尽可能自治，要开发有效的网络管理工具。 兼容性和互操作性 mesh路由器应能够集成异构无线网络。,5. 研究现状及挑战1,网络容量的理论研究 通信协议栈 网络管理 安全 跨层设计,5.1 网络容量的理论研究,3研究了无线自组网容量的理论上界和下界，据此给出了提高自组网容量的指导性方针。 3的分析方法推动了无线网络容量的研究，但存在两个缺点： 采用的模型较为简单，没有考虑网络协议的影响; 网络容量的理论边界是基于渐近分析得到的，不能反映出给定规模网络的确切容量。 分析结果能否应用于WMN还有待研究。,5.2 通信协

6、议栈物理层,先进的物理层技术 利用不同调制技术与编码速率的组合支持多传输速率，从而可为上层应用提供自适应容错能力。 支持高速传输的正交频分多路复用（OFDM）技术和超宽带（UWB）技术。 提高信道容量和信道可靠性的多天线系统，如天线分集、智能天线、多输入多输出（MIMO）系统等。 可获得更高频谱利用率和可行频率规划的频率捷变无线电（frequency-agile radios）或认知无线电（cognitive radios），这些技术可动态捕获未占用的频谱。,物理层的开放问题,还需要除OFDM和UWB之外的新的宽带传输技术； 多天线系统的复杂性和代价还太高，无法被大规模商业化； 认知无线电技术

7、还在发展初期； 允许高层协议访问或控制的物理层组件，软件无线电应是一种很有前景的技术。,通信协议栈MAC层,WMN与经典无线网络MAC层的主要差异在于多跳通信、多点-多点通信。 WMN的MAC层协议可工作在单信道或同时工作在多个信道上。 WMN的MAC层协议分为： 单信道MAC协议 多信道MAC协议。,单信道MAC协议,修改已有的MAC协议：只能获得较低的端到端吞吐量。 跨层设计： 基于有向天线的MAC协议：可消除暴露节点，但会产生更多的隐藏节点；且面临成本、系统复杂性、快速操控有向天线的实际问题。 具有功率控制的MAC协议：使用较低的传输功率，减少暴露节点，但隐藏节点问题可能变得更糟糕。 提

8、出新的MAC协议：重新回到基于TDMA或CDMA来设计MAC层协议很有必要，但到目前为止几乎没有供WMN使用的TDMA或CDMA MAC协议。,多信道MAC协议,多信道单收发器MAC协议： 每电台一个收发器，每个节点任一时刻只能工作在一个信道上，但不同节点可同时工作在不同的信道上，需要相应的MAC协议。 多信道多收发器MAC协议： 一个电台有多个并行的射频前端芯片和基带处理模块，可同时支持几个信道，但只需要一个MAC层模块协调多个信道的活动。到目前为止，尚没有提出针对WMN的多信道多收发器MAC协议。 多电台MAC协议： 一个节点有多个电台，每个电台有自己的MAC层和物理层，电台中的通信完全是

9、独立的。在MAC层上面需要一个虚拟MAC协议来协调所有信道中的通信。,MAC层协议的开放问题,可扩放的多信道MAC协议。 MAC/PHY跨层设计：可利用先进物理层功能的MAC协议。 MAC层上的网络集成： MAC层上必须开发先进的桥接功能，以使不同的无线电台（如IEEE 802.11、802.16、802.15等）可以无缝地一起工作。,通信协议栈路由协议,一个最佳的WMN路由协议必须具有以下特性： 使用多种性能测度：仅用最小跳数作为路由性能测度是不够的。 可扩放性：WMN的无线覆盖范围很大，扩放性很重要。 健壮性：为避免服务中断，WMN对于链路失效或拥塞必须是健壮的，另外还需要执行负载均衡。

10、Mesh架构上的有效路由：mesh路由器极少移动且没有能量限制，其路由协议应比移动自组网中的路由协议简单得多；有了mesh路由器提供的mesh骨干，mesh客户的路由协议也可以设计得比较简单。,已有研究工作,可采用各种性能测度的路由协议：有人研究了不同的路由测度对多跳无线网络路由的影响；实验发现，对移动节点采用最小跳数路由最好，对静止节点则不然。 多电台路由：每个电台被调谐到互不干扰的信道上，同时考虑链路质量测度和最小跳数测度，在延迟和吞吐量之间取得了较好的折衷。 多路径路由：在源节点和目的节点之间选择多条路径，以实现平衡负载和提高容错性，这种方法的性能取决于源节点和目的节点之间是否存在节点分

11、离的路径，且复杂性较高。 层次路由：主要基于对节点进行分簇，节点密度较大时可取得较好的性能，但维护层次结构的复杂性可能损害路由协议的性能。 地理路由：根据节点位置进行路由，对拓扑改变的适应性较好。,路由协议的开放问题,扩放性： 分层路由协议由于自身的复杂性和管理难度，只是部分地解决了扩放性问题。 地理路由协议依赖于GPS或类似的定位技术，增加了WMN的代价和复杂性，且位置服务是一个难点。 更好的性能测度： 需要提出新的性能测度，并能将多种性能测度集成到一个路由协议中以获得最佳的整体性能。 路由/MAC跨层设计： 仅仅交换参数是不够的，合并MAC协议和路由协议的某些功能是一种很有希望的方法 有效

12、的mesh路由： 针对WMN中的mesh骨干研究简单和有效的路由协议。,通信协议栈传输层,可靠的数据传输（TCP增强或新的协议）： 区分非拥塞性丢包：使用反馈机制区分不同原因引起的丢包。 检测链路失效：检测链路失效以增强TCP的性能。 网络不对称：使用ACK过滤和ACK拥塞控制等方法解决网络不对称的问题。 RTT变动范围大：由于节点移动、链路质量时变、流量负载波动和其它因素的影响，路径可能频繁发生并引起较大的RTT变动。 全新的协议：如专门针对自组网提出的ATP协议，但WMN要与因特网及其它许多无线网络互连，WMN的传输协议必须与TCP兼容。 实时交付： 没有用于WMN的速率控制协议。,传输层

13、上的开放问题,网络不对称的跨层解决方案 自适应TCP 自适应速率控制,通信协议栈应用层,WMN支持的应用有以下几类： 因特网访问 分布式信息存储和共享：指用户在WMN内部进行的信息存储和共享。 跨越多个无线网络的信息交换,应用层上的主要研究方向,改进已有的应用层协议：适应不完美的低层协议。 为分布式信息共享提出新的应用层协议 为WMN开发新的应用,5.3 网络管理,移动管理 mesh客户在不同mesh路由器之间的切换、连接的迁移等，需要多层移动管理方法。 有效的位置服务算法。 功率管理 mesh路由器利用功率管理控制连通性、干扰、频谱空间重用和网络拓扑 mesh客户通过功率管理节能 WMN要求

14、可同时优化功率有效性和连通性的功率管理方案。 网络监视 有效传输网络监视数据的方法，可准确检测网络异常和迅速获得多跳mesh网络拓扑的数据处理算法。,5.4 安全,WMN很容易遭受来自各个协议层上的攻击，而至今尚无有效和可扩放的安全解决方案。 需要研究分布式的鉴别、授权和安全的密钥管理方法。 设计和实现一个实用的安全系统，包括跨层安全网络协议和各种入侵检测算法，,5.5 跨层设计,MAC、路由和传输层协议需要与物理层一起互动地工作。 具体的跨层设计方法有待研究。,5.6 结论,WMN的性能远低于预期，许多问题需要解决，最重要和最迫切的是扩放性和安全性。 基于现有的MAC、路由和传输协议，WMN

15、的性能对于节点数量和跳数没有扩放性，需要为WMN研究新的MAC、路由及传输协议。 目前的安全方法可能对特定层上的特定攻击有作用，需要能够预防或对付所有层上攻击的综合机制。 目前的WMN只能部分实现自组织和自配置。 WMN集成异构无线网络的能力还非常有限。,6. 无线网络容量研究3,考虑两种类型的网络： 任意（arbitrary）网络：n个节点任意放置，每个节点任意选择一个目的节点，以任意速率和功率水平发送数据。 随机（random）网络：n个节点随机均匀分布，每个节点随机选择一个目的节点（与随机选择位置最近的节点）与之通信，所有节点是同构的（有相同的通信距离）。 考虑两种通信干扰模型： 协议模

16、型（protocol model） 物理模型（physical model）,6.1 任意网络,协议模型： 令Xi表示一个节点的位置（也表示节点本身），假设节点Xi在第m条子信道上向节点Xj发送，那么当在同一个子信道上同时发送的其它节点Xk满足以下条件时，Xj能正确接收： |Xk - Xj|(1+)| Xi - Xj| 0可以是协议规定的一个保护区，以防止邻近节点在同一个子信道上同时发送；也可以允许节点的传输范围有一定程度的误差。,物理模型,物理模型： 令Xk; k为在某个时刻、在一个特定的子信道上同时发送的节点集合，令Pk为节点Xk选择的发送功率水平，那么当满足以下条件时，节点Xi的发送可被

17、节点Xj正确接收： 为成功接收所要求的最小信噪比，N为环境噪声功率，信号功率随距离r指数下降，衰减指数通常假设大于2。,传输容量,比特-距离乘积： 在一次成功的一跳传输中，当一个比特朝着目的节点前进一米时，称网络传输了一个比特-距离（bit-meter）。 给定时间和空间上的一组成功传输，其比特-距离乘积之和是对网络传输容量的指示。,协议模型下的实验结果,以下结果假设n个节点任意分布在1m2的圆形区域上，每个节点的传输速率为W bits/sec。 网络最大传输容量： 如果节点位置、流量模式及每个节点的发送功率都是最佳选择的，则该任意网络的传输容量为： 上界为： 节点最大传输容量： 如果网络最大

18、传输容量在n个节点间平分，则每个节点的最大传输容量为： 若距目的节点1m，则每个节点可获得的吞吐量为：,物理模型下的实验结果,网络最大传输容量： 当满足Pmax/Pmin时，传输容量上界为：,6.2 随机网络,假设所有节点的传输距离均为r。 协议模型： 节点Xi在第m条子信道上向节点Xj发送，当满足以下两个条件时，Xj能正确接收： 1）| Xi - Xj| r 2）在同一个子信道上同时发送的其它节点Xk满足： |Xk - Xj| (1+)r,物理模型,所有节点的发送功率均为P。 物理模型： 令Xk; k为在某个时刻、在一个特定的子信道上同时发送的节点集合，那么当满足以下条件时，节点Xi的发送可

19、被节点Xj正确接收：,实验结果,协议模型下，每个节点可获得吞吐量： 物理模型下，每个节点可获得吞吐量：,6.3 讨论,本质上说，相邻节点共享信道的需要限制了无线网络的容量。 每个用户可获得的吞吐量随用户数量增加而趋近于零，因此， 无线网络只应当包含少量用户 多数传输只应发生在邻近区域，只有少量长距离传输（比如使用分簇结构），这样可以缩小源-目的距离。 本文未考虑由信道接入、节点移动、链路失效、路由等引起的开销，这些开销将进一步减小节点的吞吐量。 有向天线将有助于提高无线网络的容量。,7. WMN中的路由测度研究4,路由测度（routing metric）用来在所有可能的路由中确定一条最佳路由。

20、 路由测度的设计要根据目标网络的特性决定，WMN路由测度的设计要考虑以下两方面的因素： 所使用的路由协议：哪一类路由协议适合WMN，路由测度的设计应与路由协议相符合； Mesh网络的特性：静止节点 + 共享无线介质，有效的路由测度应考虑链路的信道分配，反映出干扰对路径性能的影响。,7.1 适合Mesh网络的路由协议,按需路由： 路由发现通常采用洪泛方法，适用于链路经常中断（如节点移动）的网络。 Mesh网络的节点是静止的，链路中断概率较低，基于洪泛的路由发现是冗余的。按需路由一般来说不适合mesh网络。 源路由（先应式路由）： 源节点为一个数据流计算路由，将整条路径放在包头中。 mesh网络的

21、包长通常很小，将整条路径放在包头中的消息开销很大。一般来说，源路由也不适合mesh网络。 逐跳路由（先应式路由）： 包头中的消息开销小，在网络路由中占据主导地位，也适合mesh网络。 逐跳路由的关键是要仔细设计路由测度以避免出现路由环路。,7.2 对路由测度的要求,路由测度不能引起频繁的路由改变，以确保网络的稳定性。 路由测度必须反映mesh网络的特性，以确保最小加权路径性能良好。 路由测度必须保证最小加权路径可以被多项式复杂度的算法找到。 路由测度必须保证不会形成转发环路。,路由稳定性,路由权重的稳定性与路由测度所反映的路由特性有关，分为： 负载敏感型：根据路由上的负载为路由分配权重，如拥塞

22、节点的个数； 拓扑依赖型：根据路由的拓扑特性为路由指定一个权重，如跳数、链路容量等。 路由测度适应的路由协议： 负载敏感测度：只适用于按需路由，在流量变化较大的网络中与先应式路由一起使用会导致网络不稳定； 拓扑依赖测度：可用于按需路由和先应式路由，Mesh网络较适合采用拓扑依赖测度。,最小权重路由的性能,路由测度必须能反映出影响网络性能的路径特性，路径特性有以下几种： 路径长度（跳数）：较多的跳数会增大端到端延迟和减少流的吞吐量，因此随着路径长度的增大应增加路径权重。 链路容量：随着节点间距离的增大，链路容量下降。应权衡路径长度和链路容量的关系。 包丢失率：重传会影响使用该链路的流的吞吐量和延

23、迟，因此路由测度必须反映链路的包丢失率。 干扰：路由测度必须同时反映流内干扰和流间干扰： 流间干扰：相邻数据流之间的干扰； 流内干扰：同一个数据流中相邻节点间的干扰。,流间干扰和流内干扰,流间干扰,流内干扰,计算最小权重路径的有效算法,研究表明，存在多项式复杂度的最小权重路由计算算法的充分必要条件是路由测度具有保序性。 保序性（isotonicity）： 在两条路径上添加相同的一段路径后，这两条路径的权重大小顺序不变。 Bellman-Ford算法或Dijkstra算法计算最小权重路径的充分必要条件为路由测度具有保序性。,无环路由,研究表明，如果在逐跳路由中使用Dijkstra算法，保序性是实

24、现无环转发的充分必要条件。 这意味着，对于非保序的路由测度，只能使用按需路由、源路由或距离矢量路由，因为这些路由协议不要求保序性来确保无环路由。 在mesh网络中应当使用保序的路由测度。,7.3 Mesh网络中使用的路由测度,Mesh网络中的路由测度应当是保序、拓扑依赖和能够反映mesh网络特性的。 针对WMN已提出了以下一些路由测度： 跳数 Expected Transmission Count（ETX） Expected Transmission Time（ETT） Weighted Cumulative ETT（WCETT） Metric of Interference and Chan

25、nel-switching（MIC）,（1）跳数,跳数反映了路径长度对流性能的影响。 跳数测度是保序的，存在有效的算法能够找到最小跳数的无环路径。 跳数测度没有考虑不同无线链路上传输速率和丢包率的差异以及网络中的干扰，在WMN中不能获得良好的性能。,（2）平均传输次数（ETX）,ETX定义为在无线链路上成功传输一个数据包所需要的MAC层传输次数的期望值。 路径的权重定义为该路径上所有链路的ETX总和。 由于长路径和易损路径具有较大的权重，因此ETX测度反映了路径长度和包丢失率的影响。 ETX是保序的。 ETX没有考虑干扰以及链路速率的影响。,（3）平均传输时间（ETT）,ETT定义为在无线链路

26、上成功传输一个数据包所需的MAC层传输时间的期望值，引入了链路传输速率的影响。 链路的ETX和ETT的关系如下（s为包长，b为链路的传输速率）： ETT = ETX * s / b 路径的权重定义为该路径上所有链路的ETT总和。 ETT测度反映了路径长度、包丢失率和链路容量的影响。 ETT是保序的。 ETT没有反映网络中的干扰。,（4）加权累积ETT（WCETT）,路径p的WCETT定义如下（Xj是路径p中信道j被使用的次数，maxXj为路径上同一个信道被使用的最大次数： WCETT测度在ETT的基础上考虑了流内干扰。 缺点： 没有显式考虑流间干扰； WCETT不是保序的，没有有效的算法计算最

27、小权重路径。,WCETT测度非保序的例子,（5）干扰和信道切换测度（MIC）,路径p的MIC定义如下： IRU是链路l上的传输所消耗的邻居节点信道时间的总和，反映了流间干扰，CSC反映了流内干扰。 MIC本身不是保序的，但可以转换成在虚拟网络上保序的MIC，从而可以在虚拟网络上使用有效的算法来计算最小权重路由。 仿真实验表明，MIC的性能最好（吞吐量高、延迟小、信道利用率大）。,8. 负载平衡26,无线Mesh网络中的负载平衡有三种方式： 基于路径的负载平衡： 将”接入路由器-网关“之间的流量分布到几条不同的路径上来提高网络性能和可靠性。 基于网关的负载平衡： 将与因特网交互的流量分布到多个网

28、关上。 基于Mesh路由器的负载平衡： 实现Mesh骨干网内部的负载平衡。,8.1 基于路径的负载平衡,备用路径路由（Alternate Path routing）改进传输性能的前提条件是： 存在不相交的几条路径 备用路径长度在可接受的范围内（不会导致延迟太大） 无线网络中的路径耦合尽可能小 衡量路由r1和r2之间耦合度的指标： 当r1上的一个节点发送时，r2上无法接收数据的节点的平均数量。,无线网络中路径耦合的例子,8.2 基于网关的负载平衡（1）,2采用的负载平衡策略： 提供接入服务的中继节点在其维护的生成树上，选择可获得最好性能（由路由测度决定）的网关作为缺省网关。 典型地，接入中继将其

29、产生的所有流量路由到缺省网关。 每个接入中继使用一个RTT探测工具监视到各个网关的最佳路由的质量，具有最小RTT值的网关被设为最小负载网关。 当接入中继检测到最小负载网关与缺省网关不同时，由该接入中继产生的新的数据流将使用最小负载网关作为它的因特网出口。,基于网关的负载均衡（2）,6允许每个节点将其流量平均分配到所有可访问的网关上，提出了两种调度方案。 方案一： 使用一个网络控制器，维护完整的网络信息，负责为每个节点选择到各个网关的最佳路由。 算法为每个节点-网关对维护k条最短路径。在每一轮迭代中，选择当前优先级最高的节点（节点的优先级等于剩余流量加转发流量），尝试为其分配当前最短路径；如果当

30、前最短路径上任何一条链路无法提供所需的容量（总流量的1/m，m为可用的网关数量），则尝试分配次短路径；分配成功后更新相关链路的代价（剩余容量），所有未分配最短路径的节点重新计算它们的最短路径。这个过程不断重复，直至为所有节点分配好最短路径。,基于网关的负载均衡（3）,方案二： 采用贪婪调度方法 假设节点到n个网关均有最短路径，跳数分别为h1、h2、hn, 则分配给网关i的流量为： Ti = (h1h2hn) / (h2h3hn + h1h3hn + + h1h2hn-1 ) * (1/hi ) 即较多的流量被分配给跳数较少的网关。 例如，若节点到三个网关的最小跳数分别为2、3和4，则它会发送1

31、2/26的流量给最近的网关，发送8/26的流量给次近的网关，发送6/26的流量给最远的网关。,8.3 基于mesh路由器的负载平衡,5在路由测度WCETT中引入负载因素，提出了WCETT-LB路由测度。 路径p的WCETT-LB定义为： WCETT-LB (p) = WCETT (p) + L (p) QLi为路径p上节点i的平均队列长度，bi是节点i的传输速率，QLi/bi称为节点i的拥塞水平。Min(ETT)是网络中的最小ETT，Ni是选择节点i为下一跳的节点集合，min(ETT)* Ni反映了节点i上的负载集中程度。 论文称WCETT-LB是保序的。,全局拥塞认知的路由方案,每个mesh

32、路由器定期计算自己的拥塞水平，超过门限时重新计算WCETT-LB，并向Ni中的节点广播更新的WCETT-LB。 收到WCETT-LB更新广播的节点再向以它为下一跳的节点广播，直至拥塞信息传播到接入路由器。 收到WCETT-LB更新消息的接入节点，重新计算一条最佳路径，计算最佳路径上的WCETT-LBbest。若WCETT-LBcurrent - WCETT-LBbest，切换到最佳路径上，否则继续使用当前路径。,例子,仿真实验结果,吞吐量,端到端延迟,9. 网关放置6,Mesh网络的设计涉及许多问题，网关放置是WMN设计的基本问题之一。 增加网关数量有助于提高网络性能，但每个网关必须配置因特网

33、接口，这使得网关（IGW）比普通mesh路由器（MR）成本高很多，节省网关数量也非常重要。 网关放置是一个复杂的问题，可以描述为一个约束优化问题。 6设计了能够反映WMN特性的网络模型，给出了网关放置的问题描述，并提出了求解这一问题的启发式算法。,9.1 网络模型与问题描述,每个MR配置有一个或几个无线接口； 具有几个无线接口的MR可以同时在几个不重叠的信道上与相邻的MR通信； IGW通过无线链路与相邻MR通信，通过有线链路连接因特网。,网络场景,网络模型,无向图G =（V, E），V = v1, , vn 是网络中n个节点（MR和IGW）的集合，其中m个是IGW，其余为普通MR，m (nm

34、) 。 每个MR节点（vi）配置一组射频无线接口，用(vi)=1, 2, , |(vi)| 表示，同一个节点的不同射频接口配置在不同的信道上。 集合CH = 1, 2, , c代表无线系统中c个不重叠的信道。 信道iCH上可能的数据速率用wi bit/s表示。 MR用于骨干连接的射频传输距离均为Rtran，当且仅当两个节点之间的距离小于通信距离时，它们之间存在一条边。E = e1, , ek为边集。 给定一个MR viV，其流量可能包括两部分：1）本地因特网流量Tl (vi)，由其服务区内的移动用户产生；2）中继因特网流量Tr (vi)，为其它MR转发的流量。 部署完成后，节点viV的物理位置

35、固定，每个节点都有持续的电源供应，IGW的有线连接及因特网带宽j是无限的，IGW成本比MR高。,问题描述,IGW放置问题定义为： 给定一个具有n个MR的网络，从中选择m个节点I = I1, , Im ，使得WMN能够满足每个MR的因特网流量需求（即Tl (vi)）。 IGW放置问题需要满足以下约束条件： 全覆盖：每个MR至少连接到一个IGW上（通过一跳或多跳路径）。 IGW的吞吐能力：网络中所有IGW的吞吐能力之和不小于网络中总的流量需求： MR的吞吐能力：通过一个M（vi ）R的流量不能超过它的吞吐能力： 共信道干扰（co-channel interference）：IGW和MR的吞吐能力受

36、干扰影响。 投资成本,干扰模型,理想链路模型： 如果路径的跳数不超过一个给定值，路径吞吐量不下降；超过该给定值，吞吐量为0。 基于跳数的吞吐量下降模型： 从MR vi到一个IGW的长为p跳的路径，为获得的吞吐量Tl (vi)，实际需要的吞吐量Tl (vi, p) 可用下式估算，其中为每跳多消耗的吞吐量比例： 基于碰撞的模型： 令Rint为一个信道的干扰范围（Rint Rtran），在这个范围内信道不能被重用，Wint为在该范围内使用信道的最大吞吐量。若使用多个正交信道，则Wint是在Rint范围内使用所有正交信道的最大吞吐量。,优化目标,最小化IGW的数量： 确定IGW的位置，使得用最少数量的

37、IGW提供足够的网络吞吐能力。 最小化MR-IGW的跳数： 研究表明，每个节点可获得的吞吐量为： 当使用多个信道时， 因此，IGW的放置应使得MR-IGW的平均跳数最小。 ）可承受的计算复杂度： 寻找IGW的最佳放置是一个NP难的问题。,9.2 WMN网络架构与IGW放置,为了有效部署WMN，提出了一些WMN架构，以下为6介绍的两种： IGW指向和连接的簇 以IGW为根的树,（1）IGW指向和连接的簇,一个IGW指向和连接的簇是一个连通图Clusteri = ( Vi, Ei )，其中Vi = Ii, v1, , vi， Ii是簇头，v1, , vi为MR，Ei = e1, , ei是指向IG

38、W Ii的边集。 IGW指向和连接的簇是一个有向图G，它具有以下特性： Clusteri为无环连通图，簇头为所选择的IGW； 每条边均从一个MR指向IGW； 每个MR通过一跳或多跳连接到IGW，一个MR可以有多条路径指向IGW； 给定n个节点的一个初始WMN，可以将网络划分成m个不相交的簇，每个簇的簇头为一个IGW，每个IGW有能力满足本簇内所有MR的流量需求。,图示,（2）以IGW为根的树,以IGW为根的树是一棵连通树，所有的边指向作为根节点的IGW。 基于树的WMN由以IGW为根的树组成。 寻找最小数目IGW的设计目标转化为寻找最小数目的以IGW为根的树，同时每个IGW能够满足树中所有节点

39、的流量需求。 前面的约束条件转化为： IGW吞吐能力的限制转化为对树的规模限制： 前两个干扰模型转化为对MR-IGW跳数的限制 中继负载的限制：,9.3 IGW放置的线性规划描述,参考文献,1 Ian F. Akyildiz, et, al. A Survey on Wireless Mesh Networks. IEEE Radio Communications. Sep. 2005. 2 Krishna N. Ramachandran, et, al. On the Design and Implementation of Infrastructure Mesh Networks. IEE

40、E workshop on Wireless Mesh Networks, 2005. 3 P. Gupta, and P. Kumar. The Capacity of Wireless networks. IEEE Trans. Info. Theory. Vol.46, No.2, Mar.2000. 4 Yaling Yang, Jun Wang, and Robin Kravets. Designing Routing Metrics for Mesh Networks. IEEE Workshop on Wireless Mesh Networks, 2005. 5 Liang M

41、a, and Mieso K. Denko. A Routing Metric for Load-Balancing in Wireless Mesh Networks. AINAW07, 2007. 6 Bing He, et, al. Optimizing deployment of Internet gateway in Wireless Mesh Networks. Computer Communications, 31(2008). 7 A. Raniwala, and T. Chiueh. Architecture and Algorithms for an IEEE 802.11-based multi-channel wireless mesh network. Infocom05. 8 S. Waharte, and R. Boutaba. Tree-based Wireless Mesh Network Architecture: Topology Analysis. MeshNets05.,