一種無線Ａｄ ｈｏｃ網絡ＭＡＣ協議優化算法

（1. 西北工業大學 航海學院， 西安 710072； 2.空軍工程大學 電訊工程學院， 西安 710077； 3.西安電子科技大學 通信工程學院， 西安 710071）



摘要：

通過對IEEE 802.11DCF中最優最小競爭窗口的分析，推導出最小競爭窗口的自適應調整公式，并給出一種估計網絡競爭站點數目的算法，即SDCF。將以上兩點改進應用于無線Ad hoc網絡MAC協議。仿真結果表明，這種自適應優化算法對無線Ad hoc網絡有足夠的精度和有效性，在系統飽和情況下，優化之后的系統吞吐量、系統時延和系統丟比特率均有明顯改善。

關鍵詞：無線Ad hoc網絡； IEEE 802.11； 媒體訪問控制； 性能優化

中圖分類號：TP393文獻標志碼：A

文章編號：10013695(2009)03102603



MAC protocol optimization algorithm of wireless Ad hoc networks



LV Na 1，2， XU Demin 1， ZOU Xiangyi 3



（1.College of Marine， Northwestern Polytechnical University， Xi’an710072， China; 2. Institute of Telecommunication Engineering， Air Force Engineering University， Xi’an 710077， China; 3. School of Telecommunication Engineering， Xidian University， Xi’an 710071， China）



Abstract:

Based on the analysis of the minimum contention window of IEEE802.11 DCF， this paper introduced a formula of adjusting the minimum contention window， and proposed a simple but accurate algorithm， SDCF， to estimate the number of competing terminals. Applying these improvements to Ad hoc networks， the simulation results show that this algorithm is accurate and effective. The system throughput， delay， and bitdroprate are all improved significantly.

Key words：wireless Ad hoc networks; IEEE 802.11; MAC; performance optimization



0引言

無線Ad hoc網絡是一種不依賴于基礎設施的自組織自適應網絡，它具有組網方便快捷、不受時間空間限制等優點，因而被廣泛應用于救援、會議、戰場、探險等領域。目前無線Ad hoc網絡的測試和應用中，MAC協議普遍采用IEEE 802.11 DCF。

對IEEE 802.11性能分析模型及吞吐量等性能的分析優化一直是研究的一個熱點[1~8]。文獻[1]分析了有限負載下IEEE 802.11 DCF的吞吐量。文獻[2]建立了IEEE 802.11回退機制的馬爾可夫鏈模型，并定量分析了IEEE 802.11 DCF的飽和吞吐量。文獻[3]則在考慮傳輸錯誤的情況下給出了IEEE 802.1DCF的性能分析模型。文獻[4]給出了一種IEEE 802.11 DCF的改進機制以減少DCF的分組碰撞概率。文獻[5]則從理論上分析了當無線局域網中不同站點的數據發送速率不同時IEEE 802.11b的性能。文獻[6]給出了一種自適應的簡便算法來實現RTS/CTS門限的動態調整。文獻[7]則給出了以最小化分組傳輸時間為優化目標的RTS/CTS門限調整算法。文獻[8]針對IEEE 802.11 DCF中的RTS/CTS接入模式，得到最大化IEEE 802.11 DCF飽和吞吐量的優化方法。

本文對IEEE 802.11 DCF中被廣泛使用的基本接入模式進行分析，提出一種可根據網絡狀況進行自適應優化的IEEE 802.11 MAC協議改進算法，以提高無線Ad hoc網絡的性能，并對其進行仿真驗證和分析。

1競爭站點數目估計算法

IEEE 802.11 DCF的性能隨競爭站點個數變化較大[2]。對競爭站點數目，可根據發送幀條件碰撞概率p估計，但需要使用ARMA濾波或Kalman濾波等較復雜技術[9]。本文提出一種簡單實用的站點數目估計算法——SDCF（statisticDCF， 統計DCF）。

IEEE 802.11的MAC層數據幀中，地址域的內容取決于控制域中to DS位和from DS位的取值。但是可以看到，不論何種情況，address2的內容始終為發送數據幀站點的MAC地址，即源MAC地址。地址域內容如表1所示。

表1地址域內容

toDSfrom DSaddress 1address 2address 3address 4

00DASABSSIDN/A

01DABSSIDSAN/A

10BSSIDSADAN/A

11RATADASA

SDCF算法根據成功發送的數據幀的不同源MAC地址（address2）來估計當前網絡中競爭站點的數目。該算法的具體描述如下：

