張應征, 朱 燕

?

基于DCF退避機制的算法改進及其應用

張應征*1, 朱 燕2

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

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

退避算法; 無線網絡; 仿真建模

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

1 二進制指數退避算法

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

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

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

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

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

2 退避算法的改進

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

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

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

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

改進的退避算法如下:

3 仿真建模及分析

3.1 模型的建立

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

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

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

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

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

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

3.2 節(jié)點模型

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

表1 仿真實驗參數

3.3 仿真分析

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

4 改進的退避算法的關鍵代碼

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 結果分析

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

圖3 吞吐量比較

圖4 網絡延時比較

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

從圖3和圖4可以看出, 改進的算法在吞吐量和網絡延遲都要優(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%, 在一定程度上降低了沖突概率, 減少了數據的碰撞, 同時能有效地利用信道, 提高信道利用率. 從圖5可以看出改進的算法其公平性也要優(yōu)于BEB算法, 由于改進的算法其競爭窗口的變化依照不同的競爭階段分別進行乘性和線性遞減, 能以更加合理的概率接入信道, 提高了數據流之間的公平性. 因此改進后的算法比BEB算法具有更好的適應性.

6 結束語

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

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

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

[3] 朱艷. 婁底職業(yè)技術學院無線校園網優(yōu)化設計[D]. 武漢: 華中科技大學, 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] 郭世澤. 無線局域網[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è)技術學院( GCZY11KTZ12)

(責任編校:劉剛毅)