基于ＩＥＥＥ ８０２．１１ｂ無線網(wǎng)絡(luò)的ＭＡＣ協(xié)議改良沖突解決算法

摘要：研究基于介質(zhì)訪問控制協(xié)議（MAC）的分布式爭用問題的主要焦點(diǎn)就是設(shè)計(jì)有效的具有高吞吐量性能的MAC協(xié)議。該文提出在無線局域網(wǎng)中基于MAC協(xié)議的有效爭用方法，即改良的沖突解決算法（DCR）。該算法主要做了以下幾方面的改良和創(chuàng)新：對所有現(xiàn)用網(wǎng)點(diǎn)主動的分配補(bǔ)償時間，提高解決沖突的速度；當(dāng)確定固定數(shù)量的連續(xù)空閑時間片被探測到時，對成功包傳輸?shù)恼军c(diǎn)使用較小的爭用窗口，以指數(shù)級速度減少補(bǔ)償時間片和減少空閑時間片的平均數(shù)。該文提出的改良沖突解決算法提供了高吞吐量性能和在局域網(wǎng)中的低執(zhí)行時間。

關(guān)鍵詞：介質(zhì)訪問控制協(xié)議（MAC）；補(bǔ)償時間；改良的沖突解決算法（DCR）

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)35-2123-03

DCR Algorithm of MAC Protocols Based on IEEE 802.11b Wireless Networks

XIAO Yi1，2， LIU Lian-hao1

(1.School of Information Science and Engineering， Central South University，Changsha 410083，China;2.Information Science and Technology College of Hunan Agricultural University， Changsha 410128，China)

Abstract: Design of efficient Medium Access Control (MAC) protocols with both high throughput performances is a major focus in distributed contention‐based MAC protocol research. In this paper， we propose an efficient contention‐based MAC protocol for wireless Local Area Networks， namely， the Developed Collision Resolution (DCR) algorithm. This algorithm is developed based on the following innovative ideas: to speed up the collision resolution， we actively redistribute the backoff timers for all active nodes; to reduce the average number of idle slots， we use smaller contention window sizes for nodes with successful packet transmissions and reduce the backoff timers exponentially fast when a fixed number of consecutive idle slots are detected. We show that the proposed DCR algorithm provides high throughput performance and low latency in wireless LANs.

Key words:MAC;backoff;DCR algorithm

1 簡介

無線網(wǎng)絡(luò)中基于介質(zhì)訪問控制協(xié)議（MAC）的研究以ALOHA開始，之后相繼提出MACA、 MACAW、FAMA 和 DFWMAC，用于合并CSMA技術(shù)和避免沖突的RTS和CTS的握手機(jī)制。目前最流行的基于爭用問題無線MAC協(xié)議是CSMA/CA，已經(jīng)成為IEEE 802.11b MAC協(xié)議的基礎(chǔ)[1]。但是，我們可以看到如果活動用戶數(shù)目增加，而由于沖突率非常高，IEEE 802.11b MAC協(xié)議的吞吐量性能就會急劇下降。很多研究都集中在分析和提高IEEE 802.11b MAC協(xié)議的表現(xiàn)。

要增加基于MAC協(xié)議的吞吐量性能，盡量減少每個爭用循環(huán)里的消耗是一種有效的沖突解決機(jī)制[2]。在本文中，我們提出一種新的有效的基于MAC的分布式爭用算法，也就是改良的沖突解決算法（DCR）。我們觀察到在每個爭用循環(huán)中，MAC算法來自于因?yàn)檠a(bǔ)償產(chǎn)生的包沖突和空閑時間片的浪費(fèi)。DCR算法將通過擴(kuò)大爭用決定中的沖突位置和推遲位置的爭用窗口來達(dá)到迅速解決沖突的目的。

2 IEEE 802.11b 介質(zhì)訪問控制

最流行的基于爭用的MAC協(xié)議就是CSMA/CA，目前廣泛應(yīng)用于IEEE 802.11b局域網(wǎng)中。

一個包傳送循環(huán)是一個從源站點(diǎn)成功發(fā)出的包傳送開始并跟隨著從目標(biāo)站點(diǎn)發(fā)出的承認(rèn)（ACK）[3]。一般的IEEE 802.11b MAC協(xié)議是這樣操作的（為簡單起見，我們只考慮分布式調(diào)和功能，而沒有考慮RTS-CTS握手）：如果一個站點(diǎn)有一個包需要發(fā)送，它會通過載波感覺機(jī)制來檢查媒介狀態(tài)。如果媒介是空閑的，那么傳送將會進(jìn)行。如果媒介是繁忙的，站點(diǎn)將會等待，直到媒介為空閑狀態(tài)，而補(bǔ)償程序隨之被調(diào)用。站點(diǎn)將會根據(jù)當(dāng)前爭用窗口（CW）大小將補(bǔ)償時間設(shè)置一個隨機(jī)補(bǔ)償時間。

