基于最小競爭窗口的ＩＥＥＥ ８０２．１１區分服務機制及其性能分析

摘要：針對無線ad hoc網絡不能提供數據流優先級區分的問題，本文提出了一種基于802.11 DCF退避算法的改進機制，該機制通過設置不同的MAC層最小競爭窗口來實現數據流的區分服務，使發送高優先級數據流（如實時數據流）的節點更容易連接信道，從而使高優先級數據流占有更多帶寬資源。數學分析表明，該策略能有效的提高高優先級數據流的傳輸性能。

關鍵詞：802.11DCF; 區分服務; 馬爾科夫鏈模型; 性能分析

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)35-2120-03

Service Differentiation Scheme Based on Minimum Contention Windows for IEEE 802.11 WLAN

WU Zhi-qiang， ZHU Hong-li

(Henan Polytechnic University， Jiaozuo 454000， China)

Abstract: Considering that IEEE 802.11 ad hoc networks can not provide any priority scheme， this paper proposes a new scheme based on the 802.11 DCF back-off algorithm. The algorithm， by setting different number of Minimum Contention Windows at the data link layer， can make high-priority data flow(such as Real-time data flow) access channel more easily. As a result， the high-priority data flow can obtain more bandwidth. Our mathematical analyses demonstrate that the new algorithm improve the transmission performance of data flows in high priority significantly.

Key words: 802.11DCF; diffserv; markov chain model; performance analysis

1 引言

無線ad hoc網絡是一種無固定控制中心、多跳、對等式網絡，它不需要任何額外的架構設備，只需要接點配以無線收發裝置即可隨時組成無線局域網絡。這種網絡實現簡單、靈活、不需要昂貴的基礎設施、成本低，所以在軍事通信和民用通信領域得到了廣泛的應用。但ad hoc網絡并不能提供業務的區分，難以滿足那些對QoS有嚴格要求的業務（如實時流媒體業務）的傳輸要求。

目前，對于在ad hoc網絡中提高實時業務的服務質量研究大多集中于MAC層，大部分研究者提出的支持QoS的MAC協議大多建立在IEEE802.11 DCF[1]機制上。其中的QoS增強機制主要集中在修改退避算法、幀間間隔、最大退避次數、最大幀長度等方面[2-7]。本文主要研究通過減小高優先級數據流的MAC層最小競爭窗口值來實現業務的區分服務，并利用相關數學模型對修改后的退避算法進行分析。分析結果表明，該策略能使高優先級數據流占用相對較多的帶寬，從而提高高優先級數據流的傳輸性能。

本文第2節簡要介紹IEEE 802.11 DCF退避機制；第3節則利用相關數學模型深入分析本文建立的區分服務機制；第4節對區分服務模型的性能進行分析和評價；第5節總結全文。

2 802.11 DCF描述

802.11DCF機制定義了兩種信道接入機制，即基本接入機制和RTS/CTS機制。在基本接入方式下，一個節點在發送數據分組之前要監聽信道，如果信道空閑超過一個分布式幀間間隔(DIFS)，該節點就啟動一個退避過程，DIFS之后的時間被劃分成一個個的時隙（time slot，記為σ），當信道空閑時間每超過一個時隙時間σ，計數器的值就減1。若探測到信道忙（有分組傳輸或者分組沖突）則退避計數器凍結，當再次探測到信道空閑超過一個分布式幀間間隔(DIFS)時計數器再次激活，當計數器的值到達0 時節點開始發送數據分組。如果數據分組傳輸失敗，則啟動一個指數退避過程。每個分組傳輸需要后退的時隙數目從區間（0，W-1）中均勻選取，W稱為競爭窗口，m為最大退避次數。每次開始傳輸一個新的分組時，競爭窗口被設置成最小競爭窗口，記為CWmin。此后每次傳輸失敗，競爭窗口加倍，直到達到一個最大值CWmax。若數據分組被成功接收，目的節點需要回復一個確認分組（ACK）。

