步超倫，肖揚(yáng)，葉通，吳鵬，張小建，吳軍民

（1.上海交通大學(xué)區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，上海200240；2.國網(wǎng)智能電網(wǎng)研究院，江蘇南京210003）

研究與開發(fā)

隨機(jī)訪問網(wǎng)絡(luò)后退避機(jī)制的性能分析

步超倫1，肖揚(yáng)1，葉通1，吳鵬2，張小建2，吳軍民2

（1.上海交通大學(xué)區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，上海200240；2.國網(wǎng)智能電網(wǎng)研究院，江蘇南京210003）

無線局域網(wǎng)隨機(jī)訪問協(xié)議的性能分析是近年來的研究熱點(diǎn)，而現(xiàn)有的模型還未能對(duì)其后退避機(jī)制進(jìn)行有效刻畫?；谝环N兩階段的馬爾可夫模型，分析非飽和業(yè)務(wù)狀態(tài)下隨機(jī)訪問網(wǎng)絡(luò)的性能。首先，利用嵌入式馬爾可夫鏈描述每個(gè)站點(diǎn)隊(duì)頭分組的服務(wù)過程，引入虛擬服務(wù)時(shí)間的概念，即將傳輸成功之后的后退避也看成隊(duì)頭分組服務(wù)時(shí)間的一部分，從而得到隊(duì)頭分組的虛擬服務(wù)時(shí)間分布。然后，將每個(gè)用戶隊(duì)列看成一個(gè)Geo/G/1系統(tǒng)，求得非飽和業(yè)務(wù)狀態(tài)下系統(tǒng)吞吐量、時(shí)延等參數(shù)的閉合解表達(dá)式以及系統(tǒng)的穩(wěn)定區(qū)間。仿真結(jié)果驗(yàn)證了模型的準(zhǔn)確性。本文所提模型將對(duì)今后研究無線局域網(wǎng)的分布式協(xié)調(diào)功能（DCF）協(xié)議打下基礎(chǔ)。

隨機(jī)訪問網(wǎng)絡(luò)；后退避；性能分析；馬爾可夫鏈

1 引言

近年來，人們對(duì)移動(dòng)通信以及帶寬的要求越來越高，無線局域網(wǎng)絡(luò)的應(yīng)用越來越廣泛。無線信道的隨機(jī)訪問協(xié)議是無線局域網(wǎng)的核心協(xié)議，其中較常見的隨機(jī)訪問協(xié)議有Aloha協(xié)議及其變種載波偵聽多路訪問（CSMA）協(xié)議和分布式協(xié)調(diào)功能（DCF）協(xié)議等。

隨機(jī)訪問網(wǎng)絡(luò)協(xié)議的一個(gè)突出問題是信道的捕獲效應(yīng)，即信道被同一站點(diǎn)持續(xù)占用，而其他站點(diǎn)則一直處在退避重傳的過程中無法成功發(fā)送數(shù)據(jù)，從而帶來節(jié)點(diǎn)間的不公平性。為了解決這一問題，業(yè)界引入了“后退避”機(jī)制，即在數(shù)據(jù)分組發(fā)送成功之后，站點(diǎn)進(jìn)行一段隨機(jī)退避，以便釋放信道，從而避免信道被某個(gè)站點(diǎn)持續(xù)占用。

