趙耀培，楊 揚(yáng)

（1.北京科技大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，北京100083；2.山東管理學(xué)院 科研處，山東 濟(jì)南250100）

0 引 言

現(xiàn)實(shí)應(yīng)用中，實(shí)際服務(wù)的質(zhì)量往往達(dá)不到預(yù)期要求，甚至服務(wù)失敗，這使得服務(wù)提供商和客戶的收益均受到影響。既考慮服務(wù)本身的內(nèi)容又在保證服務(wù)質(zhì)量的前提下最大化雙方收益，是服務(wù)等級協(xié)議 （service level agreement，SLA）應(yīng)運(yùn)而生且備受矚目的原因所在。

隨著通信技術(shù)的發(fā)展，無線Mesh 網(wǎng)絡(luò)廣泛應(yīng)用于諸多領(lǐng)域［1］。無線Mesh網(wǎng)絡(luò)的特點(diǎn)決定了信號在傳輸過程中會與其它設(shè)備發(fā)送的信號發(fā)生沖突，從而導(dǎo)致信道中數(shù)據(jù)包的丟失出錯頻發(fā)。為提高數(shù)據(jù)服務(wù)的正確性和可靠性，結(jié)合Mesh環(huán)境有限網(wǎng)絡(luò)資源的特點(diǎn)，提出面向服務(wù)質(zhì)量和顧客滿意度的服務(wù)沖突退避機(jī)制，最大化避免低服務(wù)等級業(yè)務(wù)搶占高服務(wù)等級數(shù)據(jù)的帶寬，或由相同服務(wù)等級數(shù)據(jù)群發(fā)產(chǎn)生碰撞導(dǎo)致數(shù)據(jù)包的丟失。

目前，關(guān)于SLA 的研究主要集中在有線網(wǎng)絡(luò)，比如文獻(xiàn) ［2］提出一種基于SLA 的服務(wù)組合和協(xié)商框架，給出一種啟發(fā)式服務(wù)組合方法從而滿足SLA 協(xié)議的服務(wù)組合最優(yōu)化，提出基于SLA 的服務(wù)組合自動協(xié)商機(jī)制適應(yīng)環(huán)境的動態(tài)變化；文獻(xiàn) ［3］提出了一種基于SLA 的面向基礎(chǔ)設(shè)施服務(wù)的平臺系統(tǒng)架構(gòu)，但是在無線網(wǎng)絡(luò)中的相關(guān)研究實(shí)屬有限；文獻(xiàn) ［4］提出了一個針對服務(wù)等級下行鏈路傳輸?shù)姆治瞿Ｐ?，該模型是基于兩站點(diǎn)的無線信道模型；文獻(xiàn)［5］提出了一種動態(tài)服務(wù)協(xié)商協(xié)議，該協(xié)議研究的是基于服務(wù)分級的無線QoS架構(gòu)。然而，這些研究主要關(guān)注將不同服務(wù)從有線核心網(wǎng)絡(luò)擴(kuò)充到無線網(wǎng)絡(luò)，并沒有結(jié)合無線網(wǎng)絡(luò)特征考慮數(shù)據(jù)服務(wù)的可靠性、可用性及有效性。事實(shí)上，無線Mesh特點(diǎn)將導(dǎo)致其服務(wù)等級協(xié)議所面臨的問題較傳統(tǒng)主干網(wǎng)絡(luò)下的SLA 策略復(fù)雜的多，主要是源于無線通信網(wǎng)絡(luò)不確定性和復(fù)雜性。無線Mesh網(wǎng)絡(luò)不需要基礎(chǔ)設(shè)施，網(wǎng)絡(luò)中的各個節(jié)點(diǎn)處于平等地位且以無線方式進(jìn)行通信，可自由移動。各節(jié)點(diǎn)通過MAC 協(xié)議的協(xié)調(diào)訪問共享信道。由于MAC 協(xié)議分布式運(yùn)行，所以不可避免地導(dǎo)致因多個節(jié)點(diǎn)同時發(fā)送數(shù)據(jù)而產(chǎn)生沖突。沖突發(fā)生時，要求各個節(jié)點(diǎn)降低對無線信道的訪問頻度，減小數(shù)據(jù)的沖突概率，提高信道利用率和網(wǎng)絡(luò)吞吐量［6］。