補(bǔ)償時間（BT）= 隨機(jī)數(shù)×aSlotTime

其中，隨機(jī)數(shù)是從0到CW-1中隨機(jī)產(chǎn)生的整數(shù)。

在分布協(xié)調(diào)功能幀間隔（DIFS）空閑時間后，站點(diǎn)會執(zhí)行補(bǔ)償程序，通過載波感覺機(jī)制來判斷在每個補(bǔ)償時間片內(nèi)是否有活動存在。如果在一個特定的補(bǔ)償時間片內(nèi)，媒介被判斷為空，然后補(bǔ)償程序就會通過aslottime減少它的補(bǔ)償時間。如果在某個站點(diǎn)中，媒介一直都被判斷為繁忙，則補(bǔ)償程序就暫緩執(zhí)行。如媒介處于DIFS空閑時間，補(bǔ)償程序就會重新開始。只要補(bǔ)償時間為0，傳送就會開始。源站點(diǎn)在給目標(biāo)站點(diǎn)傳送了一個數(shù)據(jù)包后，如果源站點(diǎn)收到了一個承認(rèn)（ACK），并且在這個短的幀間間隔（SIFS）空閑時期沒有發(fā)生錯誤，傳送過程將會被認(rèn)為成功完成。這樣的話，源站點(diǎn)的爭用窗口將被設(shè)置為初始（最小化）狀態(tài)。如果這個傳送并沒有成功完成，爭用窗口大小將被擴(kuò)大，這個過程被稱作是二進(jìn)制指數(shù)補(bǔ)償（BEB），可用來解決爭用循環(huán)中的沖突。更詳細(xì)的操作可以在參考文獻(xiàn)4中找到。

3 改進(jìn)后的無線局域網(wǎng)沖突解決算法

3.1 改進(jìn)后的沖突解決算法的基本思想

在爭用期間，導(dǎo)致IEEE 802.11b MAC協(xié)議的傳送失敗（我們只考慮因?yàn)榘鼪_突產(chǎn)生的失敗），主要是由于補(bǔ)償影響了吞吐量性能和空閑時間片。

在高交通負(fù)荷下（如：所有的M站點(diǎn)都有包要傳送），基于各態(tài)歷經(jīng)性假設(shè)，我們可以得到下面吞吐量表達(dá)式：

（公式 1）

式中E[Nc]表示一個有效傳送時間內(nèi)（或者是一個有效的傳輸循環(huán)）的平均沖突數(shù)目。E[Bc]是由每個爭用期間補(bǔ)償產(chǎn)生的空閑時間片的平均個數(shù)。ts表示時間片長度（例如：aSlottime），m是平均包長度。

對這個結(jié)果來說，最好的腳本將是如下內(nèi)容：一個成功的包傳輸將跟隨著另一個包傳輸， E[Nc] = 0，E[Bc] =0，這樣吞吐量將是：

（公式 2）

只有完美的安排才能出現(xiàn)這樣的結(jié)果，在這種情況下，每個站點(diǎn)都能發(fā)送包，在每個爭用區(qū)間，ptrans(i)的值如下：

(公式3)

這意味著如果當(dāng)今的包傳輸權(quán)利被分配到i站點(diǎn)，且只有i站點(diǎn)可以傳送，全部其他站點(diǎn)將延遲他們的包傳輸。

假設(shè)在一些隨機(jī)補(bǔ)償計(jì)劃下，我們假設(shè)補(bǔ)償時間隨機(jī)選擇，那么在當(dāng)前爭用期間，站點(diǎn)i傳送包的可能性將取決于補(bǔ)償時間。

（公式 4）

式中Bi是站點(diǎn)i的補(bǔ)償時間。這意味著，如果站點(diǎn)i的補(bǔ)償定時器為0（Bi=0），那么它的補(bǔ)償時間也為0（BT = BiaSlotTime = 0），站點(diǎn)i可以立即傳送包，表明站點(diǎn)i在爭用期間可以以1概率傳送包。如果站點(diǎn)i的補(bǔ)償定時器為∞，那么他的補(bǔ)償時間也為∞，表明站點(diǎn)i在爭用期間可以以0概率傳送包。依上所述，（公式3）就轉(zhuǎn)變成（公式5）：

（公式 5）

