一種新的區(qū)分接入算法及其理論分析*

何曉鴻(武漢交通職業(yè)學(xué)院,湖北 武漢 430065)

一種新的區(qū)分接入算法及其理論分析*

何曉鴻
(武漢交通職業(yè)學(xué)院,湖北 武漢 430065)

文章基于IEEE802.11e EDCA接入機制,提出一種區(qū)分接入算法。不同優(yōu)先級的業(yè)務(wù),使用自適應(yīng)的、不同次數(shù)的RTS請求,可增強高優(yōu)先級業(yè)務(wù)成功接入的概率;針對高優(yōu)先級業(yè)務(wù)之間同時接入的競爭狀況,提出了避讓策略,以降低高優(yōu)先級業(yè)務(wù)之間的碰撞。文章對該算法在馬爾科夫鏈建模的基礎(chǔ)上進行理論分析,證明其能夠優(yōu)化高優(yōu)先級數(shù)據(jù)流的接入成功率,提高高優(yōu)先級數(shù)據(jù)流的飽和吞吐量。

區(qū)分接入算法;服務(wù)質(zhì)量;接入控制;馬爾科夫鏈

隨著網(wǎng)絡(luò)內(nèi)容的不斷豐富,業(yè)務(wù)對網(wǎng)絡(luò)的QoS保證要求也越來越高,但無線Mesh網(wǎng)的不確定因素使其QoS問題非常復(fù)雜,這必然要求無線Mesh網(wǎng)絡(luò)MAC層具有業(yè)務(wù)區(qū)分能力,能夠為不同等級的業(yè)務(wù)提供不同的優(yōu)先級保障。

IEEE802.11e的EDCA定義了背景數(shù)據(jù)盡力而為、視頻、音頻四種接入類,并且分別定義了彼此不同的AIFS仲裁幀間間隔、CWmaxCWmin最大及最小競爭窗口,以保證對不同的接入類提供不同的QoS。然而,它只是一種概率優(yōu)先機制,并不能消除優(yōu)先級較低的數(shù)據(jù)流對優(yōu)先級較高的數(shù)據(jù)流的影響。

基于公平,改善高優(yōu)先級數(shù)據(jù)的傳輸效率,學(xué)者們在MAC層做了大量的研究。文獻[1][2]用分級的微時隙間的競爭使高優(yōu)先級數(shù)據(jù)擁有高接入率。文獻[3][4]調(diào)整信道占用的決策方式,降低沖突概率,從而提高數(shù)據(jù)信道的吞吐量。但以上解決方案都要求網(wǎng)絡(luò)嚴格同步,這在Mesh結(jié)構(gòu)的無線網(wǎng)絡(luò)中是很困難的。文獻[5]根據(jù)業(yè)務(wù)的不同等級定義了一個含有不同時隙數(shù)的超時隙,且退避以超時隙作為單位。以提高高優(yōu)先級數(shù)據(jù)流的傳輸機會,不過當高等級業(yè)務(wù)比較多的時候,反而會降低高等級業(yè)務(wù)的吞吐量。

1 區(qū)分接入算法

本文從提高高優(yōu)先級數(shù)據(jù)接入信道的成功率,減少接入失敗導(dǎo)致的等待延遲,降低等待時間出發(fā),基于IEEE802.11e的EDCF接入方式,提出了一種新的算法,該算法可以在高低優(yōu)先級數(shù)據(jù)流的狀況之下,改善高優(yōu)先級數(shù)據(jù)流的接入成功率。

