無(wú)線(xiàn)局域網(wǎng)中基于節(jié)點(diǎn)數(shù)量的時(shí)隙長(zhǎng)度設(shè)置

劉衛(wèi)，趙曉俠

昆明理工大學(xué)計(jì)算中心，昆明650024

1 引言

IEEE 802.11無(wú)線(xiàn)局域網(wǎng)技術(shù)可便捷和高速地接入網(wǎng)絡(luò)，因而得到了廣泛應(yīng)用。IEEE 802.11的MAC層采用CSMA/CA機(jī)制，其基本思想是載波偵聽(tīng)和沖突避免：當(dāng)檢測(cè)到網(wǎng)絡(luò)中發(fā)生碰撞后，節(jié)點(diǎn)采用二進(jìn)制指數(shù)退避的方式減少碰撞。國(guó)內(nèi)外眾多研究人員采用數(shù)學(xué)模型分析了IEEE 802.11協(xié)議[1-11]。Bianchi分析了CSMA/CA機(jī)制，為二進(jìn)制指數(shù)退避機(jī)制構(gòu)建了二維M arkov模型，得到了飽和吞吐量的解析式[1]。很多研究者在Bianchi的研究基礎(chǔ)上，開(kāi)展了進(jìn)一步的研究工作，以提高網(wǎng)絡(luò)的吞吐量性能[2-11]。如Kim[8]提出了沖突感知的速率自適應(yīng)機(jī)制，分析了非飽和網(wǎng)絡(luò)狀態(tài)下的協(xié)議性能；文獻(xiàn)[12]基于Kalman與ARMA濾波方法，提出了針對(duì)IEEE 802.11二進(jìn)制指數(shù)退避的估計(jì)方案，取得了良好的估計(jì)精確度。

然而，眾多研究成果表明[2-12]，當(dāng)節(jié)點(diǎn)數(shù)量增加時(shí)，IEEE 802.11的MAC協(xié)議性能惡化，如碰撞增加、吞吐量下降等問(wèn)題。因此，為提高IEEE 802.11網(wǎng)絡(luò)的性能，需要充分考慮網(wǎng)絡(luò)中的負(fù)載情況，如節(jié)點(diǎn)數(shù)量，來(lái)自適應(yīng)調(diào)整MAC協(xié)議的相關(guān)參數(shù)。

本文提出了一種基于節(jié)點(diǎn)數(shù)量估計(jì)的時(shí)隙長(zhǎng)度動(dòng)態(tài)設(shè)置算法DTSLENN（Dynamic Time Slot Length based on Estimating Number of Nodes）。根據(jù)中心節(jié)點(diǎn)AP測(cè)得的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量，計(jì)算優(yōu)化的時(shí)隙長(zhǎng)度，并以廣播的形式告訴網(wǎng)絡(luò)中所有節(jié)點(diǎn)，將時(shí)隙長(zhǎng)度設(shè)置成該優(yōu)化值，從而降低碰撞概率，提高網(wǎng)絡(luò)總吞吐量。NS2仿真驗(yàn)證了所提算法的有效性。本文的創(chuàng)新點(diǎn)在于，通過(guò)深入的理論分析，嚴(yán)格證明了取得吞吐量最大化的時(shí)隙長(zhǎng)度優(yōu)化設(shè)置解析式，從而網(wǎng)絡(luò)節(jié)點(diǎn)能根據(jù)節(jié)點(diǎn)數(shù)量來(lái)優(yōu)化設(shè)置時(shí)隙長(zhǎng)度，進(jìn)而有效地提高系統(tǒng)吞吐量，改善網(wǎng)絡(luò)性能。

2 基于節(jié)點(diǎn)數(shù)量估計(jì)的時(shí)隙長(zhǎng)度動(dòng)態(tài)設(shè)置法

2.1 時(shí)隙長(zhǎng)度的優(yōu)化設(shè)置

定理考慮有N個(gè)節(jié)點(diǎn)參與信道競(jìng)爭(zhēng)IEEE 802.11網(wǎng)絡(luò)中，對(duì)于任意節(jié)點(diǎn)，當(dāng)時(shí)隙長(zhǎng)度設(shè)置為：