因此，主要研究無線Mesh 網(wǎng)絡(luò)環(huán)境下的服務(wù)等級協(xié)議SLA 機(jī)制。相比于其它SLA 機(jī)制的研究，本文研究具備如下特點(diǎn)：①設(shè)計(jì)了基于MAC層的SLA 沖突避免機(jī)制；②采用馬爾可夫模型進(jìn)行理論分析；③優(yōu)化底層資源配置，即在提升網(wǎng)絡(luò)吞吐量、降低丟包率的情況下保障通信鏈路的可用帶寬。

1 馬爾可夫模型的提出

馬爾可夫過程 （Markov）是一類重要的隨機(jī)過程，特征概括為：在 “現(xiàn)在”已知情況下，事物變化過程的 “過去”和 “未來”沒有任何關(guān)系，即這種情況在未來的變化不依賴于過去的情況。而無線Mesh網(wǎng)絡(luò)環(huán)境中數(shù)據(jù)的發(fā)送正是一個具有上述特征的隨機(jī)過程，因此將無線Mesh中數(shù)據(jù)發(fā)送問題抽象描述為馬爾可夫模型。事實(shí)上，馬爾可夫過程可以描述現(xiàn)實(shí)生活中的很多現(xiàn)象如，視頻監(jiān)控系統(tǒng)中的視頻信號、商業(yè)活動中每天的銷售情況、液體中顆粒所做的布朗運(yùn)動等［7］。基于無線Mesh 特點(diǎn)提出的數(shù)據(jù)發(fā)送模型如下：

設(shè)有馬爾可夫過程｛Xn，n∈T｝。其中T 是離散時間集合，T ＝｛0，1，2，…｝；Xn表示隨機(jī)過程，它所有取值的集合可構(gòu)成狀態(tài)空間，即I＝｛1，2，…｝。

定義1 設(shè)某隨機(jī)過程｛Xn，n ∈T｝，如果對任意整數(shù)n∈T 和任意i0，i1，…，in＋1∈I，滿足條件概率式 （1），則稱｛Xn，n∈T｝是馬爾可夫鏈

定義2 條件概率如式 （2）所示

稱為在n時刻馬爾可夫鏈｛Xn，n∈T｝的轉(zhuǎn)移概率，該式中i，j∈I。

一般情況下，轉(zhuǎn)移概率P（n）ij與當(dāng)前時刻n及上一時刻的狀態(tài)有關(guān)。如果對于任意的i，j∈I，｛Xn，n ∈T｝的轉(zhuǎn)移概率P（n）ij都與n無關(guān)，則該馬爾可夫鏈有平穩(wěn)轉(zhuǎn)移概率，可被稱作齊次馬爾可夫鏈?，F(xiàn)實(shí)生活中，很多問題的解決都與當(dāng)前時刻無關(guān)，所以對齊次馬爾可夫鏈的研究比較廣泛和深入。齊次馬爾可夫過程對無線Mesh網(wǎng)絡(luò)的研究也有非常重要的價值。

2 服務(wù)等級算法的提出

2.1 業(yè)務(wù)流的服務(wù)等級設(shè)定與標(biāo)記