本文在EDCF的接入時序上做了調(diào)整:針對不同的業(yè)務(wù)優(yōu)先級,用差異性的間隔和重試次數(shù)來發(fā)送RTS幀,有助于較高等級的業(yè)務(wù)成功搶占信道。圖1為改進的接入時序。如圖1所示,高優(yōu)先級的數(shù)據(jù)RTS幀成功預(yù)約信道,接收方回應(yīng)CTS幀,發(fā)送方一旦收到CTS幀,立即進行數(shù)據(jù)發(fā)送;如預(yù)約失敗,則等待UIFS=SIFS+σ× slottime,σ∈(0,1,2)間隔,發(fā)送RTS請求幀,σ隨機取0,1,2,如成功,接收方發(fā)送CTS幀,發(fā)送方收到以后則發(fā)送數(shù)據(jù);如失敗進入退避。對中等優(yōu)先級業(yè)務(wù),當信道預(yù)約成功時,獲取發(fā)送機會;但如果RTS預(yù)約失敗,則可以等待MIFS=SIFS +3×slottime間隔,發(fā)送RTS請求幀,預(yù)約成功數(shù)據(jù)流則發(fā)送,失敗則開始退避過程。對低優(yōu)先級業(yè)務(wù),則沒有再次預(yù)約的機會,RTS幀如果發(fā)生了碰撞,預(yù)約失敗的話,將直接進入退避過程。

圖1 區(qū)分接入算法機制接入時序

區(qū)分接入算法對于非低優(yōu)先級數(shù)據(jù)在第一次發(fā)送RTS幀的時候,如預(yù)約失敗將第二次發(fā)送RTS請求數(shù)據(jù)幀,從而加大預(yù)約成功的概率。而低優(yōu)先級數(shù)據(jù)只能發(fā)送一次請求,如果預(yù)約失敗將會進行退避。另外,高優(yōu)先級數(shù)據(jù)流和中等優(yōu)先級的數(shù)據(jù)流在第一次預(yù)約失敗的情況下,第二次發(fā)送RTS幀的發(fā)送間隔也是不同的。確保了高優(yōu)先級數(shù)據(jù)預(yù)約成功的概率。文獻[6]也提出了一種RTS幀多次預(yù)約的算法,它在高優(yōu)先級數(shù)據(jù)進行信道預(yù)約時,使用了背靠背的多個RTS幀,這種做法導(dǎo)致在首次預(yù)約成功后,也會連續(xù)地傳送多個RTS幀,這無庸置疑浪費了信道帶寬。而本算法在信道預(yù)約成功時,將不重復(fù)發(fā)送RTS幀,自然降低了不需要的控制幀在帶寬上的消耗。而且一旦高優(yōu)先級數(shù)據(jù)幀和低優(yōu)先級數(shù)據(jù)幀產(chǎn)生沖突時,優(yōu)先級較高的數(shù)據(jù)流可以通過第二次的RTS請求幀搶占信道,從而降低了因為較低優(yōu)先級數(shù)據(jù)流的存在而產(chǎn)生的碰撞,同時優(yōu)先級較低的數(shù)據(jù)流因為發(fā)送失敗,會加大退避的窗口,發(fā)送概率則會進一步降低,優(yōu)先級較高的數(shù)據(jù)流獲取發(fā)送機會的概率則會更大。此外,由于高優(yōu)先級數(shù)據(jù)再次發(fā)送RTS幀的間隔是隨機調(diào)整的,這樣也相應(yīng)降低了多個高優(yōu)先級數(shù)據(jù)流在同一時間同時接入信道而產(chǎn)生的碰撞。

綜上所述,本文提出的區(qū)分接入算法能夠降低優(yōu)先級較低的數(shù)據(jù)流對優(yōu)先級較高的數(shù)據(jù)流的影響,進而加大對高優(yōu)先級數(shù)據(jù)業(yè)務(wù)服務(wù)質(zhì)量的保障。

2 理論建模及分析

假設(shè)同一沖突域的無線Mesh網(wǎng)絡(luò)中包含相互獨立且共享信道的n個節(jié)點,則單個節(jié)點的信道競爭過程分析如下,若k(t)作為其在時刻t的退避等級,取值范圍在[0,m]內(nèi);v(t)表示在時刻t,該節(jié)點的退避時隙計數(shù)器的取值,取值范圍在[0,Wi-1]內(nèi),其中Wi=2iW0,W0=CWmin,i∈[0, m]為該節(jié)點退避等級。則k(t)和v(t)分別是一個隨機過程,本文把此兩隨機過程看成一個整體,用二維的隨機過程{k(t),v(t)}來表述此站點的競爭信道過程。

