无线Mesh网络环境下的SLA机制

赵耀培，杨 扬

（1.北京科技大学 计算机与通信工程学院，北京100083；2.山东管理学院 科研处，山东 济南250100）

0 引 言

现实应用中，实际服务的质量往往达不到预期要求，甚至服务失败，这使得服务提供商和客户的收益均受到影响。既考虑服务本身的内容又在保证服务质量的前提下最大化双方收益，是服务等级协议 （service level agreement，SLA）应运而生且备受瞩目的原因所在。

随着通信技术的发展，无线Mesh 网络广泛应用于诸多领域［1］。无线Mesh网络的特点决定了信号在传输过程中会与其它设备发送的信号发生冲突，从而导致信道中数据包的丢失出错频发。为提高数据服务的正确性和可靠性，结合Mesh环境有限网络资源的特点，提出面向服务质量和顾客满意度的服务冲突退避机制，最大化避免低服务等级业务抢占高服务等级数据的带宽，或由相同服务等级数据群发产生碰撞导致数据包的丢失。

目前，关于SLA 的研究主要集中在有线网络，比如文献 ［2］提出一种基于SLA 的服务组合和协商框架，给出一种启发式服务组合方法从而满足SLA 协议的服务组合最优化，提出基于SLA 的服务组合自动协商机制适应环境的动态变化；文献 ［3］提出了一种基于SLA 的面向基础设施服务的平台系统架构，但是在无线网络中的相关研究实属有限；文献 ［4］提出了一个针对服务等级下行链路传输的分析模型，该模型是基于两站点的无线信道模型；文献［5］提出了一种动态服务协商协议，该协议研究的是基于服务分级的无线QoS架构。然而，这些研究主要关注将不同服务从有线核心网络扩充到无线网络，并没有结合无线网络特征考虑数据服务的可靠性、可用性及有效性。事实上，无线Mesh特点将导致其服务等级协议所面临的问题较传统主干网络下的SLA 策略复杂的多，主要是源于无线通信网络不确定性和复杂性。无线Mesh网络不需要基础设施，网络中的各个节点处于平等地位且以无线方式进行通信，可自由移动。各节点通过MAC 协议的协调访问共享信道。由于MAC 协议分布式运行，所以不可避免地导致因多个节点同时发送数据而产生冲突。冲突发生时，要求各个节点降低对无线信道的访问频度，减小数据的冲突概率，提高信道利用率和网络吞吐量［6］。

因此，主要研究无线Mesh 网络环境下的服务等级协议SLA 机制。相比于其它SLA 机制的研究，本文研究具备如下特点：①设计了基于MAC层的SLA 冲突避免机制；②采用马尔可夫模型进行理论分析；③优化底层资源配置，即在提升网络吞吐量、降低丢包率的情况下保障通信链路的可用带宽。

1 马尔可夫模型的提出

马尔可夫过程 （Markov）是一类重要的随机过程，特征概括为：在 “现在”已知情况下，事物变化过程的 “过去”和 “未来”没有任何关系，即这种情况在未来的变化不依赖于过去的情况。而无线Mesh网络环境中数据的发送正是一个具有上述特征的随机过程，因此将无线Mesh中数据发送问题抽象描述为马尔可夫模型。事实上，马尔可夫过程可以描述现实生活中的很多现象如，视频监控系统中的视频信号、商业活动中每天的销售情况、液体中颗粒所做的布朗运动等［7］。基于无线Mesh 特点提出的数据发送模型如下：

设有马尔可夫过程｛Xn，n∈T｝。其中T 是离散时间集合，T ＝｛0，1，2，…｝；Xn表示随机过程，它所有取值的集合可构成状态空间，即I＝｛1，2，…｝。

定义1 设某随机过程｛Xn，n ∈T｝，如果对任意整数n∈T 和任意i0，i1，…，in＋1∈I，满足条件概率式 （1），则称｛Xn，n∈T｝是马尔可夫链

定义2 条件概率如式 （2）所示

称为在n时刻马尔可夫链｛Xn，n∈T｝的转移概率，该式中i，j∈I。