網(wǎng)絡(luò)可以取得最大吞吐量。其中，CWmin為最小的競(jìng)爭(zhēng)窗口，Ttr為空間傳輸時(shí)間，TSFIS、TACK、TDIFS是IEEE 802.11的基本參數(shù)。

證明假設(shè)數(shù)據(jù)包傳輸發(fā)生的碰撞概率為p，節(jié)點(diǎn)可傳送數(shù)據(jù)包多次，直到收到ACK。因此，數(shù)據(jù)包被成功發(fā)送的概率為1-p。由于每次發(fā)生碰撞后，競(jìng)爭(zhēng)窗口會(huì)增大，直至增大到最大競(jìng)爭(zhēng)窗口，因此平均退避窗口為：

考慮到節(jié)點(diǎn)X發(fā)送數(shù)據(jù)時(shí)會(huì)與其他節(jié)點(diǎn)Y發(fā)生碰撞。當(dāng)節(jié)點(diǎn)Y正在傳輸數(shù)據(jù)，節(jié)點(diǎn)X的退避時(shí)間保持不變。假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量足夠多，因此節(jié)點(diǎn)X與Y傳輸不是同步，X可以在任何一時(shí)間內(nèi)傳輸，故與Y發(fā)生碰撞的概率為，而X與其他任何節(jié)點(diǎn)發(fā)生碰撞的概率為1-(1-，將式（2）代入得：

假定rsuccess為傳送成功的概率，rxmit為發(fā)生數(shù)據(jù)包的概率（包括碰撞），則平均傳輸一個(gè)數(shù)據(jù)包所需要的次數(shù)為，故由下式成立：

由于三個(gè)及其以上的多重碰撞發(fā)生的概率極小，可以忽略不計(jì)。因此，碰撞率rsuccess可以由下式給出：

設(shè)Tcycle為傳輸一次的時(shí)間，包括成功傳送和碰撞，因此：

由式（4）～（6）可以推導(dǎo)出：

在飽和狀態(tài)下，當(dāng)N個(gè)節(jié)點(diǎn)均勻的選擇競(jìng)爭(zhēng)窗口，平均競(jìng)爭(zhēng)窗口為CWmin/(N+1)。所以Tcycle可表示為：

無(wú)線(xiàn)信道利用率可以表示為：

因此，在N比較大的情況下，飽和狀態(tài)下的吞吐量為：

其中S為數(shù)據(jù)包長(zhǎng)度。

通常Ttr+TSFIS+TACK+TDIFS?4Tslot，當(dāng)Tslot滿(mǎn)足關(guān)系式（1）時(shí)，在飽和狀態(tài)下，系統(tǒng)可以得到最大吞吐量。證明如下：

令b=(Ttr+TSFIS+TACK+TDIFS)Tslot，對(duì)式（12）求導(dǎo)得：

最大值。

由式（14）有

由式（15）和（16）可以推導(dǎo)出：

p值較小，由式（13）近似可得l=2/p，所以有下式成立：

因此，當(dāng)式（1）滿(mǎn)足時(shí)，系統(tǒng)可以取得最大吞吐量。

2.2 工作流程

DTSLENN的工作流程如下：

（1）中心節(jié)點(diǎn)AP估計(jì)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量。方式采用文獻(xiàn)[12]所述方法，具體如下：當(dāng)某節(jié)點(diǎn)在發(fā)送數(shù)據(jù)包時(shí)，數(shù)據(jù)包發(fā)生碰撞的概率為p，根據(jù)條件碰撞概率p與飽和狀態(tài)下節(jié)點(diǎn)數(shù)據(jù)流之間的關(guān)系：n=f(p)，利用ARMA濾波算法，通過(guò)測(cè)量條件碰撞概率，可以測(cè)算出網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量。

（2）當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量發(fā)送改變時(shí)，AP利用廣播的形式告訴網(wǎng)絡(luò)中所有的節(jié)點(diǎn)；當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量沒(méi)有發(fā)生改變時(shí)，則不發(fā)送廣播。

（3）所有的節(jié)點(diǎn)收到AP發(fā)送的廣播后，根據(jù)公式（1）來(lái)調(diào)整相應(yīng)的時(shí)隙長(zhǎng)度。

3 仿真驗(yàn)證

通過(guò)NS2仿真工具，驗(yàn)證DTSLENN在多種網(wǎng)絡(luò)場(chǎng)景情況下的性能，并與IEEE 802.11和文獻(xiàn)[7]所提方法CARA進(jìn)行了性能比較。仿真結(jié)果表明了DTSLENN的有效性（如圖1）。

圖1 DTSLENN與IEEE 802.11、CARA的吞吐量比較（數(shù)據(jù)包長(zhǎng)度為500 Byte）

在網(wǎng)絡(luò)場(chǎng)景中，傳播模型采用TwoRayGround理想模型，仿真持續(xù)時(shí)間50 s。MAC基本速率為1 M b/s，MAC頭部大小為144 bit，PHY頭部大小為192 bit，SIFS為10μs，DIFS為50μs，CWmin為32，CWmax為1 024。各個(gè)節(jié)點(diǎn)僅僅與中心節(jié)點(diǎn)（AP）通信，各個(gè)節(jié)點(diǎn)彼此之間并不互相通信，但是在有效范圍內(nèi)可以互相偵聽(tīng)到對(duì)方的存在。

首先考察網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量變化對(duì)網(wǎng)絡(luò)性能的影響。網(wǎng)絡(luò)場(chǎng)景如下：首先保持網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量為4，然后逐漸增加節(jié)點(diǎn)的數(shù)量，以觀察節(jié)點(diǎn)數(shù)量增加對(duì)系統(tǒng)性能的影響。IEEE 802.11采用20μs的固定時(shí)隙，而DTSLENN中，時(shí)隙長(zhǎng)度的設(shè)置滿(mǎn)足公式（1）。圖2、圖3和圖4的仿真結(jié)果分別對(duì)應(yīng)了數(shù)據(jù)包長(zhǎng)度為500 Byte、1 000 Byte、1 500 Byte三種情況下的吞吐量性能。

圖2 DTSLENN與IEEE 802.11、CARA的吞吐量比較（數(shù)據(jù)包長(zhǎng)度為1 000 Byte）

圖3 DTSLENN與IEEE 802.11、CARA的吞吐量比較（數(shù)據(jù)包長(zhǎng)度為1 500 Byte）

從圖1可知，在IEEE 802.11中，當(dāng)節(jié)點(diǎn)數(shù)量為5時(shí)，系統(tǒng)總吞吐量最大達(dá)到3.63M b/s；當(dāng)節(jié)點(diǎn)數(shù)量為15時(shí)，系統(tǒng)吞吐量最小，為3.37 M b/s，降幅約為7.2%。而DTSLENN中，在節(jié)點(diǎn)數(shù)量為5時(shí)，系統(tǒng)總最大吞吐量為3.71 M b/s；當(dāng)節(jié)點(diǎn)數(shù)量為15時(shí)，取得系統(tǒng)最小吞吐量3.47M b/s。由此可以看出，DTSLENN的系統(tǒng)總吞吐量始終大于IEEE 802.11和CARA。類(lèi)似的結(jié)果也在圖2和圖3中體現(xiàn)。即當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目增加時(shí)，IEEE 802.11與DTSLENN的總吞吐量均減少，這是由于節(jié)點(diǎn)數(shù)量增加，導(dǎo)致碰撞增多，信道有效利用率變小，吞吐量下降；使用DTSLENN后，總吞吐量雖然有所減少，但是比IEEE 802.11和CARA吞吐量大，這是由于DTSLENN可以減少碰撞率，相應(yīng)的提高了信道有效利用率，從而提高了總吞吐量，改善了網(wǎng)絡(luò)性能。

此外，本文將考察DTSLENN在如圖4所示動(dòng)態(tài)場(chǎng)景下的性能。

圖4 動(dòng)態(tài)場(chǎng)景

圖4中，節(jié)點(diǎn)A、B、C、D、E、F、G和H距離AP均為250m，節(jié)點(diǎn)A、B、C、D、G和H其運(yùn)動(dòng)速度分別為2m/s、1m/s、1m/s、1m/s、2m/s和2m/s，運(yùn)動(dòng)方向如圖5箭頭所示。節(jié)點(diǎn)E與F則始終保持靜止?fàn)顟B(tài)。