對報文服務(wù)等級進(jìn)行設(shè)定與標(biāo)記，區(qū)分不同服務(wù)等級的報文質(zhì)量，從而進(jìn)行合理的調(diào)度。圖1描述了基于無線Mesh網(wǎng)絡(luò)的視頻監(jiān)控系統(tǒng)。按照攝像頭的安放地點(diǎn)將告警信號分為不同的服務(wù)等級，如將金庫內(nèi)的報警信號設(shè)為高服務(wù)等級，電梯內(nèi)的告警信號設(shè)為中服務(wù)等級，銀行大門處的告警信號設(shè)為低服務(wù)等級。服務(wù)等級設(shè)定后，便可根據(jù)業(yè)務(wù)流中標(biāo)記的服務(wù)等級來進(jìn)行隊(duì)列調(diào)度，從而保證告警模塊的要求。

圖1 無線Mesh網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)

我們根據(jù)具體業(yè)務(wù)類型，將服務(wù)等級分為高、中、低3個等級，通過在802.11數(shù)據(jù)幀中對不同服務(wù)等級的報文進(jìn)行標(biāo)記，3個等級的模型設(shè)計(jì)如下：

其中，802.11的控制幀格式如表1，其中，第一行的數(shù)字表示幀位數(shù)。

表1 802.11控制幀格式

考慮RTS幀的控制幀，將Subtype幀子類型的位數(shù)由4位增大至6位，多出的兩位用來標(biāo)記服務(wù)等級的級別。在多出來的兩位中，其服務(wù)等級的級別可見表2。

表2 服務(wù)等級標(biāo)記

即用11代表服務(wù)等級為高的業(yè)務(wù)，10代表服務(wù)等級為中的業(yè)務(wù)，01代表服務(wù)等級為低的業(yè)務(wù)。

2.2 基于服務(wù)等級的碰撞避免算法MPCA

為了解決無線Mesh網(wǎng)絡(luò)環(huán)境下不同服務(wù)等級業(yè)務(wù)的碰撞問題，如低服務(wù)等級業(yè)務(wù)增多從而影響高服務(wù)等級的業(yè)務(wù)帶寬、相同服務(wù)等級業(yè)務(wù)因同時發(fā)送數(shù)據(jù)從而產(chǎn)生碰撞，本文針對無線網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)的告警模塊中存在的不同業(yè)務(wù)類型，提出了一種基于SLA 機(jī)制的沖突避免算法MPCA，該算法通過在MAC 層采用SLA 機(jī)制，針對不同的服務(wù)等級分別調(diào)整最小競爭窗口和當(dāng)前的退避窗口大小，從而盡可能的避免低服務(wù)等級業(yè)務(wù)的數(shù)據(jù)幀突發(fā)給高服務(wù)等級業(yè)務(wù)所帶來的影響，使高服務(wù)等級的業(yè)務(wù)有效的搶占網(wǎng)絡(luò)資源［8］，并通過建立馬爾可夫模型論證了該算法的有效性。

MPCA 算法及功能特性可從兩方面描述：

（1）不同的服務(wù)等級業(yè)務(wù)對應(yīng)不同的退避算法假設(shè)節(jié)點(diǎn)競爭窗口初始值為CW0，最大競爭窗口為CWm。對于本文提出的MPCA 算法，其競爭窗口CW 的變化情況可抽象為：

對于高服務(wù)等級的數(shù)據(jù)業(yè)務(wù)，其Fdec和Finc函數(shù)見式（3）

其中，F(xiàn)dec函數(shù)表示節(jié)點(diǎn)通信成功時競爭窗口的變化情況；Finc函數(shù)表示通信失敗時競爭窗口的變化情況。無論數(shù)據(jù)傳輸是否成功，高服務(wù)等級的競爭窗口都維持CW0不變。

對于中服務(wù)等級業(yè)務(wù)，F(xiàn)dec和Finc函數(shù)見式 （4）

其中，0≤i＜m。若節(jié)點(diǎn)通信成功，則其競爭窗口按照Fdec函數(shù)變化；若節(jié)點(diǎn)通信失敗，則其競爭窗口按照Finc函數(shù)變化。

對于低服務(wù)等級的數(shù)據(jù)業(yè)務(wù)，F(xiàn)dec和Finc函數(shù)見式 （5）

