張應(yīng)征, 朱 燕

?

基于DCF退避機制的算法改進及其應(yīng)用

張應(yīng)征*1, 朱 燕2

(1. 湖南工程職業(yè)技術(shù)學(xué)院 信息工程系, 湖南 長沙, 410004; 2. 華中科技大學(xué) 計算機學(xué)院, 湖北 武漢, 430074)

無線局域網(wǎng)絡(luò)技術(shù)中采用的基本接入方式是分布式控制DCF方法, 但它需要解決2個問題: 一是由多個節(jié)點同時發(fā)送數(shù)據(jù)幀而出現(xiàn)碰撞的情況; 二是隨著網(wǎng)絡(luò)總業(yè)務(wù)量的增多或出現(xiàn)突發(fā)狀況時, 急劇增大的碰撞率情況. 為此, 采用改進的退避機制的算法, 以減少節(jié)點接入網(wǎng)絡(luò)時沖突的方法, 提高MAC協(xié)議的整體性能, 并通過建立仿真子網(wǎng)模型予以應(yīng)用測試. 結(jié)果表明, 這種方法提高了網(wǎng)絡(luò)吞吐量, 解決了網(wǎng)絡(luò)擁堵問題, 提高了通信效率.

退避算法; 無線網(wǎng)絡(luò); 仿真建模

無線局域網(wǎng)絡(luò)技術(shù)起源于二戰(zhàn)時美軍研發(fā)的無線傳輸技術(shù), 后經(jīng)過科研人員對其封包式技術(shù)的改進,由IEEE802工作組在1997年6月發(fā)布的802.11協(xié)議成為無線局域網(wǎng)的第一代協(xié)議, 在1999年又發(fā)布了補充的802.11b協(xié)議, 隨后又推出了802.11a、802.11g等, 最后形成一系列的802.11x協(xié)議, 成為無線局域網(wǎng)的標準[1]. 而802.11x系列協(xié)議標準的重點就是MAC(Media Access Control)層的協(xié)議, 其功能主要包括控制無線介質(zhì)訪問、提供有效的數(shù)據(jù)通信. 而作為IEEE 802.11 MAC層的DCF (Distributed Coordination Function)——分布式協(xié)調(diào)功能, 則用來提供異步的數(shù)據(jù)服務(wù), 各個終端節(jié)點通過競爭的方式來使用信道, 主要包括載波監(jiān)聽機制、隨機退避機制和幀間隔方法, 是一種無線網(wǎng)絡(luò)中節(jié)點共享無線信道來進行傳輸數(shù)據(jù)的方式, 但這種方法需要解決多個節(jié)點同時發(fā)送數(shù)據(jù)幀而出現(xiàn)的碰撞情況.實踐數(shù)據(jù)表明, 引入改進的二進制退避機制, 可使得數(shù)據(jù)幀發(fā)生碰撞幾率顯著減少, 具有提高通信效率的功能.

1 二進制指數(shù)退避算法

對IEEE 802.11 MAC層的DCF中的退避機制研究, 其核心是研究在DCF中采用的退避算法, 標準退避算法是二進制指數(shù)退避(Binary Exponential Backoff, BEB), 如下:

BEB算法在某些情況下解決了信道爭用問題, 但是也存在2個缺點:

(a) 前一次成功發(fā)送的節(jié)點值立刻回到初始大小, 而其他不成功的節(jié)點值較大, 因此在某一小段時間內(nèi)對于剛成功發(fā)送的節(jié)點再次競爭信道的概率大大增加, 從而造成不公平性現(xiàn)象, 并導(dǎo)致時延大范圍抖動.

(b) 當網(wǎng)絡(luò)節(jié)點數(shù)較多, 負載比較嚴重時, 節(jié)點每次成功發(fā)送后都將重置為min, 可能會引起更多的數(shù)據(jù)沖突, 不能正確反映當前信道競爭使用情況, 由于數(shù)據(jù)沖突和退避機制也要浪費時間, 從而造成系統(tǒng)的吞吐量急劇下降.

因此, 在BEB中節(jié)點的隨機時間窗口設(shè)置就成為一個很重要的問題: 隨機時間過小則沖突比較嚴重, 而過大則浪費嚴重.

2 退避算法的改進

BEB算法適合于負載比較輕的環(huán)境, 對于負載過重性能就會急劇下降, 為了能讓節(jié)點更快地達到公平的競爭狀態(tài), 提高整個網(wǎng)絡(luò)的性能, 在此基礎(chǔ)上, 需要進行退避算法的改進[2]. 改進的退避算法描述如圖1所示. 引入一個中間參數(shù)mid(min＜mid＜max), 作為區(qū)分節(jié)點競爭程度的閥值. 同時結(jié)合其他退避算法的取值, 考慮將初始競爭窗口設(shè)置min為2,max為1 024,min為32.

