無(wú)線局域網(wǎng)絡(luò)模型建立與性能分析

龐玲

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

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

各隊(duì)列的競(jìng)爭(zhēng)都基于CSMA/CA協(xié)議，結(jié)合二進(jìn)制指數(shù)退避算法。每個(gè)包在發(fā)送之前都要先偵聽信道，若信道空閑AIFSD[k]，則直接發(fā)送，否則進(jìn)入退避過(guò)程。退避時(shí)隙數(shù)在[0，CW[k]-1]的范圍內(nèi)隨機(jī)選取。CW[k]的初始值為CWmin[k]，每發(fā)生一次外部碰撞（至少兩個(gè)站點(diǎn)接入信道），CW[k]的值加倍，達(dá)到CWmax[k]后就保持不變。每次退避從檢測(cè)到信道空閑AIFSD[k]后開始，每經(jīng)過(guò)一個(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)先級(jí)隊(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í)，無(wú)論該數(shù)據(jù)包是否成功傳送，都被從隊(duì)列中刪除，重傳計(jì)數(shù)器的值清零，進(jìn)入下一個(gè)數(shù)據(jù)包的退避過(guò)程。

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

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

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

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

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

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

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

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

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

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

首先設(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ù)的過(guò)程（發(fā)送過(guò)程）都要經(jīng)歷二進(jìn)制指數(shù)后退。文中用Wi，j表示第i類業(yè)務(wù)處在第j個(gè)后退級(jí)數(shù)時(shí)的競(jìng)爭(zhēng)窗口，則 Wi，0=CWmin[i]；m 為最大重傳次數(shù)；m′為最大后退級(jí)數(shù)；CWmax[i]=2m′CWmin[i]。業(yè)務(wù)從競(jìng)爭(zhēng)窗中隨機(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ā)生，競(jìng)爭(zhēng)窗長(zhǎng)度將擴(kuò)大為原來(lái)的兩倍，因此第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傳輸過(guò)程中的第一個(gè)時(shí)隙。由于A和B的后退過(guò)程相互獨(dú)立，當(dāng)B傳輸完畢，信道空閑，A的后退計(jì)數(shù)器繼續(xù)遞減，在它的時(shí)間線上觀察到B始終保持沉默，如圖1所示。由于A在時(shí)間線上的任何時(shí)刻都可能發(fā)送數(shù)據(jù)，與B發(fā)生沖突的概率為1/wb_i（B與A是同級(jí)別業(yè)務(wù)）或者為1/wb_ib0i/wb_i，（B與A不是同級(jí)別業(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è)典型的隱藏終端問(wèn)題。節(jié)點(diǎn)C處于A的偵聽范圍之外，C的傳輸對(duì)B來(lái)自于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ú)線網(wǎng)絡(luò)中，所有節(jié)點(diǎn)處于相互的偵聽范圍內(nèi)，A和C的沖突只可能發(fā)生在相同的時(shí)隙中；而在多跳無(wú)線網(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），則對(duì)第i類業(yè)務(wù)發(fā)送RTS產(chǎn)生干擾的優(yōu)先級(jí)業(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ì)長(zhǎng)為k；I表示信道空閑，排隊(duì)隊(duì)列為空。由于MAC層服務(wù)時(shí)間是一般分布，對(duì)任選的一個(gè)時(shí)刻t，正在接收發(fā)送過(guò)程的數(shù)據(jù)幀可能還沒(méi)有發(fā)送完成，從時(shí)刻t起的剩余服務(wù)時(shí)間分布不再具有無(wú)記憶性，于是排隊(duì)系統(tǒng)的隊(duì)長(zhǎng)不再具有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ì)長(zhǎng)過(guò)程的嵌入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的泊松過(guò)程，則有：

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

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

3 結(jié)束語(yǔ)

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

通過(guò)對(duì)無(wú)線局域網(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ú)線局域網(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]張國(guó)鵬，鄒向毅，趙力強(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]吳亞軍，胡愛(ài)群，宋宇波.無(wú)線局域網(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]王琳珠，范亞芹，胡可剛.無(wú)線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ú)線局域網(wǎng)分布式自適應(yīng)信道分配問(wèn)題的研究[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.