在RTS/CTS接入方式下，節點遵循相同的指數退避機制，只是當退避計數器的值為0時發送方不是直接發送數據分組，而是發送一個稱為RTS的短分組，目的節點收到RTS分組后需要回復一個CTS分組，發送方接收到CTS分組后方可開始發送數據分組。特別是當數據分組很大的情況下RTS/CTS接入方式明顯優于基本接入方式，因為它減小了競爭階段用于檢測信道狀況的幀長度。在理想信道的情況下，僅僅當兩個或兩個以上的數據分組嘗試在同一個時隙的起始點發送時會導致沖突，當兩個發送節點都采用RTS/CTS機制時，沖突僅僅會發生在RTS分組，發送方因收不到CTS分組而得知有沖突的發生。

3 區分服務機制的數學建模分析

本文參考了文獻[8，9]中所用的方法，對本文提出的區分服務機制進行了數學建模分析，并通過相關模型得出了兩種優先級數據流的飽和吞吐量、以及總體飽和吞吐量的計算方法。

3.1 馬爾科夫鏈分析模型

在本文中，我們將網絡中的數據流分為兩種，一種為對時延敏感的數據流，我們簡稱RT（Real-Time）流；另一種為對時延不敏感的數據流，我們簡稱BF（Best-Effort）流。顯然RT流對QoS的要求高于BF流。因此本文設置RT流為高優先級數據流，而BF流為低優先級數據流。

為便于分析，定義i為數據流的優先級類別，取值為0或1，其中0表示高優先級的RT流，1代表低優先級的BF流。兩種數據流的分組都采用相同的退避機制競爭信道，因此兩種數據流的競爭窗口值可用公式(1)計算。

(1)

其中Wi，0為數據流i的最小競爭窗口值，CWi，max為數據流i的最大競爭窗口值，j為退避計數器的退避階段，m為最大退避次數，L為MAC層的最大重傳次數，這里我們設置W0，0

該文參考文獻[8]和[9]中所用的方法，對改進后的退避算法作如下建模分析。我們假設：

1) 網絡中每個節點只發送一類數據分組，并且每一類數據分組在傳輸過程產生沖突的概率恒定且獨立。

2) 信道是理想的，即分組丟失只會是由沖突造成的。

3) 系統處于飽和狀態，每個節點在成功進行一次分組發射后，立即監聽信道，待其退避計數器退至0時馬上發送下一分組。

對于傳輸第i類數據分組的節點，設B(i，t)表示其在時刻t的退避計數器值，S(i，t) 表示其在時刻t的退避階段。根據文獻[8]和[9]，{S(i，t)， B(i，t)}構成了一個離散的二維馬爾科夫鏈模型。令pi為屬于數據流i的數據分組發送時產生沖突的概率，pi，b表示屬于數據流i的數據分組在退避階段檢測到信道忙的概率。則其單步狀態轉移概率如下（我們簡記）： (2)

記為馬爾科夫鏈的穩態概率分布，由馬爾科夫鏈的相關性質可以得到如下關系：

(3)

(4)

(5)

(6)

定義τi為發送第i類數據分組的節點在一個隨機選擇的時隙中發送分組（RTS或Data）的概率。因為節點發送分組只會在退避計數器的值為0時才發送，所以有：

(7)

設發送屬于數據流i的數據分組的節點為ni個，pi，b表示發送屬于數據流i的數據分組的節點在退避階段檢測到信道忙的概率。在本模型中，信道忙只會在有數據分組成功發送或者是發生分組沖突的情況下發生。因此，pi，b也可以理解為在上一個時隙內余下的（n0+n1-1）個節點中至少有一個節點發送了分組。由此，我們可以得出：

(8)

(9)

pi表示屬于數據流i的數據分組發送時產生沖突的概率。在本模型中，分組發生沖突只會是剩余的(n0+n1-1)個節點中至少有一個節點也在同一時隙內發送了分組。因此，可以有以下結論：

(10)

(11)

在節點數量、最小競爭窗口、最大退避次數、MAC層最大重傳次數等參數已知的情況下，可以由公式（6-11）計算出p0、p1、p0，b、p1，b的值，并且有唯一值。

3.2 飽和吞吐量分析

設Ptr為在一個隨機選擇的時隙內網絡中至少有一次分組發送的概率；Pi，s表示在一個隨機選擇的時隙中成功發送一個屬于數據流i的數據分組的概率；而Ps表示在一個隨機選擇的時隙中成功發送一個任何一種數據分組的概率。則有以下結論：

(12)

(13)