a）定義變量n記錄網絡中競爭站點的數目，其初始值為1，表明在初始狀態時網絡當中只有站點自身存在。

b）定義二維數組addr[100][10]（假設網絡中競爭站點個數不會超過100個），用來記錄站點MAC地址和與此地址相關的時間數據，初始狀態為空。其中addr[0]~addr[99]分別對應不同的MAC地址項，而addr[k][0]記錄一個數據幀的源MAC地址，addr[k][1]記錄最近一次來自這個地址的數據幀的到達時刻，addr[k][2]~addr[k][9]記錄最近八次來自這個地址的數據幀的到達時間間隔。

c）由于無線局域網在物理層使用廣播信道，每一個成功發出的數據幀均可以被單跳范圍內的所有站點接收到。當一個站點成功接收到一個數據幀后，首先對其進行源MAC地址解析，得到這個數據幀的源MAC地址address，然后將address和數組addr[100][10]當中已記錄的地址進行比較：若為新地址，則在數組中增加一個新的記錄條目，并使站點數目計數器n加1；否則，只更新數組中對應address條目的最近到達時刻和到達時間間隔。

d）掃描數組addr[100][10]。若發現有過期地址，即清除相應條目，并使站點數目計數器n減1。

利用上述算法，各站點便可以實時估計出網絡中競爭站點的個數，并記錄在計數器n中。

該算法中有一個重要參數需要仔細設置，即MAC地址生存期life_time。若life_time太小，會過早刪除相應的地址項；若life_time太大，則會使估計值跟不上實際競爭站點數的變化。假設Δt為一個站點成功發送出兩個數據幀的平均時間間隔，記錄在數組addr[100][10]中（addr[k][2] ~addr[k][9]， k=0，1， …。

n-1為來自地址addr[k][0]的最近八個數據幀的到達時間間隔）。假設r為最大重傳次數極限，根據a)計算地址addr[k][0]的生存期：

life_time=r×Δt=r×∑9i=2addr[k][i]/8;k=0，1，…，n-1(1)

2IEEE 802.11 MAC協議優化算法

IEEE 802.11 DCF協議中，當站點成功發送一個數據幀后，便立即將其競爭窗口調整為一個確定的最小值（如對應直接序列擴頻調整為32）。但這種調整競爭窗口的方法并不是最優[2，8]。

在文獻[8]中，通過對IEEE 802.11 DCF系統飽和吞吐量進行分析，給出了最優最小競爭窗口與網絡中其他參數之間的關系：

