存在隱藏終端的ＩＥＥＥ ８０２．１１ｅ多跳無線網絡模型分析

摘要：首次將802.11e的接入機制放入多跳環境中進行仿真分析和定量研究。提出一種新的多跳環境下802.11e網絡模型，結合M/G/1/K排隊模型，定量分析在隱藏終端影響下802.11e網絡的MAC層吞吐率、MAC時延和幀丟失率，研究802.11e在多跳環境下性能表現的內在原因。經過仿真實驗結果與數值分析結果的對比，驗證了分析模型的準確性；通過有（無）隱藏終端影響下MAC層性能的對比分析，指出了802.11e在多跳無線網絡中支持QoS的局限性：受隱藏終端的影響，802.11e對不同接入等級的業務提供QoS區分的性能明顯降級。因而有必要研究隱藏終端問題的解決方案，提高802.11e在多跳環境下的性能。

關鍵詞：IEEE 802.11e； 增強型分布式信道接入； M/G/1/K排隊模型； 隱藏終端； 分析模型

中圖分類號：TN924.1

文獻標志碼：A

文章編號：1001－3695(2008)06－1867－05

0引言

IEEE 802.11[1]協議描述了用于無線局域網的物理層和MAC層協議，它提供的DCF機制由于其分布式的特點而廣泛應用于無線自組織網絡，但DCF不能提供QoS區分，不能滿足人們對實時業務的要求。IEEE 802.11e[2]在802.11的基礎上加入了QoS的相關內容。它引入EDCA，該機制結合幀間隔（IFS）和后退算法來提供業務區分服務，建立了一種依據傳輸業務種類分配帶寬的概率優先機制，高優先級業務能獲得更高的吞吐率和更低的接入時延。對不同接入等級的業務提供QoS區分是802.11e的主要特點，即使負載飽和，802.11e在單跳無線網絡中支持QoS區分的性能也不會明顯降級。然而，很多對802.11e EDCA性能的研[3~6]都沒能回答這樣兩個問題：802.11e在多跳無線網絡中有什么樣的性能表現；性能表現的內在原因是什么？本文首次將802.11e的接入機制放入到多跳環境中進行仿真分析和定量研究，回答了上述問題。

為了研究IEEE 802.11e網絡的性能，Xiao在文獻[4]中首先提出一種適用于EDCA接入機制的網絡模型，分析802.11e EDCA系統的飽和吞吐率、飽和時延和幀丟失率。Chen等人在文獻[5]中對802.11e EDCA在非飽和負載下的性能作了研究，他提出的網絡模型結合MAC層排隊系統，但假定排隊隊長為無窮大，這樣不能得到準確的時延分析結果。文獻[6]首次將M/G/1/K排隊模型用于分析EDCA接入機制，引入空閑狀態和不同接入等級的仲裁幀間隔（AIFS）的使用，分析了EDCA接入機制的局限性。上述對802.11e性能的研究都集中于單跳無線局域網（WLAN）的環境下。在多跳無線網絡中，節點的狀態不僅受偵聽范圍內競爭節點的影響，而且隱藏終端對節點帶來的干擾會大大降低節點上不同優先級業務爭用信道的性能。多跳環境下的復雜性使得MAC層性能的數學模型分析變得異常復雜，上述單跳環境下的分析結果不能直接用于多跳無線網絡。

為了解決隱藏終端問題，802.11協議建議了RTS/CTS接入方式。該協議假定隱藏終端處于接收節點傳輸范圍內。文獻[7]的研究指出收、發節點傳輸范圍以外的節點仍然對數據的傳輸產生干擾，當偵聽范圍大于傳輸范圍兩倍時，在多跳環境下使用RTS/CTS接入方式，隱藏終端問題得不到解決。文獻[8~12]對802.11 DCF在多跳環境下的性能作了研究，分析隱藏終端對802.11多跳無線網絡MAC層性能的影響。文獻[13]基于四個節點的拓撲結構，計算隱藏終端影響下的沖突率，文中對隱藏終端的定義沿用了802.11協議的定義，沒有考慮干擾范圍內節點引起的沖突問題。Calafate等人在文獻[14]中首次對802.11e多跳Ad hoc網絡的性能作了仿真研究，并得出結論：多跳環境并未影響802.11e支持QoS區分的性能。但他們未建立網絡模型作定量研究，也忽視了隱藏終端對不同接入等級業務帶來的影響。

