WiMAX Mesh网络中一种分布式时隙分配算法

张新有，伸桂林

西南交通大学 信息科学与技术学院，成都 610031

1 引言

随着无线通信技术的发展，宽带无线接入技术成为了人们关注的热点。WiMAX[1]以其更大的覆盖面积，更高的传输速率和更可靠的传输性能受到了人们的关注。其中具有多跳性和自组织性的WiMAX Mesh网络引起研究人员的极大兴趣。WiMAX Mesh网络标准中没有定义与WiMAX PMP网络类似的业务分类和QoS级别，也没有定义相应的资源调度算法和QoS保障机制，因此WiMAX Mesh网络的QoS保障技术急需进一步深入研究。

IEEE802.16标准为WiMAX Mesh网络定义了两种调度机制：集中式调度和分布式调度。集中式调度下所有节点的带宽请求都需要汇聚到BS，由BS进行统一调度和分配；分布式调度中节点以竞争的方式发送带宽请求消息，通过三次握手协商分配所有的带宽资源。无论是集中式调度还是分布式调度，其带宽调度算法都会对整个网络性能造成很大的影响。本文对WiMAX Mesh网络下的分布式调度机制进行了分析，提出一种基于区分服务的微时隙动态预留分配算法。

2 相关工作

目前较多文献对WiMAX Mesh分布式调度进行了研究，主要集中在两个方面：即邻居节点间对MSH-DSCH消息发送时序的竞争和对数据子帧微时隙的分配方式。尽管这些研究取得了一些进展，但仍然还有许多方面需要进一步的改进和完善。

IEEE802.16标准[1]中对邻居节点间MSH-DSCH带宽请求消息发送时序的竞争提出了一种解决方法。文献[2]分别对几种消息发送时序竞争模型进行了分析，并对各模型节点的竞争概率进行了较深入的研究；文献[3]提出了一种动态调整休眠参数的方式改变节点间的消息竞争秩序，节点每竞争成功一次发送MSH-DSCH带宽请求消息都要进行一定时间的休眠，该文献以当前请求带宽的节点队列长度作为判断节点休眠的依据，根据队列长度对节点设置不同的休眠参数，从而避免节点间大量的竞争导致带宽利用率降低。

对IEEE802.16 MAC帧中数据子帧的微时隙分配是另一个研究重点。文献[4]提出了一种分布式的微时隙分配算法，该算法每次为请求节点分配时隙时，都找最少能满足当前需求的时隙段来分配，最大化地减少时隙碎片，提高每帧的时隙利用率。

文献[5]提出了一种分布式多跳预约微时隙算法M-HBRP。传统分布式调度节点间以三次握手形式来建立连接，当多跳节点间需要发送数据时总是在相邻两个节点间三次握手，成功后再进行下一次的两个相邻节点三次握手，以此逐跳地申请带宽。而M-HBRP算法在上两个节点进行三次握手的同时，向下一节点发送握手申请，多个节点间同步地进行微时隙申请。仿真表明该算法在保证QoS的同时，可以一定程度上减小端到端的时延。

文献[6]将业务流划分为高优先级和低优先级业务流组，并且设置两个检查点和阈值，当检查点的数据子帧微时隙使用数低于阈值时认为网络状态良好，高优先级业务流和低优先级业务流同等对待，而当检查点的数据子帧微时隙使用数高于阈值时则认为网络出现一定程度的拥塞，只允许高优先级的业务流，低优先级业务流的请求返回失败信息。这种方法虽然能够保证高优先级业务的优先权，但会使得低优先级业务被严重影响。

文献[7]将资源预留的思想引入到了协同分布式调度当中，在每个Mesh帧的数据子帧中预留P个微时隙，高优先级业务流分配时隙时从数据子帧的起始位置查找满足要求的时隙段，直到查找到数据子帧末尾，低优先级业务总是从P+1开始往后查找。这种分配方式有个较为明显的缺陷：由于P值固定，而网络状态随时在变化，因此网络拥塞时可能会造成大量的微时隙浪费。

