非飽和無線局域網環境中Idle Sense 機制研究

馬治杰，趙慶林，劉 瑩

MA Zhijie,ZHAO Qinglin,LIU Ying

澳門科技大學 資訊科技學院，澳門999078

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

1 引言

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

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

然而，Idle Sense機制是在飽和環境中提出的。根據本文的實驗結果發現，Idle Sense機制并不適用于更為實際的非飽和無線環境中。因此，本文提出了新的Idle Sense 機制，使其既適用于飽和環境，又適用于非飽和環境。最后，本文通過NS-2（Network Simulator Version 2）驗證了新Idle Sense機制的有效性。

2 原Idle Sense 機制分析

2.1 Idle Sense 原理

定義ni為相鄰兩次傳輸之間的連續空閑時隙數，navg為相鄰兩次傳輸之間的平均連續空閑時隙數；nopt為最優連續空閑時隙數。

Idle Sense 原理可總結為：每個節點先根據ni計算出navg，然后根據navg與nopt的大小關系，用AIMD 算法動態的調整CW，使之最終能收斂到一個最優值。AIMD 算法可簡單歸納如下：

即當navg＞nopt時，CW將減小，反之CW將增大。其中α和ε為固定系數。

2.2 Idle Sense 在非飽和環境中存在的問題

Idle Sense機制在非飽和環境中存在兩個問題。

問題1在飽和環境中計算出來的nopt不能用于非飽和環境中。

在飽和環境中，β=1。但是在非飽和環境中，β≠1。所以，Idle Sense 機制在飽和環境中計算出來的nopt不能用在非飽和環境中。

問題2CW在非飽和環境中會遞減為零。

在非飽和環境中，由于節點獲得的空閑時隙數一直比較大，所以計算出的navg也比較大，且navg始終大于在飽和環境中計算出來的nopt。最終，在通過AIMD 算法調節CW時，CW會一直遞減，直到為零。圖1 畫出了一個節點的CW在飽和（圖1（a））與非飽和（圖1（b））環境中的變化。其中圖1（b）顯示了隨著傳輸次數的增多，CW最終遞減為零的現象。

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

圖1 一個節點在飽和（a）與非飽和（b）環境中的CW 對比

3 新Idle Sense機制分析

3.1 ni 的計算

在非飽和環境中，因為緩沖區中很可能沒有要發送的分組，此時系統將一直處于空閑狀態，所以本文提出新的機制來統計該空閑時段。

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

3.2 新Idle Sense 機制

針對原Idle Sense 機制在非飽和環境中存在的兩個問題，新Idle Sense 機制做了如下兩方面的改進（如圖2中的兩個虛線框所示）。

圖2 顯示了新Idle Sense 機制的執行過程。在該機制中，每個節點在執行完maxtrans次之后，將更新平均連續空閑時隙數navg，然后再根據AIMD 算法動態地調整CW。其中兩處改進如下。

改進1nopt的取值（參見圖2 中的第一個虛線框）。

在新Idle Sense 機制中，每個節點通過比較其分組到達率λ與一個臨界值λ′的大小關系來區分飽和與非飽和環境。根據參考文獻[13-14]，λ′的表達式為：其中σ表示空閑時隙長度，Tc表示發送分組的沖突時間，Tc可根據文獻[13]中的表1 來計算。

如果λ≥λ′，則說明該節點處于飽和狀態。此時，新機制會選擇nopt_sat作為最優空閑時隙數nopt。nopt_sat可通過公式和計算：

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

如果λ＜λ′，則說明該節點處在非飽和狀態。此時，為了避免由于存在過多的空閑時隙而導致CW連續遞減，新機制會選擇比nopt_sat更大的nopt_nonsat來作為非飽和情況下的最優空閑時隙數。本文根據多次實驗結果觀察可知，當nopt_nonsat為30 時，能適應于大多數情況。因此，本文采用nopt_nonsat=30 作為最優空閑值。

改進2避免CW遞減為0（參見圖2的第二個虛線框）。

為了避免出現圖1（b）的情況，新Idle Sense 機制在每次動態調整CW之后，判斷當前CW值是否為零。如若CW已經為零，則將其重新賦值為當前系統內節點數目N，即CW=N。從而使得CW在下次可以根據該值進行動態調節，調節方法如圖2 中兩個虛線框中間所示。本文的模擬結果顯示，在非飽和環境中，當CW=N時，新機制的性能最優。

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

4 模擬結果

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

表1 802.11b 標準參數

4.1 吞吐量

圖3表示執行標準DCF機制、原Idle Sense和新Idle Sense 機制后所得的吞吐量模擬結果。橫坐標表示分組流量強度ρ，縱坐標表示吞吐量。其中ρ的表達式為：

其中B表示系統總帶寬。

圖3 三種機制的吞吐量比較

根據模擬結果可以看出，當流量強度較小（ρ＜0.3，即非飽和情況）時，由于原Idle Sense 在非飽和環境中存在的問題，使得原Idle Sense 機制獲得的吞吐量最低，且低于標準DCF 獲得的吞吐量。而改進后的新Idle Sense 機制明顯地提高了吞吐量，且其獲得的吞吐量和DCF 的吞吐量相同。

當流量強度較大（ρ＞0.3，即飽和情況）時，由于新Idle Sense 機制執行方法和原Idle Sense一樣，所以兩者獲得了相等的吞吐量，且均高于標準DCF 機制。

4.2 延時

圖4表示執行標準DCF機制、原Idle Sense和新Idle Sense機制后所得到的延時模擬結果，橫坐標表示分組流量強度，縱坐標表示分組發送延時。

圖4 三種機制的延時比較

根據模擬結果可以看出，當流量強度較小（ρ＜0.3，即非飽和情況）時，原Idle Sense 機制獲得的延時最高，且高于標準DCF 獲得的延時。而改進后的新Idle Sense機制降低了延時，并幾乎與DCF 獲得的延時相同。

當流量強度較大（ρ＞0.3，即飽和情況）時，兩種Idle Sense 機制獲得同樣的延時，且均小于標準DCF 機制的延時。

5 結束語

本文針對原Idle Sense機制在非飽和環境中存在的問題，提出了新的Idle Sense 機制。新機制不僅保留了原機制在飽和環境中高吞吐量和低延時的特點，也提高了原機制在非飽和環境中的吞吐量，同時也降低了延時。本文提出的新Idle Sense 機制增強了其在無線局域網中的實用性。

[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.