其中，0≤i＜m。若節(jié)點(diǎn)通信成功，則其競爭窗口按照Fdec函數(shù)變化；若節(jié)點(diǎn)通信失敗，則其競爭窗口按照Finc函數(shù)變化。

（2）解決不同服務(wù)等級間的碰撞問題：①避免相同服務(wù)等級之間碰撞避免假設(shè)競爭窗口初始值CW0＝31，當(dāng)兩個高服務(wù)等級業(yè)務(wù)同時發(fā)送數(shù)據(jù)時，退避時間backoff 的取值在 （0，31）之間，所以發(fā)生碰撞的概率為，遠(yuǎn)小于1，即再次發(fā)送沖突的概率很小。②避免不同服務(wù)等級間的碰撞避免當(dāng)兩個不同級別的業(yè)務(wù)碰撞時，較高服務(wù)等級的業(yè)務(wù)退避等待時間比低服務(wù)等級的業(yè)務(wù)短，從而更有利于搶占信道。

石木、土石木結(jié)構(gòu)建筑限于材料的承重能力，平面一般為多開間、小進(jìn)深，主要平面形式有兩間，三間、三間一甩袖、三間兩甩袖，五間、五間一甩袖、五間兩甩袖，七間、七間兩甩袖，有檐廊，無檐廊等幾種類型（圖9）?？垦赂G及石砌錮窯平面多為三孔，相互獨(dú)立，各自開門。

3 基于SLA的MPCA性能分析

3.1 沖突避免機(jī)制的Markov模型

我們將以二維馬爾可夫模型為基礎(chǔ)，對上一節(jié)中設(shè)計(jì)的多服務(wù)等級沖突避免機(jī)制進(jìn)行理論分析。

在基于多服務(wù)等級沖突避免機(jī)制的馬爾可夫模型中，用退避時間和當(dāng)前退避窗口值表示當(dāng)前節(jié)點(diǎn)狀態(tài)，節(jié)點(diǎn)狀態(tài)的轉(zhuǎn)移概率取決于接收端的碰撞概率。

由于針對的是多服務(wù)等級業(yè)務(wù)發(fā)生碰撞的情況，所以分別對高、中、低3個等級的數(shù)據(jù)業(yè)務(wù)均進(jìn)行了Markov建模。通過分析3個等級的沖突避免算法，可將中、低兩個服務(wù)等級的服務(wù)策略抽象為同一數(shù)學(xué)模型，如圖2所示的是高服務(wù)等級業(yè)務(wù)對應(yīng)的沖突避免Markov模型。

圖2 高服務(wù)等級業(yè)務(wù)Markov模型

圖3 表示的是中、低服務(wù)等級業(yè)務(wù)對應(yīng)的沖突避免Markov模型。假定報文發(fā)生沖突的概率是獨(dú)立的，用i／CTC／TTS和CWj表示在時隙TC／TS時刻網(wǎng)絡(luò)中節(jié)點(diǎn)的退避階段以及競爭窗口大小。模型從START 狀態(tài)開始，到DONE狀態(tài)結(jié)束。START 狀態(tài)表示報文在MAC 層即將被調(diào)度階段，DONE 狀態(tài)表示報文成功傳輸完成時的階段。在該模型中，狀態(tài)（i，CWj）表示發(fā)送節(jié)點(diǎn)的狀態(tài)，即退避窗口值為CWj，退避時間的值為i。其中0≤i≤CWj，0≤j≤m。

基于上述分析，中、低服務(wù)等級業(yè)務(wù)的馬爾可夫過程可描述為：

（1）節(jié)點(diǎn)從START 開始以（i，CW0）0≤i≤CW0進(jìn)入退避階段，退避計(jì)數(shù)器的值依次遞減到0，節(jié)點(diǎn)開始發(fā)送RTS－CTS幀。發(fā)送RTS－CTS幀后，節(jié)點(diǎn)可進(jìn)入兩種狀態(tài)：一是發(fā)生RTS－CTS碰撞后狀態(tài)；一是RTS－CTS成功傳輸后狀態(tài)。

