【大学课件】信息通信专业 Wireless Mesh Networks.ppt

Wireless Mesh Networks,Wireless Mesh Networks的概念,无线网状网（Wi-Mesh Network,WMN）是一种新的无线接入方案，它是无线局域网（WLAN）的扩展和延伸。典型的WMN包括两类节点：mesh 路由器和mesh 客户端。其中mesh路由器的移动性很小，它们组成了WMN的主干网络，为mesh 客户端和普通客户端提供接入服务。mesh客户端可以是静止的也可以是移动的，能够自己组成网络也可以与mesh路由器一起组成网络。,根据节点功能的不同,可将无线Mesh网络分为三种典型结构:,骨干网(Infrastructure/Backbone WMNs)客户网(Client WMNs)混合网(Hybrid WMNs)。,WMN骨干网示意图,WMN客户网示意图,WMN混合网示意图,WMN的特点,节点以无线方式互连，通过具有网关功能的节点接入Internet支持Ad Hoc网络，具有自组织、自配置、自修复功能 移动性:不同类型的网络节点具有不同的移动性（MR一般具有很小的移动性,而MC则可为固定节点或移动节点）能量约束:不同类型的节点具有不同的能量约束（MR通常不以电池为动力,所以不需要考虑能量约束,而MC则需要运行一种能量使用效率较高的路由协议）与现有无线网络兼容并能协调工作,WMN的应用,宽带家庭网络社区网络、企业内部网络 城域网运输系统、建筑物自动控制医疗系统、安全监督系统突发事件中构建临时网络,WMN和ad hoc的比较,在WMN中，所有的数据最后都要通过网关进入Internet，而Ad hoc中数据流可以在任意节点之间传输 Ad hoc网络由移动节点组成，一般不包含静止的节点或设备，而mesh网络的主干节点是静止的 Ad hoc网络拓扑结构处于不定状态，变化大，而mesh网络的拓扑结构只在出现链路干扰、节点加入或退出时才发生变化 设计目的不同，Ad hoc网络是为了实现用户节点之间的交互通信，而mesh网络更侧重于用户节点的接入功能,WMN的路由问题,WMN是移动Ad Hoc网络的一种特殊形态,它继承了Ad Hoc网络的特点,具有自配置、自组织与自管理等特性,所以部分传统的Ad Hoc网络路由协议在WMN中仍然可用,但需要在WMN路由协议设计中考虑其特殊性,WMN路由应考虑的因素,路由判据 负载均衡 路由容错网络容量 QoS保证,我们组对WMN的几方面的调研,（一）路由（二）与ad hoc有关的mac层技术（三）联合信道的分配和路由（四）基于IEEE 802.11的多信道无线Mesh网(WMN)的结构和算法（五）干扰检测和服务质量路由,WMN路由研究现状,多射频链路质量源路由协议MR-LQSR 一种可以感知信道状况的路由协议（由Gautam Kulkarni等人 提出）一种多信道路由协议MCRP ROMER（Resilient Opportunistic Mesh Routing for Wireless Mesh Networks）,（一）多射频链路质量源路由协议MR-LQSR 的介绍,MR-LQSR（Multi-Radio Link-Quality Source Routing）是微软公司研发的多信道WMN 路由协议,采用一种新的路由性能判据,称为加权累计传输时间WCETT。WCETT 综合考虑了带宽等链路性能参数以及最小跳数等因素。因此该协议能在吞吐量与延时之间获得一种平衡。,期望传输次数ETX,ETX（Expected Transmission Count）考虑了无线链路丢包对于寻路的影响用来发现具有较大吞吐量的通道。对于丢包率较高的链路，成功发送数据包所需重发次数较多，因此具有较大的ETX。在发现具有较大吞吐量的路径方面，ETX优于最小跳数判据，但是，它也许会选择带宽较小但丢包率低的链路。,如果用s(k)表示报文在尝试k次后成功传输的可能性（也就是说前k-1次是不成功的，第k次是成功的），则有：,那么成功发送数据包需要经过重传次数的期望值为：,一条路径的metric值就是该路径上所有链路的ETX值的和。路由协议选择具有最小metric值的路径,考虑到链路速率的不同，Draves11提出了ETT（Expected Transmission Time)，作为对ETX的改进。链路l的ETT值是这样定义的：在链路l上成功传输一个数据包所要经历的MAC层持续时间的期望值。一条路径的权值就是该路径上所有链路的ETT值的和 链路l的ETT值同ETX的关系为：,其中：,表示链路l的传输速率，s表示数据包大小。这个定义没有引入等待无线信道花费的时间，只是反映了实际使用信道的时间。,通过把bl引入到路径的权值表达式当中，ETT能够获得链路容量对路径性能的影响。,如果我们把记为 链路i的期望传输时间，对于一个n跳的路径，它的WCETT为：,然而，我们希望WCETT能够考虑到信道差异的影响。简单地把各跳的ETT值加起来不能满足这个特性，因为上面的公式不能反映出在不同信道上的各跳的差异。为了反应出这一因素，我们需要上面公式中添加额外的项。,我们假设同一路径上使用相同信道的两跳链路总是会相互干扰对方。这个假设对于短路径通常是真实的，但对于很长的路径干扰较小。考虑一个n跳的路径，假设系统总共有k个信道，定义为：Xj表示在信道j上传输时间的和。路径上总的吞吐量受瓶颈信道的限制，即最大的Xj。如果只考虑这一个因素的话，可以把WCETT简单地定义为：,(1),(2),我们可以把公式（1）和公式（2）所描述的特性结合起来，取它们的加权平均：其中，是一个可调参数，且01。有两种方法可以解释公式（3）所定义的WCETT的表达式 第一，我们可以把它看作是整体利益与自私行为之间的一种权衡。第二，我们可以把公式（3）看作是吞吐量和延迟之间的一种权衡。,(3),（二）多跳移动Ad Hoc网络的带功率控制的多信道MAC协议,Mesh 是Ad Hoc的超子集那么很多Ad Hoc的一些算法和协议同意适合WMN或者是对WMN是有重要价值的。所以由于WMN现在还不成熟，我们有必要对Ad Hoc的各种技术进行进一步的研究。,在移动Ad Hoc网络（MANET）中，一个基本的问题就是MAC，就是如何有效地利用无线频谱来解决移动主机使用媒体时潜在的争端和冲突。把多信道和功率控制结合起来。就能很好的解决这个问题。,应遵循的原则,1，遵循“on demand”原则来分配信道给移动主机；2，信道数与网络拓扑结构和层次无关；3，它适应主机移动并且可以调节；4，不要求任何形式的始终同步，相反地，大多数现有的协议分配给每个主机一个静态的信道即使它并没有接入去传送；5，功率控制是用来开发频率的再使用。功率控制也可以用来延长电池寿命和减少信号干扰。,带功率控制的MAC协议带来的好处,1，便携式设备宝贵的电池能够支持更长的时间。2，它可以降低邻居主机的旁信道干扰（例如，CDMA系统中严重降低网络吞吐量的远近问题就可以用功率控制来明显改善）。3，它可以提高物理区域的信道复用。,（三）联合信道的分配和路由,高效的信道分配方案可以显著的减轻相邻传输的干扰，高效的路由方案可以显著的降低在连接到Internet上的网关上的冲突。在WMN(Wireless Mesh Network)中，由于其拓扑结构很少变化，且每个接入点服务的移动客户，所以假定其是固定的。我们下面介绍的这种算法就是建立在这种假设上的。,如图figure 1所示是一个四点的mesh network。我们定义这样的一个图，用一个节点t来代表有线网络，用来代表其中的mesh router，用来代表u有的接口。定义这些节点中有网关功能的节点集合为。我们假设对于同一节点的不同接口对应不同的信道（防止干扰）。对于一个节点来说可以使用的信道号集合我们定义为。对于单一节点的流量负担，我们定义为(根据前面的假设，我们认为它是定值)。,我们定义为一个节点传输的最大距离，而是引起干扰的最大距离。两个节点u,v，如果它们之间的距离时，且中有相同的信道号时，两者之间就可以进行传输，在两节点间建立一条边，定义为其中一条信道的最大传输速率。这里再定义对边e有干扰的边集合为。我们的目标是尽可能的使最大，让每个节点上有的吞吐量可以被路由到Internet上。这里我们定义为边e上，信道i上的传输速率。为了减少干扰，我们还可以将发射分成时隙，（将会互相干扰的传输错开时隙）。,（四）基于IEEE 802.11的多信道无线Mesh网(WMN)的结构和算法,尽管在2.4-5GHz频谱中存在多发性非重叠信道,但现在大多数基于IEEE 802.11的多跳ad hoc网仍采用单信道.不能充分利用信道的带宽.因此,我们建议多频道无线Mesh网络结构,每个网络节点具备多种802.11网络接口卡.,无线mesh网络结构,无线mesh网络算法,(1)负载平衡路由算法 作为直接连接在有线网络的WMN的数据流通,任一WMN节点需要覆盖一条连接单个or多个有线网关节点.每一个有线网关节点都是生成树的根,而每一WMN节点都试图连入一个or多个生成树.,(2)分布式已知负载信道分配算法,信道分配算法必须满足如下限制:1,不同频道中分配的WMN节点数和NIC数目相同;2,2个直接通信的节点必须至少有1条相同的信道;3,必须限制一无线电信道的最初容量在干扰区域中的部分;4,非混叠无线电信道数目必须固定.,(3)虚拟控制网络:,和单信道mesh网络不同,多信道WMN的节点可能不和它的物理邻居共享任何相同的信道.一个简单的做法就是在每个节点增加一个控制网卡,使它利用同一信道,路由所有的控制流量,如控制网络上的广播信息.如Fig.4所示.,(4)错误恢复:,当一个节点发生错误时,节点就失去了和有线网络的连接.WMN重新组织网络的结构,绕过错误的节点.如下图所示:当检测到错误的父节点后,每个子节点发一个”join”信息给备份的父节点,并再次和有线网重新建立连接.,（五）干扰检测拓扑控制和服务质量路由,相对于单信道通信，多信道可以减小干扰的影响，所以在无线网络应用多信道可以显著改善网络的吞吐量。不同的信道分配可以形成不同的拓扑结构.我们在联合信道干扰上做了新的定义.并且基于这个概念,我们正式定义了最小干扰存在拓扑控制(INSTC),来寻求一个拓扑结构,它能够在所有K-连接的拓扑中干扰最小.然后阐述了给定网络拓扑结构情况下的带宽检测路由(BAR)问题,在有带宽要求情况下寻找服务质量连接请求的路由.我们在通信需要是分裂的假设下,提出了一种多项式最优时间算法来解决BAR问题.,我们阐述了多跳QOS路由内流量和互流量争用的影响,特别在多信道多NIC多跳无线网络.为了解决BRA问题,我们在通信需要是分裂的假设下,提出的QOS路由算法是一种最优基于LP多项式的算法.在不需要假设分裂的情况下,我们还提出了一种有效最大化瓶颈负载的方法.最终仿真证实了算法可以和好得提高系统性能.,参考文献,IanF Akyicdiz Udong Wang Weilin Wang Wireless mesh network:a survey 2005Richard Draves,Jitendra Padhye,Brian Zill.Routing in Multi-Radio,Multi-Hop Wireless Mesh Networks.ACM Mobicom,2004 Yu-Chee Tseng Shih-Lin CHih-YyLin and Jang-Ping Sheu A Multi-Channel MAC Protocol with Power Control for Multi-Hop Mobile Ad Hoc Networks 2001 Mansoor Alicherry Randeep Bhatia Joint Channel Assignment and Routing for Throughout Optimization in Multi-radio Wireless Mesh Nerworks 2005 Ashish Raniwala Tzi-cker Chiueh Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Mesh Network Jian Tang Guoliang Xue and Weiyi Zhang Interference-Aware Topology Control and Qos Routing in Multi-Channel Wireless Mesh Networks 2005,