一般情况下，转移概率P（n）ij与当前时刻n及上一时刻的状态有关。如果对于任意的i，j∈I，｛Xn，n ∈T｝的转移概率P（n）ij都与n无关，则该马尔可夫链有平稳转移概率，可被称作齐次马尔可夫链。现实生活中，很多问题的解决都与当前时刻无关，所以对齐次马尔可夫链的研究比较广泛和深入。齐次马尔可夫过程对无线Mesh网络的研究也有非常重要的价值。

2 服务等级算法的提出

2.1 业务流的服务等级设定与标记

对报文服务等级进行设定与标记，区分不同服务等级的报文质量，从而进行合理的调度。图1描述了基于无线Mesh网络的视频监控系统。按照摄像头的安放地点将告警信号分为不同的服务等级，如将金库内的报警信号设为高服务等级，电梯内的告警信号设为中服务等级，银行大门处的告警信号设为低服务等级。服务等级设定后，便可根据业务流中标记的服务等级来进行队列调度，从而保证告警模块的要求。

图1 无线Mesh网络视频监控系统

我们根据具体业务类型，将服务等级分为高、中、低3个等级，通过在802.11数据帧中对不同服务等级的报文进行标记，3个等级的模型设计如下：

其中，802.11的控制帧格式如表1，其中，第一行的数字表示帧位数。

表1 802.11控制帧格式

考虑RTS帧的控制帧，将Subtype帧子类型的位数由4位增大至6位，多出的两位用来标记服务等级的级别。在多出来的两位中，其服务等级的级别可见表2。

表2 服务等级标记

即用11代表服务等级为高的业务，10代表服务等级为中的业务，01代表服务等级为低的业务。

2.2 基于服务等级的碰撞避免算法MPCA

为了解决无线Mesh网络环境下不同服务等级业务的碰撞问题，如低服务等级业务增多从而影响高服务等级的业务带宽、相同服务等级业务因同时发送数据从而产生碰撞，本文针对无线网络视频监控系统的告警模块中存在的不同业务类型，提出了一种基于SLA 机制的冲突避免算法MPCA，该算法通过在MAC 层采用SLA 机制，针对不同的服务等级分别调整最小竞争窗口和当前的退避窗口大小，从而尽可能的避免低服务等级业务的数据帧突发给高服务等级业务所带来的影响，使高服务等级的业务有效的抢占网络资源［8］，并通过建立马尔可夫模型论证了该算法的有效性。

MPCA 算法及功能特性可从两方面描述：

（1）不同的服务等级业务对应不同的退避算法假设节点竞争窗口初始值为CW0，最大竞争窗口为CWm。对于本文提出的MPCA 算法，其竞争窗口CW 的变化情况可抽象为：

对于高服务等级的数据业务，其Fdec和Finc函数见式（3）

其中，Fdec函数表示节点通信成功时竞争窗口的变化情况；Finc函数表示通信失败时竞争窗口的变化情况。无论数据传输是否成功，高服务等级的竞争窗口都维持CW0不变。

对于中服务等级业务，Fdec和Finc函数见式 （4）

其中，0≤i＜m。若节点通信成功，则其竞争窗口按照Fdec函数变化；若节点通信失败，则其竞争窗口按照Finc函数变化。

对于低服务等级的数据业务，Fdec和Finc函数见式 （5）

其中，0≤i＜m。若节点通信成功，则其竞争窗口按照Fdec函数变化；若节点通信失败，则其竞争窗口按照Finc函数变化。

（2）解决不同服务等级间的碰撞问题：①避免相同服务等级之间碰撞避免假设竞争窗口初始值CW0＝31，当两个高服务等级业务同时发送数据时，退避时间backoff 的取值在 （0，31）之间，所以发生碰撞的概率为，远小于1，即再次发送冲突的概率很小。②避免不同服务等级间的碰撞避免当两个不同级别的业务碰撞时，较高服务等级的业务退避等待时间比低服务等级的业务短，从而更有利于抢占信道。

石木、土石木结构建筑限于材料的承重能力，平面一般为多开间、小进深，主要平面形式有两间，三间、三间一甩袖、三间两甩袖，五间、五间一甩袖、五间两甩袖，七间、七间两甩袖，有檐廊，无檐廊等几种类型（图9）。靠崖窑及石砌锢窑平面多为三孔，相互独立，各自开门。