設(shè)數(shù)據(jù)幀的碰撞概率p彼此獨立且固定。二維隨機過程在t+1時刻的狀況{k(t+1),v(t+ 1)}只與前的一個時刻狀態(tài){k(t),v(t)}相關(guān),且狀態(tài)、時間皆為離散,那么隨機過程{k(t),v(t)}為二維Markov鏈。此外,在進行退避過程中,各節(jié)點信道為空閑,則用一樣的概率來減少退避計數(shù)值。如圖2所示。

公式(2)表明在退避的過程中,計數(shù)器在每個時隙減1;公式(3)表明在i為退避級數(shù)的時候,如果發(fā)送失敗,退避等級加1,退避計數(shù)器的值隨機的從[0,Wi+1-1]中取值;公式(4)表明,如果退避級數(shù)已達最大值,發(fā)送失敗后,退避等級不發(fā)生變化;公式(5)表明,發(fā)送成功后,退避等級回到最小值0。

如公式(6)所示:

從圖2所示的Markov模型能夠得到在穩(wěn)態(tài)下各個狀態(tài)之間的關(guān)系:

對任意的j∈[0,Wi-1]

全部vi,j都能夠用v0,0和p來表示,且=1,所以

因為當退避計時器減到零時,站點即發(fā)送數(shù)據(jù)包。所以節(jié)點在發(fā)送數(shù)據(jù)的概率是

設(shè)最小競爭窗口 W1為高優(yōu)先級的窗口值,最小競爭窗口 W2為中等優(yōu)先級的窗口值,最小競爭窗口W3為中等優(yōu)先級的窗口值,那么,高優(yōu)先級發(fā)送數(shù)據(jù)的概率r1,中等優(yōu)先級發(fā)送數(shù)據(jù)的概率r2,低優(yōu)先級發(fā)送數(shù)據(jù)的概率r3分別為:

p1、p2、p3依次是數(shù)據(jù)流發(fā)送時高優(yōu)先級、中等優(yōu)先級以及低優(yōu)先級的碰撞概率。n1、n2、n3分別是高優(yōu)先級的節(jié)點數(shù)目、中等優(yōu)先級的節(jié)點數(shù)目和低優(yōu)先級的節(jié)點數(shù)目。則對于本文算法的接入流程有:

所有站點競爭信道的過程中任意時隙內(nèi),至少有一個站點發(fā)送數(shù)據(jù)也就是信道忙的概率為:

ps1、ps2、ps3分別為高中低優(yōu)先級數(shù)據(jù)流發(fā)送成功的概率,ps11、ps22分別為在無碰撞情況下,且無更高級數(shù)據(jù)流發(fā)送時,高中優(yōu)先級數(shù)據(jù)流成功發(fā)送的概率,ps12、ps13分別為高優(yōu)先級數(shù)據(jù)流與中、低等優(yōu)先級數(shù)據(jù)流發(fā)生碰撞的狀況下的發(fā)幀成功的概率, ps23為在沒有高優(yōu)先級數(shù)據(jù)發(fā)送的條件之下,中等優(yōu)先級與低優(yōu)先級數(shù)據(jù)流發(fā)生碰撞時,中等優(yōu)先級成功發(fā)送的概率。pc1、pc2、pc3分別為在沒有更高優(yōu)先級數(shù)據(jù)流發(fā)送時,高、中、低優(yōu)先級數(shù)據(jù)流和同等優(yōu)先級之間發(fā)生碰撞且發(fā)送成功的概率。pc11、pc12分別表示高優(yōu)先級數(shù)據(jù)流之間發(fā)生了碰撞,但發(fā)送成功的概率和發(fā)送失敗的概率。bs11、bs12、bs13、bs22、bs23、bs3、bc11、bc12、bc2和bc3對應(yīng)著其占用信道的時長:

