一種基于流公平性的退避算法

徐立強，徐 祎，王 銳

（合肥電子工程學院，安徽 合肥 230037）

0 引言

IEEE 802.11DCF是為無線局域網WLAN（Wireless LAN）制定的，但目前的無線自組織網絡中大都將其直接作為MAC接入規范，從而帶來公平性問題。公平性問題研究一般分為基于節點的公平性和基于流的公平性[1-2]兩種，最終都歸結為如何在MAC協議中確保每個節點或流的接入機率[3]相等。由于數據類型的多元化，支持服務質量（QoS）的介質訪問協議（MediaAccess Control，MAC）是未來網絡的發展趨勢，因此基于流的公平性能夠更好地根據數據流類型來控制數據流的接入能力[4-8]。本文通過建模，分析了MAC機制中對流公平性的影響因素及解決流不公平問題的方法，提出一種基于流公平性的退避算法BFF（Back-off based on Flow Fairness），通過調整退避窗口最小值以減少傳輸失敗發生的概率，同時兼顧到網絡傳輸時延，改善網絡中由于隱藏終端引起的流不公平問題，最后通過網絡仿真驗證了其合理性。

1 IEEE 802.11 DCF公平性問題分析

無線網絡中的隱蔽終端問題會在競爭數據流間產生嚴重的不公平性。不失一般性地，本文針對如圖1所示的一個典型網絡場景進行仿真分析實驗，針對節點使用共享信道帶寬的公平性問題進行建模，討論Rmax次嘗試傳輸失敗（RET事件）發生概率的影響因素[9-12]。節點3和節點1相對于節點2而言互為隱藏終端。節點1和節點2之間、節點3和節點4之間均為構建在UDP傳輸協議上的CBR數據流，均由Pareto分布流量產生器產生，分別用 cbr12和 cbr34來表示。

圖1 Z字型網絡拓撲圖

設Y[n]表示節點1連續碰撞后重發n個RTS幀的起始時刻的離散時間隨機過程，T[i]表示節點3連續成功發送數據幀情況下發送第i個RTS幀的起始時刻的離散時間隨機過程。有：

其中，節點1設定RTS定時器的超時門限tout=tRTS+tCTS+tSIFS，節點3到節點4一次成功傳遞數據所耗時間tb=tRTS+tCTS+3tSIFS+tD+tA。Rmax為 RTS幀的最大重傳次數，W0為節點3連續兩次成功發送數據幀之間的隨機退避間隔（在具體計算中為了分析方便，將其窗口尺寸設為w，w為最小競爭窗口），Wj為節點 1第 j次 RTS重傳時的隨機退避間隔，最大退避階數 m=log2（CWmax/w），CWmax為最大競爭窗口，tRTS、tCTS、tSIFS、tD、tA分別為 RTS、CTS、SIFS、Data以及ACK幀的傳輸時間。

1.1 節點1和節點2握手成功的充要條件

節點1第n次發RTS幀才能握手成功的充要條件是此次發送在節點3到節點4的第i-1次成功傳送結束前tRTS時刻之后開始，而在節點3的第i次發送RTS幀到達節點2的前tSIFS時刻之前結束。

其中，N1為節點3重傳次數的下界，此時節點1連續兩次成功傳輸之間的退避間隔在最小競爭窗口內隨機選取，一次成功傳輸所耗時間最多包括tb和w-1；而N2為節點3重傳次數的上界，此時節點1的退避間隔為0，即立即傳輸，一次成功傳輸所耗時間最少為tb。

1.2 RET事件出現概率計算

通過對Z字型網絡中節點1至節點2的數據流被節點3至節點4數據流扼制的過程建模，可以看出節點1成功發送數據的充要條件是發送RTS幀的時刻Y[n]必須滿足式（3）。設第n次嘗試，節點1發送 RTS幀成功的概率為pn：

