龐玲

（四川行政學(xué)院 計(jì)算機(jī)系，四川 成都 610072）

為滿足不同業(yè)務(wù)的QoS要求，IEEE802.l1e在DCF的設(shè)計(jì)基礎(chǔ)上，提出了EDCA這種有QoS增強(qiáng)的競爭接入方案。EDCA將業(yè)務(wù)分為8個(gè)優(yōu)先級 （User Priority，UP），并定義了4種接入類別（access category，AC）來支持業(yè)務(wù)的傳輸。記第k 類接入類別為 AC[k]，k=1，2，…，k，站點(diǎn)中每個(gè) AC[k]對應(yīng)一個(gè)獨(dú)立的發(fā)送隊(duì)列；第幾個(gè)級別（隊(duì)列）有3個(gè)參數(shù)：初始競爭窗口長度CWmin[k]、最大竟?fàn)幋翱陂L度CWmax[k]和幀間隔時(shí)間AIFSD[k]。AC[k]值越大，對應(yīng)業(yè)務(wù)的優(yōu)先級就越高，上述3個(gè)參數(shù)的取值就越小，保證業(yè)務(wù)以較高優(yōu)先級接入無線信道。這3個(gè)參數(shù)分別對應(yīng)于DCF中的CWmin、CWmax和DCF幀間隔時(shí)間DIFS[1]。在DCF中，對所有業(yè)務(wù)這3個(gè)參數(shù)的取值都相同。

各隊(duì)列的競爭都基于CSMA/CA協(xié)議，結(jié)合二進(jìn)制指數(shù)退避算法。每個(gè)包在發(fā)送之前都要先偵聽信道，若信道空閑AIFSD[k]，則直接發(fā)送，否則進(jìn)入退避過程。退避時(shí)隙數(shù)在[0，CW[k]-1]的范圍內(nèi)隨機(jī)選取。CW[k]的初始值為CWmin[k]，每發(fā)生一次外部碰撞（至少兩個(gè)站點(diǎn)接入信道），CW[k]的值加倍，達(dá)到CWmax[k]后就保持不變。每次退避從檢測到信道空閑AIFSD[k]后開始，每經(jīng)過一個(gè)空閑時(shí)隙，退避計(jì)數(shù)器的值減1，退避計(jì)數(shù)器的值最先減到0的數(shù)據(jù)包占用信道。每個(gè)站點(diǎn)每次只能有一個(gè)數(shù)據(jù)包占用信道，若站點(diǎn)內(nèi)有不只一個(gè)AC隊(duì)列的頭數(shù)據(jù)包退避計(jì)數(shù)器的值同時(shí)達(dá)到0，則發(fā)生內(nèi)部碰撞，屬于較高優(yōu)先級隊(duì)列的數(shù)據(jù)包占用信道，其他的數(shù)據(jù)包進(jìn)入新一輪的退避且重傳計(jì)數(shù)器的值加1。當(dāng)數(shù)據(jù)包發(fā)送時(shí)，若還有其他站點(diǎn)的數(shù)據(jù)包正在發(fā)送，則發(fā)生外部碰撞。若數(shù)據(jù)包發(fā)生外部碰撞，該數(shù)據(jù)包所在隊(duì)列的重傳計(jì)數(shù)器值加1，進(jìn)入新一輪退避。當(dāng)達(dá)到最大重傳次數(shù)限制時(shí)，無論該數(shù)據(jù)包是否成功傳送，都被從隊(duì)列中刪除，重傳計(jì)數(shù)器的值清零，進(jìn)入下一個(gè)數(shù)據(jù)包的退避過程。

1 建立網(wǎng)絡(luò)傳輸模型

根據(jù)EDCA接入方式采用的是帶沖突避免的載波偵聽多路訪問協(xié)議（CSMA/CA），節(jié)點(diǎn)內(nèi)部存在四個(gè)隊(duì)列緩存到來的業(yè)務(wù)，每個(gè)隊(duì)列采用相應(yīng)的接入等級（AC）參數(shù)競爭信道，下面對該網(wǎng)絡(luò)傳輸模型進(jìn)行分析。不同接入等級的參數(shù)包括仲裁幀間隔（AIFS），最小、最大競爭窗（CWmin[AC]，CWmax[AC]）等。在EDCA接入方式中，有數(shù)據(jù)發(fā)送的隊(duì)列在檢測到信道空閑AIFS[AC]時(shí)間后，進(jìn)入后退過程。優(yōu)先級高的業(yè)務(wù)，AIFS[AC]時(shí)間越短[2]。下式是一種常見的AIFS[AC]的計(jì)算公式：

