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

徐立強，徐 祎，王 銳

（合肥電子工程學(xué)院，安徽 合肥 230037）

0 引言

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

1 IEEE 802.11 DCF公平性問題分析

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

圖1 Z字型網(wǎng)絡(luò)拓?fù)鋱D

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

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

1.1 節(jié)點1和節(jié)點2握手成功的充要條件

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

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

1.2 RET事件出現(xiàn)概率計算

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

當(dāng)Rmax給定時，節(jié)點1嘗試Rmax次發(fā)送RTS幀失?。≧ET事件）的概率 pRET：

n=1時，節(jié)點2收到節(jié)點3發(fā)出的RTS，根據(jù)節(jié)點 3傳輸該數(shù)據(jù)幀的時間啟動NAV計數(shù)器，節(jié)點2在計數(shù)器結(jié)束之前不偵聽信道。而節(jié)點1在節(jié)點3發(fā)完該數(shù)據(jù)幀前發(fā)送第一個RTS幀。所以節(jié)點2收不到節(jié)點1發(fā)送的 RTS 幀，故 p1=0。 n＞1 時，將式（1）、式（2）代入式（4），并令對應(yīng)的取 值 范 圍 為 ε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相應(yīng)的分布律為 pkx，pky，prz，pku，pkv，可得 pn：

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

1.3 RET事件發(fā)生概率分析

從1.2節(jié)可以看出，連續(xù) Rmax嘗試傳輸失?。≧ET事件）的概率與pn和Rmax有關(guān)，而pn與pkx、pky、prz、pku和pkv，以及它們的求和邊界有關(guān)，進(jìn)而可以發(fā)現(xiàn)pkx、pky、prz、pku和pkv與 tRTS、tCTS、tSIFS、tDIFS、tA、tD以及最小競爭窗口尺寸w有關(guān)。 由此 pRET可以看成與Rmax以及 tRTS、tCTS、tSIFS、tDIFS、tA、tD、最小競爭窗口大小w有關(guān)，其中除Rmax、tD和 w以外的參數(shù)都被802.11物理層規(guī)范所約束。又tD由MAC數(shù)據(jù)幀長決定，Rmax的變化對網(wǎng)絡(luò)的影響非常大，不僅影響MAC層傳輸時延，還會浪費節(jié)點能量，因而可以通過調(diào)整w達(dá)到pRET減小的效果。

當(dāng) 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次節(jié)點1嘗試發(fā)送RTS幀成功的概率pn隨w增大。同理，m≤n≤Rmax時pn也會增大。由此，w增大 pRET減小，但同時會增加重傳MAC幀的時延，因此需要兼顧pRET和MAC幀時延。

數(shù)值仿真計算得到的數(shù)據(jù)與仿真數(shù)據(jù)能夠較好地吻合，如圖2所示?？梢钥闯觯琾RET對于CWmin的變化非常敏感。

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

2.1 算法的重要參數(shù)指標(biāo)

（1）吞吐量變化率

圖2 pRET隨著CWmin變化情況

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

ThroughputT表示第T個周期內(nèi)的當(dāng)前節(jié)點吞吐量，ThroughputT+1表示第T+1個周期內(nèi)的當(dāng)前節(jié)點吞吐量。Th_Rate∈（-∞，0]，該點吞吐量增大；Th_Rate∈（0，啟動門限），該點吞吐量適當(dāng)減??；Th_Rate∈[啟動門限，1]，該點吞吐量急劇減小。

（2）流不公平度

定義一個新參數(shù)——流不公平度fs作為流不公平的衡量標(biāo)準(zhǔn)。

其中，ThroughputT為當(dāng)前考察數(shù)據(jù)流對應(yīng)的接收節(jié)點吞吐量，Throughputaver指可偵聽范圍內(nèi)節(jié)點接收的數(shù)據(jù)流吞吐量平均值。fs是該數(shù)據(jù)流吞吐量相對于數(shù)據(jù)流吞吐量平均值的差異，能夠有效地反映流公平性的情況，fs=0時為絕對公平。

2.2 RTS幀結(jié)構(gòu)

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

圖3 RTS數(shù)據(jù)包結(jié)構(gòu)

2.3 公平性狀況監(jiān)測表