過去的十幾年里，許多學(xué)者對(duì)基于后退避機(jī)制的隨機(jī)訪問協(xié)議進(jìn)行了分析，然而大多數(shù)分析都是基于飽和業(yè)務(wù)假設(shè)。所謂飽和業(yè)務(wù)情形，就是指各站點(diǎn)在發(fā)送成功數(shù)據(jù)分組后，緩存隊(duì)列中一定有數(shù)據(jù)在等待發(fā)送。在該情形下，當(dāng)數(shù)據(jù)分組到達(dá)隊(duì)列時(shí)，站點(diǎn)要么在忙于發(fā)送數(shù)據(jù)分組，要么在進(jìn)行“后退避”。Bianchi［1］提出了一種二維的馬爾可夫鏈模型來刻畫數(shù)據(jù)分組過程，并對(duì)系統(tǒng)的吞吐量進(jìn)行了分析。參考文獻(xiàn)［2-5］針對(duì)飽和業(yè)務(wù)情形下的隨機(jī)訪問協(xié)議系統(tǒng)進(jìn)行了分析，然而他們都基于參考文獻(xiàn)［1］中飽和業(yè)務(wù)情形的假設(shè)。在實(shí)際系統(tǒng)中，網(wǎng)絡(luò)一般不會(huì)工作在飽和業(yè)務(wù)情形下，因?yàn)榇藭r(shí)的網(wǎng)絡(luò)均處于非穩(wěn)定狀態(tài)，數(shù)據(jù)時(shí)延性能得不到保障。研究非飽和業(yè)務(wù)情形下系統(tǒng)的性能具有十分重要的意義。

在非飽和業(yè)務(wù)情形下，數(shù)據(jù)分組到達(dá)隊(duì)列時(shí)看到的情形要比飽和業(yè)務(wù)復(fù)雜得多。當(dāng)有新的數(shù)據(jù)分組到達(dá)站點(diǎn)時(shí)，該站點(diǎn)可能正在忙于發(fā)送隊(duì)頭分組，也可能正處于后退避狀態(tài)，還可能處于空閑狀態(tài)。目前，已經(jīng)有一些文獻(xiàn)對(duì)非飽和業(yè)務(wù)情形下的隨機(jī)訪問網(wǎng)絡(luò)進(jìn)行了分析。參考文獻(xiàn)［6］是基于參考文獻(xiàn)［7］的兩階段模型，分析了非飽和業(yè)務(wù)狀態(tài)下的DCF系統(tǒng)性能，但未考慮后退避機(jī)制。參考文獻(xiàn)［8，9］在參考文獻(xiàn)［1］的馬爾可夫鏈的基礎(chǔ)上，增加了站點(diǎn)空閑的狀態(tài)，并分析了非飽和業(yè)務(wù)狀態(tài)下系統(tǒng)的特性，但仍然沒有考慮后退避機(jī)制。Malone［10］則針對(duì)非飽和業(yè)務(wù)的特性，在馬爾可夫鏈［1］的基礎(chǔ)上增加了后退避狀態(tài)，然而在分析系統(tǒng)的吞吐量和時(shí)延時(shí)，涉及站點(diǎn)的空閑概率，而該概率本身又取決于系統(tǒng)的狀態(tài)，這就產(chǎn)生了記憶性，沒法求出各參數(shù)的封閉解析表達(dá)式。

為此，本文提出虛擬服務(wù)時(shí)間的概念，并基于一種兩階段模型［7］分析非飽和業(yè)務(wù)情況下的后退避的隨機(jī)訪問網(wǎng)絡(luò)性能。假設(shè)當(dāng)共享媒介的站點(diǎn)數(shù)量較多時(shí)，站點(diǎn)間的行為相互獨(dú)立，即每個(gè)站點(diǎn)看成獨(dú)立的FIFO隊(duì)列。首先，利用馬爾可夫鏈描述每個(gè)站點(diǎn)隊(duì)頭分組的服務(wù)過程，引入虛擬服務(wù)時(shí)間的概念，即將傳輸成功之后的后退避過程也看成隊(duì)頭分組服務(wù)時(shí)間的一部分。于是，上述隊(duì)頭分組可能面對(duì)的復(fù)雜情形變得清晰，一個(gè)分組到達(dá)站點(diǎn)時(shí)，要么站點(diǎn)處于繁忙狀態(tài)，要么處于空閑狀態(tài)，這樣就消除了系統(tǒng)的記憶性，體現(xiàn)出模型的馬爾可夫特性。然后，將每個(gè)用戶隊(duì)列看成一個(gè)Geo/G/1系統(tǒng)，求得非飽和業(yè)務(wù)狀態(tài)下系統(tǒng)吞吐量、時(shí)延等參數(shù)的閉合解表達(dá)式，并確定系統(tǒng)的穩(wěn)定區(qū)間。

