非飽和無線局域網(wǎng)環(huán)境中Idle Sense 機(jī)制研究

馬治杰，趙慶林，劉 瑩

MA Zhijie,ZHAO Qinglin,LIU Ying

澳門科技大學(xué) 資訊科技學(xué)院，澳門999078

Faculty of Information and Technology,Macau University of Science and Technology,Macau 999078,China

1 引言

IEEE 802.11 DCF（Distributed Coordination Function，分布式協(xié)調(diào)功能）[1]是無線局域網(wǎng)中最常用的媒體訪問控制機(jī)制，它采用CSMA/CA（Carrier Sense Multiple Access/Collision Avoidance，帶有沖突避免的載波偵聽多路訪問）原理和Exponential Back-off（指數(shù)后退）算法來減少分組發(fā)送沖突。然而，在飽和（每個(gè)節(jié)點(diǎn)時(shí)刻有分組發(fā)送）的無線局域網(wǎng)中，隨著節(jié)點(diǎn)數(shù)目的增多，DCF機(jī)制存在吞吐量迅速降低和延時(shí)迅速增大兩個(gè)問題。

目前，已有很多相關(guān)工作對(duì)DCF機(jī)制進(jìn)行了改進(jìn)（如參考文獻(xiàn)[2-9]）。Idle Sense（文獻(xiàn)[2]）是一種非常著名的MAC 層訪問機(jī)制，它在飽和環(huán)境中表現(xiàn)出了比IEEE 802.11 DCF更好的性能。在該機(jī)制中，每個(gè)節(jié)點(diǎn)將不執(zhí)行指數(shù)后退算法，而是根據(jù)相鄰兩次傳輸之間的平均連續(xù)空閑時(shí)隙數(shù)與最優(yōu)空閑時(shí)隙數(shù)的大小關(guān)系，用AIMD（Additive Increase Multiplicative Decrease，和式增加積式減少）算法[10]動(dòng)態(tài)地調(diào)整CW（Contention Window，競爭窗口），使CW最終收斂到一個(gè)最優(yōu)值，從而達(dá)到提高吞吐量和降低延時(shí)的目的。

然而，Idle Sense機(jī)制是在飽和環(huán)境中提出的。根據(jù)本文的實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，Idle Sense機(jī)制并不適用于更為實(shí)際的非飽和無線環(huán)境中。因此，本文提出了新的Idle Sense 機(jī)制，使其既適用于飽和環(huán)境，又適用于非飽和環(huán)境。最后，本文通過NS-2（Network Simulator Version 2）驗(yàn)證了新Idle Sense機(jī)制的有效性。

2 原Idle Sense 機(jī)制分析

2.1 Idle Sense 原理

定義ni為相鄰兩次傳輸之間的連續(xù)空閑時(shí)隙數(shù)，navg為相鄰兩次傳輸之間的平均連續(xù)空閑時(shí)隙數(shù)；nopt為最優(yōu)連續(xù)空閑時(shí)隙數(shù)。

Idle Sense 原理可總結(jié)為：每個(gè)節(jié)點(diǎn)先根據(jù)ni計(jì)算出navg，然后根據(jù)navg與nopt的大小關(guān)系，用AIMD 算法動(dòng)態(tài)的調(diào)整CW，使之最終能收斂到一個(gè)最優(yōu)值。AIMD 算法可簡單歸納如下：

即當(dāng)navg＞nopt時(shí)，CW將減小，反之CW將增大。其中α和ε為固定系數(shù)。

2.2 Idle Sense 在非飽和環(huán)境中存在的問題

Idle Sense機(jī)制在非飽和環(huán)境中存在兩個(gè)問題。

問題1在飽和環(huán)境中計(jì)算出來的nopt不能用于非飽和環(huán)境中。

在飽和環(huán)境中，β=1。但是在非飽和環(huán)境中，β≠1。所以，Idle Sense 機(jī)制在飽和環(huán)境中計(jì)算出來的nopt不能用在非飽和環(huán)境中。

問題2CW在非飽和環(huán)境中會(huì)遞減為零。

在非飽和環(huán)境中，由于節(jié)點(diǎn)獲得的空閑時(shí)隙數(shù)一直比較大，所以計(jì)算出的navg也比較大，且navg始終大于在飽和環(huán)境中計(jì)算出來的nopt。最終，在通過AIMD 算法調(diào)節(jié)CW時(shí)，CW會(huì)一直遞減，直到為零。圖1 畫出了一個(gè)節(jié)點(diǎn)的CW在飽和（圖1（a））與非飽和（圖1（b））環(huán)境中的變化。其中圖1（b）顯示了隨著傳輸次數(shù)的增多，CW最終遞減為零的現(xiàn)象。

上述問題惡化了Idle Sense機(jī)制在非飽和情況下的性能。圖3 和圖4 分別比較了Idle Sense 和DCF 的吞吐量和延時(shí)。由這兩幅圖可知，當(dāng)流量強(qiáng)度ρ較小（比如0.2 ＜ρ＜0.3）時(shí)，Idle Sense 的吞吐量低于DCF，而延時(shí)高于DCF。