文献[8]在文献[7]的基础上进行了改进，预留的微时隙数是可以动态变化的，并且以高优先级业务和低优先级业务在队列中所占用的比例来作为动态调整预留微时隙的依据，每次判定高优先级业务请求数大于低优先级业务请求数时认为网络拥塞，预留时微隙数P增加步长St，而高优先级业务请求数小于低优先级业务请求数时认为网络正常，预留时微隙数P减少步长St。该算法可以实现根据网络状态动态地调整预留微时隙，但以业务数量的比较来作为网络拥塞的判定依据并不合理，在高优先级业务数和低优先级业务数都较少时网络并未拥塞，而此算法无法做出正确的判断。

本文综合文献[7]、文献[8]的方法，提出一种新的微时隙预留调整机制，可以根据网络业务状态动态地调整微时隙分配格局，以达到高低业务流间的动态平衡。

3 WiMAX分布式调度机制

IEEE802.16d规定每个Mesh帧包含控制子帧和数据子帧两部分，控制子帧和数据子帧都可以划分为更小的时序（slot）或微时隙（minislot），控制子帧中时序数由MSH-NCFG消息中Network description IE中的MSH_CTRL_LEN参数决定，数据子帧用于传输业务数据，每个数据子帧包含256个微时隙。

控制子帧又可以分为网络控制子帧和调度控制子帧，二者不会同时出现在同一个Mesh帧内。网络控制子帧包括节点入网（MSH-NENT）消息和节点交换与网络配置（MSH-NCGF）消息，用来创建和维护不同节点间的协调工作。调度控制子帧包括集中式调度（MSH-CSCH）和分布式调度（MSH-DSCH）两种消息，为节点间数据交换进行调度，合理分配带宽，避免数据传输产生冲突。

分布式调度有两种类型：即协调分布式调度和非协调分布式调度，由MSH-DSCH消息中的Coordination Flag字段来区分。其中“非协调”是指Mesh中的节点通过竞争获得minislot，所以可能发生碰撞；“协调”是指节点在控制子帧里发送分布式调度消息（MSH-DSCH），通过请求-授权-授权确认三次握手的过程，协商节点间数据子帧里minislot的分配，为节点间提供无碰撞的传输数据。协调分布式调度是本文研究的重点。

3.1 MSH-DSCH消息结构

MSH-DSCH消息包括MAC消息头和若干信息单元，MAC头中包含了CID（Connection ID），该CID中包含了该数据单元的可靠性、优先级、丢弃优先级及对应的Link ID等参数[1]。信息单元用来协调节点的时隙分配与调度，主要包含以下四个部分[5]：

（1）调度信息单元（Scheduling IE）：该单元存放节点自身和邻居节点的下一次发送MSH-DSCH消息的时间间隔Next Xmt Mx和Xml Holdoff Exponent参数，节点通过这些参数计算出邻居节点下一次发送MSH-DSCH消息的时间范围，从而确定将同自己一起参与MSH-DSCH发送时序竞争的邻居集合，并通过MeshElection（）函数[9]来判断竞争结果。

（2）可用资源信息单元（Availability IE）：该单元存放当前节点可利用的带宽信息，包括起始帧号（Start Frame number）、微时隙起始位置（minislot start）、一帧中微时隙的总数（minislot range）、连续经历的帧数（Persistence）、资源信息（Direction，0表示不可用，1表示可用于发送，2表示可用于接收，3表示既可发送也可接收）、信道序号（Channel）。

（3）请求信息单元（Request IE）：该单元存放节点的带宽请求相关信息，包括与此节点通信的（Link ID）、节点的时隙请求数（Demand Level）和所有时隙请求必须连续分布的帧数（Demand Persistence）。

（4）授权信息单元（Grants IE）：该单元表明已被授权的带宽相关的信息。包括与此节点通信的Link ID、授权的起始帧号（Start Frame number）、授权的微时隙起始位置（Minislot start）、一帧中微时隙的总数（Minislot range）、连续经历的帧数（Persistence）、资源信息起始帧号（Start Frame number）、信道序号（Channel）、授权状态（Direction，1表示授权，0表示授权确认）。