當Rmax給定時，節點1嘗試Rmax次發送RTS幀失敗（RET事件）的概率 pRET：

n=1時，節點2收到節點3發出的RTS，根據節點 3傳輸該數據幀的時間啟動NAV計數器，節點2在計數器結束之前不偵聽信道。而節點1在節點3發完該數據幀前發送第一個RTS幀。所以節點2收不到節點1發送的 RTS 幀，故 p1=0。 n＞1 時，將式（1）、式（2）代入式（4），并令對應的取 值 范 圍 為 εXn=[0，（2n-2）w-n+1]，εYn=[0，（2n-1）wn]，εZi=[0，（i-1）w]，εUn=[0，（（n-m+1）2m-2）w-n+1]，εVn=[0，（（n-m+1）2m-1）w-n]，離散事件 Xn，Yn，Zi，Un，Vn相應的分布律為 pkx，pky，prz，pku，pkv，可得 pn：

已知連續碰撞造成的隨機退避間隔在對應退避窗口隨機選擇的事件相互之間是獨立的[13]，于是可以利用獨立離散隨機變量的母函數定義及性質，得到離散隨機變量 Xn、Yn、Zi、Un和 Vn的分布律 pkx、pky、prz、pku和 pkv。

1.3 RET事件發生概率分析

從1.2節可以看出，連續 Rmax嘗試傳輸失敗（RET事件）的概率與pn和Rmax有關，而pn與pkx、pky、prz、pku和pkv，以及它們的求和邊界有關，進而可以發現pkx、pky、prz、pku和pkv與 tRTS、tCTS、tSIFS、tDIFS、tA、tD以及最小競爭窗口尺寸w有關。 由此 pRET可以看成與Rmax以及 tRTS、tCTS、tSIFS、tDIFS、tA、tD、最小競爭窗口大小w有關，其中除Rmax、tD和 w以外的參數都被802.11物理層規范所約束。又tD由MAC數據幀長決定，Rmax的變化對網絡的影響非常大，不僅影響MAC層傳輸時延，還會浪費節點能量，因而可以通過調整w達到pRET減小的效果。

當 w 增大，prz、pkx、pky跟著增大。 同時在式（6）中 pkx的獨立離散變量概率求和范圍 k＜（i-1）tb+r+tRTS-tSIFS-tn比 pky的求和范圍 k＜（i-1）tb+r-tRTS-tn大，由此 2≤n≤m時，第n次節點1嘗試發送RTS幀成功的概率pn隨w增大。同理，m≤n≤Rmax時pn也會增大。由此，w增大 pRET減小，但同時會增加重傳MAC幀的時延，因此需要兼顧pRET和MAC幀時延。

數值仿真計算得到的數據與仿真數據能夠較好地吻合，如圖2所示。可以看出，pRET對于CWmin的變化非常敏感。

2 基于流公平性的退避算法

2.1 算法的重要參數指標

（1）吞吐量變化率

圖2 pRET隨著CWmin變化情況

BFF算法需要一個參數指標來判斷是否出現了造成數據流接收節點吞吐量急速下降的不公平現象。定義一個新的參數——吞吐量變化率Th_Rate，表示節點受流不公平影響時其吞吐量下降的程度。

ThroughputT表示第T個周期內的當前節點吞吐量，ThroughputT+1表示第T+1個周期內的當前節點吞吐量。Th_Rate∈（-∞，0]，該點吞吐量增大；Th_Rate∈（0，啟動門限），該點吞吐量適當減小；Th_Rate∈[啟動門限，1]，該點吞吐量急劇減小。

（2）流不公平度

定義一個新參數——流不公平度fs作為流不公平的衡量標準。

其中，ThroughputT為當前考察數據流對應的接收節點吞吐量，Throughputaver指可偵聽范圍內節點接收的數據流吞吐量平均值。fs是該數據流吞吐量相對于數據流吞吐量平均值的差異，能夠有效地反映流公平性的情況，fs=0時為絕對公平。

