一种多出口wimaxmesh网络组网方案

一种多出口wimaxmesh网络组网方案

1集中式调度模式通信网络中的反向网络是指连接到基站节点b和基站监视器（rc）的网络，包括直线和无线网络。在具体建设回程网络时,应考虑整个网络的吞吐量与QoS需求。根据蜂窝网的业务模型和用户渗透率即可计算出回程网络的容量需求。对于主要承载语音业务的2G网络,平均每基站的回程流量约几Mbit/s;对于3G网络,可以根据数据业务和语音业务的比例、用户渗透率、基站覆盖面积计算其回程流量。由于无线Mesh网络(wirelessmeshnetwork,WMN)具有以下优点IEEE802.16d标准定义了Mesh模式下的两种调度方式:集中式调度和分布式调度。在集中式调度方式下,MeshBS在调度过程中处于中心位置,并协调SS的接入问题。由于Mesh模式下没有独立的上下行子帧,BS和SS之间在通信过程中不必建立直接链路,而是可以通过中间SS中继来建立连接。在该调度模式中,BS和SS可以视为处于同一棵调度树中,BS处于调度树的根部。BS在确定链路的突发(burst)分配以及相关参数后,根据SS的请求统一调度安排网络资源。BS在MSH-CSCH消息中广播调度信息,在MSH-CSCF消息中广播各条链路的突发分配以及相关参数,各个SS节点根据MSH-CSCF消息中的调度树来进行链路更新。由于集中式调度机制中BS负责协调整个网络通信过程中SS之间的通信关系,因此在一定程度上可以避免碰撞问题,可有效解决SS对资源的竞争。但是,在集中式调度机制下容易出现以下问题:由于SS之间需要通过BS来进行通信,一旦BS与某SS之间无法建立连接将导致该SS无法与网络中其他节点进行通信;BS需要大量的额外开销来维护整个网络中节点的状态信息表;整个网络的通信效率较低;由于网络通信对于BS的过度依赖,BS必须保证工作的稳定性。在分布式调度方式中,网络中各个SS可以直接进行通信,这使得整个网络的通信效率大大提高,也有效规避了过度依赖BS带来的通信风险。依据在传输调度过程中是否存在碰撞现象,IEEE802.16d将分布式调度划分为协同分布式调度和非协同分布式调度。根据MSH-DSCH消息中特定位的比特值来标志调度类型:0为协调调度,1为非协调调度。在协同分布式调度中,控制子帧使用无碰撞的方式来传输调度包;而在非协同分布式调度中,传输调度包则采用竞争方式。IEEE802.16dMesh模式中的分布式调度是采用请求、答复和确认三次握手的方式来建立发送数据前的链接:首先由请求发送节点发送MSH-DSCH消息中的RequestIE来指明要发送数据的属性以及可用的时隙,然后目标节点则根据该请求寻找合适的时隙并回复请求节点数据的时隙位置;最后,请求节点收到目标节点回复后发送MSH-DSCH许可消息来完成链接的建立过程。通过以上分析可知,Mesh网络采用集中式调度方案更有利于保证QoS。本文将对基于WiMAX(IEEE802.16)的无线回程网络的容量提升问题进行研究。图1是目前研究WiMAXMesh网络的常用网络模型。在该网络模型里,各节点工作于WiMAX802.16的Mesh工作模式,MeshSS节点之间可以相互通信,MeshBS节点作为整个WiMAXMesh网络对外的单一出口。该网络模型的优点是概念清晰,便于建模与制定优化算法,不足之处是由于只有单个MeshBS作为网络出口,整个网络的容量因此受限,此外,如果该MeshBS发生故障,将影响整个网络的运行,无法满足实际生产环境对网络强壮性、容错性、高吞吐率等方面的需求。为此,本文提出了一种多出口的WiMAXMesh回程网组网方案和调度算法,以提高无线Mesh网络的吞吐量、强壮性和资源利用效率。仿真结果表明,本算法在这几方面性能均有显著提高。2meshs站的网络模型针对单出口网络的不足之处,本文提出了一种基于IEEE802.16d的WiMAXMesh组建回程网的新方案。假设回程网需要为n个基站承载业务,则可以为这些基站配备支持IEEE802.16d的无线网卡,令这些基站成为Mesh网络的MeshSS站;为了保证网络的容灾性和负荷分担,我们为该Mesh网络设置m(m≥2)个MeshBS作为对外连接的出口,网络模型如图2所示。由于采用无线Mesh网络作为回程网,这些MeshBS物理上可以与RNC合设。MeshBS通过无线网卡与MeshSS(MeshSS与基站合设)通信,同时还具备到SGSN、MSC网络以及其他MeshBS的高容量连接,包括有线、光纤或者微波等方式。图2是具有3个MeshBS的无线回程网络的例子。由于在本组网方案下WiMAXMesh网络有多个MeshBS与上一级网络相连,区别于以往只有单个MeshBS作为出口的情形,本文把这种组网称为多出口的WiMAXMesh组网。3多出口网络的资源调度算法在对本文所提出的WiMAXMesh网络进行最优化的资源调度时,不仅要确保在每个MeshBS所辖的MeshSS的范围内局部最优,还需要考虑当网络具有多个WiMAXBS时仍然保持全局最优,为此我们提出了一个支持多出口的Mesh回程网络的资源调度算法MEMSA(multiple-egressmeshnetworkschedulingalgorithm),以下将进行详细介绍。3.1meshs节点图3是一个随机生成的WiMAXMesh网络拓扑,图中包括了3个MeshBS和10个MeshSS节点。图中在两点之间的连线表示该连接点相互之间存在数据传输路径,也就是说在相互的无线物理传输范围内。3.2度量值的计算为了实现有效调度,需要合理构造整个Mesh网络的资源调度树。为了清晰起见,本文以路径的物理长度作为在计算调度树的边的长度的度量值(metric)。在实际应用本方案时,我们可以综合考虑各种因素,例如带宽、时延、价格、干扰等因素来计算度量值。我们在算法中为网络设置一个虚拟节点R3.3总体计算方法为了在相邻两个节点之间进行有效的无线传输,必须满足一定的信号干扰噪声比(SINR)门限,只有当SINR达到门限值时接收方才能成功接收信号。实际无线网络的SINR门限值与编码、调制、天线效率、信号功率、噪声干扰功率、传输距离等因素均有关系,而且这些因素在各个节点均有不同的值。在Mesh网络里,还要考虑调度算法、并发传输等因素对SINR的影响。为了简化模型,本算法以节点之间的传输距离作为判断节点之间无线传输是否可达的依据(实际应用时可以结合上述各项因素综合计算)。设Mesh网络由m(m>0)个MeshBS,n(n>0)个MeshSS组成。用距离矩阵D={d(i,j)|1≤i,j≤m+n}表示任意两个节点i、j之间的距离,其中i、j都是节点的编号。编号时,从MeshBS开始编号,接着进行MeshSS编号,编号是顺序增加的。本算法定义了节点之间的最大传输距离值d以下是对多出口WiMAXMesh网络从虚拟节点开始构造全局调度树并进行资源调度的算法描述。(1)在Mesh网络中新增虚拟根节点R(5)从0节点开始,选最小距离边e(6)若i=n+m则得到最小生成树T,转(9),否则转(7);(7)设已选e(8)i←i+1转(6);(10)从T中依次选取到根节点从最长到最短的路径P(11)对P(12)如果全部节点都已调度,则schlist就是调度列表;否则转(10)。以下用数学归纳法证明本算法所得到的最小生成树T是全局最优的最小生成树。·如果只有1个BS节点,则由于R·假设利用本算法已生成一棵具有m个BS和n个SS的最小生成树,而此时还有一个节点k未加入树中。·如果此节点是一个BS节点,则由于BS与R·如果此节点是一个SS节点,那么它到其他顶点的距离也是比现有最小生成树里最大距离的边还要大,否则根据本算法该节点应先于其他节点已加入树中。因此,剩余节点k只要选取与其距离最小的节点加入树中即可,从而保证得到的树仍为最小生成树。3.4全局调度树网络的选择可以通过以下流程把本算法应用在WiMAXMesh网络中。a.在无线Mesh网络中设置多个MeshBS(不少于1个),各MeshBS均与上一级网络(由SGSN或MSC等组成的网络)有连接。该连接是无线Mesh网络的出口。b.各MeshBS之间可以采用有线或微波进行互联,也可以考虑在MeshBS之间采用带外(outofband)无线回程连接。当采用带外方式时,MeshBS之间的通信频带应采用与MeshSS之间相异的频带,以免相互干扰,并提高链路容量。c.MeshSS依据到各MeshBS的距离、带宽或QoS等接入策略,选择接入某个MeshBS,这样以该MeshBS为根可以形成一颗调度树;如果某MeshSS到多个MeshBS的度量值相等,则该MeshSS可以选择序号最小的MeshBS。d.当MeshSS接入网络后,通过本文提出的MEMSA算法,可以计算一个全局最优调度树。此处的全局最优可以根据实际需要,采用功率、干扰、成本、吞吐量等判据。e.第d步计算的全局调度树可能与第c步计算的局部调度树有差别,此时MeshBS应通知相应MeshSS按照全局最优树重新选择上级节点。f.对于由MeshSS发往MeshBS的上行业务,可以通过全局最优树实现选路至相应MeshBS。g.对于由上级网络发往MeshSS的下行业务,可以依据本全局最优树计算的路由选择相应的MeshBS进行下发;如果由于路由变化、漫游等原因造成被选中的MeshBS的下级节点不包含目的MeshSS,则该MeshBS有责任把下行数据包传递到相应正确的MeshBS。h.各MeshBS之间可以进行负载均衡,也可以进行业务分类,例如某些BS承载实时业务,而某些BS承载非实时业务。i.为了保证网络的健壮性和容灾性,各MeshBS之间可以通过某种特定的策略,如Round-Robin或者指定主备的方法进行负载均衡。如果某MeshBS失效,则可以由相邻MeshBS接替承载其业务。现有网络并不需要做太大的调整来使用本算法。因为对于SS而言,它接入到哪个SS是根据其接收到的网络相关信息(例如信号强弱、跳数多少等因素)来选择的。如果使用本算法,只要在SS广播的网络信息中加上全局优化树的Metric值作为参考就可以了;在BS方面,也只须负责进行自身所带子树的调度,对于其他BS下带的SS,BS只须知道网络路由。当网络因为故障或割接等原因发生改变时,由相应BS发起在BS之间进行全网络的数据交换和运算;当SS切换时,SS根据Metric值重新选择接入的SS或BS即可。3.5用边值总成相关的比来表示边值由于本算法是一个全局最优算法,其优化效果可以采用本方法时的最小生成树的边值总和与未采用本方法时边值总和的比来表示。该比值等于对某一连通图求最小生成树得到的边长度之和与通过该连通图求得的任意连通树的边长度之和的平均值进行比较所得到的值。该值与具体连通图的拓扑构成有关,但必小于等于1。4多频率梯度仿真为了验证我们所提出算法的有效性,我们基于C语言开发了一个WiMAXMesh网络仿真平台对WiMAXMesh网络的调度算法进行仿真。在仿真过程中,我们随机生成了1000个拓扑图,并在拓扑图中随机摆放MeshBS和MeshSS节点,其数量也是随机生成的。我们比较了以下几种情况下的调度效率。·单调度树单频率(singletreesinglefrequency,STSF),所有的节点,包括多个BS和多个SS节点都共用一个调度树,而且采用同一个频段。这种情况也就是传统的调度方法;由于共用频带,因此收发干扰限制在2跳范围内。·多调度树单频率(multi-treesinglefrequency,MTSF),采用本文提出的MEMSA算法生成的多棵调度树,所有节点共用一个频段;由于共用频带,因此收发干扰限制在2跳范围内。本情况与第(a)种情况的差别主要是存在多个出口。·多调度树多频率(multi-treemulti-frequency,MTSF-ISO),采用本文提出的MEMSA算法生成的多棵调度树,各子树使用不用的频段,从而相互隔离,但同一棵子树内部仍然存在干扰,每棵子树内的收发干扰为2跳范围。·多调度树多频率加上定向天线(multi-treemulti-frequencywithdirectionalantenna,MTSF-ISO-Dir),采用本文提出的MEMSA算法生成的多棵调度树,各子树使用不用的频段,从而相互隔离,同时,各Mesh节点之间采用定向天线,可以把干扰范围限制在1跳范围内。以下是当网络有20个和50个节点时采用不同调度算法下的仿真结果。图6和图7的横轴是BS的数量,而纵轴是调度周期。从仿真结果可以看出,STSF与MTSF的调度效率相近,而MTSF由于有多个BS作为出口,总体调度周期比STSF缩短2%;当采用多频段MTSF-ISO时,调度效果得到明显提升,调度周期缩短约53%;当