AIFS[AC]=AIFSN[AC]×SlotTime+SLFSTime

式中SlotTime和SIFSTime為物理層參數(shù)。

當(dāng)有優(yōu)先級為i，j的兩種業(yè)務(wù)同時(shí)競爭信道時(shí)，如果i優(yōu)先級高于 j，則有 CWmin[i]

文中共黨員以下給出網(wǎng)絡(luò)模型3部分的詳細(xì)分析過程。首先列出兩點(diǎn)約定：

1）為了簡單說明問題，本文不考慮節(jié)點(diǎn)內(nèi)部的調(diào)度算法，即設(shè)定每個(gè)業(yè)務(wù)為一個(gè)獨(dú)立的信道競爭實(shí)體，并不影響802.11 e接入機(jī)制在多跳環(huán)境下的性能研究。

2）設(shè)定第i類業(yè)務(wù)服從到達(dá)率為λi的泊松過程[3]。

隱藏終端影響下的二進(jìn)制指數(shù)后退過程：

對多跳無線網(wǎng)絡(luò)中沖突率的分析首先從單跳飽和情況開始，逐步推廣到多跳情況，從而在模型中反映出隱藏終端對802.11e接入機(jī)制帶來的影響。

首先設(shè)節(jié)點(diǎn)的偵聽范圍內(nèi)第 類業(yè)務(wù)的個(gè)數(shù)為Ni（i=0，1，2，3）。在飽和狀態(tài)下，業(yè)務(wù)的發(fā)送隊(duì)列時(shí)時(shí)處于滿狀態(tài)，業(yè)務(wù)任何一次被服務(wù)的過程（發(fā)送過程）都要經(jīng)歷二進(jìn)制指數(shù)后退。文中用Wi，j表示第i類業(yè)務(wù)處在第j個(gè)后退級數(shù)時(shí)的競爭窗口，則 Wi，0=CWmin[i]；m 為最大重傳次數(shù)；m′為最大后退級數(shù)；CWmax[i]=2m′CWmin[i]。業(yè)務(wù)從競爭窗中隨機(jī)選擇一個(gè)時(shí)間值進(jìn)行后退延遲，則第一次后退延遲的平均時(shí)間可以表示為Wi，0/2（時(shí)隙）。令第i類業(yè)務(wù)在后退計(jì)數(shù)器變?yōu)?時(shí)，發(fā)送數(shù)據(jù)發(fā)生沖突的概率為ci，則成功發(fā)送的概率為1-ci。一旦沖突發(fā)生，競爭窗長度將擴(kuò)大為原來的兩倍，因此第i類業(yè)務(wù)成功發(fā)送數(shù)據(jù)幀所需后退時(shí)間的平均值wb_i（m

第i類業(yè)務(wù)A開始占用信道傳輸時(shí)，與其他某個(gè)正要傳輸?shù)臉I(yè)務(wù)B發(fā)生沖突的概率為wi，0。由于802.11e EDCA的載波偵聽特性，B正在發(fā)送數(shù)據(jù)時(shí)，A的后退計(jì)數(shù)器凍結(jié)，從A的時(shí)間線上觀察B的行為，B的傳輸僅占用A時(shí)間線上的一個(gè)時(shí)隙，即B傳輸過程中的第一個(gè)時(shí)隙。由于A和B的后退過程相互獨(dú)立，當(dāng)B傳輸完畢，信道空閑，A的后退計(jì)數(shù)器繼續(xù)遞減，在它的時(shí)間線上觀察到B始終保持沉默，如圖1所示。由于A在時(shí)間線上的任何時(shí)刻都可能發(fā)送數(shù)據(jù)，與B發(fā)生沖突的概率為1/wb_i（B與A是同級別業(yè)務(wù)）或者為1/wb_ib0i/wb_i，（B與A不是同級別業(yè)務(wù)），則第i類業(yè)務(wù)與其他業(yè)務(wù)發(fā)生沖突的概率ci可以表示為：

即

由上式的結(jié)果可以推導(dǎo)非飽和負(fù)載下的沖突率。設(shè)b0i為第i類業(yè)務(wù)緩存隊(duì)列非空的概率，由于第i類業(yè)務(wù)平均后退時(shí)間為wb_i，則在給定的一個(gè)時(shí)隙內(nèi)i類業(yè)務(wù)發(fā)送數(shù)據(jù)的概率為（由飽和情況擴(kuò)展到非飽和情況得出）：