圖1 一個(gè)節(jié)點(diǎn)在飽和（a）與非飽和（b）環(huán)境中的CW 對(duì)比

3 新Idle Sense機(jī)制分析

3.1 ni 的計(jì)算

在非飽和環(huán)境中，因?yàn)榫彌_區(qū)中很可能沒有要發(fā)送的分組，此時(shí)系統(tǒng)將一直處于空閑狀態(tài)，所以本文提出新的機(jī)制來統(tǒng)計(jì)該空閑時(shí)段。

新Idle Sense 機(jī)制將通過連續(xù)重啟Back-off 計(jì)時(shí)器的方法來記錄連續(xù)空閑時(shí)隙數(shù)ni。所以ni的計(jì)算方法可表示為：

3.2 新Idle Sense 機(jī)制

針對(duì)原Idle Sense 機(jī)制在非飽和環(huán)境中存在的兩個(gè)問題，新Idle Sense 機(jī)制做了如下兩方面的改進(jìn)（如圖2中的兩個(gè)虛線框所示）。

圖2 顯示了新Idle Sense 機(jī)制的執(zhí)行過程。在該機(jī)制中，每個(gè)節(jié)點(diǎn)在執(zhí)行完maxtrans次之后，將更新平均連續(xù)空閑時(shí)隙數(shù)navg，然后再根據(jù)AIMD 算法動(dòng)態(tài)地調(diào)整CW。其中兩處改進(jìn)如下。

改進(jìn)1nopt的取值（參見圖2 中的第一個(gè)虛線框）。

在新Idle Sense 機(jī)制中，每個(gè)節(jié)點(diǎn)通過比較其分組到達(dá)率λ與一個(gè)臨界值λ′的大小關(guān)系來區(qū)分飽和與非飽和環(huán)境。根據(jù)參考文獻(xiàn)[13-14]，λ′的表達(dá)式為：其中σ表示空閑時(shí)隙長度，Tc表示發(fā)送分組的沖突時(shí)間，Tc可根據(jù)文獻(xiàn)[13]中的表1 來計(jì)算。

如果λ≥λ′，則說明該節(jié)點(diǎn)處于飽和狀態(tài)。此時(shí)，新機(jī)制會(huì)選擇nopt_sat作為最優(yōu)空閑時(shí)隙數(shù)nopt。nopt_sat可通過公式和計(jì)算：

其中公式中的?是公式的根。

如果λ＜λ′，則說明該節(jié)點(diǎn)處在非飽和狀態(tài)。此時(shí)，為了避免由于存在過多的空閑時(shí)隙而導(dǎo)致CW連續(xù)遞減，新機(jī)制會(huì)選擇比nopt_sat更大的nopt_nonsat來作為非飽和情況下的最優(yōu)空閑時(shí)隙數(shù)。本文根據(jù)多次實(shí)驗(yàn)結(jié)果觀察可知，當(dāng)nopt_nonsat為30 時(shí)，能適應(yīng)于大多數(shù)情況。因此，本文采用nopt_nonsat=30 作為最優(yōu)空閑值。

改進(jìn)2避免CW遞減為0（參見圖2的第二個(gè)虛線框）。

為了避免出現(xiàn)圖1（b）的情況，新Idle Sense 機(jī)制在每次動(dòng)態(tài)調(diào)整CW之后，判斷當(dāng)前CW值是否為零。如若CW已經(jīng)為零，則將其重新賦值為當(dāng)前系統(tǒng)內(nèi)節(jié)點(diǎn)數(shù)目N，即CW=N。從而使得CW在下次可以根據(jù)該值進(jìn)行動(dòng)態(tài)調(diào)節(jié)，調(diào)節(jié)方法如圖2 中兩個(gè)虛線框中間所示。本文的模擬結(jié)果顯示，在非飽和環(huán)境中，當(dāng)CW=N時(shí)，新機(jī)制的性能最優(yōu)。

相對(duì)于原Idle Sense機(jī)制而言，新Idle Sense機(jī)制僅僅是在原機(jī)制算法上加了兩個(gè)判斷語句（詳見圖2 中的兩個(gè)虛線框），其時(shí)間復(fù)雜度是O(1)，即新增加的額外開銷可以忽略。

4 模擬結(jié)果

本章將通過NS-2 軟件（版本2.28）（http：//www.isi.edu/nsnam/ns/ns-build.html）對(duì)新Idle Sense 機(jī)制在吞吐量和延時(shí)兩方面進(jìn)行模擬驗(yàn)證。

表1 802.11b 標(biāo)準(zhǔn)參數(shù)

4.1 吞吐量

圖3表示執(zhí)行標(biāo)準(zhǔn)DCF機(jī)制、原Idle Sense和新Idle Sense 機(jī)制后所得的吞吐量模擬結(jié)果。橫坐標(biāo)表示分組流量強(qiáng)度ρ，縱坐標(biāo)表示吞吐量。其中ρ的表達(dá)式為：

其中B表示系統(tǒng)總帶寬。

