陳堅(jiān)剛

（浙江工商職業(yè)技術(shù)學(xué)院，浙江寧波315012）

IEEE802.11b的DCF退避算法實(shí)現(xiàn)技術(shù)探究

陳堅(jiān)剛

（浙江工商職業(yè)技術(shù)學(xué)院，浙江寧波315012）

本文研究了無(wú)線局域網(wǎng)IEEE 802.11b的MAC層基于隨機(jī)競(jìng)爭(zhēng)的分布式協(xié)調(diào)功能（DCF：Distributed Coordination Funct0ion）的基本信道訪問(wèn)方式的實(shí)現(xiàn)技術(shù)。DCF主要包括載波偵聽(tīng)機(jī)制、隨機(jī)退避機(jī)制、幀優(yōu)先級(jí)機(jī)制等。它定義了兩種工作方式，一種是基本訪問(wèn)方式CSMA/CA，基于物理信道的載波偵聽(tīng)；另外一種是基于RTS/CTS虛擬載波偵聽(tīng)，這種方式在CSMA/CA的基礎(chǔ)上增加兩個(gè)長(zhǎng)度特別小的數(shù)據(jù)包RTS和CTS來(lái)克服“隱藏終端”問(wèn)題?？梢酝ㄟ^(guò)對(duì)這兩種載波偵聽(tīng)機(jī)制的研究，并利用SDL圖和狀態(tài)轉(zhuǎn)移圖，完成退避算法的軟件實(shí)現(xiàn)。

退避算法；無(wú)線局域網(wǎng)；媒體接入控制（MAC）；分布式協(xié)調(diào)功能（DCF）

隨著無(wú)線局域網(wǎng)技術(shù)的日趨成熟，國(guó)內(nèi)目前無(wú)線局域網(wǎng)的應(yīng)用也比較多。無(wú)線網(wǎng)絡(luò)在賦予用戶通信自由的同時(shí)也帶來(lái)一些弊端，如設(shè)備間的信道爭(zhēng)用，造成傳輸碰撞，影響網(wǎng)絡(luò)的吞吐率，特別是當(dāng)兩個(gè)設(shè)備利用一個(gè)中心接入點(diǎn)進(jìn)行連接，這兩個(gè)設(shè)備都能夠“聽(tīng)”到中心接入點(diǎn)的存在，而互相之間則可能由于障礙或者距離原因無(wú)法感知到對(duì)方的存在的“隱含終端”問(wèn)題。IEEE 802.11b的MAC層“分布式訪問(wèn)方式”（DCF）實(shí)現(xiàn)技術(shù)將很好的解決這些弊端，確保設(shè)備之間傳輸?shù)乃俾屎蛿?shù)據(jù)的可靠性，提高吞吐率，實(shí)現(xiàn)多用戶無(wú)線媒介共享資源等問(wèn)題。DCF的實(shí)現(xiàn)技術(shù)包括載波偵聽(tīng)、退避機(jī)制和優(yōu)先級(jí)機(jī)制。本文選取退避算法作為研究對(duì)象，探究了其軟件實(shí)現(xiàn)過(guò)程。

1 退避算法

1.1 概述

常用退避算法有三種：非堅(jiān)持，1-堅(jiān)持，p堅(jiān)持。非堅(jiān)持算法采用隨機(jī)的重發(fā)延遲時(shí)間可以減少?zèng)_突發(fā)生的可能性，可是這樣處理會(huì)降低媒介利用率，1-堅(jiān)持型算法雖然能夠避免了媒介利用率的損失，但是假如有兩個(gè)或兩個(gè)以上的站點(diǎn)有數(shù)據(jù)發(fā)送，沖突就不可避免。而p堅(jiān)持既能像非堅(jiān)持算法那樣減少?zèng)_突，又能像1-堅(jiān)持算法那樣減少媒介空閑時(shí)間的，然而p值較難選擇，最終實(shí)現(xiàn)比較困難，由于無(wú)線通信的特性，IEEE 802.11工作組選擇的是非堅(jiān)持退避算法，減少?zèng)_突發(fā)生的可能性，也既是CSMA/ CA的目標(biāo)所在。

1.2 退避原理流程圖

站點(diǎn)發(fā)送協(xié)調(diào)子模塊在發(fā)送數(shù)據(jù)幀MPDU前必須進(jìn)入退避（Backoff_Procedure）子模塊進(jìn)行退避過(guò)程，而且數(shù)據(jù)幀MPDU發(fā)送失敗時(shí)，也必須進(jìn)行退避過(guò)程，退避過(guò)程是為了減少信道發(fā)生沖突的概率，提高網(wǎng)絡(luò)性能。實(shí)現(xiàn)流程圖如圖1所示。