本文旨在通過建模和仿真實驗來研究多跳環境下隱藏終端對802.11e協議的影響。提出一種新的802.11e多跳無線網絡模型（不同于文獻[3~6]的單跳網絡模型），結合M/G/1/K排隊模型，定量研究隱藏終端影響下的MAC層吞吐率、MAC時延和幀丟失率。分析數值計算與仿真結果，驗證網絡模型的準確性；通過比較有（無）隱藏終端影響下的MAC層性能，指出802.11e在多跳環境下支持QoS的局限性，回答了仿真實驗中802.11e性能表現的內在原因：多跳環境下，隱藏終端的影響導致沖突率遠遠大于單跳環境下的沖突率，使得802.11e支持QoS區分的性能明顯降級。



1 802.11e支持業務區分的特性

802.11e引入了一種新的信道接入方式，即混合信道接入方式（HCF）。HCF包括競爭信道接入方式（EDCA）和無競爭接入方式（HCCA）。HCF實現方式類似于802.11的PCF方式，當有中心節點存在的情況下，競爭接入方式和無競爭接入方式交替進行。在無中心節點時，節點采用EDCA工作方式。考慮到競爭方式是最普遍的信道接入方法，適用于Ad hoc網絡，本文主要關注該機制。

EDCA接入方式采用的是帶沖突避免的載波偵聽多路訪問協議（CSMA/CA），節點內部存在四個隊列緩存到來的業務，每個隊列采用相應的接入等級（AC）參數競爭信道。不同接入等級的參數包括仲裁幀間隔（AIFS），最小、最大競爭窗（CWmin[AC]，CWmax[AC]）等。在EDCA接入方式中，有數據發送的隊列在檢測到信道空閑AIFS[AC]時間后，進入后退過程。優先級高的業務，AIFS[AC]時間越短。式（1）是文獻[2]中推薦的AIFS[AC]的計算公式：

AIFS[AC]=AIFSN[AC]×SlotTime+SLFSTime（1）

式中SlotTime和SIFSTime為物理層參數。表1是文獻[2]中推薦的不同接入等級采用的信道競爭參數。

從表1可以看出，當有優先級為i、j的兩種業務同時競爭信道時，如果i優先級高于j，則有CWmin[i]

2 802.11e多跳無線網絡模型

文獻[8]在文獻[15]的基礎上提出了一種新的802.11 DCF分析模型，將文獻[15]中的模型應用到多跳環境下進行研究。本文擴展了文獻[8]的分析方法，與文獻[8]的模型主要區別在于考慮四種接入等級，進行信道的競爭接入，從而建立一種新的適用于802.11e接入機制的多跳無線網絡模型。模型分析主要分為三步：首先通過分析隱藏終端影響下的二進制指數后退過程來獲得某個時隙內不同優先級業務發送數據發生沖突的概率，以及業務的后退計數器遞減為0時發送數據的概率；然后依據第一步的結果，計算MAC層平均服務時間；最后結合M/G/1/K排隊模型，計算隱藏終端影響下的MAC層吞吐率、MAC時延和幀丟失率等性能。模型分析的三個步驟是數值計算的迭代過程，因為求解M/G/1/K排隊模型需要明確MAC層服務時間的分布情況；要計算MAC層平均服務時間需要知道業務隊列為空的概率；而隊列空的概率求解于M/G/1/K排隊模型。這樣計算MAC層平均服務時間和排隊模型的求解形成了一個迭代過程，如圖1所示。

本文以下給出網絡模型三部分的詳細分析過程。首先列出兩點約定：

a）為了簡單說明問題，本文不考慮節點內部的調度算法，即設定每個業務為一個獨立的信道競爭實體，并不影響802.11e接入機制在多跳環境下的性能研究。

b）設定第i類業務服從到達率為λi的泊松過程。

2．1隱藏終端影響下的二進制指數后退過程