獲得可偵聽范圍內(nèi)數(shù)據(jù)流的吞吐量后，每個節(jié)點維護(hù)一張公平狀況監(jiān)測表（Fairness State Detection Table，F(xiàn)SDT），如表1所示，用來儲存數(shù)據(jù)流的 ID和可偵聽節(jié)點對應(yīng)數(shù)據(jù)流的吞吐量。在初始化FSDT表時，獲得數(shù)據(jù)流的吞吐量后，計算吞吐量平均值（Throughputaver），以獲得網(wǎng)絡(luò)傳輸數(shù)據(jù)流的公平性性能[13-14]。FSDT要實時更新，保證網(wǎng)絡(luò)公平性情況準(zhǔn)確。

當(dāng)有節(jié)點離開當(dāng)前節(jié)點的偵聽范圍（即收不到RTS幀）時，刪除FSDT中的相關(guān)行。

表1 公平性狀況監(jiān)測表FSDT

2.4 BFF算法流程

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

圖4 算法流程圖

3 算法仿真

3.1 網(wǎng)絡(luò)仿真場景設(shè)置

通過NS模擬器對基于流公平性改進(jìn)的BFF退避算法進(jìn)行性能仿真。設(shè)置如表2所示的網(wǎng)絡(luò)仿真場景。

表2 網(wǎng)絡(luò)仿真參數(shù)配置

其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖5所示。在第0～20 s網(wǎng)絡(luò)中只有 8個節(jié)點（如圖5（a）所示），初始狀態(tài) 8個節(jié)點位置隨機，數(shù)據(jù)流隨機。第20 s時，節(jié)點0和節(jié)點3加入（如圖5（b）所示），并開始由節(jié)點 0至節(jié)點 3發(fā)送數(shù)據(jù)。節(jié)點 0的發(fā)送會被節(jié)點 1、4、7偵聽到，這樣的情況下，數(shù)據(jù)流0→3為無線自組網(wǎng)常見的突發(fā)數(shù)據(jù)，節(jié)點0的發(fā)送干擾了節(jié)點1、4、7的發(fā)送，成為隱藏終端。本網(wǎng)絡(luò)為單跳網(wǎng)絡(luò)。

圖5 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

3.2 仿真結(jié)果及分析

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

圖6 BEB算法流間不公平現(xiàn)象

從圖6中可以看出，當(dāng)?shù)?0 s節(jié)點0和節(jié)點3加入網(wǎng)絡(luò)后，阻塞了其他節(jié)點的正常數(shù)據(jù)傳輸。節(jié)點1的吞吐量迅速下降，直降為原來的10%，而數(shù)據(jù)流0→3則搶占了信道的使用權(quán)，節(jié)點3的吞吐量大幅上升，一直占有信道，造成節(jié)點4和節(jié)點7的吞吐量也有所下降。而節(jié)點0由于作為發(fā)送節(jié)點，沒有接收數(shù)據(jù)分組，所以吞吐量一直為0。

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

圖7 BFF算法改進(jìn)效果

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

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

4 結(jié)束語

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

[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路由協(xié)議的跨層退避算法研究[J].計算機應(yīng)用研究，2012（29）：55-56.

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

[6]黃家瑋.有線/無線網(wǎng)絡(luò)中TCP擁塞控制的公平性研究[D].長沙：中南大學(xué)，2010.

[7]于倩.基于 Ad Hoc網(wǎng)絡(luò)退避算法的研究[D].秦皇島：燕山大學(xué)，2012.

[8]劉濤.Ad hoc無線自組網(wǎng)的研究[D].無錫：江南大學(xué)，2011.

[9]李大鵬，袁濤，趙海濤.車載自組織網(wǎng)絡(luò)中基于鄰居節(jié)點數(shù)估計的最小競爭窗口調(diào)整算法[J].電信科學(xué)，2013（6）：14-15.

[10]袁濤.基于IEEE802_11p的車載自組網(wǎng)MAC層關(guān)鍵技術(shù)研究[D].南京：南京郵電大學(xué)，2013.

[11]張黎達(dá).基于IEEE802_11MAC層協(xié)議的研究與實現(xiàn)[D].重慶：重慶大學(xué)，2008.

[12]呂軍.無線自組織網(wǎng)絡(luò)MAC層退避和競爭避免算法研究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2009.

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

[14]曾海文，周滿元，唐勇.基于流的Ad hoc網(wǎng)絡(luò)接入公平性分析與研究[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]李林韜，王呈貴，王先，等.無線組網(wǎng)中基于卡爾曼濾波有退避界限的MAC算法[J].軍事通信技術(shù)，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.