(a) 初始時網(wǎng)絡(luò)負載較輕, 其競爭窗口≤mid時, 若發(fā)生沖突數(shù)據(jù)包發(fā)送失敗, 則競爭窗口和BEB一樣增長為原來的2倍; 若數(shù)據(jù)包發(fā)送成功, 競爭窗口線性減少, 在原窗口基礎(chǔ)上減1, 避免競爭窗口下降過快引起更多的沖突.

(b) 當網(wǎng)絡(luò)負載較多, 其競爭窗口＞mid時, 若數(shù)據(jù)包發(fā)送失敗, 則競爭窗口值和BEB一樣增長為原來的2倍; 當數(shù)據(jù)包發(fā)送成功后, 競爭窗口值不直接降到最小min, 而是在原窗口基礎(chǔ)上除以4, 讓競爭窗口快速降到mid附近, 防止過度空閑而使得信道利用率下降.

圖1 改進的退避算法描述圖

改進的退避算法如下:

3 仿真建模及分析

3.1 模型的建立

利用網(wǎng)絡(luò)仿真軟件對其進行建模, OPNET網(wǎng)絡(luò)仿真軟件是目前用于網(wǎng)絡(luò)仿真開發(fā)和應(yīng)用先進的平臺之一, OPNET仿真模型劃分為3層: 網(wǎng)絡(luò), 節(jié)點和進程層. 網(wǎng)絡(luò)模型是最頂層模型, 由網(wǎng)絡(luò)節(jié)點和通信鏈路組成, 可以反映網(wǎng)絡(luò)拓撲結(jié)構(gòu)的特點; 節(jié)點模型是由協(xié)議模型構(gòu)造和連接起來, 可以反映設(shè)備的特性, 每1個模型對應(yīng)1個或多個進程模型; 進程模型通過C語言編程的有限狀態(tài)機來進行描述, 可以反映協(xié)議如何實現(xiàn)其具體功能. 建立1個無線子網(wǎng)模型, 包括1個AP和使用wlan_station_adv (Mobile Node)作為接入點的若干個無線移動站點[3].

(a) 為整個網(wǎng)絡(luò)配置應(yīng)用模塊Application Config: 添加FTP、HTTP、Database. 為了提高仿真速度, Mix設(shè)置為50%, 業(yè)務(wù)流一半為精確發(fā)送, 一半為其他交易量. 業(yè)務(wù)交易間隔時間為exponential函數(shù)隨機取樣.

(b) Profile Config: 業(yè)務(wù)配置見圖2, 描述1類用戶群所涉及的應(yīng)用. 業(yè)務(wù)開始時間(Start time)為100 s; 主詢加載時間(duration)為仿真結(jié)束終止; 業(yè)務(wù)主詢重復(fù)性(Repeatitions)為重復(fù).

圖2 業(yè)務(wù)主詢問配置

(c) 配置服務(wù)器支持應(yīng)用, 確定每臺服務(wù)器具體支持的業(yè)務(wù).

(d) 配置客戶端業(yè)務(wù)主詢, 因為是端對端的業(yè)務(wù), 因此, 在客戶端中同樣需要設(shè)定業(yè)務(wù)主詢, 其設(shè)置同業(yè)務(wù)主詢配置一樣.

3.2 節(jié)點模型

無線節(jié)點模型采用wlan_station_adv(mob)[4], 側(cè)重分析無線網(wǎng)絡(luò)的性能指標, 特別是MAC(Media Access Control)層協(xié)議, 其中source模塊產(chǎn)生數(shù)據(jù)包. wlan_mac_intf模塊為高層和MAC層的接口. wire_lan_mac模塊完成各種MAC多址接入和傳輸, 實現(xiàn)無線介質(zhì)訪問控制協(xié)議的核心模塊, 具體由進程模型來實現(xiàn). sink模塊處理接收的數(shù)據(jù)包, 釋放內(nèi)存. 同時進行平均時延和吞吐量方便的統(tǒng)計工作. wlan_port_tx0模塊負責(zé)將數(shù)據(jù)幀發(fā)送到信道上. wlan_port_rx0模塊用于檢測信道狀態(tài), 獲取數(shù)據(jù)幀傳遞給MAC模塊來處理.

表1 仿真實驗參數(shù)

3.3 仿真分析

利用建立好的模型, 對無線子網(wǎng)進行仿真分析. 設(shè)置移動節(jié)點的數(shù)目, 使用ON-OFF模式產(chǎn)生業(yè)務(wù). 在不同的節(jié)點數(shù)目下分別采用BEB算法的基本DCF協(xié)議和改進的退避算法的基本DCF協(xié)議[5]. 分析和比較2者的吞吐量和傳輸時延性能. 仿真參數(shù)如表1所示, 程序中的cw等同于文中的.