optimal_CWmin=(2nk-1)/{1+[(1-1/ke)/(1-1/nk)]×[1-2m((1-1/ke_）/(1-1/nk))m]/[1-2×(1-1/ke）/(1-1/nk)]}(2)

其中：n為網絡中競爭站點數目；m為最大退避級數；e為自然常數；k可由下式得到：

k=Tc/2σ(3)

其中：Tc為當碰撞發生時，信道被非碰撞站點檢測為忙的平均時間；σ為一個時隙的時間長度。對應確定的物理層技術，σ、m、e均為常數，對應基本接入模式[2]：

Tc=H+（E[P]/K）+DIFS+δ(4)

其中：H=PHYhdr+MAChdr為數據幀的幀頭；R為站點數據幀的發送速率；δ為傳播時延；E[P]為發生碰撞的MAC數據幀的最大幀長度的平均值。當不考慮三個以上數據幀的同時碰撞時：

E[P]=∫Pmax0(1-F(x)2)dx(5)

其中：Pmax是數據幀的最大長度；F(x)是數據幀大小所服從的分布函數。

當獲得了相應的網絡系統信息（如網絡競爭站點數目n、數據發送速率R、MAC數據幀平均大小E[P]等）后，站點可以根據式(2)動態調整其最小競爭窗口至最優值，以提高系統性能。

3算法仿真驗證與性能分析

為了驗證本文提出的MAC協議優化算法的性能，采用OPNET平臺進行仿真分析。

3.1仿真建模

仿真場景設置為一個100 m×100 m范圍內的無線Ad hoc網絡。設定初始時刻網絡中有5個競爭站點，然后每30s增加5個站點，直至120 s時刻增加為25個站點；之后從150 s時刻開始，每30 s減少5個站點，直至270 s時刻仿真結束。各站點特性設置如表2所示。其余設置采用OPNET中默認設置。

表2站點參數設置

packet size/Bytenormal(1 024， 20)

physical characteristicsdirect sequence

data rate/bps11M

transmit power /W0.005

packet receptionpower

threshold/dBm-95

rts threshold/Bytenone

short retry limit7

long retry limit4

max receive lifetime/s0.5

buffer size/bit64 000

PCF parametersdisabled

roaming capabilitydisable

各站點首先采用SDCF方法估計網絡中當前競爭站點數目，然后利用式(2)來調整其基本接入模式下的最小競爭窗口，以達到優化系統性能的目的。

3.2仿真結果及分析

IEEE 802.11 MAC協議在非飽和業務下，通常能提供較滿意的網絡性能。但是，當系統達到飽和業務狀態后，其性能急劇惡化。

圖1為SDCF算法的估計結果。可以看到，在仿真所建立的無線Ad hoc網絡中，無論業務是否飽和，SDCF算法均能基本獲得當前網絡中站點個數的準確值。當網絡中競爭站點數目減少時，非飽和業務下的估計值有相對較明顯延遲，這是因為此時網絡中成功發送數據包的時間間隔增大，SDCF中MAC地址生存期life_time值相應增大，因而其對應MAC地址過期時間也相應增大，造成當網絡中競爭站點數目減少時，估計結果不能及時跟上網絡實際狀況的變化。

圖2～4為飽和業務下優化前后網絡性能的比較曲線。可以看到，經過優化后，網絡的系統吞吐量、時延以及丟比特率，均明顯優于優化之前。這是因為在IEEE 802.11 DCF中，每一個數據包成功發送后，其站點競爭窗口馬上被調整為一個預設的最小值，這直接導致此后的數據包碰撞概率增大，系統吞吐量降低。而優化后的協議卻能夠根據網絡規模，自適應地調整其最小競爭窗口值，以達到減少碰撞、提高網絡性能的目的。

4結束語

充分利用寶貴的無線信道資源是設計無線局域網MAC協議時要著重考慮的問題，如何提高系統飽和性能一直是研究的熱點。本文給出了一種針對IEEE 802.11 DCF協議的優化改進算法，并對其進行了仿真分析和驗證。在優化算法中，各站點首先利用SDCF算法估算當前網絡中競爭站點的數目，在此基礎上，根據其數據發送速率及數據包的平均大小來調整最優最小競爭窗口，以達到優化系統性能的目的。仿真結果表明，這種優化算法能夠顯著改善IEEE 802.11 DCF的性能，系統飽和吞吐量得到明顯提高，飽和時延和飽和丟比特率得到明顯減小。

參考文獻:

[1]

ZAKI A N， ELHADIDI M T. Throughput analysis of IEEE 802.11 DCF under finite load traffic[C]//Proc of the 1st International Symposium on Communications and Signal Processing. [S.l.]: IEEE Press，2004:535538.

[2]BIANCHI G. Performance analysis of the IEEE 802.11 distributed coordination function [J]. IEEE Journal of Selected Areas in Telecommunications， Wireless Series， 2000，18(3):535547.

[3]CHATZIMISIOS P， BOUCOUVALAS A C， VITSAS V. Performance analysis of IEEE 802.11 DCF in presence of transmission errors[C]//Proc of IEEE International Conference on Communications. [S.l.]:IEEE Press， 2004:38543858.

[4]WANG Chonggang， LI Bo， LI Lemin. A new collision resolution mechanism to enhance the performance of IEEE 802.11 DCF [J]. IEEE Trans on Vehicular Technology， 2004， 53(4):12351246.

[5]MARTIN H， FRANK R， GILLES B S， et al. Performance anomaly of 802.11b[C]//Proc of IEEE INFOCOM 2003. [S.l.]:IEEE Press， 2003:836843.

[6]趙力強，樊昌信. ADCF：IEEE 802.11 DCF協議的自適應簡便算法[J]. 電路與系統學報， 2003， 8(4):100102.

[7]劉軍，郭偉，黃飛，等. 無線局域網中一種自適應RTS門限調整算法[J]. 計算機學報， 2007， 30(4):547554.

[8]李云，陳前斌，隆克平，等. 通過自適應調整最小競爭窗口最大化IEEE 802.11 DCF的飽和吞吐量[J].電子與信息學報，2006， 28(10):19301934.

[9]BIANCHI G， TINNIRELLO L. Kalman filter estimation of the number of competing terminals in an IEEE 802.11 network[C]//Proc of IEEE INFOCOM. 2003:844852.