圖3 三種機(jī)制的吞吐量比較

根據(jù)模擬結(jié)果可以看出，當(dāng)流量強(qiáng)度較?。é眩?.3，即非飽和情況）時(shí)，由于原Idle Sense 在非飽和環(huán)境中存在的問題，使得原Idle Sense 機(jī)制獲得的吞吐量最低，且低于標(biāo)準(zhǔn)DCF 獲得的吞吐量。而改進(jìn)后的新Idle Sense 機(jī)制明顯地提高了吞吐量，且其獲得的吞吐量和DCF 的吞吐量相同。

當(dāng)流量強(qiáng)度較大（ρ＞0.3，即飽和情況）時(shí)，由于新Idle Sense 機(jī)制執(zhí)行方法和原Idle Sense一樣，所以兩者獲得了相等的吞吐量，且均高于標(biāo)準(zhǔn)DCF 機(jī)制。

4.2 延時(shí)

圖4表示執(zhí)行標(biāo)準(zhǔn)DCF機(jī)制、原Idle Sense和新Idle Sense機(jī)制后所得到的延時(shí)模擬結(jié)果，橫坐標(biāo)表示分組流量強(qiáng)度，縱坐標(biāo)表示分組發(fā)送延時(shí)。

圖4 三種機(jī)制的延時(shí)比較

根據(jù)模擬結(jié)果可以看出，當(dāng)流量強(qiáng)度較?。é眩?.3，即非飽和情況）時(shí)，原Idle Sense 機(jī)制獲得的延時(shí)最高，且高于標(biāo)準(zhǔn)DCF 獲得的延時(shí)。而改進(jìn)后的新Idle Sense機(jī)制降低了延時(shí)，并幾乎與DCF 獲得的延時(shí)相同。

當(dāng)流量強(qiáng)度較大（ρ＞0.3，即飽和情況）時(shí)，兩種Idle Sense 機(jī)制獲得同樣的延時(shí)，且均小于標(biāo)準(zhǔn)DCF 機(jī)制的延時(shí)。

5 結(jié)束語

本文針對(duì)原Idle Sense機(jī)制在非飽和環(huán)境中存在的問題，提出了新的Idle Sense 機(jī)制。新機(jī)制不僅保留了原機(jī)制在飽和環(huán)境中高吞吐量和低延時(shí)的特點(diǎn)，也提高了原機(jī)制在非飽和環(huán)境中的吞吐量，同時(shí)也降低了延時(shí)。本文提出的新Idle Sense 機(jī)制增強(qiáng)了其在無線局域網(wǎng)中的實(shí)用性。

[1] IEEE 802.11 WG.Standard 802.11 Part 11：Wireless LAN medium access control and physical layer specifications[S].New York：IEEE，2003.

[2] Heusse M，Rousseau F，Guilier R，et al.Idle sense：an optimal access method for high throughput and fairness in rate diverse wireless LANs[C]//SIGCOMM’05，2005，35（4）：121-132.

[3] Cali F，Conti M，Gregori E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit[J].ACM/IEEE Trans on Networking，2000，8（6）：785-799.

[4] Ma H，Li H，Zhang P，et al.Dynamic optimization of IEEE 802.11 CSMA/CA based on the number of competing stations[C]//Proc of ICC’04，2004，1：191-195.

[5] Ni Q，Aad I，Barakat C，Turlette T.Modeling and analysis of slow CW decrease for IEEE 802.11 WLAN[C]//2003，2：1717-1721.

[6] Song N O，Kwak B J，Song J，et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoff algorithm[C]//Proc of VTC，2003，4：2775-2778.

[7] Barghavan V，Demers A，Shenker S，et al.MACAW：a media access protocol for wireless LAN’s[C]//Proc of ACM SIGCOMM，1994，24（4）：212-225.

[8] Ho T S，Chen K C.Performance analysis of IEEE 802.11 CSMA/CA medium access control protocol[C]//PIMRC，Seventh IEEE International Symposium，1996，2：407-411.

[9] Heusse M，Rousseau F，Berger-Sabbatel G，et al.Performance anomaly of 802.11b[C]//Proc of INFOCOM，2003，2：836-843.

[10] Chiu D，Jain R.Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[J].Journal of Computer Networks and ISDN，1989，17（1）：1-14.

[11] Bianchi G.Performance analysis of IEEE 802.11 distributed coordination function[J].Selected Areas in Communications.2000，18（3）：535-547.

[12] Ramaiyan V，Kumar A，Altman E.Fixed point analysis of single cell IEEE 802.11e WLANs：Uniqueness，multistability and throughput differentiation[J].ACM/IEEE Trans on Networking，2008，16（5）：1080-1093.

[13] Zhao Qinglin，Tsang D H K，Sakurai T.A novel CAC scheme for homogeneous 802.11 networks[J].Trans on Wireless Communications，2010：1168-1174.

[14] Zhao Qinglin，Tsang D H K，Sakurai T.A simple criticalload-based CAC scheme for IEEE 802.11 DCF networks[J].ACM/IEEE Trans on Networking，2011 19（5）：1485-1498.