從上面的分析,高優(yōu)先級數(shù)據(jù)流、中等優(yōu)先級數(shù)據(jù)流、低優(yōu)先級數(shù)據(jù)流的飽和吞吐量分別為公式(36)、(37)、(38):

θ為單個空時隙的持續(xù)時間,E[data]為傳送的平均凈荷時間。作為IEEE802.11e EDCF的機制,高優(yōu)先級數(shù)據(jù)流的發(fā)送成功概率,會被較低優(yōu)先級的數(shù)據(jù)流影響,可是,本文提出的算法理論上,從公式(14)、(15)(16)中可以看出,發(fā)送數(shù)據(jù)幀時,因為碰撞導(dǎo)致失敗的概率只會被高優(yōu)先級的數(shù)據(jù)流所影響。此外,公式(18)、(19)、(20)中可以看出,在不同優(yōu)先級數(shù)據(jù)流的站點數(shù)和發(fā)幀概率一樣時,較高優(yōu)先級的數(shù)據(jù)流發(fā)送數(shù)據(jù)的成功概率要高于較低優(yōu)先級數(shù)據(jù)流。進而,公式(36)、(37)、(38)能夠得到,較高優(yōu)先級的飽和吞吐量也要比較低優(yōu)先級數(shù)據(jù)流要高。

3 結(jié)論

本文基于IEEE802.11e EDCA接入機制,提出了一種新的區(qū)分接入算法。該算法對優(yōu)先級不同的業(yè)務(wù),使用自適應(yīng)的、變次數(shù)的RTS請求,加強了高優(yōu)先級數(shù)據(jù)流的成功接入概率。此外,對于高優(yōu)先級業(yè)務(wù)同時接入的而發(fā)生競爭的狀況,提出了相應(yīng)的避讓策略,減輕了高優(yōu)先級業(yè)務(wù)之間的碰撞。而后,本文對該算法在馬爾科夫鏈建模的基礎(chǔ)上,進行了理論分析,證明了其能夠優(yōu)化高優(yōu)先級數(shù)據(jù)流的接入成功率,提高高優(yōu)先級數(shù)據(jù)流的飽和吞吐量。

[1]Jiang Sehngming,He Dajiang,Ling Xinhua,et a1.A Simple Distributed PRMA for MANETs[J].IEEE Transactions on Vehicular Technology,2002,(3): 293-305.

[2]You T,Yeh C-H,Hassanein HS.A New Class of Collision-free MAC Protocols for Ad Hoc Wireless Networks[A].Proceedings of the Eighth IEEE International Symposium on Computers and Communication(ISCC'03)[C].2003:843-848.

[3]Tantra J W.Chuan Heng Foh.Achieving near maximum throughput in IEEE802.11 WLANs with contention tone[J].IEEE Communications Letters, 2006,(9):658-660.

[4]Yang Xue,Vaidya Nitin H.A Wireless MAC Protocol Using Implicit Pipelining[J].IEEE Transactions on Mobile Computing,2006,(3):258-273.

[5]康凱,胡海波,林孝康.一種新的用于IEEE 802. 11e EDCA中提供QoS的方法[J].電子與信息學(xué)報,2007,(12):2991-2995.

[6]王朝翔,韋蓉,丁煒.帶擁塞控制的多預(yù)約MAC協(xié)議[J].電子科技大學(xué)學(xué)報,2008,(5):765-768.

10.3969/j.issn.1672-9846.2014.01.018

TN929.5

A

1672-9846(2014)01-0074-04

2014-01-07

何曉鴻(1976-),女,湖北漢川人,武漢交通職業(yè)學(xué)院電子與信息工程學(xué)院教師,主要從事電子與信息工程研究。