2 物理過程及模型建立

本文研究的隨機(jī)訪問網(wǎng)絡(luò)如圖1所示，多個(gè)站點(diǎn)通過隨機(jī)競(jìng)爭(zhēng)的方式共享同一個(gè)帶寬資源。該網(wǎng)絡(luò)是一個(gè)分時(shí)隙的系統(tǒng)，每個(gè)站點(diǎn)都服從速率為λ的伯努利到達(dá)過程，并且都帶有無限空間的緩存。

圖1 n個(gè)站點(diǎn)的時(shí)隙隨機(jī)退避網(wǎng)絡(luò)模擬隊(duì)列

圖2演示了基于后退避的時(shí)隙隨機(jī)訪問網(wǎng)絡(luò)中兩個(gè)站點(diǎn)競(jìng)爭(zhēng)發(fā)送分組的過程。當(dāng)一個(gè)數(shù)據(jù)分組成為隊(duì)頭分組，而且該站點(diǎn)不處于后退避狀態(tài)時(shí)，站點(diǎn)將在當(dāng)前時(shí)隙立即發(fā)送它。如果此時(shí)另一個(gè)站點(diǎn)在此時(shí)隙也有分組發(fā)送，就會(huì)發(fā)送沖突，如圖2中灰色方框所示。這時(shí)兩站點(diǎn)都要進(jìn)行一段隨機(jī)時(shí)間的退避，即以概率q重傳該數(shù)據(jù)分組，如圖2中實(shí)線箭頭所示；當(dāng)某個(gè)時(shí)隙只有一個(gè)站點(diǎn)發(fā)送數(shù)據(jù)分組時(shí)，數(shù)據(jù)分組可以傳送成功。但為了避免成功站點(diǎn)獨(dú)占信道，該站點(diǎn)將以概率r進(jìn)行一段后退避，如圖2中虛線箭頭所示。

圖2 基于后退避的時(shí)隙隨機(jī)訪問網(wǎng)絡(luò)中兩個(gè)站點(diǎn)競(jìng)爭(zhēng)發(fā)送分組的過程

在后退避的隨機(jī)訪問網(wǎng)絡(luò)中，站點(diǎn)的數(shù)據(jù)分組看到的本站所處的狀態(tài)會(huì)比較復(fù)雜。當(dāng)此分組到達(dá)站點(diǎn)時(shí)隊(duì)列非空，它成為隊(duì)頭分組后仍需要經(jīng)歷一個(gè)后退避的過程才能被發(fā)送；如果此分組到達(dá)時(shí)隊(duì)列為空，但站點(diǎn)后退避過程并未結(jié)束，它也需要等到后退避過程結(jié)束后才能被發(fā)送；如果此分組到達(dá)時(shí)隊(duì)列為空，且上一次后退避已經(jīng)結(jié)束，則可以在當(dāng)前時(shí)隙立即被發(fā)送。因此，新到達(dá)的分組是否能被立即發(fā)送，不僅取決于站點(diǎn)隊(duì)列是否為空，而且取決于站點(diǎn)是否處于后退避狀態(tài)，這使非飽和業(yè)務(wù)下的性能分析變得困難。參考文獻(xiàn)［1］中假設(shè)飽和業(yè)務(wù)，實(shí)際上是只考慮第一種情形，減小了問題復(fù)雜度，因此不符合一般情形。