3 基于SLA的MPCA性能分析

3.1 冲突避免机制的Markov模型

我们将以二维马尔可夫模型为基础，对上一节中设计的多服务等级冲突避免机制进行理论分析。

在基于多服务等级冲突避免机制的马尔可夫模型中，用退避时间和当前退避窗口值表示当前节点状态，节点状态的转移概率取决于接收端的碰撞概率。

由于针对的是多服务等级业务发生碰撞的情况，所以分别对高、中、低3个等级的数据业务均进行了Markov建模。通过分析3个等级的冲突避免算法，可将中、低两个服务等级的服务策略抽象为同一数学模型，如图2所示的是高服务等级业务对应的冲突避免Markov模型。

图2 高服务等级业务Markov模型

图3 表示的是中、低服务等级业务对应的冲突避免Markov模型。假定报文发生冲突的概率是独立的，用i／CTC／TTS和CWj表示在时隙TC／TS时刻网络中节点的退避阶段以及竞争窗口大小。模型从START 状态开始，到DONE状态结束。START 状态表示报文在MAC 层即将被调度阶段，DONE 状态表示报文成功传输完成时的阶段。在该模型中，状态（i，CWj）表示发送节点的状态，即退避窗口值为CWj，退避时间的值为i。其中0≤i≤CWj，0≤j≤m。

基于上述分析，中、低服务等级业务的马尔可夫过程可描述为：

（1）节点从START 开始以（i，CW0）0≤i≤CW0进入退避阶段，退避计数器的值依次递减到0，节点开始发送RTS－CTS帧。发送RTS－CTS帧后，节点可进入两种状态：一是发生RTS－CTS碰撞后状态；一是RTS－CTS成功传输后状态。

图3 中、低服务等级业务Markov模型

（3）若RTS－CTS交换成功，发送端开始发送DATA帧。状态（Tk，CWj）1≤k≤TS表示RTS－CTS帧交互成功后，在DATA 发送过程第k个时隙前节点状态。经过TS个时隙后，如果DATA－AKC 交换成功，则马尔可夫链转移到DONE状态；若果DATA－ACK 交换失败，设失败的概率为，则发送端以概率重新进入START 状态。

3.2 不同服务等级业务网络可用带宽分析

3.2.1 数据成功传输服务时间期望值分析

无线Mesh网络视频监控系统拓扑图结构如图4所示。

图4 无线视频监控系统网络拓扑

在链路e，报文服务时间的期望值等于在马尔可夫链中报文从START 状态到DONE 状态时整个过程的期望值。针对高服务等级和中、低服务等级业务服务时间期望值计算如下。

（2）中、低服务等级业务：中、低服务等级业务服务时间期望值如式 （7）所示

基于上述分析，可以看出，数据成功传输所需服务时间由两方面决定：碰撞概率和发送端的空闲等待时间。采用了服务等级机制后，服务时间明显减少，如果不采用服务等级机制，那么，所有数据在链路e上的服务时间期望值都是如式 （8）所示

3.2.2 网络可用带宽分析

基于上节结论可知，假定链路上源端的发送速率和服务时间期望值满足式 （9）［10］

则可以保证该链路e有效的避免碰撞。

式（9）中，ξ为链路服务强度，范围 （0，1］；υe为链路e在避免碰撞情况下的最高发送速率；E［Se］为服务时间的期望值。

通过服务时间和源端发送速率的关系，可以得出结论：采用服务等级算法后，由于服务时间减少，使得网络的可用带宽增加。

4 仿真分析

假定信道丢包率为0，数据丢失完全是由冲突所致，物理层使用802.11b标准，信道数据速率11 Mb／s，流量由UDP协议的恒定比特率产生。

仿真过程拓扑结构基于图4，数据流经邻居节点转发传送至接收端。在图5中，生成3条数据流，分别从节点1、5、3发出经由网关节点为7 接入internet。其中，节点1、5、3、6、7中相邻节点的横、纵向距离为200m，节点2、6、4的纵向距离为100m。

为便于分析，特将图4拓扑中的数据流向与其对应的id值规定为图5。