2.2 RTS幀結構

為了獲得可偵聽范圍內其他節點的情況，BFF算法修改了初始的請求發送 （Request To Send，RTS）幀結構，在其中攜帶1 B的吞吐量信息（如圖3所示）。

圖3 RTS數據包結構

2.3 公平性狀況監測表

獲得可偵聽范圍內數據流的吞吐量后，每個節點維護一張公平狀況監測表（Fairness State Detection Table，FSDT），如表1所示，用來儲存數據流的 ID和可偵聽節點對應數據流的吞吐量。在初始化FSDT表時，獲得數據流的吞吐量后，計算吞吐量平均值（Throughputaver），以獲得網絡傳輸數據流的公平性性能[13-14]。FSDT要實時更新，保證網絡公平性情況準確。

當有節點離開當前節點的偵聽范圍（即收不到RTS幀）時，刪除FSDT中的相關行。

表1 公平性狀況監測表FSDT

2.4 BFF算法流程

BFF算法利用RTS幀將各個節點對應數據流的周期吞吐量交換給鄰居節點，通過這種信息的交互得到臨近區域內的數據流吞吐量的平均值[15-17]。同時，節點計算當前數據流吞吐量變化率，判斷是否需要啟動算法。一旦啟動，就調整退避窗口最小值（CWmin）。接著利用吞吐量平均值作為衡量對象，求得流不公平度，判斷CWmin是否繼續調整。目的是使網絡傳輸的數據流公平地占用網絡資源，使被壓制的數據流增加訪問網絡的機會，消弱突發數據流對信道的壟斷，從而減小突發數據流對正在傳輸的數據流產生的影響。仿真采用單個節點作為觀察對象，但算法可以普適于網絡中任意節點，流程如圖4所示。

圖4 算法流程圖

3 算法仿真

3.1 網絡仿真場景設置

通過NS模擬器對基于流公平性改進的BFF退避算法進行性能仿真。設置如表2所示的網絡仿真場景。

表2 網絡仿真參數配置

其網絡拓撲結構如圖5所示。在第0～20 s網絡中只有 8個節點（如圖5（a）所示），初始狀態 8個節點位置隨機，數據流隨機。第20 s時，節點0和節點3加入（如圖5（b）所示），并開始由節點 0至節點 3發送數據。節點 0的發送會被節點 1、4、7偵聽到，這樣的情況下，數據流0→3為無線自組網常見的突發數據，節點0的發送干擾了節點1、4、7的發送，成為隱藏終端。本網絡為單跳網絡。

圖5 網絡拓撲結構圖

3.2 仿真結果及分析

IEEE 802.11采用的是BEB算法。首先仿真了BEB算法在如圖5所示的仿真場景中由隱藏終端帶來的流不公平現象。仿真結果如圖6所示。

圖6 BEB算法流間不公平現象

從圖6中可以看出，當第20 s節點0和節點3加入網絡后，阻塞了其他節點的正常數據傳輸。節點1的吞吐量迅速下降，直降為原來的10%，而數據流0→3則搶占了信道的使用權，節點3的吞吐量大幅上升，一直占有信道，造成節點4和節點7的吞吐量也有所下降。而節點0由于作為發送節點，沒有接收數據分組，所以吞吐量一直為0。

對圖5所示的仿真場景采用BFF算法解決由隱藏終端引起的流不公平問題進行了仿真，仿真結果如圖7所示。第20 s時，節點1的吞吐量變化率由于小于0.5，觸發了BFF算法，開始調整退避窗口最小值。在第40 s時，由于網絡公平性已經比較好，節點1的流不公平度小于0.1，停止調整退避窗口最小值。圖7與圖6對比可明顯看出，BFF算法較好地解決了新加入節點以及突發業務造成的流不公平問題。

圖7 BFF算法改進效果

