虛擬空閑時間對非飽和狀態DCF性能的影響

彭春華,徐湘淄

(中南大學信息科學與工程學院,長沙410075)

虛擬空閑時間對非飽和狀態DCF性能的影響

彭春華,徐湘淄

(中南大學信息科學與工程學院,長沙410075)

研究非飽和狀態下分布式協調功能(DCF)協議的性能,針對非飽和狀態下的無線局域網,引入虛擬空閑時間定量描述系統的忙碌程度,對二維馬爾科夫鏈模型進行改進。在理想信道條件下,使用基本接入方式,利用改進模型研究虛擬空閑時間及站點數對DCF性能(系統吞吐量和分組傳輸平均時延)的影響。理論推導及仿真結果表明,在不同的虛擬空閑時間下,隨著站點數的增加,系統非飽和吞吐量為先快速上升后緩慢下降的過程,分組傳輸時延則是平穩上升的過程,與選取的對比模型相比,吞吐量在站點數目較小時有明顯改善,時延性能有較大提高。

無線局域網;馬爾科夫鏈;分布式協調功能;虛擬空閑時間;吞吐量;時延

1 概述

在應用日益廣泛的IEEE802.11無線局域網中, MAC子層主要采用分布式協調功能(Distributed Coordination Function,DCF)機制[1]。DCF機制是一種基于具有沖突檢測的載波偵聽多路訪問(CSMA/ CA)的隨機訪問機制,節點通過競爭獲得信道的使用權,并在發生碰撞后采用二進制指數退避算法避免再次碰撞。

從IEEE802.11標準制定以來,對DCF性能的分析、建模、改進一直是研究熱點。針對其工作在飽和狀態的特點,許多研究者都給出了較為精確的數學模型,其中最經典的成果是文獻[2]提出的一種二維Markov鏈模型。該模型求出以沖突概率τ和網絡節點數目n作為自變量的吞吐量表達式。文獻[3]針對DCF協議提出了一種對AP和STA的退避算法進行改進,提高了AP搶占信道的優先級,從而提高無線局域網(Wireless Local Area Network, WLAN)吞吐量的方案。文獻[4-6]引入了“虛擬時隙”概念來研究DCF協議性能的影響。文獻[7]針對實時業務中的不同QoS需要,提出一種基于數據包優先級的DCF(PMDCF)模型。文獻[8]對比分析分析了3種主要DCF性能的優劣。文獻[9]提出了一種將 Markov鏈與排隊論結合的模型。文獻[10]提出了一種不飽和傳輸條件下的錯誤重傳,而不是競爭窗口加倍從相同的競爭窗口退避計數器選擇一個計數器值的Markov模型。文獻[11]建立排隊論模型來評估非飽和DCF性能。文獻[12]建立的模型,將吞吐量、時延、丟包率三者作為評估指標來評估DCF性能。文獻[13-14]中對DCF的信道做了詳細的介紹。文獻[15]是較早研究非飽和狀態DCF的提出的模型,但此模型沒有考慮退避凍結這種狀況。

本文考慮到實際應用中非飽和業務量的情況,由文獻[4-6]虛擬時隙這一概念,引出“虛擬空閑時間”這一概念描述非飽和狀態下WLAN系統的忙碌程度,并進一步探究“虛擬空閑時間”對DCF協議性能的影響。改進文獻[2]提出的二維 Markov模型[2],并推導系統的歸一化吞吐量S以及分組傳輸時延D的表達式。

2 二維Markov鏈模型

在本文提出的二維Markov鏈模型中,為了簡便分析,給出以下4條基本假設[3]:

(1)網絡中各節點的結構相同,互相之間優先級、傳輸與偵聽范圍均是相同的,節點總數量不變、始終未為n;

(2)信道是理想的,也即是信道誤碼率為0;

(3)不考慮實際情況中出現的“隱蔽終端”和“暴露終端”等問題;

(4)節點按照泊松過程接收來自上層的數據分組達到率為λ。