圖5 動(dòng)態(tài)場(chǎng)景下，DTSLENN與IEEE 802.11、CARA的吞吐量比較（數(shù)據(jù)包長(zhǎng)度為500 Byte）

從圖5、圖6可知，在不同的數(shù)據(jù)包長(zhǎng)情況下，DTSLENN的系統(tǒng)總吞吐量在絕大多數(shù)時(shí)刻總是大于IEEE 802.11和CARA，只是在極少時(shí)刻下小于IEEE 802.11和CARA。仿真結(jié)果進(jìn)一步證明了，在運(yùn)動(dòng)情況下，DTSLENN的性能較IEEE 802.11和CARA有很大改善，DTSLENN可以提高網(wǎng)絡(luò)系統(tǒng)的吞吐量。

圖6 動(dòng)態(tài)場(chǎng)景下，DTSLENN與IEEE 802.11、CARA的吞吐量比較（數(shù)據(jù)包長(zhǎng)度為1 000 Byte）

4 結(jié)論

在IEEE 802.11無(wú)線(xiàn)局域網(wǎng)中，當(dāng)節(jié)點(diǎn)數(shù)量增加時(shí)，數(shù)據(jù)包之間的碰撞會(huì)相應(yīng)增加，有時(shí)會(huì)導(dǎo)致信道利用率下降，從而降低了系統(tǒng)總吞吐量。本文提出了基于節(jié)點(diǎn)數(shù)量估計(jì)的時(shí)隙長(zhǎng)度動(dòng)態(tài)設(shè)置法（DTSLENN）。根據(jù)測(cè)得的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量，中心節(jié)點(diǎn)AP計(jì)算優(yōu)化的時(shí)隙長(zhǎng)度，并以廣播的形式告訴網(wǎng)絡(luò)中所有節(jié)點(diǎn)將時(shí)隙長(zhǎng)度設(shè)置成該優(yōu)化值。通過(guò)理論分析和仿真實(shí)驗(yàn)，證實(shí)了DTSLENN能夠有效提高系統(tǒng)吞吐量，改善網(wǎng)絡(luò)性能。