因此，我們可以得出以下結(jié)論，如果我們可以如此改進(jìn)基于爭用的MAC算法：在每個爭用期間，分配一個補(bǔ)償定時器0給一個站點(diǎn)，同時分配給其他站點(diǎn)補(bǔ)償定時器∞，我們就可以達(dá)到完美的調(diào)度，從而得到最大的吞吐量。不幸的是，這種基于爭用的MAC算法在實(shí)際中并不存在。然而，這也給我們提供了一個在MAC協(xié)議設(shè)計(jì)中怎樣去提高吞吐量性能的基本想法。我們可以使用完美計(jì)劃中的操作特性去設(shè)計(jì)接近完美計(jì)劃行為且更有效的基于爭用的MAC算法。

3.2 改進(jìn)后的沖突解決算法

IEEE 802.11b 介質(zhì)存儲控制協(xié)議的主要缺點(diǎn)是，當(dāng)現(xiàn)用站點(diǎn)數(shù)目增加時，沖突解決緩慢。在改良的沖突解決算法中，我們對延遲的站點(diǎn)改變其爭用窗口大小，并且對所有潛在的發(fā)生站點(diǎn)重新分配補(bǔ)償時間，動態(tài)避免“將來”的潛在沖突[5]。用這樣的方法，我們可以很快的解決包沖突的問題。更重要的是，改良的算法保留了IEEE 802.11b介質(zhì)存儲控制的實(shí)現(xiàn)的簡單性。

改良的沖突解決算法具有以下特點(diǎn)：

1) 使用比IEEE 802.11b MAC更小的初始化（最小化）爭用窗口minCW；

2) 使用比IEEE 802.11b MAC更大的最大化爭用窗口maxCW；

3) 當(dāng)位于沖突站和延遲站時，提高該站的爭用窗口大小；

4) 當(dāng)一定數(shù)量的連續(xù)空閑時間片被探測到時，補(bǔ)償時間片成指數(shù)級速度減少。

詳細(xì)的DCR算法根據(jù)站點(diǎn)的情況描述如下：

1) 補(bǔ)償過程：所有現(xiàn)用站點(diǎn)將監(jiān)控介質(zhì)。如果站點(diǎn)檢測到時間片的介質(zhì)，將用一個時間片來減少補(bǔ)償時間（BT），即：BTnew =BTold-aSlotTime (or slot)。當(dāng)其補(bǔ)償時間片為零時，該站點(diǎn)將傳輸一個包。如果有[(minCW+1)×2-1]個連續(xù)空閑時間片被探測到，其補(bǔ)償時間片將以指數(shù)級速度減少，即：BTnew = BTold / 2 (如果 BTnew < aSlotTime，，則BTnew = 0)。對于網(wǎng)絡(luò)的影響就是：當(dāng)一個站點(diǎn)耗盡了所有的傳輸包的時候，不必要浪費(fèi)的閑置補(bǔ)償時間片將會減少。

2) 傳輸失敗（包沖突）：如果一個站點(diǎn)注意到其包傳輸失敗，很可能是由于包沖突引起（即：如果接收從目標(biāo)接收站傳來的確認(rèn)信息失敗），該站爭用窗口的大小就應(yīng)該增加并且選擇一個隨機(jī)補(bǔ)償時間（BT），即CW = min(maxCW，CW×2)，BT = uniform(0，CW – 1) aSlotTime其中，uniform(a，，b)的含義是從a和b的均勻分布中隨機(jī)提取的數(shù)據(jù)，CW表示當(dāng)前爭用窗口大小。

3) 成功包傳輸：如果一個站已經(jīng)成功傳輸了包，則其爭用窗口大小將被還原到初始化（最小化）爭用窗口大小（minCW），并且根據(jù)CW = minCW，BT = uniform(0， CW-1) aSlotTime公式來選擇一個隨機(jī)補(bǔ)償時間值；

4) 延遲站：對于在延遲站中的站點(diǎn)而言，無論什么時候探測到一個新的忙用時間的開始（意味著在介質(zhì)中沖突或者包傳輸?shù)拈_始），該站點(diǎn)將增加其爭用窗口大小并且像如下方式選擇一個新的隨機(jī)補(bǔ)償時間：CW = min(maxCW， CW×2)， BT = uniform(0， CW-1) ×aSlotTime。

在DCR算法中，成功傳輸包的站點(diǎn)將擁有最小爭用窗口和最少補(bǔ)償時間片。因此，該站點(diǎn)將有更高概率來獲取介質(zhì)的存儲，而其他站點(diǎn)則擁有相對大的爭用窗口和相對多的補(bǔ)償時間片。在一個站點(diǎn)成功傳輸了一系列包之后，另外站點(diǎn)可能爭用到資源，隨之該新站點(diǎn)將在一段時間內(nèi)擁有更高的獲取介質(zhì)存儲概率。