另外在考慮非飽和網絡時引入“虛擬空閑時間”(Virtual Idle Time,VIT)[4-6],定義為:站點從上一次成功發送數據分組到下一次嘗試發送數據分組之間需要等待的時間。在討論一個非飽和狀態下的WLAN時,由于站點不是每時每刻都有數據分組需要發送,因此站點在兩次發送數據分組之間需要等待一段“虛擬空閑時間”。該“時間”也是對非飽和網絡狀態的站點發送數據繁忙程度的一個描述,并可以進一步影響到傳輸分組沖突的概率和信道的利用程度。當一個數據分組由于成功發送或者到達重發次數限制而被移出緩沖區,并且發送隊列為空時,節點進入“虛擬空閑時間”。

IEEE802.11 DCF有2種工作模式:基本工作接入方式和RTS/CTS工作接入方式。2種方式的退避過程基本相同,其最大的區別在于后者發送數據之前用RTS幀和CTS幀預約信道。為了簡便起見,本文采用基本工作模式。

本文提出的Markov改進模型定義一個主機在t時刻以m為最大退避級數的隨機過程。設x(t)是某個特定站點退避時間的隨機過程,t代表一個時隙(slot)的起始時刻,退避計數器在每個時隙的起始時刻減1。Markov改進模型是一個二維隨機過程{s(t),b(t)},其中,s(t)代表t時刻該節點所處的退避階數i;b(t)代表t時刻節退避計數器的值k[7]。為了計算過程的清晰,定義:

可以推導出:

又記:

其中,W0表示初始競爭窗口大小;CWmin表示最小競爭窗口;CWmax表示最大競爭窗口;m表示最大退避階數同時也是最大后退級數,即二進制退避算法中從最小競爭窗口CWmin到最大競爭窗口CWmax的增長指數;Wi表示當前競爭窗口大小,i∈[0,m],稱為退避級數[8]。

在本文提出的Markov改進模型中,有一個很重要的假設:每個不同的站點在每一次嘗試發送數據分組時,發生碰撞的概率為p且相互獨立。該假設在站點數目龐大的時候是合理的,這是因為每個站點發送數據的過程是互不相關,相互獨立的。此外,由4條基本假設可以推導出,節點發送失敗,僅由發生碰撞引起,即節點發送數據分組失敗的概率為p。

基于以上假設,可以構建改進的二維隨機過程{s(t),b(t)},這是一個離散事件的 Markov鏈,如圖1所示。對圖中符號的說明如下:(1)p0定義為節點進入“虛擬空閑時間”的概率,則當一個分組移出發送緩沖區時隊列不為空,節點進入下一輪二進制指數退避工程的概率為 1-p0; (2)q定義為節點停留在“虛擬空閑時間”狀態的概率;(3)ptr為發生沖突碰撞的概率或者說是至少有一個站點傳輸數據分組的概率,則1-ptr為數據包被成功發送的概率。

圖1 改進的Markov鏈模型狀態轉移圖

單步轉移概率如式(4)所示:

式(4)中的轉移概率包括以下9個方面:

(1)一次成功發送后,又有新的數據等待發送,這時需要啟動新的退避過程,退避時間被設置為[0,W0-1]內的隨機整數,開始新的退避過程[9];

(2)一次成功發送后,沒有新的數據分組等待發送,節點進入“虛擬空閑時間”;

(3)第i次退避過程結束,且發送失敗,開始新的退避過程,退避時間被設置為[0,W0-1]內的隨機整數;

(4)退避過程中偵聽到載波沖突,進入退避凍結狀態;

(5)當偵聽到信道為空閑時,在空閑時隙開始,退避時間計數器減1;

(6)當達到最大重傳次數限制時,丟掉當前的數據分組,CW被重置為CWmin大小,并為新的數據分組啟動退避過程;

(7)當達到最大重傳次數限制時,沒有數據分組要傳送,節點進入“虛擬空閑時間”;

(8)節點處于虛擬空閑時間時,收到上層數據分組消息,啟動新的退避過程;

(9)節點停留在“虛擬空閑時間”。

進一步推導可得:

在退避級數i不為0,即節點接收的數據分組不可能在來自“虛擬空閑時間”的情況下,結合圖1和式(4)可得:

在退避級數i為0,即節點接收的數據分組可能在來自“虛擬空閑時隙”的情況下,結合圖 1和式(4)可得:

歸納整理可得:

最后根據Markov模型的歸一化條件[10]:

定義τ為站點在某一時隙傳輸的概率,在該站點的退避計數器值為0時開始傳輸,開始傳輸的時刻與退避級數無關,則可得:

推導至此,可以看出分組傳輸率τ受p,p0,ptr以及q的影響。

當節點處于飽和狀態且不考慮退避凍結狀態和重傳次數限制,即q=0,p0=0,ptr=0以及m→∞時,可得此時τ的表達式:

與文獻[2]的模型相同,同時也與文獻[9]的模型相同。

由此可見,本文提出的模型比Bianchi模型考慮的因素更全面,同時又比文獻[7]提出的模型更為簡潔。

3 模型分析

DCF的系統性能指標主要有吞吐量、分組傳輸時延以及包重發率等,其中尤以吞吐量最為重要。本文對模型的性能進行分析時,采用歸一化吞吐量以及分組傳輸時延作為分析對象。

在第2節中,利用改進的Markov模型已經推導出了分組傳輸概率τ的表達式(10)。接下來對該模型進行分析,以便得出系統歸一化的吞吐量S的表達式。

首先定義ps是至少有一站點傳輸分組的條件下,分組傳輸成功的概率。

發生沖突碰撞的概率ptr可表示為:

進而可以導出ps表達式為:

根據p是分組發生碰撞的概率這一設定,可以得出:

由于已經設定分組達到服從泊松分布,因此長度為slot的時間內,節點處于“虛擬空閑時間”,即沒有數據分組到達的概率,表示為:

3.1 歸一化吞吐量分析

定義系統的歸一化吞吐量S如下[11]:

設E[P]是分組的平均大小,因為在單位時間內成功傳輸的概率為ptrps,所以在單位時間內成功傳輸的信息的平均有效載荷為ptrpsE[P]。

定義在單位時間內,數據分組成功發送的概率為pc:

由此可以導出系統的歸一化吞吐量:

其中,σ是空閑時隙的長度;Ts是媒體成功傳輸分組而被檢測為忙的平均時間;Tc是媒體由于發生碰撞而被檢測為忙的時間。在此給出Ts和Tc的表達式[2]。

在單位時間內,(1-ptr)σ表示空閑狀態平均占用的時間,ptrpsTs表示分組傳輸成功平均占用的時間,ptr(1-ps)Tc表示發生碰撞平均占用的時間。

其中,H=PHYhead+MAChead;PHYhead為PHY頭部長度;MAChead為MAC頭部長度;SIFS為短幀間間隔, ACK為ACK幀長;DIFS為分布協調功能幀間間隔; δ為傳播時延。

3.2 分組傳輸時延分析

定義D是無接入點的無線局域網的分組傳輸時延,并將D分為以下4個部分[12]:

(1)Ts:節點在成功競爭到信道使用權后,發送分組數據所用的時間;

(2)Ds:在節點競爭信道過程中,由于其他節點成功發送數據而使信道處于忙狀態的平均時間;

(3)Dc:由于發送沖突而使信道處于忙狀態的平均時間;

(4)Tslot:在節點競爭信道過程中,占用時隙的總時間,它包括總的退避時間以及其它節點成功發送或沖突的等待時間。

這樣,可以得到公式:

參考式(22)得:

下面將對剩下的3個變量進行推導計算。

假定站點均處于同一無線信道的覆蓋范圍內,那么任意2個站點之間都可以互相偵聽和傳輸數據,進一步,每個站點對信道的需求概率是相同的。所以,在一段較長的時間內,每個站點成功發送完成一組數據幀的概率相同,且在一個站點連續2次成功發送的