圖3 中、低服務(wù)等級業(yè)務(wù)Markov模型

（3）若RTS－CTS交換成功，發(fā)送端開始發(fā)送DATA幀。狀態(tài)（Tk，CWj）1≤k≤TS表示RTS－CTS幀交互成功后，在DATA 發(fā)送過程第k個時隙前節(jié)點(diǎn)狀態(tài)。經(jīng)過TS個時隙后，如果DATA－AKC 交換成功，則馬爾可夫鏈轉(zhuǎn)移到DONE狀態(tài)；若果DATA－ACK 交換失敗，設(shè)失敗的概率為，則發(fā)送端以概率重新進(jìn)入START 狀態(tài)。

3.2 不同服務(wù)等級業(yè)務(wù)網(wǎng)絡(luò)可用帶寬分析

3.2.1 數(shù)據(jù)成功傳輸服務(wù)時間期望值分析

無線Mesh網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)拓?fù)鋱D結(jié)構(gòu)如圖4所示。

圖4 無線視頻監(jiān)控系統(tǒng)網(wǎng)絡(luò)拓?fù)?/p>

在鏈路e，報文服務(wù)時間的期望值等于在馬爾可夫鏈中報文從START 狀態(tài)到DONE 狀態(tài)時整個過程的期望值。針對高服務(wù)等級和中、低服務(wù)等級業(yè)務(wù)服務(wù)時間期望值計(jì)算如下。

（2）中、低服務(wù)等級業(yè)務(wù)：中、低服務(wù)等級業(yè)務(wù)服務(wù)時間期望值如式 （7）所示

基于上述分析，可以看出，數(shù)據(jù)成功傳輸所需服務(wù)時間由兩方面決定：碰撞概率和發(fā)送端的空閑等待時間。采用了服務(wù)等級機(jī)制后，服務(wù)時間明顯減少，如果不采用服務(wù)等級機(jī)制，那么，所有數(shù)據(jù)在鏈路e上的服務(wù)時間期望值都是如式 （8）所示

3.2.2 網(wǎng)絡(luò)可用帶寬分析

基于上節(jié)結(jié)論可知，假定鏈路上源端的發(fā)送速率和服務(wù)時間期望值滿足式 （9）［10］

則可以保證該鏈路e有效的避免碰撞。

式（9）中，ξ為鏈路服務(wù)強(qiáng)度，范圍 （0，1］；υe為鏈路e在避免碰撞情況下的最高發(fā)送速率；E［Se］為服務(wù)時間的期望值。

通過服務(wù)時間和源端發(fā)送速率的關(guān)系，可以得出結(jié)論：采用服務(wù)等級算法后，由于服務(wù)時間減少，使得網(wǎng)絡(luò)的可用帶寬增加。

4 仿真分析

假定信道丟包率為0，數(shù)據(jù)丟失完全是由沖突所致，物理層使用802.11b標(biāo)準(zhǔn)，信道數(shù)據(jù)速率11 Mb／s，流量由UDP協(xié)議的恒定比特率產(chǎn)生。

仿真過程拓?fù)浣Y(jié)構(gòu)基于圖4，數(shù)據(jù)流經(jīng)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)傳送至接收端。在圖5中，生成3條數(shù)據(jù)流，分別從節(jié)點(diǎn)1、5、3發(fā)出經(jīng)由網(wǎng)關(guān)節(jié)點(diǎn)為7 接入internet。其中，節(jié)點(diǎn)1、5、3、6、7中相鄰節(jié)點(diǎn)的橫、縱向距離為200m，節(jié)點(diǎn)2、6、4的縱向距離為100m。

為便于分析，特將圖4拓?fù)渲械臄?shù)據(jù)流向與其對應(yīng)的id值規(guī)定為圖5。

圖5 數(shù)據(jù)流向與ID 值對應(yīng)關(guān)系