3.2 三次握手过程

节点根据所收到邻居节点的MSH-DSCH消息对自己可用微时隙状态进行更新。Mesh模式分布式调度的三次握手过程如图1所示。

图1 分布式调度三次握手过程

节点间一次数据连接的建立需要经过“请求-授权-确认”三个步骤。首先请求节点广播发送MSH-DSCH请求消息，且在MSH-DSCH的Request IE中指明Link ID、需要的时隙数、数据帧持续个数及节点自身的时隙使用情况（Availabilities IE）；授权节点根据Request IE的请求，采用合适的时隙分配算法寻找自身AvailabilitiesIE中适合的微时隙，若寻找成功则广播MSH-DSCH Grant IE（direction=1）授权消息，指明已授权的微时隙的标记；请求节点在收到授权节点的Grant IE后，复制该条消息内容并设置direction=0，在下一个MSH-DSCH发送机会时将Grant IE（direction=0）授权消息发送给授权节点。

4 区分服务微时隙分配算法

4.1 Mesh业务分类

WiMAX标准为PMP网络模式定义了4种业务类型[1]：主动授权业务（UGS），实时轮询业务（rtPS），非实时轮询业务（nrtPS），尽力而为业务（BE），且每种数据业务都与一系列的QoS参数相关联。而Mesh网络中只在Mesh CID（Connection Identifier）中定义了 Type、Reliability、Priority、Drop precedence等服务参数。本文通过区分MAC头CID中的Priority字段将业务分为两类：高优先级业务和低优先级业务，高优先级业务对时延相对敏感，低优先级业务可以容忍一定的时延。这种业务分类和PMP的4种业务类型可以没有明显的对应关系，也可以有对应关系，比如UGS和rtPS对应高优先级业务，nrtPS和BE对应低优先级业务。

4.2 算法描述

本文以高优先级业务和低优先级业务占用微时隙的状况来作为网络拥塞（时隙不足）的判定依据，动态调整预留微时隙时是以连续网络拥塞或网络正常的次数来作为调整时隙预留的依据，借鉴快加速、快后退的思想来保证高优先级业务的服务质量。该算法需要在MSH-DSCH消息中添加动态预留时隙Pt、记录高优先级业务引起的连续拥塞次数和网络连续空闲次数congestion_num、free_num。算法流程如图2所示。算法说明如下。

（1）根据请求帧中的CID参数可以将请求业务区分为高优先级业务的低优先级业务，该算法的目的是确保高优先级业务优先获得微时隙，同时确保低优先级业务不被“饿死”。

（2）授权节点设定每一MAC帧的数据子帧中最大预留时微隙数Pt_Max和最小预留微时隙数Pt_Min以及时隙变化步长St，设置高业务时隙占用比阈值TH1，低业务时隙占用比阈值TH2；初值设定congestion_num=0，free_num=0，Pt=Pt_Min 。

（3）节点要记录每一数据子帧微时隙分配情况。高（低）优先级业务微时隙占用比阈值为一个比值，分子是高（低）优先级业务占用微时隙数，分母是此算法此时分配给高（低）优先级业务微时隙总数。

（4）虽然图1中显示一个请求节点的连接过程，但由于一个请求MAC帧的消息中可能包含多个（可以来自不同节点）时隙分配请求，所以授权节点需要逐个处理内个业务请求。

（5）若请求节点发送的数据请求是高优先级的业务流请求则在Availabilities IE中从每帧的起始minislot[0]开始往后查找符合条件的时隙直到minislot[Pt-1]，如果查找成功，返回Grant IE（direction=0），否则返回失败信息；若请求节点发送的数据请求是低优先级的业务流请求则在Availabilities IE中从每帧的minislot[Pt]开始往后查找符合条件的时隙，直到末尾，如果查找成功，返回Grant IE（direction=0），否则返回失败信息。

图2 Request IE请求帧的时隙分配过程