軟件實(shí)現(xiàn)的關(guān)鍵參數(shù)是退避窗口CW的選取，退避窗口CW數(shù)值在最大值CWmax與最小值CWmin之間，并且與發(fā)送失敗次數(shù)N有關(guān)。在確定了CW的值以后，就可以在[0，CW]之間產(chǎn)生一個(gè)隨機(jī)數(shù)來(lái)初始化退避計(jì)數(shù)器的值，具體計(jì)算關(guān)系式如下：

1.3 退避算法模塊的SDL圖分析

退避規(guī)程是進(jìn)行后退回避的，進(jìn)程初始化后，對(duì)遠(yuǎn)程變量mBkIp賦值為假，表示后退回避不在進(jìn)程中，狀態(tài)變遷為No_Backoff，當(dāng)Backoff消息到達(dá)時(shí)，提取出cnt參數(shù)，這是后退回避的時(shí)間值，狀態(tài)變遷為Channel_Busy。如果idle消息到達(dá)，狀態(tài)變遷為Channel_Idle，只有在這個(gè)狀態(tài)時(shí)，每次到達(dá)一個(gè)Slot消息，后退回避時(shí)槽數(shù)減一，直到后退回避時(shí)槽數(shù)減小到為0，發(fā)送BkDone消息給TX_Coordination進(jìn)程，該消息的參數(shù)bstate=-2，表示可以發(fā)送TxRequest消息到Transmission模塊。Backoff_Procedure模塊SDL圖如圖2、3所示。

1.4 退避算法模塊狀態(tài)轉(zhuǎn)移圖

根據(jù)Backoff_Procedure模塊的SDL圖，我們可以統(tǒng)計(jì)出Backoff_Procedure模塊中包含的狀態(tài)有：No_Backoff、Channel_Busy、Channel_Idle三個(gè)狀態(tài)，狀態(tài)之間的轉(zhuǎn)移圖如圖4所示。

2 實(shí)現(xiàn)過(guò)程

2.1 模塊中信號(hào)和狀態(tài)的定義

在模塊的SDL圖中，信號(hào)和狀態(tài)是模塊流程中最主要的兩大元素。一個(gè)系統(tǒng)中各模塊之間的交互是通過(guò)信號(hào)的方式來(lái)完成的。模塊之間通過(guò)交互信號(hào)來(lái)協(xié)調(diào)工作，模塊中的進(jìn)程一般處于是等待信號(hào)的狀態(tài)。當(dāng)一個(gè)模塊接收到其他模塊傳來(lái)的信號(hào)，如果這個(gè)信號(hào)是一個(gè)有效信號(hào)，則對(duì)該信號(hào)進(jìn)行處理，處理完成狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)等待信號(hào)的輸入；如果接收到的是無(wú)效信號(hào)，則丟棄。模塊之間實(shí)現(xiàn)信號(hào)的傳遞。

2.1.1 信號(hào)定義。在程序設(shè)計(jì)中，我們采用結(jié)構(gòu)體的表達(dá)方式對(duì)各個(gè)模塊之間通信所使用的信號(hào)進(jìn)行定義。在退避模塊中的信號(hào)有：初始化信號(hào)ResetMAC，從發(fā)送協(xié)調(diào)模塊（Tx_Coordination_Sta）發(fā)送的退避信號(hào)Backoff（cw，cnt），發(fā)送到Tx_Coordination_Sta模塊的帶有退避是否結(jié)束信息的信號(hào)BkDone，以及由Reception模塊發(fā)送的信道狀態(tài)信號(hào)Busy、Idle和Slot。

結(jié)構(gòu)體定義如下：

2.1.2 狀態(tài)定義。我們采用枚舉方式對(duì)模塊中的狀態(tài)進(jìn)行定義。

在Backoff_Proucedure模塊中的狀態(tài)有：無(wú)退避進(jìn)程狀態(tài)No_Backoff，信道忙狀態(tài)Channel_Busy，信道空閑狀態(tài)Channel_Idle。

枚舉方式定義如下：

2.2 模塊狀態(tài)轉(zhuǎn)移功能的實(shí)現(xiàn)