對多跳無線網絡中沖突率的分析首先從單跳飽和情況開始，逐步推廣到多跳情況，從而在模型中反映出隱藏終端對802.11e接入機制帶來的影響。

首先設節點的偵聽范圍內第i類業務的個數為Ni(i=0，1，2，3）。在飽和狀態下，業務的發送隊列時時處于滿狀態，業務任何一次被服務的過程（發送過程）都要經歷二進制指數后退。本文用Wi， j表示第i類業務處在第j個后退級數時的競爭窗口，則Wi， 0=CWmin[i]；m為最大重傳次數;m′為最大后退級數;CWmax[i]=2m′CWmin[i]。業務從競爭窗中隨機選擇一個時間值進行后退延遲，則第一次后退延遲的平均時間可以表示為wi， 0/2（時隙）。令第i類業務在后退計數器變為0時，發送數據發生沖突的概率為ci，則成功發送的概率為1-ci。一旦沖突發生，競爭窗長度將擴大為原來的兩倍，因此第i類業務成功發送數據幀所需后退時間的平均值wb_i(m＜m′＝可以表示為

2．3M/G/1/K排隊模型分析

基于前面的約定，在802.11e EDCA接入方式下，每類業務的緩存隊列可以看做M/G/1/K排隊模型。令ε(t)(t≥0)表示在t時刻排隊系統所處的狀態，則ε(t)的狀態空間為S={I，A0，A1，A2，…，AK}。其中：AK表示在信道忙的條件下排隊隊長為k；I表示信道空閑，排隊隊列為空。由于MAC層服務時間是一般分布，對任選的一個時刻t，正在接收發送過程的數據幀可能還沒有發送完成，從時刻t起的剩余服務時間分布不再具有無記憶性，于是排隊系統的隊長不再具有Markov性質。如令tn為第n個數據包服務完畢離開排隊系統的時刻，則εn=ε(t-n），εn表示在tn時刻之前排隊系統所處的狀態，可以認為εn是隊長過程的嵌入Markov鏈[6]。此時嵌入Markov鏈的狀態空間為S′={A0，A1，A2，…，AK}。令pi，j表示狀態Ai到A j的一步轉移概率，有

3模型驗證與802.11e在隱藏終端影響下的性能分析

為了驗證本文提出的802.11e多跳無線網絡模型的準確性，需要將數值分析結果與仿真結果作比較。仿真采用的軟件是Berkeley發布的離散事件仿真器NS2的2.29版本，在Red Hat 9.0平臺上仿真。MAC層使用802.11e協議，設置信道帶寬為2 Mbps，節點的傳輸范圍為250 m（NS2默認值），仿真時間25 s。

為了簡單說明問題，考慮網絡中只有接入等級為AC3和AC0兩種業務。網絡的拓撲結構如圖4所示，可以計算節點1受干擾的范圍ri=1．78×dr=1．78×170=302．6 m[7]。其中：dr表示收、發節點的實際距離。發節點的偵聽范圍與收節點的干擾范圍相交之外的區域（在干擾范圍內）為隱藏區域，隱藏區域中的節點為隱藏終端。當偵聽范圍400 m時，節點2是隱藏終端，依據式（6），有N0=N3=1，Nh_0=Nh+3=1，如圖4（b）所示；當偵聽范圍擴大到550 m，節點0和2爭用同一信道發送數據，拓撲結構中沒有隱藏終端，有N0=N3=2、Nh_0=Nh_3=0，如圖4（a）所示。表2是仿真與數值計算使用的參數，其他參數按照文獻[1]中的802.11物理層設置，見表3。采用802.11物理層參數主要為了符合NS2的2.29版本中的802.11e模塊。各類業務流都服從到達率為λ的泊松過程，則輸入業務的負載量可以表示為S=Pλ。其中：P為平均數據幀長度。

圖5給出兩類優先級業務在有（無）隱藏終端影響下吞吐率對比的曲線圖，仿真每隔0.3 s取吞吐率平均值。每類業務輸入負載為500 Kbps時，圖5（a）顯示出沒有隱藏終端的影響，高優先級業務AC3占用大量帶寬，低優先級業務AC0只能分享信道的少量帶寬，這是802.11e支持業務區分的性能表現。當AC3受隱藏終端的影響，吞吐率大約平均下降40%。圖5（b）顯示當業務負載量加大到600 Kbps，兩種情況下的AC3吞吐率都發生降級。受隱藏終端的影響，AC3的吞吐率接近于低優先級AC0，與無隱藏終端情況下的AC3相比下降達到80%。如果繼續加大負載，AC3的吞吐率降級受隱藏終端的影響更加明顯，此時802.11e支持QoS區分的性能無法表現出來。表4列出業務負載從600 Kbps增加到1.2 Mbps過程中，低優先級業務AC0在有（無）隱藏終端影響下的收、發數據包情況。可以觀察到，隱藏終端的影響使得低優先級業務更接近于餓死狀態。

圖6和7分別給出有（無）隱藏終端情況下的數值計算與仿真結果。從隨負載變化的MAC層吞吐率、MAC時延和幀丟失率看出，仿真結果與理論分析基本匹配，證實了802.11e多跳網絡模型的準確性。需要指出的是負載量飽和情況下，仿真的時延與數值計算結果相比有較大波動，這與仿真實驗條件和網絡模型的相關假設有關，并不影響對802.11e在多跳環境下的性能研究。

如圖6所示，在非飽和階段，信道有足夠帶寬承載各類業務流，業務吞吐率隨著負載的增加而線性增加。AC3的時延從20增加到26 ms，幀丟失率最大為0.02，此時802.11e提供嚴格的QoS保證。隨著負載的繼續增加，各類優先級業務的QoS性能都趨于穩定，同時低優先級業務QoS性能明顯差于高優先級業務，這時802.11e不能為實時業務提供嚴格的QoS保證，但基于業務區分的QoS性能明顯表現出來。然而在隱藏終端影響下，各類業務負載量增加到飽和時，優先級高的業務QoS性能降級的趨勢遠遠大于無隱藏終端的情況，如圖7所示。無隱藏終端時，AC3的吞吐率為296 Kbps，隱藏終端的影響使得AC3吞吐率降到50 Kbps，下降了大約83%，MAC時延從50 ms上升到381 ms，幀丟失率也大大提高。尤其是負載量從600 Kbps增加到900 Kbps時，仿真結果顯示了更加糟糕的情況，AC3的吞吐率、時延和幀丟失率幾乎接近于AC0的MAC層性能。這樣802.11e基于業務區分的QoS性能無法表現出來，甚至可能造成高優先級業務接近餓死狀態。

圖8給出了有（無）隱藏終端情況下，AC3的沖突率對比圖。從圖中可以看出，多跳環境下，隱藏終端的影響導致AC3的沖突率遠遠大于單跳環境下AC3的后退計數器遞減到0時爭用信道發生沖突的概率，因而隱藏終端的存在大大降低了高優先級業務的QoS性能。

4結束語

本文首次將802.11e的接入方式放入到多跳無線網絡環境下進行仿真分析和定量研究。提出了一種適用于分析802.11e的多跳無線網絡模型，結合M/G/1/K排隊模型分析了802.11e在多跳環境下的MAC層吞吐率、MAC時延和幀丟失率等性能。經過仿真實驗結果與理論分析結果的對比表明，新的模型很好地描述了現有的802.11e接入方式在多跳環境下的性能。依據模型分析與仿真實驗結果，比較有（無）隱藏終端影響下的MAC層性能，得出結論：在多跳環境下，由于隱藏終端的影響，802.11e支持業務區分的性能明顯降級，甚至可能導致高優先級業務接近“餓死”，因而將802.11e應用于多跳無線網絡中支持QoS有很大的局限性，有必要研究隱藏終端問題的解決方案。

文獻[9]研究了在鏈式拓撲結構中，802.11多跳無線網絡的端到端吞吐率性能。隱藏終端導致了較高的丟包率和鏈路失敗的重路由問題，使得802.11在多跳無線網絡中吞吐率明顯降級。為了緩減隱藏終端的影響，文獻[9]提出了一種負載量控制方案。負載量控制的目的是防止業務流飽和，從圖7中可以觀察到，非飽和負載下隱藏終端幾乎不產生任何影響，所以負載量控制本質上是一種接納控制方案。文獻[10]通過對TCP流在802.11多跳Ad hoc網絡中的性能研究指出802.11并不適用于多跳Ad hoc網絡，隱藏終端的影響對TCP流產生吞吐率的不公平性和不穩定性問題。文獻[11]針對文獻[10]中指出的問題提出一種信號捕獲方案，即ps＞pn+CPThreshold。其中：ps為有用信號功率；pn為來自于隱藏終端的噪聲功率；CPThreshold為捕獲門限。滿足上式隱藏終端問題能夠解決。以上兩種解決隱藏終端問題的方案都是針對802.11在多跳無線網絡中的性能研究，802.11e是802.11的QoS增強版本，為了提高802.11e在多跳環境下的性能，有必要提出隱藏終端問題的解決方案，這是后續研究的主要內容。

參考文獻:

[1]ANSI/IEEE Std.802.11， ISO/IEC 8802－11: 1999(E)， Wireless LAN medium access control(MAC) and physical layer(PHY) specifications[S]. 1999.

[2]IEEE 802.11 WG.IEEE 802.11E/D 13.0， Draft supplement to part II:wireless medium access control(MAC) and physical layer(PHY) specifications:medium access control(MAC) enhancements for quality of service(QoS)[S]. 2005.

[3]王剛，周銀東，梅順良. IEEE 802.11e EDCA網絡模型分析[J]. 清華大學學報:自然科學版， 2005， 45(10):1389－1392.

[4]XIAO Y. Performance analysis of priority schemes for IEEE 802.11 and IEEE 802.11e wireless LANs[J]. IEEE Trans on Wireless Communication， 2005， 4(4):1506－1515.

[5]CHEN X， ZHAI H， FANG Y. Enhancing the IEEE 802.11e in QoS support:analysis and mechanism[C] //Proc of the 2nd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks. San Francisco: [s.n.]， 2005:538－549.

[6]BAI X，MAO Y M， XIE J. Performance investigation of IEEE 802.11e EDCA under non－saturation condition based on the M/G/1/K model[C] //Proc of the 2nd IEEE Conference on Industrial Electronic and Applications. Harbin: [s.n.]， 2007:122－129.

[7]XU K， GERLA M，BAE S. How effective is the IEEE 802.11 RTS/CTS handshake in Ad hoc networks?[C] //Proc of IEEEGLOBECOM. St Louis: [s.n.]， 2002:72－76.

[8]OZDEMIR M，McDONALD B. A queuing model of multi－hop wireless Ad hoc networks with hidden nodes[C] //Proc of IEEE/ACM PE－WASUN’04. Venezia: [s.n，]， 2004:56－60.

[9]NG C，LIEW S. Offered load control in IEEE 802.11 multi－hop Ad hoc networks[C] //Proc of the 1st IEEE International Conference on Mobile Ad hoc and Sensor System. Fort Lauderdale， Florida: [s.n.]， 2004:80－89.

[10]XU S， SAADARI T. Does the IEEE 802.11 MAC protocol work well in multi－hop wireless Ad hoc networks?[J]. IEEE Communications Magazine， 2001， 39(6): 130－137.

[11]JIANG Li－bin，LIEW S C. Removing hidden nodes in IEEE 802.11 wireless networks[C] //Proc of IEEE Vehicular Technology Conference. 2005:1127－1131.

[12]黃堅，畢光國. 存在隱藏終端的無線LAN性能仿真研究[J]. 通信學報，1999，20(3): 68－74.

[13]RAY S，STARROBINSKY D，CARRUTHERS J B. Performance of wireless networks with hidden nodes:a queuing theoretic analysis[J]. Journal of Computer Communications，2005， 28(10): 1179－1192.

[14]CALAFATE C T， MANZONI P. Assessing the effectiveness of IEEE 802.11e in multi－hop mobile network environments[C] //Proc of IEEE MASCOTS2004. Vollendam， The Netherlands: [s.n.]， 2004:205－212.

[15]TAY Y C，CHUA K C. A capacity analysis for the IEEE 802.11 MAC protocol[J]. ACM/Baltzer Wireless Networks， 2001， 7(2):159－171.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文