間隔之間,其他站點也必定各自都有一次成功的發送[13-14]。定義Ns是此時間段內其它站點的成功發送次數,則有NS=n-1,其中,n表示站點總數。因此,在一個節點競爭信道過程中,由于其他節點成功發送數據而使信道處于忙狀態的平均時間為:

再根據式(15)、式(16)可得:

其中,定義Nc為連續發生沖突的次數,Nc均值為:

在整個網絡中,連續2次成功發送的時間間隔內沖突次數為E[Nc],同樣的,在一個D之中有n次站點成功發送了數據,這樣推導出:

定義變量Nslot為一次退避中包含的連續的空閑時隙數,那么Nslot為一個隨機整數的概率:

Nslot均值為:

總的空閑時隙的時間為:

將式(24)、式(25)、式(28)、式(31)代入式(23),得:

4 仿真實驗及結果

利用 Matlab建立非飽和狀態下不同站點數WLAN吞吐量和時延的仿真平臺,比較IEEE802.11中的不同虛擬空閑時間下站點數對系統吞吐量的影響。仿真參數如表1所示。

表1 仿真參數

為了更直觀地顯現出本文所作出的貢獻,將文獻[9]的模型和文獻[15]的模型與本文的模型對比。其中,文獻[9]的模型以下簡稱ZPing模型,文獻[15]的模型以下簡稱Malone模型。ZPing模型全面考慮了IEEE802.11 DCF模型中包括業務量、緩沖區大小、節點總數量與系統性能之間的關系,并結合M/M/1/K模型分析了非飽和負載,還加入了信道衰落因素;但是此模型并沒有探討站點數對系統性能的關系,而且模型過于復雜,也沒有對分組傳輸時延性能做出細致分析。Malone模型考慮了實際情況下發送站不會隨時處于飽和狀態的條件,但是此模型沒有考慮節點退避過程中退避凍結情況。

從圖2的總體趨勢來看:隨著站點數的增多,系統吞吐量經歷了一個先快速增加,再緩慢下降的過程。這是因為在站點數目很少時,發生碰撞的概率很小,此時影響吞吐量的主要因素是信道的利用率。而此時信道經常處于空閑狀態,信道利用率很低,所以導致吞吐量小。當站點數增加時,信道的利用率迅速增長,使吞吐量增長,達到一個很高的水平。而當站點數足夠多時,信道基本處于忙碌狀態,此時影響系統吞吐量的因素由信道的忙閑變為了沖突的發生和解決。隨著站點數的增加,沖突的機會也增加,所以吞吐量會有下降。

圖2 系統吞吐量仿真結果

從“虛擬空閑時間”的長短對系統吞吐量的影響來看:當站點數目很少(如站點數為2,4)時,“虛擬空閑時間”越短,系統吞吐量越低。這是因為站點數目少,碰撞發生的機會較少,所以此時影響吞吐量的主要因素是信道的利用程度。而“虛擬空閑時間”越小時,信道越忙碌,利用率也就越高,系統吞吐能越好。

隨著站點數增加,當站點數達到6時,1 000 slot的吞吐量已經超越500 slot時的吞吐量;500 slot的吞吐量已經超越100 slot的吞吐量。

當站點數目達到14及其以上時,虛擬空閑時間越長,吞吐量反而越大。這是因為在站點數目比較多時,所有信道都已經基本處于忙碌狀態,沖突也都將會變得很多。此時,“虛擬空閑時間”越長,數據包發生沖突的機會反而越小,處理開銷越小,吞吐量自然也就越高。

從上述分析可以知道,信道的忙碌程度以及沖突都影響著系統的吞吐量。“虛擬空閑時間”越長,信道利用程度越低、沖突發生的機會越小。站點數目小的時候,無論“虛擬空閑時間”有多長,沖突的發生的概率都比較小,此時沖突不是影響吞吐量的主要因素,在這種情況下,“虛擬空閑時間”通過影響信道利用率來影響系統的吞吐量。站點數較多的時候,由于信道都處于忙碌狀態,因此“虛擬空閑時間”的長短對信道利用率影響很小,此時它通過影響沖突的發生概率來影響吞吐量。