4 改進的退避算法的關(guān)鍵代碼

if( backoff_slots==BACKOFF_SLOTS_UNSET)

{ if(retry_count==0||wlan_flags->perform_cw==OPC_BOOLINT_ENABLED)

if(cw<=cw_mid)

{ max_backoff= max_backoff-1;

if(max_backoff

{ max_backoff= cw_min;

}

}

else

{ max_backoff= max_backoff/4;

}

}

}

else

{ max_backoff=2* max_backoff;

if(max_backoff>cw_max)

{

max_backoff= cw_max;

}

backoff_slots=floor(op_dist_uniform(max_backoff+1));

}

5 結(jié)果分析

根據(jù)對模型的數(shù)據(jù)測試應(yīng)用, 得到結(jié)果, 圖3和圖4分別顯示了在移動節(jié)點數(shù)分別為10、20、30、40、50、60、100的情況下, BEB算法和改進的算法在飽和數(shù)據(jù)量環(huán)境下的吞吐量和傳輸延時曲線, 對2種情況進行公平性比較, 見圖5.

圖3 吞吐量比較

圖4 網(wǎng)絡(luò)延時比較

圖5 2種情況的公平性比較

從圖3和圖4可以看出, 改進的算法在吞吐量和網(wǎng)絡(luò)延遲都要優(yōu)于BEB算法. 當無線節(jié)點從10個增大到100個時, BEB算法中隨著負載的增加吞吐量急劇下降, 吞吐量從4.2 Mb/s下降到2.5 Mb/s, 下降了40%; 改進后的退避算法從4.3 Mb/s下降到3.25 Mb/s, 性能下降了24.5%, 在一定程度上降低了沖突概率, 減少了數(shù)據(jù)的碰撞, 同時能有效地利用信道, 提高信道利用率. 從圖5可以看出改進的算法其公平性也要優(yōu)于BEB算法, 由于改進的算法其競爭窗口的變化依照不同的競爭階段分別進行乘性和線性遞減, 能以更加合理的概率接入信道, 提高了數(shù)據(jù)流之間的公平性. 因此改進后的算法比BEB算法具有更好的適應(yīng)性.

6 結(jié)束語

文章通過引入二進制退避算法機制, 并對其進行改進, 應(yīng)用到無線子網(wǎng)模型中, 顯著減少了由多個節(jié)點同時發(fā)送數(shù)據(jù)幀造成的沖突, 具有重要的實際意義和參考價值.

[1] 陳偉, 張劍, 黃秋元. IEEE802.11標準MAC性能分析和一種改進方法[J]. 通信系統(tǒng)與網(wǎng)絡(luò)技術(shù), 2006, 4(3): 37—41.

[2] 王秀芳, 魏宇恒, 王洋. IEEE802.11 DCF退避機制的一種改進方法[J]. 長江大學(xué)學(xué)報: 自然科學(xué)版, 2008, 12(5): 67—70.

[3] 朱艷. 婁底職業(yè)技術(shù)學(xué)院無線校園網(wǎng)優(yōu)化設(shè)計[D]. 武漢: 華中科技大學(xué), 2010: 11.

[4] Papanikos I, Logothetis M. A study on dynamic load balance for IEEE 802.11b wireless LAN[A].Proc of COMCON[C].Los Angeles: CA:ETATS-UNIS, 2001: 83—89.

[5] 郭世澤. 無線局域網(wǎng)[M]. 北京: 人民郵電出版社, 2003: 65—68.

Improved algorithm based on DCF backoff mechanism and its application research

ZHANG Ying-zheng1, ZHU Yan2

(1. Department of Information Engineering, Hunan Engineering Polytechnic, Changsha 410004, China; 2. Computer College, Huazhong University of Science and Technology, Wuhan 430074, China)

Wireless local area network technology used in distributed control is the basic access method of DCF , but it need to solve the two problems: one is made of many nodes at the same time send data frames and appear the situation of the collision, Second is along with the increase of total volume or network emergencies, sharp increase of collision rate. Therefore, this article studies the backoff mechanism of improved algorithm, in order to reduce the conflict when the node access network, the method of improving the performance of the MAC protocol, and by establishing the simulation model of subnet and application, the results show that this method improve the network throughput, solve the network congestion problem, improve the efficiency of communication.

retreats algorithm; wireless network; simulation modeling

10.3969/j.issn.1672-6146.2013.01.012

TP 393.1

1672-6146(2013)01-0046-04

email: 406851863@qq.com.

2012-12-03

湖南工程職業(yè)技術(shù)學(xué)院( GCZY11KTZ12)

(責(zé)任編校:劉剛毅)