為了全面刻畫后退避狀態(tài)，本文引入虛擬服務(wù)時(shí)間的概念，即將后退避過程看成一個(gè)隊(duì)頭分組服務(wù)過程的一部分。換言之，從一個(gè)分組成為隊(duì)頭分組到由它引發(fā)的后退避結(jié)束的這段時(shí)間看成虛擬服務(wù)時(shí)間。在這段時(shí)間內(nèi)，站點(diǎn)都屬于“忙”的狀態(tài)。只有后退避結(jié)束之后，隊(duì)列的下一個(gè)分組才能成為一個(gè)隊(duì)頭分組。如圖3所示，用Ps表示第s個(gè)數(shù)據(jù)分組，用Xs表示數(shù)據(jù)分組s的真實(shí)服務(wù)時(shí)間，Bs表示數(shù)據(jù)分組Ps的后退避的時(shí)間，隊(duì)頭分組服務(wù)過程的虛擬服務(wù)時(shí)間則由單個(gè)分組的真實(shí)服務(wù)時(shí)間Xs和后退避時(shí)間Bs兩部分構(gòu)成，即Vs=Xs+Bs。于是，上述隊(duì)頭分組可能面對(duì)的復(fù)雜情形變得清晰。一個(gè)分組到達(dá)站點(diǎn)時(shí)，站點(diǎn)要么處于繁忙狀態(tài)，要么處于空閑狀態(tài)，而且引入虛擬服務(wù)時(shí)間的概念也不影響真實(shí)的平均服務(wù)時(shí)間的計(jì)算。因?yàn)?，只要把平均虛擬服務(wù)時(shí)間減去平均后退避時(shí)間就可以得到真實(shí)的平均服務(wù)時(shí)間。

圖3 虛擬服務(wù)時(shí)間

本文基于參考文獻(xiàn)［7］的兩級(jí)排隊(duì)模型對(duì)系統(tǒng)進(jìn)行建模。把每個(gè)站點(diǎn)看成一個(gè)Geo/G/1的排隊(duì)系統(tǒng)，其中信道對(duì)隊(duì)頭分組的服務(wù)過程可以通過圖4的馬爾可夫鏈來刻畫。隊(duì)頭分組將經(jīng)歷可直接發(fā)送狀態(tài)（狀態(tài)0）、發(fā)送失敗后的重傳狀態(tài)（狀態(tài)1）以及發(fā)送成功后的后退避狀態(tài)（狀態(tài)-1）。新的隊(duì)頭分組都是先進(jìn)入初始狀態(tài)0，如果傳送發(fā)生沖突則進(jìn)入狀態(tài)1，并以概率q再次發(fā)送；而如果隊(duì)頭分組以概率p傳送成功，則以概率r回到狀態(tài)0，以概率1-r進(jìn)入狀態(tài)-1。同樣，如果處于狀態(tài)1的隊(duì)頭分組再次沖突，則依然處于狀態(tài)1，如果傳送成功則以概率r選擇是進(jìn)入狀態(tài)-1還是狀態(tài)0。因此，參數(shù)r描述了站點(diǎn)在成功發(fā)送分組之后的時(shí)隙中，進(jìn)行后退避過程的概率。換言之，參數(shù)r也決定了一個(gè)站點(diǎn)處于后退避狀態(tài)的時(shí)長。

圖4 帶有后退避機(jī)制的時(shí)隙隨機(jī)退避網(wǎng)絡(luò)隊(duì)頭分組服務(wù)過程馬爾可夫鏈

用f0、f1和f-1分別代表圖4中各狀態(tài)的穩(wěn)態(tài)概率。利用離散時(shí)間馬爾可夫鏈的性質(zhì)，可以得到：

因?yàn)楹笸吮苓^程也可看成隊(duì)頭分組服務(wù)過程的一部分，把引入后退避機(jī)制后數(shù)據(jù)分組的到達(dá)速率和虛擬服務(wù)速率的比值稱為虛擬負(fù)載率ρυ。每一個(gè)隊(duì)頭分組的起始狀態(tài)是0，而結(jié)束狀態(tài)也是0，因此一個(gè)隊(duì)頭分組的服務(wù)速率是f0，假設(shè)輸入速率為λ，每個(gè)站點(diǎn)的虛擬負(fù)載率為：

3 性能分析

3.1 吞吐量

每個(gè)站點(diǎn)可能存在5種狀態(tài)：狀態(tài)1，空閑且緩存為空；狀態(tài)2，忙于傳送一個(gè)狀態(tài)為0的新分組；狀態(tài)3，忙于重傳一個(gè)狀態(tài)為1的發(fā)生過沖突的分組；狀態(tài)4，由于傳送發(fā)生沖突而進(jìn)行退避；狀態(tài)5，進(jìn)行后退避。