（6）图2中的①表示没有得到所需微时隙的Request IE以失败告终，授权节点将不做任何处理；另一种方法是对高优先级业务请求继续保存在请求队列，参与下一帧的微时隙分配，而低优先级业务以请求失败告终（流程中没有反映此种情况）；图2中的②表示当节点处理完所有请求后，对得到微时隙请求的节点授权Grant IE将在该节点随后竞争到的MSH-DSCH消息时序中广播发出，没有得到资源的请求将不作回应。

4.3 算法分析

相比文献[6]使用的设定固定监测点方法，采用计算微时隙占用比更能精确反映时隙的来判断时隙的使用情况。因为数据子帧的微时隙经过历史节点间请求、分配的操作后，会造成空闲时隙分配不均形成空洞，固定监测点方法无法回避此问题。此算法也改进了文献[7]中P值固定的问题，灵活地分配高低优先级业务占用时隙的比例，从而提高了时隙的利用率。相比文献[8]的高（低）优先级业务请求数之比判断时隙利用率的方法，本文微时隙占用比的方法更加准确有效。

本算法的改进主要体现在统计高低优先级业务的时隙占用比以及微时隙动态预留算法上，通过参数的设置和适当调整实现预期功能，与参考文献[6-8]相比，没有增加算法复杂性，仍然是线性查找的算法复杂性O(n)。

5 仿真结果及分析

5.1 仿真环境

采用网络模拟器NS2-2.33对算法进行仿真，基于802.16d-2004标准的mesh开源补丁Ns2mesh80216[10]。定义本文算法为A3，文献[6]算法为A0，文献[7]算法为A1，文献[8]算法为A2。仿真将所有业务流分为高优先级实时业务流和低优先级尽力业务流两种业务流，高优先级业务流用恒定速率的CBR流来表示，CBR分组长度为1 000 Byte，以恒定速率512 kb/s的速率发送，发送间隔30 ms；低优先级业务流采用可变速率的VBR流表示，VBR分组大小在100～300 Byte之间随机产生，发送间隔200 ms，发送速率120 kb/s近似于实际网络中的HTTP业务。设定本文算法A3的参数Pt_Min=128，Pt_Max设为总时隙数的3/4，即Pt_Max=192。检查点阈值在A0、A1算法中都设为158，检查点设为此帧之前的第5帧，A2中固定预留时隙长度设为158，步长St为4，A3算法中的步长St设定为2，TH1设为80%，TH2设为90%。仿真中VBR的业务流条数固定为15条不变，CBR业务流逐渐增加，仿真时间60 s。

仿真分析设置了三个考察指标：端到端的时延、节点的请求失败率以及帧的时隙利用率。仿真中通过改变节点的数量对比其他几种调度算法来进行仿真实验，对仿真数据进行统计分析。仿真参数设置见表1。

5.2 实验结果分析

图3为业务流的平均分组时延比较，从图中可以看到在固定VBR流条数不变的情况下，随着CBR流传输节点的增加，CBR流和VBR流的平均分组时延都逐渐增大，由于在时隙分配时对业务设定了优先级，VBR流的平均分组时延大于CBR流。CBR业务流下算法A0、A1、A2的平均分组时延依次减小，本文提出的A3算法与A2较为接近，比A2算法略佳；在VBR业务流下情况则正好相反，但和A2算法相比，A3算法的时延随着节点增加反而下降。一方面较为明显地体现出了区分服务的特性，高优先级的业务流得到了较低的时延；另一方面显示了A3算法对低优先级业务的时延保证。

表1 仿真参数设置列表

图3 算法平均分组延迟对比

图4为VBR流数据分组的请求失败率比较，从图中可以看出，当实时CBR流增加以后，由于CBR流具有较高的优先级，因此CBR流越多，VBR流的数据分组请求失败率就越大，其中A0算法的失败率最高，这是由于A0算法在检查到网络处于拥塞状况后低优先级的VBR流直接返回请求失败，而A1、A2、A3算法在网络处于拥塞时低优先级业务仅仅是初始搜索空闲时隙的位置不同，A1算法由于预留的微时隙是固定不变的，在最初时节点较少时由于预留微时隙比A2、A3要高，所以请求失败率比A2、A3算法要高，但随着CBR流节点增加后，A1算法的VBR流数据分组的请求失败率反而要比A2算法低。随着节点数量的增加，A3算法的请求失败率增加缓慢。