即鏈路1－＞2－＞7對應(yīng)的流id為1，鏈路5－＞6－＞7對應(yīng)的流id為2，而鏈路3－＞4－＞7對應(yīng)的流id為3。

圖6～圖8為不同服務(wù)等級業(yè)務(wù)下的節(jié)點(diǎn)發(fā)送速率范圍。其中，圖6是低服務(wù)等級業(yè)務(wù)流在盡量避免沖突情況下的發(fā)送速率范圍，在這種場景下，報文大小為1024B，數(shù)據(jù)速率為11 Mbps；圖7是中服務(wù)等級業(yè)務(wù)流在盡量避免沖突情況下的發(fā)送速率范圍，在這種場景下，報文大小為600B，數(shù)據(jù)速率為11 Mbps；圖8是高服務(wù)等級業(yè)務(wù)流在盡量避免沖突情況下的發(fā)送速率范圍，在這種場景下，報文大小為100B，數(shù)據(jù)速率為11 Mbps。

圖6 低服務(wù)等級業(yè)務(wù)流發(fā)送速率范圍

圖7 中服務(wù)等級業(yè)務(wù)流發(fā)送速率范圍

通過分析，可以發(fā)現(xiàn)，服務(wù)等級越高，節(jié)點(diǎn)發(fā)送的速率范圍越小。假定數(shù)據(jù)流1的服務(wù)等級高，數(shù)據(jù)流2的服務(wù)等級次之。當(dāng)?shù)头?wù)等級的業(yè)務(wù)數(shù)據(jù)突發(fā)與高服務(wù)等級數(shù)據(jù)流產(chǎn)生沖突時，其數(shù)據(jù)包丟失率如圖9所示。

圖8 高服務(wù)等級業(yè)務(wù)流發(fā)送速率范圍

圖9 不同服務(wù)等級業(yè)務(wù)流丟包率對比

經(jīng)仿真分析可看出，MPCA 算法可以很好的保障高服務(wù)等級業(yè)務(wù)流的傳輸，較原始的802.11協(xié)議，其高服務(wù)等級數(shù)據(jù)包的丟失率大大降低。

進(jìn)一步，假定數(shù)據(jù)流1與數(shù)據(jù)流2是相同的服務(wù)等級，當(dāng)這兩個源端同時發(fā)送數(shù)據(jù)產(chǎn)生碰撞時，丟包率如圖10所示。

圖10 相同服務(wù)等級業(yè)務(wù)流丟包率對比

從圖10 可以看出，在相同服務(wù)等級業(yè)務(wù)流沖突時，MPCA 機(jī)制下的數(shù)據(jù)丟包率明顯低于原始802.11協(xié)議下的數(shù)據(jù)丟包率。

5 結(jié)束語

針對無線Mesh網(wǎng)絡(luò)中數(shù)據(jù)傳輸所存在的問題，設(shè)計(jì)了基于服務(wù)等級的沖突避免算法，其創(chuàng)新之處在于：①提出了針對無線Mesh網(wǎng)絡(luò)沖突避免的馬爾可夫模型；②對無線Mesh網(wǎng)絡(luò)環(huán)境下的SLA 機(jī)制進(jìn)行探索性的研究，設(shè)計(jì)適用于無線Mesh網(wǎng)絡(luò)視頻監(jiān)控系統(tǒng)的多服務(wù)等級沖突避免算法MPCA。論文最后通對MPCA 算法的可行性及有效性進(jìn)行了驗(yàn)證分析。

［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 的服務(wù)組合與協(xié)商研究 ［D］.西安：陜西師范大學(xué)，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的服務(wù)質(zhì)量保證與調(diào)度算法的研究與實(shí)現(xiàn) ［D］.西安：西北大學(xué)，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）.［李瑞芳.適于無線多媒體傳感器網(wǎng)絡(luò)的MAC 層退避算法 ［J］.通信學(xué)報，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.