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

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

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