再將本文建立的模型的結果與Malone模型[15]的結果對比來看,當站點數目比較小的時候,除了虛擬空閑時間為2 000 slot情況下的吞吐量比對比模型的吞吐量小外,其余3種情況均優于對比模型的。當站點數目比較大時(12以上),吞吐量性能比對比模型的差。由此可見,本文的模型在一定程度上改善了吞吐量性能,但是同時犧牲了站點數目比較大時候的吞吐量性能。

由圖3可以看出:當站點數目較少時,“虛擬空閑時間”為100 slot,500 slot,1 000 slot及2 000 slot 4種情況下的時延都很小;當站點數目增加時,由于發送沖突的概率增加而使信道處于忙狀態的平均時間DC的增加,同時沖突處理的開銷也增加,因此時延增大。

圖3 分組傳輸時延仿真結果

再考慮“虛擬空閑時間”的長短對時延的影響:

“虛擬空閑時間”為2 000 slot時,時延始終比其他3種情況小。這是因為虛擬空閑時間很長,信道相對于其他情況較為空閑,發生的碰撞也始終最少,所以花費在沖突的探測和處理上的時間開銷小,即時延小。

“虛擬空閑時間”為100 slot,500 slot和1 000 slot 3種情況下,在站點數較少時,由于信道都處于較空閑的狀態,數據分組傳輸沖突的概率很小,因此三者的平均時延都非常小且很接近。當站點數比較多時,在此情況下,由于“虛擬空閑時間”越短,信道越忙碌,數據分組碰撞的幾率越大,因此時延越大。100 slot和500 slot情況下的時間幾乎可以視為是一致的,且高于虛擬空閑時間為1 000 slot的時延。與選ZPing模型相比較,在整個過程中,時延性能有較大的提高。

5 結束語

本文改進了Markov鏈模型,引入“虛擬空閑時間”來定量描述信道的忙碌狀態,同時綜合考慮了實際過程中非飽和狀態下節點的退避、凍結以及不同站點數等多種實際情況。通過對WLAN網絡的建模、仿真,得出不同長短的“虛擬空閑時間”下,吞吐量和時延隨著站點數的變化而變化的數據,利用數據分析了站點數的多少以及“虛擬空閑時間”的大小對DCF性能的影響。仿真結果表明,隨著站點數的上升,系統吞吐量為先上升在下降的總趨勢;與此同時, 100 slot,500 slot,1 000 slot,2 000 slot空閑時間下的吞吐量在變化過程中有交替,即吞吐量由最初的S(100 slot)＞S(500 slot) ＞S(1 000 slot) ＞S(2 000 slot)隨站點數變化逐漸變為S(2 000 slot)＞S(1 000 slot)＞S(500 slot)＞S(100 slot),直至最終幾乎一致。同時與對比模型相比,性能在一定條件下有所改善。在分組傳輸時延方面,隨著站點數上升,時延增大,虛擬空閑時間為100 slot、500 slot、1 000 slot情況下的分組傳輸時延始終較接近,且明顯大于2 000 slot情況下的分組傳輸時延。與對比模型相比,時延性能改善非常明顯。

[1] IEEE.IEEE Standard 802.11-1991WirelessLAN Medium Access Control(MAC)and Physical Layer (PHY)Specifications[S].1991.

[2] Bianchi G.Performance Analysis of the IEEE802.11 Distributed Coordination Function[J].IEEE Journal on Selected Areas in Communications,2000,18(3): 535-547.

[3] 彭春華,蔣新華.高速移動環境下提高WLAN有效吞吐量方法的研究[J].鐵道學報,2012,34(1):54-59.

[4] Zheng Haitao, Zhang Xiaomin, Cao Gaoming. Performance Analysis of IEEE802.11 DCF in Nonsaturated Conditions[C]//Proceedings of 2011 IEEE International Conference on Business Management and Electronic Information.[S.1.]:IEEE Press,2011: 495-498.

[5] 楊衛東,馬建峰,李亞輝.基于分組到達率的 802.11 DCF性能分析[J].軟件學報,2008,19(10): 2762-2769.