(14)

Ps=P0，s+P1，s (15)

設S為歸一化的系統飽和吞吐量，定義為成功發射有效載荷的信道時間在總的信道時間中所占的份額。Si表示數據流i所占有的飽和吞吐量的份額。

參考文獻[8]和[9]，可以得出數據流i所占用的吞吐量為：

(16)

系統的飽和吞吐量為：

(17)

其中，Ts表示因為一個成功發送而使信道檢測為忙的時間；Tc表示因為一個分組沖突而使信道檢測為忙的時間；σ表示空閑時隙的持續時間。E(pi)為數據流i的有效載荷的平均大小；E(p)則是系統中有效載荷的平均大小；我們假設MAC層數據分組大小恒定，所以有E(p0)= E(p1)= E(p)，這里E[pi]，E(p)，Ts，Tc，σ的值具有相同的單位。該文只考慮了基本接入機制，RTS/CTS機制可以以此類推。

參考文獻[8]，得出：

(18)

4 區分服務模型的數學分析與評價

為驗證上述分析的正確性，本節將采用數學分析的方法對在基本接入機制下改進的具有區分服務功能的MAC層協議進行性能分析。本文所采用的參數如表1所示。假設MAC層發送的數據分組大小恒定，且有n0=n1=0.5*n（n0為發送RT分組的節點的數量，n1為發送BF分組的節點的數量，n為網絡中的節點總數）。

圖1為兩種數據流在基本接入機制下所占有的飽和吞吐量對比分析。從中可以很明顯的看出本文提出的方法能夠使RT流占用相對較多的帶寬資源，且隨著節點數量的最多，BF流的吞吐量會有所下降，而RT流占用的吞吐量基本維持不變。

圖2為改進后的系統飽和吞吐量與標準802.11DCF機制下的飽和吞吐量在基本接入機制下的的變化情況，從中可以看出隨著節點數量的最多，損失的帶寬資源會加大，但加大的幅度不是很大，因而不會影響系統的整體性能。

5 結束語

針對無線ad hoc網絡不能提供數據流優先級區分的問題，本文提出了一種基于802.11MAC協議的改進機制，該機制通過設置不同的MAC層最小競爭窗口來實現數據流的區分服務，使發送高優先級數據流（如實時數據流）的節點更容易連接信道，從而使高優先級數據流占有更多帶寬資源。數學分析表明，該策略能有效的提高高優先級數據流的傳輸性能。

我們下一步的工作將繼續深入探討在無線ad hoc網絡中如何引入區分服務模型，以及如何提高實時多媒體業務在無線網絡中的傳輸性能。

參考文獻：

[1] IEEE Std 802.11-1999. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S]. International Standard ISO/IEC 8802-11: 1999(E) ANSI/IEEE Std 802.11，1999.

[2] 李云， 隆克平等. IEEE802.11無線局域網中的一種支持業務區分的回退算法[J]. 電子學報， 2006，10(34):1877-1890.

[3] Jianhua He， Lin Zheng， et al. Analytical model for service differentiation schemes for IEEE 802.11 wireless LAN [J ]. IEICE Transactions on Communications， 2004， E87-B(6):1724-1729.

[4] Li Bo， Li jianDong et al. Supporting service differentiation with enhancements of the IEEE 802.11 MAC protocol:model and analysis[J]. Science in China series F: Information Sciences. 2007，50(5):732-746.

[5] Yang Xiao， Yi Pan. Differentiation， QoS guarantee， and optimization for real-time traffic over one-hop ad hoc networks[J]. IEEE Transactions on Parallel and Distributed Systems， 2005，16(6):538-549.

[6] 楊宗凱， 許昌春， 等. 基于分組到達率的IEEE802.11無線局域網區分服務方法[J]. 電子學報， 2006，10(34):1864-1867.

[7] 王朝陽， 孫丹丹， 等. 帶區分服務擴展的802.11MAC協議及其性能分析[J]. 通信學報， 2007，28(3):1-7.

[8] Giuseppe Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications， 2000， 18(3): 535-547.

[9] Yang Xiao. Saturation Performance Metrics of the IEEE 802.11 MAC[H]. Proceedings of The IEEE Vehicular Technology Conference， Oct 2003， 6-9:1453-1457.