由式（1）～式（4）可知，Pr｛狀態(tài)1}=1-ρυ，Pr｛狀態(tài)2}=ρυf0，Pr｛狀態(tài)3}=ρυf1q，Pr｛狀態(tài)4}=ρυf1（1-q），Pr｛狀態(tài)5}=ρυf-1。

當(dāng)站點(diǎn)處于狀態(tài)1、4和5時(shí)，并不會(huì)發(fā)送數(shù)據(jù)分組。而一個(gè)站點(diǎn)想要成功發(fā)送分組的條件就是其余n-1個(gè)站點(diǎn)不發(fā)送分組，那么成功發(fā)送分組的概率為：

在穩(wěn)定狀態(tài)下，系統(tǒng)的輸出λout應(yīng)該和輸入λin相等，根據(jù)式（5）可知，每個(gè)時(shí)隙的平均嘗試發(fā)送分組率為：

所以穩(wěn)定狀態(tài)下的吞吐量為：

這與參考文獻(xiàn)［11］中的結(jié)果是一致的，這說明本文模型在吞吐量上的分析是正確的。

3.2 時(shí)延

由圖4可知，隊(duì)頭分組的服務(wù)時(shí)間是在所有狀態(tài)經(jīng)歷時(shí)間的總和，用Di表示從狀態(tài)i開始直到服務(wù)完成所經(jīng)過的時(shí)間，用Yi表示在狀態(tài)i所花費(fèi)的時(shí)間，有：

Yi是服從幾何分布的隨機(jī)變量，Yi的概率母函數(shù)為：

根據(jù)式（8）和式（9），Di的概率母函數(shù)可以表示為：

根據(jù)式（11）和式（12），有：

根據(jù)概率母函數(shù)的性質(zhì)可知，虛擬服務(wù)時(shí)間V的均值和方差可以表示為：

根據(jù)參考文獻(xiàn)［7］中的Pollaczek-Kintchine公式以及式（13）～式（16），可以得到平均虛擬服務(wù)時(shí)間為：

平均等待時(shí)間為：

計(jì)算平均總時(shí)延時(shí)，應(yīng)將平均虛擬服務(wù)時(shí)間和平均等待時(shí)間相加后，再減去平均后退避時(shí)間，即：

3.3 穩(wěn)定區(qū)間

根據(jù)參考文獻(xiàn)［11］，時(shí)隙隨機(jī)退避網(wǎng)絡(luò)的最大吞吐量約為0.368，由式（7）可以得到系統(tǒng)吞吐量與嘗試發(fā)送率之間的關(guān)系，如圖5所示。

圖5 λout與G的關(guān)系曲線

假定系統(tǒng)總輸入λin=nλ＜0.368，那么系統(tǒng)穩(wěn)定的條件就是λout=λin=nλ。對(duì)應(yīng)圖5中可以發(fā)現(xiàn)，只有在兩個(gè)紅色實(shí)心交點(diǎn)處滿足該條件，把這兩個(gè)交點(diǎn)分別記作GS和GL，根據(jù)式（6）可以得到對(duì)應(yīng)的兩個(gè)成功發(fā)送分組概率分別為pS和pL。

q是唯一一個(gè)可以由系統(tǒng)改變的參數(shù)，系統(tǒng)只有當(dāng)ρυ≤1時(shí)才會(huì)處于穩(wěn)定狀態(tài)，所以令ρυ=1，求出臨界狀態(tài)下的兩個(gè)q值。由式（4），有：

代入pL和pS有：

系統(tǒng)穩(wěn)定時(shí)需要滿足兩個(gè)條件，即ρυ≤1且E［T］＜∞，下面將分5種情形分別討論關(guān)于q的穩(wěn)定區(qū)間。

（1）情形1：q∈［0，qS）

將q代入式（4）和式（19）可知，無論p取何值，都會(huì)得到ρυ＞1且E［T］=∞，在這種情況下系統(tǒng)一定不穩(wěn)定。

（2）情形2：q=qS

