無線局域網絡模型建立與性能分析

龐玲

（四川行政學院 計算機系，四川 成都 610072）

為滿足不同業務的QoS要求，IEEE802.l1e在DCF的設計基礎上，提出了EDCA這種有QoS增強的競爭接入方案。EDCA將業務分為8個優先級 （User Priority，UP），并定義了4種接入類別（access category，AC）來支持業務的傳輸。記第k 類接入類別為 AC[k]，k=1，2，…，k，站點中每個 AC[k]對應一個獨立的發送隊列；第幾個級別（隊列）有3個參數：初始競爭窗口長度CWmin[k]、最大竟爭窗口長度CWmax[k]和幀間隔時間AIFSD[k]。AC[k]值越大，對應業務的優先級就越高，上述3個參數的取值就越小，保證業務以較高優先級接入無線信道。這3個參數分別對應于DCF中的CWmin、CWmax和DCF幀間隔時間DIFS[1]。在DCF中，對所有業務這3個參數的取值都相同。

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

1 建立網絡傳輸模型

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

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

式中SlotTime和SIFSTime為物理層參數。

當有優先級為i，j的兩種業務同時競爭信道時，如果i優先級高于 j，則有 CWmin[i]

文中共黨員以下給出網絡模型3部分的詳細分析過程。首先列出兩點約定：

1）為了簡單說明問題，本文不考慮節點內部的調度算法，即設定每個業務為一個獨立的信道競爭實體，并不影響802.11 e接入機制在多跳環境下的性能研究。

2）設定第i類業務服從到達率為λi的泊松過程[3]。

隱藏終端影響下的二進制指數后退過程：

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

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

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

即

由上式的結果可以推導非飽和負載下的沖突率。設b0i為第i類業務緩存隊列非空的概率，由于第i類業務平均后退時間為wb_i，則在給定的一個時隙內i類業務發送數據的概率為（由飽和情況擴展到非飽和情況得出）：

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

圖1的拓撲結構顯示了一個典型的隱藏終端問題。節點C處于A的偵聽范圍之外，C的傳輸對B來自于A的數據接收產生干擾，C為隱藏終端。B要成功接收A發送的RTS，隱藏終端C的傳輸必須延遲一定的時間Tv。從節點A觀察網絡，Tv=2（RTS+SIFS），如圖2所示。如果A在t=0時刻發送RTS到節點B，可以觀察到C在[t1，t2]時間段內的任何時刻發送RTS都將導致在節點B發生沖突。令Rh為Tv與時隙時間的比，有：

在單跳無線網絡中，所有節點處于相互的偵聽范圍內，A和C的沖突只可能發生在相同的時隙中；而在多跳無線網絡中，由于C為隱藏終端，在Rh的任何一個時隙內，A和C的RTS都可能在B發生沖突。

圖2 Tv示意圖Fig.2 Tv schematic

在節點的偵聽范圍內，第 i類業務的個數為 Ni（i=0，1，2，3）。在隱藏區域內，各類業務的個數設為 Nh_k（k=0，1，2，3），則對第i類業務發送RTS產生干擾的優先級業務的總數可以表示為[4]：

由此得出，隱藏終端影響下第i類業務發送數據發生沖突的概率可以表示為：

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

2 分析排隊模型

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

令a（k）表示在一個數據幀的服務時間內有k個幀到達的概率，由于i類業務服從到達率為λi的泊松過程，則有：

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

第i類業務的吞吐率Si可以表示為

3 結束語

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

通過對無線局域網絡模型的建立與分析，為進一步定量地分析網絡性能、設計更優的傳輸控制協議奠定了基礎。

[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無線局域網中的接入延遲分析模型[J].傳感技術學報，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協議分析與建模[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]張國鵬，鄒向毅，趙力強，等.基于效用最大化的IEEE 802.11 DCF性能分析及改進[J].電子與信息學報，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]吳亞軍，胡愛群，宋宇波.無線局域網協議分析系統的設計與實現[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的性能模型設計[J].吉林大學學報：信息科學版，2008，26（5）：476-479.WANG Lin-zhu，FAN Ya-qin，HU Ke-gang.Wireless LAN perfor-mance modeling[J]. Jilin University:Information Science Editor，2008，26 （5）:476-479.

[7]王靜，戎蒙恬，劉超.無線局域網分布式自適應信道分配問題的研究[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.