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

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

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

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

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

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

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

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

1 區(qū)分接入算法

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

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

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

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

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

2 理論建模及分析

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

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

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

如公式(6)所示:

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

對(duì)任意的j∈[0,Wi-1]

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

因?yàn)楫?dāng)退避計(jì)時(shí)器減到零時(shí),站點(diǎn)即發(fā)送數(shù)據(jù)包。所以節(jié)點(diǎn)在發(fā)送數(shù)據(jù)的概率是

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

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

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

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

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

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

3 結(jié)論

本文基于IEEE802.11e EDCA接入機(jī)制,提出了一種新的區(qū)分接入算法。該算法對(duì)優(yōu)先級(jí)不同的業(yè)務(wù),使用自適應(yīng)的、變次數(shù)的RTS請(qǐng)求,加強(qiáng)了高優(yōu)先級(jí)數(shù)據(jù)流的成功接入概率。此外,對(duì)于高優(yōu)先級(jí)業(yè)務(wù)同時(shí)接入的而發(fā)生競(jìng)爭(zhēng)的狀況,提出了相應(yīng)的避讓策略,減輕了高優(yōu)先級(jí)業(yè)務(wù)之間的碰撞。而后,本文對(duì)該算法在馬爾科夫鏈建模的基礎(chǔ)上,進(jìn)行了理論分析,證明了其能夠優(yōu)化高優(yōu)先級(jí)數(shù)據(jù)流的接入成功率,提高高優(yōu)先級(jí)數(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é)報(bào),2007,(12):2991-2995.

[6]王朝翔,韋蓉,丁煒.帶擁塞控制的多預(yù)約MAC協(xié)議[J].電子科技大學(xué)學(xué)報(bào),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é)院教師,主要從事電子與信息工程研究。