4 模擬和性能估算

以下演示了對DCR算法和使用DSSS規(guī)格的IEEE802.11b MAC的模擬學(xué)習(xí)。模擬工具是OPNET。在模擬中使用的參數(shù)如表1所示（參數(shù)基于IEEE802.11b網(wǎng)絡(luò)配置）。

從圖1可發(fā)現(xiàn)：從第三秒開始，使用DCR算法的網(wǎng)絡(luò)平均吞吐量比沒有使用DCR算法的吞吐量要提高了很多。在20秒之后，使用DCR算法的平均吞吐量達(dá)到穩(wěn)定狀態(tài)。

圖1 平均吞吐量比較結(jié)果

圖2是裝載這兩種算法所需的平均時間的比較。如圖所示，在模擬開始階段，也就是在0s - 2s這個時間段，網(wǎng)絡(luò)達(dá)到了裝載高峰，接下來開始趨于穩(wěn)定。由于在DCR算法中使用了更小的最小化窗口CW和更大的最大化窗口CW，沖突產(chǎn)生概率比沒有使用DCR算法時降低了很多。網(wǎng)絡(luò)裝載速度比沒有使用DCR算法前減慢了很多。

圖3顯示延遲的模擬結(jié)果。在大約25秒以后，使用DCR算法的延時一直低于2秒，而沒有使用DCR算法的延時則大于2秒。對平均延時結(jié)果的比較得出，使用DCR算法的平均延時時間低于1.75秒，比沒有使用DCR算法的平均延時時間要短很多。

從上面所有的性能分析得出：當(dāng)站點(diǎn)數(shù)目增加到50個以上時，沒有使用DCR算法的IEEE 802.11b MAC算法的性能較差。而DCR算法將更有效的提高無線局域網(wǎng)性能。因?yàn)樵贒CR算法中，除了具有正在成功傳輸包的站點(diǎn)外的所有站點(diǎn)，無論系統(tǒng)是成功的傳輸包還是遇到?jīng)_突，站點(diǎn)都會增加其爭用窗口大小。這也就意味著，所有站點(diǎn)都能迅速獲取合適大小的爭用窗口來防止將來的沖突，因此沖突概率將被降低到非常小的一個值。同時，成功傳輸包的站點(diǎn)擁有最小窗體大小3，這個值比IEEE 802.11B MAC算法中的最小爭用窗口值31（minCW=31）小了很多。和沒有使用DCR算法的IEEE 802.11B MAC比較起來，DCR算法把浪費(fèi)的介質(zhì)閑置時間降低到了一個相對很小的值。

5 小結(jié)

在該文中，我們改進(jìn)了基于爭用的介質(zhì)存儲控制（DCR）算法。改進(jìn)的DCR算法在無線局域網(wǎng)中保留簡單的執(zhí)行運(yùn)算，從而能夠使性能得到更大提升。在改進(jìn)的DCR算法中，當(dāng)成功的包傳輸或者是包沖突時，每個站點(diǎn)改變了所有活動站點(diǎn)爭用窗口大小，用以重新分配延遲時間片并且主動避免將來可能存在的沖突。由于這個操作，當(dāng)在無線局域網(wǎng)中有很多現(xiàn)用站點(diǎn)時，每個站點(diǎn)都能夠很快地解決沖突。DCR另一個觀點(diǎn)就是，當(dāng)檢測到許多空閑站點(diǎn)時，利用比IEEE 802.11BMAC更小的爭用窗口大小并且在探測到一系列空閑時間片時可迅速減少補(bǔ)償時間片。這些改變減少了爭用時期的平均空閑站點(diǎn)數(shù)，從而使性能得到了提升。

參考文獻(xiàn)：

[1] Bharghavan V. MACAW: A Media Access Protocol for Wireless LAN's.SIGCOMM'94， London， England， Aug. 1994: 212-225.

[2] Bharghvan V. Performance evaluation of algorithms for wireless medium access. IEEE international Computer Performance and Dependability Symposium IPDS'98，1998:142-149.

[3] Bianchi G. Performance Analysis of the IEEE 802.11B Distributed Coordination Function. IEEE Journal on Selected Areas in Communications，2000，18(3):535-547.

[4] IEEE 802.11B Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications，IEEE，1997.

[5] Kim K， Shin S，Kim K.A novel MAC scheme for prioritized services in IEEE 802.11Ba wireless LAN. ATM (ICATM 2001) and High Speed Intelligent Internet Symposium， Joint 4th IEEE International Conference，2002:196-199.