一種多速率的ap主動隊列管理算法

1wla網(wǎng)絡(luò)中的時間公平主動陣列管理隨著無線網(wǎng)絡(luò)技術(shù)的成熟，無線網(wǎng)絡(luò)已融入internet，成為重要的組成部分。由于IEEE802.11等無線技術(shù)能讓用戶方便地接入Internet,這些技術(shù)已經(jīng)被廣泛地部署在學(xué)校、車站、機場、運動場等信息“熱點”地區(qū)。其中,WLAN作為目前最成熟的無線網(wǎng)絡(luò),已經(jīng)廣泛地運用到日常的生活中。然而,WLAN作為一種新的技術(shù)也面臨著一些新的問題。目前,WLAN普遍存在無線網(wǎng)絡(luò)和有線網(wǎng)絡(luò)的帶寬不對稱性和流量不對稱性。一方面,通常有線網(wǎng)絡(luò)的帶寬大于無線網(wǎng)絡(luò)的帶寬;另一方面,從有線網(wǎng)絡(luò)向無線網(wǎng)絡(luò)方向(下行)的數(shù)據(jù)流量要遠大于無線網(wǎng)絡(luò)向有線網(wǎng)絡(luò)方向(上行)的數(shù)據(jù)流量。從而很容易在AP(accesspoint)造成下行流擁塞,就會導(dǎo)致排隊延遲加長、大量丟包和吞吐率的下降。在IEEE802.11WLAN中,因為信號衰減以及干擾等原因,無線節(jié)點的信號傳輸質(zhì)量與其所在位置相關(guān)。目前在WLAN中廣泛采用自適應(yīng)速率選擇策略(如ARF、RBAR),它能根據(jù)特定時間內(nèi)外界因素來決定無線數(shù)據(jù)最佳發(fā)送速率,這就使得在WLAN中普遍存在不同數(shù)據(jù)傳輸速率。而在多速率WLAN中,低速傳輸?shù)牧鲿加么罅康男诺罆r間,無形中擠占了高速傳輸流的信道時間,這樣不但WLAN總體吞吐率的急劇下降,而且下行高速流的包大部分時間只能在AP排隊等待信道變得可用,進一步加劇AP的擁塞。為此,各國學(xué)者針對這些問題提出了改進辦法,雖然在某些方面也上獲得了較好的效果,但仍面臨著擁塞導(dǎo)致網(wǎng)絡(luò)效率低和流之間公平性無法保證等問題。本文在詳細分析WLAN網(wǎng)絡(luò)中擁塞控制和公平性策略的研究成果基礎(chǔ)上,提出一種在AP上的時間公平主動隊列管理(TFRED,temporalfairRED)算法,既能避免或緩解擁塞,又可以保證各無線節(jié)點的時間公平性,提高了網(wǎng)絡(luò)的整體效率;同時能懲罰惡意的UDP流,保護TCP流的吞吐率。2關(guān)于研究現(xiàn)狀經(jīng)過多年的研究發(fā)展,針對WLAN出現(xiàn)了大量的改進方法和增強策略。其中,針對擁塞控制和時間公平這2個問題,主要做了以下的研究。2.1通過ap上的嚴(yán)格控制在WLAN中,下行流的數(shù)據(jù)包和上行TCP流的ACK包都要由AP發(fā)送,很容易造成AP緩存的擁塞。如果對AP的緩存實施擁塞控制,就能有效地避免或緩解WLAN的擁塞。在有線網(wǎng)絡(luò)主動隊列管理機制中,各輸出流在相同的有線鏈路上發(fā)送,具有相等的發(fā)送速率。FDA、RateAdaptiveSnoop和VQ-RED等算法沿用有線網(wǎng)絡(luò)中公平擁塞控制的思路,在AP上實施擁塞控制,同時保證通過AP的下行流吞吐率公平。FDA算法中,當(dāng)AP出現(xiàn)下行流擁塞時,由AP向下行TCP的發(fā)送端重復(fù)發(fā)送3次收到的ACK包副本。由于吞吐率較大的TCP流的ACK包到達AP可能性較大,吞吐率較大流降速的可能性也就較高,從而提高各流的吞吐率公平。RateAdaptiveSnoop在AP上將無線信道帶寬和AP可用緩存平均分配給各流,用ACK的通告窗口把分配給各流的帶寬延時乘積反饋給TCP發(fā)送端,保證各流的吞吐率公平。VQ-RED對通過AP的單流運用RED擁塞控制算法,為每流設(shè)置相同的丟棄門限,確保每流的吞吐率公平。但實際上在多速率WLAN中,通過AP的下行流雖然共享同一無線信道,但有不同的發(fā)送速率。如果在WLAN中保證發(fā)送速率不同的單流間吞吐率公平,反而會讓慢速發(fā)送的流長期占用無線信道,導(dǎo)致網(wǎng)絡(luò)總體效率低下。因此,在AP上保證吞吐率公平的擁塞控制管理算法完全忽視了目前WLAN中多種速率共存的實際情況,并不適用于目前普遍存在的多速率WLAN。2.2時間公平的mac層協(xié)議在多速率無線網(wǎng)絡(luò)中實現(xiàn)時間公平的核心思想是增加高速信道節(jié)點的發(fā)送概率,減少低速信道節(jié)點的發(fā)送概率,目的是保證各節(jié)點實現(xiàn)依據(jù)其信道速率的比例公平,即保證各節(jié)點占有相等長度的無線信道時間。相對于吞吐率公平,雖然會降低慢速信道節(jié)點的吞吐率,但由于避免了慢速信道節(jié)點占據(jù)不公平的信道時間,時間公平的策略保護了快速信道節(jié)點的吞吐率,從而提高網(wǎng)絡(luò)總吞吐率。目前已有保證時間公平的MAC層相關(guān)改進協(xié)議,這些協(xié)議依據(jù)各無線節(jié)點的信道速率來設(shè)置各節(jié)點不同競爭窗口大小、幀間的時隙長度和每次發(fā)送包的個數(shù)等MAC層參數(shù),保證各節(jié)點占用相等的無線信道時間。典型的時間公平的MAC層協(xié)議包括OAR、Idlesense、802.11e協(xié)議改進。但修改MAC層協(xié)議需要大范圍更新網(wǎng)絡(luò)設(shè)備,因此目前不大可能推廣應(yīng)用。在已有的多速率WLAN的AP隊列管理算法中,TTPDE算法在AP擁塞丟包時選擇丟棄發(fā)送延時最大的包,AP在發(fā)送包時選擇發(fā)送延時最小的包發(fā)送。這種極端的方法讓快速流盡量長時間占據(jù)信道,盡最大可能提高網(wǎng)絡(luò)效率,但同時有可能造成低速節(jié)點長期處于“餓死”狀態(tài),完全犧牲公平性。另外,在AP上利用隊列調(diào)度算法能夠保證時間公平,但這些算法并不能解決AP隊列的擁塞問題。針對上述問題,本文設(shè)計的目標(biāo)是:對于造成擁塞的下行流,設(shè)計一種在AP上的時間公平主動隊列管理算法,同時解決擁塞和公平性問題,簡單而有效地實現(xiàn)效率和公平性的雙贏。3基于時間公平的tranet算法3.1tf監(jiān)測技術(shù)如圖1所示,TFRED算法的核心思想是:當(dāng)下行流在AP發(fā)生擁塞時,TFRED算法依據(jù)AP的無線信道數(shù)據(jù)發(fā)送速率,以較低的丟包概率隨機丟棄高速發(fā)送流中的包,以較高的丟包概率隨機丟棄低速發(fā)送流中的包,將各流隊列長度穩(wěn)定在各自理想的目標(biāo)值,保證各流占用無線信道時間相等,并能有效避免AP上的擁塞。需要指出的是,發(fā)送到各無線節(jié)點的包在AP中并不需要真正按流來形成隊列,AP只需要統(tǒng)計目前在緩存等待發(fā)送到各無線節(jié)點的包的個數(shù)(各流“虛隊列”的長度)。同時為了避免死鎖和全局同步,采用了隨機丟棄的方法丟棄緩存單流隊列中數(shù)據(jù)包。TFRED算法如圖2所示,具體實現(xiàn)過程如下。1)當(dāng)包到達AP時,被按目的節(jié)點分成單流,并且根據(jù)每流的無線信道發(fā)送速率r計算每流的目標(biāo)隊列長度l。2)根據(jù)緩存中聚集流的當(dāng)前隊列長度判斷是否擁塞。如果擁塞,計算丟棄概率pdrop,并選擇當(dāng)前隊列長度與目標(biāo)隊列長度之差最大的單流,依據(jù)丟棄概率pdrop,隨機丟棄該單流的一個包,同時不論是否擁塞,將到達包入隊。3.2基于tov的策略在TFRED算法中,依據(jù)AP的無線信道發(fā)送速率來計算各流的目標(biāo)隊列長度。定義1802.11WLAN中,如果忽略傳輸時延,向節(jié)點i發(fā)送一個數(shù)據(jù)包的信道占用時間tchannel由發(fā)送時延ttr和控制開銷時延tov組成,記為其中,發(fā)送延時Sd為發(fā)送數(shù)據(jù)包的大小,ri為AP第i流無線信道發(fā)送速率。控制開銷延時tov包括節(jié)點的隨機退避延時和控制幀發(fā)送延時。在MAC層采用RTS/CTS機制,在沒有數(shù)據(jù)包碰撞,并且在退避時間服從均勻分布的情況下,退避時間取平均值CWmin×Slot/2。因此,tov可以認為是一個常數(shù)。例如,IEEE802.11b標(biāo)準(zhǔn)設(shè)置如表1所示,則tov=3×SIFS+定義2假設(shè)AP采用先進先出調(diào)度算法,AP發(fā)送第i流中包的概率pi為其中,li是第i流的當(dāng)前隊列長度,n是當(dāng)前通過AP的流的數(shù)目,是當(dāng)前聚集流隊列的總長度。定義3假設(shè)各流的數(shù)據(jù)包大小相等,第i流的無線信道占用時間Ti為其中,T為所有流占用信道的總時間。由式(2)、式(3)可知,為了使得不同速率的流占用相等的信道時間,AP緩存中每流的隊列長度li應(yīng)與成反比。這樣可以計算出第i流目標(biāo)隊列長度為其中,L是AP緩存中聚集流的目標(biāo)隊列長度。依據(jù)RED算法的參數(shù),將L設(shè)為4總吞吐率對比在多速率WLAN中,吞吐率公平的算法保證各流的吞吐率相等,但會導(dǎo)致慢速流壓制了快速流的吞吐率;時間公平的算法保證各流的信道占用時間相等,保護了各單流的吞吐率不會受其他節(jié)點影響。下面給出采用吞吐率公平和時間公平算法的網(wǎng)絡(luò)總吞吐率比較。假設(shè)從有線網(wǎng)絡(luò)向WLAN中各節(jié)點分別發(fā)送n條流,各流傳輸?shù)臄?shù)據(jù)包大小都是Sd,AP發(fā)送各流數(shù)據(jù)的速率分別為r1,r2,…,rn。由3.2節(jié)中的分析得到每發(fā)送一個數(shù)據(jù)包的吞吐率ti為如果保證時間公平,各流占用的信道時間相等,則時間公平的WLAN總吞吐率為:由式(5)、式(6)可知,當(dāng)r1=r2=…=rn時,Ttf=Trf。由此可見,如果向各節(jié)點發(fā)送速率相同,保證各節(jié)點時間公平其實就是保證了吞吐率公平。但如果速率存在差異,采用時間公平比吞吐率公平的網(wǎng)絡(luò)效率高。5基于ap的算法仿真實驗為了驗證算法的有效性,利用網(wǎng)絡(luò)仿真軟件NS2.27實現(xiàn)了TFRED算法,并與RED、VQ-RED、TTPDE算法進行性能比較。其中,RED作為經(jīng)典的擁塞控制算法,VQ-RED代表了吞吐率公平算法,TTPDE則是完全犧牲公平追求效率的算法。在仿真實驗中,每個移動節(jié)點包括AP采用的協(xié)議如圖3所示。路由協(xié)議采用NOAd-HocRouting(NOAH),MAC層采用IEEE802.11b協(xié)議。隊列位于LL層和MAC層之間。無線信道速率調(diào)節(jié)算法采用RBAR,信號傳播模型采用Ricean衰落信道模型。同時為了降低多路徑衰減,將Ricean模型中主徑衰落因子設(shè)為較大的值256。5.1節(jié)點e和ap之間的速率實驗1比較了AP采用RED、VQ-RED、TTPDE和TFRED時各無線節(jié)點吞吐率,實驗的網(wǎng)絡(luò)拓撲如圖4所示。實驗場景設(shè)置節(jié)點A~E到AP的距離分別是:10m、60m、80m、102m和10m。因此各節(jié)點和AP之間的速率分別是:11Mbit/s、5.5Mbit/s、2Mbit/s、1Mbit/s和11Mbit/s。模擬實驗開始后,節(jié)點E以1m/s的速率移動遠離AP,這時,節(jié)點E和AP之間的速率從11Mbit/s逐步降至5.5Mbit/s、2Mbit/s、1Mbit/s。有線鏈路帶寬都是25Mbit/s,延時為1ms。AP緩存容量為100個包。設(shè)置RED、VQ-RED和TFRED算法參數(shù)為:wq=0.002,minth=40,maxth=60,maxp=0.1。5.1.1節(jié)點間的數(shù)據(jù)發(fā)送速率首先設(shè)置5條UDP流1~5,分別從節(jié)點1~5到節(jié)點A~E。每流帶寬為5Mbit/s,數(shù)據(jù)包大小為1000字節(jié)。圖5(a)顯示當(dāng)AP使用RED算法時,各節(jié)點的吞吐率雖然變化較大,但總體趨勢都是隨著節(jié)點E的移動而下降。從圖5(b)可以看出當(dāng)AP使用VQ-RED算法時,各節(jié)點的吞吐率基本相同,都隨著節(jié)點E的移動而下降。這是由于VQ-RED算法使用較多的較為準(zhǔn)確的流狀態(tài)信息,使各節(jié)點獲取相同的吞吐率,但結(jié)果卻反而壓制了快速節(jié)點的吞吐率。圖5(c)顯示當(dāng)AP使用TTPDE算法時,保證了快速節(jié)點的吞吐率,但大大壓制其他慢速節(jié)點的吞吐率。而圖5(d)顯示當(dāng)AP使用TFRED算法時,各節(jié)點的吞吐率和其數(shù)據(jù)速率相關(guān)。由于TFRED算法考慮了各節(jié)點的情況,保證各節(jié)點的時間公平,當(dāng)節(jié)點E的數(shù)據(jù)發(fā)送速率下降,而其他靜止節(jié)點的數(shù)據(jù)發(fā)送速率不變時,TFRED算法能夠確保靜止節(jié)點的吞吐率不會降低。同時節(jié)點的數(shù)據(jù)發(fā)送速率下降意味著AP發(fā)送到節(jié)點E的數(shù)據(jù)包數(shù)減少,從而減小了AP和節(jié)點E之間通信控制開銷,其他靜止節(jié)點得到更多的信道資源,提高了靜止節(jié)點的吞吐率。從圖5(e)可以看出TFRED算法相對RED、VQ-RED算法網(wǎng)絡(luò)總吞吐率平均提升40%,這是由于TFRED算法保護靜止節(jié)點吞吐率不會下降,從而大大提高網(wǎng)絡(luò)整體效率。5.1.2般網(wǎng)絡(luò)接收點設(shè)置5條TCP流1~5,分別從節(jié)點1~5到節(jié)點A~E。節(jié)點移動和位置如圖4所示,節(jié)點E移動,其他節(jié)點靜止,數(shù)據(jù)包大小為1000字節(jié)。統(tǒng)計在4種算法下5條TCP流的平均吞吐率和網(wǎng)絡(luò)平均吞吐率如圖6所示。盡管TCP流由于在AP的擁塞和信道速率變化而出現(xiàn)抖動,但從圖6可以看出,TFRED算法仍然能夠使得TCP流的吞吐率依據(jù)其發(fā)送速率形成“梯度”,保證了網(wǎng)絡(luò)總吞吐率相對RED和VQ-RED算法的網(wǎng)絡(luò)總吞吐率較高。TTPDE算法雖然獲取了最高的吞吐率,但這完全是以犧牲慢速的TCP吞吐率為代價。5.1.3節(jié)點移動場景下實驗結(jié)果為了比較算法在多種流共存時的性能,設(shè)置4條TCP流和1條發(fā)送速率為2Mbit/s的UDP流。TCP流1~4分別從節(jié)點1~4到節(jié)點A~D,UDP流從節(jié)點5到節(jié)點E,節(jié)點移動和位置如圖4所示,節(jié)點E移動,其他節(jié)點靜止。實驗結(jié)果如圖7、圖8所示。從實驗結(jié)果看,在UDP流節(jié)點移動場景中,由于RED算法無法懲罰非響應(yīng)的UDP流,導(dǎo)致UDP流壓制其他TCP流;VQ-RED算法為了保證各流公平性,犧牲了網(wǎng)絡(luò)的總體效率,網(wǎng)絡(luò)總吞吐率最低;TTPDE算法獲得的網(wǎng)絡(luò)總吞吐率是最高的,但慢速TCP流幾乎“餓死”;而TFRED算法保證各流的信道時間公平,有效地壓制了UDP流,保護了TCP流,同時在TCP流中依據(jù)發(fā)送速率分配信道占用時間,獲得了較好的網(wǎng)絡(luò)效率。5.2udp流測試實驗2用5條UDP流測試采用RED、VQ-RED、TTPDE和TFRED時各無線節(jié)點的時間公平性和吞吐率公平性,目的是驗證TFRED算法既能保證多速率無線節(jié)點的時間公平,又能保證相同速率無線節(jié)點吞吐率公平。實驗的網(wǎng)絡(luò)拓撲如圖9所示。實驗場景設(shè)置除了節(jié)點A~D到AP的距離都是10m外,其他設(shè)置都與實驗1的UDP流測試場景相同。實驗采用公平性因子對時間公平性和吞吐率公平性進行量化。假設(shè)各個無線節(jié)點n1,