這種情形下，p=pS可以得到ρυ=1，系統(tǒng)處于臨界穩(wěn)定，然而此時(shí)E［T］=∞，系統(tǒng)并不穩(wěn)定。

（3）情形3：q∈（qS，qL）

這種情形下需要對(duì)p的取值分情況進(jìn)行討論，當(dāng)p=pS時(shí)，ρυ＜1，且ρυ隨著q的增加而降低，E［T］有上界，且E［T］隨著q的增加而逐漸降低，此時(shí)系統(tǒng)穩(wěn)定；而當(dāng)p取pL時(shí)，ρυ≥1，系統(tǒng)不穩(wěn)定，E［T］為負(fù)值，顯然不可能。這說明，在這個(gè)區(qū)間內(nèi)系統(tǒng)要想穩(wěn)定，其發(fā)送分組成功概率p一定只能等于pS。

（4）情形4：q=qL

當(dāng)q=qL時(shí)，p=pL，ρυ突然增加到1，系統(tǒng)處于臨界狀態(tài)，而E［T］突然又增加到無窮，系統(tǒng)不穩(wěn)定。

（5）情形5：q∈（qL，1］

此時(shí)無論p取pL還是pS，ρυ＜1均成立，且E［T］均有界。這似乎暗示著系統(tǒng)可以同時(shí)處于pL和pS狀態(tài)，然而模型各態(tài)遍歷的前提說明模型在此區(qū)域已經(jīng)失效，系統(tǒng)在穩(wěn)定狀態(tài)下p不可能有兩個(gè)解，即模型無法刻畫系統(tǒng)的行為。

綜上，系統(tǒng)的穩(wěn)定區(qū)間為q∈（qS，qL）。并且當(dāng)q∈［qS，qL）時(shí)，站點(diǎn)發(fā)送分組成功概率為p=pS；當(dāng)q=qL時(shí)，站點(diǎn)發(fā)送分組成功概率為p=pL。因此，在qS≤q≤qL區(qū)間內(nèi)，p是q的階躍函數(shù)。

4 仿真與分析

在C++的環(huán)境下對(duì)每個(gè)站點(diǎn)隊(duì)頭分組的不同狀態(tài)進(jìn)行仿真，默認(rèn)取站點(diǎn)個(gè)數(shù)n為50，并且令r=q，分別在3種不同的系統(tǒng)輸入流量λin=0.1、0.3和0.35的情況下進(jìn)行對(duì)比仿真，只設(shè)置一個(gè)可調(diào)參數(shù)：重傳因子q，接下來通過設(shè)置不同的q值，得到吞吐量、時(shí)延、負(fù)載率等參數(shù)的仿真結(jié)果。

圖6是吞吐量λout在不同的系統(tǒng)輸入流量下關(guān)于重傳因子q的仿真結(jié)果比較。可以看出，穩(wěn)定區(qū)間的仿真結(jié)果邊界值與用式（21）和式（22）計(jì)算的理論值（qSqL）相符，當(dāng)重傳因子q超出穩(wěn)定區(qū)間時(shí)，系統(tǒng)的吞吐量快速下降，而當(dāng)重傳因子q在穩(wěn)定區(qū)間（qS，qL）內(nèi)時(shí)，系統(tǒng)吞吐量λout始終保持恒定，即系統(tǒng)輸入流量λin。

圖6 吞吐量的仿真結(jié)果比較

圖7則對(duì)系統(tǒng)的平均總時(shí)延進(jìn)行仿真?？梢钥闯?，仿真結(jié)果可以和式（19）算出的理論結(jié)果相匹配。當(dāng)重傳因子q在穩(wěn)定區(qū)間內(nèi)逐漸增加時(shí)，平均時(shí)延從無窮大開始逐漸下降，這是因?yàn)殡S著q的增加，各站點(diǎn)在發(fā)生沖突后的重傳概率變大，那么出現(xiàn)某個(gè)站點(diǎn)持續(xù)占用信道的概率減小，也就是增加了系統(tǒng)的公平性，站點(diǎn)的緩存中排隊(duì)等待發(fā)送的數(shù)據(jù)分組變少，站點(diǎn)中隊(duì)頭分組發(fā)送沖突后退避的時(shí)間也減少，從而降低了平均時(shí)延。而當(dāng)重傳因子q超出穩(wěn)定區(qū)間后，時(shí)延突然增加到無窮大，系統(tǒng)狀態(tài)又變?yōu)椴环€(wěn)定。