圖1 在第i類業(yè)務(wù)A的時(shí)間線上觀察B的行為Fig.1 A class of business in the first time i observed B’s behavior online

圖1的拓?fù)浣Y(jié)構(gòu)顯示了一個(gè)典型的隱藏終端問題。節(jié)點(diǎn)C處于A的偵聽范圍之外，C的傳輸對B來自于A的數(shù)據(jù)接收產(chǎn)生干擾，C為隱藏終端。B要成功接收A發(fā)送的RTS，隱藏終端C的傳輸必須延遲一定的時(shí)間Tv。從節(jié)點(diǎn)A觀察網(wǎng)絡(luò)，Tv=2（RTS+SIFS），如圖2所示。如果A在t=0時(shí)刻發(fā)送RTS到節(jié)點(diǎn)B，可以觀察到C在[t1，t2]時(shí)間段內(nèi)的任何時(shí)刻發(fā)送RTS都將導(dǎo)致在節(jié)點(diǎn)B發(fā)生沖突。令Rh為Tv與時(shí)隙時(shí)間的比，有：

在單跳無線網(wǎng)絡(luò)中，所有節(jié)點(diǎn)處于相互的偵聽范圍內(nèi)，A和C的沖突只可能發(fā)生在相同的時(shí)隙中；而在多跳無線網(wǎng)絡(luò)中，由于C為隱藏終端，在Rh的任何一個(gè)時(shí)隙內(nèi)，A和C的RTS都可能在B發(fā)生沖突。

圖2 Tv示意圖Fig.2 Tv schematic

在節(jié)點(diǎn)的偵聽范圍內(nèi)，第 i類業(yè)務(wù)的個(gè)數(shù)為 Ni（i=0，1，2，3）。在隱藏區(qū)域內(nèi)，各類業(yè)務(wù)的個(gè)數(shù)設(shè)為 Nh_k（k=0，1，2，3），則對第i類業(yè)務(wù)發(fā)送RTS產(chǎn)生干擾的優(yōu)先級業(yè)務(wù)的總數(shù)可以表示為[4]：

由此得出，隱藏終端影響下第i類業(yè)務(wù)發(fā)送數(shù)據(jù)發(fā)生沖突的概率可以表示為：

為了方便運(yùn)算，這里只討論RTS/CTS的接入方式，其計(jì)算方法同樣適用于基本的接入方式。在RTS/CTS接入方式下，同樣存在數(shù)據(jù)幀的發(fā)送受隱藏終端的影響而發(fā)生沖突。有研究表明，在RTS/CTS接入方式下，數(shù)據(jù)幀發(fā)生沖突的概率遠(yuǎn)遠(yuǎn)小于RTS發(fā)生沖突的概率ci，因此這里僅考慮RTS發(fā)生的沖突。求得了第i類業(yè)務(wù)發(fā)送數(shù)據(jù)發(fā)生沖突的概率Ci，根據(jù)Markov鏈分析方法，可求得第i類業(yè)務(wù)在后退計(jì)數(shù)器遞減到0時(shí)發(fā)送數(shù)據(jù)的概率：

2 分析排隊(duì)模型

基于前面的分析，在802.11e EDCA接入方式下，每類業(yè)務(wù)的緩存隊(duì)列可以看做M/G/1/K排隊(duì)模型。令ε（t）（t≥0）表示在t時(shí)刻排隊(duì)系統(tǒng)所處的狀態(tài)，則ε（t）的狀態(tài)空間為S={I，A0，A1，A2，…，AK}。 其中：AK表示在信道忙的條件下排隊(duì)隊(duì)長為k；I表示信道空閑，排隊(duì)隊(duì)列為空。由于MAC層服務(wù)時(shí)間是一般分布，對任選的一個(gè)時(shí)刻t，正在接收發(fā)送過程的數(shù)據(jù)幀可能還沒有發(fā)送完成，從時(shí)刻t起的剩余服務(wù)時(shí)間分布不再具有無記憶性，于是排隊(duì)系統(tǒng)的隊(duì)長不再具有Markov性質(zhì)[5]。如令tn為第n個(gè)數(shù)據(jù)包服務(wù)完畢離開排隊(duì)系統(tǒng)的時(shí)刻，則 εn=ε（），εn表示在 tn時(shí)刻之前排隊(duì)系統(tǒng)所處的狀態(tài)，可以認(rèn)為εn是隊(duì)長過程的嵌入Markov鏈 。此時(shí)嵌入Markov鏈的狀態(tài)空間為 S′={I，A0，A1，A2，…，AK}。 令 Pi，j表示狀態(tài) Ai到Aj的一步轉(zhuǎn)移概率，有[6]：

