摘  要： 在無線自組織網(wǎng)絡(luò)中，合理的退避機制能夠有效地利用網(wǎng)絡(luò)資源，解決多個節(jié)點同時搶占共享信道的問題，提高網(wǎng)絡(luò)帶寬利用率。通過建立模型深入分析了由于隱藏終端產(chǎn)生的流不公平問題，給出了一種吞吐量變化率和流不公平度的度量，并提出了一種通過調(diào)整退避窗口最小值來改善流公平性的退避算法——BFF（Back-off based on Flow Fairness）算法。通過仿真分析表明算法能夠很好地提高公平性，解決BEB算法在實際運用中的流不公平問題。

　　關(guān)鍵詞： 無線自組織網(wǎng)絡(luò)；隱藏終端；退避算法；吞吐量變化率；流不公平度

0 引言

　　IEEE 802.11DCF是為無線局域網(wǎng)WLAN（Wireless LAN）制定的，但目前的無線自組織網(wǎng)絡(luò)中大都將其直接作為MAC接入規(guī)范，從而帶來公平性問題。公平性問題研究一般分為基于節(jié)點的公平性和基于流的公平性[1-2]兩種，最終都歸結(jié)為如何在MAC協(xié)議中確保每個節(jié)點或流的接入機率[3]相等。由于數(shù)據(jù)類型的多元化，支持服務(wù)質(zhì)量（QoS）的介質(zhì)訪問協(xié)議（Media Access 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)生嚴重的不公平性。不失一般性地，本文針對如圖1所示的一個典型網(wǎng)絡(luò)場景進行仿真分析實驗，針對節(jié)點使用共享信道帶寬的公平性問題進行建模，討論Rmax次嘗試傳輸失敗（RET事件）發(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來表示。

　　設(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幀到達節(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幀失敗（RET事件）的概率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）

　　已知連續(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嘗試傳輸失敗（RET事件）的概率與pn和Rmax有關(guān)，而pn與pkx、pky、prz、pku和pkv，以及它們的求和邊界有關(guā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達到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所示。可以看出，pRET對于CWmin的變化非常敏感。

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

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

　　（1）吞吐量變化率

　　BFF算法需要一個參數(shù)指標來判斷是否出現(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作為流不公平的衡量標準。

　　其中，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所示）。

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

　　獲得可偵聽范圍內(nèi)數(shù)據(jù)流的吞吐量后，每個節(jié)點維護一張公平狀況監(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ò)公平性情況準確。

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

　　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所示。

3 算法仿真

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

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

　　其網(wǎng)絡(luò)拓撲結(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ò)。

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

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

　　從圖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算法解決由隱藏終端引起的流不公平問題進行了仿真，仿真結(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ù)造成的流不公平問題。

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

4 結(jié)束語

　　通過建立無線網(wǎng)絡(luò)碰撞模型對無線自組網(wǎng)中的數(shù)據(jù)流公平性進行了細致分析，并通過NS網(wǎng)絡(luò)模擬器仿真驗證了隱藏終端造成的網(wǎng)絡(luò)中傳輸數(shù)據(jù)流不公平的問題，這種情況是無線自組網(wǎng)中MAC機制帶來的流不公平問題。通過對流不公平問題進行建模分析，提出了一種通過調(diào)整退避窗口最小值改進流公平性的退避算法——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] 張黎達.基于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].計算機工程，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]. 10th International 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.