圖7 平均時(shí)延的仿真結(jié)果比較

圖8則是虛擬負(fù)載率ρυ關(guān)于q的關(guān)系曲線。在穩(wěn)定區(qū)間內(nèi)，仿真結(jié)果與式（4）的理論值相符。虛擬負(fù)載率ρυ等于數(shù)據(jù)分組的到達(dá)速率和虛擬服務(wù)速率的比值，隨著q的增加，站點(diǎn)中隊(duì)頭分組發(fā)送沖突后退避的時(shí)間減少，也就是服務(wù)時(shí)間減少，即服務(wù)速率增加，那么在到達(dá)速率λ不變的情況下，虛擬負(fù)載率ρυ是關(guān)于q的一條單調(diào)遞減曲線。而在穩(wěn)定區(qū)間的兩個(gè)端點(diǎn)處，負(fù)載率為1，系統(tǒng)處于臨界穩(wěn)定。

圖8 系統(tǒng)負(fù)載率的仿真結(jié)果比較

當(dāng)q∈［qS，qL）時(shí)，站點(diǎn)成功發(fā)送分組的概率p始終等于pS；而當(dāng)重傳因子q=qL時(shí)，站點(diǎn)發(fā)送分組成功概率為p=pL。成功發(fā)送分組概率的仿真結(jié)果如圖9所示。在［qS，qL）內(nèi)，p始終保持恒定且等于pS，而當(dāng)q=qL時(shí)，p發(fā)生跳變，變?yōu)閜L，這又進(jìn)一步驗(yàn)證了理論分析中所預(yù)測(cè)的階躍性是正確的。

圖9 成功發(fā)送分組概率的仿真結(jié)果比較

5 結(jié)束語

本文提出了一種帶有后退避機(jī)制的馬爾可夫鏈模型，以分析時(shí)隙隨機(jī)退避網(wǎng)絡(luò)協(xié)議的性能。通過引入的虛擬服務(wù)時(shí)間和虛擬負(fù)載率等參數(shù)，分析了系統(tǒng)各項(xiàng)參數(shù)的性能，并求解出非飽和業(yè)務(wù)狀態(tài)下系統(tǒng)吞吐量、時(shí)延等參數(shù)的閉合解表達(dá)式以及系統(tǒng)的穩(wěn)定區(qū)間。仿真結(jié)果與理論分析相符，證實(shí)了本文模型的正確性。接下來將分析后退避機(jī)制在更加復(fù)雜的隨機(jī)退避網(wǎng)絡(luò)協(xié)議（如分布式協(xié)調(diào)功能（DCF）協(xié)議）中的應(yīng)用。

［1］BIANCHI G.Performance analysis of the IEEE 802.11 distributed coordination function［J］.IEEE Journal on Selected Areas in Communications，2000，18（3）：535-547.

［2］KUMAR A，ALTMAN E，MIORANDI D，et al.New insights from a fixed point analysis of single cell IEEE 802.11 WLANs［C］/The 24th Annual Joint Conference of the IEEE Computer and Communications Societies，March 13-17，2005，Miami，F(xiàn)L，USA.New Jersey：IEEE Xplore，c2005：1550-1561.

［3］CALì F，CONTI M，GREGORI E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit［J］.IEEE/ACM Transactions on Networking，2000，8（6）：785-799.

［4］WU H，PENG Y，LONG K，et al.A simple model of IEEE 802.11 wireless LAN［C］//The International Conferences on Info-tech and Info-net，October 12-14，2001，Beijing，China.New Jersey：IEEE Xplore，c2001：514-519.

［5］SAKURAI T，VU H L.MAC access delay of IEEE 802.11 DCF［J］.IEEE Transactions on Wireless Communications，2007，6（5）：1702-1710.