令a（k）表示在一個(gè)數(shù)據(jù)幀的服務(wù)時(shí)間內(nèi)有k個(gè)幀到達(dá)的概率，由于i類業(yè)務(wù)服從到達(dá)率為λi的泊松過程，則有：

一步轉(zhuǎn)移概率pij的平穩(wěn)分布可以表示為π={πn}，有πP=π。基于M/G/1/K排隊(duì)模型，可以計(jì)算隊(duì)列空的概率P0和隊(duì)列滿的概率：

第i類業(yè)務(wù)的吞吐率Si可以表示為

3 結(jié)束語

提出了一種針對IEEE802.1le標(biāo)準(zhǔn)中EDCA機(jī)制的載波偵聽多路訪問協(xié)議分析模型，該模型采用接入等級（AC）參數(shù)競爭信道的方式準(zhǔn)確地描述了EDCA的服務(wù)區(qū)分機(jī)制，并在此基礎(chǔ)上描述了不同優(yōu)先級的平均接入延遲性能，此外該模型還可以用于分析不同接入等級之間的最大最小競爭窗口，重傳次數(shù)等參數(shù)對于業(yè)務(wù)服務(wù)質(zhì)量的影響。

通過對無線局域網(wǎng)絡(luò)模型的建立與分析，為進(jìn)一步定量地分析網(wǎng)絡(luò)性能、設(shè)計(jì)更優(yōu)的傳輸控制協(xié)議奠定了基礎(chǔ)。

[1]ANSI/IEEE Std.802.11，ISO/IEC 8802-11:1999（E），Wireless LAN medium access control（MAC）and physical layer（PHY）specifications[S].1999.

[2]吳大鵬，甄巖，武穆清，等.IEEE802.11e無線局域網(wǎng)中的接入延遲分析模型[J].傳感技術(shù)學(xué)報(bào)，2008，21（12）：2044-2049.WU Da-peng，ZHEN Yan，WU Mu-qing，et al.Analysis model of MAC access delay in IEEE 802.11e wireless LAN[J].Chinese Journal of Sensors and Actuators，2008，21 （12）：2044-2049.

[3]厲群，王春曉.ROHC協(xié)議分析與建模[J].計(jì)算機(jī)工程與計(jì)，2008，29（13）:3309-3312.LI Qun，WANG Chun-xiao.ROHC protocol analysis and modeling[J].Computer Engineering andDesign，2008，29（13）:3309-3312.

[4]張國鵬，鄒向毅，趙力強(qiáng)，等.基于效用最大化的IEEE 802.11 DCF性能分析及改進(jìn)[J].電子與信息學(xué)報(bào)，2008，30（12）：3027-3030.ZHANG Guo-peng，ZOU Xiang-yi，ZHAO Li-qiang，et al.Based on utility maximization of IEEE 802.11 DCF performance analysis and improvement[J].Electronics and Information Technology，2008，30（12）:3027-3030.

[5]吳亞軍，胡愛群，宋宇波.無線局域網(wǎng)協(xié)議分析系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2008，34（22）：140-142.WU Ya-jun，HU Ai-qun，SONG Yu-bo.Wireless LAN protocol analyzer system design and implementation[J].Computer Engineering，2008，34（22）:140-142.

[6]王琳珠，范亞芹，胡可剛.無線LAN的性能模型設(shè)計(jì)[J].吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2008，26（5）：476-479.WANG Lin-zhu，F(xiàn)AN Ya-qin，HU Ke-gang.Wireless LAN perfor-mance modeling[J]. Jilin University:Information Science Editor，2008，26 （5）:476-479.

[7]王靜，戎蒙恬，劉超.無線局域網(wǎng)分布式自適應(yīng)信道分配問題的研究[J].計(jì)算機(jī)仿真， 2008，25（7）：117-120.WANG Jing，RONG Meng-tian，LIU Chao.Wireless LAN distributed adaptive channel allocationresearch[J].Computer Simulation，2008，25（7）:117-120.