图5为微时隙利用率比较，网络中通信节点越多节点的时隙利用率越大，从图中的对比可以看出在时隙利用率上A0算法的时隙利用率最差远低于A1、A2、A3算法，本文提出的A3算法由于在时隙预留调整上，出现拥塞后预留时隙以步长指数倍的增长，机动性最大，所以在整个时隙利用率的比较中占有绝对的优势，比A2和A1算法都表现得更好。

图4 算法请求失败率对比

图5 算法时隙利用率对比

综合以上对时延和分组请求失败率和时隙利用率的仿真实验，可以看出尽管A0、A1、A2、A3四种算法都实现了分类业务的QoS。同时可以看出，本文提出的A3算法表现出了更优的性能，兼顾了时延、请求失败率和时隙利用率。

6 结束语

本文提出了一种WiMAX Mesh网络中基于资源预留的微时隙分配算法，算法首先将业务分为高优先级业务和低优先级业务两类，对高优先级的业务在MAC帧中预留一定的微时隙作为分配高优先级业务的时隙，预留微时隙数量可以根据数据子帧中微时隙的利用率动态调整，仿真表明该算法在满足高优先级业务QoS的同时兼顾业务的请求失败率与时隙的利用率，降低分组的平均时延，提高整个网络的性能。仿真中A3算法不同的参数设置进行比较，如本算法中的参数TH1和TH2取值对结果有较大影响。在授权节点的时隙分配过程中需要时隙可用状态，本文将时隙的状态仅分为可用，不可用是不够的。因此如何进一步合理地设置各个参数使网络性能达到最佳还需要进一步研究。而且WiMAX Mesh网络QoS问题不仅与时隙分配算法有关，也与网络的接纳控制、路由、包管理器等环节有关，这些都是下一步的研究重点。

[1]IEEE Standard802.16-2004.IEEE standard for local and metropolitan area networks-part16：air interface for fixed broadband wireless access systems[S].2004.

[2]Cao Min，Ma Wenchao，Zhang Qian.Analysis of IEEE 802.16 Mesh mode scheduler performance[J].IEEE Transactions on Wireless Communications，2007，6（4）：1455-1464.

[3]Rostami A，Rostami A，Zokaei S，et al.A new two-stage dynamic holdoff time scheme for enhancement of signaling messages in IEEE 802.16 Mesh networks[C]//International Conference on Communication Technology（ICCT），2011：1-25.

[4]Peng Limin，Sun Suyun.Coordinated distributed data scheduling scheme in IEEE 802.16 Mesh networks[C]//International Conference on Internet Computing and Information Services，2011：389-392.

[5]Li Yun，Zhang Xin，Zhuang Hongcheng，et al.An end-to-end QoS assurance method in IEEE 802.16 Mesh networks[C]//Global Telecommunications Conference（GLOBECOM 2010），2010：1-6.

[6]Liu Fuqiang，Zeng Zhihui，Tao Jian，et al.Achieving QoS for IEEE 802.16 in Mesh mode[C]//Proceedings of the 8th International Conference on Computer Science and Informatics，2005：3102-3106.

[7]曾智慧，刘富强，陶健，等.IEEE 802.16 Mesh模式下MAC调度机制的研究[J].计算机工程与应用，2005，41（23）：135-138.

[8]汪丽萍，刘富强，王新红，等.IEEE 802.16 Mesh模式下区分服务时隙调度算法[J].计算机工程与应用，2006，42（34）：105-108.

[9]Shukaili A A，Chilamkurti N，Zeadally S.Enabling“Quality of Service”in IEEE802.16 networks for distributed mesh topologies[C]//2010 Australasian Telecommunication Networks and Applications Conference，2010：135-140.

[10]Ns2mesh80216[EB/OL].[2013-03-20].http：//cng1.iet.unipi.it/wiki/index.php/Ns2mesh80216.