［6］DAI L，SUN X.A unified analysis of IEEE 802.11 DCF networks：stability，throughput，and delay［J］.IEEE Transactions on Mobile Computing，2013，12（8）：1558-1572.

［7］LEE T T，DAI L.Buffered aloha with K-exponential backoff--part I：stability and throughput analysis［J］.arXiv preprint arXiv：0907.4251，2009.

［8］WANG B，SONG F，ZHANG S D，et al.Throughput modeling analysis of IEEE 802.11 DCF mechanism in multi-hop non-saturated wireless ad-hoc networks［C］/The International Conference on Communications，Circuits and Systems，May 25-27，2008，Xiamen，China.New Jersey：IEEE Xplore，c2008：383-387.

［9］GUPTA N，RAI C S.Non-saturation throughput analysis of IEEE 802.11 DCF considering short retry limit for single hop ad hoc networks［C］/The Second International Conference on Future Generation Communication Technology（FGCT），November 12-14，2013，London，United Kingdom.New Jersey：IEEE Xplore，c2013：10-15.

［10］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.

［11］ABRAMSON N.Packet switching with satellites［C］/The National Computer Conference and Exposition，June 4-8，1973，New York，USA.New York：AFIPS Press，c1973：695-702.

步超倫（1991-），男，上海交通大學(xué)碩士生，主要研究方向?yàn)闊o線通信網(wǎng)絡(luò)協(xié)議性能分析。

Performance analysis of random access network w ith post-backoff

BU Chaolun1，XIAO Yang1，YE Tong1，WU Peng2，ZHANG Xiaojian2，WU Junmin2
1.State Key Laboratory of Advanced Optical Communication Systems and Networks，Shanghai Jiaotong University，Shanghai 200240，China 2.State Grid Smart Grid Research Institute，Nanjing 210003，China

Performance analysis of random access network protocol in wireless local area network is a research hotspot in recent years，and the existing models have yet to describe post-backoff mechanism effectively.Therefore，the performance of the random access network under the unsaturated condition based on a two stage Markov model was analyzed.First of all，embedded Markov chain was used to describe the service process of the head-of-line（HOL）packet in each node，then the concept of virtual service time was introduced，namely regarding the p ost-backoff process after the successful transmission as a part of the HOL packet service time，then the virtual service time distribution of the HOL packet was attained.Next，the queuing process of each node was considered as a Geo/G/1 system，then the close-form result of system throughput，delay and the range of the stable region under the unsaturated condition was achieved.The simulation results have verified the accuracy of our model.The model will shed light on the future research on distributed coordination function（DCF）protocol in wireless local area network.

random access network，post-backoff，performance analysis，Markov chain

The Key Technology and Power Grid Application Research of All-Optic Switching

TN929.5

A

10.11959/j.issn.1000-0801.2016055

2015-08-20；

2016-01-07

全光交換關(guān)鍵技術(shù)及電網(wǎng)應(yīng)用研究項(xiàng)目

吳軍民（1971-），男，國網(wǎng)智能電網(wǎng)研究院高級(jí)工程師，主要研究方向?yàn)殡娏ο到y(tǒng)通信。

肖揚(yáng)（1992-），男，上海交通大學(xué)本科在讀，主要研究方向?yàn)闊o線通信網(wǎng)絡(luò)協(xié)議性能分析。

葉通（1976-），男，博士，上海交通大學(xué)副教授，主要研究方向?yàn)閷拵Ы粨Q網(wǎng)絡(luò)結(jié)構(gòu)、網(wǎng)絡(luò)算法設(shè)計(jì)和性能分析、光網(wǎng)絡(luò)系統(tǒng)。

吳鵬（1984-），男，國網(wǎng)智能電網(wǎng)研究院中級(jí)工程師，主要研究方向?yàn)殡娏ο到y(tǒng)通信。

張小建（1969-），男，國網(wǎng)智能電網(wǎng)研究院高級(jí)工程師，主要研究方向?yàn)殡娏ο到y(tǒng)通信。