[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]徐偉強(qiáng)，胡四平，汪亞明，等.IEEE 802.11中多速率多節(jié)點(diǎn)公平的數(shù)據(jù)分組長(zhǎng)度調(diào)整策略[J].通信學(xué)報(bào)，2011，32（2）：120-129.

[3]Acharya P A K，Sharma A，Belding E M，et al.Congestion-aware rate adaptation in wireless networks：a measurement-driven approach[C]//Proceedings of the IEEE SECON Conference，2008.

[4]習(xí)勇，魏急波，莊釗文.差錯(cuò)信道下IEEE 802.11 DCF最優(yōu)幀長(zhǎng)分析及信道自適應(yīng)策略[J].通信學(xué)報(bào)，2006，27（5）：84-89.

[5]Kim J，Kim S，Choi S，et al.CARA：Collision-aware Rate Adapataion for 802.11 Wireless Networks[C]//Proceedings of the IEEE INFOCOM，2006.

[6]李賀武，吳建平，馬輝，等.基于競(jìng)爭(zhēng)終端個(gè)數(shù)區(qū)間的IEEE 802.1性能優(yōu)化[J].軟件學(xué)報(bào)，2009，15（12）：1850-1859.

[7]Choi J，Na J，Lim Y S，et al.Collision-aware design of rate adaptation for multi-rate 802.11 WLANs[J].IEEE Journal on Selected A reas in Communications，2008，26（8）：1366-1375.

[8]黃家瑋，王建新.多速率802.11 WLAN中時(shí)間公平的主動(dòng)隊(duì)列管理算法[J].通信學(xué)報(bào)，2009，30（2）：34-41.

[9]Huang K D，Malone D，Duffy K R.The 802.11g 11Mb/s rate is more robust than 6 Mb/s[J].IEEE Transactions on W ireless Communications，2011，10（4）：1015-1020.

[10]Wong S，Yang H，Lu S，et al.Robust Rate Adaptation for 802.11 Wireless Networks[C]//Proceedings of the ACM MobiCom Conference，2008.

[11]Giustiniano D，Malone D，Leith D J，et al.Measuring transmission opportunities in 802.11 links[J].IEEE/ACM Transactions on Networking，2010，18（5）：1516-1583.

[12]Bianchi G，Tinnirello I.Kalman filter estimation of the number of competing terminals in an IEEE 802.11 network[C]//Proceedings of the IEEE INFOCOM，2007：844-852.