图5 数据流向与ID 值对应关系

即链路1－＞2－＞7对应的流id为1，链路5－＞6－＞7对应的流id为2，而链路3－＞4－＞7对应的流id为3。

图6～图8为不同服务等级业务下的节点发送速率范围。其中，图6是低服务等级业务流在尽量避免冲突情况下的发送速率范围，在这种场景下，报文大小为1024B，数据速率为11 Mbps；图7是中服务等级业务流在尽量避免冲突情况下的发送速率范围，在这种场景下，报文大小为600B，数据速率为11 Mbps；图8是高服务等级业务流在尽量避免冲突情况下的发送速率范围，在这种场景下，报文大小为100B，数据速率为11 Mbps。

图6 低服务等级业务流发送速率范围

图7 中服务等级业务流发送速率范围

通过分析，可以发现，服务等级越高，节点发送的速率范围越小。假定数据流1的服务等级高，数据流2的服务等级次之。当低服务等级的业务数据突发与高服务等级数据流产生冲突时，其数据包丢失率如图9所示。

图8 高服务等级业务流发送速率范围

图9 不同服务等级业务流丢包率对比

经仿真分析可看出，MPCA 算法可以很好的保障高服务等级业务流的传输，较原始的802.11协议，其高服务等级数据包的丢失率大大降低。

进一步，假定数据流1与数据流2是相同的服务等级，当这两个源端同时发送数据产生碰撞时，丢包率如图10所示。

图10 相同服务等级业务流丢包率对比

从图10 可以看出，在相同服务等级业务流冲突时，MPCA 机制下的数据丢包率明显低于原始802.11协议下的数据丢包率。

5 结束语

针对无线Mesh网络中数据传输所存在的问题，设计了基于服务等级的冲突避免算法，其创新之处在于：①提出了针对无线Mesh网络冲突避免的马尔可夫模型；②对无线Mesh网络环境下的SLA 机制进行探索性的研究，设计适用于无线Mesh网络视频监控系统的多服务等级冲突避免算法MPCA。论文最后通对MPCA 算法的可行性及有效性进行了验证分析。

［1］Makhoul A，Saadi R.Risk management in intrusion detection applications with wireless video sensor networks［C］／／Proc of IEEE Wireless Communications and Networking Conference，2010：112－119.

［2］BAI Wen.Study on service composition and consultation based on SLA ［D］.Xi’an：Shanxi Normal University，2013 （in Chinese）.［白雯，基于SLA 的服务组合与协商研究 ［D］.西安：陕西师范大学，2013.］

［3］LIU Shuang.Research and implementation of service quality guarantee and schedule algorithm based on SLA ［D］.Xi’an：North West University，2012 （in Chinese）.［刘爽.基于SLA的服务质量保证与调度算法的研究与实现 ［D］.西安：西北大学，2012.］

［4］Pablo Rodriguez－Mier， Manuel Mucientes， Manuel Lama.Automatic Web service composition with a heuristic－based search algorithm ［C］／／IEEE Intenational Conference on Web Service，2011：81－88.

［5］Chen JC.Dynamic service negotiation protocol（DSNP）and wireless DiffServ［C］／／Proc ICC，2011：1033－1038.

［6］Akyildiz IF，Wang X，Wang W.Wireless mesh networks：A survey ［J］.Comp Networks，2009，47 （4）：445－87.

［7］Matthias Winkler.Automaticing composite SLA management tasks by exploiting service dependency information ［C］／／IEEE European Conference on Web Services，2010：59－66.

［8］LI Ruifang.Backoff algorithm in MAC layer for wireless multimedia sensor networks ［J］.Journal on Communications，2010，16 （11）：512－531 （in Chinese）.［李瑞芳.适于无线多媒体传感器网络的MAC 层退避算法 ［J］.通信学报，2010，16 （11）：512－531.］

［9］Bianchi G，Tinnirello I.Kalman filter estimation of the number of competing terminals in an IEEE 802.11network ［C］／／Proceedings of IEEE INFOCOM，2003：844－852.

［10］Wang P，Zhuang W.An improved busy tone solution for collision avoidance in mobile Ad Hoc networks［C］／／Poc IEEE WICOM，2009.