[6] Yu Cheng,Ling Xinhua,Zhuang Weihua.A ProtocolindependentApproach forAnalyzing the Optimal Operation PointofCSMA/CA Protocols[C]// Proceedings of INFOCOM’09.[S.1.]:IEEE Press, 2009:2070-2078.

[7] 王 巖,王開宇,金順福.基于數據包優先級的 DCF及其性能分析[J].計算機工程,2009,35(12):97-99.

[8] Gupta N,Rai C S.Comparison of Analytical Models for Evaluating the Performance of IEEE802.11 Distributed Coordination Function Under Saturated Conditions[C]// Proceedings of ACCT’13.[S.1.]:IEEE Press,2013: 221-225.

[9] 鐘 萍,施海彬,莊玉祥,等.IEEE802.11 DCF協議性能分析模型[J].應用科學報,2013,31(1):41-47.

[10] Prakash G,Thangaraj P.Throughput Analysis of IEEE802. 11b WLAN Under a Non-Saturated Condition[C]// Proceedings ofInternationalConferenceon Emerging Trends in Technology.[S.1.]:ACM Press,2010:298-303.

[11] Zheng Qin,Xiao Jinsheng,Xie Honggang.A Novel ModelforNon-saturated Performance Analysis of IEEE802.11 DCF[C]//Proceedingsofthe2nd InternationalConference on ConsumerElectronics, Communications and Networks.[S.1.]:IEEE Press, 2012:1552-1556.

[12] Kosek-Szott K.Throughput,Delay,andFrameLoss Probability Analysis of IEEE 802.11 DCF with M/M/ 1/K Queues[C]//Proceedingsofthe 24th IEEE International Symposium on Personal Indoor and Mobile Radio Communications.[S.1.]:IEEE Press,2013: 2234-2238.

[13] 汪廣洪.IEEE 802.11無線局域網 MAC層性能及服務質量研究[D].天津:天津大學,2004.

[14] 彭春華.信道估計及 DCF算法在旅客列車無線Internet接入中的應用研究[D].長沙:中南大學,2010.

[15] Malone D,Duffy K,Leith D.Modeling the 802.11 Distributed Coordination Function in Nonsaturated Heterogeneous Conditions[J].IEEE/ACM Transactions on Networking,2007,15(1):159-172.

編輯 索書志

Effects of Virtual Idle Time on Non-saturated DCF Performance

PENG Chunhua,XU Xiangzi
(School of Information Science and Engineering,Central South University,Changsha 410075,China)

To evaluate the performance of the Distributed Coordination Function(DCF)in the case of non-saturation state,the concept of Virtual Idle Time(VIT)is introduced.It is used to measure how busy the non-saturation Wireless Local Area Network(WLAN)system is.An improved two-dimensional Markov chain model is proposed.With ideal channel and basic access mechanism,the improved Markov chain model is used to investigate the effects of VIT and the number of stations on the system’s throughput and average package delay.Theoretical analysis and simulation results show that in different VIT,as number of stations increases,the non-saturation throughput decreases slowly after a rapid rise,while the average package delay experiences a steady rise in the process.Compared with the models selected,when the number of station is small,the performance of throughput becomes better,and the performance of package delay is greatly improved.

Wireless Local Area Network(WLAN);Markov chain;Distributed Coordination Function(DCF);Virtual Idle Time(VIT);throughput;time delay

1000-3428(2015)01-0096-07

A

TP393.17

10.3969/j.issn.1000-3428.2015.01.018

彭春華(1971-),男,講師,主研方向:無線通信;徐湘淄,本科生。

2014-01-16

2014-03-24 E-mail:1499734120@qq.com

中文引用格式:彭春華,徐湘淄.虛擬空閑時間對非飽和狀態DCF性能的影響[J].計算機工程,2015,41(1):96-102.

英文引用格式:Peng Chunhua,Xu Xiangzi.Effects of Virtual Idle Time on Non-saturated DCF Performance[J]. Computer Engineering,2015,41(1):96-102.