如圖8所示為用公平性指數FI來衡量網絡流公平性的情況。圖中很直觀地體現了整個網絡的公平性程度的改進。從圖上可以看出，在第20 s時BEB算法的公平性指數驟然下降，這是由于出現了流不公平問題。而BFF算法在第20 s之前并沒有被觸發，所以與BEB算法公平性指數一樣。在第20 s之后，BFF算法被觸發，流不公平性問題得到緩解，公平性指數上升，直到第40 s處，算法認為流不公平問題得到解決，暫停調整退避窗口最小值，保持了公平性指數的相對穩定。

圖8 BFF算法在公平性指數上與BEB算法的比較

4 結束語

通過建立無線網絡碰撞模型對無線自組網中的數據流公平性進行了細致分析，并通過NS網絡模擬器仿真驗證了隱藏終端造成的網絡中傳輸數據流不公平的問題，這種情況是無線自組網中MAC機制帶來的流不公平問題。通過對流不公平問題進行建模分析，提出了一種通過調整退避窗口最小值改進流公平性的退避算法——BFF算法，軟件仿真分析結果驗證了該算法的有效性。通過與BEB算法的性能比較，BFF算法在提高流公平性，緩解由隱藏終端帶來的流不公平性問題上具有較好優勢。

[1]Wang Xiaodong，Yun Jun，Zhang Qi，et al.A cross-layer approach for efficient flooding in wireless sensor networks[C].Wireless Communications and Networking Conferenee，2005：1812-1817.

[2]BHARGHAVAN V，DEMERS A，SHENKER S，et al.MACAW： a media access protocol for wireless LAN′s[C].In Proceedings of ACM SIGCOMM′94，London，UK，1994：212-225.

[3]COLVIN A.CSMA with collision avoidance[J].Computer Communications，1983，16（5）： 27-35.

[4]柏詩玉，徐祎，朱浩.基于 DSR路由協議的跨層退避算法研究[J].計算機應用研究，2012（29）：55-56.

[5]黃家瑋，王建新.無線接入網絡中TCP流的上下行信道公平算法[J].小型微型計算機系統，2011，32（5）：5-7.

[6]黃家瑋.有線/無線網絡中TCP擁塞控制的公平性研究[D].長沙：中南大學，2010.

[7]于倩.基于 Ad Hoc網絡退避算法的研究[D].秦皇島：燕山大學，2012.

[8]劉濤.Ad hoc無線自組網的研究[D].無錫：江南大學，2011.

[9]李大鵬，袁濤，趙海濤.車載自組織網絡中基于鄰居節點數估計的最小競爭窗口調整算法[J].電信科學，2013（6）：14-15.

[10]袁濤.基于IEEE802_11p的車載自組網MAC層關鍵技術研究[D].南京：南京郵電大學，2013.

[11]張黎達.基于IEEE802_11MAC層協議的研究與實現[D].重慶：重慶大學，2008.

[12]呂軍.無線自組織網絡MAC層退避和競爭避免算法研究[D].合肥：中國科學技術大學，2009.

[13]唐勇，周滿元.Ad hoc網絡中MAC不公平性的研究與改進[J].計算機工程，2010，36（22）：100-102.

[14]曾海文，周滿元，唐勇.基于流的Ad hoc網絡接入公平性分析與研究[J].計算機工程，2011，37（2）：85-87.

[15]YASSEIN M B，OQAILY O A，MIN G.Enhanced fibonacci backoff algorithm for mobile Ad-Hoc network[C].10thInternational Conference on Computer and Information Technology，2010：749-754.

[16]李林韜，王呈貴，王先，等.無線組網中基于卡爾曼濾波有退避界限的MAC算法[J].軍事通信技術，2009，30（3）：11-17.

[17]ABDELKADER T，NAIK K，NAYAK A，et al.Adaptive backoff scheme for contention-based vehicular networks using fuzzy logic[C].FUZZ-IEEE，Korea，2009：1621-1626.