在程序設(shè)計(jì)過(guò)程中，為了能對(duì)輸入一個(gè)信號(hào)后狀態(tài)轉(zhuǎn)移至其他狀態(tài)這個(gè)過(guò)程有更直觀地認(rèn)識(shí)，我們首先根據(jù)SDL圖列出一個(gè)狀態(tài)轉(zhuǎn)移的表格。表1就是Backoff_Proucedure模塊的狀態(tài)轉(zhuǎn)移表。

表1

轉(zhuǎn)移表中第一行為模塊中的狀態(tài)。最左邊一列為輸入的信號(hào)，右邊為該信號(hào)進(jìn)入相應(yīng)的狀態(tài)后，模塊根據(jù)這個(gè)信號(hào)的功能進(jìn)行相應(yīng)的進(jìn)程處理，最后轉(zhuǎn)到另一個(gè)狀態(tài)。這個(gè)處理過(guò)程我們用一個(gè)函數(shù)來(lái)定義，這些函數(shù)實(shí)際上就是模塊中進(jìn)程實(shí)現(xiàn)的功能塊。

通過(guò)定義這些函數(shù)，我們?cè)趫?zhí)行過(guò)程中，當(dāng)輸入一個(gè)信號(hào)時(shí)，如果這個(gè)信號(hào)對(duì)當(dāng)前狀態(tài)有效，則調(diào)用相應(yīng)函數(shù)，實(shí)現(xiàn)信號(hào)的功能，并轉(zhuǎn)到下一個(gè)狀態(tài)；如果這個(gè)信號(hào)對(duì)當(dāng)前狀態(tài)無(wú)效，則丟棄并返回被丟棄的提示信息。

程序執(zhí)行結(jié)果如圖5所示。

2.3 退避算法核心代碼

3 結(jié)語(yǔ)

本文探討了IEEE802.11b規(guī)定的MAC層DCF中退避算法的實(shí)現(xiàn)過(guò)程，按照從系統(tǒng)到模塊到進(jìn)程再到函數(shù)這個(gè)線路可以繼續(xù)實(shí)現(xiàn)DCF中的載波偵聽(tīng)機(jī)制。并可以不斷改進(jìn)算法，提高通信效率?？梢灶A(yù)見(jiàn)，隨著時(shí)間的發(fā)展，IEEE802.11技術(shù)標(biāo)準(zhǔn)將會(huì)在無(wú)線局域網(wǎng)技術(shù)中發(fā)揮巨大的作用。

[1]金純，陳林星，楊吉云.IEEE802.11無(wú)線局域網(wǎng)[M].北京：電子工業(yè)出版社，2003.

[2]黎連業(yè)，郭春芳，向東明.無(wú)線網(wǎng)絡(luò)及其應(yīng)用技術(shù)[M].北京：清華大學(xué)出版社，2004.

[3]宋茂強(qiáng)等.通信軟件設(shè)計(jì)基礎(chǔ)[M].北京：北京郵電大學(xué)出版社，2001.

[4]Mark Ciampa.無(wú)線局域網(wǎng)設(shè)計(jì)與實(shí)現(xiàn)[M].王順滿，吳長(zhǎng)奇，張岌譯.北京：科學(xué)出版社，2003.

［責(zé)任編輯：熊榮生］

An Inquiry into the Random Escape Mechanism of DCF in IEEE802.11b

CHEN Jian-gang
（Zhejiang Business Technology Institute，Ningbo 315012，China）

This paper focuses on the technology of basic channel access of the random competitive DCF（Distributed Coordination Function）on MAC layer of WLAN IEEE802.11b.DCF mainly includes carrier monitoring mechanism，random escape mechanism and frame-level priority mechanism.It defines two access modes.One is the basic access mode called CSMA/CA，which is based on carrier monitoring mechanism of physical communication channel.The other mode is virtual carrier monitoring on the base of RTS/CTS.This mode adds two small-length data packages“RTS”and“CTS”to overcome the“Hidden Terminal”problem other than the base mode CSMA/CA.After my research on the two carrier monitoring mechanisms，I finished the software reality of random escape mechanism by using SDL and State-transfer diagrams.

random escape mechanism；Wireless Local Area Network（WLAN）；Media Access Control（MAC）；Distributed Coordination Function（DCF）

TP393.1文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1671-9565（2010）03-036-04

2010-06-20

陳堅(jiān)剛（1982-），男，浙江寧波人，浙江工商職業(yè)技術(shù)學(xué)院教師，主要從事模式識(shí)別方面研究。